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

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

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

  1 /**@(#)
  2 **/
  3 /* dp_match.c
  4  * 
  5  * generic stereo routines for dynamic programming
  6  * 
  7  * includes support and choice functionality
  8  * 
  9  * uses dynamic programming at its most abstract through the match list
 10  * interface */
 11 
 12 #include <math.h>
 13 #include <tina/sys.h>
 14 #include <tina/sysfuncs.h>
 15 #include <tina/math.h>
 16 #include <tina/mathfuncs.h>
 17 #include <tina/vision.h>
 18 #include <tina/visionfuncs.h>
 19 
 20 /* static variable for max DP table size plus get and set functions
 21  * 
 22  * using a fixed DP array improves efficiency as the table is not
 23  * allocated at each iteration */
 24 
 25 static int max_dp_table_size = 100;
 26 
 27 void    stereo_dp_max_size_set(int size)
 28 {
 29     max_dp_table_size = size;
 30 }
 31 
 32 int     stereo_dp_max_size_get(void)
 33 {
 34     return (max_dp_table_size);
 35 }
 36 
 37 /* add DP index to elements in the epipolar edge sub-string list that
 38  * represent ordered matching features along a raster */
 39 static void es_list_add_dpindex_prop(List * es)
 40 {
 41     List   *lptr;
 42     Tstring *str;
 43     int     i;
 44 
 45     for (lptr = es, i = 0; lptr != NULL; lptr = lptr->next, ++i)
 46     {
 47         str = (Tstring *) lptr->to;
 48         str->props = proplist_addifnp(str->props, (void *) i, DP_INDEX,
 49                                       (void (*) ()) NULL, false);
 50     }
 51 }
 52 
 53 /* recover DP index from an epipolar sub-string */
 54 static int es_index_get(Tstring * es)
 55 {
 56     return ((int) prop_get(es->props, DP_INDEX));
 57 }
 58 
 59 /* get mean x position of edge string */
 60 static double es_mean_x(Tstring * es)
 61 {
 62     Vec2    v = {Vec2_id};
 63 
 64     v = str2_centroid(es);
 65 
 66     return (vec2_x(v));
 67 }
 68 
 69 /* take an ordered list and remove repeated references */
 70 static void thin_ordered_list(List * list)
 71 {
 72     List   *p1;
 73     List   *p2;
 74     List   *p3;
 75 
 76     for (p1 = list; p1 != NULL; p1 = p2)
 77     {
 78         for (p2 = p1->next; p2 != NULL; p2 = p2->next)
 79             if (p2->to != p1->to)
 80                 break;
 81 
 82         if (p1->next == p2)
 83             continue;
 84 
 85         if (p2 == NULL)
 86             break;
 87 
 88         p3 = p1->next;
 89         p1->next = p2;
 90         while (p3 != p2)
 91         {
 92             p1 = p3->next;
 93             rfree((void *) p3);
 94             p3 = p1;
 95         }
 96     }
 97 }
 98 
 99 /* perform dynamic programming to identify optimal ordered selection of
100  * matches referenced through the list of epipolar edge sub-strings
101  * from the left image
102  * 
103  * the matching strength upon which DP is based is returned by calling the
104  * match_weight_func on the match
105  * 
106  * because of the way in which the stereo index is constructed and because
107  * it is possible to allow vertical miss-match at the match formation
108  * stage the right and side of the matches can not be guaranteed to
109  * come from a single raster of the stereo index. they are though
110  * guaranteed to be unigue with respect to uniquely labled subsections
111  * of global edge contours.
112  * 
113  * the list of all matches associated with the raster left is processed to
114  * recover a list of right hand edges strings these are subsequently
115  * ordered and thined to produce a unique list of edge sub-strings that
116  * constitues a virtual raster of the right image. */
117 List   *match_epi_dprog(List * left, double (*match_weight_func) ( /* ??? */ ))
118 /* epipolar edge list */
119 
120 {
121     List   *mlist = NULL;
122     List   *right;
123     List   *dplist;
124 
125     list_apply_func(left, es_add_to_mlist, (void *) &mlist);
126     right = mlist_to2_list(mlist);
127     right = sort_list(right, es_mean_x, NULL);
128     thin_ordered_list(right);
129 
130     if (right == NULL)
131         return (NULL);
132 
133     es_list_add_dpindex_prop(left);
134     es_list_add_dpindex_prop(right);
135 
136     mlist_set_dp_indices(mlist, es_index_get, NULL);
137 
138     dplist = dp_mlist(mlist, match_weight_func);
139 
140     list_rm_links(right);
141     list_rm_links(mlist);
142 
143     return (dplist);
144 }
145 
146 /* use raster based DP to choose optimal match order for the matching
147  * strength implied by the match_weight_func */
148 void    choose_ordered_matches(Imrect * er, double (*match_weight_func) ( /* ??? */ ))
149 /* left edgerect */
150 
151 {
152     Rindex *sx;
153     int     ly, uy, i;
154 
155     if (er == NULL || (sx = (Rindex *) prop_get(er->props, SINDEX)) == NULL)
156         return;
157 
158     ly = sx->region->ly;
159     uy = sx->region->uy;
160 
161     dp_mlist_build(max_dp_table_size);
162 
163     for (i = ly; i < uy; ++i)
164     {
165         List   *mlist = NULL;
166         List   *best;
167 
168         list_apply_func((List *) sx->index[i], es_add_to_mlist, (void *) &mlist);
169         best = match_epi_dprog((List *) sx->index[i], match_weight_func);
170         mlist_set_supp_type(mlist, BAD_MATCH);
171         mlist_set_supp_type(best, GOOD_MATCH);
172         list_rm_links(mlist);
173         list_rm_links(best);
174     }
175 }
176 
177 /* set matching strength according to DP selection the
178  * matching_strength of the support structure is
179  * 
180  * set to the weight of the match (not the DP sum) for matches on the
181  * optimal path and zero otherwise */
182 void    support_ordered_matches(Imrect * er, double (*match_weight_func) ( /* ??? */ ))
183 /* left edgerect */
184 
185 {
186     Rindex *sx;
187     int     ly, uy, i;
188     double  zero = 0;
189 
190     if (er == NULL || (sx = (Rindex *) prop_get(er->props, SINDEX)) == NULL)
191         return;
192 
193     ly = sx->region->ly;
194     uy = sx->region->uy;
195 
196     dp_mlist_build(max_dp_table_size);
197 
198     for (i = ly; i < uy; ++i)
199     {
200         List   *mlist = NULL;
201         List   *best;
202 
203         list_apply_func((List *) sx->index[i], es_add_to_mlist, (void *) &mlist);
204         best = match_epi_dprog((List *) sx->index[i], match_weight_func);
205         list_apply_func(mlist, match_set_match_strength, (void *) &zero);
206         list_apply_func(best, (void (*) ()) match_set_strength_from_weight,
207                         NULL);
208         list_rm_links(mlist);
209         list_rm_links(best);
210     }
211 }
212 

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