next up previous
Next: Re-optimising with Perturbations Up: Global Optimisation Method Previous: Resolution Adapted Powell's Method

   
Initial Search

As shown in section 3.1, the amount of time required to perform all but the most perfunctory search is prohibitive with any sub-sampling where the voxels are smaller than 8mm cubed. However, in order to find the global minima reliably, some search must be performed.

To allow a useful search to be conducted in under 20 minutes, a multi-stage search was devised. This search is based on the observation that finding the correct orientation, or rotation, is the most difficult task since the three rotation parameters are highly coupled and most erroneous registrations have an incorrect orientation. Therefore, the search concentrates on the rotational part of the transformation space. The outline is:

1.
Initially form a coarse grid over the 3 rotation parameters (Euler angles), with M angles per dimension (total of M3 grid points).
2.
At each point in the grid, perform a 4 DOF local optimisation to find the translation and (global) scale -- using initial values of translation = 0 and scale = 1.
3.
Calculate the median scaling from the optimised results.
4.
Form a finer grid over the rotation angles, with N angles per dimension.
5.
Provide initial parameter estimates for translation at each fine grid point by interpolating the optimised translation values found at the coarse grid points.
6.
Evaluate the cost function (no optimisation) at all points on the fine grid with initial scale set to the previously calculated median scale.
7.
Find all points that have lower cost than their neighbours (local minima) and perform a 7 DOF optimisation for each of these points, storing the results of the transformations (and costs) both before and after optimisation.

Ideally, by choosing a large value for M, the initial stage (steps 1 and 2) of the search would be sufficient. However, as it typically takes about 2 seconds to perform each 4 DOF optimisation in our implementation, only a small value for M can be chosen if the search is to be carried out in a limited amount of time. Therefore another two stages are introduced into the search to allow a finer grid (N > M) to be used.

To find the cost at each point on a finer grid (where N > M) only a single evaluation, rather than an optimisation, is done. However, in order that the cost value is close to the optimal value it is necessary to ensure than they are not significantly influenced by translation and scale differences. In order to achieve this, good initial estimates for these parameters are required. The initial estimates used are obtained from the parameters stored after optimisation on the coarse grid. Since the translation is strongly coupled to the rotation (that is, the correct translation is significantly different for different rotation values) the initial translation parameters are obtained by interpolating the values from the coarse grid. However, the scaling parameter is not strongly coupled with rotation, and so a single, robust estimate (the median) is taken from all the coarse grid values.

In practice, our implementation takes about 2 seconds for each 4 DOF optimisation, since the extra overhead is proportionally higher at the 8mm resolution. Therefore, even lower values for M and N are required than the values given in section 3.1 would suggest. However, it has been found that values as low as M=6 and N=20 still give good results.

This method relies on certain assumptions, namely:

1.
at least one point will occur in the global minimum's basin of attraction, and be lower than its neighbours.
2.
the initial estimates for translation and scale, provided by the coarse grid 4 DOF optimisation, are reasonable.
3.
the typical anisotropic scaling and skews are sub-voxel with 8mm cubed voxels, and can be ignored.

The first two assumptions can be partly justified by the results shown in section 3.3. Firstly, it can be seen that the typical size of the global minimum's basin of attraction is large enough that a suitably fine grid should manage to have at least one point within the basin of attraction. Secondly, the cost varies more slowly, and more smoothly, with translation and scale than it does with rotation. Consequently, it is more likely that the change in rotation between grid points will be the dominant cause of changes in the cost function, rather than small errors in the initial estimation of scale and translation.



 
next up previous
Next: Re-optimising with Perturbations Up: Global Optimisation Method Previous: Resolution Adapted Powell's Method
Mark Jenkinson
2000-05-10