WRIGHTETAL.:ROBUSTFACERECOGNITIONVIASPARSEREPRESENTATION211
Fig.1.Overviewofourapproach.Ourmethodrepresentsatestimage(left),whichis(a)potentiallyoccludedor(b)corrupted,asasparselinearcombinationofallthetrainingimages(middle)plussparseerrors(right)duetoocclusionorcorruption.Red(darker)coefficientscorrespondtotrainingimagesofthecorrectindividual.Ouralgorithmdeterminesthetrueidentity(indicatedwitharedboxatsecondrowandthirdcolumn)from700trainingimagesof100individuals(7each)inthestandardARfacedatabase.
[12],[14]penalizesthe‘1-normofthecoefficientsinthelinearcombination,ratherthanthedirectlypenalizingthenumberofnonzerocoefficients(i.e.,the‘0-norm).
Theoriginalgoaloftheseworkswasnotinferenceorclassificationperse,butratherrepresentationandcompres-sionofsignals,potentiallyusinglowersamplingratesthantheShannon-Nyquistbound[15].Algorithmperformancewasthereforemeasuredintermsofsparsityoftherepresentationandfidelitytotheoriginalsignals.Further-more,individualbaseelementsinthedictionarywerenotassumedtohaveanyparticularsemanticmeaning—theyaretypicallychosenfromstandardbases(e.g.,Fourier,Wavelet,Curvelet,andGabor),orevengeneratedfromrandommatrices[11],[15].Nevertheless,thesparsestrepresentationisnaturallydiscriminative:amongallsubsetsofbasevectors,itselectsthesubsetwhichmostcompactlyexpressestheinputsignalandrejectsallotherpossiblebutlesscompactrepresentations.
Inthispaper,weexploitthediscriminativenatureofsparserepresentationtoperformclassification.Insteadofusingthegenericdictionariesdiscussedabove,werepre-sentthetestsampleinanovercompletedictionarywhosebaseelementsarethetrainingsamplesthemselves.Ifsufficienttrainingsamplesareavailablefromeachclass,2itwillbepossibletorepresentthetestsamplesasalinearcombina-tionofjustthosetrainingsamplesfromthesameclass.Thisrepresentationisnaturallysparse,involvingonlyasmallfractionoftheoveralltrainingdatabase.Wearguethatinmanyproblemsofinterest,itisactuallythesparsestlinearrepresentationofthetestsampleintermsofthisdictionaryandcanberecoveredefficientlyvia‘1-minimization.Seekingthesparsestrepresentationthereforeautomaticallydiscriminatesbetweenthevariousclassespresentinthetrainingset.Fig.1illustratesthissimpleideausingfacerecognitionasanexample.Sparserepresentationalsoprovidesasimpleandsurprisinglyeffectivemeansofrejectinginvalidtestsamplesnotarisingfromanyclassinthetrainingdatabase:thesesamples’sparsestrepresenta-tionstendtoinvolvemanydictionaryelements,spanningmultipleclasses.
2.Incontrast,methodssuchasthatin[16]and[17]thatutilizeonlyasingletrainingsampleperclassfaceamoredifficultproblemandgenerallyincorporatemoreexplicitpriorknowledgeaboutthetypes
ofvariationthatcouldoccurinthetestsample.
Ouruseofsparsityforclassificationdifferssignificantlyfromthevariousparsimonyprinciplesdiscussedabove.Insteadofusingsparsitytoidentifyarelevantmodelorrelevantfeaturesthatcanlaterbeusedforclassifyingalltestsamples,itusesthesparserepresentationofeachindividualtestsampledirectlyforclassification,adaptivelyselectingthetrainingsamplesthatgivethemostcompactrepresenta-tion.Theproposedclassifiercanbeconsideredageneral-izationofpopularclassifierssuchasnearestneighbor(NN)[18]andnearestsubspace(NS)[19](i.e.,minimumdistancetothesubspacespannedalltrainingsamplesfromeachobjectclass).NNclassifiesthetestsamplebasedonthebestrepresentationintermsofasingletrainingsample,whereasNSclassifiesbasedonthebestlinearrepresentationintermsofallthetrainingsamplesineachclass.Thenearestfeatureline(NFL)algorithm[20]strikesabalancebetweenthesetwoextremes,classifyingbasedonthebestaffinerepresentationintermsofapairoftrainingsamples.Ourmethodstrikesasimilarbalancebutconsidersallpossiblesupports(withineachclassoracrossmultipleclasses)andadaptivelychoosestheminimalnumberoftrainingsamplesneededtorepresenteachtestsample.3
Wewillmotivateandstudythisnewapproachtoclassificationwithinthecontextofautomaticfacerecogni-tion.Humanfacesarearguablythemostextensivelystudiedobjectinimage-basedrecognition.Thisispartlyduetotheremarkablefacerecognitioncapabilityofthehumanvisualsystem[21]andpartlyduetonumerousimportantapplicationsforfacerecognitiontechnology[22].Inaddition,technicalissuesassociatedwithfacerecognitionarerepresentativeofobjectrecognitionandevendataclassificationingeneral.Conversely,thetheoryofsparserepresentationandcompressedsensingyieldsnewinsightsintotwocrucialissuesinautomaticfacerecognition:theroleoffeatureextractionandthedifficultyduetoocclusion.Theroleoffeatureextraction.Thequestionofwhichlow-dimensionalfeaturesofanobjectimagearethemostrelevantorinformativeforclassificationisacentralissueinfacerecogni-tionandinobjectrecognitioningeneral.Anenormousvolumeofliteraturehasbeendevotedtoinvestigatevariousdata-dependentfeaturetransformationsforprojectingthe
3.TherelationshipbetweenourmethodandNN,NS,andNFLisexploredmorethoroughlyinthesupplementaryappendix,whichcanbefoundontheComputerSocietyDigitalLibraryathttp://www.77cn.com.cn/10.1109/TPAMI.2008.79.