[06-30213][06-30241][06-25024]
Computer Vision and Imaging &
Robot Vision
Dr Hyung Jin Chang Dr Yixing Gao
h.j.chang@bham.ac.uk y.gao.8@bham.ac.uk
School of Computer Science
LOCAL FEATURES
(SZELISKI 4.1)
Today
Mosaics recap:
How to warp one image to the other, given H?
How to detect which features to match?
3
Local features: main components
1) Detection: Identify the interest points
2) Description:Extractvectorx =[x(1),!,x(1)]
feature descriptor surrounding each interest point.
3) Matching: Determine correspondence between descriptors in two views
11d
x =[x(2),!,x(2)] 21d
Kristen Grauman
4
Local features: desired properties
• Repeatability
– The same feature can be found in several images despite geometric and photometric transformations
• Saliency
– Each feature has a distinctive description
• Compactness and efficiency
– Many fewer features than image pixels
• Locality
– A feature occupies a relatively small area of the image; robust to clutter and occlusion
5
Applications
• Localfeatureshavebeenusedfor:
– Image alignment
– 3D reconstruction
– Motion tracking
– Robot navigation
– Indexing and database retrieval
– Object recognition
Lana Lazebnik
6
Goal: interest operator repeatability
• We want to detect (at least some of) the same points in both images.
By random sampling in each image, we will not likely detect the same points.
• Yet we have to be able to run the detection procedure independently per image.
A detector with a high detection repeatability is required!
7
Goal: descriptor distinctiveness
• We want to be able to reliably determine which point goes with which.
?
• Must provide some invariance to geometric and photometric differences between the two views.
8
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
9
• Whatpointswouldyouchoose(forrepeatability,
distinctiveness)?
10
A number of
• Hessian & Harris
• Laplacian, DoG
keypoint
detectors exist
[Beaudet ‘78], [Harris ‘88] [Lindeberg ‘98], [Lowe 1999] [Mikolajczyk & Schmid ‘01] [Mikolajczyk & Schmid ‘04] [Matas ‘02]
• Harris-/Hessian-Laplace
• Harris-/Hessian-Affine
• MSER
• FAST
• Lots of others…
• A very good tutorial ECCV 2012:
Modern features: advances, applications, and software
• These detectors have become building blocks of numerous computer vision applications!
Corners as
• Importantinsight:
• Theregionaroundacornercontainsstronggradientsin
multiple directions!
• Cornersarerepetitiveanddistinctive
C.Harris and M.Stephens. “A Combined Corner and Edge Detector.“ Proceedings of the 4th Alvey Vision Conference, 1988.
keypoints
Slide credit: Svetlana Lazebnik
Corners as distinctive interest points We should easily recognize the point by looking
through a small window
Shifting a window in any direction should give a large change in intensity
!2-,.% 0″$/(‘& ‘()*+,’$”)/’),–) #/0″*./(‘1
!”#$”%& ‘()*+,’$”),-(‘$) .+”)”#$”)#/0″*./(‘
!*(0′”0%& 1/$’/2/*,’.)*+,’$”) /’),–)#/0″*./(‘1
Slide credit: Alyosha Efros, Darya Frolova, Denis Simakov
13
Harris corner detector
• Theintensitychangeforashift[u,v]: (weighted autocorrelation function)
Weight function
Intensity after the shift
Intensity before the shift
Weight function w(x,y) =
Gaussian kernel
Slide credit: Rick Szeliski
Harris corner detector
• For small shifts E can be linearly approximated by:
with M 2×2 matrix of image derivatives: A weighted sum over the region in
Gradient w.r.t x, which we are verifying a corner. times gradient w.r.t y
Write the summation as a convolution by a Gaussian.
Harris corner detector
Image I
• Matrix M is the covariance matrix of region gradients:
• A corner is detected by analyzing the gradient covariance matrix
Ix Iy IxIy
Slide credit: K. Kitani
Slide credit: K. Kitani
Slide credit: K. Kitani
Slide credit: K. Kitani
Slide credit: K. Kitani
Slide credit: K. Kitani
The Covariance matrix analysis
• Visualizethecovariancematrixasanellipse… Direction of a slow change
(small gradient)
M
(lmin)1/2
• Decomposeintoeigenvectorsandeigenvalues:
(lmax)1/2
Direction of
a fast change (large gradient)
eigen values (ellipse SCALING)
eigen vectors (ellipse ROTATION)
The Covariance matrix analysis
• Visualizethecovariancematrixasanellipse… Direction of a slow change
(smal gradient)
M
• Decomposeintoeigenvectorsandeigenvalues:
• Thecornerhasastronggradientinbothmajordirections! • Soacornerispresentwhenbotheigenvaluesarelarge.
Direction of
a fast change (large gradient)
Eigen values: Interpretation
• CornerdetectionbyeigenvaluesofM: l2
l1 and l2 small;
E almost constant in all directions.
“edge”
l2 >> l1
l1 and l2 are large, l1 ~ l2;
E increases/decreases in all directions approximately equally.
“corner ”
“homogenous” region
“edge”
l1 >> l2
l1
Slide credit: Kristen Grauman
Eigen values: Interpretation
• Problem: Calculating the eigenvalues at each pixel is out of the question due to computational complexity!
• Solution: The ratio between the two eigenvalues and a rough estimate of their magnitude.
A standard result:
This is the corner response function!
The corner response function
• In practice we check if CRF exceeds a threshold
• We can calculate the Determinant and Trace directly:
In practice, α: (0.04 to 0.06)
Harris corner detector: Summary
• Calculatethecovariancematrix (by virtue of autocorrelation)
êxD xyDú M(s ,s )=g(s )*é I2(s ) I I (s )ù
Ix Iy2
Iy IxIy
g(I I ) x y
ID I II(s)I2(s)1.Image
êxyDyDú ëû
derivatives
Ix2
g(I 2) x
2. Squared derivatives
3. Gaussian filtered squared derivatives g(sI)
4. Corner presence– two strong eigen values
R=det[M(s ,s )]-a[trace2(M(s ,s ))] ID ID
g(I 2) y
= g(I2)g(I2)-[g(I I )]2 -a[g(I2)+g(I2)]2 xyxyxy
5. Apply a non-maxima suppression
R
Slide credit: Krystian Mikolajczyk
Harris corner detector: Summary
Slide credit: Darya Frolova, Denis Simakov
Harris corner detector: Summary
• The Corner response function:
Slide credit: Darya Frolova, Denis Simakov
Harris corner detector: Summary
• Find the strong responses: R > threshold
Slide credit: Darya Frolova, Denis Simakov
Harris corner detector: Summary
• Find the local maxima in R
Slide credit: Darya Frolova, Denis Simakov
Harris corner detector: Summary
• Detected Harris corners
Slide credit: Darya Frolova, Denis Simakov
Harris detector
Result: a very accurate corner detector.
Slide credit: Krystian Mikolajczyk
Harris detector: properties
• Isitrotationinvariant?
Ellipse rotates, but its shape (e.g., eigenvalues) remains unchanged!
The corner response function is rotation invariant!
Slide credit: Kristen Grauman
Harris detector: properties
• Rotationinvariance
• Isitinvarianttoscalechange?
scale the curve
corner all points suddenly classified as potential
corners! NOT invariant to scale change!
Slide credit: Kristen Grauman
The Hessian corner detector
• DeterminantofaHessian
Ixx
Note: these are second order derivatives!
(Recall what Hessian means àa measure of local curvature)
Intuition: Find strong gradients in two orthogonal directions
Ixy Iyy
Slide credit: Krystian Mikolajczyk
The Hessian corner detector
• DeterminantofaHessian
Ixx
Ixy Iyy
In Matlab:
Ixx.*Iyy -(Ixy).^2
Slide credit: Krystian Mikolajczyk
The Hessian corner detector
Result: responses on corners and strongly textured regions.
Slide credit: Krystian Mikolajczyk
Thank you
Hyung Jin Chang
28/02/2021