文章目录
  1. 1. Introduction
  2. 2. Canny边缘检测子算法
    1. 2.1. 图像平滑
    2. 2.2. 滞后阈值化处理
  3. 3. OpenCV Canny实现代码
  4. 4. 扩展
  5. 5. 参考文献

Canny边缘检测算法是非常通用经典的找边缘算法,本文详细介绍了Canny算法的原理,并给出OpenCV Canny算法的实现。

Introduction

Canny算法是John F.Canny在1986年提出的边缘检测算法[1],但它仍然是目前十分流行的边缘检测算子。

JFC在论文中提到边缘最优边缘检测的三个标准:
+检测标准:不丢失重要的边缘,不应有虚假的边缘。
+定位标准:实际边缘与检测到的边缘位置之间的偏差最小。
+单响应标准:将多个响应降低为单个边缘响应。这一点被第一个标准部分地覆盖了。

第三个标准简单点说就是检测出来的边缘的边缘宽度应该为1。

Canny边缘检测子算法

Canny算子的整个过程包括:
1.平滑处理:将图像与尺度为σ的高斯函数做卷积。
2.边缘强度计算:计算图像的边缘幅度及方向。
3.非极大值抑制:只有局部极大值标记为边缘。
4.滞后阈值化处理。
5.对于递增的σ,重复步骤1~4。
6.用特征综合方法,搜集多尺度的最终边缘信息。

Canny算子的完整实现很少见,一般都省略了特征综合方法,即只进行步骤1~4。下面我们也只对1~4步骤进行说明:

图像平滑

为了减少图像的噪点,通常都会使用高斯滤波器来平滑图像。σ=1.4对应的高斯滤波器卷积核为:






注意高斯滤波器在平滑图像噪点的时候也会模糊边缘信息。

### 边缘强度计算
边缘强度的计算包括边缘幅度以及边缘方向的计算。一般选择Sobel算子或者Roberts算子得到x,y方向的梯度强度,利用两个方向的梯度dx, dy,然后利用如下公式计算:
+边缘强度:$g = dx^2 + dy^2$
+边缘方向:$\theta = atan2(dy, dx)$
一般在算法实现中,为了效率边缘强度的计算会使用$|dx| + |dy|$表达。

下面为Sobel, Roberts在x,y方向的卷积核:

  Sobel x           Sobel y
–1 0 1 –1 –2 –1
–2 0 2 0 0 0
–1 0 1 –1 2 1

Roberts x Roberts y
-1 0 0 -1
0 1 1 0


Roberts算法比Sobel略快点,能应对更高频率的边缘,但是对于噪声更加敏感。另外注意使用Roberts算子计算出来的角度要减pi/4。

### 非极大值抑制
对于边缘的定义一般情况下有两种:一种是二阶导数过零点,另一种是一阶导数的极大极小值。这两种定义本质上是一致的。但是在实现上通常使用后一种。所谓的非极大值抑制按照字面理解就是不是极大值的不要。

之所以要进行非极大值抑制主要是为了让边缘单一响应。具体来看个例子,假设使用上面Sobel算子计算后的图像一阶导数中有一行是这样的:

0, 1, 5, 38, 50, -15, -23, -20, 0


假设设置边缘的阈值为20,那么如果不进行非极大值抑制抑制,38, 50, -15, -20这些点都会被当做边缘点处理,由于图像时灰度图,边缘的地方是平滑过渡的,对于上面这种情况实际边缘就只有两个,即在50, -23的为位置。因此再考虑一个点是不是边缘的时候,需要和它相邻的点进行比较,用代码来看就是

currentEdge > preEdge && currentEdge >= nextEdge

注意必须有一个是>, 另一个是>=。

上面考虑的是一维的情况,那么对于二维的情况就需要考虑边缘的方向。对超过阈值的边缘进行非极大值抑制的时候,要在边缘的方向上进行。一个点有8个相邻的点,我们要做的就是在8个相邻点中选出2个作为要比较的点。按照边缘的方向进行如下分割:





滞后阈值化处理

按照2.1~2.3已经可以做好一般的边缘分割了,但是会碰到一个问题。边缘的提取好坏很大程度上依赖阈值的选取。如果阈值选取过大,则会少掉有效边缘。如果阈值设置过小,则会有许多噪点。

对于这个问题就是滞后阈值所要处理的,也是Canny算法的关键步骤。滞后阈值分割使用两个阈值,high threshold和low threshold。当边缘强度大于high threshold的立即设置为边缘点,低于low threshold立即剔除,在中间的作为潜在边缘点,按下列原则处理:只有这些点能按照某一路径与已存在边缘点相连时,它们才被接受为边缘点。组成组成这一路径的点边缘幅度都要大于low threshold。这个过程可以这么理解,首先选定边缘幅度大于high threshold的所有边缘点,然后在边缘幅度大于low threshold的情况下尽可能延长。

OpenCV Canny实现代码

通过以上的介绍再来看OpenCV Canny的源码的话就会简单很多。可以看到OpenCV的代码还是写的非常好的,以下代码中包含对应的注释,不能再详细了:)

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
/**
* Parameters:
* image – single-channel 8-bit input image.
* edges – output edge map; it has the same size and type as image .
* threshold1 – first threshold for the hysteresis procedure.
* threshold2 – second threshold for the hysteresis procedure.
* apertureSize – aperture size for the Sobel() operator.
* L2gradient – a flag, indicating whether a more accurate L_2 norm = sqrt{(dI/dx)^2 + (dI/dy)^2} should be used to calculate the
* image gradient magnitude ( L2gradient=true ), or whether the default L_1 norm =|dI/dx|+|dI/dy| is enough ( L2gradient=false ).
*/
void cv::Canny( InputArray _src, OutputArray _dst,
double low_thresh, double high_thresh,
int aperture_size, bool L2gradient )
{
Mat src = _src.getMat();
CV_Assert( src.depth() == CV_8U );
_dst.create(src.size(), CV_8U);
Mat dst = _dst.getMat();
if (!L2gradient && (aperture_size & CV_CANNY_L2_GRADIENT) == CV_CANNY_L2_GRADIENT)
{
//backward compatibility
aperture_size &= ~CV_CANNY_L2_GRADIENT;
L2gradient = true;
}
if ((aperture_size & 1) == 0 || (aperture_size != -1 && (aperture_size < 3 || aperture_size > 7)))
CV_Error(CV_StsBadFlag, "");
if (low_thresh > high_thresh)
std::swap(low_thresh, high_thresh);
const int cn = src.channels();
Mat dx(src.rows, src.cols, CV_16SC(cn));
Mat dy(src.rows, src.cols, CV_16SC(cn));
// 使用sobel算子获取x,y方向的边缘梯度
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);
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);
// buffer空间分为两个部分,一个部分用来存放当前处理的3行边缘强度(int型)。另外用来存储整幅图像的边缘信息(uchar),
// 0表示可能是边缘,1表示不可能是边缘,2表示一定是边缘
// src.cols+2, src.rows+2,是为了再操作时内存访问不会越界
ptrdiff_t mapstep = src.cols + 2;
AutoBuffer<uchar> buffer((src.cols+2)*(src.rows+2) + cn * mapstep * 3 * sizeof(int));
int* mag_buf[3]; // 当前要处理的3行边缘幅度buf
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)); // 初始化第0行的buf
uchar* map = (uchar*)(mag_buf[2] + mapstep*cn); // 整个图像的边缘信息,对多余出来的最外面一圈需要设置为1
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]; // 栈底和栈顶位置为0
uchar **stack_bottom = &stack[0];
/* sector numbers
(Top-Left Origin)
1 2 3
* * *
* * *
0*******0
* * *
* * *
3 2 1
*/
#define CANNY_PUSH(d) *(d) = uchar(2), *stack_top++ = (d) // 栈push操作,先填充值再将top++
#define CANNY_POP(d) (d) = *--stack_top // 栈pop操作,先将top--,再取出值
// calculate magnitude and angle of gradient, perform non-maxima supression.
// 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++)
{
int* _norm = mag_buf[(i > 0) + 1] + 1;// 存储边缘幅度
if (i < src.rows)
{
short* _dx = dx.ptr<short>(i);
short* _dy = dy.ptr<short>(i);
if (!L2gradient)
{
for (int j = 0; j < src.cols*cn; j++)
_norm[j] = std::abs(int(_dx[j])) + std::abs(int(_dy[j]));
}
else
{
for (int j = 0; j < src.cols*cn; j++)
_norm[j] = int(_dx[j])*_dx[j] + int(_dy[j])*_dy[j];
}
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));
// at the very beginning we do not have a complete ring
// buffer of 3 magnitude rows for non-maxima suppression
if (i == 0)
continue;
uchar* _map = map + mapstep*i + 1;
_map[-1] = _map[src.cols] = 1;
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];
const short* _x = dx.ptr<short>(i-1);
const short* _y = dy.ptr<short>(i-1);
if ((stack_top - stack_bottom) + src.cols > maxsize) // 确保stack不会溢出
{
int sz = (int)(stack_top - stack_bottom);
maxsize = maxsize * 3/2;
stack.resize(maxsize);
stack_bottom = &stack[0];
stack_top = stack_bottom + sz;
}
// 进行非极大值抑制
int prev_flag = 0;
for (int j = 0; j < src.cols; j++)
{
#define CANNY_SHIFT 15 //放大边缘强度,使用Int型比较边缘
// tan(22.5) * 2^15 + 0.5, tan(22.5) = sqrt(2) - 1
const int TG22 = (int)(0.4142135623730950488016887242097*(1<<CANNY_SHIFT) + 0.5);
int m = _mag[j];
// 边缘强度 > 低阈值
if (m > low)
{
int xs = _x[j];
int ys = _y[j];
int x = std::abs(xs);
int y = std::abs(ys) << CANNY_SHIFT;
int tg22x = x * TG22;
if (y < tg22x)
{
if (m > _mag[j-1] && m >= _mag[j+1]) goto __ocv_canny_push;
}
else
{
// tan(67.5) * x, tan(66.5) = sqrt(2) + 1
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)
{
uchar* m;
// 保证8个相邻点全部都push到stack,stack也不会溢出
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);
}
// 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);// uchar(-1) = 255,最后得到的是一个二值图0-255
}
}

扩展

更多关于Canny算子的延伸阅读请参考维基百科

参考文献

[1] John Canny. A computational approach to edge detection. Pattern Analysis and Machine Intelligence, IEEE Transactions on, PAMI-8(6):679–698, Nov. 1986.

文章目录
  1. 1. Introduction
  2. 2. Canny边缘检测子算法
    1. 2.1. 图像平滑
    2. 2.2. 滞后阈值化处理
  3. 3. OpenCV Canny实现代码
  4. 4. 扩展
  5. 5. 参考文献