一種改進的OSID的圖像匹配算法*

陳雪松，雷 嫚，畢 波，唐錦萍

(1.東北石油大學電氣信息工程學院，黑龍江 大慶 163318；2.東北石油大學數(shù)學與統(tǒng)計學院，黑龍江 大慶 163318;3.海南醫(yī)學院公共衛(wèi)生學院，海南 ?？?571101;4.黑龍江大學數(shù)據(jù)科學與技術(shù)學院，黑龍江 哈爾濱 150080)

1 引言

盡管 SIFT(Scale Invariant Feature Transform)算法的關鍵點檢測器及描述符[1 - 4]已有十幾年的歷史，在很多基于視覺特性的應用中，包括對象識別[1]、圖像拼接[5]和圖像映射[6]等，都非常成功，但它也伴隨著大量的計算負擔，尤其是對于實時系統(tǒng)而言，例如視覺測定器或者低功耗設備手機等，因此需要找到計算成本較低的替代方案。而且隨著科學技術(shù)的進步，數(shù)據(jù)處理的需求也日益增加，對算法的復雜性和魯棒性要求也越來越高，對于低復雜度、低存儲空間的特征描述算法的需求也越來越迫切。所以，研究人員已經(jīng)開始對高維浮點型描述子進行降維處理。

于是二進制位串描述子就產(chǎn)生了，它和實值描述子最大的不同就是，不是采用歐氏距離作為度量距離，而是采用漢明距離，其優(yōu)點就是計算量比歐氏距離的小。

2013年，Wang等[7]采用一種新的快速魯棒不變特征FRIF (Fast Robust Invariant Feature)進行特征檢測和描述。其基本思想是利用快速逼近的Log檢測器來選擇尺度不變的關鍵點，并結(jié)合局部模式和模式間信息來構(gòu)造獨特的二進制描述符。2014年，Xu等[8]提出了區(qū)域不變量的序數(shù)和空間信息OSRI(Ordinal and Spatial Information of Regional Invariants)算法，該算法將特征點的局部鄰域擴展到多層范圍，并對每層鄰域按像素強度值和梯度方向順序劃分為多層子區(qū)域；按圓形區(qū)域中的像素強度值或者梯度方向值將劃分范圍進行多次旋轉(zhuǎn)(移位)，構(gòu)建多組層的子區(qū)域集合；最后通過子區(qū)域中多種不變特征的比較結(jié)果形成二進制描述向量。2016年，譚躍生等[9]針對傳統(tǒng)局部特征提取算法在提取特征點時效率不高,生成描述子需要計算主方向等問題,結(jié)合SURF(Speeded-Up Robust Features)算法和RGT(Radial Gra- dient Transform)[10],在精度損失盡可能小的情況下提高局部不變特征提取速度,提出一種改進的加速徑向SURF算法AR-SURF。實驗結(jié)果表明,AR-SURF算法節(jié)省了時空損耗,提升了定位速度,提取效果更好,更加適合海量圖像處理。2018年，于達[11]對目前常用的局部不變特征匹配算法進行研究,分析比較各算法的旋轉(zhuǎn)不變性、尺度不變性、定位精度和匹配效率。利用Grab Cut算法對識別出的目標物體進行圖像分割,針對圖像分割過程中需要人機交互的問題,將特征匹配算法與圖像分割算法連接起來,提高算法的自動化程度。其次,在完成目標物體圖像分割的基礎上,基于圖像矩計算出目標的質(zhì)心,利用極線約束提高質(zhì)心匹配效率。2019年，趙愛罡等[12]提出了一種基于兩層策略的特征點匹配方法。首先根據(jù)特征點響應的閾值對實時圖和參考圖分別提取一級特征點和二級特征點,然后依據(jù)二級特征點到一級特征點的距離使二級特征點隸屬于距離最近的一級特征點,由此達到對二級特征點進行分組的目的。仿真實驗結(jié)果表明,特征點匹配速度大幅提升。

本文提出的特征建立在最近開發(fā)的一種基于旋轉(zhuǎn)的快速提取特征的描述子ORB (Oriented FAST and Rotated BRIEF)[13,14]特征檢測和序數(shù)空間強度分布OSID(Ordinal Spatial Intensity Distribution)[15]描述子上。由于它們的優(yōu)良性能和低成本，這2種技術(shù)都是有吸引力的。本文討論了SIFT技術(shù)和OSID的幾個局限性，其中最明顯的是匹配時間成本高。

2 序數(shù)空間強度分布

OSID的特征描述子的主要思想是在亮度逐漸增加的情況下，局部塊像素強度的相對順序保持不變或穩(wěn)定。OSID是通過對二維直方圖進行柵格化來構(gòu)造的，在序數(shù)空間和空間強度中對像素分組(或組合)。在序數(shù)空間中對像素進行綁定，可以確保特征不受復雜亮度變化的影響，同時在空間上綁定像素可以捕獲圖像塊的結(jié)構(gòu)信息：如果特征是從像素的樸素直方圖中獲得的，就會丟失。為了提取特征及其描述子，通過預處理步驟和特征檢測步驟對特征點進行定位。

2.1 預處理與特征檢測

在計算特征之前，目標圖像和配準圖像需要用高斯濾波器進行平滑處理，以達到消除噪聲的目的，因為像素強度的相對順序可能對噪聲很敏感。所以，要為特征點劃分局部區(qū)域， 具體過程為：對于每個檢測到的特征點，提取大小為d*d的局部塊，其中d的典型選擇為41，但它可能隨圖像分辨率和尺度的變化而變化。

2.2 序號和空間標號

對于序數(shù)分布，塊中的像素被分組到n個箱子中，每個箱子中的像素都具有相似的像素強度。與具有n個箱子的常規(guī)直方圖不同，每個箱子表示順序范圍，而不是原始像素強度的范圍，因為原始像素可能由于幀的變化導致像素值發(fā)生改變。像素被標記為它們所屬的箱號。在空間分布中，d*d圖像塊中的像素基于n個扇形空間細分來標記。將像素分配給子圖像塊是預先計算的，以節(jié)省計算時間。

2.3 二維直方圖和柵格化

為每個局部塊創(chuàng)建一個二維直方圖，其中，直方圖中的x軸表示按相對順序編碼的像素強度，y軸表示空間分布。在二維直方圖中，位置(x,y)處的數(shù)值表示在y細分區(qū)域中像素點的個數(shù)，像素點的排序為x。

二維直方圖中的每一行都是一維直方圖，它表示像素在給定子塊的序號空間中的分布情況。它是一個n維向量，每個維表示有多少像素具有序號空間標簽。二維直方圖中的每一列表示相似強度的像素在子塊中的分布情況。

在為每個圖像塊構(gòu)造了有序空間的二維直方圖之后，需要對圖像中每個圖像塊構(gòu)造的直方圖進行柵格化處理，形成一個n*m維向量作為d*d塊的描述符。柵格化的起始庫和方向(或順序)可以是任意的，但是需要預先定義。最后，根據(jù)塊中的像素個數(shù)對特征向量進行歸一化處理，消除特征向量對描述符的影響。因此，圖像塊的大小可能因特征點的不同而不同。OSID描述符的具體步驟如圖1所示。

Figure 1 Workflow of OSID descriptor

3 改進的OSID算法

本節(jié)首先介紹改進OSID精度的方法，對OSID描述子進行改進，OSID描述符構(gòu)建的過程中，根據(jù)關鍵點信息(像素強度)區(qū)域的密集程度設置m的值，并對描述子的表現(xiàn)形式進行轉(zhuǎn)換，將直方圖描述子轉(zhuǎn)換為二進制描述子，提高算法運行速度。

3.1 對OSID描述子的改進

OSID將強度順序信息編碼為描述符，然后對局部圖像塊中不同子區(qū)域的強度順序的直方圖進行計算。這是OSID描述符的基本思想。簡單地說，它既捕獲了局部圖像塊中像素的序數(shù)分布，又捕獲了像素的空間分布，并使用它們的聯(lián)合分布作為特征描述符。具體來說，在特征點周圍取一個41*41大小的圖像塊，將圖像塊分成16個等大的扇形，再對每個扇形內(nèi)的像素進行排序，并放入8個箱子中(0～32，32～64，…,223～255)，每個特征點生成16*8的直方圖子描述子，將每個特征點的子描述子連接構(gòu)成OSID描述子。然后，在特征點41*41圖像塊范圍內(nèi)，可能存在其他特征點，為更好地表達多個特征點的圖像塊信息，本文提出將m(扇形個數(shù))自適應，在保證圖像信息的前提下節(jié)省儲存空間并提高算法計算速度。

快速檢測特征點算法FAST(Features from Accelerated Segment Test)[16,17]的提出者Rosten等將FAST的原理表述為：若某像素與其周圍鄰域內(nèi)足夠多的像素點相差較大，則該像素可能是角點。ORB描述子的特征提取是由FAST算法改進的，稱為oFAST(FAST Keypoint Orientation)[9]，即在使用FAST提取出特征點之后，給其定義一個特征點方向，以此來實現(xiàn)特征點的旋轉(zhuǎn)不變性。本文使用ORB算法檢測特征點，再對特征點構(gòu)建描述子；在構(gòu)建描述子的過程中，一個特征點的圖像塊里有多個特征點，則這個圖像塊中有多個像素點與其周圍鄰域內(nèi)足夠多的像素點相差較大，本文認為此特征點的局部圖像塊信息較為豐富，因此考慮將此局部圖像塊進行更細化的處理，增加扇形個數(shù)m，以更好地表達該區(qū)域圖像塊的信息。

OSID描述符構(gòu)建的過程中，圖像塊的扇形個數(shù)m的選擇是固定的，因此本文嘗試將扇形個數(shù)的值自適應，對特征點個數(shù)大于1的區(qū)域的m設置得更大，以保證圖像塊的信息被更好地表達，對特征點個數(shù)小于或等于1的區(qū)域的m設置得更小，在保證圖像信息能夠被表達的前提下節(jié)省儲存空間并提高算法速度。具體步驟：當某個特征點的41*41圖像塊內(nèi)除它本身外另有1～2個特征點時，將扇形個數(shù)設置為18；當某個特征點的41*41圖像塊內(nèi)除它本身外另有3～4個特征點時，將扇形個數(shù)設置為20；當某個特征點的41*41圖像塊內(nèi)除它本身外另有5個以上特征點時，將扇形個數(shù)設置為22。

3.2 對OSID匹配效果的改進

OSID最后生成的描述子是直方圖描述子。對每個特征點局部塊都創(chuàng)建一個二維直方圖，其中，直方圖中的x軸按照像素強度的相對順序編碼像素強度分布，y軸編碼空間分布。在為每個圖像塊構(gòu)造了有序空間的二維直方圖之后，對直方圖進行柵格化，形成一個n*m維向量作為d*d塊的描述符。然后，根據(jù)塊中的像素個數(shù)對特征向量進行歸一化處理，消除特征向量對描述符的影響。因此，圖像塊的大小可能因特征點的不同而不同。

由于目標圖像和配準圖像中的每一個特征點都會生成一個直方圖描述子，因此在圖像匹配的過程中，目標圖像中的任一直方圖描述子都需要與配準圖像中的所有直方圖描述子進行歐氏距離的計算，將歐氏距離數(shù)值最小的直方圖描述子對應的特征點判定為匹配特征點，因此計算復雜度高，運算時間長。二進制描述符比傳統(tǒng)描述符(即浮點向量描述符)所需的存儲空間要小得多。同時，計算用于評估二進制描述符之間的相似度的漢明距離比計算浮點向量描述符之間的歐氏距離快得多。因此，二進制描述符正在成為需要實時處理或內(nèi)存資源有限的應用程序的流行解決方案。

在此，本文將直方圖描述子編碼為二進制描述子，當生成改進OSID的直方圖描述子后，首先比較直方圖中直方條的數(shù)值 ：(1)當前直方條數(shù)值大于或等于后一個直方條數(shù)值時記為1，否則記為0；(2)直方圖最后一個直方條的數(shù)值與第一個直方條的數(shù)值進行比較，以保證描述子轉(zhuǎn)換后的二進制描述符維度與直方圖維度相同。這樣，每個特征點的局部圖像塊描述子就編碼成了二進制描述子，最后用漢明距離匹配特征點。

4 實驗

4.1 數(shù)據(jù)集

本文在標準數(shù)據(jù)集[18]上與多個著名的描述符進行性能比較，該數(shù)據(jù)集包含具有不同幾何和光度轉(zhuǎn)換的真實圖像(例如，視點變化、圖像模糊、JPEG壓縮)，本文對參考圖像(第1幅圖像)與相比變化較大的第4幅圖像，以及變化最大的第6幅圖像進行對比(對像素強度進行歸一化，使其最大值為1)。

4.2 實驗結(jié)果

實驗平臺和環(huán)境為CPU 1.8 GHz，內(nèi)存4 GB，Windows 7系統(tǒng)，Python 3.7.6，將本文算法與OSID算法、SIFT算法、SURF算法[19,20]、BRISK(Binary Robust Invariant Scalable Keypoints)算法[21 - 23]、改進ORB算法[24]和FAST算法在準確率和運行時間上進行對比。在每個數(shù)據(jù)集上給出3個算法的匹配連線圖，分別是改進OSID算法、除改進OSID算法外準確率最高的算法和除改進OSID算法外準確率最低的算法。

(1)視點更改。改進OSID描述符在wall數(shù)據(jù)集上進行了視點更改測試,結(jié)果如表1和表2所示。表1和表2為7種算法準確率和運行時間的對比，其中找到的特征點數(shù)包含2個數(shù)值，分別是目標圖像中的特征點數(shù)和配準圖像中的特征點數(shù)。

Table 1 Comparison of matching performance between the first and fourth images on wall dataset

Table 2 Comparison of matching performance between the first and sixth images in the wall dataset

由表1可以看出，由于改進OSID算法的特征點檢測部分與原算法一樣，所以二者找到的特征點數(shù)一樣，原算法準確率只有88.03%，運行時間為12.67 s。FAST算法找到的特征點數(shù)最多，但錯誤匹配點數(shù)量也最多，正確匹配率為83.65%，SIFT、SURF和BRISK算法找到的特征點數(shù)次之，改進ORB算法找到的特征點數(shù)較少，運行速度相對于SURF、BRISK和FAST算法較快。但是，改進后OSID算法找到的特征點數(shù)最少，誤匹配數(shù)量也最少，準確率為91.40%，運行時間為5.87 s。比SURF、BRISK、FAST和改進ORB等算法快5 s以上，比SIFT快70多秒。BRISK算法匹配點數(shù)最多，準確率為88.12%。由表2可以看出，在嚴重的視點變化時本文算法與對比算法的正確匹配率都有所下降，尤其是FAST算法，準確率只有51.83%，6種對比算法的表現(xiàn)也有所下降，但本文算法依然表現(xiàn)良好，準確率為86.64%，運行時間為6.01 s?？梢钥吹?，本文改進的描述子不管是在適當數(shù)量的視點變化時還是在嚴重的視點變化時表現(xiàn)得都很好。

由圖2～圖4可以直觀地看出，在wall數(shù)據(jù)集的第1幅與第4幅圖像匹配性能對比中，本文改進后的OSID算法匹配效果最好，BRISK算法次之，SIFT算法的匹配連線混亂，準確率最低。而由圖5～圖7觀察到，在wall數(shù)據(jù)集的第1幅與第6幅圖像匹配性能對比中，視角變化很大，本文改進后的OSID算法匹配效果雖然準確率有所下降，但依然是表現(xiàn)最好的，BRISK算法依舊次之，而FAST算法的匹配連線混亂，準確率最低。

Figure 2 Line matching diagram of the first and fourth images in wall dataset using improved OSID algorithm

Figure 3 Line matching diagram of the first and fourth images in wall dataset using BRISK algorithm

Figure 4 Line matching diagram of the first and fourth images in wall dataset using SIFT algorithm

Figure 5 Line matching diagram of the first and sixth images in wall dataset using improved OSID algorithm

Figure 6 Line matching diagram of the first and sixth images in wall dataset using BRISK algorithm

Figure 7 Line matching diagram of the first and sixth images in wall dataset using FAST algorithm

(2)圖像模糊。本文也在bikes數(shù)據(jù)集的模糊圖像上進行了描述符測試，結(jié)果如表3和表4所示，F(xiàn)AST、SIFT、SURF和BRISK等算法找到的特征點數(shù)都較多，但錯誤匹配點數(shù)量也較多，且在圖像模糊程度高時，SIFT、BRISK和改進ORB算法的表現(xiàn)也有所下降。原算法匹配點數(shù)和改進OSID的差不多，但是準確率低于改進OSID算法的。改進后的OSID算法在圖像模糊程度較高時準確率雖然也有所下降，但總體表現(xiàn)良好?？梢杂^察到，雖然改進OSID算法不是為了解決圖像模糊問題而提出的， 但是它也表現(xiàn)得比其他描述子優(yōu)異。

Table 3 Comparison of matching performance between the first and the fourth images on bikes dataset

Table 4 Comparison of matching performance between the first and the sixth images on bikes dataset

由圖8～圖10可以直觀地看出，在bikes數(shù)據(jù)集的第1幅與第4幅圖像匹配性能對比中，本文改進后的OSID算法匹配效果明顯良好，F(xiàn)AST算法居于第2，SIFT算法匹配效果最差。而由圖11～圖13觀察到，在bikes數(shù)據(jù)集的第1幅與第6幅圖像匹配性能對比中，模糊程度較高，本文改進后的OSID算法匹配效果依然表現(xiàn)良好，F(xiàn)AST算法依舊次之，而BRISK算法的匹配連線雜亂，準確率最低。

Figure 8 Line matching diagram of the first and fourth images in bikes dataset using improved OSID algorithm

Figure 9 Line matching diagram of the first and fourth images in bikes dataset using FAST algorithm

Figure 10 Line matching diagram of the first and fourth images in bikes dataset using SIFT algorithm

Figure 11 Line matching diagram of the first and sixth images in bikes dataset using improved OSID algorithm

Figure 12 Line matching diagram of the first and sixth images in bikes dataset using FAST algorithm

Figure 13 Line matching diagram of the first and sixth images in bikes dataset using BRISK algorithm

(3)JPEG壓縮。本文也在不同級別的JPEG壓縮下使用UBC數(shù)據(jù)集測試了描述符，結(jié)果如表5和表6所示?？梢杂^察出，在不同壓縮級別下SIFT算法都表現(xiàn)較好，準確率分別為88.12%和84.37%，但運行時間較慢，而改進后OSID描述子無論在何種壓縮級別下運行時間都最快，且在JPEG壓縮級別適中的情況下表現(xiàn)最好，在JPEG壓縮級別較高的情況下表現(xiàn)良好。

Table 5 Comparison of matching performance between the first and fourth images on UBC dataset

Table 6 Comparison of matching performance between the first and sixth images on UBC dataset

由圖14～圖16可以直觀地看出，在UBC數(shù)據(jù)集的第1幅與第4幅圖像匹配性能對比中，本文改進后的OSID算法匹配效果最優(yōu)，改進ORB算法次之，SURF算法匹配效果最差。而由圖17～圖19觀察到，在UBC數(shù)據(jù)集的第1幅與第6幅圖像匹配性能對比中，本文改進后的OSID算法和對比算法的準確率都有所下降，但改進OSID算法依然表現(xiàn)良好，F(xiàn)AST算法次之，而SURF算法的匹配連線雜而亂，準確率最低。

Figure 14 Line matching diagram of the first and fourth images in UBC dataset using improved OSID algorithm

Figure 15 Line matching diagram of the first and fourth images in UBC dataset using improved ORB algorithm

Figure 16 Line matching diagram of the first and fourth images in UBC dataset using SURF algorithm

Figure 17 Line matching diagram of the first and sixth images in UBC dataset using improved OSID algorithm

Figure 18 Line matching diagram of the first and sixth images in UBC dataset using FAST algorithm

Figure 19 Line matching diagram of the first and sixth images in UBC dataset using SURF algorithm

5 結(jié)束語

針對OSID算法同一個圖像塊多個特征點、實時性較差的問題，本文提出了一種基于局部二進制模式的快速匹配算法。該算法采用改進的局部二進制模式對ORB特征進行描述，并對構(gòu)建描述子的扇形個數(shù)采用自適應的方法，豐富描述子所包含的信息，提高了算法的準確率。實驗表明，本文算法計算復雜度低、魯棒性好，并且該描述子在復雜視點變化、圖像模糊等情況下的特征匹配是非常有效的。下一步將著重考慮對特征點檢測的速度與精度進行研究，以進一步提高圖像匹配算法性能。