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

公亞利, 林意

江南大學數字媒體學院,江蘇 無錫 214122

Gong YaLi , Lin Yi

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

1.引 言

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

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

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

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

2.構造樣條曲線

本節介紹本文構造樣條曲線函數的方法。

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

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

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

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

由式(4)可推得：

其中 ：

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

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

3.粒子群算法

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

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

設樣條曲線中有n個型值點，則整條曲線中共有(n-1)條樣條曲線段。由式(5)可知每條曲線段均由其兩端的兩個型值點決定。首尾型值點包含有邊界切向量的信息，因此在構造過程中除去首尾型值點。仿照文獻[11]建立了于三次參數樣條曲線優化的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為算法輸入變量，其限制了粒子群在一次搜索時運動速度的范圍。

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

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

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

4 適應度函數

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

4.1 圖像邊緣檢測算法

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

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

(a)圖像鄰域模板

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

其中偏導數Sx 和Sy可用卷積模板來實現，即：

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

(b)Sobel算子模板

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

4.2 適應度函數的選取

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

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

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

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

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

5.算例

本文為了驗證上文中給出的優化算法，分別給出了固定粒子規模、變化迭代次數和固定迭代次數、變化粒子規模的兩個算例。

5.1 粒子規模固定，迭代次數變化

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

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

圖1中三次參數樣條曲線在優化前后的曲率對比如圖2所示：

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

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

5.2 迭代次數固定，粒子規模變化

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

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

圖3中的三次參數樣條曲線在優化前后的曲率對比如圖4所示：

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

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

6.結束語

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

Reference)

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

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

[3]李愛國，覃 征，鮑復民等.粒子群優化算法[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]權國通，譚 超，侯海潮等.基于粒子群三次樣條優化的采煤機截割路徑規劃[J].煤炭科學技術，2011，39(3)：77-79

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

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

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