戚曉偉

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

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

中圖分類號(hào)：TP391.41;TP751文獻(xiàn)標(biāo)識(shí)碼：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

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

1 彈簧質(zhì)點(diǎn)模型邊緣檢測(cè)算法原理

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

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

Fin=FS+FC+FB（1）

為了盡量簡(jiǎn)化過(guò)程，每個(gè)像素所受的力只考慮拉伸力FS。

原始圖像X，（x，y）處的像素灰度值為X（x，y）。我們把圖像中的各像素點(diǎn)看成彈簧模型中的質(zhì)點(diǎn)，記一個(gè)像素受到另一個(gè)像素拉力的大小和方向可以用一個(gè)矢量FM，N來(lái)表示，則根據(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)時(shí)兩個(gè)質(zhì)點(diǎn)M與N之間的自由長(zhǎng)度，即彈簧的初始長(zhǎng)度，kMN表示質(zhì)點(diǎn)間的彈簧系數(shù)，‖XN-XM‖表示兩個(gè)質(zhì)點(diǎn)M、N的歐氏距離，XM和XN表示兩質(zhì)點(diǎn)的像素灰度值[5]。

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

（1）分別計(jì)算周圍像素點(diǎn)對(duì)中心像素點(diǎn)的彈簧拉力。

對(duì)于中心像素點(diǎn)（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）處于它的對(duì)角位置，則（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）計(jì)算中心像素點(diǎn)（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）計(jì)算中心像素點(diǎn)所受合力F和方向角θ。

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

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

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

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

2.1 合力算法的分析及改善

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

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

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

從而像素點(diǎn)2所受到的合力：

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

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

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

對(duì)于一些復(fù)雜的真實(shí)圖像，只采用上述改進(jìn)并不能有效進(jìn)行邊緣細(xì)化。而數(shù)學(xué)形態(tài)學(xué)是一種研究數(shù)字圖像形態(tài)結(jié)構(gòu)特征與快速并行處理的方法，它算法簡(jiǎn)單、速度快、可并行處理、易于硬件實(shí)現(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是Ω的一個(gè)子集，結(jié)構(gòu)元素B也是Ω的一個(gè)子集，b∈Ω是歐氏空間的一個(gè)點(diǎn)，定義如下幾個(gè)概念。

（1）平移：

Ab=a+ba∈A（10）

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

（2）反射：

A～=-aa∈A（11）

A～表示圖像A對(duì)于圖像原點(diǎn)反射的結(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ǔ)上，再定義另外兩個(gè)常用運(yùn)算：開運(yùn)算（opening）和閉運(yùn)算（clothing）。

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

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

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

②閉運(yùn)算：A對(duì)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ì)化與修剪、形狀識(shí)別和目標(biāo)定位等方面。

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

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

細(xì)化一般是指用一條曲線代表一個(gè)具有一定面積的區(qū)域，而擊中擊不中變換是數(shù)學(xué)形態(tài)學(xué)細(xì)化算法的關(guān)鍵環(huán)節(jié)：對(duì)給定一系列具有一定形狀的結(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為一個(gè)結(jié)構(gòu)元素序列，Bi是Bi-1的旋轉(zhuǎn)。以上細(xì)化過(guò)程可以描述為：先用B1細(xì)化一遍，再用B2對(duì)B1的結(jié)果進(jìn)行迭代細(xì)化，如此反復(fù)，直到Bn。整個(gè)過(guò)程可以繼續(xù)重復(fù)到?jīng)]有變化為止。另外，由于細(xì)化是有方向性的且需要更為對(duì)稱地進(jìn)行，因此本文選擇的是八個(gè)方向的結(jié)構(gòu)元素序列，如圖2。

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

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

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

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

2.3 算法描述

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

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

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

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

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

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

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

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

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

（a）原始合成圖像

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

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

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

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

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

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

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

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

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

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

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

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

（e）Canny原圖像檢測(cè)（f）Canny含噪圖像檢測(cè)

（g）原方法原圖像檢測(cè)（h）原方法含噪圖像檢測(cè)

（m）本文方法原圖像檢測(cè)（n）本文方法含噪圖像檢測(cè)

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

4 結(jié)語(yǔ)

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

參考文獻(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ì)點(diǎn)模型的圖像邊緣檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（4）：15731576.

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

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

[6]何新英，王家忠，孫晨霞，常淑惠，周桂紅.基于數(shù)學(xué)形態(tài)學(xué)和Canny算子的邊緣提取方法[J].計(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.