增强现实中的视频对象跟踪算法图文精.docx

1、增强现实中的视频对象跟踪算法图文精229增强现实中的视频对象跟踪算法陈 明，陈一民，黄诗华，姚争为(上海大学计算机工程与科学学院，上海 200072摘 要：根据增强现实在视频对象跟踪中的应用需求，提出一种综合利用尺度不变特征变换(SIFT算子、K 聚类算法和轮廓检测的视频对象跟踪算法。该算法利用简易SIFT 获得输入图像的特征点，通过K 聚类算法获得可能的对象聚类，并采用改进的轮廓处理方法得到对象边界，移除孤立点，确定对象特征点，在对象特征点中获取增强现实应用中需要的注册点。在关键帧匹配中，只要使用对象特征点进行对象匹配。实验结果表明，该算法具有运行速度快、匹配正确率高的特点，能满足增强现实视

2、频应用的注册需求。 关键词：增强现实；视频对象跟踪；尺度不变特征变换算子；K -means 算法；轮廓检测Video Object Tracking Algorithm for Augmented RealityCHEN Ming, CHEN Yi-min, HUANG Shi-hua, YAO Zheng-wei(School of Computer Engineering and Science, Shanghai University, Shanghai 200072【Abstract 】According to the application requirement of Augmen

3、ted Reality(AR in video object tracking, this paper proposes a video objecttracking algorithm based on Scale-Invariant Feature Transform(SIFT operator, K -means clustering algorithm and contour detection. The reducedSIFT is applied to get the feature points from the input image. The K -means cluster

4、ing algorithm is applied to cluster the object feature pointsapproximatively. The improved contour process is applied to get outlines from the clustered object feature points, removes isolation pointsand determines the object feature points. The registered point is got from the object feature points

5、 set. In the key frame, it only needs to usethe objectfeature points to match the object. Experimental results show that the algorithm is fast and accurate. It can meet the need of AR registering. 【Key words】augmented reality; video object tracking; Scale-Invariant Feature Transform(SIFT operator; K

6、 -means algorithm; contour detection计 算 机 工 程Computer Engineering第36卷 第12期Vol.36 No.12 2010年6月June 2010多媒体技术及应用 文章编号：10003428(201012022903文献标识码：A中图分类号：TN911.731 概述增强现实(Augmented Reality, AR是一种对真实世界信息和虚拟世界信息进行无缝集成的新技术。基于视频的AR 应用成本较低且便于在不同环境中使用，因此，近年来发展较快。在基于视频的AR 应用中，如何精确跟踪视频对象是一个重要问题，因为增强现实虚实融合的关键之一

7、是精确注册虚拟物体。基于视频的AR 应用通常需要将虚拟物体跟踪注册在一个实时拍摄的实际视频对象上。视频对象跟踪一直是计算机视觉的关键，如果一个视频序列的每幅关键帧图像都重复同样的跟踪算法，计算量将十分巨大。对于运动对象跟踪问题，Moscheni 等人提出利用空间、时间特性来描述运动对象，并实现对运动对象的分割与跟踪方法1。现有视频运动跟踪算法包括基于视频运动对象区域灰度等特征的跟踪算法、基于轮廓特征的跟踪算法、基于运动估计的跟踪算法和基于视觉学习的跟踪算法等2。snake 活动轮廓模型算法(Active Contour Model, ACM是一种较好的基于轮廓跟踪算法3，它定义一个与轮廓有关的

8、能量函数，轮廓的形状变化和行为变化趋向于使该能量函数值变小，直至能量函数取最小值时，轮廓形状定型且轮廓变化停止。在构造能量函数时只要正确考虑图像特征、目标特征，snake 轮廓就能收敛在图像中的目标上。但snake 及其改进算法与初始轮廓给定的位置密切相关，若给定的初始形状和位置不佳，则不易收敛或形状演化不正确，且要取得理想的轮廓效果，活动轮廓算法演化时间较长，不适合实时操作。因此，本文提出先利用特征点等方法求出图像对象的大致位置，再进行轮廓处理，而不将其作为确定对象的方法，仅用来演化大致轮廓，以去除不是对象的孤立特征点。尺度不变特征变换(Scale-Invariant Feature Tra

9、nsform, SIFT算法4是优秀的特征点计算与匹配算法，其匹配能力较强，能处理2幅图像之间发生平移、旋转、仿射变换时的匹配问题，因此，本文采用SIFT 方法来初步计算对象特征点。对于对象分类问题，采用快速的K 聚类方法来区分聚类特征点，K -means 聚类算法是一种分割式聚类方法，其主要目的是先在大量高维特征点中找出具有代表性的特征点，这些特征点可以称为类的中心代表点，然后根据这些聚类中心，进行后续处理。采用K 聚类算法的原因是该算法简单，且已被证明是最快的聚类算法之一。本文提出SIFT K 聚类轮廓跟踪算法(SIFT-K -means Contour Tracking, SIFT-K

10、-CT 。采用该算法时，在关键帧匹配中，只要使用对象特征点进行对象匹配即可。2 SIFT-K -CT 跟踪算法2.1 前提与假设本文仅在摄像机固定不变的情况下，检测视频运动对象的情况，该情况对于基于视觉的AR 应用是一种常见环境。 2.2 SIFT-K -CT 算法流程SIFT-K -CT 方法由2个部分组成：(1对象初始化识别。基金项目：国家科技支撑计划基金资助项目(2006BAK13B10；上海市重点学科建设基金资助项目(J50103作者简介：陈 明(1978 ，男，博士研究生，主研方向：多媒体 技术；陈一民，教授、博士生导师；黄诗华，硕士研究生；姚争为，博士研究生收稿日期：2010-01

11、-20 E-mail ：cmyes230先利用SIFT 算子计算出图像的特征点集，再利用K -means 聚类算法进行聚类操作。聚类数目最大的几个类作为对象识别的基础，由于K -means 算法可能产生一些不在对象中的孤立点，因此采用snake 算法来约束，仅需做几次迭代取出大概范围即可。由于snake 迭代基于K 聚类基础，避免了迭代收敛不正确的问题，且只要利用其去除不在对象中的孤立特征点，因此迭代次数约为10次。(2跟踪识别。利用SIFT 识别出的相关特征点与第(1部分识别出的对象点进行跟踪匹配，如果有3个以上的特征点匹配，则认为该对象是目标对象。如果无法确定目标对象，则认为对象不存在或重

12、新识别新的对象。识别对象成功后进入AR 应用流程。 2.2.1 对象初始化识别对象初始化识别过程如下： (1简易SIFT 检测简易SIFT 检测是加速SIFT 特征检测的过程，文献4建议对每个关键点使用44共16个种子点来描述，对于一个关键点就可以产生128个数据，即最终形成128维的SIFT 特征向量。由于下一步要对特征点进行分类，因此可以适度减少特征向量的维度。对同一幅关键帧图像的20次实验结果表明，使用338共72个维度即可。如果过于宽松，特征点数目增加过多，则必然增加K 聚类算法的运行时间。(2K -means 聚类K -means 聚类的目的是为了识别出对象的大概分布范围，为下一步s

13、nake 运算提供初始位置。K 聚类算法效率的关键是K 的初始值，如下：21arg min |j i Kj i i s S=x x u (1其中，j x 表示数据点的位置坐标向量；K 为分类数目，利用均方差最小进行聚类。对于增强现实运动目标跟踪应用，设置5K =就能完成分类。对于最大聚类是背景特征的情况，可以使用简单的背景减除技术来实现。原始关键帧图像如图1所示，图2给出了分类后的特征点分布结果。 图1 原始关键帧图像图2 SIFT-K -CT 聚类后的效果(3snake迭代主动轮廓模型又称为snake 模型，它主要定义了snake 积分能量函数，其能量函数包括内部能量、图像能量和外部能量。对

14、象跟踪的依据是使其所有能量函数积分最小。Kass 等人给出了利用变分法来求解积分最小的方法，可得能量函数如下：(, , (, , (, d d ob gr n n n An BnSe O x y O x y C x y x y = (2其中，(, obn O x y 表示视频对象；(, gr n O x y 表示背景；(, n C x y 表示2个区域之间的边界曲线。根据文献5提出的基于直方图的snake 视频跟踪方法，实际的偏微分方程如下： 1220(, (, , (, (0ob gr n n n nxP P O x y P O x y C x y n tC C=+=(3 其中，1P 为变化

15、内力；2P 为变化外力。根据式(3，从初始轮廓0C 出发，当t 充分大时，n C 收敛于局部极值，n C 就是目标轮廓。由于本文使用snake 的目的只是为了移除孤立于对象的聚类特征点，因此仅需要迭代20次就足够了，且不必过分关心演化情况，所以简化方程如下：0(, (, , (, (0ob grn n n nx O x y O x y C x y ntC C= (4 最终对象的特征点集如下：max ( j i i O Sn Km eSift I N = (5其中，j O 表示要跟踪的第j 个对象；i I 表示输入的第i 帧关键帧图像；eSift 函数表示简易SIFT 操作；Km 函数表示K -

16、means 聚类操作；max Km 表示取最大分类的点集；Sn 表示snake 移除操作；求和表示移除后的所有有效特征点集；i N 表示最少的对象点集，为匹配需要，3i N =。0j O 表示识别对象成功，否则，表示识别失败。如图3所示，对象外的孤立特征点已移除，不会再干扰对象跟踪过程。AR 注册效果如图4所示。 图3 SIFT-K -CT 对象特征识别效果 图4 AR渲染应用效果2.2.2 对象跟踪与匹配关键帧对象的跟踪与匹配有基于欧氏距离的方法、RANSAC 方法6等。欧氏距离法是最常用的方法，该方法利用关键点特征向量的欧式距离作为2幅图像中关键点的相似性判定度量。取一帧图像中的某个特征点

17、，并找出其与待匹配图像中欧式距离最近的前几个特征点，在这些点中，如果最近的距离与次近的距离比小于某个阈值，则认为匹配成功。如果降低这个阈值，SIFT 点匹配成功的数目会减少，但更加稳定。RANSAC 方法能处理错误率超过50%的数据，是最有效的Robust 估计算法之一，在计算机视觉等领域得到了广泛应用。 SIFT-K -CT 的匹配策略分2步进行，先使用RNASAC 算法进行匹配。如果无法成功匹配对象，则进行仿射不变特征匹配测试。利用马氏距离的仿射不变性7删除误匹配特征对，如式(6所示。SIFT 算法跟踪匹配效果和SIFT-K -CT 对象跟踪231匹配效果分别如图5和图6所示。 图5 SI

18、FT算法跟踪匹配效果 图6 SIFT-K -CT 对象跟踪匹配效果 21( 2( 1( /4, mi i i i Sd d d d = (6其中，m 是匹配点的对数，取m =1,2即可；Sd 表示协方差和；d i 表示马氏距离；A -1表示A 的逆矩阵，A 表示协方差矩阵。根据马氏距离定义，应有d 1=d 2, Sd =0。 2.2.3 AR注册应用AR 注册应用过程是从2D 图像坐标系到3D 相机坐标系映射的过程，包括注册点的确定和注册点方向矢量的确定 2个步骤。(1注册点位置估计注册点位置估计的目的是找出可能的渲染虚拟物体的位置。本文利用特征点的距离密度概率求核心点的聚类位置。n 00(

19、n ni i i i Max Max Dpr O = (7其中，n i Max 是估计的最大周围密度点；00n nii i O =是i 点周围半径n 中的所有对象特征点；Dpr 表示靠近模拟中心点的概率。 (2方向估计方向估计的目的是按正确的姿态渲染出虚拟物体。本文根据核心点周围特征点的SIFT 梯度平均方向求注册点的方向矢量。因此，在匹配时不宜使用简易SIFT 操作。为了有效地表征这些特征点，根据Lowe 提出的方法，先将原图像转化为梯度图像，计算每个元素的梯度幅值和方向量，再将所检测特征点的相应位置映射于梯度图像中，并设定一个有效的邻域范围(88，以区域内元素的梯度变化幅值为权重，计算方向

20、量的直方图，以此作为相应特征点的表征向量。3 实验结果与分析算法性能主要以跟踪精确度和时间效率2个指标来衡量。 3.1 算法对象跟踪利用SIFT 算法获取少量特征点，作为分类算法的输入，利用最快的K -means 分类算法对特征点进行分类，找到最大分类。可能存在最大分类是背景的情况，可以利用背景差分来解决。如图5所示，可以观察到很多错误匹配情况，无法跟踪对象。如图6所示，在背景变化的条件下，本文算法依然成功匹配、跟踪了手机对象。3.2 算法时间性能SIFT-K -CT 算法在跟踪时仅需要进行Canny 边缘检测，跟踪效果能够满足实时要求。不同算法的平均跟踪时间比较如表1所示，比较结果以10 s

21、视频设置30个关键帧图像匹配为例。图像分辨率为640480。ACM 算法以改进的snake 模型8为例。ASIFT 算法9的效果优于Harris-Affine 等算法效果较好，因此，本文以ASIFT 为例，不再比较其他类似算法。表1 不同算法的平均跟踪时间比较算法名称平均运行时间/sSIFT 0.3 ASIFT 30.0snake 0.5 SIFT-K -CT 0.14 结束语本文算法适用于对象跟踪精度要求高、有实时性要求、存在复杂背景的情况，如虚拟/增强现实与视频融合等环境。但该算法未考虑噪声较大的情况，仅采用简易的中值滤波，而没有预先进行滤波处理。另外，当图像精度不高时，该算法跟踪匹配能力

22、不足。下一步工作将尽量减少算法在对象跟踪过程中对图像精度的需要，以提高其适用范围。参考文献1 Denzler J, Niemann H. Combination of Simple Vision Modules forRobust Real Time Motion TrackingJ. European Transactions on Telecommunications, 1995, 6(3: 121-137.2 Trucco E, Plakas K. Video Tracking: A Concise SurveyJ. IEEEJournal of Oceanic Engineering,

23、 2006, 31(2: 520-529.3 陈 波, 赖剑煌. 用于图像分割的活动轮廓模型J. 中国图象图形学报, 2007, 12(1: 11-20.4 Lowe D G. Distinctive Image Features from Scale InvariantKeypointsJ. International Journal of Computer Vision, 2004, 60(2: 91-110.5 郭礼华, 袁晓彤, 李建华. 基于直方图的Snake 视频对象跟踪算法J. 中国图象图形学报, 2005, 10(2: 197-202.6 佟爱华, 周付根, 金 挺, 等. 一

24、种改进的高精度视频帧间匹配算法J. 仪器仪表学报, 2008, 29(8: 146-150.7 李玲玲, 李翠华, 曾晓明, 等. 基于Harris-affine 和SIFT 特征匹配的图像自动配准J. 华中科技大学学报: 自然科学版, 2008, 36(8: 13-16.8 Yue Fu, Erdem T A, Tekalp A M. Tracking Visible Boundary ofObjects Using Occlusion Adaptive Motion SnakeJ. IEEE Transactions on Image Processing, 2000, 9(12: 2051-2069. 9 Morel J M, Yu guoshen. ASIFT: A New Framework for Fully AffineInvariant Image ComparisonJ. SIAM Journal on Imaging Sciences, 2009, 2(2: 438-469.编辑 陈 晖