但鴻鍵 汪偉

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

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

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

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

本文通過(guò)對(duì)運(yùn)動(dòng)估計(jì)算法進(jìn)行探討，闡述了各種算法的基本原理，將算法主要?jiǎng)澐譃榭沼蚝皖l域兩個(gè)大類。如圖1所示，在空域算法中，根據(jù)最佳匹配塊選取方法的不同來(lái)細(xì)分;在頻域的算法中，又根據(jù)頻域變換方法的不同來(lái)細(xì)分。

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

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

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

1.1 塊匹配法

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

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

1.1.2 塊匹配搜索策略

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

（1） 整像素塊匹配法

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

（2） 分像素塊匹配法

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

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

1.2 光流法

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

1.3 像素遞歸法

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

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

1.4 貝葉斯法

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

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

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

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

2.1 離散余弦變換法

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

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

2.2 相位法

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

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

2.3 小波域法

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

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

3 結(jié)束語(yǔ)

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

總之，運(yùn)動(dòng)估計(jì)算法有著廣泛的應(yīng)用領(lǐng)域，在工業(yè)領(lǐng)域，可用于過(guò)程監(jiān)控和動(dòng)態(tài)測(cè)量，在醫(yī)學(xué)領(lǐng)域，可用于心臟運(yùn)動(dòng)和血流的研究，在交通領(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)動(dòng)估計(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] 王佳利，姜珊，雙凱.基于時(shí)空預(yù)測(cè)向量相關(guān)性的運(yùn)動(dòng)估計(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)動(dòng)補(bǔ)償[J].軟件學(xué)報(bào)，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)動(dòng)估計(jì)優(yōu)化的HS光流算法研究[J].四川大學(xué)學(xué)報(bào)（自然科學(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)動(dòng)估計(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] 張磊，涂國(guó)防.一種新型小波域運(yùn)動(dòng)估計(jì)算法[J].電子與信息學(xué)報(bào)，2007.29（5）：1131-1135

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