How to generate Roman style mosaics with Python

Hands-on Tutorials

Make your own mosaics with the provided code and understand the fundamental principle behind it

Images by author based on following input images: scikit-image test image "coffee", Vermeer’s Girl with a Pearl Earring and Python logo

Ancient mosaics are assembled from small pieces of hard material like marble, glass or limestone. This choice of material results in extremely long lasting artworks which give us insight into the way of life thousands of years ago. But mosaics represent modern concepts as well. To begin with, they are sustainable due to their natural and reusable building blocks. And they possess a high level of abstraction which gives them an interesting look. This effect arises automatically because the number of elements in a Mosaic is strictly limited. Despite this limitation, objects should be clearly recognizable. This is the challenge in creating a new mosaic and requires rules to be followed when placing the tiles.

Available algorithms

When I searched for tools to generate mosaics out of input images I didn’t find one that convinced me. Therefore I started to experiment with Neural Style Transfer which resulted stunning mosaics, but a closer look revealed a lot of unrealistic tiles. Then I found out that a couple of scientific papers about mosaic calculation exist and became aware of an older one (from 2005) by Di Blasi et al. which produces beautiful mosaics. I decided to adapt the published method and implement it with Python. It turned out to be harder than expected since the task is surprisingly complex. Also, I had to improvise a lot because the final steps of the algorithm are not explained in detail. Now I’d like to share the script with everyone who is interested in the matter. A few relevant lines of code are posted right here and the full code is available on GitHub.

Let’s start

Initially we load a source image:

The image is shown in the figure below. Now we can start to implement the algorithm.

Edge detection

The basic design principle of the most well-known type of mosaics (opus vermiculatum) requires placing chains of tiles along edges of visually important objects. Therefore our first task is to extract these edge features from the source Image. In the paper it is pointed out that traditional edge detection algorithms do not work well and a custom technique had to be developed based on brightness levels. This was written in 2005. Nowadays we can benefit from advances in the field of deep learning. Holistically-nested edge detection (HED) was published one decade after Di Blasi’s work and can be implemented easily using openCV. It turns out that in most cases HED works even better in detecting relevant outlines. You can see this in the comparison below where HED produces clearly less background features, but better retains the cup’s edges.

Source image is test image "coffee" from scikit-image (by Rachel Michetti). Edge detection images by author.

Guidelines

Now we have the edges and could start placing tiles there. But where to go on after that? Let’s prepare instructions for filling the whole image with tiles. Therefore, we construct a complete set of guidelines parallel to the detected edges. To do this, we first have to calculate for each pixel the distance to the closest edge. Luckily, SciPy has the right function for that:

In _imgedges the already detected edges are encoded as "1" and converted to "False" by setting _imgedges==0. You can see the resulting image in the figure below. Here, the brighter a pixel is the farther it is away from an edge.

Now we can use our new knowledge about the edge distances: We move _halftile (i.e. half the size of a tile; chosen by user) away from the edge and draw the guidelines line by line while always leaving exactly the space a chain of tiles will need:

The result is shown below. Eventually, the tiles will be placed centered along those lines. After that, we use the distances matrix again to calculate the gradient for each pixel. We will need this data later for placing the tiles with the correct orientation.

Images by author (based on scikit-image test image "coffee")

In order to make the guidelines useful for the following steps we have to convert them to an ordered list of coordinates. This is not an easy task, but thankfully SciPy is great help here again:

Tile placement

Now we can start to actually place the tiles by drawing polygons along the guidelines. With Shapely there is an awesome python library for creating and manipulating geometric shapes.

The placement of a standard tile **** is accomplished as follows:

create side 1 as line of length 2⋅_halftile; centered at the guideline (dahsed line in sketch below)
rotate side 1 by angle taken from precomputed gradient matrix
move forward on guideline for 2⋅_halftile pixels
create side 2 in the same way as side 1
create a polygon by taking the convex hull of the four corner points (i.e. two end points from both sides)
if the new tile overlaps with tiles of a nearby chain then only keep the difference

If a tile is placed along a curved guideline, its width is chosen smaller so that round objects in the final mosaic look better. As depicted in the drawing above, side 2 is drawn as soon as a critical angle is exceeded. Finally, the last tile of a guideline chain (which is typically a closed line) is fitted into the remaining space and might therefore have a smaller width as well.

All this is done in a loop and needs a considerable amount of lines of code. Just to demonstrate the easy principle behind Shapely let’s draw a single polygon:

In this example line0 is created on the left side and line1 on the right side. Both lines are rotated by the specified angle. Finally the corner points of the two lines are extracted and merged to a convex polygon.

Now let’s go on with the placement loop. In the following picture (left side) you can see the result after the first chain is finished. Also the labeled chains are plotted as colored lines. On the right image all chains are populated with tiles. But we are not done yet because we have a lot of gaps between the tiles.

Tiles into gaps

In order to fill the gaps we use scikit-image, another great Python library. To find the gaps we begin by drawing all existing tiles:

Here, x and y are a polygon’s corner coordinates. "Draw" converts them to the coordinates rr,cc of all pixels which are inside the polygon. You can see the result on the left image below. From there we calculate again the distances to existing tiles. Then, we use this information to define a second set of guidelines inside the gaps (right image).

After placing additional tiles along the new guidelines all necessary polygons are created. One more task is to cut off tiles that stick out of the image borders. Then, let’s have a look at the result. In the following picture you can see that the whole area is covered with tiles:

Image by author (based on scikit-image test image "coffee")

Handling concave tiles

It’s hardly visible without closer inspection, but there is one thing about the tile shapes that is not satisfying yet: there are a lot of concave polygons! A polygon is concave if a line between two corner points can go outside the polygon. It can be formed after placement when its overlap with nearby polygons is removed. Those shapes are not very natural because in reality pieces of stone are typically not concave, but convex. This is why the code offers the option to convert shapes to convex ones. It implements two strategies (see sketch below):

Remove spikes: a spiky part of a polygon is simply removed if the area of the polygon is not changed considerably. After spike removal the area must be smaller than before. Otherwise there is a risk of a new overlap with other tiles.
This is the case on the right sketch. If the marked corner was removed the resulting polygon would be larger than before. Instead, it is separated into two convex polygons.

Conveniently, both strategies can be implemented using shapely routines.

Coloring

Finally all tiles are in place and have a convex shape. Just the color is missing! We just copy it from the input image. The easiest way to do that is pick the color value which would be at the center of the polygon. Since weird pixel colors can be gathered in some cases it is also possible to average the color over all pixels which lie inside a tile. What you get then is shown below on the right side.

One drawback is that the resulting mosaic looks a bit artificial since not all colors occurring in modern photographs can be reproduced with pieces of natural materials. Therefore a collection of colors that can be found in real historic mosaics was collected beforehand. You can choose to change all color values to their closest counterpart from that sources. In the example below (right side) a source mosaic from Ravenna was selected which still contains a lot of colors due to the use of glass pieces.

Finished!

Let’s have a look on a few more generated mosaics.

For example we can try the effect of different tile sizes. In the left image it set to 15px and in the right to 5px. The coarser image needs 1107 tiles and the finer one takes 7069 tiles.