增强现实中的视频对象跟踪算法图文精.docx
《增强现实中的视频对象跟踪算法图文精.docx》由会员分享,可在线阅读,更多相关《增强现实中的视频对象跟踪算法图文精.docx(9页珍藏版)》请在冰点文库上搜索。
增强现实中的视频对象跟踪算法图文精
—229—
增强现实中的视频对象跟踪算法
陈明,陈一民,黄诗华,姚争为
(上海大学计算机工程与科学学院,上海200072
摘要:
根据增强现实在视频对象跟踪中的应用需求,提出一种综合利用尺度不变特征变换(SIFT算子、K聚类算法和轮廓检测的视频对象跟踪算法。
该算法利用简易SIFT获得输入图像的特征点,通过K聚类算法获得可能的对象聚类,并采用改进的轮廓处理方法得到对象边界,移除孤立点,确定对象特征点,在对象特征点中获取增强现实应用中需要的注册点。
在关键帧匹配中,只要使用对象特征点进行对象匹配。
实验结果表明,该算法具有运行速度快、匹配正确率高的特点,能满足增强现实视频应用的注册需求。
关键词:
增强现实;视频对象跟踪;尺度不变特征变换算子;K-means算法;轮廓检测
VideoObjectTrackingAlgorithmforAugmentedReality
CHENMing,CHENYi-min,HUANGShi-hua,YAOZheng-wei
(SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanghai200072
【Abstract】AccordingtotheapplicationrequirementofAugmentedReality(ARinvideoobjecttracking,thispaperproposesavideoobjecttrackingalgorithmbasedonScale-InvariantFeatureTransform(SIFToperator,K-meansclusteringalgorithmandcontourdetection.ThereducedSIFTisappliedtogetthefeaturepointsfromtheinputimage.TheK-meansclusteringalgorithmisappliedtoclustertheobjectfeaturepointsapproximatively.Theimprovedcontourprocessisappliedtogetoutlinesfromtheclusteredobjectfeaturepoints,removesisolationpointsanddeterminestheobjectfeaturepoints.Theregisteredpointisgotfromtheobjectfeaturepointsset.Inthekeyframe,itonlyneedstousetheobjectfeaturepointstomatchtheobject.Experimentalresultsshowthatthealgorithmisfastandaccurate.ItcanmeettheneedofARregistering.【Keywords】augmentedreality;videoobjecttracking;Scale-InvariantFeatureTransform(SIFToperator;K-meansalgorithm;contourdetection
计算机工程ComputerEngineering第36卷第12期
Vol.36No.122010年6月
June2010
·多媒体技术及应用·文章编号:
1000—3428(201012—0229—03
文献标识码:
A
中图分类号:
TN911.73
1概述
增强现实(AugmentedReality,AR是一种对真实世界信息和虚拟世界信息进行无缝集成的新技术。
基于视频的AR应用成本较低且便于在不同环境中使用,因此,近年来发展较快。
在基于视频的AR应用中,如何精确跟踪视频对象是一个重要问题,因为增强现实虚实融合的关键之一是精确注册虚拟物体。
基于视频的AR应用通常需要将虚拟物体跟踪注册在一个实时拍摄的实际视频对象上。
视频对象跟踪一直是计算机视觉的关键,如果一个视频序列的每幅关键帧图像都重复同样的跟踪算法,计算量将十分巨大。
对于运动对象跟踪问题,Moscheni等人提出利用空间、时间特性来描述运动对象,并实现对运动对象的分割与跟踪方法[1]。
现有视频运动跟踪算法包括基于视频运动对象区域灰度等特征的跟踪算法、基于轮廓特征的跟踪算法、基于运动估计的跟踪算法和基于视觉学习的跟踪算法等[2]。
snake活动轮廓模型算法(ActiveContourModel,ACM是一种较好的基于轮廓跟踪算法[3],它定义一个与轮廓有关的能量函数,轮廓的形状变化和行为变化趋向于使该能量函数值变小,直至能量函数取最小值时,轮廓形状定型且轮廓变化停止。
在构造能量函数时只要正确考虑图像特征、目标特征,snake轮廓就能收敛在图像中的目标上。
但snake及其改进算法与初始轮廓给定的位置密切相关,若给定的初始形状和位置不佳,则不易收敛或形状演化不正确,且要取得理想的轮廓效果,活动轮廓算法演化时间较长,不适合实时操作。
因此,本文提出先利用特征点等方法求出图像对象的大致位置,再进行轮廓处理,而不将其作为确定对象的方法,仅用来演
化大致轮廓,以去除不是对象的孤立特征点。
尺度不变特征变换(Scale-InvariantFeatureTransform,SIFT算法[4]是优秀的特征点计算与匹配算法,其匹配能力较强,能处理2幅图像之间发生平移、旋转、仿射变换时的匹配问题,因此,本文采用SIFT方法来初步计算对象特征点。
对于对象分类问题,采用快速的K聚类方法来区分聚类特征点,K-means聚类算法是一种分割式聚类方法,其主要目的是先在大量高维特征点中找出具有代表性的特征点,这些特征点可以称为类的中心代表点,然后根据这些聚类中心,进行后续处理。
采用K聚类算法的原因是该算法简单,且已被证明是最快的聚类算法之一。
本文提出SIFTK聚类轮廓跟踪算法(SIFT-K-meansContourTracking,SIFT-K-CT。
采用该算法时,在关键帧匹配中,只要使用对象特征点进行对象匹配即可。
2SIFT-K-CT跟踪算法
2.1前提与假设
本文仅在摄像机固定不变的情况下,检测视频运动对象的情况,该情况对于基于视觉的AR应用是一种常见环境。
2.2SIFT-K-CT算法流程
SIFT-K-CT方法由2个部分组成:
(1对象初始化识别。
基金项目:
国家科技支撑计划基金资助项目(2006BAK13B10;上海市重点学科建设基金资助项目(J50103
作者简介:
陈明(1978-,男,博士研究生,主研方向:
多媒体技术;陈一民,教授、博士生导师;黄诗华,硕士研究生;姚争为,博士研究生
收稿日期:
2010-01-20E-mail:
cmyes@
—230
—先利用SIFT算子计算出图像的特征点集,再利用K-means聚类算法进行聚类操作。
聚类数目最大的几个类作为对象识别的基础,由于K-means算法可能产生一些不在对象中的孤立点,因此采用snake算法来约束,仅需做几次迭代取出大概范围即可。
由于snake迭代基于K聚类基础,避免了迭代收敛不正确的问题,且只要利用其去除不在对象中的孤立特征点,因此迭代次数约为10次。
(2跟踪识别。
利用SIFT识别出的相关特征点与第(1部分识别出的对象点进行跟踪匹配,如果有3个以上的特征点匹配,则认为该对象是目标对象。
如果无法确定目标对象,则认为对象不存在或重新识别新的对象。
识别对象成功后进入AR应用流程。
2.2.1对象初始化识别
对象初始化识别过程如下:
(1简易SIFT检测
简易SIFT检测是加速SIFT特征检测的过程,文献[4]建议对每个关键点使用4×4共16个种子点来描述,对于一个关键点就可以产生128个数据,即最终形成128维的SIFT特征向量。
由于下一步要对特征点进行分类,因此可以适度减少特征向量的维度。
对同一幅关键帧图像的20次实验结果表明,使用3×3×8共72个维度即可。
如果过于宽松,特征点数目增加过多,则必然增加K聚类算法的运行时间。
(2K-means聚类
K-means聚类的目的是为了识别出对象的大概分布范围,为下一步snake运算提供初始位置。
K聚类算法效率的关键是K的初始值,如下:
21argmin||||jiK
jiisS
=∈−∑∑xxu(1
其中,jx表示数据点的位置坐标向量;K为分类数目,利用均方差最小进行聚类。
对于增强现实运动目标跟踪应用,设置5K=就能完成分类。
对于最大聚类是背景特征的情况,可以使用简单的背景减除技术来实现。
原始关键帧图像如图1所示,图2给出了分类后的特征点分布结果。
图1原始关键帧图像
图2SIFT-K-CT聚类后的效果
(3snake迭代
主动轮廓模型又称为snake模型,它主要定义了snake积分能量函数,其能量函数包括内部能量、图像能量和外部能量。
对象跟踪的依据是使其所有能量函数积分最小。
Kass等人给出了利用变分法来求解积分最小的方法,可得能量函数如下:
((,,(,,(,ddobgrnnnAnBn
SeOxyOxyCxyxy=∫∫(2
其中,(,ob
nOxy表示视频对象;(,grnOxy表示背景;(,
nCxy表示2个区域之间的边界曲线。
根据文献[5]提出的基于直方图的snake视频跟踪方法,实际的偏微分方程如下:
1220[((,((,,(,](0obgrnnnn
x
PPOxyPOxyCxynt
CC
∂⎧=+−⎪
∂⎨⎪=⎩(3其中,1P为变化内力;2P为变化外力。
根据式(3,从初始轮
廓0C出发,当t充分大时,nC收敛于局部极值,nC就是目标轮廓。
由于本文使用snake的目的只是为了移除孤立于对象的聚类特征点,因此仅需要迭代20次就足够了,且不必过分关心演化情况,所以简化方程如下:
0[((,((,,(,](0obgr
nnnn
xOxyOxyCxyn
t
CC
∂⎧=−⎪∂⎨⎪=⎩(4最终对象的特征点集如下:
max(((jiiOSnKmeSiftIN=>∑(5
其中,jO表示要跟踪的第j个对象;iI表示输入的第i帧关键帧图像;eSift函数表示简易SIFT操作;Km函数表示K-means聚类操作;maxKm表示取最大分类的点集;Sn表示snake移除操作;求和表示移除后的所有有效特征点集;iN表示最少的对象点集,为匹配需要,3iN=。
0jO≥表示识别对象成功,否则,表示识别失败。
如图3所示,对象外的孤
立特征点已移除,不会再干扰对象跟踪过程。
AR注册效果如图4所示。
图3SIFT-K-CT对象特征识别效果
图4AR渲染应用效果
2.2.2对象跟踪与匹配
关键帧对象的跟踪与匹配有基于欧氏距离的方法、RANSAC方法[6]等。
欧氏距离法是最常用的方法,该方法利用关键点特征向量的欧式距离作为2幅图像中关键点的相似性判定度量。
取一帧图像中的某个特征点,并找出其与待匹配图像中欧式距离最近的前几个特征点,在这些点中,如果最近的距离与次近的距离比小于某个阈值,则认为匹配成功。
如果降低这个阈值,SIFT点匹配成功的数目会减少,但更加稳定。
RANSAC方法能处理错误率超过50%的数据,是最有效
的Robust估计算法之一,
在计算机视觉等领域得到了广泛应用。
SIFT-K-CT的匹配策略分2步进行,先使用RNASAC算法进行匹配。
如果无法成功匹配对象,则进行仿射不变特征匹配测试。
利用马氏距离的仿射不变性[7]删除误匹配特征对,
如式(6所示。
SIFT算法跟踪匹配效果和SIFT-K-CT对象跟踪
—231—
匹配效果分别如图5和图6所示。
图5SIFT算法跟踪匹配效果
图6SIFT-K-CT对象跟踪匹配效果
2
1(2(1
(/4,m
iiiiSdddd==−∑(6
其中,m是匹配点的对数,取m=1,2即可;Sd表示协方差和;di表示马氏距离;A-1表示A的逆矩阵,A表示协方差矩阵。
根据马氏距离定义,应有d1=d2,Sd=0。
2.2.3AR注册应用
AR注册应用过程是从2D图像坐标系到3D相机坐标系映射的过程,包括注册点的确定和注册点方向矢量的确定2个步骤。
(1注册点位置估计
注册点位置估计的目的是找出可能的渲染虚拟物体的位置。
本文利用特征点的距离密度概率求核心点的聚类位置。
n00
((nn
iiiiMaxMaxDprO===∑∑(7
其中,niMax是估计的最大周围密度点;00
nn
i
iiO==∑∑是i点周围半径n中的所有对象特征点;Dpr表示靠近模拟中心点的概率。
(2方向估计
方向估计的目的是按正确的姿态渲染出虚拟物体。
本文根据核心点周围特征点的SIFT梯度平均方向求注册点的方向矢量。
因此,在匹配时不宜使用简易SIFT操作。
为了有效地表征这些特征点,根据Lowe提出的方法,先将原图像转化为梯度图像,计算每个元素的梯度幅值和方向量,再将所检测特征点的相应位置映射于梯度图像中,并设定一个有效的邻域范围(8×8,以区域内元素的梯度变化幅值为权重,计算方向量的直方图,以此作为相应特征点的表征向量。
3实验结果与分析
算法性能主要以跟踪精确度和时间效率2个指标来衡量。
3.1算法对象跟踪
利用SIFT算法获取少量特征点,作为分类算法的输入,利用最快的K-means分类算法对特征点进行分类,找到最大分类。
可能存在最大分类是背景的情况,可以利用背景差分来解决。
如图5所示,可以观察到很多错误匹配情况,无法跟
踪对象。
如图6所示,在背景变化的条件下,本文算法依然成功匹配、跟踪了手机对象。
3.2算法时间性能
SIFT-K-CT算法在跟踪时仅需要进行Canny边缘检测,跟踪效果能够满足实时要求。
不同算法的平均跟踪时间比较如表1所示,比较结果以10s视频设置30个关键帧图像匹配为例。
图像分辨率为640×480。
ACM算法以改进的snake模型[8]为例。
ASIFT算法[9]的效果优于Harris-Affine等算法效
果较好,因此,本文以ASIFT为例,不再比较其他类似算法。
表1不同算法的平均跟踪时间比较
算法名称
平均运行时间/s
SIFT0.3ASIFT30.0
snake0.5SIFT-K-CT0.1
4结束语
本文算法适用于对象跟踪精度要求高、有实时性要求、
存在复杂背景的情况,如虚拟/增强现实与视频融合等环境。
但该算法未考虑噪声较大的情况,仅采用简易的中值滤波,而没有预先进行滤波处理。
另外,当图像精度不高时,该算法跟踪匹配能力不足。
下一步工作将尽量减少算法在对象跟踪过程中对图像精度的需要,以提高其适用范围。
参考文献
[1]DenzlerJ,NiemannH.CombinationofSimpleVisionModulesfor
RobustRealTimeMotionTracking[J].EuropeanTransactionsonTelecommunications,1995,6(3:
121-137.
[2]TruccoE,PlakasK.VideoTracking:
AConciseSurvey[J].IEEE
JournalofOceanicEngineering,2006,31(2:
520-529.
[3]陈波,赖剑煌.用于图像分割的活动轮廓模型[J].中国图象图
形学报,2007,12(1:
11-20.
[4]LoweDG.DistinctiveImageFeaturesfromScaleInvariant
Keypoints[J].InternationalJournalofComputerVision,2004,60(2:
91-110.
[5]郭礼华,袁晓彤,李建华.基于直方图的Snake视频对象跟踪算
法[J].中国图象图形学报,2005,10(2:
197-202.
[6]佟爱华,周付根,金挺,等.一种改进的高精度视频帧间匹配
算法[J].仪器仪表学报,2008,29(8:
146-150.
[7]李玲玲,李翠华,曾晓明,等.基于Harris-affine和SIFT特征匹
配的图像自动配准[J].华中科技大学学报:
自然科学版,2008,36(8:
13-16.
[8]YueFu,ErdemTA,TekalpAM.TrackingVisibleBoundaryof
ObjectsUsingOcclusionAdaptiveMotionSnake[J].IEEETransactionsonImageProcessing,2000,9(12:
2051-2069.[9]MorelJM,Yuguoshen.ASIFT:
ANewFrameworkforFullyAffine
InvariantImageComparison[J].SIAMJournalonImagingSciences,2009,2(2:
438-469.
编辑陈晖