Also, I'm not an image compression expert, but I wonder if you could use this technique as a pre-pass before a more standard image compression algorithm to improve the overall results. In other words, maybe subtract the image created using the polygons from the original image and then compress the result using JPEG (or something else more suitable?).
1. The pixels in the output image should be close in value to the corresponding pixels in the input image.
2. Neighboring pixels in the output image should have similar values.
I wonder if anyone has compared compression techniques using these sorts of assumptions.
Also, wavelets are not at all "provably optimal." The only "provably optimal" transform is the KLT, and even that isn't really, since in practice overcomplete transforms tend to have better compression efficiency than complete ones, at the cost of turning compression from a simple O(nlog(n)) frequency transform into an NP-complete problem of matching pursuits.