.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,时的第献［１］对 ＭＳ 跟踪算法的经典文献和研究历程做了 详细综述。 ２００３ 年 Ｄ．Ｃｏｍａｎｉｃｉｕ 等［２］ 将 ＭＳ 应用于 视觉跟踪领域，首次提出 ＭＳ 跟踪算法，开辟了视觉 跟踪领域的新方向，自此有大量关于 ＭＳ 的改进算 法被提出。 为提高 ＭＳ 跟踪算法的适应能力，在目 标模板更新策略上，文献［３］提出基于线性加权的 模板更新；文献［４］提出基于滤波的模板更新方法； 在目标尺度及方向估计上，文献［５］提出基于特征 点匹配的尺度与方向估计方法，消除由于尺度变化 导致的定位误差；文献［６］提出基于权重图的尺度 与方向估计方法，能更准确地反应目标尺度信息；在 抗遮挡跟踪上，文献［７］在 ＭＳ 跟踪算法的基础上引 入 Ｋａｌｍａｎ 滤波器来辅助预测目标位置，增强了稳健 性；文献［８］提出目标分块的方法，通过子块的跟踪 定位来获得目标的整体位置；在跟踪快速目标上， ＭＳ 迭代容易陷入局部最优值，使得无法处理快速 运动的目标，文献［９］引入模拟退火算法，提出退火 ＭＳ 来逐步平滑代价函数，用于全局模式的搜索，跳 出局部最优值。 ＭＳ 跟踪向来以计算简单、调节参数少为优势， 这些改进算法尽管从不同方面改进了 ＭＳ 跟踪算法 的缺陷，但是也一定程度上增加了计算复杂度和调 节参数，无法很好地保证跟踪实时性。 ＭＳ 跟踪存在 的挑战问题有许多，本文旨在基本保留 ＭＳ 的跟踪 框架上解决 ＭＳ 跟踪的基本问题：颜色直方图带来 的干扰问题和计算复杂度问题。 考虑到颜色直方图 对于目标形状、姿态、旋转等变化及遮挡都具有一定 的鲁棒性，但是由于摄像机的视频图像质量普遍较 差，分辨率普遍较低，易受背景颜色干扰，使得采集 到的目标颜色特征存在较大的噪声冗余信息，然而 粒计算方法恰巧能有效地处理视频图像大数据冗余 信息。 粒计算方法由 Ｚａｄｅｈ ［１２］ 和 Ｌｉｎ ［１３］ 首次提出，是 人工智能领域中的一种新理念和新方法，它覆盖了 所有和粒度相关的理论、方法和技术，主要用于对不 确定、不精确、不完整信息的处理，对大规模海量数 据的挖掘和对复杂问题的求解［１４］ 。 粒计算的实质 是通过选择合适的粒度，来寻找一种较好的、近似的 解决方案，避免复杂的计算，从而降低问题求解的难 度。 文献［１５］归纳了粒计算方法在大数据处理中 的 ３ 种基本模式并讨论了粒计算方法应用于大数据 的可行性及优势。 考虑到摄像机视频图像中的海量 数据挖掘和行人跟踪问题的复杂计算，试图通过粒 计算方法找到降低计算代价并有效改进跟踪效果的 方法。 本文提出粒化的 ＭＳ 行人跟踪算法，基本保留 ＭＳ 跟踪算法框架，引入粒计算方法来优化颜色特 征表示，在颜色特征的采集和处理上都采用粒计算 方法表示，得到粒化后的核函数加权颜色直方图作 为颜色特征表示，通过 ＭＳ 迭代实现行人跟踪，一定 程度上削弱了图像噪声干扰，不仅降低了计算代价， 而且提高了跟踪实时性。 １ 颜色特征粒化 将大量的复杂特征及信息按其各自的特征及性 能划分为若干个较简单的块，每一块看作是一个信 息粒，这些信息粒具有相似的特征及性能，这个划分 过程就是信息粒化的过程。 定义 １ 用一个三元组来描述信息粒 Ｇ ＝ （ＩＧ， ＥＧ，ＦＧ） ，其中 ＩＧ 称为信息粒 Ｇ 的内涵， ＥＧ 称为信息 粒 Ｇ 的外延； ＦＧ 称为内涵和外延之间的转换函数。 信息粒的内涵 ＩＧ 是信息粒在特定环境下的表 现知识，表示在一个特定的任务下信息粒中所有元 素的一般性特征、规则、共同性等，可以定义一个语 言，由这个语言的公式来表示；信息粒的外延 ＥＧ 是 满足这个公式的所有对象的集合；信息粒的转换函 数 ＦＧ 是 ＥＧ 到 ＩＧ 的泛化转换函数。 对于信息粒 Ｇ ＝（ＩＧ，ＥＧ，ＦＧ） ， Ｘ 为对于信息粒 Ｇ 所有可能外 延 ＥＧ 的对象的集合，即外延的论域； Ｙ 为对于信息 粒 Ｇ 所有可能内涵 ＩＧ 的集合，即内涵的论域。 下面 给出转换函数 ＦＧ 的形式化定义。 定义 ２ 从 Ｘ 到 Ｙ 的信息粒的泛化转换函数是 笛卡尔积 Ｘ × Ｙ 的一个子集 ＦＧ ，对于每个属于 Ｘ 的 ＥＧ 都存在唯一的 Ｙ 中的元素 ＩＧ 使得 （ＥＧ，ＩＧ） 属 于 ＦＧ 。 传统的 ＭＳ 行人跟踪算法采集行人目标区域的 颜色特征信息，粒化的 ＭＳ 行人跟踪算法引入粒计 算的思想对颜色特征信息进行粒化，包含两个信息 粒化过程：图像粒化和颜色通道粒化。 １．１ 图像粒化 行人目标区域存在背景颜色干扰，为了减弱背 景颜色干扰和降低计算代价，将图像行人目标区域 进行不同粒度的粒层分块，并采集每一粒块的 Ｒ、Ｇ、 Ｂ 颜色均值，得到图像特征信息粒格，简称图像粒， 该过程为图像粒化。 用三元组 Ｇ Ｉ ＝ （ＩＧ Ｉ ，ＥＧ Ｉ ，ＦＧ Ｉ ） 表示图像粒，内涵 ＩＧ Ｉ 是由外延 ＥＧ Ｉ 集合中的每个 对象通过转换关系 ＦＧ Ｉ 计算出的 Ｒ、Ｇ、Ｂ 颜色均值 集合。 外延 ＥＧ Ｉ 的论域 Ｘ Ｉ ＝ ｛〖Ｍ × Ｎ〗 Ｍ，Ｎ ∈ ℕ ｝， 其中 〖Ｍ × Ｎ〗 表示大小为 Ｍ × Ｎ 的图像粒块， Ｌ ＲＩ ｉ ∈ Ｘ Ｉ ，ｉ ＝ １，２，…，ｎＲＩ ，表示图像粒度为 ＲＩ 时的第 ·４３４· 智 能 系 统 学 报 第 １１ 卷