The Computational Approach to Lossy Compression and its Applications to Image/Video Coding

Ever since rate distortion theory was introduced by Shannon in 1948 and particularly in 1959, it has been recognized that it provides in principle a theoretical basis for many practically important lossy compression problems. More than a half century later, it is fair to say that the rate distortion theory in Shannon probabilistic sense has not yet yielded such profound impact on practice as one might conceive. The major limitation of the rate distortion theory in Shannon probabilistic sense lies in two aspects: (1) modeling—the theory in Shannon probabilistic sense often assumes analytically tractable source models such as stationary sources and yet real-world data are often nonstationary and may not fit into any analytical model; even if they do, such a model is very difficult to construct; and (2) separation—the theory in Shannon probabilistic sense is often concerned with asymptotic performance, and lossless coding/reproduction sequence space is either decoupled from quantization or completely ignored. In this talk, we will present the computational approach to lossy compression which has been quietly developed in recent years by the speaker and others. Unlike Shannon probabilistic approach, the computational approach does not assume any model for the data to be encoded; it fully integrates lossless coding, reproduction sequence space, and quantization into one optimization problem. When data to be encoded are actually stationary, the computational approach coincides with Shannon probabilistic approach. We will also discuss the recent successful applications of the computational approach to image and video coding, and its impacts on the design of future image and video coding standards.