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

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

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