在计算机视觉领域的各种研究和应用中，目标跟踪一直是一项重要而又兼具挑战性的技术。目标跟踪的主要任务在于对视频流中的运动信息进行分析和处理，从而提取出目标物体的运动轨迹。超市作为目标跟踪的典型应用场景，其目标跟踪的主要任务集中在对顾客的运动轨迹进行提取。超市作为供应链系统的终端，顾客的运动跟踪为超市拥塞控制、商品布局、购物推荐、自动预警等应用提供了数据基石，因而具有很高的应用价值和广阔的应用前景。

当前目标跟踪的主要方法分为点跟踪、轮廓跟踪与核跟踪3类^[1]。基于点跟踪的方法，如卡尔曼滤波^{[2, 3]}、最优分配滤波跟踪^[4]等，目标在视频帧中采用点表示，通过前一帧中物体的位置、运动等状态将后一帧中的点与前一帧中的点关联起来。但基于点跟踪的方法需要在每一帧中检测出被跟踪的目标，不适合用于超市这种存在较多遮挡的应用场景中。基于轮廓跟踪的方法利用目标区域内的信息，通过轮廓演化^[5]或形状匹配^[6]进行跟踪。这种方法需要获取目标的轮廓信息，因而在超市这种顾客姿态各异的场景中应用受限。基于核跟踪的方法，如meanshift^{[7, 8, 9]}、KLT^{[10, 11, 12]}等，通过计算核在连续帧之间平移、旋转、仿射等运动进行目标的跟踪。基于核跟踪的方法通常对目标的运动方式和所处环境有一定约束，例如KLT算法要求视频流中光照强度几乎不变，且特征点在连续2帧之间的运动为微小运动。

综合以上方法的优点和不足之处，考虑到本文所述场景中超市室内光照条件能够保持基本稳定且顾客运动轨迹在相邻2帧之间无突变，本文采用KLT算法进行特征点提取和跟踪，得到一系列特征点的运动轨迹。通过特征点预处理过程对背景和短时特征点轨迹进行滤除，从而分离出视频每一帧中运动目标所在区域的关键特征点。进一步，利用当前帧中的特征点在前后帧窗口内的信息，采用meanshift算法对当前帧中的特征点所对应的轨迹进行聚类，聚为同一类的轨迹在当前帧中的特征点对应属于同一类，从而解决了仅使用单帧静态特征点聚类时多个目标之间的遮挡问题^[13]。最终，在视频每一帧中查找当前帧的所有特征点类在前一帧中相似度最高的匹配类，得到目标在连续视频帧中的运动轨迹。通过上述运动匹配算法，解决了运动目标出入视频区域以及具有复杂运动轨迹时的稳定跟踪问题。

本文采用KLT算法进行特征点提取及跟踪，KLT算法是一种经典的基于特征的跟踪算法，该算法选择图像特征窗口内梯度矩阵特征值较大的点作为特征点，并利用基于最优估计的匹配算法实现特征点在连续帧之间的匹配，从而得到特征点轨迹^{[12, 14, 15, 16]}。具体来说，KLT算法假定在特征窗口W内t时刻的图像帧表示为I(x,y,t)，t+τ时刻的图像帧表示为I(x,y,t+τ)，从t时刻到t+τ时刻的位置关系满足式(1):

由于KLT算法中提取出特征点是基于图像特征窗口内梯度矩阵的特征值，即选取纹理模式稳定且明显的点作为特征点。然而，在实际视频帧中，这样的点不仅分布在移动的目标上，也大量存在于背景中，因此需要将背景特征点及对应轨迹进行滤除。另一方面，KLT算法跟踪出的特征点轨迹中存在跟踪不稳定的情况，即一部分特征点在被跟踪较短的时间之后丢失。此时，除了补充新的特征点以保证特征点总数稳定之外，应当在跟踪结果中将这部分短暂的轨迹进行滤除。

背景特征点相对于运动目标上的特征点，其表现为在特征点轨迹中，其坐标长时间保持恒定。定义特征点FP在第t帧的坐标为FP_t=(x,y)，则背景特征点满足式(3)：

算法1    滤除背景特征点

输入    轨迹集合trajSet最大连续静止帧数s;

输出    轨迹集合trajSet。

1)for all traj in trajSet

2)    按照式(3)计算轨迹连续静止长度L

3)    ifL>s

4)      trajSet←trajSet－ {traj}

5)    end if

6)end for

短时特征点相对于被稳定跟踪的特征点，其表现为连续运动帧数过短。由于在超市不同位置的具体场景以及摄像机角度、焦距等不尽相同，故不能直接参照滤除背景特征点中的方法为特征点的连续运动帧数取固定的阈值，而应当根据当前视频中轨迹长度的分布情况选取更为合理的阈值。

定义L_i为KLT跟踪结果中第i条轨迹的长度，则最小连续运动帧数m如式(4)所示，其中λ为权重系数。

短时特征点即为满足式(5)的特征点，

在特征点轨迹提取和预处理的基础之上，本文采用轨迹聚类的方法在每一帧中检测出运动目标^{[13, 15, 17]}。考虑到视频每一帧F_i中的特征点在时间窗口内的信息，采用meanshift算法对当前帧的轨迹集合TS_i进行聚类，被聚为同一类的轨迹代表了轨迹上的特征点在当前帧F_i及其窗口内的空间位置均具有较高的相似性，对应地将同类轨迹在当前帧F_i时的特征点归为同一类目标，从而在每一帧中完成了特征点的聚类。限定meanshift聚类时的窗口大小为w，即对于每一帧F_i只考虑经过该帧的轨迹在[F_i-w,F_i+w]内的部分,采用meanshift进行轨迹聚类的迭代过程如式(6)所示：

算法2    meanshift轨迹聚类

输入    轨迹集合trajSetIn收敛阈值e，X方向带宽b_x，Y 方向带宽b_y；

输出    轨迹集合trajSetOut。

1)while丨trajSetIn丨 ≠0

2)    从trajSetIn中随机选择一条未被聚类的轨迹kTraj作为聚类中心轨迹的初值

3)    while true

4)      lastKTraj←kTraj

5)      取X、Y方向的带宽分别为b_x、 b_y，按式(6)计算本次迭代的聚类中心轨迹kTraj

6)      计算kTraj与lastKTraj在X、Y方向上的平均距离Δx、Δy

7)      ifΔx<e andΔy<e

8)        在X、Y方向上离kTraj距离小于b_x,b_y的轨迹集合trajCluster标记为新的类

9)        trajSetIn ← trajSetIn—trajCluster

10)         trajSetOut ← trajSetOut ∪ trajCluster

11)         break

12)      end if

13)    end while

14)end while

采用meanshift进行轨迹聚类在每一帧解决了特征点的稳定聚类问题，而目标的运动跟踪则需要在相邻2帧对聚类结果进行匹配，即对于当前帧中的每一类找出上一帧中的匹配类。定义CC、LC分别表示当前帧和上一帧特征点聚类结果，f(CC_i,LC_j)代表当前帧聚类结果中第i类与上一帧聚类结果中第j类之间的相似度，则对于当前帧中的每一类CC_i，上述匹配问题在于寻找k使得f(CC_i,LC_k)取得最大值，为了保证匹配结果的置信度，限定最大相似度不小于f_min。相似度、k与f_min的定义分别如式(8) ~(10)所示，其中α为最小公共系数。

在目标的运动跟踪过程中，特别是在多个目标从相近位置分开以及目标从视频画面中出现和离开阶段，会出现当前帧的多个类匹配到前一帧的同一类的情况。针对这种情况，对于前一帧中的每一类，运动跟踪算法在当前帧中选择与之相似度最高的类进行最优匹配，同时解除其他非最优匹配类与前一帧中该类的匹配关系。定义M(CC_i)表示在前一帧中与当前帧第i类所匹配的类，M （LC_j） 表示在当前帧中与前一帧第j类所匹配的类，则上述寻找最优匹配类的过程可用式(11)所描述，满足式(11)的M （LC_j） 即为在当前帧中与前一帧第j类的最优匹配类。

由于在视频流中的出现新的目标时会使最大相似度为0，同时在上述最优匹配的过程中当前帧内非最优匹配的类没有完成匹配。在这种情况时，运动跟踪匹配算法将该特征点类标记为独立类。至此，当前帧中的所有的类完成了与前一帧的匹配过程，将该匹配算法连续运用到每一帧中即可实现完整的目标运动跟踪。运动跟踪匹配算法的整体结构如算法3。

算法3    运动跟踪匹配算法

符号：    N= {N₁,N₂,…,N_n} ，

N_i：特征点类i中被匹配的特征点个数。

输入    上一帧特征点类集合lastSet，当前帧特征点类集合currentSet，最小公共系数α；

输出    当前帧聚类集合currentSet。

1)初始化N_i为0

2)for all CC in currentSet

3)    for all LC in lastSet

4)      n ← 丨CC∩LC丨

5)      ifn>α 丨CC丨andn>N_LC

6)        更新特征点类LC的匹配类为CC

7)      end if

8)    end for

9)end for

10)for all CC in currentSet

11)    ifN_CC=0

12)      将特征点类CC标记为独立类

13)    end if

14)end for

实验选取物美超市内的实际监控视频作为数据集以验证上述算法的有效性，该数据集涵盖超市入口、生鲜区域、收银台等3种典型场景，视频分辨率为352像素×288像素。

KLT特征点提取的结果如图 1所示，视频中每帧提取的特征点个数为2 000，任意2个特征点之间的最小距离为5像素。从图 1中可以看出，特征点不仅分布在运动的顾客身上，也广泛的分布于纹理特征较为明显的背景之中。

图 1 KLT特征点提取Fig. 1 Detecting KLT feature points

图选项

经轨迹预处理之后的特征点分布情况如图 2所示，其中滤除背景点算法中最大连续静止帧数s取5帧，滤除短时点算法中权重系数λ取0.3，特征点在连续2帧间最大移动距离φ取5像素。从图 2可以看出，经过预处理，在KLT特征点提取阶段出现的背景特征点与短时特征点被很好的滤除，视频帧中特征点集中在运动目标身上，为下一步meanshift轨迹聚类提供了有效、稳定的运动轨迹。

图 2 特征点轨迹预处理Fig. 2 Preprocessing trajectories of feature points

图选项

采用meanshift进行轨迹聚类的结果如图 3所示，其中X方向带宽b_x取25像素，Y方向带宽b_y取60像素，窗口大小w取20帧，收敛阈值e取1像素。对比图 2与图 3可以看出，当前帧中的特征点被聚为2类，轨迹聚类利用当前帧特征点在前后时间窗口内的信息很好地解决了目标存在部分遮挡的问题。

图 3 meanshift轨迹聚类Fig. 3 Trajectory clustering by meanshift

图选项

图 4~7展示了目标运动跟踪部分的最终实验结果，其中最小公共系数α取0.33。从图中可以看出，运动跟踪匹配算法适用于超市入口、生鲜区域、收银台等多种具体场景，并能够在单人、多人复杂运动条件下保持良好的鲁棒性。

图 4 运动跟踪，超市入口，单人Fig. 4 Movement tracking： single customer at the entrance

图选项

图 5 运动跟踪，超市入口，多人Fig. 5 Movement tracking： multiple customers at the entrance

图选项

图 6 运动跟踪，生鲜区域，多人Fig. 6 Movement tracking： multiple customers at the fresh area

图选项

图 7 运动跟踪，收银台，多人Fig. 7 Movement tracking：multiple customers at the check stand

图选项

具体而言，如图 4所示，运动跟踪匹配算法能够完整地跟踪顾客从超市监控图像中从出现到离开的整个过程，亦能适用于顾客运动过程中出现的拐弯等复杂运动状态。从图 5中可以看到，在超市中同时出现多个运动的顾客时，运动跟踪算法能够同时跟踪相应目标。如图 6所示，在视频流中出现不同时长的顾客轨迹时，本算法可以正确地分析出不同轨迹的起始和终止时刻从而进行对应跟踪。分析图 7可知，对顾客的运动跟踪即使在顾客密集的场景中也能够完整的提取出其中运动顾客的轨迹。对比图 5~7可以看到，对顾客的运动跟踪能够普遍适用于超市入口、生鲜区域以及收银台等各种具体场景。

超市顾客运动跟踪是计算机视觉领域中目标跟踪的典型应用，在超市这种复杂环境下进行顾客的运动跟踪是亟待解决的应用难点。本文在KLT特征点轨迹提取的基础之上进行特征点轨迹的预处理，进而通过meanshift轨迹聚类分离出视频流每一帧中的每类特征点，最后通过运动轨迹匹配算法将每一帧中的特征点类与前一帧相匹配得到顾客的完整运动轨迹。实验结果表明，本方法能够在实际超市监控视频中做到顾客的运动跟踪，不仅适用于超市入口、生鲜区域、收银台等多种典型场景，也能在遮挡、复杂轨迹、多人异步运动等复杂情况下保持良好的鲁棒性。因此，本文所述顾客运动跟踪算法能够为超市这一供应链终端的后续应用，如智能拥塞控制、最优商品布局、购物推荐、自动预警等提供可靠的数据基石。