DMMD

In trying to come up with better methods of organizing and presenting concepts related to Intuitive Mathematics, nothing seems to work better than using LaTeX. Therefore, the latest PDF manual (generated with LaTeX) will always be available for download here.

Certain chapters from the Intuitive Mathematics manual will also be presented in these blog pages.

– Darian Muresan

What exactly is histogram equalization and how can we think of it from an intuitive point of view, rather than the more abstract, mathematical point of view? A somewhat detailed technical point of view is given on the Wiki Page. Still, I believe there are some mathematical concepts, which I believe can be explained more intuitively. Here’s my take on histogram equalization.

Without being too rigorous about the mathematical details and the distinction between discrete and continuous cases, let’s understand how histogram equalization is implemented.

First, what exactly is histogram equalization? Ideally, histogram equalization would spread the pixel values uniformly across an entire image. Thus, if we had an image with 256 pixels in it, then 1 pixel would have value 0, 1 pixel would have a value of 1, …, and one pixel would have a value of 255. If the image had 1024 total pixels, then the normalized image would have 4 pixels of value 0, 4 pixels of value 1, …, and 4 pixels of value 255. However, knowing how to spread the pixel values around an image, such that we have a uniform distribution as described above, can be tricky. Instead, what histogram equalization does (in the discrete case) is that it spreads and adjusts the level of the pixel values (as a group) in the histogram such that the cumulative area under the new histogram (moving from left to right) increases linearly.

A simple example might be in order. Assume that image I contains 6 pixels: two of value 10, two of value 20 and two of value 199. Further, assume that each pixel can be represented using 8 bits (i.e. minimum value is 0 and maximum is 255). Then the histogram equalized image would have two pixels of value 0, two pixels of value 128 and two pixels of value 255.

Second, let’s understand histogram equalization in more details. The Figure above shows the histogram of some image I. The histogram is a distribution function that tells how many pixels are at a certain pixel value. The x − axis is the pixel value, such as pixel value i, and the y − axis is the count, or the number of pixels of value i. Histograms are not 1-to-1 with the image. For example, two different images, I and J can have the same histogram if the locations of the pixels in I are permutations of the pixel locations in J.

The cumulative distribution function (cdf) is the cumulative area under the histogram curve. In the continuous case, this area is an integral and in the discrete case, it is a sum. The cdf(i) is calculated as the area under the histogram curve, up to pixel i.

In the figure above, the cdf(i) is the red line in the bottom graph. (Notice that the line is monotonically increasing, since the area under the histrogram curve can only increase as we move from left to right. Also note, that the red line is an approximation of the cdf.) The top graph shows the histogram of image I. At step i (pixel value i) the cdf function increases by the sum Si.

In the following figure, the green line represents the cumulative distribution function for the normalized histogram, call it cdf_norm (shown in the figure as having a bar on top). The cdf_norm is a straight line because the integral of a constant function is a straight line and it has a slope of 1 because both axis have been normalized to [0, 1].

In order to convert cdf into cdf_norm, the sum contribution, which is Si along the y-axis, needs to be made at exactly the same time as when the step Si is taken along the x-axis (i.e. when we are adding the contribution of pixel Si). If this is true for all steps before step i, then step i needs to be moved to cdf(i). This is achieved by simply assigning all the pixels that were of value i to be of value cdf(i). Note that the number of pixels that were of value i is the SAME as the number of pixels that are now of value cfd(i). The sum Si, the contribution to the y-axis, does not change when the pixels of value i are changed to cdf(i).

Finally, if the desire is to convert cdf(i) to some new cumulative distribution function, call it cdf_new(i) (shown as cdf with a hat in the figure below) then this can be achieved by re-assigning i to the inverse of cdf_new of cdf(i). This mapping is shown in the figure below.

The figures above try to capture and explain the logic behind histogram equalization and histogram re-mapping. The DMA Manual has a more detailed mathematical explanation (in the chapter titled dmaHistogramEqualization).

– Darian Muresan