Fast Multigrid Optimal Mass Transport for Image Registration and Morphing

In this paper we present a novel, computationally efficient algorithm for nonrigid 2D image registration based on the work of Haker et al.[1, 2]. We formulate the registration task as an Optimal Mass Transport (OMT) problem based on the Monge-Kantorovich theory. This approach gives a number of advantages over other conventional registration methods: (1) It is parameter free and no landmarks need to be specified, (2) it is symmetrical and the energy functional has a unique minimiser, and (3) it can register images where brightness constancy is an invalid assumption. Our algorithm solves the Optimal Mass Transport program via multi-resolution, multi-grid, and parallel methodologies on a consumer graphics processing unit (GPU). Although solving the OMT problem has been shown to be computationally expensive in the past, we show that our approach is almost two orders magnitude faster than previous work and is capable of finding transport maps with optimality measures (mean curl) previously unattainable by other works (which directly influences the quality of registration). We give results where the algorithm was used to register 2D short axis cardiac MRI images and to morph two image sets from a SOHO solar flare image sequence.