How to correctly apply color palette to an image?

Question

So I have been given a task to re-write a program that converts an image to 3 different sizes, 1 being a 256 colour image with a specific palette applied. Original source code was lost.

Resizing I got working, but I am having issues with applying the palette. The palette is stored as a JASC-PAL file.

This is my code, based on my assumption that you just load the file, loop the image's current palette and replace the colours.

private List<Color> ColourPalette = new List<Color>();
void LoadColourPalette()
    {
        using (StreamReader sr = new StreamReader("HH.PAL"))
        {
            // skip first 3 lines
            sr.ReadLine();
            sr.ReadLine();
            sr.ReadLine();

            while (sr.Peek() != -1)
            {
                var readLine = sr.ReadLine();

                if(string.IsNullOrWhiteSpace(readLine))
                    continue;

                var colourBytes = readLine.Split(' ');

                ColourPalette.Add(
                    Color.FromArgb(int.Parse(colourBytes[0]),
                        int.Parse(colourBytes[1]),
                        int.Parse(colourBytes[2])
                        ));

            }
        }
    }

Loading of file and applying palette.

byte[] bytes;

using (FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read))
{
    using (var thumbnail = System.Drawing.Image.FromStream(fs))
    {
       var imagePalette = thumbnail.Palette;

       for (int i = 0; i < imagePalette.Entries.Length; i++)
           imagePalette.Entries[i] = ColourPalette[i];

       thumbnail.Palette = imagePalette;

       using (MemoryStream memory = new MemoryStream())
       {
           thumbnail.Save(memory, ImageFormat.Bmp);
           bytes = memory.ToArray();
       }
    }
}

using (FileStream fs = new FileStream(fileName, FileMode.Create, FileAccess.ReadWrite))
{
   fs.Write(bytes, 0, bytes.Length);
}

When I view the image it just looks totally wrong. Looks more like someone has chucked pixilated paint lol. I can't upload the image, but to give you an idea, the picture is of a white plate that's on a table. Table should be like shades of black/dark blue but they are shades of light brown and some green.

So I then took an image that has had the palette applied, I extracted the palette and saved to a file in the JASC-PAL format. When I compared with the palette file I was give I can see they match perfect.

Clearly there is more to it but I can't seem to find anything on the matter.

Answer 1

Applying a palette is not the same as replacing a palette. The step you're missing is to match the actual pixels on the image to the new colours.

See, the pixels on indexed images do not contain colours. They contain references to the palette. So if you got a red pixel on the image, that's not a pixel with the value "red", it's a pixel with some value from 0 to 255 referring to a colour at that index on the palette. So say it has value '23', then that means it uses the colour on index 23 on the palette, and that colour is red.

But you're replacing these colours on the palette. So obviously, after your operation, that pixel referring to index 23 will no longer be the red that it had before; it'll have whatever colour you replaced index 23 with. That's why all the colours on the image will be jumbled up.

Basically, what you need to do is look at the colours your pixels use, find their closest match on the new palette, and then save the index at which that closest match was found on the new palette into your pixels.

The way to do this is a bit trickier than you might expect. The normal .Net functions for painting on images can't access these raw index values; they can only work with colours. So you'll have to go a bit deeper.

Since this is an 8 bit per pixel image, every colour index value on the image is one byte. So the first thing you have to do is get these bytes. This is done with the LockBits operation, which gives you access to the underlying memory of the image. Then you can use Marshal.Copy to get the bytes out without a need to mess around with bare pointers.

So let's start with the function to get these bytes:

/// <summary>
/// Gets the raw bytes from an image.
/// </summary>
/// <param name="sourceImage">The image to get the bytes from.</param>
/// <param name="stride">Stride of the retrieved image data.</param>
/// <returns>The raw bytes of the image</returns>
public static Byte[] GetImageData(Bitmap sourceImage, out Int32 stride)
{
    BitmapData sourceData = sourceImage.LockBits(new Rectangle(0, 0, sourceImage.Width, sourceImage.Height), ImageLockMode.ReadOnly, sourceImage.PixelFormat);
    stride = sourceData.Stride;
    Byte[] data = new Byte[stride * sourceImage.Height];
    Marshal.Copy(sourceData.Scan0, data, 0, data.Length);
    sourceImage.UnlockBits(sourceData);
    return data;
}

Important note: the "stride" is the amount of bytes on each line on the image. Since this is generally rounded up to a multiple of 4 bytes, it is vitally important to keep it in mind, because very often it will not just match the image width.

Now we got the bytes, we need to go over them, see which colour they have on the current palette, and find the closest match on the new palette. I already described that process in this answer, but I'll repeat it here for completeness' sake.

The normal way to match an image to specific colours is to use Pythagorean distance between the colours in a 3D environment with R, G and B as axes. Note that the "take the square root" part of the Pythagorean distance calculation is not actually needed; we don't need to know the actual distance, we only need to compare them, and that works just as well without that rather CPU-heavy operation.

Note that if your image contains more than 256 pixels (which I assume most images will), it's a lot simpler to just look up the closest match for each index in your palette, rather than for each pixel in the full image, and then apply that mapping to the image data itself. Then you only need to do the colour lookups once for each actual colour.

/// <summary>
/// Uses Pythagorean distance in 3D colour space to find the closest match to a given colour on
/// a given colour palette, and returns the index on the palette at which that match was found.
/// </summary>
/// <param name="col">The colour to find the closest match to</param>
/// <param name="colorPalette">The palette of available colours to match</param>
/// <returns>The index on the palette of the colour that is the closest to the given colour.</returns>
public static Int32 GetClosestPaletteIndexMatch(Color col, Color[] colorPalette)
{
    Int32 colorMatch = 0;
    Int32 leastDistance = Int32.MaxValue;
    Int32 red = col.R;
    Int32 green = col.G;
    Int32 blue = col.B;
    for (Int32 i = 0; i < colorPalette.Length; ++i)
    {
        Color paletteColor = colorPalette[i];
        Int32 redDistance = paletteColor.R - red;
        Int32 greenDistance = paletteColor.G - green;
        Int32 blueDistance = paletteColor.B - blue;
        Int32 distance = (redDistance * redDistance) + (greenDistance * greenDistance) + (blueDistance * blueDistance);
        if (distance >= leastDistance)
            continue;
        colorMatch = i;
        leastDistance = distance;
        if (distance == 0)
            return i;
    }
    return colorMatch;
}

With the best colour match found for all the colours on the old palette, you can go over the image data itself, and replace all indices on the image with the correct matching one for the new palette. I'll put that code at the end, after we got all the pieces.

Once that's done, you got your 8-bit image array ready to be converted back into an 8-bit image. This is done with that same LockBits operation, only now in 'write' mode. Finally, you apply the new palette to the new image, pretty much like how your own code did it. Here's the BuildImage function I use for all that:

/// <summary>
/// Creates a bitmap based on data, width, height, stride and pixel format.
/// </summary>
/// <param name="sourceData">Byte array of raw source data</param>
/// <param name="width">Width of the image</param>
/// <param name="height">Height of the image</param>
/// <param name="stride">Scanline length inside the data</param>
/// <param name="pixelFormat">Pixel format</param>
/// <param name="palette">Color palette</param>
/// <param name="defaultColor">Default color to fill in on the palette if the given colors don't fully fill it.</param>
/// <returns>The new image</returns>
public static Bitmap BuildImage(Byte[] sourceData, Int32 width, Int32 height, Int32 stride, PixelFormat pixelFormat, Color[] palette, Color? defaultColor)
{
    Bitmap newImage = new Bitmap(width, height, pixelFormat);
    BitmapData targetData = newImage.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.WriteOnly, newImage.PixelFormat);
    // Get the actual minimum data width
    Int32 newDataWidth = ((Image.GetPixelFormatSize(pixelFormat) * width) + 7) / 8;
    // Cache these to avoid unnecessary getter calls.
    Int32 targetStride = targetData.Stride;
    Int64 scan0 = targetData.Scan0.ToInt64();
    // Copy data per line into the target memory.
    for (Int32 y = 0; y < height; ++y)
        Marshal.Copy(sourceData, y * stride, new IntPtr(scan0 + y * targetStride), newDataWidth);
    newImage.UnlockBits(targetData);
    // For indexed images, set the palette.
    if ((pixelFormat & PixelFormat.Indexed) != 0 && (palette != null || defaultColor.HasValue))
    {
        if (palette == null)
            palette = new Color[0];
        ColorPalette pal = newImage.Palette;
        Int32 minLen = Math.Min(pal.Entries.Length, palette.Length);
        for (Int32 i = 0; i < minLen; ++i)
            pal.Entries[i] = palette[i];
        // Fill in remainder with default if needed.
        if (pal.Entries.Length > palette.Length && defaultColor.HasValue)
            for (Int32 i = palette.Length; i < pal.Entries.Length; ++i)
                pal.Entries[i] = defaultColor.Value;
        newImage.Palette = pal;
    }
    return newImage;
}

So, now, to combine all those:

Int32 stride;
Int32 width;
Int32 height;
Color[] curPalette;
// Easier as array. Maybe you should do that right away;
// it's always 256 entries anyway.
Color[] newPalette = ColourPalette.ToArray();
Byte[] imageData;
// This 'using' block is kept small; extract the data and then dispose everything.
using (Bitmap image = new Bitmap(filename))
{
    if (image.PixelFormat != PixelFormat.Format8bppIndexed)
        return;
    width = image.Width;
    height = image.Height;
    curPalette = image.Palette.Entries;
    imageData = GetImageData(image, out stride);
}
// Make remap table to translate from old palette indices to new ones.
Byte[] match = new Byte[curPalette.Length];
for (Int32 i = 0; i < curPalette.Length; ++i)
    match[i] = (Byte)GetClosestPaletteIndexMatch(curPalette[i], newPalette);
// Go over the actual pixels in the image data and replace the colours.
Int32 currentLineOffset = 0;
for (Int32 y = 0; y < height; ++y)
{
    Int32 offset = currentLineOffset;
    for (Int32 x = 0; x < width; ++x)
    {
        // Replace index with index of the closest match found before for that colour.
        imageData[offset] = match[imageData[offset]];
        // Increase offset on this line
        offset++;
    }
    // Increase to start of next line
    currentLineOffset += stride;
}
using (Bitmap newbm = BuildImage(imageData, width, height, stride, PixelFormat.Format8bppIndexed, newPalette, Color.Black))
{
    // Old bitmap is already disposed, so there is no issue saving to the same filename now
    newbm.Save(filename, ImageFormat.Bmp);
}

Answer 2

I would assume your source image is in 24 or 32 bit colors. I.e. each pixel has a byte for each of the the Red Green and Blue channels. Paletted images does not work like this. Instead it has a single byte, that is used as a in index into a lookup table.

So to find the correct index you would need to do a search in the palette to find the color that is the most similar to the actual pixel color. I do not think you can use a 8-bit bitmap as a render target for Graphics.FromImage, so you might need to do this processing yourself, but there might be libraries available that can do it for you.

Using paletted bitmaps is not as common anymore since any size-reduction can typically achieved much more efficiently by using a modern image compression algorithm.

I'm honestly not sure what happens if you just set the palette of a regular 24bit bitmap, but apparently the result is incorrect, so it might not be relevant.