是視頻編碼和視頻處理(例如去交織)中廣泛使用的一種技術。
基本介紹
- 中文名：運動估計
- 外文名：Motion Estimation
概述,基本概念,估計方法,表示法,基於塊的運動表示法,亞像素位置的內插,運動矢量在時空域的預測方式,準則分類,搜尋算法,全局搜尋算法,分數精度搜尋算法,快速搜尋算法,分級搜尋範圍（DSR）算法,混合搜尋算法,其他資料,運動估計算法,
概述
運動估計的基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，並認為宏塊內所有象素的位移量都相同，然後對每個宏塊到參考幀某一給定特定搜尋範圍內根據一定的匹配準則找出與當前塊最相似的塊，即匹配塊，匹配塊與當前塊的相對位移即為運動矢量。視頻壓縮的時候，只需保存運動矢量和殘差數據就可以完全恢復出當前塊。
基本概念
在幀間預測編碼中，由於活動圖像鄰近幀中的景物存在著一定的相關性。因此，可將活動圖像分成若干塊或宏塊，並設法搜尋出每個塊或宏塊在鄰近幀圖像中的位置，並得出兩者之間的空間位置的相對偏移量，得到的相對偏移量就是通常所指的運動矢量，得到運動矢量的過程被稱為運動估計。
運動矢量和經過運動匹配後得到的預測誤差共同傳送到解碼端，在解碼端按照運動矢量指明的位置，從已經解碼的鄰近參考幀圖像中找到相應的塊或宏塊，和預測誤差相加後就得到了塊或宏塊在當前幀中的位置。
通過運動估計可以去除幀間冗餘度，使得視頻傳輸的比特數大為減少，因此，運動估計是視頻壓縮處理系統中的一個重要組成部分。本節先從運動估計的一般方法入手，重點討論了運動估計的三個關鍵問題：將運動場參數化、最最佳化匹配函式定義以及如何尋找到最最佳化匹配。
估計方法
一般的運動估計方法如下： 設 t 時刻的幀圖像為當前幀 f （x， y） ， t’時刻的幀圖像為參考幀f’(x，y)，參考幀在時間上可以超前或者滯後於當前幀，如圖1所示，當 t’<t 時，稱之為後向運動估計，
當 t’>t 時，稱之為前向運動估計。當在參考幀t’中搜尋到當前幀 t 中的塊的最佳匹配時，可以得到相
應的運動場 d（x; t, t + t △ ） ，即可得到當前幀的運動矢量。
H.264 編碼標準和以往採用的視頻壓縮標準很大的不同在於，在運動估計過程中採用了多參考
圖1前向或後向運動估計
圖1前向或後向運動估計幀預測來提高預測精度，多參考幀預測就是在編解碼端建一個存儲 M個重建幀的快取，當前的待編
度。由於視頻序列的連續性，當前塊在不同的參考幀中的運動矢量也是有一定的相關性的。假定當
前塊所在幀的時間為 t, 則對應前面的多個參考幀的時間分別為：t-1, t-2, ……。則當在幀 t-2 中搜尋
當前塊的最優匹配塊時，可以利用當前塊在幀 t-1 中的運動矢量 MVNR來估測出當前塊在幀 t-2 的運
動矢量。
表示法
由於在成象的場景中一般有多個物體作不同的運動，如果直接按照不同類型的運動將圖像分割成複雜的區域是比較困難的。最直接和不受約束的方法是在每個像素都指定運動矢量，這就是所謂基於像素表示法。這種表示法是對任何類型圖像都是適用的，但是它需要估計大量的未知量，並且它的解時常在物理上是不正確，除非在估計過程中施加適當的物理約束。這在具體實現時是不可能的，通常採用基於塊的物體運動表示法。
基於塊的運動表示法
一般對於包含多個運動物體的景物，實際中普遍採用的方法是把一個圖像幀分成多個塊，使得在每個區域中的運動可以很好地用一個參數化模型表征，這被稱為塊匹配法，即將圖像分成若干個n×n 塊（典型值：16×16 宏塊） ，為每一個塊尋找一個運動矢量 MV，並進行運動補償預測編碼。 每一個幀間宏塊或塊都是根據先前已編碼的數據預測出的，根據已編碼的宏塊、塊預測的值和當前宏塊、塊作差值，結果被壓縮傳送給解碼器，與解碼器所需要的其他信息如（運動矢量、預測模型等）一起用來重複預測過程。 每個分割區域都有其對應的運動矢量，並必須對運動矢量以及塊的選擇方式進行編碼和傳輸。在細節比較多的幀中如果選擇較大的塊尺寸，意味著用於表明運動矢量和分割區域類型的比特數會少些，但是運動壓縮的冗餘度要多一些；如果選擇小一點的塊尺寸，那么運動壓縮後冗餘度要少一些，但是所需比特數要比較多。因此必須要權衡塊尺寸選擇上對壓縮效果的影響，一般對於細節比較少、比較平坦的區域選擇塊尺寸大一些，對於圖像中細節比較多的區域選擇塊尺寸小一些。 宏塊中的每個色度塊 （Cb 和 Cr） 尺寸寬高都是亮度塊的一半， 色度塊的分割方法和亮度塊同樣，只是尺寸上寬高都是亮度塊一半（如亮度塊是 8×16 塊尺寸大小，那么色度塊就是 4×8，如果亮度塊尺寸為 8×4，那么色度塊便是 4×2 等等） 。每個色度塊的運動矢量的水平和垂直坐標都是亮度塊的一半。
亞像素位置的內插
幀間編碼宏塊中的每個塊或亞宏塊分割區域都是根據參考幀中的同尺寸的區域預測得到的，它
們之間的關係用運動矢量來表示。
由於自然物體運動的連續性，相鄰兩幀之間的塊的運動矢量不是以整像素為基本單位的，可能
真正的運動位移量是以 1/4 像素或者甚至 1/8 像素等亞像素作為為單位的。
圖 3.17 給出了一個視頻序列當採用 1/2 像素精度、1/4 像素精度和 1/8 像素精度時編碼效率的情
況，從圖中可以看到 1/4像素精度相對於 1/2 像素精度的編碼效率有很明顯的提高，但是 1/8 像素精
度相對於 1/4像素精度的編碼效率除了在高碼率情況下並沒有明顯的提高， 而且 1/8像素的內插公式
更為複雜， 因此在 H.264的制定過程中 1/8 像素精度的運動矢量模型逐漸被取消而只採用了 1/4 像素
精度的運動矢量模型。
圖2運動矢量在時空域的預測方式
如果對每個塊的運動矢量進行編碼，那么將花費相當數目的比特數，特別是如果選擇小尺寸的
塊的時候。由於一個運動物體會覆蓋多個分塊，所以空間域相鄰塊的運動矢量具有很強的相關性，
因此，每個運動矢量可以根據鄰近先前已編碼的塊進行預測，預測得到的運動矢量用 MVp 表示，當
前矢量和預測矢量之間的差值用 MVD 表示。同時由於物體運動的連續性，運動矢量在時間域也存
在一定相關性，因此也可以用鄰近參考幀的運動矢量來預測。
1) 運動矢量空間域預測方式
運動矢量中值預測（Median Prediction）
利用與當前塊 E 相鄰的左邊塊 A，上邊塊 B 和右上方的塊 C 的運動矢量，取其中值來作為當前
塊的預測運動矢量。
設 E 為當前宏塊、宏塊分割或者亞宏塊分割， A 在 E 的左側，B 在 E 的上方、C 在 E 的右上
方，如果 E 的左側多於一個塊，那么選擇最上方的塊作為 A，在 E 的上方選擇最左側的塊作為 B。
圖 3.18 表示所有的塊尺寸相同，圖 3.19 表示鄰近塊尺寸不同時作為預測 E 的運動矢量的塊的選擇。
在預測 E 的過程中遵守以下準則：
1、 對於除了塊尺寸為 16×8和 8×16 的塊來說，MVp是塊 A、B 和 C 的運動矢量的中值；
2、 對於 16×8 塊來說， 上方的 16×8 塊的MVp 根據B預測得到， 下方的 16×8 塊的 MVp 根據 A
得到；
3、 對於 8×16 塊來說， 左側的 16×8 塊的MVp 根據 A預測得到， 右側的 16×8 塊的 MVp 根據 C
得到；
4、 對於不用編碼的可跳過去的宏塊，16×16 矢量MVp 如第一種情況得到。
2) 運動矢量在時間域預測方式
a、前幀對應塊運動矢量預測（Corresponding-block Prediction）
利用前一幀的與當前塊相同坐標位置的塊的運動矢量來作為當前塊的預測運動矢量，如圖 3.21
所示。
b、時間域的鄰近參考幀運動運動矢量預測（Neighboring Reference-frame Prediction）
由於視頻序列的連續性，當前塊在不同的參考幀中的運動矢量也是有一定的的相干性的。如圖
3.22 所示，假設當前塊所在幀的時間為 t，則當在前面的參考幀t’中搜尋當前塊的最優匹配塊時，可
以利用當前塊在參考幀t’+1 中的運動矢量來估測出當前塊在幀他 t’的運動矢量：
在上述運動矢量的四種預測方式中，經過實驗證明，空間域的預測更為準確，其中上層塊預測
的性能最優，因為其充分利用了不同預測塊模式運動矢量之間的相關性。而中值預測性能隨著預測
塊尺寸的減小而增加，這是因為當前塊尺寸越小，相關性越強。
準則分類
是否匹配的問題，即如何定義一個匹配準則。而匹配準則的定義與運算複雜度和編碼效率都是直接
相關的，通常有如下幾類比較常用的匹配函式的定義：
設當前幀 f2，參考幀f1，
（1）最小均方差函式（MSE）
MSE (MV) =Σ|f2（x，MV）-f1(x)|
2
(3.34)
（2）最小平均絕對值誤差（MAD）等效於常用的絕對差值和（SAD）準則,性能很好,而且相對簡單
的硬體需求，因而得到了最廣泛的套用。
MAD (MV) =Σ|f2（x，MV）-f1(x)| (3.35)
（3）閾值差別計數（NTD）
NTD（MV）=ΣG（f2（x，MV）-f1(x)） (3.36)
其中：
當 | α－β | >T0 時，G（α，β）=1；
當 | α－β | <T0 時，G（α，β）=0 (3.37)
由於在用塊匹配算法進行運動估計的過程中，利用匹配準則函式進行匹配誤差的計算是最主要
的計算量，因此，我們可以從這方面進一步減少計算量。由於圖象的幀內也具有相關性，在計算誤
差匹配函式時，可以只讓圖象塊中的部分像素參與運算，將塊中的所有像素組成一個集合，那么參
與計算的這部分像素集合就是它的子集，這種誤差匹配的方法被稱為子集匹配法。實驗結果表明，
在匹配誤差無明顯增加的情況下，採用子集匹配可以大大減少每幀圖象的平均搜尋時間。
搜尋算法
匹配誤差函式，可以用各種最佳化方法進行最小化，這就需要我們開發出高效的運動搜尋算法，
主要的幾種算法歸納如下：
全局搜尋算法
為當前幀的一個給定塊確定最優位移矢量的全局搜尋算法方法是：在一個預先定義的搜尋區域
內，把它與參考幀中所有的候選塊進行比較，並且尋找具有最小匹配誤差的一個。這兩個塊之間的
位移就是所估計的 MV，這樣做帶來的結果必然導致極大的計算量。
選擇搜尋區域一般是關於當前塊對稱的，左邊和右邊各有 Rx 個像素，上邊和下邊各有 Ry個像素。
如果已知在水平和垂直方向運動的動態範圍是相同的，那么 Rx=Ry=R。估計的精度是由搜尋的步長決定的，步長是相鄰兩個候選塊在水平或者垂直方向上的距離。通常，沿著兩個方向使用相同的步長。在最簡單的情況下，步長是一個像素，稱為整數像素精度搜尋，該種算法也稱為無損搜尋算法。
分數精度搜尋算法
由於在窮盡塊匹配算法中搜尋相應塊的步長不一定是整數，一般來說，為了實現 1/K像素步長，對參考幀必須進行 K倍內插。根據實驗證明，與整像素精度搜尋相比，半像素精度搜尋在估計精度上有很大提高，特別是對於低清晰度視頻。
但是，套用分數像素步長，搜尋算法的複雜性大大增加，例如，使用半像素搜尋，搜尋點的總數比整數像素精度搜尋大四倍以上。
那么，如何確定適合運動估計的搜尋步長，對於視頻編碼的幀間編碼來說，即使得預測誤差最小化。
快速搜尋算法
快速搜尋算法和全局搜尋算法相比，雖然只能得到次最佳的匹配結果，但在減少運算量方面效果顯著。
1） 二維對數搜尋法
這種算法的基本思路是採用大菱形搜尋模式和小菱形搜尋模式，步驟如圖 6.4.20 所示，從相應於零位移的位置開始搜尋，每一步試驗菱形排列的五個搜尋點。下一步，把中心移到前一步找到的最佳匹配點並重複菱形搜尋。當最佳匹配點是中心點或是在最大搜尋區域的邊界上時，就減小搜尋步長（菱形的半徑） 。否則步長保持不變。當步長減小到一個像素時就到達了最後一步，並且在這最
後一步檢驗九個搜尋點。初始搜尋步長一般設為最大搜尋區域的一半。
其後這類算法在搜尋模式上又做了比較多的改進，在搜尋模式上採用了矩形模式，還有六邊形模式、十字形模式等等。
2） 三步搜尋法
這種搜尋的步長從等於或者略大於最大搜尋範圍的一半開始。第一步，在起始點和周圍八個 “1”標出的點上計算匹配誤差，如果最小匹配誤差在起始點出現，則認為沒有運動；第二步，以第一步中匹配誤差最小的點（圖中起始點箭頭指向的“1”）為中心，計算以“2”標出的 8個點處的匹配誤差。注意，在每一步中搜尋步長搜都比上一步長減少一半，以得到更準確的估計；在第三步以後就能得到最終的估計結果，這時從搜尋點到中心點的距離為一個像素。
但是，上述一些快速算法更適合用於估計運動幅度比較大的場合，對於部分運動幅度小的場合，它們容易落入局部最小值而導致匹配精度很差，已經有很多各種各樣的視頻流證明了這一點。
現在，針對這一缺點，國內外諸多專家學者也提出了相應的應對措施，特別是針對H.264編碼標準要求的一些快速算法的改進，並取得卓越的效果。例如[7]中提到的基於全局最小值具有自適應性的快速算法，這種算法通過在每一搜尋步驟選擇多個搜尋結果，基於這些搜尋結果之間的匹配誤差的不同得到的最佳搜尋點，因而可以很好地解決落入局部最小值的問題。
[8]中提到一種適用於H．264的基於自適應搜尋範圍的快速運動估計算法，經過實驗證明對於如salesman等中小運動序列，其速度可接近全局搜尋算法的400倍，接近三步搜尋算法的4倍；而對於大運動序列，如table tennis，該算法則會自動調節搜尋點數以適應複雜的運動。當從總體上考察速度方面的性能時，可以看到，該算法平均速度是全局搜尋算法的287．4倍，三步搜尋的2．8倍。
分級搜尋範圍（DSR）算法
分級搜尋算法的基本思想是從最低解析度開始逐級精度的進行不斷最佳化的運動搜尋策略，首先取得兩個原始圖象幀的金子塔表示，從上到下解析度逐級變細，從頂端開始，選擇一個尺寸比較大的數據塊進行一個比較粗略的運動搜尋過程，對在此基礎上進行亞抽樣（即通過降低數據塊尺寸（或提高抽樣解析度）和減少搜尋範圍的辦法）進行到下一個較細的級來細化運動矢量，而一個新的搜尋過程可以在上一級搜尋到的最優運動矢量周圍進行。在亞抽樣的過程中也有著不同的抽樣方式和抽樣濾波器。這種方法的優點是運算量的下降比例比較大，而且搜尋的比較全面。
缺點是由於亞抽樣或者濾波器的採用而使記憶體的需求增加，另外如果場景細節過多可能會容易落入局部最小點。
混合搜尋算法
由於物體的運動千變萬化，很難用一種簡單的模型去描述，也很難用一種單一的算法來搜尋最佳運動矢量，因此實際上大多採用多種搜尋算法相組合的辦法，可以在很大程度上提高預測的有效性和魯棒性。
解碼器要求傳送的比特數最小化，而複雜的模型需要更多的比特數來傳輸運動矢量，而且易受噪聲影響。因此，在提高視頻的編碼效率的技術中，運動補償精度的提高和比特數最小化是相互矛盾的，這就需要我們在運動估計的準確性和表示運動所用的比特數之間作出折中的選擇。它的效果與選用的運動模型是密切相關的。
其他資料
三常見的運動估計匹配準則有三種：MAD、MSE和NCCF，由於MAD沒有乘除操作，不需做乘法運算，實現簡單方便，所以使用較多。通常使用求和絕對誤差（SAD）代替MAD 。
運動估計算法
運動估計算法是視頻壓縮編碼的核心算法之一。高質量的運動估計算法是高效視頻編碼的前提和基礎。其中塊匹配法（BMA, Block Match Algorithm）由於算法簡單和易於硬體實現，被廣泛套用於各視頻編碼標準中。塊匹配法的基本思想是先將圖像劃分為許多子塊，然後對當前幀中的每一塊根據一定的匹配準則在相鄰幀中找出當前塊的匹配塊，由此得到兩者的相對位移，即當前塊的運動矢量。在H.264標準的搜尋算法中，圖像序列的當前幀被劃分成互不重疊16×16大小的子塊，而每個子塊又可劃分成更小的子塊，當前子塊按一定的塊匹配準則在參考幀中對應位置的一定搜尋範圍內尋找最佳匹配塊，由此得到運動矢量和匹配誤差。運動估計的估計精度和運算複雜度取決於搜尋策略和塊匹配準則。這裡使用H.264推薦算法UMHexagonS（Unsymmetrical-cross Multi-Hexagon-grid Search）作為DSP實現的算法參考，與FS算法比較，它在保證可靠搜尋精度的前提下大幅降低搜尋複雜度。同時使用絕對差和（SAD, the Sum of Absolute Difference）標準作為匹配準則，它具有便於硬體實現的優點。
