Causal video coding is a coding paradigm where video source frames X1, X2,..., XNare encoded in a frame-by-frame manner, the encoder for each frame can use all previous source frames and all previous encoded frames, and the corresponding decoder can use only all previous encoded frames. In the special case where the encoder for each frame Xkis further restricted to enlist help only from all previous encoded frames, causal video coding is reduced to predictive video coding, which all MPEG-series and H-series video coding standards proposed so far are based upon. In this paper, we compare the rate distortion performance of causal video coding with that of predictive video coding from an information theoretic perspective by modeling each frame Xkitself as a source Xk={Xk(i)}i=1∞. Let Rc*(D1,...,DN) (Rp*(D1,...,DN), respectively) denote the minimum total rate required to achieve a given distortion level D1,...,DNin causal video coding (predictive video coding, respectively). We first show that like Rc*(D1,..., DN), for jointly stationary and totally ergodic sources X1, X2,..., XN, Rp*(D1,...,DN) is equal to the infimum of the nth order total rate distortion function Rp,n(D1,...,DN) over all n, where Rp,n(D1,...,DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then prove that if the jointly stationary and totally ergodic sources X1,..., XNform a (first-order) Markov chain, we have Rp*(D1,...,DN)=Rc*(D1,...,DN). However, this is not true in general if X1,..., XNdo not form a (first-order) Markov chain. Specifically, we demonstrate that for independent and identically distributed vector source (X1,..., XN), if X1,..., XNdo not form a (first-order) Markov chain, then under some conditions on source frames and distortion, Rc*(D1,..., DN) is strictly less than Rp*(D1,..., DN) in general. Our techniques allow us to compare Rp*(D1,..., DN) with Rc*(D1,..., DN) even when the single-letter characterization of Rp*(D1,..., DN), if any, is unknown.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ..., XNare encoded in a frame by frame manner, the encoder for each frame Xkcan use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i) }i=1∞. A novel computation approach is proposed to analytically characterize, numerically compute, and compare the minimum total rate of causal video coding Rc*(D1, ...,DN) required to achieve a given distortion (quality) level D1, ...,DN>; 0. Among many other things, the computation approach includes an iterative algorithm with global convergence for computing Rc*(D1, ...,DN) . The global convergence of the algorithm further enables us to demonstrate a somewhat 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 after encoding has to be actually sent. With the help of the algorithm, it is also shown by example that Rc*(D1, ...,DN) is in general much smaller than the total rate offered by the traditional greedy coding method. As a by-product, an extended Markov lemma is established for correlated ergodic sources.

An improved iterative algorithm is first proposed to calculate the rate-distortion performance of causal video coding for any continuous sources. Instead of using continuous reproduction alphabets, it utilizes finite reproduction alphabets and iteratively updates them along with transitional probabilities from the continuous source to reproduction letters, thus overcoming the computation complexity problem encountered when applying the algorithm recently proposed by Yang et al for discrete sources to continuous sources. The proposed algorithm converges in the sense that the rate-distortion cost is monotonically decreasing until a stationary point is reached. It is then applied to practical video data to establish some theoretic coding performance benchmark. In comparison with H.264, experiments show that under the same motion compensation setting, causal video coding offers a roughly 1 dB coding gain on average over H.264 for the IPPIPP...GOP structure. This suggests that an area one could explore to further improve the rate-distortion performance of H.264 be how quantization and coding should be performed conditionally given previous frames and coded frames and given motion compensation.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ? ? ? XNare encoded in a frame by frame manner, the encoder for each frame Xk, 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 Xkitself is modeled as a source Xk= {Xk(i)}i=1?. A novel computation approach is proposed to analytically characterize and numerically compute the minimum total rate Rc(D1, ? ? ?, DN) required to achieve a given distortion (quality) level D1, ? ? ?, DN? 0. Specifically, we first show that for jointly stationary ergodic sources X1, X2, ? ? ?, XN, Rc(D1, ? ? ?, DN) is equal to the infimum of the nthorder total rate distortion function Rc,n(D1, ? ? ?, DN) over all n, where Rc,n(D1, ? ? ?, DN) 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 Rc,n(D1, ? ? ?, DN) 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 Rc(D1, ? ? ?, DN) in a novel way when the N sources are an independent and identically distributed vector source. Deep insights from the algorithm are also gained regarding how each frame should be encoded in order to achieve Rc(D1, ? ? ?, DN); it is demonstrated by example that Rc(D1, ? ? ?, DN) is in general much smaller than the total rate offered by the traditional greedy coding method by which each frame is encoded in a local optimum manner based on all information available to the encoder of the frame. In addition, a tight achievable rate distortion region is also derived.