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

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

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