基于自适应分块的移动设备上特征点提取方法

朱 莉，李文茂

(中国地质大学（武汉）计算机学院，湖北 武汉430000)

随着技术的不断进步，将增强现实技术移植到移动设备上来，可以在更广泛的领域得到应用。

增强现实AR(Augmented Reality)[1-3]是利用计算机生成一种逼真的视、触、听、动等多种感觉的虚拟环境，使用各种传感设备让用户融合到该环境中，是以交互性和构想为基本特征的计算机高级人机界面[4]。目前比较成功的案例有城市万花筒（City Lens）[5]、谷歌眼镜（Google Class）[6]和游戏 AR Zombie Invasion[7]。

在增强现实应用中，特征点提取和特征点匹配[2]是关键。当前，移动平台上存在的几种轻量级特征点提取算法FAST(Features from Accelerated Segment Test)[8-9]和ORB算法[10]在光照不变性、几何不变性以及健壮性方面都不及SURF。针对SURF算法，国内外也有很多成功的尝试，比如TA D N等人[9]提出的SURFTrac算法和TERRIBERRY T B等人[8]提出的在GPU上使用OpenCL可更有效地实现SURF。但这些方法都没有得到很好的实际应用。

本文分析了SURF算法在移动平台上性能不高的一个重要原因：移动设备较小的高速缓存容量不适应原算法的图像数据访问方式，由此提出了依据图像内容的自适应分块方法，以减少高速缓存中的冲突失效和有用信息的损失，对算法速度的提高将会有很好的贡献。

1 SURF算法与高速缓存的不匹配原因分析

在SURF算法中，为了在不同尺度上寻找极值点，需要建立图像的尺度空间。SURF在建立尺度空间时，保持原始图像不变，通过改变箱式滤波器的大小，对固定大小积分图像进行滤波得到图像的尺度空间。

图1 数据访问方式

可见，SURF算法中，数据的访问方式由箱式滤波器的大小和类型决定。例如一个9×9的箱式滤波器在计算时，假设每一次迭代过程中需要访问9×9区域内的8个元素。 如图 1所示，设元素集合 S={A，B，C，D，E，F，G，H}。在下一次迭代过程中，箱式滤波器将向右移动一个像素，从而访问集合 S右边的8个元素，即集合 S′={A′，B′，C′，D′，E′，F′，G′，H′}。

如果有一个大小为200×200的二维图像矩阵I和一个可以容纳1 024个元素的直接映射高速缓存，假设图像矩阵I的第一个元素保存在高速缓存的第一个位置，元素集合 S={A，B，C，D，E，F，G，H}用于计算；图像矩阵I以基于行的方式存储在高速缓存中。将可以同时保存在高速缓存中的连续的几行元素定义为一个集合。在图2中，第一个集合表示从第1行到第5行的元素再加上第6行的前24个元素。

图2 高速缓存中数据存放方式

在SURF算法运算开始时，第一个集合将载入高速缓存中，如图3所示，这时可以访问到第1行和第4行中的{A，B，C，D}，然后需要访问第 7行和第 9行的{E，F，G，H}，此时就需要从内存中读取第二个集合的数据替换掉第一个集合，进而可以访问第7行和第9行的{E，F，G，H}。当滤波器向右移动一个像素后，需要访问{A′，B′，C′，D′}，而此时第一个集合已经被替换掉了，这造成了自冲突失效。如果考虑最坏情况，即箱式滤波器每次访问包含前4个元素的数据后，都要被包含有后4个元素的数据所替换，而随后又需要重新访问包含前面4个元素的数据，造成另一个自冲突失效。

图3 高速缓存中数据访问方式

一个大小为 9×9的箱式滤波器在对一个 200×200的积分图像计算时，将会导致多达80 000次的高速缓存未命中以及高速缓存的数据替换。实验证明，这种自冲突失效所造成的影响将随着箱式滤波器和积分图像的变大而变得更为明显。

2 特征点提取算法改进与实现

分块的SURF算法将输入图像分割成规则的网格状图像块，然后对每个图像块分别进行生成积分图、尺度空间分析、计算Hessian矩阵，最后对每个单独图像块分别进行特征点提取。

对原图像分块后，所得的图像块每行的数据量较原始图像小，图像数据则以基于行的方式存储在高速缓存中，箱式滤波器在与分块后的积分图像计算时，可以减少数据的重载入，从而可以减少冲突失效。在第1节的例子中，如果所选择的图像块大小为24×41，则可以用8行，每行24个元素来替换一行200个元素。因此箱式滤波器的大小只要小于24×41，在计算过程中将不会产生自冲突失效。

穆叔曰：“以豹所闻，此之谓世禄，非不朽也。鲁有先大夫曰臧文仲，既没，其言立，其是之谓乎！”[注]《左传·襄公二十四年》，孔颖达：《春秋左传正义》，台北：艺文印书馆，2007年，第609页。

在分块算法中，只有选择合适的分块大小，才能最大程度地减少内存中的数据交换，块的大小选取往往根据平台的不同以及图像本身的不同而有所差异。COLEMAN S[11]提出了根据给定的高速缓存容量和高速缓存行的大小来进行分块大小的选取算法。然而，对于程序开发人员而言，可用的高速缓存的大小是无法预测的且往往比系统整个缓存要小，显然使用整个高速缓存的大小来确定分块的大小是不合适的。而通过实验来从所有可能的分块中选择合适的分块也是一个不可取的方法。

另外，不合适的分块也会造成兴趣点精度的下降。图4所示分别为原始SURF算法和简单分块后的提点效果。可以看到，有部分点的缺失。这是由于在箱式滤波器与积分图像卷积的过程中，无法计算边缘上的像素点所导致的。

图4 原始SURF与简单分块后算法提点效果

为了解决上述问题，本文提出了依据图像内容的自适应分块方法。该方法主要思想是通过图像熵的计算来确定最大连续区域，从而确定不同内容上分块的大小。

增加最大连续区域(Maximum Continuous Region)内的任一子区域的大小，都可以提高子区域的熵的大小，但是提高该区域的大小却不能进一步提高该区域的熵的大小。为了减少确定最大连续区域的计算量，提供一个待选集合S。该集合包含几个不同大小的离散区域来作为可能的最大连续区域，如：120×120、160×160、160×240、240×240和 480×480。这些离散值将是使用分块算法时对图像分块的依据。图5为确定了所有最大连续区域后的图像分块。

确定合适的最大连续区域步骤如下：

（1）选取集合 S中的第一个待选区域 96×96，计算该区域熵的大小。如果计算的熵值非常小，说明该区域包含的信息很少，因此可以忽略不计，该区域不参与后续的特征点的提取，转步骤（3）；

（2）扩大计算区域为集合S中的下一个待选区域，计算熵值。若熵停止增加或已达到最大的待选分块区域，确定所选的区域为所寻找的最大连续区域，同时转步骤（3），否则循环执行步骤（2）；

（3）判断是否存在无重叠的待划分区域。若有，转步骤（1），否则输出所有的最大连续区域。

依据内容分块选择算法的伪代码如下：

图5 确定了所有最大连续区域后的图像分块效果

输入：TSCs 候选分块组（如 96×96、96×120 等）

输出：MCRs最大连续区域（Maximum continuous Regions）

参数：tile-size为当前待选分块；tile-sizenext为下一待选分块；entropy为当前分块区域的熵；entropynext为下一待选分块区域熵。

图6 未采用分块算法与采用依据内容分块结果对比

图6所示为依据内容分块后所提取的特征点与原始SURF算法的对比。该实例显示，改进的方法对于大块的文本性内容可以自动地进行较合理的分块，减少了信息的丢失，同时略去包含极少信息量的部分，减少了后续计算。

3 实验结果

本文的研究通过在OpenSURF环境中进行仿真实验，基于OpenCV和C++，将其移植到Android平台上。实验使用的智能手机为HTC G7，该手机参数为单核CPU、一级缓存 32 KB、二级缓存 256 KB、65 nm制程，操作系统 Android 2.3，内存为 512 MB。

为了有针对性地实验，用U-SURF算法对分块的方法进行对比评估。U-SURF算法大部分的高速缓存未命中发生在点的检测部分而极少会发生在主方向分配部分。这样便于直观地查看各个阶段的用时，对于算法的提高可以分阶段统计。

本文评估分块的SURF算法采取两组实验：

第一组实验用来测试分块大小的选择对运行速度的影响，主要考察总的运行时间和每一步所用时间。预先设置了 6 种分块， 分别为 96×96、120×120、160×160、160×240、240×240及 480×480。 图 7为测试结果。 分析图7可以得出：(1)随着分块大小的增加，时间消耗也随之增加，这说明使用较小的分块可以缩短时间消耗；(2)对于单步所用时间曲线，分块大小在达到转折点（图中为240×240）之前，单步耗时缓慢地单调上升，而一旦大于该分块大小，单步耗时将显著增加。这是因为，当用于计算的分块的数据集合超过了高速缓存的容量时，高速缓存中数据将发生多次的替换，未命中的现象显著提高，时间消耗陡然上升。对于不同的移动设备，由于使用的处理器不同，出现转折的分块大小将不尽相同。

图7 不同大小分块计算时间

第二组试验用来对比依据内容自适应分块的SURF算法与原始SURF算法的运行时间，实验结果如表1所示。结果表明，优化后的SURF算法在速度上有较明显的提高(大约 1.5～1.7倍的速度提升)，有效地提高了 SURF算法在移动平台上的表现。

表1 分块SURF时间对比

本文提出了一种依据内容自适应分块的SURF算法。首先分析了分块方法的优势及存在的一些问题，然后根据图像熵的理论基础提出了依据图像内容自适应分块的方法，减少了高速缓存中的冲突失效和有用信息的损失。实验结果表明，改进后的SURF算法在没有牺牲精确度的前提下，速度提升了大约 1.5～1.7倍，有效提升了算法在移动平台上的表现。

[1]石教英.虚拟现实基础及实用算法[M].北京：科学出版社，2002.

[2]阳化冰.虚拟现实构造语言 VRML[M].北京：北京航空航天大学出版社，2000.

[3]汪成为.中国计算机学会学术著作丛书灵境(虚拟现实)技术的理论、实现及应用[M].北京：清华大学出版社，1996.

[4]朱淼良，姚远，蒋云良.增强现实综述[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，FRENCH 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.