Compression is a necessity for the efficient storage and transmission of digital video as digital video requires a huge data volume if left uncompressed. H.264 is the state-of-the-art video compression standard. It offers more than 40% of coding efficiency gain compared to previous standards such as MPEG1/2/4 and H.261/3. H.264 has many new features, such as multiple blocksize motion estimation, multiple frame motion estimation and quarter-pixel precision motion estimation. However, these features have a very high computational complexity, so it is difficult to develop a real-time H.264 system without fast algorithms. In the first part of this thesis, a generalized fast block-based integer pixel motion estimation algorithm for multiple blocksize and multiple frame motion estimation is p...[ Read more ]

Compression is a necessity for the efficient storage and transmission of digital video as digital video requires a huge data volume if left uncompressed. H.264 is the state-of-the-art video compression standard. It offers more than 40% of coding efficiency gain compared to previous standards such as MPEG1/2/4 and H.261/3. H.264 has many new features, such as multiple blocksize motion estimation, multiple frame motion estimation and quarter-pixel precision motion estimation. However, these features have a very high computational complexity, so it is difficult to develop a real-time H.264 system without fast algorithms. In the first part of this thesis, a generalized fast block-based integer pixel motion estimation algorithm for multiple blocksize and multiple frame motion estimation is proposed. This algorithm achieves hundreds to thousands times of speed up compared to the Full Search algorithm while introduces no loss in coding efficiency. This algorithm was accepted as part of the AVS-M video coding standard. The second part of this thesis is mainly focused on sub-pixel motion estimation and motion compensation. In this part, a fast sub-pixel motion estimation algorithm and a new quarter-pixel motion compensation scheme are proposed. The proposed sub-pixel motion estimation algorithm achieves 2-3 times speed up compared to the full search algorithm while introducing only a small loss in coding efficiency. The new quarter-pixel motion compensation scheme achieves up to 5% of bitrate reduction while keeping the PSNR unchanged..