Zigzag Mosaics and Single-Line Drawings

Year: 2024 Authors: Robert Bosch; Tuan Dung Do

Core claim

Single-variable calculus can convert grayscale images into zigzag mosaics and then into easy-to-trace single-line drawings.

Topics

zigzag tiles, single-line drawings, halftoning, mosaics, optimization

Domains

single-variable calculus, Euclidean geometry, optimization, halftoning mathematics, mosaic art, visualization, generative design, image rendering

Methods

path-length formula, single-variable optimization, grayscale-to-length mapping, row-by-row linking

Media

square tiles, hexagonal tiles, digital grayscale images, tempera painting reference

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

Zigzag Mosaics and Single-Line Drawings

Robert Bosch and Tuan Dung Do

Oberlin College, Oberlin, Ohio, USA; rbosch@oberlin.edu, tuandung0708@gmail.com

Abstract

We introduce several varieties of zigzag tiles and describe how to use them to make mosaics and single-line drawings.

Introduction

The lefthand side of Figure 1 displays a zigzag tile: a white square tile decorated with a black zigzag path. When we “read” a zigzag tile from left to right, we see that its zigzag path visits points 1 through 5 in succession. The positions of points 1, 3, and 5 are fixed; their $(x,y)$ coordinates are $(-0.5,0)$ , $(0,0)$ , and $(0.5,0)$ , respectively. The positions of points 2 and 4, which are forced to remain on the light gray vertical “sliders,” are not fixed but constrained: their $(x,y)$ coordinates are $(-0.25,s)$ and $(0.25,-s)$ , respectively, where $0\le s\le 0.5$ . Note that when $s=0$ , points 2 and 4 lie on the horizontal bisector of the tile, and the tile ends up being as bright as it can possibly be (due to its path being as short as possible). And when $s=0.5$ , point 2 lies on the top edge of the tile, point 4 lies on the bottom edge, and the tile ends up being as dark as we allow it to be (due to its path being as long as we allow it to be).

Figure 1: (left) A zigzag tile, and (right) a $49\times 49$ zigzag mosaic made out of $49^2=2401$ zigzag tiles.

The righthand side of Figure 1 displays a zigzag mosaic, a two-dimensional array of zigzag tiles. For each row $i$ from 1 to 49 and each column $j$ from 1 to 49, we needed to determine $s_{i,j}^{\ast }$ , the ideal $s$ -value for tile $(i,j)$ , the zigzag tile in the row- $i$ -column- $j$ entry of the array. Our goal was to produce a mosaic that would closely resemble a section of Sandro Botticelli’s Birth of Venus [4] when viewed from a distance. We accomplished this goal by solving a total of $49^2=2401$ single-variable optimization problems.

Bosch and Do

Using Single-Variable Calculus to Select the Best Zigzag Tile

Let $L(s)$ denote the length of a zigzag tile’s path. By using the Euclidean distance formula and rules for differentiation taught in a first-semester calculus course, it is straightforward to show that

$L(s)=\sqrt{1+16s^2},L^{\prime }(s)=\frac{16s}{\sqrt{1+16s^2}},\text{and}{L}^{\prime \prime }(s)=\frac{16}{(1+16s^2{)}^{3/2}}.$

Although $L(s)$ is continuous and differentiable for all values of $s$, we restrict our attention to $s$-values between $0$ and $s_{\max }=0.5$. (Later on, we will demonstrate the effect of increasing $s_{\max }$.)

Now suppose that we want a tile’s zigzag path to have length $\lambda$. Because we know that $L(0)=1$, $L(0.5)=\sqrt{5}$, and $L(s)$ is continuous and strictly increasing on $(0,\infty )$, we can conclude that if the desired length $\lambda \in [1,\sqrt{5}]$ then there is a unique $s$-value that produces that length. Moreover, we can obtain $s^{\ast }$, the ideal $s$-value, by setting $L(s)$ equal to $\lambda$ and solving for $s$. Doing so yields

$s^{\ast }=\frac{1}{4}\sqrt{{\lambda }^2-1}.$ (1)

If $\lambda \in [0,1)$ then the optimal $s$-value is $s^{\ast }=0$. If $\lambda \in (\sqrt{5},\infty )$ then the optimal $s$-value is $s^{\ast }=0.5$.

A second, equivalent way of computing $s^{\ast }$ involves using single-variable calculus to minimize the squared error function $f(s)=(L(s)-\lambda {)}^2$. By using rules for differentiation taught in a first-semester calculus course, we obtain

$f^{\prime }(s)=2(L(s)-\lambda )L^{\prime }(s)\text{and}{f}^{\prime \prime }(s)=2(L^{\prime }(s){)}^2+2(L(s)-\lambda )L^{\prime \prime }(s).$

It is clear that if $\lambda \le 1$, then $s^{\ast }=0$. In addition, if $1<\lambda \le \sqrt{5}$ then $s=0$ cannot be optimal, and the only stationary point for $f$ will be the unique $s$-value for which $L(s)=\lambda$, the value of $s^{\ast }$ shown in equation (1). Finally, $f^{\prime \prime }(s^{\ast })>0$, which tells us that $f$ is convex at $s^{\ast }$ and that $s^{\ast }$ is the global minimizer of $f$ over $[1,\sqrt{5}]$.

Figure 2 displays a $5\times 25$ zigzag mosaic of a gradient. To make this mosaic, we set ${\lambda }_{i,j}$, the desired length of tile $(i,j)$’s zigzag path, equal to ${\lambda }_{i,j}=0.95+0.05j$ for all $i,j$ satisfying $1\le i\le 5$ and $1\le j\le 25$, and then we used equation (1) to obtain the $s_{i,j}^{\ast }$’s.

Figure 2: A $5\times 25$ zigzag mosaic made out of $5\cdot 25=125$ zigzag tiles.

To make a mosaic like the Venus mosaic shown on the righthand side of Figure 1, we need to convert the target image’s grayscale values into desired lengths. If $b_{i,j}\in [0,1]$ denotes the brightness of pixel $(i,j)$, the row-$i$-column-$j$ pixel of the target image, and $0$ stands for black, $1$ stands for white, and intermediate values stand for various shades of gray, then we can use the following linear equation to compute the desired lengths:

${\lambda }_{i,j}=\sqrt{5}+(1-\sqrt{5})b_{i,j}.$ (2)

Equation (2) ensures that ${\lambda }_{i,j}=1$ (the shortest possible length) when $b_{i,j}=1$ and that ${\lambda }_{i,j}=\sqrt{5}$ (the longest length we allow ourselves to use) when $b_{i,j}=0$. If we want to use a $s_{\max }$-value other than $0.5$, we will have ${\lambda }_{\max }=\sqrt{1+16s_{\max }^2}$ and ${\lambda }_{i,j}={\lambda }_{\max }+(1-{\lambda }_{\max })b_{i,j}$.

Zigzag Mosaics and Single-Line Drawings

Figure 3 demonstrates what happens when we increase $s_{\max }$ from 0.5 to 0.7 and then to 0.9. If we allow our zigzag tiles to have longer zigzag paths, we will gain the ability to produce mosaics that have higher contrast. But when $s_{\max }$ exceeds 0.5, we may find that some of our tiles’ zigzag paths extend outside of their square frames. This can make neighboring path segments (on a tile and on the tiles above or below this tile) difficult to distinguish and, in addition, can create optical effects that may make the resulting mosaics more difficult to process by our visual systems, particularly when we view them from up close.

Figure 3: Three $29\times 29$ zigzag mosaics with (left) $s_{\text{max}}=0.5$ , (center) $s_{\text{max}}=0.7$ , and (right) $s_{\text{max}}=0.9$ .

Converting Zigzag Mosaics into Single-Line Drawings

Computationally speaking, it is very easy to make a zigzag mosaic. (If the target image is $m\times n$ , then the total amount of work required is $O(mn)$ .) And it is even easier to transform a zigzag mosaic into a single-line drawing. All we have to do is connect the first row of zigzag paths to the second row on the mosaic’s right edge, the second row to the third row on the left edge, and continue in this fashion, alternating between making connectons on the right and making them on the left. If the mosaic has an odd number of rows, it will be possible to trace the resulting single-line drawing from the top left corner to the bottom right corner, as shown in Figure 4. If the mosaic has an even number of rows, the ending point will be in the bottom left corner.

Figure 4: A single-line drawing based on a $5\times 25$ zigzag mosaic.

This method for making single-line drawings is much faster than TSP Art [2,5] and the tile-based approach that was recently introduced by Bosch and Snyder [3]. Another advantage is that zigzag-mosaic single-line drawings are extremely easy to trace by hand or eye. During the review process a helpful referee pointed out that our zigzag tiles were previously studied by Ahmed and Deussen [1], who did not discuss connections with calculus. Ahmed and Deussen refer to their work as amplitude-modulated line-based halftoning, which would put both their work and ours in the same family as Claude Mellan’s famous “line-thickness-modulated” spiral-shaped engraving The Face of Christ on St. Veronica’s Cloth [6] from 1649.

Bosch and Do

Double Zigzag Mosaics and Single-Line Drawings

The lefthand side of Figure 5 displays a double zigzag tile: a white square tile decorated with two black zigzag paths, one horizontal and one vertical. Each path passes through the center of the tile. The horizontal path connects the midpoints of the tile’s left and right edges, while the vertical path connects the midpoints of the tile’s bottom and top edges. On each path, points 1, 3, and 5 are fixed, while points 2 and 4 are confined to their sliders. On the horizontal path, points 2 and 4 have coordinates $(-0.25,s)$ and $(0.25,-s)$ , respectively, where $0\le s\le 0.5$ , just as before. On the vertical path, points 2 and 4 have coordinates $(-t,-0.25)$ and $(t,0.25)$ , respectively, where $0\le t\le 0.5$ .

Figure 5: (left) A double-zigzag tile, and (right) a $49\times 49$ double-zigzag-mosaic single-line drawing.

Here, we let $L(s,t)$ denote the length-sum, the combined lengths of a double zigzag tile’s horizontal and vertical paths. By using the Euclidean distance formula and rules for differentiation taught in a multivariable calculus course, it is straightforward to show that

Here, we let $\lambda$ denote the desired length-sum, and the squared error function is $f(s,t)=(L(s,t)-\lambda {)}^2$ . By using rules for differentiation taught in a multivariable calculus course, we obtain

Careful analysis of all of the above allows us to obtain several useful results. First, when $0\le s\le 0.5$ and $0\le t\le 0.5$ , the smallest and largest length-sums are $L(0,0)=2$ and $L(0.5,0.5)=2\sqrt{5}$ , respectively. Second, if the desired length-sum $\lambda \in [2,2\sqrt{5}]$ , then there exist $s$ -values and $t$ -values for which $L(s,t)=\lambda$ and $f(s,t)=0$ . Finally, at such values the gradient $\nabla f(s,t)$ will equal the zero vector and the Hessian matrix ${\nabla }^{2}f(s,t)$ will be positive semidefinite (and positive definite if $\lambda \in (2,2\sqrt{5}]$ ).

To find $x^{\ast }=(s^{\ast },t^{\ast })$ , a vector whose coordinates are ideal $s$ - and $t$ -values, we apply gradient descent to the squared error function $f(x)=f(s,t)$ . Let $x_0=(s_0,t_0)$ denote the vector whose coordinates are our

Zigzag Mosaics and Single-Line Drawings

initial $s$ - and $t$ -values. If $\nabla f(x_0)=\nabla f(s_0,t_0)\ne 0$ , then the direction vector $d=-\nabla f(x_0)$ will be a descent direction. Our goal is to find a positive scalar $\alpha$ such that the vector $x_1=x_0+\alpha d$ that specifies the new $s$ - and $t$ -values has both of its coordinates in the interval [0, 0.5] and satisfies the inequality f(x_1) &lt; f(x_0) . We start our search for this $\alpha$ by determining the largest step we can take in direction $d$ while keeping both coordinates of $x_1$ in [0, 0.5]. If our steplength $\alpha$ results in f(x_1) &lt; f(x_0) , we use it. If not, we cut it in half and check again. We keep cutting the steplength in half until we end up with f(x_1) &lt; f(x_0) .

To obtain the double-zigzag-mosaic single-line drawing shown in the righthand side of Figure 5, we initialized gradient descent at $x_0=(s_0,t_0)=(0.25,0.25)$ for each pixel $(i,j)$ . An examination of the formulas for $\nabla L(s,t)$ and $\nabla f(s,t)$ makes it clear that when $s=t$ , the $s$ - and $t$ -coordinates of the gradients will also be equal, and this will result in the new $s$ - and $t$ -values being equal as well. Consequently, if we start gradient descent from an initial solution that has $s_0=t_0$ , all subsequent solutions will also have equal $s$ - and $t$ -values, including the optimal solution.

But we don’t have to initialize gradient descent at $x_0=(s_0,t_0)=(0.25,0.25)$ . The double-zigzag-mosaic single-line drawing in the top of Figure 6 used (0.25, 0.25), while the one in the bottom used $x_0=(s_0,t_0)=(0.375,0.125)$ when $i+j$ was even and $x_0=(s_0,t_0)=(0.125,0.375)$ when $i+j$ was odd. Both are reminiscent of parquet deformations.

Figure 6: Two gradient pieces: (top) in which $x_0=(s_0,t_0)=(0.25,0.25)$ and (bottom) in which $x_0=(s_0,t_0)=(0.375,0.125)$ when $i+j$ was even and $(0.125,0.375)$ when $i+j$ was odd.

The lefthand side of Figure 7 displays an additional $49\times 49$ example, which was made by using gradient descent with the more complicated initialization scheme. Double-zigzag-mosaic single-line drawings are nearly as easy to trace as zigzag-mosaic single-line drawings. In each case in which both the number of rows and number of columns is odd, the line can be thought of as starting in the top left corner. It zigzags through row 1 from left to right, row 2 from right to left, and so on until it zigzags through row 49 from left to right. At this point, it moves diagonally to a point just below column 49. It then zigzags up column 49, down column 48, and so on until it finally arrives at its final destination, a point near the top left corner.

It is also possible to create triple-zigzag tiles and triple-zigzag mosaics. A triple-zigzag tile has a hexagonal frame instead of a square frame and has three zigzag paths, each with a pair of sliders. When determining the best form of a triple-zigzag tile, our length-sum function is a function of three variables, one for each zigzag path. For the triple-zigzag mosaics displayed in the righthand side of Figure 7, we forced all three variables to be equal and used single-variable calculus techniques similar to those we used to make our original zigzag mosaics. With triple-zigzag mosaics, it is impossible to achieve the same amount of contrast as with the double-zigzag mosaics or the original single zigzag mosaics. (In a triple-zigzag tile,

Bosch and Do

Figure 7: (left) A double-zigzag-mosaic single-line drawing, and (right) a triple-zigzag mosaic.

the ratio between the maximum possible and minimum possible total lengths of all of the tile’s zigzag paths is $6\sqrt{3}/(3\sqrt{3})=2$ , while in double-zigzag and single-zigzag tiles, this ratio is $2\sqrt{5}/2=\sqrt{5}/1\approx 2.24$ . And with triple-zigzag mosaics, while it is possible to connect the ends of the paths to form a single-line drawing, it doesn’t seem worth it, as the resulting single-line drawing would be very difficult to follow. But as illustrated in [1] (which did not consider double-zigzag or triple-zigzag mosaics), it would be possible to modify triple-zigzag tiles so that they could be used to render color images by employing a CMY color system and using one zigzag path for cyan, a second zigzag path for magenta, and the third path for yellow.

References

[1] Abdalla G.M. Ahmed and Oliver Deussen. Amplitude Modulated Line-Based Halftoning. In Cagatay Turkay and Tao R. Wan, editors, Computer Graphics & Visual Computing, 2016, pages 41-43. [2] Robert Bosch and Adrianne Herman. Continuous line drawings via the traveling salesman problem. Operations Research Letters, vol. 32. no. 4, pages 302-303, 2004. [3] Robert Bosch and Izzy Snyder. A new tile-based method for constructing single-line drawings. In Judy Holdener, Eve Torrence, Chamberlain Fong, and Katherine Seaton, editors, Bridges Conference Proceedings, Halifax, Nova Scotia, Canada, July 27-31, 2023, pages 37-44. https://archive.bridgesmathart.org/2023/bridges2023-37. [4] Sandro Botticelli. Birth of Venus, 1485-86. Tempera. Uffizi Gallery, Florence. [5] Craig S. Kaplan and Robert Bosch. TSP art. In Reza Sarhangi and Robert Moody, editors, Bridges Conference Proceedings, Banff, Alberta, Canada, July 31-Aug. 3, 2005, pages 301-308. https://archive. bridgesmathart.org/2005/bridges2005-301. [6] Claude Mellan. The Face of Christ on St. Veronika’s Cloth, 1649. Engraving. The Metropolitan Museum of Art, New York.