Python implementation of wavelet rasterization(github.com) |
Python implementation of wavelet rasterization(github.com) |
However, it really isn't much of an introduction to what wavelets are, or what they might be good for in general and why.
They are quite interesting mathematical objects. I think their study was hindered somewhat for a while by functional analysts thinking they were too applied and engineers thinking they were too abstract.
You'll often hear that wavelets are faster than Fourier based methods, because the DWT is O(n) while FFT is O(n log(n)), but that doesn't hold up when the FFT window is a fixed size (as in the case of JPEG). Since JPEG uses a window size of 8px, the "log n" is 3, whereas JPEG 2000 uses a wavelet with 8 coefficients. So it's basically O(n) in both cases, with a much larger constant factor on JPEG 2000's DWT.
There’s a large literature of rasterization techniques. Does anyone have insight into when this one would be useful?
Here are some other recent papers:
http://research.microsoft.com/en-us/um/people/cloop/LoopBlin... http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html
What are the most common rasterizer algorithms currently in use by vectorgraphics software? I mean pdf readers, postscript renderers, font renderers, etc...
As for the zigzag path, it doesn't run through the 64 pixels, but rather through the 64 coefficients that come out of the DCT. That's part of the coding stage, which is a separate animal. That said, JPEG's coding scheme is way simpler, and probably way faster than JPEG 2000's, so that might also have something to do with the perf difference.
My overall impression of JPEG 2000 is that it seems like they started with "wavelets can surely be used to achieve superior image compression to JPEG", and then made whatever sacrifices were necessary, in terms of implementation complexity and computational resources, to bear out that premise. You could make similar sacrifices and beat the hell out of JPEG with a DCT-based codec too (e.g. with larger windows, overlapping transforms, better psychovisual models etc.)
A linearly-separated 2D 8×8 DFT should involve 6 butterflies per pixel, no? And I guess a 2D DWT with 8 coefficients results in 16 multiply-accumulates per pixel? Does it depend on the order of the DWT?
Not sure what you mean by the order of the DWT. Do you mean how deep you transform (how many levels of the transform you apply), or the number of taps on the filter?
It definitely depends on the number of taps on the filter.
IIRC, as for the depth DWT down to one scale coefficient is still O(N) (although there's another constant factor multiplied on beyond the number of filter coefficients). Even if you only do two levels, I believe you only cut the time in half, and you lose a lot of opportunity for compression if you do. I'm not sure what depth JPEG 2000 goes to, but it's probably more than three, so I think you can largely discount any perf gains there.