Abstract: Mosaic is a non-photorealistic rendering method, which synthesizes a large image by packing a collection of small colored tiles.This paper 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.The feature edges are first extracted from the input image automatically.Then a metric matrix is defined such that the edges of the Voronoi diagram under the new metric align with the feature edges.The sizes of the Voronoi cells are controlled by a density function derived from a distance transformation.Finally, the shapes of the Voronoi cells are further optimized by Lloyd's method.Experimental results show that, our 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.