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

Linux Cross Reference
Tina4/src/vision/stereo/mat_fast.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 

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