內容感知的快速運動估計演算法

Abstract

在這篇論文中，我們提出內容感知的快速運動估計演算法 (CAFME, Content-Aware Fast Motion Estimation Algorithm) 可以減少運動估計 (Motion Estimation) 所需要的計算量，並且保持幾乎相同的壓縮效率 (Coding Efficiency)。運動估計大致可以分為搜尋 (Search Phase) 與比對 (Matching Phase) 。在搜尋部分，我們基於影片的特性提出動態搜尋範圍演算法 (SDSR, Simple Dynamic Search Range) 以減少需要檢查的搜尋點。在比對部分，我們整合連續排除演算法(SEA, Successive Elimination Algorithm) 與積分影像 (Integral Frame) ，提出一套適合H.264/AVC壓縮標準的連續排除演算法。此外，我們以比對誤差SAD (Sum of Absolute Difference)為量測，提出提前結束演算法 (ETA, Early Termination Algorithm) 。 我們所提出的動態搜尋範圍演算法的基本概念是利用運動向量 (Motion Vector) 在空間 (Temporal) 與時間 (Spatial) 的相關性，對目前方塊的搜尋範圍作調整。而我們提出的連續排除演算法則是利用積分影像來計算方塊和 (Block Sum) 且調整原本的連續排除演算法架構，使在運動估計時計算SAD的次數可以減少並且重複利用。最後，提前結束演算法則是使用目前方塊預測SAD與目前找到最好的SAD來衡量運動向量的準確度，以決定是否要結束目前方塊的運動估計。在H.264/AVC參考軟體JM9.4上實作，實驗結果顯示我們提出的方法所減少的搜尋點可達93.1%，減少編碼時間大約42%，而位元率與PSNR幾乎相同。

In this paper, we propose the Content-Aware Fast Motion Estimation Algorithm (CAFME) that reduces computation of motion estimation (ME) while maintains almost the same coding efficiency. Motion estimation can be divided into two phases, searching phase and matching phase. In searching phase, we propose the Simple Dynamic Search Range algorithm (SDSR) based on video characteristics to reduce the number of search points (SP). In matching phase, we integrate the Successive Elimination Algorithm (SEA) and the integral frame to develop a new SEA for H.264/AVC video compression standard, called Successive Elimination Algorithm with Integral Frame (SEAIF). Besides, based on sum of absolute difference (SAD), we also propose the Early Termination Algorithm (ETA) to terminate motion estimation of current block early. The basic idea of Simple Dynamic Search Range algorithm is to adjust the search range of current block by using temporal and spatial correlations of motion vector (MV). Our SEAIF uses “integral frame” to compute block sum and reuses SAD already computed. Finally, the proposed Early Termination Algorithm uses prediction of SAD of current block to measure the accuracy of matching, and then decides to terminate motion estimation or not. We implement in H.264/AVC reference software JM9.4 and the experimental results show that our proposed algorithm can reduce the number of Search Points about 93.1%, encoding time about 42%, while maintains almost the same bitrate and PSNR.