邢藝馨， 田愛(ài)奎， 張立曄， 常春紅， 郝本利

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 山東 淄博 255000)

0 引 言

目前，計(jì)算機(jī)視覺(jué)領(lǐng)域技術(shù)的快速發(fā)展，使得雙目立體視覺(jué)在工業(yè)機(jī)器人、生物醫(yī)學(xué)、虛擬現(xiàn)實(shí)以及軍事等領(lǐng)域應(yīng)用前景廣泛，其圖像匹配精度和速度一直備受關(guān)注。對(duì)此，經(jīng)典算法的提出更是推動(dòng)了該領(lǐng)域的發(fā)展。David G.Lowe 提出的SIFT(Scale Invariant Feature Transform，初度不變特征變換)算法所提取的特征點(diǎn)穩(wěn)定性高，同時(shí)具有尺度不變性和旋轉(zhuǎn)不變性的特點(diǎn)，可獲取更多信息量，但同時(shí)有存在匹配時(shí)間較長(zhǎng)的缺點(diǎn)[1]。隨后，作為SIFT算法的優(yōu)化算法——SURF(Speed Up Robust Feature)被提出，其利用了快速的Hessian矩陣檢測(cè)關(guān)鍵點(diǎn)，缺點(diǎn)是魯棒性降低[2]。2011年，Rublee[3]等對(duì)上述二種算法進(jìn)行研究改進(jìn)，提出了經(jīng)典的ORB(Oriented FAST and Rotated BRIEF)算法，該算法的優(yōu)點(diǎn)是匹配速度快，同時(shí)對(duì)噪聲敏感的缺點(diǎn)也相當(dāng)明顯，匹配精度也因此降低。傳統(tǒng)的ORB算法沒(méi)有充分解決尺度不變性的問(wèn)題，針對(duì)此問(wèn)題，戴雪梅[4]等結(jié)合SURF算法的尺度不變的特征，對(duì)ORB算法進(jìn)行了改進(jìn)，得到一種全新的SURF-ORB(簡(jiǎn)稱SURB)算法，其保留了ORB算法的速度優(yōu)勢(shì)，又有效地避免了ORB算法不具備尺度不變性的缺陷，提高了算法運(yùn)行效率。2020年，文永革[5]等提出了結(jié)合SIFT算法與K-means聚類算法的圖像匹配優(yōu)化算法，提升了圖像特征的算法效率，并且實(shí)現(xiàn)了在同等距離比率下，圖像特征匹配精度的提升。文獻(xiàn)[6]提出了一種大規(guī)模的對(duì)象檢測(cè)系統(tǒng)，用戶可通過(guò)選擇查詢圖像的區(qū)域來(lái)提供查詢對(duì)象。并且大型語(yǔ)料庫(kù)中檢索包含相同對(duì)象的圖像的排序列表在系統(tǒng)中返回，會(huì)出現(xiàn)忽略圖像的語(yǔ)義部分的情況。文獻(xiàn)[7]中，通過(guò)對(duì)局部空間進(jìn)行網(wǎng)格結(jié)構(gòu)均分的方式得到視覺(jué)詞匯表，缺點(diǎn)與文獻(xiàn)[6]相似，問(wèn)題仍未得到解決。文獻(xiàn)[8]提出，通過(guò)比較各興趣點(diǎn)局部澤尼克矩的歐氏距離，來(lái)提取最優(yōu)匹配點(diǎn)后，以興趣點(diǎn)的空間離散度計(jì)算圖像匹配性。文獻(xiàn)[9] 對(duì)K-means聚類算法進(jìn)行改進(jìn)研究，在基于主成分分析的K-means初始聚類中心優(yōu)化算法的基礎(chǔ)上，提出一種全新的基于潛在穩(wěn)定性的K-means最佳聚類數(shù)確定方法，解決了聚類分析的初始聚類中心的選擇和聚類K值的問(wèn)題。文獻(xiàn)[10]中，孫士寶等人在分析了孤立點(diǎn)和噪聲數(shù)據(jù)對(duì) K-means 算法影響的基礎(chǔ)上，提出了一種基于加權(quán)的K-means 算法。文獻(xiàn)[11]中提出了基于半監(jiān)督 K-均值聚類對(duì) K 值進(jìn)行全局尋優(yōu)算法，解決了K-means 算法隨機(jī)選擇初始聚類中心的不足。

綜上所述，本文算法目的是對(duì)ORB算法進(jìn)行改進(jìn)。考慮到K-means算法具有優(yōu)化迭代的特點(diǎn)，雙目視覺(jué)對(duì)尺度不變性要求較低，采用傳統(tǒng)ORB算法與K-means聚類算法相結(jié)合，通過(guò)亞像素插值法提升特征點(diǎn)坐標(biāo)精確度。經(jīng)多次圖像匹配實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證了本文算法對(duì)不同分辨率圖像的匹配精度有較穩(wěn)定的提升，同時(shí)性能也優(yōu)于傳統(tǒng)的圖像匹配算法。

1 ORB算法

作為高效的圖像匹配算法，ORB算法在特征匹配和抑制圖像噪聲兩方面性能都可代替SIFT算法，其算法的速度優(yōu)勢(shì)更適用于實(shí)時(shí)系統(tǒng)中。在傳統(tǒng)ORB 特征檢測(cè)算法中，首先建立特征點(diǎn)的特征描述向量，依據(jù)FAST子檢測(cè)圖像上符合條件的特征點(diǎn)，并根據(jù)灰度質(zhì)心法計(jì)算主方向；其次，根據(jù)Rotated BRIEF(Binary Robust Independent Elementary Features，二元魯棒獨(dú)立基本特征)描述算法，生成特征點(diǎn)的特征向量；最后，通過(guò)計(jì)算模板圖像特征向量和待搜索圖像特征向量的漢明距離(Hamming Distance)，來(lái)確定各個(gè)特征向量的相似度。

1.1 關(guān)鍵點(diǎn)檢測(cè)——FAST算法

判斷一個(gè)像素點(diǎn)是否為關(guān)鍵點(diǎn)，檢測(cè)方法是判斷該點(diǎn)灰度值與周?chē)徲騼?nèi)大部分的像素點(diǎn)進(jìn)行對(duì)比，若相差過(guò)大則該像素可能是角點(diǎn)(特征點(diǎn))。為判斷特征點(diǎn)是否角點(diǎn)，先假定該特征點(diǎn)為點(diǎn)P，通過(guò)以點(diǎn)P為中心，半徑為3個(gè)像素作圓，并使該圓過(guò)16個(gè)像素點(diǎn)。判斷在圓周上的16個(gè)像素點(diǎn)中，是否最少有連續(xù)的n個(gè)像素點(diǎn)滿足都比Ip+t大，或都比Ip-t小的情況。如果實(shí)際數(shù)據(jù)滿足公式(1)，則可以確定P是一個(gè)特征點(diǎn)，否則P不是特征點(diǎn)。

(1)

式中，Ip表示點(diǎn)P的灰度值；t表示閾值；I(x)表示圓周上任意像素點(diǎn)的灰度值；I(p)表示圓心的灰度值；εd表示給定的灰度差值(閾值)。若N值超過(guò)設(shè)定的閾值(一般取值為周?chē)鷪A圈點(diǎn)的3/4)，則認(rèn)為P點(diǎn)是一個(gè)特征點(diǎn)。

1.2 特征點(diǎn)匹配——BRIEF算子

得到特征點(diǎn)后，需要對(duì)這些特征點(diǎn)的屬性進(jìn)行描述。屬性的輸出稱為該特征點(diǎn)的描述子(Feature DescritorS)。ORB算法使用BRIEF算子進(jìn)行一個(gè)特征點(diǎn)描述子的計(jì)算。BRIEF特征提取思路是：在關(guān)鍵點(diǎn)附近以一定模式隨機(jī)選取適量點(diǎn)對(duì)，將這些點(diǎn)對(duì)的灰度值大小進(jìn)行比較，結(jié)果組合起來(lái)成為二進(jìn)制串，此二進(jìn)制串作為角點(diǎn)的描述子。算法操作流程如下：

Step1以關(guān)鍵點(diǎn)P為圓心且以d為半徑做圓O。

Step2在圓O內(nèi)某一模式選取N個(gè)點(diǎn)對(duì)(實(shí)際應(yīng)用中可取到512)。

Step3定義操作T

式中：IA表示點(diǎn)A的灰度。

Step4分別對(duì)已選取的點(diǎn)對(duì)進(jìn)行T操作，將得到的結(jié)果進(jìn)行整合。

BRIEF使用二進(jìn)制編碼的方法，在特征點(diǎn)周?chē)囊欢▍^(qū)域內(nèi)提取描述子。因提取的描述子簡(jiǎn)單，所以相較于SIFT、SURF算法存儲(chǔ)空間更小，因使用漢明距離進(jìn)行對(duì)比，匹配速度也比SIFT算法更快。

2 K-means聚類算法

K-means聚類分析算法有簡(jiǎn)捷易懂、適應(yīng)性強(qiáng)、高效聚類的優(yōu)點(diǎn)，是目前普遍運(yùn)用的一種聚類分析算法。根據(jù)已知關(guān)鍵點(diǎn)特征向量間的歐氏距離，運(yùn)用 K-means 聚類分析算法對(duì)這些特征向量進(jìn)行聚類，選取與其余向量差別最小的特征向量作為初始質(zhì)心的方式，可以優(yōu)化ORB特征點(diǎn)，簡(jiǎn)化計(jì)算維度。K-means聚類算法是通過(guò)迭代方式求解，具體算法流程如下：

Step1將已知數(shù)據(jù)分為K組，再隨機(jī)地選取K個(gè)對(duì)象來(lái)作為初始質(zhì)心(聚類中心)。

Step2計(jì)算每個(gè)對(duì)象與各個(gè)已知聚類中心之間的歐氏距離，再把這個(gè)對(duì)象歸類給距離最近的聚類。

Step3分配給聚類中心的對(duì)象和聚類中心就組成了一個(gè)聚類。每次新分配一個(gè)樣本，根據(jù)現(xiàn)聚類中存在的對(duì)象，再次計(jì)算出聚類的新質(zhì)心。

以上過(guò)程將持續(xù)循環(huán)，直到滿足某個(gè)終止條件后結(jié)束。若直到?jīng)]有對(duì)象或最小數(shù)目對(duì)象被重新分配給了不同的聚類，導(dǎo)致聚類中心再次發(fā)生變化，實(shí)現(xiàn)誤差平方和局部最小的條件后，迭代求解的聚類分析算法將不再重復(fù)。

K-means聚類算法中，初始聚類中心的選取與聚類數(shù)目K的確定，是兩個(gè)不容忽視的問(wèn)題。初始聚類中心的選取可采用基于主成分分析(Principal Components Analysis，PCA)的方式；聚類數(shù)K的問(wèn)題，可通過(guò)基于潛在穩(wěn)定性的K-means最佳聚類數(shù)確定方法進(jìn)行確定。

ORB算法識(shí)別到關(guān)鍵點(diǎn)的坐標(biāo)信息及描述子后，通過(guò)對(duì)關(guān)鍵點(diǎn)keypoint的坐標(biāo)進(jìn)行聚類，在K-means算法中的K值取值為2，即得到優(yōu)化后的算法。

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

為驗(yàn)證本研究算法的有效性，首先對(duì)雙目圖像公開(kāi)數(shù)據(jù)集進(jìn)行大量實(shí)驗(yàn)后，再采用CCD相機(jī)拍攝實(shí)驗(yàn)室圖像進(jìn)行測(cè)試。實(shí)驗(yàn)的CPU型號(hào)為i7-9600K，采用Python語(yǔ)言實(shí)現(xiàn)本研究中的相關(guān)算法，進(jìn)行圖像匹配。通過(guò)將本文提出的算法與傳統(tǒng)ORB算法、SIFT算法的匹配效果進(jìn)行對(duì)比，驗(yàn)證本算法的可行性。通過(guò)K-means聚類算法改進(jìn)后的算法相較于傳統(tǒng)ORB算法剔除誤匹配效果較為明顯，同時(shí)具有時(shí)間優(yōu)越性。

通過(guò)兩種算法對(duì)雙目圖片匹配結(jié)果可以看出，ORB與K-means算法結(jié)合后的算法性能，得到了一定程度的提升，即本文提出的算法在對(duì)雙目圖像進(jìn)行特征點(diǎn)進(jìn)行匹配時(shí)，圖片中特征點(diǎn)匹配準(zhǔn)確度有明顯提高，OpenCV中的ORB算法具有一定程度的尺度不變性。通過(guò)圖1與圖2對(duì)公開(kāi)雙目圖片數(shù)據(jù)集進(jìn)行圖像匹配的實(shí)驗(yàn)結(jié)果對(duì)比可見(jiàn)，在公開(kāi)數(shù)據(jù)集上進(jìn)行本文算法實(shí)驗(yàn)性能良好；圖3是使用CCD相機(jī)拍攝圖進(jìn)行圖像匹配，由圖可見(jiàn)，采用K-means聚類算法匹配結(jié)果，剔除了傳統(tǒng)ORB算法匹配結(jié)果中的誤匹配。通過(guò)兩種算法的匹配圖對(duì)比可知，結(jié)合了K-means算法的ORB算法正確率得到了明顯提高。

(a) SIFT算法匹配結(jié)果

(b) ORB算法與改進(jìn)后算法的匹配結(jié)果

(a) SIFT算法匹配結(jié)果

(b) ORB算法與改進(jìn)后算法的匹配結(jié)果

(a) SIFT算法匹配結(jié)果

(b) 拍攝的雙目圖片算法對(duì)比結(jié)果

圖像匹配算法的耗時(shí)和匹配識(shí)別個(gè)數(shù)的對(duì)比結(jié)果見(jiàn)表1、表2。

表1 圖像匹配算法耗時(shí)對(duì)比

表2 圖像匹配算法識(shí)別個(gè)數(shù)對(duì)比

由表1中可以看出，SIFT算法的運(yùn)行時(shí)間相比傳統(tǒng)ORB算法長(zhǎng)，ORB算法的實(shí)時(shí)性優(yōu)勢(shì)遠(yuǎn)超SIFT算法。本文算法在傳統(tǒng)ORB算法上疊加了K-means聚類算法，雖然本文算法比傳統(tǒng)ORB算法耗時(shí)長(zhǎng)，但運(yùn)行速度遠(yuǎn)遠(yuǎn)小于SIFT匹配算法，速度方面達(dá)到預(yù)期效果。

表2為3種算法圖像匹配識(shí)別的特征對(duì)數(shù)目的對(duì)比。通過(guò)對(duì)表格數(shù)據(jù)分析可知，本文算法消除了傳統(tǒng)ORB算法中一些匹配錯(cuò)誤的點(diǎn)，從而提高了匹配正確率。

ORB算法與K-means算法的結(jié)合，在運(yùn)行時(shí)長(zhǎng)和匹配正確率上都有很好的表現(xiàn)，具有魯棒性。結(jié)合后的算法雖然增加了一些時(shí)間開(kāi)銷，但整體上對(duì)算法的實(shí)時(shí)性驗(yàn)證并無(wú)明顯影響。

4 結(jié)束語(yǔ)

本文提出利用ORB算法進(jìn)行雙目圖像匹配，使用K-means聚類的圖像匹配算法，具有魯棒性強(qiáng)的優(yōu)點(diǎn)，耗時(shí)相比于ORB算法有一定增加，但實(shí)時(shí)性相較于SIFT算法仍有明顯優(yōu)勢(shì)。由于ORB算法不具有尺度不變性，在對(duì)具有尺度變換較大的圖片處理時(shí)，本文算法則需要改進(jìn)。因?qū)嶒?yàn)為雙目測(cè)距環(huán)境，雙目匹配對(duì)尺度不變形要求較低，而對(duì)實(shí)時(shí)性要求較高，故采用改進(jìn)的ORB算法在OpenCV中的尺度變換特征下進(jìn)行匹配，可以達(dá)到預(yù)期效果。