Low-complexity scalable video coding through table lookup VQ and index coding

The Internet community is very heterogeneous in terms of access bandwidth and terminal capabilities, hence, there is much interest for low-computation, software-only, scalable video coders that guarantee universal access to video communication. Scalability allows users to achieve a fair quality of service in relation to their resources. Low complexity, on the other hand, is necessary in order to ensure that also users with low computing power can be served. In this work, we propose a multiplication-free video codec, whose complexity is much reduced with respect to standard coders at the price of a limited increase in memory requirements. To this end we resort to very simple coding tools such as table lookup vector quantization (VQ) and conditional replenishment.We start from the simple coder proposed in [1], which already guarantees high scalability and limited computational burden, and improve upon it by further reducing complexity, as well as the encoding rate, with no effect on the encoding quality. The main innovation is the use of ordered VQ codebooks, which allows the encoder to generate correlated indexes, unlike in conventional VQ. Index correlation, in turn, allows us to carry out conditional replenishment (the most time-consuming operation in the original coder) by working on indexes rather than on block of pixels, and to reduce drastically its complexity. In addition, we also take advantage of the correlation among indexes to compress them by means of a predictive scheme, which leads to a 15-20% rate reduction in the base layer, without significant increase in complexity. Thanks to these and other minor optimizations we have obtained improved performance and, more important, a 60-70% reduction of the encoding time (on a general purpose machine) with respect to [1].