可適應運動量變化之運動向量估計演算法及H.264/AVC運動向量估計架構設計

Adaptive Motion Estimation Algorithm for Varied Motion Contents and VLSI Motion Estimation Architecture Design for H.264/AVC

卓傳育(Chuan-Yu Cho)

指導教授 ： 王家祥

國立清華大學/電機資訊學院/資訊工程學系/博士(2006年)

https://doi.org/10.6843/NTHU.2006.00009

摘要

運動向量估計演算法在現今的視訊編碼器的設計上扮演了舉足輕重的角色，因為其佔了視訊編碼器中一半以上的運算量，且運動向量估計的結果也與壓縮的品質習習相關。儘管已有相當多的快速區塊搜尋演算法被提出來降低運動向量估計的複雜度，卻沒有任何一種可以真正滿足真實世界中各種不同的影片類型—不同的快速區塊搜尋演算法只適用於特定類型的影片。因此在本論文中，首先我們便著眼於如何設計一個快速，同時又適用於各種不同類型影片的演算法。

快速及對不同影片的調適能力是我們的主要目標。為了達到這個目的，在本論文中我們分析了現有快速區塊演算法所適用的各種不同影像類型。然後引進優先序列的編碼觀念，經由探討在優先序列中的運動向量分布情形，我們設計了一個可依據影片特性動態調整搜尋策略的演算架構。將三種現有的快速區塊搜尋演算法搭配使用，截長補短設計出一個全新的可適應性快速區塊搜尋演算法。

在最新的H.264視訊壓縮標準中，為了進一步提高對各種影片類型的壓縮效率，採用了可變動區塊大小的運動向量估計演算法，並引進了多重參考影像的機制。雖然有效地提昇了壓縮品質，多達259種可能的區塊分割及多重參考影像的可能性，卻大大地增加了運動向量估計的複雜度。因此在論文的第二部分，我們針對如何有效率地實現H.264運動向量估計演算法提出了一個快速的搜尋架構。

H.264的區塊搜尋演算法可以經由一個由小到大的SAD合併樹簡化成只要一次的4×4全域區塊搜尋。但大量的中間運算結果仍需要非常大的記憶體空間來儲存，區塊分割模式的決定也要花費不少的運算量。有鑑於此，我們設計內嵌式的合併架構並即時計算R-D結果，隨時保存最佳的模式估算結果。不僅僅省去大量暫存記憶體的需求，對快取記憶體的使用效率也大大的提昇。而我們提出的管線式多重參考影像架構，更進一步將內嵌比較及記憶體節省的觀念推廣到適於多重參考影像的應用中，提供H.264的運動向量估計一個更有效率的實現架構。

關鍵字

視訊編碼 ； 視訊壓縮 ； H.264 ； AVC ； MPEG

並列摘要

Motion estimation (ME) plays an important role in H.264 not only because it has extremely computational complexity, but also it affects the following block coding modes as well as the final coded bit-stream size. Therefore, studying on advance ME algorithms is one of the most efficient ways to improve the coding efficiency of a video codec. In thesis, we exhibit two ME schemes with software- and hardware-based implementations, respectively.

Based on the studying on fast block-matching algorithms (FBMAs) and a priority list, the software-based ME scheme is started with a study on FBMAs, and then their efficiencies are illustrated in terms of algorithm checking points. A priority list is introduced to help with classification of motion content types of real world sequences. After doing statistical analyses on the proposed priority list and FBMAs, we propose a motion-content adaptive FBMA, which can adaptively switching searching strategies among three different FBMAs to maximize the coding efficiency under the considerations of motion-content variations.

The latest H.264/AVC video coding standard adopts the variable block size (VBS) block partitions and multiple reference frames (MRF), which make the motion-compensation stage become extreme complicated. To save intermediate memory and maximum the hardware utilization, we propose an embedded merging scheme with a pipeline-based MRF extension. With this embedded design, only one copy of intermediate memory is required and fully utilization is expected after fulfilling the pipeline stages.

並列關鍵字

MPEG ； H.264 ； Motion Estimation ； Block Matching ； embedded merging scheme

參考文獻

[1] T. Sikora, “Trends and perspectives in image and video coding,” Proceedings of the IEEE, vol. 93, no. 1, Jan. 2005.

[2] T. Sikora, “MPEG digital video coding standards,” IEEE Signal Processing Magazine, vol. 14, no. 5, pp.82–100, Sep. 1997.

[4] D. Marpe, H. Schwarz, and T. Wiegand, “Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard,” IEEE Transaction on Circuits System for Video Technology, vol. 13, no. 7, pp.620–636, July 2003.

[7] Y.-W. Huang, T.-C. Wang, B.-Y. Hsieh and L.-G. Chen, “Hardware Architecture Design for Variable Block Size Motion Estimation in MPEG-4 AVC/JVT/ITU-T H.264”, in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2003), vol. 2, pp.II–796 – II–799, May 2003.

[9] “Video coding for low bit rate communication,” ITU-T Rec. H.263, v1: Nov. 1995, v2: Jan. 1998, v3: Nov. 2000.