数字图像处理外文资料翻译Word格式文档下载.docx

数字图像处理外文资料翻译Word格式文档下载.docx

《数字图像处理外文资料翻译Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数字图像处理外文资料翻译Word格式文档下载.docx（10页珍藏版）》请在冰点文库上搜索。

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_nedonanorthogonalgridin2Dor3Dspace.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;

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_neavalueatp2CinthetransformedimagebasedonpixelvaluesinIatp2CanditsimmediateneighborsinN_（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;

pn=qwithpiisa4-neighborofpi􀀀

1,1_i_n.Ifp=qthedistancebetweenthemisde_nedtobezero.Thedistanced4（p;

q）hasallpropertiesofametric.Givenabinarydigitalimage.Wetransformthisimageintoanewonewhichrepresentsateachpointp2hIithed4-distancetopixelshavingvaluezero.Thetransformationincludestwosteps.Weapplyfunctionsf1totheimageIinstandardscanorder,producingI_（i;

j）=f1（i;

I（i;

j））,andf2inreversestandardscanorder,producingT（i;

j）=f2（i;

I_（i;

j））,asfollows:

f1（i;

j））=

8>

<

>

0ifI（i;

j）=0

minfI_（i􀀀

j）+1;

j􀀀

1）+1g

ifI（i;

j）=1andi6=1orj6=1

m+notherwise

f2（i;

j））=minfI_（i;

j）;

T（i+1;

T（i;

j+1）+1g

TheresultingimageTisthedistancetransformimageofI.NotethatTisasetf[（i;

j）]:

1_i_n^1_j_mg,andletT__Tsuchthat[（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;

T_（i;

j））,andg2totheresultofg1inreversestandardscanorder,producingT___（i;

j）=g2（i;

T__（i;

g1（i;

j））=maxfT_