/*M///////////////////////////////////////////////////////////////////////////////////////
//
// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
// By downloading, copying, installing or using the software you agree to this license.
// If you do not agree to this license, do not download, install,
// copy or use the software.
//
//
// Intel License Agreement
// For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
// * Redistribution's of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
//
// * Redistribution's in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// * The name of Intel Corporation may not be used to endorse or promote products
// derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/
#include "_cvaux.h"
#include "_cvvm.h"
#include <stdlib.h>
#include <assert.h>
/*======================================================================================*/
CvStatus
icvDynamicCorrespond( int *first, /* first sequence of runs */
/* s0|w0|s1|w1|...|s(n-1)|w(n-1)|sn */
int first_runs, /* number of runs */
int *second, /* second sequence of runs */
int second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
int *second_corr )
{
float Pd, Fi, S;
float Occlusion;
float *costTable;
uchar *matchEdges;
int prev;
int curr;
int baseIndex;
int i, j;
int i_1, j_1;
int n;
int l_beg, r_beg, l_end, r_end, l_len, r_len;
int first_curr;
int second_curr;
int l_color, r_color;
int len_color;
float cost, cost1;
float min1, min2, min3;
float cmin;
uchar cpath;
int row_size;
/* Test arguments for errors */
if( (first == 0) ||
(first_runs < 1) ||
(second == 0) || (second_runs < 1) || (first_corr == 0) || (second_corr == 0) )
return CV_BADFACTOR_ERR;
Pd = 0.95f;
Fi = (float) CV_PI;
S = 1;
Occlusion = (float) log( Pd * Fi / ((1 - Pd) * sqrt( fabs( (CV_PI * 2) * (1. / S) ))));
costTable = (float *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( float ));
if( costTable == 0 )
return CV_OUTOFMEM_ERR;
matchEdges = (uchar *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( uchar ));
if( matchEdges == 0 )
{
cvFree( &costTable );
return CV_OUTOFMEM_ERR;
}
row_size = first_runs + 1;
/* ============= Fill costTable ============= */
costTable[0] = 0.0f;
/* Fill upper line in the cost Table */
prev = first[0];
curr = 2;
for( n = 0; n < first_runs; n++ )
{
l_end = first[curr];
curr += 2;
costTable[n + 1] = costTable[n] + Occlusion * (l_end - prev);
prev = l_end;
} /* for */
/* Fill lefter line in the cost Table */
prev = second[0];
curr = 2;
baseIndex = 0;
for( n = 0; n < second_runs; n++ )
{
l_end = second[curr];
curr += 2;
costTable[baseIndex + row_size] = costTable[baseIndex] + Occlusion * (l_end - prev);
baseIndex += row_size;
prev = l_end;
} /* for */
/* Count costs in the all rest cells */
first_curr = 0;
second_curr = 0;
for( i = 1; i <= first_runs; i++ )
{
for( j = 1; j <= second_runs; j++ )
{
first_curr = (i - 1) * 2;
second_curr = (j - 1) * 2;
l_beg = first[first_curr];
first_curr++;
l_color = first[first_curr];
first_curr++;
l_end = first[first_curr];
l_len = l_end - l_beg + 1;
r_beg = second[second_curr];
second_curr++;
r_color = second[second_curr];
second_curr++;
r_end = second[second_curr];
r_len = r_end - r_beg + 1;
i_1 = i - 1;
j_1 = j - 1;
if( r_len == l_len )
{
cost = 0;
}
else
{
if( r_len > l_len )
{
cost = (float) (r_len * r_len - l_len * l_len) * (1 / (r_len * l_len));
}
else
{
cost = (float) (l_len * l_len - r_len * r_len) * (1 / (r_len * l_len));
}
} /* if */
len_color = r_color - l_color;
cost1 = (float) ((len_color * len_color) >> 2);
min2 = costTable[i_1 + j * row_size] + Occlusion * l_len;
min3 = costTable[i + j_1 * row_size] + Occlusion * r_len;
min1 = costTable[i_1 + j_1 * row_size] + cost + (float) cost1;
if( min1 < min2 )
{
if( min1 < min3 )
{
cmin = min1;
cpath = 1;
}
else
{
cmin = min3;
cpath = 3;
} /* if */
}
else
{
if( min2 < min3 )
{
cmin = min2;
cpath = 2;
}
else
{
cmin = min3;
cpath = 3;
} /* if */
} /* if */
costTable[i + j * row_size] = cmin;
matchEdges[i + j * row_size] = cpath;
} /* for */
} /* for */
/* =========== Reconstruct the Path =========== */
i = first_runs;
j = second_runs;
first_curr = i * 2 - 2;
second_curr = j * 2 - 2;
while( i > 0 && j > 0 )
{
/* Connect begins */
switch (matchEdges[i + j * row_size])
{
case 1: /* to diagonal */
first_corr[first_curr] = second[second_curr];
first_corr[first_curr + 1] = second[second_curr + 2];
second_corr[second_curr] = first[first_curr];
second_corr[second_curr + 1] = first[first_curr + 2];
first_curr -= 2;
second_curr -= 2;
i--;
j--;
break;
case 2: /* to left */
first_corr[first_curr] = second[second_curr + 2];
first_corr[first_curr + 1] = second[second_curr + 2];
first_curr -= 2;
i--;
break;
case 3: /* to up */
second_corr[second_curr] = first[first_curr + 2];
second_corr[second_curr + 1] = first[first_curr + 2];
second_curr -= 2;
j--;
break;
} /* switch */
} /* while */
/* construct rest of horisontal path if its need */
while( i > 0 )
{
first_corr[first_curr] = second[second_curr + 2]; /* connect to begin */
first_corr[first_curr + 1] = second[second_curr + 2]; /* connect to begin */
first_curr -= 2;
i--;
} /* while */
/* construct rest of vertical path if its need */
while( j > 0 )
{
second_corr[second_curr] = first[first_curr + 2];
second_corr[second_curr + 1] = first[first_curr + 2];
second_curr -= 2;
j--;
} /* while */
cvFree( &costTable );
cvFree( &matchEdges );
return CV_NO_ERR;
} /* icvDynamicCorrespond */
/*======================================================================================*/
static CvStatus
icvDynamicCorrespondMulti( int lines, /* number of scanlines */
int *first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
int *first_runs, /* numbers of runs */
int *second, int *second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
int *second_corr )
{
CvStatus error;
int currFirst;
int currSecond;
int currFirstCorr;
int currSecondCorr;
int n;
/* Test errors */
if( (lines < 1) ||
(first == 0) ||
(first_runs == 0) ||
(second == 0) || (second_runs == 0) || (first_corr == 0) || (second_corr == 0) )
return CV_BADFACTOR_ERR;
currFirst = 0;
currSecond = 0;
currFirstCorr = 0;
currSecondCorr = 0;
for( n = 0; n < lines; n++ )
{
error = icvDynamicCorrespond( &(first[currFirst]),
first_runs[n],
&(second[currSecond]),
second_runs[n],
&(first_corr[currFirstCorr]),
&(second_corr[currSecondCorr]) );
if( error != CV_NO_ERR )
return error;
currFirst += first_runs[n] * 2 + 1;
currSecond += second_runs[n] * 2 + 1;
currFirstCorr += first_runs[n] * 2;
currSecondCorr += second_runs[n] * 2;
}
return CV_NO_ERR;
} /* icvDynamicCorrespondMulti */
/*======================================================================================*/
/*F///////////////////////////////////////////////////////////////////////////////////////
// Name: cvDynamicCorrespondMulti
// Purpose: The functions
// Context:
// Parameters:
//
// Notes:
//F*/
CV_IMPL void
cvDynamicCorrespondMulti( int lines, /* number of scanlines */
int *first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
int *first_runs, /* numbers of runs */
int *second, int *second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
int *second_corr )
{
CV_FUNCNAME( "cvDynamicCorrespondMulti" );
__BEGIN__;
IPPI_CALL( icvDynamicCorrespondMulti( lines, /* number of scanlines */
first, /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
first_runs, /* numbers of runs */
second, second_runs, first_corr, /* s0'|e0'|s1'|e1'|... */
second_corr ));
__CLEANUP__;
__END__;
}