Reverse (remove) anti-aliasing filter

Question

I have a set of anti-aliased greyscale PNG images. I need to know how to programatically revert the anti-aliasing effect and get sharp edges again.

I'm using GDI+ but I am less interested in code. I need an algorithm.

The greyscale images (should) contain only 6 colors (or different shades of grey). This is so that later on I can re-color them using a Color-Lookup filter. However, when the images where saved, Photoshop automatically applied anti-aliasing so the edges were blurred (because the Bicubic Interpolation mode was enabled). I need to revert that effect.

Here is an example:

This is a screenshot from Photoshop

Someone suggested that I should apply a Sharpen filter, so I tried it on photoshop. Here is how it looks:

Even though the outer edges are fine, the edges where 2 different colors meet show artifacts.

EDIT:

This is how I ended up doing it. It is very much improvised and can probably be done better and faster, but I couldn't find any better solution.

The idea is to iterate over each pixel, get its direct neighbors and compare its color to theirs. If it's backed by at least 2 pixels of same color, it checks if the neighbor pixel is backed as well. If not, it replaces the neighbor pixel with its own.

Code:

    private static void Resample(Bitmap bmp)
    {
        // First we look for the most prominent colors
        // i.e. They make up at least 1% of the image
        Hashtable stats = new Hashtable();

        for (int x = 0; x < bmp.Width; x++)
        {
            for (int y = 0; y < bmp.Height; y++)
            {
                Color px = bmp.GetPixel(x, y);
                if (px.A == 0)
                    continue;

                Color pxS = Color.FromArgb(255, px);
                if (stats.ContainsKey(pxS.ToArgb()))
                    stats[pxS.ToArgb()] = (int)stats[pxS.ToArgb()] + 1;
                else
                    stats.Add(pxS.ToArgb(), 1);
            }
        }

        float totalSize = bmp.Width*bmp.Height;
        float minAccepted = 0.01f;
        List<int> selectedColors = new List<int>();

        // Make up a list with the selected colors
        foreach (int key in stats.Keys)
        {
            int total = (int)stats[key];
            if (((float)total / totalSize) > minAccepted)
                selectedColors.Add(key);
        }

        // Keep growing the zones with the selected colors to cover the invalid colors created by the anti-aliasing
        while (GrowSelected(bmp, selectedColors));
    }

    private static bool GrowSelected(Bitmap bmp, List<int> selectedColors)
    {
        bool flag = false;

        for (int x = 0; x < bmp.Width; x++)
        {
            for (int y = 0; y < bmp.Height; y++)
            {
                Color px = bmp.GetPixel(x, y);
                if (px.A == 0)
                    continue;

                Color pxS = Color.FromArgb(255, px);

                if (selectedColors.Contains(pxS.ToArgb()))
                {
                    if (!isBackedByNeighbors(bmp, x, y))
                        continue;

                    List<Point> neighbors = GetNeighbors(bmp, x, y);
                    foreach(Point p in neighbors)
                    {
                        Color n = bmp.GetPixel(p.X, p.Y);
                        if (!isBackedByNeighbors(bmp, p.X, p.Y))
                            bmp.SetPixel(p.X, p.Y, Color.FromArgb(n.A, pxS));
                    }
                }
                else
                {
                    flag = true;
                }
            }
        }

        return flag;
    }

    private static List<Point> GetNeighbors(Bitmap bmp, int x, int y)
    {
        List<Point> neighbors = new List<Point>();

        for (int i = x - 1; i > 0 && i <= x + 1 && i < bmp.Width; i++)
            for (int j = y - 1; j > 0 && j <= y + 1 && j < bmp.Height; j++)
                neighbors.Add(new Point(i, j));
        return neighbors;
    }

    private static bool isBackedByNeighbors(Bitmap bmp, int x, int y)
    {
        List<Point> neighbors = GetNeighbors(bmp, x, y);
        Color px = bmp.GetPixel(x, y);
        int similar = 0;
        foreach (Point p in neighbors)
        {
            Color n = bmp.GetPixel(p.X, p.Y);
            if (Color.FromArgb(255, px).ToArgb() == Color.FromArgb(255, n).ToArgb())
                similar++;
        }

        return (similar > 2);
    }

Result: Original Image: http://i.imgur.com/8foQwFe.png

De-anti-aliased Result: http://i.imgur.com/w6gELWJ.png

Answer 1

The reversing procedure of a filter is called Deconvolution (Which is a specific case of the General Inverse Problem).
There are two types of Deconvolution:

1. Non Blind Deconvolution - Where the operation on the image is known (For instance the coefficients of the Low Pass Filter applied are known).
2. Blind Deconvolution - Where the applied filter is unknown specifically, only some assumptions about it are assumed (Such as being an LPF or Spatially Invariant, etc...).

Those are usually (Any of them) complex algorithms which take time (Unless using the naive "Wiener Filter" approach).

Assuming the filter is some kind of LPF poor's man solution would be some kind High Pass Filter (HPF). Any of those would give a look of "Sharper Image" and "Enhanced Edges". Known filter of this type is the Unsharp Mask:

1. Apply LPF on the image (Usually using Gaussian Blur with a given STD). Let's call it lpfImage.
2. Calculate the difference image: diffImage = originalImage - lpfImage.
3. The "Unsharp Mask Image" is given by: usmImage = originalImage + (alpha * diffImage)
   Where alpha is a predefined scaling factor of the "Sharpening" level.

Enjoy...

Answer 2

I would try Color Quantization.

You need to build some type of color histogram and get top most used colors from your image. Probably it will be your initial colors before smoothing.

Create a color palette with top 6 colors.

Convert your raster PNG to indexed PNG.

I’m not sure GDI+ can create indexed PNG, but there are a lot of SDK’s which can handle that.