Fast half-pixel motion estimation based on directional search and

a linear model

Fast half-pixel motion estimation

based on directional search and a linear model

Yun-Gu Lee, Jae Hun Lee, and Jong Beom Ra

Dept. of Electrical Engineering and Computer Science,

Korea Advanced Institute of Science and Technology (KAIST)

Daejeon, Republic of Korea

ABSTRACT

As many fast integer-pixel motion estimation algorithms have become available, an integer-pixel motion vector can be found by examining less than 10 search points. Meanwhile, 8 half-pixel positions around the integer-pixel motion vector are to be examined for half-pixel motion estimation. Hence, it becomes more meaningful to reduce the computational complexity of half-pixel motion estimation. In this paper, we propose a fast half-pixel motion estimation algorithm, by combining a directional search and linear modeling of SAD curve. The proposed algorithm reduces the number of search points to 2.21 in average, while the image quality of reconstructed sequences in terms of PSNR is similar to existing fast half-pixel motion estimation algorithms. In addition, by adjusting a user-defined parameter, the proposed algorithm can significantly reduce the number of search points to 0.34 on average with a slight PSNR degradation.

Keywords: Motion estimation, half-pixel, half-pel, sub-pixel, linear model

1. INTRODUCTION

In video coding, motion estimation is used to reduce a temporal redundancy between inter frames. However, motion estimation generally requires huge computational complexity. Hence, due to its low complexity, a block matching algorithm is widely used in motion estimation. In the block matching algorithm, the current frame to be encoded is divided into non-overlapped blocks and the best matching block of each current block is found within the previous frame. In video coding standards such as H.263 and MPEG-1/2/4, the best matching block is usually examined within a limited search area.

In the full search block matching algorithm, all possible points (or corresponding blocks) within a search area in the previous frame, are checked to find a block most closely matched to the current one. Here, SAD (sum of absolute differences) is popularly used as a matching criterion.

SAD(u,v)=∑∑It(i,j) It 1(i+u,j+v) (1)

j=0i=0N 1N 1

where It(i, j) and It-1(i+u, j+v) denote luminance pixel values in the current and previous frames, respectively, and (u, v) refers to a displacement or a candidate motion vector. Also, N denotes the size of block. In order to determine a motion ; phone +82-42-869-3434; fax +82-42-869-8360; Dept. of EECS, KAIST, 373-1, Guseong-dong Yuseong-gu, Daejeon, 305-701, Republic of Korea

Visual Communications and Image Processing 2003, Touradj Ebrahimi, Thomas Sikora,Editors, Proceedings of SPIE Vol. 5150 (2003) © 2003 SPIE · 0277-786X/03/$15.001513

a linear model

vector of each block, SAD values of candidate motion vectors within a search area are examined and the motion vector which has the minimum SAD value is set to the final one.

If the best matching block of the current block is found in the previous frame, the current frame is reconstructed by using this best matching block. Hence, in order to obtain the better coding performance, this motion compensated block should be similar to the original one, or the motion compensation error should have small energy. However, since the true displacement between the pervious frame and current frame is not always a multiple of pixel interval, it is known that sub-pixel motion estimation can reduce the motion compensation error.

International video coding standards such as H.263 and MPEG-1/2/4 adopt motion estimation with half-pixel accuracy

[1-4]. To estimate a motion vector with half-pixel accuracy, a two-step search is generally used. In the first step, integer-pixel points within a search area are examined to find the best matching point, or the integer-pixel motion vector. Then, in the second step, 8 half-pixel points around the selected integer-pixel motion vector are examined and the best matching point is chosen as the final motion vector. The complexity burden of integer-pixel motion estimation takes a major portion of motion estimation because the search area of integer-pixel motion estimation is much larger than that of half-pixel motion estimation. So, most researchers have paid attention to the development of a fast integer-pixel motion estimation algorithm. However, if a recently developed fast algorithm is used for integer-pixel motion estimation, a motion vector can be found by examining less than 10 search points [5-7]. As a consequence, the computation complexity of half-pixel motion estimation becomes comparable to that of integer-pixel motion estimation and the development of a fast half-pixel motion estimation algorithm becomes important.

In this paper, we propose a new half-pixel motion estimation algorithm, by combining a directional search and linear modeling of SAD curve. In addition, we introduce an adjustable parameter so that we can reduce the number of search points further with a slight PSNR degradation. We will briefly review previous work in section 2, and describe the proposed algorithm in section 3. The simulation results are given in section 4. Finally, conclusions are presented in section 5.

2. PREVIOUS WORK

In horizontal and vertical directions as reference (HVDR), which is one of the fast half-pixel motion estimation algorithms, 4 neighboring half-pixel points in horizontal and vertical directions around the integer-pixel motion vector, are examined, and the two best matching points are found for both directions [8]. Then, a diagonal point between the two best matching points is additionally examined. If we describe the algorithm using Fig. 1, points 1, 3, 5 and 7 are first examined. Then, the point having smaller SAD value between points 1 and 7 is selected as the best matching point of vertical direction and the horizontal one is selected between points 3 and 5. If we assume that points 1 and 3 are the best matching ones of both directions, then diagonal point 0 is additionally examined. Therefore, 5 searching points are to be examined instead of 8 points in HVDR.

In the paraboloid prediction based fast half-pixel search (PPHPS), an SAD curve around an integer-pixel motion vector is modeled as a paraboloid [9]. By using the SAD values of neighboring integer-pixel points, the parameters of paraboloid equation are estimated and the SAD values of half-pixel points are predicted using the paraboloid equation. Then, the best matching point having the smallest SAD value among candidate points is predicted. Finally, the real SAD values of the predicted point and its two neighboring points are examined to find the final motion vector. For instance, if point 0 in Fig. 1 is predicted as the minimum point, the real SAD values of points 0, 1, and 3 should be examined. Therefore, PPHPS needs to examine 3 search points, and requires extra calculation for SAD curve modeling. Although SAD curve modeling needs multiplication and division operations, the total computational complexity of PPHPS is still less than that of HVDR.

1514 Proc. of SPIE Vol. 5150

a linear model

Figure 1. Search points for half-pixel motion estimation

Li and Gonzales model the SAD function around the true motion vector as a separable quadratic function and estimates x- and y-direction motion vectors by using the one-dimensional quadratic functions, respectively [10]. The complexity of this algorithm is very small because this algorithm needs only the estimation of parameters. However, since real SAD values around the optimum point are not exactly the same as the predicted SAD ones, the wrong decision of motion vectors may cause a bit-rate increase or PSNR degradation. In order to improve the motion vector accuracy, the estimated motion vector may need refinement.

3. PROPOSED ALGORITHM

In order to alleviate the complexity of half-pixel motion estimation, we may reduce the number of search points by using predicted SAD values based on a SAD function model. However, the predicted SAD values are usually different from the real ones. Thus, a motion vector estimated from predicted SAD values may be different the one from full search motion estimation where all SAD values are examined. Therefore, the proposed algorithm determines whether the real SAD value has to be examined or not, based on the proposed measure. This measure provides the information whether the predicted SAD value is accurate enough for determining the motion vector. Thereby, SAD value calculation of most search points can be skipped without performance degradation.

3.1 LINEAR MODELING

For modeling of the SAD curve around an integer-pixel motion vector, we need the SAD values of integer-pixels neighboring the integer-pixel motion vector are needed. Recently most fast integer-pixel motion estimation algorithms adopt the gradient descent search (GDS) as a search strategy and a small diamond search pattern at the final stage. Therefore, we can assume that SAD values of the four neighboring integer-pixel points along horizontal and vertical directions, or points a, b, c and d in Fig. 1, are already known. The proposed algorithm uses these 4 SAD values for modeling two SAD curves along horizontal and vertical directions.

Proc. of SPIE Vol. 5150 1515

a linear model

While PPHPS models the SAD curve as a two-dimensional quadratic function and the algorithm in [10] models it with two one-dimensional quadratic functions, the proposed algorithm models it with two one-dimensional linear functions. This is based on that the SAD function within a small area around the optimum point can be well modeled as a linear function. Note that the modeling process of linear model is simpler than that of quadratic model, because the former needs only addition and subtraction operations.

Fig. 2 depicts the SAD graph estimated by using a piecewise linear model along the horizontal direction. In Fig. 2, x-axis represents the position of search points, and its origin denotes the integer-pixel motion vector that results from integer-pixel motion estimation. And y-axis represents the SAD value. We assume in the graph that the slopes of two lines have opposite sign, while their absolute values are the same. Let us define SADC as the SAD value of an integer-pixel motion vector and SADL and SADR as the SAD values of left and right integer points of the integer-pixel motion vector (points a and c in Fig. 1), respectively. The values of SADC, SADL and SADR are already known by integer-pixel motion estimation. Then, two points, (-1, SADL) and (1, SADR), are on the two lines having a slope of the opposite sign and same magnitude, and (0, SADC) should locate on the one of two lines. Using these conditions, the two line equations can be determined, and SAD values at the two half-pixel positions, or SADHL and SADHR, can be estimated from the two line equations.

Figure 2. Linear approximation of SAD values

3.2 PREDICTION ERROR BOUND

In order to find a directional motion vector, predicted SAD values of half-pixel points are to be compared with the real SAD value of integer-pixel motion vector. However, since the predicted SAD values are not always the same as the real ones, the comparison results may not be correct. If SADE denotes a predicted SAD value, we can assume that its real SAD value locates in the range from SADE-e to SADE+e, where e is the prediction error bound.

Now let us assume that SADH is the smaller one between the two predicted SAD values, or SADHL and SADHR. Then, if (SADC - SADH) is bigger than e, the estimated SADH is considered the minimum one as in Fig. 3(a). Also, if (SADH - SADC) is bigger than e, SADC is considered the minimum one as in Fig. 3(b). But if |SADH-SADC| is less than e as shown in Fig. 3(c) and (d), the real SADH of the corresponding half-pixel point is to be examined for comparison. The same procedure is also performed for the vertical direction. Thereby, we obtain the two best matching points and their corresponding SAD’s. Here, it should be noticed that the number of search points in each direction becomes one at most.

1516 Proc. of SPIE Vol. 5150

a linear model

Figure 3. The relationship between the SAD values and the error bound

Table 1. Refinement according to directional search results Horizontal motion Vertical motion Diagonal search Final motion vector

two best matching points

(-0.5, 0)

Minimum one among diagonal points and two best matching points

(0, -0.5)

(0, 0) (0, 0.5)

Minimum one among diagonal points and two best matching points

(0.5, 0)

two best matching points

Proc. of SPIE Vol. 5150 1517

a linear model

3.3 REFINEMENT

As described in the section above, the two best matching points and their corresponding (real or predicted) SAD values are obtained. According to these results, we decide whether an additional diagonal point is to be examined or not. If either of the best matching points located at the center, any diagonal point needs not to be examined. Otherwise, an additional diagonal point is to be examined.

Table 1 shows the refinement process in all the cases. For example, let us assume that the best matching points of horizontal and vertical directions are -0.5 and -0.5, respectively. Then, the SAD value at the diagonal point (-0.5, -0.5) is to be examined and the final motion vector is decided as the point having the smallest SAD value among the three points. But if they are -0.5 and 0, the final motion vector is simply set to point (-0.5,0). Therefore, the maximum number of search points in the proposed algorithm is three, while the effective number becomes much less than three.

4. SIMULATION RESULTS

For experiment, we adopt the two video sequences of CIF format (352x288), Carphone and Foreman, and the four video sequences of SIF format (352x240), Flower garden, Football, Table tennis, and Mobile. Each sequence consists of 100 frames with a frame rate of 30Hz, and is encoded using an H.263 coder without rate-control. All frames except the first frame is encoded as P-frames. For integer-pixel motion estimation, method A adopts the full search integer-pixel motion estimation algorithm and methods B, C, D, E, F, and G use one of the recent fast algorithms, the unrestricted center-biased diamond search (UCBDS) [6]. The adopted half-pixel motion estimation algorithm and simulation condition for each method are listed in Table 2.

The simulation results in Tables 3 and 4 show that the estimation speed of proposed algorithm is faster than the other algorithms. If the value of e is set to infinite, all estimated SAD values become uncertain and their real SAD values are always to be examined. Thus, the total number of search point is about 2.21. In this case, the speed of the proposed algorithm is still faster than PPHPS and HVDR while its PSNR performance is similar to them. If the e value is set to zero, two estimated SAD values are assumed to be accurate. So they are not calculated. In this case, the total number of search points becomes about 0.34 and the PSNR degradation from full search half-pixel motion estimation (Algorithm

B) is 0.11dB. If the e value is set to 50, the proposed algorithm is 3.2 times faster than PPHPS with the PSNR degradation of only 0.05dB.

It should be noted that the computational overhead for the estimation of SAD values is negligible in the proposed algorithm.

5. CONCLUSION

We propose a fast half-pixel motion estimation algorithm for video coding. In the proposed algorithm, we first estimate x and y components of the motion vector and its SAD value. Then, according to the estimated component values, the next refinement step is decided. In the proposed algorithm, depending on the threshold value adopted, the PSNR degradation and speedup factor can be adjusted. If the threshold value is 0, the PSNR degradation is 0.11dB from full search half-pixel motion estimation (Algorithm B), but the speedup ratio is 23.5. Meanwhile, if the threshold value is set to infinite, the PSNR degradation and speed up ratio are 0.02dB and 3.6, respectively. Hence, we can conclude that the proposed algorithm is much faster than other fast algorithms with the minor PSNR degradation.

ACKNOWLEDGMENTS

This work is supported by the ITRC funded in part by the Korean Ministry of Information and Communication. 1518 Proc. of SPIE Vol. 5150

a linear model

Table 2. Integer-pixel and half-pixel motion estimation algorithms adopted for each simulation.

A Full search Half-pixel ME Full search

UCBDS

E Proposed one with e of 0

F

G Proposed one with e of 50 Proposed one with e of 10000

Table 3. Simulation results for various half-pixel ME algorithms

Flower Table garden

PSNR PSNR PSNR PSNR PSNR PSNR Search PSNR kbps kbps kbps kbps kbps kbps (dB) (dB) (dB) (dB) (dB) (dB) points (dB)

32.83

32.74

32.70

32.72

32.59

32.66

32.70

Table 4. The number of search points in the proposed algorithm

Table Flower Football 26.10 1059 24.35 1099 28.49 1085 24.34 1117 28.12 1089 24.34 1119 28.09 1097 24.32 1128 28.09 1120 24.30 1142 27.99 1115 24.31 1140 28.04 1089 24.34 1119 28.09 8 8 5 3 0.60 0.9

Proc. of SPIE Vol. 5150 1519

a linear model

REFERENCES

1.

2.

3.

4. ISO/IEC JTC1/SC29/WG11,“ISO/IEC CD 11172:Information technology,” MEPG 1 Committee Draft, Dec. 1991. ISO/IEC JTC1/SC29/WG11,“ISO/IEC CD 13818:Information technology,” MEPG 2 Committee Draft, Dec. 1993. ISO/IEC JTC1/SC29/WG11, MPEG99/5477, “MPEG-4 Video Verification Model version 14.2,” Dec. 1999. International Telecommunication Union, “Video codec for low bitrate communication,” ITU-T Recommendation

H.263, Mar. 1996.

5. L. Liu and E. Feig, “A Block-based Gradient Descent Search Algorithm for Block Motion Estimation in Video

Coding,” IEEE Trans. Circuts Syst. Video Technol., vol. 6, pp. 419-422, Aug. 1996.

6. J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A Novel Unrestricted Center-Biased Diamond

Search Algorithm for Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, pp. 369-378, Aug. 1998.

7. Shan Zhu and Kai-Kuang Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation,”

IEEE Trans. Image Processing, vol. 92, no. 2, pp. 287-290, Feb. 2000.

8. K.H. Lee, J.H. Choi, B.K. Lee, and D.G. Kim “Fast Two-Step Half-Pixel Accuracy Motion Vector Prediction,”

Electronics Letters, vol. 36, pp. 625-627, Mar. 2000.

9. C. Du and Y. He, “A Comparative Study of Motion Estimation for Low Bit Rate Video Coding,” SPIE Proc.

VCIP2000, vol. 4067, no. 3, pp. 1239-1249, Jun. 2000.

10. X. Li and C. Gonzales, “A Locally Quadratic Model of the Motion Estimation Error Criterion Function and Its

Application to Subpixel Interpolation,” IEEE Trans. Circuts Syst. Video Technol., vol. 6, pp. 118-122, Feb. 1996.

1520 Proc. of SPIE Vol. 5150

本文来源：https://www.bwwdw.com/article/hei4.html