基于積分圖的LATCH算法改進(jìn)①

陳方飛,馮 瑞

1(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 201210)

2(上海視頻技術(shù)與系統(tǒng)工程研究中心,上海 201210)

基于積分圖的LATCH算法改進(jìn)①

陳方飛1,馮 瑞2

1(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 201210)

2(上海視頻技術(shù)與系統(tǒng)工程研究中心,上海 201210)

LATCH(基于機(jī)器學(xué)習(xí)的三像素塊描述子)在原有局部二值描述子的基礎(chǔ)上通過將二像素塊比較改為三像素塊提升了局部二值描述子的準(zhǔn)確率,但提高準(zhǔn)確率的同時(shí)帶來了更大的時(shí)耗,在研究LATCH以及其他二值描述子的基礎(chǔ)上,借鑒積分圖在目標(biāo)檢測中的應(yīng)用,將積分圖的思想應(yīng)用在改進(jìn)LATCH描述子中,減少了LATCH描述子中各像素塊內(nèi)的重復(fù)計(jì)算量.實(shí)驗(yàn)證明,改進(jìn)算法的描述子計(jì)算時(shí)間較原算法縮減了30%–40%,而配準(zhǔn)精度與原算法保持相近.

局部二值描述子;LATCH;像素塊;積分圖

圖像局部視覺特征信息的有效表示在許多計(jì)算機(jī)視覺應(yīng)用中都是至關(guān)重要的,如圖像索引,需要從查詢庫中進(jìn)行大量局部特征提取與計(jì)算而定位與查詢項(xiàng)匹配度最高的圖像.因此計(jì)算機(jī)視覺領(lǐng)域研究中有很大部分關(guān)注于如何確定局部信息描述子或如何提升已有描述子的精度與效率.經(jīng)過多年的研究與發(fā)展,圖像局部信息描述子形成了兩大主流研究方向:基于分布的描述子與二值描述子.

基于分布的描述子主要描述特征表征量(如梯度,梯度方向等)的圖像分布信息,其中突出的描述子有HOG[1],SIFT[2]描述子,SIFT描述子通過計(jì)算特征局部區(qū)域梯度方向分布表征特征點(diǎn)局部視覺信息.基于分布的描述子在特征描述的準(zhǔn)確度有顯著效果,但隨著精度不斷增加,計(jì)算時(shí)耗與內(nèi)存開銷也在不斷增加.

近年來,由于計(jì)算機(jī)視覺應(yīng)用中圖像數(shù)據(jù)庫容量急劇上升,圖像分辨率增大.對特征描述子的計(jì)算時(shí)耗需求觸動(dòng)了二值描述子的逐漸發(fā)展.二值特征描述子比較像素塊之間的值得到一個(gè)二進(jìn)制串,二進(jìn)制串可以直接通過計(jì)算哈明碼距離進(jìn)行匹配,極大提高了運(yùn)算速度.其中突出的描述子有BRIEF[3],ORB[4]以及FREAK[5].

傳統(tǒng)二值描述子提高速度的同時(shí)帶來了匹配準(zhǔn)確度的下降,2015年 Gil Levi與 Tal Hassner提出了LATCH[6]算法,并且以加入OpenCV函數(shù)庫中,在傳統(tǒng)二值描述子的基礎(chǔ)上,針對匹配準(zhǔn)確度,從以下兩方面進(jìn)行了改進(jìn):

① 三像素塊比較代替兩像素比較

② 像素塊位置通過機(jī)器學(xué)習(xí)選出最優(yōu)位置組合

LATCH算法在準(zhǔn)確度上提升了,但三像素塊帶來更大的計(jì)算量.通過深層研究發(fā)現(xiàn),LATCH中主要時(shí)間消耗在每次對每像素塊進(jìn)行遍歷計(jì)算中.

參照文獻(xiàn)[7]中,通過積分圖消除重復(fù)運(yùn)算的方法,本文對LATCH算法進(jìn)行如下改進(jìn)

① 修改像素塊比較公式,適應(yīng)積分圖計(jì)算

② 應(yīng)用積分圖計(jì)算局部特征描述子

實(shí)驗(yàn)證明,改進(jìn)算法的描述子計(jì)算時(shí)間較原算法縮減了30%～40%,而配準(zhǔn)精度與原算法保持相近.

1 LATCH算法

LATCH前二值特征描述子比較以特征點(diǎn)K為中心檢測窗口W內(nèi)特定像素對比較的結(jié)果.設(shè)檢測窗口W內(nèi)T對有序樣本坐標(biāo)集如式(1)所示:

通過如下公式(2)可以求出每個(gè)像素對比較的二值結(jié)果:

比較窗口內(nèi)所有像素對,形成該特征點(diǎn)處二進(jìn)制串,可以描述該關(guān)鍵點(diǎn)特征.由于是單像素間的比較,容易受噪聲影響.LATCH在此基礎(chǔ)上提出了三像素塊之間的比較計(jì)算得到比特串,增強(qiáng)抗噪能力.

1.1 三像素塊比較

單像素間的比較,容易受噪聲影響,部分研究通高斯平滑消除噪聲影響,但消除噪聲也將造成關(guān)鍵點(diǎn)處信息丟失.Gil Levi與Tal Hassner提出通過三像素塊的比較解決噪聲的影響并提升匹配精度.

在每個(gè)檢測窗口W內(nèi)定義了T組三像素塊,窗口內(nèi)像素塊集如式(3):

每個(gè)像素塊定義為 像素塊,上述表達(dá)式中每個(gè)像素塊坐標(biāo)k×k為像素塊中心點(diǎn)坐標(biāo).通過式4評估錨點(diǎn)像素塊為像素塊中心點(diǎn)坐標(biāo).通過式4評估錨點(diǎn)像素塊與兩個(gè)對比像素塊與之間的相似度作為一個(gè)該特征點(diǎn)的一個(gè)比位.

1.2 基于學(xué)習(xí)的像素塊組合

每個(gè)檢測窗口中三像素塊位置組合數(shù)規(guī)模龐大,一個(gè)49×49檢測窗口,假定像素塊大小為7×7,三像素塊位置組合數(shù)規(guī)模在億的數(shù)量級.而特征描述計(jì)算過程中用到的三像素塊組合是有限的,如何在規(guī)模龐大的數(shù)據(jù)組合中選出有限的組合,使匹配效果達(dá)到最優(yōu)是一個(gè)重要問題.Gil Levi與Tal Hassner提出了基于機(jī)器學(xué)習(xí)確定較優(yōu)組合的方法.

1.2.1 學(xué)習(xí)數(shù)據(jù)集

學(xué)習(xí)數(shù)據(jù)集是建立在文獻(xiàn)[8]所提供據(jù)集,數(shù)據(jù)集包括:Liberty,Notre Dame以及Yosemite三個(gè)獨(dú)立數(shù)據(jù)集,每個(gè)數(shù)據(jù)集包括約20萬個(gè) 局部圖像窗體,窗體是從不同角度拍攝,并在文本文件中標(biāo)注各個(gè)局部圖像窗體是否相同(整個(gè)圖像是對場景的3D拍攝場景,通過Harris提取算法提取出不同場景點(diǎn)的局部窗口,同一場景點(diǎn)的不同拍攝角度具有相同索引號,即為相同).LATCH中使用了其中20萬個(gè)局部窗體塊,其中一半窗體為相同的,另一半為不同.

1.2.2 學(xué)習(xí)算法

LATCH學(xué)習(xí)算法的基本思想是通過對大量組合進(jìn)行匹配結(jié)果比較,篩選出較優(yōu)組合.首先通過隨機(jī)算法產(chǎn)生5萬6千個(gè)三像素塊組合.以每個(gè)像素塊組合匹配所有局部窗體結(jié)果,每個(gè)組合方案根據(jù)其匹配結(jié)果與標(biāo)注結(jié)果比較可以產(chǎn)生一個(gè) 大小的比特串(其中1表示匹配結(jié)果與標(biāo)注結(jié)果一致,0為不一致).評估每個(gè)組合方案好壞可以通過計(jì)算每個(gè)比特串的和,即公式(5):

和值越高,效果越好.

但單純這種選擇選擇結(jié)過可能導(dǎo)致相關(guān)性強(qiáng)的幾個(gè)組合方案同時(shí)被選擇,為避免該情況需要對每個(gè)待選擇組合方案與所有已選中組合方案進(jìn)行相關(guān)性計(jì)算,只有相關(guān)性小于一定閾值才可被選中,相關(guān)性的計(jì)算可以通過計(jì)算各比特串間漢明碼確定.

2 LATCH算法改進(jìn)

LATCH以像素塊取代像素點(diǎn)的計(jì)算,提升了準(zhǔn)確度,而由于需要對每個(gè)像素塊遍歷計(jì)算,增加了運(yùn)算量.本文在研究LATCH算法與積分圖算法的基礎(chǔ)上,在保持整體不變的情況下,通過改進(jìn)LATCH算法計(jì)算公式以適應(yīng)積分圖運(yùn)算.減少了計(jì)算量,同時(shí)也保證了準(zhǔn)確度.

2.1 積分圖算法

積分圖最早是由Paul Viola[9]等人提出的,并被應(yīng)用到實(shí)時(shí)的目標(biāo)檢測框架中.是能夠計(jì)算矩形塊特征的快速有效方法.積分圖中每個(gè)像素位置(x,y)的值不同于簡單灰度,或彩色圖存儲(chǔ)的是像素值,而是從原點(diǎn)到(x,y)包含區(qū)域所有像素點(diǎn)的和,其表達(dá)式如公式(6):

任意矩形區(qū)域 像素和如圖1所示.

圖1 積分原理圖

所以,利用積分圖計(jì)算矩形區(qū)域特征如公式(8)所示:

根據(jù)公式,如下代碼代碼段1是積分圖計(jì)算偽碼:

2.2 基于積分圖的LATCH算法改進(jìn)

由3.1可知,積分圖在處理矩形區(qū)域和特征計(jì)算能夠非常有效,而LATCH算法中超過95%計(jì)算量在每像素塊之間的計(jì)算中.如果能將積分圖算法引用到LATCH中像素塊計(jì)算中,可以提高LATCH算法計(jì)算效率.

由式(4)LATCH像素塊比較計(jì)算式可知,像素塊計(jì)算式對像素塊對中每個(gè)對應(yīng)像素進(jìn)行求差的絕對值再求和.因此不利于積分圖計(jì)算的開展.而如果只求差,不求絕對值,再求和,如式(9):

對上式進(jìn)行變換,可得到公式(10):

由上式可知以及積分圖算法原理可知,該計(jì)算式可以通過積分圖算法提升計(jì)算效率.如下代碼段2是改進(jìn)LATCH偽代碼.

2.3 區(qū)域分布特異化

由式(9)可知,改進(jìn)的LATCH算法中像素塊比較公式,所體現(xiàn)的是整個(gè)像素塊特征,不能在像素塊區(qū)域內(nèi)體現(xiàn)區(qū)域分布特征.而特征描述中,區(qū)域分布同樣是表示特征的非常重要信息.因此為了在像素塊內(nèi)同時(shí)體現(xiàn)區(qū)域信息,對像素塊內(nèi)不同像素帶賦予不同權(quán)值.其像素帶分布如圖2所示,根據(jù)不同像素帶,確定不同權(quán)值如公式(11)所示:

圖2 像素帶分布

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

本文實(shí)驗(yàn)平臺為Windows 7,處理器型號是Intel Core i5-3470,內(nèi)存大小為4GB,程序采用C++語言編程,通過調(diào)用OpenCV 3.0對圖像進(jìn)行基本操作.實(shí)驗(yàn)數(shù)據(jù)集如2.2.1描述數(shù)據(jù)集,該數(shù)據(jù)集共有約60萬個(gè)圖像窗口,使用其中20萬個(gè)圖像窗口進(jìn)行學(xué)習(xí)訓(xùn)練得到三像素塊位置,剩余40萬作為驗(yàn)證實(shí)驗(yàn)數(shù)據(jù)集.

3.1 實(shí)驗(yàn)評估指標(biāo)

實(shí)驗(yàn)采用文獻(xiàn)[10]中局部描述子方法對實(shí)驗(yàn)結(jié)果進(jìn)行評估,即基于正匹配率對負(fù)匹配率的ROC值得評估方法.其中:

正匹配率(True Positive Rate):指正確匹配的樣本數(shù)量與可能匹配的樣本比值,如式(12):

負(fù)匹配率(False Positive Rate):指在描述子數(shù)據(jù)集中被錯(cuò)誤地匹配的概率,如式(13):

%95錯(cuò)誤率(%95 Error Rate):正匹配率為95%時(shí)的負(fù)匹配率,如式(14)所示:

3.2 參數(shù)分析

本文所述描述子主要受兩個(gè)參數(shù)影響:每個(gè)特征點(diǎn)描述子字節(jié)長度,以及像素塊大小,下面將對兩個(gè)影響因子分別分析.

1)描述子長度分析

描述子長度是指每個(gè)特征形成的描述特征信息的二進(jìn)制位數(shù),本文分別對長度為8字節(jié)、16子節(jié)、32字節(jié)以及64字節(jié)進(jìn)行試驗(yàn),圖3是各個(gè)字節(jié)長度ROC曲線.由圖3可知,隨著字節(jié)長度增大,效果越好,64字節(jié)長度雖然比32字節(jié)整體效果好,但相差沒有特別明顯,而且64字節(jié)長度將大大提升描述子計(jì)算及匹配時(shí)間,因此本文采用32字節(jié)作為推薦描述子長度.

圖3 描述子長度對比結(jié)果

2)像素塊大小分析

影響描述子表示特征信息能力的另一個(gè)因子是像素塊大小.本文分別以5×5、7×7、9×9、11×11像素塊大小進(jìn)行比較試驗(yàn),圖4是各個(gè)尺寸ROC曲線,由圖可知,隨著尺寸增大,描述子表示特征信息效果越好,但當(dāng)增大一定尺寸后,效果開始變差,這是由于像素塊尺寸過大,將導(dǎo)致描述子各位間區(qū)分度下降.從而使描述子整體準(zhǔn)確度降低.

圖4 像素塊尺寸對比結(jié)果

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

本文主要針對LATCH算法在運(yùn)行效率上的不足進(jìn)行改進(jìn),因此本文主要與LATCH算法實(shí)驗(yàn)結(jié)果進(jìn)行比較.定量比較改進(jìn)算法與原算法在描述在計(jì)算效率以及表示特征信息準(zhǔn)確度兩方面效果.

(1)運(yùn)行效率

運(yùn)行效率的比較首先通過ORB算法對720P圖像特征點(diǎn)計(jì)算,再計(jì)算原算法與改進(jìn)算法對整副圖像描述子計(jì)算耗時(shí),本文對10幅圖像進(jìn)行試驗(yàn),最終計(jì)算對每個(gè)特征點(diǎn)描述子計(jì)算平均耗時(shí),結(jié)果如表1所示,由表可知,改進(jìn)算法相對原算法計(jì)算耗時(shí)極大減少.

表1 運(yùn)行效率對比

2)準(zhǔn)確度

為定量分析改進(jìn)算法與原算法間的準(zhǔn)確度差別,本文在原算法與改進(jìn)算法ROC曲線基礎(chǔ)上,分別計(jì)算AUC值,ACC值以及95Err值進(jìn)行比較.下表2,是計(jì)算中對比結(jié)果,由表可知,改進(jìn)算法在準(zhǔn)確度上與原算法幾乎一致.

表2 準(zhǔn)確度對比

4 結(jié)語

本文在研究LATCH算法的基礎(chǔ)上,提出了通過改進(jìn)比較公式,引用積分圖算法,減少算法在像素塊內(nèi)的計(jì)算時(shí)間,實(shí)驗(yàn)表明本文在幾乎不影響精確度的情況下,極大地減少了運(yùn)算時(shí)間,提高運(yùn)行效率.本文主要有兩個(gè)貢獻(xiàn)點(diǎn):(1)系統(tǒng)介紹了LATCH算法原理(2)提出了基于積分圖思想的LATCH算法改進(jìn),改進(jìn)了LATCH算法中像素塊間比較公式以適應(yīng)與LATCH算法,并對改進(jìn)算法與原算法進(jìn)行定量分析.

1 Dalal N,Triggs B.Histograms of oriented gradients for human detection.CVPR.San Diego,CA,USA.2005,1. 886–893.

2 Lowe DG.Distinctive image features from scale-invariant keypoints.IJCV,2004,60(2):91–110.

3 Leutenegger S,Chli M,Siegwart RY.Brisk:Binary robust invariantscalablekeypoints.ICCV,Barcelona.2011.2548–2555.

4 Yang X,Cheng KT.Ldb:An ultra-fast feature for scalable augmented reality on mobiledevices.In Mixed and Augmented Reality(ISMAR).2012.49–57.

5Alahi A,Ortiz R,Vandergheynst P.Freak:Fast retina keypoint. CVPR.Providence,USA.2012.510–517.

6 Levi G,Hassner T.LATCH:Learned arrangements of three patch codes.Winter Conference on Applications of Computer Vision(WACV).Lack Placid.2016.1–9.

7黃文杰,陳斌.一種快速圖像處理的積分圖方法.計(jì)算機(jī)應(yīng)用,2005,25(S1):266–269.

8 Brown M,Hua G,Winder S.Discriminative learning of local image descriptors.PAMI IEEE,2011,33(1):43–57.

9 Viola P,Jones M.Rapid object detection using a boosted cascade of simple features.CVPR.USA.2001,1.511–518.

10 Mikolajczyk K,Schmid C.A performance evaluation of local descriptors.PAMI IEEE,2005,27(10):1615–1630.

Improved LATCH Based on Integral Image

CHEN Fang-Fei1,FENG Rui2

1(School of Computer Science,Fudan University,Shanghai 201210,China)
2(Shanghai Engineering Research Center for Video Technology and System,Shanghai 201210,China)

LATCH(Learned Arrangements of Three Patch Codes)improves the accuracy of local binary descriptor by comparing three pixel blocks rather than tow pixel blocks.However,the improvement of accuracy brings a larger time consuming.Based on the study of LATCH and other local binary descriptors,using integral graph theory in improved LATCH descriptor,it reduces repeated calculation of each pixel blocks in LATCH descriptors.According to the experiment results,the computation time of the improved algorithm is reduced by 30%–40%compared with the original algorithms,while the accuracy of the improved algorithm is similar to that of the original algorithm.

local binary descriptor;LATCH;patch;integral image

國家科技支撐計(jì)劃(2013BAH09F01);上海市科委科技創(chuàng)新行動(dòng)計(jì)劃(14511106900);基于BIM+GIS城市大數(shù)據(jù)計(jì)算平臺的智慧臨港應(yīng)用示范(ZN2016020103)

2016-08-08;收到修改稿時(shí)間:2016-09-18

10.15888/j.cnki.csa.005716