Robotica - Intranet DEIBhome.deib.polimi.it/restelli/MyWebSite/pdf/Lezione4.pdf · 27/10/2006 Corso...

Robotica Robotica

Anno accademico 2006/2007

Davide [email protected]

27/10/200627/10/2006 Corso di Robotica 06/07Corso di Robotica 06/07Davide Migliore - [email protected] Migliore - [email protected]

22

TodayToday

● What is a feature?● Some useful information● The world of features:

– Detectors● Edges detection● Corners/Points detection

– Descriptors ?!?!?


33

What is a feature?What is a feature?


44

ImagesImages

● An image is a matrix of pixels ● Resolution

– Digital cameras: 1600 X 1200 at a minimum– Video cameras: ~640 X 480

● Grayscale: generally 8 bits per pixel – Intensities in range [0…255]

● RGB color: 3 8-bit color planes


55

Image conversionImage conversion

● RGB → Grayscale: Mean color value, or weight by perceptual importance

● Grayscale → Binary: Choose threshold based on histogram of image intensities


66

Color representationColor representation

● RGB, HSV (hue, saturation, value), YUV, etc.● Luminance: Perceived intensity● Chrominance: Perceived color

– HS(V), (Y)UV, etc.– Normalized RGB removes some illumination

dependence:


77

Binary OperationsBinary Operations

● Dilation, erosion – Dilation: All 0’s next to a 1 → 1 (Enlarge foreground)– Erosion: All 1’s next to a 0 → 0 (Enlarge background)

● Connected components– Uniquely label each n-connected region in binary image– 4- and 8-connectedness

● Moments: Region statistics– Zeroth-order: Size– First-order: Position (centroid)– Second-order: Orientation


88

● Idea: Blend four pixel values surrounding source, weighted by nearness

Vertical blend Horizontal blend

Bilinear InterpolationBilinear Interpolation


99

Image Comparison: SSDImage Comparison: SSD● Given a template image and an image

, how to quantify the similarity between them for a given alignment?

● Sum of squared differences (SSD)


1010

Cross-Correlation for Cross-Correlation for Template MatchingTemplate Matching

● Note that SSD formula can be written:

● First two terms fixed → last term measures mismatch—the cross-correlation:

● In practice, normalize by image magnitude when shifting template to search for matches


1111

FilteringFiltering

● Idea: Analyze neighborhood around some point in image with filter function ; put result in new image at corresponding location

● System properties– Shift invariance: Same inputs give same outputs,

regardless of location– Superposition: Output on sum of images = – Sum of outputs on separate images– Scaling: Output on scaled image = Scaled output on

image● Linear shift invariance → Convolution


1212

Discrete FilteringDiscrete Filtering

● Linear filter: Weighted sum of pixels over rectangular neighborhood—kernel defines weights

● Think of kernel as template being matched by correlation

● Convolution: Correlation with kernel rotated 180°

● Dealing with image edges– Zero-padding– Border replication

111-121-1-11


1313

ConvolutionConvolution

● Definition:

● Shorter notation: ● Properties

– Commutative– Associative

● Fourier theorem: Convolution in spatial domain = Multiplication in frequency domain


1414

Filtering Example 1: Filtering Example 1:

111

-121

-1-11

3

2

1

2

2

1

3

2

32

21

22

32

Rotate

1-1-1

12-1

111


1515

Step 1Step 1

3

2

1

2

2

1

3

2

32

21

22

32 5

3

2

1

2

2

1

3

2

32

21

22

32

1-2-1

24-1

111

1-1-1

12-1

111


1616

Step 2Step 2

32

1

2

21

3

2 3

2

21

2

2

3

2

1-1-1

12-1

111

3

2

1

2

2

1

3

2

32

21

22

32

3

2

1

2

2

1

3

2

32

21

22

32

3-1-2

24-2

111

45


1717

Step 3Step 3

1-1-1

12-1

111

3

2

1

2

2

1

3

2

32

21

22

32

3-3-1

34-2

111

4 45

3

2

1

2

2

1

3

2

32

21

22

32


1818

Step 4Step 4

1-1-1

12-1

111

3

2

1

2

2

1

3

2

32

21

22

32 4 4 -25

1-3-3

16-2

111

3

2

1

2

2

1

3

2

32

21

22

32


1919

Step 5Step 5

1-1-1

12-1

111

3

2

1

2

2

1

3

2

32

21

22

32

3

2

1

2

2

1

3

2

32

21

22

32

3

2

1

2

2

1

3

2

32

21

22

32 4 4

9

-25

2-2-1

14-1

221


2020

Step 6Step 6

1-1-1

12-1

111

3

2

1

2

2

1

3

2

32

21

22

32

3

2

1

2

2

1

3

2

32

21

22

32

6

4 4

9

-25

1-2-2

32-2

222


2121

Final ResultFinal Result

12

7

6

4

8

6

14

4

59

59

511

-25


2222

SeparabilitySeparability

● Definition: 2-D kernel can be written as convolution of two 1-D kernels

● Advantage: Efficiency—Convolving image with kernel requires

multiplies vs. for non-separable kernel


2323

Smoothing (Low-Pass) FiltersSmoothing (Low-Pass) Filters

● Replace each pixel with average of neighbors● Benefits: Suppress noise, aliasing● Disadvantage: Sharp features blurred● Types

– Mean filter (box)– Median (nonlinear)– Gaussian 111

111

111

3 x 3 box filter


2424

Box Filter: SmoothingBox Filter: Smoothing

7 x 7 kernelOriginal image


2525

Gaussian KernelGaussian Kernel

● Idea: Weight contributions of neighboring pixels by nearness


2626

Gaussian: BenefitsGaussian: Benefits

● Rotational symmetry treats features of all orientations equally (isotropy)

● Smooth roll-off reduces “ringing”● Efficient: Rule of thumb is kernel width ≥ 5σ

– Separable

– Cascadable: Approach to large σ comes from identity


2727

Gaussian: SmoothingGaussian: Smoothing

σ = 1 σ = 3

7 x 7kernel

Originalimage


2828

The Features worldThe Features world


2929

Edge CausesEdge Causes

● Depth discontinuity

● Surface orientation discontinuity

● Reflectance discontinuity (i.e., change in surface material properties)

● Illumination discontinuity (e.g., shadow)

depth discontinuity

surface color discontinuity

illumination discontinuity

surface normal discontinuity


3030

GradientGradient

● Think of image intensities as a function . Gradient of image is a vector

field as for a normal 2-D height function:

● Edge: Place where gradient magnitude is high; orthogonal to gradient direction


3131

What is the gradient?What is the gradient?

)0,(, ky

I

x

I =

∂∂

∂∂

Change

No Change


3232


),0(, ky

I

x

I =

∂∂

∂∂

No Change

Change


3333


)2,1(, kky

I

x

I =

∂∂

∂∂

Much ChangeMuch Change

Less ChangeLess ChangeGradient direction is Gradient direction is perpendicular to edge.perpendicular to edge.

Gradient Magnitude measures Gradient Magnitude measures edge strength.edge strength.


3434

Edge DetectionEdge Detection

● Edge Types– Step edge (ramp)– Line edge (roof)

● Searching for Edges:– Filter: Smooth image– Enhance: Apply numerical derivative approximation– Detect: Threshold to find strong edges– Localize/analyze: Reject spurious edges, include

weak but justified edges


3535

Effects of noiseEffects of noise

● Consider a single row or column of the image– Plotting intensity as a function of position gives a signal


3636

Effects of noise: solutionEffects of noise: solution


3737

Step edge detectionStep edge detection

● First derivative edge detectors: Look for extrema– Sobel operator

– Prewitt, Roberts cross

– Derivative of Gaussian

● Second derivative: Look for zero-crossings– Laplacian : Isotropic

– Second directional derivative

– Laplacian of Gaussian/Difference of Gaussians

-1-2-1000121

-101-202-101

Sobel x Sobel y


3838

● Prewitt, Roberts crossPrewitt, Roberts cross

(a): Roberts’ cross operator (b): 3x3 Prewitt operator(a): Roberts’ cross operator (b): 3x3 Prewitt operator(c): Sobel operator (d) 4x4 Prewitt operator(c): Sobel operator (d) 4x4 Prewitt operator


3939

Derivative of GaussianDerivative of Gaussian


4040

Derivative of GaussianDerivative of Gaussian

Derivative theorem of convolution


4141

Laplacian of GaussianLaplacian of Gaussian


4242

Laplacian of GaussianLaplacian of Gaussian

Consider

Laplacian of Gaussianoperator


4343

-101

-202

-101

0

0

0

0

2

2

2

2

20

20

20

20

Rotate

10-1

20-2

10-1

Edge Filtering ExampleEdge Filtering Example


4444

Step 1Step 1

0

0

1

2

2

1

2

2

22

20

20

22 0

0

0

0

0

2

2

2

2

20

20

20

20

00-1

00-2

10-1

10-1

20-2

10-1


4545

Step 2Step 2

0

0

1

2

2

2

3

2

22

20

20

22 60

0

0

0

0

2

2

2

2

20

20

20

20

200

400

10-1

10-1

20-2

10-1


4646

Step 3Step 3

0

0

1

2

2

2

3

2

30

20

20

30 6 60

0

0

0

0

2

2

2

2

20

20

20

20

200

400

10-1

10-1

20-2

10-1


4747

Step 4Step 4

0

0

0

0

2

2

3

2

30

20

20

30 6 6 -60

0

0

0

0

2

2

2

2

20

20

20

20

10-2

20-4

10-1

10-1

20-2

10-1

edgeeffect


4848

Sobel Edge Detection: Sobel Edge Detection: Gradient ApproximationGradient Approximation

Horizontal Vertical


4949

Sobel vs. LoG Edge DetectionSobel vs. LoG Edge Detection

Sobel LoG


5050

Canny Edge DetectionCanny Edge Detection

● Derivative of Gaussian● Non-maximum suppression

– Thin multi-pixel wide “ridges” down to single pixel

● Thresholding– Low, high edge-strength thresholds

– Accept all edges over low threshold that are connected to edge over high threshold


5151

Non-maximum SuppressionNon-maximum Suppression

•We wish to mark points along the curve where the magnitude is biggest.


5252


At q, we have a maximum if the value is larger than those at both p and at r. Interpolate to get these values.


5353


Assume the marked point is an edge point. Then we construct the tangent to the edge curve (which is normal to the gradient at that point) and use this to predict the next points (here either r or s).


5454


courtesy of G. Loy

Original image Gradient magnitudeNon-maxima suppressed


5555

Edge HysteresisEdge Hysteresis

● Hysteresis: A lag or momentum factor

● Idea: Maintain two thresholds khigh and klow– Use khigh to find strong edges to start edge

chain

– Use klow to find weak edges which continue edge chain

● Typical ratio of thresholds is roughly

khigh / klow = 2


5656

Edge HysteresisEdge Hysteresis

courtesy of G. Loy

gap is gone

Originalimage

Strongedges

only

Strong +connectedweak edges

Weakedges


5757

Canny Edge Detection: Example


5858

original

Edge detection by subtraction


5959

smoothed (5x5 Gaussian)



6060

smoothed – original(scaled by 4, offset +128)

Why doesthis work?



6161

Laplacian of Gaussian

Gaussian delta function

Gaussian - image filter


6262

How can we detect lines ?

An edge is not a line...


6363

Option 1:– Search for the line at every possible

position/orientation– What is the cost of this operation?

Option 2:– Use a voting scheme: Hough transform

Finding lines in an image


6464

Connection between image (x,y) and Hough (m,b) spaces– A line in the image corresponds to a point in Hough

space– To go from image space to Hough space:

● given a set of points (x,y), find all (m,b) such that y = mx + b

x

y

m

b

m0

b0

image space Hough space



6565

Connection between image (x,y) and Hough (m,b) spaces– A line in the image corresponds to a point in Hough space– To go from image space to Hough space:

● given a set of points (x,y), find all (m,b) such that y = mx + b

– What does a point (x0, y0) in the image space map to?

x

y

m

b

image space Hough space

– A: the solutions of b = -x0m + y0

– this is a line in Hough space

x0

y0



6666

Hough transform algorithmHough transform algorithmTypically use a different parameterization

• d is the perpendicular distance from the line to the origin∀ θ is the angle this perpendicular makes with the x axis• Why?


6767

Hough transform algorithmHough transform algorithmTypically use a different parameterization

• d is the perpendicular distance from the line to the origin∀ θ is the angle this perpendicular makes with the x axis• Why?

Basic Hough transform algorithm1. Initialize H[d, θ]=0

2. for each edge point I[x,y] in the image for θ = 0 to 180

H[d, θ] += 1

3. Find the value(s) of (d, θ) where H[d, θ] is maximum

4. The detected line in the image is given by

What’s the running time (measured in # votes)?


6868

tokens VotesHorizontal axis is θ, vertical is d.

Hough transform algorithmHough transform algorithm


6969

tokens votes



7070



7171

ExtensionsExtensionsExtension 1: Use the image gradient

1. same2. for each edge point I[x,y] in the image

compute unique (d, θ) based on image gradient at (x,y)

H[d, θ] += 1

3. same4. same

What’s the running time measured in votes?


7272

ExtensionsExtensionsExtension 1: Use the image gradient

1. same2. for each edge point I[x,y] in the image

compute unique (d, θ) based on image gradient at (x,y)

H[d, θ] += 1

3. same4. same

What’s the running time measured in votes?

Extension 2• give more votes for stronger edges

Extension 3• change the sampling of (d, θ) to give more/less resolution

Extension 4• The same procedure can be used with circles, squares, or any

other shape


7373

Edge detectors perform poorly at corners.

Corners provide repeatable points for matching, so are worth detecting.

Idea:

• Exactly at a corner, gradient is ill defined.

• However, in the region around a corner, gradient has two or more different values.

Finding CornersFinding Corners


7474

Corner DetectionCorner Detection● Basic idea: Find points where two edges meet

—i.e., high gradient in orthogonal directions● Examine gradient over window (Shi & Tomasi,

1994)

● Edge strength encoded by eigenvalues ; corner is where over threshold

● Harris corners (Harris & Stephens, 1988), Susan corners (Smith & Brady, 1997)


7575

The Harris corner detectorThe Harris corner detector

=

∑∑∑∑

2

2

yyx

yxx

III

IIIC

Form the second-moment matrix:

Sum over a small region around the hypothetical corner

Gradient with respect to x, times gradient with respect to y

Matrix is symmetricSlide credit: David Jacobs


7676

Simple CaseSimple Case

=

=

∑∑∑∑

2

12

2

0

0

λλ

yyx

yxx

III

IIIC

First, consider case where:

This means dominant gradient directions align with x or y axis

If either λ is close to 0, then this is not a corner, so look for locations where both are large.


7777

General CaseGeneral Case

It can be shown that since C is symmetric:

RRC

= −

2

11

0

0

λλ

So every case is like a rotated version of the one on last slide.


7878

So, to detect cornersSo, to detect corners

● Filter image with Gaussian to reduce noise● Compute magnitude of the x and y gradients at

each pixel● Construct C in a window around each pixel

(Harris uses a Gaussian window – just blur)● Solve for product of λs (determinant of C)

● If λs are both big (product reaches local maximum and is above threshold), we have a corner (Harris also checks that ratio of λs is not too high)


7979

Gradient OrientationsGradient Orientations


8080

Step 1: Gradient OrientationsStep 1: Gradient Orientations


8181

EigenvaluesEigenvalues

Corners are detected where the product of the ellipse axis lengths reaches a local maximum.


8282

Example: Corner DetectionExample: Corner Detection

courtesy of S. Smith

SUSAN corners

Robotica - Intranet DEIBhome.deib.polimi.it/restelli/MyWebSite/pdf/Lezione4.pdf · 27/10/2006 Corso...

Documents

Transcript of Robotica - Intranet DEIBhome.deib.polimi.it/restelli/MyWebSite/pdf/Lezione4.pdf · 27/10/2006 Corso...