Keywords: svg , vectorialization
Biography
Sebastiano Battiato was born in Catania, Italy, in 1972. He received the degree in Computer Science (summa cum laude) in 1995 and his Ph.D in Computer Science and Applied Mathematics in 1999. From 1999 to 2003 he has leaded the ’Imaging’ team c/o STMicroelectronics in Catania. Since 2004 he works as a Researcher at Department of Mathematics and Computer Science of the University of Catania. His research interests include image enhancement and processing, and image coding. He published more than 80 papers in international journals and conference proceedings. He is coinventor of about 15 international patents. He is reviewer for several international journals and has participated in many international and national research projects. He is a Senior Member of the IEEE.
Biography
Salvatore Nicotra was born in Catania, Italy, in 1975. He received the degree in Computer Science (summa cum laude) in 1999 and his Ph.D in Computer Science in 2003. He collaborates with Department of Mathematics and Computer Science of the University of Catania on research projects and teaching activities. Sinces 2005 he works at Neodata Group as Database Administrator. His research interests include scientific visualization, visual data mining and texture analysis.
Biography
Agata Palazzo was born in Milan, Italy, in 1981. She had a degree in Computer Science in 2007. Actually, she's working with catania university to the "città della scienza" (Science Museum) project.
This paper presents a portable compression algorithm applied to raster data images properly triangulated by using DDT (Data Dependent Triangulation). In particular the input source data are encoded to be rendered by standard SVG (Scalable Vector Graphics) engine. The proposed compression strategy works reducing the overall entropy implementing some heuristic strategies to properly re-code the redundancy inside the mesh representation. The compressed data are enclosed into an SVG player able to both decompress and show the original image. Results show the effectiveness of the approach.
1. Introduction
2. Data Dependent Triangulation
3. Triangular Mesh Compression
3.1 Step 1. Mesh Extraction from SVG files
3.2 Step 2: Preprocessing Steps
3.3 Step 3. Mesh Visit
3.4 Step 4 Huffman Compression
4. Decompression Step
4.1 Writing Compressed Elements in SVG
4.2 SVG Scripting Capabilities
4.3 Online Decompression
4.4 Optimized/Dynamic Online Decompression
5. Experimental Results
6. Conclusions and Future Works
Bibliography
The Scalable Vector Graphics (SVG) [SVG04] is an XML language for the description of bidimensional graphical objects. The SVG standard allows representing complex graphical scenes by a collection of graphic vectorial-based primitives, offering several advantages with respect to classical raster images such as: scalability, resolution independence, etc.. SVG format could find useful application in the world of mobile imaging devices, where typical camera capabilities should match with limited color/size resolutions displays. Major details can be found directly at the W3C site [SVG04].
Recently, some advanced approaches have been proposed to vectorize raster images using an SVG engine as final rendering. See ([BBD05][BGM04][BCDN05]) for more specific technical details about each method. A useful comparison is surveyed in [BDG05].
In particular in [BBD05] is presented a technique that approximates local pixel neighbourhood by making use of Data Dependent Triangulation (DDT) [DLR90]. The DDT replaces the input image with a set of triangles according to a specific cost function able to implicitly detect the edge details. The overall perceptual error is then minimized choosing a suitable cost function able to simplify triangulation. On the other hand the DDT is strictly connected to the original pixel positions; therefore the number of actual triangles is larger than the number of pixels. Although the quality achieved in this way is rather good the size of the resulting files may be very large. In [BBD05] the DDT triangulation is furtherly processed by a polygonalization step devoted to minimize the dimensions of the resulting files by merging triangles together, according to specific similarity metrics, by reducing in this way the overall amount of redundancies.
In this paper we propose an alternative approach able to properly capture the redundancy of the mesh representation. The resulting file size of the vectorized images, also using native GZIP compression of SVG (SVGZ) is too big for practical purposes. The aim of this paper is to provide a portable and compressed version of the SVG output coming from DDT. The proposed compression uses both topological and physical redundancy used to represent the mesh. Our work is mainly inspired by [Ros99], [RS99] where several strategies and heuristics are proposed to compress a general triangular mesh. Further advanced approach for mesh optimization and compression can be found in [Ros03] In our case starting from a triangular simplified 2D mesh, without holes, a simple visiting strategy that walks from one triangle onto an adjacent one has been designed. At each step it encodes whether the tip vertex and the left and right neighbours of the current triangle have already been visited. It encodes the complete connectivity of the triangle mesh in a sequence of symbols, by using a variable length encoding. Moreover the compressed information have been embedded into an SVG file that uses Ecmascript [SE99] to decompress and visualize the original data during execution, by using dynamic capabilities of the language. The final result is a lossless compressed file, able to be decoded by any SVG rendering engine, that dynamically generates the corresponding vectorial images. Without any loss in terms of image quality the proposed technique reaches satisfactory results with respect to the final compression ratio; the overall bit-size is fully comparable with the original uncompressed raster image.
The paper is structured as follows: Chapter 2 briefly reviews the main details of DDT triangulation, while in Chapter 3 the overall mesh compression engine is described. Chapter 4 is devoted to the run-time decomposition step. Chapter 5 reports some experimental results. Finally Chapter 6 closes the paper addressing direction for future works.
A triangulation is a partition of a two-dimensional plane into a triangles set. The triangulation techniques, named Data Dependent Triangulation (DDT), try to optimize the approximation of a particular function, taking also advantage from the information obtained from the co-domain. The optimum triangulation research, by considering a fixed criterion, is a not well posed problem; however good results are obtained by considering locally optimal criterions. A triangulation is called “Optimal” if it is impossible to obtain a further improvement by swapping any edges.
The algorithm introduced by Lawson [Law77] is an iterative technique able to find a locally optimal triangulation. This approach inspects all the inner edges and exchanges those that reduce the total cost of the triangulation; the algorithm iterates the process until the total cost is still unchanged.
Another approach, based on Lawson’s method and developed by Yu et alii [YMS01], has been used as starting point to develop the proposed approach:
To estimate the triangulation, the optimality criterion is fixed using the following cost function:
Cost(E)=|∇P_{1}|• |∇P_{2}| - ∇P_{1} • ∇ P_{2} (1)
where E is a common edge of two triangles and ∇P_{i}=(a_{i},b_{i}) are the gradient of the planes P_{i}, that are the interpolating linear functions of the triangles. A few iterations are needed to guarantee an effective coupling between original edges distribution and related triangle vertexes map. In our case, to further speed-up the overall process we used the following approximation:
cost(e)=(|a_{1}|+|b_{1}|) • (|a_{2}|+|b_{2}|) - (a_{1} • a_{2} + b_{1} • b_{2}) (2)
that is cost effective. Such cost function is similar to the simplified cost function used in [DLR90] to describe the roughness of triangulated terrain (Sobolev seminorm).
Therefore the global triangulation cost is summarized in:
cost(T)=∑_{∀t1,t2 contiguous in T}[|a_{1}|+|b_{1}|) • (|a_{2}|+|b_{2}|) - (a_{1} • a_{2} + b_{1} • b_{2}] (3)
The DDT approach aims to minimize the global triangulation cost. Three/Four iterations are usually needed to minimize the triangulation cost. Actually, after the fourth iteration the triangulation cost changes slightly introducing less improvement.
This section describes a generic compression scheme for digital images described by regular triangular mesh. Such technique will be applied to data coming from vectorization of raster images making use of DDT triangulation [BBD05].
The main idea of the proposed approach is to compress data using the redundancy coming from the spatial information (triangles are connected), from semantic (objects are triangles with given features) and from storage describing object’s syntax.
The spatial compression is achieved representing the triangles in a tree structure where nodes are the triangles while edges represent the connections. The mesh is connected, so it’s possible to build a tree that cover the whole mesh. Moreover in a triangle each node is adjacent to its parent, that is they have two common vertices p, q, so it’s convenient to store only the remaining vertex plus its orientation with respect to the father. Instead of storing absolutes coordinates of the point, we take into account the horizontal and vertical distance of the previous point in the triangle. Such representation allows saving space when triangulation is very fine, as in the case of images vectorized by DDT, where each original pixel belongs to 2 different triangles. Finally the tree representation is easily compressed by using an entropy encoder such as Huffman compression.
The input data is directly derived from a vectorial representation of a digital picture in an SVG format, obtained applying the DDT triangulation using the technique described in ([BBD05],[BGM04]) without considering the polygonalization step. Triangular mesh are easily represented using the PATH SVG primitive; the input of the algorithm is defined by a set of lines, each of ones describe a triangle. For example the SVG primitive:
describes the triangle of vertexes (110,90 – 140,110 – 120,110) with red background color. The complete syntax of the PATH primitive is given into Table 1.
Command | Name | Arguments | Description |
---|---|---|---|
M, m | moveto | x y | Starts a new sub plot. M (uppercase) indicates that absolute coordinates will follow; m (lowercase) indicates that relative coordinates will follow |
L, l | lineto | x y | Draws a line from actual point to (x,y). L (uppercase) indicates that absolute coordinates will follow; l (lowercase) indicates that relative coordinates will follow |
H, h | Horizontal lineto | p | Draws an horizontal line from actual point (x,y) to point (x+p,y). H (uppercase) indicates that absolute coordinates will follow; h (lowercase) indicates that relative coordinates will follow. |
V, v | Vertical lineto | p | Draws a vertical line from actual point (x,y) to point (x,y+p) V (uppercase) indicates that absolute coordinates will follow; v (lowercase) indicates that relative coordinates will follow. |
Z, z | Closepath | (none) | Close the current subpath by drawing a straight line from the current point to current subpath's initial point. |
Table 1
A triangular mesh is a geometrical structure composed by connected triangles having the following features:
An example of triangular mesh is given in Figure 2
The overall process of the compression algorithm is composed by the following steps:
Each triangle of the mesh is stored in a structure containing:
First image size is obtained from attributes width and height from the svg tag. For each PATH primitive, the d attribute is parsed obtaining the vertices coordinates.
Both absolute and relative movements into the canvas are taken into account checking if the object is a triangle and verifying also the triangular mesh constraints. The background-color is picked-up from the fill attribute. For example the triangle defined in Example 1, showed by using label 0 in Figure 2, is described as:
x1 | Y1 | x2 | y2 | x3 | y3 | R | G | B |
---|---|---|---|---|---|---|---|---|
110 | 90 | 140 | 110 | 120 | 110 | 255 | 0 | 0 |
At each step of the compression process, a triangle is extracted from the set. As already mentioned, it’s important to know the orientation of the triangle with respect to the plane. So the description of the triangles is rearranged to contain the coordinates of the basis, the right side and the left side respectively. The triangle 0 becomes:
x1 | Y1 | x2 | y2 | x3 | y3 | R | G | B |
---|---|---|---|---|---|---|---|---|
140 | 110 | 110 | 90 | 120 | 110 | 255 | 0 | 0 |
In the meanwhile, the record that describes the triangle is updated adding pointers to its neighbours as showed below:
… | T1 | T2 | T3 |
---|---|---|---|
… | Triangle 9 | Triangle 3 | Empty |
The role of the visit consists in the creation of the following elements:
A triangle during the visit can be classified (see Figure 3 for a visual explanation) as follows:
The pseudo code of the tree building is the following:
Procedure Visit_Mesh() Let T the first triangle having at most two adjacents. Let P a stack; BASE_VERTEX := Base(T); Node := T For i := 1 to #Triangles - 1; VERTEX += opposite_to_gate_edge(Node); Classification := Classify(Node); UPDATE_NEIGHBOURS(Node); CLASSIFY += Classification; R += RED(Node); G += GREEN(Node); B += Blue(Node); Switch Class Case “C”: Next := Right(T); Case “R”: Next := Left(T); Case “L”: Next := Right(T); Case “S”: Push(T,P); Next := Right(T) Case “E”: Next := Left(Pop(T,P)); End |
Example 2: Pseudo code of procedure visit mesh
The UPDATE_NEIGHBOURS procedure removes from neighbours records, the pointers to the selected Node, while opposite_to_gate_edge(Node) function returns the coordinate of the point opposite to the edge adjacent to Node.
For example the compressed elements of the mesh in Figure 2 are:
BASE_VERTEX = "140 110 30 20 20 0 255 0 0 C"
VERTEX = " 20 0 | 0 10 | 10 -10 | 10 0 | -10 -10 | -10 -20 | 30 10 | 10 10 | 10 10 | 20 0 | 10 -10 | 10 0 | 0 -10 | -20 0 | 0 -10 | -30 -10 | -10 10 | -20 0 | -20 -10 | 0 20 | -20 -10 | -10 -10 | 0 -10 | -10 0 | -10 0 | 20 10 | 0 10 10 0 | 0 -10 | -20 -10 |"
CLASSIFY = "S | E | C | R | C | S | C | C | R | R | C | R | R | S | R | E | E | C | R | S | L | S | E | L | E | C | R | R | R | E"
RED = "255 | 1 | 1 | 0 | 0 | 14 | 0 | 71 | 0 | 0 | 171 | 0 | 0 | 0 | 0 | 14 | 84 | 241 | 0 | 1 | 85 | 255 | 172 | 0 | 0 | 255 | 1 | 0 | 255 | 1"
(the GREEN and BLUE elements are similar)
The algorithm chooses the triangle #0 as starting point (it has two adjacents), such triangle is complete (C), since is it possible to return choosing the right triangle (i.e, #3,#7,#8,#9). So the BASE_VERTEX contains the coordinates: (140,110) that is the base point p; (30,20) the q distance from p; (20,0) the l distance from p. The other collected information are the RGB background color of the triangle and its classification.
The second triangle is #3, because it is Right with respect to the triangle #0. Such triangle is a Split triangle (S): it is not complete and has both left and right adjacents.
The node is pushed into the stack and the visit continues with triangle #10, that is clearly an Empty triangle (E). A pop from the stack returns the triangle #3 and the visit continues with Left with respect to #3 (i.e. triangle #7). Such triangle is Complete, while its right (triangle #11) is a Right triangle since it has only a left adjacent. The complete sequence of visited triangles is:
| 0 | 3 | 10 | 7 | 11 | 12 | 14 | 15 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 16 | 30 | 4 | 5 | 13 | 17 | 26 | 27 | 28 | 29 | 2 | 9 | 8 | 1 | 6 |
The overall data collected in the previous steps, have sensibly reduced the redundancy of the mesh representation coding a topological compression of the triangulation. In order to achieve better results each element is compressed separately using classical Huffman algorithm. The splitting does not give problems and it is based on a few simple considerations:
Such data together with the dictionaries to be used in the decoding phase, are the compressed information of the original image.
The aim of the decompression step is to reconstruct the original mesh using an SVG representation starting from the compressed information.
In this paper, we present two schemes of decompression: the first approach follows back the steps described in the previous section: Huffman decompression of the elements, mesh visit of the tree starting from the root obtaining the full set of triangles, writing of triangles using SVG PATH primitive. This method has been named offline decompression and requires an external decoder that after having properly read the data performs all the steps before getting the final result.
The second and more innovative method is a general approach to store and process compressed elements within an SVG file.
All array elements contain description of a single triangle and in order to reconstruct the overall set of triangles only the coordinates of the adjacent sides are required. So, starting from the mesh root, described by the BASE_VERTEX element, is it possible to:
The underlying idea of the method is the storing of the compressed elements into an SVG file, implementing an auto-extracting system that while reads information, prints out the triangles in the SVG canvas. Then the decompression occurs without any external software to decode the compressed information and each triangle is visualized independently during the tree visit; for this reason the method has been defined as online decompression. In the following some details about the implementation are reported.
SVG is an XML language, so SVG instructions are XML elements having attributes and content. Each compressed element can be inserted into the SVG file defining a new XML element having CDATA (Character data) content. In our application, the content of the element is the ISO 8859-1 (Latin-1) representation of the Huffman binary coding, while the attribute id describes the name of the vector. For example the array element VERTEX is defined as:
<my_data id="vertex"><![CDATA[>_;]¿ UFv³X}1á?ßp²Öp>!]]> </my_data> |
Example 3: XML representation of compressed data
The SVG language uses ECMAScript as client scripting language [SE99]. ECMAScript is an object-oriented programming language for performing computations and manipulating computational objects within a host environment. An important feature of ECMAScript is that is possible to read and write SVG elements trough the Document Object Model (DOM). The functions to read XML elements and put into a variable and to create a new triangles are:
function read_Node(id){ node=svgDocument.getElementById(id); node_content=node.getFirstChild(); node_content_data= node_content.data; return node_content; } function build_mesh(x1,y1,x2,y2,x3,y3,r,g,b) { var d ="M"+x1+","+y1+" "+x2+","+y2+" "+x3+","+y3+" Z"; var shape= svgDocument.createElementNS(svgns, "path"); var color="rgb("+r+","+g+","+b+")"; shape.setAttributeNS(null, "d", d); shape.setAttributeNS(null, "fill",color); shape.setAttributeNS(null, "stroke",color); svgDocument.documentElement.appendChild(shape);} |
Example 4: ECMAscript functions
Let c_triangle(x1,y1,x2,y2,x3,y3,r,g,b,type)
the array containing the information to build the current triangle.
The array c_triangle is initialized directly from the BASE_VERTEX array. To reconstruct the others N-1 triangles (where N is the number of triangles) the following procedure is used:
Function get_triangle(i) (x,y) = get_coordinates(VERTEX) k = get_classification(CLASSIFY) (r,g,b)=get_colors(R,G,B) switch (c_triangle[9]) case “C” or “L”://Right of preceding c_triangle[0]=c_triangle[4]; c_triangle[1]=c_triangle[5]; c_triangle[4]=c_triangle[4]-x; c_triangle[5]=c_triangle[5]-y c_triangle[6]=r:c_triangle[7]=g; c_triangle[8]=b; c_triangle[9]=k; case “R”: // Left of the preceding c_triangle[2]=c_triangle[4]; c_triangle[3]=c_triangle[5]; c_triangle[4]=c_triangle[0]-x; c_triangle[5]=c_triangle[1]-y; c_triangle[6]=r:c_triangle[7]=g; c_triangle[8]=b; c_triangle[9]=k; case “S”: // Derives from a split push(triangle_c); //save into a stack c_triangle[0]=c_triangle[4]; c_triangle[1]=c_triangle[5]; c_triangle[4]=c_triangle[4]-x; c_triangle[5]=c_triangle[5]-y; c_triangle[6]=r:c_triangle[7]=g; c_triangle[8]=b; c_triangle[9]=k; case “E” // After an empty. c_triangle=pop; // get from the stack c_triangle[4]= c_triangle[0]-x; c_triangle[5]= c_triangle[1]-y; c_triangle[6]= r; c_triangle[7]=g; c_triangle[8]=b; c_triangle[9]=k; } build_mesh(c_triangle); |
Example 5: Code of get_triangle function
In the pseudo code, the get_ functions are designed to get information about the next triangle to elaborate. The input parameter is a set of array element. For example get_classification(CLASSIFY) returns the type of the next triangle to be processed. Circular buffers are used to optimize memory space.
At first we used array to store the Huffman dictionary of the compressed arrays, in order to speed-up the search, hash tables have been introducted (optimized version).
Moreover a GUI has been introduced to show informations about the image and interactivetly users can choose "dynamic" rendering, i.e. the canvas is refreshed during the decompression step. See Figure 4
The proposed method of coding triangular mesh through SVG primitives has been implemented and tested over a demonstrative set of digital images. All images have been vectorized by DDT triangulation, without using merging, obtaining the corresponding SVG version. Afterwards the overall set has been compressed using the technique described in Section 3. Table 2 summarizes the overall results, showing also the thumbnails of the compressed images. For the offline decompression scheme, five different files, containing the compressed elements are properly generated. The computed overall bit-size of the compression is obtained by summing each file size, while the final bit-sizes of the online compression methods are the bit-size of the auto-extracting SVG(z) file.
Filename | Thumbnail | Resolution | PPM RAW | PNG | DDT SVG | DDT SVGZ | OFFLINE | ONLINE | ONLINE SVGZ | ONLINE SVGZ OPTIMIZED/DYNAMIC | Rendering Time DDT SVG | Rendering Time ONLINE SVG | Rendering Time ONLINE SVG OPTIMIZED | Rendering Time ONLINE SVG DYNAMIC | Link |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Kodim 15 | 400x266 | 319238 | 166254 | 3929061 | 557490 | 118895 | 148451 | 117110 | 119526 | 31 | 117140 | 72094 | 92391 | kodim15_play.svgz | |
Lena | 400x400 | 480038 | 301316 | 5790565 | 970851 | 203282 | 250424 | 204284 | 206643 | 16 | 219781 | 122156 | 144281 | lena_play.svgz | |
Peppers | 400x400 | 480038 | 269451 | 5790562 | 954099 | 186464 | 229911 | 187893 | 190275 | 31 | 182500 | 114875 | 145781 | peppers_play.svgz | |
kodim 23 | 400x266 | 319238 | 157694 | 3829077 | 605742 | 121774 | 151860 | 121285 | 123635 | 31 | 116563 | 73547 | 93391 | kodim23_play.svgz | |
flowers | 400x300 | 360038 | 228072 | 4326777 | 748225 | 159256 | 198644 | 162801 | 165180 | 32 | 156922 | 94781 | 115079 | flowers_play.svgz |
Table 2
In Figure 5(a) a graphical comparison of the compression ratio between the SVG file produced by DDT transformation with respect to the simple gzipped version (SVGZ), the offline method, the online compression and its gzipped version is shown. The proposed method produces encouraging results clearly outperforming the widely used GZIP compression because it is able to capture the remaining redundancy of the mesh representation. It’s important to notice how the auto-extracting script in the online compressed SVG produces a small size overhead that is almost null when a further GZIP compression is applied, also the GUI introduced int Figure 5(b) compares graphically the bit per pixels (bpp) of the coded file proving how the SVG compressed DDT transformation produces files whose size are comparable with standard raster image format both compressed and not. Figure 5(c) shows the rendering time: the only drawback of the on-line method is the overall running time because its performances are mainly related with the rendering engine implementation. On the contrary the off-line counterpart that we have implemented in ANSI C-language run in almost a few seconds.
a) Comparisons of compression ratio with respect to the file size obtained by DDT Triangulation
b) Final bit-size comparison in terms of bit per pixel.
c) Comparisons of rendering time
Figure 5: Experimental results
In this paper a lossless compression method able to reduce the entropy of a regular SVG mesh of data is presented. In particular the proposed technique has been applied to vectorial images obtained by using DDT triangulation as described in ([BGM04], [BCDN05]).
The decompression scheme has been implemented by using the dynamic characteristics of the SVG standard making use of EcmaScript capabilities. For each compressed image an auto-extracting .svgz file able to reconstruct the original data is built. Experimental results confirm the effectiveness of the proposed method.
XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.