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 made.
Vectorization of images is a fundamental component of the workflow in graphic design, technology and computer animation. It converts the rough drawings 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 the 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 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 vectorization of 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 the vectoring of transitions, proposed by Noris and his colleagues in 2013, can 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 previous developments in vectorization.
The problem is exacerbated by the noisiness of the original raster graphics, which remains after scanning the paper original. The 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 by hand.
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 an equipped field, at least one direction is aligned with the original curve, and near X- and T-intersections it is aligned in both directions.
Scientific authors say that equipped fields are logical and natural for tracking orientation of curves in such sharp transitions, but according to which 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(a high resolution image is opened by clicking) Sensitivity of the tool to small changes in the original image The method is not sensitive to the resolution of the original image Vectorization of quality works even on highly noisy original The new tool will greatly facilitate the life of designers and illustrators: minutes when working with automated tools [in each image]. This is a significant result for animators who process a lot of sketches, says
Lead author of the scientific work is 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 site of the preprints arXiv.org ( second version of the article - September 5, 2018, arXiv: 1801.01922v2). It is accepted for publication in the scientific journal ACM Transactions on Graphics .