1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
47 /*======================================================================================*/
50 icvDynamicCorrespond( int *first, /* first sequence of runs */
51 /* s0|w0|s1|w1|...|s(n-1)|w(n-1)|sn */
52 int first_runs, /* number of runs */
53 int *second, /* second sequence of runs */
54 int second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
68 int l_beg, r_beg, l_end, r_end, l_len, r_len;
74 float min1, min2, min3;
79 /* Test arguments for errors */
83 (second == 0) || (second_runs < 1) || (first_corr == 0) || (second_corr == 0) )
85 return CV_BADFACTOR_ERR;
92 Occlusion = (float) log( Pd * Fi / ((1 - Pd) * sqrt( fabs( (CV_PI * 2) * (1. / S) ))));
94 costTable = (float *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( float ));
97 return CV_OUTOFMEM_ERR;
99 matchEdges = (uchar *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( uchar ));
101 if( matchEdges == 0 )
103 cvFree( &costTable );
104 return CV_OUTOFMEM_ERR;
107 row_size = first_runs + 1;
109 /* ============= Fill costTable ============= */
113 /* Fill upper line in the cost Table */
118 for( n = 0; n < first_runs; n++ )
123 costTable[n + 1] = costTable[n] + Occlusion * (l_end - prev);
128 /* Fill lefter line in the cost Table */
134 for( n = 0; n < second_runs; n++ )
137 l_end = second[curr];
139 costTable[baseIndex + row_size] = costTable[baseIndex] + Occlusion * (l_end - prev);
140 baseIndex += row_size;
145 /* Count costs in the all rest cells */
150 for( i = 1; i <= first_runs; i++ )
152 for( j = 1; j <= second_runs; j++ )
155 first_curr = (i - 1) * 2;
156 second_curr = (j - 1) * 2;
158 l_beg = first[first_curr];
160 l_color = first[first_curr];
162 l_end = first[first_curr];
163 l_len = l_end - l_beg + 1;
165 r_beg = second[second_curr];
167 r_color = second[second_curr];
169 r_end = second[second_curr];
170 r_len = r_end - r_beg + 1;
184 cost = (float) (r_len * r_len - l_len * l_len) * (1 / (r_len * l_len));
188 cost = (float) (l_len * l_len - r_len * r_len) * (1 / (r_len * l_len));
192 len_color = r_color - l_color;
194 cost1 = (float) ((len_color * len_color) >> 2);
196 min2 = costTable[i_1 + j * row_size] + Occlusion * l_len;
198 min3 = costTable[i + j_1 * row_size] + Occlusion * r_len;
200 min1 = costTable[i_1 + j_1 * row_size] + cost + (float) cost1;
233 costTable[i + j * row_size] = cmin;
234 matchEdges[i + j * row_size] = cpath;
238 /* =========== Reconstruct the Path =========== */
243 first_curr = i * 2 - 2;
244 second_curr = j * 2 - 2;
247 while( i > 0 && j > 0 )
251 switch (matchEdges[i + j * row_size])
254 case 1: /* to diagonal */
256 first_corr[first_curr] = second[second_curr];
257 first_corr[first_curr + 1] = second[second_curr + 2];
258 second_corr[second_curr] = first[first_curr];
259 second_corr[second_curr + 1] = first[first_curr + 2];
268 case 2: /* to left */
270 first_corr[first_curr] = second[second_curr + 2];
271 first_corr[first_curr + 1] = second[second_curr + 2];
280 second_corr[second_curr] = first[first_curr + 2];
281 second_corr[second_curr + 1] = first[first_curr + 2];
290 /* construct rest of horisontal path if its need */
294 first_corr[first_curr] = second[second_curr + 2]; /* connect to begin */
295 first_corr[first_curr + 1] = second[second_curr + 2]; /* connect to begin */
302 /* construct rest of vertical path if its need */
306 second_corr[second_curr] = first[first_curr + 2];
307 second_corr[second_curr + 1] = first[first_curr + 2];
314 cvFree( &costTable );
315 cvFree( &matchEdges );
318 } /* icvDynamicCorrespond */
321 /*======================================================================================*/
324 icvDynamicCorrespondMulti( int lines, /* number of scanlines */
325 int *first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
326 int *first_runs, /* numbers of runs */
327 int *second, int *second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
343 (second == 0) || (second_runs == 0) || (first_corr == 0) || (second_corr == 0) )
344 return CV_BADFACTOR_ERR;
351 for( n = 0; n < lines; n++ )
354 error = icvDynamicCorrespond( &(first[currFirst]),
356 &(second[currSecond]),
358 &(first_corr[currFirstCorr]),
359 &(second_corr[currSecondCorr]) );
361 if( error != CV_NO_ERR )
364 currFirst += first_runs[n] * 2 + 1;
365 currSecond += second_runs[n] * 2 + 1;
366 currFirstCorr += first_runs[n] * 2;
367 currSecondCorr += second_runs[n] * 2;
373 } /* icvDynamicCorrespondMulti */
376 /*======================================================================================*/
378 /*F///////////////////////////////////////////////////////////////////////////////////////
379 // Name: cvDynamicCorrespondMulti
380 // Purpose: The functions
387 cvDynamicCorrespondMulti( int lines, /* number of scanlines */
388 int *first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
389 int *first_runs, /* numbers of runs */
390 int *second, int *second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
393 IPPI_CALL( icvDynamicCorrespondMulti( lines, /* number of scanlines */
394 first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
395 first_runs, /* numbers of runs */
396 second, second_runs, first_corr, /* s0'|e0'|s1'|e1'|... */