Search It

Large Diamond and Small Pentagon Search

Patterns for Fast Motion Estimation*

Jianbin Song, Bo Li, Dong Jiang, and Caixia Wang

Digital Media Laboratory, School of Computer Science and Engineering,

Beihang University, Beijing, 100083, China

*******@*****.***.**, ****@****.***.**,

******@***.***, ************@***.***

Abstract. In fast motion estimation, a search pattern with different shape or size

has a very important impact on search speed and distortion performance. A

motion estimation algorithm based on the novel large diamond and small

pentagon search patterns is proposed in this paper. The stride of the proposed

large diamond pattern is 3 pixels and it just need 2 or 3 search points for every

new search step. So, the large diamond pattern can find the lager-motion vector

quickly compare with the 2-pixel-stride hexagon pattern, and, it is does not easy

to lose correct search path and fall into locally optimum point compare with the

three-step search. The proposed small pentagon pattern can do more refined

search than the small diamond pattern and small hexagon pattern. The proposed

algorithm may find any motion vector regardless of no-, small-, medium-,or

large-motion with fewer search points than the diamond search algorithm and the

hexagon-based algorithm while maintaining similar distortion performance.

Experimental results substantially justify the further improvement achieved of

the LDSPS algorithm compared with several other popular fast algorithms.

1 Introduction

Block-based motion estimation is an essential technique of most international coding

standards such as MPEG 4, H.264 and so on. However, the computation of motion

estimation is extraordinarily complex. If use the full search (FS) motion estimation, it

approximately consumes 60% or higher of the encoding time. Fast motion estimation

algorithm is always the hot research in the video compression field. The search pattern

and search strategy lead a vital role in speedup of a fast algorithm. The three step search

(TSS) [1] is extremely easy to miss the correct search path and not unable to find the best

matching block. Comparing with TSS, the performance of new three step search (NTSS)

[2]

and four step search (FSS) [3]is improved greatly, but the zero-vector coding block

also needs 17 search points. The block based gradient descent search (BBGDS) [4]carries

on the search by the length of 3 3 stride and it is easy to fall into locally optimum point

The diamond search (DS) [5,6] use diamond pattern and the recently proposed

Supported by the NSFC(60505007), the Program for New Century Excellent Talents in

University, the Doctoral Education Foundation of MOE and the ERIPKU. The research is

made in the State Key Lab of Software Development Environment.

L. Jiao et al. (Eds.): ICNC 2006, Part II, LNCS 4222, pp. 608 616, 2006.

Springer-Verlag Berlin Heidelberg 2006

Large Diamond and Small Pentagon Search Patterns 609

hexagon-based search algorithm(HEXBS) [7] use hexagon pattern respectively to

remarkably decrease computational complexity of motion estimation, because of the

short search stride and the more search points for every step, there exists redundancy of

search and the performance is still waited for further enhancement.

Many efficient motion estimation motheds such as literature[8~9] based on good

search pattern is proposed. So the search patterns have very important impact in fast

motion estimation. This paper aims to study the search pattern and search strategy,

doesn t study the prediction of search beginning point and the search termination

criterion. A fast motion estimation algorithm based on novel large diamond and small

pentagon search patterns are proposed, which further speed up of the motion estimation

algorithm. Section 2 reviews and investigates HEXBS algorithm. Section 3 firstly

explains the large diamond and small pentagon patterns, and then describes the steps of

the new LDSPS algorithm. Section 4 compares the number of search points of HEXBS

with LDSPS. Compare with FS, NTSS, FSS, DS and HEXBS, section 5 presents and

analyzes the experiment results. Section 5 concludes this paper.

2 The HEXBS Algorithm

Compared with the DS algorithm, the computation speed of the HEXBS increases by

21.4% ~ 36.7%[7], while image quality nearly does not decrease. However, in Fig.1(a),

we observe the pixels in the big hexagon, if the pixel 3 or 7 is the best matching

position, it needs 11 search points; if the pixel 1 or 5 is the best, it needs two steps of big

hexagon search, 14 search points possibly; if the pixel 2/4/6/8 is the best, it needs two

steps of big hexagon search and altogether 14 search points. In addition, the search

stride of the large hexagon is 2, so the HEXBS algorithm needs many steps to find the

best position for the coding block which has large motion, search efficiency is still

insufficient and needs to improve. Statistical results suggest that 40%~70%[2][5] best

optimum point is around the center point, it has the center-biased characteristic.

Therefore, the HEXBS algorithm still has search redundancy. Designing more

reasonable search pattern and search strategy can evidently speed up the motion

estimation.

(a) (b)

Fig. 1. Seach pattern of HEXBS

610 J. Song et al.

3 The LDSPS Algorithm

3.1 Search Pattern

Based on the proposed large diamond search pattern(LDS) and the small pentagon

search pattern(SPS), this paper propose a fast motion estimation algorithm(LDSPS).

may find any motion vector regardless of no-, small-, medium-,or large-motion with

fewer search points than the diamond search algorithm and the hexagon-based

algorithm while maintaining similar distortion performance.

(a) (b)

(c) (d) (e) (f)

Fig. 2. Search pattern of LDSPS. (a) large diamond pattern; (b)group of horizontal and vertical

MBD points; (c)~(f), small pentagon patterns.

1) LDS: LDS search stride is 3 pixels and search 1 center point and 4 corner points at

the first step and needs 2 or 3 additional search points for every new LDS step, whereas

the stride of the DS is 2 pixels, at the first step it must search a center point, 4 corner

points (vertex) and 4 edge points (face).According to different search directions, it

needs 3 or 5 additional search points for every later step. In the HEXBS, the search

stride of large hexagon is 2 pixels, the first step needs to search 1 central point and 6

vertexes, every later step needs 3 search points. If the best point is the adjacent pixel

around the search center, LDSPS algorithm needs 1 step LDS, 1 step SPS and only

searches 10 points. However, the famous HEXBS algorithm needs 11 or 14 points. The

motion vector has the center-biased characteristic, therefore, for most motion block, the

LDSPS algorithm can search the best point very quickly. For the movement who has

large motion vector, LDSPS algorithm can find the best matching block in the reference

frame quickly by using LDS because of its larger search stride. The larger the motion

vector is, the more obvious the advantage of the LDS is.

Large Diamond and Small Pentagon Search Patterns 611

2) SPS: SPS is appropriate for refined search. In this paper, minimum block

distortion (MBD) is used for selection of the best position. SPS finds 4 horizontal or

vertical points around the point which is selected as the best one in the last LDS. In

order to improve search efficiency, a supplement search point is added. Here, we

assume reasonably that the global minimum has a monotonic distortion and the nearer

to the global minimum the smaller the distortion in all directions (horizontal, vertical or

diagonal) within a small neighborhood around the global minimum. So, the selection of

the supplement point is mainly based on the horizontal MBD point and the vertical

MBD point in the previous LDS. In Fig.2(b), if the horizontal MBD point and the

vertical MBD point compose Group1, the algorithm uses the small pentagon like Fig.2

(c), if Group2, uses Fig.2 (d), if Group3, uses Fig.2 (e), if Group4, uses Fig.2 (f).

Comparing with the small diamond in DS and small hexagon in HEXBS, SPS finds five

points and can achieve more refined result.

The search range of TSS, NTSS and FSS is restricted by the method itself, while the

LDSPS algorithm proposed in this paper doesn t have the restriction, so it can find

the best matching block in arbitrary search scope. The video encoder always confines

the search scope considering the balance of speed and efficiency, such as 7, 15,

31 and so on. In this kind of situation, it just needs to add boundary judgment in the

LDSPS algorithm. In section 5, the search window size of the experiment is 15 .

3.2 Algorithm Process

The LDSPS algorithm can be divided into three steps as follows:

Step 1: Taking the search beginning point as the diamond center and starting first LDS.

If the best position is the center point, then go to step 3, otherwise go to step 2;

Step 2: Taking the MBD point of the previous step as the center point, start a new LDS,

if new MBD position of current step is the diamond s center point, then go to step 3,

otherwise repeat this step;

Step 3: Judging the horizontal and vertical MBD point in previous LDS, if the

horizontal MBD point and the vertical MBD point compose Group1, the algorithm uses

the small pentagons like Fig.2 (c), if Group2, uses Fig.2 (d), if Group3, uses Fig.2 (e), if

Group4, uses Fig.2 (f).After this step, the best position of motion estimation is

obtained. After selecting the small pentagon, do the SPS, then the search process is

stop.

A search path example is showed in Fig.3. There are 6 steps of LDS. The first step

searches 5 points. The second, third and fourth step searches along the horizontal

direction and each step needs 3 points. The fifth step searches along the vertical

direction, adds 2 search points. The sixth step changes to the horizontal direction, needs

2 search points. The MBD point of this step is the center point of the diamond, so the

LDS is stopped and the SPS is started. The horizontal and vertical MBD points

compose Group4, therefore, pentagon like Fig.2 (f)is selected as final search pattern.

This search example altogether needs 23 search points.

612 J. Song et al.

Fig. 3. Search path example

4 Search Points Contrast

The hexagon center point and the large diamond center point are the search beginning

points. Supposing that the point around of the center within 4 4 search window is the

best position respectively, the HEXBS and the LDSPS respectively calculate the fewest

search points number and the total number is recorded in the Fig.4(a) and Fig.4(b).

Fig.4 (a) shows the search number of different points as the best position using the

HEXBS algorithm, Fig.4 (b) records the search point number of the LDSPS algorithm.

Fig.4(c) shows the number of search points saved by LDSPS compared with HEXBS

for each motion vector location. If the point dyed by deep color is the best position, it

needs 14 search points in the Fig.4 (a) while the same position in Fig.4 (b) just needs 10

points, 4 search points are saved by using the LDSPS. As for the other points in the

Fig.4, the LDSPS algorithm can saves 1 search point at least and 5 at most. Not only the

large motion vector but also the small motion vector, LDSPS can improve efficiency of

motion estimation all the time.

(a) (b) (c)

Fig. 4. (a) Minimum possible number of search points for each motion vector location by

HEXBS algorithm. (b) Minimum possible number of search points for each motion vector

location by proposed LDSPS algorithm. (c) Number of search points saved by LDSPS compared

with HEXBS for each motion vector location.

Large Diamond and Small Pentagon Search Patterns 613

In the video, the majority movement is along the horizontal direction, so this paper

discusses the search points of the HEXBS algorithm and the LDSPS algorithm in the

horizontal direction just as an example. Showed in Fig.5, the point (0,6k) is selected as

the comparison point, H k represents the number of search points when using the

HEXBS, while N k represents the number of search points when using the LDSPS.

According to HEXBS and LDSPS:

H 0 = 7 + 4, altogether needs 2 steps, 11 search points;

N 0 = 5 + 5, altogether needs 2 steps, 10 search points;

H 1 = 7 + 3 + 3 + 3 + 4, altogether needs 5 steps, 20 search points;

N 1 = 5 + 3+3+5, altogether needs 4 steps, 16 search points;

H 2 = 7 + 3 + 3 + 3 + 3 + 3 + 3 + 4, altogether needs 8 steps, 29 search points;

N 2 = 5 + 3+3+3+3 + 5, altogether needs 6 steps, 22 search points;

H k = 7 + 9k + 4, altogether needs 3k + 2 steps, 9k + 11 search points;

N k = 5 + 6k + 5, altogether needs 2k + 2 steps, 6k + 10 search points;

The speed improvement ratio(SIR) is defined as follow:

(9k + 11) (6k + 10) 3k + 1

SIR = 100% = 100%

6k + 10 6k + 10

When k=0, SIR is 10.0%; When k=1, SIR is 25.0%; When k=2, SIR is 31.8%; For

the large motion vector, the SIR is close to 50%.

Fig. 5. Assume that the motion vectors are in the horizontal direction with values of (0, 6k); k = 1;

2; 3 . . . : It is easy to see that to find these motion vectors, the number of search points for the

LDSPS algorithm follows 6k + 10, whereas the number for HEXBS is 9k + 11 .

5 Experimental Results for Comparison

The experimental condition is as follows. The distortion measurement of mean absolute

difference (MAD) is used, block size:8 8, and search window size of 15 . Seven standard

614 J. Song et al.

video sequences Mother, Foreman, Flower, Basket, Mobile (352 288), Boat and

Piano (720 576) were used, which vary in motion content as well as frame size. Average

MAD values and average search point numbers are summarized in Tables I and II for

different algorithms, including FS, NTSS, FSS, DS, HEXBS and our proposed LDSPS,

respectively. Note that only the search region inside the image boundary is considered

consistently for all the fast algorithms tested to make a fair comparison.

We can see that the proposed LDSPS consumes the smallest number of search points

with just a slight increase in MAD compared with other fast algorithms. The number of

search points used by the LDSPS method is substantially smaller than that by NTSS,

FSS, DS, or HEXBS, nearly half the number of NTSS. Here, we mainly compare the

HEXBS with the proposed LDSPS algorithm in terms of number of search point as well

as MAD. According to Tables 1 and 2, Table 3 particularly tabulates the average SIR

and average MAD increase in percentage of the proposed LDSPS over HEXBS. For

Mother sequence with motion vectors limited within a small region around, our

proposed LDSPS achieves 11.14% speed improvement over HEXBS. For Foreman

sequence with medium motion, the average SIR of LDSPS over HEXBS is 11.26%. For

Mobile and Boat which contain large motion, as predicted in theory, our LDSPS

has obtained higher speed improvement over HEXBS, here more than 22%. The large

the motion in a video sequence, the large the speed improvement rate of LDSPS over

HEXBS or the other fast algorithms will be. On the other hand, the change in MAD of

LDSPS compared with HEXBS is trivial, some video sequence less than 1.04% or

smaller of MAD increase, while the other video sequences MAD is decrease as high as

1.30%.

Table 1. Average MAD per pixel for different methods and different video sequence(proposed

methods are highlighted)

Mother Foreman Basket Flower Mobile Boat Piano

FS 1.086 5.884 4.963 5.963 11.656 8.478 2.257

NTSS 1.093 5.900 4.999 6.075 11.706 9.076 2.284

FSS 1.093 5.917 4.985 6.162 11.871 10.635 2.313

DS 1.091 5.920 4.980 6.104 11.734 9.390 2.310

HEXBS 1.096 5.974 4.993 6.228 11.965 9.678 2.312

LDSPS 1.095 5.996 5.003 6.293 11.957 9.552 2.295

Table 2. Average number of search points per block with respect to different methods and

different video sequence(proposed methods are highlighted). Note that the search point number

per block for the FS is Fixed as 961 for all video sequences.

Mother Foreman Basket Flower Mobile Boat Piano

FS 961-***-***-*** 961 961 961

NTSS 18.29 18.34 20.61 24.20 22.20 34.93 29.81

FSS 17.52 17.56 19.24 20.55 20.11 23.94 22.65

DS 14.08 13.99 16.95 18.55 17.51 34.76 22.00

HEXBS 11.38 11.46 13.39 14.58 14.19 22.53 16.32

LDSPS 10.24 10.30 11.61 12.83 11.62 18.34 15.00

Large Diamond and Small Pentagon Search Patterns 615

Table 3. Average SIR and Average MAD increase in percentage of LDSPS over HEXBS

Mother Foreman Basket Flower Mobile Boat Piano

Avg.SIR 11.14 11.26 15.29 13.65 22.11 22.83 8.83

Avg.MAD -0.09 0.37 0.20 1.04 -0.07 -1.30 -0.74

increase Fig. 6(a) and (b) plot a frame-by-frame comparison of MAD and search point

number per block respectively for the different algorithms applied to Basket

sequence. Fig. 6(a) shows the similar MAD performance for all the methods tested,

while Fig. 6(b) clearly manifests the substantial superiority of the proposed LDSPS to

the other methods in terms of number of search points used. From Fig. 6(b), we can also

see that the curve of the proposed LDSPS fluctuates much less violently than that of

HEXBS with respect to the number of search points. Apparently, all the experimental

results substantially justify the fastest performance of the proposed LDSPS algorithm

as compared with the other popular fast algorithms.

(a)

(b)

Fig. 6. Performance comparison of FSS, DS, HEXBS and the proposed LDSPS for Basket

sequence in terms of: (a) average MAD per pixel and (b) the average number of search points per

block

616 J. Song et al.

6 Conclusion

A novel fast algorithm using a large diamond and small pentagon search patterns in

block motion estimation is proposed in this paper, which demonstrates significant

speedup gain over the HEXBS and other fast search methods while maintaining similar

distortion performance. The proposed LDSPS consistently has a faster search

performance than DS, regardless of no-, small-, medium-, or large-motion. Strikingly,

for large motion image sequences, the new method may use much fewer search points

than the HEXBS algorithm. Theoretical analysis shows that a speed improvement of up

to 50% over the HEXBS algorithm can be obtained for locating some motion vectors in

certain scenarios. In other words, the new algorithm may find any motion vector in

motion field with fewer search points than the HEXBS algorithm. Generally speaking,

the large the motion vector, the more significant the speedup gain for the new method

will be. The experimental results have verified the statement, which have convincingly

demonstrated the superiority of the proposed LDSPS to the other fast methods in terms

of using the smallest number of search points with a very small penalty of marginal

degradation in distortion. Note that based on the LDSPS algorithm and combined the

prediction of search beginning point with the search stop criterion ahead of time,

motion estimation algorithm may be further speeded up.

References

1. T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro.: Motion compensated interframe

coding for video conferencing. In Proc. Nat. Telecommun. Conf., New Orleans, LA, Nov.

29 Dec. 3 1981, pp. G5.3.1 5.3.5.

2. R. Li, B. Zeng, and M. L. Liou.: A new three-step search algorithm for block motion

estimation. IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438 442, Aug. 1994.

3. L. M. Po and W. C. Ma.: A novel four-step search algorithm for fast lock motion estimation,

IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313 317, June 1996.

4. L. K. Liu and E. Feig.: A block-based gradient descent search algorithm for block motion

estimation in video coding. IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 419 423,

Aug. 1996.

5. S. Zhu and K.-K. Ma.: A new diamond search algorithm for fast blockmatching motion

estimation. IEEE Trans. Image Processing, vol. 9, pp.287 290, Feb. 2000.

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, pp.369 377, Aug. 1998.

7. Ce Zhu, Xiao Lin, and Lap-Pui Chau.: Hexagon-Based Search Pattern for Fast Block Motion

Estimation. IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp. 349-355, May 2002.

8. Peng Yang, Yuwen He, Shi Qiang Yang.: An Unsymmetrical-Cross Multi-Resolution

Motion Search Algorithm For Mpeg4-Avcm. 264 Coding. IEEE International Conference on

Multimedia and Expo (ICME), pp.531-534, 2004.

9. Yang Peng, Wu Hua, Yang Shiqiang.: Fast motion estimation algorithm for H.264. Journal of

Tsinghua University(Science and Technology),2005, Vo l. 45, No. 4.

Contact this candidate