Line-based 3D Reconstruction of Wiry Objects

18thComputerVisionWinterWorkshop

WalterG.Kropatsch,FuensantaTorres,GeethaRamachandran(eds.)Hernstein,Austria,February4-6,2013

Line-based3DReconstructionofWiryObjects

ManuelHofer,AndreasWendel,HorstBischofInstituteforComputerGraphicsandVisionGrazUniversityofTechnology,Austria

{hofer,wendel,bischof}@icg.tugraz.at

Abstract.Man-madeenvironmentscontainmanyweaklytexturedsurfaceswhicharetypicallypoorlymodeledinsparsepointreconstructions.Mostno-table,wirystructuressuchasfences,scaffolds,orpowerpylonsarenotcontainedatall.Thispaperpresentsanovelapproachforgeneratingline-based3Dmodelsfromimagesequences.Initially,camerapositionsareobtainedusingconventionalStructure-from-Motiontechniques.Inordertoavoidexplicitmatchingof2Dlinesegmentsinthevariousviewsweexploittheepipolarconstraintsandgenerateaseriesof3Dlinehypotheses,whicharethenveri?edandclusteredtoobtainthe?nalresult.Weshowthatthisapproachcanbeusedtodensifyvarioussparseoccupiedpointcloudsofurbanscenesinordertoob-tainameaningfulmodeloftheunderlyingstructure.

1.Introduction

Generating3Dmodelsfromasetofimageshasbecomeawidelystudied?eldofresearchoverthelastfewyears.Themajorityofavailablealgorithmsisbasedonpointcorrespondencesbetweenmulti-pleviewsusingvariouslocaldescriptorssuchastheScale-InvariantFeatureTransform(SIFT)

[13]inor-dertoobtaina3Dpointcloudwhilesimultaneouslyestimatingthecameraparameters.ThisprocessiscalledStructure-from-Motion(SfM).Thedensityoftheresultingpointcloudhighlydependsontheamountoftextureavailableintheimages.There-fore,point-basedSfMmayfailinman-madeenvi-ronmentswithalowamountofdistinctiveinterestpoints(e.g.urbanscenes,indoorscenes).Totacklethisissue,manyline-basedapproacheshavebeenpresentedovertheyears,duetothefactthatespe-ciallyman-madeobjects(e.g.buildings)canusuallyberepresentedbyasetof3Dlinesegments.Similar

Figure1.Twoexamplesforwirystructures.Theleftim-ageshowsapowerpylonandtherightimageascaffoldinfrontofahouse.

totraditionalSfMitisusuallynecessarytomatch2Dlinesegmentsfromvariousviewstotriangulatea3Dlinesegment.Thiscanbedoneusingappearance-basedsimilaritymeasures,e.g.normalized-cross-correlation(NCC)orlinedescriptors[12,21],whichcanbecombinedwithadditionalgeometriccon-straints[3].Sincetheendpointsofmatchedlineseg-mentsusuallydonotcorrespondtoeachotherduetoinexactlinesegmentdetectionorocclusions,creat-ing3Dlinesegmentsfrommatched2Dlinesismuchmoredif?cultthantraditionalpoint-to-pointmatch-ing.

Mostofthepreviousapproachesrelyonanaccu-ratelinematchingprocessbetweenthevariousviewsusingsomeappearance-basedsimilaritymeasures.Thisusuallyworks?neifthelinesarelocatedonaplanarsurfacewithconstantbackground,forin-stancewhenmatchingwindowframes.However,whendealingwithwirystructuressuchaspowerpy-lons,bridgesorscaffolds(seeFigure1forsomeex-amples),appearance-basedmatchingishardlypos-sibleduetochangingsurroundingsofthelineseg-mentsindifferentviews(seeFigure2).Wepresentanapproachwhichisespeciallydesignedtohandlesuchcasesbutalsoperformswellonsolidobjects.

内容需要下载文档才能查看 内容需要下载文档才能查看

Figure2.Anexamplewerenoappearancebasedlinematchingcanbeperformed.Notethatcorrespondinglinesegmentshavedifferentsurroundingsinbothviews(yel-lowlines).

2.RelatedWork

Inthefollowingwepresentselectedpapersfromthe?eldofline-based3Dreconstruction.Westartwithanoverviewofappearance-basedmethodswhichcannotdirectlybeappliedtoourproblembutsharesomeideaswithourapproach.

Baillardetal.[1]presentedamethodwhichmakesuseoftheepipolarconstraintbyestimatinglinecorrespondencesalongtheepipolarbeam.To?ndthecorrectmatchtheyevaluatetheNCCscoreforcandidatelinesusingpatchesaroundthelineseg-ments.Theestimated3Dlinesegmentistheinter-sectionofthehalf-planesthroughthelinesofsightofthetwoendpointsinbothviews.Theyfurtherver-ifytheirhypothesesbyminimizingthereprojectionerrorusingthetrifocaltensor[6].

Bayetal.[2]useoptionalregionmatchesinad-ditiontolinematchesbasedoncolorhistogramsinordertoestablishaninitialsetofcandidates.Theyapplyatopological?lterinordertoremovewrongcandidatesandincreasethecandidatesetbyaddingunmatchedlinesegmentswhich?ttothetopologicalstructureofthealreadymatchedhypotheses.Theyfurtherestimatetheepipolargeometryusingcopla-narsubsetsoftheircandidateset.Veryaccuratere-sultsarereported,evenforsparselytexturedscenes.Inordertogenerate3Dlinemodelsforurbanscenes,Schindleretal.[16]proposedanapproachwhichtakesvanishingpointinformationintoac-count.Theyassumethatrelevantedgesarelo-catedalongmutuallyorthogonalvanishingdirectionswhichreducesthedegreesoffreedomfor3Dlinees-timation.Theirapproachdeliverspleasantresultsforurbanstructuresbutunfortunatelyislimitedtopic-turestakenatnear-groundlevelduetotheirassump-tions.

AnotherapproachpresentedbyKimetal.[8]isbasedontheintersectioncontextofcoplanarline

pairs.TheymatchlineintersectioncontextfeaturesacrossmultipleviewsusingNCCassimilaritymea-sureandrejectfalseintersectionsusingcoplanarityconstraintsonthecorrespondinglinesegments.Theproposedmethodworkswellforawiderangeofsce-nariosevenwhenonlylittletextureisavailable.Unfortunately,alloftheseappearance-basedap-proachesusuallydonotperformwellforwirystruc-tures,sincetheytechnicallydonotmatchthelineitself,butratheritssurroundings.Inourcase,ex-plicitmatchingmaybeimpossible,sincetheeverchangingbackgroundisnotcoplanarwiththelineandoftenveryfarawayfromtheobjecttoberecon-structed.Inordertocreate3Dmodelswithouttheneedofexplicitlinematching,Jainetal.[10]de-velopedasweepingbasedapproachwhichde?nestheunknown3Dlocationsoftheendpointsof2Dlinesegmentsasrandomvariables.Theyestimate3Dlinehypothesesbygeneratingallpossibleend-pointlocationsinacertaindepthinterval(assumingknowncameraintrisicsandextrinsics)andkeeptheonewiththehighestscorebasedonthegradientim-agesofmanyneighboringviews.Hence,theycreatea3Dlineforevery2Dlineineveryview.Inordertodeleteoutliersandclustercorrespondinglineseg-mentstogether,theygroup3Dlinesegmentswhichliecloseinspaceanddiscardallsegmentswhichdonothaveatleastonesuchneighbor.Theyalsoper-formanoptimizationbasedon2Dlineconnectionsusingloopybeliefpropagationtoenforceconnected3Dlines.Eventhoughtheirapproachdeliversveryaccurateresultsandisveryrobustagainstnoiseandpartialocclusions,itisveryslowcomparedtoprevi-ousapproaches.

Inourapproachwebuildupontheprinciplespre-sentedin[10]butuseadifferentmatchingstrat-egy.Insteadofusingatimeconsumingsweepingapproachwegeneratehypothetical3Dlinesegmentsusingepipolarconstraints,whichdrasticallylimitsthenumberofpossible3Dlocationsforeach2Dlinesegment.Wewillshowthatthisleadstoasigni?cantperformanceincreasewhilestillcreatingaccuratere-sults.

3.SparseStructure-from-Motion

GivenanunorderedsetI={I1,...,In}ofnimagesandthecorrespondingcamerasC={C1,...,Cn}wewanttogenerateasetof3DlinesegmentsS={S1,...,Sk}.Sincewedonotper-formexplicitlinematchingandline-basedrelative

poseestimationthecamerashavetobeknownbe-forehand.Forthispurposeweuseapoint-basedSfMsystem.Thislimitstheapplicationtosceneswhereinterestpointscanbefound,butwehaveseenthatwecanusually?ndenoughcorrectcorrespondencesforanaccuraterelativeposeestimationintheback-groundofwirystructures.

WefollowtheapproachofWendeletal.

[20]andIrscharaetal.[9]whichenablesustoperformsparseSfMforunorderedimagesets.Thethreenec-essaryprocessingstepsarefeatureextraction,featurematching,andgeometryestimation.Inthe?rststepweextractSIFT[13]featuresfromallimages.SIFThasbeenshowntoworkwellingeneralscenes[14],butitalsoworkssurprisinglywellinscenarioswithwirystructures.Thereasonisthatmatchesareob-tainedeitherinthebackground,orintheforegroundincaseofahomogeneousbackgroundsuchassky.Afterwards,wematchtheresultingkeypointdescrip-torsbetweenallpossibleimagepairsandperformageometricveri?cationprocedureusingtheFive-Pointalgorithm[15].Inordertoeliminatepossi-bleoutliersweuseRANSAC[5]forrobustestima-tion.Theresultingpairwisereconstructionsarethenmergedtoobtainasparsereconstructionofthescene.Finally,bundleadjustment[17]isappliedtomini-mizetheglobalreprojectionerroroverallmeasure-ments.See[19]and[7]forfurtherdetails.

AsaresultweknowtherelativepositionsofallcamerasCinacommoncoordinateframe,andwecanthusproceedtothetaskof3Dlinesegmentesti-mation.

4.Reconstructionof3DLineSegments

Ouralgorithmconsistsofthreesteps:2Dlineseg-mentdetectionextractslinesegmentsfromeachin-putimage,3Dlinesegmenthypothesesgenerationtriestoestimatethe3Dpositionofthesesegments,and?nally3Dlinegroupingandoutlierremovalmergescorrespondingsegmentsfromdifferentviewsandremovesincorrectestimates.Inthefollowingsectionsthesestepswillbeexplainedindetail.

4.1.2DLineSegmentDetection

Inordertogeneratetriangulated3Dlinesegmentsfromasetofimages,we?rsthavetoapplyalinesegmentdetectionalgorithmontoourinputimages.WeemploytheLineSegmentDetector(LSD)[18]algorithmtoextractallrelevantlinesegmentswithasfewincorrectdetectionsaspossible.Theauthors

Figure3.LineSegmentDetection.ThelinesegmentsextractedusingtheLSD[18]algorithmarevisualizedinpseudo-colors.Theunderlyingwirystructureisrepre-sentedverywell,exceptforafewoutliersduetonoisygradients,causeforinstancebygrass.

reporttheiralgorithmtobesigni?cantlyfasterthanpreviousmethodswhileproducingveryaccuratere-sults.Theirapproachisbasedonthegroupingofpointswithahighgradientandsimilarlevellinean-gle,followedbyaleastsquaresline?t.AlldetectionsarevalidatedusingtheHelmholtzprinciple[4]whichprovestobeveryeffectiveforthegeneralcase.Fig-ure3showsthedetectedlinesegmentsforapowerpylonimage.

4.2.3DLineSegmentHypothesesGenerationAssumingnofalsedetectionsinthepreviousstep,every2DlinesegmentfromimageIicorrespondstoa3Dlinesegmentinworldspace.Sincewecannotperformanexplicitappearance-basedmatchingpro-cedureandtriangulation,wehavetoestimatethecor-rect3Dlocationofeachsegmentinadifferentway.AsweknowtheprojectionmatrixPiofthecam-era,http://wendang.chazidian.comingtheepipo-larlinesepandeqde?nedbythetwoendpointspandqofacertainlinesegmentlinviewi,wecanlimitthepossiblematchesforltothoselineseg-mentswhoseendpointslieonepandeqrespectively.Inpracticeitisunlikelythatwewill?ndanexactmatchwithbothendpointsbeinglocatedexactlyontheepipolarlines,e.g.duetoimpreciselinedetectionorocclusions.Thereforeweextendallcandidateseg-mentswhichoverlapwiththeregionbetweenthetwoepipolarlinestoin?nity(fromlinesegmentstoac-tuallines)andintersectthemwithepandeqinordertogeneratehypotheticalmatches.Thisenablesusto

?ndcorrectmatchesevenifthe

currentlinesegmentisshorterorlongerinIj(seeFigure4).Foreveryhypothesiswecreatea3DlinesegmentLbytrian-gulatingthetwocorrespondingendpointpairsfromthetwoviewsIiandIj.

Sinceweusuallyhavemorethanonehypothesisforeach2Dlinesegment(becausetheepipolarlinesdonotprovideenoughinformationtoperformexactmatching),wehavetodeterminewhichoneiscor-rect.Thereforeweadoptagradientbasedscoringapproachsimilarto[11,10].Wethenbackprojecteachi3DlinesegmentLintoallneighboringviewsN(I)ofIiwithacameracentercloserthanacer-taindistancedencesmallerthancandanabsoluteviewinganglediffer-dangtothecurrentcameraCi.ForeachcamerawecomputeasetofmeasurementpointsMalongandperpendiculartothebackprojectedline,andcomputetheimagegradient-basedscore

s(L)=

1

??

?????I(x)??|N(I)|

e?(λ·dist(x,L)max)2

I∈N(Ii)x∈M(I)

|M(I)|

(1)

forevery3DlinesegmentL,where?I(x)de-notestheimagegradientatpositionx,dist(x,L)istheperpendicularEuclideandistancetothebackpro-jectedlineinthecurrentimageIanddistmax(L)denotesthemaximumdistancebasedonthecon?g-urationofthemeasurementpoints.Assumingthatlinesegmentscorrespondtohighgradientareasinimages,thismethodensuresthatwechoosethehy-pothesiswhich?http://wendang.chazidian.comingthisformulawegivemoreweighttomeasurementpointswhichareclosertothebackprojectedline,andlessweighttothoseperpendiculartoitdependingonthedistance.AnillustrationisgiveninFigure5.

Aftercomputingthescoreforeachhypothesiswechoosetheonewithmaximumscore,denotedasLbest,whichisthenaddedtoour3DlinesegmenthypothesessetH.Sincewegenerate3Dlineseg-mentsforallviewsindividually,weendupwithaquitelargehypothesessetwhichhastobepruned.Figure6showsanexamplefora3Dlinemodelbe-foregroupingandoutlierremoval.

4.3.3DLineGroupingandOutlierRemovalItispossiblethatthecorrectmatchesfor2Dlinesegmentsarenotamongthecandidates,forinstancebecausethelinesegmentsarenotredetectedinanyneighboringview,andthereforewehavetoremovepossibleoutliers.Theoutlierremovalprocessgoeshandinhandwiththelinegroupingstepwhichhastobeperformedinordertoremovemultipledetec-tions.Sincewematchandtriangulatethe2Dline

Figure5.Theleftimageshowsthegradientmagnitudesfromapowerpylonimagewithabackprojected3Dlinehypothesisshowninred.Therightimageshowsaclose-upofthelinesegmentwiththesetofmeasurementpointsMillustratedasyellowlines.Theweightedsumofthegradientmagnitudesoverallmeasurementpointsiscom-putedandthendividedbythenumberofpointsinordertocomputethescoreforthisview.Theaveragescoreoverallneighboringviewsisthenusedtoevaluatethebesthy-pothesis(seeEquation1).

Figure6.3Dlinesegmenthypothesesbeforethegroup-ingandoutlierremovalprocedure.Ourapproachgener-ates71538segmentsfrom106views.Notethatthereisalargenumberofoutliersduetoincorrectmatches,butthepowerplyonwhichappearsintheimageryisclearlyrecognizable.

segmentsindividuallyforeveryview,thesame3Dlinemightbegeneratedinmultipleviews.Assumingacorrectmatchingprocedure,allthehypothesesinHwhichcorrespondtothesame3Dlineshouldbelocatedcloseinspace.Hence,alineclusteringalgo-rithmisperformedinordertogeneratethe?nal3Dlinemodel.

Inordertoremoveincorrectlytriangulated3Dlinesegmentsandclustercorrespondingsegments,weadopttheideaofspatialproximitybasedgroupingfrom[10].First,weorderthehypothesessetHby

内容需要下载文档才能查看

Figure4.WematchthelinesegmentLinviewIiwithlinesegmentsfromviewIjusingitsepipolarlinesepandeq.Thebluelinesegmentsarepossiblecandidatematchesbecauseoftheiroverlapwiththeregionbetweenthetwoepipolarlines.Theendpointsofthehypotheticallinesegmentsusedfortriangulationareshownasbluedots.Theorangelinesegmentdoesnotoverlapwiththeepipolarlinesandisthereforenotconsideredtobeapossible

match.

Figure7.Togroupcorresponding3Dlinesegmentsto-gether,thetruesegmentL(green)isexpandedby10%ineachdirection.Allotherlinesegmentswithbothend-pointswithinacylinderofradiusr,de?nedbythenewendpoints,areconsideredtobeinthesamegroupasL(bluelines).Theredlinedoesnotbelongtothegroup,becauseoneofitsendpointsisoutsidethecylinder.

Figure8.Afterthegroupingproceduremostoftheoutliershavebeensuccessfullyremovedresultinginanaccurate3Dmodel(1381linesegments).

scoreindescendingordertostartgroupingwithlineswhicharebestalignedwiththeimagegradients.ForeachlineLm∈Hwede?neacylinderofa?xedradiusrbyexpandingthecentralaxisofthelineseg-mentby10%inbothdirections.Wethentryto?ndalllinesegmentsLn,n=mwherebothendpointsarelocatedwithinthecylinder

(Figure7).

Ifthe?nallinegroup(includingLm)hasatleasthminmembersweconsiderittobevalidandexcludealllinesegmentsinthegroupfromfurthergrouping,otherwiseLmisremovedfromHandwecontinuewiththenextbesthypothesis.

Aftertheclusteringstep,eachgroupisreplacedwithonesinglelinesegmentforour?nal3DlinesegmentsetS.Tode?nethislinewe?rstcomputethecenterofgravityofalllinesegmentendpointsfromthegroup.Afterwardsweperformasingularvaluedecompositionofthescattermatrixcontainingallendpointsandtaketheeigenvectorcorrespondingtothemaximumeigenvalueasnewlinedirection.Wenowprojectallendpointsontothenewlineandaddthelinesegmentde?nedbythetwooutmostpointstoS.Figure8illustratestheoutcomeofthegrouping

procedure.NotethatcomparedtoFigure6mostoftheoutliershavebeensuccessfullyremoved.

5.Experiments

Intheprevioussectionwehavealreadyshownaresulting3Dmodelofapowerpylon.Inthissec-tionwewanttopresentadditionalresultsand?nallycompareouralgorithmto[10]usingoneoftheirtest-cases.

5.1.ParameterSelection

Thevariousstepsofourapproachrequireasetofparametersinordertogeneratepleasantresults.Mostofthemarevalidforalargenumberofscenar-iosandthereforedonotneedtobeespeciallytuned.Thelinesegmentdetectionalgorithm(LSD[18])doesnotneedparameters.Inordertoeliminateout-liersandspeedupthecomputationwereject2Dlinesegmentssmallerthan1%ofthediagonallengthoftheimageinpixels,whichisusuallysuf?cienttocap-turetheunderlyingstructureofourimages.

Duringhypothesesgenerationweneedtodeter-