Development of Fast Motion Estimation Algorithm With High Accuracy
Abhijeet Bairagi, Saket Newaskar, Raj Shah
Electronics and Telecommunication Department
Maharashtra Institute of TechnologyPuneUniversity
Address: Saket Newaskar, A/19, Shri Sai Enclave,
Tejasnagar, Kothrud, Pune 411038, India.
Abstract:
Motion estimation (ME) is one of the most time-consuming parts of video encoding system, and significantly affects the quality of reconstructed image sequences.
It is a commonly accepted theory that an algorithm for ME which has more computational complexity (low speed) results in more accurate results. Thus such an algorithm can be used only on need basis if it is to be implemented in a fast environment. Algorithms which have less computational complexity can be used in situations where they provide required accuracy.
In this paper, we propose an algorithm which decides dynamically which algorithm of ME should be used maintaining a balance between speed and accuracy.
The resulting algorithm will thus be a combination of different ME algorithms with
varying computational complexity.
1. Introduction
In video coding, ME is used to reduce temporal redundancy between inter frames. However, motion estimation generally requires huge computational complexity. Block matching algorithms are widely used in ME due to there low computational complexity. In block matching algorithms, the current image frame to be encoded is divided into non-overlapped blocks and the best matching
block of each current block is found within the previous frame. The best
matching block is usually examined within a limited search area.In the full search block matching algorithm, all possible points (or corresponding blocks) within a search area in the previous frame, are checked to find a block mostclosely matched to the current one. Here, SAD (sum of absolute differences)is popularly used as a matching criterion.
N-1 N-1
SAD (u,v)= ∑ ∑ | It (i,j)-It-1( i+u,j+v)|
j=0 i=0
where It (i,j) and It-1(i+u,j+v) denote luminance pixel values in the current and previous frames, and (u,v) refers to a displacement or a candidate motion vector(MV). Also, N denotes the size of block. In order to determine MV of each block, SAD value of MV within a search area are examined and the MV which has minimum SAD value is set to the final one.If the best matching block of the current block is found in the previous frame, the current frame is reconstructed by using this best matching block. Hence, in order to obtain better coding performance, this motion compensated block should be similar to the original one, or the motion compensation error should have small energy. However, since the true displacement between the previous frame and the current frame is not always a multiple of pixel interval, it is known that sub-pixel ME can reduce the motion compensation error.
We will briefly review basic algorithms of ME in section 2, which are used in combination in the proposed algorithm which is described in section 3.The simulation results are given in section 4. Finally, conclusions are presented in section 5 with references.
2.Review of algorithms
The following algorithms are briefly explained in this section:
1) Three step search
2) Four step search
3) Diamond search
4) Full search
1) Three step search (3ss):
Figure 1
Figure 1 above explains the three step search algorithm [3].
The best match for central block with label 1 in current frame is to be found in the previous frame. Firstly, 9 blocks(green color) in the previous frame (central block and surrounding 8) are considered .The central block in the previous frame has the same position vectors as that of the block under consideration in the current frame. The block with minimum SAD in the previous is then taken to be the new central block. The search window is halved and similar procedure is carried to find the third central block. The search window is further halved and the final best match. The MV is calculated by subtracting the position vectors of the block under consideration and the final best matching block.
2) Four step search [2]: This method is similar to three step search .The only difference is that the search widow size is halved only if the best match is found at the central block.
3) Diamond search: Figure 2 explains Diamond search algorithm.[1]
Figure 2
This algorithm is similar to four step search. The difference is that the search window is not rectangular but diamond shape.
4) Full search: In this search method block under consideration is compared with all the blocks in previous frame to find the best match.
We implemented the above four algorithms in C language for ITU-T standard H.261 Encoder [4]. The simulation results are included in section 4.
3. Proposed Algorithm
The algorithms mentioned in section 2 were tested on CIF (Common Intermediate Format) image sequences with a resolution of 352*288. A CIF image can be divided into 396 blocks of (16*16). Full search requires 396 comparisons for each block (16*16). Thus for an entire image total comparisons amount to 156816 (396*396). Three step search requires 27 comparisons for each block. Thus for an entire image total comparisons amounts to 10692. The Full search is the slowest but the most accurate algorithm mentioned in section 2. Three step search is the fastest of the four but it is highly prone to errors.
In the proposed algorithm we use Full search and Three step search in combination.The image can be down sampledup to a factor of 4.
The number of blocks in the image is constant (i.e 396).Thus the block size reduces to 8*8 instead of 16*16.So number of subtractions required for calculating SAD is reduced to 64 instead of 256. Three step search is used for Motion Detection and finding MV which are in the range of (-8 to +8). Full search is used for MV greater than | 8 |. The resulting algorithm uses, for one frame, Three step search for more than 70% of the blocks. The remaining blocks are estimated using Full search. The results obtained by this algorithm are as good as Full search. The following block diagram illustrates the proposed algorithm.
Four step search or Diamond search could also be used instead of Three step search. These two motion estimation algorithms can be used to find MVs up to |16|. However they require 27 to 35 comparisons per block as compared to 27 comparisons of Three step search.
4. Simulation Results
For experiment, we adopted 3 video sequences of CIF (352*288) format Akiyo, Forman, Mother and daughter. The results obtained by applying various algorithms and the proposed algorithm are shown below. The corresponding values of PSNR and MSE are mentioned in the result table. The simulation was carried out using H.261 Video codec ref C-code.
Simulation Result Table (for Akiyo frame no.297 with Motion Compensation):
Name Of Algorithm / PSNR / MSE / ENTROPYFull Search / 37.72 / 10.99 / 7.13
Four Step / 37.01 / 12.96 / 7.13
Three Step / 37.11 / 12.66 / 7.13
Diamond Search / 37.05 / 12.83 / 7.13
Proposed Algo. / 37.06 / 12.81 / 7.13
Inference of simulation results:
The proposed algorithm gives us the same perceptual result as that of full search with much faster speed and with a very slight degradation in PSNR. The proposed algorithm is certainly a very fast alternative for motion estimation with quality as goodas full search (i.e. best possible quality) .The proposed algorithm’s speed varies according to the motion in image sequence. Larger the motion slower is the speed. Therefore algorithm will find its application in fields such as video conferencing where motion between two frames is relatively small.
Input to H.261 Encoder
Output using Three Step Search
Output using Four Step Search
Output using Diamond Search
Output using Full Search
Output using Proposed Algorithm
Graphical results of number of times the
Full search have been used by the proposed algorithm for every frame of
different test files.
X-axis: frame number
Y-axis: number of times full search is
used
Graph of Akiyo
Graph of mother and daughter
Graph of Foreman
5. Conclusion
It is seen from above graphs that the proposed algorithm uses full search method of ME for less number of times. The proposed algorithm is best for files like Akiyo where movement isless Thus the algorithm can be used suitably for applications like video conferencing.
References:
[1]“A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”, IEEE Trans. Image Processing, S. Zhu and K. K. Ma, Feb. 2000
[2]“A Novel Four-Step Search Algorithm for Fast Block Motion Estimation”, IEEE Trans. Circuits System, Video Technology, L. M. Po and W. C. Ma, June 1996
[3]“A New Three-Step Search Algorithm for Block Motion Estimation”, IEEE Trans. Circuits System, Video Technology, R. Li, B. Zeng, and M.L. Liou, Aug. 1994
[4]Reference code developed for H.261 standardby Portable Video Research Group (PRVG), StanfordUniversity.