Image Processing

COMP4421
Hao CHEN, 陳浩
Dept. of CSE and CBE
HKUST
Image Registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

2
Image Registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

3
Introduction
• Images obtained from different conditions (e.g., modalities, angles and times)
need to be aligned properly, i.e., registration. Information from these images are
often complementary.

• Image registration is the process of transforming different sets of data into one
coordinate system.

• Equivalently, Image registration is the task of finding a spatial transform mapping

one image into another.

4
 Introduction
• Example: Aerial photos

5
https://www.mathworks.com/discovery/image-registration.html
 Introduction
• Example: Aerial photos

Landmarks

6
https://www.mathworks.com/discovery/image-registration.html
 Introduction
• Example: Multimodal medical images

7
https://www.mathworks.com/discovery/image-registration.html
 Introduction
• Example: 3D medical image registration

Post-Operation : look at the assessment, if

margin clear? Tumor removed, tissues grow

2D 3D : where the tumor is, accurately

8
http://www.slicer.org/
Introduction
• Object as function

9
 Introduction
1. Transformation
2. Stop and how to update the transformation
(Metric ? To measure the similarity btw
• 2D Image Registration

Only use the intensity from v’(x)

10
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Introduction
• 3D Image Registration

11
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
Introduction
• Typical pipeline of image registration
Reference image Floating image

Update (iterative)

12
Introduction
• Goal of image registration:

13
Introduction
• Goal of image registration:

Comparison between the reference and transformed floating volumes

based on the objective function and the current transformation T.

The goal is to find the optimal value of the objective function and the
෠
optimal transformation 𝑇.

Registration task can be viewed as an optimisation problem: Search for

𝑇 = (𝜃𝑥 , 𝜃𝑦 , 𝜃𝑧 , 𝑑𝑥 , 𝑑𝑦 , 𝑑𝑧 ) that maximises/minimizes 𝐹(𝑢, 𝑣(𝑇))

14
Image Registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

15
Geometric Transformation
• Basic set of 2D geometric transformations

16
Geometric Transformation
• Translation: 𝑇 𝑥Ԧ = 𝑥Ԧ + 𝑑Ԧ

𝑥 𝑥 𝑑𝑥
Example: 𝑇 𝑦 = 𝑦 + 𝑑𝑦
𝑧 𝑧 𝑑𝑧

17
Geometric Transformation
• Rotation
Rotation by about the z axis. (Rotation is measured clockwise about the
z axis while looking along the positive axis direction)

𝑇(𝑥)
Ԧ = 𝑅𝜃 𝑥Ԧ

cos( 𝜃) − sin( 𝜃) 0
𝑅 = sin( 𝜃) cos( 𝜃) 0
0 0 1

18
Geometric Transformation
• Rotation
Rotation by about the x axis.

1 0 0
𝑅= 0 cos( θ) −sin(θ)
0 sin(θ) cos(θ)
Rotation by about the y axis.
cos(𝜃) 0 sin(𝜃)
𝑅= 0 1 0
−sin𝜃 0 cos(θ)

19
Geometric Transformation
• Rigid body transformation: Translation + Rotation (Euclidean)

𝑇 𝑥Ԧ = 𝑅 𝑥Ԧ + 𝑑Ԧ, where 𝑅 is the composition of rotation.

Example: 𝑅 = 𝑅𝜃𝑥 𝑅𝜃𝑦 𝑅𝜃𝑧

20
Geometric Transformation
• Translation + Scaling

Translation 𝑇 𝑥Ԧ = 𝑆𝑥Ԧ + 𝑑Ԧ

𝑥 𝑆𝑥 0 0 𝑥 𝑑𝑥
Example: 𝑇 𝑦 = 0 𝑆𝑦 0 𝑦 + 𝑑𝑦
𝑧 0 0 𝑆𝑧 𝑧 𝑑𝑧

21
Geometric Transformation
• Translation + Shearing

Translation 𝑇 𝑥Ԧ = 𝐾 𝑥Ԧ + 𝑑Ԧ

𝑥 1 𝑘𝑥𝑦 𝑘𝑥𝑧 𝑥 𝑑𝑥
• Example: 𝑇 𝑦 = 𝑘𝑦𝑥 1 𝑘𝑦𝑧 𝑦 + 𝑑𝑦
𝑧 𝑘𝑧𝑥 𝑘𝑧𝑦 1 𝑧 𝑑𝑧

22
Geometric Transformation
• Translation + Shearing

No more preservation of lengths and angles

Parallel lines are preserved.
23
Geometric Transformation
• Affine transformation for non-rigid registration (including shearing and scaling).

• Beyond rigid body motion (translations and rotations only).

• At least 4 pairs of corresponding coordinates are needed to estimate the 12

parameters, i.e., 12 equations and 12 unknowns.

𝑥 𝑎11 𝑎12 𝑎13 𝑎14 𝑥

𝑦 𝑎21 𝑎22 𝑎23 𝑎24 𝑦
𝑇 𝑧 = 𝑧
𝑎31 𝑎32 𝑎33 𝑎34
1 0 0 0 1 1

24
Image Registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

25
Objective Function
• External markers

26
 Objective Function
• External markers

Stereotactic frame is rigidly attached to bone, e.g., the skull.

It is used to register between the physical patient and an image of that patient,
typically for guiding biopsy needles, etc.

27
member.nifty.ne.jp
Objective Function
• External markers
Fiducial markers are used and attached to a patient.

Point-based markers can be skull-implanted, skin-attached or bone implanted。

28
 Objective Function
• Measurement of registration errors
Markers can be seen and located in the images as tiny 3D volumes. Each marker is then
represented by a point, which is defined as the volume centroid.

West, J. B., Fitzpatrick, J. M., Wang, M. Y., Dawant, B. M., Maurer Jr, C. R., Kessler, R. M., ... & Woods, R. P. (1996, April). Comparison and evaluation of retrospective 29
intermodality image registration techniques. In Medical Imaging 1996: Image Processing (Vol. 2710, pp. 332-347). International Society for Optics and Photonics.
 Objective Function
• Internal markers: surface-based registration

Rather than external markers, corresponding surface may be identified

and used for registration. Sheet into registration? (?)

The corresponding surfaces are delineated in the two imaging

modalities and are used to guide the transformation, which minimises
the distance (or some measure of distance) between the two surfaces.

30
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Objective Function
• Internal markers: surface-based registration

X properly aligned
Good

31
Kessler M L, Li K. Image fusion for conformal radiation therapy[J]. 3-D Conformal and Intensity Modulated Radiation Therapy, 2001.
 Objective Function
• Internal markers: edge-based registration

Edges are extracted/segmented based on their values of the gradient function.

Edges are then used to guide the transformation.

32
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Objective Function
• Measurement of registration errors
The registration error is measured by a distance metric between the
corresponding points in 𝑢(𝑥)
Ԧ and 𝑣(𝑥)
Ԧ . Referenced and transformed

West, J. B., Fitzpatrick, J. M., Wang, M. Y., Dawant, B. M., Maurer Jr, C. R., Kessler, R. M., ... & Woods, R. P. (1996, April). Comparison and evaluation of retrospective 33
intermodality image registration techniques. In Medical Imaging 1996: Image Processing (Vol. 2710, pp. 332-347). International Society for Optics and Photonics.
 Objective Function
• Objective functions
1. Sum of squared difference (SSD)
2. Sum of absolute difference (SAD)
3. Correlation coefficient (CC)
4. Mutual information (MI)

34
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Objective Function
• Sum of squared difference (SSD)
Sum of squared intensity difference (widely use)

1 2
𝑆𝑆𝐷 = ෍ 𝑢 𝑥 − 𝑣 𝑇 𝑥
𝑁
𝑥∈𝐷
where D represents the coordinate domain in space.
Pixels
SSD is normalised so that it is invariant to the number of voxels in D.

35
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Objective Function
• Sum of absolute difference (SAD)
Although SSD is widely used, it is very sensitive to a small number of voxels that have
very large intensity differences between u and v (outliners), which results in large
quadratic penalty.
SAD is defined as:

1
𝑆𝐴𝐷 = ෍ |𝑢 𝑥Ԧ − 𝑣 𝑇 𝑥Ԧ |
𝑁
Ԧ
𝑥∈𝐷
SAD can reduce the effect of these outliners.

36
Medical Image Registration, Hajnal, Hill and Hawkes, CRC 2001
 Objective Function
• Correlation coefficient

σ𝑥∈𝐷
Ԧ 𝑢 − 𝑢ത 𝑣 − 𝑣ҧ
𝐶𝐶 = 1
σ𝑥∈𝐷 𝑢 − 𝑢ത 2 𝑣 − 𝑣ҧ 2 2
Ԧ

where D represents the coordinate domain in space, 𝑢ത and 𝑣ҧ represent means

of 𝑢 and 𝑣, respectively.
CC assumes that there is a linear relationship between the intensity values
in the images (-1 ≤ CC≤1).

37
https://en.wikipedia.org/wiki/Correlation_and_dependence
 Objective Function
• Mutual Information
𝑀𝐼 𝑢, 𝑣 = ℎ 𝑢 + ℎ 𝑣 − ℎ 𝑢, 𝑣
where ℎ() represents the entropy (a measure of uncertainty) of a
random variable and ℎ 𝑥, 𝑦 represents the joint entropy of two
random variables
ℎ 𝑥, 𝑦 = − ෍ ෍ 𝑝 𝑥, 𝑦 log 𝑝 𝑥, 𝑦
𝑥∈𝑋 𝑦∈𝑌

ℎ 𝑥 = − ෍ 𝑝 𝑥 log 𝑝 𝑥
https://pymedix.com/2019/03/12/history-of-image-registration-part-3/
https://matthew-brett.github.io/teaching/mutual_information.html
𝑥∈𝑋 38
http://en.wikipedia.org/wiki/Mutual_information
 Objective Function
• Mutual Information
If matched h(u,v) close to 0

𝑀𝐼 𝑢, 𝑣 = ℎ 𝑢 + ℎ 𝑣 − ℎ 𝑢, 𝑣

The third term is the joint entropy which encourages image

matching.

The two images are matched when MI is maximized.

https://pymedix.com/2019/03/12/history-of-image-registration-part-3/
https://matthew-brett.github.io/teaching/mutual_information.html 39
http://en.wikipedia.org/wiki/Mutual_information
Image Registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

40
Optimisation Method
• Goal of optimization
Find 𝑥 that minimises/maximises 𝐹(𝑥), which is an objective function

41
Optimisation Method
• Goal of optimization

For 3D rigid body transformation problem, find 𝑇 = (𝜃𝑥 , 𝜃𝑦 , 𝜃𝑧 , 𝑡𝑥 , 𝑡𝑦 , 𝑡𝑧 ) that

minimises/maximises the objective function, which is given as
𝐹(𝑢 𝑥 , 𝑣(𝑇(𝑥 )))

Global exhaustive search is often too computationally expensive.

Need to search locally the optimal solution in 6-dimensional space.

42
 Optimisation Method
• Most generic algorithm: gradient descent 𝐹 𝑇
• 𝑇 𝑡+1 ← 𝑇 𝑡 − 𝛼∇ 𝑇 𝐹

𝜕𝐹
𝜕𝑇1
• ∇𝑇 𝐹 = ⋮
𝜕𝐹
𝜕𝑇𝑛

• Calculating the gradient is also the basis for

𝑇1 =12 𝑇1
more advanced algorithms, e.g., Quasi-
Newton methods.

43
Press, W. H., Flannery, B. P., Teukolsky, S. A., & Vetterling, W. T. (1989). Numerical recipes.
 Optimisation Method
• Search strategies: multi-resolution approach

Multi-resolution approach is also called coarse-to-fine approach.

Upper level first, …

44
A multi-resolution medical image registration method based on intensity and point features.
Optimisation Method Global: too complex

• Search strategies: multi-start approach (stability)

Which one more robust?

45
Summary Principle to solve image registration

• Introduction

• Geometric transformation

• Objective function

• Optimisation method

46