1.

Introduction

Block matching motion estimation is the core process in various video coding standards because of its efficiency in removing the temporal redundancy. However, motion estimation is very computationally intensive, if the exhaustive fast search algorithm (FSA) is employed to find the optimal matched block in the reference frame. To alleviate the heavy computation, many fast algorithms, such as the well-known three-step search (3SS),¹ the four-step search (4SS),² the diamond search (DS),³ and the hexagon-based search (HEXBS),⁴ have been proposed. Except for the successive elimination algorithm (SEA),⁵ these algorithms achieve fewer computations by sampling the search points in the search range, i.e., searching over a subset of possible candidate points with certain search patterns. Although algorithms in this category considerably reduce the computational complexity, they occasionally produce ambiguous search directions, and hence result in a local minimum.

This letter proposes a new fast motion estimation algorithm, which focuses on reducing computation not by sampling the search points but by reducing the size of the search range. Based on the assumption of convexity of the unimodal error surface, the proposed method makes use of the fact that the search center is probably close to the optimal matching point when the initial cost at the search center is efficiently low. Thus, in such cases, it’s possible to reduce the size of the search range for increased speed without much increase in matching error, which is the basic concept of the proposed method.

2.

Proposed Method

In general, motion vectors of spatially adjacent blocks are highly correlated if they belong to the same moving area. Having a predictive motion vector $\left({\mathrm{MV}}_{\mathrm{p}}\right)$ for a current block as the search center, as in the H.264/AVC JM,^{6, 7} the initial cost at the search center $J\left({\mathrm{MV}}_p\right)$ is a good estimate for correlation between the motion vector of the current block $\left({\mathrm{MV}}_{\mathrm{c}}\right)$ and ${\mathrm{MV}}_{\mathrm{p}}$ . If $J\left({\mathrm{MV}}_{\mathrm{p}}\right)$ is low, it means that ${\mathrm{MV}}_{\mathrm{p}}$ is probably close to ${\mathrm{MV}}_{\mathrm{c}}$ , and hence the size of the search range can be reduced to a proper size without missing the global minimum. On the other hand, if $J\left({\mathrm{MV}}_{\mathrm{p}}\right)$ is high, it means that ${\mathrm{MV}}_{\mathrm{p}}$ is not so correlated with ${\mathrm{MV}}_{\mathrm{c}}$ , and thus the size of the search range should be larger in order to include the global minimum in the search range. Based on this background, the block matching process for each block is performed as follows:

3.

Threshold Decision

With $S{R}_{fixed}=16$ and $L=2$ , two thresholds $T_1$ and $T_2$ $(T_1<T_2)$ must be given to discriminate the ranges of $J\left({\mathrm{MV}}_{\mathrm{p}}\right)$ for the three kinds of search range such as

Fig. 1

Determination of the neighboring blocks.

4.

Experimental Results

To evaluate the performance of the proposed technique, Foreman, Stefan, and Soccer sequences with the CIF format were tested with H.264/AVC JM9.4. The encoding parameters are as follows: number of frames—200, frame rate— $15\mathrm{Hz}$ , target bit rate— $256\mathrm{kbit}∕\mathrm{s}$ ; RD optimization off; $16\times 16$ , $16\times 8$ , $8\times 16$ , and $8\times 8$ block modes on; number of reference frames—1.

Table 1 shows the performance comparison between the proposed algorithm and the conventional FSA. Note that the spiral search method with ${\mathrm{MV}}_{\mathrm{p}}$ as the initial search point is used in both methods. The computational complexity is measured relative to the FSA with a $\pm 16$ search range. The results are summarized as follows:

Table 1

Performance comparison between the proposed approach and the conventional FSA.

Table 2

Distribution of selected search ranges in the proposed approach.

Figure 2 shows PSNR and complexity graphs for a range of $\alpha$ . We can observe that as $\alpha$ grows, the reduction ratio of the complexity decreases, and it is nearly saturated over $\alpha =2.0$ , whereas the PSNR drops continually, although the degree of drop is negligible. From this result, a value about 2.0 seems proper as the empirical value for $\alpha$ .

Fig. 2

PSNR and complexity versus $\alpha$ : (a) PSNR; (b) complexity.

5.

Conclusions

This letter has presented a fast motion estimation algorithm based on the ASRA. The size of the search range is adaptively adjusted according to the initial cost at the search center. Experimental results demonstrate that the proposed method saves a significant part of computations while providing comparable performance to the conventional FSA. If we combine our method with a fast FSA such as SEA, additional reduction in computation can be simply obtained. In addition, the ASRA-based approach has a strong point with respect to the hardware implementation, since it has a regular structure like the FSA.