Keypoint Feature Detection

一開始我將課本提供的程式碼直接全部複製貼上，但跑出一行錯誤：

fatal error: opencv2/xfeatures2d.hpp: No such file or directory

接著我開始在網路上查解決方法，最後知道SIFT和SURF因為專利問題從Release版移出，移至 nonfree.hpp ，如要想要使用這些函式，就必須將opencv_contrib自己編譯到opencv裡。有查到一個好消息是SIFT的專利到期，所以移回主函式庫，但SURF仍放在nonfree.hpp中。接下來我就依照網路上查到的文章，按照內容操作。

Step13

接下來要來設定環境變數從： "設定 -> 系統 -> 系統資訊 -> 進階系統資訊"  "使用者設定檔" 的 "設定"

將要使用的函示庫的bin 路徑加入到 "系統變數 -> Path"  

最後，再重新開機一次，就大功告成了，重新執行一次程式碼，便可以順利完成keypoint detection。

Corner

在一張相片中，corner位於edge的交叉點或多邊緣交叉處，是影像中intensity變化快速的地方，最重要的特色corner 是相片中不易重複的點、有辨識性，因為corner描述了影像中的特徵，讓物件可以被精準的定位，也稱作interest point 、keypoint。在應用上有了corner便可以做物件偵測(object recognition)、3D重建(3D reconstruction)、影像拼接(image stitching)。

Harris

Harris corner detection 的原理是計算，window在所有方向上位移時的intensity變化，並將變化劇烈的部分標記為corner。

首先計算sum of square difference，求出intensity變化。

經過整理後如下，因此下一步需求出計算出 autocorrelation matrix ，從這個矩陣可以求出eigenvalue 和 eigenvecter。

GFTT

由Jianbo Shi 和 Carlo Tomasi 提出Good Features to Track (GFTT)，對 Harris corner detection 做改善，主要目的在於偵測真實物件時能增加精確度和速度。

在 Harris corner detection 有一個問題是在計算corner response function後，corner四周的分數都會很高，所以會呈現像是一群corner聚集在一起的效果，在使用GFTT 需設定兩個interest point 的最短距離。

GFTT 改變了最後的scoring function，變成R = min(λ1, λ2)。

fast

Features from Accelerated Segment Test(FAST) 由Edward Rosten 和Tom Drummond 提出，主要目的在於提升速度。為了在即時處理(real-time)的應用上，速度便成為很重要的條件，然而Harris 和 SUSAN 雖然能求出精確的key point 但在計算上過於繁雜，和FAST相比速度較慢。

FAST 中還有一個很重要的加速機制。從參考點周圍的16的pixel中取四點，每點均差90度，以上圖舉例說明，取1, 5, 9, 13，若四個pixel的亮度值有超過三點符合條件：In < Ip - Threshold 或 In > Ip+ Threshold ，則繼續逐一做比較，但若少於四點符合條件，該點直接判定不為keypoint，加入這樣的機制大大提升速度，但也造成一些問題。

• 在設定須連續超過16個pixel的n個則判定為keypoint，若n值低於12，會有太多的false positive ，尤其是當影像中每種物件間的對比度不高或是雜訊過多時，精確度不高。

• 在選擇pixel點做比較並非每次均會得到最佳的結果，FAST受keypoint 分布情形影響，會漏掉很多keypoint 或是有太多false positive 

• 因為增加了加速的機制，所以可能有一些keypoint未被偵測到

• 真正的keypoint 的周圍雨會被判定為keypoint

為了解決以上四點問題，因此又增加兩種機制Machine Learning a Corner Detector、Non-maximal Suppression

SIFT

有些keypoint detector例如Harris detector不具備scale invariant的特性，將影像放大原本的corner會被判定為edge。由D.Lowe提出Scale Invariant Feature Transform (SIFT) ，主要目的在於解決在拍攝角度不同時，造成物件被旋轉或scale的問題，希望能使用SIFT萃取出兩張圖的keypoint ，並用於下一步的matching。

2. Keypoint Localization

由上個步驟所得到的 potential keypoint，裡面有會存在edge，在這個步驟中，使用了一個Hessian matrix來計算尺度空間中的關鍵點。Hessian matrix是一個二階偏微分算子，可以用來計算圖像上某個位置的曲率和主曲率方向，接著便可以使用Taylor series來近似計算DoG金字塔的局部極值位置。最後設定一個threshold，若 potential keypoint低於threshold 則不被判定為keypoint。

3. Orientation Assignment

到這邊已具備scale invariant，接下來要處理影像被旋轉的問題。SIFT會計算ketpount的gradient大小and方向，SIFT會在關鍵點周圍的圖像區域中，計算梯度方向直方圖，然後選擇其中最大的方向作為該ketpount的主方向。

4. Keypoint descriptor

在這個步驟中，SIFT會根據每個ketpount的主方向，計算一個128維的feature vector。具體來說，SIFT會將keypoint周圍的圖像區域分成若干個子區域，然後計算每個子區域中的梯度方向直方圖。最終，將這些直方圖串聯起來，形成一個128維的feature vector，用來描述該keypoint的特徵。

surf

Speened Up Robust Features(SURF)由Bay, H., Tuytelaars, T. and Van Gool, L 三人提出，目的在於改善SIFI達到加速的效果，並應用在即時處理(real-time)的應用上。因為SURF的想發是建構在SIFT上，所以同樣的欲解決當了在拍攝角度不同時，造成物件被旋轉或scale的問題。

2. Feature Description

使用Hessian matrix計算關鍵點周圍區域的Haar-wavelet responses，以獲得每個關鍵點的特徵描述向量。Haar-wavelet responses 主要是用來表示 SURF 特徵的局部方向。在每個 SURF 特徵周圍的圖像區域中，Haar-wavelet responses 被用來計算該區域內像素的梯度方向和大小。最後，使用這些梯度大小和方向來計算 SURF 特徵的主方向和描述子，形成一個64維的feature vector，用來描述該keypoint的特徵。

brisk

BRISK(Binary Robust Invariant Scalable Keypoints)基於FAST做改進，具有rotation invariant 和 scale invariant。主要是利用FAST算法進行檢測，為了達到scale invaiant，BRISK會建立高斯金字塔(Gaussian Pyramid)，而速度比SIFI 和 SURF都快。

實踐BRISK可分為四步驟：

1. Feature Extraction

首先先建立高斯金字塔(Gaussian Pyramid)，接著在每層使用FAST偵測出局部極值點，在做Non-maximal Suppression。

4. Keypoint descriptor

以採樣點對keypoint進行二進制編碼，因此keypoint的特徵由一個512bit也就是64Byte的二進制編碼構成

orb

ORB(Oriented FAST and Rotated BRIEF)由Ethan Rublee, Vincent Rabaud, Kurt Konolige and Gary R. Bradski提出，是基於FAST 和 BRIEF的改良版，具有rotation invariant 和 scale invariant。以下分兩點講解對於FAST和 BRIEF改良的部分。

FAST:

首先先建立高斯金字塔(Gaussian Pyramid)，接著使用FAST對每層去偵測keypoint，在使用Harris 找前n 個重要的點。為了解決rotation invariant，FAST會以keypoint 為中心計算patch的intensity weighted centroid，因此方向就是從keypoint到質心(centroid)。

BRIEF:

BRIEF 使一種二進制的描述子，和SURF、SIFI不同，這兩個是使用Histogram的方式來描述特徵，ORB則採用二進制的方式表示。當BRIEF有很高的variance且均值接進0.5時，會有很高的匹配性，但在上一步將特徵加入了方向性，所以特徵更具辨識性，這時variance和均值會變低，所以為了改善這個問題，發展出rBRIEF，使用greedy search找出最高的variance，而均值也會最接近0.5，以提升匹配的效果。

以下為模擬結果，左圖為二元圖，影像呈現一塊一塊，右圖以圓形圈起的部分為corner，兩種方式的參數令的一樣，所以視覺上corner的位置也相同。

以下為模擬結果，前兩張圖僅差在最後使用不同方式標記keypoint，而三張圖都是使用GFTT的方式找keypoint且參數設定相同來，所以三張圖結果一樣。

設定threshold=40，其他則參數則設為預設值，意思是要使用non-maximal suppression，類型為TYPE_9_16表示當16個pixel中有9個滿足條件，則判定為keypoint。

接著將參數傳入detect，detect的輸出包含了檢測到的所有角點的位置和大小等信息。

最後將這些結果標示影像上。

以下為模擬結果，觀察三張圖所偵測到的keypoint數量，未使用non-maximal suppression，在keypoint四周同樣會被判定為keypoint，實踐結果所呈現的keypoint數比其他的還多。因為在分區的時會有餘數，會有一些pixel未被分類到，雖然threshold值設定相同，但先分區在做FAST所偵測到的數量會比地張圖所偵測到的數量還少。

首先將SIFT的參數設定好，這邊參數皆使用預設值，接著將參數傳入detect，使用detect偵測keypoint，而detect的輸出包含了檢測到的所有角點的位置和大小等信息。

最後將這些結果標示影像上，並將偵測到的keypoint數量打印出來。

以下為模擬結果：

以下為模擬結果，兩張圖均拍數同一棟教堂，但拍攝角度不同，第一張為正面照，第二張圖則有些歪斜，可以觀察到幾個主要的特徵點均有兩張圖都有標示到，像是窗戶。兩張圖所偵測到的keypoint數量，第一張圖比第一張圖還多。

在前面講解原理的部分，發現多數都是在改善速度，我分為兩部分比較，以具不具有rotation invariant 和 scale invariant的特性來分類，也就是Harris, GFTT, FAST為一類，SURF, SIFT, BRISK, ORB為一類 。

part1

Harris, GFTT, FAST三種keypoint detector偵測到的結果如下，我有調整FAST的參數，讓偵測到的keypoint數量再1000左右，但GFTT雖然設定1000但偵測到的keypoint數量仍維持在700。從結果可以知道Harris和GFTT的速度差不多，而FAST的速度快了很多。

視覺上三張圖偵測到的點差不多，多聚集在窗戶、中間的玻璃花、屋頂頂端等地方。

part2

我將參數設定的盡量差不多，若沒有重複的部分就照預設值來設定，結果如下，若單看時間長短是SIFI>SURF>BRISK>ORB，但他們所偵測到的keypoint數量不同，且時間也會受參數影響，所以我覺得不能直接下結論，從以下實驗能確定的是SURF和SIFT的速度較BRISK和ORB慢，符合在原理中描述的，BRISK和ORB有使用FAST做加速。

四種不同的keypoint detector所偵測到的點有些微不同，多數聚集在窗戶、門、玻璃花窗上，比較意外的是ORB並沒有判定屋頂頂端為keypoint點。

我在查資料的過程，看到很多人在講解原理後都會做match，而且在原理中也有提到，因為加速，所以精確度會下降，或是是為了提升精確度作改良，所以我使用別人放在網路上的程式碼，一樣比較SURF、SIFT、BRISK、ORB間的差異，因為上面的參數偵測到的keypoint太多做完match後畫面太雜論很難觀察，所以加入一航程式碼看偵測到的keypoint有多少，再調整參數讓keypoint落在100左右。將偵測到的keypoint數量打印出來，可以理解在理論中提到的，每種keypoint detector使用不同方式和空間來描述feature。

程式碼來源：（四十二）特征点检测-ORB , 2021-07-02 , 知乎

以下為實驗結果，以目測來說這部分匹配效果都不是很理想，也許是我所挑選的照片光線、角度差異太大。視覺上是以SURF效果匹配的最正確，尤其在中間玻璃花窗的部分，匹配效果最好。又以BRISK看起來匹配效果最差，左圖中的特徵點幾乎被配對到右圖的高塔上和樓梯扶手上，但也許是我設定參數造成偵測到的keypoint太少，以至於沒辦法匹配，但若再加大keypoint的數量，畫面又太雜亂無法以目測的方式判斷。

本次實作遇到最困難的部分是，因為專利的問題， OpenCV將SURF從Release移除，需自己重新編譯，這是我第一次嘗試自己編譯，找了一些參考的文章，但沒有找到OpenCV 、CMake、Visual Studio 三個版本均和我相同的文章，所以在操作的時候，遇到了很多問題，像是介面長不一樣，或是程式碼有改，像是SIFT、SURF函式使用的方法有改，不能直接使用課本的程式碼，最後我是到OpenCV的網站上查詢函式的格式，只能每跑出一個error單獨到網路上搜尋解決方案。

再看每種keypoint detector的原理時，尤其是以數學是描述的部分都得不是很懂，有嘗試使用ChatGPT協助完成作業，但有時候參照別的參考資料會發現，從ChatGPT有可能得到錯的答案，需要重新跑幾次才會出現正確的解釋，不清楚是不是我問問題的方式描述的不夠清楚，所以ChatGPT無法很精準的回答。這次使用ChatGPT的心得是，他是一個很好用的工具，從ChatGPT得到的答案我會當成一個方向，以他給我的幾項重點去搜尋資料，否則接去在網路上查資料像是大海撈針，會讓我不知道怎麼下手。