張娓娓,趙金龍,何 佳,陳綏陽(yáng),2,王 杰

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

0 引 言

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

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

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

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

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

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

1.1 BRIEF描述子

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

(1)

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

(2)

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

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

1.2 ORB描述子

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

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

1.3 BRISK描述子

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

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

2 OPoBRIEF描述子

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

2.1 N維BRIEF描述子

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

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

(3)

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

(4)

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

(5)

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

通過(guò)計(jì)算得到的階排列來(lái)替換BRIEF描述子中的二值測(cè)試序列,則OPoBRIEF描述子對(duì)每個(gè)特征點(diǎn)的維度變化為nd×ns。顯然,ns值過(guò)大會(huì)造成階排列字串過(guò)于復(fù)雜,通常ns取值為3和4較為合適,兩者的階排列模式只有6和24,計(jì)算開(kāi)銷(xiāo)較小。

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

2.2 平滑核的選擇

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

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

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

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

2.3 階排列距離度量

Ziegler介紹了三種不同的高效的距離計(jì)算方法[17]:Hamming距離、Cayley距離和Kendall's tau距離。其中Kendall's tau距離已經(jīng)被證明在計(jì)算階排列的距離上要比其他兩種計(jì)算方法好,雖然它的計(jì)算復(fù)雜度為O(m2),高于漢明距離和Cayley距離的計(jì)算復(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 實(shí)驗(yàn)與結(jié)果

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

3.1 描述子穩(wěn)定性實(shí)驗(yàn)

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

圖6 圖像測(cè)試集示例

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

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

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

3.2 OPoBRIEF的旋轉(zhuǎn)不變性實(shí)驗(yàn)

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

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

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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