Computation-distortion characteristics of JPEG encoding and decoding

A distortion-computation function D(C) is defined as the minimum expected distortion in computing some quantity-using an algorithm from a predefined set of algorithms-while using no more than C computational units. When the computational problem is to encode at rate R, this gives slices of a computation-rate-distortion surface. This framework is used in the analysis of a family of JPEG coders that use output-pruned DCT calculations in place of some full DCT calculations. For encoding the Lena image at 0.5 bits/pixel, this yields a 30% reduction in complexity while lowering the PSNR by only 0.4 dB. The decoding complexity can be similarly reduced.