Topological-structural-analysis-of-digitized-binar

COMPUTERVISION,GRAPHICS,ANDIMAGEPROCESSINGN,32-46(1985)TopologicalStructuralAnalysisofDigitizedBinaryImagesbyBorderFollowingSATOSHISUZUKI*GraduateSchoolofElectronicScienceandTechnology,ShizuokaUniversity,Hamamatsu432,JapanANDKEIICHIABE+DepartmentofComputerScience,ShizuokaUniversity,Hamamatsu432,JapanReceivedDecember16,1983Twoborderfollowingalgorithmsareproposedforthetopologicalanalysisofdigitizedbinaryimages.Thefirstonedeterminesthesurroundnessrelationsamongthebordersofabinaryimage.Sincetheouterbordersandtheholebordershaveaone-to-onecorrespondencetotheconnectedcomponentsofl-pixelsandtotheholes,respectively,theproposedalgorithmyieldsarepresentationofabinaryimage,fromwhichonecanextractsomesortoffeatureswithoutreconstructingtheimage.Thesecondalgorithm,whichisamodifiedversionofthefirst,followsonlytheoutermostborders(i.e.,theouterborderswhicharenotsurroundedbyholes).Thesealgorithmscanbeeffectivelyusedincomponentcounting,shrinking,andtopologicalstructuralanalysisofbinaryimages,whenasequentialdigitalcomputerisused.o1985Academicpress,I~C.1.INTRODUCTIONBorderfollowingisoneofthefundamentaltechniquesintheprocessingofdigitizedbinaryimages.Itderivesasequenceofthecoordinatesorthechaincodesfromtheborderbetweenaconnectedcomponentofl-pixels(l-component)’andaconnectedcomponentofO-pixels(backgroundorhole).Theborderfollowingtechniquehasbeenstudieddeeply,becauseithasalargevarietyofapplications,includingpicturerecognition,pictureanalysis,andimagedatacompression[l-lo].Thepurposeofthispaperistoproposeborderfollowingalgorithmswithasortoftopologicalanalysiscapability.Ifonewantstoconvertabinarypictureintotheborderrepresentation,thenhecanextractthetopologicalstructureoftheimagewithlittleadditionaleffortbyusingthealgorithmspresentedhere.Theinformationtobeextractedisthesurroundnessrelationamongthetwotypesofborders:theouterbordersandtheholeborders.Sincethereexistsone-to-onecorrespondencebetweenanouterborderandal-component,andbetweenaholeborderandaO-component,thetopologicalstructureofagivenbinaryimagecanbedetermined.Severalworkshavebeenreportedonthetopologicalstructuralanalysisofbinarypicturesusingrasterscanandlabeling[l,10,111.Analternativeforsuchanalysisistouseborderfollowing.Ifanimageprocessingsystemutilizestheborderfollowingforsomepurposeandatthesametimeneedstoanalyzethetopologicalstructureof*PresentAffiliation:YokosukaElectricalCommunicationLaboratory,NipponTelegraphandTele-phonePublicCorporation.+DepartmentofComputerScience,FacultyofEngineering,ShizuokaUniversity,3-5-lJohoku,Hamamatsu432,Japan.320734-189X/85$3.00Copyright61985byAcademicPress.Inc.Allrightsofreproductioninanyformreserved.TOPOLOGICALANALYSISBYBORDERFOLLOWING33aninputimage,thenthisapproachwouldbeattractive.Fewstudies,however,havebeendevotedtothissubject.Theexistingmethods[6,71arerathercomplicatedandtimeconsuming,sothattheydonotseemadvantageousoverotherstructuralanalysismethods[l,10,111whichdonotuseborderfollowing.Inthispaper,wefirstpresentanalgorithmwhichcanextractthetopologicalstructureofagivenbinaryimage.Thisalgorithmisanextendedversionoftheborderfollowingalgorithm[l]whichdiscriminatesbetweenouterbordersandholeborders.Theextensionsare:(1)toputauniquemarkoneachborderratherthantoadoptthesamemarkingprocedureforeveryborder(borderlabeling);and(2)toaddaprocedureforobtainingtheparentborderofthecurrentlyfollowedborder(seeDefinition4).Withthisalgorithmwecanextractthesurroundnessrelationamongtheborders,whichcorrespondstothesurroundnessrelationamongtheconnectedcomponents.Ifabinaryimageisstoredintheformofthebordersandthesurroundnessrelationisextractedbythisalgorithm,somesimpleimageprocessingcanbedonewithoutrestoringtheoriginalimage.Thusthemethodoffersaneffectivewayofstoringbinaryimagedata.Nextweshowamodifiedversionofthefirstalgorithmwhichfollowsonlytheoutermostbordersofabinaryimage(i.e.,theouterborderswhicharenotsur-roundedbyholes).Whenwewanttoignorethel-componentswhicharesurroundedbyotherl-components,thismodifiedalgorithmgivesusaquick,sequentialmethodofcountingthel-componentsorshrinkingeachl-componenttoonepoint.2.BASICCONCEPTANDNOTATIONSInthispaperonlydigitalbinarypicturessampledatpointsofrectangulargridsareconsidered.Thoughwewillfollowthegeneralterminologyandnotationssuchasin[l],wewouldliketodefineandclarifysomeconceptsandnotationsnotsowidelyestablished.Theuppermostrow,thelowermostrow,theleftmostcolumn,andtherightmostcolumnofapicturecomposeitsframe.Pixelswithdensities0and1arecalledtheO-pixelandthel-pixel,respectively.Withoutlossofgenerality,weassumethatO-pixelsfilltheframeofabinarypicture.Weassumealsothatwecanassignanyintegervaluetoapixelduringtheprocessing.Thepixellocatedintheithrowandthejthcolumnisrepresentedbytherownumberandthecolumnnumber(i,j).Weadoptthefollowingcoordinatesystem:therownumberiincreasesfromtoptobottom;thecolumnnumberjfromlefttoright.Apicturehavingthedensityvaluehjatapixel(i,j)isdenotedbyF={hi}.Al-componentandaO-componentaretheconnectedcomponentsofl-pixelsandofO-pixels,respectively.IfaO-componentScontainstheframeofthepicture,wecallSthebackground;otherwise,ahol