LocalFeatures計(jì)算機(jī)視覺 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