近年來人機互動以及工業自動化的興起，影像分析的相關演算法顯得日益重要，這些領域的應用大多透過影像當中的資訊與實際物體進行互動，並達到特定的目的。如何精確並快速分析必要的資訊，已成為致力發展的目標。為了獲取影像中特定圖樣的資訊，模板匹配已經成為其中重要的技術之一。本論文提出一種最佳化搜尋的計算方式解決模板匹配的問題，在不需要對影像進行特徵分析的情況下能準確並快速的找到特定圖樣所在的位置、大小及旋轉角度。當擁有特定圖樣以及影像的資訊時，首先由無窮多的轉換式當中粗略的取出轉換式集合，接著利用絕對差值合對取出的轉換式進行評估，並利用事先決定的限制條件來判斷是否要繼續進行最佳化搜尋。在進行最佳化搜尋時，先將集合中較差的轉換式去除，接著利用剩餘的轉換式進行小範圍的搜尋並找出新的轉換式。當找出一組新的轉換式集合時，就可以持續進行評估、收斂判斷及精細搜尋等步驟直到集合收斂或達到搜尋次數上限為止，最後便可找出最佳的轉換式。

In recent years, algorithms of image analyses have been important since rise of human-computer interaction and industrial automation. Applications in these fields are about interactions with actual objects through image information for a specific purpose. How to accurately and quickly analyze necessary information has become a primary objective. In order to obtain information of a specific pattern in an image, template matching becomes an important technology. This thesis presents a solution to a template matching problem using an optimal search. A proposed method can accurately and quickly find locations, scales, and orientations of the specific pattern without analyzing image features. When information about a specific pattern and an image is obtained, a transformation set is approximately retrieved from infinite transformations. Then, the transformation set with sums of absolute differences is evaluated to judge whether to continue the optimal search under restrictions. During the optimal search, relatively poor transformations are removed. Then, the optimal search with the rest of the transformations is done in a small area to find new transformations. After the new transformations is found, evaluations, judgements, and fine searches are performed until a convergence or the maximum number of searches is achieved. Finally, the best transformation is optimally computed.

[1]J.E. Bresenham, "Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal, pp. 25–30, 1965.
[2]J.E. Bresenham, "A Linear Algorithm for Incremental Digital Display of Circular Arcs," Communications of the ACM, pp. 100–106, 1977.
[3]M.S. Choi and W.Y. Kim, "A Novel Two Stage Template Matching Method for Rotation and Illumination Invariance," Pattern Recognition, pp. 119–129, 2002.
[4]C. Hundt and M. Lis’kiewicz, "Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations," Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 5162, Springer, pp. 395–406, 2008.
[5]R. Hartley and A. Zisserman. "Multiple View Geometry in Computer Vision," Cambridge University Press, 2008.
[6]H.Y. Kim and S.A. Araújo, "Grayscale Template-Matching Invariant to Rotation, Scale, Translation, Brightness and Contrast," IEEE Pacific-Rim Symposium on Image and Video Technology, Lecture Notes in Computer Science, Vol. 4872, pp. 100–113, 2007.
[7]H.Y. Kim, "Rotation-Discriminating Template Matching Based on Fourier Coefficients of Radial Projections with Robustness to Scaling and Partial Occlusion," Pattern Recognition, Vol. 43, No. 3, pp. 859-872, 2010.
[8]S. Korman, D. Reichman, G. Tsur, and S. Avidan, "FAsT-Match: Fast Affine Template Matching," Conference on Computer Vision and Pattern Recognition, pp. 2331–2338, 2013
[9]S. Korman, D. Reichman, G. Tsur, and S. Avidan, "Construction of the Net," 2013
[10]S. Korman, D. Reichman, G. Tsur, and S. Avidan, "Proof of the Theorem 3.1," 2013
[11]B.D. Lucas and T. Kanade, "An Iterative Image Registration Technique with an Application to Stereo Vision," International Journal of Computer Vision, pp. 674–679, 1981.
[12]J.P. Lewis, "Fast Normalized Cross-Correlation," Industrial Light & Magic, 1995.
[13]D.G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints," International Journal of Computer Vision, pp. 91–110, 2004.
[14]K. Mikolajczyk and C. Schmid, "A Performance Evaluation of Local Descriptors," IEEE Transaction on Pattern Analysis and Machine Intelligence, pp. 1615–1630, 2005.
[15]K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, and L.V. Gool, "A Comparison of Affine Region Detectors," International Journal of Computer Vision, pp. 43–72, 2005.
[16]J.M. Morel and G. Yu, "ASIFT: A New Framework for Fully Affine Invariant Image Comparison," Society for Industrial and Applied Mathematics Journal on Imaging Sciences, pp. 438–469, 2009.
[17]C.H. The and R.T. Chin, "On Image Analysis by the Methods of Moments," IEEE Transaction on Pattern Analysis and Machine Intelligence, pp. 496–513, 1988.