机器学习：基于轨迹聚类的超市顾客运动跟踪

第10卷第2期 智能系统学报 Vol.10 No.2 2015年4月 CAAI Transactions on Intelligent Systems Apr.2015 D0:10.3969/j.issn.1673-4785.201401002 网s络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20150302.1106.010.html 基于轨迹聚类的超市顾客运动跟踪 王熙1，吴为2，钱法涛 (1.浙江大学计算机科学与技术学院，浙江杭州310027；2.浙江省网络系统及信息安全重点实验室，浙江杭州310006) 摘要：针对超市等复杂应用环境下的运动目标轨迹跟踪问题，将轨迹聚类运用于目标跟踪中，提出了一种超市顾 客运动跟踪方法。该方法对Kanade--Lucas-Tomasi(KLT)算法提取并跟踪得到的特征点轨迹进行预处理，滤除背景和 短时特征点以分离出运动目标所在区域的关键特征点：进而采用均值漂移(meanshift)算法进行轨迹聚类，解决了单 帧静态特征点聚类时的目标遮挡问题：最后采用运动跟踪匹配算法对前后帧的特征点进行最优匹配，解决了目标出 入视频区域以及具有复杂路线时的稳定跟踪问题，得到顾客的完整运动轨迹。实验结果表明，该方法能够在超市入 口、生鲜区以及收银台等各种典型超市区域中完成顾客轨迹的运动跟踪，并对顾客部分遮挡、复杂运动轨迹以及异 步运动等多种特殊情况具有较高的鲁棒性。 关键词：目标跟踪：特征匹配：轨迹聚类；运动分析 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2015)02-0187-06 中文引用格式：王熙，吴为，钱沅涛.基于轨迹聚类的超市顾客运动跟踪[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 Xi',WU Wei2,QIAN Yuntao' (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 re- fine the feature points,which were detected and tracked by the Kanade-Lucas-Tomasi (KLT)algorithm.The occlu- sion problem of single frame static feature point clustering is solved by applying the mean shift algorithm to the traj- ectories 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 收稿日期：2014-01-13.网络出版日期：2015-03-02. 在计算机视觉领域的各种研究和应用中，目标跟 基金项目：国家科技支撑计划资助项目(201BA2403)浙江省网络系踪一直是一项重要而又兼具挑战性的技术。目标跟 统及信息安全重点实验室开放基金资助项目(2013002). 通信作者：钱沄涛.E-mail:ytqian(@u.cdu.cm. 踪的主要任务在于对视频流中的运动信息进行分析

第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０１００２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０３０２．１１０６．０１０．ｈｔｍｌ 基于轨迹聚类的超市顾客运动跟踪 王熙１ ，吴为２ ，钱沄涛１ （１．浙江大学 计算机科学与技术学院，浙江 杭州 ３１００２７； ２．浙江省网络系统及信息安全重点实验室，浙江 杭州 ３１０００６） 摘 要：针对超市等复杂应用环境下的运动目标轨迹跟踪问题，将轨迹聚类运用于目标跟踪中，提出了一种超市顾 客运动跟踪方法。 该方法对 Ｋａｎａｄｅ⁃Ｌｕｃａｓ⁃Ｔｏｍａｓｉ（ＫＬＴ）算法提取并跟踪得到的特征点轨迹进行预处理，滤除背景和 短时特征点以分离出运动目标所在区域的关键特征点；进而采用均值漂移（ｍｅａｎｓｈｉｆｔ）算法进行轨迹聚类，解决了单 帧静态特征点聚类时的目标遮挡问题；最后采用运动跟踪匹配算法对前后帧的特征点进行最优匹配，解决了目标出 入视频区域以及具有复杂路线时的稳定跟踪问题，得到顾客的完整运动轨迹。 实验结果表明，该方法能够在超市入 口、生鲜区以及收银台等各种典型超市区域中完成顾客轨迹的运动跟踪，并对顾客部分遮挡、复杂运动轨迹以及异 步运动等多种特殊情况具有较高的鲁棒性。 关键词：目标跟踪；特征匹配；轨迹聚类；运动分析 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０１８７⁃０６ 中文引用格式：王熙，吴为，钱沄涛． 基于轨迹聚类的超市顾客运动跟踪［Ｊ］． 智能系统学报， ２０１５， １０（２）： １８７⁃１９２． 英文引用格式：ＷＡＮＧ Ｘｉ， ＷＵ Ｗｅｉ， ＱＩＡＮ Ｙｕｎｔａｏ． Ｔｒａｊｅｃｔｏｒｙ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｃｕｓｔｏｍｅｒ ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ ｉｎ ａ ｓｕｐｅｒｍａｒｋｅｔ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： １８７⁃１９２． Ｔｒａｊｅｃｔｏｒｙ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｃｕｓｔｏｍｅｒ ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ ｉｎ ａ ｓｕｐｅｒｍａｒｋｅｔ ＷＡＮＧ Ｘｉ １ ， ＷＵ Ｗｅｉ ２ ， ＱＩＡＮ Ｙｕｎｔａｏ １ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｎｇｚｈｏｕ ３１００２７， Ｃｈｉｎａ； ２． Ｚｈｅｊｉａｎｇ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｎｅｔｗｏｒｋ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ， Ｈａｎｇｚｈｏｕ ３１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｒａｃｋｉｎｇ ｔｈｅ ｍｏｖｉｎｇ ｔａｒｇｅｔｓ ｉｎ ｃｏｍｐｌｅｘ ｓｃｅｎａｒｉｏｓ ｓｕｃｈ ａｓ ｓｕｐｅｒｍａｒｋｅｔｓ ｃａｎ ｂｅ ａ ｃｈａｌｌｅｎｇｉｎｇ ｔａｓｋ． Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｍｅｔｈｏｄ ｔｏ ｔｒａｃｋ ｍｏｖｉｎｇ ｃｕｓｔｏｍｅｒｓ ｉｎ ａ ｓｕｐｅｒｍａｒｋｅｔ ｂｙ ｃｌｕｓｔｅｒｉｎｇ ｔｈｅ ｔｒａｊｅｃｔｏｒｉｅｓ ｏｆ ｔｈｅ ｔａｒｇｅｔｓ． Ｉｎ ｔｈｉｓ ｍｅｔｈｏｄ， ａｌｌ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ ａｎｄ ｓｈｏｒｔ⁃ｔｉｍｅ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ ａｒｅ ｒｅｍｏｖｅｄ ｉｎ ｔｈｅ ｐｒｅｐｒｏｃｅｓｓｉｎｇ ｓｔｅｐ ｉｎ ｏｒｄｅｒ ｔｏ ｒｅ⁃ ｆｉｎｅ ｔｈｅ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ， ｗｈｉｃｈ ｗｅｒｅ ｄｅｔｅｃｔｅｄ ａｎｄ ｔｒａｃｋｅｄ ｂｙ ｔｈｅ Ｋａｎａｄｅ⁃Ｌｕｃａｓ⁃Ｔｏｍａｓｉ （ＫＬＴ） ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｏｃｃｌｕ⁃ ｓｉｏｎ ｐｒｏｂｌｅｍ ｏｆ ｓｉｎｇｌｅ ｆｒａｍｅ ｓｔａｔｉｃ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｃｌｕｓｔｅｒｉｎｇ ｉｓ ｓｏｌｖｅｄ ｂｙ ａｐｐｌｙｉｎｇ ｔｈｅ ｍｅａｎ ｓｈｉｆｔ ａｌｇｏｒｉｔｈｍ ｔｏ ｔｈｅ ｔｒａｊ⁃ ｅｃｔｏｒｉｅｓ ｏｆ ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ． Ｆｉｎａｌｌｙ， ｔｈｅ ｆｕｌｌ ｔｒａｊｅｃｔｏｒｉｅｓ ｏｆ ｍｏｖｉｎｇ ｃｕｓｔｏｍｅｒｓ ａｒｅ ｇｅｎｅｒａｔｅｄ ｂｙ ｔｈｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｔａｃｋｌｅｓ ｔｈｅ ｓｔａｂｌｅ ｔｒａｃｋｉｎｇ ｐｒｏｂｌｅｍ ｂｙ ｏｐｔｉｍａｌｌｙ ｍａｔｃｈｉｎｇ ｔｈｅ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｃｌｕｓｔｅｒｓ ｂｅｔｗｅｅｎ ｓｕｃｃｅｓｓｉｖｅ ｆｒａｍｅｓ ｗｈｅｎ ｔｈｅ ｔａｒｇｅｔ ｇｏｅｓ ａｃｒｏｓｓ ｔｈｅ ｂｏｕｎｄａｒｙ ｏｆ ｔｈｅ ｖｉｄｅｏ ｒｅｇｉｏｎ ｏｒ ｈａｓ ａ ｃｏｍｐｌｅｘ ｔｒａｊｅｃｔｏｒｙ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｃａｎ ｓｕｃｃｅｓｓｆｕｌｌｙ ｔｒａｃｋ ｔｈｅ ｔｒａｊｅｃｔｏｒｉｅｓ ｏｆ ｃｕｓｔｏｍｅｒｓ ｉｎ ｖａｒｉｏｕｓ ｔｙｐｉｃａｌ ｒｅｇｉｏｎｓ ｏｆ ｔｈｅ ｓｕｐｅｒｍａｒｋｅｔ ｓｕｃｈ ａｓ ｅｎｔｒａｎｃｅ， ｆｒｅｓｈ ａｒｅａ ａｎｄ ｃｈｅｃｋｏｕｔ ｓｔａｎｄ． Ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｒｏｂｕｓｔ ｕｎｄｅｒ ｐａｒｔｉａｌ ｏｃｃｌｕｓｉｏｎ， ｃｏｍｐｌｅｘ ｔｒａｊｅｃｔｏｒｙ ａｎｄ ａｓｙｎｃｈｒｏｎｏｕｓ ｍｏｖｉｎｇ． Ｋｅｙｗｏｒｄｓ：ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ； ｆｅａｔｕｒｅ ｍａｔｃｈｉｎｇ； ｔｒａｊｅｃｔｏｒｙ ｃｌｕｓｔｅｒｉｎｇ； ｆｅａｔｕｒｅ ｐｏｉｎｔ ｒｅｆｉｎｉｎｇ 收稿日期：２０１４⁃０１⁃１３． 网络出版日期：２０１５⁃０３⁃０２． 基金项目：国家科技支撑计划资助项目（２０１１ＢＡＤ２４Ｂ０３）浙江省网络系 统及信息安全重点实验室开放基金资助项目（２０１３００２）． 通信作者：钱沄涛． Ｅ⁃ｍａｉｌ：ｙｔｑｉａｎ＠ ｚｊｕ．ｅｄｕ．ｃｎ． 在计算机视觉领域的各种研究和应用中，目标跟 踪一直是一项重要而又兼具挑战性的技术。 目标跟 踪的主要任务在于对视频流中的运动信息进行分析

·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

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

第2期 王熙，等：基于轨迹聚类的超市顾客运动跟踪 ·189· 1.2.2滤除短时特征，点 式中：b,、b,分别代表x、y方向上的带宽，D(T:, 短时特征点相对于被稳定跟踪的特征点，其表 T)、D(T,T)分别表示T:与T在x和y方向上 现为连续运动帧数过短。由于在超市不同位置的具 的均方误差。采用meanshift进行轨迹聚类的流程 体场景以及摄像机角度、焦距等不尽相同，故不能直 如算法2所示： 接参照滤除背景特征点中的方法为特征点的连续运 算法2 meanshif近轨迹聚类 动帧数取固定的阈值，而应当根据当前视频中轨迹 输入轨迹集合trajSetIn收敛阈值e,X方向带 长度的分布情况选取更为合理的阈值。 宽b,Y方向带宽b,; 定义L:为KLT跟踪结果中第i条轨迹的长度， 输出轨迹集合trajSetOut。. 则最小连续运动帧数m如式(4)所示，其中入为权 1)while trajSetIn≠0 重系数。 2)从trajSetIn中随机选择一条未被聚类的轨 m=入 (4) 迹kTra作为聚类中心轨迹的初值 ni=】 3)while true 短时特征点即为满足式(5)的特征点， 4) lastKTraj←kTraj 3L∈(0，m),i>0, 5)取X、Y方向的带宽分别为b.、b,,按式 Vj∈[i,i+L-1],d(FP:,FPt1)∈[0，p] (6)计算本次迭代的聚类中心轨迹kTra (5) 6)计算kTraj与lastKTraj在X、Y方向上的 式中：L为轨迹长度，d(FP:,FP:+1)表示特征点FP 平均距离△x、△y 在第i帧与第i+1帧之间移动的距离，p表示特征 7) ifAx<eand△y<e 点在连续2帧之间最多移动的距离，若连续2帧之 8) 在X、Y方向上离kTraj距离小于b., 间移动距离超过”，则认为是一条新的轨迹。滤除 b,的轨迹集合trajCluster标记为新的类 短时特征点的算法与滤除背景特征点算法类似，在 9) trajSetIn←-trajSetIn一trajCluster 此不再复述。 10) trajSetOut +trajSetOut U trajCluster 2轨迹聚类 11) break 12) end if 在特征点轨迹提取和预处理的基础之上，本文 采用轨迹聚类的方法在每一帧中检测出运动目 13)end while 标B,5,7。考虑到视频每一帧F,中的特征点在时 14)end while 间窗口内的信息，采用meanshift算法对当前帧的轨 目标运动跟踪 迹集合TS:进行聚类，被聚为同一类的轨迹代表了 轨迹上的特征点在当前帧F:及其窗口内的空间位 采用meanshift进行轨迹聚类在每一帧解决了 置均具有较高的相似性，对应地将同类轨迹在当前 特征点的稳定聚类问题，而目标的运动跟踪则需要 帧F:时的特征点归为同一类目标，从而在每一帧中 在相邻2帧对聚类结果进行匹配，即对于当前帧中 完成了特征点的聚类。限定meanshift聚类时的窗 的每一类找出上一帧中的匹配类。定义CC、LC分 口大小为心，即对于每一帧F,只考虑经过该帧的轨 别表示当前帧和上一帧特征点聚类结果，f(CC:, 迹在[F:-e,Fw]内的部分，采用meanshift进行轨 LC:)代表当前帧聚类结果中第i类与上一帧聚类结 迹聚类的迭代过程如式(6)所示： 果中第类之间的相似度，则对于当前帧中的每一 类CC,,上述匹配问题在于寻找k使得f(CC:,LC:) i= ∑k(T,T)T (6 取得最大值，为了保证匹配结果的置信度，限定最大 ∑k(T,T) 相似度不小于fm。相似度、k与f的定义分别如 式中：T表示每步迭代产生的新的轨迹聚类中心， 式(8)~(10)所示，其中α为最小公共系数。 T表示当前轨迹聚类中心，k(T,T)表示每条带宽 f(CC,LC,)=CC n LC; (8) 范围内的轨迹与当前轨迹聚类中心的相关系数，由 k:HLC∈LC,f(CC:,LC4)≥f(CC,LC;)(9) 式(7)决定。 fuin =aCC (10) D:(T:,T)D(T:.T) k(Ti,T)=exp(- 在目标的运动跟踪过程中，特别是在多个目标从 2b月 2b2 相近位置分开以及目标从视频画面中出现和离开阶 7) 段，会出现当前帧的多个类匹配到前一帧的同一类的

１．２．２ 滤除短时特征点 短时特征点相对于被稳定跟踪的特征点，其表 现为连续运动帧数过短。 由于在超市不同位置的具 体场景以及摄像机角度、焦距等不尽相同，故不能直 接参照滤除背景特征点中的方法为特征点的连续运 动帧数取固定的阈值，而应当根据当前视频中轨迹 长度的分布情况选取更为合理的阈值。 定义 Ｌｉ 为 ＫＬＴ 跟踪结果中第 ｉ 条轨迹的长度， 则最小连续运动帧数 ｍ 如式（４）所示，其中 λ 为权 重系数。 ｍ ＝ λ １ ｎ ∑ ｎ ｉ ＝ １ Ｌｉ （４） 短时特征点即为满足式（５）的特征点， ∃Ｌ ∈ （０，ｍ），ｉ ＞ ０， ∀ｊ ∈ ［ｉ，ｉ ＋ Ｌ － １］，ｄ（ＦＰｉ，ＦＰｉ＋１ ） ∈ [０，φ] （５） 式中： Ｌ 为轨迹长度， ｄ（ＦＰｉ，ＦＰｉ＋１ ） 表示特征点 ＦＰ 在第 ｉ 帧与第 ｉ ＋ １ 帧之间移动的距离， φ 表示特征 点在连续 ２ 帧之间最多移动的距离，若连续 ２ 帧之 间移动距离超过 φ ，则认为是一条新的轨迹。 滤除 短时特征点的算法与滤除背景特征点算法类似，在 此不再复述。 ２ 轨迹聚类 在特征点轨迹提取和预处理的基础之上，本文 采用轨迹聚类的方法在每一帧中检测出运动目 标［１３， １５， １７］ 。 考虑到视频每一帧 Ｆｉ 中的特征点在时 间窗口内的信息，采用 ｍｅａｎｓｈｉｆｔ 算法对当前帧的轨 迹集合 ＴＳｉ 进行聚类，被聚为同一类的轨迹代表了 轨迹上的特征点在当前帧 Ｆｉ 及其窗口内的空间位 置均具有较高的相似性，对应地将同类轨迹在当前 帧 Ｆｉ 时的特征点归为同一类目标，从而在每一帧中 完成了特征点的聚类。 限定 ｍｅａｎｓｈｉｆｔ 聚类时的窗 口大小为 ｗ ，即对于每一帧 Ｆｉ 只考虑经过该帧的轨 迹在 ［Ｆｉ－ｗ ，Ｆｉ＋ｗ ］ 内的部分，采用 ｍｅａｎｓｈｉｆｔ 进行轨 迹聚类的迭代过程如式（６）所示： Ｔ ～ ｋ ＝ ∑ｋ（Ｔｉ，Ｔｋ）Ｔｉ ∑ｋ（Ｔｉ，Ｔｋ） （６） 式中： Ｔ ～ ｋ 表示每步迭代产生的新的轨迹聚类中心， Ｔｋ 表示当前轨迹聚类中心， ｋ（Ｔｉ，Ｔｋ） 表示每条带宽 范围内的轨迹与当前轨迹聚类中心的相关系数，由 式（７）决定。 ｋ（Ｔｉ，Ｔｋ） ＝ ｅｘｐ（ － Ｄ ２ ｘ（Ｔｉ，Ｔｋ） ２ｂ ２ ｘ － Ｄ ２ ｙ（Ｔｉ，Ｔｋ） ２ｂ ２ ｙ ） （７） 式中： ｂｘ 、 ｂｙ 分别代表 ｘ 、 ｙ 方向上的带宽， Ｄ ２ ｘ（Ｔｉ， Ｔｋ） 、 Ｄ ２ ｙ（Ｔｉ，Ｔｋ） 分别表示 Ｔｉ 与 Ｔｋ 在 ｘ 和 ｙ 方向上 的均方误差。 采用 ｍｅａｎｓｈｉｆｔ 进行轨迹聚类的流程 如算法 ２ 所示： 算法 ２ ｍｅａｎｓｈｉｆｔ 轨迹聚类 输入 轨迹集合 ｔｒａｊＳｅｔＩｎ 收敛阈值 ｅ，Ｘ 方向带 宽 ｂｘ，Ｙ 方向带宽 ｂｙ； 输出 轨迹集合 ｔｒａｊＳｅｔＯｕｔ。 １）ｗｈｉｌｅ ｔｒａｊＳｅｔＩｎ ≠ ０ ２） 从 ｔｒａｊＳｅｔＩｎ 中随机选择一条未被聚类的轨 迹 ｋＴｒａｊ 作为聚类中心轨迹的初值 ３） ｗｈｉｌｅ ｔｒｕｅ ４） ｌａｓｔＫＴｒａｊ ← ｋＴｒａｊ ５） 取 Ｘ、Ｙ 方向的带宽分别为 ｂｘ 、 ｂｙ ，按式 （６）计算本次迭代的聚类中心轨迹 ｋＴｒａｊ ６） 计算 ｋＴｒａｊ 与 ｌａｓｔＫＴｒａｊ 在 Ｘ、Ｙ 方向上的 平均距离 Δｘ 、 Δｙ ７） ｉｆ Δｘ ＜ ｅ ａｎｄ Δｙ ＜ ｅ ８） 在 Ｘ、Ｙ 方向上离 ｋＴｒａｊ 距离小于 ｂｘ ， ｂｙ 的轨迹集合 ｔｒａｊＣｌｕｓｔｅｒ 标记为新的类 ９） ｔｒａｊＳｅｔＩｎ ← ｔｒａｊＳｅｔＩｎ—ｔｒａｊＣｌｕｓｔｅｒ １０） ｔｒａｊＳｅｔＯｕｔ ← ｔｒａｊＳｅｔＯｕｔ ∪ ｔｒａｊＣｌｕｓｔｅｒ １１） ｂｒｅａｋ １２） ｅｎｄ ｉｆ １３） ｅｎｄ ｗｈｉｌｅ １４）ｅｎｄ ｗｈｉｌｅ ３ 目标运动跟踪 采用 ｍｅａｎｓｈｉｆｔ 进行轨迹聚类在每一帧解决了 特征点的稳定聚类问题，而目标的运动跟踪则需要 在相邻 ２ 帧对聚类结果进行匹配，即对于当前帧中 的每一类找出上一帧中的匹配类。 定义 ＣＣ 、 ＬＣ 分 别表示当前帧和上一帧特征点聚类结果， ｆ（ＣＣｉ， ＬＣｊ） 代表当前帧聚类结果中第 ｉ 类与上一帧聚类结 果中第 ｊ 类之间的相似度，则对于当前帧中的每一 类 ＣＣｉ ，上述匹配问题在于寻找 ｋ 使得 ｆ（ＣＣｉ，ＬＣｋ） 取得最大值，为了保证匹配结果的置信度，限定最大 相似度不小于 ｆｍｉｎ 。 相似度、 ｋ 与 ｆｍｉｎ 的定义分别如 式（８） ～ （１０）所示，其中 α 为最小公共系数。 ｆ（ＣＣｉ，ＬＣｊ） ＝ ＣＣｉ ∩ ＬＣｊ （８） ｋ：∀ＬＣｊ ∈ ＬＣ，ｆ（ＣＣｉ，ＬＣｋ） ≥ ｆ（ＣＣｉ，ＬＣｊ） （９） ｆｍｉｎ ＝ α ＣＣｉ （１０） 在目标的运动跟踪过程中，特别是在多个目标从 相近位置分开以及目标从视频画面中出现和离开阶 段，会出现当前帧的多个类匹配到前一帧的同一类的 第 ２ 期 王熙，等：基于轨迹聚类的超市顾客运动跟踪 ·１８９·

·190· 智能系统学报 第10卷 情况。针对这种情况，对于前一帧中的每一类，运动 的最小距离为5像素。从图1中可以看出，特征点 跟踪算法在当前帧中选择与之相似度最高的类进行 不仅分布在运动的顾客身上，也广泛的分布于纹理 最优匹配，同时解除其他非最优匹配类与前一帧中该 特征较为明显的背景之中。 类的匹配关系。定义M(CC:)表示在前一帧中与当 前帧第i类所匹配的类，M(LC)表示在当前帧中与 前一帧第j类所匹配的类，则上述寻找最优匹配类的 过程可用式(11)所描述，满足式(11)的M(LC:)即 为在当前帧中与前一帧第类的最优匹配类。 VCC,M(CC)=LC;, f(M(LC),LC;)f(CC:,LC;) (11) 由于在视频流中的出现新的目标时会使最大相 图1KLT特征点提取 似度为0，同时在上述最优匹配的过程中当前帧内非 Fig.1 Detecting KLT feature points 最优匹配的类没有完成匹配。在这种情况时，运动跟 经轨迹预处理之后的特征点分布情况如图2所 踪匹配算法将该特征点类标记为独立类。至此，当前 示，其中滤除背景点算法中最大连续静止帧数s取5 帧中的所有的类完成了与前一帧的匹配过程，将该匹 帧，滤除短时点算法中权重系数入取0.3，特征点在 配算法连续运用到每一帧中即可实现完整的目标运 连续2帧间最大移动距离P取5像素。从图2可以 动跟踪。运动跟踪匹配算法的整体结构如算法3。 看出，经过预处理，在KLT特征点提取阶段出现的 算法3运动跟踪匹配算法 背景特征点与短时特征点被很好的滤除，视频帧中 符号：N={N1,N2,…,Nn}, 特征点集中在运动目标身上，为下一步meanshift轨 N:特征点类i中被匹配的特征点个数。 迹聚类提供了有效、稳定的运动轨迹。 输入上一帧特征点类集合lastSet,当前帧特 2913更5且85日里日0阅：957 征点类集合currentSet,.最小公共系数a; 输出当前帧聚类集合currentSet。 1)初始化N:为0 2)for all CC in currentSet 3)for all LC in lastSet 4) n←-|CC∩LC 5) if n a CC and n Nuc 图2特征点轨迹预处理 6) 更新特征点类LC的匹配类为CC Fig.2 Preprocessing trajectories of feature points 7) end if 采用meanshift进行轨迹聚类的结果如图3所 8)end for 示，其中X方向带宽b取25像素，Y方向带宽b,取 9)end for 60像素，窗口大小0取20帧，收敛阈值e取1像素。 10)for all CC in currentSet 对比图2与图3可以看出，当前帧中的特征点被聚为 11)if Ncc =0 2类，轨迹聚类利用当前帧特征，点在前后时间窗口内 12) 将特征点类CC标记为独立类 的信息很好地解决了目标存在部分遮挡的问题。 13)end if 2013年5的日里日第9：57 14)end for 4实验结果与分析 实验选取物美超市内的实际监控视频作为数据 集以验证上述算法的有效性，该数据集涵盖超市入 口、生鲜区域、收银台等3种典型场景，视频分辨率 为352像素×288像素。 图3 meanshift轨迹聚类 KLT特征点提取的结果如图1所示，视频中每 Fig.3 Trajectory clustering by meanshift 帧提取的特征，点个数为2000，任意2个特征点之间 图4~7展示了目标运动跟踪部分的最终实验

情况。 针对这种情况，对于前一帧中的每一类，运动 跟踪算法在当前帧中选择与之相似度最高的类进行 最优匹配，同时解除其他非最优匹配类与前一帧中该 类的匹配关系。 定义 Ｍ（ＣＣｉ） 表示在前一帧中与当 前帧第 ｉ 类所匹配的类， Ｍ ＬＣｊ ( ) 表示在当前帧中与 前一帧第 ｊ 类所匹配的类，则上述寻找最优匹配类的 过程可用式（１１）所描述，满足式（１１）的 Ｍ ＬＣｊ ( ) 即 为在当前帧中与前一帧第 ｊ 类的最优匹配类。 ∀ＣＣｉ，Ｍ（ＣＣｉ） ＝ ＬＣｊ， ｆ（Ｍ ＬＣｊ ( ) ，ＬＣｊ） ≥ ｆ（ＣＣｉ，ＬＣｊ） （１１） 由于在视频流中的出现新的目标时会使最大相 似度为 ０，同时在上述最优匹配的过程中当前帧内非 最优匹配的类没有完成匹配。 在这种情况时，运动跟 踪匹配算法将该特征点类标记为独立类。 至此，当前 帧中的所有的类完成了与前一帧的匹配过程，将该匹 配算法连续运用到每一帧中即可实现完整的目标运 动跟踪。 运动跟踪匹配算法的整体结构如算法 ３。 算法 ３ 运动跟踪匹配算法 符号： Ｎ ＝ Ｎ１ ，Ｎ２ ，…，Ｎｎ { } ， Ｎｉ ：特征点类 ｉ 中被匹配的特征点个数。 输入 上一帧特征点类集合 ｌａｓｔＳｅｔ，当前帧特 征点类集合 ｃｕｒｒｅｎｔＳｅｔ，最小公共系数 α ； 输出 当前帧聚类集合 ｃｕｒｒｅｎｔＳｅｔ。 １）初始化 Ｎｉ 为 ０ ２）ｆｏｒ ａｌｌ ＣＣ ｉｎ ｃｕｒｒｅｎｔＳｅｔ ３） ｆｏｒ ａｌｌ ＬＣ ｉｎ ｌａｓｔＳｅｔ ４） ｎ ← ＣＣ ∩ ＬＣ ５） ｉｆ ｎ ＞ α ＣＣ ａｎｄ ｎ ＞ ＮＬＣ ６） 更新特征点类 ＬＣ 的匹配类为 ＣＣ ７） ｅｎｄ ｉｆ ８） ｅｎｄ ｆｏｒ ９）ｅｎｄ ｆｏｒ １０）ｆｏｒ ａｌｌ ＣＣ ｉｎ ｃｕｒｒｅｎｔＳｅｔ １１） ｉｆ ＮＣＣ ＝ ０ １２） 将特征点类 ＣＣ 标记为独立类 １３） ｅｎｄ ｉｆ １４）ｅｎｄ ｆｏｒ ４ 实验结果与分析 实验选取物美超市内的实际监控视频作为数据 集以验证上述算法的有效性，该数据集涵盖超市入 口、生鲜区域、收银台等 ３ 种典型场景，视频分辨率 为 ３５２ 像素×２８８ 像素。 ＫＬＴ 特征点提取的结果如图 １ 所示，视频中每 帧提取的特征点个数为 ２ ０００，任意 ２ 个特征点之间 的最小距离为 ５ 像素。 从图 １ 中可以看出，特征点 不仅分布在运动的顾客身上，也广泛的分布于纹理 特征较为明显的背景之中。 图 １ ＫＬＴ 特征点提取 Ｆｉｇ．１ Ｄｅｔｅｃｔｉｎｇ ＫＬＴ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ 经轨迹预处理之后的特征点分布情况如图 ２ 所 示，其中滤除背景点算法中最大连续静止帧数 ｓ 取 ５ 帧，滤除短时点算法中权重系数 λ 取 ０．３，特征点在 连续 ２ 帧间最大移动距离 φ 取 ５ 像素。 从图 ２ 可以 看出，经过预处理，在 ＫＬＴ 特征点提取阶段出现的 背景特征点与短时特征点被很好的滤除，视频帧中 特征点集中在运动目标身上，为下一步 ｍｅａｎｓｈｉｆｔ 轨 迹聚类提供了有效、稳定的运动轨迹。 图 ２ 特征点轨迹预处理 Ｆｉｇ．２ Ｐｒｅｐｒｏｃｅｓｓｉｎｇ ｔｒａｊｅｃｔｏｒｉｅｓ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ 采用 ｍｅａｎｓｈｉｆｔ 进行轨迹聚类的结果如图 ３ 所 示，其中 Ｘ 方向带宽 ｂｘ 取 ２５ 像素， Ｙ 方向带宽 ｂｙ 取 ６０ 像素，窗口大小 ｗ 取 ２０ 帧，收敛阈值 ｅ 取 １ 像素。 对比图 ２ 与图 ３ 可以看出，当前帧中的特征点被聚为 ２ 类，轨迹聚类利用当前帧特征点在前后时间窗口内 的信息很好地解决了目标存在部分遮挡的问题。 图 ３ ｍｅａｎｓｈｉｆｔ 轨迹聚类 Ｆｉｇ．３ Ｔｒａｊｅｃｔｏｒｙ ｃｌｕｓｔｅｒｉｎｇ ｂｙ ｍｅａｎｓｈｉｆｔ 图 ４ ～ ７ 展示了目标运动跟踪部分的最终实验 ·１９０· 智 能 系 统 学 报 第 １０ 卷

第2期 王熙，等：基于轨迹聚类的超市顾客运动跟踪 ·191· 结果，其中最小公共系数α取0.33。从图中可以看 4 出，运动跟踪匹配算法适用于超市入口、生鲜区域、 收银台等多种具体场景，并能够在单人、多人复杂运 动条件下保持良好的鲁棒性。 图7运动跟踪，收银台，多人 Fig.7 Movement tracking:multiple customers at the check stand 具体而言，如图4所示，运动跟踪匹配算法能够 完整地跟踪顾客从超市监控图像中从出现到离开的 图4运动跟踪，超市入口，单人 整个过程，亦能适用于顾客运动过程中出现的拐弯 Fig.4 Movement tracking:single customer at the entrance 等复杂运动状态。从图5中可以看到，在超市中同 时出现多个运动的顾客时，运动跟踪算法能够同时 跟踪相应目标。如图6所示，在视频流中出现不同 时长的顾客轨迹时，本算法可以正确地分析出不同 轨迹的起始和终止时刻从而进行对应跟踪。分析图 7可知，对顾客的运动跟踪即使在顾客密集的场景 中也能够完整的提取出其中运动顾客的轨迹。对比 图5~7可以看到，对顾客的运动跟踪能够普遍适用 于超市入口、生鲜区域以及收银台等各种具体场景。 5结束语 超市顾客运动跟踪是计算机视觉领域中目标跟 踪的典型应用，在超市这种复杂环境下进行顾客的 图5运动跟踪，超市入口，多人 运动跟踪是亟待解决的应用难点。本文在KLT特 Fig.5 Movement tracking:multiple customers at the entrance 征点轨迹提取的基础之上进行特征点轨迹的预处 理，进而通过meanshift轨迹聚类分离出视频流每一 帧中的每类特征点，最后通过运动轨迹匹配算法将 每一帧中的特征点类与前一帧相匹配得到顾客的完 整运动轨迹。实验结果表明，本方法能够在实际超 市监控视频中做到顾客的运动跟踪，不仅适用于超 市入口、生鲜区域、收银台等多种典型场景，也能在 遮挡、复杂轨迹、多人异步运动等复杂情况下保持良 好的鲁棒性。因此，本文所述顾客运动跟踪算法能 够为超市这一供应链终端的后续应用，如智能拥塞 控制、最优商品布局、购物推荐、自动预警等提供可 靠的数据基石。 图6运动跟踪，生鲜区域，多人 参考文献： Fig.6 Movement tracking:multiple customers at the fresh area [1]YILMAZ A,JAVED O,SHAH M.Object tracking:a sur-

结果，其中最小公共系数 α 取 ０．３３。 从图中可以看 出，运动跟踪匹配算法适用于超市入口、生鲜区域、 收银台等多种具体场景，并能够在单人、多人复杂运 动条件下保持良好的鲁棒性。 图 ４ 运动跟踪，超市入口，单人 Ｆｉｇ．４ Ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ： ｓｉｎｇｌｅ ｃｕｓｔｏｍｅｒ ａｔ ｔｈｅ ｅｎｔｒａｎｃｅ 图 ５ 运动跟踪，超市入口，多人 Ｆｉｇ．５ Ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ： ｍｕｌｔｉｐｌｅ ｃｕｓｔｏｍｅｒｓ ａｔ ｔｈｅ ｅｎｔｒａｎｃｅ 图 ６ 运动跟踪，生鲜区域，多人 Ｆｉｇ．６ Ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ： ｍｕｌｔｉｐｌｅ ｃｕｓｔｏｍｅｒｓ ａｔ ｔｈｅ ｆｒｅｓｈ ａｒｅａ 图 ７ 运动跟踪，收银台，多人 Ｆｉｇ．７ Ｍｏｖｅｍｅｎｔ ｔｒａｃｋｉｎｇ： ｍｕｌｔｉｐｌｅ ｃｕｓｔｏｍｅｒｓ ａｔ ｔｈｅ ｃｈｅｃｋ ｓｔａｎｄ 具体而言，如图 ４ 所示，运动跟踪匹配算法能够 完整地跟踪顾客从超市监控图像中从出现到离开的 整个过程，亦能适用于顾客运动过程中出现的拐弯 等复杂运动状态。 从图 ５ 中可以看到，在超市中同 时出现多个运动的顾客时，运动跟踪算法能够同时 跟踪相应目标。 如图 ６ 所示，在视频流中出现不同 时长的顾客轨迹时，本算法可以正确地分析出不同 轨迹的起始和终止时刻从而进行对应跟踪。 分析图 ７ 可知，对顾客的运动跟踪即使在顾客密集的场景 中也能够完整的提取出其中运动顾客的轨迹。 对比 图 ５～７ 可以看到，对顾客的运动跟踪能够普遍适用 于超市入口、生鲜区域以及收银台等各种具体场景。 ５ 结束语 超市顾客运动跟踪是计算机视觉领域中目标跟 踪的典型应用，在超市这种复杂环境下进行顾客的 运动跟踪是亟待解决的应用难点。 本文在 ＫＬＴ 特 征点轨迹提取的基础之上进行特征点轨迹的预处 理，进而通过 ｍｅａｎｓｈｉｆｔ 轨迹聚类分离出视频流每一 帧中的每类特征点，最后通过运动轨迹匹配算法将 每一帧中的特征点类与前一帧相匹配得到顾客的完 整运动轨迹。 实验结果表明，本方法能够在实际超 市监控视频中做到顾客的运动跟踪，不仅适用于超 市入口、生鲜区域、收银台等多种典型场景，也能在 遮挡、复杂轨迹、多人异步运动等复杂情况下保持良 好的鲁棒性。 因此，本文所述顾客运动跟踪算法能 够为超市这一供应链终端的后续应用，如智能拥塞 控制、最优商品布局、购物推荐、自动预警等提供可 靠的数据基石。 参考文献： ［１］ＹＩＬＭＡＺ Ａ， ＪＡＶＥＤ Ｏ， ＳＨＡＨ Ｍ． Ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ： ａ ｓｕｒ⁃ 第 ２ 期 王熙，等：基于轨迹聚类的超市顾客运动跟踪 ·１９１·

·192. 智能系统学报 第10卷 vey[J].ACM Computing Surveys (CSUR),2006,38(4) [13]HASHEMZADEH M,PAN G,WANG Y,et al.Combi- 1-45. ning velocity and location-specific spatial clues in trajecto- [2]BROIDA T J,CHELLAPPA R.Estimation of object motion ries for counting crowded moving objects[J].International parameters from noisy images[J.IEEE Transactions on Pat- Journal of Pattern Recognition and Artificial Intelligence, tern Analysis and Machine Intelligence,1986(1):90-99. 2012.27(2):1-31. [3]万琴，王耀南基于卡尔曼滤波器的运动目标检测与跟踪 [14]LUCAS B D,KANADE T.An iterative image registration [J].湖南大学学报：自然科学版，2007,34(3)：36-40. technique with an application to stereo vision[C]//Pro- WAN Qin,WANG Yaonan.Moving objects detecting and ceedings of the IJCAI.Vancouver,Canada,1981:674- tracking based on Kalman filter[J].Journal of Hunan Uni- 679. versity:Natural Sciences,2007,34(3):36-40. [15]TOMASI C,KANADE T.Detection and tracking of point [4]VEENMAN C J,REINDERS M J,BACKER E.Resolving features[M].[S.I.Carnegie Mellon Univ,1991:1-32. motion correspondence for densely moving points[J].IEEE [16]BIRCHFIELD S.KLT:An implementation of the Kanade- Transactions on Pattern Analysis and Machine Intelligence, Lucas-Tomasi feature tracker EB/OL].[2013-11-21 ] 2001,23(1):54-72. http://www.ces.clemson.edu/-stb/klt/. [5]BERTALM O M,SAPIRO G,RANDALL G.Morphing ac- [17]SUGIMURA D,KITANI K M,OKABE T,et al.Using in- tive contours [J].IEEE Transactions on Pattern Analysis dividuality to track individuals:clustering individual traj- and Machine Intelligence,2000,22(7):733-737. ectories in crowds using local appearance and frequency [6]SATO K,AGGARWAL J K.Temporal spatio-velocity trans- trait[C]//2009 IEEE 12th International Conference on form and its application to tracking and interaction[J]. Proceedings of the Computer Vision.Kyoto,Japan,2009: Computer Vision and Image Understanding,2004,96(2): 1467-1474. 100-128. [18]BROX T,MALIK J.Object segmentation by long term a- [7]COMANICIU D,RAMESH V,MEER P.Kernel-based ob- nalysis of point trajectories[M].Springer.2010:282-295. ject tracking[J].IEEE Transactions on Pattern Analysis and 作者简介： Machine Intelligence,2003,25(5):564-577. 王熙，男，1989年生，硕士研究生，主 [8]ZHOU H,YUAN Y,SHI C.Object tracking using SIFT 要研究方向为计算机视觉和数据挖掘。 features and mean shift[J].Computer Vision and Image 0 nderstanding,2009,113(3):345-352. [9]李培华.一种改进的MeanShift跟踪算法[J].自动化学 报，2007,33(4)：347-354. 吴为，1961年生，高级工程师，主要 LI Peihua.An improved Meanshift algorithm for object tac- 研究方向为计算机应用，发表学术论文 king[J].Acta Automatica Sinica,2007,33(4):347-354. [10]BENFOLD B,REID I.Stable multi-target tracking in real- 10余篇。 time surveillance video [C//2011 IEEE Conference on Proceedings of the Computer Vision and Pattern Recogni- ion(CVPR).0 xford,UK,2011:3457-3464. [11]ZACH C,GALLUP D,FRAHM J-M.Fast gain-adaptive 钱沄涛，1968年生，教授，博士生导 KLT tracking on the GPU[C]//08 IEEE Computer Society 师，中国电子学会高级会员，信号处理 Conference on proceedings of the Computer Vision and Pat- 分会委员：中国计算机学会人工智能与 tern Recognition Workshops.[S.I.],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, 智能学会智能CAD与数字艺术专委会委员。主要研究方向 USA,1994:593-600. 为模式识别、信号处理、机器学习，发表学术论文90余篇

ｖｅｙ［Ｊ］． ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ （ＣＳＵＲ）， ２００６， ３８（４）： １⁃４５． ［２］ＢＲＯＩＤＡ Ｔ Ｊ， ＣＨＥＬＬＡＰＰＡ Ｒ． Ｅｓｔｉｍａｔｉｏｎ ｏｆ ｏｂｊｅｃｔ ｍｏｔｉｏｎ ｐａｒａｍｅｔｅｒｓ ｆｒｏｍ ｎｏｉｓｙ ｉｍａｇｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔ⁃ ｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８６（１）： ９０⁃９９． ［３］万琴，王耀南 ．基于卡尔曼滤波器的运动目标检测与跟踪 ［Ｊ］． 湖南大学学报：自然科学版， ２００７， ３４（３）： ３６⁃４０． ＷＡＮ Ｑｉｎ， ＷＡＮＧ Ｙａｏｎａｎ． Ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ ｄｅｔｅｃｔｉｎｇ ａｎｄ ｔｒａｃｋｉｎｇ ｂａｓｅｄ ｏｎ Ｋａｌｍａｎ ｆｉｌｔｅｒ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈｕｎａｎ Ｕｎｉ⁃ ｖｅｒｓｉｔｙ： Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ， ２００７， ３４（３）： ３６⁃４０． ［４］ＶＥＥＮＭＡＮ Ｃ Ｊ， ＲＥＩＮＤＥＲＳ Ｍ Ｊ， ＢＡＣＫＥＲ Ｅ． Ｒｅｓｏｌｖｉｎｇ ｍｏｔｉｏｎ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｆｏｒ ｄｅｎｓｅｌｙ ｍｏｖｉｎｇ ｐｏｉｎｔｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００１， ２３（１）： ５４⁃７２． ［５］ＢＥＲＴＡＬＭ Ｏ Ｍ， ＳＡＰＩＲＯ Ｇ， ＲＡＮＤＡＬＬ Ｇ． Ｍｏｒｐｈｉｎｇ ａｃ⁃ ｔｉｖｅ ｃｏｎｔｏｕｒｓ ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０００， ２２（７）： ７３３⁃７３７． ［６］ＳＡＴＯ Ｋ， ＡＧＧＡＲＷＡＬ Ｊ Ｋ． Ｔｅｍｐｏｒａｌ ｓｐａｔｉｏ⁃ｖｅｌｏｃｉｔｙ ｔｒａｎｓ⁃ ｆｏｒｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｔｒａｃｋｉｎｇ ａｎｄ ｉｎｔｅｒａｃｔｉｏｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２００４， ９６（２）： １００⁃１２８． ［７］ＣＯＭＡＮＩＣＩＵ Ｄ， ＲＡＭＥＳＨ Ｖ， ＭＥＥＲ Ｐ． Ｋｅｒｎｅｌ⁃ｂａｓｅｄ ｏｂ⁃ ｊｅｃｔ ｔｒａｃｋｉｎｇ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００３， ２５（５）： ５６４⁃５７７． ［８］ ＺＨＯＵ Ｈ， ＹＵＡＮ Ｙ， ＳＨＩ Ｃ． Ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ＳＩＦＴ ｆｅａｔｕｒｅｓ ａｎｄ ｍｅａｎ ｓｈｉｆｔ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２００９， １１３（３）： ３４５⁃３５２． ［９］李培华．一种改进的 ＭｅａｎＳｈｉｆｔ 跟踪算法［ Ｊ］． 自动化学 报， ２００７， ３３（４）： ３４７⁃３５４． ＬＩ Ｐｅｉｈｕａ． Ａｎ ｉｍｐｒｏｖｅｄ Ｍｅａｎｓｈｉｆｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｂｊｅｃｔ ｔａｃ⁃ ｋｉｎｇ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ２００７， ３３（４）： ３４７⁃３５４． ［１０］ＢＥＮＦＯＬＤ Ｂ， ＲＥＩＤ Ｉ． Ｓｔａｂｌｅ ｍｕｌｔｉ⁃ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ｉｎ ｒｅａｌ⁃ ｔｉｍｅ ｓｕｒｖｅｉｌｌａｎｃｅ ｖｉｄｅｏ ［ Ｃ］ ／ ／ ２０１１ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ （ＣＶＰＲ）． Ｏｘｆｏｒｄ， ＵＫ， ２０１１： ３４５７⁃３４６４． ［１１］ ＺＡＣＨ Ｃ， ＧＡＬＬＵＰ Ｄ， ＦＲＡＨＭ Ｊ⁃Ｍ． Ｆａｓｔ ｇａｉｎ⁃ａｄａｐｔｉｖｅ ＫＬＴ ｔｒａｃｋｉｎｇ ｏｎ ｔｈｅ ＧＰＵ［Ｃ］ ／ ／ ０８ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔ⁃ ｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｏｒｋｓｈｏｐｓ． ［Ｓ．ｌ．］， ＵＳＡ， ２００８： １⁃７． ［１２］ ＳＨＩ Ｊ， ＴＯＭＡＳＩ Ｃ． Ｇｏｏｄ ｆｅａｔｕｒｅｓ ｔｏ ｔｒａｃｋ ［ Ｃ］ ／ ／ １９９４ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｓｅａｔｔｌｅ， ＷＡ， ＵＳＡ， １９９４： ５９３⁃６００． ［１３］ＨＡＳＨＥＭＺＡＤＥＨ Ｍ， ＰＡＮ Ｇ， ＷＡＮＧ Ｙ， ｅｔ ａｌ． Ｃｏｍｂｉ⁃ ｎｉｎｇ ｖｅｌｏｃｉｔｙ ａｎｄ ｌｏｃａｔｉｏｎ⁃ｓｐｅｃｉｆｉｃ ｓｐａｔｉａｌ ｃｌｕｅｓ ｉｎ ｔｒａｊｅｃｔｏ⁃ ｒｉｅｓ ｆｏｒ ｃｏｕｎｔｉｎｇ ｃｒｏｗｄｅｄ ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１２， ２７（２）：１⁃３１． ［１４］ＬＵＣＡＳ Ｂ Ｄ， ＫＡＮＡＤＥ Ｔ． Ａｎ ｉｔｅｒａｔｉｖｅ ｉｍａｇｅ ｒｅｇｉｓｔｒａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ｗｉｔｈ ａｎ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｓｔｅｒｅｏ ｖｉｓｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＪＣＡＩ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， １９８１： ６７４⁃ ６７９． ［１５］ＴＯＭＡＳＩ Ｃ， ＫＡＮＡＤＥ Ｔ． Ｄｅｔｅｃｔｉｏｎ ａｎｄ ｔｒａｃｋｉｎｇ ｏｆ ｐｏｉｎｔ ｆｅａｔｕｒｅｓ［Ｍ］． ［Ｓ．ｌ．］：Ｃａｒｎｅｇｉｅ Ｍｅｌｌｏｎ Ｕｎｉｖ， １９９１： １⁃３２． ［１６］ＢＩＲＣＨＦＩＥＬＤ Ｓ． ＫＬＴ： Ａｎ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ Ｋａｎａｄｅ⁃ Ｌｕｃａｓ⁃Ｔｏｍａｓｉ ｆｅａｔｕｒｅ ｔｒａｃｋｅｒ ［ ＥＢ／ ＯＬ］． ［ ２０１３⁃１１⁃２１ ］． ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｅｓ．ｃｌｅｍｓｏｎ．ｅｄｕ ／ ～ ｓｔｂ ／ ｋｌｔ ／ ． ［１７］ＳＵＧＩＭＵＲＡ Ｄ， ＫＩＴＡＮＩ Ｋ Ｍ， ＯＫＡＢＥ Ｔ， ｅｔ ａｌ． Ｕｓｉｎｇ ｉｎ⁃ ｄｉｖｉｄｕａｌｉｔｙ ｔｏ ｔｒａｃｋ ｉｎｄｉｖｉｄｕａｌｓ： ｃｌｕｓｔｅｒｉｎｇ ｉｎｄｉｖｉｄｕａｌ ｔｒａｊ⁃ ｅｃｔｏｒｉｅｓ ｉｎ ｃｒｏｗｄｓ ｕｓｉｎｇ ｌｏｃａｌ ａｐｐｅａｒａｎｃｅ ａｎｄ ｆｒｅｑｕｅｎｃｙ ｔｒａｉｔ［ Ｃ］ ／ ／ ２００９ ＩＥＥＥ １２ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ． Ｋｙｏｔｏ， Ｊａｐａｎ， ２００９： １４６７⁃１４７４． ［１８］ＢＲＯＸ Ｔ， ＭＡＬＩＫ Ｊ． Ｏｂｊｅｃｔ ｓｅｇｍｅｎｔａｔｉｏｎ ｂｙ ｌｏｎｇ ｔｅｒｍ ａ⁃ ｎａｌｙｓｉｓ ｏｆ ｐｏｉｎｔ ｔｒａｊｅｃｔｏｒｉｅｓ［Ｍ］． Ｓｐｒｉｎｇｅｒ． ２０１０： ２８２⁃２９５． 作者简介： 王熙，男，１９８９ 年生，硕士研究生，主 要研究方向为计算机视觉和数据挖掘。 吴为，１９６１ 年生，高级工程师，主要 研究方向为计算机应用，发表学术论文 １０ 余篇。 钱沄涛，１９６８ 年生，教授，博士生导 师，中国电子学会高级会员，信号处理 分会委员；中国计算机学会人工智能与 模式识别专委会委员，中国计算机学会 模糊逻辑与多值逻辑专委会委员；中国 航空学会信息融合分会委员；中国人工 智能学会智能 ＣＡＤ 与数字艺术专委会委员。 主要研究方向 为模式识别、信号处理、机器学习，发表学术论文 ９０ 余篇。 ·１９２· 智 能 系 统 学 报 第 １０ 卷