home *** CD-ROM | disk | FTP | other *** search
Text File | 1996-10-17 | 270.9 KB | 5,943 lines |
-
- Article: 79060 in news.answers
- Path: Dortmund.Germany.EU.net!main.Germany.EU.net!EU.net!enews.sgi.com!news.mathworks.com!bloom-beacon.mit.edu!ai-lab!jloup
- From: gzip@prep.ai.mit.edu (Jean-loup Gailly)
- Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
- Subject: comp.compression Frequently Asked Questions (part 1/3)
- Supersedes: <compr1_29jul96@prep.ai.mit.edu>
- Followup-To: comp.compression
- Date: 20 Aug 1996 23:27:35 GMT
- Organization: none
- Lines: 3274
- Approved: news-answers-request@mit.edu
- Distribution: world
- Expires: 15 Oct 1996 16:17:20 GMT
- Message-ID: <compr1_20aug96@prep.ai.mit.edu>
- Reply-To: gzip@prep.ai.mit.edu
- NNTP-Posting-Host: spiff.gnu.ai.mit.edu
- Summary: *** READ THIS BEFORE POSTING ***
- Keywords: data compression, FAQ
- Originator: jloup@spiff.gnu.ai.mit.edu
- Xref: Dortmund.Germany.EU.net comp.compression:28118 comp.compression.research:2194 news.answers:79060 comp.answers:20624
-
- Archive-name: compression-faq/part1
- Last-modified: Aug 20th, 1996
-
- "I've already explained this once, but repetition is
- the very soul of the net." (from alt.config)
-
- This file is part 1 of a set of Frequently Asked Questions (FAQ) for
- the groups comp.compression and comp.compression.research. If you
- can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
- by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
- files part1 to part3. This FAQ is also accessible in the World Wide Web at
- http://www.cs.ruu.nl/wais/html/na-dir/compression-faq/.html
-
- Certain questions get asked time and again, and this is an attempt to
- reduce the bandwidth taken up by these posts and their associated
- replies. If you have a question, *please* check this file before you
- post. It may save a lot of peoples time.
-
- If you have not already read the overall Usenet introductory material
- posted to "news.announce.newusers", please do. It is also available by
- ftp in ftp://garbo.uwasa.fi/pc/doc-net/usenews.zip (see item 2 below
- about .zip).
-
- If you don't want to see this FAQ regularly, please add the subject
- line to your kill file. If you don't know what a kill file is, get
- by ftp the file ftp://rtfm.mit.edu/pub/usenet/news.answers/killfile-faq
- If you have corrections or suggestions for this FAQ, send them to
- Jean-loup Gailly <gzip@prep.ai.mit.edu>. Thank you.
-
- Part 1 is oriented towards practical usage of compression programs.
- Part 2 is more intended for people who want to know how compression works.
- Part 3 is a long (but somewhat obsolete) list of image compression hardware.
-
- Main changes relative to the previous version:
-
- - fixed ftp locations of rar and tar for MSDOS [item 2]
- - major rewrite of item 9, which is now renamed as
- "Compression of random data (WEB, Gilbert and others)"
- - new item 10 "Fake compression programs (OWS, WIC)"
- - new item 78 "The Burrows-Wheeler block sorting algorithm"
-
- Contents
- ========
-
- General questions:
-
- [1] What are these newsgroups about?
- [2] What is this .xxx file type?
- Where can I find the corresponding compression program?
- [3] What is the latest pkzip version?
- [4] What is an archiver?
- [5] What is the best general purpose compression program?
- [7] Which books should I read?
- [8] What about patents on data compression algorithms?
- [9] Compression of random data (WEB, Gilbert and others)
- [10] Fake compression programs (OWS, WIC)
- [11] What is the V.42bis standard?
- [12] I need source for the winners of the Dr Dobbs compression contest
- [13] I need source for arithmetic coding
-
- Image and audio compression:
-
- [15] Where can I get image compression programs?
- [16] What is the state of the art in lossless image compression?
- [17] What is the state of fractal compression?
- [18] I need specs and source for TIFF and CCITT group 4 Fax.
- [19] What is JPEG?
- [20] I am looking for source of an H.261/H.263 codec and MPEG
- [25] Fast DCT (Discrete Cosine Transform) algorithms
- [26] Are there algorithms and standards for audio compression?
-
- Common problems:
-
- [30] My archive is corrupted!
- [31] pkunzip reports a CRC error!
- [32] VMS zip is not compatible with pkzip!
- [33] I have a problem with Stacker or DoubleSpace!
-
- Questions which do not really belong to comp.compression:
-
- [50] What is this 'tar' compression program?
- [51] I need a CRC algorithm
- [52] What about those people who continue to ask frequently asked questions?
- [53] Where are FAQ lists archived?
- [54] I need specs for graphics formats
- [55] Where can I find Lenna and other images?
- [56] I am looking for a message digest algorithm
- [57] I have lost my password on a .zip file
-
-
- Part 2: (Long) introductions to data compression techniques
-
- [70] Introduction to data compression (long)
- Huffman and Related Compression Techniques
- Arithmetic Coding
- Substitutional Compressors
- The LZ78 family of compressors
- The LZ77 family of compressors
-
- [71] Introduction to MPEG (long)
- What is MPEG?
- Does it have anything to do with JPEG?
- Then what's JBIG and MHEG?
- What has MPEG accomplished?
- So how does MPEG I work?
- What about the audio compression?
- So how much does it compress?
- What's phase II?
- When will all this be finished?
- How do I join MPEG?
- How do I get the documents, like the MPEG I draft?
-
- [72] What is wavelet theory?
- [73] What is the theoretical compression limit?
- [74] Introduction to JBIG
- [75] Introduction to JPEG
- [76] What is Vector Quantization?
- [77] Introduction to Fractal compression
- [78] The Burrows-Wheeler block sorting algorithm
-
-
- Part 3: (Long) list of image compression hardware
-
- [85] Image compression hardware
- [99] Acknowledgments
-
-
- Search for "Subject: [#]" to get to question number # quickly. Some news
- readers can also take advantage of the message digest format used here.
-
- If you know very little about data compression, read question 70 in
- part 2 first.
-
- ------------------------------------------------------------------------------
-
- Subject: [1] What are these newsgroups about?
-
-
- comp.compression is the place to discuss about data compression, both
- lossless (for text or data) and lossy (for images, sound, etc..).
- comp.compression.research was created later to provide a forum for
- current research on data compression and data compression algorithms;
- this group is now moderated. If you are not experienced in data compression,
- please post in comp.compression only.
-
- An archive of this newsgroup since Oct 1993 is available in
- ftp://spib.rice.edu/pub/news/comp.compression/*
-
- If you only want to find a particular compression program for a
- particular operating system, please read first this FAQ and the
- article "How to find sources" which is regularly posted in
- news.answers.
-
- If you can't resist posting such a request, other groups are probably
- more appropriate (comp.binaries.ibm.pc.wanted, comp.os.msdos.apps,
- comp.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d, comp.dsp,
- alt.graphics.pixutils). Please post your request in comp.compression
- only as a last resource.
-
- If your question is about graphics only (no compression), please
- post to comp.graphics.misc, *after* reading the comp.graphics FAQ (see
- item 54 below). For some unknown reason, many questions about
- graphics are incorrectly posted to comp.compression.
- For questions related to audio compression, check also comp.dsp.
-
- Please do not post any program in binary form to comp.compression.
- Very short sources can be posted, but long sources should be be posted
- to the specialized source groups, such as comp.sources.* or alt.sources.
- If the program is already available by ftp, just give the name of the
- ftp site and the full path name of the file.
-
- As for any newsgroups, do not post the same message separately to
- comp.compression and comp.compression.research.
-
- A collection of compression based information is provided at
- http://www.cs.waikato.ac.nz/~singlis/compression-pointers.html
-
- ------------------------------------------------------------------------------
-
- Subject: [2] What is this .xxx file type?
- Where can I find the corresponding compression program?
-
-
- All the programs mentioned in this section are lossless. For most
- programs, one US and one European ftp site are given. (ftp.coast.net
- & garbo.uwasa.fi) Many other sites (in particular wuarchive.wustl.edu)
- have the same programs.
-
- To keep this list to a reasonable size, many programs are not
- mentioned here. Additional information can be found in the file
- ftp://ftp.cso.uiuc.edu/pub/doc/pcnet/compression maintained by
- David Lemson (lemson@uiuc.edu). When several programs can handle
- the same archive format, only one of them is given. If you don't
- find a particular MSDOS archiver here, look also in
- ftp://ftp.cs.tu-berlin.de/pub/msdos/mirrors/ftp.elf.stuba.sk/pc/
-
- Sources for additional lossless data compressors can be found in
- ftp://garbo.uwasa.fi/pc/programming/lds_11.zip
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archivers/lz-comp2.zip
- http://wwwvms.utexas.edu/~cbloom/index.html
- ftp://ftp.imag.fr/pub/archive/compression/codecs/codecs.tgz
- ftp://garbo.uwasa.fi/pc/turbopas/preskit2.zip (sources in Pascal)
- ftp://ftp.cs.uiowa.edu/pub/jones/compress/ (Splay tree compression)
-
- For Macintosh programs, look on ftp://sumex-aim.stanford.edu/info-mac
- For VM/CMS, look on ftp://vmd.cso.uiuc.edu/public.477
- For Atari, look on ftp://atari.archive.umich.edu
- For Amiga, look on ftp://ftp.wustl.edu/pub/aminet/
-
- A general purpose lossless data compression library is available in
- ftp://ftp.uu.net/pub/archiving/zip/zlib/zlib-1.0.4.tar.gz or zlib104.zip;
- see http://quest.jpl.nasa.gov/zlib/ for more information.
-
- If you don't know how to use ftp or don't have ftp access, read the
- article "How to find sources" which is regularly posted in news.answers.
-
- If you can't find a program given below, it is likely that a newer
- version exists in the same directory. (Tell me <gzip@prep.ai.mit.edu>)
-
- A very short description of the compression algorithm is given for
- most programs. For the meaning of LZ77, LZ78 and LZW, see question 70
- in part 2 of the FAQ. If you are looking for the file format of a
- specific compression program, get the sources of the decompressor.
- For the format of uuencode, do "man 5 uuencode" on a Unix box.
-
- ext: produced by or read by
-
- ..arc, .ark: arc, pkarc for MSDOS. (LZW algorithm)
- ftp://wuarchive.wustl.edu/mirrors/msdos/starter/pk361.exe
- ftp://garbo.uwasa.fi/pc/arcers/pk361.exe
-
- arc for Unix
- ftp://wuarchive.wustl.edu/mirrors/misc/unix/arc521e.tar-z
- ftp://garbo.uwasa.fi/unix/arcers/arc.tar.Z
- Contact: Howard Chu <hyc@umix.cc.umich.edu>
-
- arc for VMS
- ftp://wuarchive.wustl.edu/packages/compression/vax-vms/arc.exe
-
- for Mac
- ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
-
- arc for Amiga
- ftp.funet.fi:pub/amiga/fish/001-100/ff070/arc.lha
-
- ..arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman
- encoding on a block basis)
- Contact: Robert K Jung <robjung@world.std.com>
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/arj242b.exe
- ftp://garbo.uwasa.fi/pc/arcers/arj250a.exe
-
- unarj for Unix. Decompresses only. (There is no arj compressor for Unix.
- Don't post a request.)
- ftp://wuarchive.wustl.edu/mirrors/misc/unix/unarj241.tar-z
- ftp://garbo.uwasa.fi/unix/arcers/unarj241.tar.Z
-
- unarj for Mac
- ftp://mac.archive.umich.edu/mac/util/compression/unarjmac.cpt.hqx
-
- unarj for Amiga
- ftp.funet.fi:pub/amiga/utilities/archivers/unarj-0.5.lha
-
- base64 (MIME encoding): This is *not* a compression issue but it keeps
- coming as a question on comp.compression. So:
- ftp://ftp.andrew.cmu.edu/pub/mpack/mpack-1.5-src.tar.Z (source)
- ftp://ftp.andrew.cmu.edu/pub/mpack/mpack15d.zip (MSDOS exe)
- ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/mpack-15.hqx (Mac)
-
- ..bck: VMS BACKUP. BACKUP is *not* a compression program. Do "help backup".
-
- ..cpt: Compact Pro for Mac and Power PC
- ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/compact-pro-151.hqx
-
- For Unix:
- ftp://sumex-aim.stanford.edu/info-mac/unix/macutil-20b1.shar
- ftp://ftp.cwi.nl/pub/dik/macutil2.0b3.shar.Z
-
- For DOS:
- ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE
- ftp://garbo.uwasa.fi/pc/arcers/ext-pc.zip
-
- ..ddi: files made by DiskDupe (Pro)
- ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/unddi11u.zip
- ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/x2file15.zip
-
- ..exe: self-extracting MSDOS executable (creates files on disk when run)
- Run the file, or try unzip, lha or arj on it.
-
- ..exe: compressed MSDOS executable (decompresses itself in memory then runs
- the decompressed code). To get the original uncompressed .exe:
- ftp://garbo.uwasa.fi/pc/execomp/unp411.zip
- To create such files:
- ftp://ftp.coast.net/mirrors/SimTel/msdos/execomp/lzexe91e.zip
- ftp://nic.funet.fi/pub/msdos/windows/util/winlite1.zip (for Windows)
-
- ..gif: gif files are images compressed with the LZW algorithm. See the
- comp.graphics FAQ list for programs manipulating .gif files. See
- suffix .Z below for source of LZW.
-
- ..gz, .z: gzip (or pack, see .z below). gzip uses the same algorithm as
- zip 2.0x (see below); it can also extract packed and compressed files.
- Contact: Jean-loup Gailly <gzip@prep.ai.mit.edu>
- http://www.teaser.fr/~jlgailly/
-
- For Unix, MSDOS, OS/2, VMS, Atari, Amiga, Primos:
- ftp://prep.ai.mit.edu/pub/gnu/gzip-1.2.4.tar (.shar or .tar.gz: source)
- ftp://prep.ai.mit.edu/pub/gnu/gzip-1.2.4.msdos.exe (MSDOS self-extract)
- ftp://ftp.coast.net/mirrors/SimTel/msdos/compress/gzip124.zip (MSDOS)
- ftp://garbo.uwasa.fi/unix/arcers/gzip-1.2.4.tar.Z (source)
- ftp://garbo.uwasa.fi/pc/unix/gzip124.zip (MSDOS exe)
- ftp://ftp.uu.net/pub/archiving/zip/WIN32/gzip124xN.zip (WIN95 & NT)
- ftp://ftp.uu.net/pub/archiving/zip/VMS/gzip124x.vax_exe (VMS exe)
- ftp://ftp.uu.net/pub/archiving/zip/UNIX/SUN/gzip124x.tar.Z (Solaris 2)
- ftp://quest.jpl.nasa.gov/beta/vmcms_mvs/gzip123-mvs.exe (MVS)
-
- For Mac:
- ftp://ivo.cps.unizar.es//Graficos/Public/SPDsoft/MacGzip_FAT_1.0.cpt.hqx
- http://persephone.cps.unizar.es/general/gente/spd/gzip/ (MacGzip page)
-
- ..ha: ha 0.99 (improved PPMC - 4th order Markov modeling)
- Contact: Harri Hirvola <harri.hirvola@vaisala.infonet.com>
- ftp://garbo.uwasa.fi/pc/arcers/ha098.zip
- ftp://ftp.nl.net/gopher/NLnet-connected/aipnl/ha0999.exe
- ftp://sunsite.unc.edu/pub/Linux/utils/compress/ha0999p-linux.tar.gz
-
- ..hap: Hamarsoft HAP archiver (Markov modeling + arithmetic coding)
- Contact: feldmann@xs4all.nl or feldmann@pi.net
- ftp://garbo.uwasa.fi/pc/arcers/hap305bp.com
- http://www.xs4all.nl/~feldmann
-
- ..hpk: hpack (archiver with strong encryption)
- Contact: Peter Gutmann <pgut1@cs.aukuni.ac.nz>
- ftp://src.doc.ic.ac.uk/computing/archiving/compress/hpack/
-
- ..hqx: Macintosh BinHex format.. (BinHex is *not* a compression program,
- it is similar to uuencode but handles multiple forks.)
- for Mac:
- ftp://mac.archive.umich.edu/mac/utilities/compressionapps/binhex4.0.bin
-
- for Unix:
- ftp://sumex-aim.stanford.edu/info-mac/cmp/mcvert-216.shar
-
- for MSDOS:
- ftp://ftp.coast.net/mirrors/SimTel/msdos/mac/xbin23.zip
- ftp://garbo.uwasa.fi/pc/unix/xbin23.zip
-
- ..jam: JAM real-time compressor for MSDOS
- ftp://garbo.uwasa.fi/pc/arcers/jam125sw.zip
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/jam125sw.zip
-
- ..lha:
- ..lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static
- Huffman coding on a block basis)
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/lha213.exe (exe)
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/lha211sr.zip (source)
- ftp://garbo.uwasa.fi/pc/arcers/lha255b.exe
-
- lharc for Unix. (LZ77 with hash table and binary trees, plus secondary
- Huffman coding)
- Warning: lharc can extract .lzh files created by
- lharc 1.xx but not those created by lha. See lha for Unix below.
- ftp://wuarchive.wustl.edu/mirrors/misc/unix/lharc102a.tar-z
- ftp://garbo.uwasa.fi/unix/arcers/lha101u.tar.Z
-
- lharc for VMS. Same warning as for Unix lharc.
- ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lharc.exe
-
- lha for Unix. Warning: all doc is in Japanese.
- ftp://wuarchive.wustl.edu/mirrors/misc/unix/lha101u.tar-z
- ftp://garbo.uwasa.fi/unix/arcers/lha-1.00.tar.Z
- Contact: lha-admin@oki.co.jp or oki@fs.telcom.oki.ac.jp
- lha for Mac
- ftp://mac.archive.umich.edu/mac/utilities/compressionapps/maclha2.0.cpt.hqx
- lha for Amiga
- ftp://ftp.funet.fi/pub/amiga/utilities/archivers/LhA_e138.run
- lha for OS/2:
- ftp://hobbes.nmsu.edu/os2/16bit/archiver/lh2_222.zip
-
- MIME: see base64 above
-
- ..pak: pak for MSDOS (LZW algorithm)
- ftp://wuarchive.wustl.edu/mirrors/msdos/archivers/pak251.exe
- ftp://garbo.uwasa.fi/pc/arcers/pak251.exe
-
- ..pit: PackIt (Macintosh)
- for Mac:
- ftp://sumex-aim.stanford.edu/info-mac/cmp/stuffit-lite-35.hqx
-
- for Unix:
- ftp://sumex-aim.stanford.edu/info-mac/cmp/mcvert-215.shar.gz
- ftp://garbo.uwasa.fi/mac/arcers/mcvert-215.shar
-
- ..pp: PowerPacker (Amiga)
- ftp.funet.fi:pub/amiga/fish/501-600/ff561/PPLib.lha
-
- ..rar: RAR (MSDOS) Contact: Eugene_Roshal@p0.f23.n5010.z2.fidonet.org
- or Andrey Spasibozhko <as@hq.icb.chel.su>
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/rar155.exe
- ftp://garbo.uwasa.fi/pc/arcers/rar200.exe
- ftp://ftp.kiae.su/msdos/arcers/rar*.exe
- ftp://ftp.elf.stuba.sk/pub/pc/pack/*rar2*.exe
-
- ..sea: self-extracting archive (Macintosh)
- Run the file to extract it. The self-extraction code can be
- removed with:
- ftp://mac.archive.umich.edu/mac/utilities/compressionapps/desea1.11.cpt.hqx
- ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE (MS Windows)
-
- ..sdn: used by the Shareware Distribution Network.
- Try the decompressors for .pak or .arj (see above)
-
- ..shar: Shell archive. This is not a compression program. Use "sh foo.shar"
- to extract on Unix. For MSDOS, use:
- ftp://garbo.uwasa.fi/pc/unix/unshar.zip
-
- ..sit: Stuffit for Macintosh
- for Mac:
- ftp://sumex-aim.stanford.edu/info-mac/cmp/stuffit-lite-35.hqx
-
- for Unix:
- ftp://sumex-aim.stanford.edu/info-mac/cmp/unsit-15-unix.shar
-
- for Amiga:
- ftp.funet.fi:pub/amiga/utilities/archivers/unsit-1.5c2.lha
-
- for MSDOS:
- ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE
- ftp://garbo.uwasa.fi/pc/arcers/unsit30.zip
-
- ..?q?: Squeeze for MSDOS (do not confuse with other 'squeeze' below).
- Static Huffman coding.
- ftp://ftp.coast.net/mirrors/SimTel/msdos/starter/sqpc12a.com (squeeze)
- ftp://ftp.coast.net/mirrors/SimTel/msdos/starter/nusq110.com (unsqueeze)
-
- ..sqz: Squeeze for MSDOS (do not confuse with other 'squeeze' above)
- LZ77 with hashing.
- ftp://wuarchive.wustl.edu/mirrors/msdos/archivers/sqz1083e.exe
- ftp://garbo.uwasa.fi/pc/arcers/sqz1083e.exe
-
- ..tar: tar is *not* a compression program. However, to be kind for you:
- for MSDOS
- ftp://ftp.coast.net/mirrors/SimTel/msdos/starter/tarread.exe
- ftp://garbo.uwasa.fi/pc/unix/tar4dos.zoo
-
- for Unix
- tar (you have it already. To extract: tar xvf file.tar)
-
- for VMS
- ftp://wuarchive.wustl.edu/packages/compression/vax-vms/tar.exe
-
- for Macintosh
- ftp://sumex-aim.stanford.edu/info-mac/util/tar-30.hqx
-
- for Amiga:
- ftp.funet.fi:pub/amiga/fish/401-500/ff445/Tar.lha
-
- ..tar.Z, .tar-z, .taz: tar + compress
- For Unix: zcat file.tar.Z | tar xvf -
- with GNU tar: tar xvzf file.tar.Z
- for MSDOS:
- ftp://garbo.uwasa.fi/pc/unix/tar320g.zip (MSDOS exe)
- ftp://ftp.kiae.su/msdos/arcers/tar*sr.zip (sources)
- ftp://ftp.kiae.su/msdos/arcers/tar*_p.zip (MSDOS exe)
- Other OS: first uncompress (see .Z below) then untar (see .tar above)
-
- ..tar.gz, .tgz, .tar-gz, .tar.z: tar + gzip
- For Unix: gzip -cd file.tar.gz | tar xvf -
- with GNU tar: tar xvzf file.tar.gz
- for MSDOS: ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/tar320c-.zip
- ftp://garbo.uwasa.fi/pc/unix/tar320g.zip
- Other OS: first uncompress (see .gz above) then untar (see .tar above)
-
- ..td0: (compressed MS-DOS floppy image produced by TeleDisk)
- ftp://ftp.coast.net/mirrors/SimTel/msdos/diskutil/teled212.zip
-
- ..uc2: UC2 for MSDOS and OS/2. (LZ77 with secondary static Huffman encoding on
- a block basis, and dynamic dictionaries shared among files.)
- Contact: desk@aip.nl
- ftp://garbo.uwasa.fi/pc/arcers/uc2r3.exe (or uc2pro.exe)
-
- ..z: pack or gzip (see .gz above). pack uses static Huffman coding.
- To extract, see .gz above.
-
- ..zip: pkzip 2.04g for MSDOS. (LZ77 with hashing, plus secondary static
- Huffman coding on a block basis). Contact: support@pkware.com
- or http://www.pkware.com/
- ftp://ftp.coast.net/mirrors/SimTel/msdos/zip/pkz204g.exe
- ftp://garbo.uwasa.fi/pc/arcers/pkz204g.exe
- ftp://garbo.uwasa.fi/windows/util/pkzws201.exe (Windows version)
-
- arcutil 2.0 for VM/CMS (unzip only, not yet compatible with pkzip 2.04)
- ftp://vmd.cso.uiuc.edu/public.477/arcutil.*
-
- zip 1.1 for Unix, MSDOS, VMS, OS/2, ... (compatible with pkzip 1.10.
- For corresponding unzip, see unzip 5.12 below).
- ftp://ftp.uu.net/pub/archiving/zip/zip11.zip
-
- zip 2.1 and unzip 5.20 for Unix, MSDOS, VMS, OS/2, Amiga, ...
- Compatible with pkzip 2.04g (LZ77 with hashing, plus secondary static
- Huffman coding on a block basis). Contact: zip-bugs@lists.wku.edu
- See also http://quest.jpl.nasa.gov/Info-ZIP/
- (On SGI, do not confuse with the editor also named 'zip'.)
-
- ftp://ftp.uu.net/pub/archiving/zip/zip21.zip (source)
- ftp://ftp.uu.net/pub/archiving/zip/unzip52.* (source)
- ftp://ftp.uu.net/pub/archiving/zip/MSDOS/zip21x.zip (MSDOS exe)
- ftp://ftp.uu.net/pub/archiving/zip/MSDOS/unz520x*.exe (MSDOS exe)
- ftp://ftp.uu.net/pub/archiving/zip/WIN32/zip21xN.zip (Win95 & NT)
- ftp://ftp.uu.net/pub/archiving/zip/WIN32/unz520xN.exe (Win95 & NT)
- [The Win95 version supports long file names; MSDOS version doesn't]
- ftp://ftp.uu.net/pub/archiving/zip/OS2/* (OS/2 exe 16&32 bit)
- See also AMIGA, ATARI, MAC, UNIX, RISCOS, VMS... subdirectories.
- If ftp.uu.net not available, use ftp://nic.switch.ch/mirror/Info-Zip/
-
- ftp://ftp.uu.net/pub/archiving/zip/zcrypt26.zip (encryption source)
- Non US residents must get the crypt versions from garbo:
- ftp://garbo.uwasa.fi/unix/arcers/zcrypt*.zip (encryption source)
-
- for Macintosh:
- ftp://mac.archive.umich.edu/mac/util/compression/unzip2.01.cpt.hqx
- ftp://mac.archive.umich.edu/mac/util/compression/zipit1.31.cpt.hqx
- ftp://ftp.uu.net/pub/archiving/zip/MAC/unz512x.hqx
- ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
-
- WinZip by Nico Mak <support@winzip.com> (uses Info-ZIP compress. code):
- ftp://ftp.winzip.com/winzip/ (MS Windows)
-
- ..zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above)
- Contact: Rahul Dhesi <dhesi@cirrus.com>
- ftp://wuarchive.wustl.edu/mirrors/msdos/zoo/zoo210.exe
- ftp://garbo.uwasa.fi/pc/arcers/zoo210.exe
-
- zoo 2.10 for Unix, VMS
- ftp://oak.oakland.edu/pub/misc/unix/zoo210.tar.Z
- ftp://garbo.uwasa.fi/unix/arcers/zoo210.tar.Z
-
- zoo for Mac
- ftp://mac.archive.umich.edu/mac/utilities/compressionapps/maczoo.sit.hqx
-
- zoo for Amiga
- ftp://ftp.funet.fi/pub/amiga/utilities/archivers/Zoo-2.1.lha
-
- ..??_: Microsoft compress.exe and expand.exe. compress.exe is available
- in the Windows SDK (Software Development Kit) and in
- ftp://ftp.microsoft.com/softlib/mslfiles/CP0982.EXE
-
- ..F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman
- encoding)
- ftp://wuarchive.wustl.edu/usenet/comp.sources.misc/volume35/freeze/part0[1-3].Z
- ftp://ftp.inria.fr/system/arch-compr/freeze-2.5.tar.Z
- Contact: Leonid A. Broukhis <leo@zycad.com>
-
- ..Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78)
- ftp://wuarchive.wustl.edu/usenet/comp.sources.unix/volume24/yabbawhap/part*.Z
- ftp://ftp.inria.fr/system/arch-compr/yabba.tar.Z
- Contact: Dan Bernstein <djb@silverton.berkeley.edu>
-
- ..Z: compress for Unix ('the' LZW algorithm)
- It is likely that your Unix system has 'compress' already. Otherwise:
- ftp://wuarchive.wustl.edu/packages/compression/compress-4.1.tar
- (not in .Z format to avoid chicken and egg problem)
-
- compress for MSDOS
- ftp://ftp.coast.net/mirrors/SimTel/msdos/compress/comp430d.zip
- ftp://garbo.uwasa.fi/pc/unix/comp430d.zip
- ftp://garbo.uwasa.fi/pc/source/comp430s.zip
-
- compress for Macintosh
- ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
- ftp://sumex-aim.stanford.edu/info-mac/cmp/maccompress-32.hqx
-
- compress for Amiga
- ftp.funet.fi:pub/amiga/utilities/archivers/compress-4.1.lha
-
- compress for VAX/VMS
- ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzcomp.exe
- ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzdcmp.exe
-
- ------------------------------------------------------------------------------
-
- Subject: [3] What is the latest PKZIP version?
-
- The latest official DOS version is 2.04g. Release 2.04c had serious bugs,
- corrected in 2.04e and 2.04g. The latest Windows version is pkzws201.exe.
-
- Be warned that there are countless bogus PKZIP 1.20, 2.0, 2.02, 3.00B,
- 3.05, 4.1 and whatever scams floating around. They usually are hacks
- of PKZIP 1.93A beta test version. Some of them are trojans and / or
- carry computer virii.
-
- Note about pkzip 2.06 from a PKware employee:
-
- Version 2.06 was released as an INTERNAL use only IBM version.
- It is identical to 2.04G, but it has IBM names in the help
- screens and such. That release is meant for IBM only.
-
- If pkunzip indicates that you need version 2.8 to extract an
- archive, your archive has been corrupted by a transfer not
- made in binary mode (see item 30 below).
- ------------------------------------------------------------------------------
-
- Subject: [4] What is an archiver?
-
-
- There is a distinction between archivers and other compression
- programs:
-
- - an archiver takes several input files, compresses them and produces
- a single archive file. Examples are arc, arj, lha, zip, zoo.
-
- - other compression programs create one compressed file for each
- input file. Examples are freeze, yabba, compress, gzip. Such programs
- are often combined with tar to create compressed archives (see
- question 50: "What is this tar compression program?").
-
- For a comparison of zip and gzip, see the gzip README file. (In short:
- zip is an archiver, gzip is not; only zip is compatible with pkzip.)
-
- ------------------------------------------------------------------------------
-
- Subject: [5] What is the best general purpose compression program?
-
-
- The answer is: it depends. (You did not expect a definitive answer,
- did you?)
-
- It depends whether you favor speed, compression ratio, a standard and
- widely used archive format, the number of features, etc... Just as
- for text editors, personal taste plays an important role. compress has
- 4 options, arj 2.30 has about 130 options; different people like
- different programs. *Please* do not start or continue flame wars on
- such matters of taste.
-
- Several benchmarks of MSDOS archivers are available:
- - ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/actest*.zip
- and http://www.mi.net/act/act.html by Jeff Gilchrist <jeffg@mi.net>
- - ftp://garbo.uwasa.fi/pc/arcers/act-*.zip
- by Jonathan Burt <jonathan@jaburt.demon.co.uk>
- - ftp://ftp.coast.net/mirrors/SimTel/msdos/info/arctst*.zip
-
- Please do not post your own benchmarks made on your own files that
- nobody else can access. If you think that you must absolutely post yet
- another benchmark, make sure that your test files are available by
- anonymous ftp.
-
- Since all other benchmarks are for MSDOS only, here is one mainly for
- Unix, on a 33Mhz Compaq 386. All programs have been run on Unix SVR4,
- except pkzip and arj which only run on MSDOS.
-
- The programs compared here were chosen because they are the most
- popular or because they run on Unix and source is available. For ftp
- information, see above. Three programs (hpack, comp-2 and ha) have
- been added because they achieve better compression (at the expense of
- speed) and one program (lzrw3-a) has been added because it favors
- speed at the expense of compression:
-
- - comp-2 is in ftp://wuarchive.wustl.edu/mirrors/msdos/ddjmag/ddj9102.zip
- (inner zip file nelson.zip),
- - hpack is in ftp://garbo.uwasa.fi/unix/arcers/hpack78src.tar.Z
- - ha 0.98 is in ftp://garbo.uwasa.fi/pc/arcers/ha098.zip
- - lzrw3-a is no longer in ftp://ftp.adelaide.edu.au/pub/compression/lzrw3-a.c
-
- The 14 files used in the comparison are from the standard Calgary
- Text Compression Corpus, available in
- ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/
-
- The whole corpus includes 18 files, but the 4 files paper[3-6] are
- generally omitted in benchmarks. It contains several kinds of file
- (ascii, binary, image, etc...) but has a bias towards large files.
- You may well get different ratings on the typical mix of files that
- you use daily, so keep in mind that the comparisons given below are
- only indicative.
-
- The programs are ordered by decreasing total compressed size. For a
- fair comparison between archivers and other programs, this size is
- only the size of the compressed data, not the archive size.
-
- The programs were run on an idle machine, so the elapsed time
- is significant and can be used to compare Unix and MSDOS programs.
-
- [Note: I did not have time to run again all benchmarks with more
- recent versions of zip, freeze, arj, hpack and ha. To be done for some
- future revision of this FAQ.]
-
- size lzrw3a compress lharc yabba pkzip freeze
- version: 4.0 1.02 1.0 1.10 2.3.5
- options: -m300000
- ------ ----- ------ ------ ------ ------ ------
- bib 111261 49040 46528 46502 40456 41354 41515
- book1 768771 416131 332056 369479 306813 350560 344793
- book2 610856 274371 250759 252540 229851 232589 230861
- geo 102400 84214 77777 70955 76695 76172 68626
- news 377109 191291 182121 166048 168287 157326 155783
- obj1 21504 12647 14048 10748 13859 10546 10453
- obj2 246814 108040 128659 90848 114323 90130 85500
- paper1 53161 24522 25077 21748 22453 20041 20021
- paper2 82199 39479 36161 35275 32733 32867 32693
- pic 513216 111000 62215 61394 65377 63805 53291
- progc 39611 17919 19143 15399 17064 14164 14143
- progl 71646 24358 27148 18760 23512 17255 17064
- progp 49379 16801 19209 12792 16617 11877 11686
- trans 93695 30292 38240 28092 31300 23135 22861
- 3,141,622 1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290
- real 0m35s 0m59s 5m03s 2m40s 5m27s
- user 0m25s 0m29s 4m29s 1m46s 4m58s
- sys 0m05s 0m10s 0m07s 0m18s 0m08s
- MSDOS: 1m39s
-
-
- zoo lha arj pkzip zip hpack comp-2 ha
- 2.10 1.0(Unix) 2.30 2.04g 1.9 0.75a 0.98
- ah 2.13(MSDOS) -jm -ex -6 a2
- ------ ------ ------ ------ ------- ------ ------ ------
- bib 40742 40740 36090 35126 34950 35619 29840 26927
- book1 339076 339074 318382 312490 312619 306876 237380 235733
- book2 228444 228442 210521 206513 206306 208486 174085 163535
- geo 68576 68574 69209 68706 68418 58976 64590 59356
- news 155086 155084 146855 144545 144395 141608 128047 123335
- obj1 10312 10310 10333 10306 10295 10572 10819 9799
- obj2 84983 84981 82052 81132 81336 80806 85465 80381
- paper1 19678 19676 18710 18531 18525 18607 16895 15675
- paper2 32098 32096 30034 29568 29674 29825 25453 23956
- pic 52223 52221 53578 52409 55051 51778 55461 51639
- progc 13943 13941 13408 13341 13238 13475 12896 11795
- progl 16916 16914 16408 16122 16175 16586 17354 15298
- progp 11509 11507 11308 11200 11182 11647 11668 10498
- trans 22580 22578 20046 19462 18879 20506 21023 17927
- 1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854
- real 4m07s 6m03s 1m49s 1h22m17s 27m05s
- user 3m47s 4m23s 1m43s 1h20m46s 19m27s
- sys 0m04s 0m08s 0m02s 0m12s 2m03s
- MSDOS: 1m49s 2m41s 1m43s 14m43s
-
- Notes:
-
- - the compressed data for 'zoo ah' is always two bytes longer than for
- lha. This is simply because both programs are derived from the same
- source (ar002, written by Haruhiko Okumura, available by ftp in
- ftp://ftp.coast.net/mirrors/SimTel/msdos/archiver/ar002.zip).
-
- - hpack 0.75a gives slightly different results on SunOS. (To be checked
- with latest version of hpack).
-
- - the MSDOS versions are all optimized with assembler code and were run
- on a RAM disk. So it is not surprising that they often go faster than
- their Unix equivalent.
-
- ------------------------------------------------------------------------------
-
- Subject: [7] Which books should I read?
-
-
- [BWC 1989] Bell, T.C, Cleary, J.G. and Witten, I.H, "Text Compression",
- Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$60
- The reference on text data compression.
-
- [Nel 1996] Mark Nelson & Jean-loup Gailly, "The Data Compression Book",
- 2nd edition. M&T Books, New York, NY 1996. ISBN 1-55851-434-1
- 541 pages. List price in the US is $39.95 including one PC-compatible
- disk bearing all the source code printed in the book.
- A practical introduction to data compression.
- The book is targeted at a person who is comfortable reading C code but
- doesn't know anything about data compression. Its stated goal is to get
- you up to the point where you are competent to program standard
- compression algorithms.
-
- [Will 1990] Williams, R. "Adaptive Data Compression", Kluwer Books, 1990.
- ISBN: 0-7923-9085-7. Price: US$75.
- Reviews the field of text data compression and then addresses the
- problem of compressing rapidly changing data streams.
-
- [Stor 1988] Storer, J.A. "Data Compression: Methods and Theory", Computer
- Science Press, Rockville, MD. ISBN: 0-88175-161-8.
- A survey of various compression techniques, mainly statistical
- non-arithmetic compression and LZSS compression. Includes complete Pascal
- code for a series of LZ78 variants.
-
- [Stor 1992] Storer, J.A. "Image and Text Compression", Kluwer Academic
- Publishers, 1992, ISBN 0-7923-9243-4
-
- [Say 1996] Sayood, Khalid. "Introduction to Data Compression",
- San Francisco: Morgan Kaufmann Publishers, 1996. ISBN 1-55860-346-8;
- US&Canada $64.95. More info in http://www.mkp.com/pages/3468/index.html
- The book covers both lossy and lossless compression techniques and their
- applications to image, speech, text, audio, and video compression.
-
- [BK 95] Bhaskaran V. and Konstantinides K., "Image and Video Compression
- Standards: Algorithms and Architectures", Kluwer Academic Publishers, 1995.
- ISBN 0-7923-9591-3
-
- [ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho,
- Kluwer Academic Press, 1991.
-
- [GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray,
- Kluwer Acad. Press, 1991, ISBN 0-7923-9181-0.
-
- [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas
- John Wiley & Sons, 1991. ISBN 0-471-06259-6.
-
- Review papers:
-
- [BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G. "Modeling for Text
- Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557
- A good general overview of compression techniques (as well as modeling for
- text compression); the condensed version of "Text Compression".
-
- [Lele 1987] Lelewer, D.A, and Hirschberg, D.S. "Data Compression", ACM
- Computing Surveys, Vol.19, No.3 (September 1987), p.261.
- A survey of data compression techniques which concentrates on Huffman
- compression and makes only passing mention of other techniques.
-
-
- ------------------------------------------------------------------------------
-
- Subject: [8] What about patents on data compression algorithms?
-
-
- [Note: the appropriate group for discussing software patents is
- comp.patents (or misc.legal.computing), not comp.compression.]
-
- All patents mentioned here are US patents, and thus probably
- not applicable outside the US. See item 70, "Introduction to data
- compression" for the meaning of LZ77, LZ78 or LZW.
-
-
- (a) Run length encoding
-
- - Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009
- granted in 1986 and 1989 respectively. The first one covers run length
- encoding in its most primitive form: a length byte followed by the
- repeated byte. The second patent covers the 'invention' of limiting the
- run length to 16 bytes and thus the encoding of the length on 4 bits.
- Here is the start of claim 1 of patent 4,872,009, just for pleasure:
-
- 1. A method of transforming an input data string comprising a plurality
- of data bytes, said plurality including portions of a plurality of
- consecutive data bytes identical to one another, wherein said data
- bytes may be of a plurality of types, each type representing different
- information, said method comprising the steps of: [...]
-
- - O'Brien has patented (4,988,998) run length encoding followed by LZ77.
-
-
- (b) LZ77
-
- - Waterworth patented (4,701,745) the algorithm now known as LZRW1,
- because Ross Williams reinvented it later and posted it on
- comp.compression on April 22, 1991. (See item 5 for the ftp site
- with all LZRW derivatives.) The *same* algorithm has later been
- patented by Gibson & Graybill (see below). The patent office failed
- to recognize that the same algorithm was patented twice, even though
- the wording used in the two patents is very similar.
-
- The Waterworth patent is now owned by Stac Inc, which won a lawsuit
- against Microsoft, concerning the compression feature of MSDOS 6.0.
- Damages awarded were $120 million. (Microsoft and Stac later
- settled out of court.)
-
- - Fiala and Greene obtained in 1990 a patent (4,906,991) on all
- implementations of LZ77 using a tree data structure. Claim 1 of the
- patent is much broader than the algorithms published by Fiala and
- Greene in Comm.ACM, April 89. The patent covers the algorithm
- published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1,
- pp 16-24). It also covers the algorithms used in lharc, lha and zoo.
-
- - Notenboom (from Microsoft) 4,955,066 uses three levels of
- compression, starting with run length encoding.
-
- - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm
- previously patented by Waterworth and reinvented by Ross Williams.
- Claims 4 and 12 are very general and could be interpreted as
- applying to any LZ algorithm using hashing (including all variants
- of LZ78):
-
- 4. A compression method for compressing a stream of input data into
- a compressed stream of output data based on a minimum number of
- characters in each input data string to be compressed, said
- compression method comprising the creation of a hash table, hashing
- each occurrence of a string of input data and subsequently searching
- for identical strings of input data and if such an identical string
- of input data is located whose string size is at least equal to the
- minimum compression size selected, compressing the second and all
- subsequent occurrences of such identical string of data, if a string
- of data is located which does not match to a previously compressed
- string of data, storing such data as uncompressed data, and for each
- input strings after each hash is used to find a possible previous
- match location of the string, the location of the string is stored
- in the hash table, thereby using the previously processed data to
- act as a compression dictionary.
-
- Claim 12 is identical, with 'method' replaced with 'apparatus'. Since
- the 'minimal compression size' can be as small as 2, the claim could
- cover any dictionary technique of the LZ family. However the text of the
- patent and the other claims make clear that the patent should cover the
- LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely
- to be invalid because of the prior art in the Waterworth patent.)
-
- - Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745)
- but the claims only apply to sorted hash tables, and when the hash
- table is substantially smaller than the window size.
-
- - IBM patented (5,001,478) the idea of combining a history buffer (the
- LZ77 technique) and a lexicon (as in LZ78).
-
- - Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77
- with hashing. The '009 patent was used in the lawsuit against Microsoft
- (see above). Stac also has a patent on LZ77 with parallel lookup in
- hardware (5,003,307).
-
- - Robert Jung, author of 'arj', has been granted patent 5,140,321
- for one variation of LZ77 with hashing. This patent covers the LZRW3-A
- algorithm, also previously discovered by Ross Williams. LZRW3-A was posted
- on comp.compression on July 15, 1991. The patent was filed two months later
- on Sept 4, 1991. (The US patent system allows this because of the
- 'invention date' rule.)
-
- - Chambers 5,155,484 is yet another variation of LZ77 with hashing.
- The hash function is just the juxtaposition of two input bytes,
- this is the 'invention' being patented. The hash table is named
- 'direct lookup table'.
-
-
- (c) LZ78
-
- - One form of the original LZ78 algorithm was patented (4,464,650) by
- its authors Lempel, Ziv, Cohn and Eastman. This patent is owned
- by Unisys.
-
-
- - The LZW algorithm used in 'compress' is patented by IBM (4,814,746)
- and Unisys (4,558,302). It is also used in the V.42bis compression
- standard (see question 11 on V.42bis below), in Postscript Level 2, in
- GIF and TIFF. Unisys sells the license to modem manufacturers for a
- onetime fee (contact: Welch Patent Desk, Unisys Corp., P.O. Box 500,
- Bluebell, PA 19424 Mailcode C SW 19). CompuServe is licensing the
- usage of LZW in GIF products for 1.5% of the product price, of which
- 1% goes to Unisys; usage of LZW in non-GIF products must be licensed
- directly from Unisys. For more information, see http://www.unisys.com/
- or email to lzw_info@unisys.com.
-
- The IBM patent application was first filed three weeks before that of
- Unisys, but the US patent office failed to recognize that they
- covered the same algorithm. (The IBM patent is more general, but its
- claim 7 is exactly LZW.)
-
- - Klaus Holtz also claims that patent 4,366,551 for his "autosophy"
- data compression method covers LZ78 and LZW. According to Holtz, most of
- the largest V.42bis modem manufacturers have paid for patent licenses.
-
- - AP coding is patented by Storer (4,876,541). (Get the yabba package
- for source code, see question 2 above, file type .Y) Storer also
- claims that his patent covers V.42bis.
-
-
- (d) arithmetic coding
-
- - IBM holds many patents on arithmetic coding (4,286,256 4,295,125 4,463,342
- 4,467,317 4,633,490 4,652,856 4,891,643 4,905,297 4,935,882). It has
- patented in particular the Q-coder implementation of arithmetic coding.
- The JBIG standard, and the arithmetic coding option of the JPEG standard
- requires use of the patented algorithm. No JPEG-compatible method is
- possible without infringing the patent, because what IBM actually claims
- rights to is the underlying probability model (the heart of an arithmetic
- coder). (See item 75 for details.)
-
- AT&T has 3 patents on arithmetic coding (4,973,961, 5,023,611, 5,025,258).
-
- (e) predictor
-
- - The 'predictor' algorithm was first described in the paper
-
- Raita, T. and Teuhola, J. (1987), "Predictive text compression by hashing",
- ACM Conference on Information Retrieval
-
- This algorithm has been patented (5,229,768) by K. Thomas in 1993. It
- is used in the Internet Draft "PPP Predictor Compression Protocol" (see
- ftp://venera.isi.edu/internet-drafts/draft-ietf-pppext-predictor-00.txt).
-
-
- As can be seen from the above list, some of the most popular compression
- programs (compress, pkzip, zoo, lha, arj) are now covered by patents.
- (This says nothing about the validity of these patents.)
-
- Here are some references on data compression patents. A number of them are
- taken from the list ftp://prep.ai.mit.edu/pub/lpf/patent-list.
-
- 3,914,586
- Data compression method and apparatus
- filed 10/25/73, granted 10/21/75
- General Motors Corporation, Detroit MI
- Duane E. McIntosh, Santa Ynez CA
- Data compression apparatus is disclosed is operable in either a bit
- pair coding mode of a word coding mode depending on the degree of
- redundancy of the data to be encoded.
-
- 3,976,844
- Data communication system for transmitting data in compressed form
- filed Apr. 4, 1975, granted Aug. 24, 1976
- inventor Bernard K. Betz, assignee Honeywell Information Systems, Inc.
- [encode differences with previous line]
-
- 4,021,782
- Data compaction system and apparatus
- inventor Hoerning
- filed 04/30/1975, granted 05/03/1977
- [A primitive form of LZ77 with implicit offsets (compare with previous record)]
-
- 4,054,951
- Data expansion apparatus
- inventor R.D. Jackson, assignee IBM
- filed Jun. 30, 1976, granted Oct. 18, 1977
- [Covers only decompression of data compressed with a variant of LZ77.]
-
- 4,087,788
- Data compression system
- filed 1/14/77, granted 5/2/78
- NCR Canada LTD - NCR Canada Ltee, Mississauga CA
- Brian J. Johannesson, Waterloo CA
- A data compression system is disclosed in which the left hand boundary
- of a character is developed in the form of a sequence of Freeman
- direction codes, the codes being stored in digital form within a
- processor.
-
- 4,286,256
- Method and means for arithmetic coding using a reduced number of operations.
- granted Aug 25, 1981
- assignee IBM
-
- 4,295,125
- A method and means for pipeline decoding of the high to low order pairwise
- combined digits of a decodable set of relatively shifted finite number of
- strings
- granted Oct 13, 1981
- assignee IBM
-
- 4,366,551
- Associative Memory Search System
- filed June 16, 1975, granted Dec. 28, 1982.
- inventor Klaus Holtz, assignee Omni Dimensional Networks.
-
- 4,412,306
- System for minimizing space requirements for storage and transmission of
- digital signals
- filed May 14, 1981, granted Oct. 25, 1983
- inventor Edward W. Moll
-
- 4,463,342
- A method and means for carry-over control in a high order to low order
- combining of digits of a decodable set of relatively shifted finite number
- strings.
- granted Jul 31, 1984
- assignee IBM
-
- 4,491,934
- Data compression process
- filed May 12, 1982, granted Jan. 1, 1985
- inventor Karl E. Heinz
-
- 4,464,650
- Apparatus and method for compressing data signals and restoring the
- compressed data signals
- inventors Lempel, Ziv, Cohn, Eastman
- assignee Sperry Corporation (now Unisys)
- filed 8/10/81, granted 8/7/84
- A compressor parses the input data stream into segments where each
- segment comprises a prefix and the next symbol in the data stream
- following the prefix. [This is the original LZ78 algorithm.]
-
- 4,467,317
- High-speed arithmetic compression using using concurrent value updating.
- granted Aug 21, 1984
- assignee IBM
-
- 4,494,108
- Adaptive source modeling for data file compression within bounded memory
- filed Jun. 5, 1984, granted Jan. 15, 1985
- invntors Glen G. Langdon, Jorma J. Rissanen
- assignee IBM
- order 1 Markov modeling
-
- 4,558,302
- High speed data compression and decompression apparatus and method
- inventor Welch
- assignee Sperry Corporation (now Unisys)
- filed 6/20/83, granted 12/10/85
- re-examined: filed 12/14/92, granted 4/1/94.
- The text for the original patent can be ftped from ftp.uni-stuttgart.de
- in /pub/doc/comp-patents/US4558302.Z.
- There is also a European Patent 0,129,439 1/2/89 for DE, FR, GB, IT
- and patent pending for Japan.
-
- 4,560,976
- Data compression
- filed 6/5/84, granted 12/24/85
- Codex Corporation, Mansfield MA
- Steven G. Finn, Framingham, MA
- A stream of source characters, which occur with varying relative
- frequencies, is encoded into a compressed stream of codewords, each
- having one, two or three subwords, by ranking the source characters by
- their current frequency of appearance, encoding the source characters
- having ranks no higher than a first number as one subword codewords,
- source characters having ranks higher than the first number but no
- higher than a second number as two subword codewords, and the
- remaining source characters as three subword codewords.
-
- 4,586,027
- Method and system for data compression and restoration
- inventor Tsukimaya et al.
- assignee Hitachi
- filed 08/07/84, granted 04/29/86
- patents run length encoding
-
- 4,597,057
- System for compressed storate of 8-bit ascii bytes using coded strings
- of 4-bit nibbles.
- inventor Snow, assignee System Development corporation.
- filed 12/31/1981, granted 06/24/1986.
- Compression using static dictionary of common words, prefixes and suffixes.
-
- 4,612,532
- Data compression apparatus and method
- inventor Bacon, assignee Telebyte Corportion
- filed Jun. 19, 1984, granted Sep. 16, 1986
- [Uses followsets as in the pkzip 0.92 'reduce' algorithm, but the
- followsets are dynamically updated. This is in effect a sort of order-1
- Markov modeling.]
-
- 4,622,545
- Method and apparatus for image compression and Manipulation
- inventor William D. Atkinson
- assignee Apple computer Inc.
- filed 9/30/82
- granted 11/11/86
-
- 4,633,490
- Symmetrical adaptive data compression/decompression system.
- granted Dec 30, 1985
- assignee IBM
-
- 4,652,856
- A multiplication-free multi-alphabet arithmetic code.
- granted Feb 4, 1986
- assignee IBM
-
- 4,667,649
- Data receiving apparatus
- filed 4/18/84, granted 6/30/87
- inventors Kunishi et al.
- assignee Canon Kabushiki Kaisha, Tokyo Japan
- compression of Fax images.
-
- 4,682,150
- Data compression method and apparatus
- inventors Mathes and Protheroe,
- assignee NCR Corporation, Dayton OH
- A system and apparatus for compressing redundant and nonredundant
- binary data generated as part of an operation of a time and attendance
- terminal in which the data represents the time an employee is present
- during working hours.
-
- 4,701,745
- Data compression system
- inventor Waterworth John R
- assignee Ferranti PLC GB, patent rights now acquired by Stac Inc.
- filed 03/03/1986 (03/06/1985 in GB), granted 10/20/1987
- Algorithm now known as LZRW1 (see above)
- I claim:
- 1. A data compression system comprising an input store for receiving
- and storing a plurality of bytes of uncompressed data from an outside
- source, and data processing means for processing successive bytes of
- data from the input store;
- the data processing means including circuit means operable to check
- whether a sequence of successive bytes to be processed identical with
- a sequence of bytes already processed, and including hash generating
- means responsive to the application of a predetermined number of
- bytes in sequence to derive a hash code appropriate to those bytes, a
- temporary store in which the hash code may represent the address of a
- storage location, and a pointer counter operable to store in the
- temporary store at said address a pointer indicative of the position
- in the input store of one of the predetermined number of bytes;
- output means operable to apply to a transfer medium each byte of data
- not forming part of such an identical sequence; and
- encoding means responsive to the identification of such a sequence to
- apply to the transfer medium an identification signal which identifies
- both the location in the input store of the previous occurrence of the
- sequence of bytes and the number of bytes contained in the sequence.
-
- 4,730,348
- Adaptive data compression system
- inventor MacCrisken, assignee Adaptive Computer Technologies
- filed Sep. 19, 1986, granted Mar. 8, 1988
- [order-1 Markov modeling + Huffman coding + LZ77]
-
- 4,758,899
- Data compression control device
- inventor Tsukiyama, assignee Hitachi
- filed 11/20/1985, granted 07/19/1988
- Limits compression to ensure that tape drive stays busy.
-
- 4,809,350
- Data compression system
- filed Jan. 30, 1987, granted Feb. 28, 1989
- inventor Yair Shimoni & Ron Niv
- assignee Elscint Ltd., Haifa, Israel
- [Image compression via variable length encoding of differences with
- predicted data.]
-
- 4,814,746
- Data compression method
- inventors Victor S. Miller, Mark N. Wegman
- assignee IBM
- filed 8/11/86, granted 3/21/89
- A previous application was filed on 6/1/83, three weeks before the
- application by Welch (4,558,302)
- Communications between a Host Computing System and a number of remote
- terminals is enhanced by a data compression method which modifies the
- data compression method of Lempel and Ziv by addition of new character
- and new string extensions to improve the compression ratio, and
- deletion of a least recently used routine to limit the encoding tables
- to a fixed size to significantly improve data transmission efficiency.
-
- 4,841,092
- continued in 5,003,307
-
- 4,853,696
- Code converter for data compression/decompression
- filed 4/13/87, granted 8/1/89
- inventor Amar Mukherjee, Maitland FL
- assignee University of Central Florida, Orlando FL
- Another hardware Huffman encoder:
- A code converter has a network of logic circuits connected in reverse
- binary tree fashion with logic paths between leaf nodes and a common
- root node.
-
- 4,872,009
- Method and apparatus for data compression and restoration
- inventor Tsukimaya et al.
- assignee Hitachi
- filed 12/07/87, granted 10/03/89
- This patent on run length encoding covers the 'invention' of limiting
- the run length to 16 bytes and thus the encoding of the length on 4 bits.
-
- 4,876,541
- Stem [sic] for dynamically compressing and decompressing electronic data
- filed 10/15/87, granted 10/24/89
- inventor James A. Storer
- assignee Data Compression Corporation
- A data compression system for encoding and decoding textual data,
- including an encoder for encoding the data and for a decoder for
- decoding the encoded data.
-
- 4,891,643
- Arithmetic coding data compression/de-compression by selectively
- employed, diverse arithmetic encoders and decoders.
- granted Jan 2, 1990
- assignee IBM
-
- 4,905,297
- granted Feb 27, 1990
- assignee IBM
- Arithmetic coding encoder and decoder system.
-
- 4,906,991
- Textual substitution data compression with finite length search window
- filed 4/29/1988, granted 3/6/1990
- inventors Fiala,E.R., and Greene,D.H.
- assignee Xerox Corporation
-
- 4,935,882
- Probability adaptation for arithmetic coders.
- granted Jun 19, 1990
- assignee IBM
-
- 4,941,193
- Barnsley, fractal compression.
-
- 4,943,869
- Compression Method for Dot Image Data
- filed 1988-05-04, granted 1990-07-24
- assignee Fuji Photo Film Co.
- Lossy and lossless image compression schemes.
-
- 4,955,066
- Compressing and Decompressing Text Files
- filed 10/13/89, granted 09/04/90
- inventor Notenboom, L.A.
- assignee Microsoft
- Now extended as 5,109,433
- [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0
- Upgrade.]
- A method of compressing a text file in digital form is disclosed.
- A full text file having characters formed into phrases is provided by an
- author. The characters are digitally represented by bytes. A first pass
- compression is sequentially followed by a second pass compression of the
- text which has previously been compressed. A third or fourth level of
- compression is serially performed on the compressed text. For example, in
- a first pass, the text is run-length compressed. In a second pass, the
- compressed text is further compressed with key phrase compression. In a
- third pass, the compressed text is further compressed with Huffman
- compression. The compressed text is stored in a text file having a Huffman
- decode tree, a key phrase table, and a topic index. The data is
- decompressed in a single pass and provided one line at a time as an output.
- Sequential compressing of the text minimizes the storage space required for
- the file. Decompressing of the text is performed in a single pass. As a
- complete line is decompressed, it is output rapidly, providing full text to
- the user.
-
- 4,973,961
- Method and apparatus for carry-over control in arithmetic coding.
- granted Nov 27, 1990
- assignee AT&T
-
- 4,988,998
- Data compression system for successively applying at least two data
- compression methods to an input data stream.
- inventor O'Brien
- assignee Storage Technology Corporation, Louisville, Colorado
- filed Sep 5, 1989, granted Jan 29, 1991.
- Run length encoding followed by LZ77.
-
- 5,001,478
- Method of Encoding Compressed Data
- filed 12/28/89, granted 03/19/91
- inventor Michael E. Nagy
- assignee IBM
- 1. A method of encoding a compressed data stream made up of a sequence of
- literal references, lexicon references and history references, which
- comprises the steps of:
- assigning to each literal reference a literal identifier;
- assigning to each history reference a history identifier;
- assigning to each lexicon reference a lexicon identifier;
- and emitting a data stream with said identifiers assigned to said references.
- Gordon Irlam <gordoni@cs.adelaide.edu.au> says:
- The invention can probably be best understood by considering the
- decompressor. It consists of a history buffer, and a lexicon buffer, both
- of which are initially empty. The history buffer contains the last n
- symbols emitted. Whenever a history buffer reference is to be output the
- string so referenced is subsequently moved to the lexicon buffer for future
- reference. Thus the history buffer keeps track of strings that may be
- repeated on a very short term basis, while the lexicon buffer stores items
- for a longer time. Furthermore a history reference involves specifying
- both the offset and length within the history buffer, whereas a lexicon
- reference simply specifies a number denoting the string. Both buffers have
- a finite size.
-
- 5,003,307
- Data compression apparatus with shift register search means
- filed Oct. 6, 1989, granted Mar. 26, 1991
- inventors George Glen A, Ivey Glen E, Whiting Douglas L
- assignee Stac Inc
- continuation of 4,841,092
-
- 5,016,009
- Data compression apparatus and method
- filed 01/13/1989, granted 05/14/1991
- inventors George Glen A, Ivey Glen E, Whiting Douglas L
- assignee Stac Inc
- LZ77 with offset hash table (extended in 5,126,739)
-
- 5,023,611
- Entropy encoder/decoder including a context extractor.
- granted Jun 11, 1991
- assignee AT&T
-
- 5,025,258
- Adaptive probability estimator for entropy encoder/decoder.
- granted Jun 18, 1991
- assignee AT&T
-
- 5,049,881
- Apparatus and method for very high data rate-compression incorporating
- lossless data compression and expansion utilizing a hashing technique
- inventors Dean K. Gibson, Mark D. Graybill
- assignee Intersecting Concepts, Inc.
- filed 6/18/90, granted 9/17/91
- [covers lzrw1, almost identical with Waterworth 4,701,745]
-
- 5,051,745
- String searcher, and compressor using same
- filed 8/21/90, granted 9/24/91
- inventor Phillip W. Katz (author of pkzip)
- In the string search method and apparatus pointers to the string to be
- searched are indexed via a hashing function and organized according to the
- hashing values of the string elements pointed to. The hashing function is
- also run on the string desired to be found, and the resulting hashing value
- is used to access the index. If the resulting hashing value is not in the
- index, it is known that the target string does not appear in the string
- being searched. Otherwise the index is used to determine the pointers which
- correspond to the target hashing value, these pointers pointing to likely
- candidates for matching the target string. The pointers are then used to
- sequentially compare each of the locations in the string being searched to
- the target string, to determine whether each location contains a match to
- the target string.
- In the method and apparatus for compressing a stream of data symbols, a
- fixed length search window, comprising a predetermined contiguous portion
- of the symbol stream, is selected as the string to be searched by the
- string searcher. If a string to be compressed is found in the symbol
- stream, a code is output designating the location within the search window
- of the matching string and the length of the matching string.
-
- 5,065,447 (continued in 5,347,600)
- Method and apparatus for processing digital data
- filed Jul. 5, 1989, granted Nov. 12, 1991
- inventors Michael F. Barnsley and Alan D. Sloan
- [Patents image compression with the "Fractal Transform"]
-
- 5,109,433
- Compressing and decompressing text files
- inventor Notenboom
- assignee Microsoft
- extension of 4,955,066
-
- 5,126,739
- Data Compression Apparatus and Method
- filed Nov. 27, 1990, granted June 30, 1992.
- inventor Whiting et. al
- assignee Stac Inc
- LZ77 with offset hash table (extension of 5,016,009)
-
- 5,140,321
- Data compression/decompression method and apparatus
- filed 9/4/91, granted 8/18/92
- inventor Robert Jung
- assignee Prime Computer
-
- 5,155,484
- Fast data compressor with direct lookup table indexing into history buffer
- filed 9/13/1991, granted 10/13/1992
- inventor Chambers, IV, Lloyd L., Menlo Park, California
- assignee Salient Software, Inc., Palo Alto, California (02)
- Uses a 64K hash table indexed by the first two characters of
- the input string. Includes several claims on the LZ77 file format
- (literal or pair offset,length).
-
- 5,179,378
- file Jul. 30, 1991, granted Jan. 12, 1993
- inventor Ranganathan
- assignee University of South Florida
- Method and apparatus for the compression and decompression of data
- using Lempel-Ziv based techniques.
- [This covers LZ77 hardware compression with a systolic array of
- processors working in parallel.]
-
- 5,229,768
- Adaptive data compression system
- granted Jul. 20, 1993
- inventor Kasman E. Thomas
- assignee Traveling Software, Inc.
- A system for data compression and decompression is disclosed. A series of
- fixed length overlapping segments, called hash strings, are formed from an
- input data sequence. A retrieved character is the next character in the input
- data sequence after a particular hash string. A hash function relates a
- particular hash string to a unique address in a look-up table (LUT). An
- associated character for the particular hash string is stored in the LUT at
- the address. When a particular hash string is considered, the content of the
- LUT address associated with the hash string is checked to determine whether
- the associated character matches the retrieved character following the hash
- string. If there is a match, a Boolean TRUE is output; if there is no match,
- a Boolean FALSE along with the retrieved character is output. Furthermore, if
- there is no match, then the LUT is updated by replacing the associated
- character in the LUT with the retrieved character. [...]
- [This algorithm is used in the Internet Draft "PPP Predictor
- Compression Protocol".]
-
- 5,347,600 (continuation of 5,065,447)
- Method and apparatus for compression and decompression of digital image
- filed 10/23/1991, granted 09/13/1994
- inventors Barnsley and Sloan
-
- 5,384,867 (continued in 5,430,812)
- filed 10/23/1991, granted 01/24/1995
- Fractal transform compression board
- inventors Barnsley et al.
-
- 5,416,856
- Method of encoding a digital image using iterated image transformations
- to form an eventually contractive map
- filed 1992/03/30, granted 1995/05/16
- inventors Jacobs, Boss and Fisher
-
- 5,430,812 (continuation of 5,384,867)
- Fractal transform compression board
- filed 1994/05/18, granted 1995/07/04
- inventors Barnsley et al.
-
- Japan 2-46275
- Coding system
- granted Feb 26, 1990
- [Patents one form of arithmetic coding.]
-
-
- ------------------------------------------------------------------------------
-
- Subject: [9] Compression of random data (WEB, Gilbert and others)
-
-
- [Note from the FAQ maintainer: this topic has generated and is still generating
- the greatest volume of news in the history of comp.compression. Read this
- before posting on this subject.
-
- I intended to remove the WEB story from the FAQ, but similar affairs come up
- regularly on comp.compression. The advertized revolutionary methods have all
- in common their supposed ability to compress random or already compressed data.
- I will keep this item in the FAQ to encourage people to take such claims with
- great precautions.]
-
-
- 9.1 Introduction
-
- It is mathematically impossible to compress without loss truly random data (see
- below and also item 73 in part 2 of this FAQ). Yet from time to time some
- people claim to have invented a new algorithm for doing so. Such algorithms are
- claimed to be applicable recursively, that is, applying the compressor to the
- compressed output of the previous run, possibly multiple times. Fantastic
- compression ratios of over 100:1 on random data are claimed to be actually
- obtained.
-
- Such claims inevitably generate a lot of activity on comp.compression, which
- can last for several months. The two largest bursts of activity were generated
- by WEB Technologies and by Jules Gilbert. Premier Research Corporation
- (with a compressor called MINC) made only a brief appearance. David C. James
- is a new contender with a patent obtained in July 96.
-
- Other people have also claimed incredible compression ratios, but the programs
- (OWS, WIC) were quickly shown to be fake (not compressing at all). This topic
- is covered in item 10 of this FAQ.
-
-
- 9.2 The counting argument
-
- The WEB compressor (see details in section 9.3 below) was claimed to compress
- without loss *all* files of greater than 64KB in size to about 1/16th their
- original length. A very simple counting argument shows that this is impossible,
- regardless of the compression method. It is even impossible to guarantee
- lossless compression of all files by at least one bit. (Many other proofs have
- been posted on comp.compression, please do not post yet another one.)
-
- Assume that the program can compress without loss all files of size >= N bits.
- Compress with this program all the 2^N files which have exactly N bits. All
- compressed files have at most N-1 bits, so there are at most (2^N)-1 different
- compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on,
- down to 1 file of size 0]. So at least two different input files must compress
- to the same output file. Hence the compression program cannot be
- lossless. (Much stronger results about the number of incompressible files can
- be obtained, but the proofs are a little more complex.)
-
- This argument applies of course to WEB's case (take N = 64K*8 bits). Note that
- no assumption is made about the compression algorithm. The proof applies to
- *any* algorithm, including those using an external dictionary, or repeated
- application of another algorithm, or combination of different algorithms, or
- representation of the data as formulas, etc... All schemes are subject to the
- counting argument. There is no need to use information theory to provide a
- proof, just basic mathematics. [People interested in more elaborate proofs can
- consult http://wwwvms.utexas.edu/~cbloom/news/nomagic.html ]
-
- This assumes of course that the information available to the decompressor is
- only the bit sequence of the compressed data. If external information such as a
- file name, a number of iterations, or a bit length is necessary to decompress
- the data, the bits necessary to provide the extra information must be included
- in the bit count of the compressed data. Otherwise, it would be sufficient to
- consider any input data as a number, use this as the file name, iteration count
- or bit length, and pretend that the compressed size is zero. For an example of
- storing information in the file name, see the program lmfjyh in the 1993
- International Obfuscated C Code Contest, available on all comp.sources.misc
- archives (Volume 39, Issue 104).
-
- A common flaw in the algorithms claimed to compress all files is to assume that
- arbitrary bit strings can be sent to the decompressor without actually
- transmitting their bit length. If the decompressor needs such bit lengths
- to decode the data (when the bit strings do not form a prefix code), the
- number of bits needed to encode those lengths must be taken into account
- in the total size of the compressed data.
-
- Another common (but still incorrect) argument is to assume that for any file,
- some still to be discovered algorithm might find a seed for a pseudo-random
- number generator which would actually generate the whole sequence of bytes
- contained in the file. However this idea still fails to take into account the
- counting argument. For example, if the seed is limited to 64 bits, this
- algorithm can generate at most 2^64 different files, and thus is unable to
- compress *all* files longer than 8 bytes.
-
- Steve Tate <srt@cs.unt.edu> suggests a good challenge for programs
- that are claimed to compress random data by a significant amount:
-
- Here's a wager for you: First, send me the DEcompression algorithm. Then I
- will send you a file of whatever size you want, but at least 100k. If you
- can send me back a compressed version that is even 20% shorter (80k if the
- input is 100k) I'll send you $100. Of course, the file must be able to be
- decompressed with the program you previously sent me, and must match
- exactly my original file. Now what are you going to provide
- when... er... if you can't demonstrate your compression in such a way?
-
- So far no one has accepted this challenge (for good reasons).
-
-
- 9.3 The WEB 16:1 compressor
-
- 9.3.1 What the press says
-
- April 20, 1992 Byte Week Vol 4. No. 25:
-
- "In an announcement that has generated high interest - and more than a
- bit of skepticism - WEB Technologies (Smyrna, GA) says it has
- developed a utility that will compress files of greater than 64KB in
- size to about 1/16th their original length. Furthermore, WEB says its
- DataFiles/16 program can shrink files it has already compressed."
- [...]
- "A week after our preliminary test, WEB showed us the program successfully
- compressing a file without losing any data. But we have not been able
- to test this latest beta release ourselves."
- [...]
- "WEB, in fact, says that virtually any amount of data can be squeezed
- to under 1024 bytes by using DataFiles/16 to compress its own output
- multiple times."
-
- June 1992 Byte, Vol 17 No 6:
-
- [...] According to Earl Bradley, WEB Technologies' vice president of
- sales and marketing, the compression algorithm used by DataFiles/16
- is not subject to the laws of information theory. [...]
- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
- 9.3.2 First details, by John Wallace <buckeye@spf.trw.com>
-
- I called WEB at (404)514-8000 and they sent me some product
- literature as well as chatting for a few minutes with me on the phone.
- Their product is called DataFiles/16, and their claims for it are
- roughly those heard on the net.
-
- According to their flier:
-
- "DataFiles/16 will compress all types of binary files to approximately
- one-sixteenth of their original size ... regardless of the type of
- file (word processing document, spreadsheet file, image file,
- executable file, etc.), NO DATA WILL BE LOST by DataFiles/16."
- (Their capitalizations; 16:1 compression only promised for files >64K
- bytes in length.)
-
- "Performed on a 386/25 machine, the program can complete a
- compression/decompression cycle on one megabyte of data in less than
- thirty seconds"
-
- "The compressed output file created by DataFiles/16 can be used as the
- input file to subsequent executions of the program. This feature of
- the utility is known as recursive or iterative compression, and will
- enable you to compress your data files to a tiny fraction of the
- original size. In fact, virtually any amount of computer data can
- be compressed to under 1024 bytes using DataFiles/16 to compress its
- own output files muliple times. Then, by repeating in reverse the
- steps taken to perform the recusive compression, all original data
- can be decompressed to its original form without the loss of a single
- bit."
-
- Their flier also claims:
-
- "Constant levels of compression across ALL TYPES of FILES"
- "Convenient, single floppy DATA TRANSPORTATION"
-
- From my telephone conversation, I was assured that this is an
- actual compression program. Decompression is done by using only the
- data in the compressed file; there are no hidden or extra files.
-
-
- 9.3.3 More information, by Rafael Ramirez <rafael.ramirez@channel1.com>:
-
- Today (Tuesday, 28th) I got a call from Earl Bradley of Web
- who now says that they have put off releasing a software version of
- the algorithm because they are close to signing a major contract with
- a big company to put the algorithm in silicon. He said he could not
- name the company due to non-disclosure agreements, but that they had
- run extensive independent tests of their own and verified that the
- algorithm works. [...]
-
- He said the algorithm is so simple that he doesn't want anybody
- getting their hands on it and copying it even though he said they
- have filed a patent on it. [...] Mr. Bradley said the silicon version
- would hold up much better to patent enforcement and be harder to copy.
-
- He claimed that the algorithm takes up about 4K of code, uses only
- integer math, and the current software implementation only uses a 65K
- buffer. He said the silicon version would likely use a parallel
- version and work in real-time. [...]
-
-
- 9.3.4 No software version
-
- Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>:
-
- tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992
- Comment(s).
- ----------
- TITLE: WEB Technology
- I promised everyone a report when I finally got the poop on WEB's
- 16:1 data compression. After talking back and forth for a year
- and being put off for the past month by un-returned phone calls,
- I finally got hold of Marc Spindler who is their sales manager.
-
- _No_ software product is forth coming, period!
-
- He began talking about hardware they are designing for delivery
- at the end of the year. [...]
-
-
- 9.3.5 Product cancelled
-
- Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992:
-
- [Long story omitted, confirming the reports made above about the
- original WEB claims.]
-
- 10JUL92 - Called to Check Status. Was told that testing had uncovered a
- new problem where 'four numbers in a matrix were the same
- value' and that the programmers were off attempting to code a
- preprocessor to eliminate this rare case. I indicated that he
- had told me this story before. He told me that the
- programmers were still working on the problem.
-
- 31JUL92 - Final Call to Check Status. Called Earl in the morning and
- was told that he still had not heard from the programmers. [...]
- Stated that if they could not resolve the problem then there would
- probably not be a product.
-
- 03AUG92 - Final Call. Earl claims that the programmers are unable to
- resolve the problem. I asked if this meant that there would
- not be a product as a result and he said yes.
-
-
- 9.4 Jules Gilbert
-
- As opposed to WEB Technologies, Jules Gilbert <coffee@spock.ici.net> does not
- claim to compress *all* files, but only "random or random-appearing" files.
- Here are some of his articles posted to compr.compression; to keep this section
- to a reasonable size, some parts marked with [...] have been removed. The demo
- mentioned in the first article has been canceled 6 days later. No comments or
- conclusion are given here since this thread is still going on in
- comp.compression at the time of writing.
-
- From: coffee@spock.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Re: No Magic Compressors, No Factoring Compressors, Jules Gilbert
- is a liar
- Date: 14 May 1996 03:13:31 -0400
- Message-ID: <4n9bqr$89k@spock.ici.net>
-
- [...]
- I will, in front of several Boston area computer scientists ('monitors'),
- people I choose but generally known to be fair and competent, under
- conditions which are sufficient to prevent disclosure of the method and fully
- protect the algorithm and other aspects of the underlying method from
- untoward discovery, use two computers, (which I am permitted to examine but
- not alter) with both machine's running Linux, and with the file-systems and
- Linux OS freshly restored from commercial CD-ROM's do the following:
-
- On one machine (the 'src-CPU') will be loaded a copy of the CALGARY-CORPUS.
- (Or other agreed on '.ZIP' or '.ARJ' file.)
-
- I will compress the CALGARY-CORPUS for transfer from the src-CPU onto 3.5"
- disks and transfer it (by sneaker-net) to the other machine for decompression
- and produce a perfect copy of the CORPUS file on the 'dst-CPU'.
-
- The CORPUS archive contents will not be 'cracked', ie', the original CORPUS
- can be encrypted and the password kept from me. All I care about is that the
- input file is highly random-aprearing.
-
- I claim that I can perform this process several times, and each iteration
- will reduce the overall file by at least 50%, ie., a ratio of 2:1. An
- 'iteration' will constitute copying, using compression, from the src-CPU to
- the dst-CPU, and then reversing the direction to achieve another iteration.
-
- For example, for say a 4M input file, it is reasonable to expect an
- approximately 1M output file, after two complete iterations.
- [...]
- ONLY RANDOM OR RANDOM-APPEARING DATA INPUT CAN BE COMPRESSED BY MY METHOD.
- [...]
- If one iteration (of the compression 'sandwich') consists of two parts, say
- an LZ phase followed by a JG phase, the LZ method will compression by
- perhaps a ration of 2:1 (at the first iteration), perhaps much better if the
- input is text, and the JG phase will do 3-4:1, but slowly!! During
- subsequent iterations, the LZ phase will do perhaps 1.25:1 and the JG phase
- will continue to do about 3-4:1.
-
- Experimentally, I have achieved compression results of nearly 150:1, overall,
- ^^^^^^^^^^^^^^ ^^^^^
- for a 60M file. (I started with a '.arj' archive of a large DOS partition.)
- [...]
- ----------------------------------------------------------------------------
- From: coffee@spock.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Re: Explanation: that uh, alg thing...
- Date: 15 May 1996 16:38:18 -0400
- Message-ID: <4ndfbq$cf3@spock.ici.net>
-
- [...]
- One more thing, I am preparing a short technical note to deal with the reason
- most programmers' and computer scientists' think it's impossible to (further)
- compress random input. (Many people think that because you can't get more
- than 2^N messages from a N-bit compressed msg, that it means that you can't
- compress random input. (Lot's of folks have told me that.) The short story
- is:
-
- I agree that you can not get more than 2^N messages from N bits. No question
- about it. BUT THAT STATMENT HAS NOTHING TO DO WHATSOEVER WITH THE
- INTERPRETATION OF WHAT THOSE BITS 'MEAN'.
- [...]
- ----------------------------------------------------------------------------
- From: coffee@spock.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Seeing is believing!
- Date: 9 Jun 1996 03:20:52 -0400
- Message-ID: <4pdu0k$otg@spock.ici.net>
-
- [...]
- If your firm needs industrial-strength compression, contact 'coffee@ici.net'
- and ask us for an on-site demonstration of our MR2 compressors. Each can
- compress large files of 'random-appearing' information, whether RSA-encrypted
- blocks, or files already compressed using LZ-techniques.
-
- Our demonstration will give you the opportunity to observe compression of
- 'random-appearing' files of at least 100MB by at least 3:1 per iteration.
- Usually, several iterations are possible. (These are minimum figures easily
- exceeded.)
- [...]
- ----------------------------------------------------------------------------
- From: coffee@spock.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Re: My remarks on Jules Gilbert
- Date: 24 Jul 1996 18:05:44 -0400
- Message-ID: <4t66no$9qq@spock.ici.net>
-
- [...]
- My claims can not possibly be true IF I'M PLAYING BY THE 'RULES' THAT YOU
- ASSUME APPLY TO ME. (Sorry to shout).
-
- Clearly, anyone sending a signal (in the Shannon context), is constrained by
- limits which make it impossible to compress RAD ('random-appearing data')
- input.
- [...]
- 1) I can't compress bits any better than the next guy. Maybe not as well,
- in fact.
-
- 2) I have designed an engine that accepts RAD input and emits far too little
- data to reconstitute the original data, based on conventional
- assumptions. Okay! I know this.
-
- 3) But, I none-the-less reconstitute the original data.
- [...]
- ----------------------------------------------------------------------------
- From: coffee@soran.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Re: Jules Gilbert's New Compresssion Technology
- Date: 12 Aug 1996 08:11:10 -0400
- Message-ID: <4un70u$a2r@soran.ici.net>
-
- I have multiple methods for compressing RAD. Watch carefully:
-
- MR1 does 3:1, on large buffers and is repeatable until the volume of input
- data falls below 128k or so. (This figure is under user control, but
- compreesion quality will suffer as the buffer size is decreased). Recent
- changes make this method about as fast as any conventional compressor.
-
- MR2 does at least 6:1, with a minimum buffer size of perhaps 32k. It is also
- repeatable. MR2 does not actually compress, though. Instead, it translates
- an input buffer into an output buffer of roughly equivalent size. This
- output buffer contains mostly constants, and other things, such as simple
- sequences: 28,29,31,32,33,35,40,41,42,43,44,45. (An actual sequence of
- bytes). Obviously, this kind of information is readily compressed, and that
- is why I claim that MR2 can achieve a minimum of 6:1. Again, like MR1, this
- process can be re-applied over it's own output.
-
- When, I've said, "No, it's impossible to compress by 100:1" I was trying to
- get this audience to see this as realistic. But I can compress RAD files
- 100:1 if allowed to re-process the output through the same process. I first
- actually achieved a 100:1 compression level in March of this year using tools
- ^^^^^^^^^^^^^^^^^^^^^^^^^
- designed for experimenting in RAD issues. But now I have C programs which
- have been written to be easy to understand and are intended to be part of my
- technology transfer process for clients.
- [...]
- So, can someone compress by 100:1 or even 1000:1? Yes! But ONLY if the input
- file is sufficiently large. A 1000:1 compression ratio would require a very
- large input file, and, at least for PC users, archive files of this size are
- almost never produced.
- ----------------------------------------------------------------------------
- From: coffee@soran.ici.net (Jules Gilbert)
- Newsgroups: comp.compression
- Subject: Re: Gilbert's RAD compression product
- Date: 18 Aug 1996 08:40:28 -0400
- Message-ID: <4v72vs$quc@soran.ici.net>
-
- [...]
- (In my original remarks), I am quoted above as claiming that a 3,152,896 byte
- 'tar 'file (conventionally compressed to 1,029,790 bytes) can be compressed
- to 50*1024 bytes. It's an accurate quote.
-
- Now how can that be possible?
-
- If a gzip compressed version of the Corpus requires roughly a 1MB, what do I
- do with the 950k bytes I don't store in the compressed intermediate file?
-
- Well, that's certainly a puzzler!
-
- For now, all I will say is that it does not go into the compressed
- intermediate file. And because it doesn't, Shannons' channel capacity axioms
- apply only to the 50k component.
-
-
- 9.5 David C. James
-
- In July 96, David C. James was granted patent 5,533,051 "Method for data
- compression" for a method claimed to be effective even on random data. No
- comments or conclusion are given here since this thread is still going on in
- comp.compression at the time of writing.
-
- From: u137@aol.com (Peter J. Cranstone)
- Newsgroups: comp.compression
- Subject: Re: Jules Gilbert's Compression Technology
- Date: Sun Aug 18 12:48:11 EDT 1996
-
- Wh have just been issued a patent (US. #5,533,051) and have several more
- pending on a new method for data compression. It will compess all types of
- data, including "random", and data containing a uniform distribution of
- "0's" and "1's".
- [...]
-
- Here is the abstract for patent 5,533,051:
-
- Methods for compressing data including methods for compressing highly
- randomized data are disclosed. Nibble encode, distribution encode, and direct
- bit methods are disclosed for compressing data which is not highly
- randomized. A randomized data compression routine is also disclosed and is
- very effective for compressing data which is highly randomized. All the
- compression methods disclosed operate on a bit level and accordingly are
- insensitive to the nature or origination of the data sought to be compressed.
- Accordingly the methods of the present invention are universally applicable
- to any form of data regardless of its source of origination.
-
- ------------------------------------------------------------------------------
-
- Subject: [10] Fake compression programs (OWS, WIC)
-
-
- Some programs claimed to achieve incredible compression ratios are completely
- fake: they do not compress at all but just stored the uncompressed data in
- hidden files on the hard disk or keep it in unused clusters. Needless to say,
- such programs are dangerous and should never be used because there is a
- significant risk of losing all the data.
-
- The OWS program just remembers which clusters contained the data on the hard
- disk. The data can be recovered only if those clusters are not used again for
- another file.
-
- The WIC program searches for the first directory in drive C: and creates a
- hidden file called WINFILE.DLL containing a copy of all the original files.
- If you copy the compressed file to another computer (which doesn't have the
- file WINFILE.DLL), WIC reports a CRC error.
-
- ------------------------------------------------------------------------------
-
- Subject: [11] What is the V.42bis standard?
-
-
- A description of the V.42bis standard is given in "The V.42bis
- standard for data-compressing modems," by Clark Thomborson
- <cthombor@theory.lcs.mit.edu>, IEEE Micro, Oct 1992, pp. 41-53.
-
- Short introduction, by Alejo Hausner <hausner@qucis.queensu.ca>:
-
- The V.42bis Compression Standard was proposed by the International
- Consultative Committee on Telephony and Telegraphy (CCITT, now ITU-T) as
- an addition to the v.42 error-correction protocol for modems. Its purpose
- is to increase data throughput, and uses a variant of the
- Lempel-Ziv-Welch (LZW) compression method. It is meant to be
- implemented in the modem hardware, but can also be built into the
- software that interfaces to an ordinary non-compressing modem.
-
- V.42bis can send data compressed or not, depending on the
- data. There are some types of data that cannot be
- compressed. For example, if a file was compressed first,
- and then sent through a V.42bis modem, the modem would not
- likely reduce the number of bits sent. Indeed it is likely
- that the amount of data would increase somewhat.
-
- To avoid this problem, the algorithm constantly monitors the
- compressibility of the data, and if it finds fewer bits
- would be necessary to send it uncompressed, it switches to
- transparent mode. The sender informs the receiver of this
- transition through a reserved code word. Henceforth the
- data is passed as plain bytes.
-
- While transmitting in transparent mode, the sender maintains
- the LZW trees of strings, and expects the receiver to do
- likewise. If it finds an advantage in returning to
- compressed mode, it will do so, first informing the receiver
- by a special escape code. Thus the method allows the
- hardware to adapt to the compressibility of the data.
-
- The choice of escape code is clever. Initially, it is a
- zero byte. Any occurrence of the escape code is replaced,
- as is customary, by two escape codes. In order to prevent a
- string of escape codes from temporarily cutting throughput
- in half, the escape code is redefined by adding 51 mod 256
- each time it is used.
-
-
- A note from Peter Gutman <pgut01@cs.auckland.ac.nz> about V.42bis
- implementations:
-
- V.42bis is covered by patents, and the licensing terms are rather complex
- because you need to license it from multiple organisations. At one point
- British Telecom were charging something like 30,000 pounds for a license
- (this was a few years ago, things may have changed since then). Because of
- this, noone has ever implemented a freely-available version of V.42bis as
- you'd find in a modem. There is a Unix implementation (called "compact") of
- a V.42bis-like algorithm which comes with a great many disclaimers that it
- can only be used for research purposes. [Note from FAQ maintainer: "compact"
- is available in
- http://ftp.sunet.se/ftp/pub/usenet/comp.sources.misc/volume15/compact_sv/
- The 'shrink' method of zip 1.1 (see item 2 above) is also similar to V.42bis]
-
- If you've ever wondered why noone other than modem manufacturers ever use
- V.42bis for anything, this is it.
-
-
- The CCITT (ITU-T) standards documents used to be available by ftp on
- ftp.uu.net in /doc/standards/ccitt, but this service has been
- discontinued. If you ftp to digital.resource.org, in directory
- pub/standards there is a file that says that making the standards
- available in the first place was just an experiment.
-
- The documents are now on src.doc.ic.ac.uk, but the directory name
- keeps changing. Check one of:
- /computing/ccitt/ccitt-standards/ccitt/
- /computing/ccitt/standards/ccitt
- /doc/ccitt-standards/ccitt
- in this order. The v42bis standard is in *standards/ccitt/1992/v/v42bis.asc.Z.
-
- See also item 20 below for other sites with standards documents.
-
- A mail server for CCITT (ITU-T) documents is available at teledoc@itu.arcom.ch
- or itudoc@itu.ch. A Gopher server is also available at gopher://info.itu.ch
-
- See also the Standards FAQ posted to news.answers or get it by ftp in
- ftp://rtfm.mit.edu/pub/usenet/news.answers/standards-faq
-
- For ISO documents, try http://www.iso.ch/
-
- ------------------------------------------------------------------------------
-
- Subject: [12] I need source for the winners of the Dr Dobbs compression contest
-
-
- The source of the top 6 programs of the Feb 91 Dr Dobbs data compression
- contest are available by ftp on
- ftp://ftp.coast.net/mirrors/SimTel/msdos/compress/ddjcompr.zip
- ftp://garbo.uwasa.fi/pc/source/ddjcompr.zip
-
- The sources are in MSDOS end-of-line format, one directory per
- program. Unix or VMS users, use "unzip -a ddjcompr" to get correct
- end-of-lines (add -d to recreate the directory structure if you are
- using an obsolete version of unzip such as 4.1). Three of the 6
- programs are not portable and only run on MSDOS. compact and urban
- work on Unix, sixpack only requires minor modifications.
-
- ------------------------------------------------------------------------------
-
- Subject: [13] I need source for arithmetic coding
-
-
- (See question 70 for an introduction to arithmetic coding.)
-
- The source for the arithmetic coder described in Chap.5 of Bell,
- Cleary, and Witten's book "Text Compression" (see question 7 above)
- (or, equivalently, in: Witten, Neal, and Cleary's article "Arithmetic
- Coding for data Compression" from Communications of the Association
- for Computing Machinery, 30 (6), pp.520-540, June, 1987) is available
- via anonymous ftp from ftp.cpsc.ucalgary.ca (136.159.7.18) in directory
- /pub/projects/ar.cod. It only comes with a simple order-0 model
- but it's set up so that adding your own more sophisticated one is
- straightforward. Look also in ftp://munnari.mu.oz.au/pub/arith_coder
-
- A low precision arithmetic coding implementation avoiding hardware
- division is available on the same site (ftp.cpsc.ucalgary.ca) in
- /pub/projects/arithmetic.coding/low.precision.version, file
- low.precision.version.shar.
-
- Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization
- with Arithmetic Coding." It describes an arithmetic coding technique
- which is quite general and computationally inexpensive. The
- documentation and example C code are available via anonymous ftp from
- media-lab.media.mit.edu (18.85.0.2), in /pub/k-arith-code.
-
- The program 'urban' in ddjcompr.zip (see item 12 above) is a high order
- arithmetic coder working at the bit level. It is written by Urban Koistinen
- <md85-epi@nada.kth.se>.
-
- The DMC program is available in ftp://plg.uwaterloo.ca/pub/dmc/*.c. It
- implements the algorithm described in "Data Compression using Dynamic
- Markov Modelling", by Gordon Cormack and Nigel Horspool, Computer
- Journal 30:6 (December 1987). This program uses Guazzo's version of
- arithmetic coding.
-
- ------------------------------------------------------------------------------
-
- Subject: [15] Where can I get image compression programs?
-
-
- JPEG:
- Source code for most any machine:
- ftp://ftp.uu.net/graphics/jpeg/jpegsrc.v6a.tar.gz
- ftp://nic.funet.fi/pub/graphics/packages/jpeg/jpegsrc.v6.tar.gz
- Contact: jpeg-info@uunet.uu.net (Independent JPEG Group)
-
- havefun.stanford.edu:pub/jpeg/JPEGv1.2.1.tar.Z (supports lossless mode)
- Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
-
- ftp://ftp.cs.cornell.edu/pub/multimed/ljpg.tar.Z (lossless jpeg)
-
- xv, an image viewer which can read JPEG pictures, is available in
- ftp://ftp.cis.upenn.edu/pub/xv/xv-3.10a.tar.Z
-
- MPEG:
- ftp://havefun.stanford.edu/pub/mpeg/MPEGv1.2.1.tar.Z
- Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
-
- ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg/play/
- mpeg_play-2.3-patched-src.tar.gz
- Contact: mpeg-bugs@cs.berkeley.edu
-
- ftp://flash.bu.edu/pub/code/mpeg_system/mpeg_system_source_v1.0.tar.gz
- (MPEG-I Multi-Stream System Layer encoder/player; includes an
- enhanced version of mpeg_play)
- Contact: Jim Boucher <jboucher@spiderman.bu.edu> or Ziv Yaar <zyaar@bu.edu>
-
- ftp://ftp.mni.mcgill.ca/pub/mpeg/mpeg_lib-1.2.tar.gz [MPEG library]
- Contact: Gregory Ward <greg@pet.mni.mcgill.ca>
-
- ftp://ftp.netcom.com/pub/cfogg/mpeg/vmpeg/vmpeg17.exe
- Contact: Stefan Eckart <stefan@lis.e.technik.tu-muenchen.de>
- ftp://decel.ecel.uwa.edu.au/users/michael/mpegw32f.zip (for Windows and NT)
-
- ftp://nvr.com/pub/NVR-software/Product-1.0.4.tar.Z
- (free demo copy of NVR's software toolkit for SPARCstations)
- Contact: Todd Brunhoff <toddb@nvr.com>
-
- ftp://ftp.netcom.com/pub/cfogg/mpeg2/* (MPEG-2 encoder and decoder)
- Contact: MPEG-L@netcom.com (MPEG Software Simulation Group)
-
- H.261(P*64):
- havefun.stanford.edu:pub/p64/P64v1.2.tar.Z
- Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
-
- ftp://zenon.inria.fr/rodeo/ivs/last_version/ivs*-src.tar.gz
- (Inria videoconference system)
- Contact: Thierry Turletti <turletti@sophia.inria.fr> (see item 20 below).
-
- H.263: (by Telenor Research)
- http://www.nta.no/brukere/DVC/h263_software
-
- JBIG:
- ftp://nic.funet.fi/pub/graphics/misc/test-images/jbig.tar.gz.
-
- ftp://ftp.informatik.uni-erlangen.de/pub/doc/ISO/JBIG/jbigkit-0.9.tar.gz
- Contact: Markus Kuhn <mskuhn@cip.informatik.uni-erlangen.de>
-
- PNG: For code and sample images, see:
- http://quest.jpl.nasa.gov/PNG/
- ftp://ftp.uu.net/graphics/png/
- ftp://swrinde.nde.swri.edu/pub/png/
-
- mg: (the MG system for compressing and indexing text and images, see item 16)
- ftp://munnari.oz.au/pub/mg/*
- Contact: Stuart Inglis <singlis@cs.waikato.ac.nz>
-
- BTPC: Binary Tree Predictive Coding
- ftp://monet.uwaterloo.ca/pub/john/btpcv3.tar.Z
- Contact: John Robinson <john@monet.uwaterloo.ca>
-
- epic: (pyramid wavelet coder, see item 72)
- ftp://whitechapel.media.mit.edu/pub/epic.tar.Z
- Contact: Eero P. Simoncelli <eero@media.mit.edu>
- The "Lenna" test image is available as part of the EPIC package,
- where it is named "test_image".
-
- hcompress: (wavelet image compression, see item 72)
- ftp://stsci.edu/software/hcompress/hcompress.tar.Z
-
- wavethresh: (wavelet software for the language S)
- ftp://gdr.bath.ac.uk/pub/masgpn/wavethresh2.2.Z
- Contact: gpn@maths.bath.ac.uk
-
- rice-wlet: (wavelet software, see item 72)
- ftp://cml.rice.edu/pub/dsp/software/rice-wlet-tools.tar.Z
-
- scalable: (2 & 3 dimensional subband transformation)
- ftp://robotics.eecs.berkeley.edu/pub/multimedia/scalable2.tar.Z
- Contact: scalable@robotics.eecs.berkeley.edu
-
- compfits:
- ftp://uwila.cfht.hawaii.edu/pub/compfits/compfits.tar.Z
- Contact: Jim Wright <jwright@cfht.hawaii.edu>
-
- fitspress:
- ftp://cfata4.harvard.edu/pub/fitspress08.tar.Z
-
- tiff:
- For source and sample images, see question 18 below.
-
- DCT algorithms:
- ftp://etro.vub.ac.be/pub/DCT_ALGORITHMS/*
- Contact: Charilos Christopoulos <chchrist@etro2.vub.ac.be>
-
- xanim: (X11 animation viewer, supports Quicktime and several other formats)
- ftp://ftp.x.org/contrib/applications/xanim2683.tar.Z
- ftp://ftp.shell.portal.com/pub/podlipec/xanim26978.tar.gz
-
- ppm2pz: (lossless 24-bit image compression)
- http://www.jyu.fi/~kuru/compression.html
-
- A demo of image compression using neural networks is available in
- http://www.ee.duke.edu/~cec/index.html.
-
- For fractal compression programs, see item 17 below.
- For Vector Quantization software, see item 76 in part 2 of this FAQ.
- For image compression hardware, see item 85 in part 3 of this FAQ.
-
- ------------------------------------------------------------------------------
-
- Subject: [16] What is the state of the art in lossless image compression?
-
-
- The current state-of-the-art is the JBIG algorithm. For an
- introduction to JBIG, see question 74 in part 2.
-
- JBIG works best on bi-level images (like faxes) and also works well on
- Gray-coded grey scale images up to about six or so bits per pixel. You
- just apply JBIG to the bit planes individually. For more bits/pixel,
- lossless JPEG provides better performance, sometimes. (For JPEG, see
- question 19 below.)
-
- You can find the specification of JBIG in International Standard
- ISO/IEC 11544 or in ITU-T Recommendation T.82. You can order a copy
- directly from ISO (www.iso.ch) or ITU (www.itu.ch) or from your
- National Standards Body. In the USA, call ANSI at (212) 642-4900.
-
- See also the MG system containing an implementation of the 'FELICS'
- algorithm of P.G. Howard and J.S. Vitter. FELICS usually gives better
- and faster compression than lossless JPEG, at least for 8-bit
- grayscale images. (See item 15 above for ftp location). From the MG
- README file:
-
- The MG system is a suite of programs for compressing and
- indexing text and images. Most of the functionality implemented
- in the suite is as described in the book ``Managing Gigabytes:
- Compressing and Indexing Documents and Images'', I.H. Witten, A.
- Moffat, and T.C. Bell; Van Nostrand Reinhold, New York, 1994, ISBN
- 0-442-01863-0; US $54.95; call 1 (800) 544-0550 to order.
-
- These features include:
-
- -- text compression using a Huffman-coded semi-static word-based
- scheme
- -- two-level context-based compression of bi-level images
- -- FELICS lossless compression of gray-scale images
- -- combined lossy/lossless compression for textual images
- -- indexing algorithms for large volumes of text in limited main
- memory
- -- index compression
- -- a retrieval system that processes Boolean and ranked queries
- -- an X windows interface to the retrieval system
-
- Paul Howard's PhD thesis, which among other things describes FELICS,
- is available in ftp://ftp.cs.brown.edu/pub/techreports/93/cs93-28.ps.Z
-
- ------------------------------------------------------------------------------
-
- Subject: [17] What is the state of fractal compression?
-
- You may want to read first item 77 in part 2 of this FAQ:
- "Introduction to Fractal compression".
-
-
- from Tal Kubo <kubo@zariski.harvard.edu>:
-
- According to Barnsley's book 'Fractals Everywhere', this method is
- based on a measure of deviation between a given image and its
- approximation by an IFS code. The Collage Theorem states that there is
- a convergent process to minimize this deviation. Unfortunately,
- according to an article Barnsley wrote for BYTE a few years ago, this
- convergence was rather slow, about 100 hours on a Cray, unless assisted by
- a person.
-
- Barnsley et al are not divulging any technical information beyond the
- meager bit in 'Fractals Everywhere'. The book explains the idea of IFS
- codes at length, but is vague about the application of the Collage theorem
- to specific compression problems.
-
- There is reason to believe that Barnsley's company has
- *no algorithm* which takes a given reasonable image and achieves
- the compression ratios initially claimed for their fractal methods.
- The 1000-to-1 compression advertised was achieved only for a 'rigged'
- class of images, with human assistance. The best unaided
- performance I've heard of is good lossy compression of about 80-1.
-
- Steve Tate <srt@duke.cs.duke.edu> confirms:
-
- Compression ratios (unzoomed) seem to range from 20:1 to 60:1... The
- quality is considerably worse than wavelets or JPEG on most of the
- non-contrived images I have seen.
-
- But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees:
-
- Their performance has improved dramatically beyond what they were
- talking about in BYTE a few years ago. Human assistance to the
- compression is no longer needed and the compression time is
- reasonable, although the more time and compute power you throw at the
- compression, the smaller the resulting file for the same level of
- quality.
-
- Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds:
-
- Iterated systems are shipping a general purpose compressor at about
- 300 Pounds in the UK that claims "640x480 24 bit colour compression of
- about 1 min at 922k -> 10k on a 486/50 software only, decomp. to 8
- bits in 3 secs, etc." At a recent multimedia conference in London they
- handed out free demo disks that show the decomp. in action. The
- package runs under both DOS anf WIN (DLLs provided for use in
- applications). They also sell a board to speed up compression and
- offer versions supporting full motion video (but not apparently at all
- SVGA sizes like the static picture version). I have not yet got my
- hands on a full version to test different types of pictures, but
- friends have a and claim it looks good.
-
-
- Thomas W. Colthurst <thomasc@athena.mit.edu> clarifies the distinction
- between IFS and the Fractal Transform:
-
- It is time, once and for all, to put to death the Barnsley myth that
- IFSs are good for image compression. They are not. Various algorithms
- have been proposed for this "inverse problem" ranging from the trendy
- (genetic algorithms) to the deep (moment methods) to the ad hoc (the
- hungry algorithm) to the absurd (the so-called "graduate student
- algorithm", consisting of locking up a grad student in a tiny office
- with a SGI workstation and not letting them out until they come up
- with a good IFS for your image). They are all useless for practical
- image compression.
-
- In fact, there are even good theoretical reasons for believing that
- IFSs will never be useful for image compression. For example, even
- if you have an IFS for object A and an IFS for object B, there is no
- way to combine these IFSs to get an IFS for object A union B or
- object A intersect B.
-
- Even Barnsley himself admits, in his latest book, that he doesn't use
- IFS image compression. Instead, he uses the so-called "fractal
- transform," which is really just a variant of vector quantization
- where you use the image itself, sampled at a higher scale, as the
- VQ codebook. To be fair, the fractal transform can be analyzed using
- local IFSs, but local IFSs are immensely more complicated and general
- than normal IFSs, to the point where one feels suspect even using the
- word "IFS" to describe them.
-
- It should be emphasized that the fractal transform is a real, working
- method that performs about as well as other existing methods like VQ
- or the discrete cosine transform. The fractal transform will probably
- never beat vector quantization (VQ) as for size of the compressed
- image, but does have the advantage that you don't need to carry your
- codebook around. The latest results have it slightly winning over
- the discrete cosine transform; only time and more research will tell
- if this advantage persists. Just like VQ, the fractal transform
- takes a while to compress, but is quick at decompression (Barnsley's
- company has hardware to do this in realtime).
-
- In short, IFSs are good for just about everything fractals are (and
- more!), but are absolutely horrid for image compression.
-
-
- Programs:
-
- Check http://links.uwaterloo.ca/ for pointers to some fractal compression
- programs and lots of papers on fractal compression.
-
- The Waterloo BragZone (http://links.uwaterloo.ca/bragzone.base.html
- or ftp://links.uwaterloo.ca/pub/BragZone/ ) compares the results of
- various image compression schemes against a 32 element test suite.
- Numerous rate-distortion graphs, data tables, and sample images are available.
-
- A fractal image compression program is available by ftp in
- ftp://inls.ucsd.edu/pub/young-fractal/yuvpak20.zip ; it contains source for
- compression and decompression, source for X-windows decompression,
- MSDOS executables and images. [Note from FAQ maintainer: Fisher's
- program (see below) implements the same algorithm but is more general;
- see http://inls.ucsd.edu/y/Fractals/ for the source code.]
-
- A fractal image decompression program (note: decompression only) is
- available in ftp://inls.ucsd.edu/pub/inls-ucsd/fractal-2.0.tar
- In the same directory, fractal_paper.ps.Z is the paper "Fractal image
- compression" by Yuval Fisher, Siggraph 92. Reading this paper is
- required to understand how the Young compression programs (see above) works.
-
- A note from Yuval Fisher <yfisher@ucsd.edu>:
-
- Connect to http://inls.ucsd.edu/y/Fractals/ . There is
- information there on my new book of contributed articles on
- fractal image compression, as well as the book's table of
- contents, some C code to encode and decode raw byte files of any
- size using a quadtree method, a manual explaining the use of the
- code, a fractal image compression bibliography (not guaranteed to
- be complete or close to it), some better executable code with
- sample encodings, and the SIGGRAPH '92 course notes on fractal
- image compression (these are based on appendix A of Chaos and
- Fractals by Peitgen et al., Springer Verlag). [The C code is also
- available in ftp://inls.ucsd.edu/pub/inls-ucsd/frac_comp.tar.Z ]
-
- Another fractal compression program is available by ftp in
- ftp://vision.auc.dk/pub/Limbo/Limbo*.tar.Z. It is also based on quadtrees,
- as yuvpak20 and frac_comp.
-
- The source code for the program published in the Oct 93 issue of
- Byte is in ftp://ftp.uu.net/published/byte/93oct/fractal.exe. This is
- a self-extractible arc file (must be run on MSDOS for extraction).
- The source code is for a TARGA video board. [Note from FAQ maintainer:
- this code is taken from Barnsley's book "Fractal Image Compression";
- it implements the brute force method and is thus very slow.]
-
- Iterated Systems have released a beta version of their fractal imager.
- It will let you view a number of formats including JPG and do
- conversions to their fractal format. The program can be downloaded
- from http://www.iterated.com
-
- "The Data Compression Book" (see [NEL 1996] in item 7 above) contains
- a chapter on fractal compression; it includes source code for a simple
- fractal compression program.
-
- Several papers on fractal image compression are available on
- ftp.informatik.uni-freiburg.de in directory /documents/papers/fractal . A
- biliography is in ftp://schmance.uwaterloo.ca/pub/Fractal/fractal.biblio.ps.Z
-
- References:
- A. Jacquin, 'Fractal image coding based on a theory of iterated
- contractive image transformations', Proc. SPIE Visual Communications
- and Image Processing, 1990, pages 227-239. (The best paper that explains
- the concept in a simple way.)
-
- A. Jacquin, "A Fractal Theory of Iterated Markov Operators with
- Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989.
- It can be obtained from university microfilms for $35, phone 1-800-521-0600.
-
- M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
- October 1991, pp. 42-52.
- M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
- 'Harnessing chaos for image synthesis', Computer Graphics,
- vol 22 no 4 pp 131-140, 1988.
- M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
- function systems to images', Visual Comm. and Image Processing,
- vol SPIE-1001, 1988.
- A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive
- Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans
- on Image Processing.
- A.E. Jacquin, 'A novel fractal block-coding technique for digital
- images', Proc. ICASSP 1990.
- G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space
- approach to image coding by contractive transformations',
- Proc. ICASSP 1991, pp 2773-2776.
- D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
- Georgia Tech, 1991. (One dimensional, not pictures)
- S. A. Hollatz, "Digital image compression with two-dimensional affine
- fractal interpolation functions", Department of Mathematics and
- Statistics, University of Minnesota-Duluth, Technical Report 91-2.
- (a nuts-and-bolts how-to-do-it paper on the technique)
- Stark, J., "Iterated function systems as neural networks",
- Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
- Monro D M and Dudbridge F, "Fractal block coding of images",
- Electronics Letters 28(11):1053-1054 (1992)
- Beaumont J M, "Image data compression using fractal techniques",
- British Telecom Technological Journal 9(4):93-108 (1991)
- Fisher Y, "Fractal image compression", Siggraph 92
- Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
- Journal Of Complexity, V8, 72-78 (1992).
- Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 169-72
- Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks',
- Proc ICASSP 92, pp. III: 485-488
- Monro D.M., Wilson D., Nicholls J.A. 'High speed image coding with the Bath
- Fractal Transform', IEEE International Symposium on Multimedia Technologies
- Southampton, April 1993
- Jacobs, E.W., Y. Fisher and R.D. Boss. "Image Compression: A study
- of the Iterated Transform Method." _Signal Processing 29_ (1992) 25-263
- Vrscay, Edward R. "Iterated Function Systems: Theory, Applications,
- and the Inverse Problem." _Fractal Geometry and Analysis_,
- J. Belair and S. Dubuc (eds.) Kluwer Academic, 1991. 405-468.
-
- Books:
- Fractal Image Compression: Theory and Application, Yuval Fisher (ed.),
- Springer Verlag, New York, 1995.
- To order the book, call 1-800-SPRINGER and ask for the book with
- ISBN number 0-387-94211-4 or check http://www.springer-ny.com/
-
- Fractal Image Compression
- Michael F. Barnsley and Lyman P. Hurd
- ISBN 0-86720-457-5, ca. 250 pp., $49.95
- Copies can be ordered directly from the publisher by sending a message
- to kpeters@math.harvard.edu with name, address and a Mastercard or
- Visa card number with expiration date.
-
- Barnsley's company is:
-
- Iterated Systems, Inc.
- 5550A Peachtree Parkway, Suite 650
- Norcross, GA 30092
- tel: 404-840-0310 or 1-800-4FRACTL
- fax: 404-840-0806
- In UK: Phone (0734) 880261, Fax (0734) 880360
-
- ------------------------------------------------------------------------------
-
- Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax
-
-
- Specs for Group 3 and 4 image coding (group 3 is very similar to group 4)
- are in CCITT (1988) volume VII fascicle VII.3. They are recommendations
- T.4 and T.6 respectively. There is also an updated spec contained in 1992
- recommendations T.1 to T.6.
-
- CCITT (now ITU-T) specs are available by anonymous ftp (see above answer on
- V.42bis). The T.4 and T.6 specs are on src.doc.ic.ac.uk in directory
- /computing/ccitt/ccitt-standards/ccitt/1988/ascii, files 7_3_01.txt.Z and
- 7_3_02.txt.Z respectively.
-
- The following paper covers T.4, T.6 and JBIG:
-
- "Review of standards for electronic imaging for facsimile systems"
- in Journal of Electronic Imaging, Vol. 1, No. 1, pp. 5-21, January 1992.
-
-
- Source code can be obtained as part of a TIFF toolkit - TIFF image
- compression techniques for binary images include CCITT T.4 and T.6:
-
- ftp://ftp.sgi.com/graphics/tiff/tiff-v3.4beta035-tar.gz
- Contact: sam@engr.sgi.com
-
- There is also a companion compressed tar file (v3.0pics.tar.Z) that
- has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z.
- Concerning JPEG compression in TIFF 6.0, Tom Lane <tgl@sss.pgh.pa.us> adds:
-
- TIFF 6.0's scheme for incorporating JPEG compression (spec section 22) has
- a bunch of serious deficiencies. Don't use it. A revised design is given
- by TIFF Technical Note #2, ftp://ftp.sgi.com/graphics/tiff/TTN2.draft.txt
- The revised design will replace section 22 in TIFF 7.0, and is implemented
- in Sam Leffler's libtiff. See also item 75 of this FAQ for more JPEG info.
-
- Software for reading and writing CCITT Group 3 and 4 images is
- also available in directory ftp://merry.cs.monash.edu.au/pub/alanf/TIFF_FAX
- Contact: Alan Finlay <alanf@bruce.cs.monash.edu.au>.
-
-
- See also question 54 below.
-
- ------------------------------------------------------------------------------
-
- Subject: [19] What is JPEG?
-
-
- JPEG (pronounced "jay-peg") is a standardized image compression mechanism.
- JPEG stands for Joint Photographic Experts Group, the original name of the
- committee that wrote the standard. JPEG is designed for compressing either
- full-color or gray-scale digital images of "natural", real-world scenes.
- It does not work very well on non-realistic images, such as cartoons or
- line drawings.
-
- JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it
- handle motion picture compression. Related standards for compressing those
- types of images exist, and are called JBIG and MPEG respectively.
-
- Regular JPEG is "lossy", meaning that the image you get out of decompression
- isn't quite identical to what you originally put in. The algorithm achieves
- much of its compression by exploiting known limitations of the human eye,
- notably the fact that small color details aren't perceived as well as small
- details of light-and-dark. Thus, JPEG is intended for compressing images that
- will be looked at by humans. If you plan to machine-analyze your images, the
- small errors introduced by JPEG may be a problem for you, even if they are
- invisible to the eye. The JPEG standard includes a separate lossless mode,
- but it is rarely used and does not give nearly as much compression as the
- lossy mode.
-
- Question 75 "Introduction to JPEG" (in part 2 of this FAQ) gives an overview
- of how JPEG works and provides references for further reading. Also see the
- JPEG FAQ article, which covers JPEG software and usage hints. The JPEG FAQ is
- posted regularly in news.answers by Tom Lane <tgl@netcom.com>. (See question
- 53 "Where are FAQ lists archived" if this posting has expired at your site.)
-
- For JPEG software, see item 15 above.
- For JPEG hardware, see item 85 in part 3 of this FAQ.
-
- ------------------------------------------------------------------------------
-
- Subject: [20] I am looking for source of an H.261/H.263 codec and MPEG
-
- Many standards and draft recommendations (including H.261, H.263,
- H.320, H.324), are available in http://www.imtc.org/imtc/
-
- The H.261 spec is also available on src.doc.ic.ac.uk in
- /computing/ccitt/standards/ccitt-standards/1992/h/h261.doc.Z (or h261.rtf.Z).
-
- For H.261 hardware, see item 85 in part 3 of this FAQ.
-
- Current drafts of H.324 and related recommendations including H.263 are
- available in ftp://ftp.std.com/vendors/PictureTel/h324
-
- Telenor Research have made available a complete simulation of
- H.263. See http://www.nta.no/brukere/DVC/h263_software
-
- from Thierry TURLETTI <turletti@sophia.inria.fr>:
-
- IVS (INRIA VIDEOCONFERENCING SYSTEM)
- - X11-based videoconferencing tool for SPARC, HP, DEC and
- Silicon Graphic workstations.
-
- ivs allows users to conduct multi-host audio and video
- conferences over the Internet. ivs requires a workstation
- with a screen with 1, 4, 8 or 24 bits depth. Multi-host
- conferences require that the kernel support multicast IP
- extensions (RFC 1112).
-
- On video input, video frames are grabbed by the VideoPix,
- SunVideo or Parallax boards for SparcStations or Raster Rops
- board for HP stations or the IndigoVideo board for SGI IRIS
- Indigo workstations. or the VIDEOTX board for DEC stations.
- No special hardware apart from the workstation's build-in
- audio hardware is required for audio conference.
-
- Video encoding is done according to the H.261 standard.
- The video stream can be encoded in either Super CIF
- (704x576 pixels) format or CIF (352x288 pixels) format or
- QCIF (176x144 pixels). Default format is CIF.
-
- Sources, binaries & manuals are freely available by anonymous
- ftp from zenon.inria.fr in the rodeo/ivs directory. An INRIA
- report describing this application is also available in the
- same directory.
-
- If you ftp & use this package, please send all remarks or
- modifications made to <turletti@sophia.inria.fr>. If you want
- to be added or deleted to the ivs-users mailing list, please send
- e-mail to ivs-users-request@sophia.inria.fr.
-
-
- from Andy Hung <achung@cs.stanford.edu>:
-
- Public domain UNIX C source code to do both image and image sequence
- compression and decompression is available by anonymous ftp:
-
- MPEG-I ftp://havefun.stanford.edu/pub/mpeg/MPEGv*.tar.Z
- CCITT H.261(P*64) ftp://havefun.stanford.edu/pub/p64/P64v*.tar.Z
- JPEG ftp://havefun.stanford.edu/pub/jpeg/JPEGv*.tar.Z
-
- These codecs operate on raw raster scanned images.
-
- A software program to display raw raster-scanned YUV images and image
- sequences on X grayscale or color monitors is provided by a program in
- ftp://havefun.stanford.edu/pub/cv/CVv*.tar.Z
- If you are using the codecs above, we recommend that you ftp this file
- over as well.
-
- The source code has been compiled on DEC and SUN workstations.
- Caution: the P64 codec has not been tested compliant (any available
- p64 video streams would be much appreciated - please let us know at
- achung@cs.stanford.edu). The other codecs have been tested with
- streams from other encoders.
-
- We also have some IPB MPEG-I video coded streams in pub/mpeg/*.mpg;
- and P64 video streams in pub/p64/*.p64 that we have generated using
- our codecs.
-
- For a more complete description see the file
- havefun.stanford.edu:pub/README.
-
- ------------------------------------------------------------------------------
-
- Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms
-
-
- Many image compression methods, including the JPEG, MPEG, and H.261 standards,
- are based on the discrete cosine transform. A good overall introduction to
- DCT is the book "Discrete Cosine Transform---Algorithms, Advantages,
- Applications" by K.R. Rao and P. Yip (Academic Press, London, 1990),
- ISBN 0-12-580203-X. This has an extensive, though already dated, bibliography.
-
- Here are some references mostly provided by Tom Lane <tgl@sss.pgh.pa.us>.
- (This list is now rather dated.)
- Most of these are in IEEE journals or conference proceedings, notably
- ICASSP = IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing.
- ICCAS = IEEE Intl. Conf. on Circuits and Systems.
- DCC = Data Compression Conference.
-
- Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
- ICASSP '90 p. 1515.
- A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
- DCC '92 p. 219.
- A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
- Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
- A DCT Chip based on a new Structured and Computationally Efficient DCT
- Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
- Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
- Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
- Practical Fast 1-D DCT Algorithms with 11 Multiplications,
- Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
- New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
- Linzer & Feig, ICASSP '91 p. 2201.
- Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
- IEEE Tr. Computers, v C-31 p. 899.
- Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
- A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
- Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
- Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.
- J.F. Blinn, "What's the Deal with the DCT", IEEE Computer Graphics and
- Applications, July 1993, pp.78-83.
- A C Hung and TH-Y Meng, "A Comparison of fast DCT algorithms, Multimedia
- Systems, No. 5 Vol. 2, Dec 1994
-
- For actual implementations, try the JPEG and MPEG software listed
- in item 15.
-
- ------------------------------------------------------------------------------
-
- Subject: [26] Are there algorithms and standards for audio compression?
-
-
- Yes. See the introduction to MPEG given in part 2 of this FAQ.
-
- A lossless compressor for 8bit and 16bit audio data (.au) is available
- in ftp://svr-ftp.eng.cam.ac.uk/pub/comp.speech/coding/shorten.tar.gz
- Shorten works by using Huffman coding of prediction residuals.
- Compression is generally better than that obtained by applying general
- purpose compression utilities to audio files. Also supports lossy
- compression. Contact: Tony Robinson <ajr@eng.cam.ac.uk>.
-
- Audio software is available on sunsite.unc.edu in subdirectories of
- /pub/electronic-publications/IUMA/audio_utils:
- - An MPEG audio player is in mpeg_players/Workstations/maplay1_2.tar.Z.
- - The sources of the XING MPEG audio player for Windows is in
- mpeg_players/Windows/mpgaudio.zip.
- - An encoder/decoder is in converters/source/mpegaudio.tar.Z.
-
- MSDOS audio software is available in
- ftp://ftp.coast.net/mirrors/SimTel/msdos/sound/
- In particular, MPEG-2 audio software is in ampegsrc.zip and ampeg43.zip.
-
- MPEG audio files are available in ftp.iuma.com and http://www.iuma.com/
-
- Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum):
-
- Strange though it seems, audio data is remarkably hard to compress
- effectively. For 8-bit data, a Huffman encoding of the deltas between
- successive samples is relatively successful. For 16-bit data,
- companies like Sony and Philips have spent millions to develop
- proprietary schemes.
-
- Public standards for voice compression are slowly gaining popularity,
- e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec). (ADPCM ==
- Adaptive Delta Pulse Code Modulation.) Free source code for a *fast*
- 32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl
- as /pub/audio/adpcm.shar. (** NOTE: if you are using v1.0, you should get
- v1.1, released 17-Dec-1992, which fixes a serious bug -- the quality
- of v1.1 is claimed to be better than uLAW **)
-
- (Note that U-LAW and silence detection can also be considered
- compression schemes.)
-
- Information and source code for adpcm are available in
- http://www.nb.rockwell.com/ref/adpcm.html
-
- Source for Sun's free implementation of CCITT compression types G.711,
- G.721 and G.723 is in ftp://ftp.cwi.nl/pub/audio/ccitt-adpcm.tar.gz
-
- You can get a G.721/722/723 package by email to teledoc@itu.arcom.ch, with
- GET ITU-3022
- as the *only* line in the body of the message.
-
-
- A note on u-law from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
-
- u-law (more precisely (greek mu)-law or 5-law if you have an 8-bit
- ISO terminal) is more an encoding then a compression method,
- although a 12 to 8 bit reduction is normally part of the encoding.
- The official definition is CCITT recommendation G.711. If you want
- to know how to get CCITT documents, check the Standards FAQ
- posted to news.answers or get the file standards-faq by ftp in
- directory ftp://rtfm.mit.edu/pub/usenet/news.answers/
-
-
- See also the comp.dsp FAQ for more information on:
-
- - The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear
- prediction voice coder version 3.2a (CELP 3.2a)
- - The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps
- linear prediction coder version 53 (LPC-10e v53)
- - Realtime DSP code and hardware for FS-1015 and FS-1016
-
- The comp.dsp FAQ is in comp.dsp with subject "FAQ: Audio File Formats" and in
- ftp://rtfm.mit.edu/pub/usenet/news.answers/audio-fmts/part1
-
-
- CELP C code for Sun SPARCs is in ftp://ftp.super.org/pub/speech/celp_3.2a.tar.Z
- An LPC10 speech coder is in ftp://ftp.super.org/pub/speech/lpc10-1.0.tar.gz ;
- a derived version is in http://www.arl.wustl.edu/~jaf/lpc/lpc10-1.1.tar.gz
-
- Source code for ITU-T (CCITT) G.728 Low Delay CELP speech compression
- is in ftp://svr-ftp.eng.cam.ac.uk/pub/comp.speech/sources/ldcelp-2.0.tar.gz
-
-
- Recommended reading:
- Digital Coding of Waveforms: Principles and Applications to Speech and
- Video. N. S. Jayant and Peter Noll. Prentice-Hall, 1984, ISBN
- 0-13-211913-7.
-
- Information on GSM sound compression is available at
- http://ccnga.uwaterloo.ca/~jscouria/gsm.html
-
-
- from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
-
- One highest quality sound compression format is called ASPEC and has
- been developed by a team at the Frauenhofer Institut in Erlangen (Germany)
- and others.
-
- ASPEC produces CD like quality and offers several bitrates, one is
- 128 kbit/s. It is a lossy algorithm that throws away frequencies that
- aren't registered in the human cochlea in addition to sophisticated
- entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi
- quality ISDN phone connections. It has been implemented on standard DSPs.
-
- The Layer 3 MPEG audio compression standard now contains what is officially
- called the best parts of the ASPEC and MUSICAM algorithms. A reference is:
-
- K.Brandenburg, G.Stoll, Y.F.Dehery, J.D.Johnston, L.v.d.Kerkhof,
- E.F.Schroeder: "The ISO/MPEG-Audio Codec: A Generic Standard for Coding
- of High Quality Digital Audio",
- 92nd. AES-convention, Vienna 1992, preprint 3336
-
-
- from Jutta Degener <jutta@cs.tu-berlin.de> and Carsten Bormann
- <cabo@cs.tu-berlin.de>:
-
- GSM 06.10 13 kbit/s RPE/LTP speech compression available
- --------------------------------------------------------
-
- The Communications and Operating Systems Research Group (KBS) at the
- Technische Universitaet Berlin is currently working on a set of
- UNIX-based tools for computer-mediated telecooperation that will be
- made freely available.
-
- As part of this effort we are publishing an implementation of the
- European GSM 06.10 provisional standard for full-rate speech
- transcoding, prI-ETS 300 036, which uses RPE/LTP (residual pulse
- excitation/long term prediction) coding at 13 kbit/s.
-
- GSM 06.10 compresses frames of 160 13-bit samples (8 kHz sampling
- rate, i.e. a frame rate of 50 Hz) into 260 bits; for compatibility
- with typical UNIX applications, our implementation turns frames of 160
- 16-bit linear samples into 33-byte frames (1650 Bytes/s).
- The quality of the algorithm is good enough for reliable speaker
- recognition; even music often survives transcoding in recognizable
- form (given the bandwidth limitations of 8 kHz sampling rate).
-
- Version 1.0 of the implementation is available per anonymous ftp from
- ftp.cs.tu-berlin.de in the directory /pub/local/kbs/tubmik/gsm/ ;
- more information about the library can be found on the World-Wide Web
- at http://www.cs.tu-berlin.de/~jutta/toast.html .
- Questions and bug reports should be directed to jutta@cs.tu-berlin.de
- and cabo@informatik.uni-bremen.de .
-
-
- from Bob Kimball <rkimball@qualcomm.com>:
-
- I work for Qualcomm Inc. and we are designing a digital cellular telephone
- system. Our phone uses our variable rate vocoder (QCELP) which is designed
- for speach and compresses 64Kb/s speach to 8Kb/s through 1Kb/s with 8Kb/s
- being full rate and 1Kb/s for 1/8 rate speach. It works great for speach.
-
- The QCELP process is documented in our Common Air Interface (CAI) which is
- available for anonymous ftp from lorien.qualcomm.com in /pub/cdma
- each chapter is a postscript file. The vocoder is described in appendix A.
- The whole document is quite large. This is the document which is currently
- going through the TIA standard committee so it is not a final version. The
- appendix on the vocoder should be almost identical to the final version...
- whenever that comes out.
-
-
- from Nicola Ferioli <ser1509@cdc835.cdc.polimi.it>:
-
- ftp://ftp.coast.net/mirrors/SimTel/msdos/sound/vocpak20.zip
- Lossless 8-bit sound file compressor
-
- VOCPACK is a compressor/decompressor for 8-bit digital sound using a
- lossless algorithm; it is useful to save disk space without degrading
- sound quality. It can compress signed and unsigned data, sampled at any
- rate, mono or stereo. Since the method used is not lossy, it isn't
- necessary to strip file headers before compressing.
-
- VOCPACK was developed for use with .VOC (SoundBlaster) and .WAV (Windows)
- files, but any 8-bit sound can be compressed since the program takes no
- assumptions about the file structure.
-
- The typical compression ratio obtained goes from 0,8 for files sampled at
- 11 KHz to 0,4 for 44 Khz files. The best results are obtained with 44 KHz
- sounds (mono or stereo): general-purpose archivers create files that can be
- twice longer than the output of VOCPACK. You can obtain smaller values
- using lossy compressors but if your goal is to keep the sound quality
- unaltered you should use a lossless program like VOCPACK.
-
- from Harald Popp <popp@iis.fhg.de>:
-
- new version 1.0 of ISO/MPEG1 Audio Layer 3 Shareware available
-
- major improvements of the new version:
- - encoder works twice as fast
- - improved file handling for encoder including .WAV files
-
- You may download the shareware from fhginfo.fhg.de (153.96.1.4)
- from the directory /pub/layer3
-
- The source code for the MPEG1 audio decoder layer 1, 2 and 3 is
- now available on fhginfo.fhg.de (153.96.1.4) in /pub/layer3/public_c.
-
- There are two files:
- mpeg1_iis.tar.Z (Unix: lines seperated by line feed only)
- mpeg1iis.zip (PC: lines seperated by carriage return and line feed)
-
- For more information about this product and MPEG Audio Layer 3, see
- the document "Informations about MPEG Audio Layer-3" maintained by
- Juergen Zeller <zeller@iis.fhg.de>, available in
- ftp://fhginfo.fhg.de/pub/layer3/MPEG_Audio_L3_FAQ.html
-
- from Monty <xiphmont@athena.mit.edu>:
-
- A beta release of the OggSquish audio compression/decompression utility is
- available at http://deskfish.cs.titech.ac.jp:8001/squish/squish_index.html
-
- OggSquish is a compression package designed to reduce the file size of
- digitized 8 and 16 bit audio samples (or samples of any periodic
- data). OggSquish will operate on files sampled at any speed, but it is
- designed to work with very high quality samples, for example, CD
- quality samples.
-
- ------------------------------------------------------------------------------
-
- Subject: [30] My archive is corrupted!
-
-
- The two most common reasons for this are
-
- (1) failing to use the magic word "tenex" (when connected to SIMTEL20 and
- other TOPS20 systems) or "binary" (when connected to UNIX systems) when
- transferring the file from an ftp site to your host machine. The
- reasons for this are technical and boring. A synonym for "tenex" is
- "type L 8", in case your ftp doesn't know what "tenex" means.
-
- (2) failing to use an eight-bit binary transfer protocol when transferring
- the file from the host to your PC. Make sure to set the transfer type
- to "binary" on both your host machine and your PC.
-
- gopher is also known to corrupt binary files. In particular, if gzip
- complains about a multi-part file, it's likely that the .gz file
- has been corrupted by gopher. Use ftp in binary mode instead.
-
- ------------------------------------------------------------------------------
-
- Subject: [31] pkunzip reports a CRC error!
-
-
- The portable zip 1.1 contains many workarounds for undocumented restrictions
- in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous
- versions (pkunzip 1.0x) have too many bugs and cannot be supported. This
- includes Borland unzip.
-
- So if your pkunzip reports a CRC error, check that you are not using
- an obsolete version. Get either pkzip 2.04g or unzip 5.12 (see question
- 2 above for ftp sites). To generate zip files compatible with pkunzip 1.10,
- use zip 1.1 (see item 2 above for ftp site).
-
- ------------------------------------------------------------------------------
-
- Subject: [32] VMS zip is not compatible with pkzip!
-
-
- The problem is most likely in the file transfer program.
-
- Many use kermit to transfer zipped files between PC and VMS VAX. The
- following VMS kermit settings make VMS-ZIP compatible with PKZIP:
-
- VMS kermit PC kermit
- --------------- --------------
-
- Uploading PKZIPped file to be UNZIPped: set fi ty fixed set fi ty bi
- Downloading ZIPped file to be PKUNZIPped: set fi ty block set fi ty bi
-
- If you are not using kermit, transfer a file created by pkzip on MSDOS
- to VMS, transfer it back to your PC and check that pkunzip can extract it.
-
- ------------------------------------------------------------------------------
-
- Subject: [33] I have a problem with Stacker or DoubleSpace!
-
-
- The newsgroup comp.compression is *not* the appropriate place to
- discuss about one specific program on one specific operating system.
- Since you have bought a legal copy of Stacker or MSDOS 6.x, you have
- the documentation of your product; please read it. If you can't find
- the answer in the documentation, please report the problem to the Stac
- or Microsoft customer support. (For Stac, use one of StacTec@aol.com,
- StacMacTec@aol.com or StacOS2tec@aol.com.) If you really feel that the
- net has to know about your problem, please post in one of the MSDOS
- newsgroups, such as comp.os.msdos.apps or comp.binaries.ibm.pc.d.
-
- ------------------------------------------------------------------------------
-
- Subject: [50] What is this 'tar' compression program?
-
-
- tar is not a compression program. It just combines several files
- into one, without compressing them. tar file are often compressed with
- 'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z.
- GNU tar has the capability to (de)compress files as well.
-
- When you have to archive a lot of very small files, it is often
- preferable to create a single .tar file and compress it, than to
- compress the individual files separately. The compression program can
- thus take advantage of redundancy between separate files. The
- disadvantage is that you must uncompress the whole .tar file to
- extract any member. You can also improve compression by grouping
- files by type, as in:
-
- tar cvf - `ls | sort -t. +1` | gzip > file.tar.gz
-
- ------------------------------------------------------------------------------
-
- Subject: [51] I need a CRC algorithm
-
-
- As its name implies (Cyclic Redundancy Check) a crc adds redundancy whereas
- the topic of this group is to remove it. Yet this question comes up often in
- comp.compression.
-
- The file ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt is a pretty
- comprehensive description of the whole CRC concept, including a C program.
-
- See also:
- - Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.
- - "Calculating CRCs by Bits and Bytes", BYTE Magazine, September 1986
- - Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE
- Micro, Aug 1988.
- - ftp://ftp.uni-erlangen.de/pub/doc/ISO/english/async-HDLC
- - the source of all archivers, such as the file makecrc.c in the sources of
- zip 2.0.1 (see item 2).
-
-
- The following C code (by Rob Warnock <rpw3@sgi.com>) does CRC-32 in
- BigEndian/BigEndian byte/bit order. That is, the data is sent most
- significant byte first, and each of the bits within a byte is sent most
- significant bit first, as in FDDI. You will need to twiddle with it to do
- Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit order. [Left as an
- exercise for the reader.]
-
- The CRCs this code generates agree with the vendor-supplied Verilog models
- of several of the popular FDDI "MAC" chips.
-
- u_long crc32_table[256];
- /* Initialized first time "crc32()" is called. If you prefer, you can
- * statically initialize it at compile time. [Another exercise.]
- */
-
- u_long crc32(u_char *buf, int len)
- {
- u_char *p;
- u_long crc;
-
- if (!crc32_table[1]) /* if not already done, */
- init_crc32(); /* build table */
- crc = 0xffffffff; /* preload shift register, per CRC-32 spec */
- for (p = buf; len > 0; ++p, --len)
- crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
- return ~crc; /* transmit complement, per CRC-32 spec */
- }
-
- /*
- * Build auxiliary table for parallel byte-at-a-time CRC-32.
- */
- #define CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */
-
- init_crc32()
- {
- int i, j;
- u_long c;
-
- for (i = 0; i < 256; ++i) {
- for (c = i << 24, j = 8; j > 0; --j)
- c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
- crc32_table[i] = c;
- }
- }
-
- ------------------------------------------------------------------------------
-
- Subject: [52] What about those people who continue to ask frequently asked
- questions in spite of the frequently asked questions document?
-
-
- Just send them a polite mail message, referring them to this document.
- There is no need to flame them on comp.compression. That would just
- add more noise to this group. Posted answers that are in the FAQ are
- just as annoying as posted questions that are in the FAQ.
-
- ------------------------------------------------------------------------------
-
- Subject: [53] Where are FAQ lists archived?
-
-
- Many are crossposted to news.answers. That newsgroup should have a
- long expiry time at your site; if not, talk to your sysadmin.
-
- FAQ lists are available by anonymous FTP from rtfm.mit.edu.
- The comp.compression FAQ that you are reading is in directory
- /pub/usenet/news.answers/compression-faq
-
- This FAQ is also accessible in the World Wide Web at
- http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
- All FAQs are available on this site.
-
- If you don't have FTP access, you can access the archives by mail
- server. Send an email message to mail-server@rtfm.mit.edu
- containing the commands
- send usenet/news.answers/compression-faq/part1
- send usenet/news.answers/compression-faq/part2
- send usenet/news.answers/compression-faq/part3
- For instructions, send an email message to the same address with the
- words "help" and "index" (no quotes) on separate lines. If you don't
- get a reply, check your return address, or add a line such as
- path myname@foo.edu
-
- ------------------------------------------------------------------------------
-
- Subject: [54] I need specs for graphics formats
-
- Get the book by Murray & vanRyper "Encyclopedia of graphics file formats",
- O'Reilly & associates, ISBN 1-56592-058-9. Or have a look in directory
- /pub/graphics.formats on zamenhof.cs.rice.edu; it contains descriptions of
- gif, tiff, fits, etc...
-
- See also the comp.graphics FAQ and the Graphics Formats FAQ. The latter is in
- ftp://rtfm.mit.edu/pub/usenet/news.answers/graphics/fileformats-faq/
- http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/fileformats-faq/top.html
-
- ------------------------------------------------------------------------------
-
- Subject: [55] Where can I find Lenna and other images?
-
- The Waterloo BragZone (http://links.uwaterloo.ca/bragzone.base.html
- or ftp://links.uwaterloo.ca:/pub/BragZone/ ) compares the results of
- various image compression schemes against a 32 element test suite.
- Sample images are available.
-
- The Computer Vision Home Page has many links to test images in
- http://www.cs.cmu.edu:80/afs/cs/project/cil/ftp/html/v-images.html
-
- A bunch of standard images (lenna, baboon, cameraman, crowd, moon
- etc..) used to be in ftp://eedsp.gatech.edu/database/images . The
- images are in 256-level grayshades (256x256 pixels, 256 "colors").
-
- [Note: the site ipl.rpi.edu mentioned below keeps changing. Images
- stay there for a while then disappear. They are again available at
- the time of writing (27 Dec 93).]
-
- The site ipl.rpi.edu (128.113.14.50) has standard images in two
- directories:
- ftp://ipl.rpi.edu/pub/image/still/usc
- ftp://ipl.rpi.edu/pub/image/still/canon
-
- (The directory /pub/image/sequence was taken offline because of
- possible copyright problems, but has come back again. In particular,
- Miss America is in subdirectories of /pub/image/sequence/missa.)
-
- In each of those directories are (usually) the following directories:
- bgr - 24 bit blue, green, red
- color - 24 bit red, green, blue
- gray - 8 bit grayscale uniform weighted
- gray601 - 8 bit grayscale CCIR-601 weighted
-
- And in these directories are the actual images.
-
- For example, the popular lena image is in
- ftp://ipl.rpi.edu/pub/image/still/usc/bgr/lena # 24 bit BGR
- ftp://ipl.rpi.edu/pub/image/still/usc/gray/lena-y.ras # 8 bit gray
-
- All of the images are in Sun rasterfile format. You can use the pbm
- utilities to convert them to whatever format is most convenient.
- [pbm is available in ftp://ftp.ee.lbl.gov/pbmplus*.tar.Z ].
- Questions about the ipl archive should be sent to help@ipl.rpi.edu.
-
-
- There are few gray-scale still images and some raw data of test results
- available in directory ftp://nic.funet.fi/pub/graphics/misc/test-images/
- There are lots of .gif images in ftp://nic.funet.fi/pub/pics/
-
- Medical images can be found in:
- ftp://decaf.stanford.edu/pub/images/medical/mri
- ftp://eedsp.gatech.edu/database/images/wchung/medical
- ftp://omicron.cs.unc.edu/pub/projects/softlab/CHVRTD
-
- The WWW address for the National Library of Medicine is http://www.nlm.nih.gov
- A list of health and medical related Internet resources is available ftp://in
- ftp.sura.net/pub/nic/HealthResources/medical.resources.3-94
-
- Rodney Peck <rodney@balltown.cma.com> is interested in some method
- of establishing a canonical ftp database of images but does not have
- the resources to provide an ftp site for that database. Send suggestions to
- rodney@balltown.cma.com.
-
-
- Beware: the same image often comes in many different forms, at
- different resolutions, etc... The original lenna image is 512 wide,
- 512 high, 8 bits per pel, red, green and blue fields. Gray-scale
- versions of Lenna have been obtained in two different ways from the
- original:
- (1) Using the green field as a gray-scale image, and
- (2) Doing an RGB->YUV transformation and saving the Y component.
- Method (1) makes it easier to compare different people's results since
- everyone's version should be the same using that method. Method (2)
- produces a more correct image.
-
- For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold,
- from November 1972. (Lenna is the spelling in Playboy, Lena is the
- Swedish spelling of the name.) Lena Soderberg (ne Sjooblom) was last
- reported living in her native Sweden, happily married with three kids
- and a job with the state liquor monopoly. In 1988, she was
- interviewed by some Swedish computer related publication, and she was
- pleasantly amused by what had happened to her picture. That was the
- first she knew of the use of that picture in the computer business.
-
- The editorial in the January 1992 issue of Optical Engineering (v. 31
- no. 1) details how Playboy has finally caught on to the fact that
- their copyright on Lena Sjooblom's photo is being widely infringed.
- It sounds as if you will have to get permission from Playboy to
- publish it in the future.
-
- The CCITT (ITU-T) test images are in ftp://ftp.cs.waikato.ac.nz/pub/ccitt/
- and http://www.cs.waikato.ac.nz/~singlis/ccitt.html
- [The images in ftp://nic.funet.fi/pub/graphics/misc/test-images/ccitt*.tif are
- corrupted.] This set is commonly used to compare binary image compression
- techniques. The images are 1728x2376 pixels.
-
- ------------------------------------------------------------------------------
-
- Subject: [56] I am looking for a message digest algorithm
-
-
- Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there.
- This question would be more appropriate on sci.crypt.
-
- ------------------------------------------------------------------------------
-
- Subject: [57] I have lost my password on a .zip file
-
- This question would be more appropriate on sci.crypt.
- Try the following:
- ftp://idea.sec.dsi.unimi.it/pub/security/crypt/code/zipcrack.c.gz
- ftp://idea.sec.dsi.unimi.it/pub/security/crypt/rpub.cl.msu.edu/crypt/msdos/zipcrack*
- ftp://idea.sec.dsi.unimi.it/pub/security/crypt/rpub.cl.msu.edu/crypt/other/zipcrack.c
- ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/fzc100.zip
- ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/pkcrack.zip
- ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/zipcrk20.zip
-
- These are brute force crackers. A known plaintext attack is also possible,
- see ftp://ripem.msu.edu/pub/crypt/docs/kocher-pkzip-attack.ps.gz
-
- End of part 1 of the comp.compression faq.
-
-
- Part 2: (Long) introductions to data compression techniques
-
- [70] Introduction to data compression (long)
- Huffman and Related Compression Techniques
- Arithmetic Coding
- Substitutional Compressors
- The LZ78 family of compressors
- The LZ77 family of compressors
-
- [71] Introduction to MPEG (long)
- What is MPEG?
- Does it have anything to do with JPEG?
- Then what's JBIG and MHEG?
- What has MPEG accomplished?
- So how does MPEG I work?
- What about the audio compression?
- So how much does it compress?
- What's phase II?
- When will all this be finished?
- How do I join MPEG?
- How do I get the documents, like the MPEG I draft?
-
- [72] What is wavelet theory?
- [73] What is the theoretical compression limit?
- [74] Introduction to JBIG
- [75] Introduction to JPEG
- [76] What is Vector Quantization?
- [77] Introduction to Fractal compression
-
- Part 3: (Long) list of image compression hardware
-
- [85] Image compression hardware
- [99] Acknowledgments
-
-
- Search for "Subject: [#]" to get to question number # quickly. Some news
- readers can also take advantage of the message digest format used here.
-
- ------------------------------------------------------------------------------
-
- Subject: [70] Introduction to data compression (long)
-
-
- Written by Peter Gutmann <pgut1@cs.aukuni.ac.nz>.
-
- Huffman and Related Compression Techniques
- ------------------------------------------
-
- *Huffman compression* is a statistical data compression technique which
- gives a reduction in the average code length used to represent the symbols of
- a alphabet. The Huffman code is an example of a code which is optimal in the
- case where all symbols probabilities are integral powers of 1/2. A Huffman
- code can be built in the following manner:
-
- (1) Rank all symbols in order of probability of occurrence.
-
- (2) Successively combine the two symbols of the lowest probability to form
- a new composite symbol; eventually we will build a binary tree where
- each node is the probability of all nodes beneath it.
-
- (3) Trace a path to each leaf, noticing the direction at each node.
-
- For a given frequency distribution, there are many possible Huffman codes,
- but the total compressed length will be the same. It is possible to
- define a 'canonical' Huffman tree, that is, pick one of these alternative
- trees. Such a canonical tree can then be represented very compactly, by
- transmitting only the bit length of each code. This technique is used
- in most archivers (pkzip, lha, zoo, arj, ...).
-
-
- A technique related to Huffman coding is *Shannon-Fano coding*, which
- works as follows:
-
- (1) Divide the set of symbols into two equal or almost equal subsets
- based on the probability of occurrence of characters in each
- subset. The first subset is assigned a binary zero, the second
- a binary one.
-
- (2) Repeat step (1) until all subsets have a single element.
-
- The algorithm used to create the Huffman codes is bottom-up, and the
- one for the Shannon-Fano codes is top-down. Huffman encoding always
- generates optimal codes, Shannon-Fano sometimes uses a few more bits.
-
-
- Arithmetic Coding
- -----------------
-
- It would appear that Huffman or Shannon-Fano coding is the perfect
- means of compressing data. However, this is *not* the case. As
- mentioned above, these coding methods are optimal when and only when
- the symbol probabilities are integral powers of 1/2, which is usually
- not the case.
-
- The technique of *arithmetic coding* does not have this restriction:
- It achieves the same effect as treating the message as one single unit
- (a technique which would, for Huffman coding, require enumeration of
- every single possible message), and thus attains the theoretical
- entropy bound to compression efficiency for any source.
-
- Arithmetic coding works by representing a number by an interval of real
- numbers between 0 and 1. As the message becomes longer, the interval needed
- to represent it becomes smaller and smaller, and the number of bits needed to
- specify that interval increases. Successive symbols in the message reduce
- this interval in accordance with the probability of that symbol. The more
- likely symbols reduce the range by less, and thus add fewer bits to the
- message.
-
- 1 Codewords
- +-----------+-----------+-----------+ /-----\
- | |8/9 YY | Detail |<- 31/32 .11111
- | +-----------+-----------+<- 15/16 .1111
- | Y | | too small |<- 14/16 .1110
- |2/3 | YX | for text |<- 6/8 .110
- +-----------+-----------+-----------+
- | | |16/27 XYY |<- 10/16 .1010
- | | +-----------+
- | | XY | |
- | | | XYX |<- 4/8 .100
- | |4/9 | |
- | +-----------+-----------+
- | | | |
- | X | | XXY |<- 3/8 .011
- | | |8/27 |
- | | +-----------+
- | | XX | |
- | | | |<- 1/4 .01
- | | | XXX |
- | | | |
- |0 | | |
- +-----------+-----------+-----------+
-
- As an example of arithmetic coding, lets consider the example of two
- symbols X and Y, of probabilities 0.66 and 0.33. To encode this message, we
- examine the first symbol: If it is a X, we choose the lower partition; if
- it is a Y, we choose the upper partition. Continuing in this manner for
- three symbols, we get the codewords shown to the right of the diagram above
- - they can be found by simply taking an appropriate location in the
- interval for that particular set of symbols and turning it into a binary
- fraction. In practice, it is also necessary to add a special end-of-data
- symbol, which is not represented in this simpe example.
-
- In this case the arithmetic code is not completely efficient, which is due
- to the shortness of the message - with longer messages the coding efficiency
- does indeed approach 100%.
-
- Now that we have an efficient encoding technique, what can we do with it?
- What we need is a technique for building a model of the data which we can
- then use with the encoder. The simplest model is a fixed one, for example a
- table of standard letter frequencies for English text which we can then use
- to get letter probabilities. An improvement on this technique is to use an
- *adaptive model*, in other words a model which adjusts itself to the data
- which is being compressed as the data is compressed. We can convert the
- fixed model into an adaptive one by adjusting the symbol frequencies after
- each new symbol is encoded, allowing the model to track the data being
- transmitted. However, we can do much better than that.
-
- Using the symbol probabilities by themselves is not a particularly good
- estimate of the true entropy of the data: We can take into account
- intersymbol probabilities as well. The best compressors available today
- take this approach: DMC (Dynamic Markov Coding) starts with a zero-order
- Markov model and gradually extends this initial model as compression
- progresses; PPM (Prediction by Partial Matching) looks for a match of the
- text to be compressed in an order-n context. If no match is found, it
- drops to an order n-1 context, until it reaches order 0. Both these
- techniques thus obtain a much better model of the data to be compressed,
- which, combined with the use of arithmetic coding, results in superior
- compression performance.
-
- So if arithmetic coding-based compressors are so powerful, why are they not
- used universally? Apart from the fact that they are relatively new and
- haven't come into general use too much yet, there is also one major concern:
- The fact that they consume rather large amounts of computing resources, both
- in terms of CPU power and memory. The building of sophisticated models for
- the compression can chew through a fair amount of memory (especially in the
- case of DMC, where the model can grow without bounds); and the arithmetic
- coding itself involves a fair amount of number crunching.
- There is however an alternative approach, a class of compressors generally
- referred to as *substitutional* or *dictionary-based compressors*.
-
- Substitutional Compressors
- --------------------------
-
- The basic idea behind a substitutional compressor is to replace an
- occurrence of a particular phrase or group of bytes in a piece of data with a
- reference to a previous occurrence of that phrase. There are two main
- classes of schemes, named after Jakob Ziv and Abraham Lempel, who first
- proposed them in 1977 and 1978.
-
- <The LZ78 family of compressors>
-
- LZ78-based schemes work by entering phrases into a *dictionary* and then,
- when a repeat occurrence of that particular phrase is found, outputting the
- dictionary index instead of the phrase. There exist several compression
- algorithms based on this principle, differing mainly in the manner in which
- they manage the dictionary. The most well-known scheme (in fact the most
- well-known of all the Lempel-Ziv compressors, the one which is generally (and
- mistakenly) referred to as "Lempel-Ziv Compression"), is Terry Welch's LZW
- scheme, which he designed in 1984 for implementation in hardware for high-
- performance disk controllers.
-
- Input string: /WED/WE/WEE/WEB
-
- Character input: Code output: New code value and associated string:
- /W / 256 = /W
- E W 257 = WE
- D E 258 = ED
- / D 259 = D/
- WE 256 260 = /WE
- / E 261 = E/
- WEE 260 262 = /WEE
- /W 261 263 = E/W
- EB 257 264 = WEB
- <END> B
-
- LZW starts with a 4K dictionary, of which entries 0-255 refer to individual
- bytes, and entries 256-4095 refer to substrings. Each time a new code is
- generated it means a new string has been parsed. New strings are generated
- by appending the current character K to the end of an existing string w. The
- algorithm for LZW compression is as follows:
-
- set w = NIL
- loop
- read a character K
- if wK exists in the dictionary
- w = wK
- else
- output the code for w
- add wK to the string table
- w = K
- endloop
-
- A sample run of LZW over a (highly redundant) input string can be seen in
- the diagram above. The strings are built up character-by-character starting
- with a code value of 256. LZW decompression takes the stream of codes and
- uses it to exactly recreate the original input data. Just like the
- compression algorithm, the decompressor adds a new string to the dictionary
- each time it reads in a new code. All it needs to do in addition is to
- translate each incoming code into a string and send it to the output. A
- sample run of the LZW decompressor is shown in below.
-
- Input code: /WED<256>E<260><261><257>B
-
- Input code: Output string: New code value and associated string:
- / /
- W W 256 = /W
- E E 257 = WE
- D D 258 = ED
- 256 /W 259 = D/
- E E 260 = /WE
- 260 /WE 261 = E/
- 261 E/ 262 = /WEE
- 257 WE 263 = E/W
- B B 264 = WEB
-
- The most remarkable feature of this type of compression is that the entire
- dictionary has been transmitted to the decoder without actually explicitly
- transmitting the dictionary. At the end of the run, the decoder will have a
- dictionary identical to the one the encoder has, built up entirely as part of
- the decoding process.
- LZW is more commonly encountered today in a variant known as LZC, after
- its use in the UNIX "compress" program. In this variant, pointers do not
- have a fixed length. Rather, they start with a length of 9 bits, and then
- slowly grow to their maximum possible length once all the pointers of a
- particular size have been used up. Furthermore, the dictionary is not frozen
- once it is full as for LZW - the program continually monitors compression
- performance, and once this starts decreasing the entire dictionary is
- discarded and rebuilt from scratch. More recent schemes use some sort of
- least-recently-used algorithm to discard little-used phrases once the
- dictionary becomes full rather than throwing away the entire dictionary.
-
- Finally, not all schemes build up the dictionary by adding a single new
- character to the end of the current phrase. An alternative technique is to
- concatenate the previous two phrases (LZMW), which results in a faster
- buildup of longer phrases than the character-by-character buildup of the
- other methods. The disadvantage of this method is that a more sophisticated
- data structure is needed to handle the dictionary.
-
- [A good introduction to LZW, MW, AP and Y coding is given in the yabba
- package. For ftp information, see question 2 in part one, file type .Y]
-
-
- <The LZ77 family of compressors>
-
- LZ77-based schemes keep track of the last n bytes of data seen, and when a
- phrase is encountered that has already been seen, they output a pair of
- values corresponding to the position of the phrase in the previously-seen
- buffer of data, and the length of the phrase. In effect the compressor moves
- a fixed-size *window* over the data (generally referred to as a *sliding
- window*), with the position part of the (position, length) pair referring to
- the position of the phrase within the window. The most commonly used
- algorithms are derived from the LZSS scheme described by James Storer and
- Thomas Szymanski in 1982. In this the compressor maintains a window of size
- N bytes and a *lookahead buffer* the contents of which it tries to find a
- match for in the window:
-
- while( lookAheadBuffer not empty )
- {
- get a pointer ( position, match ) to the longest match in the window
- for the lookahead buffer;
-
- if( length > MINIMUM_MATCH_LENGTH )
- {
- output a ( position, length ) pair;
- shift the window length characters along;
- }
- else
- {
- output the first character in the lookahead buffer;
- shift the window 1 character along;
- }
- }
-
- Decompression is simple and fast: Whenever a ( position, length ) pair is
- encountered, go to that ( position ) in the window and copy ( length ) bytes
- to the output.
-
- Sliding-window-based schemes can be simplified by numbering the input text
- characters mod N, in effect creating a circular buffer. The sliding window
- approach automatically creates the LRU effect which must be done explicitly in
- LZ78 schemes. Variants of this method apply additional compression to the
- output of the LZSS compressor, which include a simple variable-length code
- (LZB), dynamic Huffman coding (LZH), and Shannon-Fano coding (ZIP 1.x)), all
- of which result in a certain degree of improvement over the basic scheme,
- especially when the data are rather random and the LZSS compressor has little
- effect.
- Recently an algorithm was developed which combines the ideas behind LZ77 and
- LZ78 to produce a hybrid called LZFG. LZFG uses the standard sliding window,
- but stores the data in a modified trie data structure and produces as output
- the position of the text in the trie. Since LZFG only inserts complete
- *phrases* into the dictionary, it should run faster than other LZ77-based
- compressors.
-
- All popular archivers (arj, lha, zip, zoo) are variations on the LZ77 theme.
-
- ------------------------------------------------------------------------------
-
- Subject: [71] Introduction to MPEG (long)
-
-
- For MPEG players, see item 15 in part 1 of the FAQ. Frank Gadegast
- <phade@cs.tu-berlin.de> also posts a FAQ specialized in MPEG, available in
- ftp://ftp.cs.tu-berlin.de/pub/msdos/dos/graphics/mpegfa*.zip and
- http://www.powerweb.de/mpeg/mpegfaq/
-
- The site ftp.crs4.it dedicated to the MPEG compression standard,
- see the directory mpeg and subdirectories. Another MPEG FAQ is available
- in http://www.crs4.it/~luigi/MPEG/mpegfaq.html
- See also http://www-plateau.cs.berkeley.edu/mpeg
-
- A description of MPEG can be found in: "MPEG: A Video Compression
- Standard for Multimedia Applications" Didier Le Gall, Communications
- of the ACM, April 1991, Vol 34. No.4, pp.46-58.
-
- The MPEG book (ISBN 0-442-01920-3) was originally scheduled for August
- 1994 by Van Nostrand publishing (phone 800-842-3636) then later for
- December 1995 (anyone got more recent info?).
-
- MPEG-2 bitstreams are available on wuarchive.wustl.edu in directory
- /graphics/x3l3/pub/bitstreams. MPEG-2 Demultiplexer source code is
- in /graphics/x3l3/pub/bitstreams/systems/munsi_v13.tar.gz
-
- Public C source encoder for all 3 layers for mpeg2 including mpeg1 is in
- ftp://ftp.tnt.uni-hannover.de/pub/MPEG/audio/mpeg2/public_software/
- technical_report/dist08.tar.gz
-
-
- Introduction to MPEG originally written by Mark Adler
- <madler@cco.caltech.edu> around January 1992; modified and updated by
- Harald Popp <layer3@iis.fhg.de> in March 94:
-
- Q: What is MPEG, exactly?
-
- A: MPEG is the "Moving Picture Experts Group", working under the
- joint direction of the International Standards Organization (ISO)
- and the International Electro-Technical Commission (IEC). This
- group works on standards for the coding of moving pictures and
- associated audio.
-
- Q: What is the status of MPEG's work, then? What's about MPEG-1, -2,
- and so on?
-
- A: MPEG approaches the growing need for multimedia standards step-by-
- step. Today, three "phases" are defined:
-
- MPEG-1: "Coding of Moving Pictures and Associated Audio for
- Digital Storage Media at up to about 1.5 MBit/s"
-
- Status: International Standard IS-11172, completed in 10.92
-
- MPEG-2: "Generic Coding of Moving Pictures and Associated Audio"
-
- Status: Comittee Draft CD 13818 as found in documents MPEG93 /
- N601, N602, N603 (11.93)
-
- MPEG-3: no longer exists (has been merged into MPEG-2)
-
- MPEG-4: "Very Low Bitrate Audio-Visual Coding"
-
- Status: Call for Proposals 11.94, Working Draft in 11.96
-
- Q: MPEG-1 is ready-for-use. How does the standard look like?
-
- A: MPEG-1 consists of 4 parts:
-
- IS 11172-1: System
- describes synchronization and multiplexing of video and audio
-
- IS 11172-2: Video
- describes compression of non-interlaced video signals
-
- IS 11172-3: Audio
- describes compression of audio signals
-
- CD 11172-4: Compliance Testing
- describes procedures for determining the characteristics of coded
- bitstreams and the decoding porcess and for testing compliance
- with the requirements stated in the other parts
-
- Q. Does MPEG have anything to do with JPEG?
-
- A. Well, it sounds the same, and they are part of the same
- subcommittee of ISO along with JBIG and MHEG, and they usually meet
- at the same place at the same time. However, they are different
- sets of people with few or no common individual members, and they
- have different charters and requirements. JPEG is for still image
- compression.
-
- Q. Then what's JBIG and MHEG?
-
- A. Sorry I mentioned them. Ok, I'll simply say that JBIG is for binary
- image compression (like faxes), and MHEG is for multi-media data
- standards (like integrating stills, video, audio, text, etc.).
- For an introduction to JBIG, see question 74 below.
-
- Q. So how does MPEG-1 work? Tell me about video coding!
-
- A. First off, it starts with a relatively low resolution video
- sequence (possibly decimated from the original) of about 352 by
- 240 frames by 30 frames/s (US--different numbers for Europe),
- but original high (CD) quality audio. The images are in color,
- but converted to YUV space, and the two chrominance channels
- (U and V) are decimated further to 176 by 120 pixels. It turns
- out that you can get away with a lot less resolution in those
- channels and not notice it, at least in "natural" (not computer
- generated) images.
-
- The basic scheme is to predict motion from frame to frame in the
- temporal direction, and then to use DCT's (discrete cosine
- transforms) to organize the redundancy in the spatial directions.
- The DCT's are done on 8x8 blocks, and the motion prediction is
- done in the luminance (Y) channel on 16x16 blocks. In other words,
- given the 16x16 block in the current frame that you are trying to
- code, you look for a close match to that block in a previous or
- future frame (there are backward prediction modes where later
- frames are sent first to allow interpolating between frames).
- The DCT coefficients (of either the actual data, or the difference
- between this block and the close match) are "quantized", which
- means that you divide them by some value to drop bits off the
- bottom end. Hopefully, many of the coefficients will then end up
- being zero. The quantization can change for every "macroblock"
- (a macroblock is 16x16 of Y and the corresponding 8x8's in both
- U and V). The results of all of this, which include the DCT
- coefficients, the motion vectors, and the quantization parameters
- (and other stuff) is Huffman coded using fixed tables. The DCT
- coefficients have a special Huffman table that is "two-dimensional"
- in that one code specifies a run-length of zeros and the non-zero
- value that ended the run. Also, the motion vectors and the DC
- DCT components are DPCM (subtracted from the last one) coded.
-
- Q. So is each frame predicted from the last frame?
-
- A. No. The scheme is a little more complicated than that. There are
- three types of coded frames. There are "I" or intra frames. They
- are simply a frame coded as a still image, not using any past
- history. You have to start somewhere. Then there are "P" or
- predicted frames. They are predicted from the most recently
- reconstructed I or P frame. (I'm describing this from the point
- of view of the decompressor.) Each macroblock in a P frame can
- either come with a vector and difference DCT coefficients for a
- close match in the last I or P, or it can just be "intra" coded
- (like in the I frames) if there was no good match.
-
- Lastly, there are "B" or bidirectional frames. They are predicted
- from the closest two I or P frames, one in the past and one in the
- future. You search for matching blocks in those frames, and try
- three different things to see which works best. (Now I have the
- point of view of the compressor, just to confuse you.) You try
- using the forward vector, the backward vector, and you try
- averaging the two blocks from the future and past frames, and
- subtracting that from the block being coded. If none of those work
- well, you can intracode the block.
-
- The sequence of decoded frames usually goes like:
-
- IBBPBBPBBPBBIBBPBBPB...
-
- Where there are 12 frames from I to I (for US and Japan anyway.)
- This is based on a random access requirement that you need a
- starting point at least once every 0.4 seconds or so. The ratio
- of P's to B's is based on experience.
-
- Of course, for the decoder to work, you have to send that first
- P *before* the first two B's, so the compressed data stream ends
- up looking like:
-
- 0xx312645...
-
- where those are frame numbers. xx might be nothing (if this is
- the true starting point), or it might be the B's of frames -2 and
- -1 if we're in the middle of the stream somewhere.
-
- You have to decode the I, then decode the P, keep both of those
- in memory, and then decode the two B's. You probably display the
- I while you're decoding the P, and display the B's as you're
- decoding them, and then display the P as you're decoding the next
- P, and so on.
-
- Q. You've got to be kidding.
-
- A. No, really!
-
- Q. Hmm. Where did they get 352x240?
-
- A. That derives from the CCIR-601 digital television standard which
- is used by professional digital video equipment. It is (in the US)
- 720 by 243 by 60 fields (not frames) per second, where the fields
- are interlaced when displayed. (It is important to note though
- that fields are actually acquired and displayed a 60th of a second
- apart.) The chrominance channels are 360 by 243 by 60 fields a
- second, again interlaced. This degree of chrominance decimation
- (2:1 in the horizontal direction) is called 4:2:2. The source
- input format for MPEG I, called SIF, is CCIR-601 decimated by 2:1
- in the horizontal direction, 2:1 in the time direction, and an
- additional 2:1 in the chrominance vertical direction. And some
- lines are cut off to make sure things divide by 8 or 16 where
- needed.
-
- Q. What if I'm in Europe?
-
- A. For 50 Hz display standards (PAL, SECAM) change the number of lines
- in a field from 243 or 240 to 288, and change the display rate to
- 50 fields/s or 25 frames/s. Similarly, change the 120 lines in
- the decimated chrominance channels to 144 lines. Since 288*50 is
- exactly equal to 240*60, the two formats have the same source data
- rate.
-
- Q. What will MPEG-2 do for video coding?
-
- A. As I said, there is a considerable loss of quality in going from
- CCIR-601 to SIF resolution. For entertainment video, it's simply
- not acceptable. You want to use more bits and code all or almost
- all the CCIR-601 data. From subjective testing at the Japan
- meeting in November 1991, it seems that 4 MBits/s can give very
- good quality compared to the original CCIR-601 material. The
- objective of MPEG-2 is to define a bit stream optimized for
- these resolutions and bit rates.
-
- Q. Why not just scale up what you're doing with MPEG-1?
-
- A. The main difficulty is the interlacing. The simplest way to extend
- MPEG-1 to interlaced material is to put the fields together into
- frames (720x486x30/s). This results in bad motion artifacts that
- stem from the fact that moving objects are in different places
- in the two fields, and so don't line up in the frames. Compressing
- and decompressing without taking that into account somehow tends to
- muddle the objects in the two different fields.
-
- The other thing you might try is to code the even and odd field
- streams separately. This avoids the motion artifacts, but as you
- might imagine, doesn't get very good compression since you are not
- using the redundancy between the even and odd fields where there
- is not much motion (which is typically most of image).
-
- Or you can code it as a single stream of fields. Or you can
- interpolate lines. Or, etc. etc. There are many things you can
- try, and the point of MPEG-2 is to figure out what works well.
- MPEG-2 is not limited to consider only derivations of MPEG-1.
- There were several non-MPEG-1-like schemes in the competition in
- November, and some aspects of those algorithms may or may not
- make it into the final standard for entertainment video
- compression.
-
- Q. So what works?
-
- A. Basically, derivations of MPEG-1 worked quite well, with one that
- used wavelet subband coding instead of DCT's that also worked very
- well. Also among the worked-very-well's was a scheme that did not
- use B frames at all, just I and P's. All of them, except maybe
- one, did some sort of adaptive frame/field coding, where a decision
- is made on a macroblock basis as to whether to code that one as
- one frame macroblock or as two field macroblocks. Some other
- aspects are how to code I-frames--some suggest predicting the even
- field from the odd field. Or you can predict evens from evens and
- odds or odds from evens and odds or any field from any other field,
- etc.
-
- Q. So what works?
-
- A. Ok, we're not really sure what works best yet. The next step is
- to define a "test model" to start from, that incorporates most of
- the salient features of the worked-very-well proposals in a
- simple way. Then experiments will be done on that test model,
- making a mod at a time, and seeing what makes it better and what
- makes it worse. Example experiments are, B's or no B's, DCT vs.
- wavelets, various field prediction modes, etc. The requirements,
- such as implementation cost, quality, random access, etc. will all
- feed into this process as well.
-
- Q. When will all this be finished?
-
- A. I don't know. I'd have to hope in about a year or less.
-
- Q: Talking about MPEG audio coding, I heard a lot about "Layer 1, 2
- and 3". What does it mean, exactly?
-
- A: MPEG-1, IS 11172-3, describes the compression of audio signals
- using high performance perceptual coding schemes. It specifies a
- family of three audio coding schemes, simply called Layer-1,-2,-3,
- with increasing encoder complexity and performance (sound quality
- per bitrate). The three codecs are compatible in a hierarchical
- way, i.e. a Layer-N decoder is able to decode bitstream data
- encoded in Layer-N and all Layers below N (e.g., a Layer-3
- decoder may accept Layer-1,-2 and -3, whereas a Layer-2 decoder
- may accept only Layer-1 and -2.)
-
- Q: So we have a family of three audio coding schemes. What does the
- MPEG standard define, exactly?
-
- A: For each Layer, the standard specifies the bitstream format and
- the decoder. To allow for future improvements, it does *not*
- specify the encoder , but an informative chapter gives an example
- for an encoder for each Layer.
-
- Q: What have the three audio Layers in common?
-
- A: All Layers use the same basic structure. The coding scheme can be
- described as "perceptual noise shaping" or "perceptual subband /
- transform coding".
-
- The encoder analyzes the spectral components of the audio signal
- by calculating a filterbank or transform and applies a
- psychoacoustic model to estimate the just noticeable noise-
- level. In its quantization and coding stage, the encoder tries
- to allocate the available number of data bits in a way to meet
- both the bitrate and masking requirements.
-
- The decoder is much less complex. Its only task is to synthesize
- an audio signal out of the coded spectral components.
-
- All Layers use the same analysis filterbank (polyphase with 32
- subbands). Layer-3 adds a MDCT transform to increase the frequency
- resolution.
-
- All Layers use the same "header information" in their bitstream,
- to support the hierarchical structure of the standard.
-
- All Layers use a bitstream structure that contains parts that are
- more sensitive to biterrors ("header", "bit allocation",
- "scalefactors", "side information") and parts that are less
- sensitive ("data of spectral components").
-
- All Layers may use 32, 44.1 or 48 kHz sampling frequency.
-
- All Layers are allowed to work with similar bitrates:
- Layer-1: from 32 kbps to 448 kbps
- Layer-2: from 32 kbps to 384 kbps
- Layer-3: from 32 kbps to 320 kbps
-
- Q: What are the main differences between the three Layers, from a
- global view?
-
- A: From Layer-1 to Layer-3,
- complexity increases (mainly true for the encoder),
- overall codec delay increases, and
- performance increases (sound quality per bitrate).
-
- Q: Which Layer should I use for my application?
-
- A: Good Question. Of course, it depends on all your requirements. But
- as a first approach, you should consider the available bitrate of
- your application as the Layers have been designed to support
- certain areas of bitrates most efficiently, i.e. with a minimum
- drop of sound quality.
-
- Let us look a little closer at the strong domains of each Layer.
-
- Layer-1: Its ISO target bitrate is 192 kbps per audio channel.
-
- Layer-1 is a simplified version of Layer-2. It is most useful for
- bitrates around the "high" bitrates around or above 192 kbps. A
- version of Layer-1 is used as "PASC" with the DCC recorder.
-
- Layer-2: Its ISO target bitrate is 128 kbps per audio channel.
-
- Layer-2 is identical with MUSICAM. It has been designed as trade-
- off between sound quality per bitrate and encoder complexity. It
- is most useful for bitrates around the "medium" bitrates of 128 or
- even 96 kbps per audio channel. The DAB (EU 147) proponents have
- decided to use Layer-2 in the future Digital Audio Broadcasting
- network.
-
- Layer-3: Its ISO target bitrate is 64 kbps per audio channel.
-
- Layer-3 merges the best ideas of MUSICAM and ASPEC. It has been
- designed for best performance at "low" bitrates around 64 kbps or
- even below. The Layer-3 format specifies a set of advanced
- features that all address one goal: to preserve as much sound
- quality as possible even at rather low bitrates. Today, Layer-3 is
- already in use in various telecommunication networks (ISDN,
- satellite links, and so on) and speech announcement systems.
-
- Q: Tell me more about sound quality. How do you assess that?
-
- A: Today, there is no alternative to expensive listening tests.
- During the ISO-MPEG-1 process, 3 international listening tests
- have been performed, with a lot of trained listeners, supervised
- by Swedish Radio. They took place in 7.90, 3.91 and 11.91. Another
- international listening test was performed by CCIR, now ITU-R, in
- 92.
-
- All these tests used the "triple stimulus, hidden reference"
- method and the CCIR impairment scale to assess the audio quality.
- The listening sequence is "ABC", with A = original, BC = pair of
- original / coded signal with random sequence, and the listener has
- to evaluate both B and C with a number between 1.0 and 5.0. The
- meaning of these values is:
-
- 5.0 = transparent (this should be the original signal)
- 4.0 = perceptible, but not annoying (first differences noticable)
- 3.0 = slightly annoying
- 2.0 = annoying
- 1.0 = very annoying
-
- With perceptual codecs (like MPEG audio), all traditional
- parameters (like SNR, THD+N, bandwidth) are especially useless.
- Fraunhofer-IIS works on objective quality assessment tools, like
- the NMR meter (Noise-to-Mask-Ratio), too. BTW: If you need more
- informations about NMR, please contact nmr@iis.fhg.de.
-
- Q: Now that I know how to assess quality, come on, tell me the
- results of these tests.
-
- A: Well, for low bitrates, the main result is that at 60 or 64 kbps
- per channel), Layer-2 scored always between 2.1 and 2.6, whereas
- Layer-3 scored between 3.6 and 3.8. This is a significant increase
- in sound quality, indeed! Furthermore, the selection process for
- critical sound material showed that it was rather difficult to
- find worst-case material for Layer-3 whereas it was not so hard to
- find such items for Layer-2.
-
- Q: OK, a Layer-2 codec at low bitrates may sound poor today, but
- couldn't that be improved in the future? I guess you just told me
- before that the encoder is not fixed in the standard.
-
- A: Good thinking! As the sound quality mainly depends on the encoder
- implementation, it is true that there is no such thing as a "Layer-
- N"- quality. So we definitely only know the performance of the
- reference codecs during the international tests. Who knows what
- will happen in the future? What we do know now, is:
-
- Today, Layer-3 already provides a sound quality that comes very
- near to CD quality at 64 kbps per channel. Layer-2 is far away
- from that.
-
- Tomorrow, both Layers may improve. Layer-2 has been designed as a
- trade-off between quality and complexity, so the bitstream format
- allows only limited innovations. In contrast, even the current
- reference Layer-3-codec exploits only a small part of the powerful
- mechanisms inside the Layer-3 bitstream format.
-
- Q: All in all, you sound as if anybody should use Layer-3 for low
- bitrates. Why on earth do some vendors still offer only Layer-2
- equipment for these applications?
-
- A: Well, maybe because they started to design and develop their
- system rather early, e.g. in 1990. As Layer-2 is identical with
- MUSICAM, it has been available since summer of 90, at latest. In
- that year, Layer-3 development started and could be successfully
- finished in spring 92. So, for a certain time, vendors could only
- exploit the existing part of the new MPEG standard.
-
- Now the situation has changed. All Layers are available, the
- standard is completed, and new systems need not limit themselves,
- but may capitalize on the full features of MPEG audio.
-
- Q: How do I get the MPEG documents?
-
- A: You may order it from your national standards body.
-
- E.g., in Germany, please contact:
- DIN-Beuth Verlag, Auslandsnormen
- Mrs. Niehoff, Burggrafenstr. 6, D-10772 Berlin, Germany
- Phone: 030-2601-2757, Fax: 030-2601-1231
-
- E.g., in USA, you may order it from ANSI [phone (212) 642-4900] or
- buy it from companies like OMNICOM phone +44 438 742424
- FAX +44 438 740154
-
- Q. How do I join MPEG?
-
- A. You don't join MPEG. You have to participate in ISO as part of a
- national delegation. How you get to be part of the national
- delegation is up to each nation. I only know the U.S., where you
- have to attend the corresponding ANSI meetings to be able to
- attend the ISO meetings. Your company or institution has to be
- willing to sink some bucks into travel since, naturally, these
- meetings are held all over the world. (For example, Paris,
- Santa Clara, Kurihama Japan, Singapore, Haifa Israel, Rio de
- Janeiro, London, etc.)
-
- ------------------------------------------------------------------------------
-
- Subject: [72] What is wavelet theory?
-
-
- Preprints and software are available by anonymous ftp from the
- Yale Mathematics Department computer ftp://ceres.math.yale.edu/pub/wavelets/
- and /pub/software/ .
-
- For source code of several wavelet coders, see item 15 in part one of
- this FAQ.
-
- A list of pointers, covering theory, papers, books, implementations,
- resources and more can be found at
- http://www.amara.com/current/wavelet.html#Wavelinks
-
- Bill Press of Harvard/CfA has made some things available on
- ftp://cfata4.harvard.edu/pub/ There is a short TeX article on wavelet
- theory (wavelet.tex, to be included in a future edition of Numerical
- Recipes), some sample wavelet code (wavelet.f, in FORTRAN - sigh), and
- a beta version of an astronomical image compression program which he
- is currently developing (FITS format data files only, in
- fitspress08.tar.Z).
-
- The Rice Wavelet Toolbox Release 2.0 is available in
- ftp://cml.rice.edu/pub/dsp/software/ and /pub/dsp/papers/ . This is a
- collection of MATLAB of "mfiles" and "mex" files for twoband and
- M-band filter bank/wavelet analysis from the DSP group and
- Computational Mathematics Laboratory (CML) at Rice University,
- Houston, TX. This release includes application code for Synthetic
- Aperture Radar despeckling and for deblocking of JPEG decompressed
- Images. Contact: Ramesh Gopinath <ramesh@rice.edu>.
-
- A mailing list dedicated to research on wavelets has been set up at the
- University of South Carolina. To subscribe to this mailing list, send a
- message with "subscribe" as the subject to wavelet@math.sc.edu.
- For back issues and other information, check the WWW home page at
- http://www.math.sc.edu/~wavelet/
-
- A tutorial by M. Hilton, B. Jawerth, and A. Sengupta, entitled
- "Compressing Still and Moving Images with Wavelets" is available in
- ftp://ftp.math.sc.edu/pub/wavelet/papers/varia/tutorial/ . The
- files are "tutorial.ps.Z" and "fig8.ps.Z". fig8 is a comparison of
- JPEG and wavelet compressed images and could take several hours to
- print. The tutorial is also available at
- http://www.mathsoft.com/wavelets.html
-
- A page on wavelet-based HARC-C compression technology is available at
- http://www.harc.edu/HARCC.html
-
- Commercial wavelet image compression software:
- http://www.aware.com
- http://www.summus.com
-
- Details of the wavelet transform can be found in
- ftp://ftp.isds.duke.edu/pub/brani/papers/wav4kidsA.ps.Z
- ftp://ftp.isds.duke.edu/pub/brani/papers/wav4kidsB.ps.Z
-
-
- A 5 minute course in wavelet transforms, by Richard Kirk <rak@crosfield.co.uk>:
-
- Do you know what a Haar transform is? Its a transform to another orthonormal
- space (like the DFT), but the basis functions are a set of square wave bursts
- like this...
-
- +--+ +------+
- + | +------------------ + | +--------------
- +--+ +------+
-
- +--+ +------+
- ------+ | +------------ --------------+ | +
- +--+ +------+
-
- +--+ +-------------+
- ------------+ | +------ + | +
- +--+ +-------------+
-
- +--+ +---------------------------+
- ------------------+ | + + +
- +--+
-
- This is the set of functions for an 8-element 1-D Haar transform. You
- can probably see how to extend this to higher orders and higher dimensions
- yourself. This is dead easy to calculate, but it is not what is usually
- understood by a wavelet transform.
-
- If you look at the eight Haar functions you see we have four functions
- that code the highest resolution detail, two functions that code the
- coarser detail, one function that codes the coarser detail still, and the
- top function that codes the average value for the whole `image'.
-
- Haar function can be used to code images instead of the DFT. With bilevel
- images (such as text) the result can look better, and it is quicker to code.
- Flattish regions, textures, and soft edges in scanned images get a nasty
- `blocking' feel to them. This is obvious on hardcopy, but can be disguised on
- color CRTs by the effects of the shadow mask. The DCT gives more consistent
- results.
-
- This connects up with another bit of maths sometimes called Multispectral
- Image Analysis, sometimes called Image Pyramids.
-
- Suppose you want to produce a discretely sampled image from a continuous
- function. You would do this by effectively `scanning' the function using a
- sinc function [ sin(x)/x ] `aperture'. This was proved by Shannon in the
- `forties. You can do the same thing starting with a high resolution
- discretely sampled image. You can then get a whole set of images showing
- the edges at different resolutions by differencing the image at one
- resolution with another version at another resolution. If you have made this
- set of images properly they ought to all add together to give the original
- image.
-
- This is an expansion of data. Suppose you started off with a 1K*1K image.
- You now may have a 64*64 low resolution image plus difference images at 128*128
- 256*256, 512*512 and 1K*1K.
-
- Where has this extra data come from? If you look at the difference images you
- will see there is obviously some redundancy as most of the values are near
- zero. From the way we constructed the levels we know that locally the average
- must approach zero in all levels but the top. We could then construct a set of
- functions out of the sync functions at any level so that their total value
- at all higher levels is zero. This gives us an orthonormal set of basis
- functions for a transform. The transform resembles the Haar transform a bit,
- but has symmetric wave pulses that decay away continuously in either direction
- rather than square waves that cut off sharply. This transform is the
- wavelet transform ( got to the point at last!! ).
-
- These wavelet functions have been likened to the edge detecting functions
- believed to be present in the human retina.
-
-
- Loren I. Petrich <lip@s1.gov> adds that order 2 or 3 Daubechies
- discrete wavelet transforms have a speed comparable to DCT's, and
- usually achieve compression a factor of 2 better for the same image
- quality than the JPEG 8*8 DCT. (See item 25 in part 1 of this FAQ for
- references on fast DCT algorithms.)
-
- ------------------------------------------------------------------------------
-
- Subject: [73] What is the theoretical compression limit?
-
-
- This question can be understood in two different ways:
-
- (a) For a given compressor/decompressor, what is the best possible
- lossless compression for an arbitrary string (byte sequence)
- given as input?
-
- (b) For a given string, what is the best possible lossless
- compressor/decompressor?
-
- For case (a), the question is generally meaningless, because a
- specific compressor may compress one very large input file down to a
- single bit, and enlarge all other files by only one bit. There is no
- lossless compressor that is guaranteed to compress all possible input
- files. If it compresses some files, then it must enlarge some others.
- This can be proven by a simple counting argument (see item 9). In
- case (a), the size of the decompressor is not taken into account for
- the determination of the compression ratio since the decompressor is
- fixed and it may decompress an arbitrary number of files of arbitrary
- length.
-
- For case (b), it is of course necessary to take into account the size
- of the decompressor. The problem may be restated as "What is the
- shortest program p which, when executed, produces the input string s?".
- The size of this program is known as the Kolmogorov complexity
- of the string s. Strings that are truly random are not compressible:
- the smallest representation of the string is the string itself.
- On the other hand, the output of a pseudo-random number generator
- can be extremely compressible, since it is sufficient to know the
- parameters and seed of the generator to reproduce an arbitrary
- long sequence.
-
- References: "An Introduction to Kolmogorov Complexity and its Applications",
- Ming Li and Paul Vitanyi, Springer-Verlag, 1992
-
- ------------------------------------------------------------------------------
-
- Subject: [74] Introduction to JBIG
-
-
- JBIG software and the JBIG specification are available on nic.funet.fi
- in /pub/graphics/misc/test-images/jbig.tar.gz.
-
-
- A short introduction to JBIG, written by Mark Adler <madler@cco.caltech.edu>:
-
- JBIG losslessly compresses binary (one-bit/pixel) images. (The B stands
- for bi-level.) Basically it models the redundancy in the image as the
- correlations of the pixel currently being coded with a set of nearby
- pixels called the template. An example template might be the two
- pixels preceding this one on the same line, and the five pixels centered
- above this pixel on the previous line. Note that this choice only
- involves pixels that have already been seen from a scanner.
-
- The current pixel is then arithmetically coded based on the eight-bit
- (including the pixel being coded) state so formed. So there are (in this
- case) 256 contexts to be coded. The arithmetic coder and probability
- estimator for the contexts are actually IBM's (patented) Q-coder. The
- Q-coder uses low precision, rapidly adaptable (those two are related)
- probability estimation combined with a multiply-less arithmetic coder.
- The probability estimation is intimately tied to the interval calculations
- necessary for the arithmetic coding.
-
- JBIG actually goes beyond this and has adaptive templates, and probably
- some other bells and whistles I don't know about. You can find a
- description of the Q-coder as well as the ancestor of JBIG in the Nov 88
- issue of the IBM Journal of Research and Development. This is a very
- complete and well written set of five articles that describe the Q-coder
- and a bi-level image coder that uses the Q-coder.
-
- You can use JBIG on grey-scale or even color images by simply applying
- the algorithm one bit-plane at a time. You would want to recode the
- grey or color levels first though, so that adjacent levels differ in
- only one bit (called Gray-coding). I hear that this works well up to
- about six bits per pixel, beyond which JPEG's lossless mode works better.
- You need to use the Q-coder with JPEG also to get this performance.
-
- Actually no lossless mode works well beyond six bits per pixel, since
- those low bits tend to be noise, which doesn't compress at all.
-
- Anyway, the intent of JBIG is to replace the current, less effective
- group 3 and 4 fax algorithms.
-
-
- Another introduction to JBIG, written by Hank van Bekkem <jbek@oce.nl>:
-
- The following description of the JBIG algorithm is derived from
- experiences with a software implementation I wrote following the
- specifications in the revision 4.1 draft of September 16, 1991. The
- source will not be made available in the public domain, as parts of
- JBIG are patented.
-
- JBIG (Joint Bi-level Image Experts Group) is an experts group of ISO,
- IEC and CCITT (JTC1/SC2/WG9 and SGVIII). Its job is to define a
- compression standard for lossless image coding ([1]). The main
- characteristics of the proposed algorithm are:
- - Compatible progressive/sequential coding. This means that a
- progressively coded image can be decoded sequentially, and the
- other way around.
- - JBIG will be a lossless image compression standard: all bits in
- your images before and after compression and decompression will be
- exactly the same.
-
- In the rest of this text I will first describe the JBIG algorithm in
- a short abstract of the draft. I will conclude by saying something
- about the value of JBIG.
-
-
- JBIG algorithm.
- --------------
-
- JBIG parameter P specifies the number of bits per pixel in the image.
- Its allowable range is 1 through 255, but starting at P=8 or so,
- compression will be more efficient using other algorithms. On the
- other hand, medical images such as chest X-rays are often stored with
- 12 bits per pixel, while no distorsion is allowed, so JBIG can
- certainly be of use in this area. To limit the number of bit changes
- between adjacent decimal values (e.g. 127 and 128), it is wise to use
- Gray coding before compressing multi-level images with JBIG. JBIG
- then compresses the image on a bitplane basis, so the rest of this
- text assumes bi-level pixels.
-
- Progressive coding is a way to send an image gradually to a receiver
- instead of all at once. During sending, more detail is sent, and the
- receiver can build the image from low to high detail. JBIG uses
- discrete steps of detail by successively doubling the resolution. The
- sender computes a number of resolution layers D, and transmits these
- starting at the lowest resolution Dl. Resolution reduction uses
- pixels in the high resolution layer and some already computed low
- resolution pixels as an index into a lookup table. The contents of
- this table can be specified by the user.
-
- Compatibility between progressive and sequential coding is achieved
- by dividing an image into stripes. Each stripe is a horizontal bar
- with a user definable height. Each stripe is separately coded and
- transmitted, and the user can define in which order stripes,
- resolutions and bitplanes (if P>1) are intermixed in the coded data.
- A progressive coded image can be decoded sequentially by decoding
- each stripe, beginning by the one at the top of the image, to its
- full resolution, and then proceeding to the next stripe. Progressive
- decoding can be done by decoding only a specific resolution layer
- from all stripes.
-
- After dividing an image into bitplanes, resolution layers and
- stripes, eventually a number of small bi-level bitmaps are left to
- compress. Compression is done using a Q-coder. Reference [2]
- contains a full description, I will only outline the basic principles
- here.
-
- The Q-coder codes bi-level pixels as symbols using the probability of
- occurrence of these symbols in a certain context. JBIG defines two
- kinds of context, one for the lowest resolution layer (the base
- layer), and one for all other layers (differential layers).
- Differential layer contexts contain pixels in the layer to be coded,
- and in the corresponding lower resolution layer.
-
- For each combination of pixel values in a context, the probability
- distribution of black and white pixels can be different. In an all
- white context, the probability of coding a white pixel will be much
- greater than that of coding a black pixel. The Q-coder assigns, just
- like a Huffman coder, more bits to less probable symbols, and so
- achieves compression. The Q-coder can, unlike a Huffmann coder,
- assign one output codebit to more than one input symbol, and thus is
- able to compress bi-level pixels without explicit clustering, as
- would be necessary using a Huffman coder.
-
- Maximum compression will be achieved when all probabilities (one set
- for each combination of pixel values in the context) follow the
- probabilities of the pixels. The Q-coder therefore continuously
- adapts these probabilities to the symbols it sees.
-
-
- JBIG value.
- ----------
-
- In my opinion, JBIG can be regarded as two combined devices:
- - Providing the user the service of sending or storing multiple
- representations of images at different resolutions without any
- extra cost in storage. Differential layer contexts contain pixels
- in two resolution layers, and so enable the Q-coder to effectively
- code the difference in information between the two layers, instead
- of the information contained in every layer. This means that,
- within a margin of approximately 5%, the number of resolution
- layers doesn't effect the compression ratio.
- - Providing the user a very efficient compression algorithm, mainly
- for use with bi-level images. Compared to CCITT Group 4, JBIG is
- approximately 10% to 50% better on text and line art, and even
- better on halftones. JBIG is however, just like Group 4, somewhat
- sensitive to noise in images. This means that the compression ratio
- decreases when the amount of noise in your images increases.
-
- An example of an application would be browsing through an image
- database, e.g. an EDMS (engineering document management system).
- Large A0 size drawings at 300 dpi or so would be stored using five
- resolution layers. The lowest resolution layer would fit on a
- computer screen. Base layer compressed data would be stored at the
- beginning of the compressed file, thus making browsing through large
- numbers of compressed drawings possible by reading and decompressing
- just the first small part of all files. When the user stops browsing,
- the system could automatically start decompressing all remaining
- detail for printing at high resolution.
-
- [1] "Progressive Bi-level Image Compression, Revision 4.1", ISO/IEC
- JTC1/SC2/WG9, CD 11544, September 16, 1991
- [2] "An overview of the basic principles of the Q-coder adaptive
- binary arithmetic coder", W.B. Pennebaker, J.L. Mitchell, G.G.
- Langdon, R.B. Arps, IBM Journal of research and development,
- Vol.32, No.6, November 1988, pp. 771-726 (See also the other
- articles about the Q-coder in this issue)
-
- ------------------------------------------------------------------------------
-
- Subject: [75] Introduction to JPEG
-
- Here is a brief overview of the inner workings of JPEG, plus some references
- for more detailed information, written by Tom Lane <tgl@sss.pgh.pa.us>.
- Please read item 19 in part 1 first.
-
- JPEG works on either full-color or gray-scale images; it does not handle
- bilevel (black and white) images, at least not well. It doesn't handle
- colormapped images either; you have to pre-expand those into an unmapped
- full-color representation. JPEG works best on "continuous tone" images.
- Images with many sudden jumps in color values will not compress well.
-
- There are a lot of parameters to the JPEG compression process. By adjusting
- the parameters, you can trade off compressed image size against reconstructed
- image quality over a *very* wide range. You can get image quality ranging
- from op-art (at 100x smaller than the original 24-bit image) to quite
- indistinguishable from the source (at about 3x smaller). Usually the
- threshold of visible difference from the source image is somewhere around 10x
- to 20x smaller than the original, ie, 1 to 2 bits per pixel for color images.
- Grayscale images do not compress as much. In fact, for comparable visual
- quality, a grayscale image needs perhaps 25% less space than a color image;
- certainly not the 66% less that you might naively expect.
-
- JPEG defines a "baseline" lossy algorithm, plus optional extensions for
- progressive and hierarchical coding. There is also a separate lossless
- compression mode; this typically gives about 2:1 compression, ie, about 12
- bits per color pixel. Most currently available JPEG hardware and software
- handles only the baseline mode.
-
-
- Here's the outline of the baseline compression algorithm:
-
- 1. Transform the image into a suitable color space. This is a no-op for
- grayscale, but for color images you generally want to transform RGB into a
- luminance/chrominance color space (YCbCr, YUV, etc). The luminance component
- is grayscale and the other two axes are color information. The reason for
- doing this is that you can afford to lose a lot more information in the
- chrominance components than you can in the luminance component: the human eye
- is not as sensitive to high-frequency chroma info as it is to high-frequency
- luminance. (See any TV system for precedents.) You don't have to change the
- color space if you don't want to, since the remainder of the algorithm works
- on each color component independently, and doesn't care just what the data
- is. However, compression will be less since you will have to code all the
- components at luminance quality. Note that colorspace transformation is
- slightly lossy due to roundoff error, but the amount of error is much smaller
- than what we typically introduce later on.
-
- 2. (Optional) Downsample each component by averaging together groups of
- pixels. The luminance component is left at full resolution, while the chroma
- components are often reduced 2:1 horizontally and either 2:1 or 1:1 (no
- change) vertically. In JPEG-speak these alternatives are usually called 2h2v
- and 2h1v sampling, but you may also see the terms "411" and "422" sampling.
- This step immediately reduces the data volume by one-half or one-third.
- In numerical terms it is highly lossy, but for most images it has almost no
- impact on perceived quality, because of the eye's poorer resolution for chroma
- info. Note that downsampling is not applicable to grayscale data; this is one
- reason color images are more compressible than grayscale.
-
- 3. Group the pixel values for each component into 8x8 blocks. Transform each
- 8x8 block through a discrete cosine transform (DCT). The DCT is a relative of
- the Fourier transform and likewise gives a frequency map, with 8x8 components.
- Thus you now have numbers representing the average value in each block and
- successively higher-frequency changes within the block. The motivation for
- doing this is that you can now throw away high-frequency information without
- affecting low-frequency information. (The DCT transform itself is reversible
- except for roundoff error.) See question 25 for fast DCT algorithms.
-
- 4. In each block, divide each of the 64 frequency components by a separate
- "quantization coefficient", and round the results to integers. This is the
- fundamental information-losing step. The larger the quantization
- coefficients, the more data is discarded. Note that even the minimum possible
- quantization coefficient, 1, loses some info, because the exact DCT outputs
- are typically not integers. Higher frequencies are always quantized less
- accurately (given larger coefficients) than lower, since they are less visible
- to the eye. Also, the luminance data is typically quantized more accurately
- than the chroma data, by using separate 64-element quantization tables.
- Tuning the quantization tables for best results is something of a black art,
- and is an active research area. Most existing encoders use simple linear
- scaling of the example tables given in the JPEG standard, using a single
- user-specified "quality" setting to determine the scaling multiplier. This
- works fairly well for midrange qualities (not too far from the sample tables
- themselves) but is quite nonoptimal at very high or low quality settings.
-
- 5. Encode the reduced coefficients using either Huffman or arithmetic coding.
- (Strictly speaking, baseline JPEG only allows Huffman coding; arithmetic
- coding is an optional extension.) Notice that this step is lossless, so it
- doesn't affect image quality. The arithmetic coding option uses Q-coding;
- it is identical to the coder used in JBIG (see question 74). Be aware that
- Q-coding is patented. Most existing implementations support only the Huffman
- mode, so as to avoid license fees. The arithmetic mode offers maybe 5 or 10%
- better compression, which isn't enough to justify paying fees.
-
- 6. Tack on appropriate headers, etc, and output the result. In a normal
- "interchange" JPEG file, all of the compression parameters are included
- in the headers so that the decompressor can reverse the process. These
- parameters include the quantization tables and the Huffman coding tables.
- For specialized applications, the spec permits those tables to be omitted
- from the file; this saves several hundred bytes of overhead, but it means
- that the decompressor must know a-priori what tables the compressor used.
- Omitting the tables is safe only in closed systems.
-
-
- The decompression algorithm reverses this process. The decompressor
- multiplies the reduced coefficients by the quantization table entries to
- produce approximate DCT coefficients. Since these are only approximate,
- the reconstructed pixel values are also approximate, but if the design
- has done what it's supposed to do, the errors won't be highly visible.
- A high-quality decompressor will typically add some smoothing steps to
- reduce pixel-to-pixel discontinuities.
-
- The JPEG standard does not specify the exact behavior of compressors and
- decompressors, so there's some room for creative implementation. In
- particular, implementations can trade off speed against image quality by
- choosing more accurate or faster-but-less-accurate approximations to the
- DCT. Similar tradeoffs exist for the downsampling/upsampling and colorspace
- conversion steps. (The spec does include some minimum accuracy requirements
- for the DCT step, but these are widely ignored, and are not too meaningful
- anyway in the absence of accuracy requirements for the other lossy steps.)
-
-
- Extensions:
-
- The progressive mode is intended to support real-time transmission of images.
- It allows the DCT coefficients to be sent piecemeal in multiple "scans" of
- the image. With each scan, the decoder can produce a higher-quality
- rendition of the image. Thus a low-quality preview can be sent very quickly,
- then refined as time allows. The total space needed is roughly the same as
- for a baseline JPEG image of the same final quality. (In fact, it can be
- somewhat *less* if a custom Huffman table is used for each scan, because the
- Huffman codes can be optimized over a smaller, more uniform population of
- data than appears in a baseline image's single scan.) The decoder must do
- essentially a full JPEG decode cycle for each scan: inverse DCT, upsample,
- and color conversion must all be done again, not to mention any color
- quantization for 8-bit displays. So this scheme is useful only with fast
- decoders or slow transmission lines. Up until 1995, progressive JPEG was a
- rare bird, but its use is now spreading as software decoders have become fast
- enough to make it useful with modem-speed data transmission.
-
- The hierarchical mode represents an image at multiple resolutions. For
- example, one could provide 512x512, 1024x1024, and 2048x2048 versions of the
- image. The higher-resolution images are coded as differences from the next
- smaller image, and thus require many fewer bits than they would if stored
- independently. (However, the total number of bits will be greater than that
- needed to store just the highest-resolution frame in baseline form.)
- The individual frames in a hierarchical sequence can be coded progressively
- if desired. Hierarchical mode is not widely supported at present.
-
- Part 3 of the JPEG standard, approved at the end of 1995, introduces several
- new extensions. The one most likely to become popular is variable
- quantization, which allows the quantization table to be scaled to different
- levels in different parts of the image. In this way the "more critical"
- parts of the image can be coded at higher quality than the "less critical"
- parts. A signaling code can be inserted at any DCT block boundary to set a
- new scaling factor.
-
- Another Part 3 extension is selective refinement. This feature permits a
- scan in a progressive sequence, or a refinement frame of a hierarchical
- sequence, to cover only part of the total image area. This is an
- alternative way of solving the variable-quality problem. My (tgl's) guess
- is that this will not get widely implemented, with variable quantization
- proving a more popular approach, but I've been wrong before.
-
- The third major extension added by Part 3 is a "tiling" concept that allows
- an image to be built up as a composite of JPEG frames, which may have
- different sizes, resolutions, quality settings, even colorspaces. (For
- example, a color image that occupies a small part of a mostly-grayscale page
- could be represented as a separate frame, without having to store the whole
- page in color.) Again, there's some overlap in functionality with variable
- quantization and selective refinement. The general case of arbitrary tiles
- is rather complex and is unlikely to be widely implemented. In the simplest
- case all the tiles are the same size and use similar quality settings.
- This case may become popular even if the general tiling mechanism doesn't,
- because it surmounts the 64K-pixel-on-a-side image size limitation that was
- (not very foresightedly) built into the basic JPEG standard. The individual
- frames are still restricted to 64K for compatibility reasons, but the total
- size of a tiled JPEG image can be up to 2^32 pixels on a side.
-
- Lossless JPEG:
-
- The separate lossless mode does not use DCT, since roundoff errors prevent a
- DCT calculation from being lossless. For the same reason, one would not
- normally use colorspace conversion or downsampling, although these are
- permitted by the standard. The lossless mode simply codes the difference
- between each pixel and the "predicted" value for the pixel. The predicted
- value is a simple function of the already-transmitted pixels just above and
- to the left of the current one (for example, their average; 8 different
- predictor functions are permitted). The sequence of differences is encoded
- using the same back end (Huffman or arithmetic) used in the lossy mode.
-
- Lossless JPEG with the Huffman back end is certainly not a state-of-the-art
- lossless compression method, and wasn't even when it was introduced. The
- arithmetic-coding back end may make it competitive, but you're probably best
- off looking at other methods if you need only lossless compression.
-
- The main reason for providing a lossless option is that it makes a good
- adjunct to the hierarchical mode: the final scan in a hierarchical sequence
- can be a lossless coding of the remaining differences, to achieve overall
- losslessness. This isn't quite as useful as it may at first appear, because
- exact losslessness is not guaranteed unless the encoder and decoder have
- identical IDCT implementations (ie, identical roundoff errors). And you
- can't use downsampling or colorspace conversion either if you want true
- losslessness. But in some applications the combination is useful.
-
-
- References:
-
- For a good technical introduction to JPEG, see:
- Wallace, Gregory K. "The JPEG Still Picture Compression Standard",
- Communications of the ACM, April 1991 (vol. 34 no. 4), pp. 30-44.
- (Adjacent articles in that issue discuss MPEG motion picture compression,
- applications of JPEG, and related topics.) If you don't have the CACM issue
- handy, a PostScript file containing a revised version of this article is
- available at ftp://ftp.uu.net/graphics/jpeg/wallace.ps.gz. This file
- (actually a preprint for a later article in IEEE Trans. Consum. Elect.)
- omits the sample images that appeared in CACM, but it includes corrections
- and some added material. Note: the Wallace article is copyright ACM and
- IEEE, and it may not be used for commercial purposes.
-
- An alternative, more leisurely explanation of JPEG can be found in "The Data
- Compression Book" by Mark Nelson ([Nel 1991], see question 7). This book
- provides excellent introductions to many data compression methods including
- JPEG, plus sample source code in C. The JPEG-related source code is far from
- industrial-strength, but it's a pretty good learning tool.
-
- An excellent textbook about JPEG is "JPEG Still Image Data Compression
- Standard" by William B. Pennebaker and Joan L. Mitchell. Published by Van
- Nostrand Reinhold, 1993, ISBN 0-442-01272-1. 650 pages, price US$59.95.
- (VNR will accept credit card orders at 800/842-3636, or get your local
- bookstore to order it.) This book includes the complete text of the ISO
- JPEG standards, DIS 10918-1 and draft DIS 10918-2. Review by Tom Lane:
- "This is by far the most complete exposition of JPEG in existence. It's
- written by two people who know what they are talking about: both served on
- the ISO JPEG standards committee. If you want to know how JPEG works or
- why it works that way, this is the book to have."
-
- There are a number of errors in the first printing of the Pennebaker and
- Mitchell book. An errata list is available at
- ftp://ftp.uu.net/graphics/jpeg/pm.errata.gz. At last report, all known
- errors were fixed in the second printing.
-
- The official specification of JPEG is not currently available on-line, and
- is not likely ever to be available for free because of ISO and ITU copyright
- restrictions. You can order it from your national standards agency as ISO
- standards IS 10918-1, 10918-2, 10918-3, or as ITU-T standards T.81, T.83,
- T.84. See ftp://ftp.uu.net/graphics/jpeg/jpeg.documents.gz for more info.
- NOTE: buying the Pennebaker and Mitchell textbook is a much better deal
- than purchasing the standard directly: it's cheaper and includes a lot of
- useful explanatory material along with the full draft text of the spec.
- The book unfortunately doesn't include Part 3 of the spec, but if you need
- Part 3, buy the book and just that part and you'll still be ahead.
-
-
- ------------------------------------------------------------------------------
-
- Subject: [76] What is Vector Quantization?
-
- Some vector quantization software for data analysis that is available
- in the ftp://cochlea.hut.fi/pub/ directory. One package is lvq_pak and
- one is som_pak (som_pak generates Kohonen maps of data using lvq to
- cluster it).
-
- A VQ-based codec that is based on the Predictive Residual Vector
- Quantization is in ftp://mozart.eng.buffalo.edu/pub/prvq_codec/PRVQ.tar.gz
-
- VQ software is also available in ftp://isdl.ee.washington.edu/pub/VQ/
-
-
- For a book on Vector Quantization, see the reference (Gersho and Gray)
- given in item 7 of this FAQ. For a review article: N. M. Nasrabadi and
- R. A. King, "Image Coding Using Vector Quantization: A review",
- IEEE Trans. on Communications, vol. COM-36, pp. 957-971, Aug. 1988.
-
-
- A short introduction to Vector Quantization, written by Alex Zatsman
- <alex.zatsman@analog.com>:
-
- In Scalar Quantization one represents the values by fixed subset of
- representative values. For examples, if you have 16 bit values and
- send only 8 most signifcant bits, you get an approximation of the
- original data at the expense of precision. In this case the fixed
- subset is all the 16-bit numbers divisable by 256, i.e 0, 256, 512,...
-
- In Vector Quantization you represent not individual values but
- (usually small) arrays of them. A typical example is a color map: a
- color picture can be represented by a 2D array of triplets (RGB
- values). In most pictures those triplets do not cover the whole RGB
- space but tend to concetrate in certain areas. For example, the
- picture of a forest will typically have a lot of green. One can select
- a relatively small subset (typically 256 elements) of representative
- colors, i.e RGB triplets, and then approximate each triplet by the
- representative of that small set. In case of 256 one can use 1 byte
- instead of 3 for each pixel.
-
- One can do the same for any large data sets, especialy when
- consecutive points are correlated in some way. CELP speech compression
- algorithms use those subsets "codebooks" and use them to quantize
- exciation vectors for linear prediction -- hence the name CELP which
- stands for Codebook Excited Linear Prediction. (See item 26 in part 1
- of this FAQ for more information about CELP.)
-
- Note that Vector Quantization, just like Scalar Quantization, is a lossy
- compression.
-
- ------------------------------------------------------------------------------
-
- Subject: [77] Introduction to Fractal compression (long)
-
-
- Written by John Kominek <kominek@links.uwaterloo.ca>
-
- Seven things you should know about Fractal Image Compression (assuming that
- you want to know about it).
-
- 1. It is a promising new technology, arguably superior to JPEG --
- but only with an argument.
- 2. It is a lossy compression method.
- 3. The fractals in Fractal Image Compression are Iterated Function
- Systems.
- 4. It is a form of Vector Quantization, one that employs a virtual
- codebook.
- 5. Resolution enhancement is a powerful feature but is not some
- magical way of achieving 1000:1 compression.
- 6. Compression is slow, decompression is fast.
- 7. The technology is patented.
-
- That's the scoop in condensed form. Now to elaborate, beginning with a little
- background.
-
-
- A Brief History of Fractal Image Compression
- --------------------------------------------
-
- The birth of fractal geometry (or rebirth, rather) is usually traced to IBM
- mathematician Benoit B. Mandelbrot and the 1977 publication of his seminal
- book The Fractal Geometry of Nature. The book put forth a powerful thesis:
- traditional geometry with its straight lines and smooth surfaces does not
- resemble the geometry of trees and clouds and mountains. Fractal geometry,
- with its convoluted coastlines and detail ad infinitum, does.
-
- This insight opened vast possibilities. Computer scientists, for one, found a
- mathematics capable of generating artificial and yet realistic looking land-
- scapes, and the trees that sprout from the soil. And mathematicians had at
- their disposal a new world of geometric entities.
-
- It was not long before mathematicians asked if there was a unity among this
- diversity. There is, as John Hutchinson demonstrated in 1981, it is the branch
- of mathematics now known as Iterated Function Theory. Later in the decade
- Michael Barnsley, a leading researcher from Georgia Tech, wrote the popular
- book Fractals Everywhere. The book presents the mathematics of Iterated Func-
- tions Systems (IFS), and proves a result known as the Collage Theorem. The
- Collage Theorem states what an Iterated Function System must be like in order
- to represent an image.
-
- This presented an intriguing possibility. If, in the forward direction, frac-
- tal mathematics is good for generating natural looking images, then, in the
- reverse direction, could it not serve to compress images? Going from a given
- image to an Iterated Function System that can generate the original (or at
- least closely resemble it), is known as the inverse problem. This problem
- remains unsolved.
-
- Barnsley, however, armed with his Collage Theorem, thought he had it solved.
- He applied for and was granted a software patent and left academia to found
- Iterated Systems Incorporated (US patent 4,941,193. Alan Sloan is the co-
- grantee of the patent and co-founder of Iterated Systems.) Barnsley announced
- his success to the world in the January 1988 issue of BYTE magazine. This
- article did not address the inverse problem but it did exhibit several images
- purportedly compressed in excess of 10,000:1. Alas, it was not a breakthrough.
- The images were given suggestive names such as "Black Forest" and "Monterey
- Coast" and "Bolivian Girl" but they were all manually constructed. Barnsley's
- patent has come to be derisively referred to as the "graduate student algo-
- rithm."
-
- Graduate Student Algorithm
- o Acquire a graduate student.
- o Give the student a picture.
- o And a room with a graphics workstation.
- o Lock the door.
- o Wait until the student has reverse engineered the picture.
- o Open the door.
-
- Attempts to automate this process have met little success. As Barnsley admit-
- ted in 1988: "Complex color images require about 100 hours each to encode and
- 30 minutes to decode on the Masscomp [dual processor workstation]." That's 100
- hours with a _person_ guiding the process.
-
- Ironically, it was one of Barnsley's PhD students that made the graduate
- student algorithm obsolete. In March 1988, according to Barnsley, he arrived
- at a modified scheme for representing images called Partitioned Iterated
- Function Systems (PIFS). Barnsley applied for and was granted a second patent
- on an algorithm that can automatically convert an image into a Partitioned
- Iterated Function System, compressing the image in the process. (US patent
- 5,065,447. Granted on Nov. 12 1991.) For his PhD thesis, Arnaud Jacquin imple-
- mented the algorithm in software, a description of which appears in his land-
- mark paper "Image Coding Based on a Fractal Theory of Iterated Contractive
- Image Transformations." The algorithm was not sophisticated, and not speedy,
- but it was fully automatic. This came at price: gone was the promise of
- 10,000:1 compression. A 24-bit color image could typically be compressed from
- 8:1 to 50:1 while still looking "pretty good." Nonetheless, all contemporary
- fractal image compression programs are based upon Jacquin's paper.
-
- That is not to say there are many fractal compression programs available.
- There are not. Iterated Systems sell the only commercial compressor/decompres-
- sor, an MS-Windows program called "Images Incorporated." There are also an
- increasing number of academic programs being made freely available. Unfor-
- tunately, these programs are -- how should I put it? -- of merely academic
- quality.
-
- This scarcity has much to do with Iterated Systems' tight lipped policy about
- their compression technology. They do, however, sell a Windows DLL for pro-
- grammers. In conjunction with independent development by researchers else-
- where, therefore, fractal compression will gradually become more pervasive.
- Whether it becomes all-pervasive remains to be seen.
-
- Historical Highlights:
- 1977 -- Benoit Mandelbrot finishes the first edition of The Fractal
- Geometry of Nature.
- 1981 -- John Hutchinson publishes "Fractals and Self-Similarity."
- 1983 -- Revised edition of The Fractal Geometry of Nature is
- published.
- 1985 -- Michael Barnsley and Stephen Demko introduce Iterated
- Function Theory in "Iterated Function Systems and the Global
- Construction of Fractals."
- 1987 -- Iterated Systems Incorporated is founded.
- 1988 -- Barnsley publishes the book Fractals Everywhere.
- 1990 -- Barnsley's first patent is granted.
- 1991 -- Barnsley's second patent is granted.
- 1992 -- Arnaud Jacquin publishes an article that describes the first
- practical fractal image compression method.
- 1993 -- The book Fractal Image Compression by Michael Barnsley and Lyman
- Hurd is published.
- -- The Iterated Systems' product line matures.
- 1994 -- Put your name here.
-
-
- On the Inside
- -------------
-
- The fractals that lurk within fractal image compression are not those of the
- complex plane (Mandelbrot Set, Julia sets), but of Iterated Function Theory.
- When lecturing to lay audiences, the mathematician Heinz-Otto Peitgen intro-
- duces the notion of Iterated Function Systems with the alluring metaphor of a
- Multiple Reduction Copying Machine. A MRCM is imagined to be a regular copying
- machine except that:
-
- 1. There are multiple lens arrangements to create multiple overlapping
- copies of the original.
- 2. Each lens arrangement reduces the size of the original.
- 3. The copier operates in a feedback loop, with the output of one
- stage the input to the next. The initial input may be anything.
-
- The first point is what makes an IFS a system. The third is what makes it
- iterative. As for the second, it is implicitly understood that the functions
- of an Iterated Function Systems are contractive.
-
- An IFS, then, is a set of contractive transformations that map from a defined
- rectangle of the real plane to smaller portions of that rectangle. Almost
- invariably, affine transformations are used. Affine transformations act to
- translate, scale, shear, and rotate points in the plane. Here is a simple
- example:
-
-
- |---------------| |-----|
- |x | |1 |
- | | | |
- | | |---------------|
- | | |2 |3 |
- | | | | |
- |---------------| |---------------|
-
- Before After
-
- Figure 1. IFS for generating Sierpinski's Triangle.
-
- This IFS contains three component transformations (three separate lens ar-
- rangements in the MRCM metaphor). Each one shrinks the original by a factor of
- 2, and then translates the result to a new location. It may optionally scale
- and shift the luminance values of the rectangle, in a manner similar to the
- contrast and brightness knobs on a TV.
-
- The amazing property of an IFS is that when the set is evaluated by iteration,
- (i.e. when the copy machine is run), a unique image emerges. This latent image
- is called the fixed point or attractor of the IFS. As guaranteed by a result
- known as the Contraction Theorem, it is completely independent of the initial
- image. Two famous examples are Sierpinski's Triangle and Barnsley's Fern.
- Because these IFSs are contractive, self-similar detail is created at every
- resolution down to the infinitesimal. That is why the images are fractal.
-
- The promise of using fractals for image encoding rests on two suppositions: 1.
- many natural scenes possess this detail within detail structure (e.g. clouds),
- and 2. an IFS can be found that generates a close approximation of a scene
- using only a few transformations. Barnsley's fern, for example, needs but
- four. Because only a few numbers are required to describe each transformation,
- an image can be represented very compactly. Given an image to encode, finding
- the optimal IFS from all those possible is known as the inverse problem.
-
- The inverse problem -- as mentioned above -- remains unsolved. Even if it
- were, it may be to no avail. Everyday scenes are very diverse in subject
- matter; on whole, they do not obey fractal geometry. Real ferns do not branch
- down to infinity. They are distorted, discolored, perforated and torn. And the
- ground on which they grow looks very much different.
-
- To capture the diversity of real images, then, Partitioned IFSs are employed.
- In a PIFS, the transformations do not map from the whole image to the parts,
- but from larger parts to smaller parts. An image may vary qualitatively from
- one area to the next (e.g. clouds then sky then clouds again). A PIFS relates
- those areas of the original image that are similar in appearance. Using Jac-
- quin's notation, the big areas are called domain blocks and the small areas
- are called range blocks. It is necessary that every pixel of the original
- image belong to (at least) one range block. The pattern of range blocks is
- called the partitioning of an image.
-
- Because this system of mappings is still contractive, when iterated it will
- quickly converge to its latent fixed point image. Constructing a PIFS amounts
- to pairing each range block to the domain block that it most closely resembles
- under some to-be-determined affine transformation. Done properly, the PIFS
- encoding of an image will be much smaller than the original, while still
- resembling it closely.
-
- Therefore, a fractal compressed image is an encoding that describes:
- 1. The grid partitioning (the range blocks).
- 2. The affine transforms (one per range block).
-
- The decompression process begins with a flat gray background. Then the set of
- transformations is repeatedly applied. After about four iterations the attrac-
- tor stabilizes. The result will not (usually) be an exact replica of the
- original, but reasonably close.
-
-
- Scalelessnes and Resolution Enhancement
- ---------------------------------------
-
- When an image is captured by an acquisition device, such as a camera or scan-
- ner, it acquires a scale determined by the sampling resolution of that device.
- If software is used to zoom in on the image, beyond a certain point you don't
- see additional detail, just bigger pixels.
-
- A fractal image is different. Because the affine transformations are spatially
- contractive, detail is created at finer and finer resolutions with each itera-
- tion. In the limit, self-similar detail is created at all levels of resolu-
- tion, down the infinitesimal. Because there is no level that 'bottoms out'
- fractal images are considered to be scaleless.
-
- What this means in practice is that as you zoom in on a fractal image, it will
- still look 'as it should' without the staircase effect of pixel replication.
- The significance of this is cause of some misconception, so here is the right
- spot for a public service announcement.
-
- /--- READER BEWARE ---\
-
- Iterated Systems is fond of the following argument. Take a portrait that is,
- let us say, a grayscale image 250x250 pixels in size, 1 byte per pixel. You
- run it through their software and get a 2500 byte file (compression ratio =
- 25:1). Now zoom in on the person's hair at 4x magnification. What do you see?
- A texture that still looks like hair. Well then, it's as if you had an image
- 1000x1000 pixels in size. So your _effective_ compression ratio is 25x16=400.
-
- But there is a catch. Detail has not been retained, but generated. With a
- little luck it will look as it should, but don't count on it. Zooming in on a
- person's face will not reveal the pores.
-
- Objectively, what fractal image compression offers is an advanced form of
- interpolation. This is a useful and attractive property. Useful to graphic
- artists, for example, or for printing on a high resolution device. But it does
- not bestow fantastically high compression ratios.
-
- \--- READER BEWARE ---/
-
- That said, what is resolution enhancement? It is the process of compressing an
- image, expanding it to a higher resolution, saving it, then discarding the
- iterated function system. In other words, the compressed fractal image is the
- means to an end, not the end itself.
-
-
- The Speed Problem
- -----------------
-
- The essence of the compression process is the pairing of each range block to a
- domain block such that the difference between the two, under an affine trans-
- formation, is minimal. This involves a lot of searching.
-
- In fact, there is nothing that says the blocks have to be squares or even
- rectangles. That is just an imposition made to keep the problem tractable.
-
- More generally, the method of finding a good PIFS for any given image involves
- five main issues:
- 1. Partitioning the image into range blocks.
- 2. Forming the set of domain blocks.
- 3. Choosing type of transformations that will be considered.
- 4. Selecting a distance metric between blocks.
- 5. Specifying a method for pairing range blocks to domain blocks.
-
- Many possibilities exist for each of these. The choices that Jacquin offered
- in his paper are:
- 1. A two-level regular square grid with 8x8 pixels for the large
- range blocks and 4x4 for the small ones.
- 2. Domain blocks are 16x16 and 8x8 pixels in size with a subsampling
- step size of four. The 8 isometric symmetries (four rotations,
- four mirror flips) expand the domain pool to a virtual domain
- pool eight times larger.
- 3. The choices in the last point imply a shrinkage by two in each
- direction, with a possible rotation or flip, and then a trans-
- lation in the image plane.
- 4. Mean squared error is used.
- 5. The blocks are categorized as of type smooth, midrange, simple
- edge, and complex edge. For a given range block the respective
- category is searched for the best match.
-
- The importance of categorization can be seen by calculating the size of the
- total domain pool. Suppose the image is partitioned into 4x4 range blocks. A
- 256x256 image contains a total of (256-8+1)^2 = 62,001 different 8x8 domain
- blocks. Including the 8 isometric symmetries increases this total to 496,008.
- There are (256-4+1)^2 = 64,009 4x4 range blocks, which makes for a maximum of
- 31,748,976,072 possible pairings to test. Even on a fast workstation an ex-
- haustive search is prohibitively slow. You can start the program before de-
- parting work Friday afternoon; Monday morning, it will still be churning away.
-
- Increasing the search speed is the main challenge facing fractal image com-
- pression.
-
-
- Similarity to Vector Quantization
- ---------------------------------
-
- To the VQ community, a "vector" is a small rectangular block of pixels. The
- premise of vector quantization is that some patterns occur much more frequent-
- ly than others. So the clever idea is to store only a few of these common
- patterns in a separate file called the codebook. Some codebook vectors are
- flat, some are sloping, some contain tight texture, some sharp edges, and so
- on -- there is a whole corpus on how to construct a codebook. Each codebook
- entry (each domain block) is assigned an index number. A given image, then, is
- partitioned into a regular grid array. Each grid element (each range block) is
- represented by an index into the codebook. Decompressing a VQ file involves
- assembling an image out of the codebook entries. Brick by brick, so to speak.
-
- The similarity to fractal image compression is apparent, with some notable
- differences.
- 1. In VQ the range blocks and domain blocks are the same size; in an
- IFS the domain blocks are always larger.
- 2. In VQ the domain blocks are copied straight; in an IFS each domain
- block undergoes a luminance scaling and offset.
- 3. In VQ the codebook is stored apart from the image being coded; in
- an IFS the codebook is not explicitly stored. It is comprised of
- portions of the attractor as it emerges during iteration. For that
- reason it is called a "virtual codebook." It has no existence
- independent of the affine transformations that define an IFS.
- 4. In VQ the codebook is shared among many images; in an IFS the
- virtual codebook is specific to each image.
-
- There is a more refined version of VQ called gain-shape vector quantization in
- which a luminance scaling and offset is also allowed. This makes the similari-
- ty to fractal image compression as close as can be.
-
-
- Compression Ratios
- ------------------
-
- Exaggerated claims not withstanding, compression ratios typically range from
- 4:1 to 100:1. All other things equal, color images can be compressed to a
- greater extent than grayscale images.
-
- The size of a fractal image file is largely determined by the number of trans-
- formations of the PIFS. For the sake of simplicity, and for the sake of com-
- parison to JPEG, assume that a 256x256x8 image is partitioned into a regular
- partitioning of 8x8 blocks. There are 1024 range blocks and thus 1024 trans-
- formations to store. How many bits are required for each?
-
- In most implementations the domain blocks are twice the size of the range
- blocks. So the spatial contraction is constant and can be hard coded into the
- decompression program. What needs to be stored are:
-
- x position of domain block 8 6
- y position of domain block 8 6
- luminance scaling 8 5
- luminance offset 8 6
- symmetry indicator 3 3
- -- --
- 35 26 bits
-
- In the first scheme, a byte is allocated to each number except for the symme-
- try indicator. The upper bound on the compression ratio is thus (8x8x8)/35 =
- 14.63. In the second scheme, domain blocks are restricted to coordinates
- modulo 4. Plus, experiments have revealed that 5 bits per scale factor and 6
- bits per offset still give good visual results. So the compression ratio limit
- is now 19.69. Respectable but not outstanding.
-
- There are other, more complicated, schemes to reduce the bit rate further. The
- most common is to use a three or four level quadtree structure for the range
- partitioning. That way, smooth areas can be represented with large range
- blocks (high compression), while smaller blocks are used as necessary to
- capture the details. In addition, entropy coding can be applied as a back-end
- step to gain an extra 20% or so.
-
-
- Quality: Fractal vs. JPEG
- -------------------------
-
- The greatest irony of the coding community is that great pains are taken to
- precisely measure and quantify the error present in a compressed image, and
- great effort is expended toward minimizing an error measure that most often is
- -- let us be gentle -- of dubious value. These measure include signal-to-noise
- ratio, root mean square error, and mean absolute error. A simple example is
- systematic shift: add a value of 10 to every pixel. Standard error measures
- indicate a large distortion, but the image has merely been brightened.
-
- With respect to those dubious error measures, and at the risk of over-sim-
- plification, the results of tests reveal the following: for low compression
- ratios JPEG is better, for high compression ratios fractal encoding is better.
- The crossover point varies but is often around 40:1. This figure bodes well
- for JPEG since beyond the crossover point images are so severely distorted
- that they are seldom worth using.
-
- Proponents of fractal compression counter that signal-to-noise is not a good
- error measure and that the distortions present are much more 'natural looking'
- than the blockiness of JPEG, at both low and high bit rates. This is a valid
- point but is by no means universally accepted.
-
- What the coding community desperately needs is an easy to compute error meas-
- ure that accurately captures subjective impression of human viewers. Until
- then, your eyes are the best judge.
-
-
- Finding Out More
- ----------------
-
- Please refer to item 17 in part 1 of this FAQ for a list of references,
- available software, and ftp sites concerning fractal compression.
-
- ------------------------------------------------------------------------------
-
- Subject: [78] The Burrows-Wheeler block sorting algorithm (long)
-
-
- A high-quality implementation of the Burrows-Wheeler
- block-sorting-based lossless compression algorithm is available at
- http://www.cs.man.ac.uk/arch/people/j-seward/bzip-0.15.tar.gz
-
- Mark Nelson wrote an excellent article "Data Compression with the
- Burrows-Wheeler Transform" for Dr. Dobb's Journal, September 1996. A copy
- of the article is at http://web2.airmail.net/markn/articles/bwt/bwt.htm
-
- Another introduction written by Sampo Syreeni <tmaaedu@nexus.edu.lahti.fi>:
-
- The Burrows-Wheeler block sorting compression algorithm is described in
- "A Block-sorting Lossless Data Compression Algorithm" by M. Burrows and D.J.
- Wheeler, dated in May 10, 1994. A postscript copy of this paper has been made
- available by Digital on the Systems Research Center (SRC) FTP site at
- ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
-
- The method was originally discovered by one of the authors (Wheeler) back
- in 1983, but has not been published before. As such, the method is fairly new
- and hasn't gained popularity. Digital also holds the copyrights (and patents?)
- to the method, so it isn't public domain.
-
- The method described in the original paper is really a composite of three
- different algorithms: the block sorting main engine (a lossless, very slightly
- expansive preprocessor), the move-to-front coder (a byte-for-byte simple,
- fast, locally adaptive noncompressive coder) and a simple statistical
- compressor (first order Huffman is mentioned as a candidate) eventually doing
- the compression. Of these three methods only the first two are discussed here
- as they are what constitutes the heart of the algorithm. These two algorithms
- combined form a completely reversible (lossless) transformation that - with
- typical input - skews the first order symbol distributions to make the data
- more compressible with simple methods. Intuitively speaking, the method
- transforms slack in the higher order probabilities of the input block (thus
- making them more even, whitening them) to slack in the lower order statistics.
- This effect is what is seen in the histogram of the resulting symbol data.
-
- The block sorting preprocessor operates purely on a block basis. One way
- to understand the idea is to think of the input block arranged as a circular
- array where, for every symbol, the succeeding symbols are used as a predictor.
- This predictor is then used to group the symbols with similar right neighbors
- together. This predictor is realized (conceptually) as a two phase process.
- The first phase forms all cyclic shifts of the input block whose size is
- usually a power of two. Note here that the original string is always present
- intact on some row of the resulting matrix. If the block length is n then
- there exist n unique rotations of the original string (to the left). These
- rotations are now viewed as the rows of an N x N matrix of symbols. The second
- phase consists of sorting this resulting conceptual matrix. This phase results
- in the rows coming into order based on their first few symbols. If there is
- some commonly repeated string in the input block (the original paper gives
- "the" as an example), the sorting phase brings all those rotations that have a
- part of this string as the row start very close to each other. The preceding
- symbol in this common string is then found in the last column of the sorted
- matrix. This way common strings result in short bursts of just a few distinct
- characters being formed in the last column of the matrix. The last column is
- what is then output from the second phase. One further bit of information is
- derived from the input data. This is an integer with enough bits to tell the
- size of the input string (that is, log_2(n)). The number is used to note the
- row position into which the original input block got in the sorting algorithm.
- This integer always results in expansion of the data, but is necessary for us
- to be able successfully decompress the string. The absolute amount of overhead
- increases as the logarithm of the input block size so its percentage of the
- output data becomes negligible with useful block sizes anyway.
-
- The characteristics of the transformation process make the output from the
- sort ideal for certain kinds of further manipulation. The extreme local
- fluctuations in the first order statistics of the output string lead one to
- use a transformation that boosts and flattens the local fluttering of the
- statistics. The best example (and, of course, the one given in the original
- paper) is move-to-front coding. This coder codes a symbol as the number of
- distinct symbols seen since the symbol's last occurrence. Basically this means
- that the coder outputs the index of an input symbol in a dynamic LIFO stack
- and then updates the stack by moving the symbol to the top. This is easy and
- efficient to implement and results in fast local adaptation. As just a few
- common symbols will (locally) govern the input to the coder, these symbols
- will be kept on the top of the stack and thus the output will mainly consist
- of low numbers. This makes it highly susceptible to first order statistical
- compression methods which are, in case, easy and efficient to implement.
-
- The transform matrix described above would require enormous amounts of
- storage space and would not result in a usable algorithm as such. The method
- can, however, be realized very efficiently by suffix and quick sort methods.
- Thus the whole transformation together with the eventual simple compression
- engine is extremely fast but still achieves impressive compression on typical
- input data. When implemented well, the speeds achieved can be in the order of
- pure LZ and the compression ratios can still approach state-of-the-art Markov
- modeling coders. The engine also responds well to increasing block sizes -
- the longer the input block, the more space there is for the patterns to form
- and the more similar input strings there will be in it. This results in almost
- monotonously increasing compression ratios even as the block length goes well
- into the megabyte range.
- The decompression cascade is basically just the compression cascade
- backwards. More logic is needed to reverse the main sorting stage, however.
- This logic involves reasoning around the order of the first the last column of
- the conceptual coding matrix. The reader is referred to the original paper for
- an in depth treatment of the subject. The original paper also contains a more
- thorough discussion of why the method works and how to implement it.
-
- And now a little demonstration. The original block to be compressed is
- chosen to be the (rather pathological) string "good, jolly good". This was
- taken as an example because it has high redundancy and it is exactly 16 bytes
- long. The first picture shows the cyclic shifts (rotations) of the input
- string. The second shows the matrix after sorting. Note that the last column
- now has many double characters in it. Note also that the original string has
- been placed into the 6th row now. The third picture shows the output for this
- input block. The index integer has been packed to a full byte although 4 bits
- would suffice in this case (log_2(16)=4). The fourth and fifth pictures show
- the transformed string after move-to-front-coding. The sixth picture shows the
- statistical distribution of the characters in the output string. Notice the
- disproportionately large amount of ones and zeros, even with a very short
- string like this. This is the output that is then routed through the simple
- statistical encoder. It should compress very well, as the distribution of the
- characters in the input block is now very uneven.
-
-
- 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F
- ------------------------------- -------------------------------
- 0 | g o o d , j o l l y g o o d 0 | g o o d g o o d , j o l l y
- 1 | o o d , j o l l y g o o d g 1 | j o l l y g o o d g o o d ,
- 2 | o d , j o l l y g o o d g o 2 | , j o l l y g o o d g o o d
- 3 | d , j o l l y g o o d g o o 3 | d , j o l l y g o o d g o o
- 4 | , j o l l y g o o d g o o d 4 | d g o o d , j o l l y g o o
- 5 | j o l l y g o o d g o o d , 5 | g o o d , j o l l y g o o d
- 6 | j o l l y g o o d g o o d , 6 | g o o d g o o d , j o l l y
- 7 | o l l y g o o d g o o d , j 7 | j o l l y g o o d g o o d ,
- 8 | l l y g o o d g o o d , j o 8 | l l y g o o d g o o d , j o
- 9 | l y g o o d g o o d , j o l 9 | l y g o o d g o o d , j o l
- A | y g o o d g o o d , j o l l A | o d , j o l l y g o o d g o
- B | g o o d g o o d , j o l l y B | o d g o o d , j o l l y g o
- C | g o o d g o o d , j o l l y C | o l l y g o o d g o o d , j
- D | o o d g o o d , j o l l y g D | o o d , j o l l y g o o d g
- E | o d g o o d , j o l l y g o E | o o d g o o d , j o l l y g
- F | d g o o d , j o l l y g o o F | y g o o d g o o d , j o l l
-
- 1. The shifts 2. In lexicographic order
-
-
- 121,45,102,114,0,1,36,0,
- "y,dood oloojggl",5 1,113,1,0,112,110,0,3,5
-
- 3. The output from block sort 4. After move-to-front-coding
-
-
- 00: 4; 01: 3; 03: 1; 05: 1;
- 79,2D,66,72,0,1,24,0, 24: 1; 2D: 1; 66: 1; 6E: 1;
- 1,71,1,0,70,6E,0,3,5 70: 1; 71: 1; 72: 1; 79: 1
-
- 5. In hexadecimal 6. The statistics
-
- ------------------------------------------------------------------------------
-
- End of part 2 of the comp.compression faq.
-
-
- Part 3: (Long) list of image compression hardware
-
- [85] Image compression hardware
- [99] Acknowledgments
-
-
- Search for "Subject: [#]" to get to question number # quickly. Some news
- readers can also take advantage of the message digest format used here.
-
- ------------------------------------------------------------------------------
-
- Subject: [85] Image compression hardware
-
- Here is a list of sources of image compression hardware (JPEG, MPEG,
- H.261 and others), reposted with the author's permission. The list is
- certainly dated already, but it is a good starting point for
- seeking compression chips. (Please send corrections/additions to
- gzip@prep.ai.mit.edu). References are taken from:
-
- VIDEO COMPRESSION OPTIONS, IEEE CICC 6-May-92
- John J. Bloomer, jbloomer@crd.ge.com, Fathy F. Yassa, Aiman A. Abdel-Malek
- General Electric Corporate R&D, KWC317 Signals and Systems Laboratory
- PO Box 8, Schenectady NY, 12301
-
- (Too many people have sent comments, corrections or additions so I am
- just making a common acknowledgment here.)
-
- [Check also:
- http://www.dspnet.com/ Tech-Online's catalog
- http://www.c-cube.com/ C-Cube Microsystems
- http://datacompression.com/ DCP Research Corp
- http://www.ftelinc.com/ FutureTel
- ]
-
- Pipelined Processors, Building Blocks (Chip Sets)
- -------------------------------------------------
-
- STI3200, IMSA121, STI3208 - SGS-Thompson DCT processors. 602-867-6200
- - 3200 has multiple block size options, DC to 13.5 MHz
- - A121 8x8 fixed blocks, DC to 20MHz, add/sub loop, CCITT compatible
- - 3208 8x8 fixed blocks, DC to 40MHz, CCITT compatible at 20MHz
-
- STI3220 - SGS-Thompson motion estimator (H.261, MPEG). 602-867-6279
- - 8-bit input pixels, 4-bit H and V vectors out
- - adjustable block size matcher (8x8, 8x16, 16x16)
- - +7/-8 search window
- - 5V, 2W at 18MHz (max), 68 pin PLCC
-
- L64765 , L64735 , L64745 - 3-chip LSI Logic JPEG set.
- 408-433-8000, 800-433-8778
- - L64765 raster-to-block and color-space converter, jointly developed
- with Rapid Tech.
- - L64735 block DCT processor
- - L64745 JPEG coder support, stand-alone lossless DPCM codec, dynamic
- Huffman
- - 27 MB/s on CCIR601 frames
- - minimal support logic, color and gray scale
- - 68-pin PGA or PLCC, 27 and 20 MHz versions
-
- L647*0 and L6471* families - LSI Logic H.621/MPEG pieces. 408-433-8000
- - L64720 motion estimator, 30/40MHz, 8x8, 16x16 blocks, 32x32 or 16x16
- search window, 68-pin CPGA or PPGA
- - L64730 & 735 8x8 DCT processors (12 & 8-9 bits)
- - L64740 8x8 block quantization
- - L64760 intra/inter-frame coding decision
- - L64715 BCH error correction
- - L64750/L64751 variable length encode/decode (H.261-specific)
-
- ZR36020 and ZR36031 - Zoran DCT processor & quantization/encoding. 408-986-1314
- - JPEG-like scheme using 16-bit, two's complement fixed point
- arithmetic
- - includes bit-rate controls for constant # of pictures per card
- - 7.4 MHz, < 1W, 20mW in standby mode, 7.5 frames/s (f/s)
- - 36020 - 44-pin plastic quad flatpack (PQFP) or 48-pin ceramic DIP
- - 36031 - 100-pin PQFP or 85-pin PGA.
- - co-developments with Fuji Photo Film Co. Ltd. digital IC-card
- camera market
-
- Does 2-passes of image: generate histogram for optimum Huffman
- tables and quantization compute step size (ala H.261 and
- MPEG-I) for each macroblock or minimum coded unit (MCU).
-
- JPEG-compatible codec expected soon.
-
- LDM3104 - Olympus DCT coefficient encoder
- - constant rate, digital IC-card camera market
- - 750 mW, 25 mW standby, 100-poin QFP
-
- TMC2312 - TRW quantizer/Huffman encoder, TMC2313 Huffman decoder/dequantizer
-
- TMC2311 - TRW CMOS Fast Cosine Transform Processor.
- - 12 Bits, 15 M pixels/s
- - complies with the CCITT SGXV ( e.g. JPEG, H.261 and MPEG )
- - includes an adder-subtractor for linear predictive coding
-
- MN195901 - Matsushita Electric Industrial Co. See ISSCC 1992
- - 16-bit, 60 MIP video signal processor
- - 25 uS instruction processing
- - on-board DCT and absolute differencing
- - Philips Signetics US fab.
-
- HGCT - Ricoh CRC, Generalized Chen Transform demonstration chip.
- - 2D JPEG/MPEG/H.261 compatible DCT
- - includes quantization
- - 30MHz, 15K gates
- - licensing possible
-
- GCTX64000 - Graphic Communication Technology Corp. chipset
- - provides CCITT H.261
- - VLSI Technology and Hitachi supply H.261 codec core. 1 micron CMOS.
-
- BT - British Telecommunications plc., Martlesham labs designed
- - H.261 codec chipset, Motorola fab.
- - 13 chips total for codec.
-
-
- Pipelined Processors, Monolithic, Programmable
- ----------------------------------------------
-
- Vision Processor - Integrated Information Technology Inc. 408-727-1885
- - generic DCT, motion compensated & entropy coding codec
- - microcode for still- and motion-video compression (JPEG, H.261 and
- MPEG1)
- - 1 micron CMOS, 20 MHz and 33 MHz, PGA and 84-pin QFP
- - JPEG only and JPEG/H/261/MPEG versions available, H.261 at 30 f/s.
- - used by Compression Labs, Inc. CDV teleconferencing system
- - rumored to be the heart of the AT&T picture phone
-
- MN195901 - Matsushita Electric Industrial Corp
- - 40 MHz DSP, built-in DCT
- - 16-bit fixed-point
-
- AVP1000 - AT&T JPEG, MPEG and H.261 codec chipset. 800-372-2447
- - 1400D decoder, 1400C system controller
- - 1300E H.261 (CIF, QCIF, CIF240) at 30 f/s, I-frame only MPEG.
- - 1400E is superset of 1300E, motion with 1/2 pixel resolution over +/-
- 32 pixels
- - YCbCr video or digital input, on-board rate FIFOs, external RAM
- required
- - 0.75 micron, 50 MHz CMOS
-
- AVP1000 is from AT&T Microelectronics. The AT&T chip set
- handles MPEG-1, H.261, and JPEG. 1400D has on board color
- space convertor. Limited to 4Mb/s coded rate. The DSP does
- the MUSICAM decoding (up to layer II ?)
-
-
- 82750PB, 82750DB - Intel DVI pixel and display YUV color space processors.
- - proprietary machine code employed for compression
- - usable for other algorithms (e.g., JPEG, H.261 or MPEG1 at reduced
- data rates)
-
-
- Pipelined Processors, Monolithic, Fixed Lossless - Entropy Coders, DPCM, VQ
- ---------------------------------------------------------------------------
-
- DCP - Integrated Information Tech. Inc. Data Compressor Processor 408-727-1885
- - LZ codec with on-chip dictionary store
- - on-chip buffers supporting block moves
- - targeting disk drives and network controller markets
- - 3.3V, 84-pin PQFP
-
- Mystic - HP's DC-LZ codec. 408-749-9500
-
- AHA3210 - Advanced Hardware Architectures DC-LZ codec. 208-883-8000
- - two independent DMA ports for 10 MB/s compress, decompress &
- pass-thru
- - addressing allows up to 16 MB record compression
- - 20 MHz internal clock, 200 mW, 100-pin PQFP
- - interface to AHA5101/5121 QIC tape controller/formatter
- - HP licensee
-
- AHA3xxx/xxy - Rice (UNC) algorithm, 20M samples/sec, 4 to 14 bits. 208-883-8000
-
- CRM1000 - CERAM Inc. entropy codec, proprietary algorithm. 719-540-8500
-
- Rice - UNC algorithm prototype, 180 Mb/s. See IEEE CICC 1992
- - other CICC 1992 papers:
- +JS.E. Kerneny et.al. differential read, pyramidal output CCD
- + A. Aggoun et.al. DPCM processing
-
- DCD - Philips Data Compressor Decompressor IC. 914-945-6000
- - See CICC 1990 proceedings, H. Blume, et.al.
- - LZ codec, 20 MHz clock
- - Internal FIFOs, separate input/output buses, max 10 Mword/s data in
- - 5 V CMOS, 175-pin PGA
-
- 9705 - Second generation Stac Electronics accelerator chip. 619-431-7474
- - Stacker LZA compression scheme(LZ-based)
- - compress at approx. 2.5 MB/s, decompress at 6 MB/s (39+ faster than
- 9704)
- - standby mode 300uA
- - embedded in tapes and disks (e.g., QIC-122 Ten X Technology
- 512-346-8360)
- - file compression board & software:
- + for the PC/AT - from Stac
- + for the Macintosh - from Sigma Design 415-770-0100 (40 MHz 9703)
- - InfoChip Systems Inc. - proprietary string-matching technology
- 408-727-0514
-
- VCEP or OTI95C71/Am95C71 - Oak Technology Inc. 408-737-0888
- - AMD CCITT B&W fax image compression
-
-
- Pipelined Processors, Monolithic, Fixed Lossy
- ---------------------------------------------
-
- MB86356B - Fujitsu LTD.
- - JPEG DIS 10918-1 baseline codec
- - on-chip quantizer tables
- - 2.5M pixel/sec input, up to 10MB/sec output
- - supports progressive and DPCM lossless modes
- - 135 pin PGA.
-
- CL550-30 - C-Cube Microsystems 408-944-6300, literature@c-cube.com
- - JPEG-8-R2 compliant baseline codec
- - 350-level pipeline, on-chip Huffman and quantizer table
- - 44.1 MB/sec (15 MB/sec for -10)
- - RGB, YUV, CMYK supported, CCIR 601 in real-time
- - 16/32-bit host interface
- - 144 pin PGA or QFP, 2.5W at 29.41 MHz
-
- Limited to 2MB/sec (15Mb/s) coded rate. 35MHz PGA version
- available. 2:1 horizontal filter, on board programmable color
- space convertor. Allows on pair of quantization tables to be
- loaded while other pair is used to code or decode data stream.
- Needs maintanence by host.
-
- STI140 - SGS-Thompson JPEG baseline codec. 617-259-0300 [** Now cancelled **]
- - see CICC 1991 proceedings, M. Bolton.
- - 20 Mpixel/sec input, up to 20 MB/sec output
- - supports 24-bit color, 8-bit grey and 12-bit extended pixels
- - on chip Huffman and quantizer tables
- - 144 pin PQFP, 5V, < 2W., 10mW power-down mode
- - 1.2 micron, 3-layer metal CMOS, 20 MHz. `
-
- UVC7710 - UVC Corp. Integrated Multimedia Processor. Was 714-261-5336, out
- of business now.
- - proprietary, patented intra-frame compression, on-chip code tables
- - 20-35:1, 12.5 Mpixels/sec., compressed audio
- - includes much of the PC-AT (16-bit ISA) bus interface logic
- - 128 pin PJQFP plastic
-
- CL950 - C-Cube/JVC implementation of the MPEG-JVC or extended mode MPEG2
- announced. 6-9 Mb/sec.
-
- JVC mode is not MPEG-II compliant (there isn't an MPEG2 standard yet)
- but is an extension of MPEG1 at a higher rate plus interlace video
- handling.
-
- CL450 - Announced June 1992. Scaled down version of CL950, with 3Mb/sec
- limit. Does not code or decode JPEG, only MPEG-I decoding.
-
- CD-I - ASICs planned for CD-ROM, Compact Disk-Interactive defacto standards
- - CD-ROM XA - Sony-Philips-Motorola-Microsoft
- - CDTV - Commodore. YUV processing.
- - audio ADPCM encode/decode PC/AT boards available from Sony
- 408-432-0190
-
- Motorola MCD250 Full Motion Video Decoder. 512-928-5053.
- This is a CD-I MPEG Video decoder which requires only a single
- 4Mbit DRAM for FMV decoding. Decodes System and Video Layers
- at up to 5Mbits/sec, converts from 24/25/30 fps IPB streams to
- 25/30 fps output video in 24bit RGB/YUV format. Supports extra
- CD-I functions such as windowing and still picture mode.
- Targetted at low cost consumer applications such as CD-I,
- CD-Karaoke, Video-CD and cable TV.
-
- Motorola MCD260 MPEG Audio Host Interface and DSP56001-33. 512-928-5053.
- The MCD260 is a low cost interface IC which goes between a 68K
- bus and a DSP56K and strips out the MPEG System Layer whilst also
- buffering and synchronising. A 33MHz 56001 with 8Kwords of DSPRAM
- decodes the MPEG Audio (Layer 1/II @ 44.1KHz, all modes and bit rates)
-
- Pixel Magic PM-2. Contact: Don Shulsinger, Pixel Magic, 508-688-4410.
- - JBIG compression/decompression at 30 Mb/s (typical and worst-case)
- - G3/G4 compression/decompression at 90 Mb/s (typical), 30 Mb/s (worst-case)
- - scaling on decode from 1/256 to 256X
- - rotation by 90 degrees
- - clipping to a window and padding out to another
- - lookup table filtering on 3x3 neighborhoods
- - on-chip FIFOs on input and output
- - bookmarking for suspend/resume
-
-
- Codecs Chips Under Development
- ------------------------------
-
- MPEG1 codec chips due from - TI, Brooktree, Cypress Semiconductor, Motorola
- (successor to the DSP96002 Multimedia Engine), Xing Technology/Analog Devices,
- Sony and C-Cube
-
-
- Windbond Electronics Corp. is developing a DSP chip for CD-I, MPEG and JPEG
-
-
- Using these Chips: Board Level Compression Hardware
- ------------------------------------------------------
-
- + JPEG Using CL550
-
- + JPEG Using Other Chip Sets
-
- + DSP Chip Based JPEG/MPEG Solutions
-
- + Integrated Compressed Digital Video Boards
-
-
- JPEG Using CL550
- ---------------
- C-Cube - 408-944-6300 ISA and NuBus boards
- - for development and limited time-constraint applications
- - 1-2.5 MB/sec host bus constraints
- - Image Compression Interface (ISI) software for 3rd party CL550
- integration
-
- VideoSpigot/SuperSqueeze - SuperMac Technology 408 541-6100
- - a CL550A on a NuBus board
- - 24 frame/s with CD-quality audio
- - reads from Winchester and magneto-optic drives
-
- Fluency VSA-1000 - Fluent Machines, Inc. AT board set. 508 626-2144
- - compress/decompress real-time synced audio & video to a i386 PC
- Winchester
- - NTSC or PAL input, 320x240 pixels saved
- - uses i960 chip, no additional boards needed
- - M/S Windows support, 3rd party S/W (e.g., AimTech 603-883-0220)
-
- Super Motion Compression - New Media Graphics PC/AT board. 800 288-2207
- - 8Khz, 8-bit compressed audio
- - 30 f/s JPEG to & from disk
- - earlier reports: still-frame compression in several seconds per MB
-
-
- Leadview - Lead Tech Inc. AT board uses the CL550 to compress/decompress
- JFIF or JTIF format files
-
- Monalisa - Opta Inc. AT board uses the CL550
-
- Squeeze - Rapid Technology AT board
- - Integrated by a number of vendors into 3rd party multimedia,
- video-editing PC stations
-
- Parallax Graphics - SBus, VME and PC-AT boards. 408-727-2220 or
- info@parallax.com
-
- Chips and Technologies - JPEG development kit due.
-
- Image Manipulation Systems, Inc - SBus compression/framebuffer/video I/O boards
- 800-745-5602 or imsinfo%thumper@src.honeywell.com
-
-
- JPEG Using Other Chipsets
- -------------------------
-
- Visionary - Rapid Technology JPEG AT board. 716-833-8534
- - LSI Logic JPEG chips L647-35, -45 & -65
- - 30 f/s motion JPEG
- - 256x240 pixel compression and display from CCIR-601 input
- - private codec-frame buffer bus
- - also integrated with TrueVision multimedia hardware
-
- Media 100 - Data Translation nonlinear video production system for the
- Macintosh (QuickTime). 22 MB/s (PAL) and 18MB/s (NTSC) throughput.
-
- Alice - Telephoto Communications Inc. 619-452-0903
- - Alice-H350 (PC/AT) and -H365 (PS/2) codec boards
- - use a 40 MHz TMS320C51 DSP and a IMSA121 DCT processor chip
- - JPEG (lossy and lossless), CCITT G3/G4, color and grey-scale images
-
- Xing Technology - Hardware accelerator. xing@xingtech.com or 805-473-0145
- - compatible with their VT-Express JPEG Turbo Accelerator Software
-
- Video/1 - PsiTech Inc. 714-968-7818
- - includes a 6U VME/VSB JPEG Processing Card
- - compresses RS-170, NTSC, PAL or Secam video into 8 MB of on-board RAM
-
-
- DSP Chip Based JPEG/MPEG Solutions
- ----------------------------------
-
- Optipac - Optivision Inc. PC/AT, ISA & VME codecs. 800-562-8934
- - JPEG (lossless and lossy), CCITT III/IV
- - 1 to 5 TMS32C025s
- - 512x400x16-bit images in < 1 sec.
-
- XCeed ICDP-II - Micron Technology Inc. NuBus card
- - uses two AT&T Microelectronics DSP-16 DSP chips
- - driven by Storm Technologies PicturePress software
- - executes an enhanced JPEG algorithm at near-realtime.
-
- PicturePress Accelerator - Storm Technology 415-691-1111 (see above)
- - also has a line of VME compression boards
- - Micro Dynamics Ltd. imaging systems use Storm accelerator
- 301-589-6300
-
- Picture Packer Accelerator - Video & Image Compression Corp.
- - AT and NuBus boards use the JPEG Open Standard and a TMS320C25
-
- SunVideo (S-bus) - Sun Microsystems
- - PAL/NTSC framegrabber with an integrated C-Cube CL4000
- VideoRISC processor and downloadable video compression for
- MPEG, MJPEG or CellB. It achieves about 10 Frames/sec on
- MPEG Level 1 picture data compression. The board costs about $1K.
-
- Phoenix System - T/one Inc. uses an Optivision Optipac 3250 to talk to a Storm
- Technologies NuBus PicturePress Accelerator to talk JPEG over
- analog phone lines.
-
- Nextdimension - NeXt Computer Inc. 415-780-3912
- - 24+8-bit alpha, 640x480, 30 f/s decompression
- - CL550 version not shipping as announced.
-
- Spirit-40 - Sonitech International Inc. ISA card. 617-235-6824
- - two TMS320C40 DSPs for 80 MFLOPS
- - connect 16 boards in a hypercube for up to 1280 MFLOPS
- - JPEG, MPEG-1 audio and other voice coding applications included
-
- HardPak - CERAM Inc., ISA and EISA file compression board. 719-540-8500
- - 3.4 x 1.8 inch footprint (notebook, laptops)
- - 32KB on-board write-thru file compression cache
- - CERAM also has an SBus compressive swap-space accelerator for Suns
-
- macDSP - Spectral Innovations, AT&T DSPC32-based accelerator. 408-727-1314
- - JPEG functions available
- - 30 MFLOPS on the NuBus
-
-
- Integrated Digital Video Boards - Miscellaneous Multimedia, Video Conferencing
- ------------------------------------------------------------------------------
-
- VCI/oem - Vista Communication Instruments, Inc. +358 0 460 099
- - two AT-board H.261 video codec, PAL or NTSC cameras and monitors
- -56 kbps (64 kbps) to 2 Mbps, 64 kbps increments
- - H.221 framing and synchronizing - H.241 network signalling
- - H.200/AV.254 forthcoming standard for compressed audio
- - network interface boards available
-
- MediaStation- VideoLogic Inc., JPEG compression board for ISA bus. 617-494-0530
- - works with VideoLogic DVA-4000/ISA motion video board, custom bus
- - CL-550 plus ADPCM and PCM audio support
- - Inmos Transputer for I/O scheduling
- - Microsoft Windows Multimedia Extensions and proprietary interfaces
-
- DECspin - Digital Equipment CorpSound/Picture Information Network 508-493-5111
- - full motion, true-color (24-bit) and greyscale (8-bit black & white)
- - variable frame size and rate up to 640 x480 x30 NTSC true-color
- - Internet or DECnet transmission and disk I/O of live synchronized
- video/audio
- - video teleconferencing using standard network protocols
- - create and edit of audio and video sequences
- - voice grade live audio sequences
- - DECmedia DECvideo and DECaudio hardware and software required
-
- ActionMedia II - Intel/IBM DVI PS/2 and PC/AT boards. 914-642-5472
- - i750 processor boards for capture and delivery systems
- - Microsoft programming support libraries
- - proprietary RTV and PLV compression algorithms resident, time and
- time/space VQ
- - Real Time Video (RTV) algorithm 1.5 , effective 128x120 pixel
- sequence at 30 f/s.
- - RTV 1.0 is 128x240 at 10 f/s.
- - Presentation Level Video (PLV) - extensive off-line processing,
- exploits inter-frame coherence.
- - i750 processor capable of playing-back PLV-compressed 256x240
- sequences at 30 f/s.
-
- DVI Board - Fast Electronic U.S. Inc. laptop board. 508-655-3278
- - uses Intel i750 chipset
- - compress or decompress video at up to 30 f/s
-
- EyeQ - New Video Corp. DVI boards for the Macintosh. 213-396-0282
- - uses Intel i750 chipset
- - 150 KB/s full-motion compressed video
- - T1 and Winchester integration paths
-
- Copernicus 1000 & 2000 - DesignTech, 408-453-9510
- - DVI-based presentation and authoring systems
-
- Spectrum Signal Processing - DSP96002-based PC-AT board
- - up to four boards in cascade
- - other TI, Analog Devices and AT&T-based DSP offerings
-
- Ariel Corp. - Dual DSP96002 PC-AT board with compression support. 201-429-2900
-
- Capture I - UVC Corp., 16-bit ISA bus board. was 714-261-5336, out
- of business now.
- - 30 f/s of 640/480 interlace capture and record (uses UVC7710)
- - NTSC or PAL input
- - VPC200/201 development board set - proprietary NTSC video codec
- (audio card required).
-
- Leadview - Lead Technologies, Inc. accelerates an enhanced JPEG algorithm
- on ISA
-
- IBM - near-term availability:
- (1) IBM United Kingdom and British Telecommunications plc.
- - PC or PS/2 add-on boards by end of 1993
- - interface to ISDN 2 service (one or two 64kb/s channels)
- - BT also planning residential videophone product with GEC Marconi Ltd.
-
- (2) IBM Japan PS/2 board
- - uses GCTX64000 for H.261
- - ISDN (narrowband 64kb/s ) and IEEE 802.5 LAN interfaces
-
-
- Optibase 100 - Optibase, Inc. DSP-based compression/expansion boards.
- 818-719-6566
- - supports JPEG
- - supports CCITT G.721 and ANSI T1.301 & T1.303 drafts (voice and
- music)
- - and proprietary compression (AADCT, lossless)
-
- Optibase MPEG Lab Pro and MPEG Lab +. Phone: 214-386-2040 or 800-451-510
-
- Motorola - DSP56002 (fixed-point 40MHz version of the 56001)
-
- AT&T JPEG coder (George Warner <warnergt@aloft.att.com>)
- - runs on a DSP3210 under the VCOS operating system.
- The coder can be used to simultaneously compress/decompress
- multiple images and/or be used in conjunction with other DSP
- modules to preprocess or postprocess the image data.
-
- Other modules available for the DSP3210 include audio coders
- (such as MPEG, SBC, CDXA, and G.722), modem/fax data pumps
- (V.32bis, V.22bis, and V.29), DTMF, call progress detection,
- sample rate conversion, and more.
-
-
- MWave - TI, IBM, Intermetrics multimedia system, due from IBM in 1993.
-
- Misc. NuBus boards - RasterOps , Radius, Mass Microsystems, Orange Micro,
- IBM M - - Motion.
-
- P.OEM - Interated Systems Inc. fractal compression boards for the PC.
- 404-840-0310
-
- two desktop video conferencing products for Sparc's
- with the Parallax XVIDEO board:
-
- Communique! - desktop video conferencing products for Sparcs with the Parallax
- XVIDEO board:
- InSoft, Inc., 4718 Old Gettsburg Road, Executive Park West I, Suite 307
- Mechanicsburg, PA 17055, USA. email: info@insoft.com
- phone: 717-730-9501, fax: 717-730-9504
-
- PSVC - desktop video conferencing products for Sparcs with the Parallax
- XVIDEO board:
- Paradise Software, Inc., 55 Princeton Heightstown Rd, Suite 109
- Princeton, NJ 08550, USA. email: support@paradise.com
- phone: 609-275-4475, fax: 609-275-4702
-
- North Valley Research - video and other time-based media in a UNIX environment
- North Valley Research; 15262 NW Greenbriar Pkwy; Beaverton, OR 97006
- Phone (503) 531-5707, Fax (503) 690-2320. Todd Brunhoff <toddb@nvr.com>
-
- Visionetics MPEG MasterTM for 386 PC. phone (310) 316-7940,
- fax (310) 316-7457, e-mail 72622.2112@compuserve.com.
- MPEG Video compliant with ISO-11172
- Up to 16 million colors regardless of VGA card or VGA mode
- 704 x 480 NTSC, 704x576 PAL resolution
- Full motion video NTSC ( 30 fps), Pal (25 fps)
- VIGABUSTM high speed digital video bus
-
- MPEG audio Layer I and II
- 16 bit stereo digital audio playback
- 20 Hz - 20 KHz frequency response
- Stereo headphone/preamp output
-
- RealMagic board. Sigma Designs, 510-770-0100
- - MPEG Audio and Video playback board (ISA bus). Full compliance with
- ISO CD 11172. Supports 30 fps (NTSC), and 25 fps (PAL).
- - MPEG sound standards - Layer I and II.
- - On-board CD ROM interface (not on RealMagic Lite board)
-
- RealMagic Producer. Sigma Designs, 510-770-0100
- - Video/Audio Capture and MPEG encoding controller (PCI bus).
- - Compressed Data Format: MPEG-1, 352x240 (NTSC), 352x288 (PAL).
- - Audio Capture - MPEG-1, Layer I and II. 44.1 kHz sampling frequency.
- - Require Pentium system, 16 MB RAM, fast SCSI hard drive.
-
-
- Boards Under Development
- ------------------------
-
- Matrox - Matrox Studio line of PC boards will include a 64-bit MOVIE bus and
- JPEG compression.
-
-
- ------------------------------------------------------------------------------
-
- Subject: [99] Acknowledgments
-
-
- There are too many people to cite. Thanks to all people who directly
- or indirectly contributed to this FAQ.
-