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

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

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