CS 559 Computer Graphics Floyd Steinberg Dithering The Floyd Steinberg dithering algorithm is an example of an error diffusion technique The aim is to use simple threshold dithering on each pixel but to accurately account for the errors in brightness it induces As a simple motivating example consider a 50 gray image an image with every pixel exactly halfway between black and white in brightness We would like the dithered image to end up half black and half white ideally with a black white checker pattern at the pixel level as in the image below This most accurately captures the 50 gray aspect using only black and white pixel intensities This cannot be done with simple thresholding because in a 50 gray image every pixel starts with the same intensity so the result of a thresholding comparison must be the same for every pixel The solution is to take into account the result of thresholding one pixel when thresholding its neighbors This is the essence of an error diffusion algorithm the error as a result of thresholding one pixel is shifted to its neighbors where it influences their threshold operation First we must define the error e This is the difference between the target value of a pixel Iacc i j and its value after thresholding Iout i j Specifically e Iacc i j t where t 0 if Iacc i j 0 5 and t 1 if Iacc i j 0 5 Iacc is the accumulated image It starts off as the input gray image in floating point format with pixel values ranging from 0 black to 1 white At each step the error e from one pixel is added to its neighbors using the following algorithm Iacc i 1 j Iacc i 1 j 7 e 16 Iacc i 1 j 1 Iacc i 1 j 1 Iacc i j 1 Iacc i j 1 1 e 16 5 e 16 Iacc i 1 j 1 Iacc i 1 j 1 3 e 16 assuming that the index j increases from top to bottom of the image although it really doesn t matter in practice Note that the error accumulates in the image Iacc and that the value in Iacc may go above 1 or below 0 That doesn t matter If one of the pixels in Iacc required above is off the edge of the image we ignore it The pixel i j is thresholded and output Iout i j 0 if Iacc i j 0 5 or Iout i j 1 if Iacc i j 0 5 The algorithm proceeds by performing the above step on every pixel i j in a zig zag order All the even numbered rows starting at 0 go left to right using the algorithm above All the odd numbered rows go right to left using i 1 every place where you see i 1 and vice versa When it s all done every pixel in Iout has been filled and the image Iacc can be thrown away In the set of images on the next page we show the images Iacc and Iout for a 4 4 50 gray image as the algorithm progresses Iacc Iout Iacc 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 Iacc X 0 5 0 656 0 531 0 5 0 5 0 5 0 5 X 0 5 0 5 0 5 X 0 5 0 5 0 5 0 5 X X X 0 775 X X X 0 524 0 605 0 512 0 579 X X 0 5 0 5 X 0 5 X X X X X X X 0 454 0 563 0 512 0 579 X X X X X X X X X 0 761 0 512 0 579 Iacc 0 5 X X X X X X X X X X 0 5 0 526 0 631 0 408 0 579 Iacc X X Iout X Iout Iacc Iout 0 604 0 514 0 721 0 5 X Iacc X X 0 604 0 514 0 537 0 419 Iout Iout X Iacc Iacc Iout X 0 665 0 604 0 514 0 6 0 524 Iacc Iout X X Iacc X X 0 377 0 5 0 5 X 0 5 0 483 0 439 0 579 Iout 0 604 0 443 0 482 0 5 0 5 0 604 0 392 X Iacc X X Iout 0 719 0 5 0 5 X Iout Iout X X X X X X X X X X X 0 757
View Full Document
Unlocking...