WRIGHTET
AL.:ROBUSTFACERECOGNITIONVIASPARSEREPRESENTATION215
Fig.4.Nonsparsityofthe‘2-minimizer.(a)Coefficientsfrom‘2-minimizationusingthesametestimageasFig.3.Therecoveredsolutionisnotsparseand,hence,lessinformativeforrecognition(largecoefficientsdonotcorrespondtotrainingimagesofthistestsubject).(b)Theresidualsof
^Þofthecoefficientsobtainedby‘2-minimization.Theratiobetweenthetwosmallestthetestimagefromsubject1withrespecttotheprojection iðx
residualsisabout1:1.3.Thesmallestresidualisnotassociatedwithsubject1.
Example1(‘1-minimizationversus‘2-minimization).ToillustratehowAlgorithm1works,werandomlyselecthalfofthe2,414imagesintheExtendedYaleBdatabaseasthetrainingsetandtherestfortesting.Inthisexample,wesubsampletheimagesfromtheoriginal192Â168tosize12Â10.Thepixelvaluesofthedownsampledimageareusedas120-Dfeature-s—stackedascolumnsofthematrixAinthealgorithm.Hence,matrixAhassize120Â1,207,andthesystemy¼Axxisunderdetermined.Fig.3aillustratesthesparsecoefficientsrecoveredbyAlgorithm1foratestimagefromthefirstsubject.Thefigurealsoshowsthefeaturesandtheoriginalimagesthatcorrespondtothetwolargestcoefficients.Thetwolargestcoefficientsarebothassociatedwithtrainingsamplesfromsubject1.Fig.3bshowstheresidualswithrespecttothe38projected
^1Þ,i¼1;2;...;38.With12Â10down-coefficients iðx
sampledimagesasfeatures,Algorithm1achievesanoverallrecognitionrateof92.1percentacrosstheExtendedYaleBdatabase.(SeeSection4fordetailsandperformancewithotherfeaturessuchasEigenfacesandFisherfaces,aswellascomparisonwithothermethods.)Whereasthemoreconventionalminimum
x‘2-normsolutiontotheunderdeterminedsystemy¼Ax
1
istypicallyquitedense,minimizingthe‘-normfavorssparsesolutionsandprovablyrecoversthesparsestsolutionwhenthissolutionissufficientlysparse.Toillustratethiscontrast,Fig.4ashowsthecoefficientsofthesametestimagegivenbytheconventional‘2-minimization(4),andFig.4bshowsthecorrespondingresidualswithrespecttothe38subjects.Thecoefficientsaremuchlesssparsethanthosegivenby‘1-minimization(inFig.3),andthedominantcoefficientsarenotassociatedwithsubject1.Asaresult,thesmallestresidualinFig.4doesnotcorrespondtothecorrectsubject(subject1).
testsamplebasedonhowsmallthesmallestresidualis.However,eachresidualriðyÞiscomputedwithoutanyknowledgeofimagesofotherobjectclassesinthetrainingdatasetandonlymeasuressimilaritybetweenthetestsampleandeachindividualclass.
^1Inthesparserepresentationparadigm,thecoefficientsx
arecomputedglobally,intermsofimagesofallclasses.Inasense,itcanharnessthejointdistributionofallclassesfor
^arebettervalidation.Wecontendthatthecoefficientsx
statisticsforvalidationthantheresiduals.Letusfirstseethisthroughanexample.
Example2(concentrationofsparsecoefficients).WerandomlyselectanirrelevantimagefromGoogleanddownsampleitto12Â10.WethencomputethesparserepresentationoftheimageagainstthesameExtendedYaleBtrainingdata,asinExample1.Fig.5aplotstheobtainedcoefficients,http://www.77cn.com.cnparedtothecoefficientsofavalidtest
^herearenotimageinFig.3,noticethatthecoefficientsx
concentratedonanyonesubjectandinsteadspreadwidelyacrosstheentiretrainingset.Thus,thedistributionofthe
^containsimportantinfor-estimatedsparsecoefficientsx
mationaboutthevalidityofthetestimage:Avalidtestimageshouldhaveasparserepresentationwhosenonzeroentriesconcentratemostlyononesubject,whereasaninvalidimagehassparsecoefficientsspreadwidelyamongmultiplesubjects.Toquantifythisobservation,wedefinethefollowingmeasureofhowconcentratedthecoefficientsareonasingleclassinthedataset:
Definition1(sparsityconcentrationindex(SCI)).TheSCIofacoefficientvectorx2IRnisdefinedas
:kÁmaxik iðxÞk1=kxk1À1
SCIðxÞ¼
kÀ1
2½0;1 :
ð14Þ
2.4ValidationBasedonSparseRepresentationBeforeclassifyingagiventestsample,wemustfirstdecideifitisavalidsamplefromoneoftheclassesinthedataset.Theabilitytodetectandthenrejectinvalidtestsamples,or“outliers,”iscrucialforrecognitionsystemstoworkinreal-worldsituations.Afacerecognitionsystem,forexample,couldbegivenafaceimageofasubjectthatisnotinthedatabaseoranimagethatisnotafaceatall.
SystemsbasedonconventionalclassifierssuchasNNorNS,oftenusetheresidualsriðyÞforvalidation,inadditiontoidentification.Thatis,thealgorithmacceptsorrejectsa
^foundbyAlgorithm1,ifSCIðx^Þ¼1,theForasolutionx
testimageisrepresentedusingonlyimagesfromasingle
^Þ¼0,thesparsecoefficientsarespreadobject,andifSCIðx
evenlyoverallclasses.9Wechooseathreshold 2ð0;1Þandacceptatestimageasvalidif
9.DirectlychoosingxtominimizetheSCImightproducemoreconcentratedcoefficients;however,theSCIishighlynonconvexanddifficulttooptimize.Forvalidtestimages,minimizingthe‘1-normalreadyproducesrepresentationsthatarewell-concentratedonthecorrectsubjectclass.