DOI: 10.25549/usctheses-c127-657287
title: Low complexity and high efficiency prediction techniques for video coding

description: Video compression has been extensively studied in the last two decades. The success of a coding algorithm relies on the effective removal of spatial and temporal redundancies in input video sequences. On the other hand, effective spatial and temporal prediction techniques demand high computational complexity, which makes it challenging to implement in resource-limited mobile devices. This research focuses on two topics: 1) complexity reduction of temporal prediction without significant rate-distortion (RD) performance degradation; and 2) the development of a more effective spatial prediction technique to enhance the RD performance. ❧ For the first topic, complexity reduction in temporal prediction is achieved by the development of an adaptive motion search range (SR) selection algorithm.  A good choice of the SR size helps reduce memory access bandwidth while maintaining the RD coding performance.  To begin with, we get a motion vector predictor (MVP) for a target block based on motion vectors (MVs) of its spatially and temporally neighboring blocks, which form a MV prediction set. Then, we relate the variance of the MV prediction set to the SR.  That is, a larger variance implies lower accuracy of the MVP and a larger SR.  Finally, we derive a probability model for the motion vector prediction difference (MVPD), the difference between the optimal MV and the MVP, to quantify the probability for a chosen SR to contain the optimal MV. The superior performance of the proposed SR selection algorithm is demonstrated by experimental results. ❧ For the second topic, a novel multi-order-residual-prediction (MORP) coding approach is proposed to improve spatial prediction efficiency in video coding. We observe that the compression ratio of a video coding algorithm depends on the nature of sequences as indicated by the ratio between inter and intra blocks in the bit-stream. When the percentage of intra blocks increases, the prediction efficiency decreases, thus leading to a poorer coding gain. In other words, one bottleneck of video coding lies in poor intra prediction efficiency.  To address this issue, we propose an MORP coding scheme that adopts a second-order prediction scheme after the traditional first-order prediction.  Different prediction techniques are adopted in different stages to tailor to the nature of the corresponding residual signals.  The proposed MORP scheme outperforms H.264/AVC for the intra block coding and, thus, improves the overall coding efficiency. ❧ Finally, we analyze prediction inefficiency of the proposed MORP scheme and present an enhanced intra prediction coding called the generalized line-based intra prediction (GLIP) to improve it.  The GLIP allows partial prediction of a coding block by enabling a subset of the neighboring prediction pixels.  The residual signal after the first order prediction consists of the local line structure while the GLIP is designed to exploit this feature.  The vector quantization (VQ) technique is used to approximate and encode the shape of the binarized residual signal.  The coded patterns of image residuals can be predicted using partial line structures based on known neighboring pixel values. A variable length coding scheme is adopted to encode the codewords of the VQ codebook to reduce the prediction overhead. The proposed GLIP algorithm effectively reduces the residual bits for both intra- and inter- blocks and outperforms H.264/AVC by a significant margin.