One highly efficient method is described in (1). This method is named Diffusion Curves. This method does not need all contours to be enclosed lines; in fact contours can have any shape. Each contour is a double-sided line. Color of the left side of the contour differs from color of the right one. Interpolation to the whole image to be painted is based on Laplace equation (authors of (1) claim that they solve Poisson equation, but it is obviously a mistake). This is an efficient method, producing nice-looking vector images. Author, wanting to create contour based gradient fills, uses similar approach- the same equation, but another partial solution. Programs, intended to demonstrate this method (PaintingPen, PaintingPenDemo) are available for download at (2). However, the Diffusion Curves method has some disadvantages, too. Let's try to convert a raster to vector, using such approach. At the first stage one needs to convert a source raster image to a contour image. Later these contours will be used as a base to paint the whole image. But, it is quite clear, that it is hardly possible to keep color of a big region under control, using only information, distributed along its border. Thus, some additional invisible contours are necessary (any contour can be done invisible by applying an unsharp mask- it is obviously not the best method, if all what one needs is to place some vertices onto this region). This is why author believes, that the most efficient way to convert a raster to vector is the combination of both above described methods.

Let's run through process of a raster to vector conversion. We will speak for simplicity about grayscale images. This process consists of four stages. Two complex matrices with the same size as the source raster are to be created. The first matrix is filled with gradients of the source raster: real component with a gradient along x-axis, imaginary component with a gradient along y-axis. The second matrix is initially filled with zeros. If a module of the gradient at some point of the first matrix is above some predefined threshold, this complex gradient is exchanged with the gradient of the same point of the second matrix (gradient is moved to the second matrix, zero to the first one). After this operation, the first matrix contains only gradients below the threshold noticed above, therefore corresponding color distribution will be smooth. This color distribution can be restored, using relatively small number of vertices. The second matrix contains gradients above the predefined threshold and these gradients are distributed along edges, what really are present in a source raster. No additional contours are required at all. Corresponding color distribution can be obtained as a convolution with the derivation of the fundamental solution of the Poisson equation- K(z)=1/z. This color distribution is similar to a set of slices, made by scissors: one side of such a slice is lighter, the opposite darker. The difference between author's approach and the one used in (1) is that author does not fix color of both sides of contours but only their difference. This is why the proposed method is much faster and has no need in powerful video accelerators like Nvidia GeForce 8800. Convolution can be performed, using FFT. Due to the nature of hi-gradient matrix, the way to convert it to a vector object is obvious. This matrix is filled with zeros, except some contours. It looks like a set of walls with variable height. The set of these contours can be converted to the set of vector objects, using traditional technology. Each contour can be converted to the Bezier polyline. Let's assign to a link number N a real parameter s, what changes from N-1 to N inside this link. Then the gradient, distributed along a curve, may be converted to a spline, depending on that parameter. The first (low-gradient) matrix should be converted to a vector object, using vertices-based method. Color distribution, corresponding to the first matrix, can be obtained in the same way as a convolution with the same kernel. This color distribution must be reproduced with the predefined accuracy with the aid of interpolation from a set of vertices, placed onto the first (low-gradient) matrix. There are in fact two problems: where (and how many) vertices have to be placed and what colors have to be assigned to them. The first problem is non-linear, but some practical approaches are possible here. This process is shown on Fig. 1- Fig. 2.

There are some additional kinds of records to be included into SVG specification to make it able to support advanced gradient fills. They could be something like this:

<fills> <path d="M147 4 C151 1 152 2 154 4 C157 6 166 9 169 11 C171 13 174 15 177 16 C186 21 199 28 203 30 C205 32 208 33 147 4"/> <vertex> "V26 10 #484d4e V42 16 #44464f V6 16 #363b36 V34 14 #313a35 "</vertex> <slice> <path d="M145.3 329.8 C149.5 326.2 151.3 334.0 154.9 328.0 C156.7 325.0 156.7 316.6 160.9 320.8 "/> <sf:parameter d="s0.0 p18.1 s0.3 p12.7 s0.9 p-7.7 s1.7 p-8.9 s2.0 p-13.0"/> </slice> </fills>

The second tag (path) describes a path, bounding region to be painted. If it is not exist, the whole image has to be painted. The third tag (vertex) describes the set of vertices. They consist from coordinates and RGB triplets. The fourth tag (slice) describes a contour line namely its shape and a parameter, distributed along this line. This parameter is the difference in color between the left and the right sides of a contour line. Currently author does not know, how to modify this record for true color images. Of course, instead of one scalar parameter there should be RGB triplets. Problem is that original RGB triplet consists of three positive values. But their difference may adopt negative values as well.

Author believes, that advanced gradient fills, described here, will allow this format to produce such vectors images, which could be hardly obtained by any other vector format. It is quite clear, that the current state of vector graphic is not an ultimate achievement of humankind. There is no great problem to incorporate such functionality into SVG format. More difficult task is to include support of above described gradients into some of common programs (browsers, editors, raster to vector converters etc). But it is a worthwhile thing due to the fact, that advanced gradients have the whole list of advantages. Smaller size and better quality of vectors, produced by above described technology, compared with vectors, produced by another converters (Rave Grid, Vector Eye, Live Trace and so on) is crucial, when one wants to edit such vectors manually. Intel will be happy, because rasterisation of such vectors requires lots of computations.

1. Alexandrina Orzan, Adrien Bousseau, Holger Winnemцller, Pascal Barla, Joлlle Thollot, David Salesin. Diffusion Curves: A Vector Representation for Smooth-Shaded Images. diffusion_curves.pdf[12.8Mo]

2. Andrey Matseevskiy. Advanced gradient fills in vector graphic. Soft, based on above described technology, is available here