binnedfedora17

SetDistanceFunctionsfor3DObjectRecognitionLusA.
AlexandreInstitutodeTelecomunicacoes,Univ.
BeiraInterior,Covilha,PortugalAbstract.
Oneofthekeystepsin3Dobjectrecognitionisthematch-ingbetweenaninputcloudandacloudinadatabaseofknownobjects.
Thisisusuallydoneusingadistancefunctionbetweensetsofdescrip-tors.
Inthispaperweproposetostudyhowseveraldistancefunctions(somealreadyavailableandothernewproposals)behaveexperimentallyusingalargefreelyavailablehouseholdobjectdatabasecontaining1421pointcloudsfrom48objectsand10categories.
Wepresentexperimentsillustratingtheaccuracyofthedistancesbothforobjectandcategoryrecognitionandndthatsimpledistancesgivecompetitiveresultsbothintermsofaccuracyandspeed.
1IntroductionThereisagrowinginterestintheuseof3Dpointcloudimagesformanytasks,sincetherecentintroductionofcheapsensorsthatproduceRGBplusdepthimages,suchastheMicrosoftKinectortheAsusXtion.
Oneofthemostchallengingtaskstobeachievedwithsuchdataistorecognizeobjectsinascene.
Animportantpartoftheprocessofrecognitionistobeabletocomparetherepresentationsoftheinput(testorprobe)dataagainststored(trainorgallery)data.
Theobjectsareusuallyrepresentedbysetsofdescriptors.
Severaldistancesexistthatareabletoworkwithsetsofdescriptors,notablythePyramidMatchKernel[1],forobjectrecognitionfromimages.
Itisimportanttoobtainaquantitativenotionoftheperformanceofsuchdistancefunctions.
Inthispaperwepresentacomparisonbetween8distancefunctionsfor3Dobjectrecognitionfrompointclouds.
Twotypesofdescriptorsareusedandtherelativedistanceperformanceissimilarinbothcases.
Weshowboththeobjectandcategoryaccuraciesthatcanbeobtainedfromthesedistancesandalsothecomputationalcostintermsofthetimeittakestoprocessthetestsetused.
Fromtheexperimentsweconcludethatgoodperformancecanbeobtainedusingquitesimpledistancefunctions,bothintermsofaccuracyandspeed.
Therestofthepaperisorganizedasfollows:thenextsectionpresentsanoverviewofthe3Dobjectrecognitionpipelineusedinthispaper,thefollow-ingsectionexplainsthedescriptorsused;section4presentsthedistancesthatareevaluated;section5containstheexperimentsandthepaperendswiththeconclusionsinsection6.
WeacknowledgethenancialsupportofprojectPEst-OE/EEI/LA0008/2013.
J.
Ruiz-ShulcloperandG.
SannitidiBaja(Eds.
):CIARP2013,PartI,LNCS8258,pp.
57–64,2013.
cSpringer-VerlagBerlinHeidelberg201358L.
A.
Alexandre2The3DObjectRecognitionPipelineTheinputcloudgoesthroughakeypointextractionalgorithm,theHarris3DkeypointdetectorimplementedinPCL[2].
Thecovariancematrixofthesurfacenormalsonapointneighborhoodisusedtondthepoint'sresponsetothedetector.
Thendescriptorsareobtainedontheextractedkeypointsandtheseformasetthatisusedtorepresenttheinputcloud.
Thissetismatchedagainstsetsalreadypresentintheobjectdatabaseandtheonewithlargestsimilarity(smallestdistance)isconsideredthematchfortheinputcloud.
3DescriptorsInthispaperweusethetwodescriptorsthatproducedthebestresultsinthecomparativeevaluationperformedin[3].
Theybothusecolorinformation.
TherstoneisthePointFeatureHistograms(PFH)[4].
Thisdescriptor'sgoalistogeneralizeboththesurfacenormalsandthecurvatureestimates.
Giventwopoints,pandq,axedreferenceframe,consistingofthethreeunitvectors(u,v,w),isbuiltcenteredonpusingthefollowingprocedure:1)thevectoruisthesurfacenormalatp;2)v=u*pqd3)w=u*v;whered=pq2.
Usingthisreferenceframe,thedierencebetweenthenormalsatp(np)andq(nq),canberepresentedby:1)α=arccos(v·nq);2)φ=arccos(u·(pq)/d);3)θ=arctan(w·np,u·np).
Theanglesα,φ,θandthedistancedarecomputedforallpairsinthek-neighborhoodofpointp.
Infact,usuallythedistancedisdroppedasitchangeswiththeviewpoint,keepingonlythe3angles.
Thesearebinnedintoan125-binhistogrambyconsideringthateachofthemcanfallinto5distinctbins,andthenalhistogramencodesineachbinauniquecombinationofthedistinctvaluesforeachoftheangles.
Oneofthese125-binhistogramsisproducedforeachinputpoint.
TheversionofPFHusedinthispaperincludescolorinformationandiscalledPFHRGB.
Thisvariantincludesthreeadditionalhistograms,onefortheratiobetweeneachcolorchannelofpandthesamechannelofq.
Thesehistogramsarebinnedasthe3anglesofPFHandhenceproduceanother125oatvalues,givingthetotalsizeof250valuesforthePFHRGBdescriptor.
TheseconddescriptorusedistheSHOTCOLOR[5].
ThisdescriptorisbasedontheSHOTdescriptor[6],thatobtainsarepeatablelocalreferenceframeusingtheeigenvaluedecompositionaroundaninputpoint.
Giventhisreferenceframe,asphericalgridcenteredonthepointdividestheneighborhoodsothatineachgridbinaweightedhistogramofnormalsisobtained.
Thedescriptorconcatenatesallsuchhistogramsintothenalsignature.
Ituses9valuestoencodethereferenceframeandtheauthorsproposetheuseof11shapebinsand32divisionsofthesphericalgrid,whichgivesanadditional352values.
Thedescriptorisnormalizedtosum1.
TheSHOTCOLORaddscolorinformation(basedontheCIELabcolorspace)totheSHOTdescriptor.
Ituses31binseachwith32divisionsyielding992values,plusthe352fromtheSHOTwhichgivesSetDistanceFunctionsfor3DObjectRecognition59thetotalof1344values(plus9valuestodescribethelocalreferenceframe).
ThehistogramsinthiscasestoretheL1distancebetweentheCIELabcolorofapointandthecolorofitsneighbors.
4SetDistancesThefocusofthispaperisonthedistancefunctionthatshouldbeusedwhencomparingtwopointcloudsthatarerepresentedbysetsofdescriptors.
Notethattheword"distance"shouldbeinterpretedlooselysincesomeofthefunctionspresentedbelowdonotverifyalltheconditionsofanorm(forinstance,D4andD5canproduceavalueofzeroevenifthetwoinputcloudsarenotthesame).
AdescriptorcanbeseenasapointinXRn.
Weinvestigatetheperformanceoffunctionsthatreceivetwosetsofdescriptors,AXandBX,withapossibledierentnumberofelements,|A|=|B|,andreturna(distance)valueinR.
Wewillusebelowthefollowingdistancesbetweendescriptors(notsets)x,y∈X:Lp(x,y)=ni=1|x(i)y(i)|p1/p,p=1,2dχ2(x,y)=12ni=1(x(i)y(i))2x(i)+y(i).
WewillassignacodetoeachsetdistanceintheformDz,wherezisanintegertomakeiteasiertorefertotheseveraldistancesthroughoutthepaper.
4.
1HausdorDistanceConsiderS(X)tobethesetofsubsetsofXthatareclosed,boundedandnon-empty.
LetA,B∈S(X).
TheHausdordistance,D1,betweensetsAandBisdenedasD1(A,B)=max{sup{d(a,B)|a∈A},sup{d(b,A)|b∈B}}whered(a,B)isadistancebetweenapointaandasetB,denedbyd(a,B)=min{d(a,bi),i=1,B|}andd(a,bi)isthedistancebetweentwopointsaandbiinRn.
InourcaseweusetheL1distancebetweentwopoints.
4.
2PyramidMatchKernelThepyramidmatchkernel(D2)[1]usesahierarchicalapproachtomatchingthesets.
Itndsthesimilaritybetweentwosetsastheweightedsumofthenumberoffeaturematchingsfoundateachlevelofapyramid.
60L.
A.
AlexandreConsidertheinputspaceXofsetsofn-dimensionalvectorsboundedbyasphereofdiameterD.
ThefeatureextractionfunctionisΨ(x)=[H1(x),H0(x)HL(x)]whereL=log2D+1,x∈X,Hi(x)isahistogramvectorformedoverdataxusingn-dimensionalbinsofsidelength2i.
Then,thepyramidreferredaboveisgivenby:KΔ(Ψ(y),Ψ(z))=Li=0Ni/2iwhereNiisthenumberofnewlymatchedpairsatleveli.
Anewmatchatleveliisdenedasapairoffeaturesthatwerenotincorrespondenceatannerlevel(jTobecomeincorrespondencemeansthatbothfallinthesamehistogrambin.
4.
3OtherSetDistancesWeproposetoevaluatealsothefollowingsetdistances,thatareallvariationsaroundthesametheme:usestatisticalmeasureslikethemean,standardvaria-tion,maximumandminimumofthepointsineachsettodevelopsimplerepre-sentationsfortheset.
Thegoalistosearchforasimplesetdistancethatproducesaccurateresultsandatthesametimeisfast,suchthat,otherthingspermitting(thetimethekeypointstaketobedetectedplusthetimethedescriptortakestoextract)wouldallowforrealtimecloudprocessing.
Belowweuseaj(i)torefertothecoordinateiofthedescriptorj.
ThedistanceD3isobtainedbyndingtheminimumandmaximumvaluesforeachcoordinateineachsetandsumtheL1distancesbetweenthemD3=L1(minA,minB)+L1(maxA,maxB)whereminA(i)=minj=1,.
.
.
,|A|{aj(i)},i=1,nandmaxA(i)=maxj=1,.
.
.
,|A|{aj(i)},i=1,nandlikewiseforminB(i)andmaxB(i).
Thenexttwodistancesaresimplythedistancebetweenthecentroidsofeachset,cAandcBrespectively,usingthedescriptordistancesL1andL2:D4=L1(cA,cB)andD5=L2(cA,cB).
DistanceD6isthesumofD4withtheL1distancebetweenthestandarddeviationforeachdimension(coordinate)ofeachset:D6=D4+L1(stdA,stdB)SetDistanceFunctionsfor3DObjectRecognition61wherestdA(i)=1|A|1|A|j=1(aj(i)cA(i))2,i=1,nandlikewiseforstdB.
DistanceD7issimilartoD6butinsteadofusingtheL1distanceusesthedχ2distancebetweentwovectors:D7=dχ2(cA,cB)+dχ2(stdA,stdB).
ThenaldistancetobeevaluatedconsistsontheaverageL1distancebetweenallpointsinonesettoallthepointsintheother(thenormalizedaveragelinkagesetdistance):D8=1|A||B||A|i=1|B|j=1L1(ai,bj).
5Experiments5.
1DatasetWeusedasubsetofthelargedatasetof3Dpointcloudsfrom[7].
Theoriginaldatasetcontains300objectsfrom51dierentcategoriescapturedonaturntablefrom3dierentcameraposes.
Weused48objectsrepresenting10categories.
Thetrainingdatacontaincloudscapturedfromtwodierentcameraviews,andthetestdatacontainscloudscapturedusingathirddierentview.
Thetrainingsethasatotalof946cloudswhilethetestsetcontains475clouds.
Sinceforeachtestcloudwedoanexhaustivesearchthroughthecompletetrainingsettondthebestmatch,thisamountstoatotalof449.
350cloudcomparisonsforeachoftheevaluateddescriptorsandeachofthedistancefunctionsused.
5.
2SetupThecodeusedintheexperimentswasdevelopedinC++usingthePCLlibrary[2]onalinuxmachine.
ThecodeusedforD2wasfrom[8].
WeusedtheUni-formPyramidMakerwiththefollowingparametersobtainedfromexperimentswitha10%subsetoftheoneusedinthenalevaluation:finest_side_length=(1/250,104),discretize_order=(3,3)andside_length_factor=(2,2)for(PFHRGB,SHOTCOLOR),respectively.
Tomakeafaircomparisonbetweenthedistances,allstepsinthepipelineareequal.
ThedescriptorsarefoundonthekeypointsobtainedusingtheHarris3Dkey-pointdetectorwiththefollowingparameters:theradiusfornormalestimationandnon-maximasupression(Radius)wassetto0.
01andthesphereradiusthatistobeusedfordeterminingthenearestneighborsusedforthekeypointdetec-tion(RadiusSearch)wasalsosetto0.
01.
Theonlyparameterneededforthedescriptorcalculationisthesphereradiusthatistobeusedfordeterminingthenearestneighborsusedinitscalculation.
Itwassetat0.
05forbothdescriptors.
62L.
A.
AlexandreTable1.
Categoryandobjectrecognitionaccuracyandthetimeusedforevaluatingthetestsetinseconds,forthedierentdistancesanddescriptorsPFHRGBSHOTCOLORAccuracy[%]Accuracy[%]DistanceCategoryObjectTime[s]CategoryObjectTime[s]D191.
1470.
04191467.
7244.
09175D263.
9242.
19219726.
5817.
931510D388.
8267.
93188988.
8267.
72132D490.
9375.
95187687.
9769.
20137D582.
7067.
72188679.
7555.
49134D693.
8878.
06189187.
7665.
82134D794.
7379.
96189488.
1965.
82127D877.
6460.
13191471.
7341.
351745.
3ResultsTable1andgure1containtheresultsoftheexperimentsdone.
Anobjectisconsideredtoberecognizedwhenaninputcloudismatchedbyoneoftheviewsofthesameobjectinthedatabase,whereasacategoryisconsideredtoberecognizedwhentheinputcloudismatchedtoaviewofanyoftheobjectsthatareinthesamecategoryastheinputobject.
So,categoryrecognitionisaneasiertaskthanthatofobjectrecognition,sinceinthelattercasethesystemneedstodistinguishbetweenthe(similar)objectswithinagivencategory.
Thatcategoryrecognitioniseasierthanobjectrecognitioncanbeseenintable1.
Foralldistancefunctions,categoryaccuracyisalwayshigherthanobjectrecognition.
Regardingtheaccuraciesobtained,theseresultsshowtheimportanceofchoos-ingagooddistancefunction.
Foragivendescriptorthereareconsiderablevari-ationsintermsofaccuracy:intermsofobjectrecognitiontheresultsforthePFHRGBvaryfromaround42%toalmost80%whereasfortheSHOTCOLORdescriptortheresultsvaryfromaround18%toover69%.
ThebestresultsareobtainedforthePFHRGBwithdistanceD7andfortheSHOTCOLORwithdistanceD3forcategoryrecognitionandD4forobjectrecognition.
Fromtherecall*(1-precision)curvesingure1,wenotethattheresultscanbegroupedintothreesets:thebestresultsforbothdescriptors,andwithsimilarcurves,areobtainedwithdistancesD4,D6andD7(forSHOTCOLOR,D3isalsoonthisrstgroup).
ThesecondgroupcontainsthedistancesD1,D5andD8(D3isinthissecondgroupforPFHRGB)thatshowadecreaseinperformancewhencomparedwiththerstgroup.
Thedierenceinperformancefromgroup1togroup2islargerwithSHOTCOLORthanwithPFHRGB.
ThismighthavetodowiththefactthatSHOTCOLORworksonamuchhigherdimensionalspace(1344)thanPFHRGB(250).
DistanceD2isthesolememberofthethirdgroupwithapoorperformance.
Webelievethismighthavetodowithapoorchoiceofparameters.
Buthavingtochoose3parametersforadistancethatisveryheavySetDistanceFunctionsfor3DObjectRecognition6300.
20.
40.
60.
810.
20.
30.
40.
50.
60.
70.
80.
91Recall1-PrecisionD1D2D3D4D5D6D7D800.
20.
40.
60.
810.
20.
30.
40.
50.
60.
70.
80.
91Recall1-PrecisionD1D2D3D4D5D6D7D8Fig.
1.
Recall*(1-Precision)curvesfortheobjectrecognitionexperimentsusingthePFHRGB(top)andSHOTCOLOR(bottom)descriptors(bestviewedincolor)fromacomputationalpointofviewisnotaneasytaskandwemightneededtospentmoretimesearchingfortheoptimalparameterstoobtainabetterresult.
DistanceD4isbetterthanD5(thesearesimplytheL1andL2distancesbetweencloudcentroids)forbothdescriptors,conrmingthefactthattheEu-clidiandistanceisnotappropriateforthesehighdimensionalspaces.
Thefthandseventhcolumnsoftable1containthetimeinsecondsthattooktoruntheevaluation(testset)ona12threadversionusingai7-3930K@3.
2GHz64L.
A.
AlexandreCPUonFedora17.
ThePFHRGBismuchmoredemandingintermsofcompu-tationalcomplexitythantheSHOTCOLOR,hencethetimeittakesisaround10timesmorethanthetimeusedbytheSHOTCOLOR.
Intermsoftimetakentocompletethetests,D2ismuchslowerthantherest.
Givenitstimeoverhead,D2shouldonlybeusedifitcouldprovideanimprovedaccuracywhencomparedtotheremainingdistances,butthatwasnotthecase.
6ConclusionsAnimportantpartofa3Dobjectrecognitionsetupisthedistancefunctionusedtocompareinputdataagainststoreddata.
Sincetherearemanypossibledistancefunctionsthatcanbeusedinthisscenario,theuserisfacedwithatoughdecisionregardingwhichdistancetochoose.
Theobviouswayistomakeexperimentscomparingthesefunctionsfortheirparticulardescriptoranddata,butthiscanbeatimeconsumingtask.
Thispaperpresentsanevaluationof8distancefunctionsonalargepointclouddatasetusingtwodescriptors.
Fromtheresultsoftheexperimentsmadeweconcludethatsimpledistances(suchasD3,D4,D6andD7)canbeagoodchoicesincetheirperformancebothintermsofaccuracyasintermsofspeedsurpassesothermorecommonusedonessuchasD1andD2.
Theformerdistancesalsobenetbynotrequiringtheadjustmentofparameters.
References1.
Grauman,K.
,Darrell,T.
:Thepyramidmatchkernel:Ecientlearningwithsetsoffeatures.
JournalofMachineLearningResearch8,725–760(2007)2.
Rusu,R.
,Cousins,S.
:3Dishere:PointCloudLibrary(PCL).
In:IEEEInternationalConferenceonRoboticsandAutomation(ICRA),Shanghai,China(2011)3.
Alexandre,L.
A.
:3Ddescriptorsforobjectandcategoryrecognition:acompara-tiveevaluation.
In:WorkshoponColor-DepthCameraFusioninRoboticsattheIEEE/RSJInternationalConferenceonIntelligentRobotsandSystems(IROS),Vilamoura,Portugal(2012)4.
Rusu,R.
,Blodow,N.
,Marton,Z.
,Beetz,M.
:Aligningpointcloudviewsusingpersistentfeaturehistograms.
In:InternationalConferenceonIntelligentRobotsandSystems(IROS),Nice,France(2008)5.
Tombari,F.
,Salti,S.
,DiStefano,L.
:Acombinedtexture-shapedescriptorforen-hanced3Dfeaturematching.
In:IEEEInternationalConferenceonImageProcessing(2011)6.
Tombari,F.
,Salti,S.
,DiStefano,L.
:Uniquesignaturesofhistogramsforlocalsurfacedescription.
In:Daniilidis,K.
,Maragos,P.
,Paragios,N.
(eds.
)ECCV2010,PartIII.
LNCS,vol.
6313,pp.
356–369.
Springer,Heidelberg(2010)7.
Lai,K.
,Bo,L.
,Ren,X.
,Fox,D.
:ALarge-ScalehierarchicalMulti-ViewRGB-Dobjectdataset.
In:Proc.
oftheIEEEInternationalConferenceonRobotics&Automation,ICRA(2011)8.
Lee,J.
J.
:Libpmk:Apyramidmatchtoolkit.
TechnicalReportMIT-CSAIL-TR-2008-17,MITComputerScienceandArticialIntelligenceLaboratory(2008)