I am one of those people who enjoys everything. And I mean everything. You probably know one of those people, or maybe you are one. The people who try a hobby once, become instantly hooked, and then want to buy all the equipment and become a master of this new skill – well, that’s me. Bread making, calligraphy, skiing, candle making, language learning, tennis, writing, figure skating, piano playing… you get the idea.
This also extends into my academic career; you may have read on my home page that my undergraduate degree was in Theoretical Physics, but now I study Statistics and Operational research (check out this post about why I made the switch). Basically, I love to learn, and I love to discover as much as I can about the things I find interesting; hence my love of research.
One thing that has remained a constant love throughout my life though is art. I love to paint (in water colours, acrylics, dyes and oils – I told you, I enjoy everything), and also draw. I recently read a blog post by my friend Lídia, on the role of Operational Research in music – a truly interesting post that you can find here – and it got me thinking, I wonder if there was a link between Operational Research and art too?
Optimisation
Optimisation is a branch of Operational Research which considers the task of achieving optimal performance subject to certain constraints. Mathematically, optimisation problems deal with maximising or minimising some function with respective to some set; for example, given a set of decision variables x = (x1, x2, x3, …, xn), we want to find the decision variable that maximises or minimises the objective function.
The objective function could be the waiting time for customers in a system, or the profit from the sale of a product.
The subset which represents the allowable choices of decision variables is called the feasible set. Constraints in an optimisation problem work to specify what the feasible set is. For example, if we consider the waiting time for customers in a system, a constraint would be given by the fact the number of customers in a system can never be negative. This is a simple example of a constraint that one would encounter in an optimisation problem, but in reality there are often many constraints, that can be complex and highly dimensional.
So how does this relate to art?
Well, clearly when an artist works, they are subject to some real-world constraints. They are required to work within budgets, meet deadlines, and follow the instructions of the customer in the case of commissions.
But, perhaps more interestingly, some artists subject themselves to constraints voluntarily. A Sunday on La Grande Jatte (1884) is a work by the French artist Georges-Pierre Seurat (see on Wikipedia). Looking at it, the painting depicts Parisians having what looks to be a lovely day at the park. When viewed up close, however, it is possible to see that the painting is made up of many tiny dots of multicoloured paint.
If we think about the creation of this painting as an optimisation problem, we could say that Seurat’s objective was to create the best possible depiction of what he saw, subject to two key constraints: only applying the paint in tiny dots, and keeping his colours separate.
I came across this paper, which discusses applying optimisation algorithms in order to create computer generated artwork. This general idea is considered for three different branches of art: line art, tile-based methods, and freeform arrangement of elements. For this post, we’re going to be considering tile-based methods, or mosaics. See Mathematical Mosaics, American Scientist.
When photographs or other images are represented digitally, we can think of this as a function which maps each pixel location (x, y) to some colour space. This is easy to consider in a mathematical context, for colours can be denoted using an RGB colour model or similar. Once photographs are represented in this form, it is easy for artists to construct a new artistic version of this photograph by replacing each pixel or block of pixels with some object, known as tiles.
The need for optimisation becomes apparent when an artist is choosing from a finite selection of tiles (where tiles could be anything ranging from dominoes, lego pieces, or other photographs). If the artist only has access to a fixed selection of tiles, then the goal is to find the ‘best’ overall arrangement of this set of tiles, in order to produce the most aesthetically pleasing artwork. Mathematically, the most ‘aesthetically pleasing’ artwork may be considered as the artwork which is most similar to the original image.
If we let I be a W x H image, and suppose that we have an inventory of tiles T = {T1, T2, …, Tn}. So how do we quantify how similar an approximation is to the original reference image? In the paper, a distance function d(I(x,y),T) is introduced, where I(x, y) is the colour of the pixel at location (x, y) in the original image, and Tj is the colour of a particular tile. This distance function provides a quantitative method for determining how effectively a given tile approximates a pixel in the source image.
We assume that d(I(x, y),T) is never negative, and smaller values denote better approximations (a distance value of zero would indicate that the tile and the corresponding source pixel are the same colour). If we consider all possible ways in which our inventory of tiles may be arranged on our image (where each tile is used no more than once), that is, all possible mappings, we then seek to find the mapping which minimises the total of the distance functions for every pixel.
In the case that our tiles match up with the dimensions of the pixels exactly, this proves to be a relatively simple task. It is possible to solve this by constructing a complete, weighted bipartite graph, in which each pixel location (x, y) is connected to every tile Tj by an edge of weight d(I(x, y),Tj). The minimum weight matching which uses all pixels can then be computed to give the optimal solution.
This task becomes far more complex in the case that the tiles do not match up one to one with the image pixels, for example, if the artist were to use something like dominoes. However, it is presented in the paper, that the construction of domino art can be naturally reduced to an integer programming problem.
Isn’t it fascinating how optimisation techniques can be used to create impressive artwork? I certainly think so. Some people might think that applying mathematical techniques such as integer programming to create art takes away from the spontaneity and skill that goes into creating a masterpiece, but I actually think it only adds to the awe! What do you think? Let me know in the comments.
Make sure to check out the further reading if you are interested in finding out more!
Further Reading
Operations Research in the Visual Arts – Craig S. Kaplan, Robert Bosch