CamShift 目标跟踪算法设计毕业论文.doc

Comment m1 使用系统自动生成目 录 CamShift 目标跟踪算法 设计毕业论文 目目 录录 摘摘 要要 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 Comment m2 黑体小二 居左 Comment m3 黑体小三 居左 Comment m4 黑体小三 Comment m5 黑体 4 号 武汉理工大学毕业设计 论文 3 1 绪论绪论 1 1 背景分析 实时跟踪算法一直在很多计算机视觉领域里是个难题 例如在监控系统 感知用户界面 基于目标的视频压缩算法 汽车驾驶辅助系统等等尖端领域里 都是一个没有被解决的难题 传统的视觉跟踪器可以分为两大派别 一种是目 标的建模以及定位 是处理目标的现状和变化一种由下至上的过程 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 武汉理工大学毕业设计 论文 4 行线型化就得到了扩展的卡尔曼滤波法 Extended Kalman Filter EKF 8 两种 方法的后验概率分布都是高斯型 有一个另类的卡尔曼滤波法叫做 Unscented Kalman Filter UKF 9 该方法根据一些离散的样本点求出后验概率的均值和方 差 当状态空间是离散而且由有限个状态组成的时候 隐马尔科夫 Hidden Markov Models HMM 滤波 10 可以用来做跟踪 最一般的滤波族是粒子滤波 11 也叫 booststrap 滤波 是基于蒙特卡罗积分法的滤波方式 当跟踪于一个多目标的混乱环境下 一些跟踪方法的有效性和关联性就产 生了 最近邻居法 Nearest Neighbor Filter 和概率数据关联法 Probabilistic Data 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 和 Isidoro 23 进一步的改进 对模型的训练学习是建立在一些稳定的图像结构 运动信息和一些异常过程 24 的基础之上的 在不同的做法上 Ferrari 等人 25 武汉理工大学毕业设计 论文 5 提出了一种基于平坦区域和箭头的跟踪器 跟踪人的时候 会产生很多问题 这些问题大部分都是由人们的三维移动的无规律性而产生的 在一些文献中 这种问题被大量地详细分析 26 27 与此同时人的直接跟踪法 28 时间复杂度 高 而且经常会用上一些其它的模型 29 30 1 3 主要研究内容主要研究内容 本文的主要目的是研究 Meanshift 算法 并且将其用于目标跟踪 进而提出 一套改进的 Meanshift 算法 使其能够自适应物体的大小进行跟踪 其内容可以 大致分为三个部分 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 方法用于目标跟踪 并对其方法进 武汉理工大学毕业设计 论文 7 行详细介绍和跟踪效率进行分析 最后 结合跟踪算法的核函数模型 4 和 camshift 算法的自适应大小的特征 利用两者的优点做出实时的视频跟踪算法 2 2 Mean shift 算法定义以及效率分析算法定义以及效率分析 2 2 1 Mean shift 算法核函数概述算法核函数概述 1 核函数密度估计是最常见的密度估计函数之一 在 d 维空间 d R 上对给定 的n组数据 多元核函数和一个对称的正定矩阵 在 1 i x in K xdd H 处的密度用一下公式给定 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 的条件 但根据我们的目的 一般选择关于半径对称的方程作为核函数更加合适 我们所需要的研究 是一系列关于半径对称的核函数 武汉理工大学毕业设计 论文 8 5 2 k d K XckX 在这种情况下 函数被称为是核函数在正半轴上 的一个侧面 k x0 x profile 归一化常数确保了核函数的积分值为 1 是个严格正实数 k d c 由于对矩阵的所有位置都参数化表示会大大增加问题的复杂度 所以在H 实际应用中 矩阵经常被简化为一个对角矩阵或者更直接H 22 1 d Hdiag hh 地 后者明显好处是让参数变成了一个值 又一次降低了问题的 2 Hh I 0h 复杂程度 这样 将代入到方程 2 中 可以得到核函数方程 在将核函数方H 程带到 1 中 就可以得到十分著名的密度估计方程 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 kxx 0 x 同时它的多元形式为 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 在特征空间分析的第一步 就是要分析特征的密度 很容易想到 密度最 武汉理工大学毕业设计 论文 9 密集的部分 其梯度 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 定义方程 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 向量 武汉理工大学毕业设计 论文 10 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 公式 19 表明 mean shift 公式和带有算子 K 的密度方程的梯度成正比 在 Fukunaga 和 Hostetler 1 中 证明了该算法一个特性 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 1 j 从中可以看出 核函数中心是以为中心根据算子 G 的加权均值算出来的 1 j y j y 是初始核函数中心位置 相应的 mean shift 序列可以表示成 21 jKhKh yfjf 武汉理工大学毕业设计 论文 11 根据下面定理 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 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 x0 x 2 1 n ji i yx g h 武汉理工大学毕业设计 论文 12 A 5 式子右端就是一个严格正的实数 由此可见 是一个 1jj yy h K fj 递增的数列 又由于它有界 故是一个收敛数列 然后 将 A 5 的连续 m 项累加 便得到 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 武汉理工大学毕业设计 论文 13 22 1 i i xP j P x y N 其中 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 武汉理工大学毕业设计 论文 14 图 1 Mean shift 原理图 2 3 基于基于 Meanshift 的视频跟踪原理以及应用的视频跟踪原理以及应用 2 3 1 Meanshift 视频跟踪算法视频跟踪算法 本节根据前面讨论的 Mean shift 算法 介绍该算法的应用之一 视频跟踪 在做实时人脸感知系统 5 的时候 许多系统都将颜色模型运用在人脸感知 上 该方法是合理的 因为太多的统计数据会大大增加算法的复杂度从而使计 算变慢从而失去了跟踪的实时性 同时 在系统中增加太多的识别过程会让算 法变得难以运作 人脸跟踪系统最常见的模型是色相模型 该模型即是人脸色 相的直方图 该模型用在人脸感知系统的时候 是可以行得通的 因为人脸感 知只用感知人脸 在一般应用上不需要区别不同的人物 该模型的优点就是运 算快 效率好 计算机只用统计其直方图便能得到图像的特征 在进行人脸感知系统的跟踪部分时 Bradski 应用人脸 HSV 色彩空间 如图 3 去取代 RGB 色彩空间 图 2 然后提取色相维度 hue 的直方图来用作目标 武汉理工大学毕业设计 论文 15 模型 这样做的好处就是可以根据人脸的肤色作为模型 去除亮度维度可以去 掉室内的光照影响 也就是说 去掉亮度对目标的影响 同时 在感知系统的 识别工作中 该直方图也可以用作识别的数据特征之一 研究表明 所有人 除了白化病人之外 的色相是一致的 之所以有白人和黑人等之分 是因为 黑人皮肤的饱和度非常高 而白人的饱和度比较低 所以会有肤色上的差异 也可以将饱和度 Saturation 和色相一并用作目标物体的模型 从而由一位模型 变为二维模型 进而可以改进跟踪的精度 RGB 和 HSV 色彩空间的理解 可以如下图所示 图图 2 RGB 色彩空间色彩空间 武汉理工大学毕业设计 论文 16 图 3 HSV 的色彩空间示意图 由于现在的图像机制都是 RGB 图像 于是 RGB 图像转化为 HSV 图像需 要一些转换方法 34 但这些方法都有一些共同的缺点 即当图像的饱和度和 亮度都很小的时候 或者两者中有一个很小的时候 所提取的色相噪点多 并 且所提取的色相并不稳定 波动性大 这意味着在一些十分黑暗的环境下 HSV 模型会不准确 也意味着以 HSV 色彩空间为模型的目标跟踪会失效 在 本文的跟踪算法里 会忽略掉那些饱和度或者亮度比较低的像素点 反向投影也是直方图里的一个基本工具之一 该作用可以大致描述为 对 图像的一个已知区域 提取该图像的直方图 然后查找图像上所有像素 依照 直方图作为参考依据 可以判定该像素属于已知区域的概率值 我们根据这概 率值 可以进行跟踪 将属于 0 1 的概率值映射到 0 255 可以让概率越是 渐近 1 的像素点就越是亮 比如对一个人脸直方图进行反向投影 可以得到的 武汉理工大学毕业设计 论文 17 投影图如下 如图 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 及精度 武汉理工大学毕业设计 论文 18 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 算法跟踪杯子的效果 武汉理工大学毕业设计 论文 19 图 6 Meanshift 算法跟踪人脸的效果 该算法的优点是 对每一帧视频迭代快速 只需要求均值操作便可以有很好的 跟踪效果 其跟踪原理也很容易理解 即反向投影以后 利用 Meanshift 算法找 到白点密度分布最密集的位置 如图 7 图 7 反向投影跟踪效果 但该算法也有一些缺点 比如计算反向投影的时候要扫描整个图像 这样 的计算也是十分耗时的 在一些配置低端的计算机上 该算法实时性并不理想 但对目前的主流计算机来说 对一般清晰度的视频 该计算量并不成问题 但 视频如果分辨率高 则会造成很明显的延迟 其次 该算法的窗口大小有待改进 原因是由于视频当中 如果人物由进 到远的行动 人物在视频中会变小 但窗口不变 这意味着大小不变的窗口会 包括人脸 但也会包括和人脸无关的区域 这会严重影响跟踪效果 如图 8 武汉理工大学毕业设计 论文 20 图 8 人的距离变化导致跟踪失效 因此 在跟踪物体与摄像机位置发生变化时 Meanshift 算法跟踪器会失效 失效的原因在于窗口大小没有随着人脸大小而进行相应调整 从而导致窗口内 的密度分布变稀疏 Meanshift 算法失去了实用性 根据该缺陷 人们提出了许 多改进方法 其中非常有效的一种是 Camshift 5 跟踪算法 此外 本文也提出 了一种局部运算的 Camshift 算法 大大改善了跟踪效果 3 局部局部 Camshift 算法原理以及实践算法原理以及实践 3 1 Camshift 跟踪器跟踪器 3 1 1 Camshift 算法原理算法原理 Camshift 算法全称是 Continuously Adaptive Mean Shift Algorithm 是由 Meanshift 的改进算法 该算法可以实现针对物体在视频中的大小进行自适应调 整 从而大大改善跟踪效果 Camshift 5 充分利用了 Mean shift 算法的计算简单快捷的优点 并且在 不增加计算复杂度的同时 实现了自适应的窗口大小控制 在 Mean shift 迭代 完成之后 改进的算法都会对窗口大小进行调整 窗口调整的原理如下 对一副灰度连续图像 如果将该图像投影至 3 维平面内 横纵坐标分别为 对应的图像维度 z 轴范围为 0 255 其数值为在该点对应图像中的像素的灰 度值 因此 可以定义一个图像的灰度体积为 25 VI x y dxdy 利用灰度体积除以图像的平均灰度值 就可以得到图像的面积 S 武汉理工大学毕业设计 论文 21 26 V S I 其中为图像区域的平均灰度值 由于计算机图像为离散图像 故有I 27 VI x y 而为了保守图像的大小 我们采用像素最大值 即 255 来代替平均灰度值 这么做的原因 是一方面 我们希望跟踪窗口尽可能的小 以便我们在跟踪的 时候让窗口尽可能地不让无关物体进入 于是我们采取使用灰度最大值来代替 灰度平均值 当然也不能太过于小 这样容易造成跟踪窗口的尺寸太小而导致 算法容易收敛到局部最大值 因此 我们将窗口宽度设置为 28 00 2 256 M s 之所以开根号是为了长度量纲保持一致 由于人脸的形状是椭圆型 长度可以 设置为宽度的 1 2 倍 即 1 2ls 我们也可以根据需要 输出人脸的偏移角度 根据 5 可以得出 椭圆的旋转 角度为 29 11 00 22 2002 0000 2 arctan 2 cc cc M x y M MM xy MM 其中 是窗口的中心点 2 20 xy Mx I x y 2 02 xy My I x y cc xy 该算法的步骤如下 给定图像和目标直方图 窗口大小 已知精度h 1 将搜索初始点设置为目标初始位置 对给定的图像和目标直方图 进行全 局的反向投影 2 由上面的 Meanshift 算法进行迭代运算 收敛后 返回跟踪目标的零阶矩 00 M 武汉理工大学毕业设计 论文 22 3 由 28 式进行窗口的尺寸计算 并且按照该公式跟新窗口大小 4 根据更新大小的窗口作为下一帧视频的初试窗口 并且将 Meanshift 所得 到的迭代窗口中心重新作为目标初始位置 进行 2 若是视频结束 则返 回 跟踪效果如下 图 9 Camshift 算法跟踪效果 原图与对应的反向投影图 同时 该方法也有效地解决了物体里视频位置改变而产生的跟踪问题 效果如 下 武汉理工大学毕业设计 论文 23 图 10 Camshift 算法跟踪距离改变的目标 3 1 2 CamShift 算法优缺点分析算法优缺点分析 由于该算法属于一种自适应算法 根据跟踪的目标估算出其面积 并且使 得窗口做自适应调整 故该算法的使用 使得跟踪的稳定性显著提高 视频过 程中如果有其它物体干扰 对结果的影响并不大 图 11 手的干扰对跟踪的影响不大 但 Camshift 算法也有缺陷 不光是在反向投影过程中 全局运算增加了不 必要的运算负担 同时全局运算也会大大降低跟踪质量 原因主要是因为在亮 度不强的背景区域 反向投影会产生噪点 其原因是因为在 RGB 转换到 HSV 空间的时候 亮度或饱和度不大的映射稳定性不高 导致一些无关点也被当成 目标区域 原因如下图 图 12 跟踪效果不理想的原因是白点的错误分布 武汉理工大学毕业设计 论文 24 3 2 局部局部 Camshift 算法算法 3 2 1 局部局部 Camshift 算法原理算法原理 根据上述对 Camshift 算法的跟踪缺点分析 白点的错误分布是因为进行了 全局运算而导致 全局运算不仅仅增大了运算量 并且无关的计算容易让更多 无关的物体干扰跟踪算法 将算法由全局改成局部 有效的改善了跟踪效果 我们可以初步分析 无论是 Camshift 算法 还是 Meanshift 算法 如果经过反 向投影的图像 只有目标区域有离散的白点 其余区域没有 那么 这种投影 的跟踪肯定是成功的 因为图像的数据分布密集点只有一处 即目标位置 而 Camshift 算法或者 Meanshift 算法 其作用都是找到数据密集处 让反向投影的全局计算修改为局部计算 即让反向投影的范围限制在搜索 窗口的内部进行 这样不仅仅可以大大减少计算量 也可以保证跟踪质量 从 而更有效地进行跟踪 该算法如下 对给定的图像和目标直方图 初始窗口和精度 1 首先 设定初试窗口的位置 准备跟踪 2 计算一个比当前窗口稍微更大一些的范围内的反向投影值 3 使用 Meanshift 算法迭代 收敛后 返回跟踪目标的零阶矩和收敛位置 00 M 4 以收敛位置为中心建立窗口 由 28 式进行窗口的尺寸计算 并且按照该公 式更新窗口大小 5 根据更新的窗口作为下一帧视频的初试窗口 并且将 Meanshift 所得到的迭 代窗口中心重新作为目标初始位置 进行 2 若是视频结束 则返回 利用该算法做跟踪 效果如下 武汉理工大学毕业设计 论文 25 图 13 改进后的跟踪效果图 由图 12 系列可以看出 在改进之后 周围背景与人脸无关的区域的噪点有效 减少 从而也在降低计算量的同时 改善了跟踪效果 同时在距离改变的跟踪 上 问题也得到了明显改善 搜索窗口几乎很少出错 其原因正是因为限制了 反向投影的区域 使得白色点尽可能分布在搜索区域附近 效果如图 图 14 目标物体距离改变的跟踪效果 3 2 2 局部局部 Camshift 算法的优缺点分析算法的优缺点分析 该方法的优点 就是计算量非常小 跟踪的实时性好 这是由于我们 将全局的运算改为局部的运算而导致的 但该方法也有缺点 就是当视频中 武汉理工大学毕业设计 论文 26 目标移动较快的时候 有时候会出现跟踪失败的情况 原因是因为由于全局 运算改为局部运算 这样就会出现在连续两帧内 由于目标移动太快速而导 致突然从窗口中消失 窗口中没有目标的数据从而停止了移动 导致跟踪失 效 同时 由于跟踪的模型是建立在颜色模型的基础之上 无论是局部 Camshift 还是全局 Camshift 都有可能让跟踪窗口包括与目标无关的物体里 面 因此 跟踪最大的改进位置就是对目标的模型描述 如果能在跟踪的过 程中 能够对物体的形状进行描述 则该物体可以进行准确跟踪 因此 提 高模型对物体的描述才是关键 4 局部局部 Camshift 算法与算法与 Camshift 算法对比算法对比 为了进一步说明局部 CamShift 算法的优点 我们将传统的 CamShift 和局部 的 CamShift 算法进行比较 从效率以及迭代次数出发进行对比 分析局部 CamShift 算法的优缺点 4 1 局部局部 Camshift 算法的跟踪效果比较算法的跟踪效果比较 由于 CamShift 算法是基于图像的全局信息基础之上 当室内亮度不够 光 线不足的时候 容易造成色相提取的误差 并且色相运算并不稳定 导致反向 投影图有许多和目标无关的噪点 严重干扰了跟踪算法 以及跟踪的稳定性 如图 15 武汉理工大学毕业设计 论文 27 图 15 跟踪效果对比 左图为 Camshift 右图为局部 Camshift 由此可见 当室内光线十分昏暗的时候 局部 Camshift 算法可以有效地改 进跟踪效果 对目标无关的噪点进行排除 以达到跟踪效果 其原因 就是因 为在其方向投影图上 与目标无关的噪点大大减少 从而保证了跟踪质量 图 16 说明了反向投影的效果 图 16 反向投影效果对比 左图为 Camshift 右图为局部 Camshift 4 2 局部局部 Camshift 算法的迭代次数比较算法的迭代次数比较 由于局部 Camshift 算法把与目标相关的离散数据点位于一定范围内部 所 以 与目标无关的数据点会大大减少 无关数据的干扰作用也会大大减低 因 此迭代更快 我们测试对同一个视频进行跟踪 发现迭代次数在室内昏暗的时 候有所降低 原因是因为当室内光线昏暗的时候 反向投影的效果比较多 严 重影响了算法收敛方向和速度 如图 17 武汉理工大学毕业设计 论文 28 图 17 两种算法的迭代次数对比 昏暗环境下 跟踪效果如图 15 但是 当室内环境光线充足的时候 该算法的迭代速度并没有明显的改进 只 是略微减少 效果如下图 图 18 室内光线充足的情况下跟踪对比 左图为 Camshift 右图为局部 Camshift 其原因 是因为反向投影都是一样 因为室内光线充足 色相转换失真比较少 所以跟踪效果都很好 反向投影效果如下图 图 19 反向投影效果对比 左图为 Camshift 右图为局部 Camshift 武汉理工大学毕业设计 论文 29 跟踪的迭代次数对比 如下图 图 20 迭代次数对比 尽管局部 CamShift 改变了迭代效率 减轻了计算机的运算负担 但是当反 向投影的计算面积过于小的时候 也会产生跟踪失效 原因是因为一方面跟踪 目标运动过快 另一方面是因为反向投影运算面积太小而导致跟踪失效 如下 图 图 21 物体快速运动下局部反向投影的跟踪失效 但是 全局的 CamShift 在室内光线充足的情况下 很少出现这种情况 5 总结与展望总结与展望 5 1 论文总结论文总结 本论文详细讨论了 Mean shift 算法原理 以及介绍了将其用作跟踪的的原 理和方法 随后讨论了改进的 Camshift 算法已经自己改进的 Camshift 算法 并 武汉理工大学毕业设计 论文 30 且都有大量的实例来演示其跟踪效果 Meanshift 算法是先用核函数来估计数据的密度分布 核函数的要求就是 递减函数的凹函数 这在实际应用中都很容易实现 应用核函数估计出密度分 布后 再使用 Mean shift 算法来找到密度函数的最大值 Mean shift 算法本质上 是一种利用基于梯度的算法 其性质和牛顿算法有些类似 即在最优值很远的 地方收敛很慢 但在离最优值很近的地方收敛速度很慢 但是 Meanshift 并不是 牛顿梯度法 牛顿梯度法使用的是二阶导数和一阶导数 而 Meanshift 只用了函 数一阶导数 运算简单快捷 我们不用计算密度函数便可以求出 Meanshift 向量 Meanshift 算法用到跟踪的时候 就是要用到加权的 Mean shift 向量公式 其原理在与将人脸通过某种模型来提取数据 得到的图像将是一副在人脸部分 的数据分布密集 在其它无关部分数据分布稀疏的图像 由于 Meanshift 算法最 本质的作用在于找到数据分布最密集的点 于是可以通过 Meanshift 算法进行迭 代 是窗口位于数据分布最密集的位置 从而达到跟踪效果 由于 Meanshift 算法做跟踪时 会有窗口大小无法调整的缺陷 于是本文 在介绍 Meanshift 算法后 讲述了 Camshift 算法 该算法改正了 Meanshift 算法 缺点 让跟踪窗口与目标大小进行自适应调整 从而改善了跟踪效果 同时 本文结合 Camshift 算法的优点 提出局部的 Camshift 算法 使得对目标模型的 计算从整个图像变为稍微比跟踪窗口大一点的局部运算 从而产生了跟踪效果 更好地局部 Camshift 跟踪算法 有些人认为 Meanshift 或者 Camshift 跟踪只能建立在颜色模型上 这种 见解是错误的 实时上 Camshift 的直方图模型不光是可以建立颜色直方图 也可以建立轮廓直方图 该方法是近期提出来的一种新方法 用直方图来统计 物体轮廓的方向向量 从而对物体实现了几何上的描述 该方法也可以用于论 文中 让目标物体同时从几何上和颜色上进行描述 可以有更准确的跟踪方法 5 2 研究展望研究展望 相比那些和滤波以及数据关联度的跟踪算法 Meanshift 算法的计算量已经 是大大降低了 然而 跟踪的准确度依旧有待提高 修改该问题的方法 就是 在跟踪过程中 对物体的模型进行修改 个人觉得 最好的模型莫过于对物体的形状描述以及颜色描述 然而 目 前的许多跟踪算法中 都没有加入对形状描述的算法 原因是对图像中的形状 描述起来并不容易 即使有描述的方法 计算量也过大 用在跟踪里会导致跟 踪失去实时性 同时 跟踪算法是个优化的算法 所有优化的算法有一个通病 武汉理工大学毕业设计 论文 31 就是会收敛到局部极值 有时候 该值并不是我们想要的 因此 为了避免优 化算法的缺陷 可行的办法就是在建模的时候 尽可能让整个图像只出现一个 最大值 或者让提取出来的数据尽可能集中在一个区域 这样就可以保证收敛 总是处于正确位置 跟踪算法应用广泛 是有十分大的商业潜力的 由于人脸感知系统的诞生 计算机可以通过人脸的旋转和移动控制 3D 游戏的操作 也可以在许多其它方 面 如交通监控 室内监控都起到很多作用 因此 开发一套好的跟踪算法 是很有必要的 希望今后随着计算机发达 能做出跟精确的跟踪算法 Comment m6 黑体小二号 居中 武汉理工大学毕业设计 论文 32 参考文献 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 Blaz Fortuna Kernel Canonical Correlation Analysis With Applications Department of Knowledge Technologies Jozef Stefan Institute 3 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 4 D Comaniciu V Ramesh and P Meer Real Time Tracking of Non Rigid Objects Using Mean Shift Proc Eighth Int lConf Computer Vision vol 21 pp 331 337 1996 5 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 6 D DeCarlo and D Metaxas Optical Flow Constraints on Deformable Models with Applications to Face Tracking Int l J Computer Vision vol 38 no 2 pp 99 127 2000 7 R Wildes R Kumar H Sawhney S Samasekera S Hsu H Tao Y Guo K Hanna A Pope D Hirvonen M Hansen and P Burt Aerial Video Surveillance and