# How to Reverse Color Quantization?

Are there any algorithms that attempt to perform the inverse of color quantization on an image? In other words, is there a smart way to increase the bit depth of image?

The obvious answer would be to simply stretch the values of all pixels to fit the new range; however, that would leave gaps in the histogram, and the resulting image would still have the same number of different values. Are there any algorithms that, for example, take neighboring pixels into consideration in order to determine a better estimation for each pixel?

Are there any algorithms that, for example, take neighboring pixels into consideration in order to determine a better estimation for each pixel?

That would essentially be a low-pass filter.

So, yes, that exists, and is commonly used.

You can see that very nicely if you take e.g. an old computer graphics sprite, and scale it as a high-color-resolution image:

# scaled by a simple linear interpolation filter (512 px)

While the simply scaled image has as much discrete colors as the original, the linearly interpolated one has a lot more colors, and the histogram looks much more "continuous".

But:

There's no free lunch, usually. You can't just add color information back! (not being able to add back lost info is one of the fundamental truths of Information Theory, by the way). You have to sacrifice spatial resolution. Essentially, it's the same math that underlies Heisenberg's Uncertainty Principle. You can either have perfect info state of something (the color of a pixel, the impulse of a electron), or its position (sharp edges in an image, knowledge of the position of an electron). See this example:

# filtered to achieve a much more continuous color histogram, with a radius of 10px taking into consideration

• I am thinking of an operation in which, ideally, quantizing the recovered image would result on the same input image again. I think this may not be the case for every low-pass filter. Maybe we could achieve that by choosing a filter that ensures that pixels on the recovered image won't have their values changed by more than half of the quantization step? Commented Jun 21, 2017 at 16:37
• That perfect reconstruction is – by the very definition of what quantization is – impossible. Basically, a color space has the same cardinality as a power of the Real Numbers, whereas any quantized space is by definition countably finite, so almost all input values cannot be represented, or, corrolarily, infinitely many input values map to one quantized value.Hence,your reconstruction is always going to be an approximation;your job is to find one that has the minimum deviation from the original,but you'll need to find a measure for "deviation" first to even get started.Can't do that for you! Commented Jun 22, 2017 at 8:08
• The low pass filter I chose works well as illustration for the very type of imagery I mentioned – look at the noisy, speckled photo: It could have used a bit of low-pass filtering in the first place, so that the reduction in spatial exactness due to the lpf after quantization isn't really all that bad. I wanted to illustrate that it's your problem to first define in what mathematically measurable way you want your reconstruction to be as good as possible, and then things get easier. Problem is that we don't know what you need and hence can't even give you pointers to an appropriate measure Commented Jun 22, 2017 at 8:12

I'd suggest using a more sophisticated spatial filter - i.e. bilateral filter, to minimize the damage to the boundaries.

Probably better than a plain low pass filter:

https://github.com/kornelski/undither

I couldn't get it work for the example picture from the accepted answer, but the example pictures from its website look promising.