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 Qng-Yun Abstract One of the fundamental requrements for vsual survellance wth vsual sensor networks s the correct assocaton of camera s observatons wth the tracks of objects under trackng. In ths paper, we propose a hgh-order spato-temporal model to deal wth the problem of mssng detecton, and then formulate the data assocaton problem wth dynamc Bayesan networks. After presentng the exact nference algorthm for data assocaton and showng ts computatonal ntractablty, we derve two approxmate nference algorthms based on dfferent ndependency assumptons. To apply the algorthms when the object appearance model s unavalable, we ncorporate the proposed nference algorthms nto EM framework. Smulaton and expermental results demonstrate the effectveness of the proposed method. Key words Data assocaton, vsual sensor networks, hgh-order spato-temporal model, dynamc Bayesan networks,.,,., ( ),,.,, [ 2]..,.,. [3] 200--24 20-05-5 Manuscrpt receved November 24, 200; accepted May 5, 20 (43072) Supported by Bejng Natural Scence Foundaton (43072) Recommended by Assocate Edtor QIAO Hong. 009. School of Automaton Scence and Electrcal Engneerng, Bejng Unversty of Aeronautcs and Astronautcs, Bejng 009,,,,. [4],,.,,.,., [5],,,,. [6],,.,. [5]
2 : 237.,. [6 7] (Markov chan Monte Carlo, MCMC). MCMC, [8 9].,,, [0 ].,, : ),,,.,, ; 2),,.,.,. : ),.,,. ; 2),.,,. ; 3), EM, EM,.,, EM, EM. K M,.,. A = {a uv } M u,v=, a uv = (π uv, t uv, s uv ), π uv u v, π uv = 0 u v ; t uv u v, s uv., y = {o, d, c }, o, ; c d, c, d c. {y } N =.. Fg. Topology of vsual sensor networks x {,, K}, x = k y k ; z = { } K k=, {0,, } y k, = 0 k. (x, z ), p(x y 0: ).,,.., p(x, z x, z ) = p(x )f(z x = k, = l) (), p(x ), ; x z, z., k,
238 38, z, = [x k] + ( )[x = k] (2), [g] (0) g ( )..2,,., p(o x = k) = N(o ; µ k, σ 2 k) (3), µ k σk 2 k., u v, p(d, c x = k, = l, y 0: ) = p(d x = k, = l, d l, c l = u, c = v) = {, l = 0 (4) N(d d l ; t uv, s uv ), l 0,,,,, [5]...3,.,,., } M u,v=, ω u,v {,, Ruv} L u v L, u v, L = 0 u v. (x, z, ω ), ω = {ω u,v p(x, z, ω x, z, ω ) = p(x )p(ω )f(z x = k, = l) (5), p(ω ), u v r L ω (u,v) = (u, w 0,, w L, v), p(ω (u,v) = r) = π uw 0 r π uw 0 ( L l= ( L π w l w l l= ) π w l wr l ) p(d, c x = k, z, ω, y 0: ) = p(d x = k, π w L u = l, ω (u,v) = π w L u r, d l, c l = u, c = v) = {, l = 0 N(d d l ; t uv, s uv ), l 0 (6) (7) A. u r v t uv = t uw 0 L + l= t w + t l w l w (8) L v u r v s uv = s uw 0 L + l= s w + s l w l w (9) L v (5) (9),. L, L = 0 (4)..4,, [2]. 2., ;,. z (2), y (3) (7)., = 0, k =,, K.,, p(x y 0: ).
2 : 239 Fg. 2 2 ((a)) ((b)) Dynamc Bayesan networks model ((a)) and dependency n a sngle tme slce ((b)) 2 2 ω,. (Belef state) p(x, z y 0: ), x., p(x, z y 0: ) = ω p(x, z, ω y 0: ) = (0) p(y x, z, ω, y L 0: )p(x, z, ω y 0: ) = ω λ (x = k)η ( = l) p(z, x y L 0: ) x, L = p(y y 0: ). λ η λ (x = k) = p(x = k)p(o x = k), η ( = l) = ω (u,v) = l, ω (u,v) k =,, K p(ω (u,v) )p(d x = k,, d l, c l = u, c = v), l = 0,, (0) (z, x ) p(z, x = j y 0: ) = f(z x, z )p(x = j, z y 0: ) = z 2 p(x = j, z (j) = m, z ( j) z (j) =0 z (j) () = z ( j) y 0: ), =, z ( j) = 0,, 2 0, (2), ( j) j. (2), x = j z ( j) = z ( j),. (0) (2). (0),, K K,,.,,. 3,.,, (0) (2),,. [3] Kullback- Lebler (KL),.,,,. (Actve path) [4]. 2, : z (j) z (j) x z (j) y ; x x y., x,., ;,,. 3. I,
240 38 x (, z (j), x ) p(x, z y 0: ) p(x, z y 0: ) = K p(x y 0: ) p( y 0: ) (3) k= x p(x = k y 0: ) = λ (x = k) η ( = l)p(z y L 0: ) = z λ (x = k) η ( = l) L p( = l, x y 0: ) (4) x p( = l y 0: ) = L x z ( k) λ (x =k)η ( =l)p(z y 0: ) = λ (x = k)η ( = l) p( = l, x L x y 0: ) + L m) x p(z (j) K x =,x k λ (x = j) z (j) η (z (j) = = m, = l, x y 0: ) (5) (4) (5),, x ) ( p( = l, x = n y 0: ) = f( = l x = n, ) p(x = n, z y (k) 0: ) = p(x = k y 0: ), n = k, l = p(x = n y 0: )p( = l y 0: ), n k, l = 0,, 2 0, (6) p(z (j) = m, = l, x = n y 0: ) = f(z (j) = m, = l x = n, z, (j) z ) (k) z (j) p(x = n, z, (j) z y (k) 0: ) = p(x = j y 0: )p( = l y 0: ), n = j, m =, l = 0,, 2 p(x = k y 0: )p(z (j) = m y 0: ), n = k, m = 0,, 2, l = p(x = n y 0: )p(z (j) = m y 0: ) p( = l y 0: ), n j, n k, m = 0,, 2, l = 0,, 2 0, (7) (3). (4) (7), K + K,. 3.2 II 2, x z y., x z, z (j) x. p(x, z y 0: ) p (x, z y 0: ) = K p(x y 0: ) p( x, y 0: ) (8) k= x (4). x p(x = j, = l y 0: ) = λ (x = j) η (z (j) = m)p(z y L 0: ) = z ( k) λ (x = k)η ( = l) L = l, x y 0: ), j = k x p( λ (x = j) L z (j) p(z (j) x η (z (j) = m, = m) = l, x y 0: ), j k (9)
2 : 24 (8), (6) p( = l, x = n y 0: ) = p(x = k y 0: ), n = k, l = (7) p(x = n, = l y 0: ), n k, l = 0,, 2 0, p(z (j) = m, z k = l, x = n y 0: ) = p(x = j, = l y 0: ), n = j, m =, l = 0,, 2 p(x = k, z (j) = m y 0: ), n = k, m = 0,, 2, l = p(z (j) =m,x =n y 0: )p( =l,x =n y 0: ) p(x =n y 0: ), n j, n k, m = 0,, 2, l = 0,, 2 (20) 0, (2) (9) (2), K + K 2,,. 4,.,. µ k σ k.,.,., [5], EM, EM,. 3, Θ := {α k, µ k, σ k } K k=, α k = p(x = k) k, µ k σ k k. E,, EM Θ old, p(x y 0:, Θ old ). M, : αk new = N p(x = k y N 0:N, Θ old ) = N o p(x = k y 0:N, Θ old ) µ new = k = N p(x = k y 0:N, Θ old ) σ new k = N = = p(x = k y 0:N, Θ old )(o µ new k Fg. 3 N p(x = k y 0:N, Θ old ) = 3 EM The extended EM framework )(o µ new k ) T (22) EM EM [6]. EM,, ; EM,., EM. 5, A,. k,, π uv., o, t uv s uv d.,, y = {o, d, c } N =.,, q : q = K K k= q k, q k = Y k Y k Y k 00 % (23), K, Y k k ; Y k k
242 38. 5.,,,,.,,,. (%) Table The average accuracy of exact nference n case of mssng detecton (%) 2 4 8 0 87.37 85.00 8.69 75.55 92.49 90.5 85.8 82.5 2 9.6 89.43 88.3 82.8 4. 4 4 40, 24 34,.,,, 0.. 4 (a),,,, 73.6 %.,, 92.73 %, 4 (b). 5.2,. 5, 3, 0, 23 25.. 5, II, I., II 97.50 %, I 86. %., KL. KL : D[p(x ) ˆp(x )] := x p(x )ln p(x ) ˆp(x ) (24) 25, 40, KL, 6. I KL 6 (a),.727; II KL, 0.3933,, 6 (b), II. (a) (a) 0-order spato-temporal model Fg. 4 (b) (b) -order spato-temporal model 4 Margnal dstrbutons of labelng varable n exact nference
2 : 243 (a) (a) Exact nference (b) I (b) Approxmate nference I Fg. 5 (c) II (c) Approxmate nference II 5 Margnal dstrbutons of labelng varable n nference wth -order spato-temporal model (a) I (a) Approxmate nference I (b) II (b) Approxmate nference II 6 KL Fg. 6 KL dvergence caused by approxmate nference 5.3, EM,. EM [6], : p(x = k o, Θ) = N(o ; µ k, σ k) 2 N(o ; µ j, σj 2 ) j (25) 2 3 EM. 00,,., EM. 2, EM,,., 3,, 4 20 (4, 20 ),.,
244 38 2 3, II I,,. 2 (%) Table 2 The average accuracy of nference algorthms under dfferent numbers of observatons (%) EM I II 3 0 63.28 84.37 72.2 82.79 3 20 59.02 8.78 70.86 80.38 4 20 53.82 x 70.07 82.66 5 20 57.04 x 65.58 85.69 7, EM, 7, 0.5, 3.5, 7., II, EM, 7 (b) 7 (d); (23) I, EM, 7 (a) 7 (c). 3 Table 3 EM (s) Runnng tme of nference algorthms under dfferent numbers of observatons (s) EM I II 3 0 0.008 4.9809 0.066.330 3 20 0.0036 73.4384.3776 8.2304 4 20 0.0053 x 7.9897 4.750 5 20 0.0076 x 29.992 49.49 6,. 6, 8. (a) EM (a) Standard EM (b) (b) Exact nference (c) I (c) Approxmate nference I (d) II (d) Approxmate nference II 7 EM Fg. 7 Parameter learnng curves of EM wth dfferent nference algorthms
2 : 245 (23). 4 EM. 9,. 9,,.,, EM. MCMC [8 9],, MCMC EM, 9 (b),. 9 (c) 9 (d) EM, II,. 8 Fg. 8 Experment setup, 5 75,. RGB,. 0.,,,,.,, [5].,.., : ) ; 2)., [] : ) q, (23) ; 2) r: r = K r k, r k = Y k Yk 00 % (26) K Y k k= 3) F : F = 2 q r q + r (27) Table 4 4 (%) Recovered trajectores results of dfferent assocaton algorthms (%) F EM 63.07 55.23 58.89 MCMC 64.67 53.90 58.79 I 7.60 57.56 63.82 II 88.46 88.46 88.46 7,,, EM,., EM [7].,,,,. [8].,,,.,,..
246 38 (a) EM (a) Standard EM algorthm (b) MCMC + EM (b) MCMC and EM algorthm (c) II + EM (c) Approxmate nference II and EM algorthm (d) II (d) Approxmate nference II 9 Fg. 9 Expermental results n vsual sensor network References Glbert A, Bowden R. Trackng objects across cameras by ncrementally learnng nter-camera color calbraton and patterns of actvty. In: Proceedngs of the 9th European Conference on Computer Vson. Graz, Austra: Sprnger, 2006. 25 36 2 Javed O, Shafque K, Rasheed Z, Shah M. Modelng ntercamera space-tme and appearance relatonshps for trackng across non-overlappng vews. Computer Vson and Image Understandng, 2008, 09(2): 46 62 3 Song B, Roy-Chowdhury A K. Robust trackng n a camera network: a mult-objectve optmzaton framework. IEEE Journal of Selected Topcs n Sgnal Processng, 2008, 2(4): 582 596 4 Lu Shao-Hua, La Sh-Mng, Zhang Mao-Jun. A mn-cost flow based algorthm for objects assocaton of multple nonoverlappng cameras. Acta Automatca Snca, 200, 36(0): 484 489 (,,.., 200, 36(0): 484 489) 5 Zajdel W, Klose B. A sequental Bayesan algorthm for
2 : 247 survellance wth nonoverlappng cameras. Internatonal Journal of Pattern Recognton and Artfcal Intellgence, 2005, 9(8): 977 996 6 Camp F, Bernardn K, Stefelhagen R. Person trackng n camera networks usng graph-based Bayesan nference. In: Proceedngs of the 3rd ACM/IEEE Internatonal Conference on Dstrbuted Smart Cameras. Como, Italy: IEEE, 2009. 8 7 Km H, Romberg J, Wolf W. Mult-camera trackng on a graph usng Markov chan Monte Carlo. In: Proceedngs of the 3rd ACM/IEEE Internatonal Conference on Dstrbuted Smart Cameras. Como, Italy: IEEE, 2009. 8 8 Oh S, Russell S, Sastry S. Markov chan Monte Carlo data assocaton for mult-target trackng. IEEE Transactons on Automatc Control, 2009, 54(3): 48 497 9 Goyat Y, Chateau T, Bardet F. Vehcle trajectory estmaton usng spato-temporal MCMC. EURASIP Journal on Advances n Sgnal Processng, 200: Artcle ID 72854, 8 pages 0 Zajdel W, Klose B. Gaussan mxture models for multsensor trackng. In: Proceedngs of the 5th Dutch-Belgan Artfcal Intellgence Conference. Njmegen, Netherlands: BNAIC, 2003. 37 378 Zajdel W. Bayesan Vsual Survellance: from Object Detecton to Dstrbuted Cameras [Ph. D. dssertaton], Unversty of Amsterdam, Netherlands, 2006 2 Murphy K P. Dynamc Bayesan Networks: Representaton, Inference and Learnng [Ph. D. dssertaton], Unversty of Calforna, Berkeley, USA, 2002 3 Boyen X, Koller D. Tractable nference for complex stochastc processes. In: Proceedngs of the 4th Conference on Uncertanty n Artfcal Intellgence. Madson, USA: Morgan Kaufmann, 998. 33 42 4 Shachter R D. Bayes-ball: the ratonal pastme (for determnng rrelevance and requste nformaton n belef networks and nfluence dagrams). In: Proceedngs of the 4th Conference on Uncertanty n Artfcal Intellgence. Madson, USA: Morgan Kaufmann, 998. 480 487 5 Dempster A P, Lard N M, Rubn D B. Maxmum-lkelhood from ncomplete data va the EM algorthm. Journal of Royal Statstcs Socety, Seres B, 977, 39(): 38 6 Blmes J A. A Gentle Tutoral on the EM Algorthm and Its Applcaton to Parameter Estmaton for Gaussan Mxture and Hdden Markov Models, Techncal Report TR-97-02, Unversty of Calforna, Berkeley, USA, 998 7 Jepson A D, Fleet D J, El-maragh T F. Robust onlne appearance models for vsual trackng. In: Proceedngs of the IEEE Computer Socety Conference on Computer Vson and Pattern Recognton. Kaua, USA: IEEE, 200. 45 422 8 Wan J, Lu Q. Effcent data assocaton n vsual sensor networks wth mssng detecton. EURASIP Journal on Advances n Sgnal Processng, 20, 20: Artcle ID 76026, 25 pages. / /,,,.. E-mal: wanjuqng@gmal.com (WAN Ju-Qng Lecturer at the School of Automaton, Bejng Unversty of Aeronautcs and Astronautcs. Hs research nterest covers sgnal/mage/vdeo processng, statstcal nference and machne learnng, target detecton, trackng and recognton, and fault dagnoss and prognoss of complex system. Correspondng author of ths paper.).. E-mal: cnluqngyun@gmal.com (LIU Qng-Yun Master student at the School of Automaton, Bejng Unversty of Aeronautcs and Astronautcs. Her research nterest covers dgtal sgnal processng and target trackng.)