4
$\begingroup$

When output histogram is not same as reference histogram, why is the method called histogram equalization?

For example below are two figures from http://en.wikipedia.org/wiki/Histogram_equalization. The output histogram (2nd figure) looks nothing like a discrete uniform distribution. Why is it called "equalization" then? input image histogram output image histogram

$\endgroup$
4
$\begingroup$

To answer your question histogram equalization is called like this because its function is to produce an equalized histogram (that is an uniform probability density function).

There are different algorithms that may approach this function, and obviously there is a problem in the example that is shown:

  • In fact, the algorithm used there will always have trouble producing a flat histogram when mapping the function to a discrete set of 256 (except when the input histogram is already flat!)
  • As a consequence, the cumulative histogram shows discrete jumps which produce this non-regular output histogram.

Why is this simple algorithm still used? Because,

  1. the output image will often good enough for the initial purpose, that is to maximize the range of intensities used in the image - though the histogram may look ugly...
  2. it is simple!

There are simple alternatives. The simplest is to use a linear interpolation of the cumulative function.

  • Theory: In general terms, the method may be easily derived if we know the probability distribution function $dP_{i}$ of variable $a_i$ representing the luminance image at pixel $i$. Indeed, by choosing the non-linearity as the cumulative distribution function transforming any observed variable $\bar{a}_i$ into: $$ z_i(\bar{a}_i)= P_{i}(a_i \leq \bar{a}_i) = \int_{-\infty}^{\bar{a}_i} dP_{i}(a_i)% $$ This is equivalent to the change of variables which transforms the luminance image to a variable with uniform probability distribution function in $[0, 1]^M$.

  • Evaluation: In physiology (retina for instance), this distribution is assumed to be sampled for each "pixel" (photoreceptor in mammals) over time (for instance, something like "the probability distribution over last minute"). In image processing, when handling one single image, you can assume stationarity over space, that is compute the histogram over all pixel values.

  • Algorithm: now that we have all in place, some example algorithm in python:

Sample code:

import numpy as np
from scipy.misc import lena
I = 1. * lena()
I = (I - I.min())/(I.max()-I.min())
import matplotlib.pyplot as plt
# the cumulative histogram
n_quant = 40
(hist, bins) = np.histogram(I.ravel(), bins=np.linspace(0., 1., n_quant+1), normed=True)
P = np.cumsum(hist/np.sum(hist))
# equalization
I_z = np.interp(I, np.linspace(0., 1., n_quant), P)
(hist_z, bins) = np.histogram(I_z.ravel(), bins=np.linspace(0., 1., n_quant+1), normed=True)
plt.bar(np.linspace(0., 1., n_quant), hist, color='r', alpha=.3, width=1./n_quant)
plt.bar(np.linspace(0., 1., n_quant), hist_z, color='b', alpha=.3, width=1./n_quant)
plt.title('Histogram of Lena')
plt.xlabel('luminance')
plt.ylabel('probability')
plt.xlim((0,1.))
plt.savefig('equalization.png')

The output (red is raw histogram, blue is equalized). As you can see, there are variations, but it looks better :-). Notably, you have less "jumps" around most popular values. The parameter n_quant is important to tune smoothness versus precision.

output of code

$\endgroup$
  • 1
    $\begingroup$ Yes, please describe another algorithm which tries to do equalization in a different way. $\endgroup$ – user13107 Jan 17 '14 at 4:46
2
$\begingroup$

To make a signal with that distribution have a truly uniform distribution would probably require that the transformation used be time-varying: a value $10$ at time $t_0$ would be moved to, say, a value of $15$, but a value $10$ at time $t_1$ (later) would be moved to, for example, $20$.

So, what the equalizer tries to do is to make the cumulative distribution of the signal as linear as possible.

The cumulative distribution linearization approach allows a transform of the form: $$ y(t) = T[x(t)] $$ where $T[x_1]$ always maps to $y_1$, regardless of the time at which it occurs. There's a bit more explanation of the details on Wikipedia.


Edit: Not sure if this is quite what you're after, but I tried implementing what I suggested to get a fully uniform distribution in the pixel values. The scilab code is below.

For the simple example I chose, it did a reasonable job.

enter image description here


Code:

f = scf();
t=-%pi:0.1:%pi;
m=sin(t)'*cos(t);
m = 10*round(m*10);
clf()
subplot(221);
grayplot(t,t,m);
subplot(222);
histplot(100,m)
subplot(223);

[sorted,indices] = gsort(m);
m_equalized = zeros(m);
N = length(indices);
val_max = 1;
val_min = 0;
vals = [0:N-1]/(N-1)*(val_max - val_min) + val_min;

m_equalized(indices) = vals;
grayplot(t,t,m_equalized);

subplot(224)
histplot(100,m_equalized)

f.color_map = graycolormap(32);
$\endgroup$
  • $\begingroup$ 1. I'm not able to understand the time varying factor w.r.t. an image. 2. If we take euclidean distance between equalizer output and discrete uniform distribution; is it the least if we follow the procedure of making cumulative distribution as linear as possible? Or can some other transformation be proved to give the minimum distance? $\endgroup$ – user13107 Jan 16 '14 at 16:57
  • $\begingroup$ 1: In the case of an image, time -> x axis / y axis. 2: I do not think it will be... but then the "least" would give you non-sensical output: you could get close to a "perfect" uniform distribution if you just sorted the input pixel values and rescaled them linearly so that the smallest one was 0 and the largest one was 255 (for 8-bit greyscale). I do not think that's a sensible answer to the question, though.... I might try to implement something in scilab later.... $\endgroup$ – Peter K. Jan 16 '14 at 17:15
  • $\begingroup$ Thanks. Can we qualitatively say what exactly is preserved in HEq? Can we say that because the transformation is monotonic the image is preserved (unlike in sorting)? $\endgroup$ – user13107 Jan 16 '14 at 18:45
2
$\begingroup$

If I hand you a uniform distribution spanning say, 0 to 1, then I can say that the probability of a variable with this uniform distribution taking on value of say, 0.3 is, equal to the probability that it takes on a value of 0.7, or 0.01, or 0.93, etc.

In other words, since the uniform distribution is flat, all probability values are equal.

Now forget about distributions, imagine a histogram from an image. If you make an image histogram, you are just measuring the popularity of all pixel values from say, 0 to 255. If all pixel values that take on a value of 0, (black), are equal to the number of pixels that take on a value of 255, (white), are equal to the number of pixels taking on a value of 123, (greyish), etc etc, then the histogram is an equalized histogram. Again, "equalized" because all pixel-popularity measures are the same.

However not all images have this same spread. If you take a picture of a scene with the sun photo-bombing it in the background at noon, most of your pixels live around the 255 area, because the sun has made most pixels white, even if they were not white to begin with.

In this case, the histogram will be heavily skewed to the right. Now, the number of pixels that are white, is NOT equal to the number of grey pixels, or the number of black pixels, etc etc.

So in histogram equalization, this we force all the pixels to take on values, such that when you come to measure the pixel popularities in the end, then will all have equal values. Hope that helps!

Edit: Not that is we could force all pixel values to have a certain distribution, but in that case we have no guarantee that it will correspond in some form to the original image. This why you might not see a properly uniform distribution after equalization. Histogram equalization will try to make the PDF as uniform as possible, while at the same time respecting the original properties of the image.

Lastly but most importantly, histogram equalization was initially developed by assuming continuous random variables. If the original image has intensities modeled as a continuous random variable $X$ with pdf $p_x(x)$, and the HEQ image result's intensities as a continuous random variable $Y$ with PDF $p_y(y)$, then $p_y(y)$ will be a uniform distribution, if we transform the random variable $X$ by its own CDF, $T$. That is, $Y$ will be a uniformly distributed continuous random variable if we set $Y = T(X)$. However, this is for the continuous case. For real images that are discrete, we are estimating a discrete CDF $T$ from coarse quantization levels, and applying it to a specific number of pixel values. This is why we will not get a perfectly uniform histogram result. Theory proves equalization for a continuous case, while in practice, we are dealing with discrete and quantized images and imperfect CDF estimation no less.

$\endgroup$
  • $\begingroup$ I think the confusion stems from the fact that the output histogram may not look flat. In fact, I think that your last statement that says that the pixel popularities will have equal values is false, and is exactly what the OP was expecting to see but didn't. $\endgroup$ – nispio Jan 22 '14 at 23:02
  • $\begingroup$ @nispio See my edits. $\endgroup$ – Tarin Ziyaee Jan 23 '14 at 1:52
1
$\begingroup$

After doing some math, I think we can see why it's called equalization when we consider the continuous variable case.

If $y = g(x)$ then we can show that $f_{Y}(y)=f_{X}(x)\cdot |{dx \over dy}|$ where $f$ is the density function. If we equate $f_{Y}(y)$ to a uniform distribution (which is the aim of equalization), we get $f_{X}(x)\cdot |{dx \over dy}| = 1$ within the range of $X$.

Hence, $dy = f_{X}(x)dx$ or $\int_{0}^y dy = \int_{-\inf}^x f_{X}(x)dx$

$y = \int_{-\inf}^x f_{X}(x)dx = F_{X}(x)$

or $g(x) = F_{X}(x)$ which is what we do in the standard histogram equalization method.

In discrete case even though final distribution doesn't look like discrete uniform distribution, it's the best approximation that is theoretically possible. Also this is useful Lesser bins histogram looks more equalised than higher bins histogram after histogram equalisation?

$\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.