A new complexity-scalable framework for motion estimation is proposed to efficiently reduce the motioncomplexity of encoding process, with focus on long term memory motion-compensated prediction of the H.264 video coding standard in this work. The objective is to provide a complexity scalable scheme for the given motion estimation algorithm such that it reduces the encoding complexity to the desired level with insignificant penalty in rate-distortion performance. In principle, the proposed algorithm adaptively allocates available motion-complexity budget to macroblock based on estimated impact towards overall rate-distortion (RD) performance subject to the given encoding time limit. To estimate macroblock-wise tradeoff between RD coding gain (J) and motion-complexity (C), the correlation of J-C curve between current macroblock and collocated macroblock in previous frame is exploited to predict initial motion-complexity budget of current macroblock. The initial budget is adaptively assigned to each blocksize and block-partition successively and motion-complexity budget is updated at the end of every encoding unit for remaining ones. Based on experiment, proposed J-C slope based allocation is better than uniform motion-complexity allocation scheme in terms of RDC tradeoff. It is demonstrated by experimental results that the proposed algorithm can reduce the H.264 motion estimation complexity to the desired level with little degradation in the rate distortion performance.
An efficient search range prediction method is proposed to reduce the complexity of motion search in the H.264 video coding standard in this work. The main idea is to predict the temporal search range by modeling the relationship between the rate-distortion (RD) coding gain and the required computational complexity. The proposed algorithm first predicts the temporal search range to maximize the ratio of the expected RD coding gain and the normalized computational cost. Then, fast motion search is performed within the predicted search range with some early termination rule. Experimental results show that the proposed algorithm can save approximately 63-75% of the encoding complexity in motion estimation of H.264 (JM9.3) with negligible degradation in the RD performance.
In this paper, a hierarchical prediction scheme for fast motion search is proposed in order to implement an effective encoder that pays a small amount of search cost to achieve the best match without little rate-distortion performance degradation. The proposed method has a hierarchical tree structure, where each node has two sub-tasks; namely, the reference frame selection and the spatial search region prediction. From now on, let’s call best motion vector by full search as true motion vector. Proposed fast motion search for multiple reference frames can be summarized as:
Step1. Initial searching point in previous frame: In literature, majority of true motion vectors are distributed around the center of searching window in recent frames so we first search the previous frame. Diamond search fails to search the true motion when the initial point misleads search path to local minima. In order to solve this problem, initial points are searched based on multiresolution motion search.
Step2. Perform diamond search for each initial points and compare the minimum distortion measure with stopping criterion which defines maximum searching points, minimum diamond size and threshold based on QP. If the stopping criterion is met, then motion search is finished with the motion vector having minimum distortion. Otherwise go to Step 3. Here, the diamond size depends on the motion activity between current frame (T) and previous frame (T-1).
Step3. Find out search center in the frame indicated by motion trace (motion vector field obtained from previous encoding stage) for all best points in each diamonds in previous frame (T-1). Based on its motion activity, the diamond size is determined and checked the stopping criterion for all diamond in second previous frames. Iterate this step until the stopping condition is met.
A fast intra/inter mode decision method using a risk-minimization criterion is proposed to reduce the encoder complexity of the H.264 encoder in this work. The current H.264 reference codes employ exhaustive search to find the best mode that optimizes the rate-distortion performance among all possible intra/inter predictive modes. To develop a fast binary mode decision scheme (i.e. either the inter- or intra-prediction mode to be used), we consider the risk of choosing the wrong predictive mode. If the cost of choosing the wrong mode in terms of the averaged rate-distortion (RD) performance loss is low, then the risk is tolerable. The fast algorithm consists of three steps. First, three features are extracted from the current macroblock to form a 3D feature vector. Second, the feature space is partitioned into three regions, i.e. risk-free, risk-tolerable, and risk-intolerable regions. Finally, depending on the location of the feature vector in the feature space, we can apply mechanisms of different complexities for the final mode decision. The proposed algorithm can select either the correct mode or the wrong mode but with low RD performance degradation. It is demonstrated by experimental results that the proposed algorithm can save approximately 19-25% of the total encoding time of H.264 (JM7.3a) with little degradation in the rate-distortion performance.
A multistage mode decision method to reduce the complexity of Intra prediction in H.264/JVT is proposed in this work. The rate-distortion optimized (RDO) mode decision is adopted by H.264 to achieve the optimal coding gain at the cost of a very high computational complexity. Our research goal is to reduce the complexity of intra prediction without significant RD performance loss. The proposed fast intra prediction algorithm uses two features, i.e. the sum of absolute residual coefficients (SATD) and the sum of absolute gradients (SAG), and a simplified RDO method to determine the best mode for 4x4 blocks. It incorporates an early termination mechanism at various intermediate decision steps to avoide unnecessary computations when a good decision can be made at an earlier stage. It is demonstrated by experimental results that the proposed scheme performs approximately 10 to 30 times faster than the current RDO mode decision (JM7.3a) with little degradation in the coding gain.
We investigate the encoding speed improvement for H.264 with a special focus on fast intra-prediction mode selection in this work. It is possible to adopt the rate-distortion (RD) optimized mode in H.264 to maximize the coding gain at the cost of a very high computational complexity. To reduce the complexity associated with the intra-prediction mode selection, we propose a two-step fast algorithm. In the first step, we make a course-level decision to split all possible candidate modes into two groups: the group to be examined further and the group to be ignored. The sizes of these two groups are adaptively determined based on the block activities. Then, in the second step, we focus on the group of interest, and consider an RD model for final decision-making. It is demonstrated by experiment results that the proposed scheme performs 5 to 7 time faster than the current H.264 encoder (JM5.0c) with little degradation in the coding gain.