距估計演算法

1. 運動估計的搜索演算法

匹配誤差函數，可以用各種優化方法進行最小化，這就需要我們開發出高效的運動搜索演算法，
主要的幾種演算法歸納如下： 為當前幀的一個給定塊確定最優位移矢量的全局搜索演算法方法是：在一個預先定義的搜索區域
內，把它與參考幀中所有的候選塊進行比較，並且尋找具有最小匹配誤差的一個。這兩個塊之間的
位移就是所估計的 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倍。 分級搜索演算法的基本思想是從最低解析度開始逐級精度的進行不斷優化的運動搜索策略，首先取得兩個原始圖象幀的金子塔表示，從上到下解析度逐級變細，從頂端開始，選擇一個尺寸比較大的數據塊進行一個比較粗略的運動搜索過程，對在此基礎上進行亞抽樣（即通過降低數據塊尺寸（或提高抽樣解析度）和減少搜索范圍的辦法）進行到下一個較細的級來細化運動矢量，而一個新的搜索過程可以在上一級搜索到的最優運動矢量周圍進行。在亞抽樣的過程中也有著不同的抽樣方式和抽樣濾波器。這種方法的優點是運算量的下降比例比較大，而且搜索的比較全面。
缺點是由於亞抽樣或者濾波器的採用而使內存的需求增加，另外如果場景細節過多可能會容易落入局部最小點。 由於物體的運動千變萬化，很難用一種簡單的模型去描述，也很難用一種單一的演算法來搜索最佳運動矢量，因此實際上大多採用多種搜索演算法相組合的辦法，可以在很大程度上提高預測的有效性和魯棒性。
事實上，在運動估計時也並不是單一使用上述某一類搜索演算法，而是根據各類演算法的優點靈活組合採納。在運動幅度比較大的情況下可以採用自適應的菱形搜索法和六邊形搜索法，這樣可以大大節省碼率而圖象質量並未有所下降。在運動圖象非常復雜的情況下，採用全局搜索法在比特數相對來說增加不多的情況下使得圖象質量得到保證。 H.264 編碼標准草案推薦使用 1/4分數像素精度搜索。[6]中提到在整像素搜索時採用非對稱十字型多層次六邊形格點運動搜索演算法，然後採用鑽石搜索模型來進行分數像素精度運動估計。
解碼器要求傳送的比特數最小化，而復雜的模型需要更多的比特數來傳輸運動矢量，而且易受雜訊影響。因此，在提高視頻的編碼效率的技術中，運動補償精度的提高和比特數最小化是相互矛盾的，這就需要我們在運動估計的准確性和表示運動所用的比特數之間作出折中的選擇。它的效果與選用的運動模型是密切相關的。