交通監控中運動目標軌跡的距離計算和聚類

李明之，馬志強，單 勇，張曉燕

（空軍工程大學 電訊工程學院，陜西 西安710077）

0 引 言

在交通監控系統的智能化［1］研究中，軌跡分析是目標行為分析和理解的一個重要方法，如：通過對車輛行駛軌跡的分析，可以判別車輛是否發生逆行、違規轉彎等異常情況。而軌跡的距離計算和聚類是軌跡分析的基礎，軌跡距離計算和分類是否準確，將直接影響著軌跡分析的效果。

軌跡距離主要用于衡量兩條軌跡的相似程度，是軌跡聚類的前提條件。傳統軌跡距離計算方法［2］主要考慮目標軌跡的空間位置關系，但在現實當中，對于同一位置的軌跡也可以是由不同運動方向、不同運動速度或者不同尺寸大小的目標運動得到的，如果僅從空間位置關系計算軌跡間距離，將不利于后期對軌跡的聚類和目標識別。因此，部分學者提出將目標運動方向、運動速度等參數融入到軌跡距離計算當中。比如：文獻 ［3］提出利用軌跡的空間位置特征和運動方向特征計算軌跡間距離，從而可以區分不同空間位置不同方向的目標軌跡；文獻 ［4－5］在利用空間位置特征計算軌跡距離的基礎上加入了速度特征，從而可以區分不同空間位置不同速度的目標軌跡。

獲得軌跡間的距離后，就可以對監控場景中的運動目標軌跡進行分類，從而實現目標行為描述并探測場景中的異常事件。目前軌跡聚類方法主要有：層次聚類［3］、K均值聚類［6］、譜聚類［7］和基于神經網絡的聚類［8］等方法，其中，層次聚類方法簡單，但傳統的層次聚類方法對不完整軌跡進行聚類時的準確性不高，需要對其進行改進；譜聚類和基于神經網絡的聚類方法聚類效果較好，但計算復雜，難以滿足實時性要求；K均值聚類法計算簡單，但需要預先估計聚類數目K和聚類中心，文獻 ［6］采用預先人工確定K值，以及隨機選擇初始化聚類中心的方法，智能化程度不高，而且聚類結果容易陷入局部最優解。

針對軌跡距離計算和聚類算法中的主要問題，本文首先對軌跡距離計算方法進行了改進，提出將軌跡之間的距離用空間距離、速度距離、方向距離和尺寸距離4項加權求和表示，從而提高了對不同位置、不同速度、不同方向和不同尺寸運動目標的區分能力；其次，針對交通目標運動軌跡比較規律的特點，采用統計的方法對基于K均值的軌跡聚類算法進行了改進，解決了聚類數目K值和聚類初始中心的自適應確定問題。

1 軌跡距離計算

1.1 軌跡的描述

軌跡是目標運動的一系列質心點連接而成。運動目標的軌跡由目標跟蹤算法生成，給定目標的圖像序列，跟蹤算法按照等間隔Δt進行采樣，每次采樣都可以得到目標的質心位置，按順序連接不同時刻目標的質心即可得到運動軌跡。

傳統軌跡描述方法［2］主要用空間坐標來表示軌跡，如ai＝＜＞，這種方法的主要缺點是軌跡的分類不夠細、識別率不高。為了區分不同位置、不同速度、不同方向和不同尺寸運動目標的軌跡，提高軌跡聚類和目標識別的有效性，受文獻 ［9］啟發，本文利用目標運動的空間坐標、運動速度、運動方向和目標尺寸來描述目標的運動軌跡。

對軌跡集合中的任意一條軌跡A表示為

式中：ai——軌跡A的第i個采樣點，N——目標運動持續的采樣次數，——目標質心在第i次采樣中的二維空間坐標，——第i次采樣中目標的面積，用以表示目標的尺寸信息，，——第i次采樣中目標的速度大小和方向信息，其表示式分別為

式中：Δt——軌跡觀測采樣的時間間隔，式（3）中，設置系數M的原因是由于反余弦函數的取值范圍為 ［0，π］，而實際中目標運動方向的取值范圍為 ［0，2π］，因此，在計算目標運動方向角時需要在反余弦函數的基礎上加上π。M 值的確定可根據－和－的正負情況判定運動方向所在的坐標象限，當方向角在1、2象限時，M取0，方向角在3，4象限時，M取1。

1.2 軌跡的距離計算

根據軌跡的描述方法，在軌跡距離計算時，也相應的引入軌跡的空間距離dh、速度距離dv、方向距離dθ和尺寸距離ds，分別表示目標軌跡在空間位置、運動速度、運動方向和目標尺寸上的差別大小。然后將各項距離加權求和得到目標軌跡間的最終距離，如式（4），用以表示兩條軌跡的綜合差異程度

式中：kh、kv、kθ、ks——權重系數，分別表示軌跡A、B之間的空間距離、速度距離、方向距離和尺寸距離對總的距離的影響程度，kh、kv、kθ、ks的取值范圍為 ［0，1］，且滿足kh＋kv＋kθ＋ks＝1，取值大小應根據實際應用中的具體要求進行初步設置，并通過多次試驗，選取區分效果最好，識別率最高時候的值。比如：在對高速路上的交通目標進行軌跡距離計算和聚類時，由于高速路上的目標主要是車輛，尺寸、速度相差不大，因此主要考慮目標的空間位置和運動方向對軌跡的影響，而不用考慮運動速度和尺寸，所以kh、kθ取較大的值，kv、ks取較小的值或0。而對混合交通的目標進行軌跡距離計算和聚類時，由于需要區別人和車輛的運動軌跡，因此需要適當加大kv、ks的取值。

常用的軌跡距離計算方法［10］有：歐氏距離（Euclidean）［11］、Hausdorff距離［12］、LCSS（longest common subsequence）［13］和 DTW（dynamic time warping）［14］等。其中，歐氏距離要求兩條軌跡等長，而且對時序變化較為敏感，容易受噪聲的影響；Hausdorff距離的優點是可以對兩條不同長度的軌跡進行編碼，但其時間消耗率較高且沒有考慮軌跡方向的影響；LCSS和DTW能有效地對軌跡距離進行度量，但其更適合于描述柔性物體的形狀變化軌跡。

考慮到Hausdorff距離可以對不同長度的軌跡進行距離計算，因此，軌跡的空間距離dh（A，B）和速度距離dv（A，B）均采用改進的Hausdorff距離［9］進行計算。軌跡空間距離僅考慮軌跡的前2維信息，即軌跡點的空間位置坐標。對于軌跡A上的任意一點ai，在軌跡B上有距離ai最近的點滿足

那么，軌跡A，B的空間有向距離表示為

式中：NA——A的軌跡點個數。

則A、B之間的空間對稱距離為

軌跡的速度距離dv（A，B）計算與空間距離dh（A，B）計算基本相同，不同之處在于：空間距離計算中的點與點之間的距離計算公式換成速度差距計算公式

軌跡的方向距離和尺寸距離主要考慮目標運動平均方向和目標平均尺寸（考慮部分遮擋的情況）的差別，因此，軌跡A和B之間的方向距離dθ（A，B）和尺寸距離ds（A，B）均采用平均差方法進行計算

在空間距離dh（A，B）、速度距離dv（A，B）、方向距離dθ（A，B）和尺寸距離ds（A，B）都計算出來后，再將各距離縮放到 ［0，1］范圍內，最后通過式（4）得到軌跡間總的距離。

2 軌跡的聚類

在軌跡距離計算過程中，由于綜合考慮了目標空間位置、運動速度、運動方向和尺寸大小4個參數，相對于只考慮空間位置信息的距離計算，計算量增大，所以為了提高時效性，本文采用計算相對簡單的K均值算法對軌跡樣本進行聚類。

傳統K均值聚類算法［6］需要預先人工確定聚類數目K和初始化聚類中心，無法滿足視頻監控的智能化要求。為此，本文針對交通目標運動軌跡比較規律的特點，提出一種基于統計的K均值聚類初始化方法，可以自動的確定聚類數目K和初始化聚類中心。

提出該方法的基本依據：

（1）在一般的交通場景中，車輛和行人等運動目標都是按照一定的路線、速度和方向行駛的，運動軌跡比較規律，歸類相對比較清楚。

（2）相同類軌跡間距離小，方差也小，不同類軌跡間距離大，方差也大。

（3）初始聚類中心的選則遵循類內軌跡數最多，且各聚類中心分屬不同類的原則。

K均值聚類的具體過程：

（1）建立軌跡距離矩陣。假設Ω為L條訓練軌跡序列的集合，其中Ω＝｛A1，A2…AL｝，每一個元素Ai為一個軌跡序列，對每兩個軌跡序列利用式（4）進行距離計算，得到d（Ai，Aj），對所有軌跡序列進行計算則得到一個L×L的距離矩陣D，其中Di，j＝d（Ai，Aj），如圖1所示。

（2）確定聚類個數K。將距離矩陣D中的元素建立統計圖，如圖2（a），橫坐標表示軌跡距離，縱坐標相同軌跡距離段的個數，并對其進行平滑處理，得到圖2（b）。圖2為軌跡聚類實驗2中的試驗結果。

從圖2可以發現：曲線有多個凸峰，每個凸峰表示在某個距離段中的軌跡對達到極大值，那么可以認為除去0點附近凸峰外，其他每個凸峰的橫坐標都可以表示為兩個軌跡類之間的代表距離，而0點附近的凸峰的橫坐標表示為類內軌跡之間的代表距離。

（3）初始化聚類中心。首先，設定初始歸類閾值ρ。考慮到各類軌跡間的距離最小值為d1，因此可以設定初始歸類閾值為ρ＝d1/2。當滿足（9）式時，軌跡Ai與Aj判別為一類，不滿足時，判別為不同類

然后，選擇同類軌跡個數最多的軌跡作為第一類初始化聚類中心，方法是通過統計距離矩陣D中各行元素中滿足Di，j≤d1/2的個數Di，j，取得最大值的行所對應的軌跡作為第一類中心Ao1。然后，選擇同類軌跡個數次多的軌跡作為第二類中心Ao2，但為了區別第一類，軌跡Ao1和Ao2需滿足Do1，o2＞d1，這樣就避免了隨機選擇初始化中心方法中容易出現的所選中心在同一類中的問題，以此類推，選出K個聚類的初始化中心。

（4）對訓練樣本進行二次歸類。方法是：比較所有軌跡樣本Ai與各個初始化中心Aoj的距離d（Ai，Aoj），將所有的軌跡樣本歸類到與它距離最近的初始化聚類 “中心”所在的類

（5）調整聚類 “中心”。由步驟（4）可得到對應每類的樣本個數L1，L2，…Lk，對每一類，找出屬于該類的所有樣本，尋找一個新的代表，使其到該類內所有樣本的距離之和最小，該樣本即為新的聚類 “中心”

（6）重復步驟（4）和（5），直到連續兩次的迭代結果（即聚類中心）不再發生變化為止。此時的 “中心”就是聚類的 “中心”，各個類中的樣本就屬于同一類軌跡模式。

3 仿真實驗

為驗證本文提出的軌跡距離計算方法和聚類方法的有效性和適用性，分別對3個交通視頻進行了仿真實驗。試驗系統建立在1G內存的普通PC機上，仿真軟件采用Matlab 7.8，運動目標軌跡數據的提取采用文獻 ［15］的粒子濾波跟蹤算法。

3.1 軌跡距離計算實驗

為驗證本文提出的軌跡距離計算方法，分別采用文獻［3］、文獻 ［4］和本文提出的方法對Traffic＿1視頻（avi格式，320×240，25幀/s）進行軌跡距離計算實驗。本文算法中權重系數分別取kh＝0.4、kv＝0.2、kθ＝0.2、ks＝0.2。一共提取了23條軌跡進行了仿真實驗，抽取了4條有代表性的軌跡和實驗數據進行分析。如圖3所示，4條軌跡分別采用不同顏色進行區分，軌跡1為一輛車行走的軌跡，軌跡2、3、4是3個不同的人行走的軌跡，天藍色箭頭表示軌跡運動的方向。

圖3 場景Traffic＿1的軌跡

表1 軌跡距離統計

對表1的軌跡距離數據進行分析。首先，對采用本文方法得到的各軌跡距離進行對比分析，可以發現：空間距離中，軌跡2和軌跡3的距離最小，軌跡1到軌跡4的距離最大，與圖1相符合；速度距離中，軌跡2、3、4之間的距離都很小，而軌跡1到軌跡2、3、4的距離都很大，說明目標2、3、4的速度差小，目標1與目標2、3、4的速度差都大；相位距離中，軌跡1和軌跡2的距離最小，軌跡3和軌跡1、2的距離較大，說明目標1與目標2方向相近，目標3與目標1、2的方向相差大；尺寸距離中，軌跡1與軌跡2、3、4的距離都較大，而軌跡2、3、4之間的距離都較小，說明目標1與目標2、3、4的尺寸相差大，而目標2、3、4之間的尺寸相差小；總的距離中，所有軌跡間距離都比較大，其中軌跡1與軌跡4的軌跡距離最大，而軌跡2與軌跡3的距離最小；以上實驗數據分析結果與實際情況和理論分析都相符合。然后，對采用本文算法得到的軌跡間總的距離與采用文獻 ［3］和文獻 ［4］的方法得到的數據進行對比分析，可以發現：文獻 ［3］方法得到的數據中，軌跡1與軌跡2的距離很小，其他的數據都比較大，原因是由于該方法是利用軌跡的空間位置特征和運動方向特征計算軌跡間距離，所以距離計算結果受軌跡位置和運動方向的影響比較大；文獻 ［4］方法得到的數據中，軌跡2與軌跡3的距離很小，其他的數據都比較大，原因是由于該方法是利用軌跡的空間位置特征和運動速度特征計算軌跡間距離，所以距離計算結果受軌跡位置和運動速度的影響比較大；而本文所得的軌跡距離數據都比較大，原因是由于本文方法綜合考慮了目標運動軌跡的空間位置、速度、方向和尺寸信息，所以距離計算結果受軌跡位置和運動速度、運動方向和尺寸大小的綜合影響。

3.2 軌跡聚類實驗1

為驗證本文提出的軌跡聚類算法的有效性，對Traffic＿2視頻（avi格式，320×240，25幀/s）進行了仿真實驗。距離計算中權重系數取 kh＝0.4、kv＝0.25、kθ＝0.1、ks＝0.25，一共提取了80條軌跡進行了仿真實驗，主要提取的軌跡為3個不同方向的機動車行駛軌跡，以及人行道上的人或自行車的行走軌跡，如圖4（a）所示。

圖4（b）為采用本文方法進行軌跡聚類時得到的軌跡距離統計圖，圖中曲線的凸峰個數為7個，根據文章中聚類個數計算方法可自動得到k＝4，與實際情況相符。圖4（c、d、e）為軌跡聚類效果圖，從圖可以發現：3種方法軌跡聚類個數都是4個，而且向上行走車輛和向下行走車輛的軌跡聚類效果都相對較好，聚類效果相差較大的地方主要集中于人行道上行人軌跡和水平方向的車輛軌跡的聚類效果。主要原因在于水平方向的這兩種軌跡在空間分布上比較相似而且距離相近，因而空間距離較小，難以區分。文獻［3］的方法由于在軌跡聚類時主要考慮軌跡的空間位置特征和運動方向特征，因而當水平方向行駛的車輛與行人相距較近而且運動方向相同時，區分難度較大，如圖4（c）所示；同理，文獻 ［4］的方法由于在軌跡聚類時主要考慮軌跡的空間位置特征和運動速度特征，因而對與車輛相距較近而且運動速度相近的行人（如：自行車）的軌跡難以區分，如圖4（d）所示；本文方法由于考慮了軌跡的空間位置、運動速度、運動方向和尺寸特征，因而聚類效果有一定的提高，如圖4（e）所示。

圖4 場景Traffic＿2的聚類效果

表2 聚類效果對比

3.3 軌跡聚類實驗2

為驗證本文提出的軌跡聚類算法的適用性，對Traffic＿3視頻（avi格式，320×240，25幀/s）進行了仿真實驗。距離計算中權重系數仍然取kh＝0.4、kv＝0.25、kθ＝0.1、ks＝0.25，采用同樣的跟蹤和軌跡聚類方法，處理50條軌跡，同樣得到了符合場景的聚類結果，如圖5所示。實驗結果表明此方法對于試驗中場景Traffic＿3也是適用的。

圖5 場景Traffic＿3的聚類效果

需要說明的是：文中K均值聚類的初始化方法在軌跡類的空間分布都均勻對稱，運動速度、運動方向和目標類型也一致相同的情況下，軌跡間距離相差不是很明顯，如果曲線平滑不夠理想，初始化聚類個數和聚類中心選擇可能會與實際情況存在一定的偏差，但這種情況一般是比較少見的，因此，可以認為本文提出的軌跡聚類算法的適用性。

4 結束語

針對交通監控中運動目標的軌跡距離計算問題和聚類問題，本文主要做了兩方面工作：一是改進了軌跡距離計算方法，通過引入目標的空間坐標、速度、方向和尺寸4個參數，提高了對運動目標軌跡的區分能力；二是采用統計的方法對基于K均值的軌跡聚類算法進行了改進，解決了聚類數目K值的自適應確定和聚類初始中心的選擇問題。通過對真實場景的仿真實驗，驗證了本文提出的軌跡距離計算和聚類方法的有效性和適用性。軌跡距離計算和軌跡聚類是軌跡分析和行為理解的基礎，因此，本文的研究結果對于進一步的目標分類和行為理解等研究，具有一定的參考價值。

［1］Valera M，Velastin S A.Intelligent distributed surveillance systems：A review ［C］.Proceedings of the Vision，Image and Signal Processing，2005：192－204.

［2］Hwang J R，KANG H Y，LI K J.Spatio－temporal similarity analysis between trajectories on road networks ［C］.Proceedings of the 24th International Conference on Perspectives in Conceptual Modeling，2005：280－289.

［3］HAO Jiuyue，LI Chao，GAO Lei，et al.Moving object trajectory clustering method in intelligent surveillance video ［J］.Journal of Beijing University of Aeronautics and Astronautics，2009，35（9）：1083－1087（in Chinese）.［郝久月，李超，高磊，等.智能監控場景中運動目標軌跡聚類算法 ［J］.北京航空航天大學學報，2009，35（9）：1083－1087.］

［4］WEN Jia，CUI Wei.Extraction and clustering of vehicle’s trajectories from live video ［J］.Computer Engineering and Applications，2010，46（11）：155－157（in Chinese）. ［聞佳，崔維.實時視頻中的車輛運動軌跡的提取和聚類 ［J］.計算機工程與應用，2010，46（11）：155－157.］

［5］WANG X G，TIEU K，Grimson E.Learning semantic scene models by trajectory analysis ［G］.LNCS 3953：Proceedings of the 9th European Conference on Computer，2006：110－123.

［6］PAN Qiming，ZHOU Wenhui，CHENG Yongmei.Trajectory classification and recognition of moving objects ［J］.Fire Control ＆ Command Control，2009，34（11）：79－83（in Chinese）.［潘奇明，周文輝，程詠梅.運動目標軌跡分類與識別［J］.火力與指揮控制，2009，34（11）：79－83.］

［7］KONG Wanzeng，SUN Zhihai，YANG Can，et al.Automatic spectral clustering based on eigengap and orthogonal eigenvector ［J］.Acta Electronica Sinic，2010，38（8）：1880－1885（in Chinese）.［孔萬增，孫志海，楊燦，等.基于本征間隙與正交特征向量的自動譜聚類 ［J］.電子學報，2010，38（8）：1880－1885.］

［8］YUAN Hejin，ZHANG Yanning，ZHOU Tao，et al.Trajectory pattern learning approach based on cascade competitive neural networks and graph search method ［J］.Journal of System Simulation，2008，20（4）：841－845（in Chinese）.［袁和金，張艷寧，周濤，等.基于級聯網絡和圖搜索的軌跡模式學習算法［J］.系統仿真學報，2008，20（4）：841－845.］

［9］HU Hongyu.Research on methods for traffic event recognition based on video processing ［D］.Changchun：Jilin University PhD Dissertation，Changchun，2010（in Chinese）.［胡宏宇.基于視頻處理的交通事件識別方法研究 ［D］.長春：吉林大學博士學位論文，2010.］

［10］ZHANG Z，HUANG K，TAN T N.Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes［C］.Proceedings International Conference on Pattern Recognition.Piscataway，N J：IEEE Press，2006：1135－1138.

［11］FU Zhouyu，HU Weiming，TAN Tieniu.Similarity based vehicle trajectory clustering and anomaly detection ［C］.Italy：Proceedings of the IEEE International Conference on Image Processing，2005：602－605.

［12］QU Lin，ZHOU Fan，CHEN Yaowu.Trajectory classification based on Hausdorff distance for visual surveillance system［J］.Journal of Jilin University，2009，39（6）：1618－1624（in Chinese）.［曲琳，周凡，陳耀武.基于 Hausdorff距離的視覺監控軌跡分類算法 ［J］.吉林大學學報，2009，39（6）：1618－1624.］

［13］Fashandi H，Moghaddam A M E.A new rotation invariant similarity measure for trajectories ［C］.Finland：Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation，2005：631－634.

［14］Junejo I N，Foroosh H.Trajectory rectification and path modeling for video surveillance［C］.Proceedings of the IEEE International Conference on Computer Vision.Brazil IEEE Press，2007：1－7.

［15］LIU Huaping，SUN Fuchun，HE Kezhong.Symmetry－aided particle filter for vehicle tracking ［C］.Italy：IEEE International Conference on Robotics and Automation， 2007：4633－4638.