Patent Description:
Existing video coding standards, such as H. <NUM>/AVC, generally provide relatively high coding efficiency at the expense of increased computational complexity. As the computational complexity increases, the encoding and/or decoding speeds tend to decrease. Also, the desire for increased higher fidelity tends to increase over time which tends to require increasingly larger memory requirements and increasingly more complicated processing.

Referring to <FIG>, many decoders (and encoders) receive (and encoders provide) encoded data for blocks of an image. Typically, the image is divided into blocks and each of the blocks is encoded in some manner, such as using a discrete cosine transform (DCT), and provided to the decoder. The decoder receives the encoded blocks and decodes each of the blocks in some manner, such as using an inverse discrete cosine transform.

Video coding standards, such as MPEG-<NUM> part <NUM> (H. <NUM>), compress video data for transmission over a channel with limited frequency bandwidth and/or limited storage capacity. These video coding standards include multiple coding stages such as intra prediction, transform from spatial domain to frequency domain, quantization, entropy coding, motion estimation, and motion compensation, in order to more effectively encode and decode frames. Many of the coding and decoding stages are unduly computationally complex.

A context adaptive binary arithmetic coding (CABAC) based encoding and/or decoding technique is generally context adaptive which refers to (i) adaptively coding symbols based on the values of previous symbols encoded and/or decoded in the past and (ii) context, which identifies the set of symbols encoded and/or decoded in the past used for adaptation. The past symbols may be located in spatial and/or temporal adjacent blocks. In many cases, the context is based upon symbol values of neighboring blocks.

The context adaptive binary arithmetic coding (CABAC) encoding technique includes coding symbols using the following stages. In the first stage, the CABAC uses a "binarizer" to map input symbols to a string of binary symbols, or "bins". The input symbol may be a non-binary valued symbol that is binarized or otherwise converted into a string of binary (<NUM> or <NUM>) symbols prior to being coded into bits. The bins can be coded into bits using either a "bypass encoding engine" or a "regular encoding engine".

For the regular encoding engine in CABAC, in the second stage a probability model is selected. The probability model is used to arithmetic encode one or more bins of the binarized input symbols. This model may be selected from a list of available probability models depending on the context, which is a function of recently encoded symbols. The probability model stores the probability of a bin being "<NUM>" or "<NUM>". In the third stage, an arithmetic encoder encodes each bin according to the selected probability model. There are two sub-ranges for each bin, corresponding to a "<NUM>" and a "<NUM>". The fourth stage involves updating the probability model. The selected probability model is updated based on the actual encoded bin value (e.g., if the bin value was a "<NUM>", the frequency count of the "<NUM>"s is increased). The decoding technique for CABAC decoding reverses the process.

For the bypass encoding engine in CABAC, the second stage involves conversion of bins to bits omitting the computationally expensive context estimation and probability update stages. The bypass encoding engine assumes a fixed probability distribution for the input bins. The decoding technique for CABAC decoding reverses the process.

The CABAC encodes the symbols conceptually using two steps. In the first step, the CABAC performs a binarization of the input symbols to bins. In the second step, the CABAC performs a conversion of the bins to bits using either the bypass encoding engine or the regular encoding engine. The resulting encoded bit values are provided in the bitstream to a decoder.

The CABAC decodes the symbols conceptually using two steps. In the first step, the CABAC uses either the bypass decoding engine or the regular decoding engine to convert the input bits to bin values. In the second step, the CABAC performs de-binarization to recover the transmitted symbol value for the bin values. The recovered symbol may be non-binary in nature. The recovered symbol value is used in remaining aspects of the decoder.

Document <NPL> discloses to represent an intra coding mode using two syntax elements prev_intra_luma_pred_flag and mpm_idx and the prev_intra_luma_pred_flag is encoded using a regular CABAC mode.

As previously described, the encoding and/or decoding process of the CABAC includes at least two different modes of operation. In a first mode, the probability model is updated based upon the actual coded bin value, generally referred to as a "regular coding mode" The regular coding mode, requires several sequential serial operations together with its associated computational complexity and significant time to complete. In a second mode, the probability model is not updated based upon the actual coded bin value, generally referred to as a "bypass coding mode". In the second mode, there is no probability model (other than perhaps a fixed probability) for decoding the bins, and accordingly there is no need to update the probability model which reduces the computational complexity of the system.

Embodiments of the present invention are defined by the independent claims. Additional features of embodiments of the invention are presented in the dependent claims. In the following, parts of the description and drawings referring to former embodiments which do not necessarily comprise all features to implement embodiments of the claimed invention are not represented as embodiments of the invention but as examples useful for understanding the embodiments of the invention.

The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention, taken in conjunction with the accompanying drawings.

Referring to <FIG>, an exemplary encoder <NUM> includes an entropy coding block <NUM>, which may include a CABAC, receives inputs from several different other aspects of the encoder <NUM>. One of the inputs to the entropy coding block <NUM> is SAO information from a sample adaptive offset (SAO) block <NUM>. Another of the inputs to the entropy coding block <NUM> is ALF information from an adaptive loop filter <NUM>. Another of the inputs to the entropy coding block <NUM> is inter mode information from a motion estimation / motion compensation (ME/MC) block <NUM>. Another of the inputs to the entropy coding block <NUM> is intra mode information from an intra prediction block <NUM>. Another of the inputs to the entropy coding block <NUM> are residues from a quantization block <NUM>. The entropy coding block <NUM> provides an encoded bitstream. This information provided to the entropy coding block <NUM> may be encoded in the bitstream. The SAO block <NUM> provide samples to the adaptive loop filter <NUM> which provides restored samples <NUM> to a reference frame buffer <NUM> which provides data to the motion estimation / motion compensation (ME/MC) block <NUM>. Deblocked samples <NUM> from a deblocking filter <NUM> are provided to the SAO block <NUM>. As with many encoders, the encoder may further include the intra-prediction block <NUM> where predicted samples <NUM> are selected between the intra prediction block <NUM> and the ME/MC block <NUM>. A subtractor <NUM> subtracts the predicted samples <NUM> from the input. The encoder <NUM> also may include a transform block <NUM>, an inverse quantization block <NUM>, an inverse transform block <NUM>, and a reconstruction block <NUM>.

Referring to <FIG>, an associated decoder <NUM> for the encoder of <FIG> may include an entropy decoding block <NUM>, which may include a CABAC. The entropy decoding block <NUM> receives an encoded bitstream <NUM> and provides data to different aspects of the decoder <NUM>. The entropy decoding block <NUM> may provide intra mode information <NUM> to an intra prediction block <NUM>. The entropy decoding block <NUM> may provide inter mode information <NUM> to the MC block <NUM>. The entropy decoding block <NUM> may provide ALF information <NUM> to the adaptive loop filter <NUM>. The entropy decoding block <NUM> may provide SAO information <NUM> to the SAO block <NUM>. The entropy decoding block <NUM> may provide coded residues <NUM> to an inverse quantization block <NUM>, which provides data to an inverse transform block <NUM>, which provides data to a reconstruction block <NUM>, which provides data to the intra prediction block <NUM> and/or a deblocking filter <NUM>. The sample adaptive offset (SAO) block <NUM> that provides samples to an adaptive loop filter <NUM> which provides restored samples <NUM> to a reference frame buffer <NUM> which provides data to the motion compensation (MC) block <NUM>. The deblocking filter <NUM> provides deblocked samples <NUM> to the SAO block <NUM>.

Referring to <FIG>, a graphical illustration is shown of selecting a probability model when using a CABAC regular decoding engine to decode a bin <NUM> and using neighboring contexts. The context is determined as a function of the decoded symbol CtxtA <NUM> and decoded symbol CtxtB <NUM>, where CtxtA was stored in a line buffer <NUM>. The context determines the probability model used to decode <NUM>. In contrast, referring to <FIG>, a graphical illustration is shown of selecting a probability model when using a CABAC bypass decoding engine to decode a symbol <NUM>. The selected probability model does not depend on context information. Referring to <FIG>, a bitstream <NUM> includes a set of binarized syntax elements <NUM> coded using the bypass coding engine, and a set of binarized syntax elements <NUM> coded using the regular coding engine and therefore requiring probability model updates in the CABAC. As it may be observed, the requirement for a line buffer is eliminated when using the bypass coding mode, the amount of memory required is reduced, the probability model update is not performed, and the throughput of the CABAC is increased.

The CABAC decodes the video based upon a complex set of potential encoding configurations. For example, the coding configurations may include motion compensated blocks and intra-prediction blocks. The encoding and decoding of motion compensated blocks of video tend to be relatively complicated and tend to generally benefit from the added complexity afforded by the CABAC regular coding engine. Part of the complexity, in addition to the decoding technique, is the storing of information on which the symbols depends and the need for updating the probability model mechanism each time a symbol is encoded and/or decoded. The encoding and decoding of intra predicted blocks of video tend to be relatively less complicated and tend to generally benefit to a lesser degree from the added complexity afforded by the CABAC regular coding engine. In this case, the bypass coding mode tends to reduce the need for additional storage, determining the context, and the updating of the probability model, without meaningfully impacting compression efficiency. In particular, some symbols in the bitstream are generally equally likely to contain bins with values of <NUM> or <NUM> after binarization. Moreover, at the same time such symbols do not result in meaningful compression benefits due to the context adaptation of the CABAC regular coding engine. It is speculated that this lack of meaningful compression benefits is likely due to rapid fluctuations in their probability distribution.

Referring to <FIG>, in one embodiment the CABAC, which may be included as part of the entropy decoding <NUM> of the decoder <NUM>, receives bits originating in the bitstream <NUM>. For those syntax elements, or symbols, belonging to a block which was intra coded <NUM>, it may be determined, whether the particular symbol is suitable to use the bypass decoding engine <NUM>, if the impact on coding efficiency does not justify the additional computational complexity. If the syntax element, or symbol, belonging to an intra coded block <NUM> is suitable for using the bypass decoding engine, then the binarized symbol is decoded using the bypass decoding mode <NUM>. If the syntax element, or symbol, belonging to an intra coded block <NUM> is not suitable for using the bypass decoding engine, then the binarized symbol is decoded using the regular decoding mode <NUM>.

Referring to <FIG>, the CABAC may receive a symbol <NUM> to be decoded from the bitstream. A symbol <NUM> belonging to a block to the left of the current block has previously been decoded and the prediction mode for the left block has been determined as Mleft <NUM>, where prediction mode identifies a method for predicting the pixel values within a block using previously decoded data. Similarly, a symbol <NUM> belonging to a block above the current block has previously been decoded and the prediction mode for the above block has been determined as Mabove <NUM>. In most situations, the prediction mode for the current block is not expressly transmitted in the bitstream, but is instead determined based upon a likelihood of previously determined prediction modes, such as Mleft and Mabove, as previously described. Accordingly, a function generates a list of probable modes using f (Mleft, Mabove) <NUM> based upon the Mleft <NUM> and the Mabove <NUM>, which may be referred to as Mlist = f(Mleft, Mabove). The result is a list of probable modes Mlist <NUM>.

In one embodiment, the list of probable modes Mlist <NUM> generated by the function generate list of most probable modes using f (Mleft, Mabove) <NUM> may include two lists of prediction modes (or otherwise combined in a single list), a first list including the "most probable modes" and a second list including the "not most probable modes". From the bitstream the system may select MPM_FLAG bits <NUM>, which indicate a suitability for using the regular decoding engine <NUM>, and therefore a syntax element, such as MPM_FLAG <NUM>, indicating whether the prediction mode for the current block is in the "most probable mode list" (typically signaled with a "<NUM>") or is in the "not most probable mode list" (typically signaled with a "<NUM>"). A comparison <NUM> with the MPM_FLAG <NUM> for the current block may be used to determine whether the suitable prediction mode is in the "most probable mode list" <NUM> or in the "not most probable mode list" <NUM>. In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "most probable mode list" <NUM>, and in the event that there exists only a single prediction mode in the "most probable mode list", then that is a selected prediction mode <NUM> for the current block. The results of the selected prediction mode <NUM> is provide as a selected mode <NUM> as the output. In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "most probable mode list" <NUM>, and in the event that there exists only two prediction modes in a "most probable mode list" index, then a MPM_INDEX index <NUM> may be used to signal the selected prediction mode <NUM> to select between the two prediction modes and provide the selected mode <NUM> as an output. The MPM_INDEX index <NUM> may be determined by the system from the bitstream by selecting MPM_INDEX bits <NUM>, which indicate a suitability for using the bypass decoding engine <NUM>, and therefore provide the MPM_Index index <NUM>. This process of selecting among the entries of the "most probable mode list" <NUM> may be expanded with additional bit allocation to MPM_INDEX index <NUM> to distinguish between additional different modes.

As noted, based upon the past bins in the bitstream, the CABAC may determine the probability that the current bin will be a "<NUM>" or a "<NUM>". The selection between the "within the most probable list" and "not within the most probable list", is a decision that has a meaningful impact on the coding efficiency of the CABAC, and accordingly having an updated probability is beneficial.

In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "not most probable mode list" <NUM>, and in the event that there exists only a single prediction mode in the "not most probable mode list" <NUM>, then that is a selected prediction mode <NUM> for the current block. In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "not most probable mode list" <NUM>, and in the event that there exists only two prediction modes in a "not most probable mode list" index, then a REM_INTRA_PRED_MODE index <NUM> may be used to signal to the selected prediction mode <NUM> to select between the two prediction modes and provide the selected prediction mode <NUM> as an output. The REM_INTRA_PRED_MODE index <NUM> may be determined by the system from the bitstream by selecting REM_INTRA_PRED_MODE bits <NUM>, which indicate a suitability for using the bypass decoding engine <NUM>, and therefore provide the REM_INTRA_PRED_MODE index <NUM>. In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "not most probable mode list" <NUM>, and in the event that there exists only four prediction modes in a "not most probable mode list" index, then a <NUM>-bit REM_INTRA_PRED_MODE index <NUM> may be used to signal to the selected prediction mode <NUM> to select between the four prediction modes and provide the selected mode <NUM> as an output. In the event that the MPM_FLAG <NUM> for the current block indicates that the prediction mode is in the "not most probable mode list", and in the event that there exists only eight prediction modes in the "not most probable mode list" index, then a <NUM>-bit REM_INTRA_PRED_MODE index <NUM> may be used to signal to the selected prediction mode <NUM> to select between the eight prediction modes and provide the selected mode <NUM> as an output. This process of selecting modes from the not most probable mode list may be expanded with additional bit allocation to REM_INTRA_PRED_MODE index to distinguish between the different prediction modes.

As noted, based upon the past bins in the bitstream, the CABAC may determine the probability that the current bin will be a "<NUM>" or a "<NUM>". As previously noted, the selection between the "most probable mode list" and the "not within the most probable mode list", is a decision that has a meaningful impact on the coding efficiency of the CABAC, and accordingly having an updated probability is beneficial. However, the selection among the possibilities within the "not most probable mode list" <NUM> has limited impact on the coding efficiency of the CABAC, and accordingly the probabilities should not be updated, thus reducing the computational complexity of the system. In most cases, the probability assigned to a particular binarized symbol that is not updated is <NUM>%.

Referring to <FIG>, an exemplary CABAC based encoder receives syntax elements values <NUM> that are normally non-binary. A binarizer <NUM> receives the syntax elements values <NUM> and based upon the syntax element type <NUM> generates a binary string <NUM>. The syntax element type <NUM> may signal, for example, the input value corresponding to an index term derived for the current block's intra prediction mode; or the input value corresponds to a flag derived for the current block's intra prediction mode. A selector <NUM> selects whether to use a bypass encoding engine <NUM> or a regular encoding engine <NUM> based upon one or more inputs. One of the inputs to the selector <NUM> may include the syntax element type <NUM>. Another of the inputs to the selector <NUM> may include a slice type <NUM>. The slice type <NUM> may include, for example, an I-slice (intra-predicted slice), a P-slice (forward predicted slice), and/or a B-slice (a bi-directional predicted slice). Another of the inputs to the selector <NUM> may be a quantization parameter <NUM>. For example, the statistical behavior of the binarized syntax element value may change based upon the quantization parameter, which is often related to the bit rate of the bitstream. Another one of the inputs to the selector <NUM> may be collected statistics <NUM> from the resulting bitstream <NUM>. The collected statistics <NUM> facilitates the modification of the manner of encoding based upon the bitstream to further improve the encoding efficiency. If the selector <NUM> selects the bypass encoding mode <NUM>, based upon one or more of the inputs, then the binary string <NUM> is encoded using the bypass encoding engine <NUM> to generate the bitstream <NUM>. If the selector <NUM> selects the regular encoding mode <NUM>, based upon one or more of the inputs, then the binary string <NUM> is provided to the regular encoding engine <NUM>, this engine is the arithmetic encoder. Additionally the current probability estimate <NUM> is provided as input to the regular encoding engine by a context modeler <NUM> based upon spatially and/or temporally adjacent syntax elements <NUM> and binary symbols encoded in the past. The regular encoding engine <NUM> generates the bitstream <NUM>. The output of the regular encoding engine <NUM> is used to update the probability of the context modeler <NUM>. The selector <NUM> may also be used to indicate which coded bits should be included in the bitstream <NUM>.

Referring to <FIG>, the bitstream <NUM> may be received by a CABAC based decoder. A selector <NUM> selects whether to use a bypass decoding engine <NUM> or a regular decoding engine <NUM> based upon one or more inputs from the bitstream <NUM>. One of the inputs to the selector <NUM> may include the syntax element type <NUM>. Another one of the inputs to the selector <NUM> may include the slice type <NUM>. Another one of the inputs to the selector <NUM> may be the quantization parameter <NUM>. Another one of the inputs to the selector <NUM> may be the collected statistics <NUM>. If the selector <NUM> selects the bypass decoding mode <NUM>, based upon one or more of the inputs, then the bitstream <NUM> is decoded using the bypass decoding engine <NUM> to generate binary decoded bits <NUM>. If the selector <NUM> selects the regular decoding mode <NUM>, based upon one or more of the inputs, then the bitstream <NUM> is provided to the regular decoding engine <NUM>, this engine is the arithmetic decoder. Additionally the current probability estimate <NUM> is provided as input to the regular decoding engine by a context modeler <NUM> based upon spatially and/or temporally adjacent syntax element values <NUM>. The regular decoding engine <NUM> generates binary decoded bits <NUM>. The output of the regular decoding engine <NUM> is used to update the probability of the context modeler <NUM>. The selector <NUM> may also be used to indicate which binary decoded bits <NUM>, <NUM> should be provided to a debinarizer <NUM>. The debinarizer <NUM> receives the binary decoded input, together with the syntax element type <NUM>, and provides non-binary syntax element values <NUM>.

Claim 1:
A method for encoding an intra prediction mode of a current block using a list of most probable modes, wherein the list of most probable modes comprises more than one intra prediction mode, wherein the list of most probable modes is generated based on an intra prediction mode of a block to the left of the current block and an intra prediction mode of a block to the above of the current block, the method comprising:
encoding, in a bitstream, a flag (<NUM>) having a first value, wherein the first value of the flag indicates the intra prediction mode of the current block is in the list of most probable modes; and
encoding, in the bitstream, an index (<NUM>) indicating where the intra prediction mode of the current block is in the list of most probable modes;
wherein the flag (<NUM>) is encoded into the bitstream by a regular encoding mode of context adaptive binary arithmetic coding,
characterized in that
the index (<NUM>) is encoded into the bitstream by a bypass encoding mode of the context adaptive binary arithmetic coding.