但鴻鍵 汪偉

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

關(guān)鍵詞： 視頻編碼; 空域; 頻域; 運(yùn)動估計(jì)算法

中圖分類號：TP391 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：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 引言

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

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

通過對運(yùn)動估計(jì)算法的綜述，能夠?yàn)橐曨l壓縮技術(shù)的深入研究提供參考，具有重要的意義。

1 空域運(yùn)動估計(jì)算法

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

1.1 塊匹配法

1.1.1 塊匹配法理論基礎(chǔ)及準(zhǔn)則

圖2可簡要表明塊匹配算法的基本原理：設(shè)當(dāng)前幀中的待匹配的子塊為A，對應(yīng)于前一幀中的相同坐標(biāo)位置區(qū)域?yàn)樘摼€塊A，且在前一幀中以A為中心的搜索區(qū)域設(shè)定為B。塊匹配的過程就是在B中尋找一個與A最相似的子塊C，C與A的坐標(biāo)偏移V是估計(jì)得出的運(yùn)動矢量。

1.1.2 塊匹配搜索策略

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

（1） 整像素塊匹配法

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

（2） 分像素塊匹配法

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

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

1.2 光流法

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

1.3 像素遞歸法

HEVC中的像素遞歸法采用遞歸思想，對物體位移引起的像素?cái)?shù)據(jù)變化，在梯度方向的像素周圍進(jìn)行像素迭代運(yùn)算，使連續(xù)運(yùn)算收斂于一個運(yùn)動矢量，每個像素都對應(yīng)一個運(yùn)動矢量，每個像素的運(yùn)動矢量都需要由遞歸得出，如下式所示：

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

1.4 貝葉斯法

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

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

2 頻域運(yùn)動估計(jì)算法

HEVC中的頻域運(yùn)動估計(jì)算法，可直接從相位相關(guān)圖中得出更平滑和精確的運(yùn)動矢量預(yù)測，加強(qiáng)了視頻的流暢性;且不用考慮時域變化對運(yùn)動矢量預(yù)測的影響，有著良好的穩(wěn)定性;另外，頻域法的理論簡單、計(jì)算復(fù)雜度低、可實(shí)現(xiàn)并行處理。

2.1 離散余弦變換法

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

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

2.2 相位法

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

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

2.3 小波域法

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

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

3 結(jié)束語

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

總之，運(yùn)動估計(jì)算法有著廣泛的應(yīng)用領(lǐng)域，在工業(yè)領(lǐng)域，可用于過程監(jiān)控和動態(tài)測量，在醫(yī)學(xué)領(lǐng)域，可用于心臟運(yùn)動和血流的研究，在交通領(lǐng)域，可用于交通路況監(jiān)控，在多媒體技術(shù)領(lǐng)域，可用于視頻壓縮等。此類算法的應(yīng)用有著巨大的前景。

參考文獻(xiàn)（References）：

[1] 朱秀昌，劉峰，胡棟. H.265/HEVC：視頻編碼新標(biāo)準(zhǔn)及其擴(kuò)展[M].北京：電子工業(yè)出版社，2016.

[2] 向友君， 雷娜， 余衛(wèi)宇等.運(yùn)動估計(jì)算法匹配準(zhǔn)則研究[J]. 計(jì)算機(jī)科學(xué)，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] 王佳利，姜珊，雙凱.基于時空預(yù)測向量相關(guān)性的運(yùn)動估計(jì)算法[J].計(jì)算機(jī)工程與科學(xué)，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] 陸寄遠(yuǎn)，劉宇熹，侯昉等.HEVC的高效分像素運(yùn)動補(bǔ)償[J].軟件學(xué)報，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] 秦曉波，柴志成.基于運(yùn)動估計(jì)優(yōu)化的HS光流算法研究[J].四川大學(xué)學(xué)報（自然科學(xué)版），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] 余應(yīng)淮，謝仕義，梅其祥.基于核回歸修正的上采樣相位相關(guān)精確運(yùn)動估計(jì)算法[J].計(jì)算機(jī)應(yīng)用，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] 張磊，涂國防.一種新型小波域運(yùn)動估計(jì)算法[J].電子與信息學(xué)報，2007.29（5）：1131-1135

[22] 宋傳鳴，譚茹，王相海等.結(jié)合低位深像素預(yù)測起點(diǎn)的小波域運(yùn)動估計(jì)[J].計(jì)算機(jī)研究與發(fā)展，2013.4：776-786