If anyone is interested in a beginner introduction to what wavelets are generally, and how they are used - I did a blog post a while back using numpy: http://kastnerkyle.github.io/posts/wavelets/
Wavelets were a big thing when I was at university (circa 1997). They were touted to be a giant leap in image compression along with fractals. Interesting to see people are still exploring that area of maths; much of the predicted technology never took off.
They actually have made pretty big inroads into signal processing and functional analysis more generally, they just aren't a shiny new thing anymore.
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.
Well, and in fact the wavelet-based JPEG-2000 standard does produce better visual quality at smaller file size than the DFT-based JPEG standard. JPEG-2000 compressors haven't been as broadly adopted, probably because they're slower. I'm not sure if that's because of wavelets, because of unoptimized implementations of JPEG-2000, or because some other aspect of the JPEG-2000 standard makes it more computationally intensive. There's further discussion at https://lobste.rs/s/oxuu1k/jpeg_2000_the_better_alternative_....
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.
Yes to the first part, but both the DWT and DCT are linearly separable, so you can compare their performance by just looking at one dimension.
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.)
I see! That makes more sense. Thank you for explaining?
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?
Apparently this technique calculates the exact pixel values from box filtering the "infinite" resolution polygons. I wonder if the same technique can be applied for circular or elliptical arcs.
What are the most common rasterizer algorithms currently in use by vectorgraphics software? I mean pdf readers, postscript renderers, font renderers, etc...
My experience is the opposite: Python code generally looks like executable pseudocode, the opposite extreme from assembly code. If you're finding this wavelet code unreadable, like I do, most likely it's because you don't understand the math it's implementing, like I don't.
This is the kind of massively parallelizable problem you want to put on the GPU. Python is mostly a good choice for a readable-code demonstration version.