Rapid histogram-based scene interpretation in three-dimensional surface point clouds [Elektronische Ressource] / Eric Wahl

Description

Technische Universitat¤ Munchen¤Lehrstuhl fur¤ DatenverarbeitungRapid Histogram-based Scene Interpretation inThree-dimensional Surface Point CloudsEric WahlVollstandiger¤ Abdruck der von der Fakultat¤ fur¤ Elektrotechnik und Informationstechnikder Technischen Universitat¤ Munchen¤ zur Erlangung des akademischen Grads einesDoktors rer. nat.genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr.-Ing. G. Farber¤Prufer¤ der Dissertation:1. Univ.-Prof. Dr.-Ing. K. Diepold2. Hon.-Prof. Dr.-Ing. G. HirzingerDie Dissertation wurde am 04.10.2006 bei der Technischen Universitat¤ Munchen¤eingereicht und durch die Fakultat¤ fur¤ Elektrotechnik und Informationstechnik am14.05.2007 angenommen.2AcknowledgmentsThis thesis summarizes the investigations of three and a half years. Although, it wasmy part to guide this process and to draw the nal conclusions, it would have neverbeen possible without a lot of help and fortunate conditions.First of all I would like to thank Prof. Gerd Hirzinger for giving me the chance towork in a highly inspiring environment, namely the Institute of Robotics and Mecha-tronics of the German Aerospace Center (DLR). At this institute I had the opportunityto collaborate with many wonderful colleagues. Furthermore, he gave me the latitudeto develop and realize my ideas.Second, I want to thank my doctoral advisor Prof. Klaus Diepold. He was veryhelpful in guiding and motivating me when I was unsure of the direction of my research.

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2007
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

TechnischeUniversit¨atM¨unchen
Lehrstuhlf¨urDatenverarbeitung

RapidThree-dimensionalHistogram-basedSurfaceScenePInterointprCloudsetationin

WEricahl

VderollstT¨andigerechnischenAbdruckUniversitder¨atvMon¨derunchenFakultzur¨atf¨urErlangungdesElektrotechnikakademischenundGradsInformationstechnikeines

Dissertation.genehmigten

nat..rerDoktors

Vorsitzender:Univ.-Prof.Dr.-Ing.G.F¨arber
Dissertation:derufer¨Pr2.1.UnivHon.-Prof..-Prof.DrDr.-Ing..-Ing.G.K.HirzingerDiepold

DieDissertationwurdeam04.10.2006beiderTechnischenUniversit¨atM¨unchen
eingereichtunddurchdieFakult¨atf¨urElektrotechnikundInformationstechnikam
angenommen.14.05.2007

2

Acknowledgments

myThispartthesistoguidesummarizesthisprocesstheinvandtoestigationsdrawofthethreefinalandaconclusions,halfyears.itwouldAlthough,haveitnewveras
beenpossiblewithoutalotofhelpandfortunateconditions.
FirstofallIwouldliketothankProf.GerdHirzingerforgivingmethechanceto
workinahighlyinspiringenvironment,namelytheInstituteofRoboticsandMecha-
tronicsoftheGermanAerospaceCenter(DLR).AtthisinstituteIhadtheopportunity
tocollaboratewithmanywonderfulcolleagues.Furthermore,hegavemethelatitude
todevelopandrealizemyideas.
helpfulSecond,inIguidingwantandtomotithankvatingmymedoctoralwhenIwadvisorasunsureProf.ofKlausthedirectionDiepold.ofHemywasresearch.very
Also,hetookthetimeforlengthydiscussions.
Furtheracknowledgmentsgotoallmycolleagueswhosupportedmeinmanydif-
ferentways.EspeciallyDr.UlrichHillenbrandhelpedmemanyhourswithcontem-
plations.Heaskedmetherightquestionstoevaluatemywork.TimBodenm¨uller,
KlausStroblandMichaelSuppakeptthehardwarerunningandcalibratedwheneverI
andneededSusanit.MoreoSeiboldver,forIwgiouldvinglikmeetofeedbackthankonBernhardmyKpapers¨ublerand,thisChristianwork.Ott,IamandsureUlrichit
wasahardjob.LastbutnotleastIthankWolfgangSeppforanendlessnumberof
interruptingphonecallsandquickanswers.
AttheendofmythesisIwantedtotestmyalgorithmswithmanydifferent3D-
sensors.acquiredsetsHere,ofethexcellententerprise3D-dataABWwithoutGmbHanyofMr.questionsWolfinseniorreturn.IandthankMr.Wbotholfgentle-junior
help.generousthisformenmysonLastbhaduttonotleast,tolerateIthatreceiIvedwasgreatoftensupportshortoffromtime.myfNeamilyv.ertheless,Especiallybothmyhelpedwifeandme
torelaxattheweekendsandtocollectnewpowerforlongdaysstartingintheearly
morning.ThankyouNina,thankyouLovis!
EveryNote,listedthepersonorderof(andthislistsurelydoessomenotIharefervetoforthegotten)importancewereofnecessarypeople’stomakcontribeute.me
end.thereach

3

AbstractInthisworkanewframeworkforgenericsceneinterpretationisintroduced.Itisbased
onseveralstatisticalapproachesrangingfromanoveldescriptionofobjectshapesto
theirlocalizationandclassificationincomplexscenes.Inthepresentcontextascene
isastaticarrangementofseveralthree-dimensional(3D)rigidfree-formobjectsrepre-
sentedbyalargenumberof3D-surfacepointsandsurfacenormals.Theinterpretation
ofasceneisthesegmentationofthescenedataintoobject-specificpartsandclassifi-
cationoftheidentityofeachpart.
Thefirstpartofthisworkaddressestheefficientdescriptionof3Dfree-formob-
jectsusingahistogram-basedmodel.Itreliesonthestatisticaldistributionoffour-
dimensionalsurfacepoint-pairrelations.Thisshaperepresentationisderivedinatrain-
ingphasebybincountingalargeamountoffeaturesamples.Itisdemonstratedthat
onceamodelhistogramisbuilt,arelativelysmallnumberofrandomsamplesfrom
anobjectsurfaceissufficientforrecognizinganobjectfromadatabasecontaining20
models.Severalmetricsforcomparingmodelhistogramstosensedfeaturesamplesare
investigated,andthelikelihoodcriterionisfoundtobemostsuitable.Thecompact-
nessofmodelsinadditiontosmallsamplesetsenablesahighefficiencyintermsof
processingtimeandmemoryintherecognitionphase.
Nevertheless,pointsofanobjectfirstneedtobedrawn.Here,theaccesstoa
3D-shapeembeddedinascenestronglydependsontheorganizationof3D-space.To
managethistask,aregionsearchalgorithmbasedonanoctalsubdivisionofspaceis
discussed.Bycombiningtheobjectdescriptionandtheregionsearchalgorithmitispossible
torealizeaframeworkfor3D-sceneinterpretation.Thestrategyisdeterminedbythe
natureofmodelsemployed.Indetailitisthesearchforcharacteristicdistributionshid-
deninascene’spointcloud.Thetaskisachievedbyacluster-basedapproach,where
iterativelyappliedfilteringconditionsclearpointcloudsofaclusterfromirrelevantand
disturbingbackgroundpoints.Modelsareusedtocontrolthefocusofinterest,while
thealgorithmsegmentsandclassifiesanobjectsimultaneously.
Todemonstratethepotentialofthesceneinterpretationframework,therateofcor-
rectclassificationandthecorrectnessofthesegmentedpointsarediscussedinrelation
tonoise,occlusion,pointclouddensity,andtheseparationofobjectswithrespectto
theirdistancefromeachother.Forthisstudy,databasesofsyntheticandrealobjects
areused.Thealgorithmiscapableofhandlingbothincomparablyhighquality,with-
outtheneedforchanginganyparametersofthealgorithm.Theresultsobtainedfor
classificationrateandspeeddemonstratethatthesystemiswellsuitedfortasksthat
demandhighflexibilityandlowprocessingcosts.

4

1

2

3

Contents

oductionIntr1.1Motivation................................
1.2StateoftheArt.............................
1.2.1ApproachesBasedon2D-Images...............
1.2.2ApproachesBasedon3DSpatialInformation.........
1.3TargetApplications...........................
1.4Preview.................................
1.5Context.................................
1.5.1Conceptofthe3D-Modeler..................
1.5.2Definitionofthe3D-ModelerinaGlobalCoordinateSystem.
1.5.3DataFormat..........................
esentationReprObject2.1Histogram-BasedObjectRepresentation................
2.2Four-dimensionalGeometricFeature..................
2.3ModelGenerationinTrainingPhase..................
2.3.1UsingSmallandMediumSurfaceMeshesforTraining....
2.3.2UsingPointCloudsforTraining................
2.4HistogramResolutionandDescriptiveCapacity............
ClassificationHistogram-based3.1RelatedWork..............................
3.1.13D-SearchEngines.......................
3.1.2AlternativeClassificationApproaches.............
3.2StructureofaQuery...........................
3.3Histogram-similarityCriteria......................
3.3.1SquaredEuclidianDistance..................
3.3.2Intersection...........................
23.3.3-Test.............................
3.3.4Kullback-LeiblerDivergence..................
3.4LikelihoodCriterion..........................
3.5PenaltyTerm..............................
Experiments:3.6DescriptivenessandClassificationRates................
3.6.1ProcedureofTrainingPhase..................
3.6.2ProcedureofRecognitionPhase................
3.6.3SurfaceMeshing........................
3.6.4Idealconditions.........................
3.6.5Noisydata...........................
3.6.6Partialvisibility.........................

5

991010111313141415181919202325262629292930303131323234343537373939394042

6

CONTENTS

3.6.7GeneralizationAcrossMeshResolution............43
3.6.8GeneralizationandSimilarity.................43
3.6.9ConclusiontoDescriptivenessandClassification.......46
55esentationReprSpace44.1TheNeighborhoodProblem......................55
4.1.1RelatedSpaceRepresentationApproaches...........56
4.1.2RequirementsintheContextoftheObjectModel.......57
4.2IndexingRestricted3D-Space.....................57
4.2.1KeyGeneration.........................58
4.3TreeImplementation..........................60
4.3.1DataPreparation........................60
4.3.2TheOctree...........................61
4.3.3TheBalancedBinaryTree...................61
4.4TheRegionSearchAlgorithm.....................62
4.4.1PerformanceoftheAlgorithm.................65
4.4.2ExamplesforbothTreeStructures...............66
4.5IndexingUnrestricted3D-Space....................68
4.5.1SpacePartitioning.......................68
4.5.2Super-KeyGeneration.....................69
4.5.3ExtensiontotheRegionSearchAlgorithm..........69
Experiments:4.6PerformanceoftheRegionSearchAlgorithm.............70
4.6.1TestDesign...........................70
4.6.2RegionSearchResults.....................72
5SceneInterpretation75
5.1WorkingEnvironmentandIntendedResults..............75
5.2TheIdea.................................76
5.3Crosstalk................................77
5.4TheSegmentationAlgorithm......................77
Experiments:5.5SceneInterpretationinPractice.....................83
5.5.1Scenario.............................83
5.5.2SyntheticData.........................84
5.5.3ExperimentsonRealData...................91
6Outlook-ExtensionsAndRefinements99
6.1PositioningoftheClusters.......................99
6.1.1TheFloatingClusterSeedsAlgorithm.............100
6.1.2Results.............................101
6.1.3RepetitiveClustering......................102
6.2IncreasingtheNumberofClusterPoints................103
6.3ParallelismandOnline-Recognition..................104
6.3.1ParallelizedModelEvaluation.................104
6.3.2Online-Recognition.......................104
6.4PoseEstimation.............................105
107Conclusion7

CONTENTS

A

Notation

7

109

8

CONTENTS

1Introduction

ationvMoti1.1ROBifoldUSTofscenedifferentinterpretationareas.Webyfindmeansitofwhenevermachineasurvvisioneillanceisakeysyste