Compression and Decompression
As of ImageGear v14.5, the Windows DIB format is no longer used for internal storage of images. So 1-bit images are now always stored internally in run ends format (also called "run lengths" format). Previous versions of ImageGear had IG_IP_convert_runs_to_DIB() and IG_IP_convert_DIB_to_runs() functions that converted the internally stored image between run ends and DIB (uncompressed packed) format. These functions are no longer necessary because conversion is performed automatically as needed.
When you read an image's pixel data using a pixel access function such as IG_DIB_raster_get(), ImageGear decompresses the pixel data for that raster and stores it in your buffer. You can specify packed (8 pixels per byte) or unpacked (1 pixel per byte) format. When you write pixel data using a pixel access function such as IG_DIB_raster_set(), ImageGear will compress and store the pixel data in run ends format. It's important to realize that this decompression and compression is the same work that was previously performed in IG_IP_convert_runs_to_DIB() and IG_IP_convert_DIB_to_runs(). However, instead of being performed on the entire image before and after processing, this work is performed on parts of the image during processing.
This section provides the following information:
Decompressing and Compressing the Entire Image
If you want to work with an image directly and avoid using pixel access functions on a per-raster basis, you can decompress the image to your own buffer using IG_DIB_area_get(). Here's an example scenario:
- Call IG_DIB_area_size_get to get the size of the buffer.
- Allocate the buffer (i.e., with new or malloc).
- Call IG_DIB_area_get. ImageGear decompresses the image into your buffer.
- Read/write uncompressed pixel data directly in your buffer.
- Call IG_DIB_area_set if updating ImageGear's internal copy of the image is desired. ImageGear compresses the image from your buffer.
Understanding Run Ends Format
The run ends format is a specialized variant of run length encoding. Run length encoding relies on the fact that certain types of images frequently contain parts where many adjacent pixels share the same color. A description of such an occurrence is known as a run. Typically a run is described as 1) a color, and 2) the number of following pixels that are that color. An image raster (or entire image) can be stored as a collection of runs. For example, an image of this page could be described as "2000 white pixels, 5 black pixels, 15 white pixels, 5 black pixels, 15 white pixels, 5 black pixels, 30 white pixels" and so on.
Since the run ends format only works on 1-bit images, it can take advantage of the fact that there are only two possible colors present in the raster: 0 and 1. Since there are only two possible colors, the color does not need to be stored for each run. It is inferred from the previous run. Also, having only two colors makes it especially likely that long runs of identically colored pixels will occur, as compared to images with more colors present.
The following points characterize the run ends format:
- An image is stored as a collection of rasters encoded in run ends format. Each raster is independent - there is no information shared between rasters. Therefore, consider only a single raster when thinking about the run ends format.
- A run ends raster is stored as an array of run ends. A run end is a value of type AT_RUN which marks the end of a run by storing the horizontal position (X-coordinate) of where the next run begins.
- Run ends are stored in order from left to right.
- It is always assumed that the first run in a raster is white. If it is not, there will be a "null run" at the beginning of the raster which ends at column 0. This is a means of getting the first real (non-zero-length) run to be black.
- The last run end in the raster is always equal to the image width. This value is stored three times to mark the end of the raster.
Here are some examples of rasters that are 8 pixels in width. Each raster is shown first in uncompressed format, then in run ends format as it would be stored in memory on a 32-bit x86 platform. That is, the number 5 is stored in memory as "05 00 00 00".
Example 1 |
Example 2 |
11001000
02 00 00 00 // white run until column 2
04 00 00 00 // black run until column 4
05 00 00 00 // white run until column 5
08 00 00 00 // done (remainder is black)
08 00 00 00
08 00 00 00 |
00000101
00 00 00 00 // *get first run to be black*
05 00 00 00 // black run until column 5
06 00 00 00 // white run until column 6
07 00 00 00 // black run until column 7
08 00 00 00 // done (remainder is white)
08 00 00 00
08 00 00 00 |
Accessing Run Ends Data
There are two ways that you can access run ends data:
-
IG_image_DIB_raster_pntr_get() is a general purpose function for getting a pointer to pixel data for a given raster. If you use it on a 1bpp image, it will return a pointer to a run ends raster. You can access this raster directly, but be aware of the following:
- There is an additional AT_RUN value at the beginning of the raster. This value is equal to the total number of AT_RUN values used to store the raster, including this value. For example, for the raster "11001000", this value would be 7.
- You cannot write data that exceeds the original length of a raster, because ImageGear allocates only enough space to hold the runs for that raster. For this reason, it is safer to use IG_runs_row_set(), which can reallocate if necessary.
- Run ends rasters are not stored contiguously in memory. You must call IG_image_DIB_raster_pntr_get() for each raster you want to process.
Run Ends Code Examples
The following is a sample function that decompresses a run ends raster into uncompressed unpacked (1 byte per pixel) format. It's designed to work with the data you would get from IG_runs_row_get().
|
Copy Code
|
// runsToUnpacked: Decompresses a run ends raster to unpacked format.
// nWidth - width of image in pixels
// lpRuns - pointer to input buffer containing run ends data
// lpPixels - pointer to output buffer to receive unpacked pixel data
void runsToUnpacked(AT_DIMENSION nWidth, LPAT_RUN lpRuns, LPAT_PIXEL lpPixels)
{
// Starting color is white
AT_PIXEL outputPixColor = 1;
// Loop through runs
AT_INT outputPixPos = 0;
while (1)
{
// Find out when the current run ends
AT_RUN runEnd = *lpRuns++;
// Fill in pixels for this run
while (outputPixPos < runEnd)
lpPixels[outputPixPos++] = outputPixColor;
// Have we reached the end?
if (outputPixPos >= nWidth)
break;
// Switch colors for next run
outputPixColor = !outputPixColor;
}
}
|
The following is a more minimalist view of the same function:
|
Copy Code
|
void runsToUnpacked(AT_DIMENSION w, LPAT_RUN lpRuns, LPAT_PIXEL lpPixels)
{
AT_PIXEL c = 1;
AT_INT x = 0;
while (1)
{
AT_RUN r = *lpRuns++;
while (x < r)
lpPixels[x++] = c;
if (x >= w)
break;
c = !c;
}
}
|
The following is a more complex function that creates a 90-degree rotated copy of an image. It operates entirely on run ends data without ever decompressing the data. Note that this is only sample code. This does not represent how ImageGear works internally. Also, error handling is omitted.
|
Copy Code
|
// Returns a 90-degree rotated copy of the source image
HIGEAR rotate90(HIGEAR hImageSrc)
{
HIGEAR hImageDst = NULL;
HIGDIBINFO hDIB;
AT_INT d[1] = { 1 };
AT_DIMENSION srcWidth, srcHeight, dstWidth, dstHeight;
AT_PIXPOS x, y;
// Get info about source image
IG_image_dimensions_get(hImageSrc, &srcWidth, &srcHeight, NULL);
// Create destination image
dstWidth = srcHeight;
dstHeight = srcWidth;
IG_DIB_info_create(&hDIB, dstWidth, dstHeight, IG_COLOR_SPACE_ID_I, 1, d);
IG_DIB_palette_alloc(hDIB);
IG_image_create(hDIB, &hImageDst);
IG_DIB_info_delete(hDIB);
AT_RGB rgb = { 255, 255, 255 };
IG_palette_entry_set(hImageDst, &rgb, 1);
// Make a list of source raster pointers
LPAT_RUN *lpSrcRasters = NULL;
lpSrcRasters = (LPAT_RUN *) malloc(sizeof(LPAT_RUN) * srcHeight);
// Make a list of current colors for source runs
LPAT_BYTE lpSrcRunColors = NULL;
lpSrcRunColors = (LPAT_BYTE) malloc(sizeof(AT_BYTE) * srcHeight);
// Populate the lists
for (y = 0; y < srcHeight; y++)
{
AT_RUN runCount;
IG_runs_row_get(hImageSrc, y, &runCount, &lpSrcRasters[y]);
if (*lpSrcRasters[y])
lpSrcRunColors[y] = 1;
else
{
lpSrcRunColors[y] = 0;
lpSrcRasters[y]++;
}
}
// Allocate a raster large enough to store worst-case input data
LPAT_RUN lpDstRaster = (LPAT_RUN) malloc(sizeof(AT_RUN) * (dstWidth + 4));
// Loop through output rasters
for (y = 0; y < dstHeight; y++)
{
AT_INT nDstRuns = 0;
AT_BYTE dstRunColor = 1;
AT_INT srcRasterIndex = srcHeight - 1;
// If the first source pixel is black,
// set us up to start with black in the output raster
if (!lpSrcRunColors[srcRasterIndex])
{
dstRunColor = 0;
lpDstRaster[nDstRuns++] = 0;
}
// Loop through columns in destination image
for (x = 0; x < dstWidth; x++)
{
// Check the color of the run in the source raster that
// corresponds to the current column in the destination raster.
// Is it the same color as the run we're currently constructing?
if (lpSrcRunColors[srcRasterIndex] != dstRunColor)
{
// If not, then we need to store the run we've been making
// in the destination raster.
lpDstRaster[nDstRuns++] = x;
// Alternate the current destination run color
dstRunColor = !dstRunColor;
}
// See if it's time to move on to the next source run for
// this source raster
if (*lpSrcRasters[srcRasterIndex] == y)
{
lpSrcRasters[srcRasterIndex]++;
lpSrcRunColors[srcRasterIndex] = !lpSrcRunColors[srcRasterIndex];
}
// Move on to the next source raster (go *up* through the source image)
srcRasterIndex--;
}
// Add the three ending runs to the destination raster
lpDstRaster[nDstRuns++] = dstWidth;
lpDstRaster[nDstRuns++] = dstWidth;
lpDstRaster[nDstRuns++] = dstWidth;
// Store the destination raster!
IG_runs_row_set(hImageDst, y, nDstRuns, lpDstRaster);
}
// Clean up
free(lpSrcRasters);
free(lpSrcRunColors);
free(lpDstRaster);
return hImageDst;
}
|