Fourier transform in SVG graphics


Table of Contents

Vectorization
Hi- gradient matrix
Low- gradient matrix
Where to place vertices and what values to assign them
Comparison with meshes- methods of gradient fills.
How to implement such vectors into SVG
Conclusion
References

Let's go through the process of a raster to vector conversion. We'll speak for simplicity about grayscale images. This process consists of some 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 a predefined threshold, this complex gradient has to be transferred to the corresponding point of the second matrix (and zero gradient has to be placed onto the first matrix instead). After this operation, the first matrix contains only gradients below above the named threshold, therefore corresponding colour distribution will be smooth. The second matrix will contain hi-level gradients, and these gradients will be distributed along edges, what are really present in the source raster. No additional contours at all. Corresponding colour distribution can be obtained as a convolution with the fundamental solution of a Poisson's equation - Kauchy's kernel. This convolution can be efficiently performed with the aid of FT. At this stage there is still no progress- two complex matrices instead of a real one. But, due to the nature of a common photorealistic raster both of these matrices can be efficiently converted to compact vector objects, using methods, specific for each of these matrices.

Colour distribution, corresponding to this matrix, can be obtained as a convolution with the fundamental solution of a Poisson's equation - Kauchy's kernel. This colour distribution will be similar to a set of slits, made by a scissors: one side of such a slit is lighter, the opposite one is darker. Similar method is described at (1). The difference between author's approach and used in (1) is that author does not fix colours of both sides of contours - only their difference instead. Using FT makes my approach much faster, than used in (1) and eliminates need in powerful video accelerators like Nvidia GeForce 8800. 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 Bezier polyline. Let's assign to a link number N a real parameter s, that changes from N-1 to N inside this link. Then the gradient, distributed along a curve, can be converted to a spline, depending on parameter s. Because direction of this gradient is orthogonal to contour's direction, there is no need to record complex value. Contours of a common photorealistic image usually cover only small part of the whole image's canvas. Sample of this situation is shown at Fig.1.


Let's go on with the low-gradient matrix- gradients everywhere are small, but are not equal to zero at nearly for all points of this matrix. There are not selected directions, and corresponding colour distribution is smooth. Let's obtain the corresponding colour distribution as a convolution of gradient matrix with Kauchy's kernel. After this operation we can forget about complex numbers- result is real (and smoothly coloured). Question is, how such object can be efficiently converted to a vector object. One possible way is to use FT again, to get rid of hi-frequency components because they are small and therefore non-significant and to preserve small number of low-frequency harmonics. This method is efficient for compression, but useless for manual editing of such image. Here is the situation, where some analogies with theory of elasticity are very useful. If you put a thin flexible but resilient steel plate into a press and a ram is going down until the full contact with underlying bed, this plate will be deformed and its shape will became the same as this bed. There is analogy between the distorted plate and brightness of a grayscale image: height of each point of the distorted plate is equivalent of a brightness of a corresponding point of the grayscale raster. But what will happen, if some gap between the ram and the bed still remains? Shape of the distorted steel plate will not replicate precisely the underlying bed. Maximal distance between the bed and the plate will be equal to half of the gap between the ram and the bed. On the other hand, energy of deformation of this resilient plate will be as low as it is possible under these circumstances. Also, there will be some points, where this plate contacts with overlying ram and another set of points where it contacts with underlying bed. And now we can forget about press too. If contact with another object takes place at some point, it means in fact that a point force is acting upon this point. Therefore all we need is to solve biharmonic equation, where the right side of it is equal to zero except some discrete points. Trick is to find, where these points are to be placed and what values to be assigned to them. The problem is to reproduce original colour distribution with predefined accuracy, using as few control points (vertices) as possible.

What happens, when an image has been smoothed? Somewhere it is getting lighter, somewhere darker. It looks like the image was splitted to a set of pieces; each of them with only positive or only negative difference from the original. On edges of these pieces, the difference is equal to zero, of course, and reaches maximum values somewhere near the centre. Point of the maximum difference is the best candidate to place a vertex. Number of such pieces (and vertices therefore) depends on how strong the image has been smoothed. This fact can be used, when one wants to change a number of vertices. To smooth a function U(x,y) means to find another function V(x,y), which minimizes functional J, defined as

Here P is a parameter, used for smoothing: low value of P means that U(x,y) will be only slightly smoothed and vise versa. PDE, corresponding to equation (1) is:

This equation shows us, that result of smoothing can be treated as shape of a plate, distorted under vertical forces, proportional to U-V and continuously distributed on the whole surface of this plate. Problem is, therefore, to replace these distributed forces by a set of point forces. This set must be as compact as possible, and on the other hand, the shape of the plate must not be changed considerably after this replacement. Fortunately, this operation can be performed independently for each piece of the source image where the sign of U-V remains constant. If we treat U-V as a force, distributed on the surface of such a piece, this force can be characterized by set of moments, given by

where

Replacement must preserve all these moments for each piece. In that case, at least low harmonics of V will remain intact, when continuous forces have been replaced by the set of point forces. The next problem is to assign colour to each vertex. The simplest way is to use original colour of corresponding points of the source raster. At the last stage, one needs to solve biharmonic equation. It is not such a simple task. If number of vertices is not very large (several hundreds), it is possible to construct solution as a sum of fundamental solutions of the biharmonic equation, multiplied by some unknown coefficient plus a linear function. To get these coefficients, one needs to solve a linear system of equations. Dimension of this system equals to a number of vertices plus three. When these coefficients are found, resulting solution can be obtained with the aid of FT. But, this method becomes inefficient, when number of vertices is comparatively large. Alternative methods, based on direct solution of a biharmonic equation (sparse matrix and so on), can be used here. This process is shown at Fig 2-3.



These images demonstrate, that more or less satisfactory result can be obtained with relatively small number of vertices. Large number of vertices produces image, very similar to its raster prototype, but such vectors will hardly have any practical use.

The first question is, of course, if one can realize gradient fills without meshes, why to use them at all? Meshes make computation of gradient fills simpler, but simultaneously produces lots of problems. Their only advantage is localization - if one change colour at crossing column number j and row number i, colour will be changed only within four cells. Sometime it could be useful. On the other hand, and this is the most unpleasant property of meshes, if one needs to add only one control point, the mesh forces him to add the whole row and column, too. Even if the mesh is created automatically, its rebuilding is not a very simple operation. Vertices- based gradient fills is much more flexible. One may add as many vertices as he needs, delete existing ones or move them to another positions. All these operations can be performed by a single movement of a mouse, what makes such gradient fills much more convenient for manual editing.

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>
    <slit>
      <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"/>
    </slit>
  </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 colour between the left and the right sides of a contour line. Currently author does not know, how to modify this record for true colour 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 hardly be 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