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