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

Linux Cross Reference
Tina4/src/vision/curve2/conicprox.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 int init_sample = 12;
 12 static double min_aratio = 0.2;
 13 
 14 void    conic_prox_init_sample_set(int sample)
 15 {
 16     init_sample = sample;
 17 }
 18 
 19 /* approximate square of distance of point p to conic */
 20 static double conic_sqrdist_check(Conic * conic, Vec2 p)
 21 {
 22     double  t;
 23     Vec2    pc = {Vec2_id};
 24 
 25     t = conic_param(conic, p);
 26     pc = conic_point(conic, t);
 27     return (vec2_sqrdist(p, pc));
 28 }
 29 
 30 /* grow the conic along the implicit string between start and end
 31  * 
 32  * initial points are given through p1 and p2 (these are updated)
 33  * 
 34  * a form of hystersis thresholding is employed
 35  * 
 36  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
 37  * until hi_th (high thres) is exceeded the point of segmentation is
 38  * set to the last point lo_th was exceeded */
 39 Bool    conic_grow_string(Conic * conic, List * start, List * end, List ** p1, List ** p2, double lo_th, double hi_th, int max_div)
 40 {
 41     Vec2    p = {Vec2_id};
 42     List *ptr;
 43     double  sqr_dist;
 44     List *m1 = *p1;
 45     List *m2 = *p2;
 46     Bool    grown = false;
 47 
 48     /** grow backwards **/
 49     for (ptr = m1; ptr != start;)
 50     {
 51         int     misses = 0;
 52 
 53         ptr = ptr->last;
 54         DD_GET_POS2(ptr, p);
 55         sqr_dist = conic_sqrdist_check(conic, p);
 56         if (sqr_dist > hi_th)
 57             break;
 58         if (sqr_dist < lo_th)
 59         {
 60             grown = true;
 61             misses = 0;
 62             m1 = ptr;
 63         } else
 64             ++misses;
 65         if (misses > max_div)
 66             break;
 67     }
 68 
 69     /** grow forwards **/
 70     for (ptr = m2; ptr != end;)
 71     {
 72         int     misses = 0;
 73 
 74         ptr = ptr->next;
 75         DD_GET_POS2(ptr, p);
 76         sqr_dist = conic_sqrdist_check(conic, p);
 77         if (sqr_dist > hi_th)
 78             break;
 79         if (sqr_dist < lo_th)
 80         {
 81             grown = true;
 82             misses = 0;
 83             m2 = ptr;
 84         } else
 85             ++misses;
 86         if (misses > max_div)
 87             break;
 88     }
 89 
 90     *p1 = m1;
 91     *p2 = m2;
 92 
 93     if (grown || prop_get(conic->props, STRING) == NULL)
 94         /** replace string on proplist and reset ends **/
 95     {
 96         Vec2    e1 = {Vec2_id};
 97         Vec2    e2 = {Vec2_id};
 98         Vec2    emid = {Vec2_id};
 99 
100         conic->props = proplist_rm(conic->props, STRING);
101         conic->props = proplist_add(conic->props,
102           (void *) str_make(STRING, m1, m2), STRING, str_rm_only_str);
103         DD_GET_POS2(m1, e1);
104         DD_GET_POS2(m2, e2);
105         DD_GET_POS2(ddstr_mid_point(m1, m2), emid);
106         conic_set_ends(conic, e1, e2, emid);
107     }
108     return (grown);
109 }
110 
111 /* grow the conic along the implicit string between start and end
112  * 
113  * initial points are given through p1 and p2 (these are updated)
114  * 
115  * actual growing is done by conic_grow_string
116  * 
117  * the function iterates throgh new conic fits to the string */
118 Conic  *conic_grow(Conic * conic, List * start, List * end, List ** p1, List ** p2, double lo_th, double hi_th, int max_div)
119 {
120     Bool    updated;
121     List *m1 = *p1;
122     List *m2 = *p2;
123 
124     do
125     {
126         Bool    string_grown;
127 
128         /** grow start and end along conic **/
129         string_grown = conic_grow_string(conic, start, end, &m1, &m2,
130                                          lo_th, hi_th, max_div);
131 
132         if (string_grown)       /** fit a new conic and see if still good **/
133         {
134             Conic  *new_conic = ddstr_conic_ellipse_5pt(m1, m2, min_aratio);
135 
136             conic_ellipse_filter(new_conic, m1, m2, min_aratio);
137 
138             if (new_conic != NULL &&
139                 conic_check(new_conic, m1, m2, lo_th, hi_th, max_div))
140             {
141                 updated = true;
142                 conic_free(conic);
143                 conic = new_conic;
144             } else
145             {
146                 updated = false;
147                 if (new_conic != NULL)
148                     conic_free(new_conic);
149             }
150         } else
151             updated = false;
152     } while (updated);
153 
154     *p1 = m1;
155     *p2 = m2;
156 
157     return (conic);
158 }
159 
160 /* check that the conic fits the implicit string start and end
161  * 
162  * a form of hystersis thresholding is employed
163  * 
164  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
165  * until hi_th (high thres) is exceeded */
166 Bool    conic_check(Conic * conic, List * start, List * end, double lo_th, double hi_th, int max_div)
167 {
168     Vec2    pos = {Vec2_id};
169     List *dptr;
170     double  sqr_dist;
171     int     misses = 0;
172 
173     for (dptr = start;; dptr = dptr->next)
174     {
175         DD_GET_POS2(dptr, pos);
176         sqr_dist = conic_sqrdist_check(conic, pos);
177         if (sqr_dist > hi_th)
178             return (false);
179         if (sqr_dist > lo_th)
180             ++misses;
181         else
182             misses = 0;
183         if (misses > max_div)
184             return (false);
185         if (dptr == end)
186             break;
187     }
188     return (true);
189 }
190 
191 /* check that the conic fits the list of strings
192  * 
193  * a form of hystersis thresholding is employed
194  * 
195  * lo_th (low thres) can be exeeded for upto max_div (max divergence) or
196  * until hi_th (high thres) is exceeded
197  * 
198  * furthermore each string can deviate from the conic close to its
199  * endpoints */
200 Bool    conic_check_list(Conic * conic, List * strings, double lo_th, double hi_th, int max_div)
201 {
202     Vec2    pos = {Vec2_id};
203     List *dptr;
204     double  sqr_dist;
205     int     misses = 0;
206     List   *ptr;
207 
208     for (ptr = strings; ptr != NULL; ptr = ptr->next)
209     {
210         Tstring *str = (Tstring *) ptr->to;
211         int     start_div, end_div, i;
212 
213         start_div = str->count / 5;
214         end_div = str->count - start_div;
215 
216         for (i = 0, dptr = str->start; i < start_div; ++i)
217             dptr = dptr->next;
218 
219         for (; i < end_div; i++, dptr = dptr->next)
220         {
221             DD_GET_POS2(dptr, pos);
222             sqr_dist = conic_sqrdist_check(conic, pos);
223 
224             if (sqr_dist > hi_th)
225                 return (false);
226 
227             if (sqr_dist > lo_th)
228                 ++misses;
229             else
230                 misses = 0;
231 
232             if (misses > max_div)
233                 return (false);
234         }
235     }
236 
237     return (true);
238 }
239 
240 /* count the number of points (at the sample frequency) that are close
241  * to the conic */
242 int     conic_count(Conic * conic, List * start, List * end, int sample, double thres_sqr)
243 {
244     Vec2    p = {Vec2_id};
245     int     count = 0;
246     List *dptr;
247     int     i;
248 
249     for (dptr = start;;)
250     {
251         DD_GET_POS2(dptr, p);
252         if (conic_sqrdist_check(conic, p) < thres_sqr)
253             ++count;
254 
255         if (dptr == end)
256             break;
257 
258         for (i = 0; i < sample; ++i, dptr = dptr->next)
259             if (dptr == end)
260                 break;
261     }
262     return (count);
263 }
264 
265 #if 0
266 static Bool is_straight(List * dd1, List * dd2, List * dd3, double thres)
267 {
268     Vec2    p1 = {Vec2_id};
269     Vec2    p2 = {Vec2_id};
270     Vec2    p3 = {Vec2_id};
271     Vec2    v = {Vec2_id};
272 
273     DD_GET_POS2(dd1, p1);
274     DD_GET_POS2(dd2, p2);
275     DD_GET_POS2(dd3, p3);
276     v = vec2_unit(vec2_diff(p3, p1));
277     return (fit2_point_on_line(p2, v, p1, thres));
278 }
279 
280 #endif
281 
282 List *conic_prox(List * start, List * end, int sample, double lo_th, double hi_th, int max_div)
283 {
284     List *p1;
285     List *p2;
286     List *m1;
287     List *m2;
288     List *list1 = NULL;
289     List *list2 = NULL;
290     Conic  *conic = NULL;
291     double  lo_sqth = lo_th * lo_th;
292     double  hi_sqth = hi_th * hi_th;
293     int     i, maxcount = 0;
294 
295     if (start == NULL || end == NULL || start == end)
296         return (NULL);
297 
298     p1 = start;
299     p2 = ddstr_nth_point(start, end, 4 * sample + 1);
300     if (p2 == NULL)
301         p2 = end;
302 
303     while (1)
304     {
305 
306         /* if (is_straight(p1, ddstr_mid_point(p1, p2), p2, lo_th)) {
307          * if (p2 == end) break; for (i = 0; i < sample; ++i) { p1 =
308          * p1->next; p2 = p2->next; if (p2 == end) break; } continue; } */
309         conic = ddstr_conic_ellipse_5pt(p1, p2, min_aratio);
310         if (conic != NULL &&
311             conic_check(conic, p1, p2, lo_sqth, hi_sqth, max_div))
312         {
313             int     count = conic_count(conic, start, end, sample / 2, lo_sqth);
314 
315             if (count > maxcount)
316             {
317                 maxcount = count;
318                 m1 = p1;
319                 m2 = p2;
320             }
321         }
322         conic_free(conic);
323         conic = NULL;
324 
325         if (p2 == end)
326             break;
327 
328         for (i = 0; i < sample; ++i)
329         {
330             p1 = p1->next;
331             p2 = p2->next;
332             if (p2 == end)
333                 break;
334         }
335     }
336 
337     if (maxcount >= 5)
338     {
339         conic = ddstr_conic_ellipse_5pt(m1, m2, min_aratio);
340         conic = conic_grow(conic, start, end, &m1, &m2,
341                            lo_sqth, hi_sqth, max_div);
342 
343         if (conic != NULL && conic->type != ELLIPSE)
344         {
345             if (fabs(conic->t1) > 2 || fabs(conic->t2) > 2)
346             {
347                 conic_free(conic);
348                 conic = NULL;
349             }
350         }
351     }
352     if (conic == NULL)          /* failed */
353     {
354         sample = (int)(sample*0.75);            /* increase sample frequency */
355         if (sample >= 3)
356             return (conic_prox(start, end, sample, lo_th, hi_th, max_div));
357         return (linear_prox(start, end, (float)lo_th, init_sample));
358     }
359     if (m1 != start)
360         list1 = conic_prox(start, m1, sample,
361                            lo_th, hi_th, max_div);
362     if (m2 != end)
363         list2 = conic_prox(m2, end, sample,
364                            lo_th, hi_th, max_div);
365 
366     return (dd_append(list1, dd_append(dd_link_alloc((void *) conic, CONIC2), list2)));
367 }
368 
369 Tstring *conic_string(Tstring * string, int init_smpl, double lo_th, double hi_th, int max_div)
370 {
371     List *conic;
372 
373     if (string == NULL)
374         return (NULL);
375 
376     init_sample = init_smpl;
377 
378     conic = conic_prox(string->start, string->end, init_sample,
379                        lo_th, hi_th, max_div);
380 
381     if (conic == NULL)
382         return (NULL);
383 
384     return (str_make(STRING, conic, dd_get_end(conic)));
385 }
386 
387 List   *conic_strings(List * strings, int init_smpl, double lo_th, double hi_th, int max_div)
388 {
389     List   *sptr;
390     List   *splist = NULL;
391 
392     for (sptr = strings; sptr != NULL; sptr = sptr->next)
393     {
394         Tstring *string = (Tstring *) sptr->to;
395 
396         string = conic_string(string, init_smpl, lo_th, hi_th, max_div);
397         splist = ref_addtostart(splist, (void *) string, STRING);
398     }
399     return (splist);
400 }
401 

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