The University of

CS 4487/9587

Algorithms for Image Analysis Ontario

Elements of
Image (Pre)-Processing
and Feature Detection
Acknowledgements: slides from Steven Seitz, Aleosha
Efros, David Forsyth, and Gonzalez & Woods
 The University of

CS 4487/9587 Algorithms for Image Analysis

Image Processing Basics Ontario

Point Processing Extra Reading: Szeliski, Sec 3.1

gamma correction intensities, colors

window-center correction
histogram equalization
Filtering (linear and non-linear) Extra Reading: Szeliski, Sec 3.2-3.3

mean, Gaussian, and median filters contrast edges

texture
image gradients, Laplacian
templates, patches
normalized cross-correlation (NCC)
etc: Fourier, Gabor, wavelets (Szeliski, Sec 3.4-3.5)

Other features Extra Reading: Szeliski, Sec. 4.1

Harris corners, MOPS, SIFT, etc.
 The University of

Summary of image transformations Ontario

An image processing operation (or transformation) typically defines a

new image g in terms of an existing image f.

Examples:
 The University of

Summary of image transformations Ontario

An image processing operation (or transformation) typically defines a

new image g in terms of an existing image f.

Examples:

Geometric (domain) transformation:

g ( this
What kinds of operations can ) f (t x ( x, y), t y ( x, y))
x, yperform?
 The University of

Summary of image transformations Ontario

An image processing operation (or transformation) typically defines a

new image g in terms of an existing image f.

Examples:

Geometric (domain) transformation:

g ( this
What kinds of operations can ) f (t x ( x, y), t y ( x, y))
x, yperform?
Range transformation:
g ( xthis
What kinds of operations can ) t( f
, yperform? ( x, y))
 The University of

Summary of image transformations Ontario

An image processing operation (or transformation) typically defines a

new image g in terms of an existing image f.

Examples:

Geometric (domain) transformation:

g ( this
What kinds of operations can ) f (t x ( x, y), t y ( x, y))
x, yperform?
Range transformation: point processing
g ( xthis
What kinds of operations can ) t( f
, yperform? ( x, y))
neighborhood
Filtering also generates new images from an existing image processing

g ( x, y)
more on filtering later
h(u, v) f ( x u, y v) du dv
|u|
|v|
 The University of

Point Processing Ontario

g ( x, y) t ( f ( x, y))
for each original image intensity value I function t()
returns a transformed intensity value t(I).
NOTE: we will often use
I t (I ) notation Ip instead of f(x,y) to
denote intensity at pixel p=(x,y)

Important: every pixel is for itself

- spatial information is ignored!

What can point processing do?

(we will focus on grey scale images, see Szeliski 3.1 for examples of point processing for color images)
 The University of

Point Processing:

Examples of gray-scale transforms t Ontario

I t (I )

I
 The University of

Point Processing:

Negative Ontario

Ip or f ( x, y) I p or g ( x, y)

t ( I ) 255 I
g ( x, y) t ( f ( x, y)) 255 f ( x, y)
 The University of

Point Processing:

Power-law transformations t Ontario

 The University of

Point Processing:

Gamma Correction Ontario

Gamma Measuring Applet:

http://www.cs.berkeley.edu/~efros/java/gamma/gamma.html
 The University of

Point Processing:

Enhancing Image via Gamma Correction Ontario

 The University of

Point Processing:

Understanding Image Histograms Ontario

Image Brightness Image Contrast

ni ---number of pixels with intensity i

probability of intensity i : p(i )
n ---total number of pixels in the image
 The University of

Point Processing:

Contrast Stretching Ontario

 The University of

Point Processing:

Contrast Stretching Ontario

Original images Histogram corrected images

1)

2)
 The University of

Point Processing:

Contrast Stretching Ontario

Original images Histogram corrected images

3)

4)
 The University of

One way to automatically select transformation t :

Histogram Equalization Ontario

i i
t (i) p( j )
nj
= cumulative distribution
n
j 0 j 0 of image intensities

see Gonzalez and Woods, Sec3.3.1, for more details

 The University of

Point processing
Histogram Equalization Ontario

i i
t (i) p( j )
nj
= cumulative distribution
n
j 0 j 0 of image intensities

Why does that work?

Answer in probability theory:

I random variable with probability distribution p(i) over i in [0,1]

If t(i) is a cumulative distribution of I then

I=t(I) is a random variable with uniform distribution over its range [0,1]

That is, transform image I will have a uniformly-spread histogram (good contrast)
 The University of

Point Processing:

Window-Center adjustment Ontario

(monitors dynamic range)

256
Output gray level

0 60000
input gray level
(high dynamic range image)
 The University of

Point Processing:

Window-Center adjustment Ontario

(monitors dynamic range)

256
Output gray level

0 60000
input gray level
(high dynamic range image)
 The University of

Point Processing:

Window-Center adjustment Ontario

256

window
output gray level

0 center 60000

input gray level

 The University of

Point Processing:

Window-Center adjustment Ontario

Window = 4000
Center = 500
 The University of

Point Processing:

Window-Center adjustment Ontario

Window = 2000
Center = 500
 The University of

Point Processing:

Window-Center adjustment Ontario

Window = 800
Center = 500
 The University of

Point Processing:

Window-Center adjustment Ontario

Window = 0
Center = 500

If window=0 then we get

binary image thresholding
 The University of

Point Processing:

Window-Center adjustment Ontario

Window = 800 Window = 800

Center = 500 Center = 1160
 The University of

Neighborhood Processing (or filtering) Ontario

Q: What happens if I reshuffle all pixels within the image?

A: Its histogram wont change.

No point processing will be affected

Images contain a lot of spatial information

Readings: Szeliski, Sec 3.2-3.3

 The University of

Neighborhood Processing (filtering)

Linear image transforms Ontario

Lets start with 1D image (a signal): f[i]

A very general and useful class of transforms are

the linear transforms of f, defined by a matrix M
 The University of

Neighborhood Processing (filtering)

Linear image transforms Ontario

Lets start with 1D image (a signal): f[i]

matrix M
 The University of

Neighborhood Processing (filtering)

Linear image transforms Ontario

Lets start with 1D image (a signal): f[i]

matrix M
 The University of

Neighborhood Processing (filtering)

Linear shift-invariant filters Ontario

matrix M

It is known as a linear shift-invariant filter and is

represented by a kernel (or mask) h:

h [i] [a b c]
and can be written (for kernel of size 2k+1) as:
k
This pattern is very common
- same entries in each row
g [i] h [u] f [i u]
u k
- all non-zero entries near the diagonal
The above allows negative filter indices. When
gM f you implement need to use: h[u+k] instead of h[u]
 The University of

Neighborhood Processing (filtering)

2D linear transforms Ontario

We can do the same thing for 2D images by

concatenating all of the rows into one long vector
(in a raster-scan order):

f [i] f [ i / m, i%m ]
 The University of

Neighborhood Processing (filtering)

2D filtering Ontario

A 2D image f[i,j] can be filtered by a 2D kernel h[u,v] to

produce an output image g[i,j]:
k k
g [i, j ]
u k v k
h [u, v] f [i u, j v]

This is called a cross-correlation operation and written:

g h f

h is called the filter, kernel, or mask.

 The University of

Neighborhood Processing (filtering)

2D filtering Ontario

A convolution operation is a cross-correlation where the filter is

flipped both horizontally and vertically before being applied to
the image:
k k
g [i, j ]
u k v k
h [u, v] f [i u, j v]
k k
It is written: g h f h[u,v] f [i u, j v]
u k v k

How does convolution differ from cross-correlation?

If h[u, v] h[u,v] then there is no difference between convolution and cross-correlation

convolution has additional technical properties: commutativity, associativity. Also, nice properties wrt Fourier analysis.
(see Szeliski Sec 3.2, Gonzalez and Woods Sec. 4.6.4)
 The University of

2D filtering
Noise Ontario

Filtering is useful for

noise reduction...
(side effects: blurring)

Common types of noise:

Salt and pepper noise:
random occurrences of
black and white pixels
Impulse noise: random
occurrences of white pixels
Gaussian noise: variations in
intensity drawn from a
Gaussian normal distribution
 The University of

Practical noise reduction Ontario

How can we smooth away noise in a single image?

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 100 130 110 120 110 0 0
0 0 0 110 90 100 90 100 0 0
0 0 0 130 100 90 130 110 0 0
0 0 0 120 100 130 110 120 0 0
0 0 0 90 110 80 120 100 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
 The University of

Neighborhood Processing (filtering)

Mean filtering Ontario

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 0 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 0 0 0 0 0 0 0
0 0 90 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
 The University of

Neighborhood Processing (filtering)

Mean filtering Ontario

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 10 20 30 30 30 20 10
0 0 0 90 90 90 90 90 0 0 0 20 40 60 60 60 40 20
0 0 0 90 90 90 90 90 0 0 0 30 60 90 90 90 60 30
0 0 0 90 90 90 90 90 0 0 0 30 50 80 80 90 60 30
0 0 0 90 0 90 90 90 0 0 0 30 50 80 80 90 60 30
0 0 0 90 90 90 90 90 0 0 0 20 30 50 50 60 40 20
0 0 0 0 0 0 0 0 0 0 10 20 30 30 30 30 20 10
0 0 90 0 0 0 0 0 0 0 10 10 10 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
 The University of

Effect of
mean filters Ontario
 The University of

Neighborhood Processing (filtering)

Mean kernel Ontario

Whats the kernel for a 3x3 mean filter?

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0
0 0 0 90 0 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0 H [u, v]
0 0 0 0 0 0 0 0 0 0
0 0 90 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
F[ x, y]
 The University of

Neighborhood Processing (filtering)

Gaussian Filtering Ontario

A Gaussian kernel gives less weight to pixels

0 0 0 0 0 0 0 0 0 0 further from the center
0 0 0 0 0 0 0 0 0 0 of the window
0 0 0 90 90 90 90 90 0 0
0 0 0 90 90 90 90 90 0 0 1 2 1
1
0 0 0 90 90 90 90 90 0 0 2 4 2
16
0 0 0 90 0 90 90 90 0 0 1 2 1
0 0 0 90 90 90 90 90 0 0 H [u, v]
0 0 0 0 0 0 0 0 0 0
0 0 90 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
This kernel is an approximation
F[ x, y] of a Gaussian function:
 The University of

Neighborhood Processing (filtering)

Mean vs. Gaussian filtering Ontario

 The University of

Neighborhood Processing (filtering)

Median filters Ontario

A Median Filter operates over a window by

selecting the median intensity in the window.

What advantage does a median filter have over

a mean filter?

Is a median filter a kind of convolution?

- No, median filter is an example of non-linear filtering
Comparison: The University of

salt and pepper

noise Ontario
Comparison: The University of

Gaussian
noise Ontario
 The University of

Reading: Forsyth & Ponce, 8.1-8.2

Differentiation and convolution Ontario

Recall We could approximate this as

f ( x , y ) f ( x, y ) f ( xi 1 , y) f ( xi 1 , y)

f lim

x f
x
0
2 x
x f (convolution)
Now this is linear and shift
invariant, so must be the
0 0 0
result of a convolution. 1
with kernel 1 0 -1
2x
0 0 0
x [u, v]
sometimes this may not be a very good way
to do things, as we shall see
 The University of

Reading: Forsyth & Ponce, 8.1-8.2

Differentiation and convolution Ontario

Recall We could approximate this as

f ( x , y ) f ( x, y ) f ( xi 1 , y) f ( xi 1 , y)

f lim

x f
x
0
2 x
x f (convolution)
Now this is linear and shift
invariant, so must be the
0 0 0
result of a convolution. 1
with kernel 1 0 -1
2x
0 0 0
x [u, v]
sometimes this may not be a very good way
to do things, as we shall see
 The University of

Finite differences Ontario

x f
 The University of

Finite differences responding to noise Ontario

x f x f x f

Increasing noise ->

(this is zero mean additive gaussian noise)
 The University of

Finite differences and noise Ontario

Finite difference filters What is to be done?

respond strongly to noise intuitively, most pixels in
images look quite a lot like
obvious reason: image their neighbours
noise results in pixels that this is true even at an edge;
look very different from along the edge theyre similar,
their neighbours across the edge theyre not
suggests that smoothing the
Generally, the larger the image should help, by forcing
noise the stronger the pixels different to their
neighbours (=noise pixels?) to
response look more like neighbours
 The University of

Smoothing and Differentiation Ontario

Issue: noise
smooth before differentiation
two convolutions: smooth, and then differentiate?
actually, no - we can use a derivative of Gaussian filter
because differentiation is convolution, and
convolution is associative x ( H f ) ( x H ) f

x H y H
 The University of

( x H ) f
Ontario

1 pixel 3 pixels 7 pixels

The scale of the smoothing filter affects derivative estimates, and also
the semantics of the edges recovered.
 The University of

Sobel derivative kernels Ontario

x f y f

1 0 -1 1 2 1
1 1
2 0 -2 0 0 0
8x 8y
1 0 -1 -1 -2 -1
x [u, v] y [u, v]
 The University of

Image Gradients Ontario

Recall for a function of two x

(or more) variables f ( x, y)
f
x
Gradient f
x
x f y
at point (x,y) f f f
f
y
y y
a two (or more)
dimensional vector

f f
The absolute value | f | ( x ) 2 ( y ) 2 ( x f ) 2 ( y f ) 2 small image
gradients in low
is large at image boundaries textured areas

The direction of the gradient corresponds to the direction of the steepest ascend
- normally gradient is orthogonal to object boundaries in the image.
Comment: vector f is independent of
The University of

specific coordinate system Ontario

Equivalently, gradient of function f ( p)

at point p R can be defined as a
2

vector f s.t. for any unit vector n

p
Gradient f
f ( p n ) f ( p)
at point p (f n )

n f
n
directional derivative of
dot product
function f along direction n

pure vector algebra, specific coordinate system is irrelevant

works for functions of two, three, or any larger number of variables
f f
previous slide gives a specific way for computing coordinates ( x , y )
of vector f w.r.t. given orthogonal basis (axis X and Y).
 The University of

Image Gradient Ontario

Typical application where image gradients are used

is image edge detection
find points with large image gradients
edge features

Canny edge detector suppresses

non-extrema Gradient points
 The University of

Second Image Derivatives

(Laplace operator f ) Ontario

f f 2 2


f 2 2 [ x y ] f f
x

x y y divergence
of gradient
rotationally invariant
second derivative for 2D functions

0 0 0 0 1 0 0 1 0
1 -2 1 0 -2 0 1 -4 1
0 0 0 0 1 0 0 1 0

rate of change for 0 0 0 0 0 0 0 1 0 0 0 0 rate of change for

the rate of change 0 1 1 - 1 1 0 0 1 0
0 0 0
- 0 1 0
0 1 0
the rate of change
in x-direction 0 0 0 0 0 0 in y-direction
2 f
x 2 xf ( 21 ) xf ( 21 ) 2 f
y 2 yf ( 21 ) yf ( 21 )
 The University of

Laplacian of a Gaussian (LoG) Ontario

G image should
be smoothed a bit first
LoG
x2 y2
1 x y 2 2
LoG( x, y ) 4
1 e
2 2
2
2

MATLAB: logfilt = fspecial(log,25,4);

http://homepages.inf.ed.ac.uk/rbf/HIPR2/log.htm
 The University of

Second Image Derivatives

(Laplace operator f ) Ontario

f f2 2
For simplicity, assume f(x,y) = const(y).
f 2 2 Then, Laplacian of f is simply
x y a second derivative of f(x) = f(x,y)

Application: Laplacian Zero Crossings are used for edge detection

(alternative to methods computing Gradient extrema)
image intensity
along some scan line

magnitude of image gradient

along the same scan line

Laplacian (2nd derivative)

of the image along
http://homepages.inf.ed.ac.uk/rbf/HIPR2/zeros.htm the same scan line
 The University of

Laplacian of a Gaussian (LoG) Ontario

LoG

G image should
be smoothed a bit first

http://homepages.inf.ed.ac.uk/rbf/HIPR2/log.htm
 The University of

Unsharp masking Ontario

What does blurring take away? U I G*I

- =
unsharp mask

+a = ?
unsharp mask
 The University of

Unsharp masking Ontario

(1 a ) I a G * I [(1 a )G 1 a G 2 ] * I
1 2

U I G*I I a mask
unsharp U

+a = ?
unsharp mask
 The University of

Unsharp masking Ontario

unsharp mask kernel can

MATLAB be seen as a difference of
two Gaussians (DoG)
with 1 2 .
Imrgb = imread(file.jpg);
im = im2double(rgb2gray(imrgb));
unsharp mask
g= fspecial('gaussian', 25,4); kernel
imblur = conv2(im,g,same');
imagesc([im imblur])
imagesc([im im+.4*(im-imblur)])

http://homepages.inf.ed.ac.uk/rbf/HIPR2/unsharp.htm DoG G 1 G 2 LoG

 The University of

Reading: Forsyth & Ponce ch.7.5

Filters and Templates Ontario

Applying a filter at
some point can be seen
as taking a dot-product Insight
between the image and filters may look like the effects they
some vector are intended to find
filters find effects they look like
Filtering the image is a
set of dot products
x H y H
 The University of

Normalized Cross-Correlation (NCC) Ontario

filtering as a dot product

now measure the angle:
NCC output is filter output
divided by root of the sum of
squares of values over which cross-correlation of h and f at t=(x,y)
filter lies k k

h [u, v] f [ x u, y v]
u k v k
| h | | ft |
template (filter, kernel, mask)
h of size n = (2k+1) x (2k+1)
division makes this
a non-linear operation
t=(x,y)
ft
image
h ft
ft patch
g[t ] cos(a )
at t
a h | h | | ft |
f n
image
raster-scan h and ft as vectors in Rn
vector lengths | z | z
i 1
2
i
 The University of

Normalized Cross-Correlation (NCC) Ontario

filtering as a dot product Tricks:

now measure the angle: subtract template average h
NCC output is filter output (to give zero output for constant
divided by root of the sum of regions, reduces response to
squares of values over which irrelevant background)
filter lies subtract patch average f t when
computing the normalizing
constant (i.e. subtract the image
h
template (filter, kernel, mask) mean in the neighborhood)
of size n = (2k+1) x (2k+1)

t=(x,y) ft ft
image a hh (h h ) ( f t f t )
NCC
ft patch
g[t ]
| h h | | ft ft |
at t

f these vectors do not have to be

image
in the positive quadrant
 The University of

Normalized Cross-Correlation (NCC) Ontario

filtering as a dot product Tricks:

now measure the angle: subtract template average h
NCC output is filter output (to give zero output for constant
divided by root of the sum of regions, reduces response to
squares of values over which irrelevant background)
filter lies subtract patch average f t when
computing the normalizing
constant (i.e. subtract the image
h
template (filter, kernel, mask) mean in the neighborhood)
of size n = (2k+1) x (2k+1)

t=(x,y) ft ft equivalently using statistical term (standard diviation)

image a hh (h h ) ( f t f t )
NCC
ft patch
g[t ]
n h ft
at t

f these vectors do not have to be

image n
in the positive quadrant Remember: st.div. Z 1
n (z
i 1
i z )2 1
n | z z |
 The University of

Normalized Cross-Correlation (NCC) Ontario

filtering as a dot product Tricks:

now measure the angle: subtract template average h
NCC output is filter output (to give zero output for constant
divided by root of the sum of regions, reduces response to
squares of values over which irrelevant background)
filter lies subtract patch average f t when
computing the normalizing
constant (i.e. subtract the image
h
template (filter, kernel, mask) mean in the neighborhood)
of size n = (2k+1) x (2k+1)

t=(x,y) standard in statistics equivalently using statistical term cov (covariance)

correlation coefficient NCC
image
cov(h, f t )
ft patch
g[t ]
h ft
at t

between h and ft
f
image n
(a a ) (b b )
cov(a, b) E (a a )(b b ) 1
n (a a )(b b )
i 1
i i
n
 pictures from Silvio Savarese The University of

Normalized Cross-Correlation (NCC) Ontario

NCC for h and f

hA hB hC hD
A
image f

C
C

templates
points mark local maxima of NCC
for each template
D
points of interest or feature points
 The University of

Other features (Szeliski sec 4.1.1) Ontario

Feature points are used for:

Image alignment (homography, fundamental matrix)
3D reconstruction
Motion tracking
Object recognition
Indexing and database retrieval
Robot navigation
other
 The University of

Harris corner detector Ontario

C.Harris, M.Stephens. A Combined Corner

and Edge Detector. 1988
 The University of

The Basic Idea

Ontario

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
 The University of

Harris Detector: Basic Idea

Ontario

flat region: edge: corner:

no change in all no change along the edge significant change in all
directions direction directions
 The University of

Harris Detector: Mathematics Ontario

For any given image patch or window w

we should measure how it changes
u
when shifted by ds v
x
w(x,y)=1

Notation: let patch be defined

by its support function w(x,y) w(x,y)=0
over image pixels
y
 The University of

Harris Detector: Mathematics Ontario

u weighted sum of
patch w change measure for shift ds : squared differences
v

w( x, y) [ I ( x u, y v) I ( x, y)]
2
Ew (u, v) :
x, y

Window Shifted Intensity

function intensity

or
NOTE:
window support
functions w(x,y) = Gaussian
1 in window, 0 outside (weighted) support
 The University of

Harris Detector: Mathematics Ontario

assuming image gradient I

u Ix
Change of intensity for the shift ds
v I y

I ( x u, y v) I ( x, y) I x u I y v dsT I
rate of change for I at (x,y) in direction (u,v) = ds (remember gradient definition on earlier slides!!!!)
this is 2D analogue of 1st order Taylor expansion

[ I ( x u, y v) I ( x, y) ]2 dsT I I T ds

w( x, y) [ I ( x u, y v) I ( x, y)]
2
Ew (u, v)
x, y

ds w( x, y ) I I ds ds M w ds
T T
T

x, y M w
 The University of

Harris Detector: Mathematics Ontario

assuming image gradient I

u Ix
Change of intensity for the shift ds
v I y

u
Ew (u, v) [ u v ] M w dsT M w ds
v

where Mw is a 22 matrix computed from image derivatives inside patch w

matrix M is also called I x2 IxI y

Harris matrix or structure tensor I y I x I y2 This tells you how
to compute Mw

at any window w

... w( x, y ) I I ...
(t.e. any image patch)
T

x, y M w
 The University of

Harris Detector: Mathematics Ontario

assuming image gradient I

u Ix
Change of intensity for the shift ds
v I y

u paraboloid

Ew (u, v) [ u v ] M w dsT M w ds
v
M is a positive semi-definite matrix (Exercise: show that ds M ds 0 for any ds)
T

M can be analyzed via its isolines, e.g. dsT M w ds 1 (ellipsoid)

v

u
Points on this ellipsoid are shifts ds=(u,v)
2 2 giving the same value of energy E(u,v)=1.
2 1 Thus, the ellipsoid allows to visually compare
sensitivity of energy E to shifts ds in different directions
two eigen values of matrix Mw
 The University of

Harris Detector: Mathematics Ontario

Classification of image points 2 Edge

using eigenvalues of M: 2 >> 1
Corner
1 and 2 are large,
1 ~ 2;
E rapidly increases in all
directions

1 and 2 are small;

E is almost constant Flat Edge
in all directions region 1 >> 2

1
 The University of

Harris Detector: Mathematics Ontario

Measure of corner response:

det M
R
Trace M
det M 12
trace M 1 2

R should be large
(it implies that both are far from zero)
 The University of

Harris Detector Ontario

The Algorithm:

Find points with large corner response function R

R > threshold

Take the points of local maxima of R

 The University of

Harris Detector: Workflow

Ontario
 The University of

Harris Detector: Workflow

Compute corner response R Ontario
 The University of

Harris Detector: Workflow

Find points with large corner response: R>threshold Ontario
 The University of

Harris Detector: Workflow

Take only the points of local maxima of R Ontario
 The University of

Harris Detector: Workflow

Ontario
 The University of

Harris Detector: Some Properties Ontario

Rotation invariance

Ellipse rotates but its shape (i.e. eigenvalues) remains the same

Corner response R is invariant to image rotation

 The University of

Harris Detector: Some Properties Ontario

Partial invariance to affine intensity change

Only derivatives are used => invariance to intensity shift I I + b

Intensity scale: I a I

R R

threshold

x (image coordinate) x (image coordinate)

features locations stay the same,
but some may appear or disappear depending on gain a
 The University of

Harris Detector: Some Properties Ontario

But: non-invariant to image scale!

All points will be Corner !

classified as edges
 The University of

Scale Invariant Detection Ontario

Consider regions (e.g. circles) of different sizes around a point

Regions of corresponding sizes will look the same in both images
 The University of

Scale Invariant Detection Ontario

The problem: how do we choose corresponding circles independently

in each image?

Choose the scale of the best corner

 The University of

Other feature detectors Ontario

LoG and DoG operators are also used to detect features

they find reliable blob features (at appropriate scale)

these operators also respond to edges. To improve

selectivity, post-processing is necessary.
- e.g. eigen-values of the Harris matrix cold be used as in the corner operator.
If the ratio of the eigen-values is too high, then the local image is regarded
as too edge-like and the feature is rejected.
 The University of

Other features Ontario

MOPS, Hog, SIFT,

Features are characterized by location and descriptor

color any pixel RGB vector

edge Laplacian zero crossing image gradient

corner local max of R magnitude of R

more below
MOPS corners normalized intensity patch

HOG LOG extrema points gradient orientation

SIFT or other interest points histograms
highly
discriminative
(see Szeliski, Sec. 4.1.2)
 The University of

Feature descriptors Ontario

We know how to detect points

Next question: How to match them?

?
Point descriptor should be:
1. Invariant 2. Distinctive
 The University of

Descriptors Invariant to Rotation Ontario

Find local orientation

Dominant direction of gradient

Extract image patches relative to this orientation

 The University of

Multi-Scale Oriented Patches (MOPS) Ontario

Interest points
Multi-scale Harris corners
Orientation from blurred gradient
Geometrically invariant to rotation
Descriptor vector
Bias/gain normalized sampling of local patch (8x8)
Photometrically invariant to affine changes in intensity

[Brown, Szeliski, Winder, CVPR2005]

 The University of

Descriptor Vector Ontario

Orientation = blurred gradient

Rotation Invariant Frame
Scale-space position (x, y, s) + orientation ()
 The University of

Detections at multiple scales Ontario

 The University of

MOPS descriptor vector Ontario

8x8 oriented patch

Sampled at 5 x scale
Bias/gain normalisation: I = (I )/

8 pixels