基于图搜索策略的边缘检测方法

刘 炀,石文莹，石鸽娅，王 静，汤传玲

（合肥工业大学，安徽 合肥230009）

图像边缘是图像识别和计算机分析的关键信息。边缘蕴含了丰富的内在信息，是图像识别中抽取图像特征的重要属性。本质上说，图像边缘是图像局部特性不连续性的反映，它标志着一个区域的终结和另一个区域的开始。边缘提取首先检出图像局部特性的不连续性，然后再将这些不连续的边缘像素连成完备的边界。边缘的特性是沿边缘走向的像素变化平缓，而垂直于边缘方向的像素变化剧烈。从这个意义上说，提取边缘的算法就是检出符合边缘特性的边缘像素的数学算子。

目前提取边缘常采用边缘算子法、内边界检测、图搜索策略、曲面拟合法、模板匹配法和门限化等方法。

1 边缘检测算子法

在图像分析中，边缘一般用于寻找区域的边界。假定区域具有均匀的亮度，其边界就是图像函数变化的位置，因此,在理想情况下,具有高边缘幅值的像素中没有噪声，可见边界与其组件（边缘）的梯度方向垂直。

检测小局部邻域的单个梯度算子事实上是卷积，可以用卷积掩模来表达。能够检测边缘方向的算子是用一组掩模来表达的，每个掩模对应一个方向。

1.1 Roberts算子

Roberts算子是最古老的算子之一,由于它只使用了当前像素的2×2邻域，因此计算非常简单。Roberts算子的卷积掩模为：

边缘的幅值计算为：

Roberts算子的主要缺点是对噪声高度敏感，因为它仅使用了很少几个像素来近似梯度。

1.2 Laplace算子

Laplace算子▽2是近似只给出梯度幅值的二阶导数的流行方法，Laplacian在数字图像中用卷积和来近似。通常使用3×3来掩模h，对于4-邻接和8-邻接的邻域分别定义为：

Laplace算子的缺点是它对图像中的某些边缘产生双重响应。

1.3 Prewitt算子

近似图像函数一阶导数的算子由于具有确定梯度方向的能力，有时被称作罗盘算子。对于每个算子,给出前面3×3掩模，其他可以通过简单旋转得到。

梯度方向由具有最大响应的掩模给出。对于以下所有的近似一阶导数的算子也都是如此。

1.4 Sobel算子

Sobel算子通常用于水平和垂直边缘的一个简单检测子，这时使用 h1和 h3。 如果 h1的响应是 y，h3的响应是x，则可以根据式(6)得出强度：

1.5 边缘算子法实验结果及分析

利用6种边缘检测算子检测出的边缘图像如图1所示。从实验结果可以看出，Roberts算子检测精度不够，忽略了一部分边界且有噪点；而 Log算子、Canny算子和高斯滤波后的Canny算子检测结果边界太过复杂，将很多背景像素识别成了边界；Sobel和Prewitt算子检测结果比较相近，但是Sobel算子检测结果散点较多，相比之下，Prewitt算子检测结果最令人满意。Prewitt算子检测的结果比另外5种算子的检测结果边界光滑、完整且散点少，因此本实验中Prewitt算子的检测结果被认为是这幅图的最优边缘，将它与其他方法得到的边界比较，从而给出其他算法相对合理的评价，如图2所示。其中，算子检测结果越接近1,效果越好。

2 内边界跟踪及实验分析

内边界跟踪对于超过一个像素大小的区域都有效（寻找单像素区域的边界毫无意义）。该算法可以找到区域的边界，但是不能找到区域孔的边界。如果还要搜索孔的边界，边界跟踪必须在每个区域或孔的边界元素上开始，而该元素必须是以前从来没有跟踪过的边界元素。寻找边界元素搜索总是在当前跟踪的边界封闭之后才进行，而搜索“还没有使用”的边界元素的方法可依照搜索第一个边界元素的方式进行。需要注意的是，如果物体是单像素宽，就需要增加一些条件；如果目标是检测区域的外边界,所给出的方法根据4-邻接仍然可以用。

根据给定的两个起始点和结束点搜索得到的边界图像如图3所示。因为图像中前景区域已被定义，所以检测出来的边界是唯一的。将该边界与前面Prewitt算子检测出的边缘进行比较 (内边界跟踪图像÷Prewitt算子边界图像)，得出评价值为2.562 8。内边界跟踪所得到的图像的优点是没有散点且图像的连续性好，但是由于算法本身的原因，一部分边界太粗了，不够简洁。

3 图搜索的边缘跟踪

图是由一组节点ni和节点间的弧(ni,nj)构成的一种普通结构。考虑有方向的数值加权的弧，这些权称为费用。边界检测过程被转换为在加权图中搜索最优路径的问题，目的是找到连接两个指定节点(即起点和终点)的最优路径。该方法同样适用于搜索费用最大化的路径。

3.1 5种启发函数

给定回溯路径的费用，或者每步取最优路径搜索，启发函数会有不同的检测范围，边界检测的结果当然也不同。

(1)启发函数 1

启发函数1是利用灰度图像灰度差值检测实现的搜索，开始节点与子节点的灰度差值越小，这个子节点越可能是下一个边界节点，将这些点连起来。其定义为：

其中，a、b都是图像上的点，g(x)是图像上点 x的灰度。图4所示为启发函数1的搜索范围和检测结果。

(2)启发函数 2

启发函数2是在启发函数1的基础上增加对节点距离判断来进行的搜索，开始节点与子节点的距离越近，这个子节点越可能是下一个边界节点，将这些点连起来。其定义为：

其中，a、b是图像上的点，g(x)是图像上点 x的灰度，d(x1,x2)是x1、x2两点之间的距离。图5所示为启发函数2的搜索范围和检测结果。

(3)启发函数 3

启发函数3是对区域对比度最大值的判断，它考虑中心点和周围邻接点之间的关系，将当前节点与以节点为中心的3×3邻域的灰度总和进行比较，对比度为最大值的作为下一个节点，继续上面操作。其定义为：

其中,Ω′是 3×3 的图像矩阵邻域，a 是 Ω′上的点，g(x)是图像上点 x的灰度，∑g(x)是 Ω′中所有点的灰度总和。图6所示为启发函数3的搜索范围和检测结果。

(4)启发函数 4

启发函数4是对区域灰度最大值的判断，节点灰度越大越可能是下一个边界节点，其定义为：

图7所示为启发函数4的搜索范围和检测结果。

(5)启发函数 5

启发函数5是Laplace检测子，它检测像素是边缘的可能性，越可能的点，回溯路径的费用就越小。其定义为：

其 中 ，a∈L(I3×3)，L(I3×3)是 Laplace 检 测 子;p(a)是 像 素 a的边缘概率，p(a)≥thre，thre是给定的阈值，通常给定thre=0.5。图8所示为启发函数5的搜索范围和检测结果。

3.2 5种启发函数对比

在每种启发函数的检测范围中，将背景颜色设为0（即深蓝色，见颜色表），起始点颜色设为 50，对每个检测范围进行标记，下一个检测范围颜色加1，这样，可以很直观地看出启发函数的搜索路径。将5种启发函数检测范围做比较，很容易发现启发函数4检测的路径非常明确，而且范围不大，效率较高。

5种启发函数检测范围的比较如图9所示，显然，启发函数4的搜索范围比其他4个小很多，它的搜索效率高于其他4个启发函数。

5种启发函数检测精度的比较如图10所示，启发函数1和启发函数2精度太低,而启发函数3和启发函数5虽然搜索精度也比较高，但是从视觉上就能发现其并不是所要的边界；而启发函数4的搜索精度达到了0.986 6,并且形状与原图非常相近。

本文分别用3种方法对图像边缘检测进行了实验，其中边缘检测算子是一组用于在亮度函数中定位变化的非常重要的局部图像预处理方法，而边缘是亮度函数发生急剧变化的位置。各边缘检测算子通过自己特有的卷积掩模与图像做卷积，得出边界图像。在本文的边缘检测算子实验中，Prewitt算子检测结果最令人满意。

内边界检测是通过给定起始点和结束点检测二值图像的，用每次最先找到的相同像素值的节点将起始点与结束点连接起来，如此反复，得出边界图像。这样检测出的图像连续性好，但是会造成一部分边界过粗。

基于图搜索的边缘跟踪是对每条路径进行判断并找出最优路径的过程，而启发式搜索在搜索过程中加入了与问题有关的启发性信息，用以指导搜索向着一个比较小的范围内进行，加速获得结果。本文实验中，启发函数4在搜索效率和精度上比其他启发函数更令人满意。

总体来说，各种方法都有其优势及不足，在实际应用中，需要通过对图像的分析进一步选择合适的算法，以找出最理想的边界图像。在实际操作中，不同的图像对启发函数的要求也不一样，如何找到最合理的启发函数对图像进行搜索有待研究。

[1]SCHETTINI R.A segmentation algorithm for color images[J].Pattern Recognition Letters,1993(14):499-506.

[2]PRIESE L,REHRMANN V.On hierarchical color segmentation and applications[C].IEEE Proceedings of Computer Vision and Pattern Recognition,1993:633-634.

[3]王耀南,李树涛,毛建旭.计算机图像处理与识别技术[M].北京：高等教育出版社,2001.

[4]孙慧,周红霞.图像处理中边缘检测技术的研究[J].电脑开发与应用,2002,15(10):7-9.

[5]赵雪松,陈淑珍.综合全局二值化与边缘检测的图像分割方法[J].计算机辅助设计与图形学学报,2001,13(2):118-121.