Abstract: One of the most efficient block matching motion estimation (BMME) algorithms is Diamond Search. In our paper, we propose a revised diamond search algorithm, which modifies the two search patterns of DS. The proposed 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 the proposed algorithm tries to accelerate the search process compared with the diamond search algorithm.
Keywords: block matching; H.264; motion estimation; 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 [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 with best match in one of the reference frames. The Euclidean distance between the two blocks is called motion vector (MV).
Exhaustive search (Full search)[4] takes into account all possible candidate blocks in the search window to obtain suitable MVs. But FS has high computation 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, such as the three-step search (3SS)[11], the new three-step search[14], the four-step search(4SS), the diamond search(DS)[7], the adaptive rood search[8] etc. Among these fast BMAs, the diamond search (DS) algorithm is often used because of its good performance. But in diamond search, more number of search points are 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 CAVLC [1].
Related Work
In 3SS, N3SS, and 4SS, rectangular shaped search patterns of different sizes are employed. As the center-biased global motion vector distribution is considered, more than 80% of the blocks can be regarded as stationary or quasi-stationary and most of the motion vectors are enclosed in the area of 5x5 for window size w=±7. Based on this fact, N3SS proposes the first step of 3SS to evaluate eight extra neighboring candidates and employs early-stop mechanism to achieve significant speedup on sequences with stationary blocks, while 4SS uses smaller square patterns to fit the center-biased motion-vector distribution characteristics of real-world video sequences. Also DS[7] uses diamond-shaped search patterns and results in fewer search points with similar distortion performance as compared to N3SS and 4SS. DS performs block-matching just like 4SS, wherein it rotates the square-shaped search pattern by 45° to form a diamond-shaped one and has its size unchanged before the new BDM 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 BDM of the matching blocks increase away from global minimum distortion. To minimize the distortion trapped by local minima, DS keeps unrestricted number of steps instead of step-size convergence during optimal point of the search pattern. In this paper we propose a revised fast BMME algorithm by introducing a square shaped pattern in the next step, instead of small diamond search pattern, to the DS algorithm. Experimental simulations show that it can achieve fewer search points over fast BMME and maintain smaller distortion error. The rest of the paper is organized as follows. Section II analyzes the diamond search algorithm. The proposed algorithm will be described in Section III. Section IV reports the experimental results on our revised algorithm and conclusions are given in Section V.
Section II Diamond Search
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 patter (SDSP). The diamond search algorithm is as follows:
Step 1: The initial LDSP is centered at the origin of the search window, and the nine checking points of LDSP are tested. If the minimum block distortion (MBD) point calculated is located at the center position, go to Step 3; otherwise, go to Step 2.
Step 2: The MBD point found in the previous search step is re-positioned as the center point to form a new LDSP. If the new MBD point obtained is located at the center position, go to Step 3; otherwise, recursively repeat this step.
Step 3: Switch the search pattern from LDSP to SDSP. The MBD point found in this step is the final solution of the motion vector which points to the best matching block.
Figure 1 gives an example of the diamond search process which leads to the MV(-4,-2) in five search steps-four times of LDSP and one time SDSP at the final step. There are 24 search points in total-taking nine, five, three, three, and four search points at each step, sequentially. It is not necessary to do so as object or camera movement is usually in horizontal or vertical direction. To improvise the search algorithm, we minimize the number of search points considered in order to achieve more efficiency.
Fig.1 Diamond Search path example
Section III Proposed Algorithm
It is observed that nearly 80% MVs are concentrated either in horizontal or in vertical direction. This is because of objects' move 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, we could eliminate the points located at the faces of both the diamonds in DS so that computation speed increases. Large Diamond search Pattern (LDSP) has been modified as Revised Large Search Pattern(RLSP) and the Small Diamond Search Pattern(SDSP) as Revised Small Search Pattern(RSSP) as shown in the figure. The revised algorithm assures the global optimum point being reached with minimum search points. Fig.2 (a) illustrates the RLSP while Fig.2 (b) depicts the RSSP. So far, the algorithm is illustrated as follows:
LDSP ïƒ RLSP
Fig.2 (a) LDSP to RLSP
SDSPïƒ RSSP
Fig.2 (b) SDSP to RSSP
Improvement of the two search patterns
Step 1: The initial RLSP is still centered at the origin of the search window, but only the four vertexes and the origin point are calculated compared with LDSP. If the MBD point calculated is located at the center position, go to Step 3; otherwise, go to Step 2.
Step 2: The MBD point found in the previous search step is repositioned as the center point to form a new RLSP. As the prior step, only five points other than nine points are tested. If the new MBD point obtained is located at the center position, go to Step 3; otherwise, recursively repeat this step 2.
Step 3: Switch the search pattern from RLSP to RSSP. The MBD point found in this step is the final solution of the motion vector which points to the best matching block.
Fig.3 Revised Diamond Search path
Figure 3 gives an example of the proposed algorithm process which leads to the MV(-4,-2) in five search steps-four times of RLSP and one time RSSP at the final step. There are 17 search points in total-taking five, three, three, two, and four search points at each step, sequentially.
Section IV Results
The proposed algorithm is used to test different test sequences with highly inter-related sequences. In order to test the performance the search strategies proposed in [9]. The block size will vary depending on the motion present in the sequence. 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 power signal-to-noise ratio (PSNR).
PSNR=10 log 10 [(peak to peak value of original data)]
MSE
The simulation is performed with four QCIF (176 x 144) video sequences which are have low motion content as listed in Tab.2.This paper compares the proposed search 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 Tab. 1. The results given below show that the proposed search algorithm can reduce the search points to a large extent. At the same time it maintains the video quality. From the average search points, we can find that the calculating speed of the proposed algorithm is much faster than FS and DS.
Table 1. Comparison among FS, DS and proposed algorithm
Video Sequences
Algorithms
Avg. no. of Search Points.
Avg. PSNR
Foreman
FS
203.25
34.51
DS
20.17
34.09
Proposed
11.22
33.21
Grandma
FS
215.78
37.96
DS
18.91
37.51
Proposed
10.47
36.24
News
FS
200.45
36.58
DS
17.72
35.32
Proposed
16.62
34.82
Crowd
FS
195.25
30.12
DS
22.87
29.77
Proposed
14.97
29.10
Fig.4 Average Search Points
Fig. 5 PSNR Comparison
The tabulated results are shown in graphically using the following figures 4 and 5, wherein the proposed work is compared with Exhaustive search and Diamond search. Compared to the existing techniques the proposed work minimizes the number of search points used for finding the best match.
Section V Conclusion
In this paper a revised diamond search algorithm has been proposed. Experimental results show that the proposed algorithm, on comparison with exhaustive and diamond search, outperforms them by having better average search points( especially for low motion sequences). It is suitable for highly inter-related sequences as it maintains a suitable PSNR value.
