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
44 icvCannyGetSize_t icvCannyGetSize_p = 0;
45 icvCanny_16s8u_C1R_t icvCanny_16s8u_C1R_p = 0;
46
47 CV_IMPL void
cvCanny(const void * srcarr,void * dstarr,double low_thresh,double high_thresh,int aperture_size)48 cvCanny( 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