Error analysis of 3D shape construction from struc

PergamonPatternRecoonition,Vol.29,No.2,pp.189-206,1996ElsevierScienceLtdCopyright©1996PatternRecognitionSocietyPrintedinGreatBritain.Allrightsreserved0031-3203/96$15.00+.000031-3203(95)00076-3ERRORANALYSISOF3DSHAPECONSTRUCTIONFROMSTRUCTUREDLIGHTING*ZAIMINGYANGandY.F.WANGtDepartmentofComputerScience,UniversityofCalifornia,SantaBarbara,CA93106,U.S.A.(Received29December1993;inrevisedform10May1995;receivedforpublication2June1995)AbstractInthispaper,wepresentadetailedmodelandanalysisofseveralerrorsourcesandthiereffectsonmeasuringthree-dimensional(3D)surfacepropertiesusingthestructuredlightingtechnique.Theanalysisisbasedonageneralsystemconfigurationandidentifiesthreetypesoferrorsurces--systemmodelingerror,imageprocessingerrorandexperimentalerror.Absoluteandrelativeerrorboundsinobtaining3Dsurfaceorientationandcurvaturemeasurementsusingstructuredlightingarederivedintermsofthesystemparametersandlikelyerrorsources.Inadditiontothequantizationerror,otherlikelyerrorsourcesinsystemmodelingandexperimentalsetuparealsoconsidered.Eventhoughouranalysisisonstructuredlighting,theresultsarereadilyapplicabletoothertriangulation-basedtechniquessuchasstereopsis.Finally,ouranalysisfocusesonerrorininferringsurfaceorientationandprincipalsurfacecurvature.Suchanalyses,toourknowledge,haveneverbeenattemptedbefore.ImageprocessingStructuredlightOrientationCurvatureErroranalysis1.INTRODUCTIONTheproblemofreconstructing3Dsurfacestructuresfromtheir2Dprojectionsisanimportantresearchtopicincomputervision.Overthepasttwodecades,avarietyoftechniqueshavebeendevelopedtoinfer3Dsurfacestructuresfrom2Dimagesusingdifferentimagingdevices,shapecuesandheuristics.(1-3)Thesetechniquescanrelyonambientlightreflection(passivesensing)orcanemployalightsourcetoactivelyprobetheenvironment(activesensing).Theyhavealsoreliedonmanyimageshapecuessuchasstereodisparity,imagebrightnessandsurfacepatterntorecoverthedepth,orientationandcurvatureofanimagedsurface.Tostudythefeasibilityofthese3Dshaperecon-structiontechniquesinindustrialapplications,itisimperativethattheiraccuracybeunderstood.Thatis,foreachtechnique,rigidmodelingandanalysisoftheinherenterrorsourcesandtheireffectson3Dshapeinferenceareneeded.However,erroranalysisofalltypesofsensorsusedinmachinevisionisbeyondthescopeofthispaper.Ourdiscussionwillbelimitedtothestructuredlight-sensingtechnique,whichwehavesomeexperiencewith.Thus,thegoalofthispaperistoidentifylikelyerrorsourcesandinvestigatetheireffectsoncomputingsurfacepropertiesusingthestructuredlightsensingtechnique.Moreprecisely,errorsinusingstrucfuredlightingtoinfersurfaceorientationandprincipalsurfacecurvaturesareanalysed.Error*ThisresearchwassupportedinpartbyagrantfromtheNationalScienceFoundation,IRI-8908627.~Authorforcorrespondence.boundsarederivedintermsofvarioussystempara-metersanderrorsources.Simulationwasconductedtoverifythecorrectnessoftheanalysis.Structuredlightingisanactivesensingtechniquewhichprojectsaspatiallymodulatedpatterntoencodetheimageobjectforanalysis.~4-15)Traditionalstruc-turedlighttechniquesuseagridpatternandrelyonthetriangulationprincipleintheanalysis,i.e.theobservedpatternismatchedwiththeprojectedone,andthe3Dpositionofthepattern--hencethatoftheencodedsurface--isrecoveredthroughtriangulation.Morerecently,itwasshownthatitispossibletoanalysetheorientationandcurvatureoftheprojectedpatterntoinfertheorientationandcurvatureoftheencodedsurfaces.(lo,11.13,14)Althoughmanyimageanalysistechniqueshavebeendevelopedusingstructuredlighting,noformalmodelingandanalysisoferrorsinstructuredlightinghavebeenattempted,except,maybe,forreferences(16,17).Frobin(16'1v)consideredtheimageprocessifiger-rorinhisreconstructionequationandmodeledsuchanerrorasuncorrelatedGaussiannoiseateachpixellocation.Hethencomputedthe3Dsurfacepositionusingtheleast-squaresminimization,withsensordataweightedbytheinverseoftheobservationerror.How-ever,Frobin'sanalysiswasoncomputing3Dsurfacepositionusingstructuredlightingandtheanalysisresultsarenotapplicabletothesurfaceorientationandcurvaturecomputations.Otherresearchesonerroranalysisincomputervisionweremainlyconcernedwiththeanalysisofthestereopsistechniqueandconsideredonlythequantiza-tionerror31822)DudaandHart~23)gaveabrieftreat-189190Z.YANGandY.F.WANGmentonthesubject.McVeyandLee~2°)performedaworst-caseerroranalysisofthestereopsistechnique,sodidSolina.126~MatthiesandSharer~19~used3DGaussiandistributiontomodelthetriangulationerrorinthestereovision.BlosteinandHuang~18~usedauni-formdistributionerrormodelandderivedtheprob-hbilityprofileoftheabsolutepositionalerror.RodriguezandAggarwalt21~usedanapproachsimilartothatofinreference(18)butgaveaformulationintermsoftherelativeerror.Alltheaboveanalyseswerebasedonasimplifiedstereoconfiguration,inwhichthelinesofsightofthetwocameraswereparallel.VerriandTorre(22)as-sumedaslightlymoregeneralconfigurationandallowedindependentcoordinatesystemstobeasso-ciatedwiththeleftandrightcameras.However,theiranalysisresultswereapplicableonlytotheplaneinthescenewhichwasofthesamedistancetotheoriginsoftheleftandrightcoordinatesys