Histograms, Histogram Processing, Equalization, Matching, Image Thresholding

Histogram

A histogram (or brightness histogram) of an image denotes the frequencies of the brightness levels in an image.

To compute the histogram, we first create an array of 0s (size of the array=number of gray-levels). Then, for each pixel, we check the intensity value and increment the count for the corresponding array element.

h(i) will denote the number of times the intensity level i is present in the image i.e. $n_i$.

The histogram of an image is usually represented using a bar graph. Consider the following image and its histogram:

Note that several images can have the same histogram if they have the same intensity distribution. Histograms therefore don't depend on the objects contained by the image, but only depend on the intensity distribution.

Probability Density Function (PDF)

The PDF of a histogram is computed after normalizing the histogram by the image size, and it represents the probabilities of occurrences of different intensity values in a given image.

$p(i)=\frac{h(i)}{image\_size}$ and $\sum_{i=1}^{L}p(i)=1$

The following is the PDF of the histogram shown earlier:

Cumulative Distribution Function (CDF)

The CDF is obtained by taking a cumulative sum of the probability values from thr PDF.

$CDF(X) = \sum_{-\infty}^{X} p(i)$

The max. value in a CDF is 1.

The following is the CDF computed from the PDF shown earlier:

Histogram Equalization

Histogram Equalization is the process of enhancing the contrast of an image by modifying the intensity distribution of its histogram.

Ideally, the equalized histogram should have a uniform flat distribution. However, in practice, this is not the case. This is because histogram equalization will only move existing bins but will not redistribute them. So, the bins will get spaced out or compressed but will not change in height. This happens because of the discrete nature of the histogram. Also, while computing the CDF, we approximate the continuous integral using a discrete summation, thereby affecting the outcome.

Implementation: new_intensity(x,y) = (L-1) CDF(intensity(x,y)); where L is the number of gray levels

After equalization, we expect the histogram to become flatter (if not completely flat) and the CDF to become linear.

The following denote the image, histogram, PDF and CDF after equalization:

Histogram Matching

Histogram Matching is a process that aims to make the histogram of one image (that lacks contrast/clarity) match that of another image (that has good contrast/clarity). This is usually used to enhance the quality of the first image.

It is performed by first computing the CDFs of both the images followed by a mapping between them using a lookup table.

Image Segmentation and Thresholding

Image segmentation is the process of subdividing an image into its constituent regions or objects.

Thresholding (also called gray-level thresholding) is one of the most common ways to perform segmentation.

We decide which pixels do/don't belong to an object based on their intensity values being greater than/lesser than a certain threshold.

If the image is denoted by f(x,y), the image after segmentation g(x,y) is obtained using:

$g(i,j) = \begin{cases}1, & f(i,j)\gt T\\0, & f(i,j)\leq T\\\end{cases}$

where T is the threshold, and g(i, j) = 1 for pixels of objects, and g(i, j) = 0 for pixels of the background (or vice versa).

The threshold can be determined using:

• trial and error

• the histogram of the image

Thresholding is computationally inexpensive and fast and can also be used for real-time image segmentation.

In practice, a single global threshold will not be enough to perform segmentation on the whole image. Adaptive thresholding (using different local thresholds for different parts of the image) is the solution.

Thresholding using Histogram of the Image

For images where the objects are well-separable from the background, the histogram will be bimodal i.e. it will have two peaks: one for the intensities corresponding to the object pixels and the other corresponding to the background pixels. In such a case, it is easy to set the threshold for segmentation as the gray-level that has minimum frequency between the two maxima.

Similarly, multiple thresholds can be set if a histogram is multimodal.

The image above shows the thresholds set for bimodal and multimodal histograms.

In practice, however, factors such as noise and illumination make it difficult to easily separate the object from the background. In such cases, the histogram will not directly provide the optimal threshold.

Optimal Thresholding involves obtaining an optimal threshold(s) by approximating the histogram of an image as the weighted sum of class-specific PDFs. The threshold is set as the gray-level corresponding to the minimum probability between the maxima of two PDFs. This results in minimum error segmentation i.e. the smallest number of pixels get mis-segmented.