December 01, 1997
URL:http://www.drdobbs.com/image-compression-using-laplacian-pyrami/184403435

Figure 1: The Reduce operation

Figure 2: The Expand operation

Figure 3: Producing a Laplacian Image

Figure 4: Constructing a Laplacian pyramid

Figure 5: Some sample compressed images and average bits per byte

Listing 1: The Reduce function

void LP::Reduce (unsigned level)
{
    // Reduce an image using a three by three block

    if (level >= _levels || level + 1 >= _levels)
        throw "Level is out of range";

    unsigned char *src = _r_images[level];
    unsigned char *dest = _r_images[level + 1];
    unsigned width = _width >> level;
    unsigned height = _height >> level;

    for (int y = 0; y < (int) (height - 3); y += 2)
    {
        for (int x = 0; x < (int) (width - 3); x += 2)
        {
            // Reduce argument is the top left corner
            // of the sample block

            unsigned char r = Reduce3x3 (&src[y * width + x], width);

            dest[((y / 2) * (width / 2)) + x / 2] = r;
        }
    }

    // Fix the edges

    // If the width is a multiple of two, then the reduced 
    // image has a missing column on the right hand side.

    if (!(width & 1))
    {
        for (int y = 0; y < (int) (height - 3); y += 2)
        {
            unsigned char r =
                Reduce2x3 (&src[y * width + width - 2], width);

            dest[((y / 2) * (width / 2)) + (width - 2) / 2] = r;
        }
    }

    // If the height is a multiple of two, then the reduced 
    // image has a missing row on the bottom.

    if (!(height & 1))
    {
        for (int x = 0; x < (int) (width - 3); x += 2)
        {
            unsigned char r =
                Reduce3x2 (&src[(height - 2) * width + x], width);
            dest[(((height - 2) / 2) * (width / 2)) + x / 2] = r;
        }
    }

    // If both the width and height are multiples of two, then
    // we missed the bottom right corner.

    if (!(width & 1) && !(height & 1))
    {
        unsigned char r =
            Reduce2x2 (&src[(height - 2) * width + (width - 2)],
                       width);

        dest[(((height-2)/2) * (width / 2)) + (width - 2) / 2] = r;
    }
}
//End of File

Listing 2: The weighted averaging routines

unsigned char
LP::Reduce3x3 (const unsigned char *block, unsigned width)
{
    // Reduce a block using a 3 by 3 equivalent weighting function

    unsigned r;

    r = *block; // First row
    r += *++block * 2;
    r += *++block;
    block += width - 2;
    r += *block * 2; // Second row
    r += *++block * 4;
    r += *++block * 2;
    block += width - 2;
    r += *block; // Third row
    r += *++block * 2;
    r += *++block;

    return r / 16;
}

unsigned char
LP::Reduce2x3 (const unsigned char *block, unsigned width)
{
    // Reduce a block using a 3 by 3 equivalent weighting function

    // Reflect left column to right column

    unsigned r;

    r = *block * 2; // First row
    r += *++block * 2;
    block += width - 1;
    r += *block * 4; // Second row
    r += *++block * 4;
    block += width - 1;
    r += *block * 2; // Third row
    r += *++block * 2;

    return r / 16;
}

unsigned char
LP::Reduce3x2 (const unsigned char *block, unsigned width)
{
    // Reduce a block using a 3 by 3 equivalent weighting function

    // Reflect top row to bottom row

    unsigned r;

    r = *block * 2; // First row
    r += *++block * 4;
    r += *++block * 2;
    block += width - 2;
    r += *block * 2; // Second row
    r += *++block * 4;
    r += *++block * 2;

    return r / 16;
}

unsigned char
LP::Reduce2x2 (const unsigned char *block, unsigned width)
{
    // Reduce a block using a 3 by 3 equivalent weighting function

    // Reflect left column to right column
    // Reflect top row to bottom row

    unsigned r;

    r = *block * 4; // First row
    r += *++block * 4;
    block += width - 1;
    r += *block * 4; // Second row
    r += *++block * 4;

    return r / 16;
}
//End of File

Listing 3: The Expand function

void LP::Expand (unsigned level)
{
    if (level >= _levels || level + 1 >= _levels)
        throw "Level is out of range";

    unsigned char *src = _r_images[level + 1];
    unsigned char *dest = _l_images[level];

    unsigned width = _width >> level;
    unsigned height = _height >> level;

    for (int y = 0; y < (int) (height - 3); y += 2)
    {
        for (int x = 0; x < (int) (width - 3); x += 2)
        {
            // Expand argument is the top left corner
            // of the sample block

            Expand3x3 (src[((y / 2) * (width / 2)) + x / 2],
                       &dest[y * width + x], width);
        }
    }

    // Fix the edges

    // If the width is a multiple of two, then the reduced 
    // image has a column on the right that was not expanded.


    if (!(width & 1))
    {
        for (int y = 0; y < (int) (height - 3); y += 2)
        {
            Expand2x3 (src[((y/2) * (width/2)) + (width - 2) / 2],
                       &dest[y * width + (width - 2)], width);
        }
    }

    // If the height is a multiple of two, then the reduced 
    // image has a row on the bottom that was not expanded.

    if (!(height & 1))
    {
        for (int x = 0; x < (int) (width - 3); x += 2)
        {
            Expand3x2 (src[(((height - 2)/2) * (width/2)) + x/2],
                       &dest[(height - 2) * width + x], width);
        }
    }

    // If both the width and height are multiples of two, then
    // the bottom right corner was never expanded.

    if (!(width & 1) && !(height & 1))
    {
        Expand2x2 (src[(((height-2)/2) * (width/2)) + (width-2)/2],
                   &dest[(height-2) * width + (width-2)], width);
    }

    // When expanding, the outer edges need a little more
    // fixing because they have not been interpolated enough.

    // The top row only got interpolated with half the number 
    // of pixels needed.

    for (int x = 0; x < (int) (width); x++)
        dest[x] *= 2;

    // Same with the left column.  The top left corner only got 1/4
    // the number of pixels it needed, but we're multiplying it
    // by 2 twice, so it's OK.

    for (y = 0; y < (int) (height); y++)
        dest[y * width] *= 2;

    // If the width is an odd number, the number of pixels needed
    // to interpolate the right column is 1/2.  If it's an even
    // number, then it's OK.

    if (width & 1)
        for (int y = 1; y <= (int) (height); y++)
            dest[y * width - 1] *= 2;

    // If the height is an odd number, then the bottom row needs
    // twice as many pixels to interpolate correctly.

    if (height & 1)
        for (int x = 0; x < (int) (width); x++)
            dest[(height - 1) * width + x] *= 2;

    // Notice that the NE, SE, and SW corners are OK -- they
    // were multiplied by 2 or 4 automatically when the sides
    // were being fixed.
}
//End of File

Listing 4: The expansion routines used by function Expand

void LP::Expand3x3 (
    unsigned char val, unsigned char *block, unsigned width)
{
    *block += val / 4; // First row
    *++block += val / 2;
    *++block += val / 4;
    block += width - 2;
    *block += val / 2; // Second row
    *++block += val;
    *++block += val / 2;
    block += width - 2;
    *block += val / 4; // Third row
    *++block += val / 2;
    *++block += val / 4;
}

void LP::Expand2x3 (
    unsigned char val, unsigned char *block, unsigned width)
{
    *block += val / 4; // First row
    *++block += val / 2;
    block += width - 1;
    *block += val / 2; // Second row
    *++block += val;
    block += width - 1;
    *block += val / 4; // Third row
    *++block += val / 2;
}

void LP::Expand3x2 (
    unsigned char val, unsigned char *block, unsigned width)
{
    *block += val / 4; // First row
    *++block += val / 2;
    *++block += val / 4;
    block += width - 2;
    *block += val / 2; // Second row
    *++block += val;
    *++block += val / 2;
}

void LP::Expand2x2 (
    unsigned char val, unsigned char *block, unsigned width)
{
    *block += val / 16; // First row
    *++block += val / 8;
    block += width - 1;
    *block += val / 8; // Second row
    *++block += val / 4;
}
//End of File

Listing 5: Laplacian pyramid constructor used for compression

LP::LP (unsigned width, unsigned height, 
     const unsigned char *image,
     unsigned levels, unsigned *bpp)
{
    // Build pyramid structure and copy initial image

    if (!width || !height || !levels || !image)
        throw "Invalid parameter";

    _width = width;
    _height = height;

    // Adjust levels if width or height is too small

    while (width >> (levels - 1) == 0 || height >> (levels - 1) == 0)
        --levels;

    _levels = levels;
    _bpp = new unsigned [levels];

    if (!_bpp)
        throw "Memory allocation error";

    for (unsigned level = 0; level < levels; level++)
        _bpp[level] = bpp[level];

    AllocateLevels ();

    // Copy image into level 0

    memcpy (_r_images[0], image, _width * _height);
}
//End of File

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.