nozF.L.Valverde,N.Guil,J.Mu˜
Q.Li,M.Aoyama,K.DoiKurtRossmanLaboratories
DepartmentofRadiologyTheUniversityofChicago,USA
resultsshowthatournewdeformablemodelisabletoseg-mentobjectsinnoisyimages.Finally,inSection5,conclu-sionsarepresented.
2.DEFORMABLEMODELSFORSEGMENTATIONThedeformablemodelscanbeclassifiedintofourcategories[7]:
1Parametricallydeformablemodels,whichareessen-tially2Dinnatureandaidinthesegmentationofim-ageslices.TheapproachisbasedonellipticFourierdecompositionasproposedbyStaibandDuncan[8]2Energyminimizingsnakesareattractedtoimagefea-turessuchaslinesandedges,whereasinternalsplineforcesimposeasmoothnessconstraint,asdescribedbyKassetal.[1].Someinterestingextensionstothisinitialworkcanbefoundin[9,10,11,12].
33Ddeformablesurfaces,usedbyCohenetal.[13]wheredeformablemodelsthatdeformundertheac-tionofinternalforces,suchaselasticpropertiesofthesurface,andexternalforcesattractingthesurfacetowarddetectededgeelements.
4Deformablesuperquadrics,proposedbyTerzopoulosandMetaxas,[14],anddeformablegeneralizedcylin-ders,proposedbyO’DonnelandGupta[15],whichincorporateglobalshapeparametersofasuperellip-soidandgeneralizedcylinder,respectively,andlocaldegreesoffreedombasedonelasticpropertiesandactionofexternalforces.Thesemodelscanbeusedforextractinggrossshapefeaturesfromvisualdata,whichcanbeusedforindexingontoadatabaseofstoredmodelstoprovideshaperecognition.Localde-formationhelpsinreconstructingthedetailsofcom-plexshapestoprovideshapereconstruction.Themethodologyproposedinthispaperisincludedinthesecondcategory.
(1)DepartmentofComputerScience(2)DepartmentofComputerArchitecture
UniversityofMalaga,Spain
ABSTRACT
Deformable-model-basedsegmentationtechniquescanovercomesomelimitationsofthetraditionalimageprocess-ingtechniques.Currentlydevelopeddeformablemodelscancopewithgapsandanotherirregularitiesinobjectbound-aries.However,theypresentproblemsinnoisyimages.Ourapproach,presentedinthispaper,isabletosegmentobjectsinnoisyimagesbydefininganewenergyfunctionassoci-atedwithimagenoiseandavoidingthetendencyofcontourpointstobunchup.Themodelisvalidatedforvesselseg-mentationonmammograms.
1.INTRODUCTION
Adeformable-model-basedsegmentationschemecanover-comemanyofthelimitationsoftraditionalsegmentationtechniques.Continuousgeometricmodelsconsideranob-jectboundaryasawholeandcanmakeuseofaprioriknowl-edgeofobjectshapetoconstrainthesegmentationprob-lem.Theinherentcontinuityandsmoothnessofthemodelscancompensateforgapsandotherirregularitiesinobjectboundaries.Furthermore,theparametricrepresentationsofthemodelsprovideacompactandanalyticaldescriptionoftheobjectshape.
Snakes[1]representaspecialcaseofthegeneralmulti-dimensionaldeformablemodeltheory[2].Snake-basedal-gorithmstypicallyusedynamicprogramming(DP)inordertominimizeanenergyexpression.SeveralmethodsbasedonDPhavebeenpublishedbyAminietal.[3],Popeetal.[4],WilliamsandShah[5],andGeigerandKogler[6],butnoneofthemisapplicabletonoisyimages.Wewillpresentanewapproachbasedthatisadequateforsegmentingob-jectsinnoisyimages.
Thispaperisorganizedasfollows.Inthenextsectionabriefreviewofpreviousworkondeformablemodelsinseg-mentationisgiven.Thelimitationsoftheseproposedmeth-odsandsomeopenproblemsarepointedout.Ournewap-proachtoadeformable-model-basedsegmentationschemeispresentedinSection3,whereanewenergyfunctionforsegmentationinnoisyimagesisdescribed.InSection4the
0-7803-6725-1/01/$10.00 ©2001 IEEE82
2.1.Relatedwork
Aminietal[3]appliedaniterativealgorithmwhere,ateachstep,DPwasemployedtominimizethecurrentenergy,byallowingjustsmallchangesinthesnake.Thisapproachpermitstheinclusionofhardconstraintsinadditiontosoftconstraints.However,themethodhashighcomputationalcomplexity.Otherapproaches,likethatofPopeetal.[4],restrictthetypeofcontourthatcanbeused.WilliamsandShah[5]presentedafastalgorithmforactivecontours.Their”greedy”algorithmhasaperformancecomparabletody-namicprogrammingandvariationalcalculusapproaches.Thesepreviousmethodsalsohavesomecommonlim-itations,andseveralgeneralproblemscanbepointedout.First,theinitialapproachbyKassetal.[1]hassomeprob-lems,suchasnumericalinstabilityandatendencyforpointsto’bunchup’ondenseportionsofedgecontours.Theap-proachofAminietal.[3]ismorestableandsolvestheproblemof’bunchup’,butitisveryslow.ThebunchupproblemisalsosolvedwiththealgorithmofWilliamsandShah,buttheactivecontourdoesnotshrinkwhenthefunc-tionenergyisminimized.Second,acarefulcontourini-tializationisnecessaryintheabovementionedmethodsinordertoobtainagoodfinalresult.Infact,theapplicationofWilliamsandShah’salgorithm[5]producesbadsegmenta-tionresultsiftheinitialcontourisnotclosetotheedgesoftheobject.Third,noneoftheseapproachesareapplicabletonoisyimagesbecausenoisyregionsareconsideredapartoftheedgeofanobject.Thiscancauseerroneousobjectsegmentation.
3.DESCRIPTIONOFANEWDEFORMABLE
MODELIntheinitialapproachofKassetal.thecontourisrepre-sentedbyavector,,whereisthearclength.Theenergyalongthesnakeiscalculatedasfollows:
Fig.1.Processofmoving
to
3.1.Solvingthe’bunchup’problem
Inourdeformablemodelanewapproach,basedondynamicprogramming,isusedtoavoidthetendencyofpointsto’bunchup’ondenseportionsofacontour.Thus,thedis-tancebetweenconsecutivecontourpointsisevaluatedateachstep,anddeviationsfromthemeandistancehigherthanathresholdarenotallowed.Inthefollowing,theex-pressionstoimplementthisnewconditionindynamicpro-grammingarepresented.Letbeadiscreteandclosedcontourofpoints,with=.Themeandis-tanceisdefinedas:
(2)
representsthepositionofapointIf
asfollows:wecandefine
attime,
(3)
andisthepointwiththehighestwhere
valueforthegradientoftheenergyfunction,withinacircleofradiuscenteredatpoint.Inaddition,theexpression
functionisforthe
(1)
(4)
isavectorofmagnitudeandhavingthewhere
.Figure1illustratesthevaluessamedirectionas
thatthepreviouslydefinedfunctionstakeinastepofthealgorithm.Noticethatparametercontrolsthedegreeofuniformityinthedistancebetweenpoints.Thesmallerthevalueof,themoreevenlyspacedarethepoints.When=0,thepointsareasevenlyspacedaspossible.
representstheinternalenergyofthecontourwhere
duetobendingordiscontinuities,isrelatedtoim-indicatestheexternalconstraints.Theageforces,and
imageforcescanbeduetovariouseventsaslines,edges,orterminations[1].Theinternalsplineenergyisrepresentedbyafirst-order-termwhichgenerateslargervaluesincurvegaps.Thesecond-ordercontinuitytermtakeslargervalueswherethecurveisbendingrapidly.Theandcoefficientsareusedtodeterminethestrengthtowhichthecontourisal-lowedtostretchorbendatapoint.
3.2.Noiseproblem
Noisedetectioncanbecarriedoutbyincorporationofglobalpixelinformation.Forthispurpose,wedefineanewenergy
83
term,
,asfollows:
(5)
whereistheprobabilityofhavinglocalnoiselocatedatpoint.
isbasedontheThedefinitionofthefunction
noisefeaturesofaparticularapplication.Inthiswork,weareapplyingsnaketechniquestoimagesfrommammogramswherethemajorityofthenoiseisproducedbysmallar-tifacts.Thus,twoassumptionshavebeenmade:noiseisspreadalongsmallregionsontheimage,andtheseregionsarefarenoughfromtheobjecttobesegmentedorarean-othernoisyregion.
isdefinedas:Function
.Else-assignedtotheprobabilityif
where,thepointisassociatedwithanoisyregion.Figure2illustratesdifferentsituationsforthecalculationof.
valueisincludedasaterminthegen-Thenew
eralexpressionofthesnakeenergy:
(7)
Thisnewtermeliminatestheattractionthatsmallnoisere-gionscauseonthesnake.
(6)
calculatesthenumberofclusters
withthatappearonacircumferencecenteredat
radius.Theseclustersaregeneratedbybinarizing(withathreshold)theoriginalimagewithinthede-finedcircleandeliminatingallthepointsonthecir-cumferencethatarenotconnectedtothecenter.
isthevalueofthecurvatureinthecon-.touratthepoint
isathresholdforandisusedtodiscrim-inatebetweensmallregionsofnoiseandsmallgapsontheedgesoftheobject.Thefurthertheregionsofnoisearefromtheobject,thelargerthecurvature
.Inthisway,smallgapsontheobjectatpoint
edgecanbedistinguishedfromnoisyregions.
Fig.3.a)Initialcontour,b)after20iterations,c)40itera-tions,d)60iterations,e)80iterations,f)100iterations,g)118iterations.
4.RESULTS
Thenewapproachtodeformablecontoursegmentationhasbeenvalidatedinadatabaseofmammogramsbydetectingvesselsontheimages.Asinitialcontour,acircumferencethatcircumscribestheimageisused.InFigure3,thestepsofouralgorithmareshown.
Inaddition,otherresultsarepresentedinFigure4.Theseimageshaveasizeof128x128pixelswith256graylevels.
valuesForapplicationofourtechnique,thesameand
havebeenemployedinalltheimages.Valuesof10and90havebeenusedforand,respectively.
Mostcasesdriventoaprecisedetectionofthevessel.Eveninsomedifficultcircumstances,asthatinFigure4.e,
Fig.2.Computationof
¿Fromequation6,apointcorrespondstoanoisyre-gion(probabilityequalto1)ifnoclustersaredetectedon
.Avalueof0.5isthecircumference,and
84
theresultsareacceptable.However,baddetectionswereperformedinsomesituationsduetolimitationsonthenoisemodel(Figures4.g,h,i).
Currently,wearestudyingimprovementsofthenoisemodelinordertoavoidsituationsthatcausebadsegmenta-tions.
[2]D.Terzopoulos,“Regularizationofinversevisualproblems
involvingdiscontinuities,”IEEETrans.PatternAnal.Ma-chineIntelligence,vol.8,no.4,pp.413–424,1986.[3]A.Amini,T.Weymouth,andR.Jain,“Usingdynamicpro-grammingforsolvingvariationalproblemsinvision,”IEEETrans.PatternAnal.MachineIntelligence,vol.12,no.9,pp.885–867,1990.[4]D.Pope,D.Parker,C.Clayton,andDGustafason,“Left
ventricularborderrecognitionusingadynamicsearchalgo-rithm,”Radiology,vol.155,no.2,pp.513–517,1985.[5]D.WilliamsandM.Shah,“Afastalgorithmforactivecon-toursandcurvatureestimation,”CVGIP:ImageUnderstand-ing,vol.55,no.1,pp.14–26,1991.[6]D.GeigerandJ.Kogler,“Scallingimagesandimagefeatures
viathenormalizationgroup,”Proc.IEEEConf.ComputerVisionandPatternRecognition,1993.[7]R.AcharyaandR.P.Menon,“Areviewofbiomedicalseg-mentationtechniques,”DeformableModelsinMedicalIm-ageAnalysis.IEEEComputerSociety,pp.140–161,1998.[8]L.H.StaibandJ.S.Duncan,“Boundaryfindingwithpara-metricdeformablemodels,”IEEETrans.PatternAnal.Ma-chineIntelligence,vol.14,pp.1061–1075,1992.[9]A.BlakeandR.Cipollo,“Thedynamicanalysisofapparent
contours,”FirstECCV.Spinger-Verlag,pp.73–82,1990.[10]A.P.PentlandandB.Horowitz,“Rcoveryofnonrigidmotion
andstructure,”IEEETrans.PatternAnal.MachineIntelli-gence,vol.13,no.7,July1991.[11]A.P.PentlandandJ.R.Willians,“Goodvibrations:Modal
dynamicsforgraphicsandanimation,”Proc.ACMSIG-GRAPH,,pp.215–222,1989.[12]A.YuilleandP.Hallinan,“Deformabletemplates,”Active
Vision,MITPress,Cambirdge,Mass,1992.
Fig.4.Resultsfornineimages
5.CONCLUSIONS
Anewapproachtoimagesegmentationbasedonadeformablecontourmodelhasbeenpresented.Anewconditionhasbeenaddedtothedynamicprogrammingalgorithminordertoavoidthebunchupproblem.Inaddition,anewtermofenergyhasbeenintroducedintotheglobalenergycompu-tation.Thistermidentifiesthenoiseassociatedwithimageregionsandallowsthesnaketokeepawayfromnoiseat-traction.
6.ACKNOWLEDGEMENT
TheauthorsaregratefultoMrs.Lanzlforeditingthedocu-ment.
7.REFERENCES
[1]M.Kass,A.Witkin,andD.Terzopoulus,“Snakes:Active
contourmodels,”Int.J.Comput.Vision,vol.1,no.4,pp.321–331,1988.
[13]I.Cohen,L.D.Cohen,andN.Ayache,“Usingdeformable
surfacestosegement3-dimagesandinterdifferentialstruc-tures,”CVGIP:ImageUnderstanding,vol.56,no.2,pp.242–263,1992.[14]D.TerzopoulosandD.Metaxas,“Dynamic3dmodelswith
localandglobaldeformations:Deformablesuperquadrics,”IEEETrans.PatternAnal.MachineIntelligence,vol.13,no.7,pp.703–714,July1991.[15]T.etalO’Donnel,“Extrudedgeneralizedcylinder:Ade-formablemodelforobjectrecovery,”Proc.CVPR,IEEEComputerSocietyPress,LosAlamitos,Calif.,1994.
85
因篇幅问题不能全部显示,请点此查看更多更全内容