關(guān)鍵點(diǎn)檢測(cè)、描述以及匹配的背后原理

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

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

Background Knowledge

特征(Feature)

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

邊緣

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

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

Detector

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

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

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

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

2、 尺度變換

3、 強(qiáng)度變換

4、仿射變換

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

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

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

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

常見關(guān)鍵點(diǎn)檢測(cè)器

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

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

經(jīng)典關(guān)鍵點(diǎn)檢測(cè)器的目的是為了最大化檢測(cè)精度，復(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)鍵點(diǎn)檢測(cè)器

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

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

基于梯度HOG描述符

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

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

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

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

二進(jìn)制描述符

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

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

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

從長(zhǎng)對(duì)中，關(guān)鍵點(diǎn)方向向量G 計(jì)算如下：

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

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

OPENCV Detector/Descriptor implementation

目前存在各種各樣的特征點(diǎn)檢測(cè)器/描述符，如 HARRIS, SHI-TOMASI, FAST, BRISK, ORB, AKAZE, SIFT, FREAK, BRIEF。每一種都值得單獨(dú)用一篇博客去描述，但是本文的目的是為了給大家一份綜述，因此不詳細(xì)的從原理上分析這些檢測(cè)器/描述符。網(wǎng)上有大量描述這些檢測(cè)器/描述符的文章，但是我還是建議大家先看OPENCV庫的Tutorial: How to Detect and Track Object With OpenCV. 以下我會(huì)介紹各個(gè)特征點(diǎn)檢測(cè)器/描述符的代碼實(shí)現(xiàn)以及參數(shù)詳解, 文章結(jié)尾會(huì)基于實(shí)際結(jié)果對(duì)這些組合進(jìn)行評(píng)價(jià)。 有些OPENCV函數(shù)可以同時(shí)用于檢測(cè)器/描述符，但是有的組合會(huì)出現(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)識(shí)別等計(jì)算機(jī)視覺應(yīng)用的一部分，是在同一場(chǎng)景 / 目標(biāo)的兩幅圖像之間建立對(duì)應(yīng)關(guān)系的任務(wù)。一種常用的圖像匹配方法是從圖像數(shù)據(jù)中檢測(cè)出一組與圖像描述符相關(guān)聯(lián)的興趣點(diǎn)。一旦從兩個(gè)或更多的圖像中提取出特征和描述符，下一步就是在這些圖像之間建立一些初步的特征匹配。

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

描述符之間的距離

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

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

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

漢明距離 (Hamming distance)

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

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

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

尋找匹配對(duì)

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

蠻力匹配(Brute Force Matching)

尋找對(duì)應(yīng)對(duì)的最明顯方法是將所有特征相互比較，即執(zhí)行N x M比較。對(duì)于第一張圖像中給定的關(guān)鍵點(diǎn)，它將獲取第二張圖像中的每個(gè)關(guān)鍵點(diǎn)并計(jì)算距離。距離最小的關(guān)鍵點(diǎn)將被視為一對(duì)。這種方法稱為“蠻力匹配(Brute Force Matching)”或“最近鄰居匹配(Nearest Neighbor Matching)”。OPENCV中蠻力匹配的輸出是一個(gè)關(guān)鍵點(diǎn)對(duì)的列表，這些關(guān)鍵點(diǎn)對(duì)按其在所選距離函數(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)建的潛在匹配候選對(duì)象。該庫構(gòu)建了非常有效的數(shù)據(jù)結(jié)構(gòu)（KD樹）來搜索匹配對(duì)，并避免了窮舉法的窮舉搜索。因此，速度更快，結(jié)果也非常好，但是仍然需要調(diào)試匹配參數(shù)。 BFMatching和FLANN都接受描述符距離閾值T，該距離閾值T用于將匹配項(xiàng)的數(shù)量限制為“好”，并在匹配不對(duì)應(yīng)的情況下丟棄匹配項(xiàng)。相應(yīng)的“好”對(duì)稱為“正陽性（TP）”，而錯(cuò)對(duì)稱為“假陽性（FP）”。為T選擇合適的值的任務(wù)是允許盡可能多的TP匹配，而應(yīng)盡可能避免FP匹配。根據(jù)圖像內(nèi)容和相應(yīng)的檢測(cè)器/描述符組合，必須找到TP和FP之間的權(quán)衡點(diǎn)，以合理地平衡TP和FP之間的比率。下圖顯示了SSD上TP和FP的兩種分布，以說明閾值選擇。

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

選擇匹配對(duì)

BFMatching- crossCheck

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

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

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

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

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

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

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

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

Conclusion

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

不同檢測(cè)器和描述符組合的描述時(shí)間

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

不同檢測(cè)器和描述符組合的總運(yùn)行時(shí)間

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

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

FAST + BRIEF (Higher speed and relative good accuracy)

BRISK + BRIEF (Higher accuracy)

FAST + ORB (relatively good speed and accuracy)

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

Shi-Tomasi

FAST

BRISIK

ORB

AKAZE

SIFT

引用資料UDACITY A Comparative Analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK Deepanshu Tyagi 如果你想了解整個(gè)圖像特征提取匹配的流程，可以參看我的代碼庫的README文件。 如果有什么疑問，可以隨時(shí)聯(lián)系我的個(gè)人郵箱。Github：https://github.com/williamhyin/SFND_2D_Feature_TrackingEmail：williamhyin@outlook.comLinkedin：https://linkedin.com/in/williamhyin