Difficulties

The standard formulation described above is based, in most cases, on the following assumptions:

1.

the location of the global minimum of the cost function, T^*, corresponds to the desired solution,

2.

at the maximum sub-sampling n = n₀, the global minimum is the nearest minimum to the starting position and can be found by local optimisation: $T^*_{n_0} \approx \ensuremath{{\mathrm{Op}}} _{n_0}(T_0)$,

3.

the location of the global minimum found using one sub-sampling, n₁ is inside the basin of attraction (as defined by the optimisation method) of the global minimum for the next sub-sampling, n₂: $T^*_{n_2} \approx \ensuremath{{\mathrm{Op}}} _{n_2}(T_{n_1})$.

Here the basin of attraction for some minimum is defined as the set of initial transformations that, after successive applications of the local optimisation algorithm, converge to that minimum. That is: $B(T) = \{ \, T_0 \; \vert \; \ensuremath{{\mathrm{Op}}} _{n}^M(T_0) \rightarrow T \;\; \mathrm{as} \;\; M \rightarrow \infty \}$. This set depends on the precise optimisation algorithm used and should be empty for any T that is not a minimum. Furthermore, such sets have very complicated boundaries, often with a fractal nature.

However, these assumptions do not always hold. The following describes some cases where they are not true.

• If the cost function for some extreme transformation gives a low value then the global minimum will be (at least degenerately) given by this limiting case. For example, large scalings can create low cost values even though the registration is poor. Furthermore, limiting the domain is not a general solution to this as it would be necessary to guarantee that the cost at the edge of the domain was higher than the global minimum value which is unknown.
• Sub-sampling to lower resolutions may not reduce the number of local minima sufficiently. In fact, some work on interpolation [Pluim et al., 2000] has shown how it can actually create additional local minima.
• Minima will move in scale-space, which is a well known phenomenon, so that the location of a minimum for some sub-sampling may fall inside the basin of attraction of a different minimum for another sub-sampling.

To develop a reliable, automatic registration method it is necessary to examine these assumptions and tailor the method to this problem. In order to do this the characteristics of a typical cost function needs to be understood, and these are examined in the next section.