Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)We propose an automatic 3D medical image registration method that combines the watershed transform from greyscale marker, to effectively reduce the number of key points needed for registration, with a robust optimisation algorithm, called multi-scale parameter search (MSPS), to quickly estimate the mapping function. We evaluate it for rigid and intra-subject registration of pre- and post-surgery MR-T1 images of the brain. The visual analysis of its effectiveness is facilitated by a colour-coding scheme. Extensive experiments show that our approach is very accurate, robust to noise and provides 3D registration in less than 40 s, with no multi-resolution image schemes needed. We also evaluate MSPS on a testbed of 12 optimisation benchmark problems, in comparison with well-known optimisers, such as particle swarm optimiser, simulated annealing and differential evolution, showing that it can also be explored in other applications.52138156FAPESP [2007/52015-0, 2010/00994-8, 2010/05647-4, 2013/11359-0]CNPq [302970/2014-2, 477662/2013-7, 304352/2012-8, 479070/2013-0]CAPESMicrosoftFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)