120 Pages
English

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

Gain access to the library to view online
Learn more

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.

Subjects

Informations

Published by
Published 01 January 2007
Reads 28
Language English
Document size 2 MB

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.Webyfindmeansitofwhenevermachineasurvvisioneillanceisakeysystemfactorisinappliedaman-to
thatsupportneedsortoreplaceperformahumanactionsinoperatoran.unknoItiswnandessentialdynamicforenautonomyvironment,e.g.aontheservicebasisrobotof
itsvisualsensorinputs.Inindustrialproduction,integratedsceneinterpretationsys-
temsproblemaddressreducestotheshortennumberdoofwntimechangesofrobots,thathavesincetoabemoremadetogenericadapttheformulationcontrollingofa
are.softwThedifficultiesstartwiththeacquisitionofdata,whichdependsontherangeand
thecorrelatedaccuracyofasensorandonthe(oftenchanging)illuminationconditions.
Oncethedataisacquired,problemsariseindetermininghowtosegmentanobject,or
separatetomaticallyrelevproantvidesanditsirreleposevantwhichdata.isLastthebutrelationnotleast,betweenaseangmentedobjectandobjecttheneitherobserverau-,
noritsidentitythatisthesubscribingclassorlabel.
Earlyvisionapproachessufferedfromthelimitedprocessingcapabilitiesoftheir
times.Accordingly,theyusedsuchhighrestrictionsthatmostapproachesdidnotleave
thelaboratoriestogainaccesstoindustry.
Withtheavailabilityofeverfastercomputersand3D-sensingtechnology(real-time
stereoprocessing,laserrange-scanner,etc.),moregeneralapproachesbecamefeasible.
Theyallowweakerscenerestrictionsandhencefacilitatenewscenarios.Fundamental
tovisualobjectrecognitioninthesenseoffacilitatingabroadrangeofapplications
arelentapproachesdescriptionsinofgeneralrepresentationfree-formandshapes.classificationAgoodisgiovvenervieinwsurvofetheysofcurrentlyBeslandprevJaina-
[BJ85],ChinandDyer[CD86],FaugerasandHebert[FH86],Stockman[Sto87],Bel-
laire[Bel94],SinhaandJain[SJ94],andCampbellandFlynn[CF01].
Infree-forms.computerTheyaregraphics,alsosurfusefulaceformeshesrecognitionareapopularpurposesandandtheestablishedInternetmakdescriptionesthemof

9

ODUCTIONINTR1.CHAPTER10accessibletoeverybodyfortestingandcomparingalgorithms.Amajordrawback,
however,istheirlargememoryrequirement.Furthermore,surfacemeshesaredefined
withrespecttoaglobalcoordinatesystem.Thustimeconsumingregistrationisnec-
essarytoaligntheobjectofinteresttotheframeofthereferredobjectmodelbefore
matchingispossible.Thesameproblemsapplytovoxel-baseddescriptionsofshape.
Othervolumetricrepresentationsbasedonsuperquadrics,generalizedcylinders,
andsplinesallsufferfromagreatsensibilitytonoiseandoutliersinthesenseddata.A
significanteffortisrequiredtoobtainarobustfittingprocedureandtoselectthemodel
ordersoastoavoidover-fitting.
Itis,therefore,mostdesirabletodevelopashaperepresentationthat(i)iscom-
pact,(ii)isrobust,(iii)doesnotdependonaglobalcoordinateframe,and(iv)hasthe
descriptivecapacitytodistinguisharbitraryshapes.
Apromisingapproachistoanalyzethestatisticaloccurrenceoffeaturesonasur-
facein3Dspace.Thishasbeenpursuedbyextractinglocalfeaturessuchassurface
curvaturesorgeometricrelationssuchasdistances.Theirdistributionsarerepresented
asdiscretehistogramsorpiecewise-linearapproximationsthereof.Theclassification
stepmayberealizedbymatchingameasureddistributionagainstdistributionsstored
inareferencedatabaseofprototypesorbythesearchforcharacteristicpatternsina
ution.distribThefollowingsectionoutlinesthestateofresearchandsummarizesthemostre-
latedworkoftheresearchersthatinfluencedthisthesis.Itfurtherdiscussesthediffer-
capabilities.anddesigninences

ArttheofState1.2Sceneinterpretationalgorithmscanbedividedintotwogeneralgroups.Thefirstgroup
istheonethatisbasedon2D-imagesacquiredbyasinglecamera.Thesecondone
reliesuponsophisticatedsensorsystemsthatadditionallyprovidedepthinformation.
1.2.1ApproachesBasedon2D-Images
Thefirstandoldergroupofsceneinterpretationfamiliesusedimage-basedapproaches.
Comparedtootherdevices,acameraisalow-costsensorthatquicklyprovidestwo-
dimensionalprojectionsofthefocusedworkspace.Unfortunately,anyinformation
aboutdepthisveryweakandhastobeacquiredindirectly,e.g.reconstructionby
shapefromshadingorinterpretationofedgeconstellations.Thus,thisgrouptendsto
realizationsthataremostlydescribedasappearance-basedorview-based.Thestrategy
istherecognitionofatypicalconglomerateofsingleormultiplefeature-typesexpected
undergivenilluminationfromaspecificpointofview.Asaby-producttheprocessof
recognitionandposeestimationisverycorrelated.
SeibertandWaxman[SW92]proposedabiologicalinspirednetworkforobject
recognition.Intheirdesignnodesrepresentsingleviews,whilelinksbetweennodes
representthetransitionstogetfromoneviewtoanother.Theapproachsimplifiesthe
problemofobjectsegmentationbyusingblackenedobjectsinfrontofabrightgrey
structuredbackground.Nonetheless,reliablesegmentationisstillakeyproblemandis
nottrivialatall.Additionally,theapproachcalculatestheobjectcenterofashapefor
comparison.Thisfactdeniestheoccurrenceofocclusion,sinceitleadstoshiftsofthe
center,andthenafollowingcomparisonwouldsuffer.

1.2.STATEOFTHEART11
Anothernetwork-basedmethodisproposedbyWunsch[Wun98].Again,nodes
areusedtorepresentdifferentviewsofanobject.Thepositionsofthesenodesare
optimizedwithaKohonen-network.Afterfeedingthenetworkwithanimage,the
nodewiththemostresemblingviewanswersanddeliversanapproximation1ofthe
pose.Inthefollowing,theapproachusesedgedetectionforfittingaCADmodel
totheobservedscene.Thetreatmentofocclusionsisnotdesigned.Moreover,the
specializationonCADdataandedgesseemsnotsuitedforarbitraryfree-forms.
Thisthesisdealswithahistogram-baseddescriptionoffree-formobjects.Itprofits
mostfromtheideatoformulateobjectrepresentationasacharacteristicstatisticaldis-
tributionoffeatures.SwainandBallard[SB91]describedthisideaforone-dimensional
colorhistograms.Therevolutionarynewaspectintheirapproachwastoclassifyob-
jectsbythedistributionofcolorvalues.Thus,insteadofusingrelationsoffeaturesand
theirpositionsintheimage,theyappliedpositioninvariantinformation.
Schiele[Sch97]andSchieleandCrowley[SC96b,SC96a,SC00]continuedthis
lineofresearch.Theydemonstratedrapidclassificationinmonochromeimages.Their
approachworkedeveninpresenceofocclusion.Theseresearchersbuildoneessential
sourceofinspiration.Detailsontheparallelismbetweentheirworkandtheapproach
discussedherearegiveninthenextchapter(seeChap.2,p.19).
Plagemannetal.[PMB05]representedaview-basedobjectlocalizationusingprob-
abilisticmodelsofappearance.Thesetofappliedfeaturescontainsedges,joints,cor-
nersandcomplexgroupingsthereof.Theirworkconcentratesonsituationswherethe
objectcoversonlyasmallpartofanimage.However,theworkisabletohandlediffi-
cultlightingcondition.Occlusionisnotadiscussedtopic.

1.2.2ApproachesBasedon3DSpatialInformation
Moresophisticatedsensorsprovidemeasurementsofspatialinformation.Thiscate-
goryincludespassiveandactivesystems.Passivesystemsareobserverslikestereo
visionapproaches,whileactivesystemscomprehendanemitterandareceiversuchas
structuredlightapproachesandlaserscanners.Thechosenkindofsensordetermines
thespeed,theaccuracyofmeasurements,andthefinalrealizationofdataacquisition.
HorneggerandNiemann[HN95]presentedagenericframeworkforstatisticallearn-
ing,localizationandidentificationoftwo-andthree-dimensionalobjects.Theyim-
pliedanexpectationmaximization(EM)approachtodeterminetheposeandtypeof
anobject.Unfortunately,theapproachsufferstheEM-typicallongprocessingtimes.
Moreover,thealgorithmneedsalargenumberofviewsfortrainingphaseandseemsto
expectthepresenceofexactlyonesensedobjectinrecognitionphase.Thisassumption
isunrealisticformanyapplications,e.g.itcannotbeassumedthatadesiredobject
isomnipresentinthesensedareaofanexploringservicerobot.Theexpectationof
presentknownobjects(tableorthingsupon)isviolatedwhenevertheservicerobot
entersanemptyroomandthetasktoclearatable.Thenpre-processingisnecessaryto
preventthealgorithmgettingintoundefinedstates.
Osadaetal.[OFCD02]samplethestatisticsofpoint-pairdistancesacrossthe
wholesurfaceof3Dobjects.Theydemonstratesimilaritysearchbasedonthedis-
tancedistribution.However,alotofinformationonshapeisdiscardedbyreduction
tothisone-dimensionalfeature.Vandeborreetal.[VCD02]usethreedistributions
ofone-dimensionalgeometricfeatures,basedoncurvature,distance,andvolume.In
1DesignAidedComputer

ODUCTIONINTR1.CHAPTER12bothworks,recognitionperformanceismoderateandonlysuitableforapreliminary
selectionasperformed,e.g.,byanInternetsearchengine.
HameiriandShimshoni[HS02]lookforsymmetricformprimitiveslikecylinders,
cones,etc.,indepthimages.Asthebasiclocalfeature,theyusethetwoprinciplesur-
facecurvatures,accumulatedinatwo-dimensionalhistogram.Thesurface-curvature
histogramischaracteristicforeachidealformprimitiveandknowna-priorifromgeo-
metricalconsiderations.Forrealmeasureddata,however,relianceuponcurvaturesis
verysensitivetonoiseandartifacts.Moreover,forgeneralshapesthedistributionof
curvatureswillnotbeascrispasforhighlysymmetricshapes.Hence,itmaybeless
informative,andmanyhistogramsmayberequiredtocoverallobjectviews.
Multipleview-basedhistogramshavebeenusedbyHetzeletal.[HLLS01,LHL01]
whoadaptedthealreadymentionedprobabilistic2D-approachfromSchieleandCrow-
leytodepthimages.AccordingtoBayes’rule,thebestmatchiscalculatedastheone
withthehighestaposterioriprobability,givenasetofrandomfeaturesamples.Asa
featuretheyhaveemployedacollectionoflocalsurfacemeasures,namely,pixeldepth,
surfacenormal,andcurvature.Generally,however,ahighnumberofhistogramsper
time.processingincreasesmodelobjectGottfriedetal.[GLW99]usedrangeimagestosolvethetaskofautonomousgrasp-
ingofanobjectfromafilledbox.Theirworkincludedthesegmentationofanobject
inthepresenceofbackgroundandocclusion.However,theyusedtwoalgorithmsde-
signedwithrespecttotheveryspecialobjectgeometriesofasphereandacylinder.An
adaptationtogeneraltasksseemstobequestionable.
Boyeretal.[BSF02]andMokhtarianetal.[MKY01]bothdescribe3Dfree-
formsbymulti-scalerrepresentationsofsurfacecurvatures.Theideaistoidentify
characteristicregionsthatremainstableformultipledifferentscalesofshape.These
approachestypicallysufferfromextensiveprocessing.
SteinandMedioni[SM92]proposedtorepresentobjectsviasplashesand3D-
curvesencodedasconnectedlinearsegments.Theirideaistostoreasetofsigna-
turesthatdescribelocalsurfaceproperties.Inrecognitionphasetheybuildhypothesis
aboutthemostreasonableobject.Accordingly,processingdramaticallyincreasesby
thenumberofisolatedlocalitiesandhypothesesderivedtherefrom.Moreover,ade-
pendencytolocalinformationcorrelateswithasensitivitytonoise.
Analternativelineofresearchhassoughtfordescribingsingle,possiblycharac-
teristicpointsonanobjectbytheirlocalsurfaceshape.Thisincludesthespinimages
ofJohnsonandHebert[JH96,JH99],thesphericalspinimagesofRuiz-Correraetal.
their[RCSM00histograms,],andthesurfacesurfacepointssignaturarepickesedofYandamanayplaneandisFaragrotated[YF02about].theirForlocalcreatingsur-
facenormal.Thesurroundingpointsareaccumulatedinthatplane.Duetorestricted
domain,theplanescanbeinterpretedasa2Dhistogramorimage.Toidentifyanob-
ject,bothapproachesneedtofindatleastthreesignificantpointsandtheirhistograms.
Thentheinformationisusedtodeterminetheobjectposeaswell.Nevertheless,the
approachessufferfromtherequirementofdensesurfacemeshes.
HillenbrandandHirzinger[HH02]havecharacterizedsingularsurfaceshapeby
four-point-relationdensitiesthataredirectlyconstructedfroma3D-pointset.Their
approachgeneratesalargenumberofhypotheseswithrespecttotheobject-typeand
thepose.Tokeepprocessingcostslow,theiralgorithmtestseveryhypothesisinturn
ordering.probabilisticatoaccording

13

1.3.TARGETAPPLICATIONS13
1.3TargetApplications
Iftheproblemoffree-formobjectrecognitionandsceneinterpretationisdiscussed
fromaneconomicpointofview,thefollowingthreesubjectswillbeofmajorinterest:
1.Theobjectdescriptionhastobegenerictoenablemodelingofamaximumnum-
objects.ferentdifofber2.Theclassificationratehastobehigh,whileprocessingcostsneedtobelow.This
enablestheusageofstandardcomputersandonlineapplications.
3.Ingeneral,algorithmsaredesignedforonespecificpurpose.Applyingtheal-
gorithmsjustifiabletoforalarsimilargequantitiesapplicationofusuallyproductorrequiresperformedchanges.actions.ThiseWhenexpenseviseronlypro-
ductioncyclesareshort,theadaptationofanalgorithmhastobeminimal.Au-
tomatedproductionthenbecomesinterestingassoftwarehasalongerlife-cycle
costs.itsforpaytoAsystemthatisabletofulfillallconditionsandcanbewedinawiderangeofap-
plicationswillbeofeconomicinterest.Currently,theEuropeanUnionrecognized
theimportanceofthesequestionsandisfinancinganEU-projectcalledSMErobots2
[sme05],whichisembeddedinthe6thFrameworkProject(FP6).
Thisthesisconcentratesontypicaldemandsofroboticsapplications.Thepresented
approachaddressesrigidfree-formobjectsbeingembeddedinastatic3D-scene,where
inputdataisgivenasacloudofsurfacepointsandsurfacenormals.Applicationswith
piecewiserigidshapes,likearobotarmbuiltofseveraljoints,wouldneedanexpansion
ofthiswork.Deformableshapesarebeyondthefocus.
Further,thetaskoffastobjectsegmentationandclassificationisaddressed.Thusa
resultisdesiredtobeasetofobjectspecificpointcloudsextractedfromtheobserved
scene.applicationThewposeouldofneedobjects,posei.e.information,theirspatialitcouldbeorientation,easilyisecalculatedxplicitlyefromxcluded.theobject’Ifans
algorithms.specializedviacloudspointviewePr1.4Thepresentedresearchleadsthereadertoagenericsceneinterpretationframework,
fulfillingthepreviouslysummarizedpre-conditions.Itisgenericinmanydifferent
concerns.Firstitisanobjectdescriptioncapableofrepresentingthree-dimensional
free-forms.Theusedinformationisthedistributionofpairwiseparameterizedsurface
points.Suchadescriptiondoesnotdemandforspecialrestrictionstoanobjectandcan
beobtainedwithevery3D-sensingdevice.Asystemwillbediscussedwhichisableto
handledifferentdegreesofsurfacedensity.Furthermore,collectingsurfacesamples,
calculatingthedistribution,andstoringtheresultinamodelisaverysimpleandnot
anobjectspecificprocess.Itispossibletogeneratemodelsfromsyntheticsourceslike
CADmodelsorrealdatawithoutchanginganymethod.Asaconsequenceitiswell
suitedforapplicationswhereauserhasonlylimitedknowledgeaboutappliedtechnical
methods.Itwillbeshownthatthepresentedframeworkkeepsthesimplicityinusagefor
thesceneinterpretationaswell.Thisispossiblebecauseofastatisticalapproach,
2SmallandMediumEnterprisesRobots

14

ODUCTIONINTR1.CHAPTER

wherethesceneisdividedintosetsofpoint-pairswhicharemostlikelyforamodel.
Theunderlyingideaisthatthesesetsshowevidentcumulationsatthelocationsofthe
supposedobjecttypes.Therefore,aclusterrefinementstrategyisfollowedthatfinally
deliverspointcloudsbearingthelabelofanobjecttype.
Experimentswillshowtheefficiencyandeffectivenessoftheframeworkwithre-
specttoachievedclassificationandprocessingtime.Indetail,itwillbeshownthatnot
onlythetypeofalocalpointsetispreciselydetermined.Moreover,thepercentage
oftruetofalseobjectpointsperresultisconvincing.Again,thesceneinterpretation
satisfiesthelabel”generic”,becauseofstrictlyrelyingonthedistributionofsurface
point-pairs.Thisconditionentitlesnospecificshapeorstructuralrequirementstoa
scene.Furthermore,theparameterizationoftheframeworkshowsnoneedforadap-
tationwhenchangingthesensingdevicefromsyntheticdatatolaser-scanner,laser
light.structuredor,stripe-profiler

Context1.5Mostsceneinterpretationalgorithmsaredesignedasanembeddedpartofamorecom-
prehensivesystem.Here,thecompletesystemisamulti-sensorydeviceworkingina
poseglobalandcoordinatesourceofframe.control.ItisOnealreadyisafreehandappliedinmotwvoedsensordemonstratorsfor3D-surfwithacedifferentmodeling,pur-
theotherisanautonomousenvironmentexplorationofanindustrialrobot’sworking
forcell.Wfurthereaddressdecisionthemakingsecondandapplicationplanningtoofimplymanipulationrecognitiontasks.ofarobotsenvironment

3D-ModelertheofConcept1.5.1ThedeviceusedinthiscontextwasdevelopedintheInstituteofRoboticsandMecha-
tronicsoftheGermanAerospaceCenter(DLR).Itisamulti-sensorydevice(3D-
Modeler)[SH04]thatincludesthreedifferentsensorsfortheacquisitionofrangedata:
1.Thecentralunitisalaserrange-scanneralsodevelopedintheInstituteofRobotics
andMechatronics[HDH97,las05].Itcontainsalaseremitterandareceiveras-
sembledinonecylindricalunit,whichrotatesaroundaverticalaxis.There-
flectionsofthelaserbeamaremeasuredwithaphoto-chip.Thedistanceiscal-
culatedviatriangulation.Thesensorprovidessamplinginarangefrom50mm
to150mmatanaccuracybetterthan0.1mm.Thesensorprovidessufficiently
accuratemeasurements,exceptfortransluminentormirroringsurfaces.
2.Thesecondsensorisacombinationofanobservingcameraandatransmitting
laser-stripeprofiler.Thedistancesareprocessedbycalculatingtheverticalpo-
sitionsofthelaserbeaminthecameraimage.Basisforthisistheknowledge
abouttheorientationoftheemittedlaserplanewithrespecttothecamerathatis
determinedinacalibrationphase[SSW+04].Therangeofthesensorisabout
300mmto1500mm.Theaccuracyofthemeasurementsiscomparabletothe
module.-scannerlaser3.Alternatively,thecameraofthelaserstripesystemcanbecoupledwithasecond
camera.Thepairofcamerasbuildsastereosystem,whichcanbeusedtoac-
quiredistancesabove500mm.Stereoprovidestheadvantagesoffastacquiring

CONTEXT1.5.

15

depthmaps,whereeverymeasurementhaseasilyobtainableneighborhoodrela-
tions.Ontheotherhandstereoistypicallyverynoisyandsuffersfromahigh
dradependencwbacksyoftoasurfstereoacedetevice.xture.Takingintoaccountmotionhelpstoeliminatethe
Figure1.1showsasketchofthefirstfreehandprototypeofthe3D-Modeler,while
forFig.the1.2(a)useinshowsrobotics.theItsecondismoregeneration.compactTheanddeprovicevidesdepictednointriggersFig.on1.2(b)theisoutsidedesignedof
hull.the

1.5.2Definitionofthe3D-ModelerinaGlobalCoordinateSystem
Theacquireddataareinrelationtothe3D-Modeler.Hence,asecondsystemhas
tobeinvolvedtoregisterthemovementsofthemulti-sensordeviceandtotranslate
forsensorgettingrelativtheepositionmeasurementsandposeintoofatheglobal3D-Modelercoordinateareinsystem.use:Threealternativetools
1.Thefirsttoolrefersthepositionofthemodelerbytheuseofopticalmethods.

Figure1.1:ThepictureshowsasketchofthefirstfreehandversionoftheDLR3D-
Modeler.Fromthetopdownwardsthepictureshowsthecamerausedforsensing
alaser-stripe,thelaserrange-scannerwiththelaseremitteraboveandthereceiver
beneath,thesecondcameraforstereo-vision,andthelaser-stripeprojector.The3D-
ModeleriscontrolledwiththreetriggersandoneLCD-displayinthegrip.

16

(a)

(b)

1.CHAPTER

ODUCTIONINTR

Figure1.2:BothpicturesshowsketchesofthesecondgenerationDLR3D-Modeler.
(a)Fromthetopdownwardsthepictureshowsthenewfreehand3D-Modelerversion
showsapairofcamerasusedforstereovisionandlaser-stripeprofiling,thenthelaser
range-scannerunit,andatthebottomthelaser-stripeprojectors.(b)Thepictureshows
asketchoftheDLR3D-Modelerforrobots.Insteadofagrip,thesensordevicecanbe
robot.aonmounted

CONTEXT1.5.

(a)

(b)

17

Figurecoordinate1.3:Theframe.picturesInFig.show1.3(a)twothepossibilities3D-Modelerofisreferringequippedthewith3D-Modelerasetofinareflectingglobal
fiducialmarkersthatareposedinanon-ambiguousconfiguration.Thenasetofmul-
tiplelocatethecamerassend3D-Modeler.infraredAnotherflashesatpossibilityconstantisrate,depictedsointhatFig.themark1.3(b).erscanThere,beusedreferringto
isdonewithapassivearmandthe3D-Modelerisfixedattheend.Thearmmeasures
allsixdegreesoffreedomandthusisabletoprovidethe3D-Modeler’sposition.

Therefore,atleasttwocamerasareusedtosurveyaworkingspace.Then,a
periodicallytransmittedinfrared-flashilluminatesasetoffiducialmarkersthat
areplacedinadefiniteconstellationonthesurfaceofthe3D-Modeler’shull.
Bythehelpofband-widthfiltersthecamerasonlysensethereflectionsinthe
chosenwavelengths.Then,themeasureddataofthemodeleraretranslatedinto
system.coordinateglobalpre-defineda

2.Thesecondoneisapassivearmrealizedasa7-degrees-of-freedom(7-DoF)arm,
inlikeitindustryisshoorwnrevinerseFig.1.3.engineering.TheseDuesystemstoareincrementalmostlyusedsensorsforineveryinspectionjoint,tasksthe
trajectoryofthebasistothetoolcenterpointisprocessible.

3.Thethirdmethodofbuildingareferencefortheposeandpositionof3the3D-
Modelerissimilartothesecondone.Itisarobotwithproprioceptioncapabil-
ities.Hence,therobothasthetransformationmatrixatanytimeandisableto
3ArobotThewithtermprproprioceptionoprioceptiondescribescapabilitiesaisablesystemstomeasurefeasibilitythetogetactualinformationanglesinevabouteryitsjoint.actualconfiguration.

18

INTR1.CHAPTERODUCTION

transformthesensoroutputsintoitsowncoordinateframe.

ormatFData1.5.3The3D-Modelerprovidesmultipledataformatsforthesampledsurfaces.Inthecase
ofspatialinformationfourformatsareofinterest:

point&surfdiraceection:point,theTheraotherwisformattheviewconsistsdirectionofpairsoftheof3D-vsensoratectors.acquisitionOnevectortime.isa

depthmap:Thestereocamerasprovidedepthmaps.Here,theviewdirectionisavail-
ableforallmeasurementsintheimage.Surfacenormalshavetobecalculated
.separately

mesh:easilyThethirdobtainedformatbydisplayscalculationsasurfovaceerasaneighboringtriangulatedtrianglesmesh.toaSurfpoint.acenormalsare

orientedsurfacepoint:Thesurfacescanalsobedirectlyobtainedaspairsofsurface
pointsandcorrespondingsurfacenormals.

Thenormalsfirstareandnotthedirectlysecondavformatailable.demandTheirforcalculationpreparationneedsofthesomedatakindsinceofthesurfacesurfas-ace
sumptionwithrespecttoquestionsconcerningwhetheralocalareaisalocalplanar
patchoflowdensityorahole.Themeshneedsaseparatedcalculatingstepfornor-
mals,too,butitistrivialandfast.Thedatagiveninorientedsurfacepointscontain
allnecessaryinformationforthediscussedsceneinterpretationapproachatacquisition
time.

2RepresentationObject

HEpotentialofanobjectrecognitionapproachwithrespecttoversatility,relia-
Tbilityandperformancestronglydependsontheusedobjectrepresentation.Each
descriptionisbasedononeormultiplefeaturesthataresupposedtobealmostinvariant
forchangesoftheenvironment.Thelessspecificsuchafeatureisthemoreobjectsit
represent.canOntheotherhand,genericfeaturestendtooccurintheobjectsofinterestaswell
asintherestoftheenvironment,whichisfurtherreferredtoasbackground.Toavoid
ambiguitiestherelativeoccurrencesofafeatureandtheirconstellationsaremeasured
analyzed.andThischapterintroducesanovelobjectrepresentationforthree-dimensionalfree-
formobjects.Itincludesthederivationofagenericnovelsurfacefeatureandexplains
howitcanbeusedtodescribeanobject.Thechapterconcludeswithtwodifferent
approachestogenerateanobjectrepresentation.

esentationReprObjectHistogram-Based2.1Objectsfeatures.oftenStatisticsshowhaveprocharacteristicsventobeinathepowerfulconstellationtooltoasdescribewellasinthesethecharacteristics.appearanceof
SwainandBallard[SB91]appliedastatisticalapproachtocomputervisionand
accuraterepresenteddescriptionobjectsofbyshapenorone-dimensionalanyothercolorgeometrichistograms.aspect,Evitenshowsthoughasimplethisisandnotfastan
methodthatinspiredmanyresearchers.
OnesignificantcontributioninthislineofresearchistheapproachofSchieleand
Crofromwlecolory[SC96bimages,toSC96a,gray-scaleSch97,images.SC00].TheTherefore,yportedtheytheinterpretedhistogram-basedgrey-scalevmethodalues
asheightsinanintensitymap.Theresultingmapswereusedforcalculatinglocal
Gaussianderivatives.Thedistributionoftwo-dimensionalGaussianderivativesbuilds
onecharacteristichistogramperimage.Finally,theobjectrepresentationconsistsof

19

20CHAPTER2.OBJECTREPRESENTATION
severalhistogramsgeneratedfromdifferentpointsofview.Schieleetal.demonstrated
anapproach,whichisabletodealwithocclusionandclutteredscenes.
Inthefollowing,Hetzeletal.[HLLS01]presentedastronglyrelatedapproach,
wheretheGaussianderivativesarecalculatedfromadepth-map(2.5Dimage).Asin
agray-scaleversiontheydescribedanobjectwithacollectionofmaps,takenfrom
differentpositions.Nevertheless,thereductiontolocalaspectsisalossofinformation
thatcannotrepresentglobalaspectsevenifusingdifferentpointsofview.Moreover,
themultitudeofviewsandcorrespondinghistogramsleadstohighprocessingcostsfor
recognition.Someresearchers,e.g.Ankerstetal.[AKKS99],proposedtoinvolvethecenterof
massintheobjectdescription,sincethisleadstoatranslationinvariance.Considering
typicalproblemsofsceneinterpretationlikeincompletesurfaces,clutter,andthepres-
enceofanunknownbackground,onecanseethatthedeterminationofthecenterof
masssuffers.Thus,thecircumstancesdemandothermethods.
OthercommonconceptsliketheExtendedGaussianImage[Hor84,Bel94,CF01]
offertranslationalinvarianceandremainrotationallyvariant.
Althoughotherresearchersdidnotcoverlocalandglobalaspectsofshapeinone
singlehistogram,theyhavetobementionedsincetheirstudiesgavehintsastoimpor-
representation.objectforaspectstantForinstance,Osadaetal.[OFCD02]sampledthestatisticsofone-dimensional
point-pairdistancesacrossthewholesurfaceof3Dobjects.Theydemonstratedsimi-
laritysearchbasedonthedistancedistribution.Vandeborreetal.[VCD02]usedthree
distributionsofone-dimensionalgeometricfeatures,basedoncurvature,distance,and
volume.Bothworkssuggestthatone-dimensionalfeaturedistributionsarenotcapable
ofdistinguishingmanyobjects,sincedifferentobjectscanproduceequalorverysim-
ilardistributions.Distancedistributionsforexamplecannotdiffermirrorimage-like
objects.Nevertheless,moderaterecognitionresultsarestillsuitableforapplications
thatsatisfywithapreliminaryorcoarseselection.Anexampleofanapplicationis
anewtypeofInternetsearchengines,whereaqueryconsistingofanobjectsketch
resultsinaobjectlistorderedbyacertainsimilaritycriterion.
HameiriandShimshoni[HS02]lookedforsymmetricformprimitives,likecylin-
ders,cones,etc.,indepthimages.Asthebasiclocalfeature,theyusedthetwoprin-
ciplesurfacecurvatures,accumulatedinatwo-dimensionalhistogram.Thesurface-
curvaturehistogramischaracteristicforeachidealformprimitiveandknowna-priori
fromgeometricalconsiderations.Forrealmeasureddata,however,relianceuponcur-
vaturesisverysensitivetonoiseandartifacts.Moreover,forgeneralshapesthedistri-
butionofcurvatureswillnotbeascrispasforhighlysymmetricshapesandmayhence
belessinformative,andmanyhistogramsmayberequiredtocoverallobjectviews.

2.2Four-dimensionalGeometricFeature
Inthecontextofthree-dimensionalsurfacerepresentationsextrinsicparametersde-
scribetheposeofanobjectinagivencoordinateframe,whiletheshapeisdefinedby
intrinsicparameterslikecurvature.Asurfacecanbedecomposedinorientedpoints.
Thiscontext,allowsfor:
DEFINITION2.1:Asurfletdefinesanorientedpoint.Itconsistsofa3Dpointloca-
tionandanormalized3Dpointorientation.Inthecontextofshapedescription,a

2.2.FOUR-DIMENSIONALGEOMETRICFEATURE21
surfletisasurfacepointanditscorrespondingsurfacenormal.Surfacenormals
alwayspointoutsideashape.
Inthecontextofobjectclassification,themostinterestinginformationconcernsthe
toidentitythepointofanofobject.observation.UnfortunatelyAs,alreadytheappearancementionedofintheobjectsbecanginningvaryaoflotthisdependingchapter,
representationsthatarenottranslationandrotationindependentneedtocompensate
stratethesegydeisgreestoofrecordfreedomthevinariantthemodelappearancesorinduringthemodel.recognition.AFcommonorthefirstsolutioncase,isaa
casecollectionfollowsofamultiplecomplementaryposesperstrateobject.gy.AAccordinglydetailed,modelmemoryiscostcomparedishigh.toThethesensedsecond
thisdata.Iftypicallythereisinvolvenoughesaelargevidencenumberforafit,ofhypothesesrecognitionthatwillbeneedtosuccessful.beevaluated.Unfortunately,

n1replacementsPSfragp1

(a)

n2

p2

(b)Figure2.1:(a)Twosurfacepointsp1,p2andtheirorientationsn1,n2.(b)Illustration
ofthefour-dimensionalfeatureparameterization.Thevectorn2istheprojectionofn2
intheuw-plane.Theparameters,arccos,andarccosareangles,whileisthe
lengthofthevectorp2p1.

22CHAPTER2.OBJECTREPRESENTATION
ingOncosttheintensiothervehand,processinglimitingforathelossrepresentationofposetotheinformation.intrinsicThisisparametersaminortradesdraavwbackoid-
sinceitismuchcheapertorecoverafterrecognitionwhenitiseverneeded.Thisthe-
sisrealizesthisconceptbytheuseoffeaturesthatdescriberelationsbetweensurflets.
Thedistributionofsuchafeaturebuildstherepresentationofanobject.Afeature
distribimpliesutionthatallcandebegreesinterpretedoffreedomasannotecoxpansionveredofbyathesinglefeaturefeature.alsoThecannotebexpansioncov-
eredbythedistributionandleadtoambiguities.Accordingly,thisthesisintroduces
anovelfour-dimensionalfeaturethatdefinitelyparameterizestheintrinsicsurflet-pair
curvrelations.aturesmeasureSurflet-pairgeometricrelationscanrelationsbeviewedbetweenasaneighboringgeneralizationsurflets,ofcurvsurflet-pairatures.Whilerela-
tionsencodethesameforanytwosurflets.
thesurfEachacesurfletnormalisn.describedLetthebyaoperatorpair(p,n)denote,theconsistingscalaroftheproductpositionoftwvovectorectors,pand
thecrossproductoftwovectors,||||theEuclideannormofavector,and||the
modulusofarealnumber.Foreachsurflet-pair
s=((p1,n1),(p2,n2)),(2.1)
anunambiguouscoordinatesystemhastobedefined.Therefore,theoriginischosen
tobep1,if
|n1(p2p1)||n2(p2p1)|,(2.2)
anditisp2else.
Nowp1isassumedtobetheorigin.Thebasevectorsofthecoordinatesystemare
asdefinedthenu=n1,(2.3)
(p2p1)u
v=(p2p1)u,(2.4)
w=uv.(2.5)
Therelationbetweenthesurflets(p1,n1)and(p2,n2)isdescribedbytheparameters
=arctan(wn2,un2),(2.6)
=vn2,(2.7)
=upp2pp1,(2.8)
12=p2p1,(2.9)
efeaturthedefinewhichfs=(,,,).(2.10)
Theprocessoffeaturegenerationisfurthersymbolizedbythefunction
:s→fs.(2.11)
notationshorthandtheHerearctan(y/x)forx>0∧y>0,
arctan(x,y):=arctan(y/x)+forx<0,
arctan(y/x)+2forx>0∧y<0

23

2.3.MODELGENERATIONINTRAININGPHASE23
isused.Accordingly,thecodomainis
∈[,[,(2.12)
∈[1,1],(2.13)
∈[1,1],(2.14)
∈]0,M,max].(2.15)
Therangeofvaluesisobject-independentexceptfor,whereM,maxisthemaximum
distancethatoccursbetweentwosurfletsofanobject.
angle,Therespectiattribvutesely.Theandanglerepresentandnthe2asandistanceazimuthalrepresentangletheandthedirectioncosineandofalengthpolarof
thetranslationfromp1top2,respectively.Limitingandtoscalarproductskeeps
.wlocostsprocessingThisparameterizationisillustratedinFig.2.1.Ofcourse,ifcondition(2.2)deter-
minesp2tobetheorigin,theparameterswillbeobtainedbyinterchangingtheindices
1and2intheequationsabove.
Equations(2.6)to(2.9)mapeveryconfigurationofasurfletpairtoauniquesetof
parameters,andeverypossiblesetofparametersdescribesexactlyonesuchconfigu-
ration.Moreover,condition(2.2)ensuresthatthebasevectorsu,v,waredefinedin
themostrobustmanner:bychoosingthemoreorthogonalanglebetweenp2p1and
thetwosurfacenormalsn1,n2fordefiningv[Eq.(2.3),Eq.(2.4)]thedirectionofv
isdeterminedwithhigheraccuracy.Giventhefulfilledcondition(2.2)andchoosing
p2fortheoriginofthecoordinatesystemendangerstheunambiguoutyofthefeature.
Inthiscaseasurfacenormalwouldbeallowedtobecollineartothevectorp2p1.
Thisconstellationdoesnotallowfordefininganunambiguouscoordinateframe.
2.3ModelGenerationinTrainingPhase
Onefeaturedescribestherelationsoftwosurfacepointstoeachother.Theoccurrence
oftheacertainprobabilityfeatureofafeatureparameterizationparameterizationdependstoonoccurthe,vshapeariesofwithantheobject.observedAccordinglyshape.,
Moreover,itispossiblethatsomeparameterizationsareinvalidinthecontextofan
object.Regardingasphereforexample,itisnotpossibletogetapairofsurface
points,wherethesurfacenormalsareparallel1Thus,anobjectdescriptioncanusethe
distributionoffeaturesforrepresentation.
setawithStarting={(p1,n1),...,(pm,nm)}(2.16)
ofmsurflets(pi,ni),wedefinethefunction
:,k→S,(2.17)
setthegenerateswhichS={s1,...,sk}(2.18)
ofksurflet-pairssi.Thenumbermofsurfletsresultsinamaximumnumberof
nfs=m(m1)(2.19)
21Note:Thepointlyingexactlyontheothersideofthesphereiscollinearbutanti-parallel.

24CHAPTER2.OBJECTREPRESENTATION
surfletpairings,wheneverysurfletiscombinedwitheveryothersurfletoftheshape.
Inthiscase,wegetk=nfs.Forrealobjects,thenumberofsurfletsresultsinvery
largenumbersfornfs.Accordingly,kischosentobemuchsmallerthannfs.The
distributionofthecorrespondingfour-dimensionalfeatures
={fs|fs=(s),∀s∈S}(2.20)
isapproximatedbythehistogramHM.Therefore,themapping-function
hM:fs→b∈{1,2,...,d}(2.21)
transfersafeaturefstothecorrespondingbin2HM(b).Althoughthefeaturevector
consistsoffourdimensionsthehistogramislinearizedtosimplifyfurthercalculations.
sizehistogramtheThus,d=dddd(2.22)
isthenumberofbins,whered,d,danddaretheresolutionstepsthatdefinethe
numberofintervalsperfeaturecomponent.Thechoiceofresolutionstepsspecify
thedescriptivenessaswellasthecompactnessoftheobjectrepresentation.Figure
2.2showsasketchofalinearizedfour-dimensionalhistogram.Itshowstherelation
betweenindexedhistogrambinsandthecorrespondingdiscretizationintervalsofthe
feature.-dimensionalfour

HMHM(dddd1)
HM(0)HM(d1)∈[dd2,[,