In Problem Set #3, you will be implementing a parallel algorithm for tone mapping.
Tone mapping is the process of mapping an image with a wide range
of brightness values into an image with a narrow range of brightness values.
This is an important operation because the real world has an enormous range of different brightness values.
For example, think of this spectrum as the range of brightness values in the real world.
On one end of the spectrum we have a bright, sunny day.
On the other end of the spectrum we have a very dark, moonlit night.
And it turns out that the bright, sunny day is about a million times brighter than the night.
Unfortunately, our computer screen can only display a narrow range of values.
And think of this spectrum as the range of brightness values that our computer screen can display.
So tone mapping is the problem of taking the brightness values that we seen the real world
and mapping them down into a tiny range of brightness values that we can display on our computer screen.
This process is tone mapping.
There's a good chance that the camera on your cell phone has a high dynamic range or HDR mode.
When you take pictures in HDR mode,
then your camera is performing a tone mapping step
to arrive at the final image that it shows you.
In this problem set, you will be implementing a simple algorithm for tone mapping called "histogram equalization,"
and this factors nicely into parallel map, reduce, scatter, and scan operations.
You have been exposed to the map operation in previous homework,
so in this homework you will focus on reduce, scatter, and scan.
Recall that histogram counts the number of occurrences of something in the data set.
For example, if we measure the heights of everyone taking this class
and compute a histogram of the heights, it may look something like this.
The height of each bar in this histogram is a count of how many peoples' height fall into a particular range.
For example, this bar may represent that range of people whose height is from 170 cm to 180 cm.
And this bar right here may represent people whose height is from 200 cm to 210 cm,
and these people are really tall by the way.
The main idea in this homework is to first compute a histogram of the brightness values in the image.
And after that we will compute a scan of the histogram
that we computed in step one, using the plus operator.
It turns out that the array resulting from the scan, tells us exactly
how to remap the brightness values in the original image.
This is just one of the many really interesting applications of scan,
and that is why we're going to focus on scan in this particular problem set.
In order to figure out the range of brightness values that should go into each column of the histogram,
you will need to, first, compute the minimum brightness in the image
and, second, compute the maximum brightness in the image.
We will provide you with an array of brightness values,
but you will need to figure out the minimum and the maximum values using the parallel reduce operation.
When computing a histogram parallel, it is very likely that different threads will try to update
the same memory locations at the same time,
and to correctly handle this parallel data scattering requires special care.
For now we recommend that you use the atomicAdd function when computing your histogram.
Although using atomicAdd may be a little slow,
but it will ensure that multiple threads don't try to update the same memory location concurrently.
In return, that will ensure the correctness of your histogram computation.
Once you get everything working,
feel free to start experimenting
and see if you can avoid using atomicAdd.
If you're interested, we have included a more detailed mathematical formulation
of the histogram equalization in the instructor comments.
Lastly, I'd like to thank Eric Ellson of Royal Caliber and Mike Roberts
for writing the script and the code to this problem set. Good luck.