5 ms·
Python implementation of wavelet rasterization
- leni536 11y agoApparently 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...
- muizelaar 11y agoMost rasterizers typically use some kind of super-sampling scanline conversion: http://lists.cairographics.org/archives/cairo/2007-July/011092.html http://lists.cairographics.org/archives/cairo/2007-July/0110...
- stuaxo 11y agoThis looks like a perfect thing to try various python optimisations/optimisers on - numba, pypy, cython and shedskin to name 4.
- jacobolus 11y agoHere’s the paper, which I haven’t read yet. http://faculty.cse.tamu.edu/schaefer/research/wavelet_rasterization.pdf http://faculty.cse.tamu.edu/schaefer/research/wavelet_raster... 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/LoopBlinn05.pdf http://research.microsoft.com/en-us/um/people/cloop/LoopBlin... http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html http://w3.impa.br/~diego/projects/GanEtAl14/ http://w3.impa.br/~diego/projects/GanEtAl14/ https://developer.nvidia.com/gpu-accelerated-path-rendering https://developer.nvidia.com/gpu-accelerated-path-rendering
- onion2k 11y agoWavelets 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.
- ska 11y agoThey 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.
- kragen 11y agoWell, 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_to_jpeg_that_never_made_it_big https://lobste.rs/s/oxuu1k/jpeg_2000_the_better_alternative_....
- mistercow 11y agoIt's probably slower because of the wavelets. 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.
- kragen 11y agoDoesn't JPEG use a window size of 8×8 = 64px, with a sort of boustrophedon diagonal path through those 64 pixels?
- kastnerkyle 11y agoIf 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/ http://kastnerkyle.github.io/posts/wavelets/
- ska 11y agoI see the "how [some of them] can be used [in numpy]" part there, it looks pretty good for that purpose. However, it really isn't much of an introduction to what wavelets are, or what they might be good for in general and why.
- chestervonwinch 11y agoI agree. Write a prequel GP! :)
- astazangasta 11y agoWhy does Python code always look like assembly code? Is this just laziness on the coder's part or is Python inherently unreadable?
- sp332 11y agoI've always found Python to be pretty readable. Are you just talking about the matrix math, or the rest?
- astazangasta 11y agoAll of it. The 40 line methods with no self documenting variables, order or sense.
- sp332 11y agoIt's probably transliterated right out of a math textbook into Python.
- kragen 11y agoMy 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.