camshift目标跟踪算法毕业设计

camshift目标跟踪算法毕业设计内容摘要：

，对应的时间更新的方程用1( , )k k k kx f x v 来描述。 可以利用的方法集合 1,...{}kkz  和相应的状态方程( , )k k k kz h x n 相关。 概括的说， kf ， kh 都是非线性的向量，值都是随着时间变化的 1,....{}kkv  和 1,....{}kkn  都是噪声向量，并且假设为独立同分布 的随机变量。 当噪声向量是属于高斯分布， kf ， kh 都是线型算子的时候，最好的方法是用卡尔曼滤波法 (Kalman Filter)[8, ]，当 kf ， kh 都是非线性算子的时候，进行线型化就得到了扩展的卡尔曼滤波法 (Extended Kalman Filter, EKF)[8]，两种方法的后验概率分布都是高 斯型。 有一个另类的卡尔曼滤波法叫做 Unscented Kalman Filter(UKF)[9], 该方法根据一些离散的样本点求出后验概率的均值和方差。 当状态空间是离散而且由有限个状态组成的时候，隐马尔科夫 (Hidden Markov Models, HMM)滤波 [10]可以用来做跟踪。 最一般的滤波族是粒子滤波[11]，也叫 booststrap 滤波，是基于蒙特卡罗积分法的滤波方式。 当跟踪于一个多目标的混乱环境下，一些跟踪方法的有效性和关联性就产生了。 最近邻居法 (Nearest Neighbor Filter)和概率数据关联法 (Probabilistic Data Association Filter)对一个单目标都是有效的。 这些做法的假设是，对于一个给定武汉理工大学毕业设计 (论文 ) 4 的目标来说，只有一种方法是有效的，其余的方法都是随机的干扰。 这就是说，独立同分布的均匀分布量。 连接数据关联度滤波 (Joint Data Association Filter(JPDAF)[8, ], 于此同时，计算了方法和目标的关联度概率把所有目标都联系起来。 一个与众不同的方法是多重假设滤波 (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 来进行图像跟踪。 基于目标建模和定位的跟踪算法研究现状 在另一方面，目标跟踪算法的第二派系：基于目标的建模与定位的跟踪。 当滤波和数据关联度在控制理论中已经拥有了它们的基础，但基于目标建模和定位的跟踪算法更加贴近图像，同时也和配准方法 [20]有类似之处。 目标定位和配准方法都是最大化似然函数。 区别在于，在跟踪的时候，连续的两帧图像里的位置和目标的模型数据的变化不会太大，这点是和 配准方法截然相反的。 目前有许多学者根据这点特性做了许多算法，基于梯度的算法 [21]是根据归一化的相关度来进行跟踪，然后相关度有所缺点，就是对光照特别敏感。 Hager 和 Belhumeur [22]明确地建立了几何光照的变化模型，该方法又由 Sclaroff 和 Isidoro[23] 进一步的改进。 对模型的训练学习是建立在一些稳定的图像结构，运动信息和一些异常过程 [24]的基础之上的。 在不同的做法上， Ferrari 等人 [25]提出了一种基于平坦区域和箭头的跟踪器。 跟踪人的时候，会产生很多问题，这些问题大部 分都是由人们的三维移动的无规律性而产生的。 在一些文献中，这种问题被大量地详细分析 [26][27]。 与此同时人的直接跟踪法 [28]时间复杂度高，而且经常会用上一些其它的模型 [29][30]。 主要研究内容 本文的主要目的是研究 Meanshift 算法，并且将其用于目标跟踪，进而提出一套改进的 Meanshift 算法，使其能够自适应物体的大小进行跟踪。 其内容可以大致分为三个部分： 1) 推出了一种基于目标建模和定位的跟踪算法，该算法为跟踪非刚性物体提供武汉理工大学毕业设计 (论文 ) 5 了新的框架。 首先介绍并分析了 meanshift 算法的收敛 特征，初步介绍了该算法在计算机视觉领域的应用并且成功地解决了视觉领域许多问题； 2) 对跟踪的目标建立直方图模型，并为跟踪算法提供依据。 最后，利用 Meanshift算法对其进行跟踪并且分析其算法复杂度和该算法的优势； 3) 在 Meanshift 的基础之上，建立一个能够自适应目标大小的 camshift 算法，同时将全局运算改为对图像的局部进行运算，从而可以大大节省运算量。 并将此算法用作跟踪。 武汉理工大学毕业设计 (论文 ) 6 2 Mean Shift 跟踪器设计 引言 Mean Shift 算法，在 1975 年就已经被 Fukunaga 和 Hostetler [1]等人提出，当时几乎快被人们遗忘，直到 Cheng 的一篇论文 [31]才点燃了人们对该算法的兴趣。 尽管该算法有其优越的特性，但该算法在统计领域并不为人所知。 一本书 [32]讨论了用 Meanshift 做密度检测的优点时，这个算法才被统计领域所发现并广泛使用。 正如接下来将要讨论和介绍的一样，基于 Meanshift 的算法在特征分析空间中是个十分多样化的工具，对计算机视觉领域的许多问题都提出了很好的解决办法 [3]。 本文的主要介绍 的是 Meanshift 在跟踪问题上的应用。 该论文介绍了对目标进行核函数建模 ,并将核函数和目标模型的相关度作为对比依据，这样，一个跟踪问题就简化为在连续两帧图像里搜寻相关度最大位置的问题。 由于建立的相关度摸型是个连续函数，因此，基于梯度的方法便可以使用，使得该优化方法会比优化的搜索方法要快速许多。 候选目标与目标的相似度是用 Bhattacharyya 的相关系数。 在跟踪这方面， Bhattacharyya 相关系数的实际意义就是对候选目标进行打分。 新的目标模型和定位也可以选择通过多种滤波和数据关联度的方法进行卷积。 本论文成功的进行了很多跟踪方法，处理了许多复杂的跟踪问题。 论文的大致框架如下：在第二节，对 Meanshift 算法的定义和性质进行了详细分析。 在第三节，将直方图作为目标的主要模型，通过对直方图的对比来提取图像中与目标相近的点，然后 Meanshift 方法用于目标跟踪，并对其方法进行详细介绍和跟踪效率进行分析。 最后，结合跟踪算法的核函数模型 [4]和 camshift算法的自适应大小的特征，利用两者的优点做出实时的视频跟踪算法。 Meanshift 算法定义以及效率分析 Meanshift 算法核函数概述 [1] 核函数密度估计是最常见的密度估计函数之一。 在 d 维空间 dR 上对给定的n 组数据 , 1,....,ix i n ，多元核函数 ()Kx和一个 dd 对称的正定矩阵 H ,在 x 处的密度用一下公式给定： 11( ) ( )n Hiif X K X Xn (1) 武汉理工大学毕业设计 (论文 ) 7 其中： 1 / 2 1 / 2( ) ( )HK x H K H x  (2) d 维变量函数 ()Kx是一个有界函数，并且要同时满足一下条件 [33,] ( ) 1l i m ( ) 0( ) 0()dddRdxRTKRK x d xx K xx K x d xx x K x d x c I (3) 其中 kc 是常量。 多元核函数可以通过单变量核函数 1()Kx用以下不同的方式产生 11( ) ( )dPiK x K x ,1( ) ( )S kdK x a K x (4) 其中 ()PKx是通过单变量核函数的累积而获得的，核函数 ()SKx是通过对单变量核函数在 d 维空间内的旋转而产生的，对与固定的半径，该函数的值都是相同的（即该函数关于半径对称）。 常数项 ,kda 确保了 ()SKx在整个平面内的积分值为1。 以上讨论的两种函数都可以满足公式 (3)的条件，但根据我们的目的，一般选择关于半径对称的方程作为核函数更加合适。 我们所需要的研究，是一系列关于半径对称的核函数 2,( ) ( )kdK X c k X (5) 在这种情况下，函数 ()kx 被称为是核函数在正半轴上（ 0x ）的一个侧面(profile)。 归一化常数 ,kdc 确保了核函数的积分值为 1，是个严格正实数。 由于对矩阵 H 的所有位置都参数化表示会大大增加问题的复杂度，所以在实际应 用中，矩阵 H 经常被简化为一个对角矩阵 221[ , ...., ]dH diag h h 或者更直接地 2H hI。 后者明显好处是让参数变成了一个值 0h ，又一次降低了问题的复杂程度。 这样，将 H 代入到方程 (2)中，可以得到核函数方程。 在将核函数方程带到 (1)中，就可以得到十分著名的密度估计方程 11( ) ( )n idiXXf X Kn h h  (6) 该方程的估计质量，可以用实际密度与估计值之间误差的平均值和方差值来表示。 在实际应用当中只有当 n 并且 0h 的速率要小于 1n 时，才有一个渐近的估计。 在两种由一元变量的方程来产生多元核函数方程的公式中，人们测出武汉理工大学毕业设计 (论文 ) 8 （同时也证明了）最好的估计质量的核函数 方程为 [33,] 1()0Exkx   011xx (7) 同时，它在 d 维空间中，按照半径对称的形式进行扩展可以得到 211 ( 2) (1 )() 20dEc d XKX    1Xotherwise (8) 需要注意的是， 该形式的核函数在边界出不存在导数。 但如果需要导数存在，则可以用核函数 1( ) e x p ( )2Nk x x 0x (9) 同时它的多元形式为 2/2 1( ) ( 2 ) e x p ( )2dNK X X  (10) 这种形式被称为正态核函数。 这些核函数可以满足实际应用中的大多数需求。 把核函数形式代入到 (6)中 ，密度估计可以重新写成： 2, 1( ) ( )nkd ihK d ic XXf X kn h h  (11) 在特征空间分析的第一步，就是要分析特征的密度。 很容易想到，密度最密集的部分，其梯度 ( ) 0fx， Meanshift 方法就是找到该点位置的一个快捷算法。 Meanshift 算法梯度函数 有了密度估计函数 (11)，对其进行求导，便可以得到该密度函数的梯度 2,2 12( ) ( ) ( ) ( )nkd ih K h K id ic XXf X f X X X knh h      (12) 定义方程 ( ) ( )g x k x (13) 同时也定义与其相对应的算子 2,( ) ( )gdG X c g X (14) 武汉理工大学毕业设计 (论文 ) 9 ,gdc是对应的归一化常数。 假设对 一切 X，核函数的导数都存在。 将 ()gx 代入到(12)中，便得到 2, 21, 12112。