Digital image and video coding has witnessed rapid development in the past decades. Conventional hybrid motion-compensated-prediction (MCP) based video coding exploits both spatial and temporal redundancy at the encoder. Hence the encoder requires much more computational resources than the decoder. This poses a challenge for applications such as video surveillance systems and wireless sensor networks. Only limited memory and power are available at the encoder for these applications, while the decoder has access to more powerful computational resources. The Slepian-Wolf theorem and Wyner-Ziv theorem have proved that a distributed video coding scheme is achievable where sources are encoded separately and decoded jointly. The basic goal of our research is to analyze the performance of the low complexity video encoding theoretically, and to design new practical techniques to achieve a high video coding efficiency while maintaining low encoding complexity.

In this thesis, we propose a new backward channel aware Wyner-Ziv approach. The basic idea is to use backward channel aware motion estimation to code the key frames in Wyner-Ziv video coding, where motion estimation is done at the decoder and motion vectors are sent back to the encoder. We refer to these backward predictive coded frames as BP frames. A mode decision scheme through the feedback channel is studied. Compared to Wyner-Ziv video coding with INTRA coded key frames, our approach can significantly improve the coding efficiency. We further consider the scenario when there are transmission errors and delays over the backward channel. A hybrid scheme with selective coding is proposed to address the problem. Our results show that the coding performance can be improved by sending more motion vectors to the encoder. However, there is a tradeoff between complexity and rate-distortion performance in backward channel aware Wyner-Ziv video coding. We present a model to quantitatively analyze the complexity and rate-distortion tradeoff for BP frames. Three estimators, the minimum estimator, the median estimator and the average estimator, are proposed and the complexity-rate-distortion analysis is presented.