As the name implies, this is my take on wavelet-based image compression. First off, I'll excite you with a list of "Cool Things"(tm) about it, and then I'll give an overview of how it's done!
Download wavelet.zip (sources included, GPL'd).
There's also a test-page with installation instructions and some samples to check it is all working...
I've now also written a browser-plugin which can be used to embed WKO-images into web-pages. It is based on the
WebBMP plugin by Jason Summers. He placed his code in
the public domain (many thanks for that), and he assured me it's allright to include the derived source, too.
The (completely multi-threaded) plugin seems to work in Internet Explorer (newer versions of that need to install the registry-file to enable
Netscape-compatible plugins to work) [6.0 tested], Opera [6.02 tested] and Netscape Navigator [4.72 tested], but I'm not too
confident on the "Printing"-support of the plugin.
Progressive transmission is taken full advantage of (if your connection is slow enough to need it ;)), files can be saved as
both .wko and .bmp. The "View Image" context menu only works in Opera and Netscape (maybe because the IE-plugin emulation does not
provide fullscreen support?).
To display such images in web-pages use:
<embed src="lena_col.wko" type="image/wko" width="512" height="512">
We start by computing a complete wavelet-transform using the Cohen-Daubechies-Fevereau (2,2) biorthogonal wavelet
(which incidentally seems to be the same as used for lossless JPEG2000, but they call it a (5,3)?). For this, the image
needs dimensions which are a power of 2. To achieve this, I simply repeated the last column and row of the image as
necessary.
Then the coefficients are "reordered" into a one-dimensional array by octave-bands (and using "Fractal Z"-ordering
within each octave, outputting coefficients from HD (horizontal detail) block first, followed by the VD (vertical detail) coefficients,
and finally the DD (diagonal detail) coefficients, i.e. in chunks of three interleaved coefficients).
Each of these blocks is then quantised and encoded independently using adaptive run-length Rice coding (Golomb coder of
order 2^k) from the most-significant bitplane to the least-significant one. Only the coefficients whose most-significant
bit has not yet been encoded are included in this run-length coding; all other bits (i.e. the ones
whose most-significant bit(s) have already been encoded) are written directly (called refinement bits).
To keep the progressive transmission / embedded bit-stream property for multi-channel images, their blocks are
coded interleaved.
This is were things get interesting. I construct a "possible refinement tree" (although it's not really a tree),
which works as follows:
For each block and for each possible quantiser setting for that block (restricted to powers of 2), compute by how much
that block (with a particular quantisation) improves the image and how many bits it takes up. This is now done by an
error estimation routine which (IMO) should be mathematically correct, but isn't... Help? Have a look at the included
Mathematica-notebook for the derivation of this estimate. Anyway, it seems to be good enough!
A recursive routine then tries to find the best "path" (using one quantisation setting for each of the blocks) through
this "tree" that yields the best error performance (computed as sum of errors incurred by each block) within a given number
of bits (size-constrained) or satisfies the prescribed maxium error with the least number of bits (quality-constrained).
Let me tell you, recursion can be hard to get working correctly... If if you calculate with floats, it gets even worse... ;)
The new (even more) approximate error-estimator simply computes the statistically average deviation from a standard
dead-zone quantiser with a given quantisation...
| that's it, folks... © 2002-2003 Daniel Vollmer [maven] |
comments & suggestions to: maven@maven.de |