Multi-Start Optimisation with Perturbations

Following the previous search stage (at 8mm scale) there are usually several local minima selected as candidates for initialising more detailed searches for the global minimum. This stage (at 4mm scale) performs a local optimisation for the best of these candidate transformations. In addition, it takes several perturbations of the candidate transformations and performs local optimisation of these perturbations. Finally, the single best (minimum cost) solution is selected from among these optimisation results. In practice, the three best candidates are taken from the previous stage, together with ten perturbations of each candidate. Two perturbations are applied to each rotation parameter, each being half the magnitude of the fine search step size from the previous stage. As well as these six rotational perturbations, four perturbations in scale ( $\pm 0.1, \pm 0.2$) are also applied. The number and size of the perturbations used is arbitrary, with these values chosen here being selected largely from experience with the magnitude and type of typical mis-registrations. This approach of trying several candidate solutions is effectively a multi-start strategy similar to that used in genetic algorithms and other global optimisation methods. Furthermore, the use of ``local'' perturbations is similar to the way in which alternatives are generated in simulated annealing. It has been found empirically that the combination of these strategies, together with the initial search, avoids getting trapped in local minima to a much greater extent than for a local optimisation method alone within a multi-resolution framework.