Harris corner detection
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
Credit: Matt Brown
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
Image matching
by Diva Sian
by swashford
Harder case
by Diva Sian by scgbt
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
Approach
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 x1 = [ x1(1) , ! , xd(1) ]
each interest point.
3) Matching: Determine
correspondence between x 2 = [ x1( 2) ,!, xd( 2) ]
descriptors in two views
Kristen Grauman
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: “edge”: “corner”:
no change in all no change along the significant change in
directions edge direction 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 (u,v)
W
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
Taylor Series 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) W
(u,v)
• define an SSD “error” E(u,v):
Corner detection: the math
Consider shifting the window W by (u,v) W
(u,v)
• define an SSD “error” E(u,v):
Corner detection: the math
The surface E(u,v) is locally approximated:
E(u,v)
Horizontal edge:
v
u
E(u,v)
Vertical edge:
v
u
Quick eigenvalue/eigenvector review
The eigenvectors of a matrix A are the vectors x that satisfy:
The scalar l is the eigenvalue corresponding to x
– The eigenvalues are found by solving:
– In our case, A = H is a 2x2 matrix, so we have
– The solution:
Example
By:
𝐴 − 𝜆𝐼 = 0
0.1 − 𝜆 0.3
=0
Solve this equation: 0.9 0.7 − 𝜆
0.1 − 𝜆 0.7 − 𝜆 − 0.9×0.3 = 0
X is eigenvector
𝜆! − 0.8𝜆 − 0.2 = 0
𝜆 contains eigenvalues 𝜆 = 1 𝑜𝑟 𝜆 = −0.2
𝐴𝑋 = 𝜆𝑋
𝐴 − 𝜆𝐼 𝑋 = 0
Quiz
• 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:
l2 “Edge”
l2 >> l1 “Corner”
R= l1 l2 – k(l1 + l2)2
l1 and l2 are large,
l1 ~ l2;
R is large for corner E increases in all
R is negative (with large magnitude) for edge
directions
R is small for flat region
l1 and l2 are small;
E is almost constant “Flat” “Edge”
in all directions region l1 >> l2
l1
Other Versions of The Harris operator
lmin 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 (lmin > threshold)
• Choose those points where lmin 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)
