home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Assembler / dse-src3.dms / in.adf / Source / Vectors / Dithering / Quantize.lha / Quantize.txt < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  3.3 KB
  1. From: garyo@masscomp.UUCP (Gary Oberbrunner)
  2. Newsgroups: comp.graphics
  3. Subject: Re: Advanced Dither Needed
  4. Summary: Floyd-Steinberg Dither explained
  5. Date: 7 Jan 88 03:03:58 GMT
  6. Organization: MASSCOMP - Westford, Ma
  7.  
  8. In article <3703@ames.arpa> watson@ames.UUCP (John S. Watson) writes:
  9. >    I'm looking for either references to, or code for a really 
  10. >nice color dithering algorithm.  The algorithm produces 8-bit dithered 
  11. >images that are almost indistinguishable from the original 24-bit images.  
  12.  
  13. Floyd & Steinberg's dithering algorithm is described in the following paper:
  14.  
  15. Floyd, R.W. and Steinberg, L. "An Adaptive Algorithm for Spatial Gray Scale."
  16. SID 75m Int. Symp. Dig. Tech. Papers (1975), p. 36.
  17.  
  18. I don't actually have this paper, just a reference to it in Heckbert's "Color
  19. Image Quantization for Frame Buffer Display (Siggraph proceedings, 1982,
  20. p. 297).  You probably want to check this paper out too.
  21. But the way F/S dither works is like this (it's so simple...)
  22.  
  23.  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  24. First you come up with a color map - use uniform segmentation for speed or
  25. Heckbert's method for quality.  Then you work from the top left to the bottom
  26. right of the image (pixel order), as follows:
  27.  
  28. Find the closest match in the color map to the true pixel color.
  29. Use that color map entry to represent that pixel.
  30.  
  31. Compute the r,g,b error resulting from the above approximation.
  32.  
  33. Add 3/8 of that error to the pixel to the right, and 3/8 to the pixel
  34. below the current pixel.  The remaining 1/4 goes to the pixel diagonally
  35. below.  Don't forget to clip the rgb, as well as check your boundary
  36. conditions.
  37.  
  38. And that's it - compute the next pixel!  No dither maps, no muss no fuss no
  39. bother.  And it's real fast since you can do the 3/8 and 1/4 by shifting.
  40. On some images it can help to add some random noise; for instance if you
  41. have a smooth (flat-shaded) surface that's just below one of the colors in
  42. the map, the error will build up slowly until you get a line of brighter
  43. color somewhere in the surface.  A bit o' noise gets rid of that line nicely.
  44.  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  45.  
  46. Of course choosing the color map is the fun part. :-) :-)
  47.  
  48.                 Gary Oberbrunner
  49.  
  50. Here is a hack C program which implements both Heckbert's algorithm and F/S
  51. dither (no claims of any kind are made for this program - in fact this article
  52. ended above with my name, and this is all line nois)@(#*&...
  53. No seriously, this code needs real help - it was written for a one-shot deal,
  54. and it is very inefficient in many places.  But it does work ok.
  55. The worst part is where every possible color mapping is computed - SLOW!
  56. And Remap() ain't a speed-demon either, but that's where Floyd et. al.
  57. come in...
  58.             Enjoy (watch out for possible signature at end...)
  59.  
  60. ----------------------------------------------------------------------------
  61. Remember,               -Truth is not beauty;
  62. Information is not knowledge; /    Beauty is not love;      Gary Oberbrunner
  63. Knowledge is not wisdom;     /    Love is not music;      ...!masscomp!garyo
  64. Wisdom is not truth;    ----/    Music is the best. - FZ
  65. ----------------------------------------------------------------------------
  66. # Files that go with this:
  67. #    quantize.c    (most everything in here)
  68. #    split.c        (the color-space-splitting algorithm)
  69. #    quantize.h    (structs & externs)
  70. #    std.h        (my "gotta have it" stuff)
  71.