Programming 5
Keypoint Feature Detection
Goal
學習編寫幾種由OpenCV實現的關鍵點檢測算法(GFTT, SIFT, SURF, FAST, BRISK, ORB)。
比較這些算法的多尺度檢測能力。
作業環境
硬體規格:
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.3.0
問題與解決方法
由於 SIFT 算法擁有專利權，我先以之前一直使用的 OpenCV 4.7.0 版本，並且參考了OpenCV 4 Computer Vision Application Programming Cookbook CH8 提供的程式碼進行測試，確實沒有辦法直接使用。
使用 Chat GPT 詢問此問題得知 SIFT 算法在 3.4.11 之後的版本被移到了 contrib 程式庫中，於是我下載 4.7.0 版本的 contrib 程式庫，並使用 CMAKE 重新編譯 OpenCV ，以下為步驟。
在 Github 上找到 OpenCV_contrib 並選擇版本下載。
接著使用 CMAKE 編譯，source code 選擇 OpenCV 的 sources 資料夾，並解創建一個新的資料夾放置新編譯出來的 OpenCV，必須跟原本的分開，避免混淆，按下Configure。
找到 OPENCV_EXTRA_MODULES_PATH 添加剛才下載的 contrib 庫中的 modules 資料夾，並將上面的 OPENCV_ENABLE_NONFREE 打勾，因為這個版本的 SIFT 不是屬於免費功能的。
接著按下 Generate，完成後可以直接按下 Open Project 打開所有專案。
打開後對所有方案進行建置，這會需要一段時間。
確認無錯誤訊息，建置成功。
接著找到 CMakeTargets 的 INSTALL 選擇"僅建置 INSTALL"。
這樣就成功將 contrib 函式庫編譯進 OpenCV 了。
編譯出來的 OpenCV 會在剛剛選定的資料夾內，名稱為 install ，可以更改名稱並移到想要的位置。
因為是新編譯出來的 OpenCV，所以也必須完成之前在 Exercise2 中做過的一些設定，才能開始使用。
完成了 contrib 庫的添加和編譯，卻還是看到一樣的錯誤訊息。
接著當我向 Chat GPT 詢問 SIFT 的路徑想確認 OpenCV 4.7.0 的 contrib 中有沒有 SIFT 時得知了從 4.4 版開始，SIFT 也從 contrib 被移除了。
於是我進入 xfeatures2.hpp 尋找，確實還是沒有 SIFT的相關物件和函式，但這個步驟應該在開始前在 Github 上就能確認，就不會浪費太多時間。
接著我在 Github 確認了 4.3.0 版本的 contrib 還存在 SIFT 算法，並且重新安裝了 4.3.0 版本的 OpenCV 將4.3.0 版的 contrib 編譯進去，必須對應版本不然會發生編譯錯誤。
完成以上建置後，範例程式碼就能成功編譯沒有錯誤訊息了。
此程式使用的影像是我自行拍攝的影像，設備為 iPhone Xs 的內建相機 (並調整尺寸為500*375)
第一張是以手電筒補光的影像。
第二張是沒有補光，並且物件有些微旋轉，鏡頭視角略低的影像，這些變化是為了想要驗證特徵點在 translation, rotation, scale 和 intensity 的不變性。
GFTT（Good Features to Track）
簡介：
GFTT 特徵點檢測算法的原理基於以下假設：在圖像的局部區域中，如果存在著明顯的邊緣、角點或紋理變化，則這些區域更容易被追蹤和匹配，因為它們在不同圖像之間的外觀變化較大。
GFTT 算法的主要步驟：
計算圖像的梯度：使用梯度算子（例如Sobel算子）計算圖像在水平和垂直方向上的梯度。
計算局部自相關矩陣：對於每個像素，計算其周圍區域的自相關矩陣，該矩陣描述了像素周圍區域的特徵。
計算響應函數：通過計算自相關矩陣的特徵值，計算每個像素的響應函數值。響應函數的計算側重於尋找具有高角度變化的像素。
選擇具有最高響應值的特徵點：通過設定閾值或選擇具有最高響應值的固定數量的特徵點，確定最終的特徵點。
GFTT 的參數：
maxCorners：設定要檢測的最大特徵點數量。
qualityLevel：指定特徵點的品質閾值，該閾值用於篩選具有較低品質的特徵點。
minDistance：指定特徵點之間的最小距離，以避免在過於接近的區域檢測到重複的特徵點。
blockSize：定義計算特徵點響應函數時使用的鄰域區域大小。
useHarrisDetector：指定是否使用 Harris 角點檢測算法作為特徵點選擇的標準。如果設置為 false，則使用 GFTT 的原始形式。
k：在指定使用 Harris 角點算法時才生效的參數，也就是計算角點響應值的係數 k。
程式碼
程式碼解釋：
以灰階形式讀入影像 object1.jpg 存儲在 image 中。
定義特徵點容器：建立 vector 類型的變數 keypoints，用於存儲檢測到的特徵點。
創建 GFTT 檢測器：使用 cv::GFTTDetector::create 函式創建一個 GFTT 檢測器的指針 ptrGFTT，設定最多檢測特徵點數量為 500，特徵點的品質閾值為 0.01，特徵點之間的最小距離為 10。
執行特徵點檢測：使用 ptrGFTT->detect 函式對影像進行特徵點檢測，檢測結果將存儲在 keypoints 中。
繪製特徵點：使用迭代器 it 依次遍歷所有檢測到的特徵點，並在每個特徵點的位置畫一個半徑為 3 的圓。
顯示特徵點：創建一個名為"GFTT"的視窗，並在該窗口中顯示帶有特徵點的影像。
這段程式碼的目的是使用 GFTT 算法檢測影像中的特徵點並將其視覺化。
結果
maxCorners=500
qualityLevel=0.01
minDistance=10
object1
object2
接著我將 qualityLevel 提升為 0.02 因為在 object1 有一些不屬於物件的 keyKeypoint ，並且將 maxCorners 下降至 200，因為偵測出的 keyKeypoint 數量也沒到最大值這麼多，我認為這樣的更動可以更準確。
更改參數
maxCorners=200
qualityLevel=0.02
minDistance=10
object1
object2
FAST（Features from Accelerated Segment Test）
簡介：
FAST 的原理是基於加速分割測試，通過對圖像的每個像素進行測試，判斷該像素是否為特徵點。並且該算法通過進行二進制測試來加速計算，從而實現高效率的特徵檢測，這使得FAST算法成為許多實時應用和資源受限場景中常用的特徵檢測算法。
FAST 算法的主要步驟：
選擇一個像素作為中心像素。
定義一個閥值 t，用於判斷像素的亮度變化。
選擇一個半徑為3的圓形區域，該區域上有 16 個像素。
對於這 16 個像素，檢查它們和中心像素的亮度變化情況。
如果有連續的 n 個像素明顯亮於或暗於中心像素加上閥值 t，則中心像素被認為是一個特徵點。
重複步驟 1 到 5，對圖像的每個像素進行測試，得到所有的特徵點。
可選：進行非極大值抑制，過濾掉局部最大值周圍的特徵點，以達到特徵點的稀疏性。
FAST的參數：
Threshold：判斷像素的亮度變化是否足夠大以被視為特徵點。
Non-maximum Suppression（非極大值抑制）：用於過濾掉局部最大值周圍的特徵點，以達到特徵點的稀疏性，設置為 true 或 false。
Detector Type：FAST 算法有幾種變種，如 FAST-9、FAST-10、FAST-12 和 FAST-16，這些數字表示檢測區域上像素的數量。
Order：用於決定在檢測到特徵點後如何對它們進行排序。可以選擇像素的亮度值或特徵點的響應值進行排序。
程式碼
程式碼解釋：
讀取灰階影像。
keypoints.clear：清空存儲特徵點的容器，確保 keypoints 內為空的。
創建 FAST 特徵檢測器，閥值設置為 40，用於判斷像素的亮度變化是否足夠大以被視為特徵點。
使用FAST檢測器對輸入影像進行特徵檢測，並將檢測到的特徵點存儲在 keypoints 中。
將檢測到的特徵點繪製在原始影像上。
創建視窗，並顯示繪製了特徵點的影像。
結果
Threshold=40
object1
object2
由於閥值設定為判斷像素的亮度變化是否足夠大以被視為特徵點，我將閥值調整為 30 讓更多特徵點能夠被納入。
Threshold=30
object1
object2
若把非極大值抑制設定為 false ，會導致特徵點太過密集。
Threshold=30
Non-maximum Suppression
=false
object1
object2
SIFT（Scale-Invariant Feature Transform）
簡介：
SIFT（尺度不變特徵轉換）算法是由David Lowe（大衛·羅）在1999年提出的。David Lowe 是一位加拿大計算機科學家和教授，他在 University of British Columbia（英屬哥倫比亞大學）擔任教職。
SIFT 算法的提出解決了傳統特徵檢測算法在尺度變化、旋轉變化和光照變化等方面的限制。該算法通過在多個尺度下檢測關鍵點，提取並描述這些關鍵點的局部特徵，從而實現對圖像的高效識別和匹配。為計算機視覺領域的經典算法之一，被廣泛應用於圖像識別、物體檢測、三維重建等領域。
David G. Lowe
原理與步驟
尺度空間構建：
將原始圖像應用高斯濾波器進行模糊操作，生成一系列不同尺度的圖像，能夠去除圖像中的高頻細節信息，保留圖像的整體結構，並且每個尺度層級都對應著一個特定的高斯模糊參數，用於控制模糊的程度。
然後，通過對模糊後的圖像進行下採樣，生成不同尺度的圖像金字塔。金字塔的每一層都是上一層的圖像下採樣得到的，即尺度變小的圖像，這樣就得到了一個多尺度的圖像金字塔，其中每一層圖像都對應著不同的尺度。
尺度空間構建的目的是為了使 SIFT 算法能夠在不同尺度上對圖像進行特徵檢測和描述，由於圖像中的物體可能在不同尺度上具有不同的外觀，通過構建尺度空間，可以更好地捕捉並描述這些尺度變化的特徵。這使得SIFT算法能夠對於物體的尺度、旋轉和光照變化具有較好的 Robustness，從而實現準確的圖像識別和匹配。
極值點檢測：
使用 DoG（Difference of Gaussians），目的是找到圖像中局部區域的極值點，即具有最大或最小值的像素，這些像素被認為是關鍵點的候選點。
在進行極值點檢測時，需要考慮像素的局部環境，例如像素的周圍區域或像素的相鄰像素。通常使用一個固定大小的窗口或鄰域來定義局部區域，檢測時可以使用不同的方法，如差分、梯度等。
通過極值點檢測，可以找到圖像中具有顯著變化或紋理的區域，這些區域可能包含有用的特徵信息，用於生成特徵描述子，從而實現圖像的識別和匹配。
關鍵點定位：
利用局部區域的梯度信息來確定每個關鍵點的位置和尺度，從而描述其局部結構特徵。並使用插值方法，以提高關鍵點的定位精度。同時，通過過濾掉低對比度和不穩定的關鍵點，能夠去除那些在特徵描述和匹配中可能產生不可靠結果的關鍵點。
經過關鍵點定位，能夠獲得具有準確位置和尺度的關鍵點，並具有較好的對比度和穩定性。
方向估計：
對於每個關鍵點，計算其主方向，目的是增強特徵的旋轉不變性，使得特徵描述子能夠在圖像旋轉的情況下保持穩定性。
在方向估計中，計算關鍵點周圍區域的梯度方向，通過直方圖找到主要的梯度方向，即該區域中梯度方向最強的方向，這一步驟可以使用直方圖峰值檢測等方法來實現。
為每個關鍵點確定主方向後，可以將該方向作為特徵描述子計算的參考方向。通過將特徵描述子旋轉到主方向上，可以實現對於圖像旋轉的不變性，從而提高特徵描述子的匹配準確性。
SIFT 的參數:
nfeatures：控制檢測到的關鍵點的數量。設定此值來增加或減少檢測到的關鍵點數量。
nOctaveLayers：每個金字塔層級的圖像數量。值越高，金字塔的層級就越多，特徵的尺度也就更多。
contrastThreshold：檢測關鍵點時的對比度閾值。值越低，越容易檢測到具有較低對比度的關鍵點。
edgeThreshold：用於過濾邊緣關鍵點的邊緣閾值。值越大，越容易濾除邊緣上的關鍵點。
sigma：高斯模糊的初始尺度。可以調整這個值來改變檢測到的特徵的大小。
程式碼
程式碼解釋：
讀取影像為灰階模式。
建立 SIFT 特徵檢測器的對象 ptrSIFT。
使用 ptrSIFT 對影像進行 SIFT 特徵檢測，檢測結果將存儲在 keypoints 中，其中包含了檢測到的關鍵點的位置、尺度和方向等信息。
將檢測到的關鍵點繪製到原始圖像上，並顯示帶有關鍵點的特徵圖像。
結果
查看 xfeatures2d.hpp 中發現 SIFT 的默認參數為：
nfeatures=0 (不限制)
nOctaveLayers=3 (層)
contrastThreshold=0.04
edgeThreshold=10
sigma=1.6
object1
object2
結果分析：
SIFT 是通過在不同尺度的圖像上應用高斯模糊來構建尺度空間，並通過在每個尺度上檢測極值點來確定關鍵點，所以結果中會出現有大有小的特徵點，代表不同尺度的圖像區域具有不同的細節級別和特徵。
在較低的尺度級別上，由於較強的細節和邊緣，會產生較小的特徵點。而在較高的尺度級別上，由於較弱的細節，會產生較大的特徵點。這種大小不一的特徵點有助於提取圖像中不同尺度的細節信息，並提供更全面和穩定的特徵描述。同時，這些大小不一的特徵點也可以提供一定程度上的尺度不變性，使得 SIFT 算法能夠在不同尺度的圖像中進行特徵匹配。
可以通過設置 nOctaveLayers 參數的值來控制生成尺度空間的層數，從而影響生成的特徵點的大小範圍。
object1
nOctaveLayers=5
object2
nOctaveLayers=5
結果分析：
將 nOctaveLayers 設為 5 層時，可以發現更為細緻的特徵點被檢測出來，而由於 nfeatures 是無限制狀態，有多少特徵點都會被檢測出來，所以明顯感覺到計算量變大很多。但就準確度來說感覺是非常精確的，除了我設定的物件之外，桌面紋路也出現了許多特徵點。
SURF（Speeded-Up Robust Features）
簡介：
SURF 是由 Herbert Bay 等人在 2006 年提出的，旨在加速傳統的特徵提取算法（例如SIFT）並保持其 Robustness。
SURF 和 SIFT 算法都基於尺度空間和局部特徵，但它們使用不同的方法。SIFT 使用高斯差分金字塔來構建尺度空間，而 SURF 使用高斯金字塔。此外，SURF算法使用快速 Hessian 矩陣檢測極值點，而 SIFT 算法使用 DoG（Difference of Gaussians）檢測極值點。
SURF 的原理和步驟：
尺度空間構建：使用高斯金字塔來生成圖像的多尺度表示。
特徵點檢測：在每個尺度的圖像中，使用 Hessian 矩陣來檢測關鍵點。Hessian 矩陣表示圖像上的局部結構信息，通過計算矩陣的行列式和追蹤來檢測圖像的區域極值點，這些極值點被視為關鍵點的候選點。
方向估計：對每個關鍵點，使用圖像的 Haar 小波響應來估計關鍵點的主方向。將關鍵點周圍的區域劃分為小的子區域，並計算每個子區域的 Haar 小波響應，主方向是響應最大的方向。
特徵描述：使用了一種稱為簡單快速特徵描述子（Simple Fast Feature Descriptor）的方法，該描述子基於子區域中的 Haar 小波響應。使用關鍵點的主方向，將每個關鍵點周圍的區域劃分為小的子區域。在每個子區域中，計算 Haar 小波響應的方向和大小。然後，使用這些響應值來構建特徵描述子。
SURF 的參數：
hessianThreshold：Hessian 矩陣的閾值，用於關鍵點檢測。僅保留具有大於該閾值的 Hessian 矩陣行列式的極值點作為關鍵點。
nOctaves：金字塔的總層數。
nOctaveLayers：每個金字塔層級的子層數。
extended：描述子的長度。如果為 true，則描述子的長度為 128 維；如果為 false，則描述子的長度為 64 維。
upright：描述子方向。如果為 true，則不計算特徵點的方向；如果為 false，則計算特徵點的主方向。
程式碼
程式碼解釋：
讀取灰階影像。
清空 keypoints ，準備存儲檢測到的 SURF 特徵點。
創建 SURF 特徵檢測器的指針 ptrSURF。指定閾值為 2000，用於控制特徵點的檢測數量。
使用 ptrSURF 檢測圖像中的 SURF 特徵點，並存儲在 keypoints 中。
創建一個空白的 featureImage 矩陣，用於繪製特徵點。
將檢測到的特徵點繪製到原始圖像上，並將結果存儲在 featureImage 中。
將特徵點的繪製結果 featureImage 顯示，視覺化檢測到的SURF特徵點。
結果
object1
hessianThreshold=2000
object2
hessianThreshold=2000
object1
hessianThreshold=1000
object2
hessianThreshold=1000
結果分析：
降低閥值後觀察，SURF 對於細緻的特徵偵測似乎較 SIFT 弱一些，並且對於大尺度的特徵較為敏感。
BRISK（Binary Robust Invariant Scalable Keypoints）
簡介：
BRISK 是一種特徵點檢測和描述符生成的算法，用於在圖像中檢測並描述關鍵點。
原理與步驟：
尺度空間構建：使用多尺度的圖像金字塔，通過應用高斯模糊操作在不同尺度上對圖像進行平滑處理，生成多尺度的圖像。
尺度不變關鍵點檢測：在每個尺度的圖像中，使用分布式二進制點的方法尋找關鍵點。BRISK 使用較大的角度值來產生更多的二進制描述子，這樣可以提高關鍵點的區分性。
方向估計：對於每個關鍵點，計算其主要方向。可以通過檢測圖像梯度的方向直方圖來實現。
特徵描述符生成：根據關鍵點的位置和方向，生成與尺度和旋轉不變的二進制描述符。BRISK 使用圓形區域對特徵點周圍的像素進行采樣，並將亮度差異轉換為二進制字符串。
BRISK 的參數：
thresh: 檢測關鍵點的閾值，用於過濾低對比度的區域。預設值為30。
octaves: 圖像金字塔的層數，用於檢測多尺度的關鍵點。預設值為3。
patternScale: 二進制描述子的比例因子，影響特徵描述子的大小和區分能力。預設值為1.0。
scaleRange: 尺度空間的範圍，用於計算每個尺度上的特徵點。預設值為10。
orientationNormalized: 是否進行方向正規化，以確保關鍵點的旋轉不變性。預設值為 true。
scaleNormalized: 是否進行尺度正規化，以確保關鍵點的尺度不變性。預設值為 true。
varyingThresh: 是否使用可變閾值，在不同尺度上調整關鍵點的閾值。預設值為 true。
coreThreshold: 核心關鍵點的閾值，用於選擇最優的關鍵點。預設值為20。
程式碼
程式碼解釋：
讀取影像為灰階模式。
清空 keypoints。
建立 BRISK 特徵檢測器，並設置閾值為 60 和金字塔層數為 5。
使用 ptrBRISK 檢測圖像中的 BRISK 特徵點，將結果存在 keypoints 中。
繪製特徵點。
顯示特徵點檢測的結果圖像。
結果
thresh=60
octaves=5
patternScale=1.0
object1
object2
thresh=60
octaves=5
patternScale=2.0
結果分析：
將 patternScale 提高至 2.0 之後，大尺度的特徵點減少了，似乎也增加了描述子的區分能力。
ORB（Oriented FAST and Rotated BRIEF）
簡介：
ORB 是一種特徵檢測和描述子生成算法，結合了 FAST 的關鍵點檢測的速度和 BRIEF 的描述子，提供一種快速且有效的特徵檢測和描述子生成方法。這使得ORB在實時應用和資源受限的場景中具有良好的性能。
ORB 的原理：
FAST 關鍵點檢測：使用 FAST 算法，通過比較像素點和其周圍像素點的亮度值，找到具有一定數量連續像素的角點。
方向估計：通過計算周圍像素的梯度方向，找到主要的梯度方向作為關鍵點的方向。
BRIEF 描述子生成：ORB 使用 BRIEF 的描述子生成，基於計算特定位置的像素對的亮度差異，並將這些差異轉換為二進制串。
ORB 的參數：
nFeatures：要檢測的最大特徵點數量。
scaleFactor：圖像金字塔的縮放因子，用於生成不同尺度的圖像。
nLevels：圖像金字塔的層數，控制生成多少個尺度的圖像。
edgeThreshold：邊緣閾值，用於檢測關鍵點時過濾邊緣點。
firstLevel：圖像金字塔的起始層級。
WTA_K：BRIEF 描述子生成過程中每個像素的比較次數，通常為2或4。
scoreType：計算關鍵點的得分類型，可以是 HARRIS、FAST 或等效於 FAST 的 FASR。
patchSize：計算關鍵點得分時使用的區域大小。
fastThreshold：FAST 算法中用於判斷關鍵點的亮度差異閾值。
程式碼
程式碼解釋：
讀取影像為灰階模式。
清空關鍵點容器 keypoints。
創建一個ORB特徵檢測器對象，並設置最大特徵點數量參數為 75 和圖像金字塔的縮放因子 1.2，以及圖像金字塔的層數 8。
使用ptrORB 檢測圖像中的關鍵點，存在keypoints中。
將檢測到的關鍵點繪製在原始圖像上，並存在 featureImage 中。
創建一個窗口來顯示結果，並顯示包含關鍵點的圖像。
結果
nFeatures=75
scaleFactor=1.2
nLevels=8
object1
object2
nFeatures=175
scaleFactor=1.2
nLevels=3
object1
object2
結果分析：
原本的結果在 object1 中手錶和美工刀都沒特徵點出現，本來認為原因可能是最大特徵點數量設置太少導致，但當我將其調整為 175 時，一樣沒有出現，只增加了魔術方塊上的特徵點數量，所以不是最大數量導致，接著降低金字塔層數為 3 層，此時特徵點就出現了，由此可知原因是手表和美工刀的特徵點尺度較小，設定太大反而偵測不出來。
額外補充
在做完此實驗之後我向 Chat GPT 再次提問 SIFT 相關專利問題發現此專利早在 2019 年就已經到期，照理說 OpenCV 應該會重新加入這個強大的算法。
於是我嘗試在 OpenCV 4.7.0 內翻找，發現xfeatures2d.hpp 並不存在，只剩下features2d.hpp。
進入 features2d.hpp 發現 SIFT 函式其實是存在的只是被移動了位置，代表 SIFT 在現今版本早就已經開放可以使用了。
上面範例程式碼以及網路上一些舊的程式碼都是引入 xfeatures2d.hpp 去 create 檢測器，這是在使用 3.4.11 至 4.3.0 版本的 contrib 庫時使用的程式碼，所以會有錯誤訊息，因為在 4.4.0 之後的版本的 SIFT 和 SURF 都放在 features2d.hpp 裡面。
include 正確的函示庫，並用以上的程式碼 creat 就沒報錯了。
在 4.7.0 版本成功可用。
結論與心得
我在 Github 確認了 SIFT 算法在 OpenCV 從 3.4.11 至 4.3.0 版本因為專利權的保護期，被移動到 contrib 庫中而且被歸類為 NONFREE，想要使用還得在編譯 OpenCV 時去打勾 NONFREE 選項才能使用，4.4.0 之後被重新加入在 features2d.hpp 函式庫，所以想使用 SIFT 的話，不需要再另外編譯 contrib 或 VLfeat 這類額外的函式庫，在 OpenCV 提供的主函式庫就有了。
這次實作超過一半時間在處理環境問題，繞了一大圈才發現答案就在眼前。