孫亭+黃鳳蘭+袁夢(mèng)琪+卜凡亮

摘要：本文采用SIFT算法進(jìn)行特征點(diǎn)檢測(cè)，運(yùn)用Kd-tree構(gòu)造數(shù)據(jù)索引空間，采用最近鄰檢測(cè)算法在其中進(jìn)行數(shù)據(jù)的查詢，實(shí)現(xiàn)待匹配圖像特征點(diǎn)和參考圖像特征點(diǎn)的匹配。由于SIFT算法描述的特征點(diǎn)具有旋轉(zhuǎn)不變性、尺度不變性等優(yōu)良特性，借助這些特征點(diǎn)對(duì)，能夠?qū)崿F(xiàn)測(cè)量系統(tǒng)中的立體匹配。本文對(duì)獲取的同一場(chǎng)景的兩幅圖像進(jìn)行處理，用上述方法進(jìn)行立體匹配，實(shí)現(xiàn)了較好的匹配效果，達(dá)到了接近實(shí)時(shí)性的匹配速度。

關(guān)鍵詞：SIFT算法；Kd-tree；最近鄰檢測(cè)；立體匹配

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）15-0199-03

圖像匹配是雙目視覺測(cè)量系統(tǒng)中的關(guān)鍵技術(shù)?；趫D像特征的匹配方法是最常用的匹配方法，該方法首先提取圖像的局部特征（區(qū)域、線、點(diǎn)），然后計(jì)算兩幅圖像特征的相關(guān)性來確定它們之間的最佳匹配，再通過反映兩幅圖像關(guān)系的變換矩陣，將待匹配圖像投影到參考圖像中，實(shí)現(xiàn)兩幅圖像之間的匹配?；趫D像特征的匹配方法研究要從Moravec[1]利用角點(diǎn)檢測(cè)實(shí)現(xiàn)立體匹配開始。Harris角點(diǎn)檢測(cè)在有效地運(yùn)動(dòng)跟蹤方面具有重要的研究?jī)r(jià)值。Schmid[2]和Mohr研究表明不變尺度特征匹配能夠擴(kuò)展應(yīng)用到一般的圖像識(shí)別問題。由于Harris角點(diǎn)描述符對(duì)圖像的尺度比較敏感，用于不同尺度的圖像之間匹配，效果不是很理想。1999年David G.Lowe總結(jié)了已有的基于不變量技術(shù)的特征檢測(cè)方法，提出了一種基于圖像局部特征的描述算子，SIFT特征描述算子[3]。該算子具有多種良好的不變特性，對(duì)圖像的旋轉(zhuǎn)、縮放、尺度空間變換和仿射變換等均保持不變性，此外，該算法將特征檢測(cè)、特征矢量生成、特征匹配搜索等步驟完整的結(jié)合，并進(jìn)行進(jìn)一步優(yōu)化處理，達(dá)到了接近實(shí)時(shí)的運(yùn)算速度，實(shí)現(xiàn)了良好的匹配效果。

本文利用SIFT算法對(duì)圖像中的特征點(diǎn)進(jìn)行檢測(cè)，并利用基于Kd-tree的最近鄰算法進(jìn)行特征點(diǎn)的匹配，最后依賴于已有的特征點(diǎn)匹配對(duì)，實(shí)現(xiàn)雙目視覺立體匹配。

1.2 SIFT特征描述子及特征矢量

SIFT描述子是一種用于特征檢測(cè)的特征描述子，通過量化描述圖像局部特征，客觀地反映特征點(diǎn)附近局部區(qū)域內(nèi)圖像的分布情況。為了實(shí)現(xiàn)圖像的旋轉(zhuǎn)不變性，我們通過圖像的梯度參數(shù)，求取特征點(diǎn)附近局部結(jié)構(gòu)的穩(wěn)定方向。對(duì)于已經(jīng)檢測(cè)到的特征點(diǎn)，特征點(diǎn)尺度值是確定的，我們可以得到最接近該值的高斯圖像：

1.3 圖像特征點(diǎn)匹配

對(duì)捕獲的同一場(chǎng)景兩幅圖像，如果兩個(gè)特征點(diǎn)描述矢量之間相距較近，就認(rèn)為這兩個(gè)特征點(diǎn)對(duì)應(yīng)于三維場(chǎng)景中的同一位置；反之，則處于不同的位置。特征點(diǎn)匹配技術(shù)就是從對(duì)應(yīng)同一場(chǎng)景的兩幅圖像特征點(diǎn)集合中，找到兩兩距離最近的特征點(diǎn)，實(shí)現(xiàn)特征點(diǎn)一對(duì)一匹配。

特征匹配常采用線性掃描法，就是將特征點(diǎn)和查詢點(diǎn)逐一進(jìn)行距離比較，選擇距離最小的點(diǎn)，但是該檢索方法搜索效率比較低。本文采用Kd-tree[5]的數(shù)據(jù)結(jié)構(gòu)，將整個(gè)數(shù)據(jù)空間劃分成小空間，逐級(jí)展開搜索，搜尋最近鄰點(diǎn)。Kd-tree本質(zhì)上就是二叉樹，每個(gè)節(jié)點(diǎn)表述一個(gè)空間范圍。構(gòu)建流程如下：

（1）分析數(shù)據(jù)點(diǎn)數(shù)據(jù)，展開kd-tree；

（2）找到分割超面，確定其垂直方向軸序號(hào)，計(jì)算對(duì)應(yīng)維度上的數(shù)據(jù)方差；

（4）分割數(shù)據(jù)。維數(shù)小于閾值的，其對(duì)應(yīng)的特征點(diǎn)放在右子樹空間；否則放在左子樹空間；

（5）分別展開左子樹、右子樹，重復(fù)上述步驟（2）、（3）、（4），將空間和數(shù)據(jù)集進(jìn)一步細(xì)化，直至空間中只包含一個(gè)特征數(shù)據(jù)點(diǎn)。

在kd-tree中進(jìn)行數(shù)據(jù)的查詢是為了檢索kd-tree數(shù)據(jù)集中與查詢點(diǎn)距離最近的數(shù)據(jù)點(diǎn)。按照二叉樹結(jié)構(gòu)展開搜索，沿著搜索路徑，找到最近鄰的近似點(diǎn)，也就是包含查詢點(diǎn)的葉子節(jié)點(diǎn)。但是這樣找到的葉子節(jié)點(diǎn)不一定就是最近鄰點(diǎn)，最近鄰點(diǎn)肯定距離查詢點(diǎn)更近，也就是說，最近鄰點(diǎn)一定在以查詢點(diǎn)為圓心，通過葉子節(jié)點(diǎn)為半徑的圓域內(nèi)。這就需要我們沿搜索路徑回溯操作，看是否存在某一數(shù)據(jù)點(diǎn)，距離查詢點(diǎn)更近。若存在，就用新查到的數(shù)據(jù)點(diǎn)代替葉子節(jié)點(diǎn)，反之若不存在，則認(rèn)為已經(jīng)找到的葉子節(jié)點(diǎn)就是最近鄰點(diǎn)，從而完成特征點(diǎn)的匹配。

2 立體匹配

立體匹配[6]是指對(duì)參考圖像中的任意像素，在待匹配圖像中找到與之相對(duì)應(yīng)的像素點(diǎn)的過程，即找到空間中任一場(chǎng)景點(diǎn)在兩幅圖像中對(duì)應(yīng)的像素點(diǎn)。這些像素點(diǎn)有可能是已經(jīng)檢測(cè)出的特征點(diǎn)，也有可能只是普通的像素點(diǎn)。由于使用SIFT算法檢測(cè)到的特征點(diǎn)具有多種不變特性，在圖像中處于相對(duì)穩(wěn)定的區(qū)域，我們可以建立待匹配像素點(diǎn)和周圍特征點(diǎn)的關(guān)系，來實(shí)現(xiàn)像素點(diǎn)之間的匹配。

本文在特征匹配的基礎(chǔ)上，研究了普通像素點(diǎn)和特征點(diǎn)之間的關(guān)系，實(shí)現(xiàn)了圖像的立體匹配。算法具體流程如下：

（1）在參考圖像中，從上往下，從左至右對(duì)圖像特征點(diǎn)依次排序，并求取各特征點(diǎn)到參考像素點(diǎn)之間的歐氏距離；

（2）比較求得的歐氏距離，選擇其中距離最小的特征點(diǎn)為最近特征點(diǎn)，如存在距離相同的特征點(diǎn)，選擇序號(hào)最小的特征點(diǎn)為最近特征點(diǎn)；同理，選擇距離次小的特征點(diǎn)為次近特征點(diǎn)；

（3）從匹配好的特征點(diǎn)對(duì)中，找到最近特征點(diǎn)和次近特征點(diǎn)，并從已經(jīng)存在的匹配對(duì)集合中，找到待匹配圖像中與之對(duì)應(yīng)的最近特征點(diǎn)和次近特征點(diǎn)。

（4）在參考圖像中，建立兩個(gè)特征點(diǎn)與參考像素點(diǎn)之間的函數(shù)關(guān)系。運(yùn)用該函數(shù)關(guān)系求出待匹配圖像中對(duì)應(yīng)的像素點(diǎn)。

對(duì)于立體匹配，除了借助特征點(diǎn)匹配對(duì)，立體匹配本身還具有一些約束條件：1）唯一性約束。每個(gè)參考像素點(diǎn)存在且只存在唯一的待匹配像素點(diǎn)與之相匹配；2）順序一致性約束。同一掃描線上的兩個(gè)像素點(diǎn)在參考圖像和待匹配圖像上具有相同位置次序；3）一致性約束。兩幅圖像中，對(duì)于未遮擋的相同場(chǎng)景，對(duì)應(yīng)的像素點(diǎn)具有相同的視差。運(yùn)用立體匹配條件，可以進(jìn)一步優(yōu)化我們已經(jīng)得到的立體匹配點(diǎn)對(duì)，實(shí)現(xiàn)更好的匹配效果。

3 實(shí)驗(yàn)結(jié)果及分析

本文使用的實(shí)驗(yàn)設(shè)備：一個(gè)帶有旋轉(zhuǎn)云臺(tái)的自動(dòng)三腳架（三腳架和云臺(tái)的運(yùn)動(dòng)情況可以進(jìn)行參數(shù)設(shè)置），一臺(tái)85mm微距的尼康攝像機(jī)，一臺(tái)戴爾的臺(tái)式電腦。

將攝像機(jī)安裝在三腳架上，設(shè)置三腳架運(yùn)動(dòng)參數(shù)，使得三腳架只進(jìn)行垂直運(yùn)動(dòng)。用該設(shè)備獲取三腳架運(yùn)動(dòng)前后，對(duì)著的同一場(chǎng)景的兩幅圖像。

應(yīng)用SIFT算法，對(duì)獲取的兩幅圖像進(jìn)行特征點(diǎn)檢測(cè)。圖中黑色的點(diǎn)表示檢測(cè)到的特征點(diǎn)，從圖1可以看出，利用SIFT算法進(jìn)行特征點(diǎn)檢測(cè)，得到的檢測(cè)結(jié)果大多是比較明顯的邊緣點(diǎn)、角點(diǎn)、像素灰度變化比較大的點(diǎn)，這為后續(xù)的特征匹配打下了良好的基礎(chǔ)。

從特征點(diǎn)匹配的實(shí)驗(yàn)結(jié)果來看，檢測(cè)到的特征點(diǎn)都能在目標(biāo)圖像中找到對(duì)應(yīng)的特征點(diǎn)，完成特征點(diǎn)的相互匹配。但是仔細(xì)觀察不難發(fā)現(xiàn)，本實(shí)驗(yàn)中存在錯(cuò)誤的匹配對(duì)。本實(shí)驗(yàn)中一共實(shí)現(xiàn)了151對(duì)特征點(diǎn)的匹配，其中存在3對(duì)錯(cuò)誤的匹配，即誤匹配率為1.98%，實(shí)現(xiàn)了較好的匹配效果。而且匹配運(yùn)算時(shí)間只用了6.763 S，達(dá)到了很好的實(shí)時(shí)性效果。圖中誤匹配點(diǎn)對(duì)主要集中在圖像中部，分析是書柜排布相似、書本上存在個(gè)別效果不明顯的特征點(diǎn)等原因?qū)е碌摹?/p>

在立體匹配上，本文進(jìn)行了多次實(shí)驗(yàn)，選取其中幾組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖所示。其中藍(lán)線表示最近特征點(diǎn)對(duì)和次近特征點(diǎn)對(duì)，紅線表示對(duì)應(yīng)的求得的匹配像素點(diǎn)對(duì)。實(shí)驗(yàn)像素坐標(biāo)如表1所示。

從上述實(shí)驗(yàn)數(shù)據(jù)中可以看出，大部分?jǐn)?shù)據(jù)橫、縱軸差值相當(dāng)，對(duì)比實(shí)驗(yàn)圖像，實(shí)驗(yàn)數(shù)據(jù)是真實(shí)可靠的。進(jìn)行實(shí)驗(yàn)時(shí)，理論上智能三腳架只進(jìn)行垂直升降運(yùn)動(dòng)，由此參考像素點(diǎn)和待匹配像素點(diǎn)的橫坐標(biāo)是相同的，但是在實(shí)際的操作中，由于地面不完全平整、儀器本身?xiàng)l件限制等原因，攝像機(jī)運(yùn)動(dòng)過程中存在一定程度的晃動(dòng)，會(huì)產(chǎn)生一定程度的橫向偏移，使得參考像素點(diǎn)和待匹配像素點(diǎn)的橫軸坐標(biāo)不一致。其次，由于像素點(diǎn)的匹配是依賴于特征點(diǎn)匹配對(duì)的，如果特征點(diǎn)匹配對(duì)是誤匹配，會(huì)直接導(dǎo)致后面的像素點(diǎn)匹配對(duì)發(fā)生錯(cuò)誤，如圖4所示。還有即使特征點(diǎn)匹配對(duì)是正確的，后面建立的幾何函數(shù)的不精準(zhǔn)或是計(jì)算的精確度等原因，也會(huì)影響像素點(diǎn)的匹配。

4 結(jié)語

在刑事案件現(xiàn)場(chǎng)中，一般人造物品比較多，特征都比較明顯。本文利用SIFT算法對(duì)拍攝的現(xiàn)場(chǎng)圖像進(jìn)行特征點(diǎn)檢測(cè) ，能夠快速、有效的實(shí)現(xiàn)特征點(diǎn)的檢測(cè)。在特征匹配的過程中，通過SIFT特征描述子建立特征矢量，對(duì)檢測(cè)到的特征點(diǎn)進(jìn)行詳細(xì)的描述。 構(gòu)造Kd-tree數(shù)據(jù)結(jié)構(gòu)，利用該結(jié)構(gòu)進(jìn)行近鄰檢測(cè)，實(shí)現(xiàn)特征點(diǎn)的匹配，再在此基礎(chǔ)上，完成立體匹配。本文實(shí)現(xiàn)了快速的立體匹配，實(shí)現(xiàn)了較好的匹配效果。但仍然存在不足，有誤匹配的出現(xiàn)，正確的匹配在精度上也有待加強(qiáng)，有待于進(jìn)一步優(yōu)化。

參考文獻(xiàn)：

[1] Moravec H. Rover visual obstacle avoidance[C]. In International Joint Conference on Artificial Intelligence， Vancouver， Canada， 1981， 785-790.

[2] Schmid C. and Mohr R. Local gray-value invariants for image retrieval[J]. IEEE Trans. On Pattern Analysis and Machine Intelligence， 1997， 19（5）：530-534.

[3] Lowe D. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision， 2004， 60（2）：91-110.

[4] 王永明，王貴錦.圖像局部不變性特征與描述[M].北京：國防工業(yè)出版社，2010.4：79-88

[5] 杜振鵬，李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究[J].計(jì)算機(jī)與數(shù)字工程，2012（2）：96-100.

[6] 姜宏志，趙慧潔.基于極線校正的快速相位立體匹配[J].光學(xué)精密工程，2011（10）：2520-2527.