摘 要： 當(dāng)前，移動(dòng)設(shè)備的計(jì)算能力越來(lái)越強(qiáng),，但類似增強(qiáng)現(xiàn)實(shí)對(duì)實(shí)時(shí)性要求較高的應(yīng)用,，其性能還無(wú)法完全滿足需求。在增強(qiáng)現(xiàn)實(shí)應(yīng)用中,，提取特征點(diǎn)和特征點(diǎn)的匹配是關(guān)鍵,。主要關(guān)注特征點(diǎn)的提取，以SURF算法為例,，針對(duì)移動(dòng)設(shè)備較小的高速緩存容量不適應(yīng)原算法圖像數(shù)據(jù)訪問方式的問題,，提出了依據(jù)圖像內(nèi)容的自適應(yīng)分塊方法,。實(shí)驗(yàn)結(jié)果表明,，改進(jìn)后的算法在沒有犧牲精確度的情況下，速度提高了1.5～1.7倍,。
關(guān)鍵詞： 增強(qiáng)現(xiàn)實(shí),；特征點(diǎn)提取；SURF,；自適應(yīng)分塊
隨著技術(shù)的不斷進(jìn)步,，將增強(qiáng)現(xiàn)實(shí)技術(shù)移植到移動(dòng)設(shè)備上來(lái)，可以在更廣泛的領(lǐng)域得到應(yīng)用,。
增強(qiáng)現(xiàn)實(shí)AR(Augmented Reality)[1-3]是利用計(jì)算機(jī)生成一種逼真的視,、觸、聽,、動(dòng)等多種感覺的虛擬環(huán)境,，使用各種傳感設(shè)備讓用戶融合到該環(huán)境中，是以交互性和構(gòu)想為基本特征的計(jì)算機(jī)高級(jí)人機(jī)界面[4],。目前比較成功的案例有城市萬(wàn)花筒（City Lens）[5],、谷歌眼鏡（Google Class）[6]和游戲AR Zombie Invasion[7]。
在增強(qiáng)現(xiàn)實(shí)應(yīng)用中,，特征點(diǎn)提取和特征點(diǎn)匹配[2]是關(guān)鍵,。當(dāng)前，移動(dòng)平臺(tái)上存在的幾種輕量級(jí)特征點(diǎn)提取算法FAST(Features from Accelerated Segment Test)[8-9]和ORB算法[10]在光照不變性,、幾何不變性以及健壯性方面都不及SURF,。針對(duì)SURF算法,，國(guó)內(nèi)外也有很多成功的嘗試，比如TA D N等人[9]提出的SURFTrac算法和TERRIBERRY T B等人[8]提出的在GPU上使用OpenCL可更有效地實(shí)現(xiàn)SURF,。但這些方法都沒有得到很好的實(shí)際應(yīng)用,。
本文分析了SURF算法在移動(dòng)平臺(tái)上性能不高的一個(gè)重要原因：移動(dòng)設(shè)備較小的高速緩存容量不適應(yīng)原算法的圖像數(shù)據(jù)訪問方式，由此提出了依據(jù)圖像內(nèi)容的自適應(yīng)分塊方法,，以減少高速緩存中的沖突失效和有用信息的損失,，對(duì)算法速度的提高將會(huì)有很好的貢獻(xiàn)。
1 SURF算法與高速緩存的不匹配原因分析
在SURF算法中,，為了在不同尺度上尋找極值點(diǎn),，需要建立圖像的尺度空間。SURF在建立尺度空間時(shí),，保持原始圖像不變,，通過改變箱式濾波器的大小，對(duì)固定大小積分圖像進(jìn)行濾波得到圖像的尺度空間,。
可見,，SURF算法中，數(shù)據(jù)的訪問方式由箱式濾波器的大小和類型決定,。例如一個(gè)9×9的箱式濾波器在計(jì)算時(shí),，假設(shè)每一次迭代過程中需要訪問9×9區(qū)域內(nèi)的8個(gè)元素。如圖1所示,，設(shè)元素集合S={A,，B，C,，D,，E，F(xiàn),，G,，H}。在下一次迭代過程中,，箱式濾波器將向右移動(dòng)一個(gè)像素,，從而訪問集合S右邊的8個(gè)元素，即集合S′={A′,，B′,，C′，D′,，E′,，F(xiàn)′，G′,，H′},。
一個(gè)大小為9×9的箱式濾波器在對(duì)一個(gè)200×200的積分圖像計(jì)算時(shí),，將會(huì)導(dǎo)致多達(dá)80 000次的高速緩存未命中以及高速緩存的數(shù)據(jù)替換。實(shí)驗(yàn)證明,，這種自沖突失效所造成的影響將隨著箱式濾波器和積分圖像的變大而變得更為明顯,。
2 特征點(diǎn)提取算法改進(jìn)與實(shí)現(xiàn)
分塊的SURF算法將輸入圖像分割成規(guī)則的網(wǎng)格狀圖像塊，然后對(duì)每個(gè)圖像塊分別進(jìn)行生成積分圖,、尺度空間分析,、計(jì)算Hessian矩陣，最后對(duì)每個(gè)單獨(dú)圖像塊分別進(jìn)行特征點(diǎn)提取,。
對(duì)原圖像分塊后,，所得的圖像塊每行的數(shù)據(jù)量較原始圖像小，圖像數(shù)據(jù)則以基于行的方式存儲(chǔ)在高速緩存中,，箱式濾波器在與分塊后的積分圖像計(jì)算時(shí),，可以減少數(shù)據(jù)的重載入，從而可以減少?zèng)_突失效,。在第1節(jié)的例子中,，如果所選擇的圖像塊大小為24×41，則可以用8行,，每行24個(gè)元素來(lái)替換一行200個(gè)元素,。因此箱式濾波器的大小只要小于24×41，在計(jì)算過程中將不會(huì)產(chǎn)生自沖突失效,。
在分塊算法中,，只有選擇合適的分塊大小,，才能最大程度地減少內(nèi)存中的數(shù)據(jù)交換,，塊的大小選取往往根據(jù)平臺(tái)的不同以及圖像本身的不同而有所差異。COLEMAN S[11]提出了根據(jù)給定的高速緩存容量和高速緩存行的大小來(lái)進(jìn)行分塊大小的選取算法,。然而,，對(duì)于程序開發(fā)人員而言，可用的高速緩存的大小是無(wú)法預(yù)測(cè)的且往往比系統(tǒng)整個(gè)緩存要小,，顯然使用整個(gè)高速緩存的大小來(lái)確定分塊的大小是不合適的,。而通過實(shí)驗(yàn)來(lái)從所有可能的分塊中選擇合適的分塊也是一個(gè)不可取的方法。
另外,，不合適的分塊也會(huì)造成興趣點(diǎn)精度的下降,。圖4所示分別為原始SURF算法和簡(jiǎn)單分塊后的提點(diǎn)效果?？梢钥吹?，有部分點(diǎn)的缺失。這是由于在箱式濾波器與積分圖像卷積的過程中,，無(wú)法計(jì)算邊緣上的像素點(diǎn)所導(dǎo)致的,。
為了解決上述問題,，本文提出了依據(jù)圖像內(nèi)容的自適應(yīng)分塊方法。該方法主要思想是通過圖像熵的計(jì)算來(lái)確定最大連續(xù)區(qū)域,，從而確定不同內(nèi)容上分塊的大小,。
增加最大連續(xù)區(qū)域(Maximum Continuous Region)內(nèi)的任一子區(qū)域的大小，都可以提高子區(qū)域的熵的大小,，但是提高該區(qū)域的大小卻不能進(jìn)一步提高該區(qū)域的熵的大小,。為了減少確定最大連續(xù)區(qū)域的計(jì)算量，提供一個(gè)待選集合S,。該集合包含幾個(gè)不同大小的離散區(qū)域來(lái)作為可能的最大連續(xù)區(qū)域,，如：120×120、160×160,、160×240,、240×240和480×480。這些離散值將是使用分塊算法時(shí)對(duì)圖像分塊的依據(jù),。圖5為確定了所有最大連續(xù)區(qū)域后的圖像分塊,。
確定合適的最大連續(xù)區(qū)域步驟如下：
（1）選取集合S中的第一個(gè)待選區(qū)域96×96，計(jì)算該區(qū)域熵的大小,。如果計(jì)算的熵值非常小,，說明該區(qū)域包含的信息很少，因此可以忽略不計(jì),，該區(qū)域不參與后續(xù)的特征點(diǎn)的提取,，轉(zhuǎn)步驟（3）；
（2）擴(kuò)大計(jì)算區(qū)域?yàn)榧蟂中的下一個(gè)待選區(qū)域,，計(jì)算熵值,。若熵停止增加或已達(dá)到最大的待選分塊區(qū)域，確定所選的區(qū)域?yàn)樗鶎ふ业淖畲筮B續(xù)區(qū)域,，同時(shí)轉(zhuǎn)步驟（3）,，否則循環(huán)執(zhí)行步驟（2）；
（3）判斷是否存在無(wú)重疊的待劃分區(qū)域,。若有,，轉(zhuǎn)步驟（1），否則輸出所有的最大連續(xù)區(qū)域,。
依據(jù)內(nèi)容分塊選擇算法的偽代碼如下：
Initialize TSCs = {96*96, 96*120…}
for each tile
tile-size = 96x96
entropy = Entropy( tile-size)
if (entropy<ε)
continue
for T = 2:end
tile-sizenext = TSCs [T]
entropynext= Entropy( tile-sizenext )
if ( entropynext>entropy)
tile-size = tile-sizenext
entropy = entropynext
else
break
endif
end
end
輸入：TSCs 候選分塊組（如96×96,、96×120等）
輸出：MCRs最大連續(xù)區(qū)域（Maximum continuous Regions）
參數(shù)：tile-size為當(dāng)前待選分塊；tile-sizenext為下一待選分塊,；entropy為當(dāng)前分塊區(qū)域的熵,；entropynext為下一待選分塊區(qū)域熵。
圖6所示為依據(jù)內(nèi)容分塊后所提取的特征點(diǎn)與原始SURF算法的對(duì)比,。該實(shí)例顯示,，改進(jìn)的方法對(duì)于大塊的文本性內(nèi)容可以自動(dòng)地進(jìn)行較合理的分塊,，減少了信息的丟失，同時(shí)略去包含極少信息量的部分,，減少了后續(xù)計(jì)算,。
3 實(shí)驗(yàn)結(jié)果
本文的研究通過在OpenSURF環(huán)境中進(jìn)行仿真實(shí)驗(yàn)，基于OpenCV和C++,，將其移植到Android平臺(tái)上,。實(shí)驗(yàn)使用的智能手機(jī)為HTC G7，該手機(jī)參數(shù)為單核CPU,、一級(jí)緩存32 KB,、二級(jí)緩存256 KB、65 nm制程,，操作系統(tǒng)Android 2.3,，內(nèi)存為512 MB。
為了有針對(duì)性地實(shí)驗(yàn),，用U-SURF算法對(duì)分塊的方法進(jìn)行對(duì)比評(píng)估,。U-SURF算法大部分的高速緩存未命中發(fā)生在點(diǎn)的檢測(cè)部分而極少會(huì)發(fā)生在主方向分配部分。這樣便于直觀地查看各個(gè)階段的用時(shí),，對(duì)于算法的提高可以分階段統(tǒng)計(jì),。
本文評(píng)估分塊的SURF算法采取兩組實(shí)驗(yàn)：
第一組實(shí)驗(yàn)用來(lái)測(cè)試分塊大小的選擇對(duì)運(yùn)行速度的影響，主要考察總的運(yùn)行時(shí)間和每一步所用時(shí)間,。預(yù)先設(shè)置了6種分塊,，分別為96×96、120×120,、160×160,、160×240、240×240及480×480,。圖7為測(cè)試結(jié)果,。分析圖7可以得出：(1)隨著分塊大小的增加，時(shí)間消耗也隨之增加,，這說明使用較小的分塊可以縮短時(shí)間消耗；(2)對(duì)于單步所用時(shí)間曲線,，分塊大小在達(dá)到轉(zhuǎn)折點(diǎn)（圖中為240×240）之前,，單步耗時(shí)緩慢地單調(diào)上升，而一旦大于該分塊大小,，單步耗時(shí)將顯著增加,。這是因?yàn)椋?dāng)用于計(jì)算的分塊的數(shù)據(jù)集合超過了高速緩存的容量時(shí),，高速緩存中數(shù)據(jù)將發(fā)生多次的替換,，未命中的現(xiàn)象顯著提高,，時(shí)間消耗陡然上升。對(duì)于不同的移動(dòng)設(shè)備,，由于使用的處理器不同,，出現(xiàn)轉(zhuǎn)折的分塊大小將不盡相同。
本文提出了一種依據(jù)內(nèi)容自適應(yīng)分塊的SURF算法,。首先分析了分塊方法的優(yōu)勢(shì)及存在的一些問題,，然后根據(jù)圖像熵的理論基礎(chǔ)提出了依據(jù)圖像內(nèi)容自適應(yīng)分塊的方法，減少了高速緩存中的沖突失效和有用信息的損失,。實(shí)驗(yàn)結(jié)果表明,，改進(jìn)后的SURF算法在沒有犧牲精確度的前提下，速度提升了大約1.5～1.7倍,，有效提升了算法在移動(dòng)平臺(tái)上的表現(xiàn),。
參考文獻(xiàn)
[1] 石教英.虛擬現(xiàn)實(shí)基礎(chǔ)及實(shí)用算法[M].北京：科學(xué)出版社，2002.
[2] 陽(yáng)化冰.虛擬現(xiàn)實(shí)構(gòu)造語(yǔ)言VRML[M].北京：北京航空航天大學(xué)出版社,，2000.
[3] 汪成為.中國(guó)計(jì)算機(jī)學(xué)會(huì)學(xué)術(shù)著作叢書靈境(虛擬現(xiàn)實(shí))技術(shù)的理論,、實(shí)現(xiàn)及應(yīng)用[M].北京：清華大學(xué)出版社，1996.
[4] 朱淼良,，姚遠(yuǎn),，蔣云良.增強(qiáng)現(xiàn)實(shí)綜述[J].中國(guó)圖象圖形學(xué)報(bào)，2004,，9(7)：767-774.
[5] 蘇慧.AR Zombie Invasion[EB/OL].(2011-12-06).http://mobile.51cto.com/hot-305941.htm.
[6] RUBLEE E,，RABAUD V，KONOLIGE K,，et al.ORB：an efficient alternative to SIFT or SURF[C].Proceedings of ICCV,，2011.
[7] ROSTEN E，DRUMMOND T.Machine learning for high speed corner detection[C].Proceedings of ECCV,，2006.
[8] TERRIBERRY T B,，F(xiàn)RENCH L M，HELMSEN J.GPU accelerating speeded-up robust features[C].Proceedings of 3DPVT,，2008.
[9] TA D N,，Chen Weichao，GELFAND N,，et al.SURF Trac：efficient tracking and continuous object recognition using local feature descriptors[C].Proceedings of CVPR,，2009.
[10] ROSTEN E，PORTER R,，DOUMMOND T.Faster and better：a machine learning approach to corner detection[J].IEEE Transactions on PAMI,，2010，32(1)：105-119.
[11] COLEMAN S，MCKINLEY K S.Tile size selection using cache organization and data layout[C].Proceedings of SIGPLAN,，1995.