Harris corner detection

Reading • Szeliski: 4.1

Copyright By cscodehelp代写 加微信 cscodehelp

Feature extraction: Corners and blobs

Feature extraction: Corners and blobs • Interest points:

– A corner can be defined as the intersection of two edges.

– blob detection methods are aiming at detecting regions in the image that differ in properties, such as brightness or color, compared to surrounding regions

(credit: Wikipedia)

Motivation: Automatic panoramas

Why extract features?

• Motivation: panorama stitching

– We have two images – how do we combine them?

Why extract features? • Motivation: panorama stitching

– We have two images – how do we combine them?

Step 0: interest point detection Step 1: extract features

Step 2: match features

Why extract features? • Motivation: panorama stitching

– We have two images – how do we combine them?

Step 0: interest point detection Step 1: extract features

Step 2: match features

Step 3: align images

by Diva Sian

Image matching

by swashford

Harder case

by Diva Sian

Harder still?

Answer below (look for tiny colored squares…)

NASA Mars Rover images with SIFT feature matches

Feature Matching

Feature Matching

Invariant local features

Find features that are invariant to transformations – geometric invariance: translation, rotation, scale – photometric invariance: brightness, exposure, …

Feature Descriptors

Advantages of local features Locality

– features are local, so robust to occlusion and clutter Quantity

– hundreds or thousands in a single image Distinctiveness:

– can differentiate a large database of objects Efficiency

– real-time performance achievable

More motivation…

Feature points are used for: – Image alignment

– 3D reconstruction

– Motion tracking

– Object recognition

– Indexing and database retrieval – Robot navigation

– … other

Feature detection: find it Feature descriptor: represent it Feature matching: match it

Feature tracking: track it, when motion

Local features: main components

1) Detection: Identify the interest points

2) Description: Extract vector feature descriptor surrounding each interest point.

3) Matching:Determine correspondence between descriptors in two views

x =[x(1),,x(1)] 11d

x =[x(2),,x(2)] 21d

What makes a good feature?

Snoop demo

Want uniqueness

Look for image regions that are unusual

– Lead to distinct matches in other images

– The particular object in only a few number of images

How to define “unusual”?

Local measures of uniqueness Suppose we only consider a small window of pixels

– What defines whether a feature is a good or bad candidate?

Credit: S. Seitz, D. Frolova, D. Simakov

Local measure of feature uniqueness

How does the window change when you shift it?

Shifting the window in any direction causes a big change

“flat” region: no change in all directions

no change along the edge direction

significant change in all directions

Credit: S. Seitz, D. Frolova, D. Simakov

Harris corner detection: the math

Consider shifting the window W by (u,v)

• how do the pixels in W change?

• compare each pixel before and after by summing up the squared differences (SSD)

• this defines an SSD “error” E(u,v):

• We are happy if this error is high

• Slow to compute exactly for each pixel and each offset (u,v)

Small motion assumption expansion of I:

If the motion (u,v) is small, then first order approximation is good

Plugging this into the formula on the previous slide…

Corner detection: the math

Consider shifting the window W by (u,v) • define an SSD “error” E(u,v):

Corner detection: the math Consider shifting the window W by (u,v)

• define an SSD “error” E(u,v):

• Thus, E(u,v) is locally approximated as a quadratic error function

Corner detection: the math The surface E(u,v) is locally approximated by a quadratic form.

Horizontal edge:

Vertical edge:

Quick eigenvalue/eigenvector review The eigenvectors of a matrix A are the vectors x that satisfy:

The scalar is the eigenvalue corresponding to x

– The eigenvalues are found by solving:

– In our case, A = H is a 2×2 matrix, so we have

– The solution:

Solve this equation:

X is eigenvector

𝜆 contains eigenvalues

0.9 0.7 − 𝜆

0.1−𝜆 0.7−𝜆 −0.9×0.3=0

Example By:

𝐴−𝜆𝐼 =0 0.1 − 𝜆 0.3

𝜆2 −0.8𝜆−0.2=0 𝜆 = 1 𝑜𝑟 𝜆 = −0.2

𝐴 − 𝜆𝐼 𝑋 = 0

• Which of the following can be called as the “corners”

– Pixels with large gradient magnitude

– Pixels at the end of a straight line

– Pixels at the junction of horizontal and vertical lines

Interpreting the eigenvalues

Classification of image points using eigenvalues of H: 2

R=12 –k(1 +2)2

R is large for corner

R is negative (with large magnitude) for edge R is small for flat region

1 and 2 are small;

E is almost constant in all directions

1 and 2 are large, 1 ~ 2;

E increases in all directions

“Flat” region

Other Versions of The Harris operator

min is a variant of the “Harris operator” for feature detection

Corner detection summary

Here’s what you do

• Compute the gradient at each point in the image

• Create the H matrix from the entries in the gradient

• Compute the eigenvalues.

• Find points with large response (min > threshold)

• Choose those points where min is a local maximum as features

Harris detector example

f value (red high, blue low)

Threshold (f > value)

Find local maxima of f

Harris features (in red)

Weighting the derivatives

• In practice, using a simple window W doesn’t work too well

• Instead, we’ll weight each derivative value based on its distance from the center pixel

[Harris88]

I2( ) I I ( )

( , )=g( ) x D x y D 1.Image

Ix 2 IxIy

g(Iy2) g(IxIy)

ID I II()I2()

y D derivatives

(optionally, blur first)

detM = 12

traceM = + 12

2. Square of derivatives

3. Gaussian filter g(I)

Ix2 g(Ix2)

4. Cornerness function – both eigenvalues are strong

5. Local maxima above some threshold

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com