Fast Color Depth Change for Bitmaps

• Download source files - 32.16 KB

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.

  /// <summary>
  /// Converts input bitmap to 8bpp format
  /// </summary>
  /// Bitmap to convert
  /// <returns>Converted bitmap</returns>
  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.

  /// <summary>
  /// Reads all bitmap data at once
  /// </summary>
  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)
          );
      }
  }
  
  /// <summary>
  /// Writes bitmap data to unmanaged memory
  /// </summary>
  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.

  /// <summary>
  /// This method matches indices from pallete ( 256 colors )
  /// for each given 24bit color
  /// </summary>
  /// <param name="buffer">Buffer that contains color for each pixel</param>
  /// <param name="destBuffer">Destination buffer that will contain index 
  /// for each color</param>
  /// <param name="pixelSize">Size of pixel info ( 24bit colors supported )</param>
  /// <param name="pallete">Colors pallete ( 256 colors )</param>
  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
  }
  
  /// <summary>
  /// Returns Similar color
  /// </summary>
  /// <param name="palette"></param>
  /// <param name="color"></param>
  /// <returns></returns>
  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;
  }
  
  /// <summary>
  /// Return similar color
  /// </summary>
  /// <param name="a"></param>
  /// <param name="b"></param>
  /// <returns></returns>
  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