advantages131邮箱

ANITERATIVEMODEL-CONSTRAINEDGRAPH-CUTALGORITHMFORABDOMINALAORTICANEURYSMTHROMBUSSEGMENTATIONMotiFreiman1,StevenJ.
Esses2,3,LeoJoskowicz1,JacobSosna31SchoolofEngineeringandComputerScience,TheHebrewUniversityofJerusalem,Israel.
2MountSinaiSchoolofMedicine,NewYork,NY.
3Dept.
ofRadiology,HadassahHebrewUniversityMedicalCenter,Jerusalem,Israel.
Email:freiman@cs.
huji.
ac.
ilABSTRACTWepresentaniterativemodel-constrainedgraph-cutalgo-rithmforthesegmentationofAbdominalAorticAneurysm(AAA)thrombus.
Givenaninitialsegmentationoftheaorticlumen,ourmethodautomaticallysegmentsthethrombusbyiterativelycouplingintensity-basedgraphmin-cutsegmenta-tionandgeometricalparametricmodeltting.
Thegeometricmodeleffectivelyconstrainsthegraphmin-cutsegmentationfrom"leaking"tonearbyveinsandmuscles.
Experimentalresultson8AAACTAdatasetsyieldanaverageabsolutevolumedifferenceof8.
04%andvolumetricoverlaperrorof12.
86%inlessthantwoandahalfminutes.
Ourevaluationshowsthattheproposedmethodiscomparabletotheinterob-servererror,androbustfortheautomaticsegmentationoftheAAAthrombus.
IndexTerms—AbdominalAorticAneurysmthrombus,segmentation,modelconstrainedgraphmin-cut.
1.
INTRODUCTIONAbdominalAorticAneurysms(AAA)areacommonanddangerousconditionoftheendovascularsystem.
AnAAAisformedwhenthearterialwallsoftheabdominalaortaareweakened,thusincreasingtheriskofruptureandinter-nalbleeding.
ContrastenhancedCTAngiography(CTA)iswidelyusedforAAAevaluation,asitprovidesdetailedimagesoftheaorticanatomy,includingthelumen,thecalci-cations,andthethrombus.
Automaticsegmentationand3DreconstructionoftheAAAfromCTAimagescanbeofclini-calusetosupportdecisionsincludingruptureriskestimationbasedontheaneurysmdiameterandvolume[1],evaluationofendovascularrepair,selectionofstenttypeandsize[1],andpostoperativefollow-upbasedAAAvolumechanges[2].
Althoughmanysegmentationmethodsforvascularstruc-tureshavebeendeveloped(see[3]foracurrentsurvey),thesegmentationoftheAAAthrombusremainsachallengingThisresearchissupportedinpartbyMAGNETONgrant38652fromtheIsraeliMinistryofTradeandIndustry.
taskduetotheintensityvaluesoverlapoftheaorticwallandtheaneurysmthrombusanditssurroundingtissue(Fig.
1a).
SeveralAAAthrombussegmentationmethodshavebeenre-centlydeveloped.
Theyinclude:1)aninteractivecontourtrackingmethodforaxialslices[4];2)adeformablemodelapproachsteeredbyanonparametricstatisticalgreylevelap-pearancemodelofapriorlumencontourshapesegmentedinteractively[5];3)alevel-setsegmentationbasedonapara-metricstatisticalmodelthatcombinesbothlocalandglobalfeaturesinitializedwitharoughsurface[6],and;4)ade-formableB-splineparametricmodelbasedonanonparamet-ricintensitydistributionmodel[7].
Themaindrawbacksofthesemethodsarethattheyrequiresignicantuserinteractiontoinitializethemodelandne-tunethemodelparametersforsteeringthemodeldeformationprocess.
Oftentimes,theop-timizationprocessconvergestoalocalminimumandthustheresultingsegmentationisnotoptimal.
Thegraphmin-cutmethod[8]isaglobaloptimizationapproachthathasproventobeeffectiveinavarietyofsegmentationtasks,includingvesselslumensegmentation[9,10].
Itclassiesthevoxelnodesthatseparatetheobjectofinterestfromthebackgroundbasedonbothweightedvoxeladjacenciesandpriorintensitymodelsoftheobjectandthebackground.
Theadvantagesofthegraphmin-cutsegmen-tationarethatitisgeneric,nearlyparameter-free,doesnotrequireinitialization,andguaranteesagloballyoptimalso-lution.
However,sincethegraphmin-cutmethodreliesonanintensitymodel,itcannotalwaysdifferentiatebetweentheaorticthrombusanditssurroundingtissue.
Theadditionofgeometricalshapeconstraintcanhelpindiscriminatingandinguidingtheoptimizationtowardsamoreaccurateseg-mentation.
However,incorporatingglobalconstraintssuchasconnectivity[11]orgeometricalparametricshapeconstraintturnsthegraphmin-cutproblemintoanNP-hardproblemforwhichonlyapproximateglobalsolutionsarefeasible.
Inthispaper,wepresentaniterativegraphmin-cutseg-mentationapproachforthesegmentationoftheAAAthrom-busthatusesahybridmodelthatcombinesintensityinfor-mationwithglobalgeometricalparametricmodelconstraint.
Aniterativeapproachisusedtoestimatethelatentmodelandtoperformthesegmentation.
Thiscouplingiterativelycon-strainsthenalglobalshapeofthesegmentedsurface,andthusprovideaccuratesegmentationoftheAAAthrombus.
Experimentalresultson8datasetsshowthatourmethodcansegmenttheAAAthrombusaccuratelyandthatitisrobustandapplicableforroutineclinicaluse.
2.
METHODGivenaCTAvolumeI,werstcomputealumensegmenta-tionandlumencenterlinewiththemethoddescribedin[9].
Basedonthissegmentation,thegoalistoseparatetheAAAthrombus(object)fromthesurroundingstructures(back-ground).
TheseparationisdenedbyalabelingmapMinwhicheachvoxeliislabeledasbeingeitherobjectorback-ground.
Thestandardgraphmin-cutapproach[8]minimizestheenergyfunction:E(M)=Xiφ(Ii|mi)+Xjψ(mi,mj)!
whereφ(Ii|mi)istheprobabilityofvoxelitohavethelabelmibasedonagivenpriorIntensityProbabilityDistributionFunction(IPDF)model,andψ(mi,mj)representstheprob-abilitythatvoxelianditsneighborvoxelsjhavedifferentlabelsbasedontheintensitydifferencebetweenthem.
Themodeldenedbythisfunctionhasseveraldrawbacks:1)thepriorintensitymodelφ(Ii|mi)doesnotincludeglobalshapeinformationoftheobject;2)itscomputationrequiresintensiveuserinteracton;and3)theestimatedintensitymodelaccuracyislimited.
Forthespecictaskofthrombussegmen-tation,amodelthatonlyreliesonintensitydistributioncannotproperlyseparatebetweenthethrombusanditssurroundingtissue(Fig.
1).
Toovercomethesedrawbacks,weproposetouseahybridmodelthatconsistsofbothintensityandglobalgeometricalshapeconstraintinaprobabilisticframeworkthatcombinesbothmodelestimationandobjectsegmentation.
Ourmodelisdenedusingthefollowingenergyfunction:E(M,Θ)=Xiφ(Ii|mi)·ψ(mi|Θ)+Xjψ(mi,mj|Θ)!
whereΘisageometricalparametricmodeldescribestheglobalshapeoftherequiredobject.
Theprobabilitythatvoxelihasthelabelmibasedontheintensitymodelφ(Ii|mi)isnowmultipliedbyψ(mi|Θ)whichdescribesprobabilitythatthevoxelhavethelabelmibasedonestimatedgeometricalmodel,andψ(mi,mj|Θ)describestheprobabilitythatvox-elsiandjhavedifferentlabels,consideringboththeintensitydifferencebetweenthevoxelsandtheirspatiallocationwithrespecttotheestimatedgeometricalmodelΘ.
SinceΘisunknown,thisfunctioncannotbedirectlymin-imized.
Instead,weuseatwo-stepiterativeapproach[12]:1234567(a)originalimage(b)initialmin-cut(c)modeltting(d)nalresultFig.
1.
IllustrationofthesegmentationprocessonaclinicalaxialCTAsliceofanaorticthrombus:(a)originalslicewiththefollowinganatomy:1)aorticlumen,2)aorticthrombus,3)InferiorVenaCava(IVC),4)rightpsoasmuscle,5)leftpsoasmuscle,6)vertebrae,7)thesmallbowel;(b)theinitialmin-cutsegmentation;(c)parametricmodelttedto(b),and;(d)nalresult,aftertheiterativeprocess,combinedbothlumenandthrombussegmentationresults.
1.
EstimationofthelabelingmapMwhileassumingaxedgeometricparametricmodelΘ2.
UpdateofthegeometricalparametricmodelΘandtheobjectintensitymodelφ(Ii|mi)withthelabelingmapM.
Thetwostepsareiterateduntilconvergence,i.
e.
,untiltheMandΘdonotchangeanymore.
Wedescribethetwostepsindetailnext.
2.
1.
LabelingmapestimationThelabelingmapMiscomputedusingthegraphmin-cuttechniqueasfollows.
LetG=(V,E)betheimagegraph,wherethegraphnodesdeneasV={v1,.
.
.
vn,vs,vt}suchthatnodevicorrespondstovoxeliandterminalnodesvsandvtcorrespondtotheobjectandbackgroundclasses.
ThegraphedgesE={(vi,vs),(vi,vt),(vi,vj)}consistofthreegroups:1)edges(vi,vs)fromvoxelstotheobjectterminalnode;2)edges(vi,vt)fromvoxelstothebackgroundtermi-nalnode,and;3)edges(vi,vy)betweenadjacentvoxels(4or8neighborsfor2Dimages,6or26neighborsfor3Dim-ages).
Thecostofacut|C|thatdividesthegraphintotheobjectclass(sourcevertex)andthebackgroundclass(targetvertex)isdenedasthesumoftheweightsofthecutedgese∈C.
Thesegmentationisthebipartitegraphpartitionthatminimizesthecostofthecutbetweenthetwoparts.
Edgeweightsareassignedasfollows.
Edgeweightsw(vi,vs)representtheposteriorprobabilitythatvoxelviisrelatedtothethrombus(object)basedonahybridmodelintensityandgeometricconstraintsmodel:w(vi,vs)=φ(Ii|mo)·ψ(mi=mo|Θ)whereφ(Ii|mo)istheprobabilitythatthevoxelibelongstotheobjectclassmobasedonthevoxelintensityandobjectIPDF.
Thetermψ(mi=mo|Θ)istheprobabilitythatvoxellabelmiistheobjectlabelmogiventheestimatedgeometri-calmodelΘ.
Edgeweightsw(vi,vt)representtheprobabilityofeachvoxeltobelongtobackgroundclass.
Sincewedonothaveapriormodelforthebackground,wedeneitasthecomple-mentoftheobjectpriormodel:w(vi,vt)=1w(vi,vs)Edgeweightsw(vi,vj)representtheprobabilityoftheseedgetorepresentthesurfacediscriminatebetweentheobjectandthebackground.
ItisbasedonacombinationofthelocalgradientmagnitudeandthespatiallocationoftheedgewithrespecttotheestimatedgeometricalmodelΘ:w(vi,vj)=exp(IiIj)2σ·ψ(mi,mj|Θ)whereσisanormalizationconstant,andψ(mi,mj|Θ)rep-resentstheprobabilitythatthevoxelsiandjhavedifferentlabelsgiventheestimatedgeometricalmodel.
2.
2.
GeometricalparametricmodelttingGivenaninitialsegmentation,thenextstepistotthegeo-metricalparametricmodelΘtoit.
Basedontheobservationsin[4],theabdominalaorticthrombuscanbemodeledasasetof2Daxialellipsoids.
Thus,foreachaxialslice,wetanellipsoidusingtheIterativeClosestPointapproach[13].
Thettingalgorithmconsistsofthreesteps:1.
CollectasetofpointsPonthesegmentationsurfacebycomputingtheintersectionbetweenthatsurfaceand360rayscenteredontheprevioussliceellipsoidcenterpoint.
2.
Computethedistancefromeachpointpi∈Ptothees-timatedellipsoidsurfaceusingEuclidiandistancemaprepresentationofthesurface[14].
3.
Fita2DparametricellipsoidtothesetofpointsPusingTaubin'sleast-squaresmethod[15].
Steps2and3areappliediteratively,whereoneachit-eration,onlythenclosestpointstothecomputedellipsoid(a)Axialview(b)Sagittalview(c)Coronalview(d)3Dview(e)3DviewFig.
2.
AAAthrombussegmentationresults.
(a)-(c)2Dslicesofdifferentpatientswithandwithoutstentplacement.
There-sultedlumenandthrombuscontour(red)withthemanualseg-mentationcontour(green)areoverliedontheoriginalCTAslice.
(d)-(e)3Dsurfacerenderingsshowthelumen(red)andthethrombus(green)oftheresultedsegmentations.
Addi-tionalimagesandmoviescanbefoundin:http://www.
cs.
huji.
ac.
il/freiman/AAAremaininP.
Thismethodprovidesrobustandaccuratet-tingofaparametricmodeltotheobservedpointsset.
Sincethedifferencesbetweennearbyslicesarerelativelysmall,theestimatedmodelforslicezisusedtoinitializethettingal-gorithmforslicez+1.
Thecouplingofmin-cutsegmentationandglobalgeomet-ricalmodelttingyieldsarobustandaccuratemethodthatsegmentthethrombussuccessfullyfordifferentdatasetswithvaryingthrombussizeandlocations.
3.
EXPERIMENTALRESULTSWeevaluatedtheperformanceofourmethodbyautomati-callysegmenting8AAACTAdatasets.
TheCTAshad512*512*500voxelswithvariousphysicalvoxelsize(range0.
7-1.
2mm).
Thedatasetsincludedvarioussizesandlocationsofthethrombus.
Someofthemacquiredafterstentplacement,andthusincludestrongstreakingartifacts.
Ground-truthsegmen-tationsofthethrombusforeachdatasetwasobtainedman-uallybyaclinicalradiologist.
Foreachthrombus,theuserprovidedtwoseedsforthelumensegmentation[9].
Then,theautomaticthrombussegmentationalgorithmwasapplied.
Fig.
2presentsourmethod'sresultsonseveralrepresen-tativecases.
Notethatourmethodsuccessfullyseparatedbe-tweenthethrombusandthesurroundingstructuressuchasveins,muscles,andfat.
Bothvolumetric(1-2),andsurface(3)basedmeasureswereusedtoevaluateourmethod'sperformance.
Themean(std)valueswere:(1)absolutevolumedifference8.
04%(7.
03%);(2)volumetricoverlaperror12.
86%(std=4.
33%);(3)averagesymmetricsurfacedistance1.
46mm(0.
39mm).
Themeanrunningtimeforentiresegmentation,includ-ingbothlumenandthrombussegmentationwas150sec(std=25sec)onastandardPC(dual-core2.
0GHZproces-sorand4GBofmemory).
Theseresultsarecomparablewithpreviouslyreportedinterobservererrors[4],whilemuchlessuserinteractionisrequiredcomparedtopreviouslysuggestedmethods[7,4,5].
4.
CONCLUSIONSWehavepresentedanautomaticmethodfortheaccurateseg-mentationofAAAthrombus,givenaninitiallumensegmen-ration.
Ourapproachappliediteratively,intensitybasedgraphmin-cutsegmentationconstrainedbyparametricmodelttedtoprevioussegmentationresult.
Thettedmodelconstrainedthegraphmin-cutsegmentationfromleakingtothethrombusnearbystructuressuchastheveinsandmuscles.
Ourexper-imentalresultsshowthatthetoolisaccurate,iseasytouse,andisrobusttovaryingthrombuslocationsandsizes,forbothdatasetswithandwithoutstents.
5.
REFERENCES[1]S.
C.
Whitaker,"Imagingabdominalaorticaneurysmbe-foreandafterendoluminalstent-graftrepair,"Eur.
J.
Radiol.
,vol.
39,pp.
3–15,2001.
[2]B.
Kritpracha,H.
G.
Beebe,andA.
J.
Comerota,"Aor-ticdiameterisaninsensitivemeasurementofearlyaneurysmexpansionafterendografting,"J.
Endovasc.
Ther.
,vol.
11,no.
2,pp.
184–190,2004.
[3]D.
Lesage,E.
D.
Angelini,I.
Bloch,andG.
Funka-Lea,"AReviewof3DVesselLumenSegmentationTechniques:Models,FeaturesandExtractionSchemes,"Med.
ImageAnal.
,vol.
InPress,2009.
[4]M.
deBruijne,B.
vanGinneken,M.
A.
Viergever,andW.
J.
Niessen,"InteractivesegmentationofabdominalaorticaneurysmsinCTAimages,"Med.
imageanal.
,vol.
8,no.
2,pp.
127–138,2004.
[5]S.
D.
Olabarriagaandetal,"SegmentationofthrombusinabdominalaorticaneurysmsfromCTAwithnonpara-metricstatisticalgreylevelappearancemodeling,"IEEETrans.
Med.
Imaging,,vol.
24,no.
4,pp.
477–485,2005.
[6]F.
Zhuge,G.
D.
Rubin,S.
Sun,andSNapel,"Anab-dominalaorticaneurysmsegmentationmethod:Levelsetwithregionandstatisticalinformation,"Med.
Phys.
,vol.
33,no.
5,pp.
1440–1453,2006.
[7]S.
Demirci,G.
Lejeune,andN.
Navab,"Hybridde-formablemodelforaneurysmsegmentation,"inIEEEInt.
Symp.
onBiomedicalImaging:FromNanotoMacro,ISBI'2009,2009.
[8]Y.
BoykovandG.
Funka-Lea,"GraphCutsandEfcientN-DImageSegmentation,"Int.
J.
ofComp.
Vision,vol.
70,no.
2,pp.
109–131,2006.
[9]M.
Freiman,N.
Broide,M.
Natanzon,L.
Weizman,E.
Nammer,O.
Shilon,J.
Frank,L.
Joskowicz,andSosna.
J.
,"Vessels-Cut:agraphbasedapproachtocarotidarteriespatient-specicmodeling,"in2ndwork-shopon:3DPhysiologicalHuman3DPH'2009,2009,vol.
5903ofLNCS,pp.
1–12.
[10]GulsunM.
A.
andH.
Tek,"SegmentationofCarotidAr-teriesByGraph-CutsUsingCenterlineModels,"in3DSegmentationintheClinic:CarotidLumenSegmenta-tionandStenosisGradingChallenge,R.
Hameeteman,M.
Zuluaga,L.
Joskowicz,M.
Freiman,andT.
vanWal-sum,Eds.
,2009,http://cls2009.
bigr.
nl.
[11]S.
Vicente,V.
Kolmogorov,andC.
Rother,"Graphcutbasedimagesegmentationwithconnectivitypriors,"inIEEEConf.
Comp.
Vis.
andPatt.
Rec.
CVPR'2008,2008.
[12]M.
P.
Kumar,P.
H.
S.
Torr,andA.
Zisserman,"OBJCUT,"inIEEEConf.
Comp.
Vis.
andPatt.
Rec.
CVPR'2005,2005.
[13]P.
J.
BeslandH.
D.
McKay,"Amethodforregistrationof3-Dshapes,"IEEETrans.
Patt.
Anal.
andMach.
Intell.
,vol.
14,no.
2,pp.
239–256,1992.
[14]C.
R.
Maurer,Q.
Rensheng,andV.
Raghavan,"AlineartimealgorithmforcomputingexactEuclideandistancetransformsofbinaryimagesinarbitrarydimensions,"IEEETrans.
Patt.
Anal.
andMach.
Intell.
,vol.
25,no.
2,pp.
265–270,2003.
[15]G.
Taubin,"EstimationOfPlanarCurves,SurfacesAndNonplanarSpaceCurvesDenedByImplicitEqua-tions,WithApplicationsToEdgeAndRangeImageSegmentation,"IEEETrans.
Patt.
Anal.
andMach.
In-tell.
,vol.
13,no.
11,pp.
1115–1138,1991.