210IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.31,NO.2,FEBRUARY2009
RobustFaceRecognitionviaSparseRepresentation
JohnWright,StudentMember,IEEE,AllenY.Yang,Member,IEEE,
ArvindGanesh,StudentMember,IEEE,S.ShankarSastry,Fellow,IEEE,and
YiMa,SeniorMember,IEEE
Abstract—Weconsidertheproblemofautomaticallyrecognizinghumanfacesfromfrontalviewswithvaryingexpressionand
illumination,aswellasocclusionanddisguise.Wecasttherecognitionproblemasoneofclassifyingamongmultiplelinearregressionmodelsandarguethatnewtheoryfromsparsesignalrepresentationoffersthekeytoaddressingthisproblem.Basedonasparserepresentationcomputedby‘1-minimization,weproposeageneralclassificationalgorithmfor(image-based)objectrecognition.Thisnewframeworkprovidesnewinsightsintotwocrucialissuesinfacerecognition:featureextractionandrobustnesstoocclusion.Forfeatureextraction,weshowthatifsparsityintherecognitionproblemisproperlyharnessed,thechoiceoffeaturesisnolongercritical.Whatiscritical,however,iswhetherthenumberoffeaturesissufficientlylargeandwhetherthesparserepresentationiscorrectlycomputed.UnconventionalfeaturessuchasdownsampledimagesandrandomprojectionsperformjustaswellasconventionalfeaturessuchasEigenfacesandLaplacianfaces,aslongasthedimensionofthefeaturespacesurpassescertainthreshold,predictedbythetheoryofsparserepresentation.Thisframeworkcanhandleerrorsduetoocclusionandcorruptionuniformlybyexploitingthefactthattheseerrorsareoftensparsewithrespecttothestandard(pixel)basis.Thetheoryofsparserepresentationhelpspredicthowmuchocclusiontherecognitionalgorithmcanhandleandhowtochoosethetrainingimagestomaximizerobustnesstoocclusion.Weconductextensiveexperimentsonpubliclyavailabledatabasestoverifytheefficacyoftheproposedalgorithmandcorroboratetheaboveclaims.
IndexTerms—Facerecognition,featureextraction,occlusionandcorruption,sparserepresentation,compressedsensing,‘1-minimization,validationandoutlierrejection.
Ç
1
INTRODUCTION
ARSIMONY
P
hasarichhistoryasaguidingprinciplefor
inference.Oneofitsmostcelebratedinstantiations,theprincipleofminimumdescriptionlengthinmodelselection[1],[2],stipulatesthatwithinahierarchyofmodelclasses,themodelthatyieldsthemostcompactrepresentationshouldbepreferredfordecision-makingtaskssuchasclassification.Arelated,butsimpler,measureofparsimonyinhigh-dimensionaldataprocessingseeksmodelsthatdependononlyafewoftheobservations,selectingasmallsubsetoffeaturesforclassificationorvisualization(e.g.,SparsePCA[3],[4]amongothers).Suchsparsefeatureselectionmethodsare,inasense,dualtothesupportvectormachine(SVM)approachin[5]and[6],whichinsteadselectsasmallsubsetofrelevanttrainingexamplestocharacterizethedecisionboundarybetweenclasses.Whiletheseworkscompriseonlyasmallfractionoftheliteratureonparsimonyforinference,theydoservetoillustrateacommontheme:allofthemuseparsimonyasaprinciplefor
.J.Wright,A.Ganesh,andY.MaarewiththeCoordinatedScienceLaboratory,UniversityofIllnoisatUrbana-Champaign,1308WestMainStreet,Urbana,IL61801.E-mail:{jnwright,abalasu2,yima}@uiuc.edu..A.YangandS.SatryarewiththeDepartmentofElectricalEngineeringandComputerScience,UniversityofCalifornia,Berkeley,Berkeley,CA94720.e-mail:{yang,sastry}@eecs.berkeley.edu.Manuscriptreceived13Aug.2007;revised18Jan.2008;accepted20Mar.2008;publishedonline26Mar.2008.
RecommendedforacceptancebyM.-H.Yang.
Forinformationonobtainingreprintsofthisarticle,pleasesende-mailto:tpami@http://www.77cn.com.cn,andreferenceIEEECSLogNumberTPAMI-2007-08-0500.
DigitalObjectIdentifierno.10.1109/TPAMI.2008.79.
0162-8828/09/$25.00ß2009IEEE
choosingalimitedsubsetoffeaturesormodelsfromthetrainingdata,ratherthandirectlyusingthedataforrepresentingorclassifyinganinput(test)signal.
Theroleofparsimonyinhumanperceptionhasalsobeenstronglysupportedbystudiesofhumanvision.Investigatorshaverecentlyrevealedthatinbothlow-levelandmidlevelhumanvision[7],[8],manyneuronsinthevisualpathwayareselectiveforavarietyofspecificstimuli,suchascolor,texture,orientation,scale,andevenview-tunedobjectimages.Consideringtheseneuronstoformanovercompletedictionaryofbasesignalelementsateachvisualstage,thefiringoftheneuronswithrespecttoagiveninputimageistypicallyhighlysparse.
Inthestatisticalsignalprocessingcommunity,thealgorithmicproblemofcomputingsparselinearrepresenta-tionswithrespecttoanovercompletedictionaryofbaseelementsorsignalatomshasseenarecentsurgeofinterest[9],[10],[11],[12].1Muchofthisexcitementcentersaroundthediscoverythatwhenevertheoptimalrepresentationissufficientlysparse,itcanbeefficientlycomputedbyconvexoptimization[9],eventhoughthisproblemcanbeextre-melydifficultinthegeneralcase[13].Theresultingoptimizationproblem,similartotheLassoinstatistics
1.Intheliterature,theterms“sparse”and“representation”havebeenusedtorefertoanumberofsimilarconcepts.Throughoutthispaper,wewillusetheterm“sparserepresentation”toreferspecificallytoanexpressionoftheinputsignalasalinearcombinationofbaseelementsinwhichmanyofthecoefficientsarezero.Inmostcasesconsidered,thepercentageofnonzerocoefficientswillvarybetweenzeroand%30percent.However,incharacterizingthebreakdownpointofouralgorithms,wewillencountercaseswithupto70percentnonzeros.
PublishedbytheIEEEComputerSociety