程序代写代做代考 database graph Fundamentals of Computer Vision

Fundamentals of Computer Vision
Lecture

• General Hough transform.
• Some applications
• Why detect corners?
• Visualizing quadratics.
• Harris corner detector.
• Multi-scale detection.
Overview of today’s lecture

Slide credits
Most of these slides were adapted from:
• Kris Kitani (15-463, Fall 2016), Ioannis Gkioulekas (16-385, Spring 2019). Some slides were inspired or taken from:
• Fredo Durand (MIT).
• James Hays (Georgia Tech).

Generalized Hough Transform
• Whatifwewanttodetectarbitraryshapes?
Intuition:
x
xx
x
Displacement vectors
Ref. point
Model image Novel image Vote space
Now suppose those colors encode gradient directions…
Kristen Grauman
x

Generalized Hough Transform
• Define a model shape by its boundary points and a reference point.
xa
θ
θ
p2
p1
Model shape
Offline procedure:
At each boundary point, compute displacement vector: r = a – pi.
Store these vectors in a table indexed by gradient orientation θ.
θ
…
θ
…
[Dana H. Ballard, Generalizing the Hough Transform to Detect Arbitrary Shapes, 1980] Kristen Grauman
…

Generalized Hough Transform
Detection procedure:
For each edge point:
• Use its gradient orientation θ to index into stored table
• Use retrieved r vectors to vote for reference point
x
xx xx
θ
θ
θ
θ
p1
θ
Novel image
θ
…
θ
…
Assuming translation is the only transformation here, i.e., orientation and scale are fixed.
Kristen Grauman
…

Generalized Hough for object detection
• Instead of indexing displacements by gradient orientation, index by matched local patterns.
“visual codeword” with displacement vectors
training image
B. Leibe, A. Leonardis, and B. Schiele, Combined Object Categorization and Segmentation with an Implicit Shape Model, ECCV Workshop on
Statistical Learning in Computer Vision 2004
Source: L. Lazebnik

Generalized Hough for object detection
• Instead of indexing displacements by gradient orientation, index by “visual codeword”
test image
Source: L. Lazebnik

Basic reading:
• Szeliski textbook, Sections 3.4, 3.5
References
Additional reading:
• Burt and Adelson, “The Laplacian Pyramid as a Compact Image Code,” IEEE ToC 1983.
The original Laplacian pyramid paper.
• Hubel and Wiesel, “Receptive fields, binocular interaction and functional architecture in the cat’s
visual cortex,” The Journal of Physiology 1962
A foundational paper describing information processing in the visual system, including the
different types of filtering it performs;; Hubel and Wiesel won the Nobel Prize in Medicine in 1981 for the discoveries described in this paper.

Harris Corner Detection

Why detect corners?

Why detect corners?
Image alignment (homography, fundamental matrix) 3D reconstruction
Motion tracking
Object recognition
Indexing and database retrieval Robot navigation

Planar object instance recognition
Database of planar objects Instance recognition

3D object recognition
Database of 3D objects 3D objects recognition

Recognition under occlusion

Robot Localization

Image matching

NASA Mars Rover images
Where are the corresponding points?

Pick a point in the image. Find it again in the next image.
What type of feature would you select?

Pick a point in the image. Find it again in the next image.
What type of feature would you select?
a corner

Visualizing quadratics

Equation of a circle
Equation of a ‘bowl’ (paraboloid)
If you slice the bowl at what do you get?

can be written in matrix form like this…

‘sliced at 1’

What happens if you increase coefficient on x?
and slice at 1

What happens if you increase coefficient on x?
and slice at 1
decrease width in x!

What happens if you increase coefficient on y?
and slice at 1

What happens if you increase coefficient on y?
and slice at 1
decrease width in y

can be written in matrix form like this…
What’s the shape? What are the eigenvectors? What are the eigenvalues?

can be written in matrix form like this…
Result of Singular Value Decomposition (SVD)
eigenvectors
eigenvalues along diagonal
Inverse sqr of length of the quadratic along the axis
axis of the ‘ellipse slice’

Eigenvectors Eigenvalues
Inverse sqr of the size of the axis
Eigenvector
Eigenvectors
Eigenvector

Recall:
you can smash this bowl in the y direction
you can smash this bowl in the x direction

Eigenvalues
Eigenvectors
Eigenvectors
Inverse sqr of length of axis
Eigenvector
Eigenvector

Eigenvectors
Eigenvectors
Eigenvalues

Gradient Visualization
M.Hebert, CMU

Design a program to detect corners (hint: use image gradients)

Finding corners
1.Compute image gradients over small region
2.Subtract mean from each image gradient
3.Compute the covariance matrix
4.Compute eigenvectors and eigenvalues
5.Use threshold on eigenvalues to detect corners

Compute image gradients over a small region (not just a single pixel)
array of x gradients
array of y gradients

Subtract the mean from each image gradient plot intensities
constant intensity gradient
intensities along the line
subtract mean
plot of image gradients
data is centered (‘DC’ offset is removed)

3. Compute the covariance matrix
=sum( .* ) array of x gradients array of y gradients

Plotting Derivatives as 2D Points
M.Hebert, CMU

distribution reveals edge orientation and magnitude

• •
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
“edge”:
no change along the edge direction
“corner”:
significant change in all directions
Credit: S. Seitz, D. Frolova, D.
Simakov

Harris corner detection: the math
Consider shifting the window p by (u,v)
• how do the pixels in p change?
• compare each pixel before and after by summing up the squared differences (SSD)
• this defines an SSD “error” E(u,v):
p

Error function
Change of intensity for the shift [u,v]:
Error Window function function
Window function w(x,y) =
Shifted intensity
Intensity
1 in window, 0 outside
Gaussian
or

Some mathematical background…
Change of intensity for the shift [u,v]:
Error Window Shifted function function intensity
Intensity
Error function
For nearly constant patches, this will be near 0. For very distinctive patches, this will be larger. We want patches where E(u,v) is LARGE for any small offsets u and v.

Taylor Series for 2D Functions
First partial derivatives Second partial derivatives
Third partial derivatives
(Higher order terms)
First order approx

Harris corner detection: the math
Using the small motion assumption, replace I
with a linear approximation (Shorthand: )
p
Rewrite as matrix equation

Bilinear approximation
For small shifts [u,v] we have a ‘bilinear approximation’:
Change in appearance for a shift [u,v]
where M is a 2×2 matrix computed from image derivatives:
‘second moment’ matrix ‘structure tensor’
M

Visualization of a quadratic
The surface E(u,v) is locally approximated by a quadratic form

Which error surface indicates a good image feature?
flat edge corner ‘line’ ‘dot’

Harris Corner Matrix
M=
A real(-number), symmetric matrix => has real eigenvalues
=> can be decomposed as R D RT => describes the shape of an ellipse!

Compute eigenvalues and eigenvectors eigenvalue
eigenvector
1. Compute the determinant of (returns a polynomial)
2. Find the roots of polynomial (returns eigenvalues)
3. For each eigenvalue, solve (returns eigenvectors)

eig(M)

Visualization as an ellipse
Since M is symmetric, we have
We can visualize M as an ellipse with axis lengths determined by
the eigenvalues and orientation determined by R direction of the
Ellipse equation:
fastest change
(lmax)-1/2
(lmin)-1/2
direction of the slowest change

interpreting eigenvalues
l2
l2 >> l1
What kind of image patch does each region represent?
l1 >> l2
l1

interpreting eigenvalues
l2
edge
l2 >> l1
l1 ~ l2
corner
flat
l1 >> l2 ‘vertical’
edge
‘horizontal’
l1

interpreting eigenvalues
l2
edge
l2 >> l1
l1 ~ l2
corner
‘horizontal’
flat
l1 >> l2 ‘vertical’
edge
l1

5. Use threshold on eigenvalues to detect corners

l2
5. Use threshold on eigenvalues to detect corners
flat
Think of a function to score ‘cornerness’
l1

l2
5. Use threshold on eigenvalues to detect corners
flat
strong corner
Think of a function to score ‘cornerness’
l1

5. Use threshold on eigenvalues to detect corners
l2
R<0 R>0
^

corner
flat
R<0 l1 l2 5. Use threshold on eigenvalues to detect corners ^ corner Use the smallest eigenvalue as the response function flat l1 Harris & Stephens (1988) Kanade & Tomasi (1994) Nobel (1998) Interpreting the eigenvalues Classification of image points using eigenvalues of M: l2 “Edge” l2 >> l1
“Corner”
l1 and l2 are large, l1 ~ l2;
E increases in all directions
“Edge”
l1 >> l2
“Flat” region
l1 and l2 are small;
E is almost constant in all directions
l1

Related Posts