基于彈簧質點模型邊緣檢測算法的改進

戚曉偉

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

關鍵詞：邊緣檢測;彈簧質點模型;數學形態學;細化邊緣

中圖分類號：TP391.41;TP751文獻標識碼：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

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

1 彈簧質點模型邊緣檢測算法原理

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

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

Fin=FS+FC+FB（1）

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

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

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

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

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

在圖像的3×3鄰域內，對于圖像中的每個像素點，通過來自其周圍像素點的彈簧拉力的合力大小判定它是否是邊緣上的點。中心像素點假設為（i，j），鄰域內其他像素點記為（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）設置一個合適的閾值T，如果某像素點所受合力大于這個閾值，可以認為這個像素點為邊緣點。

2 改進的彈簧質點模型邊緣檢測算法

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

2.1 合力算法的分析及改善

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

在圖1中，假設鄰域內水平或垂直的兩像素點間的歐氏距離設為a，那么對角的兩像素點間的距離為2a，為方便計算，這里設定彈簧系數為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所在鄰域的整體灰度值是不同的。由此可見，利用物理力學中的胡可定律計算像素點所受到的合力并以此作為判定邊緣的根據會引起誤判，從而采用彈簧質點模型邊緣檢測算法所檢測到的邊緣較粗。為充分利用鄰域的整體性質并考慮鄰域內的整體灰度情況，本文將像素點所受合力的計算公式改為F=（X-+X（i，j））F2x+F2y，其中X-為鄰域內灰度均值。以此合力作為判定像素點（i，j）是否為邊緣的依據，實驗顯示該方法可以得到較細的像素邊緣。

2.2 數學形態學細化原理

對于一些復雜的真實圖像，只采用上述改進并不能有效進行邊緣細化。而數學形態學是一種研究數字圖像形態結構特征與快速并行處理的方法，它算法簡單、速度快、可并行處理、易于硬件實現[6]。

數學形態學中最基本的運算是腐蝕和膨脹。主要進行集合相關的運算。下面介紹數學形態學的基本概念和運算。

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

（1）平移：

Ab=a+ba∈A（10）

Ab表示圖像A被b平移后的結果，即Ab中所有元素是A中的對應元素平移到以b為原點的坐標系內的結果。

（2）反射：

A～=-aa∈A（11）

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

（3）膨脹（dilation）的運算定義式為：

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

（4）腐蝕（erosion）的運算定義式為：

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

圖像A被結構元素B膨脹，膨脹后A形狀與結構元素B的形狀息息相關。同樣，圖像A被結構元素B腐蝕，腐蝕的結果與結構元素B的選取有關。因此，選取不同的結構元素B做膨脹或腐蝕運算后所得的結果可能截然不同。

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

①開運算：A對B的開運算的結果定義為：

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

即A先被B腐蝕，再被B膨脹的結果。

②閉運算：A對B的閉運算定義為：

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

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

形態學還有一種稱為擊中擊不中的變換，它被廣泛應用在保持拓撲結構的形狀細化與修剪、形狀識別和目標定位等方面。

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

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

細化一般是指用一條曲線代表一個具有一定面積的區域，而擊中擊不中變換是數學形態學細化算法的關鍵環節：對給定一系列具有一定形狀的結構元素后，順序循環地刪除滿足擊中變換的像素。

于是，圖像A被結構元素B細化的定義為：

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

即AB為在A中去掉A被B擊中的結果。那么A被結構元素序列細化的定義為：

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

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

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

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

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

式中，m是進行圖像細化收斂時的總循環次數，它的結果由目標圖像的大小和邊緣粗細決定[7]。

2.3 算法描述

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

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

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

（3）對所得到的邊緣圖像運用數學形態學細化邊緣;

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

3 實驗結果及分析

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

3.1 合成圖的檢測結果

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

（a）原始合成圖像

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

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

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

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

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

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

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

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

3.2 真實圖像的邊緣檢測結果

對真實圖像進行各算法的邊緣檢測結果，如圖4所示。

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

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

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

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

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

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

4 結語

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

參考文獻：

[1]Richard EWoods，Steven L.Eddins.數字圖像處理[M].電子工業出版社，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].計算機應用研究，2011，28（4）：15731576.

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

[5]滿利紅，王士同.應用改進的彈簧質點模型進行圖像濾波的算法[J].計算機輔助設計與圖形學學報，2009，21（11）：16181623.

[6]何新英，王家忠，孫晨霞，常淑惠，周桂紅.基于數學形態學和Canny算子的邊緣提取方法[J].計算機應用，2008，28（2）：477479.

[7]崔屹.圖像處理與分析——數學形態學方法及應用[M].北京：科學出版社，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.