A promising direction to go would be to generate gradients using the polygons instead of colors directly and use Poisson blending [1,2] with gradient mixing [e.g. 3] to generate the final image from that. It would lead to many fewer noticeable artifacts at a similar compression ratio.
But I should point out that, while a fun hack, this is not really a viable compression method in practice.
Neat. After playing Out of this World a long time ago, I was wondering if it was viable to compress video data using polygons annotated image block overlays in the high-frequency/high-error areas. Looks like I might've been onto something, since it seems like polys alone are pretty good at capturing the image.
This has been done a very long time ago when the demo group Spaceballs released "9 fingers" on Amiga, where a number of video sequences were reproduced entirely in polygons. There were artifacts but the effect was impressive at that time, when MPEG-1 decompression was impossible on such low-power machines. You can check the effect on youtube. I do not know what tools they used to compress the video into polygons, though.
"As far as I remember, we used a S-VHS camcorder and replayed the video with a VHS-player capable of showing the video one frame at the time with a certain degree of "stableness". Then we digitized the frame with a normal digitizer (DigiView?). Custom software were then used to "vectorize" the images. But all this is a little hazy. It's been "a few" years since I called myself Dark Helmet..."
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".
Thanks for your answer - very interesting. You must have owned an Amiga if you know this matter in so great details :)
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...
Yeah, the demoscene has always been full of surprises, especially on low-end hardware. About those amiga demos, they run fine with Amiga Emulators such as WinUAE, so you can check them out for yourself fairly easily.
Would it make sense to include the error image in the format to make the compression lossless? As I see it, if the final fitness is high enough, the error image should be highly compressible?
I have looked to see what existing research there is on doing that but found very little. Obviously the error image is compressible, it has patterns in it that are visible, and it is predominantly greyish. Those are aspects that can be exploited.
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.
That's not really true. The residuals of a good lossy compression algorithm ought to look like uncorrelated noise with a smaller dynamic range than the original image, and the second fact (smaller dynamic range) makes them compressible.
That doesn't make any sense. You've taken an image with arbitrary bytes, and turned it into one where the bytes are tightly centered around a small range of values.That's perfect for Golomb coding (for instance.)
No free lunches. For a lossless compressor, (Information theory bits of polygons) + (Information theory bits of remaining error) >= (Information theory bits of original image), where the > represents the possibility that the first two elements aren't perfectly separated by your process or have inescapable overlap.
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.
Obviously. That's the definition of compression. If the image is well modeled by overlapping polygons + small residuals, the encoding will better approach the uncomputable ideal, and thus, compress.
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...