計算機科學與技術學碩專碩-計算機視覺碩士課件-第14章

ShapeandMatching

AndrewBender

AlexanderCobian

Topics

?ApproachesInvolvingNewDescriptors

-ShapeContexts

-MatchingLocalSelf-Similarities

?NovelMatchingTechniques

-PyramidMatchKernel

-SpatialPyramidMatching

ShapeContexts(2002)

?ShapeMatchingandObjectRecognitionUsing

ShapeContexts

-SergeBelongie

-JitendraMalik

-JanPuzicha

ShapeContexts(2002)

S5

?Asvectorsofpixelbrightnessvalues,very

different

?Asshapestohumanperception,verysimilar

Threestepstoshapematchingwith

shapecontexts

1.Findthecorrespondencebetweensetsof

pointsfromthetwoshapes

2.Usethematchestocomputeanalignment

transform

3.Computethe"distance"betweentheshapes

Threestepstoshapematchingwith

shapecontexts

1.Findthecorrespondencebetweensetsof

pointsfromthetwoshapes

2.Usethematchestocomputeanalignment

transform

3.Computethe"distance"betweentheshapes

Shapecontextsareapointdescriptorusedinstep1

Qj

~100pointsaresampledat

randomfromtheedge.

Uniformityisnotrequired!

Histogramusesbins

whichareuniformin

log-polarspace.

Rotationinvariance

?Ifrotationinvarianceisdesiredforadomain,

theshapecontextcanbecalculatedwiththe

tangentvectorasthex-axis.

?Formanydomainsthisisundesirable.

Matchingpoints

?Mustfindthedistancefromeverypointinone

imagetoeverypointintheother

?Dummypointswithaconstantedistancefrom

everyotherpointareaddedtobothsets

?Fornon-dummypoints,thecostofmatchingis

theL2norm

ShapeDistance

?Theauthorsuseaniterativemethodto

measurethemagnitudeofthetransformation

requiredtoalignthepoints

CategorizationofImages

?Prototype-basedapproach(withk-NN)

?Prototypesarechosenusingk-medoids

?kisinitializedtothenumberofcategories

?Worstcategoryissplituntiltraining

classificationerrordropsbelowacriterion

level

Application:DigitRecognition

210:58a1:

2le92Q77二

948

la-s132/015317(1

213q

?

4/z的K>

Trainingsetsize:

弓

32099T1791:2-?71879:8-?319029->4

-2772<

38s307yay

20,00034762420

e

826;0-Yb57的3

Testsetsize:-207-4:M3s2448:4T92463:2-?02583:9-?7

10,000vi夕。夕

7j

M3251:2T,34216K3476:3-?7

gs今

Error:

0.63%Z67

吊

og皿43769T44498:8-?74506:9-?7

,［夕p)

-*X叱

WI6555:2-?765729-?76577:7-416596:0-*7

I?)779

K：

LJ95067-?296419-+79730:5-*6985l:0-*6

Application:BreakingCAPTCHA

鎘爸密室浸翳感

盛最蠅瀚啜弱羲92%successrateon

EZ-Gimpy

weight

「，「「尸

again

蕊mW，-jewuL

,JI，E

承運郎總滔鎘盜種三

陛登二三中,$oxiiid^v"%；，二口匚二:甘寡

建懣遞遞逑逑11space

rice

CCF卜ATK

pwr-4**sock

Application:BreakingCAPTCHA

Mustidentify1版P

threewords.

33%successrate

onGimpy.

Application:TrademarkRetrieval

?Canbeusedto

finddifferent

shapeswithquery1:0.0862:0.1083:0.109

similarelements.至

query1:0.0662:0.0733:0.077

?UsefultoRADIO<PISTA

determinecasesqueryI:0.0462:0.1073:0.114

oftrademarkA岸

infringement.queiy1:0.0462:0.1073:0.114

Application:3DObjectRecognition

Notthemostnatural

applicationofshape

contexts.

Testexamplescan

onlybematchedtoan

imagetakenfroma

verysimilarangle.

Shapecontextconclusions

?Shapecontextisalocaldescriptorthat

describesapoint'slocationrelativetoits

neighbors

?Goodatcharacterrecognition,comparisonof

isolated2Dstructures

?Notwellsuitedtoclassificationofobjectswith

significantvariance

MatchingImages/VideoUsing

LocalSelf-Similarities(2007)

?MatchingLocalSelf-SimilaritiesacrossImages

andVideos

-EliShechtman

-MichalIrani

MatchingImages/VideoUsing

LocalSelf-Similarities(2007)

?Allofthese

imagescontain

thesameobject.

?Theimagesdo□□oo

口

notsharecolors,o口△△△A△△o

△口△口△

△o△

textures,or□△o

o△□△△°

edges.□△△△°

o□

Problem:

?PreviousDescriptorsforImageMatching:

-Pixelintensityorcolorvaluesoftheentireimage

-Pixelintensityorcolorvaluesofpartsoftheimage

一Texturefilters

-Distribution-baseddescriptors(e.g.,SIFT)

一Shapecontext

?Alloftheseassumethatthereexistsavisual

propertythatissharedbythetwoimages.

Solution:A"Self-Similarity"Descriptor

?Thefourheartimagesaresimilaronlyinthat

thelocalinternallayoutsoftheirself-

similaritiesareshared.

?Videodata(seenasacubeofpixels)isrife

withself-similarity.

GeneralApproach

?Oursmallestunitofcomparisonisthe"patch"

ratherthanthepixel.

?Patchesarecomparedtoalarger,encompassing

imageregion.

InputimageCorrelationImage

surfacedescriptor

置;

image

region?、

image百y

patchg:

GeneralApproach

?Thecomparisonresultsinacorrelationsurfacewhich

determinesnearbyareasoftheimagewhichare

similartothecurrentpatch.

?Thecorrelationsurfaceisusedtoproduceaself-

similarityimagedescriptorforthepatch.

InputimageCorrelationImage

surfacedescriptor

GeneralApproach

?Forvideodata,thepatchandregionarecubes,

astimeisthedepthdimension.

?Theresultingvideodescriptoriscylindrical.

CorrelationVideo

volumedescriptor

DescriptorGenerationProcess

Foreveryimagepatchq(e.g.,5x5pixelarea)

一Foreverypatch-sizedareacontainedintheenclosing

imageregion(eg,50x50pixelarea)

?CalculateSSDanddeterminecorrelationsurface

SSDq(x’y)

Sq@y)=exp—

max(varnoisefvarauto

?varnoiseisaconstantwhichspecifiesthelevelofacceptable

photometricvariation

1z

?vardmUitLnU(、q)isthemaximalvarianceofthedifferenceofall

patchesnearq

DescriptorGenerationProcess

?Transformeachcorrelationsurfacetolog-

polarcoordinateswith80bins(20angles,4

radialintervals)

?Thelargestvalueineachbindeterminesthe

entryinthedescriptor.

DescriptorGenerationProcess

DescriptorGenerationProcess

?Videodataadaptations:

-Imagepatchexistsinthreedimensions,butis

usuallychosentohave1framedepth(e.g.,5x5x1)

-Imageregionencompassesseveralframes(e.g.,

60x60x5)

一Thiscreatesacuboidcorrelationvolume,from

whichwegenerateacylindricaldescriptorby

binningitinloglogpolarcoordinates

PropertiesoftheSelf-Similarity

Descriptor

?Self-similaritydescriptorsarelocalfeatures

?Thelog-polarrepresentationallowsforsmall

affinedeformations(likeforshapecontexts)

?Thenatureofbinningallowsfornon-rigid

deformations

?Usingpatchesinsteadofpixelscapturesmore

meaningfulpatterns

PerformingShapeMatching

1.Calculateself-similaritydescriptorsforthe

imageatavarietyofscales(givesusinvariance

toscale)

2.Filterouttheuninformativedescriptorsforeach

scale

3.Employprobabilisticstargraphmodeltofind

theprobabilityofapatternmatchateachsite

foreachscale

4.Normalizeandcombinetheprobabilitymaps

usingaweightedaverage

Results

?Resultsrequireonlyonequeryimagewhich

canbemuchsmallerthanthetargetimages

?Processevenworkswhenoneoftheimagesis

hand-drawn

Results

Results

Sketch

Template

Inputvideo

[Sh?chtm?n-lraniCVPR

[Shechtman-lraniCVPR'07]

Our

result

Image1Image2OurMethodGLOHShapeMutual

(template)(extendedSIFT)ContextInformation

X

衣

應

Self-SimilarityConclusions

?Candiscoversimilarshapesinimagesthat

sharenocommonimageproperties

?Requiresonlyasinglequeryimagetoperform

complexshapedetection

?Hand-drawnsketchesaresufficienttofind

matches

?Videoisanaturalextension

ThePyramidMatchKernel(2005)

?ThePyramidMatchKernel:Discriminative

ClassificationwithSetsofImageFeatures

-KristenGrauman

-TrevorDarrell

ThePyramidMatchKernel(2005)

?SupportVector

Machines++

-Widelyused+

approachto+-

discriminative

classification+

-Findstheoptimal

separating

hyperplanebetween

twoclasses▼

ThePyramidMatchKernel(2005)

?Kernelscanbeusedtotransformthefeature

space(e.g.XOR)

?Kernelsaretypicallysimilaritymeasures

betweenpointsintheoriginalfeaturespace

ThePyramidMatchKernel(2005)

?Mostkernelsareusedonfixed-lengthfeature

vectorswhereorderingismeaningful

?Inimagematching,thenumberofimage

featuresdiffer,andtheorderingisarbitrary

?Furthermore,mostkernelstakepolynomial

time,whichisprohibitiveforimagematching

Desirablecharacteristicsinan

imagematchingkernel

?Capturesco-occurrences

?Ispositive-definite

?Doesnotassumeaparametricmodel

?Canhandlesetsofunequalcardinality

?Runsinsub-polynomialtime

?Nopreviousimagematchingkernelshadallfour

ofthefirstcharacteristics,andallranin

polynomialtime

GeneralApproach

?Dividethefeaturespaceintobinsofequalsize

?Repeat

-Countthefeatureswhichfallintoeachbinfor

bothimages

-Minthetwocountstofindtheoverlapineachbin

-Calculatenewmatchscorebasedonnewoverlaps

andeaseofoverlappingatthisresolution

-Createanewsetofbinswithsidelengthdouble

thatofthecurrentsidelength

GeneralApproach

n

Process

?InputspaceX

?d-dimensionalfeaturevectorsthat

-areboundedbyasphereofdiameterD

一haveaminimuminter-vectordistanceof學

Process

?FeatureExtractionAlgorithm:

W(x)=[H.1(X),H0(X),...,HL(X)]

?Harehistograms

?Listhenumberoflevelsinthepyramid

Process

?Similaritybetweentwofeaturesetsisdefinedas:

L

K△（叭叭z））={wM=

i=02

?Njisthenumberofnewmatchesacrossallbins

?Wjisthemaximumdistancethatcouldexist

betweenpointsthatmatchedatthislevel

Process

(a)Pointsets(b)Histosrampyramids(c)Intersections

Process

?Tocounteractthearbitrarynatureofthebin

borders,theentireprocessisrepeatedseveral

timeswiththeoriginrandomlyshifted.

PartialMatchCorrespondences

?Unequalcardinalitiesarenotanissue

?Algorithmmatchesthemostsimilarpairsfirst;

onlytheleastsimilarfeatureswillbe

unmatched

Results:SyntheticData

Approximationoftheoptimalbiy^ctivematching

19000

16000?Pyramidmatch

?Optimal1.6

14000

12000

o

o

u10000

g

ID

fi

6000

0.6

4000

0.4

02

50001000000

54MM10000

EqualCardinalitiesUnequalCardinalities

Results:ObjectRecognition

ObjectrecognitiononETH-80images

⑥

)。

A

o

e

n』

880

E75

u70

o65

一

七60

U

6

0

0

0

B

55

o20406080100120

Timetogenerate400x400kernelmatrix(sec)

PyramidKernelConclusions

?Bynotsearchingforspecificfeature

correspondences,thekernelcanruninless

thanpolynomialtime

?Accuracyisgenerallyhigherthanotherkernels

onbothartificialandreal-worlddata

?Canhandlearbitrary-lengthfeaturesets

SpatialPyramidMatching(2006)

?BeyondBagsofFeatures:SpatialPyramid

MatchingforRecognizingNatureScene

Categories

-SvetlanaLazebnik

一CordeliaSchmid

-JeanPonce

SpatialPyramidMatching(2006)

?Task:Wholeimageclassification

-Bagoffeaturesmethods(likepyramidkernel)are

somewhateffective,butignorefeaturelocation

?Alternatesolution:Kernel-basedrecognition

methodthatcalculatesaglobalrough

geometriccorrespondenceusingapyramid

matchingscheme

GeneralApproach

?Similarpyramidmatchingschemetoprevious

approach,but

-pyramidmatchinginimagespace

一clusteringinfeaturespace

?UsetrainingdatatoclusterfeaturesintoM

types

?Withinimage-spacebins,countoccurrences

ofeachfeaturetype

Process

?Algorithmparameters

-M=numberoffeaturetypestolearn(200)

-L=levelsinthepyramid(2)

?LearnMfeatureprototypesviak-means

clustering

?Ass