Mosaic Image Generation Method Based On Geodesic Voronoi Diagram

Mosaic is a non-photorealistic rendering method, which synthesizes a large image by packing a collection of small colored tiles. This thesis presents a novel feature-preserving method for mosaic image generation, which is based on Voronoi diagram under a non-Euclidean metric. Each Voronoi cell is taken as a tile in the mosaic image. We combine the geodesic distance and centroidalVoronoi diagram.The geodesic distance is defined by the feature edges which are first extracted from the input image automatically. A metric matrix is defined such that the edges of the Voronoi diagram under the new metric align with the feature edges, preserving the feature information. We use the fast marching algorithm for the generation of Voronoi diagram under the geodesic distance. Besides the geodesic distance metric, we also define a density function of mosaic tiles, which controlsthe distribution of different mosaic tiles. Density function is defined by a distance field, whichrepresents the shortest distance of each pixel to the feature edges.It can be quickly calculated by Euclidean distance transformation. Finally, we combinecentroidalVoronoi tessellation method.The shapes of the Voronoi cells are further optimized by Lloyd’s method towards hexagonal shapes, and the distribution of Voronoi cells are controlled by the density map. Experimental results show thatour algorithm keeps the features of the input image faithfully. The tiles in the generated mosaic image are well shaped and arranged, and vary in size according to the density function. We also show the applications ofthe proposed method in the super-pixel image segmentation and B-spline surface fitting with adaptive node insertion.