以適應性門檻改進快速移動估測演算法與硬體架構設計

Abstract

在目前的影像壓縮規格中如H.264與MPEG 4等，移動估測的計算是佔總計算量比例最大的部分，所以許多為了減少計算量的快速演算法持續便被設計出來，而其中相對於使用全部搜尋區塊匹配演算法的快速搜尋演算法能減少大量的計算量，目前這一類的快速演算法中以鑽石搜尋演算法為基礎的區塊匹配演演算法能有較佳的效能，但是其中還是含有不必要的多餘計算量，所以我們設計一套提早終止的機制來節省更多的計算量，主要是藉由預測出可能的移動估測結果來避免無效的搜尋步驟，而預測出的數值即為提早終止機制的門檻值。我們從連續畫面中時間域上的關連性來預測出移動估測的結果，以決定出在每一張畫面的移動估測計算前都會更新的門檻值，這個門檻值能依照不同連續影像而改變數值以達到良好的適應性質，而能在不影響移動估測結果的情況下來節省計算量，這樣的提早終止技術可適用於各種快速區塊匹配演算法，而我們將之應用在鑽石搜尋法上設計出一套全新的快速移動估測演算法。為了希望能即時的完成壓縮編碼，所以我們也針對新演算法設計出硬體架構以實現移動估測，在設計上的目標為了減少外部記憶體的讀取量及功率消耗，所以此架構中利用平行處理的方式與設計特殊的記憶體位址產生器來實現此快速移動估測演算法。

In present video compression standard, such as H.264 and MPEG4, the computation of motion estimation is most of total encoding computation. Thus, many fast algorithms for saving computation load have been proposed. The fast search algorithm saves a lot of computation load comparing full search block matching algorithm. In this type of fast algorithm, the block matching algorithm based on diamond search has better performance. But there is unnecessary computation in those fast block matching algorithms. We have designed an early termination technique to save more computation load. This technique tries to avoid unnecessary search step with predicting result of motion estimation. This predictive result is the threshold of early termination technique. We use the relation of temporal domain to predict result in sequence frames. The threshold is set before starting motion estimation of next frame. Thus, this threshold has good adaptability in those different video cases. Because this early termination technique can save computation load without destroying motion estimation, it should be applied to different fast search block matching algorithm. We proposed a novel diamond search algorithm based on early termination. For encoding in real time, we also designed architecture of this novel algorithm to implement. To cope with low off-chip memory utilization and low power consumption, the proposed architecture has parallel schedule and special memory address generator.