1da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian/*M/////////////////////////////////////////////////////////////////////////////////////// 2da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 3da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 5da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// By downloading, copying, installing or using the software you agree to this license. 6da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// If you do not agree to this license, do not download, install, 7da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// copy or use the software. 8da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 9da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 10da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// Intel License Agreement 11da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// For Open Source Computer Vision Library 12da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 13da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// Copyright (C) 2000, Intel Corporation, all rights reserved. 14da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// Third party copyrights are property of their respective owners. 15da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 16da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// Redistribution and use in source and binary forms, with or without modification, 17da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// are permitted provided that the following conditions are met: 18da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 19da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// * Redistribution's of source code must retain the above copyright notice, 20da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// this list of conditions and the following disclaimer. 21da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 22da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// * Redistribution's in binary form must reproduce the above copyright notice, 23da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// this list of conditions and the following disclaimer in the documentation 24da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// and/or other materials provided with the distribution. 25da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 26da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// * The name of Intel Corporation may not be used to endorse or promote products 27da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// derived from this software without specific prior written permission. 28da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 29da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// This software is provided by the copyright holders and contributors "as is" and 30da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// any express or implied warranties, including, but not limited to, the implied 31da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// warranties of merchantability and fitness for a particular purpose are disclaimed. 32da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// In no event shall the Intel Corporation or contributors be liable for any direct, 33da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// indirect, incidental, special, exemplary, or consequential damages 34da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// (including, but not limited to, procurement of substitute goods or services; 35da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// loss of use, data, or profits; or business interruption) however caused 36da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// and on any theory of liability, whether in contract, strict liability, 37da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// or tort (including negligence or otherwise) arising in any way out of 38da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// the use of this software, even if advised of the possibility of such damage. 39da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian// 40da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian//M*/ 41da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian#include "_cv.h" 42da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 43da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian#define ICV_DIST_SHIFT 16 44da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian#define ICV_INIT_DIST0 (INT_MAX >> 2) 45da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 46da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanianstatic CvStatus 47da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh VenkatasubramanianicvInitTopBottom( int* temp, int tempstep, CvSize size, int border ) 48da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian{ 49da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int i, j; 50da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = 0; i < border; i++ ) 51da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 52da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* ttop = (int*)(temp + i*tempstep); 53da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tbottom = (int*)(temp + (size.height + border*2 - i - 1)*tempstep); 54da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 55da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < size.width + border*2; j++ ) 56da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 57da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian ttop[j] = ICV_INIT_DIST0; 58da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tbottom[j] = ICV_INIT_DIST0; 59da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 60da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 61da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 62da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian return CV_OK; 63da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian} 64da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 65da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 66da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanianstatic CvStatus CV_STDCALL 67da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh VenkatasubramanianicvDistanceTransform_3x3_C1R( const uchar* src, int srcstep, int* temp, 68da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int step, float* dist, int dststep, CvSize size, const float* metrics ) 69da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian{ 70da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int BORDER = 1; 71da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int i, j; 72da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT ); 73da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT ); 74da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const float scale = 1.f/(1 << ICV_DIST_SHIFT); 75da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 76da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian srcstep /= sizeof(src[0]); 77da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian step /= sizeof(temp[0]); 78da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian dststep /= sizeof(dist[0]); 79da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 80da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian icvInitTopBottom( temp, step, size, BORDER ); 81da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 82da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // forward pass 83da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = 0; i < size.height; i++ ) 84da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 85da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const uchar* s = src + i*srcstep; 86da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 87da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 88da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < BORDER; j++ ) 89da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0; 90da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 91da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < size.width; j++ ) 92da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 93da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( !s[j] ) 94da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = 0; 95da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian else 96da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 97da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = tmp[j-step-1] + DIAG_DIST; 98da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t = tmp[j-step] + HV_DIST; 99da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 100da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step+1] + DIAG_DIST; 101da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 102da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-1] + HV_DIST; 103da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 104da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 105da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 106da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 107da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 108da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 109da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // backward pass 110da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = size.height - 1; i >= 0; i-- ) 111da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 112da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian float* d = (float*)(dist + i*dststep); 113da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 114da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 115da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = size.width - 1; j >= 0; j-- ) 116da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 117da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = tmp[j]; 118da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > HV_DIST ) 119da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 120da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t = tmp[j+step+1] + DIAG_DIST; 121da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 122da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step] + HV_DIST; 123da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 124da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step-1] + DIAG_DIST; 125da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 126da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+1] + HV_DIST; 127da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 128da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 129da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 130da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian d[j] = (float)(t0 * scale); 131da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 132da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 133da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 134da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian return CV_OK; 135da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian} 136da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 137da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 138da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanianstatic CvStatus CV_STDCALL 139da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh VenkatasubramanianicvDistanceTransform_5x5_C1R( const uchar* src, int srcstep, int* temp, 140da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int step, float* dist, int dststep, CvSize size, const float* metrics ) 141da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian{ 142da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int BORDER = 2; 143da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int i, j; 144da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT ); 145da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT ); 146da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int LONG_DIST = CV_FLT_TO_FIX( metrics[2], ICV_DIST_SHIFT ); 147da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const float scale = 1.f/(1 << ICV_DIST_SHIFT); 148da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 149da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian srcstep /= sizeof(src[0]); 150da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian step /= sizeof(temp[0]); 151da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian dststep /= sizeof(dist[0]); 152da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 153da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian icvInitTopBottom( temp, step, size, BORDER ); 154da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 155da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // forward pass 156da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = 0; i < size.height; i++ ) 157da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 158da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const uchar* s = src + i*srcstep; 159da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 160da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 161da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < BORDER; j++ ) 162da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0; 163da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 164da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < size.width; j++ ) 165da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 166da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( !s[j] ) 167da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = 0; 168da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian else 169da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 170da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = tmp[j-step*2-1] + LONG_DIST; 171da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t = tmp[j-step*2+1] + LONG_DIST; 172da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 173da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step-2] + LONG_DIST; 174da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 175da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step-1] + DIAG_DIST; 176da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 177da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step] + HV_DIST; 178da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 179da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step+1] + DIAG_DIST; 180da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 181da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step+2] + LONG_DIST; 182da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 183da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-1] + HV_DIST; 184da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 185da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 186da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 187da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 188da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 189da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 190da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // backward pass 191da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = size.height - 1; i >= 0; i-- ) 192da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 193da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian float* d = (float*)(dist + i*dststep); 194da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 195da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 196da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = size.width - 1; j >= 0; j-- ) 197da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 198da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = tmp[j]; 199da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > HV_DIST ) 200da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 201da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t = tmp[j+step*2+1] + LONG_DIST; 202da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 203da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step*2-1] + LONG_DIST; 204da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 205da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step+2] + LONG_DIST; 206da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 207da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step+1] + DIAG_DIST; 208da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 209da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step] + HV_DIST; 210da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 211da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step-1] + DIAG_DIST; 212da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 213da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step-2] + LONG_DIST; 214da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 215da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+1] + HV_DIST; 216da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) t0 = t; 217da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 218da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 219da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian d[j] = (float)(t0 * scale); 220da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 221da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 222da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 223da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian return CV_OK; 224da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian} 225da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 226da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 227da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanianstatic CvStatus CV_STDCALL 228da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh VenkatasubramanianicvDistanceTransformEx_5x5_C1R( const uchar* src, int srcstep, int* temp, 229da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int step, float* dist, int dststep, int* labels, int lstep, 230da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian CvSize size, const float* metrics ) 231da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian{ 232da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int BORDER = 2; 233da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 234da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int i, j; 235da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT ); 236da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT ); 237da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const int LONG_DIST = CV_FLT_TO_FIX( metrics[2], ICV_DIST_SHIFT ); 238da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const float scale = 1.f/(1 << ICV_DIST_SHIFT); 239da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 240da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian srcstep /= sizeof(src[0]); 241da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian step /= sizeof(temp[0]); 242da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian dststep /= sizeof(dist[0]); 243da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian lstep /= sizeof(labels[0]); 244da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 245da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian icvInitTopBottom( temp, step, size, BORDER ); 246da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 247da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // forward pass 248da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = 0; i < size.height; i++ ) 249da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 250da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian const uchar* s = src + i*srcstep; 251da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 252da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* lls = (int*)(labels + i*lstep); 253da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 254da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < BORDER; j++ ) 255da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0; 256da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 257da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = 0; j < size.width; j++ ) 258da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 259da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( !s[j] ) 260da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 261da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = 0; 262da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian //assert( lls[j] != 0 ); 263da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 264da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian else 265da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 266da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = ICV_INIT_DIST0, t; 267da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int l0 = 0; 268da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 269da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step*2-1] + LONG_DIST; 270da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 271da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 272da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 273da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep*2-1]; 274da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 275da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step*2+1] + LONG_DIST; 276da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 277da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 278da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 279da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep*2+1]; 280da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 281da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step-2] + LONG_DIST; 282da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 283da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 284da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 285da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep-2]; 286da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 287da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step-1] + DIAG_DIST; 288da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 289da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 290da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 291da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep-1]; 292da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 293da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step] + HV_DIST; 294da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 295da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 296da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 297da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep]; 298da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 299da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step+1] + DIAG_DIST; 300da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 301da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 302da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 303da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep+1]; 304da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 305da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-step+2] + LONG_DIST; 306da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 307da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 308da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 309da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-lstep+2]; 310da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 311da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j-1] + HV_DIST; 312da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 313da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 314da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 315da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j-1]; 316da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 317da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 318da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 319da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian lls[j] = l0; 320da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 321da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 322da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 323da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 324da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian // backward pass 325da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( i = size.height - 1; i >= 0; i-- ) 326da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 327da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian float* d = (float*)(dist + i*dststep); 328da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER; 329da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int* lls = (int*)(labels + i*lstep); 330da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 331da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian for( j = size.width - 1; j >= 0; j-- ) 332da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 333da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t0 = tmp[j]; 334da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int l0 = lls[j]; 335da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > HV_DIST ) 336da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 337da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian int t = tmp[j+step*2+1] + LONG_DIST; 338da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 339da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 340da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 341da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep*2+1]; 342da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 343da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step*2-1] + LONG_DIST; 344da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 345da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 346da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 347da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep*2-1]; 348da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 349da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step+2] + LONG_DIST; 350da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 351da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 352da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 353da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep+2]; 354da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 355da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step+1] + DIAG_DIST; 356da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 357da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 358da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 359da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep+1]; 360da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 361da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step] + HV_DIST; 362da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 363da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 364da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 365da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep]; 366da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 367da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step-1] + DIAG_DIST; 368da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 369da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 370da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 371da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep-1]; 372da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 373da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+step-2] + LONG_DIST; 374da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 375da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 376da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 377da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+lstep-2]; 378da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 379da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t = tmp[j+1] + HV_DIST; 380da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian if( t0 > t ) 381da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian { 382da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian t0 = t; 383da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian l0 = lls[j+1]; 384da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 385da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian tmp[j] = t0; 386da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian lls[j] = l0; 387da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 388da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian d[j] = (float)(t0 * scale); 389da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 390da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian } 391da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 392da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian return CV_OK; 393da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian} 394da49e34c1fb5e99681f4ad99c21d9cfd83eddb96Vignesh Venkatasubramanian 395 396static CvStatus 397icvGetDistanceTransformMask( int maskType, float *metrics ) 398{ 399 if( !metrics ) 400 return CV_NULLPTR_ERR; 401 402 switch (maskType) 403 { 404 case 30: 405 metrics[0] = 1.0f; 406 metrics[1] = 1.0f; 407 break; 408 409 case 31: 410 metrics[0] = 1.0f; 411 metrics[1] = 2.0f; 412 break; 413 414 case 32: 415 metrics[0] = 0.955f; 416 metrics[1] = 1.3693f; 417 break; 418 419 case 50: 420 metrics[0] = 1.0f; 421 metrics[1] = 1.0f; 422 metrics[2] = 2.0f; 423 break; 424 425 case 51: 426 metrics[0] = 1.0f; 427 metrics[1] = 2.0f; 428 metrics[2] = 3.0f; 429 break; 430 431 case 52: 432 metrics[0] = 1.0f; 433 metrics[1] = 1.4f; 434 metrics[2] = 2.1969f; 435 break; 436 default: 437 return CV_BADRANGE_ERR; 438 } 439 440 return CV_OK; 441} 442 443 444static void 445icvTrueDistTrans( const CvMat* src, CvMat* dst ) 446{ 447 CvMat* buffer = 0; 448 449 CV_FUNCNAME( "cvDistTransform2" ); 450 451 __BEGIN__; 452 453 int i, m, n; 454 int sstep, dstep; 455 const float inf = 1e6f; 456 int thread_count = cvGetNumThreads(); 457 int pass1_sz, pass2_sz; 458 459 if( !CV_ARE_SIZES_EQ( src, dst )) 460 CV_ERROR( CV_StsUnmatchedSizes, "" ); 461 462 if( CV_MAT_TYPE(src->type) != CV_8UC1 || 463 CV_MAT_TYPE(dst->type) != CV_32FC1 ) 464 CV_ERROR( CV_StsUnsupportedFormat, 465 "The input image must have 8uC1 type and the output one must have 32fC1 type" ); 466 467 m = src->rows; 468 n = src->cols; 469 470 // (see stage 1 below): 471 // sqr_tab: 2*m, sat_tab: 3*m + 1, d: m*thread_count, 472 pass1_sz = src->rows*(5 + thread_count) + 1; 473 // (see stage 2): 474 // sqr_tab & inv_tab: n each; f & v: n*thread_count each; z: (n+1)*thread_count 475 pass2_sz = src->cols*(2 + thread_count*3) + thread_count; 476 CV_CALL( buffer = cvCreateMat( 1, MAX(pass1_sz, pass2_sz), CV_32FC1 )); 477 478 sstep = src->step; 479 dstep = dst->step / sizeof(float); 480 481 // stage 1: compute 1d distance transform of each column 482 { 483 float* sqr_tab = buffer->data.fl; 484 int* sat_tab = (int*)(sqr_tab + m*2); 485 const int shift = m*2; 486 487 for( i = 0; i < m; i++ ) 488 sqr_tab[i] = (float)(i*i); 489 for( i = m; i < m*2; i++ ) 490 sqr_tab[i] = inf; 491 for( i = 0; i < shift; i++ ) 492 sat_tab[i] = 0; 493 for( ; i <= m*3; i++ ) 494 sat_tab[i] = i - shift; 495 496#ifdef _OPENMP 497 #pragma omp parallel for num_threads(thread_count) 498#endif 499 for( i = 0; i < n; i++ ) 500 { 501 const uchar* sptr = src->data.ptr + i + (m-1)*sstep; 502 float* dptr = dst->data.fl + i; 503 int* d = (int*)(sat_tab + m*3+1+m*cvGetThreadNum()); 504 int j, dist = m-1; 505 506 for( j = m-1; j >= 0; j--, sptr -= sstep ) 507 { 508 dist = (dist + 1) & (sptr[0] == 0 ? 0 : -1); 509 d[j] = dist; 510 } 511 512 dist = m-1; 513 for( j = 0; j < m; j++, dptr += dstep ) 514 { 515 dist = dist + 1 - sat_tab[dist + 1 - d[j] + shift]; 516 d[j] = dist; 517 dptr[0] = sqr_tab[dist]; 518 } 519 } 520 } 521 522 // stage 2: compute modified distance transform for each row 523 { 524 float* inv_tab = buffer->data.fl; 525 float* sqr_tab = inv_tab + n; 526 527 inv_tab[0] = sqr_tab[0] = 0.f; 528 for( i = 1; i < n; i++ ) 529 { 530 inv_tab[i] = (float)(0.5/i); 531 sqr_tab[i] = (float)(i*i); 532 } 533 534#ifdef _OPENMP 535 #pragma omp parallel for num_threads(thread_count) schedule(dynamic) 536#endif 537 for( i = 0; i < m; i++ ) 538 { 539 float* d = (float*)(dst->data.ptr + i*dst->step); 540 float* f = sqr_tab + n + (n*3+1)*cvGetThreadNum(); 541 float* z = f + n; 542 int* v = (int*)(z + n + 1); 543 int p, q, k; 544 545 v[0] = 0; 546 z[0] = -inf; 547 z[1] = inf; 548 f[0] = d[0]; 549 550 for( q = 1, k = 0; q < n; q++ ) 551 { 552 float fq = d[q]; 553 f[q] = fq; 554 555 for(;;k--) 556 { 557 p = v[k]; 558 float s = (fq + sqr_tab[q] - d[p] - sqr_tab[p])*inv_tab[q - p]; 559 if( s > z[k] ) 560 { 561 k++; 562 v[k] = q; 563 z[k] = s; 564 z[k+1] = inf; 565 break; 566 } 567 } 568 } 569 570 for( q = 0, k = 0; q < n; q++ ) 571 { 572 while( z[k+1] < q ) 573 k++; 574 p = v[k]; 575 d[q] = sqr_tab[abs(q - p)] + f[p]; 576 } 577 } 578 } 579 580 cvPow( dst, dst, 0.5 ); 581 582 __END__; 583 584 cvReleaseMat( &buffer ); 585} 586 587 588/*********************************** IPP functions *********************************/ 589 590icvDistanceTransform_3x3_8u32f_C1R_t icvDistanceTransform_3x3_8u32f_C1R_p = 0; 591icvDistanceTransform_5x5_8u32f_C1R_t icvDistanceTransform_5x5_8u32f_C1R_p = 0; 592icvDistanceTransform_3x3_8u_C1IR_t icvDistanceTransform_3x3_8u_C1IR_p = 0; 593icvDistanceTransform_3x3_8u_C1R_t icvDistanceTransform_3x3_8u_C1R_p = 0; 594 595typedef CvStatus (CV_STDCALL * CvIPPDistTransFunc)( const uchar* src, int srcstep, 596 void* dst, int dststep, 597 CvSize size, const void* metrics ); 598 599typedef CvStatus (CV_STDCALL * CvIPPDistTransFunc2)( uchar* src, int srcstep, 600 CvSize size, const int* metrics ); 601 602/***********************************************************************************/ 603 604typedef CvStatus (CV_STDCALL * CvDistTransFunc)( const uchar* src, int srcstep, 605 int* temp, int tempstep, 606 float* dst, int dststep, 607 CvSize size, const float* metrics ); 608 609 610/****************************************************************************************\ 611 User-contributed code: 612 613 Non-inplace and Inplace 8u->8u Distance Transform for CityBlock (a.k.a. L1) metric 614 (C) 2006 by Jay Stavinzky. 615\****************************************************************************************/ 616 617//BEGIN ATS ADDITION 618/* 8-bit grayscale distance transform function */ 619static void 620icvDistanceATS_L1_8u( const CvMat* src, CvMat* dst ) 621{ 622 CV_FUNCNAME( "cvDistanceATS" ); 623 624 __BEGIN__; 625 626 int width = src->cols, height = src->rows; 627 628 int a; 629 uchar lut[256]; 630 int x, y; 631 632 const uchar *sbase = src->data.ptr; 633 uchar *dbase = dst->data.ptr; 634 int srcstep = src->step; 635 int dststep = dst->step; 636 637 CV_ASSERT( CV_IS_MASK_ARR( src ) && CV_MAT_TYPE( dst->type ) == CV_8UC1 ); 638 CV_ASSERT( CV_ARE_SIZES_EQ( src, dst )); 639 640 ////////////////////// forward scan //////////////////////// 641 for( x = 0; x < 256; x++ ) 642 lut[x] = CV_CAST_8U(x+1); 643 644 //init first pixel to max (we're going to be skipping it) 645 dbase[0] = (uchar)(sbase[0] == 0 ? 0 : 255); 646 647 //first row (scan west only, skip first pixel) 648 for( x = 1; x < width; x++ ) 649 dbase[x] = (uchar)(sbase[x] == 0 ? 0 : lut[dbase[x-1]]); 650 651 for( y = 1; y < height; y++ ) 652 { 653 sbase += srcstep; 654 dbase += dststep; 655 656 //for left edge, scan north only 657 a = sbase[0] == 0 ? 0 : lut[dbase[-dststep]]; 658 dbase[0] = (uchar)a; 659 660 for( x = 1; x < width; x++ ) 661 { 662 a = sbase[x] == 0 ? 0 : lut[MIN(a, dbase[x - dststep])]; 663 dbase[x] = (uchar)a; 664 } 665 } 666 667 ////////////////////// backward scan /////////////////////// 668 669 a = dbase[width-1]; 670 671 // do last row east pixel scan here (skip bottom right pixel) 672 for( x = width - 2; x >= 0; x-- ) 673 { 674 a = lut[a]; 675 dbase[x] = (uchar)(CV_CALC_MIN_8U(a, dbase[x])); 676 } 677 678 // right edge is the only error case 679 for( y = height - 2; y >= 0; y-- ) 680 { 681 dbase -= dststep; 682 683 // do right edge 684 a = lut[dbase[width-1+dststep]]; 685 dbase[width-1] = (uchar)(MIN(a, dbase[width-1])); 686 687 for( x = width - 2; x >= 0; x-- ) 688 { 689 int b = dbase[x+dststep]; 690 a = lut[MIN(a, b)]; 691 dbase[x] = (uchar)(MIN(a, dbase[x])); 692 } 693 } 694 695 __END__; 696} 697//END ATS ADDITION 698 699 700/* Wrapper function for distance transform group */ 701CV_IMPL void 702cvDistTransform( const void* srcarr, void* dstarr, 703 int distType, int maskSize, 704 const float *mask, 705 void* labelsarr ) 706{ 707 CvMat* temp = 0; 708 CvMat* src_copy = 0; 709 CvMemStorage* st = 0; 710 711 CV_FUNCNAME( "cvDistTransform" ); 712 713 __BEGIN__; 714 715 float _mask[5] = {0}; 716 int _imask[3]; 717 CvMat srcstub, *src = (CvMat*)srcarr; 718 CvMat dststub, *dst = (CvMat*)dstarr; 719 CvMat lstub, *labels = (CvMat*)labelsarr; 720 CvSize size; 721 CvIPPDistTransFunc ipp_func = 0; 722 CvIPPDistTransFunc2 ipp_inp_func = 0; 723 724 CV_CALL( src = cvGetMat( src, &srcstub )); 725 CV_CALL( dst = cvGetMat( dst, &dststub )); 726 727 if( !CV_IS_MASK_ARR( src ) || (CV_MAT_TYPE( dst->type ) != CV_32FC1 && 728 (CV_MAT_TYPE(dst->type) != CV_8UC1 || distType != CV_DIST_L1 || labels)) ) 729 CV_ERROR( CV_StsUnsupportedFormat, 730 "source image must be 8uC1 and the distance map must be 32fC1 " 731 "(or 8uC1 in case of simple L1 distance transform)" ); 732 733 if( !CV_ARE_SIZES_EQ( src, dst )) 734 CV_ERROR( CV_StsUnmatchedSizes, "the source and the destination images must be of the same size" ); 735 736 if( maskSize != CV_DIST_MASK_3 && maskSize != CV_DIST_MASK_5 && maskSize != CV_DIST_MASK_PRECISE ) 737 CV_ERROR( CV_StsBadSize, "Mask size should be 3 or 5 or 0 (presize)" ); 738 739 if( distType == CV_DIST_C || distType == CV_DIST_L1 ) 740 maskSize = !labels ? CV_DIST_MASK_3 : CV_DIST_MASK_5; 741 else if( distType == CV_DIST_L2 && labels ) 742 maskSize = CV_DIST_MASK_5; 743 744 if( maskSize == CV_DIST_MASK_PRECISE ) 745 { 746 CV_CALL( icvTrueDistTrans( src, dst )); 747 EXIT; 748 } 749 750 if( labels ) 751 { 752 CV_CALL( labels = cvGetMat( labels, &lstub )); 753 if( CV_MAT_TYPE( labels->type ) != CV_32SC1 ) 754 CV_ERROR( CV_StsUnsupportedFormat, "the output array of labels must be 32sC1" ); 755 756 if( !CV_ARE_SIZES_EQ( labels, dst )) 757 CV_ERROR( CV_StsUnmatchedSizes, "the array of labels has a different size" ); 758 759 if( maskSize == CV_DIST_MASK_3 ) 760 CV_ERROR( CV_StsNotImplemented, 761 "3x3 mask can not be used for \"labeled\" distance transform. Use 5x5 mask" ); 762 } 763 764 if( distType == CV_DIST_C || distType == CV_DIST_L1 || distType == CV_DIST_L2 ) 765 { 766 icvGetDistanceTransformMask( (distType == CV_DIST_C ? 0 : 767 distType == CV_DIST_L1 ? 1 : 2) + maskSize*10, _mask ); 768 } 769 else if( distType == CV_DIST_USER ) 770 { 771 if( !mask ) 772 CV_ERROR( CV_StsNullPtr, "" ); 773 774 memcpy( _mask, mask, (maskSize/2 + 1)*sizeof(float)); 775 } 776 777 if( !labels ) 778 { 779 if( CV_MAT_TYPE(dst->type) == CV_32FC1 ) 780 ipp_func = (CvIPPDistTransFunc)(maskSize == CV_DIST_MASK_3 ? 781 icvDistanceTransform_3x3_8u32f_C1R_p : icvDistanceTransform_5x5_8u32f_C1R_p); 782 else if( src->data.ptr != dst->data.ptr ) 783 ipp_func = (CvIPPDistTransFunc)icvDistanceTransform_3x3_8u_C1R_p; 784 else 785 ipp_inp_func = icvDistanceTransform_3x3_8u_C1IR_p; 786 } 787 788 size = cvGetMatSize(src); 789 790 if( (ipp_func || ipp_inp_func) && src->cols >= 4 && src->rows >= 2 ) 791 { 792 _imask[0] = cvRound(_mask[0]); 793 _imask[1] = cvRound(_mask[1]); 794 _imask[2] = cvRound(_mask[2]); 795 796 if( ipp_func ) 797 { 798 IPPI_CALL( ipp_func( src->data.ptr, src->step, 799 dst->data.fl, dst->step, size, 800 CV_MAT_TYPE(dst->type) == CV_8UC1 ? 801 (void*)_imask : (void*)_mask )); 802 } 803 else 804 { 805 IPPI_CALL( ipp_inp_func( src->data.ptr, src->step, size, _imask )); 806 } 807 } 808 else if( CV_MAT_TYPE(dst->type) == CV_8UC1 ) 809 { 810 CV_CALL( icvDistanceATS_L1_8u( src, dst )); 811 } 812 else 813 { 814 int border = maskSize == CV_DIST_MASK_3 ? 1 : 2; 815 CV_CALL( temp = cvCreateMat( size.height + border*2, size.width + border*2, CV_32SC1 )); 816 817 if( !labels ) 818 { 819 CvDistTransFunc func = maskSize == CV_DIST_MASK_3 ? 820 icvDistanceTransform_3x3_C1R : 821 icvDistanceTransform_5x5_C1R; 822 823 func( src->data.ptr, src->step, temp->data.i, temp->step, 824 dst->data.fl, dst->step, size, _mask ); 825 } 826 else 827 { 828 CvSeq *contours = 0; 829 CvPoint top_left = {0,0}, bottom_right = {size.width-1,size.height-1}; 830 int label; 831 832 CV_CALL( st = cvCreateMemStorage() ); 833 CV_CALL( src_copy = cvCreateMat( size.height, size.width, src->type )); 834 cvCmpS( src, 0, src_copy, CV_CMP_EQ ); 835 cvFindContours( src_copy, st, &contours, sizeof(CvContour), 836 CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE ); 837 cvZero( labels ); 838 for( label = 1; contours != 0; contours = contours->h_next, label++ ) 839 { 840 CvScalar area_color = cvScalarAll(label); 841 cvDrawContours( labels, contours, area_color, area_color, -255, -1, 8 ); 842 } 843 844 cvCopy( src, src_copy ); 845 cvRectangle( src_copy, top_left, bottom_right, cvScalarAll(255), 1, 8 ); 846 847 icvDistanceTransformEx_5x5_C1R( src_copy->data.ptr, src_copy->step, temp->data.i, temp->step, 848 dst->data.fl, dst->step, labels->data.i, labels->step, size, _mask ); 849 } 850 } 851 852 __END__; 853 854 cvReleaseMat( &temp ); 855 cvReleaseMat( &src_copy ); 856 cvReleaseMemStorage( &st ); 857} 858 859/* End of file. */ 860