376 36, Kalman,.,,.,. 2,,,,. 2)., ( 2).. Mean shft. ( ) ( ),.,,,,.,,,,,,,.,,.,,.,,,,.,. Elgammal [16], ( ),,,. Cucchara [10]. Belezna [11] Mean shft,

Size: px

Start display at page:

Download "376 36, Kalman,.,,.,. 2,,,,. 2)., ( 2).. Mean shft. ( ) ( ),.,,,,.,,,,,,,.,,.,,.,,,,.,. Elgammal [16], ( ),,,. Cucchara [10]. Belezna [11] Mean shft,"

蜃水
5 years ago
Views:

1 36 3 Vol. 36, No ACTA AUTOMATICA SINICA March, ,. : 1) ; 2), ; 3), ( 2),,. IBM. DOI,,, /SP.J A Greedy Searchng Algorthm for Multple Object Trackng and Occluson Handlng YANG Tao 1 LI Jng 2 PAN Quan 3 ZHANG Yan-Nng 1 Abstract Ths paper presents a novel real-tme multple object trackng algorthm, whch contans three parts: regon correlaton based foreground segmentaton, mergng-splttng based data assocaton and greedy searchng based occluded object localzaton. The man characterstcs of the proposed algorthm are summarzed as follows: 1) the multple object trackng and occluson handlng problem s successfully changed nto an mage classfcaton problem wth pror knowledge of object number and feature; 2) a hghly effcent greedy searchng method s presented to meet real-tme capablty; 3) t has good performance n expansblty, and t has no constrants about the number of occluded objects, the occluson rato and the object s moton model. Experment results wth hand labeled IBM database demonstrate that the method s effectve and effcent. Key words Multple object detecton and trackng, occluson handlng, greedy searchng, ntellgent vdeo survellance,. [1 16]., Manuscrpt receved October 22, 2008; accepted January 21, 2009 (863 ) (2009AA01Z315), ( , , ), (708085) Supported by Natonal Hgh Technology Research and Development Program of Chna (863 Program) (2009AA01Z315), Natonal Natural Scence Foundaton of Chna ( , , ), and Cultvaton Fund of the Key Scentfc and Techncal Innovaton Project, Mnstry of Educaton of Chna (708085) Shaanx Key Laboratory of Speech and Image Informaton Processng, School of Computer Scence, Northwestern Polytechncal Unversty, X an School of Telecommuncatons Engneerng, Xdan Unversty, X an School of Automaton, Northwestern Polytechncal Unversty, X an : 1) ; 2) ; 3) ; 4) ; 5)., 1) 5), 2), ( 3) ( 4).,., ;,. 1),,,.,,,. McKenna [13] Bremond [14],. Pater [15]

2 376 36, Kalman,.,,.,. 2,,,,. 2)., ( 2).. Mean shft. ( ) ( ),.,,,,.,,,,,,,.,,.,,.,,,,.,. Elgammal [16], ( ),,,. Cucchara [10]. Belezna [11] Mean shft, Mean shft., : Cucchara [10],.,,,. Belezna [11],, Mean shft.,.,,,,,.,. : 1 ; 2 ; 3 ; 4 ; : 1) ; 2) ; 3). 1.,,,,.,, ;,,,. Fg. 1 1 Greedy searchng based multple object trackng and occluson handlng algorthm

3 3 : (Background subtracton) [17 22],,,.. [17] [18].,. (Gaussan mxture model, GMM) [17],. GMM : X, K : ( K P (X t ) = ω,t η X t, µ,t, ) (1) =1,t ω,t t, K ω =1,t = 1, η(x t, µ,t,,t ) X t. η(x t, µ,t, 1 ) = (2π) n 2,t,t e (Xt µ,t)t (X t µ,t),t 1 2 (2) = 1,, K, n X t,, R, G, B,,,t = σ2 I. GMM,,., X t,,,.,, :,, ;,,,., GMM,,. (u, v), (2N +1) (2N +1) F T t D CF : v+n 1 u+n D(u, v) = F T (2N + 1) 2 t (x, y) f = y=v N x=u N { 1, D(u, v) T c 0, (3), T c = 0.1.,,. I B, (u, v) (2M +1) (2M +1) : NCC(u, v) = M M v= M u= M ( M / (B(u + u, v + v)i(u + u, v + v)) M v= M u= M M M v= M u= M B(u + u, v + v) 2 I(u + u, v + v) 2 ), (4).,,. 2.2 T, = 1,, N 1, D j, j = 1,, N 2. T D, [23]. : M C. 1) M T D,,.,,,, M. S T D j (4) M(, j) = c (5) S T + S Dj, S T D j T D j, S T S Dj T D j, c, c = 2, M(, j) [0, 1].,,.

4 ) C M,, T D C. C 0, C : a) M, T, j max, C 1: j max = arg max M(, j), j = 1,, N 1 j C(, j max ) = C(, j max ) + 1 (6) b) M, D j, j max, C 1: j max = arg max M(, j), = 1,, N 2 C( max, j) = C( max, j) + 1 (7) c) C, 2,, M 0, a) ; C 2,. C, T D 3 : 1) ; 2) ; 3)., ;,.,,. [6, 23],,.,,, 2,,. 3,,,.,,.,.,., Z g, P (Z g H). 2, H w {T } =1,,w, Z g {T } =1,,w,. H R, Z g R w,, Z g. Fg. 2 2 Multple objects locaton n a merged foreground Z g, : {V } =1,,w,. V,. V = T T (8) Z g, : Z 1 = arg max Z 2 = arg max Z k = arg max. V, [1,, w] V, V, [1,, w], V / {V 1 } [1,, w], V / {V j } j=1,,k 1 (9) V 1, P (Z H),, V, P (Z H)., T, T P (Z H) V,,,, : P (Z 1 H) = max P (Z H) P (Z 2 H, Z 1 ) = max P (Z H, Z 1 )

5 3 : 379. P (Z k H, Z 1,, Z k 1) = max P (Z H, Z 1,, Z k 1) (10) [1,, w], Z / {Zj } j=1,,k 1., T T j, (10), : P (Z 1 H) P (Z w H, Z 1,, Z w 1) = P (Z g H) (11) (10) (11), P (Z g H) Z g,,. Z 1 : Z 1 = arg max P (Z H), = 1,, w (12) Z1, Zk: Z k = arg max P (Z H, Z 1, Z 2,, Zk 1) (13), = 1,, w, Z / {Zj } j=1,,k 1. P (Z H, Z1,, Zk 1), T Z H,. : P (Z H, Z 1,, Z k 1) = max(p (Z F xc )), xc H (14) F xc xc Z. P (Z F xc ) T F xc.,, F xc P (Z F xc ): P (Z F xc ) = 1 zw zh x k F xc P (T I(x)) (15), I(x) x k, zw zh Z. I(x) T P (T I(x)), P (T I(x))., P (T I(x)),, H P (T I(x)): P (T I(x)) = P (I(x) T )P (T ) w P (I(x) T s )P (T s ) s=k (16), P (I(x) T ) I(x) T. (16),,.. (16) Z1,, Zk 1,,,., H : H Z1,, Zk 1 X+ g Xg, (16) : P (I(x) T )P (T ), x X w g P (I(x) T s )P (T s ) s=k P (T I(x)) = P (I(x) T )P (T ) ϕ(x), x X w g + P (I(x) T s )P (T s ) s=k (17) ϕ(x) [0, 1],,. 3., H,,.,, (14) (15) (17) T,, X g +,.,. 4, VC++. Intel Core 2 CPU 1.66 GHz, 2 G. IBM [24], [25]. 4.1, 3 : 1) ;

6 Fg. 3 3 Flowchart of greedy searchng algorthm 2) ; 3).,,,, PETS2006 [25] 9, : Tracker detecton rate (TRDR) = TP TG False ala rate (FAR) = FP FP TP Detecton rate (DR) = TP + FN TN Specfcty = FP + TN TP + TN Accuracy = TF TP Postve predcton (PP) = TP + FP TN Negatve predcton (NP) = FN + TN FN False negatve rate (FNR) = FN + TP False postve rate (FPR) = FP FP + TN (18), TP, TN, FP, FN True postve, True negatve, False postve, False negatve, TG (Total ground truth), TF (Total frame).,., : (Occluson error rate, OER), : = (19) 4.2,.,. PETS IBM [24], CAVIAR [26], ETISEO [27]. IBM

3期杨涛等: 一种基于贪心搜索的实时多目标遮挡处理算法人遮挡事件, 因此, 实验中采用该数据库对基于贪心搜索的跟踪算法进行评估.

在标定时, 对于每个目标, 用外接矩形框标示出目标所在位置, 并赋予不同的编号, 标定的真实轨迹保存在数据库中. 作者手工标定了 10 组共计 7 443 帧图像, 其中含有目标 3 085 帧, 发生遮挡总数为 64 次.

4 IBM 室内监控数据库中 10 个场景手工标记的真实轨迹 Hand labeled ground truth trajectory of IBM ndoor survellance vdeo database 测试时,

(c) 和 6 (d) 中近处行人). 图 6 (e) 和 6 (f) 给出本文算法的检测结果, 通过联合候选前景点周围的邻域信息, 将像素级差分扩展为特征级差分, 本算法在增加检测率的同时可减少运动阴影干扰.

5 Movng foreground segmentaton results under smlar background (The frst row shows the nput vdeo, the second row

3 相似背景下的前景检测结果实验中采用 IBM 室内监控数据库, 从相似背景和运动阴影两方面对第 2.1 节检测算法进行评估, 并与混合高斯背景模型的检测结果比较.

相似背景会造成目标的割裂甚至漏检. 图 5 给出一组相似背景条件下的运动前景检测结果.

7 3期杨涛等: 一种基于贪心搜索的实时多目标遮挡处理算法人遮挡事件, 因此, 实验中采用该数据库对基于贪心搜索的跟踪算法进行评估. IBM 提供的目标真实位置采样率较低, 因此, 在实验前先对 10 组 IBM 视频内的运动目标的位置标号进行手工标定, 生成测试用的真实位置 (Ground truth). 在标定时, 对于每个目标, 用外接矩形框标示出目标所在位置, 并赋予不同的编号, 标定的真实轨迹保存在数据库中. 作者手工标定了 10 组共计帧图像, 其中含有目标帧, 发生遮挡总数为 64 次. 图 4 中给出 10 个场景手工标定的目标真实轨迹. 图4 Fg. 4 IBM 室内监控数据库中 10 个场景手工标记的真实轨迹 Hand labeled ground truth trajectory of IBM ndoor survellance vdeo database 测试时, 先从数据库中同时读取图像文件所在路径和真实轨迹, 然后与算法跟踪结果进行比较, 并按照矩形重叠面积比率判断真实位置和检测位置是否匹配, 统计每一帧的 TP TN FP FN, 最终的评估结果由式 (18) 和 (19) 给出. 381 景输出, 造成虚警率上升. 从图 6 (c) 和 6 (d) 中可以看出, 基于像素级差分的 GMM 模型检测结果中包含有大量的阴影区域 (图 6 (c) 和 6 (d) 中远处行人), 此外, 地板和目标灰度相似也造成目标分割结果出现空洞 (图 6 (c) 和 6 (d) 中近处行人). 图 6 (e) 和 6 (f) 给出本文算法的检测结果, 通过联合候选前景点周围的邻域信息, 将像素级差分扩展为特征级差分, 本算法在增加检测率的同时可减少运动阴影干扰. 图 5 相似背景条件下的运动前景分割结果 (第 1 行: 输入视频图像; 第 2 行: GMM 检测结果; 第 3 行: 本文检测结果) Fg. 5 Movng foreground segmentaton results under smlar background (The frst row shows the nput vdeo, the second row dsplays the GMM results, and the thrd row dsplays our results) 4.3 相似背景下的前景检测结果实验中采用 IBM 室内监控数据库, 从相似背景和运动阴影两方面对第 2.1 节检测算法进行评估, 并与混合高斯背景模型的检测结果比较. 在计算像素邻域间的相关系数时, 采用 9 9 的邻域窗口, 阈值为 0.9. 对 IBM 数据库的实验结果表明, 对输入分辨率为的序列, 前景检测的平均处理速度为 15 帧/秒. 相似背景会造成目标的割裂甚至漏检. 图 5 给出一组相似背景条件下的运动前景检测结果. 由于地板格和运动前景目标色彩相近, GMM 漏检了大量前景像素点 (图 5 第 2 行), 场景中同一个运动目标的检测结果会出现割裂, 严重影响后继目标跟踪的稳定性. 本文算法通过候选前景点提取, 能够完整准确地分割出运动目标, 大幅度提高了对运动前景的检测率, 取得满意的效果 (图 5 第 3 行). 图 6 给出一组场景内同时出现运动阴影和相似背景时的前景检测结果. 当目标在场景中运动时, 在地面墙面投射了大量阴影. 根据图像照度模型, 阴影区域内的像素灰度会发生比率变化, 这使得用欧氏距离做度量的像素级差分会将该区域当作运动前 (a) 输入图像 (b) 背景图像 (a) Input mage (b) Background mage (c) GMM 分割前景 (c) GMM segmentaton result (d) GMM 前景图像 (d) GMM foreground mage (e) 本文算法分割前景 (e) Our segmentaton result (f) 本文算法前景图像 (f) Our foreground mage 图6 Fg. 6 运动阴影相似背景条件下的运动前景分割结果 Movng foreground segmentaton results under cast shadow and smlar background

本算法采用贪心搜索的思路, 首先根据观测概率大小定位出可视度最高的 1 号目标, 然后按照式 (17) 修正合并前景块内像素概率, 并根据 2 号目标的未被遮挡的部分对其进行定位.

8 自 382 动化 4.4 多人遮挡跟踪结果图 7 中给出 3 组两人交错时的跟踪结果. 当两目标交错时, 基于合并分裂的跟踪算法[6, 23] 会把目标作为一个整体进行跟踪. 与之不同, 通过贪心搜索, 本算法在遮挡过程中仍能准确地估计目标位置图 (7 (a) (c) 中第 2 列和第 3 列). 在图 7 (c) 中, 2 号目标在交错时被严重遮挡 (图 7 (c) 中第 3 列), 目标外观发生较大改变, 此时一些基于局部最优的跟图7 Fg. 7 报 36 卷踪算法, 如相关跟踪 Mean shft 等容易发生失跟. 本算法采用贪心搜索的思路, 首先根据观测概率大小定位出可视度最高的 1 号目标, 然后按照式 (17) 修正合并前景块内像素概率, 并根据 2 号目标的未被遮挡的部分对其进行定位. 该算法对目标的被遮挡程度无约束, 因此能在遮挡过程中连续给出当前两个目标的最优位置组合 (图 7 (c) 中第 3 列), 而且当被完全遮挡的目标重新出现时, 可恢复对该目标的跟踪 (图 7 (c) 中第 4 列). 两人遮挡跟踪结果 Experment results of two people trackng through occluson 图8 Fg. 8 学三人遮挡跟踪结果 Experment results of three-people trackng through occluson

3 : 383 8 3. 1, 2.,, 3 ( 8 180, 222). 3,,., 3 ( 8 180, 222), 3 ( 8 204, 240). [25] (18). 9 IBM 10, 7 443., : (False negatve rate, FNR) 0.027 ( 9),.,, ;, N M (M < N),. (False postve rate, FPR) 0.

9 3 : , 2.,, 3 ( 8 180, 222). 3,,., 3 ( 8 180, 222), 3 ( 8 204, 240). [25] (18). 9 IBM 10, , : (False negatve rate, FNR) ( 9),.,, ;, N M (M < N),. (False postve rate, FPR) 0.077,, IBM, 10 64, 50, 0.22.,,, 10 /. Fg IBM Performance evaluaton results of IBM database,,,,.,,,., IBM,.,,,,. References 1 Senor A, Hampapur A, Tan Y L, Brown L, Pankant S, Bolle R. Appearance models for occluson handlng. Image and Vson Computng, 2006, 24(11): Cucchara R, Grana C, Tardn G, Vezzan R. Probablstc people trackng for occluson handlng. In: Proceedngs of the 17th Internatonal Conference on Pattern Recognton. Cambrdge, UK: IEEE, Nguyen H T, Smeulders A W M. Fast occluded object trackng by a robust appearance flter. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2004, 26(8): Wu Y, Yu T, Hua G. Trackng appearances wth occlusons. In: Proceedngs of IEEE Computer Vson and Pattern Recognton. Wsconsn, USA: IEEE, Sebel N T, Maybank S J. Fuson of multple trackng algorthms for robust people trackng. In: Proceedngs of the 7th European Conference on Computer Vson. Copenhagen, Denmark: Sprnger, Huang Y, Essa I. Trackng multple objects through occlusons. In: Proceedngs of IEEE Conference on Computer Vson and Pattern Recognton. San Dego, USA: IEEE, Chang T H, Gong S G, Jong E. Trackng multple people under occluson usng multple cameras. In: Proceedngs of Brtsh Machne Vson Conference. Brstol, UK: Brtsh Machne Vson Assocaton, Hu W M, Hu M, Zhou X, Tan T N, Lou J G, Maybank S. Prncpal axs-based correspondence between multple cameras for people trackng. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2006, 28(4): Zhao T, Nevata R. Trackng multple humans n complex stuatons. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2004, 26(9): Cucchara R, Grana C, Tardn G. Track-based and objectbased occluson for people trackng refnement n ndoor survellance. In: Proceedngs of the 2nd Internatonal Workshop on Vdeo Survellance and Sensor Networks. New York, USA: ACM, Belezna C, Schlol T, Wachmann B, Bschof H, Kropatsch W G. Trackng multple objects n complex scenes. In: Proceedngs of the 26th Workshop of the Austran Assocaton for Pattern Recognton. Austra: Josh N, Avdan S, Matusk W, Kregman D J. Synthetc aperture trackng: trackng through occlusons. In: Proceedngs of the 11th IEEE Internatonal Conference on Computer Vson. Ro de Janero, Brazl: IEEE, McKenna S J, Jabr S, Durc Z, Rosenfeld A, Wechsler H. Trackng groups of people. Computer Vson and Image Understandng, 2000, 80(1): 42 56

384 36 14 Bremond F, Thonnat M. Trackng multple non-rgd objects n vdeo sequences. IEEE Transactons on Crcuts and Systems for Vdeo Technology, 1998, 8(5): 585 591 15 Pater J H, Crowley J L.

141 147 16 Elgammal A E, Davs L S. Probablstc framework for segmentng people under occluson. In: Proceedngs of the 8th Internatonal Conference on Computer Vson. Vancouver, Canada: IEEE, 2001.

A texture-based method for modelng the background and detectng movng objects. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2006, 28(4): 657 662 19 Shekh Y, Shah M.

Detectng salent moton by accumulatng drectonally-consstent flow. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2000, 22(8): 774 780 21 Bugeau A, Perez P.

10 Bremond F, Thonnat M. Trackng multple non-rgd objects n vdeo sequences. IEEE Transactons on Crcuts and Systems for Vdeo Technology, 1998, 8(5): Pater J H, Crowley J L. Mult-modal trackng of nteractng targets usng Gaussan approxmatons. In: Proceedngs of the 2nd IEEE Internatonal Workshop on Performance Evaluaton of Trackng and Survellance. Hawa, USA: IEEE, Elgammal A E, Davs L S. Probablstc framework for segmentng people under occluson. In: Proceedngs of the 8th Internatonal Conference on Computer Vson. Vancouver, Canada: IEEE, Stauffer C, Grmson W E L. Learnng patterns of actvty usng real-tme trackng. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2000, 22(8): Hekkla M, Petkanen M. A texture-based method for modelng the background and detectng movng objects. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2006, 28(4): Shekh Y, Shah M. Bayesan modelng of dynamc scenes for object detecton. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2005, 27(11): Wxson L. Detectng salent moton by accumulatng drectonally-consstent flow. IEEE Transactons on Pattern Analyss and Machne Intellgence, 2000, 22(8): Bugeau A, Perez P. Detecton and segmentaton of movng objects n hghly dynamc scenes. In: Proceedngs of the IEEE Conference on Computer Vson and Pattern Recognton. Mnnesota, USA: IEEE, Zhu S, Avdan Q, Cheng K T. Learnng a sparse, cornerbased representaton for tme-varyng background modelng. In: Proceedngs of the IEEE Conference on Computer Vson. Bejng, Chna: IEEE, Yang T, Pan Q, L J, L S Z. Real-tme multple object trackng wth occluson handlng n dynamc scenes. In: Proceedngs of the IEEE Conference on Computer Vson and Pattern Recognton. San Dego, USA: IEEE, Brown L M, Senor A W, Tan Y L, Connell J, Hampapur A. Performance evaluaton of survellance systems under varyng condtons [Onlne], avalable: November 3, Bashr F, Porkl F. Performance evaluaton of object detecton and trackng systems. In: Proceedngs of the IEEE Internatonal Workshop on Performance Evaluaton of Trackng and Survellance. New York, USA: IEEE, CAVIAR test case scenaros [Onlne], avalable: homepages.nf.ed.ac.uk/rbf/caviar/, January 10, Vdeo understandng evaluaton [Onlne], avalable: slogc.fr/etseo, November 19, E-mal: yangtaonwpu@163.com (YANG Tao Postdoctor at the School of Computer Scence, Northwestern Polytechncal Unversty. He receved hs Ph. D. degree n control scence and control engneerng from the School of Automaton, Northwestern Polytechncal Unversty n Hs research nterest covers vdeo content analyss, vsual object detecton and trackng, and mage regstraton. Correspondng author of ths paper.) E-mal: jnglxd@mal.xdan.edu.cn (LI Jng Lecturer at the School of Telecommuncatons Engneerng, Xdan Unversty. She receved her Ph. D. degree n control scence and control engneerng from the School of Automaton, Northwestern Polytechncal Unversty n Her research nterest covers mage processng and pattern recognton, mage regstraton, text locaton and recognton.).. E-mal: quanpan@nwpu.edu.cn (PAN Quan Professor at Northwestern Polytechncal Unversty. Hs research nterest covers theory and applcaton of nformaton fuson, multtarget trackng, and ntellgence nformaton processng.).. E-mal: ynzhang@nwpu.edu.cn (ZHANG Yan-Nng Professor at Northwestern Polytechncal Unversty. Her research nterest covers computer vson, mage and vdeo sgnal processng, ntellgence nformaton processng, and pattern recognton.)

2 : 237.,. [6 7] (Markov chan Monte Carlo, MCMC). MCMC, [8 9].,,, [0 ].,, : ),,,.,, ; 2),,.,.,. : ),.,,. ; 2),.,,. ; 3), EM, EM,.,, EM, EM. K M,.,. A

2 : 237.,. [6 7] (Markov chan Monte Carlo, MCMC). MCMC, [8 9].,,, [0 ].,, : ),,,.,, ; 2),,.,.,. : ),.,,. ; 2),.,,. ; 3), EM, EM,.,, EM, EM. K M,.,. A 38 2 Vol. 38, No. 2 202 2 ACTA AUTOMATICA SINICA February, 202.,.,, EM,.. DOI,,, 0.3724/SP.J.004.202.00236 Data Assocaton n Vsual Sensor Networks Based on Hgh-order Spato-temporal Model WAN Ju-Qng LIU