LocalFeatures计算机视觉 Berkeley课件

C280,ComputerVision

Prof.TrevorDarrell

trevor@

Lecture6:LocalFeatures

LastTime:ImagePyramids

•ReviewofFourierTransform

•SamplingandAliasing

•ImagePyramids

•Applications:Blendingandnoiseremoval

Today:FeatureDetectionand

Matching

•Localfeatures

•Pyramidsforinvariantfeaturedetection

•Invariantdescriptors

•Matching

Imagematching

byDivaSian

byswashford

Hardercase

byDivaSianbyscqbt

Harderstill?

NASAMarsRoverimages

Answerbelow(lookfortinycoloredsquares...)

NASAMarsRoverimages

withSIFTfeaturematches

FigurebyNoahSnavely

Localfeaturesandalignment

•Weneedtomatch(align)images

•Globalmethodssensitivetoocclusion,lighting,parallax

effects.Solookforlocalfeaturesthatmatchwell.

•Howwouldyoudoitbyeye?

[DaryaFrolovaandDenisSimakov]

Localfeaturesandalignment

•Detectfeaturepointsinbothimages

[DaryaFrolovaandDenisSimakov]

Localfeaturesandalignment

•Detectfeaturepointsinbothimages

•Findcorrespondingpairs

[DaryaFrolovaandDenisSimakov]

Localfeaturesandalignment

•Detectfeaturepointsinbothimages

•Findcorrespondingpairs

•Usethesepairstoalignimages

[DaryaFrolovaandDenisSimakov]

Localfeaturesandalignment

•Problem1:

-Detectthesamepointindependentlyinboth

images

nochancetomatch!

Weneedarepeatabledetector

[DaryaFrolovaandDenisSimakov]

Localfeaturesandalignment

•Problem2:

-Foreachpointcorrectlyrecognizethe

correspondingone

Weneedareliableanddistinctivedescriptor

[DaryaFrolovaandDenisSimakov]

Geometrictransformations

Photometrictransformations

FigurefromT.TuytelaarsECCV2006tutorial

Andothernuisances...

•Noise

•Blur

•Compressionartifacts

Invariantlocalfeatures

Subsetoflocalfeaturetypesdesignedtobeinvariantto

commongeometricandphotometrictransformations.

Basicsteps:

1)Detectdistinctiveinterestpoints

2)Extractinvariantdescriptors

Figure:DavidLowe

Mainquestions

•Wherewilltheinterestpointscomefrom?

-Whataresalientfeaturesthatwelldetectin

multipleviews?

•Howtodescribealocalregion?

•Howtoestablishcorrespondences,i.e.,

computematches?

Figure4.3:Imagepairswithextractedpatchesbelow.Noticehowsomepatchescanbelocalized

ormatchedwithhigheraccuracythanothers.

FindingCorners

Keyproperty:intheregionaroundacorner,

imagegradienthastwoormoredominant

directions

Cornersarerepeatableanddistinctive

C.HarrisandM.Stephens."ACombinedComerandEdgeDetector.”

Proceedingsofthe4thAlveyVisionConference:pages147-151.

Source:LanaLazebnik

Cornersasdistinctiveinterestpoints

Weshouldeasilyrecognizethepointby

lookingthroughasmallwindow

Shiftingawindowinanydirectionshouldgive

alargechangeinintensity

“flat”region:“edge”：“corner”：

nochangeinnochangesignificant

alldirectionsalongtheedgechangeinall

directiondirections

Source:A.Efros

HarrisDetectorformulation

Changeofintensityfortheshift[u,v\\

v)=ZMx,y)[/(x+么y+v)—

1inwindow,0outsideGaussian

Source:R.Szeliski

HarrisDetectorformulation

Thismeasureofchangecanbeapproximatedby:

u

E(u,v)[uv]M

V

whereMisa2x2matrixcomputedfromimagederivatives:

rii

M=£w(x,y)XXyGradientwith

III2respecttox,

xyytimesgradient

withrespecttoy

Sumoverimageregion-area

wearecheckingforcorner

£Ix【xEIxlylx

M=[[①ly]

£Ixly£lyly

HarrisDetectorformulation

whereMisa2x2matrixcomputedfromimagederivatives:

M=£w(x,y)3Gradientwith

respecttox,

Atimesgradient

withrespecttoy

Sumoverimageregion-area

wearecheckingforcorner

£Ix【xEIxly

M=[[①ly]

£Ixly£lyly

Whatdoesthismatrixreveal?

First,consideranaxis-alignedcorner:

Whatdoesthismatrixreveal?

First,consideranaxis-alignedcorner:

o-

M=

5Z4=_o

Thismeansdominantgradientdirectionsalignwith

xoryaxis

IfeitherAiscloseto0,thenthisisnotacorner,so

lookforlocationswherebotharelarge.

Whatifwehaveacornerthatisnotalignedwiththe

imageaxes?

Slidecredit:DavidJacobs

GeneralCase

40

SinceMissymmetric,wehaveM=R~]R

o4

WecanvisualizeMasanellipsewithaxis

lengthsdeterminedbytheeigenvaluesand

orientationdeterminedbyR

directionofthe

slowestchange

SlideadaptedformDaryaFrolova,DenisSimakov.

Interpretingtheeigenvalues

Classificationofimagepointsusingeigenvalues

ofM:

九2

九1and九2aresmall;

Eisalmostconstant

inalldirections

Cornerresponsefunction

R=det(M)-atrace(M)2=44一研4+4)?

a：constant(0.04to0.06)

HarrisCornerDetector

•Algorithmsteps:

-ComputeMmatrixwithinallimagewindowstoget

theirRscores

-Findpointswithlargecornerresponse

(/?>threshold)

-TakethepointsoflocalmaximaofR

HarrisDetector:Workflow

SlideadaptedformDaryaFrolova,DenisSimakov,WeizmannInstitute.

HarrisDetector:Workflow

ComputecornerresponseR

HarrisDetector:Workflow

Findpointswithlargecornerresponse:7?>threshold

HarrisDetector:Workflow

TakeonlythepointsoflocalmaximaofR

HarrisDetector:Workflow

HarrisDetector:Properties

•Rotationinvariance

Ellipserotatesbutitsshape(i.e.

eigenvalues)remainsthesame

CornerresponseRisinvarianttoimagerotation

HarrisDetector:Properties

•Notinvarianttoimagescale

G

AllpointswillbeCorner!

classifiedasedges

•Howcanwedetectscaleinvariant

interestpoints?

Howtocopewithtransformations?

•Exhaustivesearch

•Invariance

•Robustness

Exhaustivesearch

•Multi-scaleapproach

SlidefromT.TuytelaarsECCV2006tutorial

Exhaustivesearch

•Multi-scaleapproach

为

Exhaustivesearch

•Multi-scaleapproach

Exhaustivesearch

•Multi-scaleapproach

Invariance

•Extractpatchfromeachimageindividually

Automaticscaleselection

•Solution:

-Designafunctionontheregion,whichis“scale

invariant55(thesameforcorrespondingregions,

eveniftheyareatdeferentscales}

Example:averageintensity.Forcorresponding

regions(evenofdifferentsizes)itw川bethesame.

-Forapointinoneimage,wecanconsideritas

afunctionofregionsize(patchwidth)

regionsizeregionsize

Automaticscaleselection

•Commonapproach:

Takealocalmaximumofthisfunction

Observation:regionsize,forwhichthemaximumis

achieved,shouldbeinvarianttoimagescale.

Important:thisscaleinvariantregionsizeis

foundineachimageindependently!

AutomaticScaleSelection

_

.s

」o

l

n

j

_

u

o

E

u

6

o

o

aH)Sameoperatorresponsesifthepatchcontainsthesameimageup

ol

gtoscalefactor.

q

o

ron48

sK.Grauman,B.Leibe

>

AutomaticScaleSelection

Functionresponsesforincreasingscale(scalesignature)

Hro

o

nl

l

U

O

E

U

6

0

0

0H)

l

o

a)-

q

o

a

n

s49

>K.Grauman,B.Leibe

AutomaticScaleSelection

Functionresponsesforincreasingscale(scalesignature)

Hro

o

l

n

l

U

O

E

U

6

0

0

0>H

l

o

a)-

q

o

-

e

n

s

>50

K.Grauman,B.Leibe

AutomaticScaleSelection

Functionresponsesforincreasingscale(scalesignature)

Hro

o

nl

l

U

0

4

C

6

0

0

0>H

l

o

a)-

q

o

-

e

n

sK.Grauman,B.Leibe

>

AutomaticScaleSelection

•Functionresponsesforincreasingscale(scalesignature)

_

.s

o」

nl

_j

U

0

E

U

6

0

。①

a

l

o

g

q

o

7nB

s

>52

K.Grauman,B.Leibe

AutomaticScaleSelection

-

B

H

O

nl

l

U

O

E

U

6

O

O

O

H

l

o

o)-

q

o

a

n

s

>

K.Grauman,B.Leibe

AutomaticScaleSelection

Hro

o

nl

l

U

O

4

C

6

O

O

O

H

1

0

<D-

q

0

a

n

s

>54

K.Grauman,B.Leibe

Scaleselection

•Usethescaledeterminedbydetectortocompute

descriptorinanormalizedframe

[ImagesfromT.Tuytelaars]

WhatIsAUsefulSignatureFunction?

Laplacian-of-Gaussian="blob"detector

-

B

M

O

l

n

l

U

0

W

U

6

0

0

①

a

ol

a-)

q

o

-

e

n

s

>

56

K.Grauman,B.Leibe

Characteristicscale

Wedefinethecharacteristicscaleasthescale

thatproducespeakofLaplacianresponse

2000

1500

1000

500

°017

characteristicscale

T.Lindeberg(1998)."FeaturedetectionwthautomaticscaleselectionJ

InternationalJournalofComputerVision30(2):pp77--116.Source:LanaLazebnik

Laplacian-of-Gaussian(LoG)

•Interestpoints:

5

Localmaximainscalea

spaceofLaplacian-of-

Gaussiana4

-

B

M

O

l

n

l

U

O

4

C

6

O2

。o

①

a

1

0nListof

<l-)

q

0

76n

s

>

K.Grauman,B.Leibe

Scale-spaceblobdetector:Example

Source:LanaLazebnik

Scale-spaceblobdetector:Example

sigma=11.9912

Source:LanaLazebnik

Scale-spaceblobdetector:Example

Source:LanaLazebnik

KeypointlocalizationwithDoG

•Detectmaximaof

difference-of-Gaussian

(DoG)inscalespace

•Thenrejectpointswithlow

contrast(threshold)

•Eliminateedgeresponses

Candidatekeypoints:

listof(x,y,o)

Exampleofkeypointdetection

(a)233x189image

(b)832DOGextrema

(c)729leftafterpeak

valuethreshold

(d)536leftaftertesting

ratioofprinciple

curvatures(removing

edgeresponses)

ScaleInvariantDetection:Summary

•Given:twoimagesofthesamescenewitha

largescaledifferencebetweenthem

•Goal:findthesameinterestpoints

independentlyineachimage

•Solution:searchformaximaofsuitable

functionsinscaleandinspace(overthe

image)

Mainquestions

•Wherewilltheinterestpointscomefrom?

-Whataresalientfeaturesthatwelldetectin

multipleviews?

•Howtodescribealocalregion?

•Howtoestablishcorrespondences,i.e.,

computematches?

Localdescriptors

•Weknowhowtodetectpoints

•Nextquestion:

Howtodescribethemformatching?

Pointdescriptorshouldbe:

1.Invariant

2.Distinctive

Localdescriptors

•Simplestdescriptor:listofintensitieswithin

apatch.

•Whatisthisgoingtobeinvariantto?

WriteregionsasvectorsregionB

A—>a,B-yb

I

I

vectoravectorb

Featuredescriptors

Disadvantageofpatchesasdescriptors:

•Smallshiftscanaffectmatchingscorealot

Solution:histograms

o2兀

Source:LanaLazebnik

Featuredescriptors:SIFT

ScaleInvariantFeatureTransform

Descriptorcomputation:

•Dividepatchinto4x4sub-patches:16cells

•Computehistogramofgradientorientations(8reference

angles)forallpixelsinsideeachsub-patch

•Resultingdescriptor:4x4x8=128dimensions

DavidG.Lowe."Distinctiveimagefeaturesfromscale-invariantkeypoints."IJCV60

(2),pp.91-110,2004.

Source:LanaLazebnik

RotationInvariantDescriptors

•Harriscornerresponsemeasure:

dependsonlyontheeigenvaluesofthe

matrixM

E㈡人

RotationInvariantDescriptors

•Findlocalorientation

Dominantdirectionofgradientfortheimagepatch

•Rotatepatchaccordingtothisangle

Thisputsthepatchesintoacanonical

orientation.

RotationInvariantDescriptors

ImagefromMatthewBrown

Featuredescriptors:SIFT

Extraordinarilyrobustmatchingtechnique

•Canhandlechangesinviewpoint

-Uptoabout60degreeoutofplanerotation

・Canhandlesignificantchangesinillumination

-Sometimesevendayvs.night(below)

•Fastandefficient-canruninrealtime

・Lotsofcodeavailable

一http:〃/albert/ladvnack/wiki/index.php/KnownimplementationsofSIFT

WorkingwithSIFTdescriptors

•Oneimageyields:

-n128-dimensionaldescriptors:each

oneisahistogramofthegradient

orientationswithinapatch

•[nx128matrix]

一nscaleparametersspecifyingthesize

ofeachpatch

•[nx1vector]

-norientationparametersspecifyingthe

angleofthepatch

•[nx1vector]

-n2dpointsgivingpositionsofthe

patches

•[nx2matrix]

AffineInvariantDetection

(aproxyforinvariancetoperspectivetransformations)

•Aboveweconsidered:

Similarity•transfo匚rm(rota•tion+uniformscale)

•Nowwegoonto:

Affinetransform(rotation+non-uniformscale)

■U

Mikolajczyk:HarrisLaplace

Mikolajczyk:HarrisLaplace

7.Initialization:MultiscaleHarriscorner

detection

2ScaleselectionbasedonLaplacian

Harrispoints

Harris-Laplacepoints

Mikolajczyk:HarrisAffine

►BasedonHarrisLaplace

►Usingnormalization/deskewing

Mikolajczyk:HarrisAffine

1.Detectmulti-scaleHarrispoints

2.Automaticallyselectthescales

3.Adaptaffineshapebasedonsecondordermomentmatrix

4.Refinepointlocation

Mikolajczyk:affineinvariant

interestpoints

1.Initialization:MultiscaleHarriscorner

detection

2.Iterativealgorithm

Normalizewindow(deskewing)

Selectintegrationscale(max.ofLoG)

Selectdifferentiationscale(max.

Detectspatiallocalization(Harris)

Computenewaffinetransformation

Gotostep2.(unlessstopcriterion)

HarrisAffine

AffineInvariantDetection:

Summary

•Underaffinetransformation,wedonotknowinadvance

shapesofthecorrespondingregions

•Ellipsegivenbygeometriccovariancematrixofaregion

robustlyapproximatesthisregion

•Forcorrespondingregionsellipsesalsocorrespond

OtherMethods:

1.Searchforextremumalongrays[Tuytelaars,VanGool]:

2.MaximallyStableExtremalRegions[Mataset.al.]

Featuredetectoranddescriptorsummary

•Stable(repeatable)featurepointscanbe

detectedregardlessofimagechanges

-Scale:searchforcorrectscaleasmaximumofappropriatefunction

-Affine:approximateregionswithellipses(thisoperationisaffine

invariant)

•Invariantanddistinctivedescriptorscanbe

computed

-Invariantmoments

-Normalizingwithrespecttoscaleandaffinetransformation

Moreonfeaturedetection/description

Address;希http://www.robots.ox.ac.uk/~vgg/research/affine/

Google▼mikolajczyk▼侬SearchWeb

AffineCovariantRegions

Publications

Regiondetectors•Harris-Affine&HessianAffine.K.MikolajczykandC.Schmid,ScaleandAffineinvariantinterestpointdetectors.In

UCV1(60):63-86,2004.PDF

•MSER.J.Matas,0.Chum,M.Urban,andT.Pajdla,Robustwidebaselinestereofrommaximallystableextremalregions.

InBMVCp.384-393,2002.PDF

•1BR&EBR.T.TuytelaarsandL.VonGool,MatchingwidelyseparatedviewsbasedonaflSneinvariantregions.InUCV1

(59):61-85,2004.PDF

•Salientregions:T.Kadir,A.Zisserman,andM.Brady,Anaffineinvariantsalientregiondetector.InECCVp.404-416,

2004.PDF

Regiondescriptors•SIFT.D.Lowe,Distinctiveimagefeaturesfromscaleinvariantkeypoints.InUCV2(60):91-110,2004.PDF

Performance•K.Mkolaiczyk,T.Tuytelaars,C.Schmid,A.Zisserman,J.Matas,F.Schafifalitzky,T.KadirandL.VanGool,A

evaluationcomparisonofaffineregiondetectors.TechnicalReport,acceptedtoUCV.PDF

•K.Mikolajczyk,C.Schmid,Aperformanceevaluationoflocaldescriptors.TechnicalReport,acceptedtoPAMI.PDF

Mainquestions

•Wherewilltheinterestpointscomefrom?

-Whataresalientfeaturesthatwelldetectin

multipleviews?

•Howtodescribealocalregion?

•Howtoestablishcorrespondences,i.e.,

computematches?

Featuredescriptors

Weknowhowtodetectanddescribegoodpoints

Nextquestion:Howtomatchthem?

Featurematching

Givenafeatureinl1}howtofindthebestmatchinl2?

1.Definedistancefunctionthatcomparestwodescriptors

2.Testallthefeaturesinl2,findtheonewithmindistance

Featuredistance

Howtodefinethedifferencebetweentwofeatures,f2?

•SimpleapproachisSSD(t|,f2)

-sumofsquaredifferencesbetweenentriesofthetwodescriptors

-cangivegoodscorestoveryambiguous(bad)matches

12

Featuredistance

Howtodefinethedifferencebetweentwofeatures,f2?

•Betterapproach:ratiodistance=880(^,f2)/SSD(f),f?')

-f2isbestSSDmatchtoinl2

nd

-f2'is2bestSSDmatchtoiinl2

-givessmallvaluesforambiguousmatches

Evaluatingtheresults

Howcanwemeasuretheperformanceofafeaturematcher?

200

featuredistance

True/falsepositives

-50—

truematch

-75-

-2oq-

falsematch

featuredistance

Thedistancethresholdaffectsperformance

•Truepositives=#ofdetectedmatchesthatarecorrect

-Supposewewanttomaximizethese—howtochoosethreshold?

•Falsepositives=#ofdetectedmatchesthatareincorrect

-Supposewewanttominimizethese—howtochoosethreshold?

Evaluatingtheresults

Howcanwemeasuretheperformanceofafeaturematcher?

______#truepositives

#matchingfeatures(positives)

______#falsepositives______

#unmatchedfeatures(negatives)

Evaluatingtheresults

Howcanwemeasuretheperformanceofafeaturematcher?

ROCcurve("ReceiverOperatorCharacteristic")

______#truepositives

#matchingfeatures(positives)

______#falsepositives______

#unmatchedfeatures(negatives)

ROCCurves

•Generatedbycounting#current/incorrectmatches,fordifferentthreholds

•Wanttomaximizeareaunderthecurve(AUC)

•Usefulforcomparingdifferentfeaturematchingmethods

•Formoreinfo:http:〃en.wikipedia.orq/wiki/Receiveroperatingcharacteristic

Advancedlocalfeaturestopics

•Self-Similarity

•Space-Time

MatchingLocalSeif-SimilaritiesacrossImagesandVideos

EliShechimanMichalIrani

Dept,ofComputerScienceandAppliedMath

TheWeizmannInstituteofScience

76100Rehovot,Israel

Abstract

Wepresentanapproachformeasuringsimilaritybe­

tweenvisualentities(imagesorvideos)basedonmatch­

inginternalself-similarities.Whatiscorrelatedacross

images(oracrossvideosequences)istheinternallay­

outoflocalself-similarities(uptosomedistortions).e\ren

thoughthepatternsgeneratingthoselocalself-similarities

arequitedifferentineachoftheinuigesAideos.Thesein­

ternalself-similaritiesareefficientlycapturedbyacom-

9

paalocal^self-similaritydescriptorfmeasureddensely

throughouttheiniage/video,atmultiplescales,whileac-

cowuingforlocalandglobalgeometricdistortions.This

givesrisetomatchingcapabilitiesofcomplexvisualdata,

includingdetectionofobjectsinrealclutteredimagesusing

onlyroughhand-sketches,handlingtexturedobjeaswith

noclearboundaries,anddetectingcomplexactionsincha-

teredvideodatawithnopriorlearning.Wecompareour

measuretocommonlyusedimage-basedandvideo-based

similaritymeasures,anddemonstrateitsapplicabilitytoob-

jeadetection,retrieval,andactiondetection.

FiguiuLTheseimagesofthesameobject(aheart)doNOTshare

commonimageproperties(colors,textures,edges),butDOshare

asimilargeometriclayoutoflocaliruernalself-similarines.

InputimageCorrelationImage

surfacedescriptor

Figure3.Corresponding"-Self-similaritydescriptors''.We

showafewcorrespondingpoints(1,2,3)acrosstwoimagesofthe

sameobject,withtheir"self-simUarity"descriptors.Despitethe

largedifferenceinphotometricpropertiesbetweenthetwoimages,

theircorrespondingself-similarity"descriptorsarequitesimilar.

Figure4.Objectdetection,(a)Asingletemplateimage(aflower),

(b)Theimagesagainstwhichitwascomparedwiththecorre­

spondingdetections.Thecontinuouslikelihoodvaluesabovea

threshold(samethresholdforallimages)areshownsuperimposed

onthegrayscaleimages,displayingdetectionsofthetemplateat

correctlocations(redcorrespondstothehighestvalues).

⑶入

Figure6.Detectionusingasketch,(a)Ahand-sketchedtem­

plate.(b)Theimagesagainstwhichitwascomparedwiththe

correspondingdetections.

Image1Image2OurMethodGLOHShapeMutual

(template)(extendedSIFT)ContextInformation

旗INRIA

Humanactions

incomputervision

IvanLaptev

INRIARennes,France

ivan.laptev@inria.fr

Summerschool,June30-July11,2008,LotusHill,China

Motivation

Goal:

Interpretation

ofdynamic

scenes

...non-rigidobjectmotion...cameramotion...complexbackgroundmotion

Commonmethods:Commonproblems:

•Camerastabilization•ComplexBGmotion

•Segmentation?

•Changesinappearance

•TrackingQ一

=>Noglobalassumptionsaboutthescene

Space-time

Noglobalassumptions=>

Considerlocalspatio-temporalneighborhoods

Space-time

Noglobalassumptions=>

Considerlocalspatio-temporalneighborhoods

Space-Timeinterestpoints

Whatneighborhoodstoconsider?

HighimageLookatthe

Distinctive

=variationin=distributionof

neighborhoods

spaceandtimethegradient

Definitions:

/:R2xRROriginal