In this paper author proposes one efficient method of raster to vector conversion, based on the Fast Fourier Transform (FFT). Let’s consider a problem of conversion of photorealistic raster images to vectors and back transform- rasterization of vectors. A raster image to be converted to vector file can be represented as a combination of three components: (sharp) contours, which separate more or less smoothly colored regions with low color gradients, and hi-frequency noise or texture. This paper focuses on highly efficient method of raster-to-vector conversion of contours and gradient fills. Hi-frequency noise or texture probably should be converted to vector objects with the aid of fractals. On the one hand, the goal is to create a vector file looking similar to its raster prototype, and on the other, this file must be as small and compact as possible. Let’s speak for simplicity about grayscale images. The first step is to replace the original raster with the matrix of the same size, containing color gradients. For the grayscale image, this gradient is a vector, one component of which is a derivative of brightness along X-axis, and the other is a derivative of a brightness along Y-axis. This matrix can be converted to raster image by convolution with Cauchy kernel. The best way to perform this operation is by using FFT. The essence is that this matrix of gradients can be efficiently compressed with only minor losses. Such a matrix, obtained from a general raster, will be filled mostly with low gradients, and only small part of it would contain high gradients, corresponding to contours of the source raster image. These high gradients will be located along narrow lines, like fences between plots of land. Therefore, they can be converted into well-known Bezier curves that have one additional feature. This feature is a non-constant parameter distributed along each curve that designates the color discontinuity across this curve. Corresponding type of record in SVG is well-known. The residual matrix contains low gradients; corresponding distribution of colors is smooth. Thus, this object can be converted to a small vector file. Common methods for this operation are based on meshes: triangular, rectangular or distorted rectangular ones. However, there is no need to use them because interpolation from a set of vertices is able to perform this op much better. There are two problems: where to place these vertices and how to interpolate these colors to the whole image. FFT can be used here as well. Let’s smooth a grayscale image a little and compare the source and smoothed output. The source matrix is somewhere brighter, somewhere darker then the smoothed one. It means, that the difference between these two matrices looks like a mosaic: it contents regions with negative difference and regions with positive one. One needs to put a vertex at the center of each of such regions and to assign a color value to it. Interpolation from the set of vertices to the whole image is based on a biharmonic equation. Solution of this equation is a sum of fundamental solutions of the biharmonic equation, multiplied by some coefficients. To obtain these coefficients, one needs to solve a system of linear equations. If number of vertices is not very large (up to 500, approximately), this method is rather efficient. After these coefficients are obtained, result of interpolation is in fact convolution too. Therefore, FFT can be used here as well. Otherwise (if number of vertices is too large) some methods, based on sparse matrices can be used. To convert such a vector image to raster, some operations are to be performed. Two matrices with the size of output image are to be created: the first one is a gradient matrix, the second matrix is a color matrix. Both of them are initially filled with zeros. Color gradient from the set of curves is to be placed onto the first matrix. Then direct FFT is to be performed. Result is to be multiplied by Cauchy kernel and transformed back. Then vertices are to be placed onto the second matrix. Colors are to be interpolated from the set of vertices to the whole matrix and both matrices are to be superimposed. Using FFT is really fast, may be fast enough to perform a real-time video (25 frames per second). This method being incorporated into SVG offers a possibility to obtain small vector files with almost photographic quality.
Let’s look at the process of conversion. The first image- http://www.smartfills.com/Html/Images/contour.png represents set of contours, obtained from the source raster. The second image- http://www.smartfills.com/Html/Images/harm.jpg
is the result of convolution of density, distributed along these contours, with Cauchy kernel. The rest is suppressed. The third image- http://www.smartfills.com/Html/Images/harm_plus_biharm.jpg
is the second one plus a smooth color distribution (low gradients), based on set of vertices, placed onto image’s canvas. Of course, each intermediate variant is possible too- when one decreases number of vertices, the third image is getting more and more like image two.
