218
m
IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.31,NO.2,FEBRUARY2009
wheree02IRisavectoroferrors—afraction, ,ofitsentriesarenonzero.Thenonzeroentriesofe0modelwhichpixelsinyarecorruptedoroccluded.Thelocationsofcorruptioncandifferfordifferenttestimagesandarenotknowntothecomputer.TheerrorsmayhavearbitrarymagnitudeandthereforecannotbeignoredortreatedwithtechniquesdesignedforsmallnoisesuchastheonegiveninSection2.2.2.
Afundamentalprincipleofcodingtheory[52]isthatredundancyinthemeasurementisessentialtodetectingandcorrectinggrosserrors.Redundancyarisesinobjectrecogni-tionbecausethenumberofimagepixelsistypicallyfargreaterthanthenumberofsubjectsthathavegeneratedtheimages.Inthiscase,evenifafractionofthepixelsarecompletelycorruptedbyocclusion,recognitionmaystillbepossiblebasedontheremainingpixels.Ontheotherhand,featureextractionschemesdiscussedintheprevioussectionwoulddiscardusefulinformationthatcouldhelpcompen-satefortheocclusion.Inthissense,norepresentationismoreredundant,robust,orinformativethantheoriginalimages.Thus,whendealingwithocclusionandcorruption,weshouldalwaysworkwiththehighestpossibleresolution,performingdownsamplingorfeatureextractiononlyiftheresolutionoftheoriginalimagesistoohightoprocess.
Ofcourse,redundancywouldbeofnousewithoutefficientcomputationaltoolsforexploitingtheinformationencodedintheredundantdata.Thedifficultyindirectlyharnessingtheredundancyincorruptedrawimageshasledresearcherstoinsteadfocusonspatiallocalityasaguidingprincipleforrobustrecognition.Localfeaturescomputedfromonlyasmallfractionoftheimagepixelsareclearlylesslikelytobecorruptedbyocclusionthanholisticfeatures.Infacerecognition,methodssuchasICA[53]andLNMF[54]exploitthisobservationbyadaptivelychoosingfilterbasesthatarelocallyconcentrated.LocalBinaryPatterns[55]andGaborwavelets[56]exhibitsimilarproperties,sincetheyarealsocomputedfromlocalimageregions.Arelatedapproachpartitionstheimageintofixedregionsandcomputesfeaturesforeachregion[16],[57].Notice,though,thatprojectingontolocallyconcentratedbasestransformsthedomainoftheocclusionproblem,ratherthaneliminatingtheocclusion.Errorsontheoriginalpixelsbecomeerrorsinthetransformeddomainandmayevenbecomelesslocal.Theroleoffeatureextractioninachievingspatiallocalityisthereforequestionable,sincenobasesorfeaturesaremorespatiallylocalizedthantheoriginalimagepixelsthemselves.Infact,themostpopularapproachtorobustifyingfeature-basedmethodsisbasedonrandomlysamplingindividualpixels[28],sometimesinconjunctionwithstatisticaltechniquessuchasmultivariatetrimming[29].
Now,letusshowhowtheproposedsparserepresen-tationclassificationframeworkcanbeextendedtodealwithocclusion.Letusassumethatthecorruptedpixelsarearelativelysmallportionoftheimage.Theerrorvectore0,likethevectorx0,thenhassparse14nonzero
x0,wecanrewrite(19)asentries.Sincey0¼Ax
14.Here,“sparse”doesnotmean“veryfew.”Infact,asourexperiments
willdemonstrate,theportionofcorruptedentriescanberathersignificant.Dependingonthetypeofcorruption,ourmethodcanhandleupto ¼40percentor ¼70percentcorruptedpixels.
x:
y¼½A;I 0¼Bw0:
e0
ð20Þ
Here,B¼½A;I 2IRmÂðnþmÞ,sothesystemy¼Bwwisalwaysunderdeterminedanddoesnothaveauniquesolutionforw.However,fromtheabovediscussionaboutthesparsityofx0ande0,thecorrectgeneratingw0¼½x0;e0 hasatmostniþ mnonzeros.Wemightthereforehopetorecoverw0asthesparsestsolutiontothesystemy¼Bww.Infact,ifthematrixBisingeneralposition,thenaslongas
~forsomew~withlessthanm=2nonzeros,w~isthey¼Bw
uniquesparsestsolution.Thus,iftheocclusionecoversless
nthanmÀpixels,%50percentoftheimage,thesparsest~toy¼Bwsolutionwwisthetruegenerator,w0¼½x0;e0 .Moregenerally,onecanassumethatthecorruptingerrore0hasasparserepresentationwithrespecttosomebasisAe2IRmÂne.Thatis,e0¼Aeu0forsomesparsevectoru02IRm.Here,wehavechosenthespecialcaseAe¼I2IRmÂmase0isassumedtobesparsewithrespecttothenaturalpixelcoordinates.Iftheerrore0isinsteadmoresparsewithrespecttoanotherbasis,e.g.,FourierorHaar,wecansimplyredefinethematrixBbyappendingAe(insteadoftheidentityI)toAandinsteadseekthesparsestsolutionw0totheequation:
y¼BwwwithB¼½A;Ae
2IRmÂðnþneÞ:
ð21Þ
Inthisway,thesameformulationcanhandlemoregeneral
classesof(sparse)corruption.
Asbefore,weattempttorecoverthesparsestsolutionw0fromsolvingthefollowingextended‘1-minimizationproblem:ð‘1eÞ:
^1¼argminkwk1w
subjectto
Bww¼y:
ð22Þ
Thatis,inAlgorithm1,wenowreplacetheimagematrixAwiththeextendedmatrixB¼½A;I andxwithw¼½x;e .Clearly,whetherthesparsesolutionw0canberecoveredfromtheabove‘1-minimizationdependsontheneighborli-nessofthenewpolytopeP¼BðP1Þ¼½A;I ðP1Þ.ThispolytopecontainsverticesfromboththetrainingimagesAandtheidentitymatrixI,asillustratedinFig.7.Theboundsgivenin(8)implythatifyisanimageofsubjecti,the‘1-minimization(22)cannotguaranteetocorrectlyrecoverw0¼½x0;e0 if
niþjsupportðe0Þj>d=3:
Generally,d)ni,so,(8)impliesthatthelargestfractionofocclusionunderwhichwecanhopetostillachieveperfectreconstructionis33percent.Thisboundiscorroboratedbyourexperimentalresults,seeFig.12.
Toknowexactlyhowmuchocclusioncanbetolerated,weneedmoreaccurateinformationabouttheneighborli-nessofthepolytopePthanalooseupperboundgivenby(8).Forinstance,wewouldliketoknowforagivensetoftrainingimages,whatisthelargestamountof(worstpossible)occlusionitcanhandle.Whilethebestknownalgorithmsforexactlycomputingtheneighborlinessofapolytopearecombinatorialinnature,tighterupperboundscanbeobtainedbyrestrictingthesearchforintersectionsbetweenthenullspaceofBandthe‘1-balltoarandomsubsetofthet-facesofthe‘1-ball(see[37]fordetails).We