1 /**@(#)
2 **/
3 /* mat_fast.c
4 *
5 * Specialised functions for stereo matching based upon strict string
6 * match identity and dynamic programming.
7 *
8 * Faster and less memory overhead than generic version.
9 *
10 * Weeker figural continuity criteria could be used.
11 *
12 * Works by matching edge strings as a whole rather than at the stereo
13 * index epipolar edge strings level.
14 *
15 * Individual matches are considered between regular edge strings
16 * associated with a global string. These only cross each epipolar once
17 * are distinguished using the unique label added during the
18 * construction of the stereo index (it is stored on the property list
19 * of the stereo index sub-strings using the key STRING). */
20
21 #include <math.h>
22 #include <string.h>
23 #ifdef TRANSPUTER
24 #include <valuesdual.h>
25 #else
26 #include <values.h>
27 #endif
28 #include <tina/sys.h>
29 #include <tina/sysfuncs.h>
30 #include <tina/math.h>
31 #include <tina/mathfuncs.h>
32 #include <tina/vision.h>
33 #include <tina/visionfuncs.h>
34
35 /* Add match information at the match string level for the epipolar
36 * edge sub-string from one image with respect to the list of epipolar
37 * edge strings from the other.
38 *
39 * This includes the accumulation of strict figural contour support.
40 *
41 * First identify the edge contour string and substring identifier of
42 * which this epipolar sub-string forms a part. */
43 static void match_strings(Tstring * es, List * slist, int r, double lx, double ux, Bool(*match_func) ( /* ??? */ ))
44 /* string contiguous edges along a raster */
45 /* list of raster edge strings */
46 /* row/raster value */
47 /* matching window */
48
49 /* edge string match test (NULL for all matches) */
50 {
51 List *lptr;
52 Tstring *s1, *s2;
53 Edgel *edge;
54 List *mlist;
55 int s1_id, s2_id;
56 int mlist_updated = 0;
57
58 edge = (Edgel *) es->start->to;
59 s1 = (Tstring *) prop_get(edge->props, STRING);
60 mlist = (List *) prop_get(s1->props, MLIST);
61 s1_id = (int) prop_get(es->props, STRING);
62
63 for (lptr = slist; lptr != NULL; lptr = lptr->next)
64 {
65 s2 = (Tstring *) lptr->to;
66 if ((s2->type == FORWARD && vec2_x(DD_EDGE_POS(s2->end)) > lx) ||
67 (s2->type == BACKWARD && vec2_x(DD_EDGE_POS(s2->start)) > lx))
68 break;
69 }
70
71 for (; lptr != NULL; lptr = lptr->next)
72 {
73 s2 = (Tstring *) lptr->to;
74 if ((s2->type == FORWARD && vec2_x(DD_EDGE_POS(s2->end)) > ux) ||
75 (s2->type == BACKWARD && vec2_x(DD_EDGE_POS(s2->start)) > ux))
76 break;
77 if (match_func == NULL || match_func(es, s2)) /* they can match */
78 {
79 String_match *sm;
80
81 s2_id = (int) prop_get(s2->props, STRING);
82 if ((sm = str_mat_from_list(mlist, s1_id, s2_id)) == NULL)
83 {
84 edge = (Edgel *) s2->start->to;
85 sm = sm_make(s1, (Tstring *) prop_get(edge->props, STRING), s1_id, s2_id);
86 sm->r_low = sm->r_up = r;
87 mlist = ref_addtostart(mlist, (void *) sm, s1_id);
88 mlist_updated = 1;
89 }
90 sm->support += ss_match_weight(es, s2);
91 if (r < sm->r_low)
92 sm->r_low = r;
93 if (r > sm->r_up)
94 sm->r_up = r;
95 }
96 }
97 if (mlist_updated)
98 s1->props = proplist_addifnp(s1->props, (void *) mlist, MLIST, sm_list_rm, false);
99 }
100
101 /* consider epipolar edge sub-strings from the stereo index at the
102 * raster level
103 *
104 * use the match_strings function to accumulate match string data between
105 * implicit edge strings */
106 static void match_strings_epi(List * left, List * right, int r, Bool(*match_func) ( /* ??? */ ))
107 /* list of edge strings on left epipolar */
108 /* list of edge strings on right epipolar */
109 /* row/raster number */
110
111 /* edge string match test (NULL for all matches) */
112 {
113 double lowd, upd; /* range of allowed disparity */
114 List *ptr;
115
116 for (ptr = left; ptr != NULL; ptr = ptr->next)
117 {
118 double lx, ux;
119 Tstring *es = (Tstring *) ptr->to;
120
121 (void) disp_range_at_pos2(str2_centroid(es), &lowd, &upd);
122
123 if (es->type == FORWARD)
124 {
125 lx = vec2_x(DD_EDGE_POS(es->start)) + lowd;
126 ux = vec2_x(DD_EDGE_POS(es->end)) + upd;
127 } else
128 { /* BACKWARD */
129 lx = vec2_x(DD_EDGE_POS(es->end)) + lowd;
130 ux = vec2_x(DD_EDGE_POS(es->start)) + upd;
131 }
132 match_strings(es, right, r, lx, ux, match_func);
133 }
134 }
135
136 /*********************************************************************
137 * *
138 * END OF MATCH STRING SUPPORT FUNCTIONS *
139 * *
140 * START OF DYNAMIC PROGRAMMING FUNCTIONS *
141 * *
142 **********************************************************************/
143
144 /* build dynamic programming index list for the current complete edge
145 * countour it containes separate index list elements for each labled
146 * sub-string that is unique in raster coverage
147 *
148 * actual index values are filled in later depending upon the raster that
149 * is being initialised for dynamic programming
150 *
151 * walk along edge string using epipolar sub-strings and notice changes in
152 * sub-string labels */
153 static void es_build_dpindex_prop(Tstring * es)
154 {
155 List *dptr;
156 List *end;
157 int old_str_id = 0, str_id;
158 List *index = NULL;
159
160 if (es == NULL)
161 return;
162
163 end = es->end;
164 for (dptr = es->start;; dptr = dptr->next)
165 {
166 Edgel *e = (Edgel *) dptr->to;
167 Tstring *sub;
168
169 sub = (Tstring *) prop_get(e->props, SINDEX);
170 if (sub == NULL)
171 {
172 if (dptr == end)
173 break;
174 continue;
175 }
176 str_id = (int) prop_get(sub->props, STRING);
177
178 if (str_id != old_str_id)
179 {
180 index = ref_addtostart((List *) index, (void *) 0, str_id);
181 old_str_id = str_id;
182 }
183 dptr = sub->end;
184 if (dptr == end)
185 break;
186 }
187 es->props = proplist_addifnp(es->props, (void *) index, DP_INDEX, list_rm_links, true);
188 }
189
190 /* set dynamic programming indices on the basis of the list of edges
191 * that constitute a current raster of the stereo index
192 *
193 * the dynamic programming index is associated whole edge contour as well
194 * as the epipolar sub-string as that is where match information is
195 * made explicit. */
196 static int es_list_set_dpindices(List * es)
197 {
198 List *lptr;
199 List *index;
200 Tstring *str;
201 int str_id, i;
202
203 for (lptr = es, i = 0; lptr != NULL; lptr = lptr->next, ++i)
204 {
205 str = (Tstring *) lptr->to;
206 str_id = (int) prop_get(str->props, STRING);
207 str->props = proplist_addifnp(str->props, (void *) i, DP_INDEX,
208 (void (*) ()) NULL, false);
209 str = (Tstring *) prop_get(((Edgel *) str->start->to)->props, STRING);
210 index = (List *) prop_get(str->props, DP_INDEX);
211 for (; index; index = index->next)
212 {
213 if (index->type == str_id)
214 {
215 index->to = (void *) i;
216 break;
217 }
218 }
219 }
220 return (i);
221 }
222
223 /* Static data structures to simplify dynamic programming code and
224 * minimise data structure allocation and freeing. */
225
226 static int dp_size; /* size of square DP array */
227 static Dpnode **dp_array; /* the DP array */
228 static int *low, *up; /* lower and upper indices into DP
229 * array */
230
231 /* Build dynamic programming array of size s by s if s is less than or
232 * equal to the size of the existing array then just return
233 *
234 * free up the existing array allocate space for low and up index arrays
235 * they delimit the active parts of the DP array that is those elements
236 * containing valid data */
237 static void dp_build(int s)
238 {
239 unsigned int label;
240
241 if (s <= dp_size)
242 return;
243
244 label = ralloc_end_blocked(); /* allow for blocked allocation */
245
246 narray_free((char **) dp_array, 0, dp_size, 0, dp_size, sizeof(Dpnode));
247 rfree((void *) low);
248 rfree((void *) up);
249 dp_size = s;
250 dp_array = ts_narray_alloc(0, 0, dp_size, dp_size, Dpnode);
251 low = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
252 up = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
253 if (label) /* allocation was blocked */
254 (void) ralloc_start_blocked(label); /* re-start blocking */
255 }
256
257 /* apply dynamic programming to the rasters implicit in the lists left
258 * and right and return a list of DP matches
259 *
260 * the form of the match list returned by the dynamic programming routines
261 * is determined by the data field of the Dpnode for efficiency (memory
262 * allocation is avoided) it is an integer value that uniquely
263 * identifies the DP indices of the left and right edge
264 * strings/sub-strings: l_index*r_no + r_index + 1 where r_no is the
265 * number of edge strings crossing the right raster. The final 1 is
266 * added as if the data field has value is 0 it is not returned (the
267 * null match).
268 *
269 * The DP array is first filled with entries implied by relavent edge
270 * string matches and appropriate low and up indices adusted.
271 *
272 * The low and up array idives are then validated to allow the
273 * computationally optimal form of dynamic programming to be performed. */
274 static List *dp_string_matches(List * left, List * right, int r, int l_no, int r_no)
275
276 /* raster/row number */
277 /* max number of left and right indices */
278 {
279 List *ptr;
280 List *mlist;
281 Tstring *str;
282 int firsti, lasti, minj = MAXINT;
283 int s1_id, s2_id;
284 int i, j;
285
286 if (left == NULL || right == NULL)
287 return (NULL);
288
289 if (l_no > dp_size || r_no > dp_size)
290 {
291 error("dp_mlist: dynamic programming table limit exeeded", warning);
292 return (NULL);
293 }
294 /* initialise dp array */
295 for (i = 0; i < l_no; ++i)
296 {
297 low[i] = up[i] = -1;
298 (void) memset((char *) dp_array[i], 0, r_no * sizeof(Dpnode));
299 }
300
301 for (ptr = left; ptr != NULL; ptr = ptr->next)
302 {
303 str = (Tstring *) ptr->to;
304 i = (int) prop_get(str->props, DP_INDEX);
305 s1_id = (int) prop_get(str->props, STRING);
306 str = (Tstring *) prop_get(((Edgel *) str->start->to)->props, STRING);
307 mlist = (List *) prop_get(str->props, MLIST);
308 for (; mlist != NULL; mlist = mlist->next)
309 {
310 List *index_list;
311 String_match *sm;
312
313 if (s1_id != mlist->type)
314 continue;
315
316 sm = (String_match *) mlist->to;
317 if (r > sm->r_up || r < sm->r_low)
318 continue;
319
320 s2_id = sm->s2_id;
321 str = (Tstring *) ((String_match *) mlist->to)->s2;
322 index_list = (List *) prop_get(str->props, DP_INDEX);
323 for (; index_list != NULL; index_list = index_list->next)
324 if (s2_id == index_list->type)
325 break;
326 if (index_list == NULL)
327 continue;
328 j = (int) index_list->to;
329 if (low[i] == -1 || j < low[i])
330 low[i] = j;
331 if (up[i] == -1 || j > up[i])
332 up[i] = j;
333 if (j < minj)
334 minj = j;
335 dp_array[i][j].data = (void *) (i * r_no + j + 1);
336 dp_array[i][j].cost = (float) ((String_match *) mlist->to)->support;
337 }
338 }
339
340 /* find range of left index values with possible matches */
341 for (i = 0; i < l_no; ++i)
342 if (low[i] != -1)
343 break;
344 firsti = i;
345 for (i = l_no - 1; i >= 0; --i)
346 if (low[i] != -1)
347 break;
348 lasti = i;
349
350 if (firsti > lasti)
351 return (NULL);
352
353 form_valid_dp_array(low, up, firsti, lasti, minj);
354 dp_accum(dp_array, low, up, firsti, lasti);
355 return (dp_solution(dp_array, low, up, firsti, lasti));
356 }
357
358 /* run dynamic programming on the left and right raster r and interpret
359 * the result
360 *
361 * the function dp_string_matches actually performs the dynamic
362 * programming
363 *
364 * matches are formed between matching left and right epipolar edge
365 * strings and added to the property list of the left member using the
366 * key MLIST */
367 static void choose_matches_epi(List * left, List * right, int r)
368 /* list of edge strings on left epipolar */
369 /* list of edge strings on right epipolar */
370 /* raster number */
371 {
372 int l_no, r_no;
373 List *mlist;
374 List *ptr;
375
376 l_no = es_list_set_dpindices(left);
377 r_no = es_list_set_dpindices(right);
378 mlist = dp_string_matches(left, right, r, l_no, r_no);
379
380 for (ptr = mlist; ptr != NULL; ptr = ptr->next)
381 {
382 int i, j;
383 Tstring *l_es, *r_es;
384 Match *match;
385
386 i = ((int) ptr->to) - 1;
387 j = (i % r_no);
388 i = (i / r_no);
389 l_es = (Tstring *) (list_nth(left, i))->to;
390 r_es = (Tstring *) (list_nth(right, j))->to;
391 match = match_make((void *) l_es, (void *) r_es, STRING);
392 l_es->props = proplist_addifnp(l_es->props, (void *) link_alloc((void *) match, MATCH),
393 MLIST, mlist_free, true);
394 }
395
396 list_rm_links(mlist);
397 }
398
399 /*********************************************************************
400 * *
401 * END OF DYNAMIC PROGRAMMING FUNCTIONS *
402 * *
403 **********************************************************************/
404
405 /* external function call for rapid stereo matching uses all above
406 * static funtions and variables
407 *
408 * uses left and right edgrect and a matching funtion updates the MLIST
409 * property associated with the stereo index sub-strings of the left
410 * image */
411 void er_string_matcher(Imrect * er_left, Imrect * er_right, Bool(*match_func) ( /* ??? */ ))
412 /* imrects containing left and right edges */
413
414 /* edge string match test (NULL for all matches) */
415 {
416 Rindex *sx_left;
417 Rindex *sx_right;
418 List *left;
419 List *right;
420 int ll, lu, rl, ru;
421 int i;
422
423 if (er_left == NULL || er_right == NULL)
424 return;
425
426 er_apply_to_all_strings(er_left, es_init_mlist, NULL);
427 er_apply_to_all_strings(er_left, es_build_dpindex_prop, NULL);
428 er_apply_to_all_strings(er_right, es_build_dpindex_prop, NULL);
429
430 sx_left = (Rindex *) prop_get(er_left->props, SINDEX); /* Stereo INDEX */
431 sx_right = (Rindex *) prop_get(er_right->props, SINDEX);
432
433 if (sx_left == NULL || sx_right == NULL)
434 return;
435
436 ll = sx_left->region->ly;
437 rl = sx_right->region->ly;
438 lu = sx_left->region->uy;
439 ru = sx_right->region->uy;
440
441 /* match whole sub strings and compute support */
442
443 for (i = ll; i < lu; ++i)
444 {
445 if (i < rl || i >= ru)
446 continue;
447 left = (List *) sx_left->index[i];
448 right = (List *) sx_right->index[i];
449 match_strings_epi(left, right, i, match_func);
450 }
451
452 /* select correct matches using dynamic programming to force order */
453
454 dp_build(stereo_dp_max_size_get());
455
456 for (i = ll; i < lu; ++i)
457 {
458 if (i < rl || i >= ru)
459 continue;
460 left = (List *) sx_left->index[i];
461 right = (List *) sx_right->index[i];
462 choose_matches_epi(left, right, i);
463 }
464 }
465
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.