一种无标识图像的FLANN-LM配准算法

张乃千，王占刚

(北京信息科技大学 信息与通信工程学院，北京 100192)

0 引言

增强现实(augmented reality，AR)是一种实时地将摄像机角度、位置及相应图像、视频、3D模型叠加计算的新兴领域，用来完善用户与现实世界交互的感官体验。传统的增强现实大多使用基于人工标识的跟踪注册技术，需要检测有一定特征的标志物。虽然能较好地抵抗干扰，但是应用范围受到大幅限制。

3D跟踪注册技术是增强现实技术的根本，而其关键技术是提取与匹配特征点，所以，寻找一种同时兼顾旋转不变性、尺度不变性又伴随鲁棒性强、精确性高、实时性好的特征检测匹配算法是增强现实系统不可或缺的存在。早期的 Harris角点检测[1]实时性、鲁棒性好，但不具备尺度不变性；Lee等[2]提出了基于尺度不变特征SIFT(scale-invariant feature transform)算子的特征检测算法，较好地解决了图像在不同尺寸、旋转、光照等条件下的匹配失败问题，但速度很慢；Chen等[3]提出了加速稳健特征SURF(speed up robust features)算子，在一定程度上提高了处理速度，但降低了准确性；Michael Calonder 等[4]提出了BRIEF (binary robust independent elementary features)算法，该算法高效简单，但易受噪声影响，不具备尺度不变性及旋转不变性；Rublee[5]提出了ORB (ORIENTED BRIef) 算法，这是一种高效的二进制局部特征描述算子，ORB算法虽在速度上有了很大提升，却仍然没有解决好图像光照、纹理变化对注册精度的影响；Alexandre Alahi 等[6]提出 了FREAK算法，该二进制描述符以人类视网膜获取图像为基础，利用由模糊到清晰、扫视搜索的匹配方法，更好地满足了对光照、旋转等变化的适应性，同时完善了对于实时性的追求。在上述算法的基础上，本文以图像在自然特征下的虚实注册为基础，运用SURF算法提取特征点，使用FREAK算法描述图像特征点，利用FLANN-LM算法匹配特征点，完成整个增强现实系统的跟踪注册过程，并在此基础上完成三维模型的融合叠加。

1 提取特征点

摄像头采集到图像后首先运用SURF算法提取特征点，FREAK算法描述特征点，接着运用FLANN算法粗匹配，最后运用LM算法剔除错误匹配点提升匹配精度。图像识别与匹配算法流程如图1所示。

图1 图像识别与匹配算法流程

1.1 SURF特征点检测及尺度空间的构建

SURF算法利用H(X,σ)检测图像特征点[7]。图像I(x,y)中，尺度为σ的点x的Hessian矩阵为

(1)

式中Lxx、Lxy、Lyy为二阶微分算子。

为简化计算，SURF算法利用尺度图像积分获取高斯二阶微分函数的近似结果，组成图像金字塔，完成多尺度空间的构建[8]。其中，用加权的9×9框状滤波器模板Dxx、Dxy、Dyy代替原来的二阶微分算子，其中图形积分过程如图2所示。

图2 高斯滤波器与框状滤波器

简化后的Hessian矩阵的行列式为

det(H)=DxxDyy-(0.9Dxy)2

(2)

Hessian矩阵的迹为

tr(H)=Dxx+Dyy

(3)

确定特征点的位置可以采用非极大值抑制[9]。为简化计算，求主曲率D与特征值的比值rratio。假设最大特征值记为α，最小特征值记为β，且α=rβ，则比值rratio可表示为

(4)

1.2 FREAK特征描述子

FREAK算法是根据人眼识别物体提出的，其描述子的采样点与视网膜结构类似，采样点和特征点分别均匀分布在小圆和大圆圆心上。FREAK描述子每个圆圈代表一块感受野，重叠的感受野可以获取更多信息，具有更好的性能。

由于FREAK特征描述子是由0、1组成的二进制描述符，采样点的二值描述[10]可以通过对比采样点附近一组点对的强度得到：

(5)

(6)

为保证算法具有旋转不变形性，一般以梯度作为特征点主方向，特征点方向集合如图3所示。

图3 特征点方向集合

特征点计算方法如下：

(7)

2 FLANN-LM配准图像

2.1 FLANN匹配搜索

Hamming距离[11]是比较等长字符串上不同字符数量，即特征描述子间的相似程度，因此可以用Hamming距离衡量配准图像与参考图像间的关系。由于匹配的准确性与阈值T有关，根据参考文献[12]对快速二进制高维最近邻FLANN算法的描述，其关键在于快速找到特征点的近邻点。若最近邻与次近邻的特征点p、q的欧式距离用Dp和Dq表示，则Dp与Dq的比值为Dr=Dp/Dq。将该比值与阈值T作比较，若Dr小于T则匹配成功，否则匹配失败。FLANN匹配算法在保证匹配精度的同时，能有效减少计算量，提高匹配速度。

2.2 求解相机内外参数值

根据摄像机的成像模型可知[13]，若一个二维点坐标m=[u,v]T和一个三维点M=[X,Y,Z]T存在投影关系，则该三维点M与其图像投影点m的关系可以表示为

(8)

增强现实系统中[14]，使用相机模型建立二维图像点与相机视觉三维空间点的联系。转换模型共涉及4种坐标系，世界坐标系(XwYwZw)可以从现实世界中获得，相机坐标系(XcYcZc)以相机光心为原点，图像坐标系(OIXY)以图像平面的中心为原点。整个转换过程如图4所示。

图4 坐标系的相互转换

根据上述坐标系变换，可得到世界坐标系与图像坐标系间的转换关系

(9)

式中：fx、fy、u0、v0为摄像机的内部参数；M为内参矩阵。该矩阵实现了二维坐标与三维坐标间的转换。

由于标定棋盘位于世界坐标系中的Zw=0平面[15]，因此，可将式(8)按照式(9)的形式改写成

(10)

其中，矩阵H为世界坐标系转换到图像坐标系3×3的单应性矩阵：

(11)

式中1为归一化后的结果。这样矩阵只包含8个未知数，达到了简化计算的目的。将式(11)代入式(8)化简可得：

(12)

根据式(12)化简可得：

(13)

式中：

(14)

将式(13)用Ah=0的矩阵形式描述，要想求解H至少需要4组对应的世界坐标系点和图像坐标系点，但在真实场景中计算点对会包含如像素偏差或特征点匹配错误等噪声，一般都会选取远大于4组匹配点对求解单应性矩阵。由于单硬性矩阵的求解过程中涉及到最优解求解问题，因此运用非线性最小二乘法[16]优化误差函数，得到单硬性矩阵H。

2.3 LM算法剔除错误匹配点

LM(levenberg-marquardt)算法是在高斯牛顿算法的基础上得到的，是梯度下降算法与高斯牛顿算法的结合，该算法稳定性高[17]、速度快，适合运用在对实时性要求高的增强现实系统中。

用最大似然估计最小化真实值与标定点间的差异后，建立优化目标函数

(15)

为了减小图像标定点ECi与图像实测点Ci位置的噪声误差，本文通过求解迭代增量确定单应性矩阵的最优解，并判断该特征点是否可以作为匹配特征点。根据LM算法将迭代增量改写为

Xn+δxn⟹

(16)

在迭代过程中，给定初始值k=0，ε0=10-3。判断得到的Δhlm是否使得误差减小，若减小则保留；将ε除以10，否则将ε乘以10，重新求解方程，直到误差减小为止。

LM算法进一步剔除了误配的特征点，图像匹配的准确性得到了良好的改善，有助于提升图像虚实融合的精度。

通过优化得到的单应性矩阵及已经标定的摄像机内参A可以很容易地求解摄像机外参：

(17)

式中：A为摄像机内参矩阵；h1、h2、h3为单应性矩阵；r1、r2、r3是正交旋转矩阵R的参数；T为平移变换矩阵。

3 实验仿真及运行结果

本文的实验环境：电脑Intel(R)CPU为Core (TM)i7-2600，主频为3.40 GHz，内存4.00 GB，win7系统, 以Visual Studio 2013为主要平台，利用OpenCV图像处理工具、OpenGL三维图形库进行开发，并配合使用Unity3D加入FBX三维模型文件，最终完成基于FLANN-LM配准算法的虚实融合实验。

3.1 目标识别与匹配效果实验

在特征点的提取与匹配实验中，对同一幅图像改变旋转角度、遮挡特征点，比较本文算法与传统SURF- RANSAC、SURF-FREAK-RANSAC算法得到的匹配效果。

图像旋转时，特征点匹配效果如图5所示。

图5 图片旋转时不同配准算法比较

从图5可以看出，图像发生旋转时，传统SURF方法经过RANSAC处理后，匹配到的特征点数量较少，不适合增强现实系统的应用。SURF-FREAK-RANSAC虽然部分提升了特征点匹配的准确性，但在图像旋转时，错误匹配点没有剔除干净。而用本文算法匹配特征点，匹配精度较前2种算法明显提高。

遮挡部分图像特征，特征点匹配效果如图6所示。

图6 图片遮挡时不同配准算法比较

从图6可以看出，图像发生遮挡时，经过RANSAC处理的图像特征点匹配数量少，不利于增强现实系统虚实融合实验的进行。使用SURF-FREAK-RANSAC匹配特征点准确性明显提高，但仍有个别特征点匹配错误，导致增强现实系统的三维模型无法正确叠加。而本文算法的匹配准确性及抗干扰性较前2种传统算法有明显提高，更有利于图像进行虚实融合。

比较本文算法与传统方法在图片旋转、遮挡的平均时间及匹配准确率，对比结果如表1所示。

表1 算法性能对比

从表1可以看出，本文算法SURF-FREAK-FLANN- LM在运行速度上比传统的SURF-RANSAC算法提高约2倍，比SURF-FREAK-RANSAC方法提升约1.4倍，匹配的准确性更是达到了91.2%，满足了增强现实系统对实时性和稳定性的要求。

3.2 虚实融合叠加实验结果

完成图5、图6特征点的匹配与剔除后，对该识别图进行三维叠加，实现增强现实渲染，论证本文方法的可行性。

实验共分为3组，第一组：不增加任何干扰且不增加纹理直接识别图片，验证实验的可行性。第二组：图片发生旋转并给模型增加纹理贴图。第三组：图片发生遮挡并给模型增加纹理贴图。

无干扰无纹理直接识别图片，并叠加不同的三维模型，虚实注册结果如图7 所示。

图7 直接识别图片叠加三维模型效果

为验证本文算法的可行性，即更清晰看出三维模型和要识别的物体，本组实验分别将无纹理的椅子模型、仙人掌模型及电脑模型叠加到识别图的侧面位置。从图7可以看出，本方法可以很好地完成增强现实系统的虚实融合实验。

旋转角度发生变化时，虚实注册结果如图8所示。

图8 图片发生旋转三维模型叠加效果

图8是识别图顺时针或逆时针旋转90度时，识别并叠加三维模型的虚实融合效果，根据实验结果可以看出改变识别图旋转角度仍可以很好地实现跟踪注册。

特征点发生遮挡时，虚实注册结果如图9所示。

图9 图片发生遮挡三维模型叠加效果

图9为特征点发生遮挡时的跟踪注册效果，以白色纸条为遮挡物，在遮挡一部分特征点时，以上3幅图仍可以很好地实现增强现实系统的虚实渲染实验。

本文方法在改变图片旋转角度和遮挡特征点的情况下均能较好地实现图像的虚实融合。另外，除了抗干扰性能的提升，系统的实时性也得到了有效地改善，能更好地满足不同实验对象的应用条件。

4 结束语

为了加强人类对于真实世界的感官体验，本文以实现不同对象的增强现实应用为背景，改善增强现实系统匹配效果差和运行速率慢的问题。本文提出以SURF算法为依据，配合使用FREAK算法描述特征点，利用FLANN及LM算法剔除错误特征点，完成特征点的匹配与筛选，实现特征图的识别与叠加。实验证明，该算法具有较好的抗干扰性、稳定性及实时性，适用于图像自然特征的虚实融合场景，以此完善用户对现实世界与虚拟世界的交互体验，具有一定的参考与应用价值。