An example of different kind of pixels: internal (blue), close (red) and open (green).
Figure 1: Different Kind of Pixels
Keywords: SVG , Rendering Order , Raster to Vector
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 co-inventor 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
Giovanni Puglisi was born in Acireale, Italy, in 1980. He received his degree in Computer Science Engineering (summa cum laude) from Catania University, Italy, in 2005. He is currently Ph.D. student in the Department of Mathematics and Computer Science. His research interests include video stabilization and raster-to-vector conversion techniques.
Vector representation of digital images offers a number of advantages over the more common raster representation, such as scalability and resolution independence. Many efforts have been made to deploy scalable raster standards for photographic imagery addressed to portable applications. However, they lack the flessibility and simplicity of vector representation. Vector graphics is a new and little explored alternative to the more common representation. In this paper we present our raster to vector technique, called SVGStat, improved with a new boundaries simplification algorithm.
1. Introduction
2. SVGStat
3. SVG Generation Code
4. Boundaries Simplification
5. Experimental Results
Bibliography
Vector representation of digital images offers a number of advantages over the more common raster representation, such as scalability and resolution independence. These features make it amenable for portable applications since it can accomodate for a wide range different displaying conditions, varying in resolution, quality, and level of detail.
Many efforts have been made to deploy scalable raster standards for photographic imagery addressed to portable applications, such as JPEG2K [JPE]. Anyway, since they have been focused on raster images, they lack the flessibility and simplicity of vector representation. On the other hand, while many applications exist to enable artists to build vector images from scratch, converting photographic imagery from raster to vector formats is a relatively new topic.
Recently, SVG (Scalable Vector Graphics), a new vector format for web deployment, has been released ([DHH02], [Qui03]). A number of applications have appeared to convert raster images to vector graphics in the SVG format (Vector Eye [VLDP03], Autotrace [Web02], Kvec [Kuh03], VISTA [PS05]). Anyway, most of these methods are devoted to synthetic images with a small colour palette and strong neat borders between image regions. They often fail to vectorialize photographic images, because they have blurred and fuzzy edges and huge colour palettes. As we already shown in ([BFP06b], [BFP06a]), our technique SVGStat, outperforms other methods both in terms of rendering quality and overall compression rate. Moreover it is based on a single input parameter that makes easy to find the correct trade-off between final perceived quality, scalability and corresponding file size. In this paper we have introduced a boundaries simplification step in the algorithm that permits us to obtain smaller file size without losing in perceived and measured quality.
The rest of the paper is organized as follows. In section 2 we briefly review the main details of SVGStat. The successive section describes the new boundary simplification step whereas section 4 reports some experimental results devoted to compare the performances of the proposed approach with respect to previous version of SVGStat. A final section closes the paper tracking also direction for future works.
SVGStat is a raster to vector technique that consists of three main steps:
Segmentation is the process of partitioning an image into disjoint and homogeneous regions. Recently, thanks to the increasing speed and decreasing cost of computation, many techniques have been developed for segmentation of colour images. In particular we used the Statistical Region Merging ([NN04]) algorithm, a region growing techniques with statistical test for region fusion. This algorithm has several good features: it has a linear complexity and a single input parameter that fixes the "coarseness" of segmentation. SRM algorithm gives, for each segmented region, the list of pixels belonging to it and the related mean colour. We use this output as starting point to create a vectorial representation of image.
To obtain a vectorial representation we have to find the border of segmented regions. This could be done more easily if we considered the pixels belonging to several groups (Figure 1). First of all pixels are divided in:
Due to the overall complexity of border regions a further setting into two groups is required:
An example of different kind of pixels: internal (blue), close (red) and open (green).
Figure 1: Different Kind of Pixels
After having assigned each pixel to the corresponding category we describe regions in vectorial form. In particular there are two types of curves: close curves and open curves. In both cases we could approximate their boundaries through segments with eight possible directions (Figure 2).
A close curve is a curve made up of only close pixels. Initially, we consider a simple configuration (Figure 3) to explain how segments could be found from close pixels list. The pseudo-code that describes the algorithm is the following:
initialPixel = findFirstPixel();
currentPixel = findNextPixel(initialPixel);
direction = findDirection(initialPixel, currentPixel);
segment = createNewSegment(initialPixel, direction);
while (currentPixel != initialPixel){
oldCurrentPixel = currentPixel;
oldDirection = Direction;
currentPixel = findNextPixel(oldCurrentPixel);
direction = findDirection(oldCurrentPixel, currentPixel);
if (direction != oldDirection){
setFinalCoordinate(segment, oldCurrentPixel);
insertInSegmentsList(segment);
segment = createNewSegment(oldCurrentPixel, direction);
}
}
setFinalCoordinate(segment, currentPixel);
insertInSegmentsList(segment);
|
The functions are:
currentPixel): it looks for the
next pixel in the neighbourhood following a counter
clockwise direction.
oldCurrentPixel, direction):
it creates a new segment with first coordinate
oldCurrentPixel and direction direction.
segment, oldCurrentPixel):
it sets the final coordinate of segment
segment at oldCurrentPixel.
segment): it adds
segment
in the list of segments that describes the close
curve.
Our algorithm chooses the top-left pixel of curve as initial pixel and, following the boundary in counter clockwise direction, it creates the segments necessary for a vectorial description.
There are a series of complex configuration:
To properly consider these cases it is needed to modify the algorithm described above in the following way:
while(closePixelsList contains some pixel){
currentCurve = createNewCurve();
initialPixel = findFirstPixel();
curveType = getCurveType(initialPixel);
currentPixel = findNextPixel(initialPixel, curveType);
direction = findDirection(initialPixel, currentPixel);
segment = createNewSegment(initialPixel, direction);
while (currentPixel != initialPixel){
oldCurrentPixel = currentPixel;
oldDirection = direction;
currentPixel = findNextPixel(oldCurrentPixel);
direction = findDirection(oldCurrentPixel, currentPixel);
if (direction != oldDirection){
setFinalCoordinate(segment, oldCurrentPixel);
addInCurve(currentCurve, segment);
segment = createNewSegment(oldCurrentPixel, direction);
}
}
setFinalCoordinate(segment, currentPixel);
addInCurve(curve, segment);
insertInCurvesList(currentCurve);
}
|
Some functions have been modified and other are new, in particular:
currentCurve,segment): it inserts in
currentCurve the segment segment;
currentCurve): it inserts
currentCurve in the list of curves that describes
the boundary of regions;
initialPixel): analyzing neighbours of
initialPixel it returns the type of curve (internal or external);
initialPixel,curveType): it looks for the
next pixel in the neighbourhood following a clockwise or counter
clockwise direction based on curveType value. If there is
an ambiguity the pixel on the left is chosen. Moreover each pixel have
a multiplicity equals to the number of regions they are near to. When a
pixel is chosen its multiplicity is decremented by one and when it becomes
0 that pixel is deleted from the list of close pixel.
Even if a good segmentation algorithm should create regions with simple boundaries and not ragged this is not always the case. For this reason we have divided border pixels into two groups: close pixels and open pixels. The last are the pixels devoted to describe the ragged above mentioned.
For simple configurations (Figure 4) we could use the following algorithm:
initialPixel = findFirstPixel();
currentPixel = findNextPixel(initialPixel);
direction = findDirection(initialPixel, currentPixel);
segment = createNewSegment(initialPixel, direction);
while (it is possible to find new nearby pixels){
oldCurrentPixel = currentPixel;
oldDirection = direction;
currentPixel = findNextPixel(oldCurrentPixel);
direction = findDirection(oldCurrentPixel, currentPixel);
if (direction != oldDirection){
setFinalCoordinate(segment, oldCurrentPixel);
insertInSegmentsList(segment);
segment = createNewSegment(oldCurrentPixel, direction);
}
}
setFinalCoordinate(segment, currentPixel);
insertInSegmentsList(segment);
|
It is very similar to the one described for the close curve, but the following function has a different behaviour:
For complex configuration is needed a more sophisticated algorithm:
while(openPixelsList contains some pixels){
currentCurve = createNewCurve();
initialPixel = findFirstPixel();
currentPixel = findNextPixel(initialPixel);
direction = findDirection(initialPixel, currentPixel);
segment = createNewSegment(initialPixel, direction);
while (secondList is not empty or it's the first execution){
if (there isn't new currentPixel and it isn't the first execution){
initialPixel = getPixelFromSecondList();
currentPixel = findNextPixel(initialPixel);
direction = findDirection(initialPixel, currentPixel);
segment = createNewSegment(oldInitialPixel, direction);
}
while (it's possible to find a new currentPixel){
oldCurrentPixel = currentPixel;
oldDirection = direction;
currentPixel = findNextPixel(currentPixel);
direction = findDirection(oldCurrentPixel, currentPixel);
if (direction != oldDirection){
setFinalCoordinate(segment, oldCurrentPixel);
addInCurve(currentCurve, segment);
segment =createNewSegment(oldCurrentPixel, direction);
}
}
setFinalCoordinate(segment, currentPixel);
addInCurve(currentCurve, segment);
}
insertInCurvesList(currentCurve);
}
|
Some functions have been modified and other are new, in particular:
initialPixel): it is similar to the precedent
version, but it also adds some pixel in the secondList every time
there is an ambiguity in the choice of the next pixel.
After we have tracked the boundaries of curves it is necessary to map the data by SVG primitives. In particular a generic close curve could be represented in the following way:
< path d="M x1,x1 L x2,y2 Lx3,y3 Z" stroke ="#RRGGBB" fill"#RRGGBB" /> |
where x1, y1, x2, y2, x3, y3 are the vertexes coordinates and RR, GG, BB are respectively the hex representation of red, green, blue mean value of the region that close curve belong to.
An open curve could be represented in the following way:
< path d="M x1,x1 L x2,y2 Lx3,y3" stroke ="#RRGGBB" fill="none" /> |
Open curves are not filled (fill = "none") and the starting point is not equal to final point (Z parameter is absent).
In order to obtain small file size some optimization could be done [Wor03]:
Each identified region has been properly contoured by making use of a list of segments. However, this representation is not optimal in terms of coding efficiency; in fact each border is considered twice. In order to reduce such redundancy the rendering order is used to simplify some boundaries. Just for example considering two nearby regions Ri and Rj, some borders of Ri can be extended under the image region covered by Rj with ordering such that i < j. Such simplification strategy is useful to reduce the overall number of points and primitives required by the classical boundary description. Just before boundaries reduction a closing operation is applied just to smooth ragged borders.
In order to obtain boundaries reduction an iteratively three step strategy has been implemented. The first simplification step aims to make convex each involved region. In particular it iterates over all segments setting as "blocked" (no further optimization can be done) those that have nearby regions already drawn. Afterwards it considers couples of not blocked consecutive segments (s1, s2) that form a concave region. This method considers the segment s3 starting from the initial point of s1 and ending on the final point of s2; if the triangle formed by (s1, s2, s3) segments can be added to current region without including parts of other regions already drawn, it simplifies the border removing s1, s2 and introducing the new segment s3 (see Figure 5).
The second step simplifies an oblique segment by using two segments along the main axes (see Figure 6). Like in the first simplification step it is necessary to avoid to include parts of regions already drawn.
The third and final step consists of a simplification of consecutive segments with the same direction. In particular it iterates over all not blocked segments and, detecting consecutive sequences with the same direction, it replaces them with one segment (see Figure 7). In the case of segment with opposite direction, this method simplifies these segments by making use of an algebraic sum of their length.
First simplification step: this method adds the triangle (s2, s3, s9) to region A. Moreover the region B doesn’t allow to include the triangle made up of s6, s7, s10.
Figure 5: First Simplification
Second simplification step: this method includes the triangle (s9, s11, s12) into region A.
Figure 6: Second Simplification
Example of third simplification step; this method, in this case, simplifies segments s1, s11 and s12, s4 (Figure 6) into s13 and s14 respectively.
Figure 7: Third Simplification
The overall technique can be summarized by the following pseudo code:
BorderSimplify(List RegionsList){
OrderedRegionList = sort(RegionList);
While (there are regions to process){
currentRegion = getRegion(OrderedRegionList);
nearRegionsIdList = computeNearRegionsId(currentRegion);
count = computeNumberNearRegionsAlreadyDrawn(nearRegionsIdList);
if (count ==0){
simplify = computeAndControlRect(currentRegion);
if (simplify) simplifyWithRect(currentRegion);
else iterativelySimplify(currentRegion);
} else if (count < size(nearRegionsId))
iterativelySimplify(currentRegion);
} else {
//If all nearby regions has been already drawn no simplification can be made.
}
}
}
iteratevelySimplify(Region currentRegion){
simplify = true;
while(true){
simplify = firstSimplification(currentRegion);
if (!simplify) break;
secondSimplification(currentRegion);
thirdSimplification(currentRegion);
}
thirdSimplification(currentRegion);
}
|
The functions are:
RegionList): it sorts, in decreasing order, the
regions list according to dimension of rectangle containing
the regions.
OrderedRegionList): it returns the
first element of OrderedRegionList;
currentRegion): it
computes currentRegion nearby regions identifiers;
nearRegionsIdList): it computes the number of
regions, near currentRegion, already drawn;
currentRegion): it
verifies if currentRegion can be replaced with the
rectangle containing it. This simplification has not to include
visible parts of regions already drawn.
currentRegion): it simplify
currentRegion with the rectangle containing it;
currentRegion): it
implements the first simplification step described above.
It returns true only when a simplification has been made.
currentRegion): it
implements the second simplification step described
above.
currentRegion): it
implements the third simplification step described above.
As it can be seen in Figure 8, regions produced with the boundaries simplification step are simpler than those of the previous version of SVGStat.
Comparison between old and new rendering of regions. Regions considered by new algorithm (see d, e, f) are simpler than those of the old algorithm (see a, b, c).
Figure 8: Rendering Comparison
In [BFP06a] we have shown that SVGStat, without the optimizations introduced in this work, outperforms other similar approaches like Vector Eye [VLDP03], Autotrace [Web02], VISTA [PS05], SVGenie [BBD*05] and SWaterG [BCDN05] in particular for photographic images. Maintaining the same level of perceived (and measured by PSNR) visual quality, SVGStat [BFP06a] obtains better performances in terms of compression rate. In this paper we have proposed a new step in SVGStat that, simplifying regions boundaries, allows obtaining, without losing in visual quality (see Figure 9, Figure 10, Figure 11), greater compression rate. In particular, considering visually agreeable images, we obtain an average gain in file size of 11,5 percent for photographic images (see Figure 12) and of 21,9 percent for clip art images (see Figure 13). This happens because our boundaries simplification technique is only devoted to close curves and clip arts, due to their simplicity, are described principally by this kind of curves. Moreover as shown in Figure 14 the optimized approach outperforms the previous version of SVGStat also varying the quantization parameter. In fact the new SVGStat PSNR-bpp curve is always above the other.
Visual comparison between image Lena vectorized with our old e new solution. The quality of image produced with our techniques is the same but the optimized approach produces a smaller svg file.
Figure 9: Comparison old-new SVGStat Version
PSNR comparison between old and new version of SVGStat for photographic images.
Figure 10: PSNR Comparison (photographic images)
PSNR comparison between old and new version of SVGStat for clip art images.
Figure 11: PSNR Comparison (clip art images)
Bpp comparison between old and new version of SVGStat for photographic images.
Figure 12: Bpp Comparison (photographic images)
Bpp comparison between old and new version of SVGStat for clip art images.
Figure 13: Bpp Comparison (clip art images)
Relation beetwen PSNR and bbp for Lena image in the new and old version of SVGStat.
Figure 14: PSNR and Bpp for Lena Image
Some example of original (png) and svg files produced by our approach are listed below.
 |
|
 |
|
 |
|
 |
|
 |
|
 |
Table 1
In order to compare our approach with other raster-to-vector techniques we consider svg files of the same size and we visually compare them.
Lena svg file produced by SVGenie can be viewed here.
Lena svg file produced by SVGStat can be viewed here.
Lena svg file produced by Vector Eye can be viewed here.
Tiger svg file produced by VISTA can be viewed here.
Tiger svg file produced by SVGStat can be viewed here.
XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.
