The basic method of solving this is the following:
- Go over the image, and build up a histogram of all occurring colours. Since colours can be represented as an
Int32, You can use a Dictionary<Int32,Int32> for this.
- Take the two top colours from this histogram. Designate the most commonly occurring one as the "background colour" and the second as the "content colour".
- Take the differences in R, G and B between the background and the content colour, and use those to make a colour palette with a smooth 256-colour fade from one colour to the other.
- Go over all pixels of the image, and for each pixel, use the Pythagorean distance in 3D colour space to determine which colour from the generated palette it is the closest to.
- On the resulting image, set the colours to a smooth fade from black to white.
Now, GetPixel and SetPixel, when looped over an entire image, are ridiculously slow, because they have to perform a rather heavy LockBits operation on the image for every pixel they handle. So instead, you can perform the LockBits operation once on the entire image, copy the bytes out, do all your operations on the resulting byte array, and then use LockBits a second time to copy the result into a new image.
Since we're dealing with grayscale colours here, it's also probably more efficient to write the end result into a 8-bit image. This also makes it trivially easy to manipulate the colour palette after doing the actual colour matching.
If you instead prefer to match it to exactly two colours, the method is exactly the same, except that instead of generating a colour fade between the two colours, the palette to match to will only contain the two found colours. Since the only possible indices to match on that will be 0 and 1, the final image's palette will likewise just need to have index 0 and index 1 set to black and white, rather than getting a whole grayscale fade.
The resulting method:
/// <summary>
/// Finds the two most prominent colours in an image, and uses them as
/// extremes for matching all pixels on the image to a grayscale palette.
/// </summary>
/// <param name="image">Image to reduce.</param>
/// <param name="bgWhite">True if the background (the most found colour) should become the white colour. If not, it will be the black one.</param>
/// <returns>
/// An 8-bit image with the image content of the input reduced to grayscale,
/// with the two most-found colours as black and white.
/// </returns>
public static Bitmap ReduceToTwoColorFade(Bitmap image, Boolean bgWhite)
{
// Get data out of the image, using LockBits and Marshal.Copy
Int32 width = image.Width;
Int32 height = image.Height;
// LockBits can actually -convert- the image data to the requested colour depth.
// 32 bpp is the easiest to get the colour components out.
BitmapData sourceData = image.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
// Not really needed for 32bpp, but technically the stride does not always match the
// amount of used data on each line, since the stride gets rounded up to blocks of 4.
Int32 stride = sourceData.Stride;
Byte[] imgBytes = new Byte[stride * height];
Marshal.Copy(sourceData.Scan0, imgBytes, 0, imgBytes.Length);
image.UnlockBits(sourceData);
// Make colour population histogram
Int32 lineOffset = 0;
Dictionary<Int32, Int32> histogram = new Dictionary<Int32, Int32>();
for (Int32 y = 0; y < height; y++)
{
Int32 offset = lineOffset;
for (Int32 x = 0; x < width; x++)
{
// Optional check: only handle if not mostly-transparent
if (imgBytes[offset + 3] > 0x7F)
{
// Get colour values from bytes, without alpha.
// Little-endian: UInt32 0xAARRGGBB = Byte[] { BB, GG, RR, AA }
Int32 val = (imgBytes[offset + 2] << 16) | (imgBytes[offset + 1] << 8) | imgBytes[offset + 0];
if (histogram.ContainsKey(val))
histogram[val] = histogram[val] + 1;
else
histogram[val] = 1;
}
offset += 4;
}
lineOffset += stride;
}
// Sort the histogram. This requires System.Linq
KeyValuePair<Int32, Int32>[] histoSorted = histogram.OrderByDescending(c => c.Value).ToArray();
// Technically these colours will be transparent when built like this, since their
// alpha is 0, but we won't use them directly as colours anyway.
// Since we filter on alpha, getting a result is not 100% guaranteed.
Color colBackgr = histoSorted.Length < 1 ? Color.Black : Color.FromArgb(histoSorted[0].Key);
// if less than 2 colors, just default it to the same.
Color colContent = histoSorted.Length < 2 ? colBackgr : Color.FromArgb(histoSorted[1].Key);
// Make a new 256-colour palette, making a fade between these two colours, for feeding into GetClosestPaletteIndexMatch later
Color[] matchPal = new Color[0x100];
Color toBlack = bgWhite ? colContent : colBackgr;
Color toWhite = bgWhite ? colBackgr : colContent;
Int32 rFirst = toBlack.R;
Int32 gFirst = toBlack.G;
Int32 bFirst = toBlack.B;
Double rDif = (toBlack.R - toWhite.R) / 255.0;
Double gDif = (toBlack.G - toWhite.G) / 255.0;
Double bDif = (toBlack.B - toWhite.B) / 255.0;
for (Int32 i = 0; i < 0x100; i++)
matchPal[i] = Color.FromArgb(
Math.Min(0xFF, Math.Max(0, rFirst - (Int32)Math.Round(rDif * i, MidpointRounding.AwayFromZero))),
Math.Min(0xFF, Math.Max(0, gFirst - (Int32)Math.Round(gDif * i, MidpointRounding.AwayFromZero))),
Math.Min(0xFF, Math.Max(0, bFirst - (Int32)Math.Round(bDif * i, MidpointRounding.AwayFromZero))));
// Ensure start and end point are correct, and not mangled by small rounding errors.
matchPal[0x00] = Color.FromArgb(toBlack.R, toBlack.G, toBlack.B);
matchPal[0xFF] = Color.FromArgb(toWhite.R, toWhite.G, toWhite.B);
// The 8-bit stride is simply the width in this case.
Int32 stride8Bit = width;
// Make 8-bit array to store the result
Byte[] imgBytes8Bit = new Byte[stride8Bit * height];
// Reset offset for a new loop through the image data
lineOffset = 0;
// Make new offset var for a loop through the 8-bit image data
Int32 lineOffset8Bit = 0;
for (Int32 y = 0; y < height; y++)
{
Int32 offset = lineOffset;
Int32 offset8Bit = lineOffset8Bit;
for (Int32 x = 0; x < width; x++)
{
Int32 toWrite;
// If transparent, revert to background colour.
if (imgBytes[offset + 3] <= 0x7F)
{
toWrite = bgWhite ? 0xFF : 0x00;
}
else
{
Color col = Color.FromArgb(imgBytes[offset + 2], imgBytes[offset + 1], imgBytes[offset + 0]);
toWrite = GetClosestPaletteIndexMatch(col, matchPal);
}
// Write the found colour index to the 8-bit byte array.
imgBytes8Bit[offset8Bit] = (Byte)toWrite;
offset += 4;
offset8Bit++;
}
lineOffset += stride;
lineOffset8Bit += stride8Bit;
}
// Make new 8-bit image and copy the data into it.
Bitmap newBm = new Bitmap(width, height, PixelFormat.Format8bppIndexed);
BitmapData targetData = newBm.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.WriteOnly, newBm.PixelFormat);
// get minimum data width for the pixel format.
Int32 newDataWidth = ((Image.GetPixelFormatSize(newBm.PixelFormat) * width) + 7) / 8;
// Note that this Stride will most likely NOT match the image width; it is rounded up to the
// next multiple of 4 bytes. For that reason, we copy the data per line, and not as one block.
Int32 targetStride = targetData.Stride;
Int64 scan0 = targetData.Scan0.ToInt64();
for (Int32 y = 0; y < height; ++y)
Marshal.Copy(imgBytes8Bit, y * stride8Bit, new IntPtr(scan0 + y * targetStride), newDataWidth);
newBm.UnlockBits(targetData);
// Set final image palette to grayscale fade.
// 'Image.Palette' makes a COPY of the palette when accessed.
// So copy it out, modify it, then copy it back in.
ColorPalette pal = newBm.Palette;
for (Int32 i = 0; i < 0x100; i++)
pal.Entries[i] = Color.FromArgb(i, i, i);
newBm.Palette = pal;
return newBm;
}
The used GetClosestPaletteIndexMatch function:
/// <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;
// Technically, Pythagorean distance needs to have a root taken of the result, but this is not needed for just comparing them.
Int32 distance = (redDistance * redDistance) + (greenDistance * greenDistance) + (blueDistance * blueDistance);
if (distance >= leastDistance)
continue;
colorMatch = i;
leastDistance = distance;
if (distance == 0)
return i;
}
return colorMatch;
}
The result:
