基于積分圖的LATCH算法改進①

陳方飛,馮 瑞

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

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

基于積分圖的LATCH算法改進①

陳方飛1,馮 瑞2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 LATCH算法

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

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

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

1.1 三像素塊比較

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

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

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

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

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

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

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

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

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

和值越高,效果越好.

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

2 LATCH算法改進

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

2.1 積分圖算法

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

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

圖1 積分原理圖

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

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

2.2 基于積分圖的LATCH算法改進

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

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

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

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

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

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

圖2 像素帶分布

3 實驗結(jié)果

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

3.1 實驗評估指標(biāo)

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

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

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

%95錯誤率(%95 Error Rate):正匹配率為95%時的負匹配率,如式(14)所示:

3.2 參數(shù)分析

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

1)描述子長度分析

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

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

2)像素塊大小分析

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

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

3.3 實驗結(jié)果對比

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

(1)運行效率

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

表1 運行效率對比

2)準(zhǔn)確度

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

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

4 結(jié)語

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

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黃文杰,陳斌.一種快速圖像處理的積分圖方法.計算機應(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

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

2016-08-08;收到修改稿時間:2016-09-18

10.15888/j.cnki.csa.005716