An Improved Approach of Block Matching Algorithm for Motion Vector Estimation

An Improved Approach of Block Matching Algorithm for Motion Vector Estimation

Shailesh D. Kamble (Nagpur University, Nagpur, India), Sonam T. Khawase (Yeshwantrao College of Engineering, Nagpur, India), Nileshsingh V. Thakur (Prof Ram Meghe College of Engineering & Management, Amravati, India) and Akshay V. Patharkar (K.D.K. College of Engineering, Nagpur, India)
Copyright: © 2018 |Pages: 19
DOI: 10.4018/IJIRR.2018010103


Motion estimation has traditionally been used in video encoding only, however, it can also be used to solve various real-life problems. Nowadays, researchers from different fields are turning towards motion estimation. Motion estimation has become a serious problem in many video applications. It is a very important part of video compression technique and it provides improved bit rate reduction and coding efficiency. The process of motion estimation is used to improve compression quality and it also reduces computation time. Block-based motion estimation algorithms are used as they require less memory for processing of any video file. It also reduces the complexity involved in computations. In this article, various block-matching motion estimation algorithms are discussed such as Full search (FS) or Exhaust Search, Three-Step search (TSS), New Three-Step search (NTSS), Four-Step search (FSS), Diamond search (DS) etc.
Article Preview

1. Introduction

The video coding background consists of a number of various methods, namely, the lossy and the lossless compression techniques. The aim of “lossless” coding is to reduce the image or video data while retaining the quality of the original image. The aim of “lossy” coding techniques is to meet a given target bitrate for storage and transmission. In video sequences, spatial and temporal redundancies are present. These are reduced by using intra and inter frame coding techniques (Koga & Iinuma, 1981). Block-based motion estimation is the most commonly used algorithms for motion estimation in comparison to region-based and pixel-based algorithms. This is because block-based motion estimation algorithms are simple and easy to understand. Figure 1 shows the block matching motion estimation process and motion vector. In this method, two frames, i.e. current and reference, frames are considered. The current frame is divided into fixed size macroblocks of size 16×16. For the reference frame, the search area is defined for each block in the current frame. After the search is performed, the best match is found in reference frame within the search area. The process of the searching best match, block by block, is defined as block-based motion estimation.

Figure 1.

Motion Estimation Process


Motion Vector (MV) is the displacement between current candidate block and best match block within a search window in the reference frame. The maximum value of motion vector is determined by search range and it has a direct relation with the search parameter (Figure 2). Motion vector shows the displacement in horizontal and vertical directions. i.e. along x-axis and y-axis.

Figure 2.

Block Matching Motion Vector Estimation (Kamble, Thakur, & Bajaj, 2016)


Pixel based, region based and block based are three types of motion estimation algorithms. As the threshold value varies from pixel to pixel, pixel based algorithm is not preferred due to dependency on the threshold. Region based is restricted as it has large computations and complexity involved in segmentations. So mostly used is block based algorithm as it is simple and regular. Process of the searching best match, block by block, is defined as block-based motion estimation (BMA). Some block matching algorithms such as Full search, Three-step search (Koga & Iinuma, 1981), New Three step search (Li, Zeng, & Liou, 1994), Four step search (Po & Ma, 1996), are discussed below:

1.1. Full Search (FS)

The full search algorithm is also known as Exhaustive Search. It is the most computationally expensive algorithm in comparison to other algorithms. It calculates the cost for entire search window. If searching parameter p = 6, 7, 8 then it requires 169, 225, 289 iterations respectively. Computation depends on the size of the search window. A larger search window requires a large number of computations. Full Search algorithm gives the highest PSNR. So, it produces best image quality.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing