2024年4月21日发(作者：魔声钻石之泪耳机)

TowardsInternet-scaleMulti-viewStereo

YasutakaFurukawa

1

1

GoogleInc.

Abstract

Thispaperintroducesanapproachforenablingexist-

ingmulti-viewstereomethodstooperateonextremelylarge

nideaistodecom-

posethecollectionintoasetofoverlappingsetsofphotos

thatcanbeprocessedinparallel,andtomergetheresult-

erlappingclusteringproblem

isformulatedasaconstrainedoptimizationandsolvedit-

gingalgorithm,designedtobeparallel

andout-of-core,incorporatesrobustfilteringstepstoelim-

inatelow-qualityreconstructionsandenforceglobalvisi-

roachhasbeentestedonseveral

,includingone

withovertenthousandimages,yieldinga3Dreconstruc-

tionwithnearlythirtymillionpoints.

BrianCurless

2

1,2

RichardSzeliski

3

2

UniversityofWashington

3

MicrosoftResearch

sereconstructionofPiazzaSanMarco(Venice)

from13,703imageswith27,707,825reconstructedMVSpoints

(furtherupsampledx9forhighqualitypoint-basedrendering).

uction

Thestateoftheartin3Dreconstructionfromimageshas

dwith

theexplosionofimageryavailableonlineandadvancesin

computing,wehavetheopportunitytorunreconstruction

,wecannowattemptto

,everybuilding,landscape,

and(static)objectthatcanbephotographed.

Themostimportanttechnologicalingredientstowards

,

SIFT[17])provideaccuratecorrespondences,structure-

from-motion(SFM)algorithmsusethesecorrespondences

toestimateprecisecamerapose,andmulti-view-stereo

(MVS)methodstakeimageswithposeasinputandproduce

dense3Dmodelswithaccuracynearlyonparwithlaser

scanners[22].Indeed,thistypeofpipelinehasalreadybeen

demonstratedbyafewresearchgroups[11,12,14,19],

withimpressiveresults.

Toreconstructeverything,onekeychallengeisscala-

bility.

1

Inparticular,howcanwedevisereconstructional-

,onthemillions

?

areotherchallengessuchashandlingcomplexBRDFsand

lightingvariations,whichwedonotaddressinthispaper.

1

There

GivenrecentprogressonInternet-scalematchingandSFM

(notablyAgarwaletal.’sRome-in-a-dayproject[1]),wefo-

cusoureffortsinthispaperonthelaststageofthepipeline,

i.e.,Internet-scaleMVS.

MVSalgorithmsarebasedontheideaofcorrelating

measurementsfromseveralimagesatoncetoderive3D

Salgorithmsaimatrecon-

structingaglobal3Dmodelbyusingalltheimagesavail-

ablesimultaneously[9,13,20,24].Suchanapproachisnot

d,itbecomes

importanttoselecttherightsubsetofimages,andtocluster

themintomanageablepieces.

Weproposeanovelviewselectionandclusteringscheme

thatallowsawideclassofMVSalgorithmstoscaleupto

edwithanewmergingmethod

thatrobustlyfiltersoutlow-qualityorerroneouspoints,we

demonstrateourapproachrunningforthousandsofimages

temisthefirstto

demonstrateanunstructuredMVSapproachatcity-scale.

Weproposeanoverlappingviewclusteringproblem[2],

inwhichthegoalistodecomposethesetofinputimages

pisimportant

fortheMVSproblem,asastrictpartitionwouldundersam-

ustered,we

applyastate-of-the-artMVSalgorithmtoreconstructdense

3Dpoints,andthenmergetheresultingreconstructionsinto

1

filteringalgo-

rithmsareintroducedtohandlereconstructionerrorsand

thevastvariationsinreconstructionqualitythatoccurbe-

tweendistantandnearbyviewsofobjectsinInternetphoto

filtersaredesignedtobeout-of-coreand

parallel,inordertoprocessalargenumberofMVSpoints

effivisualizationsofmodelscontaining

tensofmillionsofpoints(seeFigure1).

dWork

ScalabilityhasrarelybeenaconsiderationinpriorMVS

algorithms,aspriordatasetshavebeeneitherrelatively

small[22],avideosequence

whichcanbedecomposedintoshorttimeintervals[19]).

Nevertheless,somealgorithmslendthemselvesnaturally

icular,severalalgorithmsoperate

bysolvingforadepthmapforeachimage,usingalocal

neighborhoodofnearbyimages,andthenmergetheresult-

ingreconstructions[11,12,18,19].Eachdepthmapcan

r,the

depthmapstendtobenoisyandhighlyredundant,leading

ore,thesealgorithms

typicallyrequireadditionalpost-processingstepstoclean

upandmergethedepthmaps.

ManyofthebestperformingMVSalgorithmsinstead

reconstructaglobal3Dmodeldirectlyfromtheinputim-

ages[9,13,20,24].Globalmethodscanavoidredun-

dantcomputationsandoftendonotrequireaclean-uppost-

process,eptionisJancoseketal.

[14]whoachievescalabilitybydesigningthealgorithmout-

r,rast,

weseekanout-of-corealgorithmthatisalsoparallelizable.

Withdepth-mapbasedMVSalgorithms,severalauthors

havesucceededinlarge-scaleMVSreconstructions[18,

19].Pollefeysetal.[19]presentareal-timeMVSsys-

timateadepthmap

foreachinputimage,reducenoisebyfusingnearbydepth

maps,andmergetheresultingdepthmapsintoasingle

ketal.[18]proposeapiece-wise

planardepthmapcomputationalgorithmwithverysimilar

r,bothmethodshave

beentestedonlyonhighlystructured,street-viewdatasets

obtainedbyavideocameramountedonamovingvan,and

nottheunstructuredphotocollectionsthatweconsiderin

thispaper,whichposeadditionalchallenges.

Besidesscalability,variationinreconstructionqualityis

anotherchallengeinhandlinglargeunorganizedimagecol-

lections,assurfacesmaybeimagedfrombothcloseupand

eetal.[12]proposedthefirstMVSmethod

appliedtoInternetphotocollections,whichhandlesvaria-

tioninimagesamplingresolutionsbyselectingimageswith

etal.[10]select

imagesatdifferentbaselinesandimageresolutionstocon-

SFM point

P

1

SFM points

P

3

P

4

image

images

P

2

cluster

{P

1

,P

2

, ...}

P

Images

5

{I

1

,I

2

, ...}

C

I

I

4

1

I

2

I

Image clusters

1

3

C

2

{C

1

,C

2

, ...}

wclusteringalgorithmtakesimages{I

visibility

}

information

.

{V

i

},SFM

points{P

j

},andtheirassociated

j

},then

producesoverlappingimageclusters{C

k

thesemethodshandlevariation

ech-

niquesmaybeusedinconjunctionwiththemethodspro-

posedhere,butthemajordifferenceinourworkisthatwe

alsohandlethevariationinapost-processingstep,when

thatsomepriordepth

mapmergingalgorithmstakeintoaccountestimatesofun-

,bytakingweightedcombinationsofdepth

samplestorecoveramesh[4,25].Whilesuchapproaches

canhandlenoisevariation,wefindtheydonotperformwell

forlargeInternetphotocollections,whereresolutionvaria-

tionisamajorfactor,becausecombininghighandlowreso-

lutiongeometriesinthestandardwayswilltendtoattenuate

eadproposeasimplemerg-

ingstrategythatfiltersoutlowresolutiongeometry,which

wehavefoundtoberobustandwell-tailoredtorecovering

apoint-basedmodelasoutput.

w-

clusteringalgorithmisexplainedinSection2,anddetails

oftheMVSpointmergingandrenderingaregiveninSec-

mentalresultsareprovidedinSection4and

lementationof

theproposedview-clusteringalgorithmisavailableat[6].

ustering

Weassumethatourinputimages{I

algorithmtoyieldcamera

i

}havebeenpro-

cessedbyanSFMposesanda

sparsesetof3Dpoints{P

j

},eachofwhichisvisibleina

setofimagesdenotedbyV

j

.WetreattheseSFMpointsas

sparsesamplesofthedensereconstructionthatMVSwill

,theycanbeusedasabasisforviewclus-

ecifically,thegoalofviewclusteringisto

find(anunknownnumberof)overlappingimageclusters

{C

k

}suchthateachclusterisofmanageablesize,andeach

SFMpointcanbeaccuratelyreconstructedbyatleastone

oftheclusters(seeFigure2).

mFormulation

Theclusteringformulationisdesignedtosatisfythefol-

lowingthreeconstraints:(1)redundantimagesareexcluded

fromtheclusters(compactness),(2)eachclusterissmall

enoughforanMVSreconstruction(sizeconstraint);and