Multimed Tools Appl

DOI 10.1007/s11042-016-3562-4

All-layer search algorithm using mean inequality

and improved checkerboard partial distortion search
for fast motion estimation

Zhibin Pan 1 & Liang Dong 1 & Weiping Ku 1

Received: 4 August 2015 / Revised: 21 March 2016 / Accepted: 28 April 2016

# Springer Science+Business Media New York 2016

Abstract Block-matching motion estimation algorithm is used in many video compression

coding systems because it could greatly reduce the temporal redundancy between the conse-
quent video sequences. In this paper, an all-layer search algorithm using mean inequality and
improved checkerboard partial distortion search scheme for fast block-matching motion
estimation is proposed. A layer in the proposed method refers to a processed image which is
derived from the reference frame or the adjacent lower layer. Firstly, the proposed algorithm
constructs all layers from the reference frame or the adjacent lower layer by summing up all
pixels over a sub-block. Then, a new mean inequality elimination method is introduced to
reject a lot of unnecessary candidate search points on the top layers before calculating the real
block matching distortion. Finally, the proposed algorithm utilizes an improved checkerboard
partial distortion search scheme in the process of the real block distortion calculation on the
following layers to further reduce the amount of computation. Experimental results show that
the proposed algorithm can effectively reduce the computational complexity of motion
estimation meanwhile guarantee the matching quality compared to other motion estimation
algorithms. Compared to the full search algorithm, the proposed algorithm can reduce 97.30 %
computational complexity with a negligible degradation of the peak signal to noise ratio
(PSNR). Compared to the diamond search algorithm, directional gradient descent search
algorithm, partial distortion search algorithm, transform-domain successive elimination algo-
rithm and two-layer motion estimation algorithm, the proposed algorithm can also save
63.56 %, 52.73 %, 92.87 %, 85.77 % and 33.96 % computational complexity, respectively.

Keywords Motion estimation . Mean inequality elimination . Improved checkerboard partial

distortion search . All-layer search

* Zhibin Pan
zbpan@mail.xjtu.edu.cn

1
School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, People’s
Republic of China
 Multimed Tools Appl

1 Introduction

With the advent of big data era, more and more video data need to be stored and transmitted.
However, due to limitations of storage capacity and transmission bandwidth, these numerous
video data need to be compressed before they are stored and transmitted. Hence, video
compression coding system has become increasingly important. Block-matching algorithm
for motion estimation (ME) is a high-efficient method in video coding system. It can efficiently
reduce temporal redundancy of video sequences. In the block-matching ME method, the frame
of video sequence is firstly divided into a series of non-overlapping N × N sub-image blocks.
Then the motion estimation is implemented based on the blocks. Due to its simplicity and
efficiency, the block-matching ME algorithm has been widely adopted by many video coding
systems such as H.264 [23] and MPEG-4. The full search (FS) algorithm is the simplest
motion estimation algorithm. It can obtain the optimal motion vector and the best matching
quality. However, since the FS algorithm needs to exhaustively check all the candidate
matching points in the search window, it can lead to a great amount of computations.
Motion estimation occupies over 50 % computational burden in the current video coding
system. In order to reduce the computational complexity of motion estimation and speed up
the process of video compression coding, numerous fast motion estimation algorithms have
been proposed in recent years. These fast motion estimation algorithms can be classified into
two categories. One category [1, 4, 8, 10, 12–17, 20, 21] uses various search templates to
reduce the search points of ME. Well-known examples are 2-D logarithmic search (LOGS)
[12], three-step search (TSS) [20], four-step search (FSS) [15], diamond search (DS) [21],
Adaptive Rood Pattern Search (ARPS) [13, 17], hexagon-based search (HS) [4], directional
gradient descent search (DGDS) [14], etc. According to utilizing fixed or mixed search
templates and assuming the block distortion decreases monotonically as the search position
moves toward the minimum distortion point, these fast algorithms skip a lot of unnecessary
search points and reduce the computational complexity of ME. Although these fast algorithms
are simple and efficient, it is very difficult to further reduce more search points due to its
restrictions of search templates and search approaches.
Another category [2, 3, 6, 7, 9, 11, 22, 24, 25] adopts some reasonable strategies to decrease
the amount of the calculation of the real block matching distortion in the process of motion
estimation, such as partial distortion search (PDS) [6, 7, 9, 24, 25] algorithm, transform-
domain successive elimination algorithm (TSEA) [11] and hierarchical motion estimation
(HME) [2, 3, 22] algorithm. The PDS algorithm and the TSEA algorithm only step by step
make use of a part of pixels in block matching distortion calculation to reject unnecessary
candidate search point so as to reduce the total computational complexity of motion estimation.
Moreover, the most important advantage of these partial distortion search techniques is that it
can be incorporated into any template search based on block matching for motion estimation
algorithm. However, the efficiency of these PDS algorithms is limited if it is directly applied to
the block matching distortion calculation in motion estimation. The HME algorithm firstly
generates the constructed layers from the original reference frame. Then the motion search
process is performed layer by layer on these constructed layers. The image resolution of
constructed layers is generally smaller than that of the image resolution of original reference
frame. For example, the constructed layers are sub-sampled from the original reference frame
in cross-diamond search in hierarchical search (CD-HS) algorithm [2]. Therefore, the block
matching distortion calculation for each search point can be cut down when the motion search
process is performed on constructed layers. The two-layer motion estimation (TME) [18]
Multimed Tools Appl

algorithm is also one of typical hierarchical motion estimation algorithms which combines the
advantages of template search schemes and partial distortion search techniques. If the size of
current block is N×N, the TME algorithm can construct (log2N)-1 layers. However, the TME
algorithm only uses two constructed layers to perform the motion estimation process. It is
found that all of the constructed layers can be used for motion estimation. In TME algorithm,
the pixel on the constructed layers is a summation of pixels within a block in the reference
frame. It means that there are relationships among these constructed layers. Through the
analysis of the relationship among these constructed layers, we discovered that a mean
inequality elimination scheme can be used on the upper layers to reject the unnecessary
candidate search points. Then, the motion estimation search process is performed on the
bottom layers to find the best motion vector. By this way, we can greatly speed up the motion
estimation process and reduce the computational burden of motion estimation.
In this paper, we propose a new fast block-matching motion estimation approach, which is
called all-layer motion estimation (AME) search algorithm. A layer in the proposed method
refers to a processed image which is derived from the reference frame or the adjacent lower
layer. The AME algorithm firstly constructs all-layers from the reference frame or the adjacent
lower layer by summing up the pixels over a sub-block. Then, a mean inequality elimination
method is introduced to reduce the unnecessary candidate search points before calculating the
real block matching distortion. Finally, the proposed algorithm uses an improved checkerboard
partial distortion search strategy to cut down the amount of block matching distortion
calculation so as to further reduce the computational complexity of ME. The Bcomputational
complexity^ means that all the average number of calculation operations per block when
searching for the best matched block in the motion estimation process. The proposed AME
algorithm not only reduces the search points in motion estimation, but also cuts down the
amount of computation of the block matching distortion so as to further speed up the process
of motion estimation.
The rest of the paper is organized as follows. Section 2 presents the related block-matching
motion estimation methods. In Section 3, the proposed algorithm is introduced in detail. Section 4
presents the extensive experimental results. Finally, the conclusions are given in Section 5.

2 Related work

In block-matching motion estimation algorithm, the computational complexity mainly comes

from the block matching distortion measure. Among the available block matching distortion
criteria, the Sum of Absolute Difference (SAD) is the simplest and most popular method due to
it has lower computational complexity and has similar performance compared with other block
matching distortion criteria. Let ft(x, y) and ft − 1(x, y) represent the intensity of pixel at position
(x, y) in the current frame and the reference frame, respectively. Assume the size of block is
N × N. The SAD between the current block and the candidate search point can be calculated
from Eq. (1).
N −1 N −1
X X  
SAD ¼  f ðx; yÞ−f 
t t−1 x þ d x ; y þ d y ð1Þ
x¼0 y¼0

where (dx, dy) is the relative displacement. It is obviously observed that the once calculation of
SAD requires 2N2 − 1 addition operations and N2 absolute value operations. In the process of
 Multimed Tools Appl

motion estimation, when checking a candidate search point, the SAD needs to be calculated
once. In order to find the optimal motion vector, a lot of candidate search points need be
checked. From above analysis, we can easily find that there are two approaches to reduce the
computational complexity of motion estimation. The first approach cuts down the computa-
tional complexity of motion estimation by reducing the number of search points. The repre-
sentative algorithms are template search methods such as TSS algorithm, DS algorithm, HS
algorithm and DGDS algorithm. The second approach reduces the computational complexity
by decreasing the amount of calculation of SAD such as PDS algorithm and TME algorithm.

2.1 Partial distortion search algorithm

The partial distortion search (PDS) algorithm [5] was firstly used in the vector quantization
(VQ) encoding process. Because of its excellent performance, then the PDS algorithm is also
used in the process of motion estimation. The PDS algorithm divides the total distortion
calculation into several groups of pixels’ distortion calculation. The PDS algorithm is defined
as follows. First, suppose the current block and the candidate matching block contains k
components. The total distortion between the current block and the candidate matching block
is obtained by adding these k partial distortions one by one. If the current accumulated partial
distortion is greater than the minimum distortion, the candidate matching block can be rejected,
and the remaining partial distortions do not need to be calculated. Otherwise, the minimum
distortion will be updated. The PDS algorithm can greatly cut down the number of the block
matching distortion calculation so as to reduce the computational complexity of ME.

2.2 Two layer motion estimation algorithm

In 2014, Paramkusam and Reddy proposed a two-layer motion estimation (TME) algorithm
which performs ME on two layers that are constructed from the reference frame directly [18].
The two layers are composed by a set of macro-pixels which are a summation of pixels within
a block in the reference frame. If the size of current block is N × N, the TME algorithm can
construct l layers, 0 ≤ l ≤ (log2N) − 1. Let ft − 1(x, y) represents the intensity of pixel at position
(x, y) in the reference frame, ftl − 1(x, y) represents the value of a macro-pixel at position (x, y) on
the lth layer. The summation of macro-pixel can be calculated by (2).

ððN =2l Þ−1Þ ððN =2l Þ−1Þ

X X
f lt−1 ðx; yÞ ¼ f t−1 ðx þ a; y þ bÞ; 0≤l ≤ ðlog 2 N Þ−1 ð2Þ
a¼0 b¼0

The basic idea of TME algorithm is to reduce the computational complexity by reducing the
amount of the block matching distortion calculations. The TME algorithm used a partial sum
of absolute differences (PSAD) to calculate the block matching distortion when the ME is
performed on two layers. The PSAD is defined in Eq. (3).

2l −1 2l −1    
X X uN vN ðu;vÞ 
PSADl ðx; yÞ ¼ f l p þ x þ ; q þ y þ −M
 t−1 2l 2l l 
u¼0 v¼0
ð3Þ
ðN =2l Þ−1 ðN =2l Þ−1  
ðu;vÞ
X X uN vN
Ml ¼ Bðp;qÞ m þ l ;n þ l
m¼0 n¼0 2 2
Multimed Tools Appl

where (u, v) is the index of sub-block, B(p,q)(m, n) = ft(p + m, q + n) denotes a macro-block in

the current frame with the top left corner at position (p, q). The TME algorithm utilizes the
PSAD instead of the conventional SAD calculated block matching distortion. Therefore, as
other block-matching motion estimation algorithms, when checking a candidate search point in
the process of ME, the PSAD needs to be calculated once. For each search point, it can be
obviously seen from the Eq. (3) that the number of block matching distortion calculation
operation in PSAD on the lth layer usually is only 4l in the TME algorithm. However, in the
conventional ME algorithms, the calculation of SAD requires N2 operations. If the size of
block is N × N, the maximum number of layer l will be ((log2N) − 1). For example, when N is
16, l will be 0,1,2,3. The maximum value of 4l is 64. While N2 = 256. Hence, 4l is less than N2.
Therefore, compared to other ME algorithms, TME algorithm can greatly cut down the
number of block matching distortion calculation so as to reduce the computational complexity
of ME by using the PSAD instead of SAD. TME algorithm which performs ME on two layers
instead of the reference frame can drastically reduce the computational complexity of ME.
However, the TME algorithm need to be further improved in two aspects. 1) TME
algorithm has some redundant computations when constructing layers because these two
layers are always constructed from the same reference frame. 2) TME algorithm only utilizes
two layers in the ME process. The information of other higher layers is not utilized yet.

3 The proposed scheme

In the AME algorithm, all layers which are constructed from the reference frame or the
adjacent lower layer firstly. Secondly, a mean inequality elimination scheme is used on the
upper layers to reject unnecessary candidate search points before calculating the real block
matching distortion. Finally, the proposed AME algorithm utilizes an improved checkerboard
partial distortion search method to calculate the real block matching distortion so as to further
reduce the computational complexity of ME. In the proposed AME algorithm, the PSAD
criterion is still used to calculate the block matching distortion. These improvements increase
the efficiency of the algorithm so as to further reduce the computational complexity of ME.

3.1 Construction of all layers

The TME algorithm only uses two layers which are directly constructed from the reference
frame in the ME process. However, according to a lot of experiments, we found that all layers
which are constructed from the reference frame or the adjacent lower layer can be used in the
ME process. The pixel of the constructing layer is generated by summing the pixels of a sub-
block in the reference frame or the adjacent lower layer, so it is called macro-pixel. When
constructing the layers, the addition operations of pixels will produce numerous computational
complexities. In TME algorithm, the sum norm of constructing layers is defined in Eq. (2). If
the size of reference frame is W × H. It is observed from Eq. (2) that the resolution of the lth
layer is ((W − (N/2l) + 1) × (H − (N/2l) + 1)). The two layers are always constructed from the
reference frame. This construction method will bring about many redundant addition
computations.
In order to reduce the number of addition operations of pixels when constructing the layers,
an effective method which is similar to the pyramid structure is introduced in our proposed
algorithm. The analogous pyramid structure method means that the upper layer is generated
 Multimed Tools Appl

from its adjacent lower layer or the reference frame. The details of the analogous pyramid
structure method are shown as follows:
If the size of a block is N × N, the maximum number of the layers constructed from the
reference frame will be (log2N) − 1. The value of a macro-pixel on the lth layer is denoted as
ftl − 1(x, y). It can be calculated by summing up all the pixels of a sub-block over the region 2 ×
2. The macro-pixel on the lth layer can be obtained from Eq. (4)

X
1
X
1
f lt−1 ðx; yÞ ¼ f t−1 ðx þ a; y þ bÞ; l ¼ ðlog2 N Þ−1
a¼0 b¼0
ð4Þ
XX
1 1
f lt−1 ðx; yÞ ¼ t−1 ðx
f lþ1 þ a; y þ bÞ; 0≤l < ðlog2 N Þ−1
a¼0 b¼0

From Eq. (4), it can be seen that the bottom layer (l = (log2N) − 1) constructed from the
reference frame, and the other layers constructed from their adjacent lower layer. If the block
size N is 16, then four layers (i.e., the 0th layer, the 1st layer, the 2nd layer and the 3rd layer) can
be constructed. First, the bottom 3rd layer is constructed from the reference frame by summing
up the pixels of a sub-block over the region 2 × 2 according to the Eq. (4). Then the upper 2nd
layer is constructed from the bottom 3rd layer using the same method. In the same way, the
other two upper layers are constructed from the adjacent lower layers. Notice that only the
bottom layer (l = (log2N) − 1) is constructed from the reference frame, and the other layers are
generated from their adjacent lower layer. The construction steps of four layers are shown in
Fig. 1. The analogous pyramid structure method avoids redundant addition computations of
pixels when constructing layers, so it also reduces the total computational complexity of ME.
After four layers are constructed, the proposed AME algorithm uses a mean inequality
elimination scheme on the two upper layers (i.e., the 0th layer and the 1st layer) and utilizes an
improved checkerboard partial distortion search method on the two bottom layers (i.e., the 2nd
layer and the 3rd layer) to reduce the computational complexity of ME.

3.2 Mean inequality elimination scheme

The proposed AME algorithm introduces a mean inequality elimination scheme to reject the
unnecessary candidate search points after four layers having been constructed. The mean

Reference frame
layer layer layer
layer
step1 step2 step3 step4
Fig. 1 The construction process of the layers by using our proposed method
Multimed Tools Appl

inequality elimination scheme is an early termination method. It was usually used in the vector
quantization (VQ) encoding process [19]. For k dimensional vector x, its mean is defined as
 
k−1
mx ¼ ∑ xi =k. Assume the current k dimensional vector is x, the candidate matching k
i¼0
dimensional vector is y, and the current minimum distortion is dmin. The mean of the current k
dimensional vector x is denoted as mx, the mean of the candidate k dimensional candidate
matching vector y is denoted as my. The mean inequality is defined in inequality (5):
  pffiffiffiffiffiffiffiffiffiffiffiffiffi
mx −my  ≥ d min =k ð5Þ

If the candidate matching k dimensional vector y satisfied inequality (5), y will be rejected.
Due to its superior performance, the mean inequality elimination scheme also can be intro-
duced in motion estimation.
In the process of motion estimation, Assume the size of the current block is N × N, Mt(x, y)
represents the mean of pixel of the block in the current frame with the top left corner at position
(x, y), and Mt − 1(x + dx, y + dy) represents the mean of pixel of the block in the reference frame
with the top left corner at position (x + dx, y + dy).
N −1 N −1
1 XX
M t ðx; yÞ ¼ f ðx þ m; y þ nÞ ð6Þ
N 2 m¼0 n¼0 t

N −1 N −1
  1 XX  
M t−1 x þ d x ; y þ d y ¼ 2 f x þ d x þ m; y þ d y þ n ð7Þ
N m¼0 n¼0 t−1

where ft(x, y) and ft − 1(x, y) represent the intensity of pixel at position (x, y) in the current frame
and the reference frame respectively. (dx, dy) is the relative displacement. Then, the mean
inequality in motion estimation process can be rewritten as
   qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
M t ðx; yÞ−M t−1 x þ d x ; y þ d y  ≥ d min =N 2 ð8Þ

where dmin denotes the current minimum distortion between the current block and the
candidate matching block.
In this paper, we extend the mean inequality elimination scheme to a multilayer case so as
to achieve tighter and tighter decision boundaries for eliminating more unnecessary candidate
search points. If the size of block is N × N, the proposed AME algorithm can construct l layers,
0 ≤ l ≤ (log2N) − 1. The mean elimination inequality used in our AME algorithm is defined as
inequality (9)

 qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
2 −1 2 −1
l l
X X 
M l ðx; yÞ−M l x þ d x ; y þ d y  ≥ d min =N 2 ð9Þ
t t−1
m¼0 n¼0

where Mlt(x, y) represents the mean of pixel of the block on the lth layer in the current frame
with the top left corner at position (x, y), and Mtl − 1(x + dx, y + dy) represents the mean of pixel
of the block on the lth layer in the reference frame with the top left corner at position (x + dx, y +
dy). On the different layer, the mean inequality for elimination is different. In our AME
algorithm, the current minimum block matching distortion dmin is denoted as PSADmin. The
 Multimed Tools Appl

proposed AME algorithm uses mean inequality elimination scheme on two upper layers (i.e.,
the 0th layer and the 1st layer). The mean elimination inequalities used on the 0th layer and the
1st layer are shown in (10) and (11), respectively.
 0   qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
M ðx; yÞ−M 0 x þ d x ; y þ d y  ≥ PSADmin =N 2 ð10Þ
t t

X X  qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
1 1
 1 
M ðx; yÞ−M 1 x þ d x ; y þ d y  ≥ PSADmin =N 2 ð11Þ
t t
m¼0 n¼0

The proposed AME algorithm utilizes the mean inequality elimination method on the top
0th layer and the 1st layer to reject unnecessary candidate search points before calculating the
real distortion, so as to reduce the computational complexity of ME. In AME algorithm, the
mean inequality elimination scheme is firstly used before calculating the real block matching
distortion. When checking a candidate search point, the mean inequality elimination scheme is
firstly used in 0th layer to determine whether or not this candidate search point will be rejected
before calculating the real block matching distortion. If the current candidate point satisfies
Eq. (10), it will be rejected. Then, go to check the next candidate search point. Otherwise, the
mean inequality elimination scheme is used in 1st layer to determine whether or not this
candidate search point will be rejected. If the current candidate search point satisfies Eq. (11), it
will be rejected. Then, go to check the next candidate search point. Otherwise, the real block
matching distortion of the current search point will be calculated.
The AME algorithm uses the mean inequality elimination scheme on the 0th layer and 1st
layer to reject unnecessary candidate search points, and performs ME search on the 2nd layer
and the 3rd layer by using the diamond search method [21]. To demonstrate the effectiveness
of the proposed mean inequality elimination scheme, we evaluate the elimination rate of search
points on the 2nd layer and the 3rd layer, respectively. Our experiments utilize twenty typical
video sequences which cover a wide range of motion characteristics and have various formats.
The formats of the test video sequences used in the experiments are listed in Table 1. The
experimental results are shown in Table 2.
In Table 2, the ratio represents the average elimination rate of the search points for mean
inequality elimination scheme. It is defined as Eq. (12)

T M E searchpoints −AME searchpoints

ratio ¼  100 ð12Þ
T M E searchpoints

It can be observed in Table 2 that the average elimination rate of the search points on the
2nd layer and the 3rd layer are 64.1 % and 28.9 %, respectively. This result implies that many
unnecessary candidate search points can be rejected by using the mean inequality elimination
scheme before calculating the real block matching distortion.

3.3 Improved checkerboard partial distortion search method

As previously mentioned, the proposed AME algorithm firstly utilizes a mean inequality
elimination scheme to reject unnecessary candidate search points. If the candidate search
points cannot be rejected, the block matching distortion of the candidate search points will be
calculated. In the proposed AME algorithm, we still use the PSAD criterion to calculate the
block matching distortion. However, the calculation of the PSAD also will generate huge
Multimed Tools Appl

Table 1 Test video sequences

used in our experiments Video sequence The number Format Size
of frames

Akiyo 298 QCIF 176 × 144

Carphone 379 QCIF 176 × 144
Coastguard 298 CIF 352 × 288
Container 73 QCIF 176 × 144
Football 258 CIF 352 × 288
Foreman 298 CIF 352 × 288
Hall_monitor 327 QCIF 176 × 144
Mobile 298 CIF 352 × 288
Mother_and_daughter 297 QCIF 176 × 144
News 297 QCIF 176 × 144
Soccer 298 CIF 352 × 288
Suzie 148 QCIF 176 × 144
Waterfall 258 CIF 352 × 288
Ballroom 250 VGA 640 × 480
Exit 250 VGA 640 × 480
Tunnel 150 D1_PAL 720 × 576
Kendo 150 XGA 1024 × 768
Newspaper 200 XGA 1024 × 768
Shark 100 1080HD 1920 × 1080
PoznanStreet 120 1080HD 1920 × 1080

computational complexity. In order to further reduce the computational complexity of ME, we

utilize an improved checkerboard partial distortion search (ICPDS) method to calculate the
PSAD. The ICPDS method divides the current block and the candidate blocks into four
components according to the improved checkerboard form, as shown in Fig. 2. The conven-
tional checkerboard form divides the current block into two parts. However, we use the
improved checkerboard form to divide the current block into four components. In Fig. 2, each
color represents a component. The PSAD calculation is also divided into four parts. The total
distortion is obtained by adding these four partial distortions one by one. If the current
accumulated partial distortion PSAD is greater than the minimum distortion PSADmin, the
candidate block can be rejected, and the remaining partial distortions need not to be calculated.
Otherwise, the PSADmin will be updated. There is only a part of PSAD of a block needs to be
calculated in the proposed algorithm. Therefore, the ICPDS method can further reduce the
computational cost of ME.

3.4 Summary of AME

The proposed AME algorithm performs ME on all layers. The AME algorithm firstly
constructs all layers from the reference frame or the adjacent lower layer. Then, a mean
inequality elimination method is used to reject unnecessary candidate search points before
calculating the value of PSAD. Finally, the ICPDS scheme is utilized to further reduce the
computational complexity of ME when calculating the value of PSAD. The AME search steps
can be summarized as follows:
 Multimed Tools Appl

Table 2 The elimination rate of search points for twenty test video sequences when mean inequality elimination
scheme is used in the proposed AME

Video sequence The 2nd layer The 3rd layer Total search point

TME AME Ratio TME AME Ratio TME AME Ratio

Akiyo 7.83 1.04 86.7 % 4.62 1.17 74.7 % 12.45 2.21 82.3 %
Carphone 7.83 2.31 70.5 % 6.06 3.39 44.1 % 13.89 5.70 59.0 %
Coastguard 8.40 3.51 58.2 % 6.20 5.03 18.9 % 14.60 8.54 41.5 %
Container 7.83 1.23 84.3 % 4.64 2.18 53.0 % 12.47 3.41 72.7 %
Football 8.40 5.49 34.6 % 13.81 12.74 7.8 % 22.21 18.23 17.9 %
Foreman 8.40 3.53 58.0 % 9.16 6.77 26.1 % 17.56 10.30 41.3 %
Hall_monitor 7.83 1.54 80.3 % 4.96 2.38 52.0 % 12.79 3.92 69.4 %
Mobile 8.40 3.43 59.2 % 6.99 5.17 26.0 % 15.39 8.60 44.1 %
Mother&daughter 7.83 1.66 78.8 % 5.06 2.56 49.4 % 12.89 4.22 67.3 %
News 7.83 1.30 83.4 % 4.88 1.67 65.8 % 12.71 2.97 76.6 %
Soccer 8.40 5.10 39.3 % 12.08 10.33 14.5 % 20.48 15.43 24.7 %
Suzie 7.83 1.95 75.1 % 5.55 3.27 41.1 % 13.38 5.22 61.0 %
Waterfall 8.40 1.77 78.9 % 5.14 3.72 27.6 % 13.54 5.49 59.5 %
Ballroom 8.65 2.89 66.6 % 7.67 5.69 25.8 % 16.32 8.58 47.4 %
Exit 8.65 4.65 46.2 % 7.93 6.46 18.5 % 16.58 11.11 33.0 %
Tunnel 8.70 2.28 73.8 % 7.60 4.99 34.3 % 16.30 7.27 55.4 %
Kendo 8.78 4.46 49.2 % 9.50 7.47 21.4 % 18.28 11.93 34.7 %
Newspaper 8.78 2.52 71.3 % 6.62 3.74 43.5 % 15.40 6.26 59.4 %
Shark 8.86 5.12 42.2 % 13.62 11.51 15.5 % 22.48 16.63 26.0 %
PoznanStreet 8.86 4.10 53.7 % 6.78 5.64 16.8 % 15.64 9.74 37.7 %
Average 8.32 2.99 64.1 % 7.44 5.29 28.9 % 15.77 8.29 47.4 %

Step1: Construct all layers by using the analogous pyramid structure method. In our
proposed algorithm, the block size is 16 × 16, therefore, four layers (i.e., the 0th
layer, the 1st layer, the 2nd layer and the 3rd layer) will be constructed.
Step2: Perform the motion estimation search on the 2nd layer using the large diamond search
pattern (LDSP) only once to obtain the minimum distortion point. It will be the initial

Fig. 2 Macro-block partition in

PSAD calculation on the 2nd layer
and the 3rd layer which is used in
the improved checkerboard partial
distortion search method

(a) (b)
Multimed Tools Appl

search center in the next layer. The LDSP is shown in Fig. 3a. For each candidate
point, the mean inequality elimination method is used on the 0th layer and the 1st
layer respectively to reject the unnecessary candidate search point. If the candidate
point can be rejected, then go to check the next candidate search point. Otherwise, an
ICPDS method is adopted to calculate the block matching distortion for the candidate
points by using the PSAD criteria.
Step3: Perform the motion estimation search on the 3rd layer cyclically using the small
diamond search pattern (SDSP) until the minimum block distortion point falls in the
center position of the small diamond search pattern to obtain the minimum distortion
point. The SDSP is shown in Fig. 3b. As mentioned above, for each search point, the
mean inequality elimination method is used on the 0th layer and the 1st layer
respectively to reject the impossible candidate search points. If the candidate point
can be rejected, then go to check the next candidate search point. Otherwise, an
ICPDS method is adopted to calculate the block matching distortion of the candidate
points by using the PSAD criteria. Figure 4 illustrates the flowchart of the whole
AME algorithm.

4 Experimental Results

Numerous experiments are conducted to illustrate the performance and the effectiveness of the
proposed AME algorithm. In our experiments, the size of the blocks in the current frame is
16 × 16 and the search range is set to 15 × 15 pixels. Our experiments utilize twenty typical
video sequences which cover a wide range of motion characteristics and have various formats,
as shown in Table 1. The average Peak Signal to Noise Ratio (PSNR) per frame and the
average number of total operations per block of the ME of different video sequences are
measured in the experiments. We compare the proposed AME method with the FS algorithm,
TSS algorithm, DS algorithm, DGDS algorithm, CD-HS algorithm, PDS algorithm, TSEA
algorithm and the TME algorithm. The experimental results of the average PSNR per frame of
the ME are shown in Table 3. The PSNR is usually used to evaluate the matching quality of the
motion estimation algorithm. From Table 3, it can be found that the PSNR values of the
proposed AME are exactly equal to PSNR of the TME algorithm. In addition, compared to
TSS algorithm, DS algorithm, DGDS algorithm and the CD-HS algorithm, the decrease of the

Fig. 3 The large diamond search

pattern and the small diamond
search pattern

(a) LDSP (b) SDSP

 Multimed Tools Appl

Begin

Construct all layers

Search on the 2nd layer

using the LDSP

For each search point, use mean inequality

elimination algorithm on the 0th layer

Y
Search point can be rejected ?

N
Use the mean inequality elimination The search point is rejected,
algorithm on the 1st layer go to the next search point

Y
N
Search point can be rejected ?

Calculate the PSAD of search Find the minimum distortion point, it is the The search point is rejected,
point using the ICPDS method initial search center in the 3rd layer go to the next search point

Search on the 3rd layer using the SDSP

For each search point, use mean inequality

elimination algorithm on the 0th layer

Y
Search point can be rejected ?
N
The search point is rejected,
Use the mean inequality elimination go to the next search point
algorithm on the 1st layer
Y
N
Search point can be rejected ?

The search point is rejected,

Calculate the PSAD of search
go to the next search point
point using the ICPDS method

Find the minimum distortion point from

all un-rejected candidate search points

END

Fig. 4 Flowchart of the AME algorithm

average PSNR values of the proposed method are 0.13 dB, 0.09 dB, 0.12 dB and 0.23 dB,
respectively. That reduction in the PSNR of the proposed method is acceptable. It should be
noted that the average PSNR of TSEA algorithm higher than the average PSNR of FS
algorithm. This is because the TSEA algorithm uses the sum of squared differences (SSD)
criterion in transform domain, the other comparison algorithms utilizing the sum of absolute
differences (SAD) criterion. The SSTD between the current block and the candidate search
block can be calculated as Eq. (13).
N −1 N −1
X X  2
SSD ¼ f t ðx; yÞ−f t−1 x þ d x ; y þ d y ð13Þ
x¼0 y¼0
Multimed Tools Appl

Table 3 The average PSNR per frame (dB) among different algorithms

Video sequence FS TSS DS DGDS PDS TME CD-HS TSEA AME_SSD AME

Akiyo 44.30 44.30 44.30 44.30 44.30 44.27 44.30 44.31 44.29 44.27
Carphone 31.40 31.20 31.22 31.24 31.40 31.16 31.31 31.51 31.32 31.16
Coastguard 30.43 30.26 30.36 30.36 30.43 30.32 30.39 30.56 30.39 30.32
Container 43.72 43.72 43.72 43.72 43.72 43.72 43.72 43.72 43.72 43.72
Football 23.97 23.61 23.34 23.48 23.97 23.16 23.63 24.10 23.84 23.16
Foreman 31.20 30.70 30.82 30.92 31.20 30.66 31.11 31.31 30.94 30.66
Hall_monitor 36.93 36.92 36.92 36.92 36.93 36.91 36.92 37.00 36.91 36.91
Mobile 24.55 24.26 24.49 24.52 24.55 24.40 24.53 24.58 24.45 24.40
Mother_and_daughter 41.14 41.08 41.10 41.11 41.14 41.07 41.11 41.22 41.11 41.07
News 36.25 36.19 36.20 36.19 36.25 36.18 36.22 36.39 36.21 36.18
Soccer 25.95 25.50 25.31 25.33 25.95 25.27 25.64 26.10 25.73 25.27
Suzie 36.12 35.95 36.05 36.09 36.12 35.98 36.10 36.27 36.17 35.98
Waterfall 34.57 34.57 34.57 34.57 34.57 34.54 34.57 34.58 34.55 34.54
Ballroom 29.56 29.40 29.29 29.33 29.56 29.22 29.39 29.72 29.48 29.22
Exit 35.62 35.42 35.37 35.33 35.62 35.24 35.55 35.77 35.37 35.24
Tunnel 30.37 29.74 29.63 29.42 30.37 29.25 30.25 30.58 29.39 29.25
Kendo 32.74 32.36 32.44 32.51 32.74 32.37 32.57 32.86 32.36 32.37
Newspaper 38.64 38.28 38.31 38.33 38.64 38.22 38.39 38.78 38.55 38.22
Shark 30.43 29.52 28.87 29.13 30.43 28.66 29.34 30.54 29.67 28.66
PoznanStreet 33.59 33.39 33.26 33.32 33.59 33.17 33.37 33.68 33.49 33.17
Average 33.57 33.32 33.28 33.31 33.57 33.19 33.42 33.68 33.40 33.19

ft(x, y) and ft − 1(x, y) represent the value of Hadamard transform of pixel at position (x, y) in the
current frame and the reference frame, respectively. To make experiment comparison fair, we
also used the SSD criterion in our proposed AME algorithm, which is denoted as AME_SSD.
We compare the TSEA algorithm with the AME_SSD algorithm. The experiment results shown
that our proposed AME algorithm can be used not only SAD criterion, but also SSD criterion.
Figure 5 draws the average PSNR per frame for the Carphone sequence, Foreman
sequence, Exit sequence, Tunnel sequence, Newspaper sequence and PoznanStreet sequence,
respectively. It shows that the proposed AME algorithm maintains similar PSNR compared to
the FS algorithm, TSS algorithm, DS algorithm, DGDS algorithm, CD-HS algorithm, PDS
algorithm, TSEA algorithm and TME algorithm.
Table 4 illustrate the average number of total operations per block of the ME. It is worth
mentioning that all addition operations of constructing layers are included in the total
computational operations of the proposed AME algorithm and the TME algorithm. It can be
observed from Table 4 that the proposed AME algorithm has the least number of operations in
block distortion calculation than other ME algorithms. Compared to the FS algorithm, the
proposed AME algorithm saves 97.30 % computational complexity in the process of ME.
Compared to the TSS algorithm, DS algorithm, DGDS algorithm, CD-HS algorithm, PDS
algorithm and TSEA algorithm, the reduction of the average number of total operations per
block of the proposed AME algorithm is 76.35 %, 63.65 %, 52.73 %, 84.75 %, 92.87 % and
85.77 %, respectively. Even compared to the recent TME algorithm, the proposed method also
reduces 33.96 % number of total operations per block. These great savings in the number of
total operations per block illustrate that the proposed AME algorithm greatly reduces the
computational complexity of ME than other fast motion estimation algorithm.
 Multimed Tools Appl

Carphone
42
FS TSS DS DGDS PDS TSEA CD-HS TME AME
40

38

36
PSNR per frame (dB)

34

32

30

28

26

24

22
50 100 150 200 250 300 350
Frame Number
(a) Carphone (379 frames, 176×144)
Foreman
40
FS TSS DS DGDS PDS TSEA CD-HS TME AME
38

36
PSNR per frame (dB)

34

32

30

28

26

24

22

20
50 100 150 200 250
Frame Number
(b) Foreman (298 frames, 352×288)
Exit
38
FS TSS DS DGDS PDS TSEA CD-HS TME AME
37

36
PSNR per frame (dB)

35

34

33

32

31

30

29

28
50 100 150 200
Frame Number
(c) Exit (250 frames, 640×480)
Fig. 5 The average PSNR per frame for the Carphone, Foreman, Exit, Tunnel, Newspaper and PoznanStreet sequence
Multimed Tools Appl

Tunnel
36
FS TSS DS DGDS PDS TSEA CD-HS TME AME

34

PSNR per frame (dB)

32

30

28

26

24
20 40 60 80 100 120 140
Frame Number
(d) Tunnel (150 frames, 720×576)
Newspaper
44
FS TSS DS DGDS PDS TSEA CD-HS TME AME

42

40
PSNR per frame (dB)

38

36

34

32

30
20 40 60 80 100 120 140 160 180
Frame Number
(e) Newspaper (200 frames, 1024×768)
PoznanStreet
38
FS TSS DS DGDS PDS TSEA CD-HS TME AME

36
PSNR per frame (dB)

34

32

30

28

26
10 20 30 40 50 60 70 80 90 100 110
Frame Number
(f) PoznanStreet (120 frames, 1920×1080)

Fig. 5 (continued)
Table 4 The average number of total operations per block among different algorithms

Video sequence FS TSS DS DGDS PDS TME CD-HS TSEA AME_SSD AME

Akiyo 141737.7 16499.4 8777.3 3640.8 13507.0 5715.8 9641.5 2696.8 3268.9 3230.7
Carphone 141737.7 16603.4 10064.1 7707.3 42623.2 5991.8 31944.2 15944.2 3872.3 3691.0
Coastguard 156888.2 17950.6 12680.8 9120.8 67914.9 6122.8 23714.5 20541.7 4013.9 4038.2
Container 141737.7 16500.7 8784.5 6034.0 24755.9 5719.0 10324.2 4384.2 3397.1 3333.9
Football 156888.2 18016.8 16833.8 16521.0 100019.4 7583.9 41203.5 68819.4 6072.3 5873.3
Foreman 156888.2 17917.5 13330.4 11389.3 74525.6 6691.4 46525.6 33169.9 4742.7 4544.3
Hall_monitor 141737.7 16507.4 8859.4 6158.4 29417.9 5779.7 13238.4 8608.0 3607.3 3464.4
Mobile 156888.2 17838.4 10233.4 7595.4 58670.3 6274.6 23155.6 19842.6 4053.4 4029.5
Mother_and_daughter 141737.7 16519.1 9113.8 6507.3 33425.0 5799.5 14764.1 11232.8 3569.9 3476.4
News 141737.7 16499.5 8958.5 5248.1 20850.0 5764.6 11386.9 5063.8 3379.5 3322.0
Soccer 156888.2 18118.1 15860.6 13709.6 91906.0 7251.3 39521.3 49959.2 5468.0 5268.1
Suzie 141737.7 16556.7 9615.9 7178.7 44230.2 5892.8 16128.7 13791.8 3742.8 3611.3
Waterfall 156888.2 17825.9 9420.6 6713.5 39052.8 5918.4 11365.2 12059.9 3706.3 3680.4
Ballroom 163516.4 18443.3 11536.1 8873.7 61361.5 6434.6 30219.3 28304.5 4525.3 4335.2
Exit 163516.4 18442.7 11664.2 8402.8 84815.0 6483.8 28206.1 60530.1 4703.5 4611.5
Tunnel 164827.9 18521.5 11827.8 9089.8 55481.8 6430.3 17481.8 24293.7 4383.2 4160.1
Kendo 166968.0 18773.4 14219.7 12133.4 96062.7 6807.6 47865.2 59193.5 5183.2 4924.6
Newspaper 166968.0 18708.6 11132.3 8065.9 51490.2 6257.5 27132.3 20040.0 4182.1 4051.6
Shark 169101.7 18992.3 16614.5 14795.1 108748.2 7608.3 76235.8 85829.2 6023.6 5734.7
PoznanStreet 169101.7 18899.4 10885.5 8310.8 76071.7 6301.7 29345.9 44244.0 4402.4 4381.7
Average 154874.7 17706.7 11520.7 8859.8 58746.5 6341.5 27470.0 29427.5 4314.9 4188.1
Multimed Tools Appl
Multimed Tools Appl

6
Carphone
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME

The number of total operations

5
10

4
10

3
10
50 100 150 200 250 300 350
Frame Number
(a) Carphone (379 frames, 176×144)
Foreman
6
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME
The number of total operations

5
10

4
10

3
10
50 100 150 200 250
Frame Number
(b) Foreman (298 frames, 352×288)
6
Exit
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME
The number of total operations

5
10

4
10

3
10
50 100 150 200
Frame Number
(c) Exit (250 frames, 640×480)
Fig. 6 The average number of total operations per block for the Carphone, Foreman, Exit, Tunnel, Newspaper
and PoznanStreet sequence
 Multimed Tools Appl

6
Tunnel
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME

The number of total operations 5

10

4
10

3
10
20 40 60 80 100 120 140
Frame Number
(d) Tunnel (150 frames, 720×576)
Newspaper
6
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME
The number of total operations

5
10

4
10

3
10
20 40 60 80 100 120 140 160 180
Frame Number
(e) Newspaper (200 frames, 1024×768)

6
PoznanStreet
10
FS TSS DS DGDS PDS TSEA CD-HS TME AME
The number of total operations

5
10

4
10

3
10
10 20 30 40 50 60 70 80 90 100 110
Frame Number
(f) PoznanStreet (120 frames, 1920×1080)

Fig. 6 (continued)
Multimed Tools Appl

Figure 6 draws the average number of total operations per block for the Carphone sequence,
Foreman sequence, Exit sequence, Tunnel sequence, Newspaper sequence and PoznanStreet
sequence, respectively. It shows that the proposed AME algorithm has the least operations
compared to the FS algorithm, TSS algorithm, DS algorithm, DGDS algorithm, CD-HS algorithm,
PDS algorithm, TSEA algorithm and TME algorithm. The experimental results also demonstrated
that our AME algorithm can effectively reduce the computational complexity of ME.

5 Conclusions

In this paper, an all-layer search algorithm using mean inequality and an improved checker-
board partial distortion search scheme for fast block motion estimation is proposed. The
proposed AME algorithm not only greatly reduces the number of candidate search points
but also cuts down the amount of computation of block matching distortion. Compared to the
FS algorithm, the proposed AME algorithm can reduce 97.30 % computation. The proposed
AME algorithm also saves 76.35 %, 63.65 %, 52.73 %, 84.75 %, 92.87 %, 85.77 % and 33.96 %
computation than the TSS algorithm, DS algorithm, DGDS algorithm, CD-HS algorithm, PDS
algorithm, TSEA algorithm and TME algorithm, respectively. The experimental results show that
the proposed AME has a better performance than the conventional fast motion estimation
algorithm. The AME algorithm can result in much less computational complexity of ME, and
meanwhile has similar PSNR compared with other fast motion estimation algorithms.

Acknowledgments This work is supported by the Major Programs of National Natural Science Foundation of
China (Grant No. 41390454), Specialized Research Fund for the Doctoral Program of Higher Education (Grant
No. 20130201110071), Open Project Program of the National Laboratory of Pattern Recognition (Grant No.
201407370) and Open Project Program of the State Key Lab of CAD&CG (Grant No. A1115).

References

1. Ahmad I, Weiguo Z, Jiancong L, Ming L (2006) A fast adaptive motion estimation algorithm. IEEE Trans
Circuits Syst Video Technol 16(3):420–438. doi:10.1109/TCSVT.2006.870022
2. Al-Najdawi N, Noor Al-Najdawi M, Tedmori S (2014) Employing a novel cross-diamond search in a
modified hierarchical search motion estimation algorithm for video compression. Inf Sci 268:425–435. doi:
10.1016/j.ins.2013.08.009
3. Bao X, Zhou D, Liu P, Goto S (2012) An advanced hierarchical motion estimation scheme with lossless
frame recompression and early-level termination for beyond high-definition video coding. IEEE Trans
Multimedia 14(2):237–249. doi:10.1109/TMM.2011.2171677
4. Ce Z, Xiao L, Chau LP (2002) Hexagon-based search pattern for fast block motion estimation. IEEE Trans
Circuits Syst Video Technol 12(5):349–355. doi:10.1109/TCSVT.2002.1003474
5. Chang-da B, Gray RM (1985) An improvement of the minimum distortion encoding algorithm for vector
quantization. IEEE Trans Commun 33(10):1132–1133. doi:10.1109/TCOM.1096214
6. Chao-Cing Y, Gwo-Long L, Ming-Chieh C, Mei-Juan C, Chia-Hung Y (2010) Prediction error prioritizing
strategy for fast normalized partial distortion motion estimation algorithm. IEEE Trans Circuits Syst Video
Technol 20(8):1150–1155. doi:10.1109/TCSVT.2010.2056953
7. Chok-Kwan C, Lai-Man P (2000) Normalized partial distortion search algorithm for block motion estima-
tion. IEEE Trans Circuits Syst Video Technol 10(3):417–422. doi:10.1109/76.836286
8. Chun-Ho C, Lai-Man P (2002) A novel cross-diamond search algorithm for fast block motion estimation.
IEEE Trans Circuits Syst Video Technol 12(12):1168–1177. doi:10.1109/TCSVT.2002.806815
9. Chun-Ho C, Lai-Man P (2003) Adjustable partial distortion search algorithm for fast block motion
estimation. IEEE Trans Circuits Syst Video Technol 13(1):100–110. doi:10.1109/TCSVT.2002.808091
 Multimed Tools Appl

10. Chun-Ho C, Lai-Man P (2005) Novel cross-diamond-hexagonal search algorithms for fast block motion
estimation. IEEE Trans Multimedia 7(1):16–22. doi:10.1109/TMM.2004.840609
11. Chun-Su P (2013) Multilevel motion estimation based on distortion measure in transform domain. Electron
Lett 49(14):880–882. doi:10.1049/el.2013.1318
12. Jain J, Jain A (1981) Displacement measurement and its application in interframe image coding. IEEE Trans
Commun 29(12):1799–1808. doi:10.1109/TCOM.1981.1094950
13. Kai-Kuang M, Gang Q An improved adaptive rood pattern search for fast block-matching motion estimation
in JVT/H.26L. In: Circuits and systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium
on, 25–28 May 2003 2003. pp II-708-II-711 vol. 702. doi:10.1109/ISCAS.2003.1206072
14. Lai-Man P, Ka-Ho N, Kwok-Wai C, Ka-Man W, Uddin YMS, Chi-Wang T (2009) Novel directional gradient
descent searches for fast block motion estimation. IEEE Trans Circuits Syst Video Technol 19(8):1189–1195.
doi:10.1109/TCSVT.2009.2020320
15. Lai-Man P, Wing-Chung M (1996) A novel four-step search algorithm for fast block motion estimation.
IEEE Trans Circuits Syst Video Technol 6(3):313–317. doi:10.1109/76.499840
16. Lin CC, Lin Y, Hsieh HJ (2009) Multi-direction search algorithm for block motion estimation in H.264/AVC.
IET Image Process 3(2):88–99. doi:10.1049/iet-ipr.2008.0042
17. Nie Y, Kai-Kuang M (2002) Adaptive rood pattern search for fast block-matching motion estimation. IEEE
Trans Image Process 11(12):1442–1449. doi:10.1109/TIP.2002.806251
18. Paramkusam AV, Reddy VSK (2014) Two-layer motion estimation algorithm for video coding. Electron Lett
50(4):276–278. doi:10.1049/el.2013.4032
19. Ra SW, Kim JK (1993) A fast mean-distance-ordered partial codebook search algorithm for image vector
quantization. IEEE Trans Circuits Syst II, Analog Digit Signal Process 40(9):576–579. doi:10.1109/82.257335
20. Renxiang L, Bing Z, Liou ML (1994) A new three-step search algorithm for block motion estimation. IEEE
Trans Circuits Syst Video Technol 4(4):438–442. doi:10.1109/76.313138
21. Shan Z, Kai-Kuang M (2000) A new diamond search algorithm for fast block-matching motion estimation.
IEEE Trans Image Process 9(2):287–290. doi:10.1109/83.821744
22. Tedmori S, Al-Najdawi N (2012) Hierarchical stochastic fast search motion estimation algorithm. IET
Comput Vis 6(1):21–28. doi:10.1049/iet-cvi.2010.0188
23. Wiegand T, Sullivan GJ, Bjontegaard G, Luthra A (2003) Overview of the H.264/AVC video coding
standard. IEEE Trans Circuits Syst Video Technol 13(7):560–576. doi:10.1109/TCSVT.2003.815165
24. Xiaoquan Y, Nam L (2007) Improved normalized partial distortion search with dual-halfway-stop for rapid
block motion estimation. IEEE Trans Multimedia 9(5):995–1003. doi:10.1109/TMM.2007.898930
25. Xuan J, Chau LP (2007) Partial distortion search algorithm using predictive search area for fast full-search
motion estimation. IEEE Signal Process Lett 14(11):840–843. doi:10.1109/LSP.2007.900035

Zhibin Pan received the B.S. degree in Information and Telecommunication Engineering in 1985 and the M.S.
degree in Automation Science and Technology in 1988 from Xi’an Jiaotong University, P.R. China, respectively.
He received the Ph.D. degree in Electrical Engineering in 2000 from Tohoku University, Japan. He is a professor
in the Department of Information and Telecommunication Engineering, Xi’an Jiaotong University, P.R. China.
His current research interests include image compression, multimedia security and object recognition.
Multimed Tools Appl

Liang Dong received the BS degree in School of Electronic and Information Engineering, Xi'an Jiaotong
University, Xi’an, P.R. China, in 2013. She is currently pursuing her MS degree in School of Electronic and
Information Engineering, Xi’an Jiaotong University, Xi’an, P.R. China. Her research interests include image
processing, video compression coding.

Weiping Ku received the BS degree in School of Electronic and Information Engineering, Xi’an Jiaotong
University, Xi’an, P.R. China, in 2014. He is currently pursuing his MS degree in School of Electronic and
Information Engineering, Xi’an Jiaotong University, Xi’an, P.R. China. His research interests include image
processing, video compression coding.