FROMGAITSEQUENCES
AravindSundaresan,AmitRoyChowdhury,RamaChellappa
CentreforAutomationResearch,andDepartmentofElectricalandComputerEngineering
UniversityofMaryland,CollegePark,MD20742
ABSTRACT
InthispaperweproposeagenericframeworkbasedonHid-denMarkovModels(HMMs)forrecognitionofindividualsfromtheirgait.TheHMMframeworkissuitable,becausethegaitofanindividualcanbevisualizedashisadoptingposturesfromaset,inasequencewhichhasanunderlyingstructuredprobabilisticna-ture.TheposturesthattheindividualadoptscanberegardedasthestatesoftheHMMandaretypicaltothatindividualandpro-videameansofdiscrimination.Theframeworkassumesthat,dur-inggait,theindividualtransitionsbetweenNdiscreteposturesorstatesbutitisnotdependentontheparticularfeaturevectorusedtorepresentthegaitinformationcontainedinthepostures.Theframework,thus,providesflexibilityintheselectionofthefeaturevector.ThestatisticalnatureoftheHMMlendsrobustnesstothemodel.Inthispaperweusethebinarizedbackground-subtractedimageasthefeaturevectorandusedifferentdistancemetrics,suchasthosebasedontheL1andL2normsofthevectordifference,andthenormalizedinnerproductofthevectors,tomeasurethesimilaritybetweenfeaturevectors.Theresultsweobtainarebet-terthanthebaselinerecognitionratesreportedbefore.
1.INTRODUCTION
Biometricscanbeapowerfulcueforreliableautomatedpersonidentificationandthereexistseveralestablishedbiometric-basedidentificationtechniquesincludingfingerprintandhandgeometrymethods,speakeridentification,facerecognitionandirisidentifi-cation.However,theapplicabilityofallthesemethodologiesisusuallyrestrictedtocontrolledenvironmentsorrequirecoopera-tionofthesubject.We,therefore,needtoexplorebiometricsigna-tureswhichcanbeobtainednon-invasivelyfromadistance.Gaitisonesuchbiometricwhichiscurrentlybeingexploredforpurposessuchasidentification.Weknowfromexperiencethatpeopleoftenrecognizeothersbysimplyobservingthewaytheywalkimply-ingthatbodyshapeanddynamicsaresufficientlydistinctacrosshumans.
Ithasbeenobservedthatgaitcanbemodelledasatransi-tionacrossstates,whereeachstateisexemplifiedbyatypicalfeaturevectororexemplar.Inthispaperweproposeageneralframeworkthatemploysexemplar-basedHMMstocharacterizeanindividual’sgaitandthereafterrecognizetheindividualfromhisgait.HMMshavebeenusedinspeechmodellingand[1]pro-videsagoodtutorialonHMMs.Theuseoftemporaltemplates,whichcapturemotionofeachpixelintheframe,hasbeenpro-posedforrecognitionofbothhumanactions[2]andhumansfrom
SupportedbytheDARPA/ONRgrantN00014-03-1-0520
theirgait[3].HMMshavealsobeenusedtorecognizehumanac-tions[4,5,6].Exemplarshavebeenusedinlearningprobabilisticmodelsin[7]andtrackingin[8].Ourobjectiveistorecognizeanindividualfromavideosequenceoftheindividualwalkinginafronto-parallelpose.Werepresentthestructuralaspectofthepersonbyusingtypicalfeaturevectorscorrespondingtodiffer-ent“states”,andthedynamicalaspectoftheindividual’sgaitbymodellingthetransitionbetweenthese“states”usingthetransi-tionmatrixlikein[9].Weintegratethesetwocomponentstotrainmodelsforrepresentationandidentification.Additionally,wepro-poseaprobabilitydistributionfortheobservationsbasedontheexemplars.Thisframeworkaffordsusflexibilityinourchoiceoffeaturevectors,andsuitabledistancemetricscorrespondingtothefeaturevectorsthatwechoose.Weprovidealgorithmstotraintheexemplarsasafunctionofallthefeaturevectorsunlike[9]whichselectsjustNframesastheexemplarsandtrainstheFeature-to-Exemplardistancevectorsinstead.Thisstepmakesouralgorithmmuchlesssusceptibletonoiseinthefeaturevectors.Inourexper-iments,wehaveusedvideosequencesfromtheUSFdatabase[10].Wecomparetheperformanceofouralgorithmtothebaselineal-gorithmproposedin[11].
2.OVERVIEWOFTHEHMMFRAMEWORKLetthedatabaseconsistsofvideosequencesofPpersons.TheHMMforthepthpersonisgivenbyλp=(Ap,Bp,πp)withNnumberofstates.Themodel,λp,istrainedusingtheobservationsequencefortheOp={Opppthperson,p
i.e.thesequenceoffeaturevectors
1,O2,...,OTpthevideosequenceofthep}th,whereperson.TpisthenumberofframesinApisthetransitionmatrix,andπpistheinitialdistribution.TheBpparametercomprisesoftheprobabilitydistributionsforafeaturevectorconditionalstateindex,i.e.,theset{Pppp
onthe
1(.),P2(.),...,PN(.)}(see(1)).Theprobabilitydistributionsaredefinedintermsofexemplars,wherethejthexemplarisatypicalrealizationofthejthstate.TheemplarsforthepthpersonaregivenbyEp={Epp,Ep
ex-Henceforth,thesuperscriptdenotingtheindex1,Eofthe2,...personN}is.droppedforsimplicity.Themotivationbehindusinganexemplar-basedmodelisthattherecognitioncanbebasedonthedistancemeasurebetweentheobservedfeaturevectorandtheexemplars.Thedistancemetricisevidentlyakeyfactorintheperformanceofthealgorithm.Pj(Ot)isdefinedasafunctionofD(Ot,Ej),thedistanceofthefeaturevectorOtfromthejthexemplar.
Pj(Ot)=αe−αD(Ot,Ej)
(1)
Duringthetrainingphase,amodelisbuiltforallthesubjectsinthegallery,indexedbyp=1,2,...,P.Aninitialestimateof
F1F2F3F4F5F6F7
Fig.1.PartofanObservationSequence
EpandλpisformedfromOp,andtheseestimatesarerefinedit-erativelyusingExpectation-Maximisation.NotethatBiscom-pletelydefinedbyEifαisfixedbeforehand.WecaniterativelyrefineestimatesofAandπbyusingtheBaum-WelchalgorithmandkeepingEfixed.ThealgorithmtorefineestimatesofEisde-terminedbythechoiceofthedistancemetric.GivenaGalleryLT,=X{=λ1,λ2,...,λP{X1,X2,...},,XweTidentifyaprobesequenceoflength{q1,q2,...,qT},qtbeingthe}statetraversingindexanattimeunknownt,as
pathQ=ID=argpmaxQ,p
Pr[Q|X,λp].
(2)
3.METHODOLOGY
Thefeaturevectorweuseintheexperimentsisthebinarizedver-sionofthebackgroundsubtractedimagesprovidedintheUSFdatabase.TheimagesarescaledandalignedtothecentreoftheframeasinFig.1whichfeaturespartofasequenceoffeaturevec-tors.WedescribeinthissectionthemethodsusedtoobtaininitialestimatestheHMMparameters,thetrainingalgorithmandfinallyandidentificationfromaprobesequence.3.1.InitialEstimateofHMMParameters
Inordertoobtainagoodestimateoftheexemplarsandthetran-sitionmatrix,wefirstobtainaninitialestimateofanorderedsetofexemplarsfromthesequenceandthetransitionmatrixanditer-ativelyrefinetheestimate.TheinitialE0={E01,E02,...,E0
estimatefortheexemplars,
Narefromthejthstateto}eitherissuchthethatjththeoronlythetransitions(jmodNallowed+1)thstate.A0correspondinginitialestimateofthetransitionmatrix,A0
(withAj,j=A0j,jmodN+1=0.5,andallotherA0
j,k=0)isalsoobtained.Theinitialprobabilitesπjaresettobeequalto1/N.
Weobservethatthegaitsequenceisquasi-periodicandweusethisfacttoobtaintheinitialestimateE0.Wecandividethesequenceinto“cycles”,whereacycleisdefinedasthatsegmentofthesequenceboundedbysilhouetteswherethesubjecthasarmsbyhissideandlegsapproximatelyalignedwitheachother.WecanfurtherdivideeachcycleintoNtemporallyadjacentclustersofapproximatelyequalsize.Wevisualizetheframesofthejthclusterofallcyclestobegeneratedfromthejthstate.ThuswecangetagoodinitialestimateofEjfromthefeaturevectorsbe-longingtothejthcluster.Forexample,assumethatthetrainingsequenceisgivenbyY={Y1,Y2,...th,YTthesequenceintoKcycles,withthekcycle}given.WecanbyframespartitioninthesetYk={YSk,YSk+1,...,YSthethindexofthefirstframeofthek+Lkthk−1cycle,},whereandtheSkandLkarelengthofthekcyclerespectively.Wedefinethefirst1clustertocomprise
offrameswithindicesSk,Sk+1,...,Sk+2Lk
/N,Sk+Lk1
−2Lk/N,Sk+Lk−1L/N+1,...,Sk+Lk(j=2,3,...,N)2k
terisdefinedtocompriseofframes−1.Thewithjthclus-indices
Sk+(j−32)Lk/N,Sk+(j−32)Lk/N+1,...,Sk+(j−12)Lk/N.Original Signal800Adaptive Filtered SignalMedian Filtered SignalDifferential Smoothed Signal600slexip d400nuorgero200f fo mus 0detcartbu−200s naeM−400−600−800360380400420440460480500520540Frame indexFig.2.Cycleboundariesestimatedusinganadaptivefilter
Weneedtorobustlyestimatethecycleboundariessothatwecan
partitionthesequenceintoNclustersandobtaintheinitiales-timatesoftheexemplars.Ifthesumsoftheforegroundpixelsofeachimageareplottedwithrespecttotime,then,asperourdefinitionofacycle,theminimasshouldcorrespondtothecy-cleboundaries.Wedenotethesumoftheforegroundpixelsofthesilhouetteinthenthframeass[n].Thissignalisnoisyandmaycontainseveralspuriousminima.Howeverwecanexploitthequasi-periodicityofthesignalandfilterthesignaltoremovethenoisebeforeidentifyingtheminima.Methodssuchasmedianfilteringordifferentialsmoothingofs[n]arenotveryrobustastheydonottakeintoaccountthefrequencyofthegait.Amorerobustmethodwouldbetoanalyses[n]inthefrequencyorthetime-frequencydomain,usingband-passorlow-passfiltersortheShortTimeFourierTransform(STFT).
Thespecificationsoftheband-passfilteraresuchastoal-lowfrequenciesthataretypicalforvery-slow-to-fastwalk.Thevideoiscapturedat30framespersecond,andthesamplingfre-quency,fs=1/30andTs=30.Themaximumgaitfrequencyisassumedtobefm=0.1correspondingtoacycleperiodofTm=10.AHammingwindowoflengthLisused.Theex-tendedsequencex[n]isobtainedbysymmetricallyextendings[n]inbothdirectionsbyL/2.Thereforethesequencex[n]haslengthM=N+L.Theresultantsequenceisfilteredusingaband-passfilter(withuppercut-offfrequencyfuc=fm),inbothdirectionstoremovephasedelay.Thedistancesbetweentheminimasofthefilteredsequenceleadustoanestimateofthecycleperiod.Thecyclefrequencyisestimatedastheinverseofthemedianofcy-cleperiods.Usingthisrevisedestimateofthefrequencygait,f
ˆofthe
,afuc=f
ˆnewfilterisconstructedwithuppercutofffrequency+0.02.Forlongsequences,STFTtechniquescouldbeusedinsteadofstraightforwardfilteringinordertoaccountforaslowlyvaryingfrequencyofgait.Fig.2illustratestheperfor-manceofseveralalgorithmsinidentifyingthecycleboundaries.AmanualexaminationofallthesequencesintheGalleryrevealeda100%detectionratewithhardlyanyfalsedetectionofcycleboul-daries.Wealsoobservedfromthetheinitialexemplarsobtainedusingthecycleregistrationresultsfromthefilteringmethodthatthefrequencybasedfilteringmethodismoreaccurateandrobustcomparedtotheothermethods.
3.2.TrainingtheHMMParameters
Theiterativerefiningoftheestimatesisperformedintwosteps.Inthefirststep,aViterbievaluation[1]ofthesequenceisper-formedusingthecurrentvaluesfortheexemplarsandthetran-sitionmatrix.Thusfeaturevectorsareclusteredaccordingtothemostlikelystatetheyoriginatedfrom.Theexemplarsforthestatesarenewlyestimatedfrom)theseclusters.Usingthecurrentvaluesoftheexemplars,E(iandthetransitionmatrix,A(i),Viterbide-codingisperformedonthesequenceYtoobtainthemostprobable
pathQ={q(i)(i)(i)
(i)1,q2,...,qT},whereqtisthestateattimet.Thusthesetofobservationindices,whosecorrespondingobserva-tionisestimatedtohavebeengeneratedfromstatejisgivenbyT(i)t:q(i)
j={t=j}.Wenowhaveasetofframesforeachstateandwewouldliketoselecttheexemplarssoastomaximisetheprobabilityin(3).Ifweusethedefinitionin(1),(4)follows.
E(i+1)
j=argEmaxQt∈T(i)P(Yt|E)
(3)E(i+1)
j
=argEmin
P
j
t∈T(i)
D(Yt,E)(4)
j
Theactualmethodforminimisingthedistancein(4)howeverde-pendsonthedistancemetricused.Wehaveexperimentedwith
threedifferentdistancemeasures,namelytheEuclidean(EUCLID)distance,theinnerproduct(IP)distance,andthesumofabsolutedifference(SAD)distancewhicharegivenby(5),(6),and(7)re-spectively.NotethatthoughYtandEare2-dimensionalimages,theyarerepresentedasvectorsofdimensionD×1foreaseofnotation.1D×1isavectorofDones.
DEUCLID(Y,E)
=(Y−E)T(Y−E)(5)DIP(Y,E)=1−
√YTEYTYETE(6)DSAD(Y,E)
=
|Y−E|T1D×1
(7)
TheequationsforupdatingthejthelementoftheexemplarsintheEUCLIDdistance,IPdistanceandtheSADdistancecasesaresentedin(8),(9)and(10)respectively.Y
˜pre-denotesthenormalizedvectorYand|T(i)(i)
j|denotesthecardinalityofthesetTj.
E(i+1)
1
j
(j)=|T(i)P
t(j)(8)E(i+1)
j(j)=P
j|
t∈T(i)
Yj
t∈T
(i)Y˜t(j)(9)j
E(i+1)j(j)
=
mediant∈T(i){Yt(j)}
(10)
j
Theexemplarsestimatedforoneobservationsequenceusingthe
threedistancemetricsin(5),(6),and(7)aredisplayedinFig.3.GivenE(i+1)andA(i),wecancalculateA(i+1)usingtheBaum-Welchalgorithm[1].ThuswecaniterativelyrefineourestimatesoftheHMMparameters.Itusuallytakesonlyafewiterationsinordertoobtainanacceptableestimate.3.3.IdentifyingfromaTestSequence
Identifyingthemodelindexfromasequenceinvolvesdecidingwhichofthemodelparameterstousefordiscrimination.Giventhemodelsinthegallery,L={λ1,λ2,...,λPquence,X={X1,X2,...,XT}andtheprobese-andthepaththatmaximisesthe}probability,wewouldoflikethetopathfindthegivenmodeltheprobesequence.TheIDisobtainedasin(2).Wedonotneedto
E1E2E3E4E5E6
(a)Innerproductdistance
E1
E2
E3
E4
E5
E6
(b)Euclideandistance
E1
E2
E3
E4
E5
E6
(c)SADdistance
Fig.3.Exemplarsestimatedusingvariousdistancemeasures
usethetrainedparameterset,λ,asawhole.Forexample,ifwebelievethatthetransitionmatrixispredominantlyindicativeofthespeedatwhichthesubjectwalks,andisthereforenotsuitableasadiscriminantoftheIDofthesubject,thenwehavetheoptionofusingonlypartoftheparametersetgivenbyγp=(Bp,πp)in-steadofusingtheHMMparametersetinitsentirety.Inthiscase,theconditionalprobabilityofthesequence,giventheID,isgivenasfollows.TheBaum-WelchalgorithmcouldbeusedinordertoobtainAXprecursivelyin(12).
Pr[Q|X,γp]=Pr[Q|X,AXp,γp](11)AXp=argAmaxPr[X|A,γp](12)
4.EXPERIMENTALRESULTS
Theobjectiveofourexperimentswastoevaluatetheperformanceofthealgorithmandalsocomparetheefficacyofthedifferentdis-tancemeasuresingaugingthesimilaritybetweentwoimagesasfaraspostureisconcerned.TheUSFdatabasecontainsvideose-quencesof75individualsasubsetofwhomfeatureinsequencescollectedundereachof8differentconditions.ThesequencesarelabelledGallery,ProbeA,ProbeB,ProbeC,ProbeD,ProbeE,ProbeF,andProbeG.Thenumberofvalidbackground-subtractedsequencesinsomeprobesislessthanthenumberofactualse-quences.WetrainedourparametersusingthesequencesfromtheGalleryset.Ineachexperiment,wetriedtoidentifythesequencesineachofthesevenprobesetsfromthemodelsobtainedfromtheGallerysetusingtheinnerproductdistancemeasure.TheIDwascalculatedusing(2).Theexperimentswererepeatedwithdiffer-entdistancemeasures.TheresultsoftheexperimentusingtheIPdistancemeasurebetweenfeaturevectorsintheformofCumula-tiveMatchScores(CMS)plots[11]areinFig.4.Table1givesabriefsummaryoftheexperimentsconducted(GandCdenote
Cumulative Match Scores (Training Set is Gallery)100908070serocS60 hctaM 50evitalum40uC30ProbeAProbeBProbeC20ProbeDProbeEProbeF10ProbeG002468101214161820Rank
Fig.4.CMSplotsofProbesA-GtestedagainstGallery
100Baseline − rank 1HMM − rank 190Baseline − rank 5HMM − rank 58070)%( 60etar noit50acifitned40I3020100ABCDEFGProbesFig.5.Comparisonofdetectionratesatranks1and5
grassandconcretesurfaces,AandBdenotedifferentshoetypes,andRandLdenotedifferentcameraviews).Weobservethatthedistancemeasurethatworksbestandismostsimpletoimplementistheinnerproductdistance.Theperformancecomparisonwiththebaseline[11]isillustratedinFig.5.
5.CONCLUSION
Inthispaper,wehaveproposedageneralHMM-basedframeworktorepresentandrecognizehumangait.TheframeworkprovidesalgorithmstotraintheHMMparamtersandtoidentifyprobese-quences.Theframeworkhasthepotentialtoworkwithsuitablycomplexfeaturevectorsanddistancemeasuresthatarelesssus-ceptibletoviewinganglesorotherfactors,thoughwehaveusedsequenceswithaconstantviewingangle.Theperiodicnatureofgaitwasexploitedinalinearfilteringnetworktoobtaingoodini-tialvaluesfortheexemplars.Wehaveanalyseddifferentdistancemetricsandfindthattheinnerproductdistanceworksbest.The
ProbePI(atrank1)PIPEuclidSADIPI(atrank5)EuclidSADA(GAL)[66]99%99%98%100%100%100%B(GBR)[37]89%89%89%92%92%92%C(GBL)[37]78%78%75%92%92%92%D(CAR)[62]36%29%23%62%60%59%E(CBR)[39]29%28%21%54%54%59%F(CAL)[62]24%19%16%47%46%44%G(CBL)[38]18%14%15%48%48%45%
Table1.Performanceacrossdistancemetrics.Thenumbersin
squarebracketsdenotethenumberofindividualsinthatset.resultsobtainedaresignificantlybetterthanthebaselinewiththeadditionaladvantageofcompactrepresentationascomparedtothebaseline.Infutureworkwewillstudytheeffectofthebackgroundsubtractionandotherfactorssuchasfootwearinordertoobtainamorerobustandcompactfeaturevector.
6.REFERENCES
[1]L.R.Rabiner,“Atutorialonhiddenmarkovmodelsandse-lectedapplicationsinspeechrecognition,”ProceedingsoftheIEEE,vol.77,no.2,pp.257–285,February1989.
[2]A.F.BobickandJ.W.Davis,“Therecognitionofhuman
movementusingtemporaltemplates,”IEEETrans.onPat-ternAnal.andMachineIntell.,vol.23,pp.257–267,2001.[3]P.S.Huang,C.J.Harris,andM.S.Nixon,“Recognizinghu-mansbygaitviaparametriccanonicalspace,”ArtificialIn-telligenceinEngineering,vol.13,no.4,pp.359–366,1999.[4]C.Bregler,“Learningandrecognisinghumandynamicsin
videosequences,”Proc.oftheIEEEConf.onComp.VisionandPatt.Recog.,pp.568–574,1997.
[5]T.Starner,J.Weaver,andA.Pentland,“Real-timeamerican
signlanguagerecognitionfromvideousinghmms,”IEEETrans.onPatternAnal.andMachineIntell.,vol.12,no.8,pp.1371–1375,1998.
[6]J.Yamato,J.Ohya,andL.Ishii,“Recognizinghumanac-tionintime-sequentialimagesusinghiddenmarkovmodel,”Proc.oftheIEEEConf.onComputerVisionandPatternRecognition,pp.624–630,1995.
[7]B.FreyandN.Jojic,“Learninggraphicalmodelsofimages,
videosandtheirspatialtransformations,”Proc.oftheConf.onUncertaintyinArtificialIntelligence,2000.
[8]K.ToyamaandA.Blake,“Probabilistictrackinginametric
space,”Proc.oftheInt.Conf.onComputerVision,2001.[9]A.Kale,N.Cuntoor,andR.Chellappa,“Aframeworkfor
activity-specifichumanrecognition,”Proc.oftheInt.Conf.onAcoustics,SpeechandSignalProcessing,May2002.[10]P.J.Phillips,S.Sarkar,I.Robledo,P.Grother,and
K.Bowyer,“Thegaitidentificationchallengeproblem:Datasetsandbaselinealgorithm,”Proc.oftheInt.Conf.onPat-ternRecognition,2002.
[11]P.J.Phillips,S.Sarkar,I.Robledo,P.Grother,and
K.Bowyer,“Baselineresultsforthechallengeproblemofhumanidusinggaitanalysis,”Proc.ofthe5thIEEEInt.Conf.onAutomaticFaceandGestureRecognition,2002.
因篇幅问题不能全部显示，请点此查看更多更全内容