216IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.31,NO.2,FEBRUARY
2009
Fig.5.Exampleofaninvalidtestimage.(a)SparsecoefficientsfortheinvalidtestimagewithrespecttothesametrainingdatasetfromExample1.Thetestimageisarandomlyselectedirrelevantimage.(b)Theresidualsoftheinvalidtestimagewithrespecttotheprojection iðx^Þof
1
thesparserepresentationcomputedby‘-minimization.Theratioofthetwosmallestresidualsisabout1:1.2.
^Þ! ;SCIðxð15Þ
andotherwiserejectasinvalid.Instep5ofAlgorithm1,one
maychoosetooutputtheidentityofyonlyifitpassesthiscriterion.
UnlikeNNorNS,thisnewruleavoidstheuseoftheresidualsriðyÞforvalidation.NoticethatinFig.5,evenforanonfaceimage,withalargetrainingset,thesmallestresidualoftheinvalidtestimageisnotsolarge.Ratherthanrelyingonasinglestatisticforbothvalidationandidentification,ourapproachseparatestheinformationrequiredforthesetasks:theresidualsforidentificationandthesparsecoefficientsforvalidation.10Inasense,theresidualmeasureshowwelltherepresentationapprox-imatesthetestimage;andthesparsityconcentrationindexmeasureshowgoodtherepresentationitselfis,intermsoflocalization.
Onebenefittothisapproachtovalidationisimprovedperformanceagainstgenericobjectsthataresimilartomultipleobjectclasses.Forexample,infacerecognition,http://www.77cn.com.cningresidualsforvalidationmorelikelyleadstoafalsepositive.However,agenericfaceisunlikelytopassthenewvalidationruleasagoodrepresentationofittypicallyrequirescontribu-tionfromimagesofmultiplesubjectsinthedataset.Thus,thenewrulecanbetterjudgewhetherthetestimageisagenericfaceorthefaceofoneparticularsubjectinthedataset.InSection4.7,wewilldemonstratethatthenewvalidationruleoutperformstheNNandNSmethods,withasmuchas10-20percentimprovementinverificationrateforagivenfalseacceptrate(seeFig.14inSection4orFig.18inthesupplementaryappendix,whichcanbefoundontheComputerSocietyDigitalLibraryathttp://www.77cn.com.cn/10.1109/TPAMI.2008.79).
3.1TheRoleofFeatureExtraction
Inthecomputervisionliterature,numerousfeatureextrac-tionschemeshavebeeninvestigatedforfindingprojectionsthatbetterseparatetheclassesinlowerdimensionalspaces,whichareoftenreferredtoasfeaturespaces.OneclassofmethodsextractsholisticfacefeaturessuchasEigen-faces[23],Fisherfaces[24],andLaplacianfaces[25].Anotherclassofmethodstriestoextractmeaningfulpartialfacialfeatures(e.g.,patchesaroundeyesornose)[21],[41](seeFig.6forsomeexamples).Traditionally,whenfeatureextractionisusedinconjunctionwithsimpleclassifierssuchasNNandNS,thechoiceoffeaturetransformationisconsideredcriticaltothesuccessofthealgorithm.Thishasledtothedevelopmentofawidevarietyofincreasinglycomplexfeatureextractionmethods,includingnonlinearandkernelfeatures[42],[43].Inthissection,wereexaminetheroleoffeatureextractionwithinthenewsparserepresentationframeworkforfacerecognition.
Onebenefitoffeatureextraction,whichcarriesovertotheproposedsparserepresentationframework,isreduceddatadimensionandcomputationalcost.Forrawfaceimages,thecorrespondinglinearsystemy¼Axxisverylarge.Forinstance,ifthefaceimagesaregivenatthetypicalresolution,640Â480pixels,thedimensionmisintheorderof105.AlthoughAlgorithm1reliesonscalablemethodssuchaslinearprogramming,directlyapplyingittosuchhigh-resolutionimagesisstillbeyondthecapabilityofregularcomputers.
Sincemostfeaturetransformationsinvolveonlylinearoperations(orapproximatelyso),theprojectionfromtheimagespacetothefeaturespacecanberepresentedasamatrixR2IRdÂmwithd(m.ApplyingRtobothsidesof(3)yields
:~¼Ryyy¼RAxx0
2IRd:
ð16Þ
3
TWOFUNDAMENTALISSUES
RECOGNITION
IN
FACE
Inthissection,westudytheimplicationsoftheabovegeneralclassificationframeworkfortwocriticalissuesinfacerecognition:1)thechoiceoffeaturetransformation,and2)robustnesstocorruption,occlusion,anddisguise.
10.Wefindempiricallythatthisseparationworkswellenoughinourexperimentswithfaceimages.However,itispossiblethatbettervalidationandidentificationrulescanbecontrivedfromusingtheresidualandthesparsitytogether.
Inpractice,thedimensiondofthefeaturespaceistypicallychosentobemuchsmallerthann.Inthiscase,thesystemof
~¼RAxequationsyx2IRdisunderdeterminedintheun-knownx2IRn.Nevertheless,asthedesiredsolutionx0is
sparse,wecanhopetorecoveritbysolvingthefollowingreduced‘1-minimizationproblem:ð‘1rÞ:
^1¼argminkxk1x
subjectto
~k2 ";kRAxxÀy
ð17Þ
foragivenerrortolerance">0.Thus,inAlgorithm1,thematrixAoftrainingimagesisnowreplacedbythematrix