快速與穩健的樣型比對演算法及其應用

Efficient and Robust Pattern Matching Algorithms for Different Applications

魏守德(Shou-Der Wei)

指導教授 ： 賴尚宏

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

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

摘要

樣型識別在電腦視覺與影像處理的領域上有很多的應用，比如說立體對應，物體追蹤，物體偵測，樣型識別與視訊壓縮等等。最常用的相似度量測的方法有絕對差值合 (sum of absolute differences, SAD), 平方差值合 (the sum of squared differences, SSD)與正規化相關匹配法 (normalized cross correlation, NCC)。SSD相似度量測常用於物體追蹤與偵測，以SSD為主的搜尋法是藉由計算模板與在被搜尋的影像上的每一區塊之間的歐幾里德距離，而找到距離最小的候選區塊。傳統的完全搜尋法非常的耗時。在實際的應用上非常的需要快速有效率的方法。尤其是在視訊壓縮裡，區塊的移動向量估測是在視訊編碼中不可或缺的，可以用來找到時間軸上的相關性, 用來減少兩張連續畫面的重複部份，進而達到高壓縮率。雖然使用NCC 當作相似度量測能夠在光源均勻變化下找到最相似的位置，但是此種方法在光源不平均的情況下仍然不能夠正確的找到最佳位置。在某些實際應用上，比如說工業檢測上的影像定位(image alignment)與人臉辨識(face recognition)，經常會遇到在不平均光源下找到最相似位置的問題。這此論文中，我們提出了三種不同類別的新型樣型比對演算法。第一種類別是以SAD與SSD為相似度量測為基礎的樣型比對方法，主要應用於視訊壓縮上的區塊移動向量偵測。而我們所提出來的第二種類別是以NCC 為基礎的快速影像比對方法，能夠抵抗均勻光源的變化。除了以上兩種以外，我們還發展了一個穩健且快速的影像比對方法可以用於工業檢測上的影像定位與不平均光源的人臉偵測上。

關鍵字

樣型識別 ； 正規化相關匹配法 ； 影像定位 ； 快速演算法 ； 絕對差值合 ； 平方差值合

並列摘要

Pattern matching has been widely used in many applications related to computer vision and image processing, such as stereo matching, object tracking, object detection, pattern recognition and video compression, etc. The most popular similarity measures are the sum of absolute differences (SAD), the sum of squared differences (SSD) and the normalized cross correlation (NCC). The SSD measure is very popular similarity measure for object tracking and object detection by calculating the Euclidean distance between the pattern and the candidate in the search image to find the one with the minimum distance. The traditional full search method is very time-consuming. For practical applications, an efficient pattern matching algorithm is strongly demanded especially for motion-compensated video compression. Although using NCC as the similarity measure can find the pattern under uniform lighting variation, but it cannot work well under uneven lighting condition. For the practical applications of image alignment for industrial inspection and face recognition, the problem becomes to finding a given pattern in the search image under uneven lighting conditions. In this dissertation, we propose three types of new pattern matching algorithms. The first one contains several fast template matching techniques based on minimizing SAD or SSD measure for block-based motion estimation in video compression. Secondly, we propose efficient normalized cross correlation algorithms for robust pattern matching under uniform illumination variations.. In addition to the above two categories, we also develop a robust and efficient image matching algorithm that can be applied to the image alignment for industrial inspection and the face recognition under lighting variations.

並列關鍵字

pattern matching ； normalized cross correlation ； image alignment ； fast algorithm ； sum of absolute differences ； sum of squared differences

參考文獻

[1] M. Gharavi-Alkhansari, "A fast globally optimal algorithm for template matching using low-resolution pruning", IEEE Trans. on Image Processing, Vol. 10, No. 4, pp. 526-533, April 2001.

[2] Y. Hel-Or and H. Hel-Or, "Real-time pattern matching using projection kernels," IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 27, No. 9, pp. 1430-1445, Sept. 2005.

[3] S. Zhu and K. K. Ma, "A new diamond search algorithm for fast block-matching motion estimation," IEEE Trans. Image Processing, Vol. 9, No. 2, pp. 287-290, Feb. 2000.

[4] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishinguro, "Motion compensated interframe coding for video conferencing," Proc. Nat. Telecommun. Conf., 1981.

[5] 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.