臺灣博碩士論文加值系統

利用影像技術進行空間資料之獲取一直是空間資訊技術中核心工作之一，例如使用立體對影像重建三維模型、影像校齊、影像鑲嵌、影像檢索等工作中，共同的特點是必需從影像中提取適當數量之特徵點作為相關處理之依據。以立體對影像重建三維模型為例，傳統上一般均使用區域基礎(像元灰度值)作為影像匹配運算之基礎，可以達到次像元等級高精度量測之目的，但其中仍存在有不易解決之困難，如兩影像間尺度、攝影傾角及光照條件之差異及影像中之均調區等均可能造成影像匹配之失敗。

本研究援引SIFT演算法於立體對影像匹配與遙測影像檢索之應用，研究結果顯示，該演算法對影像尺度、角度及光照等差異的不變性，並於立體對影像中，對點特徵提取及影像匹配處理提供重要的應用，無論在紋理明顯(如建物、道路)或均調區域(如植被)均具有良好之匹配結果；配合核線幾何約制，可加速運算效率，並提升匹配成功點位之可靠度與精確度，可以解決目前使用區域基礎之匹配方法所面臨的困難。在影像檢索之應用，更明確顯示SIFT演算法在基於內容檢索及多目標快速檢測之優越性。

Utilize the image technology to acquire geo-spatial data is one of the main purposes in geo-spatial information technology, such as to extract the proper feature points while using the stereo image to reconstruct the 3D model, image registration, image stitching and image retrieval for being the basis for related use. For instance, the area-based matching is traditionally used in the stereo image to 3D model reconstruction for the base of the image matching calculation. Even if the area-based matching can achieve the sub-pixel and increase the high-precision measuring, the area-based matching still can not surmount the difficulty of image matching such as the different scale, rotation, illuminance and homogeneous regions in the two images.

This study cite the application of SIFT algorithm to stereo image matching and remote sensing images retrieval. The result indicated the invariant to image scale, rotation and illuminance and shown to provide the considerable application in point feature extraction and image matching, both distinctive texture and homogeneous regions can gain the favorable matching result. Area-based matching failure is solved by integrating SIFT algorithm and epipolar constraint which can speed up the calculation efficiency and increase the reliable and precision of the matching point. The result of image retrieval application shown the superiority of SIFT algorithm in content-based Image retrieval and multi-object retrieval.

摘要---------------------------------------------------------I-
Abstract-----------------------------------------------------II-
致謝---------------------------------------------------------III-
目錄---------------------------------------------------------IV-
表目錄-------------------------------------------------------VII-
圖目錄-------------------------------------------------------VIII-
第一章、緒論-------------------------------------------------1-
1.1 前言------------------------------------------------1-
1.2 研究動機與目的--------------------------------------1-
1.3 研究方法------------------------------------------------2-
1.4 研究流程------------------------------------------------3-
1.5 論文架構------------------------------------------------3-

第二章、文獻回顧---------------------------------------------5-
2.1 SIFT演算法相關應用----------------------------------5-
2.1.1 物件識別(Object Recognition)--------------------5-
2.1.2 影像檢索(Image Retrieval)-----------------------7-
2.1.3 自動影像拼接(Automatic Image Stitching)---------8-
2.1.4 機器人定位(Robot Location)---------------------10-
2.1.5 擴增實境(Augmented Reality)--------------------12-
2.2 SIFT演算法改進算法與比較---------------------------13-
2.3 立體匹配相關研究---------------------------------------15-
2.3.1 立體匹配關鍵技術-------------------------------------16-
2.3.2 特徵空間---------------------------------------------16-
2.3.3 相似性評估-------------------------------------------17-
2.3.4 搜尋空間---------------------------------------------19-
2.3.5 搜尋策略---------------------------------------------21-
2.4 立體匹配演算法分類-------------------------------------21-
2.4.1 區域匹配演算法---------------------------------------22-
2.4.2 特徵匹配演算法---------------------------------------23-

第三章、SIFT演算法相關理論與技術----------------------------25-
3.1 影像特徵簡介---------------------------------------25-
3.1.1 點特徵提取算法---------------------------------------25-
3.1.1.1 Moravec 角點檢測演算法-----------------------------25-
3.1.1.2 Harris 角點檢測演算法------------------------------28-
3.2 SIFT演算法-----------------------------------------31-
3.2.1 尺度空間極值求取--------------------------------------34-
3.2.1.1 高斯差分（DoG）建立多尺度空間影像------------------34-
3.2.1.2 DoG 影像極值---------------------------------------38-
3.2.2 特徵點位置的確定-------------------------------------39-
3.2.3 特徵點最大梯度方向之確定-----------------------------41-
3.2.4 特徵點描述符-----------------------------------------43-
3.2.5 SIFT算法匹配與除錯-----------------------------------44-
2.3.5.1 KD-Tree--------------------------------------------44-
2.3.5.2 RANSAC除錯-----------------------------------------50-
3.3 實驗與分析---------------------------------------------54-

第四章、影像幾何相關理論------------------------------------56-
4.1 核線幾何（Epipolar Geometry）----------------------56-
4.2 基礎矩陣（Fundamental Matrix）-------------------------57-
4.2.1 基礎矩陣定義-----------------------------------------57-
4.2.2 基礎矩陣推算法---------------------------------------60-
4.2.2.1 基礎矩陣之線性解法---------------------------------61-
4.2.2.2 基礎矩陣之線非性解法-------------------------------62-
4.2.2.3 RANSAC基礎矩陣推估法-------------------------------64-
4.3 實驗與分析---------------------------------------------66-

第五章、SIFT演算法用於立體對影像匹配研究--------------------70-
5.1 前言-----------------------------------------------70-
5.2 SIFT演算法基本測試---------------------------------72-
5.2.1 旋轉不變性匹配測試------------------------------73-
5.2.2 尺度不變性匹配測試------------------------------74-
5.2.3 光照影像敏感度匹配測試--------------------------75-
5.3 SIFT演算法用於立體對影像匹配-----------------------75-
5.3.1 一般近景攝影影像--------------------------------76-
5.3.2 特定物件影像------------------------------------81-
5.4 SIFT演算法匹配精度與可靠度評估---------------------90-
5.5 核線約制之SIFT演算法-------------------------------99-
5.6 核線約制之SIFT演算法精度評估-----------------------100-
5.7 核線約制應用於立體對匹配之討論---------------------108-

第六章、SIFT演算法用於影像檢索之研究------------------------111-
6.1 基於內容影像檢索(CBIR)簡介-------------------------111-
6.2 基於SIFT演算法影像檢索---------------------------------114-
6.2.1 目標影像之大小與影像定位之測試-----------------------116-
6.2.2 影像檢索使用-----------------------------------------119-
6.3 影像區(patch)快速定位---------------------------------121-
6.4 多目標檢索之應用----------------------------------128-

第七章、結論與建議------------------------------------------134-

參考文獻----------------------------------------------------136-

[ 1] David G. Lowe, 2004, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110
[ 2] David G. Lowe, 1999, "Object recognition from local scale-invariant features," International Conference on Computer Vision, Corfu, Greece (September 1999), pp. 1150-1157
[ 3] Loncomilla, P.[Patricio], Ruiz-del-Solar, J.[Javier], 2005, "Improving SIFT-Based Object Recognition for Robot Applications, " LECTURE NOTES IN COMPUTER SCIENCE, 2005, NUMB 3617, pages 1084-1092.
[ 4] F. Rothganger, S. Lazebnik, C. Schmid, and J. Ponce., 2006, "3D Object Modeling and Recognition from Photographs and Image Sequences",Toward Category-Level Object Recognition, Springer-Verlag Lecture Notes in Computer Science vol. 4170, J. Ponce, M. Hebert, C. Schmid, and A. Zisserman (eds.), 2006, pp. 105-126.
[ 5] Yan Ke, Rahul Sukthankar, Larry Huston, 2004, "Efficient Near-duplicate Detection and Sub-image Retrieval," Proceedings of ACM International Conference on Multimedia (MM), 2004, IRP-TR-04-07.
[ 6] Stoettinger, J. Hanbury, A. Sebe, N. Gevers, T., 2007, "Colour Interest Points for Image Retrieval," Image Processing, 2007. ICIP 2007. IEEE International Conference on, 16 2007-Oct. 19 2007 I - 169-I – 172.
[ 7]H. Su, D. Crookes, A. Bouridane, and M. Gueham, 2007, "Shoeprint Image Retrieval Based on Local Image Features," School of EEE and CS, Queen’s University Belfast, pages 387-392.
[ 8] Moravec, http://www.cim.mcgill.ca/~dparks/CornerDetector/mainMoravec.htm
[ 9] M. Brown and D. G. Lowe, 2003, "Recognising Panoramas," 13-16 Oct. 2003 Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 1218-1225 vol.2.
[10] Autopano-SIFT, http://user.cs.tu-berlin.de/~nowozin/autopano-sift/
[11] hugin - Panorama photo stitcher, http://hugin.sourceforge.net/
[12] Stephen Se, David Lowe, and James J. Little.,2000, "Vision-based mobile robot localization and mapping using scale-invariant features,". submitted to ICRA-00, 2000. http://citeseer.ist.psu.edu/se01visionbased.html
[13] Dr. Lisa Spencer, 2006 , "Writing Video Applications", Opencv Learning Opencv, http://www.cs.ucf.edu/~lspencer/vid_app.pdf
[14] Chunrong Yuan, 2006, "Markerless Pose Tracking for Augmented Reality,". ISVC (1) 2006: 721-730
[15] K. Mikolajczyk and C. Schmid.,2003, "A performance evaluation of local
descriptors,". In Proceedings of Computer Vision and Pattern Recognition, June 2003.
[16] Y. Ke and R. Sukthankar,2004 , "PCA-SIFT: A More Distinctive Representation for Local Image Descriptors," Computer Vision and Pattern Recognition, 2004
[17] Herbert Bay, Tinne Tuytelaars and Luc Van Gool, 2006, "SURF: Speeded Up Robust Features", Proceedings of the 9th European Conference on Computer Vision, Springer LNCS volume 3951, part 1, pp 404--417, 2006.
[18] Moravec H P., 1979, "Visual mapping by a robot rover", Proc. of 6th IJCAI, 1979:589-600
[19] Harris C, Stephens M., 1988, "A combined corner and edge detector", Proc. Alvey Vision Conf., 1988: 147-151
[20] J.J. Koenderink, 1984, "The structure of images", Biological Cybernetics,50:363-396, 1984.
[21] T. Lindeberg, 1994, "Scale-space theory: A basic tool for analysing structures at different scales", Journal of Applied Statistics, 21(2):224-270, 1994.2(60):91-110
[22] Martin A. Fischler and Robert C. Bolles, June 1981, "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24: 381–395.
[23] Z.Zhang, R. Deriche, O. Faugeras, and Q. Luong., 1995, "A Robust Technique for Matching two Uncalibrated Images through the Recovery of Unknown Epipolar Geometry", Artificial Intelligence, 78:87—119, 1995.
[24] A. W. Moore, Nov. 1990, "Efficient Memory-Based Learning for Robot Control", University of Cambridge Computer Laboratory, University of Cambridge
[25] Wikipedia , 2008 , "RANSAC", http://en.wikipedia.org/wiki/RANSAC
[26] Beis, J. S. and Lowe, D. G., 2003, "Shape indexing using approximate nearest-neighbor search in high-dimensional spaces", In Conferenceon Computer Vision and Pattern Recognition (CVPR) (2003),pp. 1000--1006.
[27] O. Faugeras and Q.-T. Luong, 1996 , "The fundamental matrix : Theory Algorithms, and Stability Analysis", Int＇l J. Computer Vision, 17, pp. 43-45, 1996.
[28] Zhang Z Y, 1998, "Determining the Epipolar geometry and its uncertainty:a review", International Journal of Computer Vision, 1998 , 27(2):161-198.
[29] Brigham Anderson, Andrew Moore, Dan Pelleg, Alex Gray, Bob Nichols, Andy Connolly,2008, "Scalable Data Mining",The Auton Lab, Carnegie Mellon University, www.autonlab.org
[30] M.A. Fischler and R.C. Bolles. "Random sample consensus: A paradigm for model Fitting with applications to image analysis and automated cartography". Communications of the ACM, 24(6):381–395, 1981.
[31] Google Inc. Picasa, 2008, http://picasa.google.com/
[32] K. Mikolajczyk and C., 2004, "Schmid, Scale and Affine invariant interest point detectors"., In IJC V 60(1):63-86, 2004.
[33] J.Matas, O. Chum, M. Urban, and T, 2002, "Pajdla, Robust wide baselinestereo from maximally stable extremal regions", In BMVC p. 384-393, 2002.
[34] T.Tuytelaars and L. Van Gool, 2004, "Matching widely separated views based on affine invariant regions" . In IJCV 59(1):61-85, 2004.
[35] T. Kadir, A. Zisserman, and M. Brady, 2004, "An affine invariant salient region detector". In ECCV p. 404-416, 2004.
[36] Edward Rosten and Tom Drummond, 2005, "Authors: Edward Rosten and Tom Drummond", IEEE International Conference on Computer Vision 1508--1511
[37] ward Rosten and Tom Drummond, 2006, "Machine learning for high-speed
corner detection", European Conference on Computer Vision,430—443.
[38] FAST Corner Detection,http://mi.eng.cam.ac.uk/~er258/work/fast.html
[39] Paul Viola, Michael Jones, 2001, "Rapid Object Detection using a Boosted Cascade of Simple Features", ACCEPTED CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION 2001
[40] 周明全，耿國華，韋娜,2007, "基於內容圖像檢索技術", 清華大學出版社, 7/1/2007
[41] 吳銳航 , 李紹滋 , 鄒豐美, 2008, "基於 SIFT特徵的圖像檢索," 計算機應用研究 App lication Research of Computers, 100123695 (2008) 0220478204.
[42] 李家欣,2005, “多視點輔助定位系統”, 國立臺灣科技大學機械工程系碩士論文.
[43] 張洪剛 陳光 郭軍,　2006, "圖像處理與識別",　北京郵電大學出版社,pp1-pp20
[44] 簡大淵,　2002, "內視鏡影像序列之自動校正、重構與病灶量測",　碩士論文,　國立成功大學資訊工程學系碩士班