The Mathematics of the Mosaic

Two problems

The first problem is the grid: how to cut a surface into pieces that fit together without gaps and still follow the form. The second is the match: given the pieces available, which one goes into which cell. A third, smaller problem sits between them: what to do when no piece matches the tone exactly. In the four layers of a mosaic, the first and the third belong to the constructing mechanism, and the second joins the constructing mechanism to the tesserae.¹

None of this replaces the eye. It makes the decisions explicit, so that they can be changed one at a time, which is how we work.

Tessellation: covering a surface without gaps

A tessellation is a covering of a surface by shapes that leave no gaps and do not overlap. The word comes from the same Latin family as tessera, the small cube of the mosaicist.

Only three regular polygons tile the plane on their own: the equilateral triangle, the square and the regular hexagon. Every other tiling combines shapes, bends them or gives up regularity. The geometric traditions of the Islamic world and the Japanese kumiko lattice build rich patterns from a few rules of construction; the irregular cells of a leaf or a dry-stone wall follow no fixed shape at all. The nine grids on The Four Layers of a Mosaic range across these families, from arabesque and kumiko to circle packing and Voronoi cells.

The idea that the world itself is built from small shapes is old. In Plato’s Timaeus, the four elements are made of regular solids, and the faces of those solids are made of two kinds of right triangle: the half of an equilateral triangle, and the half of a square.² It is the first geometry of tesserae, applied to the cosmos.

In 1619 Johannes Kepler, in Harmonices Mundi, made one of the first systematic studies of how regular polygons fit together around a point, and described the tilings that combine more than one kind of polygon, such as octagons with squares.³ Later tilings went further. In 1704 Sébastien Truchet studied square tiles divided along a diagonal into two colours, and the patterns they make when they are turned by a rule; the variant with quarter-circle arcs, drawn in the figure below, was introduced by Cyril Stanley Smith in 1987.^{4, 5} In 2007 Peter Lu and Paul Steinhardt showed that the girih patterns of medieval Islamic architecture were built from a small set of decorated tiles, and that some of them come close to quasi-crystalline order.⁶ Roger Penrose’s tiling of 1974 covers the plane without ever repeating.⁷ Short definitions of each are in the Mosaic Glossary.

Wassily Kandinsky began his Bauhaus book Point and Line to Plane with the point, the smallest element of form, and built a whole grammar of the picture from it.⁸ A tessera is a point that has been given a size, a shape and a material.

A mosaicist’s grid has one demand that a mathematician’s tiling does not: it must follow the image. The rows of a Roman floor bend around a face, and that flow, the andamento, is what the next section writes down.

The grid, written down

The first mosaicists solved a geometric problem by eye: how to divide a surface into pieces of similar size that still follow the form. Mathematics has a name for one of the most useful answers, the Voronoi diagram, named after Georgy Voronoi, who defined it in general form in 1908; Lejeune Dirichlet had used the same construction in 1850.^{9, 10} Scatter some points, the seeds, over a surface Ω. Each seed p_i claims every place x that is closer to it than to any other seed:

The cells are irregular, like the stones of a dry wall or the cells of a leaf. Now move every seed to the centre of mass of its own cell, and repeat. This is Lloyd’s algorithm, which Stuart Lloyd wrote down at Bell Labs in 1957 and published in 1982,¹¹ and it ends in a centroidal Voronoi tessellation: cells of nearly equal size that still fit together without a gap.¹²

The density ρ is where this becomes a mosaicist’s tool. Where ρ is high, the cells grow small; where it is low, they grow large. Give ρ the detail of a face and the pieces crowd around the eyes and the mouth, the way a mosaicist uses small tesserae for detail and large ones for the background. Alejo Hausner used centroidal Voronoi diagrams in 2001 to simulate decorative mosaics whose tiles follow the edges of the image: the andamento of the ancient floors, computed.¹³

Variable size: the quadtree

Lloyd’s algorithm makes cells small where a density is high. A simpler structure does the same with squares. A quadtree starts from one square and splits it into four whenever it contains too much detail, then splits each of those again, as many times as needed. The name comes from Raphael Finkel and Jon Bentley, who described a quadtree for searching data in 1974; the form that divides an image into equal quarters, the region quadtree, is surveyed by Hanan Samet.^{14, 15} The result is a grid of large squares where the image is quiet and small squares where it is busy.

The rule that decides when to split is where the image enters the mathematics. It can be the variation of tone inside a cell, the presence of edges, or an importance map that marks a face, an eye, a logo. In the portrait of Mohamed Salah on Why a Mosaic Works, the tiles are smallest where the face needs drawing and grow, and scatter, towards the edges.

The matching problem, written down

Every photographic mosaic has to answer one question thousands of times: which piece goes where? In 2021, Hongbo Zhang and his colleagues wrote it down as an assignment problem.¹⁶

Read it like this. The target image is cut into M blocks, and there are N candidate tiles. D_ij is the distance between block i and tile j, here the Euclidean distance between their average colours. X_ij is 1 if tile j is placed in block i, and 0 if not. The two constraints make the assignment one to one: every block receives exactly one tile, and no tile is placed more than once; the authors treat it as a perfect matching in a bipartite graph. T, the sum of the distances of the chosen pairs divided by the area of the finished mosaic (w_pi × h_pi), is the error to be made as small as possible. Instead of choosing the best tile for each block one at a time, the method chooses for the whole picture at once, with the Hungarian algorithm.^{16, 17}

Written this way, the matching rule shows what it really is: a decision about what to compare (D) and a decision about how to choose (X). Change either, and you get a different mosaic, as the nine matching rules on The Four Layers of a Mosaic show.

Measuring colour

Every matching rule needs a distance: a number that says how far apart two colours, or two cells, are. The obvious choice, the difference between red, green and blue values on a screen, is a poor one, because equal steps in those numbers are not equal steps for the eye. In 1976 the International Commission on Illumination defined the CIELAB colour space, built so that distances in it come closer to the differences people see. L* is lightness, a* runs from green to red, b* from blue to yellow, and the difference between two colours is the straight-line distance between them:¹⁸

Later formulas refine it, but the principle stays: a mosaic should be matched in a space that resembles seeing, not in the space of the screen.

Nine ways to compare

Average colour is only the first of many things a matching rule can compare. The nine matching rules on The Four Layers of a Mosaic correspond to different answers to the question what is similar?

• Average colour and brightness. One value per cell. Fast, and blind to everything inside the cell.
• The layout of colour and tone. Each cell and each tile divided into smaller parts and compared part by part, so that a tile with a dark lower half goes where the image is dark below. This is the logic of the photographic mosaics of the 1990s.¹⁹
• The distribution of colours. The full range of colours in a cell compared with the range in a tile, for example with a sliced Wasserstein distance. A Wasserstein distance measures how much colour would have to be moved to turn one distribution into the other; the sliced version estimates it quickly by comparing many one-dimensional projections of the colours.
• Edges and structure. Where the lines run inside a cell. Measures of structural similarity, such as the one published by Zhou Wang and his colleagues in 2004, compare local luminance, contrast and structure rather than single values.²⁰
• Features learned by a vision model. A neural network turns each cell and each tile into a list of numbers that describes what it contains, and similarity is measured between those lists.
• Dithering. Not a comparison of one cell at a time, but a rule that carries the error of each choice on to the next, as the next section describes.

Tone, written down: dithering

When no tile matches the tone of a cell exactly, the difference does not have to be lost. Error diffusion, published by Robert Floyd and Louis Steinberg in 1976, passes it on: the error left at one place is shared among the neighbours that have not yet been decided, so that the tones balance out over a small area.²¹ In their scheme, seven sixteenths of the error go to the next place on the right, and three, five and one sixteenths to the three places below.

A variant named after Bill Atkinson, who wrote the graphics software of the first Macintosh, passes on only three quarters of the error, in eighths, to six neighbours. The picture gains contrast and loses some smoothness. The last cell of the nine matching rules on The Four Layers of a Mosaic uses it: the same logic, applied to tiles instead of black and white dots.

Importance: where the small pieces go

The density ρ in Lloyd’s algorithm asks a question that mathematics cannot answer by itself: what is important in this image? Research in visual attention offers one answer. In 1998 Laurent Itti, Christof Koch and Ernst Niebur described a model that computes, from colour, intensity and orientation, a map of the places in an image that draw the eye.²² A map of that kind can become ρ, and then the cells grow small where the eye will go and large where it will not.

We make these maps with Hipparchus, our own mapping application, and then edit each one by hand into the version the mosaic needs, because the places that matter in a commission are not always the places that are salient. Why a variable size of piece works on the viewer is the subject of Why a Mosaic Works.

More is different

In 1972 the physicist Philip Anderson published an essay with a short title, “More Is Different”. At each level of complexity, he argued, new properties appear that cannot be read off the level below: the whole is not just the parts, added up.²³ A mosaic is a small, visible case of this. No equation in this page contains a face. The face appears only when thousands of pieces, each chosen by a rule, stand together, and the meaning of the whole then returns to each piece, as the semantic layer on The Four Layers of a Mosaic describes.

What the mathematics does not decide

The equations choose the best answer to the question they are given. They do not choose the question. What D compares, what ρ marks as important and which library of pieces the matching draws on are decisions about meaning, and they belong to the fourth layer of the mosaic, the semantic layer.¹ Mathematics turns the constructing mechanism into something that can be written down and tested. The reason for building it is still ours.

Questions

What is a tessellation?

A covering of a surface by shapes that leave no gaps and do not overlap. A mosaic approximates a tessellation with material pieces; its joints are the small gaps that pure geometry does not have. Only three regular polygons tile the plane alone: the triangle, the square and the hexagon.

What is a Voronoi diagram?

A division of a surface into cells around a set of points, the seeds: each cell contains every place that is closer to its seed than to any other. It is named after Georgy Voronoi, who defined it in general form in 1908.

What is Lloyd's algorithm?

A method that moves every seed to the centre of mass of its Voronoi cell and repeats. It ends in a centroidal Voronoi tessellation, with cells of nearly equal size, or of sizes controlled by a density function.

How does a computer decide which tile goes where in a mosaic?

It measures a distance between each cell of the target image and each candidate tile, for example the difference of their average colours, and then chooses. It can choose cell by cell, or for the whole picture at once as an assignment problem, solved with the Hungarian algorithm.

What is a quadtree?

A way of dividing a square into four, and each part again into four, only where more detail is needed. In a mosaic it gives small pieces where the image is busy and large pieces where it is quiet. The name comes from Raphael Finkel and Jon Bentley (1974); the region quadtree used for images is surveyed by Hanan Samet (1984).

How is colour difference measured in a mosaic?

Usually in a perceptual colour space such as CIELAB, where the distance between two colours comes closer to the difference people see than distances between red, green and blue screen values do.

What is dithering?

A way of keeping the tone of an image when the available tones are few: the error at one place is passed to its neighbours. Floyd and Steinberg’s error diffusion (1976) and the variant named after Bill Atkinson are two widely used schemes.

Further reading

• What Is a Mosaic?Meaning, materials, techniques, types and history: the answer, from pebbles to algorithms.
• The Four Layers of a MosaicOne portrait, twenty-seven mosaics: the grid, the tiles and the matching rule, changed one at a time.
• Why a Mosaic WorksPerception, Gestalt and distance: why the eye finds the figure in the fragments.
• Mosaic GlossaryThe words of the mosaic, from tessera and andamento to matching rule.
• The Tradition We Work InThe history of the mosaic, from the clay cones of Uruk to Bell Labs.
• Research, Science and TechnologyMatching, importance, Gestalt and geometry: the knowledge behind our instruments.
• Algorithmic MosaicWhat an algorithmic mosaic is, and how we make one.
• ApplicationsWhere mosaics work today: campaigns, editorial, architecture, corporate art and gifts.
• Photographic Mosaics: How the Algorithms DevelopedSixty years of mosaic algorithms, from Bell Labs to diffusion models.
• Mosaic StylesThe styles of our digital work, from classic grids to maps and stained glass.

References

1. Tsevis Studio, The Tradition We Work In, sections I, III, IV and XIII. tsevis.com
2. Plato, Timaeus, 53c–56c.
3. Johannes Kepler, Harmonices Mundi (Linz, 1619), book II.
4. Sébastien Truchet, “Mémoire sur les combinaisons,” Mémoires de l’Académie Royale des Sciences (1704): 363–372.
5. Cyril Stanley Smith, with a translation of Truchet’s text by Pauline Boucher, “The Tiling Patterns of Sebastien Truchet and the Topology of Structural Hierarchy,” Leonardo 20, no. 4 (1987): 373–385. doi:10.2307/1578535
6. Peter J. Lu and Paul J. Steinhardt, “Decagonal and Quasi-Crystalline Tilings in Medieval Islamic Architecture,” Science 315, no. 5815 (2007): 1106–1110. doi:10.1126/science.1135491
7. Roger Penrose, “The Role of Aesthetics in Pure and Applied Mathematical Research,” Bulletin of the Institute of Mathematics and Its Applications 10 (1974): 266ff.
8. Wassily Kandinsky, Punkt und Linie zu Fläche (Munich: Albert Langen, 1926), Bauhausbücher 9.
9. Georges Voronoi, “Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire,” Journal für die reine und angewandte Mathematik 134 (1908): 198–287.
10. G. Lejeune Dirichlet, “Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen,” Journal für die reine und angewandte Mathematik 40 (1850): 209–227.
11. Stuart P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory 28, no. 2 (1982): 129–137. doi:10.1109/TIT.1982.1056489
12. Qiang Du, Vance Faber and Max Gunzburger, “Centroidal Voronoi Tessellations: Applications and Algorithms,” SIAM Review 41, no. 4 (1999): 637–676. doi:10.1137/S0036144599352836
13. Alejo Hausner, “Simulating Decorative Mosaics,” Proceedings of SIGGRAPH 2001: 573–580. doi:10.1145/383259.383327
14. Raphael A. Finkel and Jon L. Bentley, “Quad trees: a data structure for retrieval on composite keys,” Acta Informatica 4, no. 1 (1974): 1–9. doi:10.1007/BF00288933
15. Hanan Samet, “The Quadtree and Related Hierarchical Data Structures,” ACM Computing Surveys 16, no. 2 (1984): 187–260. doi:10.1145/356924.356930
16. Hongbo Zhang, Xin Gao, Jixiang Du, Qing Lei and Lijie Yang, “Tile selection method based on error minimization for photomosaic image creation,” Frontiers of Computer Science 15, no. 3 (2021): 153702. doi:10.1007/s11704-020-9242-6
17. Harold W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly 2 (1955): 83–97. doi:10.1002/nav.3800020109
18. Commission Internationale de l’Éclairage, Colorimetry, 4th ed., CIE 015:2018 (Vienna: CIE, 2018), on the CIE 1976 L*a*b* colour space.
19. Robert S. Silvers, Photomosaics: Putting Pictures in Their Place, S.M. thesis, Massachusetts Institute of Technology, Program in Media Arts and Sciences, 1996. hdl.handle.net
20. Zhou Wang, Alan C. Bovik, Hamid R. Sheikh and Eero P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Transactions on Image Processing 13, no. 4 (2004): 600–612. doi:10.1109/TIP.2003.819861
21. Robert W. Floyd and Louis Steinberg, “An adaptive algorithm for spatial greyscale,” Proceedings of the Society for Information Display 17, no. 2 (1976): 75–77.
22. Laurent Itti, Christof Koch and Ernst Niebur, “A model of saliency-based visual attention for rapid scene analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence 20, no. 11 (1998): 1254–1259. doi:10.1109/34.730558
23. Philip W. Anderson, “More Is Different,” Science 177, no. 4047 (1972): 393–396. doi:10.1126/science.177.4047.393

About the author

Charis Tsevis is a Greek visual designer and computational artist educated in Athens and Milan. A designer since the late 1980s, he has worked with mosaics for more than three decades and builds his own tools for them. He has taught design thinking, colour theory and Gestalt psychology at art colleges since 1996. With Vira Konstanta he runs Tsevis Studio. About the studio.

Version and how to cite