Mathematical Hints for Parameter Selection for AA Patterns

Year: 2011 Authors: Abdalla G. M. Ahmed

Core claim

Continued-fraction structure of α can be used to predict and tune AA Pattern repetition, clustering, and crossbreeding behavior.

Topics

algorithmic art, continued fractions, parameter selection, pattern repetition, quantization artifacts

Domains

affine transformations, Pell equation, number theory, continued fractions, algorithmic art, visual pattern design, generative graphics, visualization

Methods

elementary algebra, continued-fraction analysis, rational approximation, pattern crossbreeding

Media

pixel patterns, Java applet, colored figures

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 2011: Mathematics, Music, Art, Architecture, Culture

Mathematical Hints for Parameter Selection for AA Patterns

Abdalla G. M. Ahmed Email: abdalla_gafar@hotmail.com

Abstract

“AA Patterns” is the collective name of a recently introduced algorithmic art, where a simple affine 2D transformation is employed to generate aesthetic patterns. AA Patterns are controlled by a single real parameter between 1 and 2. This paper presents examples of how mathematical analysis can help in selecting and tuning the pattern parameter in such a way as to attain certain features in the generated pattern.

1 Introduction

“AA Patterns” is the name of a new algorithmic art comprising symmetric pixel patterns generated from a simple affine 2D transformation with one parameter. AA Patterns were first introduced in [2], along with detailed technical analysis and some generation and coloring algorithms. In Section 2 we briefly provide the reader with essential background about these patterns, then we discuss in subsequent sections some ideas for the objective selection of the parameter, and we show how certain structures of real numbers manifest in AA Patterns.

2 AA Patterns Overview

Consider the transformation

which maps integer points $(x,y)$ in a source plane to the corresponding integer points $(X,Y)$ in a target plane, using the floor function to quantize real numbers to integers. There are target points to which no source points map, and the set of all these target points is called an AA Pattern. Any real number $\alpha$ between 1 and 2 is associated with a unique AA Pattern, designated as $AA(\alpha )$.

Figure 1 shows example AA Patterns. Notice how the points that make these patterns tend to group in symmetric clusters. We will elaborate on this observation further, so let us define some terms to describe AA Patterns:

Levels: The constituent clusters of an AA Pattern come in varying levels of complexity, as in Figure 2. We will use the term ‘level n’ to mean both the nth level of complexity, and the clusters at that level. In all AA Patterns, Level 1, the simplest, is made of either isolated points, or grids of points.

There are also some points which do not belong to a specific cluster. Instead, these points fill the pattern outside the various clusters. We have colored different levels in different colors throughout the illustrations in this paper.

Density: The patterns $AA(94/53)$ in Figure 1(b), and $AA(89/50)$ in Figure 2, have identical clusters at levels 1 and 2. Notice, however, that $AA(89/50)$ is crowded with level 2 clusters, in contrast to the sparse appearance of these clusters in $AA(94/53)$. We say that level 2 is denser in $AA(89/50)$ than in $AA(94/53)$. In section 4 we will see an example of how the density of levels relate to the parameter $\alpha$.

Ahmed

(a)

(b)

(c)

Figure 1: Example AA Patterns: (a) $AA(51/28)$ , (b) $AA(94/53)$ , and (c) $AA(53/30)$ ; colored to reveal details. Notice how points tend to group in symmetric clusters, and notice the apparent gaps between the clusters. (a)

(b) Figure 2: (a) $AA(89/50)$ is built from 3 distinct types of clusters (b), at varying levels of complexity. The smallest tile of this pattern contains 25 level 1 clusters of 1 point each, 25 level 2 clusters of 12 points each, 1 level 3 cluster of 336 points, and 860 unclustered points. Notice how each level 3 cluster has pockets for housing 9 level 1 clusters and 4 level 2 clusters.

The natural question about AA Patterns is how to select the parameter $\alpha$ . Indeed, there is an infinitude of real numbers between 1 and 2, and it is desirable to have a way to know which values of $\alpha$ will generate patterns with some specific set of features. In the rest of this paper we will demonstrate how mathematical analysis could help in achieving this goal.

3 Square Roots

It was shown in [2] that an irrational parameter $\alpha$ generates an aperiodic AA Pattern, whereas a rational parameter $\alpha =p/q$ , $p,q\in \mathbb{N}$ , generates a periodic pattern $AA(p/q)$ , with translational symmetries over the steps

Even when $p/q$ is only a close approximation to $\alpha$ , then the pattern $AA(\alpha )$ tends to repeat, with small discrepancies, over the same steps as in (2). They are these discrepancies that distinguish AA Patterns from simple tiling patterns.

Thus, the best rational approximations of $\alpha$ manifest in the distances between repeating details in the pattern, and if we have a method to understand or control the distribution of the best rational approximations of $\alpha$, then that method will help us predict or control the associated pattern. Continued fractions offer this sought after method, and square roots offer good template parameters to start with. Indeed, square roots (and all quadratic irrationals) have periodic continued fraction expansions, and hence have regular distributions of best rational approximations. Let us make a quick review of this. Let $s$ be a non-square integer, and let

$p/q\approx \sqrt{s}p,q\in \mathbb{N}.$ (3)

The closest $p/q$ can come to $\sqrt{s}$ is when

$p^2-s{q}^2=\pm 1.$ (4)

This is the Pell equation [3]. Now suppose that another pair of integers $\{p\prime ,q\prime \}$ also satisfies equation (4), and that $\{p\prime ,q\prime \}$ is linearly related to $\{p,q\}$:

[ \left[\begin{array}[]{c}p\prime\ q\prime\end{array}\right]=\left[\begin{array}[]{cc}a&b\ c&d\end{array}\right]\left[\begin{array}[]{c}p\ q\end{array}\right]\quad a,b,c,d\in\mathbb{Z},. ] (5)

Substituting $p\prime$ and $q\prime$ from (5) into (4):

$(ap+bq{)}^2-s(cp+dq{)}^2=\pm 1,$

or

$(a^2-s{c}^2)p^2+(2ab-2scd)pq-(s{d}^2-b^2)q^2=\pm 1.$ (6)

Comparing (6) to (4) we get:

$a^2-s{c}^2$ $=$ $\pm 1,$ (7) $s{d}^2-b^2$ $=$ $\pm s,$ (8) $ab-scd$ $=$ $0.$ (9)

From these three equations we can see that $a=d$ and $b=sc$. It remains, then, to solve (7) which is, again, Pell’s equation. It is known to have a solution for all $s$ in the positive case, hence it is always possible to find linearly related best rational approximations of square roots that satisfy (4). But we are not solving for $s$! We are actually interested in $a$ and $c$. Indeed, a bit of algebra shows that the set of $\{p,q\}$ pairs that solve equation (4) forms the sequences

$p_n$ $=$ $2a{p}_{n-1}\mp p_{n-2},$ (10) $q_n$ $=$ $2a{q}_{n-1}\mp q_{n-2},$ (11)

for which

${\lim }_{n\to \infty }\frac{p_{n+1}}{p_n}={\lim }_{n\to \infty }\frac{q_{n+1}}{q_n}=a+c\sqrt{s}.$ (12)

If the limiting ratio in (12) is too large, the best rational approximations of $\alpha$ are too far apart, so are the partial-repetition steps of the pattern. We should therefore search for relatively small values of $a$ and $c$. One way to do so is to set $c$ and then find $s$ for different values of $a$. Thus, (7) should be re-arranged to read

$s=\frac{a^2\pm 1}{c^2}.$ (13)

When $c$ is 1, (13) solves to

$s_1=\{3,8,15,\dots \}$ (14)

for the minus case, and

$s_2=\{5,10,17,\dots \}$ (15)

for the plus case. Square roots of these are all candidate template parameters to start from, after applying the suitable integer offset $F$ that brings $\alpha$ back into the the range $(1,2)$, as required in the transform (1). Experimentation revealed that the group of patterns $\mathrm{AA}\left(\sqrt{s_1}-F\right)$, and the group $\mathrm{AA}\left(F-\sqrt{s_2}\right)$, constitute two families of AA Patterns characterized by common features. We will call these two families of patterns the $s_1$ and the $s_2$ families, respectively.

Figure 3 shows example $s_1$ and $s_2$ patterns. Let us take $AA(\sqrt{3})$ as a reference, and make a short description of it. Each cluster in $AA(\sqrt{3})$ looks like a tilted ‘#’, with two arms in each of the East-of-North, South-of-East, West-of-South, and North-of-West directions. Each cluster is surrounded by a ring of 12 clusters from the lower level, and each cluster houses one cluster from the lower level in the middle, and houses 16 clusters from the next lower level, and many more from each of the lower levels. These relationships are recursive. For example, each of the surrounding clusters has its own suite from the lower levels. More important, there is an apparent self-similarity between levels, and each level looks like being synthesized from parts of the lower level.

The other $s_1$ patterns are similar to $\mathrm{AA}(\sqrt{3})$, but have increasing densities at all levels. For example, the single lower-level cluster in the middle becomes a grid of clusters, the two arms become many arms, and the surrounding ring becomes a band of rings. The corresponding patterns from the $s_1$ and $s_2$ families have the same general features, but the latters have longer arms than the formers, as can be seen in Figure 3.

The metrics (the distances between repeating details) in $s_1$ and $s_2$ patterns reflect sequences obtained from (10) and (11). For example, the metrics of $\mathrm{AA}(\sqrt{3})$ manifest the sequences $\{1,4,15,56,\dots \}$ and $\{1,3,11,41,\dots \}$ (seq. A001353 and A001835 in [5]). A unique property of $\mathrm{AA}(\sqrt{3})$ is that $\sqrt{3}$ and the limits in (12) are related to the trigonometry of multiples of $\pi /6$, and for this reason the pattern also exhibits a sort of rotational symmetry around this angle which divides the circle uniformly.

4 Continued Fractions

In the previous section we have selected square roots of two sets of integers as template parameters for AA Patterns, and in this section we will illustrate how to tweak these initial parameters in order to control the patterns. For this purpose we will investigate the continued fraction expansions of our template parameters. We will write continued fractions in the form

$\alpha =\left[{\alpha }_0;{\alpha }_1,{\alpha }_2,\cdots \right].$

Further, we will use curly brackets $\{\}$ to enclose a portion of the continued fraction that repeats zero or more times, or possibly repeats forever if it is the last entry.

Equations (10) and (11) describe the convergents of the parameter $\alpha$, in terms of the two preceding convergents. In this form, the equations essentially tell that subsequent entries of the continued fraction expansion of $\alpha$ are equal:

${\alpha }_i=2a;a=2,3,4,\cdots ,$ (16)

but the $s_1$ parameters use subtraction in their continued fraction, like

$\sqrt{3}=2-1/\left(4-1/\left(4-1/\left(4-1/\cdots \right)\right)\right).$

Mathematical Hints for Parameter Selection for AA Patterns

(a)

(b)

(c) Figure 3: (a) $AA(\sqrt{3})$ and (b) $AA(4-\sqrt{5})$ are the first patterns in the $s_1$ and $s_2$ families, respectively, and (c) $AA(\sqrt{8}-1)$ and (d) $AA(5-\sqrt{10})$ are the seconds. Notice how the $s_2$ family of patterns have longer arms than the $s_1$ family, and notice that the second pattern in each family is denser than the first, at all levels, and that its clusters has one more arm in each side.

(d)

Ahmed

(a)

(b)

(c) Figure 4: (a) $AA([1;1,2,1])$, (b) $AA([1;1,2,1,2,1])$, and (c) $AA([1;1,2,1,2,1,2,1])$, showing how a new higher level appears on adding a new period to the continued fractions expansion of $\alpha$ compliant to (17) and (18).

When the appropriate offsets are included, and if we restrict ourselves to addition only in continued fractions, we find that the parameters of $s_1$ patterns have the periodic form

and the parameters of $s_2$ patterns maintain the periodic form

Let us now try some tweaks on our template parameters. The reader is also encouraged to experiment himself using the interactive Java applet which the author has made available online [1].

Truncated Patterns: The first tweak that might come into mind is to truncate the infinite continued fraction of the irrational $\alpha$ at some period. It was found that truncating the continued fraction to few periods limited the constituent clusters of the pattern to few levels. Seen the other way round, each additional period in the continued fraction corresponds to a new level in the pattern, as illustrated in Figure 4. We will use patterns truncation in our subsequent examples to limit the patterns to level 4, which should be sufficient for the illustrations.

Intra-Family Hybrids: Instead of exactly repeating the periodic entries of the continued fraction, a possible tweak is to borrow one or more periods from the parameters of other members in the same family of patterns. The borrowed periods bring features from their source patterns, as illustrated in Figure 5. Another way to look at this tweak is that we modify the value of $x$ at certain periods. Seen this way, we find that the value of $x$ at different periods control the density of levels. It is subtle, however, to notice that the level whose density is affected is not the level associated with the modified period (in terms of truncation discussed above), but the lower level.

Inter-Family Hybrids: Crossbreeding the $s_1$ and $s_2$ families is also possible. It took some experimentation to find out how to switch between the continued fraction forms (17) and (18). For an AA Pattern to start like $s_1$ patterns, and then switch to look like $s_2$ patterns at higher levels, the parameter should have the form

and for a pattern to start like $s_2$ patterns, and then switch to look like $s_1$ patterns at higher levels, the parameter should have the form

Mathematical Hints for Parameter Selection for AA Patterns

(a)

(b)

(c)

Figure 5: (a) $AA([1;1,4,1,2,1,2,1])$ , (b) $AA([1;1,2,1,4,1,2,1])$ , and (c) $AA([1;1,2,1,2,1,4,1])$ , showing the effect of replacing the first, second, or third period, of (truncated) $AA(\sqrt{3})$ with the corresponding periods from $AA(\sqrt{8}-1)$ . Compare with the original patterns in Figure 1(a, c). (a)

(b)

Figure 6: (a) $AA([1;1,2,1,3,4])$ looks like $s_1$ patterns (short arms) at level 2, and like $s_2$ patterns (long arms) at level 3. In contrast, (b) $A([1;1,3,4,3,1])$ looks like $s_2$ at level 2, then switches to look like $s_1$ at level 3. Level 1 has the same look in $s_1$ and $s_2$ patterns. (a) Figure 7: Example dual-parameters patterns: (a) AA ([1; 1, 2, 1, 2, 1, 2, 1], [1; 1, 4, 1, 2, 1, 2, 1]), and (b) AA ([1; 1, 2, 1, 2, 1, 2, 1], [1; 1, 3, 4, 4]).

(b)

Figure 6 illustrates these tweaks. It is possible to switch back and force between the two families as many times as wished.

Dual-Parameters Patterns: There is a completely different approach to crossbreeding in AA Patterns: to use different values of $\alpha$ in the two entries of (1). Not all AA Patterns can mix this way, but at least all members of $s_1$ and $s_2$ families (and their truncated, intra-family, and inter-family derivatives) can mix smoothly. The resulting patterns reflect one of the mixed patterns in one direction, and the other parent pattern in the orthogonal direction. Dual-parameters patterns can be designated as $AA({\alpha }_1,{\alpha }_2)$. Figure 7 shows some examples.

5 Conclusion

We have seen that the AA Patterns are controllable in many ways by manipulating the continued fraction of $\alpha$. Only two forms of continued fractions were investigated, and we have found that it is possible to tweak these forms as needed. Other forms of continued fractions should be the subject of future research.

What we have discussed could be approached differently as a way to predict AA Patterns. Indeed, if the continued fraction of $\alpha$ could be parsed successfully into the form:

$[1,1,\{\{2x,1\},2x+1,\{2x+2\},2x+1,1\}],$

or in the continued fraction form:

$2-1/\left((2x_0+2)\pm 1/\left((2x_1+2)\pm 1/\left((2x_2+2)\pm 1/\cdots \right)\right)\right),$

then it is possible for a person, or even a computer, to tell how the resulting pattern would look. This suggests a role for AA Patterns in visualization.

It is worth noting that AA Patterns are closely related to Voronoi patterns discovered accidentally by Kaplan [4], since both types involve quantization artifacts. Many differences make research on AA Patterns easier than Voronoi patterns. After all, the logic of AA Patterns is completely contained inside the generating algorithm, and the algorithm is simple and linear. The argument remains, however, that such accidentally discovered algorithmic arts are worth the research.

Moreover, Kaplan resorted to frequency domain in his analysis, whereas all the analysis of AA Patterns, herein or in [2], used elementary algebra. Thus, there is a potential of making new findings, either in AA Patterns or in Voronoi patterns, by exchanging the analysis approaches. Experimenting with either types of patterns remains a good starting point for making new findings like the ones discussed here, and for that reason the reader is encouraged to experiment with the Java applet the author has made available online [1].

References

• [1] Abdalla G. M. Ahmed. AA Patterns Web Site. http://aapatterns.abdallagafar.com.
• [2] Abdalla G. M. Ahmed. Pixel Patterns from Quantization Artifacts of Forward Affine Mapping. Journal of Graphics, GPU, and Game Tools, 15(2):73–94, 2011. DOI: 10.1080/2151237X.2011.563670.
• [3] H. W. Lenstra Jr. Solving the Pell Equation. Notices of The American Mathematical Society, 49 Number 2:182–192, 2002.
• [4] Craig S. Kaplan. Aliasing Artifacts and Accidental Algorithmic Art. In Renaissance Banff: Bridges 2005: Mathematical Connections in Art, Music and Science, pages 349–356, 2005.
• [5] Neil A. J. Sloane. The On-Line Encyclopedia of Integer Sequences. Accessible electronically at http://www.research.att.com/~njas/sequences/ or at http://www.oeis.org.