Image Processing
RotateScanline  Lab Report

Chinese Translation by Hector Xiang

Rotate Bitmap Any Angle Using Scanline Property

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.

Mathematical Background

RotateAxes.gif (2571 bytes)
(See RotateAxes.ZIP for a simple Delphi project to create this diagram.)

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:

RotateAxes1.gif (1527 bytes)

Recall the angle-sum relations:

AngleAddition.gif (1526 bytes)

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

RotateAxes2.gif (1245 bytes)

These two equations can be express in matrix form as follows:

RotateAxes3.gif (1515 bytes)

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

  1. The origin is translated to (xcenter, ycenter).  

  2. The rotation described above is performed.

  3. The rotated points are translated back to compensate for the original translation of the origin.

This can be summarized in matrix form:

TranslateAndRotateAxes.gif (1855 bytes)

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.

Materials and Equipment

Software Requirements
Windows 95/98/NT
Delphi 3 or 4 (to recompile)
RotateScanline.EXE
BMP, JPG, ICO, WMF or EMF file (GIFs could be used if you have a TGIFImage component. See below.)

Hardware Requirements
VGA display in high color or true color mode

Procedure

  1. Double click on the RotateScanline.EXE icon to start the program.
  2. Press the Load Image button and select a bitmap, such as flower1.bmp. By default, an image is stretched and rotated 30 degrees clockwise with the axis of rotation through the center of the image. (The image above was rotated 30.55 degrees.)
  3. If desired, check the Stretch checkbox so the image fits in the available TImage objects. For a 1-to-1 pixel mapping between the TBitmap and the TImage, uncheck the Stretch checkbox.
  4. Use the Rotation Angle spinbox to change the angle of rotation, or the (I, J) spinboxes to change the center of the rotation axis.

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.

For other details about image rotation, including multipass rotation, see section 8.5 in High Performance Computer Imaging.

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 at www.melander.dk/delphi/gifimage . Change the conditional compilation value from NOGIF to GIF and recompile once TGIFImage is installed. (You are responsible for any licensing with Unisys.)

Comments from Brien Smith about how not to clip the corners (11 Nov 1998).
A simpler approach to avoid clipping corners suggested by Didier Gombert (27 Nov 1999).

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)

Additional links to Bitmap Rotation techniques can be found on the Delphi Graphics Algorithms page.

Also see:
-Turn, Turn, Turn:  Using the Graphics Class to Rotate Images
http://msdn.microsoft.com/library/periodic/period99/turn.htm

- HowTo: Display a Bitmap into a Rotated or Non-rectangular Area
http://support.microsoft.com/support/kb/articles/Q186/5/89.ASP

- A Quick Spin on NT:  www.delphizine.com/features/1999/01/di199901rv_f/di199901rv_f.asp  (subscribers only)

- Jack Sudarev's RotateBitmap procedure that performs antialiasing.

- Rotate a bitmap image, http://codeguru.earthweb.com/bitmap/rotate_bitmap.shtml (C code, all pixel formats)

See other "Bitmap Rotation" links on Delphi Graphics Image Processing page.

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

Downloads
Delphi 3/4/5 Source and EXE (196 KB):  RotateScanline.ZIP 

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 

Version of program for use with pf8bit BMP files including palettes:  RotateScanlinePf8bit.ZIP

Darren Gallagher's Borland C++ Builder Source Code (7 KB):
DarrenGallagher_Builder_RotateScanline.ZIP  

24-bit color BMP test image:
Parrots.ZIP (200 KB)

8-bit color BMP test image:
Deer.ZIP (28 KB)

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.


Update Notes
The October 1998 update contains the following features:

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


Updated 10 Jun 2003


since 1 Nov 1998