vcs.maemo.org Git - opencv/blob - src/cv/cvcanny.cpp

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