# What is the algorithm to copy a region of one bitmap, into a region in another?

In my project (and I am sure many others), I need to copy a subset (R2) of one bitmap image (R1), into a region (R3) in another, where the destination region can be any size (stretching and scaling where necessary).

I am sure this is a solved problem but I cannot find any examples; what is the most straightforward algorithm for performing this operation? (Linear interpolation would be sufficient for filling in the pixels when the source is scaled upwards, if that is the quickest (computationally) method)

-

Here's C-like pseudocode. You can figure how to handle the edge cases (e.g. clipping, mirroring, etc). I'll leave it to you to also figure out how to make this use integer or fixed point math if performance is an issue.

``````struct {
bitmap bmp;
float x, y, width, height;
} xfer_param;

scaled_xfer(xfer_param src, xfer_param det)
{
float src_dx = dst.width / src.width;
float src_dy = dst.height / src.height;
float src_maxx = src.x + src.width;
float src_maxy = src.y + src.height;
float dst_maxx = dst.x + dst.width;
float dst_maxy = dst.y + dst.height;
float src_cury = src.y;

for (float y = dst.y; y < dst_maxy; y++)
{
float src_curx = src.x;
for (float x = dst.x; x < dst_maxx; x++)
{
// Point sampling - you can also impl as bilinear or other
dst.bmp[x,y] = src.bmp[src_curx, src_cury];
src_curx += src_dx;
}

src_cury += src_dy;
}
}
``````

To do sub-pixel interpolation, you can sample the 4 pixels around the floating-point src_curx, src_cury, and take a weighted average. One of the highest quality methods is to effectively take a sample rectangle in the source image that corresponds to a single pixel in the dest image. Then you just average all the values in that and write the destination pixel. However, that rect will likely not fall on clean pixel boundaries, so you will want to take the clipped edge pixels and weight them accordingly.

-
Thank you - this is what I wanted - the principles behind the code to sample/transform and interpolation/sampling methods; I have implemented my method and the scaling/stretching is working perfectly. – sebf May 12 '12 at 12:19

Perhaps the mechanism you seek is the BitBlt algorithm?

Bit blit (also written BITBLT, BIT BLT, BitBLT, Bit BLT, Bit Blt etc., which stands for bit-level block transfer) is a computer graphics operation in which several bitmaps are combined into one using a raster operator.

The operation involves at least two bitmaps, a source and destination, possibly a third that is often called the "mask" and sometimes a fourth used to create a stencil. The pixels of each are combined bitwise according to the specified raster operation (ROP) and the result is then written to the destination. The ROP is essentially a boolean formula. The most obvious ROP overwrites the destination with the source. Other ROPs may involve AND, OR, XOR, and NOT operations...

-
or StretchBlt... – James May 10 '12 at 23:54
@James, yes, that does just what I was trying to describe. Although the Windows implementation takes HDCs so I can't use it directly, it is very helpful reading about it. – sebf May 12 '12 at 12:23

In order to resize an image properly (particularly, to reduce the size of an image), you need an interpolation filter scaled to the smaller of the source and destination sizes.

Unfortunately, if your destination buffer really is a bitmap, you have no way to store the grayscale pixels you will get from your filter. The best you can do (short of extraordinary measures) is threshold the results at 50%, in order to get a binary pixel value to store in your output buffer.

In many cases, a quick & dirty program won't bother to try resizing an arbitrarily-scaled bitmap properly at all -- they will simply grab the source pixel closest to the interpolated target location, as you describe. This is certainly fast, but it looks quite ugly, especially for size reduction (as your question suggests), or for dynamic stretching (animated or interactive).

However, if you're doing everything with bitmaps, maybe that particular kind of ugly could be useful for a bit of 8-bit cred...

-

Generally the best way is to work on a grid in the destination and interpolate the source pixel. That way you are sure that there are no gaps or aliasing effects in the destination.

-