一种基于贪心搜索的实时多目标遮挡处理算法

1、 36 3 2010 3 $ k acta automatica sinicavol. 36, no. 3march, 2010% 1 2 3 1 %$ff%fi, :%,q %. %ka$: 1) f%k%; 2) %$%, f%; 3) $, fiaf% (qr%$ 2), %fi$, $%. $i% ibm fi$fi%f%$. fi, , , doi10.3724/sp.j.1004.2010.00375a greedy searching algorithm for multiple objecttracking and occlusion handlingyang tao1li j

2、ing2pan quan3zhang yan-ning1abstract this paper presents a novel real-time multiple object tracking algorithm, which contains three parts: regioncorrelation based foreground segmentation, merging-splitting based data association and greedy searching based occluded object localization. the main chara

3、cteristics of the proposed algorithm are summarized as follows: 1) the multiple object tracking and occlusion handling problem is successfully changed into an image classification problem with prior knowledge of object number and feature; 2) a highly efficient greedy searching method is presented to

4、 meet real-time capability; 3) it has good performance in expansibility, and it has no constraints about the number of occluded objects, the occlusion ratio and the objectt s motion model. experiment results with hand labeled ibm database demonstrate that the method is effective and efficient.key wo

5、rds multiple object detection and tracking, occlusion handling, greedy searching, intelligent video surveillance%k%fififl$%fi, y,$a,$%f. f%fi116 %$% aa$. r$, $%, $afi $%.%pf 5 : 1) fi; 2) fiq; 3) qfi; 4) fi; 5) fi. $, 1) 5) %, 2) qr %, fa% ( 3) % ( 4) %a.k, f%lfffflfl. $q:, q %; $% , %a%.1) q %, qr%

6、, %, qfl%qf%. l, q r%q$%, %qr%, $. mckenna 13 bremond14 k, ,. piater 15 k$ 2008-10-22 fi$ 2009-01-21manuscript received october 22, 2008; accepted january 21,2009$q (863 ) (2009aa01z315), (60903126, 60872145, 60634030), i$ (708085) supported by national high technology research and de-velopment prog

7、ram of china (863 program) (2009aa01z315), national natural science foundation of china (60903126,60872145, 60634030), and cultivation fund of the key scien- tific and technical innovation project, ministry of education of china (708085)1. ffli!$fa fp710129 2. fp$i fp 710071 3. ffli!$k fp 7101291. s

8、haanxi key laboratory of speech and image informationprocessing, school of computer science, northwestern polytech- nical university, xir an 710129 2. school of telecommunica- tions engineering, xidian university, xir an 710071 3. school of automation, northwestern polytechnical university, xir an71

9、0129, q kalman %, .q %fl%, $q , fl%,%. q%, q%k%. %a%qr%$ 2, %:fi, %$, fl%k%$ %f%, f.2) %$%k. qr %$, flfi ($ 2) $%. %a%.%,mean shift . $% (a,ka,) $ (fi ,%l), % %. , %, $%,%$, %f. %, $l, %fikfi, qrfl%, %$, f%, $%, . flk, %, %f%.a%$%,$%, %$k. l,qr%, $%fia, f$fiqr%, %fi, %fl %. fl, $%$fifik. elgammal 16

10、 %fi$% %, %$% % (fi,$,), %$ fi$%$, %, q. cucchiara10 :$fi$% $. beleznai 11 mean shift fi%$, q% mean shift . %, lffl: cucchiara 10 fik, fk%. flk,fi%, fi%, %f%. beleznai 11 $% l, f, f% mean shift %$.$lfl, %$%fi. q , fi%, %$a%, f%k%, q%, $%. qr%,% %fi$, f%$.$%pf: 1 ;$% ; 2 ;$%q ; 3 ;%; 4 ;$; 5 ;%.1 k 3

11、 : 1) %;2) q; 3) %. 1 . pfifi,%$, fifi:, :%k%k %, %q. $qr%, , q; $qr%, fi%q, % , $%. 1 %fifig. 1 greedy searching based multiple object tracking and occlusion handling algorithm3 : %fi3772 q2.1 % (background subtraction)1722%f%, $ %p%$%, ,%,fi, flfi$%f. %$%. p%$, ,%17 ,%,a f tt %a d %$%a c f :v+n u+

12、n1.d(u, v) =f tt (x, y)(2n + 1)2y=vn x=un.1,q d(u, v) tc0,f =(3)$, tc = 0.1. $fi% %k, a%k%ka%, %$. i b $p$, a (u, v) % (2m +1)(2m +1)kfi%fif:n c c (u, v) =$18 .f%$, ,%,kh%$f.$ % (gaussian mixture model, gmm)17 %, q$% $r. gmm f:$fiafi% x $, %f k $:m.m.(b(u + u, v + v)i (u + u, v + v)v=m u=m.m.m.b(u +

13、 u, v + v)2 ,v=m u=m.m.m.k.i (u + u, v + v)2(4)p (xt ) = . i,t xt , i,t , .,(1)v=m u=mi=1i,t%, fi (4) $%. $, $k% f%, %$.2.2q ti , i = 1, , n1 $%,fi$ i,t i $ t %, %$.k.i=1 i,t = 1, (xt , i,t , i,t ) % x t %i $.1(xt , i,t , .) =i,tn.i,t1(2) 2 | 2 d , j = 1, , n $j2%. t d %, $ 23 $%$%q. fl%fl: m c .1)

14、m t d $%fi%, $%, k,%. %fi%, %kq$%$, fl, k:fl%, r m .t 1 2 (xt i,t ) . (xt i,t )i,t1e(2)fi$ i = 1, , k , n $ xt %, f%, p r, g, b a, q$%, $ .i,t = i i . $ gmm $2$%$, $fifi%$%$, %k. flk, f% xt , %, %fi%k, fi%.fifik fl, fi$%, %$: %, , f; $%, :%fifi%qr%k, :$, l. fll, $ gmm %l, , a%$. fia (u, v), (2n + 1)

15、 (2n + 1) sti djm (i, j) = c(5)sti + sdj$, sti dj$ ti dj %:, sti sdj $ ti dj %k, fi c %kp, %$ c = 2, m (i, j) 0, 1. fl, %$ f%$fl, fl$%.2) c m , %$, t d % c . % c %$yfi 0, c f:a) m , ti , $%fi jmax , q c % 1:fiq%, % z , g% p (zg |h ) $k. 2 $f%, $ h fi$ w ti i=1, ,w%q, zg fi$ ti i=1, ,w q$%$, %k%q%$.

16、h r a%, zg % rw , %jmax = arg max m (i, j),j = 1, , n1j, fi% z flgc (i, jmax ) = c (i, jmax ) + 1(6)%.b) fi m , %dj , $% jmax , q c % 1:jmax = arg max m (i, j),i = 1, , n2ic (imax , j) = c (imax , j) + 1(7)c) c , 2 %yfi, yfi%, q m$%fi$yfi 0, a) fl%; c $yfi 2, $n.y c %, t d % 3 : 1) %;2) $%; 3) $%fi%

17、. $%, % ,%,% q; $fi%, % $,%. fl, $%$%qr, fiqf.q %6, 23 q %fi, fl %k,%,%, fla%. %, q, f $%, qr%$ 2 %, %, .3 %yfq %, $;%$%, $%k%, q% . f%, %, flkk%. l;%q, fiq. fl%, k%fi%. 2 $%fifig. 2 multiple objects location in a merged foreground% z g , $%: % vi i=1, ,w , %. vi $, $%. ti $%vi =(8) t ifi%g , %$fi%f

18、ifi:z z 1 = arg max vi ,i 1, , wi2 = arg max v ,i 1, , w, v / v z ii1i(9).z = arg max vi ,i 1, , w,kivi / v j j=1, ,k1% vi 1, % p (zi |h )fi$, %, vi , fl% p (zi |h ) %. l, ti$qr$%fl%k%, ti % p (zi |h ) % vi $fl, fl, $%, q%$, f%$%fi:p (z 1 |h ) = max p (zi |h )p (z |h, z ) = max p (z |h, z )21i13 : %

19、fi379fi$, p (i (x)|ti ) fi i (x) ti %$%.fi (16) %, % %, %$% fi. %. %fi (16) %$y.p (z |h, z , , z ) =k1k1max p (z |h, z , , z )(10)i1k1fi$ i 1, , w, zi / z j=1, ,k1 . j$a, ti % tj , fi (10) fi$, q%fi:% z 1 , , zk1 %, fl%, $fi%,ffiq$k%.f, h $%fifl:p (z |h ) p (z |h, z , , z ) = p (z |h )1w1w1g(11)fi (

20、10) fi (11) $, % p (zg |h )$k%. %h $% z 1 , , zk1 f%fi xg+$k% z , %, $%fi x g , qfi (16) $:g p (i (x)| ti )p (ti ) % z %$%:1,x x wg . p (i (x)|t )p (t )1 = arg max p (zi |h ),i = 1, , w(12)z s sis=kp (ti |i (x) =fi z , $k% p (i (x)| ti )p (ti ) (x), x1fi z :x +wgk .p (i (x)|ts )p (ts )s=kk = arg max

21、 p (zi |h, z1 , z2 , , zk1 )(13)z i(17)$, i = 1, , w, zi / z j=1, ,k1 . f (x) 0, 1, %f%fi, %fifi%. 3 $. $q r%, fi%q h , q%, qr%,. %, $%, fi (14),(15) (17) ti %, q%$, %fifij% p (zi |h, z , , z ) , ti1k1%k zi h l$%, q%. $%:p (zi |h, z , , z ) = max(p (zi |fxc ), xc h1k1(14)$a xc %k zi ffxc%. % p (zi |

22、fxc ) fi$f ti fxc %. , f%, $ fxc $fi% p (zi |fxc ):+ xg $, q$%fi. l, fi$%.4q$, vc+ flqf%fi$fi. $fi intel core2 cpu 1.66 ghz , 2 g. ibm fi$fi24 %fi, q 25 $%.4.1%, f 3 :1) %fi ;1.xk fxcp (zi |fxc ) = zwp (ti |i (x)(15) zhfi$, i (x) fi$ xk %fifi%, zw zh$ zi %. fi i (x) ti % p (ti |i (x) $, p (ti |i (x)

23、 %. qr%$%, fk% p (ti |i (x), fi, h $% p (ti |i (x): p (i (x)| ti )p (ti ) p (ti |i (x) =(16)w. p (i (x)|ts )p (ts )s=k 3 fig. 3 flowchart of greedy searching algorithmfp2) k%;3) %.fi$i, , fl$k% fi, %, q pets2006 $ 25 % 9 % , %f:false positive rate (fpr) =(18)fp + tn$, tp, tn, fp, fn $ true positive,

24、 truenegative, false positive, false negative $%, tg (total ground truth) %$%, tf (total frame) %. k%, $,%. f %, $%: (occlusion error rate, oer), qr%fl:tptgtracker detection rate (trdr) =fpfalse ala rate (far) =fptp% =(19)detection rate (dr) =qr%tp + fntn4.2%, kp%$fi, % hr$%. fl, $fi%fi. % fl fi pet

25、s,ibm % fi24 , % caviar fi26 , % etiseo27 . ibm fi$fispecificity =fp + tntp + tnaccuracy =tftppositive prediction (pp) =tp + fptnnegative prediction (np) =fn + tnfnfalse negative rate (fnr) =fn + tp3 : %fi381$, fl, $fi%.ibm %, fl, 10 ibm % ,$i, r% (ground truth). %, , k $, q%, %fi$. $if 10 7 443 , $

26、 3 085 , qr 64 . 4 $ 10 $i%.$, l. 6 (c) 6 (d) $, fi% gmm %$ $%: ( 6 (c) 6 (d) $), flk, kfi%h$ ( 6 (c) 6 (d) $). 6 (e) 6 (f ) $%, a%, fi, $%$. 4 ibm fi$ 10 $i%fig. 4 hand labeled ground truth trajectory of ibmindoor surveillance video database%, fi$% , fl, q fl%, % tp,tn,fp,fn, %fi (18) (19) $. 5 f%

27、( 1 : p; 2 : gmm ; 3 : $)fig. 5 moving foreground segmentation results under similar background (the first row shows the input video, the second row displays the gmm results, and the third row displays our results)4.3%$ ibm fi, fl 2.1 ;, q %fl. fi%fi%, 9 9 %d, 0.9. ibm fi%$, p 320 240 %fifi, % 15 /.

28、%k. 5 $f%. k, gmm f$ fia ( 5 2 ), $ %$, fl%. $a%, y,k$, $%f%, % ( 5 3 ). 6 $%$ %. $%, k,f$. %, :%fifi%qrfl%k, %fi:(b) (b) background image(a) p(a) input image(d) gmm (d) gmm foreground image(c) gmm (c) gmm segmentation result(f ) $(f ) our foreground image(e) $(e) our segmentation result 6fig. 6,f%m

29、oving foreground segmentation results under cast shadow and similar background4.4$, ,mean shift %qr.$%, %$% 1 , fi (17)$qfi%, q 2 %$%. %$, fl$fi$fl% ( 7 (c) $ 3 fi), f%ya%$%, % ( 7 (c) $ 4 fi). 7 $ 3 fl$%. fl%, q %6, 23 . $, , $k (7 (a) (c) $ 2 fi 3 fi). 7 (c) $, 2%fl ( 7 (c) $ 3 fi), kqr$%, fl% 7 f

30、l$experiment results of two people tracking through occlusionfig. 7 8 $experiment results of three-people tracking through occlusionfig. 83 : %fi383 8 $ 3 $f%. $ 1 $p, 2 $ %. %fi, $ %qra, $%$fi$% 3 % ( 8 $ #180, #222). 3 %q%, $%, q %qr. $ , $k$ 3 % ( 8 $ #180, #222), q 3 $ ( 8 $ #204, #240). 25 fi (

31、18) $% . 9 $ ibm fi$% 10 , 7 443 % . fi, $f%: (false negative rate, fnr) 0.027 (9), $%f%. %, %fi, f% ; %, n $ m (m n ) %, f%$ . fi% (false positive rate, fpr) 0.077, , ibm fi$ fl, 10 fifi$qr64 , $f 50 , 0.22. flk, , $%, fi% fi 10 /.%, %, $%. $, $i% ibm fi$fi , f%$. %$,$%f, fi% %, %p, % f%.references

32、1 senior a, hampapur a, tian y l, brown l, pankanti s, bolle r. appearance models for occlusion handling. image and vision computing, 2006, 24(11): 123312432 cucchiara r, grana c, tardini g, vezzani r. probabilistic people tracking for occlusion handling. in: proceedings of the 17th international co

33、nference on pattern recognition. cambridge, uk: ieee, 2004. 1321353 nguyen h t, smeulders a w m. fast occluded object track- ing by a robust appearance filter. ieee transactions on pattern analysis and machine intelligence, 2004, 26(8):109911044 wu y, yu t, hua g. tracking appearances with occlu- sions. in: proceedings of ieee computer vision and pat- tern recognition. wisconsin, usa: ieee, 20