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