HK1111549B - Method and system for estimating a pixel intra-prediction mode to conduct encoding or decoding of a digital video - Google Patents

Description

Method and system for estimating intra-pixel prediction mode for encoding or decoding digital video

The present application is a divisional application filed on the filing date of 27/5/2003 and under the filing number 03812403.3 entitled "method and system for intra image prediction mode estimation, communication and organization".

Correlation reference

This application claims us patent application serial No. 60/319,272 filed on 28/5/2002 and us patent application serial No. 60/319,390 filed on 11/7/2002.

Technical Field

Embodiments of the present invention relate to intra prediction of images.

Background

Digital video requires a large amount of data to represent each and all frames in a digital video sequence (e.g., a sequence of frames) in an uncompressed manner. Due to bandwidth limitations, it is not feasible for most applications to transmit uncompressed digital video over computer networks. In addition, uncompressed digital video requires a large amount of storage space. Digital video is typically encoded in some manner to reduce storage space requirements and may reduce bandwidth requirements.

One technique for encoding digital video is inter frame (interframe) coding. Interframe coding exploits the fact that different frames in a video typically include regions that are approximately the same as the pixels selected as x by x. During encoding, motion vectors are correlated with the motion of a block of pixels in one frame to a similar block of pixels in another frame. Thus, the system does not have to encode the pixel block twice, but only once, and provides a motion vector that predicts the other pixel blocks.

Another technique in digital video coding is intra (intraframe) coding. Intra-frame coding encodes a frame or a portion thereof without reference to pixels in other frames. Typical intra-frame coding encodes a frame, or a portion thereof, on a block basis. For example, in mpeg-2, intra-coding uses a discrete cosine transform of a block of pixels, and then encodes the transform coefficients. Other intra-frame coding techniques exist, such as wavelet (wavelet) coding.

Typically, these techniques all use a fairly large data table for reference prediction modes. The memory occupied by these tables is burdensome on many low cost machines. In addition, in a processing device, it is a heavy burden to provide sufficient memory for storing data tables. Moreover, the presence of large data tables ultimately increases the complexity of the system.

Disclosure of Invention

According to a first aspect of the present invention, there is provided a system for encoding or decoding a digital video and estimating an intra-pixel prediction mode, the system comprising: an intra prediction means for predicting pixel values in a given direction; and prediction mode estimation means for estimating a prediction mode for the target block, wherein the intra prediction means uses at least one of a diagonal down/left prediction mode using a designated direction diagonally down and left at an angle of about 45 degrees with respect to a horizontal direction, a diagonal down/right prediction mode using a designated direction diagonally down and right at an angle of about 45 degrees with respect to the horizontal direction, a vertical right prediction mode using a designated direction diagonally down and right at an angle of about 67.5 degrees with respect to the horizontal direction, and a horizontal down prediction mode using a designated direction diagonally down and right at an angle of about 22.5 degrees with respect to the horizontal direction as the intra prediction modes, the prediction modes are numbered in order of the diagonal down/left prediction mode, the diagonal down/right prediction mode, the vertical right prediction mode, and the horizontal down prediction mode with gradually increasing numbers, and the prediction mode estimation means determines, as the prediction mode for the target block, a prediction mode having a lower mode number among the prediction modes of a first block adjacent to and above the target block and a second block adjacent to the left side of the target block.

According to a second aspect of the present invention, there is provided a method for estimating an intra pixel prediction mode, the method comprising: an intra prediction step for predicting pixel values in a given direction; and a prediction mode estimation step for estimating a prediction mode for the target block, wherein the intra prediction step uses at least one of a diagonal down/left prediction mode using a designated direction diagonally down and left at an angle of about 45 degrees with respect to a horizontal direction, a diagonal down/right prediction mode using a designated direction diagonally down and right at an angle of about 45 degrees with respect to a horizontal direction, a vertical right prediction mode using a designated direction diagonally down and right at an angle of about 67.5 degrees with respect to a horizontal direction, and a horizontal down prediction mode using a designated direction diagonally down and right at an angle of about 22.5 degrees with respect to a horizontal direction, the prediction modes are numbered in order of the diagonal down/left prediction mode, the diagonal down/right prediction mode, the vertical right prediction mode, and the horizontal down prediction mode with increasing numbers, and the prediction mode estimation step determines, as the prediction mode for the target block, a prediction mode having a lower mode number among the prediction modes of a first block adjacent to and above the target block and a second block adjacent to the left side of the target block.

Drawings

The following drawings illustrate only typical embodiments of the invention and are therefore not to be considered limiting of its scope, for the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings.

Figure 1 shows some form of contiguous blocks.

Fig. 2 shows a block of pixels and adjacent pixels used for prediction.

Fig. 3 shows the general prediction mode direction.

Fig. 4 shows the general direction of the prediction mode in the embodiment of the present invention.

Fig. 5 shows the general direction of the prediction mode in the embodiment of the present invention.

Fig. 6 shows the general direction of the prediction mode in the embodiment of the present invention.

Fig. 7 shows the general direction of the prediction mode in the embodiment of the present invention.

Fig. 8 shows the general direction of the prediction mode in the embodiment of the present invention.

FIG. 9 is a block diagram representation of mode estimation in some embodiments of the inventions.

FIG. 10 is a block diagram representation of mode estimation using an ordered set of prediction modes in some embodiments.

FIG. 11 is a block diagram showing mode estimation using sorted sets associated with numerical values.

Fig. 12 is a block diagram showing mode estimation selection when some adjacent block data is not available.

FIG. 13 is a block diagram representing a mode order modification in some embodiments of the invention.

FIG. 14 is a block diagram representing an embodiment of the present invention in which estimated patterns are used to modify pattern order usage; and

FIG. 15 is a block diagram representing an embodiment of the present invention in which an estimated schema is used to modify the schema order using a particular specifier.

Detailed Description

Embodiments of the invention include methods and systems relating to intra prediction of images. Since all embodiments relate to intra prediction, the terms "intra prediction" and "prediction" may be used interchangeably when referring to intra prediction processes.

Embodiments of the present invention use intra-frame coding (intracoding) or intra-coding (intracoding) to exploit spatial redundancy in video images. Since contiguous blocks typically have similar properties, the efficiency of the encoding process is improved by referencing the spatial correlation between contiguous blocks. The prediction target block may use this correlation based on the prediction mode used by the neighboring block.

For more efficient processing, or for other reasons, a digital image may be divided into blocks. As shown in fig. 1, target block "C" 12 may be adjacent to adjacent block "a" 14, with block "a" 14 being located directly above target block "C" 12. The other adjacent block "B" 16, is located directly to the left of the target block "C" 12. Blocks that have a common boundary with the target block "C" 12 are also considered to be contiguous blocks of the block "C" 12.

In different configurations, a block may include a different number of pixels. For example, a block may comprise a 4 x 4 sequence of pixels. A block may also comprise a 16 x 16 or 8 x 8 sequence of pixels. Other pixel configurations, including square and rectangular sequences, may constitute blocks.

Each pixel in the target block can be predicted with reference to the correlation data for the pixels in the neighboring blocks. The adjacent pixel data or adjacent block data includes a prediction mode for predicting those adjacent blocks or adjacent pixels. The particular contiguous pixels and the pixels in the target block may be referenced using an english numerical index as shown in fig. 2. Fig. 2 shows a 4 x 4 target block, e.g., block "C" 12 comprises 16 pixels, represented by a lower case alphabetic character 22. The pixels in the adjacent block, which are directly above the target block, are represented by the capital letter characters 24. The pixels in the adjacent block, which are directly to the left of the target block, are represented by upper case alphabetic characters 26.

The prediction mode includes instructions or algorithms for predicting a particular pixel in the target block. These patterns may refer to one or more adjacent block pixels, as described in the pattern description below.

Prediction mode

Mode 0: vertical prediction

a, e, i, m can be predicted by A;

b, f, j, n can be predicted by B;

c, g, k, o can be predicted by C;

d, j, l, p can be predicted by D.

Mode 1: horizontal prediction

a, b, c, c can be predicted by I;

e, f, g, h can be predicted from J;

i, j, K, l can be predicted by K;

m, n, o, p can be predicted from L.

Mode 2: DC prediction

If the full sample A, B, C, D, I, J, K, L is available, all samples can be predicted using (A + B + C + D + I + J + K + L +4) > 3. If A, B, C, D is not available, and I, J, K and L are available, all samples can be predicted with (I + J + K + L +2) > 2. If I, J, K, and L are not available, and A, B, C, D is available, all samples can be predicted with (A + B + C + D +2) > 2. If none of the 8 samples are available, then the prediction value for all the luma samples in the block is 128. This mode is always used to predict the block.

Mode 3: diagonal down/left prediction

a can be predicted by (A +2B + C + I +2J + K +4) > 3;

b, e can be predicted by (B +2C + D + J +2K + L +4) > 3;

c, f, i can be predicted by (C +2D + E + K +2L + M +4) > 3;

d, g, j can be predicted by (D +2E + F + L +2M + N +4) > 3;

h, k, N can be predicted by (E +2F + G + M +2N + O +4) > 3;

l, O can be predicted by (F +2G + H + N +2O + P +4) > 3;

p can be predicted by (G + H + O + P +2) > 2;

mode 4: diagonal down/right prediction

m can be predicted by (J +2K + L +2) > 2;

i, n can be predicted by (I +2J + K +2) > 2;

e, J, o can be predicted by (Q +2I + J +2) > 2;

a, f, k, p can be predicted by (A +2Q + I +2) > 2;

b, g, l can be predicted by (Q +2A + B +2) > 2;

c, h can be predicted by (A +2B + C +2) > 2;

d can be predicted by (B +2C + D +2) > 2;

mode 5: vertical left prediction

a, j can be predicted by (Q + A +1) > 1;

b, k can be predicted by (A + B +1) > 1;

c, l can be predicted by (B + C +1) > 1;

d can be predicted by (C + D +1) > 1;

e, n can be predicted by (I +2Q + A +2) > 2;

f, o can be predicted by (Q +2A + B +2) > 2;

g, p can be predicted by (A +2B + C +2) > 2;

h can be predicted by (B +2C + D +2) > 2;

i can be predicted by (Q +2I + J +2) > 2;

m can be predicted by (I +2J + K +2) > 2;

mode 6: horizontal down prediction

a, g can be predicted by (Q + I +1) > 1;

b, h can be predicted by (I +2Q + A +2) > 2;

c can be predicted by (Q +2A + B +2) > 2;

d can be predicted by (A +2B + C +2) > 2;

e, k can be predicted by (I + J +1) > 1;

f, l can be predicted by (Q +2I + J +2) > 2;

i, o can be predicted by (J + K +1) > 1;

j, p can be predicted by (I +2J + K +2) > 2;

m can be predicted by (K + L +1) > 1;

n can be predicted by (J +2K + L +2) > 2;

mode 7: vertical right prediction

a can be predicted by (2A +2B + J +2K + L +4) > 3;

b, i can be predicted by (B + C +1) > 1;

c, j can be predicted by (C + D +1) > 1;

d, k can be predicted by (D + E +1) > 1;

l can be predicted by (E + F +1) > 1;

e can be predicted by (A +2B + C + K +2L + M +4) > 3;

f, m can be predicted by (B +2C + D +2) > 2;

g, n can be predicted by (C +2D + E +2) > 2;

h, o can be predicted by (D +2E + F +2) > 2;

p can be predicted by (E +2F + G +2) > 2;

mode 8: horizontal over-the-horizon prediction

a can be predicted by (B +2C + D +2I +2J +4) > 3;

b can be predicted by (C +2D + E + I +2J + K +4) > 3;

c, e can be predicted by (J + K +1) > 1;

d, f can be predicted by (J +2K + L +2) > 2;

g, i can be predicted by (K + L +1) > 1;

h, j can be predicted by (K +2L + M +2) > 2;

l, N can be predicted by (L +2M + N +2) > 2;

k, M can be predicted by (L + M +1) > 1;

o can be predicted by (M + N +1) > 1;

p can be predicted by (M +2N + O +2) > 2.

The ordering process, which is based on the possibility of fewer prediction errors for each mode, improves coding efficiency, reduces memory requirements, and may be defined at least in part mathematically.

Each prediction mode may be described literally with the general prediction direction in the modes named above (i.e., horizontally above, vertically and diagonally below and to the left). The prediction mode may be graphically described using angular directions. This angular orientation may be depicted graphically by arrows radiating outward from a central point, as shown in FIG. 3. In such a graph, each arrow, as well as the center point, represents a prediction mode. The angle corresponding to the prediction mode has a regular relationship with the direction determined by the direction from the weighted average position of the neighboring pixels used for predicting the target pixel to the position of the actual target pixel. However, in the above definitions and the JVT standard, there is a more precise definition of the description of the schema. In fig. 3, the center point 32 indicates no direction, so this point may be associated with a DC prediction mode. Horizontal arrow 34 may represent a horizontal prediction mode. Vertical arrow 36 may represent a vertical prediction mode. An arrow 38 extending diagonally downward and rightward from the center point at about 45 degrees from the horizontal line indicates a diagonal down/right (DDR) prediction mode. An arrow 40 extending diagonally downward and to the left from the center point, at approximately 45 degrees from the horizontal, indicates a diagonal down/left (DDL) prediction mode. The DDR and DDL prediction modes are both referred to as diagonal prediction modes.

The cluster center points are slanted toward the right and up direction, with arrow 42 at about 22.5 degrees from horizontal, indicating a Horizontal Up (HU) prediction mode. An arrow 44 extending diagonally from the center point to the lower right at about 22.5 degrees from the horizontal indicates a lower Horizontal (HD) prediction mode. Arrow 46, extending diagonally downward and to the right from the center point, at about 67.5 degrees from the horizontal, represents a Vertical Right (VR) prediction mode. Arrow 48, extending diagonally from the center point in the lower left direction, at about 67.5 degrees from horizontal, represents the Vertical Left (VL) prediction mode. HU, HD, VR and VL, are collectively referred to as intermediate angle prediction modes.

Many other prediction modes can be made and described using this angular description mode.

Prediction mode order

The present invention determines that the prediction modes should be ordered in a manner that is generally consistent with producing a reduced likelihood of prediction error. With prediction modes ordered according to an order that generally yields less likelihood of prediction error, the resulting data itself has a more consistent tendency to order. Further, the communication of the modes may utilize coding techniques that reduce the required memory and bandwidth. For example, the inventors have determined that horizontal and vertical prediction modes are generally more likely than diagonal modes; whereas the diagonal mode is more likely than the intermediate angular prediction mode. In addition, the DC prediction mode (e.g., when neighboring blocks are intra-mode coded) is generally less likely than the horizontal and vertical prediction modes, but is generally more likely than the diagonal mode.

For blocks of non-continuous boundaries, such as image edges or cut-like (swipe) boundaries, the order established in some embodiments of the invention, using conventional terminology, may be described as follows: vertical and horizontal prediction modes having a higher likelihood of producing reduced prediction errors than the DC prediction mode; the DC prediction mode has a higher likelihood of producing reduced prediction errors than the diagonal prediction mode; whereas the diagonal prediction mode has a higher likelihood of producing reduced prediction errors than the intermediate angular prediction mode.

For blocks where adjacent edges or boundaries are not available, or where adjacent blocks or pixel prediction mode data is not available, the order established in some embodiments of the present invention may be described as follows using conventional terminology: the DC prediction mode has a higher likelihood of producing reduced prediction errors than the vertical and horizontal prediction modes; the vertical and horizontal prediction modes have a higher likelihood of producing reduced prediction errors than the diagonal prediction mode; diagonal prediction modes have a higher likelihood of producing reduced prediction errors than intermediate angular prediction modes.

In the first set of embodiments as shown in fig. 4, the pattern order may be defined in the following way:

mode 0: vertical prediction

Mode 1: horizontal prediction

Mode 2: DC prediction

Mode 3: diagonal down/left prediction

Mode 4: diagonal down/right prediction

Mode 5: horizontal down prediction

Mode 6: vertical right prediction

Mode 7: vertical left prediction

Mode 8: horizontal over-the-horizon prediction

In the second set of embodiments as shown in fig. 5, the pattern order may be defined in the following way:

mode 0: horizontal prediction

Mode 1: vertical prediction

Mode 2: DC prediction

Mode 3: diagonal down/left prediction

Mode 4: diagonal down/right prediction

Mode 5: horizontal down prediction

Mode 6: vertical right prediction

Mode 7: vertical left prediction

Mode 8: horizontal over-the-horizon prediction

In the third set of embodiments as shown in fig. 6, the pattern order may be defined in the following way:

mode 0: vertical prediction

Mode 1: horizontal prediction

Mode 2: DC prediction

Mode 3: diagonal down/left prediction

Mode 4: diagonal down/right prediction

Mode 5: vertical right prediction

Mode 6: horizontal down prediction

Mode 7: vertical left prediction

Mode 8: horizontal over-the-horizon prediction

In the fourth set of embodiments as shown in fig. 7, the pattern order may be defined in the following way:

mode 0: horizontal prediction

Mode 1: vertical prediction

Mode 2: DC prediction

Mode 3: diagonal down/left prediction

Mode 4: diagonal down/right prediction

Mode 5: vertical right prediction

Mode 6: horizontal down prediction

Mode 7: vertical left prediction

Mode 8: horizontal over-the-horizon prediction

In the fifth set of embodiments as shown in fig. 8, the pattern order may be defined in the following way:

mode 0: DC prediction

Mode 1: vertical prediction

Mode 2: horizontal prediction

Mode 3: diagonal down/left prediction

Mode 4: diagonal down/right prediction

Mode 5: vertical right prediction

Mode 6: horizontal down prediction

Mode 7: vertical left prediction

Mode 8: horizontal over-the-horizon prediction

It should be noted that in other embodiments of the present invention, the order of the modes may be different from the order in the examples.

In some embodiments of the invention, the horizontal prediction (mode 0) and vertical prediction (mode 1) may be reversed if desired. It is also appreciated that the diagonal down/left prediction mode and the horizontal down prediction mode may be reversed, if desired. Additionally, it is also appreciated that the diagonal down/right prediction mode (mode 5), the vertical right prediction mode (mode 6), the vertical left prediction mode (mode 7), and the horizontal up prediction mode (mode 8) may be reordered if desired. Further, it is desirable that the DC prediction be placed between the mode 0/mode 1 set and the mode 3/mode 4 set; but may be placed between the mode 3/mode 4 set and the mode 5/mode 6/mode 7/mode 8 set, or in other locations, if desired. Furthermore, if desired, the angular patterns 3-8 can be renumbered without significant impact on the efficiency of the encoding.

In embodiments of the present invention, the prediction modes may be reordered separately on a prediction basis for all blocks (e.g., those using the prediction scheme). In addition, not all individual blocks (e.g., those using the prediction scheme) use a prediction reference, e.g., more than 50%, 75%, or 90% if desired. The order of prediction modes of different blocks may be the same or different. Further, such reordering of each of the prediction-based modes (e.g., according to a predetermined consistency approach), at least for prediction mode 5, mode 6, and mode 7, may be implemented in any other manner to order the remaining modes. The order of the prediction modes is preferably 0, 1, 2, 3, 4, 5, 6, 7, and 8. Other predefined orders of prediction modes may be used as well.

In some embodiments of the invention, one or more data tables may be included for organizing the pattern data. These patterns are typically organized in an ordered fashion, and can be used together in each cell of the data table to provide a more ordered set. For example, each entry in the data table may include an ordered set of numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Alternatively, in each entry of the data table, the ordered set of numbers in the data table comprises an ordered set of numbers of 5, 6, 7, 8, or 9. For example, the entries of the data table include the following data sets of entries {1, 2, 3, 5, 7 }; {0, 1, 2, 3, 4, 5, 6 }; {0, 1, 3, 5, 6, 7, 8}, where each digit in the set is an increasing numerical value. For example, another option, the entries of the data table include the following data sets {1, 2, 3, 5, 7 }; {0, 1, 2, 3, 4, 5, 6 }; {0, 1, 3, 5, 6, 7, 8}, where each set is at least comprised by 25%, or 35%, or 50%, or 75%, or 90% or higher proportion of units. In this way, the predictability of the table is greater and the required memory is reduced relative to known data table approaches.

The predefined manner of ordering the set of data entries should be independent of the prediction mode of the contiguous set of pixels (e.g., macroblocks). It is to be understood that the data tables may be "static" in nature, or may be effectively dynamically generated in whole or in part when the underlying schema is needed in the data. Thus, the entries may be determined using a mathematical equation or algorithm, wherein such techniques may be employed to create a "table". Therefore, a "data table" used therein is not limited to only a static table, but further includes a set of values used for prediction of the values thus determined.

Unfortunately, replacing digits of a previous pattern with new pattern digits (e.g., replacing digits in cells of a known data table), while perhaps an improvement, still results in a data set that is typically not ordered.

Estimating pixel prediction mode based on adjacent block data

In contrast to the above-described, usually unordered data sets, even if alternatives are used, the present invention further derives the insight that the prediction mode with the highest likelihood should be ranked first, second and second, and the remaining modes should be processed in a predefined manner, if desired. This predefined approach should be independent of the prediction modes of the neighboring macroblocks. The preferred ordering of the remaining modes should be in order of decreasing likelihood of the remaining modes occurring (the most likely prediction mode, or, if desired, the second most likely prediction mode).

Based on the intra prediction modes of block a and block B, as shown in fig. 1, the intra prediction mode order of block C may be determined in the following manner:

(1) if both block a and block B are "external" (e.g., not available), only DC prediction (mode 2) is allowed, so the intra prediction mode order for block C is {2 }.

(2) If block a is "external" (e.g., not available) and block B is not "external", only DC prediction (mode 2) and horizontal prediction (mode 0) are allowed for block C, and therefore;

(i) if block B is 2, the prediction mode order of block C is 2, 0;

(ii) otherwise, the intra prediction mode order of block C is {0, 2 };

(3) if block a is not "external", but block B is "external", only DC prediction (mode 2) and vertical prediction (mode 1) are allowed for block C, and therefore;

(i) if block a is 2, the intra prediction mode order of block C is {2, 1 };

(ii) otherwise, the intra prediction mode order of block C is {1, 2 };

(4) if neither block a nor block B is "external",

(i) if the prediction mode of block a is less than the prediction mode of block B, then the intra-prediction mode order of block C is { intra-prediction block mode a, intra-prediction block mode B, other modes ordered in ascending order };

(ii) if the prediction mode of block a is more than that of block B, then the intra-prediction mode order of block C is { intra-prediction block mode B, intra-prediction block mode a, other modes ordered in ascending order };

(iii) if the prediction mode of block a is equal to that of block B, then the intra-prediction mode order of block C is { intra-prediction block mode a, with the other modes ordered in ascending order }.

For example, if the prediction mode of block a is 3 and the prediction mode of block B is 1, then the intra-prediction mode order of block C is {1, 3, 0, 2, 4, 5, 6, 7, 8 }. The automatic arrangement of the occurrences of the remaining patterns will still be regularly arranged in the appropriate sequence, according to the patterns arranged with decreasing (or increasing) likelihood of occurrence of the totality. The likelihood of proper prediction can be increased forward by ordering in a sequence from high to low likelihood. Using entropy coding, the resulting coded bit stream can be reduced. Other arrangements may be used as well.

The selection plan is conceptually based on the rule that if the prediction of block a is X and the prediction of block B is Y, then the prediction of block C may be either X or Y. The prediction of X and/or Y is located at the beginning of the table and the remaining patterns are arranged sequentially after it.

Declaring another case when the prediction modes of a and B are known (including the case where a or B or both are outside the slice) gives the most probable mode of C, i.e. the minimum of the modes used by blocks a and B. If one of block a or block B is "external," the most probable mode is equal to prediction mode 2. The ordering of the prediction modes assigned to block C, and therefore the most likely mode, is therefore followed by the remaining modes in ascending order.

An embodiment of the present invention is described with reference to fig. 9. In these embodiments, one target block is selected for prediction 50. The prediction mode used for predicting the first neighboring block, which is directly adjacent to the target block, is determined 52. The prediction mode used for predicting the second neighboring block, which also neighbors the target block, is determined 54. These contiguous block prediction modes are then detected 56 to determine which produces the least prediction error with a higher likelihood.

In other embodiments of the present invention, the set of prediction modes is ordered 58 by the likelihood of the modes producing fewer prediction errors, as shown in FIG. 10. A target block 60 is selected. A prediction mode for a first neighboring block is determined 62 and a prediction mode for a second neighboring block is determined 64. The two prediction modes are then detected 66 to determine which of the ordered set of modes occurs first, thus determining the mode that corresponds to the high likelihood of producing fewer prediction errors.

In other embodiments of the present invention, the set of prediction modes is ordered 68 according to likelihood of producing fewer prediction errors, as shown in FIG. 11. The patterns in these sorted sets are then associated 70 with values, so that patterns with a higher likelihood of producing fewer prediction errors are associated with smaller values. Thereafter, a mode for predicting the first neighboring block is determined 72, and a mode for predicting the second neighboring block is also determined 74. These contiguous block patterns are then detected to determine which pattern is associated with a lower value. This mode is designated as the evaluation mode of the target block prediction.

In other embodiments, the set of prediction modes is ordered according to likelihood of producing fewer prediction errors, as shown in fig. 12. These patterns in the sorted set are combined 80 with values, which results in patterns with a greater likelihood of fewer prediction errors, combined with a smaller value. An attempt 82 is made to determine the mode used to predict the first neighboring block and an attempt 84 is made to determine the mode used to predict the second neighboring block. If the prediction mode used to predict the first neighboring block is not available 86, a default prediction mode (e.g., DC prediction mode) is assigned as the evaluated prediction mode 90 for the target block. Similarly, if the prediction mode used to predict the second neighboring block is not available 88, a default prediction mode (e.g., DC prediction mode) is designated as the evaluated prediction mode 90 for the target block. When contiguous block prediction modes are available, these contiguous block modes may be detected and a determination made as to which mode is associated with a lower value. This mode is then designated as the evaluation mode 92 to predict the target block.

Modifying prediction mode order based on contiguous block data

In some embodiments of the invention, the prediction mode ordering is determined independently of contiguous block data, as described above, and may be modified using contiguous block data. Prediction mode estimates determined with reference to contiguous block data may be inserted into the prediction mode order to modify the order to reflect additional information obtained from contiguous block data.

In some embodiments, the prediction mode estimates are based on contiguous block data and may be inserted directly into the prediction mode order set. Typically, the prediction mode estimates will be inserted or anticipated ahead of the prediction mode order, at the locations most likely to produce a mode that reduces prediction errors. However, in some embodiments, the estimates may be inserted at different positions in the pattern order.

In some embodiments of the present invention, as shown in FIG. 13, a prediction mode order is selected 102, wherein the prediction mode order elements may be arranged in an order of their likelihood of producing fewer prediction errors. In other words, the first element in the order, which indicates that the prediction mode is most likely to produce fewer prediction errors, the next element in the order, which indicates that the prediction mode is less likely to produce fewer prediction errors, and so on, until the last prediction mode in the order, which indicates that the prediction mode in the order is least likely to produce fewer prediction errors.

As described above, a prediction mode estimate is determined 104. Using the contiguous block data, the estimate is determined. Typically, the estimate is a prediction mode used in one or more neighboring blocks that are most likely to produce lower prediction errors. However, other ways of determining the prediction may also be used. When sufficient contiguous block prediction mode data is not available, for example at the edge of an image or at the boundary of a slice, the prediction mode of the target block can be estimated in the absence of one or more contiguous blocks or their prediction mode data. In many cases, the DC prediction mode is estimated when contiguous block data is limited or unavailable.

In some such embodiments, once the estimated prediction mode is estimated, the estimated prediction mode is placed 106 into the mode order as the mode most likely to produce a lower prediction error. In some embodiments, this is the first mode in the sequence, or the mode associated with the lowest numerical value.

In other embodiments, the estimated prediction mode may be prioritized over a pre-selected mode order. In some such embodiments, as shown in fig. 14, a pre-selected mode order is specified 110 in the encoder and decoder. This order includes a set of prediction modes, arranged in order of likelihood of producing a lower prediction error, or other order. Based on the contiguous block data, an estimated prediction mode is also determined 112. The estimated prediction mode is determined in the encoder and decoder according to the same algorithm or method. The encoder also determines the actually best prediction mode 114 for predicting the pixels based on motion vectors or other known techniques. The encoder then compares 116 the substantially best prediction mode and the estimated prediction mode to determine if they are the same. If the estimated prediction mode is the same as the actually best prediction mode, the encoder signals the decoder to use the estimated prediction mode 118. In some embodiments, estimating the prediction mode signal may be performed using a 1-bit specifier to identify whether to use an estimation mode.

If the prediction mode is estimated not to be the actually best prediction mode, the encoder signals the decoder to use the other modes 120. This may be performed by reference to a pre-established pattern order. The encoder determines which mode in the sequence of modes is the most equal to the actually best prediction mode and signals the decoder to use that mode.

When a sorted set of prediction modes is used, the order of the set is reordered as soon as further data is obtained. The ordered set of prediction modes is reordered, for example, when an estimated prediction mode is determined, or when the best actual prediction mode is determined. Thus, the modification pattern is to be abruptly inserted into, placed in front of, or, in some cases, deleted from the sorted set.

In some embodiments of the invention, each mode in the sequence of modes is associated with a numerical value in the sequence. In these embodiments, the value associated with the mode to be used signals the decoder to use the prediction mode. In some such embodiments, as shown in fig. 15, a mode order 130 is selected that includes 9 prediction modes. An estimated prediction mode, which is one of the 9 modes in the order, based on contiguous block data, is determined 132. The best prediction mode 134 is determined by a motion vector method or other methods. The best prediction mode is then compared 136 to the estimated prediction mode. If the estimated prediction mode is substantially the same as the best prediction mode, the decoder sends a 1-bit specifier signal to use the estimated prediction mode, the 1-bit specifier signal having been identified at the decoder. If the estimated prediction mode is not equal to the best prediction mode, the estimated prediction mode is essentially excluded from the order 140. The exclusion is achieved by reordering the sets, skipping the estimation mode in order, or using other methods. The remaining order effectively comprises 8 modes, which can be represented using a 3-bit specifier. This 3-bit specifier may be sent to the decoder to specify which mode to use in prediction.

The terms and expressions which have been employed in the foregoing detailed description are used therein as terms of description and not of limitation, and there is no intention, in the use of such terms and expressions, of excluding equivalents of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.

Claims (2)

1. A system for estimating an intra-pixel prediction mode for encoding or decoding a digital video, the system comprising:

an intra prediction means for predicting pixel values in a given direction; and

a prediction mode estimation means for estimating a prediction mode for the target block, wherein

The intra prediction apparatus uses at least one diagonal down/left prediction mode using a designated direction of diagonal down left at an angle of about 45 degrees with respect to the horizontal direction, one diagonal down/right prediction mode using a designated direction of diagonal down right at an angle of about 45 degrees with respect to the horizontal direction, one vertical right prediction mode using a designated direction of diagonal down right at an angle of about 67.5 degrees with respect to the horizontal direction, and one horizontal down prediction mode using a designated direction of diagonal down right at an angle of about 22.5 degrees with respect to the horizontal direction as the intra prediction modes,

numbering the prediction modes in the order of diagonal down/left prediction mode, diagonal down/right prediction mode, vertical right prediction mode and horizontal down prediction mode with increasing numbers, and

the prediction mode estimation means determines, as the prediction mode for the target block, a prediction mode having a lower mode number among the prediction modes of a first block adjacent to and above the target block and a second block adjacent to the left side of the target block.

2. A method of estimating an intra-pixel prediction mode for encoding or decoding a digital video, the method comprising:

an intra prediction step for predicting pixel values in a given direction; and

a prediction mode estimation step for estimating a prediction mode for the target block, wherein

The intra prediction step uses at least one diagonal down/left prediction mode using a designated direction of diagonal down left at an angle of about 45 degrees with respect to the horizontal direction, one diagonal down/right prediction mode using a designated direction of diagonal down right at an angle of about 45 degrees with respect to the horizontal direction, one vertical right prediction mode using a designated direction of diagonal down right at an angle of about 67.5 degrees with respect to the horizontal direction, and one horizontal down prediction mode using a designated direction of diagonal down right at an angle of about 22.5 degrees with respect to the horizontal direction,

numbering the prediction modes in the order of diagonal down/left prediction mode, diagonal down/right prediction mode, vertical right prediction mode and horizontal down prediction mode with increasing numbers, and

the prediction mode estimation step determines, as the prediction mode for the target block, a prediction mode having a lower mode number among the prediction modes of a first block adjacent to and above the target block and a second block adjacent to the left side of the target block.