一種基于二維離散余弦模型的運動估計算法研究

趙臣臣（廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院，廈門 361001）

一種基于二維離散余弦模型的運動估計算法研究

趙臣臣
（廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院，廈門 361001）

0　引言

隨著技術(shù)的進步，互聯(lián)網(wǎng)以及移動互聯(lián)網(wǎng)的快速發(fā)展，視頻信息流在互聯(lián)網(wǎng)傳播中日益占有越來越重要的信息體現(xiàn)價值。視頻因其直觀、高效、易于接受等特點，已經(jīng)從單純的視頻流轉(zhuǎn)變?yōu)楸O(jiān)控、視頻會議、無線流媒體等方向轉(zhuǎn)變，因此對于視頻壓縮的要求提出更高的要求。近幾十年來，通過近幾代人的努力，視頻編碼技術(shù)已經(jīng)取得了長足的進度，從第一代的視頻標(biāo)準(zhǔn) H.261到后來的歷代標(biāo)準(zhǔn)如 H.263、MPEG-1、MPEG-2、H.264、MPEG-4［3］等。對視頻的壓縮率已經(jīng)提高了幾十上百倍，高效的視頻壓縮技術(shù)不僅降低信息的冗余，同時了通過壓縮提高了碼流的利用率，緩解網(wǎng)絡(luò)頻寬的壓力。

在視頻編解碼中，幀間運動估計是其耗費時間較大的一個環(huán)節(jié)，同時也是影響視頻壓縮質(zhì)量的重要一環(huán)。因此，運動估計算法常常影響視頻編碼算法的最終效果。運動估計與補償?shù)哪繕?biāo)是減小幀間冗余信息，運動估計不是以估計物體的真實位移為目標(biāo)，而是追求最優(yōu)化率失真。自第一代視頻壓縮框架，基于平移運動模型的塊匹配算法BMA已經(jīng)被證實為有效的運動估計算法。在塊匹配算法中，每一幀被分割成固定大小的塊，并采用參考幀中最佳匹配塊去預(yù)測，這種方案假設(shè)每一塊相對于參考幀都具有相對獨立的運動適量。對于大部分連續(xù)性視頻序列來說，當(dāng)前幀與前后幀之間存在很強的相關(guān)性，它們之間的差異性也可能很小，這些差別主要來自于幀內(nèi)局部變化或者全局變化量。傳統(tǒng)的運動估計算法是基于塊的方式進行幀間預(yù)測。首先，當(dāng)前幀被劃分成若干個互不重疊的宏塊，并假定宏塊內(nèi)部具有相同的運動矢量，然后選定當(dāng)前幀的前一幀或者后一幀作為參考幀，并在參考幀中規(guī)定搜索的范圍搜索，因此，搜索范圍和搜索的算法直接決定了搜索的精度和效率。

在H.261中，16×16塊大小被采用，最近，更大塊的64×64被采用，一些學(xué)者對塊的劃分合并提出了一些改進算法等，基于塊的算法因其分割簡單，易于實現(xiàn)，算法變化量化的方便，被認(rèn)為是最合適的選擇，但是近年來，國內(nèi)外學(xué)者在改進運動模型方面做了大量的研究和改進，大部分研究都是基于塊匹配框架的基礎(chǔ)進行，例如Seferidis和Ghanbari兩位學(xué)者提出了普遍適用的基于塊匹配框架去估計運動矢量，他們采用了基于仿射、透視和雙線性變換等運動模型對四邊形塊進行變換。Wen-Hsiao等為了進一步優(yōu)化新一代視頻壓縮標(biāo)準(zhǔn)HEVC的幀間預(yù)測技術(shù)，他們提出了基于模板匹配和塊匹配的聯(lián)合運動補償技術(shù)去近似真實運動矢量場。本文將在后續(xù)章著重介紹基于彈性運動模型的算法理論研究和主客觀實驗分析，包括了二維離散余弦基函數(shù)彈性模型、迭代求解彈性模型參數(shù)算法、整體的求解流程以及實驗仿真對比。

1　運動估計算法

在視頻編解碼算法中，運動估計通常采用基于塊的匹配算法?；趬K運動估計算法通常是一個確定的搜索塊，這類算法使用固定搜索的方式在搜索區(qū)域內(nèi)搜索運動矢量，傳統(tǒng)的搜索算法有全搜索算法（FS）、3步搜索算法（3SS）、新三步搜索（N3SS）、4步搜索（4SS）、梯度下降搜索（BBGHD），菱形搜索（DS）等。此類算法中，主要以一個固定的模式，進行一個范圍內(nèi)搜索，此類算法一般是基于一個最小點進行步長的縮短等，但是很多算法會陷入局部最小。當(dāng)搜索模式的大小與實際運動程度不符合的時候，很容易造成搜索的不精度，影響尋找的匹配結(jié)果精度。

在塊運動估計算法中一般是基于平移模型，適用于匹配塊的垂直或者水平運動。該模型對于旋轉(zhuǎn)、縮放和形變等不能很好地描述，近年來，為了有效對非平移運動矢量進行預(yù)測以提高視頻壓縮效果，一些基于非平移模型的算法被學(xué)者關(guān)注和提出。比較典型的有仿射運動模型，透視運動模型，雙線性運動模型，基于光流模型的運動估計，基于網(wǎng)格模型的運動估計等算法。

圖1　運動估計原理示意圖

2　基于彈性模型的運動估計算法研究

基于平移的運動模型因其簡單性，幾乎主流的標(biāo)準(zhǔn)都采用了該平移模型的塊運動估計，但是由于對形變模型估計的需求，我們一改以往的剛性運動模型，提出了基于二維離線余弦基函數(shù)的彈性運動模型的運動估計算法。在常見的視頻序列中，主要有以下幾種運動方式：第一基于全局運動，第二局部塊運動。在傳統(tǒng)的運動模型中，對這兩種模型都有較好的表現(xiàn)，但是綜合這兩種運動形式會形成較復(fù)雜的運動矢量場，因此傳統(tǒng)塊運動模型賦予同一匹配所有像素點相同的運動矢量并不能很好地描述復(fù)雜矢量場的情況，塊運動估計模型處理復(fù)雜運動場的通常做法是采用較小的分塊，但是這樣必然會帶來比特信息流的開銷。本文介紹了一種基于二維離線余弦函數(shù)的彈性運動模型將有效的改善塊運動模型對運動矢量復(fù)雜的表現(xiàn)。

圖像匹配準(zhǔn)則技術(shù)的關(guān)鍵在于得到參考幀和測試幀之間相似點坐標(biāo)的映射函數(shù)。經(jīng)典的圖像配準(zhǔn)技術(shù)都能夠快速適用于視頻壓縮中。在視頻中假定兩個匹配塊為I（xi+yi）和 I'（xi'+yi'）

其中，P是運動參數(shù)的總數(shù)，mk為運動參數(shù)，φk（*）為任意的基函數(shù)，它能描述I與I'之間坐標(biāo)的復(fù)雜對應(yīng)關(guān)系?；瘮?shù)φk（*）可以為B樣條插值、多項式、諧波函數(shù)、仿射基函數(shù)以及小波變換等。

2.1基于二維離散余弦運動基函數(shù)的彈性運動模型

基于二維離線余弦基函數(shù)能夠用較少的系數(shù)有效表述彈性運動矢量場。離散余弦基函數(shù)的坐標(biāo)變換可以表示為：

2.2迭代高斯-牛頓梯度非線性最優(yōu)算法

在運動模型中，我們采用高斯牛頓梯度法來計算運動模型的參數(shù)，以使其從參考幀中得到最佳預(yù)測塊。我們采用的是迭代高斯-牛頓梯度非線性最優(yōu)化算法。在這種算法中，我們采用一階泰勒近似平方差和去線性化非線性表達式：

其中，把I與I'表示為I（xi+yi）和I'（xi'+yi'）。

2.3彈性運動模型參數(shù)求解流程

基于迭代高斯-牛頓梯度非線性最優(yōu)算法求解流程可以總結(jié)為以下9步：

（1）獲得當(dāng)前運動參數(shù)所對應(yīng)的映射模型，也就是把參數(shù)代入彈性運動模型并且計算對應(yīng)匹配點的像素位置。

（2）計算出當(dāng)前塊與參考塊的殘差。

（3）計算圖像水平和垂直的梯度。

（4）計算彈性運動模型對參數(shù)的導(dǎo)數(shù)。

（5）計算（3）和（4）的積。

（6）計算Hessian矩陣。

（7）計算（5）和（2）的值。

（8）計算彈性運動模型參數(shù)增量。

（9）更新彈性運動模型的參數(shù)值，本次迭代求解結(jié)束。

3　實驗結(jié)果分析

為了驗證本文研究的彈性運動模型運動估計算法對非平移運動矢量場的預(yù)測效果，本次實驗選取了A、B和C三類國際視頻標(biāo)準(zhǔn)測試序列，對各個測試序列的前50幀分別進行基于兩種不同運動模型的主客觀性能驗證，也就是彈性運動模型和BMA運動模型的算法比較，測試序列如表1所示。

表1　實驗所用測試序列

表2為本文采用的彈性運動模型與全搜索塊匹配算法BMA的實驗對比表，分割大小為64×64（表中1、4、7列）、32×32（表中2、5、8列）和16×16（表中3、6、9列），它們的匹配精度均為1/4像素，所有實驗數(shù)據(jù)均在單一分割層得到。

表2　64×64、32×32和16×16塊分割實驗對比表

從表中可以看出，對于塊分割大小為64×64，，相比于BMA算法，采用本文研究的彈性運動模型其平均PSNR都有提高。對于A類視頻序列，分辨率為352× 288，對其進行64×64塊分割后，由于分辨率低而分割塊大造成每個64×64編碼塊都包含了豐富的紋理信息，在編碼塊相對于參考幀運動并具有復(fù)雜矢量場情況下，采用傳統(tǒng)的BMA算法則無法有效地對運動矢量場進行預(yù)測而造成較大的殘差，相反，采用彈性運動模型則能有效地對非剛性運動矢量場進行表述，一定程度地減少了預(yù)測殘差能量。

圖2　32×32塊分割快匹配算法與彈性模型主觀圖對比

4　結(jié)語

基于彈性模型算法與常用的塊匹配算法是兩個完全不一樣的理論體系，我們根據(jù)實驗仿真數(shù)據(jù)從主客觀兩方面論證了本文研究的彈性運動模型的有效性，特別在預(yù)測復(fù)雜矢量場時，由于BMA算法的局限性，本文研究的彈性運動模型有更好的預(yù)測效果。

［1］X.Jing，L.P.Cha.An Effieient Three-step Search Algorithm for Block Motion Estimation.IEEE Transactions on Multimedia，2004

［2］W.Li，E.Salari.Suceessive Elimination Algorithm for Motion Estimation.IEEE Transactions on Image Processing

［3］Video Codec for Audiovisual Services at px64 Kbit/s，ITU-T Rec．H.261［S］，1993

［4］Sullivan G J，Ohm J，Woo-Jin H，et al.Overview of the High Efficiency Video Coding（HEVC）Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1649～1668

［5］Video Coding for Low Bitrate Communication，Version 1.ITU-T Rec.H.263［S］.ITU-T Rec.H.263，1995

［6］Iu S L.Comparison of Motion Compensation Using Different Degrees of Sub-pixel Accuracy for Interfield/Interframe Hybrid Coding of HDTV Image Sequences［C］.IEEE International Conference on Acoustics，Speech，and Signal Processing，1992

［7］Muhit A A，Pickering M R，F(xiàn)rater M R，et al.Video Coding Using Elastic Motion Model and Larger Blocks［J］.IEEE Transactions on Circuits and Systems for Video Technology，2010，20（5）：661～672

Two-Dimensional Discrete Cosine；HEVC；Motion Estimation

Research on a Motion Estimation Algorithm Based on the Two-Dimensional Discrete Cosine Model

ZHAO Chen-chen
（College of Information Science and Technology，Xiamen University，Xiamen 361001）

1007-1423（2015）10-0017-04

10.3969/j.issn.1007-1423.2015.10.005

趙臣臣（1989-），男，山東臨沂人，碩士研究生，研究方向為視頻編解碼

2015-02-05

2015-03-18

隨著視頻需求變大，視頻編解碼的要求越來越高，傳統(tǒng)的視頻編解碼技術(shù)基于塊匹配算法，其在同一個運動矢量場內(nèi)使用相同的運動矢量，并不能很好表現(xiàn)像素點的細(xì)節(jié)，同時對于采用較小塊劃分的結(jié)構(gòu)帶來大量的比特信息量，介紹一種基于二維離散余弦模型的方式實現(xiàn)更加精確描述復(fù)雜矢量場模型，能有效表現(xiàn)視頻序列的細(xì)節(jié)及節(jié)省比特開銷。

二維離散余弦；HEVC；運動估計

With the development of video demand，higher and higher requirements of video code，the conventional video coding technology based on the block matching algorithm，which uses the same motion vectors in the same motion vector field，it doesn't has a very good performance of pixel details，also for using relatively small partition structure brought a large number of bits，introduces a two-dimensional discrete cosine model based on the way to achieve a more accurate description of complex vector field model，which can effectively describe video sequence in details and save the bits.