...,公司之前已将基于人工智能机器视觉的自动光学检测系统作为应用...
夏德芳+刘传才
摘 要： 增强现实是一种虚实信息融合的技术。随着智能手机的普及，移动平台增强现实的应用开发成了热点。在智能手机硬件计算资源有限的情况下，基于人工标识的移动增强现实系统存在标识检测识别算法计算量大、配准跟踪实时性较差等缺陷。针对上述不足，提出了利用水漫填充法和外接矩形的几何特征快速检测标识4个角点，设计了基于海明编码特征的人工标识，提高了标识的识别速度，并具有一定的抗局部遮挡性能。为了精确快速地求解摄像机位姿，系统采用Levenberg?Marquardt算法优化求出的平面单应性矩阵。最终根据优化的单应性矩阵求解出摄像机位姿，并根据求出的位姿对虚拟物体加载渲染。实验结果表明该系统有良好的实时性和有效性。
关键词： 移动增强现实； 人工标识； 角点检测； 位姿估计
中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2015）08?0026?05
Fiducial marker based registration algorithm for mobile augmented reality
XIA De?fang， LIU Chuan?cai
（School of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing 210094， China）
Abstract： Augmented reality is the false and true information fusion technology. With the popularity of smart phones， application development of the mobile platform augmented reality has become a hot spot. Because the mobile augmented reality system based on fiducial marker has some defects of mass calculation and poor rectification tracking real?time performance of identification detection recognition algorithm in the case of limit hardware calculation resource of smart phone， a scheme to detect four corner points quickly by means of the flood?fill method and geometrical characteristics of bounding rectangle is proposed to reduce computation time. The fiducial marker based on hamming code was designed to improve the marker identification speed. In order to quickly and accurately compute the camera external parameters， the plane homography matrix was optimized by using Levenberg?Marquardt iterative algorithm， and then the rendering is loaded on the virtual object on fiducial marker according to the obtained camera external parameters. The experimental results show that the system has perfect real?time performance and effectiveness.
Keywords： mobile augmented reality； fiducial marker； corner detection； pose estimation
0 引 言
增强现实（Augmented Reality，AR）是伴随着计算机图形学、计算机视觉、多传感器技术和人机交互技术等领域的发展而产生的。增强现实系统借助上述技术将计算机生成的虚拟物体融合到用户周围的真实场景中去，使得用户从感官效果上确信虚拟物体是其周围真实场景的组成部分。早期的增强现实系统都是基于桌面电脑和头戴式显示设备。近些年，随着智能手机硬件和软件不断地升级换代，现有的智能手机包含了常用的传感器和摄像头显示屏等，使得智能手机天然地成为了移动增强现实（Mobile Augmented Reality，MAR）系统应用推广的最佳平台，如图1所示左边是一款移动增强现实投篮游戏、右上图是宜家公司推出的家具增强现实应用、右下图是奔驰公司推出的增强现实应用。
图1 移动增强现实应用
Azuma将增强现实总结为3大特点：虚实结合、实时交互、三维配准[1]。增强现实中要做到虚实结合的无缝性和实时性，就必须精确实时地计算出虚拟图形在真实世界中的位置（Position）和姿态（Pose），称之为位姿估计。位姿计算的方法主要有3种：基于传感器的跟踪技术，基于计算机视觉的跟踪技术和基于前两者技术的混合跟踪技术[1]。第1种方法利用各种传感器的信息获得用户或显示设备在真实环境中的位置和方向，常用的传感器有：GPS、加速度计和电子罗盘等；第2种方法基于计算机视觉的跟踪技术则是通过摄像头捕获的视频图像计算得到摄像机的位姿来实现虚拟结合。
基于视觉跟踪配准的增强现实系统中又可以分为基于标识的跟踪配准技术和无标识的跟踪配准技术。基于标识跟踪配准的增强现实系统，为了达到实时的、鲁棒的跟踪效果，一般是通过在场景中预先布置标识物来实现，标识物可分为人工标识和自然标识。人工标识易于识别跟踪，但破坏了场景的真实性。如由Hirokazu Kato博士开发、华盛顿大学HIT Lab维护的增强现实开发包ARToolKit是此类增强现实系统的典型代表[4]。自然特征标识的跟踪配准技术基于不变量的局部描述算子的特征识别及匹配方法，如SIFT，SURF和Freak等算法，克服了人工标识局部遮挡后无法识别的缺点，同时自然标识的使用使系统更加真实。但是自然标识的跟踪配准计算量大，智能手机有限的计算能力很难对自然标识进行实时跟踪。无标识的跟踪技术则可以实时地对环境进行特征检测、定位和重建，这种方法不需要预先存储标识的特征信息，适用于未知环境，计算更为复杂，其中SLAM和PTAM/M是此类技术的典型代表[5]。
因为智能手机计算资源有限，为了获得实时性的跟踪，本系统采用人工标识的跟踪技术。在基于人工标识的配准跟踪技术中，都是通过检测正方形4个角点的位置来估算摄像机的位姿，从而进行虚拟物体的加载。为了能够在智能手机上体验到实时的增强现实，提出了利用水漫填充法和外接矩形的几何特征直接快速检测标识4个角点，并采用Levenberg?Marquardt算法来优化求出的平面单应性矩阵。最终，根据优化的单应性矩阵，求解出摄像机的位姿为虚拟物体加载渲染。
1 摄像机模型
在增强现实系统中，为了使计算机产生的虚拟物体精确地加载到真实世界中，必须知道摄像机在真实世界坐标系中的位姿。如图2所示，在增强现实系统中，虚实配准常涉及3个坐标系的转换关系：世界坐标系、摄像机坐标系和图像坐标系。其中，图像坐标系又分为图像物理坐标系和图像像素坐标系。齐次坐标是计算机视觉和计算机图形学中重要的表示手段之一，它既能够用来明确区分向量和点，也能在仿射（线性）几何变换中使用[6]。齐次坐标是将原本n维的向量用一个n+1维向量表示。
[Zcuv1=αx0u000αyv000010RT0T1XwYwZw1] （1）
式（1）为真实世界坐标系到图像像素坐标系的转换公式，包括世界坐标系到摄像机坐标系的刚体转换、摄像机坐标系到图像物理坐标系的透视投影转换和图像物理坐标系到图像像素坐标系的转换。[αx=fdx，αy=fy]，其中f是摄像机固有的焦距，[αx， αy， u0， v0]都是摄像机内部参数，用K表示，这些参数只与摄像头内部结构有关系，可以通过标定技术得到这些内部参数[7]。R是一个3×3 正交矩阵，T是3×1的平移变量。摄像机相对于标识物的位置和方向就可以由旋转矩阵R和平移变量T来表示，这两个变量就是摄像机外部参数。
2 人工标识的设计和快速检测识别
2.1 人工标识的设计
人工标识的跟踪包括检测和识别。检测意味着检测到了候选标识，需进一步判断识别候选标识。因为不同的标识渲染可能对应不同的虚拟物体。目前人工标识的识别方法主要分为2种：基于图像模板匹配的标识识别和基于编码特征的标识识别[8]。基于图像模板匹配的标识具有可读性，标识本身带有一定的信息，例如ARToolKit中使用的标识，但需要将校正后的候选图像与3种光照条件下的4个方向上的标准图像模板进行逐一匹配，当候选标识有N个，则需要进行12×N次的模板匹配，这种方法计算量很大，影响增强现实系统实时性。
基于编码特征的标识识别通过对图像内部进行解码来识别标识，不仅提高了标识的识别速度，也增强了标识的可扩展性[8]。为了提高标识的识别效率，本文设计了一种基于编码特征的标识，如图3所示。
本系统中所用的人工标识如图3所示：标识最外围一圈是黑色边界，用于快速检测是否为候选标识。标识中心是5×5的栅格，每一行都是海明编码，第3位和第5位是有效码，其余3位是校验码，可以用来确定标识的方向和标识内的编码。这种设计方法总共可以标识1 024种不同标识ID。
2.2 人工标识的快速检测识别
由于智能手机计算资源的限制，标识的检测识别算法应该快速有效。现阶段常见的标识检测主要步骤是：输入图像二值化、连通区域寻找、对连通区域轮廓进行形状拟合、直线求交点获得4个角点，其中常常用到Hough变换、轮廓拟合等复杂计算量方法。如果简单地将桌面端的增强现实系统移植到移动平台，必然会降低系统的实时性能。因为大多数人工标识的增强现实系统都是通过检测四边形的四个角点求对应单应性矩阵的，所以本文提出利用区域填充法找到标识最大外接矩形，然后利用最大外接矩形和连通区域外轮廓来检测四个角点。算法主要步骤如下：
（1） 利用全局静态阈值将输入图像二值化；
（2） 从二值图像的左上角开始逐行扫描图像，直到遇到黑色像素为止；
（3） 将扫描到的黑色像素标记为已处理并设置为种子点，并在其周围创造一个外接矩形；
（4） 依次对种子点上下左右递归遍历，遇到黑色像素点就扩大外接矩形；
（5） 当没有黑色像素点能够被递归发现的时候，就找到了一个连通区域的最大外接矩形，这个外接矩形中就可能存在一个标识；
（6） 继续扫描，当再次扫描到未被处理过的黑色像素，则重复上面的步骤（3）和步骤（5）。
在检测4个角点之前，先将面积很小、纵横比较大的外接矩形去除掉。接下来检测外接矩形内连通区域的外轮廓上可能存在的4个角点。连通区域的外接矩形可能是正方形也可能是长方形，统一将外接矩形按比例缩放成正方形，然后依次从外接矩形的4个顶点出发，在连通区域中的轮廓中寻找距离每个顶点最远的一个点，作为检测到的角点。因为之前是将外接矩形尺度化正方形，所以检测到角点的具体坐标位置后，需要利用之前的尺度还原。如下图4所示是检测出的标识的4个角点。以上检测的是粗略地估计4个角点，当下一步确认标识合法以后，会进行角点亚像素级别的精确化检测。
接着利用4个角点，计算平面与平面之间的平面单应性矩阵，将标识图像校正到100×100像素的图像，并且将其二值化。可以将标识校正为更小的图像，加快标识的校正速度，但这可能会降低标识的识别率。随后，根据海明编码规则，为标识的4个方向解码，确定标识的正方向和内部编码。在Android平台上，实验检测了1 000帧的视频序列，计算了本文所提算法和ARToolKitPlus的平均检测时间和平均识别时间，结果如表1所示。
图5是抗遮挡性方面的对比示意图。图5（a）是本文算法实验结果，（b）是ARToolKitPlus算法实验结果。在抗遮挡性方面，ARToolKitPlus先天不足，因为ARToolKitPlus首先对连通区域外轮廓进行直线拟合，然后通过直线求交点检测到角点，所以一旦连通区域外轮廓形状发生细微改变都会检测失败。而本文所提出的角点检测算法并不是通过直线拟合求交点获得的，所以对标识局部遮挡具有一定的鲁棒性。本算法和ARToolKitPlus算法在遮挡情况下进行了对比实验。 本算法在局部浅色小遮挡情况下不会造成标识检测失败，当遮挡物的颜色接近于黑色时候，因为连通区域寻找失败，导致标识检测错误，如图5左下角标识被黑色钥匙局部遮挡后效果。 ARToolKitPlus的抗遮挡性能则很差，只要边缘被遮挡后，直线无法检测，则最终标识无法检测，如图5（b）所示。
3 摄像机参数求解
标识的内部编码决定了加载哪个虚拟物体，摄像机的外参数则决定了虚拟物体在屏幕中加载的位置。在多标识的系统中，每一个标识有独立的坐标系。因此，需计算摄像机相对于每一个标识的外参数。ARToolKit是通过标识外轮廓的4条边之间的关系来求解摄像机的外参数，往往会因为图像噪声导致的直线偏移而不能精确地计算出外参数[4]。为了精确快速地求解摄像机位姿，首先根据图像像素坐标系和世界坐标系对应的4对点，采用Levenberg?Marquardt算法来优化求出的平面单应性矩阵。最终，根据优化的单应性矩阵求解出摄像机位姿，并根据求出的位姿为虚拟物体加载渲染。在标识的角点检测过程中，由于角点的位置精度不够，需要精确地定位角点位置。使用OpenCV中的cornerSubPix函数将之前检测的4个角点位置精度提高到亚像素级别。
因为标识的4个角点都在世界坐标系Zw=0的平面上，所以可将式（1）改写为：
[Zcuv1=KR1R2T001XwYw1=HXwYw1H=h11h12h13h21h22h23h31h32h33] （2）
式中：H是3×3的平面单应性矩阵。将式（2）中的齐次系数Zc消去，可得式（3）：
[XwYw1000-uXw-uYw-u000XwYw1-vXw-vYw-vh11h12h13h21h22h23h31h32h33=0] （3）
式（3）是一个形如Ah=0的矩阵方程。当有n对对应的像素坐标系点和世界坐标系点时，则A是一个2n×9的矩阵。显然这是个线性齐次方程组，只需要4对图像像素点和世界坐标系点，就能解出H单应性矩阵。当超过4个相对应点的时，形成的是一个超定方程组，这是一个最优解问题。可以直接求解A矩阵的奇异值分解（SVD），对应于最小特征值的单位特征矢量即是解h矩阵。奇异值分解方法经常用来解决最小平方误差问题，这种方法算出来的h并没有考虑摄像机成像过程中的非线性畸变问题，为了提高精度，非线性最优化算法不可避免[8]。
采用Levenberg?Marquardt算法来优化单应性矩阵，这个算法是解决非线性最小二乘法的有效方法。它是Marquardt在Levenberg工作的基础上提出的一种迭代策略，是对Gauss?Newton方法的改进，相当于Gauss?Newton和梯度下降法的结合，具有良好的稳定性。可以建立以下优化目标函数：
[fh=ipi-HPi2] （4）
单应性矩阵优化旨在使通过单应性矩阵投影到图像的点与实际获得的图像点之间的几何误差最小，即式（4）中[pi]对应图像中实际测得的点，[HPi]则是世界坐标系中的点通过单应性矩阵投影到像素坐标系的坐标。
迭代增量式如式（5）所示：
[Δh=JThJh+uI-1JTf1h] （5）
式中：JT（h）是f（h）的雅克比矩阵；Δh是每次迭代的增量。通过迭代，可以最终确定单应性矩阵的最优解。通过上面计算优化出来的单应性矩阵以及事先标定好的摄像机内参数K，摄像机外参数可用下式求出：
[r1=ZcK-1h1r2=ZcK-1h2r3=r1×r2t=ZcK-1h3Zc=1K-1h1=1K-1h2] （6）
式中，通常称Zc为尺度因子；[R=r1r2r3]，单应性矩阵[H=h1h2h3]。根据以上得到的摄像机外参数将虚拟物体加载到标识上，效果如图6所示。
4 结 语
随着智能手机技术的发展和普及，移动增强现实技术必将为日常生活带来非同凡响的新体验。移动平台应用实时性等体验是最需要解决的问题，本文提出了一种基于人工标识的快速检测识别方法，通过实验，这种方法极大提高了增强现实应用的实时性，对于简单环境中的增强现实具有良好的用户体验。
参考文献
[1] AZUMA R. A survey of augmented reality [J]. Teleoperators and Virtual Environments， 1997， 6（4）： 355?385.
[2] 李玉，王涌天，刘越.基于彩色标志点的增强现实注册算法研究[J].系统仿真学报，2008，20（3）：654?656.
[3] BAGGIO Daniel Lélis， EMAMI S， ESCRIV? David Millán. Master OpenCV with practical computer vision projects [M]. [S.l.]： Packt Publishing， 2012： 46?92.
[4] KATO H， BILLINGHURST M. Marker tracking and HMD calibration for a video?based augmented reality conferencing system [C]// Proceedings of 2nd IEEE and ACM International Workshop on Augmented Reality. [S.l.]： IEEE， 1999： 85?94.
[5] DAVISON A J. Real?time simultaneous localisation and mapping with a single camera [C]// Proceedings of the Ninth IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2003： 1403?1406.
[6] 邱子鉴.基于改进随机蕨的增强现实注册算法的设计与实现[D].哈尔滨：哈尔滨理工大学，2014.
[7] ZHANG Z. Flexible camera calibration by viewing a plane from unknown orientations [C]// Proceedings of International Conference on Computer Vision. Corfu， Greece： ICCV， 1999： 666?673.
[8] GANDY M， MACINTYRE B. Designer's augmented reality toolkit， ten years later： implications for new media authoring tools [C]// Proceedings of the 27th annual ACM symposium on User interface software and technology. New York： ACM， 2014： 627?636.
[9] 张振杰.基于共面特征点的视觉导航位姿测定技术研究[D].郑州：解放军信息工程大学，2013.
[10] ALAHI A， ORTIZ R， VANDERGHEYNST P. FREAK： Fast retina key point [C]// Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]： IEEE， 2012： 510?517.
[11] 周国众.移动增强现实关键技术及应用[J].测绘与空间地理信息，2012，35（9）：141?144.
[12] 马颂德，张正友.计算机视觉：计算理论与算法基础[M].北京：科学出版社，1998.
[13] WANGER D. Handheld augmented reality [D]. Graz： Graz University of Technology， 2007.
