CS代考 CMT107 Visual Computing

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