Today’s Mindboggler: 1000:1 compression ratios?
A few posts ago, I wondered aloud what applications would be good for quantum GPUs. Here’s one.
Roger Alsing brings us:
Genetic Programming: Evolution of Mona Lisa
This is a classic example of a highly asymmetric compression/decompression scheme. It takes an impossibly long time to find a good “fit” candidate model for compression, but once you do, it takes very little bytes (and very little time and complexity) to tell a decoder how to reconstruct the image.
What this does is use a genetic algorithm to “refine” a list of transparent, overlapping polygons to best represent a given reference image. It takes a long time to run the “encoder”, but what it spits out at the end of a few hundred thousand iterations is a short list of transparent polygons, say, 70… that when overlaid give a good approximation of the reference image.
The polygon colors and points can be “transmitted” with entropy coding in an impossibly small amount of bandwidth, and the “decoder” only needs to render a few polygons — a triviality that even an Intel GMA 900 GPU can perform in less than a nanosecond.
The encoding, however … takes a good deal longer. The takeaway here is that if someone builds a CPU or GPU that can perform 18 Yottaflop, someone will find a way to chew it all up, fruitfully.
Also, Mr. Alsing has posted the source code and windows binaries for this, so you can even play around with it yourself.