Line Portrait Generator
Tags
Table of Contents
Motivation
As for many of my projects, especially in the software realm, the inspiration for this projected originated in the desire to learn a new skill. I wanted to dive deeper into image processing and image transformation. At that time, I remembered a 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 (click here to view the mentioned article). I decided to try to implement a similar algorithm myself using Python.
The Software
My Line Portrait Generator software is entirely written in Python, and it can transform a raster image such as a .png file into a vector graphics (.svg) file that represents the original image by only using straight lines. Let’s start with an example of what the software can do before diving deeper into the technical details.
Exemplary Use Case
The following example is taken from my Ellie’s Journey artwork, where I used the software 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 line portrait based on the following image.
Due to some limitations of my software, the best results can only be achieved with some preprocessing of the image. 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 end result. The right eye has been edited in the preprocessing, while the left one has been left in its original state.
After cutting out the 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. In the future, I want to automate this process even further and make the software more resilient to a wider range of image characteristics.
Finally, I take the image exported from Lightroom and feed it into my software. It offers many parameters for controlling the algorithm, so I usually try out many parameter values through what is commonly referred to as a grid search. A grid search is a technique where you systematically explore various combinations of specified parameters and values. My software has a build in function that can perform such a search. The following image shows a comparison of two line 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 38,420 lines.
Technical Details
This section will roughly explain the algorithm that my software uses to generate the line portraits. The algorithm has the goal of placing a certain number of straight lines on a canvas so that the lines 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 lines should be placed. Second, it needs to find out how many lines it should place or, more specifically, it has to figure out when to stop placing additional lines.
The algorithm starts by dividing the image into many smaller parts with the same size. The problem of placing lines is then solved individually for each area because it is much easier to solve a bunch of small problems than it is to solve a large one. However, when solving the line placing problem for a particular area, the neighboring areas have to also be considered in the case of lines that overlap multiple areas.
The core of the algorithm that solves the line placing problem for individual areas is based on a score function. The score function can determine how similar a bunch of lines placed in that area look to the part of the input image that this area should represent. The score function works by comparing the darkness of pixels in the area to the lines placed in it. The darker an individual pixel is, the higher the reward that the algorithm gets from the score function for placing a line that intersects this pixel. The opposite, however, is also true. The lighter a pixel is, the higher is the punishment that the score functions deals to the algorithm if it places a line that intersects that pixel. 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 an area relative to the number of lines that the area contains. This ensures that the algorithm doesn’t just place a practically infinite number of lines in the purely dark areas, since each line would just increase the score.
For each individual area, the algorithm starts by placing lines of different lengths in different, mostly random positions. For every line, it evaluates the impact that line has on the score function and determines if the line should be kept or if it should be disregarded. To tell the algorithm when to stop placing lines, the user can set a threshold score value that needs to be reached for every area regarding the score function. Once the algorithm has optimized the line placement enough for it to satisfy the score threshold for an individual, the area is considered finished. The algorithm ends once all areas are considered finished.
Limitations
The software has several limitations that arise from its architecture. For example, the algorithm needs significant preprocessing of an image to achieve good results. Additionally, it is very computationally intensive and since it is written in Python, it is rather slow. To achieve usable running times for generating an image, I had to resort to using the Pypy Just-in-time compiler and the multiprocessing module for true parallel computation. Even with these optimizations, it still takes about 10 to 30 minutes to generate a good-looking line portrait. This is problematic when you want to perform a grid search with many different parameter values. Python is simply not a fast enough language for this kind of computationally intensive tasks, if you cannot rely on a library written in C.
Another limitation that I find a bit annoying is that the algorithm only supports placing single straight lines. It would be interesting if it allowed to place symbols or shapes made up of multiple lines onto a canvas. However, the way it was implemented makes it difficult to change this behavior retroactively.
Future Work
Due to the limitations of the software, I am planning to reimplement it in Go which is a much faster programming language than Python. The new implementation should mitigate the performance problems and should also address some of the additional features that I am desiring. For example, it should allow placing arbitrary shapes made up of multiple lines onto a canvas instead of just single straight lines. Once I have finished this project, I will update this article to include the new implementation.
Update 2024-10-09: I have reimagined the software in a tool called Vecart. It is written in Go so it is faster and it also improves on some of the other problems mentioned in this article. Additionally, it is open source and, therefore, free to use, modify, and distribute. You can read about it in this blog post.