Jump to content
  • Advertisement
Sign in to follow this  
  • entry
    1
  • comments
    2
  • views
    4766

About this blog

Just starting nothing to see here.

Entries in this blog

 

Floyd-Steinberg Dithering or is it Halftoning?

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.

The next little shock I got was when I read:

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:

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.

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:

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:

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

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

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:

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

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:

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

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:

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

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.

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:
float oldPixel, quant_error, newPixel;
int offset, pos;
//for each y from top to bottom
for (int y = 1; y 1; y++) {
offset =y*width;
//for each x from left to right
for (int x=1; x 1; x++) {
pos = offset + x;
//oldpixel := pixel[x][y]
oldPixel = pixels[pos];

//newpixel := find_closest_palette_color(oldpixel)
newPixel = (oldPixel >= 0.5)?1.0f : 0.0f;

//pixel[x][y] := newpixel
pixels[pos] = newPixel ;

//quant_error := oldpixel - newpixel
quant_error = oldPixel - newPixel;

//pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
pixels[pos + 1] += 0.4375f * quant_error;

//pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
pixels[pos - 1 + width] += 0.1875f * quant_error;

//pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
pixels[pos + width] += 0.3125f * quant_error;

//pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error
pixels[pos + 1 + width] += 0.0625f * quant_error;
}
}


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.

4fingers

4fingers

Sign in to follow this  
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!