 # The mathematics behind the Droste effect. This article uses jsMath which requires Java.

Posted on 2008-12-26 21:20

A logarithmic image transformation

Jos Leys

Abstract : An image transformation method, first used by the artist M.C. Escher, and described by Lenstra et al. is generalized for use in a graphics program. Figure 1: Escher's "Printgallery" In 1956, Maurits Cornelis Escher completed a drawing called Print Gallery. The drawing depicts a young man looking at a print in a gallery that is deformed almost beyond recognition. There is an enigmatic white area in the center of the image. In 2003, a group of mathematicians at Leiden University, led by Prof. Hendrik Lenstra succeeded in unraveling the mathematical structure of the image. Once this structure was known, they could complete the image by filling in the famous white spot with the help of a computer algorithm. A summary of their method was published in a paper  , and received a lot of acclaim, not only in academic circles, but also in the general press.

In this article I will show how Lenstras method can be applied more generally for the transformation of images, and the generation of endless zoom animations.

The transformation consists of three stages, which will be described hereunder:

Stage 1: transformation by $\log(z)$. ( base e logarithm).

The transformation $z \mapsto \log(z)$ will transform the complex plane in a strip running from $-\infty$ to $+\infty$ along the real axis with a width equal to 2$\pi$: any point on the complex plane can be represented as $re^{i\theta}$, so $\log(z)=\log(r)+i\theta$. As $0\leq\theta\leq2\pi$,all points will be transformed to a strip of width $2\pi$.

However as $re^{i\theta}=re^{i(\theta+n2\pi)}$ for any integer $n$, any parallel strip between $n2\pi$  and  $(n+1)2\pi$ can be considered as an image of the complex plane: in other words, $\log(z)$ will transform the complex  plane into an infinite number of copies..

For our image transformation, lets consider how $\log(z)$ transforms the area between a set of concentric circles of radius $r_1$ and $r_2$. ( Fig. 2). Figure 2: Concentric circles. Figure 3: Circles transformed by $\log(z)$.

The transformation illustrated in Figs. 2 and 3 is the transformation $z\mapsto \log(\frac{z}{r_1})$ . The outer circle becomes a vertical line at $\log(\frac{r_2}{r_1})$ , and the inner circle is transformed to a vertical line at zero: we have cut the disc of Fig. 1 along line A-A, and bent it into a rectangle.

Stage 2: Rotation and scaling.

The rectangle in Fig.3 is now rotated so that its diagonal coincides with the imaginary axis, and the rectangle is shrunk so that the diagonal is equal to 2$\pi$. In transformation terms, this is equal to $z\mapsto zfe^{i\alpha}$, with  $\alpha=\arctan(\frac{\log(r_2/r_1}{2\pi})$ and $f=\cos(\alpha)$ . (Fig. 4) Figure 4: rotation and scaling

In the next stage we will do the transformation that is the inverse of the log transformation of phase 1.

Stage 3: exponentiation.

We will now transform the rectangle of Fig.4 with the transformation $z\mapsto e^z$ . This produces the image in Fig. 5:

All the sides of the rectangle of Fig. 4 are transformed into spirals. Notice that points A and A now coincide, as they were transformed from  $2\pi i$ and $0$ respectively, which both transform to $1$. Figure 5: Exponential transformation.

This concludes the basic transform.

Combining all the stages, the transformation becomes $$z\mapsto (\frac{z}{r_1})^\beta,$$ where $\beta=fe^{i\alpha}$. The original image of two concentric circles will be transformed into an identical image by the transformation $z\mapsto \frac{z}{r_2/r_1}$, so for the transformed image, an identical copy is obtained if z is divided by $(\frac{r_2}{r_1})^\beta$ .This means a scaling by  $|(\frac{r_2}{r_1})^\beta|$ and  a rotation by minus the argument of $(\frac{r_2}{r_1})^\beta$.

We now go back to stage 2. We replicate the rectangle of Fig. 4 so that it tiles the plane, and then do the stage 3 transformation again. Figure 6: Tiling Figure 7: Exponentiation of the tiling

Rectangle E in Fig. 6 is the original rectangle of Fig. 5, and is transformed by stage 3 to the area E in Fig. 7. Rectangle G and H will also be transformed to area E. Rectangle F will be transformed to area F in Fig. 7. We thus obtain an infinite number of replicas of the original image, transformed so that they tile in spiral form in a seamless fashion. All the replicas are self-similar: area E in Fig.7 can be enlarged and rotated to cover area F exactly.

The configuration of stage 2, where the rectangle is rotated and scaled so that the diagonal is vertical, and equals 2$\pi$ is not the only one possible. All possible configurations are shown in Fig.8. If the rotation is 0° or 180° and the scaling factor equals 1, the transformation will produce an infinite number of concentric copies of the original image.  In all other cases, the scaling equals $f=\cos(\alpha)$ ,and the rotation equals $\alpha$ , $\pi-\alpha$, $\pi+\alpha$, or -$\alpha$. Figure 8: Possible configurations

In summary, the transformation logic is as follows:

• Choose $r_1$ and $r_2$ ( a slight adaptation is necessary to allow circle centers different from the origin).
• Calculate $\alpha$, $f$, and $\beta$ .
• Calculate  $\beta \log(z/r_1)$ for the area between the circles, tile the resulting rectangle, and finally calculate $e^{\beta \log(z/r_1)}$ for all pixels.

The transformation was implemented in Ultrafractal , a graphics program that features user defined algorithms, and some examples follow below: Figure 9: image 1, original Figure 10: image 1, transformed Figure 11: image 2, original Figure 12: image 2, transformed Figure 13: image 3, original Figure 14: image 3, transformed

The algorithm can be adapted to allow for non-concentric circles, or even non-concentric polygons.
The area between the two squares in Fig. 15a is transformed by the log transformation into the shaded area in Fig. 15b. This area is then tiled taking into account the angle offset between the two squares. After exponentiation, Fig. 15c is obtained. With a rotation of the tiling after the log transformation, the outcome is Fig. 15d. Figure 15a Figure 15b Figure 15c Figure 15d

One can zoom in or out on the transformed images indefinitely. The value of  $\beta$ can be calculated from the size ratio of the small image vs. the large, and this allows to calculate the magnification and rotation needed to obtain an image that is identical to the start image. A limited number of frames thus suffices to obtain and endless zoom movie, provided the video file is shown in loop mode. Fig.16 shows such a zoom movie. ( A Droste effect movie)

 Figure 16

Fig.17 shows anarrangement whereby the smaller square is off-center versus the large square. We now need to calculate the fixed point of the transformation. With $C_L$ =center of large square, $C_S$=center of small square, $\theta$ = offset angle between the two squares and $m$ = ratio of the side of the small square vs. the large square, the fixed point $C_F$ is given by:

$$C_F=C_L+\frac{(C_L-C_S)}{(1-me^{i\theta})}$$

The log transform then takes the form $z\mapsto \log( \frac{(z-C_F)}{a})$ with $a$ = the shortest distance from $C_F$ to the edge of the small square.
The overall transform becomes $z\mapsto (\frac{(z-C_F)}{a})^\beta$, where $\beta=fe^{i\alpha}$, with $f=\frac{2\pi}{(2\pi-\theta)}\cos(\alpha)$, $\alpha=\arctan(\frac{\ln(m)}{2\pi})$ .
An identical copy is achieved through a scaling and rotation by the absolute value and the argument of $\Large m^{\frac{fe^{i(\alpha-\phi)}}{\cos(\phi)}}$ with $\phi=\arctan(\frac{\theta}{\log(m)})$. Figure 17a Figure 17b Figure 17c Figure 17d

The figures below show some examples. Figure 19:   LW346 by M.C. Escher Figure 20:   Transformed image Figure 21:   Original Figure 22:   Transformed

Fig. 23 shows frames from a Droste effect animation based on a vintage airline poster.      Figure 23

Finally, the transformation can also be applied to any shape. In this case, the shape in question has to be made fully transparent. One can then have the algorithm find the rim of the shape by reading the alpha channel of the image file. The alpha channel value for a transparent pixel is zero, so a simple algorithm can find the location of the rim. Figure 24 shows a sequence of images to illustrate this: The area in the picture on the wall in the image on the right is first made transparent, as to obtain the middle image. One then chooses a point in the transparent area, and a size factor. This will then create a similar area outside the transparent area (which may be rotated  versus the transparent image)., as in the image on the right.   Figure 24

This can then create the following images:   Figure 25

Below are some other examples of free-form image shapes.  Figure 26

Professor Lenstra and his team proved that the M.C. Escher Print Gallery image has a ratio $m=\frac{r_2}{r_1}=256$ . This means that the rotation angle for stage 2 is $\alpha=arctan(\frac{\log(r_2/r_1}{2\pi})$  or 41.429..degrees, and the scale factor $f=\cos(\alpha)$  or 0.749767 . .
With $\beta=fe^{i\alpha}$,  $|(\frac{r_2}{r_1})^\beta|$ = 22.5836, and the argument of $|(\frac{r_2}{r_1})^\beta|$ is 157.62559degrees, so an identical image is obtained by zooming by a factor of 22.5836and a rotation by -157.62559degrees.

It is amazing that M.C. Escher drew his Print Gallery by intuition, as he was untrained in mathematics. Yet, his image is very close to the computer generated image, based on the above algorithm. It is also known that Escher spent a very long time on this drawing. It makes one wonder what he could have done with a computer.

References

 Escher and the Droste effect. http://escherdroste.math.leidenuniv.nl/.

 B. de Smit and H. W. Lenstra Jr: The mathematical structure of Eschers Print Gallery. Notices of the AMS, Volume 50, number 4.

 Ultrafractal by Frederik Slijkerman

 The MacTutor History of Mathematics archive. (webpage)

Back to articles index 