影像處理技術中，有許多基礎的研究議題存在，舉凡圖形辨識、人臉辨識、影像拼接、3D建模、圖形比對等應用，皆有一共同的基礎方法：從圖形中找出某些特徵點(feature points)，再經過比對(matching)達到定位的目的。特徵點的定義與找尋，雖然基礎但並不簡單且影響深遠。一開始能將許多不同角度獲取的圖形中相同位置正確無誤的對應出來，接下來的步驟將會是工半而事倍；反之如果存在錯誤的對應，則會引後續處理極大的麻煩。本篇論文所要研討的議題即為從圖形中提取依據各像素(pixels)的鄰近區域的特徵點，再對特徵點作描述，成為區域性特徵描述器，另外加入圖像大範圍資訊，成為廣域特徵描述器，並在不同部份對稱影像間比對，提高圖形比對(match)的準確率，而不會誤判。
  在此篇論文中，將以 Scale Invariant Feature Transform (SIFT) 為基礎，研究 SIFT 的演算法，對原圖片縮放和高斯模糊產生高斯金字塔差，並提取其中的關鍵點，並提高抗噪訊能力，以及增加比對的穩定性；再分配關鍵點基準方向，使得特徵描述器具有旋轉不變性；最後再增加廣域描述器資訊，使得部份相似圖形中，可以增加比對準確性。
  在此將使用Open Source的Library OpenSIFT為基礎，實作 Global Context Feature Descriptor，再取相似性高的各種不同圖片，套用實作的執行結果，並與原始的OpenSIFT作比較，以驗證所實作出的方法是可改善相似性高的影像比對正確率和速度。
  本論文主要研究關鍵在於SIFT在相似性高的圖片中，利用本地特徵描述器與廣域特徵描述器的廣域資訊作結合，來減少圖像比對錯誤的錯誤比率，以及使用SIFT加GC和Sample Keypoints來加速比對速度。例如棋盤中有許多相似區域，使用棋盤來比較驗証實作比對的結果與OpenSIFT比對的結果。

In image processing, there are many basic research topics, for example, image recognition, face detection, image stich, 3D reconstruction, image matching applications, there is a same basic method: To extract feature points from image, through match to reach the goal of location. The definition and search from feature points, although basic, it is not simple but influence deeply; To correctly extract same position but difference angle from beginning, next steps will be work half the things times; On the contrary, if exist mismatch, subsequent processing great trouble is thrown. The topic of research discussion from the thesis is extract interest feature point according to every pixels neighbor area from image, then describes it, become local feature descriptors. Besides of this, adding global context information, as global feature descriptors, utilized them to match between images, increase the precise rate of matching, rather than mismatch.
  In the thesis, depends on “Scale Invariant Feature Transform”(SIFT), studying the algorithm of SIT, Scaling and Gaussian Blurring image to produce the Gaussian pyramid, then extract keypoint, increase the ability for noise, and stability for matching; Then to assign orientation for keypoint, let feature descriptor to be invariant to image rotation; Finally, adding the global descriptor information, so increase the matching ability for the partially similar image.
  Base on using the OpenSIFT library, which were written by Rob Hess, implement Global Context Feature Descriptor, to take many highly partially similar image, experiment the result, to compare with the result experiment by OpenSIFT, to exam if the method can improve the correct matching and speed.
  The thesis major in researching improved the incorrect matching rate between highly similar image; To utilize the combination of Global Feature Descriptors global information and local feature descriptors to decrease incorrect matching. For example, checkerboard has many similar areas, to verify if the matching rate improved then OpenSIFT is we are compared.

第一章  緒論	1
1.1 前言	1
1.2 研究動機	2
1.3 研究目的	2
1.4 論文內容大綱	3
第二章  背景知識	4
2.1 尺度不變特徵轉換 (Scale Invariant Feature Transform, SIFT)	4
2.1.1 尺度空間極值檢測	4
2.1.1.1 尺度空間	5
2.1.1.2 高斯差分金字塔 (Difference of Gaussian Pyramid)	6
2.1.1.3 極值檢測 (Extrema detection)	9
2.1.2 關鍵點定位 (Keypoint localization)	10
2.1.2.1 精確定位 (Accurate localization)	10
2.1.2.2 消除邊緣響應 (Eliminating edge responses)	11
2.1.3 方向定位 (Orientation assignment)	12
2.1.4 關鍵點描述器 (Keypoint descriptor)	14
2.1.5 比對 (Matching)	16
2.2 加速穩健特徵(Speeded Up Robust Features, SURF)	17
2.2.1 偵測興趣點 (Interest Point Detection)	17
2.2.1.1 積分圖像 (Integral Images)	17
2.2.1.2 海森矩陣 (Hessian Matrix)	18
2.2.2 尺度空間描述與特徵點定位 (Describe Scale space and Locate Feature point)	19
2.2.3 興趣點描述與比對 (Interest Point Description and Matching)	19
2.2.3.1 方向定位 (Orientation Assignment)	20
2.2.3.2 計算描述器 (Descriptor Calculation)	20
2.2.3.3 快速索引比對 (Fast Indexing for Matching)	21
2.3 梯度位置和方向直方圖(Gradient Location and Orientation Histogram, GLOH)	21
2.4 廣域特徵描述器(Global Feature Descriptor)	22
2.4.1 曲率影像 (Curvature image)	22
2.4.2 對數極座標 (Log polar)	23
2.4.3 描述器統計	24
2.4.4 比對方式	24
2.5 OpenCV	26
2.6 OpenSIFT	26
第三章  SIFT算法的改進	27
3.1 SIFT+GC比對流程圖	27
3.2 SIFT+GC特徵尋找流程圖	29
3.3 SIFT+GC改進方案	30
3.4 OpenSIFT的編譯環境	35
第四章  研究結果探討	36
4.1 SIFT比對結果	37
4.2 SIFT+GC+AR大於0.8比對結果	38
4.3 實驗結果	38
第五章  未來展望及討論	40
參考文獻	42
附錄－英文論文	44
圖目錄  
圖2-1 高斯拉普拉斯與高斯差分的比較	6
圖2-2 高斯差分金字塔的生成	7
圖2-3 DoG空間極值檢測	9
圖2-4 左圖為邊緣消除前，右圖為邊緣消除後	12
圖2-5 關鍵點直方圖	13
圖2-6 關鍵點描述器梯度方向分配	16
圖2-7 右圖為GLOH圖形	21
圖2-8 對數極座標	23
圖3-1 SIFT+GC比對流程圖	27
圖3-2 SIFT+GC特徵尋找流程圖	29
圖3-3 左圖棋盤圖，右圖旋轉棋盤圖，皆為2048*1536	31
圖3-4 左圖棋盤圖，右圖旋轉棋盤圖，皆為1024*768	31
圖3-5棋盤圖2048*1536,左圖SIFT比對結果，總共444比對上，261錯比對，誤比對率58.78%，右圖SIFT+GC比對結果，總共102比對上，23錯比對，誤比對率22.54%	32
圖3-6 棋盤圖1024*768, 左圖SIFT比對結果, 總共147比對上，51點錯比對，誤比對率34.69%，右圖SIFT+GC比對結果, 總共56比對上，4點錯比對，誤比對率7.14%	32
圖3-7 蟲圖像a	33
圖3-8蟲圖像b	33
圖3-9 OpenSIFT比對結果，比對56點，13點錯誤，誤比對率23%	34
圖3-10 SIFT+GC比對結果，比對上6點，無比對錯點，誤比對率0%	34
圖3-11 SIFT+GC+閥值15 比對結果，比對上10點，且全正確，誤比對率0%	35
圖4-1 圍棋原始圖片	36
圖4-2 象棋原始圖片	36
圖4-3 SIFT比對結果	37
圖4-4 SIFT+GC+AR大於0.8比對結果	38
表目錄
表2-1 圖像金字塔大小與層數關係圖	8
表2-2 SIFT和SIFT+GC+Sample Keypoint比對速度表	31

[1] David G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints.”, International Journal of Computer Vision, 60:91-110, 2004.
[2] David G. Lowe. “Object recognition from local scale-invariant features.”, International Journal of Computer Vision, 1999.
[3] E.N. Mortensen, Hongli Deng, and L. Shapiro., “A SIFT descriptor with global context.”, Computer Vision and Pattern Recognition, 2005. IEEE Computer Society Conference on, volume 1, pages 184-190 vol. 1, June 2005.
[4] S. Belongie, J. Malik and J. Puzicha, “Shape matching and object recognition using shape contexts,” PAMI, 24(4):509-522, 2002
[5] S. Belongie, J. Malik and J. Puzicha, “Shape context: A new descriptor for shape matching and object recognition,” in NIPS, pp. 831-837, 2000.
[6] K. Mikolajczyk and C. Schmid, “A performance evaluation of local descriptors,” in CVPR, pp. 257-264, 2003.
[7] C. Harris and M. Stephens, “A combined corner and edge detector,” in Fourth Alvey Vision Conf., pp. 147-151, 1988
[8] C. Steger, “An unbiased detector of curvilinear structures,” PAMI, 20(3):113-125, 1998.
[9] Demo Software: SIFT Keypoint Detector http://www.cs.ubc.ca/%7Elowe/keypoints/
[10] OpenCV. http://opencv.org
[11] Rob Hess, “An Open-Source SIFT Library”, ACM MM, 2010.
[12] OpenSIFT. https://robwhess.github.io/opensift