公亞利, 林意

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

Gong YaLi , Lin Yi

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

1.引 言

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

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

邊緣表達(dá)式即可以克服圖像邊緣點(diǎn)集數(shù)據(jù)量大的缺點(diǎn)，又能很好反應(yīng)邊緣的一些形態(tài)和拓?fù)浣Y(jié)構(gòu)，同時(shí)還克服了鏈碼、多邊形的粗糙性[1]。

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

2.構(gòu)造樣條曲線(xiàn)

本節(jié)介紹本文構(gòu)造樣條曲線(xiàn)函數(shù)的方法。

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

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

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

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

由式(4)可推得：

其中 ：

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

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

3.粒子群算法

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

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

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

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

MAX_SPEED和MIN_SPEED為算法輸入變量，其限制了粒子群在一次搜索時(shí)運(yùn)動(dòng)速度的范圍。

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

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

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

4 適應(yīng)度函數(shù)

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

4.1 圖像邊緣檢測(cè)算法

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

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

(a)圖像鄰域模板

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

其中偏導(dǎo)數(shù)Sx 和Sy可用卷積模板來(lái)實(shí)現(xiàn)，即：

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

(b)Sobel算子模板

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

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

適應(yīng)度函數(shù)用來(lái)對(duì)樣條曲線(xiàn)進(jìn)行評(píng)價(jià)。本文使用圖像邊緣檢測(cè)中典型的Sobel算子為基礎(chǔ)編寫(xiě)適應(yīng)度函數(shù)。評(píng)價(jià)好壞的依據(jù)就是擬合之后的樣條曲線(xiàn)是否貼合被提取的圖像邊緣。評(píng)價(jià)過(guò)程分為三個(gè)層次:

(1)粒子的比較。首先分別抽取當(dāng)前粒子中的參數(shù)和對(duì)比粒子中的參數(shù)來(lái)擬合兩條曲線(xiàn)，然后通過(guò)比較這兩條曲線(xiàn)的優(yōu)劣來(lái)判斷粒子的優(yōu)劣。

(2)擬合曲線(xiàn)的比較。通過(guò)比較曲線(xiàn)上各個(gè)擬合點(diǎn)的優(yōu)劣來(lái)得出的，擁有更多比較中占優(yōu)的擬合點(diǎn)的曲線(xiàn)更加優(yōu)秀。

(3)擬合點(diǎn)的比較。通過(guò)比較擬合點(diǎn)的圖像邊緣檢測(cè)算子卷積的大小來(lái)判斷，卷積大的，對(duì)應(yīng)的擬合點(diǎn)就更優(yōu)秀。

擬合點(diǎn)的比較決定曲線(xiàn)比較的結(jié)果，曲線(xiàn)比較的結(jié)果又會(huì)決定粒子比較的結(jié)果。最終得出哪個(gè)粒子更優(yōu)秀，更加優(yōu)秀的粒子意味著該粒子對(duì)應(yīng)的擬合曲線(xiàn)更貼近圖像邊緣。更加優(yōu)秀的粒子會(huì)被用來(lái)更新 Pbesti和 Gbesti。

5.算例

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

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

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

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

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

圖2 曲率對(duì)比圖Fig.2 Curvature effect drawing

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

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

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

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

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

圖4 曲率對(duì)比圖Fig.4 Curvature contrast diagram

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

6.結(jié)束語(yǔ)

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

Reference)

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

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

[3]李?lèi)?ài)國(guó)，覃 征，鮑復(fù)民等.粒子群優(yōu)化算法[J]，計(jì)算機(jī)工程與應(yīng)用，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]沈麗容.圖像邊緣檢測(cè)算法比較研究[J].福建電腦，2011，(5)：5-9

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

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

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

[9]葉康倫.樣條應(yīng)用與曲線(xiàn)光順[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]權(quán)國(guó)通，譚 超，侯海潮等.基于粒子群三次樣條優(yōu)化的采煤機(jī)截割路徑規(guī)劃[J].煤炭科學(xué)技術(shù)，2011，39(3)：77-79

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

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

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