Corner

www.elsevier.nl/locate/patrec

Cornerdetectionviatopographicanalysisofvector-potential

BinLuo

aa,b,A.D.J.Crossa,E.R.Hancock

a,*DepartmentofComputerScience,UniversityofYork,YorkYO15DD,UK

bAnhuiUniversity,Anhui,People'sRepublicofChinaReceived22September1998;receivedinrevisedform23December1998

Abstract

Thispaperdescribeshowcornerdetectioncanberealisedusinganewfeaturerepresentationbasedonamagneto-staticanalogy.Theideaistocomputeavector-potentialbyappealingtoananalogyinwhichtheCannyedge-mapisregardedasanelementarycurrentdensityresidingontheimageplane.Inthispaper,wedemonstratethatcornersarelocatedatthesaddle-pointsofthemagnitudeofthevector-potential.Thesepointscorrespondtotheintersectionsofsaddle-ridgeandsaddle-valleystructures,i.e.tojunctionsoftheedgeandsymmetrylines.Wedescribeatemplate-basedmethodforlocatingthesaddle-points.Thisinvolvesperforminganon-minimumsuppressiontestinthedirectionofthevector-potentialandanon-maximumsuppressiontestintheorthogonaldirection.Experimentalresultsusingbothsyntheticandrealimagesaregiven.Weinvestigatetheangleandscalesensitivityofthenewcornerdetectorandcompareitwithanumberofalternativecornerdetectors.Ó1999ElsevierScienceB.V.Allrightsreserved.

Keywords:Cornerdetection;Topographicanalysis;Vector-potential;Saddle-pointdetection

1.Introduction

Cornersareimportantdominantpointsindig-italimages.Inmanycomputervisiontasks,suchasimageregistration,imagematching(Costabileetal.,1985),objectrecognition(LiuandSrinath,1990b;HanandJang,1990)andmotionanalysis(DreschlerandNigel,1992),accuratecornerde-tectionisessential.Broadlyspeaking,therearetwocornerdetectionstrategiesadoptedinthelit-erature.The®rstoftheseisbasedontheanalysisofpre-segmentedcontours,whilethesecondisbasedonthedi󰂀erentialanalysisoftherawgrey-scaleimage.However,inbothcasesitistherateof

changeofcontouranglethatisusedtocharac-terisecornerfeatures.1.1.Relatedliterature

Inthecaseofboundary-basedcornerdetectionfrompre-segmentedcontourstherearethreepro-cessingsteps.Firstly,theimageispre-segmented.Secondly,boundariesoftheobjectintheimageareextractedandchain-coded.Finally,algorithmsaredevelopedforidentifyingcornersinthechain-codes.Acommontechniqueistosearchforcor-nersattheintersectionpointsorjunctionpointsbetweenstraightlinesegments(Xieetal.,1993).Infact,theuseofchain-codestoprovideadigitalcharacterisationofcornersaboundinthelitera-ture(FreemanandDavis,1977;BeusandTiu,1987;KoplowitzandPlante,1995;Rosenfeldand

Correspondingauthor.Tel.:+441904432767;fax:+441904432767;e-mail:erh@minster.cs.york.ac.uk

*0167-8655/99/$±seefrontmatterÓ1999ElsevierScienceB.V.Allrightsreserved.PII:S0167-8655(99)00028-8

636B.Luoetal./PatternRecognitionLetters20(1999)635±650

Johmston,good(1990a).review1973;weakHowever,isRosenfeldprovidedandWeszka,1975).AitmustbybeLiustressedandSrinathdetectionlinkinthecontour-basedmethodofthatcornertheageistheprioravailabilityofareliableim-dividedGrey-scalesegmentation.

detectorsintotwocornergroups.detectionTemplate-basedalgorithmscancornerbe1990)plateexploit(Rangarajantheetal.,1989;Mehrotraetal.,window.ofspeci®corientationsimilaritybetweenforeachagiventem-aresive.used,Becausethetechniquemultipleorientationimagetemplatessub-andGiraudon,Rosenfeld,Gradient-basedcorneriscomputationallydetectors(Kitchenexpen-1995;1993;1982;Noble,Singh,1988;1990;WangDericheandandhand,HarristhatThepassesrelyonandStephens,1988),ontheBrady,otherthroughmeasuringathecurvatureofanedgebothstrengthofthecornergivenimageresponseneighbourhood.dependsonedge-direction.theedge-strengthtechniquesGradient-basedandtherateofchangeoftheiraremorelikelytorespondcornertonoisedetectionthanformcontour-basedcounterparts,andoftencornerFocusingquitepoorly.

per-inadetection,moreWangdetailandBradyon(1995)gradient-basedthecurvature-based``totalstrengthofcornerscornerdetectorwhichmeasuresdescribetionalcurvature''.Thetotalintermscurvatureoftheisso-calledtensitytothesecondderivativeoftheimagepropor-in-inverselyalongmethodproportionaltheedge-tangenttotheedge-strength.direction,andisanvidingexplicito󰂀ersmeasuretheattractivefeatureofexploitingTheever,falseoneadegreeofitsweaknessesoffalseofcurvaturecorneraswellaspro-isthatsuppression.itHow-present.responseswhensigni®cantimagecannotnoisecontrolisStephens,Thedetector1988)popularisanotherPlesseycurvature-basedoperator(Harrisandthewhichisbasedonlyon®rstderivativescornerofwithimage`L'-junctionsrespectintensity.tonoise,Althoughitisquiterobusttionorright-angleitcancorners.onlyperformThewelloncornerofotherjunctiontypesispoor.Thelocalisa-SUSANotherAdegreehand,detectorofperforms(SmithrobustnessalocalandBrady,1997),ontheisachievedtemplatebycomparison.computing

templatecentredexaminesoncorrelationwhichthethestatisticsforacircularmasknumbercornercandidates.ofpixelsInparticular,itThefornumberhaveaofsimilaragreementbrightnesswithincountsistotakenthethetemplate.maskasavotetakenthemethodtocornerhypothesis.Highvotingpixelsaresiontestalsohavetorejectperformsasigni®cantfalse-positives.anon-maximumcornerstrength.suppres-The1.2.Paperoutline

detectionOuraiminthispaperistopresentanewcornerbasedgradient-basedandmethodgradient-basedwhichconcepts.exploitsbothWeappealtemplate-toaalreadyimagerepresentationwhichhaspographicbeenfeaturesrepresentationshowntoprovideforaconvenientto-representation(CrossandHancock,edge1997,and1998).symmetryThemap,tensity.i.e.computeBytherotatingdirectionalcommencesthegradientfromtheCannyedge-edge-gradientofthevectorsimagein-vectorsprocessarea®eldofedge-tangents.Thetangentweinginwhichsmoothedthevectorsbyperformingareanaveragingpointtogestedinthequestion.inverseofThistheirweightingdistanceweightedfunctionfromtheaccord-isimagesug-thebymagneto-statics.Asaresult,werefertoAccordingresultingthetogradientthisrepresentation,®eldasthevector-potential.localtionalmagnitudeDirectionallyconsistencyvector-®eldwhichexhibitmaximadirec-ofareconsistent(i.e.ridges)localcorrespondminima(i.e.toedges.topographicsymmetrylines.Inthispaper,weextendravines)thissaddle-structurespictureridgeswheretoincludedirectionallycorners.TheseconsistentareanalysisItisandimportantravinesintersect.

tocontrastour(HaralickwithonetHaralick'stopographicprimalmethodsketchof(i.e.thetopographical.,1983).structureWhereasofHaralickfocusestopographyascalarimagerepresentation),grey-scaleweanalysefeaturesthemainrectionaladvantageofagraphicconsistencyisvector-®eldthatinwerepresentation.Thethearelocalisationabletoexploitofdi-robustnessstructuregraphicrepresentationoffeatureand,detection.hence,improvetopo-theinhand,theWithmainthepractical

topo-B.Luoetal./PatternRecognitionLetters20(1999)635±650637

problemsaddle-points.thatconfrontsusisthelocalisationoftheridgesidentifyingandravinesThisismoredi󰂁cultthanlocalisingfeatures.exploitInpointthecasefeaturessinceweofridgesratherareconcernedwithandravines,thancontourdirectionality.constraintsoncompatiblecontinuitywecanorconstraintslocationsareInmorethesubtle,caseofsaddle-pointsthejunctionswhichareconsistentsincewithweareseekingvalleys.

betweensaddle-ridgesandbeingsaddle-thegraphicBasedoninplate-basedthevector-potential.teststhisforobservation,theconsistentwedeveloptopo-Thisise󰂀ectivelysaddle-structureatem-valleypotentialstructuremethod.orthogonalandconsistentintheWedirectionsearchforconsistentridgestructureofthevector-tionaldirection.Inotherwords,theindirec-thetureravineastemplatetheintersectioncharacterisesoflocalsaddle-struc-computation(i.e.symmetry)structures.ridge(i.e.Moreover,edge)and®xedtial.tobeissimpli®edsincethetemplateisofintensity.directionalInthisinwaythedirectionofthevector-poten-secondweavoidderivativesexplicitofcomputationthisAswewilldemonstrateexperimentally,theimagesensitivity.

o󰂀ersadvantagesintermsofimprovednoisetionTheoutlineofthispaperisasfollows.InSec-tion.2,representationSectionwereview3theintroducesvector-potentialrepresenta-Inoffeaturesinthethevector-potential.topographicdi󰂁cultiesSection4,Real-worldassociatedweconfrontsomeofthepracticalinandSectionexperimentalwithexamplessaddle-localisation.arepresentednally,comparison5.Questionsareaddressedofalgorithminsensitivityidenti®esSectionavenues7providesforfuturesomeinvestigation.conclusionsSection6.andFi-2.Imagerepresentationusingvector-potentialtationInthissection,wereviewthefeature-represen-(1997).recentlyedge-mapThestartingreportedpointbyCrossandHancockmenceby(Canny,convolving1986).istheAccordingly,tocomputetherawimagesweCannywithcom-a

Gaussianfollowingkernelform:

ofwidthr.Thekerneltakestheqr󰂅xYy󰂆󰂈

1

!2pr2expÀx2󰂇y2

2r2X󰂅1󰂆Withmapistherecovered®lteredimagebycomputinginhand,thethegradientCannyedge-E󰂈rqrÃsX

󰂅2󰂆

Inoforderauxiliarytheedge-map,tocomputeavector-®eldrepresentation

natezdimensionwetowilltheneedoriginaltointroducexanco-ordinatesystemoftheplaneimage.Inthis±augmentedyco-ordi-mapwords,areinputimagethecon®nedsystem,edge-vectortothethecomponentsattheimagepointplane.oftheedge-󰂅xYyY0In󰂆onothertheHplaneisgivenby

oqrÃs󰂅xYy󰂆IoxE󰂅xYyY0󰂆󰂈fdoqrÃs󰂅xYy󰂆g

oyeX

󰂅3󰂆

0

Forentmorewillanidealbedirectedstep-edge,alongthetheresultingboundaryimagenormal.gradi-AvectorsconvenientAccordingly,which¯owrepresentationalongtheisobjecttheedge-tangentboundary.theywere-directtheedge-vectorssothatcomputingaretangentialthethecross-producttotheoriginalwithplanartheshapebyatde®nedtheimagepointplanetobe

󰂅xYy󰁞zY0󰂈󰂆󰂅on0Y0theY1󰂆T

input.Theimagetangentnormalplanevectorto

isj󰂅xYyY0󰂆󰂈󰁞z󰁞rqrÃs󰂅xYy󰂆X

󰂅4󰂆

Totangentbemorevectorexplicit,isgivenintermsby

ofitscomponentstheHÀoqrÃs󰂅xYy󰂆Ioyj󰂅xYyY0󰂆󰂈fdoqrÃs󰂅xYy󰂆g

oxeX󰂅5󰂆

0

Inunderlyingourpreviouslyreportedwork,theacterisegraphicedgestheimageandsymmetryrepresentationwaskeytochar-ideacorrespondedstructurestorstolocationsintheedge-tangentlinesusing®eld.Edgestopo-boundariesre-enforcewherethetangentvec-tangent®eld.areone-another.Inotherwords,theSymmetryidenti®edpointsaslocalaremaximathoseatofwhich

the638B.Luoetal./PatternRecognitionLetters20(1999)635±650

thereposedisoftangentcancellationvectors.betweenAxesofsymmetrydiametricallyarelinesop-oflocallocal®nedetail,minimumintensityintheridgestangentorravines®eld.AtgivetheriseleveltoareUnfortunately,symmetryaxes.

sincetherawgradientsmoothinglikelytothethebetangentnoisywe®eldmustsothatdevelopwecanameansvectorsperformofgoal,requiredtopographicanalysis.Torealisethismeanswely,ofappealsmoothingtomagneto-staticsthetangent®eld.toAccording-developabywementaryregardingcomputetheanedge-tangentsanalogueoftheasvector-potentialaintegratingcurrents.tributingovervolumeThevector®eldofele-andpotentialisfoundbyotherroriginal󰂈󰂅xYwords,currentsyYimagez󰂆T

intheaccordingvector-potentialtoweightinginverseatdistance.thecon-thepoint

Inplanetheaugmentedisembeddedspaceis

inwhichthe󰁚

A󰂅xYyYz󰂆󰂈lj󰂅xHYyHYzH󰂆󰁖HjrÀrHjd󰁖HY󰂅6󰂆whereconstantrH󰂈󰂅xHYcontributingwhichyHweYzH󰂆Tsetandequallistotheunity.permeability

Sincethedistributedintegralonlyedge-tangentvectors(orcurrents)areplane.reducestoonantheareaimageintegralplane,overthethevolumepotentialAsarearesult,asfollows:

thecomponentsofthevector-imageA󰂅xYyHYz󰂆

󰁒󰁒fÀoqI

rÃs󰂅xHYyH󰂆oyHp󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁1HH󰂅xÀxH󰂆2󰂇󰂅yÀyH󰂆2󰂇z2

󰂁dxdyg󰂈fff󰁒󰁒oqdrÃs󰂅xHYyH󰂆oxHp󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁1󰂅xÀxH󰂆2󰂇󰂅yÀyH󰂆2

󰂇z2dxHdyHgggX0

e󰂅7󰂆

Thefurtherstructureponentscomment.ofInthethevector-potential®rstinstance,thedeservescom-ofmovetheauxiliaryarecon®nedtothex±yplaneforallvaluesauxiliaryawayfromco-ordinatetheimageplanez.However,theroleaswecurrentsoriginaloverdimensionanincreasinglyistoaverageofthislargethegeneratingthevolumeauxiliaryimageplane.Inotherwords,areatheroleoftheofintegrationz-dimensionoftheisedge-tangenttoallowusvectors.toperformBysamplingplanesimagetion.plane,atincreasingthevector-potentialforvariousx±yweinducesamplingascale-spaceheightzabovethecoarseWeexploitthispropertytoproducerepresenta-a®ne-to-vector-potentialimagerepresentationaswesampletheaboveatincreasingsamplingheightsoperatorsInorderthephysicaltodevelopimagetheplane.

appropriatedi󰂀erentialvector-potentialforfeatureanalogywehavecharacterisationtakenthemagneto-staticfromthegeometryonecordingthetoofstepfurtherandhaveappealedtothemagneto-statics,theassociatedthemagneticmagnetic®eld.®eldAc-isstresscurltractablethatofthevector-potential.Itisimportantto®eldthanbecausethevector-potential,itislesscomputationallythemagnetictation.isanmagneticauxiliaryTheneverroleuseddirectlyinourimagerepresen-representation.ofthemagneticThe®eldistoprovideential®eldallowsustounderstandgeometrytheofdi󰂀er-thetosymmetryourstructurerepresentationofthevector-potential.oftheimageAccordingvector-potential.linesfollowimageInthelocalminimastructure,oftheedgepointswhereotherthereiswords,strongtheycancellationconnectplacedtangentcontoursobjectvectorsboundaries.associatedBywithcontrast,symmetricallyedge-potential.followedge-linesAccordingthelocaltomaximaofthevector-directionalconnectpointsourwhererepresentation,thereisstrongthevectors.locationsSymmetryre-enforcementtowherelinescanbetweenbeinterpretededge-tangentaswherethesamplingtheimagemagneticplane.®eldEdgesisperpendicularsampling®eldofplane.linesaretangentialtoarethelocationsrelevantsymmetrythedi󰂀erentialWhenstructureviewedoffromthetheperspectiveof󰁞zthecurllinesinarelocationswherevector-potential,thecomponentthe󰁞r󰁞A󰂅xYyYz󰂆󰂈the0,imageedgesplanearelocationsvanishes,i.e.ishes,transversei.e.rÁ󰂅󰁞zcomponent󰁞A󰂅xYyYzofthedivergencewherevan-daryCorners,orpointsof󰂆󰂆locally󰂈0.

maximumboun-wherecurvature,withthereisacanlocalbesymmetryviewedasedge-locationsviewedarapidchangeinboundarydirection.axisassociatedWhensentation,fromcornerstheperspectivethereforeofourcorrespondimagerepre-to

B.Luoetal./PatternRecognitionLetters20(1999)635±650639

locationsconditionswheretopographicareboththeedgeandsymmetryboundaryviewpoint,simultaneouslycornerssatis®ed.arelocatedFromwhereawords,linesandsymmetrylinesmeet.Inothertherevector-potentialiswealocalareinterestedmaximuminlocatingpointswhereimumcornerintheorthogonalinonedirectionofthemagnitudeandalocalofmin-thedetection.

detectioncanbetreateddirection.asAssaddle-pointaresult,3.Topographicrepresentation

saddle-pointsInSection2,weestablishedtential.scalarquantityWethereforeinthemagnitudefocusontheofthatanalysisthecornersvector-po-areoftheg󰂅xYy󰂆z󰂈jA󰂅xYyYz󰂆jX

󰂅8󰂆

Thecanbetopographicstructureofthe󰀒characterised󰀓usingtheHessianvector-potentialmatrix

Hg󰂈

ggxxgxy

xygyyY󰂅9󰂆wherethesecondderivativesaregivenbygxx󰂈

o2g󰂅xYy󰂆o2zYgo2xxy󰂈

g󰂅xYy󰂆oxo2yzYgyy󰂈o2g󰂅xYy󰂆o2yzX

beTheeigen-structureoftheHessiantwousedminimumeigen-valuestogaugetheofcurvatureHaretheofthematrixcanmaximumsurface.Theandtorsdirections.ofHcurvatures.isTheareknownTheorthogonaleigen-vec-mean-curvatureastheprincipal(Kcurvaturecurvatures.foundbyaveragingequalFinally,thethe)ofthesurfaceGaussianmaximumcurvatureandminimum(Hresult,

totheproductofthetwoeigen-values.As)isar󰂈gxxgyyÀg2

xy

󰂅10󰂆

andu󰂈

gxx󰂇gyy

2X󰂅11󰂆

TableCurvature1

classesClassSymbolKHRegion-typeDomeRidge

DÀEllipticSaddle-ridgeRÀ+Plane

SRÀParabolicSaddle-pointPÀ00HyperbolicCupS0ÀHyperbolicValley

C0+HyperbolicSaddle-valley

V+SV

++

0EllipticÀ

ParabolicHyperbolic

curvaturesThesignsandzerosofthemeanandGaussiansurfacegraphicgeometrycanbeusedtocategorisethelocalTablesaddle-structures1.classes.intoanumberofdistincttopo-InthisThesepaper,classesaresummarisedinfeaturesterisedinthetable.whichweareinterestedintheThesearelabelledashyperbolicarebeinginterestedbytheconditioninpointsr`features0.Inparticular,arecharac-wei.e.dle-valleys.inthetheintersectionsintersectionsofthatofedgeareconsistentwithsaddle-ridgesandsymmetrylines,tionsisThejointconditionfortheandintersec-sad-u󰂈0󰁞r`0X

󰂅12󰂆

Bysaddle-ridges,searchingofweforovercometheintersectionsomeofconsistentrconstraints`localising0.Thiscansaddle-points,forwhichoftheuproblems󰂈0andfeature.andInfromprovedi󰂁cultsincetherearenoparticular,thedirectionalityweofthedesiredtemplatesrealisesymmetrylinestothesearchcornerandedge-lines.

forlocalisationmitigatethisdi󰂁cultythejunctionsprocessbetweenusing4.Implementation

implementationInthissection,theseofwedescribetwoaspectsofthetor-potentialisthemeansourbywhichcornerwedetector.computeThethe®rstvec-ofcomplexityrealisedusingofandfasttheFouriermethod.theresultingtransforms.ThecomputationcomputationalThesecond

is640B.Luoetal./PatternRecognitionLetters20(1999)635±650

implementationaldetailconcernsthepracticalmeansbywhichwelocatesaddle-structures.4.1.Computingthevector-potential

Keytoourimplementationisthefactthatthevolumeintegralsappearinginthede®nitionofthevector-potential(Eq.(7))canbereplacedbyspa-tial-convolutionswithasamplingheight-depen-dent®lter.Speci®cally,weinvoketheFourierdualitybetweenconvolutioninthespatialdomainandmultiplicationinthefrequencydomain.Inthisway,thediscretisedversionofthevector-potentialcanbecomputedusingjustthree2DFourier

Fig.1.Topographicrepresentationandcornerdetection.

B.Luoetal./PatternRecognitionLetters20(1999)635±650641

transformsandapairoffrequency-domaincon-volutions.

Ourbasicgoalistocomputethevector-poten-tialatagivensamplingheightabovetheimageplane.The2Dintegralsappearinginthede®nitionofthevector-potentialcanbediscretisedtogivethefollowingxandycomponents:

ex󰂅xYyYz󰂆󰂈À

󰁘󰁘oqrÃs󰂅xHYyH󰂆

xH

yH

oyH󰂅13󰂆

1

Âq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁Y

󰂅xÀxH󰂆2󰂇󰂅yÀyH󰂆2󰂇z2

Fig.2.Topographicrepresentationatdi󰂀erentsamplingheights.

642B.Luoetal./PatternRecognitionLetters20(1999)635±650

ey󰂅xYyYz󰂆󰂈

󰁘󰁘oqrÃs󰂅xHYyH󰂆

xH

yH

oxH󰂅14󰂆

1

Âq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁X

󰂅xÀxH󰂆2󰂇󰂅yÀyH󰂆2󰂇z2

Thedoublesummationcanbereplacedbyaconvolutionwithacomposite®lter.Forinstance,thex-componentofthevector-potentialisasfollows:

ex󰂅xYyYz󰂆󰂈À󰂅󰁖x󰂅rYz󰂆Ãs󰂆󰂅xYy󰂆X

󰂅15󰂆

Fig.3.Topographicrepresentationatdi󰂀erentsamplingheights.

B.Luoetal./PatternRecognitionLetters20(1999)635±650643

Weexploitthecommutativepropertiesofconvo-lutiontocomputethecomposite®lter󰁖x󰂅rYz󰂆.The®lterisfoundbyconvolvingtheappropriatedi-rectionalderivativeoftheGaussianwiththein-verseEuclideandistanceoperator,i.e.,󰁖x󰂅rYz󰂆󰂅xYy󰂆

󰁘󰁘oqr󰂅xHYyH󰂆󰂆󰂈

oyHxHyH

1

Âq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁X

󰂅xÀxH󰂆2󰂇󰂅yÀyH󰂆2󰂇z2

󰂅16󰂆composite®ltersinturn,i.e.wecomputeF󰂉ex󰂅rYz󰂆󰂊andF󰂉ey󰂅rYz󰂆󰂊.Finally,thetwospa-tialcomponentsofthevector-potentialareob-tainedbyinverseFouriertransformationofthetwoweightedfrequencydistributions.

SincethecomputationisimplementedusingfastFouriertransforms,thetimecomplexityisof

2

theorder󰂅xln󰂅x󰂆󰂆wherexisthelinearimagedimension.Infact,wehaveimplementedtheal-gorithmonanSGIIndyworkstationwhereitiscapableofprocessing256´256pixelimagesattherateof25framespersecond.4.2.Localisingsaddles

BasedontheresultspresentedinSection3,wemakethefollowingobservationsconcerningthetopographicstructureofthevector-potentialintheproximityofcorners:

·Thereisalocalminimaofthemagnitudeofthevector-potentialinthedirectionofthevector-potential.

·Thereisalocalmaximaofthemagnitudeofthevector-potentialintheorthogonaldirection.·Atthelocationsofcorners,themagnitudeofvector-potentialalongboththecontouranditsorthogonaldirectionchangesrapidly.

·Atthelocationsofcorners,themagnitudeoftheGaussiancurvatureissigni®cant.

Basedonthe®rsttwoobservations,wesearchforsaddle-pointsthatareconsistentwhenviewed

Forpracticalreasons,wewouldliketorealisethecomputationofthecomponentsofthevector-potentialusingfastFouriertransforms.OurbasicstrategyistoexploittheFourierdualitybetweenconvolutioninthespatial-domainandmultiplica-tioninthefrequencydomain.Schematically,weutilisetheidentity

ex󰂈FÀ1󰂉F󰂉󰁖x󰂅rYz󰂆󰂊ÂF󰂉s󰂊󰂊

󰂅17󰂆

tocomputeeachofthecomponentsofthevector-potentialinturn.Inthiswaythevector-potentialcanbeobtainedusingthreeseparateFouriertransformoperations.The®rstoftheseinvolvescomputingtheFouriertransformoftherawimageF󰂉s󰂊.TwoseparateweightedspatialfrequencydistributionsarethenconstructedbymultiplyingthecomponentsoftheimageFouriertransformwiththeFourierrepresentationforeachofthe

Fig.4.Cornerdetectionresults.

644B.Luoetal./PatternRecognitionLetters20(1999)635±650

froma®nitesupportneighbourhood.Inpracticewelocaliseconsistenttopographicstructureusingasimpli®edformoftemplateconvolution.Ourtemplatetestsfororthogonalmaximaandminimausingdirectionalsecondderivativesandsubse-quentnon-maximumsuppressionandnon-mini-mumsuppressiontests.Thesaddle-pointsarecornercandidates.Becauseofimagenoiseand

Fig.5.Cornerdetectionatdi󰂀erentsamplingheights.

B.Luoetal./PatternRecognitionLetters20(1999)635±650645

otherimperfections,thepointsdetectedbyoursaddle-templatearenotalwaysthelocationsoftruecornersintheimage.Toovercomethisproblemwecanappealtothedirectionalconsis-tencyofthederivativesofthevector-potentialtore®nethecornerestimates.Theaimistosearchfororthogonalridgeandravinestructures.Tomeetthisgoal,weuseddirectionalsecondderivativeoperatorstocomputeacorner``strength''mea-sure.Thismeasurecapturesthedirectionalvaria-tionsofthevector-potentialalongthecontourdirectionandintheorthogonaldirection.

Tobemoreformal,supposethat󰁖󰂅xYyYz󰂆󰂈2~rjjjejisthesecondderivativeofthemagnitudeofthevector-potentialinthedirectionofthevector-potential.Themagnitudeofthisquantitywilltakeonamaximumvaluewhenthereisalocalmini-mumorvalleystructureinthemagnitudeofthevector-potential.Furthersupposethat󰁒󰂅xYyYz󰂆󰂈

~r2cjejisthesecondderivativeofthemagnitudeofthevector-potentialinthedirectionperpendiculartothelocalorientationofthevector-®eld.Themagnitudeofthisquantityexhibitsalocalmaximawhenthereisaridgestructureorlocalmaximainthevector-potential.Usingthesetwooperators,wesearchforcornersbycomputingthefollowingcornerstrengthmeasurewhichgaugesconsistentsaddle-structure:

g󰂈j󰁖󰂅xYyYz󰂆jÂj󰁒󰂅xYyYz󰂆jX

󰂅18󰂆

ThemeasureisanapproximationtotheGaussiancurvature.Itislargeinvaluewhenthereareor-thogonalridgesandvalleysinthemagnitudeofthevector-potential.Cornersareselectedby

thresholdingthisaggregatemeasureofcornerstrength.5.Experiments

Inthissection,weprovidesomeexperimentalevaluationofthecornerdetectionalgorithm.Theexperimentalworkisdividedintotwoparts.Wecommencewithsomeexamplesonbinaryimagerytoillustratesomeofthepropertiesoftherepre-sentation.Nextwefurnishreal-worldexamples.Toillustratethepropertiesofourvector-potentialrepresentationandcornerdetectionalgorithm,weuseasimplebinaryimageof``E''.Fig.1(a)isthemagnitudeofthevector-potentialforthebinaryimage,Fig.1(b)isthedirectionofthevector-potential.Fig.1(c)showsthedetectedcorners.Forthissimpleimage,theresultsareallcorrect.Themagnitudeofthevector-potentialisdisplayedasafunctionofthesamplingheightzinFig.1(a)toemphasisethetopographicstructure.Herethesaddle-structureassociatedwiththecornersisclear.Theridgeandravinestructureoftheedgeandsymmetrylinesisalsoevident.InFig.1(b)wedisplaythevectorialrepresentationofA󰂅xYyY0󰂆.Themainfeaturetonotefromthis®gureisthatthedirectionofthevector-potentialchangesrapidlyatthecornerlocations.

Asexplainedearlier,wecanendowourimagerepresentationwithascale-spacedimensionbysamplingthevector-potentialatincreasingsam-plingheightsabovetheimageplane.InFigs.2and3,weprovidesomequalitativeexamplesofthis

Fig.6.Cog-wheeltestimages.

646B.Luoetal./PatternRecognitionLetters20(1999)635±650

Fig.7.Comparisonfordi󰂀erentsamplingheights.

scale-spacesampling.Ineachcasetheleft-hand®gureisanelevationmapshowingthemagnitudeofthevector-potentialwhiletheright-hand®gureisthevector-®eld.Themainfeaturetonotefromtheseexamplesisthatasthescaleorsamplingheightisincreased,sothesaddle-structuresbe-comeshallower.

Wenowturnourattentiontoreal-worldscenes.Toprovidesomecomparison,wehaveprovidedsomeexperimentationwiththeSUSANcornerdetector(SmithandBrady,1997).Fig.4(a)istheoriginalINRIAo󰂁ceimage.InFig.4(b)weshowtheresultofapplyingthealgorithmreportedinthispaper,whileFig.4(c)showstheresultofap-

Fig.8.Saddle-structuresfordi󰂀erentopeningangles.

B.Luoetal./PatternRecognitionLetters20(1999)635±650647

plyingobtainedtheandsometherewithSUSANarefewerouralgorithmcornerdetector.Theresultsfalsepositives.aregenerallyTherecleaner,tectedinterestingmeetingcorners.qualitativedi󰂀erencesinarethealsode-verticaloftheline-likeForinstancehorizontalinouralgorithm,thejunctions.barsofthewindowaredetectedbarsandthickerareInthecaseofSUSAN,doubleascornerssingleperceptuallyreturned.forintuitiveTheresultandofmayourprovealgorithmmoreisusefulmorespaceFinally,higherlevelwematchingproblems.

scene.detectionprovideatFig.5showsofthecornerssomeexamplesofthescale-resultsinoftheINRIAo󰂁cecolumnanumberofdi󰂀erentsamplingcornerheights.detectionTheleftvector-potential,ofthe®guredetectedwhileshowstheright-columnthemagnitudeshowsofthetheimage.cornerssuperimposedontheoriginaltoAswemovefromthetoprowofthe®gurevector-potentialthebottomrow,increases,main.thensoincreases.thesamplingheightzoftheonlytheAsdominantthesamplingcornersheightcornersHowever,heights.

persistoverthemajoritythefullofsettheofsigni®cantre-sampling6.Performanceanalysis

measuringOur®naltectortiveandcomparingthepiecenoiseofexperimentalsensitivityworkisaimedatitwithsomeofourcornerde-sectioncornerdetectorsreviewedintheofintroductorythealterna-in(Smiththiscomparisonofthispaper.areThespeci®calgorithmsusednerandBrady,1997),theSUSANWangandcornerBrady'sdetectorPlesseydetector1988).corner(WangandBrady,1995)andcor-theatedTorealisedetectorthiscomparison,(HarrisweandStephens,andsyntheticimagesofcog-wheelshave(seeFig.gener-6)proportion.haveaddedthereducecircumferenceByincreasingsalt-and-pepperofthecog,thewenumbernoisewithknowncansystematicallyofspikesonthetictheonnumber®guretheopeningangleofthecorners.Thesyn-ofprovidestargetcornersground-truthisdatainwhichnertwodetector.aspectsTheof®rstthenoiseofthesesensitivityknown.isthescale-depen-

ofWeourfocuscor-danceistives.

theerroroftheratecornerfordetectionfalsepositivesprocess.andThefalsesecondnega-accuracyWecommenceourevaluationbymeasuringthefunctioncornerofofsamplingthecornerheightdetection(i.e.spatialprocessscale)asacorrectlyopeningplingdetectedangle.cornersFig.7asshowsthefractionandofopeningheightz.Thedi󰂀erentcurvesafunctionarefordi󰂀erentofsam-drawndegradesfromangles.thisTheplotmainisthatconclusionthatcanbealsowithansmallindicationwithincreasingopeningthatsamplingourcornerheight.detectorThereisanglewecorners.

encounterdi󰂁cultiesFig.9.Comparisonofnoisesensitivity.

648B.Luoetal./PatternRecognitionLetters20(1999)635±650

Inordertounderstandinaqualitativewaytheanglesystematicsinvolvedincornerdetection,wehavegeneratedaseriesofsyntheticexamples.Theresultingplotsofthevector-potentialmagnitudeareshowninFig.8.Astheangleincreases,sothedepthofthesaddledecreases.Atsmallopeningangles,thewidthofthesaddlebecomesverynar-rowandhencedi󰂁culttolocalise.

Fig.10.Noisesensitivityforvariousopeningangles.

B.Luoetal./PatternRecognitionLetters20(1999)635±650649

provideThesecondcornersomeaspectcomparisonofoursensitivitystudyistonoise.bothThedetectorsplotsunderconditionswiththeofalternativecontrolledcornerstruepositives,inFig.i.e.9theshowtheprobabilityofabilitythatarecorrectlydetected,fractionandofthegenuineprob-tectedofprobabilitiescornersfalsepositives,whicharei.e.thefractionofde-arefractionplottedoftruepositivesfalseandfalsealarms.positivesThecurvelongistheofaddedasafunctionresultofnoise.theproposedInofeachthecase,probabilityoralgorithm,thesolidthetector,dashedcornerthePlesseydetectordashedcurveisfortheSUSANcornerde-andcurvetheisdottedforWanglineandBrady'swecornerdetector.FromtheplotofisFig.for9(a),thegorithmcandrawinconsistentlytheconclusionoutperformsthattheproposedal-positivesthesensethatithasahigherprobabilitythealternativesofmoreofnoiseforissmallportionsofaddednoise.WhentrueWangourmethodaddedisalmosttotheidenticalimage,theperformanceOurandBrady,andthePlesseycornerwiththatdetectors.oftheofitsmethodprobabilityalwaysofoutperformstruepositives.

SUSANintermsconclusiveTheresultstector.supportshownforinourFig.9(b)providemorepositivesHereweseethattheproposedprobabilitycorneroffalsede-signi®cantlyforourcornerlowerproposedthanthatmethodforisconsistentlynoiseslightlylevelsdetectors.whereThethePlesseyonlyexceptionthecornerdetectoroccursalternativeato󰂀erslowtheNext,betterweaimperformance.

andcornerdetectorstocomparefordi󰂀erenttheperformanceopeninganglesofopeningdi󰂀erent90anglesamplingof30°heights.WechooseasmallFig.°andmeasured10,wealargedrawopening,amediumopeningangleoftheconclusionangleof120°.Fromtives,intermsofthefractionofthat,truewhenposi-thatopeningofourthemethodotherperformscornerdetectorsalittleworsethanmediumangles,alittlebetterthantheforotherssmallatthanWhentheopeningalternativesangles,atandlargesigni®cantlyopeningangles.betterpositives,gaugedtivesatbothourmethodintermsofthefractionoffalsesmallopeningisbetteranglesthantheandalterna-large

openingworseopeningthanangles.However,itperformsalittleangle.thePlesseycornerdetectoratmedium7.Conclusions

tectionInthispaper,wehavepresentedacorneranalysismethodthatisbasedonthetopographicde-tion.saddle-pointsAccordingofavector-potentialtoourimagerepresenta-leysmethodintersect.wheresaddle-ridgesrepresentation,andcornerssaddle-val-areSUSANo󰂀ersperformanceExperimentaladvantagesresultsrevealoverthenermostdetectorcornerdetector,WangandBrady'scor-thefalsepositives.

strikingandofthesethePlesseyistoo󰂀ercornerbetterdetector.controloverThepresentedThereareanumberofwaysinwhichtheclearlyinthispapercouldbedeveloped.ideasWescale-space.havethatandofAsadaInathismeansrespect,ofcomputingourworkaiscurvaturesimilartolaterepresentationthisMackworthandworkby(1992).BradyinvestigatingOur(1986)nextandstepMokhtarianistoemu-recognition.

canbeusedforshapehowthematchingnewcornerandReferences

Asada,TransactionsH.,Brady,onM.,Pattern1986.Thecurvatureprimalsketch.IEEEBeus,8(1),AnalysisandMachineIntelligencealgorithmH.L.,2±14.

Tiu,basedS.S.H.,on1987.AnimprovedcornerdetectionCanny,ognitionchain-codeplane-curves.PatternRec-tion.J.F.,20(20),291±296.

Costabile,IntelligenceIEEE1986.TransactionsAcomputationalapproachtoedgedetec-8(6),679±698.

onPatternAnalysisandMachineshapes:M.F.,Guerra,C.,Pieroni,G.,1985.MatchingCross,Vision,GraphicsAcasestudyintimevaryingimages.ComputerfeatureA.D.J.,Computeranalysis.Hancock,andIn:IEEEE.R.,ImageProcessing29,296±310.

Computer1997.Scale-spacevector®eldforPuertoVisionandPatternRecognition,SocietyConferenceSanonCross,pp.Rica.IEEEComputerSociety,SilverSpring,Juan,MD,symmetryA.D.J.,738±743.

Hancock,E.R.,1998.Scale-spacevector®eldappear.

detection.ImageandVisionComputing11,forto650B.Luoetal./PatternRecognitionLetters20(1999)635±650

Deriche,forcornerR.,Giraudon,andG.,1993.Acomputationalapproach

Dreschler,Computervertexdetection.InternationalJournaloftrajectoryL.,VisionNigel,10,101±124.

framesequenceofamovingH.,1992.ofastreetcarscene.derivedVolumetricmodeland3DIn:fromProceedingsmonocularofTV-Freeman,pp.692±697.

IJCAIchainH.,codeDavis,curves.L.S.,IEEE1977.TransactionsAcorner®ndingonComputersalgorithmfor

26,Han,297±303.

pointsM.H.,forJang,theD.,recognition1990.TheuseofmaximumcurvatureHaralick,PatternR.,Recognitionofpartiallyoccludedobjects.Watson,L.,23,21±33.

Harris,primalLa󰂀ey,T.,1983.ThetopographicKitchen,detector.C.G.,sketch.IJRR2,50±72.

L.,In:Stephens,Rosenfeld,4thAlveyM.,1988.Acombinedcornerandedge

A.,Vision1982.Conference,Gray-levelcornerpp.147±151.detection.

Koplowitz,PatternRecognitionJ.,Plante,S.,Letters1995.1,Corner95±102.

detectionLiu,codedLiu,code.H.C.,curves.PatternSrinath,PatternRecognition28(6),843±852.

forchain-RecognitionM.D.,1990a.23Corner(1±2),51±68.

detectionfromchain-contourH.C.,Srinath,actionsmatchingM.D.,indistance1990b.Partialclassi®cationusing

1072±1079.

onPatternAnalysisandtransformation.MachineIntelligenceIEEETrans-12,Mehrotra,Mokhtarian,detection.R.,scaleF.,PatternNichani,Mackworth,RecognitionS.,Ranganathan,N.,1990.CornerA.K.,231992.(11),1223±1233.

Atheoryofmulti-curves.curvature-basedIEEETransactionsshapeonrepresentationPatternforplanarNoble,chineRangarajan,J.A.,Intelligence1988.Finding14(8),789±805.

AnalysisandMa-detection.K.,Shah,M.,Brackle,corners.D.V.,IVC6(2),121±128.

Rosenfeld,48,230±245.

ComputerVisionGraphicsand1989.ImageOptimalProcessingcornerRosenfeld,curves.IEEEA.,Johmston,angleA.,Weszka,TransactionsE.,1973.AngledetectionondigitalJ.S.,1975.onComputersAnimproved22,875±878.methodSingh,Computersdetection24,ondigitalcurves.IEEETransactionsonofandA.,1990.Gray940±941.

levelcornerdetection±AgeneralizationSmith,GraphicsarobustlevelS.,Brady,andImagereal-timeJ.,1997.Processingimplementation.SUSAN51±A(1),ComputerVisionnew54±69.

approachtoWang,Visionimage23(1),processing.InternationalJournalofComputerlowXie,algorithmH.,Brady,45±78.

formotionM.,1995.Real-timecornerdetectioncostX.,Sudhakar,R.,Zhuang,estimation.H.,1993.IVC13(9),695±703.1235±1243.

minimizationapproach.PatternCornerRecognitiondetection26by(8),a