全面綜述：圖像特徵提取與匹配技術

加入極市專業CV交流羣，與 1 0000+來自港科大、北大、清華、中科院、CMU、騰訊、百度 等名校名企視覺開發者互動交流！

同時提供每月大咖直播分享、真實項目需求對接、乾貨資訊彙總，行業技術交流。關注 極市平臺 公衆號，回覆 加羣， 立刻申請入羣~

作者：William

來源：自動駕駛全棧工程師知乎專欄， https://www.zhihu.com/people/william.hyin/columns

特徵提取和匹配是許多計算機視覺應用中的一個重要任務，廣泛運用在運動結構、圖像檢索、目標檢測等領域。每個計算機視覺初學者最先了解的特徵檢測器幾乎都是1988年發佈的HARRIS。在之後的幾十年時間內各種各樣的特徵檢測器/描述符如雨後春筍般出現，特徵檢測的精度與速度都得到了提高。

特徵提取和匹配由關鍵點檢測，關鍵點特徵描述和關鍵點匹配三個步驟組成。不同的檢測器，描述符以及匹配器之間的組合往往是初學者疑惑的內容。本文將主要介紹關鍵點檢測、描述以及匹配的背後原理，不同的組合方式之間的優劣，並提出幾組根據實踐結果得出的最佳組合。

Background Knowledge

特徵(Feature)

特徵是與解決某個應用程序相關的計算任務有關的一條信息。特徵可能是圖像中的特定結構，例如點，邊緣或對象。特徵也可能是應用於圖像的一般鄰域操作或特徵檢測的結果。這些功能可以分爲兩大類：

1、圖片中特定位置的特徵，如山峯、建築角落、門口或有趣形狀的雪塊。這種局部化的特徵通常被稱爲關鍵點特徵(或者甚至是角點) ，它們通常以點位置周圍出現的像素塊來描述，這個像素塊往往被稱作圖像補丁(Image patch)。

2、可以根據其方向和局部外觀（邊緣輪廓）進行匹配的特徵稱爲邊緣，它們也可以很好地指示圖像序列中的對象邊界和遮擋事件。

特徵點

邊緣

特徵提取和匹配的主要組成部分

1、檢測(detection)：識別感興趣點

2、描述(description): 描述每個特徵點周圍的局部外觀，這種描述在光照、平移、尺度和平面內旋轉的變化下是(理想的)不變的。我們通常會爲每個特徵點提供一個描述符向量。

3、匹配(mataching): 通過比較圖像中的描述符來識別相似的特徵。對於兩幅圖像，我們可以得到一組對(Xi，Yi)->(Xi’ ，Yi’) ，其中(Xi，Yi)是一幅圖像的特徵，(Xi’ ，Yi’)是另一幅圖像的特徵.

Detector

關鍵點/興趣點(Key point/ Interest point)

關鍵點也稱興趣點，是紋理中表達的點。關鍵點往往是物體邊界方向突然改變的點或兩個或多個邊緣段之間的交點。它在圖像空間中具有明確的位置或很好地定位。即使圖像域的局部或全局存在如光照和亮度變化等的擾動，關鍵點仍然是穩定，可以被重複可靠地計算出。除此之外它應該提供有效的檢測。

關鍵點的計算方法有兩種:

1、基於圖像的亮度（通常通過圖像導數）。

2、基於邊界提取（通常通過邊緣檢測和曲率分析）。

關鍵點檢測器光度和幾何變化的不變性

在OPENCV庫，我們可以選擇很多特徵檢測器，特徵檢測器的選擇取決於將要檢測的關鍵點的類型以及圖像的屬性，需要考慮相應檢測器在光度和幾何變換方面的魯棒性。

選擇合適的關鍵點檢測器時，我們需要考慮四種基本轉換類型：

1、旋 轉變換

2、尺度變換

3、強度變換

4、仿射變換

塗鴉序列是計算機視覺中使用的標準圖像集之一，我們可以觀察到第i+n幀的塗鴉圖片包括了所有的變換類型。而對於高速公路序列，當專注於前面的車輛時，在第i幀和第i + n幀之間只有比例變化以及強度變化。

傳統的HARRIS傳感器在旋轉和加性強度偏移情況下具有較強的魯棒性，但對尺度變化、乘性強度偏移(即對比度變化)和仿射變換敏感。

自動尺度選擇

爲了在理想尺度上檢測關鍵點，我們必須知道(或找到)它們在圖像中的各自維度，並適應本節前面介紹的高斯窗口 w (x，y) 的大小。如果關鍵點尺度是未知的或如果關鍵點與存在於不同的大小圖像中，檢測必須在多個尺度級連續執行。

基於相鄰層之間的標準差增量，同一個關鍵點可能被多次檢測到。這就提出了選擇最能代表關鍵點的“正確”尺度的問題。1998年Tony Lindeberg 發表了一種“自動選擇比例的特徵提取(Feature detection with automatic scale selection)”的方法。它提出了一個函數 f (x，y，scale) ，該函數可以用來選擇在尺度上 FF 有穩定最大值的關鍵點。Ff 最大化的尺度被稱爲各關鍵點的“特徵尺度”。

如在下圖中顯示了這樣一個函數 FF，它經過了幾個尺度級別的評估，在第二張圖中顯示了一個清晰的最大值，可以看作是圓形區域內圖像內容的特徵尺度。

一個好的檢測器能夠根據局部鄰域的結構特性自動選擇關鍵點的特徵尺度。現代關鍵點探測器通常具有這種能力，因此對圖像尺度的變化具有很強的魯棒性。

常見關鍵點檢測器

關鍵點檢測器是一個非常受歡迎的研究領域，因此這些年來已經開發了許多強大的算法。關鍵點檢測的應用包括物體識別和跟蹤，圖像匹配和全景拼接以及機器人制圖和3D建模等。檢測器的選擇除了需要比較上述轉換中的不變性之外，還需要比較檢測器的檢測性能和處理速度。

經典關鍵點檢測器

經典關鍵點檢測器的目的是爲了最大化檢測精度，複雜度一般不是首要考慮因素。

HARRIS- 1988 Harris Corner Detector (Harris, Stephens)

Shi, Tomasi- 1996 Good Features to Track (Shi, Tomasi)

SIFT- 1999 Scale Invariant Feature Transform (Lowe) -None free

SURT- 2006 Speeded Up Robust Features (Bay, Tuytelaars, Van Gool) -None free

現代關鍵點檢測器

近年來，一些更快的探測器已經開發出來，用於智能手機和其他便攜設備上的實時應用。下面的列表顯示了屬於這個組的最流行的檢測器:

FAST- 2006 Features from Accelerated Segment Test (FAST) (Rosten, Drummond)

BRIEF- 2010 Binary Robust Independent Elementary Features (BRIEF) (Calonder, et al.)

ORB- 2011 Oriented FAST and Rotated BRIEF (ORB) (Rublee et al.)

BRISK- 2011 Binary Robust Invariant Scalable Keypoints (BRISK) (Leutenegger, Chli, Siegwart)

FREAK- 2012 Fast Retina Keypoint (FREAK) (Alahi, Ortiz, Vandergheynst)

KAZE- 2012 KAZE (Alcantarilla, Bartoli, Davidson)

Feature Descriptor

基於梯度與二進制的描述符

由於我們的任務是在圖像序列中找到對應的關鍵點，因此我們需要一種基於相似性度量將關鍵點彼此可靠地分配的方法。很多文獻中已經提出了各種各樣的相似性度量(稱爲Descriptor)，並且在很多作者已經同時發佈了一種用於關鍵點檢測的新方法以及針對其關鍵點類型進行了優化的相似性度量。也就是說已經封裝好的OPENCV關鍵點檢測器函數大部分同樣可以用來生成關鍵點描述符。

區別在於：

關鍵點檢測器是一種根據函數的局部最大值從圖像中選擇點的算法，例如我們在HARRIS檢測器中看到的“角度”度量。

關鍵點描述符是用於描述關鍵點周圍的圖像補丁值的向量。描述方法有比較原始像素值的方法也有更復雜的方法，如梯度方向的直方圖。

關鍵點檢測器一般是從一個幀圖片中尋找到特徵點。而描述符幫助我們在“關鍵點匹配”步驟中將不同圖像中的相似關鍵點彼此分配。如下圖所示，一個幀中的一組關鍵點被分配給另一幀中的關鍵點，以使它們各自描述符的相似性最大化，並且這些關鍵點代表圖像中的同一對象。除了最大化相似性之外，好的描述符還應該能夠最大程度地減少不匹配的次數，即避免將彼此不對應於同一對象的關鍵點分配給彼此。

基於梯度HOG描述符

雖然出現了越來越多快速的檢測器/描述符組合，但是基於定向直方圖(HOG)描述符之一的尺度不變特徵轉換(SIFT)依然被廣泛運用。HOG的基本思想是通過物體在局部鄰域中的強度梯度分佈來描述物體的結構。爲此，將圖像劃分爲多個單元，在這些單元中計算梯度並將其收集到直方圖中。然後，將所有單元格的直方圖集用作相似性度量，以唯一地標識圖像塊或對象。

SIFT/SURF使用HOG作爲描述符，既包括關鍵點檢測器，也包括描述符，功能很強大，但是被專利保護。SURF是在SIFT的基礎上改進，不僅提高了計算速度，而且更加安全魯棒性，兩者的實現原理很相似。在此我先僅介紹SIFT。

SIFT方法遵循五步過程，下面將對此進行簡要概述。

首先，使用稱爲“拉普拉斯高斯（LoG）”的方法來檢測圖像中的關鍵點，該方法基於二階強度導數。LoG應用於圖像的各種比例級別，並且傾向於檢測斑點而不是拐角。除了使用唯一的比例級別外，還根據關鍵點周圍局部鄰域中的強度梯度爲關鍵點分配方向。

其次，對於每個關鍵點，其周圍區域都會通過消除方向而改變，從而確保規範的方向。此外，該區域的大小將調整爲16 x 16像素，從而提供了標準化的圖像補丁。

第三，基於強度梯度_Ix_和_Iy_計算歸一化圖像補丁內每個像素的方向和大小。

第四，將歸一化的貼片劃分爲4 x 4單元的網格。在每個單元內，超出幅度閾值的像素的方向收集在由8個bin組成的直方圖中。

最後，將所有16個單元格的8柱狀直方圖連接到一個128維向量（描述符）中，該向量用於唯一表示關鍵點。

SIFT檢測器/描述符即使在雜波中和部分遮擋下也能夠可靠地識別物體。尺度，旋轉，亮度和對比度的均勻變化是不變的，仿射失真甚至是不變的。

SIFT的缺點是速度低，這使其無法在智能手機等實時應用中使用。HOG系列的其他成員（例如SURF和GLOH）已針對速度進行了優化。但是，它們仍然在計算上過於昂貴，因此不應在實時應用中使用。此外，SIFT和SURF擁有大量專利，因此不能在商業環境中自由使用。爲了在OpenCV中使用SIFT，必須使用 #include <opencv2/xfeatures2d/nonfree.hpp> ，並且需要安裝OPENCV_contribute包，注意一定要在Cmake選項中開啓 OPENCV_ENABLE_NONFREE 。

二進制Binary描述符

基於HOG的描述符的問題在於它們基於計算強度梯度，這是非常昂貴的操作。即使已進行了一些改進（例如SURF），使用了積分圖像，速度提高了，但這些方法仍然不適合處理能力有限的設備（例如智能手機）上的實時應用程序。二進制描述符家族是基於HOG的方法的一種更快（免費）的替代方案，但準確性和性能稍差。

二進制描述符的核心思想是僅僅依賴強度信息(即圖像本身) ，並將關鍵點周圍的信息編碼爲一串二進制數字，當搜索相應關鍵點時，這些數字可以在匹配步驟中非常有效地進行比較。也就是說二進制描述符將興趣點的信息編碼成一系列數字，並作爲一種數字“指紋” ，可用於區分一個特徵和另一個特徵。目前，最流行的二進制描述符是 BRIEF、 BRISK、 ORB、 FREAK 和 KAZE (所有這些都可以在 OpenCV 庫中找到)。

二進制描述符

從高層次的角度來看，二進制描述符由三個主要部分組成：

1、一種描述樣本點位於關鍵點附近的位置的採樣模式( sampling pattern )。

2、一種消除了圖像補丁圍繞關鍵點位置旋轉影響的方向補償方法( orientation compensation)。

3、一種樣本對選擇的方法(ample-pair selection)，它產生成對的樣本點，這些樣本點根據它們的強度值相互比較。如果第一個值大於第二個值，我們就在二進制字符串中寫一個“1” ，否則就寫一個“0”。在對採樣模式中的所有點對執行此操作之後，將創建一個長的二進制鏈(或“ string”)(因此得到描述符類的族名)。

BRISK “二進制魯棒不變可伸縮關鍵點” 關鍵點檢測器 / 描述符是二進制描述符的代表。在此我先僅介紹BRISIK。

2011年Stefan Leutenegger 提出的 BRISK 是一個基於 FAST 的檢測器和一個 Binary描述符 的組合，這個描述符由通過對每個關鍵點鄰域進行專門採樣而獲得的強度比較創建。

BRISK的採樣模式由多個採樣點（藍色）組成，其中每個採樣點周圍的同心環（紅色）表示應用高斯平滑的區域。與某些其他二進制描述符（例如ORB或Brief）相反，BRISK採樣模式是固定的。平滑對於避免混疊非常重要（這種效應會導致不同信號在採樣時變得難以區分-或彼此混疊）。

在樣本對選擇期間，BRISK算法會區分長距離對和短距離對。長距離對（即在樣本圖案上彼此之間具有最小距離的樣本點）用於根據強度梯度估算圖像補丁的方向，而短距離對用於對已組裝的描述符字符串進行強度比較。在數學上，這些對錶示如下：

首先，我們定義所有可能的採樣點對的集合A。然後，我們從A提取子集L，子集L的歐氏距離大於上閾值。L是用於方向估計的長距離對。最後，我們從A提取歐氏距離低於下閾值的那些對。該集合S包含用於組裝二進制描述符串的短距離對。

下圖顯示了短對（左）和長對（右）的採樣模式上的兩種距離對。

從長對中，關鍵點方向向量G 計算如下：

首先，根據歸一化的單位矢量計算兩個採樣點之間的梯度強度，歸一化的單位矢量給出兩個點之間的方向，乘以兩個點在各自比例下的強度差。然後在(2)中，關鍵點方向向量 g 從所有梯度強度的總和中計算出。

基於 g ，我們可以使用採樣模式的方向重新排列短距離配對，從而確保旋轉不變性。基於旋轉不變的短距離配對，可以如下構建最終的二進制描述符：

從 g 計算出關鍵點的方位後，我們使用它使短距離配對旋轉不變。然後，所有對之間的強度 S 被比較並用於組裝可用於匹配的二進制描述符。

OPENCV Detector/Descriptor implementation

目前存在各種各樣的特徵點檢測器/描述符，如 HARRIS, SHI-TOMASI, FAST, BRISK, ORB, AKAZE, SIFT, FREAK, BRIEF。每一種都值得單獨用一篇博客去描述，但是本文的目的是爲了給大家一份綜述，因此不詳細的從原理上分析這些檢測器/描述符。網上有大量描述這些檢測器/描述符的文章，但是我還是建議大家先看OPENCV庫的T utorial: How to Detect and Track Object With OpenCV.

以下我會介紹各個特徵點檢測器/描述符的代碼實現以及參數詳解, 文章結尾會基於實際結果對這些組合進行評價。

有些OPENCV函數可以同時用於檢測器/描述符，但是有的組合會出現問題。

SIFT Detector/Descriptor SIFT detector and ORB descriptor do not work together

int nfeatures = 0;// The number of best features to retain.
int nOctaveLayers = 3;
// The number of layers in each octave. 3 is the value used in D. Lowe paper.
double contrastThreshold = 0.04;
// The contrast threshold used to filter out weak features in semi-uniform (low-contrast) regions.
        double edgeThreshold = 10;// The threshold used to filter out edge-like features.
        double sigma = 1.6;
        // The sigma of the Gaussian applied to the input image at the octave \#0.
xxx=cv::xfeatures2d::SIFT::create(nfeatures, nOctaveLayers, contrastThreshold, edgeThreshold, sigma);

HARRIS Detector

// Detector parameters
int blockSize = 2;     // for every pixel, a blockSize × blockSize neighborhood is considered
int apertureSize = 3;  // aperture parameter for Sobel operator (must be odd)
int minResponse = 100; // minimum value for a corner in the 8bit scaled response matrix
double k = 0.04;       // Harris parameter (see equation for details)
// Detect Harris corners and normalize output
cv::Mat dst, dst_norm, dst_norm_scaled;
dst = cv::Mat::zeros(img.size(), CV_32FC1);
cv::cornerHarris(img, dst, blockSize, apertureSize, k, cv::BORDER_DEFAULT);
cv::normalize(dst, dst_norm, 0, 255, cv::NORM_MINMAX, CV_32FC1, cv::Mat());
cv::convertScaleAbs(dst_norm, dst_norm_scaled);
 
// Look for prominent corners and instantiate keypoints
double maxOverlap = 0.0; // max. permissible overlap between two features in %, used during non-maxima suppression
for (size_t j = 0; j < dst_norm.rows; j++) {
    for (size_t i = 0; i < dst_norm.cols; i++) {
        int response = (int) dst_norm.at<float>(j, i);
        if (response > minResponse) { // only store points above a threshold
 
            cv::KeyPoint newKeyPoint;
            newKeyPoint.pt = cv::Point2f(i, j);
            newKeyPoint.size = 2 * apertureSize;
            newKeyPoint.response = response;
 
      // perform non-maximum suppression (NMS) in local neighbourhood around new key point
            bool bOverlap = false;
            for (auto it = keypoints.begin(); it != keypoints.end(); ++it) {
                double kptOverlap = cv::KeyPoint::overlap(newKeyPoint, *it);
                if (kptOverlap > maxOverlap) {
                    bOverlap = true;
                    if (newKeyPoint.response >
                        (*it).response) {                      
                        // if overlap is >t AND response is higher for new kpt
                        *it = newKeyPoint; // replace old key point with new one
                        break;             // quit loop over keypoints
                    }
                }
            }
            if (!bOverlap) {                                     
            // only add new key point if no overlap has been found in previous NMS
                keypoints.push_back(newKeyPoint); // store new keypoint in dynamic list
            }
        }
    } // eof loop over cols
}     // eof loop over rows

SHI-TOMASIDetector

int blockSize = 6;       
//  size of an average block for computing a derivative covariation matrix over each pixel neighborhood
double maxOverlap = 0.0; // max. permissible overlap between two features in %
double minDistance = (1.0 - maxOverlap) * blockSize;
int maxCorners = img.rows * img.cols / max(1.0, minDistance); // max. num. of keypoints
double qualityLevel = 0.01; // minimal accepted quality of image corners
double k = 0.04;
bool useHarris = false;
// Apply corner detection
vector<cv::Point2f> corners;
cv::goodFeaturesToTrack(img, corners, maxCorners, qualityLevel, minDistance, cv::Mat(), blockSize, useHarris, k);
 
// add corners to result vector
for (auto it = corners.begin(); it != corners.end(); ++it) {
    cv::KeyPoint newKeyPoint;
    newKeyPoint.pt = cv::Point2f((*it).x, (*it).y);
    newKeyPoint.size = blockSize;
    keypoints.push_back(newKeyPoint);
}

BRISIK Detector/Descriptor

int threshold = 30;        // FAST/AGAST detection threshold score.
int octaves = 3;           // detection octaves (use 0 to do single scale)
float patternScale = 1.0f; // apply this scale to the pattern used for sampling the neighbourhood of a keypoint.
xxx=cv::BRISK::create(threshold, octaves, patternScale);

FREAK Detector/Descriptor

bool orientationNormalized = true;// Enable orientation normalization.
bool scaleNormalized = true;// Enable scale normalization.
float patternScale = 22.0f;// Scaling of the description pattern.
int nOctaves = 4;// Number of octaves covered by the detected keypoints.
const std::vector<int> &selectedPairs = std::vector<int>(); 
// (Optional) user defined selected pairs indexes,
xxx=cv::xfeatures2d::FREAK::create(orientationNormalized, scaleNormalized, patternScale, nOctaves,selectedPairs);

FAST Detector/Descriptor

int threshold = 30;// Difference between intensity of the central pixel and pixels of a circle around this pixel
bool nonmaxSuppression = true;// perform non-maxima suppression on keypoints
cv::FastFeatureDetector::DetectorType type = cv::FastFeatureDetector::TYPE_9_16;
// TYPE_9_16, TYPE_7_12, TYPE_5_8
xxx=cv::FastFeatureDetector::create(threshold, nonmaxSuppression, type);

ORB Detector/Descriptor SIFT detector and ORB descriptor do not work together

int nfeatures = 500;// The maximum number of features to retain.
float scaleFactor = 1.2f;// Pyramid decimation ratio, greater than 1.
int nlevels = 8;// The number of pyramid levels.
int edgeThreshold = 31;// This is size of the border where the features are not detected.
int firstLevel = 0;// The level of pyramid to put source image to.
int WTA_K = 2;
// The number of points that produce each element of the oriented BRIEF descriptor.
auto scoreType = cv::ORB::HARRIS_SCORE;
// The default HARRIS_SCORE means that Harris algorithm is used to rank features.
int patchSize = 31;// Size of the patch used by the oriented BRIEF descriptor.
int fastThreshold = 20;// The fast threshold.
xxx=cv::ORB::create(nfeatures, scaleFactor, nlevels, edgeThreshold, firstLevel, WTA_K, scoreType,patchSize, fastThreshold);

AKAZE Detector/Descriptor KAZE/AKAZE descriptors will only work with KAZE/AKAZE detectors.

auto descriptor_type = cv::AKAZE::DESCRIPTOR_MLDB;
// Type of the extracted descriptor: DESCRIPTOR_KAZE, DESCRIPTOR_KAZE_UPRIGHT, DESCRIPTOR_MLDB or DESCRIPTOR_MLDB_UPRIGHT.
int descriptor_size = 0;// Size of the descriptor in bits. 0 -> Full size
int descriptor_channels = 3;// Number of channels in the descriptor (1, 2, 3)
float threshold = 0.001f;// Detector response threshold to accept point
int nOctaves = 4;// Maximum octave evolution of the image
int nOctaveLayers = 4;// Default number of sublevels per scale level
auto diffusivity = cv::KAZE::DIFF_PM_G2;
// Diffusivity type. DIFF_PM_G1, DIFF_PM_G2, DIFF_WEICKERT or DIFF_CHARBONNIER
xxx=cv::AKAZE::create(descriptor_type, descriptor_size, descriptor_channels, threshold, nOctaves,nOctaveLayers, diffusivity);

BRIEF Detector/Descriptor

int bytes = 32;
// Legth of the descriptor in bytes, valid values are: 16, 32 (default) or 64 .
bool use_orientation = false;
// Sample patterns using keypoints orientation, disabled by default.
xxx=cv::xfeatures2d::BriefDescriptorExtractor::create(bytes, use_orientation);

Descriptor Matching

特徵匹配或一般意義上的圖像匹配是圖像配準、攝像機標定和目標識別等計算機視覺應用的一部分，是在同一場景 / 目標的兩幅圖像之間建立對應關係的任務。一種常用的圖像匹配方法是從圖像數據中檢測出一組與圖像描述符相關聯的興趣點。一旦從兩個或更多的圖像中提取出特徵和描述符，下一步就是在這些圖像之間建立一些初步的特徵匹配。

一般來說，特徵匹配方法的性能取決於基本關鍵點的性質和相關圖像描述符的選擇。

我們已經瞭解到關鍵點可以通過將其局部鄰域轉換爲高維向量來描述，高維向量可以捕獲梯度或強度分佈的獨特特徵。

描述符之間的距離

特徵匹配需要計算兩個描述符之間的距離，這樣它們之間的差異被轉換成一個單一的數字，我們可以用它作爲一個簡單的相似性度量。

目前有三種距離度量：

絕對差之和(SAD)- L1-norm
平方差之和(SSD)- L2-norm
漢明距離 (Hamming distance)

SAD和SSD之間的差異在於：首先兩者之間的最短距離是一條直線，給定每個向量的兩個分量，SAD計算長度差之和，這是一維過程。而SSD計算平方和，遵循畢達哥拉斯定律，在一個矩形三角形中，寬邊平方的總和等於斜邊的平方。因此，就兩個向量之間的幾何距離而言， L2-norm 是一種更準確的度量。注意，相同的原理適用於高維描述符。

而漢明距離對於僅由１和０組成的二進制描述符很適合，該距離通過使用XOR函數計算兩個向量之間的差，如果兩個位相同，則返回零如果兩位不同，則爲1。因此，所有XOR操作的總和就是兩個描述符之間的不同位數。

值得注意的是必須根據所使用的描述符的類型選擇合適距離度量。

BINARY descriptors :BRISK, BRIEF, ORB, FREAK, and AKAZE- Hamming distance
HOG descriptors : SIFT (and SURF and GLOH, all patented)- L2-norm

尋找匹配對

讓我們假設在一個圖像中有N個關鍵點及其關聯的描述符，在另一幅圖像中有M個關鍵點。

蠻力匹配(Brute Force Matching)

尋找對應對的最明顯方法是將所有特徵相互比較，即執行N x M比較。對於第一張圖像中給定的關鍵點，它將獲取第二張圖像中的每個關鍵點並計算距離。距離最小的關鍵點將被視爲一對。這種方法稱爲“蠻力匹配(Brute Force Matching)”或“最近鄰居匹配(Nearest Neighbor Matching)”。OPENCV中蠻力匹配的輸出是一個關鍵點對的列表，這些關鍵點對按其在所選距離函數下的描述符的距離進行排序。

快速最近鄰(FLANN)

2014年，David Lowe和Marius Muja發佈了"快速最近鄰(fast library for approximate nearestneighbors(FLANN)")。FLANN訓練了一種索引結構，用於遍歷使用機器學習概念創建的潛在匹配候選對象。該庫構建了非常有效的數據結構（KD樹）來搜索匹配對，並避免了窮舉法的窮舉搜索。因此，速度更快，結果也非常好，但是仍然需要調試匹配參數。

BFMatching和FLANN都接受描述符距離閾值T，該距離閾值T用於將匹配項的數量限制爲“好”，並在匹配不對應的情況下丟棄匹配項。相應的“好”對稱爲“正陽性（TP）”，而錯對稱爲“假陽性（FP）”。爲T選擇合適的值的任務是允許儘可能多的TP匹配，而應儘可能避免FP匹配。根據圖像內容和相應的檢測器/描述符組合，必須找到TP和FP之間的權衡點，以合理地平衡TP和FP之間的比率。下圖顯示了SSD上TP和FP的兩種分佈，以說明閾值選擇。

第一閾值T1被設置爲兩個特徵之間的最大允許的SSD，其方式是選擇了一些正確的正匹配，而幾乎完全避免了錯誤的正匹配。但是，使用此設置也將丟棄大多數TP匹配項。通過將匹配閾值增加到T2，可以選擇更多的TP匹配，但是FP匹配的數量也將顯着增加。在實踐中，幾乎沒有找到TP和FP的清晰明瞭的分離，因此，設置匹配閾值始終是平衡“好”與“壞”匹配之間的折衷。儘管在大多數情況下都無法避免FP，但目標始終是儘可能降低FP次數。在下文中，提出了實現這一目標的兩種策略。

選擇匹配對

BFMatching- crossCheck

只要不超過所選閾值T，即使第二圖像中不存在關鍵點，蠻力匹配也將始終返回與關鍵點的匹配。這不可避免地導致許多錯誤的匹配。抵消這種情況的一種策略稱爲 交叉檢查匹配 ，它通過在兩個方向上應用匹配過程並僅保留那些在一個方向上的最佳匹配與在另一個方向上的最佳匹配相同的匹配來工作。交叉檢查方法的步驟爲：

1、對於源圖像中的每個描述符，請在參考圖像中找到一個或多個最佳匹配。

2、切換源圖像和參考圖像的順序。

3、重複步驟1中源圖像和參考圖像之間的匹配過程。

4、選擇其描述符在兩個方向上最匹配的那些關鍵點對。

儘管交叉檢查匹配會增加處理時間，但通常會消除大量的錯誤匹配，因此，當精度優於速度時，應始終執行交叉匹配。交叉匹配一般僅僅用於BFMatching。

Nearest neighbor distance ratio (NN)/K-nearest-neighbor(KNN)

減少誤報數量的另一種非常有效的方法是爲每個關鍵點計算最近鄰距離比(nearest neighbor distance ratio)。

KNN與 NN 的區別在與 NN 每個特徵點只保留一個最好的匹配 (keeping only the best match)，而 KNN 每個特徵點保留k個最佳匹配(keeping the best k matches per keypoint). k一般爲2.

主要思想是不要將閾值直接應用於SSD。相反，對於源圖像中的每個關鍵點，兩個(k=2)最佳匹配位於參考圖像中，並計算描述符距離之間的比率。然後，將閾值應用於比率，以篩選出模糊匹配。下圖說明了原理。

在該示例中，將具有關聯描述符da的圖像補丁與其他兩個具有描述符的圖像補丁d_ b1 和 d_b2進行比較。可以看出，圖像補丁看起來非常相似，並且會導致模棱兩可，因此不可靠。通過計算最佳匹配與次佳匹配之間的SSD比值，可以過濾掉這些較弱的候選對象。

在實踐中，已證明閾值0.8可以在TP和FP之間提供良好的平衡。在原始SIFT中檢查的圖像序列中，使用此設置可以消除90％的錯誤匹配，而丟失少於5％的正確匹配。注意，只有KNN能設置閾值0.8。NN只會提供一個最佳匹配。

以下是匹配的執行代碼：

void matchDescriptors(std::vector<cv::KeyPoint> &kPtsSource, std::vector<cv::KeyPoint> &kPtsRef, cv::Mat &descSource,cv::Mat &descRef,std::vector<cv::DMatch> &matches, std::string descriptorclass, std::string matcherType,std::string selectorType) {
    // configure matcher
    bool crossCheck = false;
    cv::Ptr<cv::DescriptorMatcher> matcher;
    int normType;
 
    if (matcherType.compare("MAT_BF") == 0) {
        int normType = descriptorclass.compare("DES_BINARY") == 0 ? cv::NORM_HAMMING : cv::NORM_L2;
        matcher = cv::BFMatcher::create(normType, crossCheck);
 
    } else if (matcherType.compare("MAT_FLANN") == 0) {
        // OpenCV bug workaround : convert binary descriptors to floating point due to a bug in current OpenCV implementation
        if (descSource.type() !=CV_32F) {
            descSource.convertTo(descSource, CV_32F);
            // descRef.convertTo(descRef, CV_32F);
        }
        if (descRef.type() !=CV_32F) {
            descRef.convertTo(descRef, CV_32F);
        }
        matcher = cv::DescriptorMatcher::create(cv::DescriptorMatcher::FLANNBASED);
    }
 
    // perform matching task
    if (selectorType.compare("SEL_NN") == 0) { // nearest neighbor (best match)
        matcher->match(descSource, descRef, matches); 
        // Finds the best match for each descriptor in desc1
    } else if (selectorType.compare("SEL_KNN") == 0) { // k nearest neighbors (k=2)
        vector<vector<cv::DMatch>> knn_matches;
        matcher->knnMatch(descSource, descRef, knn_matches, 2);
        //-- Filter matches using the Lowe's ratio test
        double minDescDistRatio = 0.8;
        for (auto it = knn_matches.begin(); it != knn_matches.end(); ++it) {
            if ((*it)[0].distance < minDescDistRatio * (*it)[1].distance) {
                matches.push_back((*it)[0]);
            }
        }
    } 
}

Evaluating Matching Performance

目前特徵提取與匹配存在大量的檢測器和描述符類型，爲了解決的問題，必須基於諸如關鍵點的準確性或匹配對的數量之類的要求來選擇合適的算法對。下面，概述了最常用的措施。

真陽性率( True Positive Rate-TPR ) 是已經匹配的正確關鍵點 ( true positives - TP ) 和所有潛在匹配的總和之間的比值，包括那些被檢測器/描述符（ false negatives - FN ）錯過了的。完美匹配器的TPR爲1.0，因爲不會有錯誤匹配。TPR也稱爲召回( recall )，可用於量化實際發現了多少個可能的正確匹配。

假陽性率 ( False Positive Rate-FPR ) 是已經匹配 錯誤的關鍵點(f_alse positives - FP_) 和所有應該不被匹配的特徵點之間的比值。完美匹配器的FPR爲0.0。FPR也稱爲 false alarm rate ，它描述檢測器/描述符選擇錯誤的關鍵點對的可能性。

Matcher Precision是正確匹配的關鍵點(TP)的數量除以所有匹配的數量。此度量也稱爲 inlier ratio 。

很多人對於TP, FP, FN以及 TN的理解經常會產生偏差，尤其是FN和TN。下圖是它們各自的定義:

在這裏我們需要介紹ROC的定義。

ROC曲線是一個圖形化的圖表，它顯示了一個檢測器 / 描述符如何很好地區分真假匹配，因爲它的區分閾值是不同的。ROC 可以直觀地比較不同的檢測器 / 描述符，併爲每個檢測器選擇一個合適的鑑別閾值。

下圖顯示瞭如何通過更改SSD的鑑別閾值，根據正陽性和假陽性的分佈構造ROC。理想的檢測器/描述符的TPR爲1.0，而FPR同時接近0.0。

在下圖中，顯示了兩個好的和不好的檢測器/描述符的示例。在第一個示例中，無法安全區分TP和FP，因爲兩條曲線都匹配，並且辨別閾值的更改將以相同的方式影響它們。在第二個示例中，TP和FP曲線沒有明顯重疊，因此可以選擇合適的鑑別器閾值。

在該圖中，您可以看到不同描述符（例如，SIFT，BRISK和其他幾個描述符）的ROC曲線，並在視覺上進行比較。請注意，這些結果僅對實際用於比較的圖像序列有效-對於其他圖像集（例如，交通場景），結果可能會有很大差異。

Conclusion

2D_Feature_Tracking 項目的目的在於使用檢測器和描述符的所有可能組合，爲所有10張圖像計算只在前方車輛範圍內的關鍵點數量，檢測時間，描述時間，匹配時間以及匹配的關鍵點數量。在匹配步驟中，使用BF方法及KNN選擇器並將描述符距離比設置爲0.8。

以下是結果：

不同檢測器的平均檢測時間及檢測出的關鍵點數目

不同檢測器和描述符組合的描述時間

不同檢測器和描述符組合的匹配點數目(控制匹配算法爲不變量)

不同檢測器和描述符組合的總運行時間

從上表中的第一印象可以可以看出：

通過考慮所有這些變化，我可以說檢測器/描述符的前三個組合是:

FAST + BRIEF (Higher speed and relative good accuracy)
BRISK + BRIEF (Higher accuracy)
FAST + ORB (relatively good speed and accuracy)

以上結論是基於實際測試比較表面數據得到的結論，你們也可以自己嘗試修改我代碼庫中的檢測器和描述符組合，看看結果有什麼不同。

最後引用Shaharyar Ahmed Khan Tareen在其比較不同檢測器和描述器組合性能的論文A Comparative Analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK中的結論：

SIFT，SURF和BRISK被認爲是大多數尺度不變特徵檢測器（基於可重複性），它們在廣泛的尺度尺度變化中不受影響。ORB具有最小的尺度不變性。ORB（1000），BRISK（1000）和AKAZE比其他旋轉不變性更高。與其他相比，ORB和BRISK通常對仿射更改更加不變。與其餘圖像相比，SIFT，KAZE，AKAZE和BRISK具有更高的圖像旋轉精度。儘管ORB和BRISK是可以檢測大量特徵的最有效算法，但如此大量特徵的匹配時間會延長總圖像匹配時間。相反，ORB（1000）和BRISK（1000）執行最快的圖像匹配，但其準確性受到損害。對於所有類型的幾何變換，SIFT和BRISK的總體精度最高，SIFT被認爲是最精確的算法。

定量比較表明，特徵檢測描述器檢測大量特徵的能力的一般順序爲：

ORB>BRISK>SURF>SIFT>AKAZE>KAZE

每個特徵點的特徵檢測描述器的計算效率順序爲：

ORB>ORB (1000) >BRISK>BRISK (1000) >SURF (64D)>SURF (128D)>AKAZE>SIFT>KAZE

每個特徵點的有效特徵匹配順序爲：

ORB (1000) >BRISK (1000) >AKAZE>KAZE>SURF (64D)>ORB>BRISK>SIFT>SURF (128D)

特徵檢測描述器的整體圖像匹配速度順序爲：

ORB (1000) >BRISK (1000) >AKAZE>KAZE>SURF (64D)>SIFT>ORB>BRISK>SURF (128D)

備註：不同檢測器的檢測圖像，從中可以看出它們關鍵點鄰域的大小和分佈。

HARRIS