您好,欢迎访问三七文档
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-TimeLengthEstimationAlgorithmThomasB ulow(1)andReinhardKlette(2)(1)InstituteofComputerScience,ChristianAlbrechtsUniversityPreusserstrasse1{9,24105Kiel,Germany(2)CITR,UniversityofAuckland,TamakiCampus,Building731Auckland,NewZealandAbstract.Weconsidersimpledigitalcurvesina3Dorthogonalgridasspecialpolyhedrallyboundedsets.Thesedigitalcurvesmodeldigitizedcurvesorarcsinthree-dimensionaleuclideanspace.Thelengthofsuchasimpledigitalcurveisde nedtobethelengthoftheminimum-lengthpolygonalcurvefullycontainedandcompleteinthetubeofthisdigi-talcurve.Sofarnoalgorithmwasknownforthecalculationofsuchashortestpolygonalcurve.Thispaperprovidesaniterativealgorithmicsolution,includingapresentationofitsfoundationsandofexperimentalresults.1IntroductionTheanalysisofdigitalcurvesin3Dspaceisofincreasingpracticalrelevanceinvolumetricimagedataanalysis.Adigitalcurveistheresultofaprocess(3Dskeleton,3Dthinningetc.)whichmapscaptured‘curve-like’objectsintowell-de neddigitalcurves(seede nitionbelow).Thelengthofasimpledigitalcurveinthree-dimensionaleuclideanspaceisbasedonthecalculationoftheshortestpolygonalcurveinapolyhedrallyboundedcompactset[8,9].ThispaperpresentsanalgorithmforcalculatingsuchapolygonalcurvewithmeasuredtimecomplexityinO(n),wherendenotesthenumberofgridcubesofthegivendigitalcurve.Anygridpoint(i;j;k)2R3isassumedtobethecenterpointofagridcubewithfacesparalleltothecoordinateplanes,withedgesoflength1,andvertices.Cellsareeithercubes,faces,edgesorvertices.Theintersectionoftwocellsiseitheremptyorajointsideofbothcells.Weconsideranon-empty nitesetKofcellssuchthatforanycellinKitholdsthatanysideofthiscellisalsoinK.SuchasetKisaspecial niteeuclideancomplex[6].Letdim(a)denotethedimensionofacella,whichis0forvertices,1foredges,2forfacesand3forcubes.Then[K; ;dim]isalsoacellcomplex[4,6,10]withpropertiessuchas(i) istransitiveonK,(ii)dimismonotoneonKwithrespectto ,and(iii)foranypairofcellsa;b2Kwitha banddim(a)+1dim(b)thereexistsacellc2Kwitha c b.Cellbboundsacellai a b,andbisapropersideofainthiscase.Twocellsaandbareincidenti aboundsb,orbboundsa.Fig.1.Twocube-curvesin3Dspace.Wede nedigitalcurvesgin3Dspacewithrespecttosuchaeuclideancomplexasspecialsequences(z0;z1;:::;zm)ofcellswhereziisincidentwithzi+1,andjdim(zi) dim(zi+1)j=1,fori+1(modm+1).Thereare(atleast)threedi erentoptionswhichmaydependuponanapplicationcontext,oruponapreferenceofeitheragrid-pointmodeloracellularmodelwhicharedualapproaches[2].Letn 1.(i)Anedge-curveisasequenceg=(v0;e0;v1;e1;:::;vn;en)ofverticesviandedgesei,for0 i n,suchthatverticesviandvi+1aresidesofedgeei,for0 i nandvn+1=v0.Itissimplei eachedgeofghasexactlytwoboundingverticesing.Itfollowsthatavertexoredgeiscontainedatmostonceinasimpleedgecurve.1(ii)Aface-curveisasequenceg=(e0;f0;e1;f1;:::;en;fn)ofedgeseiandfacesfi,for0 i n,suchthatedgeseiandei+1aresidesoffacefi,for0 i nanden+1=e0.Itissimplei n 4,andforanytwofacesfi,fkingwithji kj 2(modn+1)itholdsthatiffi\fk6=;thenji kj=2(modn+1)andfi\fkisavertex.(iii)Acube-curveisasequenceg=(f0;c0;f1;c1;:::;fn;cn)offacesfiandcubesci,for0 i n,suchthatfacesfiandfi+1aresidesofcubeci,for0 i nandfn+1=f0.Itissimplei n 4,andforanytwocubesci,ckingwithji kj 2(modn+1)itholdsthatifci\ck6=;theneitherji kj=2(modn+1)andci\ckisanedge,orji kj=3(modn+1)andci\ckisavertex.Atubegistheunionofallcubescontainedinacube-curveg.Itisapolyhedrally-boundedcompactsetinR3,anditishomeomorphicwithatorusincaseofasimplecube-curve.2Thispaperdealsexclusivelywithsimplecube-curves.Thecube-curveontheleftofFig.1issimple,andthecube-curveontherightisnot.Thelatter1Thisde nitionisconsistentwith,eg.,thede nitionofa4-curvein[7](seeproposition2.3.3)for2Dgridswhereouredgesare‘hidden’inaneighborhoodde nition,orofaclosedsimplepathin[11](seepage7)forundirectedgraphs.2Closedsimpleone-dimensionalgridcontinua[8,9]arede nedsuchthateachcubeofghasexactlytwoboundingfacesing.exampleshowsthatthepolyhedrally-boundedcompactsetgofacube-curvegisnotnecessarilyhomeomorphicwithatorusifeachcubeofthiscube-curveghasexactlytwoboundingfacesing.A(Jordan)curveiscompleteingi ithasanon-emptyintersectionwithanycubecontaineding.De nition1.Aminimum-le
本文标题:and a Linear-Time Length Estimation Algorithm
链接地址:https://www.777doc.com/doc-3397719 .html