Vecart
Tags
Table of Contents
Motivation
A few years ago, I wanted to dive deeper into image processing and image transformation. At that time, I remembered this blog post from the artist Sergej Stoppel that I had read some time ago. He had developed several algorithms that could transform images into line art that could be drawn by a plotter. I decided to try to implement a similar algorithm myself using Python. I called the software the Line Portrait Generator (LPG).
The implementation of the LPG quite messy and it has many problems and limitations. For example, due to it being implemented in Python, it is rather slow. This year I started programming in Go. To get more familiar with the language, I was looking for a project that I could tackle with it. I had always planned to reimplement the LPG in a faster language and at the same time fix some of the other issues it has. Therefore, I decided to reimagine the LPG in Go.
The Software
Vecart is a tool for creating vector art specifically targeted at plotters or laser engravers (It focuses on strokes and ignores the fillings of vector shapes). It can convert raster images (e.g., PNG, JPG) into vector graphics (i.e., SVG) made up of arbitrary shapes. It is open source and freely available for everyone to use, modify, and distribute under the MIT license. The source code as well as binary executables can be found on GitHub (github.com/DavidJilg/Vecart).
The software currently provides similar features to the LPG, but it extends them. Besides the performance gains, the main difference between Vecart and the LPG is that the limitation that only vector artworks with straight lines can be generated has been lifted. Vecart supports various shapes including lines, polylines, triangles, rectangles, arbitrary polygons, circles, and text. Vecart also supports the grouping of multiple shapes to create more complex shapes. The following artwork was generated by Vecart based on differently sized triangles, rectangles, and circles.
Another major improvement that is often overlooked in software development concerns the usability of the software. The LPG was never developed to be a well usable software that I could also distribute to other people. For example, the entire configuration including the source image is hard-coded in a Python script. So to configure it, you have to edit the source code. In contrast, Vecart was from the outset developed with the goal of being a usable software that I can make available for other people. The technical details section further highlights some of the changes I made to benefit usability.
Exemplary Use Case
The following example is adapted from my Ellie’s Journey artwork, where I used the LPG to generate a series of portraits depicting the journey of Ellie Williams through the video game The Last of Us. Let’s go through the process of generating a portrait with Vecart based on the following image.
To achieve the best results, some preprocessing of the image is advisable. First I start by removing the background since I want it to be white in the generated portrait. I then edit the eyes to be a clearer white color. This results in more contrast between the sclera and the pupil in the generated portrait.
For comparison, here is an image showing the difference that the editing of the eyes has on the generated artwork. The right eye has been edited in the preprocessing, while the left one has been left in its original state.
After removing the black background and editing the eyes, I load the image into Adobe Lightroom to first convert it into an 8-bit grayscale image and then do some other optimizations such as boosting the contrast. Vecart could do the grayscale conversion itself, but doing it beforehand gives you more control over the look of the image.
Finally, I take the image exported from Lightroom and feed it into Vecart. It offers many parameters for controlling the algorithm, so I usually try out several parameter values. The following image shows a comparison of two portraits, both generated from the previously displayed input image but with drastically different parameter configurations. The left portrait was generated with an optimal configuration, and the right one was purposefully generated using a bad configuration.
The following image shows the final line portrait generated with the most optimal parameter configurations I could find. The portrait is made up of exactly 24,284 shapes.
Technical Details
Major improvements have been made to the usability of the approach first implemented in the LPG. For example, Vecart accepts JSON-based configuration files, so the user does not have to change values in the source code to configure it. Additionally, quality of life features such as warnings considering unfavorable configurations and proper console outputs have been added. There are also binaries of Vecart available on GitHub, so that users do not have to run or build the source code themselves. The readme in the repository also includes documentation and some examples to get started.
Algorithm
This section will roughly explain the algorithm that Vecart uses to generate artworks. The algorithm has the goal of placing a certain number of shapes on a canvas so that the shapes together represent the input image as closely as possible. This results in two problems that the algorithm has to solve. First, it needs to determine where the shapes should be placed. Second, it needs to find out how many shapes it should place or, more specifically, it has to figure out when to stop placing additional shapes.
The algorithm starts by dividing the image into many smaller parts with the same size. In the source code and in the parameter options, these parts are called ‘Quadrants’. Considering the actual meaning of the word ‘quadrant’ this is not really fitting. I was watching some Star Trek episodes while coding the LPG and this word is frequently used in the show to describe an area of stellar space, so I used it here. As Phil Karlton once said:
There are only two hard things in Computer Science: cache invalidation and naming things. Phil Karlton
After dividing the image into smaller quadrants, the problem of placing shapes is then solved individually for each quadrant because it is much easier to solve several small problems than it is to solve a large one. However, when solving the shape placing problem for a particular quadrant, the neighboring quadrants have to also be considered in the case of shapes that overlap multiple quadrants.
The core of the algorithm that solves the shape placing problem for individual quadrants is based on a heuristic function that scores each shape placement. The score represents how much a shape is contributing to making the the union of all shapes look like the original image. The sum of the scores of all shapes in a quadrant can, therefore, be used to determine how similar a bunch of shapes placed in a quadrant look to the part of the input image that this quadrant should represent. The heuristic function works by comparing the darkness of pixels in the area to the shapes placed in it. The darker an individual pixel is, the higher the score that the algorithm gets from the score function for placing a shape that intersects this pixel. Additionally, the score function can also punish the algorith if it places a shape onto white pixels. This behavior of the score functions teaches the algorithm to place lines carefully so that they only intersect dark pixels and avoid light colored pixels. Additionally, the score function calculates the score given to a quadrant relative to the number of shapes that it contains. This ensures that the algorithm doesn’t just place a practically infinite number of shapes in the purely dark areas, since each shape would just increase the score.
For each individual quadrant, the algorithm starts by placing shapes onto the pixels with the highest darkness. For every shape, it evaluates the impact that shape has on the score function and determines if the shape should be kept or if it should be disregarded. To tell the algorithm when to stop placing shapes, the user can set a threshold score value that needs to be reached for every quadrant regarding the score function. Once the algorithm has optimized the shape placement enough for it to satisfy the score threshold for an individual quadrant, the quadrant is considered finished. The algorithm ends once all quadrants are considered finished.
Remaining Limitations
Of the many limitations that the LPG had and that I wanted to adress in Vecart, only one still remains. To achieve the best results the user still has to do some preprocessing of the input image before handing it to Vecart. I experimented a lot with automatically adjusting input images to be suited for generating artworks but I could not get to a point where I was able to achieve better or at least equally good looking results in comparison to manually preprocessing the images. Maybe a human touch is just essential for creating good art and maybe that is a good thing regarding the current flood of underwhelming AI-generated art.
Future Work
I currently do not plan to add any big feature updates to Vecart in the near future but I do have some ideas for extensions that could be added in the long term. For example, it would be nice if Vecart could also be used to generate G-Code based on the generated artworks so that you do not need additional software control CNC-machines that can transfer the artwork to our physical world. Additionally, I would like to explore some other ways of representing raster images with vector graphics that do not rely on simply placing shapes on a canvas.
Further Examples
Earth Rise
Zebra
Single Shape Types
All following examples have been generated using the following source image.
Just Lines
Just Circles
Just Rectangles
Just Triangles
Just Text (‘DJ’)
