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:
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:
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.