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: M.C. Escher’s “Print Gallery”[1]

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[2]. 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[3] , 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 zlog(z) will transform the complex plane into a strip running from – to + along the real axis with a width equal to 2: any point on the complex plane can be represented as , so . As , all points will be transformed to a strip of width 2.

However as, for any integer n, any parallel strip between and 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₁and r₂. ( Fig. 2).

Figure 2: Concentric circles

Figure 3: Circles transformed by log(z)

The transformation illustrated in Figs. 2 and 3 is the transformation . The outer circle becomes a vertical line at , 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. In transformation terms, this is equal to , with and . (Fig. 4)

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

Figure 4: Rotation and scaling

Stage 3: Exponentiation

We will now transform the rectangle of Fig.4 with the transformation . This produces the image in Fig. 5:

Figure 5: Exponential transformation.

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 and 0 respectively, which both transform to 1.

This concludes the basic transform.

Combining all stages, the transformation becomes , where .

The original image of two concentric circles will be transformed into an identical image by the transformation , so for the transformed image, an identical copy is obtained if z is divided by .This means a scaling by and a rotation by minus the argument of

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 is not the only one possible. All possible configurations are shown in Fig.8.

Figure 8: Possible configurations.

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 ,and the rotation equals , 180°-, 180°+, or -.

In summary, the transformation logic is as follows:

Choose r₁ and r_{2 (}a slight adaptation is necessary to allow circle centers different from the origin)
Calculate , , and .
Calculate for the area between the circles, tile the resulting rectangle, and finally calculate for all pixels.

The transformation was implemented in Ultrafractal[4], 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

One can zoom in or out on the transformed images indefinitely. The value of 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.15 shows frames from such a zoom movie. ( A “Droste effect” movie)

Figure 15:

Frames from an animation

The algorithm can be adapted to allow for non-concentric circles, or even non-concentric polygons.

The area between the two squares in Fig. 16a is transformed by the log transformation into the shaded area in Fig. 16b. This area is then tiled taking into account the angle offset between the two squares. After exponentiation, Fig. 16c is obtained. With a rotation of the tiling after the log transformation, the outcome is Fig. 16d.

Figure 16a

Figure 16b

Figure 16c

Figure 16d

Fig.17 shows an arrangement 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, = offset angle between the two squares and m= ratio of the side of the small square vs. the large square, the fixed point is given by:

The log transform then takes the form log( (z-C_F)/a) with a= the shortest distance from C_F to the edge of the small square.

The overall transform becomes , where , with , .

An identical copy is achieved through a scaling and rotation by the absolute value and the argument of , with

Figure 17a

Figure 17b

Figure 17c

Figure 17d

The procedure is similar for rectangles, or other polygons. The figures below show some examples.

Figure 19 “LW346” by M.C. Escher[5]

Figure 20 Transformed image

Figure 21 Original

Figure 22 Transformed

Figure 23 Original, by Salvador Dali

Figure 24 Transformed

Fig. 25 shows frames from a ‘Droste effect’ animation based on a vintage airline poster.

Figure 25

Professor Lenstra and his team proved that the M.C. Escher Print Gallery image has a ratio . This means that the rotation angle for stage 2 is or 41.429..…degrees, and the scale factor or 0.749767… . .

With , = 22.5836…, and the argument of 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”.[6] 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