Article Preview
TopIntroduction
Video is the most important medium of communication and entertainment in the present era. Video technology has witnessed a huge transformation in the last decade. The inclusion of high-resolution movie sequences, machine-generated synthetic video series, 360-degree video sequences, and other advanced video formats fundamentally transformed the video encoding and decoding process. The joint video experts team adopted the versatile video coding (VVC) standard in 2020 for such diverse video characteristics (Bross et al., 2021). VVC relied on motion estimation and motion compensation for interframe coding. As a brute force search, the full search algorithm provides the best result for motion estimation at a very slow speed (Acharjee, 2012). The geometrical pattern-based searches, such as the three-step search (Barjatya, 2004), the four-step search (Po & Ma, 1996), the diamond search (Zhu & Ma, 2000), and many more such algorithms, limit the number of search points and increase the speed of motion estimation. A few other approaches use the search point elimination technique to improve the pace of the process (Liu & Salari, 1995).
Hosur (Hosur, 2003) applied predictors to find the initial search point in the motion vector field adaptive search technique (MVFAST). The algorithm used the position of the present block and its neighboring blocks as an input to the predictor. Inclusion of the predictors reduced the calculation time in the motion approximation process. Tourapis et al. replaced the other predictors with the median predictor in the predictive motion vector field adaptive search technique (Tourapis et al., 2000). Tourapis further offered a few changes to the zonal search method, which included improved prediction and thresholding measures (Tourapis, 2002). These changes increased the speed of the motion approximation process considerably compared to the fixed pattern-based motion estimation.
In the high efficiency video coding standard, the zonal search-based test zone motion estimation algorithm has been accepted as a benchmark algorithm (Sullivan et al., 2012). Test zone search is a multi-staged procedure which includes both the zonal search as well as the raster search (Figure 1). In zonal search, a square or diamond pattern search is performed around the initial search point. The adaptive motion vector predictor (AMVP) is used to select the initial search point (Liu et al., 2006). The dimension of the diamond or square pattern will vary from one to the size of the search window. The search window is defined in the reference frame at a certain distance around all directions from the initial search point. The next phases in the test zone search are controlled by fraster, which is the sub-sampling frequency of the search region during raster search. Following the zonal search, the test zone search follows one of the processes listed below.
First, if the best match is within one pixel of the current search center, a two-step search is performed to explore for even better results among nearby unexplored solutions.
Second, the search center moves to the position of the best match when the distance between the present best match and the search center is greater than one but smaller than the fraster. A diamond or square patterned grid search is performed again with fraster as the size of the search window. The search window is centered around the new search center.
Third, when the best match is identified at a distance larger than fraster, the raster search of the entire search window is done with a sub-sampling frequency of fraster. A refinement search was performed, centering around the position with the lowest distortion between the reference coding unit and the current coding unit during raster search.