一种基于SURF与地理格网模型的增强现实方法

2018-06-28毕金强许家帅辛全波尚东方

计算机与现代化 2018年6期

毕金强,许家帅,辛全波,尚东方

(交通运输部天津水运工程科学研究所，天津 300456)

0 引言

增强现实技术(Augmented Reality， AR)是在用户观察到的真实自然环境中添加计算机生成的文字、3D模型等信息的技术[1]。在综合计算机图形、光电成像、多传感器、融合显示、图像处理和计算机视觉等学科知识的基础上，实时地计算摄像机的位置及角度将虚拟世界套在现实世界并进行互动，已经成功应用到医疗手术、工业设计、市政规划、军事仿真、教育培训和文化娱乐等领域。图像识别与匹配作为增强现实图像信息提取与目标匹配的基础，是现实世界场景匹配到虚拟对象的关键环节。1999年Lowe提出的SIFT(Scale-Invariant Feature Transform)尺度不变特征转换算法，通过侦测与描述影像中的局部性特征，在空间尺度中寻找极值点来提取出其位置、尺度、旋转不变量，成为图像识别与匹配的典型算法，但是该算法在灰度变化相似的区域易产生误匹配且特征提取及匹配速度效率较低[2]。因此，国内外学者们开展了大量研究和算法改进，如Rosten等[3]提出的FAST(Features from Accelerated Segment Test)特征点检测算法、Bay等[4]提出的SURF(Speeded-Up Robust Features)算法、Wanger等[5]提出的基于自然特征的6自由度跟踪注册算法、李杨等[6]提出的自然特征注册方法等，通过检测中心与周围像素点的明暗程度来确定特征点，不仅稳定高效，还降低了算法复杂度，提高了特征检测和匹配的实时性。但是，上述算法的研究通常局限在室内或户外小范围环境，所以无法适用于户外大规模图像的实时跟踪注册，以北京理工大学为代表的团队开展了三维注册、光照模型、深度检测等方法研究并利用相关技术在重建圆明园的实验中取得重要进展，开创户外增强现实领域的先河[7]。

对于室内小范围场景或者单一精细场景而言，可定义图像中的多个方向上的极大变化点，采用基于线性搜索和基于机器学习的特征分类等识别算法进行特征识别[8-9]，在户外场景识别方面，范志强等[10]和秦磊等[11]分别从数据聚类和内容相关性方面进行了特征匹配方法的研究并取得进展。户外增强现实一方面拥有更加复杂的地物信息，如场景图像数量较大、相似建筑结构的纹理信息不易区分等，增加了图像识别与匹配的难度；另一方面存在空间范围广、场景识别随机性大等问题，加上手机的运算和存储能力有限，难以进行大规模运算且效率较低。针对上述问题，本文提出的方法克服户外场景图像数量大、相似性多的难点，运用地理格网分割区域并建立空间索引提升运算处理效率，构建了智能端+服务端相结合的移动增强现实系统，实现了户外场景移动增强现实效果。

1 方法

本文方法主要由4个部分组成：1)采集场景目标图像，提取特征点； 2)基于地理格网构建空间四叉树索引，建立样本库； 3)目标场景与位置信息集成，生成特征图像； 4)特征图像与样本库中的特征点进行训练和匹配。

图1展示了该方法的总体设计流程，整个流程分为2个分支：1)静态样本库的建立，采集增强目标图像进行特征点的提取，在此基础上建立基于地理格网单元的空间索引并完成入库；2)动态特征的生成，将获取的实时图像场景和位置角度信息进行集成。最后将动态特征与静态样本库进行匹配训练，提取满足阈值要求的匹配信息，将增强信息渲染绘制在屏幕上，达到增强显示效果。

图1 总体设计流程图

1.1 图像特征点检测提取

图像特征检测是近年来计算机视觉领域的研究热点，孙世宇等[12]总结了特征检测子目前存在问题及指出可能的发展方向，对比分析了当前普遍使用的特征检测子的鲁棒性与速度。文献[4]中的图像特征检测算法在降低描述器维数和增强描述器鲁棒性方面进行了优化，惠记庄等[13]在此算法基础上提出了一种基于SURF-BRISK的目标识别匹配与定位方法。本文对文献[4]中的算法做了进一步改进，集成场景图像的地理位置信息，提取并生成Location-SURF图像特征描述，不仅提高了图像识别与匹配的准确率，同时，能根据位置区分具有相似纹理的图像特征。具体步骤为：

1)采集场景图像。准备一张矢量化地图，利用摄像机拍摄建筑不同方位的图像，存储建筑图像并标记位置信息及相关属性信息。

2)提取像素值点。利用Hessian[14]矩阵H(x,σ)检测特征点，其中x表示特征点坐标，σ表示尺度。选取图像后依次读取像素点值I(x，y)，将像素点值代替Hessian矩阵公式中的函数值f(x，y)，计算出Hessian矩阵的3个矩阵元素。公式(1)表示在图像中的一个点x(i，j)处尺度为σ的Hessian矩阵H(x,σ)。

(1)

c(x,y,σ)=DxxDyy-(0.9Dxy)2

(2)

比较求出的值c(x,y,σ)与设定的阈值的大小，如果大于阈值则标记该点像素值为关键点。

3)特征点定位。为了更精细表达图像特征，构建金字塔式的图像尺度空间，确保金字塔层中的每一层图像大小保持不变，避免图像二次抽样，通过改变滤波器大小的方式按照上述步骤进行像素值的提取，标记出所有符合像素值的关键点。在以关键点为中心3×3×3的像素邻域内进行比较计算，即与同一尺度层中相邻的8个点以及上下2层尺度的9个点分别进行比较计算，如图2(a)所示。根据计算结果，丢弃小于预设极值的取值，依次调整阈值逐步减少检测特征点的数量，最终确定以特征值大于周围像素的点为关键特征点。接下来确定关键特征点的主方向，如图2(b)所示，以关键特征点为中心，6S(S为特征点所在的尺度值)为半径绘制圆形，在60°扇形范围内按照距离特征点的远近贡献大小，统计覆盖区域内所有点X、Y方向的特征并计算矢量方向，然后遍历整个圆形区域，以最长矢量方向作为该特征点的主方向。按照上述步骤，逐个计算出关键特征点的主方向，如图2(c)所示。

(a) 关键特征点提取

(b) 主方向计算

4)特征点描述。根据关键特征点和主方向计算关键特征点的描述算子，以关键特征点为中心，沿主方向绘制长度20S(S为特征点所在的尺度值)的正方形窗格，将该正方形窗格划分成4×4的子区域，每个子区域再分为25个像素分别计算水平方向和垂直方向的Haar小波特征，最后计算出水平方向值之和∑dx、水平方向绝对值之和∑|dx|、垂直方向之和∑dy、垂直方向绝对值之和∑|dy|，由此得出每个特征点的64维特征描述算子。

5)结合步骤1中记录的位置信息，提取经纬度坐标数据，融合到特征描述算子中，生成Location-SURF图像特征描述。

通过上述5步即可检测提取出图像的所有关键特征点和描述信息。

1.2 样本库构建

图像特征点检测提取生成海量的样本特征点数据，地理格网具有准确表达位置，可根据实际需要控制格网精度等优点，已广泛应用于位置服务以及地理国情监测等诸多方面[15-16]。本文结合地理格网理论[17]在区域范围进行地理格网单元的划分，通过位置建立地理格网单元与图像特征点的索引机制，进而提高数据的集成匹配速率。地理格网是指按一定的数学法则对地球表面进行划分形成的格网，基于小范围区域的网格划分方法有3种：按照方网格划分的规则格网、按道路街区划分的不规则格网和按行政区划划分的地理格网。结合本文研究的区域范围，采用方网格划分的方式构建地理格网模型，过程如下：

1)地图处理。将研究区域范围的地形图进行坐标配准，建立WGS84空间参考系统并开展矢量化操作。

2)地理格网分级。以同一纬度上相邻2条格网点的经度坐标A(α1,β1),B(α2,β2)，根据公式(3)计算距离D：

D=R×arccos(cos β1cos β2cos (α1-α2)+sin β1sin β2)

(3)

其中，R代表地球半径。

(a) 地理格网划分图

(b) 目标分割示意图图3 试验区域地图

按照2″格网间隔进行计算经度方向约为57 m，纬度方向距离约为62 m，确保设备在格网单元中采集图像可获取目标的整体性，图3(a)表示户外场景试验区地理格网划分图。

3)地理格网编码。单元格网代码由象限代码、格网间距代码、间隔单位代码、纬经度代码和秒纬、经度格网代码共18位组成，如图4所示。

图4 格网编码规则

以图3中左上角网格坐标计算出单元网格代码为NE02S2912100181242，依次类推，形成该区域地理网格划分编码，上述过程完成了试验区域地理网格的分级与编码。

基于空间地理位置，将特征点与地理单元网格按空间四叉树索引[18-19]的机制，将区域递归划分区域→单元格网→目标场景→特征点层次的树形结构，图5表示本文建立的四叉树结构，右图自上而下根节点表示由ABCD这4个单元格网构成的区域，中间节点表示单元网格，叶子节点表示包含的建筑实体，每一个建筑实体包含若干特征点，通过树形结构建立索引关系，具有较高的区域空间数据查询检索效率。

图5 四叉树索引示意图

对于场景目标横跨格网单元来说，如图5中目标场景③横跨A、B这2个单元格网，传统的四叉树索引会造成数据的冗余，计算机会遍历目标物的所有特征点进行查询，每次查询的数据量将增多，导致查询效率下降。本文基于Location-SURF图像特征描述中的位置信息，将此类目标场景进行分割，按照图像的位置与格网单元建立索引，这样在查询计算时匹配所在单元网格中的特征点。如图3(b)所示，目标场景划分为区域1和区域2，对应的特征点分别与各自的单元格网建立索引，减少特征点的冗余。按照空间四叉树索引规则，建立样本数据库表，将1.1节中提取的特征点存储，构建目标特征点的样本库。

1.3 特征图像生成

特征图像是指采用二进制编码将位置、角度信息和视频帧数据嵌入，生成的具有唯一标识的特征图像信息数据。数据包括文件头和文件体2个部分信息，文件头存放拍摄经纬度坐标、方向角度、分辨率等信息，文件体存放视频帧数据信息。其中视频帧的获取可调用Android手机的onPreviewFrame()接口，实时截取每一帧视频流生成图像。在增强现实表达过程中，需要保证设备的稳定性，避免终端姿态变换等因素的干扰[20]。图6表示手机竖直静止状态下的方位特征，X轴水平向右，Y轴垂直向上，Z轴指向屏幕正面，Pitch表示顶底部翘起的角度，Roll表示左右侧翘起的角度，Azimuth表示顶部朝向与正北方向的角度。拍摄过程中分别设置XYZ方向上的运动阈值，在一定时间内不超过阈值则可采集图像，同时记录Azimuth和GPS坐标数据，写入编码数据中。

图6 传感器方位示意图

1.4 训练匹配

训练匹配是方法的关键一步，也是评价本文方法是否成功的最主要依据。将特征图像信息数据进行解析，按照1.1节图像特征点检测方法，首先根据特征图像解析的经纬度坐标确定采集点所在的单元网格，查询该网格内所包含的目标元素特征点集合，结合方位角计算可进一步缩小查询的目标范围。其次取某个关键点，采用欧氏距离与样本库的特征点向量进行相似性度量匹配，求出欧氏距离最近的前2个关键点，如果2个点最近的距离除以次近的距离小于比例阈值，则记录这一对匹配点。针对图像特征点与样本库的特征点数量达到万级别的点集，采用线性搜索依次遍历点集的方式非常耗时，本文采用k-d树算法[21-22]查找每个特征点的近似最近邻特征点，匹配效果如图7所示。

图7 训练匹配效果图

上述4节论述了本文方法，在显示过程中求出匹配的特征点的中心点并挂接虚拟增强信息，返回到智能终端进行三维注册。

2 实验分析及应用

2.1 实验分析

本文选取宁波环球航运广场户外场景区域，面积约为0.376 km2。为确保移动设备在某一格网单元中倾斜摄影可获取目标的整体，试验区域按2″×2″划分成28个网格，共采集270余幅增强现实目标图像，建立20余万样本特征数据记录。为了验证本文所提方法的有效性和正确性，开展了2组试验。

1)可行性试验。

表1 目标与样本特征点匹配表

名称特征点数量匹配点数(样本1)匹配点数(样本2)匹配点数(样本n)匹配成功图像1113610…否图像271101…否图像3116314…否图像411241177…是图像5647134…否图像6141800…否图像777563…否图像8856491…是图像992000…否

利用智能终端在户外不同位置采集了9幅室外场景图像(其中2幅图像与样本库采集图像接近)，提取特征点共计8750个，与样本库中270幅图像样本特征点(指图像特征点检测提取生成的特征描述信息的集合)进行匹配。表1记录了匹配成功的特征点数，结论为采集的图像与样本库中样本相近可匹配成功；图8展示了图像与样本1进行训练匹配的效果。试验结果表明本文方法是正确、可行的。

图8 目标与样本特征点匹配图

2)准确性试验。

由于特征点空间具有高维性，相似的距离可能有大量的错误匹配问题。该试验在上一试验的基础上，通过调整匹配成功点位(图像4与样本2、图像8与样本1)的比例阈值，逐步排除错误的匹配点，图9显示了不同比例阈值范围内的样本匹配数量。当阈值设置较高时，匹配点数量多但错误率高，阈值设置较低时，匹配准确度高但数量少。综合匹配数量与准确性2个方面因素得出，比例阈值设置为0.5～0.6之间时，既满足匹配的数量又满足匹配准确程度，可以得到良好的训练匹配结果。

(a) 图像4与样本2匹配

(b) 图像8与样本1匹配图9 比例阈值与匹配数量关系

3)对比分析。

在2组试验的基础上进行匹配率计算和时间复杂度的对比，进一步分析本文所提方法的效率。设置匹配点位的比例阈值为0.5，采用SURF算法和本文方法分别计算9幅图像的正确匹配点数和所用的时间，匹配率计算结果如图10(a)所示，时间复杂度对比结果如图10(b)所示。

(a) 算法匹配率统计

(b) 时间复杂度分析图10 算法对比分析

从匹配率结果看，图像4和图像8匹配成功，匹配率在95%以上，得出本文方法与SURF在匹配效果上基本保持一致。从时间复杂度结果看，本文方法可快速进行地理格网定位并进行匹配，耗费时间较短。综上，本文方法具有更高的匹配效率。

2.2 系统应用

基于本文提出的方法，采用感知采集、网络传输、数据分析、增强展示四层技术架构，利用空间数据库进行样本数据存储，开发了移动增强现实系统(MARS)，其中感知采集和增强展示数据利用Android智能终端系统完成，数据的分析与匹配计算在服务器端进行，通过4G网络传输实时交换数据和结果，系统体系结构如图11所示。在系统中构建虚实融合场景的2层视图框架，一层是摄像机视图，用于显示真实场景视频画面；一层是模型视图，用于绘制注册的虚拟增强信息，通过2层视图的叠加建立现实世界与虚拟物体的坐标系统关联，达到增强显示效果。

图11 系统体系结构

模型采用Unity3D软件制作，将模型设计在软件中的坐标轴原点，以物体对象中心为轴心，建立模型面和点，制作完成后进行纹理贴图，生成增强显示模型文件，如图12所示。

图12 增强显示模型

对试验区域户外建筑物进行识别，开启手机摄像头和GPS传感器，对准目标建筑物，生成特征图像并上传至服务端运算，匹配成功后将虚拟增强信息绘制于屏幕上，图13(a)和图13(b)分别为环球航运大厦和交通大厦的增强现实效果。

(a) 环球航运大厦 (b) 交通大厦图13 增强现实应用效果图

3 结束语

针对开展户外增强现实存在空间范围广、相似纹理多等问题，本文提出一种基于SURF与地理格网的移动增强现实方法，该方法首先构建静态样本库，划分地理空间格网，建立四叉树空间索引机制存储图像特征点，其次采集图像特征和位置角度信息利用二进制编码生成特征图像，最后通过计算特征点的欧氏距离，采用k-d树算法完成特征点的训练匹配。通过2组试验的分析与评价，验证了方法的有效性和正确性，并基于该方法开发了移动增强现实系统，实现了户外场景增强现实显示，并且可以很好地应用于室内小范围场景和单一精细场景。

在户外不同环境下进行场景识别时，受光照、阴雨天气等因素影响导致识别匹配率较低，下一步将针对该方法考虑增加光照模型等内容，提升匹配率。

参考文献：

[1] 罗斌,王涌天,沈浩,等. 增强现实混合跟踪技术综述[J]. 自动化学报, 2013,39(8):1185-1201.

[2] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2):91-110.

[3] Rosten E, Drummond T. Fusing points and lines for high performance tracking[C]// Proceedings of the 10th IEEE International Conference on Computer Vision. 2005,2:1508-1515.

[4] Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features (SURF)[J]. Computer Vision and Image Understanding(CVIU), 2008,110(3):346-359.

[5] Wagner D, Reitmayr G, Mulloni A, et al. Pose tracking from natural features on mobile phones[C]// Proceedings of the 7th IEEE/ACM International Symposium on Mixed and Augmented Reality(ISMAR ’08). 2008:15-18.

[6] 李扬,孙超,张明敏,等. 跟踪与匹配并行的增强现实注册方法[J]．中国图象图形学报, 2011,16(4)：680-685.

[7] 王涌天,林倞,刘越,等. 亦真亦幻的户外增强现实系统-圆明园的数字重建[J]. 中国科学基金, 2006,20(2):76-80.

[8] Oliva A, Torralba A. Modeling the shape of the scene: A holistic representation of the spatial envelope[J]. International Journal on Computer Vision, 2001,42(3):145-175.

[9] Vogel J, Schiele B. Natural scene retrieval based on a semantic modeling step[C]// The 3rd International Conference on Image and Video Retrieval. 2004:207-215.

[10] 范志强,赵沁平. 一种基于数据聚类的鲁棒SIFT特征匹配方法[J]. 计算机研究与发展, 2012,49(5)：1123-1129.

[11] 秦磊,高文. 基于内容相关性的场景图像分类方法[J]. 计算机研究与发展, 2009,46(7):1198-1205.

[12] 孙世宇,张岩,李建增,等. 影响特征检测子鲁棒性与速度方法的对比分析[J]. 电光与控制, 2017(8):24-28.

[13] 惠记庄,罗丽,杨永奎,等. 基于SURF-BRISK的目标识别匹配与定位方法研究[J]. 长安大学学报(自然科学版), 2016,36(3):93-101.

[14] 罗菁,林树忠,倪建云,等. 基于Hessian矩阵的指纹细节点提取方法[J]. 光电工程, 2008,35(11):134-138.

[15] 狄琳. 建立新国家地理格网服务地理国情监测初探[J]. 测绘通报, 2011(12):1-2.

[16] 白凤文,许华燕. 国家地理格网在数字城市建设中的应用[J]. 测绘通报, 2012(4):92-94.

[17] GB/T 12409-2009, 地理格网[S].

[18] 郭薇,郭菁,胡志勇. 空间数据库索引技术[M]. 上海:上海交通大学出版社, 2006.

[19] 周玉科,周成虎,马廷,等. 基于数据分治与双层索引的并行点面叠加分析方法研究[J]. 地理与地理信息科学, 2015,31(2):1-6.

[20] 严雷,杨晓刚,郭鸿飞,等. 结合图像识别的移动增强现实系统设计与应用[J]. 中国图象图形学报, 2016,21(2):184-191.

[21] 张贵安,袁志勇,童倩倩,等. 层次结构K-d树的立体图像快速匹配方法[J]. 软件学报, 2016,27(10):2462-2472.