增强现实中的视频对象跟踪算法概要

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

2、；视频对象跟踪；尺度不变特征变换算子；K -means算法;轮廓检测Video Object Track ing Algorithm for Augme nted RealityCHEN Mi ng, CHEN Yi-mi n, HUANG Shi-hua, YAO Zhe ng-wei（School of Computer Engin eeri ng and Scie nee, Shan ghai Uni versity, Shan ghai 200072【Abstract 】 According to the application requirement of Augmented Rea

3、lity(AR in video object track ing, this paper proposes a video object track ing algorithm based on Scale-I nv aria nt Feature Tran sform(SIFT operator, K -mea ns clusteri ng algorithm and con tour detectio n. The reduced SIFT is applied to get the feature poi nts from the in put image. The K -means

4、clustering algorithm is applied to cluster the object feature points approximatively. The improved con tour process is applied to get outl ines from the clustered object feature poin ts, removes isolati on poi nts and determ ines the object feature points. The registered point is got from the object

5、 feature points set. In the key frame, it on ly n eeds to use the object feature points to match the object. Experime ntal results show that the algorithm is fast and accurate. It can meet the n eed of AR registeri ng【Key words 】augme nted reality; video object track ing; Scale-I nv aria nt FeatureT

6、ran sform(SIFT operator; K -mea ns algorithm; con tour detect ion计算机工程Computer Engineering第36卷第12期Vol.36 No.12 2010 年 6 月June 2010多媒体技术及应用文章编号：1000 3428(201012-0229 03文献标识码:A中图分类号:TN911.731概述增强现实(Augmented Reality, AR是一种对真实世界信息和虚拟世界信息进行 无缝集成的新技术。基于视频的 AR应用成本较低且便于在不同环境中使用，因此， 近年来发展较快。在基于视频的 AR应用中，如何精

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

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

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

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

11、授、博士 生导师;黄诗华，硕士研究生;姚争为，博士研究生收稿日期：2010-01-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建议对每个关键点使用 4>4共16个种子点来描述，对于一个关键点就可以产生128个数据，即最终形成128 维的SIFT特征向量。由于下一步要对特征点进行分类，因此可以适度减少特征向量 的维度。对同一幅关键帧图像的 20次实验结果表明，使用3X3X8共72个维度即 可。如果过于宽松，特征点数目增加过多，则必然增加K聚类算法的运行时间。（2K -mea

13、 ns 聚类K -means聚类的目的是为了识别出对象的大概分布范围，为下一步snake运算提供初始位置。K聚类算法效率的关键是K的初始值，如下：21arg min |j i Kj i i s S其中,j x表示数据点的位置坐标向量;K为分类数目，利用均方差最小进行聚对于增强现实运动目标跟踪应用，设置5K =就能完成分类。对于最大聚类是背 景特征的情况，可以使用简单的背景减除技术来实现。原始关键帧图像如图1所示,图2给出了分类后的特征点分布结果。图1原始关键帧图像图2 SIFT-K-CT聚类后的效果(3sn ake 迭代主动轮廓模型又称为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个区域之间的边界曲线。根据文献提出的基于直方图的snake视频跟踪方法，实际的偏微分方程如下：1220(,(,(,(0ob gr n nn nxP P O x y P O x y C x y n tC C? =+_ ? =?

15、(3其中,1P为变化内力；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

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

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

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

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

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

21、CM算法以改进的snake模型8为 例。ASIFT算法9的效果优于Harris-Affine等算法效果较好，因此，本文以ASIFT为例，不再比较其他类似算法表1不同算法的平均跟踪时间比较算法名称平均运行时间/SSIFT 0.3 ASIFT 30.0snake 0.5 SIFT-K -CT 0.14结束语本文算法适用于对象跟踪精度要求高、有实时性要求、存在复杂背景的情况，如虚拟/增强现实与视频融合等环境。但该算法未考虑噪 声较大的情况，仅采用简易的中值滤波，而没有预先进行滤波处理。另外，当图像精度 不高时，该算法跟踪匹配能力不足。下一步工作将尽量减少算法在对象跟踪过程中 对图像精度的需要，以提高其适用范围。参考文献1 Den zler J, Niema nn H. Comb in atio n of Simple Visio n Modules forRobust Real Time Moti on Tracki ngJ. Europea n Tran sacti ons onTelecommunications, 1995, 6(3: 121-137.2 Trucco E, Plakas K. Video Tracking: A Concise SurveyJ. IEEEJournal of Oceanic Engineering, 2006, 31(2