and a Linear-Time Length Estimation Algorithm

ComputerScienceDepartmentofTheUniversityofAucklandCITRatTamakiCampus()CITR-TR-55December1999DigitalCurvesin3DSpaceandaLinear-TimeLengthEstimationAlgorithmThomasBülow1,andReinhardKlette2AbstractWeconsidersimpledigitalcurvesina3Dorthogonalgridasspecialpolyhedrallyboundedsets.Thesedigitalcurvesmodeldigitizedcurvesorarcsinthree-dimensionaleuclideanspace.Thelengthofsuchasimpledigitalcurveisdefinedtobethelengthoftheminimum-lengthpolygonalcurvefullycontainedandcompleteinthetubeofthisdigitalcurve.Sofarnoalgorithmwasknownforthecalculationofsuchashortestpolygonalcurve.Thispaperprovidesaniterativealgorithmicsolution,includingapresentationofitsfoundationsandofexperimentalresults.1InstituteofComputerScience,ChristianAlbrechtsUniversity,Preusserstrasse1-9,24105Kiel,Germany2TheUniversityofAuckland,ComputerScienceDepartment,CITR,TamakiCampus(Building731),GlenInnes,Auckland,NewZealandDigitalCurvesin3DSpaceandaLinear-TimeLengthEstimationAlgorithmThomasBulow(1)andReinhardKlette(2)(1)InstituteofComputerScience,ChristianAlbrechtsUniversityPreusserstrasse1{9,24105Kiel,Germany(2)CITR,UniversityofAuckland,TamakiCampus,Building731Auckland,NewZealandAbstract.Weconsidersimpledigitalcurvesina3Dorthogonalgridasspecialpolyhedrallyboundedsets.Thesedigitalcurvesmodeldigitizedcurvesorarcsinthree-dimensionaleuclideanspace.Thelengthofsuchasimpledigitalcurveisdenedtobethelengthoftheminimum-lengthpolygonalcurvefullycontainedandcompleteinthetubeofthisdigi-talcurve.Sofarnoalgorithmwasknownforthecalculationofsuchashortestpolygonalcurve.Thispaperprovidesaniterativealgorithmicsolution,includingapresentationofitsfoundationsandofexperimentalresults.1IntroductionTheanalysisofdigitalcurvesin3Dspaceisofincreasingpracticalrelevanceinvolumetricimagedataanalysis.Adigitalcurveistheresultofaprocess(3Dskeleton,3Dthinningetc.)whichmapscaptured‘curve-like’objectsintowell-deneddigitalcurves(seedenitionbelow).Thelengthofasimpledigitalcurveinthree-dimensionaleuclideanspaceisbasedonthecalculationoftheshortestpolygonalcurveinapolyhedrallyboundedcompactset[8,9].ThispaperpresentsanalgorithmforcalculatingsuchapolygonalcurvewithmeasuredtimecomplexityinO(n),wherendenotesthenumberofgridcubesofthegivendigitalcurve.Anygridpoint(i;j;k)2R3isassumedtobethecenterpointofagridcubewithfacesparalleltothecoordinateplanes,withedgesoflength1,andvertices.Cellsareeithercubes,faces,edgesorvertices.Theintersectionoftwocellsiseitheremptyorajointsideofbothcells.Weconsideranon-emptynitesetKofcellssuchthatforanycellinKitholdsthatanysideofthiscellisalsoinK.SuchasetKisaspecialniteeuclideancomplex[6].Letdim(a)denotethedimensionofacella,whichis0forvertices,1foredges,2forfacesand3forcubes.Then[K;;dim]isalsoacellcomplex[4,6,10]withpropertiessuchas(i)istransitiveonK,(ii)dimismonotoneonKwithrespectto,and(iii)foranypairofcellsa;b2Kwithabanddim(a)+1dim(b)thereexistsacellc2Kwithacb.Cellbboundsacellaiab,andbisapropersideofainthiscase.Twocellsaandbareincidentiaboundsb,orbboundsa.Fig.1.Twocube-curvesin3Dspace.Wedenedigitalcurvesgin3Dspacewithrespecttosuchaeuclideancomplexasspecialsequences(z0;z1;:::;zm)ofcellswhereziisincidentwithzi+1,andjdim(zi)dim(zi+1)j=1,fori+1(modm+1).Thereare(atleast)threedierentoptionswhichmaydependuponanapplicationcontext,oruponapreferenceofeitheragrid-pointmodeloracellularmodelwhicharedualapproaches[2].Letn1.(i)Anedge-curveisasequenceg=(v0;e0;v1;e1;:::;vn;en)ofverticesviandedgesei,for0in,suchthatverticesviandvi+1aresidesofedgeei,for0inandvn+1=v0.Itissimpleieachedgeofghasexactlytwoboundingverticesing.Itfollowsthatavertexoredgeiscontainedatmostonceinasimpleedgecurve.1(ii)Aface-curveisasequenceg=(e0;f0;e1;f1;:::;en;fn)ofedgeseiandfacesfi,for0in,suchthatedgeseiandei+1aresidesoffacefi,for0inanden+1=e0.Itissimplein4,andforanytwofacesfi,fkingwithjikj2(modn+1)itholdsthatiffi\fk6=;thenjikj=2(modn+1)andfi\fkisavertex.(iii)Acube-curveisasequenceg=(f0;c0;f1;c1;:::;fn;cn)offacesfiandcubesci,for0in,suchthatfacesfiandfi+1aresidesofcubeci,for0inandfn+1=f0.Itissimplein4,andforanytwocubesci,ckingwithjikj2(modn+1)itholdsthatifci\ck6=;theneitherjikj=2(modn+1)andci\ckisanedge,orjikj=3(modn+1)andci\ckisavertex.Atubegistheunionofallcubescontainedinacube-curveg.Itisapolyhedrally-boundedcompactsetinR3,anditishomeomorphicwithatorusincaseofasimplecube-curve.2Thispaperdealsexclusivelywithsimplecube-curves.Thecube-curveontheleftofFig.1issimple,andthecube-curveontherightisnot.Thelatter1Thisdenitionisconsistentwith,eg.,thedenitionofa4-curvein[7](seeproposition2.3.3)for2Dgridswhereouredgesare‘hidden’inaneighborhooddenition,orofaclosedsimplepathin[11](seepage7)forundirectedgraphs.2Closedsimpleone-dimensionalgridcontinua[8,9]aredenedsuchthateachcubeofghasexactlytwoboundingfacesing.exampleshowsthatthepolyhedrally-boundedcompactsetgofacube-curvegisnotnecessarilyhomeomorphicwithatorusifeachcubeofthiscube-curveghasexactlytwoboundingfacesing.A(Jordan)curveiscompleteingiithasanon-emptyintersectionwithanycubecontaineding.Denition1.Aminimum-le