After graduating from University I decided that I wanted to take my current Computer Graphics degree and try and apply it to the games industry.

To help me get a quick overview of how well my new found knowledge holds up for solving real world problems, I decided to look at current questions being asked in the Graphics Programming and Theory forum at GameDev.net . The test usually consists of going through each thread and seeing if I understand what is being said. Sounds simple enough but I was amazed at the amount of subjects that I had trouble understanding. This was probably mainly down to the technical terms used that I had never heard of before. Such examples would be things like:

• Cube and Hemi-sphere Maps ( Realtime cubemap reflections (GTA IV))


• Geo-mipmapping ( About terrain PVS......)


• Screen Space Ambient Occlusion (Ambient Occlusion raytraced)


• HDRR ( HDRR problem with image key)


• Quaternions ( Rotating around more than 1 global axis )


• Spherical Clipmaps for Terrain Rendering ( SSAO without deferred rendering)

I understand that this is more of a collective knowledge from different discipline but I would at least like a basic understanding of what they all mean.
One thread that caught my eye was entitled "Grayscale to binary image conversion" mainly because I could read it without getting confused. Memories then came flooding back of a module I did that covered this exact scenario. I thought I would try help out where I could so that I could get some useful revision done. I didn't know at the time it would spark a massive journal entry.

A look into my notes found that the process of generating a binary pattern of black and white dots from an image of varying tones is called digital Halftoning. My notes then mention three digital halftoning techniques: Patterning, Dithering and Error diffusion. For more information I suggest that you visit this website Digital Halftoning since it gives good descriptions and examples of each method.

Armed with that knowledge I went to reply, on my arrival I saw that someone had already cleverly suggested error diffusion as one technique. I therefore suggested dithering as another. I decided not to suggest patterning since the results are not that good due to its simple nature.

Here comes the confusion, I hadn't yet discovered the previous website so I decided to link to a part of a Wikipedia entry called Dithering algorithms. The problem being that the definition of dithering was different to what I was taught. I was told that dithering was just a distinctive thresholding technique for digital halftoning an image as described on the previous website. Instead Wikipedia uses it as a generalised term to describe the process of creating the illusion of colour depth, similar to my definition of halftoning.

Quote:Dithering is a technique used in computer graphics to create the illusion of color depth in images with a limited color palette (color quantization).

The next little shock I got was when I read:

Quote:Dithering is analogous to the halftone technique used in printing.

Along with my new found definition of dithering I am now introduced to the idea that halftone is now being used to describe a key technique instead of a general algorithmic process for binarising an image for which there are many methods for. This led me on to read the halftone entry on Wikipedia which did indeed back up this new definition of the word:

Quote:Halftone is the reprographic technique that simulates continuous tone imagery through the use of equally spaced dots of varying size.

Although it would have been better to class that definition as analogue halftoning but later it does talk about digital halftoning. Initially I don't have a problem with this section either where it describes how it simply changes the round dots to groups of monochrome pixels to simulate the look of dots.

Quote:to emulate the photographic halftone cell, the digital halftone cell must contain groups of monochrome pixels within the same-sized cell area

Except it stops there and doesn't go on to explain that there are other digital halftoning methods. Instead it explains how dithering algorithms can be used to create a better effect:

Quote:digital image processing has also enabled more sophisticated dithering algorithms to decide which pixels to turn black or white, some of which yield better results than digital halftoning.

At this stage note how dithering algorithms and the digital halftoning technique have so far been described as being separate.

Back to the dithering entry and we seem to get our first contradiction where halftone is classed as dithering which goes against what was written in the halftone entry:

Quote:Halftone dithering looks similar to halftone screening in newspapers.

My definition of Patterning also comes under fire which now seems to be called ordered dithering:

Quote:Ordered dithering: dithers using a fixed pattern. For every pixel in the image the value of the pattern at the corresponding location is used as a threshold. Different patterns can generate completely different dithering effects.

Compare this to my description of patterning taken from the Digital Halftoning website mentioned earlier:

Quote:pattern generates a digital halftoning image from an input image using the patterning technique. The program pattern reads an input image, quantizes the pixel values, and maps each pixel to its corresponding pattern.

To find out more I decided to read the Ordered dithering entry and to my surprise it seemed to have nothing to do with fixed patterns. Instead it resembled my definition of dithering that was taught to me at University:

Quote:The algorithm achieves dithering by applying a threshold map on the pixels displayed, causing some of the pixels to be rendered at a different color, depending on how far in between the color is of available color entries.

Again comparing the description of dithering over on the Digital Halftoning website:

Quote: Dithering can be thought of as thresholding the source image with a dither matrix. The matrix is laid repeatedly over the source image. Wherever the pixel value of the image is greater than the value in the matrix, a dot on the output image is filled.

Finally the dithering entry also mentions error diffusion but again even that definition is not safe. At one point in the page it seems to class error diffusion as being different and separate from dithering algorithms:

Quote:Error-diffusion algorithms typically produce images that more closely represent the original than simpler dithering algorithms

While other times it explicitly casts it as a dithering algorithm:

Quote:Error-diffusion dithering: diffuses the quantization error to neighbouring pixels.

Then going to the actual error diffusion entry the first thing it does is class it as a type of halftoning just like it was taught to me:

Quote:Error diffusion is a type of halftoning

This is a good example of why Wikipedia should not always be the only place to retrieve information from. In an attempt to get a better understanding of the correct definitions of things I managed to find a book entitled: Digital Halftoning By Robert Ulichney (1987). One of the interesting things it notes it that halftoning can also be called spatial dithering. Compare this to a website that is used as a reference in the dithering entry that states

Quote: Dithering, also called Halftoning

Clearly confusion must have built over the years but the book also mentions that halftone was originally just a printing process where the meaning was tightly defined. This is much like the one used on the halftone entry on Wikipedia but it goes on to say that it can be widened.

Quote: It should also be noted that the word halftone originates from the photoengraving process used in printing and has a well defined meaning that is somewhat broadened here. It is borrowed in a liberal way to describe the theme of this book.

If I had the time I would attempt to re-evaluate the entire dithering and halftone entries but sadly I don't have the time.

Putting that aside the original poster of the thread was still require help in implementing the Floyd-Steinberg algorithm which was a type of error diffusion. Despite being unsure whether it was right to call it a dithering algorithm the entry did give a good pseudo code example. I thought it wouldn't hurt if I tried to implement this as well so that I could answer any questions about it and it might be useful to have an implementation of this hanging around.

I fired up ImageJ ( Introduction to ImageJ) which basically is a Java image processing program that allows me to write plug-ins for, meaning I don't need to worry about writing a back-end GUI.
With one lines I created a simple 128 by 128, 32 bit, floating point, horizontal greyscale ramp that would serve as the original image. The pixel values from that image are then placed into a one dimensional floating point array and modified by the code seen below. The equivalent pseudo code line seen on the Wikipedia entry has then been commented out above each line of code:

The resulting code turns the left image into the right image:


The Wikipedia entry correctly notes that a serpentine scan is sometimes used instead of a simple raster scan. The difference is that a raster scan goes from left to right for each line whereas a serpentine scan goes from left-to-right for even lines then right-to-left on odd. It was suggested by someone that this new method could fix the top left area which has a distinct curve as the error is slowly built up. So that you aren't destroying your retina here is an image zoomed in area of the part I am talking about

My first try of this serpentine scan brought up a strange and rather wrong result:


Turns out I had forgotten to horizontally flip the matrix when your go from right to left otherwise you may get a similar result. So for left to right we have the matrix on the left then for right to left we have the matrix on the right:

After sometime correcting everything, my final result was this:


Because we are working at a pixel level it is hard to see any difference between the two methods. It is not till we zoom into some key areas that we start to see some improvement. A thing to look out for is that the serpentine places more quantization error along diagonal frequencies than the raster method. This means pixels are more evenly distributed on the serpentine scan. An example of this would be when we look closer at the raster scan on the left where we can start to see patterns of white pixels creating diagonal lines:

Compare this to the same section on a serpentine scan on the right which has a more evenly distributed effect:

There is also an improvement on the curve seen at the top of the image with the raster scan on the left and serpentine scan on the right:


If people want me to release a robust, feature full ImageJ plug-in with different halftoning methods etc, then I will happily make one. At the moment though this was just meant to be a simple revision exercise so I have stopped here. I haven't yet cleaned up my current plug-in but I might try and upload it later when it is easier to read and better commented.

Thanks for reading.