4.3.10 FREAK算法
和BRIEF算法一樣，F(xiàn)REAK算法只實(shí)現(xiàn)了描述符提取部分，不包含關(guān)鍵點(diǎn)檢測(cè)器。該算法是作為BRIEF、BRISK和ORB算法的改進(jìn)版本被提出的，另外FREAK描述符是一個(gè)受生物啟發(fā)的描述符。它的計(jì)算方式和BRIEF描述符類似，主要的區(qū)別是它計(jì)算了用于二值比較的面積。第二個(gè)細(xì)微的區(qū)別是FREAK算法并不使用均勻平滑圖像周圍的像素進(jìn)行比較，相反用于比較的像素點(diǎn)分別都對(duì)應(yīng)了不同大小的積分區(qū)域，離描述符中心越遠(yuǎn)的點(diǎn)對(duì)應(yīng)的積分區(qū)域越大。FREAK算法通過(guò)這種方式模擬人的視覺(jué)系統(tǒng)特征，也因此得名Fast Retinal Keypoint。
FREAK算法計(jì)算關(guān)鍵點(diǎn)描述符的原理示意圖如下，其中直線連接的是可能的測(cè)試定點(diǎn)對(duì)，圓圈表示的是每個(gè)頂點(diǎn)關(guān)聯(lián)的接受域(Receptive Field)，接受域的面積隨著其關(guān)聯(lián)頂點(diǎn)距離中心距離的增大而增大。
為了理解FREAK描述符的計(jì)算過(guò)程，回憶一下前文講到的BRIEF描述符，但是這次重一個(gè)稍微不同的角度。BRIEF從關(guān)鍵點(diǎn)附近選擇了大量的像素對(duì)進(jìn)行比較，并且為了提高對(duì)噪聲的抗性，首先會(huì)對(duì)原圖應(yīng)用高斯模糊濾鏡。在FREAK算法中，用于比較的像素其強(qiáng)度值都可以看作是在原圖中該點(diǎn)附近像素強(qiáng)度的高斯加權(quán)和，這兩種方式在數(shù)學(xué)上是完全等價(jià)的。但是在上圖中的這種方式引入了待比較像素的接受域概念，并且考慮了視網(wǎng)膜上神經(jīng)細(xì)胞和使其發(fā)生響應(yīng)的感光器集合之間的關(guān)系。在標(biāo)準(zhǔn)的結(jié)構(gòu)中，BRIEF算法包含43個(gè)接收域。
和ORB描述符一樣，F(xiàn)REAK的作者使用了一種學(xué)習(xí)技術(shù)組織這些接受域中可能的測(cè)試對(duì)，并按照效果遞減排序。通過(guò)這種方式具有更高辨識(shí)度的測(cè)試對(duì)(通過(guò)較大特征訓(xùn)練集得出)相對(duì)于更低辨識(shí)度的測(cè)試對(duì)具有更高的優(yōu)先級(jí)。一旦這個(gè)順序被確定，只有當(dāng)測(cè)試對(duì)相比于具有更高獨(dú)立實(shí)用性的競(jìng)爭(zhēng)者具有更強(qiáng)的去相關(guān)性(Decorrelation)時(shí)才會(huì)被保留。在應(yīng)用中，對(duì)于幾十個(gè)不同大小的接受域和幾千個(gè)可能的測(cè)試對(duì)，只有最有用的512個(gè)測(cè)試對(duì)才有保留的價(jià)值。
FERAK算法將這512個(gè)測(cè)試對(duì)分為4個(gè)集合，每個(gè)集合包含128個(gè)測(cè)試對(duì)。根據(jù)經(jīng)驗(yàn)可以觀察到每個(gè)集合連續(xù)包含了更多的里中心更近的面積相對(duì)較小的接受域，但是最主要的具有辨識(shí)度的測(cè)試對(duì)都是兩個(gè)較大面積接受域?qū)?yīng)樣本之間的比較。因此可以先只處理這些覆蓋更大面積接受域的主要測(cè)試對(duì)，如果足夠相似，則繼續(xù)處理其他的測(cè)試對(duì)從而優(yōu)化匹配。每組128個(gè)測(cè)試對(duì)的結(jié)果只需要一次異或(XOR)操作(和位求和)即可完成比較，即通過(guò)一個(gè)16字節(jié)的值。這個(gè)值很重要，因?yàn)楹芏喱F(xiàn)代的處理器都可以在一個(gè)周期內(nèi)完成這樣的比較，因此FREAK描述符在比較時(shí)是十分高效的。
相關(guān)接口
如前文所講FREAK算法相關(guān)類只實(shí)現(xiàn)了描述符提取相關(guān)接口，其定義如下。
class FREAK : public Features2D {
public:
// 實(shí)例創(chuàng)建方法
// orientationNormalized：是否對(duì)其特征方向，使計(jì)算的描述符具有旋轉(zhuǎn)不變性
// scaleNormalized：是否根據(jù)關(guān)鍵點(diǎn)大小進(jìn)行標(biāo)準(zhǔn)化處理，使計(jì)算的描述符具有縮放不變性
// patternScale：用于控制接受域縮放，下文介紹，通常使用默認(rèn)值
// nOctaves：關(guān)鍵點(diǎn)覆蓋的層數(shù)，下文介紹，通常使用默認(rèn)值
// selectedPairs：使用的測(cè)試對(duì)在算法內(nèi)部查詢表內(nèi)的索引，通常不需要使用該參數(shù)
static Ptr<FREAK> create(bool orientationNormalized = true, bool scaleNormalized = true,
float patternScale = 22.0f, int nOctaves = 4,
const vector<int>& selectedPairs = vector<int>());
// 描述符的字節(jié)長(zhǎng)度
virtual int descriptorSize() const;
// 描述符的類型
virtual int descriptorType() const; // returns the descriptor type
...
};
通常情況下構(gòu)建該類實(shí)例的時(shí)候使用默認(rèn)的參數(shù)值都能夠取得很好的結(jié)果。在FREAK算法的論文中，計(jì)算描述符時(shí)使用的方向和采樣區(qū)域大小都是相同的，在這種情況下其不具備旋轉(zhuǎn)一致性和縮放一致性。在OpenCV的實(shí)現(xiàn)中，擴(kuò)展了該算法，通過(guò)一些額外的計(jì)算來(lái)確定關(guān)鍵點(diǎn)的特征方向和大小，從而實(shí)現(xiàn)旋轉(zhuǎn)一致性(作為交換會(huì)降低描述符的辨識(shí)度)和縮放一致性。通過(guò)參數(shù)orientationNormalized和scaleNormalized可以分別開(kāi)啟和關(guān)閉這兩個(gè)選項(xiàng)。
參數(shù)patternScale用于縮放所有的接受域，通常不需要改變默認(rèn)值。在計(jì)算FREAK描述符時(shí)會(huì)生成一個(gè)包含所有必要信息的查詢表，這些查詢表包含不同尺度下的信息。屬性patternScale和nOctaves可以控制查詢表的覆蓋范圍，也就是這些接受域的大小?？梢酝ㄟ^(guò)如下公式計(jì)算出精確的刻度。
上式中nbScales是尺度的總數(shù)量，在當(dāng)前的實(shí)現(xiàn)中為64，隨著屬性nOctaves的增加或減少，兩個(gè)不同尺度的差值也隨之增加或減少。如果你對(duì)于nOctaves屬性的命名感到陌生，回想一下在累Cv::KeyPoint中有一個(gè)octave屬性，表示關(guān)鍵點(diǎn)被找到的尺度層索引，而這里的nOctaves就是指的在計(jì)算描述符時(shí)，使用的不同尺度數(shù)量。
參數(shù)selectedPairs是為那些該領(lǐng)域內(nèi)真正的專家預(yù)留的，他可以允許你自定義構(gòu)建描述符時(shí)使用的測(cè)試對(duì)。使用該參數(shù)時(shí)傳入的向量長(zhǎng)度必須等于512，其中的每個(gè)元素為算法內(nèi)部的一個(gè)包含所有可能的由接受域構(gòu)成的測(cè)試對(duì)查詢表的索引，其索引取值為0到902，對(duì)應(yīng)的接受域索引對(duì)從(1, 0)、(2, 0)、(2, 1)增長(zhǎng)到(42, 41)。這算法內(nèi)部通過(guò)一個(gè)嵌套循環(huán)來(lái)構(gòu)建所有的測(cè)試對(duì)索引，外層i循環(huán)的取值為[1, 43)，內(nèi)層j循環(huán)的取值為[0, j)，從而構(gòu)建出所有的測(cè)試對(duì)索引pair[k] = (i, j)。然而你可能不愿意直接使用這些索引，而是使用OpenCV提供的函數(shù)cv::FREAK::selectPairs()來(lái)構(gòu)建這個(gè)索引向量。大部分用戶并不需要使用該參數(shù)，當(dāng)你在閱讀完FREAK論文后，如果認(rèn)為需要重復(fù)作者使用的學(xué)習(xí)過(guò)程從而提升這些描述符在你自己的數(shù)據(jù)集上的質(zhì)量時(shí)可以使用該參數(shù)。
4.3.11 稠密網(wǎng)格法
稠密網(wǎng)格法實(shí)際上不是一個(gè)關(guān)鍵點(diǎn)檢測(cè)器，而是一個(gè)通過(guò)網(wǎng)格化圖像生成關(guān)鍵點(diǎn)的算法。同樣的該算法不包含描述符計(jì)算部分，當(dāng)你得到生成的關(guān)鍵點(diǎn)后需要使用其他算法計(jì)算描述符。一個(gè)稠密網(wǎng)格算法生成的關(guān)鍵點(diǎn)示意圖如下，為了方便演示相關(guān)的參數(shù)中網(wǎng)格密度數(shù)量設(shè)置為3，第一層網(wǎng)格中關(guān)鍵點(diǎn)大小設(shè)置為50，不同層網(wǎng)格間關(guān)鍵點(diǎn)大小縮放系數(shù)為2。
稠密網(wǎng)格法相關(guān)類定義如下，如前文所講該算法不包含描述符計(jì)算部分，因此該類未實(shí)現(xiàn)相關(guān)接口。
class cv::DenseFeatureDetector : public cv::FeatureDetector {
public:
// 構(gòu)造函數(shù)
// initFeatureScale：初始層網(wǎng)格中關(guān)鍵點(diǎn)的大小
// featureScaleLevels：網(wǎng)格的層數(shù)
// featureScaleMul：不同網(wǎng)格層之間關(guān)鍵點(diǎn)的大小縮放系數(shù)
// 第一層后的每一層網(wǎng)格中關(guān)鍵點(diǎn)的大小都等于該屬性和前一層關(guān)鍵點(diǎn)大小的乘積
// initXyStep：關(guān)鍵點(diǎn)之間的間距
// initImgBound：免于計(jì)算關(guān)鍵點(diǎn)的圖像邊緣框距離
// varyXyStepWithScale：在不同層之間是否根據(jù)關(guān)鍵點(diǎn)的大小縮放initXyStep作為關(guān)鍵點(diǎn)之間的間距
// varyImgBoundWithScale：在不同層之間是否根據(jù)關(guān)鍵點(diǎn)的大小縮放initImgBound作為免于計(jì)算關(guān)鍵點(diǎn)的圖像邊緣框距離
explicit DenseFeatureDetector(float initFeatureScale = 1.f, int featureScaleLevels = 1,
float featureScaleMul = 0.1f, int initXyStep = 6, int initImgBound = 0,
bool varyXyStepWithScale = true, bool varyImgBoundWithScale = false);
cv::AlgorithmInfo* info() const;
...
};
算法內(nèi)部生成特征點(diǎn)的簡(jiǎn)單示意圖如下，算法會(huì)為原圖構(gòu)建間距不等的多層網(wǎng)格，其中網(wǎng)格的層數(shù)通過(guò)參數(shù)featureScaleLevels控制。網(wǎng)格的間距為對(duì)應(yīng)層的關(guān)鍵點(diǎn)大小和間距，其中首層的關(guān)鍵點(diǎn)大小通過(guò)參數(shù)initFeatureScale控制，其默認(rèn)值為1，通常情況下并不是我們想要的，但是需要注意該值的設(shè)置不僅和圖像自身的屬性相關(guān)，還與你想要使用的描述符生成算法相關(guān)。首層關(guān)鍵點(diǎn)之間的間距由參數(shù)initXyStep控制。參數(shù)featureScaleMul控制了關(guān)鍵點(diǎn)大小和其上一層關(guān)鍵點(diǎn)大小的比例，而參數(shù)varyXyStepWithScale控制關(guān)鍵點(diǎn)之間的間距是否也需要在不同網(wǎng)格層間隨著關(guān)鍵點(diǎn)大小改變而改變。
參數(shù)initImgBound和varyImgBoundWithScale用于確定免于計(jì)算關(guān)鍵點(diǎn)的圖像邊緣框距離，在大多是情況下將它設(shè)置參數(shù)initFeatureScale的值，確保關(guān)鍵點(diǎn)不會(huì)覆蓋到圖像的邊界之外。
4.4 關(guān)鍵點(diǎn)過(guò)濾
很多時(shí)候你都需要精簡(jiǎn)關(guān)鍵點(diǎn)列表，這樣做的原因可能很多，例如關(guān)鍵點(diǎn)太多，或者是想要?jiǎng)h除低質(zhì)量的關(guān)鍵點(diǎn)，或者是想要移除重復(fù)的關(guān)鍵點(diǎn)，又或者是需要移除位于指定區(qū)域外的所有關(guān)鍵點(diǎn)。OpenCV提供一個(gè)關(guān)鍵點(diǎn)過(guò)濾器類和一系列類方法來(lái)完成這些任務(wù)。在前文講到的很多關(guān)鍵點(diǎn)檢測(cè)器內(nèi)部都隱式調(diào)用了相關(guān)函數(shù)，但是有時(shí)可能你也需要直接使用它們。該類的部分定義如下。
class cv::KeyPointsFilter {
public:
// 移除圖像邊緣框內(nèi)的所有關(guān)鍵點(diǎn)
// keypoints：待處理的關(guān)鍵點(diǎn)
// imageSize：原始圖片的大小
// borderSize：圖像邊框的距離
static void runByImageBorder(
vector<cv::KeyPoint>& keypoints, cv::Size imageSize, int borderSize);
// 移除大小不符合規(guī)則的關(guān)鍵點(diǎn)
// minSize：需要保留的關(guān)鍵點(diǎn)最小尺寸
// maxSize：需要保留的關(guān)鍵點(diǎn)最大尺寸
static void runByKeypointSize(vector<cv::KeyPoint>& keypoints, float minSize, float maxSize = FLT_MAX);
// 根據(jù)蒙版過(guò)濾關(guān)鍵點(diǎn)
// mask：過(guò)濾蒙版，非0值對(duì)應(yīng)的關(guān)鍵點(diǎn)才會(huì)被保留，矩陣應(yīng)和原圖大小相同
static void runByPixelsMask(vector<cv::KeyPoint>& keypoints, const cv::Mat& mask);
// 移除重復(fù)的關(guān)鍵點(diǎn)
static void removeDuplicated(vector<cv::KeyPoint>& keypoints);
// 保留指定數(shù)量的更高質(zhì)量關(guān)鍵點(diǎn)，根據(jù)cv::KeyPoint的屬性Response排序
// npoints：需要保留的關(guān)鍵點(diǎn)數(shù)量
static void retainBest(vector<cv::KeyPoint>& keypoints, int npoints);
}
4.5 關(guān)鍵點(diǎn)匹配
關(guān)鍵點(diǎn)匹配的方法有兩個(gè)，第一個(gè)是暴力匹配(Brute Force Matching)，這種方法比較了兩個(gè)集合中所有可能的組合。第二種方法被稱為FLANN，實(shí)際上是一系列定位距離最近關(guān)鍵點(diǎn)的接口集合。
4.5.1 暴力匹配
暴力匹配相關(guān)類的部分定義如下。
class cv::BFMatcher : public cv::DescriptorMatcher {
public:
BFMatcher(int normType, bool crossCheck=false);
virtual ~BFMatcher() {}
// 是否支持蒙版矩陣，總返回true
// 蒙版矩陣不是應(yīng)用于原圖像，而是用于確定某些描述符之間是否需要比較
virtual bool isMaskSupported() const { return true; }
virtual Ptr<DescriptorMatcher> clone(bool emptyTrainData=false) const;
...
};
暴力匹配取出查詢集中的每個(gè)描述符和匹配器本身持有的描述符集合字典，或者是通過(guò)參數(shù)提供的訓(xùn)練描述符集合中的每個(gè)元素進(jìn)行比較。這種方式你只需要關(guān)注匹配時(shí)度量距離的標(biāo)準(zhǔn)，在構(gòu)造本類實(shí)例的時(shí)候通過(guò)參數(shù)normType指定，其可取值以及對(duì)應(yīng)的公式如下。
暴力匹配的另一個(gè)特性是可以開(kāi)啟交叉檢查(Cross-Checking)，通過(guò)構(gòu)建實(shí)例時(shí)的參數(shù)crossCheck控制。當(dāng)交叉匹配開(kāi)啟后，只有當(dāng)查詢集中第i個(gè)元素query[i]在訓(xùn)練集中的最鄰近元素為train[j]，同時(shí)訓(xùn)練集中第j個(gè)元素train[j]在查詢集中的最鄰近元素是query[i]時(shí)，才判定query[i]和train[j]匹配。這對(duì)于提高匹配的正確性很有用，但是會(huì)消耗額外的計(jì)算成本。
4.5.2 快速近似最近相鄰項(xiàng)法
OpenCV使用類cv::FlannBasedMatcher實(shí)現(xiàn)FLANN(Fast Library for Approximate Nearest Neighbor)的功能，該類實(shí)現(xiàn)了多種在更高維度尋找最近相鄰項(xiàng)的算法，其定義如下。
class cv::FlannBasedMatcher : public cv::DescriptorMatcher {
public:
// 構(gòu)造函數(shù)
// indexParams：算法內(nèi)部索引構(gòu)建策略，下文介紹
// searchParams：類似于終止條件等搜索行為控制參數(shù)，下文介紹
FlannBasedMatcher(const cv::Ptr<cv::flann::IndexParams>& indexParams
= new cv::flann::KDTreeIndexParams(),
const cv::Ptr<cv::flann::SearchParams>& searchParams = new cv::flann::SearchParams());
virtual void add(const vector<Mat>& descriptors);
virtual void clear();
virtual void train();
virtual bool isMaskSupported() const;
virtual void read(const FileNode&);
virtual void write(FileStorage&) const;
virtual cv::Ptr<DescriptorMatcher> clone(bool emptyTrainData = false) const;
...
}
線性索引構(gòu)建策略
當(dāng)參數(shù)indexParams指定為cv::FlannBasedMatcher的實(shí)例時(shí)，表示使用線性索引構(gòu)建策略，使用該策略時(shí)算法內(nèi)部的實(shí)現(xiàn)和暴力匹配法基本相同。它用于基準(zhǔn)比較(Benchmark Comparisons)通常很有用，當(dāng)然也可以用來(lái)驗(yàn)證其他算法得到的結(jié)果是否是令人滿意的。該類的構(gòu)造函數(shù)不包含任何參數(shù)，下面的示例代碼構(gòu)建了這樣一個(gè)使用線性索引構(gòu)建策略的FLANN匹配器。
// 這里只是示例代碼，因此并未考慮內(nèi)存管理問(wèn)題
cv::FlannBasedMatcher matcher(new cv::flann::LinearIndexParams(), new cv::flann::SearchParams());
KD樹(shù)索引構(gòu)建策略
當(dāng)參數(shù)indexParams指定為結(jié)構(gòu)體cv::flann::KDTreeIndexParams的實(shí)例時(shí)，表示使用隨機(jī)KD樹(shù)匹配描述符。算法內(nèi)部會(huì)構(gòu)建很多歌隨機(jī)數(shù)并關(guān)聯(lián)描述符的索引，算法在每個(gè)樹(shù)上向下查詢到最近相鄰項(xiàng)時(shí)，候選項(xiàng)不僅會(huì)與自生的樹(shù)上迄今為止已經(jīng)發(fā)現(xiàn)的最近相鄰項(xiàng)比較，還會(huì)與其他樹(shù)上的候選項(xiàng)進(jìn)行比較。該結(jié)構(gòu)題的定義如下。
struct cv::flann::KDTreeIndexParams : public cv::flann::IndexParams {
// 構(gòu)造方法
// trees：構(gòu)建的KD樹(shù)數(shù)量，通常設(shè)置為16或者更大的值
KDTreeIndexParams(int trees = 4);
};
使用該策略的FLANN匹配器構(gòu)建示例代碼如下。
// 這里只是示例代碼，因此并未考慮內(nèi)存管理問(wèn)題
cv::FlannBasedMatcher matcher(new cv::flann::KDTreeIndexParams(16), new cv::flann::SearchParams());
分層k均值索引構(gòu)建策略
另外一種構(gòu)建索引的策略是分層K均值聚類法(Hierarchical k-means Clustering)，它的優(yōu)勢(shì)是能夠智能應(yīng)用數(shù)據(jù)集中點(diǎn)的密度，該算法在后文機(jī)器學(xué)習(xí)章節(jié)還會(huì)詳細(xì)介紹。該算法是一個(gè)遞歸方法，首先數(shù)據(jù)會(huì)被分為很多個(gè)聚類，然后每個(gè)聚類再分為多個(gè)子聚類，然后遞歸該過(guò)程。這種數(shù)據(jù)結(jié)構(gòu)對(duì)高效匹配很有幫助，其相關(guān)類定義如下。
struct cv::flann::KMeansIndexParams : public cv::flann::IndexParams {
// 構(gòu)造函數(shù)
// branching：分支因子，即樹(shù)每一層的聚類數(shù)量
// iterations：聚類構(gòu)建時(shí)需要的迭代次數(shù)
// 如果設(shè)置為-1，則強(qiáng)制聚類算法一直迭代直至收斂
// centers_init：集群中心初始化策略，下文介紹
// cb_index：控制樹(shù)的搜索邏輯，下文介紹
KMeansIndexParams(int branching = 32, int iterations = 11,
cv::flann::flann_centers_init_t centers_init = cv::flann::CENTERS_RANDOM,
float cb_index = 0.2);
};
在大多數(shù)情況下使用構(gòu)造函數(shù)默認(rèn)的參數(shù)就能夠得到很好的效果。其中參數(shù)centers_init控制了集群中心初始化的策略，傳統(tǒng)上通常使用值cv::flann::CENTERS_RANDOM，但是近年來(lái)實(shí)踐證明在大多數(shù)場(chǎng)景下謹(jǐn)慎選擇該值能夠得到顯著更好的結(jié)果。該參數(shù)的另外兩個(gè)取值分別時(shí)cv::flann::CENTERS_GONXSLES和cv::flann::CENTERS_KMEANSPP，后者逐漸成為了標(biāo)準(zhǔn)選項(xiàng)。參數(shù)cb_index是為那些真正的FLANN專家所預(yù)留的，算法內(nèi)部搜索樹(shù)時(shí)會(huì)使用到該參數(shù)，它可以控制樹(shù)被搜索到方式。通常情況下最好將其設(shè)置為默認(rèn)值或者0，設(shè)置為0時(shí)表示當(dāng)搜索完一個(gè)域時(shí)，應(yīng)該直接繼續(xù)搜索最近的未搜索過(guò)的域。
KD樹(shù)和K均值法聯(lián)合索引構(gòu)建策略
該方法簡(jiǎn)單的結(jié)合了KD樹(shù)和k均值策略，從而嘗試找到它們其中某種方法能夠?qū)崿F(xiàn)的最佳匹配。因?yàn)檫@兩個(gè)方法匹配近似項(xiàng)方法，因此尋找到另外一種方法總有潛在的收益。你可以將這種方法看作是KD樹(shù)法具有多個(gè)隨機(jī)數(shù)的一種邏輯擴(kuò)展。相關(guān)結(jié)構(gòu)體的定義如下。
struct cv::flann::CompositeIndexParams : public cv::flann::IndexParams {
// 構(gòu)造函數(shù)
// trees：構(gòu)建的KD樹(shù)數(shù)量，通常設(shè)置為16或者更大的值
// branching：分支因子，即樹(shù)每一層的聚類數(shù)量
// iterations：聚類構(gòu)建時(shí)需要的迭代次數(shù)
// 如果設(shè)置為-1，則強(qiáng)制聚類算法一直迭代直至收斂
// cb_index：控制樹(shù)的搜索邏輯
// centers_init：集群中心初始化策略
CompositeIndexParams(int trees = 4, int branching = 32,
int iterations = 11, float cb_index = 0.2,
cv::flann::flann_centers_init_t centers_init = cv::flann::CENTERS_RANDOM);
};
局部敏感哈希索引構(gòu)建策略
另外一種區(qū)別很大的索引構(gòu)建方式是局部敏感哈希(Locality-Sensitive Hash, LSH)索引構(gòu)建策略，它使用哈希函數(shù)將類似的對(duì)象映射到同一個(gè)桶中。這些哈希函數(shù)能夠很快生成候選對(duì)象列表，并對(duì)其進(jìn)行評(píng)估和比較。OpenCV中實(shí)現(xiàn)的LSH變體最早由Lv等人提出，在OpenCV中相關(guān)結(jié)構(gòu)體的定義如下。
struct cv::flann::LshIndexParams : public cv::flann::IndexParams {
// 構(gòu)造函數(shù)
// table_number：哈希表數(shù)量
// key_size：哈希鍵的位數(shù)，取值空間通常為[10, 20]
// multi_probe_level：控制如何搜索相鄰存儲(chǔ)區(qū)
// 建議使用默認(rèn)值2，如果設(shè)置為0，算法會(huì)退化成為非多重探測(cè)LSH算法
LshIndexParams(unsigned int table_number, unsigned int key_size,
unsigned int multi_probe_level);
};
需要注意FLANN中的LSH索引構(gòu)建策略僅適用于二進(jìn)制類型秒速符，處理其他類型描述符時(shí)不應(yīng)該使用該策略。
自動(dòng)索引構(gòu)建策略
自動(dòng)索引構(gòu)建策略是讓FLANN算法自動(dòng)尋找最佳的索引策略，顯然這需要一定的時(shí)間成本。使用該策略時(shí)，可以設(shè)置目標(biāo)精度，即返回的最近相鄰項(xiàng)中正確的結(jié)果所占百分比。當(dāng)然所需的精度越高，尋找到合適的索引構(gòu)建策略就會(huì)越困難，生成所有的索引消耗的時(shí)間就會(huì)更長(zhǎng)。相關(guān)結(jié)構(gòu)體的定義如下。
struct cv::flann::AutotunedIndexParams : public cv::flann::IndexParams {
// 構(gòu)造函數(shù)
// target_precision：目標(biāo)精度
// build_weight：構(gòu)造索引的速率權(quán)重
// 如果你不關(guān)心算法構(gòu)建索引的速率，可以使用默認(rèn)值，如果你需要經(jīng)常構(gòu)建該索引，可以將該值設(shè)置更大
// memory_weight：節(jié)約內(nèi)存的權(quán)重
// 如果你不關(guān)心算法消耗的內(nèi)存時(shí)，可以使用默認(rèn)值
// sample_fraction：訓(xùn)練集的比例
// 如果該值過(guò)大，則尋找合適索引構(gòu)建策略的時(shí)間越長(zhǎng)，如果該值過(guò)小，整個(gè)數(shù)據(jù)集合的計(jì)算結(jié)果可能會(huì)比訓(xùn)練集的計(jì)算結(jié)果糟糕很多
// 對(duì)于大的數(shù)據(jù)集，使用默認(rèn)值是一個(gè)不錯(cuò)的選擇
AutotunedIndexParams(float target_precision = 0.9, float build_weight = 0.01,
float memory_weight = 0.0, float sample_fraction = 0.1);
};
FLANN搜索參數(shù)
搜索參數(shù)控制了FLANN算法的一些簡(jiǎn)單行為，相關(guān)的結(jié)構(gòu)體定義如下。
struct cv::flann::SearchParams : public cv::flann::IndexParams {
// 構(gòu)造函數(shù)
// checks：算法內(nèi)部最近相鄰候選項(xiàng)的數(shù)量限制，從這些候選項(xiàng)中會(huì)確定真正的最近相鄰項(xiàng)
// eps：保留屬性，暫時(shí)未使用
// 用于KD樹(shù)的變體KDTreeSingleIndex，控制在特定分支向下查詢節(jié)點(diǎn)時(shí)的終止條件，
// 即查找的點(diǎn)已經(jīng)足夠接近以至于幾乎找不到更近的節(jié)點(diǎn)
// sorted：當(dāng)查詢到多個(gè)項(xiàng)時(shí)，如滿足指定距離內(nèi)的項(xiàng)是否根據(jù)與查詢點(diǎn)的距離升序排序
// 對(duì)于kNN搜索而言，該參數(shù)無(wú)效，返回結(jié)果一定升序排列
SearchParams(int checks = 32, float eps = 0, bool sorted = true);
};
4.6 結(jié)果展示
4.6.1 關(guān)鍵點(diǎn)展示
關(guān)鍵點(diǎn)展示的函數(shù)定義如下。當(dāng)參數(shù)color設(shè)置為cv::Scalar::all(-1)，表示使用不同的顏色繪制關(guān)鍵點(diǎn)。參數(shù)flags定義了關(guān)鍵點(diǎn)的繪制策略，可取值為cv::DrawMatchesFlags::DEFAULT和cv::DrawMatchesFlags::DRAW_RICH_KEYPOINTS。當(dāng)使用前者時(shí)，每個(gè)關(guān)鍵點(diǎn)出會(huì)繪制一個(gè)小圓圈，當(dāng)使用后者時(shí)，如果關(guān)鍵點(diǎn)有大小，則使用該值作為直徑繪制圓，如果有方向還會(huì)繪制特征方向。
// image：用于繪制關(guān)鍵點(diǎn)的圖片
// keypoints：待繪制的關(guān)鍵點(diǎn)
// outImg：繪制完成后的圖片
// color：繪制關(guān)鍵點(diǎn)使用的顏色
// flags：關(guān)鍵點(diǎn)繪制策略
void cv::drawKeypoints(const cv::Mat& image,
const vector<cv::KeyPoint>& keypoints,
cv::Mat& outImg,
const Scalar& color = cv::Scalar::all(-1),
int flags = cv::DrawMatchesFlags::DEFAULT);
4.6.2 匹配結(jié)果展示
給定一組圖片，以及它們關(guān)聯(lián)的關(guān)鍵點(diǎn)，和使用匹配器計(jì)算的由cv::Dmatch實(shí)例組成的匹配項(xiàng)列表，函數(shù)cv::drawMatches會(huì)組合這兩副圖像，并可視化關(guān)鍵點(diǎn)以及匹配結(jié)果。該函數(shù)的一個(gè)使用例子如下圖。圖中使用的關(guān)鍵點(diǎn)和描述符算法未SIFT，計(jì)算匹配項(xiàng)使用了算法FLANN，匹配的關(guān)鍵點(diǎn)使用白色直線相連，未找到匹配項(xiàng)的關(guān)鍵點(diǎn)使用黑色圓圈表示。
函數(shù)cv::drawMatches有兩種變體，包含了兩個(gè)不同參數(shù)，它們的定義如下。
// 包含單個(gè)匹配項(xiàng)列表時(shí)使用的繪圖函數(shù)
// img1：拼接圖像時(shí)的左圖
// keypoints1：img1內(nèi)的關(guān)鍵點(diǎn)
// img2：拼接圖像時(shí)的右圖
// keypoints2：img2內(nèi)的關(guān)鍵點(diǎn)
// matches1to2：匹配項(xiàng)
// outImg：繪制完成的圖像
// matchColor：繪制匹配項(xiàng)時(shí)使用的顏色
// singlePointColor：無(wú)匹配項(xiàng)的關(guān)鍵點(diǎn)繪制顏色
// matchesMask：匹配項(xiàng)繪制的蒙版向量，只有非0值對(duì)應(yīng)的匹配項(xiàng)才會(huì)被繪制
// flags：關(guān)鍵點(diǎn)和匹配項(xiàng)的繪制策略，下文介紹
void cv::drawMatches(const cv::Mat& img1, const vector<cv::KeyPoint>& keypoints1,
const cv::Mat& img2, const vector<cv::KeyPoint>& keypoints2,
const vector<cv::DMatch>& matches1to2,
cv::Mat& outImg,
const cv::Scalar& matchColor = cv::Scalar::all(-1),
const cv::Scalar& singlePointColor = cv::Scalar::all(-1),
const vector<char>& matchesMask = vector<char>(),
int flags = cv::DrawMatchesFlags::DEFAULT)
// 包含多個(gè)匹配項(xiàng)列表時(shí)使用的繪圖函數(shù)
void cv::drawMatches(const cv::Mat& img1, const vector<cv::KeyPoint>& keypoints1,
const cv::Mat& img2, const vector<cv::KeyPoint>& keypoints2,
const vector<vector<cv::DMatch>>& matches1to2,
cv::Mat& outImg,
const cv::Scalar& matchColor = cv::Scalar::all(-1),
const cv::Scalar& singlePointColor = cv::Scalar::all(-1),
const vector<vector<char>>& matchesMask = vector<vector<char>>(),
int flags = cv::DrawMatchesFlags::DEFAULT);
參數(shù)flags的可取值有??DEFAULT、??DRAW_RICH_KEYPOINTS、??DRAW_OVER_OUTIMG、和??NOT_DRAW_SINGLE_POINTS(?? = cv::DrawMatchesFlags::)，其中第一個(gè)選項(xiàng)的值為0，你可以使用邏輯與符合組合這些選項(xiàng)。其中DEFAULT和DRAW_RICH_KEYPOINTS的含義與函數(shù)drawKeypoints中對(duì)應(yīng)項(xiàng)含義相同。當(dāng)參數(shù)flag含有DRAW_OVER_OUTIMG就不會(huì)清除參數(shù)outImg的內(nèi)容，當(dāng)你需要用不同顏色繪制多組匹配項(xiàng)時(shí)，則可以多次調(diào)用函數(shù)drawMatches，并在第一次調(diào)用后都加入該標(biāo)記。NOT_DRAW_SINGLE_POINTS被添加時(shí)，未找到匹配項(xiàng)的關(guān)鍵點(diǎn)將不會(huì)被繪制在輸出圖像中。
5 小結(jié)
在本章的開(kāi)頭介紹了次像素坐標(biāo)和稀疏光流的概念，緊接著又討論了關(guān)鍵點(diǎn)的基本概念，并介紹了一系列OpenCV中包含的關(guān)鍵點(diǎn)檢測(cè)和描述符生成算法，以及OpenCV中對(duì)應(yīng)的接口。然后我們討論了如何高效的匹配關(guān)鍵點(diǎn)和描述符，從而應(yīng)用于目標(biāo)識(shí)別和追蹤應(yīng)用。在本章結(jié)尾介紹了如何在原圖中可視化這些關(guān)鍵點(diǎn)和匹配項(xiàng)，更多的關(guān)鍵點(diǎn)檢測(cè)器和描述副類型在本系列文章的后記中xfeatures2d部分會(huì)詳細(xì)列出。
