Some time ago I wrote about how I was intending to use this blog to highlight research in DSP that is worth learning about so as to help starting constructive discussion about new DSP ideas or theories. I finally found the time to write about a paper I recently finished reading. The paper reference is:
B. Foo, Y. Andreopoulos and M. van der Schaar, “Analytical Rate-Distortion-Complexity Modeling of Wavelet-based Video Coder”, IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 56, NO. 2, FEBRUARY 2008, pp.: 797-815.
The paper can be found at ieeexplore or from one of the authors’ web pages at University College London
The title pretty much says it all what the paper is about. The paper presents an analytical model that accurately predicts the rate, distortion and decoding complexity of wavelet-based video coders. This main contribution is important because it is actually rare to find research presenting accurate analytical models of the rate, distortion or complexity in video codecs. Most of the works out there present some analysis but they invariably rely on exhaustive simulations to match some parameter or variable. This is not the case with this paper, which bases most of the analysis on deriving probabilities for the significance of blocks and coefficients with different quantization threshold. Also, the fact that the paper deals with the less common (at least for now) wavelet-based video coders is not really a problem because the analysis can be applied or extended in many cases to other types of video coders, which is another of the positives of this paper.
Besides the introduction, an overview, simulations and the conclusions, the paper has four main sections that describe quite well the flow of the paper: derivation of the probabilities for the significance of blocks and coefficients, analysis of rate approximation, analysis of distortion approximation, and analysis of complexity approximation.The derivation of the probabilities for the significance of blocks and coefficients has a number of operations that are worth citing. For once, it is interesting the statistical modeling of the significance of coefficient. Although not all the content here is new, I found the presentation to be very comprehensive and thorough. Another interesting part of the analysis in this section is the work with the erf and erfc functions. Coming myself from a background in communications I’m all too familiar with approximations for these functions but I found the treatment in this section (some actually in Appendices) to be different and useful for other many other derivations that include erf and erfc functions. Also, another very nice feature of this function is that it goes beyond the mathematical derivations to also provide some insight that I believe are useful for improving the coding efficiency of future codecs. Such is the case with the comments that most of the blocks within a subband become significant at the same bitplane, or at most at two consecutive bitplanes, or that the probability of significance of high-frequency spatio-temporal subbands is driven by a heavy-tail distribution based on a doubly stochastic model.
The following sections build on the expressions for the probabilities. There are a number of passages that are worth highlighting nonetheless. For example, there is some more work that is done with the useful approximations of expressions with the erf and erfc functions. One interesting observation also is that it is very difficult to compress the significance map encoding of quadtree structures due to their underlying distribution, which is another useful point to consider when designing codecs with improved efficiency. One other interesting concern during the analysis of the rate is that it was taken into consideration the exploitation of dependencies between neighboring coefficients.
Finally, the thorough analytical work in the paper gets underscored by a number of simulation results that show the accuracy of the analytical results as predictions for the actual codec behavior. One of the nice things about the results is that they show how the model developed in the paper can be used to control the tradeoffs between the different sources for complexity (entropy decoding, inverse discrete wavelet transform, etc.), and optimally configure the codec based on the specific performance strength and weaknesses. Along the same lines, the analysis seems as a useful tool to study tradeoffs between complexity and coding rate for a fixed video quality.
