数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.docx

数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.docx

《数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.docx》由会员分享，可在线阅读，更多相关《数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.docx（11页珍藏版）》请在冰点文库上搜索。

数字图像处理外文翻译外文文献英文文献数字图像处理

数字图像处理外文翻译外文文献英文文献数字图像处理

DigitalImageProcessing

1Introduction

Manyoperatorshavebeenproposedforpresentingaconnectedcomponentnadigitalimagebyareducedamountofdataorsimpliedshape.Ingeneralwehavetostatethatthedevelopment,choiceandmodi_cationofsuchalgorithmsinpracticalapplicationsaredomainandtaskdependent,andthereisno\bestmethod".However,itisinterestingtonotethatthereareseveralequivalencesbetweenpublishedmethodsandnotions,andcharacterizingsuchequivalencesordi_erencesshouldbeusefultocategorizethebroaddiversityofpublishedmethodsforskeletonization.Discussingequivalencesisamainintentionofthisreport.

1.1CategoriesofMethods

Oneclassofshapereductionoperatorsisbasedondistancetransforms.Adistanceskeletonisasubsetofpointsofagivencomponentsuchthateverypointofthissubsetrepresentsthecenterofamaximaldisc（labeledwiththeradiusofthisdisc）containedinthegivencomponent.Asanexampleinthis_rstclassofoperators,thisreportdiscussesonemethodforcalculatingadistanceskeletonusingthed4distancefunctionwhichisappropriatetodigitizedpictures.Asecondclassofoperatorsproducesmedianorcenterlinesofthedigitalobjectinanon-iterativeway.Normallysuchoperatorslocatecriticalpoints_rst,andcalculateaspeci_edpaththroughtheobjectbyconnectingthesepoints.

Thethirdclassofoperatorsischaracterizedbyiterativethinning.Historically,Listing[10]usedalreadyin1862thetermlinearskeletonfortheresultofacontinuousdeformationofthefrontierofaconnectedsubsetofaEuclideanspacewithoutchangingtheconnectivityoftheoriginalset,untilonlyasetoflinesandpointsremains.Manyalgorithmsinimageanalysisarebasedonthisgeneralconceptofthinning.Thegoalisacalculationofcharacteristicpropertiesofdigitalobjectswhicharenotrelatedtosizeorquantity.Methodsshouldbeindependentfromthepositionofasetintheplaneorspace,gridresolution（fordigitizingthisset）ortheshapecomplexityofthegivenset.Intheliteraturetheterm\thinning"isnotused

-1-

inauniqueinterpretationbesidesthatitalwaysdenotesaconnectivitypreservingreductionoperationappliedtodigitalimages,involvingiterationsoftransformationsofspeci_edcontourpointsintobackgroundpoints.AsubsetQ_Iofobjectpointsisreducedbyade_nedsetDinoneiteration,andtheresultQ0=QnDbecomesQforthenextiteration.Topology-preservingskeletonizationisaspecialcaseofthinningresultinginaconnectedsetofdigitalarcsorcurves.Adigitalcurveisapathp=p0;p1;p2;:

:

:

;pn=qsuchthatpiisaneighborofpi?

1,1_i_n,andp=q.Adigitalcurveiscalledsimpleifeachpointpihasexactlytwoneighborsinthiscurve.Adigitalarcisasubsetofadigitalcurvesuchthatp6=q.Apointofadigitalarcwhichhasexactlyoneneighboriscalledanendpointofthisarc.Withinthisthirdclassofoperators（thinningalgorithms）wemayclassifywithrespecttoalgorithmicstrategies:

individualpixelsareeitherremovedinasequentialorderorinparallel.Forexample,theoftencitedalgorithmbyHilditch[5]isaniterativeprocessoftestinganddeletingcontourpixelssequentiallyinstandardrasterscanorder.AnothersequentialalgorithmbyPavlidis[12]usesthede_nitionofmultiplepointsandproceedsbycontourfollowing.Examplesofparallelalgorithmsinthisthirdclassarereductionoperatorswhichtransformcontourpointsintobackgroundpoints.Di_erencesbetweentheseparallelalgorithmsaretypicallyde_nedbytestsimplementedtoensureconnectednessinalocalneighborhood.Thenotionofasimplepointisofbasicimportanceforthinninganditwillbeshowninthisreportthatdi_erentde_nitionsofsimplepointsareactuallyequivalent.SeveralpublicationscharacterizepropertiesofasetDofpoints（tobeturnedfromobjectpointstobackgroundpoints）toensurethatconnectivityofobjectandbackgroundremainunchanged.Thereportdiscussessomeofthesepropertiesinordertojustifyparallelthinningalgorithms.

1.2Basics

Theusednotationfollows[17].AdigitalimageIisafunctionde_nedonadiscretesetC,whichiscalledthecarrieroftheimage.TheelementsofCaregridpointsorgridcells,andtheelements（p;I（p））ofanimagearepixels（2Dcase）orvoxels（3Dcase）.Therangeofa（scalar）imageisf0;:

:

:

GmaxgwithGmax_1.Therangeofabinaryimageisf0;1g.WeonlyusebinaryimagesIinthisreport.LethIibethesetofallpixellocationswithvalue1,i.e.hIi=I?

1

（1）.Theimagecarrierisde_nedonanorthogonalgridin2Dor3D

-2-

space.Therearetwooptions:

usingthegridcellmodela2Dpixellocationpisaclosedsquare（2-cell）intheEuclideanplaneanda3Dpixellocationisaclosedcube（3-cell）intheEuclideanspace,whereedgesareoflength1andparalleltothecoordinateaxes,andcentershaveintegercoordinates.Asasecondoption,usingthegridpointmodela2Dor3Dpixellocationisagridpoint.

Twopixellocationspandqinthegridcellmodelarecalled0-adjacenti_p6=qandtheyshareatleastonevertex（whichisa0-cell）.Notethatthisspeci_es8-adjacencyin2Dor26-adjacencyin3Difthegridpointmodelisused.Twopixellocationspandqinthegridcellmodelarecalled1-adjacenti_p6=qandtheyshareatleastoneedge（whichisa1-cell）.Notethatthisspeci_es4-adjacencyin2Dor18-adjacencyin3Difthegridpointmodelisused.Finally,two3Dpixellocationspandqinthegridcellmodelarecalled2-adjacenti_p6=qandtheyshareatleastoneface（whichisa2-cell）.Notethatthisspeci_es6-adjacencyifthegridpointmodelisused.AnyoftheseadjacencyrelationsA_,_2f0;1;2;4;6;18;26g,isirreexiveandsymmetriconanimagecarrierC.The_-neighborhoodN_（p）ofapixellocationpincludespandits_-adjacentpixellocations.Coordinatesof2Dgridpointsaredenotedby（i;j）,with1_i_nand1_j_m;i;jareintegersandn;marethenumbersofrowsandcolumnsofC.In3Dweuseintegercoordinates（i;j;k）.Basedonneighborhoodrelationswede_neconnectednessasusual:

twopointsp;q2Care_-connectedwithrespecttoM_CandneighborhoodrelationN_i_thereisasequenceofpointsp=p0;p1;p2;:

:

:

;pn=qsuchthatpiisan_-neighborofpi?

1,for1_i_n,andallpointsonthissequenceareeitherinMorallinthecomplementofM.AsubsetM_Cofanimagecarrieriscalled_-connectedi_MisnotemptyandallpointsinMarepairwise_-connectedwithrespecttosetM.An_-componentofasubsetSofCisamaximal_-connectedsubsetofS.Thestudyofconnectivityindigitalimageshasbeenintroducedin[15].ItfollowsthatanysethIiconsistsofanumberof_-components.Incaseofthegridcellmodel,acomponentistheunionofclosedsquares（2Dcase）orclosedcubes（3Dcase）.Theboundaryofa2-cellistheunionofitsfouredgesandtheboundaryofa3-cellistheunionofitssixfaces.Forpracticalpurposesitiseasytouseneighborhoodoperations（calledlocaloperations）onadigitalimageIwhichde_neavalueatp2Cinthetransformedimagebasedonpixel

-3-

valuesinIatp2CanditsimmediateneighborsinN_（p）.

2Non-iterativeAlgorithms

Non-iterativealgorithmsdeliversubsetsofcomponentsinspeciedscanorderswithouttestingconnectivitypreservationinanumberofiterations.Inthissectionweonlyusethegridpointmodel.

2.1\DistanceSkeleton"Algorithms

Blum[3]suggestedaskeletonrepresentationbyasetofsymmetricpoints.InaclosedsubsetoftheEuclideanplaneapointpiscalledsymmetrici_atleast2pointsexistontheboundarywithequaldistancestop.Foreverysymmetricpoint,theassociatedmaximaldiscisthelargestdiscinthisset.Thesetofsymmetricpoints,eachlabeledwiththeradiusoftheassociatedmaximaldisc,constitutestheskeletonoftheset.Thisideaofpresentingacomponentofadigitalimageasa\distanceskeleton"isbasedonthecalculationofaspeci_eddistancefromeachpointinaconnectedsubsetM_Ctothecomplementofthesubset.Thelocalmaximaofthesubsetrepresenta\distanceskeleton".In[15]thed4-distanceisspeciedasfollows.De_nition1Thedistanced4（p;q）frompointptopointq,p6=q,isthesmallestpositiveintegernsuchthatthereexistsasequenceofdistinctgridpointsp=p0,p1;p2;:

:

:

;pn=qwithpiisa4-neighborofpi?

1,1_i_n.

Ifp=qthedistancebetweenthemisde_nedtobezero.Thedistanced4（p;q）hasallpropertiesofametric.Givenabinarydigitalimage.Wetransformthisimageintoanewonewhichrepresentsateachpointp2hIithed4-distancetopixelshavingvaluezero.Thetransformationincludestwosteps.Weapplyfunctionsf1totheimageIinstandardscanorder,producingI_（i;j）=f1（i;j;I（i;j））,andf2inreversestandardscanorder,producingT（i;j）=f2（i;j;I_（i;j））,asfollows:

f1（i;j;I（i;j））=

8><>>:

0ifI（i;j）=0

minfI_（i?

1;j）+1;I_（i;j?

1）+1g

ifI（i;j）=1andi6=1orj6=1

-4-

m+notherwise

f2（i;j;I_（i;j））=minfI_（i;j）;T（i+1;j）+1;T（i;j+1）+1g

TheresultingimageTisthedistancetransformimageofI.NotethatTisasetf[（i;j）;T（i;j）]:

1_i_n^1_j_mg,andletT__Tsuchthat[（i;j）;T（i;j）]2T_i_noneofthefourpointsinA4（（i;j））hasavalueinTequaltoT（i;j）+1.Forallremainingpoints（i;j）letT_（i;j）=0.ThisimageT_iscalleddistanceskeleton.Nowweapplyfunctionsg1tothedistanceskeletonT_instandardscanorder,producingT__（i;j）=g1（i;j;T_（i;j））,andg2totheresultofg1inreversestandard