Similarity metrics based on nonadditive entropies for 2D-3D multimodal biomedical image registration Mark P. Wachowiaka*, Renata Smolíkováa, Georgia D. Tourassib, and Adel S. Elmaghrabya a

Department of Computer Engineering and Computer Science University of Louisville, Louisville, KY 40292 USA b Department of Radiology, Duke University Medical Center, Durham, NC 27710 USA ABSTRACT Information theoretic similarity metrics, including mutual information, have been widely and successfully employed in multimodal biomedical image registration. These metrics are generally based on the Shannon-Boltzmann-Gibbs definition of entropy. However, other entropy definitions exist, including generalized entropies, which are parameterized by a real number. New similarity metrics can be derived by exploiting the additivity and pseudoadditivity properties of these entropies. In many cases, use of these measures results in an increased percentage of correct registrations. Results suggest that generalized information theoretic similarity metrics, used in conjunction with other measures, including Shannon entropy metrics, can improve registration performance. Keywords: Image registration, similarity measures, Tsallis entropy, Renyi entropy, mutual information

1. INTRODUCTION In this paper, the use of information theoretic similarity metrics based on generalized entropy for 2D-3D multimodal biomedical image registration is studied. Mutual information based on the Shannon definition of entropy is often employed for image registration. While some generalized entropy and divergence measures have previously been studied in this context, many other metrics have properties that make them conducive to registration. Furthermore, in previous studies, generalized information theoretic metrics were selected to be functionally dissimilar from mutual information. In the current study, the parameterization of generalized measures slightly alters the Shannon mutual information registration function. Thus, the measures presented in this paper are complimentary to the traditional measures. The suitability of these metrics is demonstrated with four sets of multimodal registration experiments.

2. INFORMATION THEORETIC SIMILARITY MEASURES In intensity-based registration, similarity metrics are computed from the intensities of the overlapping regions of the images and/or volumes. Many such metrics have been used, including the sum of squared intensity difference,1 the Woods measure,2 generalized correlation coefficient,3 ratio image uniformity,1 and various information theoretic measures.4-9 The latter comprise one of the most widely used and robust classes of similarity metrics. These metrics are generally based on the Shannon-Boltzmann-Gibbs (henceforth, Shannon) definition of entropy, denoted as HS. Let X denote a discrete random variable with distribution p ≡ p(x) = (p1, p2, …, pN)T. Then H S (X ) = −

∑ p ln p . N

i

i

(1)

i =1

*

Further author information: (Send correspondence to Mark Wachowiak) Email: [email protected] Telephone: +1 (519) 663-5777. Address: Imaging Laboratories, Robarts Research Institute, London, ON, Canada N6A 5K8.

1090

Medical Imaging 2003: Image Processing, Milan Sonka, J. Michael Fitzpatrick, Editors, Proceedings of SPIE Vol. 5032 (2003) © 2003 SPIE · 1605-7422/03/$15.00

For two discrete random variables X and Y with joint distribution p ≡ p(x, y) = pij, i = 1, 2, …, N, j = 1, 2, …, M, the joint entropy of X and Y is given as: H S ( X ,Y ) = −

∑∑ p ln p N

M

ij

ij

.

(2)

i =1 j =1

An important property of HS is additivity: If X and Y are independent random variables, then p(x, y) = p(x)p(y), and HS(X, Y) = HS(X) + HS(Y). If X and Y are maximally correlated, then HS(X, Y) = HS(X) = HS(Y). It is possible to quantify how much X “explains” Y with the Kullback-Leibler divergence, D, between P(X, Y) and P(X)P(Y), and this value is known as mutual information, denoted as I(X, Y): D(( X , Y ) || X × Y ) = I ( X , Y ) =

∑ p( x, y) ln pp(x()x,py( )y) = H ( X ) + H (Y ) − H ( X ,Y ) .

(3)

x, y

From (3), it is seen that mutual information indicates the degree to which X and Y are independent, with I(X, Y) = 0 denoting independence. In the context of biomedical image registration, without loss of generality, X denotes the intensity values of the “floating” image that is to be registered to the reference image, Y. In 2D-3D registration with a 2D floating image, Y denotes the slice in the 3D volume that spatially overlaps with X. The correct registration transformation is determined by maximizing the mutual information function with respect to its transformation parameters. Powell’s method, the Nelder-Mead simplex, gradient methods, stochastic approaches, and other optimization (minimization) techniques are employed to find the minimum of the negative of the registration function. A normalized mutual information (NMI) metric was proposed to reduce the effect of the size of the overlap of two images X and Y on the joint density8: ~ H ( X ) + H (Y ) I ( X ,Y ) = . 2H ( X , Y )

(4)

3. GENERALIZED INFORMATION MEASURES Some work on generalized measures as similarity metrics for image registration have appeared in the literature.2,9-12 One such family of metrics are the f-information measures, which are generalized divergence metrics. In a recent study, three f-information measures were examined: V-information, Iα-information, and Mα-information.9 One of the most successful of these metrics, Iα-information, is written as9: I α (( X , Y ) || X × Y ) =

1

α (α

− 1)

∑ x, y

p α ( x, y ) − 1 . α −1 ( p( x) p( y ))

(5)

Papers using Renyi entropy and Renyi divergence have also appeared.2,10-12 The Renyi entropy of order q, Rq, was one of the first generalized entropies to gain widespread attention.13 It is expressed as: Rq ( X ) =

∑

N 1 ln piq , q ∈ ℜ \ {0,1} . 1 − q i=1

(6)

As can be verified with L’Hôpital’s Rule, Rq specializes to HS in the limit q → 1. Quadratic Renyi entropy (Renyi entropy of order q = 2) has been used in image registration.2,10 Like Shannon entropy, Renyi entropy is additive. ~ Therefore, mutual information using Rq can be defined analogously to that derived from HS. A normalized variant, I qR , is given as:

Proc. of SPIE Vol. 5032

1091

Rq ( X ) + Rq (Y ) ~R . I q ( X ,Y ) = Rq ( X , Y )

(7)

The Havrda-Charvat entropy is another early, generalized entropy measure.14 C. Tsallis introduced a functionally equivalent entropy into the physics literature, where it became important in statistical mechanics and atomic physics because of its ability to describe non-extensive processes that are common at many physical levels.15 (Non-extensivity in physics is roughly analogous to information-theoretic non-additivity). The Havrda-Charvat-Tsallis entropy of type q, henceforth simply called the Tsallis entropy, is denoted as Sq, and is expressed as15: Sq =

1 1− q

∑ [p (1 − p N

q i

1− q i

i =1

)],

q ∈ ℜ \ {0,1} .

(8)

The Tsallis measure exhibits pseudoadditivity: For independent random variables X and Y, the joint entropy of X and Y is the sum of the marginals and some function of the marginals. In the case of the Tsallis measure, Sq(X, Y) = Sq(X) + Sq(Y) + (1 – q) Sq(X) Sq(Y). 16 Therefore, the generalized mutual information of X and Y based on Tsallis entropy, denoted as I qS ( X , Y ) , is given as16: I qS ( X , Y ) = S q ( X ) + S q (Y ) + (1 − q) S q ( X ) S q (Y ) − S q ( X , Y ) .

(9)

A normalized measure based on (9) can also be derived. It has been shown that the upper bound on I qS ( X , Y ) is given by16:

(

)

{

}

I qS ,max,Φ ( X , Y ) = Φ + (1 − q) S q ( X ) S q (Y ) , Φ ∈ S q ( X ), S q (Y ) .

(10)

~ Thus, normalized mutual information based on nonadditive Tsallis entropy, I qS , is expressed as:

~ I qS ( X , Y ) =

I qS I qS ,max,Φ

∈ [0,1] .

(11)

The properties of these metrics can be predicted to some extent by analyzing their curves as functions of relative independence. In Figure 1, metrics were computed from 8-bit joint distributions ranging from independence (pij = 1/2562 for all i, j = 1, 2, …, 256) to complete dependence (pij = 1/256 for i = j, 0 otherwise). Figure 1(a) shows that the ~ curve of I qR , (7), is very similar to that of Shannon normalized mutual information for all q (only curves for q = 0.1 and ~ ~ q = 4 are shown in the figure). In Figure 1(b), the curves for I qS , (11), are shown, and scaled to I qS ∈ [0.5, 1], the same ~ range as for I . Here, the upper bound is computed as I qS ,max ( X , Y ) = S q (Y ) + (1 − q ) S q ( X ) S q (Y ) . It is seen that for low q (q < 1), the gradient of the curve from independence to dependence is low. As the joint distribution indicates ~ more dependence, curves of higher q (q > 1) exhibit a higher gradient than for I . The curves predict that for a “good” ~ initial orientation, I qS with q > 1 may be useful for discerning small changes in degrees of dependence, and consequently, for finding the maximum in a complex and irregular registration function. Actual registration functions ~ ~ for CT-histology registration (see below) are shown in Figures 2-4 for Shannon NMI, I qR , and I qS , respectively. The surfaces are functions of transformations consisting of translations along the x- and y-axes, and translations along the yand z-axes with the addition of small rotation errors. As optimization methods usually perform minimization, the negative similarity metric functions are shown.

(

1092

Proc. of SPIE Vol. 5032

)

(a)

~

~

(b)

Figure 1. Curves of (a) I qR (Renyi) and (b) I qS (Tsallis) normalized mutual information for various q, computed from joint distributions ranging from independent to dependent.

(a) (b) Figure 2. (a) Shannon NMI for CT-histological head volume registration, for translations about the x- and y-axes, and (b) NMI for translations about the y- and z-axes, and small out-of-plane rotations.

(a) q = 0.25

(b) q = 1.25

(c) q = 2

(d) q = 0.25

(e) q = 1.25

(f) q = 2

Figure 3. (a-c) Renyi NMI CT-histological head volume registration, for translations about the x- and y-axes, and (d-f) translations about the y- and z-axes, and small out-of-plane rotations.

Proc. of SPIE Vol. 5032

1093

(a) q = 0.25

(b) q = 1.25

(c) q = 2

(d) q = 0.25

(e) q = 1.25

(f) q = 2

Figure 4. (a-c) Tsallis NMI for CT-histological head volume registration, for translations about the x- and y-axes, and (d-f) translations about the y- and z-axes, and small out-of-plane rotations.

Although this paper focuses on similarity metrics based on the Renyi and Tsallis entropies, other entropy definitions exist, such as the R-norm measure,17-18 trigonometric entropy,19 and other measures,20 and image registration similarity metrics can also be derived from them.

4. METHODS All experiments consisted of rigid body multimodal registration of 2D biomedical images to 3D volumes. Four volumes were available for these experiments. For each volume, four 2D images were obtained to correspond to four different spatial orientations within each volume. In all experiments, the modality of the 2D image was different from the modality of the volume to which the image was registered. Two volumes involved registration of 2D slices with volumes generated from histological sections. Registration involving histology sections is important in atlas matching, functional studies, and in basic biomedical research.21,22 1. 2D simulated ultrasound B-scans (133×133) to an abdominal histology volume (312×212×149). An abdominal volume (Volume 1) was obtained through the NLM-NIH Visible Human Project®, and consists of histological sections from a deceased female. Volumes are generated from stacking individual slices together. The resolution along the x-, y-, and z-axes is 0.33 mm. Because of the heavy computational requirements involved in image registration, the volume was downsampled by a factor of 4, and interpolated using cubic splines. A slice from the abdominal histology volume is shown in Figure 5(a). Downsampling does not noticeably degrade the quality of the image (although in diagnostic applications, higher resolution is required). The 2D images are realistic B-mode ultrasound simulations generated from physical parameters of ultrasound scattering: the density, amplitude (crosssection), and regularity of the placement of the scatterers in tissue.23 A simulated B-scan is shown in Figure 5(b). 2. 2D brain CT (133×155) to a brain histological volume (174×204×149). A brain volume (Volume 2) was also obtained through the Visible Human Project, as were corresponding CT images registered to this volume (Figures 6(a-b)). As with Volume 1, the volume, 0.33 mm resolution on all axes, was

1094

Proc. of SPIE Vol. 5032

downsampled by 4 and interpolated. The CT images were quantized to 8-bit intensities. The CT images have a resolution of 0.48828 mm along the x- and y-axes, and 1 mm along the z-axis. Thus, isotropic volumes cannot be generated directly from CT slices, although such volumes may be generated with interpolation. The CT images were scaled to the downsampled histology volumes using bicubic interpolation. 3. 2D T2-weighted MRI (128×128) to a MRI T1-weighted brain volume (181×217×181). A realistic simulated T1-weighted MRI volume of a normal brain (Volume 3) and corresponding T2-weighted images were obtained from the BrainWeb database at McGill University.24,25 The purpose of this simulator is to provide researchers with ground truth data for image analysis techniques and algorithms. The volume is isotropic, with 1 mm resolution on all three axes. The data are quantized to 8-bits. The T1 simulations had 3% noise, while the T2 volume was noise-free. 4. 2D PD-weighted MRI (128×128) to a MRI T2-weighted brain volume (181×217×181). Simulated PD- and T2-weighted MRI of a brain with multiple sclerosis lesions was also obtained from BrainWeb at McGill University. The T2 volume had 3% noise, while the PD images were contaminated with 9% noise. The large amount of noise in the PD images reduces the contrast of many of the intensity features that are useful in computing similarity metrics. Therefore, registrations with this volume and set of images are considered to be particularly difficult.

(a)

(b)

Figure 5. Ultrasound-to-histology registration. (a) Slice from abdominal histological volume. (b) Corresponding simulated ultrasound B-scan.

(a)

(b)

Figure 6. CT-to-histology registration. (a) Slice from histological head volume. (b) Corresponding CT image.

Proc. of SPIE Vol. 5032

1095

To test the proposed similarity metrics, rigid body registration experiments were performed, in which translations along the x-, y-, and z- axes (tx, ty, and tz, respectively) and Euler angle rotations about the x-, y-, and z-axes (α, β, and γ, respectively) were determined. For all experiments, ground truth transformations, x* = [tx* ty* tz* α* β* γ*]T, were known. Four 2D images from the modalities described above were registered to each of the 3D volumes. For instance, for Volume 1, four simulated B-scans with different 3D orientations were aligned to the histology volume. Each slice was initially oriented at Euclidean distances of 2, 4, 6, 8, and 10 voxels from ground truth. For each initial distance, 10 sets of misrotations were applied, with angles ranging from ±5° to ±30° from ground truth. During the registration process, partial volume interpolation6,26 was employed. Optimization was performed with Powell’s method. ~ Registration performance of the following similarity metrics was compared: I (normalized Shannon mutual ~ ~ information), I qR and I qS , with q ∈ {0.25, 0.5, 0.9, 1.1, 1.25, 1.5, 2}, and Iα, with α ∈ {0.1, 0.2, 0.5, 0.9, 1.1, 1.25, 1.5, ~ 2} (Many of these values were also used in a previous study).9 For I qS , the upper bound was computed as ~ I qS ,max ( X , Y ) = S q (Y ) + (1 − q ) S q ( X ) S q (Y ) . I qS was scaled to [0.5, 1.0], the same range as Shannon NMI. The probability densities were estimated from 64-bin histograms.

(

)

The performance of the metrics was compared on three criteria: (1) The correctness ratio, CR, is the ratio of registration trials classified as correct to all registrations. A registration is considered “correct” if the Euclidean distance between the final and ground truth translation parameters is strictly less than 1.75 voxels, and if the root meansquared error between the rotation matrices of the final and ground truth rotation parameters is strictly less than 0.25. (2) The efficiency is the average number of function evaluations (computation of the similarity metric) for correct registrations. (3) The accuracy (and corresponding precision, measured by standard deviation) is an actual numerical distance of the final transformation from ground truth. Accuracy, for correct registrations, is defined to be the mean of the distances from the four corners of an image transformed by the ground truth transformation, and the transformation returned by the registration algorithm. For perfect registration, this mean distance is numerically zero with zero standard deviation. In the current work, the image from which the corners are computed has dimensionality 10 × 10 voxels.

5. RESULTS ~ The ratio of correct registrations and efficiency values for the Shannon NMI ( I ), Tsallis, Renyi, and Iα measures ~ are shown by volume in Table 1. CR values higher than those for I are displayed in boldface. From these results, it is ~S seen that the I q and Iα measures generally have higher correctness ratios than Shannon NMI for specific parameter ~ ~ values. I qS outperformed I for 3 of the 4 volumes for q very close to 1 (recall that Sq → HS as q → 1), and for q > 1. The latter observation can be predicted on the basis of Figure 1, where the curves for q > 1 have a higher gradient as random variables move from independence to dependence. The Iα metrics also performed well, especially for the ~ ultrasound-histology and PD-T2 MRI registrations. However, I qS outperformed Iα for the CT-histology and T2-T1 MRI experiments. The Renyi metrics generally did not perform as well as Shannon NMI. The highest percentage of correct registrations for all metrics occurred with the ultrasound-histology (Volume 1) and CT-histology (Volume 2) registrations, and the lowest, with the PD-T2 MRI (Volume 4).

In efficiency, the Shannon metric generally required the fewest function evaluations for correct registrations. ~S I q required slightly more evaluations than Shannon NMI, but less than Iα, as evidenced in Table 1. The increased number of function evaluations required by Iα was also reported in a previous study.9 ~ ~ ~ The accuracies of the best performers, I , I qS , and Iα are shown in Table 2. From this table, it is seen that I is the ~ most accurate measure, followed by Iα, with I qS slightly less accurate than Iα.

1096

Proc. of SPIE Vol. 5032

For all metrics, as expected, the best results were observed for initial translational positions close to ground truth, with a decrease in correct registrations with increasing Euclidean distance. Thus, although many of the generalized measures has fewer misregistrations, the problem of entrapment in local minima is not completely avoided. ~

~

~

Table 1. Ratio of correct registrations (CR) and efficiencies for the Shannon ( I ), Renyi ( I qR ), Tsallis ( I qS ), and Iα information measures.

Metric ~ I ~R Iq

Par. − 0.25 0.5 0.9 1.1 1.25 1.5 2 0.25 0.5 0.9 1.1 1.25 1.5 2 0.1 0.2 0.5 0.9 1.1 1.25 1.5 2

~S Iq

Iα

CR Vol.1 0.65 0.08 0.34 0.54 0.58 0.57 0.39 0.29 0.08 0.36 0.71 0.83 0.80 0.86 0.63 0.46 0.66 0.79 0.84 0.86 0.85 0.86 0.61

Vol.2 0.53 0.03 0.11 0.49 0.56 0.51 0.39 0.16 0.09 0.45 0.61 0.67 0.68 0.58 0.41 0.18 0.34 0.49 0.57 0.63 0.55 0.54 0.33

Efficiency Vol.3 0.49 0.01 0.08 0.28 0.36 0.40 0.41 0.34 0.03 0.24 0.50 0.51 0.52 0.46 0.21 0.16 0.16 0.32 0.38 0.38 0.36 0.34 0.17

Vol.4 0.14 0.01 0.03 0.09 0.10 0.09 0.08 0.07 0.01 0.04 0.08 0.13 0.11 0.09 0.04 0.09 0.14 0.20 0.18 0.20 0.20 0.18 0.07

~

~

Vol.1 584 ± 140 658 ± 104 616 ± 158 560 ± 142 577 ± 155 557 ± 148 542 ± 123 510 ± 155 315 ± 136 484 ± 149 661 ± 176 662 ± 162 676 ± 174 708 ± 179 679 ± 191 1142 ± 303 1195 ± 484 986 ± 310 910 ± 259 872 ± 257 859 ± 260 874 ± 252 838 ± 247

Vol.2 534 ± 113 545 ± 322 539 ± 63 513 ± 108 502 ± 89 532 ± 119 509 ± 112 478 ± 117 404 ± 78 537 ± 104 564 ± 120 590 ± 136 595 ± 145 600 ± 132 622 ± 145 1060 ± 356 1016 ± 213 766 ± 177 703 ± 155 684 ± 172 685 ± 168 714 ± 176 820 ± 221

Vol.3 789 ± 164 1548 ± 21 1097 ± 327 807 ± 165 774 ± 211 795 ± 208 789 ± 209 803 ± 194 291 ± 326 795 ± 198 792 ± 193 799 ± 196 809 ± 186 869 ± 221 812 ± 236 1630 ± 785 1516 ± 659 1020 ± 289 942 ± 393 904 ± 321 935 ± 304 1003 ± 351 1068 ± 260

Vol.4 594 ± 99 509 ± 0 500 ± 79 637 ± 97 558 ± 147 574 ± 169 516 ± 147 540 ± 79 275 ± 0 447 ± 118 674 ± 170 652 ± 165 662 ± 198 636 ± 163 511 ± 238 1092 ± 353 1229 ± 375 1177 ± 332 1013 ± 295 959 ± 314 1122 ± 382 1045 ± 373 1071 ± 378

~

Table 2. Accuracy for the Shannon ( I ), Renyi ( I qR ), Tsallis ( I qS ), and Iα information measures.

Metric ~ I ~S Iq

Iα

Parameter −

Vol. 1 1.05 ± 0.65

Vol. 2 0.44 ± 0.45

Vol. 3 0.18 ± 0.46

Vol. 4 0.44 ± 0.30

0.9 1.1 1.25 1.5 0.5 0.9 1.1 1.25

1.08 ± 0.68 1.07 ± 0.69 1.09 ± 0.66 1.00 ± 0.70 1.15 ± 0.62 1.01 ± 0.69 1.02 ± 0.67 1.02 ± 0.67

0.78 ± 0.58 0.79 ± 0.57 0.73 ± 0.53 0.72 ± 0.57 0.62 ± 0.57 0.60 ± 0.55 0.57 ± 0.52 0.56 ± 0.50

1.14 ± 0.81 1.09 ± 0.84 1.01 ± 0.87 1.00 ± 0.87 0.89 ± 0.78 0.86 ± 0.82 0.87 ± 0.80 0.76 ± 0.81

1.25 ± 0.75 1.05 ± 0.71 1.21 ± 0.82 1.31 ± 0.71 1.43 ± 0.55 1.50 ± 0.57 1.32 ± 0.61 1.37 ± 0.68

Proc. of SPIE Vol. 5032

1097

6. DISCUSSION It has not yet been proven that information theoretic similarity measures are optimal.4 In many instances, the global minimum of the registration function does not occur at the correct transformation, as has been reported by other investigators.4 In addition, sensitivity to interpolation artifacts9,26 and irregularity in the metric function may lead to many misregistrations, as was the case with the noisy PD images (Volume 4). However, the information theoretic measures have been shown to have a high success rate overall, and the current work contributes to the study of these measures by applying generalized metrics to biomedical image registration. ~ The success of the Tsallis information measure I qS , (11) can be explained to some extent in terms of properties of the Tsallis entropy. Recall that information based on the Tsallis entropy is given as16: I qS ( X , Y ) = S q ( X ) + S q (Y ) + (1 − q ) S q ( X ) S q (Y ) − S q ( X , Y ) .

(12)

If X and Y are statistically independent, then S q ( X , Y ) = S ( X ) + S (Y ) + (1 − q) S ( X )S (Y ) . The ratio of the Tsallis ~ ~ information to the upper bound, I qS , measures the degree of dependence between random variables.16 If I qS with q > 0 is plotted as a function of the independence of the variables X and Y, the curve runs from 0, indicating complete independence of X and Y, to unity, indicating a one-to-one correspondence between X and Y; that is, X and Y are maximally correlated (Figure 1(b)). There is also an optimal value of q, qopt, for a given degree of correlation, for ~ ~ which I qS is most capable of detecting small variations of correlation among the variables. That is, the gradient of I qS is most sensitive at qopt.16 However, there are as yet no guidelines for selecting qopt,16 except possibly by experiment. It should not be expected that there is one qopt for each problem. For the registration experiments presented in the current study, values of q close to unity (q = 0.9, 1.1) and slightly higher than unity (q = 1.1, 1.25, 1.5) resulted in a high percentage of correct registrations. For low orders (q = 0.25, 0.5), the basins of attraction for the minima are narrower, and the surrounding landscape is flatter, with many tiny minima “pores”. However, the irregularity of the landscape greatly increases for larger q, such as q = 2. Although the regions surrounding the basin of attraction are not flat, as they are with low orders, the increase in the number of clearly discernable local minima poses challenges for optimization algorithms. Furthermore, there are possibly computational difficulties associated with very high or very low q. As the individual intensity probabilities are very small, loss of machine precision may accumulate, leading to small variations in the similarity metric function that may affect an optimization algorithm. Another consideration is that interpolation artifacts are encountered during the registration process.26 These errors affect the intensity histogram, and are magnified by high orders of entropy. ~R I q showed promising results in a previous study, where it outperformed normalized Shannon mutual information in both correctness and efficiency.27 In that study, 2D-to-2D registration was performed on an MRI reference image and a corresponding simulated B-scan. However, in the current work, the Renyi measure had a lower ratio of correct registrations than for the Shannon measure. The fact that good performance – in fact, better performance than Shannon mutual information – with this measure (and the R-norm metric) was observed in a different set of experiments27 indicates that the success of the similarity metrics is highly dependent on the modalities being registered.

Finally, it must be emphasized that very good performance was attained with q values close to unity. As demonstrated in many studies, the Shannon mutual information has proven to be a very effective similarity metric in biomedical image registration. Thus, varying q slightly from the Shannon limit value of q = 1 has the effect of only slightly altering the Shannon metric registration function. Specifically, use of Tsallis information measures with q close to one can be considered as using a “modified” version of the Shannon mutual information, rather than a completely different metric. Additionally, it was suggested that the Shannon measure may be used in the early stages of registration, and that generalized measures may be used to improve the final accuracy.9 In this study, by contrast, the high accuracy of the Shannon measure suggests that generalized metrics in the early, more “global” optimization stages can be followed by utilization of the Shannon measure to accurately determine the correct registration transformation.

1098

Proc. of SPIE Vol. 5032

7. CONCLUSIONS The results presented in this paper demonstrate that similarity metrics based on nonadditive entropy, specifically the Tsallis entropy, often produce fewer misregistrations than the widely used Shannon measure. They also generally require fewer function evaluations than Iα information. However, for correct registrations, the Shannon metric was more accurate than either the Tsallis measure or Iα information. Furthermore, as the curves in Figure 1 predict, better registrations occur for q > 1 for the Tsallis measure. However, the best results occur for q close to unity. As the Tsallis entropy becomes the Shannon entropy as q → 1, the former measure can be considered as a “slight deviation” from the latter, for q close to unity. Generalized metrics can thus be considered as modifications adjustments to the Shannon measure, making it more conducive to optimization. Generalized similarity metrics are presented as complementary to the Shannon measure (and other metrics), and not as replacements. A promising future direction is to utilize the parameterization of the generalized measures by adaptive parameter adjustment during the course of the optimization. As shown in this work, parameterized generalized measures frequently exhibit increased success if the parameter values deviate slightly from unity (in which most of the measures specialize to corresponding Shannon metrics). Therefore, it may prove beneficial that these metrics adapt the values of their parameters in response to the progress of the search. Adaptive generalized measures may be relatively broad in the early stages of the search to widen the basin of attraction, consequently drawing the search into the vicinity of the minimum. As the search progresses, parameters may be adapted to sharpen this region, providing faster convergence. Finally, the Shannon measure can be used in the final stages of the search for increased accuracy. To implement adaptive measures, feedback must be obtained from the optimization algorithm. In this respect, Powell’s method, which is a direction set technique, may not provide enough feedback to allow similarity metric adaptation, and simplex methods, such as the Nelder-Mead algorithm, may be more appropriate for this purpose. Adaptation is desirable because a single metric cannot be the best performer in all registration situations. Alternative optimization approaches may also be less susceptible to registration errors resulting from complex registration functions.9 Furthermore, the selection of an “optimal” parameter, or even whether such a parameter exists, is an open question that cannot be determined from experimental results alone.9,27 However, generalized metrics merit further study on a rigorous, mathematical basis, to determine the registration situations in which their use is most appropriate. Although generalized metrics were shown improve registration performance (in terms of correct registrations) in many circumstances, this paradigm should also be studied in conjunction with multiresolution strategies or incorporation of other criteria, such as gradient information.3,28 Finally, validation on a wide range of clinical data is also required.

ACKNOWLEDGEMENTS The authors wish to thank the U.S. National Library of Medicine-National Institutes of Health Visible Human Project for making their data available. The authors also acknowledge the BrainWeb project at McGill University in Montréal, Quebec, Canada (http://www.bic.mni.mcgill.ca/brainweb/), for internet-based generation MRI brain volumes.

REFERENCES 1. 2. 3.

D. L. G. Hill and P. Batchelor, “Registration methodology: concepts and algorithms,” in Medical Image Registration, J. V. Hajnal, D. L. G. Hill, and D. J. Hawkes, Editors. CRC Press, Boca Raton, FL, 2001. M. Čapek, L. Mroz, and R. Wegenkittl, “Robust and fast medical registration of 3D-multimodality data sets,” Proc. of Medicon 2001, Part I, pp. 515-518, 2001. A. Roche, X. Pennec, G. Malandain, and N. Ayache, “Rigid registration of 3-D ultrasound with MR images: a new approach combining intensity and gradient information,” IEEE Transactions on Medical Imaging 20, pp. 10381049, 2001.

Proc. of SPIE Vol. 5032

1099

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.

22. 23. 24. 25. 26. 27.

28.

1100

D. L. G. Hill, P. G. Batchelor, M. Holden, and D. J. Hawkes, “Medical image registration,” Physics in Medicine and Biology 46, pp. R1-R45, 2001. J. B. A. Maintz and M. A. Viergever, “A survey of medical image registration,” Medical Image Analysis 2, pp. 137, 1998. F. Maes, A. Collignon, D. Vandermeulen, G. Marchal, and P. Suetens, “Multimodality image registration by maximization of mutual information,” IEEE Transactions on Medical Imaging 16, pp. 187-198, 1997. W. M. Wells III, P. Viola, H. Atsumi, S. Nakajima, S., and R. Kikinis, “Multimodal volume registration by maximization of mutual information,” Medical Image Analysis 1, pp. 35-51, 1996. C. Studholme, D. L. G. Hill, and D. J. Hawkes, “An overlap invariant entropy measure of 3D medical image alignment,” Pattern Recognition 32, pp. 71-86, 1999. J. P. W. Pluim, J. B. A. Maintz, and M. A. Viergever, “f-information measures in medical image registration,” Proc. of SPIE Medical Imaging: Image Processing, pp. 579-587, 2001. B. Ma, A. Hero, and J. Gorman, “Image registration with minimal spanning tree algorithm,” Proc. the IEEE International Conference on Image Processing (ICIP), Vancouver, BC, Canada, 2000. Y. He, A. B. Hamza, and H. Krim, “An information divergence measure for ISAR image registration,” Proc. IEEE Workshop on Statistical Signal Processing, Singapore, 2001. H. Neemuchwala, A. O. Hero, and P. Carson, “Feature coincidence trees for registration of ultrasound breast images,” Proc. IEEE International Conference on Image Processing, Thesaloniki, Greece, 2001. A. Renyi, Probability Theory, North-Holland, Amsterdam, 1970. J. H. Havrda and F. Charvat, “Quantification methods of classification processes: concepts of structural α entropy,” Kybernetica 3, pp. 30-35, 1967. C. Tsallis, “Possible generalization of Boltzmann-Gibbs statistics,” Journal of Statistical Physics 52, pp. 479-487, 1988. L. Borland, A. R. Plastino, and C. Tsallis, “Information gain within nonextensive thermostatistics,” Journal of Mathematical Physics 39, pp. 6490-6501, 1998. S. Arimoto, “Information-theoretical considerations on estimation problems,” Information and Control 19, pp. 191194, 1971. D. E. Boekee and J. C. A. Van der Lubbe, “The R-norm information measure,” Information and Control 45, pp. 136-155, 1980. A. P. Sant’anna and I. J. Taneja, “Trigonometric entropies, Jensen difference divergence measures, and error bounds,” Information Sciences 35, pp. 145-156, 1985. J. N. Kapur, Measures of Information and Their Applications, John Wiley & Sons, New York, NY, 1994. M. S. Mega, S. S. Chen, P. M. Thompson, R. P. Woods, T. J. Karaca, A. Tiwari, H. V. Vinters, G. W. Small, and A. W. Toga, “Mapping histology to metabolism: coregistration of stained whole-brain sections to premortem PET in Alzheimer's disease,” Neuroimage 5, pp. 147-153, 1997. A. W. Toga and P. M. Thompson, “The role of image registration in brain mapping,” Image and Vision Computing 19, pp. 3-24, 2001. V. M. Narayanan and P. M. Shankar, “Non-Rayleigh statistics of ultrasonic backscattered signals,” IEEE Trans. on Ultrasonics, Ferroelectrics and Frequency Control 41, pp. 845-852, 1994. D. L. Collins, A. P. Zijdenbos, V. Kollokian, J. G. Sled, N. J. Kabani, C. J. Holmes, and A. C. Evans, “Design and construction of a realistic digital brain phantom,” IEEE Transactions on Medical Imaging 17, pp. 463-468, 1998. R. K.-S. Kwan, A. C. Evans, and G. B. Pike, “MRI simulation-based evaluation of image processing and classification methods,” IEEE Transactions on Medical Imaging 18, pp. 1085-1097, 1999. J. P. W Pluim, J. B. A. Maintz, and M. A. Viergever, “Interpolation artefacts in mutual information-based image registration,” Computer Vision and Image Understanding 77, pp. 211-232, 2000. M. P. Wachowiak, R. Smolíková, G. D. Tourassi, and A. S. Elmaghraby, “Generalized mutual information as a similarity metric for multimodal biomedical image registration,” Proc. 2nd Annual IEEE EMBS/BMES Joint Conference, Houston, pp. 1005-1006, 2002. J. P. W. Pluim, J. B. A. Maintz, and M. A. Viergever, “Image registration by maximization of combined mutual information and gradient information,” IEEE Transactions on Medical Imaging 19, pp. 809-814, 2000.

Proc. of SPIE Vol. 5032

Department of Computer Engineering and Computer Science University of Louisville, Louisville, KY 40292 USA b Department of Radiology, Duke University Medical Center, Durham, NC 27710 USA ABSTRACT Information theoretic similarity metrics, including mutual information, have been widely and successfully employed in multimodal biomedical image registration. These metrics are generally based on the Shannon-Boltzmann-Gibbs definition of entropy. However, other entropy definitions exist, including generalized entropies, which are parameterized by a real number. New similarity metrics can be derived by exploiting the additivity and pseudoadditivity properties of these entropies. In many cases, use of these measures results in an increased percentage of correct registrations. Results suggest that generalized information theoretic similarity metrics, used in conjunction with other measures, including Shannon entropy metrics, can improve registration performance. Keywords: Image registration, similarity measures, Tsallis entropy, Renyi entropy, mutual information

1. INTRODUCTION In this paper, the use of information theoretic similarity metrics based on generalized entropy for 2D-3D multimodal biomedical image registration is studied. Mutual information based on the Shannon definition of entropy is often employed for image registration. While some generalized entropy and divergence measures have previously been studied in this context, many other metrics have properties that make them conducive to registration. Furthermore, in previous studies, generalized information theoretic metrics were selected to be functionally dissimilar from mutual information. In the current study, the parameterization of generalized measures slightly alters the Shannon mutual information registration function. Thus, the measures presented in this paper are complimentary to the traditional measures. The suitability of these metrics is demonstrated with four sets of multimodal registration experiments.

2. INFORMATION THEORETIC SIMILARITY MEASURES In intensity-based registration, similarity metrics are computed from the intensities of the overlapping regions of the images and/or volumes. Many such metrics have been used, including the sum of squared intensity difference,1 the Woods measure,2 generalized correlation coefficient,3 ratio image uniformity,1 and various information theoretic measures.4-9 The latter comprise one of the most widely used and robust classes of similarity metrics. These metrics are generally based on the Shannon-Boltzmann-Gibbs (henceforth, Shannon) definition of entropy, denoted as HS. Let X denote a discrete random variable with distribution p ≡ p(x) = (p1, p2, …, pN)T. Then H S (X ) = −

∑ p ln p . N

i

i

(1)

i =1

*

Further author information: (Send correspondence to Mark Wachowiak) Email: [email protected] Telephone: +1 (519) 663-5777. Address: Imaging Laboratories, Robarts Research Institute, London, ON, Canada N6A 5K8.

1090

Medical Imaging 2003: Image Processing, Milan Sonka, J. Michael Fitzpatrick, Editors, Proceedings of SPIE Vol. 5032 (2003) © 2003 SPIE · 1605-7422/03/$15.00

For two discrete random variables X and Y with joint distribution p ≡ p(x, y) = pij, i = 1, 2, …, N, j = 1, 2, …, M, the joint entropy of X and Y is given as: H S ( X ,Y ) = −

∑∑ p ln p N

M

ij

ij

.

(2)

i =1 j =1

An important property of HS is additivity: If X and Y are independent random variables, then p(x, y) = p(x)p(y), and HS(X, Y) = HS(X) + HS(Y). If X and Y are maximally correlated, then HS(X, Y) = HS(X) = HS(Y). It is possible to quantify how much X “explains” Y with the Kullback-Leibler divergence, D, between P(X, Y) and P(X)P(Y), and this value is known as mutual information, denoted as I(X, Y): D(( X , Y ) || X × Y ) = I ( X , Y ) =

∑ p( x, y) ln pp(x()x,py( )y) = H ( X ) + H (Y ) − H ( X ,Y ) .

(3)

x, y

From (3), it is seen that mutual information indicates the degree to which X and Y are independent, with I(X, Y) = 0 denoting independence. In the context of biomedical image registration, without loss of generality, X denotes the intensity values of the “floating” image that is to be registered to the reference image, Y. In 2D-3D registration with a 2D floating image, Y denotes the slice in the 3D volume that spatially overlaps with X. The correct registration transformation is determined by maximizing the mutual information function with respect to its transformation parameters. Powell’s method, the Nelder-Mead simplex, gradient methods, stochastic approaches, and other optimization (minimization) techniques are employed to find the minimum of the negative of the registration function. A normalized mutual information (NMI) metric was proposed to reduce the effect of the size of the overlap of two images X and Y on the joint density8: ~ H ( X ) + H (Y ) I ( X ,Y ) = . 2H ( X , Y )

(4)

3. GENERALIZED INFORMATION MEASURES Some work on generalized measures as similarity metrics for image registration have appeared in the literature.2,9-12 One such family of metrics are the f-information measures, which are generalized divergence metrics. In a recent study, three f-information measures were examined: V-information, Iα-information, and Mα-information.9 One of the most successful of these metrics, Iα-information, is written as9: I α (( X , Y ) || X × Y ) =

1

α (α

− 1)

∑ x, y

p α ( x, y ) − 1 . α −1 ( p( x) p( y ))

(5)

Papers using Renyi entropy and Renyi divergence have also appeared.2,10-12 The Renyi entropy of order q, Rq, was one of the first generalized entropies to gain widespread attention.13 It is expressed as: Rq ( X ) =

∑

N 1 ln piq , q ∈ ℜ \ {0,1} . 1 − q i=1

(6)

As can be verified with L’Hôpital’s Rule, Rq specializes to HS in the limit q → 1. Quadratic Renyi entropy (Renyi entropy of order q = 2) has been used in image registration.2,10 Like Shannon entropy, Renyi entropy is additive. ~ Therefore, mutual information using Rq can be defined analogously to that derived from HS. A normalized variant, I qR , is given as:

Proc. of SPIE Vol. 5032

1091

Rq ( X ) + Rq (Y ) ~R . I q ( X ,Y ) = Rq ( X , Y )

(7)

The Havrda-Charvat entropy is another early, generalized entropy measure.14 C. Tsallis introduced a functionally equivalent entropy into the physics literature, where it became important in statistical mechanics and atomic physics because of its ability to describe non-extensive processes that are common at many physical levels.15 (Non-extensivity in physics is roughly analogous to information-theoretic non-additivity). The Havrda-Charvat-Tsallis entropy of type q, henceforth simply called the Tsallis entropy, is denoted as Sq, and is expressed as15: Sq =

1 1− q

∑ [p (1 − p N

q i

1− q i

i =1

)],

q ∈ ℜ \ {0,1} .

(8)

The Tsallis measure exhibits pseudoadditivity: For independent random variables X and Y, the joint entropy of X and Y is the sum of the marginals and some function of the marginals. In the case of the Tsallis measure, Sq(X, Y) = Sq(X) + Sq(Y) + (1 – q) Sq(X) Sq(Y). 16 Therefore, the generalized mutual information of X and Y based on Tsallis entropy, denoted as I qS ( X , Y ) , is given as16: I qS ( X , Y ) = S q ( X ) + S q (Y ) + (1 − q) S q ( X ) S q (Y ) − S q ( X , Y ) .

(9)

A normalized measure based on (9) can also be derived. It has been shown that the upper bound on I qS ( X , Y ) is given by16:

(

)

{

}

I qS ,max,Φ ( X , Y ) = Φ + (1 − q) S q ( X ) S q (Y ) , Φ ∈ S q ( X ), S q (Y ) .

(10)

~ Thus, normalized mutual information based on nonadditive Tsallis entropy, I qS , is expressed as:

~ I qS ( X , Y ) =

I qS I qS ,max,Φ

∈ [0,1] .

(11)

The properties of these metrics can be predicted to some extent by analyzing their curves as functions of relative independence. In Figure 1, metrics were computed from 8-bit joint distributions ranging from independence (pij = 1/2562 for all i, j = 1, 2, …, 256) to complete dependence (pij = 1/256 for i = j, 0 otherwise). Figure 1(a) shows that the ~ curve of I qR , (7), is very similar to that of Shannon normalized mutual information for all q (only curves for q = 0.1 and ~ ~ q = 4 are shown in the figure). In Figure 1(b), the curves for I qS , (11), are shown, and scaled to I qS ∈ [0.5, 1], the same ~ range as for I . Here, the upper bound is computed as I qS ,max ( X , Y ) = S q (Y ) + (1 − q ) S q ( X ) S q (Y ) . It is seen that for low q (q < 1), the gradient of the curve from independence to dependence is low. As the joint distribution indicates ~ more dependence, curves of higher q (q > 1) exhibit a higher gradient than for I . The curves predict that for a “good” ~ initial orientation, I qS with q > 1 may be useful for discerning small changes in degrees of dependence, and consequently, for finding the maximum in a complex and irregular registration function. Actual registration functions ~ ~ for CT-histology registration (see below) are shown in Figures 2-4 for Shannon NMI, I qR , and I qS , respectively. The surfaces are functions of transformations consisting of translations along the x- and y-axes, and translations along the yand z-axes with the addition of small rotation errors. As optimization methods usually perform minimization, the negative similarity metric functions are shown.

(

1092

Proc. of SPIE Vol. 5032

)

(a)

~

~

(b)

Figure 1. Curves of (a) I qR (Renyi) and (b) I qS (Tsallis) normalized mutual information for various q, computed from joint distributions ranging from independent to dependent.

(a) (b) Figure 2. (a) Shannon NMI for CT-histological head volume registration, for translations about the x- and y-axes, and (b) NMI for translations about the y- and z-axes, and small out-of-plane rotations.

(a) q = 0.25

(b) q = 1.25

(c) q = 2

(d) q = 0.25

(e) q = 1.25

(f) q = 2

Figure 3. (a-c) Renyi NMI CT-histological head volume registration, for translations about the x- and y-axes, and (d-f) translations about the y- and z-axes, and small out-of-plane rotations.

Proc. of SPIE Vol. 5032

1093

(a) q = 0.25

(b) q = 1.25

(c) q = 2

(d) q = 0.25

(e) q = 1.25

(f) q = 2

Figure 4. (a-c) Tsallis NMI for CT-histological head volume registration, for translations about the x- and y-axes, and (d-f) translations about the y- and z-axes, and small out-of-plane rotations.

Although this paper focuses on similarity metrics based on the Renyi and Tsallis entropies, other entropy definitions exist, such as the R-norm measure,17-18 trigonometric entropy,19 and other measures,20 and image registration similarity metrics can also be derived from them.

4. METHODS All experiments consisted of rigid body multimodal registration of 2D biomedical images to 3D volumes. Four volumes were available for these experiments. For each volume, four 2D images were obtained to correspond to four different spatial orientations within each volume. In all experiments, the modality of the 2D image was different from the modality of the volume to which the image was registered. Two volumes involved registration of 2D slices with volumes generated from histological sections. Registration involving histology sections is important in atlas matching, functional studies, and in basic biomedical research.21,22 1. 2D simulated ultrasound B-scans (133×133) to an abdominal histology volume (312×212×149). An abdominal volume (Volume 1) was obtained through the NLM-NIH Visible Human Project®, and consists of histological sections from a deceased female. Volumes are generated from stacking individual slices together. The resolution along the x-, y-, and z-axes is 0.33 mm. Because of the heavy computational requirements involved in image registration, the volume was downsampled by a factor of 4, and interpolated using cubic splines. A slice from the abdominal histology volume is shown in Figure 5(a). Downsampling does not noticeably degrade the quality of the image (although in diagnostic applications, higher resolution is required). The 2D images are realistic B-mode ultrasound simulations generated from physical parameters of ultrasound scattering: the density, amplitude (crosssection), and regularity of the placement of the scatterers in tissue.23 A simulated B-scan is shown in Figure 5(b). 2. 2D brain CT (133×155) to a brain histological volume (174×204×149). A brain volume (Volume 2) was also obtained through the Visible Human Project, as were corresponding CT images registered to this volume (Figures 6(a-b)). As with Volume 1, the volume, 0.33 mm resolution on all axes, was

1094

Proc. of SPIE Vol. 5032

downsampled by 4 and interpolated. The CT images were quantized to 8-bit intensities. The CT images have a resolution of 0.48828 mm along the x- and y-axes, and 1 mm along the z-axis. Thus, isotropic volumes cannot be generated directly from CT slices, although such volumes may be generated with interpolation. The CT images were scaled to the downsampled histology volumes using bicubic interpolation. 3. 2D T2-weighted MRI (128×128) to a MRI T1-weighted brain volume (181×217×181). A realistic simulated T1-weighted MRI volume of a normal brain (Volume 3) and corresponding T2-weighted images were obtained from the BrainWeb database at McGill University.24,25 The purpose of this simulator is to provide researchers with ground truth data for image analysis techniques and algorithms. The volume is isotropic, with 1 mm resolution on all three axes. The data are quantized to 8-bits. The T1 simulations had 3% noise, while the T2 volume was noise-free. 4. 2D PD-weighted MRI (128×128) to a MRI T2-weighted brain volume (181×217×181). Simulated PD- and T2-weighted MRI of a brain with multiple sclerosis lesions was also obtained from BrainWeb at McGill University. The T2 volume had 3% noise, while the PD images were contaminated with 9% noise. The large amount of noise in the PD images reduces the contrast of many of the intensity features that are useful in computing similarity metrics. Therefore, registrations with this volume and set of images are considered to be particularly difficult.

(a)

(b)

Figure 5. Ultrasound-to-histology registration. (a) Slice from abdominal histological volume. (b) Corresponding simulated ultrasound B-scan.

(a)

(b)

Figure 6. CT-to-histology registration. (a) Slice from histological head volume. (b) Corresponding CT image.

Proc. of SPIE Vol. 5032

1095

To test the proposed similarity metrics, rigid body registration experiments were performed, in which translations along the x-, y-, and z- axes (tx, ty, and tz, respectively) and Euler angle rotations about the x-, y-, and z-axes (α, β, and γ, respectively) were determined. For all experiments, ground truth transformations, x* = [tx* ty* tz* α* β* γ*]T, were known. Four 2D images from the modalities described above were registered to each of the 3D volumes. For instance, for Volume 1, four simulated B-scans with different 3D orientations were aligned to the histology volume. Each slice was initially oriented at Euclidean distances of 2, 4, 6, 8, and 10 voxels from ground truth. For each initial distance, 10 sets of misrotations were applied, with angles ranging from ±5° to ±30° from ground truth. During the registration process, partial volume interpolation6,26 was employed. Optimization was performed with Powell’s method. ~ Registration performance of the following similarity metrics was compared: I (normalized Shannon mutual ~ ~ information), I qR and I qS , with q ∈ {0.25, 0.5, 0.9, 1.1, 1.25, 1.5, 2}, and Iα, with α ∈ {0.1, 0.2, 0.5, 0.9, 1.1, 1.25, 1.5, ~ 2} (Many of these values were also used in a previous study).9 For I qS , the upper bound was computed as ~ I qS ,max ( X , Y ) = S q (Y ) + (1 − q ) S q ( X ) S q (Y ) . I qS was scaled to [0.5, 1.0], the same range as Shannon NMI. The probability densities were estimated from 64-bin histograms.

(

)

The performance of the metrics was compared on three criteria: (1) The correctness ratio, CR, is the ratio of registration trials classified as correct to all registrations. A registration is considered “correct” if the Euclidean distance between the final and ground truth translation parameters is strictly less than 1.75 voxels, and if the root meansquared error between the rotation matrices of the final and ground truth rotation parameters is strictly less than 0.25. (2) The efficiency is the average number of function evaluations (computation of the similarity metric) for correct registrations. (3) The accuracy (and corresponding precision, measured by standard deviation) is an actual numerical distance of the final transformation from ground truth. Accuracy, for correct registrations, is defined to be the mean of the distances from the four corners of an image transformed by the ground truth transformation, and the transformation returned by the registration algorithm. For perfect registration, this mean distance is numerically zero with zero standard deviation. In the current work, the image from which the corners are computed has dimensionality 10 × 10 voxels.

5. RESULTS ~ The ratio of correct registrations and efficiency values for the Shannon NMI ( I ), Tsallis, Renyi, and Iα measures ~ are shown by volume in Table 1. CR values higher than those for I are displayed in boldface. From these results, it is ~S seen that the I q and Iα measures generally have higher correctness ratios than Shannon NMI for specific parameter ~ ~ values. I qS outperformed I for 3 of the 4 volumes for q very close to 1 (recall that Sq → HS as q → 1), and for q > 1. The latter observation can be predicted on the basis of Figure 1, where the curves for q > 1 have a higher gradient as random variables move from independence to dependence. The Iα metrics also performed well, especially for the ~ ultrasound-histology and PD-T2 MRI registrations. However, I qS outperformed Iα for the CT-histology and T2-T1 MRI experiments. The Renyi metrics generally did not perform as well as Shannon NMI. The highest percentage of correct registrations for all metrics occurred with the ultrasound-histology (Volume 1) and CT-histology (Volume 2) registrations, and the lowest, with the PD-T2 MRI (Volume 4).

In efficiency, the Shannon metric generally required the fewest function evaluations for correct registrations. ~S I q required slightly more evaluations than Shannon NMI, but less than Iα, as evidenced in Table 1. The increased number of function evaluations required by Iα was also reported in a previous study.9 ~ ~ ~ The accuracies of the best performers, I , I qS , and Iα are shown in Table 2. From this table, it is seen that I is the ~ most accurate measure, followed by Iα, with I qS slightly less accurate than Iα.

1096

Proc. of SPIE Vol. 5032

For all metrics, as expected, the best results were observed for initial translational positions close to ground truth, with a decrease in correct registrations with increasing Euclidean distance. Thus, although many of the generalized measures has fewer misregistrations, the problem of entrapment in local minima is not completely avoided. ~

~

~

Table 1. Ratio of correct registrations (CR) and efficiencies for the Shannon ( I ), Renyi ( I qR ), Tsallis ( I qS ), and Iα information measures.

Metric ~ I ~R Iq

Par. − 0.25 0.5 0.9 1.1 1.25 1.5 2 0.25 0.5 0.9 1.1 1.25 1.5 2 0.1 0.2 0.5 0.9 1.1 1.25 1.5 2

~S Iq

Iα

CR Vol.1 0.65 0.08 0.34 0.54 0.58 0.57 0.39 0.29 0.08 0.36 0.71 0.83 0.80 0.86 0.63 0.46 0.66 0.79 0.84 0.86 0.85 0.86 0.61

Vol.2 0.53 0.03 0.11 0.49 0.56 0.51 0.39 0.16 0.09 0.45 0.61 0.67 0.68 0.58 0.41 0.18 0.34 0.49 0.57 0.63 0.55 0.54 0.33

Efficiency Vol.3 0.49 0.01 0.08 0.28 0.36 0.40 0.41 0.34 0.03 0.24 0.50 0.51 0.52 0.46 0.21 0.16 0.16 0.32 0.38 0.38 0.36 0.34 0.17

Vol.4 0.14 0.01 0.03 0.09 0.10 0.09 0.08 0.07 0.01 0.04 0.08 0.13 0.11 0.09 0.04 0.09 0.14 0.20 0.18 0.20 0.20 0.18 0.07

~

~

Vol.1 584 ± 140 658 ± 104 616 ± 158 560 ± 142 577 ± 155 557 ± 148 542 ± 123 510 ± 155 315 ± 136 484 ± 149 661 ± 176 662 ± 162 676 ± 174 708 ± 179 679 ± 191 1142 ± 303 1195 ± 484 986 ± 310 910 ± 259 872 ± 257 859 ± 260 874 ± 252 838 ± 247

Vol.2 534 ± 113 545 ± 322 539 ± 63 513 ± 108 502 ± 89 532 ± 119 509 ± 112 478 ± 117 404 ± 78 537 ± 104 564 ± 120 590 ± 136 595 ± 145 600 ± 132 622 ± 145 1060 ± 356 1016 ± 213 766 ± 177 703 ± 155 684 ± 172 685 ± 168 714 ± 176 820 ± 221

Vol.3 789 ± 164 1548 ± 21 1097 ± 327 807 ± 165 774 ± 211 795 ± 208 789 ± 209 803 ± 194 291 ± 326 795 ± 198 792 ± 193 799 ± 196 809 ± 186 869 ± 221 812 ± 236 1630 ± 785 1516 ± 659 1020 ± 289 942 ± 393 904 ± 321 935 ± 304 1003 ± 351 1068 ± 260

Vol.4 594 ± 99 509 ± 0 500 ± 79 637 ± 97 558 ± 147 574 ± 169 516 ± 147 540 ± 79 275 ± 0 447 ± 118 674 ± 170 652 ± 165 662 ± 198 636 ± 163 511 ± 238 1092 ± 353 1229 ± 375 1177 ± 332 1013 ± 295 959 ± 314 1122 ± 382 1045 ± 373 1071 ± 378

~

Table 2. Accuracy for the Shannon ( I ), Renyi ( I qR ), Tsallis ( I qS ), and Iα information measures.

Metric ~ I ~S Iq

Iα

Parameter −

Vol. 1 1.05 ± 0.65

Vol. 2 0.44 ± 0.45

Vol. 3 0.18 ± 0.46

Vol. 4 0.44 ± 0.30

0.9 1.1 1.25 1.5 0.5 0.9 1.1 1.25

1.08 ± 0.68 1.07 ± 0.69 1.09 ± 0.66 1.00 ± 0.70 1.15 ± 0.62 1.01 ± 0.69 1.02 ± 0.67 1.02 ± 0.67

0.78 ± 0.58 0.79 ± 0.57 0.73 ± 0.53 0.72 ± 0.57 0.62 ± 0.57 0.60 ± 0.55 0.57 ± 0.52 0.56 ± 0.50

1.14 ± 0.81 1.09 ± 0.84 1.01 ± 0.87 1.00 ± 0.87 0.89 ± 0.78 0.86 ± 0.82 0.87 ± 0.80 0.76 ± 0.81

1.25 ± 0.75 1.05 ± 0.71 1.21 ± 0.82 1.31 ± 0.71 1.43 ± 0.55 1.50 ± 0.57 1.32 ± 0.61 1.37 ± 0.68

Proc. of SPIE Vol. 5032

1097

6. DISCUSSION It has not yet been proven that information theoretic similarity measures are optimal.4 In many instances, the global minimum of the registration function does not occur at the correct transformation, as has been reported by other investigators.4 In addition, sensitivity to interpolation artifacts9,26 and irregularity in the metric function may lead to many misregistrations, as was the case with the noisy PD images (Volume 4). However, the information theoretic measures have been shown to have a high success rate overall, and the current work contributes to the study of these measures by applying generalized metrics to biomedical image registration. ~ The success of the Tsallis information measure I qS , (11) can be explained to some extent in terms of properties of the Tsallis entropy. Recall that information based on the Tsallis entropy is given as16: I qS ( X , Y ) = S q ( X ) + S q (Y ) + (1 − q ) S q ( X ) S q (Y ) − S q ( X , Y ) .

(12)

If X and Y are statistically independent, then S q ( X , Y ) = S ( X ) + S (Y ) + (1 − q) S ( X )S (Y ) . The ratio of the Tsallis ~ ~ information to the upper bound, I qS , measures the degree of dependence between random variables.16 If I qS with q > 0 is plotted as a function of the independence of the variables X and Y, the curve runs from 0, indicating complete independence of X and Y, to unity, indicating a one-to-one correspondence between X and Y; that is, X and Y are maximally correlated (Figure 1(b)). There is also an optimal value of q, qopt, for a given degree of correlation, for ~ ~ which I qS is most capable of detecting small variations of correlation among the variables. That is, the gradient of I qS is most sensitive at qopt.16 However, there are as yet no guidelines for selecting qopt,16 except possibly by experiment. It should not be expected that there is one qopt for each problem. For the registration experiments presented in the current study, values of q close to unity (q = 0.9, 1.1) and slightly higher than unity (q = 1.1, 1.25, 1.5) resulted in a high percentage of correct registrations. For low orders (q = 0.25, 0.5), the basins of attraction for the minima are narrower, and the surrounding landscape is flatter, with many tiny minima “pores”. However, the irregularity of the landscape greatly increases for larger q, such as q = 2. Although the regions surrounding the basin of attraction are not flat, as they are with low orders, the increase in the number of clearly discernable local minima poses challenges for optimization algorithms. Furthermore, there are possibly computational difficulties associated with very high or very low q. As the individual intensity probabilities are very small, loss of machine precision may accumulate, leading to small variations in the similarity metric function that may affect an optimization algorithm. Another consideration is that interpolation artifacts are encountered during the registration process.26 These errors affect the intensity histogram, and are magnified by high orders of entropy. ~R I q showed promising results in a previous study, where it outperformed normalized Shannon mutual information in both correctness and efficiency.27 In that study, 2D-to-2D registration was performed on an MRI reference image and a corresponding simulated B-scan. However, in the current work, the Renyi measure had a lower ratio of correct registrations than for the Shannon measure. The fact that good performance – in fact, better performance than Shannon mutual information – with this measure (and the R-norm metric) was observed in a different set of experiments27 indicates that the success of the similarity metrics is highly dependent on the modalities being registered.

Finally, it must be emphasized that very good performance was attained with q values close to unity. As demonstrated in many studies, the Shannon mutual information has proven to be a very effective similarity metric in biomedical image registration. Thus, varying q slightly from the Shannon limit value of q = 1 has the effect of only slightly altering the Shannon metric registration function. Specifically, use of Tsallis information measures with q close to one can be considered as using a “modified” version of the Shannon mutual information, rather than a completely different metric. Additionally, it was suggested that the Shannon measure may be used in the early stages of registration, and that generalized measures may be used to improve the final accuracy.9 In this study, by contrast, the high accuracy of the Shannon measure suggests that generalized metrics in the early, more “global” optimization stages can be followed by utilization of the Shannon measure to accurately determine the correct registration transformation.

1098

Proc. of SPIE Vol. 5032

7. CONCLUSIONS The results presented in this paper demonstrate that similarity metrics based on nonadditive entropy, specifically the Tsallis entropy, often produce fewer misregistrations than the widely used Shannon measure. They also generally require fewer function evaluations than Iα information. However, for correct registrations, the Shannon metric was more accurate than either the Tsallis measure or Iα information. Furthermore, as the curves in Figure 1 predict, better registrations occur for q > 1 for the Tsallis measure. However, the best results occur for q close to unity. As the Tsallis entropy becomes the Shannon entropy as q → 1, the former measure can be considered as a “slight deviation” from the latter, for q close to unity. Generalized metrics can thus be considered as modifications adjustments to the Shannon measure, making it more conducive to optimization. Generalized similarity metrics are presented as complementary to the Shannon measure (and other metrics), and not as replacements. A promising future direction is to utilize the parameterization of the generalized measures by adaptive parameter adjustment during the course of the optimization. As shown in this work, parameterized generalized measures frequently exhibit increased success if the parameter values deviate slightly from unity (in which most of the measures specialize to corresponding Shannon metrics). Therefore, it may prove beneficial that these metrics adapt the values of their parameters in response to the progress of the search. Adaptive generalized measures may be relatively broad in the early stages of the search to widen the basin of attraction, consequently drawing the search into the vicinity of the minimum. As the search progresses, parameters may be adapted to sharpen this region, providing faster convergence. Finally, the Shannon measure can be used in the final stages of the search for increased accuracy. To implement adaptive measures, feedback must be obtained from the optimization algorithm. In this respect, Powell’s method, which is a direction set technique, may not provide enough feedback to allow similarity metric adaptation, and simplex methods, such as the Nelder-Mead algorithm, may be more appropriate for this purpose. Adaptation is desirable because a single metric cannot be the best performer in all registration situations. Alternative optimization approaches may also be less susceptible to registration errors resulting from complex registration functions.9 Furthermore, the selection of an “optimal” parameter, or even whether such a parameter exists, is an open question that cannot be determined from experimental results alone.9,27 However, generalized metrics merit further study on a rigorous, mathematical basis, to determine the registration situations in which their use is most appropriate. Although generalized metrics were shown improve registration performance (in terms of correct registrations) in many circumstances, this paradigm should also be studied in conjunction with multiresolution strategies or incorporation of other criteria, such as gradient information.3,28 Finally, validation on a wide range of clinical data is also required.

ACKNOWLEDGEMENTS The authors wish to thank the U.S. National Library of Medicine-National Institutes of Health Visible Human Project for making their data available. The authors also acknowledge the BrainWeb project at McGill University in Montréal, Quebec, Canada (http://www.bic.mni.mcgill.ca/brainweb/), for internet-based generation MRI brain volumes.

REFERENCES 1. 2. 3.

D. L. G. Hill and P. Batchelor, “Registration methodology: concepts and algorithms,” in Medical Image Registration, J. V. Hajnal, D. L. G. Hill, and D. J. Hawkes, Editors. CRC Press, Boca Raton, FL, 2001. M. Čapek, L. Mroz, and R. Wegenkittl, “Robust and fast medical registration of 3D-multimodality data sets,” Proc. of Medicon 2001, Part I, pp. 515-518, 2001. A. Roche, X. Pennec, G. Malandain, and N. Ayache, “Rigid registration of 3-D ultrasound with MR images: a new approach combining intensity and gradient information,” IEEE Transactions on Medical Imaging 20, pp. 10381049, 2001.

Proc. of SPIE Vol. 5032

1099

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.

22. 23. 24. 25. 26. 27.

28.

1100

D. L. G. Hill, P. G. Batchelor, M. Holden, and D. J. Hawkes, “Medical image registration,” Physics in Medicine and Biology 46, pp. R1-R45, 2001. J. B. A. Maintz and M. A. Viergever, “A survey of medical image registration,” Medical Image Analysis 2, pp. 137, 1998. F. Maes, A. Collignon, D. Vandermeulen, G. Marchal, and P. Suetens, “Multimodality image registration by maximization of mutual information,” IEEE Transactions on Medical Imaging 16, pp. 187-198, 1997. W. M. Wells III, P. Viola, H. Atsumi, S. Nakajima, S., and R. Kikinis, “Multimodal volume registration by maximization of mutual information,” Medical Image Analysis 1, pp. 35-51, 1996. C. Studholme, D. L. G. Hill, and D. J. Hawkes, “An overlap invariant entropy measure of 3D medical image alignment,” Pattern Recognition 32, pp. 71-86, 1999. J. P. W. Pluim, J. B. A. Maintz, and M. A. Viergever, “f-information measures in medical image registration,” Proc. of SPIE Medical Imaging: Image Processing, pp. 579-587, 2001. B. Ma, A. Hero, and J. Gorman, “Image registration with minimal spanning tree algorithm,” Proc. the IEEE International Conference on Image Processing (ICIP), Vancouver, BC, Canada, 2000. Y. He, A. B. Hamza, and H. Krim, “An information divergence measure for ISAR image registration,” Proc. IEEE Workshop on Statistical Signal Processing, Singapore, 2001. H. Neemuchwala, A. O. Hero, and P. Carson, “Feature coincidence trees for registration of ultrasound breast images,” Proc. IEEE International Conference on Image Processing, Thesaloniki, Greece, 2001. A. Renyi, Probability Theory, North-Holland, Amsterdam, 1970. J. H. Havrda and F. Charvat, “Quantification methods of classification processes: concepts of structural α entropy,” Kybernetica 3, pp. 30-35, 1967. C. Tsallis, “Possible generalization of Boltzmann-Gibbs statistics,” Journal of Statistical Physics 52, pp. 479-487, 1988. L. Borland, A. R. Plastino, and C. Tsallis, “Information gain within nonextensive thermostatistics,” Journal of Mathematical Physics 39, pp. 6490-6501, 1998. S. Arimoto, “Information-theoretical considerations on estimation problems,” Information and Control 19, pp. 191194, 1971. D. E. Boekee and J. C. A. Van der Lubbe, “The R-norm information measure,” Information and Control 45, pp. 136-155, 1980. A. P. Sant’anna and I. J. Taneja, “Trigonometric entropies, Jensen difference divergence measures, and error bounds,” Information Sciences 35, pp. 145-156, 1985. J. N. Kapur, Measures of Information and Their Applications, John Wiley & Sons, New York, NY, 1994. M. S. Mega, S. S. Chen, P. M. Thompson, R. P. Woods, T. J. Karaca, A. Tiwari, H. V. Vinters, G. W. Small, and A. W. Toga, “Mapping histology to metabolism: coregistration of stained whole-brain sections to premortem PET in Alzheimer's disease,” Neuroimage 5, pp. 147-153, 1997. A. W. Toga and P. M. Thompson, “The role of image registration in brain mapping,” Image and Vision Computing 19, pp. 3-24, 2001. V. M. Narayanan and P. M. Shankar, “Non-Rayleigh statistics of ultrasonic backscattered signals,” IEEE Trans. on Ultrasonics, Ferroelectrics and Frequency Control 41, pp. 845-852, 1994. D. L. Collins, A. P. Zijdenbos, V. Kollokian, J. G. Sled, N. J. Kabani, C. J. Holmes, and A. C. Evans, “Design and construction of a realistic digital brain phantom,” IEEE Transactions on Medical Imaging 17, pp. 463-468, 1998. R. K.-S. Kwan, A. C. Evans, and G. B. Pike, “MRI simulation-based evaluation of image processing and classification methods,” IEEE Transactions on Medical Imaging 18, pp. 1085-1097, 1999. J. P. W Pluim, J. B. A. Maintz, and M. A. Viergever, “Interpolation artefacts in mutual information-based image registration,” Computer Vision and Image Understanding 77, pp. 211-232, 2000. M. P. Wachowiak, R. Smolíková, G. D. Tourassi, and A. S. Elmaghraby, “Generalized mutual information as a similarity metric for multimodal biomedical image registration,” Proc. 2nd Annual IEEE EMBS/BMES Joint Conference, Houston, pp. 1005-1006, 2002. J. P. W. Pluim, J. B. A. Maintz, and M. A. Viergever, “Image registration by maximization of combined mutual information and gradient information,” IEEE Transactions on Medical Imaging 19, pp. 809-814, 2000.

Proc. of SPIE Vol. 5032