基于高效視頻編碼的運動估計算法綜述

但鴻鍵 汪偉

摘 ?要： 運動估計是高效視頻編碼標準中的重要技術，通過幀間的運動矢量估計有效地減少視頻中的時間冗余，進而提高視頻編碼的壓縮效率。文章分析了運動估計算法的基本原理，將算法劃分為空域和頻域兩大類，并進一步將空域類算法細分為塊匹配法、光流法、像素遞歸法和貝葉斯法等，將頻域類算法分為相位法、離散余弦變換法和小波域法，詳盡地討論了在高效視頻編碼應用過程中各種方法的優缺點。最后，對基于高效視頻編碼的運動估計算法進行總結，探討了發展趨勢。

關鍵詞： 視頻編碼; 空域; 頻域; 運動估計算法

中圖分類號：TP391 ? ? ? ? ?文獻標識碼：A ? ? 文章編號：1006-8228（2020）01-01-04

Abstract： Motion estimation is an important technology in high efficiency video coding standard. Motion vector estimation between frames can effectively reduce the time redundancy in video and improve the compression efficiency of video coding. This paper analyzes the basic principle of motion estimation algorithm， divides the algorithm into two categories， i.e. spatial domain and frequency domain， and further subdivides the spatial domain algorithm into block matching method， optical flow method， pixel recursive method and Bayesian method， and divides the frequency domain algorithm into phase method， discrete cosine transform method and wavelet domain method. The advantages and disadvantages of the application of various methods in efficient video coding are discusses in detail. Finally， the motion estimation algorithms for high efficiency video coding are summarized， and the corresponding development trends are discussed.

Key words： video coding; spatial domain; frequency domain; motion estimation algorithm

0 引言

在如今的信息化時代，三維影像、超高清視頻和虛擬現實等視頻服務需求日益增長，高清晰度視頻的編碼和傳輸日益成為研究的熱點問題。高清視頻有冗余度高、信息量大等特點，為了使其能滿足網絡領域內的傳輸和儲存要求，必須先對視頻數據進行壓縮，再進行傳輸和儲存。運動估計（Motion Estimation，ME）算法是HEVC（High Efficiency Video Coding）視頻編碼過程中最為關鍵的算法，它占用了整個視頻編碼一半以上的計算量和絕大部分的運算時間，是決定視頻壓縮效率的主導因素。

本文通過對運動估計算法進行探討，闡述了各種算法的基本原理，將算法主要劃分為空域和頻域兩個大類。如圖1所示，在空域算法中，根據最佳匹配塊選取方法的不同來細分;在頻域的算法中，又根據頻域變換方法的不同來細分。

通過對運動估計算法的綜述，能夠為視頻壓縮技術的深入研究提供參考，具有重要的意義。

1 空域運動估計算法

目前，HEVC運動估計算法中常用的空域方法有：塊匹配法、光流法、像素遞歸法和貝葉斯法。

1.1 塊匹配法

1.1.1 塊匹配法理論基礎及準則

圖2可簡要表明塊匹配算法的基本原理：設當前幀中的待匹配的子塊為A，對應于前一幀中的相同坐標位置區域為虛線塊A，且在前一幀中以A為中心的搜索區域設定為B。塊匹配的過程就是在B中尋找一個與A最相似的子塊C，C與A的坐標偏移V是估計得出的運動矢量。

1.1.2 塊匹配搜索策略

塊匹配搜索策略的選擇對運動估計的速度和準確性都有極大的影響。目前HEVC中塊匹配搜索策略可主要有整像數和分像數兩大類。其中，經過改進的整像素塊匹配法有著良好的壓縮效率，分數塊匹配法有著更高的精度。

（1） 整像素塊匹配法

此類算法從運動矢量分布角度，提出了新三步法（NTSS）[3]和新四步法（NFSS）[4]等。新三步法和新四步法主要是解決在運動較小的情況下，因第一步搜索步長設置過大，難以找到最佳匹配點的問題;從搜索模式角度，Abdelazim等[5]提出了一種改進的鉆石法搜索，先用相位相關法來找出編碼單元的近似偏移中心，再采用9點菱形搜索在偏移中心找到最佳匹配塊;從相鄰塊相關性角度，王佳利等[6]提出一種基于UMHexagonS算法，根據時間預測矢量和空間預測矢量的位置關系確定搜索方法，得到局部范圍最佳匹配點后，利用矢量相關性繼續展開搜索。相比之前，這些方法更有效地利用相鄰塊相關性，減少搜索點數、提高搜索效率、增強了算法的魯棒性和降低了陷入局部最優的可能性。

（2） 分像素塊匹配法

自然物體的運動具有連續性，運動矢量往往不會恰好是整數像素單位，在實際視頻中也并不存在分數像素處的樣值。為保證像素精度，在HEVC中對亮度的運動補償精度采用分像素技術，采用的運動矢量精度是亮度1/2和亮度1/4像素內插、色度1/8像素的內插，并使用了更科學的插濾波抽頭值。

Jia等[7]采用亞像素的運動估計算法，跳過平滑部分的亞像素搜索過程，并且根據視頻中的紋理方向來進行搜索，進一步減少計算復雜度;陸寄遠等[8]提出嘗試整合分像素插值和分像素運動估計的方法，把分像素插值的代價融合在分像素運動估計中，構建區域分像素集的插值算法，只動態地計算在運動估計中用到分像素。此類算法有更精確的運動矢量和較小的計算復雜度。

1.2 光流法

為提高光流法運動估計效率，秦曉波等[11]提出一種優化的HS算法，在圖像檢測中得到的Harris角點，結合塊匹配運動估計確定感興趣區域，將此區域作為光流法初始運動矢量。雖然光流法能有效得到運動矢量，但存在計算復雜度高、耗時長、實時性差和存在將變化光線當成光流的可能性。因此，一方面可降低算法計算復雜度來減少計算時長，提高實時性;另外一方面還需增強算法的抗干擾性。

1.3 像素遞歸法

HEVC中的像素遞歸法采用遞歸思想，對物體位移引起的像素數據變化，在梯度方向的像素周圍進行像素迭代運算，使連續運算收斂于一個運動矢量，每個像素都對應一個運動矢量，每個像素的運動矢量都需要由遞歸得出，如下式所示：

為了提高視頻的清晰度，Haan等[12]將像素遞歸搜索引入到運動估計算法中，使運動估計的運動矢量計算達到了亞像素精度;Tashlinskii等[13]提出利用隨機梯度法對所有像素點進行運動估計的方法，先采用梯度下降法對節點逐行處理，再利用行間的相關性提高行處理效率。然而，此類方法計算復雜度大、在物體運動劇烈快速情況下的實時性差。

1.4 貝葉斯法

貝葉斯法是Bayes于1763年提出的一種基于概率統計知識對數據分類的算法。此類算法在HEVC中，一方面，通過利用相鄰塊的運動矢量來自適應地選擇最佳搜索模式[14]，合理利用計算資源;另一方面，根據相鄰塊的相關性和貝葉斯算法結合，制定提前終止策略，減少無效的搜索次數。

為減少運動估計算法的復雜度和提高計算速度，Shen等[15]提出基于貝葉斯決策規則的編碼單元尺寸決策算法;Shen等[16]提出基于貝葉斯決策規則的變換單元尺寸決策算法，它們根據殘差系數和塊相關性給出提前終止算法，避免對所有編碼塊和變換塊的尺寸窮盡搜索。此類算法將貝葉斯理論與運動矢量預測結合，既提高了預測精度，又減少了算法的計算量。

2 頻域運動估計算法

HEVC中的頻域運動估計算法，可直接從相位相關圖中得出更平滑和精確的運動矢量預測，加強了視頻的流暢性;且不用考慮時域變化對運動矢量預測的影響，有著良好的穩定性;另外，頻域法的理論簡單、計算復雜度低、可實現并行處理。

2.1 離散余弦變換法

基于離散余弦變換（DCT）的運動估計方法，可對圖像進行有損壓縮。通過計算DCT中的虛相位移，利用正弦正交原理從一維信號中估計出運動物體位移，再根據二維平移運動模型，進一步推廣到二維圖像中。該算法可給編碼器提供更多的空間進行高度并行操作。

為提升頻域算法的效率，Ismail等[17]提出了一種采用DCT變換進行頻域復變換，通過相位相關平面計算出運動矢量的方法，與塊匹配法結合使用。然而，基于DCT的方法，目前的壓縮效率還不足以支持龐大的視頻數據傳輸，抗誤碼性也不夠好，在運動估計中應用并不廣泛。

2.2 相位法

相位法是一種基于傅里葉變換的頻域運動估計方法，利用傅里葉變換估算塊位移，能同時對多個目標進行檢測且可以避免光照的干擾，可減少計算復雜度，提高運動估計速度，并較好的保持視頻編碼的壓縮比和運動圖像質量。

余應淮等[18]提出一種基于核回歸修正上采樣的相位相關法，通過檢測上采樣相位相關曲面的峰值坐標來實現亞像素運動估計，再用核回歸方法擬合初始估計值的鄰域，最后通過檢測擬合函數的峰值，對初始估計值進行修正;Podder等[19]提出利用相位相關法得到當前塊和參考塊之間的運動信息，再根據運動信息選擇最佳的搜索模板。此類方法可減少運動估計的時間，并有著良好的魯棒性。

2.3 小波域法

Koga[20]于1991年提出小波域運動估計算法，該方法比DCT法有更高的壓縮比、更強的抗誤碼性、并能支持漸進傳輸。

張磊等[21]提出一種采用雙高通濾波新型小波域的運動估計法，比傳統小波域算法的計算復雜度更低，運動估計性能更好;宋傳鳴等[22]提出像素預測起點搜索的小波域運動估計，采用非均勻搜索起點搜索模板搜索初始運動向量，減少小波變換中移變產生的影響。該方法可在預測精度和計算復雜度之間達到平衡，避免發生算法精度高而增加計算復雜度，或減少計算復雜度而犧牲算法精度的情況。

3 結束語

本文結合運動估計的基本原理對運動估計算法進行了綜述。塊匹配法依舊會是近幾年的主流方法，其中改進的鉆石搜索算法因計算速度快、計算復雜度小、算法簡單且容易在硬件平臺上實現的特點繼續受到眾多研究者的青睞;光流法因其良好的跟蹤效果，在交通監控和室內監控中有很好的效果;而像素遞歸法中的高精度特性適用于高清圖像;相位法不太依賴時間相關性，在運動復雜無規律的視頻中會有不錯的效果;小波域法能考慮人眼對頻帶的敏感性，可在未來的電影電視中廣泛應用。根據視頻需求，合理利用各種方法的特點對視頻進行壓縮，可有效地利用資源以滿足當前對視頻處理的巨大需求。

總之，運動估計算法有著廣泛的應用領域，在工業領域，可用于過程監控和動態測量，在醫學領域，可用于心臟運動和血流的研究，在交通領域，可用于交通路況監控，在多媒體技術領域，可用于視頻壓縮等。此類算法的應用有著巨大的前景。

參考文獻（References）：

[1] 朱秀昌，劉峰，胡棟. H.265/HEVC：視頻編碼新標準及其擴展[M].北京：電子工業出版社，2016.

[2] 向友君， 雷娜， 余衛宇等.運動估計算法匹配準則研究[J]. 計算機科學，2009.36（9）：278-280

[3] Li R，Zeng B，Liou M L.A new three-step search algorithm for block motion estimation [J]. IEEE Transactions on Circuits & Systems for Video Technology， 2002.4（4）：438-442

[4] Wang K T，Chen O T C.Motion estimation using an efficient four-step search method[C]//IEEE International Symposium on Circuits & Systems.1998.

[5] AbdelazimA，Hamza A，Hefeida M，et al.Diamond frequency domain inter frame motion estimation for HEVC[J].2017.

[6] 王佳利，姜珊，雙凱.基于時空預測向量相關性的運動估計算法[J].計算機工程與科學，2014.36（3）.

[7] Jia S，Ding W，Shi Y，et al.A fast sub-pixe estimation algorithm for HEVC[C]//IEEE International Symposium on Circuits & Systems. IEEE，2016.

[8] 陸寄遠，劉宇熹，侯昉等.HEVC的高效分像素運動補償[J].軟件學報，2017.28（8）：2214-2226

[9] Horn B K P，Schunck B G. Determining Optical Flow[M].1980.

[10] Lucas B D，Kanade T.An iterative image registration technique with an application to stereo vision[C]//International Joint Conference on Artificial Intelligence. 1981.

[11] 秦曉波，柴志成.基于運動估計優化的HS光流算法研究[J].四川大學學報（自然科學版），2014.51（4）.

[12] Haan G D，Biezen P W A C.Sub-pixel motion estimation with 3-D recursive search block-matching[J].Signal Processing：Image Communication，1994.6（3）：229-239

[13] Tashlinskii A G，Smirnov P V，Tsaryov M G.Pixel-by-pixel estimation of scene motion in video[J].ISPRS-International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，2017，XLII-2/W4：61-65

[14] Tohidypour H R，Pourazad M T，Nasiopoulos P.A low complexity mode decision approach for HEVC-based 3D video coding using a Bayesian method[C] //International Conference on Acoustics，Speech and Signal Processing （ICASSP）. IEEE，2014.

[15] Shen X，Lu Y，Jie C.Fast coding unit size selection for HEVC based on Bayesian decision rule[C]// Picture Coding Symposium. 2012.

[16] Shen L，Zhang Z，Zhang X，et al.Fast TU size decision algorithm for HEVC encoders using Bayesian theorem detection[J]. Image Communication，2015.32（C）：121-128

[17] Ismail Y，Elgamel M A，Bayoumi M A.Fast Variable Padding Motion Estimation Using Smart Zero Motion Prejudgment Technique for Pixel and Frequency Domains[J].IEEE Transactions on Circuits & Systems for Video Technology，2009.19（5）：609-626

[18] 余應淮，謝仕義，梅其祥.基于核回歸修正的上采樣相位相關精確運動估計算法[J].計算機應用，2016.36（8）：2316-2321

[19] Podder P K，Paul M，Murshed M，et al. Fast Intermode Selection for HEVC Video Coding Using Phase Correlation[C]//International Conference on Digital Image Computing： Techniques & Applications. 2015.

[20] Koga T.Motion-compensated wavelet transform coding for color video compression[C]//Visual Communications，Boston，Ma. International Society for Optics and Photonics，1991.

[21] 張磊，涂國防.一種新型小波域運動估計算法[J].電子與信息學報，2007.29（5）：1131-1135

[22] 宋傳鳴，譚茹，王相海等.結合低位深像素預測起點的小波域運動估計[J].計算機研究與發展，2013.4：776-786