Description
Problem 1. Adaptive Histogram Equalization (10 points)
It is often found in image processing and related fields that real world data is unsuitable for
direct use. This warrants the inclusion of pre-processing steps before any other operations are
performed. An example of this is histogram equalization (HE) and its extension adaptive histogram
equalization (AHE).
The goal of this problem is to implement a function for AHE as described in Chapter 1 of
Adaptive Histogram Equalization – A Parallel Implementation1
. The function has the following
specifications:
(i) The desired function AHE() takes two inputs: the image im and the contextual region size
win size.
(ii) Using the pseudocode in Algorithm 1 as a reference, compute the enhanced image after AHE.
(iii) You may use loops if necessary. You should not make use of any inbuilt MATLAB/Python
functions for AHE or HE.
(iv) The function returns one output: the enhanced image after AHE.
Algorithm 1 Pseudocode for Adaptive Histogram Equalization of an Image
*Pre-requirement : Pad the image im on all 4 sides by mirroring intensity values so that the
contextual region for edge pixels remains valid. This can be done in MATLAB using padarray()
or Python using numpy.pad() with the ’symmetric’ argument.
1: function ahe(im, win size)
2: for each pixel (x, y) in image im do
3: rank ← 0
4: contextual region∗ ← (win size × win size) window centered around (x, y)
5: for each (i, j) in contextual region do
6: if im(x, y) > im(i, j) then
7: rank ← rank + 1
8: output(x, y) ← rank × 255/(win size × win size)
9: return output
Evaluate your function on the image beach.png for win size = 33, 65 and 129. In your report,
include the original image, the 3 images after AHE, and the image after simple HE (you may use
MATLAB/Python inbuilt function for HE). Make sure to resize all images to ensure they do not
take up too much space. Additionally, include your answers (no more than three sentences each)
to the following questions:
• How does the original image qualitatively compare to the images after AHE and HE respectively?
• Which strategy (AHE or HE) works best for beach.png and why? Is this true for any image
in general?
1You can find this article here.
2
Problem 2. Binary Morphology (10 points)
In this problem, you will be separating out various objects in binary images using morphology,
followed by connected component analysis to gather more information about objects of interest.
(i) For the binary image circles lines.jpg, your aim is to separate out the circles in the image,
and calculate certain attributes corresponding to these circles.
• The first step is to remove the lines from the image. This can be achieved by performing the opening operation with an appropriate structuring element. You may find the
following functions to be of use.
MATLAB: imopen(), strel();
Python: skimage.morphology.opening()
Feel free to try other functions as well for this question.
• Once we have a binary image with just the circles, the individual regions need to be
labeled to represent distinct objects in the image i.e. connected component labeling.
This can be done in
MATLAB using the function bwlabel();
Python using scipy.ndimage.measurements.label().
Feel free to try other functions as well for this question.
• We now have access to individual regions in the image, each of which can be analyzed
separately. For each labeled circular region, calculate its centroid and area. Tabulate
these values for each connected component. You may use loops for this part of the
problem.
Note : This step must be performed entirely by your code without making use
of MATLAB/Python’s inbuilt functions (like regionprops()) for connected
component analysis. You can still use simple utility functions like sum(),
mean(), find() etc.
(ii) In this part, we are interested in performing similar operations on the binary image lines.jpg.
Your aim now is to separate out the vertical lines from the horizontal ones in the image, and
then calculate certain attributes corresponding to these vertical lines.
• In a similar manner to part (i) above, use the opening operation with a suitable structuring element to remove the horizontal lines in the image.
• Next, perform connected component labeling on the resulting image to identify and label
each unique vertical line.
• Finally, for each labeled region, calculate the length (the longer dimension) and the
centroid. Tabulate these values for each connected component. You may use loops for
this part of the problem.
Note : This step must be performed entirely by your code without making use
of MATLAB/Python’s inbuilt functions (like regionprops()) for connected
component analysis. You can still use simple utility functions like sum(),
mean(), find() etc.
Things to turn in:
3
• Part (i) & (ii) : The original image, the image after opening, the image after connected component labeling (plot with colorbar), and a table with the desired values for each component.
• The structuring element type and size that was used to perform the opening operation (for
both parts).
• Codes for the problem .
Problem 3. Lloyd-Max Quantizer (10 points)
For this part of the homework, we study the Lloyd-Max quantizer. Before you get started, carefully
study pages 602-603 of the book2
. Then, proceed to implement the following:
(i) Write a function that takes as inputs a greyscale 8-bit (uint8) image, a scalar s ∈ [1, 7] and
performs uniform quantization over the entire range [0, 255] so that the output is quantized
to an s-bit image. You may use loops for this part if necessary.
(ii) The m-file lloyds.m is found in the communications toolbox in MATLAB. It performs Lloyd
Max quantization (optimal quantization in the squared error sense). If you don’t have this
toolbox (it’s not standard with the student version), lloyds.m (along with its dependencies)
is provided in the data folder. You can use this function 2 ways:
[partition, codebook] = lloyds(training_set, initcodebook)
where you give it an initial codebook, or
[partition, codebook] = lloyds(training_set, len)
where len is the size of the codebook desired.
The input training set is a vector of training data (which is used as an empirical measure of
the probability mass function), so you will have to reshape your image by
[M,N] = size(image);
training_set = reshape(image,N*M,1);
For the images lena512.tif and diver.tif, calculate the MSE values for s ∈ [1,7] using both
your uniform quantizer and the Lloyd-Max quantizer (you may use loops for the Lloyd-Max
quantizer as well). Plot the results (MSE versus number of bits).
Show one plot for lena512.tif
(with both uniform and Lloyd-Max quantization) and another plot for diver.tif. Compare the
results for the different quantizers/images and explain them. That is, why does one quantizer
outperform the other, and why is the performance gap larger for one image than for the
other?
Note : You should not make use of MATLABs immse() function for calculating the MSE
values.
2
Included in the data folder.
4
(iii) Now use global histogram equalization on lena512.tif and on diver.tif to generate two new
images, for example:
a = histeq(lena512,256);
Repeat part (ii) for these two new images. Compare them with the previous set of plots.
What has happened to the gap in MSE between the two quantization approaches and why?
(iv) Why is the MSE of the 7-bit Lloyd-Max quantizer zero or near zero for the equalized images? One might have thought that equalization is not to the advantage of the Lloyd-Max
quantizer, because equalizing the histogram should be flattening the distribution, making
it more uniform, which should be to the advantage of the uniform quantizer. Explain this
phenomenon.
5
