臺灣博碩士論文加值系統

影像比對在電腦視覺應用中扮演很重要的角色，而發展一個能準確找到對應點的方法使比對更穩定是關鍵，且比對時有效率也是重點，所以此篇論文提出一個方法能同時提升影像比對的效率與準確度。首先相似的影像用SIFT演算法做分析，經過SIFT技術取出特徵後，我們可以利用此兩組特徵描述子，一組建立最佳k-d樹，另一組用近乎最接近鄰近搜尋法去搜尋最佳候選對應點，此搜尋法可以減少很多比對的時間。最後為了提升準確度，我們利用修改過的區域協調控制矯正方法自動消除錯誤的對應點，同時保留下正確的對應點。我們提出的方法經過測試影像資料庫、歪斜和部分扭曲驗證，和其他方法做比較，實驗結果顯示我們的方法可以同時提升SIFT影像比對的效率與準確度。

Image matching plays an important role in many computer vision applications. It is crucial to develop an accuracy correspondence mechanism and make the matching more stable. The efficiency is also the key course of matching. This thesis presents a model of improving both efficiency and accuracy in image matching. Pictures that have similar contents are first analyzed by SIFT algorithm. After the SIFT feature section, we can utilize two groups of descriptors. A group of descriptors building the optimized k-d tree, and the other group of descriptors finding the best candidate match by approximate nearest neighbor searching and reduce a lot of matching time. Finally, we use a Modifiable Area Harmony Dominating Rectification method to eliminate mismatched key-point couples automatically and protect the matching couples. The proposed method is evaluated on test image database and transformation of shearing effect and thin plate splines. Compared with other method,, the performance of our method is promising in improving the efficiency and accuracy for SIFT image matching.

Contents
Abstract i
Acknowledgement i
Contents iii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Literature Survey 5
2.1 Feature Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Key-point Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Recti¯able Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 SIFT Algorithm 18
3.1 Scale-space Extrema Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Key-point localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Orientation Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Key-point Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Key-point Matching and Recti¯cation 29
4.1 Key-point Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 The Standard K-d Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 The Optimized K-d Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4 Approximate Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . 40
4.5 Split Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6 Area Harmony Dominating Recti¯cation Method . . . . . . . . . . . . . . . 47
4.7 Modi¯able Area Harmony Dominating Recti¯cation Method . . . . . . . . . 48
5 Experimental Results 53
5.1 Data Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.1 Data Sets in Shear E®ect . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.2 Data Sets in Thin Plate Splines E®ect . . . . . . . . . . . . . . . . . 60
5.2 Evaluation Method and Set Parameter . . . . . . . . . . . . . . . . . . . . . 67
5.3 Comparison of Exhaustive Search and Our Model . . . . . . . . . . . . . . . 70
5.4 Compare Our Model With Similar Method . . . . . . . . . . . . . . . . . . . 75
6 Conclusion 77
Bibliography 78

Bibliography
[1] T. Tuytelaars and K. Mikolajczyk. Local invariant feature detectors:a survey. Found. Trends. Comput. Graph. Vis., 3(3):177–280, 2008.
[2] D.G. Lowe.Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.
[3] K. Mikolajczyk and C. Schmid.A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10):1615–1630, 2005.
[4] C. Harris and M. Stephens.A combined corner and edge detector. In Alvey vision conference, volume 15, page 50, 1988.
[5] C. Schmid, R. Mohr, and C. Bauckhage. Evaluation of interest point detectors.International Journal of computer vision, 37(2):151–172, 2000.
[6] S.M. Smith and J.M. Brady.SUSAN -A new approach to low level image processing. International Journal of Computer Vision, 23(1):45–78, 1997.
[7] K. Mikolajczyk and C. Schmid. Scale & affine invariant interest point detectors.International Journal of Computer Vision, 60(1):63–86, 2004.
[8] T. Lindeberg. Detecting salient blob-like image structures and their scales with a scale-space primal sketch: a method for focus-of-attention. International Journal of Computer Vision, 11(3):283–318, 1993.
[9] T. Lindeberg. Feature detection with automatic scale selection.International Journal of Computer Vision, 30(2):79–116, 1998.
[10] K. Mikolajczyk and C. Schmid.Indexing based on scale invariant interest points. In Proc. ICCV, volume 1, pages 525–531, 2001.
[11] R.O. Duda and P.E. Hart. Pattern classification and scene analysis. New York, 1973.
[12] D.G. Lowe. Object recognition from local scale-invariant features. In Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, volume 2, 1999.
[13] T. Lindeberg.Direct estimation of affine image deformations using visualfront-end operations with automatic scale selection. In Computer Vision, 1995. Proceedings., Fifth International Conference on, pages 134–141, 1995.
[14] T. Lindeberg and J. G˚arding. Shape-adapted smoothing in estimation of 3-D shape cues from affine deformations of local 2-D brightness structure. Image and Vision Computing, 15(6):415–434, 1997.
[15] A. Baumberg. Reliable feature matching across widely separated views. In IEEE Conference on Computer Vision and Pattern Recognition, 2000. Proceedings, volume 1, 2000.
[16] T. Tuytelaars, L. Van Gool, et al. Content-based image retrieval based on local affinely invariant regions. Lecture Notes in Computer Science, pages 493–500, 1999.
[17] T. Tuytelaars and L. VanGool. Matching widely separated views based on affine invariant regions. International Journal of Computer Vision, 59(1):61–85, 2004.
[18] J. Canny.A computational approach to edge detection. IEEE Transactions on pattern analysis and machine intelligence, pages 679–698, 1986.
[19] T. Kadir and M. Brady.Saliency, scale and image description. International Journal of Computer Vision, 45(2):83–105, 2001.
[20] T. Kadir, M. Brady, and A. Zisserman. An affine invariant method for selecting salient regions in images. In Proceedings of the European Conference on Computer Vision, pages 345–457, 2004.
[21] T. Tuytelaars and L. Van Gool. Wide baseline stereo matching based on local, affinely invariant regions. In British Machine Vision Conference, pages 412–425, 2000.
[22] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust wide-baseline stereo from maximally stable extremal regions. Image and Vision Computing, 22(10):761–767, 2004.
[23] 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, 65(1):43–72, 2005.
[24] K. Mikolajczyk and C. Schmid.Comparison of affine-invariant local detectors and descriptors. In Proc. European Signal Processing Conf, 2004.
[25] M. Donoser and H. Bischof. Efficient maximally stable extremal region (MSER) tracking. In Proceedings of the Conference on Computer Vision and Pattern Recognition, pages 553–560, 2006.
[26] A. Vedaldi. An Implementation of Multi-Dimensional Maximally Stable Extremal Regions. 2007.
[27] J.L. Crowley and A.C. Parker.Representation for shape based on peaks and ridges in the difference of low-pass transform. IEEE Transactions Pattern Anal. Mach. Intellig., 6(2):156–170, 1984.
[28] P. Gaussier, J.P. Cocquerez, E. ETIS, and C. Pontoise.Neural networks for complex scene recognition: simulation of avisual system with several cortical areas. In Neural Networks, 1992. IJCNN., International Joint Conference on, volume 3, 1992.
[29] S. Grossberg, E. Mingolla, and D. Todorovic. A neural network architecture for preattentive vision. IEEE Transactions on Biomedical Engineering, 36(1):65–84, 1989.
[30] T. Lindeberg.Scale-space theory: A basic tool for analyzing structures at different scales. Journal of applied statistics, 21(1):225–270, 1994.
[31] J. Sporring, L. Florack, M. Nielsen, and P.Johansen. Gaussian scale-space theory. Kluwer Academic Publishers Norwell, MA, USA, 1997.
[32] A.P. Witkin et al. Scale-space filtering, April 14 1987. US Patent 4,658,372.
[33] H. Bay, T. Tuytelaars, and L. Van Gool.Surf: Speeded up robust features. Lecture Notes in Computer Science, 3951:404, 2006.
[34] H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool. Speeded-up robust features (SURF). Computer Vision and Image Understanding, 110(3):346–359, 2008.
[35] P. Viola and M. Jones. Rapid Object Detection using a Boosted Cascade of Simple. In Proceedings of CVPR2001, volume 1.
[36] E. Rosten and T. Drummond. Fusing points and lines for high performance tracking. In Tenth IEEE International Conference on Computer Vision, 2005. ICCV 2005, volume 2, 2005.
[37] E. Rosten and T. Drummond. Machine learning for high-speed corner detection. Lecture Notes in Computer Science, 3951:430, 2006.
[38] J.R. Quinlan. Induction of decision trees.Machine learning, 1(1):81–106, 1986. 82
[39] L.M.J. Florack, B.M. ter Haar Romeny, J.J. Koenderink, and M.A. Viergever. General intensity transformations and differential invariants. Journal of Mathematical Imaging and Vision, 4(2):171–187, 1994.
[40] F. Mindru, T. Tuytelaars, L.V. Gool, and T. Moons. Moment invariants for recognition under changing viewpoint and illumination. Computer Vision and Image Understanding, 94(1-3):3–27, 2004.
[41] W.T. Freeman and E.H. Adelson. The design and use of steerable filters.IEEE Transactions on Pattern analysis and machine intelligence, 13(9):891–906, 1991.
[42] G. Carneiro and A.D. Jepson.Multi-scale phase-based local features. In 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings, volume 1, 2003.
[43] Y. Ke and R. Sukthankar.PCA-SIFT: A more distinctive representation for local image descriptors. In Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, volume 2.
[44] J.H. Friedman, J.L. Bentley, and R.A. Finkel.An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), 3(3):209–226, 1977.
[45] J.S. Beis and D.G. Lowe.Shape indexing using approximate nearest-neighbour search inhigh-dimensional spaces. In 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1997. Proceedings., pages 1000–1006, 1997.
[46] S. Arya and D.M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 271–280. Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 1993.
[47] S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A.Y. Wu.An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891–923, 1998.
[48] S. Maneewongvatana and D.M. Mount. Its okay to be skinny, if your friends are fat. In Center for Geometric Computing 4th Annual Workshop on Computational Geometry, 1999.
[49] Z.Wei, X. Weisheng, and Y. Youling. Area Harmony Dominating Rectification Method for SIFT Image Matching. In Electronic Measurement and Instruments, 2007. ICEMI’07. 8th International Conference on, pages 2–935, 2007.
[50] J.J. Koenderink. The structure of images. Biological cybernetics, 50(5):363–370, 1984.
[51] M. Brown and D.G. Lowe.Invariant features from interest point groups. In British Machine Vision Conference, Cardiff, Wales, pages 656–665, 2002.
[52] J.L. Bentley. Multidimensional binary search trees used for associative searching. 1975.
[53] S. Arya, D.M. Mount, and O. Narayan.Accounting for boundary effects in nearest-neighbor searching. Discrete and Computational Geometry, 16(2):155–176, 1996.
[54] D.M. Mount and S. Arya. ANN: A library for approximate nearest neighbor searching. In CGC 2nd Annual Fall Workshop on Computational Geometry. Citeseer, 1997.
[55] S. Maneewongvatanaand D.M. Mount. Analysis of approximate nearest neighbor searching with clustered point sets. Arxiv preprint cs.CG/9901013, 1999.
[56] S. Arya and H.Y.A. Fu.Expected-case complexity of approximate nearest neighbor searching. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 379–388. Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 2000.
[57] Thepackages contain images and homographies between image pairs. http://www.robots.ox.ac.uk/ vgg/research/affine/.html.
[58] J.L. Kuo, DT Lin, EC Lin, and SY Huang. Image Analysis Systems for Protein Two Dimensional Gel Electrophoresis. Department of Computer Science and Information Engineering Chung-Hua University, 2002.
[59] G. Donato and S. Belongie. Approximation methods for thin plate spline mappings and principal warps. Computer Vision–ECCV, pages 28–31, 2002.