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

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

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