This article includes a fast implementation of 2:1 image shrink algorithm.
Introduction
This article offers a simple and fast, practical implementation of 2:1 image shrink algorithm.
2:1 image shrink is used in very specific cases, but it does a nice job.
Background
Image processing is always an expensive job. When one needs to show a scaled picture, it is always better to use GPU for rendering (OpenGL, DirectX). But using GPU is not always possible and it is good to have an alternative.
The high-quality image resize (enlarge/shrink) is extremely CPU demanding, especially on large images. In addition, sometimes it is required to do the processing multiple times. To relieve this, there are different tricks that could be applied. If a picture has to be shrunk (scaled down), a trick that is similar to mip-maps could be applied. Such case is if we want to shrink a picture more than twice (destination size is less than half of the original), we could speed up the whole process by applying half-shrink prior to actual scale. 2:1 scale-down is very fast, due to simplest algorithm that uses less computations.
For example, if we have image 1920x1024 and need to shrink it to 500x281, we have to execute code like this:
shrink( imageDst, imageSrc )
But we could optimize this by pre-shrink 2:1 like this:
shrinkHalf( imageHalf, imageSrc );
shrink( imaheDst, imageHalf );
In one of my projects, when I had to scale the image of 3 monitors to generate a preview, the result was:
Scale: 46 ms
ShrinkHalf + Scale: 25 ms
ShrinkHalf + ShrinkHalf + Scale: 16 ms
Which means, the trick applied once, causes %36 speedup.
And the trick applied twice, causes %66 speedup.
The demo application has two buttons:
- Shrink 2:1 - performs image shrink of the whole source image
- Shrink 2:1 rnd - performs image shrink of random rectangle from the source image
On the left, there is the original image. On the right, there is the original image in grayscale and the shrunk image (or shrunk part) in color.
Shrinking only parts of the image is appropriate when the original was updated and there is a need to update the shrunk copy too. This could save a lot of CPU and time for processing.
2:1 of the Whole Picture
2:1 of Random Rectangle
Using the Code
There is a pair of files in the project: ShrinkHalf.h and ShrinkHalf.cpp
To use the code, you only need to put these files into your project and include the ShrinkHalf.h file.
These files contain the implementations of all algorithms.
shinkHalf function has the following arguments:
BYTE* dstPixels
- destination array of pixels in format 24 bit BGR (b,g,r, b,g,r, ..., b,g,r) BYTE* srcPixels
- source array of pixels in format 24 bit BGR (b,g,r, b,g,r, ..., b,g,r) int srcWidth
- width in pixels of the image int srcHeight
- height in pixels of the image
So, in order to use the functions, you should do the following:
#include "ShrinkHalf.h"
...
shrinkHalf( dstPixels, srcPixels, srcWidth, srcHeight );
Note that, the destination does not provide dimensions, as they are calculated from the source sizes.
Here are the functions available:
void shrinkHalf ( BYTE* target, const BYTE* source, int srcWidth, int srcHeight );
void shrinkHalfPart( BYTE* target, const BYTE* source, int srcWidth,
int srcHeight, int x1, int y1, int x2, int y2 );
The first function performs 2:1 shrink of the whole image.
The second function performs 2:1 shrink of the specified rectangle from the source image, calculating the respective rectangle for the destination image.
If you use this, you should pay attention that you could need a correction of +1/-1 of the source rectangle points, because of the integer roundup.
This is very useful if there are intensive updates that should be applied (for example, video rendering).
Points of Interest
In the shrinkHalf
function, there is a commented code that works, but I preferred to leave the internal call to shrinkHalfPart
.
void shrinkHalf( BYTE* target, const BYTE* source, int srcWidth, int srcHeight )
{
shrinkHalfPart( target, source, srcWidth,
srcHeight, 0, 0, srcWidth-1, srcHeight-1 );
}
So, if someone wants a clean and simpler function, thou could remove the first line that calls shrinkHalfPart
and uncomment the commented code.
History
- 8th April, 2020: Initial version