1.

Introduction

Motion estimation is an essential part of most video coding standards. Although the full search (FS) method gives the best performance, it incurs enormous computational complexity. Thus, many low-complexity motion estimation algorithms have been proposed, including the one-bit transform (1BT), two-bit transform (2BT), and constrained 1BT (C1BT) methods.^1–3 These low-complexity methods greatly reduce the complexity, but they lead to very low peak signal-to-noise ratio (PSNR) values. In order to solve this problem, many hybrid methods have been proposed that combine the low-complexity methods with the FS method. For example, the modified 1BT (M1BT) method combines the 1BT method with the FS method.⁴ The modified 2BT (M2BT) and modified C1BT (MC1BT) methods also combine low-complexity methods with the FS method.^5,6 This paper proposes an efficient search scheme that not only reduces the complexity, but also improves the performance of these conventional hybrid methods.

2.

Conventional Hybrid Methods

The FS method is based on the sum of absolute differences (SAD) measure, which is defined as follows:

Instead of using the SAD measure, the 1BT method uses the number of non-matching points (NNMP) measure, which is defined as follows:

Thus, Ref. 4 proposed a hybrid method, called the M1BT algorithm, which combines the low-complexity 1BT algorithm with the high-accuracy FS algorithm. In the first stage of the M1BT method, two motion vectors, $m{v}_1$ and $m{v}_2$, are selected, which have the lowest and second lowest NNMP values. Then, the SAD of the motion vector $m{v}_1$ is computed. If it is less than a threshold value $T_1$, $m{v}_1$ is selected as the final motion vector. Otherwise, the SAD of the second motion vector $(m{v}_2)$ is computed. If it is smaller than $T_1$, $m{v}_2$ is selected as the final motion vector. If not, the search process goes on to the second stage.

The second stage consists of two steps, as shown in Fig. 1. In the first step of the second stage, the SAD values of four additional points (in addition to the center point) are computed, and then the point with the minimum SAD is selected as the center point for the second step. In the second step, the SAD values of eight additional points (i.e., the square-shaped points in Fig. 1) are computed. The two steps are applied for $m{v}_1$ and $m{v}_2$, and the point with the minimum SAD is selected as the final motion vector.

Fig. 1

Two-step search in the M1BT method.

The M1BT method leads to a good tradeoff between performance and complexity, and as a result, several similar approaches have been proposed. For example, the 2BT and C1BT methods have been combined with the FS method to yield the M2BT⁵ and MC1BT⁶ methods, respectively.

3.

Proposed Method

The SAD computation in Eq. (1) requires relatively complex full-bit operations, whereas the NNMP computation in Eq. (3) uses only simple 1-bit operations. In order to reduce the complexity of the SAD operation, it is possible to use some subsampled SAD (SSAD) measures as follows:⁴

The SSAD computation, however, is still much more complex than the NNMP computation. Thus, it is important to reduce the number of search points that require SAD (or SSAD) computations.

It is possible to use only one of $m{v}_1$ or $m{v}_2$ in order to reduce the number of search points, but this will lead to considerable performance degradation. However, after analyzing extensive simulation results, we found that $m{v}_1$ and $m{v}_2$ are, in most cases, located very close to each other. Table 1 shows the probability distribution of Euclidean distance (ED) between $m{v}_1$ and $m{v}_2$ for various video sequences. As can be seen from the table, $\mathrm{ED}(m{v}_1,m{v}_2)$ is very small in most cases.

Table 1

Euclidean distance between mv1 and mv2 in M1BT.

Here, it is important to note that the search areas around $m{v}_1$ and $m{v}_2$ mostly overlap when $\mathrm{ED}(m{v}_1,m{v}_2)$ is very small. Thus, the proposed method will search only one search area without checking the other one if $\mathrm{ED}(m{v}_1,m{v}_2)$ is less than or equal to 4. To be more precise, the proposed method will check only the search points around $m{v}_X$, where $m{v}_X$ represents either $m{v}_1$ or $m{v}_2$, whichever has a smaller SAD value (it should be noted that the SAD of $m{v}_2$ may be smaller than that of $m{v}_1$, even though the NNMP of $m{v}_1$ is always smaller than that of $m{v}_2$). This new scheme will significantly decrease the number of search points at the expense of slight PSNR degradation, and the simulation results will be given in the next section.

The M1BT method performs well when either $m{v}_1$ or $m{v}_2$ is located near $m{v}_{\_\mathrm{FS}}$, where $m{v}_{\_FS}$ represents the optimal motion vector determined by the FS method. This is usually the case, but sometimes, both $\mathrm{ED}(m{v}_1,m{v}_{\_\mathrm{FS}})$ and $\mathrm{ED}(m{v}_2,m{v}_{\_\mathrm{FS}})$ can become quite large. On the other hand, all of the search points in the M1BT method are located within very small areas around $m{v}_1$ and $m{v}_2$. To be more precise, for every search point $X$ around $m{v}_1$, $\mathrm{ED}(m{v}_1,X)$ is always less than or equal to 4, as can be seen in Fig. 1. The same is true for $m{v}_2$ and every search point around $m{v}_2$. Thus, when both $\mathrm{ED}(m{v}_1,m{v}_{\_\mathrm{FS}})$ and $\mathrm{ED}(m{v}_2,m{v}_{\_\mathrm{FS}})$ are quite large, $\mathrm{ED}(m{v}_{\_\mathrm{M}1\mathrm{BT}}m{v}_{\_\mathrm{FS}})$ will also be quite large, leading to significant PSNR degradation, where $m{v}_{\_\mathrm{M}1\mathrm{BT}}$ represents the final motion vector determined by the M1BT method.

After analyzing diverse simulation results, we found that $\mathrm{ED}(m{v}_1,m{v}_{\_\mathrm{FS}})$ and $\mathrm{ED}(m{v}_2,m{v}_{\_\mathrm{FS}})$ are quite large when the area around the current macroblock contains high motion. Thus, the proposed method will adaptively determine $d_1$ and $d_2$ (in Fig. 1), based on the degree of motion (it should be mentioned that $d_1$ and $d_2$ are fixed to 2 and 1, respectively, in the original M1BT method). In order to account for the degree of motion, we use the information of the co-located macroblock (i.e., the macroblock at the same position in the previous frame) as follows:

It should be emphasized that the proposed dynamic search range method does not increase the number of search points even if $d_1$ and $d_2$ are larger than the original values. Instead, it just checks a different set of search points. In other words, the proposed method skips some of the search points around the search center, but checks some additional search points that are far from the search center (when $d_1$ and $d_2$ are large). Finally, it should be noted that there are some frames that do not have motion vector information for the co-located macroblocks. For example, the first two frames in a video sequence with an IPPP… structure are such cases. For frames like this, $d_1=9$ and $d_2=3$ will be used, which are values that have also been determined based on extensive simulation results. We will call the proposed method the dynamic M1BT (DM1BT) method since the number of search points and the search area are dynamically determined.

4.

Comparison with the Conventional Methods

Table 2 compares the proposed DM1BT method with the conventional 1BT and M1BT methods in terms of the PSNR and the total number of search points that require SSAD computation. Both the macroblock size $N$ and the search range $s$ were set to 16, and the $D_2$ SSAD measure in Eq. (4) was used in the simulation. As mentioned in the previous section, the DM1BT method is based on two techniques. First, it reduces the complexity by checking only one of two neighboring search areas. Second, it improves the performance by adaptively deciding $d_1$ and $d_2$. In order to examine the effect of each technique, Table 2 shows three kinds of results for the proposed method, where the ${\mathrm{DM}1\mathrm{BT}}_1$ method uses only the first technique, the ${\mathrm{DM}1\mathrm{BT}}_2$ method uses only the second technique, and the DM1BT method uses both techniques.

Table 2

Comparison with the 1BT and M1BT methods.

First of all, we can see that the ${\mathrm{DM}1\mathrm{BT}}_1$ method uses a much smaller number of search points than M1BT. As mentioned, this is because the ${\mathrm{DM}1\mathrm{BT}}_1$ method checks only one of the two search areas when the distance between $m{v}_1$ and $m{v}_2$ is small. On average, the ${\mathrm{DM}1\mathrm{BT}}_1$ method reduces the number of search points by 36.1%. On the other hand, the PSNR degradation is negligible. This is because the final motion vectors of ${\mathrm{DM}1\mathrm{BT}}_1$ are, in most cases, the same as those of M1BT. The hit rate in Table 2 represents the probability that the final motion vectors of ${\mathrm{DM}1\mathrm{BT}}_1$ and M1BT are the same. As can be seen, the hit rates of the ${\mathrm{DM}1\mathrm{BT}}_1$ method for various test sequences are quite high. Table 2 also shows that the ${\mathrm{DM}1\mathrm{BT}}_2$ method significantly improves the PSNR performance of the M1BT method. As explained in the previous section, this is because the ${\mathrm{DM}1\mathrm{BT}}_2$ method adaptively increases the search range when a video sequence contains high motion. It should be noted that the ${\mathrm{DM}1\mathrm{BT}}_2$ method uses a slightly smaller number of search points than the M1BT method. This is because some of the candidate search points in the ${\mathrm{DM}1\mathrm{BT}}_2$ method go beyond the boundary of the frame when $d_1$ and $d_2$ are large.

As expected, we can see that the DM1BT method, which is based on both techniques, not only decreases the number of search points, but also improves the PSNR performance. On average, the DM1BT method increases the PSNR of M1BT by 0.36dB and reduces the number of search points by 37.3%. It can also be seen that the hit rates of DM1BT (as compared with ${\mathrm{DM}1\mathrm{BT}}_2$) are very high although they are slightly smaller than the hit rates of ${\mathrm{DM}1\mathrm{BT}}_1$ (as compared with M1BT).

Finally, it should be mentioned that the proposed search scheme can be easily applied to other hybrid search methods, such as the M2BT⁵ and MC1BT⁶ methods, which also use two search centers and fixed search ranges. Table 3 compares the proposed DM2BT method with the conventional 2BT and M2BT methods, whereas Table 4 compares the proposed DMC1BT method with the conventional C1BT and MC1BT methods. As can be seen, the DM2BT and DMC1BT methods also efficiently enhance the conventional M2BT and MC1BT methods in terms of both PSNR performance and computational complexity.

Table 3

Comparison with the 2BT and M2BT methods.

Table 4

Comparison with the C1BT and MC1BT methods.

5.

Conclusions

We proposed a new low-complexity block motion estimation method. Using the fact that the two search centers are closely located in most cases, the proposed method significantly reduces the number of search points and hence the overall complexity. It also improves the PSNR performance by using an adaptive search scheme based on the motion vector information of the co-located macroblock. The proposed search scheme can be easily applied to many hybrid motion estimation methods.