FUNDAMENTALS OF OBJECT TRACKING Kalmanfilter,particlefilter,IMM,PDA,ITS,randomsets...Thenumberofuseful objecttrackingmethodsisexploding.Buthowaretheyrelated?Howdotheyhelp totrackeverythingfromaircraft,missilesandextra-terrestrialobjectstopeopleand lymphocytecells?Howcantheybeadaptedtonovelapplications? Fundamentals ofObjectTrackingtellsyouhow. Starting with the generic object tracking problem, it outlines the generic Bayesiansolution.Itthenshowssystematicallyhowtoformulatethemajortrack- ing problems – maneuvering, multi-object, clutter, out-of-sequence sensors – withinthisBayesianframeworkandhowtoderivethestandardtrackingsolutions. Thisstructuredapproachmakesverycomplexobjecttrackingalgorithmsaccessi- ble to the growing number of users working on real-world tracking problems and supportsthemindesigningtheirowntrackingfiltersundertheiruniqueapplication constraints.Thebookconcludeswithachapteronissuescriticaltothesuccessful implementationoftrackingalgorithms,suchastrackinitializationandmerging. SUBHASH CHALLA is a Professor and Senior Principal Researcher at the NICTA, Victoria Research Laboratory at the University of Melbourne. He is also the co-founder and CEO of SenSen Networks Pty Ltd, a leading video business intelligencesolutionscompany. MARK R. MORELANDE isaSeniorResearchFellowintheMelbourneSystems LaboratoryattheUniversityofMelbourne. DARKO MUSˇICKI isaProfessorintheDepartmentofElectronicSystemsEngi- neeringatHanyangUniversityinAnsan,RepublicofKorea. ROBIN J. EVANS is a Professor of Electrical Engineering at the University of MelbourneandtheDirectorofNICTA,VictoriaResearchLaboratory. WilliamofOckham Frustrafitperplura,quodfieripotestperpauciora (Itisvaintodowithmorewhatcanbedonewithless) FUNDAMENTALS OF OBJECT TRACKING SUBHASH CHALLA NationalICTAustralia(NICTA),UniversityofMelbourne,Australia MARK R. MORELANDE UniversityofMelbourne,Australia DARKO MUSˇ ICKI HanyangUniversity,Ansan,RepublicofKorea ROBIN J. EVANS NationalICTAustralia(NICTA),UniversityofMelbourne,Australia CAMBRIDGE UNIVERSITY PRESS Cambridge,NewYork,Melbourne,Madrid,CapeTown, Singapore,Sa˜oPaulo,Delhi,Tokyo,MexicoCity CambridgeUniversityPress TheEdinburghBuilding,CambridgeCB28RU,UK PublishedintheUnitedStatesofAmericabyCambridgeUniversityPress,NewYork www.cambridge.org Informationonthistitle:www.cambridge.org/9780521876285 (cid:2)C S.Challa,M.R.Morelande,D.MusˇickiandR.J.Evans2011 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2011 PrintedintheUnitedKingdomattheUniversityPress,Cambridge AcataloguerecordforthispublicationisavailablefromtheBritishLibrary LibraryofCongressCataloginginPublicationdata Fundamentalsofobjecttracking/SubhashChalla...[etal.]. p. cm. Includesindex. ISBN978-0-521-87628-5(hardback) 1.Linearprogramming. 2.Programming(Mathematics) I.Challa,Sudha,1953– QA402.5.F86 2011 519.7–dc22 2011008595 ISBN978-0-521-87628-5Hardback CambridgeUniversityPresshasnoresponsibilityforthepersistenceor accuracyofURLsforexternalorthird-partyinternetwebsitesreferredto inthispublication,anddoesnotguaranteethatanycontentonsuch websitesis,orwillremain,accurateorappropriate. Contents Preface pageix 1 Introductiontoobjecttracking 1 1.1 Overviewofobjecttrackingproblems 2 1.2 Bayesianreasoningwithapplicationtoobjecttracking 7 1.3 RecursiveBayesiansolutionforobjecttracking 16 1.4 Summary 21 2 Filteringtheoryandnon-maneuveringobjecttracking 22 2.1 TheoptimalBayesianfilter 22 2.2 TheKalmanfilter 25 2.3 TheextendedKalmanfilter 31 2.4 TheunscentedKalmanfilter 36 2.5 Thepointmassfilter 43 2.6 Theparticlefilter 46 2.7 Performancebounds 53 2.8 Illustrativeexample 57 2.9 Summary 60 3 Maneuveringobjecttracking 62 3.1 Modelingformaneuveringobjecttracking 62 3.2 TheoptimalBayesianfilter 66 3.3 Generalizedpseudo-Bayesianfilters 72 3.4 Interactingmultiplemodelfilter 84 3.5 Particlefiltersformaneuveringobjecttracking 91 3.6 Performancebounds 97 3.7 Illustrativeexample 99 3.8 Summary 102 v vi Contents 4 Single-objecttrackinginclutter 103 4.1 TheoptimalBayesianfilter 104 4.2 Thenearestneighborfilter 107 4.3 Theprobabilisticdataassociationfilter 111 4.4 Maneuveringobjecttrackinginclutter 119 4.5 Particlefilterfortrackinginclutter 122 4.6 Performancebounds 126 4.7 Illustrativeexamples 131 4.8 Summary 132 5 Single-andmultiple-objecttrackinginclutter: object-existence-basedapproach 133 5.1 Introduction 133 5.2 Problemstatement/models 138 5.3 Trackstate 142 5.4 OptimalBayes’recursion 147 5.5 Optimaltrackupdatecycle 171 5.6 Trackcomponentcontrol 184 5.7 Object-existence-basedsingle-objecttracking 191 5.8 Object-existence-basedmulti-objecttracking 205 5.9 Summary 221 6 Multiple-objecttrackinginclutter:random-set-basedapproach 223 6.1 TheoptimalBayesianmulti-objecttrackingfilter 225 6.2 Theprobabilistichypothesisdensityapproximations 227 6.3 Approximatefilters 237 6.4 Object-existence-basedtrackingfilters 244 6.5 Performancebounds 260 6.6 Illustrativeexample 262 6.7 Summary 264 7 Bayesiansmoothingalgorithmsforobjecttracking 265 7.1 Introductiontosmoothing 265 7.2 OptimalBayesiansmoothing 266 7.3 AugmentedstateKalmansmoothing 268 7.4 Smoothingformaneuveringobjecttracking 271 7.5 Smoothingforobjecttrackinginclutter 275 7.6 Smoothingwithobjectexistenceuncertainty 278 7.7 Illustrativeexample 283 7.8 Summary 288 Contents vii 8 Objecttrackingwithtime-delayed,out-of-sequence measurements 289 8.1 OptimalBayesiansolutiontotheOOSMproblem 289 8.2 Single-andmulti-lagOOSMalgorithms 293 8.3 AugmentedstateKalmanfilterformultiple-lagOOSM 294 8.4 AugmentedstatePDAfilterformultiple-lagOOSMinclutter 297 8.5 Simulationresults 302 8.6 Summary 311 9 Practicalobjecttracking 312 9.1 Introduction 312 9.2 Linearmulti-targettracking 313 9.3 Cluttermeasurementdensityestimation 317 9.4 Trackinitialization 322 9.5 Trackmerging 329 9.6 Illustrativeexamples 332 9.7 Summary 343 AppendixA: Mathematicalandstatisticalpreliminaries 344 AppendixB: Finitesetstatistics(FISST) 354 AppendixC: Pseudo-functionsinobjecttracking 358 References 361 Index 370 Preface Tracking the paths of moving objects is an activity with a long history. People in ancient societies used to track moving prey to hunt and feed their kith and kin, and invented ways to track the motion of stars for navigation purposes and to predict seasonal changes in their environments. Object tracking has been an essentialtechnologyforhumansurvivalandhassignificantlycontributedtohuman progress. In recent times, there has been an explosion in the use of object tracking tech- nology in non-military applications. Object tracking algorithms have become an essentialpartofourdailylives.Forexample,GPS-basednavigationisadailytool ofhumankind.Inthisapplicationagroupofartificialsatellitesinouterspacecon- tinuouslylocatethevehiclespeopledriveandtheobjecttrackingalgorithmswithin the GPS perform self-localization and enable us to enjoy a number of location- based services, such as finding places of interest and route planning. Similarly, tracking of objects is used in a wide variety of contexts, such as airspace surveil- lance,satelliteandspacevehicletracking,submarineandwhaletrackingandintel- ligentvideosurveillance.Theyarealsousedinautonomousrobotnavigationusing lasers, stereo cameras and other proximity sensors, radiosonde-enabled balloon tracking for accurate weather predictions, and, more recently, in the study of cell biologytostudycellfateunderdifferentchemicalandenvironmentalinfluencesby trackingmanykindsofcells,includinglymphocyteandstemcellsthroughmulti- plegenerationsofbirthanddeath. This book is an introduction to the fascinating field of object tracking and provides a solid foundation to the collection of diverse algorithms developed over the past 60 years by academics, scientific researchers and engineers. His- torically, advances in the field of object tracking were a result of the systematic extension of methods that worked under severely restrictive ideal-world condi- tions to less restrictive real-world conditions. The advances were often a result of inspired innovations by scientists incorporating either more descriptive object ix