Harris corner detection
Reading • Szeliski: 4.1
Copyright By PowCoder代写 加微信 powcoder
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com