# Automatic Rigid and Deformable Medical Image Registration. a dissertation submitted to the

Automatic Rigid and Deformable Medical Image Registration

by

Hongliang Yu

A Dissertation Submitted to the Faculty of the

WORCESTER POLYTECHNIC INSTITUTE

in partial fulfillment of the requirements for the Degrees of Doctor of Philosophy in Mechanical Engineering by _________________ May 2005

Committee Approval: ____________________________ Professor John M. Sullivan, Jr. (Advisor) ____________________________ Professor Allen H. Hoffman (Committee Member) ____________________________ Professor Reinhold Ludwig (Committee Member) ____________________________ Professor Gretar Tryggvason (Committee Member) ____________________________ Professor Zhikun Hou (Graduate Committee Representative)

Abstract

Advanced imaging techniques have been widely used to study the anatomical structure and functional metabolism in medical and clinical applications. Images are acquired from a variety of scanners (CT/MR/PET/SPECT/Ultrasound), which provide physicians with complementary information to diagnose and detect specific regions of a patient. However, due to the different modalities and imaging orientations, these images rarely align spatially. They need to be registered for consistent and repeatable analyses. Therefore, image registration is a critical component of medical imaging applications.

Since the brains of rodent animal mostly behave in the rigid manner, their alignments may be generally described by a rigid model without local deformation. Mutual information is an excellent strategy to measure the statistical dependence of image from mono-modality or multi-modalities. The registration system with rigid model was developed to combine with mutual information for functional magnetic resonance (fMRI) analysis, which has five components: (1) rigid body and affine transformation, (2) mutual information as the similarity measure, (3) partial volume interpolation, (4) multidimensional optimization techniques, and (5) multi-resolution acceleration.

In this research three innovative registration systems were designed with the configurations of the mutual information and optimization technique: (1) mutual information combined with the downhill simplex method of optimization. (2) the derivative of mutual information combined with Quasi-Newton method. (3) mutual

i

information combined with hybrid genetic algorithm (large-space random search) to avoid local maximum during the optimization. These automatic registration systems were evaluated with a variety of images, dimensions and voxel resolutions. Experiments demonstrate that registration system combined with mutual information and hybrid genetic algorithm can provide robust and accurate alignments to obtain a composite activation map for functional MRI analysis.

In addition, deformable models (elastic and viscous fluid) were applied to describe the physical behavior of the soft tissues (female breast cancer images). These registration methods model the movement of image as an elastic or viscous fluid object with material attributes corresponding to the constitution of specific tissues. In these two models the physical behavior of deformable object is governed by Navier linear elastic equation or Navier-Stokes equation. The gradient of image intensity was selected as the driving force for the registration process. The equations were solved using finite difference approach with successive over-relaxation (SOR) solver. Soft tissue and synthetic images were used to verify the registration method. All of these advancements enhanced and facilitated the research on functional MR images for rodent animals and female breast cancer detection.

ii

Acknowledgements

I wish to express sincere gratitude to professor John M. Sullivan, Jr., my advisor, for his academic guidance and generous financial support for my PhD education at Worcester Polytechnic Institute. Throughout the four years of research work, his continuous help, enthusiasm and technical insights encourages me to overcome the problems and enrich my knowledge and skills.

My deep appreciation goes to Dr, Allen H. Hoffman, Dr. Reinhold Ludwig, Dr. Gretar Tryggvason, and Dr. Zhikun Hou for their service as the committee member. They provided the valuable time, advice and suggestions in reviewing my thesis.

Thanks to the all students, lab members and staff I have worked with at WPI and University of Massachusetts Medical School. As the member of lab, I benefit a lot from their friendship and support.

I would like to express sincere gratitude to my parents who have given me lifetime love and encouragement.

I wish to convey special thanks to my wife, Vicky. Her undying love and support encourages me to turn my instant inspirations into the reality. We will remember the cheerful time we spent together at WPI.

iii

Table of Contents

Abstract............................................................................................................................... i Acknowledgements .......................................................................................................... iii Table of Contents………………………………………………………………………..iv List of Figures................................................................................................................. viii Chapter 1 Introduction................................................................................................. 1

1.1 Medical Imaging Modalities ..................................................................................... 2 1.1.1 Computerized Topography (CT)........................................................................ 2 1.1.2 Magnetic Resonance Imaging (MRI)................................................................. 3 1.1.3 Functional Magnetic Resonance Imaging (fMRI) ............................................. 6 1.1.4 Positron Emission Topography (PET) and Single Position Emission Computerized Topography (SPECT).......................................................................... 8 1.2 Medical Image Registration...................................................................................... 8 1.2.1 Definition of Registration .................................................................................. 9 1.2.2 General Workflow for Synthetic Imaging ......................................................... 9 1.3 Applications of Medical Image Registration .......................................................... 10 1.3.1 Radiation Therapy............................................................................................ 11 1.3.2 Cancer Detection.............................................................................................. 11 1.3.3 Template Atlas Application ............................................................................. 11 1.3.4 Functional MRI Analysis................................................................................. 12

iv

1.3.5 Image-guided Surgery...................................................................................... 13 Chapter 2 Background ............................................................................................... 15

2.1 Registration Methodologies .................................................................................... 15 2.1.1 Manual Registration......................................................................................... 15 2.2.2 Landmark Registration..................................................................................... 17 2.2.3 Surface Registration......................................................................................... 19 2.2.4 Intensity-based Registration............................................................................. 20 2.2 Classifications by Model......................................................................................... 24 2.2.1 Rigid Transformation....................................................................................... 24 2.2.2 Deformable Transformation............................................................................. 25 2.3 Objectives of the Dissertation................................................................................. 29 Chapter 3 Rigid Registration..................................................................................... 31

3.1 Rigid-body Model................................................................................................... 32 3.2 Affine Model........................................................................................................... 33 3.3 Coordinate System Transforms............................................................................... 34 3.3.1 Image-to-world Transform............................................................................... 35 3.3.2 World-to-image Transform.............................................................................. 36 3.3.3 Image-to-image Transform .............................................................................. 37 3.4 Mutual Information................................................................................................. 37 3.4.1 Definition ......................................................................................................... 37 3.4.2 Gradient of Mutual Information....................................................................... 41 3.5 Interpolation............................................................................................................ 43

v

3.5.1 Nearest-neighbor Interpolation…………………………………………...…..45 3.5.2 Trilinear Interpolation...................................................................................... 46 3.5.3 Partial Volume Interpolation............................................................................ 48 3.6 Multi-dimensional Optimization Techniques ......................................................... 49 3.6.1 Downhill Simplex Method............................................................................... 50 3.6.2 Quasi-Newton .................................................................................................. 54 3.6.3 Genetic Algorithm (GA) .................................................................................. 55 3.7 Multi-Resolution Speedup ...................................................................................... 63 3.8 Implementation ....................................................................................................... 63 3.8.1 3D Registration System ................................................................................... 63 3.8.2 Registration Framework................................................................................... 65 3.8.3 Application on Functional MRI Analysis ........................................................ 66 3.9 Validation................................................................................................................ 67 Chapter 4 Deformable Registration .......................................................................... 70

4.1 Deformable Registration with Linear Elastic Model……………………………...71 4.1.1 Navier Linear Elastic Equation........................................................................ 71 4.1.2 Image Registration with Linear Elastic Model ................................................ 72 4.1.3 Experiment of Linear Elastic Image Registration…………………………….75 4.1.4 Limitations ……………………………………….…………………………..76 4.2 Deformable Registration with Viscous Fluid Model……………………………...76 4.2.1 Navier-Stokes Equation ................................................................................... 76 4.2.2 Viscous Fluid Image Registration.................................................................... 77 4.2.3 Experiment of Viscous Fluid Image Registration............................................ 78

vi

4.3 Discussion ............................................................................................................... 79 Chapter 5 Results........................................................................................................ 82

5.1 Rigid Registration on 3D Synthetic Images……………….……………….……...82 5.2 Rigid Registration on 3D Rat Brain Images…..………………………….…….....84 5.3 Deformable Registration on 2D Rat Brain Images……….…………………….....90 Chapter 6 Conclusions................................................................................................ 94

References........................................................................................................................ 97

vii

List of Figures

Figure 1 -1 Figure 1 -2 Figure 1 -3 Figure 1 -4 Figure 1 -5 Figure 1 -6 Figure 1 -7 Figure 1 -8 Figure 1 -9 Figure 2 -1 Figure 2 -2 Figure 2 -3 Figure 2 -4 Figure 2 -5 Figure 3 -1 Figure 3-2 Figure 3-3 Figure 3 -4 Figure 3 -5 Figure 3 -6

The schema of computerized topography (CT) imaging ............................. 3 The movement of proton.............................................................................. 4 a) with the external field the movement will aligned with B0...................... 5 Magnetic resonance (MR) images of human brain. ..................................... 6 “Lit-up” example of function MRI brain analysis ....................................... 8 Image registration process............................................................................ 9 The workflow of synthetic imaging ........................................................... 10 The rat brain atlas overlaid on subject provides standard information. ..... 12 Two subjects of rat brain in functional MRI analysis ................................ 13 An example of 2D landmark registration................................................... 18 Illustration of “fit a hat to head” algorithm................................................ 19 Transformation of rigid-body model.......................................................... 24 Transformation of affine model ................................................................. 25 Transformation of deformable model ........................................................ 26 Definitions of world and image coordinate systems .................................. 34 Representation of mutual information (MI)................................................ 38 The relation between entropy and mutual information ............................... 41 The pseudo code for coordinate mapping .................................................. 44 2D example for coordinate mapping.......................................................... 44 Nearest-neighbor interpolation................................................................... 45

viii

Figure 3 -7 Figure 3 -8 Figure 3 -9 Figure 3 -10 Figure 3 -11 Figure 3 -12

The pseudo code of nearest-neighbor interpolation ................................... 46 Trilinear interpolation ................................................................................ 46 The pseudo code for trilinear interpolation................................................ 48 The pseudo code for partial volume interpolation .................................... 49 The initial simplex..................................................................................... 50 Reflection away from the highest point .................................................... 51

Figure 3 -13 The reflection and expansion away from the highest point ...................... 51 Figure 3 -14 Figure 3 -15 Contraction in one direction from the highest point ................................. 52 Contractions in all directions towards the best point ................................ 52

Figure 3 -16 The pseudo code for downhill simplex method ........................................ 53 Figure 3-17 Figure 3-18 The workflow of genetic algorithm …….………………………………...59 Three crossover operators……………………………..…………………60

Figure 3-19 The workflow of hybrid genetic algorithm ………………………………63 Figure 3 -20 Figure 3 -21 Figure 3 -22 Multi-resolution registration with 3 levels……………………………….65 The constitution of registration component……………………………...66 The mutual information registration in application of fMRI analysis…...67

Figure 4–1 The elastic registration of female breast image........................................... 74 Figure 4–2 Figure 4–3 Figure 4-4 Figure 4-5 Figure 5–1 The deformation field of reference image .................................................. 75 Experiment on the synthetic image circle and rectangle. ........................... 78 The deformation process at different time steps ......................................... 80 The similarity measure within fluid registration……………………..........80 The performance of GA, Downhill simplex and Quasi-Newton methods for

test data 1-3 (reference 2 with subject 9). ......................................................................... 87

ix

Figure 5–2 Figure 5-3 Figure 5-4 Figure 5-5 Figure 5-6

Image views for registration results of experiment 4……………………..89 Solid model views for registration results of experiment 4…………….....90 Deformable registration on reference 2 and subject 9………………….....91 Linear elastic registration on reference 2 and subject 9…………………...92 Viscous fluid registration on reference 2 and subject 9…………………...93

x

Chapter 1 Introduction

Rapid development of computer techniques expands the imaging tools to study, diagnose and predict the illness of patient. In early 1970s computerized topography (CT) was put into the clinical application. Other imaging modalities such as magnetic resonance imaging (MRI), positron emission topography (PET), single photon emission computed topography (SPECT), functional magnetic resonance imaging (fMRI), followed the CT pathway into the surgical and radiotherapy applications. With the aid of advanced diagnostic techniques, physicians can obtain accurate and complementary information about a tumor or situation, which greatly benefits the early detection of diseases and unhealthy conditions.

In clinical and surgical procedures, patients undergo a series of medical imaging studies CT, MRI, PET before the treatment. Since each imaging strategy alters the orientation and positioning of the patient, the physician must address the issue of how to compare and analyze the images from all the modalities. The best strategy is image fusion [1] that integrates the useful information from all the images into one image. All the images need to be co-registered into the same spatial location before they can be integrated and visualized.

Function MRI analysis is a newly developed strategy to study psychological behaviors associated with various physical and/or psychological stimulations like fear,

1

hunger or other chemical stimuli. During the experiment, images are acquired from a group of subjects to explore the brain functional activities. Registration of images from all subjects is a critical step to obtain an accurate composite activation map. Medical image registration plays a very important role in clinical and medical applications. To analyze the image from different scanners, all the images need to be aligned into the same location where the structure of tissues can be compared. Various registration strategies based on manual registration, landmark, voxel similarity were developed to satisfy the increasing needs of medical applications. 1.1 Medical Imaging Modalities Generally, medical imaging modalities are divided into two main categories: (1) the anatomical imaging with high resolution (CT and MRI) to describe the primary morphology. (2) the functional imaging with low resolution (PET, SPECT and fMRI) to study the functionality of underlying anatomical structures. The integration of the images from the different modalities provides the complementary information for surgical planning and guidance of radiotherapy.

1.1.1 Computerized Topography (CT) CT was the first medical imaging modality [2]. The x-ray tube is rotated around the patient. X-rays are emitted by the tube as it transverses around the body. Linear detectors are installed on the other side of the x-ray tube to receive the transmitted x-ray beams after attenuation.

2

Since the x-ray attenuation properties of various tissues differ, the final transmitted x-rays can be correlated to the tissue properties within its path. Detectors will collect the profiles of x-rays with different strength passed through the patient and generate the projection data. Through the backward projection method, the cross-section image slice will be reconstructed from the collected data. Figure 1-1 shows the schema that x-ray tube rotates around the patient and detectors collect the passing beam of x-rays.

Figure 1 -1:

The schema of computerized topography (CT) imaging Source: http://www.fda.gov/cdrh/ct/what.html

1.1.2 Magnetic Resonance Imaging (MRI) MRI [2] [3] is an imaging technology that does not employ ionizing radiation. According to the quantum mechanic of atomic structure, the nucleus of hydrogen spins around the axis and produces the magnetic moment. In the biological tissue there are abundant hydrogen nuclei with the form of water (H2O) and other carbon hydrogen compounds. Hydrogen nuclei (protons) have the strongest magnetic moment, which

3

makes MR imaging possible by analyzing the reaction of protons within the biological tissue under the external magnetic field.

Spin of Proton External Magnetic Field

(a)

(b) Figure 1 -2 The movement of proton. (a) spinning movement under the external magnetic field (b) random movement without the external magnetic field.

In the absence of an external magnetic field, the direction of magnetic moment for protons is random. If an external magnetic field is applied, the nuclear magnetic moment will align with the external magnetic field.

4

B0 External magnetic field

Anti-parallel

Parallel

(a)

Z

B0

Mz M

Y Mxy X

(b) Figure 1 -3 a) with the external field the moment will aligned with B0, b) magnetic moment is turned into the transverse plane.

In MR imaging, a radiofrequency (RF) pulses generated by RF coil, as the external field, are applied on the patient. Under the RF perturbation, the hydrogen nuclei (protons) in the patient absorb the energy and leave the location of equilibrium. Through

5

the transverse relaxation and longitudinal relaxation, the protons will return to equilibrium after some time that depends on the magnetic property of the biological tissue. During this period of time, the energy of protons will be dissipated as the radio wave. These electromagnetic waves emitted by the protons will be detected by another coil (receiver) that surrounds the patient.

The slice selection is accomplished by varying the gradient of the magnetic field as a function of position. This causes the linear variation of the proton resonance frequency along with the position. The MR imaging system uses the frequency encoding and phase encoding to determine the position of each signal within the patient.

Figure 1 -4 Magnetic resonance (MR) images of human brain. Source: Visible Human Project (VHP), NLM [10]

1.1.3 Functional Magnetic Resonance Imaging (fMRI) Functional MRI is an approach to explore which part of brain is activated by various types of physical simulations (sound, sight and fear) or chemical stimulation.

6

A time series of 3D images are acquired during the functional MR imaging experiments. In general, the experiment is designed with two time periods: control period and stimulation period. During the control period the subject is performing normal functions or a normal task. During the stimulation period, the subject is applied with single or multiple well-controlled stimulus or specific tasks.

It is believed that when an area of the brain is activated with the specific task, it will require more energy and oxygen. Consequently, the blood flow increases to that region of activity. The MRI is sensitive to the slight changes in blood flow and therefore the intensity in that region changes. Frequently this response is labeled Blood

Oxygenation Level Dependant (BOLD). Pixels with significant change or corresponding changes in image intensities indicate their association of the input specific task. With the statistical analysis, the areas of activated pixels are determined. The map of brain activation can either be overlapped on the co-registered anatomical image or “lit up” over multiple time steps and visualized in three-dimensional brain surface. This approach provides the researchers to study the areas of brain function and illness.

The statistical time analyses include Student T-test, Anova (univariate analysis of variance), Manova (multivariate analysis of variance) and GLM (General Linear Regression Model).

7

Figure 1 -5 “Lit-up” example of function MRI brain analysis. Source: http://astor.som.jhmi.edu/~esg/TALKS/fMRI.ppt

1.1.4 Positron Emission Topography (PET) and Single Position Emission Computerized Topography (SPECT) PET and SPECT [2] images are generated by depicting the distribution of radioactive isotopes in patients. When the radio-labeled compounds are injected in trace amounts, their emissions can be detected similar to x-rays in CT imaging. The resulting image represents the distribution of the labeled compound, which may reflect the blood flow, oxygen or other metabolism. 1.2 Medical Image Registration The spatial registration of multimodality images is the essential pre-requisite of surgery and medical imaging applications.

Many strategies have been proposed and implemented for the image registration based on either the geometrical features (point-like anatomic features or surfaces) or intensity similarity measures (cross correlation, squared intensity differences or mutual information).

8

1.2.1 Definition of Registration Image registration is the process to find the best alignment to map or transform the points in one image set to the points of another image set. The matching process mainly involves: firstly defining a metric (goodness of registration) to measure how well two images are aligned; and secondly, searching for the best transformation to bring two images into the spatial alignment.

Transform

Figure 1 -6 Image registration process is to search for the best spatial transform between two images.

1.2.2 General Workflow for Synthetic Imaging Although the anatomical nature of specific areas of biological tissue (shape, position, size, etc) is same, visibility of same tissue is different under various modalities. Although it is visible in one modality, it may not be seen in the other imaging modalities. The combination of images from different modalities leads to additional clinical information which is not apparent in the separate imaging modality. For this reason physicians prefer multiple imaging modalities to obtain more details. Image fusion is performed to extract all the useful information from the individual modality and integrate

9

them into one image. For the images obtained from different scanners, they must be aligned into the same spatial location before image fusion and visualization.

Figure 1-7 shows the workflow of synthetic imaging [54]. Images from the different scanners are co-registered into the same geometrical location. Then all these images are integrated into one image through image fusion. The resulting composite image is visualized [4] with computer graphic system. This strategy provides physician the most complete information integrated from each individual modality.

Figure 1 -7

The workflow of synthetic imaging.

1.3 Applications of Medical Image Registration Medical image registration is widely used in the clinical and medical applications.

10

1.3.1 Radiation Therapy The radiation therapy utilizes the ionizing radiation (X-rays, Gamma rays) from a linear accelerator to kill or stop the growth of tumor. The goal of radiation treatment is to deliver energy dose of radiation to abnormal tissue to stop cancer cells from dividing. At the same time with precise therapy simulation and planning, damage of therapy will be minimized for the surrounding normal tissue.

Therefore, before therapy treatment, both CT and MRI scans are employed on patient. MR imaging is suitable for the localization of tumor; CT imaging for calculation of radiation dose and determination of optimal path.

1.3.2 Cancer Detection Image registration is important in the early detection of cancers [5]. Radiologists need to identify the exact anatomical location of cancer and monitor its effects on motion. It is still difficult to localize and determine the tumor with the anatomical information from CT and MR scans because of the low contrast between the tumor and the surrounding tissues. SPECT and PET imaging makes it possible to acquire high contrast images. However, they do not provide enough anatomic detail to determine the position of a tumor or other lesion. It would be more useful to align the structural anatomic image from CT/MR onto the functional image from SPECT/PET. 1.3.3 Template Atlas Application As the standard information database, an atlas is constructed from imaging studies of a large number of subjects. Therefore, an atlas includes the most details about the

11

anatomical structure of subject, which is very helpful for understanding the structure and function areas of subject. In the functional MRI analysis, matching MR scans with anatomic atlases provide an important means to evaluate and identify the features (size, shape, location) of anatomical areas. This registration process is accomplished through several operations: (1) manually manipulate the images into the same location. (2) identify the anatomical landmarks and transform image to the atlas space by minimizing the distance among landmarks. (3) deform atlas into the shape of any subject. Through these operations, atlas and subject image will be overlapped with the corresponding areas aligned, which helps researcher compare structures of multiple subjects to the atlas (reference) quantitatively.

Figure 1 -8

The rat brain atlas overlaid on subject provides standard information.

1.3.4 Functional MRI Analysis In functional MRI experiments, time-sequential 3D images are acquired for statistical analysis. When the images are analyzed to infer the activation response for statistical confidence level, it is based on assumption that a given pixel of functional area

12

is located at the same location for all the subjects. If the subject moves around during the scans, the false BOLD activation areas will be identified in the time-series analysis. Therefore, it is critical to register the time series of images from the spatial and temporal space before statistical data analysis.

Figure 1-9 shows two MR images of rat brain acquired from different subjects. There are dramatic anatomical differences (size and shape) between the two images. In addition, it is impossible to have the subjects positioned at the same location during scans. Inter-subject registration work is necessary to align two images geometrically before the functional MRI analysis.

(a) Figure 1 -9

(b)

Two subjects of rat brain in functional MRI analysis. (a) misalignment; (b) good alignment

1.3.5 Image-guided Surgery Image-guided surgery is the part of computer-assisted surgery, which is composed with pre-operative planning and intra-operative navigation. Pre-operative planning

13

includes obtaining the information from CT and MR scans to localize the lesion or tumor, generating three-dimensional model and determining the optimal path of surgery. During the intra-operative navigation each movement of instruments is tracked from the video camera and superimposed on the image, which assists a surgeon identify intra-operative movement of the instrument relative to pre-operative 3D model of patient. This powerful computer technology provides the ability of 3D rendering and analysis like the real-time surgery. During the surgery image registration is employed in the navigation system to real-time track the changes of instruments in relation to 3D model built from the preoperative CT/MR scans.

14

Chapter 2 Background

This chapter provides a literature review for medical image registration. Since a large number of publications in this area are available, the papers were reviewed following the classification of medical image registration techniques.

2.1 Registration Methodologies The classification of image registration methods [6][7][8] can be based on the nature of matching base or the nature of transformation. According to the nature of matching base, medical image registration is divided into four main categories: manual registration, landmark-based registration, surface-based registration, and intensity-based registration. According to the nature of transformation, image registration can also grouped into several categories: rigid body model, affine model, linear elastic model, viscous fluid model, finite element model (FEM), radial basis function (RBF) model, optical flow model, and others.

2.1.1 Manual Registration Manual registration is the process that user needs to do all the registration work interactively with the visual feedback from computer system. Many medical image applications [9] provide the utility of manual registration to align image studies from same or different modality. Users are able to manipulate images through 3 orthogonal

15

views (axial, coronal and sagittal) interactively with real-time visual feedback and achieve accurate alignment with the help of anatomical and surface features.

Manual registration has some limitations. The accuracy of registration depends on the user’s judgment on the correspondence between anatomical features. Different users have different results. And it may take user much time to get good alignment. Figure 2-1 shows the human brain MR image from VHP project [10] displayed in three views (axial, coronal and sagittal). Good alignment is achieved by manual

adjustments of one image volume to fit another in three-dimensional space. The transformation is the linear combination of translations, rotations and scale factors in x, y, z directions, respectively.

Figure 2-1 Manual registration. a) two unaligned image volumes, b) manual registration adjustment GUI, c) aligned image volume sets.

16

2.2.2 Landmark Registration Landmark registration [11][12][13][14][15] involves the identification of the locations of corresponding points within different images and determination of the spatial transformation with these paired points.

There are two types of landmark: internal landmark and external landmark. Internal landmark are commonly known as anatomical markers, which are point-like anatomical features within the images of all the modalities. They are identified and marked by medical expert by means of software to define the corresponding anatomical structures. External marker is the artificial object attached to the patient before image acquisition. They need to be visible and easily identified within all images.

The basic process of landmark registration is: (1) identifies and pairs the landmarks (anatomical features or external marker) from the corresponding images. (2) calculate the geometrical transformation by minimizing the distance between the coordinates of these landmarks. The definition of landmark registration: given 2 sets of corresponding N points P = {pi} and Q = {qi}, we are looking for the transformation T which minimizes the root square distance between the corresponding points: Sum _ diff = (∑ (T ( pi ) ? qi ) 2 ) 2

i 1

(2.1)

In 1998 Fitzpatrick et al [16] mathematically analyzed error occurring in rigidbody landmark-based registration, which is decomposed into three parts: (1) fiducial

17

localization error (FLE): displacement error resulting from improper placement of landmarks; (2) target registration error (TRE): the registration error from the corresponding landmarks; (3) fiducial registration error (FRE): registration error from searching for transformation by minimizing the root square distance difference between the corresponding landmarks. Formula 2.1 belongs to the least-square problem [17], which is solved by singular value decomposition (SVD) or other least-square solvers.

Figure 2-2 shows an example of 2D landmark registration between MR image and a slice of rat brain atlas [18]. Within each image four or more points need to be identified and paired (A1, B1), (A2, B2), (A3, B3) and (A4, B4). The registration process is driven by minimizing the distance between the coordinates of these paired landmarks.

Figure 2 -1

An example of 2D landmark registration.

18

2.2.3 Surface Registration Surface-based registration [19][20][21][22][23] involves the extraction of the surface models from the images and determination of transformation by minimizing of the distance between the corresponding surface models. For landmark-based registration control points are identified by user manually, whereas the surface-based technique needs to reconstruct surface models from a stack of contours segmented from image slices.

Pelizzari et al [24] developed a surface matching strategy to accurately align CT, PET, and /or MR brain image, which he described as “fit a hat to head”. Through this technique two surface models were generated: “hat” and “head”. The “hat” surface is a skin surface from PET scan with low resolution. The “head” surface is a stack of skin contour from CT or MR scans with high resolution. Two segmented surfaces were visualized in 3D computer graphic system and aligned by minimizing the mean square distance between them.

Figure 2 -2

Illustration of “fit a hat to head” algorithm. Source: Internet

19

In Figure 2-3, two 3D surface models were generated from the images: “hat” surface was represented as a list of discrete 3d points with low resolution, while “head” surface consists of a stack of contours with high resolution. Accurate alignment was achieved by minimizing the distance between two surface models.

Borgefors [25] proposed the fast “Hierarchical Chamfer Matching “algorithm for surface matching. A chamfer distance map was defined by the distance of corresponding edges. The surface matching applies this distance map as a potential function and the total potential was minimized with hierarchical approach to reduce computational load.

Besl and Mckay [26] presented more general-purpose registration strategy “Iterative Closest Point (ICP)”. For each iteration of registration process, the closest point in one surface was determined from all the points relative to another surface. These point correspondences were used to align the image by optimizing the transformation.

2.2.4 Intensity-based Registration Since the early of 1990s, many fully automatic algorithms have been put forward for image registration by optimizing voxel similarity measures. From the statistical view an image is the distribution of random variable (image intensity). Intensity-based registration is to measure the similarity of two images, the distributions between two random variables, by the statistical description and optimize it by adjusting the transformation parameters.

20

Correlation Coefficient (CC) The correlation coefficient (CC) [27][28], also called Pearson’s product-moment correlation coefficient, was used for the intra-modality registration. It is expressed as:

CC =

∑ ( A( x) ? A) ? ( B

x

?

T

( x) ? B )

T

?

∑ ( A( x) ? A)

x

?

2

?

∑ (B

x

( x) ? B )

?

(2.2)

2

in which A and B are the mean intensity values of image A and B, respectively. T is the transformation.

?

?

Squared Intensity Difference (SSD) The sum of squared intensity differences (SSD) measure [29] [30] was also applied for intra-modality registration of medical images. The SSD measure is calculated by:

SSD =

1 N

∑ [ A( x) ? B

i =1

N

T

( x)]2

(2.3)

where A(x) and B(x) are the intensity values at the corresponding voxel x in image A and B, respectively. N is the total pixel numbers of image A. T is the transformation.

Ratio Image Uniformity (RIU)

Woods et al [31][32][33][34] introduced the ratio image uniformity (RIU) as the similarity measure in 1992 for intra-modality alignment of PET and MR images, as well as cross-modality registration of PET and MR images.

21

If A(x) and B(x) are the intensity values at the corresponding voxel x of image A and B, respectively. The gray scale intensity ratio is calculated by R(x) = A(x) / B(x). The registration strategy assumes that R(x) is maximally uniform across voxels if the two images are accurately registered. If σ is the standard deviation of R(x) and R is the mean value of R(x), this strategy uses σ / R as the similarity measure to evaluate how well the two images are registered. A( x) B ( x)

? ?

Image Ratio

R( x) =

?

(2.4)

Mean value

R=

1 N

∑

1 N

x

R( x)

?

(2.5)

2

Standard deviation

σ=

∑ ( R( x) ? R)

x

(2.6)

? 2

Ratio image uniformity

RIU =

1 N

∑ ( R( x) ? R)

x

R

?

(2.7)

Mutual Information (MI)

In 1994 Viola and Wells [35] [36], and Maes et al [37] presented a new approach, maximization of mutual information, based on information theory. This approach applied mutual information to evaluate the statistical dependence (association) between two image intensity distributions. It assumes that mutual information will be maximized if two images are spatially aligned.

22

According to communication (information) theory, the uncertainty of a random variable x with probability mass function p x ( x) is measured by its entropy H ( x) . The

Shannon entropy [38] is defined as: H ( x) = ?∑ p x ( x) log p x ( x)

x

(2.8)

Given two random variables x and y with joint probability mass function Pxy ( x, y ) , the amount of information that one variable contains about another is

evaluated by mutual information: MI = H ( x) + H ( y ) ? H ( x, y ) = H ( x) ? H ( x | y )

= H ( y ) ? H ( y | x)

in which, Joint entropy of x and y:

(2.9)

H ( x, y ) = ?∑ p xy ( x, y ) log p xy ( x, y )

x, y

(2.10)

Conditional entropy of A given B:

H ( x | y ) = ?∑ p xy ( x, y ) log p xy ( x | y )

x, y

(2.11)

Conditional entropy of B given A: H ( y | x) = ?∑ p xy ( x, y ) log p xy ( y | x)

x, y

(2.12)

Therefore, mutual information is the difference between the marginal entropy of x and y and the joint entropy of x and y.

23

2.2 Classifications by Model

The registration methods are classified into two main categories by transformation models: rigid model and deformable model, which reveal the inherent characteristic (physical or optical) of transformation that drives one image warp into another image.

2.2.1 Rigid Transformation

Rigid body and affine transformation define rigid transformation in which the transformed coordinates are the linear transformations of the original coordinates.

Rigid-body Model

Rigid body modal only includes the combination of translations and rotations. The object has no shape change. The distance between two points in the first image is preserved after mapping into the second image.

(a)

(b)

Figure 2 -4 Transformation of rigid body model. (a) Original image, (b) Rigid body transformation.

24

Affine Model

Affine model [39] involves the succession of translations, rotations and scalings. The parallelism will be preserved when the straight line in the first image is mapped into straight line in second image.

(a)

(b)

Figure 2 -5 Transformation of affine model. (a) Original image, (b) Affine transformation.

2.2.2 Deformable Transformation

The general formulation of image deformable registration is to minimize the energy or cost function. The cost function, the objective function of optimization, is defined as cos t =

volume

∫

deformation ?

volume

∫ similarity

(2.13)

The similarity term works as the external driving force to maximize the similarity of two image sets , which can be either the distance between landmarks (anatomical structure) or intensity similarity (intensity difference, mutual information).

25

(a)

(b)

Figure 2 -6 Transformation of deformable model. (b) Original image, (b) deformable transformation. The deformation term is the motion of object to be registered. The motion depends on the physical properties of object, which can be linear elastic deformation, viscous fluid deformation and other complicated forms.

Elastic Model

The registration with elastic model was presented by Bajcsy et al [40][41][42][43] to align the human brain images. The principle of elastic registration is to imagine the registration process as deforming elastic object under the external body force. The motion of elastic object is governed by the Navier linear elastic equation:

?? 2 u + (λ + ? ) ?(? ? u ) + f = 0

→

→

→

→

→

(2.14)

in which: u is the deformation field. f is the external force. λ and ? are elasticity constants, which determine the material properties of object to be registered.

26

Viscous Fluid Model

In 1994 Christensen [44][45][46] proposed viscous-fluid-continuum model to accommodate the large deformation while keeping continuity and smooth deformation of the object. It can model the local small deformation, while linear elastic registration not. In the Eulerian reference frame, the formulation of viscous fluid model is described by Navier-Stokes equation:

→ → →

?? 2 v + (λ + ? ) ?(? ? v ) + f = 0

→ →

(2.15)

in which , v is the velocity field. f is the external force. λ and ? are viscosity constants. ?2 is the Laplace operator.

Christensen solved this equation by using successive over-relaxation (SOR) method within the finite difference frame. It is very time consuming to numerically solve the equation at each grid over the full 3D image set. Bro-Nielsen [47] accelerated the registration process by applying the multi-dimension convolution filter derived from the linear elasticity operator.

Finite Element Model (FEM)

Finite element model [48][49][50] is also called the biomechanical model. The Navier linear elastic equation is solved at a set of discrete nodes on finite element mesh. This method will segment the image volume into various tissues of interest, generate the volume meshes for specific tissue and assign them the specific tissue material properties as the deformation constraints. Similar to the finite difference solver, the extern forces can the gradient of similarity measures (mutual information, correlation coefficient, 27

intensity difference) and the distance between the landmarks (anatomical areas). By tracking and visualizing the motion of tissues, the finite element model is suitable for image-guided surgery.

Radical Basis Function (RBF)

Deformable registration can be also realized by representing the deformation field through a linear combination of radial basis functions, which can be high-order polynomials, thin-plate spline, B-splines, and so on. The general formulation is like:

?x' ? ? f 1 ( x, y, z ) ? ?m00 ? '? ? ? ?m ... ?y ? = T ? ? ? = ? 10 n ' ?z ? ? f n ( x, y, z )? ?m20 ? ? ? ? ? 1 ?1? ? ? ? ? 0 ? m 01 ... m0 n ? ? f1 ( x, y, z ) ? ? ? ... m11 ... m1n ? ??? ? m21 ... m2 n ? ? f n ( x, y, z )? ? ? ? 0 0 1 ? ? 1 ?

(2.16)

Wood et al implemented an AIR (automatic image registration) package to provide the deformable registration [51] with high-order polynomial whose order varies from low to high. The seventh order polynomial provides 360 degree of freedom. Mayer et al [52] [53] [54] proposed the thin plate spline for warping registration. Rueckert [55] presented the free-form B-spline to align the female breast MR images. Radial basis function was also applied for human brain mapping within Fristion’s [56][57][58] statistical parametric mapping (SPM) software.

Optical Flow Model

This approach of deformable registration was presented by Thirion [59][60] to apply the optical flow, which assumes that the image intensity remains constant to recover the movement between object and viewer over time span of image sequences.

28

I ( x, y, z, t ) = I ( x + dx, y + dy, z + dz, t + dt )

Therefore, the temporal derivative of image intensity is equal to zero.

(2.17)

dI ?I ?x ?I ?y ?I ?z ?I + + = + dt ?x ?t ?y ?t ?z ?t ?t

= ?I ?I ?I ?I Vx + V y + Vz + ?x ?y ?z ?t

→

= ?I xyz ? V + ?I t = 0

(2.18)

The vector field can be derived and added to the previous the deformation field.

V =?

→

?I t ?I xyz

(2.19)

2.3 Objectives of the Dissertation

The goal of this thesis is to develop automatic rigid and deformable registrations to align functional MR rat brain images and deformed soft-tissue images such as those associated with breast cancer imaging.

In this thesis, image registration systems with the rigid model and deformable model were designed, implemented and validated.

For rigid model (rigid-body and affine model) registration system, an innovative method was proposed to calculate the gradient of mutual information by using finite difference approach. This approach is to evaluate the derivative of mutual information with partial volume interpolation. Compared with the other methods, it can provide the

29

accurate derivative of mutual information while improving computational efficiency greatly.

Most registration systems were built on the conventional multi-dimensional optimization techniques to search for maximum mutual information of two image volumes. However, because of image distortion, interpolation methods, bin size of histogram and other reasons, the registration process may contain many local maxima. Conventional optimization methods require a good initial start location. Sometimes, they fail due to entrapment of local maxima. A global optimization strategy using the genetic algorithm (GA) was implemented to ensure the convergence to a solution from almost any starting point. Three registration systems with non-gradient method (downhill simplex), gradient method (Quasi-Newton method) and global method (genetic algorithm) were designed and implemented. Experiments were conducted and compared with images of different dimensions and voxel resolutions on these systems. Coupling with mutual information with GA strategy was proved to be a robust and accurate strategy for image registration.

For the female breast cancer images the registration systems were also designed with deformable models (linear elastic model and viscous fluid model). Squared sum of intensity difference as the external force was selected to drive the deformation process. The systems were validated by female breast MR images and synthetic images.

30

Chapter 3 Rigid Registration

The image registration is the process to search for the best alignment that transforms the points in one image to the corresponding points in another image. In the rigid registration the material of subject is hard and its movement is approximately described as the combination of translations and rotations.

Two image sets are required to input for registration: the moving image (subject image) and the fixed image (reference image). Subject space and reference space are three-dimensional spaces defined by their dimensions and spacings in x, y and z directions.

To measure the dependence of two images, four major operations are involved: (1) transforming the coordinates of subject image into the reference space; (2) generating new image with interpolation within the reference space; (3) comparing the new image with the reference image through similarity measure; and (4) adjusting the transformation parameters according to the goodness of fit measure until a good alignment is achieved. The similarity measure (objective function) will be maximized (or minimized) in the optimization process to find the best alignment.

Both rigid body model and affine model have a matrix representation with homogenous coordinate as shown in formula (3.1), which is a succession of rotation, translation and scaling.

31

? x'? ?m00 ? y '? ? m ? ? = ? 10 ? z ' ? ?m20 ? ? ? ?1? ? 0

m01 m11 m21 0

m02 m12 m22 0

m03 ? ? x ? ? ? m13 ? ?? y? m23 ? ? z ? ?? ? 1 ? ?1 ?

? x? ? y? ?? ? ?z? ? ? ?1 ?

? x? ? y? = M ?? ? = Mr ?Mw ?Ms ?z? ? ? ?1 ?

(3.1)

The matrix M transforms the coordinates [ x reference space [ x '

y

z 1] from subject space into

y'

z ' 1] . It involves a series of coordinate transforms that include

world-to-world transform M w , image-to-world transform M s in subject space and worldto-image transform M r in reference space.

3.1 Rigid-body Model

World-to-world transform for rigid body model is the product of translations and rotations matrices, which is specified by

M w = T ? R y ? Rx ? Rz

in which, Translation matrix T describes the displacements [t x

(3.2)

ty

t z ] in x, y, z directions.

?1 ?0 T =? ?0 ? ?0

0 1 0 0

0 tx ? 0 ty ? ? 1 tz ? ? 0 1?

32

(3.3)

Rotation matrix R y describes the rotation about y-axis (roll).

? cos β ? 0 Ry = ? ?? sin β ? ? 0

0 sin β 1 0 0 cos β 0 0

0? 0? ? 0? ? 1?

(3.4)

Rotation matrix R x describes the rotation about x-axis (pitch). 0 ?1 ?0 cos α Rx = ? ?0 ? sin α ? 0 ?0 0 sin α cos α 0 0? 1? ? 1? ? 1?

(3.5)

Rotation matrix R z describes the rotation about z-axis (yaw).

? cos γ ?? sin γ Rz = ? ? 0 ? ? 0

sin γ cos γ 0 0

0 0 1 0

0? 0? ? 0? ? 1?

(3.6)

3.2 Affine Model

World-to-world transform for affine model is the product of translations, rotations and scalings. M w = T ? R y ? Rx ? Rz ? S in which, Scaling matrix S describes the scaling ratios about the origin in x, y, z directions.

?s x ?0 S=? ?0 ? ?0

(3.7)

0 sy 0 0

0 0 sz 0

0? 0? ? 0? ? 1?

(3.8)

33

3.3 Coordinate System Transforms Image coordinate system: defined the coordinate associated with image. The

origin is located at the left up corner in the first slice of image set. The x-axis is from left to right along the column direction. The y-axis is up to down along the row direction. The z-axis is from the first slice to the last slice along the plane direction.

World coordinate system: described the movement in the real world. It is

generally defined by the RAS coordinate system. The origin is positioned at the center of FOV (field of view). The x-axis is from the left to right (L-R). The y-axis is from the posterior to anterior (P-A). The z-axis is from the inferior to superior (I-S).

Figure 3 -1

Definitions of world and image coordinate systems.

34

3.3.1 Image-to-world Transform

Image-to-world transform is performed in the subject space to map the image coordinates to world coordinates. Three-dimensional subject space is defined with dimensions [ Dsx directions. Spacing (voxel size) in x:

v sx = FOVsx Dsx

Dsy

Dsz ] , field of views [ FOVsx

FOVsy

FOVsz ] in x, y, and z

Spacing (voxel size) in y:

v sy =

FOVsy Dsy

FOVsz Dsz

Spacing (voxel size) in z:

v sz =

The image-to-world transform M s is calculated by

M s = Vs ? C s

(3.10)

in which, Center Matrix C s describes the movement of image coordinate from the origin of image coordinate system to that of world coordinate system.

? ?? 1 0 ? ? Cs = ? 0 ? 1 ? ?0 0 ?0 0 ? 0 Dsx ? 2 ? Dsy ? ? 0 2 ? D ? 0 ? sz ? 2 0 1 ? ?

(3.11)

Voxel size matrix Vs describes the voxel sizes in x, y, z directions, respectively.

35

?v sx ?0 Vs = ? ?0 ? ?0

0 v sy 0 0

0 0 v sz 0

0? 0? ? 0? ? 1?

(3.12)

3.3.2 World-to-image Transform

World-to-image transform is performed in the reference space to map the world coordinate to image coordinate. Three-dimensional reference space is defined with dimensions [ Drx directions. Spacing (voxel size) in x:

v rx = FOVrx Drx

Dry

Drz ] , field of views [ FOVrx

FOVry

FOVrz ] in x, y, and z

Spacing (voxel size) in y:

v ry =

FOVry Dry

FOVrz Drz

Spacing (voxel size) in z:

v rz =

The world-to-image transform M s is calculated by: M r = Vr ? C r in which Center Matrix C r describes the movement of world coordinate from origin of world coordinate system to that of image coordinate system.

?1 ?1

(3.13)

36

? ?? 1 0 ? ? Cr = ? 0 ? 1 ? ?0 0 ?0 0 ?

0 0 0 0

Drx ? 2 ? Dry ? ? 2 ? Drz ? 2 ? 1 ? ?

(3.14)

Voxel size matrix Vr describes the voxel sizes in x, y, z directions, respectively. ?v rx ?0 Vr = ? ?0 ? ?0 0 v ry 0 0 0 0 v rz 0 0? 0? ? 0? ? 1?

(3.15)

3.3.3 Image-to-image Transform

The overall transformation from subject space into reference space is represented by a single matrix M , which is the concatenation of world-to-image transform M r in reference space, world-to-world transform M w and image-to-world transform M s in subject space. M = Mr ?Mw ?Ms (3.16)

3.4 Mutual Information 3.4.1 Definition

Image is the collection of pixel intensities, the distribution of random variable (image intensity) from the statistical description. Mutual information is one of measures to evaluate the statistical dependence between two images.

37

Figure 3-2 depicts the concept of mutual information given two image sets. Here we have two rat brain MR images (a), which can be represented by their histograms (b). The mutual information is the common (overlapping) area under the two distributions. It will be maximized if two images are geometrically aligned.

(a)

(b) Figure 3-2 Representation of mutual information (MI). (a) MR images; (b) histograms

38

There are two situations about the dependence of two distributions. The first is that one distribution is independent of another distribution. The second is that one distribution is dependent (associated) with another distribution.

The mutual information is used to measure the strength of dependence of two distributions, which applies the information-theoretic concept of entropy. According to the information theory, entropy represents the measure of information with the probability of occurrence.

Given the random variable x and its probability mass function p x ( x) , the entropy H ( x) is defined: H ( x) = ?∑ p x ( x) log p x ( x)

x

(3.17)

For two discrete random variables x and y, the joint histogram is constructed with the entries N xy . N is the total count of possibilities. N x. is the count of possibility for x only. N . y is the count of possibility for y only. The marginal probability mass functions p x ( x) and p y ( y ) , and the joint probability mass function p xy ( x, y ) are determined by: Marginal probability of x

p x ( x) = N x. N

(3.18)

Marginal probability of y

p y ( y) =

N.y N N xy N

(3.19)

Joint probability of x and y

p xy ( x, y ) =

(3.20)

39

Correspondingly, the marginal entropies H ( x) and H ( y ) as well as joint entropy H ( x, y ) are defined: Marginal entropy of x Marginal entropy of y Joint entropy of x and y H ( x) = ?∑ p x ( x) ? log p x ( x)

x

(3.21) (3.22) (3.23)

H ( y ) = ?∑ p y ( y ) ? log p y ( y )

y

H ( x, y ) = ?∑ p xy ( x, y ) ? log p xy ( x, y )

x, y

Conditional entropy of x given y

H ( x | y ) = ?∑ p xy ( x, y ) ? log p xy ( x | y ) = ?∑ p xy ( x, y ) log

x, y x, y

p xy ( x, y ) p y ( y)

(3.24)

Conditional entropy of y given x H ( y | x) = ?∑ p xy ( x, y ) ? log p xy ( y | x) = ?∑ p xy ( x, y ) log

x, y x, y

p xy ( x, y ) p x ( x)

(3.25)

The strength of dependence between x and y is measured by their mutual information:

MI = H ( x) + H ( y ) ? H ( x, y ) = H ( x) ? H ( x | y )

= H ( y ) ? H ( y | x) The mutual information is also expressed as: MI = ∑ p xy ( x, y ) ? log

x, y

(3.26)

p xy ( x, y ) p x ( x) ? p y ( y )

(3.27)

Normalized mutual information [27] is defined as

NMI =

H ( x) + H ( y ) H ( x, y )

(3.28)

40

Figure 3-3 illustrates the relationship between the entropy and mutual information.

Figure 3-3 The relation between entropy and mutual information. Source: [61] “Elements of Information Theory”

3.4.2 Gradient of Mutual Information

To maximize mutual information via gradient-based optimization approaches, one needs accurate gradient of mutual information. Wells et al presented [36] the Parzen window function to construct the smooth function of mutual information from the samples. For this method the settings of window function will affect the accuracy of image registration greatly. Maes et al [37] derived analytical expressions for the gradient of mutual information with partial volume interpolation.

In this research a finite difference approach was proposed to evaluate the derivative of mutual information with partial volume interpolation and successfully applied it in Quasi-Newton optimization for image registration.

41

The joint histogram was constructed by the partial volume interpolation. This interpolation strategy has the mutual information vary smoothly as a function of transformation parameters. Therefore, a small transformation parameter adjustment results in a well-behaved small change of mutual information.

The finite difference method was used to approximate the derivative for each transformation parameter. According to the theory of finite difference method, a function

f ( x) is deployed by Taylor expansion: ?f ( x) ?x 2 ? 2 f ( x) f ( x + ?x) = f ( x) + ?x ? + ? + O(?x 3 ) 2 2 ?x ?x

(3.29)

If the high-order terms is ignored, then Forward Difference

?f ( x) f ( x + ?x) ? f ( x) + O(?x) = ?x ?x

Backward Difference

(3.30)

?f ( x) f ( x) ? f ( x ? ?x) + O(?x) = ?x ?x

Center Difference:

(3.31)

?f ( x) f ( x + ?x) + f ( x ? ?x) ? 2 f ( x) = + O(?x 2 ) ?x 2?x

(3.32)

The affine model was 4 by 4 matrix involving translations, rotations, and differential scaling in all 3 directions, independently. The finite difference formulation provides accurate derivative information and computation efficiency for a rapid

42

registration technique. The affine transformation model required 9 evaluations of the mutual information (one for each degree of freedom); the rigid model needs only 6 evaluations.

3.5 Interpolation

To map the voxel from subject space into the reference space, the image-to-image transformation with formula (3.16) is applied on the each voxel of subject image. The three dimension reference space is defined by dimensions [ Drx and z directions, respectively. In x direction: 0 ≤ I r < Drx In y direction: 0 ≤ J r < Dry In z direction: 0 ≤ K r < Drz Similarly, the three-dimension subject space is defined by dimensions [ Dsx Dsy Dsz ] in the x, y, and z directions, respectively. In x direction: 0 ≤ I s < Dsx In y direction: 0 ≤ J s < Dsy In z direction: 0 ≤ K s < Dsz The process of mapping the coordinates from subject space into reference space is shown with the pseudo code in Figure 3 -4. Dry Drz ] in the x, y,

43

For K s = 0, Dsz For J s = 0, Dsy

// Loop all the slices // Loop all the columns

For I s = 0, Dsx // Loop all the rows

[I s , J s , K s ] = M ? [I s , J s , K s ]

' '

' ' '

// Apply the transformation

'

If 0 ≤ I s < Drx && 0 ≤ J s < Dry && 0 ≤ K s < Drz // Check if within reference space

R( I s , J s , K s ) = Interpolation_In_Reference_Space ( I s , J s , K s )

' ' ' ' ' '

End End Figure 3 -4 The pseudo code for coordinate mapping.

Subject Image

Reference Image

Figure 3 -5

2D example for coordinate mapping.

Figure 3-5 shows a 2D example of coordinate mapping. The new coordinate in the reference space will not coincide with the grid point after the transformation. Therefore,

44

it is necessary to compute the intensity value at an arbitrary point in the reference space with interpolation technique.

There are a variety of interpolation methods available: nearest-neighbor interpolation, trilinear interpolation, partial volume interpolation, B-spline interpolation and so on. Their qualities vary from the low to high, which affect the accuracy of registration directly.

3.5.1 Nearest-neighbor Interpolation

Nearest-neighbor interpolation is the simplest but least accurate method of interpolation. The voxel closest to interpolation point amongst eight neighboring voxels is identified and its intensity value is assigned to the interpolation point. The intensity is the piecewise function with the middle point as the separator between the grid points.

R(i,j+1,k+1) R(i+1,j+1,k+1)

R(i,j,k+1)

R(i+1,j,k+1)

R(i,j+1,k)

R(i+1,j+1,k)

R(i,j,k)

R(i+1,j,k)

Figure 3 -6

Nearest-neighbor interpolation.

With the nearest-neighbor interpolation the joint histogram is constructed by: (1) calculating the intensity for point after transformation with the nearest-neighbor

45

interpolation within the reference space. (2) the joint histogram of these paired points will be updated by 1. The pseudo code is shown in Figure 3-7. Find_Minimum_Distance ( Ms, Ri ) = Rm R ( Ms) = Rm Joint histogram: h( S ( s), R( Ms))+ = 1 Figure 3 -7 The pseudo code of nearest-neighbor interpolation.

3.5.2 Trilinear Interpolation

Trilinear interpolation assumes the intensity varies linearly with the distance between the grid points along each direction. It considers all the contributions to interpolation point from the eight neighboring pixels. The distances are different between interpolation point and each of neighboring voxels. Therefore, the contribution (weight) from each voxel is different. Trilinear interpolation sums up the contribution (weight) from each neighboring voxel as the intensity value of interpolation point. Figure 3-8 shows the trilinear interpolation in 3D space.

R(i,j+1,k+1) R(i+1,j+1,k+1)

R(i,j,k+1)

R(i+1,j,k+1)

R(i,j+1,k)

R(i+1,j+1,k)

R(i,j,k)

R(i+1,j,k)

Figure 3 -8

Trilinear interpolation

46

The new coordinates are designated as Ms = [ I s , J s , K s ] after mapping from subject space into reference space. In the reference space, I s falls into the interval between x[i ] and x[i + 1] . J s falls into the interval between y[ j ] and y[ j + 1] . K s falls into the interval between z[k ] and z[k + 1] . That is, x[i ] ≤ Is' ≤ x[i + 1]

' '

'

'

'

'

y[ j ] ≤ Js' ≤ y[ j + 1] z[k ] ≤ Ks' ≤ z[k + 1]

The distance Tx Ty

Tz

= Is' ? i = Js' ?

j

= Ks ' ? k

The weight from each voxel is calculated as follows: R0 = R[i ][ j ][k ]

R1 = R[i + 1][ j ][k ] R2 = R[i ][ j + 1][k ]

w0 = (1 ? Tx ) ? (1 ? T y ) ? (1 ? Tz ) w1 = Tx ? (1 ? T y ) ? (1 ? Tz ) w2 = (1 ? Tx ) ? T y ? (1 ? Tz ) w3 = Tx ? T y ? (1 ? Tz ) w4 = (1 ? Tx ) ? (1 ? T y ) ? Tz w5 = Tx ? (1 ? T y ) ? Tz w6 = (1 ? Tx ) ? T y ? Tz w7 = Tx ? T y ? Tz 47 (3.33)

R3 = R[i + 1][ j + 1][k ]

R4 = R[i ][ j ][k + 1]

R5 = R[i + 1][ j ][k + 1] R6 = R[i ][ j + 1][k + 1] R7 = R[i + 1][ j + 1][k + 1]

With the trilinear interpolation the joint histogram is constructed by: (1) calculate the weights of eight neighboring voxels with the formula (3.33). (2) the joint histogram of these paired points will be updated by 1. The pseudo code is shown in Figure 3-9. The weight:

∑w

n =0

7

n

=1

The intensity value of interpolation point is: R ( Ms) = ∑ Rn ? wn

n =0 7

The joint histogram is updated by:

h( S ( s), R( Ms))+ = 1

Figure 3 -9

The pseudo code of trilinear interpolation.

3.5.3 Partial Volume Interpolation

The partial volume interpolation is the technique [37] to construct the joint histogram without introducing new intensity values. Rather than interpolating the intensity value in the reference space, partial volume interpolation distributes the contribution from image intensity S ( s) over the neighboring eight voxels within the reference space. Eight entries of the joint histogram are updated by adding the corresponding weight at the same time. The calculation of weights from eight voxels is identical to the trilinear interpolation.

48

With partial volume interpolation the joint histogram is constructed by: (1) calculate the weights of eight neighboring voxels with the formula (3.33). (2) eight entries of joint histogram corresponding to eight paired points will be updated by the weight. The pseudo code is shown in Figure 3-10.

The weight:

∑w

n =0

7

n

=1

The joint histogram is updated by: ?n : h( S ( s ), R( Ms))+ = wn Figure 3 -10 The pseudo code for partial volume interpolation. This interpolation strategy has the mutual information vary smoothly behaved as a function of registration parameters. As a consequence, small transformation parameter adjustments results in well behaved small mutual information changes.

3.6 Multi-dimensional Optimization Techniques

To find the best alignment between the subject image and reference image, multidimensional optimization techniques is applied to optimize the similarity measure (objective function) by adjusting the transformation parameters.

49

3.6.1 Downhill Simplex Method

Nelder-Mead simplex method [62] starts with the initial simplex defined by ( N + 1 ) points and will optimize the transformation parameters of all the points at the same time. The starting point is P0 , followed by other N points Pi = P0 + λei

(3.34)

in which, λ is the constant to along each vector direction. ei are the N unit vectors to define a set of directions. N is the problem size (number of parameters).

The simplex algorithm searches for the minimum value through a series of operations: reflection, reflection and expansion, contraction and multiple contractions.

high low

Figure 3 -11 The initial simplex.

Reflection: moving the highest point of the simplex through the opposite face of

simplex to a lower point.

50

low

reflection

high low

Figure 3 -12 Reflection away from the highest point.

Reflection and expansion: if the value of reflection point is less than the lowest

point, then expand the distance by 2 along reflection direction.

expansion low reflection

high low

Figure 3 -13 The reflection and expansion away from the highest point.

Contraction: if the value of reflection point is between the second-highest and

highest values, the simplex will contract itself in one direction.

51

reflection contraction

high low

Figure 3 -14 Contraction in one direction from the highest point.

Multiple contractions: if the contraction point is greater than highest point, the

simplex contracts itself in all directions, pulling itself in around lowest (best) point.

multiple reflection

high low

Figure 3 -15 Contractions in all directions towards the best point. Convergence is declared if: (1) the difference between lowest and highest value at the vertices of the simplex is less than the threshold. (2) The maximum number of iteration is reached without the convergence. (3) The objective function (MI) cannot get improved with 5 iterations.

52

1. Set N + 1 points, P 1, P 2 ,...P n +1 , to define the initial simplex. 2. While (iteration < Max_iteration) { Evaluate the function at these N + 1 points. Phigh is the point having the highest value. Plow is the point having the lowest value. Psec ond is the point having the second highest value. If fabs ( f ( Phigh ) ? f ( Plow )) < tolerance Break; Else if Psum = ∑ Pi

i =1 n +1

// convergence

// Reflection 2 (n + 2) Preflection = ? Psum ? ? Phigh n n If f ( Preflection ) < f ( Plow ) Pexp ansion = // Expansion

?1 1 + 2n ? Phigh ? Psum + n n

Else if f ( Preflection ) > f ( Psec ond ) && f ( Preflection ) < f ( Phigh ) // Contraction in one direction 1 1+ n Pconstraction = ? Phigh ? Psum + 2n 2n If f ( Pcontraction ) ≥ f ( Phigh ) // Contraction in all directions For i = 1, N + 1 // all the points Pi = 0.5 * ( Pi + Plow ) End End } Figure 3 -16 The pseudo code for downhill simplex method [62].

53

3.6.2 Quasi-Newton

Quasi-Newton method [62] is an efficient gradient-based multi-dimensional optimization method. It constructs and updates an approximation of Hessian matrix H instead of calculating it directly, which involves a lot calculation used in the Newton type methods.

Function f (x) can be approximated by its Taylor series, that is,

→ → → → → → → 1 → → f ( x ) = f ( x i ) + ( x ? x i ) ? ?f ( x i ) + ( x ? x i ) ? A ? ( x ? x i ) 2

→ → → →

(3.35)

?f ( x ) = ?f ( x i ) + A ? ( x ? x i )

(3.36)

Using Newton’s method leads to:

→

x ? xi = ? A ?1 ? ?f ( xi )

→

→

(3.37)

The main idea of Quasi-Newton method is how to build the computable approximation A-1 for Hessian matrix. The iteration step becomes:

xi +1 = xi ? A ?1 ? [?f i +1 ? ?f i ]

→

→

(3.38)

There are two well-known implementations for Quasi-Newton methods: Davidson-Fletcher-Powell (DFP) algorithm and Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. The main difference of two approaches is the way on how to update the Hessian matrix A ?1 during the iteration process. BFGS provides the formulation for updating Hessian matrix:

54

H i +1

(?f i +1 ? ?f i ) ? (?f i +1 ? ?f i ) T = Hi + (?f i +1 ? ?f i ) T ? ( xi +1 ? xi ) ?

?

H i ( xi +1 ? xi ) T ? ( xi +1 ? xi ) ? H i ( xi +1 ? xi ) T ? H i ? ( xi +1 ? xi )

T

(3.39)

3.6.3 Genetic Algorithm (GA)

Different from the previous two classical methods, genetic algorithm (GA) [63] [64][65][66][67][68][69][70] is a global optimization method based on the biological metaphor on a group of samples. It follows the principle of Darwinian natural selection (survival of the fittest).

There are three basic biological operators on the group of samples:

Selection: selects the individuals from the population for reproduction. The

principle of selection is based on the fitness of individual. The individual with higher fitness value has the more chance to participate the reproduction.

Crossover: randomly exchanges some part of parents at the crossover point to

generate the new individuals. If we have two parents (genome), parent A is expressed as [011011] and parent B as [111101]. When the crossover point is randomly chosen to be first bit, two new individuals will be generated: [111011] and [011101].

Mutation: this operation is to randomly flip some parts of parent to generate new

individual. Mutation generally takes place with small probability, which is useful to keep

55

away from the local optima during the optimization process. If parent A is selected to do mutation at the second bit, the offspring will be generated as [101011].

The general workflow of a genetic algorithm is shown on Figure 3-17, which is described as follows: 1. Randomly generate an initial population. The population of individuals is created among the multi-dimensional search space.

2. Evaluate the fitness of initial population. Mutual information is selected as fitness function for the registration process.

3. Repeat the following natural selection operation until the termination measure is satisfied. (a). the selection process identifies individuals as the parents based on the their fitness to participate the reproduction. The individual with the largest fitness value in current population will be selected as a parent at default.

(b). the selected parents will take part in the reproduction to create new individuals with crossover probability.

(c). the selected parents will architecture-alter some parts with mutation probability to generate the new individual.

56

(d). evaluate the fitness of current population including the parents and new individuals, and update the population based on the fitness while preserving the size of population.

(e). once the termination criteria are satisfied, the best individual evolved from the population. If not, go back to step (a) and repeat the whole process.

For medical image registration, the transformation parameters are optimized to find the beat alignment between two images. The transformation parameters of rigidbody model are expressed as a vector [Tx , T y , Tz , R x , R y , R z ] in multi-dimensional space. The transformation parameters of affine model are represented as

[Tx , T y , Tz , R x , R y , R z , S x , S y , S z ] . They are similar to the expression of genome which consists of some genes. User specifies the search space for each parameter of transformation model. The range of each parameter is specified in section 5.2. Mutual information is the fitness function (objective function) for the registration process.

There are three popular crossover operators for genetic algorithm: (1) Unimodal normal distributed crossover operator ( UNDX ): the offspring are normally distributed around the mean vector determined by parents.

57

Start GA G=0 Generate initial population

Evaluate the fitness of population G=G+1 Select parents

Crossover

Mutation

Evaluate the fitness

Update the population

No

Maximum iteration is reached or the fittest value cannot get improved?

Yes Output

Figure 3-17 The workflow of genetic algorithm.

58

(2) Simplex crossover operator ( SPX ): the offspring are uniformly distributed around the mean vector within the predefined space.

(3) Parent-centric crossover operator ( PCX ): the offspring have more probability to be distributed around each parent.

Figure 3-18 shows three crossover operators: (1) UNDX , (2) SPX , (3) PCX . Since the SPX operator can produce the offspring faster than UNDX and PCX operator,

SPX operator is applied to generate the offspring for our image registration system.

(a) Figure 3-18

(b)

(c)

Three crossover operators. (a) UNDX , (b) SPX , (c) PCX . Source: KanGAL Report [64]

To improve the computational efficiency while preserving the robustness of genetic algorithm, the hybrid genetic algorithm was designed and implemented that integrates the global random search (GA) with local optimization (downhill simplex

59

method) to accelerate the registration process. The workflow of this hybrid genetic algorithm is described as follows. (1) Generate the initial population composed of M individuals. They are generated randomly within the user-specified search space. To utilize the local downhill simplex method, the population size M will be the product of point number (degree+1) of initial simplex and number of groups N .

M = N * (deg ree + 1)

(3.40)

in which, M is the population size. Degree is the freedom of transformation model. N is the number of group. For rigid body registration, the population size may be selected as the number like 14, 21, 28, which are 2, 3, 4 times of point number (7) of simplex.

(2) Begin the new generation. The population will be divided into N groups. N simplex are created to search for the maxima locally. The N local maxima will be generated from the population and selected as parents.

(3) Generate the M offspring by SPX crossover among N parents. The centroid (mean vector) of N parents will be calculated and M offspring will be uniform deviate random number within the space defined by the centroid and range settings. The centroid of N parents is calculated by: The new individual is created by:

ci =

1 N

∑v

i =1

N

i

(3.41) (3.42)

vi = ci + ri

60

in which, vi is the parameter i of transformation vector. ci is the centroid (mean value) of transformation parameter vi . ri is the uniform deviate random number around mean vector within the predefined space.

(4) Mutate the parents to produce N offspring by randomly selecting one parameter from transformation vector of each parent, replacing it with uniform deviate random number around mean vector within the predefined space while keeping other parameters unchanged. For each parent, the randomly selected parameter i :

vi = ri

(3.43)

in which, vi is the selected parameter i of transformation vector. ri is the uniform deviate random number around mean vector within the predefined space.

(5) Evaluate the fitness function (mutual information) of the new population including parents and new individuals (2 N + M ) , sort the individuals and keep

N individuals based on fitness to form new population.

(6) If maximum iteration number is reached or the difference between the fittest value of old population and new population is less than tolerance, then the program will be terminated and output the final transformation parameters. (7) If not, then go back to step (2) to repeat the whole process. Figure 3-19 shows the workflow of hybrid genetic algorithm.

61

Start GA G=0 Generate initial population M G=G+1 Population divided into N groups (simplex) Efficient local search by downhill simplex

Calculate the centroid of N parents

Determine N parents

Generate the M offspring randomly by mean-centric SPX crossover

Mutate N parents

Update the population

Yes

The improvement of fittest individual is greater than tolerance

No

Output No The maximum number of iteration is reached Yes

Figure 3-19 The workflow of hybrid genetic algorithm.

62

3.7 Multi-Resolution Speedup

The evaluation of mutual information, the objective function of optimization, is a time-consuming task. Multi-resolution technique is an efficient approach to accelerate the registration process and avoid local maxima.

The whole registration process is divided into several levels to build up the image pyramid, a hierarchical representation shown in Figure 3-20. The different parameters were set for each level: termination criteria and sampling rate. Through this strategy, the registration process can be realized from the coarse level to fine level. At the coarse level, it is relatively easy to find the approximate location of maxima. At the fine level, the maximum is searched with the full resolution to ensure the accuracy. The different sampling rate is selected along each dimension of space. For different optimization techniques, the sampling rates may be [441, 221, 111], [331, 221, 111] and so on.

3.8 Implementation 3.8.1 3D Registration System

The complete 3D registration system is designed with 4 major components: (1) GUI (graphical user interface): to receive the parameters of registration (tolerance, the selection of transformation model) defined by users. (2) Registration component: to provide the ability for image registration on rigidbody model and affine model, and output the final transformation matrix for best alignment.

63

Registration on level 1

Registration on level 2

Registration on level 3

Subject Image Multi-level

Final Transform

Reference Image Multi-level

Figure 3 -20 Multi-resolution registration with 3 levels. Source: The ITK Software Guide [71]

(3) Reslice component: to generate new image volume within the reference space by applying the transformation matrix output from registration component on subject image.

(4) Validation component: to evaluate the goodness of registration with the similarity measure quantitatively and with the visual check qualitatively.

64

GUI Rigid Registration Registration System Reslice SSD Quantitative Validation Correlation Coefficient Visual Assessment Qualitative Landmark Assessment

Figure 3 -21 The components of 3D registration system.

3.8.2 Registration Framework

Deformable

The component of registration consists of four parts: (1) Similarity measure: mutual information is selected to measure the statistical dependence between two images. And it is the objective function of optimization process.

65

(2) Optimization technique: to search for the maximum value of objective function by adjusting the transformation parameters within the multi-dimensional space.

(3) Interpolation: to determine the intensity value at the interpolation point within reference space after rigid transformation.

(4) Transformation: the rigid or deformable movement to map the points of the image from subject space into reference space.

Figure 3 -22 The constitution of registration component. Source: The ITK Software Guide [71]

3.8.3 Application on Functional MRI Analysis

The rigid body and affine registration systems were integrated into our application of functional MRI analysis. They provide an accurate and convenient registration work of the subjects within the study group, which is a vital step to get an accurate map of brain activation from fMRI studies.

66

Figure 3-23 shows the graphical user interface of mutual information registration integrated into the application for fMRI analysis. During the fMRI analysis, images for the group of subjects are acquired and loaded into the fMRI module. Mutual information registration is applied for the automatically register all subjects to the standard image. User can select two models of registration: ‘Rigid-6DOF’ and ‘Affine-9DOF’. ‘Rigid6DOF’ button refers to the rigid body model that registers images by translations and rotations. ‘Affine-9DOF’ button refers to affine model that registers images by translations, rotations and scalings. The registration process will start when ‘Align’ button is pressed. The time of registration varies with the dimensions and FOV of the specified images as well as the type of model. Generally it takes 5 minutes to align a pair of images. The output transformation matrix will be applied on all the subjects after the registration process is done. User can visually check the results of registration by overlapped standard image and subject image displayed in three image windows (axial, coronal and sagittal).

3.9 Validation

Three registration methodologies were implemented and validated with the configuration of objective function and optimization technique: System 1: the function of mutual information combined with downhill simplex (DHS) optimization technique.

67

Figure 3 -23 The mutual information registration in application of fMRI analysis. System 2: the derivative of mutual information combined with Quasi-Newton (QSA) optimization technique. System 3: the function of mutual information combined with hybrid genetic algorithm (GA) optimization technique.

The Table 3.1 indicates the features (optimization type, objective function, accuracy, speed, interpolation method, transformation model, and endian type) provided by these three different registration systems. Chapter 5 demonstrates the results from a series of 3D image sets experimented on three systems.

68

Table 3.1 Feature

Features of three systems for rigid registration. System 1 DHS System 2 QSN Local Derivative of mutual information Quasi-Newton Good Fast System 3 GA Global Mutual information Genetic Algorithm Good Fast for global optimization

Optimization Objective function

Local Mutual information

Optimization strategy Accuracy Time

Downhill simplex Good Fast

Interpolation Model

Partial Volume Rigid-body & Affine

Partial Volume Rigid-body & Affine Big & Little

Partial Volume Rigid-body & Affine Big & Little

Endian

Big & Little

69

Chapter 4 Deformable Registration

Rigid body and affine model are widely used in the medical imaging applications to register the human brain or brain image of rodent animals. During the matching process the shape and form of anatomical structure keep unchanged.

However, these two models cannot describe the behavior of deformable tissue such as: the female breast image, lung of human images and so on. A deformable model needs to be built to depict the physical behavior under some kind of external force mathematically.

The deformable model in behavior can be described by some form of partial differential equation (PDE). The deformable registration of soft tissue images is the process to (1) solving the PDE to calculate the deformation field at each time step. (2) applying the deformation field on the reference image to warp it into subject image.

For the deformable registration with linear elastic model and viscous fluid model were applied as the motivation of the physical models. However, these models are not valid for large strain case. Therefore, the number of iterations for convergence is large for deforming soft tissue. For these two models, the homogeneous coefficients ? and λ are applied for image registration.

70

4.1 Deformable Registration with Linear Elastic Model 4.1.1 Navier Linear Elastic Equation

The physical behavior of elastic model is described by Navier linear elastic equation [72], which is defined as:

?? 2 u + ( ? + λ )?(? ? u ) + f = 0

This equation can be deployed in x and y direction. In x direction

→

→

→

(4.1)

? ??

? ? 2u x ? 2u x ? ? ? 2u x ? 2u y ? + + + ? ( ? λ ) ? ? 2 + ?+ f 2 ?x?y ? ?y 2 ? ? ?x ? ?x

x

=0

(4.2)

The finite-difference representation of equation (4.2) can be written as:

? (2? + λ ) x ? u i +1, j + u ix?1, j ? 2u ix, j + 2 ? u ix, j +1 + u ix, j ?1 ? 2u ix, j 2 h h

[

]

[

]

(4.3)

+

(? + λ ) y ? u i +1, j +1 + u iy?1, j ?1 ? u iy?1, j +1 ? u iy+1, j ?1 + f i ,xj = 0 2 4h

[

]

After the simplification, the deformation at the time step n is:

u ix, j =

(2? + λ ) ? ? u ix+1, j + u ix?1, j + ? u ix, j +1 + u ix, j ?1 + (6? + 2λ ) (6? + 2λ )

[

]

[

]

+

(? + λ ) h2 f i ,xj ? u iy+1, j +1 + u iy?1, j ?1 ? u iy?1, j +1 ? u iy+1, j ?1 + 4( 6 ? + 2 λ ) ( 6 ? + 2λ )

[

]

(4.4)

In the successive-over-relaxation (SOR) iterative method, w is defined as the over relaxation factor. The updating form of equation (4.4) from time step n to n+1 is derived in x direction by: 71

u ix, (jn +1) = u ix, (jn ) + ?u ix.,(jn )

? (2? + λ ) ? ? 1) ) x ( n +1) = u ix, (jn ) + w ? ? ? u ix+(1n, )j + u ix?(1n, + + ? u ix, (jn +? +1 + u i , j ?1 j (6? + 2λ ) ? (6 ? + 2λ ) ?

[

]

[

]

? (? + λ ) ? h2 ) y ( n +1) y ( n +1) y(n) + w?? ? u iy+(1n + ? ? + u u u f i ,xj ? u ix, (jn ) ? , j +1 i ?1, j ?1 i ?1, j +1 i +1, j ?1 ( 6 ? + 2λ ) ? 4( 6 ? + 2λ ) ?

[

]

(4.5)

Similar expression in y direction can be derived by:

u iy, (j n +1) = u iy, (j n ) + ?u iy.,(jn )

? (2? + λ ) ? +1) ) y ( n +1) = u iy, (j n ) + w ? ? ? u iy+(1n, )j + u iy?(1n + ? u iy, (j n ,j +1 + u i , j ?1 (6? + 2λ ) ? (6? + 2λ ) ? (? + λ ) h2 1) x ( n +1) x(n) u u f i ,yj + w?? ? u ix+(1n, )j +1 + u ix?(1n, + ? ? + j ?1 i ?1, j +1 i +1, j ?1 4 ( 6 ? 2 λ ) ( 6 ? 2 λ ) + + ?

[

]

[

]+? ?

?

? ? u iy, (j n ) ? ?

[

]

(4.6)

4.1.2 Image Registration with Linear Elastic Model

The registration process of linear elastic object is imagined as applying the external force on the elastic object and warping it with elastic constraints.

Two spaces are defined: reference space R and subject space S . Each voxel within the reference space is tracked by it position at different time step. Through the concatenation of deformation at each time step, a voxel at the position of x ∈ R and its grayscale intensity value will be mapped into the S space: R (T ( x)) = S ( x ) .

72

The registration process is to find the deformation field which maps the voxel in one image space into the voxel of another image space by minimizing the similarity measure between two images. The sum of intensity difference was selected as the cost function for optimization. When the sum of intensity difference at the corresponding position is minimized, two images will be aligned with local deformation.

The first order derivative of the cost function, the gradient of image intensity, works as the external body force to drive the deformable registration.

f ( x, u ( x, t )) = ?[R( x ? u ( x, t )) ? S ( x)] ? ?R | x ?u ( x ,t )

(4.7)

In this work the equation (4.1) was solved by the finite difference approach with successive over-relaxation (SOR) iterative method on each image grid at different time step. The procedure to solve the elastic linear PDE becomes: (1) t i = 0 and u ( x,t i ) = 0. (2) The drive force f ( x, u ( x, t i )) is calculated through the formula (4.7). (3) Solve the elastic linear equation (4.5) and (4.6) with SOR iterative solver to obtain the deformation field u ( x, t i ) at the time step t i . (4) Update the deformation field and apply this deformation to warp the reference image. (5) Repeat this process until the sum of intensity difference between two images is minimized.

73

4.1.3 Experiment of Linear Elastic Image Registration

The system of elastic registration was implemented in C on PC with the configuration (Pentium 4 Celeron, 2.6 Ghz, Windows XP OS). Female breast cancer MR images are used to validate the system of elastic registration.

Figure 4-1 shows the results of elastic registration on female breast MR images. The images have 256x256 in-plane dimensions. The computation time of mapping two images was about 5 hours. The number of iterations for warping images was approximately 400 times.

Figure 4–1 The elastic registration of female breast image with ?=1.0 and λ=0.1. (1) reference image (2) subject image (3) deformed reference image

Figure 4-2 demonstrates the deformation process of image grid for elastic registration on female breast images. By concatenating the deformation field at each time step and applying it on reference image, reference image warps itself into the subject image under body force.

74

Figure 4–2

The deformation field of reference image output at every 100 iterations.

4.1.4 Limitations

Image Registration with linear elastic model can model the deformation of elastic object under the external force and cover the shape difference between images. However, the linear elastic model has some limitations: (1) It works only for the linear elastic deformation, which is not valid for large strain case.

75

(2) In this test case, we only consider the motion of image within 2D plane under body force. When converting linear elastic equation from 3D to 2D case, the assumptions of plane strain need to be made. The strains in z direction are equal to zero. There is no displacement in z direction.

(3) The female breast consists of fat, glandular and other tissues. In this preliminary case, the lame’s coefficients ? and λ are homogeneous for all the tissues within female breast.

(4) It cannot model the large deformation since elastic energy increases linearly with the strength of the external body force.

4.2 Deformable Registration with Viscous Fluid Model 4.2.1 Navier-Stokes Equation

In the Eulerian reference frame, the behavior of viscous fluid can be described by Navier-Stokes equation [44]:

?? 2 v( x, t ) + (λ + ? )?(? ? v( x, t )) + f ( x, t ) = 0

(4.8)

in which, v( x, t ) is the velocity field. f ( x, t ) is the external force. λ and ? are viscosity constants. At each time step velocity field is calculated in viscous fluid registration rather than the deformation field in elastic registration. Then the deformation field is derived from velocity field by:

76

?u ( x, t ) = v ( x , t ) ? v ( x , t ) ? ? u ( x, t ) ?t

The perturbation

(4.9)

P ( x, t ) = v ( x , t ) ? v ( x , t ) ? ?u ( x, t )

(4.10)

The derivate of grayscale intensity works as the extern body force to drive the registration process.

f ( x, t ) = ?[R( x ? u ( x, t )) ? S ( x)] ? ?R | x ?u ( x ,t )

(4.11)

4.2.2 Viscous Fluid Image Registration

The sum of intensity difference is selected to be similarity measure in the registration process. It will be minimized if two images are aligned with local deformation. The general framework of viscous fluid registration is: (1) When t i = 0, the u ( x, t i ) = 0 , v( x, t i ) = 0 . (2) Derive the intensity force by using the formula (4.11). (3) Solve the PDE (4.8) to obtain the velocity field v( x, t i ) at time step t i . (4) Calculate the perturbation P ( x, t i ) with the formula (4.10). (5) The time step ?t is selected to satisfy ?t ? | P( x, t i ) |< u _ max , u_max is the limit of deformation in each iteration. (6) Calculate the deformation field u ( x.t i +1 ) with the formula (4.9). (7) Concatenate the deformation field and apply it to deform the reference image (8) If the jacobian of deformation field is less than 0.5, regrid the deformed reference image.

77

(9) Go back to step (2) and continue above operations until the sum of intensity difference is minimized

4.2.3 Experiment of Viscous Fluid Image Registration

The experiment with same breast images was conducted with viscous fluid registration. Viscous fluid registration allows for the large deformation and more degrees of variability. Therefore, the computational time of viscous fluid registration is much less than that of elastic registration to achieve the desired deformation. The total time of mapping two breast MR images was about 50 minutes.

The viscous fluid registration was also validated by the synthetic image. In this experiment two images were generated: circle and rectangle. The circle and rectangle have nearly same area. Each of them was divided into two parts and assigned with different intensity values. The shape and form of two synthetic images were shown in Figure 4-3.

Figure 4–3 Experiment on the synthetic image circle and rectangle with ?=1.0 and λ=0.1. (1) reference image (2) subject image (3) deformed image

78

The figure 4-4 demonstrates the concatenation of deformation process to warp the circle into rectangle. The result of registration exhibits the powerful ability of deformation underlying two images.

Figure 4 -4

4.3 Discussion

The deformation process at different time steps.

There are some limitations for deformable registration. The formula (4.11) is used to calculate the driving force. It consists of two parts: the first part is the intensity

79

difference for the corresponding space between two images [R ( x ? u ( x, t )) ? S ( x)] . The second part is the gradient of intensity of subject image ?R | x ?u ( x ,t ) . For the case if two images have no overlapping area, the driving force is always equal to zero. The global movement is required to transform two images into the same location before deformable registration.

Figure 4-5 The similarity measure within fluid registration.

The sum of intensity difference is selected as the objective function in optimizing the similarity of two images. It is suitable for registering the images from same modality. If two images are from the different modalities (cross-modality), mutual information needs to be applied as the similarity measure for image registration.

80

My current registration system works on two-dimensional images. It can be extended to three-dimensional space. And the computation time is much longer. The deformable registration is time-consuming process. Some strategies will help to improve computational efficiency. (1) Applying the multi-resolution strategy to realize the registration process from the coarse level to fine level. This will speed up the registration process effectively.

(2) Apply other efficient solvers instead of the SOR method to solve the linear elastic equation and Navier-Stokes equation.

(3) Develop the serial code working on single machine into the parallel code, which distributes the computational work among a group of computers (cluster). It is an excellent strategy for improving the computational efficiency.

81

Chapter 5 Results

To validate the registration systems, numerous experiments were conducted with images of different dimensions and pixel resolutions. Registration systems were implemented in C and tested on a Pentium 4 Celeron, 2.6 Ghz PC with a Windows XP OS. The registration techniques demonstrated in this chapter are the Downhill simplex method (DHS), the Quasi-Newton method (QSN), the hybrid genetic algorithm method (GA), linear elastic model and viscous fluid model.

5.1 Rigid Registration on 3D Synthetic Images Reference image: the 3D MR image of rat brain whose parameters (modality,

dimensions, field of view, data type, endian type) are listed in Table 5-1.

Table 5-1 Image Reference-1 Modality MR

The parameters of reference image. Dimension 256x256x18 FOV (mm) 30x30x18 Data type 16 bit Endian Big

Subject images: six subject images were synthetically generated by adjusting the

transformation parameters relative to the reference image. [Tx , T y , Tz ] are translations in x, y, z directions. [ R x , R y , R z ] are the rotations around x, y, z directions, [ S x , S y , S z ] are scaling ratios in x, y z directions. The length unit is pixel for translation and degree for

82

rotation. Table 5-2 indicates the spatial relations between the reference image and subject images.

Table 5-2 Operations Subject 1 Subject 2 Subject 3 Subject 4 Subject 5 Subject 6

The relations between reference image and subject images.

Tx

20 15 15 15 15 15

Ty

Tz

Rz

Sx

Sy

20 20 20 20 20 3 3 3 3 5 5 5 1.2 1.2 1.2

Registration settings: For the system with Downhill simplex method, the initial

position [T x, T y , Tz ] , [ R x , R y , R z ] , [ S x , S y , S z ] were selected as [10, 10, 3] [1, 1, 1], [1, 1, 1] respectively. For the system with Quasi-Newton method were set as [10, 10, 1.2] [0, 0, 3], [1, 1, 1]. For the system with genetic algorithm, the range of transformation parameters was set by users: [-20, 20] pixels for translation, [-10, 10] degrees for rotation and [0.5, 1.5] for scaling ratio.

Registration result: the parameters of rigid body and affine transformation

matrix output from three registration systems were listed in Table 5-3.

83

Table 5-3 System DHS QSN GA DHS QSN GA DHS QSN GA DHS QSN GA DHS QSN GA DHS QSN GA Exp Sub 1 Sub 1 Sub 1 Sub 2 Sub 2 Sub 2 Sub 3 Sub 3 Sub3 Sub 4 Sub 4 Sub 4 Sub 5 Sub 5 Sub 5 Sub 6 Sub 6 Sub 6

The outputs from three registrations.

Tx

20.000 20.000 20.000 15.000 15.000 15.000 15.242 14.999 15.005 14.902 14.973 14.975 15.443 15.337 15.448 14.959 14.984 14.987

Ty

0.000 0.000 -0.000 20.000 19.999 20.000 19.994 20.001 19.992 19.983 19.970 19.978 18.816 19.932 20.089 20.016 19.982 19.981

Tz

Rz

Sx

Sy

-0.000 -0.000 -0.000 -0.000 0.000 -0.000 2.955 2.999 2.999 2.999 2.999 2.999 2.942 3.000 2.999 2.999 2.998 3.000

-0.000 -0.000 -0.000 0.000 -0.000 0.000 -0.002 -0.000 0.006 4.993 5.001 5.009 3.948 4.276 4.417 5.028 4.998 4.998 1.193 1.197 1.199 1.200 1.200 1.200 0.987 0.999 1.002 1.438 1.200 1.441

Discussion: In this test series, three registration systems provided accurate

registrations for single subject with image sources from same modality. However, for

84

Downhill simplex method, Quasi-Newton method, good initial search location needs to be provided within the normal range of misregistration. As the function of mutual information varies with the input image sets, the Downhill simplex method and QuasiNewton method may fail due to bad initial search point. Since the hybrid genetic algorithm generates large number of random start points within the searching space, it is more likely to find the maximum mutual information globally.

5.2 Rigid Registration on 3D Rat Brain Images Test data: this group of rat brain images has 6 subjects and their specifications

were described in Table 5-4. Each image set had (256x256) in-plane pixel resolution. However, the pixel spacing and slice counts were different. Dataset entitled Reference-2 was assigned as the reference image, and all others as subject images.

Table 5-4 Num 1 2 3 4 5 6 Name Reference-2 Subject 7 Subject 8 Subject 9 Subject 10 Subject 11

Specifications of rat brain images. Dimension 256x256x18 256x256x16 256x256x16 256x256x16 256x256x18 256x256x16 FOV (mm) 30x30x18 30x30x16 30x30x16 30x30x16 30x30x18 30x30x16 Data type 16 bit 16 bit 16 bit 16 bit 16 bit 16 bit Endian Big Big Big Big Big Big

85

Registration settings: No pre-processing (smoothing, threshold setting) was

required for registration process. All the test data were validated for six-degree rigid body registration. For the system with Downhill simplex method, the initial position [Tx , T y , Tz , R x , R y , R z , Tx ] are selected as [10, 10, 3, 1, 1, 1, 20]. For the system with Quasi-Newton method initial location are set as [10, 10, 1.2, 0, 0, 3]. For the system with genetic algorithm, the range of transformation parameters was: [-20, 20] pixels for translation, [-10, 10] degrees for rotation and [0.5, 1.5] for scaling ratio.

Registration results: three registration systems registration were validated with 5

pair of image sets. The computational time, initial mutual information and maximum mutual information of each experiment were listed in Table 5-5.

Table 5-5 The outputs from three registration systems. System DHS QSN GA DHS QSN GA DHS QSN GA Experiment 1-2 1-2 1-2 1-3 1-3 1-3 1-4 1-4 1-4 Time (sec) 369.1 429.8 2017.2 307.1 1064.0 2108.4 341.5 620.6 2696.6 Initial MI 0.325 0.325 0.325 0.325 0.325 0.325 0.317 0.317 0.317 Maximum MI 0.389 0.556 0.596 0.401 0.664 0.618 0.476 0.485 0.489

86

DHS QSN GA DHS QSN GA

1-5 1-5 1-5 1-6 1-6 1-6

341.5 295.6 2890.6 538.3 942.3 1759.4

0.400 0.400 0.400 0.457 0.457 0.457

0.469 0.446 0.453 0.613 0.562 0.624

Figure 5–1

The performance of hybrid GA, Downhill simplex and Quasi-Newton methods for test data 1-3 (reference 2 with subject 9).

Figure 5-2 shows an example of two image sets: reference 2 and subject 9. Figure 5-2 (a) displays the initial misalignment at 3 distinct regions of the brain prior to

87

registration. Figure 5-2(b) shows the 3 regions after registration. Figure 5-2(c) shows the initial misalignment in an axial, sagittal, and coronal view. Figure 5-2(d) shows the final alignment corresponding to those presented in (c). The alignment differences within the brain are graphically indistinguishable. Figure 5-3 shows the solid model views for registration results of experiment 4 on reference 2 and subject 9.

(a)

(b)

88

(c)

(d) Figure 5–2 Image views for registration results of experiment 4.

(a) 3 distinct regions of the brain prior to registration; (b) the 3 regions after registration;(c) one region of brain in three views before registration;(d) one region of brain in three views after registration.

(a)

89

(b) Figure 5-3 Solid model views for registration results of experiment 4. (a) Before registration (b) after registration

Discussion: the registration results were compared with the Downhill simplex,

Quasi-Newton and Genetic Algorithm on the same group of image sets. Figure 5-1 demonstrates the performance of GA, Downhill simplex and Quasi-Newton methods on test data 1-3 (reference 2 with subject 9). Although Downhill simplex and Quasi-Newton methods had faster registration speeds, the GA approach always produce good alignments without any user interaction The results demonstrate that as the global optimization technique, registration with GA could achieve more robust and precise alignment than other methods.

Conclusion: An image registration strategy using the global maximization of

mutual information was developed [73]. Coupling this mutual information with a GA strategy was shown to be a robust and accurate registration strategy. The registration quality was superior to the conventional alignment techniques. Significantly, the GA was not strongly sensitive to the initial start point nor was it susceptible to local maxima.

90

5.3 Deformable Registration on 2D Rat Brain Images Test data: the slice 10 of reference-2 after rigid registration was selected as the

reference image and slice 10 of subject 9 as the subject image. Each image set had (256x256) in-plane dimension and area of brain was segmented from the original image. Figure 5-4 (a) shows deformable registration on reference 2 and subject 9 (a) reference 2, (b) subject 9.

(a) Figure 5-4

(b)

Deformable registration on reference 2 and subject 9. (a) reference 2, (b) subject 9.

Linear Elastic Registration of 2D Rat Brain Images Registration settings: linear elastic model was applied for deformable

registration. The difference of image intensity drives the registration process. The SOR solver is applied to solve Navier linear elastic equation. If the termination criteria is satisfied: (1) the maximum iteration number (500 times) is reached;(2) the squared intensity difference can not get improved within 10 times, then the process of registration will be stopped.

91

Registration results: Figure 5-5 shows the linear elastic registration on reference

2 and subject 9: a) reference 2 after registration, (b) difference image (embossed) before registration, (c) difference image (embossed) after elastic registration. The difference image (b) and (c) demonstrate the shape and intensity change of reference 2 to match subject 9. The total number of iteration was 91 and the corresponding deformed reference image output at each time step

(a) Figure 5-5

(b)

(c)

Linear elastic registration on reference 2 and subject 9. (a) reference 2 after

registration, (b) difference image before registration, (c) difference image after registration.

Viscous Fluid Registration on 2D Rat Brain Images Registration settings: viscous fluid model was selected for deformable

registration. The difference of image intensity drives the registration process. The SOR solver is applied to solve Navier-Stokes equation. If the termination criteria is satisfied: (1) the maximum iteration number (500 times) is reached;(2) the squared intensity difference can not get improved within 5 times, then the process of registration will be stopped.

92

Registration results: Figure 5-6 shows viscous fluid registration on reference 2

and subject 9: (a) reference 2 after registration, (b) difference image (embossed) before fluid registration, (e) difference image (embossed) after fluid registration. The difference image (b) and (c) demonstrate the shape and intensity change of reference 2 to match subject 9. The total number of iteration was 20 and the corresponding deformed reference image output at each time step.

(a) Figure 5-6

(b)

(c)

Viscous fluid registration on reference 2 and subject 9. (a) reference 2 after

registration, (b) difference image before registration, (c) difference image after registration.

Conclusion: Both linear elastic model and viscous fluid model can effective warp

the reference 2 into subject 9 to cover the shape differences of two images, which cannot be eliminated by rigid model. Since the viscous fluid registration can accommodate the large deformation and large variability, the process of fluid registration needs less iteration than the linear elastic model.

93

Chapter 6 Conclusions

The research was focused on the development of automatic rigid and deformable algorithms for medical image registration.

One of the main advances was the rigid registration with mutual information. Mutual information is a good similarity measure for image registration. A novel strategy is presented to calculate the derivative of mutual information. It provides the accurate gradient of mutual information while improving computational efficiency.

Conventional optimization methods depend on good initial search point. They sometimes fail by catching the local maximum when image sets with different size, resolution and image quality are input. An innovative strategy was proposed to combine the mutual information with the genetic algorithm, which is a global optimization method to efficiently searching for the maximum value within the large searching space. To improve the computational efficiency, the hybrid genetic algorithm was developed to integrate the large-scale random search with efficient local optimization. Experiments demonstrate it is robust, accurate and efficient strategy for image registration with rigid model.

Three innovative registration systems were developed and implemented with the configurations of objective function and multi-dimensional optimization technique: the function of mutual information combined with the downhill simplex method, the derivative of mutual information combined with Quasi-Newton method and the function 94

of mutual information combined with the hybrid genetic algorithm (GA) method.

The

experiments were conducted with images with different dimensions and FOVs. The results from three registration systems were compared, which provides the valuable information about the design of registration system.

The registration systems of rigid-body model and affine model were integrated into the application of functional MRI analysis. It provides the fast, precise, robust automatic image registration work to align a group of subjects of rodent animals, which is the vital step to determine the area of brain activation in fMRI research.

Another advance is the deformable registration system based on elastic model and viscous fluid model. The registration of soft tissue images (female breast cancer images, lung image) still remains an obstacle because the mathematical modeling of soft tissue is difficult and the mapping of soft tissue is computational complicated. The female breast is actually the composite of different materials. It can be approximately described by the linear elastic model and viscous fluid model with the appropriate elastic constants for specific patient. The registration system of elastic model and viscous model were

developed and validated by woman breast MR images and synthetic images.

Parallel computing, high performance computing on cluster, is the promising strategy to improve the computational efficiency by utilizing the power of computer resource. The parallel computing strategy can be applied on linear elastic and viscous

95

fluid registrations, which involve solving partial differential equations on a large collection of data independently.

All of these advancements enhanced the research of medical image registration significantly. It provides the useful information about modeling and system implementation of medical image registration. The registration systems designed in this work have been successfully applied on the functional MRI research of rodent animals.

96

References

1. Hill, D.L.G., “Combination of 3D Medical Images from Multiple Modalities”, PhD thesis, Image Processing Group, Radiological Sciences UMDS, University of London, (1993). 2. Bushberg, J.B., Seibert, J.A., Leidholdt, E.M. and Boone, J.M., “The essential physics of medical imaging”, Second Edition, ISBN 0683301187, Lippincott Williams Wilkins, (2002). 3. Keller, P.J., “Basic Principles of MR Images”, St. Joseph’s Hospital and Medical Center, Phoenix, AZ 4. Schroeder, W., Martin, K. and Lorensen., W., “The Visualization Toolkit-an objectoriented approach to 3D graphics, Third Edition, Kitware, Inc. 5. Knerek, K., Ivanovic, M., Machac,J., Weber, D.A, “Medical image registration”, Europhysics News, Vol. 31, (2000). 6. Maintz, J.B.A. and Viergever, M.A., “A Survey of Medical Image Registration”, Medical Image Analysis, Vol. 2, pp: 1-36, (1998). 7. Elsen, V.D., Pol, E.J.D., Viergever, M.A., “Medical image matching-a review with classification”, IEEE, Engineering in Medicine and Biology Magazine, Vol.12, pp: 26 –39, (1993). 8. Dawant, B.M.; “Non-rigid registration of medical images: purpose and methods, a short survey”, IEEE, International Symposium, Biomedical Imaging, Proceedings, pp: 465 –468, (2002). 9. Habboush, Mitchell, K.D., Mulkern, R.V., Barnes, P.D. and Treves, S.T., “ Registration and Alignment of Three-Dimensional Images: An Interactive Visual

97

Approach”, Radiology, Vol.199, pp: 573-578, (1996). 10. NLM, “ The Visible Human Project”, http://www.nlm.nih.gov/research/visible/visible_human.html, (2002). 11. Maurer, C.R., Fitzpatrick, J.M., Wang, M.Y., Galloway, R.L., Maciunas, R.J. and Allen, G.G., “Registration of head volume images using implantable fiducial markers”, IEEE, Transactions on Medical Imaging, Vol.16, pp: 447-462, (1997). 12. Fox, P.T., Perlmutter, J.S. and Raichle, M.E., “A Stereotactic Method of Anatomical Localization of Positron Emission Tomography”. Journal of Computer Assisted Tomography, Vol. 9, pp: 141 – 153, (1985). 13. Evans, A.C., Marrett, S.,Collins, L., Peters,TM., “Anatomical-functional correlative analysis of the human brain using three dimensional imaging systems”, Medical imaging processing, Vol.1092, pp: 264-274, SPIE press, (1989). 14. Strother, S.C., Anderson, J.R., Xu, X., Liow, J., Bonar, D.C., Rottenberg, D.A., “Quantitative comparisons of image registration techniques based on high-resolution MRI of the brain”, Journal of Computer Assisted Tomography, Vol.18, pp: 954-962, (1994). 15. Schad, L.R., Boesecke, R., Schlegel, W., Hartmann, G.H., Sturm, G.H., Strauss, L.G., Lorenz, W.J., “Three dimensional image correlation of CT, MR, and PET studies in radiotherapy treatment of brain tumors”, Journal of Computer Assisted Tomography, Vol.11, pp: 948-954, (1987). 16. Fitzpatrick, J.M., West, J.B. and Maurer, C.R., “Predicting error in rigid-body pointbased registration”, IEEE, Transactions on Medical Imaging, Vol.17, pg: 694-702, (1998).

98

17. Umeyama, S., “Least-squares estimation of transformation parameters between two point patterns”, IEEE, Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, pp: 376 –380, (1991). 18. Swanson, L., “Brain Maps: Structure of the Rat Brain”, Third Edition, ISBN: 0126105820. 19. Grimpson, WEL., Ettinger, GJ., White, SJ., T.Lozano-Perez, Wells, WM and Kikinis,R., “An automatic registration method for frameless stereotaxy, image guided surgery, and enhanced reality visualization”, IEEE, Transaction on Medical Imaging, Vol. 15, pp: 129-140, (1996). 20. Herring, J.L., Dawant, B.M., Maurer, C.R., Jr., Muratore, D.M., Galloway, R.L. and Fitzpatrick, J.M., “Surface-based registration of CT images to physical space for image-guided surgery of the spine: a sensitivity study”, IEEE, Transactions on Medical Imaging, Vol.17, pp: 743 –752, (1998). 21. Kanatani, K., “Analysis of 3-D rotation fitting”, IEEE, Transactions on Pattern Analysis and Machine Intelligence”, Vol.16, pp: 543 –549, (1994). 22. Declerc, J., Feldmar, J., Betting, F. and Goris, M.L., “Automatic registration and alignment on a template of cardiac stress and rest SPECT images”, IEEE, Transactions on Medical Imaging, Vol.16, pp: 727 –737,(1997). 23. Maurer, C.R., Jr., Maciunas, R.J. and Fitzpatrick, J.M., “Registration of head CT images to physical space using a weighted combination of points and surfaces”, IEEE, Transactions on Medical Imaging, Vol.17, pp: 753 –761, (1998). 24. Pelizzari, C.A., Chen, G.T.Y., Spelbring, D.R., Weichselbaum, R.R. and Chen, C.T., “Accurate three-dimensional registration of CT, PET, and / or MR images of the brain”. Computer assisted tomography, Vol. 13, pp: 20-26, (1989). 99

25. Borgefors, G.; “Hierarchical chamfer matching: a parametric edge matching algorithm”, IEEE, Transactions on Pattern Analysis and Machine Intelligence, Vol.10, pp: 849 –865, (1988). 26. Besl, P.J., McKay, N.D., "A Method for Registration of 3-D Shapes”, IEEE, Transaction on Pattern Recognition and Machine Intelligence”, Vol. 14, pp: 239-256, (1992). 27. Studholme, C., Hill, D.L.G. and Hawkes, D.J., “Automated 3D MR and PET brain image registration”, Journal of Computer Assisted Radiology, pp: 248-253,1(1995). 28. Maintz, J.B.A., Elsen, V.D. and Viergever, M.A., “Evaluation of ridge seeking operators for multimodality medical image matching”, IEEE, Transactions on Pattern Analysis and Machine Intelligence, Vol.18, pp: 353 –365, (1996). 29. Hajnal, J.V., Saeed, N., Soar, E.J., Oatridge, A., Young, I.R. and Bydder, G.M, “A Registration and Interpolation Procedure for Subvoxel Matching of Serially Acquired MR Images”, Journal of Computer Assisted Tomography, Vol. 19, pp: 289-296, (1995). 30. Zhao, W., Young, T.Y. and Ginsberg, M.D., “Registration and three-dimensional reconstruction of autoradiographic images by the disparity analysis method”, IEEE, Transactions on medical imaging, Vol.12, pg 782-791, (1993). 31. Woods, R.P., Grafton, S.T., Holmes, C.J., Cherry, S.R. and Mazziotta, J C., “Automated Image Registration: I. General Methods and Intrasubject, Intramodality Validation”, Journal of Computer Assisted Tomography, Vol. 12, pp: 153-165, (1994).

100

32. Woods, R.P., Grafton, S.T., Watson, J.D.G., Sicotte, N.L. and Mazziotta, J.C, “Automated Image Registration: II. Intersubject Validation of Linear and Nonlinear Models”, Vol. 22, pg: 153-65, (1994). 33. Woods, R.P., Mazziotta, John C and Cherry, S.R. “MRI-PET Registration with Automated Algorithm”, Journal of Computer Assisted Tomography, Vol.17, pp: 536546, (1994). 34. Woods, R.P., Cherry, S.R. and Mazziotta, J.C., “Rapid Automated Algorithm for Aligning and Reslicing PET Images”, Journal of Computer Assisted Tomography, Vol.16, pp: 620-633, (1994). 35. Wells, W.M., Viola, P., Atsumi, H., Nakajima, S. and Kikinis, R., “Multi-modal volume registration by maximization of mutual information”, Medical Image Analysis, Vol. 1, pp: 35-51, (1996). 36. Viola, P. and Wells, W.M., “Alignment by maximization of mutual information”, Journal of Computer Vision, Vol. 24, pp: 137-154, (1997). 37. Maes, F., Collignon, A., Vandermeulen, D., Marchal, G. and Suetens, P., “Multimodality Image Registration by Maximization of Mutual Information”, IEEE, Transactions on Medical Imaging, Vol.16, pg: 187-198, (1997). 38. Shannon, C.E., “A Mathematical Theory of Communication”, Reprinted with corrections from The Bell System Technical Journal Vol. 27, pg: 379–423, 623–656, (1948). 39. Collins, D.L., Neelin, P., Peters, T.M. and Evans, A.C, “Automatic 3D intersubject registration of MR volumetric data in standardized Talairach space”, Journal of Computer Assisted Tomography, Vol. 18, pg: 192-205, (1994).

101

40. Gee, J., Reivich, M. and Bajacsy R., “ Elastically deforming 3D atlas to match anatomical brain images”, Journal of Computer Assisted Tomography, Vol.17, pg: 225-236, (1993). 41. Bajcsy, R. and Kovacic, S., “Multiresolution elastic matching”, Computer Vision, Graphics and Image Processing, Vol.46, pg:1-21, (1989). 42. Amit, Y., “A nonlinear variational problem for image matching”, SIAM, Journal on Scientific Computing, Vol.15, pg: 207-224, (1994). 43. Thompson, P., and Toga, A.W., “ A surface-based technique for warping threedimensional images of the brain”, IEEE, Transactions on Medical Imaging, Vol.15, pg: 402-417, (1996). 44. Christensen, G.E., Rabitt, R.D. and Miller, M.I., “Deformable Templates Using Large Deformation Kinematics, IEEE, Transactions on Medical Imaging, Vol.5, pg:14351447, (1996). 45. Christensen, G.E., “Individualizing neuroanatomical atlases using a massively parallel computer”, IEEE, Computer, Vol.29, pg: 32-38, (1996). 46. Lester, H., Arridge, S.R, Jansons, K. M., Lemieux3, L., Hajnal, J.V. and Oatridge, A., “Non-linear registration with the variable viscosity fluid algorithm”, 16th International Conference on Information Processing in Medical Imaging, pg: 238251, (1999). 47. Bro-Nielsen, M. and Cramkow, C., “Fast Fluid Registration of Medical Images”, Proc. Visualization in Biomedical Computing (VBC’96), Lecture Notes in Computer Science, Vol.1131, pg: 267-276, Springer, (1996). 48. Gee, J.C., Haynor, D.R., Reivich, M. and Bajcsy, “Finite element approach to

102

warping of brain images”, Proceeding, SPIE Medical Imaging, Vol.2167, pg:18-27, (1994). 49. Edwards, P.J., Hill, D.L.G., Little, J.A. and Hawkes, D.J., “ A three-component deformation model for image-guided surgery”, Medical Image Analysis, Vol.2, pg: 355-367, (1998). 50. Tanner, C., Degenhard, A., Schnabel, J.A., Smith, A.C., Hayes, C., Sonoda, L.I., Leach, M.O., Hose, D.R., Hill, D.L.G. and Hawkes, D.J., “ A Method for the Comparison of Biomechanical Breast Models”, IEEE, pg:11-18, (2001). 51. Zhang, Q.Y., Sullivan, J. M., Yu, H.L. and Wu, Z.J., “Image guided multi-modality registration and visualization for breast cancer detection”, SPIE, Proceedings Medical Imaging, (2005). 52. Bookstein, F.L.; “Principal warps: thin-plate splines and the decomposition of deformations”, IEEE, Transactions on Pattern Analysis and Machine Intelligence, Vol.11, pp: 567 –585, (1989). 53. Meyer, C.R., Boes, J.L., Kim, B., Bland, P.H., Kison, P.V., Koral, K., Frey, K.A. and Wahl, R.L., “Demonstration of accuracy and clinical versatility of mutual information for automatic multimodality image fusion using affine and thin-plate spline warped geometric deformations”, Medical Image Analysis, Vol.1, pg: 195-207, (1997). 54. Wirth, M.A., “ A Nonrigid approach to medical image registration: matching images of the breast”, PhD thesis, RMIT University, Australia, (1999).

55. Rueckert, D., Sonoda,L.I., Hayes, C., Hill, D.L.G., Leach, M.O. and Hawkes, D.J., “Non-rigid registration using free-form deformation: application to breast MR images”, IEEE, Transactions on Medical Imaging, V18, pg:712-721, (1999).

103

56. Ashburner, J. and Friston, K.J., “Nonlinear spatial normalization using basis functions”, Human Brain Mapping, Vol.7, pg 254 –266, (1999). 57. Statistical Parameter Mapping (SPM), http://www.fil.ion.ucl.ac.uk/spm/ 58. Friston K.J, Ashburner J., Frith C.D., Poline J.B., Heather JD and Frackowiak R.S.J, “Spatial registration and normalization of images”, Human Brain Mapping, Vol.2, pp: 165-189, (1995). 59. Tririon, J.P., “ Non-rigid matching using demons”, Proc. Int. Conf. Computer Vision and Pattern Recognition (CVPR’96), San Francisco, CA, pg:245-251, (1996). 60. Thirion, J.-P., “ Image matching as the diffusion process: An analogy with Maxewell’s demons”, Medical Image Analysis, Vol.2, pg:243-260, (1998). 61. Cover, T.M. and Thomas, J.A., “Elements of Information Theory”, Wiley Series in Telecommunications. 62. Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P., “Numerical Recipes in C, The art of Scientific Computing”, Second Edition, Cambridge University Press, (1992). 63. Holland, J.H., “Adaptation in Natural and Artificial Systems”, The University of Michigan Press, Ann Arbor, Michigan, (1975). 64. Goldberg, D.E., “ Genetic Algorithm in Search, Optimization and Machine Learning”, Addison-Wesley Professional, (1989). 65. Deb, K., Anand, A., and Joshi, D., “A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization”. KanGAL Report, (2002).

104

66. Mitchell, M., “An Introduction to Genetic Algorithms”, MIT Press, Cambridge, MA, (1996). 67. Vose, M.D., “The Simple Genetic Algorithm: Foundation and Theory”, MIT Press, Cambridge, MA, (1999). 68.Rouet, J.M., Jacq, J.J.and Roux, C., “Genetic algorithms for a robust 3-D MR-CT registration”, IEEE, Transactions on Information Technology in Biomedicine, Vol.4, pg:126-136,(2000). 69. Matsopoulos, G.K., Mouravliansky, N.A.; Delibasis and K.K.; Nikita, K.S., “Automatic retinal image registration scheme using global optimization techniques”, IEEE, Transactions on Information Technology in Biomedicine, Vol.3, pg: 47-60, (1999). 70. Chi Kin Chow, Hung Tat Tsui Tong Lee and Tze Kin Lau, “Medical image registration and model construction using genetic algorithms”, Proceedings of International Workshop on Medical Imaging and Augmented Reality, pg:174-179, (2001). 71. Ibanez, L., Schroeder, W., Ng, L. and Cates, J., “The ITK Software Guide”, Kitware, Inc. 72. Smith, I.M., Griffiths, D.V., “Programming the Finite Elements Method”, Third Edition, John Wiley & Sons, (1997). 73. Yu, H.L., Sullivan, J.M., Ghadyani, H.R., Zhang, J.Q., “Image Registration by Global Maximization of Mutual Information Based on a Genetic Algorithm”, International Society for Magnetic Resonance in Medicine, (2005).

105