High Efficiency Video Coding is a new video coding standard after H.264/AVC. By introducing a flexible coding unit, which can be recursively divided from 64×64 to 8×8 blocks in a Quadtree-Structure, HEVC achieves significantly higher coding efficiency than the previous standards. With the flexible CU structure, HEVC can effectively adapt to highly varying contents with a smaller CU or to flat contents with a larger CU, making it suitable for applications from mobile video to super high definition television. On the other hand, CU division does incur high computational cost for HEVC. In this paper, we propose a simple and fast CU division algorithm by using only a subset of pixels to determine when CU division happens. Experiment results show that our algorithm can achieve prediction quality close to HEVC Test Model with much lower computational cost.

Conventional fast block-matching algorithms, such as TSS and DSWA/IS, are widely used for motion estimation in the low-bit-rate video coding. These algorithms are based on the assumption that when searching in the previous frame for the block that best matches a block in the current frame, the difference between them increases monotonically when a matching block moves away from the optimal solution. Unfortunately, this assumption of global monotonicity is often not valid, which can lead to a high possibility for the matching block to be trapped to local minima. On the other hand, monotonicity does exist in localized areas. In this paper, we proposed a new algorithm called Peano-Hilbert scanning search algorithm (PHSSA). With the Peano-Hilbert image representation, the assumption of global monotonicity is not necessary, while local monotonicity can be effectively explored with binary search. PHSSA selects multiple winners at each search stage, minimizing the possibility of the result being trapped to local minima. The algorithm allows selection of three parameters to meet different search accuracy and process speed: (1) the number of initial candidate intervals, (2) a threshold to remove the unpromising candidate intervals at each stage, and (3) a threshold to control when interval subdivision stops. With proper parameters, the multiple-candidate PHSSA converges to the optimal result faster and with better accuracy than the conventional block matching algorithms.

This paper presents a block-based motion vector search algorithm for video coding based on an interpolation scheme of search blocks. The basic idea of motion vector estimation between frames is to select a block in the previous frame that best matches a block in the current frame by minimizing the difference between them. In most of the search algorithms, however, the best-match block can only be on a pre-defined grid pattern. Although using a pre-defined pattern increases the search efficiency, it may also reduce the search accuracy. To balance the two aspects and to fully utilize the block information, we propose a strategy, which, instead of selecting from pre-defined blocks, searches for a best match interpolated from the pre-defined blocks. Experiment results demonstrate a better accuracy and efficiency of this search method than some commonly-used methods for different kinds of motion.

This paper presents a novel approach to pixel decimation for motion estimation in video coding. Early techniques of pixel decimation use regular pixel patterns to evaluate matching criterion. Recent techniques use adaptive pixel patterns and have achieved better efficiency. However, these adaptive techniques require an initial division of a block into a set of uniform regions and therefore are only locally-adaptive in essence. In this paper, we present a globally-adaptive scheme for pixel decimation, in which no regions are fixed at the beginning and pixels are selected only if they have features important to the determination of a match. The experiment results show that when no more than 40 pixels are selected out of a 1616 block, this approach achieves a better search accuracy by 13-22% than the previous locally-adaptive methods which also use features.