computing the medial axis transform in parallel wi

DIMACSTechnicalReport94-46September1994ComputingtheMedialAxisTransforminParallelwithO(1)scanoperationsbyAfonsoFerreira1;2CNRS-LIPENSLyon{69364LyonCedex07FranceStephaneUbeda3TSIUniversiteJean-MonnetSaintEtienneFrance1VisitingMember,partiallysupportedbyDimacsNSFgrantSTC{91{199999andtheNJCommis-siononScienceandTechnology.2PartiallysupportedbythePRCPRSandMath-InfooftheFrenchCNRS.3PartiallysupportedbytheTIPI-TSIProject.DIMACSisacooperativeprojectofRutgersUniversity,PrincetonUniversity,AT&TBellLaboratoriesandBellcore.DIMACSisanNSFScienceandTechnologyCenter,fundedundercontractSTC{91{19999;andalsoreceivessupportfromtheNewJerseyCommissiononScienceandTechnology.ABSTRACTThemainresultofthispapershowsthattheblock-baseddigitalmedialaxistransformcanbecomputedinparallelbyaconstantnumberofcallstoscan(parallelprex)operations.Thisgivestimeand/orwork-optimalparallelalgorithmsforthedistancebasedandtheblockbasedmedialaxistransforminawidevarietyofparallelarchitectures.Themostimportantcontribution,however,isthepracticalaspectsofouralgorithms.Inordertodesignsuchanalgorithm,werstdemonstratethatcomputingablock-basedmedialaxistransformofabinaryimagereducestocomputingthedistancebasedmedialaxistransformofanoversamplingoftheimage,becausetheirlabelingsareequivalent.1IntroductionOneofthemostimportantproblemsinpatternrecognitionliesinshaperepresentation,whichisbothanissuerelatedtodatareductionanddatadescription.In[5],ashapedescriptornamedmedialaxiswasdescribedthatallowsafullreconstructionoftheoriginalshapeandthathasgoodpropertiesfordatareduction[13,14].Themedialaxisofacontinuousobjectcanbedenedwiththehelpoftheregrassconcept,wheretheobjectisseenasameadow,andareislitalongitscontoursuchthatallrefrontsinvadetheobjectwiththesamespeed.Themedialaxisoftheobjectisthenthesetofpointsreachedbymorethanonerefrontatthesametime(seeFigure1-(I)).Itcanbealsodenedasthesetconstitutedbythecenterofthemaximaldisksthatrecovertheobject(seeFigure1-(II)).Themedialaxisisapowerfulshapedescriptor,whosemostimportantpropertiesinclude:anobjectanditsmedialaxisarehomotopic;themedialaxisofanobjectismadeofthickarcsandcurves;andnally,ifanypointofthemedialaxisofanobjectislabeledwiththeradiusofitscorrespondingmaximaldisk,thentheobjectcanbeexactlyrebuiltusingtheinformationofitsmedialaxis[17].(I)Resultofafiregrassonarectangularform(II)SomemaximaldisksofarectangularformFigure1:IllustrationofthecontinuousmedialaxisThesubjectofthispaperisthedigitalmedialaxisofanobjectfromabinaryimage,whichisaderivativeofthemedialaxisoriginallyproposedin[5].Unfortunately,itiswellknownthatsuchtranspositions,fromcontinuoustodigitalcases,raisemanyproblems[6,18].Inthiscase,workinginadiscretespaceimpliesthatrewavefrontsaresymbolizedbycontourlines,anddisksbecomeofsquaredform.Therefore,thedigitalMedialAxisTransform(MATforshort)isdenedasarecoveringoftheobjectbymaximaldigitaldisksincludedintheobject,whereadigitaldiskissaidtobemaximalifitisnotincludedinanyotherdigitaldiskcontainedintheobject[15].Inthispaper,wefocusontheparallelprocessingoftwotypesofMAT,namely,thedistance-basedMAT(denotedDB-MAT)whichcorrespondstoasetofpixelsincludedintheobject,eachlabeledwithitsdistancetothebackgroundofthepictureandtheblock-basedMAT(denotedBB-MAT)whichisbasedonthenotionofrecoveringtheobjectbymaximalsquareblocksofpixelsofanyparitysize.WeconsiderimagesasNNsquaresetsofpointsofadigitalgridE,eachpointbeingassociatedtoabinaryvalue,0todenoteabackgroundpixel,and1todenoteanobjectpixel.1.1PreviousworkAsseenabove,theserialmedialaxis,aswellasitsutilisationinimageprocessingandshaperecognition,havebeenextensivelystudied.Besidesthepapersreferencedthusfar,ofgreatimportanceforourresultsisthecomputationofthemedialaxisontheoversampledimagethatwasdescribedin[3].MostoftheseresultswillberecalledinthenextSection.Intheparallelsetting,also,extensiveresearchhasbeencarriedoutinconnectiontothecomputationofthemedialaxistransformofbinaryimages.Thedistancebasedextractionofamedialaxistransformisrelatedtothedistancetransformoftheimage.Therefore,thislatterproblemreceivedconsiderableattentionintheliterature.Inparticular,BitzandKungproposedasystolicimplementationin[4].Basedonsuchalgorithm,MiguetandRobertdesignedadistancetransformalgorithmforMIMDcomputers([11]).RegardingSIMDalgorithms,LuandVarmanstudiedthedistancetransformonmesh-connectedcomputersin[10],andJenqandSahniobtainedaparallelalgorithmforadynamicprogrammingsolutionofthemedialaxistransform{block-basedversion{,thatcanbeimplementedonaCREWPRAMwithN2processors,intimeO(logN)[8].Finally,awork-optimalEREW-PRAMalgorithmwasgivenbyKimin[9],intimeO(logN)withN2=logNprocessors.1.2ThispaperThework-optimalalgorithmfrom[9]isbasedonadivide-and-conquerapproachwheretheoriginalproblemofsizeSispartitionedintoproblemsofsizepS,andthisrecursively.Therefore,itisofcompleximplementationevenintheEREW-PRAM.FormorepracticalarchitecturesasHypercubemultiprocessorsorrealparallelsystems,suchanalgorithmwouldbeverydiculttoprogramandwouldhavealargercomplexity.Themainresultpresentedinthispaperisasfollows:Aparallelalgorithmtocompu