A Novel Rendering Strategy for SVG Vectorization

Keywords: SVG , Rendering Order , Raster to Vector

Dr. Sebastiano Battiato
D.M.I. Università di Catania
Via Andrea Doria, 6
95125, Catania
Italy
battiato@dmi.unict.it

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.

Giovanni Puglisi
D.M.I. Università di Catania
Via Andrea Doria, 6
95125, Catania
Italy
puglisi@dmi.unict.it

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.


Abstract


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.


Table of Contents


1. Introduction
2. SVGStat
3. SVG Generation Code
4. Boundaries Simplification
5. Experimental Results
Bibliography

1. Introduction

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.

2. SVGStat

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:

tipi_di_pixel_60.png

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).

directions_60.png

Possible directions of segments that approximate the boundaries of regions.

Figure 2: Directions

simple_region_60.png

An example of region with simple boundaries.

Figure 3: Simple Boundaries

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:

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:

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.

simple_open_curve_60.png

An example of simple open curve.

Figure 4: Simple Open Curve

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:

3. SVG Generation Code

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]:

4. Boundaries Simplification

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.

firstSimplification.png

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

secondSimplification.png

Second simplification step: this method includes the triangle (s9, s11, s12) into region A.

Figure 6: Second Simplification

thirdSimplification.png

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:

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.

SVGStat_fig_8.png

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

5. Experimental Results

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.

Lena_old_new.png

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_photographic.png

PSNR comparison between old and new version of SVGStat for photographic images.

Figure 10: PSNR Comparison (photographic images)

PSNR_clip_art.png

PSNR comparison between old and new version of SVGStat for clip art images.

Figure 11: PSNR Comparison (clip art images)

bpp_photographic.png

Bpp comparison between old and new version of SVGStat for photographic images.

Figure 12: Bpp Comparison (photographic images)

bpp_clip_art.png

Bpp comparison between old and new version of SVGStat for clip art images.

Figure 13: Bpp Comparison (clip art images)

PSNR_bpp_lena_old_new.png

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.

flowers.png

svg file

kodim01.png

svg file

kodim03.png

svg file

kodim07.png

svg file

kodim21.png

svg file

kodim23.png

svg file

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.

SVGenieLena.png

Raster version of Lena svg file produced by SVGenie;

Figure 15: Lena SVGenie

Lena svg file produced by SVGenie can be viewed here.

Lena_Q_3000.png

Raster version of Lena svg file produced by SVGStat;

Figure 16: Lena SVGStat

Lena svg file produced by SVGStat can be viewed here.

VectorEyeLena.png

Raster version of Lena svg file produced by Vector Eye;

Figure 17: Lena Vector Eye

Lena svg file produced by Vector Eye can be viewed here.

VistaTiger.png

Raster version of Tiger svg file produced by VISTA .

Figure 18: Tiger VISTA

Tiger svg file produced by VISTA can be viewed here.

tiger_Q_650.png

Raster version of Tiger svg file produced by SVGStat.

Figure 19: Tiger SVGStat

Tiger svg file produced by SVGStat can be viewed here.

Bibliography

[BBD*05]
Barbera G., Di Blasi G., Gallo G., Messina G. Advanced SVG Triangulation/Polygonalization of Digital Images. In proceedings of IS&T/SPIE Electronic Imaging 2005.
[BCDN05]
Battiato S., Costanzo A., Di Blasi G., Gallo G., Nicotra S. SVG Rendering by Watershed Decomposition. In proceedings of IS&T/SPIE Electronic Imaging 2005.
[Bat05a]
Battiato S., Di Blasi G., Gallo G., Messina G., Nicotra S. SVG Rendering of Digital Images: an Overview. In poster proceedings of ACM/WSCG2005
[BFP06a]
Battiato S., Farinella G.M., Puglisi G. Statistical Based Vectorization for Standard VectorGraphics. In Fifth Int.Workshop on Computer Graphics and Geometric Modeling LNCS (2006)
[BFP06b]
Battiato S., Farinella G.M., Puglisi G. SVG Vectorization by Statistical Region Merging. In Proocedings of Fouth Conference Eurographics Italian Chapter (2006), Catania (Italy).
[DHH02]
DUCE D., HERMAN I., HOPGOOD B. Web 2D Graphics File Format. Computer Graphics forum 21, 1 (2002), 43–64.
[JPE]
ISO/IEC JTCI/SC29/WG! N1646: JPEG2000 final committee draft v1.0. http://www.jpeg.org/jpeg2000/
[Kuh03]
KUHL K. Kvec 2.99, 2003. Copyright KKSoftware, http://www.kvec.de
[NN04]
NOCK R., NIELSEN F. Statistical Region Merging. IEEE Transaction on Pattern Analysis and Machine Intelligence 26, 11 (NOVEMBER 2004), 1452–1458.
[PS05]
PRASAD L., SKOURIKHINE A. Raster to Vector Conversion of Images for Efficient SVG Representation. In Proceedings of SVGOpen’05 (August 2005), NL.
[Qui03]
QUINT A. Scalable Vector Graphics. IEEE Multimedia 3 (2003), 99–101.
[VLDP03]
VANTIGHEM C., LAURENT N., DECKEUR D., PLANTINET V. Vector eye 1.0.7.6, 2003. Copyright SIAME e Celinea, http://www.siame.com
[Web02]
WEBER M. Autotrace 0.31, 2002. GNU General Public License, http://www.autotrace.sourceforge
[Wor03]
WEBER M. WORLD WIDE WEB CONSORTIUM: Scalable Vector Graphics (SVG) 1.1 Specification, 2003. http://www.w3.org/TR/2003/REC-SVG11-20030114/

XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.