String art is a technique to draw by weaving a string between pins, obtaining a picture entirely composed of straight lines. Its origins are probably ancient, but a computational approach to produce photorealistic results has been popularized by artist Petros Vrellis in 2016. I have recently stumbled upon a blog post by Possibly Wrong about this topic, and I decided to give it a go myself, before looking at any other implementation. It turns out that even a simple algorithm can yield good results, especially if we allow many pins and a very long string.

First attempt

Once a grayscale input image is fixed, the first idea was to use a very simple greedy algorithm. Starting from any pin, we can look at all the possible lines from the starting pin to any of the others, and choose the darkest one, then wind the string around that pin and reiterate. By darkest we mean that we imagine this line overlapped to the original image, look at the average value of the pixels below the line, and pick the line with the lowest average. If

• $I_0(x)$ is the brightness of the original image $I_0$ at its point $x$ (lower means darker),
• $\ell_{p_0,p_1}$ is a line from the $p_0$-th pin to the $p_1$-th pin,

then the goal it to find a sequence of pins $p_0, p_1, \ldots, p_K$ which creates the string image, stopping at some step $K$ which we need to find.

We decide to start with any pin $p_0$, and we look for the next pin $p_1$ by minimizing the quantity

$$f_{I_0,p_0}(n) = \frac{\int_{x \in \ell_{p_0,n}} I_0(x) dx}{\text{length}(\ell_{p_0,n})}$$

over all possible choices of the second pin $n$.

Now that the first step is done and we have stretched the string from $p_0$ to $p_1$, it would be tempting to simply find $p_2$ the exact same way. The first problem is that each pin as a uniquely determined successor, this means that if at some point we go back to $p_0$ (or any of the previous pins), then we end up in a loop without a possibility of adding new lines. This can be easily solved by keeping track of which lines has already been added. Then we need to figure out a way to stop, otherwise, since already added lines cannot be used again, we will simply exhaust all the possible lines until we hit a pin which is already connected to all the others. Intuitively, a good moment to stop is when the average brightness of the best line is at most the halfway point of the greyscale spectrum, as drawing a line exceeding that quantity will surely bring us further away from the input image than not drawing it. Here is what this algorithm produces, stopping at different points of the grayscale spectrum.

Note that some details are actually captured, like the shape of the face and the dark background, but we are far from creating a photorealistic picture.

A slightly refined algorithm

So far we have an algorithm which is good at drawing dark and bright regions of the canvas, but it misses all the details. The reason is that it focuses on the dark regions, keeping drawing dark lines regardless of what the canvas currently looks like. The idea is to use this information to better choose the following pin. So let’s perform the fist step as described below, but once we found $p_1$ we modify the original input image $I_0$ by whitening the pixels below $\ell_{p_0, p_1}$, producing the image $I_1$. We do this at each step, producing intermediate images $I_1, I_2, \ldots$, intuitively we can think of this as

$$I_k = I_{k-1} - \ell_{p_{k-1}, p_k}, \text{ for } k > 0,$$

where the subtraction indicates that the dark pixels of the line are subtracted from the pixels of the image, making them brighter. At the $k$-th step, we find $p_k$ as the pin $n$ minimizing the quantity

$$f_{I_k,p_k}(n) = \frac{\int_{x \in \ell_{p_{k},n}} I_{k}(x) dx}{\text{length}(\ell_{p_{k},n})}.$$

In this way the algorithm dares drawing lines where we need some darker details, instead of focusing on ‘‘safer’’ dark areas. Note that we still need to stop the algorithm for some average value for the new lines, but this time we could be more conservative, and already for some low values on the grayscale spectrum we get some improved result.

This is already an improvement from the previous attempt, as we can see some details as the eyes and the hair, but it is still barely recognizable.

The final algorithm

Note how the previous algorithm sketches some details, like the eyes, but then does not define them properly. The reason seems to be that the intermediate image $I_k$ loses information about these details too fast, as they quickly get whitened by the previous lines. The next step is then to be more conservative with this whitening process, and instead of subtracting a black line from $I_k$ to obtain $I_{k+1}$, we subtract a gray one, or - better - we subtract a black line multiplied by an opacity value $o \in (0,1)$. Opacity works multiplicatively, intuitively this means that lines will brighten up dark regions faster than brighter ones. On the output image this has the effect of forcing more lines to overlap on darker spots. To do this operation in a cleaner way I used a draft image $D_0$, which is initialized as a white image of the same size as the input image $I_0$, and we progressively add lines with some transparency to it. Formally, at the step $k > 0$ we update the draft image as follow

$$ D_k = D_{k-1} + o \cdot \ell_{k-1, k}. $$

We can think of what previously was $I_k$ as $I_0 - D_{k-1}$, with the difference that now we are subtracting a whole range of gray pixels, instead of just black ones. The advantage of using $D_k$ is that sometimes we might end up overshooting, and get pixels on the draft image which are darker than on the input image. If we simply keep track of lines by whitening $I_0$, this occurrences will not be recorded, as pixel will not get whiter than white. On the other hand by using $D_k$ we can decide to minimize both $I_0$ and the negative $\overline{D_k} = W - D_k$ of the draft image $D_k$ at the same time:

$$ f’_{I_k,p_k}(n) = \frac{\int _{x \in \ell _{p_k,n}} I_0(x) + \overline{D_k}(x) dx}{\text{length}(\ell _{p_k,n})} $$

Above, $W$ is the value corresponding to a complete white pixel (e.g. 255 for 8-bits grayscale).

This worked like a charm, here are some results for different values of opacity.

For the picture at the top of the page I have picked a value of $0.15$.

Is the greedy approach restrictive?

One might argue that this greedy approach might be too rough, what if instead of picking the best line, we pick one which is slightly worse but which allows us to draw better lines later on? This makes absolutely sense, and such an algorithm would surely improve the final result. We could also derive from the previous one. Instead of minimizing the brightness of a line from a given pin over all the possible choices for the following pin, we could at each step minimize the same quantity over all the possible choices of both pins. In this way we could create an image made up of disconnected segments on the canvas, which then we can attempt to reorder to see if they can be concatenated correctly. This is extremely unlikely to be the case, this problem is equivalent to find an Eulerian path in the graph defined by all the segments, and a necessary (and sufficient) condition for one to exist is that this graph is connected (extremely likely if there are many pins) and every vertex has even degree (extremely unlikely if there are many pins). But at this point we can force the graph to satisfy this condition by progressively adding lines until all vertices have even degree, which can be done with little impact on the final image.

The question is how much better the results will get by doing so? We can make an experiment comparing the result of the greedy algorithm with a modified “disconnected” one drawing the best line at each step, without bothering checking that the latter can be realized with a unique connected string.

While differences are expected when the number of pins is small, the results are almost identical when the number grows. Since for photorealistic applications the number of pins needs to be in the hundreds, I decided to stick with the greedy - and way faster - algorithm.

Final touches

At this point I was quite satisfied with the result. As a final touch I felt that it would be against the spirit of the string artist to stretch short lines between neighboring pins, so I added the options to control how close two consecutive pins can be. For the picture at the top of the page the number I have picked is $32$, one eighth of the total number of pins, meaning that two consecutive pins on the string path are at least $32$ pins away from each other.

Note that this choice has the effect of discoloring outside a circle, while keeping all the details inside of it. Such circle is the one tangent to all the chords between pairs of closest possible pins.

Implementation and choice of parameters

The implementation of the algorithm is available on my GitHub. It is written in C++ and I have followed quite closely the algorithm described above. I added a bunch of arguments to granularly control all the parameters I have discussed so far. Here is how a call to the script looks like:

string_art input.pgm num_pins opacity threshold skipped_neighbors output_scale output.pgm

The opacity and threshold arguments can be used to tweak the final result, see the differences in the table below.

For parsing the image and the other argument I readapted the code from Possibly Wrong. The input and output images are square binary “P5” .pgm (portable graymap) images, as they are easy to read and write.

Results and comparisons

On the post on Possibly Wrong there is a comparison between their result with those from a paper by Birsak et al. The following results of my implementation can be compared with the table at the bottom of the post.

Regarding the algorithm used, it seems like I have basically reinvented the wheel, as most of the implementations I have looked up seem to follow a similar logic. Birsak et al. - beside several other improvements and technicalities - instead of opacity use a block-based upscaling where a pixel of the original image corresponds to a block, and when multiple threads pass through that block they update the fraction of its area which is covered, then they transform this fraction into a gray tone which is finally compared against the original pixel. This approach has the advantage to automatically set the correct the ‘‘opacity’’ when changing the scale factor, while with my implementation they are independent and the opacity is manually set.

At the end of the day, I am extremely satisfied with the results and the path leading me to the final version, and comparing the outputs with those on the original paper it seems that - and here I might be very wrong - the conversion from list of pins $p_0, p_1, \ldots$ to a computer image makes as big of a difference as the algorithm used, at least for these large values. I use a Bresenham line black-or-white approach, where probably a antialiased line with an alpha channel would have made the result sharper. Maybe I could have tried to output the image as a .svg, and let the conversion do the rest.

Some trippy animations

Beside the mandatory animated sequence of lines that generate the final image at the top of the page, we can use animations to visualize how the output changes when we let one parameter vary, and fix all the others. The results are indeed trippy!