關(guān)鍵點檢測器光度和幾何變化的不變性

特征提取和匹配是許多計算機(jī)視覺應(yīng)用中的一個重要任務(wù)，廣泛運用在運動結(jié)構(gòu)、圖像檢索、目標(biāo)檢測等領(lǐng)域。每個計算機(jī)視覺初學(xué)者最先了解的特征檢測器幾乎都是1988年發(fā)布的HARRIS。在之后的幾十年時間內(nèi)各種各樣的特征檢測器/描述符如雨后春筍般出現(xiàn)，特征檢測的精度與速度都得到了提高。

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

特征(Feature)

特征是與解決某個應(yīng)用程序相關(guān)的計算任務(wù)有關(guān)的一條信息。特征可能是圖像中的特定結(jié)構(gòu)，例如點，邊緣或?qū)ο?。特征也可能是?yīng)用于圖像的一般鄰域操作或特征檢測的結(jié)果。這些功能可以分為兩大類： 1、圖片中特定位置的特征，如山峰、建筑角落、門口或有趣形狀的雪塊。這種局部化的特征通常被稱為關(guān)鍵點特征(或者甚至是角點) ，它們通常以點位置周圍出現(xiàn)的像素塊來描述，這個像素塊往往被稱作圖像補(bǔ)丁(Image patch)。 2、可以根據(jù)其方向和局部外觀（邊緣輪廓）進(jìn)行匹配的特征稱為邊緣，它們也可以很好地指示圖像序列中的對象邊界和遮擋事件。特征點

邊緣

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

1、檢測(detection)：識別感興趣點 2、描述(description): 描述每個特征點周圍的局部外觀，這種描述在光照、平移、尺度和平面內(nèi)旋轉(zhuǎn)的變化下是(理想的)不變的。我們通常會為每個特征點提供一個描述符向量。 3、匹配(mataching): 通過比較圖像中的描述符來識別相似的特征。對于兩幅圖像，我們可以得到一組對(Xi，Yi)->(Xi’ ，Yi’) ，其中(Xi，Yi)是一幅圖像的特征，(Xi’ ，Yi’)是另一幅圖像的特征.

Detector

關(guān)鍵點/興趣點(Key point/ Interest point)

關(guān)鍵點也稱興趣點，是紋理中表達(dá)的點。關(guān)鍵點往往是物體邊界方向突然改變的點或兩個或多個邊緣段之間的交點。它在圖像空間中具有明確的位置或很好地定位。即使圖像域的局部或全局存在如光照和亮度變化等的擾動，關(guān)鍵點仍然是穩(wěn)定，可以被重復(fù)可靠地計算出。除此之外它應(yīng)該提供有效的檢測。 關(guān)鍵點的計算方法有兩種: 1、基于圖像的亮度（通常通過圖像導(dǎo)數(shù)）。 2、基于邊界提?。ㄍǔＭㄟ^邊緣檢測和曲率分析）。

關(guān)鍵點檢測器光度和幾何變化的不變性

在OPENCV庫，我們可以選擇很多特征檢測器，特征檢測器的選擇取決于將要檢測的關(guān)鍵點的類型以及圖像的屬性，需要考慮相應(yīng)檢測器在光度和幾何變換方面的魯棒性。 選擇合適的關(guān)鍵點檢測器時，我們需要考慮四種基本轉(zhuǎn)換類型：1、旋轉(zhuǎn)變換

2、 尺度變換

3、 強(qiáng)度變換

4、仿射變換

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

傳統(tǒng)的HARRIS傳感器在旋轉(zhuǎn)和加性強(qiáng)度偏移情況下具有較強(qiáng)的魯棒性，但對尺度變化、乘性強(qiáng)度偏移(即對比度變化)和仿射變換敏感。自動尺度選擇為了在理想尺度上檢測關(guān)鍵點，我們必須知道(或找到)它們在圖像中的各自維度，并適應(yīng)本節(jié)前面介紹的高斯窗口 w (x，y) 的大小。如果關(guān)鍵點尺度是未知的或如果關(guān)鍵點與存在于不同的大小圖像中，檢測必須在多個尺度級連續(xù)執(zhí)行。

基于相鄰層之間的標(biāo)準(zhǔn)差增量，同一個關(guān)鍵點可能被多次檢測到。這就提出了選擇最能代表關(guān)鍵點的“正確”尺度的問題。1998年Tony Lindeberg 發(fā)表了一種“自動選擇比例的特征提取(Feature detection with automatic scale selection)”的方法。它提出了一個函數(shù) f (x，y，scale) ，該函數(shù)可以用來選擇在尺度上 FF 有穩(wěn)定最大值的關(guān)鍵點。Ff 最大化的尺度被稱為各關(guān)鍵點的“特征尺度”。 如在下圖中顯示了這樣一個函數(shù) FF，它經(jīng)過了幾個尺度級別的評估，在第二張圖中顯示了一個清晰的最大值，可以看作是圓形區(qū)域內(nèi)圖像內(nèi)容的特征尺度。

一個好的檢測器能夠根據(jù)局部鄰域的結(jié)構(gòu)特性自動選擇關(guān)鍵點的特征尺度?，F(xiàn)代關(guān)鍵點探測器通常具有這種能力，因此對圖像尺度的變化具有很強(qiáng)的魯棒性。

常見關(guān)鍵點檢測器

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

經(jīng)典關(guān)鍵點檢測器

經(jīng)典關(guān)鍵點檢測器的目的是為了最大化檢測精度，復(fù)雜度一般不是首要考慮因素。

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

現(xiàn)代關(guān)鍵點檢測器

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

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

基于梯度與二進(jìn)制的描述符

由于我們的任務(wù)是在圖像序列中找到對應(yīng)的關(guān)鍵點，因此我們需要一種基于相似性度量將關(guān)鍵點彼此可靠地分配的方法。很多文獻(xiàn)中已經(jīng)提出了各種各樣的相似性度量(稱為Descriptor)，并且在很多作者已經(jīng)同時發(fā)布了一種用于關(guān)鍵點檢測的新方法以及針對其關(guān)鍵點類型進(jìn)行了優(yōu)化的相似性度量。也就是說已經(jīng)封裝好的OPENCV關(guān)鍵點檢測器函數(shù)大部分同樣可以用來生成關(guān)鍵點描述符。 區(qū)別在于： 關(guān)鍵點檢測器是一種根據(jù)函數(shù)的局部最大值從圖像中選擇點的算法，例如我們在HARRIS檢測器中看到的“角度”度量。 關(guān)鍵點描述符是用于描述關(guān)鍵點周圍的圖像補(bǔ)丁值的向量。描述方法有比較原始像素值的方法也有更復(fù)雜的方法，如梯度方向的直方圖。 關(guān)鍵點檢測器一般是從一個幀圖片中尋找到特征點。而描述符幫助我們在“關(guān)鍵點匹配”步驟中將不同圖像中的相似關(guān)鍵點彼此分配。如下圖所示，一個幀中的一組關(guān)鍵點被分配給另一幀中的關(guān)鍵點，以使它們各自描述符的相似性最大化，并且這些關(guān)鍵點代表圖像中的同一對象。除了最大化相似性之外，好的描述符還應(yīng)該能夠最大程度地減少不匹配的次數(shù)，即避免將彼此不對應(yīng)于同一對象的關(guān)鍵點分配給彼此。

基于梯度HOG描述符

雖然出現(xiàn)了越來越多快速的檢測器/描述符組合，但是基于定向直方圖(HOG)描述符之一的尺度不變特征轉(zhuǎn)換(SIFT)依然被廣泛運用。HOG的基本思想是通過物體在局部鄰域中的強(qiáng)度梯度分布來描述物體的結(jié)構(gòu)。為此，將圖像劃分為多個單元，在這些單元中計算梯度并將其收集到直方圖中。然后，將所有單元格的直方圖集用作相似性度量，以唯一地標(biāo)識圖像塊或?qū)ο蟆?SIFT/SURF使用HOG作為描述符，既包括關(guān)鍵點檢測器，也包括描述符，功能很強(qiáng)大，但是被專利保護(hù)。SURF是在SIFT的基礎(chǔ)上改進(jìn)，不僅提高了計算速度，而且更加安全魯棒性，兩者的實現(xiàn)原理很相似。在此我先僅介紹SIFT。SIFT方法遵循五步過程，下面將對此進(jìn)行簡要概述。 首先，使用稱為“拉普拉斯高斯（LoG）”的方法來檢測圖像中的關(guān)鍵點，該方法基于二階強(qiáng)度導(dǎo)數(shù)。LoG應(yīng)用于圖像的各種比例級別，并且傾向于檢測斑點而不是拐角。除了使用唯一的比例級別外，還根據(jù)關(guān)鍵點周圍局部鄰域中的強(qiáng)度梯度為關(guān)鍵點分配方向。 其次，對于每個關(guān)鍵點，其周圍區(qū)域都會通過消除方向而改變，從而確保規(guī)范的方向。此外，該區(qū)域的大小將調(diào)整為16 x 16像素，從而提供了標(biāo)準(zhǔn)化的圖像補(bǔ)丁。

第三，基于強(qiáng)度梯度_Ix_和_Iy_計算歸一化圖像補(bǔ)丁內(nèi)每個像素的方向和大小。 第四，將歸一化的貼片劃分為4 x 4單元的網(wǎng)格。在每個單元內(nèi)，超出幅度閾值的像素的方向收集在由8個bin組成的直方圖中。

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

SIFT檢測器/描述符即使在雜波中和部分遮擋下也能夠可靠地識別物體。尺度，旋轉(zhuǎn)，亮度和對比度的均勻變化是不變的，仿射失真甚至是不變的。 SIFT的缺點是速度低，這使其無法在智能手機(jī)等實時應(yīng)用中使用。HOG系列的其他成員（例如SURF和GLOH）已針對速度進(jìn)行了優(yōu)化。但是，它們?nèi)匀辉谟嬎闵线^于昂貴，因此不應(yīng)在實時應(yīng)用中使用。此外，SIFT和SURF擁有大量專利，因此不能在商業(yè)環(huán)境中自由使用。為了在OpenCV中使用SIFT，必須使用#include ，并且需要安裝OPENCV_contribute包，注意一定要在Cmake選項中開啟 OPENCV_ENABLE_NONFREE。 二進(jìn)制Binary描述符 基于HOG的描述符的問題在于它們基于計算強(qiáng)度梯度，這是非常昂貴的操作。即使已進(jìn)行了一些改進(jìn)（例如SURF），使用了積分圖像，速度提高了，但這些方法仍然不適合處理能力有限的設(shè)備（例如智能手機(jī)）上的實時應(yīng)用程序。二進(jìn)制描述符家族是基于HOG的方法的一種更快（免費）的替代方案，但準(zhǔn)確性和性能稍差。 二進(jìn)制描述符的核心思想是僅僅依賴強(qiáng)度信息(即圖像本身) ，并將關(guān)鍵點周圍的信息編碼為一串二進(jìn)制數(shù)字，當(dāng)搜索相應(yīng)關(guān)鍵點時，這些數(shù)字可以在匹配步驟中非常有效地進(jìn)行比較。也就是說二進(jìn)制描述符將興趣點的信息編碼成一系列數(shù)字，并作為一種數(shù)字“指紋” ，可用于區(qū)分一個特征和另一個特征。目前，最流行的二進(jìn)制描述符是 BRIEF、 BRISK、 ORB、 FREAK 和 KAZE (所有這些都可以在 OpenCV 庫中找到)。

二進(jìn)制描述符

從高層次的角度來看，二進(jìn)制描述符由三個主要部分組成： 1、一種描述樣本點位于關(guān)鍵點附近的位置的采樣模式( sampling pattern )。 2、一種消除了圖像補(bǔ)丁圍繞關(guān)鍵點位置旋轉(zhuǎn)影響的方向補(bǔ)償方法( orientation compensation)。 3、一種樣本對選擇的方法(ample-pair selection)，它產(chǎn)生成對的樣本點，這些樣本點根據(jù)它們的強(qiáng)度值相互比較。如果第一個值大于第二個值，我們就在二進(jìn)制字符串中寫一個“1” ，否則就寫一個“0”。在對采樣模式中的所有點對執(zhí)行此操作之后，將創(chuàng)建一個長的二進(jìn)制鏈(或“ string”)(因此得到描述符類的族名)。BRISK“二進(jìn)制魯棒不變可伸縮關(guān)鍵點”關(guān)鍵點檢測器 / 描述符是二進(jìn)制描述符的代表。在此我先僅介紹BRISIK。 2011年Stefan Leutenegger 提出的BRISK是一個基于FAST的檢測器和一個Binary描述符的組合，這個描述符由通過對每個關(guān)鍵點鄰域進(jìn)行專門采樣而獲得的強(qiáng)度比較創(chuàng)建。 BRISK的采樣模式由多個采樣點（藍(lán)色）組成，其中每個采樣點周圍的同心環(huán)（紅色）表示應(yīng)用高斯平滑的區(qū)域。與某些其他二進(jìn)制描述符（例如ORB或Brief）相反，BRISK采樣模式是固定的。平滑對于避免混疊非常重要（這種效應(yīng)會導(dǎo)致不同信號在采樣時變得難以區(qū)分-或彼此混疊）。

在樣本對選擇期間，BRISK算法會區(qū)分長距離對和短距離對。長距離對（即在樣本圖案上彼此之間具有最小距離的樣本點）用于根據(jù)強(qiáng)度梯度估算圖像補(bǔ)丁的方向，而短距離對用于對已組裝的描述符字符串進(jìn)行強(qiáng)度比較。在數(shù)學(xué)上，這些對表示如下：

首先，我們定義所有可能的采樣點對的集合A。然后，我們從A提取子集L，子集L的歐氏距離大于上閾值。L是用于方向估計的長距離對。最后，我們從A提取歐氏距離低于下閾值的那些對。該集合S包含用于組裝二進(jìn)制描述符串的短距離對。 下圖顯示了短對（左）和長對（右）的采樣模式上的兩種距離對。

從長對中，關(guān)鍵點方向向量G 計算如下：

首先，根據(jù)歸一化的單位矢量計算兩個采樣點之間的梯度強(qiáng)度，歸一化的單位矢量給出兩個點之間的方向，乘以兩個點在各自比例下的強(qiáng)度差。然后在(2)中，關(guān)鍵點方向向量 g 從所有梯度強(qiáng)度的總和中計算出。 基于 g ，我們可以使用采樣模式的方向重新排列短距離配對，從而確保旋轉(zhuǎn)不變性?；谛D(zhuǎn)不變的短距離配對，可以如下構(gòu)建最終的二進(jìn)制描述符：

從g計算出關(guān)鍵點的方位后，我們使用它使短距離配對旋轉(zhuǎn)不變。然后，所有對之間的強(qiáng)度S被比較并用于組裝可用于匹配的二進(jìn)制描述符。

OPENCV Detector/Descriptor implementation

目前存在各種各樣的特征點檢測器/描述符，如 HARRIS, SHI-TOMASI, FAST, BRISK, ORB, AKAZE, SIFT, FREAK, BRIEF。每一種都值得單獨用一篇博客去描述，但是本文的目的是為了給大家一份綜述，因此不詳細(xì)的從原理上分析這些檢測器/描述符。網(wǎng)上有大量描述這些檢測器/描述符的文章，但是我還是建議大家先看OPENCV庫的Tutorial: How to Detect and Track Object With OpenCV. 以下我會介紹各個特征點檢測器/描述符的代碼實現(xiàn)以及參數(shù)詳解, 文章結(jié)尾會基于實際結(jié)果對這些組合進(jìn)行評價。 有些OPENCV函數(shù)可以同時用于檢測器/描述符，但是有的組合會出現(xiàn)問題。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

特征匹配或一般意義上的圖像匹配是圖像配準(zhǔn)、攝像機(jī)標(biāo)定和目標(biāo)識別等計算機(jī)視覺應(yīng)用的一部分，是在同一場景 / 目標(biāo)的兩幅圖像之間建立對應(yīng)關(guān)系的任務(wù)。一種常用的圖像匹配方法是從圖像數(shù)據(jù)中檢測出一組與圖像描述符相關(guān)聯(lián)的興趣點。一旦從兩個或更多的圖像中提取出特征和描述符，下一步就是在這些圖像之間建立一些初步的特征匹配。

一般來說，特征匹配方法的性能取決于基本關(guān)鍵點的性質(zhì)和相關(guān)圖像描述符的選擇。 我們已經(jīng)了解到關(guān)鍵點可以通過將其局部鄰域轉(zhuǎn)換為高維向量來描述，高維向量可以捕獲梯度或強(qiáng)度分布的獨特特征。

描述符之間的距離

特征匹配需要計算兩個描述符之間的距離，這樣它們之間的差異被轉(zhuǎn)換成一個單一的數(shù)字，我們可以用它作為一個簡單的相似性度量。 目前有三種距離度量：

絕對差之和(SAD)-L1-norm

平方差之和(SSD)-L2-norm

漢明距離 (Hamming distance)

SAD和SSD之間的差異在于：首先兩者之間的最短距離是一條直線，給定每個向量的兩個分量，SAD計算長度差之和，這是一維過程。而SSD計算平方和，遵循畢達(dá)哥拉斯定律，在一個矩形三角形中，寬邊平方的總和等于斜邊的平方。因此，就兩個向量之間的幾何距離而言，L2-norm是一種更準(zhǔn)確的度量。注意，相同的原理適用于高維描述符。 而漢明距離對于僅由１和０組成的二進(jìn)制描述符很適合，該距離通過使用XOR函數(shù)計算兩個向量之間的差，如果兩個位相同，則返回零如果兩位不同，則為1。因此，所有XOR操作的總和就是兩個描述符之間的不同位數(shù)。 值得注意的是必須根據(jù)所使用的描述符的類型選擇合適距離度量。

BINARY descriptors :BRISK, BRIEF, ORB, FREAK, and AKAZE-Hamming distance

HOG descriptors : SIFT (and SURF and GLOH, all patented)-L2-norm

尋找匹配對

讓我們假設(shè)在一個圖像中有N個關(guān)鍵點及其關(guān)聯(lián)的描述符，在另一幅圖像中有M個關(guān)鍵點。

蠻力匹配(Brute Force Matching)

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

快速最近鄰(FLANN)

2014年，David Lowe和Marius Muja發(fā)布了"快速最近鄰(fast library for approximate nearestneighbors(FLANN)")。FLANN訓(xùn)練了一種索引結(jié)構(gòu)，用于遍歷使用機(jī)器學(xué)習(xí)概念創(chuàng)建的潛在匹配候選對象。該庫構(gòu)建了非常有效的數(shù)據(jù)結(jié)構(gòu)（KD樹）來搜索匹配對，并避免了窮舉法的窮舉搜索。因此，速度更快，結(jié)果也非常好，但是仍然需要調(diào)試匹配參數(shù)。 BFMatching和FLANN都接受描述符距離閾值T，該距離閾值T用于將匹配項的數(shù)量限制為“好”，并在匹配不對應(yīng)的情況下丟棄匹配項。相應(yīng)的“好”對稱為“正陽性（TP）”，而錯對稱為“假陽性（FP）”。為T選擇合適的值的任務(wù)是允許盡可能多的TP匹配，而應(yīng)盡可能避免FP匹配。根據(jù)圖像內(nèi)容和相應(yīng)的檢測器/描述符組合，必須找到TP和FP之間的權(quán)衡點，以合理地平衡TP和FP之間的比率。下圖顯示了SSD上TP和FP的兩種分布，以說明閾值選擇。

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

選擇匹配對

BFMatching- crossCheck

只要不超過所選閾值T，即使第二圖像中不存在關(guān)鍵點，蠻力匹配也將始終返回與關(guān)鍵點的匹配。這不可避免地導(dǎo)致許多錯誤的匹配。抵消這種情況的一種策略稱為交叉檢查匹配，它通過在兩個方向上應(yīng)用匹配過程并僅保留那些在一個方向上的最佳匹配與在另一個方向上的最佳匹配相同的匹配來工作。交叉檢查方法的步驟為： 1、對于源圖像中的每個描述符，請在參考圖像中找到一個或多個最佳匹配。 2、切換源圖像和參考圖像的順序。 3、重復(fù)步驟1中源圖像和參考圖像之間的匹配過程。 4、選擇其描述符在兩個方向上最匹配的那些關(guān)鍵點對。 盡管交叉檢查匹配會增加處理時間，但通常會消除大量的錯誤匹配，因此，當(dāng)精度優(yōu)于速度時，應(yīng)始終執(zhí)行交叉匹配。交叉匹配一般僅僅用于BFMatching。

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

減少誤報數(shù)量的另一種非常有效的方法是為每個關(guān)鍵點計算最近鄰距離比(nearest neighbor distance ratio)。KNN與NN的區(qū)別在與NN每個特征點只保留一個最好的匹配 (keeping only the best match)，而KNN每個特征點保留k個最佳匹配(keeping the best k matches per keypoint). k一般為2. 主要思想是不要將閾值直接應(yīng)用于SSD。相反，對于源圖像中的每個關(guān)鍵點，兩個(k=2)最佳匹配位于參考圖像中，并計算描述符距離之間的比率。然后，將閾值應(yīng)用于比率，以篩選出模糊匹配。下圖說明了原理。

在該示例中，將具有關(guān)聯(lián)描述符da的圖像補(bǔ)丁與其他兩個具有描述符的圖像補(bǔ)丁d_ b1 和 d_b2進(jìn)行比較 ?？梢钥闯觯瑘D像補(bǔ)丁看起來非常相似，并且會導(dǎo)致模棱兩可，因此不可靠。通過計算最佳匹配與次佳匹配之間的SSD比值，可以過濾掉這些較弱的候選對象。 在實踐中，已證明閾值0.8可以在TP和FP之間提供良好的平衡。在原始SIFT中檢查的圖像序列中，使用此設(shè)置可以消除90％的錯誤匹配，而丟失少于5％的正確匹配。注意，只有KNN能設(shè)置閾值0.8。NN只會提供一個最佳匹配。 以下是匹配的執(zhí)行代碼：

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

目前特征提取與匹配存在大量的檢測器和描述符類型，為了解決的問題，必須基于諸如關(guān)鍵點的準(zhǔn)確性或匹配對的數(shù)量之類的要求來選擇合適的算法對。下面，概述了最常用的措施。真陽性率(True Positive Rate-TPR)是已經(jīng)匹配的正確關(guān)鍵點 (true positives - TP)和所有潛在匹配的總和之間的比值，包括那些被檢測器/描述符（false negatives - FN）錯過了的。完美匹配器的TPR為1.0，因為不會有錯誤匹配。TPR也稱為召回(recall)，可用于量化實際發(fā)現(xiàn)了多少個可能的正確匹配。假陽性率 (False Positive Rate-FPR)是已經(jīng)匹配錯誤的關(guān)鍵點(f_alse positives - FP_)和所有應(yīng)該不被匹配的特征點之間的比值。完美匹配器的FPR為0.0。FPR也稱為 false alarm rate，它描述檢測器/描述符選擇錯誤的關(guān)鍵點對的可能性。Matcher Precision是正確匹配的關(guān)鍵點(TP)的數(shù)量除以所有匹配的數(shù)量。此度量也稱為 inlier ratio。 很多人對于TP, FP, FN以及 TN的理解經(jīng)常會產(chǎn)生偏差，尤其是FN和TN。下圖是它們各自的定義:

在這里我們需要介紹ROC的定義。 ROC曲線是一個圖形化的圖表，它顯示了一個檢測器 / 描述符如何很好地區(qū)分真假匹配，因為它的區(qū)分閾值是不同的。ROC 可以直觀地比較不同的檢測器 / 描述符，并為每個檢測器選擇一個合適的鑒別閾值。 下圖顯示了如何通過更改SSD的鑒別閾值，根據(jù)正陽性和假陽性的分布構(gòu)造ROC。理想的檢測器/描述符的TPR為1.0，而FPR同時接近0.0。

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

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

Conclusion

2D_Feature_Tracking項目的目的在于使用檢測器和描述符的所有可能組合，為所有10張圖像計算只在前方車輛范圍內(nèi)的關(guān)鍵點數(shù)量，檢測時間，描述時間，匹配時間以及匹配的關(guān)鍵點數(shù)量。在匹配步驟中，使用BF方法及KNN選擇器并將描述符距離比設(shè)置為0.8。 以下是結(jié)果： 不同檢測器的平均檢測時間及檢測出的關(guān)鍵點數(shù)目

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

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

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

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

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

FAST + BRIEF (Higher speed and relative good accuracy)

BRISK + BRIEF (Higher accuracy)

FAST + ORB (relatively good speed and accuracy)

以上結(jié)論是基于實際測試比較表面數(shù)據(jù)得到的結(jié)論，你們也可以自己嘗試修改我代碼庫中的檢測器和描述符組合，看看結(jié)果有什么不同。 最后引用Shaharyar Ahmed Khan Tareen在其比較不同檢測器和描述器組合性能的論文A Comparative Analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK中的結(jié)論： SIFT，SURF和BRISK被認(rèn)為是大多數(shù)尺度不變特征檢測器（基于可重復(fù)性），它們在廣泛的尺度尺度變化中不受影響。ORB具有最小的尺度不變性。ORB（1000），BRISK（1000）和AKAZE比其他旋轉(zhuǎn)不變性更高。與其他相比，ORB和BRISK通常對仿射更改更加不變。與其余圖像相比，SIFT，KAZE，AKAZE和BRISK具有更高的圖像旋轉(zhuǎn)精度。盡管ORB和BRISK是可以檢測大量特征的最有效算法，但如此大量特征的匹配時間會延長總圖像匹配時間。相反，ORB（1000）和BRISK（1000）執(zhí)行最快的圖像匹配，但其準(zhǔn)確性受到損害。對于所有類型的幾何變換，SIFT和BRISK的總體精度最高，SIFT被認(rèn)為是最精確的算法。 定量比較表明，特征檢測描述器檢測大量特征的能力的一般順序為： 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) 備注：不同檢測器的檢測圖像，從中可以看出它們關(guān)鍵點鄰域的大小和分布。HARRIS

Shi-Tomasi

FAST

BRISIK

ORB

AKAZE

SIFT

責(zé)任編輯人：CC