In the previous part we crafted a decent algorithm for monochrome String-Art images, but why stop here? Although this part diverged from what my original intention for this project was, I wanted to make the most out of it.

Generalizing the monochrome algorithm to multicolor images is definitely not straight-forward. Given the subtractive nature of real-life colors, the naive method would be to apply the monochrome algorithm per channel, and render using CMYK (cyan, blue, magenta, black — the opposites of red, green, blue, white) threads. This works in theory and even in simulation, but when rendering with opaque strings it just completely fails.

A note about color theory

I chose to model color blending in the straight-forward method — by simple addition in RGB space, but this is certainly not the most accurate color blending model there is. Our perception of colors (and color blending) is much more complicated, and modelling a correct color space is key for success of the multicolor algorithm. LAB for example, is considered a perceptual color space much more similar to the way the human eye works.

In algorithms study, there are usually two main approaches to extend an algorithm to a broader/harder case:

1. Reduction — Taking the harder problem and breaking it into smaller, more manageable parts which we may already have the solution to.
2. Generalization — Looking at the base case as a specific case of a more general problem, and extending the idea of the base case to handle the general case.

With this in mind, I’ll break down how each approach leads us to different algorithms, both based on the monochrome algorithm which we already have.

Reduction — Dithering + Monochrome Optimizer

After trying a few methods, and conducting some research, I came across this excellent blogpost by Callum Mcdougal, who made a very similar project (and from whom I borrowed most of my example images displayed here below). He proposed a very interesting idea, which I had been circling around myself in my trials.

The key here is an image processing algorithm called Dithering, specifically Floyd-Steinberg dithering. It is the process of approximating an image with a small color-palette, based on the idea that the human eye blends nearby colors. For example, a chess-board image with alternating black and white pixels will, from far enough away, just look gray. The algorithm works by scanning the image pixel by pixel, approximating the nearest color from the palette for each pixel, and diffusing the estimation error to the surrounding pixels.

Building on this, we draw up the following method:

1. Initialization — Choose an appropriate color palette for the image (more on this later).
2. Preprocessing — Apply dithering to produce a single binary image for each color in the palette.
3. Optimization — Run the monochrome algorithm on each color-image separately.
4. Postprocessing — Interweave the threads of each color-image to a single solution.

For the postprocessing part, I came up with two methods:

1. Interweave — Based on Callum Mcdougal’s idea, we:
   a. Order the colors from lightest to darkest.
   b. Reverse the order of threads for each color. This is because we assume that in the optimization process, the more important lines were discovered earlier, so we would like them on top.
   c. Cyclically add only a segment of each color’s threads (e.g., 25% of color #1, 25% of color #2, 25% of color #3, then the next 25% of each color until done).
2. Combine by simulation — A different, optimization based, approach. Now that we have a fixed list of threads per color, we may solve a simpler optimization problem, which only chooses the next color to add in each step, progressing through the strings of each color in order. Since the search space is very small (only a single line to test per color) it runs pretty fast. Then just flip the order, placing the more important threads on top.

Personally, I couldn’t decide which one worked better, but we may point out the difference between the approaches: Interweave is more user controllable, and Combine is more automatic but can sometimes turn out worst.

The nice thing about this method, is that it’s agnostic to the monochrome optimization algorithm being used in the per-color part. Any String-Art algorithm that works on monochrome images may be plugged in here and be expanded to work on multicolor images.

Generalization — Multicolor Binary Linear optimizer

First, let’s recall our monochrome problem and optimization rules, equations (3)-(5) from the previous post:

The idea here is to rephrase our linear approximation of the optimization problem to the more general case of multicolor strings. Formally, we slightly change the definitions of the matrices and vectors, and add color representation:

• b (hw × 3) - The flattened RGB image.
• C (k × 3) - The color dictionary. Each row represents the RGB of a different color in the dictionary.
• x (n × k) - A binary vector representing which lines (from all possible nail-pairs) are added to the String-Art solution, and in which color of the color dictionary. We allow at most a single 1 per row.
• A (hw × n) - The transformation matrix, doesn’t change from it’s original definition.

Now we optimize for l — the line number (as before), but also for c — the color number. The new optimization problem becomes:

And the updated equations (this time I won’t show the derivation):

With A⁎ₗ being the l-th column of A, and Cc⁎ being the c-th row of C. With these update equations, we apply the exact same greedy iteration algorithm as the original monochrome solution, with each step adding a string of a new color.

Implementing this in practice

There are some software engineering technicalities here, such as how we enforce each color to start from its previous nail, how we efficiently implement the calculations of equation (4') or how we make sure that we don’t switch colors too often.

Finally, as in the previous approach, we assume that the more important lines are found earlier, so we flip the order in postprocessing.

A slight improvement — CMY-log

Diving a bit deeper into color theory, I found that color blending behaves differently than just simple additive RGB blending. A more accurate model assumes multiplicative blending in CMY space (the complement of RGB). But how do we simulate multiplicative blending when all our equations above are linear? The good old log trick will come in handy, as we find that we can just slightly change the inputs of the above optimization problem, and get the desired multiplicative behavior.

A single pixel color blending in this model is represented by:

Therefore, we can change the inputs accordingly:

And from here we just solve the same optimization problem as before, with the updated inputs.

Finding the Color Palette

We have just one last problem left to solve. Both methods heavily rely on choosing the correct color palette to approximate the image. From my experience, the algorithm is very sensitive to the chosen colors, and choosing even a slightly off palette will significantly degrade the results for most images. It’s therefore very important to choose the best color palette in the preprocessing/initialization step.

Seeing as my aim was to have the algorithm be as much plug-and-play as possible, I gave a shot at a few different approaches, varying in levels of automaticity. I’ll lay out my trials process approximately as it went.

1. Manual color palette — The least automatic method, just receive a palette defined by the user. This has the best potential of being the most accurate, but finding the exact right palette may be hard and tiresome.
2. Clustering-based palette — Run a clustering algorithm (such as KMeans or Median-Cut) on the image pixels to choose the k most dominant colors. This is the most automatic method, as it has no need for a predefined color dictionary, but unfortunately didn’t work for most images, since clustering algorithms tend to find average centers for clusters, and not the most common ones.
3. Histogram-based palette — First define a fairly small (~25 colors) but highly representative color dictionary. Now we calculate a discrete histogram on the image pixels with this dictionary. An important addition here is to smooth the histogram, so that different shades of the same color (or perceptually similar colors) will also be accounted for. This method unfortunately resulted in picking different shades of the same color over other, more important, colors, since colors with a very high representation (e.g., background) also increased their neighbor’s histogram value.
4. Dithering simulation on patches — Seeing as our target is to use this palette for dithering, we could define the dithering error as our target function for the palette selection. The problem here is that we don’t want to dither the entire image for all possible color combinations, this would be very inefficient. Instead, we could randomly select a few small patches, dither them, calculate the dithering error vs. the original patches, and choose the palette which resulted in the overall lowest average error. This makes the search fairly quick although it’s brute-force.
   4.1 RGBCMYKW — Use the 8 “corner” colors (red, green, blue, cyan, magenta, yellow, black, white) as our color dictionary, resulting in (8 choose k) color combinations.
   4.2 Color dictionary — Use the representative color dictionary we defined for the histogram method. This has much more color combination possibilities (24 choose k), making it much slower in practice, but much more accurate.

Finally, the method I arrived at was to take the “best of all worlds”:

1. Define a representative color dictionary.
2. Resize the image to be max 512 × 512, for efficiency.
3. Calculate 10 most common colors in the smoothed histogram (very quick), reducing the color dictionary size for the next step.
4. Simulate dithering error on small patches for all color combinations on the reduced color dictionary, and take the best one (much quicker than checking all combinations from the original dictionary).

** In all steps, we fix black and white to the palette, since these provide the main details in the image.

Future Work

I think this just about wraps up my work on this project for now, but here are a few directions I would love to explore in the future.

• Better thread combination method — The two proposed methods (interweave and combine) work pretty fine, but I do believe that better results can be achieved here. The important = last approach might also be suboptimal.
• Deep Learning NN-based algorithm — Having a lot of background in the field of Deep Learning, as this is what I do in my day-job, I would really like to formalize the problem and solution as a neural network learning/optimization problem and give it a go sometime.
• Better Robustness — The aim of this project was for the algorithm to work automatically on any image. This was only partially achieved as, from my experience, the algorithm works better on single or double color palette images, and finds it harder to achieve good results on full color images. This leads me to…
• Get a deeper understanding on color blending — The way we simulate the multicolor String-Art makes assumptions on color blending which might miss how this actually works in real life. In my simulation, I assume natural RGB-space blending, but in real life occlusions are to be considered, and color blending is probably more subtle (or at least modelled in a different color space). Using a better, more accurate, understanding of the physical model could open the door to working with more diverse, in-the-wild images.
• Actually try to physically create one of the images, and see how it turns out in real life compared to the simulation results.

I believe that this concludes the deep-dive into the process of developing my String-Art project. Although this has been a fairly long and thorough post, there are still some aspects of the project that I haven’t covered, such as how we turn this into a PDF with instructions for physically making the String-Art, how we convert a non-continuous list of lines to a continuous one, how we initialize the canvas, and some other minor improvements I made in the algorithm.

Once again, feel free to try the Colab playground, and take a look at the complete code in GitHub.

Special thanks to Shira Bar On for carefully reading initial drafts of this post and giving kind and thoughtful comments, and for being the first one aside of me to try out the algorithm on her own image.

References

• A New Way to Knit (2016), Petros Vrellis — The original String-Art project, which came up with this wonderful and creative idea, and inspired the work for everyone playing around with this problem.
• The Mathematics of StringArt, Virtually Passed — A fun and well-described youtube video, which was the first interaction I got with this line of work and inspired me to try it myself.
• Computational String Art, Callum Mcdougal — An excellent blogpost I found while working on the project, which gave me some very clever and innovative ideas for the multicolor part, as well as most of the example images used in this post.
• String Art: Towards Computational Fabrication of String Images, Birsak et. al. — The best (and almost only) academic article I found related to the String-Art problem.

String Art is a decorative craft where threads are stretched and woven across a set of fixed points on the perimeter of a canvas, gradually building up intricate patterns and images. What might appear at first as a purely artistic pursuit is deeply connected to mathematics: each line is chosen with precision, and together they approximate shapes, textures, and even photorealistic portraits. This interplay between art and algorithm was beautifully demonstrated in A New Way to Knit (2016) by Petros Vrellis, whose pioneering work showed how a simple thread, looped thousands of times, can reconstruct an image with both elegance and surprising fidelity.

I took on myself a weekend project to explore this line of work, and try to create my own String Art algorithm. My vision was to make the algorithm as robust and automatic as possible, and although I can’t say this was fully achieved, I did learn a lot along the way, and there are still plenty more interesting ideas to implement towards this goal.

In this post I will try to deep dive into the full details of the project development process and thought process, including failed ideas, efficiency considerations, and carefully deriving the mathematical formulas required to solve this problem.

Setup and Simulation Model

Our first course of action is to model the real-world String Art problem as a computer simulation. Doing this correctly is of vast importance, since the entire optimization process and rendering process are based on this.

Single line simulation

Each line may be represented by a pair of nails on the canvas perimeter, our main challenge is how we simulate a line given this nail-pair. My first attempt was to explicitly model a line equation and thread profile, for example:

Where d(x,y;l) is the distance between pixel (x,y) and the line l, and t is the line thickness. This is very accurate and allows versatility in the line representation, but it’s quite slow, as we must perform this calculation for every pixel in the image, and for every nail-pair.

Therefore, I turned to implement the lines with a library function. Specifically I found skimage.draw.line_aa to be the fastest implementation that supports antialiasing lines, which is important since the real-world strings aren’t of constant intensity. This implementation also has the benefit of returning the image pixels which are included in the line, which will be important for efficient error calculation, since it will allow us to calculate the effect only on the relevant pixels.

Canvas simulation

At first glance, it might seem as though using the highest canvas resolution is the best choice, but in practice using a smaller image size (around 600×600–900×900) is better. This has two main advantages:

1. Line simulation time — The less pixels there are to calculate, the less time it takes.
2. Color blending — Using a low resolution means that a string takes less than a pixel (accurately, a string’s intensity through a pixel will be: I = string width [mm] ⋅ canvas resolution [pixels] / canvas size [mm]). We haven’t gotten to the colored version of the work, but having I << 1 will come in handy when simulating color blending of different color strings passing through the same pixel, which closely approximates how the human eye perceives colors.

However, for the final rendering we will use a bigger resolution, to simulate the real-world appearance of opaque overlapping strings, which don’t blend when looking up close. Using the same formula as above, we’ll set the canvas resolution so that the string intensity will turn out as 1 pixel.

B&W Algorithms

Solving the black-and-white case is the core challenge. Multicolor optimization can either be reduced to, or built upon, a B&W base. I examined several approaches for this algorithm.

A note on preprocessing:
Since the strings are black and the canvas is white, the first thing we do
for each image is to negate it, making it's values 1 for black and 0 for
white. Now the optimization process will work by adding blacks to recreate
the image.

Naive greedy optimizer

Although I called it “naive” due to it being the first method which comes to mind, it actually works surprisingly well! The greedy method works by minimizing the error for the current step only, and continuing from there. For our problem, this means that for each step we want to find the best line to add, i.e. the one which improves (minimizes) the error by the biggest factor. Putting this in mathematical terms, let x be the current String-Art result, y be the original image, and l be an image representing the line being checked, we want:

To make calculations a bit more efficient, we may subtract the previous error, which doesn’t effect the minimization because it doesn’t depend on l:

This allows us to efficiently calculate the error improvement only along the nonzero pixels of the line l.

Linear Optimizer

I love rigorously formulating problems as optimization problems. I find it to be one of the most elegant ways to apply the full power of mathematics, and once we succeed in doing so, a vast range of optimization algorithms are suddenly added to our toolbox. So naturally, this is what I wanted to do for our String-Art problem. The go-to approach would be a linear model. It’s important to note that modelling the problem as a linear equation is an approximation (since in real world overlapping strings don’t add up, but just hide eachother), but it’s an approximation that works and helps as a relaxation of the problem to a solvable one.

Where we have:

• b (hw × 1) - The flattened image.
• x (n × 1) - A binary vector representing which lines (from all possible nail-pairs) are added to the String-Art solution.
• A (hw × n) - The transformation matrix, which translates each line to it’s image representation, and sums them to the result image.

We pre-calculate A by using the canvas simulation for each possible nail pair, flattening the result, and stacking them as columns in the matrix.

A note about efficiency

The matrix A is a very big one, and therefore consumes a lot of memory, and calculations involving it are time-consuming. However, we may notice that most of it’s values are zeros (only the pixels related to the specific line in each column are nonzero), and choose to represent it as a sparse matrix (e.g., using scipy.sparse) , vastly improving both time and memory efficiency.

Now that we have this representation of the problem as a linear equation, we may plug in various linear regressors. The problem here, is that the solution isn’t restricted to being binary (and not even restricted to being positive!). We may approximate the binary solution by setting some threshold, above which the values of x will become 1, and under which they will become 0.

Unsurprisingly, although the optimizer solution was near-perfect, the approximation is far from good, since the binarization process causes a divergence too big from the original non-binary solution.

So using Least-Squares optimization fails, but can this formulation help us develop something better, with just a little bit of hard work?

Binary Linear optimizer

Let’s try to combine the success of the greedy approach with the formulation of the linear model. What we want is a per-step update formula, derived from the minimization problem from equation (2).

Where we defined:

Such that lₖ₊₁ is the next line number added to the solution, δₗ (n × 1) is a one-hot vector with 1 in the index l, and A⁎ₗ (hw × 1) is the l-th column of A. And so, we arrive at a straight-forward update rule:

Put in words, in each step we calculate equation (4) for all lines, find the best one, and update the residual error rₖ after adding this line via equation (5). If we implement these equations using sparse matrices and vectorized calculations, this process becomes extremely fast!

The runtime improvement is also substantial. Compared on a 300 × 420 image:

Algorithm Improvements

There are a few natural improvements to add to this algorithm, making it work better and faster.

1. Continuous lines — All of the above algorithms could output any sequence of nail-pairs, in any order. To make the physical weaving process easier, we’d like for the algorithm to work with a single long thread, so we should demand that each line starts from the target nail of the previous line. This is done by limiting equation (4) to check only such valid lines. One way to do it is to set eₖ₊₁(l)=∞ for non-valid lines.
2. Importance weights — In some images, where there is much detail in a specific region, we would like the algorithm to emphasize on these regions to capture those details. This may be done by adding a weight map W (hw × 1) which gives higher weights to these regions. All it requires is a very simple manipulation (try developing the update formulas again yourself): Aᵥᵥ=A⊙W, where ⊙ means element-wise multiplication of each column A of with W.
3. Valid nails subset — We may make the algorithm even faster by limiting the number of nails we allow in each step. First, we don’t want a nail to connect to nails which are too close to it anyways, since the result will be perceptually insignificant. Second, we limit it even further by selecting a smaller random subset of nails in each step. This hardly affects the output, but significantly improves efficiency.

That wraps up the B&W side of the project, laying the groundwork for everything. The real challenge, however, lies in extending these ideas to multicolor images. The next post will explore exactly how we can weave colored strings into the algorithm: Algorithmic String Art — Multicolor.

Feel free to try the Colab playground, and take a look at the complete code in GitHub.