強(qiáng) 俊

彈性粒子群算法在運(yùn)動(dòng)估計(jì)中的應(yīng)用研究

強(qiáng) 俊

針對(duì)隔行掃描到逐行掃描轉(zhuǎn)換中出現(xiàn)的運(yùn)動(dòng)圖像鋸齒現(xiàn)象和在去鋸齒過(guò)程中計(jì)算量大的問(wèn)題，對(duì)整個(gè)系統(tǒng)中運(yùn)算量最大的運(yùn)動(dòng)估計(jì)部分進(jìn)行算法改進(jìn)。通過(guò)改進(jìn)的彈性粒子群算法，得到全局最優(yōu)點(diǎn)，減少迭代次數(shù)，降低計(jì)算量并提高計(jì)算精度。試驗(yàn)證明，改進(jìn)的彈性粒子群算法對(duì)于運(yùn)動(dòng)劇烈圖像的各方面的性能都有明顯提高。

去鋸齒；運(yùn)動(dòng)估計(jì)；彈性粒子群算法

鋸齒效應(yīng)是隔行電視的一個(gè)普遍現(xiàn)象。這種現(xiàn)象是在靜止或運(yùn)動(dòng)物體的對(duì)角線斜邊會(huì)出現(xiàn)鋸齒的形狀。在進(jìn)行運(yùn)動(dòng)圖像去鋸齒的研究中，運(yùn)動(dòng)估計(jì)是系統(tǒng)中非常重要的計(jì)算模塊。如果運(yùn)動(dòng)估計(jì)算法部分運(yùn)算量過(guò)大，會(huì)影響整個(gè)系統(tǒng)的運(yùn)行效率。因此降低運(yùn)動(dòng)估計(jì)部分的運(yùn)算復(fù)雜度，減少搜索點(diǎn)數(shù)，是筆者研究的重點(diǎn)。通過(guò)對(duì)運(yùn)動(dòng)估計(jì)和粒子群算法研究后，筆者提出了在運(yùn)動(dòng)估計(jì)部分采用改進(jìn)的粒子群算法。

1 運(yùn)動(dòng)估計(jì)算法

運(yùn)動(dòng)估計(jì)是視頻壓縮領(lǐng)域中最重要的環(huán)節(jié)與研究熱點(diǎn)，其計(jì)算量占據(jù)了整個(gè)編碼過(guò)程中相當(dāng)大的比重，達(dá)到了60%～80%。如何降低計(jì)算量并保持運(yùn)動(dòng)估計(jì)的精度是各國(guó)學(xué)者多年來(lái)研究的重點(diǎn)?；趬K的運(yùn)動(dòng)估計(jì)是最常見(jiàn)的方法之一，經(jīng)典算法有全搜索(FS)、三步搜索法(TSS)[1]、四步搜索法(FSS)[2]、鉆石搜索法(DS)[3]等，該類方法采用固定的搜索模式，搜索簡(jiǎn)單，計(jì)算復(fù)雜度低，但在不同程度上容易陷入局部最優(yōu)。對(duì)小運(yùn)動(dòng)序列的運(yùn)動(dòng)估計(jì)精度較好，而對(duì)大運(yùn)動(dòng)場(chǎng)景估計(jì)精度明顯下降。對(duì)于隔行視頻中，運(yùn)動(dòng)劇烈的圖像特別容易出現(xiàn)鋸齒狀邊沿，上述算法很難滿足對(duì)該類圖像的運(yùn)動(dòng)估計(jì)精度要求。而基于遺傳算法的全局運(yùn)動(dòng)估計(jì)方法運(yùn)算精度高，但是運(yùn)算速度遠(yuǎn)低于基于塊的運(yùn)動(dòng)估計(jì)算法。為此，筆者在保證運(yùn)動(dòng)估計(jì)精度的基礎(chǔ)上又考慮到降低運(yùn)算量的要求，因而嘗試結(jié)合改進(jìn)型粒子群算法(彈性粒子群算法)來(lái)減少迭代次數(shù)，降低運(yùn)算量[4]。

2 粒子群算法

粒子群算法(PSO)是由Kennedy等在1995年提出的一種全局優(yōu)化進(jìn)化算法，源于對(duì)鳥(niǎo)類捕食行為的模擬，通過(guò)群體中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索，具有個(gè)體數(shù)目少、計(jì)算簡(jiǎn)單、魯棒性好等優(yōu)點(diǎn)，目前該算法已成功應(yīng)用于函數(shù)參數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和模糊系統(tǒng)控制等領(lǐng)域。

一個(gè)由m個(gè)粒子組成的群體在D維空間中以一定的速度飛行，每個(gè)粒子都在自己搜索到的歷史最好點(diǎn)和群體內(nèi)其他粒子的歷史最好點(diǎn)基礎(chǔ)上，進(jìn)行位置的遷移。每一個(gè)粒子i(1 ≤i≤m)在這里都會(huì)被定義3種屬性：①粒子位置向量Xi；②粒子移動(dòng)向量Vi；③在此局部范圍內(nèi)得到的最優(yōu)個(gè)體粒子的位置Li。粒子群算法步驟如下：

步1 初始化Xi和Vi，并設(shè)定在1 ≤i≤s的范圍內(nèi)，局部最優(yōu)Li=Xi。

步4 在1≤i≤m的范圍內(nèi)，粒子移動(dòng)向量Vi的優(yōu)化更新可以表示為：

Vi=wVi+c1r1(Li-Xi) +c2r2(G-Xi)

(1)

粒子的位置的優(yōu)化根據(jù)公式：

Xi=Xi+Vi

(2)

如果發(fā)現(xiàn)Xi比Li好，那么就會(huì)有：Li=Xi。

步5 重回第3步直至粒子群收斂完成。

式中，G為粒子群里當(dāng)前全局的最優(yōu)粒子；w為用來(lái)提高收斂速度的慣性因子；c1、c2分別表示自學(xué)習(xí)因子和群學(xué)習(xí)因子；r1、r2是2個(gè)處于0和1之間的隨機(jī)數(shù)。

3 基于彈性粒子群算法的運(yùn)動(dòng)估計(jì)

通過(guò)對(duì)運(yùn)動(dòng)矢量的平均分布分析，結(jié)果表明，有60%左右的矢量與預(yù)測(cè)矢量相同，絕大多數(shù)的圖像塊是靜止或準(zhǔn)靜止的。而在運(yùn)動(dòng)的圖像塊中，水平和垂直方向的運(yùn)動(dòng)要比對(duì)角線上的運(yùn)動(dòng)要多。對(duì)出現(xiàn)鋸齒效應(yīng)的運(yùn)動(dòng)圖像，從隔行到逐行的轉(zhuǎn)變過(guò)程中，奇偶行被隔一場(chǎng)抽掉一行奇場(chǎng)或偶場(chǎng)，被抽掉的部分就會(huì)成黑場(chǎng)，然后把被抽掉奇數(shù)行的偶數(shù)場(chǎng)插入被抽掉偶數(shù)行的奇數(shù)場(chǎng)，也就是兩場(chǎng)合二為一幀，而由于畫(huà)面的運(yùn)動(dòng)，后一場(chǎng)和前一場(chǎng)會(huì)有差別，兩場(chǎng)合二為一幀形成了錯(cuò)位。也就是因?yàn)樗椒较蚝痛怪狈较蛏线\(yùn)動(dòng)差異造成了視覺(jué)上對(duì)角線斜邊的鋸齒效應(yīng)，而且運(yùn)動(dòng)越劇烈，鋸齒效應(yīng)越明顯。所以不能單從對(duì)角線方向上考慮其運(yùn)動(dòng)矢量，要從水平和垂直2個(gè)方向考慮運(yùn)動(dòng)矢量的疊加，因此計(jì)算量的加大是無(wú)可避免的。利用全局運(yùn)動(dòng)估計(jì)的遺傳算法特征，結(jié)合傳統(tǒng)粒子群算法，提出以下算法，來(lái)減少迭代次數(shù)降低計(jì)算量。

圖1 初始種群交叉搜索預(yù)測(cè)

根據(jù)運(yùn)動(dòng)矢量的中心偏置特性和空間一致性，選擇一定固定點(diǎn)和隨機(jī)點(diǎn)作為算法的初始種群。筆者采用交叉搜索算法，第1步搜索是“X”字形，下一步就是“+”字形，兩者交替進(jìn)行，每次搜索的過(guò)程中調(diào)整窗口大小，初始搜索點(diǎn)數(shù)為6點(diǎn)，包含當(dāng)前中心點(diǎn)、周邊十字交叉的4個(gè)點(diǎn)及運(yùn)動(dòng)預(yù)測(cè)點(diǎn)(見(jiàn)圖1)。這樣可以更加準(zhǔn)確的確定最佳匹配點(diǎn)。需要考慮的重點(diǎn)在于粒子群何時(shí)收斂到全局最優(yōu)。

綜合以上思路，彈性粒子群算法的運(yùn)動(dòng)估計(jì)步驟如下：

1)設(shè)置一個(gè)最大迭代次數(shù)，筆者設(shè)置為10，若滿足給定條件則可提前結(jié)束迭代。

2)在粒子群優(yōu)化算法的初始階段，給定一個(gè)遠(yuǎn)大于40的初始粒子數(shù)量，以保證在空間域中有最廣闊的搜索域，涵蓋具有全局最優(yōu)值的區(qū)域。一旦此區(qū)域被搜索到，算法將很好的調(diào)整所有粒子的位置，以向全局最優(yōu)值收斂。

3)分析個(gè)體最優(yōu)與全局最優(yōu)位置，并考慮是否對(duì)其進(jìn)行更新。對(duì)于個(gè)體粒子，如果其適應(yīng)度值優(yōu)于其經(jīng)歷過(guò)的最優(yōu)位置，則用當(dāng)前粒子替換原有最優(yōu)位置；對(duì)于整個(gè)粒子群來(lái)說(shuō)，如果當(dāng)前全局最優(yōu)位置的適應(yīng)度值優(yōu)于原有的全局最優(yōu)位置，則用當(dāng)前全局最優(yōu)位置替換原有值。

4)檢查是否滿足迭代終止條件，如滿足，則終止迭代，否則轉(zhuǎn)向步驟2)繼續(xù)判斷。

5)PSO搜索結(jié)束。

該策略可以初始化眾多的粒子，以確保該算法能識(shí)別出含有全局最優(yōu)值的區(qū)域，然而在后期的迭代過(guò)程中，當(dāng)搜索域已經(jīng)縮小到較小的區(qū)域時(shí)，就不需要那么多的粒子了。

設(shè)置一個(gè)閾值T，當(dāng):

SAD

(3)

式中，SAD為當(dāng)前塊像素值與前一幀對(duì)應(yīng)位置塊像素值的絕對(duì)誤差和。T取512時(shí)，可以達(dá)到加速運(yùn)動(dòng)估計(jì)速度卻不明顯影響視覺(jué)效果。因此在達(dá)到最大迭代次數(shù)之前，如果滿足式(3)則可提前終止迭代[5-9]。

4 試驗(yàn)結(jié)果

為了驗(yàn)證算法的性能，分別選取運(yùn)動(dòng)相對(duì)平緩的silent、flower和運(yùn)動(dòng)劇烈的foreman、football、soccer這5個(gè)典型的測(cè)試序列的前100幀作為測(cè)試對(duì)象。幀率為30fps。宏塊大小固定為16(pixel)×16(pixel)，搜索范圍為16(pixel)，量化參數(shù)為28。在同一環(huán)境下分別測(cè)試全局運(yùn)動(dòng)估計(jì)算法和結(jié)合了彈性粒子群算法的運(yùn)動(dòng)估計(jì)，進(jìn)行了試驗(yàn)數(shù)據(jù)對(duì)比。

表1 運(yùn)動(dòng)平緩圖像的試驗(yàn)數(shù)據(jù)

注：Ⅰ和Ⅱ分別表示全局運(yùn)動(dòng)估計(jì)算法和結(jié)合了彈性粒子群算法的全局運(yùn)動(dòng)估計(jì)。

表2 運(yùn)動(dòng)劇烈圖像的試驗(yàn)數(shù)據(jù)

從表1試驗(yàn)數(shù)據(jù)可以看出，算法Ⅱ與算法Ⅰ相比，對(duì)運(yùn)動(dòng)平緩圖像的PSNR，搜索時(shí)間，迭代次數(shù)和編解碼一幀的平均時(shí)間改善不明顯。原因在于，固定模式的運(yùn)動(dòng)估計(jì)容易陷入局部最優(yōu)，全局運(yùn)動(dòng)估計(jì)對(duì)運(yùn)動(dòng)平緩圖像改善不明顯。從表2試驗(yàn)數(shù)據(jù)可以看出，算法Ⅱ與算法I相比，對(duì)于運(yùn)動(dòng)劇烈圖像的各方面的性能都有明顯提高，原因是算法Ⅱ結(jié)合了彈性粒子群算法，具有全局性，可以獲得全局最優(yōu)點(diǎn)，對(duì)運(yùn)動(dòng)劇烈圖像效果良好，有利于降低運(yùn)算量，提高運(yùn)算精度。

5 結(jié) 語(yǔ)

筆者通過(guò)對(duì)運(yùn)動(dòng)估計(jì)算法的改進(jìn)，提高運(yùn)算精度，降低運(yùn)算量，提升整個(gè)系統(tǒng)的性能，使系統(tǒng)資源可以更好的用來(lái)消除運(yùn)動(dòng)圖像的鋸齒現(xiàn)象。試驗(yàn)結(jié)果表明，該算法對(duì)運(yùn)動(dòng)圖像的整體性能提升效果良好，實(shí)際可行。

[1]Koga T,Iinnma K,Hirano A,et al.Motion-Compensated Interframe Coding for Video Conferencing [A]. Nut Telecommun Con[C]. 1981:145-153.

[2] Po L M，Ma W C.A Novel Four-Step Search Algorithm for Fast Block Motion Estimation[J].IEEE Trans Circuits Syst Video Technol,1996,6:313-317.

[3] Tham J Y,Ranganath S,Ranganath M,et al.A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation[J].IEEE Trans Circuits Syst Video Technol,1998,8:369-377.

[4] 鄭偉，劉文耀，王涌天.一種結(jié)合遺傳算法和鉆石搜索的多模式快速運(yùn)動(dòng)估計(jì)方法[J].電子學(xué)報(bào)，2006，34(10):1911-1916.

[5]Hassan R,Cohanim B K,Weck O D,et al.A Comparison of particle swarm optimization and the genetic algorithm[A]. in Proceedings of the 1st AIAA Multidisciplinary Design Optimization Specialist Conference[C].2005.

[6] van den Bergh F，Engelbrecht A P.A Cooperative approach to Particle Swarm Optimization[J].IEEE Transactions on Evolutionary Computation, 2004, 8(3):225-239.

[7] Kennedy J，Eberhart R C.Particle Swarm Optimization[J].IEEE International Conference on Neural Networks, 1995,(12):1942-1948.

[8]Ranganadhan D，Gorpuni P.An efficient bidirectional frame prediction using particle swarm optimization technique[A].Proc of International Conference on Advances in Recent Technologies in Communication and Computing Kottayam[C].2009:42-46.

[9]ZHAN Zhi-hui,ZHANG Jun,LI Yun,et al.Adaptive particle swarm optimization[J].IEEE Trans on Systems Man and Cybernetics Part B:Cybernetics,2009,39(6):1362-1381.

[編輯] 易國(guó)華

10.3969/j.issn.1673-1409(N).2012.06.041

TP391

B

1673-1409(2012)06-N122-03