Photomosaic Generation by Rearranging Subimages, with GPU Acceleration

The main contribution of this paper is to show a new photomosaic generation method by rearranging subimages of an image. In the photomosaic generation, an input image is divided into small subimages and they are rearranged such that the rearranged image reproduces another image given as a target image. Therefore, this problem can be considered as a combinatorial optimization problem to obtain the rearrangement which reproduces approximate images to the target image. Our new idea is that this rearrangement problem is reduced to a minimum weighted bipartite matching problem. By solving the matching problem, we can obtain the best rearrangement image. Although it can generate the most similar photomosaic image, a lot of computing time is necessary. Hence, we propose an approximation algorithm of the photomosaic generation. This approximation algorithm does not obtain the most similar photomosaic image. However, the computing time can be shortened considerably. Additionally, we accelerate the computation using the GPU (Graphics Processing Unit). The experimental results show that the GPU implementations for the optimization algorithm and the approximation algorithm can accelerate the computation to 40 and 66 times faster than the serial CPU implementation, respectively.