A Formalization of Image Vectorization by Region Merging

Image vectorization converts raster images into vector graphics composed of regions separated by curves. Typical vectorization methods first define the regions by grouping similar colored regions by color quantization, then approximate their boundaries by Bézier curves. In that way, the raster input is converted into an SVG format parameterizing the regions’ colors and the Bézier control points. This compact representation has many graphical applications thanks to its universality and resolution-independence. In this paper, we remark that image vectorization is nothing but an image segmentation, and that it can be built by fine to coarse region merging. Our analysis of the problem leads us to propose a vectorization method that alternates region merging and curve smoothing. We formalize the method by alternate operations on the dual and primal graph induced by any domain partition. In that way, we address a limitation of current vectorization methods, which separate the update of regional information from curve approximation. We formalize region merging methods by associating them with various gain functionals, including the classic Beaulieu–Goldberg and Mumford–Shah functionals. More generally, we introduce and compare region merging criteria that involve the number of regions, the scale, the area, and the internal standard deviation of each region. We also show that the curve smoothing, implicit in all vectorization methods, can be performed by the shape-preserving affine scale-space. We extend this flow to a network of curves and give a sufficient condition for the topological preservation of the segmentation. The general vectorization method that follows from this analysis shows explainable behaviors, explicitly controlled by a few intuitive parameters. It is experimentally compared to state-of-the-art software and proved to have comparable or superior fidelity and cost efficiency.