"H.264 is one of the most important international standards for data compression coding.
Fast motion estimation algorithm has always been a research hotspot in video compression. Aiming at the situation that some fast estimation algorithms determine the search direction prematurely, easily fall into local minimum points and lose the search accuracy, this paper uses the combination of Diamond Cross Search Algorithm (DCS) and threshold estimation to improve the performance of motion estimation. Experimental results show that the algorithm can achieve the same effect as full search (FS) with less search cost, and is better than diamond method (DS) in search speed.
0 Introduction
H. 264 adopts a motion estimation algorithm to reduce the redundancy between frames of video image. Traditional motion estimation algorithms include full search (FS), three-step search (TSS), new three-step search (NTSS), four-step search (FSS), etc; Diamond search (DS) and asymmetric cross multi-level hexagonal lattice motion search algorithm (UMHexagonS) are commonly used. Motion estimation is the largest computation module in the whole video coding, which can account for more than 70% of the computation of the whole software encoder. Therefore, the complexity of encoder in video system depends on the complexity of motion estimation algorithm architecture.
1 Analysis of motion estimation algorithm
1.1 diamond search (DS) algorithm
DS algorithm, namely diamond search algorithm, is adopted by MPEG-4 international standard and included in the verification model VM (verification model). It is a fast motion estimation algorithm recommended by MPEG-4. DS algorithm adopts two kinds of search templates: a large template with 9 detection points and a small template with 5 detection points. During the search, the large template LDSP is used for matching calculation at the center and 8 points around the search area. When the smallest error occurs at the center point, the large template LDSP is replaced with SDSP, and then the matching calculation is carried out. At this time, the MBD (minimum block distortion) among the 5 points is the optimal matching point; Otherwise, change the center position and repeat the calculation with LDSP.
1.2 Diamond Cross Search (DCS) algorithm
The diamond cross search algorithm (DCS) algorithm is improved on the basis of DS algorithm. The matching template of DCS is based on two different search templates, namely large Diamond Cross (ldcsp) and Small Diamond Cross (sdcsp), as shown in Figure 1. Among them, the cross type can correspond to the vector distribution of the actual motion, while the cross type is to accelerate the search effect.
There are three possible situations when DCS algorithm performs motion estimation matching operation:
(1) If the MBD point is located at the center of the ldcsp, the image is still, and the DCS algorithm ends in one step;
(2) If the MBD point is located at the small cross of ldcsp, it indicates that the motion of the image is small. On this basis, the cross search is repeated according to the sdcsp template.
(3) If the MBD point is located at the large cross of ldcsp, it indicates that the image has a large motion, and on this basis, the cross search is repeated according to the ldcsp template.
It can be seen that the advantage of DCS algorithm is that it can select the corresponding search template in the next step according to the motion type of the image (such as the above three cases), so as to make the search related to the image content (content-based search), so as to obtain a better search effect; The search of DCS algorithm does not necessarily go through the inevitable process of template from large to small. Sometimes the search can be completed in one step; When searching with DCS, the cross template corresponds to the actual motion vector distribution, and the cross template has the characteristic of accurate "focusing", which essentially reflects that DCs is an effective combination of coarse positioning and accurate positioning.
2 threshold determination of motion estimation
Most of the motion vectors of video images are zero vectors or very small motion vectors. A block with zero motion vector is called a stationary block; The block with small motion vector (in the circle with the center of the search window as the center and two pixels as the radius) is called quasi-static stop block, while others are called motion blocks. If more than 80% of the motion vector is small, it can be regarded as static or quasi-static stop. Therefore, a threshold value t can be set. When the value of motion vector is less than t, sdcsp search method can be used for accurate positioning directly to find the best advantage; When the value of motion vector is greater than t, ldcsp search algorithm can be used to find the best advantage.
The prediction methods of motion vector space domain include motion vector median prediction and upper block mode motion vector in space domain; The prediction methods in the time domain include the motion vector prediction of the corresponding block of the previous frame and the motion vector prediction of the adjacent reference frame in the time domain. In this paper, the motion vector median prediction method is used. According to the motion vectors of the left block a, the upper block B and the upper right block C adjacent to the current block e, the median value is taken as the predicted motion vector of the current block. As shown in Figure 2.
Set the motion vector of the current block e to be encoded as MVP. If the value of motion vector MVP ≥ T, the motion correlation between blocks adjacent to block e is high, indicating that the change in this region is relatively gentle; If the value of motion vector MVP < T, the correlation of motion between blocks adjacent to block e is low, indicating that the region changes violently. According to the detection of missa, grandmother, Carphone and salesman, the threshold T = 2.
3 adaptive motion estimation algorithm
Combined with the above DCS algorithm and the determination of threshold, we can first judge the threshold of the moving block of the video image, and then search the best matching block according to the judgment result. The specific search steps are described as follows:
Step 1: judge the current block motion vector MVP and threshold value. If MVP ≥ T, enter step 2; If MVP < T, enter step 5.
Step 2: use ldcsp to perform matching operation at 8 points in and around the center of the search area, and then judge to find out MBD points. If the MBD point is located at the center point, it indicates that the macroblock is static, and the DCS algorithm ends in one step to obtain the optimal matching block; Otherwise, proceed to step 3.
Step 3: if the MBD point is at the small cross of the ldcsp template, take this point as the center to build the sdcsp for matching calculation. If the MBD point is at the center, the obtained MBD point is the required value. Otherwise, go to step 4.
Step 4: if the MBD point is at the big cross of the ldcsp template, take this point as the center to build LCSP for matching calculation, and enter step 2.
Step 5: use ldcsp to perform matching operation at 5 points in and around the center of the search area, and then judge to find out MBD points. If the MBD point is located at the center point, the obtained MBD point is the calculated value; Otherwise, continue with step 5.
The algorithm flow chart is shown in Figure 3
4 experimental results and description
The search time and PSNR value are used to verify the performance of DCS. All video files used in this experiment are in QCIF (Quartet coordinated format) format. The experiment takes Visual C + + 6.0 running on PC with main frequency of 1.8GHz as the platform. The test objects are missa, salesman, news, grandmother, foreman, Carphone and claim, and the search scope is 16 × 16, the quantization range is 2 ~ 12, and the size of each frame image in the test sequence is 176 × 144。
4.1 comparison of search time
In order to test the accuracy of time test, two accurate time functions provided by VC + + are used: queryPerformance frequency() and ouerperformancecounter(). The accuracy of standard test sequences missa, salesman, news, grandmother, foreman and Carphone are accurately measured, and table 1 is obtained (the data are the average values obtained from three measurements).
It can be seen from table 1 that: A. FS has the best search effect, but it takes too long; DS algorithm is greatly improved and can realize real-time compression; Compared with DS, the running time of DCS is reduced to varying degrees, so DCS algorithm has advantages in search speed. b. From a single sequence, DCS algorithm is the most significant for missa and salesman time optimization, accounting for only 7.42% and 7.50% of FS algorithm and 98.17% and 97.49% of DS algorithm respectively; The search speed of Carphone sequence is also greatly optimized, accounting for 7.97% of FS search algorithm and 97.82% of DS algorithm. It can be seen from the comprehensive video characteristics that the DCS algorithm optimizes the search speed obviously for video objects with gentle motion.
4.2 comparison of signal-to-noise ratio
Determine the standard test sequence claim and Carphone sequence, and calculate the PSNR in Table 2.
The average PSNR of FS in Table 2 is the highest, reaching 42.38, but the search time is the longest; The PSNR of DS is the lowest, 42.31, while that of DCS is 42.35, which is higher than that of DS algorithm and only 0.03db lower than that of FS algorithm. From a single sequence, the DCS algorithm optimizes claim the most, exceeding the PSNR value of FS, indicating that the DCS algorithm is only applicable to the video with facial expression and motion characteristics. The PSNR value of Carphone calculated by DCs algorithm is lower than FS algorithm, but higher than DS algorithm; The PSNR value of DCS algorithm of missa sequence is almost the same as that of FS and DS method. Therefore, DCS algorithm is guaranteed in search speed and image quality.
5 Conclusion
This paper analyzes and compares the performance of various block matching motion estimation algorithms in terms of search time and image quality. The experimental results show that the combination of Diamond Cross Search Algorithm and threshold judgment can optimize the search speed to a great extent, and can obtain the image quality equivalent to FS and DS search algorithms. DCS algorithm has obvious effect on video with gentle motion, so it is inferred that this algorithm is suitable for real-time video compression such as TV, telephone, distance education and so on.
Technology Zone
Solution of liquid level measurement using capacitive sensing technology
Industry 4.0 will re drive the western manufacturing industry or reverse the trend of globalization
Cable fault detection method
Make water level gauge with LM339
Design principle analysis and advantages of temperature measurement circuit based on EWB
Statement: the content and drawings of this article are written by the settled author or reprinted by the settled cooperative website. The views of the article only represent the author himself, not the position of e-enthusiast.com. The article and its drawings are only for engineers to learn. If there is any content, picture infringement or other problems, please contact this site for infringement and deletion. Infringement complaints, pay attention to wechat, an electronic enthusiast
Interesting and informative information and technology dry goods
Download enthusiast app
Create an electronic circle of your contacts
Focus on enthusiast class
Lock in the live broadcast of the latest course activities and technologies and collect them
0 collections
Share:, comment
Lin Chaowen PCB Design: pads tutorial, pads video tutorial, Zheng Zhenyu teacher: Altium designer tutorial, Altium designer video tutorial, Zhang Fei actual combat electronic video tutorial, Zhu Youpeng teacher: Hisilicon hi3518e tutorial, hi3518e video tutorial, Li Zeng teacher: signal integrity tutorial, high-speed circuit simulation tutorial, Huawei Hongmeng system tutorial, harmonyos video tutorial, saisheng: EMC design tutorial, EMC video tutorial Mr. Du Yang: STM32 tutorial, STM32 video tutorial, Tang zuolin: basic C language tutorial, basic C language video tutorial, Zhang Fei: Buck Power tutorial, buck power video tutorial, punctual atom: FPGA tutorial, FPGA video tutorial, Mr. Wei Dongshan: embedded tutorial, Embedded video tutorial Zhang Xianfeng: C language basic video tutorial Xu Xiaogang: Modbus communication video tutorial Wang Zhentao: NB IOT development video tutorial mill: FPGA tutorial, zynq video tutorial c language video tutorial linux driver development video tutorial Zhu Youpeng: u-boot source code analysis video tutorial harmonyos, published, relevant recommendations
DSP implementation and optimization of H.264 video codec
Digital video compression coding technology is the key technology to solve this problem. H. 264 with its good network adaptability and high coding and compression efficiency, flexible
Published on September 20, 2011 16:16
•
491 readings“
Our other product:
