Please read the general instructions on this page first, and then check the individual tasks for more details. For each task you can download a zip file that contains the code templates you can use for development.
|Task||Attempts||Points||Max||Rating||Man.||Deadline for full points|
|MF1: CPU baseline|
Implement a simple sequential baseline solution. Make sure it works correctly. Do not try to use any form of parallelism yet. You are expected to use a naive algorithm that computes the median separately for each pixel, with a linear-time median-finding algorithm.
|–||–||5 + 0||★||M||2023-08-31 at 23:59:59|
|MF9a: better algorithm|
Design a better algorithm that does not recalculate the median separately for each pixel. Make it as efficient as possible, also for very large window sizes. You are encouraged to use all resources that you have in the CPU.
|–||–||5 + 0||★★★||M||2023-08-31 at 23:59:59|
|MF2: multicore parallelism|
Parallelize your solution to MF1 with the help of OpenMP so that you are exploiting multiple CPU cores in parallel.
|–||–||3 + 0||★||M||2023-08-31 at 23:59:59|
In this task, we will implement a program for doing 2-dimensional median filtering with a rectangular window.
You need to implement the following function:
void mf(int ny, int nx, int hy, int hx, const float* in, float* out)
out are pointers to
float arrays, each of them contains
ny*nx elements. The arrays are already allocated by whoever calls this function; you do not need to do any memory management.
The original value of pixel (x,y) is given in
in[x + nx*y] and its new value will be stored in
out[x + nx*y].
In the output, pixel (x,y) will contain the median of all pixels with coordinates (i,j) where
0 <= i < nx,
0 <= j < ny,
x - hx <= i <= x + hx,
y - hy <= j <= y + hy.
This is the sliding window. Note that the window will contain at most
(2*hx+1) * (2*hy+1) pixels, but near the boundaries there will be fewer pixels.
For our purposes, the median of the vector a = (a1, a2, …, an) is defined as follows:
These examples show what a correct implementation will do if you apply it to each color component of a bitmap image. In these examples, for each color component, the value of each pixel is the median of all pixel values within a sliding window of dimensions (2k+1) × (2k+1). Hover the mouse on the output images to see the differences between input and output.
k = 1
k = 2
k = 5
k = 10
Noise reduction, k = 1
Noise reduction, k = 2
Make sure that you use a fast selection algorithm to find the median. Do not sort; quickselect and other good selection algorithms are much faster than sorting, and there is already a good implementation in the C++ standard library, so you do not need to reinvent it.
Here are some examples of possible techniques that you can use to solve task MF9a: