H.264/MPEG-4 AVC 移動估測的快速演算法與架構設計

Abstract

隨著高解析數位電視時代的來臨，為了兼顧大且精緻的畫面，高壓縮率規格(H.264)是我們現行的解決方案。它不僅可有效節省儲存媒體所需的空間，同時也可在現行的通訊環境下允許傳輸更高解析的畫面。伴隨著種種好處而來的就是極之龐大的運算量，而大量的快速演算法也因此應運而生。如何兼顧畫質和運算速度成了當前最重要的課題，而這也是本篇論文的主旨。

根據已出版的文獻，位移估測是整個壓縮過程中最為費時的。更進一步去了解這個部份，我們可以把他大致上分為整數位移估測和分數位移估測。在原始演算法的條件下，由於搜尋範圍較大整數位移估測佔去了絕大部分的時間。因此我們非常直覺的認為，若能大幅減少搜尋範圍又能使畫質維持差不多水準將可以有效節省壓縮時程，我們提出的快速演算法能夠針對不同解析畫面達到88% (352 x 288)和75%(720 x 480)的節省。分數位移估測在原始演算法的架構下，由於搜尋點數遠少於整數位移估測所以在整個壓縮的過程中並沒有決定性的影響。但隨著整數位移估測快速演算法的發展，分數位移估測搜尋點數所佔的比例慢慢升高，分數位移估測快速演算法也愈來愈有存在的必要性。在單一樣式錯誤表面的假設下，我們利用特定點的錯誤數值去預測整個搜尋視窗的錯誤表面。除此之外，我們也引進了提前終止的技術。此分數快速位移估測部分可以減少超過50%的運算量。在整數和分數位移估測同時使用快速演算法的情形下，以1280 x 720為測試解析度，我們可以加速總壓縮時間達20倍之鉅。另外一種常見的解決方式是利用硬體平行化同時處理多筆資料以達到加速的目的。在分數位移估測方面，拜快速演算法之賜，我們的架構可以減少將近40%面積和加速14%。

With modern day advances in computer processing and multimedia applications, improvements in the area of image processing and video compression are analogous. Video compression allows the reduction of high-resolution video into a more compact memory space to thereby reduce storage and video processing resources during playback.

According to the literature published before, we can find that the motion estimation process is the most time consumed part. To further realize this process, we can mainly divide it into two parts: integer motion estimation and fractional motion estimation. Integer motion estimation cost most part of time under the original algorithm unchanged. The main reason is that the search window is too large. So we have a very simple idea that we want to decrease the search window. We can reduce 88% (input sequence as CIF size) and 75% (input sequence as D1 size) search points respectively. Fractional motion estimation will not affect obviously under the original condition. But when the fast algorithm is applied for integer motion estimation, the portion of encoding time due to fractional motion estimation is getting larger. Based on the assumption of uni-modal error surface, we want to use the results of half pixel step to predict the slope of error surface. We also apply early termination technique. We can get 50% search points reduction in this part. By applying both fast algorithms, we get 20 times speed up with the input sequence size as 1280 x 720. Making use of hardware parallelism to speed up is also a common method in H.264 research field. By the benefit of applying fast fractional motion estimation algorithm, we decrease 40% area and speed up by 14% in our fast fractional motion estimation architecture.