Evolving an image out of polygons
screamingduck.com
screamingduck.com
But I should point out that, while a fun hack, this is not really a viable compression method in practice.
[1] Original paper: http://scholar.google.com/scholar?cluster=703822277846437904...
[2] Some easier-to-understand slides about it: http://www.cs.unc.edu/~lazebnik/research/fall08/jia_pan.pdf
[3] Someone's project implementing it: http://www.cs.brown.edu/courses/csci1950-g/results/proj2/edw...
* http://news.ycombinator.com/item?id=392036
* http://news.ycombinator.com/item?id=389727
* http://news.ycombinator.com/item?id=503811
* http://news.ycombinator.com/item?id=450886
(this is still an excellent post however)
- [one of the dudes who wrote 9 Fingers](http://www.youtube.com/comment?lc=9Y2eZp3mPIlNEaQPjdPLHJ3xls...)
I would not be surprised if the algorithm used to compress the video into polygons was called "tracing it by hand". I'm pretty sure I've read that was the algorithm used for their earlier video-focused demo "State of the Art".
I did not know that for "state of the art" they drew the vectors by hand. Which is basically what Eric Chahi did for Another World back then, using rotoscoping. I am assuming that the technique they used for "9 fingers" is different though. They are WAY more vectors in 9 fingers than in State of the Art, and that would take a huge amount of time to reproduce them on screen. I am pretty sure they found a smarter way to do it (you can guess this from the fact that the video reproduction in vectors is almost perfect in 9 fingers, while in state of the art the animation is sometimes jerky and they use shadows/blur/changing background to hide the imperfections).
The demoscene is/was amazing. One downside of everything going through browsers is that people have lost the ability to talk directly to the metal - it's what separated the men from the boys. Some of the Commodore 64 demos are absolutely incredible when you consider how few resources they have available. I think I'll be spending a few hours watching these Amiga demos...
Of course the error image will be much larger than the compressed image, but you have moved to the field of lossless compression so the bar is at a different level.
Algorithms designed to compress error maps should work on a different set of assumptions to plain lossless image compression. Error images are noisy but have an overall low magnitude.
I do wonder if there could be a entire field in collaborative image compression where multiple techniques can layer to try and achieve a better result. Algorithms would take an existing image and try and move it closer to the target while using as few bits as possible.
I specify "information theory bits" because they aren't really what you see in the computer's RAM; they're closer to "post-compression bits". But regardless, no matter how you move the encoding around there is no escaping information theory.