Using spanning trees for reduced complexity image mosaicing

Image mosaicing, i.e., reconstruction of an image from a set of overlapping sub-images, has numerous applications that include high resolution image acquisition of works of art. Unfortunately, optimal mosaicing has very large computational complexity that soon becomes prohibitive as the number of sub-images increases. In this paper, two methods which achieve significant computational savings by applying mosaicing in pairs of two sub-images at a time, without significant reconstruction losses, are proposed. Simulations are used to verify the computational efficiency and good performance in terms of matching error of the proposed techniques.