基于軌跡聚類的超市顧客運動跟蹤

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150302.1106.010.html

基于軌跡聚類的超市顧客運動跟蹤

王熙1，吳為2，錢沄濤1

(1.浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027； 2.浙江省網(wǎng)絡(luò)系統(tǒng)及信息安全重點實驗室，浙江 杭州 310006)

摘要：針對超市等復(fù)雜應(yīng)用環(huán)境下的運動目標軌跡跟蹤問題，將軌跡聚類運用于目標跟蹤中，提出了一種超市顧客運動跟蹤方法。該方法對Kanade-Lucas-Tomasi(KLT)算法提取并跟蹤得到的特征點軌跡進行預(yù)處理，濾除背景和短時特征點以分離出運動目標所在區(qū)域的關(guān)鍵特征點；進而采用均值漂移(meanshift)算法進行軌跡聚類，解決了單幀靜態(tài)特征點聚類時的目標遮擋問題；最后采用運動跟蹤匹配算法對前后幀的特征點進行最優(yōu)匹配，解決了目標出入視頻區(qū)域以及具有復(fù)雜路線時的穩(wěn)定跟蹤問題，得到顧客的完整運動軌跡。實驗結(jié)果表明，該方法能夠在超市入口、生鮮區(qū)以及收銀臺等各種典型超市區(qū)域中完成顧客軌跡的運動跟蹤，并對顧客部分遮擋、復(fù)雜運動軌跡以及異步運動等多種特殊情況具有較高的魯棒性。

關(guān)鍵詞：目標跟蹤；特征匹配；軌跡聚類；運動分析

DOI:10.3969/j.issn.1673-4785.201401002

中圖分類號：TP391.4 文獻標志碼：A

收稿日期：2014-01-13. 網(wǎng)絡(luò)出版日期：2015-03-02.

基金項目：國家科技支撐計劃資助項目(2011BAD24B03)浙江省網(wǎng)絡(luò)系統(tǒng)及信息安全重點實驗室開放基金資助項目(2013002).

作者簡介：

中文引用格式：王熙，吳為，錢沄濤. 基于軌跡聚類的超市顧客運動跟蹤[J]. 智能系統(tǒng)學(xué)報， 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.

在計算機視覺領(lǐng)域的各種研究和應(yīng)用中，目標跟蹤一直是一項重要而又兼具挑戰(zhàn)性的技術(shù)。目標跟蹤的主要任務(wù)在于對視頻流中的運動信息進行分析和處理，從而提取出目標物體的運動軌跡。超市作為目標跟蹤的典型應(yīng)用場景，其目標跟蹤的主要任務(wù)集中在對顧客的運動軌跡進行提取。超市作為供應(yīng)鏈系統(tǒng)的終端，顧客的運動跟蹤為超市擁塞控制、商品布局、購物推薦、自動預(yù)警等應(yīng)用提供了數(shù)據(jù)基石，因而具有很高的應(yīng)用價值和廣闊的應(yīng)用前景。

當(dāng)前目標跟蹤的主要方法分為點跟蹤、輪廓跟蹤與核跟蹤3類[1]?；邳c跟蹤的方法，如卡爾曼濾波[2-3]、最優(yōu)分配濾波跟蹤[4]等，目標在視頻幀中采用點表示，通過前一幀中物體的位置、運動等狀態(tài)將后一幀中的點與前一幀中的點關(guān)聯(lián)起來。但基于點跟蹤的方法需要在每一幀中檢測出被跟蹤的目標，不適合用于超市這種存在較多遮擋的應(yīng)用場景中?；谳喞櫟姆椒ɡ媚繕藚^(qū)域內(nèi)的信息，通過輪廓演化[5]或形狀匹配[6]進行跟蹤。這種方法需要獲取目標的輪廓信息，因而在超市這種顧客姿態(tài)各異的場景中應(yīng)用受限?；诤烁櫟姆椒?，如meanshift[7-9]、KLT[10-12]等，通過計算核在連續(xù)幀之間平移、旋轉(zhuǎn)、仿射等運動進行目標的跟蹤?；诤烁櫟姆椒ㄍǔδ繕说倪\動方式和所處環(huán)境有一定約束，例如KLT算法要求視頻流中光照強度幾乎不變，且特征點在連續(xù)2幀之間的運動為微小運動。

綜合以上方法的優(yōu)點和不足之處，考慮到本文所述場景中超市室內(nèi)光照條件能夠保持基本穩(wěn)定且顧客運動軌跡在相鄰2幀之間無突變，本文采用KLT算法進行特征點提取和跟蹤，得到一系列特征點的運動軌跡。通過特征點預(yù)處理過程對背景和短時特征點軌跡進行濾除，從而分離出視頻每一幀中運動目標所在區(qū)域的關(guān)鍵特征點。進一步，利用當(dāng)前幀中的特征點在前后幀窗口內(nèi)的信息，采用meanshift算法對當(dāng)前幀中的特征點所對應(yīng)的軌跡進行聚類，聚為同一類的軌跡在當(dāng)前幀中的特征點對應(yīng)屬于同一類，從而解決了僅使用單幀靜態(tài)特征點聚類時多個目標之間的遮擋問題[13]。最終，在視頻每一幀中查找當(dāng)前幀的所有特征點類在前一幀中相似度最高的匹配類，得到目標在連續(xù)視頻幀中的運動軌跡。通過上述運動匹配算法，解決了運動目標出入視頻區(qū)域以及具有復(fù)雜運動軌跡時的穩(wěn)定跟蹤問題。

1特征點軌跡提取及預(yù)處理

1.1特征點軌跡提取

本文采用KLT算法進行特征點提取及跟蹤，KLT算法是一種經(jīng)典的基于特征的跟蹤算法，該算法選擇圖像特征窗口內(nèi)梯度矩陣特征值較大的點作為特征點，并利用基于最優(yōu)估計的匹配算法實現(xiàn)特征點在連續(xù)幀之間的匹配，從而得到特征點軌跡[12, 14-16]。具體來說，KLT算法假定在特征窗口W內(nèi)t時刻的圖像幀表示為I(x,y,t)，t+τ時刻的圖像幀表示為I(x,y,t+τ)，從t時刻到t+τ時刻的位置關(guān)系滿足式(1):

(1)

定義d=(Δx,Δy)為點X(x,y)的偏移量。KLT匹配的過程即為尋找d使得式(2)中ε達到最小值。

(2)

式中：I、J表示2幀圖像，W為特征窗口，ω(X)為加權(quán)函數(shù)。

1.2 特征點軌跡預(yù)處理

由于KLT算法中提取出特征點是基于圖像特征窗口內(nèi)梯度矩陣的特征值，即選取紋理模式穩(wěn)定且明顯的點作為特征點。然而，在實際視頻幀中，這樣的點不僅分布在移動的目標上，也大量存在于背景中，因此需要將背景特征點及對應(yīng)軌跡進行濾除。另一方面，KLT算法跟蹤出的特征點軌跡中存在跟蹤不穩(wěn)定的情況，即一部分特征點在被跟蹤較短的時間之后丟失。此時，除了補充新的特征點以保證特征點總數(shù)穩(wěn)定之外，應(yīng)當(dāng)在跟蹤結(jié)果中將這部分短暫的軌跡進行濾除。

1.2.1濾除背景特征點

背景特征點相對于運動目標上的特征點，其表現(xiàn)為在特征點軌跡中，其坐標長時間保持恒定。定義特征點FP在第t幀的坐標為FPt=(x,y)，則背景特征點滿足式(3)：

(3)

式中：L為軌跡連續(xù)靜止幀數(shù)，d(FPi,FPi+1)表示特征點FP在第i幀與第i+1幀之間移動的距離，s表示特征點最大連續(xù)靜止幀數(shù)。濾除背景特征點的過程即為在KLT特征點的跟蹤結(jié)果中遍歷每一條特征點軌跡，若滿足式(3)，則將該軌跡標記為無效軌跡。濾除背景特征點的流程如算法1所示。

算法1 濾除背景特征點

輸入軌跡集合trajSet最大連續(xù)靜止幀數(shù)s;

輸出軌跡集合trajSet。

1)for all traj in trajSet

2)按照式(3)計算軌跡連續(xù)靜止長度L

3) if L>s

5) end if

6)end for

1.2.2濾除短時特征點

短時特征點相對于被穩(wěn)定跟蹤的特征點，其表現(xiàn)為連續(xù)運動幀數(shù)過短。由于在超市不同位置的具體場景以及攝像機角度、焦距等不盡相同，故不能直接參照濾除背景特征點中的方法為特征點的連續(xù)運動幀數(shù)取固定的閾值，而應(yīng)當(dāng)根據(jù)當(dāng)前視頻中軌跡長度的分布情況選取更為合理的閾值。

定義Li為KLT跟蹤結(jié)果中第i條軌跡的長度，則最小連續(xù)運動幀數(shù)m如式(4)所示，其中λ為權(quán)重系數(shù)。

(4)

短時特征點即為滿足式(5)的特征點，

(5)

式中：L為軌跡長度，d(FPi,FPi+1)表示特征點FP在第i幀與第i+1幀之間移動的距離，φ表示特征點在連續(xù)2幀之間最多移動的距離，若連續(xù)2幀之間移動距離超過φ，則認為是一條新的軌跡。濾除短時特征點的算法與濾除背景特征點算法類似，在此不再復(fù)述。

2軌跡聚類

在特征點軌跡提取和預(yù)處理的基礎(chǔ)之上，本文采用軌跡聚類的方法在每一幀中檢測出運動目標[13, 15, 17]?？紤]到視頻每一幀F(xiàn)i中的特征點在時間窗口內(nèi)的信息，采用meanshift算法對當(dāng)前幀的軌跡集合TSi進行聚類，被聚為同一類的軌跡代表了軌跡上的特征點在當(dāng)前幀F(xiàn)i及其窗口內(nèi)的空間位置均具有較高的相似性，對應(yīng)地將同類軌跡在當(dāng)前幀F(xiàn)i時的特征點歸為同一類目標，從而在每一幀中完成了特征點的聚類。限定meanshift聚類時的窗口大小為w，即對于每一幀F(xiàn)i只考慮經(jīng)過該幀的軌跡在[Fi-w,Fi+w]內(nèi)的部分,采用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進行軌跡聚類在每一幀解決了特征點的穩(wěn)定聚類問題，而目標的運動跟蹤則需要在相鄰2幀對聚類結(jié)果進行匹配，即對于當(dāng)前幀中的每一類找出上一幀中的匹配類。定義CC、LC分別表示當(dāng)前幀和上一幀特征點聚類結(jié)果，f(CCi,LCj)代表當(dāng)前幀聚類結(jié)果中第i類與上一幀聚類結(jié)果中第j類之間的相似度，則對于當(dāng)前幀中的每一類CCi，上述匹配問題在于尋找k使得f(CCi,LCk)取得最大值，為了保證匹配結(jié)果的置信度，限定最大相似度不小于fmin。相似度、k與fmin的定義分別如式(8) ～(10)所示，其中α為最小公共系數(shù)。

(8)

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

(9)

(10)

?CCi,M(CCi)=LCj,

(11)

由于在視頻流中的出現(xiàn)新的目標時會使最大相似度為0，同時在上述最優(yōu)匹配的過程中當(dāng)前幀內(nèi)非最優(yōu)匹配的類沒有完成匹配。在這種情況時，運動跟蹤匹配算法將該特征點類標記為獨立類。至此，當(dāng)前幀中的所有的類完成了與前一幀的匹配過程，將該匹配算法連續(xù)運用到每一幀中即可實現(xiàn)完整的目標運動跟蹤。運動跟蹤匹配算法的整體結(jié)構(gòu)如算法3。

算法3運動跟蹤匹配算法

Ni:特征點類i中被匹配的特征點個數(shù)。

輸入上一幀特征點類集合lastSet，當(dāng)前幀特征點類集合currentSet，最小公共系數(shù)α；

輸出當(dāng)前幀聚類集合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實驗結(jié)果與分析

實驗選取物美超市內(nèi)的實際監(jiān)控視頻作為數(shù)據(jù)集以驗證上述算法的有效性，該數(shù)據(jù)集涵蓋超市入口、生鮮區(qū)域、收銀臺等3種典型場景，視頻分辨率為352像素×288像素。

KLT特征點提取的結(jié)果如圖1所示，視頻中每幀提取的特征點個數(shù)為2000，任意2個特征點之間的最小距離為5像素。從圖1中可以看出，特征點不僅分布在運動的顧客身上，也廣泛的分布于紋理特征較為明顯的背景之中。

圖1　KLT特征點提取 Fig.1　Detecting KLT feature points

經(jīng)軌跡預(yù)處理之后的特征點分布情況如圖2所示，其中濾除背景點算法中最大連續(xù)靜止幀數(shù)s取5幀，濾除短時點算法中權(quán)重系數(shù)λ取0.3，特征點在連續(xù)2幀間最大移動距離φ取5像素。從圖2可以看出，經(jīng)過預(yù)處理，在KLT特征點提取階段出現(xiàn)的背景特征點與短時特征點被很好的濾除，視頻幀中特征點集中在運動目標身上，為下一步meanshift軌跡聚類提供了有效、穩(wěn)定的運動軌跡。

圖2　特征點軌跡預(yù)處理 Fig.2　Preprocessing trajectories of feature points

采用meanshift進行軌跡聚類的結(jié)果如圖3所示，其中X方向帶寬bx取25像素，Y方向帶寬by取60像素，窗口大小w取20幀，收斂閾值e取1像素。對比圖2與圖3可以看出，當(dāng)前幀中的特征點被聚為2類，軌跡聚類利用當(dāng)前幀特征點在前后時間窗口內(nèi)的信息很好地解決了目標存在部分遮擋的問題。

圖3　meanshift軌跡聚類 Fig.3　Trajectory clustering by meanshift

圖4～7展示了目標運動跟蹤部分的最終實驗結(jié)果，其中最小公共系數(shù)α取0.33。從圖中可以看出，運動跟蹤匹配算法適用于超市入口、生鮮區(qū)域、收銀臺等多種具體場景，并能夠在單人、多人復(fù)雜運動條件下保持良好的魯棒性。

圖4　運動跟蹤，超市入口，單人 Fig.4　Movement tracking： single customer at the entrance

圖5　運動跟蹤，超市入口，多人 Fig.5　Movement tracking： multiple customers at the entrance

圖6　運動跟蹤，生鮮區(qū)域，多人 Fig.6　Movement tracking： multiple customers at the fresh area

圖7　運動跟蹤，收銀臺，多人 Fig.7　Movement tracking：multiple customers at the check stand

具體而言，如圖4所示，運動跟蹤匹配算法能夠完整地跟蹤顧客從超市監(jiān)控圖像中從出現(xiàn)到離開的整個過程，亦能適用于顧客運動過程中出現(xiàn)的拐彎等復(fù)雜運動狀態(tài)。從圖5中可以看到，在超市中同時出現(xiàn)多個運動的顧客時，運動跟蹤算法能夠同時跟蹤相應(yīng)目標。如圖6所示，在視頻流中出現(xiàn)不同時長的顧客軌跡時，本算法可以正確地分析出不同軌跡的起始和終止時刻從而進行對應(yīng)跟蹤。分析圖7可知，對顧客的運動跟蹤即使在顧客密集的場景中也能夠完整的提取出其中運動顧客的軌跡。對比圖5～7可以看到，對顧客的運動跟蹤能夠普遍適用于超市入口、生鮮區(qū)域以及收銀臺等各種具體場景。

5結(jié)束語

超市顧客運動跟蹤是計算機視覺領(lǐng)域中目標跟蹤的典型應(yīng)用，在超市這種復(fù)雜環(huán)境下進行顧客的運動跟蹤是亟待解決的應(yīng)用難點。本文在KLT特征點軌跡提取的基礎(chǔ)之上進行特征點軌跡的預(yù)處理，進而通過meanshift軌跡聚類分離出視頻流每一幀中的每類特征點，最后通過運動軌跡匹配算法將每一幀中的特征點類與前一幀相匹配得到顧客的完整運動軌跡。實驗結(jié)果表明，本方法能夠在實際超市監(jiān)控視頻中做到顧客的運動跟蹤，不僅適用于超市入口、生鮮區(qū)域、收銀臺等多種典型場景，也能在遮擋、復(fù)雜軌跡、多人異步運動等復(fù)雜情況下保持良好的魯棒性。因此，本文所述顧客運動跟蹤算法能夠為超市這一供應(yīng)鏈終端的后續(xù)應(yīng)用，如智能擁塞控制、最優(yōu)商品布局、購物推薦、自動預(yù)警等提供可靠的數(shù)據(jù)基石。

參考文獻:

[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]. 湖南大學(xué)學(xué)報：自然科學(xué)版, 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]. 自動化學(xué)報, 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年生，碩士研究生，主要研究方向為計算機視覺和數(shù)據(jù)挖掘。

吳為，1961年生，高級工程師，主要研究方向為計算機應(yīng)用，發(fā)表學(xué)術(shù)論文10余篇。

錢沄濤，1968年生，教授，博士生導(dǎo)師，中國電子學(xué)會高級會員，信號處理分會委員；中國計算機學(xué)會人工智能與模式識別專委會委員，中國計算機學(xué)會模糊邏輯與多值邏輯專委會委員；中國航空學(xué)會信息融合分會委員；中國人工智能學(xué)會智能CAD與數(shù)字藝術(shù)專委會委員。主要研究方向為模式識別、信號處理、機器學(xué)習(xí)，發(fā)表學(xué)術(shù)論文90余篇。