This paper deals with the motion estimation algorithms for the video sequences analysis in hybrid compression standards H.264/AVC and H.265/HEVC. Based on the analysis of the advantages and disadvantages of existing algorithms has been offered a new algorithm, which is called Fast Multigrid Pattern Search (FMPS). This new algorithm includes the Fast Interger-Pel Search FIPS, Adaptive Rood Pattern Search ARPS and hierarchical search MP (Hierarchical search or Mean pyramid). All motion estimation algorithms have been implemented using MICROSOFT VISUAL STUDIO and tested with several video sequences. The criteria for evaluating the algorithms were: speed, peak signal to noise ratio and RD-curves. The proposed method showed a much better performance at a comparable error and deviation (about 4 times faster). The average loss of the RD curve value (PSNR versus bitrate) is up to 3.75% in all. Application of this algorithm in hybrid codecs (H.264/AVC and H.265/HEVC) instead of the standard can significantly reduce compression time. This feature enables to recommend it in telecommunication systems for multimedia data storing, transmission and processing.
Interframe predictive coding is used to eliminate the large amount of temporal
and spatial redundancy that exists in video sequences and helps in compressing
them. In conventional predictive coding the difference between the current frame
and the predicted frame (based on the previous frame) is coded and
transmitted. The better the prediction, the smaller the error and therefore lowered the
transmission bit rate. If a scene is still, then a good prediction for a particular
pixel in the current frame is the same pixel in the previous frame and the error
is zero. However, when there is motion in a sequence, then a pixel on the same
part of the moving object is a better prediction for the current pixel [
There are many motion estimation algorithms for interframe prediction
coding. This work is oriented on algorithms that are called "block matching
algorithms" [
Motion estimation has a fairly large amount of computation and can consume up to 80% of the processing power of the encoder, when a full search (FS) is used. It evaluates all possible candidate blocks within the search window. Outgoing of this disadvantage, looking for other effective algorithms is started.
The Unsymmetrical-cross Multihexagon-grid Search (UMHexagonS) or FIPS
was proposed for the fast integer pel motion estimation in H. 264/AVC [
To overcome the disadvantages of existing algorithms, we propose the following algorithm called “Fast Multigrid Pattern Search”, which includes the FIPS algorithm for integer pel estimation, ARPS algorithm for fractional pel estimation and Hierarchical Search MP. The whole motion estimation process of FMPS is exemplified in the flowchart in fig. 1:
Component algorithms are discussed in the following sections. 3
FIPS is a hybrid method because it includes four steps with different kinds
of search pattern [
For each step mentioned above, the best search point (which means a point
with minimum cost so far) generated by the previous step is used as a search
center for the current search step. Initial search point prediction is an important
technique introduced by many fast motion estimation algorithms [
As fig. 3 shows, median predictor is used in median prediction of MV, the median value of the adjacent blocks on the left, up, and up-right (or up-left) of the current block is used to predict the motion vector of the current block:
M Vpredict = median(M Vleft; M Vup; M Vup right): Therefore we can predict the SAD (Sum of Absolute Differences) by: SADpredict = min(SADXpredict; SADY predict): (1) (2) 3.2
As fig. 4 shows, there are seven inter prediction block modes defined in H.264. 8x8 modes (mode 4, 5, 6, 7) are first searched followed by 16x16 modes (mode 3, 2, 1). Such a strategy is not beneficial in utilizing the motion relationship between different modes, therefore the search order of the modes here is changed according to the size of the block mode, a hierarchically search order from mode 1 to 7 is chosen as our mode search order and the motion vector of the up layer block (for example, mode 5 or 6 is the up layer of mode 7, and mode 4 is the up layer of mode 5 or 6, etc.) is used as one of the prediction candidates of lower layer, just as fig. 5 demonstrates.
M Vpredict = median(M VUpLayer): Therefore we can predict the SAD by: (3)
Multi-reference frames motion compensation is adopted in JVT to increase prediction accuracy and coding efficiency. For the same current block, motion vectors in different reference frames exhibit a strong correlation in our experiment. Therefore current block’s motion vector in reference frame tp can be predicted by scaling of current block’s motion vector in reference frame tp+1, as fig. 6 shows:
Therefore we can predict the SAD by:
M Vpredict = M Vneigh tc tc
tp tp 1
:
SADpredict = SADneigh: 3.4
For natural video sequence, the motion track of a moving object is continuous except scene change occur, therefore there is strong correlation of motion vector in the temporal domain, and then we utilize this property to give an accurate starting search position. In this prediction mode, the motion vector of the corresponding block in the last frame is used as one motion vector candidate, as fig. 7 shows: (4) (5) (6) Therefore we can predict the SAD by:
SADpredict = SADcorres:
The prediction with the minimum cost among these prediciencies will be chosen as the initial search position of next search step. (7) (8)
The algorithm uses the fact that the total motion of the frame is usually coherent, i.e. if the blocks around the current block moving in a certain direction then there is a high probability that the current block will also have a similar motion vector. This algorithm uses the motion vector of the block to its immediate left to predict its own motion vector [10]. The algorithm summarized as follows (fig. 8): – Step 1: Find the predicted motion vector of the block. Set step size as max (|x|, |y|), where (x, y) – coordinates of predicted motion vector. Find points (around the center) are located at a distance of step size from the center. Find the point with the minimum distortion, which then to be the new center. – Step 2: Perform a search on SDSP around the new center. Repeat SDSP search until point with the minimum distortion is at the center of SDSP. 5
MP algorithm is described as: At the beginning, to eliminate the effect of noise low-resolution image is obtained by low-pass filter [11, 12]. The scheme of the MP algorithm is shown in fig. 9.
The proposed algorithm was implemented using Microsoft Visual Studio and tested with several video sequences1.
In the experiment, we will compare the proposed algorithm with the
algorithm FS, FIPS with ARPS[
The coding time is estimated by comparing the average coding time for encoding each video sequence (shown in Table 1). It can be seen that the proposed algorithm reduces the coding time by about 4 times in comparison with the other algorithms.
The quality of the video sequence is estimated by comparing the average PSNR video exponent (Table 2) and the RD curve values (Fig. 10). The results of the research show that the proposed algorithm loses not more than 0.87 to 3.75% of the PSNR ratio in comparison with other algorithms.
In Fig. 10 shows the curves of the dependence of the distortion rate RD of the proposed algorithm and others for the difference video sequences with QP (quantization parameter) equal to 37, 32, 27, 22, vertical axes are PSNR (dB), horizontal axes correspond to bitrate (kbps), and each point on the curves represents the parameter QP. From Fig. 10 that the RD-curves for the considered algorithms (FS, FIPS with ARPS, EPZS and proposed algorithms) are close for each sub-step. This can explain the fact that the proposed change has little impact on both PSNR and bitrate. 1 Test video sequences ftp://ftp.tnt.uni-hannover.de/pub/svc/testsequences/.
A new algorithm for interframe encoding of the hybrid codecs is proposed, which includes well-known algorithms FIPS, ARPS and MP. The algorithm was tested with several video sequences. Experimental results showed that the proposed algorithm works faster 4 times, while the PSNR coefficient is only 0.863.75% below the other algoritms. 10. Nguyen, V. T., Tropchenko, A. A. Hierarchical adaptive rood pattern search for motion estimation at video sequence analysis // Scientific and Technical Journal of Information Technologies, Mechanics and Optics. 2016. Vol. 16, No. 3. P. 474–481. 11. Nguyen, V. T., Tropchenko, A. A. Methods And Algorithms For Reducing Temporal Redundancy Of Video Data / Sbornik statyei II-oy Mezdunarodnoy nauchnoprakticheskoy konferensyy “Aktualnye problem nauky XXI veka”. 2015. Vol. 2. P. 3641. — Moscow: Cognitio, 2015. 12. Tropchenko, A. A., Tropchenko, A. U., Nguyen, V.T. Research of Block-Based Motion Estimation Methods for Video Compression // TEM Jornal - 2016. Vol. 5, No. 3, P. 187-194.