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
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.