Are Maximally Unbalanced, Hilbert-Style, Square-Filling Curve Motifs a Drawing Medium?

Year: 2023 Authors: Douglas M. McKenna

Core claim

Maximally unbalanced Hilbert-style motifs can function as a subtle drawing medium for low-resolution images, with perceptibility enhanced by vertical or horizontal motion.

Topics

space-filling curves, Gray codes, image perception, optical illusion

Domains

Hamiltonian cycles, toroidal grid-graphs, n-ary Gray codes, computational art, visual communication, optical illusion, pixel-based drawing

Methods

motif construction, low-resolution image experiment, orientation rotation, visual perceptibility test

Media

computer screen, binary-valued pixels, filled polygon, smiley face image

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 2023 Conference Proceedings

Are Maximally Unbalanced, Hilbert-Style, Square-Filling Curve Motifs a Drawing Medium?

Douglas M. McKenna

Mathemæsthetics, Inc., Boulder, Colorado, USA; doug@mathemaesthetics.com

Abstract

Hilbert-style, square-filling curve motifs build Hamiltonian cycles on toroidal grid-graphs. Order- $n$ motif paths are equivalent to two-dimensional $n$ -ary Gray codes, which can be characterized by their balance: the disparity between the vertical and horizontal counts of the line segments used. We report on an experiment using maximally—but oppositely—unbalanced Hilbert-style motifs, both dual and zipping, as binary-valued “pixels” in a low resolution image. The images are subtly perceptible, more so when in motion vertically or horizontally on a computer screen.

Introduction

A space-filling curve continuously maps a one-dimensional parameter $0.0\le t\le 1.0$ onto every point within a higher-dimensional region. Each construction can be illustrated using a path that approximates the limiting, non-differentiable curve. An approximation path is typically built of piecewise-connected line segments, with convergent detail added iteratively. In the limit, space-filling curves are surjective, i.e., self-contacting. But when an approximation path is self-avoiding, its progress through the region being filled is visually unambiguous and divides its space into two simply connected pieces. The constraint of self-avoidance can also have combinatorial consequences.

Consider those constructions that fill a square $S$ , recursively subdivided into an $n\times n$ array $S_n$ of orientable subsquares $s_i$ . On $S_n$ , a motif is a sequence of length $n^2$ comprising all subsquares $s_i$ for $1\le i\le n^2$ where (a) each sequential pair $(s_i,s_{i+1})$ is spatially adjacent, and (b) $s_1$ and $s_{n^2}$ are chosen such that connected scaled and oriented copies of the motif can be placed (using a suitable linear transformation) in each oriented $s_i$ to build a next level of detail in a connected path. There are three recursive motif connection geometries [7, 8] (see Fig. 1 of [8]), one of which is Hilbert-style, where $s_1$ is at a corner of $S$ and $s_{n^2}$ is at an adjacent corner. We focus here on Hilbert-style constructions whose approximation paths—built from repeated, oriented, connected sub-paths based on the motif—are self-avoiding lattice paths having horizontal and vertical segments only.

Figure 1: Left: Edge adjacent subsquares only. Right: Mixed edge and corner-only adjacency.

Each $(s_i,s_{i+1})$ can be pairwise-adjacent in two ways, depending on whether $s_i$ and $s_{i+1}$ share one or two corners (see Fig. 1 above). If they share two corners, $s_i$ and $s_{i+1}$ necessarily share an edge, and we say the pair is edge-adjacent. If just one corner is shared, the pair is corner only-adjacent. For all approximation paths—which graphically represent the sequence of subsquares—to be self-avoiding

McKenna

on the lattice at all iterative levels of detail, Hilbert-style motifs are either zipping or dual, depending on whether a corner-only adjacent (“catty-corner”) pair of subsquares is present or not.

Because the center of each $s_i$ is a node in the dual grid-graph, dual motifs are illustrated by connecting centers of adjacent subsquares with line segments (graph edges); such paths are always self-avoiding. Zipping motif paths are formed using just the edges of sequential $s_i$ ‘s sharing the corner where two such edges meet. For square-filling constructions, these paths can be self-avoiding only when certain Fibbinary “zipper” patterns form along the four sides of $S_n$ [6], such as in Figure 2.

Figure 2: A sample zipping configuration along bottom and top boundaries of two motifs.

In both cases, the sequence of line segments forms a self-avoiding path of edges that can be treated as a Hamiltonian cycle on an order- $n$ toroidal grid-graph. As the order $n$ increases, the number of possible motifs, whether dual or zipping, for $S_n$ increases (at the very least) exponentially; see A000532 (dual motif counts) and A350148 (distinct zipping counts) [12]. One can then pick and choose among motifs according to some criteria, and to use them for other graphic purposes.

We do not use Knowlton’s technique of building a gray-scale image substituting partial (zipping) motifs at the final level [11, 5]. Nor do we use half-toning techniques to create gray scales, as applied to piecewise-continuous paths by varying line width [9], or substituting final independent patterns, such as truchet tiles [2]. Here, the experiment is to see what is minimally possible.

Gray Code Balance

A Hamiltonian cycle on an $N$ -dimensional grid-graph traverses edges to reach every node sequentially. The path is equivalent to a Gray code [4], where a transition is a step from one grid-graph node to a neighbor, such that exactly one of the neighbor nodes’ $N$ coordinate values changes. This is why center-connected dual paths for motifs with corner-only adjacent pairs don’t qualify as Gray codes, because a diagonal edge requires a change in two coordinates (e.g., see Fig. 1, right).

Gray codes can be classified according to their transition count distribution among coordinates. For $N=2$ , let $(h,\nu )$ be the counts of (horizontal, vertical) edges. When these counts are as close as possible, $|\nu -h|$ is either 0 or 1 and the code is considered balanced [1] (if a path has an odd number of edges in it, the difference in counts can never be 0). But our visual system distinguishes between horizontal and vertical elements of an image. So here we want to play with motifs whose approximation paths are maximally unbalanced, i.e., where $h\gg \nu$ or $\nu \gg h$ , while leaving all else essentially homogeneous.

Drawing with Dual Path Motifs

Consider the dual path motif for $S_6$ in Figure 3. The motif is highly unbalanced; it has 26 vertical segments connecting the centers of subsquares, but only 9 horizontal. Because of this, the $2\times 2$ array of still-vertical motifs in the lower middle of the second approximation stands out, surrounded by motifs rotated by $90^{\circ }$ on all sides. When an unbalanced vertical (or horizontal) motif is rotated

Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing

Medium?

by $\pm 90^{\circ }$ , it now contributes horizontal (or vertical) unbalance to the new approximation path. Even though the path homogeneously reaches each $s_i$ , the difference is still perceptible in this low resolution case, even more so in the filled case where, on average, there is (above the added base) the same amount of foreground space as unfilled background.

Figure 3: Left: An order-6 motif. Middle: Its second approximation path. Right: Its third, with base, filled.

In Hilbert-style motifs, there is an asymmetry between horizontal and vertical. The motif has to travel horizontally only from lower left to lower right. But vertically, what goes up must come down. Hence maximally vertically unbalanced dual motifs look like those in the top row of Figure 4. For even $n$ , there are only $n-1$ horizontal path segments (the minimum possible), but all the rest $(n^2-n)$ are necessarily vertical. For odd $n$ , more horizontal segments are required for the self-avoiding dual path to reach its destination down the right side. This tells us that $n$ ‘s parity has an effect on both form and maximum unbalance. Maximally horizontally unbalanced order- $n$ motifs have related structures, as the bottom row of Figure 4 shows.

Figure 4: Maximally vertical (top) and horizontal (bottom) motifs for orders $n=6,7,8$ , and 9.

Under normal space-filling curve construction, a motif’s self-similar arrangement of horizontally and vertically oriented subsquares containing scaled copies of that same motif has essentially no combinatorial freedom with which to find ways to place a single motif in a manner that might depict an arbitrary image represented by binary pixel values. But for an approximation path rendered to a given iterative level, we can mix and match any motifs (of the same order) at the last substitution level, using one or the other unbalanced motif to undo the intrinsic orientation, and then doing the opposite for the foreground binary pixel values in another image. For example, Figure 5 uses the order-2 Hilbert Curve to create a linearized sequence of subsquare “pixels” in a $32\times 32$ image. Each

McKenna

pixel will in turn be an $8\times 8$ array of subsquares. Depending on the binary value of each “pixel,” one of two maximally unbalanced vertical or horizontal order-8 dual motifs taken from Figure 4 is placed at that pixel’s position, keeping the self-avoiding path piecewise-connected. When the resultant path is filled, even though the entire image is as close as possible to everywhere $50\%$ gray, one’s eye can still perceive the image subtly being depicted. Interestingly, the image is more easily perceived when it is moving horizontally or vertically on a digital display (e.g., as a PDF drawing), because oppositely valued display pixels separated by horizontal lines don’t change much with overall horizontal movement, whereas they change a lot with vertical movement, and vice-versa.

Figure 5: Filled simple polygon (with a base) showing an image made of oppositely oriented dual motifs as “pixels.” Foreground (background) pixels are maximally unbalanced horizontally (vertically). The foreground black is a filled, simply connected polygon with $(32^2\times 8^2=65536)+3$ sides.

Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing

Medium?

The Same Experiment with Zipping Path Motifs

The second type of Hilbert-style motifs, zipping motifs, have approximation paths built by connecting subsquare edges, not centers. Unlike dual paths, which always traverse the interior of $S_n$ , zipping paths must travel along portions of $S_n$ ‘s four sides. To be always self-avoiding, these motifs have boundaries characterized by palindromic bit patterns where no two 1 bits are adjacent. Each such pattern creates a “Fibbinary zipping mode” [6]. Order- $n$ motifs having the same zipping mode can mesh (zip) with each other to maintain Hamiltonian self-avoidance. So for a given mode, we can pick and choose motifs based on maximal unbalance, just as we did above for dual path motifs. Unlike dual path motifs, it is not easy to determine whether an order- $n$ zipping motif is maximally unbalanced without resorting to computer enumeration and analysis. The left half of Figure 6 shows two maximally unbalanced order-9 motifs, which we’ve used in Figure 8. The right half shows another two maximally unbalanced order-13 motifs, used in Figure 9.

Figure 6: Motifs for maximally, but oppositely, unbalanced order-9, zipping mode 1 (left half), and order-13, zipping mode 0 (right half), used in Figures 8 and 9, respectively.

At a low resolution, it is fairly easy to perceive the transitions between vertical and horizontal $13\times 13$ “pixels,” as this close-up of Figure 9 shown in Figure 7 shows:

Figure 7: Close up of left side of Figure 9 showing maximally vertical and horizontal, order-13 “pixels.” At this low resolution, it is fairly easy to perceive the vertically and horizontally unbalanced areas.

McKenna

Conclusions

The answer to the paper’s title question is yes, but just barely. From a distance, $50\%$ grayness overwhelms all else. The closer one looks at the details, the easier it is to see oppositely balanced “pixels” (motifs), but then the overall image becomes harder to see in full, except perhaps when the image is moving, either vertically or horizontally. An optimal intermediate resolution level is likely.

Figure 8: Filled polygon (with a base) showing an image made of oppositely oriented zipping motifs as “pixels.” Foreground (background) pixels are maximally unbalanced horizontally (vertically). The foreground black is a filled, simply connected polygon with $(49^{\mathcal{I}}\times 9^{\mathcal{I}}=194481)+3$ sides.

Maximally unbalanced, Hilbert-style, dual motifs appear to have an edge (ironic pun intended) in visual comprehensibility over zipping motifs, because the latter must intermix horizontal and

Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing

Medium?

vertical elements along their boundaries, so that all unbalance is in each zipping motif’s interior. We’ve not yet played with other style motifs. For instance, Peano-style (from corner to opposite corner) are likely to be similar to dual motifs in perceptibility, especially because every Peano motif, whether maximally unbalanced or not, has an oppositely oriented version of itself by virtue of a simple mirroring across the subdivided square’s diagonal, flipping horizontal edges with vertical.

Figure 9: Maximally, but oppositely, unbalanced order-13, mode 0 zipping motifs. Foreground (background) pixels are maximally unbalanced horizontally (vertically). The underlying smiley face image is more perceptible when it is moving or being scrolled on a computer screen. The foreground black is a filled, simply connected polygon with $(49^2\times 13^2=405769)+3$ sides.

McKenna

There are generalizations of Hamiltonian paths on square grids involving loops [3] that can also be classified according to balance. But not every Hamiltonian path has the property that each edge can be bijectively associated with each sub-area of a filled region, as is true of space-filling motifs and the non-looping piecewise-connected paths they can create.

Font glyphs and simple logos rely on low-resolution, single-toned images, and might be interesting areas for further exploration. To the extent the technique fails to depict an image whose information is nonetheless there, there may also be steganographic or optical illusion applications.

References

[1] G. S. Bhat and C. D. Savage. “Balanced Gray Codes.” Elec. Jour. of Combinatorics, Vol. 1, #3, Article R25 (1996). www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r25.

[2] R. Bosch. “Opt Art: Special Cases.” Bridges Conference Proceedings (2011), pp. 249–256. http://archive.bridgesmathart.org/2011/bridges2011-249.html.

[3] J. Gier. “Fully Packed Loop Models on Finite Geometries.” In Polygons, Polyominoes and Polycubes, Springer, Dordrecht (2009), pp. 317–346. https://arxiv.org/pdf/0901.3963.pdf.

[4] M. Gardner. “The Binary Gray Code.” Knotted Doughnuts and Other Mathematical Entertainments, W. H. Freeman (1986), ch. 2.

[5] K. Knowlton. “Portrait of Doug McKenna, using one of his curves.” (2002). https://www.knowltonmosaics.com/pages/DgMcK.htm.

[6] D. M. McKenna. “Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-style Square-Filling Curves.” Enumerative Combinatorics and Applications, 2:2, Article S2R13 (2022). ecajournal.haifa.ac.il/Volume2022/ECA2022_S2A13.pdf.

[7] D. M. McKenna. “Asymmetry vs. Symmetry in a New Class of Space-Filling Curves.” Bridges Conference Proceedings (2006), pp. 371–378. https://archive.bridgesmathart.org/2006/bridges2006-371.html.

[8] D. M. McKenna. “The 7 Curve, Carpets, Quilts, and Other Asymmetric, Square-Filling, Threaded Tile Designs.” Bridges Conference Proceedings (2007), pp. 225–232. https://archive.bridgesmathart.org/2007/bridges2007-225.html.

[9] K. Mitchell. “Oak Tree.” Print (2007). http://www.kerrymitchellart.com/gallery20/oaktree.html.

[10] P. Prusinkiewicz and A. Lindenmyer. The Algorithmic Beauty of Plants. Springer (1996), p. 14. http://algorithmicbotany.org/papers/abop/abop-ch1.pdf.

[11] A. Seckel. Masters of Deception: Escher, Dali & the Artists of Optical Illusion. Sterling Pub. Co. (2004), p. 171.

[12] N. A. J. Sloane. The On-Line Encyclopedia of Integer Sequences. www.oeis.org.

98