Motion Estimation Video Compression Using Fast Search Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

On video compression, motion-compensated prediction is used to reduce the temporal redundancy in the video frame sequences. Among motion estimation methods, the Block- Matching Algorithm (BMA) seems to be the most popular method for its effectiveness and simplicity to apply on both software and hardware implementations. BMA is also used widely in all current international video compression standards such as MPEG-1, MPEG-2, MPEG-4, H.261, and H.263.

Basically, each frame image is divided into non-overlapping blocks that are then compared with corresponding block and its adjacent neighbours in the previous frame. The movement of a macro block from one location to another is creating the vector and treated as one single motion vector to be estimated for all the pixels. The motion vector to be estimated is base on block matching which is minimized the matching error between the two corresponding pixels. The matching error between the position (x,y) at the current image (It) and the candidate position (x+u, y+v) at the reference image (It-1) is normally defined as the sum of absolute difference (SAD)

The search area for block matched is limited to p pixels on all fours sides of the corresponding macro block in the previous frame. This 'p' is called as search parameter which depending on the motion speeds. Larger motions will require a larger p, and the larger search parameter will require more computationally. The matching of one macro block with another is based on the output of a cost function. The macro block that results in the least cost is the one that matches the closest to current block. Besides SAD, there are several of costs functions as defined per below.

N is the side of macro block, while Cij and Rij are the pixels being compared in the current macro block and reference macro block.

Peak-Signal-to-Noise-Ratio (PSNR) given by below equation characterizes the motion compensated image that is created by using motion vectors from the reference frame.

2.0 Literature Review

In the past research, there are several fundamental block matching algorithm has been introduced and implemented. They are Full Block Matching Algorithm (FBMA), Three Step Search (TSS), New Three Step Search (NTSS) and Diamond Search (DS).

A. Full Block Matching Algorithm (FBMA)

Full Block Matching Algorithm is the most popular block matching technique because of its ability to obtain an excellent image quality at the decoder side at low control overhead. This algorithm is calculated the cost function at each possible location in the search window and finding the best possible match. As a result, it achieved the highest possible PSNR while requires more computation with the larger search window on other hand.

B. Three Step Search (TSS)

This algorithm starts with one point at the based centre and another 8 points at around with step size of 4 of each others. From this 9 point, it will calculate the cost function and pick up the one with the least cost to be the search origin. Again, it will repeat the similar search with step size of S/2 until the step size become 1. The motions vectors are then are calculated, save and transmitted.

C. New Three Step Search (NTSS)

NTSS is the alternatives of TSS by providing a centre biased searching scheme and having provisions for half way stop to reduce computational cost. It was one of the first accepted fast algorithms and widely implemented on the early standard like MPEG 1 and H.261.

TSS is allocating the check point uniformly with the same of step size which is not applicable for the small motion. In NTSS, there are 16 points will be the checking point. The first of 8 points will use step size of 4 (same as TSS) meanwhile the other 8 will use the step size of 1. The point with the lowest cost function will be the search origin. If the lowest point is fall to the point with step size S = 4, we will follow the normal procedure as TSS. If the lowest cost is fall to point with step size 1, it will set as the origin and continue the similar search with the same step size 1. The location that given the lowest cost is the closest match and motion vector is set to that location.

D. Four Step Search (4SS)

Similar to NTSS, 4SS also employs centre biased searching and has a halfway stop provision. 4SS will set step size to 2 with 9 checking points. If the lowest weight falls to the origin, this will jump to step four. If the least weight is fall into other points, the point will be the search origin with step size of 2 for other check points. Again, if the lowest weight is fall into the centre, we will jump into fourth step. Else, we will continue similar setting as the second step. In the fourth step, the step size will be reduced to 1. The location with the least weight is the best matching and motion vector set to that location.

E. Diamond Search (DS)

DS algorithm is exactly same like 4SS, but the search pattern used in algorithm is diamond instead of square. There are no limited step in this algorithm can take. There are two different patterns, one is Large Diamond Search Pattern (LDSP) and the other one is Small Diamond Search Pattern. The first step is used LDSP and if the least weight is at the centre, this will jump to last step which using SDSP around the new search origin. If not, the similar search will continue using LDSP. As the search pattern is neither too small nor too big and the fact that there is no limit to the number of steps, this algorithm can find global minimum very accurately and effectively.

3.0 Problem Statement

Video is a medium to use for communications and useable in the most of multimedia application. Video files contained of photographic images that running in speeds so that it will appear as image of full motion to the eye of human. With this set of images, it may produce a very big size of files to realization the appearance of the motions.

Besides the storage, bandwidth is become a concern. Transmitting data over the channel bandwidth is become very challenging due to the limitation of channel bandwidth. They are not only need for huge storage of capacity but wide channel bandwidth during transmission.

With the rapid growth of technology, more and more multimedia application is disseminated through internet and mobile telephone networks. In order to transfer very effectively, they need to compress and decompressed in order to use. The quality of the decompressed output, the rate of compression and the time consumed on this process is become the major thing to support on the user demanding.

In order to get the best decompression output, the noise must be minimal and quality must be optimal. The compression rate should be higher to achieve on the lowest bandwidth possible. To consume the time effectively, the calculation complexity during the compression process is must be minimised with adhere good quality of output.

4.0 Objectives

The objectives of this project from technical purpose are:

1) To understand the motion estimation work and implementation using MATLAB software

2) To investigate matching criteria parameter available in ME methods.

3) To simulate the matching criteria parameter using MATLAB tool.

4) To prove that fast search algorithm is less computational with assuring optimal quality.

5) To compare between the 4SS, DS and Full Search method in term of computational complexity and average of PSNR.

5.0 Proposed Methodology

5.1 Flow Chart

Study the background and basic knowledge of ME and choose the algorithm/ topics

Narrow down to ME and the algorithm picked up. Preview on the previous work related

Extract Video Sequence using Matlab software

Implementing FFBMA and selected algorithms using Matlab source code developed

Develop Matlab code to test the matching criteria parameter

Analysis the matching criteria parameter obtained and compare with the selected algorithms

Writing thesis report

Project Completed

5.2 Expected Result

DS is expected to give the best block matching algorithm compare with 4SS while reducing its computation by up than 20%.Compare with other algorithm, it works better on average in terms of MSE values and PSNR and also reconstructed image quality. However these both fast search algorithms will give high reduction of computational complexity while assuring good quality.


6.0 Contribution to the Body of Knowledge

Unlike other fast search algorithm, the search window size used in DS is not restricted. The compact shape of the search patterns used in the DS algorithm increased the possibility of finding the global minimum point located inside the search pattern. Therefore, the DS tends to produce smaller or at least similar motion estimation error compared with other fast BMA's.

The fast search algorithm is reducing computational complexity by limited number of the search points. Compare with full search, all possible displacements within search range are compared. Therefore, intelligence and accurate block-based search technique is highly desirable to ensure much reduced processing delay while maintaining good reconstructed image quality.