0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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:

original (32 x 32 px)

libreoffice database Icon

scaled without interpolation filter (512 px)

libreoffice database icon scaled to 512x512

scaled by a simple linear interpolation filter (512 px)

libreoffice datababase icon linearly interp 512x512

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:

original photo

original

original (512 x 512px) reduced to 16 colors

original, color-reduced

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

original, Gaussian filter

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – guissoares Jun 21 '17 at 16:37
  • $\begingroup$ 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! $\endgroup$ – Marcus Müller Jun 22 '17 at 8:08
  • $\begingroup$ 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 $\endgroup$ – Marcus Müller Jun 22 '17 at 8:12
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.