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

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

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