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

陳方飛,馮 瑞

1(復旦大學 計算機科學技術學院,上海 201210)

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

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

陳方飛1,馮 瑞2

1(復旦大學 計算機科學技術學院,上海 201210)

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

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

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

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

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

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

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

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

② 像素塊位置通過機器學習選出最優位置組合

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

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

① 修改像素塊比較公式,適應積分圖計算

② 應用積分圖計算局部特征描述子

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

1 LATCH算法

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

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

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

1.1 三像素塊比較

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

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

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

1.2 基于學習的像素塊組合

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

1.2.1 學習數據集

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

1.2.2 學習算法

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

和值越高,效果越好.

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

2 LATCH算法改進

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

2.1 積分圖算法

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

任意矩形區域 像素和如圖1所示.

圖1 積分原理圖

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

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

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

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

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

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

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

2.3 區域分布特異化

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

圖2 像素帶分布

3 實驗結果

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

3.1 實驗評估指標

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

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

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

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

3.2 參數分析

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

1)描述子長度分析

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

圖3 描述子長度對比結果

2)像素塊大小分析

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

圖4 像素塊尺寸對比結果

3.3 實驗結果對比

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

(1)運行效率

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

表1 運行效率對比

2)準確度

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

表2 準確度對比

4 結語

本文在研究LATCH算法的基礎上,提出了通過改進比較公式,引用積分圖算法,減少算法在像素塊內的計算時間,實驗表明本文在幾乎不影響精確度的情況下,極大地減少了運算時間,提高運行效率.本文主要有兩個貢獻點:(1)系統介紹了LATCH算法原理(2)提出了基于積分圖思想的LATCH算法改進,改進了LATCH算法中像素塊間比較公式以適應與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黃文杰,陳斌.一種快速圖像處理的積分圖方法.計算機應用,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);上海市科委科技創新行動計劃(14511106900);基于BIM+GIS城市大數據計算平臺的智慧臨港應用示范(ZN2016020103)

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

10.15888/j.cnki.csa.005716