212IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.31,NO.2,FEBRUARY2009
high-dimensionaltestimageintolowerdimensionalfeaturespaces:examplesincludeEigenfaces[23],Fisherfaces[24],Laplacianfaces[25],andahostofvariants[26],[27].Withsomanyproposedfeaturesandsolittleconsensusaboutwhicharebetterorworse,practitionerslackguidelinestodecidewhichfeaturestouse.However,withinourproposedframework,thetheoryofcompressedsensingimpliesthattheprecisechoiceoffeaturespaceisnolongercritical:Evenrandomfeaturescontainenoughinformationtorecoverthesparserepresentationandhencecorrectlyclassifyanytestimage.Whatiscriticalisthatthedimensionofthefeaturespaceissufficientlylargeandthatthesparserepresentationiscorrectlycomputed.
Robustnesstoocclusion.Occlusionposesasignificantobstacletorobustreal-worldfacerecognition[16],[28],[29].Thisdifficultyismainlyduetotheunpredictablenatureoftheerrorincurredbyocclusion:itmayaffectanypartoftheimageandmaybearbitrarilylargeinmagnitude.Nevertheless,thiserrortypicallycorruptsonlyafractionoftheimagepixelsandisthereforesparseinthestandardbasisgivenbyindividualpixels.Whentheerrorhassuchasparserepresentation,itcanbehandleduniformlywithinourframework:thebasisinwhichtheerrorissparsecanbetreatedasaspecialclassoftrainingsamples.Thesubsequentsparserepresentationofanoccludedtestimagewithrespecttothisexpandeddictionary(trainingimagespluserrorbasis)naturallyseparatesthecomponentofthetestimagearisingduetoocclusionfromthecomponentarisingfromtheidentityofthetestsubject(seeFig.1foranexample).Inthiscontext,http://www.77cn.com.cnanizationofthispaper.InSection2,weintroduceabasicgeneralframeworkforclassificationusingsparserepresen-tation,applicabletoawidevarietyofproblemsinimage-basedobjectrecognition.Wewilldiscusswhythesparserepresentationcanbecomputedby‘1-minimizationandhowitcanbeusedforclassifyingandvalidatinganygiventestsample.Section3showshowtoapplythisgeneralclassificationframeworktostudytwoimportantissuesinimage-basedfacerecognition:featureextractionandrobust-nesstoocclusion.InSection4,weverifytheproposedmethodwithextensiveexperimentsonpopularfacedatasetsandcomparisonswithmanyotherstate-of-the-artfacerecognitiontechniques.Furtherconnectionsbetweenourmethod,NN,andNSarediscussedinthesupplementaryappendix,whichcanbefoundontheComputerSocietyDigitalLibraryathttp://www.77cn.com.cn/10.1109/TPAMI.2008.79.
Whiletheproposedmethodisofbroadinteresttoobjectrecognitioningeneral,thestudiesandexperimentalresultsinthispaperareconfinedtohumanfrontalfacerecognition.Wewilldealwithilluminationandexpressions,butwedonotexplicitlyaccountforobjectposenorrelyonany3Dmodeloftheface.Theproposedalgorithmisrobusttosmallvariationsinposeanddisplacement,forexample,duetoregistrationerrors.However,wedoassumethatdetec-tion,cropping,andnormalizationofthefacehavebeenperformedpriortoapplyingouralgorithm.
2
CLASSIFICATIONBASEDREPRESENTATION
ON
SPARSE
Abasicprobleminobjectrecognitionistouselabeledtrainingsamplesfromkdistinctobjectclassestocorrectlydeterminetheclasstowhichanewtestsamplebelongs.Wearrangethegivennitrainingsamplesfromtheithclassas
:
columnsofamatrixAi¼½vi;1;vi;2;...;vi;ni 2IRmÂni.Inthecontextoffacerecognition,wewillidentifyawÂhgray-scaleimagewiththevectorv2IRmðm¼whÞgivenbystackingitscolumns;thecolumnsofAiarethenthetrainingfaceimagesoftheithsubject.
TestSampleasaSparseLinearCombinationofTrainingSamples
Animmensevarietyofstatistical,generative,ordiscrimi-nativemodelshavebeenproposedforexploitingthestructureoftheAiforrecognition.Oneparticularlysimpleandeffectiveapproachmodelsthesamplesfromasingleclassaslyingonalinearsubspace.Subspacemodelsareflexibleenoughtocapturemuchofthevariationinrealdatasetsandareespeciallywellmotivatedinthecontextoffacerecognition,whereithasbeenobservedthattheimagesoffacesundervaryinglightingandexpressionlieonaspeciallow-dimensionalsubspace[24],[30],oftencalledafacesubspace.Althoughtheproposedframeworkandalgorithmcanalsoapplytomultimodalornonlineardistributions(seethesupplementaryappendixformoredetail,whichcanbefoundontheComputerSocietyDigitalLibraryathttp://www.77cn.com.cn/10.1109/TPAMI.2008.79),foreaseofpresentation,weshallfirstassumethatthetrainingsamplesfromasingleclassdolieonasubspace.Thisistheonlypriorknowledgeaboutthetrainingsampleswewillbeusinginoursolution.4
Givensufficienttrainingsamplesoftheithobjectclass,Ai¼½vi;1;vi;2;...;vi;ni 2IRmÂni,anynew(test)sampley2IRmfromthesameclasswillapproximatelylieinthelinearspanofthetrainingsamples5associatedwithobjecti:
y¼ i;1vi;1þ i;2vi;2þÁÁÁþ i;nivi;ni;
ð1Þ
2.1
forsomescalars, i;j2IR,j¼1;2;...;ni.
Sincethemembershipiofthetestsampleisinitiallyunknown,wedefineanewmatrixAfortheentiretrainingsetastheconcatenationofthentrainingsamplesofallkobjectclasses:
:
ð2ÞA¼½A1;A2;...;Ak ¼½v1;1;v1;2;...;vk;nk :Then,thelinearrepresentationofycanberewrittenin
termsofalltrainingsamplesas
y¼Axx0
2IRm;
ð3Þ
wherex0¼½0;ÁÁÁ;0; i;1; i;2;...; i;ni;0;...;0 T2IRnisa
coefficientvectorwhoseentriesarezeroexceptthoseassociatedwiththeithclass.
4.Infacerecognition,weactuallydonotneedtoknowwhetherthelinearstructureisduetovaryingilluminationorexpression,sincewedonotrelyondomain-specificknowledgesuchasanilluminationmodel[31]toeliminatethevariabilityinthetrainingandtestingimages.
5.Onemayreferto[32]forhowtochoosethetrainingimagestoensurethispropertyforfacerecognition.Here,weassumethatsuchatrainingsetisgiven.