canny.cpp 11.3 KB
Newer Older
wester committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

#include "precomp.hpp"

wester committed
44 45
/*
#if defined (HAVE_IPP) && (IPP_VERSION_MAJOR >= 7)
a  
Kai Westerkamp committed
46 47
#define USE_IPP_CANNY 1
#else
wester committed
48
#undef USE_IPP_CANNY
wester committed
49
#endif
wester committed
50 51
*/
#ifdef USE_IPP_CANNY
wester committed
52 53
namespace cv
{
a  
Kai Westerkamp committed
54
static bool ippCanny(const Mat& _src, Mat& _dst, float low,  float high)
wester committed
55
{
a  
Kai Westerkamp committed
56 57
    int size = 0, size1 = 0;
    IppiSize roi = { _src.cols, _src.rows };
wester committed
58

wester committed
59 60
    ippiFilterSobelNegVertGetBufferSize_8u16s_C1R(roi, ippMskSize3x3, &size);
    ippiFilterSobelHorizGetBufferSize_8u16s_C1R(roi, ippMskSize3x3, &size1);
a  
Kai Westerkamp committed
61
    size = std::max(size, size1);
wester committed
62
    ippiCannyGetSize(roi, &size1);
a  
Kai Westerkamp committed
63
    size = std::max(size, size1);
wester committed
64

a  
Kai Westerkamp committed
65 66
    AutoBuffer<uchar> buf(size + 64);
    uchar* buffer = alignPtr((uchar*)buf, 32);
wester committed
67

a  
Kai Westerkamp committed
68
    Mat _dx(_src.rows, _src.cols, CV_16S);
wester committed
69
    if( ippiFilterSobelNegVertBorder_8u16s_C1R(_src.data, (int)_src.step,
a  
Kai Westerkamp committed
70 71 72
                    _dx.ptr<short>(), (int)_dx.step, roi,
                    ippMskSize3x3, ippBorderRepl, 0, buffer) < 0 )
        return false;
wester committed
73

a  
Kai Westerkamp committed
74
    Mat _dy(_src.rows, _src.cols, CV_16S);
wester committed
75
    if( ippiFilterSobelHorizBorder_8u16s_C1R(_src.data, (int)_src.step,
a  
Kai Westerkamp committed
76 77 78
                    _dy.ptr<short>(), (int)_dy.step, roi,
                    ippMskSize3x3, ippBorderRepl, 0, buffer) < 0 )
        return false;
wester committed
79

a  
Kai Westerkamp committed
80
    if( ippiCanny_16s8u_C1R(_dx.ptr<short>(), (int)_dx.step,
wester committed
81 82
                            _dy.ptr<short>(), (int)_dy.step,
                            _dst.data, (int)_dst.step, roi, low, high, buffer) < 0 )
a  
Kai Westerkamp committed
83
        return false;
wester committed
84 85 86 87 88
    return true;
}
}
#endif

a  
Kai Westerkamp committed
89
void cv::Canny( InputArray _src, OutputArray _dst,
wester committed
90 91 92
                double low_thresh, double high_thresh,
                int aperture_size, bool L2gradient )
{
wester committed
93 94
    Mat src = _src.getMat();
    CV_Assert( src.depth() == CV_8U );
wester committed
95

wester committed
96 97
    _dst.create(src.size(), CV_8U);
    Mat dst = _dst.getMat();
wester committed
98 99 100

    if (!L2gradient && (aperture_size & CV_CANNY_L2_GRADIENT) == CV_CANNY_L2_GRADIENT)
    {
wester committed
101
        //backward compatibility
wester committed
102 103 104 105 106
        aperture_size &= ~CV_CANNY_L2_GRADIENT;
        L2gradient = true;
    }

    if ((aperture_size & 1) == 0 || (aperture_size != -1 && (aperture_size < 3 || aperture_size > 7)))
wester committed
107
        CV_Error(CV_StsBadFlag, "");
wester committed
108 109 110 111 112

    if (low_thresh > high_thresh)
        std::swap(low_thresh, high_thresh);

#ifdef HAVE_TEGRA_OPTIMIZATION
wester committed
113
    if (tegra::canny(src, dst, low_thresh, high_thresh, aperture_size, L2gradient))
wester committed
114 115 116
        return;
#endif

wester committed
117 118 119 120 121
#ifdef USE_IPP_CANNY
    if( aperture_size == 3 && !L2gradient &&
        ippCanny(src, dst, (float)low_thresh, (float)high_thresh) )
        return;
#endif
a  
Kai Westerkamp committed
122

wester committed
123
    const int cn = src.channels();
a  
Kai Westerkamp committed
124 125 126
    Mat dx(src.rows, src.cols, CV_16SC(cn));
    Mat dy(src.rows, src.cols, CV_16SC(cn));

wester committed
127 128
    Sobel(src, dx, CV_16S, 1, 0, aperture_size, 1, 0, cv::BORDER_REPLICATE);
    Sobel(src, dy, CV_16S, 0, 1, aperture_size, 1, 0, cv::BORDER_REPLICATE);
wester committed
129 130 131 132 133 134 135 136 137 138 139 140

    if (L2gradient)
    {
        low_thresh = std::min(32767.0, low_thresh);
        high_thresh = std::min(32767.0, high_thresh);

        if (low_thresh > 0) low_thresh *= low_thresh;
        if (high_thresh > 0) high_thresh *= high_thresh;
    }
    int low = cvFloor(low_thresh);
    int high = cvFloor(high_thresh);

a  
Kai Westerkamp committed
141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
    ptrdiff_t mapstep = src.cols + 2;
    AutoBuffer<uchar> buffer((src.cols+2)*(src.rows+2) + cn * mapstep * 3 * sizeof(int));

    int* mag_buf[3];
    mag_buf[0] = (int*)(uchar*)buffer;
    mag_buf[1] = mag_buf[0] + mapstep*cn;
    mag_buf[2] = mag_buf[1] + mapstep*cn;
    memset(mag_buf[0], 0, /* cn* */mapstep*sizeof(int));

    uchar* map = (uchar*)(mag_buf[2] + mapstep*cn);
    memset(map, 1, mapstep);
    memset(map + mapstep*(src.rows + 1), 1, mapstep);

    int maxsize = std::max(1 << 10, src.cols * src.rows / 10);
    std::vector<uchar*> stack(maxsize);
    uchar **stack_top = &stack[0];
    uchar **stack_bottom = &stack[0];

    /* sector numbers
       (Top-Left Origin)

        1   2   3
         *  *  *
          * * *
        0*******0
          * * *
         *  *  *
        3   2   1
    */
wester committed
170

a  
Kai Westerkamp committed
171 172
    #define CANNY_PUSH(d)    *(d) = uchar(2), *stack_top++ = (d)
    #define CANNY_POP(d)     (d) = *--stack_top
wester committed
173

a  
Kai Westerkamp committed
174 175 176 177 178 179
    // calculate magnitude and angle of gradient, perform non-maxima suppression.
    // fill the map with one of the following values:
    //   0 - the pixel might belong to an edge
    //   1 - the pixel can not belong to an edge
    //   2 - the pixel does belong to an edge
    for (int i = 0; i <= src.rows; i++)
wester committed
180
    {
a  
Kai Westerkamp committed
181 182 183 184 185
        int* _norm = mag_buf[(i > 0) + 1] + 1;
        if (i < src.rows)
        {
            short* _dx = dx.ptr<short>(i);
            short* _dy = dy.ptr<short>(i);
wester committed
186

a  
Kai Westerkamp committed
187 188
            if (!L2gradient)
            {
wester committed
189
                for (int j = 0; j < src.cols*cn; j++)
a  
Kai Westerkamp committed
190 191 192 193
                    _norm[j] = std::abs(int(_dx[j])) + std::abs(int(_dy[j]));
            }
            else
            {
wester committed
194
                for (int j = 0; j < src.cols*cn; j++)
a  
Kai Westerkamp committed
195 196
                    _norm[j] = int(_dx[j])*_dx[j] + int(_dy[j])*_dy[j];
            }
wester committed
197

a  
Kai Westerkamp committed
198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
            if (cn > 1)
            {
                for(int j = 0, jn = 0; j < src.cols; ++j, jn += cn)
                {
                    int maxIdx = jn;
                    for(int k = 1; k < cn; ++k)
                        if(_norm[jn + k] > _norm[maxIdx]) maxIdx = jn + k;
                    _norm[j] = _norm[maxIdx];
                    _dx[j] = _dx[maxIdx];
                    _dy[j] = _dy[maxIdx];
                }
            }
            _norm[-1] = _norm[src.cols] = 0;
        }
        else
            memset(_norm-1, 0, /* cn* */mapstep*sizeof(int));
wester committed
214

a  
Kai Westerkamp committed
215 216 217 218
        // at the very beginning we do not have a complete ring
        // buffer of 3 magnitude rows for non-maxima suppression
        if (i == 0)
            continue;
wester committed
219

a  
Kai Westerkamp committed
220 221
        uchar* _map = map + mapstep*i + 1;
        _map[-1] = _map[src.cols] = 1;
wester committed
222

a  
Kai Westerkamp committed
223 224 225
        int* _mag = mag_buf[1] + 1; // take the central row
        ptrdiff_t magstep1 = mag_buf[2] - mag_buf[1];
        ptrdiff_t magstep2 = mag_buf[0] - mag_buf[1];
wester committed
226

a  
Kai Westerkamp committed
227 228
        const short* _x = dx.ptr<short>(i-1);
        const short* _y = dy.ptr<short>(i-1);
wester committed
229

a  
Kai Westerkamp committed
230 231 232
        if ((stack_top - stack_bottom) + src.cols > maxsize)
        {
            int sz = (int)(stack_top - stack_bottom);
wester committed
233
            maxsize = std::max(sz + src.cols, maxsize * 3/2);
a  
Kai Westerkamp committed
234 235 236 237
            stack.resize(maxsize);
            stack_bottom = &stack[0];
            stack_top = stack_bottom + sz;
        }
wester committed
238

a  
Kai Westerkamp committed
239 240 241 242 243
        int prev_flag = 0;
        for (int j = 0; j < src.cols; j++)
        {
            #define CANNY_SHIFT 15
            const int TG22 = (int)(0.4142135623730950488016887242097*(1<<CANNY_SHIFT) + 0.5);
wester committed
244

a  
Kai Westerkamp committed
245
            int m = _mag[j];
wester committed
246

a  
Kai Westerkamp committed
247 248 249 250 251 252
            if (m > low)
            {
                int xs = _x[j];
                int ys = _y[j];
                int x = std::abs(xs);
                int y = std::abs(ys) << CANNY_SHIFT;
wester committed
253

a  
Kai Westerkamp committed
254
                int tg22x = x * TG22;
wester committed
255

a  
Kai Westerkamp committed
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295
                if (y < tg22x)
                {
                    if (m > _mag[j-1] && m >= _mag[j+1]) goto __ocv_canny_push;
                }
                else
                {
                    int tg67x = tg22x + (x << (CANNY_SHIFT+1));
                    if (y > tg67x)
                    {
                        if (m > _mag[j+magstep2] && m >= _mag[j+magstep1]) goto __ocv_canny_push;
                    }
                    else
                    {
                        int s = (xs ^ ys) < 0 ? -1 : 1;
                        if (m > _mag[j+magstep2-s] && m > _mag[j+magstep1+s]) goto __ocv_canny_push;
                    }
                }
            }
            prev_flag = 0;
            _map[j] = uchar(1);
            continue;
__ocv_canny_push:
            if (!prev_flag && m > high && _map[j-mapstep] != 2)
            {
                CANNY_PUSH(_map + j);
                prev_flag = 1;
            }
            else
                _map[j] = 0;
        }

        // scroll the ring buffer
        _mag = mag_buf[0];
        mag_buf[0] = mag_buf[1];
        mag_buf[1] = mag_buf[2];
        mag_buf[2] = _mag;
    }

    // now track the edges (hysteresis thresholding)
    while (stack_top > stack_bottom)
wester committed
296
    {
a  
Kai Westerkamp committed
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
        uchar* m;
        if ((stack_top - stack_bottom) + 8 > maxsize)
        {
            int sz = (int)(stack_top - stack_bottom);
            maxsize = maxsize * 3/2;
            stack.resize(maxsize);
            stack_bottom = &stack[0];
            stack_top = stack_bottom + sz;
        }

        CANNY_POP(m);

        if (!m[-1])         CANNY_PUSH(m - 1);
        if (!m[1])          CANNY_PUSH(m + 1);
        if (!m[-mapstep-1]) CANNY_PUSH(m - mapstep - 1);
        if (!m[-mapstep])   CANNY_PUSH(m - mapstep);
        if (!m[-mapstep+1]) CANNY_PUSH(m - mapstep + 1);
        if (!m[mapstep-1])  CANNY_PUSH(m + mapstep - 1);
        if (!m[mapstep])    CANNY_PUSH(m + mapstep);
        if (!m[mapstep+1])  CANNY_PUSH(m + mapstep + 1);
wester committed
317 318
    }

a  
Kai Westerkamp committed
319 320 321 322 323 324 325 326 327
    // the final pass, form the final image
    const uchar* pmap = map + mapstep + 1;
    uchar* pdst = dst.ptr();
    for (int i = 0; i < src.rows; i++, pmap += mapstep, pdst += dst.step)
    {
        for (int j = 0; j < src.cols; j++)
            pdst[j] = (uchar)-(pmap[j] >> 1);
    }
}
wester committed
328 329 330 331 332 333 334 335 336 337 338 339

void cvCanny( const CvArr* image, CvArr* edges, double threshold1,
              double threshold2, int aperture_size )
{
    cv::Mat src = cv::cvarrToMat(image), dst = cv::cvarrToMat(edges);
    CV_Assert( src.size == dst.size && src.depth() == CV_8U && dst.type() == CV_8U );

    cv::Canny(src, dst, threshold1, threshold2, aperture_size & 255,
              (aperture_size & CV_CANNY_L2_GRADIENT) != 0);
}

/* End of file. */