一種基于階陣列的BRIEF特征描述子

張娓娓,趙金龍,何 佳,陳綏陽,2,王 杰

(1.西安思源學(xué)院 電子信息工程學(xué)院,陜西 西安 710038;2.西安交通大學(xué) 理學(xué)院,陜西 西安 710071)

0 引 言

在圖像處理領(lǐng)域,特征描述子對目標(biāo)物的不變性研究具有重要意義。一個好的描述子應(yīng)該能夠抵抗目標(biāo)物的尺度變化、光線變化、旋轉(zhuǎn)變化、仿射變化和噪聲干擾。一般而言,一個描述子的構(gòu)成首先是從圖像中提取一些特征點,然后根據(jù)特征點周圍的區(qū)域形成描述子,最后,采用適當(dāng)?shù)木嚯x度量方法來比對描述子的相似程度,判定描述子與目標(biāo)物之間是否同一。對于視覺分類問題而言,常用的方法是通過特征向量來描述一類具有共同點的物體,然后形成可查找的視覺關(guān)鍵字[1-2]。假定關(guān)鍵點是已知的,理想的描述子應(yīng)該是能夠包含關(guān)鍵點周圍區(qū)域的絕大多數(shù)重要且惟一的信息內(nèi)容。

在實時性和穩(wěn)定性要求嚴(yán)格的應(yīng)用領(lǐng)域,描述子必須能夠提供快速的計算和比對結(jié)果,這就需要設(shè)計一個穩(wěn)定而高效的描述子,人們?yōu)榇碎_展了大量的實驗和研究。其中,為了滿足描述子的抗尺度不變性,Lowe提出了基于直方圖計算梯度主方向的方法[3-4],這一方法是在一系列尺度下,對經(jīng)過高斯濾波的特征點周圍區(qū)域的灰度值進(jìn)行采樣,計算出圖像主方向。該方法被廣泛用于描述關(guān)鍵點的方向性。類似的計算主方向的方法還有GLOH[5]和HOG[6]。雖然這些方法并不能很直觀地反映圖像空間頻率關(guān)系,但它們擁有很準(zhǔn)確的方向判斷性。此外,SURF描述子主要利用特征點周圍像素點對HAAR濾波的響應(yīng)來提高運算速度[7-8],其性能不亞于SIFT描述子。即使如此,SIFT和SURF描述子的計算代價依然很高,不能很好地應(yīng)用于實時圖像處理。為此,Ke和Skthankar[9]提出在計算SIFT描述子主元時,采用PCA方法對特征點周圍41×41的像斑區(qū)域進(jìn)行計算,從而將原有的2×39×39維的向量降低成20維向量,形成更為精準(zhǔn)的PCA-SIFT描述子。PCA-SIFT描述子保留了SIFT描述子的尺度不變性,同時降低了特征向量維數(shù),但在計算描述子過程中會增加一定的計算量和損失少量的差異性。Bin基于階序組合池提出了兩種抗旋轉(zhuǎn)不變的描述子[10]:一種是MROGH(Multi-support Region Order-based Gradient Histogram),主要是對特征匯聚策略進(jìn)行了改進(jìn);另一種是MRRID(Multi-support Region Rotation and Intensity Monotonic Invariant Descriptor)。Miksik和Mikolajczyk通過實驗驗證了基于階排列的描述子的計算復(fù)雜度要低于SIFT和SURF[5,11]。LIOP(Local Intensity Order Pattern)方法進(jìn)一步證實這一觀點[12],LIOP是一種用來刻畫圖像局部亮度順序信息的特征描述方法。該特征描述方法利用圖像(塊)整體的亮度順序信息將圖像塊分割為若干個局部子區(qū)域,以此來加快LIOP的計算速度。整個圖像塊的整體和局部亮度順序信息被提取出來,構(gòu)成LIOP特征。這種特征不僅對光照變換不敏感,對視角變化、圖像模糊、圖像有損壓縮等也同樣不敏感。

除了實時應(yīng)用需求,在大規(guī)模數(shù)據(jù)運算和移動設(shè)備上,計算量也是一個至關(guān)重要的約束條件。計算量小的描述子主要有Calonder提出的二值特征描述子BRIEF[13-14],以及基于BRIEF的抗尺度變化和旋轉(zhuǎn)變化的改進(jìn)特征描述子BRISK[15]。此外,ORB也是一種具有抗旋轉(zhuǎn)不變性、計算高效的描述子[16],它采用了基于FAST算子的特征點檢測方法。Ziegler也提出了一種線性時間復(fù)雜度的描述子[17],該描述子通過對兩張圖片的RGB分塊值進(jìn)行排序,結(jié)合排序后序列的距離,實現(xiàn)對圖片的特征描述[18]。

該文提出一種基于BRIEF的改進(jìn)的階排列描述子OPoBRIEF (Order Permutation of BRIEF)。OPoBRIEF采樣多組對比對進(jìn)行分析,并對采樣點進(jìn)行排列,從而形成局部特征描述。該方法比BRIEF描述子包含更多的局部信息,而且計算簡單,易于實現(xiàn)。首先,介紹BRIEF相關(guān)概念;然后,將BRIEF描述子擴(kuò)展到N維,為后續(xù)的階排列提供基礎(chǔ),并分析采樣過程中使用box filter的濾波效果,以及序列的距離度量計算方式;最后對OPoBRIEF的主要性能進(jìn)行實驗分析。

1 相關(guān)描述子簡介

BRIEF特征描述子由Calonder等在ECCV’2010上提出[1],基本思想是對特征點附近的分塊區(qū)域隨機采樣,將采樣的像素對灰度化后進(jìn)行比較,比較結(jié)果形成一個二進(jìn)制串,將這個二進(jìn)制串作為該特征點的特征描述子。BRIEF特征描述子的主要優(yōu)點是計算簡單,匹配效率高,能滿足實時視頻或者移動計算環(huán)境的要求。

1.1 BRIEF描述子

定義一個經(jīng)過高斯平滑后的圖像塊p,圖像塊的大小為s×s,隨機在塊中采樣一對像素點進(jìn)行比較,比較結(jié)果由下式?jīng)Q定。

(1)

式中,I(p,x)表示第p個圖像塊中的像素點x的灰度值,I(p,y)表示第p個圖像塊中的像素點y的灰度值。在塊p中隨機采樣n對對比對,形成一個n維的二進(jìn)制描述串,也就是BRIEF描述子,如下:

(2)

在選取采樣點時,采樣點的空間分布應(yīng)服從高斯分布,保證采樣更為全局化。描述子向量之間的距離可以采用漢明距離,通過異或操作實現(xiàn)快速計算。通常,nd代表了形成的二值序列的維度,可以取值為128、256、512。BRIEF描述子的一個采樣實例如圖1所示。

圖1 BRIEF 相關(guān)的空間采樣

1.2 ORB描述子

BRIEF描述子本身僅考慮了單個像素,不具備方向,也就不具有旋轉(zhuǎn)不變性。ORB描述子嘗試給BRIEF添加一個方向,特征點的主方向是通過矩(moment)和圖像矩心計算而來,然后,通過貪心算法尋找二值準(zhǔn)則特征集中相關(guān)性最低的對比對集合,作為ORB描述子。圖2顯示了在大小為31×31的圖像塊上,采用5×5大小的子窗口進(jìn)行處理后獲得的ORB描述子。

圖2 ORB相關(guān)的空間采樣

1.3 BRISK描述子

BRISK描述子采用領(lǐng)域采樣模式,即在以特征點為中心的每個離散化同心圓上,取均勻分布的N個點,如圖3所示。BRISK描述子具有旋轉(zhuǎn)不變性和尺度不變性的特點。文獻(xiàn)[10]中BRISK采用了不同尺度高斯平滑去噪技術(shù),并使用FAST算子值作為度量局部的最大性指標(biāo),在多尺度空間上尋找最值,使其具有尺度不變性;為了適應(yīng)旋轉(zhuǎn)不變性,在建立描述子的過程中,利用長距離點對的梯度累加從而估計特征點角點的主方向。

圖3 BRISK相關(guān)的空間采樣

2 OPoBRIEF描述子

Ziegler通過隨機提取圖像局部的像素對,比對灰度值形成二值序列,然后計算漢明距離(hamming distance)進(jìn)行相似匹配[17]?？紤]到灰度對比對的不穩(wěn)定性,首先增加采樣點數(shù)量,然后引入階排列的概念,加強對二值對比對的條件約束,最后形成更為穩(wěn)定的階排列BRIEF描述子。

2.1 N維BRIEF描述子

Calonder提出的BRIEF描述子只是利用局部圖像鄰域內(nèi)兩個隨機點的灰度關(guān)系來建立局部圖像特征描述子,得到的是二值特征描述子。這種方法結(jié)構(gòu)簡單,計算速度快。但是,由于只選取了兩個采樣點,所構(gòu)成的對比對的關(guān)系比較簡單,使得描述子不夠穩(wěn)定。通過對局部圖像塊進(jìn)行多次采樣形成一個采樣組,組內(nèi)采樣點數(shù)為n(n>2),進(jìn)而引入采樣點的階排列的概念,提出OPoBRIEF描述子。

由于有多個采樣點需要進(jìn)行比對,首先對式(1)進(jìn)行擴(kuò)展。給定從基準(zhǔn)圖和測試圖中提取特征關(guān)鍵點的集合為χ,χ?Rs,且采樣圖像的分塊區(qū)域都經(jīng)過平滑處理,降低了圖像灰度值的一些噪聲影響。獲得描述子后,可以通過計算不同集合下采樣組的相似關(guān)系來進(jìn)行特征匹配。每組采樣點中組內(nèi)采樣點的二值測試序列可以描述為:

(3)

實際上,Calonder所介紹的二值序列BRIEF特征描述子是ns=2時的情況,即式(1)替換表示為:

(4)

用來形成二值序列串的描述子式也可以擴(kuò)展到nd維,表示為:

(5)

在OPoBRIEF中,階排列是用在有多個采樣點的情況。例如圖4情況,在平滑過的子塊上隨機抽取4個采樣點:I(x(j,1))=60,I(x(j,2))=160,I(x(j,3))=15,I(x(j,4))=200,該組采樣點的階排列字串為4 213。

通過計算得到的階排列來替換BRIEF描述子中的二值測試序列,則OPoBRIEF描述子對每個特征點的維度變化為nd×ns。顯然,ns值過大會造成階排列字串過于復(fù)雜,通常ns取值為3和4較為合適,兩者的階排列模式只有6和24,計算開銷較小。

圖4 構(gòu)造階排列的過程

2.2 平滑核的選擇

高斯噪聲可能損壞階排列的穩(wěn)定性,主要原因是噪聲會引起像素值局部極大值或者極小值突變,從而改變灰度值在特征向量里的排列順序。為此,采用不同大小的高斯核濾波和不同窗口的Boxing濾波,研究測試OPoBRIEF的穩(wěn)定性。

通常來說,Boxing濾波的窗口尺寸越大,階排列得到的結(jié)果就越穩(wěn)定。但是,這會導(dǎo)致同樣的階排列生成不同的排列串。為避免這一問題,該文嘗試通過在一些公共圖像測試集上進(jìn)行實驗,尋找一個窗口大小合適的Boxing濾波。圖5給出在測試圖像集合Benchmark上,采用不同窗口大小的Boxing濾波算法,對不同種類的圖像集合進(jìn)行平滑后,描述子的正確匹配率實驗結(jié)果。其中,分塊大小p=48、維度nd=256,每一組實驗包含了8個不同大小窗口的Boxing濾波測試的結(jié)果。由圖可見,當(dāng)k值在13附近時,Boxing濾波能夠達(dá)到較高正確匹配率。

圖5 不同窗口大小Boxing濾波后描述子的正確匹配率

Calonder建議采用48×48的分塊、7×7的窗口和δ=2高斯核進(jìn)行濾波處理,能夠獲得穩(wěn)定的效果[11]。實驗結(jié)果表明,采用boxing濾波比高斯濾波的效果更好,穩(wěn)定性高于高斯濾波,實驗結(jié)果優(yōu)于文獻(xiàn)[13]。另一方面,考慮到構(gòu)造一個boxing濾波只需要四個點和三次加法運算,算法更為簡單有效,更適用于進(jìn)行區(qū)域分塊平滑濾波。

2.3 階排列距離度量

Ziegler介紹了三種不同的高效的距離計算方法[17]:Hamming距離、Cayley距離和Kendall's tau距離。其中Kendall's tau距離已經(jīng)被證明在計算階排列的距離上要比其他兩種計算方法好,雖然它的計算復(fù)雜度為O(m2),高于漢明距離和Cayley距離的計算復(fù)雜度O(m)。

Kd(π1,π2)=|{(i,j)|(π1(i)<π1(j)∧π2(i)>π2(j))∨(π1(i)>π1(j)∧π2(i)<π2(j)),1≤i,j≤ns}|

(6)

3 實驗與結(jié)果

在公共圖像數(shù)據(jù)集上進(jìn)行了不同采樣大小的測試。首先計算了ns=3和ns=4情況下提取的OPoBRIEF描述子,并與BRIEF進(jìn)行對比;而后又對OPoBRIEF的旋轉(zhuǎn)不變性進(jìn)行了實驗和分析。實驗硬件環(huán)境:Intel(R) 雙核CPU-E7500,主頻2.9 GHz,6.0 GB內(nèi)存,軟件環(huán)境:Linux系統(tǒng),基于OpenCV類庫采用C語言編程。

3.1 描述子穩(wěn)定性實驗

實驗選取五個不同的圖片數(shù)據(jù)集wall、ubc、leuve、trees和bikes進(jìn)行測試,每組圖片6個,如圖6所示。這五個不同的數(shù)據(jù)集可用來測試在不同情況下圖像變換對描述子穩(wěn)定性的影響。其中,wall主要針對的是相機的鏡頭視點的改變;ubc主要針對的是圖像壓縮率的變化;leuve主要針對的是圖像的光照變化;trees和bikes主要針對的是圖像的模糊變化。

圖6 圖像測試集示例

Surf算法是OpenCV中一個快速和高效的特征點檢測算法,因此,該文主要采用Surf進(jìn)行關(guān)鍵點提取。表1是每組圖片比對結(jié)果,在最高匹配率前面加上了星號做標(biāo)記。表1記錄了在nd=256的情況下,3采樣點OPoB-3,4采樣點OPoB-4和BRIEF(B-256)三種方法的實驗結(jié)果。

表1 不同數(shù)據(jù)集的正確匹配率

通過分析表1的實驗結(jié)果可以發(fā)現(xiàn),除了第一組實驗,OPoBRIEF比BRIEF的整體匹配效果好,其中,OPoB-4比OPoB-3的整體匹配效果更好,OPoB-4的正確匹配率高于BRIEF。實驗結(jié)果同時說明選擇的采樣點數(shù)量越多,描述子包含的信息量越多,匹配的正確性也就越高。在測試描述子對旋轉(zhuǎn)不變性的實驗中,描述子OPoBRIEF的匹配效果并不比BRIEF描述子好很多。在trees和bikes測試集上的實驗結(jié)果表明,OPoB-4的匹配效果明顯優(yōu)于OPOB-3和BRIEF。尤其是在trees的數(shù)據(jù)集上,描述子OPOB-4要比描述子BRIEF平均多出21對以上的正確匹配對,這說明描述子OPoBRIEF對圖像的模糊有較強的抵抗性。而在用來測試光照變化對描述子影響的數(shù)據(jù)集leuve上,OPOB-4的效果也明顯優(yōu)于OPOB-3和BRIEF。最后在不同壓縮率比圖像的測試中,BRIEF的性能大多數(shù)情況會好過OPoBRIEF,但兩者的差距并不是十分巨大。

3.2 OPoBRIEF的旋轉(zhuǎn)不變性實驗

為了檢驗OPoBRIEF的旋轉(zhuǎn)不變性,設(shè)計了一組實驗。實驗所用的數(shù)據(jù)集是new york圖片序列,該圖片序列包含了35張圖片,覆蓋了從0到170和170到350度旋轉(zhuǎn)的圖片。特征點的提取算法使用的是最新版OpenCV中的SIFT和ORB算法,其中使用SIFT特征點提取法獲得26 235對匹配對,使用ORB算法獲得26 430對匹配對。如果考慮每10度作為一個錯誤區(qū)間,則有26 200對匹配對被衡量。實驗結(jié)果如表2所示,提供了錯誤區(qū)間為10到50的實驗結(jié)果。從實驗結(jié)果可以發(fā)現(xiàn),SIFT算法的主方向的準(zhǔn)確率為69.03%,要遠(yuǎn)高于ORB算法的主方向的準(zhǔn)確率57.95%,但在其他旋轉(zhuǎn)度SIFT算法不及ORB。通常算法中都會選用10度到12度作為偏移區(qū)間,因此,SIFT主方向計算方法更能滿足該文的主方向計算需求。SIFT與OPoBRIEF的對比結(jié)果如圖7所示,表明OPoBRIEF的旋轉(zhuǎn)不變性不亞于SIFT特征描述子的效果。

表2 不同旋轉(zhuǎn)度的匹配率

圖7 OPoBRIEF與SIFT特征描述子旋轉(zhuǎn)不變性比較

3.3 實驗結(jié)果

在上述穩(wěn)定性實驗中,選擇采樣點數(shù)量越多,描述子包含的信息量越多,匹配的正確性也相應(yīng)越高,說明OPoBRIEF比BRIEF的整體匹配效果好。在測試描述子對旋轉(zhuǎn)不變性的實驗中,描述子OPoBRIEF的匹配效果也好于BRIEF描述子,對于SIFT特征描述子來說,OPoBRIEF的旋轉(zhuǎn)不變性更加穩(wěn)定。

4 結(jié)束語

對二值描述子BRIEF進(jìn)行了改進(jìn),引入了更多的對比對來加強特征描述子的信息包含量,并引入了灰度值的序排序,提出了一種改進(jìn)的描述子OPoBRIEF。與BRIEF描述子相比,OPoBRIEF需要增加的計算開銷很少,適合移動與實時計算環(huán)境;選擇三采樣點(OPoB-3)和四采樣點(OPoB-4)進(jìn)行了實驗,結(jié)果表明提出的描述子穩(wěn)定性更好;進(jìn)一步的實驗還證明,采用Kendall's tau距離進(jìn)行描述子匹配時,該方法的匹配效果更好。