1/*M/////////////////////////////////////////////////////////////////////////////////////// 2// 3// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4// 5// By downloading, copying, installing or using the software you agree to this license. 6// If you do not agree to this license, do not download, install, 7// copy or use the software. 8// 9// 10// Intel License Agreement 11// For Open Source Computer Vision Library 12// 13// Copyright (C) 2000, Intel Corporation, all rights reserved. 14// Third party copyrights are property of their respective owners. 15// 16// Redistribution and use in source and binary forms, with or without modification, 17// are permitted provided that the following conditions are met: 18// 19// * Redistribution's of source code must retain the above copyright notice, 20// this list of conditions and the following disclaimer. 21// 22// * Redistribution's in binary form must reproduce the above copyright notice, 23// this list of conditions and the following disclaimer in the documentation 24// and/or other materials provided with the distribution. 25// 26// * The name of Intel Corporation may not be used to endorse or promote products 27// derived from this software without specific prior written permission. 28// 29// This software is provided by the copyright holders and contributors "as is" and 30// any express or implied warranties, including, but not limited to, the implied 31// warranties of merchantability and fitness for a particular purpose are disclaimed. 32// In no event shall the Intel Corporation or contributors be liable for any direct, 33// indirect, incidental, special, exemplary, or consequential damages 34// (including, but not limited to, procurement of substitute goods or services; 35// loss of use, data, or profits; or business interruption) however caused 36// and on any theory of liability, whether in contract, strict liability, 37// or tort (including negligence or otherwise) arising in any way out of 38// the use of this software, even if advised of the possibility of such damage. 39// 40//M*/ 41 42#include "_cv.h" 43 44icvCannyGetSize_t icvCannyGetSize_p = 0; 45icvCanny_16s8u_C1R_t icvCanny_16s8u_C1R_p = 0; 46 47CV_IMPL void 48cvCanny( const void* srcarr, void* dstarr, 49 double low_thresh, double high_thresh, int aperture_size ) 50{ 51 CvMat *dx = 0, *dy = 0; 52 void *buffer = 0; 53 uchar **stack_top, **stack_bottom = 0; 54 55 CV_FUNCNAME( "cvCanny" ); 56 57 __BEGIN__; 58 59 CvMat srcstub, *src = (CvMat*)srcarr; 60 CvMat dststub, *dst = (CvMat*)dstarr; 61 CvSize size; 62 int flags = aperture_size; 63 int low, high; 64 int* mag_buf[3]; 65 uchar* map; 66 int mapstep, maxsize; 67 int i, j; 68 CvMat mag_row; 69 70 CV_CALL( src = cvGetMat( src, &srcstub )); 71 CV_CALL( dst = cvGetMat( dst, &dststub )); 72 73 if( CV_MAT_TYPE( src->type ) != CV_8UC1 || 74 CV_MAT_TYPE( dst->type ) != CV_8UC1 ) 75 CV_ERROR( CV_StsUnsupportedFormat, "" ); 76 77 if( !CV_ARE_SIZES_EQ( src, dst )) 78 CV_ERROR( CV_StsUnmatchedSizes, "" ); 79 80 if( low_thresh > high_thresh ) 81 { 82 double t; 83 CV_SWAP( low_thresh, high_thresh, t ); 84 } 85 86 aperture_size &= INT_MAX; 87 if( (aperture_size & 1) == 0 || aperture_size < 3 || aperture_size > 7 ) 88 CV_ERROR( CV_StsBadFlag, "" ); 89 90 size = cvGetMatSize( src ); 91 92 dx = cvCreateMat( size.height, size.width, CV_16SC1 ); 93 dy = cvCreateMat( size.height, size.width, CV_16SC1 ); 94 cvSobel( src, dx, 1, 0, aperture_size ); 95 cvSobel( src, dy, 0, 1, aperture_size ); 96 97 if( icvCannyGetSize_p && icvCanny_16s8u_C1R_p && !(flags & CV_CANNY_L2_GRADIENT) ) 98 { 99 int buf_size= 0; 100 IPPI_CALL( icvCannyGetSize_p( size, &buf_size )); 101 CV_CALL( buffer = cvAlloc( buf_size )); 102 IPPI_CALL( icvCanny_16s8u_C1R_p( (short*)dx->data.ptr, dx->step, 103 (short*)dy->data.ptr, dy->step, 104 dst->data.ptr, dst->step, 105 size, (float)low_thresh, 106 (float)high_thresh, buffer )); 107 EXIT; 108 } 109 110 if( flags & CV_CANNY_L2_GRADIENT ) 111 { 112 Cv32suf ul, uh; 113 ul.f = (float)low_thresh; 114 uh.f = (float)high_thresh; 115 116 low = ul.i; 117 high = uh.i; 118 } 119 else 120 { 121 low = cvFloor( low_thresh ); 122 high = cvFloor( high_thresh ); 123 } 124 125 CV_CALL( buffer = cvAlloc( (size.width+2)*(size.height+2) + 126 (size.width+2)*3*sizeof(int)) ); 127 128 mag_buf[0] = (int*)buffer; 129 mag_buf[1] = mag_buf[0] + size.width + 2; 130 mag_buf[2] = mag_buf[1] + size.width + 2; 131 map = (uchar*)(mag_buf[2] + size.width + 2); 132 mapstep = size.width + 2; 133 134 maxsize = MAX( 1 << 10, size.width*size.height/10 ); 135 CV_CALL( stack_top = stack_bottom = (uchar**)cvAlloc( maxsize*sizeof(stack_top[0]) )); 136 137 memset( mag_buf[0], 0, (size.width+2)*sizeof(int) ); 138 memset( map, 1, mapstep ); 139 memset( map + mapstep*(size.height + 1), 1, mapstep ); 140 141 /* sector numbers 142 (Top-Left Origin) 143 144 1 2 3 145 * * * 146 * * * 147 0*******0 148 * * * 149 * * * 150 3 2 1 151 */ 152 153 #define CANNY_PUSH(d) *(d) = (uchar)2, *stack_top++ = (d) 154 #define CANNY_POP(d) (d) = *--stack_top 155 156 mag_row = cvMat( 1, size.width, CV_32F ); 157 158 // calculate magnitude and angle of gradient, perform non-maxima supression. 159 // fill the map with one of the following values: 160 // 0 - the pixel might belong to an edge 161 // 1 - the pixel can not belong to an edge 162 // 2 - the pixel does belong to an edge 163 for( i = 0; i <= size.height; i++ ) 164 { 165 int* _mag = mag_buf[(i > 0) + 1] + 1; 166 float* _magf = (float*)_mag; 167 const short* _dx = (short*)(dx->data.ptr + dx->step*i); 168 const short* _dy = (short*)(dy->data.ptr + dy->step*i); 169 uchar* _map; 170 int x, y; 171 int magstep1, magstep2; 172 int prev_flag = 0; 173 174 if( i < size.height ) 175 { 176 _mag[-1] = _mag[size.width] = 0; 177 178 if( !(flags & CV_CANNY_L2_GRADIENT) ) 179 for( j = 0; j < size.width; j++ ) 180 _mag[j] = abs(_dx[j]) + abs(_dy[j]); 181 else if( icvFilterSobelVert_8u16s_C1R_p != 0 ) // check for IPP 182 { 183 // use vectorized sqrt 184 mag_row.data.fl = _magf; 185 for( j = 0; j < size.width; j++ ) 186 { 187 x = _dx[j]; y = _dy[j]; 188 _magf[j] = (float)((double)x*x + (double)y*y); 189 } 190 cvPow( &mag_row, &mag_row, 0.5 ); 191 } 192 else 193 { 194 for( j = 0; j < size.width; j++ ) 195 { 196 x = _dx[j]; y = _dy[j]; 197 _magf[j] = (float)sqrt((double)x*x + (double)y*y); 198 } 199 } 200 } 201 else 202 memset( _mag-1, 0, (size.width + 2)*sizeof(int) ); 203 204 // at the very beginning we do not have a complete ring 205 // buffer of 3 magnitude rows for non-maxima suppression 206 if( i == 0 ) 207 continue; 208 209 _map = map + mapstep*i + 1; 210 _map[-1] = _map[size.width] = 1; 211 212 _mag = mag_buf[1] + 1; // take the central row 213 _dx = (short*)(dx->data.ptr + dx->step*(i-1)); 214 _dy = (short*)(dy->data.ptr + dy->step*(i-1)); 215 216 magstep1 = (int)(mag_buf[2] - mag_buf[1]); 217 magstep2 = (int)(mag_buf[0] - mag_buf[1]); 218 219 if( (stack_top - stack_bottom) + size.width > maxsize ) 220 { 221 uchar** new_stack_bottom; 222 maxsize = MAX( maxsize * 3/2, maxsize + size.width ); 223 CV_CALL( new_stack_bottom = (uchar**)cvAlloc( maxsize * sizeof(stack_top[0])) ); 224 memcpy( new_stack_bottom, stack_bottom, (stack_top - stack_bottom)*sizeof(stack_top[0]) ); 225 stack_top = new_stack_bottom + (stack_top - stack_bottom); 226 cvFree( &stack_bottom ); 227 stack_bottom = new_stack_bottom; 228 } 229 230 for( j = 0; j < size.width; j++ ) 231 { 232 #define CANNY_SHIFT 15 233 #define TG22 (int)(0.4142135623730950488016887242097*(1<<CANNY_SHIFT) + 0.5) 234 235 x = _dx[j]; 236 y = _dy[j]; 237 int s = x ^ y; 238 int m = _mag[j]; 239 240 x = abs(x); 241 y = abs(y); 242 if( m > low ) 243 { 244 int tg22x = x * TG22; 245 int tg67x = tg22x + ((x + x) << CANNY_SHIFT); 246 247 y <<= CANNY_SHIFT; 248 249 if( y < tg22x ) 250 { 251 if( m > _mag[j-1] && m >= _mag[j+1] ) 252 { 253 if( m > high && !prev_flag && _map[j-mapstep] != 2 ) 254 { 255 CANNY_PUSH( _map + j ); 256 prev_flag = 1; 257 } 258 else 259 _map[j] = (uchar)0; 260 continue; 261 } 262 } 263 else if( y > tg67x ) 264 { 265 if( m > _mag[j+magstep2] && m >= _mag[j+magstep1] ) 266 { 267 if( m > high && !prev_flag && _map[j-mapstep] != 2 ) 268 { 269 CANNY_PUSH( _map + j ); 270 prev_flag = 1; 271 } 272 else 273 _map[j] = (uchar)0; 274 continue; 275 } 276 } 277 else 278 { 279 s = s < 0 ? -1 : 1; 280 if( m > _mag[j+magstep2-s] && m > _mag[j+magstep1+s] ) 281 { 282 if( m > high && !prev_flag && _map[j-mapstep] != 2 ) 283 { 284 CANNY_PUSH( _map + j ); 285 prev_flag = 1; 286 } 287 else 288 _map[j] = (uchar)0; 289 continue; 290 } 291 } 292 } 293 prev_flag = 0; 294 _map[j] = (uchar)1; 295 } 296 297 // scroll the ring buffer 298 _mag = mag_buf[0]; 299 mag_buf[0] = mag_buf[1]; 300 mag_buf[1] = mag_buf[2]; 301 mag_buf[2] = _mag; 302 } 303 304 // now track the edges (hysteresis thresholding) 305 while( stack_top > stack_bottom ) 306 { 307 uchar* m; 308 if( (stack_top - stack_bottom) + 8 > maxsize ) 309 { 310 uchar** new_stack_bottom; 311 maxsize = MAX( maxsize * 3/2, maxsize + 8 ); 312 CV_CALL( new_stack_bottom = (uchar**)cvAlloc( maxsize * sizeof(stack_top[0])) ); 313 memcpy( new_stack_bottom, stack_bottom, (stack_top - stack_bottom)*sizeof(stack_top[0]) ); 314 stack_top = new_stack_bottom + (stack_top - stack_bottom); 315 cvFree( &stack_bottom ); 316 stack_bottom = new_stack_bottom; 317 } 318 319 CANNY_POP(m); 320 321 if( !m[-1] ) 322 CANNY_PUSH( m - 1 ); 323 if( !m[1] ) 324 CANNY_PUSH( m + 1 ); 325 if( !m[-mapstep-1] ) 326 CANNY_PUSH( m - mapstep - 1 ); 327 if( !m[-mapstep] ) 328 CANNY_PUSH( m - mapstep ); 329 if( !m[-mapstep+1] ) 330 CANNY_PUSH( m - mapstep + 1 ); 331 if( !m[mapstep-1] ) 332 CANNY_PUSH( m + mapstep - 1 ); 333 if( !m[mapstep] ) 334 CANNY_PUSH( m + mapstep ); 335 if( !m[mapstep+1] ) 336 CANNY_PUSH( m + mapstep + 1 ); 337 } 338 339 // the final pass, form the final image 340 for( i = 0; i < size.height; i++ ) 341 { 342 const uchar* _map = map + mapstep*(i+1) + 1; 343 uchar* _dst = dst->data.ptr + dst->step*i; 344 345 for( j = 0; j < size.width; j++ ) 346 _dst[j] = (uchar)-(_map[j] >> 1); 347 } 348 349 __END__; 350 351 cvReleaseMat( &dx ); 352 cvReleaseMat( &dy ); 353 cvFree( &buffer ); 354 cvFree( &stack_bottom ); 355} 356 357/* End of file. */ 358