第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992/is.201605033 网络出版地址：http://www.cnki.net/kcms/detail,/23.1538.TP.20160808.0831.022.html 粒化的Mean Shift行人跟踪算法 刘翠君，赵才荣，苗夺谦，王学宽 (同济大学电子与信息工程学院，上海201804) 摘要：Mean Shift行人跟踪采用颜色特征直方图作为跟踪特征，存在易受背景颜色干扰等问题。基于此，在传统的 Mean Shift行人跟踪算法中引入粒计算的思想，提出粒化的Mean Shift行人跟踪算法，对图像目标区域作粒层分块来 提取块颜色特征信息，并在颜色特征表示上作不同粒度的粒化，最后在Mean Shift迭代框架下实现行人跟踪。该方 法相比传统的跟踪方法具有计算复杂度更低、稳健性更好的优点。在PETS20O9和CAVIAR数据库做的实验表明， 这种方法跟踪正确率更高，在颜色干扰下稳健性更好，能够实时有效地跟踪行人。 关键词：信息粒：粒计算：Mean Shift:特征提取：行人跟踪 中图分类号：TP391文献标志码：A文章编号：1673-4785(2016)04-0433-09 中文引用格式：刘翠君，赵才荣，苗夺谦，等.粒化的Mean Shif价行人跟踪算法[J].智能系统学报，2016,11(4)：433-441. 英文引用格式：LIUCuijun,ZHAO Cairong,MIAO Duoqian,etal.Granular mean shift pedestrian tracking algorithm[J].CAAl Transactions on Intelligent Systems,2016,11(4):433-441. Granular mean shift pedestrian tracking algorithm LIU Cuijun,ZHAO Cairong,MIAO Duoqian,WANG Xuekuan (College of Electronics and Information Engineering,Tongji University,Shanghai 201804,China) Abstract:Mean shift pedestrian tracking that uses a color histogram as its tracking feature has drawbacks,e.g., performance can easily be affected by the introduction of a background color.To solve this problem,the idea of granular computing was introduced into the traditional mean shift pedestrian tracking algorithm,and a new granular mean shift pedestrian tracking algorithm,based on granular computing,is presented.The algorithm blocks the im- age's target area with specific granularity to extract color features,then adopts different color channels of granula- tion on the feature,and finally realizes target tracking under the framework of the mean shift iteration.Compared with other traditional methods the algorithm displays lower computational complexity and is more robust.Experimen- tal results on PETS2009 and CAVIAR databases show that the algorithm achieves a higher tracking accuracy,better robustness and efficiency under color interference,and can track the target pedestrian in real time. Keywords:information granules;granular computing;mean shift;feature extraction;pedestrian tracking 行人跟踪涉及行人检测和行人跟踪两部分。行标匹配和目标定位。行人跟踪算法分属两大类：确 人检测属于运动目标检测，目的是从图像序列中将 定性跟踪和随机跟踪。确定性跟踪以Mean Shift 行人目标从背景图像中提取出来：行人跟踪则是在 (MS)跟踪为主线，是以相似度度量作为代价函数的 视频图像序列中检测定位出行人，包括目标建模、目 优化问题，有一系列基于MS的跟踪算法[2-)：随机 跟踪将视觉跟踪转化为贝叶斯理论框架下的状态估 收稿日期：2016-05-30.，网络出版日期：2016-08-08. 计问题，目前典型的随机跟踪算法有Kalman滤波跟 基金项目：国家自然科学基金项目(61273304)：上海市中医药三年行动 计划重点项目(ZY3-CCCX-3-6002) 踪[o和粒子滤波跟踪)。以MS为代表的行人跟 通信作者：苗夺谦.E-mail:dqmiao(@tongji.cdu.cm. 踪算法因其简单稳健的优势而广受研究者青睐。文
第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０５０３３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３１．０２２．ｈｔｍｌ 粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法 刘翠君，赵才荣，苗夺谦，王学宽 （同济大学 电子与信息工程学院，上海 ２０１８０４） 摘 要：Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪采用颜色特征直方图作为跟踪特征，存在易受背景颜色干扰等问题。 基于此，在传统的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法中引入粒计算的思想，提出粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法，对图像目标区域作粒层分块来 提取块颜色特征信息，并在颜色特征表示上作不同粒度的粒化，最后在 Ｍｅａｎ Ｓｈｉｆｔ 迭代框架下实现行人跟踪。 该方 法相比传统的跟踪方法具有计算复杂度更低、稳健性更好的优点。 在 ＰＥＴＳ２００９ 和 ＣＡＶＩＡＲ 数据库做的实验表明， 这种方法跟踪正确率更高，在颜色干扰下稳健性更好，能够实时有效地跟踪行人。 关键词：信息粒；粒计算；Ｍｅａｎ Ｓｈｉｆｔ；特征提取；行人跟踪 中图分类号： ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０４３３－０９ 中文引用格式：刘翠君，赵才荣，苗夺谦，等． 粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ４３３－４４１． 英文引用格式：ＬＩＵ Ｃｕｉｊｕｎ， ＺＨＡＯ Ｃａｉｒｏｎｇ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ｅｔ ａｌ． Ｇｒａｎｕｌａｒ ｍｅａｎ ｓｈｉｆｔ ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ４３３－４４１． Ｇｒａｎｕｌａｒ ｍｅａｎ ｓｈｉｆｔ ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ ＬＩＵ Ｃｕｉｊｕｎ， ＺＨＡＯ Ｃａｉｒｏｎｇ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＷＡＮＧ Ｘｕｅｋｕａｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈａｎｇｈａｉ ２０１８０４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｍｅａｎ ｓｈｉｆｔ ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ ｔｈａｔ ｕｓｅｓ ａ ｃｏｌｏｒ ｈｉｓｔｏｇｒａｍ ａｓ ｉｔｓ ｔｒａｃｋｉｎｇ ｆｅａｔｕｒｅ ｈａｓ ｄｒａｗｂａｃｋｓ， ｅ． ｇ．， ｐｅｒｆｏｒｍａｎｃｅ ｃａｎ ｅａｓｉｌｙ ｂｅ ａｆｆｅｃｔｅｄ ｂｙ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ａ ｂａｃｋｇｒｏｕｎｄ ｃｏｌｏｒ． Ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ， ｔｈｅ ｉｄｅａ ｏｆ ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ ｗａｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｍｅａｎ ｓｈｉｆｔ ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ， ａｎｄ ａ ｎｅｗ ｇｒａｎｕｌａｒ ｍｅａｎ ｓｈｉｆｔ ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ， ｂａｓｅｄ ｏｎ ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ， ｉｓ ｐｒｅｓｅｎｔｅｄ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂｌｏｃｋｓ ｔｈｅ ｉｍ⁃ ａｇｅ’ｓ ｔａｒｇｅｔ ａｒｅａ ｗｉｔｈ ｓｐｅｃｉｆｉｃ ｇｒａｎｕｌａｒｉｔｙ ｔｏ ｅｘｔｒａｃｔ ｃｏｌｏｒ ｆｅａｔｕｒｅｓ， ｔｈｅｎ ａｄｏｐｔｓ ｄｉｆｆｅｒｅｎｔ ｃｏｌｏｒ ｃｈａｎｎｅｌｓ ｏｆ ｇｒａｎｕｌａ⁃ ｔｉｏｎ ｏｎ ｔｈｅ ｆｅａｔｕｒｅ， ａｎｄ ｆｉｎａｌｌｙ ｒｅａｌｉｚｅｓ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ｕｎｄｅｒ ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ ｔｈｅ ｍｅａｎ ｓｈｉｆｔ ｉｔｅｒａｔｉｏｎ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｏｔｈｅｒ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｄｉｓｐｌａｙｓ ｌｏｗｅｒ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｉｓ ｍｏｒｅ ｒｏｂｕｓｔ． Ｅｘｐｅｒｉｍｅｎ⁃ ｔａｌ ｒｅｓｕｌｔｓ ｏｎ ＰＥＴＳ２００９ ａｎｄ ＣＡＶＩＡＲ ｄａｔａｂａｓｅｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｃｈｉｅｖｅｓ ａ ｈｉｇｈｅｒ ｔｒａｃｋｉｎｇ ａｃｃｕｒａｃｙ， ｂｅｔｔｅｒ ｒｏｂｕｓｔｎｅｓｓ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｕｎｄｅｒ ｃｏｌｏｒ ｉｎｔｅｒｆｅｒｅｎｃｅ， ａｎｄ ｃａｎ ｔｒａｃｋ ｔｈｅ ｔａｒｇｅｔ ｐｅｄｅｓｔｒｉａｎ ｉｎ ｒｅａｌ ｔｉｍｅ． Ｋｅｙｗｏｒｄｓ： ｉｎｆｏｒｍａｔｉｏｎ ｇｒａｎｕｌｅｓ； ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ； ｍｅａｎ ｓｈｉｆｔ； ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ； ｐｅｄｅｓｔｒｉａｎ ｔｒａｃｋｉｎｇ 收稿日期：２０１６－０５－３０． 网络出版日期：２０１６－０８－０８． 基金项目：国家自然科学基金项目（６１２７３３０４）；上海市中医药三年行动 计划重点项目（ＺＹ３⁃ＣＣＣＸ⁃３⁃６００２） 通信作者：苗夺谦． Ｅ⁃ｍａｉｌ：ｄｑｍｉａｏ＠ ｔｏｎｇｊｉ．ｅｄｕ．ｃｎ． 行人跟踪涉及行人检测和行人跟踪两部分。 行 人检测属于运动目标检测，目的是从图像序列中将 行人目标从背景图像中提取出来；行人跟踪则是在 视频图像序列中检测定位出行人，包括目标建模、目 标匹配和目标定位。 行人跟踪算法分属两大类：确 定性跟踪和随机跟踪。 确定性跟踪以 Ｍｅａｎ Ｓｈｉｆｔ （ＭＳ）跟踪为主线，是以相似度度量作为代价函数的 优化问题，有一系列基于 ＭＳ 的跟踪算法［２－９］ ；随机 跟踪将视觉跟踪转化为贝叶斯理论框架下的状态估 计问题，目前典型的随机跟踪算法有 Ｋａｌｍａｎ 滤波跟 踪［１０］和粒子滤波跟踪［１１］ 。 以 ＭＳ 为代表的行人跟 踪算法因其简单稳健的优势而广受研究者青睐。 文
.434 智能系统学报 第11卷 献[1]对MS跟踪算法的经典文献和研究历程做了 本文提出粒化的MS行人跟踪算法，基本保留 详细综述。2003年D.Comaniciu等2]将MS应用于 MS跟踪算法框架，引入粒计算方法来优化颜色特 视觉跟踪领域，首次提出MS跟踪算法，开辟了视觉 征表示，在颜色特征的采集和处理上都采用粒计算 跟踪领域的新方向，自此有大量关于MS的改进算 方法表示，得到粒化后的核函数加权颜色直方图作 法被提出。为提高MS跟踪算法的适应能力，在目 为颜色特征表示，通过MS迭代实现行人跟踪，一定 标模板更新策略上，文献[3]提出基于线性加权的 程度上削弱了图像噪声干扰，不仅降低了计算代价， 模板更新：文献[4]提出基于滤波的模板更新方法： 而且提高了跟踪实时性。 在目标尺度及方向估计上，文献[5]提出基于特征 1颜色特征粒化 点匹配的尺度与方向估计方法，消除由于尺度变化 导致的定位误差：文献[6]提出基于权重图的尺度 将大量的复杂特征及信息按其各自的特征及性 与方向估计方法，能更准确地反应目标尺度信息：在 能划分为若干个较简单的块，每一块看作是一个信 抗遮挡跟踪上，文献[7]在MS跟踪算法的基础上引 息粒，这些信息粒具有相似的特征及性能，这个划分 入Kalman滤波器来辅助预测目标位置，增强了稳健 过程就是信息粒化的过程。 性：文献[8]提出目标分块的方法，通过子块的跟踪 定义1用一个三元组来描述信息粒G=(IG, 定位来获得目标的整体位置：在跟踪快速目标上， EG,FG),其中IG称为信息粒G的内涵，EG称为信息 MS迭代容易陷入局部最优值，使得无法处理快速 粒G的外延：FG称为内涵和外延之间的转换函数。 运动的目标，文献[9]引入模拟退火算法，提出退火 信息粒的内涵IG是信息粒在特定环境下的表 MS来逐步平滑代价函数，用于全局模式的搜索，跳 现知识，表示在一个特定的任务下信息粒中所有元 出局部最优值。 素的一般性特征、规则、共同性等，可以定义一个语 MS跟踪向来以计算简单、调节参数少为优势， 言，由这个语言的公式来表示：信息粒的外延EG是 这些改进算法尽管从不同方面改进了MS跟踪算法 满足这个公式的所有对象的集合：信息粒的转换函 的缺陷，但是也一定程度上增加了计算复杂度和调 数FG是EG到IG的泛化转换函数。对于信息粒 节参数，无法很好地保证跟踪实时性。MS跟踪存在 G=(IG,EG,FG),X为对于信息粒G所有可能外 的挑战问题有许多，本文旨在基本保留MS的跟踪 延EG的对象的集合，即外延的论域：Y为对于信息 框架上解决MS跟踪的基本问题：颜色直方图带来 粒G所有可能内涵IG的集合，即内涵的论域。下面 的干扰问题和计算复杂度问题。考虑到颜色直方图 给出转换函数FG的形式化定义。 对于目标形状、姿态、旋转等变化及遮挡都具有一定 定义2从X到Y的信息粒的泛化转换函数是 的鲁棒性，但是由于摄像机的视频图像质量普遍较 笛卡尔积X×Y的一个子集FG,对于每个属于X的 差，分辨率普遍较低，易受背景颜色干扰，使得采集 EG都存在唯一的Y中的元素IG使得(EG,IG)属 到的目标颜色特征存在较大的噪声冗余信息，然而 于FG。 粒计算方法恰巧能有效地处理视频图像大数据冗余 传统的MS行人跟踪算法采集行人目标区域的 信息。 颜色特征信息，粒化的MS行人跟踪算法引入粒计 粒计算方法由Zadeh2]和Lin1)首次提出，是 算的思想对颜色特征信息进行粒化，包含两个信息 人工智能领域中的一种新理念和新方法，它覆盖了 粒化过程：图像粒化和颜色通道粒化。 所有和粒度相关的理论、方法和技术，主要用于对不 1.1图像粒化 确定、不精确、不完整信息的处理，对大规模海量数 行人目标区域存在背景颜色干扰，为了减弱背 据的挖掘和对复杂问题的求解4。粒计算的实质 景颜色干扰和降低计算代价，将图像行人目标区域 是通过选择合适的粒度，来寻找一种较好的、近似的 进行不同粒度的粒层分块，并采集每一粒块的R、G、 解决方案，避免复杂的计算，从而降低问题求解的难 B颜色均值，得到图像特征信息粒格，简称图像粒， 度。文献[15]归纳了粒计算方法在大数据处理中 该过程为图像粒化。用三元组G=(IG,EG,FG) 的3种基本模式并讨论了粒计算方法应用于大数据 表示图像粒，内涵IG是由外延EG集合中的每个 的可行性及优势。考虑到摄像机视频图像中的海量 对象通过转换关系FG计算出的R、G、B颜色均值 数据挖掘和行人跟踪问题的复杂计算，试图通过粒 集合。外延EG的论域X'={【M×N】M,N∈ 计算方法找到降低计算代价并有效改进跟踪效果的 N{,其中【M×N】表示大小为M×N的图像粒块， 方法。 L∈X,i=1,2,…,n,表示图像粒度为R,时的第
献［１］对 ＭＳ 跟踪算法的经典文献和研究历程做了 详细综述。 ２００３ 年 Ｄ．Ｃｏｍａｎｉｃｉｕ 等［２］ 将 ＭＳ 应用于 视觉跟踪领域，首次提出 ＭＳ 跟踪算法，开辟了视觉 跟踪领域的新方向，自此有大量关于 ＭＳ 的改进算 法被提出。 为提高 ＭＳ 跟踪算法的适应能力，在目 标模板更新策略上，文献［３］提出基于线性加权的 模板更新；文献［４］提出基于滤波的模板更新方法； 在目标尺度及方向估计上，文献［５］提出基于特征 点匹配的尺度与方向估计方法，消除由于尺度变化 导致的定位误差；文献［６］提出基于权重图的尺度 与方向估计方法，能更准确地反应目标尺度信息；在 抗遮挡跟踪上，文献［７］在 ＭＳ 跟踪算法的基础上引 入 Ｋａｌｍａｎ 滤波器来辅助预测目标位置，增强了稳健 性；文献［８］提出目标分块的方法，通过子块的跟踪 定位来获得目标的整体位置；在跟踪快速目标上， ＭＳ 迭代容易陷入局部最优值，使得无法处理快速 运动的目标，文献［９］引入模拟退火算法，提出退火 ＭＳ 来逐步平滑代价函数，用于全局模式的搜索，跳 出局部最优值。 ＭＳ 跟踪向来以计算简单、调节参数少为优势， 这些改进算法尽管从不同方面改进了 ＭＳ 跟踪算法 的缺陷，但是也一定程度上增加了计算复杂度和调 节参数，无法很好地保证跟踪实时性。 ＭＳ 跟踪存在 的挑战问题有许多，本文旨在基本保留 ＭＳ 的跟踪 框架上解决 ＭＳ 跟踪的基本问题：颜色直方图带来 的干扰问题和计算复杂度问题。 考虑到颜色直方图 对于目标形状、姿态、旋转等变化及遮挡都具有一定 的鲁棒性，但是由于摄像机的视频图像质量普遍较 差，分辨率普遍较低，易受背景颜色干扰，使得采集 到的目标颜色特征存在较大的噪声冗余信息，然而 粒计算方法恰巧能有效地处理视频图像大数据冗余 信息。 粒计算方法由 Ｚａｄｅｈ ［１２］ 和 Ｌｉｎ ［１３］ 首次提出，是 人工智能领域中的一种新理念和新方法，它覆盖了 所有和粒度相关的理论、方法和技术，主要用于对不 确定、不精确、不完整信息的处理，对大规模海量数 据的挖掘和对复杂问题的求解［１４］ 。 粒计算的实质 是通过选择合适的粒度，来寻找一种较好的、近似的 解决方案，避免复杂的计算，从而降低问题求解的难 度。 文献［１５］归纳了粒计算方法在大数据处理中 的 ３ 种基本模式并讨论了粒计算方法应用于大数据 的可行性及优势。 考虑到摄像机视频图像中的海量 数据挖掘和行人跟踪问题的复杂计算，试图通过粒 计算方法找到降低计算代价并有效改进跟踪效果的 方法。 本文提出粒化的 ＭＳ 行人跟踪算法，基本保留 ＭＳ 跟踪算法框架，引入粒计算方法来优化颜色特 征表示，在颜色特征的采集和处理上都采用粒计算 方法表示，得到粒化后的核函数加权颜色直方图作 为颜色特征表示，通过 ＭＳ 迭代实现行人跟踪，一定 程度上削弱了图像噪声干扰，不仅降低了计算代价， 而且提高了跟踪实时性。 １ 颜色特征粒化 将大量的复杂特征及信息按其各自的特征及性 能划分为若干个较简单的块，每一块看作是一个信 息粒，这些信息粒具有相似的特征及性能，这个划分 过程就是信息粒化的过程。 定义 １ 用一个三元组来描述信息粒 Ｇ ＝ （ＩＧ， ＥＧ，ＦＧ） ，其中 ＩＧ 称为信息粒 Ｇ 的内涵， ＥＧ 称为信息 粒 Ｇ 的外延； ＦＧ 称为内涵和外延之间的转换函数。 信息粒的内涵 ＩＧ 是信息粒在特定环境下的表 现知识，表示在一个特定的任务下信息粒中所有元 素的一般性特征、规则、共同性等，可以定义一个语 言，由这个语言的公式来表示；信息粒的外延 ＥＧ 是 满足这个公式的所有对象的集合；信息粒的转换函 数 ＦＧ 是 ＥＧ 到 ＩＧ 的泛化转换函数。 对于信息粒 Ｇ ＝（ＩＧ，ＥＧ，ＦＧ） ， Ｘ 为对于信息粒 Ｇ 所有可能外 延 ＥＧ 的对象的集合，即外延的论域； Ｙ 为对于信息 粒 Ｇ 所有可能内涵 ＩＧ 的集合，即内涵的论域。 下面 给出转换函数 ＦＧ 的形式化定义。 定义 ２ 从 Ｘ 到 Ｙ 的信息粒的泛化转换函数是 笛卡尔积 Ｘ × Ｙ 的一个子集 ＦＧ ，对于每个属于 Ｘ 的 ＥＧ 都存在唯一的 Ｙ 中的元素 ＩＧ 使得 （ＥＧ，ＩＧ） 属 于 ＦＧ 。 传统的 ＭＳ 行人跟踪算法采集行人目标区域的 颜色特征信息，粒化的 ＭＳ 行人跟踪算法引入粒计 算的思想对颜色特征信息进行粒化，包含两个信息 粒化过程：图像粒化和颜色通道粒化。 １．１ 图像粒化 行人目标区域存在背景颜色干扰，为了减弱背 景颜色干扰和降低计算代价，将图像行人目标区域 进行不同粒度的粒层分块，并采集每一粒块的 Ｒ、Ｇ、 Ｂ 颜色均值，得到图像特征信息粒格，简称图像粒， 该过程为图像粒化。 用三元组 Ｇ Ｉ ＝ （ＩＧ Ｉ ，ＥＧ Ｉ ，ＦＧ Ｉ ） 表示图像粒，内涵 ＩＧ Ｉ 是由外延 ＥＧ Ｉ 集合中的每个 对象通过转换关系 ＦＧ Ｉ 计算出的 Ｒ、Ｇ、Ｂ 颜色均值 集合。 外延 ＥＧ Ｉ 的论域 Ｘ Ｉ ＝ ｛〖Ｍ × Ｎ〗 Ｍ，Ｎ ∈ ℕ ｝， 其中 〖Ｍ × Ｎ〗 表示大小为 Ｍ × Ｎ 的图像粒块， Ｌ ＲＩ ｉ ∈ Ｘ Ｉ ，ｉ ＝ １，２，…，ｎＲＩ ，表示图像粒度为 ＲＩ 时的第 ·４３４· 智 能 系 统 学 报 第 １１ 卷
第4期 刘翠君，等：粒化的Mean Shift行人跟踪算法 ·435. i个图像粒块，其中R,={1,2,…}表示图像粒层分 块，同时更新外延集合和内涵集合：依此类推，当图 块的粒度。相同粒度下的图像粒块大小一致，令原 像粒度R,=5时，粒化为n个1×1大小的粒块，已 始图像块大小为m×n,图像粒度为R,时的图像粒 经达到像素点级，粒化过程结束。实验表明图像粒 块L的大小为m×n:,ne表示粒度为R,时的图 度R,=4时，实验效果较好。 像粒块总数，有 1.2颜色通道粒化 nR=Lm×n/m×n」j (1) 行人跟踪的视频图像往往分辨率较低，存在一 内涵IG的论域Y={(CR,Cc,Cg)|CR,Cc, 定程度的颜色噪声干扰。颜色级数越多，表示的颜 CB∈(0,255)}，其中(CR,Cc,Cg）为R、G、B三通 色信息就越多，但是相应的颜色干扰信息也越多，且 道的颜色特征向量，C∈'，i=1,2,…,nR,表示图 运算代价也越大，通过颜色特征计算相似性度量参 像粒度为R,时第i个图像粒块的颜色特征均值。转 数（巴氏系数）的速度也越慢，这对行人跟踪需要高 换函数FG:X'→Y定义为 实时性的要求具有很大挑战，因此不利于实时的行 ∑(CR,Cc,Cs） 人跟踪。粒计算的思想能有效地对这种不确定的模 fIM×NI)= 糊信息进行简化处理，因此在颜色特征表示上引入 (2) M×N 粒计算的思想：行人目标区域经过图像粒化和转换 转换函数对外延集合中的每个图像粒块求R、 函数处理后得到行人目标区域的颜色特征矩阵，对 G、B三通道的颜色特征均值，得到图像粒的内涵集 颜色特征矩阵做颜色通道粒化处理得到最终粒化后 合，外延集合中的粒块对象和内涵集合中颜色特征 的颜色特征矩阵。 向量对象一一对应，内涵集合中的所有颜色特征向 分别将R、G、B三通道颜色区间进行不同粒度 量对象构成该图像目标区域的颜色特征矩阵。 的量化，每通道的颜色区间都均匀二分，得到一系列 图1为粒化的MS行人跟踪算法的图像粒化过 均匀的子颜色区间，称为颜色区间信息粒格，简称颜 程示意图。 色粒，该过程为颜色通道粒化。用三元组G= (IGC,EGC,FGC)来表示颜色粒，内涵IGC是由外延 EG集合中的每个颜色区间通过转换关系FGC计算 出的R、G、B颜色量值集合。外延EG的论域为 Xc={[a,b],0≤a,b≤255，a,b∈N},Lc∈Xc, i=1,2,…,ngc表示颜色粒度为Rc时第i个颜色粒 区间，nR,=2c-1表示颜色粒度为Rc时的颜色粒总 数，则颜色粒度为R。时的每一个颜色粒区间长度为 length(Le)=256/ne=28/2c-1=29-c(3) (a)R,=I (b)R=2 (c)R=3 (d)R=4 颜色粒度为Rc时第i个颜色粒区间Lc可表示为 m×n=7m×nm×=8×8m×n=4×4m×81=2×2 [length(Lc)×(i-1),length(Lc)×i],内涵IGc 图1图像粒化过程 的论域∈[0,255]，转换函数FGc可定义为 Fig.1 Image granulation fc(Lc)=i (4) R,为图像粒度，m×n为图像粒度为R,时的 令v表示颜色粒区间Lc的一个颜色值，即v∈ 图像粒块的大小。当图像粒度R,=1时，图像粒块 [length(Lc)×(i-1),length(Lc)×i],则转换函 为行人目标区域m×n,图像粒的外延集合中只有 数可变换为 一个对象，即EG={L=1,i=1},图像粒的内涵集 fc(v)=v/length(Lc)=v.2Rc-9 (5) 合也只有一个图像粒块L1的颜色特征均值，即 至此可直接通过转换函数式(5)计算出颜色特 IG={C=1,i=1};当图像粒度R=2时，考虑到行 征值在任一粒度下粒化后的颜色特征值，较大程度 人目标区域m×n尺度较小且形状倾向于矩形，因 降低计算量。 此将m×n的目标区域首次粒化成8×8的图像粒 考虑到采集的原始颜色特征为R、G、B颜色值， 块，更新外延集合为EG={L=2,i=1,2,…,n2}和 有R通道、G通道和B通道。每个颜色通道对颜色敏 内涵集合为IG={C2,i=1,2,…,n2},其中 感度不一样，如若对每个颜色通道采用一样的粒度来 n2=lm×n/8×8」；当图像粒度R,=3时，对n2个 量化，则不仅没有降低噪声干扰，而且模糊了行人目 8×8大小的图像粒块再粒化成n,个4×4大小的粒 标的颜色特征。因此对每一个颜色通道采用相应的
ｉ 个图像粒块，其中 ＲＩ ＝ ｛１，２，…｝ 表示图像粒层分 块的粒度。 相同粒度下的图像粒块大小一致，令原 始图像块大小为 ｍ × ｎ ，图像粒度为 ＲＩ 时的图像粒 块 Ｌ ＲＩ ｉ 的大小为 ｍ ＲＩ × ｎ ＲＩ ， ｎＲＩ 表示粒度为 ＲＩ 时的图 像粒块总数，有 ｎＲＩ ＝⌊ｍ × ｎ ／ ｍ ＲＩ × ｎ ＲＩ」 （１） 内涵 ＩＧ Ｉ 的论域 Ｙ Ｉ ＝ ｛（ＣＲ ，ＣＧ ，ＣＢ ） ｜ ＣＲ ，ＣＧ ， ＣＢ ∈（０，２５５）｝ ，其中 （ＣＲ ，ＣＧ ，ＣＢ ） 为 Ｒ、Ｇ、Ｂ 三通 道的颜色特征向量， Ｃ ＲＩ ｉ ∈ Ｙ Ｉ ，ｉ ＝ １，２，…，ｎＲＩ 表示图 像粒度为 ＲＩ 时第 ｉ 个图像粒块的颜色特征均值。 转 换函数 ＦＧ Ｉ ：Ｘ Ｉ → Ｙ Ｉ 定义为 ｆ Ｉ（〖Ｍ × Ｎ〗） ＝ 〖 ∑Ｍ×Ｎ〗 （ＣＲ ，ＣＧ ，ＣＢ ） Ｍ × Ｎ （２） 转换函数对外延集合中的每个图像粒块求 Ｒ、 Ｇ、Ｂ 三通道的颜色特征均值，得到图像粒的内涵集 合，外延集合中的粒块对象和内涵集合中颜色特征 向量对象一一对应，内涵集合中的所有颜色特征向 量对象构成该图像目标区域的颜色特征矩阵。 图 １ 为粒化的 ＭＳ 行人跟踪算法的图像粒化过 程示意图。 图 １ 图像粒化过程 Ｆｉｇ．１ Ｉｍａｇｅ ｇｒａｎｕｌａｔｉｏｎ ＲＩ 为图像粒度， ｍ ＲＩ × ｎ ＲＩ 为图像粒度为 ＲＩ 时的 图像粒块的大小。 当图像粒度 ＲＩ ＝ １ 时，图像粒块 为行人目标区域 ｍ × ｎ ，图像粒的外延集合中只有 一个对象，即 ＥＧ Ｉ ＝ ｛Ｌ ＲＩ ＝ １ ｉ ，ｉ ＝ １｝ ，图像粒的内涵集 合也只有一个图像粒块 Ｌ ＲＩ ＝ １ １ 的颜色特征均值，即 ＩＧ Ｉ ＝ ｛Ｃ ＲＩ ＝ １ ｉ ，ｉ ＝ １｝ ；当图像粒度 ＲＩ ＝ ２ 时，考虑到行 人目标区域 ｍ × ｎ 尺度较小且形状倾向于矩形，因 此将 ｍ × ｎ 的目标区域首次粒化成 ８ × ８ 的图像粒 块，更新外延集合为 ＥＧ Ｉ ＝ ｛Ｌ ＲＩ ＝ ２ ｉ ，ｉ ＝ １，２，…，ｎ２ ｝ 和 内涵集合为 ＩＧ Ｉ ＝ ｛Ｃ ＲＩ ＝ ２ ｉ ，ｉ ＝ １，２，…，ｎ２ ｝ ， 其 中 ｎ２ ＝⌊ｍ × ｎ ／ ８ × ８」 ；当图像粒度 ＲＩ ＝ ３ 时，对 ｎ２ 个 ８ × ８ 大小的图像粒块再粒化成 ｎ３ 个 ４ × ４ 大小的粒 块，同时更新外延集合和内涵集合；依此类推，当图 像粒度 ＲＩ ＝ ５ 时，粒化为 ｎ５ 个 １ × １ 大小的粒块，已 经达到像素点级，粒化过程结束。 实验表明图像粒 度 ＲＩ ＝ ４ 时，实验效果较好。 １．２ 颜色通道粒化 行人跟踪的视频图像往往分辨率较低，存在一 定程度的颜色噪声干扰。 颜色级数越多，表示的颜 色信息就越多，但是相应的颜色干扰信息也越多，且 运算代价也越大，通过颜色特征计算相似性度量参 数（巴氏系数）的速度也越慢，这对行人跟踪需要高 实时性的要求具有很大挑战，因此不利于实时的行 人跟踪。 粒计算的思想能有效地对这种不确定的模 糊信息进行简化处理，因此在颜色特征表示上引入 粒计算的思想：行人目标区域经过图像粒化和转换 函数处理后得到行人目标区域的颜色特征矩阵，对 颜色特征矩阵做颜色通道粒化处理得到最终粒化后 的颜色特征矩阵。 分别将 Ｒ、Ｇ、Ｂ 三通道颜色区间进行不同粒度 的量化，每通道的颜色区间都均匀二分，得到一系列 均匀的子颜色区间，称为颜色区间信息粒格，简称颜 色粒， 该过程为颜色通道粒化。 用三元组 Ｇ Ｃ ＝ （ＩＧ Ｃ ，ＥＧ Ｃ ，ＦＧ Ｃ ） 来表示颜色粒，内涵 ＩＧ Ｃ 是由外延 ＥＧ Ｃ 集合中的每个颜色区间通过转换关系 ＦＧ Ｃ 计算 出的 Ｒ、Ｇ、Ｂ 颜色量值集合。 外延 ＥＧ Ｃ 的论域为 Ｘ Ｃ ＝｛［ａ，ｂ］，０ ≤ ａ，ｂ ≤２５５，ａ，ｂ ∈ ℕ ｝ ， Ｌ ＲＣ ｉ ∈ Ｘ Ｃ ， ｉ ＝ １，２，…，ｎＲＣ 表示颜色粒度为 ＲＣ 时第 ｉ 个颜色粒 区间， ｎＲＣ ＝ ２ ＲＣ －１ 表示颜色粒度为 ＲＣ 时的颜色粒总 数，则颜色粒度为 ＲＣ 时的每一个颜色粒区间长度为 ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） ＝ ２５６ ／ ｎＲＣ ＝ ２ ８ ／ ２ ＲＣ －１ ＝ ２ ９－ＲＣ （３） 颜色粒度为 ＲＣ 时第 ｉ 个颜色粒区间 Ｌ ＲＣ ｉ 可表示为 ［ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） × （ｉ － １），ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） × ｉ］ ，内涵 ＩＧ Ｃ 的论域 Ｙ Ｃ ∈ ［０，２５５］ ，转换函数 ＦＧ Ｃ 可定义为 ｆＣ（Ｌ ＲＣ ｉ ） ＝ ｉ （４） 令 ｖ 表示颜色粒区间 Ｌ ＲＣ ｉ 的一个颜色值，即 ｖ ∈ ［ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） × （ｉ － １），ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） × ｉ］ ，则转换函 数可变换为 ｆＣ（ｖ） ＝ ｖ／ ｌｅｎｇｔｈ（Ｌ ＲＣ ｉ ） ＝ ｖ·２ ＲＣ －９ （５） 至此可直接通过转换函数式（５）计算出颜色特 征值在任一粒度下粒化后的颜色特征值，较大程度 降低计算量。 考虑到采集的原始颜色特征为 Ｒ、Ｇ、Ｂ 颜色值， 有 Ｒ 通道、 Ｇ 通道和 Ｂ 通道。 每个颜色通道对颜色敏 感度不一样，如若对每个颜色通道采用一样的粒度来 量化，则不仅没有降低噪声干扰，而且模糊了行人目 标的颜色特征。 因此对每一个颜色通道采用相应的 第 ４ 期 刘翠君，等：粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法 ·４３５·
.436 智能系统学报 第11卷 粒度来量化，经验得出G通道最敏感，R通道次之，B 比较两图，可看到粒化后的颜色直方图在颜色 通道敏感度最低。因此G通道要表现更多的颜色特 级数上降低了大约5倍，曲线与横轴所围成的面积 征信息，颜色粒度则赋予最大：而敏感度相对最弱的 是采集的目标区域的像素点数量，可见粒化后的像 B通道表现最少的颜色特征信息，颜色粒度则赋予最 素点数量大约降低了4倍，大大降低了计算量。这 小。令R、G、B通道的量化粒度分别表示为R、、 一点将在后续的实验中得到进一步的验证。 R,经验得出当R=5、R=6、R=3时表现的颜色 特征信息最为有效，行人跟踪效果较好。 2粒化的Mean Shift行人跟踪算法 计算经过颜色通道粒化后的3个颜色通道的直 粒化的Mean Shift行人跟踪算法(GMS)是利用 方图虽然已经降低了一定的计算代价和存储代价， 图像粒化及颜色通道粒化后的核函数空间加权的颜 但是为了更进一步简化计算量和降低存储代价，将 色直方图作为目标模型，采用巴氏系数作为相似度 颜色粒化后的三通道颜色值整合成一维颜色值作为 度量，通过自适应步长的MS迭代来实时跟踪行人 该颜色粒的颜色特征值，由于颜色的权重信息已经 目标的位置。 在颜色粒化的时候通过颜色粒度表现，因此整体的 2.1算法描述 转换函数f代)直接体现为各颜色通道的转换函数 设{L,i=1,2,…,n}表示中心位置为y的 的叠加，且保证f代)≥1，表达为 行人目标区域经过图像粒度R,粒化后的图像粒， fc(v)=fc(vg)+fc(vc)+fc(vg)= x·表示每个图像粒L的中心位置，则经过图像粒 g·2隆-9+6·2-9+g·2晚-9+1(6) 化后的加权核函数为 式中：u=(R,"c,B)表示R,G,B颜色特征值向量， mRc=n限+n+n+1表示最终得到的一维颜色 2 特征值的级数。 -XX≤1x=1I(7) K0=0,X>1 未经颜色特征粒化(a)和经过颜色特征粒化后 的颜色直方图(b)如图2所示。 式中：h表示行人目标区域核半径。{xJj=1,2,…, 300 m×n}表示图像粒L的像素位置，b(x,)= 250 [b(x)b(x)b(x,)]表示像素x,的R、G、 B颜色特征值向量，其中b(x)、b(x)、b(x) 200 分别表示R、G、B三颜色通道的特征值，则每个图像 150 粒L的颜色特征值向量通过转换函数式(2)得到 100 f(L)= (8) m×n 通过式(6)和式(8)，求得行人目标区域经过图像粒 50 100150200250300 化和颜色通道粒化后的参考颜色直方图q= 颜色级数 为 (a)颜色特征直方图 (qu)u=1.2..mgc 35 g.=cI y-x [fc(f(L)）-] 30 (9) 25 式中：8为Kronecker函数；C为归一化常数，使得 20 15 ∑9.=1，因此有 10 C= (10) K A 10 20306060 同理，设在跟踪过程中行人目标候选区域的颜 颜色级数 色直方图经过图像粒化和颜色通道粒化后表示为 (b)粒化的颜色特征直方图 图2颜色直方图 p少o)=p.(少o)=1,2。,其中为为目标候选区 域的中心位置，同样有 Fig.2 Color histogram
粒度来量化，经验得出 Ｇ 通道最敏感， Ｒ 通道次之， Ｂ 通道敏感度最低。 因此 Ｇ 通道要表现更多的颜色特 征信息，颜色粒度则赋予最大；而敏感度相对最弱的 Ｂ 通道表现最少的颜色特征信息，颜色粒度则赋予最 小。 令 Ｒ、Ｇ、Ｂ 通道的量化粒度分别表示为 Ｒ Ｒ Ｃ 、 Ｒ Ｇ Ｃ 、 Ｒ Ｂ Ｃ ，经验得出当 Ｒ Ｒ Ｃ ＝ ５、 Ｒ Ｇ Ｃ ＝ ６、 Ｒ Ｂ Ｃ ＝ ３ 时表现的颜色 特征信息最为有效，行人跟踪效果较好。 计算经过颜色通道粒化后的 ３ 个颜色通道的直 方图虽然已经降低了一定的计算代价和存储代价， 但是为了更进一步简化计算量和降低存储代价，将 颜色粒化后的三通道颜色值整合成一维颜色值作为 该颜色粒的颜色特征值，由于颜色的权重信息已经 在颜色粒化的时候通过颜色粒度表现，因此整体的 转换函数 ｆ（ｖ） 直接体现为各颜色通道的转换函数 的叠加，且保证 ｆ（ｖ） ≥ １，表达为 ｆＣ（ｖ） ＝ ｆＣ（ｖＲ ） ＋ ｆＣ（ｖＧ ） ＋ ｆＣ（ｖＢ ） ＝ ｖＲ·２ ＲＲ Ｃ －９ ＋ ｖＧ·２ ＲＧ Ｃ －９ ＋ ｖＢ·２ ＲＢ Ｃ －９ ＋ １ （６） 式中： ｖ ＝ （ｖＲ ，ｖＧ ，ｖＢ ） 表示 Ｒ、Ｇ、Ｂ 颜色特征值向量， ｍＲＣ ＝ ｎＲＲ Ｃ ＋ ｎＲＧ Ｃ ＋ ｎＲＢ Ｃ ＋ １ 表示最终得到的一维颜色 特征值的级数。 未经颜色特征粒化（ ａ）和经过颜色特征粒化后 的颜色直方图（ｂ）如图 ２ 所示。 （ａ）颜色特征直方图 （ｂ）粒化的颜色特征直方图 图 ２ 颜色直方图 Ｆｉｇ．２ Ｃｏｌｏｒ ｈｉｓｔｏｇｒａｍ 比较两图，可看到粒化后的颜色直方图在颜色 级数上降低了大约 ５ 倍，曲线与横轴所围成的面积 是采集的目标区域的像素点数量，可见粒化后的像 素点数量大约降低了 ４ 倍，大大降低了计算量。 这 一点将在后续的实验中得到进一步的验证。 ２ 粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法 粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法（ＧＭＳ）是利用 图像粒化及颜色通道粒化后的核函数空间加权的颜 色直方图作为目标模型，采用巴氏系数作为相似度 度量，通过自适应步长的 ＭＳ 迭代来实时跟踪行人 目标的位置。 ２．１ 算法描述 设 ｛Ｌ ＲＩ ｉ ，ｉ ＝ １，２，…，ｎＲＩ ｝ 表示中心位置为 ｙ 的 行人目标区域经过图像粒度 ＲＩ 粒化后的图像粒， ｘ ∗ ｉ 表示每个图像粒 Ｌ ＲＩ ｉ 的中心位置，则经过图像粒 化后的加权核函数为 Ｋ（Ｘ） ＝ １ － Ｘ ０， { ，Ｘ ≤ １ Ｘ ＞ １ Ｘ ＝ ‖ ｙ － ｘ ∗ ｉ ｈ ‖ ２ （７） 式中：ｈ 表示行人目标区域核半径。 ｛ｘｉ，ｊ，ｊ ＝ １，２，…， ｍ ＲＩ × ｎ ＲＩ｝ 表示图像粒 Ｌ ＲＩ ｉ 的像素位置， ｂｆ（ｘｉ，ｊ） ＝ ［ｂ Ｒ ｆ （ｘｉ，ｊ） ｂ Ｇ ｆ （ｘｉ，ｊ） ｂ Ｂ ｆ （ｘｉ，ｊ）］ 表示像素 ｘｉ，ｊ 的 Ｒ、Ｇ、 Ｂ 颜色特征值向量，其中 ｂ Ｒ ｆ （ｘｉ，ｊ）、ｂ Ｇ ｆ （ｘｉ，ｊ）、ｂ Ｂ ｆ （ｘｉ，ｊ） 分别表示 Ｒ、Ｇ、Ｂ 三颜色通道的特征值，则每个图像 粒 Ｌ ＲＩ ｉ 的颜色特征值向量通过转换函数式（２）得到 ｆ Ｉ（Ｌ ＲＩ ｉ ） ＝ ∑ ｍＲ Ｉ×ｎＲ Ｉ ｊ ＝ １ ｂｆ（ｘｊ） ｍ ＲＩ × ｎ ＲＩ （８） 通过式（６）和式（８），求得行人目标区域经过图像粒 化和 颜 色 通 道 粒 化 后 的 参 考 颜 色 直 方 图 ｑ ＝ ｑｕ { } ｕ ＝ １，２，…，ｍＲ Ｃ 为 ｑｕ ＝ Ｃ∑ ｎＲ Ｉ ｉ ＝ １ Ｋ ‖ ｙ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ δ ｆＣ（ｆ Ｉ（Ｌ ＲＩ [ ｉ ）） － ｕ] （９） 式中： δ 为 Ｋｒｏｎｅｃｋｅｒ 函数； Ｃ 为归一化常数，使得 ∑ ｍＲ Ｃ ｕ ＝ １ ｑｕ ＝ １，因此有 Ｃ ＝ １ ∑ ｎＲ Ｉ ｉ ＝ １ Ｋ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ （１０） 同理，设在跟踪过程中行人目标候选区域的颜 色直方图经过图像粒化和颜色通道粒化后表示为 ｐ（ｙ０ ） ＝ ｛ｐｕ（ｙ０ ）｝ｕ ＝ １，２，…，ｍＲ Ｃ ，其中 ｙ１ 为目标候选区 域的中心位置，同样有 ·４３６· 智 能 系 统 学 报 第 １１ 卷
第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算法的平均迭
ｐｕ（ｙ０ ） ＝ Ｃ∑ ｎＲ Ｉ ｉ ＝ １ Ｋ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ δ ｆＣ（ｆ Ｉ（Ｌ ＲＩ [ ｉ ）） － ｕ] （１１） 基于巴氏系数，求得目标区域的参考颜色直方图 ｑ 和目标候选区域的颜色直方图 ｐ（ｙ０ ） 的相似度为 ρ［ｐ（ｙ０ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ０ ）ｑｕ （１２） 至此，粒化的 ＭＳ 行人跟踪算法的 ＭＳ 跟踪迭代 步骤可以总结为算法 １。 算法 １ 粒 化 的 Ｍｅａｎ Ｓｈｉｆｔ 行 人 跟 踪 算 法 （ＧＭＳ） 输入 行人跟踪视频图像序列。 初始化 图像粒度 ＲＩ ＝ ３ 和颜色通道粒度 Ｒ Ｒ Ｃ ＝５， Ｒ Ｇ Ｃ ＝ ６， Ｒ Ｂ Ｃ ＝ ３；给定行人目标初始中心位置 ｙ０ 及行人目标区域核半径 ｈ ，由式（９）得到行人目 标区域经过粒化后的参考颜色直方图 ｑ 。 跟踪过程 １）以 ｙ０ 为行人目标初始中心位置，分别由式 （ １１ ） 和 式 （ １２ ） 计 算 ｛ｐｕ（ｙ０ ）｝ｕ ＝ １，２，…，ｍＲ Ｃ 和 ρ［ｐ（ｙ０ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ０ ）ｑｕ 。 ２）计算权值 ｗｉ { } ｉ ＝ １，２，…，ｎＲ Ｉ 。 ｗｉ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ δ ｆＣ（ｆ Ｉ（Ｌ ＲＩ [ ｉ ）） － ｕ] ｑｕ ｐｕ（ｙ０ ） ３）计算行人目标新位置 ｙ１ ： ｙ１ ＝ ∑ ｎＲ Ｉ ｉ ＝ １ ｘ ∗ ｉ ｗｉｇ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ ∑ ｎＲ Ｉ ｉ ＝ １ ｇ ‖ ｙ０ － ｘ ∗ ｉ ｈ ‖ ２ æ è ç ö ø ÷ ４）计算新位置的颜色直方图 ｛ｐｕ（ｙ１ ）｝ｕ ＝ １，２，…，ｍＲ Ｃ 。 ５）由式（１２）计算新位置和行人目标的相似度 ρ［ｐ（ｙ１ ），ｑ］ ＝ ∑ ｍＲ Ｃ ｕ ＝ １ ｐｕ（ｙ１ ）ｑｕ 。 ６）如果 ρ［ｐ（ｙ１ ），ｑ］ ＜ ρ［ｐ（ｙ０ ），ｑ］ ，则令 ｙ１ ← １ ２ （ｙ０ ＋ ｙ１ ）。 ７）若 ‖ｙ１ － ｙ０‖ ＜ ε ，则本轮迭代结束；否则 ｙ０ ← ｙ１ 返回 １）继续迭代更新行人目标位置。 输出 当前帧行人目标区域实时最优位置。 ２．２ 算法计算复杂度 ＧＭＳ 算法的跟踪迭代框架基本维持 ＭＳ 算法的 跟踪框架，因此 ＧＭＳ 算法和 ＭＳ 算法的计算代价主 要区别在每次迭代的计算代价，表现在颜色直方图 ｐ 、新位置 ｙ１ 和相似度 ρ 的计算代价上，ＭＳ 算法中 表示为 ＣＨ 、 Ｃｙ 、 Ｃρ ，ＧＭＳ 算法中表示为 Ｃ′Ｈ 、 Ｃ′ｙ 、 Ｃ′ρ ，如表 １。 表 １ ＭＳ 和 ＧＭＳ 的运算代价 Ｔａｂｌｅ １ Ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｃｏｓｔ ｏｆ ＭＳ ａｎｄ ＧＣＭＳ 代价 ＭＳ ＧＭＳ 直方图 ＣＨ ＝ ＲＣｗ ＋ Ｒ（Ｃｐ ＋ ３Ｃｍ ＋ Ｃａ ） Ｃ′Ｈ ＝ Ｒ′Ｃｗ ＋ Ｒ′（Ｃｐ ＋ ３Ｃｒ ＋ Ｃａ ） 新位置 Ｃｙ ＝ ｕ（Ｃｗ ＋ Ｃｄ ） ＋ Ｒ（３Ｃｍ ＋ Ｃａ ） Ｃ′ｙ ＝ ｕ′（Ｃｗ ＋ Ｃｄ ） ＋ Ｒ′（３Ｃｍ ＋ Ｃａ ） 相似度 Ｃρ ＝ ｕ（Ｃｓ ＋ Ｃｍ ＋ Ｃａ ） Ｃ′ρ ＝ ｕ′（Ｃｓ ＋ Ｃｍ ＋ Ｃａ ） 表中 Ｃｗ 、 Ｃｐ 、 Ｃｍ 、 Ｃａ 、 Ｃｒ 、 Ｃｄ 、 Ｃｓ 分别表示 核函数加权、获取像素值、浮点数乘法、加法、移位运 算、除法运算和开方的计算代价； Ｒ 、 ｕ 分别表示 ＭＳ 算法中的行人目标区域大小及颜色直方图的级数； Ｒ′ 、 ｕ′ 分别表示 ＧＭＳ 算法中的行人目标区域大小 及颜色直方图的级数；满足近似关系 Ｒ ／ Ｒ′ ＝ ４， ｕ ／ ｕ′ ≈５， Ｃｍ 和 Ｃｒ 的关系无法准确比较，但是 Ｃｍ ≻ Ｃｒ 一定成立。 至此可近似估计出 ＭＳ 和 ＧＭＳ 的每 次迭代的计算代价关系，为式（ １３）。 理论计算得 出，仅考虑各运算代价时，ＧＭＳ 算法比 ＭＳ 算法的计 算代价至少快 ４ 倍，是个可观的结果。 在实际实验 中，由于图像分块函数消耗、硬件等原因会使得真正 计算效率低于 ４ 倍。 ＣＨ ＋ Ｃｙ ＋ Ｃρ Ｃ′Ｈ ＋ Ｃ′ｙ ＋ Ｃ′ρ ≈ ４ （１３） ３ 实验结果与分析 在 ＣＰＵ２．６ ＧＨｚ、内存 ４ ＧＢ 的 ＰＣ 机、ＭＡＴＬＡＢ （Ｒ２０１３ｂ）的环境下进行实验，实现本文的改进算法 ＧＭＳ 跟踪算法，并实现传统 ＭＳ 跟踪算法、Ｋａｌｍａｎ 滤波跟踪算法和粒子滤波跟踪算法与之比较。 采用 ４ 组视频图像序列进行实验，图像序列选 自 ＰＥＴＳ２００９ 和 ＣＡＶＩＡＲ 视频图像库，涵盖了行人 跟踪的主要场景及挑战场景，包括简单背景、复杂背 景、目标遮挡、形变及光照变化等。 为检测本文方法 的性能，将与传统 ＭＳ 跟踪算法、Ｋａｌｍａｎ 滤波跟踪算 法和粒子滤波跟踪算法进行比较分析。 ３．１ 与传统 ＭＳ 跟踪的比较 图 ３ 选取的视频图像是 Ｓ２＿Ｌ１ 项目中 Ｖｉｅｗ＿ ００５ 中的部分序列，序列中红衣女子从视频窗口右 端水平穿过走向视频窗口左端，期间活动窗口只有 红衣女子一人，跟踪图像背景较简单。 其中图 ３（ａ） 是 ＭＳ 的跟踪结果，图 ３（ｂ）是 ＧＭＳ 的跟踪结果。 从 跟踪结果可发现该序列 ＭＳ 和 ＧＭＳ 的跟踪效果都 较好，在整个行人跟踪过程中都有正确跟踪到目标 行人，但是观察表 ２ 发现该序列 ＭＳ 算法的平均迭 第 ４ 期 刘翠君，等：粒化的 Ｍｅａｎ Ｓｈｉｆｔ 行人跟踪算法 ·４３７·