·188 智能系统学报 第10卷 和处理，从而提取出目标物体的运动轨迹。超市作为 征点在连续帧之间的匹配，从而得到特征点轨 目标跟踪的典型应用场景，其目标跟踪的主要任务集 迹[2,416]。具体来说，KLT算法假定在特征窗口W 中在对顾客的运动轨迹进行提取。超市作为供应链 内t时刻的图像帧表示为I(x,y,t),t+T时刻的图 系统的终端，顾客的运动跟踪为超市拥塞控制、商品 像帧表示为I(x,y,t+r),从1时刻到t+T时刻的 布局、购物推荐、自动预警等应用提供了数据基石，因 位置关系满足式(1)： 而具有很高的应用价值和广阔的应用前景。 I(x,y,t+T)=I(x-△x,y-△y）（1) 当前目标跟踪的主要方法分为点跟踪、轮廓跟踪 定义d=(△x,△y)为点X(x,y)的偏移量。KLT匹 与核跟踪3类)。基于点跟踪的方法，如卡尔曼滤 配的过程即为寻找d使得式(2)中ε达到最小值。 波2)、最优分配滤波跟踪等，目标在视频帧中采用 s=J[J(x+d)-1(X)]o(X)dx (2)》 点表示，通过前一帧中物体的位置、运动等状态将后 一帧中的点与前一帧中的点关联起来。但基于点跟 式中：I、J表示2帧图像，W为特征窗口，ω(X)为 踪的方法需要在每一帧中检测出被跟踪的目标，不适 加权函数。 合用于超市这种存在较多遮挡的应用场景中。基于 1.2特征点轨迹预处理 轮廓跟踪的方法利用目标区域内的信息，通过轮廓演 由于KLT算法中提取出特征点是基于图像特 化)或形状匹配6进行跟踪。这种方法需要获取目 征窗口内梯度矩阵的特征值，即选取纹理模式稳定 标的轮廓信息，因而在超市这种顾客姿态各异的场景 且明显的点作为特征点。然而，在实际视频帧中，这 中应用受限。基于核跟踪的方法，如meanshift-)、 样的点不仅分布在移动的目标上，也大量存在于背 KLTo]等，通过计算核在连续帧之间平移、旋转、仿 景中，因此需要将背景特征点及对应轨迹进行滤除。 射等运动进行目标的跟踪。基于核跟踪的方法通常 另一方面，KLT算法跟踪出的特征点轨迹中存在跟 对目标的运动方式和所处环境有一定约束，例如KLT 踪不稳定的情况，即一部分特征点在被跟踪较短的 算法要求视频流中光照强度几乎不变，且特征点在连 时间之后丢失。此时，除了补充新的特征点以保证 续2帧之间的运动为微小运动。 特征点总数稳定之外，应当在跟踪结果中将这部分 综合以上方法的优点和不足之处，考虑到本文所 短暂的轨迹进行滤除。 述场景中超市室内光照条件能够保持基本稳定且顾 1.2.1滤除背景特征点 客运动轨迹在相邻2帧之间无突变，本文采用KLT 背景特征点相对于运动目标上的特征点，其表 算法进行特征，点提取和跟踪，得到一系列特征点的运 现为在特征点轨迹中，其坐标长时间保持恒定。定 动轨迹。通过特征点预处理过程对背景和短时特征 义特征点FP在第t帧的坐标为FP,=(x,y),则背 点轨迹进行滤除，从而分离出视频每一帧中运动目标 景特征点满足式(3)： 所在区域的关键特征点。进一步，利用当前帧中的特 3L∈(s,+0),i>0, 征点在前后帧窗口内的信息，采用meanshift算法对 j∈[i,i+L-1],d(FP,FP+1)=0(3) 当前帧中的特征点所对应的轨迹进行聚类，聚为同一 式中：L为轨迹连续静止帧数，d(FP:,FP+1)表示 类的轨迹在当前帧中的特征点对应属于同一类，从而 特征点FP在第i帧与第i+1帧之间移动的距离，s 解决了仅使用单帧静态特征点聚类时多个目标之间 表示特征点最大连续静止帧数。滤除背景特征点的 的遮挡问题]。最终，在视频每一帧中查找当前帧 过程即为在KLT特征点的跟踪结果中遍历每一条 的所有特征点类在前一帧中相似度最高的匹配类，得 特征点轨迹，若满足式(3)，则将该轨迹标记为无效 到目标在连续视频帧中的运动轨迹。通过上述运动 轨迹。滤除背景特征点的流程如算法1所示。 匹配算法，解决了运动目标出入视频区域以及具有复 算法1滤除背景特征点 杂运动轨迹时的稳定跟踪问题。 输入轨迹集合trajSet最大连续静止帧数s; 输出轨迹集合trajSet。 1 特征点轨迹提取及预处理 1)for all traj in trajSet 1.1特征点轨迹提取 2)按照式(3)计算轨迹连续静止长度L 本文采用KLT算法进行特征点提取及跟踪， 3)ifL>s KLT算法是一种经典的基于特征的跟踪算法，该算 4) trajSet +-trajSet -(traj} 法选择图像特征窗口内梯度矩阵特征值较大的点作 5)end if 为特征点，并利用基于最优估计的匹配算法实现特 6)end for和处理，从而提取出目标物体的运动轨迹。 超市作为 目标跟踪的典型应用场景，其目标跟踪的主要任务集 中在对顾客的运动轨迹进行提取。 超市作为供应链 系统的终端，顾客的运动跟踪为超市拥塞控制、商品 布局、购物推荐、自动预警等应用提供了数据基石，因 而具有很高的应用价值和广阔的应用前景。 当前目标跟踪的主要方法分为点跟踪、轮廓跟踪 与核跟踪 ３ 类［１］ 。 基于点跟踪的方法，如卡尔曼滤 波［２⁃３］ 、最优分配滤波跟踪［４］等，目标在视频帧中采用 点表示，通过前一帧中物体的位置、运动等状态将后 一帧中的点与前一帧中的点关联起来。 但基于点跟 踪的方法需要在每一帧中检测出被跟踪的目标，不适 合用于超市这种存在较多遮挡的应用场景中。 基于 轮廓跟踪的方法利用目标区域内的信息，通过轮廓演 化［５］或形状匹配［６］ 进行跟踪。 这种方法需要获取目 标的轮廓信息，因而在超市这种顾客姿态各异的场景 中应用受限。 基于核跟踪的方法，如 ｍｅａｎｓｈｉｆｔ ［７⁃９］ 、 ＫＬＴ ［１０⁃１２］等，通过计算核在连续帧之间平移、旋转、仿 射等运动进行目标的跟踪。 基于核跟踪的方法通常 对目标的运动方式和所处环境有一定约束，例如 ＫＬＴ 算法要求视频流中光照强度几乎不变，且特征点在连 续 ２ 帧之间的运动为微小运动。 综合以上方法的优点和不足之处，考虑到本文所 述场景中超市室内光照条件能够保持基本稳定且顾 客运动轨迹在相邻 ２ 帧之间无突变，本文采用 ＫＬＴ 算法进行特征点提取和跟踪，得到一系列特征点的运 动轨迹。 通过特征点预处理过程对背景和短时特征 点轨迹进行滤除，从而分离出视频每一帧中运动目标 所在区域的关键特征点。 进一步，利用当前帧中的特 征点在前后帧窗口内的信息，采用 ｍｅａｎｓｈｉｆｔ 算法对 当前帧中的特征点所对应的轨迹进行聚类，聚为同一 类的轨迹在当前帧中的特征点对应属于同一类，从而 解决了仅使用单帧静态特征点聚类时多个目标之间 的遮挡问题［１３］ 。 最终，在视频每一帧中查找当前帧 的所有特征点类在前一帧中相似度最高的匹配类，得 到目标在连续视频帧中的运动轨迹。 通过上述运动 匹配算法，解决了运动目标出入视频区域以及具有复 杂运动轨迹时的稳定跟踪问题。 １ 特征点轨迹提取及预处理 １．１ 特征点轨迹提取 本文采用 ＫＬＴ 算法进行特征点提取及跟踪， ＫＬＴ 算法是一种经典的基于特征的跟踪算法，该算 法选择图像特征窗口内梯度矩阵特征值较大的点作 为特征点，并利用基于最优估计的匹配算法实现特 征点在 连 续 帧 之 间 的 匹 配， 从 而 得 到 特 征 点 轨 迹［１２， １４⁃１６］ 。 具体来说，ＫＬＴ 算法假定在特征窗口 Ｗ 内 ｔ 时刻的图像帧表示为 Ｉ（ｘ，ｙ，ｔ） ， ｔ ＋ τ 时刻的图 像帧表示为 Ｉ（ｘ，ｙ，ｔ ＋ τ） ，从 ｔ 时刻到 ｔ ＋ τ 时刻的 位置关系满足式（１）： Ｉ（ｘ，ｙ，ｔ ＋ τ） ＝ Ｉ（ｘ － Δｘ，ｙ － Δｙ） （１） 定义 ｄ ＝ （Δｘ，Δｙ） 为点 Ｘ（ｘ，ｙ） 的偏移量。 ＫＬＴ 匹 配的过程即为寻找 ｄ 使得式（２）中 ε 达到最小值。 ε ＝ ∬ Ｗ ［Ｊ（Ｘ ＋ ｄ） － Ｉ（Ｘ）］ ２ω（Ｘ）ｄＸ （２） 式中： Ｉ 、 Ｊ 表示 ２ 帧图像， Ｗ 为特征窗口， ω（Ｘ） 为 加权函数。 １．２ 特征点轨迹预处理 由于 ＫＬＴ 算法中提取出特征点是基于图像特 征窗口内梯度矩阵的特征值，即选取纹理模式稳定 且明显的点作为特征点。 然而，在实际视频帧中，这 样的点不仅分布在移动的目标上，也大量存在于背 景中，因此需要将背景特征点及对应轨迹进行滤除。 另一方面，ＫＬＴ 算法跟踪出的特征点轨迹中存在跟 踪不稳定的情况，即一部分特征点在被跟踪较短的 时间之后丢失。 此时，除了补充新的特征点以保证 特征点总数稳定之外，应当在跟踪结果中将这部分 短暂的轨迹进行滤除。 １．２．１ 滤除背景特征点 背景特征点相对于运动目标上的特征点，其表 现为在特征点轨迹中，其坐标长时间保持恒定。 定 义特征点 ＦＰ 在第 ｔ 帧的坐标为 ＦＰｔ ＝ （ｘ，ｙ） ，则背 景特征点满足式（３）： ∃Ｌ ∈ （ｓ， ＋ ¥），ｉ ＞ ０， ∀ｊ ∈ ［ｉ，ｉ ＋ Ｌ － １］，ｄ（ＦＰｉ，ＦＰｉ＋１ ） ＝ ０ （３） 式中： Ｌ 为轨迹连续静止帧数， ｄ（ＦＰｉ，ＦＰｉ＋１ ） 表示 特征点 ＦＰ 在第 ｉ 帧与第 ｉ ＋ １ 帧之间移动的距离， ｓ 表示特征点最大连续静止帧数。 滤除背景特征点的 过程即为在 ＫＬＴ 特征点的跟踪结果中遍历每一条 特征点轨迹，若满足式（３），则将该轨迹标记为无效 轨迹。 滤除背景特征点的流程如算法 １ 所示。 算法 １ 滤除背景特征点 输入 轨迹集合 ｔｒａｊＳｅｔ 最大连续静止帧数 ｓ； 输出 轨迹集合 ｔｒａｊＳｅｔ。 １）ｆｏｒ ａｌｌ ｔｒａｊ ｉｎ ｔｒａｊＳｅｔ ２） 按照式（３）计算轨迹连续静止长度 Ｌ ３） ｉｆ Ｌ ＞ ｓ ４） ｔｒａｊＳｅｔ ← ｔｒａｊＳｅｔ － {ｔｒａｊ} ５） ｅｎｄ ｉｆ ６）ｅｎｄ ｆｏｒ ·１８８· 智 能 系 统 学 报 第 １０ 卷