基于圖論的邊緣提取方法

張寧波　劉振忠　張昆　王路路

摘要：針對傳統(tǒng)邊緣方法提取的邊緣具有不連續(xù)、不完整、傾斜、抖動和缺口等問題，提出基于圖論的邊緣提取方法。該方法視像素為節(jié)點，在水平或垂直方向上連接兩個相鄰的節(jié)點構成一個邊，從而將圖像看作無向圖。它包括三個階段：在像素相似性計算階段，無向圖的邊上被賦予權值，權值代表了像素間的相似性；在閾值確定階段，將所有權值的均值（整幅圖像的相似度）確定為閾值；在邊緣確定階段，只保留權值小于閾值的水平邊的左邊節(jié)點與垂直邊的上邊節(jié)點，從而獲得了圖像的邊緣。實驗表明，該方法適用于具有明顯目標與背景的圖像的邊緣提取，能夠克服不連續(xù)、不完整、傾斜、抖動和缺口等缺陷，并且對Speckle噪聲和高斯噪聲具有抗噪性能。

關鍵詞：邊緣提取；圖論；閾值；噪聲

中圖分類號：TP391.41

文獻標志碼：A

0引言

圖像中目標和背景間的邊界稱為邊緣，通常使用圖像中像素灰度值的變化來檢測和提取邊緣。邊緣提取的目的是提取能夠被計算機識別的有價值的邊緣信息，以便于圖像目標識別和圖像濾波[1]。邊緣提取是圖像分割和特征提取的基礎，同時也是機器視覺和模式識別的基礎[2]。因此，本文聚焦邊緣提取。

目前，現(xiàn)有的邊緣提取方法主要分為兩類[3]：第一類使用一階偏導數(shù)提取邊緣，例如Sobel算子和Prewitt算子；第二類使用二階偏導數(shù)提取邊緣，例如LoG（Laplacian of Gaussian）算子。此外，還有其他的邊緣提取方法，例如Canny算子。

在上述的邊緣提取方法中，Sobel算子、Prewitt算子和LoG算子計算簡單，但對噪聲敏感[4]，它們提取的邊緣是不精確的，例如不連續(xù)、不完整、傾斜、抖動和缺口等。Canny算子能夠克服不連續(xù)和不完整問題，但仍然存在傾斜、抖動和缺口等缺陷（如圖1所示）；此外，Canny算子也對噪聲敏感。為了克服上述邊緣提取方法的不足，本文提出了基于圖論的邊緣提取方法。

通常，邊緣提取方法包括像素差異性計算、閾值確定和邊緣確定三個階段。在像素差異性計算階段，先前方法使用梯度（模板）來描述像素差異性，例如Sobel算子和Prewitt算子，如果某像素點的梯度值大于閾值，那么該點被看作邊緣點[5]；然而，本文使用像素間相似性來描述像素差異性，如果兩個像素的相似性小于閾值，那么其中的一個像素點被看作邊緣點。在閾值確定階段，先前方法主要使用給定的閾值；而本文方法將整幅圖像的相似度均值看作閾值，它能夠描述圖像的全部信息，彌補了直接給出閾值的主觀性。

基于上述分析，本文利用無向圖理論提出了基于圖論的邊緣提取方法，它包括像素間相似性計算、閾值確定和邊緣確定三個階段。

1本文方法原理

2基于圖論的邊緣提取方法

2.1像素間相似性計算

為了能夠表示像素間的像素差異性，本文借助無向圖理論提出了像素間相似性。如圖2（a）所示，本文將圖像視為無向圖，對無向圖的邊賦予權值，它代表了由這條邊連接起來的兩個節(jié)點的相似度，從而構建了基于無向帶權圖的像素間相似性。本文利用圖像像素的整體信息（灰度值與空間位置）計算邊上的權值（像素間相似性），即w（u，v）[7-8]：

2.2閾值確定

對于基于圖論的邊緣提取方法，如何確定閾值尤為重要，它決定了其結果的優(yōu)劣。在先前文獻中，閾值通?；谀承┮?guī)則被確定出來，這些規(guī)則被應用于局部或者全局閾值方法。對于局部閾值方法，例如，文獻[9]以灰度方差法為基礎，結合灰度梯度與灰度方差的特性從而確定局部閾值；文獻[10]運用圖像梯度方差對圖像加以分塊，并對各子塊采用最大類間方差法從而確定閾值。對于全局閾值方法，例如，文獻[11]通過最大化目標和背景中像素的熵從而確定閾值；文獻[12]利用定義的邊界梯度控制函數(shù)確定了分割閾值的集合，并在該集合中采用最大熵原理求得最優(yōu)閾值。在本文中，閾值是基于全局閾值而確定的。根據(jù)圖像的特性，即像素在目標和背景內(nèi)部的相似性大，而在邊緣處相似性小，由此可知，EA和EB中邊上的權值是大于EAB中邊上的權值，因此可以推斷出所有的權值的均值（mean）小于或等于EA和EB中邊上的權值，而大于EAB中邊上的權值。因此，mean被確定為閾值。mean的定義為：

步驟2確定圖像的邊緣，它由節(jié)點（像素）構成。本文只保留EAB中的所有水平邊的左邊節(jié)點（像素），即標記成深灰色的節(jié)點，將它們的灰度值設置為255，其余節(jié)點（像素）的灰度值設置為0，從而獲得圖像中的垂直邊（見圖3（b））；另一方面，本文只保留EAB中的所有垂直邊的上邊節(jié)點（像素），即標記成深灰色的節(jié)點，將它們的灰度值設置為255，其余節(jié)點（像素）的灰度值設置為0，從而獲得了圖像中的水平邊（見圖3（c））。綜上所述，被保留下來的節(jié)點（像素）構成了圖像的最終邊緣（見圖3（d））。

2.4基于圖論的邊緣提取方法的算法

本文方法的算法包括以下幾個步驟：

步驟1將原始圖像轉(zhuǎn)化成一個無向圖。將像素視為節(jié)點，在水平或垂直方向連接兩個相鄰的節(jié)點構成一條邊，從而將一幅圖像轉(zhuǎn)化成一個無向圖，如圖2（a）所示。

步驟2像素間相似性計算。按式（2）計算出每一條邊上的權值，它代表了這條邊連接的兩個節(jié)點（像素）的相似度。

步驟3確定閾值。按式（3）求得閾值，它是在全部均值的基礎上確定的，因此它能夠代表圖像的全部信息。

步驟4獲得邊集EAB。邊集EAB包括水平邊和垂直邊，將權值與閾值進行比較，若水平方向邊上的權值小于閾值，則這條水平邊被確定為邊集EAB內(nèi)的水平邊；若垂直方向邊上的權值小于閾值，則這條垂直邊被確定為邊集EAB內(nèi)的垂直邊。按照這種方式，通過選擇權值小于閾值的這些邊從而獲得邊集EAB。

步驟5獲取圖像的邊緣。圖像的邊緣由節(jié)點（像素）構成，通過保留EAB中水平邊的左邊的節(jié)點（像素）與垂直邊的上邊的節(jié)點（像素），將其灰度值設置為255，將未保留的節(jié)點（像素）的灰度值設置為0，從而獲得圖像的垂直邊與水平邊。按照上述方式，通過節(jié)點的保留與更新設置其灰度值，從而獲得圖像的邊緣。

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算子和本文方法能夠很好地提取蘋果的邊緣。

為了更好地比較上述方法的優(yōu)劣，本文在圖4中選取了兩個部分并加以放大，并采用白色實線和白色虛線的方框加以區(qū)別，經(jīng)放大后的結果分別如圖5和圖6所示。

如圖5與圖6所示，Sobel算子、Prewitt算子、LoG算子和Canny算子提取的邊緣均有不同程度的缺陷。其中：Sobel算子、Prewitt算子提取的邊緣具有不連續(xù)、傾斜、抖動與缺口等缺陷；LoG算子和Canny算子提取的邊緣具有傾斜、抖動的情況，并且Canny算子提取的邊緣存在缺口；而本文方法提取的邊緣不存在上述缺陷，從這方面來看，本文方法優(yōu)于Sobel算子、Prewitt算子、LoG算子和Canny算子。

從圖7（b）～（c）可以看出，Sobel算子與Prewitt算子不能提取圖像中的一些細節(jié)邊緣，例如，攝影師的手、耳朵與頭發(fā)的邊緣沒有被很好地提取出來，而且提取出來的邊緣是不連續(xù)的、不完整的。圖7（d）～（f）顯示，LoG算子、Canny算子和本文方法提取的圖像邊緣是連續(xù)的、完整的；然而，LoG算子和Canny算子在提取攝影師有價值的邊緣的同時，也提取了很多無價值的邊緣。而本文方法既能夠提取攝影師有價值的邊緣，又減少了無價值邊緣的提取數(shù)量。

如圖8所示，Sobel算子、Prewitt算子、LoG算子和Canny算子提取的邊緣是不連續(xù)的、不完整的、抖動的，特別是漢字“圖”外框的提取結果，此外部分邊緣還存在缺口；然而本文方法提取的邊緣則不存在上述缺陷。

從圖9可以看出，本文方法提取的車牌的邊緣比Sobel算子、Prewitt算子、LoG算子和Canny算子提取的邊緣更加清晰和完整。

基于以上分析，本文方法優(yōu)于傳統(tǒng)邊緣提取方法。

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算子提取的邊緣也快速退化，而本文方法能清晰地提取出這些圖像的骨架。因此，本文方法對高斯噪聲具有抗噪性能，且優(yōu)于傳統(tǒng)邊緣提取方法。

為了驗證本文方法的效率，將上述方法提取各圖像邊緣的時間進行了8次隨機統(tǒng)計，并求均值進行匯總得到表1。由表1 可以看出，當圖像分辨率較低（像素數(shù)較少）時，例如圖8、圖10～11，各方法的運行時間滿足：本文

綜上，本文選取的圖像具有明顯的目標與背景，根據(jù)上述各方法提取的邊緣結果可知，本文方法對水平邊緣與垂直邊緣比較敏感，并能夠?qū)λ鼈冞M行完整的提取，此外，通過對攝影師與車牌的邊緣提取可知，本文方法也適用于其他方向的邊緣的提取。因此，本文方法適用于具有明顯目標與背景的圖像邊緣的提取。

4結語

本文提出了一種基于圖論的邊緣提取方法，它包括像素間相似性計算、閾值確定和邊緣確定三個階段。首先，將圖像看作無向帶權圖，利用邊上的權值從而計算出像素間相似性；其次，全部權值（整幅圖像的相似度）的均值被確定為閾值；最后通過保留權值小于閾值的水平邊的左邊的節(jié)點與垂直邊的上邊的節(jié)點從而獲得圖像的邊緣。實驗結果表明，本文方法適用于具有明顯目標與背景的圖像的邊緣提取，能夠克服Sobel算子、Prewitt算子、LoG算子和Canny算子的不足，例如不連續(xù)性、不完整、傾斜、抖動和缺口等，并且該方法對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.）