KR100845644B1 - Fast motion mode decision method - Google Patents

Abstract

The present invention relates to a fast motion mode determination method. A fast motion mode determination method for performing a motion prediction and compensation process using at least one motion block type in video compression encoding, comprising: an object between an encoding target block and a reference block Calculating similarity with respect to the motion block type; comparing the calculated similarity with a preset threshold; determining similarity; and when the determination indicates that the similarity is high, the target motion block type is a motion estimation block type. And determining the final motion block type by comparing the calculated rate-distortion cost with each other. To speed up the process and more effectively Cattle can be.

Motion prediction, encoder

Description

FAST MOTION MODE DECISION METHOD}

1 is a diagram showing the structure of an encoder of MPEG-4 AVC | H.264 of the present invention;

2 is a diagram illustrating an MPEG-4 AVC | H.264 motion prediction variable block type form of the present invention.

3 is a diagram illustrating a screen in which a motion prediction block mode is determined in various block sizes.

4 is a diagram illustrating an example of a t-statistic distribution applied to an embodiment of the present invention.

5 is a diagram illustrating a current block and a reconstructed block to which statistical hypothesis verification is applied to successive frames for applying a fast motion determination method according to an embodiment of the present invention.

6 is a flowchart illustrating a method of determining a fast motion mode according to an embodiment of the present invention.

The present invention relates to a fast motion mode determination method, and more particularly, to a fast motion mode determination method capable of effectively shortening while minimizing image quality degradation and amount of bits generated during motion prediction using various motion blocks. It is about.

In general, the associative amount required for motion prediction has an absolute effect on the amount of computation required for the entire encoding.

For example, when the motion prediction is performed on one or more forward and backward reference frames such as the H.264 | AVC compression coding scheme, the complexity is very high, and in the case of the MPEG-4 AVC | H.264 compressed video structure, the temporal When motion prediction is performed using various blocks on hierarchical B-pictures for scalability, the complexity increases exponentially.

Therefore, there have been many obstacles in implementing a software real-time encoder, and there is a problem in that it is relatively dependent on hardware.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problems, and an object of the present invention is to provide a fast motion mode determination method that can effectively reduce the amount of computation by speeding up the motion prediction process that requires a large amount of computation in video encoding. have.

Another object of the present invention is to provide a fast motion mode determination method capable of effectively shortening while minimizing image quality degradation and amount of generated bits in a process of performing motion prediction using various motion blocks.

In order to achieve the above object, a first aspect of the present invention is a fast motion mode determination method for performing a motion prediction and compensation process using at least one motion block type in video compression encoding. Calculating a similarity between the pixels in the encoding target block and the pixels in the reference block for the block type; (b) comparing the calculated similarity with a preset threshold to determine similarity; (c) determining the target motion block type as the motion estimation block type when it is determined that the similarity is high as a result of the determination in step (b); (d) calculating the rate-distortion cost; And (e) determining the final motion block type by comparing the calculated rate-distortion cost.

Here, in the step (a), it is preferable to establish a statistical hypothesis for comparing the similarity in order to calculate the similarity between the pixel values in the encoding object block and the reference block, and to calculate a verification statistic for verifying the statistical hypothesis.

Preferably, a verification statistic is calculated for the similarity measure for at least one of mean and variance for pixel values in the current block and pixel values in the reference block.

Preferably, in constructing a statistical hypothesis for the test of similarity between pixel values in the current block and the reference block, the hypothesis for comparing the pixel values of the two blocks with respect to at least one of the mean and the variance is further established. Include.

Preferably, step (b) determines similarity by determining whether a test statistic exists within a given confidence interval for a hypothesis for using statistical hypothesis testing.

Preferably, the step (c) further comprises the step of early termination of the motion prediction and compensation process without performing the motion prediction and compensation process for the other motion block type.

Preferably, step (e) compares the rate-distortion cost for each motion estimation block type to determine the motion estimation block type that generates the minimum cost as the final motion block type.

A second aspect of the present invention provides a recording medium having recorded thereon a program for executing the above-described fast motion mode determination method.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. However, embodiments of the present invention illustrated below may be modified in many different forms, and the scope of the present invention is not limited to the embodiments described below. Embodiment of the present invention is provided to more fully explain the present invention to those skilled in the art.

First, an encoder using motion prediction for compressing image data can obtain a high compression rate, but a large amount of association is required for a motion estimation process for accurate motion prediction.

The encoder using such motion prediction uses various blocks for accurate motion prediction. For example, in the case of the H.264 | AVC compressed coder, there are seven types of block sizes for motion prediction: 16x16, 16x8, 8x16, 8x8, 8x4, 4x8, and 4x4.

That is, after performing the encoding process using all seven types in motion estimation, the motion estimation block type having the minimum weighting cost is determined as the final block type by the distortion degree and the generated bit amount of the original image and the reconstructed image. .

In this case, since the encoder performs motion prediction for all blocks, a large amount of association is required, which acts as a big obstacle to real-time software encoding. Accordingly, the present invention provides a fast motion mode determination method that can effectively reduce the amount of computation during encoding by more efficiently performing the conventional motion prediction process requiring an excessive amount of association.

Inter-screen motion prediction, on the other hand, uses block-based motion compensation to generate predictive models from one or more frames or fields before or after. For example, MPEG-4 AVC | H.264 uses a total of seven block sizes for motion prediction and motion compensation of variable block size.

In addition, one motion vector is measured for each block size, and the motion vector is measured and compensated with 1/4 pixel precision. Table 1 below shows the difference between the existing video coding standard and MPEG-4 AVC | H.264.

As shown in Table 1, a much higher amount of computation is required than a conventional video codec in order to increase MPEG-4 AVC | H.264 coding efficiency.

1 is a diagram showing the structure of an encoder of MPEG-4 AVC | H.264 of the present invention, wherein the encoder shows the use of a motion block mode for inter-screen motion prediction and compensation.

Referring to FIG. 1, an encoder of MPEG-4 AVC | H.264 is largely classified into coder control, transform / scaling / quantization, decoder, motion estimation, and motion estimation. And entropy coding are organically coupled to each other.

The decoder includes a scaling & inv. Transform, a deblocking filter, an intra-frame prediction, a motion compensation, and the like.

On the other hand, each of the above-described components are conventional, a detailed description thereof will be omitted.

The encoder of MPEG-4 AVC | H.264 configured as described above performs motion estimation and compensation for all seven block types, and compares the rate-distortion (RD) cost for each of the minimum values. The block mode indicating is determined as the final block mode. By doing so, a large amount of computation is required at the time of encoding.

FIG. 2 is a diagram illustrating an MPEG-4 AVC | H.264 motion prediction variable block type according to the present invention, and shows blocks having various sizes that are hierarchically divided.

Referring to FIG. 2, there are blocks having relatively large sizes such as 16x16, 16x8, 8x16, and 8x8 in the first level, and blocks having small sizes such as 8x8, 8x4, 4x8, and 4x4 in the lower level.

The difference from previous video codec standards is that it supports multiple block sizes (16x16, 16x8, 8x16, 8x8, 8x4, 4x8 and 4x4) and subsample motion vectors with 1/4 precision. In previous video coding standards, motion vectors were measured in units of 16 × 16 macroblocks.

However, since the 16x16 macroblock alone does not reflect the motion and texture characteristics of various objects, the MPEG-4 AVC | H.264 video standard uses the seven block modes to reflect the characteristics of the content.

In other words, a large block size, such as a 16x16 block, is allocated to an area with little or no homogeneous characteristics, and a sub macro block with a small block size, such as 8x8 to 4x4, has a large area or a fine texture. It is assigned to the area showing the characteristic.

The determination of this block size follows the principle of finding the rate-distortion (RD) cost for all blocks and assigning the block with the smallest rate-distortion cost.

3 is a diagram illustrating a screen in which a motion prediction block mode is determined in various block sizes.

Referring to FIG. 3, the amount of computation increases rapidly with mode determination and motion vector determination with various block sizes. This is because there is a motion vector for each block, and the complexity of calculating the rate-distortion cost for all seven blocks in order to determine the block size in one macro block is large. This is because at the cost of increasing the amount of computation in order to maximize the coding efficiency.

For example, in MPEG-4 AVC | H.264, the inter-screen mode determination determines a block that minimizes Equation 1 as an optimal block.

으로 계산된다. 그리고, SSD는 원 영상과 복원된 영상간의 왜곡도를 나타내며 클수록 왜곡이 심하며 모드 결정이 잘못된 것을 의미한다.Here, s means original image and c means reconstructed image. Q _p denotes a quantization parameter used when determining a motion vector and an interframe mode. λ _mode is the Lagrangian coefficient

Is calculated. In addition, the SSD represents a degree of distortion between the original image and the reconstructed image, and the larger the value, the more severe the distortion and the incorrect mode decision.

In addition, MPEG-4 AVC | H.264 is designed to select an optimal block from a plurality of reference pictures during inter prediction. This is for the purpose of increasing the coding efficiency by using several reference pictures, but the amount of computation increases rapidly since motion vectors for seven block types have to be estimated from the plurality of reference pictures.

A key technical aspect of the present invention is to provide a fast motion determination method capable of speeding up an operation at the time of encoding by effectively performing a complicated motion prediction mode and rapidly reducing the amount of computation. It is easy to achieve the purpose.

The present invention is described as an example of the MPEG-4 AVC | H.264 (ISO / IEC 14496-10) video compression standard. However, the scope of the present invention is not limited to the MPEG-4 AVC | H.264 (ISO / IEC 14496-10) video compression standard, and any video compression method that makes a motion mode determination using at least one or more motion blocks. It is also applicable to the method.

First, in order to use this hypothesis testing method in the fast interframe mode determination method of SVC (Scalable Video Coding), X _C and X _R are called independent normal populations as random variables representing pixel values of the current block and the reference block, respectively. It is assumed and defined as in Equation 2 below.

Here, μ _c and μ _R represent the average of the random values of the pixel values of the current block and the reference block, respectively, and assume that these values are already known, and hypothesis verification is performed as in Equation 3 below.

Here, H ₀ is called a null hypothesis and determines whether pixel values of the current block and the reference block are from the same population. If the set null hypothesis is accepted, the two groups of pixels in the current block and the restored reference block are determined to be from the same population, and the mode is determined by the size of the block currently being tested.

을 현재 블록과 참조 블록 내 픽셀들의 샘플 평균과 분산이라고 하자. 이때, 알려지지 않은 모집단의 분산이 같다고 가정하고, 상기의 수학식 3에 대하여 가설 검증을 실시한다. 두 평균에 대하여 귀무가설을 테스트하기 위해 다음과 같은 t 통계 분포를 사용한다. 이때, 자유도

(n₁ 및 n₂는 매크로 블록 의 수)를 가진 t 통계 분포는 하기의 수학식 4 및 수학식 5와 같다.

Let be the sample mean and variance of the pixels in the current block and the reference block. At this time, it is assumed that the variance of the unknown population is the same, and the hypothesis test is performed with respect to Equation 3 above. To test the null hypothesis for two means, we use the following t-statistic distribution: Where the degrees of freedom

The t statistical distribution with (n ₁ and n ₂ are the number of macro blocks) is as shown in Equations 4 and 5 below.

는 두 개의 샘플 집단을 대표하는 분산으로 공분산이라고 한다. 일단 t 통계 분포가 생성되면, α를 갖는 신뢰 구간(Confidence Interval)을 설정하여, 구간 내에 t 통계 분포가 존재하면, 즉,

이면 귀무가설을 받아들이고(H₀ accepted), 그렇지 않을 경우 받아들이지 않는다(H₀ rejected).here,

Is a variance representing two sample populations and is called covariance. Once the t statistic distribution is generated, a confidence interval with α is set so that if there is a t statistic distribution in the interval, i.e.

If so, the null hypothesis is accepted (H ₀ accepted), otherwise it is not accepted (H ₀ rejected).

4 is a diagram illustrating an example of a t-statistic distribution applied to an embodiment of the present invention. Once a confidence interval is set and a t-test statistic using the variance of the sample is within the confidence interval, the mean of the two populations is the same. To judge.

The following is a hypothesis test method for variance. Like hypothesis test for two means, hypothesis test is performed for two variances. As in Equation 3, the null hypothesis for variance is set as in Equation 6 below.

The z statistical distribution is used to test the hypotheses (H ₀ , H ₁ ) for these two variances. The z statistical distribution is defined as in Equation 7 below.

Here, S _{p, which} is a prediction value of the common standard deviation, is defined as in Equation 8 below.

And, the z statistical distribution generally follows a normal distribution. This also sets the confidence interval and computes the z-validation statistics for verifying that each variance of the pixel values of the two blocks (the current block and the reference block) is equal to each other and, if it is in the confidence interval, accepts the null hypothesis Otherwise it will not be accepted.

Here, both the null hypothesis for the mean and the variance are accepted, but because the current block and the reference block are considered to be matched blocks from the same population, the current block is estimated without measuring the motion vector and determining the mode for the current block and the lower block. The mode decision process is completed early by selecting 16x16 blocks or 8x8 blocks.

Hereinafter, a method of determining an inter-frame fast block mode according to an embodiment of the present invention will be described in detail.

First, the fast block mode determination method for reducing the amount of computation is based on the statistical hypothesis verification test described above. The block mode determination method proposed in the present invention follows the following process.

Step 1: If the current block is P-picture prediction, skip mode (SKIP Mode) first, if B prediction, direct mode (Direct Mode).

Step 2: Measure the motion vector for the 16x16 macroblock.

Step 3: Perform statistical hypothesis testing of mean and variance on the optimal reconstructed reference macro block and the current block moved using the motion vector.

Step 4: If both hypotheses and variance tests are passed, the current block compares the 16x16 block with the direct or skip mode to determine the best mode and completes the mode decision process. If not, proceed to Step 5.

Step 5: Measure motion vectors for 16x8, 8x16, and 8x8 blocks based on the rate-distortion (RD) optimization method.

Step 6: Test the statistical hypothesis test of mean and variance for each 8x8 block.

Step 7: If the hypothesis verification passes for each 8x8 block, the current block is determined to be an 8x8 block, and completes the mode decision process for the 8x8 subblock. Otherwise go to step 8.

Step 8: Perform motion vector measurement and mode determination on 8x4, 4x8, and 4x4 blocks based on the rate-distortion (RD) optimization method.

Step 9: Proceed with mode determination for the next macro block.

In step 2, a reference block for hypothesis testing is found by estimating a motion vector having a minimum rate-distortion cost. That is, the hypothesis verification test is performed between the current block and the reference block by finding out which frame the macroblock is among the multiple reference frames. FIG. 5 illustrates a current block and a reconstructed block to which statistical hypothesis verification is applied to successive frames for applying the fast motion determination method according to an embodiment of the present invention.

On the other hand, the skip mode (SKIP Mode) and the direct mode (Direct Mode) of the above process 1 is a conventional technique, a detailed description thereof will be omitted (Korean Patent Publication No. 2005-98243 (enhanced coding mode selection) Method and device)).

6 is a flowchart illustrating a method of determining a fast motion mode according to an embodiment of the present invention.

Referring to FIG. 6, first, an input image step S100 of using a reference frame as an input image with respect to a current frame (macro block) of the input image, and skip (SKIP) / direct (Direct) and 16x16 mode motion prediction and compensation Step S101, skip / direct mode, and 16x16 mode rate-distortion (RD) cost calculation step (S102), 16x16 mode hypothesis verification step (S103), and confidence intervals of hypothesis verification statistics exist Whether or not the determination step (S104), the 16x8, 8x16 and 8x8 mode motion prediction and compensation step (S105), the 16x8, 8x16 and 8x8 mode rate-distortion (RD) cost calculation step (S106), and the 8x8 mode rate-distortion cost 8x8 mode hypothesis verification step (S107), the existence of the confidence interval of the hypothesis test statistics (S108), 8x4, 4x8 and 4x4 mode motion prediction and compensation step (S109), 8x4, 4x8 And 4x4 mode rate-distortion (RD) cost calculation step (S110), minimum rate-distortion (RD) cost determination and final motion block. Mode determining step (S111) are linked is continuously performed.

As described above, in the determination of the motion mode, when performing the hypothesis verification on the 16x16 block (S104), the final motion mode is determined as the 16x16 motion block when the verification statistic value exists within a given confidence interval, thereby making the motion mode prediction and compensation process. Will finish early. In this case, a large amount of computation can be reduced because the motion prediction and compensation processes for the lower 16x8, 8x16, and 8x8 motion blocks are not required.

If the verification statistic value does not exist within the given confidence interval, after performing the motion prediction and compensation process for the 16x8, 8x16 and 8x8 blocks (S105), the rate-distortion cost is calculated (S106).

Here, when the 16x8 or 8x16 motion block mode generates a minimum rate-distortion cost value, the final motion block mode is determined as the 16x8 or 8x16 motion block mode (S107).

However, if the 8x8 motion block generates a minimum rate-distortion cost value, a hypothesis verification process is performed (S108). If the verification statistics value exists in the confidence interval, the 8x8 motion block mode is determined as the final motion block mode. The motion prediction and compensation process ends (S111). In this case, a large amount of computation can be reduced because the motion prediction and compensation process for the lower 8x4, 4x8 and 4x4 motion blocks is not required.

If the verification statistic value does not exist within the given confidence interval, after performing the motion prediction and compensation process for the 8x4, 4x8 and 4x4 blocks (S109), the rate-distortion cost value is calculated (S110). Here, the block that generates the minimum rate-distortion cost value is determined as the final motion mode.

On the other hand, the fast motion mode determination method according to an embodiment of the present invention can also be implemented as computer-readable code on a computer-readable recording medium. The computer-readable recording medium includes all kinds of recording devices in which data that can be read by a computer system is stored.

For example, a computer-readable recording medium may be a ROM, a RAM, a CD-ROM, a magnetic tape, a hard disk, a floppy disk, a removable storage device, a flash memory. Optical data storage, and the like, and also implemented in the form of a carrier wave (eg, transmission over the Internet).

The computer readable recording medium can also be distributed over computer systems connected over a computer network so that the computer readable code is stored and executed in a distributed fashion.

While a preferred embodiment of the method for determining a high speed motion mode according to the present invention has been described above, the present invention is not limited thereto, and various modifications are made within the scope of the claims and the detailed description of the invention and the accompanying drawings. It is possible and this also belongs to the present invention.

According to the fast motion mode determination method of the present invention as described above, there is an advantage that the amount of calculation can be effectively reduced by speeding up the motion prediction process that requires a large amount of calculation in video encoding.

In addition, according to the present invention, there is an advantage that the process of performing motion prediction using various motion blocks can be effectively shortened while minimizing image quality deterioration and amount of generated bits.

In addition, according to the present invention, by reducing the excessive amount of operations required for the motion prediction and compensation process in the encoding process, there is an advantage that can meet the high-speed processing requirements that are important in designing a real-time software encoder by improving the encoding processing speed.

Claims (8)

A fast motion mode determination method for performing motion prediction and compensation using at least one motion block type in video compression encoding. (a) calculating the similarity between the pixels in the encoding target block and the pixels in the reference block for the given target motion block type; (b) comparing the calculated similarity with a preset threshold to determine similarity; (c) determining the target motion block type as the motion estimation block type when it is determined that the similarity is high as a result of the determination in step (b); (d) calculating the rate-distortion cost; And (e) determining a final motion block type by comparing the calculated rate-distortion cost. The method of claim 1, wherein step (a) A statistical hypothesis for similarity comparison is established to calculate the similarity between pixel values in a block to be encoded and a reference block, and a verification statistic for verifying the statistical hypothesis is calculated. 3. The method of claim 2, wherein a verification statistic is calculated for a similarity measure for at least one of mean and variance for pixel values in the current block and pixel values in the reference block. 3. The process of claim 2, wherein in the statistical hypothesis for the test of similarity between pixel values in the current block and the reference block, a hypothesis for comparing pixel values of two blocks with respect to at least one of an average and a variance. The fast motion mode determination method further comprises. The method of claim 1, wherein step (b) comprises: A method for determining a fast motion mode, characterized in that for a hypothesis for using statistical hypothesis testing, a similarity is determined by determining whether a verification statistic exists in a given confidence interval. The method of claim 1, wherein in step (c), And prematurely terminating the motion prediction and compensation process without performing the motion prediction and compensation process for the other motion block types. The method of claim 1, wherein step (e) And comparing the rate-distortion cost for each motion estimation block type to determine a motion estimation block type that generates the minimum cost as the final motion block type. A computer-readable recording medium having recorded thereon a program capable of executing the method of any one of claims 1 to 7.

Images