| Abstract: | 自從2001年Joint Video Term的MPEG群組以及VCEG群組共同開發H.264/MPEG-4 Part10 Advanced Video Coding之後，許多新的特性便一直是大家討論的重點，其中多張參考畫面更是大大的增加位移估測演算法搜尋能力。雖然新的標準壓縮效能方面遠遠勝過其他先前所提出的標準，但是編碼的計算複雜卻無法達到即時(real-time)，對於目前H.264標準的參考軟體， JM9.2版本所採用的快速移動估測方法為非對稱多解析度六角搜尋演算法(UMHexagonS)，在移動估測中，為了尋找最佳的移動向量，UMHexagonS演算法的混合式移動搜尋策略方式明顯的優於其他演算法(FS, 3TT, 4TT, DS,…etc.)。但是，相較於其他演算法，UMHexagonS演算法的計算複雜度以及不容易被實現的問題也隨之而產生。在本論文中，我們針對這個問題，提出一個單純並有效率的移動搜尋演算法，所提的演算法藉由更精確的預測初始搜尋中心能避免尋找到區域最佳解，另外，我們提出單一搜尋策略讓硬體實現問題能被有效解決。實驗結果顯示，本篇論文當中所提的演算法明顯的加速位移向量估測時間，大幅度的降低搜尋點數，並且客觀影像評估(Peak Signal to Noise Ratio)以及位元率(Bitrate)方面與H.264採用的UMHexagon演算法幾乎無差異。
In the past years, video coding experts from ITU-T H.264 and ISO/IEC MPEG-4 Advanced Video Coding (AVC) group formed the Joint Video Term (JVT) to develop the emerging standard. H.264/AVC has achieved significant rate-distortion efficiency by many useful video encoding and decoding tools. Compared with H.263, the new technique includes motion estimation (ME) with variable block sizes and multiple reference frames, intra prediction, 4×4 block based residue coding, adaptive block size transform, in-loop deblocking filter, …, etc. However, the motion estimation process concerns greatly on computational complexity. Hence, the algorithm on fast motion estimation becomes one of the most important issues in the development of H.264/AVC.
In the new version reference software JM9.2 of H.264 standard, the UMHexagonS motion estimation algorithm is adopted to find the best motion vector for video coding. The hybrid search strategies have significantly outperformed other algorithms (FS, 3TT, 4TT, DS, …, etc.). However the highly computational complexity leads the codec to become too complex and hard to be implemented in real time applications. In this work, we propose an efficient algorithm by using the precision initial search and simple search strategies to finish the motion estimation. Experimental results indicate that the proposed method can obtain good performances. Through the proposed features, the coding performance can be improved significantly, and the computation complexity of the integer pixel motion estimation of H.264 is also decreased tremendously. In this thesis, a new fast motion estimation algorithm, Hierarchical Single Cross Search (HSCS), is proposed for H.264. |
