以NCC為基礎的有效率影像比對演算法及其在視訊壓縮的應用

Efficient NCC-Based Image Matching Algorithms with Application to Video Coding

潘威豪(Wei-Hau Pan)

指導教授 ： 賴尚宏

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

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

摘要

在這篇論文中，我們提出了兩個基於正規化相關匹配法(NCC)的有效率影像比對演算法，並將之應用於樣型識別與運動估計上。除此之外，我們也展現了一個新型的混合式運動估計方法，並可調式地結合了絕對差值合(SAD)與正規化相關匹配法(NCC)評估方法於視訊壓縮上。
首先，我們提出了一個以NCC為基礎並結合了winner-update演算法及Walsh-Hadamard轉換的快速影像比對方法。Walsh-Hadamard轉換是一個易於計算的正交轉換並有很好的能量集中特性。這個演算法發展了一個交互相關的上界，並階層式的逐一使用Hadamard的參數來做比對。
接下來，我們提出了一個多層式快速基於 NCC的影像比對方法以及一個新型可調式地結合了SAD與NCC評估方法的混合式運動估計方法於視訊壓縮上。我們使用了SAD以及影像梯度的資訊來做為選擇SAD或是NCC的依據。一般來說，使用了NCC為基準來做運動估計，跟以SAD為基準相比，會產生較平坦的差值，並使得視訊的壓縮更有效率。

關鍵字

影像比對 ； 視訊壓縮

並列摘要

In this thesis, we propose two efficient image matching algorithms based on the normalized cross correlation (NCC) criterion for pattern matching and motion estimation, respectively. Moreover, a novel hybrid motion estimation algorithm that adaptively combines the SAD (Sum of Absolute Differences) and NCC measures is presented for video compression.
First, we propose an efficient NCC-based image matching algorithm by applying the winner-update strategy on the Walsh-Hadamard transform, which is an orthogonal transformation that is easy to compute and has great energy packing capability. This efficient algorithm is based on deriving the upper bound for the cross correlation between the corresponding Hadamard coefficients in a hierarchical order. In addition, a multi-level fast NCC-based image matching algorithm and a new hybrid approach for block based motion estimation based on adaptively using the NCC and SAD measures are proposed. We use the SAD value and gradient sum as the criterion to determine which similarity measure to be used for motion estimation for a macroblock. In general, using the NCC as the similarity measure in the motion estimation leads to more uniform residuals than those of using the SAD, thus leading to more efficient video compression.

並列關鍵字

Image Matching ； Video Coding

參考文獻

[1]S. Zhu and K. K. Ma, A new diamond search algorithm for fast block matching motion estimation, IEEE Trans. Image Processing, 9(2):287 -290, 2000.

[2]R. Li, B. Zeng and M.L. Liou, A new three-step search algorithm for block motion estimation, IEEE Trans. Circuits Systems Video Technology, Vol. 4, No. 4, pp. 438-442, Aug. 1994.

[3]L. M. Po and W. C. Ma, A novel four-step search algorithm for fast block motion estimation, IEEE Trans. Circuits Syst. Video Technol., 6:313-317, 1996.

[4]W. Li and E. Salari, Successive elimination algorithm for motion estimation, IEEE Trans. Image Processing, 4(1):105-107, 1995.

[5]X. Q. Gao, C. J. Duanmu, and C. R. Zou, A multilevel successive elimination algorithm for block matching motion estimation, IEEE Trans. Image Processing, 9(3):501-504, 2000.