基于粒子群三次樣條優(yōu)化的圖像邊緣描述算法

公亞利, 林意

江南大學數(shù)字媒體學院,江蘇 無錫 214122

Gong YaLi , Lin Yi

School of Digital Media, Jiangnan University, Wuxi 214122，China

1.引 言

在圖像研究和應用中，人們一般只對圖像中的某些部分感興趣，這些部分對應圖像中特定的、具有獨特性質的區(qū)域，一般稱之為目標。為了辨識和分析目標，需要將這些區(qū)域分離出來，在此基礎上才有能對目標區(qū)域進一步應用[1]。而要分離這些區(qū)域，首先要得到圖像區(qū)域的邊緣。圖像區(qū)域邊緣不僅能夠勾畫出目標輪廓,使觀察者一目了然，而且蘊含豐富的內(nèi)在信息。因此，圖像目標邊緣檢測技術被廣泛研究并在不同的領域應用。

一般的邊緣檢測算法中，圖像邊緣以離散點集的形式給出，受噪聲的影響較大，檢測結果不可靠，無法準確判定邊緣是否存在，也無法給出其準確位置，不利于區(qū)域的形狀描述及應用。相比較而言，邊緣表達式要簡單得多。該方法先通過指定少量的型值點來定義一個大概的曲線輪廓，然后利用樣條曲線來擬合選定的型值點，就可以得到大致的圖像邊緣。

邊緣表達式即可以克服圖像邊緣點集數(shù)據(jù)量大的缺點，又能很好反應邊緣的一些形態(tài)和拓撲結構，同時還克服了鏈碼、多邊形的粗糙性[1]。

三次參數(shù)樣條曲線方程可以作為邊緣表達式來描述圖像邊緣。但從實驗中發(fā)現(xiàn)，手工選點擬合生成的三次參數(shù)樣條曲線與圖像邊緣點集的一致性較差。雖然有較高的逼近度，但不能很好地貼合邊緣點集。主要表現(xiàn)在曲線與邊緣點集的交叉很多，導致曲線對應的邊緣點集失去了其實際應用價值。針對這一問題，通過深入研究粒子群算法[2-3]，發(fā)現(xiàn)該算法具有個體數(shù)目少、計算簡單、收斂速度快等特點，可以用于描述圖像邊緣的三次參數(shù)樣條曲線的優(yōu)化。因此，本文利用粒子群算法來優(yōu)化三次參數(shù)樣條曲線，通過優(yōu)化三次參數(shù)樣條曲線的型值點，使優(yōu)化之后的樣條曲線形態(tài)和邊緣輪廓一致，對邊緣有較好的貼合。其核心思想是通過利用粒子群算法搜索樣條曲線的新型值點[4]，然后用邊緣檢測算子[5]來評估經(jīng)過調(diào)整的型值點，調(diào)整粒子群算法搜索的方向。不斷地進行迭代搜索，最終得到一組型值點，使用該組型值點擬合出的樣條曲線可以較好的貼合圖像邊緣。實驗表明該算法能夠快速擬合曲線，且擬合得到的曲線平滑貼合圖像邊緣。

2.構造樣條曲線

本節(jié)介紹本文構造樣條曲線函數(shù)的方法。

首先，在圖像區(qū)域的邊緣上取一組外型曲線的型值點列向量 Vj=(xj, yj)(j=0,1,…,n)，然后通過該組型值點構造三次參數(shù)樣條參數(shù)插值曲線[6-9]，所求三次參數(shù)樣條曲線 r(t)=(x(t),y(t))，向量 r(t)符合 ：

參數(shù)t取累加弦長，即：t0=0,t1=|V1-V0|,…,tn=tn-1+|Vn-Vn-1|，在分Δ:t0≤t1≤t2≤t3≤t4…≤tn-2≤tn-1≤tn上作三次樣條參數(shù)曲線。由(1)式知，x(t)和 y(t)的形式相同，故僅給出x(t)的構造過程。

設型值點Vj的切向量mj=(mxj,myj)T已知。將xj-1,xj,mxj-1,mxj代入x(t)得到：

又由于三次參數(shù)樣條曲線在整個區(qū)間上C2連續(xù)，即xj-1(t), xj(t)在t=tj處二階導數(shù)連續(xù)，即：

由式(4)可推得：

其中 ：

該方程組是關于未知數(shù)m0,m1,…,mn的n-1個方程，需添加兩個邊界條件：

其中，邊界條件為手工設定。聯(lián)立式(5)、(6)可以求出mxj(j=1,…,n-1)，將其代入(3)求出參數(shù)曲線x(t)。同理，可以求出y(t)。

3.粒子群算法

本文把圖像邊緣樣條曲線優(yōu)化看作是在三次樣條空間中搜索最佳型值點的過程。

在使用粒子群算法[10-12]對三次樣條曲線進行優(yōu)化之前，首先需要建立粒子。

設樣條曲線中有n個型值點，則整條曲線中共有(n-1)條樣條曲線段。由式(5)可知每條曲線段均由其兩端的兩個型值點決定。首尾型值點包含有邊界切向量的信息，因此在構造過程中除去首尾型值點。仿照文獻[11]建立了于三次參數(shù)樣條曲線優(yōu)化的2(n-2)維粒子L，用向量表示為：

在搜索過程中，每個粒子都有一個2(n-2)維的速度向量 v=＜v1, v2, v3, v4, v5,…,v2n-1,v2n-2＞，其中，vi(i=1,2,3,…,2 n-1,2 n -2)為每個維度上的速度分量，在粒子初始化時被隨機賦值為介于MAX_SPEED和MIN_SPEED之間的一個值。

MAX_SPEED和MIN_SPEED為算法輸入變量，其限制了粒子群在一次搜索時運動速度的范圍。

在迭代過程中，粒子根據(jù)兩個極值來更新自己。第一個為粒子本身找到的最優(yōu)解，稱為個體極值，即 Pbesti；第二個極值為整個種群目前找到的最優(yōu)解，稱為全局極值，即Gbesti。粒子根據(jù)這兩個極值來更新自己。

三次樣條參數(shù)曲線中，對一個型值點的調(diào)整對它相鄰兩個型值點的影響最大，對其余型值點的影響迅速減小。針對這個特點，對粒子群算法的速度公式進行了修改，引入了影響因子，用來描述某個型值點受到其左右兩個型值點變化的影響。經(jīng)過修改的速度公式如下：

該式用來計算某個速度的各個速度分量，其中vi表示速度的第i個分量；Li表示粒子的第i個分量； ω表示慣性權重；c1，c2為學習因子； r1和r2為兩個均勻分布在(0,1)之間的隨機數(shù)； n1，n2為鄰型值點影響因子，n1表示速度分量受到左型值點影響的影響因子，n2表示速度分量受到右型值點影響的影響因子； vl,vr分別表示左型值點的速度分量和右型值點的速度分量。

4 適應度函數(shù)

本文將三次樣條曲線用于圖像邊緣提取，因此評價擬合之后的樣條曲線的好壞最重要的依據(jù)就是擬合之后的樣條曲線是否貼近被提取圖形的邊緣。所以本文使用典型的邊緣檢測算子來對生成的曲線進行評價。

4.1 圖像邊緣檢測算法

邊緣檢測的基本算法有很多,如梯度算子、方向算子、拉普拉斯算子和坎尼(Canny)算子等等。常用的邊緣檢測方法則有Roberts算子、Sobel算子和Prewitt算子、高斯偏導濾波器(LOG)以及Canny邊緣檢測器等。常用的邊緣檢測算子[13-14]中比較優(yōu)秀的是Canny算子。但由于該算子在使用之前需要將圖形高斯化，使用起來比較復雜，因此本文使用Sobel算子來對曲線進行評價。

Sobel算子是一階導數(shù)的邊緣檢測算子。在算法實現(xiàn)過程中，通過3×3模板作為核與圖像中的每個像素點做卷積和運算，然后選取合適的閾值以提取邊緣。采用3×3鄰域可以避免在像素之間內(nèi)插點上計算梯度。即：

(a)圖像鄰域模板

Sobel算子也是一種梯度幅值，即：

其中偏導數(shù)Sx 和Sy可用卷積模板來實現(xiàn)，即：

Sobel算子算法的優(yōu)點是計算簡單，速度快。因此，為了檢測特定方向上的邊緣，減少噪聲點的影響，本文采用不同方向的Sobel算子模板如下所示：

(b)Sobel算子模板

圖像中的每個像素點均用(b)中的四個核做卷積，將四個卷積核的最大值作為該點的輸出值。

4.2 適應度函數(shù)的選取

適應度函數(shù)用來對樣條曲線進行評價。本文使用圖像邊緣檢測中典型的Sobel算子為基礎編寫適應度函數(shù)。評價好壞的依據(jù)就是擬合之后的樣條曲線是否貼合被提取的圖像邊緣。評價過程分為三個層次:

(1)粒子的比較。首先分別抽取當前粒子中的參數(shù)和對比粒子中的參數(shù)來擬合兩條曲線，然后通過比較這兩條曲線的優(yōu)劣來判斷粒子的優(yōu)劣。

(2)擬合曲線的比較。通過比較曲線上各個擬合點的優(yōu)劣來得出的，擁有更多比較中占優(yōu)的擬合點的曲線更加優(yōu)秀。

(3)擬合點的比較。通過比較擬合點的圖像邊緣檢測算子卷積的大小來判斷，卷積大的，對應的擬合點就更優(yōu)秀。

擬合點的比較決定曲線比較的結果，曲線比較的結果又會決定粒子比較的結果。最終得出哪個粒子更優(yōu)秀，更加優(yōu)秀的粒子意味著該粒子對應的擬合曲線更貼近圖像邊緣。更加優(yōu)秀的粒子會被用來更新 Pbesti和 Gbesti。

5.算例

本文為了驗證上文中給出的優(yōu)化算法，分別給出了固定粒子規(guī)模、變化迭代次數(shù)和固定迭代次數(shù)、變化粒子規(guī)模的兩個算例。

5.1 粒子規(guī)模固定，迭代次數(shù)變化

首先，選擇4個型值點，擬合優(yōu)化前的三次參數(shù)樣條曲線(a)(黑色點為型值點，黑色實曲線為優(yōu)化前的三次參數(shù)樣條曲線)。然后將粒子規(guī)模固定為10，迭代次數(shù)分別為10、15、20次，擬合的三次參數(shù)樣條曲線分別是(b)、(c)、(d)(黑色虛線為優(yōu)化后的三次參數(shù)曲線），其不同參數(shù)的迭代次數(shù)效果對比圖如圖1所示：

圖1 不同參數(shù)的效果圖Fig.1 The effect of different parameters

圖1中三次參數(shù)樣條曲線在優(yōu)化前后的曲率對比如圖2所示：

圖2 曲率對比圖Fig.2 Curvature effect drawing

如圖1所示，(a)優(yōu)化前擬合的三次參數(shù)樣條曲線，其首尾型值點附近的曲線段偏向于圖像區(qū)域邊緣外側，中間的曲線段偏向于圖像區(qū)域邊緣內(nèi)側。依據(jù)優(yōu)化后的曲線段要更加貼合圖像邊緣的要求，曲線的變化趨勢應該是兩側曲線曲率變小，中間部分的曲率變大。如圖2所示，優(yōu)化前后曲線的曲率變化趨勢大體上符合上述推測。優(yōu)化后的曲線更平滑、更貼近圖像區(qū)域邊緣。因此，在粒子規(guī)模固定的情況下，隨著迭代次數(shù)的增加，粒子群搜索結果擬合的曲線越來越貼合圖像邊界。

5.2 迭代次數(shù)固定，粒子規(guī)模變化

首先，選擇了4個型值點，擬合優(yōu)化前的曲線(e)(黑色點為型值點，黑色實曲線為優(yōu)化前的三次參數(shù)樣條曲線)。然后將迭代次數(shù)固定為10，粒子規(guī)模分別為10、15、20個，擬合的三次參數(shù)樣條曲線分別是(f)、(g)、(h)(黑色虛線為優(yōu)化后的三次參數(shù)樣條曲線)，其不同參數(shù)的迭代效果對比如圖3所示:

圖3 不同參數(shù)的效果圖Fig.3 The effect of different parameters

圖3中的三次參數(shù)樣條曲線在優(yōu)化前后的曲率對比如圖4所示：

圖4 曲率對比圖Fig.4 Curvature contrast diagram

如圖3所示，(e)優(yōu)化前擬合的三次參數(shù)樣條曲線，其首尾型值點附近的曲線段偏向于圖像區(qū)域邊緣外側，中間的曲線段偏向于圖像區(qū)域邊緣內(nèi)側。依據(jù)優(yōu)化后的曲線段要更加貼合圖像邊緣的要求，曲線的變化趨勢應該是兩側曲線曲率變小，中間部分的曲率變大。如圖4所示，優(yōu)化前后三次參數(shù)曲線的曲率變化趨勢大體上符合上述推測。優(yōu)化后的曲線更平滑、更貼近圖像區(qū)域邊緣。因此，在迭代次數(shù)固定的情況下，隨著粒子群規(guī)模的增加，粒子群搜索結果擬合的曲線越來越貼合圖像邊界。

6.結束語

本文利用粒子群算法結合邊緣檢測算子優(yōu)化手工選點生成的三次參數(shù)樣條曲線，在手工確定邊界切向量的情況下，利用粒子群算法修改插值曲線的型值點，以邊緣檢測算子為基礎形成評價函數(shù)，并用其評估優(yōu)化之后的曲線。實驗表明，優(yōu)化后的樣條曲線既能較好地逼近區(qū)域邊緣又能夠達到平滑的效果，并對圖像邊緣有很好地貼合，能夠用于對圖像邊緣的描述。由于粒子群規(guī)模和迭代的次數(shù)對圖像邊緣的貼合有直接的影響，當粒子群規(guī)模和迭代次數(shù)很大時，優(yōu)化速度較慢。另外，型值點的個數(shù)對圖像邊緣曲線的擬合也有影響。這些都有待于進一步的研究。

Reference)

[1]林意，吳錫生.一種圖像區(qū)域邊緣表達方法[J].重慶大學學報，2006，29(7)：77-80.

[2]楊 維, 李歧強.粒子群優(yōu)化算法綜述[J].中國工程科學，2004，6(5)：87-94

[3]李愛國，覃 征，鮑復民等.粒子群優(yōu)化算法[J]，計算機工程與應用，2002，(21):1-3,17

[4]Huaiping Yang,Wenping Wang,Jiaguang Sun.Control point adjustment for B-spline curve approximation[J].Computer-Aided Design,2004,(36),,639-652

[5]沈麗容.圖像邊緣檢測算法比較研究[J].福建電腦，2011，(5)：5-9

[6]王仁宏，李崇君，朱春鋼.計算幾何教程[M].北京：科學出版社，2008：48-60.

[7]方逵，張啟松，李建平.計算機輔助幾何設計[M].河北：河北教育出版社，1994：29-49.

[8]孫家廣，楊長貴.計算機圖形學(新版)[M].北京：清華大學出版社，1997：284-294.

[9]葉康倫.樣條應用與曲線光順[J].廣船科技，2003，(1)：11-25

[10]Russell C.Eberhart, Yuhui Shi.Particle Swarm Optimization:Developments,Applications and Resource[J].Evolutionary omputation,2001,(1),81-86

[11]權國通，譚 超，侯海潮等.基于粒子群三次樣條優(yōu)化的采煤機截割路徑規(guī)劃[J].煤炭科學技術，2011，39(3)：77-79

[12]吳憲祥，郭寶龍，王 娟.基于粒子群三次樣條優(yōu)化的移動機器人路徑規(guī)劃算法[J].機器人，2009，31(6)：556-560

[13]譚 艷，王宇俊，李飛龍等.幾種典型的圖象邊緣檢測算法的分析比較[J].電腦知識與技術，2012,8(7)：1604-1608

[14]趙來剛，陳道炯.一種基于 Sobel算子的新型邊緣提取算法[J].機械與電子，2011,(2):59-61