Domino Steganography

Year: 2020 Authors: Robert Bosch; Aaron Kreiner

Core claim

Domino mosaics can encode a hidden secondary image through an optimization-based partition and domino assignment scheme.

Topics

domino mosaics, steganography, optimization, image encoding

Domains

discrete optimization, linear programming, quadratic error minimization, combinatorial design, visual design, opt art, image mosaic, graphic composition

Methods

Knowlton-Knuth method, binary-variable model, Gurobi Optimizer, two-phase optimization

Media

double-nine dominos, brightness grids, Frankenstein image, block letters

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

Domino Steganography

Robert Bosch and Aaron Kreiner

Oberlin College, Oberlin, Ohio, USA; rbosch@oberlin.edu

Abstract

We present a method that, when given two target images, can be used to design plans for a domino mosaic that resembles a primary target image when all of the dominos are used, yet resembles a secondary target image when all of the horizontally-oriented dominos are removed from the mosaic. One can employ this method to hide one image inside another (i.e., to perform domino steganography).

Introduction

The Knowlton-Knuth method for designing a domino mosaic that resembles a target image has two phases ([4,5] and [2, pp. 66-78].) In the first, the target image is partitioned into domino-sized slots, and in the second, complete sets of double-nine dominos are assigned to the slots. The second phase is much more important than the first. For even if we don’t put much effort into Phase I and construct what turns out to be a low-quality partition, if we do our best work on Phase II we will end up with a domino mosaic that resembles the target image.

Figure 1: (a) A low-res rendition of Frankenstein’s monster; (b) the corresponding brightness values.

Bosch and Kreiner

The left-hand side of Figure 1 displays a low-resolution rendition of Frankenstein’s monster based on a public-domain publicity photograph of Boris Karloff. The right-hand side of Figure 1 shows the corresponding brightness values, measured on a 0-to-9, black-to-white scale (which is ideal for double-nine dominos).

Figure 2 displays output from the two phases of the Knowlton-Knuth method applied to the low-resolution Frankenstein’s monster image. The left-hand side shows an optimal partition, an optimal solution to Phase I. In Phase I, the objective is to maximize the total contrast score, which is defined to be $K={\sum }_s{k}_s$ , where the summation is taken over all slots $s$ , and $k_s$ is defined to be the contrast value for slot $s$ (the absolute value of the difference of the two numbers in slot $s$ ). For example, if $s_{\mathrm{TL}}$ refers to the slot in the top-left corner of the partition, then $k_{s_{\mathrm{TL}}}=|6-6|=0$ . And if $s_{\mathrm{TR}}$ , $s_{\mathrm{BL}}$ , and $s_{\mathrm{BR}}$ refer to the slots in the top-right, bottom-left, and bottom-right corners, respectively, then $k_{s_{\mathrm{TR}}}=|5-6|=1$ , $k_{s_{\mathrm{BL}}}=|8-4|=4$ , and $k_{s_{\mathrm{BR}}}=|8-2|=6$ . Here, the total contrast score ends up being $K=482$ .

The right-hand side of Figure 2 shows an optimal assignment of three complete sets of double-nine dominos to the slots, an optimal solution to Phase II. In Phase II, the objective is to minimize the total cost $C$ , which is defined to be the sum of the squares of the differences between the numbers on the dominos and the brightness values to which they correspond. The 6-6 domino in the top-left corner is perfectly placed, as it contributes $(6-6{)}^2+(6-6{)}^2=0$ to the total cost. The 5-6 domino in the top-right corner and the 4-8 domino in the bottom-left corner are also perfectly placed, as $(5-5{)}^2+(6-6{)}^2=0$ and $(8-8{)}^2+(4-4{)}^2=0$ . The 2-9 domino in the bottom-right corner, however, is not perfectly placed. It contributes $(9-8{)}^2+(2-2{)}^2=1$ to the total cost. Here, the total cost ends up being $C=97$ .

Figure 2: (a) An optimal partition $[K=482]$ and (b) an optimal assignment of dominos $[C=97]$ .

Figure 3 displays output from a hand-designed, suboptimal partition on Phase I and an optimal assignment of dominos to the slots on Phase II. With these particular suboptimal slots, the total contrast score $K=294$ is lower, and the optimal cost value $C=317$ is much higher. The resulting domino mosaic does resemble the target image, but not as closely as does the previous one.

Domino Steganography

Figure 3: (a) A suboptimal partition $[K=294]$ and (b) an optimal assignment of dominos $[C=317]$ .

Figure 4: The hidden image revealed by removing the horizontally oriented dominos.

Figure 4 shows what happens when we remove the horizontally oriented dominos from the lower quality mosaic: we obtain a hidden message, YOLO. Even if you are a monster built out of body parts by a mad scientist, you only live once.

In the next section, we present a mathematical optimization model [1] for domino steganography, hiding a secondary image (e.g., the word “YOLO” in block letters) inside a domino mosaic that resembles a primary image (e.g., Frankenstein’s monster).

Appendix A Mathematical Optimization Model for Domino Steganography

Let ${\beta }_{i,j}\in [0,1]$ denote the brightness of the row-$i$-column-$j$ cell of the secondary target image, where $0$ stands for black, $1$ stands for white, and intermediate values stand for various shades of gray.

The simplest version of our model employs three sets of binary variables. The first two deal with the partitioning of the image into slots. We set $h_{i,j}$ equal to $1$ if on Phase I we cover cell $(i,j)$ with a horizontal slot that also covers the cell to its right, cell $(i,j+1)$, and we set $v_{i,j}$ equal to $1$ if on Phase I we cover cell $(i,j)$ with a vertical slot that also covers the cell beneath it, cell $(i+1,j)$. To ensure that an interior cell $(i,j)$ is covered by one and only one slot, we impose the following constraint:

$h_{i,j-1}+h_{i,j}+v_{i-1,j}+v_{i,j}=1.$ (1)

A non-interior cell (one in the top or bottom rows or in the leftmost or rightmost columns) has a similar constraint but with fewer terms.

The third set of variables measures how bright cell $(i,j)$ will be after we remove all horizontal dominos. We let $x_{i,j}$ stand for the brightness of cell $(i,j)$. For an interior cell $(i,j)$ we define $x_{i,j}$ via the equation $x_{i,j}=1\cdot h_{i,j-1}+1\cdot h_{i,j}+0\cdot v_{i-1,j}+0\cdot v_{i,j}$, which simplifies to

$x_{i,j}=h_{i,j-1}+h_{i,j}.$ (2)

Equation (2) states that cell $(i,j)$ will be white if covered by a horizontal slot and black if covered by a vertical slot.

For our objective, we minimize what can be thought of as the sum of squares of all “two-by-two error” terms:

${\sum }_{i=1}^{m-1}{\sum }_{j=1}^{n-1}{\left[(x_{i,j}+x_{i,j+1}+x_{i+1,j}+x_{i+1,j+1})-({\beta }_{i,j}+{\beta }_{i,j+1}+{\beta }_{i+1,j}+{\beta }_{i+1,j+1})\right]}^2.$ (3)

If we minimize (3) subject to (1) and (2), we will obtain the Phase I partition that most closely resembles the secondary target image when all horizontal dominos are removed. In practice, we introduce an additional set of binary variables to linearize the objective function (3), and we use the Gurobi Optimizer to solve resulting discrete linear optimization problem. Figures 5-8 display two examples.

References

• [1] D. Bertsimas and J.T. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.
• [2] R. Bosch, Opt Art: From Mathematical Optimization to Visual Design, Princeton University Press, 2019.
• [3] Gurobi optimization. http://www.gurobi.com/products/gurobi-optimizer
• [4] Knowlton mosaics. http://www.knowltonmosaics.com
• [5] D.E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, 1993.

Domino Steganography

Figure 5: Frankenstein’s monster in 48 complete sets of double-nine dominos (version 1).

Bosch and Kreiner

Figure 6: The hidden image (Dracula) formed by removing the horizontally oriented dominos in version 1.

Domino Steganography

Figure 7: Frankenstein’s monster in 48 complete sets of double-nine dominos (version 2).

Bosch and Kreiner

Figure 8: The hidden image (The Mummy) formed by removing the horizontal dominos in version 2.