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

趙臣臣（廈門大學信息科學與技術學院，廈門 361001）

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

趙臣臣
（廈門大學信息科學與技術學院，廈門 361001）

0　引言

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

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

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

1　運動估計算法

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

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

圖1　運動估計原理示意圖

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

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

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

其中，P是運動參數的總數，mk為運動參數，φk（*）為任意的基函數，它能描述I與I'之間坐標的復雜對應關系。基函數φk（*）可以為B樣條插值、多項式、諧波函數、仿射基函數以及小波變換等。

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

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

2.2迭代高斯-牛頓梯度非線性最優算法

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

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

2.3彈性運動模型參數求解流程

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

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

（2）計算出當前塊與參考塊的殘差。

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

（4）計算彈性運動模型對參數的導數。

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

（6）計算Hessian矩陣。

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

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

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

3　實驗結果分析

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

表1　實驗所用測試序列

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

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

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

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

4　結語

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

［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，Frater 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

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

二維離散余弦；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.