A hidden markov model based framework for recognition of humans from gait sequences

FROMGAITSEQUENCES

AravindSundaresan,AmitRoyChowdhury,RamaChellappa

CentreforAutomationResearch,andDepartmentofElectricalandComputerEngineering

UniversityofMaryland,CollegePark,MD20742

ABSTRACT

InthispaperweproposeagenericframeworkbasedonHid-denMarkovModels(HMMs)forrecognitionofindividualsfromtheirgait.TheHMMframeworkissuitable,becausethegaitofanindividualcanbevisualizedashisadoptingposturesfromaset,inasequencewhichhasanunderlyingstructuredprobabilisticna-ture.TheposturesthattheindividualadoptscanberegardedasthestatesoftheHMMandaretypicaltothatindividualandprovideameansofdiscrimination.Theframeworkassumesthat,duringawalkcycle,theindividualtransitionsamongdiscreteposturesorstates.Anadaptivefilterisusedtoautomaticallydetectthecycleboundaries.Ourmethodisnotdependentontheparticularfeaturevectorusedtorepresentthegaitinformationcontainedinthepos-tures.ThestatisticalnatureoftheHMMlendsrobustnesstothemodel.Inthispaperweusethebinarizedbackground-subtractedimageasthefeaturevectorandusedifferentdistancemetrics,suchasthosebasedontheandnormsofthevectordifference,andthenormalizedinnerproductofthevectors,tomeasurethesimilaritybetweenfeaturevectors.Theresultsweobtainarebet-terthanthebaselinerecognitionratesreportedbefore.

1.INTRODUCTION

Biometricscanbeapowerfulcueforreliableautomatedpersonidentificationandthereexistseveralestablishedbiometric-basedidentificationtechniquesincludingfingerprintandhandgeometrymethods,speakeridentification,facerecognitionandirisidentifi-cation.However,theapplicabilityofallthesemethodologiesisusuallyrestrictedtocontrolledenvironmentsorrequirecoopera-tionofthesubject.We,therefore,needtoexplorebiometricsigna-tureswhichcanbeobtainednon-invasivelyfromadistance.Gaitisonesuchbiometricwhichiscurrentlybeingexploredforpurposessuchasidentification.Weknowfromexperiencethatpeopleoftenrecognizeothersbysimplyobservingthewaytheywalkimply-ingthatbodyshapeanddynamicsaresufficientlydistinctacrosshumans.

Ithasbeenobservedthatgaitcanbemodeledasatransitionacrossstates,whereeachstateisexemplifiedbyatypicalfeaturevectororexemplar.Inthispaperweproposeageneralframeworkthatemploysexemplar-basedHMMstocharacterizeanindivid-ual’sgaitandthereafterrecognizetheindividualfromhisgait.Theuseoftemporaltemplates,whichcapturemotionofeachpixelintheframe,hasbeenproposedforrecognitionofbothhumanac-tions[1]andhumansfromtheirgait[2].HMMshavealsobeenusedtorecognizehumanactions[3,4,5].Exemplarshavebeenusedinlearningprobabilisticmodelsin[6]andtrackingin[7].

F1F2F3F4F5F6F7

Fig.1.PartofanObservationSequence

Duringthetrainingphase,amodelisbuiltforallthesubjects,indexedbyofiteratively.and,inthegallery.AninitialestimateNoteisformedthatisfromcompletely,anddefinedtheseestimatesbyifisarefixedrefinedbe-forehand.WecaniterativelyestimateWelchalgorithm,keepingandbyusingtheBaum-isdeterminedbythechoicefixed.oftheThedistancealgorithmmetric.tore-estimateDuringtest-ing,givenaGalleryandtheprobese-quenceoflength,

traversingthepath,beingthestateindexattime,weobtain

theIDoftheprobesequenceas

(2)

3.METHODOLOGY

Thefeaturevectorweuseintheexperimentsisthebinarizedver-sionofthebackgroundsubtractedimages.TheimagesarescaledandalignedtothecenteroftheframeasinFigure1whichfeaturespartofasequenceoffeaturevectors.WedescribeinthissectionthemethodsusedtoobtaininitialestimatesoftheHMMparame-ters,thetrainingalgorithmandfinally,identificationresultsusingUSFdatadescribedin[9].

3.1.InitialEstimateofHMMParameters

Inordertoobtainagoodestimateoftheexemplarsandthetransi-tionmatrix,wefirstobtainaninitialestimateofanorderedsetofexemplarsfromthesequenceandthetransitionmatrixandsucces-sivelyrefinetheestimate.Theinitialestimatefortheexemplars,

issuchthattheonlytransitionsallowed

arefromthestatetoeithertheorthe

state.Acorrespondinginitialestimateofthetransitionmatrix,(withobtained.Theinitialprobabilites,andareallsetothertobeequalto)isalso.

Weobservethatthegaitsequenceisquasi-periodicandweusethisfacttoobtaintheinitialestimatesequenceinto“cycles”,whereacycleisdefined.Weasthatcansegmentdividetheofthesequenceboundedbysilhouetteswherethesubjecthasarmsbyhis/hersideandlegsapproximatelyalignedwitheachother.Wecanfurtherdivideeachcycleintotemporallyadjacentclustersofapproximatelyequalsize.Wevisualizetheframesoftheclusterofallcyclestobegeneratedfromthestate.Thuswecangetagoodinitialestimateoflongingtothecluster.Forexample,fromassumethefeaturethatthevectorstrainingbe-sequenceisgivenby.Wecanpartitionthesequenceintosetcycles,withthecyclegivenbyframesinthe,whereandaretheindexofthefirstframeofthecycle,andthelengthof

the

cyclerespectively.Wedefinethefirstclustertocompriseofframeswithindices

.

Weneedtorobustlyestimatethecycleboundariessothatwecanpartitionthesequenceintoclustersandobtaintheinitiales-timatesoftheexemplars.Ifthesumsoftheforegroundpixelsofeachimageareplottedwithrespecttotime,then,asperourdefinitionofacycle,theminimasshouldcorrespondtothecy-cleboundaries.Wedenotethesumoftheforegroundpixelsofthesilhouetteintheframeasmaycontainseveralspuriousminima..HoweverThissignalweiscannoisyexploitandthequasi-periodicityofthesignalandfilterthesignaltoremovethenoisebeforeidentifyingtheminima.Methodssuchasmedianfilteringordifferentialsmoothingofarenotveryrobustastheydonottakeintoaccountthefrequencyofthegait.Amore

robustmethodwouldbetoanalyse

time-frequencydomain,usingband-passfiltersintheorfrequencytheShortorTimetheFourierTransform(STFT).

Thespecificationsoftheband-passfilteraresuchastoallowfrequenciesthataretypicalforafastwalk.Thevideoiscapturedat30framespersecond,andthesamplingfrequency,andcorresponding.Themaximumtoacyclegaitperiodfrequencyofisassumedtobe

mingwindowoflengthisobtainedbysymmetricallyisextendingused.Theextended.AHam-resultant.Thereforesequencetheissequencefilteredusinghasabandpasslengthinbothsequence

directionsfilter(with.by

upperThecut-offfrequencydelay.Thedistancesbetween),theinbothminimasdirectionsofthefilteredtoremovesequencephaseleadustoanestimateofthecycleperiod.Thecyclefrequencyisestimatedastheinverseofthemedianofcycleperiods.Usingthisrevisedestimateofthefrequencyofthegait,,anewfilteriscon-structedwithuppercutofffrequencysequences,STFTtechniquescouldbeusedinsteadofstraightfor-.Forlongwardfilteringinordertoaccountforaslowlyvaryingfrequencyofgait.Figure2illustratestheperformanceofseveralalgorithmsinidentifyingthecycleboundaries.AmanualexaminationofallthesequencesintheGalleryrevealeda100%detectionratewithhardlyanyfalsedetectionofcyclebouldaries.Wealsoobservedfromthetheinitialexemplarsobtainedusingthecycleregistration

resultsfromthefilteringmethodthatthefrequencybasedfilteringmethodismoreaccurateandrobustcomparedtotheothermeth-ods.

3.2.TrainingtheHMMParameters

Theiterativerefiningoftheestimatesisperformedintwosteps.Inthefirststep,aViterbievaluation[11]ofthesequenceisper-formedusingthecurrentvaluesfortheexemplarsandthetran-sitionmatrix.Thusfeaturevectorsareclusteredaccordingtothemostlikelystatetheyoriginatedfrom.Theexemplarsforthestatesarenewlyestimatedfromtheseclusters.Usingthecurrentvaluesoftheexemplars,andthetransitionmatrix,,Viterbide-codingisperformedonthesequencetoobtainthemostprobablepath,whereisthestateattime.Thusthesetofobservationindices,whosecorrespondingobserva-tionisestimatedtohavebeengeneratedfromstateisgivenby

.Wenowhaveasetofframesforeachstate

andwewouldliketoselecttheexemplarssoastomaximisetheprobabilityin(3).Ifweusethedefinitionin(1),(4)follows.

(3)(4)

Theactualmethodforminimisingthedistancein(4)howeverde-pendsonthedistancemetricused.Wehaveexperimentedwiththreedifferentdistancemeasures,namelytheEuclidean(EUCLID)distance,theinnerproduct(IP)distance,andthesumofabsolutedifference(SAD)distancewhicharegivenby(5),(6),and(7)re-spectively.Notethatthoughandare2-dimensionalimages,

foreaseoftheyarerepresentedasvectorsofdimension

notation.isavectorofones.

(5)(6)

(7)

TheequationsforupdatingtheelementoftheexemplarsintheEUCLIDdistance,IPdistanceandtheSADdistancecasesarepre-sentedin(8),(9)and(10)respectively.denotesthenormalizedvectoranddenotesthecardinalityoftheset.

Cumulative Match Scores (Training Set is Gallery)100908070Cumulative Match Scores6050403020100ProbeAProbeBProbeCProbeDProbeEProbeFProbeGIP

A(GAL)[66]B(GBR)[37]C(GBL)[37]D(CAR)[62]E(CBR)[39]F(CAL)[62]G(CBL)[38]

(atrank1)EuclidSAD

100%

92%92%62%54%47%48%

100%92%92%60%54%46%48%

100%92%92%59%59%44%45%

0246810Rank

1214161820Fig.4.CMSplotsofProbesA-GtestedagainstGallery

100908070Identification rate (%)6050403020100Baseline − rank 1HMM − rank 1Baseline − rank 5HMM − rank 5ABCDProbesEFGFig.5.Detectionratesatranks1and5forthebaselineandHMMalgorithms

IPdistancemeasurebetweenfeaturevectorsintheformofCumu-lativeMatchScores(CMS)plots[10]areinFigure4.Table1givesabriefsummaryoftheexperimentsconducted(GandCdenotegrassandconcretesurfaces,AandBdenotedifferentshoetypes,andRandLdenotedifferentcameraviews).Weobservethatthedistancemeasurethatworksbestandismostsimpletoimplementistheinnerproductdistance.Theperformancecomparisonwiththebaseline[10]isillustratedinFigure5.

5.CONCLUSION

Inthispaper,wehaveproposedageneralHMM-basedframeworktorepresentandrecognizehumans.Theframeworkprovidesal-gorithmstotraintheHMMparametersandtoidentifyprobese-quences.Ithasthepotentialtoworkwithsuitablycomplexfeaturevectorsanddistancemeasuresthatarelesssusceptibletoviewinganglesorotherfactors,thoughwehaveusedsequenceswithacon-