john@anasaz.uucp (John Moore) (06/14/91)
Can anyone post a summary of the concept of wavelet transforms? I have read that these are the "hot new thing." In an attempt to solicit information, let me guess what they are. That way, if you know but are too lazy to answer my first request, you will be sorely tempted to set me straight:-) I would guess that they are a form of the general Fourier transform. By this, I do not mean the traditional transform, but rather a class of transforms characterized by the use of orthogonal functions - by this definition a LaPlace (sp?) transform and a Walsh transform is also a Fourier transform. With wavelets, presumably someone found a nifty set of orthogonal, spanning functions that resemble solitons or sinx/x functions or something else that is new and marvelous. Well, am I close? Am I all wet? Please don't send arcane references, as I am quite a distance from a good library. Thanks (I hope).
abed@saturn.wustl.edu (Abed M. Hammoud) (06/15/91)
In article <6654@qip.UUCP> john@anasaz.uucp (John Moore) writes: >Can anyone post a summary of the concept of wavelet transforms? I have >read that these are the "hot new thing." > >In an attempt to solicit information, let me guess what they are. That >way, if you know but are too lazy to answer my first request, you >will be sorely tempted to set me straight:-) > >I would guess that they are a form of the general Fourier transform. >By this, I do not mean the traditional transform, but rather a class >of transforms characterized by the use of orthogonal functions - by this >definition a LaPlace (sp?) transform and a Walsh transform is also a >Fourier transform. With wavelets, presumably someone found a nifty >set of orthogonal, spanning functions that resemble solitons or >sinx/x functions or something else that is new and marvelous. > >Well, am I close? Am I all wet? Please don't send arcane references, as >I am quite a distance from a good library. > >Thanks (I hope). I would also be interested in reading something about wavelets transform.... thanks, abed@saturn.wustl.edu
juni@ss.titech.ac.jp (Junibakuti Sanubari) (06/16/91)
In article <6654@qip.UUCP>, john@anasaz.uucp (John Moore) writes:
I am also interesting to hear something about this transform. Please do
not left me behind and let me know something about this also.
rainer@boulder.Colorado.EDU (Rainer Malzbender) (06/17/91)
Here is a post I saved which has a bunch of wavelet references. Sorry, no explanations. I've meant to check into this, but haven't. My understanding is that the transform involves a set of localized functions (wavelets), as opposed to plane waves of infinite extent. --- Begin quoted article --- Article 14360 of comp.graphics: Path: boulder!ncar!asuvax!cs.utexas.edu!sdd.hp.com!ucsd!ucbvax!ucsfcgl!socrates.ucsf.edu!rl From: rl@socrates.ucsf.edu (Robert Langridge) Newsgroups: comp.graphics Subject: Re: References on wavelets Message-ID: <rl.655227166@socrates.ucsf.edu> Date: 6 Oct 90 15:32:46 GMT References: <109624@philabs.Philips.Com> Sender: daemon@cgl.ucsf.edu Lines: 53 cc: rl zhu@gandalf.Philips.Com (Benjamin Zhu) writes: >I would like to receive some references on wavelets in image >processing or related disciplines. I am not exactly sure if >it has a synonym elsewhere. Please respond by e-mail. Thanks. >Ben >------------ >Benjamin Zhu (914) 945-6564 >Philips Laboratories zhu@philabs.philips.com I posted refences to sci.math. Here is a longer list. 1. DAUBECHIES I. THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS. IEEE TRANSACTIONS ON INFORMATION THEORY, 1990 SEP, V36 N5:961-1005. 4. KNOWLES G. VLSI ARCHITECTURE FOR THE DISCRETE WAVELET TRANSFORM. ELECTRONICS LETTERS, 1990 JUL 19, V26 N15:1184-1185. 7. WORNELL GW. A KARHUNEN-LOEVE-LIKE EXPANSION FOR 1/F PROCESSES VIA WAVELETS. Pub type: Letter. IEEE TRANSACTIONS ON INFORMATION THEORY, 1990 JUL, V36 N4:859-861. 14. LEWIS AS; KNOWLES G. VIDEO COMPRESSION USING 3D WAVELET TRANSFORMS. ELECTRONICS LETTERS, 1990 MAR 15, V26 N6:396-398. 20. SLEZAK E; BIJAOUI A; MARS G. IDENTIFICATION OF STRUCTURES FROM GALAXY COUNTS - USE OF THE WAVELET TRANSFORM. ASTRONOMY AND ASTROPHYSICS, 1990 JAN, V227 N2:301-316. 21. MALLAT SG. MULTIFREQUENCY CHANNEL DECOMPOSITIONS OF IMAGES AND WAVELET MODELS. IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1989 DEC, V37 N12:2091-2110. 30. MALLAT SG. A THEORY FOR MULTIRESOLUTION SIGNAL DECOMPOSITION - THE WAVELET REPRESENTATION. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1989 JUL, V11 N7:674-693. Best Regards Bob Langridge Phone: +1 415 476-2630, -1540, -5128 Computer Graphics Laboratory FAX: +1 415 476-0688 University of California E-Mail: rl@cgl.ucsf.edu San Francisco CA 94143-0446 -- Rainer Malzbender Dept. of Physics (303)492-6829 U. of Colorado, Boulder rainer@boulder.colorado.edu 128.138.240.246
eero@media-lab.media.mit.edu (Eero Simoncelli) (06/18/91)
John Moore (john@qip.UUCP) writes: > Can anyone post a summary of the concept of wavelet transforms? I have > read that these are the "hot new thing." > > .... With wavelets, presumably someone found a nifty > set of orthogonal, spanning functions that resemble solitons or > sinx/x functions or something else that is new and marvelous. This is a reasonable description, but most people would add a few additional properties: 1) The basis functions form an octave subband (constant Q) transform (when viewed in the frequency domain). 2) The transform is defined (and typically implemented) recursively. In addition, people are often interested in the convergence properties of the recursive construction. If the process converges to a smooth function, the wavelet set is called "regular". One useful mathematical review that hasn't been mentioned is the following: @ARTICLE{Strang89, AUTHOR = "G. T. Strang", TITLE = "Wavelets and dilation equations: A brief introduction", JOURNAL = "{SIAM} Review", VOLUME = 31, NUMBER = 4, MONTH = "December", YEAR = 1989, PAGES = "614--627" } Also, researchers in the speech coding community have been using a version of discrete wavelet transforms (under the name of Quadrature Mirror Filter banks) since 1976. They've also been used in image coding. Here are some references: @INPROCEEDINGS{Croisier76, AUTHOR = "A. Croisier and D. Esteban and C. Galand", TITLE = "Perfect channel splitting by use of interpolation/decimation/tree decomposition techniques", BOOKTITLE = "International Conference on Information Sciences and Systems", YEAR = 1976, MONTH = "August", ADDRESS = "Patras", PAGES = "443--446" } @INPROCEEDINGS{Esteban77, AUTHOR = "D. Esteban and C. Galand", TITLE = "Application of quadrature mirror filters to split band voice coding schemes", BOOKTITLE = "Proceedings ICASSP", YEAR = "1977", PAGES = "191--195" } @ARTICLE{Vetterli84, AUTHOR = "M. Vetterli", TITLE = "Multi-dimensional sub-band coding: Some theory and algorithms", JOURNAL = "Signal Processing", PUBLISHER = "Elsevier Science Publishers~B.V. (North-Holland)", MONTH = "February", YEAR = "1984", VOLUME = "6", NUMBER = "2", PAGES = "97--112" } @ARTICLE{Woods86, AUTHOR = "J. W. Woods and S. D. O'Neil", TITLE = "Subband coding of images", JOURNAL = "IEEE Trans. ASSP", MONTH = "October", YEAR = "1986", VOLUME = "ASSP-34", NUMBER = "5", PAGES = "1278--1288" } @INPROCEEDINGS{Gharavi86, AUTHOR = "Gharavi, H. and Tabatabai, A.", TITLE = "Sub-band coding of digital images using two-dimensional quadrature mirror filtering", BOOKTITLE = "Proceedings of SPIE", YEAR = "1986", VOLUME = "707", PAGES = "51--61" } @INPROCEEDINGS{Adelson87, AUTHOR = "E. H. Adelson and E. Simoncelli and R. Hingorani", TITLE = "Orthogonal pyramid transforms for image coding", BOOKTITLE = "Proceedings of SPIE", ADDRESS = "Cambridge, MA", VOLUME = 845, MONTH = "October", PAGES = "50--58", YEAR = 1987 } @ARTICLE{Simoncelli89, AUTHOR = "E. Simoncelli and E. H. Adelson", TITLE = "Non-separable Extensions of Quadrature Mirror Filters to Multiple Dimensions", JOURNAL = "Proceedings of the IEEE: Special Issue on Multi-dimensional Signal Processing", MONTH = "April", YEAR = 1990 } @BOOK{Woods90, EDITOR = "J. W. Woods", BOOKTITLE = "Subband Image Coding", PUBLISHER = "Kluwer Academic Publishers", ADDRESS = "Norwell, MA", YEAR = 1990 } Finally, two interesting related transforms are the Laplacian pyramid and the Lapped Orthogonal Transform: @ARTICLE{Burt83, AUTHOR = "P. J. Burt and E. H. Adelson", TITLE = "The {L}aplacian pyramid as a compact image code", JOURNAL = "IEEE Trans. Communications", MONTH = "April", YEAR = "1983", VOLUME = "COM-31", NUMBER = "4", PAGES = "532--540" } @ARTICLE{Malvar89, AUTHOR = "H. S. Malvar and D. H. Staelin", TITLE = "The {LOT}: Transform Coding Without Blocking Effects", JOURNAL = "IEEE Trans. ASSP", VOLUME = "ASSP-37", NUMBER = 4, PAGES = "553--559", MONTH = "April", YEAR = 1989 } Hope you find these useful, Eero. -- Eero Simoncelli eero@media-lab.media.mit.edu MIT Media Laboratory, E15-385, 20 Ames Street, Cambridge, MA 02139
edhall@rand.org (Ed Hall) (06/18/91)
In article <545@pollux.ss.titech.ac.jp> juni@ss.titech.ac.jp (Junibakuti Sanubari) writes: >In article <6654@qip.UUCP>, john@anasaz.uucp (John Moore) writes: > >I am also interesting to hear something about this transform. Please do >not left me behind and let me know something about this also. The following article was posted to comp.compression a couple of days ago. Since it involves the Wavelet Transform, I thought you might be interested. -Ed Hall edhall@rand.org ========= Path: randvax!usc!wuarchive!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!news.media.mit.edu!media-lab.media.mit.edu!eero From: eero@media-lab.media.mit.edu (Eero Simoncelli) Newsgroups: comp.compression Subject: Re: JPEG obsolete Summary: Fast Wavelet compression software Keywords: wavelet,pyramid,coder,compression,jpeg Message-ID: <1991Jun14.184807.27995@news.media.mit.edu> Date: 14 Jun 91 18:48:07 GMT References: <1991May30.203723.21550@ns.network.com> <1991Jun1.055212.18204@alembic.acs.com> Sender: eero@media-lab.media.mit.edu Organization: MIT Media Laboratory Lines: 111 For those of you interested in Wavelet compression schemes, I have a very fast (on the decompression end) pyramid wavelet coder. It works reasonably well (informal comparisons seemed noticably better than JPEG), but there is certainly room for improvement. It is available via anonymous ftp -- here is the README file: --------------------------------------------------------------------- --- EPIC (Efficient Pyramid Image Coder) --- --- Designed by Eero P. Simoncelli and Edward H. Adelson --- --- Written by Eero P. Simoncelli --- --- Developed at the Vision Science Group, The Media Laboratory --- --- Copyright 1989, Massachusetts Institute of Technology --- --- All rights reserved. --- --------------------------------------------------------------------- Permission to use, copy, or modify this software and its documentation for educational and research purposes only and without fee is hereby granted, provided that this copyright notice appear on all copies and supporting documentation. For any other uses of this software, in original or modified form, including but not limited to distribution in whole or in part, specific prior permission must be obtained from M.I.T. and the authors. These programs shall not be used, rewritten, or adapted as the basis of a commercial software or hardware product without first obtaining appropriate licenses from M.I.T. M.I.T. makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty. --------------------------------------------------------------------- EPIC (Efficient Pyramid Image Coder) is an experimental image data compression utility written in the C programming language. The compression algorithms are based on a hierarchical subband decomposition using asymmetric filters (described in the references given below) and a combined run-length/Huffman entropy coder. The filters have been designed to allow extremely fast decoding on conventional (ie, non-floating point) hardware, at the expense of slower encoding. We are making this code available to interested researchers who wish to experiment with a subband pyramid coder. We have attempted to optimize the speed of pyramid reconstruction, but the code has not been otherwise optimized, either for speed or compression efficiency. In particular, the pyramid construction process is unnecessarily slow, quantization binsizes are chosen to be the same for each subband, and we have used a very simple scalar entropy coding scheme to compress the quantized subbands. Although this coding technique provides good coding performance, a more sophisticated coding scheme (such as vector quantization) using the same pyramid decomposition could result in substantial coding gains. EPIC is currently limited to 8-bit monochrome square images, and does not explicitly provide a progressive transmission capability. Epic is available via anonymous ftp from whitechapel.media.mit.edu (IP number 18.85.0.125) in the file pub/epic.tar.Z. Comments, suggestions, or questions should be sent to: Eero P. Simoncelli Vision Science Group MIT Media Laboratory, E15-385 Cambridge, MA 02139 Phone: (617) 253-3891, E-mail: eero@media-lab.media.mit.edu References: Edward H. Adelson, Eero P. Simoncelli and Rajesh Hingorani. Orthogonal pyramid transforms for image coding. In Proceedings of SPIE, October 1987, Volume 845. Eero P. Simoncelli. Orthogonal Sub-band Image Transforms. Master's Thesis, EECS Department, Massachusetts Institute of Technology. May, 1988. Edward H. Adelson, Eero P. Simoncelli. Subband Image Coding with Three-tap Pyramids. Picture Coding Symposium, 1990. Cambridge, MA. USAGE: ------ Typing "epic" gives a description of the usage of the command: epic infile [-o outfile] [-x xdim] [-y ydim] [-l levels] [-b binsize] An example call might look like this: epic /images/lenna/data -o test.E -x 512 -y 512 -l 5 -b 33.45 Note that: 1) the infile argument must be a file containing raw image data 2) this file must be an 8 bit file (not 32 bit or float) 3) if the size of the image is different than 256x256, you must specify it on the command line. Currently, the code is limited to square images only. 4) the binsize can be any floating point number. Larger numbers give higher compression rates, smaller numbers give better image quality. Using a binsize of zero should give perfect reconstruction. 5) Color images can be compressed best by converting from rgb to yiq and compressing each of the components separately. The decompression command "unepic" is much easier to use. Typing "unepic test.E" will create a raw 8bit data file called "test.E.U". If you don't like that name, you can specify a different name as an optional second argument. -- Eero Simoncelli Vision Science Group MIT Media Laboratory, E15-385 Cambridge, MA 02139
jdp@engr.uark.edu (Dalton Porter) (06/24/91)
john@anasaz.uucp (John Moore) writes: >Can anyone post a summary of the concept of wavelet transforms? I have >read that these are the "hot new thing." > >Well, am I close? Am I all wet? Please don't send arcane references, as >I am quite a distance from a good library. I hope you don't consider this arcane but check out the June (I think) issue of Radio Electronics in the Hardware Hacker section. This gives a brief intro to the subject. /* Dalton Porter, University of Arkansas, Fayetteville Dept. of Electrical Engineering E-Mail -> jdp@engr.uark.edu "I would get up but the boy crippled me." -Homer Simpson */