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

一種基于二維離散余弦模型的運(yùn)動(dòng)估計(jì)算法研究

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

0　引言

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

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

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

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

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

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

圖1　運(yùn)動(dòng)估計(jì)原理示意圖

2　基于彈性模型的運(yùn)動(dòng)估計(jì)算法研究

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

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

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

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

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

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

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

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

2.3彈性運(yùn)動(dòng)模型參數(shù)求解流程

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

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

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

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

（4）計(jì)算彈性運(yùn)動(dòng)模型對(duì)參數(shù)的導(dǎo)數(shù)。

（5）計(jì)算（3）和（4）的積。

（6）計(jì)算Hessian矩陣。

（7）計(jì)算（5）和（2）的值。

（8）計(jì)算彈性運(yùn)動(dòng)模型參數(shù)增量。

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

3　實(shí)驗(yàn)結(jié)果分析

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

表1　實(shí)驗(yàn)所用測(cè)試序列

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

表2　64×64、32×32和16×16塊分割實(shí)驗(yàn)對(duì)比表

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

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

4　結(jié)語

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

［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-），男，山東臨沂人，碩士研究生，研究方向?yàn)橐曨l編解碼

2015-02-05

2015-03-18

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

二維離散余弦；HEVC；運(yùn)動(dòng)估計(jì)

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.