[cite] [home]
Next: Classification Up: Diffusion Tensor Imaging Previous: Rigid Registration   Contents

Subsections

# Nonrigid Registration

Nonrigid registration is the general term for an algorithm for the alignment of data sets that are mismatched in a nonlinear or nonuniform manner. The term ''matching'' is used to refer to any process that determines correspondences between data sets [32].

This chapter discusses all the methods that have been used to align two tensorfields with a nonrigid registration. The following series of steps are used:

1. Extract points with high local structure in one data set.
2. For each extracted point find the best corresponding point in the second data set.
3. Check the displacement for the selected points and remove overlapping displacements.
4. Interpolate the displacement for the selected and matched points to get a displacement field for the whole data set.
5. Apply the interpolated displacement field on the second data set.
6. Eventually improve the alignment by using multiple resolutions or looping.

For simplicity in this section any field is called a three dimensional image with values at position . The values can therefore be any of the types scalar, tensor or eigensystem. The stationary image is and the moving . The transformation from to is denoted :

 (7.1)

More precisely the goal is to find
 (7.2)

which is closest to :
 (7.3)

The displacement field is

 (7.4)

so that
 (7.5)

A point at position in in the stationary image has a neighborhood which is a small window of size . A neighborhood of a point at position in of size is referred to as . These notation conventions are summarized in Figure 7.1. Furthermore a collection of n points with is denoted .

Every point for which is known can be displaced to a new location . If is known for every point the whole image can be displaced. The resulting image though will have points which have not been assigned a value from . That is, the function is not directly invertible, since is not necessarily onto and not necessarily one to one.

As a result an image is expected that has values everywhere. Instead of interpolating the points to get missing values for the matching procedure can be inverted to get a function . This second approach is used here. Thus points are selected in the stationary image . When the corresponding points have been found and the displacement field interpolated this leads to a displacement approximated by from the stationary to the moving image. Now for every position in a resulting image the position where the values came from is known, and the transform is onto, so that is empty.

# Point Extraction

To find a correspondence between two points both points must be uniquely identifiable in a certain neighborhood, so that the correspondence is unambiguous. The term ''certain neighborhood'' means a region that is large enough so that the corresponding point certainly lies in it but small enough so that no two equal correspondences are present. This is well known as the ''Aperture Problem''. This section assumes that this constraint is met.

A point on a line for example cannot be unambiguously matched to a point on a line in the second image if no additional information is provided. A corner instead has a unique counterpart in both images and can therefore be matched uniquely, of course only if the corner is present in both images. A measure of cornerness tells how much structure there is around a certain point.

In the scalar case the derivatives of the image are computed and the outer product of the resulting vector is built, which is by definition the correlation matrix . With the derivatives

 (7.6)

becomes
 (7.7)

which is a symmetric matrix where the determinant always equals zero. A classical measure of local structure is to use the local expectance of the values in , i.e. averaging the components of over a window of size .
 (7.8)

This matrix may have a nonzero determinant, since , as long as . An eigensystem decomposition of allows a classification of the point under inspection in edge, corner or flat region [1]. For the two dimensional case this is illustrated in Figure 7.2.

can be seen as a tensor of order 2. The eigenvalues can be illustrated by an ellipsoid. The rounder the ellipsoid the bigger the cornerness, i.e. the measure close-sphere in Equation 4.15 is a measure for cornerness in this case.

For any symmetric matrix the trace is the sum of the eigenvalues

 (7.9)

as can be seen by using Equation 4.8. The determinant is the product of the eigenvalues
 (7.10)

Using only these measurements to obtain a value for the cornerness avoids doing an eigensystem decomposition.

Ruiz and co-workers [15] propose to use points above a threshold

 (7.11)

and remove false detections by thresholding the result with
 (7.12)

with the dimension of the image, i.e. usually 2 or 3. The value of varies between one and zero depending on the shape of the ellipsoid, one being a perfect sphere.

Here a modified version is used, where the two thresholds are incorporated in one formula. The structure is then defined as

 (7.13)

where can usually be set to 1% or 0.01. will have values between zero and close to one.

Using the expectance causes blurring of the point-selection since high values are diffused. The trace of has a non-zero value without averaging and is an edge detector [1], as

 (7.14)

There are now several options to improve the point-selection. Before the process is started an anisotropic filter can be applied to enhance edges. After using a point-selection as described the result can be masked with the trace of (not !) to undo the blurring effect of the expectance computation. Finally the local maxima of a region of the function 7.13 can be selected to get single voxel positions.

In the case of tensorfields the points should be extracted from a structure with six independent values. For each independent component of the tensor a matrix can be computed and the sum over the components of these matrix used as a final matrix

 (7.15)

Expectance and sum are commutative, i.e.
 (7.16)

The collection of points that have enough structure and have therefore been selected, is referred to as

The parameters for the point-selection in the program nonrigidreg are described in Table A.3 in page .

# Matching

The matching process involves two steps: First finding the best corresponding points in the second image and second locally optimizing the displacements found.

For each selected point in a neighborhood is selected. At the same position in the moving image a search window is selected, i.e. an area where the corresponding point is assumed to lie. For each point in this search-window a neighborhood is compared to the neighborhood and a value measuring the result of the comparison assigned to . Two different measurements of similarity for scalar data are implemented.

#### Maximal normalized cross correlation

The normalized cross correlation (NCC) between two windows and of same size is defined as
 (7.17)

This is computed for every position . The position where the NCC is maximal, i.e. closest to one, is the best match and therefore the selected correspondence.

#### Least square error (LSE)

Here the distance between the image values is used as measure
 (7.18)

and the minimal value for all is the location where the matching point is selected.

#### Search Strategy

In both cases, the search strategy is based on brute force, that is, no local optimization to find the best match is done. The windows that are compared, and , can be weighted with a Gaussian function prior to comparison. This makes the matching less sensitive to the size of the window and increases the ''importance'' of the center points and .

Instead of simply selecting the best matching value the resulting vectors NCC() respectively LSE() are sorted so that NCC(), LSE() are the best and NCC(), LSE() the worst matches. Before accepting a match the sorted vectors can be analyzed. If the best and worst match are too close to each other, i.e. NCC() NCC(), there is not enough structure in the search-window so that the match should be ignored. Furthermore if there are several equally or almost equally good matches the displacement field in the neighborhood should be considered and matching should additionally be based on smoothness of the over-all displacement field. Only the first approach has been implemented.

In a second step, when for all points a correspondence has been found, the displacements are checked. Overlapping displacements, i.e. displacement vectors that cross each other are eliminated since the tissue of a subject should not be folded. Whenever two displacements cross each other the shorter displacement is kept and the larger removed.

# Kriging

In order to obtain a displacement field for the whole volume, the sparse displacements obtained at single locations have to be interpolated. This section describes the selected interpolation method. It is assumed that the sparse displacement field has an unknown underlying random field. References [35] and [38] give a good introduction and a simple example on how to use Kriging.

Kriging interpolation originates from geostatistics and is known to be the best linear unbiased estimator because it is theoretically capable of minimizing the estimation error variance while being a completely unbiased estimation procedure [34].

Kriging is a modified linear regression technique that estimates a value at a point by assuming that the value is spatially related to the known values in a neighborhood near that point. Kriging computes the value for the unknown data point using a weighted linear sum of known data values. The weights are chosen to minimize the estimation error variance and to maintain unbiasedness in the sampling. Unlike other techniques for scalar values, Kriging bases its estimates upon a dynamic, not static, neighborhood point configuration and treats those points as regionalized variables instead of random variables. Regionalized variables assume the existence of regions of influence in the data. In Kriging each region is analyzed to determine the correlation or interdependence among the data in the region and this is encoded through a function called a variogram. For the unknown value at the position within the neighborhood of known points with known values the basic Kriging equation is:

 (7.19)

is the actual value at a point , and is the number of known points used to compute . The 's are the regionalized variables and the 's the weights. Unlike other techniques which also use a weighted sums, in Kriging the weights are not selected based solely upon the distance between sampled and unsampled points. Kriging does not assume that the variability of the data is linear [33].

Optimal weights are determined by enforcing the error expectation in the estimate be zero

 (7.20)

and the error variance be minimal

 (7.21)

where is the expected value or mean and the mean-square-error of the dissimilarity between the two variables and . These two conditions make the best linear unbiased estimator and are the base equations to derive the Kriging system of equations. Furthermore the unbiasedness implies that the weights must sum up to one:

 (7.22)

As an exact interpolator, Kriging predicts known values with zero error. Using the method of Lagrange Multipliers it is possible to obtain a linear equation for the weights of the estimator, where is the evaluation of the variogram between the points and :
 (7.23)

#### Variogram Models

The variogram expresses the variability of a spatial process as a function of distance and direction. Suppose the data is collected according to a random spatial process in , i.e. we observe . It is assumed that is only a function of the distance vector . The process is said to be isotropic if it only depends upon , the Euclidean distance between sites. Then the function is called the variogram, while is the semivariogram. Typically, the variogram is assumed to increase with the distance , assuming that the difference between pairs of observations closer in space should tend to exhibit less variability than that for pairs further apart. It is often the case that after a certain distance, called the range , will level out at a value called the sill. The range is therefore the distance beyond which the deviation in the values does not depend on distance and hence values are no longer correlated.

In addition, there may be a discontinuity at the origin, the so-called nugget effect. This means that the fitted model does not pass through the origin, but intersects the y-axis at a positive value of , which is . This quantity is an estimate of , the residual, that represents spatially uncorrelated noise associated with any value of a random variable at . This terminology is illustrated in Figure 7.3.

The relationship between the variogram and the covariance is given by [36]

 (7.24)

where the sill is , the range and a parametric correlation function. The semivariogram is also a graphical display of , i.e. semivariance, versus distance.

Table 7.1 is a collection of different parametric correlation functions. Figure 7.4 shows the semivariogram (Equation 7.24) for the functions in Table 7.1 with and .

Table 7.1: Common Parametric Correlation Forms ([36] and [35]).
 Name Linear Exponential Gaussian

In most cases the variogram is unknown and is approximated by a process called structural analysis. As there is no prior information on the resulting displacement field this approach is not applicable. Instead different variogram models are implemented so that the best model can be empirically determined by comparing the results of the registration process.

An example interpolation is shown where a synthetic example is randomly sampled at 10% and interpolated using the linear variogram model and two different neighborhoods (see Figure 7.5).

Figure 7.5:     Example of using Kriging interpolation. (a) Original image; (b) Randomly selected 10% of the points; (c) Interpolation using linear Kriging and neighborhood 5; (d) Interpolation using linear Kriging and neighborhood 10. It can be seen that in (d) a value reaches further so that the transition from black to white is smoother.
 (a) (b) (c) (d)

# Local Warping of Tensors

After the displacement field is known for every position in the image the image can easily be computed since every location in ''knows'' where it comes from. This is done for each component separately. Again, as with the rigid registration, the problem arises, that tensors are structures and have to be locally transformed according to the displacement.

Three different local transformations are presented and discussed here. The first is proposed in reference [15]. is the tensor in image that is displaced by to a new position . The transformation is . Then the local transformation is applied on to get the final tensor at the position .

#### Local Warp with Scaling

The deformation gradient is computed which is the differential of the transformation or the Jacobian matrix of the mapping
 (7.25)

where is the transformation in the th dimensions. Combining Equations 7.1 and 7.6
 (7.26)

can be expressed in terms of the displacement
 (7.27)

The local relation of and is then
 (7.28)

This local mapping of a tensor includes rotation, scaling and distortion of the tensor. Figure 7.7 illustrates the result of this method on a synthetic square (see Figure 6.1 on page ). The applied displacement field is shown in Figure 7.6.

As can be seen, the shape of some tensors has been changed quite a bit.

#### Local Warp without Scaling

In a second approach the scaling of the tensors is removed while still allowing the tensor to change shape. This is done by rescaling the result of Equation 7.28 so that the determinant of is the same as for :
 (7.29)

The result is displayed in Figure 7.8.

#### Local Rotation

Using the Single Value Decomposition (SVD) the matrix can be decomposed in a pure rotation component and a strain component . The SVD for any non-singular square matrix is given by
 (7.30)

where and are orthogonal matrices and is a diagonal matrix. The matrix can be now written in the form
 (7.31)

where is a matrix with orthogonal columns and is a symmetric, positive semidefinite matrix 7.1. is said to be a pure strain if with the identity matrix, while if , is called a rigid rotation at this position [15]. Therefore any deformation of the tensor can be avoided by applying in Equation 7.28 instead of . For the case of the synthetic square this can be seen in Figure 7.9. This form of local rotation is the transformation mentioned in Section 4.2 and shown in Figure 4.6.

Again, as was done for the rigid transformation, it is argued here to use this transformation when nonrigidly aligning the tensor images. When aligning two different subjects the structures should not be changed. In the scalar case gray-values are displaced to the new position but their value is not changed. Equivalently in the case of tensors, a local rotation is part of the transformation but changing the shape is not obvious and meaningful in all cases. The meaning of any local change would have to be studied for each application separately and even separately for each tissue, so that it is safest to not apply any strain. Also, if the point-extraction and the matching part of the nonrigid registration are based on measurements of the tensors that depend on the shape, changing the shape after the transformation leads to a change of the similarity. This can make the chosen displacement appear wrong after the local transformation.

The implementation allows to choose between any of the described local transformations (see Table A.3).

# Multi-scale Matching

The overall process can be improved in two ways; looping and matching using multiple resolutions. Looping is simple since the second loop does not need to know anything about the previous processing and can be seen as a completely independent matching process. If the overall displacement field should be known, i.e. not only the final match is of interest, the problem of combining the displacement fields is the same as for multiple resolution matching and will be discussed there. Figure 7.10 illustrates the principle of multi-scale matching as it has been implemented. The single steps are:
1. Optionally smooth the given images and with a Gaussian filter. This step is not useful when working with binary or segmented data, but for all data types that have continuous values.
2. Downsample the image to get and
3. a) Select points in the lowest level
b) Threshold the selection
4. Find the matches for the selected points, i.e. the displacements at this positions.
5. Upsample the displacements to all the higher levels.
6. Interpolate the displacements
7. Apply the interpolated displacements to the corresponding image
8. Copy the resulting image back
9. While set , else stop
10. Go to step 3
This form of multi-scale matching can certainly be improved. E.g. step 7 the displacement in higher levels would not need to be applied. Instead the resulting displacements could be added and in a final step the overall displacement could be applied on . Combining two displacement fields though is not a trivial problem. For at least one of the transformations the inverse has to be known, but cannot be computed directly as has been explained in the beginning of this chapter.

The size of the search-window is adapted to the current scale. For the lowest scale it is the specified search-window, divided by the number of scales times the scale-factor. When moving towards higher levels the search-window is a bit larger than twice the scale-factor, since any larger displacement should have been found in the lower levels.

# Measuring Results

To test the nonrigid registration synthetic displacement fields were generated and applied on different test images. The synthetic displacement is generated separately and independently for each component . First a maximal displacement is fixed. Then a regular grid with distance is built and each position is assigned a random value between . The sparse grid is interpolated using Kriging with a linear variogram model so that smooth random displacement fields are generated. is then applied to to get a test image . Then the nonrigid registration technique described in the previous sections is used to align back to .

Measuring the results, i.e. the improvement from

 (7.32)

to
 (7.33)

where is the data set, clearly depends on the similarity measurement. A visual inspection of the image gives a very good impression of the results.

For the binary test data measuring the improvement is trivial and boils down to be the number of voxel positions that have different values in each image. The same principle can be used when matching segmented data. Here the number of positions with different classes in each image is a meaningful measure for dissimilarity. In grayscale data counting positions where the graylevels are different is not very suggestive since this will be the case almost everywhere in the body. Of course the number should decrease as the border of the body should be better aligned after the registration, but this will be a small percentage. The total distance

 (7.34)

is much more suitable since it linearly weights the difference at each position. Similarity between tensor data sets needs to be defined to be able to use the last formula. Reference [16] proposes the inner product of two tensors
 (7.35)

being the equivalent to the vector product as similarity measure.

When registering medical data the goal is to align the structures of one data set to the other data set. Ideally the structures in both data sets and are known, e.g. by segmenting the data. The displaced structures can then be compared.

Different tests are documented in Table 7.2. The parameters used are explained in Table A.3 in Appendix A.6. The process for the case of the chessboard is illustrated in Figure 7.11 and for the segmented baby brain in Figure 7.12.

Table 7.2: Comparison of results when testing with synthetic deformation fields
 Test images Parameters used Results Chessboard and synthetic ./nonrigidreg 0 1938 points different displacement -m=0 -sw=21 -mw=9 -d=15 before matching, -r=20 -pm=2 -km=2 50 after matching MRI image and synthetic ./nonrigidreg 1 133016 total graylevel distance displacement -s=pointmatcherdata/cm.001 before matching, -o=pointmatcherdata/cm 42167 after matching -syn=pointmatcherdata/cm -mw=9 -sw=15 -m=1 -r=15

Figure 7.11:     Chessboard example for the nonrigid matching process. (a) Original image; (b) Synthetically displaced version; (c) Difference between (a) and (b); (d) Displacement field for nonrigid registration from (b) to (a), zoom into the center region; (e) Resulting match; (f) Difference between (a) and (e).
 (a) (b) (c) (d) (e) (f)

Figure 7.12:     Alignment of syntheticaly displaced MRI scan to original scan as an example for the nonrigid matching process. (a) Original image; (b) Synthetically displaced version; (c) Difference between (a) and (b); (d) Displacement field for nonrigid registration from (b) to (a); (e) Resulting match; (f) Difference between (a) and (e).
 (a) (b) (c) (d) (e) (f)

#### Footnotes

... matrix7.1
http://www.cs.ut.ee/toomas_l/linalg/lin2/node26.html

[cite] [home]
Next: Classification Up: Diffusion Tensor Imaging Previous: Rigid Registration   Contents
Raimundo Sierra 2001-07-19