Monadic Operations

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

• histograms and CDFs
• basic monadic operations
• histogram equalization
• histogram matching

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

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

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.

Your first task is to implement the following basic monadic operations, as defined in the lecture:

• negative
• threshold
• brightness adjustment
• gamma correction
• contrast adjustment
• non-linear contrast adjustment
• 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.

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):

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:

Tuesday 2023-10-17, 23:59:00

Please note: Do not put your functions into any sub-folders. That is, when your submission ZIP archive is decompressed, the files should extract to the same directory where the ZIP archive is. Upload only the files containing functions implemented by yourself, both the required and supplementary ones.