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

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

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

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

2 遺傳算法的基本原理

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

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

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

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

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

3.1 編碼方案的確定 

碼需要建立一種從搜索空間中的各個候選點(diǎn)到確定長度的各個染色體串的雙向映射并確定染色體串的長度L和字母表規(guī)模k，塊匹配問題的待解參數(shù)為運(yùn)動矢量MV(x，y)。本文采用二進(jìn)制串表示法( k= 2)將運(yùn)動矢量映射到染色體(x1，x2，…，xn，y1，y2，…，yn)，其中L=2n;n = ［log2W］ + 1;W = max{sx ，sy };sx ，sy 分別為搜索窗的水平半徑和垂直半徑。 由于偏移量具有方向性，故專用x1，y1來表示運(yùn)動偏移量的正負(fù)(例如:x1=1表示水平運(yùn)動矢量為負(fù)，x1=0表示水平運(yùn)動矢量為正)。在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)，而BMA中最優(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)動矢量的水平矢量和垂直矢量。

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

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

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

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

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

圖1 運(yùn)動矢量預(yù)測

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

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

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

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

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

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

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

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

I=log2 W

W是最大運(yùn)動偏移量，他的值由搜索窗決定，搜索窗越大代數(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)中，采用兩個典型的標(biāo)準(zhǔn)測試序列foreman.yuv和coastguard.yuv來驗(yàn)證該算法的性能指標(biāo)，這兩個序列均為CIF格式，速率為30 f/s，他們還有一個特點(diǎn)就是圖像運(yùn)動劇烈，攝像機(jī)鏡頭移動幅度比較大。本文對這兩個測試序列中的30幀圖像進(jìn)行運(yùn)動估計(jì)，計(jì)算出他們的PSNR值與運(yùn)動估計(jì)搜索點(diǎn)數(shù)，并將他們的值和FS，DS搜索法的值相比較。在做運(yùn)動估計(jì)時，圖像塊大小為16×16像素，染色體長度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 

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

5 結(jié) 語

將遺傳算法應(yīng)用于視頻壓縮的運(yùn)動估計(jì)部分，引入全局優(yōu)化思想，同時考慮運(yùn)動矢量具有中心偏移特性以及相鄰宏塊運(yùn)動相似，避免了局部最優(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］龔濤，丁潤濤，一種基于改進(jìn)的遺傳算法的塊匹配運(yùn)動估計(jì)方法［J］.信號處理，2003，19(3):207210.

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

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



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

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

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

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