第4期 刘翠君，等：粒化的Mean Shift行人跟踪算法 .437. 表1MS和GMS的运算代价 Table 1 The calculation cost of MS and GCMS (11) 代价 MS GMS 基于巴氏系数，求得目标区域的参考颜色直方图 Cu RC+ C'H=R'C.+ 直方图 q和目标候选区域的颜色直方图p(y。)的相似度为 R(C。+3Cm+C.)R'(C。+3C,+C。) plp(),9]=∑p.o)9 (12) C,=u(C.+C)+ C',=u'(Cm+ 新位置 至此，粒化的MS行人跟踪算法的MS跟踪迭代 R(3C+C.) Ca)+R'(3C+C.) 步骤可以总结为算法1。 C。= 相似度 C'。= 算法1粒化的Mean Shift行人跟踪算法 u(C,+C.+C.) u'(C,+C.+C.) (GMS) 表中C。、C。、Cm、C。、C,、Cd、C,分别表示 输入行人跟踪视频图像序列。 核函数加权、获取像素值、浮点数乘法、加法、移位运 初始化图像粒度R,=3和颜色通道粒度 算、除法运算和开方的计算代价：R、u分别表示MS R=5,R=6,R=3;给定行人目标初始中心位置 算法中的行人目标区域大小及颜色直方图的级数； y。及行人目标区域核半径h,由式(9)得到行人目 R'、u'分别表示GMS算法中的行人目标区域大小 标区域经过粒化后的参考颜色直方图q。 及颜色直方图的级数；满足近似关系R/R'=4, 跟踪过程 u/u'≈5，Cm和C,的关系无法准确比较，但是Cm> 1)以y。为行人目标初始中心位置，分别由式 C,一定成立。至此可近似估计出MS和GMS的每 (11)和式(12)计算{p.(o)=12“,。 和 次迭代的计算代价关系，为式(13)。理论计算得 出，仅考虑各运算代价时，GMS算法比MS算法的计 p[p）9]=∑p.09.。 算代价至少快4倍，是个可观的结果。在实际实验 2)计算权值{w:}=12,…,R,0 中，由于图像分块函数消耗、硬件等原因会使得真正 计算效率低于4倍。 o,=∑δef(L)-u, qu P.(Yo) Cm+C,+Cp≈4 (13) 3)计算行人目标新位置y1: C'H+C',+C。 ∑x,1 3实验结果与分析 在CPU2.6GHz、内存4GB的PC机、MATLAB (R2013b)的环境下进行实验，实现本文的改进算法 4)计算新位置的颜色直方图{P.(少)=12.…，m。 GMS跟踪算法，并实现传统MS跟踪算法、Kalman 滤波跟踪算法和粒子滤波跟踪算法与之比较。 5)由式(12)计算新位置和行人目标的相似度 采用4组视频图像序列进行实验，图像序列选 p[p0),9]=∑9.。 自PETS2009和CAVIAR视频图像库，涵盖了行人 6)如果p[p(y),q]<p[p(ya),q],则令y1←- 跟踪的主要场景及挑战场景，包括简单背景、复杂背 2(+y)。 景、目标遮挡、形变及光照变化等。为检测本文方法 的性能，将与传统MS跟踪算法、Kalman滤波跟踪算 7)若‖y1-yo‖<8，则本轮迭代结束；否则 法和粒子滤波跟踪算法进行比较分析。 y。←一y,返回1)继续迭代更新行人目标位置。 3.1与传统MS跟踪的比较 输出当前帧行人目标区域实时最优位置。 图3选取的视频图像是S2_Ll项目中View- 2.2算法计算复杂度 005中的部分序列，序列中红衣女子从视频窗口右 GMS算法的跟踪迭代框架基本维持MS算法的 端水平穿过走向视频窗口左端，期间活动窗口只有 跟踪框架，因此GMS算法和MS算法的计算代价主 红衣女子一人，跟踪图像背景较简单。其中图3(a) 要区别在每次迭代的计算代价，表现在颜色直方图 是MS的跟踪结果，图3(b)是GMS的跟踪结果。从 p、新位置y,和相似度p的计算代价上，MS算法中 跟踪结果可发现该序列MS和GMS的跟踪效果都 表示为Cg、C,、C。,GMS算法中表示为Cg、C',、 较好，在整个行人跟踪过程中都有正确跟踪到目标 C'。,如表1。 行人，但是观察表2发现该序列MS算法的平均迭ｐｕ（ｙ０ ） ＝ Ｃ∑ ｎＲ Ｉ ｉ ＝ １ Ｋ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ δ ｆＣ（ｆ Ｉ（Ｌ ＲＩ [ ｉ ）） － ｕ] （１１） 基于巴氏系数，求得目标区域的参考颜色直方图 ｑ 和目标候选区域的颜色直方图 ｐ（ｙ０ ） 的相似度为 ρ［ｐ（ｙ０ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ０ ）ｑｕ （１２） 至此，粒化的 ＭＳ 行人跟踪算法的 ＭＳ 跟踪迭代 步骤可以总结为算法 １。 算法 １ 粒 化 的 Ｍｅａｎ Ｓｈｉｆｔ 行 人 跟 踪 算 法 （ＧＭＳ） 输入 行人跟踪视频图像序列。 初始化 图像粒度 ＲＩ ＝ ３ 和颜色通道粒度 Ｒ Ｒ Ｃ ＝５， Ｒ Ｇ Ｃ ＝ ６， Ｒ Ｂ Ｃ ＝ ３；给定行人目标初始中心位置 ｙ０ 及行人目标区域核半径 ｈ ，由式（９）得到行人目 标区域经过粒化后的参考颜色直方图 ｑ 。 跟踪过程 １）以 ｙ０ 为行人目标初始中心位置，分别由式 （ １１ ） 和 式 （ １２ ） 计 算 ｛ｐｕ（ｙ０ ）｝ｕ ＝ １，２，…，ｍＲ Ｃ 和 ρ［ｐ（ｙ０ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ０ ）ｑｕ 。 ２）计算权值 ｗｉ { } ｉ ＝ １，２，…，ｎＲ Ｉ 。 ｗｉ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ δ ｆＣ（ｆ Ｉ（Ｌ ＲＩ [ ｉ ）） － ｕ] ｑｕ ｐｕ（ｙ０ ） ３）计算行人目标新位置 ｙ１ ： ｙ１ ＝ ∑ ｎＲ Ｉ ｉ ＝ １ ｘ ∗ ｉ ｗｉｇ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ ∑ ｎＲ Ｉ ｉ ＝ １ ｇ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ ４）计算新位置的颜色直方图 ｛ｐｕ（ｙ１ ）｝ｕ ＝ １，２，…，ｍＲ Ｃ 。 ５）由式（１２）计算新位置和行人目标的相似度 ρ［ｐ（ｙ１ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ１ ）ｑｕ 。 ６）如果 ρ［ｐ（ｙ１ ），ｑ］ ＜ ρ［ｐ（ｙ０ ），ｑ］ ，则令 ｙ１ ← １ ２ （ｙ０ ＋ ｙ１ ）。 ７）若 ‖ｙ１ － ｙ０‖ ＜ ε ，则本轮迭代结束；否则 ｙ０ ← ｙ１ 返回 １）继续迭代更新行人目标位置。 输出 当前帧行人目标区域实时最优位置。 ２．２ 算法计算复杂度 ＧＭＳ 算法的跟踪迭代框架基本维持 ＭＳ 算法的 跟踪框架，因此 ＧＭＳ 算法和 ＭＳ 算法的计算代价主 要区别在每次迭代的计算代价，表现在颜色直方图 ｐ 、新位置 ｙ１ 和相似度 ρ 的计算代价上，ＭＳ 算法中 表示为 ＣＨ 、 Ｃｙ 、 Ｃρ ，ＧＭＳ 算法中表示为 Ｃ′Ｈ 、 Ｃ′ｙ 、 Ｃ′ρ ，如表 １。 表 １ ＭＳ 和 ＧＭＳ 的运算代价 Ｔａｂｌｅ １ Ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｃｏｓｔ ｏｆ ＭＳ ａｎｄ ＧＣＭＳ 代价 ＭＳ ＧＭＳ 直方图 ＣＨ ＝ ＲＣｗ ＋ Ｒ（Ｃｐ ＋ ３Ｃｍ ＋ Ｃａ ） Ｃ′Ｈ ＝ Ｒ′Ｃｗ ＋ Ｒ′（Ｃｐ ＋ ３Ｃｒ ＋ Ｃａ ） 新位置 Ｃｙ ＝ ｕ（Ｃｗ ＋ Ｃｄ ） ＋ Ｒ（３Ｃｍ ＋ Ｃａ ） Ｃ′ｙ ＝ ｕ′（Ｃｗ ＋ Ｃｄ ） ＋ Ｒ′（３Ｃｍ ＋ Ｃａ ） 相似度 Ｃρ ＝ ｕ（Ｃｓ ＋ Ｃｍ ＋ Ｃａ ） Ｃ′ρ ＝ ｕ′（Ｃｓ ＋ Ｃｍ ＋ Ｃａ ） 表中 Ｃｗ 、 Ｃｐ 、 Ｃｍ 、 Ｃａ 、 Ｃｒ 、 Ｃｄ 、 Ｃｓ 分别表示 核函数加权、获取像素值、浮点数乘法、加法、移位运 算、除法运算和开方的计算代价； Ｒ 、 ｕ 分别表示 ＭＳ 算法中的行人目标区域大小及颜色直方图的级数； Ｒ′ 、 ｕ′ 分别表示 ＧＭＳ 算法中的行人目标区域大小 及颜色直方图的级数；满足近似关系 Ｒ ／ Ｒ′ ＝ ４， ｕ ／ ｕ′ ≈５， Ｃｍ 和 Ｃｒ 的关系无法准确比较，但是 Ｃｍ ≻ Ｃｒ 一定成立。 至此可近似估计出 ＭＳ 和 ＧＭＳ 的每 次迭代的计算代价关系，为式（ １３）。 理论计算得 出，仅考虑各运算代价时，ＧＭＳ 算法比 ＭＳ 算法的计 算代价至少快 ４ 倍，是个可观的结果。 在实际实验 中，由于图像分块函数消耗、硬件等原因会使得真正 计算效率低于 ４ 倍。 ＣＨ ＋ Ｃｙ ＋ Ｃρ Ｃ′Ｈ ＋ Ｃ′ｙ ＋ Ｃ′ρ ≈ ４ （１３） ３ 实验结果与分析 在 ＣＰＵ２．６ ＧＨｚ、内存 ４ ＧＢ 的 ＰＣ 机、ＭＡＴＬＡＢ （Ｒ２０１３ｂ）的环境下进行实验，实现本文的改进算法 ＧＭＳ 跟踪算法，并实现传统 ＭＳ 跟踪算法、Ｋａｌｍａｎ 滤波跟踪算法和粒子滤波跟踪算法与之比较。 采用 ４ 组视频图像序列进行实验，图像序列选 自 ＰＥＴＳ２００９ 和 ＣＡＶＩＡＲ 视频图像库，涵盖了行人 跟踪的主要场景及挑战场景，包括简单背景、复杂背 景、目标遮挡、形变及光照变化等。 为检测本文方法 的性能，将与传统 ＭＳ 跟踪算法、Ｋａｌｍａｎ 滤波跟踪算 法和粒子滤波跟踪算法进行比较分析。 ３．１ 与传统 ＭＳ 跟踪的比较 图 ３ 选取的视频图像是 Ｓ２＿Ｌ１ 项目中 Ｖｉｅｗ＿ ００５ 中的部分序列，序列中红衣女子从视频窗口右 端水平穿过走向视频窗口左端，期间活动窗口只有 红衣女子一人，跟踪图像背景较简单。 其中图 ３（ａ） 是 ＭＳ 的跟踪结果，图 ３（ｂ）是 ＧＭＳ 的跟踪结果。 从 跟踪结果可发现该序列 ＭＳ 和 ＧＭＳ 的跟踪效果都 较好，在整个行人跟踪过程中都有正确跟踪到目标 行人，但是观察表 ２ 发现该序列 ＭＳ 算法的平均迭 第 ４ 期 刘翠君，等：粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法 ·４３７·