基于轨迹聚类的超市顾客运动跟踪

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150302.1106.010.html

基于轨迹聚类的超市顾客运动跟踪

王熙1，吴为2，钱沄涛1

(1.浙江大学 计算机科学与技术学院，浙江 杭州 310027； 2.浙江省网络系统及信息安全重点实验室，浙江 杭州 310006)

摘要：针对超市等复杂应用环境下的运动目标轨迹跟踪问题，将轨迹聚类运用于目标跟踪中，提出了一种超市顾客运动跟踪方法。该方法对Kanade-Lucas-Tomasi(KLT)算法提取并跟踪得到的特征点轨迹进行预处理，滤除背景和短时特征点以分离出运动目标所在区域的关键特征点；进而采用均值漂移(meanshift)算法进行轨迹聚类，解决了单帧静态特征点聚类时的目标遮挡问题；最后采用运动跟踪匹配算法对前后帧的特征点进行最优匹配，解决了目标出入视频区域以及具有复杂路线时的稳定跟踪问题，得到顾客的完整运动轨迹。实验结果表明，该方法能够在超市入口、生鲜区以及收银台等各种典型超市区域中完成顾客轨迹的运动跟踪，并对顾客部分遮挡、复杂运动轨迹以及异步运动等多种特殊情况具有较高的鲁棒性。

关键词：目标跟踪；特征匹配；轨迹聚类；运动分析

DOI:10.3969/j.issn.1673-4785.201401002

中图分类号：TP391.4 文献标志码：A

收稿日期：2014-01-13. 网络出版日期：2015-03-02.

基金项目：国家科技支撑计划资助项目(2011BAD24B03)浙江省网络系统及信息安全重点实验室开放基金资助项目(2013002).

作者简介：

中文引用格式：王熙，吴为，钱沄涛. 基于轨迹聚类的超市顾客运动跟踪[J]. 智能系统学报， 2015, 10(2): 187-192.

英文引用格式：WANG Xi， WU Wei， QIAN Yuntao. Trajectory clustering based customer movement tracking in a supermarket[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 187-192.

Trajectory clustering based customer movement tracking in a supermarket

WANG Xi1， WU Wei2， QIAN Yuntao1

(1. College of Computer Science, Zhejiang University, Hangzhou 310027, China; 2. Zhejiang Key Laboratory of Network Technology and Information Security, Hangzhou 310006, China)

Abstract：Tracking the moving targets in complex scenarios such as supermarkets can be a challenging task. This paper proposes a method to track moving customers in a supermarket by clustering the trajectories of the targets. In this method, all the background and short-time feature points are removed in the preprocessing step in order to refine the feature points, which were detected and tracked by the Kanade-Lucas-Tomasi (KLT) algorithm. The occlusion problem of single frame static feature point clustering is solved by applying the mean shift algorithm to the trajectories of moving objects. Finally, the full trajectories of moving customers are generated by the matching algorithm of movement tracking. The algorithm tackles the stable tracking problem by optimally matching the feature point clusters between successive frames when the target goes across the boundary of the video region or has a complex trajectory. Experimental results showed that the proposed method can successfully track the trajectories of customers in various typical regions of the supermarket such as entrance, fresh area and checkout stand. This method is robust under partial occlusion, complex trajectory and asynchronous moving.

Keywords：object tracking; feature matching; trajectory clustering; feature point refining

通信作者：钱沄涛. E-mail：ytqian@zju.edu.cn.

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

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

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

1特征点轨迹提取及预处理

1.1特征点轨迹提取

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

(1)

定义d=(Δx,Δy)为点X(x,y)的偏移量。KLT匹配的过程即为寻找d使得式(2)中ε达到最小值。

(2)

式中：I、J表示2帧图像，W为特征窗口，ω(X)为加权函数。

1.2 特征点轨迹预处理

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

1.2.1滤除背景特征点

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

(3)

式中：L为轨迹连续静止帧数，d(FPi,FPi+1)表示特征点FP在第i帧与第i+1帧之间移动的距离，s表示特征点最大连续静止帧数。滤除背景特征点的过程即为在KLT特征点的跟踪结果中遍历每一条特征点轨迹，若满足式(3)，则将该轨迹标记为无效轨迹。滤除背景特征点的流程如算法1所示。

算法1 滤除背景特征点

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

输出轨迹集合trajSet。

1)for all traj in trajSet

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

3) if L>s

5) end if

6)end for

1.2.2滤除短时特征点

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

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

(4)

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

(5)

式中：L为轨迹长度，d(FPi,FPi+1)表示特征点FP在第i帧与第i+1帧之间移动的距离，φ表示特征点在连续2帧之间最多移动的距离，若连续2帧之间移动距离超过φ，则认为是一条新的轨迹。滤除短时特征点的算法与滤除背景特征点算法类似，在此不再复述。

2轨迹聚类

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

(6)

(7)

算法2meanshift轨迹聚类

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

输出轨迹集合trajSetOut。

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

3)while true

4)lastKTraj←kTraj

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

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

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

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

9)trajSetIn←trajSetIn—trajCluster

10)trajSetOut←trajSetOut∪trajCluster

11)break

12)end if

13)end while

14)end while

3目标运动跟踪

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

(8)

k:∀LCj∈LC,f(CCi,LCk)≥f(CCi,LCj)

(9)

(10)

∀CCi,M(CCi)=LCj,

(11)

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

算法3运动跟踪匹配算法

Ni:特征点类i中被匹配的特征点个数。

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

输出当前帧聚类集合currentSet。

1)初始化Ni为0

2)for all CC in currentSet

3)for all LC in lastSet

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

7)end if

8)end for

9)end for

10)for all CC in currentSet

11)if NCC=0

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

13)end if

14)end for

4实验结果与分析

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

KLT特征点提取的结果如图1所示，视频中每帧提取的特征点个数为2000，任意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方向带宽bx取25像素，Y方向带宽by取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可以看到，对顾客的运动跟踪能够普遍适用于超市入口、生鲜区域以及收银台等各种具体场景。

5结束语

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

参考文献:

[1]YILMAZ A, JAVED O, SHAH M. Object tracking: a survey[J]. ACM Computing Surveys (CSUR), 2006, 38(4): 1-45.

[2]BROIDA T J, CHELLAPPA R. Estimation of object motion parameters from noisy images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986(1): 90-99.

[3]万琴,王耀南 .基于卡尔曼滤波器的运动目标检测与跟踪[J]. 湖南大学学报：自然科学版, 2007, 34(3): 36-40.

WAN Qin, WANG Yaonan. Moving objects detecting and tracking based on Kalman filter[J]. Journal of Hunan University: Natural Sciences, 2007, 34(3): 36-40.

[4]VEENMAN C J, REINDERS M J, BACKER E. Resolving motion correspondence for densely moving points[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(1): 54-72.

[5]BERTALM O M, SAPIRO G, RANDALL G. Morphing active contours[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(7): 733-737.

[6]SATO K, AGGARWAL J K. Temporal spatio-velocity transform and its application to tracking and interaction[J]. Computer Vision and Image Understanding, 2004, 96(2): 100-128.

[7]COMANICIU D, RAMESH V, MEER P. Kernel-based object tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577.

[8]ZHOU H, YUAN Y, SHI C. Object tracking using SIFT features and mean shift[J]. Computer Vision and Image Understanding, 2009, 113(3): 345-352.

[9]李培华.一种改进的MeanShift跟踪算法[J]. 自动化学报, 2007, 33(4): 347-354.

LI Peihua. An improved Meanshift algorithm for object tacking[J]. Acta Automatica Sinica, 2007, 33(4): 347-354.

[10]BENFOLD B, REID I. Stable multi-target tracking in real-time surveillance video[C]//2011 IEEE Conference on Proceedings of the Computer Vision and Pattern Recognition (CVPR). Oxford, UK, 2011: 3457-3464.

[11]ZACH C, GALLUP D, FRAHM J-M. Fast gain-adaptive KLT tracking on the GPU[C]//08 IEEE Computer Society Conference on proceedings of the Computer Vision and Pattern Recognition Workshops. [S.l.], USA, 2008: 1-7.

[12]SHI J, TOMASI C. Good features to track[C]//1994 IEEE Computer Society Conference on proceedings of the Computer Vision and Pattern Recognition. Seattle, WA, USA, 1994: 593-600.

[13]HASHEMZADEH M, PAN G, WANG Y, et al. Combining velocity and location-specific spatial clues in trajectories for counting crowded moving objects[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2012, 27(2):1-31.

[14]LUCAS B D, KANADE T. An iterative image registration technique with an application to stereo vision[C]//Proceedings of the IJCAI. Vancouver, Canada, 1981: 674-679.

[15]TOMASI C, KANADE T. Detection and tracking of point features[M]. [S.l.]：Carnegie Mellon Univ, 1991: 1-32.

[16]BIRCHFIELD S. KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[EB/OL]. [2013-11-21]. http://www.ces.clemson.edu/～stb/klt/ .

[17]SUGIMURA D, KITANI K M, OKABE T, et al. Using individuality to track individuals: clustering individual trajectories in crowds using local appearance and frequency trait[C]//2009 IEEE 12th International Conference on Proceedings of the Computer Vision. Kyoto, Japan, 2009: 1467-1474.

[18]BROX T, MALIK J. Object segmentation by long term analysis of point trajectories[M]. Springer. 2010: 282-295.

王熙，男，1989年生，硕士研究生，主要研究方向为计算机视觉和数据挖掘。

吴为，1961年生，高级工程师，主要研究方向为计算机应用，发表学术论文10余篇。

钱沄涛，1968年生，教授，博士生导师，中国电子学会高级会员，信号处理分会委员；中国计算机学会人工智能与模式识别专委会委员，中国计算机学会模糊逻辑与多值逻辑专委会委员；中国航空学会信息融合分会委员；中国人工智能学会智能CAD与数字艺术专委会委员。主要研究方向为模式识别、信号处理、机器学习，发表学术论文90余篇。