張寧波　劉振忠　張昆　王路路

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

關(guān)鍵詞：邊緣提??；圖論；閾值；噪聲

中圖分類(lèi)號(hào)：TP391.41

文獻(xiàn)標(biāo)志碼：A

0引言

圖像中目標(biāo)和背景間的邊界稱(chēng)為邊緣，通常使用圖像中像素灰度值的變化來(lái)檢測(cè)和提取邊緣。邊緣提取的目的是提取能夠被計(jì)算機(jī)識(shí)別的有價(jià)值的邊緣信息，以便于圖像目標(biāo)識(shí)別和圖像濾波[1]。邊緣提取是圖像分割和特征提取的基礎(chǔ)，同時(shí)也是機(jī)器視覺(jué)和模式識(shí)別的基礎(chǔ)[2]。因此，本文聚焦邊緣提取。

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

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

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

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

1本文方法原理

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

2.1像素間相似性計(jì)算

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

2.2閾值確定

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

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

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

本文方法的算法包括以下幾個(gè)步驟：

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

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

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

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

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

3實(shí)驗(yàn)結(jié)果分析及比較

為了驗(yàn)證本文方法的性能，將它與Sobel算子、Prewitt算子、LoG算子和Canny算子進(jìn)行了有無(wú)噪聲實(shí)驗(yàn)比較。在噪聲實(shí)驗(yàn)中，實(shí)驗(yàn)圖像被加入了Speckle噪聲和不同水平的高斯噪聲。本文選取了二維條碼、攝影師、漢字和車(chē)牌等圖像作為實(shí)驗(yàn)圖像。在式（2）中，dI、dX和r分別設(shè)置為25、2和2[7]。

3.1無(wú)噪聲實(shí)驗(yàn)比較

如圖4（b）～（d）所示，從整體來(lái)看，Sobel算子、Prewitt算子和LoG算子不能提取原始圖像（圖4（a））中心位置處蘋(píng)果標(biāo)志的完整邊緣，然而Canny算子和本文方法能夠很好地提取蘋(píng)果的邊緣。

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

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

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

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

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

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

3.2噪聲實(shí)驗(yàn)比較

為了驗(yàn)證本文方法的抗噪性能，本文進(jìn)行了漢字、二維條碼的Speckle噪聲實(shí)驗(yàn)和車(chē)牌的不同水平的高斯噪聲實(shí)驗(yàn)。

圖10和圖11分別顯示了各邊緣提取方法對(duì)含有Speckle噪聲（var=0.01）的漢字和二維條碼的邊緣提取結(jié)果。通過(guò)對(duì)比圖10與圖8、圖11與圖6，可以看出加入Speckle噪聲后，由Sobel算子、Prewitt算子、LoG算子和Canny算子提取的圖像邊緣變得更加抖動(dòng)，而本文方法提取的邊緣不存在抖動(dòng)。因此，本文方法對(duì)Speckle噪聲具有抗噪性能。

通過(guò)對(duì)比圖9、圖12～14，可知Sobel算子和Prewitt算子對(duì)高斯噪聲沒(méi)有抗噪性能，即Sobel算子和Prewitt算子不能提取出加入不同水平的高斯噪聲的車(chē)牌圖像的邊緣；當(dāng)高斯噪聲的均值由0.3增加到0.5時(shí)，LoG算子和Canny算子提取的邊緣也快速退化，而本文方法能清晰地提取出這些圖像的骨架。因此，本文方法對(duì)高斯噪聲具有抗噪性能，且優(yōu)于傳統(tǒng)邊緣提取方法。

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

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

4結(jié)語(yǔ)

本文提出了一種基于圖論的邊緣提取方法，它包括像素間相似性計(jì)算、閾值確定和邊緣確定三個(gè)階段。首先，將圖像看作無(wú)向帶權(quán)圖，利用邊上的權(quán)值從而計(jì)算出像素間相似性；其次，全部權(quán)值（整幅圖像的相似度）的均值被確定為閾值；最后通過(guò)保留權(quán)值小于閾值的水平邊的左邊的節(jié)點(diǎn)與垂直邊的上邊的節(jié)點(diǎn)從而獲得圖像的邊緣。實(shí)驗(yàn)結(jié)果表明，本文方法適用于具有明顯目標(biāo)與背景的圖像的邊緣提取，能夠克服Sobel算子、Prewitt算子、LoG算子和Canny算子的不足，例如不連續(xù)性、不完整、傾斜、抖動(dòng)和缺口等，并且該方法對(duì)Speckle噪聲和高斯噪聲具有一定的抗噪性能。而對(duì)于不具有明顯目標(biāo)與背景圖像的邊緣提取及提取耗時(shí)上有待更進(jìn)一步的研究。

本文無(wú)矢量、向量、矩陣。為空集。

參考文獻(xiàn)：

[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]. 計(jì)算機(jī)學(xué)報(bào)， 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].計(jì)算機(jī)工程與應(yīng)用，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]張帆，彭中偉，蒙水金.基于自適應(yīng)閾值的改進(jìn)Canny邊緣檢測(cè)方法[J].計(jì)算機(jī)應(yīng)用，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].計(jì)算機(jī)應(yīng)用，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.）