基于遺傳塊匹配算法的高效運動估計技術研究

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

關鍵詞：視頻壓縮；運動估計；塊匹配；遺傳算法

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

2 遺傳算法的基本原理

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

遺傳算法解決問題的基本步驟為：將實際問題參數進行編碼；確定作為優勝標準的適應值度量；選取初始種群；運用選擇、交叉、變異等遺傳算子對種群進行選擇進化；運用停止運行原則得到優勝個體，最終得到問題的解。

3 基于GA的塊匹配運動估值方法

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

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

3.1 編碼方案的確定 

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

3.2 定義適應度函數

遺傳算法最優值為適應度大的點，而BMA中最優點是使MAD值最小的點，為使兩者統一，適應性函數定為:F(i)=1/MAD，MAD越小的點，其適應度越高。

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，坐標(0，0)表示塊的左上角像素。[WTHX]d[WTBX]x，[WTHX]d[WTBX]y分別是參考宏塊的運動矢量的水平矢量和垂直矢量。

3.3 設定種群規模和初始種群 

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

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

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

對于內部宏塊，根據周圍匹配過的宏塊預先設定運動矢量，初始點為該運動矢量周圍的9個點，如圖2（b）所示。

圖1 運動矢量預測

圖2 初始點分布示意圖

[BT3-*3]3.4 確定進化機制

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

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

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

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

3.5 停止運行的準則

迭代終止的條件為達到種群進化的最大代數I。

I=log2 W

W是最大運動偏移量，他的值由搜索窗決定，搜索窗越大代數越多。在MPEG4標準中，圖像塊大小為16×16，故本文中取W=16，則種群進化的最大代數I=4。若達到此最大代數則迭代終止，得到最優匹配點，如果不滿足條件，則執行交叉，變異，選擇。 

3.6 算法流程 

算法流程如圖3所示。

圖3 算法流程圖

4 實驗結果及分析 

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

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

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

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

5 結 語

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

參 考 文 獻

［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］雷英杰，張善文，李續武.Matlab遺傳算法工具箱及應用 ［M］.西安:西安電子科技大學出版社，2005.

［6］龔濤，丁潤濤，一種基于改進的遺傳算法的塊匹配運動估計方法［J］.信號處理，2003，19(3):207210.

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

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



作者簡介 陳 紅 女，1980年出生，西安工業大學電子信息工程學院助教，碩士研究生。主要研究方向為圖像處理、通信技術、信息論與編碼。

齊 華 女，1963年出生，西安工業大學教務處副處長、高教研究室主任。主要研究方向為信息論與編碼、圖像處理。

張 健 男，1980年出生，西安工業大學電子信息工程學院碩士研究生。主要研究方向為圖像處理、通信技術。

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