A computation approach to the minimum total rate problem of 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 ^?. A novel computation approach is proposed to analytically characterize and numerically compute the minimum total rate R_c(D₁, ? ? ?, D_N) required to achieve a given distortion (quality) level D₁, ? ? ?, D_N ? 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 n^th order total rate distortion function R_c,n(D₁, ? ? ?, D_N) over all n, where R_c,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 vector source. Deep insights from the algorithm are also gained regarding how each frame should be encoded in order to achieve R_c(D₁, ? ? ?, D_N); it is demonstrated by example that R_c(D₁, ? ? ?, D_N) 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.