Warning

In this lab, the following topics will be dealt with:

Note the following conventions used in this assignment:

• Images are stored by float (single or double) matrices, and are normalized to $[0, 1]$ range.
• Discretized 1D functions of an intensity range $[0, 1]$ are stored in row vectors by function values ('$y$-values') only. This includes histogram(s), cumulative distribution functions (CDFs), or look-up-tables (LUTs). It is understood that the corresponding domain intensity values ($x$-values) can be obtained from a row vector by the following considerations:
• first element in the vector corresponds to intensity $x=0$
• last element in the vector corresponds to $x=1$
• the stepping between these two limits is uniform.
• Thus, for a vector h, the corresponding intensity values x can be obtained by

x = linspace(0, 1, length(h));

### Histograms and CDFs

Go to this page for better understanding of image histograms and CDFs.

### Getting started

Change to the directory where you unzipped the archive. Have a close look onto the provided functions/templates and try to run it in Matlab. Make sure that you understand the code well.

• negative
• threshold
• gamma correction
• logarithmic scaling
• quantization

Take a look at the function file get_monadic_operation.m. This function takes one or two arguments. The first argument is the (simplified) name of the monadic operation. The possible values for the operation name can be derived from the switch statement within the function. If the operation requires a parameter, it should be specified as the second argument. The function then returns a reference (“a pointer”) to a function that should perform the requested monadic operation. Your task is to implement these individual functions. They are located in the same script, below the described function - look for all the % TODO comments. Remember that the intensity range is $<0, 1>$ and some operation can create under/over-flow of the intensity values, which needs to be fixed.

Once implemented, you can test the operations via the script hw_monadic_ops_1.m (trying individual operations) or hw_monadic_ops_2.m. The second script tests all the operations in one go.

Here are images generated by the second script, which you can compare to the outputs of your implementation: Basic monadic operation examples.

### Histogram equalization

Implement a function for histogram equalization into the file hist_equalization.m. The histogram equalization algorithm must be implemented without using related special Matlab functions: histeq, cdf, hist. Use only basic programming structures, array/matrix indexing and mathematical operations (sum function is allowed).

Here is a template of the main function:

function eq_img = hist_equalization(img)
intensity_levels = 256;
img_size = size(img);

% compute the image CDF
img_cdf = compute_cdf(img, intensity_levels);  % <= this function needs to be also implemented!

% equalize the image
eq_img = zeros(img_size);
% TODO: implement the histogram equalization algorithm here
end

Finish the parts of the code marked % TODO, then you can test the function using the hw_monadic_ops_3.m script. You will also need to implement the helper functions compute_hist and compute_cdf. Again, the same restrictions as for the main function apply (no built-in Matlab functions for histogram or CDF computation, etc.).

The original image: The equalized image (output of the hw_monadic_ops_3.m script):

Note that the compute_hist function can be implemented in two valid ways:
• A - regularly sample N bin centers between 0 and 1 (first and last bin have half the width of the other bins)
• B - regularly sample N+1 bin borders between 0 and 1

Brute will give you both reference solutions for comparison.

### Histogram matching

Have a look at these two images:

The levels of the one on the right (target image) have been adjusted by hand in photo editing program. The left one (input image) was taken by a cheap camera and not edited in any way. You can see that many of the details on the left image are drowned out. To fix this, we would like to bring the histogram (and CDF) of the input image as close as possible to the histogram (and CDF) of the target image. Instead of doing it by hand, we would like to do it automatically. Methods which do this are called histogram matching.

We know that any image can be intensity-normalized by equalization:

This suggests that a transformation which would make the histograms of input and target close would be the one which first transforms the input to an equalized one by cdf_input, and then transforms by the inverse of cdf_target.

Practically, there are several ways how to do it. One option is to simply invert the cdf_target function (as any normal function). Then, you can simply compute:

$image\_matched = cdf\_target^{-1}(cdf\_input(input))$

as shown in the lecture. The issue with this is that the transformation function (in this case $cdf\_target^-1$) needs to be strictly monotonic and defined for all possible intensity levels of the input image. Neither of these conditions are guaranteed for a simply inverted function. To solve this, you can make use of the following Matlab functions:

linspace, unique, interp1

Another option is to find for each possible input value (intensity level) of the $cdf\_input$ function the input value of the $cdf\_target$ for which the output equals for both functions. This will tell us directly to which intensity value should we transform the intensities in the input image. The following illustration depicts the process:

Again, in practice, there are some issues. Mainly, that the CDFs might not have exactly matching output values. Thus, the closest matching value must be found instead.

For both approaches, the computed function (or rather, a lookup table) is used to transform the input image. Beware of the following:

• indexing of arrays in Matlab starts from 1
• intensity levels of the input and output images are in the range $I \in <0, 1>$ (i.e., not suitable for indexing of arrays)
• integer based intensity values of images with 256 intensity levels are in the range $I \in <0, 255>$

Your task is to implement histogram matching, using either of the described approaches into the match_hists function:

function img_matched = match_hists(img, img_target, intensity_levels)
if ~exist('intensity_levels', 'var')
intensity_levels = 256;
end

% get both CDFs
% TODO

% create histogram matching lookup table
matching_lut = zeros(intensity_levels, 1);
% TODO

% match the histograms
% TODO
end

Once this function is available, you can test its functionality via the hw_monadic_ops_4.m script. Here is an example of histogram matching:

Histogram matching can also be used to match an image, which was somehow calibrated, e.g., in case of satellite images.

### Assignment summary

To fulfil this assignment, you need to submit these files (all packed in a single .zip file) into the upload system:
• get_monadic_operation.m : Given the arguments operation and parameter (if applicable), returns the requested monadic operation function reference. The main task is to implement the individual monadic functions within that file.
• operation, parameter → operation_ref
• compute_hist.m : Computes the (normalized) histogram of the given image. No hist or similar image processing Matlab functions can be used, only basic mathematical operations.
• img → img_hist
• compute_cdf.m : Computes the cumulative distribution function of the given image. No cdf, hist or similar image processing Matlab functions can be used, only basic mathematical operations.
• img → img_cdf
• hist_equalization.m : Equalizes the histogram of the given image. No histeq, cdf, hist or similar image processing Matlab functions can be used, only basic mathematical operations.
• img → eq_img
• match_hists.m : Matches the histogram of one image close to the histogram of another image. No histeq, cdf, hist or similar image processing Matlab functions can be used, only basic mathematical operations.
• img → matched_img

All of the function described above are included in the template zip file as templates to be implemented by you. These template functions are functional in the sense they produce some output - usually identity function (i.e., copy input image to the output) - so that the test scripts (the ones named hw_monadic_ops_*.m) work out of the box. Your task is to replace and/or finish the marked parts of the functions (with % TODO) so that they perform the required operations. There might be some parts of the code for convenience (e.g., input validity checking) or some suggested structure. You can change these, unless specified otherwise in the code comments. However, you must never change the function signature (name, inputs/output variable names and counts - for example, you must never add more inputs to a function).

You will be given the following functions to get you started (you do not need to submit these):

• get_image.m : reads an image fname to 2D matrix img. The output image img adheres to the conventions above (range, type).
• fname → img
• image_hist_cdf : computes histogram and CDF of an image (not to be used in hist_equalization or match_hists).
• im, Nbins → bin_centers, h, cdf
• showim_hist_cdf : just shows the use of subplot to show img, its histogram and CDF in a single Figure.