RECONSTRUCTION OF SCULPTURE FROM UNCALIBRATED IMAGE PROFILES

RobertoCipollaandKwan-YeeK.Wong

DepartmentofEngineering,UniversityofCambridge,TrumpingtonStreet,Cambridge,CB21PZ,UK[cipolla|kykw2]@eng.cam.ac.uk

http://svr-www.eng.cam.ac.uk/∼cipolla

frontier pointcontour generatorABSTRACT

Profilesofasculptureproviderichinformationaboutitsgeometry,andcanbeusedformodelreconstructionunderknowncameramotion.Byexploitingcorrespondencesin-ducedbyepipolartangentsontheprofiles,asuccessfulso-lutiontomotionestimationhasbeendevelopedforthecaseofcircularmotion.Arbitrarygeneralviewscanthenbein-corporatedtorefinethemodelbuiltfromcircularmotion.

1.INTRODUCTION

Profiles(alsoknownasoutlines,orsilhouettes)areoftenadominantfeatureinimages.Theycanbeextractedrel-ativelyeasilyandreliablyfromtheimages,andproviderichinformationaboutboththeshapeandmotionofanob-ject.Classicaltechniques[1]formodelreconstructionandmotionestimationdependonpointand/orlinecorrespon-dences,andhencecannotbeapplieddirectlytoprofiles,whichareviewpointdependent.Thiscallsforthedevel-opmentofacompletelydifferentsetofalgorithmsspecifictoprofiles.Thispaperwillgiveabriefreviewofsomeofthestate-of-artalgorithmsformodelbuildingandmotionestimationfromprofiles.

2.PROFILESOFSURFACES

Profilesareprojectionsofcontourgenerators[2],whichde-pendonboththesurfacegeometryandcamerapositions.Ingeneral,2contourgeneratorsonasurface,associatedwith2differentcamerapositions,willbe2distinctspacecurves,andthusthecorrespondingprofilesontheimagesdonotreadilyprovidepointcorrespondences.Afrontierpoint[2]istheintersectionof2contourgeneratorsandliesonanepipolarplanetangenttothesurface(seefig.1).Itfollowsthatafrontierpointwillprojecttoapointontheprofilewhichisalsoonanepipolartangent[3].Epipolartangen-ciesthusprovidepointcorrespondencesonprofiles,andcanbeexploitedformotionestimation.

1

epipolar tangencysilhouetteepipolar planecamera centerepipoleFig.1.Afrontierpointistheintersectionoftwocontourgeneratorsandliesonanepipolarplanewhichistangenttothesurface.Itfollowsthatafrontierpointwillprojecttoapointontheprofilewhichisalsoonanepipolartangent.

3.MODELRECONSTRUCTION

Theimageprofilesofanobjectproviderichinformationaboutitsshape.Underknowncameramotion,itispossibletoreconstructamodeloftheobjectfromitsprofiles.Forcontinuouscameramotionandsimplesmoothsurfaces,asurfacerepresentationcanbeobtainedfromtheprofilesus-ingtheepipolarparameterization[4].CipollaandBlake[4]developedasimplenumericalmethodforestimatingdepthfromaminimumof3discreteviewsbydeterminingtheosculatingcircleoneachepipolarplane.VaillantandFaugeras[5]developedasimilaralgorithmwhichusestheradialplaneinsteadoftheepipolarplane.BoyerandBerger[6]derivedadepthformulationfromalocalapproximationofthesurfaceuptoorder2,whichallowsthelocalshapetobeestimatedfrom3consecutiveviewsbysolvingapairofsimultaneousequations.In[7],Wongetalproposedtousesimpletriangulationforreconstructionfromprofiles,andshowedthatresultsfromsimpletriangulationarecompa-rabletothosefromBoyerandBerger’smethodwhenthecameramotionissmall.

Alternatively,fordiscretemotionandobjectswithmorecomplexgeometry,avolumetricmodelcanbeobtainedby

anoctreecarvingalgorithm[8].ThistechniqueischoseninSection4forillustratingtheresultsofreconstructionusingthemotionestimatedfromprofiles,andthusisdescribedinmoredetailshere.Initially,theoctreeconsistsofasinglecubeinspacewhichenclosesthemodeltobereconstructed.Thecubeisprojectedontoeachimagesandclassifiedaseither(a)completelyoutside1ormoreprofiles,(b)com-pletelyinsidealltheprofiles,or(c)ambiguous.Ifthecubeisclassifiedastype(c),itissubdividedinto8sub-cubes(hencethenameoctree)eachofwhichisagainprojectedontotheimagesandclassified.Thisprocessisrepeatedun-tilapresetmaximumlevel(resolution)isreached.Cubesclassifiedastype(a)arethrownaway,leavingtype(b)and(c)cubeswhichconstitutethevolumetricmodeloftheob-ject.Surfacetriangles,ifneeded,canbeextractedfromtype(c)cubesusingamarchingcubesalgorithm[9].Theoctreecarvingtechniqueissummarizedinalgorithm1,andanoc-treecarvingsoftwarecanbedownloadedfreeat:http://svr-www.eng.cam.ac.uk/research/vision.Algorithm1OctreeCarvingfromProfilesinitializeacubethatenclosethemodel;whilemaxlevelnotreacheddo

foreachcubeinthecurrentleveldoprojectthecubeontoeachimage;classifythecubeaseither:

(a)completelyoutside1ormoreprofiles,(b)completelyinsidealltheprofiles,or(c)ambiguous;

ifthecubeisclassifiedastype(c)thensubdividethecubeinto8sub-cubes;addthesub-cubestothenextlevel;endifendfor

increasethelevelcount;endwhile

Itisworthnotingthatboththesurfaceandvolumetricmodels,estimatedonlyfromtheprofilesoftheobject,cor-respondtothevisualhulloftheobjectwithrespecttothesetofcamerapositions.Concavitiescannotberecoveredastheyneverappearaspartoftheprofiles.Inorderto”carve”awaytheconcavities,methodslikespacecarving[10,11]shouldbeusedinstead.

4.MOTIONESTIMATION

Apracticalalgorithmformotionestimationfromprofiles,inthecaseofcompletecircularmotion,wasintroducedin[12].In[13],theprofilesfrom(incomplete)circularmotionwereexploitedfortheregistrationofanyarbitrarygeneralview,andacompletesystemformodelacquisitionfromun-calibratedprofilesunderbothcircularandgeneralmotion

2

wasdeveloped.Asummaryofthetechniquesreportedin[12,13]isgivenbelow.

The3mainimagefeaturesincircularmotion,namelytheimageoftherotationaxisls,thehorizonlhandaspecialvanishingpointvx(see[12]fordetails),arefixedthrough-outthesequenceandsatisfy

vx·lh

vx

==

0,andKKTls,

(1)(2)

whereKisthe3×3cameracalibrationmatrix.Thefun-damentalmatrixcanbeparameterizedexplicitlyintermsofthesefeatures[14,12],andisgivenby

θT

F=[vx]×+κtan(lslTh+lhls),2

(3)

whereθistheangleofrotation,andκisaconstantwhich

canbedeterminedfromthecameraintrinsicparameters.AsequenceofNimagestakenundercircularmotion,withknowncameraintrinsicparameters,canhencebedescribedbyN+2motionparameters.Byusingthe2outerepipolartangents[13],theNimageswillprovide2N(or2whenN=2)independentconstraintsontheseparameters,andasolutionwillbepossiblewhenN≥3.

Thecircularmotionwillgenerateawebofcontourgen-eratorsaroundtheobject,whichcanbeexploitedforreg-isteringanynewarbitrarygeneralview.Givenanarbitrarygeneralview,theassociatedcontourgeneratorwillintersectwiththiswebandformfrontierpoints.Ifthecameraintrin-sicparametersareknown,the6motionparametersofthenewviewcanbefixedifthereare6ormorefrontierpointsontheassociatedcontourgenerator.Thiscorrespondstohavingaminimumof3viewsundercircularmotion,eachproviding2outerepipolartangentstotheprofileinthenewgeneralview(seefig.2).

ej0ej1ej2Fig.2.Threeviewsfromcircularmotionprovide6outerepipolartangentstotheprofileinthenewgeneralviewforestimatingitspose.

Themotionestimationproceedsasanoptimizationwhichminimizesthereprojectionerrorsofepipolartan-gents.Forviewiandviewj,afundamentalmatrixFijisformedfromthecurrentestimateofthemotionparame-ters,andtheepipoleseijandejiareobtainedfromtheright

andleftnullspacesofFij.Theouterepipolartangentpointstij0,tij1andtji0,tji1arelocatedinviewiandjrespec-tively(seefig.3).Thereprojectionerrorsarethengivenbythegeometricdistancesbetweentheepipolartangentpointsandtheirepipolarlines,

dijk

==

󰀄,

T2T2(Fijtjik)1+(Fijtjik)2󰀃.2(Fijtijk)2+(Ft)ijijk21

Fijtij0tji0ejiTtFijji0tTjikFijtijktTjikFijtijk

(4)

Fig.4.Top:4imagesfromanuncalibratedsequenceofa

haniwa.Bottom:4imagesfromanuncalibratedsequenceofahumanhead.

djik(5)

tij0eij

Fijtij1tji1tij1TtFijji1Fig.3.Themotionparameterscanbeestimatedbymin-imizingthereprojectionerrorsofepipolartangents,which

aregivenbythegeometricdistancesbetweentheepipolartangentpointsandtheirepipolarlines.

ForasequenceofNimagestakenundercircularmotion,theimageoftherotationaxisandthehorizonareinitializedapproximately,andtheanglesarearbitrarilyinitialized.Thecostfunctionisgivenby1󰀂

Ccm(x)=

4i=1

(i+3,N)2Nmin󰀂󰀂

j=i+1

k=1

Fig.5.Differentviewsofthemodelreconstructedfrom

thehaniwasequenceusingthemotionestimatedfromtheprofiles.

dijk(x)2+djik(x)2,(6)

wherexconsistsoftheN+2motionparameters.

Forarbitrarygeneralmotion,the6motionparameterscanbeinitializedbyroughlyaligningtheprojectionofthe3Dmodelbuiltfromtheestimatedcircularmotionwiththeimage.Thecostfunctionofgeneralmotionforviewjisgivenby

󰀇󰀆󰀁N󰀁2

󰀂2󰀂2󰀆fijk=1dijk(x)+djik(x),(7)Cj(x󰀂)=󰀅i=1󰀁N

4i=1fijwherex󰀂consistsofthe6motionparameters.fijis0ifthebaselineformedwithviewipassesthroughtheobject,otherwiseitis1.

Themotionestimationprocedureissummarizedinal-gorithm2.Fig.5andfig.6showsomeexamplesofrecon-structionfromthemotionestimatedusingprofiles(seefig.4fortheimagesequencesused).

3

Fig.6.Differentviewsofthemodereconstructedfromtheheadsequenceusingthemotionestimatedfromtheprofiles.

Algorithm2MotionEstimationfromProfiles

extracttheprofilesusingcubicB-splinesnakes[4];initializels,lhandtheN−1anglesforthecircularmo-tion;

whilenotconvergeddo

computethecostforcircularmotionusing(6);

updatetheN+2motionparameterstominimizethecost;endwhile

Formtheessentialmatricesfromthefundamentalmatri-cesusingthecalibrationmatrix;

Decomposetheessentialmatricestoobtaintheprojectionmatrices;

Buildapartialmodelusinganoctreecarvingalgorithm;foreacharbitrarygeneralviewdo

initializethe6motionparametersusingthepartialmodelfromcircularmotion;whilenotconvergeddo

computethecostforthegeneralmotionusing(7);updatethe6motionparameterstominimizethecost;endwhileendfor

Refinethemodelusingthenowcalibratedimagesfromgeneralmotion.

[4]R.CipollaandA.Blake,“Surfaceshapefromthede-formationofapparentcontours,”Int.JournalofCom-puterVision,vol.9,no.2,pp.83–112,November1992.[5]R.VaillantandO.D.Faugeras,“Usingextremal

boundariesfor3Dobjectmodeling,”IEEETrans.onPatternAnalysisandMachineIntelligence,vol.14,no.2,pp.157–173,February1992.[6]E.BoyerandM.O.Berger,“3dsurfacereconstruction

usingoccludingcontours,”Int.JournalofComputerVision,vol.22,no.3,pp.219–233,March1997.[7]K.-Y.K.Wong,P.R.S.Mendonc¸a,andR.Cipolla,

“Reconstructionandmotionestimationfromapparentcontoursundercircularmotion,”inProc.BritishMa-chineVisionConference,T.PridmoreandD.Elliman,Eds.,vol.1,Nottingham,UK,September1999,pp.83–92.[8]R.Szeliski,“Rapidoctreeconstructionfromimagese-quences,”ComputerVision,GraphicsandImagePro-cessing,vol.58,no.1,pp.23–32,July1993.[9]W.E.LorensenandH.E.Cline,“Marchingcubes:

ahighresolution3Dsurfaceconstructionalgorithm,”ACMComputerGraphics,vol.21,no.4,pp.163–169,July1987.[10]K.N.KutulakosandS.M.Seitz,“Atheoryofshape

byspacecarving,”Int.JournalofComputerVision,vol.38,no.3,pp.197–216,July2000.[11]A.Broadhurst,T.W.Drummond,andR.Cipolla,“A

probabilisticframeworkforspacecarving,”inProc.8thInt.Conf.onComputerVision,vol.I,Vancouver,BC,Canada,July2001,pp.388–393.[12]P.R.S.Mendonc¸a,K.-Y.K.Wong,andR.Cipolla,

“Epipolargeometryfromprofilesundercircularmo-tion,”IEEETrans.onPatternAnalysisandMachineIntelligence,vol.23,no.6,pp.604–616,June2001.[13]K.-Y.K.WongandR.Cipolla,“Structureandmotion

fromsilhouettes,”inProc.8thInt.Conf.onComputerVision,vol.II,Vancouver,BC,Canada,July2001,pp.217–222.[14]T.VievilleandD.Lingrand,“Usingsingulardisplace-mentsforuncalibratedmonocularvisualsystems,”inProc.4thEuropeanConf.onComputerVision,ser.LectureNotesinComputerScience,B.BuxtonandR.Cipolla,Eds.,vol.1065.Cambridge,UK:Springer–Verlag,April1996,pp.207–216.

5.CONCLUSIONS

Theincorporationofarbitrarygeneralviewsrevealsin-formationwhichisconcealedundercircularmotion,andgreatlyimprovesboththeshapeandtexturesofthe3Dmodels.Sinceonlyprofileshavebeenusedinboththemotionestimationandoctreecarving,nocornerdetectionnormatchingisnecessary.Thismeansthatthealgorithmiscapableofreconstructinganykindofobjects,includingsmoothandtexturelesssurfaces.Experimentsonvariousobjectshaveproducedconvincing3Dmodels,demonstrat-ingthepracticalityofthealgorithm.

6.REFERENCES

[1]O.D.Faugeras,Three-DimensionalComputerVision:

aGeometricViewpoint.Cambridge,MA:MITPress,1993.[2]R.CipollaandP.J.Giblin,VisualMotionofCurves

andSurfaces.Cambridge,UK:CambridgeUniver-sityPress,1999.[3]J.PorrillandS.B.Pollard,“Curvematchingand

stereocalibration,”ImageandVisionComputing,vol.9,no.1,pp.45–50,February1991.

4