CN1960487B - Method for estimating motion vector based on distance weighted search order - Google Patents

Abstract

The invention discloses a method for estimating motion vector based on distance weighted searching sequence, which refers to a preset image block of a first image and searches image blocks matched with the preset image block in a second adjacent image to estimate the motion vector of the preset image block, and is characterized in that: the method selects a block as an initial point in the second picture according to a predetermined principle, and expands and searches the block matched with the predetermined block in a distance weighting mode to estimate the motion vector of the predetermined block.

Description

A method for estimating motion vectors based on distance-weighted search order

technical field

The present invention relates to a method for motion estimation of video coding, in particular to a method for motion estimation in a distance weighted order.

Background technique

As shown in Figure 1, currently in the data stream (Data stream) of MPEG video coded images, its data structure is composed of one or more sequences (Sequence), and each sequence contains most A group of pictures (Group of Picture, GOP), and the so-called group of pictures refers to a group composed of many pictures (Frame) or pictures (Picture), and the pictures can be distinguished from intra-frame coding pictures according to their attributes (I Frame), predictive coding frame (PFrame), and bidirectional coding frame (B Frame) image types.

Each of the above-mentioned pictures can be coded. Generally, the intra-coded (I) picture is used as the starting point of image compression. By estimating the motion vector (Motion Vector), the predictive coded (P) picture can be intra-coded (I) picture or predictive coded (P) picture is used as a reference picture for prediction, while bidirectionally coded (B) picture is based on both intra coded (I) picture and predictive coded (P) picture or two predictive coded (P) pictures ) frame is estimated as the motion vector generated by the reference frame, so that after playing the frame continuously, it will be presented as a dynamic MPEG video image in front of the user.

In the MPEG compression standard, in addition to the estimation of the motion vector, there is also the so-called motion compensation (Motion Compensation). Generally, the most direct method of motion compensation is to record the brightness and chroma of each pixel, and use The Full Search method records the changes of the two, but this will consume a lot of resources. Therefore, the current practice is to subdivide each picture into several slices, and the slices can be further divided into several slices. A macroblock (MacroBlock, MB), and a macroblock can be composed of four brightness (Luminance) blocks and several chroma (Chrominance) blocks, and finally each block (Block) is defined as an MPEG data structure The smallest coding unit.

Cooperating with motion vector estimation and motion compensation technology, the current frame can find the best matching pixel blocks from the previous frame through the existing image blocks, and use the calculated motion vector and difference data to convert the image blocks of the previous frame to Adjust to become the current picture, the image block can be transferred to the appropriate position according to the motion vector, and the difference data can provide the change of brightness, chroma and saturation value, because there is no need to record most of the repeated data, so the amount of stored data can be saved To achieve the purpose of data compression.

As shown in FIG. 2, the above-mentioned method of finding the best matching image block from the previous picture is taken as an example of a current three-step search (Three Step Search; TSS) judgment method. First, a search area 21 to be searched is used The center is defined as the starting point 210, and the outer 8 points are used as checkpoints, assuming that the search area size of the search area 21 is 4×4, and the checkpoint 20 found at the bottom right of the search area 21 is similar, then the checkpoint 20 is used The search area 22 is narrowed down to 2×2 as the center, and finally the most similar checkpoint 220 is found at the upper right of the search area 22 , and the motion vector value can be defined accordingly.

There is an existing Diamond Shape Search (DSS) judgment method, which uses a rhombus frame as the search area. The steps are as follows:

Step 1: Find a search starting point and a hollow rhombus frame with the starting point as the center, a total of nine points, if the most similar point is in the center of the rhombus, go to step 4, if the most similar point is in the rhombus frame, go to step 2.

Step 2: Take the most similar point as the center point, and repeatedly use a diamond-shaped outer frame as the search area.

Step 3: If the most similar point is still at the center point, go to step 4, if the most similar point is on the diamond frame, then repeat step 2.

Step 4: Narrow down the search area. The search range is a small solid diamond, and the search ends when the most similar point is found.

As shown in Figure 3, in step 1, the most similar point is found in the diamond center 1', so step 4 is performed to narrow the search area to a small solid diamond, and finally the most similar point 2' is found to end the search.

As shown in Figure 4, it shows that in step 1, the most similar point 1" is in the diamond-shaped outer frame, so proceed to step 2, take the most similar point 1" as the center point, and repeatedly use a diamond-shaped outer frame as the search area, and then proceed to step 3 , because the most similar point 2” is on the rhombus outer frame, so repeat step 2 and use a rhombus outer frame as the search area, and find that the most similar point is still at the center of the rhombus 2”, so proceed to step 4 to narrow the search range of the search area It is a small solid diamond, and the search ends after finding the most similar point 4".

As shown in Figures 5 and 6, no matter whether it is a three-step search or a diamond search, the search sequence is still mainly scanning (Raster Pattern) search or spiral (Spiral Pattern) search method. The so-called scanning search is to find the most similar checkpoints column by row from left to right and top to bottom within the defined search range; while the so-called spiral search method is to search from the center to Starting from the point, search outward point by point in a spiral order.

Contents of the invention

Therefore, it is an object of the present invention to provide a method for estimating a motion vector based on a distance-weighted search sequence that saves time spent on searching and improves efficiency.

Therefore, the method for estimating the motion vector based on the distance-weighted search order of the present invention is to refer to a predetermined image block in a first frame, and search for a matching image block corresponding to the predetermined image block in an adjacent second frame to estimate the predetermined image block. The moving vector of the image block is characterized in that: the method is to use a image block selected according to a predetermined principle as a starting point in the second picture, and gradually expand outwards in a distance-weighted manner to search for a match with the predetermined image block The selected image block is used to estimate the motion vector of the predetermined image block, and the selected image block is the center point of the search area.

In view of the fact that the motion vectors usually appear in a radial distribution, the distance-weighted sequential search according to the present invention can avoid the search time spent point by point in the aforementioned scanning search or spiral search method.

Description of drawings

Below in conjunction with accompanying drawing and embodiment the present invention is described in detail:

Fig. 1 is a schematic diagram illustrating the current data data structure of an MPEG video coded image;

Fig. 2 is a schematic diagram illustrating an existing three-step judgment method;

Fig. 3 is a schematic diagram illustrating an existing diamond judging method;

Fig. 4 is a schematic diagram illustrating an existing diamond judging method;

Fig. 5 is a schematic diagram illustrating a current scanning search method;

Fig. 6 is a schematic diagram illustrating a current spiral search method;

Fig. 7 is a block diagram of a circuit, illustrating that the system using the method of the present invention is a video encoding device for performing MPEG video encoding functions;

FIG. 8 is a schematic diagram illustrating the motion vector estimation method of the method for estimating motion vectors based on the distance-weighted search sequence of the present invention;

FIG. 9 is a schematic diagram illustrating the search sequence performed by the distance-weighted sequence rule in the first preferred embodiment of the method for estimating motion vectors based on the distance-weighted search sequence;

FIG. 10 is a schematic diagram illustrating the search sequence performed by the distance-weighted order rule in the second preferred embodiment of the method for estimating motion vectors based on the distance-weighted search order of the present invention.

Detailed ways

The aforementioned and other technical contents, features and effects of the present invention will be clearly presented in the following detailed description of three preferred embodiments with reference to the drawings. Before the present invention is described in detail, it should be noted that in the following description, similar elements are denoted by the same reference numerals.

As shown in FIG. 7 , the system using the method of the present invention is a video coding device 1 for performing MPEG video compression function. However, in other embodiments, it may be applied to a processing system for performing similar video compression function.

The video encoding device 1 has a preprocessor unit (Preprocessor) 10, a motion estimation unit (MotionEstimation) 11, a motion compensation unit 12, a motion vector encoding unit (Motion Vector Encoding Unit) 13, a texture encoding module (Texture Encoding Unit) ) 14, a bit stream composition unit (Bit-Stream Composer) 15 and a memory 16.

When an original input image 100 is to be input to the video coding device 1, a pre-processing unit 10 of the video coding device 1 first defines each large block data in a given frame and temporarily stores it in the memory 16; then the motion estimation unit 11 calculates the bulk data of the frame in the input image 100, for example, after computing the corresponding pixel data in the front and rear frames, the motion vector of each pixel data in the full frame can be obtained Data 102; then it is input to the motion compensation unit 12, and the motion compensation unit 12 uses the motion vector to retrieve the image block data in the previous or next frame to obtain a reference data 104; then the pre-processing unit 10 After subtracting the reference data 104 obtained by the motion compensation unit 12 from the image block data possessed by the input image 100, a difference data 103 is obtained, and the texture coding module 14 operates on the difference data 103 to obtain compressed texture and Reconstructed references.

A discrete cosine transform unit 141 of the texture coding module 14 is to apply discrete cosine transform (DCT) to the pixel data of each image block, and then use the frequency domain transform unit 142 to convert the pixel data from the time domain to the frequency domain, and then A quantization (Quantize) step is applied by the quantization unit 143, so that many DCT coefficients quantized to zero after the discrete cosine transform are removed, and high-frequency parts are removed; And the inverse discrete cosine transform operation, which is then fed back to the motion estimation unit 11 . Each motion vector can be coded by the motion vector coding unit 13 and output to a variable length coder 151 of the bit stream combining unit 15 .

At the same time, it is necessary to use the AC/DC prediction unit 146 (AC/DC Prediction) to remove the redundant information repeated in each block (Block) in the same picture, and then the interleaved scanning unit 147 performs interleaved scanning (Zig-zag scan) to quantize After the DCT coefficients are rearranged, the low-frequency coefficients are arranged in front and the high-frequency coefficients are arranged in the back, and finally the dynamic length encoding (Run Length Encoding; RLE) is performed on the DCT coefficients after interleaved scanning, and finally the bit stream combination unit Another variable length encoder 152 in 15 performs variable length coding (VariableLength Coding; VLC) on the two, and combines them by the bit stream combining unit 15 to complete the output in the MPEG compression format.

As shown in Figures 7 and 8, the three preferred embodiments of the method for estimating the motion vector based on the distance-weighted search sequence of the present invention are all performed in the motion estimation unit 11 of the video coding device 1, however, in other embodiments , the concept of the present invention can also be used in the current common all-find search, diamond search, three-step search, four-step search or any other dynamic estimation.

Described method is from a predetermined image block 51 that a first picture 501 (also known as current picture; Current Frame) has, and searches for an adjacent second picture 502 (also known as reference picture; Reference Frame) corresponding The matching image block 52 of the predetermined image block 51 is used to estimate the movement vector 53 of the predetermined image block 51. The method is to select a image block as a starting point in the second picture 502 according to a predetermined principle, and to The matching image block 52 is gradually expanded to estimate the motion vector 53 of the predetermined image block 51 .

The method for estimating the motion vector based on the distance-weighted search sequence of the present invention can be described by formula 1 for the concept of weighted distance:

Search weighted distance = H(u, v); Formula 1

H is a predetermined distance weight function, u is the U-axis coordinate distance from the starting point, v is the V-axis coordinate distance from the starting point, the U and V coordinates are a set of bases (Bases) that constitute the plane, and the search order is Start searching from the image blocks with the smallest weighted distance first.

As shown in Figure 9, it illustrates the first preferred embodiment of the method for estimating the motion vector based on the distance-weighted search order of the present invention. In this embodiment, the distance-weighted calculation is calculated according to formula 2; x is the distance from the starting point is the X-axis coordinate of , y is the Y-axis coordinate of the distance from the starting point, and the search sequence is to start searching from each image block with the smallest weighted search distance.

Weighted search distance = (absolute value (x) + absolute value (y)) Formula 2

The search sequence is to start from the center point 301 of a search area 201 (Original), and start searching according to the calculated minimum distance. Spread out to the unsearched area, and so on, until the closest block is found.

As shown in FIG. 10 , the second preferred embodiment of the method for estimating the motion vector based on the distance-weighted search order of the present invention is illustrated. In this embodiment, the distance-weighted calculation is calculated according to formula 3; x is the distance from the starting point is the X-axis coordinate of , y is the Y-axis coordinate of the distance from the starting point, and the search sequence is to start searching from the image block with the smallest weighted search distance.

Weighted search distance = minimum value (square root (x ² +y ² )) Formula 3

The search sequence of the second preferred embodiment is similar to that of the first preferred embodiment. The center point 302 of a search area 202 is used as the starting (Original) point, and the search is started according to the calculated minimum distance. For example, search 302 itself first. (1), then search for the 4 points (2, 3, 4, 5) closest to 302, and then gradually search for 4 points (6, 7, 8, 9) around 302, if the above 9 points cannot be searched , and then spread out to the outer multi-points of the unsearched area, still start searching with the point closest to 302, such as first find (10, 11, 12, 13), and then find (14, 15, 16, 17 , 18, 19, 20, 21), and so on, until the closest block is found.

The third preferred embodiment of the present invention converts various distance values by looking up a table, and the calculation of the weighted distance is shown in formula 4:

Search weighted distance = F(u)+G(v)=F(abs(x))+G(abs(y)) Formula 4

F(u) and G(v) can be converted from a predetermined distance weight function table by means of table lookup, x is the x-axis coordinate distance from the starting point, y is the y-axis coordinate distance from the starting point, and the search order It is to start searching from each image block with the smallest weighted distance first. Examples of the foregoing distance weight function table are shown in Table 1 and Table 2, and F(·)=G(·) in the formula.

Table 1

u F(u) 0 1 1 3 2 4 3 5 4 7 5 8 6 8 7 8 8 10 9 10 10 10 11 11 12 11 13 11 14 11 15 11

Table 2

u F(u) 0 1 1 4 2 7 3 8 4 10 5 10

u F(u) 6 11 7 11 8 11 9 11 10 11 11 11 12 11 13 12 14 12 15 12

It must be noted that the values of u and v in Tables 1 and 2 can be counted incrementally, that is, the values of u and v and the corresponding values of F(u) can be continuously amplified, without being limited to the above list; in addition, this In addition to the way that the values of u and v increase each time in the embodiment, the value of an integer point can be substituted into the distance weight function table, or a non-integer point, such as 1/2, 1/4 or 1/8, etc. Numerical values are substituted into the distance weight function table, all of which belong to the applicable category of the present invention.

To sum up the above, the principle of the method for estimating the motion vector based on the distance-weighted search order of the present invention is that the general motion vector usually appears in a radially distributed manner from inside to outside, so compared with the previous scanning search, or It is a spiral search method, and according to the present invention, similar image blocks can be quickly found by searching in distance-weighted order, and unnecessary search time is saved so that the estimation of the motion vector is more efficient.

Claims (8)

1. A method for estimating a motion vector based on a distance-weighted search order, which is to refer to a predetermined image block in a first frame, and search for a matching image block corresponding to the predetermined image block in an adjacent second frame to estimate The moving vector of predetermined image block is characterized in that: In the second frame, the method selects a block as a starting point according to a predetermined principle, and uses a distance-weighted method to search for blocks matching the predetermined block to estimate the movement vector of the predetermined block. A selected image block is the center point of the search area. 2. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 1, wherein: The calculation of the weighted distance is based on the following formula: Search weighted distance = H(u, v); H is a predetermined distance weight function, u is the U-axis coordinate away from the starting point, v is the V-axis coordinate away from the starting point, the U and V coordinates are a set of bases that constitute the plane, and the search order is self-weighted Each image block with the smallest distance starts to search. 3. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 2, wherein: The calculation of the weighted distance is based on the following formula: Search weighted distance = (absolute value (x) + absolute value (y)); x is the X-axis coordinate of the distance from the starting point, y is the Y-axis coordinate of the distance from the starting point, and the search sequence starts from the image blocks with the smallest weighted distance. 4. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 2, wherein: The calculation of the weighted distance is based on the following formula: Search weighted distance = (square root(x ² +y ² )); x is the X-axis coordinate of the distance from the starting point, y is the Y-axis coordinate of the distance from the starting point, and the search sequence starts from the image blocks with the smallest weighted distance. 5. The method for estimating motion vectors based on distance-weighted search order as claimed in claim 2, characterized in that: The calculation of the weighted distance is based on the following formula: Search weighted distance = F(u)+G(v)=F(abs(x))+G(abs(y)) F(u) and G(v) can be converted from a predetermined distance weight function table by means of table lookup, x is the x-axis coordinate distance from the starting point, y is the y-axis coordinate distance from the starting point, and the search order It is to start searching from each image block with the smallest weighted distance first. 6. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 5, wherein: In the formula, the unit of each increment of the u and v values is substituted with an integer value. 7. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 5, wherein: In the formula, the unit of each increment of the u and v values is substituted with a non-integer value. 8. The method for estimating a motion vector based on a distance-weighted search order as claimed in claim 1, wherein: The method can be used in full search, diamond search, three-step search, four-step search and any other dynamic estimation methods.

Images