MEDICAL IMAGE

PROCESSING
DR. HEBA HAMDY
Lecture 6
 IMAGE
MATCHING

3
 IMAGE
MATCHING

Image Features II 3
 IMAGE MATCHING

Image Features II 4
 INVARIANT LOCAL
FEATURES
Find features that are invariant to transformations
− geometric invariance: translation, rotation, scale
− photo-metric invariance: brightness, …

Image Features II Feature Descriptors 5

 WHAT MAKES A GOOD
FEATURE?

Image Features II 6
 WANT
UNIQUENESS
Look for image regions that are unusual
− Lead to unambiguous matches in other
images

How to define “unusual”?

Image Features II 7
 It is not very distinctive

Image Features II 8
 Corners are good features to match

Image Features II 9
 CORNER DETECTOR:
INTUITION

“flat” region: “edge”: “corner”:

no change in all no change along significant change
directions the edge direction in all directions

Image Features II 10
 Corner Detectors Versus Interest Points
• An image corner can be defined as an image point where two or more
edges meet.
• Alternatively, a corner may also be defined as a location where
variations of intensity function in both directions are high.
• Alternatively, a corner may also be defined as a point with low self-
similarity.
• An interest point is a point which has a well-defined position and can be
robustly detected.
• This means that an interest point can be a corner but it can also be, for
example, an isolated point of local intensity maximum or minimum, line
endings, or a point on a curve where the curvature is locally maximal.
• Generally, corner detectors tend to detect interest points rather than
corners.
 CORNER
DETECTOR
• Shift in any direction would result in a significant
change at a corner.

Algorithm:
• Shift in horizontal,
vertical, and diagonal
directions by one pixel.
• Calculate the absolute
value of the MSE for
each shift.
• Take the minimum as
the cornerness
response.

Image Features II 12
 Harris Corner Detector

• The Harris Corner Detector is a mathematical operator that finds

features in an image.
• It is simple to compute, and is fast enough to work on computers. Also, it
is popular because it is rotation, scale and illumination variation
independent.
 CONCEPT

Our aim is to find

little patches of
image (or
"windows") that
generate a large
variation when
moved around.
Have a look at this
image:
 CONCEPT

Regions with
extremely
high variation
 CORNER DETECTOR:
MATHEMATICS
Change of intensity for the shift [u,v]:

E(u, v) =  w(x, y) I (x + u, y + v) − I (x, y) 

2

x, y

Window Shifted
Intensity
function intensity

Window function w(x,y) = or

Image Features II 1 in window, 0 outside Gaussian 15

Image Features II 17
 CORNER DETECTOR:
MATHEMATICS
Consider shifting the window W by (u,v)
• how do the pixels in W change?
• compare each pixel before and after by W
summing up the squared differences (SSD)
• this defines an SSD “error” of E(u,v):

Image Features II 18
 CORNER DETECTOR:
MATHEMATICS
For small shifts [u,v] we have the following approximation:

u 
E(u, v)  u, v  M  
v

where M is a 22 matrix computed from image derivatives:

 I x2 IxI y 
M =  w(x, y)  2 
x, y I x I y I y 

Image Features II 19
 CORNER DETECTOR:
MATHEMATICS


 (I x (x k , y k )) 2
 I (x , y )I (x , y
x k k y k k )
 x 
E = (x y ) ( xk , yk )W ( xk , y k )W
 y 
 I x (x k , y k )I y (x k , yk )
( xk , yk )W  (I (x , y )) y k k
2
 
( xk , y k )W 

Auto-correlation matrix M

22
 CORNER DETECTOR:
MATHEMATICS

Image Features II 21
 CORNER DETECTOR:
MATHEMATICS
Intensity change in shifting window: eigenvalue analysis
u 
E(u, v)  u, v  M   1, 2 – eigenvalues of M
v
direction of the
fastest change
Ellipse E(u,v) = const direction of the
slowest change

(max)-1/2
(min)-1/2

Image Features II 22
 CORNER DETECTOR:
MATHEMATICS
Classification of 2 “Edge”
image points using 2 >> 1 “Corner”
eigenvalues of M: 1 and 2 are large,
1 ~ 2 ;
E increases in all
directions

1 and 2 are small;

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

Image Features II 1 25
 HARRIS
DETECTION
• Auto-correlation matrix
− captures the structure of the local
neighborhood
− measure based on eigenvalues of M
2 strong eigenvalues • => interest point
1 strong eigenvalue • => contour
0 eigenvalue • => uniform region

• Interest point detection

− threshold on the eigenvalues

26
 FEATURE DETECTION
Here’s what you do
SUMMARY
• Compute the gradient at each point in the image
• Create the M matrix from the entries in the gradient
• Compute the eigenvalues.
• Find points with large response ( > threshold)
• Choose those points where  is a local maximum as features

Image Features II
 27
 CORNER
DETECTOR
Measure of corner response:

R = det M − k (trace M )
2

det M = 12
trace M =  + 
1 2

(k – empirical constant, k = 0.04-0.06)

No need to compute eigenvalues explicitly!

Image Features II 28
 CORNER
DETECTOR
• Corner strength R = Det(M) – k Tr(M)2
• Let  and  be the two eigenvalues. We don’t have to
calculate them!

• R is positive for corners, - for edges, and small for flat

regions

27
THE HARRIS
OPERATOR

Harris
operator


28
HARRIS DETECTOR
EXAMPLE

29
R VALUE(RED HIGH, BLUE
LOW)

30
 THRESHOLD (R >
VALUE)

Image Features II 31
FIND LOCAL MAXIMA
OF R
HARRIS FEATURES (IN
RED)

35
 HARRIS DETECTOR
[HARRIS88]

 I x2 ( D ) I x I y ( D ) 
 ( I ,  D ) = g( I )    Ix Iy
Ix I y ( D ) I y2 ( D )  1. Image
derivatives
Ix2 Iy2
IxIy
2. Square of
derivatives
det M = 12
trace M = 1 + 2
3. Gaussian g(Ix2) g(Iy2) g(IxIy)
filter g(I)

4.Cornerness function – both eigenvalues are strong

har = det[  ( I , D)] − [trace(  ( I , D)) 2 ] =
g(I x2 )g(I y2 ) −[g(I x I y )]2 − [g(I x2 ) + g(I y2 )]2
5. Non-maxima suppression 36
Slide:har
Der ek
SUMMARY OF THE HARRIS DETECTOR

37
 HARRIS DETECTOR: SOME PROPERTIES

• Rotation invariance

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

the same

Corner response R is invariant to image rotation

Image Features II 36
 HARRIS DETECTOR: SOME PROPERTIES

• But: non-invariant to image scale!

All points will be Corner !

classified as edges
Image Features II 37
 FAST ALGORITHM
FAST (FEATURES FROM ACCELERATED SEGMENT TEST)

• Identifying interest points in an image.

•An interest point in an image is a pixel which has a
well-defined position and can be robustly detected.
•The reason of the fast algorithm was to develop an
interest point detector for use in real time frame rate
applications.
•Interest point detection has applications in image
matching, object recognition, tracking etc.
FAST ALGORITHM
 FAST ALGORITHM

1.Select a pixel p in the image. Assume the intensity of this pixel to be IP. This is the pixel
which is to be identified as an interest point or not.

2.Set a threshold intensity value t, (say 20% of the pixel under test).

3.Consider a circle of 16 pixels surrounding the pixel p. (This is a bresenham circle of radius
3.)

4.“N” pixels out of the 16 need to be either above or below ip by the value
t, if the pixel needs to be detected as an interest point. (The authors have used N = 12 in the
first version of the algorithm)
 FAST ALGORITHM

5.To make the algorithm fast, first compare the intensity of pixels 1, 5, 9 and
13 of the circle with IP , at least three of these four pixels should satisfy the
threshold criteria so that the interest point will exist.

6.If at least three of the four pixel values. I1 ,I5 ,I9 I13 are not above or below
IP + T, then P is not an interest point (corner).
1.In this case reject the pixel p as a possible interest point.
2.Else if at least three of the pixels are above or below ip +t, then check for
all 16 pixels and check if 12 pixels fall in the criteria.

7.Repeat the procedure for all the pixels in the image.

 FAST ALGORITHM

There are a few limitations to the algorithm.

• First, for N<12, the algorithm does not work very

well in all cases because when N<12 the number of
interest points detected are very high.

• Second, the order in which the 16 pixels are queried

determines the speed of the algorithm.