A-fast-parallel-algorithm-for-thinning-digital-pat

RESEARCHCONTRIBUTIONSImageProcessingandComputerVisionRobertM.HaralickEditorAFastParallelAlgorithmforThinningDigitalPatternsT.Y.ZHANGandC.Y.SUENABSTRACT:Afastparallelthinningalgorithmisproposedinthispaper.Itconsistsoftwosubiterations:oneaimedatdeletingthesouth-eastboundarypointsandthenorth-westcornerpointswhiletheotheroneisaimedatdeletingthenorth-westboundarypointsandthesouth-eastcornerpoints.Endpointsandpixelconnectivityarepreserved.Eachpatternisthinneddowntoaskeletonofunitarythickness.Experimentalresultsshowthatthismethodisveryeffective.1.INTRODUCTIONItiswellknownthatthegeneralproblemofpatternrecognitionliesintheeffectivenessandefficiencyofextractingthedistinctivefeaturesfromthepatterns.Thestrokeanalysismethodisapowerfulapproachtorecognizingcertaintypesofdigitalpatternssuchasal-phanumericcharactersandideographs.Itshouldbenotedthatthestrokesthinnedbyhardwareorsoftwareareaccompaniedbydifferentkindsofdistortion.Differ-entthinningalgorithmsproducedifferentdegreesofdistortion[1-5,7-12].Thereisnogeneralagreementintheliteratureonanexactdefinitionofthinness.Pavlidis[6]describesathinningalgorithmthatdeterminesskeletalpixelsbylocaloperations.Atthesametime,thepixelsarela-beledsothattheoriginalimagecanbereconstructedfromitsskeleton.Thegoalofthispaperistofinda©1984ACM0001-0782/84/0300-023675¢fasterandmoreefficientparallelthinningalgorithm.Thedistortionshouldbeaslittleaspossible.Experi-mentalresultsindicatethatthismethodcanbeusedtothinavarietyofdigitalpatterns.2.PARALLELPICTUREPROCESSINGAbinarydigitizedpictureisdefinedbyamatrixITwhereeachpixelIT(i,j)iseither1or0.Thepatternconsistsofthosepixelsthathavevalue1.Eachstrokeinthepatternismorethanoneelementthick.IterativetransformationsareappliedtomatrixITpointbypointaccordingtothevaluesofasmallsetofneighboringpoints.Itisassumedthattheneighborsofthepoint(i,j)are(i-1,j),(i-1,j+1),(i,j+1),(i+1,j+1),(i+1,j),(i+1,j-1),(i,j-1),and(i-1,j-1),asisshowninFigure1.Inparallelpictureprocessing,thenewvaluegiventoapointatthenthiterationdependsonitsownvalueaswellasthoseofitseightneighborsatthe(n-1)thiteration,sothatallpicturepointscanP,(i-1,j-1)P,(i,j-1)P2P3(i-1,j)(i-1,j+1)P1(i,j)P,(i,j+1)P~PePs(i+1,j-1)(i+1,j)(i+1,j+1)FIGURE1.Designationsoftheninepixelsina3x3window.236CommunicationsoftheACMMarch1984Volume27Number3ResearchContributionsbeprocessedsimultaneously.Itisassumedthata3x3windowisused,andthateachelementisconnectedwithitseightneighboringelements.Thealgorithmpre-sentedinthispaperrequiresonlysimplecomputations.3.THINNINGALGORITHMOurmethodforextractingtheskeletonofapictureconsistsofremovingallthecontourpointsofthepic-tureexceptthosepointsthatbelongtotheskeleton.Inordertopreservetheconnectivityoftheskeleton,wedivideeachiterationintotwosubiterations.Inthefirstsubiteration,thecontourpointP1isde-letedfromthedigitalpatternifitsatisfiesthefollowingconditions:(a)2_B(P1)-6(b)A(P~)=1(C)P2*P4*P6=0(d)P4*P6*P8=0whereA(P1)isthenumberof01patternsintheorderedsetP2,P3,P4,-•-P8,P9thataretheeightneighborsofP1(Figure1),andB(Pi)isthenumberofnonzeroneighborsofP1,thatis,B(P1)=P2+P3+P4+•••+P8+P9.Ifanyconditionisnotsatisfied,e.g.,thevaluesofP2,P3,P4,••-P9asshowninFigure2,thenA(Pi)=2Therefore,P~isnotdeletedfromthepicture.Inthesecondsubiteration,onlyconditions(c)and(d)arechanged(Figure3)asfollows:(c')P2*P4*P8=0(d')P2*P6*P8=0andtherestremainthesame.Byconditions(c)and(d)ofthefirstsubiteration,itwillbeshownthatthefirstsubiterationremovesonlythesouth-eastboundarypointsandthenorth-westcor-nerpointswhichdonotbelongtoanidealskeleton.Theproofforthefirstsubiterationisgiven,thatis,thepointstobedeletedsatisfyconditions:00Ii1:P~01I00\2JFIGURE2.Countingthe01patternsintheorderedsetP2,P~,P4,....P~,P~.WestNorthP2PaPlP4PaSouthEastFIGURE3.Pointsunderconsiderationandtheirlocations•.@~.~•@.~@.~@@@@@@8@.@8#@@8@@.@@8@@88~.@@8@@@@~..@@8@8@8@8@@8@@@.@8@@@@8@..@@@8888@@@@@@~8.@@~0@@@8..88@8@8@#@@@@@@@.@@@@@~@@..@@8@~@@@@@~@8@@.@@@@@@@@..@88@8@@@@8@~@@8.8@~@@@@@..@8@@@88@@8@@8@@.@@~@@88@..88888@~~8@@8@@@.@@@@@@@@..8@@@@@@@~8@8@@@@@@88@@@8@@@@@8@@8@.8808@@88088@8@@@@@@@@~8~8@8.@@@@@@@O@@@@@@@@O@@@@@@~@@@.@@8@888@8@88@8~@8@@8~@@@@8@.888@8@8~8@@@@@8@@8@@@@@#@0.@@@~@@@8~8@8@8@@8@@@@@@~8@8.@888@@88~..........888~88@@.@@@@@8@@.@@@@@8@@.@@@@@@@@.~#@@@@@8.@@@@@@8@.@@@@@~8@.@@@@8~@@.8@@@@8@@.@@@@@0@@.#@@@@0@@.888@@8@~.@8@@@@@@.8~8@@@@@.@@8@@@#8.@@@@@@@@.#@#@@088.~@#@@@#.@@@@@@@@.°•o........o......(a).•°.....@@@@88@.8@@8@@@.@@@8@8@.@@@@8@@.@@~8@@@.@@@@@@@.@@@@88@.@@@8@@8.@@@@@0@.@@@@@@@O@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@#@@O@~@@@@@@@@.~88@@8@@@@@~@~8@8@@@@@@@@@.8@8@@@@#@88@@@@@@8@@@@@8@@.@@@@@@@@@8@@@@088@@@@@@@@@....@°.'.....~o.•....@..°....@...•°@o°°.°.@....•°o@.,°°...@......°@....°°°@.....°@.,o...............~......@..................@......@..................@......8@@@@@@@@@~8@@8@#@@@....•.@..................@....•.@..................@......~..................@.o•.@@@8@8@.@@8@@@8--@........~...•8@@@8@@.@@@8@@@--@........@...•@@@8~@@.@888@@~.-@........~...8@@@@@@.@8@@@@@..8........~...•.@........8...@@@@@@0.@@@@88@@88@8@8.@@@8@88..................@