Photomosaic Generation by Rearranging Divided Images

Abstract

In this paper, we propose a photomosaic generation method by rearranging divided images. 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, we can consider this problem as combinatorial optimization 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 method of the photomosaic generation. This approximation method does not obtain the most similar photomosaic image. However, the computing time can be shortened considerably. Additionally, we accelerate the approximation method using the GPU (Graphics Processing Unit). The experimental result shows that the GPU implementation attains a speed-up factor of 25 times over the sequential CPU implementation.