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

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

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