2000CVPR最佳论文-运用均值漂移实现对非刚性物体的实时追踪

Real TimeTrackingofNon RigidObjectsusingMeanShift DorinComaniciuVisvanathanRameshPeterMeer Imaging VisualizationDepartmentElectrical ComputerEngineeringDepartment SiemensCorporateResearchRutgersUniversity CollegeRoadEast Princeton NJ BrettRoad Piscataway NJ Abstract Anewmethodforreal timetrackingofnon rigidob jectsseenfromamovingcameraisproposed Thecen tralcomputationalmoduleisbasedonthemeanshift iterationsand ndsthemostprobabletargetpositionin thecurrentframe Thedissimilaritybetweenthetarget model itscolordistribution andthetargetcandidates isexpressedbyametricderivedfromtheBhattacharyya coe cient Thetheoreticalanalysisoftheapproach showsthatitrelatestotheBayesianframeworkwhile providingapractical fastande cientsolution The capabilityofthetrackertohandleinreal timepartial occlusions signi cantclutter andtargetscalevaria tions isdemonstratedforseveralimagesequences Introduction Thee cienttrackingofvisualfeaturesincomplex environmentsisachallengingtaskforthevisioncom munity Real timeapplicationssuchassurveillanceand monitoring perceptualuserinterfaces smart rooms andvideocompression allrequire theabilitytotrackmovingobjects Thecomputational complexityofthetrackeriscriticalformostapplica tions onlyasmallpercentageofasystemresourcesbe ingallocatedfortracking whiletherestisassignedto preprocessingstagesortohigh leveltaskssuchasrecog nition trajectoryinterpretation andreasoning Thispaperpresentsanewapproachtothereal time trackingofnon rigidobjectsbasedonvisualfeatures suchascolorand ortexture whosestatisticaldistribu tionscharacterizetheobjectofinterest Theproposed trackingisappropriateforalargevarietyofobjectswith di erentcolor texturepatterns beingrobusttopartial occlusions clutter rotationindepth andchangesin cameraposition Itisanaturalapplicationtomotion analysisofthemeanshiftprocedureintroducedearlier Themeanshiftiterationsareemployedto nd thetargetcandidatethatisthemostsimilartoagiven targetmodel withthesimilaritybeingexpressedbya metricbasedontheBhattacharyyacoe cient Vari oustestsequencesshowedthesuperiortrackingperfor mance obtainedwithlowcomputationalcomplexity Thepaperisorganizedasfollows Section presents andextendsthemeanshiftproperty Section intro ducesthemetricderivedfromtheBhattacharyyacoef cient Thetrackingalgorithmisdevelopedandana lyzedinSection Experimentsandcomparisonsare giveninSection andthediscussionsareinSection MeanShiftAnalysis Wede nenextthesamplemeanshift introducethe iterativemeanshiftprocedure andpresentanewthe oremshowingtheconvergenceforkernelswithconvex andmonotonicpro les Forapplicationsofthemean shiftpropertyinlowlevelvision ltering segmenta tion see SampleMeanShift Givenasetfx i g i n ofnpointsinthed dimensionalspaceR d themultivariatekerneldensity estimatewithkernelK x andwindowradius band width h computedinthepointxisgivenby f x nh d n X i K x x i h Theminimizationoftheaverageglobalerrorbetween theestimateandthetruedensityyieldsthemultivariate Epanechnikovkernel p K E x c d d kxk ifkxk otherwise wherec d isthevolumeoftheunitd dimensionalsphere Anothercommonlyusedkernelisthemultivariatenor mal K N x d exp kxk Letusintroducethepro leofakernelKasafunc tionk RsuchthatK x k kxk For example accordingto theEpanechnikovpro leis k E x c d d x ifx otherwise andfrom thenormalpro leisgivenby k N x d exp x Employingthepro lenotationwecanwritethedensity estimate as f K x nh d n X i k x x i h Wedenote g x k x assumingthatthederivativeofkexistsforallx exceptfora nitesetofpoints AkernelG canbede nedas G x Cg kxk whereCisanormalizationconstant Then bytaking theestimateofthedensitygradientasthegradientof thedensityestimatewehave rf K x r f K x nh d n X i x x i k x x i h nh d n X i x i x g x x i h nh d n X i g x x i h P n i x i g x x i h P n i g x x i h x where P n i g x x i h canbeassumedtobe nonzero NotethatthederivativeoftheEpanechnikov pro leistheuniformpro le whilethederivativeofthe normalpro leremainsanormal Thelastbracketin containsthesamplemean shiftvector M h G x P n i x i g x x i h P n i g x x i h x andthedensityestimateatx f G x C nh d n X i g x x i h computedwithkernelG Usingnow and becomes rf K x f G x C h M h G x fromwhereitfollowsthat M h G x h C rf K x f G x Expression showsthatthesamplemeanshiftvec torobtainedwithkernelGisanestimateofthenormal izeddensitygradientobtainedwithkernelK Thisisa moregeneralformulationoftheproperty rstremarked byFukunaga p ASu cientConvergenceCondition Themeanshiftprocedureisde nedrecursivelyby computingthemeanshiftvectorM h G x andtrans latingthecenterofkernelGbyM h G x Letusdenoteby y j j thesequenceofsucces sivelocationsofthekernelG where y j P n i x i g y j x i h P n i g y j x i h j istheweightedmeanaty j computedwithkernelG andy isthecenteroftheinitialkernel Thedensity estimatescomputedwithkernelKinthepoints are f K n f K j o j n f K y j o j Thesedensitiesareonlyimplicitlyde nedtoobtain rf K Howeverweneedthemtoprovetheconvergence ofthesequences and Theorem IfthekernelKhasaconvexandmono tonicdecreasingpro leandthekernelGisde nedac cordingto and thesequences and are convergent TheTheorem generalizestheconvergenceshown in whereKwastheEpanechnikovkernel andG theuniformkernel ItsproofisgivenintheAppendix NotethatTheorem isalsovalidwhenweassociateto eachdatapointx i apositiveweightw i BhattacharyyaCoe cientBased MetricforTargetLocalization Thetaskof ndingthetargetlocationinthecurrent frameisformulatedasfollows Thefeaturezrepre sentingthecolorand ortextureofthetargetmodelis assumedtohaveadensityfunctionq z whilethetarget candidatecenteredatlocationyhasthefeaturedis tributedaccordingtop z y Theproblemisthento ndthediscretelocationywhoseassociateddensity p z y isthemostsimilartothetargetdensityq z Tode nethesimilaritymeasurewetakeintoaccount thattheprobabilityofclassi cationerrorinstatistical hypothesistestingisdirectlyrelatedtothesimilarity ofthetwodistributions Thelargertheprobabilityof error themoresimilarthedistributions Therefore contrarytothehypothesistesting weformulatethe targetlocationestimationproblemasthederivationof theestimatethatmaximizestheBayeserrorassociated withthemodelandcandidatedistributions Forthe moment weassumethatthetargethasequalprior probabilitytobepresentatanylocationyintheneigh borhoodofthepreviouslyestimatedlocation AnentitycloselyrelatedtotheBayeserroristhe Bhattacharyyacoe cient whosegeneralformisde nedby y p y q Z p p z y q z dz PropertiesoftheBhattacharyyacoe cientsuchasits relationtotheFishermeasureofinformation quality ofthesampleestimate andexplicitformsforvarious distributionsaregivenin Ourinterestinexpression is however moti vatedbyitsnearoptimalitygivenbytherelationship totheBayeserror Indeed letusdenoteby and twosetsofparametersforthedistributionspandqand by p q asetofpriorprobabilities Ifthevalue of issmallerfortheset thanfortheset it canbeproved that thereexistsasetofpriors forwhichtheerrorprobabilityfortheset islessthan theerrorprobabilityfortheset Inaddition starting from upperandlowererrorboundscanbederived fortheprobabilityoferror ThederivationoftheBhattacharyyacoe cientfrom sampledatainvolvestheestimationofthedensitiesp andq forwhichweemploythehistogramformulation Althoughnotthebestnonparametricdensityestimate thehistogramsatis esthelowcomputationalcost imposedbyreal timeprocessing Weestimatethedis cretedensity q f q u g u m with P m u q u fromthem binhistogramofthetargetmodel while p y f p u y g u m with P m u p u isestimated atagivenlocationyfromthem binhistogramofthe targetcandidate Hence thesampleestimateofthe Bhattacharyyacoe cientisgivenby y p y q m X u p p u y q u Thegeometricinterpretationof isthecosineof theanglebetweenthem dimensional unitvectors p p p p m and p q p q m Usingnow thedistancebetweentwodistribu tionscanbede nedas d y p p y q Thestatisticalmeasure iswellsuitedforthe taskoftargetlocalizationsince Itisnearlyoptimal duetoitslinktotheBayes error Notethatthewidelyusedhistograminter sectiontechnique hasnosuchtheoreticalfoun dation Itimposesametricstructure seeAppendix The Bhattacharyyadistance p orKullbackdi vergence p arenotmetricssincetheyviolate atleastoneofthedistanceaxioms Usingdiscretedensities isinvarianttothe scaleofthetarget uptoquantizatione ects His togramintersectionisscalevariant Beingvalidforarbitrarydistributions thedis tance issuperiortotheFisherlineardiscrim inant whichyieldsusefulresultsonlyfordistri butionsthatareseparatedbythemean di erence p Similarmeasureswerealreadyusedincomputervi sion TheCherno andBhattacharyyaboundshave beenemployedin todeterminethee ectivenessof edgedetectors TheKullbackdivergencehasbeenused in for ndingtheposeofanobjectinanimage Thenextsectionshowshowtominimize asa functionofyintheneighborhoodofagivenlocation byexploitingthemeanshiftiterations Onlythedistri butionoftheobjectcolorswillbeconsidered although thetexturedistributioncanbeintegratedintothesame framework TrackingAlgorithm Weassumeinthesequelthesupportoftwomodules whichshouldprovide a detectionandlocalizationin theinitialframeoftheobjectstotrack targets and b periodicanalysisofeachobjecttoaccountfor possibleupdatesofthetargetmodelsduetosigni cant changesincolor ColorRepresentation TargetModelLetfx i g i n bethepixelloca tionsofthetargetmodel centeredat Wede nea functionb R f mgwhichassociatestothe pixelatlocationx i theindexb x i ofthehistogram bincorrespondingtothecolorofthatpixel Theprob abilityofthecoloruinthetargetmodelisderivedby employingaconvexandmonotonicdecreasingkernel pro lekwhichassignsasmallerweighttothelocations thatarefartherfromthecenterofthetarget The weightingincreasestherobustnessoftheestimation sincetheperipheralpixelsaretheleastreliable be ingoftena ectedbyocclusions clutter orbackground Theradiusofthekernelpro leistakenequaltoone byassumingthatthegenericcoordinatesxandyare normalizedwithh x andh y respectively Hence wecan write q u C n X i k kx i k b x i u where istheKroneckerdeltafunction Thenormal izationconstantCisderivedbyimposingthecondition P m u q u fromwhere C P n i k kx i k sincethesummationofdeltafunctionsforu m isequaltoone TargetCandidatesLetfx i g i n h bethepixel locationsofthetargetcandidate centeredatyinthe currentframe Usingthesamekernelpro lek butwith radiush theprobabilityofthecoloruinthetarget candidateisgivenby p u y C h n h X i k y x i h b x i u whereC h isthenormalizationconstant Theradiusof thekernelpro ledeterminesthenumberofpixels i e thescale ofthetargetcandidate Byimposingthe conditionthat P m u p u weobtain C h P n h i k k y x i h k NotethatC h doesnotdependony sincethepixello cationsx i areorganizedinaregularlattice ybeingone ofthelatticenodes Therefore C h canbeprecalculated foragivenkernelanddi erentvaluesofh DistanceMinimization AccordingtoSection themostprobablelocation yofthetargetinthecurrentframeisobtainedbymin imizingthedistance whichisequivalenttomaxi mizingtheBhattacharyyacoe cient y Thesearch forthenewtargetlocationinthecurrentframestartsat theestimatedlocation y ofthetargetintheprevious frame Thus thecolorprobabilitiesf p u y g u m ofthetargetcandidateatlocation y inthecurrent framehavetobecomputed rst UsingTaylorexpan sionaroundthevalues p u y theBhattacharyyaco e cient isapproximatedas aftersomemanipula tions p y q m X u p p u y q u m X u p u y s q u p u y whereitisassumedthatthetargetcandidate f p u y g u m doesnotchangedrasticallyfromthe initialf p u y g u m andthat p u y forall u m Introducingnow in weobtain p y q m X u p p u y q u C h n h X i w i k y x i h where w i m X u b x i u s q u p u y Thus tominimizethedistance thesecondterm inequation hastobemaximized the rstterm beingindependentofy Thesecondtermrepresents thedensityestimatecomputedwithkernelpro lekat yinthecurrentframe withthedatabeingweightedby w i Themaximizationcanbee cientlyachieved basedonthemeanshiftiterations usingthefollowing algorithm BhattacharyyaCoe cient p y q Maximization Giventhedistributionf q u g u m ofthetargetmodel andtheestimatedlocation y ofthetargetinthepre viousframe Initializethelocationofthetargetinthecur rentframewith y computethedistribution f p u y g u m andevaluate p y q P m u p p u y q u Derivetheweightsfw i g i n h accordingto Basedonthemeanshiftvector derivethenew locationofthetarget y P n h i x i w i g y x i h P n h i w i g y x i h Updatef p u y g u m andevaluate p y q P m u p p u y q u While p y q p y q Do y y y Ifk y y k Stop OtherwiseSet y y andgotoStep Theproposedoptimizationemploysthemeanshiftvec torinStep toincreasethevalueoftheapproximated Bhattacharyyacoe cientexpressedby Sincethis operationdoesnotnecessarilyincreasethevalueof p y q thetestincludedinStep isneededtovali datethenewlocationofthetarget However practical experiments trackingdi erentobjects forlongperi odsoftime showedthattheBhattacharyyacoe cient computedatthelocationde nedbyequation was almostalwayslargerthanthecoe cientcorresponding to y Lessthan oftheperformedmaximizations yieldedcaseswheretheStep iterationswerenecessary Theterminationthreshold usedinStep isderived byconstrainingthevectorsrepresenting y and y to bewithinthesamepixelinimagecoordinates Thetrackingconsistsinrunningforeachframethe optimizationalgorithmdescribedabove Thus given thetargetmodel thenewlocationofthetargetinthe currentframeminimizesthedistance intheneigh borhoodofthepreviouslocationestimate ScaleAdaptation Thescaleadaptationschemeexploitstheproperty ofthedistance tobeinvarianttochangesinthe objectscale Wesimplymodifytheradiushofthe kernelpro lewithacertainfraction weused letthetrackingalgorithmtoconvergeagain andchoose theradiusyieldingthelargestdecreaseinthedistance AnIIR lterisusedtoderivethenewradius basedonthecurrentmeasurementsandoldradius Experiments Theproposedmethodhasbeenappliedtothetask oftrackingafootballplayermarkedbyahand drawn ellipsoidalregion rstimageofFigure These quencehas framesof pixelseachand theinitialnormalizationconstants determinedfrom thesizeofthetargetmodel were h x h y TheEpanechnikovpro le hasbeenusedforhis togramcomputation therefore themeanshiftitera tionswerecomputedwiththeuniformpro le Thetar gethistogramhasbeenderivedintheRGBspacewith bins Thealgorithmrunscomfortablyat fpsona MHzPC Javaimplementation ThetrackingresultsarepresentedinFigure The meanshiftbasedtrackerprovedtoberobusttopartial occlusion clutter distractors frame inFigure Figure Footballsequence Trackingtheplayerno withinitialwindowof pixels Theframes and areshown andcameramotion Sincenomotionmodelhasbeen assumed thetrackeradaptedwelltothenonstationary characteroftheplayer smovements whichalternates abruptlybetweenslowandfastaction Inaddition theintenseblurringpresentinsomeframesanddueto thecameramotion didnotin uencethetrackerper formance frame inFigure Thesamee ect however canlargelyperturbcontourbasedtrackers 050100150 2 4 6 8 10 12 14 16 18 Frame Index Mean Shift Iterations Figure Thenumberofmeanshiftiterationsfunction oftheframeindexfortheFootballsequence Themean numberofiterationsis perframe Thenumberofmeanshiftiterationsnecessaryfor eachframe onescale intheFootballsequenceisshown inFigure Onecanidentifytwocentralpeaks corre spondingtothemovementoftheplayertothecenter oftheimageandbacktotheleftside Thelastand largestpeakisduetothefastmovementfromtheleft totherightside 40 20 0 20 40 40 20 0 20 40 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 X Y Bhattacharyya Coefficient Initial location Convergence point Figure ValuesoftheBhattacharyyacoe cientcor respondingtothemarkedregion pixels in frame fromFigure Thesurfaceisasymmetric duetotheplayercolorsthataresimilartothetarget Fourmeanshiftiterationswerenecessaryforthealgo rithmtoconvergefromtheinitiallocation circle Todemonstratethee ciencyofourapproach Fig ure presentsthesurfaceobtainedbycomputingthe Bhattacharyyacoe cientfortherectanglemarkedin Figure frame Thetargetmodel theselected ellipticalregioninframe hasbeencomparedwith thetargetcandidatesobtainedbysweepingtheellipti calregioninframe insidetherectangle Whilemost ofthetrackingapproachesbasedonregions mustperformanexhaustivesearchintherectangleto ndthemaximum ouralgorithmconvergedinfourit erationsasshowninFigure Notethatsincethebasin ofattractionofthemodecoverstheentirewindow the correctlocationofthetargetwouldhavebeenreached alsofromfartherinitialpoints Anoptimizedcompu tationoftheexhaustivesearchofthemode hasa muchlargerarithmeticcomplexity dependingonthe chosensearcharea Thenewmethodhasbeenappliedtotrackpeopleon subwayplatforms Thecamerabeing xed additional geometricconstraintsandalsobackgroundsubtraction canbeexploitedtoimprovethetrackingprocess The followingsequences however havebeenprocessedwith thealgorithmunchanged A rstexampleisshowninFigure demonstrating thecapabilityofthetrackertoadapttoscalechanges Thesequencehas framesof pixelseach andtheinitialnormalizationconstantswere h x h y Figure presentssixframesfroma minutese quenceshowingthetrackingofapersonfromthemo mentsheentersthesubwayplatformtillshegetson thetrain frames Thetrackingperformanceis remarkable takingintoaccountthelowqualityofthe processedsequence duetothecompressionartifacts A thoroughevaluationofthetracker however issubject toourcurrentwork Theminimumvalueofthedistance foreach frameisshowninFigure Thecompressionnoise determinedthedistancetoincreasefrom perfect match toastationaryvalueofabout Signi cant deviationsfromthisvaluecorrespondtoocclusionsgen eratedbyotherpersonsorrotationsindepthofthetar get Thelargedistanceincreaseattheendsignalsthe completeocclusionofthetarget Discussion Byexploitingthespatialgradientofthestatistical measure thenewmethodachievesreal timetrack ingperformance whilee ectivelyrejectingbackground clutterandpartialocclusions Notethatthesametechniquecanbeemployed toderivethemeasurementvectorforoptimalpredic tionschemessuchasthe Extended Kalman lter p ormultiplehypothesistrackingapproaches Inreturn thepredictioncandetermine thepriors de ningthepresenceofthetargetinagiven neighborhood assumedequalinthispaper Thiscon nectionishoweverbeyondthescopeofthispaper A patentapplicationhasbeen ledcoveringthetracking algorithmtogetherwiththeKalmanextensionandvar iousapplications We nallyobservethattheideaofcentroidcompu tationisalsoemployedin Themeanshiftwas u