一種健壯的超像素跟蹤算法①

郭 利,周盛宗,3,付璐斯,于志剛

1(中國科學院 福建物構所,福州 350002)

2(福建師范大學 數學與計算機科學學院,福州 350117)

3(中北大學 計算機與控制工程學院,太原 030051)

一種健壯的超像素跟蹤算法①

郭 利1,2,周盛宗1,2,3,付璐斯1,3,于志剛1,3

1(中國科學院 福建物構所,福州 350002)

2(福建師范大學 數學與計算機科學學院,福州 350117)

3(中北大學 計算機與控制工程學院,太原 030051)

在目標跟蹤中,傳統的超像素跟蹤算法在發生遮擋等情況后,會將非目標超像素標記為目標加入到特征空間. 在對候選樣本置信度計算中,利用特征空間中最近鄰超像素來劃定樣本中超像素的簇歸屬會產生錯誤; 而依據的近鄰超像素數量過多時,又會造成分類誤差的積累. 為解決上述問題,本文提出一種健壯的超像素跟蹤算法. 本算法以貝葉斯算法為框架,首先,將前幾幀進行超像素切割,提取特征并使用均值漂移聚類算法和基于超像素的外觀表示模型進行分類和計算類置信度,放入特征空間中. 其次,根據接下來幾幀的平均中心誤差確定最佳近鄰數目. 最后,在跟蹤過程中,對獲取幀的指定區域進行超像素切割,提取特征、進行軟分類和計算置信度; 根據上一幀目標位置進行高斯采樣,累加樣本內超像素置信度,獲得樣本置信度; 在發生嚴重遮擋時,不進行滑動窗口更新和外觀模型修改,使用當前模型繼續跟蹤. 與傳統的最近鄰超像素算法相比,本算法能夠有效提升跟蹤成功率和降低平均中心誤差.

最佳近鄰數目; 軟分類; 目標跟蹤; 均值漂移算法; 置信度; 遮擋

運動目標跟蹤是機器視覺研究的一個基本課題,在視頻監控、運動分析、人機交互和自動駕駛等領域中發揮著重要作用. 目標跟蹤是從一系列圖像中,確定目標在每幀圖像中的位置、方向、面積、形狀等. 由于受光照強弱、相機顛簸、物體遮擋、形態變化、速度調整等因素的影響,目標外觀發生了很大的變化,從而使得目標跟蹤非常有難度. A.Yilmaz等[1]認為目標跟蹤主要分為點跟蹤、核跟蹤、剪影跟蹤三類. 點跟蹤主要包括確定法和統計法,代表性的方法有MGE[2]、GOA[3]、卡爾曼濾波[4]、JPDAF[5]、PMHT[6]等; 核跟蹤主要包括基于模板和密度的外觀模型、多角度外觀模型等,前者的代表性方法有Mean-Shift[7]、KLT[8]、分層[9],后者的代表性方法有特征值跟蹤[10]、支持向量機跟蹤[11]; 剪影跟蹤主要包括輪廓演變、形狀匹配,前者的代表性方法有狀態空間模型[12]、變量方法[13]、啟發方法[14]. 這些數算法大都是圍繞著目標表示、特征選擇、運動建模、外觀表示、形態變化等五個方面進行改進,在特定場景下取得了不錯的效果. 在目標運動中,自適應外觀算法[15-20]能夠很好的表示外觀的變化,但基于低層特征的自適應外觀算法在前后幀的關聯上表現很差; Kwon等[21]提出的基于多運動模型和改進觀測模型的粒子濾波框架能較好的處理遮擋、尺度、光照和尺度等因素引起的外觀變化,由于未區分目標、背景,會出現跟蹤目標丟失. Ren等[22]提出的超像素跟蹤算法,使用Delaunay三角化和條件隨機場單獨對每幀完整圖做區域匹配,能夠對前景、背景有限分割,但仍然無法處理跟蹤過程中的遮擋、復雜背景等問題.Yant等[23]提出的健壯超像素跟蹤算法,在有限遮擋、光照變化、姿態變化、復雜背景等情況下,都取得不錯效果,但由于遮擋等情況下,劃定到特征空間中的超像素在目標、背景劃分及簇歸屬上會存在一些錯誤,僅根據特征空間中離其最近的超像素的簇歸屬來劃定簇是錯誤的; 同樣,依據的超像素數量過多時,又會造成分類誤差的積累,有限數目超像素來確定當前超像素簇歸屬會更有效. 因此,提出一種健壯的超像素跟蹤算法,該算法根據歷史樣本匹配度尋找最佳近鄰數目,使用貝葉斯框架構造聯合外觀模型,使用基于超像素的判別型外觀模型將前景對象從背景中區分開來.

1 算法的主要部分

1.1 確定最佳近鄰個數

如圖1,K=5時,黃色橢圓的最近5個鄰居是2個綠色正方形和3個紅色三角形,K-近鄰判別法判定黃色橢圓與紅色三角形同類; K=9時,黃色橢圓的最近9個鄰居是5個綠色正方形、3個紅色三角形和1個深紅梯形,K-近鄰判別法判定黃色橢圓與綠色正方形同類.

圖1 不同近鄰對分類的影響

其中,

1.2 貝葉斯跟蹤框架

給定t時刻的狀態Xt、所有的觀測值Y1:t,設定歸一化項為α,計算最大后驗分布[23],具體如式(2).

1.3 基于超像素的外觀區分模型

正值越大,簇屬于目標的置信度越高,反之亦然.

1.4 基于k近鄰的置信度計算

當新幀到來時,使用高斯采樣提取目標的周邊區域,根據當前超像素與簇空間中超像素的距離來計算置信度,并確定置信度最高的樣本為跟蹤目標. 在遮擋等情況下,超像素在目標、背景的劃分上較難,僅依據空間中最近鄰的超像素來劃定簇歸類不準確. 因為置信度與兩個因素有關: 距離較近的超像素所屬的簇、在特征空間中超像素與簇中心的距離. 取定近鄰超像素的個數為 k=k*,距離分別為D1,D2,...,Dk,則:

1.5 觀察和運動模型

設定運動模型為高斯分布[23],

觀測模型[23]:

1.6 針對遮擋和漂移的在線更新

使用滑動窗口機制進行跟蹤,每U幀,添加一個新幀到H幀序列中,并刪除序列中的第k幀(k

大于零時,表示當前幀的平均準確率評估的置信度比保存序列中的規范化置信度的平均值小,超過一定閾值時,候選區域可能屬于背景區域,或發生嚴重遮擋.

2 算法的實現過程

2.1 初始化

fort= 1 tom(設定m=4)

1) 初始化t幀的各個參數.

End

2.2 學習近鄰數目

fort=m+1 ton(設定n=15)

1) 切割Xt周邊區域為Nt個超像素,提取特征. 使用公式(6)、(7)計算目標背景置信度.

4) 依據公式(1),獲取最佳后驗時的近鄰數目k.

5) 使用公式(12)來探測嚴重或完全遮擋.

6) 每隔U幀,添加一幀到更新序列.

7) 每隔W幀,更新一次外觀模型.

2.3 跟蹤

fort=n+1 to 幀數

1) 切割Xt周邊區域為Nt個超像素,提取特征. 使用公式(6)、(7)計算值目標背景置信度.

5) 使用公式(12)來探測嚴重或完全遮擋.

6) 每隔U幀,添加一幀到更新序列.

7) 每隔W幀,更新一次外觀模型.

End

3 實驗結果及分析

實驗在CPU為3.6 GHZ、內存為8 G的PC機上進行,采用 Matlab2012b、Microsoft Visual Studio 2010混合編程實現.

3.1 實驗設置

HIS顏色空間降低了像素受光照變化的影響,在區分不同超像素方面,比其他顏色空間的區分能力更強,使用HIS顏色空間中的規范化圖表作為每個超像素的特征. 使用SLIC算法切割圖片時,空間近似權值設置為10,超像素數目設置為300,均值漂移聚類算法的尺度設置為0.18.

在初始階段,為了獲取訓練集,前4幀的目標區域可以通過目標定位器或手動獲取. 按照經驗,設置H=15,U=1,W=10,速度變化 σc=7.6,尺度變化 σs=7. 為簡化遮擋探測,設置 μc=0.5.

3.2 實驗結果及分析

表1對比了IVT[25](不斷學習的健壯跟蹤)、Frag[18](使用積分直方圖的基于碎片的健壯跟蹤算法)、MIL(在線的多實例學習的視覺跟蹤)、VTD[26](視覺跟蹤分解)、L1[27](使用加速接近梯度算法的實時健壯L1跟蹤)、TLD[28](基于機構約束的增強二進制分類器)、Struck[29](基于核的機構性輸出跟蹤)、SPT[23](基于超像素的目標跟蹤)、KSPT(基于有限學習的軟分類超像素跟蹤算法)在Lemming、liquor、basketball、bolt等數據集上中心定位錯誤的幀數上,KSPT都是最少的.

表1 中心定位錯誤的幀數

表2對比了 IVT[25]、Frag[18]、MIL、VTD[26]、L1[27]、TLD[28]、Struck[29]、SPT[23]、KSPT 在 Lemming、liquor、basketball、bolt等數據集上成功跟蹤到的幀數,KSPT 都是最多的.

表2 成功跟蹤到的幀數

表3對比了SPT[23]、KSPT在surfing1、singer1、woman、girl_move等數據集上的成功率,KSPT比SPT都有了很大提升. 這是因為超像素空間中,各類在簇的劃分上,并不絕對準確,最近鄰超像素跟蹤算法只依據與超像素空間最近鄰的超像素進行分類,易發生分類錯誤. 而通過訓練過程,學習出最佳的近鄰數目,引導超像素分類,一定程度增加了待分類的超像素的容錯程度,提升了超像素置信度計算的準確度,從而提高算法對目標的跟蹤能力.

表3 成功率 (%)

圖2中,不同近鄰個超像素的SPT在Lemming數據集第16～25幀上的位置誤差情況,1、10、200近鄰個超像素的SPT對應位置總誤差59.3936、36.3729、70.3006像素; 10近鄰個超像素(*型實線)的SPT表現最好,其他近鄰的SPT總誤差相對較大. 在此10幀的跟蹤中,10近鄰超像素的SPT表現更為穩定,誤差相對最小. 根據該 10 幀,推測出 KSPT 中最佳 K=10; 而事實上,在26～800幀上,10近鄰的SPT表現也最好,其中370～430、460～600幀表現最明顯,見圖3、圖4.

圖2 不同近鄰個超像素的SPT的位置誤差

圖3 不同近鄰個超像素的SPT的位置誤差

圖3中,不同近鄰個超像素的SPT在Lemming數據集第370～430幀上位置誤差,1、10、200近鄰個超像素的SPT對應位置總誤差9088.5、275.3、12043像素; 10近鄰個超像素(*型實線)的SPT表現最好,其他近鄰的SPT總誤差相對較大.

圖4中,不同近鄰個超像素的SPT在Lemming數據集第460～600幀上的位置誤差情況,1、10、200近鄰個超像素的SPT對應位置誤差31904、779、2594像素.

圖4 不同近鄰個超像素的SPT的位置誤差

圖5中,不同近鄰個超像素的SPT在skating1數據集第16～25幀上位置誤差,1、10、20近鄰個超像素的SPT對應位置總誤差為60.8563、40.4681、56.9368像素; 10近鄰個超像素(*型實線)的SPT表現最好,其他近鄰的SPT總誤差相對較大. 在此10幀的跟蹤中,10近鄰超像素的SPT表現更為穩定,誤差相對最小. 根據該 10 幀,推測出 KSPT 中最佳 K=10; 而事實上,10近鄰超像素的SPT在26～300幀上,10近鄰的SPT表現也很好,見圖6、圖7. 在75～230幀上,20近鄰的SPT發生跟蹤漂移,跟蹤效果很差,見圖6;260～300幀,1近鄰的SPT發生跟蹤漂移,跟蹤效果也很差,見圖7.

圖5 不同近鄰個超像素的SPT的位置誤差

圖6 不同近鄰個超像素的SPT的位置誤差

圖7 不同近鄰個超像素的SPT的位置誤差

圖6中,不同近鄰個超像素的SPT在skating1數據集第75～230幀上位置誤差情況,1、10、20近鄰個超像素的SPT對應位置總誤差3848、3439、22189像素.

圖7中,不同近鄰個超像素的SPT在第260～300幀上位置誤差情況,1、10、20近鄰個超像素的SPT對應位置總誤差6952.6、862.7、1968.5像素;10近鄰個超像素(*型實線)的SPT表現最好,其他近鄰的SPT總誤差相對較大.

圖8的Lemming數據集中,存在光照變化、尺度變化、不同程度遮擋、快速運動、離面旋轉等情況.在這種背景下,基于歷史外觀模型的IVT由于外觀模型不能很好的應對外觀變化,所以在目標姿態和尺度都變化不大時表現良好,而在姿態和尺度發生較大變化時表現不佳. 基于邊信息的TLD由于未使用基于中層特征的外觀模型,所以在跟蹤姿態、尺度發生較大變化的目標時效果不如KSPT算法. 在跟蹤目標發生遮擋的第332幀、快速運動的第399幀、離面旋轉的第997、1299幀,KSPT均表現出相當的優異性.

圖8 KSPT(細線)、TLD(粗線)、IVT(虛線)在 Lemming 數據集第332、399、997、1299幀上的跟蹤結果.

圖9 KSPT(細線)、TLD(粗線線)、IVT(虛線)在 bolt數據集第20、92、222、350幀上的跟蹤結果.

圖9的Bolt數據集中,存在不同程度遮擋、變形、平面內運動、離面運動等情況. 在這種背景下,基于邊信息的TLD、基于歷史外觀模型的IVT的跟蹤效果卻差了很多,再次印證KSPT依托的中層特征外觀模型的優越性. 在跟蹤目標因為運動引起形變的第20、92、222、350幀,KSPT均表現出相當的優異性.

4 結語

針對現有超像素跟蹤算法僅依據特征池中最近鄰超像素劃定當前超像素簇歸屬造成分類錯誤的問題,本文提出一種健壯的超像素跟蹤算法. 該算法通過歷史樣本的平均中心誤差,確定最佳近鄰個數. 根據最佳近鄰個超像素劃定當前超像素的簇歸屬,減弱了部分遮擋情況下特征置信度對候選樣本的干擾,從而有效提升中心定位成功率和成功跟蹤到的幀數. 考慮到均值漂移聚類算法的耗時性,正在探索其他有效、快速的算法; 運動模型中的速度、尺度參數都是經驗值,不能實現自適應變化,尤其是出現撐桿跳等快速運動情況就很難發揮作用. 另外,鑒于簡單HIS顏色特征尚且取得不錯的效果,相信更好特征的出現,一定能夠很好的提升跟蹤效果.

1Yilmaz A,Javed O,Shah M. Object tracking: A survey.ACM Computing Surveys,2006,38(4): 13. [doi: 10.1145/1177352]

2Salari V,Sethi IK. Feature point correspondence in the presence of occlusion. IEEE Trans. on Pattern Analysis and Machine Intelligence,1990,12(1): 87–91. [doi: 10.1109/34.41387]

3Veenman CJ,Reinders MJT,Backer E. Resolving motion correspondence for densely moving points. IEEE Trans. on Pattern Analysis and Machine Intelligence,2001,23(1):54–72. [doi: 10.1109/34.899946]

4Broida TJ,Chellappa R. Estimation of object motion parameters from noisy images. IEEE Trans. on Pattern Analysis and Machine Intelligence,1986,8(1): 90–99.

5Bar-Shalom Y,Fortmann TE. Tracking and data association.San Diego,CA,USA: Academic Press Professional,Inc.,1988.

6Streit RL,Luginbuhl TE. Maximum likelihood training of probabilistic neural networks. IEEE Trans. on Neural Networks,1994,5(5): 764–783. [doi: 10.1109/72.317728]

7Comaniciu D,Ramesh V,Meer P. Kernel-based object trac-king. IEEE Trans. on Pattern Analysis and Machine Intelligence,2003,25(5): 564–577. [doi: 10.1109/TPAMI.2003.1195991]

8Shi JB,Tomasi. Good features to track. 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,1994. Seattle,WA,USA. 1994. 593–600.

9Tao H,Sawhney HS,Kumar R. Object tracking with Bayesian estimation of dynamic layer representations. IEEE Trans. on Pattern Analysis and Machine Intelligence,2002,24(1): 75–89. [doi: 10.1109/34.982885]

10Black MJ,Jepson AD. EigenTracking: Robust matching and tracking of articulated objects using a view-based representation. International Journal of Computer Vision,1998,26(1):63–84. [doi: 10.1023/A:1007939232436]

11Avidan S. Support vector tracking. Proc. of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2001. Kauai,HI,USA. 2001. 184–191.

12Isard M,Blake A. CONDENSATION-Conditional density propagation for visual tracking. International Journal of Computer Vision,1998,29(1): 5–28. [doi: 10.1023/A:1008 078328650]

13Bertalmio M,Sapiro G,Randall G. Morphing active contours: A geometric approach to topology-independent image segmentation and tracking. Proc. of 1998 International Conference on Image Processing. Chicago,IL,USA. 1998.318–322.

14Kang JM,Cohen I,Medioni G. Object reacquisition using invariant appearance model. Proc. of the 17th International Conference on Pattern Recognition. Cambridge,UK. 2004.759–762.

15Jepson AD,Fleet DJ,El-Maraghi TF. Robust online appearance models for visual tracking. IEEE Trans. on Pattern Analysis and Machine Intelligence,2003,25(10): 1296–1311. [doi: 10.1109/TPAMI.2003.1233903]

16Lim J,Ross DA,Lin RS,et al. Incremental learning for visual tracking. Advances in Neural Information Processing Systems.Vancouver,Canada. 2004. 793–800.

17Collins RT,Liu YX,Leordeanu M. Online selection of discriminative tracking features. IEEE Trans. on Pattern Analysis and Machine Intelligence,2005,27(10): 1631–1643. [doi:10.1109/TPAMI.2005.205]

18Adam A,Rivlin E,Shimshoni I. Robust fragments-based tracking using the integral histogram. 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York,NY,USA. 2006. 798–805.

19Grabner H,Leistner C,Bischof H. Semi-supervised on-line boosting for robust tracking. Proc. of the 10th European Conference on Computer Vision: Part I. Marseille,France.2008. 234–247.

20Kwon J,Lee KM. Tracking of a non-rigid object via patchbased dynamic appearance modeling and adaptive basin hopping monte carlo sampling. IEEE Conference on Computer Vision and Pattern Recognition(CVPR 2009).Miami,FL,USA. 2009. 1208–1215.

21Kwon J,Lee KM. Visual tracking decomposition. 2010 IEEE Conference on Computer Vision and Pattern Recognition(CVPR 2010). San Francisco,CA,USA. 2010. 1269–1276.

22Ren XF,Malik J. Tracking as repeated figure/ground segmentation. IEEE Conference on Computer Vision and Pattern Recognition. Minneapolis,MN,USA. 2007. 1–8.

23Yang F,Lu HC,Yang MH. Robust superpixel tracking. IEEE Trans. on Image Processing,2014,23(4): 1639–1651. [doi:10.1109/TIP.2014.2300823]

24陳桂景,王堯弘. 自適應近鄰判別分析. 數學物理學報,1996,16(S1): 9–19.

25Ross DA,Lim J,Lin RS,et al. Incremental learning for robust visual tracking. International Journal of Computer Vision,2008,77(1-3): 125–141. [doi: 10.1007/s11263-007-0075-7]

26Kwon J,Lee KM. Visual tracking decomposition. 2010 IEEE Conference on Computer Vision and Pattern Recognition(CVPR 2010). San Francisco,CA,USA. 2010. 1269–1276.

27Bao CL,Wu Y,Ling HB,et al. Real time robust L1 tracker using accelerated proximal gradient approach. IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2012). Providence,RI,USA. 2012. 1830–1837.

28Kalal Z,Matas J,Mikolajczyk K. P-N learning: Bootstrapping binary classifiers by structural constraints. 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010). San Francisco,CA,USA. 2010. 49–56.

29Hare S,Golodetz S,Saffari A,et al. Struck: Structured output tracking with kernels. IEEE Trans. on Pattern Analysis and Machine Intelligence,2016,38(10): 2096–2109. [doi:10.1109/TPAMI.2015.2509974]

Robust Superpixes Tracking Method

GUO Li1,2,ZHOU Sheng-Zong1,2,3,FU Lu-Si1,3,YU Zhi-Gang1,3

1(Fujian Institute of Research on the Structure of Matter,Chinese Academy of Sciences,Fuzhou 350002,China)
2(College of Mathematics and Computer Science,Fujian Normal University,Fuzhou 350117,China)
3(School of Computer and Control Engineering,North University of China,Taiyuan 030051,China)

During the object tracking,when occlusion occurs,the traditional superpixel tracking algorithm will add the superpixels of the non-target area into the feature space. In the calculation of the candidate sample confidence,the nearest neighbor superpixel in the feature space is used to delimit the cluster attribution of the superpixels in the sample,and the accumulation of the classification error is caused by the excessive number of neighboring superpixels. To solve the problems above,we propose a robust superpixels tracking method. This algorithm uses Bayesian algorithm as the framework. Firstly,we slice the first few frames into superpixels,extract the feature,use the mean shift clustering algorithm and representation model based on superpixel to classify and calculate the class confidence value,and put the feature into feature space. Secondly,the suitable numbers of neighbors can be found with the mean center error of next few frames. Last but not least,during the tracking process,the superpixel is segmented in the specified area of the acquired frame,to extract the feature. The cluster is confirmed with soft classification and the confidence value is calculated. According to the previous frame target position,the Gaussian sampling is collected. We can obtain the sample confidence value with the accumulation of the confidence value. In case of severe occlusion,the sliding window update and the appearance model modification are not carried out,and we continue to use the current model to track. Compared with the traditional tracking algorithm based on nearest superpixel,the algorithm can effectively improve the tracking success rate and reduce the average center errors.

best number of nearest neighbors; soft classification; object tracking; meanshif; confidence; occlusion

郭利,周盛宗,付璐斯,于志剛.一種健壯的超像素跟蹤算法.計算機系統應用,2017,26(12):130–136. http://www.c-s-a.org.cn/1003-3254/6120.html

2017-03-16; 修改時間: 2017-04-05; 采用時間: 2017-04-17