Optimized construction of linear approximations to image data

We present a method for the efficient construction, optimization, and storage of linear approximations to image data. A general simulated annealing-based optimization technique is adapted to the specific problem of optimizing image approximations. A linear approximation is defined by a triangulated subset of the source image pixels and the quality of an approximation may be judged with reference to a computed mean or RMS per-pixel difference between the source image and the approximation. A greedy algorithm for the construction of an initial configuration is described for which the spatial distribution of approximation points rejects the distribution of detail in the image. The approximation is optimized by a sequence of reconfiguration steps chosen according to a simulated annealing process. We outline an efficient implementation of the optimization procedure, explore fast error-recalculation methods, and describe an approximation-compression technique that allows efficient storing, transmission, and viewing of the final approximations. Test results are provided to illustrate the performance of the approximation construction pipeline.