Optimal Transport and Stippling Art: Turning Images into Particle Paintings with Algorithms

When Mathematics Meets a Five-Century-Old Art Technique

Stippling is nothing new. As early as the beginning of the 16th century, this engraving technique — which uses dense dots to represent light, shadow, and depth — had already emerged. Artists relied on experience and intuition to painstakingly place dots one by one, producing stunning images. In fact, stippling reached its craft zenith during the era of copperplate and steel engraving. The 18th-century Italian engraver Giulio Campagnola is considered one of the early masters of this technique, and by the 19th century, stippling had become a core craft in anti-counterfeiting engraving for currency, stamps, and securities — because dense, precisely arranged dot patterns are extremely difficult to replicate. This relentless pursuit of "precise dot placement" foreshadowed its deep connection with modern computational science. However, viewed through the lens of mathematics and computer science, this ancient art conceals an extremely challenging problem: How do you optimally place a set of discrete points so they accurately approximate the distribution of a target image?

This seemingly simple question is, in fact, an excellent application scenario for Optimal Transport theory. Recently, a developer shared on Reddit an experiment in stippling generation based on optimal transport principles, transforming ordinary images into artworks composed of "optimally placed particles" using 20,000 dots — sparking widespread interest in the community.

Why Stippling Generation Is a "Hard" Problem

Intuitively, stippling seems like nothing more than "putting dots where they belong." But if you try to describe this precisely in mathematical language, you quickly discover that the complexity far exceeds expectations.

The Dilemma of Naive Approaches

The goal is to make the spatial distribution of dots match the grayscale distribution of the image — dense dots in dark areas, sparse dots in bright areas. If you directly model and optimize this objective, you'll quickly find yourself in a computationally intractable situation. This intractability stems from the combinatorial explosion inherent in the problem: when the number of dots reaches tens of thousands, each dot's optimal position is coupled with the positions of all other dots, forming a high-dimensional, non-convex optimization problem. Traditional approaches like Lloyd's relaxation algorithm (centroid iteration based on Voronoi diagrams) can produce relatively uniform distributions, but converge slowly and easily get trapped in local optima, struggling to balance density fitting with visual quality. The original poster referenced a Wolfram blog post (by Silvia-hao) that provides a classic introduction to computational stippling, discussing in detail whether machines can match or even surpass human artists at this task.

The crux of the problem is this: dots cannot overlap or cluster, yet they need to maintain a kind of "ordered disorder" — random yet uniform. This ideal distribution state is precisely the Blue Noise property that has been a long-standing research topic in computer graphics.

Blue Noise: The Key to Uniform Yet Irregular Distribution

Blue noise refers to a noise distribution where energy is concentrated at high frequencies and low-frequency components are absent. When applied to dot placement, this means dots maintain relatively uniform spacing without forming regular grid patterns — avoiding both the clumps and voids of random sampling while preserving a natural visual texture. This is exactly the ideal distribution that high-quality stippling requires.

Notably, the concept of blue noise was first systematically introduced by Robert Ulichney in the 1980s during his research on dithering algorithms, and it has since become a cornerstone technology in rendering. In real-time graphics rendering, blue noise is widely used for Monte Carlo sampling, anti-aliasing, and ambient occlusion calculations — because the human eye is far less sensitive to high-frequency noise than low-frequency noise, so images sampled with blue noise distribution appear "cleaner" even at low sampling rates. Interestingly, many structures in nature, such as the arrangement of photoreceptor cells on the retina and the pigment distribution in bird feathers, exhibit blue noise-like characteristics, which may explain why this distribution feels particularly natural and comfortable to the human eye.

The Gaussian Blue Noise Algorithm: The Core Solution for Stippling Generation

At the heart of this experiment is the Gaussian Blue Noise algorithm proposed by Ahmed, Ren, and Wonka (arXiv: 2206.07798).

The Basic Idea

This method treats each dot as a Gaussian kernel and optimizes dot positions so that the density field formed by superimposing these Gaussian kernels approximates the target image's density distribution as closely as possible, while maintaining blue noise spectral properties. This approach elegantly unifies the two seemingly contradictory objectives — "fitting the target distribution" and "maintaining inter-point uniformity" — within a single optimization framework.

Gaussian kernels are an ideal choice because of their excellent mathematical properties: they maintain Gaussian form in both spatial and frequency domains, with continuous and differentiable derivatives everywhere, enabling efficient optimization with gradient descent and other modern optimization methods. "Softening" discrete points into a continuous Gaussian density field essentially transforms a discrete combinatorial problem into a continuously differentiable optimization problem — a core idea behind many modern machine learning techniques. When two points get too close, their Gaussian kernels produce a strong overlapping "repulsion" signal, driving the optimization process to push them apart. This naturally gives rise to the uniform spacing characteristic of blue noise, without explicitly constraining inter-point distances.

Using this algorithm, the author demonstrated 4 stippling examples generated with 20,000 dots. Compared to traditional hand-drawn stippling or simple random sampling, this optimal transport-based method can accurately reproduce the tonal range and details of images while maintaining visual uniformity.

An Intuitive Understanding of Optimal Transport Theory

From a broader perspective, the process of matching a point set distribution to a target image is essentially finding an optimal "mass transport" plan — how to move points from an initial distribution to a target distribution at minimum cost. This is exactly the core problem studied by optimal transport theory, and the deeper meaning behind the title "Optimal Transport is art."

Optimal transport theory has a long and fascinating history. It was first proposed by French mathematician Gaspard Monge in 1781 while studying how to most economically move earth (the "excavation and fill problem"), which is why its optimal solution is also known as the "Monge problem." Nearly two centuries later, Soviet mathematician Leonid Kantorovich reformulated and generalized it in the 1940s — work that later earned him the Nobel Prize in Economics. In the 21st century, French mathematician Cédric Villani won the 2010 Fields Medal for his deep research in optimal transport, bringing the theory back into the spotlight of the mathematical community. Today, optimal transport has far transcended its mathematical origins, finding wide applications in generative models in machine learning (such as the Earth Mover's Distance used in Wasserstein GANs), image style transfer, domain adaptation, and even single-cell biology data analysis, becoming a universal language for connecting probability distributions.

Open-Source Implementation: A Stippling Tool for Everyone

Commendably, the author didn't stop at showcasing results but packaged the entire workflow into a ready-to-use Python library, enabling anyone to experiment with stippling on their own images.

Two Quick Ways to Get Started

• Local installation: Install the Python package via pip and directly apply blue noise stippling to images in your code (code snippets were provided in the original post's comment section).
• Online demo: The author also provides a Google Colab notebook — no local environment setup needed. Just upload an image and generate stippling results right in your browser, dramatically lowering the barrier to entry.

This combination of "research ideas + open-source tools + one-click demo" is exactly the kind of sharing format that today's tech community loves most. It not only makes abstract mathematical algorithms accessible and tangible but also provides artists and designers with new expressive tools. In fact, Google Colab, as a cloud-based Jupyter environment offering free GPU compute, has dramatically lowered the barrier to experiencing cutting-edge algorithms in recent years. It allows researchers to reproduce and share results without setting up complex local environments, and has become the de facto standard for "click and try" demos in academic papers and open-source projects.

Conclusion: When Algorithms Open New Possibilities for Art

The significance of this experiment lies not only in demonstrating a beautiful image processing effect, but more importantly in revealing the deep connections between mathematics, algorithms, and art. From the hand-carved dots of 16th-century engravers to today's algorithmic generation based on optimal transport and blue noise, humanity has always been asking the same question: how to arrange discrete points in the most elegant way to approximate continuous beauty.

At the end of the post, the author also extended an invitation, asking for "cool images suitable for stippling rendering" — a reminder that the value of tools ultimately depends on human imagination. As algorithms grow ever more powerful, perhaps what's truly scarce are the images and inspirations worthy of being reinterpreted through stippling. For readers interested in computer graphics, generative art, or optimal transport, why not open that Colab link yourself and see what kind of particle constellation your own photos might become.