Smoothing out sketches’ rough edges Artists may soon have at their disposal a new MIT-developed tool that could help them create digital characters, logos, and other graphics more quickly and easily.
Many digital artists rely on image vectorization, a technique that converts a pixel-based image into an image comprising groupings of clearly defined shapes. In this technique, points in the image are connected by lines or curves to construct the shapes. Among other perks, vectorized images maintain the same resolution when either enlarged or shrunk down.
To vectorize an image, artists often have to hand-trace each stroke using specialized software, such as Adobe Illustrator, which is laborious. Another option is using automated vectorization tools in those software packages. Often, however, these tools lead to numerous tracing errors that take more time to rectify by hand. The main culprit: mismatches at intersections where curves and lines meet.
In a paper being published in the journal ACM Transactions on Graphics, MIT researchers detail a new automated vectorization algorithm that traces intersections without error, greatly reducing the need for manual revision. Powering the tool is a modified version of a new mathematical technique in the computer-graphics community, called “frame fields,” used to guide tracing of paths around curves, sharp corners, and messy parts of drawings where many lines intersect.
The tool could save digital artists significant time and frustration. “A rough estimate is that it could save 20 to 30 minutes from automated tools, which is substantial when you think about animators who work with multiple sketches,” says first author Mikhail Bessmeltsev, a former Computer Science and Artificial Intelligence Laboratory (CSAIL) postdoc associate who is now an assistant professor at the University of Montreal. “The hope is to make automated vectorization tools more practical for artists who care about the quality of their work.”
Co-author on the paper is Justin Solomon, an assistant professor in CSAIL and in the Department of Electrical Engineering and Computer Science, and a principal investigator in the Geometric Data Processing Group.
Guiding the lines
Many modern tools used to model 3-D shapes directly from artist sketches, including Bessmeltsev’s previous research projects, require vectorizing the drawings first. Automated vectorization “never worked for me, so I got frustrated,” he says. Those tools, he says, are fine for rough alignments but aren’t designed for precision: “Imagine you’re an animator and you drew a couple frames of animation. They’re pretty clean sketches, and you want to edit or color them on a computer. For that, you really care how well your vectorization aligns with your pencil drawing.”
Many errors, he noted, come from misalignment between the original and vectorized image at junctions where two curves meet — in a type of “X” junction — and where one line ends at another — in a “T” junction. Previous research and software used models incapable of aligning the curves at those junctions, so Bessmeltsev and Solomon took on the task.
The key innovation came from using frame fields to guide tracing. Frame fields assign two directions to each point of a 2-D or 3-D shape. These directions overlay a basic structure, or topology, that can guide geometric tasks in computer graphics. Frame fields have been used, for instance, to restore destroyed historical documents and to convert triangle meshes — networks of triangles covering a 3-D shape — into quadrangle meshes — grids of four-sided shapes. Quad meshes are commonly used to create computer-generated characters in movies and video games, and for computer-aided design (CAD) for better real-world design and simulation.
Bessmeltsev, for the first time, applied frame fields to image vectorization. His frame fields assign two directions to every dark pixel on an image. This keeps track of the tangent directions — where a curve meets a line — of nearby drawn curves. That means, at every intersection of a drawing, the two directions of the frame field align with the directions of the intersecting curves. This drastically reduces the roughness, or noise, surrounding intersections, which usually makes them difficult to trace.
“At a junction, all you have to do is follow one direction of the frame field and you get a smooth curve. You do that for every junction, and all junctions will then be aligned properly,” Bessmeltsev says.
Cleaner vectorization
When given an input of a pixeled raster 2-D drawing with one color per pixel, the tool assigns each dark pixel a cross that indicates two directions. Starting at some pixel, it first chooses a direction to trace. Then, it traces the vector path along the pixels, following the directions. After tracing, the tool creates a graph capturing connections between the solid strokes in the drawn image. Using this graph, the tool matches the necessary lines and curves to those strokes and automatically vectorizes the image.
In their paper, the researchers demonstrated their tool on various sketches, such as cartoon animals, people, and plants. The tool cleanly vectorized all intersections that were traced incorrectly using traditional tools. With traditional tools, for instance, lines around facial features, such as eyes and teeth, didn’t stop where the original lines did or ran through other lines.
One example in the paper shows pixels making up two slightly curved lines leading to the tip of a hat worn by a cartoon elephant. There’s a sharp corner where the two lines meet. Each dark pixel contains a cross that’s straight or slightly slanted, depending on the curvature of the line. Using those cross directions, the traced line could easily follow as it swooped around the sharp turn.
“Many artists still enjoy and prefer to work with real media (for example, pen, pencil, and paper). … The problem is that the scanning of such content into the computer often results in a severe loss of information,” says Nathan Carr, a principal researcher in computer graphics at Adobe Systems Inc., who was not involved in the research. “[The MIT] work relies on a mathematical construct known as ‘frame fields,’ to clean up and disambiguate scanned sketches to gain back this loss of information. It’s a great application of using mathematics to facilitate the artistic workflow in a clean well-formed manner. In summary, this work is important, as it aids in the ability for artists to transition between the physical and digital realms.”
Next, the researchers plan to augment the tool with a temporal-coherence technique, which extracts key information from adjacent animation frames. The idea would be to vectorize the frames simultaneously, using information from one to adjust the line tracing on the next, and vice versa. “Knowing the sketches don’t change much between the frames, the tool could improve the vectorization by looking at both at the same time,” Bessmeltsev says.