Sunday, August 14, 2011

Approximate rotations of the square lattice

Orbits of points under approximate rotation.

Rotation of the integer lattice

Rotation of a point \((x,y)\) by angle \(\phi\) is given by the following linear transformation:

$$\begin{align} x_1 &= \cos(\phi)x-\sin(\phi)y\\ y_1 &= \sin(\phi)x+\cos(\phi)y \end{align}$$

Consider square lattice \(\mathbb{Z}^2\): the set of plane points with integer coordinates. Square lattice is a natural model for raster images, where lattice points represent pixels. It is impossible to rotate such lattice \(\mathbb{Z}^2\) by an angle other than \(\pi k/2\, k \in \mathbb{N}\), because for any other angle coordinates of the rotated points will not be integer. It is, however, possible to make an approximate rotation.

The simplest approach is the nearest-point approximation: after transforming, use the nearest point with integer coordinates. However, such rotation with nearest-point approximation is not very elegant mathematically (well, it's just my impression), because it is not a bijection. This means that sometimes, 2 different points of the original are mapped the the same target point, and some target points don't have any original. This also means that such approximate rotation is not reversible: information is lost during the transform.

How to find a more elegant, bijective approximation? Here is a way.

Shear transform

There is an affine transform that is simpler than rotation: shear. Horizontal shear is defined as:

$$ \begin{align} x_1 &= x + ky\\ y_1 &= y \end{align}$$

Here \(k=\tan \phi\) is the shear coefficient and \(\phi\) is the shear angle. Similarly to rotation, shear is unitary: it preserves the area. Indeed, shear with non-integer coefficient will not map integer lattice to itself, and some approximation is needed. Let's take a nearest-point approximation again:

Approximate shear. Note that it is a bijective mapping.

Contrary to the rotation, this approximated transform is clearly a bijection! Each source point is unambiguously mapped to one target point, and vice versa.

Rotation by shears

In the previous post, it was shown that every rotation with angle \(\phi\) can be decomposed to 3 horizontal and vertical shears with coefficients \(\tan(\phi/2), -\sin\phi, \tan(\phi/2)\) correspondingly. Let's replace ideal shears with approximated:

Composition of 3 approximate shears gives approximate rotation.

Because the resulting transform is a composition of bijections, it is a bijection too. This gives a bijective approximation to rotation of integer lattice. The total transform is described by the equations: $$\begin{align} x'&= x + \lfloor \tan(\phi/2)y\rceil \\ y_1&= y - \lfloor \sin(\phi) x'\rceil \\ x_1&= x'+ \lfloor \tan(\phi/2)y_1\rceil \end{align} $$

Here, \(\phi\) is the rotation angle, (x, y) is the original point and (x1, y1) is the rotated one; "broken" braces denote nearest integer. The resulting transformation produces a bit more "noise" compared to the simple rotation with nearest-point approximation, but it gives one-to-one correspondence between the original and rotated image.

Approximate rotation compared to exact rotation.

If the rotation angle varies continuously, transformed image will move like below. Note that the number of pixels of each color never changes - it's a consequence of the bijective nature of the transform.

Animated approximate rotation. Number of cells of each color remains constant.


Take some point and apply approximate rotation to it iteratively. If the rotation were exact, the point would move by circular orbit around the center of rotation. However, under the approximate rotation, the point would step away from the ideal circle.

Because the transform is bijective, all orbits will be either closed (cyclic) or infinite. No orbits will ever collide. Because integer rotation approximately preserves distance from point to the origin, cyclic orbit are more likely.

Orbits under the approximate rotation by \(\pi/5\).

The animation above demonstrates some orbits, obtained by iterating approximate rotation by \(\pi/5\). First part of this animation shows separate points of one of the orbits. Second part shows multiple orbits, each colored in a different color.

By painting different orbits with different colors, a colorful images resembling fractals can be generated. On these images, different orbits were painted with different colors. To make images more visually appealing, nearby orbits were colored with similar colors. The monochrome pictures are showing length of the orbit, by modulo 256. All these pictures share the invariance property: they are exactly preserved during corresponding integer rotations. In other words, they are the fixed point of the approximate rotation.

Source code to generate such images (C++).

Some additional examples (more in the gallery). Click to view full image. (Warning: big image files.)

2π/7 (2048 x 2048)
4π/9 (2048 x 2048)
5π/9 (2048 x 2048)
(2π/7)7: on each step, point was approximately rotated 7 times. (2048 x 2048)
(2π/5)5 (2048 x 2048)
2π/5, orbit length. (1024 x 1024)
π/3, orbit length (1024 x 1024)

Finite orbit conjecture

Numeric tests show that orbits are always closed, no orbit goes infinitely. Intuitively, it seems to be viable because approximate rotation nearly preserves distance from the point to the center. Thus, one can expect that some point will eventually hit its own trail. However, I don't see any way to prove it.

Thursday, August 11, 2011

Rotate image in Paint

It is hard to impress people with computer drawing of a car nowadays. However, if you do it with MS Paint, the impression could be completely different. But even the most prominent mspaint wizards will probably say that Paint can't rotate images by arbitrary angle: only rotations by 90°, 180° and 270° are supported. Rotating a picture by, for example, 30° is simply not possible, is it?

Well, with mathematics, a workaround can be found:

Rotating image (original) by 30° with 3 shears, useless but curious.

The key is the shear transform, which is supported by some reason (I guess, because it is simple to implement). If you shear a picture once, it will get distorted, not rotated. It may seem that shearing twice can solve the problem, but alas, two shears are also not enough. However, 3 finely tuned shears can produce pure rotation, with all distortions cancelled out. Here is some math.

Mathematically, both rotation and shears are linear transformations, described by the square rank 2 matrices:

$$ R(\phi) = \begin{bmatrix}\cos\phi & -\sin\phi \\ \sin\phi & \cos\phi \end{bmatrix},$$ $$ S_H(\phi) = \begin{bmatrix}1&\tan\phi\\0&1\end{bmatrix}, S_V(\phi) = \begin{bmatrix}1&0\\\tan\phi&1\end{bmatrix}.$$

Here, R is the rotation matrix, SH is the horizontal shear matrix, and SV is the vertical shear matrix, and φ is the angle of rotation or shear. Since combining transforms is equivalent to multiplying their matrices, the problem can be reformulated as: decompose rotation matrix R into matrix product of several shear matrices.

Like this:

$$ R(\phi) = S_H(\phi/2)\cdot S_V(-\arctan\sin\phi)\cdot S_H(\phi/2), $$ because it can be easily checked that: $$ \begin{bmatrix}\cos\phi & -\sin\phi \\ \sin\phi & \cos\phi \end{bmatrix} = \begin{bmatrix}1&\tan(\phi/2)\\0&1\end{bmatrix}\cdot \begin{bmatrix}1&0\\-\sin\phi&1\end{bmatrix}\cdot \begin{bmatrix}1&\tan(\phi/2)\\0&1\end{bmatrix}. $$

In other words, translating from math to English: to rotate by φ, shear horizontally by φ/2, then vertically by -arctan(sin(φ)), then again horizontally by φ/2.

Calculator for shear angles

Enter desired rotation angle and shear 3 times according to instruction. For the best result, angle should be in the interval [-45°; 45°]. Allowed interval is [-178°; 178°], but big shear angle can produce extremely large images. Since Paint can only shear by integer angle, calculator automatically rounds results. (You need to enable Java script to use it).

To rotate by °:

Further improvements

Better angle approximation

Paint only shear shears by integer angle, if measured in degrees. Values, given by the formula above, are generally non-integer and must be rounded. This causes additional distortion, result is slightly different from exact rotation.

The solution is to replace 1 shear with 2 or more consecutive shears in the same direction. The law for combining shears is: $$ \tan\alpha+\tan\beta=\tan\gamma,$$ where \(\alpha,\beta,\gamma\) are shear angles. Thus to shear by 26.565°, instead of shearing by 27° (relative error is 1.6%) one may shear by 11° and then by 17°. This will give total shear angle of 26.570°, with relative error 0.018%. That's some 87 times better! Improved algorithm for rotation by 30° is:

  • Shear horizontally by 15°
  • Vertically by -11°.
  • Vertically by -17°.
  • Again horizontally by 15°.
Using 3 and more shears can give even better approximation, however, each shear introduces distortions, caused by rounding and using to many of them may diminish effect of better approximation.

Another example: to rotate by 45°, use the following sequence of 6 shears: H 4°; H 19°; V 10°; V 28°; H 4°; H 19°. This gives overall transform very close to the true rotation, but image will be noisy because of big numbers of transforms.

Image interpolation

When shearing image, Paint uses nearest-point approximation, moving each original pixel by integer amount. This causes rotated images to become "noisy", each pixel shifted by some random value. To overcome this, stretch image before rotation (400% is just fine), then shrink it back after. Shrinking will make image smoother.