On the rate distortion theory for causal video coding

Causal video coding is considered from an information theoretic point of view, where video source frames X₁, X₂, ..., X_N are encoded in a frame by frame manner, the encoder for each frame X_k, k = 1, ..., N, can use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame X_k itself is modeled as a source X_k = {X_k(i)}_i=1 ^infin. A novel computation approach is proposed to analytically characterize, numerically compute, and compare the minimum total rate of causal video coding R_c(D₁, ..., D_N) required to achieve a given distortion (quality) level D₁, ..., D_N ges 0. Specifically, we first show that for jointly stationary ergodic sources X₁, X₂, ..., X_N, R_c(D₁, ..., D_N) is equal to the infimum of the nth order total rate distortion function R_c,n(D₁, ..., D_N) over all n, where _Rc,n(D₁, ..., D_N) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then present an iterative algorithm for computing R_c,n(D₁, ...,D_N) and demonstrate the convergence of the algorithm to the global minimum. The global convergence of the algorithm further enables us to establish a single-letter characterization of R_c(D₁, ...,D_N) in a novel way when the N sources are an independent and identically distributed (IID) vector source. With the help of the algorithm, we also demonstrate a surprising result (dubbed the more and less coding theorem-under some conditions on source frames and distortion, the more frames need to be encoded and transmitted, the less amount of data has to be actually sent. Predictive video coding, wher- e each encoder and its corresponding decoder can use only all previous encoded frames, is also investigated.