Implementation and complexity of the watershed-from-markers algorithm computed as a minimal

Watershed-from-MarkersAlgorithmComputedasaMinimal

CostForest

PetrFelkel

VrVisCenter,Lothringerstraße.16/4,A-1030Vienna,Austria,www.vrvis.at,contactaddress:felkel@vrvis.at

MarioBruckschwaigerandRainerWegenkittl

TIANIMedgraphGmbH,Campus21,LiebermannstraßeA01304,A-2345BrunnamGebirge,Austria,www.tiani.com

Abstract

Thewatershedalgorithmbelongstoclassicalalgorithmsinmathematicalmorphology.Lotufoetal.1publishedaprin-cipleofthewatershedcomputationbymeansofaniterativeforesttransform(IFT),whichcomputesashortestpathforestfromgivenmarkers.Thealgorithmitselfwasdescribedfora2Dcase(image)withoutadetaileddiscussionofitscomputationandmemorydemandsforrealdatasets.

AsIFTcleverlysolvestheproblemofplateausandasitgivespreciseresultswhenthinobjectshavetobesegmented,itisobvioustousethisalgorithmfor3Ddatasetstakinginmindtheminimizingofahighermemoryconsumptionforthe3DcasewithoutloosinglowasymptoticaltimecomplexityofOmC(andalsotherealcomputationspeed).ThemaingoalofthispaperisanimplementationoftheIFTalgorithmwithapriorityqueuewithbucketsandcarefultuningofthisimplementationtoreachasminimalmemoryconsumptionaspossible.

ThepaperpresentsfivepossiblemodificationsandmethodsofimplementationoftheIFTalgorithm.Allpresentedim-plementationskeepthetimecomplexityofthestandardpriorityqueuewithbucketsbutthebestoneminimizesthecostlymemoryallocationandneedsonly19–45%ofmemoryfortypical3Dmedicalimagingdatasets.

MemorysavingwasreachedbyanIFTalgorithmsimplification,whichstoresmoreelementsintemporarystructuresbuttheseelementsaresimplerandthusneedlessmemory.

Thebestpresentedmodificationallowssegmentationoflarge3Dmedicaldatasets(upto512512680voxels)with12-or16-bitspervoxeloncurrentlyavailablePCbasedworkstations.

1.Introduction

Theideabehindapplicationofwatersheds(WS)inagrey-scaleimagesegmentationisverysimple.Theaimistofindobjectsandtheirborders.Astheobjectbordersarelociofthehighestgradientintheimage,thegradientimageistakenasaninputheightfield(topographicalimage)thatisstepbystepimmersedintowater.Duringtheprocessofimmersion,waterformscatch-mentbasins,whichcorrespondinanidealcasetotheobjects.Thecreationofcatchmentbasinsbeginsinlocalminimaofthegradientimage.Whenthesecatchmentbasinsmeet(touch)adamisbuilttopreventthemtojoin.Thesedamsformthenthewatershedlines,whichshouldcorrespondtoobjectboundaries.Thewatershedalgorithmsstartinginlocalminimasufferfromoversegmentationifappliedtoimageswithnoise,asmen-tioned,e.g.,bySonka2.Foraregiongrowingitisbettertouseawatershedfrommarkers,wherethecreationofcatchmentbasinsbeginsinthesemarkersandonlyagivennumberofob-jectsarefound.

Averyinterestingalgorithmforcomputationofwatershedsfromgivenmarkersbymeansoftheiterativeforesttransform(IFT)withapriorityqueuehasbeenproposedbyLotufoand

Falcao1butwithoutdetailedimplementationissues.Anadvan-tageofthisalgorithmisitshigherresolution,asitcancorrectlysegmentblobsconnectedbyanone-pixelthickregion.Thetuningoftheimplementationofthepriorityqueueviabucketstoreachasminimalmemoryconsumptionaspossible,keepingthespeedofthestandardpriorityqueuewithbucketsistheaimofthispaper.Thebestoffivepresentedalgorithmvariantsneedsonlyaboutonethirdofmemoryinatypicalcaseof3Dmedicalimagingdatasets.

Thepaperhasthefollowingstructure.Section2describesbasicterms,Section3theIFTalgorithmasproposedbyLotufoandFalcao1,Section4describesfivemodificationsoftheIFTalgorithm,Section5thedatasetsandtheworstandaveragecaseanalysisofthealgorithms.Conclusionsandthefutureworkfol-lowinSection6.

2.Definitionsandnotations

LetD(x,y,z)beavolumetricdatasetofsizexyzvoxels.LetthisdatasetbetakenasanundirectedgraphGVEwithnodesetVofsizenxyzandarcsetEofsizemxyz1

2Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest

xy1zx1yz,definedbya6-connectivityofneighboring

voxels.

Letwpqbeaweightofthearcpqbetweentheneigh-boringvoxelsandfuavaluestoredinvoxel(node)u.Thenonnegativeintegerarcweightisforthewatershedalgorithmdefinedaswpqfpfq.Notethatthisformulationofthearcweightgivesaverysimpleapproximationofacom-plete3Dgradientasknownincommonsensebutworkscor-rectlywithinthisalgorithm.LetCbeamaximalarcweightinthedataset.

Theshortest-pathforestproblemfindsforeachgraphnodetheshortestpathconnectingittoitsnearestrootnode.Incaseofthewatershedsfrommarkers,therootnodesaredefinedbytheuserasmarkersoftwotypes:theINmarkerfortheobjectsandtheOUTmarkerforthebackground.Thepathlengthismeasuredbythepathcostdefinedasfollows:

LetpathcostCpqMdinthepathfromnodeptonodeqbedefinedasapairofvaluesinlexicographicorder.Thefirstcomponent(withahigherpriority)isthemaximumarcweightM.Thesecondcomponentdisadistancefromtheendofthepathtothenearestnodewithalowerpathcost.Accord-ingtoLotufoandFalcao1,thiscomponentreflectsthefloodingprocesswhenthewaterreachesaplateauintherelief.

Theshortest-pathcostbetweentwonodesCpqisdefinedasthesmallestlexicographiccostofallpathsbetweenpandq.Thedetectionoftheshortest-pathcostfromallnodesresultsinthedetectionofthe“nearest”markerforeachnode,i.e.,label-ingofthevoxelasbeingpartoftheobjectorofthebackground.

LotufoandFalcao1describethephysicalmeaningintheframeofatopologicalreliefoftheimageasfollows:“Thearcweightistheheightofthewallbetweennodesandtheshortest-pathcostistheminimalheightwherethewatercomingfromtwopointsmerges....,thesecondcomponentofthelexico-graphiccostallowsthepartitiontobeatthemediallineoftheplateau.”

Theorderofen-queueingofthemarkersintothepriorityqueueisimportant,asitdeterminestheorderofprocessingofthemarkersandalsotheshapeandthesizeoftheresultingla-beledarea.Thesoonerdefinedmarkersacquirelittlelargerar-eas(ofaboutone-pixelonplateaus).

Thetheoreticalmostefficientknownalgorithmfortheshortest-pathforestproblemistheDijkstra’salgorithm3,whichcanbeefficientlyimplementedbymeansofapriorityqueue.ItrunsinOmtimeplusthetimerequiredtoperformqueueoperations.

Ifthearcweightsarerealnumbersandonlybinarycompar-isonsareusedintheheapimplementationthebestpossibletimefortheDijkstra’salgorithmisOmnlogn,asdescribede.g.byAhujaetal.4Ifallthearcweightsareintegersofmoder-atesizeC(whichistrueinthecaseofmedicaldatasets)spe-cialalgorithmsexistthatdifferintheimplementationofthepriorityqueue,runningfromatypicaltimeofOmnC(theDial’s5implementationwithbuckets)tothebestknowntimeofOmnlogC(Two-LevelRadixheapsbyAhujaetal.4,whichcombineRadixheapsandFibonacciheaps).Theseval-uesarevalidforpathcostdefinedasasumoftheweightsalongthepath.Thedefinitionusedforthewatershedalgorithmasde-scribedaboveinthissectionresultsinatimecomplexityofOmC(DetailsinSection5.2).

Thememorycomplexitiesofthesealgorithmsare:OnCfortheDijkstra’s3andtheDial’s5algorithms(uptoOnifim-plementedwithhashingbutthetimeisthennotdeterministic),

andOmlogCforOnelevelRadixheapsbyAhujaetal.4.ForTwolevelRadixheapswasbyAhujaetal.4notmentioned.

3.IFTalgorithmbyLotufoandFalcao

LotufoandFalcao1implementedthewatershedalgorithmasanIterativeForestTransform(IFT).TheyaccentthenecessityofapriorityqueuewithaFIFOrestrictionforthecorrecthandlingofplateaus.Inthealgorithm,Cpisthecostpathfromptoitsnearestmarker,Lpistheinputmarkerimageandalsotheresultofthewatershedpartitioning,flagpdifferentiatesfi-nallylabelednodesfromnon-processedortemporarilylabelednodes.TheIFTalgorithmworksasfollows:

1.Initialization

a)forallnodespdo

flag(p)=TEMP;

b)forallnon-markernodespdo

C(p)=infinity;

c)forallmarkernodespdo

C(p)=0;EnQueue(p,0);

2.Propagation

whileQueueNotEmpty()do

a)v=DeQueueMin;b)flag(v)=DONE;

c)foreachpneighborofvwith

flag(p)==TEMPdo

ifmax{C(v),w(v,p)}A)C(p)=max{C(v),w(v,p)};

L(p)=L(v);

B)ifIsInQueue(p)then

DeQueue(p);

C)EnQueue(p,C(p));

Thealgorithmpartitionsallthegraphnodesintotwosets:permanently(DONE)andtemporarily(TEMP)labeled.Ateachiterationstepitselectsatemporarilylabelednodewithamin-imumcostfromthepriorityqueueasthenextnodetobescanned.Onceanodeisprocesseditbecomespermanentlyla-beled.Thealgorithmterminateswhenallnodesbecomeperma-nentlylabeled,i.e.,whenthequeueisempty.Asthepathcostisanon-decreasingfunction,theimportantpropertyofthealgo-rithmisthatwhenthenodebecomespermanentitspathcostisthefinaloptimalpathcost.Anotherimportantpropertyisthatthesecondcomponentdofthepathcostdoesnotneedtobestored,astheFIFOpriorityqueuekeepsthesecondcomponentintrinsicallysorted.

Intheinitializationphase,allthenodesarelabeledastem-porary(line1a),themarkershaveassignedacostto0(line1c),allothernodestoinfinity(line1b).Themarkersareenteredintothepriorityqueue.Thequeueinsertionsequenceformarkersofthesametype(e.g.,onlybackgroundones—OUT)isnotimpor-tant.Ontheotherhand,theorderofinsertionsofthemarkersofadifferenttypeintothequeueisimportant,becausethefol-lowingprocessingisalsodoneintheFIFOorderandthefirstcomemarker“wins”alargerregion.Thereforetwoseparatein-putlistsofobjectandbackgroundmarkersareusedandthealgorithmstartswidthen-queueingoftheobjectmarkers.Duringthepropagationstep,thenodevwithaminimalpathcostisremovedfromthequeueandmarkedasperma-nent(lines2a,b).Allitstemporarilylabeledneighborsparethentestedandifthepathcostthroughthepermanentnodevissmallerthanthetemporarycostassociatedwithnodep(line2cA)thetemporarycostandlabelareupdated.Ifthenodewasalreadyinthequeueitisremoved(line2cB)andfinallyanodeisenqueuedwiththepriorityofanewpathcost(line2cC).

Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest3

Forabetterunderstandingoftheroleofthedistancecom-ponentditwillbediscussedinagreaterdetail:Thealgorithmprocessesthenodesfromthelowestpathcosttothehighest,asthefloodingbywaterproceeds.Thatalsomeanswhilepro-cessingagivenlevelofpathcost,allthenodeswithalowerpathcostarealreadyprocessed!Thesameisalsotrueforthedistancecomponentd,asallnodeswithalowerdistancearealreadyprocessedandonlythenodeswithdistancedandd1existinthequeue.Moreprecisely,thenodeswithdistanced0existonlyforthecurrentpathcostlevelCv,whichmeans,forthequeueimplementedwithbuckets,inthecurrentbucket.

Iftheprocessednodevisonthegiven“water”level,whichmeansithasthepathcostequaltoCv,therearethreepossi-bilitiesfortheneighboringnodep:

1.ThepathcostCpwillnotbeupdated,asthepaththroughthenodevwouldbemoreexpensive.Thesameistrueford,whichsurvivesunchanged(testinline2cisfalse),

2.thepathcostwillbeupdatedtomaxCvwpv,asitischeapertogothroughthenodev(testinline2cistrue):

a)Pathcostincreases(thearcweightwpvCv),Cpwpvandanewdistancedp0,b)pathcostvalueremains,plateau(wvpCp),Cpremainsunchangedandanewdistancedpdv1iscomputed.

InbothcaseswherethepriorityqueueisupdatedtheFIFOrestrictionhandlescorrectlytheinsertionofanewnodeintheendofallalreadystorednodes.Inthecase2a),anewnodeisinsertedasthelastnodewiththepathcostequaltoCp.AllstorednodeswiththecosthigherthanCphavethedistanced0.

Inthecase2b),whichhandlesplateaus,neighboringnodesare“reinserted”withthecostCvunchangedbutwiththedistancedincremented(dpdv1).Thenodesalreadystoredinthequeuewiththispathcosthaveassociatedtwopos-siblevaluesofthedistanced:Thedistanceiseitherequaltodv(thenodeiswaitingforprocessingatthislevelofCvanddv)orthedistanceisequaltodv1(theneighboringnodethathasbeenprocessedatthecurrentlevelofCvandd).NewlyprocessednodesaresuccessivelyinsertedafterallnodeswithvaluesCvanddv1.

Ifanimplementationwithbucketsisusedboththecases2a)and2b)representinsertingofthenodesintheendoftheappro-priatebucket.TheprincipleofbucketsisexplainedinSection4.4.ImplementationoftheIFTalgorithm

FalcaoandLotufo1didnotdiscusstheimplementationofthealgorithmindetail.TheyonlynotedtheapplicationofbucketsforimplementationofthepriorityqueuesimilartoDial5.Buck-etscanbeused,asthemaximalarcweightCwmaxpqforagiveninputgrey-scalevolumeisknown—itisthemaximalab-solutedifferenceofvoxelvalues(Cmaxfpfqforallneighboringvoxels).CisalsocalledMaxDiffinthefollowingtextanditisupper-boundedbythemaximalvaluestore-ableinthedataset.Thismaximalstore-ablevalueisinthispapercalledadatasetprecision(Cp)anditisgivenbythe12–16bitrepresentationofthenumbersinthedataset.

Theyalsoproposedtosparetheline2cBintheIFTalgo-rithm,whichsimplifiesthedatastructureforpriorityqueueim-plementationbutresultsinmoreelementsstoredinthepriorityqueue,asmultipleentriesforonevoxelwillappearinthequeue.

PossiblemethodsfortheimplementationoftheIFTalgorithmwillbediscussedbelowinthissection.

TheIFTalgorithmofFalcaoandLotufo1followstheideasproposedbyDial5andusesbucketsforthepriorityqueueimple-mentationtoovercomethelogarithmtimecomplexityofheapbasedapproaches(forhandlingoftemporarylabelednodes),whichisidentifiedasabottleneckofthewholealgorithm.Thebucketkstoresalltemporarilylabelednodeswhosedistancela-belsareequaltok(orfallwithinacertainrange,asinotherap-proaches).Thenodesinbucketscanbestoredindouble-linkedlistsofnodes,towhichthearrayofpointerswithasizeequaltothenumberofbucketsCpoints.

TheDial’simplementationrequiresnC1bucketsintheworstcase,whereCisthemaximalcost.However,Ahujaetal.6provedthatforagraphwithamaximumcoststepC(networkwithamaximalarclengthC)onlyC1bucketsarenecessarytomaintainallthetemporarilystoredlabelsinacircularqueue.Asthealgorithmusesthemaximumonthepathasapathcost,evenacircularqueueisnotneededandthenumberofbucketsCisupper-boundedbytheprecisionCpofthedataset.

Inthefollowingtextfivevariantsofthealgorithmimplemen-tationwillbediscussedandresultsofmeasurementsoftheirtimeandmemoryconsumptionifappliedonreal3Dmedicaldatasetswillbeshown.Thedifferentmodificationsofthealgo-rithmusedifferentlevelsofsimplificationofthedatastructuresnecessaryfortheimplementationandthereforealsochangethememorycomplexityofthealgorithminbothaverageandworstcases.Thealgorithmshavebeentestedinordertoknowwhichoftheimplementationshastheminimalaveragememorycon-sumptionkeepingalsothetimecomplexityofOmC.Thetestedalgorithmmodificationswere:

I)AcompleteIFTalgorithmwithdequeuingandafixedvol-umeforqueue(Section4.2),

II)acompleteIFTalgorithmwithdequeuingandadynamical

queue(Section4.3),

III)anIFTalgorithmwithoutdequeuingoftheentrieswitha

higherpathcostfromthequeue(Section4.4),

IV)amodificationwithoutdequeuingthatstoresallthecostsin

thequeue(Section4.5),andfinally

V)animprovementofthemodification(IV)whichsavesthe

spacenecessaryforthequeueimplementation(Section4.6).Inthefollowingsubsectionsallfivevariantsofthealgorithmmodificationswillbeexplained.

4.1.CommonandalgorithmspecificdatastructuresWehavedesignedthedatastructuresinallalgorithmmodifica-tionswiththeaimofachievingaconstanttimecomplexityforthequeuemodification.Theconstanttimecomplexityisvalidforallqueueoperationsexceptofsearchingforthefirstnon-emptybucketintheoperationQueueNotEmpty(),whichhasacomplexityofOC.

Thefollowingdatastructuresarecommontoallpresentedimplementations:

Inputdataset—volumeofscalarvaluesofsizenxyz,storedwithprecisionCp4096or65536,givenbythe12-to16-bitnumberrepresentation.Thedatasethasmarcs(asdescribedinSection2),

twofixedarraysofpointerstothebeginningsandendsofthebuckets.Thearrayshaveindicesinrange0CwhereCMaxDiffisthemaximalabsolutedifferenceofneighbor-ingvaluesinthedataset.Astheupperboundforthisnum-berisgivenbytheprecisionCpofthethedataset,MaxDiff

4Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest

NUMBEROFELEMENTSINARRAYS

OFSIZEC,mORn

ALGORITHM

CompleteIFT,deQing,fixvolume(I)CompleteIFT,deQing,dynam.Q(II)IFTnodeQing,dynam.Q(III)IFTnomaxtest,dynam.Q(IV)IFTnomaxtest,bricks(V)Sizeofoneelement[bits]Sizeofoneelement[Bytes]

C-TEMPptr22222324

FIXEDSIZEn-TEMP

costflagptr1––––162

111111

18n-RESULTlabel

111111

18cost–11––162

DYNAMICSIZEn-,m-TEMP

labelpositionptr––1(1)(1)(1)1or0

–––11

–211

12index––––

122211––324

28–3143248–161–2

Table1:Memorynecessaryforthealgorithms(innumberofelementsineacharray)withoutaninputdataset.Thehorizontallineseparatesthen-(upperpart)andm-(lowerpart)sizeofthetemporaryvolume.*Positionfor(III)iscomputedindirectlyfromthevaluesofpointers.**Indexandpointersizesapproximatedforbricksof256*4Bytes—oneptrand2indicesforbrickof2elements

OCpandthereforeCpcanbedirectlyusedasthehigherindexinthefollowingsectionsifthemaximalvalueCisnotavailable,

temporaryvolumeofflags—onebitvaluethatdistinguishesTEMPandDONEstatusofeachnodeinthevolume.Theflagsarestoredeitherinaseparatebit-volumeortogetherwiththepositionasonebitfromthe4-bytevalue,

resultingvolumeoflabels—onebitforeachlabel,asonlytheobjectandthebackgroundaredistinguished.

4.2.CompleteIFTwithdequeuingandfixedvolumefor

queue(I)ThecompleteIFTalgorithm,aspublishedbyLotufoandFalcao1,isdescribedinSection3.Toachievethetimecomplex-ityofOmCthepriorityqueuewithbucketsisimplementedasadouble-linkedliststoredinthepreallocatedfixedvolumeofthesamesizeequaltothesizeofthedataset(seeFigure1,wherefourvoxelsarestoredinbucket0).

Theimplementationspecificdatastructures,whichdifferinthemodificationsofIFT,areasfollows:

Bucketsofelements—implementedasafixedvolumeordy-namicallyasdouble-linkedlists,single-linkedlistsorlistsstoredinstructurescalledbricks,whichwillbedescribedinSection4.6,

temporarynodecosts—inafixedvolumeorasapartofadynamicallyallocatedbucketelement,

nodepositions—storedimplicitlyasapositioninafixedvol-ume,explicitlyasasetofcoordinates,orevennotstored.

AnoverviewofsizesofthestoredvaluesisconcentratedinTable1whereforeachalgorithmthecolumnheadersrepresentthesizeofthestructureinnumbersofelements(Cmorn)—thefixedsizeforstaticdatastructuresorthemaximalsizefordynamicstructures)—andthetableentriesrepresenttheamountofdatastoredineachelementofthesestructures.

Figure1:DatastructuresforcompleteIFTalgorithmwithde-queuingandfixedvolumeforqueue(I)

Forbetterunderstandingofthememorydemandsofthepre-sentedalgorithmsTables2,3and5showthemodification-specificrepresentationinamountsofbits/bytesindifferentlev-elsofsubstitutionandconversion,takingintoaccountthelasttwolinesofTable1.Detailsarediscussedintheexplanationsofthealgorithmmodifications(I–V)inSections4.2–4.6andillustratedinFigures1to5.

Theproposeddatastructurescanhandle16-bitdatasetsofmaximalsizesupto102410242048voxels.Thisupperlimitisgivenbythestorageofthetemporarylabelandpositioninone32-bitelement.Ontheotherhand,thereallimitsforthepresentedalgorithmsaretheamountofRAMinatypicalnowa-daysworkstationandthelargestpossibledatasetsizespresentlyavailableintheclinicalpraxis(about5125121024voxels),i.e.,theselecteddatastructuresformnottherestrictivepartofthealgorithmimplementation.

ThisversionusesalltheoperationsdescribedattheendofSection3.Twoarraysofpointerstobothendsofthebucket-FIFOsareusedforaconstanttimeDeQueueMin()andEn-Queue(p,c)whilesearchingoftheminimalelementisdoneinQueueNotEmpty()inOC.

Thedouble-linkedlistisnecessaryforaconstanttimeDe-Queue(p)foranodepanywhereinthebucketqueue;thecom-pletelistisstoredinthevolumeofthesamesizeasthesizeofthedatasettohaveaconstanttimefortheIsInQueue(p)testandforaconstanttimelocationoftheneighborsGetNeigh-bor(v,dir).EachlistelementhasalsoanentrywithacurrenttemporarycostCvtoachieveaconstanttimeGetCost(p)(fordetailsseealsothefirstlineinTables1–3).TheonlyOCtimeoperationisthetestQueueNotEmpty(),whichsequentiallysearchesthearrayofbucketsforthefirstnon-emptybucket.Thecompletesearchisperformedonceduringtherunofthealgorithm.

Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest5

ALGORITHM

CompleteIFT(I)CompleteIFT(II)

IFTwithoutdequeue(III)IFTwithoutmax(IV)IFTwithbricks(V)

MAXIMALMEMORYCONSUMPTIONO

FIXEDTEMP

INTERMSOF

Cnm

FIXEDRESULT

DYNAMICTEMP

2C2C2C2C2C

2n1n1n

ptrptrptrptrptr

nnnnn

costflagflagflagflag

flag

+n+n+n+n+n

labellabellabellabellabel

+0

+ncost2ptr

+mcostlabelptr+mlabelposptr

1

+mlabelpos2ptr

2

2ind

Table2:Memorynecessaryforthealgorithmsintheworstcase(inmultiplicandsofCnmanddatatypepieces).Underlinedlabel+posarestoredtogether,underlinedlabelalonehastooccupyawholeByte.Thefractionalconstantforptrandindiscomputedforthebricksizeof2elements

ALGORITHM

CompleteIFT(I)CompleteIFT(II)

IFTwithoutdequeue(III)IFTwithoutmax(IV)IFTwithbricks(V)

MAXIMALMEMORYCONSUMPTIONO

FIXEDTEMP

INTERMSOF

Cnm

FIXEDRESULTDYNAMICTEMP

2C2C2C2C2C

2n1n1n

44444

nnnnn

2

1818181818+n+n+n+n+n

1818181818+0

+n224+m214+m44

1

+m424

2

22Table3:Table2aftersubstitutionofdatatyperepresentationsizesaccordingtothelastlineofTable1.Underlinednumbersarisefromsharingofspace(label+pos),allocationofthewholebyteinthedynamicalstructures(labelalone),orstorageofindicesintwoBytes

4.3.CompleteIFTwithdequeuinganddynamicalqueue

(II)Inanaveragecaseofthealgorithm,thenumberofelementssi-multaneouslystoredinthequeueislessthantheplacereservedinafixedvolumeofnentries(thisfeatureisdiscussedinde-tailinSection5.3).Toreducethisextremelyhighfixedmem-oryconsumptionadynamicalversionofthepriorityqueuewasproposed.

Asnovoxelisstoredinthequeuemorethanoncethearrayreservedfortheresultinglabelscanbe“reused”alsoforthetemporarylabelsthesamewayasinthecompletealgorithm(I).ThesetofoperationsandtheircomplexitiesareequaltothefixedvolumeversionfromthepreviousSection4.2.4.4.IFTalgorithmwithoutdequeuing(III)

LotufoandFalcaodescribedalsoapossiblesimplificationoftheproposedalgorithm.Theyproposetoomitthedequeuingofthenodeswithahighertemporarycostfromthepriorityqueueduringthenode-costreplacingoperation(line2cBofthecompleteIFTalgorithm).Thismodificationshouldsimplifythequeuedatastructure,astheoperationDeQueue(p)doesnotneedtobeimplemented.

However,herewiththeuniquityofthenodesinthequeueisalsolost,asthenode(voxel)canbe(andinmanycasesalsois)storedmoretimesthanonceinthequeue.Thereforemoredifferenttemporarycostsandlabelsexistforonenodeatthesamemoment.ItresultsinarepeatedstorageofthetemporarycostCpandtemporarylabelinthequeuewithineachqueueentry.Multipleoccurrencesofthenodesinthequeuearealsocommontobothourmodifications(describedinSections4.5and4.6).

Figure2:DatastructuresforcompleteIFTalgorithmwithde-queuinganddynamicalqueue(II)

Thequeueisnowstoredinadynamicallyallocateddouble-linkedlist,eachelementofthislistcontainsthevalueofthetemporarycostCvandtwopointersforlinkingofthelist(fordetailsseethesecondlineinTables1–3).Asadirectaccesstotheelementsinthequeueisstillneeded,afixedvolumeofpointerstotheelementsinthelist(queue)isstillnecessary.

ButtopreservetheconstanttimeoftheoperationGetNeigh-bor(v,dir),whichisusedinthecomparisoninthemaxtestinline2coftheIFTalgorithm,adirectlocationoftheneighborsinthequeueisstillnecessary.Thisdemandviolatesthepre-sumptionproposedbyLotufoandFalcao1thattheDeQueue(p)operationcanbecompletelyremoved(moreprecisely,thisop-erationcanberemovedbutthespeedofthealgorithmissimul-taneouslylostwhentheelementinthequeueissearched,orthevolumeofcurrentminimaltemporarycostsisstillnecessarytobeused,whichneedsmemoryandwhichstillhastobecontin-uouslyupdated)!

6Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest

Thedirectaccessofnodeneighborscanbeachievedbyhan-dlingofthevolumeofpointerstotheelementsinthequeue;sameasinthepreviousalgorithm(IIinSection4.3).AndtheoperationDeQueue(p)canbeonlysimplifiedtomovethepointertotheelementwithalowervalueofCpwithoutphys-icalremovalofthepreviouslypointedelement(ortoupdatethecurrentminimalcostincaseofafixedvolumeoftemporarycosts).

Tosummarizethememorydemands(seealsothethirdlineofTables1–3):

Onlyonepointerineachqueueelementisnowneeded,astheelementsarenotremovedfromthequeueandthequeueisimplementedasasingle-linkedlist;butmultipleentriesofonenodeexistinthequeue(double-entryexampleinFig-ure4).Therefore,westorealsothecurrentcostandlabelinthequeuebutalsomultipletimeswitheachnode.

Inthefixedpartofthedatastructureonlyonepointerinthefixedvolumeofpointersissaved(similarto(II)).

Asadisadvantagethemaximumqueuelengthsimultane-ouslyincreasesfromOn,asinmodifications(I)and(II),toOm.ForillustrationofthedatastructuresseeFigure3.

Figure3:DatastructuresforIFTalgorithmwithoutdequeuing(III)

4.5.IFTwithoutdequeuingandwithoutamaxtest(IV)Tosaveeventhememoryofthefixedvolumeofpointersan-othermodificationoftheIFTalgorithmwithoutdequeuingofelementsisproposedinthispaperwherenotonlythedequeu-ingisomittedbutalsothemaximumtest(inline2c).Simply,ALLnodes(theirlabelandposition)arestoredaccordingtothenewvaluesofthetemporarypathcostintotheappropriatebucketinthepriorityqueuewhereeachbucketisimplementedasasingle-linkedlist.ThecostisNOTstoredinthequeue—thisinformationisintrinsictoeachbucket,asitistheindexinthebucket-begin-andbucket-end-pointerarrays(fordetailsseeFigure4andthefourthlineofTable1).AstheFIFOreturns(dequeues)theelementswithlowestcostfirstandthealgorithmignoresthemultipleentriesaftersettingoftheflagtoDONE,themodifiedalgorithmgivesexactlythesameresultsastheal-readydiscussedvariants(I)–(III).Takenoteofareversedirec-tionofpointingfromthequeueelementsintothevolume(viaposition)andalsoadouble-entryexampleinFigure4.Thevol-umenowcontainsonlytheresultinglabel(R-label)andaflag,thetemporarylabelandpositionarestoredinthedynamicallyallocatedqueueelements.

Figure4:DatastructuresforIFTalgorithmwithadynamicalqueuewithoutdequeuingandwithoutmaxtest(IV)

Asadisadvantage,wealsocanhaveamaximumofOmelementsinthequeue.TheexactnumberofelementsinthequeueisuptotwotimeshigherthaninSection4.4,asalsotheelementswithahigherpathcostwillbestoredsomewhereintheendofthequeue.

AboutonehalfofthememoryisusedforthepointersinthedynamicalimplementationoftheFIFOviaalist(fordetailsseealsothefourthlineofTables2or3,thecolumnDynamictemp).4.6.IFTwithoutdequeuingandwithoutamaxtestwith

bricks(V)

Figure5:DatastructuresforIFTalgorithmwithoutdequeuingandwithoutmaxtestwithbricks(V)

Tosavethememoryusedforpointersinthedynamicallistin(IV),anallocationofmemoryinlargeramountswasproposed–theyarecalledbricks(seeFigure5,wherethebucket“0”con-tainsonebrickwithfiveentries,wheretwoofthempointtothesamevoxel).Eachbrickhasonepointertothenextbrickandtwolocalindicesforthefirstandthelast(nextfreepositionbehindthelast)elementsofthequeuepartstoredinthisbrick(markedbyFandLinFigure5).8-bitindices,allowthebricksize(numberofnodeentriesstoredinonebrick)ofmax256el-ements.Thecommonmemoryallocationschemeofmultiplesof8bytes(#pragmapackinVC++)7mayprefer2entries,

Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest7

NO123456

DATASETSIZEXYZNUMBEROFNODESnARCSm129433631457285267025280979843276800044302336

3840093470721569474087001087913856132471808

ARCCOSTS

MAXMEANSDEV40955683921162740951483

50.409.9826.1823.8124.2723.00

152.0520.8268.4678.6080.5750.25

ARC/NODE

RATIO

128256255256512512

128256255256512512

7948814441251692.9722.9712.9802.9902,9882.990

Table4:Characteristicsofmedicaldatasetsusedinthestudy

as6-8bytesareusedforindicesandapointertonextbrick(to-gether2568Bytes.FordetailsseethefifthlineofTables1–3,thecolumnDynamictemp).

Tosavethememoryallocationtimesanemptybrickmanage-ment,whichcollectsemptybricksinaseparate“empty-brick”stack,isused.5.Tests

Studiesofcomputationalandmemorycomplexityexistfortheshortestpathforestproblem,e.g.,ingeneralcasebyAhujaetal.4andfortherealroadnetworksbyZhan8.Thepresentedstudyisrelatedtothelargemedicalvolumetricdatasets,wherealsothedifferentshortestpathcostfunctionisused(notsum,butmaximumonthepath,seeSections2and5.2).

FivemodificationsoftheIFTbasedwatershedalgorithmwerediscussedwithsegmentationoflarge3Dmedicaldatasetsinmind.Thissectiondiscussestheestimationsofasymptoticcomputationalandmemorycomplexitiesbeingmade.Therealcasemeasurementsonthe3Dmedicalimagingdatasetsfollow.PropertiesofourtypicalvolumetricmedicaldatasetsarecharacterizedinSection5.1.Memoryandcomputationalanal-ysisoftheworstandaveragecaseforeachalgorithmfollowoninSections5.2and5.3.ResultsoftestsaresummarizedinSection5.4.5.1.Datasets

Thetypeofthedataset(itssizeandprecisionofstoredvalues)isimportantforthealgorithmimplementation,asitdeterminesthememorydemandsfortemporarydatastructures,e.g.,therepresentationofstoredcostsanddatastructuresforthepriorityqueue,asdiscussedinSection4.

TheimplementationofIFTalgorithmhasbeentestedandtunedonthe3Ddatasets(volumes)acquiredbythecomputertomography(CT)andthemagneticresonanceimaging(MRI).ThesizeofthesedatavolumesisrrS,whereinter-sliceresolutionrvariesfrom128to512andthenumberofslicesSvariesfrom48to444.Characteristicsofmedicaldatasetsusedfortestssuchasmaximal,meanandstandarddeviationofthearcsarelistedinTable4.Thedatasetsareorderedaccordingtothenumberofnodes.TheexampleimagesofthreeofthemareinFigure6.

Thepracticalmaximalsizeofdatasetthealgorithmcanhan-dleisgivenbytheoperationmemoryofPC’satthepresenttimelimitedtoabout1GB,i.e.,about512–680slices(512toomitswapping,whichoccursifabout75%memoryisused).Nevertheless,theproposeddatastructuresallowtousedatasetsupto102410242048slices,astheyuseonebitforthelabel

and31bitsareleftfortheposition.Higherdatasetsizesormorethanonelabelvaluecauseanincreaseinmemorycomplexity,asthelabelhastoallocateaseparatebyte.

AsalreadynotedinSection4.1,precisionCpofthe12–16-bitdatasetsgivesanupperboundforthemaximaldifferenceC.Thatmeansafixedsizeofabucketpointerarrayof4096–65536pairsofbucketpointerscanbeusedifthemaximaldif-ferenceofvaluesinthedatasetwerenotdirectlyavailableandhadtobecomputed(inanadditionalcomputationalcostOm).Thisroughlyapproximatedarrayofbucketpointersoccupiesabout0.5MBofmemory,neverthelessthisamountofmemoryincomparisontothewholememorydemandsofthealgorithmisinpracticaltermsinconsiderable.

Zhan8drawtheattentiontodifferenttypesofgraphsfordif-ferenttasks,classifiedaccordingtoarc-to-noderatio,asthispa-rameterdirectlyimpliesthecomplexityofthealgorithm.Zhan8alsowarnsthatthemeasurementsoftheperformanceoftheshortest-pathalgorithmshavebeendoneonartificialnetworkswitharc-to-noderatiouptoten,wheretherealroadnetworkgraphsachievethevalueofonlyapproximatelythree.Thearc-to-noderatio(mn)isalmostequaltothreeforavolumetricgraph,becausemostofthenodesbelongtotheinnervoxelswithsixneighborsandeacharcisprocessedonlyonce.Arc-to-noderatioofmedicaldatasetsusedfortestsislistedinthelastcolumnTable4.

Forrealroadnetworks,oneofthefastestalgorithmswastheDijkstra’salgorithmimplementedwithappropriatebuckets.Asthevolumetricdatasetshavetheequalarc-to-noderatio,itcanbededucedthattheconcentrationoftheworkonagoodimple-mentationoftheDijkstra’salgorithmwithbucketswasagoodchoice.

5.2.Theworstcaseanalysis

AllpresentedmodificationsofthealgorithmhavethesameOmCtimecomplexity,theydifferintheconstantfactorintheaverageandmaximalrunningtimesandinthemaximalmemorycomplexity.

AsstatedinSection2,thepathcostisforthewatershedalgo-rithmcomputedbytheIFTdefinedasthemaximalarcweightinthepath.The“classical”shortestpathforestalgorithms(dis-cussedbyAhuja4orZhan8)useadifferentdefinitionofthepathcostasthesumofthearcweightsinthepath.The“clas-sical”variantsthereforeneednrunsthroughthequeueintheworstcaseandreachtimecomplexityofOmnfC–withthemultiplicativetermn.TheIFT-WSbyLotufoetal.1needsonlyonecompleterunandthetimecomplexityissimplifiedtoOmC.

8Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest

325

Figure6:Examplesofthedatasetsusedintests.Toprowshowsawindowedviewofinputdatasets,bottomrowsegmentedstructures.NumbersareaccordingtoTable4.(DatasetswithcourtesyofTIANIMedgraphGmbH,Austria)

TheworstcasememorycomplexityofpresentedalgorithmmodificationsvariesfromOntoOm:

Thealgorithmvariantswithdequeuing(thecompleteIFTwithafixedvolume(I)andthecompleteIFTwithdynamicalqueue(II))haveafixedsizeofthesupportingdatastructuresofOnCandafixedormaximalsizeforthequeueOn.ThereforememoryconsumptionofOnC.

Thevariantswithoutdequeuing(IFTwithoutdequeuing(III),IFTwithoutdequeuingwithoutthemaxtest(IV)andIFTwithoutdequeuingwithoutthemaxtestandwithbricks(V))haveallthefixedsizeofthesupportingdatastructuresofOnCand,astheelementsarenotdequeued,themaximalsizeforthequeueofOm.ThereforememoryconsumptionofOmnCOmC.

ALGI

IIIIIIVV

MAXMEMORYOfCnmFIXEDPARTDYNAMICAL

FORALLDIFFPART

RELATIVE

QLEN[%]100%60%29%42%82%

8C8C8C8C8C

14n14n14n14n14n

10n4n4n——

—10n7m21n8m24n40314m˙121n

Table5showsthemaximal(worstcase)memorysizesoffivetestedalgorithms(I–V)inmultiplesofCnandmafterallsubstitutionsandconversions.Thesemaximalsizesarereachedonlyinaspecialcaseofinputmarkerssetinachessboardpat-tern,whichcauseplanningofallarcssimultaneouslyintothequeue.Inrealsituations,thedynamicalpartdependsontherealqueuelengthmorn,whichissmallerthanmorn.

Table5:Table3afterconversioninmultiplicandsofbytes.ThelastcolumnshowsthemaximalamountofelementsthatcanbeprocessedinthesamememoryasusedbythecompleteIFTalgorithmwiththequeueinthefixedvolume(I).(Algorithm(I,II)inpercentsofn,(III–V)inpercentsofm3n)

Beforetestingthealgorithms,acomparisonofthemaxi-malnumberofelementsthealgorithmscanhandleinthesameamountofmemoryasthecompleteIFTalgorithm(I)wasper-formed(seethelastcolumnofTable5).Forinstance,thevariantwithbricks(V)canhandleupto82%oftheelementsstoredinthequeue(oflengthabout3n).Thecomparisonisbasedonthepremisethatthequeueswillbefilledsimilarlyinallvariants(I–V),whichmustnotbetrue,asthestoragestrategiesdiffer.Itispossibletosee,thattheLotufoandideaforthedatastructuressimplificationbyomittingthedequeuingis

Falcao’s1

formedicaldatasetsnotsogood(moreprecisely,abetterwayofitsimplementationisnotknowntotheauthorsofthispa-per).OmittingtheDeQueue(p)operationwithsurvivalofthemaximumtestallowonly29%ofarcsstoredinthequeuetobehandledinthesameamountofmemoryas(I)(Table5).Or,tosavememory,thevolumeofpointersusedforthedirectaccessofthequeueelementsinthemaxtestcanbealsoomittedbutitwouldslowdownthealgorithm.

5.3.AveragecasecomplexityanalysisformedicaldatasetsSixvolumetricmedicaldatasetsweretestedandmeasured.Thetestsweredesignedtoverifythederivedtimeandmemorycom-plexities,theaveragefillingofthequeueand,forthelastmodi-

Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest9

MEMOF

DSNO1

ALGNO

FIXTEMP8C1/4nVOL

MB

DYNAM

MAX

MB

MB

MB

DYNAMICUSEDBYELEMENTS

NOELEMSFILLINGMEM(mORn)%OFQMB

SUMMEMORY

MAX

USED

MB

MB

%MAXI%

I

IIIIIIVVIIIIIIIVVIIIIIIIVVIVIVIV

0.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.50.5

0.30.30.30.30.30.80.80.80.80.81.31.31.31.31.36.96.97.87.810.610.6

12.344.944.94––30.0012.0012.00

––50.2320.0920.09

––277.50

–312.50

–422.50

–

–12.325.929.614.9–30.063.072.036.3–50.2105.5120.660.8–335.8–378.1–511.2

181243181243558862102930810293081073959107395915629002503049250304975745375745326295784155241552–

11735946–

265309–

47513276

14.0%14.0%14.5%26.8%26.8%34.1%34.1%16.7%26.8%26.8%14.4%14.4%16.8%29.6%29.6%–13.5%–27.1%–35.9%

–1.73.77.94.9–10.210.419.19.9–7.217.635.4187–45.4–102.7–1819

13.218.131.730.415.731.343.376.373.337.652.072.1127.3122.362.5284.9343.2320.8386.4433.6522.3

13.27.59.58.75.631.323.523.720.311.152.029.139.437.220.5284.952.8320.8111.0433.6193.0

100%41%30%28%30%100%%31%28%29%100%40%31%30%31%100%15%100%29%100%37%

100%57%72%66%42%100%75%76%65%36%100%56%76%71%40%100%19%100%35%100%45%

2

3

456

Table6:Measurementsofmemoryconsumptionfor3Dmedicaldatasets.Valuesformeasurementsondatasetsnumber4–6thatdidnotfitintomemoryofourimplementationwereomitted(thequeuelengthforalgorithm(I)andcompletelinesfor(II–IV))

fication,alsotheaveragebrickfilltocheckthesuitabilityoftheselectedbricksize.Inallcases,CMaxDiffwasused,asthisvaluewasdirectlyavailableforeachdataset.

ant(V)canhandleallthecaseswithalargereserveinthesameamountofmemoryas(I)butthevariant(III)cannot.Moreinterestingisthecomparisonofmemoryusageforthealgorithmmodifications,concentratedinthesecondboldcol-umninTable6.Itispossibletosee,e.g.,thatthealgorithmvariantthatstoresallarcsinthequeueandperformsnocom-parisonsofpreviouslystoredcosts(V)needsonlyabout19to45%ofthememoryofthereferencecompleteimplementationwithafixedvolume(I).Thisisthebestimplementedmodifica-tion.

Theamountofelementsinthequeueandthereforethewholememorydependsubstantiallyonthesegmentedstructure,givenmarkersandthecharacterofthedataset.Itseemsthatsmallhomogeneousstructuresinahomogeneousbackgroundneedaloweramountofelementssimultaneouslyinthequeue(DatasetNo.4with13.5%ofelements)butuptonowtheexactcorrela-tionbetweentheseparametersandtheaveragequeuefillhavenotbeenfound.Thisisatopicforafurtherresearch.

Thelasttestwasdesignedtofindtheaveragebrickfillforthebrickswiththeselectedsizeof2elements.Fortheversionwithbricks(V),thelargestamountofbricksisusedinsuchacasewhenallbucketscontainabrickwithoneelementandtherestismoreorlessfull.Butthissituationchangesthememorydemandsinamountofonesofpercentforlargedatasetsandthereforecanbeomittedinthetests.ResultsofthetestsarecollectedinTable7.Thebrickfillistypicallybetween45and1,whichmeansthatthebricksizeisrelativelyoptimalandthesizeofbrickwaschosencorrectly.

Finalnote:Tobeexactithastobementionedthatthemem-oryusedbyacompilerforhandlingofthedynamicalmemory

Atfirstatest-bedimplementationofallalgorithmswasdonebymeansofgeneralcontainerlibrary7.Thetestsshowedthatthememoryconsumptionofalgorithms(I–IV)wastoohighforthe3Dmedicaldatasetsandalsothatthedynamicalspacemanagementconsumestoomuchprocessorpower(upto10-timesslowerinourtestimplementation).Aftertheseprelimi-narytests,thelastvariant(V)wascarefullyimplementedwiththespecifically-designeddatastructures.

ThereforethecomputationaltimesweremeasuredonlyforthelastimplementationoftheIFTalgorithm(V)andtheyarecollectedforthepresented3Dmedicaldatasetsinthelastcol-umnofTable7.Thelineartimecomplexityisfromthesenum-bersobvious.

Thememoryconsumptionwasmeasuredforallvariants(I–V).AsmentionedinSection5.2,theextremesituation(maxi-mummemoryconsumption)whenthemaximumofmelementssimultaneouslystoredinthequeuewerereachedispracticallyimpossibleforrealcasesofthevolumetricdatasetswithmanu-allysetmarkers.

Intherealsituation,whentheuserputsmarkersinthe3Dvolumeandstartsthealgorithm,thememoryconsumptionofallthemodifications(II–V)islessthantheneedsofcompleteIFT(I).ThefirstboldcolumninTable6showstherelativequeuefillreachedinourtests,whichvariesfrom14to34%forvari-ants(I,II)to26to36%forvariant(V).AcomparisonofthesevalueswiththelastcolumnofTable5showsthatthelastvari-

10Felkel,BruckschwaigerandWegenkittl/ImplementationofWatershed-from-MarkersasaMinimalCostForest

DSNUMBEROFAVERAGECOMPUT

NOELEMSINQBRICKSBRICKSIZE

TIME

110293084970205.82.32250304910126245.56.034155219174242.110.1411735946502252.451.65265309105184252.267.86

47513276

186232

253.1

108.2

Table7:Testsofthebrickfillingforalldatasetsinthestudy(ContinuingofTable4foralgorithm(V)).Numberofbricksisherewithequaltoamountofmemoryusedforbricksin[kB].Thelastcolumnshowsthecomputatonaltimefor(V)

(inthecompilerdocumentation7calledthe“maintenancecost”)wasnottakenintoconsideration.5.4.Summaryoftestsresults

ThecompleteIFTalgorithmimplementedwithafixedvol-ume(I)servedasareferenceforcomparisonofthealgorithms.Itusesafixedamountofmemory,whichisgivenbynumberofvoxelsinthedataset.

Thedynamicalversionofthecompletealgorithm(II)usesabout56–75%ofthememoryof(I).Eventhatitdoesreplac-ingoftheelementsinthequeueandthereforealsostoreseachnodeinthequeuemaximallyonce.Handlingofthedynamicalvariablesresultsinslowercomputationaltimes(upto10-timesslowerinourtest-bedimplementation).

Byomittingofthenodereplacing(line2cB/C),asproposedLotufoandFalcao1(III),theimplementationsaveslessmemorythen(II),asomittingofdequeuingcausesmultiplenodeentriesinthequeueandtheseentriesneedarelativelylargeamountofmemoryforstorage.Thisvariantneedsinanaveragecaseabout72–76%ofthememoryof(I).

Notmuchbetteristhefirstmax-testsimplification(IV),whichsavesthefixedpartofthetemporarymemory(pointerstothequeueelements)byomittingofthecomparisonintheline2c.Thesavedmemoryisnearlyallusedbythemultipleentriesofnodeswithahighercost.Theaveragememorycon-sumptionisabout65–71%ofthememoryof(I).

Significantly(twotimes)betterintheworstcaseandeventhebestimplementationinaveragecaseforreal3Dmedicaldatasetsisthesecondmax-testsimplificationwithbricks(V).Italsosavesthefixedpartofthetemporarymemorybut,bybettermemoryallocationinlargeramounts,itcanhandleupto80%ofthemaximalqueuelengthinthesameamountofthememoryof(I)andinanaveragecaseneedsonly19–45%ofthememoryof(I).

6.Conclusionsandfuturework

ThepaperpresentsfivevariationsoftheIterativeForestTrans-form(IFT)algorithmimplementedwiththeaimofperformingsegmentationbywatershedfrommarkersforlarge3Dmedicaldatasetsinalimitedamountofoperationalmemory.

Anoptimizationofthememoryconsumptionwasperformedandthebestalgorithmvariantneedsinanaveragecaseabout19–45%ofmemoryofthecompleteIFTalgorithmimple-mentedaccordingtoLotufoandFalcao.

Thebestimplementationvariantallowssegmentationofdatasetsuptosizesof102410242048voxelsbutthememoryofcurrentlyavailablemedicalworkstationsbasedonPCtechnologyallowsasegmentationofsignificantlysmallerdatasetsofsizesupto512512512–680voxels.

Aninterestingareaforthefutureworkisfindingcorrela-tionsbetweendatasetparameters(suchasthatinTable4)andthenumberandthecharacterofinputmarkerstothemaximalqueuelength.Ifthiscorrelationexists,itcanbeusedforpre-dictionoftheoverallmemoryconsumptionofthesegmentationalgorithm.

Amodificationofarc-weightsinaninterslicedirectionzcanalsobetestedonthebasisofthepresumtionthatifthesam-plingdistanceinz-directionishigher,thenalsotheabsolutedifferenceishigherandthereforetheflowinthe2Dslicemaybepreferredoverjumpingtotheneighboringslice.

Anotherinterestingareaisanapplicationofhierarchicaltechniquesforspeedingupthewatershedalgorithmitselfandtheoveralluserinteraction.Atpresent,acombinationof2Dand3Dwatershedshasbeentested,wherethecompleteresultsof2Dwatershedshavebeenusedasmarkersfor3Dwatershed.Thiscombinationhasgivenpromisingresults.

Thepresentedalgorithmshouldbealsofurthervalidatedinaclinicalpraxis.Acknowledgments

VRVisissupportedbytheAustrian“Kplus”researchprogram.TheDatasetsusedfortestsinthispaperarecourtesyofTIANIMedgraphGmbH,Vienna,Austria,http://www.tiani.com.References1.

R.LotufoandA.Falcao,“Theorderedqueueandtheop-timalityofthewatershedapproaches”,inMathematicalMorphologyandItsApplicationstoImageandSignalPro-cessing(J.Goutsias,L.Vincent,andD.S.Bloomberg,eds.),KluwerAcademicPublishers,(May2000).2.

M.Sonka,V.Hlavac,andR.Boyle,ImageProcessing,AnalysisandMachineVision.PublishedbyPWSPublish-ing,Brooks/Cole,PacificGrove,CA,2ed.,(1999).3.

E.W.Dijkstra,“Anoteontwoproblemsinconnectionwithgraphs”,NumericheMathematik,1,pp.269–271(1959).CitedaccordingtoZhan8.

4.

R.K.Ahuja,K.Mehlhorn,J.B.Orlin,andR.E.Tarjan,“Fasteralgorithmsfortheshortestpathproblem”,JournaloftheACM,37(2),pp.213–223(1990).

5.

R.B.Dial,“Algorithm360:Shortestpathforestwithtopologicalordering”,CommunicationsoftheACM,12,pp.632–633(1969).CitedaccordingtoZhan8.

6.

R.K.Ahuja,T.L.Magnanti,andJ.B.Orlin,NetworkFlows:Theory,AlgorithmsandApplications.PrenticeHall,EnglewoodCliffs,N.J.,(1993).CitedaccordingtoZhan8.

7.“ThedocumentationforMicrosoftVisualC++version6.0.”MSDNLibraryVisualStudio6.0release.

8.

F.B.Zhan,“Threefastestshortestpathalgorithmsonrealroadnetworks:Datastructuresandprocedures”,JournalofGeographicInformationandDecisionAnalysis,1(1),pp.69–82(1997).