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

Linux Cross Reference
Tina4/src/vision/curve2/curvprox.c

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

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

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