~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina5/tina-libs/tina/geometry/geomCurve_conicprox.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  * 
  3  * This file is part of the TINA Open Source Image Analysis Environment
  4  * henceforth known as TINA
  5  *
  6  * TINA is free software; you can redistribute it and/or modify
  7  * it under the terms of the GNU Lesser General Public License as 
  8  * published by the Free Software Foundation.
  9  *
 10  * TINA is distributed in the hope that it will be useful,
 11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 13  * GNU Lesser General Public License for more details.
 14  *
 15  * You should have received a copy of the GNU Lesser General Public License
 16  * along with TINA; if not, write to the Free Software Foundation, Inc., 
 17  * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  *
 19  **********
 20  * 
 21  * Program :    TINA
 22  * File    :  $Source: /home/tina/cvs/tina-libs/tina/geometry/geomCurve_conicprox.c,v $
 23  * Date    :  $Date: 2008/12/16 11:34:54 $
 24  * Version :  $Revision: 1.4 $
 25  * CVS Id  :  $Id: geomCurve_conicprox.c,v 1.4 2008/12/16 11:34:54 neil Exp $
 26  *
 27  * Author  : Legacy TINA
 28  *
 29  * Notes :
 30  *
 31  *********
 32 */
 33 
 34 #include "geomCurve_conicprox.h"
 35 
 36 #if HAVE_CONFIG_H
 37   #include <config.h>
 38 #endif
 39 
 40 #include <math.h>
 41 #include <tina/sys/sysDef.h>
 42 #include <tina/sys/sysPro.h>
 43 #include <tina/math/mathDef.h>
 44 #include <tina/math/mathPro.h>
 45 #include <tina/geometry/geomDef.h>
 46 #include <tina/geometry/geom_LineDef.h>
 47 #include <tina/geometry/geom_LinePro.h>
 48 #include <tina/geometry/geom_CurveDef.h>
 49 #include <tina/geometry/geomCurve_conic.h>
 50 #include <tina/geometry/geomCurve_con_util.h>
 51 #include <tina/geometry/geomCurve_con_fltr.h>
 52 #include <tina/geometry/geomCurve_conic_5pt.h>
 53 
 54 
 55 static int init_sample = 12;                    /* static data! */
 56 static double min_aratio = 0.2;                 /* static data! */
 57 #define MAX_DIST 200000
 58 
 59 void    conic_prox_init_sample_set(int sample)
 60 {
 61     init_sample = sample;
 62 }
 63 
 64 /* approximate square of distance of point p to conic */
 65 static double conic_sqrdist_check(Conic * conic, Vec2 p)
 66 {
 67     double  t;
 68     Vec2    pc = {Vec2_id};
 69 
 70     t = conic_param(conic, p);
 71     pc = conic_point(conic, t);
 72     return (vec2_sqrdist(p, pc));
 73 }
 74 
 75 /* grow the conic along the implicit string between start and end
 76  * 
 77  * initial points are given through p1 and p2 (these are updated)
 78  * 
 79  * a form of hystersis thresholding is employed
 80  * 
 81  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
 82  * until hi_th (high thres) is exceeded the point of segmentation is
 83  * set to the last point lo_th was exceeded */
 84 Bool    conic_grow_string(Conic * conic, List * start, List * end, List ** p1, List ** p2, double lo_th, double hi_th, int max_div)
 85 {
 86     Vec2    p = {Vec2_id};
 87     List *ptr;
 88     double  sqr_dist;
 89     List *m1 = *p1;
 90     List *m2 = *p2;
 91     Bool    grown = false;
 92 
 93     /** grow backwards **/
 94     for (ptr = m1; ptr != start;)
 95     {
 96         int     misses = 0;
 97 
 98         ptr = ptr->last;
 99         DD_GET_POS2(ptr, p);
100         sqr_dist = conic_sqrdist_check(conic, p);
101         if (sqr_dist > hi_th)
102             break;
103         if (sqr_dist < lo_th)
104         {
105             grown = true;
106             misses = 0;
107             m1 = ptr;
108         } else
109             ++misses;
110         if (misses > max_div)
111             break;
112     }
113 
114     /** grow forwards **/
115     for (ptr = m2; ptr != end;)
116     {
117         int     misses = 0;
118 
119         ptr = ptr->next;
120         DD_GET_POS2(ptr, p);
121         sqr_dist = conic_sqrdist_check(conic, p);
122         if (sqr_dist > hi_th)
123             break;
124         if (sqr_dist < lo_th)
125         {
126             grown = true;
127             misses = 0;
128             m2 = ptr;
129         } else
130             ++misses;
131         if (misses > max_div)
132             break;
133     }
134 
135     *p1 = m1;
136     *p2 = m2;
137 
138     if (grown || prop_get(conic->props, STRING) == NULL)
139         /** replace string on proplist and reset ends **/
140     {
141         Vec2    e1 = {Vec2_id};
142         Vec2    e2 = {Vec2_id};
143         Vec2    emid = {Vec2_id};
144 
145         conic->props = proplist_rm(conic->props, STRING);
146         conic->props = proplist_add(conic->props,
147           (void *) str_make(STRING, m1, m2), STRING, str_rm_only_str);
148         DD_GET_POS2(m1, e1);
149         DD_GET_POS2(m2, e2);
150         DD_GET_POS2(ddstr_mid_point(m1, m2), emid);
151         conic_set_ends(conic, e1, e2, emid);
152     }
153     return (grown);
154 }
155 
156 /* grow the conic along the implicit string between start and end
157  * 
158  * initial points are given through p1 and p2 (these are updated)
159  * 
160  * actual growing is done by conic_grow_string
161  * 
162  * the function iterates throgh new conic fits to the string */
163 Conic  *conic_grow(Conic * conic, List * start, List * end, List ** p1, List ** p2, double lo_th, double hi_th, int max_div)
164 {
165     Bool    updated;
166     List *m1 = *p1;
167     List *m2 = *p2;
168 
169     do
170     {
171         Bool    string_grown;
172 
173         /** grow start and end along conic **/
174         string_grown = conic_grow_string(conic, start, end, &m1, &m2,
175                                          lo_th, hi_th, max_div);
176 
177         if (string_grown)       /** fit a new conic and see if still good **/
178         {
179             Conic  *new_conic = ddstr_conic_ellipse_5pt(m1, m2, min_aratio);
180 
181             conic_ellipse_filter(new_conic, m1, m2, min_aratio);
182 
183             if (new_conic != NULL &&
184                 conic_check(new_conic, m1, m2, lo_th, hi_th, max_div))
185             {
186                 updated = true;
187                 conic_free(conic);
188                 conic = new_conic;
189             } else
190             {
191                 updated = false;
192                 if (new_conic != NULL)
193                     conic_free(new_conic);
194             }
195         } else
196             updated = false;
197     } while (updated);
198 
199     *p1 = m1;
200     *p2 = m2;
201 
202     return (conic);
203 }
204 
205 /* check that the conic fits the implicit string start and end
206  * 
207  * a form of hystersis thresholding is employed
208  * 
209  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
210  * until hi_th (high thres) is exceeded */
211 Bool    conic_check(Conic * conic, List * start, List * end, double lo_th, double hi_th, int max_div)
212 {
213     Vec2    pos = {Vec2_id}, pmid = {Vec2_id};
214     List *dptr;
215     double  sqr_dist;
216     int     misses = 0;
217     double t, min_dist = MAX_DIST, diff;
218 
219 
220     t = conic->t1 + (conic->t2 - conic->t1)/2.0;
221     pmid = conic_point(conic, t);
222 
223     for (dptr = start;; dptr = dptr->next)
224     {
225         DD_GET_POS2(dptr, pos);
226         sqr_dist = conic_sqrdist_check(conic, pos);
227         if (sqr_dist > hi_th)
228             return (false);
229         if (sqr_dist > lo_th)
230             ++misses;
231         else
232             misses = 0;
233         if (misses > max_div)
234             return (false);
235 /* check for closest point to middle NAT 11/11/08 */
236         diff = vec2_sqrdist(pos, pmid);
237         if (diff < min_dist)
238             min_dist = diff;
239 
240         if (dptr == end)
241             break;
242     }
243     pos = conic_point(conic, conic->t1);
244     diff = vec2_sqrdist(pos, pmid);
245 
246     if (min_dist > diff/4.0) /* data is on the other side of the elipse!! NAT */
247        return(false);
248     else 
249        return (true);
250 }
251 
252 /* check that the conic fits the list of strings
253  * 
254  * a form of hystersis thresholding is employed
255  * 
256  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
257  * until hi_th (high thres) is exceeded
258  * 
259  * furthermore each string can deviate from the conic close to its
260  * endpoints */
261 Bool    conic_check_list(Conic * conic, List * strings, double lo_th, double hi_th, int max_div)
262 {
263     Vec2    pos = {Vec2_id};
264     List *dptr;
265     double  sqr_dist;
266     int     misses = 0;
267     List   *ptr;
268 
269     for (ptr = strings; ptr != NULL; ptr = ptr->next)
270     {
271         Tstring *str = (Tstring *) ptr->to;
272         int     start_div, end_div, i;
273 
274         start_div = str->count / 5;
275         end_div = str->count - start_div;
276 
277         for (i = 0, dptr = str->start; i < start_div; ++i)
278             dptr = dptr->next;
279 
280         for (; i < end_div; i++, dptr = dptr->next)
281         {
282             DD_GET_POS2(dptr, pos);
283             sqr_dist = conic_sqrdist_check(conic, pos);
284 
285             if (sqr_dist > hi_th)
286                 return (false);
287 
288             if (sqr_dist > lo_th)
289                 ++misses;
290             else
291                 misses = 0;
292 
293             if (misses > max_div)
294                 return (false);
295         }
296     }
297 
298     return (true);
299 }
300 
301 /* count the number of points (at the sample frequency) that are close
302  * to the conic */
303 int     conic_count(Conic * conic, List * start, List * end, int sample, double thres_sqr)
304 {
305     Vec2    p = {Vec2_id};
306     int     count = 0;
307     List *dptr;
308     int     i;
309 
310     for (dptr = start;;)
311     {
312         DD_GET_POS2(dptr, p);
313         if (conic_sqrdist_check(conic, p) < thres_sqr)
314             ++count;
315 
316         if (dptr == end)
317             break;
318 
319         for (i = 0; i < sample; ++i, dptr = dptr->next)
320             if (dptr == end)
321                 break;
322     }
323     return (count);
324 }
325 
326 #if 0
327 static Bool is_straight(List * dd1, List * dd2, List * dd3, double thres)
328 {
329     Vec2    p1 = {Vec2_id};
330     Vec2    p2 = {Vec2_id};
331     Vec2    p3 = {Vec2_id};
332     Vec2    v = {Vec2_id};
333 
334     DD_GET_POS2(dd1, p1);
335     DD_GET_POS2(dd2, p2);
336     DD_GET_POS2(dd3, p3);
337     v = vec2_unit(vec2_diff(p3, p1));
338     return (fit2_point_on_line(p2, v, p1, thres));
339 }
340 
341 #endif
342 
343 List *conic_prox(List * start, List * end, int sample, double lo_th, double hi_th, int max_div)
344 {
345     List *p1;
346     List *p2;
347     List *m1;
348     List *m2;
349     List *list1 = NULL;
350     List *list2 = NULL;
351     Conic  *conic = NULL;
352     double  lo_sqth = lo_th * lo_th;
353     double  hi_sqth = hi_th * hi_th;
354     int     i, maxcount = 0;
355 
356     if (start == NULL || end == NULL || start == end)
357         return (NULL);
358 
359     p1 = start;
360     p2 = ddstr_nth_point(start, end, 4 * sample + 1);
361     if (p2 == NULL)
362         p2 = end;
363 
364     while (1)
365     {
366 
367         /* if (is_straight(p1, ddstr_mid_point(p1, p2), p2, lo_th)) {
368          * if (p2 == end) break; for (i = 0; i < sample; ++i) { p1 =
369          * p1->next; p2 = p2->next; if (p2 == end) break; } continue; } */
370         conic = ddstr_conic_ellipse_5pt(p1, p2, min_aratio);
371         if (conic != NULL &&
372             conic_check(conic, p1, p2, lo_sqth, hi_sqth, max_div))
373         {
374             int     count = conic_count(conic, start, end, sample / 2, lo_sqth);
375 
376             if (count > maxcount)
377             {
378                 maxcount = count;
379                 m1 = p1;
380                 m2 = p2;
381             }
382         }
383         conic_free(conic);
384         conic = NULL;
385 
386         if (p2 == end)
387             break;
388 
389         for (i = 0; i < sample; ++i)
390         {
391             p1 = p1->next;
392             p2 = p2->next;
393             if (p2 == end)
394                 break;
395         }
396     }
397 
398     if (maxcount >= 5)
399     {
400         conic = ddstr_conic_ellipse_5pt(m1, m2, min_aratio);
401         conic = conic_grow(conic, start, end, &m1, &m2,
402                            lo_sqth, hi_sqth, max_div);
403 
404         if (conic != NULL && conic->type != ELLIPSE)
405         {
406             if (fabs(conic->t1) > 2 || fabs(conic->t2) > 2)
407             {
408                 conic_free(conic);
409                 conic = NULL;
410             }
411         }
412     }
413     if (conic == NULL)          /* failed */
414     {
415         sample = (int)(sample*0.75);            /* increase sample frequency */
416         if (sample >= 3)
417             return (conic_prox(start, end, sample, lo_th, hi_th, max_div));
418         return (linear_prox(start, end, (float)lo_th, init_sample));
419     }
420     if (m1 != start)
421         list1 = conic_prox(start, m1, sample,
422                            lo_th, hi_th, max_div);
423     if (m2 != end)
424         list2 = conic_prox(m2, end, sample,
425                            lo_th, hi_th, max_div);
426 
427     return (dd_append(list1, dd_append(dd_link_alloc((void *) conic, CONIC2), list2)));
428 }
429 
430 Tstring *conic_string(Tstring * string, int init_smpl, double lo_th, double hi_th, int max_div)
431 {
432     List *conic;
433 
434     if (string == NULL)
435         return (NULL);
436 
437     init_sample = init_smpl;
438 
439     conic = conic_prox(string->start, string->end, init_sample,
440                        lo_th, hi_th, max_div);
441 
442     if (conic == NULL)
443         return (NULL);
444 
445     return (str_make(STRING, conic, dd_get_end(conic)));
446 }
447 
448 List   *conic_strings(List * strings, int init_smpl, double lo_th, double hi_th, int max_div)
449 {
450     List   *sptr;
451     List   *splist = NULL;
452 
453     for (sptr = strings; sptr != NULL; sptr = sptr->next)
454     {
455         Tstring *string = (Tstring *) sptr->to;
456 
457         string = conic_string(string, init_smpl, lo_th, hi_th, max_div);
458         splist = ref_addtostart(splist, (void *) string, STRING);
459     }
460     return (splist);
461 }
462 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.