Article Preview
Top1. 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.