摘  要： 當前，移動設備的計算能力越來越強，但類似增強現(xiàn)實對實時性要求較高的應用，其性能還無法完全滿足需求。在增強現(xiàn)實應用中，提取特征點和特征點的匹配是關(guān)鍵。主要關(guān)注特征點的提取，以SURF算法為例，針對移動設備較小的高速緩存容量不適應原算法圖像數(shù)據(jù)訪問方式的問題，提出了依據(jù)圖像內(nèi)容的自適應分塊方法。實驗結(jié)果表明，改進后的算法在沒有犧牲精確度的情況下，速度提高了1.5～1.7倍。
關(guān)鍵詞： 增強現(xiàn)實；特征點提取；SURF；自適應分塊

    隨著技術(shù)的不斷進步，將增強現(xiàn)實技術(shù)移植到移動設備上來，可以在更廣泛的領(lǐng)域得到應用。
    增強現(xiàn)實AR(Augmented Reality)[1-3]是利用計算機生成一種逼真的視、觸、聽、動等多種感覺的虛擬環(huán)境，使用各種傳感設備讓用戶融合到該環(huán)境中，是以交互性和構(gòu)想為基本特征的計算機高級人機界面[4]。目前比較成功的案例有城市萬花筒（City Lens）[5]、谷歌眼鏡（Google Class）[6]和游戲AR Zombie Invasion[7]。
    在增強現(xiàn)實應用中，特征點提取和特征點匹配[2]是關(guān)鍵。當前，移動平臺上存在的幾種輕量級特征點提取算法FAST(Features from Accelerated Segment Test)[8-9]和ORB算法[10]在光照不變性、幾何不變性以及健壯性方面都不及SURF。針對SURF算法，國內(nèi)外也有很多成功的嘗試，比如TA D N等人[9]提出的SURFTrac算法和TERRIBERRY T B等人[8]提出的在GPU上使用OpenCL可更有效地實現(xiàn)SURF。但這些方法都沒有得到很好的實際應用。
    本文分析了SURF算法在移動平臺上性能不高的一個重要原因：移動設備較小的高速緩存容量不適應原算法的圖像數(shù)據(jù)訪問方式，由此提出了依據(jù)圖像內(nèi)容的自適應分塊方法，以減少高速緩存中的沖突失效和有用信息的損失，對算法速度的提高將會有很好的貢獻。
1 SURF算法與高速緩存的不匹配原因分析
    在SURF算法中，為了在不同尺度上尋找極值點，需要建立圖像的尺度空間。SURF在建立尺度空間時，保持原始圖像不變，通過改變箱式濾波器的大小，對固定大小積分圖像進行濾波得到圖像的尺度空間。
    可見，SURF算法中，數(shù)據(jù)的訪問方式由箱式濾波器的大小和類型決定。例如一個9×9的箱式濾波器在計算時，假設每一次迭代過程中需要訪問9×9區(qū)域內(nèi)的8個元素。如圖1所示，設元素集合S={A，B，C，D，E，F(xiàn)，G，H}。在下一次迭代過程中，箱式濾波器將向右移動一個像素，從而訪問集合S右邊的8個元素，即集合S′={A′，B′，C′，D′，E′，F(xiàn)′，G′，H′}。

    一個大小為9×9的箱式濾波器在對一個200×200的積分圖像計算時，將會導致多達80 000次的高速緩存未命中以及高速緩存的數(shù)據(jù)替換。實驗證明，這種自沖突失效所造成的影響將隨著箱式濾波器和積分圖像的變大而變得更為明顯。
2 特征點提取算法改進與實現(xiàn)
    分塊的SURF算法將輸入圖像分割成規(guī)則的網(wǎng)格狀圖像塊，然后對每個圖像塊分別進行生成積分圖、尺度空間分析、計算Hessian矩陣，最后對每個單獨圖像塊分別進行特征點提取。
    對原圖像分塊后，所得的圖像塊每行的數(shù)據(jù)量較原始圖像小，圖像數(shù)據(jù)則以基于行的方式存儲在高速緩存中，箱式濾波器在與分塊后的積分圖像計算時，可以減少數(shù)據(jù)的重載入，從而可以減少沖突失效。在第1節(jié)的例子中，如果所選擇的圖像塊大小為24×41，則可以用8行，每行24個元素來替換一行200個元素。因此箱式濾波器的大小只要小于24×41，在計算過程中將不會產(chǎn)生自沖突失效。
    在分塊算法中，只有選擇合適的分塊大小，才能最大程度地減少內(nèi)存中的數(shù)據(jù)交換，塊的大小選取往往根據(jù)平臺的不同以及圖像本身的不同而有所差異。COLEMAN S[11]提出了根據(jù)給定的高速緩存容量和高速緩存行的大小來進行分塊大小的選取算法。然而，對于程序開發(fā)人員而言，可用的高速緩存的大小是無法預測的且往往比系統(tǒng)整個緩存要小，顯然使用整個高速緩存的大小來確定分塊的大小是不合適的。而通過實驗來從所有可能的分塊中選擇合適的分塊也是一個不可取的方法。
    另外，不合適的分塊也會造成興趣點精度的下降。圖4所示分別為原始SURF算法和簡單分塊后的提點效果?？梢钥吹?，有部分點的缺失。這是由于在箱式濾波器與積分圖像卷積的過程中，無法計算邊緣上的像素點所導致的。

    為了解決上述問題，本文提出了依據(jù)圖像內(nèi)容的自適應分塊方法。該方法主要思想是通過圖像熵的計算來確定最大連續(xù)區(qū)域，從而確定不同內(nèi)容上分塊的大小。
    增加最大連續(xù)區(qū)域(Maximum Continuous Region)內(nèi)的任一子區(qū)域的大小，都可以提高子區(qū)域的熵的大小，但是提高該區(qū)域的大小卻不能進一步提高該區(qū)域的熵的大小。為了減少確定最大連續(xù)區(qū)域的計算量，提供一個待選集合S。該集合包含幾個不同大小的離散區(qū)域來作為可能的最大連續(xù)區(qū)域，如：120×120、160×160、160×240、240×240和480×480。這些離散值將是使用分塊算法時對圖像分塊的依據(jù)。圖5為確定了所有最大連續(xù)區(qū)域后的圖像分塊。

    確定合適的最大連續(xù)區(qū)域步驟如下：
    （1）選取集合S中的第一個待選區(qū)域96×96，計算該區(qū)域熵的大小。如果計算的熵值非常小，說明該區(qū)域包含的信息很少，因此可以忽略不計，該區(qū)域不參與后續(xù)的特征點的提取，轉(zhuǎn)步驟（3）；
    （2）擴大計算區(qū)域為集合S中的下一個待選區(qū)域，計算熵值。若熵停止增加或已達到最大的待選分塊區(qū)域，確定所選的區(qū)域為所尋找的最大連續(xù)區(qū)域，同時轉(zhuǎn)步驟（3），否則循環(huán)執(zhí)行步驟（2）；
    （3）判斷是否存在無重疊的待劃分區(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<&epsilon;)
            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&times;96、96&times;120等）
    輸出：MCRs最大連續(xù)區(qū)域（Maximum continuous Regions）
    參數(shù)：tile-size為當前待選分塊；tile-sizenext為下一待選分塊；entropy為當前分塊區(qū)域的熵；entropynext為下一待選分塊區(qū)域熵。
    圖6所示為依據(jù)內(nèi)容分塊后所提取的特征點與原始SURF算法的對比。該實例顯示，改進的方法對于大塊的文本性內(nèi)容可以自動地進行較合理的分塊，減少了信息的丟失，同時略去包含極少信息量的部分，減少了后續(xù)計算。

3 實驗結(jié)果
    本文的研究通過在OpenSURF環(huán)境中進行仿真實驗，基于OpenCV和C++，將其移植到Android平臺上。實驗使用的智能手機為HTC G7，該手機參數(shù)為單核CPU、一級緩存32 KB、二級緩存256 KB、65 nm制程，操作系統(tǒng)Android 2.3，內(nèi)存為512 MB。
    為了有針對性地實驗，用U-SURF算法對分塊的方法進行對比評估。U-SURF算法大部分的高速緩存未命中發(fā)生在點的檢測部分而極少會發(fā)生在主方向分配部分。這樣便于直觀地查看各個階段的用時，對于算法的提高可以分階段統(tǒng)計。
    本文評估分塊的SURF算法采取兩組實驗：
    第一組實驗用來測試分塊大小的選擇對運行速度的影響，主要考察總的運行時間和每一步所用時間。預先設置了6種分塊，分別為96&times;96、120&times;120、160&times;160、160&times;240、240&times;240及480&times;480。圖7為測試結(jié)果。分析圖7可以得出：(1)隨著分塊大小的增加，時間消耗也隨之增加，這說明使用較小的分塊可以縮短時間消耗；(2)對于單步所用時間曲線，分塊大小在達到轉(zhuǎn)折點（圖中為240&times;240）之前，單步耗時緩慢地單調(diào)上升，而一旦大于該分塊大小，單步耗時將顯著增加。這是因為，當用于計算的分塊的數(shù)據(jù)集合超過了高速緩存的容量時，高速緩存中數(shù)據(jù)將發(fā)生多次的替換，未命中的現(xiàn)象顯著提高，時間消耗陡然上升。對于不同的移動設備，由于使用的處理器不同，出現(xiàn)轉(zhuǎn)折的分塊大小將不盡相同。

    本文提出了一種依據(jù)內(nèi)容自適應分塊的SURF算法。首先分析了分塊方法的優(yōu)勢及存在的一些問題，然后根據(jù)圖像熵的理論基礎提出了依據(jù)圖像內(nèi)容自適應分塊的方法，減少了高速緩存中的沖突失效和有用信息的損失。實驗結(jié)果表明，改進后的SURF算法在沒有犧牲精確度的前提下，速度提升了大約1.5～1.7倍，有效提升了算法在移動平臺上的表現(xiàn)。
參考文獻
[1] 石教英.虛擬現(xiàn)實基礎及實用算法[M].北京：科學出版社，2002.
[2] 陽化冰.虛擬現(xiàn)實構(gòu)造語言VRML[M].北京：北京航空航天大學出版社，2000.
[3] 汪成為.中國計算機學會學術(shù)著作叢書靈境(虛擬現(xiàn)實)技術(shù)的理論、實現(xiàn)及應用[M].北京：清華大學出版社，1996.
[4] 朱淼良，姚遠，蔣云良.增強現(xiàn)實綜述[J].中國圖象圖形學報，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.