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

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

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

  1 /**@(#)
  2 **/
  3 /* setindex.c
  4  * 
  5  * functions for constructing and handling a raster based 2D spatial index
  6  * of a set of edge contours, the first dimension of the index is the
  7  * raster. elements in the index are stored as an ordered list along
  8  * the raster. the second dimension of the index provides a spatial
  9  * jump along the list.
 10  * 
 11  * it is built prior to stereo matching
 12  * 
 13  * edge contours are indexed at a sub-string level, that is sub-strings
 14  * are constructed for that part of an edge contour that crosses a
 15  * specific raster. Edges may be defined at a much finer scale than the
 16  * scale of the "image" rasters as a result of prior projective scaling
 17  * and warping.
 18  * 
 19  * Edge strings that run in a near vertical direction across the image
 20  * will usually produce very short, mainly unit length, within raster
 21  * sub strings.
 22  * 
 23  * The type of the sub-string is used to indicate the direction it runs
 24  * (either forward of backward) along the raster
 25  * 
 26  * It is also useful to identify those longer sub-sections of edge
 27  * contours that are unique with respect to rasters, ie. sections of
 28  * strings which cross a set of rasters only once. Some strings
 29  * (without max or min in the y direction) only have a single section.
 30  * 
 31  * Each constituent "within raster" sub-string is given a label to
 32  * identify which "raster wise unique" edge sub-string it forms a part.
 33  * Basicly this results in the implicit segmentation of edge contours
 34  * at turning points wrt the y direction. */
 35 
 36 #include <tina/sys.h>
 37 #include <tina/sysfuncs.h>
 38 #include <tina/math.h>
 39 #include <tina/vision.h>
 40 #include <tina/visionfuncs.h>
 41 
 42 /* label for unique string sections (wrt epipolars) */
 43 static int string_label = 0;    /* fist value used is 1 */
 44 
 45 /* add an edge countour string to a stereo index
 46  * 
 47  * involves identifying short sub-strings that run along the current
 48  * raster membership of a raster is defined by truncation of y
 49  * locations
 50  * 
 51  * if a string has gaps with respect to the row spacing (ie inbetween rows
 52  * without any data points on them) the index does not. The closest
 53  * available indexed sub-string is indexed again (perhaps repeatedly
 54  * for larger gaps). Due care must be taken when using the index.
 55  * 
 56  * label members of the raster wise unique edge sub-strings
 57  * 
 58  * leave a hook from the edge to the sub-string it is part of using the
 59  * SINDEX flexible property value of the Edgel */
 60 static void es_add_to_index(List ** index, Tstring * string)
 61 {
 62     List *start;
 63     List *end;
 64     Tstring *laststr = NULL, *str;
 65     int     row, lastrow = 0;
 66     int     incrow = 0;
 67 
 68     if (index == NULL || string == NULL)
 69         return;
 70 
 71     ++string_label;             /* new label for raster wise uniqueness */
 72 
 73     start = string->start;
 74     while (1)
 75     {
 76         row = (int)floor(vec2_y(DD_EDGE_POS(start)));
 77         if (incrow != 0 && incrow * (row - lastrow) < 0)
 78             ++string_label;     /* a change row increment direction */
 79         if (laststr != NULL)
 80             incrow = row - lastrow;
 81 
 82         end = start;
 83         while (1)               /* find rest of string on this raster */
 84         {
 85             if (end == string->end)
 86                 break;
 87             if (row != (int) vec2_y(DD_EDGE_POS(end->next)))
 88                 break;
 89             end = end->next;
 90         }
 91 
 92         if (vec2_x(DD_EDGE_POS(start)) < vec2_x(DD_EDGE_POS(end)))
 93             str = str_make(FORWARD, start, end);
 94         else
 95             str = str_make(BACKWARD, start, end);
 96 
 97         /* add the sub-string to the property list of the edges */
 98         es_add_to_prop_list(str, (void *) str, SINDEX, (void (*) ()) NULL, false);      /* expensive */
 99         /* add the current label to the property list sub-string */
100         str->props = proplist_add(str->props, (void *) string_label, STRING,
101                                   (void (*) ()) NULL);
102 
103         index[row] = ref_addtostart((List *) index[row], (void *) str, STRING);
104 
105         /* fill the index over any gaps in the edge contour string */
106         if (laststr != NULL && abs(row - lastrow) != 1)
107         {
108             int     i, r1 = lastrow, r2 = row;
109 
110             ORDER(int, r1, r2);
111             for (i = r1 + 1; i < r2; ++i)
112             {
113                 if (abs(i - row) <= abs(i - lastrow))
114                     index[i] = ref_addtostart((List *) index[i], (void *) str, STRING);
115                 else
116                     index[i] = ref_addtostart((List *) index[i], (void *) laststr, STRING);
117             }
118         }
119         laststr = str;
120         lastrow = row;
121         if (end == string->end)
122             break;
123         start = end->next;
124     }
125 }
126 
127 /* function used to sort epipolar sub-strings along the raster
128  * 
129  * the type of the string determines the direction, FORWARD or BACKWARD,
130  * it runs along the raster */
131 static double first_xpos(Tstring * string)
132 {
133     if (string->type == FORWARD)
134         return (vec2_x(DD_EDGE_POS(string->start)));
135     else
136         return (vec2_x(DD_EDGE_POS(string->end)));
137 }
138 
139 /* main function for stereo index building
140  * 
141  * takes a list of edge strings representing contours and constructs a
142  * suitable stereo index for them
143  * 
144  * first finds a region that surrounds the edge locations this may have
145  * little to do with the region of the edgerect the latter is
146  * determined by storage requirements wrt original image the former may
147  * subsequently have been subject to a projective transformation
148  * 
149  * then each edge string is considered in tern and added to the rows
150  * 
151  * of the stereo index (this also sets the gross string labels)
152  * 
153  * each row of the index is sorted in the x direction and spatially
154  * indexed */
155 Rindex *strings_set_sindex(List * strings)
156 {
157     List   *sptr;
158     Rindex *sx;
159     Rindex *rx_alloc();
160     List  **index;
161     Imregion *region;
162     Imregion *strings_bounding_region();
163     int     ly, uy;
164     int     i;
165 
166     region = strings_bounding_region(strings);
167     if (region == NULL)
168     {
169         error("sindex: nil region", warning);
170         return (NULL);
171     }
172     ly = region->ly;
173     uy = region->uy;
174     sx = rx_alloc(region, SINDEX);
175     index = (List **) sx->index;
176 
177     for (sptr = strings; sptr != NULL; sptr = sptr->next)
178         es_add_to_index(index, (Tstring *) sptr->to);
179 
180     for (i = ly; i < uy; ++i)
181         index[i] = sort_list(index[i], first_xpos, NULL);
182 
183     return (sx);
184 }
185 
186 /* function for adding/replacing the stereo index of an edgerect
187  * 
188  * updates the SINDEX propety of the edgerect for future reference
189  * 
190  * function strings_set_sindex does the actual work */
191 void    er_set_sindex(Imrect * er)
192 /* edge rect ptr image */
193 {
194     List   *strings;
195     void    rx_free_links();
196     Rindex *sx;
197 
198     if (er == NULL || er->vtype != ptr_v)
199     {
200         error("sindex: passed non edge rect", warning);
201         return;
202     }
203     strings = (List *) prop_get(er->props, STRING);
204     if (strings == NULL)
205     {
206         error("sindex: no strings available", warning);
207         return;
208     }
209     sx = strings_set_sindex(strings);
210     if (sx == NULL)
211         return;
212 
213     er->props = proplist_addifnp(er->props, (void *) sx, SINDEX, rx_free_links, true);
214 }
215 
216 /* apply function to each stereo index sub-string of given string
217  * 
218  * uses the SINDEX property of the edgel to get to the sub-string and from
219  * their the next element and sub-string in the list. */
220 void    es_apply_to_sindex_strings(Tstring * es, void (*func) ( /* ??? */ ), void *data)
221 {
222     List *dptr;
223     List *end;
224 
225     if (es == NULL)
226         return;
227 
228     end = es->end;
229     for (dptr = es->start;; dptr = dptr->next)
230     {
231         Edgel  *e = (Edgel *) dptr->to;
232         Tstring *sub;
233 
234         sub = (Tstring *) prop_get(e->props, SINDEX);
235         if (sub != NULL)
236         {
237             func(sub, STRING, data);
238             dptr = sub->end;
239         }
240         if (dptr == end)
241             break;
242     }
243 }
244 
245 /* apply to every entry of the stereo index
246  * 
247  * note that some entries could have multiple entries */
248 void    er_apply_through_sindex(Imrect * er, void (*func) ( /* ??? */ ), void *data)
249 {
250     Rindex *sx;
251     List   *lptr;
252     int     i;
253 
254     if (er == NULL || (sx = (Rindex *) prop_get(er->props, SINDEX)) == NULL)
255         return;
256 
257     for (i = sx->region->ly; i < sx->region->uy; ++i)
258         for (lptr = (List *) (sx->index[i]); lptr != NULL; lptr = lptr->next)
259             func(lptr->to, lptr->type, data);
260 }
261 
262 /* copy edge string to string of sub-strings */
263 Tstring *string_of_sindex_strings(Tstring * es)
264 {
265     List *start;
266     List *end;
267     List *ptr;
268     List *substrings = NULL;
269 
270     if (es == NULL)
271         return (NULL);
272 
273     start = es->start;
274     end = es->end;
275 
276     for (ptr = start;; ptr = ptr->next)
277     {
278         Edgel  *edge = (Edgel *) ptr->to;
279         Tstring *sub;
280 
281         sub = (Tstring *) prop_get(edge->props, SINDEX);
282         if (sub == NULL)
283             continue;
284         substrings = dd_ref_addtostart(substrings, (void *) sub, STRING);
285         ptr = sub->end;
286         if (ptr == end)
287             break;
288     }
289     if (substrings == NULL)
290         return (NULL);
291     return (str_make(SINDEX, substrings, dd_get_end(substrings)));
292 }
293 

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