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 Jing2PAN 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 characteristics 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 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 words 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%, %, 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 Program 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. Shaanxi 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 an710129, 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 %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%,