efg's Image Processing -- Rotate Scanline Lab Report

Purpose
The purpose of this program, RotateScanline.EXE, is to show how to rotate a bitmap any angle using Scanline property introduced in Delphi 3.

The point P can be expressed in either (x,y) coordinate space or (x',y') coordinate space, where the x'-y' axes are rotated an angle alpha from the x-y axes:

Using the angle-sum relations in the expressions for x and y, the equations for rotation of axes are:

These equations only apply to a rotation about the origin, O. If the center of rotation is about some other point, (x_center, y_center), three steps are then needed:

Note that in computer graphics the above operations are usually performed with "homogeneous coordinates," which are described in texts such as Computer Graphics -- Principles and Practice by Foley, et al. Because generality isn't needed for image rotation, homogeneous coordinates usually are not used.

Discussion
If one attempts to rotate a bitmap in the "forward" direction by selection Pixel (i, j) and rotating it into new Pixel (i',j'), you will discover "holes" in the rotated image due to the discrete space and integer math. To avoid this problem, use a "reverse" method. Consider each Pixel (i, j) in the rotated image, and lookup where this pixel was in the original image. This technique avoid any "holes" in the rotated image.

This version of the Rotate Scanline program has three methods of rotation that can be selected via a Combobox: Simple, Center of Pixel 1, and Center of Pixel 2. These are implemented in the code in Functions RotateBitmapMethodN.

The "Simple" method implements the math nearly exactly as described above in the Mathematical Background. Here's the relevant code:

CONST
MaxPixelCount = 32768;

TYPE
TRGBTripleArray = ARRAY[0..MaxPixelCount-1] OF TRGBTriple;
pRGBTripleArray = ^TRGBTripleArray;
...

// "Simple" approach. For pixel (i,j), use "reverse" rotation to find
// where the rotated pixel must have been before the rotation.
// Don't bother with center of pixel adjustment.
// Assumes input BitmapOriginal has PixelFormat = pf24bit.
FUNCTION RotateBitmapMethod1 (CONST BitmapOriginal: TBitmap;
CONST iRotationAxis, jRotationAxis: INTEGER;
CONST AngleOfRotation: DOUBLE {radians} ): TBitmap;

VAR
    cosTheta   : EXTENDED;
    i          : INTEGER;
    iOriginal  : INTEGER;
    iPrime     : INTEGER;
    j          : INTEGER;
    jOriginal  : INTEGER;
    jPrime     : INTEGER;
    RowOriginal: pRGBTripleArray;
    RowRotated : pRGBTRipleArray;
    sinTheta   : EXTENDED;
BEGIN
// The size of BitmapRotated is the same as BitmapOriginal. PixelFormat
// must also match since 24-bit GBR triplets are assumed in ScanLine.
RESULT := TBitmap.Create;
RESULT.Width := BitmapOriginal.Width;
RESULT.Height := BitmapOriginal.Height;
RESULT.PixelFormat := pf24bit; // Force this

// Get SIN and COS in single call from math library
sincos(AngleOfRotation, sinTheta, cosTheta);

// If no math library, then use this:
// sinTheta := SIN(AngleOfRotation);
// cosTheta := COS(AngleOfRotation);

// Step through each row of rotated image.
FOR j := RESULT.Height-1 DOWNTO 0 DO
BEGIN
    RowRotated := RESULT.Scanline[j];
    jPrime := j - jRotationAxis;

    FOR i := RESULT.Width-1 DOWNTO 0 DO
    BEGIN
      iPrime := i - iRotationAxis;
      iOriginal := iRotationAxis + ROUND(iPrime * CosTheta - jPrime * sinTheta);
      jOriginal := jRotationAxis + ROUND(iPrime * sinTheta + jPrime * cosTheta);

      // Make sure (iOriginal, jOriginal) is in BitmapOriginal. If not,
      // assign blue color to corner points.
      IF (iOriginal >= 0) AND (iOriginal <= BitmapOriginal.Width-1) AND
          (jOriginal >= 0) AND (jOriginal <= BitmapOriginal.Height-1)
      THEN BEGIN
        // Assign pixel from rotated space to current pixel in BitmapRotated
        RowOriginal := BitmapOriginal.Scanline[jOriginal];
        RowRotated[i] := RowOriginal[iOriginal]
      END
      ELSE BEGIN
        RowRotated[i].rgbtBlue := 255; // assign "corner" color
        RowRotated[i].rgbtGreen := 0;
        RowRotated[i].rgbtRed := 0
     END

    END
END
END {RotateBitmapMethod1};

In the original version of this program, I went to great length to use the center of the pixel as the "location" of the pixel. Method 2 uses location (i + 0.5, j + 0.5) for pixel (i, j) and then does the "reverse" lookup as described above. Method 3 was like Method 2 but attempted to used more integer math. If you multiply (i + 0.5, j + 0.5) by 2, you can work in space (2i + 1, 2j + 1). Method 3 effectively is a more complicated way to implement Method 2 -- unfortunately Method 3 was the way Rotate ScanLine was implemented. This confused several people, so I restructured this Lab to show the "Simple" method. The timing differences between Methods 1-3 doesn't seem to be that significant.

Aliasing effects of rotating a 24-bit color bitmap usually aren't noticed for a "real world" image but may be noticed if rotating a bitmap with lines or sharp edges. To reduce such aliasing, a bilinear interpolation would be an improvement of the existing algorithm that just picks the closest pixel (but it'll be slower).

For even a better way to rotate a bitmap (but it'll be somewhat slower), see "High Accuracy Rotation of Images," in Computer Vision, Graphics and Image Processing, Vol. 54, No. 4, July 1992, pp. 340-344.

In Windows NT the plgblt (parallelogram block transfer) API call can be used for bitmap rotation if the RC_BITBLT is supported by a device. See the article "A quick spin on NT" by Robert Vivrette in the Jan. 99 Delphi Informant for a plgblt example.

For GIF support you will need a GIF component such as TGIFImage from Anders Melander. Change the conditional compilation value from NOGIF to GIF and recompile once TGIFImage is installed. (You are responsible for any licensing with Unisys.)

Jim Hargis' has an improved RotateBitmap that
- handles all the bitmap formats (auto-translates pf1bit, pf4 bit to pf8bit; all others are unchanged).
- no corner clipping.
- background fill is transparent.
JimHargis_RotateBitmap.ZIP (17 Jan 2000)

Conclusions
Rotating an image using the TCanvas Scanline property is far faster than using the Pixels property. A 640 x 480 pixel x 24-bit color bitmap can be rotated any angle in about a second on a 166 MHz Pentium.

The technique shown here with Scanline is only for a 24-bit color bitmap. Similar, but different, code is needed for other PixelFormats.

Keywords
Scanline, Bitmap Rotation, pf24Bit PixelFormat, pRGBTripleArray, TRGBTRipleArray, TRGBTriple, GetTickCount, BMP, JPG, GIF, EMF, WMF

RotateBitmap Procedure Highly Optimized -- Now 400% Faster -- by John O'Harrow
1. Local variables used to reduce calculation time within loops
2. All references to Scanline property within loops removed

Noteworthy
In a February 1998 E-mail to Stefan Akerwall in Sweden, I told him that I had to E-mail him a solution of how to rotate a bitmap since I didn't have a web site. Stefan gave me web space at www.infomaster.net/external/efg for telling him how to rotate a bitmap and that was the beginning of efg's Computer Lab. In November 1998, the Computer Lab moved from Stockholm, Sweden to the USA. An early version of this project was the beginning of the Computer Lab on the Web.

The March 1999 update added the Mathematical Background section and introduced Methods 1-3 to rotate a bitmap.

		RotateScanline		Lab Report
Chinese Translation by Hector Xiang

Rotate Bitmap Any Angle Using Scanline Property