16acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*M/////////////////////////////////////////////////////////////////////////////////////// 26acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 36acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 46acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 56acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// By downloading, copying, installing or using the software you agree to this license. 66acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// If you do not agree to this license, do not download, install, 76acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// copy or use the software. 86acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 96acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Intel License Agreement 116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// For Open Source Computer Vision Library 126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Copyright (C) 2000, Intel Corporation, all rights reserved. 146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Third party copyrights are property of their respective owners. 156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Redistribution and use in source and binary forms, with or without modification, 176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// are permitted provided that the following conditions are met: 186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's of source code must retain the above copyright notice, 206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer. 216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's in binary form must reproduce the above copyright notice, 236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer in the documentation 246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and/or other materials provided with the distribution. 256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * The name of Intel Corporation may not be used to endorse or promote products 276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// derived from this software without specific prior written permission. 286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This software is provided by the copyright holders and contributors "as is" and 306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// any express or implied warranties, including, but not limited to, the implied 316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// warranties of merchantability and fitness for a particular purpose are disclaimed. 326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// In no event shall the Intel Corporation or contributors be liable for any direct, 336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// indirect, incidental, special, exemplary, or consequential damages 346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// (including, but not limited to, procurement of substitute goods or services; 356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// loss of use, data, or profits; or business interruption) however caused 366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and on any theory of liability, whether in contract, strict liability, 376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// or tort (including negligence or otherwise) arising in any way out of 386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the use of this software, even if advised of the possibility of such damage. 396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*/ 416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* 436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Partially based on Yossi Rubner code: 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ========================================================================= 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn emd.c 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Last update: 3/14/98 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn An implementation of the Earth Movers Distance. 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Based of the solution for the Transportation problem as described in 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Introduction to Mathematical Programming" by F. S. Hillier and 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn G. J. Lieberman, McGraw-Hill, 1990. 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Copyright (C) 1998 Yossi Rubner 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Computer Science Department, Stanford University 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn E-Mail: rubner@cs.stanford.edu URL: http://vision.stanford.edu/~rubner 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ========================================================================== 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn*/ 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cv.h" 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define MAX_ITERATIONS 500 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define CV_EMD_INF ((float)1e20) 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define CV_EMD_EPS ((float)1e-5) 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* CvNode1D is used for lists, representing 1D sparse array */ 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvNode1D 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float val; 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn struct CvNode1D *next; 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvNode1D; 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* CvNode2D is used for lists, representing 2D sparse matrix */ 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvNode2D 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float val; 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn struct CvNode2D *next[2]; /* next row & next column */ 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvNode2D; 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvEMDState 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ssize, dsize; 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float **cost; 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *_x; 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *end_x; 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *enter_x; 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char **is_x; 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D **rows_x; 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D **cols_x; 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D *u; 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D *v; 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int* idx1; 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int* idx2; 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find_loop buffers */ 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D **loop; 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *is_used; 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* russel buffers */ 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *s; 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *d; 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float **delta; 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float weight, max_cost; 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *buffer; 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvEMDState; 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* static function declaration */ 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus icvInitEMD( const float *signature1, int size1, 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float *signature2, int size2, 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dims, CvDistanceFunction dist_func, void *user_param, 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float* cost, int cost_step, 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvEMDState * state, float *lower_bound, 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *local_buffer, int local_buffer_size ); 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus icvFindBasicVariables( float **cost, char **is_x, 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * u, CvNode1D * v, int ssize, int dsize ); 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float icvIsOptimal( float **cost, char **is_x, 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * u, CvNode1D * v, 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ssize, int dsize, CvNode2D * enter_x ); 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvRussel( CvEMDState * state ); 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus icvNewSolution( CvEMDState * state ); 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvFindLoop( CvEMDState * state ); 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvAddBasicVariable( CvEMDState * state, 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int min_i, int min_j, 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * prev_u_min_i, 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * prev_v_min_j, 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * u_head ); 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float icvDistL2( const float *x, const float *y, void *user_param ); 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float icvDistL1( const float *x, const float *y, void *user_param ); 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float icvDistC( const float *x, const float *y, void *user_param ); 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* The main function */ 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL float 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvCalcEMD2( const CvArr* signature_arr1, 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const CvArr* signature_arr2, 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dist_type, 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvDistanceFunction dist_func, 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const CvArr* cost_matrix, 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvArr* flow_matrix, 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *lower_bound, 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn void *user_param ) 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char local_buffer[16384]; 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *local_buffer_ptr = (char *)cvAlignPtr(local_buffer,16); 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvEMDState state; 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float emd = 0; 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvCalcEMD2" ); 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( &state, 0, sizeof(state)); 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double total_cost = 0; 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvStatus result = CV_NO_ERR; 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float eps, min_delta; 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *xp = 0; 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat sign_stub1, *signature1 = (CvMat*)signature_arr1; 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat sign_stub2, *signature2 = (CvMat*)signature_arr2; 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat cost_stub, *cost = &cost_stub; 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat flow_stub, *flow = (CvMat*)flow_matrix; 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dims, size1, size2; 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( signature1 = cvGetMat( signature1, &sign_stub1 )); 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( signature2 = cvGetMat( signature2, &sign_stub2 )); 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( signature1->cols != signature2->cols ) 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnmatchedSizes, "The arrays must have equal number of columns (which is number of dimensions but 1)" ); 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dims = signature1->cols - 1; 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn size1 = signature1->rows; 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn size2 = signature2->rows; 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_ARE_TYPES_EQ( signature1, signature2 )) 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnmatchedFormats, "The array must have equal types" ); 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_TYPE( signature1->type ) != CV_32FC1 ) 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, "The signatures must be 32fC1" ); 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flow ) 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( flow = cvGetMat( flow, &flow_stub )); 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flow->rows != size1 || flow->cols != size2 ) 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnmatchedSizes, 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The flow matrix size does not match to the signatures' sizes" ); 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_TYPE( flow->type ) != CV_32FC1 ) 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, "The flow matrix must be 32fC1" ); 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cost->data.fl = 0; 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cost->step = 0; 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist_type < 0 ) 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cost_matrix ) 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist_func ) 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Only one of cost matrix or distance function should be non-NULL in case of user-defined distance" ); 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( lower_bound ) 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The lower boundary can not be calculated if the cost matrix is used" ); 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cost = cvGetMat( cost_matrix, &cost_stub )); 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cost->rows != size1 || cost->cols != size2 ) 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnmatchedSizes, 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The cost matrix size does not match to the signatures' sizes" ); 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_TYPE( cost->type ) != CV_32FC1 ) 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, "The cost matrix must be 32fC1" ); 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( !dist_func ) 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "In case of user-defined distance Distance function is undefined" ); 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dims == 0 ) 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadSize, 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Number of dimensions can be 0 only if a user-defined metric is used" ); 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn user_param = (void *) (size_t)dims; 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch (dist_type) 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_DIST_L1: 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_func = icvDistL1; 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_DIST_L2: 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_func = icvDistL2; 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_DIST_C: 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_func = icvDistC; 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadFlag, "Bad or unsupported metric type" ); 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( result = icvInitEMD( signature1->data.fl, size1, 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn signature2->data.fl, size2, 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dims, dist_func, user_param, 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cost->data.fl, cost->step, 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &state, lower_bound, local_buffer_ptr, 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( local_buffer ) - 16 )); 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( result > 0 && lower_bound ) 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn emd = *lower_bound; 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn eps = CV_EMD_EPS * state.max_cost; 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* if ssize = 1 or dsize = 1 then we are done, else ... */ 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( state.ssize > 1 && state.dsize > 1 ) 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int itr; 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( itr = 1; itr < MAX_ITERATIONS; itr++ ) 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find basic variables */ 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = icvFindBasicVariables( state.cost, state.is_x, 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state.u, state.v, state.ssize, state.dsize ); 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( result < 0 ) 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* check for optimality */ 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_delta = icvIsOptimal( state.cost, state.is_x, 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state.u, state.v, 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state.ssize, state.dsize, state.enter_x ); 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_delta == CV_EMD_INF ) 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNoConv, "" ); 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* if no negative deltamin, we found the optimal solution */ 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_delta >= -eps ) 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* improve solution */ 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( icvNewSolution( &state )); 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* compute the total flow */ 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( xp = state._x; xp < state.end_x; xp++ ) 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float val = xp->val; 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i = xp->i; 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int j = xp->j; 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ci = state.idx1[i]; 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int cj = state.idx2[j]; 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( xp != state.enter_x && ci >= 0 && cj >= 0 ) 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn total_cost += (double)val * state.cost[i][j]; 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flow ) 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((float*)(flow->data.ptr + flow->step*ci))[cj] = val; 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn emd = (float) (total_cost / state.weight); 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( state.buffer && state.buffer != local_buffer_ptr ) 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &state.buffer ); 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return emd; 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/************************************************************************************\ 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* initialize structure, allocate buffers and generate initial golution * 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\************************************************************************************/ 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvInitEMD( const float* signature1, int size1, 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float* signature2, int size2, 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dims, CvDistanceFunction dist_func, void* user_param, 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float* cost, int cost_step, 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvEMDState* state, float* lower_bound, 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char* local_buffer, int local_buffer_size ) 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float s_sum = 0, d_sum = 0, diff; 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ssize = 0, dsize = 0; 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int equal_sums = 1; 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int buffer_size; 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float max_cost = 0; 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *buffer, *buffer_end; 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( state, 0, sizeof( *state )); 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cost_step % sizeof(float) == 0 ); 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cost_step /= sizeof(float); 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* calculate buffer size */ 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer_size = (size1+1) * (size2+1) * (sizeof( float ) + /* cost */ 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( char ) + /* is_x */ 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( float )) + /* delta matrix */ 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (size1 + size2 + 2) * (sizeof( CvNode2D ) + /* _x */ 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( CvNode2D * ) + /* cols_x & rows_x */ 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( CvNode1D ) + /* u & v */ 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( float ) + /* s & d */ 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( int ) + sizeof(CvNode2D*)) + /* idx1 & idx2 */ 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (size1+1) * (sizeof( float * ) + sizeof( char * ) + /* rows pointers for */ 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( float * )) + 256; /* cost, is_x and delta */ 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( buffer_size < (int) (dims * 2 * sizeof( float ))) 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer_size = dims * 2 * sizeof( float ); 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* allocate buffers */ 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( local_buffer != 0 && local_buffer_size >= buffer_size ) 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer = local_buffer; 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer = (char*)cvAlloc( buffer_size ); 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !buffer ) 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OUTOFMEM_ERR; 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->buffer = buffer; 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer_end = buffer + buffer_size; 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx1 = (int*) buffer; 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (size1 + 1) * sizeof( int ); 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx2 = (int*) buffer; 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (size2 + 1) * sizeof( int ); 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->s = (float *) buffer; 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (size1 + 1) * sizeof( float ); 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->d = (float *) buffer; 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (size2 + 1) * sizeof( float ); 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* sum up the supply and demand */ 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < size1; i++ ) 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float weight = signature1[i * (dims + 1)]; 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( weight > 0 ) 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s_sum += weight; 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->s[ssize] = weight; 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx1[ssize++] = i; 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( weight < 0 ) 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADRANGE_ERR; 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < size2; i++ ) 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float weight = signature2[i * (dims + 1)]; 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( weight > 0 ) 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d_sum += weight; 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->d[dsize] = weight; 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx2[dsize++] = i; 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( weight < 0 ) 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADRANGE_ERR; 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ssize == 0 || dsize == 0 ) 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADRANGE_ERR; 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* if supply different than the demand, add a zero-cost dummy cluster */ 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn diff = s_sum - d_sum; 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs( diff ) >= CV_EMD_EPS * s_sum ) 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn equal_sums = 0; 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( diff < 0 ) 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->s[ssize] = -diff; 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx1[ssize++] = -1; 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->d[dsize] = diff; 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->idx2[dsize++] = -1; 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->ssize = ssize; 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->dsize = dsize; 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->weight = s_sum > d_sum ? s_sum : d_sum; 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( lower_bound && equal_sums ) /* check lower bound */ 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int sz1 = size1 * (dims + 1), sz2 = size2 * (dims + 1); 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float lb = 0; 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float* xs = (float *) buffer; 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float* xd = xs + dims; 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( xs, 0, dims*sizeof(xs[0])); 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( xd, 0, dims*sizeof(xd[0])); 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < sz1; j += dims + 1 ) 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float weight = signature1[j]; 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dims; i++ ) 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xs[i] += signature1[j + i + 1] * weight; 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < sz2; j += dims + 1 ) 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float weight = signature2[j]; 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dims; i++ ) 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xd[i] += signature2[j + i + 1] * weight; 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lb = dist_func( xs, xd, user_param ) / state->weight; 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = *lower_bound <= lb; 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *lower_bound = lb; 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i ) 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return ( CvStatus ) 1; 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* assign pointers */ 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_used = (char *) buffer; 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* init delta matrix */ 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->delta = (float **) buffer; 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += ssize * sizeof( float * ); 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->delta[i] = (float *) buffer; 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += dsize * sizeof( float ); 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->loop = (CvNode2D **) buffer; 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (ssize + dsize + 1) * sizeof(CvNode2D*); 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->_x = state->end_x = (CvNode2D *) buffer; 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += (ssize + dsize) * sizeof( CvNode2D ); 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* init cost matrix */ 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cost = (float **) buffer; 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += ssize * sizeof( float * ); 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* compute the distance matrix */ 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ci = state->idx1[i]; 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cost[i] = (float *) buffer; 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += dsize * sizeof( float ); 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ci >= 0 ) 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < dsize; j++ ) 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int cj = state->idx2[j]; 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cj < 0 ) 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cost[i][j] = 0; 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float val; 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist_func ) 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn val = dist_func( signature1 + ci * (dims + 1) + 1, 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn signature2 + cj * (dims + 1) + 1, 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn user_param ); 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cost ); 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn val = cost[cost_step*ci + cj]; 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cost[i][j] = val; 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_cost < val ) 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_cost = val; 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < dsize; j++ ) 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cost[i][j] = 0; 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->max_cost = max_cost; 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( buffer, 0, buffer_end - buffer ); 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->rows_x = (CvNode2D **) buffer; 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += ssize * sizeof( CvNode2D * ); 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cols_x = (CvNode2D **) buffer; 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += dsize * sizeof( CvNode2D * ); 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->u = (CvNode1D *) buffer; 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += ssize * sizeof( CvNode1D ); 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->v = (CvNode1D *) buffer; 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += dsize * sizeof( CvNode1D ); 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* init is_x matrix */ 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_x = (char **) buffer; 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += ssize * sizeof( char * ); 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_x[i] = buffer; 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer += dsize; 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( buffer <= buffer_end ); 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRussel( state ); 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->enter_x = (state->end_x)++; 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NO_ERR; 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvFindBasicVariables * 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvFindBasicVariables( float **cost, char **is_x, 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * u, CvNode1D * v, int ssize, int dsize ) 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, found; 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int u_cfound, v_cfound; 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D u0_head, u1_head, *cur_u, *prev_u; 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D v0_head, v1_head, *cur_v, *prev_v; 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* initialize the rows list (u) and the columns list (v) */ 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u0_head.next = u; 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u[i].next = u + i + 1; 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u[ssize - 1].next = 0; 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u1_head.next = 0; 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v0_head.next = ssize > 1 ? v + 1 : 0; 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 1; i < dsize; i++ ) 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[i].next = v + i + 1; 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[dsize - 1].next = 0; 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v1_head.next = 0; 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* there are ssize+dsize variables but only ssize+dsize-1 independent equations, 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn so set v[0]=0 */ 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[0].val = 0; 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v1_head.next = v; 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v1_head.next->next = 0; 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* loop until all variables are found */ 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u_cfound = v_cfound = 0; 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( u_cfound < ssize || v_cfound < dsize ) 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn found = 0; 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( v_cfound < dsize ) 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* loop over all marked columns */ 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v = &v1_head; 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( found |= (cur_v = v1_head.next) != 0; cur_v != 0; cur_v = cur_v->next ) 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float cur_v_val = cur_v->val; 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = (int)(cur_v - v); 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the variables in column j */ 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u = &u0_head; 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_u = u0_head.next; cur_u != 0; ) 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(cur_u - u); 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( is_x[i][j] ) 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* compute u[i] */ 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_u->val = cost[i][j] - cur_v_val; 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* ...and add it to the marked list */ 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u->next = cur_u->next; 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_u->next = u1_head.next; 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u1_head.next = cur_u; 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_u = prev_u->next; 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u = cur_u; 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_u = cur_u->next; 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v->next = cur_v->next; 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v_cfound++; 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( u_cfound < ssize ) 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* loop over all marked rows */ 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u = &u1_head; 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( found |= (cur_u = u1_head.next) != 0; cur_u != 0; cur_u = cur_u->next ) 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float cur_u_val = cur_u->val; 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *_cost; 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *_is_x; 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(cur_u - u); 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _cost = cost[i]; 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _is_x = is_x[i]; 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the variables in rows i */ 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v = &v0_head; 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_v = v0_head.next; cur_v != 0; ) 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = (int)(cur_v - v); 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( _is_x[j] ) 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* compute v[j] */ 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_v->val = _cost[j] - cur_u_val; 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* ...and add it to the marked list */ 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v->next = cur_v->next; 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_v->next = v1_head.next; 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v1_head.next = cur_v; 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_v = prev_v->next; 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v = cur_v; 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_v = cur_v->next; 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u->next = cur_u->next; 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u_cfound++; 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !found ) 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NOTDEFINED_ERR; 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NO_ERR; 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvIsOptimal * 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvIsOptimal( float **cost, char **is_x, 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * u, CvNode1D * v, int ssize, int dsize, CvNode2D * enter_x ) 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float delta, min_delta = CV_EMD_INF; 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, min_i = 0, min_j = 0; 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the minimal cij-ui-vj over all i,j */ 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float u_val = u[i].val; 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *_cost = cost[i]; 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *_is_x = is_x[i]; 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < dsize; j++ ) 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !_is_x[j] ) 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn delta = _cost[j] - u_val - v[j].val; 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_delta > delta ) 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_delta = delta; 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_i = i; 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_j = j; 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn enter_x->i = min_i; 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn enter_x->j = min_j; 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return min_delta; 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvNewSolution * 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvNewSolution( CvEMDState * state ) 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float min_val = CV_EMD_INF; 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int steps; 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D head, *cur_x, *next_x, *leave_x = 0; 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *enter_x = state->enter_x; 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D **loop = state->loop; 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* enter the new basic variable */ 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = enter_x->i; 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = enter_x->j; 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_x[i][j] = 1; 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn enter_x->next[0] = state->rows_x[i]; 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn enter_x->next[1] = state->cols_x[j]; 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn enter_x->val = 0; 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->rows_x[i] = enter_x; 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cols_x[j] = enter_x; 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find a chain reaction */ 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn steps = icvFindLoop( state ); 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( steps == 0 ) 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NOTDEFINED_ERR; 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the largest value in the loop */ 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 1; i < steps; i += 2 ) 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp = loop[i]->val; 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_val > temp ) 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn leave_x = loop[i]; 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_val = temp; 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* update the loop */ 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < steps; i += 2 ) 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp0 = loop[i]->val + min_val; 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp1 = loop[i + 1]->val - min_val; 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn loop[i]->val = temp0; 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn loop[i + 1]->val = temp1; 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* remove the leaving basic variable */ 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = leave_x->i; 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = leave_x->j; 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_x[i][j] = 0; 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn head.next[0] = state->rows_x[i]; 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x = &head; 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( (next_x = cur_x->next[0]) != leave_x ) 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x = next_x; 8066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cur_x ); 8076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x->next[0] = next_x->next[0]; 8096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->rows_x[i] = head.next[0]; 8106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn head.next[1] = state->cols_x[j]; 8126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x = &head; 8136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( (next_x = cur_x->next[1]) != leave_x ) 8146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x = next_x; 8166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cur_x ); 8176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_x->next[1] = next_x->next[1]; 8196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cols_x[j] = head.next[1]; 8206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* set enter_x to be the new empty slot */ 8226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->enter_x = leave_x; 8236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NO_ERR; 8256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 8306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvFindLoop * 8316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 8326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 8336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvFindLoop( CvEMDState * state ) 8346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 8356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, steps = 1; 8366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *new_x; 8376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D **loop = state->loop; 8386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *enter_x = state->enter_x, *_x = state->_x; 8396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char *is_used = state->is_used; 8406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( is_used, 0, state->ssize + state->dsize ); 8426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = loop[0] = enter_x; 8446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_used[enter_x - _x] = 1; 8456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn steps = 1; 8466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 8486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (steps & 1) == 1 ) 8506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find an unused x in the row */ 8526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = state->rows_x[new_x->i]; 8536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( new_x != 0 && is_used[new_x - _x] ) 8546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = new_x->next[0]; 8556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find an unused x in the column, or the entering x */ 8596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = state->cols_x[new_x->j]; 8606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( new_x != 0 && is_used[new_x - _x] && new_x != enter_x ) 8616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = new_x->next[1]; 8626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( new_x == enter_x ) 8636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 8646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( new_x != 0 ) /* found the next x */ 8676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* add x to the loop */ 8696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn loop[steps++] = new_x; 8706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_used[new_x - _x] = 1; 8716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else /* didn't find the next x */ 8736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* backtrack */ 8756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 8766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = steps & 1; 8786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = loop[steps - 1]; 8796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 8806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_x = new_x->next[i]; 8826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( new_x != 0 && is_used[new_x - _x] ); 8846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( new_x == 0 ) 8866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_used[loop[--steps] - _x] = 0; 8886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( new_x == 0 && steps > 0 ); 8916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_used[loop[steps - 1] - _x] = 0; 8936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn loop[steps - 1] = new_x; 8946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_used[new_x - _x] = 1; 8956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( steps > 0 ); 8986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return steps; 9006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 9016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 9056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvRussel * 9066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 9076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 9086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvRussel( CvEMDState * state ) 9096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 9106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, min_i = -1, min_j = -1; 9116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float min_delta, diff; 9126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D u_head, *cur_u, *prev_u; 9136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D v_head, *cur_v, *prev_v; 9146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D *prev_u_min_i = 0, *prev_v_min_j = 0, *remember; 9156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D *u = state->u, *v = state->v; 9166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ssize = state->ssize, dsize = state->dsize; 9176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float eps = CV_EMD_EPS * state->max_cost; 9186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float **cost = state->cost; 9196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float **delta = state->delta; 9206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* initialize the rows list (ur), and the columns list (vr) */ 9226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u_head.next = u; 9236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 9246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u[i].next = u + i + 1; 9266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u[ssize - 1].next = 0; 9286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v_head.next = v; 9306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dsize; i++ ) 9316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[i].val = -CV_EMD_INF; 9336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[i].next = v + i + 1; 9346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[dsize - 1].next = 0; 9366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the maximum row and column values (ur[i] and vr[j]) */ 9386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 9396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float u_val = -CV_EMD_INF; 9416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *cost_row = cost[i]; 9426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < dsize; j++ ) 9446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp = cost_row[j]; 9466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( u_val < temp ) 9486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u_val = temp; 9496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( v[j].val < temp ) 9506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn v[j].val = temp; 9516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn u[i].val = u_val; 9536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* compute the delta matrix */ 9566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < ssize; i++ ) 9576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float u_val = u[i].val; 9596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *delta_row = delta[i]; 9606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *cost_row = cost[i]; 9616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < dsize; j++ ) 9636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn delta_row[j] = cost_row[j] - u_val - v[j].val; 9656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the basic variables */ 9696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 9706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the smallest delta[i][j] */ 9726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_i = -1; 9736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_delta = CV_EMD_INF; 9746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u = &u_head; 9756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_u = u_head.next; cur_u != 0; cur_u = cur_u->next ) 9766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(cur_u - u); 9786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *delta_row = delta[i]; 9796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v = &v_head; 9816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_v = v_head.next; cur_v != 0; cur_v = cur_v->next ) 9826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = (int)(cur_v - v); 9846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_delta > delta_row[j] ) 9856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_delta = delta_row[j]; 9876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_i = i; 9886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_j = j; 9896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u_min_i = prev_u; 9906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v_min_j = prev_v; 9916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v = cur_v; 9936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u = cur_u; 9956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( min_i < 0 ) 9986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* add x[min_i][min_j] to the basis, and adjust supplies and cost */ 10016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn remember = prev_u_min_i->next; 10026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvAddBasicVariable( state, min_i, min_j, prev_u_min_i, prev_v_min_j, &u_head ); 10036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* update the necessary delta[][] */ 10056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( remember == prev_u_min_i->next ) /* line min_i was deleted */ 10066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_v = v_head.next; cur_v != 0; cur_v = cur_v->next ) 10086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = (int)(cur_v - v); 10106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cur_v->val == cost[min_i][j] ) /* column j needs updating */ 10116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float max_val = -CV_EMD_INF; 10136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the new maximum value in the column */ 10156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_u = u_head.next; cur_u != 0; cur_u = cur_u->next ) 10166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp = cost[cur_u - u][j]; 10186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_val < temp ) 10206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_val = temp; 10216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* if needed, adjust the relevant delta[*][j] */ 10246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn diff = max_val - cur_v->val; 10256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_v->val = max_val; 10266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs( diff ) < eps ) 10276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_u = u_head.next; cur_u != 0; cur_u = cur_u->next ) 10296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn delta[cur_u - u][j] += diff; 10306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else /* column min_j was deleted */ 10356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_u = u_head.next; cur_u != 0; cur_u = cur_u->next ) 10376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(cur_u - u); 10396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cur_u->val == cost[i][min_j] ) /* row i needs updating */ 10406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float max_val = -CV_EMD_INF; 10426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* find the new maximum value in the row */ 10446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_v = v_head.next; cur_v != 0; cur_v = cur_v->next ) 10456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp = cost[i][cur_v - v]; 10476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_val < temp ) 10496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_val = temp; 10506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* if needed, adjust the relevant delta[i][*] */ 10536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn diff = max_val - cur_u->val; 10546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_u->val = max_val; 10556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs( diff ) < eps ) 10576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( cur_v = v_head.next; cur_v != 0; cur_v = cur_v->next ) 10596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn delta[i][cur_v - v] += diff; 10606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( u_head.next != 0 || v_head.next != 0 ); 10666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 10676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 10716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* icvAddBasicVariable * 10726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 10736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 10746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvAddBasicVariable( CvEMDState * state, 10756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int min_i, int min_j, 10766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode1D * prev_u_min_i, CvNode1D * prev_v_min_j, CvNode1D * u_head ) 10776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 10786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float temp; 10796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvNode2D *end_x = state->end_x; 10806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( state->s[min_i] < state->d[min_j] + state->weight * CV_EMD_EPS ) 10826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { /* supply exhausted */ 10836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp = state->s[min_i]; 10846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->s[min_i] = 0; 10856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->d[min_j] -= temp; 10866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else /* demand exhausted */ 10886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp = state->d[min_j]; 10906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->d[min_j] = 0; 10916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->s[min_i] -= temp; 10926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* x(min_i,min_j) is a basic variable */ 10956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->is_x[min_i][min_j] = 1; 10966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_x->val = temp; 10986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_x->i = min_i; 10996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_x->j = min_j; 11006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_x->next[0] = state->rows_x[min_i]; 11016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_x->next[1] = state->cols_x[min_j]; 11026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->rows_x[min_i] = end_x; 11036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->cols_x[min_j] = end_x; 11046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn state->end_x = end_x + 1; 11056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* delete supply row only if the empty, and if not last row */ 11076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( state->s[min_i] == 0 && u_head->next->next != 0 ) 11086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_u_min_i->next = prev_u_min_i->next->next; /* remove row from list */ 11096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 11106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_v_min_j->next = prev_v_min_j->next->next; /* remove column from list */ 11116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 11156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* standard metrics * 11166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 11176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float 11186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvDistL1( const float *x, const float *y, void *user_param ) 11196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 11206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, dims = (int)(size_t)user_param; 11216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double s = 0; 11226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dims; i++ ) 11246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double t = x[i] - y[i]; 11266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s += fabs( t ); 11286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return (float)s; 11306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float 11336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvDistL2( const float *x, const float *y, void *user_param ) 11346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 11356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, dims = (int)(size_t)user_param; 11366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double s = 0; 11376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dims; i++ ) 11396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double t = x[i] - y[i]; 11416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s += t * t; 11436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return cvSqrt( (float)s ); 11456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic float 11486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvDistC( const float *x, const float *y, void *user_param ) 11496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 11506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, dims = (int)(size_t)user_param; 11516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double s = 0; 11526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < dims; i++ ) 11546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double t = fabs( x[i] - y[i] ); 11566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s < t ) 11586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = t; 11596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return (float)s; 11616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* End of file. */ 11646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1165