Wavelet transform might work for you, but you should know that it doesn't differ from the mean by much.Indeed, they don't (since it's the mean what's being used in the predict step). Though of course there are some quite different (much more complicated) wavelets, too. The reason why I pointed them out is that I find the representation of the data extremely convenient for an application that handles heightfields.
You can reconstruct any level of detail you want simply by leaving away some amount of data at the end. No special code, just stop early. And, it gives a good solution to streaming terrain, with progressive refinement. All the same, using the same algorithm with no special paths, and at a very affordable cost computation-wise.
I'm not even going to mention that it lends to (both lossless and lossy) compression. It's just a darn cool representation :-)