用于Canny算子边缘检测的广度优先算法研究

肖瑞莹，杨 帆，董正宏

(1.装备学院 研究生管理大队，北京 101416；2.装备学院 信息装备系，北京 101416)

0 引 言

图像的边缘检测通过在噪声背景中识别目标物体边界点与边界线段，提取出图像的边缘轮廓。图像边缘广泛存在于目标物体基本单元之间以及目标物体与图像背景之间，图像边缘的检测是图像视觉领域从底层向顶层推理的重要基础，包含着图像重要信息与图像特征。边缘检测算法作为图像视觉领域的研究基础，在军事、医学、环境学等领域发挥着重要作用。

高效的边缘检测算法可以提高后续图像处理的正确率，基于此许多针对边缘检测的算法研究相继展开[1-4]。实际检测算法中常用到一阶与二阶导数算法。Canny算子[5]通过一阶梯度算法计算得到梯度变化极大值点，具有高信噪比的检测特点，但是检测结果具有较多断裂的线段，图像的边缘不能构成较为完整的轮廓。二阶梯度算法如Log算子[6]利用二阶导数过零点，进一步检测出图像边缘点。二阶算法可以检测出突变像素点作为边缘点，便于进行后续图像处理，但二阶导数算法易受噪声影响，在检测中容易损失部分图像信息[7]。

针对一阶导数Canny算子存在较多断裂点、图像边缘不完整的缺点，可以在提取图像边缘之后应用边缘连接方法将不完整的边缘进行处理，优化图像边缘，提高边缘检测正确率。目前对于已经提取得到的图像边缘进行边缘连接提出的优化算法不断涌现。如基于人类感知的边缘连接法[8]，将人工设定阈值改进为自适应求阈值，通过求得的自适应高低两个阈值分别得到两幅阈值图像，对高阈值图像的边缘点进行邻域搜索，寻找低阈值图像中是否存在与其相连的像素点，符合判别条件的点都存入最终将输出的图像数组中。另外，基于稳健拟合的直线边缘连接法[9]，使用卡尔曼滤波器对图像检测得到的边缘点进行搜索，找到部分遗漏的微小信息，再利用稳健法代替传统的最小二乘法，对图像边缘点进行拟合主要针对直线的边缘线段有着较好的连接效果。然而在实际应用中需要一种具有一般适用性的边缘连接算法，以提高图像连通性。

文中设计并实现了一个二维图像的边缘检测系统，在Canny算子的基础上实现了边缘的优化。采用基于广度优先算法[10]的边缘连接算法减少断裂点，从而提高边缘的连续性和图像的连通性，并定量分析图像边缘查全率和连通分量。

1 Canny算子实现图像检测

利用Canny算子检测图像[11]时，需要首先对图像进行灰度化处理。对初始彩色图像进行灰度化处理的方法是将每个像素点的RGB格式像素通过公式转化为灰度像素：

Gray=0.299R+0.587G+0.114B

(1)

式1考虑到人眼识别图像的特点，对RGB像素进行了加权平均。

其次对灰度图像进行高斯平滑滤波，即使用高斯滤波器对初始图像进行平滑滤波去噪。这里H(χ,y)为高斯平滑函数。

(2)

与待检测图像f(χ,y)做卷积可得到平滑图像G(χ,y)。

G(χ,y)=f(χ,y)*H(χ,y)

(3)

使用一阶偏导数计算梯度幅值和方向，得到x和y两个方向的偏导数矩阵：

(4)

梯度幅值和方向为：

ψ1(m,n)=f(m,n)*H1(m,n)

(5)

ψ2(m,n)=f(m,n)*H2(m,n)

(6)

(7)

(8)

最后对梯度幅值进行极大值抑制，排除非边缘点像素点。

经过上述处理，筛选所得像素点还需通过非极大值抑制排除非边缘的像素点。对当前像素点集合进行附近八邻域像素点比较，如果该点不是九个像素点中梯度幅值最大的点，则从边缘点集合中剔除。使用该方法遍历集合中所有点，即可实现非极大值点抑制。

八邻域点位置如图1所示。

32140567

图1 八邻域点示意图

为减少检测图像的断裂点，Canny算子本身采用了手动设定的双阈值检测与边缘连接。选取使用高低两个阈值，并利用两个阈值对图像进行阈值分割，可以得到两幅阈值分割图。以高阈值分割的图像噪音少，但边缘断点相对多，而以低阈值分割的图像包括了较多的边缘信息。由此可利用低阈值分割图像对高阈值分割图像进行补充，在高阈值分割图像的端点处通过八邻域搜索算法搜索周围是否存在高于低阈值的点，如果存在，则将两点相连，并对下一个点继续进行搜索，直到搜索结束，再对另一个高阈值图像中的端点进行新一轮的搜索，最终使得图像边缘连接成一个完整的轮廓。

使用Canny算子边缘检测算法，检测结果的图像对较弱边缘也可做出较好的响应，但检测图片中图像边缘仍存在较多断裂处。Canny算子对边缘进行连接的效果不理想，图像边缘不能构成较为完整的轮廓。

2 Canny算子的边缘优化

2.1 基于广度优先的边缘连接算法基本原理

文中采用基于广度优先的边缘连接算法进行优化图像连通性的设计与实现。该算法首先使用基于人类感知连接法中相同原理判断像素点是否为端点，之后采取广度优先的搜索算法将图像端点相连。对检测图像中的端点进行连接前，首先应判断哪些点是端点，这里采取的办法仍是对边缘点八邻域进行搜索，如果邻域中有一个点与之相连则该点是端点，否则其他情况均不是端点。

一个像素点的八邻域指图1所示的0至7八个点。要建立3×3的邻域拓扑图。

判断一个像素点的八邻域点，相连情况一共有四种：没有点与其相连则该像素点为孤立点，有一个点相连为端点，有两个点相连为边缘线中的一点，有四个点相连为两条边缘线交叉点。

在对每一个像素点进行判断后，将属于端点的像素点存入端点数组中。然后对端点数组中的像素点进行搜索，搜到同为端点的像素点时将两者相连完成闭合即可。当满足停止条件，即搜索长度大于最大阈值或搜索到另一个端点时，标记搜索路径完成闭合，随后再从中断处重新开始扫描。

该算法具体步骤如下：

(1)将每个轮廓像素的邻域Xi添加一个从0至7的整数标号，如图1所示。

每个轮廓像素通过编码方式V分配邻域配置：

(9)

(2)建立一张查阅表T，查阅表中的每一个元素由V定址。当编码的配置是一个端点时，将T[V]设置为1。首先确认它的编码配置V0，然后判断T[V0]的值是否为1，满足T[V0]=1的点就可以判定为端点。图2给出了一幅V=4的典型配置极点示意图，该标记方块表明了一个边界像素，且标号为5、6、7的方块表明该像素将包括在搜索过程中。

图2 V=4搜索示意图

为了建立闭合路径，需要检查图2中选中像素点的3个拓扑邻域。相对靠近中央区域的点的邻域坐标与T[V]连接，一个端点则是树的一个根节点，树的分支代表了所有可能的闭合路径。每个节点代表一个像素且被梯度值标号。一条路径的代价为该路径所有节点标号值之和。

使用广度优先算法挑出端点中最佳后继[12]，这里对广度优先算法进行优化，最佳后继点不可同属于同一连通分量[13]，即将搜索到非同一连通分量的端点相连，减少错边。将选中点标记为一个轮廓点，则上文所述的过程开始后，就开始建立闭合路径，直到满足停止搜索的条件。停止搜索条件为：路径的长度比给定的最大阈值要大，路径搜索中得到了可连接的一个端点。

其中，广度优先搜索算法的步骤如下[14]：

(1)把被搜索的像素点作为起点，对起点进行第一层搜索，如搜索到端点则结束，对下一个像素点重复进行搜索；否则进行步骤2。

(2)若步骤1中未搜索到目标点，则进行第二层搜索，第二层为第一层搜索逐个扩展得到的点，重复对每个点进行搜索，如搜索到端点则结束，对下一个像素点进行相同搜索步骤；否则判断搜索层数是否超过预设的最高搜索阈值，如果超过则本次搜索结束，对下一个像素进行广度优先搜索，如果未超则对第二层像素点继续扩展并重复步骤1。

2.2 实验结果和评价

采取基于广度优先的边缘连接算法对Canny边缘检测结果进行边缘连接，通过对比原图与连接后的图像，对基于广度优先的边缘连接算法的实验结果进行分析。

2.2.1 边缘连接图像展示

如图3所示，实验对边缘连接前后图像进行上色，连接起来的边缘点用相同颜色进行标记，相同颜色线条表明其为完整无断裂的线条。颜色数量越少，图像断裂处越少。对比图像实现边缘连接前后的边缘线颜色，可以看到经过广度优先算法优化后的边缘连接图像取得了较为理想的结果。

图3 图像对比

从图3明显看出边缘图像中颜色显著减少，即连通在一起的线段大幅增加，观察到图像中长颈鹿图形已经连接成为一个整体。由于广度优先的边缘连接算法事先定义了一个最大阈值，当对于一个端点的邻域搜索大于定义阈值时将不再进行搜索，也即该点不再与其他端点相连。因此可以看到图中距离较远的线条未被连接，从而保持了边缘图像的正确性。最大阈值的设置可尝试由大至小，低阈值连接范围小，连接的端点数会少于高阈值结果，但相应地，高阈值连接图中出现的假边缘错边缘概率也有可能增大。

该算法需要选择设置较优化的阈值，才使得图像端点既能得以较好连接，同时不会大幅增加假边错边的数量，此外搜索长度超出最大阈值时算法将放弃对该点的边缘连接，可能使得图像仍存在小部分断裂点。在实验结果中，最大阈值设为5，可以看到这种设定对于文中用到的图像有较好的效果。

2.2.2 边缘连接算法评估

为了对边缘连接算法进行定量的性能分析，需要将边缘连接前后的边缘点查全率R(也称召回率，Recall)[15]与连通分量进行计算与比较。查全率反映了检测结果的正确率，查全率越高，说明检测结果正确率越高，连通分量的数值反映了图像的连通性，连通分量越小，说明图像的连通性越好。

查全率R定义如下：

(10)

其中，Correctmun为通过Canny算子检测得到的边缘点正确个数之和，也即Canny检测结果中也属于标准边缘的像素点个数之和；Edgemun为标准正确边缘图像中边缘点的个数总和。

文中实现查全率检测的算法步骤如下：

(1)将待评估图像与正确边缘图像分别灰度化，易知不是白色像素点，即灰度值不为255的像素点即为两图边缘点。遍历每一个像素点，统计得到标准正确边缘图像中边缘点的个数总和Edgemun，同时初始化Correctmun值为0。

(2)对两图相同像素位置点进行判断，若待评估图像中为边缘点的像素点同时也为正确图像中的边缘点，则Correctmun加1。

(3)遍历每一个像素点，输出最终Correctmun值。

(4)使用式10计算出R值。

对连通分量的定义如下：无向图V中，若两个顶点相连，则称两顶点是连通的，整幅图像每个点之间都是两两相连的则称其为连通图，否则称为非连通图。一个非连通图的极大连通子图就是该图的一个连通分量。将每一个极大连通子图分别用不同色彩标记，可直观判断出实现边缘连接算法之后的图像连通分量的数量是否减少。

文中采用了ETHZ Shape Classes-V1.2数据库中的图像及其人工标记出的相应图像的边缘作为判别标准。对经过边缘连接的Canny算法和本节边缘连接算法优化后的10幅图像分别计算查全率与联通分量，并对结果求平均值，结果如表1所示。

由表1可知，在使用边缘连接算法后图像查全率均有所提高，而优化后边缘图像连通分量均大幅降低。由此可以得出，基于广度优先的边缘连接算法能够对Canny算子进行优化改进，对提高图像连通性起到了较为理想的效果。

3 结束语

文中采用基于广度优先的边缘检测算法，在Canny算子的基础上实现了边缘优化，采用基于广度优先的边缘连接算法，减少断裂点，从而提高边缘连续性和图像连通性。基于广度优先的边缘连接算法在优化阈值选取时可以针对边缘图像断裂处主动进行边缘预测，不依赖于图像梯度和图像自身，从而成功连接大部分细小的断裂边缘。研究结果证明了该算法的有效性。

参考文献：

[1] ARAGHI L F,ARVAN M R.An implementation image edge and feature detection using neural network[C]//Proceedings of the international multi conference of engineers and computer scientists.[s.l.]:[s.n.],2009:18-20.

[2] 廖剑利.基于小波变换的图像边缘检测方法研究[D].长沙：湖南大学，2005.

[3] KONISHI S,YUILLE A,COUGHLAN J.A statistical approach to multi-scale edge detection[J].Image and Vision Computing,2003,21(1):37-48.

[4] 蒋 伟,陈 辉.基于分数阶微分和Sobel算子的边缘检测新模型[J].计算机工程与应用,2012,48(4):182-185.

[5] 薛丽霞,李 涛,王佐成.一种自适应的Canny边缘检测算法[J].计算机应用研究,2010,27(9):3588-3590.

[6] 贺 强,晏 立.基于LOG和Canny算子的边缘检测算法[J].计算机工程,2011,37(3): 210-212.

[7] 谭 艳,王宇俊,李飞龙,等.几种典型的图像边缘检测算法的分析比较[J].电脑知识与技术,2012,8(3):1604-1608.

[8] 贺赛先,唐 艳.一种基于人类感知的边缘连接方法[J].红外技术,2005,27(4):338-342.

[9] 文贡坚,王润生.一种稳健的直线提取算法[J].软件学报,2001,12(11):1660-1666.

[10] 杨智明.图的广度优先搜索遍历算法的分析与实现[J].农业网络信息,2009(12):136-137.

[11] 曾 俊.图像边缘检测技术及其应用研究[D].武汉:华中科技大学,2012.

[12] GLIANNAROU S,TANIA S.A novel framework for object recognition under severe occlusion[J].Computational Intelligence,2013,410:235-258.

[13] GEORGIEVA P,MIHAYLOVA L,JAIN L C.Advances in intelligent signal processing and data mining:theory and applications[M].Berlin:Springer,2013.

[14] 张 研,韩 露.用广度优先搜索算法实现路径搜索[J].电脑编程技巧与维护,2012(19):78-81.

[15] SMEULDERS A W M,SANTINI S,WORRING M,et al.Content based image retrieval at the end of the early years[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(12):1349-1380.