SURF中快速求取積分圖像的直接替換算法*

韓 冰,孫繼銀

(第二炮兵工程學(xué)院,西安 710025)

0 引言

SURF(speed up robust features)[1-3]算法 ,是目前效率最高的局部區(qū)域特征提取和描述算法,非常適用于目標(biāo)識別和目標(biāo)跟蹤等對實時性要求較高的軍事領(lǐng)域。SURF的高性能與積分圖像(integral image)的使用密切相關(guān)。積分圖像最早由 Crow[4]于1984年提出,用于求取圖像的紋理映射。后又被應(yīng)用于灰度圖像匹配[5-6]、人臉識別[7]和目標(biāo)識別[8-9]。凡是使用過積分圖像的算法,在執(zhí)行速度上都會得到明顯的提升,這是由于它在計算一定矩形區(qū)域內(nèi)灰度值和時,只需3個簡單加減運算即可完成,能夠大大提高算法效率。

積分圖像的求取過程是SURF算法的第1步,因此其計算速度和內(nèi)存占用都會對SURF的整體性能提升造成一定影響。目前已有的快速求取積分圖像的算法有兩種,一是由Lewis[5]于1995年提出(以下簡稱 Lewis算法),二是由Viola[7]于2001年提出(以下簡稱Viola算法)。其中Viola算法也是SURF中所使用的算法[1-3,10]。由于其在執(zhí)行過程中,共需占用3個圖像空間,因而內(nèi)存消耗過大,而且過多內(nèi)存占用,會使圖像空間之間的查址調(diào)用過程消耗過多的時間,使得算法速度變慢。

因此,文中從降低內(nèi)存消耗和時間花費的角度出發(fā),對已有Viola和Lewis算法分別進(jìn)行改進(jìn),結(jié)合SURF算法過程只使用積分圖像而不使用原圖像的特點,提出了兩種只占用1個圖像空間的快速積分圖像求取算法——直接替換算法I和II(direct replacement algorithm I and II)。經(jīng)理論分析和實驗驗證,這兩種直接替換算法在執(zhí)行時不僅大大降低了內(nèi)存消耗,而且其時間花費均明顯少于Viola和Lewis算法。

1 Lewis和Viola算法

積分圖像的定義是:圖像中任意一點(i,j)的值ii(i,j),表示原圖像相應(yīng)灰色區(qū)域灰度值和,如圖1和式(1)所示。

圖1 積分圖像的定義

式中:p表示原圖像,p(i′,j′)表示原圖像中像素點(i′,j′)的灰度值 。

如果直接利用式(1)求取積分圖像,1個像素會被遍歷很多次,算法效率很低,速度很慢。而 Lewis和Viola算法卻只需對圖像像素遍歷一遍,速度較快,因此下面將詳細(xì)分析比較這兩種快速的積分圖像求取算法。

1.1 Lewis算法

1995年,為了快速計算歸一化積相關(guān)系數(shù),Lewis提出了一種快速的積分圖像求取算法,如式(2)[8-9]所示。

式中:ii(i-1,j)、ii(i,j-1)和ii(i-1,j-1)表示與(i,j)相鄰的3個已知像素積分值,p(i,j)為原圖像(i,j)位置的像素值。

1.2 Viola算法

2001年,Viola在其人臉識別算法中也提出一種快速求取積分圖像的算法[10-12],如式(3)、式(4)所示:

其中,S(i,j)表示圖像某一行的列積分值,且S(i,-1)=0,ii(-1,j)=0。

1.3 Lewis與Viola算法比較

這里將從內(nèi)存消耗和時間花費兩個方面對Lewis和Viola算法進(jìn)行比較。

1)在內(nèi)存消耗上,如式(3)、式(4)所示,Viola算法需要分配3個圖像大小的空間給S、p和ii,內(nèi)存占用率過高,這在某些內(nèi)存只有幾MB或幾十MB的嵌入式系統(tǒng)中,消耗過大;相對而言,Lewis算法只需分配2個圖像空間給p和ii,如式(2)所示,因此內(nèi)存消耗較低。

2)Viola算法計算一個像素積分值只需兩個加法運算,而Lewis算法計算一個積分值卻需要3個加減運算。因此,理論上Viola算法的速度應(yīng)當(dāng)快于Lewis算法。但是實際中,由于Viola算法占用的內(nèi)存大,其花費在CPU和內(nèi)存I/O傳輸?shù)臅r間就要比Lewis多,因為Viola計算一個像素積分值時需要在3個圖像之間進(jìn)行查址調(diào)用,而Lewis只需在2個圖像之間進(jìn)行查址調(diào)用。所以,實際計算中,Viola算法的運算速度要比Lewis算法慢,如圖2所示。

由圖2可以看出,Viola算法的速度確實較慢,其計算一個積分值只需2步加減運算的優(yōu)勢并未發(fā)揮出來,而是被在3個圖像之間中進(jìn)行查址調(diào)用所占用的時間給掩蓋了。因而可以說明對于積分圖像求取算法而言,占用圖像空間越多,其時間花費也就越多。

圖2 Lewis和Viola算法的時間花費比較

2 直接替換算法

積分圖像的求取是SURF算法的第1步,因此其執(zhí)行速度的快慢會對SURF算法的整體性能產(chǎn)生一定的影響。圖3給出了SURF算法的執(zhí)行流程?？梢钥闯?圖中除步驟①需要使用原圖像外,其余②～⑥步均未用到原圖像,其中②、⑤、⑥步使用的是積分圖像,③、④步?jīng)]有用到任何圖像,只用到了之前步驟中求出的det(Hessian)尺度空間。因此對于SURF算法,原圖像只被用于積分圖像的計算。

圖3 SURF算法的執(zhí)行流程

如果在計算積分圖像時直接用積分值來替換原圖像中的像素值,不僅可以達(dá)到節(jié)約內(nèi)存的目的,而且無需在圖像之間進(jìn)行像素值的查址調(diào)用,從而可以提升算法速度。因此文中從降低內(nèi)存消耗和減少時間花費的角度出發(fā),提出了兩種適合SURF使用,并只需占用1個圖像空間的快速求取積分圖像的直接替換算法。

2.1 直接替換算法I

第一種直接替換算法是對原Lewis算法的改進(jìn),其詳細(xì)執(zhí)行過程如圖4所示。

圖4 直接替換法I的算法過程

假設(shè)原圖像大小為 H×W(高H,寬 W),則積分圖像的求取步驟為:

Step 1 計算第0行,第 1至第(W-1)列的積分圖像像素值,如式(5)所示。

Step2 計算第0列,第1至第(H-1)行的積分圖像像素值,如式(6)所示。

Step3 計算第1至第(H-1)行,第1至第(W-1)列的積分圖像像素值,如式(7)所示。

在直接替換法I的執(zhí)行過程中,直接使用積分值代替了原像素值,因而整個過程只占用了1個圖像空間。另外,CPU只需要針對1個圖像空間做讀寫操作,而不用像Lewis那樣在2個不同的圖像空間中進(jìn)行尋址、讀取和寫入操作,因而花費在I/O傳輸上的時間較少,所以速度也有所提升。

2.2 直接替換算法II

圖5 直接替換算法II的算法過程

第二種直接替換算法是對原Viola算法的改進(jìn),其詳細(xì)的執(zhí)行步驟如圖5所示。假設(shè)原圖像大小為 H×W(高 H,寬W),則積分圖像的求取步驟為:

Step1 首先定義一個變量s,并將原圖像 p中(0,0)處的像素值賦給它,如式(8)所示。

Step2 計算第0行,第1至第(W-1)列的積分圖像像素值,如式(9)和式(10)所示。

Step3 計算第1至第(H-1)行,第0至第(W-1)列的積分圖像像素值。

首先計算第i行,第0列的積分圖像像素值,如式(11)和式(12)所示。然后計算第i行,第1至第(W-1)列的積分圖像像素值,如式(13)和式(14)所示。

直接替換算法II將原Viola算法中用于存儲列積分值的中間圖像S,簡化為用一個變量s來代替,然后再用計算得到的圖像積分值直接替換原像素值,因此整個過程也只占用1個圖像空間即可完成。

2.3 兩種直接替換算法的比較

下面將在內(nèi)存消耗和算法執(zhí)行速度方面對以上兩種直接替換算法進(jìn)行比較。

1)兩種算法的內(nèi)存消耗基本相同,只是從過程上來看,由于直接替換算法II要比算法I多引入了一個變量s,因此直接替換算法II比算法I要多消耗至少4個字節(jié)的內(nèi)存。

2)從算法速度上看,將式(7)與式(13)、式(14)進(jìn)行對照可以看出,直接替換算法II求取一個積分值時只需要2個加減運算即可完成,直接替換算法I則需要3個加減運算。因此在一般的串行流程下,直接替換算法II的運行速度要快于直接替換算法I。然而,如果在有并行運算能力的硬件環(huán)境下,直接替換算法I可以通過并行技術(shù)進(jìn)行加速,加速后的直接替換算法I能夠獲得快于直接替換算法II串行執(zhí)行時的速度。具體分析如下。

圖6 直接替換算法I的并行執(zhí)行

對于直接替換算法I來說,式(7)中圖像坐標(biāo)(i-1,j)和(i,j-1)處的積分值在求取過程中只有一個同時依賴的元素,即坐標(biāo)(i-1,j-1)處的積分值,只要(i-1,j-1)處的像素積分值求出之后,在并行條件下,(i-1,j)和(i,j-1)處的像素積分值就可以同時求出,因此,同樣計算4個相鄰坐標(biāo)處的像素積分值,串行條件下,需要4步才能完成,并行條件下只需3步即可實現(xiàn),如圖6所示。

依據(jù)以上思想,可以將直接替換算法I在并行條件下的執(zhí)行步驟改進(jìn)如下。具體過程如圖7所示。

Step1 按照式(5)計算第0行,第 1至第(W-1)列的積分圖像像素值。

Step2 按照式(6)計算第0列,第 1至第(H-1)行的積分圖像像素值。

Step3 按照式(7)求取第1至第(H-1)行,第1至第(W-1)列的積分值,求取過程執(zhí)行并行計算,每次同時計算兩行的積分值。

對于直接替換算法II而言,其算法過程不容易進(jìn)行并行實現(xiàn),這是因為在計算積分值時,直接替換算法II必須依賴存儲列積分值的變量s,只有先計算出s的值才能算出每個積分值,而且s的值在計算每一個積分值時都需要不斷更新,因此在并行條件下,利用直接替換算法II計算整個積分圖像時,只能進(jìn)行串行條件下的逐行運算,實現(xiàn)同時求取幾個像素積分值的并行運算不太容易。

因此如果計算圖7中2行共12個像素的積分值,直接替換法II共需要執(zhí)行24個加法運算,直接替換算法I逐像素求取時需要執(zhí)行36個加減運算,而在并行求取時,相當(dāng)于只需要執(zhí)行3+3×4+3=18個加減運算即可完成,因此經(jīng)過并行加速后的直接替換算法I比直接替換算法II的執(zhí)行速度要快。

圖7 基于直接替換算法I的積分圖像并行求取

3 實驗分析與驗證

3.1 實驗環(huán)境

文中在CPU為Genuine Intel(R)T2400 Core Duo,主頻 1.83GHZ,內(nèi)存1G的PC機(jī)實驗環(huán)境下,在Visual Studio 2008中,使用C#語言編程實現(xiàn)了求取積分圖像的Viola算法、Lewis算法和文中提出的直接替換算法I和II,并對它們的內(nèi)存消耗和時間花費進(jìn)行了實驗測試。實驗用圖來自http://www.robots.ox.au.uk/～vgg提供的Graffiti圖像,將其進(jìn)行裁剪后得到如圖8所示的測試圖。實驗時對該圖像進(jìn)行縮放變換,依次選取分辨率為128×128～1024×1024的圖像序列進(jìn)行測試,其圖像間的像素增長間隔為128。

3.2 內(nèi)存占用分析和測試

3.2.1 圖像空間的定義及其內(nèi)存占用分析

這里將一幅圖像所占用的內(nèi)存定義為一個圖像空間。圖像空間所占用的內(nèi)存大小與其自身像素值的存儲格式密切相關(guān)。

對于未處理過的原圖像,一般為灰度圖像,其像素值最大為255,由于256=28,因此原圖像一般采用字節(jié)型或8位整型數(shù)來存儲單個像素。相對而言,積分圖像中的每一個像素值代表了原圖像一定區(qū)域的像素值和,如果假設(shè)原圖像尺寸為256×256,考慮其中所有像素灰度值都為255的極限情況,那么積分圖像最右下角的像素值就為:28×28×28=224。這時如果還簡單的使用字節(jié)型或8位整型數(shù)來存儲單個像素,就會造成數(shù)據(jù)丟失的錯誤,這時應(yīng)使用32位(4字節(jié))的整型或浮點型。更進(jìn)一步分析,假設(shè)原始圖像尺寸為8192×8192,同樣也考慮原圖像所有像素灰度值都為255的極限情況,那么積分圖像右下角的像素值就為:213×213×28=234。在這種情況下,32位的整型或浮點型數(shù)也無法存儲單個像素,因此需要改用64位(8字節(jié))的長整型或雙浮點型數(shù)來存儲。

綜上所述,對于原圖像而言,其像素值的存儲格式與圖像尺寸無關(guān),采用字節(jié)型或8位整型存儲即可,對于積分圖像而言,其像素值的存儲格式與圖像尺寸有關(guān),只要圖像長寬均不超過4096,就可使用32位的整型或浮點型來存儲,否則,要改用64位的長整型或雙浮點型。

3.2.2 四種算法內(nèi)存消耗比較與測試

假設(shè)原圖像的大小為H×W(H和W均小于4096)。

對于Viola算法,原圖像p占用的內(nèi)存空間為H×W字節(jié),中間圖像S和積分圖像ii分別占用4×H×W字節(jié),整個算法過程共占用至少9×H×W字節(jié)的內(nèi)存。

對于Lewis算法,原圖像p占用的內(nèi)存空間為H×W字節(jié),積分圖像ii占用4×H×W字節(jié),則整個算法過程需占用5×H×W字節(jié)的內(nèi)存。

對于直接替換算法I,由于存在像素值替換,因此在處理前,需要統(tǒng)一原圖像p與積分圖像ii像素值的數(shù)據(jù)類型,即全部采用32位的整型或浮點型數(shù)來存儲像素。這樣整個算法過程只需占用4×H×W字節(jié)的內(nèi)存空間即可完成。

對于直接替換算法II,需要引入變量s來代替原Voila算法中的圖像S,這里需要將s的存儲格式定義為32位的整型或浮點型數(shù)據(jù)。另外與直接替換法I相同,在處理前也需要將原圖像與積分圖像ii的像素值的類型統(tǒng)一為32位的整型或浮點型,因此該算法過程占用的內(nèi)存空間為4×H×W+4。

文中分別對Viola算法、Lewis算法和文中的直接替換算法I和II在運行過程中實際內(nèi)存消耗進(jìn)行了測試,詳細(xì)的測試結(jié)果如表1所示。

表1 四種算法的內(nèi)存消耗對比,單位/byte

由表1可以看出,隨著原圖像尺寸的不斷增大,四種算法的內(nèi)存消耗都隨之增大。其中Viola算法的消耗最大、Lewis算法次之、直接替換算法I和II最小。并且隨著圖像尺寸的進(jìn)一步不斷增大,直接替換算法I和II節(jié)省內(nèi)存消耗的效果會更加明顯。對于直接替換算法I和II而言,兩者的內(nèi)存消耗差別不大,算法II只比I多消耗了4個字節(jié)內(nèi)存,從而也驗證了以上分析。

3.3 時間花費分析和測試

由1.3節(jié)分析可知 Viola與 Lewis算法相比,Lewis算法的速度較快。從2.3節(jié)的分析可以看出,在串行條件下,直接替換算法II的執(zhí)行速度要快于直接替換算法I,但是直接替換算法I可以利用并行加速的方法獲得比算法II還要快的速度。

對于直接替換算法I,式(7)中雖然也包含了3個加減法運算,但是它畢竟只占用1個圖像空間,整個過程CPU只需對p一個圖像空間進(jìn)行查址調(diào)用和讀寫操作,因此與Viola和Lewis算法相比,直接替換算法I的執(zhí)行速度應(yīng)該較快。

文中分別對Viola算法、Lewis算法、直接替換算法I和II執(zhí)行所花費的時間進(jìn)行了測試,由于文中測試的實驗環(huán)境是雙核CPU,因此也對直接替換算法I的并行加速部分進(jìn)行了編程實現(xiàn),并測試了它的時間花費,詳細(xì)的測試結(jié)果如表2所示。

表2 積分圖像求取算法的時間花費對比,單位/ms

由表2可以看出,隨著輸入原圖像尺寸的不斷增大,四種算法的時間花費也隨之增大,在串行執(zhí)行的條件下,時間花費最少的為直接替換算法II,其次為直接替換算法I,然后為Lewis算法,花費最高的為Viola算法,另外還可以看出,直接替換算法I經(jīng)并行加速后,速度比直接替換算法II要快,時間花費最少,從而也驗證了以上分析。

4 結(jié)束語

文中針對目前SURF中采用的積分圖像求取算法內(nèi)存消耗和時間花費過大問題,通過對Viola算法和Lewis算法分別進(jìn)行改進(jìn),并結(jié)合SURF算法只使用積分圖像而不使用原圖像的特點,提出了兩種只占用一個圖像空間的快速求取積分圖像的直接替換算法。經(jīng)過文中的理論分析和實驗結(jié)果驗證,得出了以下結(jié)論:

1)直接替換算法I和II的內(nèi)存消耗和時間花費均小于Viola和Lewis算法。隨著輸入圖像尺寸的不斷增大,其省時省內(nèi)存的效果會更加明顯。

2)在SURF算法中應(yīng)用時,由于直接替換算法II在串行執(zhí)行時的速度最快,因此適合在PC環(huán)境下使用。但是算法II不易進(jìn)行并行實現(xiàn),相對的,直接替換算法I則非常易于并行實現(xiàn),并且經(jīng)并行加速后的直接替換算法I速度要快于算法II,因此它適用于并行的硬件環(huán)境,如DSP等。

[1]Herbert Bay,Tinne Tuytelaars,Luc VanGool.SURF:Speeded up robust features[C]//ECCV 2006,Springer LNCS 3951(1),404-417,2006.

[2]Herbert Bay,Andreas Ess,Tinne Tuytelaars,et al.Speeded up robust features(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.

[3]Herbert Bay,Beat Fasel,Luc Van Gool.Interactive Museum guide:Fast and robust recognition of museum objects[C]//IMV,2006.

[4]Franklin C Crow.Summed-area tables for texture mapping[J].Computer Graphics,1984,18(3):207-212.

[5]J P Lewis.Fast template matching[C]//Vision Interface,1995:120-123.

[6]D M Tsai,C T Lin.Fast normalized cross correlation for detection[EB/OL].Online,Internet,available:http://machinevision.iem.yzu.edu.tw/english_version/tech/correlation2-FastNorma-lized.pdf.

[7]Viola P,Jones M.Robust real time face detection[C]//ICCV2001,2001:747-760.

[8]Viola P,Jones M.Rapid object detection using a boosted cascade of simple features[C]//CVPR2001,2001:511-518.

[9]Viola P,Jones M.Robust real-time object detection[C]//Second International Workshop on Statistical and computational Theories of Vision Modeling,Learning,Computing,and Sampling,2001:1-25.

[10]Christopher Evans.Notes on the OpenSURF Library[EB/OL],Online,Internet,available:http://www.chrisevansdev.com/.MSc Computer Science,University of Bristol,2010.