CN100377599C - A Fast Subpixel Motion Estimation Method - Google Patents

Abstract

The invention relates to a fast sub-pixel motion estimation method, which belongs to the field of image processing. The present invention directly calculates the optimal sub-pixel position on the basis of integer-pixel motion estimation, thereby reducing the number of search points for sub-pixel motion estimation to less than 2, avoiding the point-by-point search and comparison of traditional methods, and not only greatly Search speed is improved, and the storage overhead required to interpolate sub-pixel points approaches zero. Experimental results show that this method achieves the same effect as full search with a very small search cost.

Description

A Fast Subpixel Motion Estimation Method

technical field

The invention relates to a method for increasing the speed of sub-pixel motion estimation and reducing storage overhead in the process of sub-pixel motion estimation, belonging to the technical field of image processing.

Background technique

In the past 10 years, coding schemes based on discrete cosine transform and motion compensation have been widely used in video compression and incorporated into a series of international standards, such as H.263, MPEG-4 and JVT. In this scheme, motion estimation is an effective method to eliminate redundancy between video frames, but because it uses block-by-block search and comparison between frames, the computational complexity is huge, and it becomes a key technical obstacle affecting video compression performance. Motion estimation consists of two parts: integer pixel motion estimation and subpixel motion estimation. Integer-pixel motion estimation directly uses the coded frame as the reference frame to search for the optimal matching block at the integer-pixel level; sub-pixel motion estimation uses interpolation to estimate the value of non-direct sampling points (sub-pixel points) in the reference frame as a reference , on the basis of integer pixel motion estimation to further search for the optimal matching block at the sub-pixel level. Experiments show that sub-pixel motion estimation based on integer-pixel motion estimation can significantly improve the effect of motion compensation, so sub-pixel motion estimation has become an effective method to improve image compression ratio.

The sub-pixel motion estimation commonly used in current video compression standards is a full search method, that is, the entire image is interpolated first, and on this basis, eight 1/2 pixel points around the optimal point of integer pixel motion estimation are searched to obtain 1 The optimal point of /2 pixel level, and so on, each level of sub-pixel search will search the 8 next-level sub-pixel points around it centered on the optimal point of the previous level of search. For K-level (or 1/2 ^K ) sub-pixel motion estimation, each current block needs to search 8×K blocks, and the image after interpolation is increased to ^22K times of the input image, and the encoding process needs Increase the interpolation storage space by 2 ^2K -1 times. This full search method not only has extremely high computational complexity, but also increases the interpolation storage cost exponentially with the increase of sub-pixel precision.

In order to solve the problems existing in the sub-pixel full search method, many fast algorithms have been produced. These current methods generally narrow the search scope from the aspects of search strategy and termination conditions to reduce the number of search points. Generally speaking, there is still a large gap between its search accuracy and full search, and the search speed needs to be further improved; in addition, a large amount of interpolation storage overhead is also a difficult problem to solve. In practical applications, especially for applications with limited storage resources, a good sub-pixel motion estimation method must simultaneously consider search accuracy, operating efficiency and storage overhead.

Contents of the invention

The purpose of the present invention is to provide a fast sub-pixel motion estimation method. This method directly derives the optimal sub-pixel position under arbitrary precision according to the adjacent integer pixel values, thus avoiding the storage overhead brought by the traditional point-by-point search and comparison method.

For realizing above-mentioned purpose of the invention, the present invention adopts following technical scheme:

A fast sub-pixel motion estimation method, including obtaining the optimal matching block of the integer pixel according to the integer pixel motion estimation, is characterized in that it further includes the following steps:

Steps: use the current block, the optimal integer matching block and its adjacent integer pixel blocks to indicate the minimum mean square difference between the current block and the sub-pixel blocks around the integer-pixel optimal matching block and the corresponding optimal sub-pixel blocks, And according to the relationship between the current block, the optimal integer pixel matching block and its adjacent integer pixel blocks, the positions of the horizontal and vertical optimal sub-pixel blocks under arbitrary precision are respectively calculated;

Step 2: According to the sub-pixel precision used in the specific application, the optimal sub-pixel position obtained in step 1 is approximated to obtain the approximate optimal position under the specified precision;

Step 3: Combining the approximate optimal positions in the horizontal and vertical directions respectively obtained in step 2 to obtain a two-dimensional approximate optimal position;

If the two-dimensional approximate optimal position is in a sub-pixel position, use its corresponding block as a candidate block; and select the one with the smallest residual error from the approximate optimal sub-pixel positions obtained in step 2 in the horizontal direction and in the vertical direction, If it is in a sub-pixel position, its corresponding block is used as another candidate block;

The candidate block is searched and matched, and compared with the integer pixel motion estimation result, and the optimal block is taken as the final result.

Described step one comprises the steps:

(11) Calculate the minimum matching error between the current block and the sub-pixel blocks on the left and right sides of the optimal matching block for integer pixel motion estimation, and take the minimum value of the two as the horizontal minimum residual error;

(12) Calculate the minimum matching error between the current block and the sub-pixel blocks on the upper and lower sides of the optimal matching block for integer pixel motion estimation, and take the minimum value of the two as the vertical minimum residual error.

Described step one further comprises the following steps:

(13) According to the minimum matching errors in the horizontal and vertical directions obtained in steps (11) and (12), respectively calculate their corresponding optimal sub-pixel positions under arbitrary precision.

The minimum matching error is one of the minimum mean square error and the minimum sum of absolute differences.

The relationship between the minimum mean square error between the current block and the sub-pixel block and the current block, the optimal integer pixel matching block and its adjacent integer pixel blocks is:

$\mathrm{<span\; class="notranslate">\; Min</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}}$

The relationship between the position of the optimal sub-pixel block and the current block, the optimal integer pixel matching block and its adjacent integer pixel blocks is: $m_h=\frac{{\mathrm{D.}}_{c_{i,j}{r}_{i+1,j}}-{\mathrm{D.}}_{c_{i,j}{r}_{i,j}}}{2{\mathrm{D.}}_{r_{i,j}{r}_{i+1,j}}}+\frac{1}{2}$

Among them, the symbol of the form D _{dx, yd'x, y} represents the absolute difference sum of the two blocks whose upper left position point in the image is dx _{, y,} d' _{x, y} , ci _{, j} is the point on the current block, r _{i, j} is the point on the optimal matching block of an integer pixel, Min(D _{ci, jsi, j} ) represents the minimum mean square error between the sub-pixel block and the current block, and m _h represents the optimal position.

Approximate processing of the optimal sub-pixel position obtained in step 1 in said step 2 includes: when the specified search accuracy is 1/2 ^K , the one-dimensional approximate optimal position m′ and the optimal sub-pixel position obtained in step 1 The relationship between positions m _{and h} is: m'=roumd(m _b ×2 ^K )/2 ^k , where roumd() indicates rounding, thus obtaining an approximate optimal position.

In the third step, the candidate block at the sub-pixel position is selected from the two-dimensional approximate optimal position and the approximate optimal sub-pixel position in the horizontal and vertical directions, including:

1) If the block corresponding to the two-dimensional approximate optimal position is in the sub-pixel position, it is taken as a candidate block.

2) Judging the minimum absolute difference sum corresponding to the approximate optimal position in the horizontal direction and the approximate optimal position in the vertical direction, if the minimum absolute difference sum corresponding to the approximate optimal position in the horizontal direction is small, then further judge whether the approximate optimal position in the horizontal direction is in Sub-pixel position, if it is, select the block corresponding to the approximate optimal position in the horizontal direction as the candidate block; if the minimum absolute difference sum corresponding to the approximate optimal position in the vertical direction is small, then further judge whether the approximate optimal position in the vertical direction is in the sub-pixel position If yes, the block corresponding to the approximate optimal position in the vertical direction is selected as the candidate block.

Step 3 also includes: calculating the value of each sub-pixel point in the candidate block by interpolation, and calculating the minimum absolute difference sum of the block and the current block, and comparing it with the minimum absolute difference sum obtained by integer pixel motion estimation, and comparing the two The corresponding position of the smaller value is used as the final searched motion vector.

The present invention uses the intermediate result of the whole pixel motion estimation to directly determine 0-2 optimal sub-pixel candidate blocks through calculation, and searches on the basis of the candidate blocks. Theoretical analysis shows that for sub-pixel motion estimation with a search accuracy of 1/2 ^K , compared with the sub-pixel full search method, the reduction rate of search blocks is as high as (8×K-2)/8×K or more. Experimental results show that when 1/4 sub-pixel motion estimation is performed, the number of search blocks decreases by more than 90%, while the image quality and compression rate do not change significantly. At the same time, the interpolation storage overhead in the search process of the present invention is close to zero, which is very important for video encoders implemented on special chips and DSP.

Description of drawings

Fig. 1 is a flow chart of the sub-pixel motion estimation method of the present invention;

Fig. 2 is a schematic diagram of pixel distribution of two-dimensional sub-pixel motion;

Fig. 3 is a schematic diagram of decomposing two-dimensional motion into one-dimensional motion for motion estimation;

Fig. 4 is a schematic diagram of a one-dimensional optimal approximation position.

Detailed ways

On the basis of integer pixel motion estimation, the present invention directly deduces the optimal sub-pixel position under arbitrary precision according to adjacent integer pixel values, thereby proposing a fast sub-pixel motion estimation method based on optimal position calculation.

Since the sub-pixel position points are not directly sampled, but are interpolated from adjacent integer pixel sampling points, the position of the sub-pixel block that has the best match with the current block can be directly derived from its surrounding integer pixel values to avoid the current method A point-by-point search comparison in .

The implementation of the present invention will be described below in conjunction with the accompanying drawings. Figure 1 clearly shows the overall flow of the method of the present invention, that is: first calculate the one-dimensional optimal sub-pixel position in the horizontal and vertical directions respectively; Approximate processing to obtain the approximate optimal positions in the horizontal and vertical directions respectively; finally, select candidate blocks according to the approximate optimal positions in the horizontal and vertical directions to complete the search. The details are as follows:

Step 1: According to the relationship between the current block and the optimal matching block of the whole pixel and its adjacent blocks, respectively calculate the positions of the horizontal and vertical optimal sub-pixel blocks with arbitrary precision.

How to calculate the horizontal or vertical optimal sub-pixel position will be described in detail below with reference to FIG. 2 and FIG. 3 . In Figure 2 and Figure 3, "●" represents an integer pixel point; "X" represents a sub-pixel point. In Fig. 3, each point is the upper left point of the block where it is located, R _{i, j} is the optimal matching block of Integer Pixel Motion Estimation (IME), R _{i+1, j} and R _{i-1, j} are the horizontal distances on both sides of For a neighboring block of 1 pixel, R _i,j+1 and R _i,j+1 are neighboring blocks whose vertical distance on both sides is 1 pixel.

In the method of the present invention, it is assumed that the point on the current block to be searched in the coding frame is c _{i, j} (i ∈ (0, M), j ∈ (0, N)), where M and N represent the search block respectively The number of pixels in the horizontal and vertical directions included; each point on the optimal matching block in the reference frame obtained after integer pixel motion estimation is r _{i, j} (i∈(0,M), j∈(0,N)); The sub-pixel block obtained by interpolation between each point r _{i, j} on the optimal matching block is s _{i, j} , and S _{i, j} satisfies the formula: s _{i, j} = mr _{i, j} + (1+m)r _{i+ 1, j} where m is a positional parameter.

Through mathematical derivation, the mean square error between the sub-pixel block on one side of the IME optimal matching block in the horizontal or vertical direction and the current block can be finally expressed as:

${\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Deriving formula (2), and according to the nature of the quadratic function, it can be known that the minimum mean square error between the sub-pixel block and the current block is:

$\mathrm{<span\; class="notranslate">\; Min</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The optimal sub-pixel position corresponding to any precision is:

${\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}}{\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Among them, the symbol of the form D _{dx, d′x, y} represents the absolute difference sum of the two blocks whose upper left position in the image is dx _{, y} , d′ _{x, y,} and ci _{, j} is the upper point of the current block, r _{i, j} is the point on the optimal matching block of an integer pixel, Min(D _{ci, jsi, j} ) represents the minimum mean square error between the sub-pixel block and the current block, and m _h represents the optimal position.

It should be pointed out that motion estimation usually uses mean square error (MSE) or its simplified form sum of absolute difference (SAD) as a matching criterion. In the above mathematical analysis, the MSE matching criterion is used for analysis. In the actual motion estimation process, the mean square error MSE is usually replaced by absolute difference and SAD value in order to reduce the amount of computation. Therefore, it can be understood that the method described in the present invention can similarly adopt the SAD matching criterion. In this case, the MSE values in formulas (2) and (3) are replaced by the corresponding SAD values.

According to the mathematical formula obtained by the above mathematical derivation, the specific implementation steps that need to be carried out in step 1 are as follows:

(1) Calculate the minimum absolute difference sum of the sub-pixel blocks on the left and right sides of the current block and R _{i, j} by formula (2), and take the minimum value of the two as the horizontal minimum residual, denoted as S _h ;

(2) Calculate the minimum absolute difference sum of the sub-pixel blocks on the upper and lower sides of the current block and R _{i, j} by formula (2), and take the minimum value of the two as the vertical minimum residual, denoted as S _v ;

(3) Calculate the optimal sub-pixel positions h and v corresponding to Sh _and S _v respectively under arbitrary precision according to formula (3).

Step 2: According to the sub-pixel precision used in the specific application, the optimal sub-pixel position obtained in step 1 is approximated to obtain the approximate optimal position under the specified precision.

Step 1 obtains the optimal position under arbitrary precision. However, in practical applications, after the motion estimation (ME) reaches a certain accuracy, the reduction of the residual coefficient is very small, but the motion vector occupies a large number of bits, so that the final coding bit number no longer decreases significantly. Therefore, 1/2, 1/4 or 1/8 precision is generally used in practical applications. For example, ME of MPEG-4 uses 1/2 pixel, and JVT can be accurate to 1/8 pixel. In order to conform to the international standard, the value of m _h in practical application should be consistent with the search accuracy (1/2, 1/4 or 1/8) used in the standard.

From formula (1), the absolute difference sum D _ci,jsi,j of the sub-pixel blocks around the current block and the optimal matching block of the whole pixel is the quadratic parabolic function of the sub-pixel position m, and it can be known from the symmetric monotonicity of the parabola: when When the search accuracy is specified as 1/2 ^K , the sub-pixel position closest to the optimal position for calculation is the optimal approximation. Based on this, the calculation formula for the one-dimensional approximate optimal position m′ under the specified accuracy is obtained:

m'＝round(m _b ×2 ^K )/2 ^K (4)

Among them, round means rounding, and m _h is the optimal position obtained in step 1. As shown in Figure 2, when the 1/4 pixel precision is used and the sub-pixel position is 9/16, the minimum absolute difference sum is obtained. At this time, the 1/4 sub-pixel position closest to 9/16 is 1/2, so 1/ 2 is the best approximate position.

According to the optimal positions h and v obtained in step 1 and the specified search precision, calculate the approximate optimal positions h' and v' under the search precision according to formula (4).

Step 3: Combine the approximate optimal positions in the horizontal and vertical directions in step 2 to obtain a two-dimensional approximate optimal position. Select a candidate block at a sub-pixel position from the two-dimensional approximate optimal position obtained by synthesis and the approximate optimal sub-pixel position in the horizontal and vertical directions in the preceding steps, and search the candidate block to obtain a motion estimation result.

In step 2, the approximate optimal positions on two one-dimensional directions, horizontal and vertical, are calculated respectively. Considering that two-dimensional motion can be regarded as the synthesis of sub-motions on two one-dimensional directions, horizontal and vertical, in the present invention, the horizontal , and the two-dimensional position block corresponding to the vertical position synthesis as a candidate block. In addition, considering that the position of the candidate block is an approximate result, in order _{to improve the accuracy of ME, the corresponding block of the smaller one of the horizontal optimal position block Sh and the vertical optimal position block S v is} taken as another candidate blocks. Search and match the block at the sub-pixel position among the two candidate blocks, and compare it with the integer-pixel search result, and take the optimal block as the final result. It can be seen that the present invention reduces the candidate blocks to two or less, thus significantly reducing the overhead, but the search speed is very fast. The specific steps of step three are as follows:

(1) Set the candidate block set to be empty, if the point (h', v') is in the sub-pixel position, add its corresponding block to the candidate block set;

(2) If S _h ≤ S _v and the point (h', 0) is at the sub-pixel position, add the block corresponding to (h', 0) to the candidate block set; go to (4);

(3) If S _h > S _v and the point (0, v') is at the sub-pixel position, then add the block corresponding to (v', 0) to the candidate block set;

(4) Perform operations such as interpolation and search on each block in the candidate block set to determine the final result. That is: calculate the value of each sub-pixel point in the candidate block by interpolation, and calculate its absolute difference sum with the current block, compare it with the minimum absolute difference sum of the whole pixel motion estimation, and take the corresponding position of the minimum value of the two as the final The searched motion vector.

The above disclosures are only specific embodiments of the present invention. According to the ideas provided by the present invention, changes conceivable by those skilled in the art should fall within the protection scope of the present invention.

Claims (9)

1. A fast sub-pixel motion estimation method, comprising obtaining the optimal matching block of the whole pixel according to the whole pixel motion estimation, is characterized in that further comprising the following steps: Step 1: Use the current block, the optimal matching block of the integer pixel and its adjacent integer blocks to represent the minimum mean square difference between the current block and the sub-pixel blocks around the optimal matching block of the integer pixel and the position of the corresponding optimal sub-pixel block , and calculate the positions of the horizontal and vertical optimal sub-pixel blocks with arbitrary precision according to the relationship between the current block, the optimal integer-pixel matching block and its adjacent integer-pixel blocks; Step 2: According to the sub-pixel precision used in the specific application, the optimal sub-pixel position obtained in step 1 is approximated to obtain the approximate optimal position under the specified precision; Step 3: Combining the approximate optimal positions in the horizontal and vertical directions respectively obtained in step 2 to obtain a two-dimensional approximate optimal position; If the two-dimensional approximate optimal position is in a sub-pixel position, use its corresponding block as a candidate block; and select the one with the smallest residual error from the approximate optimal sub-pixel positions obtained in step 2 in the horizontal direction and in the vertical direction, If it is in a sub-pixel position, its corresponding block is used as another candidate block; The candidate block is searched and matched, and compared with the integer pixel motion estimation result, and the optimal block is taken as the final result. 2. fast sub-pixel motion estimation method as claimed in claim 1, is characterized in that: described step 1 comprises the step: (11) Calculate the minimum matching error between the current block and the sub-pixel blocks on the left and right sides of the integer pixel optimal matching block, and take the minimum value of the two as the horizontal minimum residual error; (12) Calculate the minimum matching error between the current block and the sub-pixel blocks on the upper and lower sides of the optimal integer matching block, and take the minimum value of the two as the vertical minimum residual error. 3. fast sub-pixel motion estimation method as claimed in claim 2, is characterized in that: described step 1 further comprises the following steps: (13) According to the minimum matching errors in the horizontal and vertical directions obtained in steps (11) and (12), respectively calculate their corresponding optimal sub-pixel positions under arbitrary precision. 4. fast sub-pixel motion estimation method as claimed in claim 2, is characterized in that: The minimum matching error is one of the minimum mean square error and the minimum sum of absolute differences. 5. fast sub-pixel motion estimation method as claimed in claim 1, is characterized in that: The relationship between the minimum mean square error between the current block and the sub-pixel block and the current block, the optimal integer pixel matching block and its adjacent integer pixel blocks is: $\mathrm{<span\; class="notranslate">\; Min</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; D.</span>}}_{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}}$ The relationship between the position of the optimal sub-pixel block and the current block, the optimal integer pixel matching block and its adjacent integer pixel blocks is: $m_b=\frac{{\mathrm{D.}}_{c_{i,j}{r}_{i+1,j}}-{\mathrm{D.}}_{c_{i,j}{r}_{i,j}}}{{2\mathrm{D.}}_{r_{i,j}{r}_{i+1,j}}}+\frac{1}{2}$ Among them, the symbol of the form D _{dx, yd'x, y} represents the absolute difference sum of the two blocks whose upper left position point in the image is dx _{, y} , d' _{x, y} , ci _{, j} is the point on the current block, r _{i, j} is the point on the optimal matching block of an integer pixel, Min(D _{ci, jxi, j} ) represents the minimum mean square error between the sub-pixel block and the current block, and m _b represents the optimal position. 6. The fast sub-pixel motion estimation method as claimed in claim 1, characterized in that: Approximate processing of the optimal sub-pixel position obtained in step 1 in said step 2 includes: when the specified search accuracy is 1/2 ^K , the one-dimensional approximate optimal position m′ and the optimal sub-pixel position obtained in step 1 The relationship between the positions m _b is: m'=round(m _b ×2 ^K )/2 ^K , where, round() means rounding, thus obtaining an approximate optimal position. 7. The fast sub-pixel motion estimation method as claimed in claim 1, characterized in that: In said step 3, selecting a candidate block at a sub-pixel position from the two-dimensional approximate optimal position and the approximate optimal sub-pixel position in the horizontal and vertical directions, including: 1) If the block corresponding to the two-dimensional approximate optimal position is in the sub-pixel position, it is taken as a candidate block. 2) Judging the minimum absolute difference sum corresponding to the approximate optimal position in the horizontal direction and the approximate optimal position in the vertical direction, if the minimum absolute difference sum corresponding to the approximate optimal position in the horizontal direction is small, then further judge whether the approximate optimal position in the horizontal direction is in Sub-pixel position, if yes, select the block corresponding to the approximate optimal position in the horizontal direction as the candidate block; if the minimum absolute difference sum corresponding to the approximate optimal position in the vertical direction is small, then further judge whether the approximate optimal position in the vertical direction is in the sub-pixel position If yes, the block corresponding to the approximate optimal position in the vertical direction is selected as the candidate block. 8. The fast sub-pixel motion estimation method as claimed in claim 7, characterized in that: The third step also includes: calculating the value of each sub-pixel point in the candidate block by interpolation, and calculating the minimum absolute difference sum of the block and the current block, and comparing it with the minimum absolute difference sum obtained by integer pixel motion estimation, and comparing the two The corresponding position of the smaller value among them is used as the final searched motion vector.

Images