基于彈簧質(zhì)點模型邊緣檢測算法的改進(jìn)

戚曉偉

摘要：本文基于物理學(xué)中彈簧力學(xué)的理論提出了一種改進(jìn)的彈簧質(zhì)點模型邊緣檢測算法。為解決現(xiàn)有彈簧質(zhì)點模型邊緣檢測算法檢測的邊緣較粗問題，本文在該模型計算像素點合力的公式中增加一個合力因子，結(jié)合數(shù)學(xué)形態(tài)學(xué)中腐蝕膨脹的原理來改進(jìn)彈簧質(zhì)點模型邊緣檢測算法，以便能得到單像素寬度的邊緣。實驗結(jié)果表明，該算法的檢測效果更加理想。

關(guān)鍵詞：邊緣檢測;彈簧質(zhì)點模型;數(shù)學(xué)形態(tài)學(xué);細(xì)化邊緣

中圖分類號：TP391.41;TP751文獻(xiàn)標(biāo)識碼：A

Theimproved algorithm based on Massspring model edge detection

Qi Xiaowei

Jiangsu College of TourismJiangsuYangzhou225217

Abstract：This paper puts forward an improved springmass model edge detection algorithm based on the physics of the spring mechanics theory.In order to solve the problem that the edges are thicker which is detected by the existing massspring model edge detection algorithm，based on the model this paper add a force factor to calculate the force.In the meanwhile the paper combines with mathematical morphology in the principle of erosion and dilation to improve massspring model edge detection algorithm so as to get the edge of single pixel width.The experimental results show that this algorithm can get more ideal results.

Key words：edge detection;Massspring model;mathematical morphology;edge thinning

圖像的邊緣信息往往能夠告訴我們圖像的特征信息，因而圖像的邊緣檢測一直是人們值得研究和關(guān)注的課題。傳統(tǒng)的邊緣檢測算子，多數(shù)都是基于微分的算子，算法盡管簡單，編程方便，然而對噪聲的極其敏感，限制了在實際當(dāng)中的應(yīng)用[1]。隨著科學(xué)技術(shù)的不斷進(jìn)步，出現(xiàn)了新的邊緣檢測算法，Sun等人在2007年結(jié)合物理學(xué)知識提出了基于萬有引力的邊緣檢測算法[2]，這種算法新穎獨(dú)特，開拓了邊緣檢測研究的新視野，在此啟發(fā)下，文獻(xiàn)[3]提出了彈簧質(zhì)點模型邊緣檢測算法，但該算法檢測到的邊緣較粗。本文在分析了彈簧質(zhì)點模型算法的缺點后，在計算像素合力時增加一個合力因子（鄰域灰度均值與中心像素灰度之和），并利用數(shù)學(xué)形態(tài)學(xué)中腐蝕膨脹的原理對該算法進(jìn)行改善，得到了單像素邊緣的檢測算法。

1 彈簧質(zhì)點模型邊緣檢測算法原理

就物理角度看，彈簧質(zhì)點模型是一個經(jīng)典的力學(xué)模型，它一直廣泛地應(yīng)用于織物變形及圖像配準(zhǔn)的研究中[4]。彈簧質(zhì)點模型邊緣檢測算法也是利用這個物理模型，將鄰域內(nèi)中心像素所受到的合力通過門限值作為判定是否是邊緣點的依據(jù)，取得了較好的邊緣檢測效果。

在一個彈簧質(zhì)點模型中，假設(shè)兩質(zhì)點之間存在的是一根無質(zhì)量的彈簧。使彈簧變形的主要有拉伸力FS、剪切力FC和彎曲力FB三類彈性力，那么所受內(nèi)力可以表示為：

Fin=FS+FC+FB（1）

為了盡量簡化過程，每個像素所受的力只考慮拉伸力FS。

原始圖像X，（x，y）處的像素灰度值為X（x，y）。我們把圖像中的各像素點看成彈簧模型中的質(zhì)點，記一個像素受到另一個像素拉力的大小和方向可以用一個矢量FM，N來表示，則根據(jù)力學(xué)胡克定律，F(xiàn)M，N可表示為：

FM，N=kMN（‖XN-XM‖-l0MN）·XN-XM‖XN-XM‖

=kMN1-l0MN‖XN-XM‖·（XN-XM）（2）

其中，l0MN表示該模型在開始狀態(tài)時兩個質(zhì)點M與N之間的自由長度，即彈簧的初始長度，kMN表示質(zhì)點間的彈簧系數(shù)，‖XN-XM‖表示兩個質(zhì)點M、N的歐氏距離，XM和XN表示兩質(zhì)點的像素灰度值[5]。

在圖像的3×3鄰域內(nèi)，對于圖像中的每個像素點，通過來自其周圍像素點的彈簧拉力的合力大小判定它是否是邊緣上的點。中心像素點假設(shè)為（i，j），鄰域內(nèi)其他像素點記為（k，l）。則算法步驟為：

（1）分別計算周圍像素點對中心像素點的彈簧拉力。

對于中心像素點（i，j），若（k，l）處于它的水平位置，則（i，j）在水平和垂直方向上的受力為：

F1x（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））

F1y（i，j;k，l）=0（3）

同理，若（k，l）處于它的垂直位置，則（i，j）在水平和垂直方向上的受力為：

F1x（i，j;k，l）=0

F1y（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））（4）

若（k，l）處于它的對角位置，則（i，j）在水平和垂直方向上的受力為：

F2x（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））·cosθ

F2y（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））·sinθ（5）

其中，θ為45°。

（2）計算中心像素點（i，j）所受合力F在x，y軸方向上的分力。

Fx=∑F1x（i，j;k.l）+∑F2x（i，j;k，l）

Fy=∑F1y（i，j;k.l）+∑F2y（i，j;k，l）（6）

（3）計算中心像素點所受合力F和方向角θ。

F=F2x+F2y，θ=arctanFyFx（7）

（4）設(shè)置一個合適的閾值T，如果某像素點所受合力大于這個閾值，可以認(rèn)為這個像素點為邊緣點。

2 改進(jìn)的彈簧質(zhì)點模型邊緣檢測算法

原始的彈簧質(zhì)點模型的邊緣檢測算法由于沒有使用傳統(tǒng)的微分算法檢測邊緣，雖然在抗噪聲性能上有一定的提高，但檢測到的邊緣也較粗，因此本文從以下兩個方面對該算法進(jìn)行改善。

2.1 合力算法的分析及改善

原始彈簧質(zhì)點模型邊緣檢測算法檢測出的邊緣較粗。以下從二值合成圖像分析導(dǎo)致該結(jié)果的原因。

在圖1中，假設(shè)鄰域內(nèi)水平或垂直的兩像素點間的歐氏距離設(shè)為a，那么對角的兩像素點間的距離為2a，為方便計算，這里設(shè)定彈簧系數(shù)為1.0，彈簧的初始長度為1.0，并且合成的二值圖像白色像素點灰度值為1，黑色像素點灰度值為0。那么可以計算：

F1=F4=0（8）

F2x=22（1-12a）（X5-X2）+22（1-12a）（X9-X2）+（1-1a）（X1-X2）-22（1-12a）（X7-X2）-22（1-12a）（X11-X2）-（1-1a）（X3-X2）

=-（2+1-2a）F2y=22（1-12a）（X5-X2）+22（1-12a）（X7-X2）+（1-1a）（X6-X2）-22（1-12a）（X9-X2）-22（1-12a）（X11-X2）-（1-1a）（X10-X2）

=0

從而像素點2所受到的合力：

F2=F22x+F22y=（2+1-2a）（9）

同理，像素點3所受到的合力也為F3=（2+1-2a）。在選定合適閾值后，由于像素點2、3所受到的合力值相同，因此在檢測時把這兩個像素點都判定為邊緣點，顯然這是不合理的。從圖2中可以看出，像素點2和3所在鄰域的整體灰度值是不同的。由此可見，利用物理力學(xué)中的胡可定律計算像素點所受到的合力并以此作為判定邊緣的根據(jù)會引起誤判，從而采用彈簧質(zhì)點模型邊緣檢測算法所檢測到的邊緣較粗。為充分利用鄰域的整體性質(zhì)并考慮鄰域內(nèi)的整體灰度情況，本文將像素點所受合力的計算公式改為F=（X-+X（i，j））F2x+F2y，其中X-為鄰域內(nèi)灰度均值。以此合力作為判定像素點（i，j）是否為邊緣的依據(jù)，實驗顯示該方法可以得到較細(xì)的像素邊緣。

2.2 數(shù)學(xué)形態(tài)學(xué)細(xì)化原理

對于一些復(fù)雜的真實圖像，只采用上述改進(jìn)并不能有效進(jìn)行邊緣細(xì)化。而數(shù)學(xué)形態(tài)學(xué)是一種研究數(shù)字圖像形態(tài)結(jié)構(gòu)特征與快速并行處理的方法，它算法簡單、速度快、可并行處理、易于硬件實現(xiàn)[6]。

數(shù)學(xué)形態(tài)學(xué)中最基本的運(yùn)算是腐蝕和膨脹。主要進(jìn)行集合相關(guān)的運(yùn)算。下面介紹數(shù)學(xué)形態(tài)學(xué)的基本概念和運(yùn)算。

設(shè)Ω為二維歐幾里得空間，圖像A是Ω的一個子集，結(jié)構(gòu)元素B也是Ω的一個子集，b∈Ω是歐氏空間的一個點，定義如下幾個概念。

（1）平移：

Ab=a+ba∈A（10）

Ab表示圖像A被b平移后的結(jié)果，即Ab中所有元素是A中的對應(yīng)元素平移到以b為原點的坐標(biāo)系內(nèi)的結(jié)果。

（2）反射：

A～=-aa∈A（11）

A～表示圖像A對于圖像原點反射的結(jié)果。

（3）膨脹（dilation）的運(yùn)算定義式為：

AB=a+ba∈A，b∈B=∪Ab（12）

（4）腐蝕（erosion）的運(yùn)算定義式為：

AΘB=z∈ΩBzA=∩Ab（13）

圖像A被結(jié)構(gòu)元素B膨脹，膨脹后A形狀與結(jié)構(gòu)元素B的形狀息息相關(guān)。同樣，圖像A被結(jié)構(gòu)元素B腐蝕，腐蝕的結(jié)果與結(jié)構(gòu)元素B的選取有關(guān)。因此，選取不同的結(jié)構(gòu)元素B做膨脹或腐蝕運(yùn)算后所得的結(jié)果可能截然不同。

在定義腐蝕和膨脹運(yùn)算的基礎(chǔ)上，再定義另外兩個常用運(yùn)算：開運(yùn)算（opening）和閉運(yùn)算（clothing）。

①開運(yùn)算：A對B的開運(yùn)算的結(jié)果定義為：

A°B=（AΘB）B（14）

即A先被B腐蝕，再被B膨脹的結(jié)果。

②閉運(yùn)算：A對B的閉運(yùn)算定義為：

A·B=（AB）ΘB（15）

即A先被B膨脹，其結(jié)果再被B腐蝕。它與開運(yùn)算正好相反。依據(jù)開運(yùn)算和閉運(yùn)算的特征，一般可以運(yùn)用開運(yùn)算刪除圖像中的小分支，運(yùn)用閉運(yùn)算填補(bǔ)圖像中的空穴。

形態(tài)學(xué)還有一種稱為擊中擊不中的變換，它被廣泛應(yīng)用在保持拓?fù)浣Y(jié)構(gòu)的形狀細(xì)化與修剪、形狀識別和目標(biāo)定位等方面。

（5）擊中擊不中變換：假設(shè)B由兩個不相交的部分B1和B2組成，即B滿足B=B1∪B2且B1∩B2=，則A被B擊中定義為：

AB=x（B1）xA，（B2）xAc（16）

細(xì)化一般是指用一條曲線代表一個具有一定面積的區(qū)域，而擊中擊不中變換是數(shù)學(xué)形態(tài)學(xué)細(xì)化算法的關(guān)鍵環(huán)節(jié)：對給定一系列具有一定形狀的結(jié)構(gòu)元素后，順序循環(huán)地刪除滿足擊中變換的像素。

于是，圖像A被結(jié)構(gòu)元素B細(xì)化的定義為：

AB=A-（AB）=A∩（AB）c（17）

即AB為在A中去掉A被B擊中的結(jié)果。那么A被結(jié)構(gòu)元素序列細(xì)化的定義為：

AB=（（…（（AB`1）B2）…）Bn（18）

其中，B=B1，B2，…，Bn為一個結(jié)構(gòu)元素序列，Bi是Bi-1的旋轉(zhuǎn)。以上細(xì)化過程可以描述為：先用B1細(xì)化一遍，再用B2對B1的結(jié)果進(jìn)行迭代細(xì)化，如此反復(fù)，直到Bn。整個過程可以繼續(xù)重復(fù)到?jīng)]有變化為止。另外，由于細(xì)化是有方向性的且需要更為對稱地進(jìn)行，因此本文選擇的是八個方向的結(jié)構(gòu)元素序列，如圖2。

圖2中，B1，B3，B5，B7，B2，B4，B6，B8是用來對稱地去掉南、西、北、東、西南、西北、東北、東南八個方向上的點?！皁”點方格表示參考中心點;“1”方格表示目標(biāo)圖像上的點;“0”方格表示背景圖像上的點;“*”表示既可以是目標(biāo)上的點，也可以是背景上的點。

因此，式（18）就被定義為：

ABm=（（…（（AB1）B2）…）B8）m（19）

式中，m是進(jìn)行圖像細(xì)化收斂時的總循環(huán)次數(shù)，它的結(jié)果由目標(biāo)圖像的大小和邊緣粗細(xì)決定[7]。

2.3 算法描述

以下是本文給出的改進(jìn)的彈簧質(zhì)點模型邊緣檢測算法過程：

（1）輸入原圖像，對所有鄰域內(nèi)中心像素點用改進(jìn)的算法分別計算其所受x軸、y軸方向的分力，并求出其合力大小及方向;

（2）選取一個合適的閾值，對圖像中各像素點進(jìn)行二值化，合力大小大于閾值的像素點判為邊緣點，否則為非邊緣點;

（3）對所得到的邊緣圖像運(yùn)用數(shù)學(xué)形態(tài)學(xué)細(xì)化邊緣;

（4）輸出最終邊緣圖像。

3 實驗結(jié)果及分析

本文使用合成圖像和真實圖像進(jìn)行實驗，并且與效果較好的LoG算子、Canny算子以及原彈簧質(zhì)點模型檢測算法進(jìn)行比較。其中，對合成圖像的檢測性能用定量的邊緣檢測品質(zhì)因子分析各算法的優(yōu)劣，真實圖像則通過視覺效果判斷各算法檢測效果。

3.1 合成圖的檢測結(jié)果

圖3顯示了無噪合成圖像的各算法邊緣檢測結(jié)果。

（a）原始合成圖像

（b）LoG算子（c）Canny算子

（d）原彈簧模型算法（e）本文方法

從上圖可以看出，本文方法較于其他方法不僅可以檢測到單像素邊緣，而且能夠準(zhǔn)確檢測出邊緣的位置。

目前盡管沒有較統(tǒng)一權(quán)威的判別依據(jù)來確定不同邊緣檢測方法的性能，但區(qū)分從檢測方法中獲得的主要信息和輔助性信息幫助我們判定一個邊緣檢測方法的性能的好壞。這些信息包括邊緣像素點的位置、邊緣的高度和斜面傾角及其在空間中的方位等。

此外，邊緣判定的可靠性因子可以用來刻畫實際擬合邊緣與理想邊緣之間的接近程度。邊緣檢測過程中，三種類型的誤差會造成邊緣的錯誤檢測，分別為：（1）邊緣點丟失，（2）邊緣點定位失效，（3）將噪聲波動誤認(rèn)為是邊緣點。于是可以用真實邊緣檢測的概率來描述邊緣檢測的性能，該概率可以通過對理想邊緣檢測器和實際邊緣檢測器檢測到的邊緣圖形進(jìn)行比較來進(jìn)行估計。在此基礎(chǔ)上，Pratt提出了品質(zhì)因子來判定邊緣檢測器的性能。品質(zhì)因子的定義式為：

R=1IN∑IAi=111+ad2（20）

式中，IN=MAXII，IA，II和IA表示理想和實際邊緣圖形點的數(shù)量。a是一個比例常數(shù)，d為實際邊緣點到理想邊緣點連線的垂直距離。R值越大，表示邊緣定位精度越高，邊緣檢測性能就越好[89]。下表給出了各算法的品質(zhì)因數(shù)。

由上表可以看出，本文對于合成圖像的邊緣檢測效果要優(yōu)于其他算法。

3.2 真實圖像的邊緣檢測結(jié)果

對真實圖像進(jìn)行各算法的邊緣檢測結(jié)果，如圖4所示。

（a）原圖像（b）加噪圖像

（c）LoG原圖像檢測（d）LoG含噪圖像檢測

（e）Canny原圖像檢測（f）Canny含噪圖像檢測

（g）原方法原圖像檢測（h）原方法含噪圖像檢測

（m）本文方法原圖像檢測（n）本文方法含噪圖像檢測

在圖4中，左列各圖是無噪情況下邊緣檢測的情況，右列是對圖像加了一定強(qiáng)度的高斯噪聲后各算法邊緣檢測的結(jié)果。在無噪聲的情況下，原彈簧質(zhì)點模型邊緣檢測算法檢測出的邊緣很明顯較粗;LoG算子和Canny算子圖像邊緣檢測的邊緣雖然較精細(xì)，但它們均檢測出了一些偽邊緣，丟失了很多重要的細(xì)節(jié)信息，從而導(dǎo)致檢測圖像并不能很好的反映圖像本身的特征，也就失去了邊緣檢測的意義。在加入高斯噪聲的圖像檢測中，由于LoG算子和Canny算子本身具有高斯濾波器平滑噪聲的作用，檢測后的圖像中噪聲較少，但由于高斯濾波器過度平滑噪聲，很多邊緣信息也被平滑掉，檢測出來的結(jié)果很不真實，失去了很多反映結(jié)構(gòu)特征的邊緣信息;原彈簧質(zhì)點模型檢測算法檢測出的結(jié)果仍然存在檢測不精細(xì)的缺點，雖然較Canny算法能夠提取出圖像的邊緣信息，可是由于受到噪聲的影響，破壞了檢測性能。本文方法無論是對原圖像還是含噪聲圖像，檢測出的邊緣信息清晰，邊緣的連續(xù)性也較好，很好地反映圖像的重要特征，同時也有一定的濾波效果，綜合考慮，本文算法相比其他算法有了很大的改善。

4 結(jié)語

針對原彈簧質(zhì)點模型邊緣檢測算法檢測到的邊緣較粗的弊端，本文提出了一種改進(jìn)的彈簧質(zhì)點模型邊緣檢測算法，算法中將鄰域灰度均值與該鄰域中心像素灰度值之和作為因子考慮到所求合力中，檢測到的邊緣更加精細(xì)，再將數(shù)學(xué)形態(tài)學(xué)應(yīng)用到該算法中細(xì)化邊緣，通過實驗表明改進(jìn)后的算法在邊緣檢測的性能上有了很大的改善。

參考文獻(xiàn)：

[1]Richard EWoods，Steven L.Eddins.數(shù)字圖像處理[M].電子工業(yè)出版社，2008.

[2]SUN Genyun，LIU Qinhuo，LIN Qian.A novel approach for edgedetectionbased on the theory of universal gravity[J].PatternRecognition，2007，40（10）：27662775.

[3]徐遙，張如艷，王世同.一種新的基于改進(jìn)彈簧質(zhì)點模型的圖像邊緣檢測算法[J].計算機(jī)應(yīng)用研究，2011，28（4）：15731576.

[4]龔永義，羅笑南，賈維嘉，等.基于改進(jìn)的彈簧質(zhì)子模型的醫(yī)學(xué)圖像配準(zhǔn)[J].計算機(jī)學(xué)報，2008，31（7）：12241233.

[5]滿利紅，王士同.應(yīng)用改進(jìn)的彈簧質(zhì)點模型進(jìn)行圖像濾波的算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（11）：16181623.

[6]何新英，王家忠，孫晨霞，常淑惠，周桂紅.基于數(shù)學(xué)形態(tài)學(xué)和Canny算子的邊緣提取方法[J].計算機(jī)應(yīng)用，2008，28（2）：477479.

[7]崔屹.圖像處理與分析——數(shù)學(xué)形態(tài)學(xué)方法及應(yīng)用[M].北京：科學(xué)出版社，2002.1.

[8]I.Abdou.Quantitative Methods of Edge Detection[R].USCIPI Report 830，Image Processing Institute，University of Southern California，Los Angeles，1973.

[9]I.E.AdouW.K.Pratt.Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors[J].Proc.IEEE1979：753763.