Recently some approaches have been proposed to vectorize raster images using a Scalable Vector Graphic file as final rendering (See [BDG05]).
This paper presents a portable compression algorithm applied to raster data images properly triangulated by using the techinique described in [BBD05] that approximates local pixel neighbourhood by making use of Data Dependent Triangulation (DDT).
A triangulation is a partition of a two-dimensional plane into a triangles set. The triangulation techniques, named DDT, try to optimize the approximation of a particular function, taking also advantage from the information obtained from the co-domain.
The result of this techique is a vector representation of the input raster images that has been defined by an SVG file composed by the triangles obtained.
Although the quality achieved in this way is rather good the size of the resulting SVG files may be very large.
We propose an approach able to properly capture the redundancy of the mesh representation providing a portable and compressed version of the SVG output coming from DDT.
The main idea 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.
Our work is mainly inspired by [Ros99] where several strategies and heuristics are proposed to compress a general triangular mesh.
The spatial compression is achieved representing the triangles in a tree structure where nodes are the triangles while edges represent the connections. Since the mesh is connected, 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.
Finally the tree representation is compressed by using an entropy encoder such as Huffman compression.
The underlying idea of the method is the storing of the compressed elements into an SVG file,using CDATA (Character data) section and the implemention an auto-extracting system in ECMAScript that while reads information, prints out the triangles in the SVG adding new triangles to the canvas trough the Document Object Model (DOM).
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.
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.
Bibliography