recognition introduction 计算机视觉 berkeley课件

C280,ComputerVision

Prof.TrevorDarrell

trevor@

Lecture12:IntroductiontoRecognition;

Boosting,HOG,andBag-of-WordModels

Lastfewlectures...

•Feature-basedAlignment

-Stitchingimagestogether

-Homographies,RANSAC,Warping,Blending

-Globalalignmentofplanarmodels

•DenseMotionModels

-Localmotion/featuredisplacement

-Parametricopticflow

•Stereo/'Multi-view':Estimatingdepthwithknowninter­

camerapose

•/Structure-from-motion,:Estimationofposeand3Dstructure

-Factorizationapproaches

—Globalalignmentwith3Dpointmodels

RecognitionChallenges/

Overview

ObjectCategorization

75

一

o一

-

n

l

u

o

口

C

6

O

O

O•HowtorecognizeANYcow

H

l

o

CDJ

q

o

-

B

n

s

一

4

K.Grauman,B.Leibe

Challenges:robustness

w

M

o

lIlluminationObjectposeClutter

n

l

u

o

口

C

6

O

O

O

H

l

o

g

q

o

-OcclusionsIntra-class

BViewpoint

n

sappearance

>

Challenges:robustness

w

oK

nl

.J

u

o

口

6C

0

0

O•DetectioninCrowdedScenes

)H>Learnobjectvariability

1

0-Changesinappearance,scale,andarticulation

.9q>»Compensateforclutter,overlap,andocclusion

0

-

B

n

s

>K.Grauman,B.Leibe

Challenges:contextandhumanexperience

w

K

o

l

n

l

u

o

口

C

6

O

O

O

H

l

o

g

q

o

-

B

n

s

>

K.Grauman,B.Leibe

Challenges:contextandhumanexperience

w

K

o

nl

l

U

0

4

C

6

0

0

0H)Contextcues

ol

g

q

o

-

B

n

s

>

Imagecredit:D.Hoeim

Challenges:learningwithminimalsupervision

w

K

o

l

n

l

u

o

口

C

6

O

O

O

H

l

o

g

q

o

-

B

n

s

>

K.Grauman,B.Leibe

Thisisa

pottopod

SlidefromPietroPerona,2004ObjectRecognitionworkshop

RBuegel,I562

SlidefromPietroPerona,2004ObjectRecognitionworkshop

Roughevolutionoffocusinrecognitionresearch

量“L

76qz46

Kw

lo工久2223

Jn

.nputimage。

u0A3g7

o

口

6C

0

0

O

)H

1

0

.9q>

01980s1990stoearly2000s2000-2010...

-

B

n

s

>

Inputs/outputs/assumptions

•Whatisthegoal?

-Sayyes/noastowhetheranobjectpresentinimage

And/or:

-Determineposeofanobject,e.g.forrobottograsp

-Categorizeallobjects

-Forcedchoicefrompoolofcategories

-Boundingboxonobject

-Fullsegmentation

-Buildamodelofanobjectcategory

Today

•Scanningwindowparadigm

•GIST

•HOG

•BoostedFaceDetection

•Local-featureAlignment;fromRobertsto

Lowe...

•BOWIndexing

Nextthreelectures

•Thursday:learningobjectcategoriesfromtheweb

-LSAandLDAmodels

-Harvestingtrainingdatafromtheweb

-Exploitingimageandtext

•Tues.Oct.20th:Generativemodels

-Condensation

-ISM

-Transformed-HDPs

-MoreContext...

•Thurs.Oct.22nd:AdvancedBOWkernels

-Pyramidandspatial-pyramidmatch

-Multi-kernellearning

-Latent-partSVMmodels

Scanningwindows...

Detectionviaclassification:Mainidea

Basiccomponent:abinaryclassifier

Kw

loCar/non-car

n—►

.J

uClassifier

o

口

6C

0

0

ONoYemtcaicar.

)H

1

0

.9q>

0

-

B

n

s

>K.Grauman,B.Leibe

Detectionviaclassification:Mainidea

Ifobjectmaybeinaclutteredscene,slideawindow

aroundlookingforit.

Kw

loCar/non-car

n—►

.J

uClassifier

o

口

6C

0

0

O

)H

1

0

(Essentially,ourskindetectorwasdoingthis,witha

.9q>

0windowthatwasonepixelbig.)

-

B

n

s

>K.Grauman,B.Leibe

Detectionviaclassification:Mainidea

Fleshingoutthis

pipelineabitmore,

weneedto:

1.Obtaintrainingdata

2.Definefeatures

3.Defineclassifier

w

oKTrainingexamples

nl

.J

uuu

o

口

6C

0

0Car/non-car

OClassifier

)H

1

0Feature

.9q>^extraction.

0

-

B

n

s

>K.Grauman,B.Leibe

Detectionviaclassification:Mainidea

•Considerallsubwindowsinanimage

>Sampleatmultiplescalesandpositions(andorientations)

•Makeadecisionperwindow:

»“DoesthiscontainobjectcategoryXornot?”

75

一

o一

-

n

l

u

o

口

C

6

O

O

O

H

l

o

CDJ

q

o

-

B

n

s

一

20

K.Grauman,B.Leibe

Featureextraction:

globalappearance

w

oK

nl

.J

u

o

口

6CSimpleholisticdescriptionsofimagecontent

0

0»grayscale/colorhistogram

O

)H»vectorofpixelintensities

1

0

.9q>

0

-

B

n

s

>K.Grauman,B.Leibe

Eigenfaces:globalappearancedescription

Anearlyappearance-basedapproachtofacerecognition

Generatelow­

dimensional

I*】❾国-->representation

ofappearance

75withalinear

一

一Eigenvectorscomputed

oTrainingimages

-fromcovariancematrixsubspace.

n

l

u

o

口

CProjectnew

6

Oimagesto”face

O

O

Hspace”.

l

oRecognitionvia

CDJ

q

onearestneighbors

-

B

ninfacespace

s

一

Turk&Pentland,1991

K.Grauman,B.Leibe

Featureextraction:globalappearance

•Pixel-basedrepresentationssensitivetosmallshifts

iJSBi

w

oK

nl

.J•Colororgrayscale-basedappearancedescriptioncanbe

u

osensitivetoilluminationandintra-classappearance

口

6Cvariation

0

0

Cartoonexample:

O

analbinokoala

)H

1

0

.9q>

0

-

B

n

s

>K.Grauman,B.Leibe

Gradient-basedrepresentations

•Consideredges,contours,and(oriented)intensity

gradients

一

.S,

I

O

5

1

口

6C

0

0

O

)H

L

O

G

Q

O

-

BN

S

>

K.Grauman,B.Leibe

Gradient-basedrepresentations

•Consideredges,contours,and(oriented)intensity

gradients

w

oK

nl

.J

u

o

口

6C

0

0•Summarizelocaldistributionofgradientswithhistogram

O

)HaLocallyorderless:offersinvariancetosmallshiftsandrotations

1

0>Contrast-normalization:trytocorrectforvariableillumination

.9q>

0

-

B

n

s

>K.Grauman,B.Leibe

I-

s

0

RepresentingImageStructurewith

“GIST”

Steerable

Vectorof

Globalfeatures

Oliva&Torralba(2001,2002,2006)

SlideCredit:OliviaNiir

WhatdoImagesStatisticssay

aboutDepth?

SlideCredit:Torralba,Olivia,J.HuangNiir

SceneScale

□''Thepointofviewthatanygivenobserveradoptsonaspecific

sceneisconstrainedbythevolumeofthescene."

□Howdoestheamountofcluttervaryagainstscenescaleinman­

madeenvironments?Innaturalenvironments?

■■■■

■■■■SlideCredit:Torralba,Olivia,J.HuangNiir

CategorizationofNaturalScenes

ConfusionMatrix(in%usingLayouttemplate):

Classificationofprototypicalscenes(400/category)Localorganization:

CoastCountrysideForestMountaincorrectfor92%images

(4similarimageson7K-NN)

Coast88.68.9

Countryside9.885.2

0.43.6

Mountain0.44.6

SlideCredit:OliviaNiir

o

oH

Gradient-basedrepresentations:

Histogramsoforientedgradients(HoG)

75

一

o一

-

n

l

u

o

口

C

6

OMapeachgridcellintheinput

O

O

Hwindowtoahistogramcounting

l

othegradientsperorientation.

CDJ

q

o

-Codeavailable:

B

n

shttp://pascal.inrialpes.fr/soft/olt/

一

DalalDTriggs,CVPR2005

K.Grauman,B.Leibe

Slidecredit:Dalal,Triggs,P.Barnum

Person/

Input

non-person

imageclassification

Slidecredit:Dalal,Triggs,RBarnum

NormalizeWeightedvoteContrastnormalizePerson/

Input_ComputeColledHOGsLinear

aiima&—►—►intospatial&-Aoveroverlapping——►overdetection—>non-person

imagegradientsS\M

colourorientationcellsspntialblockswindowclassification

•Testedwith

-RGB

-LAB

一Grayscale

•GammaNormalizationandCompression

一Squareroot

-Log

Slidecredit:Dalal,Triggs,RBarnum

Person/

Input

non-person

imageclassification

-101□□

centered□□

diagonal

-11

uncentered

□□H0□

1-808-1S□

cubic-Sobel

corrected

Slidecredit:Dalal,Triggs,RBarnum

NormalizeWeightedvoteContrastnormalizeColledHOGsPerson/

InputComputeLinear

gamma&->intospatial&Aoveroverlapping->overdetection>―>non-person

imagegradientsSVM

colourorientationcellsspntialblockswindowclassification

Histogramofgradient

orientations

-Orientation-Position

90

13545

1800

225315

270

-Weightedbymagnitude

Slidecredit:Dalal,Triggs,RBarnum

NormalizeWeightedvoteContrastnormalizeColledHOGsPerson/

Input_ComputeLinear

gamma&intospatial&Aoveroverlappingoverdetection―►non-person

imagegradientsSVM

colourorientationcellsspntialblockswindowclassification

R-HOGC-HOG

ft

爸

0

王

1±

RadialBins.AnsularBins

Slidecredit:Dalal,Triggs,RBarnum

Person/

Input

non-person

image

classification

R-HOGC-HOG

CellCenterBin

-H

a

o

O

王

RadialBins.AngularBins

Ll-norm:v——>v/(||v||i+£)Ll-sqrt:v­»\/v/(||v||i+6)

L2-norm:v—，+FL2-hys:L2-norm,plusclippingat.2andrcnomalizing

Slidecredit:Dalal,Triggs,RBarnum

Person/

Input

non-person

imageclassification

Slidecredit:Dalal,Triggs,RBarnum

Person/

Input

non-person

imageclassification

Slidecredit:Dalal,Triggs,RBarnum

Person/

Input

non-person

imageclassification

Slidecredit:Dalal,Triggs,RBarnum

Slidecredit:Dalal,Triggs,RBarnum

BoostedFaceDetection

withGradientFeatures

Gradient-basedrepresentations:

Rectangularfeatures

w

K

o

l

n

l

u

o

口

C

6

O

O

OComputedifferencesbetweensumsofpixelsinrectangles

H

l

o

gCapturescontrastinadjacentspatialregions,efficientto

q

ocompute

-

B

n

sEachfeatureparameterizedbyscale,position,type.

>

Viola&Jones,CVPR2001

K.Grauman,B.Leibe

ioosting

•Buildastrongclassifierbycombiningnumberof"weak

classifiers”，whichneedonlybebetterthanchance

•Sequentiallearningprocess:ateachiteration,adda

weakclassifier

•Flexibletochoiceofweaklearner

75

一

o一

->includingfastsimpleclassifiersthatalonemaybeinaccurate

n

l

u

o

口1

C•WeIIlookatFreund&Schapire'sAdaBoostalgorithm

6

O

OaEasytoimplement

O

H

l>BaselearningalgorithmforViola-Jonesfacedetector

o

CDJ

q

o

-

B

n

s

一

46

K.Grauman,B.Leibe

AdaBoost:Intuition

Considera2-dfeature

Weakspacewithpositiveand

Classifier1negativeexamples.

Eachweakclassifiersplits

w

K

othetrainingexampleswith

l

n

latleast50%accuracy.

U

0

4

CExamplesmisclassifiedby

6

0

0apreviousweaklearner

0)Haregivenmoreemphasis

1

0atfuturerounds.

,9q>

0

-

B

n

s

一FigureadaptedfromFreundandSchapire

47

K.Grauman,B.Leibe

AdaBoost:Intuition

Weights

Increased

Weak

Classifier1

•oWeak

ooClassifier2

-

,-s

0

1

n

l

u

o

C口

6

O

O

O

H

l

o

.sq>

o

-

B

n

s

一48

K.Grauman,B.Leibe

AdaBoost:Intuition

75

一

o一

-

n

l

uWeak

oclassifier3

口

C

6

O

O

OFinalclassifieris

H

lcombinationofthe

oweakclassifiers

CDJ

q

o

-

B

n

s

一

49

K.Grauman,B.Leibe

•Givenexampleimages(J；I,,(^n,?/n)where

yi=0,1fornegativeandpositiveexamplesrespec­

tively.AdaBoostAlgorithm

•Initializeweights=for仍=0,1respec­Startwith

tively,wheremandIarethenumberofnegativesanduniformweights

positivesrespectively.ontraining

•Forf=1,...,T:examples

1.Normalizetheweights.

ForTrounds

sothatwtisaprobabilitydistribution.

Evaluate

2.Foreachfeature,j,trainaclassifierhjwhich

isrestrictedtousingasinglefeature.Theweightederror

errorisevaluatedwithrespecttowt,e；=foreachfeature,

皿电(g)-yi\.pickbest.

3.Choosetheclassifier.In.withthelowesterroret.

4.Updatetheweights:

Re-weighttheexamples:

-+i,t=皿,iB；CiIncorrectlyclassified->moreweight

whereei=0ifexampleXiisclassifiedcor­Correctlyclassified->lessweight

rectly,a=1otherwise,and仇=y1七■.

•Thefinalstrongclassifieris:

Finalclassifieriscombinationofthe

刀，1a力加(/)NI£着at

'-10otherwiseweakones,weightedaccordingto

errortheyhad.

wherec\f=log+Freund&Schapire1995

Example:Facedetection

•Frontalfacesareagoodexampleofaclasswhere

globalappearancemodels+aslidingwindow

detectionapproachfitwell:

>Regular2Dstructure

>Centeroffacealmostshapedlikea“patch"/window

75

一

o一

-

n

l

u

o

口

C

6

O

O

O

H

l

o

CDJ

q

o•Nowwe'lltakeAdaBoostandseehowtheViola-

-

B

nJonesfacedetectorworks

s

一

51

K.Grauman,B.Leibe

Featureextraction

“Rectangular”filters

Featureoutputisdifference

betweenadjacentregions

75

一

o一

-

n

lEfficientlycomputable

u

owithintegralimage:any

口

Csumcanbecomputed

6

O

Oinconstanttime

O

H

l

oAvoidscalingimages9

CDJscalefeaturesdirectly

q

oforsamecost=/+(A+3+C+Z))—(A+C+/+B)

-

B

n

s

一

Viola&Jones,CVPR200152

K.Grauman,B.Leibe

Largelibraryoffilters

75

一

o一

-

n

l

u

o

口

C

6

O

O

O

H

l

oUseAdaBoostbothtoselecttheinformative

CDJ

qfeaturesandtoformtheclassifier

o

-

B

n

s

一

Viola&Jones,CVPR2001

AdaBoostforfeature+classifierselection

•Wanttoselectthesinglerectanglefeatureandthreshold

thatbestseparatespositive(faces)andnegative(non­

faces)trainingexamples,intermsofweightederror.

ftResultingweakclassifier:

a一e■o~~e㊀।eooo〉

T.o

l

n+1iff(x)>9

ltt

ht(x)=

Ui

0-1otherwise

4

C

6■6^0。㊀OOO———

0

0

：——f[(x)一Fornextround,reweightthe

0)Hexamplesaccordingtoerrors,

。1

①Outputsofapossiblechooseanotherfilter/threshold

q一rectanglefeatureon

ocombo.

-facesandnon-faces.

B

n

s

>Viola&Jones,CVPR2001

•Givenexampleimages(J；I,,(^n,?/n)where

yi=0,1fornegativeandpositiveexamplesrespec­

tively.AdaBoostAlgorithm

•Initializeweights=for仍=0,1respec­Startwith

tively,wheremandIarethenumberofnegativesanduniformweights

positivesrespectively.ontraining

•Forf=1,...,T:examples

1.Normalizetheweights.

ForTrounds

sothatwtisaprobabilitydistribution.

Evaluate

2.Foreachfeature,trainaclassifierh)which

isrestrictedtousingasinglefeature.Theweightederror

errorisevaluatedwithrespecttowt,与=foreachfeature,

皿陶(g)一词.pickbest.

3.Choosetheclassifier,lit,withthelowesterrore.t.

4.Updatetheweights:

Re-weighttheexamples:

Wt+l,i=皿，俐"Incorrectlyclassified->moreweight

wheree/=0ifexamplexiisclassifiedcor-Correctlyclassified->lessweight

•Thefinalstrongclassifieris:

Finalclassifieriscombinationofthe

i£屋1。也(1)>}E?=i

h[x)=

0otherwiseweakones,weightedaccordingto

errortheyhad.

whereat=logJ-Freund&Schapire1995

AdaBoostforEfficientFeature

Selection

•ImageFeatures=WeakClassifiers

•Foreachroundofboosting:

-Evaluateeachrectanglefilteroneachexample

-Sortexamplesbyfiltervalues

-Selectbestthresholdforeachfilter(minerror)

•Soiledlistcanbequicklyscaimedfortheoptimalthreshold

-Selectbestfilter/thresholdcombination

-Weightonthisfeatureisasimplefunctionofen*orrate

-Reweightexamples

ViolaandJones.Robustobjectdetectionusingaboostedcascadeofsimplefeatures.CVPR2001

•Evenifthefiltersarefasttocompute,each

newimagehasalotofpossiblewindowsto

search.

•Howtomakethedetectionmoreefficient?

Cascadingclassifiersfordetection

Forefficiency,applyless

accuratebutfasterclassifiers

firsttoimmediatelydiscard

windowsthatclearlyappearto

benegative;e.g.,

w

oKaFilterforpromisingregionswithan

nl

.Jinitialinexpensiveclassifier

u

o

口aBuildachainofclassifiers,choosing

6Ccheaponeswithlowfalsenegative

0

0ratesearlyinthechain

O

)H

1

0

.9q>

0Fleuret&Geman,IJCV2001

-RowleyetaL,PAMI1998

B

n

sViola&Jones,CVPR200158

>K.Grauman,B.LeibeFigurefromViola&JonesCVPR2001

Viola-JonesFaceDetector:Summary

翻・■■可■■)■/■

♦电•感所国,通・・F

■*妙硒I二中

再⑥三■-

♦5电««♦费型IT

卧♦电•即♦出■♦卜

wJ/KJtL，・<AJ

w

oK

nl

.J

u

o

口

C

6Non-faces

0

0

O•Trainwith5Kpositives,350Mnegatives

)H

1•Real-timedetectorusing38layercascade

0

•6061featuresinfinallayer

.9q>

0•[ImplementationavailableinOpenCV:

-

B/technology/computing/opencv/]

n

s59

>K.Grauman,B.Leibe

Viola-JonesFaceDetector:Results

Firsttwofeatures

selected

r