Programming 6
Feature Matching
Goal
學習實現多個局部特徵描述子的特徵匹配。
了解模板匹配和特徵描述子匹配方法。
實現 5 個關鍵點描述符的 OpenCV 特徵匹配方法：SIFT、SURF、ORB、BRISK、FREAK。
作業環境
硬體規格:
CUP:12th Gen Intel(R) Core(TM) i5-12400 2.50 GHz
RAM:32G
軟體規格:
作業系統:Windows 10 專業版
C++ IDE:Visual Studio Community 2022 (64 位元) 版本 17.5.1
OpenCV:4.7.0 (contains contrib)
問題與解決方法
上一篇結尾提到 OpenCV 4.7.0 版本已經將 SIFT 加入主函式庫中，但由於 P5 實驗都是以 4.3.0 並包含 contrib 版本實現的，而後續以 4.7.0 版本也只針對 SIFT 做測試，卻忽略了其實 SURF 不在 4.7.0 的主函式庫中。
經過網路搜索得知 SURF 算法在 SIFT 移回主函式庫時，被放到了 nonfree.hpp 裡面，而這個標頭檔只在有編譯 contrib 庫的 OpenCV 出現，先前為了測試，我編譯了四種版本的 OpenCV 剛好派上用場。
接著我測試使用 OpenCV 4.7.0直接編譯 OPENCV_ENABLE_NONFREE，雖然 CMAKE 找到了 nonfree 模塊，但編譯出來的檔案是沒有 nonfree 內容的，證明了還是得編譯 contrib 庫，才能使用 SURF，如果只需使用其他算法如 SIFT, GFTT, FAST, BRISK, ORB 的話，直接用 OpenCV 提供的函式庫就能實現了。
接著我進入 OpenCV 4.7.0 contrib，成功編譯出來的 nonfree.hpp 在這個路徑，雖然 SURF 在 nonfree.hpp 裡，但直接引入 xfeatures2d.hpp 就可以使用了，不需要特別引入 nonfree.hpp。
原因是因為 nonfree.hpp 已經被引入在 xfeatures2d 裡面了，同樣的，許多算法其實也在 features2d.hpp 內，也已經都被引入了。
而正因為 SIFT 和 SURF 來自不同的標頭檔，在創建檢測器的時候程式碼也會有所不同。
SURF 算法雖然是以 SIFT 為基礎做改良，但專利提出時間是在 2006 年，以美國專利規定保護年限為 20 年就必須等到 2026 年，SURF 才能被完全開放，這也是為什麼 SIFT 已經可以在新版本直接使用，而 SURF 卻還需要額外編譯 contrib 庫的 nonfree modules 的原因。
相關理論概述
模板匹配(template matching)：
模板匹配是一種圖像處理技術，用於在圖像中尋找與給定模板最相似的區域。
原理是將模板與圖像的各個位置進行比較，通過計算它們之間的相似度來確定最佳匹配位置，通常使用像素值之間的差異來度量，例如平方差或相關性。
模板匹配常用於物體檢測、圖像識別和目標追蹤等應用中。
k最近鄰匹配(knn matching)：
k最近鄰匹配是一種特徵匹配方法，用於在兩組特徵描述子之間找到最相似的對應。
原理是對於每個特徵描述子，在另一組描述子中找到與之最相似的k個鄰居，通常使用歐氏距離或餘弦相似度等度量方式計算。
通過k最近鄰匹配，可以建立特徵之間的對應關係，用於圖像配對、物體追蹤和三維重建等應用。
半徑匹配(radius matching)：
半徑匹配是一種特徵匹配方法，用於在圖像中尋找與給定特徵描述子在一定半徑內相似的特徵點。
原理是對於每個特徵描述子，在給定半徑範圍內搜索相似的特徵點，通常使用距離度量方式來計算。
半徑匹配常用於圖像檢測、圖像對齊和圖像檢索等應用中。
交叉檢查(cross check)：
交叉檢查是一種用於特徵匹配的技術，旨在確保匹配是雙向的。
原理是對於每對匹配的特徵點，檢查其互相之間的匹配情況，如果兩個特徵點互相匹配，則將其視為有效的匹配。
交叉檢查可以幫助過濾掉單向的錯誤匹配，提高匹配的準確性。
比值測試(ratio test)：
比值測試是一種特徵匹配的篩選方法，用於過濾不確定或不可靠的匹配。
原理是對於每對匹配的特徵點，計算它們與最近鄰和次近鄰之間的距離比值，若比值小於閾值，則將其視為有效的匹配。
比值測試可以減少誤匹配的可能性，提高匹配的可靠性。
此程式使用的影像是我自行拍攝的影像，設備為 iPhone Xs 的內建相機 (並調整尺寸為500*375)
第一張是以手電筒補光的影像。
第二張是沒有補光，並且物件有些微旋轉，鏡頭視角略低的影像，這些變化是為了想要驗證特徵點在 translation, rotation, scale 和 intensity 的不變性。
SURF（Speeded-Up Robust Features）
1.特徵點偵測。
這是 P5 做過的 Feature detection，並使用 SURF 算法針對兩張範例影像偵測 keypoints 和 descriptors 並分別儲存。
keypoints 是一個存儲關鍵點的容器，包含了其在圖像中的位置、尺度、方向等信息。
descriptors 是描述子的容器，每個關鍵點都對應著一個描述子，用於描述該關鍵點周圍區域的特徵。
BFMatcher 是 OpenCV 中的一個特徵匹配器類別。
它用於在給定的兩組特徵描述子之間進行特徵匹配，並使用簡單的暴力匹配方法（Brute-Force Matching）進行特徵匹配。
對於每個特徵描述子，計算與另一組描述子之間的距離，然後找到距離最接近的描述子對作為匹配對。
參數
normType：用於計算距離的距離度量方法，常見的有 NORM_L2(歐氏)和 NORM_HAMMING(漢明)等，預設值為 NORM_L2。
crossCheck：一個布林值參數，表示是否進行交叉驗證，預設值為 false，設為 true 時，當匹配對是互相最佳的時候才會被保留。
2.匹配動作。
創建 BFMatcher 物件，並指定了歐氏距離為測量方法 NORM_L2，計算描述子之間的距離。
接著進行特徵匹配，descriptors1 和 descriptors2 作為輸入，並將匹配結果存儲在 matches 中。
matches 容器中存儲了描述子之間的匹配結果，每個 DMatch 物件代表一個匹配對，包含了兩個描述子的索引和它們之間的距離。
3.畫上匹配結果
4.顯示結果及匹配對數量。
在結果中觀察到，使用 SURF 方法提取特徵點，並用歐式距離為 BFMatcher 的距離計算方法匹配時，共有 74 個匹配對數量，其中包含正確以及一些不正確的匹配。
而同樣方法參數下，使用我自己拍攝的影像匹配結果多達 168 組，也包含許多不正確匹配。
以下是加入交叉比對(cross check)之後的結果。
經過 cross check 之後，匹配結果數量被過濾至原本的25%~30%，被保留下來的正確率也較高。
接著使用 knnMatch 匹配並將 k 設定為 2，並使用 ratio test 將比值設為 0.7，對所有匹配進行訪問，並將 2 個最佳匹配對象比值大於 0.7 的匹配過濾掉，保留小於 0.7 的匹配視為有效匹配。
參數k：指定要找到的最佳匹配數目，即 k 個最近鄰。
接著使用半徑匹配 (radius matching)，並將可接受最大距離設置為 0.3。
參數 maxDistance：最大距離閾值，超過此閾值的匹配將被排除。
結論
關於半徑匹配、交叉檢查、比值測試都屬於過濾匹配結果的方法，這些過濾方法的目的是排除一些可能的誤匹配，從而提高匹配的準確性和可靠性，可以根據應用的需求，使用其中一種或多種方法進行組合，以得到更好的匹配結果。
模板匹配(template matching)
定義鄰域的大小 nsize(11)，此處設置為11x11。
矩形 neighborhood，代表了圖像中的一個區域，其大小為11x11。
patch1 和 patch2 用於儲存圖像中的區域。
result 用於儲存模板匹配的結果。
matches 為儲存匹配結果的向量。
matchTemplate 函數，用於在一個圖像中搜尋另一個小的模板圖像，尋找與模板圖像最相似的區域。
第一區域
根據第一張圖像中的關鍵點的位置，計算出圖像區域的左上角坐標，確定區域的位置。
接著檢查計算得到的區域是否超出了圖像的邊界，如果超出邊界，則跳過該關鍵點的處理。
根據計算得到的區域位置，在第一張圖像中提取相應的圖像區域，將其存儲到patch1中。
bestMatch，用於存儲最佳匹配結果。
第二區域
使用第二層迴圈遍歷第二張圖像的關鍵點。
第三區域
使用模板patch1與patch2進行特徵匹配，這裡使用的匹配方法是平方差匹配（TM_SQDIFF）。
檢查匹配結果的相似度是否優於之前找到的最佳匹配結果，如果匹配結果更好，則更新bestMatch的相關屬性。
將找到的最佳匹配點加入到matches向量中。
接著留下最佳的50個匹配。
這是輸出結果，模板匹配是基於圖像區域的匹配方法，簡單來說就是從第一張圖像中提取所有 11x11 大小的區域，然後將這些區域與第二張圖像的相同大小的區域使用模板匹配方法進行比對，將每個區域與目標圖像中的對應區域進行相似性度量的比較，找到最佳匹配的區域。
這樣做的目的是找到兩張圖像中相似的區域，或者說是找到第一張圖像中的關鍵點在第二張圖像中的最佳匹配點。
其他特徵提取方法的匹配結果
接著實現 SIFT, ORB 及 BRISK 這些不同的 keypoint descriptors 在相同條件下的 Feature Matching 效果。
為了觀察對於算法的差異，都是使用 BFMatcher 並含有交叉檢查(cross check)，並且保留前50個匹配結果作為輸出。
結果分析及心得
在 Feature Matching 的實作中學習到多種匹配方法，模板匹配、knn matching、radius matching，以及各種針對特徵點進行篩選動作的方法，半徑匹配、交叉檢查、比值測試，綜合這些方法的實作結果我認為使用 BFMatcher 含有 cross check，並且保留前50個匹配結果作為輸出這樣的條件在特徵配對的準確率上有很好的表現。
在特徵提取的算法中，幾乎都能匹配到正確位置，不過 SIFT 算法的強大終究還是我最佩服的，對於特徵描述子的唯一性非常可靠，從網路資訊得知一些知名企業，Google、Facebook、Adobe Photoshop 和 Amazon 都曾有透過這個算法研發自家產品，其應用也非常廣，從物體識別、圖像檢索、圖像拼接、全景圖生成、特徵跟踪、運動估計、圖像校正和圖像修復，以及目前持續發展的增強現實（AR）和虛擬現實（VR）。