Linear-Time-Maximally-Stable-Extremal-Regions

LinearTimeMaximallyStableExtremalRegionsDavidNist´erandHenrikStew´enius1MicrosoftLiveLabs2GoogleSwitzerlandAbstract.InthispaperwepresentanewalgorithmforcomputingMax-imallyStableExtremalRegions(MSER),asinventedbyMatasetal.Thestandardalgorithmmakesuseofaunion-finddatastructureandtakesquasi-lineartimeinthenumberofpixels.Thenewalgorithmprovidesexactlyidenticalresultsintrueworst-caselineartime.Moreover,thenewalgorithmusessignificantlylessmemoryandhasbettercache-locality,resultinginfasterexecution.OurCPUimplementationperformstwiceasfastasastate-of-the-artFPGAimplementationbasedonthestandardalgorithm.Thenewalgorithmisbasedonadifferentcomputationalorderingofthepixels,whichissuggestedbyanotherimmersionanalogythantheonecorrespondingtothestandardconnected-componentalgorithm.Withthenewcomputationalordering,thepixelsconsideredorvisitedatanypointduringcomputationconsistofasingleconnectedcomponentofpixelsintheimage,resemblingaflood-fillthatadaptstothegrey-levellandscape.Thecomputationonlyneedsapriorityqueueofcandidatepixels(theboundaryofthesingleconnectedcomponent),asinglebitimagemaskingvisitedpixels,andinformationforasmanycomponentsastherearegrey-levelsintheimage.Thisissubstantiallymorecompactinpracticethanthestandardalgorithm,wherealargenumberofconnectedcomponentsmustbeconsideredinparallel.Thenewalgorithmcanalsogeneratethecomponenttreeoftheimageintruelineartime.TheresultshowsthatMSERdetectionisnottiedtotheunion-finddatastructure,whichmayopenmorepossibilitiesforparallelization.1IntroductionExtractionofinvariantregionshasrecentlybeenthefocusofintensestudy[1,2,3,4,5,6,7,8,9,10,11,12],supportingawidevarietyofapplicationssuchasrecognition,imageretrieval,mosaicing,3Dreconstruction,tracking,robotnav-igationandmore.TestinginacommonframeworkwasenabledbyMikolajczyketal.[5]withadatasetthatallowstestingtherepeatabilityofaregiondetec-torunderdisturbancessuchasblur,viewpointchange,zoom,rotation,lightingchangesandJPEGcompression.MaximallyStableExtremalRegions(MSER)describedbyMataselal[3]havebecomeoneofthecommonlyusedregiondetectortypes,partlybecauseoftheirhighrepeatabilityandpartlybecausetheyaresomewhatcomplementarytomanyothercommonlyuseddetectors[7,4,13].TheyareviablewitharelativelyD.Forsyth,P.Torr,andA.Zisserman(Eds.):ECCV2008,PartII,LNCS5303,pp.183–196,2008.cSpringer-VerlagBerlinHeidelberg2008184D.Nist´erandH.Stew´eniusFig.1.Thetwoimmersionanalogies.Ontheleft,thestandardimmersion.Ontheright,theimmersioncorrespondingtothenewlineartimealgorithm.smallnumberofregionsperimage,andarethereforewellsuitedforlargescaleimageretrievaltasks[14,15].Theyhavealsobeenusedinrecognition[16]aswellastracking[11]andhavebeenextendedtocolor[17]andvolumetricimages[18].ThedetectionhasevenbeenimplementedonFPGA[19].ThestandardalgorithmforcomputingMSERfollowsthesamelinesasaverypopularfloodingsimulationalgorithmforcomputingawatershedsegmentation,suggestedin[20].Thewatershedsegmentationhasalonghistoryandhasbeenintenselystudied,see[21]forareview.Intheimmersionanalogy,Fig1,thegrey-levelprofileoftheimageisimaginedasalandscapeheight-map.Thewaterlevelisraisedgraduallyuntilthewholelandscapeisimmersed.Inthestandardimmersionanalogy,thelevelisraisedequallyatallplacesinthelandscape(im-age).Thatis,oneeitherthinksofthelandscapeasporoussothatthewaterlevelwillbeequaleverywhere,orequivalently,imaginesthataholeispiercedineachlocalminimumofthelandscape,allowingwatertoenter.Thealgorithmkeepstracksoftheconnectedcomponentsofwater(connectedcomponentsofpixels)usingaunion-finddatastructurewithpath-compression.Theunion-finddatastructurewithpath-compressionsupportsquasi-lineartimeinthenum-berofpixels[21,22,23].Moreprecisely,thetimerequiredcanbeshowntobeboundedbyO(nα(n)),wherenisthenumberofpixelsandα(n)istheinverseoftheAckermannfunction,whosevalueissmallerthan5ifnisoftheorder1080.Hencetheexpression’quasi-linear’iswellmotivated,althoughatruelin-eartimealgorithmfortheunion-findproblemtoourknowledgerequireslimitingassumptionssuchasforexampletheexistenceofacomputerwithlog(n)wordlengthandincrementalgrowingofthedatastructure[24].Inthispaper,analgorithmispresentedthatcancomputeMSERandtheso-calledthecomponenttree(ofconnectedcomponentsastheyevolveduringtheflooding),allintruelineartimeinthenumberofpixels.Perhapsevenmoreimportantly,thealgorithmworkswithasingleconnectedcomponentofpixels,resultinginlessmemoryusageandfasterexecution.Thealgorithmisnaturalandsimple,sharingmanypropertieswiththepreviousalgorithm,butwithonecriticaldifference.Insteadoffloodingtheimagewiththesamewaterlevelevery-where,thefloodingoccursasifthelandscapewasopaqueandwaterisbeingpouredonatsomearbitrarilyselectedpoint(pixel),seeFig.1.Thewaterfirstfillsupthebasinwherewaterispouredon,andthenspillsovertootherpartsLinearTimeMaximallyStableExtremalRegions185Fig.2.Typicalprogressstagesforthealgorithmonthefirstpass.Thetopleftpixelisusedasthesourcepixel.Thefloodingoccurs,withpreferencefordarkregions,MSERaredetectedintheprocess,andeventuallythewholeimageisflooded.Theprocesswillthenberepeatedwithpreferenceforbrightregions.ofthelandscapeastheybecomeaccessibleto