JP2002135784A - Video coding method - Google Patents

Abstract

(57) Abstract: A video encoding method using motion estimation and compensation with an adaptive motion search range is provided. A fixed motion search range sometimes fails to find a true match for very fast motion. Also, a fixed motion search range wastes enormous processing time for very slow motion. By using a method of adaptively expanding / reducing the motion search range from the reference value, the efficiency of motion estimation is increased, and as a result, the coding efficiency is improved.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to compression of a video signal,
In particular, it relates to motion estimation and compensation for moving images.

[0002]

2. Description of the Related Art Digital transmission and storage of television and video signals has received increasing attention recently. The reason is that the quality is higher and the flexibility is greater as compared with the analog signal. Digital video images contain large amounts of image data and transmission bandwidth is limited, so that video signal encoding techniques are required to be very efficient. The most efficient compression systems use not only spatial correlation, as in still image processing, but also time correlation between adjacent frames. Systems that consider both spatial and temporal correlation are also referred to as hybrid coding systems.

[0003] The elimination of redundancy in the spatial domain has been studied for a long time, and various transformation methods have been studied.
DCT (Discrete Cosine Transform) has proven to be the best transform in terms of efficiency and complexity. DCT
Can compress the energy of the transformed data into smaller regions, and therefore require less data to represent the original data.

[0004] Removal of temporal redundancy is basically performed using a differential encoding technique. That is, the prediction is first made based on information derived from the previous frame of the same video sequence, and the difference between the real frame and the prediction of the real frame is transmitted.

[0005] Since the amount of motion in a video frame is very different for different parts of the frame, the video frame is processed by dividing the frame into a number of blocks of pixel data. For each block in the frame, a motion vector is derived by comparing the block of pixel data of the current frame with the block of the previous frame, and motion compensation is performed by subtracting similar block data of the previous frame from the block data of the current frame. Is performed, and differential encoding is realized by motion compensation on each block of pixel data for one frame.

The process of finding motion vectors is called motion estimation, and it is well known that efficient motion estimation provides efficient motion compensation with high prediction accuracy, resulting in an efficient coding system. I have.

[0007] Further, since the processing time of the motion estimation is shorter, real-time applications can be realized at low cost.

[0008] A good product is to be a good system with high coding efficiency and low cost.

[0009]

In current compression algorithms, the same algorithm is used to encode various video sequences. Some sequences contain no motion, some contain slow motion, and some contain very fast motion.

In the MPEG (Moving Picture Expert Group) coding standard, a matching method with a search window is used to search for a similar block of pixel data in a preceding frame or a succeeding frame. The size of the search window is called a search range. Regardless of whether the motion content of the image frames in the sequence is static, slow motion, or fast motion, the search range is (+/− 15 pixels or +/− 30 pixels or +/− 30 pixels) for the entire frame and the entire encoding process. Fixed to one of the pixels).

The larger the search range, the greater the amount of calculation required to perform the search. If the search range is too small, the motion block may be left outside the search range.

[0012] Locking the search range causes some problems in sequences containing various levels of motion. For example, the motion in the frame is too fast (ie, the actual motion vector value is large), the fixed motion search range is not enough to cover the motion block, the efficiency of motion compensation is low, etc. FIG. 1 illustrates the problem that arises when the +/− 15 motion search range is not sufficient.

The reason for the inefficiency is that if the true matching block (A 'in FIG. 1) of the pixel data of the preceding frame (reference frame) cannot be found in the motion search range of +/- 15 pixels, Is adopted as a substitute for the true match block of A. As a result, the prediction error becomes so large that more bits are allocated to encode the block. Furthermore, if the number of bits is limited, the block reconstructed from the false matching block is very different from the true block of A, resulting in significant distortion.

On the other hand, if the movement in the frame is very slow,
Alternatively, when the image is almost a still image, an extremely small motion search range is sufficient. Performing motion estimation and compensation using a +/- 15 pixel search window wastes unnecessary computation time.

FIG. 2 illustrates this problem. A is the current block,
A ₀ ′ is a block in the reference frame at the same position as A in the current frame, and A ′ is a block matching A. For a slow motion sequence, A's matching block A 'is at almost the same position in the reference frame as compared to A in the current frame. That is, a very small search range is sufficient for such a sequence, and a fixed large search range wastes a lot of search time.

In view of the above problems, it is advantageous to provide an adaptive motion search range for different regions in one sequence and for different sequences in the video coding process. An object of the present invention is to provide a video encoding method using motion estimation and compensation with such an adaptive motion search range.

[0017]

SUMMARY OF THE INVENTION A video encoding method according to the present invention first examines all the motion vectors in a frame and, depending on whether the motion is slow or fast, respectively,
Alternatively, a middle motion search range (reference) is set. Motion estimation is performed using this criterion as the size of the search window.

Next, the video encoding method according to the present invention examines a motion estimation error (prediction error) in one area,
The error is compared with a predetermined threshold value, and the motion search range (reference) is adjusted according to the result of the comparison. If the prediction error is larger than the threshold, the motion search range is expanded, otherwise it is reduced.

The video encoding method according to the present invention also includes a method of fine-tuning the threshold by examining the characteristics of a processing region in which different thresholds are set for regions having different characteristics. .

According to another aspect of the present invention, there is provided a video encoding method comprising: dividing a current frame of an input video signal into a plurality of blocks of pixel data; Dividing the reference frame into a number of blocks of pixel data; searching for a block in the reference frame that best matches the current block within a reference motion search range; and detecting the motion content in the current frame. Step: Enlarging the reference motion search range to an appropriate value when high-speed motion exists, and reducing the reference motion search range to an appropriate value when there is no motion or low-speed motion And a step.

The video encoding method according to claim 2 of the present invention is the video encoding method according to claim 1 of the present invention, wherein the step of detecting the content of the motion is performed between the current block and the matched block. Obtaining a prediction error of the above and comparing it with a threshold value to determine whether or not a high-speed motion exists; and, when a high-speed motion exists in the sequence, setting the reference motion search range to an appropriate value. It is characterized by including a step of enlarging and a step of searching for a motion vector from the corrected search range.

A video encoding method according to a third aspect of the present invention is the video encoding method according to any one of the first and second aspects of the present invention, wherein the reference motion search range is a frame of a frame corresponding to a minimum prediction error. Obtaining all the motion vectors, checking whether all of the motion vectors are smaller than a predetermined value, and reducing the motion search range when all of the motion vectors are smaller than the predetermined value. It is characterized in that it is adjusted on the basis of this.

A video encoding method according to a fourth aspect of the present invention is the video encoding method according to any one of the first to third aspects of the present invention, wherein a motion vector obtained from the motion estimation is used. Finding a corresponding matching block from the frames resulting from the local decoder;
Generating a prediction error between a current block in a current frame and a matching block from a decoded frame; and encoding the prediction error for transmission. It is.

A video encoding method according to a fifth aspect of the present invention is the video encoding method according to the second aspect of the present invention, wherein a step of calculating a standard deviation of a current block of pixel data, Calculating an average standard deviation of the current block, calculating a correction value from the standard deviation and the average standard deviation in the current block, and correcting a predetermined threshold value using the correction value. Is what you do.

According to a sixth aspect of the present invention, in the video encoding method according to the first aspect of the present invention, the adjustment of the adaptive motion search range is performed on a sequence basis, a frame basis, a micro block basis, and a region basis. It is characterized in that it can be performed on a standard basis.

A video encoding method according to a seventh aspect of the present invention is the video encoding method according to the first aspect of the present invention, wherein the motion search window indicating the adaptive motion search range is a square, a circle, a rectangle, or any other arbitrary one. It may be characterized by the following shape.

With the method described above, the present invention detects a slow or fast motion sequence in the encoding process,
A small or medium value is assigned as an initial reference for the motion search range for each of the slow or fast motions. This criterion is then compared with the prediction error and a threshold value to see if the criterion of the motion search range is sufficient, thereby maximizing the efficiency of motion estimation in the shortest possible processing time, i.e., video coding. To get the best image quality.

[0028]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An encoding method according to an embodiment of the present invention is suitable for motion estimation and compensation in different modes that require searching for a motion vector in any reference region.
These include frame-based motion estimation and compensation, field-based motion estimation and compensation, and adaptive frame / motion estimation.
Includes field motion estimation and compensation.

A preferred embodiment of the present encoding method is shown in FIGS.

FIGS. 3 and 4 show a flow for adaptively changing the motion search range. 3 and 4, the MS in step S1
R means a motion search range. Min_ of step S8
error is the minimum error among all the prediction errors within the fixed motion search range. Further, each prediction error is the sum of the absolute differences of each pixel pair between the block in the current frame and the block in the reference frame.

The threshold value in step S8 in FIG. 4 is a presentation value, the MSR_exp in step S9 is the motion search range after expansion, and the Exp in step S9 is expansion based on the initial reference value of the motion search range. Value. T_p in step S13 is a period, and needs to be determined before encoding starts.

There are two main processes described below.

A) The first process is step S in FIG.
1 and S2 (for example, T
A minimum reference motion search range is found by checking all the motion vectors of the frames shown in steps S1, S2, and S3 in FIG. 3 within _P = 1 second).

The detailed process will be described below, starting from the first frame.

First, in steps S1 and S2 of FIG. 3, the first frame of the video sequence is encoded to remove spatial correlation, and each block of pixel data of the second frame is predicted from the first frame. . That is, a medium motion search range (eg, +/− 15 pixels)
In step S3, a motion vector indicating the position of each current block in the reference frame is obtained, and a smaller value (for example, +/-) is obtained.
8 pixels). If all the absolute values of the motion vectors are much smaller than the smaller value, the motion search range is changed for the following other frames in step S of FIG.
As shown in FIG. 4, the medium value (+/− 15 pixels) is set to this small value (+/− 8 pixels), or the motion search range is still medium as in step S5 of FIG. (+/− 15 pixels).

B) The second process searches for a true matching block based on the reference motion search range obtained from the first process by adaptively expanding the motion search range. The detailed process includes: That is, in steps S6 and S7, a match is made in the reference frame using a medium motion search range (+/− 15 pixels) for fast motion or a smaller value (+/− 8 pixels) for slow motion. Search for blocks.

FIGS. 5 and 6 show detailed flows of steps S6 and S7.

As shown in FIGS. 5 and 6, in step S14, one block is obtained from the current frame.
Gets the block at the same position from the reference frame. In step S16, the absolute error between the two blocks is calculated, and the minimum error, that is, min1, min2, is obtained for field 1 and field 2. The minimum error for the frame, min is field 1 and field 2
It is the sum of the minimum errors for

In step S17, the next block is obtained from the reference frame in the motion search range.
Calculate absolute errors err1 and err2 for field 1 and field 2, respectively. The frame error (err) is the sum of the errors for field 1 and field 2.

In step S19, err1, er
r2 and err are compared with min1, min2 and min, respectively, and any one of the corresponding mi
If it is smaller than n1, min2 or min, the corresponding m
Replace in1, min2 or min. As shown in step S20, this step is performed until the motion search range is reached. If the end of the motion search range has not been reached, steps S17 to S20 are continued. To process.

Min1, min2, min, err1,
The definitions of err2 and err will be described with reference to FIG. FIG.
In the figure, the hatched portion of each block indicates the field 1, and the blank portion of each block indicates the field 2. Min1 in FIG. 6 is a block (C) from the current frame;
6 is the absolute error of field 1 between two blocks of block (D) from the reference frame located at the same position as the current block, min2 in FIG. 6 is the absolute error of field 2 between the two blocks, and min in FIG. Is the absolute error of the frame between the two blocks, and min is the sum of min1 and min2.

Err1 in FIG. 6 is the absolute error of field 1 between the current block (C) and another block (D) from the reference frame within the fixed motion search range. Err2 in FIG. 6 is the absolute error of field 2 between the current block (C) and another block (D) from the reference frame within the fixed motion search range. Err in FIG. 6 is the absolute error of the frame between the current block (C) and another block (D) from the reference frame in the fixed motion search range.

As shown in step S8 of FIG. 4, the minimum prediction error (min_error) is set to a predetermined threshold value (Th).
(reshold), and if not, it is necessary to expand the motion search range as shown in step S9 in FIG. 4, and if so, it is not corrected as shown in step S10 in FIG. Put in.

FIG. 8 shows a detailed flow of steps S8, S9 and S10.

As shown in FIG. 8, after reaching the end of the motion search range, in the block in the current frame, in step S21, min1, min2, and mi are set for each of field 1, field 2, and the frame.
n is obtained, and then min1, min2 in step S22.
And min are threshold1, thr, respectively.
Compared to eshold2 and threshold. If min1 is smaller than threshold1 and at the same time min2 is smaller than threshold2 or min is smaller than threshold, MSR
The (motion search range) is not expanded (as shown in step S24) and proceeds to the next block, or the MSR is expanded (as shown in step S23).

FIG. 9 shows the predetermined threshold value and its correction.

Here, the threshold is slightly corrected by the relative deviation of the current block. When the deviation of a certain block is large, that is, in the high-detail area, particularly when the area includes a high-speed motion, the matching error (prediction error) is large. As shown, the relative deviation here must be corrected higher.

Dev is the standard deviation of the current block, d
ev_t is the total deviation of all blocks at that time, dev_a is the average deviation with respect to the number of blocks, and dev_m is a correction value obtained from dev and dev_a.

[0049]

(Equation 1)

[0050]

(Equation 2)

[0051]

(Equation 3) Here, num_mb is the number of blocks at this time.

The threshold is used to check a motion search range when performing frame motion estimation. t
Threshold1 and Threshold2 are used to check a motion search range when performing field motion estimation.

As shown in FIG. 9, in step S25, the deviation of the current block is calculated, and the result is indicated as dev.
The average deviation of the current block dev_a is calculated in steps S26 and S26.
27, and the correction value dev_m is obtained from step S28. threshold1, threshold
d2 and threshold are de at step S29.
Modified by v_m.

When the motion search range is expanded in step S11 of FIG. 4, the search for a matching block is continued within the expanded search range.

FIG. 10 shows an embodiment of motion estimation with an adaptive motion search range.

The input video is input to the system frame by frame, and the frame is then subdivided (at step S31) into many blocks of pixel data.

When the second frame arrives in step S32, the initial medium motion search range selected here +/-
Full pixel motion estimation is performed using 15 pixels. It is checked whether all the motion vectors generated for that frame are much less than a smaller value, for example +/− 8 pixels. If so, the motion search range is reset to a smaller value. If not, the motion search range is not modified. In step S33, half-pixel motion estimation is performed based on the motion vector obtained as a result of the full-pixel motion estimation. Further, motion compensation (S34), DCT (S35), quantization (S36),
Run-length encoding and VLC (S37) are performed on the frame. After step S37, the encoded stream is output.

FIG. 11 shows a detailed embodiment of the motion estimation in FIG.

When the third frame comes, full pixel motion estimation is performed using this reference motion search range (shown as M1 in FIG. 11). During coding of all blocks in the entire frame, it is checked whether the reference motion search range is sufficient (M2 in FIG. 11). If so, the motion estimation proceeds to another block. If not enough, the reference motion search range is expanded (M3 in FIG. 11), and a matching block is searched for in the expanded motion search range (M3 in FIG. 11).
4).

After the full pixel motion search range is complete, half pixel motion estimation, motion compensation, DCT, quantization, run length coding and VLC are performed as usual.

In FIG. 10, "inverse quantization" (S4
2), "Inverse DCT" (S41), and "Locally decoded frame memory" (S40) constitute a local decoder for motion compensation. "Rate control" (S43) allocates bits to each frame. "Frame interpolation" (S39) is for half-pixel motion estimation. "Reference frame memory" (S38)
Stores the last frame for motion estimation.

Further, in step S12 of FIG.
It is checked whether or not the motion estimation has been completed for the current frame. If completed, the process proceeds to step S13, and if not completed, the process returns to step S6. Step S13 in FIG.
In, the next frame is obtained, and the encoding time> = T_p
Check whether or not. If the encoding time> = T_p, FIG.
Returning to step S1, if the encoding time <T_p,
It returns to step S6.

The present encoding method has two major improvements over the prior art method where the motion search range is fixed throughout the encoding process. For very fast motions, a fixed motion search range is not enough to obtain a matching block, so adaptively expanding the motion search range improves the performance of motion estimation, and therefore the coding efficiency and image quality. Is improved. This improvement can be achieved with M, such as "marbles" and "fireworks".
Seen in the PEG test sequence.

For very slow motion or still scenes,
The encoding method adaptively reduces the search range to a smaller range (e.g., +/- 8 pixels), thereby saving most of the motion estimation processing time without compromising motion estimation accuracy. This improvement is found in the MPEG "Mobile &Calendar" test sequence.

Test experiments were performed on "marbles" and "fireworks" (60 frames) for a high-speed motion sequence, and "Mobile &Calendar" (60 frames) for a low-speed motion sequence. The following table shows only the results for fast motion.

[0066]

[Table 1] Prediction error of motion estimation The saved processing time% is a fixed motion search range (+
/ -30), the motion search range (+
/ -15 or +/- 30) means the percentage of processing time saved when motion estimation is performed.

From the above table, when the motion search range is fixed at +/− 15, the prediction errors are “marble” and “fireworks”.
It can be seen that “1373” and “2093” are extremely large, respectively. When the motion search range is fixed to +/− 30, the prediction errors are “809” and “160”, respectively.
8 ", but takes much longer processing time. When the motion search range is adaptively corrected to +/− 15 or +/− 30, the prediction error is almost the same as when using the motion search range fixed to +/− 30, and the processing time is the maximum. 51% and 48% savings.

The adaptive motion search range adjustment can perform better prediction in a shorter processing time.

[Brief description of the drawings]

FIG. 1 is an explanatory diagram showing a problem that occurs when a motion search range is fixed and a search range is too small to find a block that truly matches a current block.

FIG. 2 is an explanatory diagram illustrating a problem that occurs when a motion search range is fixed and wastes unnecessary processing time due to a very large motion search range.

FIG. 3 is a schematic diagram for explaining a method according to the present invention.

FIG. 4 is a schematic diagram for explaining a method according to the present invention.

FIG. 5 is an explanatory diagram showing how to find a matching block.

FIG. 6 is an explanatory diagram showing how to find a matching block.

FIG. 7 is an explanatory diagram showing calculation of a field error between two blocks.

FIG. 8 is an explanatory diagram showing a method of checking whether a motion search range is sufficient.

FIG. 9 is an explanatory diagram showing a method of determining and correcting a threshold value.

FIG. 10 is an explanatory diagram showing an encoder system with adaptive motion compensation based on MPEG2.

FIG. 11 is a detailed diagram illustrating the full pixel motion estimation of FIG. 10;

[Explanation of symbols]

A: current block A ': true matching block A ₀ ': block in the reference frame B: false matching block

 ──────────────────────────────────────────────────の Continuing on the front page (72) Inventor Chak Joo Lee Singapore 534415 Singapore, Thai Sen Avenue, Block 1022, 04-3530, Thai Sen Industrial Estate, Panasonic Singapore Research Institute, Inc. F term (reference) 5C059 KK19 MA05 MA23 MC11 MC38 ME01 ME05 NN03 NN15 NN24 NN28 PP04 TA63 TB04 TB08 TC03 TC11 TC13 TD03 TD04 TD12

Claims (7)

[Claims] 1. dividing a current frame of the input video signal into a number of blocks of pixel data; dividing a reference frame of the input video signal into a number of blocks of pixel data; Searching for a block that best matches the current block in the reference frame; detecting the motion content in the current frame; expanding the reference motion search range to an appropriate value if high-speed motion exists Reducing the reference motion search range to an appropriate value if there is no motion or low-speed motion. 2. The step of detecting a motion content includes obtaining a prediction error between the current block and the matched block, comparing the prediction error with a threshold value, and determining whether a high-speed motion exists. A step of enlarging the reference motion search range to an appropriate value when a high-speed motion exists in a frame; and a step of searching for a motion vector from the corrected search range. The video encoding method according to claim 1. 3. The reference motion search range includes: obtaining all motion vectors of a frame corresponding to a minimum prediction error; checking whether all of the motion vectors are smaller than a predetermined value; 3. The video encoding method according to claim 1, wherein the step of reducing the motion search range is performed when all of the values are smaller than the predetermined value. 4. Using a motion vector obtained from said motion estimation to find a corresponding matching block from a frame originating from a local decoder; and from the current block in the current frame and the decoded frame. A video code as claimed in any one of the preceding claims, comprising the steps of: generating a prediction error between the matching block of the video signal; and encoding the prediction error for transmission. Method. Calculating a standard deviation of the current block of pixel data; calculating an average standard deviation of the current block of pixel data; and calculating a correction value from the standard deviation and the average standard deviation of the current block. 3. The video encoding method according to claim 2, further comprising: modifying a predetermined threshold using the modification value. 6. The video encoding method according to claim 1, wherein the adjustment of the adaptive motion search range can be performed on a sequence basis, a frame basis, a microblock basis, and a region basis. 7. The video encoding method according to claim 1, wherein the motion search window indicating the adaptive motion search range may be a square, a circle, a rectangle, or any other shape.