Board index » delphi » How to optimize rotation of a bitmap

How to optimize rotation of a bitmap


2007-05-30 11:13:12 PM
delphi268
Hi,
Below is my version of a procedure to rotate a bitmap through 90 degrees. It
works, but is slow compared to a similar function in the OS, and the code is
unsafe by .Net standards, because of lack of range checking on the Scanline
data. On my computer it takes about 3.2 sec to rotate a 2592x1944 bitmap
(including up-front processing). Can anyone suggest any ways to improve
speed, and/or safety? Is there a better interface to the bitmap data than
Scanline available?
procedure GetRotatedBitmap90deg(InputBitmap: TBitmap;
var OutputBitmap: TBitmap);
type
TByteArrayFixed= array[0..High(ShortInt)] of Byte;
TByteArrayPtr= ^TByteArrayFixed;
var
PixelByteCount: integer;
InputWidth, InputHeight, OutputWidth, OutputHeight: integer;
Offsets: TIntegerArray;
RowIndex, ColIndex, RowIndex1, ColIndex1: integer;
OutputRowPtr, InputRowPtr: TByteArrayPtr;
begin
SetPixelByteCount(InputBitmap, PixelByteCount);
{Determine output bitmap dimensions:}
InputWidth:= InputBitmap.Width;
InputHeight:= InputBitmap.Height;
OutputWidth:= InputHeight;
OutputHeight:= InputWidth;
{Create output bitmap:}
if (OutputBitmap<>nil) and (OutputBitmap<>InputBitmap) then
OutputBitmap.Free;
OutputBitmap:= TBitmap.Create;
OutputBitmap.Width:= OutputWidth;
OutputBitmap.Height:= OutputHeight;
OutputBitmap.PixelFormat:= InputBitmap.PixelFormat;
{Generate offset table:}
CreateOffsetLookupTable(InputWidth, InputHeight, PixelByteCount, Offsets);
{Generate output bitmap:}
for RowIndex:= 0 to OutputHeight-1 do
begin
OutputRowPtr:= OutputBitmap.ScanLine[RowIndex];
ColIndex1:= RowIndex;
for ColIndex:= 0 to OutputWidth-1 do
begin
{Transform output pixel indeces to input pixel indeces:}
RowIndex1:= InputHeight - ColIndex - 1;
{Copy pixel data from input bitmap to output bitmap:}
InputRowPtr:= InputBitmap.Scanline[RowIndex1];
Move(InputRowPtr^[Offsets[ColIndex1]],
OutputRowPtr^[Offsets[ColIndex]],
PixelByteCount);
end;
end;
end;
Thanks for any suggestions.
Enquiring Mind
 
 

Re:How to optimize rotation of a bitmap

Enquiring Mind writes:
Quote
Hi,

Below is my version of a procedure to rotate a bitmap through 90
degrees. It works, but is slow compared to a similar function in the
OS, and the code is unsafe by .Net standards, because of lack of
range checking on the Scanline data. On my computer it takes about
3.2 sec to rotate a 2592x1944 bitmap (including up-front processing).
Can anyone suggest any ways to improve speed, and/or safety? Is there
a better interface to the bitmap data than Scanline available?
[]
Thanks for any suggestions.

Enquiring Mind
Avoid the repeated calls to Scanline. Either:
- create two arrays and call scanline at the start of the operation for
each row of each bitmap, and save the pointers in the arrays
or:
- call ScanLine (0) and ScanLine (1) for each bitmap, and create a
calculated value for ScanLine from then on. Something like:
Base := ScanLine (0);
LineOffset := Integer (ScanLine (1)) - Integer (Base);
ScanLine (N) := Pointer (Integer (Base) + N * LineOffset);
Just a guide, I hope you see what I mean.
Cheers,
David
 

Re:How to optimize rotation of a bitmap

I don't have delphi code but this does a 2592 x 1944 in about 1.65 sec and
it rotates all angles.Its based on Efgs scanline rotate which is in delphi
this could use some work, lots of math in the loops
rotateScanline(Graphics::TBitmap *SrcBitmap, Graphics::TBitmap *DestBitmap,
int angle)
{ // FROM EFG'S
int DestX, XOriginal, SrcX, XRotated;
int DestY, YOriginal, SrcY, YRotated;
double Theta, cosTheta, sinTheta;
RGBTRIPLE* RowOriginal, *RowRotated;
DestBitmap->Width = SrcBitmap->Width;
DestBitmap->Height = SrcBitmap->Height;
DestBitmap->PixelFormat = pf24bit;
int CentreX = DestBitmap->Width/2;
int CentreY = DestBitmap->Height/2;
Theta = - angle * M_PI/180;
sinTheta = sin(Theta);
cosTheta = cos(Theta);
for ( DestY = DestBitmap->Height-1; DestY>= 0 ; DestY--)
{
RowRotated = (RGBTRIPLE*)DestBitmap->ScanLine[DestY];
SrcY = 2 * (DestY - CentreY) + 1;
for ( DestX = DestBitmap->Width-1; DestX>= 0; DestX--)
{
SrcX = 2 * (DestX - CentreX) + 1;
XRotated = int(SrcX * cosTheta - SrcY * sinTheta);
YRotated = int(SrcX * sinTheta + SrcY * cosTheta);
XOriginal = (XRotated - 1)/2 + CentreX;
YOriginal = (YRotated - 1)/2 + CentreY;
if ( (XOriginal>= 0) && (XOriginal <= SrcBitmap->Width-1) &&
(YOriginal>= 0) && (YOriginal <= SrcBitmap->Height-1) )
{
RowOriginal = (RGBTRIPLE*)SrcBitmap->ScanLine[YOriginal];
RowRotated[DestX] = RowOriginal[XOriginal];
}
else
{
RowRotated[DestX].rgbtBlue = 255; // assign "corner" color
RowRotated[DestX].rgbtGreen = 0;
RowRotated[DestX].rgbtRed = 0;
}
}
}
} //====================
 

Re:How to optimize rotation of a bitmap

change this
// SrcY = 2 * (DestY - CentreY) + 1;
to
SrcY =(DestY - CentreY)<< + 1; //this shaves of 30-40 ms on a 2500 x
1900
and this
// SrcX = 2 * (DestX - CentreX) + 1;
to
SrcX = (DestX - CentreX)<< + 1; //this shaves of 30-40 ms
and these two
// XOriginal = (XRotated - 1)/2 + CentreX;
// YOriginal = (YRotated - 1)/2 + CentreY;
to
XOriginal = (XRotated - 1)>>+ CentreX;
YOriginal = (YRotated - 1)>>+ CentreY;
and it will do the same Image in under .8 sec !
 

Re:How to optimize rotation of a bitmap

Quote
// SrcY = 2 * (DestY - CentreY) + 1;

to
SrcY =(DestY - CentreY)<< + 1;
The Delphi optimizer replaces "2 * x" with "x shl 1" automatically
Quote
// XOriginal = (XRotated - 1)/2 + CentreX;
// YOriginal = (YRotated - 1)/2 + CentreY;

to
XOriginal = (XRotated - 1)>>+ CentreX;
YOriginal = (YRotated - 1)>>+ CentreY;
as well as "x div 2" with "x shr 1" (well, in fact it is SAR instead
IIRC). So when translating the code to Delphi it should be fine anyway.
--
Jens Gruschel
www.pegtop.net
 

Re:How to optimize rotation of a bitmap

the first two changes are valid
but the last two shrink the image so it makes it faster HA HA but the 1.6
sec is valid. I should've tried it first.
all compiler optimizarions are turned off for this testing
"tom" <XXXX@XXXXX.COM>writes
Quote
change this
// SrcY = 2 * (DestY - CentreY) + 1;

to
SrcY =(DestY - CentreY)<< + 1; //this shaves of 30-40 ms on a 2500 x
1900

and this
// SrcX = 2 * (DestX - CentreX) + 1;

to
SrcX = (DestX - CentreX)<< + 1; //this shaves of 30-40 ms

and these two
// XOriginal = (XRotated - 1)/2 + CentreX;
// YOriginal = (YRotated - 1)/2 + CentreY;

to
XOriginal = (XRotated - 1)>>+ CentreX;
YOriginal = (YRotated - 1)>>+ CentreY;

and it will do the same Image in under .8 sec !

 

Re:How to optimize rotation of a bitmap

"Enquiring Mind" <XXXX@XXXXX.COM>writes
Quote
(including up-front processing). Can anyone suggest any ways to improve
speed, and/or safety? Is there a better interface to the bitmap data than
Scanline available?
If you are _just_ trying to draw the bitmap rotated, you can also use the
various gdi transform functions. That wont work obviously if what you are
after is the actual rotated bitmap. But it is pretty fast.
 

Re:How to optimize rotation of a bitmap

With the two units provided in the ZIP download later on.. it goes like
this
RotateBitmap90Deg(Src, Dst: TBitmap);
// Assumes both Src and Dst are initialized
var
SI, DI: TsdMapIterator;
S, D: Pbyte;
Stride: integer;
begin
Dst.Width := Src.Height;
Dst.Height := Src.Width;
SI := TsdMapIterator.Create;
DI := TsdMapIterator.Create;
try
GetBitmapIterator(Src, SI);
GetBitmapIterator(Dst, DI);
if SI.CellStride <>DI.CellStride then
raise Exception.Create('incompatible pixel formats');
Stride := SI.CellStride;
SI.Method := imReaderYInv;
DI.Method := imReaderX;
S := SI.First;
D := DI.First;
while S <>nil do
begin
Move(S^, D^, Stride);
S := SI.Next;
D := DI.Next;
end;
finally
SI.Free;
DI.Free;
end;
end;
It works for any kind of bitmap, as long as the pixelformats of Src and Dst
are compatible. It rotates 90 deg clockwise. Just exchange SI.Method and
DI.Method to get counter-clockwise rotation.
On my machine it takes ~ 200msec to rotate a 2000 x 3000 full color (24bit)
bitmap.
The two units you need (very small):
www.simdesign.nl/download/bitmapiterators.zip
Hope that helps,
Nils Haeck
www.simdesign.nl
"Enquiring Mind" <XXXX@XXXXX.COM>schreef in bericht
Quote
Hi,

Below is my version of a procedure to rotate a bitmap through 90 degrees.
It works, but is slow compared to a similar function in the OS, and the
code is unsafe by .Net standards, because of lack of range checking on the
Scanline data. On my computer it takes about 3.2 sec to rotate a 2592x1944
bitmap (including up-front processing). Can anyone suggest any ways to
improve speed, and/or safety? Is there a better interface to the bitmap
data than Scanline available?


procedure GetRotatedBitmap90deg(InputBitmap: TBitmap;
var OutputBitmap: TBitmap);
type
TByteArrayFixed= array[0..High(ShortInt)] of Byte;
TByteArrayPtr= ^TByteArrayFixed;
var
PixelByteCount: integer;
InputWidth, InputHeight, OutputWidth, OutputHeight: integer;
Offsets: TIntegerArray;
RowIndex, ColIndex, RowIndex1, ColIndex1: integer;
OutputRowPtr, InputRowPtr: TByteArrayPtr;
begin
SetPixelByteCount(InputBitmap, PixelByteCount);
{Determine output bitmap dimensions:}
InputWidth:= InputBitmap.Width;
InputHeight:= InputBitmap.Height;
OutputWidth:= InputHeight;
OutputHeight:= InputWidth;
{Create output bitmap:}
if (OutputBitmap<>nil) and (OutputBitmap<>InputBitmap) then
OutputBitmap.Free;
OutputBitmap:= TBitmap.Create;
OutputBitmap.Width:= OutputWidth;
OutputBitmap.Height:= OutputHeight;
OutputBitmap.PixelFormat:= InputBitmap.PixelFormat;
{Generate offset table:}
CreateOffsetLookupTable(InputWidth, InputHeight, PixelByteCount,
Offsets);
{Generate output bitmap:}
for RowIndex:= 0 to OutputHeight-1 do
begin
OutputRowPtr:= OutputBitmap.ScanLine[RowIndex];
ColIndex1:= RowIndex;
for ColIndex:= 0 to OutputWidth-1 do
begin
{Transform output pixel indeces to input pixel indeces:}
RowIndex1:= InputHeight - ColIndex - 1;
{Copy pixel data from input bitmap to output bitmap:}
InputRowPtr:= InputBitmap.Scanline[RowIndex1];
Move(InputRowPtr^[Offsets[ColIndex1]],
OutputRowPtr^[Offsets[ColIndex]],
PixelByteCount);
end;
end;
end;

Thanks for any suggestions.

Enquiring Mind


 

Re:How to optimize rotation of a bitmap

I should mention.. it only works for pixel formats:
pf8bit, pf15bit, pf16bit, pf24bit, pf32bit
the pfDevice, pfCustom, pf1bit and pf4bit are not supported, because in that
case the cell either has unknown size, or size smaller than one byte.
Nils
 

Re:How to optimize rotation of a bitmap

"David J Taylor" <XXXX@XXXXX.COM>
writes news:465d97b5$XXXX@XXXXX.COM...
Thanks for the useful suggestions.
Regarding the avoidance of unnecessary repeated evaluation of the same
scanline function values:
1. The scanline function in the outer loop is called only once for each row,
therefore is not called more often than necessary.
2. The scanline function in the inner loop is re-evaluated for each row, and
as such is called more often than necessary. However to get the pointers
from a look-up array seems to me to involve as much work as the calculating
the offset address using scanline.
Quote
- call ScanLine (0) and ScanLine (1) for each bitmap, and create a
calculated value for ScanLine from then on. Something like:

Base := ScanLine (0);
LineOffset := Integer (ScanLine (1)) - Integer (Base);
ScanLine (N) := Pointer (Integer (Base) + N * LineOffset);

Shouldn't the Scanline procedure do the same to calculate the scanline
pointer, only more efficiently, because possibly written in assembly
language? Or is it the procedure call rather than the address calculation
that's the time consuming element?
For maximum efficiency, perhapse the best approach is to eliminate the
Scanline(n) calls altogether, and calculate the offsets of each pixel from
the Base address using offset values that are incremented in each loop,
thereby avoiding multiplications such as N * LineOffset.
Regards,
Enquiring Mind
 

Re:How to optimize rotation of a bitmap

"tom" <XXXX@XXXXX.COM>writes
Quote
I don't have delphi code but this does a 2592 x 1944 in about 1.65 sec and
it rotates all angles.Its based on Efgs scanline rotate which is in delphi
this could use some work, lots of math in the loops


I did have a look at the EFG implementation, but I decided not to use it for
the following reasons:
1) It assumes each pixel has a 24-bit bit format. It is therefore not
general enough to handle any type of bitmap, which can feature a variety of
different pixel sizes.
2) It does a non 90 degree rotation which involves time-consuming
evaluation of trigonometric functions which add to the execution time! These
should be avoided if a 90 degree rotation is all that is required.
3) Time consuming floating point expressions must be evaluated to determine
the rotated pixel coordinates, followed by truncation/rounding conversions
to integers.
4) It includes some Boolean expressions needed to clip the corners of the
output image. These also add to the execution time, and are not needed for a
90 degree rotation.
Given the above, if your routine ran in half the time that mine did, I can
only conclude that either your computer is more than twice as fast as mine,
or the compiler that you use produces very more more efficient code than the
Delphi 7 compiler!
Regards,
Enquiring Mind
 

Re:How to optimize rotation of a bitmap

"Nils Haeck" <XXXX@XXXXX.COM>writes
Quote

It works for any kind of bitmap, as long as the pixelformats of Src and
Dst
are compatible. It rotates 90 deg clockwise. Just exchange SI.Method and
DI.Method to get counter-clockwise rotation.

On my machine it takes ~ 200msec to rotate a 2000 x 3000 full color
(24bit)
bitmap.

The two units you need (very small):
www.simdesign.nl/download/bitmapiterators.zip

Hope that helps,

Thanks for that. It sounds very promising. I can see that using the Next
methods to iterate through the bitmap pixels should be faster than the code
I posted, because they presumably just increment the current pointer by an
appropriate increment.
Enquiring Mind
 

Re:How to optimize rotation of a bitmap

Quote
Thanks for that. It sounds very promising. I can see that using the Next
methods to iterate through the bitmap pixels should be faster than the
code I posted, because they presumably just increment the current pointer
by an appropriate increment.
Yes, try it out :) The iterator is a very powerful class, be it small. The
code indeed just evaluates ScanLine twice, to calculate what I call
"ScanStride", the distance between ScanLine[1] and ScanLine[0]. The ScanLine
property for some reason is very slow, even if you only do it once per row.
Then, the pointers just get incremented, so no multiplications.
Third, there's no logic whatsoever for "other than 90 degree" rotations,
just sets the bitmap sizes correcty depending if Width/Height must be
interchanged or not, then fires off copying triplets (in case of 24bit).
I've now also posted the exe test program (which also has some other
functions), just use the same link to download.
www.simdesign.nl/download/bitmapiterators.zip
Nils
 

Re:How to optimize rotation of a bitmap

Enquiring Mind writes:
[]
Quote
Regarding the avoidance of unnecessary repeated evaluation of the same
scanline function values:
1. The scanline function in the outer loop is called only once for
each row, therefore is not called more often than necessary.
That's fine, then.
Quote
2. The scanline function in the inner loop is re-evaluated for each
row, and as such is called more often than necessary. However to get
the pointers from a look-up array seems to me to involve as much work
as the calculating the offset address using scanline.
Well, except that the lookup array is called for every pixel, and doing an
indexed lookup is a whole lot faster than ScanLine.
Quote
>- call ScanLine (0) and ScanLine (1) for each bitmap, and create a
>calculated value for ScanLine from then on. Something like:
>
>Base := ScanLine (0);
>LineOffset := Integer (ScanLine (1)) - Integer (Base);
>ScanLine (N) := Pointer (Integer (Base) + N * LineOffset);
>
Shouldn't the Scanline procedure do the same to calculate the scanline
pointer, only more efficiently, because possibly written in assembly
language? Or is it the procedure call rather than the address
calculation that is the time consuming element?

For maximum efficiency, perhapse the best approach is to eliminate the
Scanline(n) calls altogether, and calculate the offsets of each pixel
from the Base address using offset values that are incremented in
each loop, thereby avoiding multiplications such as N * LineOffset.

Regards,

Enquiring Mind
Why not take a look at the source code for ScanLine to see how it works?
It's the internal calculations rather than the procedure call.
Yes, an increment is another way, but I find the table lookup very fast.
In any of these optimisations, getting the algorithm right is, perhaps,
90% of the effort. You may keep shaving a cycle or two off subsequently,
but once one part of the program is optimised another part often becomes
the bottleneck. it is easy to spend far too much time optimising, for
relatively little gain.
Cheers,
David
 

Re:How to optimize rotation of a bitmap

Nils Haeck writes:
Quote
The ScanLine property for some reason is very slow,
Part of the reason is the fact that GetScanLine checks (and guarantees) the
'contract' - that there is a DIB, that the GDI cache is flushed, etc. etc.
Another part is that BytesPerScanline is a function that calculates the
value from the Bitmap header, not a constant or variable.
There are probably good reasons it is written like this, maybe the 'copy on
write' logic that is hidden deep down in the bitmap handling. If you want to
modify a bitmap that has just been assigned from another bitmap, they are
still sharing the same bitmap handle - do you really want to modify both of
them? No, probably not...
The Borland VCL designer probably thought 'better safe than sorry' when
implementing this system. This means that we can write faster code under
certain assumptions, we're adding restrictions to the contract when we use
saved values of Scanline instead of calling it for every use, when using
constants for BytesPerScanLine, and so on. For tight loops it will certainly
work, but don't rely on one call to Scanline at the start of the application
to be valid until the final application end.
--
Anders Isaksson, Sweden
BlockCAD: web.telia.com/~u16122508/proglego.htm
Gallery: web.telia.com/~u16122508/gallery/index.htm