A-Combined-Corner-and-Edge-Detector

ACOMBINEDCORNERANDEDGEDETECTORChrisHarris&MikeStephensPlesseyResearchRokeManor,UnitedKingdom©ThePlesseyCompanypic.1988Consistencyofimageedgefilteringisofprimeimportancefor3Dinterpretationofimagesequencesusingfeaturetrackingalgorithms.Tocaterforimageregionscontainingtextureandisolatedfeatures,acombinedcornerandedgedetectorbasedonthelocalauto-correlationfunctionisutilised,anditisshowntoperformwithgoodconsistencyonnaturalimagery.INTRODUCTIONTheproblemweareaddressinginAlveyProjectMMI149isthatofusingcomputervisiontounderstandtheunconstrained3Dworld,inwhichtheviewedsceneswillingeneralcontaintoowideadiversityofobjectsfortop-downrecognitiontechniquestowork.Forexample,wedesiretoobtainanunderstandingofnaturalscenes,containingroads,buildings,trees,bushes,etc.,astypifiedbythetwoframesfromasequenceillustratedinFigure1.Thesolutiontothisproblemthatwearepursuingistouseacomputervisionsystembaseduponmotionanalysisofamonocularimagesequencefromamobilecamera.Byextractionandtrackingofimagefeatures,representationsofthe3Danaloguesofthesefeaturescanbeconstructed.Toenableexplicittrackingofimagefeaturestobeperformed,theimagefeaturesmustbediscrete,andnotformacontinuumliketexture,oredgepixels(edgels).Forthisreason,ourearlierwork1hasconcentratedontheextractionandtrackingoffeature-pointsorcorners,sincetheyarediscrete,reliableandmeaningful^.However,thelackofconnectivityoffeature-pointsisamajorlimitationinourobtaininghigherleveldescriptions,suchassurfacesandobjects.Weneedthericherinformationthatisavailablefromedges3.THEEDGETRACKINGPROBLEMMatchingbetweenedgeimagesonapixel-by-pixelbasisworksforstereo,becauseoftheknownepi-polarcamerageometry.Howeverforthemotionproblem,wherethecameramotionisunknown,theapertureproblempreventsusfromundertakingexplicitedgelmatching.Thiscouldbeovercomebysolvingforthemotionbeforehand,butwearestillfacedwiththetaskoftrackingeachindividualedgepixelandestimatingits3Dlocationfrom,forexample,KalmanFiltering.Thisapproachisunattractiveincomparisonwithassemblingtheedgelsintoedgesegments,andtrackingthesesegmentsasthefeatures.Now,theunconstrainedimageryweshallbeconsideringwillcontainbothcurvededgesandtextureofvariousscales.Representingedgesasasetofstraightlinefragments4,andusingtheseasourdiscretefeatureswillbeinappropriate,sincecurvedlinesandtextureedgescanbeexpectedtofragmentdifferentlyoneachimageofthesequence,andsobeuntrackable.Becauseofill-conditioning,theuseofparametrisedcurves(eg.circulararcs)cannotbeexpectedtoprovidethesolution,especiallywithrealimagery.Figure1.Pairofimagesfromanoutdoorsequence.147Havingfoundfaultwiththeabovesolutionstotheproblemof3Dedgeinterpretation,wequestionthenecessityoftryingtosolvetheproblematall!Psycho-visualexperiments(theambiguityofinterpretationinviewingarotatingbentcoat-hangerinsilhouette),showthattheproblemof3Dinterpretationofcurvededgesmayindeedbeeffectivelyinsoluble.Thisproblemseldomoccursinrealitybecauseoftheexistenceofsmallimperfectionsandmarkingsontheedgewhichactastrackablefeature-points.Althoughanaccurate,explicit3Drepresentationofacurvingedgemaybeunobtainable,theconnectivityitprovidesmaybesufficientformanypurposes-indeedtheedgeconnectivitymaybeofmoreimportancethanexplicit3Dmeasurements.Trackededgeconnectivity,supplement-edby3Dlocationsofcornersandjunctions,canprovidebothawire-framestructuralrepresentation,anddelimitedimageregionswhichcanactasputative3Dsurfaces.Thisleavesuswiththeproblemofperformingreliable(ie.consistent)edgefiltering.Thestate-of-the-artedgefilters,suchas5,arenotdesignedtocopewithjunctionsandcorners,andarereluctanttoprovideanyedgeconnectivity.ThisisillustratedinFigure2fortheCannyedgeoperator,wheretheabove-andbelow-thresholdedgelsarerepresentedrespectivelyinblackandgrey.Notethatinthebushes,some,butnotall,oftheedgesarereadilymatchablebyeye.Afterhysteresishasbeenundertaken,followedbythedeletionofspursandshortedges,theapplicationofajunctioncompletionalgorithmresultsintheedgesandjunctionsshowninFigure3,edgesbeingshowningrey,andjunctionsinblack.Inthebushes,veryfewoftheedgesarenowreadilymatched.Theproblemhereisthatofedgeswithresponsesclosetothedetectionthreshold:asmallchangeinedgestrengthorinthepixellationcausesalargechangeintheedgetopology.Theuseofedgestodescribethebushissuspect,anditisperhapsbettertodescribeitintermsoffeature-pointsalone.Figure2.UnlinkedCannyedgesfortheoutdoorimagesFigure3.LinkedCannyedgesfortheoutdoorimages148Thesolutiontothisproblemistoattempttodetectbothedgesandcornersintheimage:junctionswouldthenconsistofedgesmeetingatcorners.Topursuethisapproach,weshallstartfromMoravec'scornerdetector6.MORAVECREVISITEDMoravec'scornerdetectorfunctionsbyconsideringalocalwindowintheimage,anddeterminingtheaveragechangesofimageintensitythatresultfromshiftingthewindowbyasmallamountinvariousdirections.Threecasesneedtobeconsidered:A.Ifthewindowedimagepatchisflat(ie.approximatelyconstantinintensity),thenallshiftswillresultinonlyasmallchange;B.Ifthewindowstraddlesanedge,thenashiftalongtheedgewillresultinasmallchange,butashiftperpendiculartotheedgewillresultinalargechange;C.Ifth