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

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

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

  1 /**@(#)
  2 **/
  3 /* disp_hist.c
  4  * 
  5  * Disparity histograming.
  6  * 
  7  * Used to get spatially localised approximate disparity ranges.
  8  * 
  9  * The spatial localisation leads to the construction of a 2D array of
 10  * histograms resulting in 3D altogether. */
 11 
 12 #include <math.h>
 13 #include <string.h>
 14 #include <tina/sys.h>
 15 #include <tina/sysfuncs.h>
 16 #include <tina/math.h>
 17 #include <tina/mathfuncs.h>
 18 #include <tina/vision.h>
 19 #include <tina/visionfuncs.h>
 20 
 21 #define MIN_COUNT 100
 22 
 23 /* standard binning parameters they scale with image size */
 24 static int im_height = 256;
 25 static int im_width = 256;
 26 static int bin_disp = 5;
 27 static int bin_height = 12;
 28 static int bin_width = 16;
 29 static int row_spacing = 2;
 30 
 31 /* Set bining parameters for given image dimensions. */
 32 void    disp_hist_set_params(int width, int height, int bin_h, int bin_w, int bin_d, int space)
 33 {
 34     im_width = width;
 35     im_height = height;
 36     bin_height = bin_h;
 37     bin_width = bin_w;
 38     bin_disp = bin_d;
 39     row_spacing = space;
 40 }
 41 
 42 /* Update image dimensions and scale other static parameters
 43  * accordingly. */
 44 void    disp_hist_set_image_dimension(int width, int height)
 45 {
 46     if (width != im_width)
 47     {
 48         bin_width = bin_width * width / im_width;
 49         row_spacing = row_spacing * width / im_width;
 50         if (row_spacing == 0)
 51             row_spacing = 1;
 52         im_width = width;
 53     }
 54     if (height != im_height)
 55     {
 56         bin_height = bin_height * height / im_height;
 57         im_height = height;
 58     }
 59 }
 60 
 61 /* Static histogram state parameters to simplify code. */
 62 static Windex *histogram;
 63 static Windex *count;
 64 static int disp_bins;
 65 static double lowd, upd;
 66 
 67 /* Add to the disparity histogram array the matches between left and
 68  * right. Each list corresponds to a row/raster from a stereo index.
 69  * The match_func determines the matchable pairings (NULL is all
 70  * matches). */
 71 static void raster_hist_fill(List * left, List * right, Bool(*match_func) ( /* ??? */ ))
 72 {
 73     List   *lptr;
 74     List   *rptr;
 75     int   **c_index = (int **) count->index;
 76 
 77     for (lptr = left; right != NULL && lptr != NULL; lptr = lptr->next)
 78     {
 79         Tstring *esl, *esr;
 80         double  lowx, upx;
 81         Vec2    vl = {Vec2_id};
 82         Vec2    vr = {Vec2_id};
 83         Ipos    p = {Ipos_id};
 84         int    *hist;
 85 
 86         esl = (Tstring *) lptr->to;
 87         vl = str2_centroid(esl);
 88         lowx = vec2_x(vl) + lowd;
 89         upx = vec2_x(vl) + upd;
 90 
 91         p = wx_get_index(histogram, vl);
 92         hist = (int *) wx_get(histogram, ipos_y(p), ipos_x(p));
 93         if (hist == NULL)       /* outside histogram */
 94             continue;
 95 
 96         c_index[ipos_y(p)][ipos_x(p)]++;
 97 
 98         do
 99         {
100             esr = (Tstring *) right->to;
101             vr = str2_centroid(esr);
102             if (vec2_x(vr) > lowx)
103                 break;
104             right = right->next;
105         } while (right != NULL);
106 
107         for (rptr = right; rptr != NULL && vec2_x(vr) < upx;)
108         {
109             if (match_func == NULL || match_func(esl, esr))
110                 ++hist[(int) (vec2_x(vr) - vec2_x(vl) - lowd) / bin_disp];
111             rptr = rptr->next;
112             if (rptr != NULL)
113             {
114                 esr = (Tstring *) rptr->to;
115                 vr = str2_centroid(esr);
116             }
117         }
118     }
119 }
120 
121 /* Fill disparity histogram array according to matches between entries
122  * in the stereo indices recovered from to the left and right images.
123  * 
124  * Rows of the overlapping sections of the stereo indies are sampled
125  * according to the static row_spacing parameter.
126  * 
127  * Matches from each row/raster are entered using raster_hist_fill. */
128 static void sindex_hist_fill(Rindex * sx_l, Rindex * sx_r, Bool(*match_func) ( /* ??? */ ))
129 {
130     int     lrow, urow;
131     int     i;
132 
133     lrow = MAX(sx_l->region->ly, sx_r->region->ly);
134     urow = MIN(sx_l->region->uy, sx_r->region->uy);
135 
136     for (i = lrow; i < urow; i += row_spacing)
137     {
138         List   *left = (List *) sx_l->index[i];
139         List   *right = (List *) sx_r->index[i];
140 
141         raster_hist_fill(left, right, match_func);
142     }
143 }
144 
145 /* Add two histograms of length n. */
146 static void hist_add(int *h1, int *h2, int n)
147 {
148     int     i;
149 
150     for (i = 0; i < n; ++i)
151         h1[i] += h2[i];
152 }
153 
154 /* Accumulate disparity histograms spatially to give larger samples.
155  * 
156  * Each histogram and count value is replaced by the sum of histograms and
157  * counts in an area around it.
158  * 
159  * The locality over which each individual the histogram is summed is
160  * determined by the count accumulation which should exceed MIN_COUNT.
161  * 
162  * Hence image regions with sparse features will accumulate over larger
163  * areas than those with dense features (which may not accumulate at
164  * all).
165  * 
166  * The aim is to get a significant sample to work with. */
167 static void accum_hist(void)
168 {
169     Windex *accum;
170     Windex *total;
171     int  ***index1, ***index2;
172     int   **c1, **c2;
173     int     i, j, m, n, bins, r, maxr;
174 
175     if (histogram == NULL)
176         return;
177 
178     m = histogram->m;
179     n = histogram->n;
180     bins = disp_bins * sizeof(int);
181     maxr = MAX(m, n);
182 
183     accum = wx_alloc(histogram->region, m, n, (int) NULL);
184     total = wx_alloc(count->region, m, n, (int) NULL);
185 
186     index1 = (int ***) accum->index;
187     index2 = (int ***) histogram->index;
188     for (i = 0; i < m; ++i)
189         for (j = 0; j < n; ++j)
190         {
191             index1[i][j] = (int *) ralloc((unsigned) bins);
192             (void) memcpy((char *) index1[i][j], (char *) index2[i][j], bins);
193         }
194 
195     c1 = (int **) total->index;
196     c2 = (int **) count->index;
197 
198     for (i = 0; i < m; ++i)
199         for (j = 0; j < n; ++j)
200         {
201             int     tot = c2[i][j];
202 
203             for (r = 1; r < maxr && tot < MIN_COUNT; ++r)
204             {
205                 int     ii, jj;
206 
207                 ii = i - r;
208                 for (jj = j - r; ii >= 0 && jj <= j + r && jj < n; ++jj)
209                 {
210                     if (jj < 0)
211                         continue;
212                     tot += c2[ii][jj];
213                     hist_add(index1[i][j], index2[ii][jj], disp_bins);
214                 }
215                 ii = i + r;
216                 for (jj = j - r; ii < m && jj <= j + r && jj < n; ++jj)
217                 {
218                     if (jj < 0)
219                         continue;
220                     tot += c2[ii][jj];
221                     hist_add(index1[i][j], index2[ii][jj], disp_bins);
222                 }
223                 jj = j - r;
224                 for (ii = i - r + 1; jj >= 0 && ii < i + r && ii < m; ++ii)
225                 {
226                     if (ii < 0)
227                         continue;
228                     tot += c2[ii][jj];
229                     hist_add(index1[i][j], index2[ii][jj], disp_bins);
230                 }
231                 jj = j + r;
232                 for (ii = i - r + 1; jj < n && ii < i + r && ii < m; ++ii)
233                 {
234                     if (ii < 0)
235                         continue;
236                     tot += c2[ii][jj];
237                     hist_add(index1[i][j], index2[ii][jj], disp_bins);
238                 }
239             }
240             c1[i][j] = tot;
241         }
242     wx_free(histogram, rfree);
243     histogram = accum;
244     wx_free(count, (void (*) ()) NULL);
245     count = total;
246 }
247 
248 /* The final stage in disparity range estimation using histograms is to
249  * interpret each individual local histogram in the context of its
250  * sample size.
251  * 
252  * A threshold based upon sample size is used to identify lower and upper
253  * disparity limits which are returned as range vectors (Vec2s). */
254 static void hist_set_range(Windex * range)
255 {
256     int  ***index;
257     int   **c;
258     Vec2 ***disp;
259     int     i, j, k, m, n;
260     int     dbm1 = disp_bins - 1;
261 
262     if (range == NULL || histogram == NULL)
263         return;
264 
265     m = range->m;
266     n = range->n;
267 
268     if (m != histogram->m || n != histogram->n)
269         return;
270 
271     index = (int ***) histogram->index;
272     c = (int **) count->index;
273     disp = (Vec2 ***) range->index;
274 
275     for (i = 0; i < m; ++i)
276         for (j = 0; j < n; ++j)
277         {
278             int     thres = c[i][j] / 5;
279             int    *hist = index[i][j];
280 
281             for (k = 0; k < dbm1; ++k)
282                 if (hist[k] + hist[k + 1] > thres)
283                     break;
284             if (k < dbm1)
285                 vec2_x(*disp[i][j]) = (float)(lowd + (k - 1) * bin_disp);
286             else
287                 vec2_x(*disp[i][j]) = (float)lowd;
288 
289             for (k = dbm1; k > 0; --k)
290                 if (hist[k] + hist[k - 1] > thres)
291                     break;
292             if (k > 0)
293                 vec2_y(*disp[i][j]) = (float)(lowd + (k + 1) * bin_disp);
294             else
295                 vec2_y(*disp[i][j]) = (float)upd;
296         }
297 }
298 
299 /* Primary external function for disparity histogram construction.
300  * 
301  * Requires appropriate image dimension parameters to be set prior to call
302  * using either disp_hist_set_image_dimension or disp_hist_set_params.
303  * 
304  * Sets static overall disparity range parameters.
305  * 
306  * Allocates 3D histogram and 2D count arrays for the left image stereo
307  * index. */
308 Windex *sindex_disp_hist(Rindex * sx_left, Rindex * sx_right, double lowdisp, double updisp, Bool(*match_func) ( /* ??? */ ))
309 
310 /* max disp range */
311 
312 /* edge string match test (NULL for all matches) */
313 {
314     Windex *disp_range;
315     Imregion *region;
316     int     i, j, m, n, bins;
317     int  ***index;
318 
319     if (sx_left == NULL || sx_right == NULL)
320         return (NULL);
321 
322     region = sx_left->region;
323     m = (region->uy - region->ly) / bin_height + 1;
324     n = (region->ux - region->lx) / bin_width + 1;
325 
326     lowd = lowdisp;
327     upd = updisp;
328     disp_bins = (int)((upd - lowd) / bin_disp + 1);
329     bins = disp_bins * sizeof(int);
330 
331     histogram = wx_alloc(region, m, n, (int) NULL);
332     count = wx_alloc(region, m, n, (int) NULL);
333     index = (int ***) histogram->index;
334     for (i = 0; i < m; ++i)
335         for (j = 0; j < n; ++j)
336         {
337             index[i][j] = (int *) ralloc((unsigned) bins);
338             (void) memset((char *) index[i][j], 0, bins);
339         }
340 
341     sindex_hist_fill(sx_left, sx_right, match_func);
342     accum_hist();
343     disp_range = disp_range_build(region, m, n);
344     hist_set_range(disp_range);
345     wx_free(histogram, rfree);
346     wx_free(count, (void (*) ()) NULL);
347     return (disp_range);
348 }
349 
350 /* Edgerect level wrapper around sindex_disp_hist.
351  * 
352  * Sets the appropriate image dimension parameters and recovers left and
353  * right stereo index data structures from the respective property
354  * lists of the edgerects. */
355 Windex *er_disp_hist(Imrect * er_left, Imrect * er_right, double lowdisp, double updisp, Bool(*match_func) ( /* ??? */ ))
356 /* imrects containing left and right edges */
357 /* max disp range */
358 
359 /* edge string match test (NULL for all matches) */
360 {
361     Rindex *sx_left;
362     Rindex *sx_right;
363 
364     if (er_left == NULL || er_right == NULL)
365         return (NULL);
366 
367     disp_hist_set_image_dimension(er_left->width, er_left->height);
368     sx_left = (Rindex *) prop_get(er_left->props, SINDEX);
369     sx_right = (Rindex *) prop_get(er_right->props, SINDEX);
370 
371     if (sx_left == NULL || sx_right == NULL)
372         return (NULL);
373     return (sindex_disp_hist(sx_left, sx_right, lowdisp, updisp, match_func));
374 }
375 

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