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