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

   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
  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. */