Extracting Unit Cells from Tilings with Color Symmetries: Case of Counterchange Patterns

Year: 2016 Authors: Venera Adanova; Sibel Tari

Core claim

Spatial connectivity graphs built from thresholded masks and transformed motif centers can recover unit cells and symmetries, including cases with or without color permutations.

Topics

color symmetry, unit cell extraction, tiling symmetry detection, counterchange patterns

Domains

plane symmetry groups, geometric transformations, crystallographic notation, ornament design, pattern analysis, generative tilings

Methods

adaptive recursive thresholding, HSV channel masking, watershed transform, connectivity graph extraction

Media

digital tile images, HSV color channels, iOrnament

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.

Extracting Unit Cells from Tilings with Color Symmetries: Case of Counterchange Patterns

Venera Adanova and Sibel Tari

Dept. of Computer Engineering, Middle East Technical University, 06800 Ankara

adanovenus@gmail.com, stari@metu.edu.tr

Abstract

In this work, we present a novel computer method for obtaining units cells and symmetry operations required to analyze the tiling, without assuming the knowledge of the underlying symmetry group.

Introduction

Repeating a base motif on a plane using four fundamental operations (translation, rotation, reflection, and glide reflection) creates a tile with different symmetries depending on the group of primitive repetition operators. For example, a $p1$ tile is obtained when only translations in two independent directions are used, or a $p6m$ tile is obtained when the motif is reflected and then the resulting motif of mirror symmetry is repeated by $60^{\circ }$ rotations. There are exactly $17$ different ways to tile a plane by repeating a base motif via four primitive geometric operations. This result has been known for several centuries [3]. Two planar tiles are shown in Fig. 1 (a)-(b). These two tiles, respectively, belong to the symmetry groups $p4g$ and $p6m$, two of the $17$ different ways to tile a plane. The classification, however, gets complicated if color permutations are allowed. A tile has color symmetry, if applying certain geometric symmetry operation maps all regions of one color to the regions of another color. A mapping might be either color preserving or color reversing. Note that the color symmetry can occur only when a tile contains motifs of similar shapes. Given an uncolored tile of certain symmetry, there are only finite ways of coloring it using $c$ colors. For example, the remaining two tiles shown on the two rightmost columns of Fig. 1(c-d) exhibit color symmetry. Notice that the first tile of this second group is constructed via $60^{\circ }$ rotations. However, at each turn, the color is also switched, giving the six-fold form of this tile a different character than that in the red/green tile. The group of this tile is $p6/p3$ in Coxeter notation [1] – one of the $46$ counterchange patterns. It, alternatively, can be denoted as $p6[2]$ in the notation of [2]. This example shows the only way of coloring an uncolored tile of $p6$ group using two colors. The symmetry of the second tile of this group is $pgg/pg$. Its symmetry is reduced because one of the glide reflections are color reversing. This example shows one of the two ways of coloring an uncolored tile of $pgg$ group using two colors.

The interpretation of symmetry in counterchange patterns is twofold; one can recognize color changes as a part of symmetry operations (allow color permutations) or consider only the symmetries that the tiles of a single color exhibit. As an example consider the $p6/p3$ tile in Fig. 1(c). Each $60^{\circ }$ turn reverses the color of a motif, while each $120^{\circ }$ turn preserves it. Then, if color permutations are allowed the tile belongs to $p6$ group, otherwise, if color changes are considered as asymmetric operations the tile belongs to $p3$ group

In this work, we present a novel computer method to extract unit cells and fundamental domains of tiles with various color symmetries, both allowing and forbidding color permutations. Instead of locating repetitions via autocorrelation, we form a spatial connectivity graph from which all repetion patterns can be extracted. The nodes of the connectivity graph are robustly obtained by virtue of a spatial transformation that is applied to thresholded tiles. The key virtue of this transformation is that it suppresses the shape details in the motif, highlighting the shape centers that we employ to construct the nodes in the connectivity graph.

Adanova and Tari

Figure 1: Four sample tiles. (a) A tile of $p4g$ group with no color symmetry. (b) A tile of $p6m$ group with no color symmetry. (c) One of the 46 counterchange patterns $p6/p3$ or $p6[2]$ in Coxeter notation; it shows the only way of coloring an uncolored tile of $p6$ group using two colors. Here, dots indicate the centers of six-fold rotations. (d) Shows another counterchange pattern, namely $pgg/pg$ .

Figure 2: A demonstration of the method on a tile of four-fold symmetry. The group is $p4[2{]}_1$ also denoted as $p4/p4$ . (Top row) The input tile, and node centers for each mask. (Middle row) Connection groups extracted from a single mask. (Bottom row) Connection groups extracted by combining the nodes from both masks, i.e., by allowing color permutations.

The Method

Given a tile, the first step is to extract binary masks which reveal the way the colors are permuted. This is done by thresholding the image HSV channels at a number of adaptively selected thresholding levels. The number of binary masks depend on the number of colors in a tile. If an image contains two colors, then one threshold is selected, while for three color images two thresholds are selected, and so on. For thresholding, we resort to an adaptive recursive thresholding scheme to split the tile domain into two sets respectively corresponding to a foreground and background. The scheme we use is available in any image processing tool such as Matlab. The threshold values are obtained using the histogram for each of the HSV channels. Assuming a bi-modal distribution a threshold that splits the set of values to two subsets is determined. For splitting the image into more than two subsets the procedure is applied recursively to produce $2k-1$ thresholds, such that $k$ is the smallest number that satisfy 2k - 1 > t , where $t$ is the number of colors in a tile. Then the top $t$ most effective threshold values are selected. Generally for one of the HSV channels we obtain acceptable set of binary masks (indicating a foreground and a background). Once the binary masks are extracted, a spatial transformation to highlight the motif centers is performed on each mask. This is implemented in two steps. First, an initialization is performed: at each background point, the value is set

to zero whereas at each foreground point, the minimal distance to the nearest background is computed. The peaks of this initial transformation occur at the centers of the foreground motifs. The node centers may be sensitive to errors in the mask extraction process. Therefore, we perform a kind of regularization and obtain a more robust centroid location. Node centers in a tile are detected by applying a watershed transform on a transformed image. The watershed transform detects local maxima.

The next step is an iterative extraction of various connections. In the first iteration, the minimal distance between two node centers is found and all connections with similar distances (2 or 3 pixels of tolerance) are extracted. In the next iteration, the connections of the previous iteration are ignored, and a new minimal distance is computed to extract new connections. Thus, after $n$ iterations, connections of various sizes are obtained. Note that the meaningful connections come with the small size connections (typically $n$=5). Increasing number of iterations leads to the repetition of the same symmetries on a larger scale. Next, these connections are organized into $m$ groups. Recall that in the previous step the connections are considered to have similar sizes even if they differ for 2 or 3 pixels. If that prediction of error was set correctly then $m=n$ (which is generally the case). Otherwise one has to increase or decrease $m$ depending on the classification results obtained. The connections are classified as following. Initially each connection forms a group itself. We then iteratively join different groups based on sizes and orientations. The tolerance for differences in distances among the connections of the same group is set to $1$ pixel initially. Each iteration joins the closest connections in terms of size and orientation. If no connections join in an iteration, then the tolerance is increased by one. The iterations stops when the number of groups reaches $m$. Connections that belong to the same group show similar symmetries of an ornament. As an example see Fig. 2 for the four connection groups obtained for one of the masks of a tile forbidding color permutations ( Fig. 2 middle row) and for the combination of two mask nodes when color permutation is allowed ( Fig. 2 bottom row). For both cases two of the connection groups contain two-point connections indicating two-fold rotations; while the other two connection groups contain four-point connections indicating four-fold rotations (observe that the centers of squares fall on the centers of four-fold rotations). Thus, the highest order of rotation for this tile, in both cases, is four. Connecting the translations of any of the two four-fold rotation centers give a unit cell. Detected symmetries along with extracted unit cells for both cases are shown in Fig. 3.

There are three symmetry groups involving four-fold rotations: $p4$, $p4m$ and $p4g$. The $p4g$ group contains only one four-fold rotation center, while for this particular tile we extracted two different four-fold rotation centers. Then we do not consider $p4g$ group any further. The $p4m$ group requires a mirror reflection along the diagonals of the unit cell. From depicted unit cells, along with the connections incident with it, one observes that none of the points of red square in Fig. 3 lie on the diagonals of the unit cell, neither the diagonal divides the square equally. Then the diagonal does not divide the four-fold rotation center equally so that the mirror reflection occurs. Thus, we conclude that the tile is of $p4$ group.

Observe that the unit cell for the first case (Fig. 3 second column) is twice as big as the unit cell for the combined case (Fig. 3 forth column). This is because in the former case, one needs two lizards of different colors (since we consider them as two different shapes) to recreate the entire tile, while in the latter case only one is enough (since all shape are considered to be similar).

Results

More results on symmetry detection and unit cell extraction are given in Fig. 4. The symmetries inferred from the connection groups, computed as described above, are given for each tile both forbidding and allowing color permutations. The first tile (Fig. 4 first row) is of $p6/p3$ group. If the color changes are not considered to be the part of symmetry operations, then the tile is constructed via $120^{\circ }$ rotations of two different motifs and the symmetry group is $p3$. Otherwise, the tile is constructed via $60^{\circ }$ rotations of a single motif, with color changes, and the symmetry group is $p6$. Similarly, for the second tile (Fig. 4 second row), in the first case it

Adanova and Tari

Figure 3: Symmetries of an ornament inferred from the connection graph. Red and blue squares indicate the unit cell of an ornament; along with the cell, the connections incident with it are also depicted. The demonstration on the right takes color permutations into account; hence, obtains a smaller unit.

Figure 4: 2 sample tiles with color symmetry.

is constructed via $180^{\circ }$ rotations of two different motifs and the symmetry group is $cmm$ . In the second case, the tile is constructed via $90^{\circ }$ rotations of a single motif, with color changes, and the symmetry group is $p4g$ . Note that taking color permutations into account leads to an increase in the number of allowable symmetry operations; hence, causes a decrease in the size of the unit cell. There is no restriction on the number of colors for the algorithm. In other words, the same analyses can be done on tiles with more than two colors. All input tiles are produced by the authors using iOrnament.

References

[1] H. S. M. Coxeter. Coloured symmetry. In M. C. Escher: Art and Science, pages 15-33. North-Holland, 1986. [2] B. Grünbaum and G. C. Shephard. Tilings and Patterns. Freeman, 1987. [3] G. Polya. Über die analogie der kristallsymmetrie in der ebene. Z. Kristallogr., 50:278-282, 1924.