Feature Matching

以下為本次作使用的圖片。

得到 cv::matchTemplate()的輸出結果後，可以用 cv::minMaxLoc()來找最大最小值，以求出matching point.

radius matching

radius matching使用在計算完propensity score後，設定一個範圍(radius)，接下來比較範圍內的所有數值。使用radius matching方法會比nearest neighbor matching的結果更加精準，nearest neighbor matching是將距離最小的兩個keypoint判定為match，但有可能第一張偵測到的keypoint在第二張圖中未出現，導致距離很大但仍判定為match的情況。使用radius matching會得到更小的偏差，因為不是對整張圖做matching ，而是局部的鄰近區域中做matching。

在OpenCV 中，實踐 radius matching 的函式稱作 cv::DescriptorMatcher::radiusMatch()。

cross check

Brute-Force matcher 是一個很值觀的matching方法，在OpenCV中提供的函式稱作 cv::BFMatcher。原理是拿第一張圖中每個keypoint 的 descriptor，依序對第二張圖所有keypoint做distance calculation，距離最近的兩個keypoint，則標示為match。將距離最短得定為matching point 會遇到一個問題是，有可能第一張偵測到的keypoint在第二張圖中未出現，但根據理論，演算法仍會認為距離最短的是matching，所以為了提高matching的正確度，發展出cross check。

cross check的概念是，除了拿第一張圖中每個keypoint 的 descriptor，依序對第二張圖所有keypoint做distance calculation，還需要反向再做一次，意思是拿第二張圖中每個keypoint 的 descriptor，依序對第ㄧ張圖所有keypoint做distance calculation，將兩次matching 結果取交集，只有在雙向做match且得到相同的一組keypoint時，才判定為matching point。cross check的缺點是，需要花費兩倍的運算時間，雖然運算量大，但在資料數少的時候效果很好。

 ratio test

Ratio test 目的是為了增加matching 結果的精確度，會將一些模稜兩可的答案去除掉。假設從影像一中取keypoint (fa) ，欲在影像二中找匹配點，會在影像二中找和影像一中的keypoint距離最短的兩個點( fb1、fb2 )，也就是最匹配的兩個keypoint，其中又以 fb1 的距離比 fb2 短，下一步帶入公式d(fa, fb1) / d(fa, fb2)計算兩點的ratio test。

若計算結果數值很小，代表fb1 的距離遠小於 fb2的距離，則fb1是良好的matching結果，相反的若計算結果很大，則有代表fb1 的距離和 fb2的距離很接近，fb1是模稜兩可的matching結果，因此將 fb1、fb2捨棄。

goal of this code

主要使用FAST做keypoint detect，FAST的優點是速度很快，本節將利用template matching來完成maching。以下主要說明實踐template matching的理論、程式碼說明及測試當使用不同keypoint detector所得到的效果差異。

theory and principle explanation

完成keypoint detect 後，所得到的結果是單一pixel，僅單一piexl無法做matching，必須將四周的pixel都考慮進去。實踐概念是，分別求出兩張圖的keypoint，接著將圖片一中得到的keypoint，依序在圖片二中找最相近pixel，判斷兩張圖中pixel的相似程度用方法有很多種最基本的方式是，計算Sum of Squared Differences，以得到兩個patch裡的intensity values differences，最後將差異最小的兩個keypoint，則判定為match。

最後使用cv::drawMatches() 劃出matching結果就完成了，以下為模擬結果，先看左圖，matching結果大致上還算正確，只有幾條呈現傾斜的線段matching錯誤。再看到右圖，書名"Harry Potter"的部分多數都matching到別本數，人物的部分乍看下還算正確。

接下來做另一種模擬，測試template matching的效果。

我嘗試換其他照片希望可以找到一些規律，要如何選擇選擇區域，可以讓效果清楚一些。以下結果可以發現，選擇不同區域，使用cv::matchTemplate() 模擬出來的效果不穩定，第一組圖就很正確的選擇到牆上的裝飾，但第二張圖卻選擇到視覺上差異很大的patch。我認為選擇區域選擇patch內顏色差異大的，且選定物件在兩張圖中都清晰可見的效果最好。

result comparison or analysis

以下我使用不同的keypoint detector做模擬，在上一次作業中有提到，每種不同的keypoint detector被發展出來的優勢，有的是為了提高精確度，有的是為了提高速度，有的是為了解決scaleing和rotation的問題，我在程式碼中加入計算時間的涵式如下，計算從翠取出keypoint到matching結束的時間，並分析比較結果。

double time = static_cast<double>(cv::getTickCount());

time = (static_cast<double>(cv::getTickCount()) - time) / cv::getTickFrequency();

std::cout << "time = " << time << "ms" << std::endl;

首先先使用FAST來偵測keypoint，參數設定如下，和前面相同，先matching較多的點，再取前50個較好的matching結果輸出。

ptrDetector = cv::FastFeatureDetector::create(80);

cv::Ptr<cv::xfeatures2d::SURF>  ptrDetector = cv::xfeatures2d::SURF::create(2000.0);

cv::Ptr<cv::SIFT>  ptrDetector = cv::SIFT::create(1000);

cv::Ptr<cv::BRISK>  ptrDetector = cv::BRISK::create(60, 5);

cv::Ptr<cv::ORB>  ptrDetector = cv::ORB::create(1000, 1.2, 8);

依時間長短做比較，需要花費的時間長短依序為：BRISK > ORB > SIFT > SURF > FAST， 時間長短落差很大。在看matching結果，沒辦法很精確的比較，但視覺上是ORB的效果最好，像是玻璃花窗的部分結果最正確。

以下調整不同的patch大小，match點一樣限制為50個，並分析不同大小對結果帶來的影響。隨著patch大小變大，一次考慮更多的pixel所花的時間也變長。當 nsize = 9 有一條很明顯的斜線，nsize 增加後斜線就不見了，nsize = 11 和 nsize = 13 必較，觀察人物身上的match結果可以發現隨著patch大小變大視覺上match的結果也更精準。

goal of this code

SIFT和SURF 使用feature descriptor來描述keypoint周圍的特徵，本節將了解feature desriptor的原理並利用template matching、radius match、KNN matching、ratio test來實踐matching。

theory and principle explanation

SIFT 使用128 dimension來描述特徵，SURF 使用64 dimension來描述特徵。造成兩中方法的feature descriptor大小不同是因為，SIFT則利用多個空間區域的梯度方向histogram，得到一個128維的feature descriptor。SURF為了加速SIFT而作改良，使用近似 Gaussan來進行關鍵點描述，來得到一個64維的feature descriptor。

求出feature descriptor 後，將第一張圖的keypoint 依序和第二張圖做比較，差異最小的則為標示為 matching。 

 code segment 

這部分主要選擇Brute-Force matcher來做matching，並測試兩件事，第一使用SURF和SIFT作為keypoint detector的差異，第二使用使用cross check 對結果的影像。

這部分選擇KNN matching，並使用ratio test 來提升結果的準確度。

最後測試使用SIFT的效果，我將原先放在最後的程式碼複製到最前面，使用SIFT重新測試四種不同matching 方法

result comparison or analysis

先看觀察SURF的結果，未使用cross check 的結果總共matching 到364個keypoint，畫面看起來很雜亂，很難清楚辨認match結果的正確性，視覺上看起來大多數都是不正確得，再看到有使用cross check的結果偵測到48個matching結果，視覺上玻璃花窗的部分看起最正確，其他部分正確度不高。

再將SURF和SIFT做比較，SIFT設定震測到364個keypoint，未使用cross check 的結果畫面一樣很雜亂，使用cross check後偵測到119個matching結果，比SURF偵測到的多，而正確率看起來也比SIFT還高，尤其是在玻璃花窗還有樓塔上窗戶兩部分。

以下測試ratio test改變不同的 ratioMax 帶來的效果，及比較在相同 ratioMax 使用不同keypoint detector 的差異。 

隨著ratioMax 增大matches增加，代表fb1和fb2間的距離差異變短，被判定為match 的門檻降低。使用SIFT的matches比使用SURF所呈現的matches多，且視覺上SIFT的正確度較高，我推測是因為SIFT是使用128為的feature descriptor，而SURF使用64維，所以SIFT所能呈現的結果較精確。

以下測試radius match改變不同的 maxDist帶來的效果，及比較在相同 maxDist 使用不同keypoint detector 的差異。 

使用SURF的matches比使用SIFT所呈現的matches多，在前面也有提到，我將參數設定 maxDist = 100 結果沒改變，我推測是我選擇這兩張圖差異過大。再看到使用SURF的三張圖，隨著 maxDist 提高matches也越多，正確率提高。

goal of this code

ORB和BRISK 使用Binary descriptor來描述keypoint周圍的特徵，Binary descriptor 和 feature descriptor的差異是，binary descriptor使用binary strings可以更佳容易計算和做特徵比較。本節將了解Binary descriptor的原理及實踐matching。

theory and principle explanation

Binary descriptor 的原理是先在keypoint的周圍選擇patch的範圍，接著在patch的範圍內倆倆一組比較intensity，令其中一點為S1一點為S2，若 I(S1) > I(S2) 則編碼為1，相反的I(S1) <= I(S2) 則編碼為0。接著比較每個keypoint的binary descriptor來完成matching，比較的方式是計算Normalized Hamming Distance。先從hamming distance開始說明，hamming distance是比較兩個binary descriptor在相同位置上有幾個bit數值不同，而Normalized Hamming Distance = Hamming Distance/ length of the string，是將Hamming Distance做正規化的結果。

ORB：

• binary descriptor為256 維

• 計算binary descriptor 的採樣方式是取 optimal sampling pairs 。希望採樣點具辨識性(discriminative )，所以Sampling Pairs 須具備uncorrelated 和 high variance 兩特性，使用Greedy search找出符合這兩個特性最佳的binary descriptor。

• 具有 rotation invariant，實踐的方法是做rotation compensation，計算patch的質心(centroid)及主方向(main orientation)

 code segment 

這部分主要實作ORB並選擇Brute-Force matcher來做matching。

這部分實踐BRISK，且搭配FREAK以增加精確度。FREAK 不是從影像中去提取特徵，而是從既有的特徵中去提取具辨識性(discriminative )的Sampling Pairs，從而計算binary descriptor，因此需搭配ORB或BRISK作使用。 FREAK 計算binary descriptor的方式和ORB很像，若I(S1) > I(S2) 則編碼為1，反之則編碼為0 。

result comparison or analysis

以下調整FREAK裡的參數，改變不同的patternScale 帶來的效果。 

隨著patternScale 增加matches慢慢減少，視覺上改變不明顯，但看起來正確率有提升。

雖然正確率有提高但整體上錯誤率仍很高，剛好在查資料的時候，有看到有人有和我相同的疑問，使用BRISK搭配FREAK來增加精確度，但模擬結果還是不理想，底下有人建議可以使用再搭配coross check 和 ratio-test 提高精確度，所以以下增加ratio-test的程式碼，再重新模擬一次比較結果。

FREAK的參數設定如下，接著使用BREAK 和 ORB個模擬一次，比較結果。

cv::xfeatures2d::FREAK::create(true, true, 22.0f, 4, std::vector< int >())

因為上圖matching 結果仍不是很正確，所以我慢慢降低threshold值，偵測出更多的keypoint點，matching效果更好。

因為前面由BRISK在threshold=80時於第一張圖中偵測到988個keypoint，我將keypoint detector 改為使用 ORB設定在nfeatures =988，以觀察結果。matches變少，因為在第二張圖中右邊塔上的窗戶沒有被偵測到keypoint，所以將左邊的塔和第一張圖的窗戶匹配在一起，選擇最相接近的特徵作匹配。

這次的作業很多函式在上一次作業中就使用過，所以在解讀程式碼和做一些變化的部分沒遇到甚麼困難。在模擬的時候，我一直在測試不同的參數，以觀察其對結果的影響，希望找到一組能夠提高匹配結果準確度的參數，但特別是在模擬BRISK和ORB的部分，無論我如何調整參數，都難以達到像之前使用SURF和SIFT時那樣高精確度的匹配結果。我猜想問題可能出在我所選擇的圖片上，可能是因為圖片的顏色或旋轉角度差異太大，這使得結果都不太理想。