I'd be curious to know how this stacks up in terms of speed and quality.
EDIT: Oh yes, and there's also "Image Compression Using
Data-Dependent Triangulations" and "Survey of Techniques for Data-dependent Triangulations Approximating Color Images", both by Lehner et al., 2007. I don't mean to discourage you here, just pointing out the bar to be beaten. It's a cool idea.
See e.g. http://scribblethink.org/Courses/ScatteredInterpolation/scat...
I may have to read further, though. That's a lot of math.