Motion Estimation is an important step in video compression wherein block matching algorithms are used for computing Motion Vectors (MV). Diamond Search (DS) is one of the most efficient block matching motion estimation (BMME) algorithms. A revised diamond search algorithm, which modifies the two search patterns of DS, is proposed in this paper. The MDSS algorithm on comparison with the existing search algorithms is advantageous as it minimizes the number of search points used, while maintaining the video quality. Moreover it tries to accelerate the search process compared with the diamond search algorithm.
Keywords- Block matching; Motion estimation; Diamond search; Peak signal to noise ratio; Lossless video compression;
INTRODUCTION
The goal of lossless video compression [3, 13] is to represent a video signal with the smallest possible number of bits without loss of any information, thereby speeding up transmission and minimizing storage requirements. Lossless compression is possible because, in general, there is significant redundancy present in video signals. This redundancy is proportional to the amount of correlation within a frame. Also, for video, there is an additional temporal correlation [12] among samples in successive video frames. Lossless video compression is important to applications in which loss in video quality cannot be tolerated, such as archiving of a video, compression of medical and satellite videos, etc. Recently, there has been increasing interests in developing lossless video compression technique.
Motion Estimation (ME) [10] is one of the important steps in video compression, which exploits the temporal redundancy to enhance the compression performance. Improvement in ME could enhance the process of encoding. Motion Estimation is done by Block Matching Algorithms (BMA) for finding the best match between two nearby frames. Many algorithms have been proposed to improvise the encoding efficiency [1, 2] by means of different block searching algorithms. Block matching motion estimation (BMME) is more efficient for software and hardware implementation compared with pixel search method, hence it has been recommended by popular video coding standards such as MPEG-1, MPEG-2, and MPEG-4 [2] and so on. In block matching technique, frames are divided into blocks of varying sizes. For each block in the current frame, the ME algorithm searches for the Motion Vector (MV) with best match in one of the reference frames.
Exhaustive search (Full search) [4] takes into account all possible candidate blocks in the search window to obtain suitable MVs. But FS has high computational complexity and hence is not suitable for real-time applications. A number of block matching algorithms have been proposed to eliminate the drawbacks present in FS, like the three-step search (3SS)[11], the new three-step search (N3SS) [14], the four-step search (4SS) [15], the diamond search (DS) [7], the adaptive rood search [8] etc. Among these fast BMAs, the DS algorithm is often used because of its good performance. But in diamond search, more number of search points is taken into consideration. This will reduce the search speed. To overcome this, a new method is proposed. After block matching is done, encoding is performed using Context Adaptive Variable Length Coding (CAVLC) [1].
RELATED WORK
In 3SS, N3SS, and 4SS, rectangular shaped search patterns of variable sizes are used. If the center-biased global motion vector distribution is examined, greater than 80% of the blocks can be considered as stationary or quasi-stationary and most of the motion vectors are bound in the area of 5x5 for window size w=±7. Based on this fact, N3SS suggests the first step of 3SS to estimate eight extra neighboring candidates and applies early-stop mechanism to achieve significant speedup on sequences with stationary blocks. 4SS employs smaller square patterns to adapt to the center-biased MV distribution characteristics in real-world video sequences. The 3SS algorithm examines 33 points in order to locate the motion vector. Also it is efficient only for sequences with large motion and it gets trapped in local minima for sequences with small motion. The N3SS and 4SS
algorithms performs better than 3SS in terms of number of search points and mean square error . Moreover the half way stop technique used in these search algorithms will lose its precision in finding the global minimum. Also DS[7] uses diamond-shaped search patterns and emanates in fewer search points with analogous distortion performance as considered to N3SS and 4SS. DS performs block-matching just like 4SS, wherein it pivots the square-shaped pattern by 45° to structure a diamond-shaped search pattern and has its size unchanged before the new Minimum Block Distortion (MBD) reaches the diamond's center. The advantages of using DS include consideration of all possible directions for an investigating motion vector and fewer checking points in the final step.
The MBD of the matching blocks increases from global minimum distortion. To reduce the distortion entrapped by local minima, DS keeps unlimited number of steps contrary to step-size convergence during optimal point selection in the search pattern, which in turn increases the computational cost. In order to overcome this difficulty, this paper proposes a revised fast BMME algorithm by introducing a square shaped pattern in the next step, instead of small diamond search pattern, present in DS. Experimental simulation demonstrates that it results in fewer search points over fast BMME and maintains minimal distortion error reducing the computational cost.
Most of the BMME algorithms besides the DS are based on one assumption: the distortion function monotonically increases as the search point moves away from the global optimum point along any direction in each of the four quadrants. But it is not the truth in case of real-world video sequences. DS uses two search patterns to reduce the probability of the search being trapped into local optimum. They are large diamond search pattern (LDSP) and small diamond search pattern (SDSP). The diamond search algorithm is as follows:
Step 1: For the initial LDSP, its pivot is at the center (0, 0) of the search window, and the nine search points of LDSP are tested. If the minimum block distortion (MBD) point computed is present at the center, then go to Step 3; else, go to Step 2.
Step 2: The minimum block distortion point obtained in the previous step is re-positioned as the new center point to form another LDSP. Check whether the new MBD point found is situated at the center position, if true then go to Step 3; else, recursively repeat this step.
Step 3: The search pattern is switched from LDSP to SDSP. The final result of the motion vector is obtained by MBD point found in this step. This MV points to the best matching block.
Fig. 1 gives an example of the diamond search process which leads to the MV (-4,-2) in five search stages-four times of LDSP and last stage is SDSP. Totally there are 24 search points in the order- initially nine, then five, followed by three, three, and then four search points at each step, in order. It is not necessary to do so as object or camera movement is usually in horizontal or vertical direction. To improvise the search algorithm, the number of search points considered is minimized.
Fig. 1 Diamond Search path example
PROPOSED MDSS ALGORITHM
The MDSS algorithm avoids the facial points in the diamond search pattern. This is because , the results indicate that nearly 80% MVs are concentrated either in horizontal or in vertical direction, due to the objects' movement or camera's tracking, panning or tilting, etc. So, it can be concluded that most of the MVs are present in these two directions. On this basis, the points located at the faces of both the diamonds in DS are eliminated so that computation speed increases. Large Diamond search Pattern (LDSP) has been modified as Modified Large Search Pattern (MLSP) and the Small Diamond Search Pattern (SDSP) as Modified Small Search Pattern (MSSP) as shown in the figure. The revised algorithm assures the global optimum point being reached with minimum search points. Fig.2 (a) illustrates the MLSP while Fig.2 (b) depicts the MSSP. The proposed Modified Diamond-Square Search (MDSS) technique as follows:
LDSP ïƒ MLSP
(a) LDSP to MLSP
SDSPïƒ MSSP
(b) SDSP to MSSP
Fig. 2 Proposed MDSS Algorithm
Step 1: The initial MLSP is pivoted at the origin of the search window, but only the four vertexes and the origin point are calculated unlike LDSP. If the MBD point computed is found at the center position, then go to Step 3; else, go to Step 2.
Step 2: A new MLSP is formed with the MBD point of the previous step. In prior step, only five points other than nine points are tested. If the new MBD point found is located at the center, then go to Step 3; else, recursively repeat this step 2.
Step 3: Switch the search pattern from MLSP to MSSP. The resultant motion vector is obtained by MBD point found in this step. This MV points to the best matching block.
Fig. 3 MDSS Search path
Fig. 3 gives an example of the MDSS algorithmic process which leads to the MV(-4,-2) in five search stages-four times of MLSP and one time MSSP at the final step. There are 17 search points in total-taking five, three, three, two, and four search points present at each step.
SIMULATION RESULTS
The MDSS algorithm is used to test different test video sequences with highly inter-related frames. In order to test the performance, various search strategies have been proposed to classify the videos based on degree of motion present. Two important characteristics considered for analyzing the results are:
Average number of search points per block, in which it has a significant effect on motion estimation time.
Video quality will be evaluated by using the peak signal-to-noise ratio (PSNR).
The simulation is performed with four Quarter Common Intermediate Format ,QCIF,(176 x 144) video sequences which have low motion content as listed in Tab.2.This paper compares the MDSS algorithm against FS and DS, in search points and PSNR. Among the test sequences Crowd, Grandma, Container and News are used. The experimental results are shown in the Table I. The results given below show that the MDSS algorithm can reduce the search points to a large extent. At the same time it maintains the video quality. From the average search points, it can be inferred that the calculating speed of the MDSS algorithm is much faster than FS and DS.
TABLE I
COMPARISON AMONG FS, DS AND MDSS ALGORITHM
Video Sequences
Algorithms
Avg. no. of Search Points.
Avg. PSNR in dB
Foreman
FS
203.25
34.51
DS
20.17
34.09
MDSS
11.22
33.21
Grandma
FS
215.78
37.96
DS
18.91
37.51
MDSS
10.47
36.24
News
FS
200.45
36.58
DS
17.72
35.32
MDSS
16.62
34.82
Crowd
FS
195.25
30.12
DS
22.87
28.7
MDSS
14.97
28.48
Fig. 4 Average Search Points vs PSNR Comparison
The tabulated results are shown graphically in Fig. 4, wherein the MDSS algorithm is compared with Exhaustive search and Diamond search for standard video sequences like Foreman, Grandma, News and Crowd. Compared to the existing techniques the MDSS algorithm minimizes the number of search points used for finding the best match. The PSNR values are almost closer to that of DS.
CONCLUSION
In this paper a revised diamond search algorithm has been proposed. Experimental results show that the MDSS algorithm, on comparison with exhaustive and diamond search, outperforms them by reducing average search points (especially for low motion sequences). From the results obtained it can be found that there is 92% search point reduction when compared with Full Search (FS) and 30% search point reduction when compared with Diamond Search (DS). It is suitable for highly inter-related sequences as it maintains a suitable PSNR value. Future work includes enhancing the compression ratio based on the MDSS algorithm and improving the PSNR values by improving the search technique.
