CamShift_目标跟踪算法毕业设计.doc

武汉理工大学 本科生毕业设计（论文） 局部局部 CamShift 跟踪算法跟踪算法 学院（系）： 理学院 专业班级： 信计 0703 学生姓名： 刘毅 指导教师： 楚杨杰 武汉理工大学毕业设计(论文) 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包括任何其他个人或集体已经发表 或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。 作者签名： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向 有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权省级优秀学士论文评选机构将本学位论文的全部或部分内容编入有关数据进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1、保密囗，在 年解密后适用本授权书 2、不保密囗 。 （请在以上相应方框内打“”） 作者签名： 年 月 日 导师签名： 年 月 日 武汉理工大学毕业设计(论文) 毕业设计毕业设计(论文论文)任务书任务书 学生姓名：学生姓名： 刘毅刘毅 专业班级：专业班级： 信息与计算科学 0703 班 指导教师：指导教师： 楚杨杰楚杨杰 工作单位：工作单位： 武汉理工大学理学院 设计设计(论文论文)题目：跟踪算法的研究题目：跟踪算法的研究 设计（论文）主要内容：设计（论文）主要内容： 该论文在国内外现有的跟踪算法研究基础之上，深入讨论目前的主流 跟踪算法 Mean-Shift 跟踪算法，并且讨论 Mean-shift 的本质原理以及应用 到目标跟踪的应用方法，并同时讨论了 Mean-shift 算法的改进算法 Camshift。在编程分析算法的跟踪优缺点以后，提出自己创建的算法：局部 Camshift 算法，最后，应用大量实践视频来做跟踪，分析跟踪效果。 要求完成的主要任务要求完成的主要任务: 1、查阅不少于 15 篇的相关资料，其中英文文献不少于 5 篇，完成开题报告； 2、深入理解 Mean-shift 算法原理机制，了解 Mean-shift 的算法本质； 3、理解 Mean-shift 算法用作跟踪的原理，并且掌握 Camshift 跟踪算法最后再加以改进； 4、完成不少于 20000 英文(5000 汉字)的英文文献翻译； 5、完成不少于 12000 字的毕业设计论文. 必读参考资料：必读参考资料： 1 K.Fukunaga and L.D.Hostetler,“The Estimation of the Gradient of a Density Function,with Applications in Pattern Recognition“ IEEE Trans.Information Theory,vol.21,pp.32-40,1975. 2 D. Comaniciu and P. Meer, “Mean Shift: A Robust Approach Toward Feature Space Analysis,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603- 619, May 2002. 3 D.Comaniciu, V. Ramesh, and P.Meer “Real-Time Tracking of Non-Rigid Objects Using Mean Shift“ Proc Eighth IntlConf. Computer Vision, vol,21,pp.331-337,1996 武汉理工大学毕业设计(论文) 4 G.R.Bradski,“Computer Vision Face Tracking as a Component of a Perceptual User Interface,“Proc.IEEE Workshop Applications of Computer Vision,pp.214-219,Oct.1998 指导教师签名：指导教师签名： 系主任签名：系主任签名： 院长签名院长签名(章章) 武汉理工大学武汉理工大学 本科学生毕业设计（论文）开题报告本科学生毕业设计（论文）开题报告 1、目的及意义（含国内外的研究现状分析）、目的及意义（含国内外的研究现状分析） 实时跟踪算法一直在很多计算机视觉领域里是个难题，例如在监控系统，感知用户 界面，基于目标的视频压缩算法，汽车驾驶辅助系统等等尖端领域里，都是一个没有被 解决的难题。传统的视觉跟踪器可以分为两大派别，一种是目标的建模以及定位，是处 理目标的现状和变化一种由下至上的过程。另一种滤波和数据关联度是一个处理目标动 态变化，先验学习的由上至下的过程。当噪声向量是属于高斯分布，最好的方法是用卡 尔曼滤波法 但是，从本论文的研究现状的讨论中，可以知道卡尔曼滤波是一种把大多数情况进行理 想化的粗糙办法，实用性并不强。论文中罗列了一系列方法都是国内外目前比较先进的 办法。但是这些方法，都是属于上面两大派别的其中一种，无一例外。 2、基本内容和技术方案、基本内容和技术方案 本文在目前国内外做跟踪算法的研究基础之上，介绍了国内外的跟踪算法研究现状， 并且详细地讨论了国内外跟踪算法领域里十分有名的算法：Mean-shift 算法。在第二章 节中，本文详细讨论了 Mean-shift 算法原理，深入解析了该算法的本质和证明了它的基 本特征，得出了 Mean-shift 算法的迭代过程是个逐步递增的迭代过程，并且只会收敛到 函数极大值。在分析了该方法之后，介绍了该方法在计算机视觉领域的应用之一：目标 跟踪。 在实践了 Mean-shift 做目标函数跟踪之后，通过实例来分析该算法用作跟踪的优点和缺 点，并且在保证该算法优点的同时，也改进了该算法的缺点，从而介绍了一种比较普遍 的改进算法：Camshift。该算法主要的改进部分是根据目标矩阵的零阶矩，来估计目标 的面积区域，从而改变跟踪窗口的大小。通过大量的实例分析，我们得出：无论是 Camshift 还是 Meanshift，在跟踪的时候会由于目标的亮度变暗而失真，其主要原因是 因为国际上现存的 RGB 到 HSV 转换方法是在亮度或者饱和度很小的情况下，色相会产生 很大的波动并且不稳定。由于两者的跟踪都是基于色相数据模型之上，所以该跟踪算法 武汉理工大学毕业设计(论文) 的稳定性不强。本文将全局跟踪修改为局部跟踪，是得算法有效地避开了目标背景区域 亮度不强而引起的跟踪无效现象，使得算法检测不到背景亮度值非常低的区域，从而很 少产生误差。并且在改善跟踪的同时，也可以降低计算量，减少了算法的时间复杂度。 3、进度安排、进度安排 第 1 周第 3 周：查阅相关文献资料，明确研究内容，了解研究所需的相关背景知识， 确定方案，完成开题报告； 第 4 周第 6 周：深入学习 Meanshift 算法原理，以及该算法的性质，复杂度等分析， 并且了解该算法在跟踪领域的应用； 第 7 周第 10 周：了解 Meanshift 跟踪算法的优缺点，并且在保证优点的情况下， 修改其缺点，结合自己的创新研究更好的跟踪算法，同时编程实践； 第 11 周第 14 周：完成并修改毕业设计论文； 第 15 周：准备论文答辩。 4、指导教师意见、指导教师意见 指导教师签名： 年 月 日 注：注：1开题报告应根据教师下发的毕业设计（论文）任务书，在教师的指导下由学生独立撰写， 在毕业设计开始后三周内完成。 2 “设计的目的及意义”至少 800 字， “基本内容和技术方案”至少 400 字。进度安排应尽可能详 武汉理工大学毕业设计(论文) 细。 3指导教师意见：学生的调研是否充分？基本内容和技术方案是否已明确？是否已经具备开 始设计（论文）的条件？能否达到预期的目标？是否同意进入设计（论文）阶段。进入设计（论 文）阶段。 武汉理工大学毕业设计(论文) 目目 录录 摘摘 要要.I ABSTRACT.2 1 绪论绪论 2 1.1 背景分析.2 1.2 研究现状.3 1.2.1基于滤波和数据关联度的跟踪算法研究现状3 1.2.2 基于目标建模和定位的跟踪算法研究现状.4 1.3 主要研究内容.4 2 MEAN SHIFT 跟踪器设计跟踪器设计.6 2.1 引言.6 2.2 MEAN-SHIFT 算法定义以及效率分析6 2.2.1 Mean-shift 算法核函数概述1 .6 2.22 Mean-shift 算法梯度函数.8 2.2.3 Mean-shift 收敛定理证明以及算法综述10 2.3 基于 MEANSHIFT 的视频跟踪原理以及应用 .13 2.3.1 Meanshift视频跟踪算法.13 2.3.2 Meanshift视频跟踪应用以及优缺点分析.17 3 局部局部 CAMSHIFT 算法原理以及实践算法原理以及实践.19 3.1 CAMSHIFT跟踪器19 3.1.1 Camshift算法原理19 3.1.2 CamShift算法优缺点分析21 3.2 局部 CAMSHIFT 算法22 3.2.1 局部Camshift算法原理22 3.2.2 局部Camshift算法的优缺点分析24 4 局部局部 CAMSHIFT 算法与算法与 CAMSHIFT 算法对比算法对比.25 4.1 局部 CAMSHIFT算法的跟踪效果比较 25 4.2 局部 CAMSHIFT算法的迭代次数比较 26 5 总结与展望总结与展望 28 5.1 论文总结.28 5.2 研究展望.28 附录附录 I 源程序源程序(OPENCVTEST.CPP).32 致谢致谢 38 武汉理工大学毕业设计(论文) I 摘摘 要要 Meanshift 算法是一种在一组数据的密度分布中寻找局部极值的稳定的方法。 在离散的数据集上，meanshift 能很快的找到数据分布最密集的点，本文介绍了 Meanshift 算法的性质，并且也讲述了 MeanShift 算法用于跟踪的方法。在分析 一些传统的跟踪算法优缺点后，提出了局部的 CamShift 算法，后经分析得知， 该算法在保证了 MeanShift 的快速优点的前提下，改进了该算法的多种缺点， 从而能够在目标距离发生变化，室内环境光线昏暗，目标物体遭到干扰的情况 下依然能够有效地追踪物体。 本文以 Meanshift 算法为起点，逐步深入地了解跟踪算法本质，具体内容如 下： (1) 介绍了 meanshift 算法的基本原理和算法的效率分析，并介绍了该算法 用于检测离散数据密度分布的应用以及其用作检测密度的优越特性。 (2) 介绍了 meanshift 算法在目标跟踪领域里的应用，讲述了该过程中图像 的特征提取，直方图之间进行对比（反向投影）运算的方法从而提取出离散数 据点的分布，最后利用 meanshift 找出该分布的最密集位置，从而实现跟踪效果。 (3) 将 Meanshift 做跟踪的算法改进 Camshift 运用到跟踪过程中，并且将 图像的全局运算改为迭代窗口的局部运算，从而在大大节省了计算量的同时也 有效的实现实时跟踪。并用大量的实例演示其跟踪效果。 关键词关键词： meanshift；目标跟踪；实时跟踪；camshift； 武汉理工大学毕业设计(论文) 2 Abstract Meanshift is an algorithm which can find local stationary point in the discrete density distribution. In discrete data set, mean shift algorithm can quickly find the most density distribution. This paper introduce the mean shift algorithms property, and state the way how it was used in tracking problem. After the analysis of the advantage and disadvantage of the tracking, we introduce the partial camshift algorithm, and provide a analysis in detail. This algorithm inherit the advantage of the mean shift, and overcome many disadvantages like the changing distance, dim environment, and some distract of the object, the algorithm works well with them. This paper starts from the mean shift, and gradual deepening the understanding on the intrinsic nature of the tracking problem. We will discuss in detail: (1) We introduce the basic principle and the efficiency of the mean shift algorithm and furthermore, we also introduce the utility of the algorithm in discrete mode distribution detection and density detection. (2) We introduce the mean shift algorithms utility in the object tracking and analysis the advantage and efficiency in the object tracking. Finally use the mean shift to find the maximum portion in the distribution. (3) Introduce the modification of the mean shift-camshift, and use it into the object tracking. At last, use the CAMSHIFT to find the local maximum in the feature distribution. Then achieve the real-time tracking. Also, we use a great number of examples to show the effect of the tracking. Keywords: MEANSHIFT; CAMSHIFT; object tracking; real-time tracking; 1 绪论绪论 1.1 背景分析 实时跟踪算法一直在很多计算机视觉领域里是个难题，例如在监控系统， 感知用户界面，基于目标的视频压缩算法，汽车驾驶辅助系统等等尖端领域里， 武汉理工大学毕业设计(论文) 3 都是一个没有被解决的难题。传统的视觉跟踪器可以分为两大派别，一种是目 标的建模以及定位，是处理目标的现状和变化一种由下至上的过程。Meanshift 算法1是该派别的主力算法之一，该算法是一种在一组数据的密度分布中寻找 局部极值的稳定2的方法。在离散的数据集上，meanshift 能很快的找到数据分 布最密集的点，并且 Comaniciu 等人3把 Meanshift 成功的运用在特征空间的 分析，在图像平滑和图像分割中 Meanshift 都得到了很好的应用，取得了非常好 的效果。同时 Comaniciu 等人4 还把跟踪问题近似为一个 meanshift 最优化问 题，使得跟踪可以实时的进行。之后，Bradski 5 针对 meanshift 算法提出了改 进，使得跟踪更加有效快捷。另一种滤波和数据关联度是一个处理目标动态变 化，先验学习的由上至下的过程。两种方式结合在一个有效稳定的目标跟踪器 中可以发挥着关键作用。例如，人群中的人脸更多的依靠目标的表现形式，而 不是目标动态6，而在现场的目标监控系统里7，目标的移动和摄像机的自我 移动是更关键的部分。在实时跟踪系统中，只有系统中的少量资源可以被用来 做跟踪，其余部分可以用来做识别等预处理，因此，要将计算复杂度尽可能地 降到最低。 1.2 研究现状研究现状 1.2.1 基于滤波和数据关联度的跟踪算法研究现状基于滤波和数据关联度的跟踪算法研究现状 基于滤波和数据关联度的目标跟踪，可以归纳为对离散时间动态系统的状 态空间建模方法。描述目标特征的信息定义为，对应的时间更新的方 0,1, kk x 程用来描述。可以利用的方法集合和相应的状态方程 1 (,) kkkk xfxv 1,. kk z 相关。概括的说， 都是非线性的向量，值都是随着时间(,) kkkk zh x n k f k h 变化的 和 都是噪声向量，并且假设为独立同分布的随机变量。 1, kk v 1, kk n 当噪声向量是属于高斯分布，都是线型算子的时候，最好的方法是 k f k h 用卡尔曼滤波法(Kalman Filter)8, p.56，当， 都是非线性算子的时候，进 k f k h 行线型化就得到了扩展的卡尔曼滤波法(Extended Kalman Filter, EKF)8，两种 方法的后验概率分布都是高斯型。有一个另类的卡尔曼滤波法叫做 Unscented Kalman Filter(UKF)9, 该方法根据一些离散的样本点求出后验概率的均值和方 差。当状态空间是离散而且由有限个状态组成的时候，隐马尔科夫(Hidden Markov Models, HMM)滤波10可以用来做跟踪。最一般的滤波族是粒子滤波 11，也叫 booststrap 滤波，是基于蒙特卡罗积分法的滤波方式。 当跟踪于一个多目标的混乱环境下，一些跟踪方法的有效性和关联性就产 生了。最近邻居法(Nearest Neighbor Filter)和概率数据关联法(Probabilistic Data 武汉理工大学毕业设计(论文) 4 Association Filter)对一个单目标都是有效的。这些做法的假设是，对于一个给定 的目标来说，只有一种方法是有效的，其余的方法都是随机的干扰。这就是说， 独立同分布的均匀分布量。连接数据关联度滤波(Joint Data Association Filter(JPDAF)8, p.222, 于此同时，计算了方法和目标的关联度概率把所有目标 都联系起来。一个与众不同的方法是多重假设滤波(Multiple Hypothesis Filter, MHF)12，通过计算给定的目标产生一系列方法的概率来适应目标的状态分布。 以上讨论的滤波和数据关联的方法都用于计算机视觉领域中多目标的跟踪 情形。Boykov 和 Huttenlocher 用卡尔曼滤波法跟踪车辆13，Rosales 和 Sclaroff 用扩展的卡尔曼滤波实现了 2D 图像到 3D 图形的构造和重建14，Isard 和 Blake 提出的压缩算法15 中提出了粒子滤波。在文献16中，概率排除的 多目标算法被提出。Chen 和其他人17 用隐马尔科夫方程和数据关联来跟踪 物体，Rui 和 Chen 提出基于人脸轮廓的粒子滤波跟踪法18，Cham 和 Rehg 19 应用多变的 MHF 来进行图像跟踪。 1.2.2 基于目标建模和定位的跟踪算法研究现状基于目标建模和定位的跟踪算法研究现状 在另一方面，目标跟踪算法的第二派系：基于目标的建模与定位的跟踪。 当滤波和数据关联度在控制理论中已经拥有了它们的基础，但基于目标建模和 定位的跟踪算法更加贴近图像，同时也和配准方法20有类似之处。目标定位 和配准方法都是最大化似然函数。区别在于，在跟踪的时候，连续的两帧图像 里的位置和目标的模型数据的变化不会太大，这点是和配准方法截然相反的。 目前有许多学者根据这点特性做了许多算法，基于梯度的算法21是根据归一 化的相关度来进行跟踪，然后相关度有所缺点，就是对光照特别敏感。Hager 和 Belhumeur 22明确地建立了几何光照的变化模型，该方法又由 Sclaroff 和 Isidoro23 进一步的改进。对模型的训练学习是建立在一些稳定的图像结构， 运动信息和一些异常过程24的基础之上的。在不同的做法上，Ferrari 等人25 提出了一种基于平坦区域和箭头的跟踪器。跟踪人的时候，会产生很多问题， 这些问题大部分都是由人们的三维移动的无规律性而产生的。在一些文献中， 这种问题被大量地详细分析2627。与此同时人的直接跟踪法28时间复杂度 高，而且经常会用上一些其它的模型2930。 1.3 主要研究内容主要研究内容 本文的主要目的是研究 Meanshift 算法，并且将其用于目标跟踪，进而提出 一套改进的 Meanshift 算法，使其能够自适应物体的大小进行跟踪。其内容可以 武汉理工大学毕业设计(论文) 5 大致分为三个部分： 1) 推出了一种基于目标建模和定位的跟踪算法，该算法为跟踪非刚性物体提供 了新的框架。首先介绍并分析了 meanshift 算法的收敛特征，初步介绍了该算法 在计算机视觉领域的应用并且成功地解决了视觉领域许多问题； 2) 对跟踪的目标建立直方图模型，并为跟踪算法提供依据。最后，利用 Meanshift 算法对其进行跟踪并且分析其算法复杂度和该算法的优势； 3) 在 Meanshift 的基础之上，建立一个能够自适应目标大小的 camshift 算法， 同时将全局运算改为对图像的局部进行运算，从而可以大大节省运算量。并将 此算法用作跟踪。 武汉理工大学毕业设计(论文) 6 2 Mean Shift 跟踪器设计跟踪器设计 2.1 引言引言 Mean Shift 算法，在 1975 年就已经被 Fukunaga 和 Hostetler 1等人提出， 当时几乎快被人们遗忘，直到 Cheng 的一篇论文31才点燃了人们对该算法的 兴趣。尽管该算法有其优越的特性，但该算法在统计领域并不为人所知。一本 书32讨论了用 Meanshift 做密度检测的优点时，这个算法才被统计领域所发现 并广泛使用。 正如接下来将要讨论和介绍的一样，基于 Meanshift 的算法在特征分析空 间中是个十分多样化的工具，对计算机视觉领域的许多问题都提出了很好的解 决办法3。本文的主要介绍的是 Meanshift 在跟踪问题上的应用。该论文介绍 了对目标进行核函数建模,并将核函数和目标模型的相关度作为对比依据，这样， 一个跟踪问题就简化为在连续两帧图像里搜寻相关度最大位置的问题。由于建 立的相关度摸型是个连续函数，因此，基于梯度的方法便可以使用，使得该优 化方法会比优化的搜索方法要快速许多。候选目标与目标的相似度是用 Bhattacharyya 的相关系数。在跟踪这方面，Bhattacharyya 相关系数的实际意义 就是对候选目标进行打分。新的目标模型和定位也可以选择通过多种滤波和数 据关联度的方法进行卷积。本论文成功的进行了很多跟踪方法，处理了许多复 杂的跟踪问题。 论文的大致框架如下：在第二节，对 Meanshift 算法的定义和性质进行了 详细分析。在第三节，将直方图作为目标的主要模型，通过对直方图的对比来 提取图像中与目标相近的点，然后 Meanshift 方法用于目标跟踪，并对其方法进 行详细介绍和跟踪效率进行分析。最后，结合跟踪算法的核函数模型4和 camshift 算法的自适应大小的特征，利用两者的优点做出实时的视频跟踪算法。 2.2 Mean-shift 算法定义以及效率分析算法定义以及效率分析 2.2.1 Mean-shift 算法核函数概述算法核函数概述1 核函数密度估计是最常见的密度估计函数之一。在 d 维空间 d R 上对给定 武汉理工大学毕业设计(论文) 7 的n组数据，多元核函数和一个对称的正定矩阵,在,1, i x in( )K xddH 处的密度用一下公式给定：x (1) 1 1 ()() n Hi i f XKXX n 其中： (2) 1/2 1/2 ( )() H KxHK Hx d 维变量函数是一个有界函数，并且要同时满足一下条件33,p.95( )K x (3) ( )1 lim( )0 ( )0 ( ) d d d R d x R T K R K x dx xK x xK x dx xx K x dxc I 其中是常量。多元核函数可以通过单变量核函数用以下不同的方式产 k c 1( ) K x 生 (4) 1 1 ( )( ) d P i KxK x ,1 ( )() S k d KxaKx 其中是通过单变量核函数的累积而获得的，核函数是通过对单变( ) P Kx( ) S Kx 量核函数在维空间内的旋转而产生的，对与固定的半径，该函数的值都是相d 同的（即该函数关于半径对称） 。常数项确保了在整个平面内的积分 ,k d a( ) S Kx 值为 1。以上讨论的两种函数都可以满足公式(3)的条件，但根据我们的目的， 一般选择关于半径对称的方程作为核函数更加合适。 我们所需要的研究，是一系列关于半径对称的核函数 (5) 2 , ()() k d K XckX 在这种情况下，函数被称为是核函数在正半轴上（）的一个侧面( )k x0x (profile)。归一化常数确保了核函数的积分值为 1，是个严格正实数。 ,k d c 由于对矩阵的所有位置都参数化表示会大大增加问题的复杂度，所以在H 实际应用中，矩阵经常被简化为一个对角矩阵或者更直接H 22 1 , d Hdiag hh 地。后者明显好处是让参数变成了一个值，又一次降低了问题的 2 Hh I0h 复杂程度。这样，将代入到方程(2)中，可以得到核函数方程。在将核函数方H 程带到(1)中，就可以得到十分著名的密度估计方程 武汉理工大学毕业设计(论文) 8 (6) 1 1 ()() n i d i XX f XK nhh 该方程的估计质量，可以用实际密度与估计值之间误差的平均值和方差值 来表示。在实际应用当中只有当并且的速率要小于时，才有一n 0h 1 n 个渐近的估计。在两种由一元变量的方程来产生多元核函数方程的公式中，人 们测出（同时也证明了）最好的估计质量的核函数方程为33,p.104 (7) 1 ( ) 0 E x kx 01 1 x x 同时，它在维空间中，按照半径对称的形式进行扩展可以得到d (8) 2 1 1 (2)(1) ()2 0 d E cdX KX 1X otherwise 需要注意的是，该形式的核函数在边界出不存在导数。但如果需要导数存 在，则可以用核函数 (9) 1 ( )exp() 2 N kxx0x 同时它的多元形式为 (10) 2 /2 1 ()(2 )exp() 2 d N KXX 这种形式被称为正态核函数。这些核函数可以满足实际应用中的大多数需 求。把核函数形式代入到(6)中，密度估计可以重新写成： (11) 2 , , 1 ()() n k d i h K d i cXX fXk nhh 在特征空间分析的第一步，就是要分析特征的密度。很容易想到，密度最 密集的部分，其梯度，Meanshift 方法就是找到该点位置的一个快捷( )0f x 算法。 2.22 Mean-shift 算法梯度函数算法梯度函数 有了密度估计函数(11)，对其进行求导，便可以得到该密度函数的梯度 (12) 2 , , 2 1 2 ()()() () n k d i h Kh Ki d i cXX fXfXXX k nhh 定义方程 武汉理工大学毕业设计(论文) 9 (13) ( )( )g xk x 同时也定义与其相对应的算子 (14) 2 , ()() g d G XcgX 是对应的归一化常数。假设对一切 X，核函数的导数都存在。将代入 ,g d c( )g x 到(12)中，便得到 (15) 2 , , 2 1 , 1 2 1 1 2 ()() () () 2 () () n k d i ih K d i n i i n k d ii nd ii i cXX fXXX g nhh XX X g cXX h gX XXnhh g h 被假定为一个正实数。这个条件在实际应用中不难做到。在 1 () n i i XX g h (15)式中，各个公式都有很重要的意义。式中的第一项和(11)式形式十分近似， 因此可以将算子 G 代替(12)中的 K 算子，便得到(15)中的第一个乘项 (16) 2 , , 1 ()() n g d i h G d i c XX fXg nhh 第二项便是 mean-shift 向量 (17) 1 , 1 () () () n i i i h G n i i XX X g h mXX XX g h 这也就是表示，mean-shift 向量是用核函数加权的样本均值和 X 的差。将(16) 式和(17)式代入到方程(15)，便得到 (18) , , 2 , 2 ()()() k d h Kh Gh G g d c fXfXmX h c 也就是说 (19) ,2 , , () 1 () 2 () h K h G h G fX mXh c fX 武汉理工大学毕业设计(论文) 10 公式(19)表明，mean-shift 公式和带有算子 K 的密度方程的梯度成正比。在 Fukunaga 和 Hostetler1中，证明了该算法一个特性：Meanshift 向量会一直指向 密度增长最快的方向。该公式的启发性也是很大的，对于局部的均值，会让窗 口漂移至分布点密集的区域。由于 mean-shift 向量是根据该点的梯度计算出来 的，所以 mean-shift 向量可以给该点提供路线指向估计密度的一个稳定点。 Meanshift 算法就是通过这样的连续迭代来收敛到稳定点。低密度区域是不感兴 趣的区域，在这片区域内，由于算法的性质2，Meanshift 步长会比较大和快速， 相应的，在最大值附近，收敛步长会变慢，分析地就越仔细，因此该梯度是一 个自适应的梯度。 我们用来表示核函数 G 的位置序列（即 Meanshift 迭代序列） ，根 2, 1 jj y 据(17)式，我们可以得到 (20) n i ij n i ij i j h Xy g h Xy gX y 1 2 2 1 1 )( )( ,.2 , 1j 从中可以看出，核函数中心是以为中心根据算子 G 的加权均值算出来的。 1j y j y 是初始核函数中心位置，相应的 mean-shift 序列可以表示成 (21) )()( ,jKhKh yfjf 根据下面定理2陈述，可知和是收敛数列，同时也 2, 1 jj y , ( ) h K fj , ( ) h K fj 是以递增的数组。 2.2.3 Mean-shift 收敛定理证明以及算法综述收敛定理证明以及算法综述 定理定理 如果核函数 K 是由一个递减的凹函数所定义的，那么序列( )k x 和递减收敛2。 2, 1 jj y , ( ) h K fj 证明： 由于 n 是有限的，序列是有界的，根据序列的定义， , ( ) h K fj , ( ) h K fj 武汉理工大学毕业设计(论文) 11 22 1, , 1 (1)( )()() n jijik d h Kh K d i yxyxc fjfjkk nhhh (A .1) 根据凹函数的定义，对于所有的就有 1212 ,0,),x xxx 21121 ()()()()k xk xk xxx (A .2) 由于，(A.2)式可以化为( )( )g xk x (A .3) 21112 ()()()()k xk xg xxx 代入上式到(A.1)，得 (A .4) , 2 22 , 1 2 1 2 22 , 11 2 1 (1)( ) () ()2() h Kh K n jik d jiji d i n jik dTT jjjij d i fjfj yxc gyxyx nhh yxc gyyyxy nhh 根据(20)式，得到 (A .5) 2 2 , 1, 2 1 (1)( )() n jik d jjh Kh K d i yxc fjfjyyg nhh 由于在上单调递减，因此就是一个正实数。故只要( )k x0x 2 1 () n ji i yx g h ，(A.5)式子右端就是一个严格正的实数。由此可见，是一个 1jj yy , ( ) h K fj 递增的数列。又由于它有界，故是一个收敛数列。 然后，将(A.5)的连续 m 项累加，便得到 武汉理工大学毕业设计(论文) 12 2 2 1, 1, 2 1 2 2 , 1 2 1 22 , 11 2 2 , 2 ()( )(). () . n j mik d j mj mh Kh K d i n jik d jj d i k d j mj mjj d k d j mj d yxc fjmfjyyg nhh yxc yyg nhh c yyyyM nh c yyM nh (A .6) 表示上式的 m 个的最小值。由此可见，是个柯西数列，M 2 1 () n ji i yx g h 2, 1 jj y 也收敛。 2, 1 jj y 该定理确保了 Meanshift 的收敛性和值的递增性。 综上所述，综上所述，Meanshift 算法可以概述为以下步骤：算法可以概述为以下步骤： 对给定的点集和核函数和精度： 1,2 ii x ( )k x (1) 计算核函数的导数，同时选定初始点；( )( )g xk x 0 y (2) 根据算式(20)，计算，并且同时计算； 1j y ,1 () h Gjjj myyy (3) 令如果，则重复步骤(2),否则则进行(4)；1jj , () h Gj my (4) 返回，该点即为密度最大点。算法结束。 j y 当核函数为 之类的线性函数时，式中 1 ( ) 0 x k x 01 1 x x 的可以理解为窗口大小。当属于以为中心，半径长度为的圆 2 () i yx k h h i xyh 里面的时候，有大于 0 的值。由于，故在窗口的圆内部，有 ( )( )g xk x ，在圆外，有，于是，算式(20)，可以写为：( )1g x ( )0g x (22)1 i i xP j P x y N 武汉理工大学毕业设计(论文) 13 其中 P 表示以当前的为中心，为半径的圆。表示属于该圆的样本点 j yh P N 数目。由该式可见，Meanshift 算法非常简单，计算量小。实际应用中，有时候 也需要对样本点的重要性进行加权，但这并不会影响其收敛性和递增性3。加 权平均后，(22)式子可以表示为： (23) i i ii xP j i xP w x y w 其中，分母除以是为了将权值归一化（即和为 1） 。 i i xP w 从数学上看，Mean-shift 方法与牛顿爬山法类似，是一种基于梯度来求得 函数最大值的方法。从密度上看，mean-shift 算法有这密度检测功能，它能将搜 索窗口移至密度分布最大的位置。(算法过程如下图 1) 图 1 Mean-shift 原理图 武汉理工大学毕业设计(论文) 14 2.3 基于基于 Meanshift 的视频跟踪原理以及应用的视频跟踪原理以及应用 2.3.1 Meanshift 视频跟踪算法视频跟踪算法 本节根据前面讨论的 Mean-shift 算法，介绍该算法的应用之一，视频跟踪。 在做实时人脸感知系统5的时候，许多系统都将颜色模型运用在人脸感知 上。该方法是合理的，因为太多的统计数据会大大增加算法的复杂度从而使计 算变慢从而失去了跟踪的实时性。同时，在系统中增加太多的识别过程会让算 法变得难以运作。人脸跟踪系统最常见的模型是色相模型。该模型即是人脸色 相的直方图，该模型用在人脸感知系统的时候，是可以行得通的，因为人脸感 知只用感知人脸，在一般应用上不需要区别不同的人物。该模型的优点就是运 算快，效率好，计算机只用统计其直方图便能得到图像的特征。 在进行人脸感知系统的跟踪部分时，Bradski 应用人脸 HSV 色彩空间(如图 3)去取代 RGB 色彩空间（图 2） ，然后提取色相维度(hue)的直方图来用作目标 模型。这样做的好处就是可以根据人脸的肤色作为模型，去除亮度维度可以去 掉室内的光照影响，也就是说，去掉亮度对目标的影响，同时，在感知系统的 识别工作中，该直方图也可以用作识别的数据特征之一。研究表明，所有人 （除了白化病人之外）的色相是一致的，之所以有白人和黑人等之分，是因为 黑人皮肤的饱和度非常高，而白人的饱和度比较低，所以会有肤色上的差异。 也可以将饱和度(Saturation)和色相一并用作目标物体的模型，从而由一位模型 变为二维模型，进而可以改进跟踪的精度。 RGB 和 HSV 色彩空间的理解，可以如下图所示： 图图 2 RGB 色彩空间色彩空间 武汉理工大学毕业设计(论文) 15 图 3 HSV 的色彩空间示意图 由于现在的图像机制都是 RGB 图像，于是 RGB 图像转化为 HSV 图像需 要一些转换方法34，但这些方法都有一些共同的缺点，即当图像的饱和度和 亮度都很小的时候（或者两者中有一个很小的时候） ，所提取的色相噪点多，并 且所提取的色相并不稳定，波动性大。这意味着在一些十分黑暗的环境下， HSV 模型会不准确，也意味着以 HSV 色彩空间为模型的目标跟踪会失效。在 本文的跟踪算法里，会忽略掉那些饱和度或者亮度比较低的像素点。 反向投影也是直方图里的一个基本工具之一。该作用可以大致描述为，对 图像的一个已知区域，提取该图像的直方图，然后查找图像上所有像素，依照 直方图作为参考依据，可以判定该像素属于已知区域的概率值。我们根据这概 率值，可以进行跟踪。将属于0 , 1的概率值映射到0 , 255，可以让概率越是 渐近 1 的像素点就越是亮。比如对一个人脸直方图进行反向投影，可以得到的 武汉理工大学毕业设计(论文) 16 投影图如下（如图 4）： 图 4 反向投影成像（右）和原图（左） 由上节的 mean-shift 算法，我们可以知道可以加权改进该算法。我们根据 直方图的反向投影，算出视频中的每一个点属于目标的概率值，然后依据这些 概率值来作为权值给 mean-shift 算法进行加权求解。 确切地说，给定一个目标和直方图，我们可以用一下公式进行 Mean-shift 迭代： (24) (,) 1 (,) (,) (,) mnj mnj mnm xyP j mn xyP p xyx x p xy (,) 1 (,) (,) (,) mnj mnj mnn xyP j mn xyP p xyy y p xy 其中就是像素点经过反向投影后的概率值。该式即是(23)(,) mn p xy(,) mn xy 式中，将该点的概率值作为权值代入方程(23)中，从而得到该公式。(,) mn p xy i w 由此可知，根据 Mean-shift 加权的算法步骤如下： 输入一个图像和给定的直方图以及初始的搜索点和窗口半径，以 00 (,)xyh 及精度： 武汉理工大学毕业设计(论文) 17 (1) 计算该图像相对与模型直方图的反向投影，生成概率图像;( , )I x y (2) 对每个以搜索点为中心的窗口，计算该窗口内的概率图像的一阶矩和 零阶矩，公式如下： 00 ( , ) xy MI x y 10 ( , ) xy MxI x y 01 ( , ) xy MyI x y (3) 计算新的搜索中心 ， 10 00 c M x M 01 00 c M y M (4) 比较新旧搜索点，如果距离大于等于，则重复步骤(2)和(3)，否则， 返回，算法结束。 2.3.2 Meanshift 视频跟踪应用以及优缺点分析视频跟踪应用以及优缺点分析 运用该算法跟踪，得到的效果如下（如图 5，6）： 图 5 Meanshift 算法跟踪杯子的效果 武汉理工大学毕业设计(论文) 18 图 6 Meanshift 算法跟踪人脸的效果 该算法的优点是，对每一帧视频迭代快速，只需要求均值操作便可以有很好的 跟踪效果。其跟踪原理也很容易理解，即反向投影以后，利用 Meanshift 算法找 到白点密度分布最密集的位置。 （如图 7） 图 7 反向投影跟踪效果。 但该算法也有一些缺点。比如计算反向投影的时候要扫描整个图像，这样 的计算也是十分耗时的，在一些配置低端的计算机上，该算法实时性并不理想， 但对目前的主流计算