基于冗余分組的軌跡摘要算法

魏 昊，徐 慶

(天津大學 計算機科學與技術學院，天津 300350)

基于冗余分組的軌跡摘要算法

魏 昊，徐 慶*

(天津大學 計算機科學與技術學院，天津 300350)

(*通信作者電子郵箱qingxu@tju.edu.cn)

為了對視頻監控設備采集到的軌跡數據進行聚類和異常檢測，提出了一種新的軌跡摘要算法。使用了Jensen-Shannon Divergence(JSD)度量方法實現了軌跡數據的重采樣，使得計算軌跡間相似度的準確性有所提高，并為后續濾波過程提供了必要的等采樣點個數的軌跡數據; 自適應地確定軌跡相似性的閾值，并采用非局部的思想，將軌跡數據進行冗余分組，同時識別出異常軌跡數據; 從信號處理的角度對分組后的軌跡數據進行硬閾值濾波，經過合并得到摘要軌跡; 此外，不受軌跡輸入順序的影響，并且提供了可視化的多尺度軌跡摘要結果。與具有噪聲的基于密度的聚類(DBSCAN)算法的異常檢測效果進行對比，所提算法在準確率(Precision)、召回率(Recall)以及F1指標上均有所提升。

軌跡摘要；重采樣；非局部去噪；信號處理；多尺度濾波

0 引言

軌跡數據在諸多實際領域都有十分重要的作用，如智能交通等[1]。Sermanet等[2]使用聚類算法對行人軌跡數據進行分析。Le[3]使用多尺度模型對軌跡數據進行無監督聚類。為了獲取數據的模型或發現數據中隱藏的深層信息，聚類是分析模型常用且有效的途徑[4-5]。目前聚類算法已經有了大量的研究，常見的聚類算法有k-means[6]、BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)[7]、具有噪聲的基于密度的聚類方法(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)[8]、OPTICS(Ordering Points To Identify the Clustering Structure)[9]以及STING(STatistical INformation Grid)[10]等。在上述聚類算法中，k-means算法存在一個棘手的問題，即如何在聚類前確定數據中類的個數，而且異常數據對聚類效果的影響較大。BIRCH算法對數據分布的形狀有一定的要求。DBSCAN算法的鄰域半徑參數需要人工給出。OPTICS算法雖然對DBSCAN算法進行了改進，但其內部復雜處理過程使得實際運行速度遠遠低于DBSCAN。STING算法形成的類簇的外邊界不確定性較大。這些聚類算法難以直接應用在復雜軌跡數據上，主要因為軌跡數據有以下三點特殊性：每條軌跡都是一個單獨的元素，其內部擁有不同的采樣點個數；在同一場景的不同區域里，軌跡間的相似性不盡相同；正常軌跡與異常軌跡往往會存在交叉重疊等可能性。

Vlachos等[11]使用了小波變換改變軌跡的表現形式來提升聚類算法效果。在圖像領域，基于塊匹配的三維濾波算法(Block-Matching and 3D filtering, BM3D)是目前較為領先的圖像濾波算法[12]，該算法首次利用了相似結構的圖像塊的一致性使得濾波效果得以提升。受以上核心思想的啟發，本文提供了一種對軌跡做摘要處理的算法，通過對軌跡重采樣以及非局部去噪，尋找更有效的軌跡數據聚類和異常檢測算法。

1 軌跡摘要算法框架

本文算法框架主要是由兩部分構成，即重采樣和非局部去噪。下面的章節將詳細介紹這兩個過程。

1.1 重采樣

通常不同的軌跡有不同個數的采樣點，難免包含一些噪聲采樣點，會對后續距離計算造成不準確的影響，且后續的硬閾值濾波過程需要使用的是等長(即等采樣點個數，下文中所有等長均為此含義)軌跡。本文使用了重采樣技術，使得軌跡得以平滑處理，將噪聲采樣點的影響降低，并使每一條軌跡等長。每一條軌跡的采樣點都會被重采樣為相同的間隔。為了使重采樣過程對原始軌跡數據信息量的破壞降到最小，需要針對一個軌跡數據集找到一個最優采樣點數moptimal，盡可能保留原始軌跡的數據特征。

在本文中，重采樣所處理的軌跡數據是二維坐標點序列，不妨令Traj={p1,p2,…,pm}表示一條具有m個采樣點軌跡，此處的pi=(xi,yi)是二維坐標。本文將二維坐標序列中的時間序號i作為自變量，將x坐標和y坐標分別作為因變量。此時，對(i,xi)序列做多項式擬合，使用最小二乘法來優化多項式的參數。同樣的，也對(i,yi)序列擬合，根據實驗結果表明，通常多項式擬合中的最高項次數設置為8比較合適。分別將x曲線和y曲線劃分為moptimal-1段，可以計算出moptimal個x坐標以及moptimal個y坐標，由此可以得到一條具有moptimal個采樣點的重采樣軌跡。

考慮到重采樣后需要保留原始軌跡的整體形狀信息，為獲取最優值moptimal，使用重采樣前后的JSD(Jensen-Shannon Divergence)距離作為衡量標準，目的是最小化JSD距離。因此在這里將軌跡采樣點的夾角分布作為軌跡形狀的重要特征，以考量軌跡重采樣前后的信息變化量。

軌跡的夾角信息{θi,i=1,2,…,m-2}如圖1所示。

圖1 軌跡點和角度說明Fig. 1 View of trajectory points and angles

使用具有B個bins的角度直方圖建立概率分布P(x)，夾角的角度值范圍從min{θi}至max{θi}，同時設置B=12。通過實驗，發現moptimal的最優值對B的變化并不敏感。對重采樣后的軌跡Traj′，可以使用同樣的方法取得Q(x)，Traj和Traj′的JSD距離可以通過式(1)計算:

(1)

其中:D(P‖M)=∑P(x) ln [P(x)/M(x)]，D(Q‖M)=∑Q(x) ln [Q(x)/M(x)]，M=(P+Q)/2。用式(1)對數據集中的每條軌跡計算得到結果，并取平均值，可以得到JSD值關于重采樣點個數的曲線，如圖2所示。本文所采用的數據集中每條軌跡至少有10個以上采樣點，因此重采樣后如果點數過少顯然不能表示復雜曲折的軌跡。JSD值越小表明原始軌跡和重采樣后的軌跡信息損失更小。moptimal的取值即為使得JSD值最小的重采樣點個數，即為圖2中最低點的x坐標。實驗表明，對于不同的數據集，JSD曲線圖的趨勢基本一致。

圖2 JSD曲線Fig. 2 JSD curve

1.2 非局部去噪

在軌跡重采樣之后，本文使用非局部去噪方法，通過多次迭代獲得多尺度摘要。該方法包含冗余匹配、硬閾值處理以及合并3個組成部分。異常軌跡會在某一次迭代中被剔除，且不會參與后續的迭代過程。

為了便于理解，定義TRk作為第k次迭代的輸出軌跡集合，同時也作為第k+1次迭代的輸入軌跡集合。TR0是原始軌跡重采樣后的軌跡集合。迭代的終止條件是兩次相鄰迭代的輸出軌跡結果幾乎不改變，即TRk-1≈TRk。

1.2.1 冗余匹配

在這一步驟中，相似的軌跡將被互相匹配并建立軌跡組，與此同時，異常軌跡也可能在相似性匹配的過程中被檢測和剔除。每一條軌跡會作為一個參考軌跡，匹配與其相似性較高的其他軌跡。假定當前參考軌跡為Traj={p1,p2,…,pm}，則其相似軌跡組G可以通過式(2)計算得到:

G={Trajx|distance(Trajx,Traj)≤ξ}

(2)

由于軌跡是等長的，在式(2)中，distance函數為軌跡間歐氏距離，即將兩條軌跡的所有對應點的歐氏距離求均值。在匹配過程中，冗余的體現之處在于一條軌跡的信息可能會出現在多個軌跡組當中，且在各個組內的處理是獨立的。ξ是距離的閾值，可以自適應地選取，在后續章節本文將詳細闡述自適應的方法。異常軌跡所在的分組可以較為容易地和其他軌跡組區分，通常如果軌跡組內的軌跡數量不足3條，則認為該條參考軌跡是異常的。

1.2.2 硬閾值處理

在本過程中，需對所有軌跡組進行小波硬閾值[13]處理。假定Traj為一條參考軌跡，擁有g個相似的鄰居軌跡，則軌跡組G信號形式為:

(3)

此處si為軌跡組的第i個信號，由組內所有軌跡的第i個采樣點組成，之后對si作小波硬閾值處理。首先，對si做小波變換，將其轉換為小波系數；其次，對小波系數作硬閾值處理，使得數據更為平滑；最后，去噪之后的信號會通過小波反變換還原到原始空間，整個過程如式(4):

si=wavelet-1(threshold(wavelet(si)))

(4)

其中:wavelet(·)表示小波變換，threshold(·)表示硬閾值濾波，wavelet-1表示小波反變換。

1.2.3 合并

在之前的過程中，對每條軌跡都作了冗余匹配，因而在硬閾值處理之后，不同的軌跡組中的軌跡可能來源于本次迭代分組前的同一條軌跡Trajx。將這些軌跡合并，作為軌跡Trajx本次迭代的結果。合并過程即為將這些軌跡相對應采樣點求加權均值，權重為軌跡所在分組的軌跡數量。使用本次迭代的軌跡結果作為下一次迭代的輸入數據，直到滿足迭代的終止條件。

1.3 參數的自適應選取

對于某個軌跡數據集，距離閾值ξ可以通過數據集的所有軌跡自適應地獲取。首先，對于每一條軌跡，可以獲得該條軌跡到其他所有軌跡的歐氏距離，并將這些距離按升序排序。其次，將所有軌跡的第x小距離相加，并求平均值，結果如圖3(a)所示。該圖像是單調遞增的，且增長速度在不同的位置也不同。最后對該函數求二階導，即求出增長速度變化量的曲線，如圖3(b)所示，圖中的最高點表明距離變化最大之處，此處x=153。將閾值ξ設置為圖3(a)中x=153時y坐標的值。這是因為，小于ξ的部分代表類簇內部的距離，大于ξ的部分代表類簇之間的距離，在此處會出現距離增大速度十分陡峭的現象。閾值ξ用作軌跡相似性的判定是合適的。

圖3 閾值ξ的選取Fig. 3 Selection of threshold ξ

2 實驗說明

為了更清晰地體現本文提出的軌跡摘要算法的特點，本文對兩個數據集進行了可視化，以便分析多次迭代的軌跡結果。

2.1 交叉數據集的分析

圖4(a)是交叉路口數據集[1]的原始軌跡，數據集中有軌跡262條，軌跡的采樣點個數區間為[8,22]。迭代結果分別為圖4(b)～圖4(f)。從宏觀上看，軌跡數據從雜亂重疊的原始數據，被壓縮為了精簡的7類軌跡，也可以成為7類模式。迭代在第5次之后停止，因為這次迭代的結果和第4次的迭代結果并無差異，滿足了迭代的終止條件。從圖中可以看出，本身較為復雜的軌跡數據通過多次迭代形成了多尺度的結果，例如圖4(a)～圖4(b) 的過程，軌跡被大幅度地規整，并且其中有12條異常軌跡被檢測出，因而在第1次迭代的結果中被剔除了；在圖4(b)～圖4(c)的第2次迭代中，有一條從左向右貫穿的軌跡，由于其右側明顯的拐角變化(箭頭指向位置)，因而被檢測為異常軌跡。圖4(g) 是DBSCAN的聚類結果，本文使用不同的灰度值區分不同的類，位置明顯不同的軌跡也屬于不同的類。可以看到，DBSCAN將整個軌跡數據集聚為5類。如圖4(h)，從DBSCAN的聚類結果的每個類中選出一條能代表該類的中心軌跡，作為數據集的摘要。在圖4(f)中，原始軌跡在1處和2處的軌跡數量并不多，但也有一定的規模，不能將其簡單地視為異常，本文算法最終保留下了這些信息，而在DBSCAN的結果中這些軌跡則被視為了異常。

圖4 交叉路口數據集摘要結果Fig. 4 Abstraction of cross dataset

2.2 實驗室數據集的結果分析

圖5(a)是實驗室數據集[1]的原始軌跡，軌跡條數為122，采樣點個數的范圍是[39,624]。各次迭代的軌跡摘要結果分別為圖5(b)～圖5(f)。在圖5(f)中，可以清晰地看到圖中7條軌跡，這7條中的每一條軌跡實際上是數十條相同的軌跡重合的結果。圖5(g)和圖5(f)分別是DBSCAN的聚類結果和聚類中心。

圖5 實驗室數據集摘要結果Fig. 5 Abstraction of lab dataset

3 客觀評價對比

本文提出的軌跡摘要算法，不僅能提供簡潔的可視化結果，也能通過多次迭代對軌跡數據進行異常檢測。為評估本文算法的異常檢測效果，本文引入了召回率(Recall)和準確率(Precision)兩種指標，與DBSCAN算法作對比。之所以引入這兩個指標，是因為在異常檢測算法的結果中，可能有一些異常的數據沒有被檢測到，也可能把一些正常的數據視為異常。Recall指標的意義是衡量異常的數據是否被檢測到的情況，Precision指標的意義是衡量把正常的數據是否視為異常的情況。假定A表示算法找到的異常軌跡中確實是真實的異常軌跡的數量，B表示數據中的真實異常軌跡的總數量，C表示算法所認為的異常軌跡的數量。Recall可以表示為A/B，即算法找出的真正的異常軌跡條數與數據集中的真實異常軌跡條數的比值；Precision可以表示為A/C，即算法找出的真正的異常軌跡條數與算法所認為的異常軌跡數量的比值。為客觀評價，兩種算法均采用自適應方法選取距離閾值。本文所有實驗在Intel Core i5-3570 CPU 3.4 GHz，內存4 GB上運行。具體實驗結果見表1，這兩種指標的值越大表明異常檢測的能力越好。

表1 2種算法的性能指標對比Tab. 1 Performance comparison of two algorithms

在表1中，本文算法并不是在每一項指標中都完全優于DBSCAN算法，因為Recall和Precision兩種指標的側重點不同，且它們之間存在制約關系，所以可能出現此消彼長的情況。為了對比算法異常檢測的綜合性能，可以使F1指標(F1-measure),該指標由式(5)計算:

F1=2PR/(P+R)

(5)

其中：R表示Recall，P表示Precision，該指標的對比結果見表1。從表1可以看出，本文算法在各個數據集上異常檢測的綜合性能基本優于DBSCAN算法。

4 結語

為了對復雜軌跡數據聚類和異常檢測，本文提出了一種軌跡摘要算法。通過重采樣，將軌跡等長化，為后續算法提供了可用的數據，同時對可視化效果也有所提升; 采用自適應閾值，使軌跡相似性的計算更為準確; 利用非局部去噪，將整個軌跡數據集拆分為各個小部分，以便獨立處理，提升了異常檢測效果，算法運行效率也得以提升。在后續研究中，主要工作是考慮將較長軌跡分段處理，同時改進當前異常檢測的方法，以及嘗試提升軌跡摘要可視化效果的方法。

References)

[1] MORRIS B T, TRIVEDI M M. Understanding vehicular traffic behavior from video: a survey of unsupervised approaches[J]. Journal of Electronic Imaging, 2013, 22(4): 041113.

[2] SERMANET P, KAVUKCUOGLU K, CHINTALA S, et al. Pedestrian detection with unsupervised multi-stage feature learning[C]// Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2013: 3626-3633.

[3] LE Q V. Building high-level features using large scale unsupervised learning[C]// Proceedings of the 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2013: 8595-8598.

[4] LAXHAMMAR R, FALKMAN G. Online learning and sequential anomaly detection in trajectories[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6): 1158-1173.

[5] MORRIS B T, TRIVEDI M M. A survey of vision-based trajectory learning and analysis for surveillance[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(8): 1114-1127.

[6] KHAN S S, AHMAD A. Cluster center initialization algorithm forK-means clustering[J]. Pattern Recognition Letters, 2004, 25(11): 1293-1302.

[7] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[C]// Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1996: 83-94.

[8] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[J].Knowledge Discovery and Data Mining, 1996, 96(34): 226-231.

[9] ANKERST M, BREUNIG M, KRIEGEL H P. Ordering points to identify the clustering structure[EB/OL].[2016-06-20].http://www.nwadmin.de/folien-optics.pdf.

[10] WANG W, YANG J, MUNTZ R. STING: a statistical information grid approach to spatial data mining[C]// Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann Publishers, 1997, 97: 186-195.

[11] VLACHOS M, LIN J, KEOGH E, et al. A wavelet-based anytime algorithm fork-means clustering of time series[EB/OL].[2016-06-20].http://cs.gmu.edu/～jessica/publications/ikmeans_sdm_workshop03.pdf.

[12] DABOV K, FOI A, KATKOVNIK V, et al. Image denoising by sparse 3-D transform-domain collaborative filtering[J]. IEEE Transactions on Image Processing, 2007, 16(8): 2080-2095.

[13] JOHNSTONE I M, SILVERMAN B W. Wavelet threshold estimators for data with correlated noise[J]. Journal of the Royal Statistical Society: Series B, 1997, 59(2): 319-351.

[14] ANJUM N, CAVALLARO A. Multifeature object trajectory clustering for video analysis[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(11): 1555-1564.

This work is partially supported by the National Natural Science Foundation of China (61471261, 61179067, U1333110).

WEI Hao, born in 1991, M. S. candidate. His research interests include trajectory analysis and visualization.

XU Qing, born in 1969, Ph. D. professor. His research interests include visualization analysis, machine learning, motion trajectory analysis.

Redundant group based trajectory abstraction algorithm

WEI Hao, XU Qing*

(SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300350,China)

In order to cluster and detect anomalies for the trajectory data collected by video surveillance equipment, a novel trajectory abstraction algorithm was proposed. Trajectories were firstly resampled by utilizing the Jensen-Shannon Divergence (JSD) measurement to improve the accuracy of similarity measurement between trajectories. Resampled trajectories in equal length, i.e. with the same number of sampling points, were required by the following non-local denoising. The similarity thresholds of the trajectory were determined adaptively, and the non-local means were used to cluster the trajectory data and identify the abnormal trajectory data. From the perspective of signal processing, the grouping trajectory data was filtered by the hard-thresholding method to get the summary trajector. The proposed algorithm was insensitive to the order of input trajectories and provides visual multi-scale abstractions of trajectory data. Compared with the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm, the proposed algorithm performs better in terms of precision, recall and F1-mearsure.

trajectory abstraction; resampling; non-local denoising; signal processing; multi-scale filtering

2016-10-10;

2016-12-05。 基金項目:國家自然科學基金資助項目(61471261, 61179067, U1333110)。

魏昊(1991—)，男，河南新鄉人，碩士研究生，主要研究方向：軌跡分析與可視化； 徐慶(1969—)，男，湖北漢川人，教授，博士，主要研究方向：可視化分析、機器學習、運動軌跡分析。

1001-9081(2017)05-1503-04

10.11772/j.issn.1001-9081.2017.05.1503

TP391.4

A