====== Monadic Operations ======
In this lab, the following topics will be dealt with:
* histogram
* basic monadic operations
* histogram equalization
* histogram matching
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), CDF(s), 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 ====
{{:courses:b4m33dzo:labs:hist_cdf_image.png?1000|}}
Go to this page to see a more detailed [[courses:b4m33dzo:labs:1_monadic_functions:histogram_cdf_example|visualization of histograms and CDFs]].
==== ====
Start by downloading the {{courses:b4m33dzo:labs:hw_monadic_ops_student.zip|template}} of the assignment. It contains function templates and the data needed for the tasks.
==== 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 it really well.**
==== Basic monadic operations ====
Your first task is to implement the following basic monadic operations, as defined in the [[https://dcgi.fel.cvut.cz/home/sykorad/dzo/slides/dzo-l01.pdf|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:
[[courses:b4m33dzo:labs:1_monadic_functions:simple_monadic_examples|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.).
Here is an example of and equalized image with its histogram and CDF (output of the ''hw_monadic_ops_3.m'' script):
{{ :courses:b4m33dzo:labs:1_monadic_functions:hist_eq_out.png?1000 |Equalized image}}
For reference, [[courses:b4m33dzo:labs:1_monadic_functions:hist_eq_orig|here]] is the original, un-equalized image.
====Histogram matching====
Have a look at these two images:
{{:courses:b4m33dzo:labs:1_monadic_functions:cm2.jpg?200|good image}}
{{:courses:b4m33dzo:labs:1_monadic_functions:cm1.jpg?228|bad image}}
----
The levels of the one on the left have been adjusted by hand in photo editing program.
The right one was taken by a cheap camera and not edited in any way. You can see that many of the details on the right image are drowned out. To fix this, we would like to bring the histogram of the second one as close as possible to the first one. 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:
{{ :courses:b4m33dzo:labs:match_hists.png?350 |}}
This suggests that a transformation which would make the histograms of ''image'' and ''target'' close would be the one which first transforms the ''image'' to an equalized one by ''cdf'', 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(image))$
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$ 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:
{{ :courses:b4m33dzo:labs:1_monadic_functions:hist_match_cdfs.png?600 |cdf transformation}}
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:
{{courses:b4m33dzo:labs:match_hists_example.png?direct&800|}}
==== Assignment summary ====
To fulfil this assignment, you need to submit these files (all packed in a single ''.zip'' file) into the [[https://cw.felk.cvut.cz/upload/| 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 {{courses:b4m33dzo:labs:hw_monadic_ops_student.zip|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.
=====Assignment deadline=====
**Tuesday 14.3.2023, 23:59**
**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.