Home | History | Annotate | Download | only in src
      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. */
    358