Mikhail Bessmeltsev with a colleague developed new algorithms for graphics vectorization

From left to right: the original, equipped field (frame field) and the final result. On the base of a noisy bitmap image in grayscale, an equipped field is calculated, aligned with the lines of the picture. Sharp angles such as X- and T-intersections are superimposed by vectors in both directions. Then the drawing topology is extracted from this field - and the final generation of vector curves is performed.

Image vectorization is a fundamental component of the workflow in graphic design, engineering and computer animation. It converts the drafts of artists and designers into smooth curves needed for editing.

The first image vectorization algorithms appeared in the early 1990s and
used in vector graphics editing tools such as Adobe Illustrator (Live Trace), CorelDRAW (PowerTRACE) and Inkscape. Despite their widespread adoption in industry, these algorithms still suffer from serious flaws and are in active development. In several industries where vectorization is essential, including traditional animation and engineering design, it is often done manually. Designers painstakingly trace the scanned image using drawing tools.

Unfortunately, modern algorithms, even for clean drawings, do not allow to precisely vectorize X- and T-intersections, so vector drawings with incorrect connectivity are obtained. Because of these problems, designers often hesitate whether to use automated vectoring tools. Their reliability is questionable. More precisely, it has been so far until two researchers, Mikhail Bessmeltsev and Justin Solomon, from the computer science and artificial intelligence laboratory (CSAIL) of the Massachusetts Institute of Technology have not adapted well-known mathematical algorithms for vectoring raster images.
')
Incorrect processing of junctions and intersections of lines is the main drawback of all vectorization algorithms. These errors lead to the generation of incorrect topology and violation of connectivity. The new vectorization method is based on modern mathematical algorithms for processing rigged fields. The algorithm is specially adapted to eliminate ambiguity at the line junctions without loss of quality.


a) A local approach to vectoring transitions, proposed by Noris and his colleagues in 2013, may lead to incorrect or inaccurate connections. b) Favreau et al. (2016) method can produce a result that deviates significantly from the raster original. (c) The new method proposed by Bessmaltsev and Solomon is superior to the previous vectorization developments.

The problem is exacerbated by the noisiness of the original raster graphics, which remains after scanning the paper original. Violation of the connectivity does not allow to apply the tools of the automatic fill / coloring, that is, such vector drawings still have to be brought to mind manually.

Taking into account these problems of existing methods, the authors of the scientific work proposed a new method of tracing for images, including special processing of T-shaped and X-shaped intersections, where the initial information can be ambiguously interpreted. The main technical innovation is to use an equipped field with two pairs of vectors for each point on the plane.


In a rigged field, at least one direction of the field is aligned with the original curve, and near X- and T-intersections it is aligned in both directions.

The authors of the scientific work say that the equipped fields are logically and naturally suitable for tracking the orientation of curves in such abrupt transitions, but for some reason they have never been used to vectorize images. The results shown demonstrate that the quality of vectorization is significantly higher than that of previous methods. Even on highly noisy originals, the geometry of the curves is not lost and coincides with the original outlines.

Examples

(click to open high resolution image)


Tool sensitivity to small changes in the source image






The method is not sensitive to the resolution of the original image


Vectorization works well even on highly noisy original.

The new tool will greatly facilitate the life of designers and illustrators: “According to a rough estimate, it will save 20 to 30 minutes when working with automated tools [in each image]. This is a significant result for animators who process a lot of sketches, ” says the leading author of a scientific paper, Mikhail Bessmeltsev, a former employee of CSAIL, and now associate professor (assistant professor) at the University of Montreal. “We hope to make automated vectorization tools more convenient for artists who care about the quality of their work.”

The scientific article was published on January 5, 2018 on the website of the preprints arXiv.org (the second version of the article - September 5, 2018, arXiv: 1801.01922v2). It is accepted for publication in the scientific journal ACM Transactions on Graphics .