CMT107 Visual Computing
Corner Detection
Copyright By PowCoder代写 加微信 powcoder
Xianfang Sun,
School of Computer Science and Informatics
Cardiff University
• Feature Extraction
• Characteristics of good features
• Applications
• Corner Detection
• Basic idea
• Mathematics
• Invariance and Covariance
Feature Extraction: Corners
9300 Pkwy, Charlotte, NC
• Motivation: panorama stitching
• We have two images – how do we combine them?
Why Extract Features
Step 1: extract features
Step 2: match features
Step 3: align images
• Repeatability
• The same feature can be found in several images despite geometric and photometric
transformations
• Saliency
• Each feature is distinctive
• 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
Characteristics of Good Features
• Feature points are used for
• Image alignment
• 3D reconstruction
• Motion tracking
• Robot navigation
• Indexing and database retrieval
• Object recognition
Applications
• Key properties: In the region around a corner, image gradient has two or
more dominant directions
• Corners are repeatable and distinctive
C.Harris and M.Stephens. “A Combined Corner and Edge Detector.“ Proceedings of the 4th
Conference, 1988: pages 147–151.
Finding Corners
http://www.csse.uwa.edu.au/~pk/research/matlabfns/Spatial/Docs/Harris/A_Combined_Corner_and_Edge_Detector.pdf
• We can easily recognise the point by looking through a small window
• Shifting a window in any direction should give a large change in intensity
Corner Detection: Basic Idea
no change along
the edge direction
significant change
in all directions
“flat” region:
no change in
all directions
• Change of intensity for the shift [𝑢, 𝑣]
Corner Detection: Mathematics
( , ) ( , ) ( , ) ( , )
E u v w x y I x u y v I x y= + + −
• Change of intensity for the shift 𝑢, 𝑣
• Window function 𝑤 𝑥, 𝑦 = or
Corner Detection: Mathematics
( , ) ( , ) ( , ) ( , )
E u v w x y I x u y v I x y= + + −
1 in window, 0 outside Gaussian
• Change of intensity for the shift 𝑢, 𝑣
• We want to find out how this function behaves for small shifts
Corner Detection: Mathematics
( , ) ( , ) ( , ) ( , )
E u v w x y I x u y v I x y= + + −
• Change of intensity for the shift 𝑢, 𝑣
• We want to find out how this function behaves for small shifts
• Using first-order Taylor approximation:
𝐼 𝑥 + 𝑢, 𝑦 + 𝑣 ≈ 𝐼 𝑥, 𝑦 + 𝑢𝐼𝑥 𝑥, 𝑦 + 𝑣𝐼𝑦(𝑥, 𝑦), Then:
𝑤(𝑥, 𝑦) 𝐼 𝑥, 𝑦 + 𝑢𝐼𝑥 𝑥, 𝑦 + 𝑣𝐼𝑦 𝑥, 𝑦 − 𝐼(𝑥, 𝑦)
𝑤(𝑥, 𝑦) 𝑢𝐼𝑥 𝑥, 𝑦 + 𝑣𝐼𝑦(𝑥, 𝑦)
Corner Detection: Mathematics
( , ) ( , ) ( , ) ( , )
E u v w x y I x u y v I x y= + + −
𝑤 𝑥, 𝑦 𝑢2𝐼𝑥
2 + 2𝑢𝑣𝐼𝑥𝐼𝑦
𝑤(𝑥, 𝑦) 𝑢 𝑣
Corner Detection: Mathematics
• The approximation simplifies to
• where M is a second moment matrix computed from image derivatives:
Corner Detection: Mathematics
MvuvuE ][),(
• The surface 𝐸 𝑢, 𝑣 is locally approximated by a quadratic form. Let’s try to
understand its shape.
Interpreting the Second Moment Matrix
MvuvuE ][),(
• Consider a horizontal slice of 𝐸 𝑢, 𝑣 : 𝑢 𝑣 𝑀
• This is an equation of an ellipse
Interpreting the Second Moment Matrix
• Consider a horizontal slice of 𝐸 𝑢, 𝑣 : 𝑢 𝑣 𝑀
• This is an equation of an ellipse
• Diagonalization of 𝑀: 𝑀 = 𝑅−1
• The axis lengths are determined by the eigenvalues: 𝜆1and 𝜆2, and the
orientation is determined by 𝑅
• If either 𝜆 is close to 0,
then this is not a corner,
so look for positions where both are large.
Interpreting the Second Moment Matrix
direction of the
slowest change
direction of the
fastest change
Visualization of Second Moment Matrices
Visualization of Second Moment Matrices
• Classification of image points using eigenvalues of 𝑀.
Interpreting the Eigen Values
1 and 2 are large,
E increases in all
directions
1 and 2 are small;
E is almost constant
in all directions
• 𝑅 = 𝜆1𝜆2 − 𝛼 𝜆1 + 𝜆2
2 = det 𝑀 − 𝛼 trace 𝑀 2
𝛼: constant (0.04 to 0.15)
Corner Response function
• Compute Gaussian derivatives at each pixel
• Compute second moment matrix 𝑀 in a Gaussian window around each pixel
• Computer corner response function 𝑅
• Threshold 𝑅
• Find local maxima of response function (nonmaximum suppression)
C.Harris and M.Stephens. “A Combined Corner and Edge Detector.”
Proceedings of the 4th Conference: pages 147—151, 1988.
http://www.bmva.org/bmvc/1988/avc-88-023.pdf
• Compute corner response 𝑅
• Find points with larger corner response: 𝑅 > 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑
• Take the points of local maxima of 𝑅
• We want corner locations to be invariant to photometric transformations,
and covariant to geometric transformations.
• Invariance: image is transformed and corner locations do not change
• Covariance: if we have two transformed versions of the same image, features should
be detected in corresponding locations.
• 𝐼 → 𝑎𝐼 + 𝑏
• Only derivatives are used ⇒ invariance to intensity shift 𝐼 → 𝐼 + 𝑏
• Intensity scaling: 𝐼 → 𝑎𝐼
Affine Intensity Change
x (image coordinate)
x (image coordinate)
Partially invariant to affine intensity change
• Derivatives and window function are shift-invariant
Image Translation
Corner location is covariant w.r.t. translation
• Second moment ellipse rotates, but its shape (i.e., eigenvalues) remains the
Image Rotation
Corner location is covariant w.r.t. rotation
All points will be classified as edges
Corner location is not covariant to scaling!
• Why we need feature extraction? What are the applications of feature
extraction?
• What are the characteristics of good features?
• Describe the basic idea of corner detection
• How to decide whether a point is in a flat region, on an edge, or a corner
according to the two eigenvalues of the second moment matrix?
• Describe the steps of Harris detector
• What is Invariance and Covariance?
• Is affine intensity change invariant? Is image translation, rotation, scaling
covariant?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com