關於運動估計快速搜尋演算法的研究的論文
關於運動估計快速搜尋演算法的研究的論文
摘要：h.264是itu-t的vceg(影片編碼專家組)和iso／iec的mpeg(活動圖象編碼專家組)的聯合影片組(jvt：joint videoteam)開發的一個新的數字影片編碼標準，它既是itu-t的h.264，又是1so／iec的mpeg-4的第10部分。新一代標準h.264可以得到更好的壓縮影象效果、擁有更多的功能和更大的靈活性。本文主要從實時影片應用的角度，對h 264／avc編碼過程中運動估計模組快速搜尋演算法進行了研究。
關鍵詞：影片編碼 h 264／avc 運動估計 快速搜尋演算法
隨著資訊科技的發展和社會的不斷進步，人類對資訊的需求越來越豐富，人們希望無論何時何地都能夠方便的、快捷、靈活的透過語音、資料、影象與影片等多種方式進行通訊。數字訊號處理技術、物理媒體與網路技術、超大規模積體電路技術突飛猛進的發展，使得多媒體通訊成為研究和應用的熱點。本文主要是針對影片壓縮中的運動估計快速搜尋演算法的研究。影片壓縮後的資料流大小的關鍵因素在於能否較好的去除其時間相關性，尋找到最佳的匹配塊。
1.h.264／avc概述
與早期的影片編碼標準(h.261，mpeg-1，mpeg-2，h.263，mpeg-4)類似，h.264／avc也是建立在塊匹配的混合編碼框架上。基本演算法依然是透過幀間預測和運動補償來消除影片序列中的時域冗餘，經過變換編碼消除頻域冗餘。因此基本的功能模組：例如預測、變換、量化、編碼都沒有發生根本的變化。
2.運動估計原理
2.1運動估計概述
在基於塊匹配的混合影片編碼體系中，運動搜尋是其中計算複雜性最高的模組。h.264／avc為了獲得更精確的預測和更高的壓縮比，採用了多種塊模式的運動估計，多參考幀和更高解析度的運動向量。雖然這樣可以增加預測的精度，提高壓縮比，但h.264／avc中運動估計的計算複雜性卻因此急劇增加。
運動搜尋快速演算法的實質是基於某種策略在減少搜尋點數提高搜尋效率的同時，儘可能保持編碼影象質量不變(與fs的情況相比)。但簡單的減少搜尋點數的演算法(例如tts，2-d對數等快速演算法)通常都假設匹配誤差曲面是單峰的，而實際的影片影象是非常複雜的，常常不能滿足這樣的假設，因此容易在搜尋起始階段落入區域性最小點。為解決區域性最小點的問題，通常可以採用相鄰塊預測的方法獲得更好的搜尋起點。但有些情況下特別是在運動複雜度高的序列中，相鄰塊會包含與當前塊不同的運動物件，因此也會產生錯誤的運動向量。更好的策略是採用覆蓋整個搜尋區域的全域性搜尋(global search)的概念，即搜尋點在整個搜尋區域的稀疏網格上選擇。雖然這種策略增加了搜尋點數，但可以有效的避免在搜尋起始階段落入區域性最小點以及可能的錯誤起始點預測。
2.2運動搜尋的步驟
最佳匹配塊的確定是透過運動搜尋來實現的，運動搜尋包含整數運動搜尋和小數運動搜尋，具體的流程圖如圖2.1所示：
2.2.1參考幀的選取
在h.264協議中，定義了三種基本的幀型別，即i、p、b幀型別，其中i幀只能作為其他幀的參考幀，它本身在編碼的時候，幀內宏塊根據已經編編碼的相鄰塊的資料來編碼，不參考其它幀；p幀在編碼的時候，只能參考在時間軸上靠前的幀，包括之前已經編碼的i幀以及p幀，即前向預測；b幀則可以雙向預測，它的參考幀可以是時間上“過去”的幀。也可以是時間上“將來”的幀，它的參考幀也可以是i幀以及p幀，b幀只能參考其它幀，其本身不能作為其他幀的參考幀，所以他不會引起預測誤差擴散。在具體的編碼中，當遇到b型幀時，先把它讀到快取中，編碼後面的p幀，當前後的參考幀都被編碼以後，再編碼b幀。在解碼端，當解碼解到b幀時，則先將它讀入快取，待到解碼完它後面的p幀，再解碼b幀。
2.2.2預測運動向量的獲取
如果對每個塊的運動向量進行編碼，那麼將花費相當數目的位元數，特別是在選擇小尺寸的塊的情況下。由於一個運動物體會覆蓋多個分塊，所以空間域相鄰塊的運動向量具有很強的相關性。因此，每個運動向量可以根據臨近先前已編碼的塊進行預測，預測得到的運動向量用mvp表示，當前向量和預測向量之間的差值用mvd表示。同時由於物體運動具有連續性，運動向量在時間域也存在一定的相關性，因此也可以用臨近參考幀的運動向量來進行預測。
2.2.3搜尋範圍的確定
當獲取了預測運動向量以後，在參考幀中找到當前塊的對應塊，此點即對應運動向量(o，o)，並以此為基點，向其上下左右擴出運動搜尋範圍大小，此即我們需要的運動搜尋範圍。
搜尋區域的選擇一般是相對於當前塊對稱得，左邊和右邊各有d個畫素，上邊和下邊各有d個畫素。
3.一種新的運動估計快速搜尋演算法
這些年來，許多的快速搜尋演算法都被提了出來，其中比較好的有三步法，四步法，菱形搜尋法等等，它們與全搜尋演算法相比節省了大量的運動時間。可是這些演算法中大部分不論在水平還是在垂直方向上都是規則對稱的.，三步法和四步法等等都是如此，但是在實際的運動影象當中都是水平方向的運動要遠比垂直方向的運動要劇烈的多，這是因為對於一個以常見的現實世界為內容的影片序列來說，它的前後幀之間的差異來源主要有兩個方面：影片目標的運動和影片獲取裝置的運動。影片目標的常見運動集中在水平方向，如汽車和火車的行駛，行人在路上走等；而攝像機的運動一般以平動和水平轉動為主，所以運動向量就應該是以水平方向的運動向量為主。
從運動向量的搜尋過程中我們可以得知，後步的搜尋都是建立在前一步的基礎上的，每一步都為下一步指出了運動向量所在的大致方向，而運動向量又是以水平方向的運動向量為主，所以本演算法中第一步以偏水平方向的十字搜尋模板作為搜尋基礎。
基於偏水平十字及偏向雙鑽石搜尋演算法(dhcdds)主要是將兩種搜尋模版相結合儘可能的以最小的搜尋時間準確的確定最佳匹配點，一種是偏水平十字型搜尋模板，另一種是偏向雙鑽石搜尋模板，其中第一個偏水平十字搜尋模板主要是根據影片影象的運動變化主要是集中在水平方向上的特點來初步確定搜尋的基本位置，第二個偏向雙鑽石搜尋模板是根據偏水平十字搜尋模板的初步定位，進一步使用搜索效果比較理想的雙鑽石搜尋模板來確定當前最佳匹配點，直到當前最佳匹配點在中心點或偏中心點才結束搜尋過程，然後透過比較幾個候選點的sad值的大小來確定最佳匹配點的位置。該快速運動估計搜尋演算法所要搜尋的點數較少，提高了編碼效率。
4.結語
本文主要對於影片壓縮中的運動估計快速搜尋演算法進行了簡單的研究。影片壓縮後的資料流大小的關鍵因素在於能否較好的去除其時間相關性，尋找到最佳的匹配塊。實驗表明在信噪比和位元率變化很小的情況下，搜尋時間大為縮短。文中提出的演算法僅僅採用了搜尋模板的改變來提升搜尋速度，相信再結合其他提升搜尋速度的辦法，比如說提前終止技術等，就能在此基礎上進一步的提高搜尋速度。由於運動估計佔了h.264編碼時間中的大部分，所以運動估計搜尋速度的提高對於h.264的編碼效率是很重要的。