基于自適應(yīng)分塊的移動(dòng)設(shè)備上特征點(diǎn)提取方法

朱 莉，李文茂

(中國(guó)地質(zhì)大學(xué)（武漢）計(jì)算機(jī)學(xué)院，湖北 武漢430000)

隨著技術(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ī)生成一種逼真的視、觸、聽(tīng)、動(dòng)等多種感覺(jué)的虛擬環(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。但這些方法都沒(méi)有得到很好的實(shí)際應(yīng)用。

本文分析了SURF算法在移動(dòng)平臺(tái)上性能不高的一個(gè)重要原因：移動(dòng)設(shè)備較小的高速緩存容量不適應(yīng)原算法的圖像數(shù)據(jù)訪問(wèn)方式，由此提出了依據(jù)圖像內(nèi)容的自適應(yīng)分塊方法，以減少高速緩存中的沖突失效和有用信息的損失，對(duì)算法速度的提高將會(huì)有很好的貢獻(xiàn)。

1 SURF算法與高速緩存的不匹配原因分析

在SURF算法中，為了在不同尺度上尋找極值點(diǎn)，需要建立圖像的尺度空間。SURF在建立尺度空間時(shí)，保持原始圖像不變，通過(guò)改變箱式濾波器的大小，對(duì)固定大小積分圖像進(jìn)行濾波得到圖像的尺度空間。

圖1 數(shù)據(jù)訪問(wèn)方式

可見(jiàn)，SURF算法中，數(shù)據(jù)的訪問(wèn)方式由箱式濾波器的大小和類型決定。例如一個(gè)9×9的箱式濾波器在計(jì)算時(shí)，假設(shè)每一次迭代過(guò)程中需要訪問(wèn)9×9區(qū)域內(nèi)的8個(gè)元素。 如圖 1所示，設(shè)元素集合 S={A，B，C，D，E，F(xiàn)，G，H}。在下一次迭代過(guò)程中，箱式濾波器將向右移動(dòng)一個(gè)像素，從而訪問(wèn)集合 S右邊的8個(gè)元素，即集合 S′={A′，B′，C′，D′，E′，F(xiàn)′，G′，H′}。

如果有一個(gè)大小為200×200的二維圖像矩陣I和一個(gè)可以容納1 024個(gè)元素的直接映射高速緩存，假設(shè)圖像矩陣I的第一個(gè)元素保存在高速緩存的第一個(gè)位置，元素集合 S={A，B，C，D，E，F(xiàn)，G，H}用于計(jì)算；圖像矩陣I以基于行的方式存儲(chǔ)在高速緩存中。將可以同時(shí)保存在高速緩存中的連續(xù)的幾行元素定義為一個(gè)集合。在圖2中，第一個(gè)集合表示從第1行到第5行的元素再加上第6行的前24個(gè)元素。

圖2 高速緩存中數(shù)據(jù)存放方式

在SURF算法運(yùn)算開(kāi)始時(shí)，第一個(gè)集合將載入高速緩存中，如圖3所示，這時(shí)可以訪問(wèn)到第1行和第4行中的{A，B，C，D}，然后需要訪問(wèn)第 7行和第 9行的{E，F(xiàn)，G，H}，此時(shí)就需要從內(nèi)存中讀取第二個(gè)集合的數(shù)據(jù)替換掉第一個(gè)集合，進(jìn)而可以訪問(wèn)第7行和第9行的{E，F(xiàn)，G，H}。當(dāng)濾波器向右移動(dòng)一個(gè)像素后，需要訪問(wèn){A′，B′，C′，D′}，而此時(shí)第一個(gè)集合已經(jīng)被替換掉了，這造成了自沖突失效。如果考慮最壞情況，即箱式濾波器每次訪問(wèn)包含前4個(gè)元素的數(shù)據(jù)后，都要被包含有后4個(gè)元素的數(shù)據(jù)所替換，而隨后又需要重新訪問(wèn)包含前面4個(gè)元素的數(shù)據(jù)，造成另一個(gè)自沖突失效。

圖3 高速緩存中數(shù)據(jù)訪問(wèn)方式

一個(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ì)算過(guò)程中將不會(huì)產(chǎn)生自沖突失效。

穆叔曰：“以豹所聞，此之謂世祿，非不朽也。魯有先大夫曰臧文仲，既沒(méi)，其言立，其是之謂乎！”[注]《左傳·襄公二十四年》，孔穎達(dá)：《春秋左傳正義》，臺(tái)北：藝文印書館，2007年，第609頁(yè)。

在分塊算法中，只有選擇合適的分塊大小，才能最大程度地減少內(nèi)存中的數(shù)據(jù)交換，塊的大小選取往往根據(jù)平臺(tái)的不同以及圖像本身的不同而有所差異。COLEMAN S[11]提出了根據(jù)給定的高速緩存容量和高速緩存行的大小來(lái)進(jìn)行分塊大小的選取算法。然而，對(duì)于程序開(kāi)發(fā)人員而言，可用的高速緩存的大小是無(wú)法預(yù)測(cè)的且往往比系統(tǒng)整個(gè)緩存要小，顯然使用整個(gè)高速緩存的大小來(lái)確定分塊的大小是不合適的。而通過(guò)實(shí)驗(yàn)來(lái)從所有可能的分塊中選擇合適的分塊也是一個(gè)不可取的方法。

另外，不合適的分塊也會(huì)造成興趣點(diǎn)精度的下降。圖4所示分別為原始SURF算法和簡(jiǎn)單分塊后的提點(diǎn)效果?？梢钥吹剑胁糠贮c(diǎn)的缺失。這是由于在箱式濾波器與積分圖像卷積的過(guò)程中，無(wú)法計(jì)算邊緣上的像素點(diǎn)所導(dǎo)致的。

圖4 原始SURF與簡(jiǎn)單分塊后算法提點(diǎn)效果

為了解決上述問(wèn)題，本文提出了依據(jù)圖像內(nèi)容的自適應(yīng)分塊方法。該方法主要思想是通過(guò)圖像熵的計(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ì)算的熵值非常小，說(shuō)明該區(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)容分塊選擇算法的偽代碼如下：

圖5 確定了所有最大連續(xù)區(qū)域后的圖像分塊效果

輸入：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)容分塊結(jié)果對(duì)比

圖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é)果

本文的研究通過(guò)在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í)間消耗也隨之增加，這說(shuō)明使用較小的分塊可以縮短時(shí)間消耗；(2)對(duì)于單步所用時(shí)間曲線，分塊大小在達(dá)到轉(zhuǎn)折點(diǎn)（圖中為240×240）之前，單步耗時(shí)緩慢地單調(diào)上升，而一旦大于該分塊大小，單步耗時(shí)將顯著增加。這是因?yàn)?，?dāng)用于計(jì)算的分塊的數(shù)據(jù)集合超過(guò)了高速緩存的容量時(shí)，高速緩存中數(shù)據(jù)將發(fā)生多次的替換，未命中的現(xiàn)象顯著提高，時(shí)間消耗陡然上升。對(duì)于不同的移動(dòng)設(shè)備，由于使用的處理器不同，出現(xiàn)轉(zhuǎn)折的分塊大小將不盡相同。

圖7 不同大小分塊計(jì)算時(shí)間

第二組試驗(yàn)用來(lái)對(duì)比依據(jù)內(nèi)容自適應(yīng)分塊的SURF算法與原始SURF算法的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如表1所示。結(jié)果表明，優(yōu)化后的SURF算法在速度上有較明顯的提高(大約 1.5～1.7倍的速度提升)，有效地提高了 SURF算法在移動(dòng)平臺(tái)上的表現(xiàn)。

表1 分塊SURF時(shí)間對(duì)比

本文提出了一種依據(jù)內(nèi)容自適應(yīng)分塊的SURF算法。首先分析了分塊方法的優(yōu)勢(shì)及存在的一些問(wèn)題，然后根據(jù)圖像熵的理論基礎(chǔ)提出了依據(jù)圖像內(nèi)容自適應(yīng)分塊的方法，減少了高速緩存中的沖突失效和有用信息的損失。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的SURF算法在沒(méi)有犧牲精確度的前提下，速度提升了大約 1.5～1.7倍，有效提升了算法在移動(dòng)平臺(tái)上的表現(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.