home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / research / 427 < prev    next >
Encoding:
Internet Message Format  |  1993-01-11  |  3.1 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!howland.reston.ans.net!paladin.american.edu!gatech!mailer.cc.fsu.edu!sun13!cgl.citri.edu.au
  2. From: craig@cgl.citri.edu.au (Craig McNaughton)
  3. Newsgroups: comp.graphics.research
  4. Subject: re: Fast Dithering Techniques?
  5. Message-ID: <11676@sun13.scri.fsu.edu>
  6. Date: 11 Jan 93 23:16:51 GMT
  7. Sender: news@sun13.scri.fsu.edu
  8. Lines: 63
  9. Approved: murray@vs6.scri.fsu.edu
  10. X-Submissions-To: graphics@scri1.scri.fsu.edu
  11. X-Administrivia-To: graphics-request@scri1.scri.fsu.edu
  12.  
  13.  
  14. >Tom_Lane@G.GP.CS.CMU.EDU writes:
  15. >
  16. >>The free JPEG image compression software currently uses traditional
  17. >>Floyd-Steinberg dithering when reducing the number of colors in its output.
  18. >
  19. >>Even with careful coding, F-S dithering is a remarkably expensive
  20. >>proposition... in our current release, dithering *alone* (not counting color
  21. >>selection) takes nearly as much time as JPEG decompression proper.
  22. >
  23. >>If anyone is aware of cheaper dithering techniques that give results as good
  24. >>as F-S, or of implementation tricks to speed up F-S, I'd appreciate hearing
  25. >>about them.
  26. >
  27. >I once made a variant of F-S that was somewhat faster: instead of
  28. >distributing the error to four neighbouring pixels, distribute it to
  29. >only one. The idea is to make the choice of which pixel to distribute
  30. >to random: in the simplest case you randomly choose either the next
  31. >pixel on the same scan-line or the same pixel on the next scan-line.
  32. >You need a fast way to generate random bits, bit a simple
  33. >shift-register method works reasonably well. If you want slightly
  34. >better quality, you randomly choose one of the four pixels that F-S
  35. >would distribute the error to.
  36. >
  37. >The quality is not quite up to the standard of F-S, but nearly so.
  38. >
  39. >    Torben Mogensen (torbenm@diku.dk)
  40.  
  41. Another alternative is to only propogate error to the next pixel in the path,
  42. but to use a more convoluted path than the standard linear or serpentine scan
  43. that F-S uses.  If you can find a cheap space filling curve to cover your image,
  44. then traversing the image along that curve and propogating error to just the
  45. next pixel produces results that are in many cases better than F-S. (a lot of
  46. the directional artifacts go away).
  47.  
  48. For more information on this, see :
  49.  
  50. Cole, "Naive Halftoning", Proceedings of CG International '90, Chua and Kunii eds.
  51. Springer Verlag, 1990  pp 203-222
  52.  
  53. Witten and Neal "Using Peano Curves for Bilevel display of continuous tone images"
  54. IEEE CG&A, May 1982, pp 47-52
  55.  
  56. Wyvill and McNaughton, "Three Plus Five Makes Eight, A Simplified Approach to
  57. Halftoning", Scientific Visualisation of Physical Phenomena, Proceedings of CG
  58. International '91, Patrikalakis (ed), Springer Verlag, 1991, pp 379-392.
  59.  
  60.  
  61. Craig McNaughton (craig@godzilla.cgl.citri.edu.au)
  62.  
  63.  
  64.  
  65.  
  66.  
  67. -- 
  68. Craig McNaughton                  | "If at first you don't succeed, then
  69. craig@godzilla.cgl.citri.edu.au   | just give up and go and watch TV, no
  70. Advanced Computer Graphics Centre | matter whats on."
  71. RMIT, Melbourne, Australia        |                     Homer J. Simpson
  72.  
  73. --
  74. Moderated by SCRI Vis <>           Submissions to: graphics@scri1.scri.fsu.edu
  75. Guy, John R. Murray   <> Administrivia to: graphics-request@scri1.scri.fsu.edu
  76.