Tuti Interweaving

Year: 2017 Authors: Abdalla G. M. Ahmed; Oliver Deussen

Core claim

Alternating yarn colors in Tuti Weaving enable a structured approach to weaving images on basic Jacquard looms while respecting loom and float constraints.

Topics

algorithmic weaving, image weaving, halftoning, Jacquard looms

Domains

combinatorial matrices, binary arrays, halftoning, textile design, fiber arts, pattern design

Methods

systematic design approach, modular block construction, modified Floyd-Steinberg algorithm

Media

warp yarn, weft yarn, woven fabric, bitmap images

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

Tuti Interweaving

Abdalla G. M. Ahmed* Oliver Deussen Department of Computer and Information Science, University of Konstanz, Germany

Abstract

Tuti Weaving is a family of algorithmic weaving patterns that we introduced in Bridges 2016. In this paper we leverage the alternating yarn color idea of Tuti Weaving to build a systematic approach for image weaving in Jacquard looms.

Introduction

Weaving design is a research area that lends itself well to mathematical study. The problem statement is simple: we want to create aesthetic weaving patterns under the physical and practical constraints of the looms and the weaving process. This problem has attracted many scholars over the time, including Grünbaum and Shephard [9], authors of the famous “Tilings and Patterns” textbook [10]; Andrew Glassner [7], a renowned figure in computer graphics; and Ralph E. Griswold [8], the late computer scientist. The Bridges conference published some articles in this area, for example [1, 3, 4, 5]. For the interested reader, sarah-marie belcastro maintains an excellent compilation of “mathematical articles on fiber arts” [11].

In our previous Bridges papers [1, 3, 4] we described different systematic approaches to produce aesthetic weaving patterns, but in all these papers we targeted the most basic weaving looms: 2- or 4-shaft dobby looms. In this paper we use some of the ideas we learned in previous papers to build a systematic design approach for more advanced weaving looms that are known as Jacquard looms.

A basic understanding of the woven fabric structure, and the weaving process, is essential to understand the constraints that we have in the weaving design process. Thus, we start with a brief discussion about the weaving process, and set our target weaving mechanism. In this discussion we provide a summary of our previous Bridges paper [3]. We then move on to describe our suggested approach.

The Weaving Process

A simple woven fabric is a uniform mesh of yarns that run along the fabric, called the “warp,” and yarns that run across, called the “weft.” At each intersection, either the warp or the weft yarn runs above, and we see the color of that yarn, while the color of the yarn running beneath is seen on the other side. The whole piece of fabric can be abstracted as a two dimensional matrix with binary entries: each row corresponds to a weft yarn, each column corresponds to a warp yarn, and each entry indicates whether the warp yarn is (0) above

*Email: abdalla_gafar@hotmail.com

or (1) beneath. For example, the weaving matrices for two common fabrics are:

[ \mathbf{S}{\text{plain}}=\left(\begin{array}[]{cccccccc}0&1&0&1&0&1&\cdots\ 1&0&1&0&1&0&\cdots\ 0&1&0&1&0&1&\cdots\ 1&0&1&0&1&0&\cdots\ 0&1&0&1&0&1&\cdots\ 1&0&1&0&1&0&\cdots\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right);,\quad\mathbf{S}{\text{twill}}=\left(\begin{array}[]{cccccccc}1&1&0&0&1&1&\cdots\ 1&0&0&1&1&0&\cdots\ 0&0&1&1&0&0&\cdots\ 0&1&1&0&0&1&\cdots\ 1&1&0&0&1&1&\cdots\ 1&0&0&1&1&0&\cdots\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right);. ]

The weaving matrix ‘S’ reflects the structure of the woven fabric, but not necessarily what is actually seen by the eye. Colors and other properties of individual yarns are superimposed on the weaving structure to determine the final look of the fabric, which could also be represented as a matrix ‘F’. Incorporating actual color information is a simple look-up process. A ‘0’ in the weaving matrix is replaced by the color of the corresponding warp yarn, and a ‘1’ is replaced by the color of the corresponding weft. Algebraically:

$\mathbf{F}[i,j]={\mathbf{Clr}}_{\mathbf{weft}}[i].\mathbf{S}[i,j]+{\mathbf{Clr}}_{\mathbf{warp}}[j].\bar{\mathbf{S}}[i,j],$ (1)

where the over-bar means taking the binary complement; that is, replace a ‘0’ by a ‘1’ and a ‘1’ by a ‘0’.

Woven fabrics are produced by a device called a loom. It weaves the fabric row by row, and for each row it raises the warp yarns designated to stay above, according to the weaving matrix, and passes the weft yarn beneath them. Weaving an arbitrary matrix requires full control over each individual warp yarn. This capability is provided by “Jacquard” looms, which are very expensive. The alternative is to raise warp yarns in groups rather than individually. A “dobby” loom uses “shafts” to control groups of warp yarns. In our previous Bridges papers [1, 3, 4] we confined ourselves to dobby looms. This time we consider Jacquard looms, but we confine our discussion to a single layer of fabric and a ‘basic’ Jacquard loom — one that offers individual lifting control over warp yarns, no more.

3.2 Image Weaving

At first glance, the yarn-by-yarn control in Jacquard looms may sound like we are free to weave an arbitrary pattern, or an image. There are, however, still some important constraints that limit this ability. First off, the color of the yarn remains fixed along the whole row or column, which drastically limits the choices of weaving design in comparison to tiling design: from a 2-dimensional matrix with arbitrary entries, to a pair of 1-dimensional vectors convolved with a binary matrix, as described in Eq (1). Secondly, we have the “floats” problem, which relates to the fabric itself rather than the weaving mechanism. In weaving terminology, a float is a loose strand of yarn. It results in a weak fabric, and the strand of yarn becomes prone to tearing and snagging. Floats are reflected as long runs of 0s or 1s in the weaving matrix; whether in rows (weft), columns (warp), or both.

That being said, the idea of weaving images is still attractive; especially monochrome (halftoned) images, since these only use two yarn colors, and we are only left with the floats problem. In “The Woven Pixel” book [12], the authors describe a modular approach towards weaving an image. That is, they assemble the weaving matrix from float-free blocks, each distinct block containing a different percentage of 1s, and therefore conveys a different tone of gray. By “float-free block” we mean a small binary matrix that contains at least a single ‘0’ and a single ‘1’ in each row and each column. The essence of such a block is that when it is replicated to make a large matrix, the longest float is shorter than the size of the block. If, however, different blocks are used together, then there is a chance that the largest float length is doubled, even if each individual block is float-free. For example, in one row a block may have a single ‘0’, located in the leftmost

Tuti Inter-Weaving

(a)

(b)

(c) Figure 1: Construction of a Tuti Pattern. (a) We start with a rasterized regular grid, where the points at the intersections of even rows and columns are set. (b) We connect pairs of these points along the rows and the columns; starting from (0) the first or (1) the second point, as indicated by the binary string $\mathbf{X}$ for the columns and $\mathbf{Y}$ for the rows. (c) How the pattern is eventually woven into a fabric.

column, and the adjacent block on the right may also have a single ‘0’, but located in the rightmost column. While it is possible to design a set of float-free blocks that avoids such a situation [12], this substantially limits the number of blocks, which, in turn, degrades the halftoning quality.

The modular approach in the Woven Pixel is based on the idea that the actually-visible pattern on the fabric coincides with the weaving matrix. That is, the warp yarn supplies one and only one color, and the weft supplies the other color. From our previous work on Tuti Weaving [3] we learned that sharing the yarn colors between the weft and the warp could be beneficial. Building on this, we will subsequently describe a different systematic approach to image weaving that can be used modularly or non-modularly. However, we stop briefly to describe Tuti Weaving.

Tuti Weaving

Tuti Weaving [3] refers to a family of ornamental binary patterns, along with a plan for weaving them. Constructing a Tuti Pattern is simple, as illustrated in Figure 1. We start from a rasterized grid, as in Figure 1(a). In each row or column that contains grid points, we connect every other pair of points, guided by a bit string, as in Figure 1(b). A ‘0’ in the bit string means that the first two points are joined, and a ‘1’ means they are disjoint.

To weave Tuti Patterns, the weaving matrix does not have to be identical to the visible pattern. The key observation is that, counting from 0, evenly-indexed rows and columns are dominated by black: $75\%$ , since these rows and columns, by construction, contain periodic repetitions of the binary string “0001”, where ‘0’ means black and ‘1’ means white. Thus, instead of using black warp and white weft (or vise-versa) we found it more constructive to split the two colors between the warp and the weft. Using alternating black and white yarns, we gained a $50\%$ degree of freedom in the weaving matrix. That is, in $50\%$ of the entries in the weaving matrix only one of the intersecting yarns (Eq (1)) matches the visible color in the pattern, and therefore that yarn has to run in the front. In the remaining $50\%$ , however, both yarns have the same color, hence there is flexibility about whether the warp or the weft yarn is on top. We exploited this degree of freedom to shape the weaving matrix so that it is weavable in the simplest looms, and the structure of Tuti Patterns automatically provides float control, as described in the referenced paper [3].

Ahmed and Deussen

Figure 2: (top-left) A Tuti interwoven image, obtained by (top-right) plain-weaving the black yarns, (bottom-left) plain-weaving the white yarns, and (bottom-right) interweaving the two colors in accordance with the underlying image. The pattern in this illustration is extracted from the right eye area in Figure 5(c).

Tuti Interweaving

Now we describe how to use the same concepts in a different way. In Tuti Weaving the black-white intersections were dictated by the prescribed Tuti Pattern, and we were free to choose which yarn is on top in all the black-black and white-white intersections. For our current problem of image weaving, we also use alternating black and white yarns in both the warp and the weft, and take advantage of the degree of freedom availed by having both colors coming along both axes. This time, however, we use this freedom in an opposite sense: we fix the white-white and black-black intersections, devoting them to solve the floats problem. Once the floats problem is excluded, we may now exercise our freedom in the remaining $50\%$ intersections to control the color in accordance with the image we would like to render.

The core concept is now simple: we plain-weave the black yarns together, plain-weave the white yarns together, and interweave the two colors in accordance with the underlying image; see Figure 2. Since each second yarn is the same color, the plain weave guarantees a maximum float length of 3.

Tuti Inter-Weaving

Figure 3: The complete palette of distinct visible $4\times 4$ blocks in modular Tuti Interweaving, showing for each block: the number, $n$ , of 1s among $b_0$ through $b_7$ in the block, the actual black and white pixels, and the target average grayscale tone. Entries are ordered by the binary number “ $b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0$ ” and we start at the top right to be consistent with the matrix form in Eq (2). Note that while the target tones range between (0) full black and (1) full white, the actual conveyable range of tones is [0.25, 0.75], obtained by dividing $n+4$ by 16. Since $n$ is between 0 and 8, inclusive, we have only 9 distinct tones in this range.

Feeding the Input Images

The aforementioned procedure simplifies the image-weaving process to halftoning. We have more than one choice to implement this. The first is a modular approach, similar to “The Woven Pixel” approach discussed earlier: we construct a set of blocks with varying percentages of 1s to convey different tones of gray. The smallest block size to capture the black-black and white-white plain weave is $4\times 4$ , which defines our block size. Within the 16 bits of every block, 8 bits are preset, and we are completely free to set the remaining 8. The visual pattern of the blocks and the corresponding weaving matrix block read:

where each $b_i$ is either ‘0’ or ‘1’. As implied by Eq (1), an entry in $\mathbf{S}$ must be complemented in $\mathbf{F}$ whenever the warp color is ‘1’ (white) and the weft color is ‘0’ (black). For both the warp and the weft in a block, the yarn colors are [0, 1, 0, 1].

The different combinations of $b_0$ through $b_7$ give us a nicely sized palette of 256 distinct blocks, as shown in Figure 3. Please note, however, that these 256 entries contain only 9 different tones, corresponding to the number of 1s among $b_0$ through $b_7$ . Specifically, the tones are 4/16 through 12/16, and they are conveyed, respectively, by $\{1,8,28,56,70,56,28,8,1\}$ distinct blocks. This mapping is connected to many topics in mathematics, including combinations and permutations, symmetries, the binomial theorem, and Pascal’s triangle.

Using the modular approach, four steps are needed to convert an image to a weavable bitmap. We convert the image into grayscale, reduce the resolution by a factor of $\frac{1}{4}\times \frac{1}{4}$ , and use our favorite image

Ahmed and Deussen

manipulation software to map the pixels to the 9 tones $\text{nicefrac}08$ through $\text{nicefrac}88$. Finally, for each pixel we choose a block with the appropriate tone from the set in Figure 3, and place it in the output bitmap. For all the tones other than 0 and 1, there is more than one possible choice of a block. We may choose randomly, or use a more sophisticated way. For example, we may use the image gradient; that is, if the neighbor pixel on the right is darker than the one on the left, we may choose a block that has more black pixels on the right. Figure 4 shows an example with random allocation of same-tone blocks.

The modular approach implies three levels of quantization: we reduce the spatial resolution to one quarter, then the brightness resolution to 9 tones, and finally halftone these tones using $4\times 4$ black and white blocks. We may instead follow a non-modular approach that directly maps to black and white, and gain more granularity in controlling the quantization errors by directly distributing black and white pixels over the 50% set-able entries in the final bitmap. One possible way to achieve this is to adapt the Floyd-Steinberg error-diffusion algorithm [6] as follows: We first adjust the gray levels to account for the 50% loss of contrast. We then diffuse the errors and compute the output pixels the normal way; however, for pixels that are preset, namely at odd-odd or even-even coordinates, we output the preset value, and adjust the errors if the preset output is different from the computed output. In the supplementary material we provide a basic implementation.

Like the modular approach, the output spatial resolution in the non-modular approach is the same as the input, but the effective resolution is only 50% of that, since 50% of the pixels are preset, which also implies a 50% global taint of gray; cf. image embroidery using amplitude-modulated line-based halftoning [2]. Nevertheless, quite decent image qualities are attainable, as demonstrated in Figure 5.

Conclusion

Thinking in a mathematical way could help people discover alternative solutions of a given problem. For example, Eq (1) has played an important role in the development of the ideas in this paper. Indeed, when you think of weaving as a procedure, you may first think of the weave structure, then the yarn colors. The equation formulation, however, immediately enables the idea that these are independent degrees of freedom that we may optimize to achieve our goals. As seen in Figure 5(c), the weaving structure could be quite dissimilar to the visible pattern; but a good understanding of how these elements interact could help us render our final image using such a seemingly random structure.

The modular and non-modular application of Tuti Interweaving are equivalent in terms of the physical properties of the fabric (floats), but the non-modular variant is evidently better in terms of the visual quality, which is not surprising, given the three-fold quantization in the modular variant. That being said, we still find the modular variant interesting for its potential future extensions.

Thanks to the anonymous reviewers for their helpful comments.

References

• [1] Abdalla G. M. Ahmed. Modular Duotone Weaving Design. In Gary Greenfield, George Hart, and Reza Sarhangi, editors, Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture, pages 27–34, Phoenix, Arizona, 2014. Tessellations Publishing. Available online at http://archive.bridgesmathart.org/2014/bridges2014-27..
• [2] Abdalla G. M. Ahmed and Oliver Deussen. Amplitude Modulated Line-Based Halftoning. In Cagatay Turkay and Tao Ruan Wan, editors, Computer Graphics and Visual Computing (CGVC). The Eurographics Association, 2016.

Tuti Inter-Weaving

(a)

(b) Figure 4: Modular application of Tuti Interweaving. (a) Input image, (b) After $25\%$ reduction of spatial resolution, and quantization to 9 levels of gray. (c) The final weavable bitmap, obtained by replacing each pixel in (b) by a block from Figure 3 that has the appropriate number of white pixels.

(c)

(a) Figure 5: Non-modular application of Tuti Interweaving on the input image in Figure 4(a). (a) The final weavable bitmap is directly obtained using a modified Floyd-Steinberg algorithm. (b) The output of the regular Floyd-Steinberg algorithm, shown for comparison. (c) The weaving matrix shown as a bitmap.

(b)

(c)

[3] Abdalla G. M. Ahmed and Oliver Deussen. Tuti weaving. In Carlo Séquin Douglas McKenna Kristóf Fenyvesi Eve Torrence, Bruce Torrence and Reza Sarhangi, editors, Proceedings of Bridges 2016: Mathematics, Music, Art, Architecture, Education, Culture, pages 49–56, Phoenix, Arizona, 2016. Tessellations Publishing. Available online at http://archive.bridgesmathart.org/2016/bridges2016-49.html.

• [4] Abdalla G.M. Ahmed. AA Weaving. In George W. Hart and Reza Sarhangi, editors, Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture, pages 263–270, Phoenix, Arizona, 2013. Tessellations Publishing. Available online at http://archive.bridgesmathart.org/2013/bridges2013-263.html.
• [5] Loe M. G. Feijs. Geometry and Computation of Houndstooth (Pied-de-poule). In Robert Bosch, Douglas McKenna, and Reza Sarhangi, editors, Proceedings of Bridges 2012: Mathematics, Music, Art, Architecture, Culture, pages 299–306, Phoenix, Arizona, USA, 2012. Tessellations Publishing.
• [6] R. W. Floyd and L. Steinberg. An Adaptive Algorithm for Spatial Grey Scale. Proceedings of the Society of Information Display, 17:75–77, 1976.
• [7] A.S. Glassner. Morphs, Mallards & Montages: Computer-Aided Imagination. Ak Peters Series. A K Peters, 2004.
• [8] Ralph E. Griswold. On-Line Digital Archive of Documents on Weaving and Related Topics. http://www.cs.arizona.edu/patterns/weaving/webdocs.html, as of Jan 27, 2016.
• [9] Branko Grünbaum and G C Shephard. Satins and Twills: An Introduction to the Geometry of Fabrics. Mathematics Magazine, 53(3):139–161, 1980.
• [10] Branko Grünbaum and G C Shephard. Tilings and Patterns. W. H. Freeman & Co., New York, NY, USA, 1986.
• [11] sarah-marie belcastro. Reference Lists: Mathematical Articles on Fiber Arts. http://www.toroidalsnark.net/mkreflist.html, as of Jan. 27, 2016.
• [12] Alice Schlein and Bhatki Ziek. The Woven Pixel: Designing for the Jacquard and Dobby Looms Using Photoshop. Greenville, SC : Bridgewater Press, 2006.