Click here to Skip to main content
Click here to Skip to main content
Go to top

Fast Color Depth Change for Bitmaps

, 15 Jan 2007
Rate this:
Please Sign up or sign in to vote.
This article describes color depth change for Bitmaps

Introduction

This article describes fast bitmap color depth change. After my previous code sample, I've got some e-mails from people who were interested in my TTF convert solution, but they claimed that my code has poor performance. Ok, guys, (thanks a lot to all of you) you are right. I've developed my utility to run it on bitmaps with a size of 16X16 pixels. When you try to run it on bigger bitmaps, it will take much more time. For example, it will take more than 20 minutes to convert a 1024x768 bitmap (I run Centrino 1.8G).

Reasons

So let's see the reasons for such bad results. Look at the ConvertTo8bppFormat method. The core of this method is a double loop (width X height), so for big bitmaps (1024x768 and bigger) there are millions and more iterations. During iteration, the code reads pixel's information from the source bitmap, then matches some known color (256 iterations in the worst case) and then copies it to the destination. So I'll perform the following steps to improve performance:

  • Decrease the number of iterations, its mean, read all source information at once and copy all destination information at once.
  • Decrease the number of property and method invocations of .NET classes. For example, see the double loop of ConvertTo8bppFormat. There are two invocations of Bitmap width and height properties for each pixel (its mean is 2M invocations). You can check the cost of such an invocation with a profiler - for sure, it is more expensive than reading it only one time to some temp variable before the loop.
  • Decrease the number of memory allocations inside the loop. It is one of the principles for time critical code development – do not allocate memory on demand, but perform allocation before.
  • Use previous information. For example, during color matching, for each 24bit color we match the appropriate index in the 256 color palette. Almost every image has a lot of pixels that have the same color, so for those pixels, color matching will be executed only once.

Solutions

Now let's see the solution and test results. All results are relevant for 1024x768 bitmaps.

  • ConvertTo8bppFormat has no loops; its role is to allocate all buffers and to call methods that do the real job.

    /// <span class="code-SummaryComment"><summary></span>
    /// Converts input bitmap to 8bpp format
    /// <span class="code-SummaryComment"></summary></span>
    /// <param name="bmpSource" />Bitmap to convert</param />
    /// <span class="code-SummaryComment"><returns>Converted bitmap</returns></span>
    public Bitmap ConvertTo8bppFormat(Bitmap bmpSource)
    {
        int imageWidth = bmpSource.Width;
        int imageHeight = bmpSource.Height;
    
        Bitmap bmpDest = null;
        BitmapData bmpDataDest = null;
        BitmapData bmpDataSource = null;
    
        try
        {
            // Create new image with 8BPP format
            bmpDest = new Bitmap(
                imageWidth,
                imageHeight,
                PixelFormat.Format8bppIndexed
                );
    
            // Lock bitmap in memory
            bmpDataDest = bmpDest.LockBits(
                new Rectangle(0, 0, imageWidth, imageHeight),
                ImageLockMode.ReadWrite,
                bmpDest.PixelFormat
                );
    
            bmpDataSource = bmpSource.LockBits(
                new Rectangle(0, 0, imageWidth, imageHeight),
                ImageLockMode.ReadOnly,
                bmpSource.PixelFormat
            );
    
            int pixelSize = GetPixelInfoSize(bmpDataSource.PixelFormat);
            byte[] buffer = new byte[imageWidth * imageHeight * pixelSize];
            byte[] destBuffer = new byte[imageWidth * imageHeight];
    
            // Read all data to buffer
            ReadBmpData(bmpDataSource, buffer, pixelSize, imageWidth, imageHeight);
    
            // Get color indexes
            MatchColors(buffer, destBuffer, pixelSize, bmpDest.Palette);
    
            // Copy all colors to destination bitmaps
            WriteBmpData(bmpDataDest, destBuffer, imageWidth, imageHeight);
    
            return bmpDest;
        }
        finally
        {
            if (bmpDest != null) bmpDest.UnlockBits(bmpDataDest);
            if( bmpSource != null ) bmpSource.UnlockBits( bmpDataSource );
        }
    }
  • ReadBmpData and WriteBmpData – These methods just copy unmanaged memory (pixels color information) to managed buffer and vice versa. Pay attention, only 24bit bitmaps are supported now, but you can easily extend it for other bitmap types, just add code to GetPixelInfoSize and GetSimilarColor methods. ReadBmpData and WriteBmpData are pretty quick, it takes only 0.01s to read and write data.

    /// <span class="code-SummaryComment"><summary></span>
    /// Reads all bitmap data at once
    /// <span class="code-SummaryComment"></summary></span>
    private void ReadBmpData(
        BitmapData bmpDataSource,
        byte[] buffer,
        int pixelSize,
        int width,
        int height)
    {
        // Get unmanaged data start address
        int addrStart = bmpDataSource.Scan0.ToInt32();
    
        for (int i = 0; i < height; i++)
        {
            // Get address of next row
            IntPtr realByteAddr = new IntPtr( addrStart +
                System.Convert.ToInt32(i * bmpDataSource.Stride)
                );
    
            // Perform copy from unmanaged memory
            // to managed buffer
            Marshal.Copy(
                realByteAddr,
                buffer,
                (int)(i * width * pixelSize),
                (int)(width * pixelSize)
            );
        }
    }
    
    /// <span class="code-SummaryComment"><summary></span>
    /// Writes bitmap data to unmanaged memory
    /// <span class="code-SummaryComment"></summary></span>
    private void WriteBmpData(
        BitmapData bmpDataDest,
        byte[] destBuffer,
        int imageWidth,
        int imageHeight)
    {
        // Get unmanaged data start address
        int addrStart = bmpDataDest.Scan0.ToInt32();
    
        for (int i = 0; i < imageHeight; i++)
        {
            // Get address of next row
            IntPtr realByteAddr = new IntPtr(addrStart +
                System.Convert.ToInt32(i * bmpDataDest.Stride)
                );
    
            // Perform copy from managed buffer
            // to unmanaged memory
            Marshal.Copy(
                destBuffer,
                i*imageWidth,
                realByteAddr,
                imageWidth
            );
        }
    }
  • MatchColors – This method matches the index of 256 color palettes for each 24bit color. This method is expensive; color matching calculation takes 99% of run time of this application. So to make it faster, I've used a hash table to store all known colors and that’s why this code will be run really fast on bitmaps with the same colored background and it will be slow on bitmaps with a wide range of colors. I've got from 1 sec to 10 secs of calculation time in my test.

    /// <span class="code-SummaryComment"><summary></span>
    /// This method matches indices from pallete ( 256 colors )
    /// for each given 24bit color
    /// <span class="code-SummaryComment"></summary></span>
    /// <span class="code-SummaryComment"><param name="buffer">Buffer that contains color for each pixel</param></span>
    /// <span class="code-SummaryComment"><param name="destBuffer">Destination buffer that will contain index </span>
    /// for each color<span class="code-SummaryComment"></param></span>
    /// <span class="code-SummaryComment"><param name="pixelSize">Size of pixel info ( 24bit colors supported )</param></span>
    /// <span class="code-SummaryComment"><param name="pallete">Colors pallete ( 256 colors )</param></span>
    private void MatchColors(
        byte[] buffer,
        byte[] destBuffer,
        int pixelSize,
        ColorPalette pallete)
    {
        int length = destBuffer.Length;
    
        // Temp storage for color info
        byte[] temp = new byte[pixelSize];
    
        int palleteSize = pallete.Entries.Length;
    
        int mult_1 = 256;
        int mult_2 = 256 * 256;
    
        int currentKey = 0;
    
        // For each color
        for (int i = 0; i < length; i++)
        {
            // Get next color
            Array.Copy(buffer, i * pixelSize, temp, 0, pixelSize);
    
            // Build key for hash table
            currentKey = temp[0] + temp[1] * mult_1 + temp[2] * mult_2;
    
            // If hash table already contains such color - fetch it
            // Otherwise perform calculation of similar color and save it to HT
            if (!m_knownColors.ContainsKey(currentKey))
            {
                destBuffer[i] = GetSimilarColor(pallete, temp, palleteSize);
                m_knownColors.Add(currentKey, destBuffer[i]);
            }
            else
            {
                destBuffer[i] = (byte)m_knownColors[currentKey];
            }
        }// for
    }
    
    /// <span class="code-SummaryComment"><summary></span>
    /// Returns Similar color
    /// <span class="code-SummaryComment"></summary></span>
    /// <span class="code-SummaryComment"><param name="palette"></param></span>
    /// <span class="code-SummaryComment"><param name="color"></param></span>
    /// <span class="code-SummaryComment"><returns></returns></span>
    private byte GetSimilarColor(ColorPalette palette, byte[] color, int palleteSize)
    {
        byte minDiff = byte.MaxValue;
        byte index = 0;
    
        if (color.Length == 3)// Implemented for 24bpp color
        {
            // Loop all pallete ( 256 colors )
            for (int i = 0; i < palleteSize - 1; i++)
            {
                // Calculate similar color
                byte currentDiff = GetMaxDiff(color, palette.Entries[i]);
    
                if (currentDiff < minDiff)
                {
                    minDiff = currentDiff;
                    index = (byte)i;
                }
            }// for
        }
        else// TODO implement it for other color types
        {
            throw new ApplicationException("Only 24bit colors supported now");
        }
    
        return index;
    }
    
    /// <span class="code-SummaryComment"><summary></span>
    /// Return similar color
    /// <span class="code-SummaryComment"></summary></span>
    /// <span class="code-SummaryComment"><param name="a"></param></span>
    /// <span class="code-SummaryComment"><param name="b"></param></span>
    /// <span class="code-SummaryComment"><returns></returns></span>
    private static byte GetMaxDiff(byte[] a, Color b)
    {
        // Get difference between components ( red green blue )
        // of given color and appropriate components of pallete color
        byte bDiff = a[0] > b.B ? (byte)(a[0] - b.B): (byte)(b.B - a[0]);
        byte gDiff = a[1] > b.G ? (byte)(a[1] - b.G) : (byte)(b.G - a[1]);
        byte rDiff = a[2] > b.R ? (byte)(a[2] - b.R) : (byte)(b.R - a[2]);
    
        // Get max difference
        byte max = bDiff > gDiff ? bDiff : gDiff;
        max = max > rDiff ? max : rDiff;
    
        return max;
    }

Conclusion

As you can see, performance was improved (from 20 minutes to 1-10 seconds for changing the color depth). This means that if .NET code is written properly and carefully, it can be very fast and used in time critical applications!

Good luck!

History

  • 15th January, 2007: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Dima Statz
Retired
Israel Israel
Name: Statz Dima
Fields of interest: software

Comments and Discussions

 
QuestionAwesome Pinmembermilpool27-Jun-13 20:20 
GeneralFaster way for converting to 8bpp PinmemberJoeSharp7-Aug-08 2:35 
GeneralThis kind of conversion can never be optimal using .net PinmemberDuggi3-Jun-08 13:03 
GeneralRe: This kind of conversion can never be optimal using .net PinmemberAngular14-Dec-13 7:40 
Generalimage is not 8bit Pinmemberyandra2k20-May-08 7:45 
Generalimage quantization coz that is basicly what happens Pinmemberda_vinci7_oh_fucking_4044-May-08 21:23 
GeneralRe: image quantization coz that is basicly what happens PinmemberAngular14-Dec-13 7:44 
GeneralArticle seems to be damaged Pinmemberpicobit6-Dec-07 3:35 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140926.1 | Last Updated 15 Jan 2007
Article Copyright 2007 by Dima Statz
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid