基于图论的边缘提取方法

张宁波　刘振忠　张昆　王路路

摘要：针对传统边缘方法提取的边缘具有不连续、不完整、倾斜、抖动和缺口等问题，提出基于图论的边缘提取方法。该方法视像素为节点，在水平或垂直方向上连接两个相邻的节点构成一个边，从而将图像看作无向图。它包括三个阶段：在像素相似性计算阶段，无向图的边上被赋予权值，权值代表了像素间的相似性；在阈值确定阶段，将所有权值的均值（整幅图像的相似度）确定为阈值；在边缘确定阶段，只保留权值小于阈值的水平边的左边节点与垂直边的上边节点，从而获得了图像的边缘。实验表明，该方法适用于具有明显目标与背景的图像的边缘提取，能够克服不连续、不完整、倾斜、抖动和缺口等缺陷，并且对Speckle噪声和高斯噪声具有抗噪性能。

关键词：边缘提取；图论；阈值；噪声

中图分类号：TP391.41

文献标志码：A

0引言

图像中目标和背景间的边界称为边缘，通常使用图像中像素灰度值的变化来检测和提取边缘。边缘提取的目的是提取能够被计算机识别的有价值的边缘信息，以便于图像目标识别和图像滤波[1]。边缘提取是图像分割和特征提取的基础，同时也是机器视觉和模式识别的基础[2]。因此，本文聚焦边缘提取。

目前，现有的边缘提取方法主要分为两类[3]：第一类使用一阶偏导数提取边缘，例如Sobel算子和Prewitt算子；第二类使用二阶偏导数提取边缘，例如LoG（Laplacian of Gaussian）算子。此外，还有其他的边缘提取方法，例如Canny算子。

在上述的边缘提取方法中，Sobel算子、Prewitt算子和LoG算子计算简单，但对噪声敏感[4]，它们提取的边缘是不精确的，例如不连续、不完整、倾斜、抖动和缺口等。Canny算子能够克服不连续和不完整问题，但仍然存在倾斜、抖动和缺口等缺陷（如图1所示）；此外，Canny算子也对噪声敏感。为了克服上述边缘提取方法的不足，本文提出了基于图论的边缘提取方法。

通常，边缘提取方法包括像素差异性计算、阈值确定和边缘确定三个阶段。在像素差异性计算阶段，先前方法使用梯度（模板）来描述像素差异性，例如Sobel算子和Prewitt算子，如果某像素点的梯度值大于阈值，那么该点被看作边缘点[5]；然而，本文使用像素间相似性来描述像素差异性，如果两个像素的相似性小于阈值，那么其中的一个像素点被看作边缘点。在阈值确定阶段，先前方法主要使用给定的阈值；而本文方法将整幅图像的相似度均值看作阈值，它能够描述图像的全部信息，弥补了直接给出阈值的主观性。

基于上述分析，本文利用无向图理论提出了基于图论的边缘提取方法，它包括像素间相似性计算、阈值确定和边缘确定三个阶段。

1本文方法原理

2基于图论的边缘提取方法

2.1像素间相似性计算

为了能够表示像素间的像素差异性，本文借助无向图理论提出了像素间相似性。如图2（a）所示，本文将图像视为无向图，对无向图的边赋予权值，它代表了由这条边连接起来的两个节点的相似度，从而构建了基于无向带权图的像素间相似性。本文利用图像像素的整体信息（灰度值与空间位置）计算边上的权值（像素间相似性），即w（u，v）[7-8]：

2.2阈值确定

对于基于图论的边缘提取方法，如何确定阈值尤为重要，它决定了其结果的优劣。在先前文献中，阈值通常基于某些规则被确定出来，这些规则被应用于局部或者全局阈值方法。对于局部阈值方法，例如，文献[9]以灰度方差法为基础，结合灰度梯度与灰度方差的特性从而确定局部阈值；文献[10]运用图像梯度方差对图像加以分块，并对各子块采用最大类间方差法从而确定阈值。对于全局阈值方法，例如，文献[11]通过最大化目标和背景中像素的熵从而确定阈值；文献[12]利用定义的边界梯度控制函数确定了分割阈值的集合，并在该集合中采用最大熵原理求得最优阈值。在本文中，阈值是基于全局阈值而确定的。根据图像的特性，即像素在目标和背景内部的相似性大，而在边缘处相似性小，由此可知，EA和EB中边上的权值是大于EAB中边上的权值，因此可以推断出所有的权值的均值（mean）小于或等于EA和EB中边上的权值，而大于EAB中边上的权值。因此，mean被确定为阈值。mean的定义为：

步骤2确定图像的边缘，它由节点（像素）构成。本文只保留EAB中的所有水平边的左边节点（像素），即标记成深灰色的节点，将它们的灰度值设置为255，其余节点（像素）的灰度值设置为0，从而获得图像中的垂直边（见图3（b））；另一方面，本文只保留EAB中的所有垂直边的上边节点（像素），即标记成深灰色的节点，将它们的灰度值设置为255，其余节点（像素）的灰度值设置为0，从而获得了图像中的水平边（见图3（c））。综上所述，被保留下来的节点（像素）构成了图像的最终边缘（见图3（d））。

2.4基于图论的边缘提取方法的算法

本文方法的算法包括以下几个步骤：

步骤1将原始图像转化成一个无向图。将像素视为节点，在水平或垂直方向连接两个相邻的节点构成一条边，从而将一幅图像转化成一个无向图，如图2（a）所示。

步骤2像素间相似性计算。按式（2）计算出每一条边上的权值，它代表了这条边连接的两个节点（像素）的相似度。

步骤3确定阈值。按式（3）求得阈值，它是在全部均值的基础上确定的，因此它能够代表图像的全部信息。

步骤4获得边集EAB。边集EAB包括水平边和垂直边，将权值与阈值进行比较，若水平方向边上的权值小于阈值，则这条水平边被确定为边集EAB内的水平边；若垂直方向边上的权值小于阈值，则这条垂直边被确定为边集EAB内的垂直边。按照这种方式，通过选择权值小于阈值的这些边从而获得边集EAB。

步骤5获取图像的边缘。图像的边缘由节点（像素）构成，通过保留EAB中水平边的左边的节点（像素）与垂直边的上边的节点（像素），将其灰度值设置为255，将未保留的节点（像素）的灰度值设置为0，从而获得图像的垂直边与水平边。按照上述方式，通过节点的保留与更新设置其灰度值，从而获得图像的边缘。

3实验结果分析及比较

为了验证本文方法的性能，将它与Sobel算子、Prewitt算子、LoG算子和Canny算子进行了有无噪声实验比较。在噪声实验中，实验图像被加入了Speckle噪声和不同水平的高斯噪声。本文选取了二维条码、摄影师、汉字和车牌等图像作为实验图像。在式（2）中，dI、dX和r分别设置为25、2和2[7]。

3.1无噪声实验比较

如图4（b）～（d）所示，从整体来看，Sobel算子、Prewitt算子和LoG算子不能提取原始图像（图4（a））中心位置处苹果标志的完整边缘，然而Canny算子和本文方法能够很好地提取苹果的边缘。

为了更好地比较上述方法的优劣，本文在图4中选取了两个部分并加以放大，并采用白色实线和白色虚线的方框加以区别，经放大后的结果分别如图5和图6所示。

如图5与图6所示，Sobel算子、Prewitt算子、LoG算子和Canny算子提取的边缘均有不同程度的缺陷。其中：Sobel算子、Prewitt算子提取的边缘具有不连续、倾斜、抖动与缺口等缺陷；LoG算子和Canny算子提取的边缘具有倾斜、抖动的情况，并且Canny算子提取的边缘存在缺口；而本文方法提取的边缘不存在上述缺陷，从这方面来看，本文方法优于Sobel算子、Prewitt算子、LoG算子和Canny算子。

从图7（b）～（c）可以看出，Sobel算子与Prewitt算子不能提取图像中的一些细节边缘，例如，摄影师的手、耳朵与头发的边缘没有被很好地提取出来，而且提取出来的边缘是不连续的、不完整的。图7（d）～（f）显示，LoG算子、Canny算子和本文方法提取的图像边缘是连续的、完整的；然而，LoG算子和Canny算子在提取摄影师有价值的边缘的同时，也提取了很多无价值的边缘。而本文方法既能够提取摄影师有价值的边缘，又减少了无价值边缘的提取数量。

如图8所示，Sobel算子、Prewitt算子、LoG算子和Canny算子提取的边缘是不连续的、不完整的、抖动的，特别是汉字“图”外框的提取结果，此外部分边缘还存在缺口；然而本文方法提取的边缘则不存在上述缺陷。

从图9可以看出，本文方法提取的车牌的边缘比Sobel算子、Prewitt算子、LoG算子和Canny算子提取的边缘更加清晰和完整。

基于以上分析，本文方法优于传统边缘提取方法。

3.2噪声实验比较

为了验证本文方法的抗噪性能，本文进行了汉字、二维条码的Speckle噪声实验和车牌的不同水平的高斯噪声实验。

图10和图11分别显示了各边缘提取方法对含有Speckle噪声（var=0.01）的汉字和二维条码的边缘提取结果。通过对比图10与图8、图11与图6，可以看出加入Speckle噪声后，由Sobel算子、Prewitt算子、LoG算子和Canny算子提取的图像边缘变得更加抖动，而本文方法提取的边缘不存在抖动。因此，本文方法对Speckle噪声具有抗噪性能。

通过对比图9、图12～14，可知Sobel算子和Prewitt算子对高斯噪声没有抗噪性能，即Sobel算子和Prewitt算子不能提取出加入不同水平的高斯噪声的车牌图像的边缘；当高斯噪声的均值由0.3增加到0.5时，LoG算子和Canny算子提取的边缘也快速退化，而本文方法能清晰地提取出这些图像的骨架。因此，本文方法对高斯噪声具有抗噪性能，且优于传统边缘提取方法。

为了验证本文方法的效率，将上述方法提取各图像边缘的时间进行了8次随机统计，并求均值进行汇总得到表1。由表1 可以看出，当图像分辨率较低（像素数较少）时，例如图8、图10～11，各方法的运行时间满足：本文

综上，本文选取的图像具有明显的目标与背景，根据上述各方法提取的边缘结果可知，本文方法对水平边缘与垂直边缘比较敏感，并能够对它们进行完整的提取，此外，通过对摄影师与车牌的边缘提取可知，本文方法也适用于其他方向的边缘的提取。因此，本文方法适用于具有明显目标与背景的图像边缘的提取。

4结语

本文提出了一种基于图论的边缘提取方法，它包括像素间相似性计算、阈值确定和边缘确定三个阶段。首先，将图像看作无向带权图，利用边上的权值从而计算出像素间相似性；其次，全部权值（整幅图像的相似度）的均值被确定为阈值；最后通过保留权值小于阈值的水平边的左边的节点与垂直边的上边的节点从而获得图像的边缘。实验结果表明，本文方法适用于具有明显目标与背景的图像的边缘提取，能够克服Sobel算子、Prewitt算子、LoG算子和Canny算子的不足，例如不连续性、不完整、倾斜、抖动和缺口等，并且该方法对Speckle噪声和高斯噪声具有一定的抗噪性能。而对于不具有明显目标与背景图像的边缘提取及提取耗时上有待更进一步的研究。

本文无矢量、向量、矩阵。为空集。

参考文献：

[1]LOPEZ-MOLINA C， DE BAETS B， BUSTINCE H. A framework for edge detection based on relief functions [J]. Information Sciences， 2014， 278： 127-140.

[2]EL-TAWEL G S， HELMY A K. An edge detection scheme based on least squares support vector machine in a contourlet HMT domain [J]. Applied Soft Computing， 2015， 26： 418-427.

[3]BHARDWAJ S， MITTAL A. A survey on various edge detector techniques [J]. Procedia Technology， 2012， 4： 220-226.

[4]JUNEJA M， SANDHU P S. Performance evaluation of edge detection techniques for images in spatial domain [J]. International Journal of Computer Theory and Engineering， 2009， 1（5）： 1793-8201.

http：//ijcte.org/papers/100-G205-621.pdf

[5]SRIDEVI M， MALA C. A survey on monochrome image segmentation methods [J]. Procedia Technology， 2012， 6： 548-555.

[6]SHI J， MALIK J. Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888-905.

[7]陶文兵， 金海. 一种新的基于图谱理论的图像阈值分割方法[J]. 计算机学报， 2007， 30（1）： 110-119.（TAO W B， JIN H. A new image thresholding method based on graph spectral theory [J]. Chinese Journal of Computers， 2007， 30（1）： 110-119.）

[8]SEN D， GUPTA N， PAL S K. Incorporating local image structure in normalized cut based graph partitioning for grouping of pixels [J]. Information Sciences， 2013， 248： 214-238.

[9]马文科，王玲，何浩.一种指纹图像的局部阈值分割算法[J].计算机工程与应用，2009，45（34）：177-179. （MA W K， WANG L， HE H. Local threshold segmentation algorithm for fingerprint images [J]. Computer Engineering and Applications， 2009， 45（34）： 177-179.）

[10]张帆，彭中伟，蒙水金.基于自适应阈值的改进Canny边缘检测方法[J].计算机应用，2012，32（8）：2296-2298. （ZHANG F， PENG Z W， MENG S J. Improved Canny edge detection method based on self-adaptive threshold [J]. Journal of Computer Applications， 2012， 32（8）： 2296-2298.）

[11]KAPUR J N， SAHOO P K， WONG A K C. A new method for gray-level picture thresholding using the entropy of the histogram [J]. Computer Vision Graphics & Image Processing， 1980， 29（3）：273-285.

[12]王倩.基于边界梯度控制的最大熵阈值分割方法[J].计算机应用，2011，31（4）：1030-1032. （WANG Q. Segmentation of maximum entropy threshold based on gradient boundary control [J]. Journal of Computer Applications， 2011， 31（4）： 1030-1032.）