home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compress / 3000 < prev    next >
Encoding:
Internet Message Format  |  1992-08-13  |  4.5 KB
  1. Path: sparky!uunet!mcsun!corton!chorus!octave.chorus.fr!jloup
  2. From: rthomson@dsd.es.com (Rich Thomson)
  3. Newsgroups: comp.compression
  4. Subject: Fractal compression
  5. Message-ID: <14026@chorus.fr>
  6. Date: 13 Aug 92 14:16:06 GMT
  7. Sender: jloup@chorus.fr
  8. Reply-To: rthomson@dsd.es.com (Rich Thomson)
  9. Organization: Design Systems Division, Evans & Sutherland, SLC, UT
  10. Lines: 101
  11.  
  12. [Rich Thomson <rthomson@dsd.es.com> sent me the following message
  13. in answer to item 17 of the FAQ "What is the state of fractal compression?".
  14. I thought it was interesting and Rich asked me to post it.
  15. Jean-loup Gailly <jloup@chorus.fr> ]
  16.  
  17.  
  18. At SIGGRAPH 1992, Barnsley was at a press conference held by the
  19. publisher Jones & Bartlett.  They are publishing two new books by
  20. Barnsley that give more concrete details of the method:
  21.  
  22.     The Fractal Transform,
  23.     Michael F. Barnsley and Louisa F. Anson
  24.     ISBN 0-86720-218-1, ca. 250 pp, $49.95
  25.  
  26. and
  27.     Fractal Image Compression
  28.     Michael F. Barnsley and Lyman P. Hurd
  29.     ISBN 0-86720-457-5, ca. 250 pp., $49.95
  30.  
  31. the publisher can be reached at:
  32.  
  33.     Jones & Bartlett Publishers, Inc.
  34.     One Exeter Plaza
  35.     Boston, MA 02116
  36.     (617) 859-3900
  37.     FAX: (617) 859-7675
  38.     kpeters@math.harvard.edu
  39.  
  40. Also, at this press conference Barnsley claimed to have patents filed
  41. "worldwide" for their technology.
  42.  
  43. >from Tal Kubo <kubo@zariski.harvard.edu>:
  44. >
  45. >According to Barnsley's book 'Fractals Everywhere', this method is
  46. >based on a measure of deviation between a given image and its
  47. >approximation by an IFS code.  The Collage Theorem states that there is
  48. >a convergent process to minimize this deviation.  Unfortunately,
  49. >according to an article Barnsley wrote for BYTE a few years ago, this
  50. >convergence was rather slow, about 100 hours on a Cray, unless assisted by
  51. >a person.
  52.  
  53. Their performance has improved dramatically beyond what they were
  54. talking about in BYTE a few years ago.  Human assistance to the
  55. compression is no longer needed and the compression time is
  56. reasonable, although the more time and compute power you throw at the
  57. compression, the smaller the resulting file for the same level of
  58. quality.
  59.  
  60. >Barnsley et al are not divulging any technical information beyond the
  61. >meager bit in 'Fractals Everywhere'.
  62.  
  63. See above; now that they have obtained their patents they are talking
  64. more about the method (since their 'competitive edge' is protected).
  65.  
  66. >There is reason to believe that Barnsley's company has
  67. >*no algorithm* which takes a given reasonable image and achieves
  68. >the compression ratios initially claimed for their fractal methods.
  69.  
  70. Barnsley may have pissed alot of people off because of the way he
  71. presents (or doesn't) his work, but that doesn't mean that his method
  72. is bogus.  It is quite reasonable and it works.
  73.  
  74. >Steve Tate <srt@duke.cs.duke.edu> confirms:
  75. >
  76. >Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
  77. >quality is considerably worse than wavelets or JPEG on most of the
  78. >non-contrived images I have seen.
  79.  
  80. You need to supply a date for this observation because Iterated
  81. Systems Inc. has 10 full-time mathematicians who do nothing but work
  82. on making the fractal compression algorithms more efficient as well as
  83. produce higher-quality images for a given file size.  I suspect that this
  84. observation "quality is considerably worse" is quite dated by now.
  85.  
  86. >  A. Jacquin, 'Fractal image coding based on a theory of iterated
  87. >    contractive image transformations', Visual Comm. and Image
  88. >    Processing, vol SPIE-1360, 1990.
  89.  
  90. For people who are starving to find out what the method really is,
  91. this is the best paper that explains the concept in a simple way.
  92.  
  93. The algorithm searches for 'affine redundancy' by searching for
  94. transformations that map regions of pixels to a smaller region of
  95. pixels in the source image.  The space of all possible transformations
  96. is quite large for any given image, so that is why the process needed
  97. human aid at first and also explains why smaller file sizes can be
  98. found for a given quality level if more compute power/time is applied
  99. to the search process.
  100.  
  101. Also, at the press conference Barnsley stated that Microsoft has
  102. licensed the technology and will be supplying a CDROM with 16,000
  103. compressed images on it.  He didn't mention what the original
  104. resolution of the images was, but I suspect something common for PC
  105. images like 640x480.
  106.  
  107.                         -- Rich
  108. -- 
  109.     Repeal the personal income tax; vote Libertarian in 1992.
  110. Disclaimer: I speak for myself, except as noted; Copyright 1992 Rich Thomson
  111. UUCP: ...!uunet!dsd.es.com!rthomson            Rich Thomson
  112. Internet: rthomson@dsd.es.com    IRC: _Rich_        PEXt Programmer
  113.