基于遺傳塊匹配算法的高效運(yùn)動(dòng)估計(jì)技術(shù)研究

摘 要：在MPEG4視頻壓縮中，運(yùn)動(dòng)估計(jì)是幀間視頻編碼中的關(guān)鍵技術(shù)，塊匹配方法BMA（Block Matching Algorithm）是目前廣泛使用的運(yùn)動(dòng)估計(jì)方法，但在現(xiàn)有的快速搜索算法中大都是次優(yōu)算法，容易陷入局部最優(yōu)。針對(duì)此問(wèn)題，將遺傳算法GA(Genetic Algorithm)應(yīng)用于塊匹配運(yùn)動(dòng)估計(jì)。實(shí)驗(yàn)證明，該算法不僅有效解決了局部極小問(wèn)題，且計(jì)算量相對(duì)較少。

關(guān)鍵詞：視頻壓縮；運(yùn)動(dòng)估計(jì)；塊匹配；遺傳算法

中圖分類號(hào)：TN919.81文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2008)08-121-03

Technology Research Based on Genetic Algorithm Efficient Block Matching Motion Estimation

CHEN Hong，QI Hua，ZHANG Jian

(School of Electronic Information Engineering，Xi′an Technological University，Xi′an，710032，China)

Abstract：Motion estimation is essential for many interframe video coding techniques in MPEG4 video compression.The Block Matching Algorithm(BMA) is currently widely used in motion estimation，However the existing quick search algorithm are mostly suboptimal algorithm and get a suboptimal solution.Aiming at this problem，this paper applies the genetic algorithm to block matching motion estimation.The result shows that the algorithm not only solve the problem of being trapped to local optima but also have a relatively small amount of computation.

Keywords：video compression;motion estimation;block matching;genetic algorithm

1 引 言

MPEG4是現(xiàn)在最重要最有影響的多媒體數(shù)據(jù)壓縮編碼國(guó)際標(biāo)準(zhǔn)之一。基于對(duì)象的編碼思想使其具有高壓縮比、可擴(kuò)展性、可交互性等許多優(yōu)點(diǎn)。MPEG4 視頻壓縮算法主要是對(duì)某一時(shí)刻某幀畫(huà)面VO（Video Object）的形狀、運(yùn)動(dòng)、紋理等信息進(jìn)行編碼。而實(shí)現(xiàn)上述編碼的關(guān)鍵是運(yùn)動(dòng)估計(jì)，運(yùn)動(dòng)估計(jì)的結(jié)果不僅會(huì)影響視頻圖像壓縮編碼的質(zhì)量，也會(huì)影響壓縮編碼的效率，因此提高運(yùn)動(dòng)估計(jì)的效率是整個(gè)編碼的重點(diǎn)。現(xiàn)有的快速搜索算法中大都是次優(yōu)算法，且易陷于局部極小點(diǎn)。遺傳算法是借助于計(jì)算機(jī)編程將待求問(wèn)題表示成串(或染色體)，即為二進(jìn)制碼或數(shù)碼串，從而構(gòu)成一群串，并置于問(wèn)題的求解環(huán)境中，根據(jù)一定適應(yīng)度的原則選擇出適應(yīng)環(huán)境的串進(jìn)行復(fù)制，且通過(guò)交叉和變異兩種基因操作產(chǎn)生新的更適應(yīng)環(huán)境的一代種群，經(jīng)這樣一代代不斷變化，最后收斂到一個(gè)最適應(yīng)環(huán)境的串上，而求得問(wèn)題的最優(yōu)解。本文提出了一種將遺傳算法應(yīng)用于塊運(yùn)動(dòng)估計(jì)中的遺傳搜索塊匹配運(yùn)動(dòng)估計(jì)算法。該方法把塊運(yùn)動(dòng)向量作為遺傳染色體，經(jīng)過(guò)交叉、變異等操作，以便得到全局意義上的最優(yōu)解 。

2 遺傳算法的基本原理

遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方法，他借鑒了達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)。其本質(zhì)是一種高效、并行、全局搜索的方法，他能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)、并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。遺傳算法操作使用適者生存的原則，在潛在的解決方案種群中逐次產(chǎn)生一個(gè)近似最優(yōu)的方案。他利用某種編碼技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進(jìn)化過(guò)程。遺傳算法通過(guò)有組織的、隨機(jī)的信息交換重新組合那些適應(yīng)性好的串，生成新的串的群體。如今他以其固有的計(jì)算并行性，已廣泛應(yīng)用于問(wèn)題優(yōu)化、模型識(shí)別、并行處理等領(lǐng)域。 

遺傳算法解決問(wèn)題的基本步驟為：將實(shí)際問(wèn)題參數(shù)進(jìn)行編碼；確定作為優(yōu)勝標(biāo)準(zhǔn)的適應(yīng)值度量；選取初始種群；運(yùn)用選擇、交叉、變異等遺傳算子對(duì)種群進(jìn)行選擇進(jìn)化；運(yùn)用停止運(yùn)行原則得到優(yōu)勝個(gè)體，最終得到問(wèn)題的解。

3 基于GA的塊匹配運(yùn)動(dòng)估值方法

運(yùn)動(dòng)估計(jì)是消除圖像幀間冗余的有效方法。 塊匹配算法（BMA）是目前應(yīng)用最廣的一種運(yùn)動(dòng)估計(jì)算法。各種快速搜索算法都是基于一種假設(shè)前提:在沿搜索路徑到最佳匹配點(diǎn)的搜索過(guò)程中，匹配誤差是單調(diào)遞減的，也即假設(shè)在整個(gè)搜索窗中，匹配誤差只有一個(gè)最小值，但實(shí)際上這種假設(shè)在絕大多數(shù)應(yīng)用中得不到滿足，通常情況下的匹配誤差在整個(gè)搜索窗內(nèi)呈現(xiàn)多極值狀態(tài)，因此，這些快速搜索算法往往陷于局部最優(yōu)解，而得不到全局最優(yōu)解，從而導(dǎo)致編碼質(zhì)量的顯著下降。為了解決局部最優(yōu)化問(wèn)題，本文采用基于遺傳算法的塊匹配運(yùn)動(dòng)估計(jì)。

已出現(xiàn)的幾種基于遺傳算法(GA)的塊匹配算法中，文獻(xiàn)［1］提出的一種GSA算法，由于具有很高的迭代次數(shù)，故其計(jì)算耗時(shí)非常大，接近FSA，所以很難應(yīng)用于圖象視頻編碼；文獻(xiàn)［2］中提出的LGSA算法，雖然計(jì)算時(shí)間大大減少，但由于他未采用交叉操作，僅利用生存競(jìng)爭(zhēng)策略控制下的高變異率去尋找全局最優(yōu)，因此也會(huì)使算法質(zhì)量變得不穩(wěn)定。本文提出的基于遺傳算法的塊匹配算法，不僅能有效地解決局部極小問(wèn)題，而且大大減少計(jì)算量。

3.1 編碼方案的確定 

碼需要建立一種從搜索空間中的各個(gè)候選點(diǎn)到確定長(zhǎng)度的各個(gè)染色體串的雙向映射并確定染色體串的長(zhǎng)度L和字母表規(guī)模k，塊匹配問(wèn)題的待解參數(shù)為運(yùn)動(dòng)矢量MV(x，y)。本文采用二進(jìn)制串表示法( k= 2)將運(yùn)動(dòng)矢量映射到染色體(x1，x2，…，xn，y1，y2，…，yn)，其中L=2n;n = ［log2W］ + 1;W = max{sx ，sy };sx ，sy 分別為搜索窗的水平半徑和垂直半徑。 由于偏移量具有方向性，故專用x1，y1來(lái)表示運(yùn)動(dòng)偏移量的正負(fù)(例如:x1=1表示水平運(yùn)動(dòng)矢量為負(fù)，x1=0表示水平運(yùn)動(dòng)矢量為正)。在MPEG4標(biāo)準(zhǔn)中，圖像塊大小為16×16，搜索窗大小為(2W+1)2，故n=5，L=10。

3.2 定義適應(yīng)度函數(shù)

遺傳算法最優(yōu)值為適應(yīng)度大的點(diǎn)，而B(niǎo)MA中最優(yōu)點(diǎn)是使MAD值最小的點(diǎn)，為使兩者統(tǒng)一，適應(yīng)性函數(shù)定為:F(i)=1/MAD，MAD越小的點(diǎn)，其適應(yīng)度越高。

MAD=1/I×J∑|i|≤1[]2∑|j|≤1[]2|f(i，j)

-g(i-[WTHX]d[WTBX]x，j-[WTHX]d[WTBX]y)|

其中I=J=16，坐標(biāo)(0，0)表示塊的左上角像素。[WTHX]d[WTBX]x，[WTHX]d[WTBX]y分別是參考宏塊的運(yùn)動(dòng)矢量的水平矢量和垂直矢量。

3.3 設(shè)定種群規(guī)模和初始種群 

在常規(guī)遺傳算法中，初始個(gè)體通常是隨機(jī)產(chǎn)生的，其個(gè)數(shù)和位置決定著能否快速找到最優(yōu)解。個(gè)數(shù)過(guò)少、分布過(guò)于集中，迭代可能過(guò)早收斂；個(gè)數(shù)過(guò)大，運(yùn)算量較大；分布過(guò)稀，迭代次數(shù)較多。在BMA具體問(wèn)題中，應(yīng)根據(jù)運(yùn)動(dòng)序列的具體情況指定初始點(diǎn)。首先，運(yùn)動(dòng)矢量具有中心偏移特性，即認(rèn)為運(yùn)動(dòng)偏移大多限制在圍繞搜索窗中心的一個(gè)很小區(qū)域內(nèi)。其次，相鄰宏塊運(yùn)動(dòng)相似，可以用已編碼相鄰宏塊的運(yùn)動(dòng)矢量來(lái)預(yù)測(cè)當(dāng)前宏塊的運(yùn)動(dòng)矢量，如圖1所示。

根據(jù)以上2個(gè)特性，初始染色體個(gè)數(shù)為9個(gè)，位置指定方法如下:

對(duì)于圖像邊緣的宏塊，沒(méi)有參考宏塊，初始點(diǎn)為搜索窗口中心的9個(gè)點(diǎn)，如圖2（a）所示。

對(duì)于內(nèi)部宏塊，根據(jù)周圍匹配過(guò)的宏塊預(yù)先設(shè)定運(yùn)動(dòng)矢量，初始點(diǎn)為該運(yùn)動(dòng)矢量周圍的9個(gè)點(diǎn)，如圖2（b）所示。

圖1 運(yùn)動(dòng)矢量預(yù)測(cè)

圖2 初始點(diǎn)分布示意圖

[BT3-*3]3.4 確定進(jìn)化機(jī)制

采用交叉、變異和選擇3種算子作用于進(jìn)化過(guò)程，具體過(guò)程如下：

(1) 交叉：用轉(zhuǎn)輪法選擇N個(gè)用來(lái)繁殖后代的個(gè)體，并放入雜交池中。從雜交池中任選2個(gè)個(gè)體作為父、母代個(gè)體，根據(jù)預(yù)先設(shè)置的交叉率Pc進(jìn)行交配或者復(fù)制，重復(fù)該過(guò)程，最后得到N個(gè)子代個(gè)體。交叉過(guò)程是遺傳算法中很重要的部分，交叉率的選擇將直接關(guān)系到算法的性能，Pc過(guò)高，群體中個(gè)體的更新越快，則高性能個(gè)體的破壞也越快，Pc過(guò)低，相對(duì)來(lái)說(shuō)，搜索范圍就會(huì)變小，易造成算法停滯不前，交叉率Pc需要根據(jù)經(jīng)驗(yàn)值來(lái)選取，經(jīng)過(guò)實(shí)驗(yàn)令Pc=0.8效果較好。

(2) 變異:變異操作，用以模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變。其方法是根據(jù)生物遺傳中基因變異的原理，以變異率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。即對(duì)執(zhí)行變異的對(duì)應(yīng)位求反，把1變?yōu)?，把0變?yōu)?。單靠變異不能在求解中得到好處，但是他能保證算法過(guò)程中不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特性。具體做法是：根據(jù)突變概率Pm，對(duì)雜交池中的個(gè)體進(jìn)行變異操作，最后得到后代的群體。在有交叉環(huán)節(jié)的情況下令Pm=0.05。

(3) 選擇:將得到的N個(gè)后代個(gè)體與N個(gè)父代個(gè)體共2N個(gè)個(gè)體，按其適應(yīng)值從大到小依次排列，取前N個(gè)個(gè)體形成下一代群體。

3.5 停止運(yùn)行的準(zhǔn)則

迭代終止的條件為達(dá)到種群進(jìn)化的最大代數(shù)I。

I=log2 W

W是最大運(yùn)動(dòng)偏移量，他的值由搜索窗決定，搜索窗越大代數(shù)越多。在MPEG4標(biāo)準(zhǔn)中，圖像塊大小為16×16，故本文中取W=16，則種群進(jìn)化的最大代數(shù)I=4。若達(dá)到此最大代數(shù)則迭代終止，得到最優(yōu)匹配點(diǎn)，如果不滿足條件，則執(zhí)行交叉，變異，選擇。 

3.6 算法流程 

算法流程如圖3所示。

圖3 算法流程圖

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

在表1和表2中，列舉采用本文算法和FS，DS搜索法后得到的PSNR值，以及采用他們所需要的搜索點(diǎn)數(shù)。在實(shí)驗(yàn)中，采用兩個(gè)典型的標(biāo)準(zhǔn)測(cè)試序列foreman.yuv和coastguard.yuv來(lái)驗(yàn)證該算法的性能指標(biāo)，這兩個(gè)序列均為CIF格式，速率為30 f/s，他們還有一個(gè)特點(diǎn)就是圖像運(yùn)動(dòng)劇烈，攝像機(jī)鏡頭移動(dòng)幅度比較大。本文對(duì)這兩個(gè)測(cè)試序列中的30幀圖像進(jìn)行運(yùn)動(dòng)估計(jì)，計(jì)算出他們的PSNR值與運(yùn)動(dòng)估計(jì)搜索點(diǎn)數(shù)，并將他們的值和FS，DS搜索法的值相比較。在做運(yùn)動(dòng)估計(jì)時(shí)，圖像塊大小為16×16像素，染色體長(zhǎng)度L=10，交叉率Pc=0.8，變異率Pm=0.05，搜索窗大小為33×33，最大迭代次數(shù)I=4。

表1 采用3種算法得到的foreman的Y，U，V三分量的PSNR

表2 采用3種算法得到的 coastguard的Y，U，V三分量的PSNR 

通過(guò)比較可以看到，采用本文算法，可以使用最少的搜索點(diǎn)搜索到最優(yōu)點(diǎn)，PSNR值較FS略有降低，但略高于DS算法。這是由于本文采用了選擇、交叉、變異等遺傳算子，且在產(chǎn)生初始種群時(shí)考慮了運(yùn)動(dòng)矢量具有中心偏移特性以及相鄰宏塊運(yùn)動(dòng)相似，既防止早熟現(xiàn)象，又保證了種群的進(jìn)化收斂，避免陷入局部最優(yōu)，從而得到全局最優(yōu)解。

5 結(jié) 語(yǔ)

將遺傳算法應(yīng)用于視頻壓縮的運(yùn)動(dòng)估計(jì)部分，引入全局優(yōu)化思想，同時(shí)考慮運(yùn)動(dòng)矢量具有中心偏移特性以及相鄰宏塊運(yùn)動(dòng)相似，避免了局部最優(yōu)，極大地提高了算法性能。實(shí)驗(yàn)結(jié)果表明，本文算法得到的PSNR值略低于FS，略高于DS算法，而搜索點(diǎn)數(shù)較上兩種算法大大減少，減少了計(jì)算量，提高了速度，可以很好地應(yīng)用于MPEG4視頻壓縮編碼中。

參 考 文 獻(xiàn)

［1］Chow K H K，Liou M L.Genetic Motion Search Algorithm for Video Compression\\[J\\].IEEE Trans.，Circuits Syst.Video Technol.，1993，3:440 445.

［2］Lin Chunhung，Wu Jaling.A Lightweight Genetic Block Matching Algorithm for VideoCoding\\[J\\].IEEE.Trans.Circuits Syst.Video Technol.，1998，8:386 392.

［3］Zhu Shan，Ma K K.New Diamond Search Algorithm for Fast Block Matching Motion Estimation\\[C\\].Int′L.Conf.on Information，Commun And Signal Proc.(ICICS′97)，Singapore，1997.

［4］Holland J H.Adaptation in Natural and Artificial Systems\\[M\\].2nd Edition.CambridgeMA:MIT Press，1992.

［5］雷英杰，張善文，李續(xù)武.Matlab遺傳算法工具箱及應(yīng)用 ［M］.西安:西安電子科技大學(xué)出版社，2005.

［6］龔濤，丁潤(rùn)濤，一種基于改進(jìn)的遺傳算法的塊匹配運(yùn)動(dòng)估計(jì)方法［J］.信號(hào)處理，2003，19(3):207210.

［7］李珅，徐維樸，鄭南寧，等.一種新的基于遺傳算法的快速運(yùn)動(dòng)估計(jì)方法［J］.電子學(xué)報(bào)，2000(6):115118.

［8］劉偉峰，莊奕琪，屈文博，等.基于TMS320DSC21的視頻編碼系統(tǒng)設(shè)計(jì)\\[J\\].現(xiàn)代電子技術(shù)，2005，28(12):7679.



作者簡(jiǎn)介 陳 紅 女，1980年出生，西安工業(yè)大學(xué)電子信息工程學(xué)院助教，碩士研究生。主要研究方向?yàn)閳D像處理、通信技術(shù)、信息論與編碼。

齊 華 女，1963年出生，西安工業(yè)大學(xué)教務(wù)處副處長(zhǎng)、高教研究室主任。主要研究方向?yàn)樾畔⒄撆c編碼、圖像處理。

張 健 男，1980年出生，西安工業(yè)大學(xué)電子信息工程學(xué)院碩士研究生。主要研究方向?yàn)閳D像處理、通信技術(shù)。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文