Wavelet afbildninger, Wavelet Transformationer

Image Compression - from DCT to Wavelets : A Review by Subhasis Saha
"...Conclusion
While the DCT-based image coders perform very well at moderate bit rates, at higher compression ratios, image quality degrades because of the artifacts resulting from the block-based DCT scheme. Wavelet-based coding on the other hand provides substantial improvement in picture quality at low bit rates because of overlapping basis functions and better energy compaction property of wavelet transforms....
"
UCLA Image Communications Lab: Wavelet Image Coding: PSNR Results

Wavelet Transformation

Den DWT [diskrete Wavelet transformation], er en linear og invertibel afbildning. Den kan udføres direkte på k*n² elementære operationer. DWT kan via FFT [Fast Fourier Transformationen] udføres på k*n* log₂(n) operationer. Hvis basisfunktionerne har kompakt støtte , kan DWT udføres paa k*n-operationer via FWT [Fast Wavelet Transformationen]. FWT er en faktorisering af DWT til log₂(n)-1 afbildninger. Afbildningerne er filterbank filtreringer.

Filterbank afbildning - et FWT trin

Father-skaleringsfunktionen og mother-waveletten - de 2 basisfunktionsskabeloner - er FWT koefficienternes funktioner over R. Her er grafer af Daubechies 4 Father-skaleringsfunktionen og mother-waveletten. Af mother og father funktionen kan alle Wavelet- og skalerings-funktioner dannes ved dilation og translation.

Wavelet og skaleringskoefficienterne udgør hhv. den diskretiserede skalerings og den diskretiserede Wavelet-funktion. Daubechies 4 koefficienterne er Wavelet_D4[0,1,2,3]=[1+sqrt(3), 3+sqrt(3), 3-sqrt(3), 1-sqrt(3)]/8, nul ellers og Skalering_D4[0,1,2,3]=[1-sqrt(3), -3+sqrt(3), 3+sqrt(3), -1-sqrt(3)]/8, nul ellers. De er diskretiseret i Wavelet basen selv! Ikke i en almindelig Shannon-diskretisering (eng. sampling), der benyttes i CD afspillere, telefoni, Satellit TV (DBS), PC-lydkort og DAT båndoptager.

Father- og mother-funktionen kaldes også hhv. ved de græske bogstaver φ (phi) og ψ (psi). Basisfunktionerne udgør hhv. et midlings (eng. averages)- og fluktuations (eng. differences)- filter - disse 2 termer haves fra Yves Meyer "Wavelets Algorithms and Applications" SIAM 1993. Filtrene kaldes "fejlagtigt" hhv. lavpas- og båndpas-filteret.

Filtrene udgør ikke en komplet diskret filtrering, da resultatet af filtreringerne med midlings- og fluktuations-filteret, hver især kun har hver anden af filter koefficienterne. Output koefficient antallet fra filtrene, er derfor ligeså mange som input.

Midlings og fluktuations-filteret omtales under et, som en filterbank med 2 filtre. Filterbanken kan med fordel ses som en matrix. WT-filterbankmatricen baseret på ortogonale basisfunktioner, er per definition invertible og dermed kvadratiske. Det er bedst at implementere filterbank afbildningen med en af statistik operationerne, foldning (eng. convolution) eller korrelation, der kan udføres på k*n operationer, når den ene af funktionerne til foldning eller korrelation, er kompakt støttet. En brute force matrix vektor operation udføres på n² operationer. Den historiske baggrund af filterbanker er i Yves Meyer.

Fast Wavelet Transformation af 1D funktioner

En 1D funktion afbildes til 2D i Wavelet-funktionsrummet. Den ekstra dimension er skalaen (eng. scale). Antallet af output koefficienter delt over skalaer er n/2, n/4, n/8... . En måde at nummerere skalaerne er at tælle opad for hver filterbank filtrering, andre lader i stedet skalaerne tælle ned.

Vi starter med en input-vektor med længde n og kræver at n er en 2-potens. Så udføres en filterbank filtrering, som tager input-vektoren og afbilder den over i en output-vektor. Output-vektoren udgøres af 2 delvektorer, med hver n/2 koefficienter. Disse er på skala 1. Fluktuationsvektordelen lader vi være. Midlingsvektordelen arbejder vi videre med og får hermed rolle af input-vektor. Denne filterbank filtreres og resultatet er en ny vektor på n/2 koefficienter (skala 2), som igen består af en fluktuations og en Midlingsdel. Det fortsætter vi med log₂(n)-1 gange og ender med 2 koefficienter, hvoraf den ene er middelværdien *k. Vi har nu nået vores mål: udført en FWT. Vektoren er fluktuationskoefficienterne: n/2+n/4+n/8+...+1(+1 middelværdien*k) i alt n koefficienter ( (n-1) Wavelet-koefficienter og middelværdien*k).

Wavelet diskretisering

Én dimensionel input til WT, og dermed første filterbank, er skaleringskoefficienter. Disse er dannet ved indre produkter mellem input over R med n skaleringsfunktioner over R. Skaleringsfunktionerne dannes ved translation t= x, x tilhører 0, 1,..., n-1, når skabelonskaleringsfunktionens dilation er valgt, så de er indbyrdes ortogonale. Dette er netop opskriften på Wavelet-diskretisering af en input-funktion.

En alternativ og ækvivalent metode er kontinuert filtrering med skaleringsfunktionen. Den anvendte skaleringsfunktion er dilateret, så den er ortogonal med sig selv til t= x, x tilhører 0, 1,..., n-1. Dernæst foldes resultatet med delta funktioner til t= x, x tilhører 0, 1,..., n-1.

Partiel Wavelet Transformation PWT

I praksis er 5 til 7 filter banks filtreringer nok, til at afgøre om input-vektoren giver mange små output-koefficienter og dermed en mulig kompression. Afbildninger dannet ved færre end log₂(n)-1 filterbank filtreringer, vælger jeg at kalde Partiel Wavelet Transformation PWT. Mange små koefficienter kan være følgen af input-funktionens hurtige konvergens i Wavelet og skalerings funktions rummet. PWT er en meget anvendt metode, men omtales i flæng som WT.

I følgende eksempel er en Firkantfunktion Partiel Wavelet Transformeret med 6 D4 analyse filterbanker. De benyttede PWT(analyse) og IPWT(syntese) filterbanker. Bemærk at Wavelet koefficientvektorerne kaldes Detail. Her er skalerings koefficientvektorer V_n og Wavelet koefficientvektorer D_n (n=skala). I dette eksempel benyttes V₆ og D_1...6 ved rekonstruktion, efter afrunding mod nul af de mindste Wavelet-koefficienter. Rekonstrueret efter kompression med maksimal tilladt 2-norms afvigelse på 5%. For hver n>=1 udgør vektorerne V_n og D_1...n en basis for Firkantfunktionen, men n=6 gav den bedste kompression.

Faktisk er V₀, Firkantfunktionen selv, den bedste at komprimere, da RLC kun skulle kode 3 intervaller og 2 forskellige tal (binært kvantiseret). Mange virkelige funktioner er mere sammensatte og desuden overlejret med støj, som resulterer i at direkte kompression af funktionen ikke er givtigt.

Eksemplets anvendte kompressionsalgoritme er yderst simpel og bør erstattes med processen vektorkvantisering (eng. VQ) og en kodning af nulværdikoefficienter. Kodningen kan for 1D funktioner være RLC og for 2D funktioner være SPIHT kodning.

En output koefficient er det indre produkt mellem den resulterende afbildnings underliggende basisfunktion over R og input-funktionen over R. En output-koefficient er ækvivalent det indre produkt mellem den resulterende afbildnings underliggende basisfunktion over t= 0, 1,...,n-1 og input-funktionen over t= 0, 1,...,n-1. For hver filterbank filtrering vil output-koefficienterne repræsentere dobbelt så lange basisfunktioner som input-koefficienternes basisfunktioner.

Invers Fast Wavelet Transformation IFWT IPWT

For en ortonormal matrix med koefficienter i R, vil den inverse være den transponerede: A^-1 = A^T. Dette anvendes ved beregning af den inverse WT og de inverse filterbanker. Den sidst anvendte filterbank inverteres og anvendes til invers afbildning. Dernæst den næstsidste og så fremdeles. Vi har jo: A_n^T*...*A₂^T*A₁^T = (A₁*A₂*...*A_n)^T. Af dette kan det vises, at de 2 forward skabelon basis funktioner spejlet om en lodret linie, er de inverse skabelonbasisfunktioner. Er input tidssignaler, kaldes basisfunktionens spejling, tidsreversering.

PWT vigtige iagttagelser

Input koefficienter er her resultatet af en Wavelet diskretisering og output er progressivt flere og flere Wavelet-(fluktuations)-koefficienter og tilsvarende færre skaleringskoefficienter for hver filterbank filtrering.

1. Koefficienter har kun muligt bidrag fra input, hvor basisfunktionen er forskellig fra nul.

2. For hver filterbank filtrering vil de afbildede input-koefficienter; output have dobbelt så lange basisfunktioner (indtil den kompakt støttede funktions ender, mødes).

3. En Wavelet basis funktion har integrale nul. For små skalaer er basisfunktionerne korte og når input-funktionen er omtrent ortogonal på disse - f.eks. omtrent konstant i basisfunktionens virke - så vil fluktuationskoefficienten være lille.

4. En skaleringsbasisfunktion har integrale forskellig fra nul. For små skalaer er basisfunktionerne korte. Når input funktionen er omtrent konstant, i basisfunktionens virke, så vil input give et betydeligt bidrag til skaleringskoefficienten. For hver filterbank filtrering, vil antallet af skaleringskoefficienter halveres. Den samlede output-vektor vil tilsvarende få øget antallet af fluktuationskoefficienter.

5. En matematisk sætning i [Strang96] garanterer eksponentiel aftagende fluktuationskoefficienter, for input-funktioner, der er kompakt støttet i frekvens (Fourier) funktionsrummet.

IPWT vigtige iagttagelser

Input er Wavelet og skaleringskoefficienter fra den samme skala og output er progressivt flere og flere skaleringskoefficienter for hver filterbank filtrering. Den underliggende output-funktion over R, dannes ved en vægtet sum af skala nuls koefficienter og skaleringsbasisfunktionerne over R.

1. Output har kun mulig bidrag fra koefficienter, hvor basisfunktionen er forskellig fra nul. Koefficienter fra lavere skalaer, har derfor kun lokal indflydelse på den rekonstruerede output-funktion.

2. For hver filterbank afbildning, fra Wavelet og skalerings til skaleringskoefficienter, vil koefficienterne få halvt så lange basis funktioner. Dvs. for hver gang skala sænkes, har koefficienterne smallere indflydelse i output.

Referencer

Filterbanker

En god bog om filterbanker:
http://saigon.ece.wisc.edu/~waveweb/Tutorials/book.html eller http://www-math.mit.edu/~gs/books/wfb.html
@book{Strang96,
    author = "G. Strang and T. Nguyen",
    booktitle = "Wavelets and Filter Banks",
    edition = "1",
    year = "1996",
    publisher = "Wellesley-Cambridge Press"
}

Ingrid Daubechies

Daubechies var den første, der konstruerede en ortogonal familie af kompakt støttede WT basisfunktioner (D4, D6, D8,...). F.eks. D4 - Daubechies diskretiserede skalerings- og Wavelet-funktion med hver 4 koefficienter.

En bedre FWT's algoritme

Wavelet funktionerne til anvendelse i FWT og WT kaldes nu for 1.generations Wavelets. I starten af 90'erne fandt nogle personer en mere generel Wavelet transformationsalgoritme. Fordelen er mindst en halvering af elementære operationer i forhold til FWT og transformationen kan udføres direkte på input-vektoren (eng. inplace). Algoritmen kaldes "The Lifting Scheme" og muliggør konstruktion af Wavelet baser på f.eks. kugleoverflader - de kaldes sfæriske Wavelets. Wavelets som kræver metoden, kaldes 2.generations Wavelets. Metoden lader sig let parallelisere.

The Lifting Scheme

(Søg efter "Wavelets and the lifting scheme: A 5 minute tour").
Her ligger der også mange andre interessante artikler.

The Fast Lifting Wavelet Transform

The Wavelet Lifting Scheme

[Vejviser] Amara Graph: Alt omhandlende Wavelet transformationer.

WT med heltalsaritmetik

Normalt benyttes flydende tals aritmetik til beregning af en WT. Men der findes Wavelet basisfunktioner, som muliggør beregning med heltalsaritmetik via "The Lifting Scheme". I [Strang96] side 216-218 kaldes de binlets. De er biortogonale. Det betyder at transformationsmatricen baseret på binlets er invertible, men ikke ortogonale:
http://www.cs.kuleuven.ac.be/~wavelets/
@techreport{Uytterhoeven97a,
    author = "Geert Uytterhoeven and Filip Van Wulpen and Maarten Jansen and Dirk Roose and Adhemar Bultheel",
    booktitle = " WAILI: Wavelets with Integer Lifting, Report TW 262, July 1997",
    institution = "Katholieke Universiteit Leuven, Department of Computer Science",
    number = "262",
    pages = "2,1-21",
    year = "1997",
    url = " http://www.cs.kuleuven.ac.be/publicaties/rapporten/tw/TW262.ps.gz",
    note = "C++"
}

En anden artikel, som beskriver "map integers to integers" via simpel heltals afrunding i Lifting-beregningerne. Herved mistes linearitets egenskaben:
(Søg efter "Wavelet transforms that map integers to integers")
@article{Daubechies98,
    author = "R. Calderbank and I. Daubechies and W. Sweldens and B.-L. Yeo",
    title = "Wavelet transforms that map integers to integers",
    journal = "Applied and Computational Harmonic Analysis (ACHA)",
    volume = "5",
    number = "3",
    pages = "332-369",
    year = "1998",
    url = " http://cm.bell-labs.com/who/wim/papers/integer.ps.gz"
}

Blandet

MathSoft: Wavelet Resources (Webarchive backup)

Her er en internet adresse til en MatLab pakke Wavelab:
@manual{WaveLab96,
    author = "J. Buckheit and S. Chen and D. Donoho and I. Johnstone and J. Scargle",
    booktitle = "About WaveLab",
    institution = "Stanford University",
    edition = "0.701",
    year = "1996",
    url = " http://www-stat.stanford.edu/~wavelab/Wavelab_850/download.html"
}
Filen "WaveLab .701:Orthogonal:MakeONFilter.m" indeholder de diskretiserede basisfunktioners koefficienter. Her er også koefficienter til Wavelet basens filterbank Symmlet.

Den matematiske udledning af WT er i følgende bog. FWT er udledt i kapitel 7:
@book{Kaiser94,
    author = "Gerald Kaiser",
    booktitle = "A Friendly Guide to Wavelets",
    edition = "1",
    year = "1995",
    publisher = "Birkh{\"a}user"
}

Adresse til bogen "Numerical Recipes" med Wavelet implementation. Billederne i slutningen af 13.10 viser WT anvendt til kompression. Led efter "13.10 Wavelet Transforms 591":
@book{press94,
    author = "William H. Press and William T. Vetterling and Saul A. Teukolsky and Brian P. Flannery",
    booktitle = "Numerical Recipies in C: the art of scientific computing",
    edition = "2",
    year = "1994",
    publisher = "Cambridge University Press",
    url = "http://www.nr.com/nronline_switcher.html"
}

Denne afhandling benytter Wavelet til preprocessering ved mønstergenkendelse (se i afsnit 4.3.5 side 50):
@phdthesis{Tate96,
    author = "Anne Rosemary Tate",
    booktitle = "Pattern Recognition Analysis of In Vivo Magnetic Resonance Spectra",
    school = "University of Sussex at Brighton",
    volume = "432",
    year = "1996",
    note = "Cognitive Science Research Papers"
}

Beskrivelse af kodingsalgoritmen SPIHT anvendt med 2D PWT:
Welcome to the WWW home page that describes Set Partitioning in Hierarchical Trees (SPIHT): the powerful new wavelet-based image compression method.

Internet adresser til mange koefficienter til Wavelet basers filterbanker:
http://phase.etl.go.jp/phase/wavelet/ in the file coeff.tar.Z
ToolSmiths® FirWav Page: A Brief Introduction to the FirWav Filter Library.

Wavelet komunikation

Moving at Wavelet speed
Wavelet modulation can help squeeze more out of existing networks By Mark Laubach, Office of the President and CTO, Rainmaker Technologies Inc.

Wavelet modulation performance in Gaussian and Rayleigh fading channels Manish J. Manglani and Amy E. Bell HTML , PDF

January 31, 2002 Soon, It's Gonna Rain
A New Modulation Technology [Wavelet modulation] Promises to Turn Your Cable TV Connection Into a 10 Gigabit-Per-Second Digital Fire Hose

"...Wavelet modulation--also referred to as fractal modulation -- simultaneously sends data at multiple rates through an unknown channel. This novel multirate diversity strategy offers improved message recovery over conventional modulation techniques:..."

Wavelet anvendelser

JP2 is the file extension for the new image format called JPEG2000 based on state-of-the-art wavelet compression.

LuraWave.jp2 Photoshop Plug-In , LuraWave.jp2 (JPEG2000)

Fnord: j2k is a free plug-in for [PhotoShop] reading and writing the JPEG 2000 file format, the successor to JPEG.

Jpeg.org: JPEG2000 - final CD "... Anyone implementing software according to the description available in this FCD, risks not being compliant with the final JPEG2000 International Standard (IS), which is due to be published some time in 2001 as IS15444-1. ..."

BERLIN The International Standards Organization's JPEG2000 committee has finalized specs for a new algorithm that compresses images up to 200 times with no appreciable degradation in quality. The JPEG2000 spec, which will become ISO 15444 when it's officially approved in 2001, uses wavelet transformations instead of Fourier transforms to achieve the performance gain.

XnView is a utility for viewing and converting graphics files (FREEWARE for non-commercial use). (incl.JP2) ( Linux )

MacOS: GraphicConverter supports new technologies like the LuraWave (LWF) wavelet compression

SouthDowns Perl software for creating JPEG 2000 files

Kakadu: A comprehensive, heavily optimized, fully compliant software toolkit for JPEG2000 developers

JPEG2000: The next generation still image compression standard

TECHNOLOGY DEVELOPMENTS JPEG 2000 by Dunc Petrie

Scalable Streaming of JPEG2000 Images using Hypertext Transfer Protocol

Chris Raile, Zerotree Based Wavelet Image Compression
"...The following compressed images originated as uncompressed 24-bit (true-color) Targa files. They were then converted to the YCbCr colorspace, decomposed using the "2-6" wavelet, then the wavelet coefficients were encoded using a zerotree representation. In all cases the chromanance information (Cb and Cr) was severely subsampled; in two of the examples, only two chromanance wavelet coefficients were stored for every 128 luminance (Y) coefficients. The images were then reconstructed and stored using the Targa format.
..."

Dartmouth, Geoff Davis: Wavelet Image Compression Construction Kit

Information Coding Laboratory: Robust Image Compression PZW; Wavelet zerotree image compression with packetization.

PZW Wavelet zerotree image compression with packetization "... We present here the results of our latest noise robust codec. We've used a variation of the SPIHT and PZW encoders as a basis for a Packetized Wavelet Zerotree Compression scheme (EZW). The algorithm de-interleaves the output bitstream from the encoder into sub-groups, each of which corresponds to a localized region of the image. These are then selectively re-interleaved and combined into fixed-length packets. Each transmitted packet is self-decodable. Packet erasure is concealed with simple 8-neighbor interpolation.
The full version of the paper which has been submitted for DCC '98 is available here(~4.5MB Postscript). An abbreviated version was recently accepted for publication in IEEE Signal Processing Letters. ..."

EZW encoding (Embedded Zerotree Wavelet)

New Approximations for Avoiding Gibbs Phenomenon in Wavelet Subspaces

Wavelet Lossless Compression of Coronary Angiographic Images

(Macintosh) G4 Velocity Engine implementation of Wavelet transform "...There are various approaches to wavelet processing of color images, and machine architecture dictates in large measure which algorithm is optimal. This sample is a Velocity Engine (G4) implementation in which pixels are processed as four-dimensional (RGBA) vector entities. In this mode the vector machinery performs the (Daubechies D4) wavelet algebra in only three vector operations per pixel.
We also implemented a more standard, channel-correlation scenario, with YUV-decomposed RGB images (with UV sub-sampling) and a biorthogonal (Burt 5/7) wavelet transform applied thrice. A key to these fast vector implementations is the adoption of certain rational approximations-we call "shift-rational" forms-to the true wavelet coefficients, allowing for efficient Velocity Engine arithmetic. Other Velocity Engine enhancements include very fast subsampling for the UV channels, via vector-average instructions.
Timing experiments show a Velocity Engine speedup of 5x or more over corresponding scalar (G3) implementation in the RGBA approach. For the YUV approach, the speedup is likewise impressive, with a complete inverse-wavelet-YUV image reconstruction on a 320-by-240 full color image taking less than 0.005 second on 300 MHz. G4..."

(Macintosh) G4 Velocity Engine implementation of fast Fourier transform (FFT) and associated convolution/correlation routines.

MeVis Technologies: MT- WICE Photo "...the new tool for excellent image compression ... lossless compression and lossy compression up to 200:1 ... better quality than JPEG and many other wavelet-based image compression products ... Try MT-WICE Photo for Windows 95/98/NT/2000 and Apple MacOS now! ..."

MeVis Technologies: Photoshop shareware Wavelet Plug-in til Macintosh og Windows

LuraTech LuraWave Free viewer & browser plug-in for MacOS and Windows. "...LuraWave is a state-of-the-art file format that uses wavelet-based compression to reduce file sizes while achieving better image quality than conventional methods such as JPEG and TIFF..."

LuraTech LuraDocument Free viewer & browser plug-in for MacOS and Windows. "...LuraDocument optimizes compression by processing text and image data separately, applying best suited compression algorithms for the different data structures. LuraDocument encoder software performs an image analysis that separates the original document into text and image regions. Text regions are then compressed using a state-of-the-art bitonal compression algorithm while the image regions are compressed using LuraWave, our patented wavelet-based image compression technology...."

LizardTech MrSID - A Master of Raster Image Compression: MrSID Viewer & MrSID Browser Plug-in 1.3 for MacOS and Windows, "...MrSID utilizes a wavelet transform-based algorithm to achieve both the efficient storage and retrieval of digital images of very large dimensions. ..."

MrSID Photo Solo for MacOS and Windows, download for free (14-4-2001)

USA Video Interactive: streaming video

Summus: Wavelet Image Software Developer's Kit (SDK)

MacInTouch Report: JPEG2000 and Wavelet-based Compression

Gormish Notes on JPEG2000

Datacompression conference

...project proposal by CRF, EPFL and ERICSSON to develop a Java (TM) implementation of JPEG2000. This project is named JJ2000. ... The objectives of JJ2000 are to: accelerate convergence of the JPEG2000 standardisation process...

webreview.com - JPEG 2000 More Than New Millennium Buzz

Pegasus Imaging: PICTools & Wavelet2000 "... Touted as one the most efficient image compression technologies available, Pegasus Imaging Corporation has added a full wavelet compression implementation within the PICTools Medical Compression Toolkit for still image compression and Wavelet2000 for streaming low bandwidth video. Still image compression libraries are available in the PICTools Medical Compression Toolkit while Wavelet2000 utilizes a wavelet based interfame coding technology for low bandwidth video. ..."

MIT TechRewiev profile: Wim Sweldens

JPEG Related links

SPIE - The International Society for Optical Engineering: Wavelet Applications in Signal and Image Processing VII

SPIE - The International Society for Optical Engineering: Wavelet Applications in Signal and Image Processing VIII (AM210), Year 2000

SPIE - The International Society for Optical Engineering: Wavelet Applications in Signal and Image Processing, current year

Proceedings of the I.E.E.E. International Conference on Acoustics, Speech and Signal Processing (ICASSP-95), Detroit, Mi., May, 1995. Frequency and Spatially Adaptive Wavelet Packets

http://math.yale.edu/pub/wavelets/index.html

Wavelet.org, Wavelet Digest

List of Wavelet People (mirror)

hovedside , spejl/mirror

Glenn Møller-Holst