Outline
• Pattern recognition in computer vision
• Background on the development of SIFT
• SIFT algorithm and some of its variations
• Computational considerations (SURF)
• Potential improvement
• Summary
7/2/201011/6/
01
021
2
Pattern Recognition
• Pattern recognition is a classical problem in computer vision. It
consists of two crucial steps: feature extraction and pattern matching.
Our focus today is on feature extraction.
• Features are effective and efficient representations of a pattern that
are discriminative and invariant
Discriminative: similar objects are close to each other in the feature space
Invariant: values remain stable under normal variation of conditions.
• Scale (focal length) change is frequent and normal to any camera-
based application. A person has no problem in identifying object with
different focal length. A useful camera app needs to be scale-invariant.
• Ideally, features should also be photometric (illumination) invariant
and geometrical (rotational, affine, or perspective).
7/2/201011/6/
01
031
3
Example on Discriminative Features
7/2/201011/6/
01
041
4
Methods on Feature Extraction
• Features could be global or local. Global means features are derived
based on the entire image. Eigen-face (or Fisher-face) is a good
example of global feature.
• It has tractable mathematics with straightforward algorithm (although
could be MIPS intensive). It is, however, subject to variations due to
multiple factors: geometrical, photometrical, and partial occlusion to
name a few. It only works well under well controlled conditions.
• Local features are features intrinsic to an object and can be
computed using patches of images. The minutia (breaks and
branching points), for example, are effective local features for
fingerprint recognition.
• Local features could be difficult to compute; but has several
advantages.
7/2/201011/6/
01
051
5
Fingerprint Recognition
7/2/201011/6/
01
061
6
Additional Advantages of Local Features
• Locality: features are local, so robust to occlusion and
clutter.
• Distinctiveness: individual features can be matched to a
large database of objects.
• Quantity: many features can be generated for even a small
object.
• Efficiency: close to real-time performance.
• Corners together with a description of its neighboring
structure appear to be a excellent candidate as local feature
for general object recognition.
• Corner provide a stable focal point whereas its neighboring
structures provide some uniqueness of an object.
7
Harris Corner Detector
• SIFT is primarily originated from the Harris corner detector.
• Harris corner detector is correlation based:
7/2/201011/6/
01
081
8
Computing Harris Corner
'x'y) is computed as
• Auto-SSD for a point (x,y) and a shift ('
where C(x,y) is an effective representation for corner determination.
7/2/201011/6/
01
091
9
Corner Determination
Computer eigen values are difficult. A quick measure on corner strength is:
7/2/201011/6/
01
01
10
10
Harris Corner: Rotational Invariant
7/2/201011/6/
01
01
11
11
Harris Corner: Not Scale Invariant
7/2/201011/6/
01
01
12
12
Harris Corner: The Problem
7/2/201011/6/
01
01
13
13
SIFT
• SIFT resolves the problem of Harris corner with two major
improvements.
• First, a scale space representation is built to facilitate the
search for features (corners) at a distinctive scale
• Second, difference of Gaussian (DoG) was used to replace
the computation of C(x,y)
It is computationally efficient for building scale space
representations
It approximates Laplacian of Gaussian (LoG) and its extremes also
provide stable anchor points (such as Harris corners) for feature
extraction.
• This results from the heat equation We will come
back to this point later on.
14
Overview of SIFT
7/2/201011/6/
01
01
15
15
Construct Scale Space
• All scales must be examined to identify scale-invariant
features. An efficient way is to construct the Difference of
Gaussian (DoG) pyramid:
R
es
amp
le
Resam
ple
Blur
Subtract
B
lu
r
S
ub
tr
act
16
Take Difference of Gaussian
17
Locate DoG Extrema
• Detect maxima and
minima of difference-of-
Gaussian in scale space
• These extrema are Resam
ple
Blur
Subtract
potential candidates for
features and referred to as
key-points or interest-
points.
18
Sub-Pixel Localization
• The problem • The solution
-Take Taylor series
expansion
& wDT & 1 & T w 2 DT &
Dx D & x x &2 x
wx 2 wx
1
w 2 D wD
x &2 &
wx wx
- Differentiate and set to 0
-to get location in terms of
(x,y,σ)
19
Keypoint Filtering - Low Contrast
• Low Contrast Points Filter
Dx smaller than 0.03 will be discarded because it is likely to
be generated by noise.
20
Eliminating Edge Responses
• Edge also has high response along one direction; but is not a
useful feature.
• Use eigen values of Hessian matrix to eliminate edges:
Eigenvalues are proportional to principle curvatures
The ratio between trace and determinant could identify stable features
21
Orientation Assignment
• Use scale of point to choose correct image:
L x, y G x, y, V * I x, y
• Compute gradient magnitude and orientation using finite
differences:
2 2
m x, y L x 1, y L x 1, y L x, y 1 L( x, y 1)
§ L x, y 1 L( x, y 1) ·
T x, y tan 1 ¨¨ ¸¸
© L x 1, y L x 1, y ¹
• Use directional histogram
22
Compute Final SIFT Vector
• Actual implementation uses 4x4 descriptors from 16x16 which
leads to a 4x4x8=128 element vector
23
Example of Key-point Detection
Threshold on value at DOG peak and on ratio of principle curvatures
(Harris approach)
(a) 233x189 image
(b) 832 DOG extrema
(c) 729 left after peak
value threshold
(d) 536 left after testing
ratio of principle
curvatures
24
Repeatability against Noise
25
Repeatability against View Angles
7/2/201011/6/
01
01
26
26
Variations of SIFT
• SIFT uses DoG in both spatial and scale space operations.
DoG is an approximation of LoG. Threshold and edge
elimination are part of the computations.
• Alternatively, other derivative based functions or operators
can also be used to compute scale space representation:
SIFT
Square gradient:
Laplacian:
Harris function:
7/2/201011/6/
01
01
27
27
Two Alternatives on Finding Key-points
m Laplacian o
scale
Harris-Laplacian1
Find local maximum of:
Laplacian in scale
y
Harris corner detector
in space (image m Harris o x
coordinates)
m DoG o
• SIFT2 scale
Find local maximum of:
Difference of y
Gaussians in space
and scale m DoG o x
1
2 -
28
Performance Comparisons
7/2/201011/6/
01
01
29
29
Some Computational Considerations
• Discrete implementation of SIFT provides opportunity for the
development of fast algorithm.
• The Gaussian kernel for computing derivatives, for example,
need to be quantized and windowed.
• A coarse quantization with square windowing can help to
save MIPS by change convolution to additions.
• Speed Up Robust Features (SURF) made successful use of
the property for the computation of Hessian Matrix
needed for the detection of extrema.
7/2/201011/6/
01
01
30
30
Computational Profile on SIFT
• 8800GTX(800*600)
31
Approximating the Gaussian Kernel
• Approximated second order derivatives with box filters for the
computation of 2nd order derivatives (Fast-Hessian).
32
32
Comparisons of Different Algorithms
7/2/201011/6/
01
01
33
33
Potential Improvements on SIFT
• The vector representation is a heuristic scheme and could be
replaced by more rigorous vector-generation method. PCA, for
example, could be used to compute the canonical orientation.
• The algorithm is build on intensity image only. Color image
introduces further math sophistications.
• SIFT is affine invariant (covariant); it can tolerate only small,
insignificant perspective variations.
• SIFT makes use the solutions of linear equation of heat
diffusion. An evolution of non-linear diffusion could potentially
minimizes the need to search in scale space.
7/2/201011/6/
01
01
34
34
Summary
• We did a tutorial review on the development of SIFT in pattern
recognition.
• The focus is on SIFT; but we also briefly reviewed several
variations of SIFT.
• We also quickly covered one computation scheme - SURF.
• Potential work on improving SIFT is discussed.
• This tutorial mainly talks about feature extraction. Pattern
matching using SIFT is not covered.
7/2/201011/6/
01
01
35
35