Method and apparatus for fast mode decision for interframes

There is disclosed a video encoder and corresponding method for encoding video data for an image block. The video encoder performs a mode decision by performing initial motion estimation on only a subset of possible block sizes to output motion information corresponding thereto, and determining, based upon the motion information corresponding to only the subset of possible of block sizes and upon other image-related analysis data, whether other block sizes are to be evaluated.

FIELD OF THE INVENTION

The present invention relates generally to video encoders and, more particularly, to a method and apparatus for fast mode decision for interframes.

BACKGROUND OF THE INVENTION

Inter and intra coding methods can both be used to encode interframes in accordance with various video compression standards. Intra coding uses only spatial correlation while inter coding uses temporal correlation from previously coded frames. In general, inter coding is used for macroblocks that are well predicted from previous pictures, and intra coding is used for macroblocks that are not well predicted from previous pictures, or for macroblocks with low spatial activity.

Typically, an encoder makes an inter/intra coding decision for each macroblock based on coding efficiency and subjective quality considerations. In the JVT/H.264/MPEG AVC (“JVT”) standard, inter coding allows various block partitions and multiple reference pictures to be used for predicting a 16×16 macroblock.

The JVT encoder uses tree-structured hierarchical macroblock partitions. Inter-coded 16×16 pixel macroblocks may be broken into macroblock partitions, of sizes 16×8, 8×16, or 8×8. Macroblock partitions of 8×8 pixels are also known as sub-macroblocks. Sub-macroblocks may be further broken into sub-macroblock partitions, of sizes 8×4, 4×8, and 4×4. An encoder may select how to divide the macroblock into partitions and sub-macroblock partitions based on the characteristics of a particular macroblock, in order to maximize compression efficiency and subjective quality.

Multiple reference pictures may be used for inter-prediction, with a reference picture index coded to indicate which of the multiple reference pictures is used. In P pictures (or P slices), only single directional prediction is used, and the allowable reference pictures are managed in list0. In B pictures (or B slices), two lists of reference pictures are managed, list0and list1. In B pictures (or B slices), single directional prediction using either list0or list1is allowed, or bi-prediction using both list0and list1is allowed. When bi-prediction is used, the list0and the list1predictors are averaged together to form a final predictor.

Each macroblock partition may have an independent reference picture index, prediction type (list0, list1, bipred), and an independent motion vector. Each sub-macroblock partition may have independent motion vectors, but all sub-macroblock partitions in the same sub-macroblock use the same reference picture index and prediction type.

For inter-coded macroblocks, besides the above macroblock partition, P frame also supports SKIP mode, while B frame supports both SKIP mode and DIRECT mode. In SKIP mode, no motion and residual information are encoded. The motion information for a SKIP macroblock is the same as a motion vector predictor specified by the picture/slice type (P or B), and other information such as sequence and slice level parameters, and is related to other temporally or spatial adjacent macroblocks and its own macroblock position within the slice. In contrast, in DIRECT mode, no motion information is encoded, but prediction residue is encoded. Both macroblocks and sub-macroblocks support DIRECT mode.

As for mode decision, inter pictures need to support both inter and intra modes. Intra modes include INTRA4×4 and INTRA16×16. For P pictures, inter modes include SKIP and 16×16, 16×8, 8×16 and sub-macroblock 8×8 partitions. 8×8 further supports 8×8, 8×4, 4×8 and 4×4 partitions. For B pictures, both list0and list1and DIRECT mode are considered for both macroblocks and sub-macroblocks.

In the prior art, a Rate-Distortion Optimization (RDO) framework is used for mode decision. For inter modes, motion estimation is separately considered from mode decision. Motion estimation is first performed for all block types of inter modes, then the mode decision is made by comparing the cost of each inter mode and intra mode. The mode with the minimal cost is selected as the best mode.

A conventional procedure to encode one macroblock s in a P- or B-picture (hereinafter the “conventional macroblock encoding procedure”) is summarized as follows.

In a first step of the conventional macroblock encoding procedure, given the last decoded pictures, we decide the Lagrangian multiplier λMODE, λMOTION, and the macroblock quantizer QP.

In a second step of the conventional macroblock encoding procedure, motion estimation and reference picture selection are performed by minimizing
J(REF,m(REF)|λMOTION)=SA(T)D(s,c(REF,m(REF)))+λMOTION(R(m(REF)−p(REF))+R(REF))
for each reference picture and motion vector of a possible macroblock mode. In the preceding equation, m is the current motion vector being considered, REF denotes the reference picture, p is the motion vector used for the prediction during motion vector coding, R(m−p) represents the bits used for coding motion vector and R(REF) is the bits for coding reference picture. SAD denotes the Sum of Absolute Differences between original signal and reference signal predicted by the motion vector.

In a third step of the conventional macroblock encoding procedure, the macroblock prediction mode is chosen by minimizing
J(s,c,MODE|QP,λMODE)=SSD(s,c,MODE|QP)+λMODE·R(s,c,MODE|QP),
given QP and λMODEwhen varying MODE. SSD denotes the Sum of Square Differences between the original signal and the reconstructed signal. R(s,c,MODE) is the number of bits associated with choosing MODE, including the bits for the macroblock header, the motion and all DCT coefficients. MODE indicates a mode out of the set of potential macroblock modes:

With respect to the conventional macroblock encoding procedure, a conventional fast mode selection was introduced which could considerably reduce the complexity of mode decision while having little impact in quality by considering that the mode decision error surface is more likely to be monotonic and therefore if certain modes are examined first it might be simpler to find the best mode. If mode decision for a given mode is not performed, then this essentially implies that motion estimation also is not performed, the latter being the most costly part of encoding even if a fast motion estimation algorithm is used. More specifically, in this approach SKIP and 16×16 modes were examined first. According to their distortion relationship (i.e. (J(SKIP)<J(16×16)) and the availability of residual, a further decision was made whether or not to terminate the search. Otherwise, J(8×8) and J(4×4) were also computed. Based on the relationship of J(16×16), J(8×8), and J(4×4), additional decisions were made to determine which of the remaining block sizes should be tested. For example, if the distortion is monotonic (i.e., J(16×16)>J(8×8)>J(4×4) or J(16×16)<J(8×8)<J(4×4)), then it can easily be determined which additional partitions should be examined. For the first case, for example, only small partitions (8×4 and 4×8) are tested, while in the second case only 16×8 and 8×16 are examined. If the distortion is not monotonic, then all possible modes are tested.

In a different conventional fast mode decision approach, additional conditions were introduced based on the distortion values (seeFIG. 1below) and the relationships between different modes (seeFIG. 2below), which allowed the search to terminate even faster without much impact in quality.

Turning toFIG. 1, a method for motion vector and mode decision based on distortion values is generally indicated using the reference numeral100. The method100includes a start block102that passes control to a function block104. The function block104checks SKIP mode and 16×16 mode, and passes control to a decision block106. The decision block106determines whether or not the distortion in SKIP mode, J(SKIP), is less than the distortion in 16×16 mode, J(16×16), and whether or not 16×16 mode has any residue. If the distortion in SKIP mode is not less than the distortion in 16×16 mode and/or 16×16 mode has a residue, then control is passed to a function block108. Otherwise, if the distortion in SKIP mode is less than the distortion in 16×16 mode and 16×16 mode has no residue, then control is passed to a decision block126.

The function block108checks 8×8 mode for a current (i.e., currently evaluated) 8×8 sub-partition, and passes control to a decision block110and to a function block114. The decision block110determines whether or not 8×8 mode has the same motion information as 16×16 mode for the current 8×8 sub-partition. If 8×8 mode does not have the same motion information as 16×16 mode for the subject sub-partition, then control is passed to a function block112. Otherwise, if 8×8 mode has the same motion information as 16×16 mode for the current 8×8 sub-partition, then control is passed to a function block114.

The function block112checks 16×8 and 8×16 sub-partitions, and passes control to function block114.

The function block114checks 4×4 mode for a current 4×4 sub-partition, and passes control to a decision block116and to a function block120. The decision block116determines whether or not 4×4 mode has the same motion information as 8×8 mode for the current 4×4 sub-partition. If 4×4 mode does not have the same motion information as 8×8 mode for the current 4×4 sub-partition, then control is passed to a function block118. Otherwise, if 4×4 mode has the same motion information as 8×8 mode for the current 4×4 sub-partition, then control is passed to a function block120.

The function block118checks 8×4 and 4×8 sub-partitions, and passes control to function block120.

The function block120checks intra modes, and passes control to a function block122. The function block122selects the best mode from among the evaluated modes, and passes control to an end block124. The end block124ends the macroblock encoding.

The decision block126determines whether or not SKIP mode has the same motion information as 16×16 mode for a current (i.e., currently evaluated) 16×16 MB. If SKIP mode does not have the same motion information as 16×16 mode for the current 16×16 MB, then control is passed to decision block108. Otherwise, if SKIP mode has the same motion information as 16×16 mode for the current 16×16 MB, then control is passed to function120.

Turning toFIG. 2, a method for motion vector and mode decision based on relationships between different modes is generally indicated using the reference numeral200. The method200includes a start block202that passes control to a function block204. The function block204checks SKIP mode and 16×16 mode, and passes control to a decision block206. The decision block206determines whether or not MC2>T1, where MC2=min(J(SKIP), J(16×16)), the minimum distortion between SKIP mode and 16×16 mode, and T1is the first threshold. If MC2<=T1, then control is passed to a decision block208. Otherwise, if MC2>T1, then control is passed to a function block210and a function block212.

The decision block208determines whether or not MC2 is greater than T2(a second threshold). If MC2 is not greater than T2, then control is passed to function block210and function block212. Otherwise, if MC2 is greater than T2, then control is passed to a function block218.

The function block210checks other inter modes, and passes control to a function block212. The function block212checks other non-tested intra modes, and passes control to a function block214. The function block214selects the best mode from among the evaluated modes, and passes control to an end block216. The end block216ends the macroblock encoding.

The function block218checks the intra4×4 DC, and passes control to a decision block220. The decision block220determines whether or not J(INTRA4×4 DC) is less than a*MC2+b, where a and b are constants. If J(INTRA4×4 DC) is not less than a*MC2+b, then control is passed to function block210and function block212. Otherwise, if J(INTRA4×4 DC) is less than a*MC2+b, then control is passed to the function block212.

In another different conventional fast mode decision approach, a picture was first analyzed using simple methods such as homogeneity analysis and stationarity detection. Homogeneity analysis can be performed by considering simple statistical measurements such as standard deviation or variance, skewness and kyrtosis. Unfortunately, these metrics might not be as appropriate for real time implementations. The determination of which modes should be considered was also somewhat based on a yet different conventional approach using a fast intra decision and, in particular, relating to edge direction. A method relating to the approach that uses homogeneity analysis and stationarity detection can be seen inFIG. 3, where modes 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, and 4×4 are sequentially assigned to modes1through7.

Turning toFIG. 3, a method for mode decision using homogeneity and stationarity is generally indicated using the reference numeral300. The method300includes a start box302that passes control to a function block304. The function block304performs edge detection, and passes control to a function block306. The function block306performs fast intra mode decision, and passes control to a function block308. The function block308sets mode1to mode7flags, and passes control to a decision block310. The decision block310determines whether or not a subject (i.e., currently evaluated) 16×16 macroblock (MB) has zero motion. If the 16×16 MB does not have zero motion, then control is passed to a decision block312. Otherwise, if the 16×16 MB does have zero motion, then control is passed to a function block318.

The decision block312determines whether or not the 16×16 MB is homogenous. If the 16×16 MB is not homogenous, then control is passed to a decision block314. Otherwise, if the 16×16 MB is homogenous, then control is passed to a function block328.

The decision block314determines whether or not each 8×8 sub-block of the 16×16 block is homogenous. If each 8×8 sub-block is not homogenous, then control is passed to a decision block316. Otherwise, if each 8×8 sub-block is homogenous, then control is passed to a function block332.

The decision block316determines whether or not a subject 8×8 sub-block is the last sub-block in the 16×16 MB. If the 8×8 sub-block is not the last sub-block in the 16×16 MB, then control is returned to step314. Otherwise, if the 8×8 sub-block is the last sub-block in the 16×16 MB, then control is passed to a function block324. The function block324performs motion estimation on different block sizes only for modes that have set flags, and passes control to an end block326. The end block326ends the macroblock encoding.

The function block318computes the MB difference, and passes control to a decision block320. The decision block320determines whether or not the MB difference is less than a pre-specified threshold. If the MB difference is not less than a pre-specified threshold, then control is passed to step312. Otherwise, if the MB difference is less than a pre-specified threshold, then control is passed to a function block322.

The function block322clears all mode flags except mode1, and passes control to the function block324.

The function block328clears all mode4,5,6, and7flags, and passes control to a function block330. The function block330clears the mode2flag when intra vertical prediction is selected, clears the mode3flag when intra horizontal prediction is selected, otherwise clears modes2and3, and then passes control to the function block324.

The function block332clears the mode5,6, and7flags for the 8×8 sub-block, and passes control to the decision block316.

Inter mode decision is associated with motion estimation, various block sizes and multiple reference picture selection. Intra mode decision is associated with various block types and multiple spatial prediction mode selection. Therefore, mode decision for interframes incurs a big burden on the encoder.

Accordingly, it would desirable and highly advantageous to have a method and apparatus for performing a fast mode decision for interframes that lessens the burden on the encoder.

SUMMARY OF THE INVENTION

These and other drawbacks and disadvantages of the prior art are addressed by the present invention, which is directed to a method and apparatus for fast mode decision for interframes.

According to an aspect of the present invention, there is provided a video encoder for encoding video data for an image block. The video encoder includes an encoder for performing a mode decision by performing initial motion estimation on only a subset of possible block sizes to output motion information corresponding thereto, and determining, based upon the motion information corresponding to only the subset of possible of block sizes and upon other image-related analysis data, whether other block sizes are to be evaluated.

According to another aspect of the present invention, there is provided a method for encoding video data for an image block. The method include the step of performing a mode decision by performing initial motion estimation on only a subset of possible block sizes to output motion information corresponding thereto, and determining, based upon the motion information corresponding to only the subset of possible of block sizes and upon other image-related analysis data, whether other block sizes are to be evaluated.

DETAILED DESCRIPTION

The present invention is directed a method and apparatus for fast mode decision for interframes. Advantageously, the present invention reduces mode decision complexity, while at the same time maintaining coding efficiency, as compared to prior art approaches to fast mode decision for interframes.

The present description illustrates the principles of the present invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope.

Herein, a novel method and apparatus are provided that, in part, utilize certain aspects of conventional approaches in a novel combination to further reduce the complexity of mode decision. The present invention can provide an improvement in performance over related prior art approaches. For example, in one embodiment of the present invention, improved performance over related prior art approaches is achieved by considering the error surface monotonicity. Moreover, the present invention can provide an improvement in efficiency over related prior art approaches. For example, it is observed that in one related prior art approach that uses homogeneity conditions, all modes need to be checked if no homogeneity condition is satisfied. In contrast to that prior art approach, the present invention may examine first only 16×16, 8×8, and 4×4 modes, and check the appropriate modes based on, e.g., the conditions specified in another conventional approach and/or other conditions specified herein. An example of such an implementation can be seen inFIG. 5. It is to be noted that edge information is used for the mode decision, as this metric may be better for real-time implementations than metrics such as standard deviation or variance, skewness, and kyrtosis. Of course, these and other metrics may also be employed by the present invention, while maintaining the scope of the present invention.

Turning toFIG. 4, an encoder for encoding video data is indicated generally by the reference numeral400.

An input to the encoder400is connected in signal communication with a non-inverting input of a summing junction410. The output of the summing junction410is connected in signal communication with a block transformer420. The transformer420is connected in signal communication with a first input of a quantizer430. The output of the quantizer430is connected in signal communication with a variable length coder (“VLC”)440, where the output of the VLC440is an externally available output of the encoder400. A first input of a rate controller477is connected in signal communication with the output of the summing junction410, a second input of the rate controller477is connected in signal communication with the output of the VLC440, and an output of the rate controller477is connected in signal communication with a second input of the quantizer430.

The output of the quantizer430is further connected in signal communication with an inverse quantizer450. The inverse quantizer450is connected in signal communication with an inverse block transformer460, which, in turn, is connected in signal communication with a reference picture store470. A first output of the reference picture store470is connected in signal communication with a first input of a motion estimator480. The input to the encoder400is further connected in signal communication with a second input of the motion estimator480. The output of the motion estimator480is connected in signal communication with a first input of a motion compensator490. A second output of the reference picture store470is connected in signal communication with a second input of the motion compensator490. The output of the motion compensator490is connected in signal communication with an inverting input of the summing junction410.

In the event that the encoder400is a transcoder or is used with a transcoder, then the transcoder may extract motion vectors from pre-coded bitstreams.

The approach employed inFIG. 5will now be described generally, followed by a more detailed description thereof with respect to the method steps illustrated inFIG. 5.

SKIP mode and 16×16 mode are first tested. If the minimum distortion is below a threshold T1, or SKIP mode and 16×16 mode have the same motion vectors and 16×16 mode has no residual, then the mode search may be terminated immediately. Otherwise, homogeneity conditions are examined. If 16×16 mode is homogeneous, then only 8×16 mode or 16×8 mode may need to be tested depending on edge information (i.e., for vertical edges, test 8×16 mode; for horizontal edges, test 16×8 mode—otherwise, terminate mode decision). If 16×16 is not homogeneous, the 8×8 mode and, if applicable, the 16×8 mode and the 8×16 mode are also tested. If the minimum distortion is below a threshold T2, then the mode search may again be terminated and the mode with the minimum distortion may be selected as the best mode. Otherwise, for each 8×8 sub-partition, the homogeneity condition is again applied. If an 8×8 sub-partition is found to be homogeneous, then no additional mode search is needed. Otherwise, the 4×4 mode for the current sub-partition is also checked. Examining 8×4 and 4×8 sub-partitions can be decided based on thresholding parameters or the relationship of 4×4 mode with respect to 8×8 mode (i.e., if 4×4 MVs are different from 8×8 MVs). When all 8×8 sub-partitions are tested, the search of all modes can be terminated.

Turning toFIG. 5, a method for mode decision is generally indicated using the reference numeral500. The method500includes a start block502that passes control to a function block504. The function block504performs edge detection, and passes control to a function block506. The function block506performs fast intra mode decision, and passes control to a function block508. The function block508sets all mode flags, and passes control to a function block510. The function block510checks SKIP mode and 16×16 mode, and passes control to a decision block512. The decision block512determines, for a current (i.e., currently evaluated) 16×16 macroblock (MB), whether or not the distortion in SKIP mode, J(SKIP), is less than the distortion in 16×16 mode, J(16×16), and that 16×16 mode has no residue. If the distortion in SKIP mode is not less than the distortion in 16×16 mode and/or 16×16 mode has a residue, then control is passed to a decision block514. Otherwise, if the distortion in SKIP mode is less than the distortion in 16×16 mode and 16×16 mode has no residue, then control is passed to a decision block528.

The decision block514determines whether or not the minimum distortion (MinJ) is less than a pre-specified threshold T1. If MinJ is not less than T1, then control is passed to a decision block516. Otherwise, if MinJ is less than T1, then control is passed to a function block530.

The decision block516determines whether or not the 16×16 MB is homogenous. If the 16×16 MB is not homogenous, then control is passed to a function block518. Otherwise, if the 16×16 MB is homogenous, then control is passed to a function block534.

The function block518checks 8×8 mode for a current (i.e., currently evaluated) 8×8 sub-partition of the 16×16 MB, and passes control to a decision block536and also to a decision block520.

The decision block536determines whether or not 8×8 mode has the same motion information as 16×16 mode for the current 8×8 sub-partition. If 8×8 mode does not have the same motion information as 16×16 mode for the current 8×8 sub-partition, then control is passed to a function block538. Otherwise, if 8×8 mode has the same motion information as 16×16 mode for the current 8×8 sub-partition, then control is passed to decision block520.

The function block538checks the 16×8 and 8×16 sub-partitions, and passes control to decision block520.

The decision block520determines whether or not the minimum distortion (MinJ) is less than a pre-specified threshold T2. If MinJ is not less than T2, then control is passes to a decision block522. Otherwise, if MinJ is less than T2, then control is passes to function block530.

The decision block522determines, for each 8×8 sub-partition of the 16×16 MB, whether that 8×8 sub-partition is homogenous. If a current 8×8 sub-partition is not homogenous, then control passes to a function block524. Otherwise, if the current 8×8 sub-partition is homogenous, then control passes to a function block526.

The function block524checks 4×4 mode for a current 4×4 sub-partition of the 16×16 MB, and passes control to a decision block540and also to a decision block526.

The decision block540determines whether or not 4×4 mode has the same motion information as 8×8 mode for the current 4×4 sub-partition. If 4×4 mode does not have the same motion information as 8×8 mode for the subject 4×4 sub-partition, then control is passed to a function block542. Otherwise, if 4×4 mode has the same motion information as 8×8 mode for the current 4×4 sub-partition, then control is passed to decision block526.

The decision block526determines whether or not the current 8×8 sub-partition is the last 8×8 sub-partition included in the 16×16 MB. If the current 8×8 sub-partition is not the last 8×8 sub-partition included in the 16×16 MB, then control is passed to decision block522. Otherwise, if the subject 8×8 sub-partition is the last 8×8 sub-partition included in the 16×16 MB, then control is passed to a function block530.

The decision block528determines whether or not SKIP mode has the same motion information as 16×16 mode for the 16×16 MB. If SKIP mode does not have the same motion information as 16×16 mode for the 16×16 MB, then control is passed to decision block514. Otherwise, if SKIP mode has the same motion information as 16×16 mode for the 16×16 MB, then control is passed to function530.

The function block534checks 8×16 when intra vertical is used and checks 16×8 when intra horizontal is used, and passes control to function block530.

The function block542checks the 8×4 and 4×8 sub-partitions, and passes control to decision block526.

The function block530selects the best mode from among the evaluated modes, and passes control to an end block532. The end block532ends the macroblock encoding.

The above scheme may also be readily varied to include the additional conventional parameters relating to distortion and relationships between modes, that is to consider additional distortion based thresholds and adapt such thresholds based on previously computed blocks or macroblocks, etc., and further and extending beyond the preceding, to consider mode motion vector (MV) correlation.

One characteristic of the conventional approach that uses homogeneity analysis and stationarity detection that was not discussed above was the consideration of zero motion within a partition. This concept could be rather beneficial in determining backgrounds or in general stationary regions, nevertheless it may not be as useful if an image is characterized by significant global motion. Considering that several encoders may also include a preprocessing element that already employs a preliminary, usually 16×16, ME or are even based on transcoding architectures (e.g., source input is in a different format A such as MPEG-2 which is decoded and then re-encoded to format B), it is disclosed herein that if such element is available instead of considering zero motion the new motion vector from this element may be used instead. More specifically, an additional condition is added after checking modes 16×16 and SKIP, according to which if IMVBestMode−MVPredMV|<ε and MinJ<T3, where BestMode is the mode with the minimum distortion MinJ, PredMV the preprocessing element MV, while ε and T3are predefined thresholds, search is terminated once again. A similar condition could also apply for testing 8×8 sub-partitions, since this approach may be used to determine region homogeneity based on motion information.

A description will now be given of some of the many attendant advantages/features of the present invention. For example, one advantage/feature is an encoder that performs mode decision by initially performing motion estimation only for a subset of possible block sizes and then uses the motion information, and also additional analysis characteristics, to determine if other block sizes should be examined. Another advantage/feature is an encoder as described above, wherein the analysis characteristics are based on homogeneity analysis. Yet another advantage/feature is an encoder as described above, wherein thresholding criteria are also introduced to terminate the search. Still another advantage/feature is an encoder as described above, wherein the analysis characteristics are based on homogeneity analysis as described above, and wherein the encoder includes a preprocessing element that uses precomputed MV to enhance the homogeneity analysis. A further advantage is an encoder as described above, wherein the analysis characteristics are based on homogeneity analysis as described above, and wherein block error surface is used combined with homogeneity conditions to decide which block partitions to be examined.

These and other features and advantages of the present invention may be readily ascertained by one of ordinary skill in the pertinent art based on the teachings herein. It is to be understood that the teachings of the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or combinations thereof.

Although the illustrative embodiments have been described herein with reference to the accompanying drawings, it is to be understood that the present invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one of ordinary skill in the pertinent art without departing from the scope or spirit of the present invention. All such changes and modifications are intended to be included within the scope of the present invention as set forth in the appended claims.