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

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

特征(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 ，并且需要安裝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庫的Tutorial: How to Detect and Track Object With OpenCV. 以下我會介紹各個特征點檢測器/描述符的代碼實現以及參數詳解, 文章結尾會基于實際結果對這些組合進行評價。 有些OPENCV函數可以同時用于檢測器/描述符，但是有的組合會出現問題。SIFTDetector/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::create(nfeatures, nOctaveLayers, contrastThreshold, edgeThreshold, sigma);HARRISDetector

// Detector parametersint blockSize = 2; // for every pixel, a blockSize × blockSize neighborhood is consideredint apertureSize = 3; // aperture parameter for Sobel operator (must be odd)int minResponse = 100; // minimum value for a corner in the 8bit scaled response matrixdouble k = 0.04; // Harris parameter (see equation for details)// Detect Harris corners and normalize outputcv::Mat dst, dst_norm, dst_norm_scaled;dst = cv::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 keypointsdouble maxOverlap = 0.0; // max. permissible overlap between two features in %, used during non-maxima suppressionfor (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(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::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 rowsSHI-TOMASIDetector

int blockSize = 6; // size of an average block for computing a derivative covariation matrix over each pixel neighborhooddouble 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 keypointsdouble qualityLevel = 0.01; // minimal accepted quality of image cornersdouble k = 0.04;bool useHarris = false;// Apply corner detectionvector corners;cv::goodFeaturesToTrack(img, corners, maxCorners, qualityLevel, minDistance, cv::Mat(), blockSize, useHarris, k); // add corners to result vectorfor (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);}BRISIKDetector/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::create(threshold, octaves, patternScale);FREAKDetector/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 &selectedPairs = std::vector(); // (Optional) user defined selected pairs indexes,xxx=cv::create(orientationNormalized, scaleNormalized, patternScale, nOctaves,selectedPairs);FASTDetector/Descriptor

int threshold = 30;// Difference between intensity of the central pixel and pixels of a circle around this pixelbool nonmaxSuppression = true;// perform non-maxima suppression on keypointscv::DetectorType type = cv::TYPE_9_16;// TYPE_9_16, TYPE_7_12, TYPE_5_8xxx=cv::create(threshold, nonmaxSuppression, type);ORBDetector/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::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::create(nfeatures, scaleFactor, nlevels, edgeThreshold, firstLevel, WTA_K, scoreType,patchSize, fastThreshold);AKAZEDetector/Descriptor KAZE/AKAZE descriptors will only work with KAZE/AKAZE detectors.

auto descriptor_type = cv::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 sizeint descriptor_channels = 3;// Number of channels in the descriptor (1, 2, 3)float threshold = 0.001f;// Detector response threshold to accept pointint nOctaves = 4;// Maximum octave evolution of the imageint nOctaveLayers = 4;// Default number of sublevels per scale levelauto diffusivity = cv::DIFF_PM_G2;// Diffusivity type. DIFF_PM_G1, DIFF_PM_G2, DIFF_WEICKERT or DIFF_CHARBONNIERxxx=cv::create(descriptor_type, descriptor_size, descriptor_channels, threshold, nOctaves,nOctaveLayers, diffusivity);BRIEFDetector/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::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 &kPtsSource, std::vector &kPtsRef, cv::Mat &descSource,cv::Mat &descRef,std::vector &matches, std::string descriptorclass, std::string matcherType,std::string selectorType) { // configure matcher bool crossCheck = false; cv::Ptr matcher; int normType; if (matcherType.compare("MAT_BF") == 0) { int normType = descriptorclass.compare("DES_BINARY") == 0 ? cv::NORM_HAMMING : cv::NORM_L2; matcher = cv::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::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> 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

Shi-Tomasi

FAST

BRISIK

ORB

AKAZE

SIFT

責任編輯人：CC