sift演算法特徵點如何匹配？

01-07

我需要把一張照片和訓練集中的圖片進行匹配。我把一張照片提取特徵值並建立kd樹，然後把訓練集的圖片依次讀進來，然後把圖片的特徵點依次放進kd樹裡面找最近的點，第一個問題就是這2個點的距離，方向之比，長度之比在什麼範圍內算是匹配的？第二個問題是匹配的特徵點與總共的特徵點之比達到什麼範圍就可以認為2幅圖片是匹配的？第三個問題是我們是需要找到一幅匹配的圖片就結束還是遍歷所有圖片以後找到最匹配的圖片再結束？

題主應該是如果只是想知道SIFT是怎麼在兩幅圖像間進行匹配的話，下面是我總結的四種匹配方法，希望對題主了解SIFT匹配過程有幫助。

一般在詞袋模型中，為了提高檢索的精度，你可以通過很多的trick來提高其精度(mAP)，其中一個廣泛使用的技巧就是對返回的圖像進行重排，重排有很多種方法，比如對多特徵在分數層(決策層)進行融合也是一種重排方式，不過這裡要做的是通過剔除查詢圖像與候選圖像錯配點對的方式進行重排，剔除錯配點一般採用的是RANSAC演算法，關於RANSAC原理可以閱讀RANSAC演算法做直線擬合這篇文章，或者採用類RANSAC演算法。作為初級階段的實踐，這裡從兩幅圖像的匹配逐步深入。

代碼下載：下面貼圖的結果的代碼都可以sift(asift)-match-with-ransac-cpp下載。

1NN匹配

「1NN匹配」（勿wiki，自創的一個辭彙），講起來比較順口，而且從字面也應該可以猜測出點意思來，所以就這麼寫在這裡了。所謂的「1NN」匹配，即是對於圖像im1中的某個SIFT特徵點point1，通過在im2圖像上所有SIFT關鍵點查找到與point1最近的SIFT關鍵點，重複這個過程，即可得到圖像im1中所有的特徵點在im2中的匹配點(最近鄰，1NN)。這種匹配方法，會出現很多的錯配點，下面是採用1NN匹配的結果：

從上圖可以看到，1NN匹配的方法出現了很多的錯配點，而這些錯配點對無論是對圖像檢索中的重排，還是圖像拼接等，都是不希望看到的，所以得進一步對其中的錯配點對進行剔除，下面採用「1NN/2NN&<0.8」的方法進行錯配點對剔除。

1NN/2NN&<0.8

"1NN/2NN&<0.8"，不要詫異你未見過這樣一種說法，沒錯，自己瞎創的一種表述。對上面1NN方法理解了，這個水到渠成。所謂「1NN/2NN&<0.8」，即對於圖像im1中的某個SIFT特徵點point1，通過在im2圖像上所有SIFT關鍵點查找到與point1最近的SIFT關鍵點point21(記該關鍵點point21到point1的距離為dis1)和次近的關鍵點point22(記該關鍵點point22到point1的距離為dis2)，如果dis1/dis2&<0.8，則我們將其視為正確匹配的點對，否則則為錯配的點對予以剔除。這種尋找匹配的方法，由Lowe在其Distinctive image features from scale-invariant keypoints中有說明，當然，0.8這個閾值是可以調整的，不過一般都採用0.8。下面是採用該方法進行匹配後的結果：

可以看到，經過該方法匹配後，相比與「1NN」匹配方法，相比於「1NN」，這種方法進行匹配時有了很大的改善，不過正配點相比與1NN有部分損失。下面再探討用RANSAC方法對這兩種情況進行錯配點剔除。

1NN+RANSAC

回到前面的「1NN」匹配的點對，我們再採用RANSAC方法對其進行錯配點剔除，RANSAC方法的原理前面已有相關文章RANSAC演算法做直線擬合，這裡不再重複，相關的代碼請看utils.cpp中findInliers函數，調用的是OpenCV中的cv::findFundamentalMat函數計算其變換矩陣，下面是「1NN」經過RANSAC剔除錯配點對的結果：

可以看到，經過RANSAC後，「1NN」中的很多錯配點對差不多剔除得比較好了，不過還有錯配的點對沒有剔除掉，圖中用紅色矩形框標出了未剔除的錯配點對。我們在來看看對「1NN/2NN&<0.8」進行RANSAC後會是怎樣的結果呢？

1NN/2NN&<0.8+RANSAC

在看匹配結果前，我們可以先做一個大概的預測，因為「1NN/2NN&<0.8」得到的很多點就是正確匹配的點對，所以將其放入RANSAC中後，能夠得到很好的擬合模型，所以其剔除錯配點對效果也應該更好。為了驗證這一預測，我們看一下「1NN/2NN&<0.8+RANSAC」具體的效果，如下圖所示：

可以看到，已經完全沒有錯配點了，從這一點來說，其效果是非常好的。不過，從正配點對數目來看，「1NN+RANSAC」的結果更密集，也就是說「1NN+RANSAC」包含了更多的正配點對，「1NN/2NN&<0.8+RANSAC」正配點對要稍微少些。在大多數情況下，我們會選擇完全剔除了錯配點對的模型。

上面分別介紹了兩種匹配方法，分別是「1NN」和「1NN/2NN&<0.8」匹配方法，以及對它們採用RANSAC剔除錯配點對的方法。有時候，如果要求經過RANSAC匹配後保留更多的正配點對，這時候，我們可以採用Affine-SIFT，簡稱ASIFT，具體可以閱讀ASIFT: An Algorithm for Fully Affine Invariant Comparison這篇文章，作者提供了ASIFT的C++代碼和匹配演算法，可以在ASIFT下載得到，我大概跑了一下裡面的demo，相比與SIFT，ASIFT可以提取到很多的關鍵點，對旋轉等變換具有更好的不變性，不過缺點也很明顯，速度實在太慢，很難做到實時，所以要使用的話，一般應用在對實時性不做要求的場合。我那個代碼里有OpenCV的實現，你也可以試一下其效果，該OpenCV代碼實現來源於OPENCV ASIFT C++ IMPLEMENTATION，OpenCV自帶其Python實現，使用比較方便，就是速度太慢，所以自己在圖像檢索在寫的項目中，也不打算用它了。

--------------------------------------------------------------------------------------------------------------------------------------------

更新一下：

這兩天自己用c++重新寫的一個剔除錯配點的方法，效果很不錯：

實現的代碼可以在這裡找到covdet。

思路錯了！

SIFT特徵屬於圖像局部不變性特徵，這類特徵比較常用來進行圖像配准，注意不是圖像匹配，它關心的是圖像上像素及像素領域的屬性，往往是同一物體在不同位置和不同時刻形成的兩幅圖像的配准。

圖像匹配一般使用全局特徵，如顏色直方圖，感知哈希編碼等特徵。

樓主好，我最近也在看sift，演算法中說匹配時計算兩圖關鍵點歐氏距離最小，請問這是怎麼個比較法，不同的角度和位置不都應該會影響到距離嗎？

Lowe的SIFT代碼網上是有很多大牛寫的代碼的，參考一下就好。