（计算机应用技术专业论文）视频图像中运动目标跟踪有关算法的研究.pdf

捅姜 视频目标跟踪融合了图像处理、模式识别、人工智能、自动控制、计算机 应用、生理学、物理学、数学等相关领域的先进技术和研究成果，具有可视性， 抗干扰，成本低等优点，已被广泛的应用到军事监控、交通管制、机器智能、 医疗诊断等方面。随着各种复杂环境应用领域的不断需求，除了引入各种新的 技术外，如何提高现有跟踪算法的精度以及鲁棒性也是当前目标跟踪领域研究 的重点。 本文详细的介绍m e a n s h i f t 算法在目标跟踪领域中的应用方法，针对信息度 较少的直方图特征引入了空间位置信息加权的目标特征表示方法。通过对 m e a n s h i f t 算法跟踪效果的分析，得出m e a n s h i f l 算法固有的缺陷。本文主要的 工作是对其固有的缺陷提出了两个方面的改进。 首先，针对m e a n s h i f t 算法不能处理目标完全遮挡的情况，提出了k a l m a n 滤波和m e a n s h i f l 算法相结合的方法，利用k a l m a n 滤波预测目标在当前帧中可 能出现的位置，然后利用m e a n s h i f t 算法在其邻域搜索。本文将目标被遮挡情况 分为无遮挡、部分遮挡和完全遮挡三种状态，采用k a l m a n 的残差来判定目标的 被遮挡的状态。目标进入完全遮挡状态，利用线性运动特征预测其位置。针对 动态更新模板，提出了引入实例推理机制的方案，有效的解决遮挡中模板动态 适应的问题。 另外，引入了动态自适应核窗口的方法叫a m s h i f t 算法，采用h s v 颜色 模型，有效的解决了m e a n s h i f l 算法中固定核窗口的问题，同时也有效的解决了 m e a n s h i f t 算法对光照敏感的问题；采用椭圆搜索窗口，提高了跟踪的目标旋转 形变问题的精度。最后本文提出了一种基于c a m s h i f t 算法的全自动目标跟踪策 略，有效的减少由于手工选取目标引起的误差。 关键字：目标跟踪，均值平移，卡尔曼滤波，完全遮挡，c a m s h i f t 。 a b s t r a c t m o v i n go b j e c tt r a c k i n gi nv i d e oa s s e m b l e sa d v a n c e dt e c h n o l o g i e si nm a n y f i e l d ss u c ha si m a g ep r o c e s s i n g ，p a t t e r nr e c o g n i t i o n , a r t i f i c i a li n t e l l i g e n c e ，a u t o m a t i c c o n t r o lc o m p u t e ra p p l i c a t i o n ，p h y s i o l o g y , p h y s i t sa n dm a t h e m a t i c s ，e ta 1 i th a sm a n y e x c e l l e n ta d v a n t a g e so fv i s u a ls c e n e ，a n t i i n t e r f e r e n c ea n dc o s t - e f f e c t i v e ，a n dh a s b e e nw i d e l ya p p l i e dt om i l i t a r ys u r v e i l l a n c e ，ir a m cc o n t r o l ，m a c h i n ei n t e l l i g e n c e ， m e d i c a ld i a g n o s i s ，a n ds oo n w i t ht h ec o n t i n u o u sd e m a n do fc o m p l e xe n v i r o n m e n t a p p l i c a t i o n s ，b e s i d e si n t r o d u c i n gn e wt e c h n o l o g y , h o wt oi m p r o v et h ea c c u r a c ya n d r o b u s to ft h ee x i s t i n gt r a c k i n ga l g o r i t h mi st h ef o c u so ft h ec u r r e n tw o r k i nt h i st h e s i s ，w ed e s c r i b et h em e t h o dt h a th o wt h em e a n s h i f ta l g o r i t h ma p p l i e d i no b j e c tt r a c k i n gf i e l d ，a n dw e i g h tt h el o c a t i o ni n f o r m a t i o no nt h ec o l o rh i s t o g r a m b ya n a l y z i n gr e s u l t so fm e a n s h i f ta l g o r i t h mt r a c k i n ge x p e r i m e n t ，w eg e tt h ei n h e r e n t d e f e c t so fm e a n s h i f la l g o r i t h m t h em a i nw o r ko ft h et h e s i si sp r e s e n tan e wm e t h o d t oi m p r o v et w od e f e c t so fm e a n s h i f ta l g o r i t h m f i r s t ，f o rt h ep r o b l e mt h a tt h em e a n s h i f ta l g o r i t h mc a n n o tt r a c ko b j e c tt h a ti s o c c l u s i o nc o m p l e t e l y , w ep r o p o s eas o l u t i o nt h a tc o m b i n e dm e a n s h i f la l g o r i t h ma n d k a l r n a nf i l t e r , w h i c hu s ek a l m a nf i l t e rt op r e d i c tt h eo b j e c tp o s i t i o ni nc u r r e n tf r a m e ， t h e ns e a r c ht h et a r g e ti nt h en e i g h b o r h o o du s i n gm e a n s h i f ta l g o r i t h m i nt h et h e s i s ， w ed i v i d et h eo c c l u s i o ns t a t u si n t ot h r e es t a t e m e n t s ：n oo c c l u s i o n ，p a r t l yo c c l u s i o n , c o m p l e t e l yo c c l u s i o n i na d d i t i o n , t h er e s i d u a lo fk a l m a ni st h ec r i t e r i ao ft h r e e s t a t u s e s w h e nt h eo b j e c ti so c c l u s i v ec o m p l e t e l y , w ep r e d i c ti t sl o c a t i o nb yi t sl i n e a r m o t i o nf e a t u r e s f o rd y n a m i ct e m p l a t e ，t h i sp a p e re m p l o y e dc a s e b a s e dr e a s o n m e t h o d i ts h o wg o o dp e r f o r m a n c ew h i c ht h ef i x e dt e m p l a t ec a n n o th a n d l e t h e n , w ee m p l o y e dc o n t i n u o u s l ya d a p t i v em e a n s h i f t ( c a m s h i f i ) a l g o r i t h m ， w h i c hc a l lr e s i z ek e m e lw i n d o wa d a p t i v e l y u s i n gh s vc o l o rm o d e li m p r o v e st h e a l g o r i t h mp e r f o r m a n c eo no p t i c a l - s e n s i t i v e u s i n ge l l i p s es e a r c h i n gw i n d o wm a k e s t h es e a r c hr e s u l to f t r a n s f o r m i n go b j e c tm o r ea c c u r a t e a tl a s t , t h i st h e s i si n t r o d u c e s a na u t o m a t i co b j e c tt r a c k i n gs t r a t e g y , w h i c he f f e c t i v e l yr e d u c e st h ee r r o r st h a tc a u s e d b yi n i t i a lt h et a r g e tm a n u a l l y k e yw o r d s ：o b j e c tt r a c k i n g ，m e a n s h i f t ，k a l m a nf i l t e r , o c c l u s i o nc o m p l e t e l y ， c a m s h i f t 。 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 型篓：羔! 尸 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 鹭逊导师签名：乏缘日期：丝遣：丘 z 乒， 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 人们利用自己的眼、耳、鼻、嘴以及其他器官从周围的环境中获取信息， 从而在纷繁的世界中生存与发展。因此，一旦产生了计算机，人们也希望计算 机能够替代他们与周围的环境交换信息，这就导致了计算机视觉这门学科的产 生与发展。计算机视觉是研究用计算机来模拟生物外显或宏观视觉功能的科学 和技术。机器视觉系统的首要目标是用图像创建或恢复现实世界模型，然后认 知现实世界。计算机视觉是人工智能领域最热门的研究课题之一，它和专家系 统、自然语言理解已成为人工智能领域最活跃的三大领域。尽管它还没有形成 完整的理论体系，在很多方面它解决问题的方法还是一种技巧，但它是实现工 业生产高度自动化、机器人智能化、自主车导航、目标跟踪，以及各种工业检 测、医疗和军事应用的核心内容之一，也是实现智能机器人的关键因素之一， 它的发展不仅将大大推动智能系统的发展，也将拓宽计算机与各种智能机器的 研究范围和应用领域l l j 。 机器视觉是在2 0 世纪5 0 年代从统计模式识别开始的，当时的工作主要集 中在二维图像分析和识别上，如光学字符识别、工件表面、显微图片和航空图 片的分析和解释等。6 0 年代，r o b e r t s 通过计算机程序从数字图像中提取出诸如 立方体、楔形体、棱柱体等多面体的三维结构，并对物体形状及物体的空间关 系进行描述。r 0 1 ) e r t s 的研究工作开创了以理解三维场景为目的的三维机器视觉 的研究。r o b e r t s 对积木世界的创造性研究给人们以极大的启发，许多人相信， 一旦由白色积木玩具组成的三维世界可以被理解，则可以推广到理解更复杂的 三维场景。于是，人们对积木世界进行了深入的研究。研究的范围从边缘、角 点等待征提取，到线条、平面、曲面等几何要素分析，一直到图像明暗、纹理、 运动以及成像几何等，并建立了各种数据结构和推理规则。到了7 0 年代，已经 出现了一些视觉应用系统。 7 0 年代中期，麻省理工学院( t ) 人工智能( a i ) 实验室正式开设“机 武汉理工大学硕士学位论文 器视觉( m a c h i n ev i s i o n ) 课程，由国际著名学者b k e h o m 教授讲授同时， m i ta i 实验室吸引了国际上许多知名学者参与机器视觉的理论、算法、系统设 计的研究。d a v i dm a n 教授就是其中的一位。他于1 9 7 3 年应邀在m i t 硝实验 室领导一个以博士生为主体的研究小组，1 9 7 7 年提出了不同于“积木世界 分 析方法的计算视觉( c o m p u t a t i o n a lv i s i o n ) 理论，该理论在8 0 年代成为机器视 觉研究领域中的一个十分重要的理论框架【2 j 。m a r r 视觉计算理论立足于计算机 科学，系统地概括了心理生理学、神经生理学等方面业已取得的所有重要成果。 是三维扫描仪视觉研究中迄今为止最为完善的视觉理论。m a n 建立的视觉计算 理论，使计算机视觉研究有了一个比较明确的体系，并大大推动了计算机视觉 研究的发展。人们普遍认为，计算机视觉这门学科的形成与m a n 的视觉理论有 着密切的关系。m a r r 视觉计算理论将整个视觉过程所要完成的任务分成三个过 程，而获得这些表示的过程依次称为初级视觉、中级视觉和高级视觉。 计算机视觉是在数字图像处理的基础上发展起来的新兴学科，它从信息处 理的层次研究视觉信息的认知过程，研究视觉信息处理的计算理论和表达与计 算方法，包括图像特征提取，摄像机定标，立体视觉，运动视觉( 或称序列图 像分析) ，由图像灰度恢复三维物体形状的方法，物体建模与识别方法以及距离 图像分析方法等方面。作为一门综合性的交叉学科，计算机视觉处理的领域涉 及到计算机科学与工程、信号处理、物理学、应用数学与统计学以及神经生理 学与认知科学等方面，并在制造业、检验、文档分析、医疗诊断和军事等领域 的各种智能自主系统中有着广泛的应用。 在序列图像中进行目标跟踪是计算机视觉研究的一个核心方向之一。与目 标跟踪相关的主要应用领域有智能视频监控【3 4 】、人机交互【5 】、自动驾驶【6 】、视觉 控制【7 1 、农业自动化【8 1 、医学图像【9 1 、视觉重构【1 0 1 等。 目前目标跟踪算法都是针对某些特定环境或者目标，缺乏通用性。目标跟 踪是更高级的视频处理的基础，为更高级的计算机视觉提供有价值的信息。因 此，对视频序列目标跟踪算法的研究意义非常重大，也充满挑战。 1 2 目标跟踪算法综述 在计算机视觉领域，目标跟踪问题的中心问题是：当目标相对摄像机运动 时，在视频序列中找出每帧图像中表示目标区域或目标特征图像的图像结构的 2 武汉理工大学硕士学位论文 连续对应性。然而，由于视频信号的丰富性和多变性，在复杂背景下跟踪一个 或多个运动目标依然很困难。 目标跟踪的目的就是通过对摄像头获得的图像序列进行分析，计算出目标 在每一帧图像上的二维位置坐标，并根据不同的特征值，将图像序列中不同帧 内同一运动目标关联起来，得到各个运动目标完整的运动轨迹，即在连续的视 频序列中建立运动目标的对应关系。简单来说，就是在下一幅图像中找到目标 的确切位置。在运动目标跟踪中主要的工作就是选择好的目标特征和采用实用 的搜索算法。 目标跟踪技术的研究进行了多年，目前已经提出了许多算法。这些算法有 的是针对刚性目标的跟踪、有的是针对非刚体目标的跟踪、有的是针对提高跟 踪匹配的准确性而提出的，这类算法的主要特点是通过选取好的跟踪特征来提 高目标的搜索匹配速度和匹配的正确程度：有的算法是针对缩小目标搜索范围 提出的，这类算法主要特点是通过某种方法预测目标下一时刻可能出现的位置， 通过缩小目标的搜索范围来缩短目标搜索时间。 目标跟踪方法有很多，迄今为止，没有权威的分类方法，目标跟踪方法大 体上可以分为基于模型匹配的跟踪、基于区域匹配的跟踪、基于特征匹配的跟 踪和基于运动特性的跟踪。另外也可以从基于前提假设条件来分类。 ( 1 ) 基于模型匹配的跟踪( m o d e l b a s e dt r a c k i n g ) 该方法利用点、线、区域把被跟踪的目标拟合成一个几何模型，如果可以 得到描述特定目标的模型( 也称为模板) ，那么目标跟踪就变成了模板与在分析 下的图像序列之间的特征匹配过程，运动目标的跟踪变成了目标识别问题。这 种方法充分利用了目标的特殊性质，与别的方法比较起来，更能适应复杂环境 中的目标跟踪。模板匹配分为固定模板和可变模板。固定模板在目标形状不随 摄像机视角而变化的情况下是可用的，而可变性模板方法对于目标由于刚性和 非刚性变形而变化的情形是更适合的。由于目标物体在运动过程中可能有旋转， 大小，形状的变化，所以固定模板不能满足准确匹配的要求，在实际跟踪任务 中最常用的是可变形模板【1 1 , 1 2 。 ( 2 ) 基于区域匹配的跟踪( r e g i o n b a s e dt r a c k i n g ) 区域匹配算法就是在当前帧中搜索上一帧中目标区域的相关度最大的区 域，也可以叫做基于相关型( c o r r e l a t i o n b a s e dt r a c k i n g ) ，具体做法就是将目标 图像在当前帧图像上以不同的偏移值位移，然后根据一定的相似性度量准则对 3 武汉理工大学硕士学位论文 每一个偏移值下重叠的两个图像目标图像及与目标图像同样大小的当前帧 图像进行相关处理，根据判别准则和相关处理结果，判断目标在实时图像中的 位置，相似度最大对应的位置就是目标的位置。这种方法在很多系统中被应用， 一方面因为他算法简单，另一方面，在图像中目标特征不明显，其他算法效果 不是很明显的时候，区域匹配算法还能有足够的精度。区域匹配算法计算量大， 的难以达到实时性需求，而且能否准确分割也直接影响到算法的效果。由于区 域匹配算法依据颜色信息，所以当场景遇到光照强度的变化，目标姿态的变化 或者其他噪音的时候，算法可能失效。j o r g e 】等人提出区域跟踪算法不仅利用 分割结果来给跟踪提供信息，同时也能利用跟踪所提供的信息改善分割效果， 把连续的目标匹配起来跟踪目标。 ( 3 ) 基于特征的跟踪( f e a t u r e b a s e dt r a c k i n g ) 实现跟踪，没有必要跟踪目标的每个一点，在基于特征的目标跟踪中，选 取目标的一部分特征点进行跟踪。这种方法的思路是：选取目标中具有高度稳 定性的显著特征序列( 如角点、边界线条、线段、小面或者局部能量) ，这些特 征应该不受外界因素如光照，噪音的影响，提取特征后，对特征属性矢量进行 相关度匹配。相关系数的峰值即为匹配位置。其优点是，即使场景中出现部分 遮挡，只要有一些特征点可见，仍可以保持对运动目标的跟踪。特征点的选取 是这种算法的关键所在，它应具有对目标的大小、位置、方位和照度变化不敏 感，图像的特征可以是幅度分布、频谱、几何特征，如点、线、面、边缘、纹 理等。这些特征的提取比较容易，算法可靠，运算量小。但这类特征不是很稳 健。另外还有一些图像的高级特征比如小波特征、三维特征等。小波特征在时 域、空域都具有很好的分辨率，一些小波( 比如g a b o r 小波1 1 4 】) 同时也具有很 好的人类视觉特性。这类特征量比较稳健，抗干扰性好，但是这类特征的提取 比较复杂【。比较典型的应用如b l a k e t l 5 】等用自适应边缘模型，c u r w e n 1 6 j 等用 s n a k e 算法都实现了对变形的运动轮廓的跟踪。 ( 4 ) 基于运动特性的跟踪( m o v i n gc h a r a c t e r - b a s e dt r a c k i n g ) 如果已知目标的一些运动特性，可以采用基于运动特征的跟踪算法。基于 运动特性的目标跟踪算法一般可分为两种：一种是依据目标运动的连续性进行 关联的算法，被用在多种跟踪算法相融合的场合，只需要较少的运算就可以大 大提高跟踪的准确性；另外一种是运动预测跟踪算法，可以根据目标的物理运 动特征来估计目标在下一时刻可能的位置。如果目标运动轨迹是光滑的，或者 4 武汉理工大学硕士学位论文 加速度是恒定的，即运动轨迹是线性的。且图像噪音是高斯噪音，可以采用卡 尔曼( k a l m a n ) 1 7 - 2 0 l 滤波来预测目标的在下帧中的位置：如果运动轨迹不是 线性的，可以使用扩展卡尔曼( e k a l m a n ) 1 2 1 , 2 2 1 滤波；如果噪音不是高斯分布， 可以使用粒子滤波【2 3 l 来预测目标在下一帧的位置。复杂环境中目标跟踪常用的 方法是粒子滤波，也是目前跟踪领域中的重要的一直方法。 其他方法如主动轮廓线，频率域匹配，光流分析，帧差分跟踪算法，记忆 外推跟踪算法，实例推理跟踪算法等都是基于以上四种算法发展或者改进来的。 近年来，均值平移( m e a n s h i f t ) 方法1 2 l l 解决计算机视觉底层过程中表现 出了良好的鲁棒性和较高的处理速度，因而在计算机视觉领域得到了高度关注。 尤其在目标跟踪方面，均值平移方法的发展为同时解决目标跟踪的稳定性和实 时性提供了一个有力的工具。均值平移方法具有很高的稳定性，能够适应目标 的形状、大小的连续变化，而且计算速度很快，抗干扰能力强，能够保证系统 的实时和稳定性。目前已有众多关于均值平移的文献被发表。但是任何一种方 法都不是完美的，均值平移方法的主要缺点是对初始预测位置的要求较高，如 果给定的初始值不够精确，该方法将无法准确跟踪目标，甚至丢失目标。将 m e a n s h i f t 算法扩展到连续图像序列，就形成了c a m s h i f t 0 2 j 算法。c a m s h i f t 算法 是基于连续图像颜色动态变化的概率分布的一种跟踪算法，具有鲁棒性强和实 时性好等优点。它利用目标的颜色特征在视频图像中找到运动目标所在的位置 和大小，在下一帧视频图像中，用运动目标当前的位置和大小初始化搜索窗口， 重复这个过程就可以实现对目标的连续跟踪。其缺点是受图像的颜色概率分布 影响，主要适用于与背景相比具有明显色彩差异的彩色目标跟踪。对于被遮挡 目标，采用m e a n s h i f t 结合k a l m a n 滤波的方法【3 3 】，利用目标的运动特征，可 以有效的解决被遮挡的问题1 3 5 - 3 6 1 。 1 - 3 目标跟踪中难点 在时域上进行跟踪，就是在连续帧中将相同的目标对应起来。跟踪的难点 源于场景的复杂性和目标的复杂性。目标运动时由于噪声和遮挡等原因，不同 的目标有可能运动到一起，合并成一个目标，而同一目标又可能分裂成多个新 的目标，同时在目标运动过程中，目标的外表特征也可能发生改变，如光照变 化或阴影的影响造成的色彩上的变化等。 武汉理工大学硕士学位论文 目标检测跟踪的基础就是对动态序列图像的运动分析，关键是目标检测跟 踪的准确性和智能化程度。但是众多的因素导致图像灰度和内容会产生变化， 例如物体本身随着运动变大或变小、摄像机与物体产生相对运动、场景环境的 变化等，从而使跟踪的过程变得比较复杂。 由于各种跟踪算法都有自己的偏重点，所以没有通用的算法。在不同的环 境下要选择适当的算法。 但是影响目标跟踪的有一些共同的因素【3 7 1 ，主要有： 复杂的背景：在基于颜色的跟踪算法中，与目标颜色相似的背景容易导致 跟踪失败； 。光照的变化：光照的变化引起目标颜色的变化，从而导致目标模板不可靠， 而且也容易使得背景颜色发生变化，对某些算法中目标检测造成影响； 阴影问题：阴影属于非运动目标区域，但是与背景颜色存在差别，给运动 目标检测带来很大的困难； 目标的形变：在基于模板或者特征的跟踪中，形变使得原始模板或者特征 目标无效； 遮挡问题：目标被非目标物体遮挡，或者多目标之间相互遮挡是跟踪中的 又一个难点； 摄像机架的抖动：摄像机的抖动会导致目标与背景之间的相对平移或者变 形，会导致很多相关问题的出现； 目标的初始化：目前很多学者的主要精力放在改进跟踪算法上面，但是作 为一个完整的目标跟踪系统，如何初始化目标，是一个很重要的课题，目标初 始化的精确度直接影响到跟踪结果的精度； 实时性要求：由于实时性系统的要求，目标跟踪过程中必然要降低精度来 提高速度，如何在提高速度的同时也提高精度也是我们要研究的一个重要课题。 1 4 论文内容概述 本文所做的工作主要包括以下几个方面： 介绍m e a n s h i r 算法相关知识以及实现对视频图像的目标跟踪。 介绍k a l m a n 滤波以及相关知识，并将其融入到m e a n s h i r 算法中，解决目 标跟踪过程中完全遮挡的问题。 6 武汉理工大学硕士学位论文 介绍c a m s h i f t 算法相关理论，并且实现快速稳定的全自动跟踪算法。解决 目标跟踪过程中目标大小变化的问题。 1 5 论文的创新点 1 引入实例推理机制以及k a l m a n 滤波器到m e a n s h i f t 算法中，提出一种新 的动态更新模板的策略，实现目标完全遮挡情况下跟踪的鲁棒算法。 2 提出全自动的c a m s h i f t 跟踪策略。 7 武汉理工大学硕士学位论文 第2 章m e a n s h i f t 算法在目标跟踪中的应用 2 1 引言 m e a n s h i f t 算法的原形“v a l l e y - s e e k i n gp r o c e d u r e 于19 7 5 年由f u k u n a g a 和 h o s t e t l e r 提出【强j ，用于梯度概率密度函数估计，其最初含义正如其名，就是偏 移的均值向量，在这里m e a n s h i f t 是一个名词，它指代的是一个向量，但随着 m e a n s h i f t 理论的发展，m e a n s h i f t 的含义也发生了变化，如果我们说m e a n s h i f l 算法，一般是指一个迭代的步骤，即先算出当前点的偏移均值，移动该点到其 偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。 均值平移算法利用核函数的性质，无需对整个区域的概率密度进行估计， 就能利用核函数对当前点的梯度估计，并进一步导出均值平移步长。虽然关于 均值平移方法的应用方面的研究很多，但是这个方法的内在机理并没有得到很 好的研究。最初，f u k u n a g a 和h o s t e t l e r 认为均值平移可以看作是求最大值的快 速上升法。此后2 0 年都未引起学术界的重视。直到1 9 9 5 年y c h e n g t 2 4 l 对基本算 法做了两个方面的扩展，修正了f u k u n a g a 和h o s t e t l e r 的观点，认为均值平移算 法是具有自适应步长的最速上升法，并成功的引入到计算机图形学领域，才引 起广泛的关注。y c h e n g 对m e a n s h i f t 算法做了两个方面的扩展为：定义一族核 函数，使得距离对均值偏移向量也有不同的贡献；设定权重系数，使得不同的 样本贡献不同。这两个扩展大大的扩大了m e a n s h i f f 算法的应用领域。2 0 0 5 年， d u k e 大学的m a r kf a s h i n g 和c a r l ot o m a s i t ”】提出了一种观点，认为均值平移算 法是一种边界优化方法。 c o m a n i c i u 和m e e r 把m e a n s h i f t 成功地运用于特征空间的分析1 4 0 1 ，在图像 平滑和图像分割1 4 l j 中m e a n s h i f t 都得到了很好的应用。在文献 1 8 】中，c o m a n i c i u 等主要讨论了m e a n s h i f t 在目标跟踪中的应用，这是m e a n s h i f t 在目标跟踪中应 用的经典文献。在文献【4 2 j 中，c o m a n i c i u 等论述了m e a n s h i f t 中核函数带宽的选 择问题，计算繁琐，实用性不强，但有理论价值。c h a n g j i a n gy 锄g 【4 3 j 对多维图 像的m e a n s h i f f 方法进行了讨论，算法选用了高斯核。高斯核与图像的卷积运算 8 武汉理工大学硕士学位论文 量很大，因此采用了改进的快速高斯变换提高算法的速度。c o l l i n s l 4 4 1 将尺度空 间和m e a n s h i f i 相结合解决了核函数带宽实时变化时的目标跟踪，但算法的速度 不好。n u m m i a o 等【4 5 j 研究了粒子滤波器和m e a n s h i f t 方法相结合的情况，但是 粒子滤波器本身的复杂计算降低了跟踪的实时性1 2 l 。 本章主要介绍了m e a n s h i f i 算法的理论以及在目标跟踪中的应用，章节安排 如下： 2 2 节介绍m e a n s h i f i 理论相关知识，2 3 节介绍m e a n s h i f t 算法在目标跟踪 中的应用实例，2 4 节对m e a n s h i f i 算法在目标跟踪中效果进行分析。 2 2m e a n s h i f f 理论 2 2 1 背景知识 设 勋 ，1 ，。表示从未知的、概率密度为厂的分布中抽出的”个d 维向量的集 合。根据对的先验知识，概率密度函数厂的估计，可以根据以下两种方法来 确定：参数方法和非参数方法。 如果预先假定数据样本按一定参数模型分布，那么通过这种假设估计的结 果就是参数化的估计。在这种情况下，样本被用来估计这种参数模型的参数， 例如：在正态分布条件下，这些参数就是均值向量和协方差，当知道预先假定 分布的参数后，我们就确定了这个分布的形式，密度函数的估计就可以根据这 个确定的分布形式估计出来。有限个密度函数混和分布的模型也可以看成是一 个参数模型，它可以表达为： jl f ( x ) = 脚( x ) ( 2 - 1 ) = i 其中 扔，“。是密度函数的估计， p j j “m 是先验概率。总的来说，参数模 型不是很复杂并且比较容易估计，但是不一定能正确的表达出实际的分布情况， 因为它预先做的假设不一定正确。因此，参数模型只是在预先可以肯定样本的 分布形式或是估计过程必须要求低复杂性时才能采用。如果一个样本集的自由 度和样本集的势比较大，那么这个样本集的密度模型就不具备一个固定分布形 式，它是非参数化的。最近邻方法和核函数估计法是两种非参数的描述数据的 方法。 9 武汉理工大学硕士学位论文 非参数方法为了达到一个好的估计效果，一般来说都需要大量的样本数据， 这样就增加了这种方法的复杂性。总之，只要对样本的分布有一定的要求或预 先知道样本的分布，我们就用参数法，如果对样本的分布要求不严格或预先不 知道样本的分布，我们就用非参数法。 估计统计密度的非参数方法有多种，主要有直方图法、七近邻法、核函数法 等。其中基于核函数的密度估计是最常用的非参数估计方法。 2 2 2 核函数密度估计 首先考虑一维情况，设缸t ，工，勘) 是用于估计密度的一组样本，由概率密度定 义可得： x + h p ( x - h x 工+ ) = ip ( t ) d t 2 h p ( x ) ( 2 - 2 ) x - h 则司以得出 p ( 砷玄p ( x - h x x + h ) ( 2 - 3 ) 可以推导出概率密度函数由样本的估计值： 如) 2 吉善似x - x ，, h ) ( 2 - 4 ) 其中x ，渤是观测值，w 是矩形加权函数，形式如下： 毗炉陆 h 如 ( 2 - 5 ) 【0 e l s e 可以证明用公式( 2 - 4 ) 估计出的概率密度b ( x ) 具有概率密度的性质：b ( x ) 0 和r p ( x ) 出= 1 。可以解释此核函数估计为用一个矩形窗( 1 2 h x 2 h ) 选取某个 观测点附近所有的点，用该区域的概率密度估计来估计所选观测点的概率。增 加h ，那么矩形选取框的宽度也就相应的增加，也就增加了概率密度函数的平滑 程度。在实际应用中也可以采用其他权值函数，如高斯函数： w ( r ，j i i ) 。丽1 一p ( _ t 2 1 2 h 2 ) ，一 f 佃 ( 2 - 6 ) 设有多维样本集x = “，t ) ，r d ，权重函数为w ：r d 哼r 。则该样本 集的密度函数f ( x ) 的核密度估计为： l o 武汉理工大学硕士学位论文 五州町= 翥c 善c x 一毛m = 翥c 善尼c i l 等1 1 2 m c 2 忉 这里的c 是归一化常数。 其中函数k ( x ) 称作轮廓函数，其中x 【0 ，+ o o ) ，并且k ( x ) 满足下面的条件： 1 ) 七( x ) 是非负的； 2 ) 七( x ) 是非增的。即k ( a ) 七( 6 ) ，如果a b ； 3 ) 七 ) 是分段、连续的。并且f k ( r ) d r 、 7 0 = f l r c c o s 色饱和度分量由下式给出： s = 1 一南n ( r , g , b ) 】 最后，强度分量由下式给出： ，= 三( 尺+ g + b ) 1 5 ( 2 1 9 ) ( 2 2 0 ) 两 一| 以淼 扣i f 审 武汉理工大学硕士学位论文 对于采用颜色特征的跟踪算法，一般可以采用r g b 空间。也可以采用h s i 空间。 2 3 2 目标模型的描述 本文采用的是r g b 颜色空间，对于r g b 彩色图像序列，将r g b 颜色空间 中的每个r 、g 、b 子空间分成k 个相等的区间，每个区间成为一个b i n ，构成 特征空间，特征空间的个数( 也就是b i n 的个数) 为m = 矿。由于r g b 空间中邻 近的颜色相似，在光线等条件的影响下，对跟踪效果影响不大，将每个子空间 划分后合并成大的子空间，可以减少总空间的维数，从而减少运算量，并且对 跟踪效果影响不大。 直方图是对目标特征的比较弱的描述，在目标周围存在与目标颜色分布相 似的物体时，跟踪算法容易跟丢目标。y c h e n g 在论文【2 4 】中提出了一种将目标 内的像素的空间信息也考虑在内的目标模型，通过将空间信息引入到目标模型 去，增强了对目标的描述。通过这样的一种改进后，可以提高跟踪算法的精度 和收敛速度。 通过已经建立的目标模型，可以得到运动目标的位置和大小，一般情况下 目标区域选取为矩形，目标区域像素的中心坐标设定为砌，第f 个像素的坐标用 知表示。在目标模型为所值得直方图，归一化后，目标模型的颜色分布特征值甜 的概率密度为： 孵驯孚胁瞅小甜】 ( 2 2 1 ) 其中u = l ，2 ，3 m ，k & 夕为核函数，h 表示核函数的带宽，核带宽h 的计 算方法有很多种，各种不同的方法对跟踪结果的影响是不同的，其运算量也是 不同的。在实际应用中可以综合考虑两种因素来选取适当的h ，“) 扣d 。表示第f 个像素点在目标区域定义的矩阵中的坐标，6 ( 薯) ：尺2 一 l m ) 是位于点像素的 特征值，这里是转换到k 空间以后的颜色值，万( x ) 是k r o n e c h e r 如加方程。 万【6 ) 一 】的作用是判断坐标处的像素是否属于第u 个b i n ，将不同的颜色分 量分离开来，计算出颜色分布的直方图；c 是一个标准化常量系数，使得 e q 一= 1 ( 2 - 2 2 ) 其中 1 6 武汉理工大学硕士学位论文 c = 彳二一 ( 2 - 2 3 ) k ( i l 孚1 1 2 ) i = l 目标区域外围的像素可能被遮挡或者受到背景颜色的影响，是相对不可靠 的，并且对目标主体贡献率较低，为此对目标内不同位置的像素应赋予不同的 权值，位置与目标更中心点距离越远，其相应的权值越小，所以这里引入核函 数k 来实现区分不同空间位置像素对目标整体特征值的贡献率。 2 3 3 候选模型的描述 运动目标在第二帧以及以后每帧中可能包含目标的区域成为候选区域，其 中心位置为y o ， x ，) 川。表示该区域中每个像素点的坐标。候选模型特征值 为： 讹州驯峄p 瞅咿甜， 陆2 4 ， 其中u = l ，2 , 3 m ，k & 夕为核函数，h 表示核函数的带宽， ) m 埘表示第 i 个像素点在目标区域定义的矩阵中的坐标，6 ( ) ：r 2 _ 1 一1 1 1 ) 是位于点薯像素 的特征值，这里是转换到k 空间以后的颜色值，万( z ) 是k r o n e c h e rd e l t a 方程。 d b ( x o - u 】的作用是判断而坐标处的像素是否属于第材个b i n ，c 是一个标准化常 量系数，使得p u - 1 c h = 百二一 ( 2 - 2 5 ) 圳孕1 1 2 ) 2 3 4 相似性函数 相似形函数用于定义目标模型与候选模型之间的距离，为了适应各种不同 的模型，相似性函数必须结构化，以便在不同维空间都能够使用。b h a t t a c h a