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

Linux Cross Reference
Tina5/tina-libs/tina/geometry/geomCurve_curvprox.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_curvprox.c,v $
 23  * Date    :  $Date: 2005/01/09 17:49:25 $
 24  * Version :  $Revision: 1.3 $
 25  * CVS Id  :  $Id: geomCurve_curvprox.c,v 1.3 2005/01/09 17:49:25 paul Exp $
 26  *
 27  * Author  : Legacy TINA
 28  *
 29  * Notes :
 30  *
 31  *********
 32 */
 33 
 34 #include "geomCurve_curvprox.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_GenDef.h>
 47 #include <tina/geometry/geom_GenPro.h>
 48 #include <tina/geometry/geom_CurveDef.h>
 49 #include <tina/geometry/geomCurve_conic.h>
 50 #include <tina/geometry/geomCurve_conic_5pt.h>
 51 #include <tina/geometry/geomCurve_con_util.h>
 52 #include <tina/geometry/geomCurve_con_fltr.h>
 53 #include <tina/geometry/geomCurve_conicprox.h>
 54 
 55 
 56 static double long_length = 100.0;      /* cant be a conic */                           /* static data! */
 57 static double short_length = 20.0;                                                                              /* static data! */
 58 static double ignore_length = 10.0;     /* debris of fiting */                          /* static data! */
 59 static double conic_thres = 0.2;        /* residual threshold for conic */      /* static data! */
 60 static double resid_ratio = 1.0;        /* conservative threshold */            /* static data! */
 61 static double dot_thres_hi = 0.95;                                                                              /* static data! */
 62 static double dot_thres_low = 0.8;                                                                              /* static data! */
 63 static double len_ratio_thres = 3.0;                                                                    /* static data! */
 64 
 65 
 66 /***** PAB: what's this for? Simpel misordered functions, or something more sinister? ****/
 67 
 68 extern void poly_con_grow_conics(Tstring * string,
 69     int sample, double low_th, double up_th, int max_div);
 70 
 71 double max_ratio(double x, double y)
 72 {
 73     double ratio = fabs(x / y);
 74     return ((ratio < 1.0) ? 1 / ratio : ratio);
 75 }
 76 
 77 /* compute residual of line fit to underlying edge strings, may be subsampled */
 78 static double line_pair_residual(Line2 * l1, Line2 * l2,
 79     Tstring * s1, Tstring * s2)
 80 {
 81     List *end;
 82     List *dptr;
 83     int     n;
 84     double  p, p2_sum = 0;      /* perpendicular statistics */
 85     Vec2    q = {Vec2_id};
 86 
 87     end = s1->end;
 88     for (n = 2, dptr = s1->start;; dptr = dptr->next, ++n)
 89     {
 90         DD_GET_POS2(dptr, q);
 91         p = vec2_dist_point_line(q, l1->p1, l1->v);
 92         p2_sum += p * p;
 93         if (dptr == end)
 94             break;
 95     }
 96 
 97     end = s2->end;
 98     for (dptr = s2->start;; dptr = dptr->next, ++n)
 99     {
100         DD_GET_POS2(dptr, q);
101         p = vec2_dist_point_line(q, l2->p1, l2->v);
102         p2_sum += p * p;
103         if (dptr == end)
104             break;
105     }
106     return ((n == 0) ? 0.0 : sqrt(p2_sum / n));
107 }
108 
109 /* compute residual of conic fit to underlying edge string */
110 static double conic_residual(Conic * conic, List * start, List * end)
111 {
112     List *dptr;
113     int     n;
114     double  p2_sum = 0;         /* perpendicular staistics */
115 
116     for (n = 1, dptr = start;; dptr = dptr->next, ++n)
117     {
118         Vec2    q = {Vec2_id};
119         Vec2    r = {Vec2_id};
120         double  t;
121 
122         DD_GET_POS2(dptr, q);
123         t = conic_param(conic, q);
124         r = conic_point(conic, t);
125         p2_sum += vec2_sqrmod(vec2_diff(r, q));
126         if (dptr == end)
127             break;
128     }
129     return ((n == 0) ? 0.0 : sqrt(p2_sum / n));
130 }
131 
132 /* ordered line segments along string */
133 static int line2_pair_possible_conic(Line2 * l1, Line2 * l2)
134 {
135     Tstring *s1, *s2;
136     Conic  *conic;
137     double  lresid, cresid;
138     double  dp, len_ratio;
139 
140     if (l1 == NULL || l2 == NULL)
141         return (0);
142 
143     /* first accept/reject gross examples */
144 
145     len_ratio = l1->length / l2->length;
146     if (len_ratio < 1)
147         len_ratio = 1 / len_ratio;
148 
149     if (len_ratio > 10.0)
150         return (0);
151 
152     dp = fabs(vec2_dot(l1->v, l2->v));
153 
154     if (l1->length > short_length && l2->length > short_length &&
155         dp < dot_thres_low)
156         return (0);
157 
158     /* check residuals */
159 
160     s1 = (Tstring *) prop_get(l1->props, STRING);
161     s2 = (Tstring *) prop_get(l2->props, STRING);
162 
163     if (s1 == NULL || s2 == NULL)
164         return (0);
165 
166     conic = ddstr_conic_5pt(s1->start, s2->end);
167     lresid = line_pair_residual(l1, l2, s1, s2);
168     cresid = conic_residual(conic, s1->start, s2->end);
169     conic_free(conic);
170 
171     if (cresid < conic_thres || cresid < lresid * resid_ratio)
172         return (1);
173 
174     /* finally check more subtle accept/reject */
175 
176     if (dp < dot_thres_low)
177         return (0);
178 
179     if (len_ratio > len_ratio_thres)
180         return (0);
181 
182     if (dp > dot_thres_hi)
183         return (1);
184 
185     return (0);
186 }
187 
188 static List *start_of_curve(List * lptr, List * end)
189 {
190     Line2  *line = NULL;
191     Line2  *last = NULL;
192     int     last_was_short = 0;
193     List *pos_start = NULL;
194 
195     for (;; lptr = lptr->next)
196     {
197         line = (Line2 *) lptr->to;
198 
199         if (line->length < ignore_length)
200         {
201             if (last_was_short) /* possible start of curve */
202             {
203                 if (last != NULL && !line2_pair_possible_conic(last, line))
204                     pos_start = lptr->last;
205                 break;
206             }
207             if (pos_start == NULL)
208                 pos_start = lptr;
209             if (lptr == end)
210             {
211                 if (last != NULL)
212                     pos_start = NULL;
213                 break;
214             }
215             last_was_short = 1;
216             continue;
217         }
218         if (line->length > long_length) /* not part of conic */
219         {
220             last = NULL;
221             pos_start = NULL;
222         } else if (last != NULL)
223         {
224             if (line2_pair_possible_conic(last, line))
225                 break;
226             lptr = pos_start;   /* go back */
227             pos_start = NULL;
228             last = NULL;
229         } else
230         {
231             last = line;
232             if (pos_start == NULL)
233                 pos_start = lptr;
234         }
235 
236         if (lptr == end)
237         {
238             if (pos_start != NULL && last_was_short && last == NULL)
239             {
240                 last = (Line2 *) pos_start->to;
241                 if (!line2_pair_possible_conic(last, line))
242                     pos_start = NULL;
243             }
244             break;
245         }
246         last_was_short = 0;
247     }
248     return ((pos_start == NULL) ? lptr : pos_start);
249 }
250 
251 List *end_of_curve(List * lptr, List * end)
252 {
253     Line2  *line = NULL;
254     Line2  *last = NULL;
255     int     last_was_short = 0;
256     List *pos_end = lptr;
257 
258     for (;; lptr = lptr->next)
259     {
260         line = (Line2 *) lptr->to;
261 
262         if (line->length < ignore_length)
263         {
264             if (last_was_short)
265                 last = NULL;
266             pos_end = lptr;
267             last_was_short = 1;
268             if (lptr == end)
269                 break;
270             continue;
271         }
272         if (line->length > long_length) /* not part of conic */
273             break;
274         else if (last == NULL)
275             last = line;
276         else if (line2_pair_possible_conic(last, line))
277         {
278             pos_end = lptr;
279             last = line;
280         } else
281             break;
282 
283         last_was_short = 0;
284 
285         if (lptr == end)
286             break;
287     }
288     return (pos_end);
289 }
290 
291 /* take a poly strings and replace candidate sections with conics */
292 void poly_string_find_conics(Tstring * string,
293     int sample, double low_th, double up_th, int max_div)
294 {
295     List *lptr;
296     List *start;
297     List *end;
298     List *conics;
299     Tstring *s1, *s2;
300 
301     if (string == NULL)
302         return;
303 
304     start = string->start;
305     end = string->end;
306 
307     for (lptr = start;;)
308     {
309         List *lptr1 = NULL;
310         List *lptr2 = NULL;
311         Line2  *line = NULL;
312         Line2  *last = NULL;
313 
314         lptr = lptr1 = start_of_curve(lptr, end);
315         if (lptr == end)
316             break;
317         lptr = lptr2 = end_of_curve(lptr, end);
318 
319         if (lptr != end)
320             lptr = lptr->next;
321 
322         last = (Line2 *) lptr1->to;
323         line = (Line2 *) lptr2->to;
324         s1 = (Tstring *) prop_get(last->props, STRING);
325         s2 = (Tstring *) prop_get(line->props, STRING);
326         conics = conic_prox(s1->start, s2->end, sample, low_th, up_th, max_div);
327 
328         if (conics != NULL)
329         {
330             if (lptr1 == start)
331             {
332                 start = conics;
333                 start->last = lptr1->last;      /* this may be a
334                                                  * substring */
335                 lptr1->last = NULL;
336                 if (start->last != NULL)
337                     start->last->next = start;
338             } else
339             {
340                 lptr1->last->next = conics;
341                 conics->last = lptr1->last;
342                 lptr1->last = NULL;
343             }
344 
345             conics = dd_get_end(conics);
346 
347             if (lptr2 == end)
348             {
349                 end = conics;
350                 end->next = lptr2->next;        /* this may be a
351                                                  * substring */
352                 if (end->next != NULL)
353                     end->next->last = end;
354                 lptr2->next = NULL;
355                 ddstr_rm(lptr1, lptr2, geom_free);
356                 break;
357             } else
358             {
359                 lptr2->next->last = conics;
360                 conics->next = lptr2->next;
361                 lptr2->next = NULL;
362             }
363             ddstr_rm(lptr1, lptr2, geom_free);
364         }
365         if (lptr == end)
366             break;
367     }
368 
369     string->start = start;
370     string->end = end;
371     poly_con_grow_conics(string, sample, low_th, up_th, max_div);
372 }
373 
374 /* ARGSUSED quieten lint */
375 void poly_con_grow_conics(Tstring * string,
376     int sample, double low_th, double up_th, int max_div)
377 {
378     List *start;
379     List *end;
380     List *cptr;
381 
382     if (string == NULL)
383         return;
384 
385     low_th *= low_th;           /* conic check uses sq thresholds */
386     up_th *= up_th;
387 
388     start = string->start;
389     end = string->end;
390 
391     for (cptr = start;;)
392     {
393         Conic  *conic;
394         Conic  *tot_conic = NULL;
395         List *lptr1 = cptr;
396         List *lptr2 = cptr;
397         List *conics;
398         Tstring *s1, *s2;
399 
400         if (cptr->type != CONIC2)
401         {
402             if (cptr == end)
403                 break;
404             cptr = cptr->next;
405             continue;
406         }
407         s1 = s2 = (Tstring *) geom_prop_get(cptr->to, cptr->type, STRING);
408 
409         if (cptr != start)      /* grow back */
410         {
411             for (lptr1 = cptr->last;; lptr1 = lptr1->last)
412             {
413                 double  dummy = 0.0;
414 
415                 s1 = (Tstring *) geom_prop_get(lptr1->to, lptr1->type, STRING);
416 
417                 /* BUG ddstr_conic_ellipse_5pt requires 3rd arg: double
418                  * min_aratio */
419                 conic = ddstr_conic_ellipse_5pt(s1->start, s2->end, dummy);
420 
421                 if (conic == NULL ||
422                     conic_check(conic, s1->start, s2->end,
423                                 low_th, up_th, max_div) == false)
424                 {
425                     conic_free(conic);
426                     lptr1 = lptr1->next;
427                     break;
428                 }
429                 conic_free(tot_conic);
430                 tot_conic = conic;
431                 if (lptr1 == start)
432                     break;
433             }
434         }
435         if (cptr != end)        /* grow back */
436         {
437             for (lptr2 = cptr->next;; lptr2 = lptr2->next)
438             {
439                 double  dummy = 0.0;
440 
441                 s2 = (Tstring *) geom_prop_get(lptr2->to, lptr2->type, STRING);
442 
443                 /* BUG ddstr_conic_ellipse_5pt requires 3rd arg: double
444                  * min_aratio */
445                 conic = ddstr_conic_ellipse_5pt(s1->start, s2->end, dummy);
446                 if (conic == NULL ||
447                     conic_check(conic, s1->start, s2->end,
448                                 low_th, up_th, max_div) == false)
449                 {
450                     conic_free(conic);
451                     lptr2 = lptr2->last;
452                     break;
453                 }
454                 conic_free(tot_conic);
455                 tot_conic = conic;
456                 if (lptr2 == end)
457                     break;
458             }
459         }
460         cptr = (lptr2 == end) ? end : lptr2->next;
461         if (lptr1 == lptr2)
462         {
463             if (cptr == end)
464                 break;
465             continue;
466         }
467         s1 = (Tstring *) geom_prop_get(lptr1->to, lptr1->type, STRING);
468         s2 = (Tstring *) geom_prop_get(lptr2->to, lptr2->type, STRING);
469         conic_ellipse_filter(tot_conic, s1->start, s2->end, 0.2);
470 
471         tot_conic->props =
472             proplist_add(tot_conic->props,
473                 (void *) str_make(STRING, s1->start, s2->end), STRING,
474                 str_rm_only_str);
475         conics = dd_link_alloc((void *) tot_conic, CONIC2);
476         if (lptr1 == start)
477         {
478             start = conics;
479             start->last = lptr1->last;  /* this may be a substring */
480             if (start->last != NULL)
481                 start->last->next = start;
482         } else
483         {
484             lptr1->last->next = conics;
485             conics->last = lptr1->last;
486         }
487 
488         if (lptr2 == end)
489         {
490             end = conics;
491             end->next = lptr2->next;    /* this may be a substring */
492             if (end->next != NULL)
493                 end->next->last = end;
494             lptr1->last = lptr2->next = NULL;
495             ddstr_rm(lptr1, lptr2, geom_free);
496             break;
497         } else
498         {
499             lptr2->next->last = conics;
500             conics->next = lptr2->next;
501         }
502         lptr1->last = lptr2->next = NULL;
503         ddstr_rm(lptr1, lptr2, geom_free);
504 
505         if (cptr == end)
506             break;
507     }
508     string->start = start;
509     string->end = end;
510 }
511 
512 void    poly_strings_find_conics(List * strings,
513     int sample, double low_th, double up_th, int max_div)
514 {
515     List   *sptr;
516 
517     for (sptr = strings; sptr != NULL; sptr = sptr->next)
518         poly_string_find_conics((Tstring *) sptr->to,
519             sample, low_th, up_th, max_div);
520 }
521 

~ [ 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.