Glass Mosaics Using Right-Triangle Subdivision

Year: 2018 Authors: Thomas M. Denker

Core claim

Recursive right-triangle subdivision reduces mosaic error while keeping geometry simple and fabrication easier with rectangular tesserae.

Topics

photo mosaic algorithms, recursive subdivision, color quantization, glass tesserae

Domains

computational geometry, error minimization, RGB color space, mosaic art, glass art, photomosaic design

Methods

recursive subdivision, mean square error minimization, bottom-up evaluation, color mapping

Media

Venetian smalti, mosaic glass, digital photo

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Glass Mosaics Using Right-Triangle Subdivision

Thomas M. Denker

Frankfurt, Germany; t-denker@t-denker.de

Abstract

An algorithm is presented that designs a glass mosaic from a photo. The image is tessellated by right triangles such that each triangle is implemented with glass of one color. The arrangement of triangles is determined by a recursive mean square error minimization technique.

Introduction

I am a maker of mosaics. Typically, I derive the design of a mosaic from a photo taken by myself or some other photographer. For the mosaic design my computer replaces the pixels of the photo by tesserae (mosaic stones) of appropriate color. Then I assemble the mosaic from Venetian smalti by hand. Figure 1 shows an example.

Figure 1: Frida Kahlo $(40\times 40cm)$

Artists using this and similar techniques are presented in [2]. While [5] shows the work of a pioneer in the fields of computer arts and photomosaics, [4] presents an impressive example in my home town. More of my work can be seen in [6] and on my web site http://www.t-denker.de.

Objective

The approach presented in this paper tries to overcome the somewhat mechanical appearance of computer designed mosaics. For this purpose the photo is tessellated by right triangles. Each triangle is then implemented with mosaic glass of a single color. Triangles are used to keep the geometry simple. The restriction to right triangles makes the mosaic implementation with rectangular tesserae easier. The approach attempts to reproduce the photo with triangles which are not too small and whose number is not too large.

Denker

The Algorithm

The photo is cut into two or more initial triangles. The easiest way to do this is by splitting the image along one of its diagonals as shown in Figure 2.

Figure 2: Initial triangles

Each triangle or sub-triangle is split into two or four sub-triangles according to one of the six distinct schemes shown in Figure 3.

Figure 3: Splitting schemes

For each possible splitting scheme the algorithm recurses to the sub-triangles and then computes an error as described below. The splitting scheme, which minimizes this error, is eventually applied. The recursion ends when either of two conditions is met: the triangles become ‘too small’ or the approximation is ‘good enough’. These two expressions are clarified below. Triangles that are further split are non-terminal. Triangles that are not further split (the ones which actually implement the mosaic) are terminal triangles. Note, that the algorithm is bottom up. The error of a non-terminal triangle can only be determined after all sub-triangles have been evaluated.

Let’s $s\in S=\{A,B,C,D,E,F\}$ be one of the schemes of Figure 3. Then

Glass Mosaics Using Right-Triangle Subdivision

denotes the set of either two or four similar sub-triangles in which a non-terminal triangle $T$ is split by splitting scheme $s$. The error for $T$ is then defined as the sum of the errors of the sub-triangles

and the splitting scheme $s$ is selected where $E_T$ is minimized.

Let’s denote $p_{ij}$ the RGB-triple presenting the color of the pixel in row $i$ and column $j$ of the photo. If ${\sum }_T$ stands for the summation over all pixels with an upper left corner inside triangle $T$, then $n={\sum }_{T}1$ is the number of pixels inside $T$ and

is the average color of the pixels inside $T$. If all those pixels are replaced by pixels of color $a_T$, then a total quadratic error²

is introduced for $T$ and the per pixel quadratic error will be

When any of the splitting products of a triangle $T$ has a hypotenuse length $c$ with c < c_{min} or when the per pixel quadratic error $e_T$ becomes less than a certain threshold $e_{max}$, the recursion ends and $T$ becomes a terminal triangle.

Results

Figure 4 shows two mosaic designs with different $c_{min}$. The one shown in Figure 4a has 209 terminal triangles, while the one in Figure 4b has 633 triangles. About $4.2\cdot 10^6$ and $70\cdot 10^6$ triangles had to be constructed and analyzed to generate the two designs.

The original photo is black and white. If the color version of this paper is viewed, it can be seen that the mosaic designs are a ‘bit colored’. The above error definition formulas ignore a nasty detail, namely that the glass factory cannot deliver smalti in any computed average color $a_T$. At a certain point, a mapping $D(a_T)$ is applied which maps an arbitrary color to one of the 293 colors available from the Donà glass factory [3]. I manipulate this mapping such that some not-so-grayish colors give a bit more vibrancy to an originally black and white picture.

Alas, the software was not ready with all the necessary bells and whistles, when I had to deliver the portrait (Figure 5) of Simone Veil³ to the French Mosaic Biennale [1]. So I executed it with my standard technique. I promise, however, to present a real mosaic composed from triangles at the Bridges 2018 conference!

²I.e., that a Euclidean metric is applied in the RGB color space.

³Simone Veil, 1927–2017, holocaust survivor, French politician, President of the European Parliament

469

Denker

(a) $c_{min}=0.1\cdot H$

(b) $c_{min}=0.05\cdot H$

Figure 4: Mosaic designs with different $c_{min}$ in relation to mosaic height $H$ Figure 5: Simone Veil (76 × 72 cm)

References

[1] M. Blanchard. “The Mosaic Experience.” Mosaic exhibition, Auray, France, 20 April – 17 May, 2018. [2] M. de Melo. “Pixerae: Mosaic as Research.” Mosaïque Magazine, MM no. 13, 2017, pp. 72-73. [3] S. Donà. http://www.mosaicidonamurano.com (last accessed 30 April 2018). [4] S. Huber. http://www.stephanhuberkunst.de/fotoseite/fra-tresw. (last accessed 30 April 2018). [5] K. Knowlton. http://www.knowltonmosaics.com (last accessed 30 April 2018). [6] J. Weisbrod. “A Mosaic Passover Story II, Symbols of Judaism.” Mosaïque Magazine, MM no. 12, 2016, pp. 48–49.