KR102314801B1 - Selective Blending for Entropy Coding in Video Compression - Google Patents

Abstract

An apparatus for decoding transform coefficients using an alphabet of transform coefficient tokens includes a memory and a processor. A first probability distribution corresponding to the first context is selected, and a second probability distribution corresponding to the second context is selected. In response to determining that the second probability distribution includes a probability for the transform coefficient token, the first probability distribution and the second probability distribution are mixed to produce a mixed probability. The transform coefficient tokens are entropy decoded using mixing probabilities. A first probability distribution is defined for all tokens of the alphabet. A second probability distribution is defined for a non-obvious partition of tokens.

Description

Selective Blending for Entropy Coding in Video Compression

Digital video streams may represent video using a sequence of frames or still images. Digital video may be used in a variety of applications including, for example, video conferencing, high-definition video entertainment, video advertisements, or sharing of user-generated videos. A digital video stream may contain large amounts of data and may consume a significant amount of computing or communication resources of a computing device for processing, transmission, or storage of the video data. Various approaches have been proposed to reduce the amount of data in video streams, including compression and other encoding techniques.

Encoding based on motion estimation and compensation may be performed by dividing frames or images into blocks, the blocks being predicted based on one or more predictive blocks of reference frames. The differences (ie residual errors) between the blocks and the prediction blocks are compressed and encoded into a bitstream. The decoder reconstructs the frames or images using the differences and reference frames.

An aspect is an apparatus for decoding transform coefficients using an alphabet of transform coefficient tokens, comprising a memory and a processor. The processor is responsive to selecting a first probability distribution corresponding to a first context, selecting a second probability distribution corresponding to a second context, and determining that the second probability distribution includes a probability for the transform coefficient token. to execute instructions stored in the memory to mix the first probability distribution and the second probability distribution to generate a mixing probability, and to entropy decode the transform coefficient token from the encoded bitstream using the mixing probability. do. A first probability distribution is defined for all tokens of the alphabet. A second probability distribution is defined for a non-obvious partition of tokens. For a non-empty set X, a “non-obvious partition” of set X may be used herein to refer to any partition of X other than set {X}. That is, a “non-obvious partition” of set {X} may be an appropriate subset of set {X}.

Another aspect is a method for coding transform coefficients using an alphabet of tokens. The method includes selecting a first probability distribution corresponding to a first context and defined for some tokens of an alphabet, selecting a second probability distribution corresponding to a second context and defined for non-obvious partitioning of tokens and in response to determining that the first probability distribution comprises a probability for the token and the second probability distribution comprises a second probability for the token, to produce a mixed probability, the first probability distribution and the second probability distribution mixing the two probability distributions, and coding the token using the mixing probability.

Another aspect is an apparatus for decoding transform coefficients using an alphabet of tokens organized into a coefficient token tree, comprising a memory and a processor. The processor is configured to select a first probability distribution corresponding to a first context and defined for internal nodes of the coefficient token tree, and a first probability distribution corresponding to a second context and defined for some but not all internal nodes of the coefficient token tree. select two probability distributions, and execute instructions stored in the memory to decode the token by decoding the first decision related to the first inner node of the coefficient token tree using the mixed probability. The mixed probability is generated by mixing the first probability distribution and the second probability distribution.

These and other aspects of the present disclosure are set forth in the following detailed description of embodiments, the appended claims, and the appended drawings.

[0008] The description herein refers to the accompanying drawings, in which like reference numbers refer to like parts throughout the various drawings.
1 is a schematic diagram of a video encoding and decoding system;
2 is a block diagram of an example of a computing device that may implement a transmitting station or a receiving station;
3 is a diagram of a video stream to be encoded and subsequently decoded;
4 is a block diagram of an encoder in accordance with implementations of the present disclosure;
5 is a block diagram of a decoder in accordance with implementations of the present disclosure;
6 is a diagram illustrating quantized transform coefficients in accordance with implementations of the present disclosure.
7 is a diagram of a coefficient token tree that may be used to entropy code code blocks into a video bitstream, in accordance with implementations of the present disclosure.
8 is a diagram of an example of a tree for binarizing a quantized transform coefficient, in accordance with implementations of the present disclosure.
9 is a flow diagram of a process for encoding a sequence of symbols, according to an implementation of the present disclosure.
10 is a flow diagram of a process for decoding a sequence of symbols, according to an implementation of the present disclosure.
11 is a diagram of an example of a binary tree of conditional probabilities, according to an implementation of the present disclosure.
12 is a flow diagram of a process for entropy coding, according to an implementation of the present disclosure.
13 is a flow diagram of a process for coding transform coefficients using an alphabet of transform coefficient tokens, according to an implementation of the present disclosure.
14 is a diagram of neighbor templates for deriving a context, according to implementations of the present disclosure.

As noted above, compression schemes related to coding video streams divide images into blocks and use one or more techniques to generate a digital video output bitstream to limit the information contained in the output. may include doing The received encoded bitstream can be decoded to reconstruct blocks and source images from limited information. Encoding a video stream or a portion thereof, such as a frame or block, may include using temporal or spatial similarities in the video stream to improve coding efficiency. For example, a current block of a video stream may be encoded based on identifying a difference (residual) between previously coded pixel values and pixel values within the current block. In this way, only the residual, and the parameters used to generate the residual, need be added to the encoded bitstream. The residual may be encoded using a lossy quantization step.

As described further below, the residual block may be in the pixel domain. The residual block may be transformed into the frequency domain to generate a transform block of transform coefficients. The transform coefficients may be quantized to produce a quantized transform block of quantized transform coefficients. The quantized coefficients may be entropy encoded and added to the encoded bitstream. A decoder may receive the encoded bitstream and entropy decode the quantized transform coefficients to reconstruct the original video frame.

[0025] Entropy coding is a technique for “lossless” coding that relies on a probabilistic model to model the distribution of values occurring in an encoded video bitstream. By using probabilistic models based on a measured or estimated distribution of values, entropy Coding can reduce the number of bits required to represent video data close to a theoretical minimum In practice, the actual reduction in the number of bits required to represent video data depends on the accuracy of the probabilistic model, the bits on which the coding is performed may be a function of the number of s, and the arithmetic precision of the fixed-point arithmetic used to perform the coding.

In an encoded video bitstream, many of the bits are either content prediction (eg, inter mode/motion vector coding, intra prediction mode coding, etc.) or residual coding (eg, transform coefficients). is used for Encoders may use techniques to reduce the number of bits consumed for coefficient coding. For example, a coefficient token tree (also referred to as a binary token tree) specifies a range of values with forward-adaptive probabilities for each branch within the token tree. After the token base value is subtracted from the value to be coded and a residual is formed, the block is coded with fixed probabilities. A similar approach is also possible with some modifications including backward-adaptability. Adaptive techniques can change probabilistic models as a video stream is being encoded to adapt to changing characteristics of data. In any case, the decoder is informed (or available) of the probabilistic model used to encode the entropy-coded video bitstream, in order to decode the video bitstream.

As described above, entropy coding a sequence of symbols typically uses a probabilistic model to determine a probability p for the sequence, then uses binary arithmetic coding to map the sequence to a binary codeword at the encoder. and decoding the sequence from the binary codeword at the decoder. The length of the codeword (ie the number of bits) is given by -log(p). The efficiency of entropy coding can be directly related to the probabilistic model. Throughout this specification, log denotes a base 2 logarithmic function, unless otherwise specified.

As used herein, a model may be lossless (entropy) coding, or may be a parameter in lossless (entropy) coding. The model can be any parameter or method that affects the probability estimation for entropy coding. For example, a model may define a probability that will be used to encode and decode a decision at an inner node within a token tree (as described with respect to FIG. 7 below). In this case, the two-pass process for learning the probabilities for the current frame can be simplified to a single-pass process by mixing multiple models as described herein. In another example, the model may define a specific context derivation method. In such a case, implementations according to the present disclosure may be used to automatically blend the coding probabilities generated by a number of such methods. In another example, the model may define an entirely new lossless coding algorithm.

The purpose of context modeling is to obtain probability distributions for subsequent entropy coding engines, such as arithmetic coding, Huffman coding, and other variable-length-to-variable-length coding engines. To achieve good compression performance, multiple contexts may be required. For example, some video coding systems may include hundreds or even thousands of contexts for transform coefficient coding only. Each context may correspond to a probability distribution.

The probability distribution may be learned by a decoder and/or may be included in a header of a frame to be decoded.

Learning means that the decoder's entropy coding engine can adapt to the probability distributions (ie, probability models) of the context model based on the decoded frames. For example, the decoder may use an initial probability distribution that the decoder (eg, the decoder's entropy coding engine) may continuously update as the decoder decodes additional frames. The update of the probabilistic models may ensure that the initial probability distribution is updated to reflect the actual distributions in the decoded frames.

Including the probability distribution in the header may instruct the decoder to use the included probability distribution to decode the next frame, given the corresponding context. The cost (in bits) is associated with including each probability distribution in the header. For example, in a coding system that contains 3000 contexts and encodes a probability distribution (coded as an integer value between 1 and 255) using 8 bits, 24,000 bits are added to the encoded bitstream. These bits are overhead bits. To reduce the number of overhead bits, some techniques may be used. For example, probability distributions for some but not all of the contexts may be included. For example, to reduce overhead bits, prediction schemes may also be used. Even with these overhead reduction techniques, the overhead is non-zero.

[0033] A major design challenge or problem in context modeling is balancing two conflicting goals, which are further described below: 1) improving compression performance by adding more contexts, and 2) to reduce the overhead cost associated with contexts. The problem is particularly relevant when multi-symbol, non-binary alphabets are involved, in part due to the fact that the overhead associated with the context increases as the alphabet size increases.

Implementations according to the present disclosure use selective mixing, so that contexts can be added while limiting the overhead associated with the contexts being added. The context may, for example, define a probability distribution over the alphabet of tokens used to encode the transform coefficients. In selective mixing, a first context model may be used to determine a defined first probability distribution for all tokens, and a second context may be used to determine a second probability distribution for more frequent tokens. The number of more frequent tokens is less than the number of all tokens. In coding the coefficients, selective mixing mixes the first and second probability distributions for more frequent tokens and uses the first probability distribution for the remaining tokens.

Implementations according to the present disclosure may use selective mixing of probabilistic models. Mixed models can be used to encode any value encoded using entropy coding. For example, to entropy code the quantized transform coefficients, two or more probabilistic models may be mixed. Advantages of implementations in accordance with the present disclosure include reduced overhead associated with contexts and improved compression performance. Additionally, using selective mixing, context modeling in a coding system allows some contexts to be derived from context information affecting the overall distribution for the letter E, while affecting only a portion of the distribution for the letter E. It can be designed such that other contexts can be derived from the context information that affects it, thereby reducing the overhead associated with contexts as compared to coding systems that do not use selective mixing.

Mixing for entropy coding in video compression is first described herein with reference to a system in which the teachings may be incorporated.

1 is a schematic diagram of a video encoding and decoding system 100 . The transmitting station 102 may be, for example, a computer having an internal configuration of hardware as illustrated in FIG. 2 . However, other suitable implementations of the transmitting station 102 are possible. For example, the processing of the transmitting station 102 may be distributed among multiple devices.

The network 104 may couple the transmitting station 102 and the receiving station 106 for encoding and decoding of a video stream. Specifically, a video stream may be encoded at a transmitting station 102 , and the encoded video stream may be decoded at a receiving station 106 . Network 104 may be the Internet, for example. Network 104 may also route a local area network (LAN), wide area network (WAN), virtual private network (VPN), cellular telephone network, or video stream from a transmitting station 102 to a receiving station 106 in this example. It may be any other means of transmitting.

In one example, the receiving station 106 may be a computer having an internal configuration of hardware as described in FIG. 2 . However, other suitable implementations of the receiving station 106 are possible. For example, the processing of the receiving station 106 may be distributed among multiple devices.

Other implementations of the video encoding and decoding system 100 are possible. For example, an implementation may omit the network 104 . In other implementations, after the video stream is encoded, it may be stored for later transmission to the receiving station 106 or any other device having memory. In one implementation, the receiving station 106 receives the encoded video stream (eg, over the network 104, a computer bus, and/or some communication path) and stores the video stream for later decoding. In an example implementation, Real Time Transport Protocol (RTP) is used for transmission of encoded video over network 104 . In other implementations, a transport protocol other than RTP may be used, for example, a Hyper Text Transfer Protocol (HTTP)-based video streaming protocol.

[0041] When used in a videoconferencing system, for example, the transmitting station 102 and/or the receiving station 106 may include the ability to both encode and decode a video stream as described below. For example, the receiving station 106 may be a videoconferencing participant, which receives, decodes and views an encoded video bitstream from a videoconferencing server (eg, the transmitting station 102), and furthermore, itself encodes the video bitstream of , and sends it to a video conferencing server for decoding and viewing by other participants.

2 is a block diagram of an example of a computing device 200 that may implement a transmitting station or a receiving station. For example, computing device 200 may implement one or both of transmitting station 102 and receiving station 106 of FIG. 1 . Computing device 200 may be in the form of a computing system including multiple computing devices, or in the form of a single computing device, eg, a mobile phone, tablet computer, laptop computer, notebook computer, desktop computer, and the like.

The CPU 202 of the computing device 200 may be a central processing unit. Alternatively, the CPU 202 may be any other type of device or multiple devices capable of manipulating or processing information that currently exists or is later developed. Although the disclosed implementations may be implemented with a single processor, eg, CPU 202 as shown, advantages of speed and efficiency may be achieved using more than one processor.

Memory 204 in computing device 200 may be a read-only memory (ROM) device or a random access memory (RAM) device in an implementation. Any other suitable type of storage device may be used as memory 204 . Memory 204 may contain code and data 206 that is accessed by CPU 202 using bus 212 . The memory 204 may further include an operating system 208 and application programs 210 , the application programs 210 being at least one that enables the CPU 202 to perform the methods described herein. includes the program of For example, application programs 210 may include applications 1 - N, wherein applications 1 - N further include a video coding application that performs the methods described herein. Computing device 200 may also include secondary storage 214 , which may be, for example, a memory card used with computing device 200 that is mobile. Because video communication sessions may contain a significant amount of information, they may be stored in whole or in part in secondary storage 214 and loaded into memory 204 as needed for processing.

Computing device 200 may also include one or more output devices, such as display 218 . Display 218 may, in one example, be a touch-sensitive display that couples the display with a touch-sensitive element operable to sense touch inputs. Display 218 may be coupled to CPU 202 via bus 212 . Other output devices that allow a user to program or otherwise use computing device 200 may be provided in addition to or as an alternative to display 218 . Where the output device is or includes a display, the display may be displayed in a variety of ways, including a liquid crystal display (LCD), a cathode-ray tube (CRT) display, or a light emitting diode (LED) display, such as an organic LED (OLED) display. can be implemented with

Computing device 200 is also capable of sensing an image, such as an image-sensing device 220 , eg, an image of a user operating computing device 200 , either presently present or later developed. , a camera, or any other image-sensing device 220 . The image-sensing device 220 may be positioned to face a user operating the computing device 200 . In one example, the position and optical axis of the image-sensing device 220 may be configured such that the field of view encompasses the area immediately adjacent the display 218 and in which the display 218 is visible.

Computing device 200 may also be a sound-sensing device 222 , eg, a microphone or any other currently existing or later developed microphone capable of sensing sounds in the vicinity of computing device 200 . It may include or be in communication with a sound-sensing device. The sound-sensing device 222 may be positioned to face a user operating the computing device 200 , and while the user operates the computing device 200 , sounds made by the user, such as speech or other may be configured to receive utterances.

2 shows the CPU 202 and the memory 204 of the computing device 200 as integrated into a single unit, other configurations may be utilized. The operations of the CPU 202 may be distributed across multiple machines, each machine having one or more of the processors, which may be coupled either directly or via a local area or other network. Memory 204 may be distributed across multiple machines, such as network-based memory, or memory in multiple machines performing the operation of computing device 200 . Although shown here as a single bus, bus 212 of computing device 200 may be comprised of multiple buses. In addition, secondary storage 214 may be directly coupled to other components of computing device 200 or may be accessed over a network, such as a single integrated unit, such as a memory card, or multiple memory cards. It may include multiple units. Accordingly, the computing device 200 may be implemented in various configurations.

3 is a diagram of an example of a video stream 300 to be encoded and subsequently decoded. The video stream 300 includes a video sequence 302 . At the next level, the video sequence 302 includes a number of contiguous frames 304 . Although three frames are shown as adjacent frames 304 , the video sequence 302 may include any number of adjacent frames 304 . The adjacent frames 304 may then be further subdivided into individual frames, eg, frame 306 . At the next level, the frame 306 may be divided into a series of segments 308 or planes. Segment 308 may be, for example, subsets of frames that allow for parallel processing. Segments 308 may also be subsets of frames that may separate video data into distinct colors. For example, a frame 306 of color video data may include a luminance plane and two chrominance planes. Segments 308 may be sampled at different resolutions.

Irrespective of whether the frame 306 is divided into segments 308 , the frame 306 is divided into blocks that may include, for example, data corresponding to 16×16 pixels within the frame 306 . (310) can be further subdivided. Blocks 310 may also be arranged to include data from one or more segments 308 of pixel data. Blocks 310 may also be of any other suitable size, such as 4x4 pixels, 8x8 pixels, 16x8 pixels, 8x16 pixels, 16x16 pixels or more.

4 is a block diagram of an encoder 400 in accordance with implementations of the present disclosure. The encoder 400 may be implemented at the transmitting station 102 by providing a computer software program stored in a memory such as, for example, the memory 204, as described above. The computer software program may include machine instructions that, when executed by a processor, such as CPU 202 , cause transmitting station 102 to encode video data in the manner described herein. The encoder 400 may also be implemented, for example, as special hardware included in the transmitting station 102 . The encoder 400 uses the video stream 300 as input to generate an encoded or compressed bitstream 420 in the next stage to perform various functions in the forward path (shown by solid connecting lines). Fields: have an intra/inter prediction stage 402 , a transform stage 404 , a quantization stage 406 and an entropy encoding stage 408 . The encoder 400 may also include a reconstruction path (shown by dashed connecting lines) for reconstructing a frame for encoding of future blocks. In FIG. 4 , the encoder 400 performs the following stages for performing various functions in the reconstruction path; It has an inverse quantization stage 410 , an inverse transform stage 412 , a reconstruction stage 414 and a loop filtering stage 416 . Other structural variants of the encoder 400 may be used to encode the video stream 300 .

When the video stream 300 is presented for encoding, the frame 306 may be processed in units of blocks. In the intra/inter prediction stage 402, blocks may be encoded using intra-frame prediction (also referred to as intra-prediction) or inter-frame prediction (also referred to as inter-prediction) or a combination of the two. have. In any case, a prediction block can be formed. In the case of intra-prediction, all or part of a predictive block may be formed from samples in a previously encoded and reconstructed current frame. For inter-prediction, all or part of a predictive block may be formed from samples in one or more previously constructed reference frames determined using motion vectors.

Next, still referring to FIG. 4 , the predictive block may be subtracted from the current block in an intra/inter prediction stage 402 to produce a residual block (also referred to as a residual). The transform stage 404 transforms the residual into transform coefficients in the frequency domain using, for example, block-based transforms. Such block-based transforms include, for example, Discrete Cosine Transform (DCT) and Asymmetric Discrete Sine Transform (ADST). Other block-based transformations are possible. Also, combinations of different transforms can be applied to a single residual. In one example of application of the transform, the DCT transforms the residual block into the frequency domain in which the transform coefficient values are based on spatial frequency. The lowest frequency (DC) coefficient is at the top left of the matrix, and the highest frequency coefficient is at the bottom right of the matrix. It is worth noting that the size of the prediction block, and thus the size of the resulting residual block, may be different from the size of the transform block. For example, a predictive block may be divided into smaller blocks to which separate transforms are applied.

The quantization stage 406 transforms the transform coefficients into discrete quantum values, using a quantizer value or quantization level, which are referred to as quantized transform coefficients. For example, the transform coefficients may be truncated by dividing by the quantizer value. The quantized transform coefficients are then entropy encoded by an entropy encoding stage 408 . Entropy coding can be performed using any number of techniques, including tokens and binary trees. The entropy-encoded coefficients are then stored in a compressed bitstream ( 420) is output. Information for decoding a block may be entropy coded into block, frame, slice and/or section headers within the compressed bitstream 420 . The compressed bitstream 420 may also be referred to as an encoded video stream or an encoded video bitstream, and these terms will be used interchangeably herein.

The reconstruction path of FIG. 4 (shown by dashed lines) is the same reference frame for both the encoder 400 and the decoder 500 (described below) to decode the compressed bitstream 420 . can be used to ensure that the fields and blocks are used. The reconstruction path inverse quantizes the quantized transform coefficients in an inverse quantization stage 410 and inverse transforms the inverse quantized transform coefficients in an inverse transform stage 412 to produce a differential residual block (also referred to as a differential residual). functions similar to those occurring during the decoding process discussed in more detail below, including In the reconstruction stage 414 , the prediction block predicted in the intra/inter prediction stage 402 may be added to the differential residual to produce a reconstructed block. A loop filtering stage 416 may be applied to the reconstructed block to reduce distortion such as blocking artifacts.

Other variants of the encoder 400 may be used to encode the compressed bitstream 420 . For example, the non-transform based encoder 400 can quantize the residual signal directly without the transform stage 404 for certain blocks or frames. In another implementation, the encoder 400 may have a quantization stage 406 and an inverse quantization stage 410 combined into a single stage.

5 is a block diagram of a decoder 500 in accordance with implementations of the present disclosure. The decoder 500 may be implemented at the receiving station 106 by, for example, providing a computer software program stored in the memory 204 . The computer software program, when executed by a processor, such as CPU 202, may include machine instructions that cause receiving station 106 to decode video data in the manner described in FIGS. 8 and 9 below. The decoder 500 may also be implemented in hardware included in, for example, the transmitting station 102 or the receiving station 106 . Similar to the reconstruction path of the encoder 400 discussed above, the decoder 500 is, in one example, the following to perform various functions to generate an output video stream 516 from the compressed bitstream 420 . Stages: entropy decoding stage 502 , inverse quantization stage 504 , inverse transform stage 506 , intra/inter-prediction stage 508 , reconstruction stage 510 , loop filtering stage 512 and deblocking filtering stage (514). Other structural variants of the decoder 500 may be used to decode the compressed bitstream 420 .

When the compressed bitstream 420 is presented for decoding, the data elements in the compressed bitstream 420 are decoded by the entropy decoding stage 502 to produce a set of quantized transform coefficients. can The inverse quantization stage 504 inverse quantizes the quantized transform coefficients (eg, by multiplying the quantized transform coefficients by a quantizer value), and the inverse transform stage 506 inversely quantizes the transform using the selected transform type. Inverse transform the coefficients to produce a differential residual, which may be identical to that produced by inverse transform stage 412 in encoder 400 . Using the header information decoded from the compressed bitstream 420 , the decoder 500 uses an intra/inter-prediction stage 508 , for example, the encoder 400 in an intra/inter prediction stage 402 . ) can generate the same prediction block as generated in . In the reconstruction stage 510 , the prediction block may be added to the differential residual to produce a reconstructed block. A loop filtering stage 512 may be applied to the reconstructed block to reduce blocking artifacts. Other filtering may be applied to the reconstructed block. In one example, a deblocking filtering stage 514 is applied to the reconstructed block to reduce blocking distortion, and the result is output as an output video stream 516 . Output video stream 516 may also be referred to as a decoded video stream, and these terms will be used interchangeably herein.

Other variants of the decoder 500 may be used to decode the compressed bitstream 420 . For example, the decoder 500 can generate the output video stream 516 without the deblocking filtering stage 514 . In some implementations of the decoder 500 , a deblocking filtering stage 514 is applied before the loop filtering stage 512 . Additionally or alternatively, the encoder 400 includes a deblocking filtering stage in addition to the loop filtering stage 416 .

6 is a diagram 600 illustrating quantized transform coefficients in accordance with implementations of the present disclosure. Diagram 600 shows a current block 620 , a scan order 602 , a quantized transform block 604 , a non-zero map 606 , an end-of-block map 622 , and a sign map 626 . The current block 620 is illustrated as a 4x4 block. However, any block size is possible. For example, the current block may have a size (ie dimensions) of 4x4, 8x8, 16x16, 32x32, or any other square or rectangular block size. The current block 620 may be a block of the current frame. In another example, the current frame may be partitioned into segments (eg, segments 308 of FIG. 3 , tiles, etc.) each comprising a set of blocks, where the current block is a block of partitioning.

The quantized transform block 604 may be a block having a size similar to that of the current block 620 . The quantized transform block 604 includes non-zero coefficients (eg, coefficient 608 ) and zero coefficients (eg, coefficient 610 ). As described above, the quantized transform block 604 includes quantized transform coefficients for the residual block corresponding to the current block 620 . Also, as described above, the quantized transform coefficients are entropy coded by an entropy-coding phase, such as entropy coding stage 408 of FIG. 4 .

Entropy coding a quantized transform coefficient is a context model (probabilistic context model, probability) that provides estimates of conditional probabilities for coding a binary symbol of a binarized transform coefficient, as described below with respect to FIG. Also referred to as models, models and contexts). When entropy coding the quantized transform coefficients, additional information can be used as a context for selecting a context model. For example, magnitudes of previously coded transform coefficients may be used, at least in part, to determine a probabilistic model.

[0063] To encode a transform block, a video coding system traverses the transform block in scan order, and as the quantized transform coefficients are each traversed (ie, visited), it encodes (eg, entropy) the quantized transform coefficients. can be encoded). In a zig-zag scan order, such as scan order 602, the upper left corner of the transform block (also known as the DC coefficient) is traversed and encoded first, and the next coefficient in the scan order (i.e., corresponding to the position marked "1") transform coefficients) are traversed and encoded, and so on. In the zig-zag scan order (ie, scan order 602 ), some quantized transform coefficients above and to the left of the current quantized transform coefficient (eg, the transform coefficient to be encoded) are traversed first. Other scan sequences are possible. A one-dimensional structure (eg, an array) of quantized transform coefficients may result from a traversal of a two-dimensional quantized transform block using a scan order.

In some examples, encoding the quantized transform block 604 determines a non-zero map 606 that indicates that the quantized transform coefficients of the quantized transform block 604 are zero and non-zero. may include The non-zero coefficient and the zero coefficient may be represented by values of 1 and 0, respectively, in the non-zero map. For example, non-zero map 606 contains non-zero 607 at Cartesian positions (0, 0) corresponding to coefficients 608 and Cartesian positions (2, 0) corresponding to coefficients 610 . ) to zero (608).

In some examples, encoding the quantized transform block 604 may include generating and encoding an end-of-block map 622 . The end-of-block map indicates whether the non-zero quantized transform coefficient of the quantized transform block 604 is the last non-zero coefficient for a given scan order. If the non-zero coefficient is not the last non-zero coefficient in the transform block, it may be indicated as binary bit 0 in the end-of-block map. On the other hand, if the non-zero coefficient is the last non-zero coefficient in the transform block, it may be represented by the binary value 1 in the end-of-block map. For example, since the quantized transform coefficient corresponding to the scan position 11 (ie, the last non-zero quantized transform coefficient 628 ) is the last non-zero coefficient of the quantized transform block 604 , it is equal to 1 indicated by the block-end value 624; All other non-zero transform coefficients are denoted as zeros.

In some examples, encoding the quantized transform block 604 may include generating and encoding a sign map 626 . The sign map 626 indicates which non-zero quantized transform coefficients of the quantized transform block 604 have positive values and which quantized transform coefficients have negative values. Transform coefficients that are zero need not be represented in the sign map. The sign map 626 illustrates the sign map for the quantized transform block 604 . In the sign map, negative quantized transform coefficients may be represented by zeros, and positive quantized transform coefficients may be represented by ones.

7 is a diagram of a coefficient token tree 700 that may be used to entropy code blocks into a video bitstream, in accordance with implementations of the present disclosure. Coefficient token tree 700 is referred to as a binary tree because, at each node of the tree, one of two branches must be taken (ie, traversed). The coefficient token tree 700 includes a root node 701 and a node 703 corresponding to nodes denoted A and B, respectively.

As described above with respect to FIG. 6 , when an End-of-Block (EOB) token is detected for a block, coding of the coefficients in the current block may end, and the remaining coefficients in the block are inferred to be zero. can be As such, coding of EOB positions may be an integral part of a coefficient in a video coding system.

[0069] In some video coding systems, the binary decision to determine whether the current token is equal to (or not equal to) the EOB token of the current block is immediately after the non-zero coefficient is decoded or the first scan position (DC) is coded in In an example, for a transform block of size MxN, where M represents the number of columns and N represents the number of rows in the transform block, the maximum number of codings for whether the current token is equal to the EOB token is MxN and same. M and N may take values such as 2, 4, 8, 16, 32 and 64. As described below, the binary decision corresponds to the coding of "1" bits corresponding to the decision to move from the root node 701 to the node 703 in the coefficient token tree 700. Here, the "bit coding" " can mean the output or generation of a bit in a codeword representing a transform coefficient to be encoded. Similarly, "bit decoding" is a quantized transform that is decoded such that the bit corresponds to a branch traversed in the coefficient token tree. may mean reading (eg, from an encoded bitstream) bits of a codeword corresponding to a coefficient.

Using the coefficient token tree 700 , a quantized coefficient (eg, coefficients 608 , 610 of FIG. 6 ) of a quantized transform block (eg, quantized transform block 604 of FIG. 6 ) ), a string of binary digits is generated.

In an example, the quantized coefficients in an NxN block (eg, quantized transform block 604 ) follow a prescribed scan order (eg, scan order 602 in FIG. 6 ) in 1D( 1 - dimension) consists of an array (here, array u). N may be 4, 8, 16, 32 or any other value. The quantized coefficient at the i-th position of the 1D array may be referred to as u[i], where i = 0, ... , N*N-1. u[i],… The starting position of the last run of zeros in , u[N*N-1] may be denoted as eob. If u[N*N-1] is not zero, eob may be set to the value N*N. That is, when the last coefficient of the 1D array u is not zero, eob may be set to the value N*N. Using the example of Figure 6, the 1D array u has entries u[] = [-6, 0, -1, 0, 2, 4, 1, 0, 0, 1, 0, -1, 0, 0, 0, 0]. The values in each of u[i] are quantized transform coefficients. The quantized transform coefficients of the 1D array u may also be referred to herein simply as “coefficients” or “transform coefficients.” The coefficient at position i = 0 (ie, u[0] = -6) is DC Corresponds to the coefficient In this example, eob is equal to 12, since there are no non-zero coefficients after the zero coefficient at position 12 of the 1D array u.

[0072] Coefficients u[i], ... for i = 0 to N*N-1 , u[N*N-1], a token t[i] is generated at each position i <= eob. The token t[i] for i < eob may indicate the size and/or size range of the corresponding quantized transform coefficient in u[i]. The token for the quantized transform coefficient in eob may be EOB_TOKEN, which is a token indicating that the 1D array u contains no non-zero coefficients (inclusive) after the eob position (including 0). That is, t[eob] = EOB_TOKEN indicates the EOB position of the current block. Table 1 below provides an example list of token values excluding EOB_TOKEN and their corresponding names according to implementations of the present disclosure.

In an example, the quantized coefficient values are taken as signed 12-bit integers. To represent the quantized coefficient value, the range of 12-bit signed values can be divided into 11 tokens (Token 0 - Token 10 in Table 1) plus an end-of-block token (EOB_TOKEN). The coefficient token tree 700 may be traversed to generate a token representing the quantized coefficient value. The result of traversing the tree (i.e., bit string) may then be encoded into a bitstream (such as bitstream 420 in FIG. 4) by the encoder as described for entropy encoding stage 408 in FIG. have.

Count token tree 700 includes tokens EOB_TOKEN (token 702), ZERO_TOKEN (token 704), ONE_TOKEN (token 706), TWO_TOKEN (token 708), THREE_TOKEN (token 710) ), FOUR_TOKEN (token (712)), CAT1 (token (714) that is DCT_VAL_CAT1 in Table 1), CAT2 (token that is DCT_VAL_CAT2 in Table 1 (716)), CAT3 (token (718) that is DCT_VAL_CAT3 in Table 1), CAT4 (token 720 that is DCT_VAL_CAT4 in Table 1), CAT5 (token 722 that is DCT_VAL_CAT5 in Table 1), and CAT6 (token 724 that is DCT_VAL_CAT6 in Table 1). As can be seen, the coefficient token tree maps map a single quantized coefficient value to a single token, such as one of tokens 704 , 706 , 708 , 710 and 712 . Other tokens, such as tokens 714, 716, 718, 720, 722 and 724, represent ranges of quantized coefficient values. For example, a quantized transform coefficient having a value of 37 may be represented by a token DCT_VAL_CAT5 (token 722 in FIG. 7 ).

The default value of a token is defined as the smallest number in its range. For example, the default value of token 720 is 19. Entropy coding can form a residual by identifying a token for each quantized coefficient and subtracting a base value from the quantized coefficient if the token represents a range. For example, to enable the decoder to reconstruct the original quantized transform coefficients, by including the token 720 and the residual value of 1 (ie 20 minus 19) in the encoded video bitstream, the value of 20 A quantized transform coefficient may be represented. The end of the block token (ie, token 702 ) signals that no more non-zero quantized coefficients remain in the transformed block data.

[0076] In another example of token values for coefficient coding, Table 1 is split into two, where the first (head) set includes ZERO_TOKEN, ONE_NOEOB, ONE_EOB, TWO_NOEOB, and TWO_EOB, and the second (tail) The set includes TWO_TOKEN, THREE_TOKEN, FOUR_TOKEN, DCT_VAL_CAT1, DCT_VAL_CAT2, DCT_VAL_CAT3, DCT_VAL_CAT4, DCT_VAL_CAT5 and DCT_VAL_CAT6. The second (tail) set is used only when TWO_EOB or TWO_NOEOB in the first (head) set is encoded or decoded. Tokens ONE_NOEOB and TWO_NOEOB correspond to ONE_TOKEN and TWO_TOKEN, respectively, when traversal of coefficient token tree 700 begins at node 703 (ie, when checkEob = 0). The tokens ONE_EOB and TWO_EOB may be or correspond to, respectively, ONE_TOKEN and TWO_TOKEN (ie, a traversal of the coefficient token tree 700 starting at the root node 701 ). Tree traversal and checkEob of coefficient token tree 700 are described further below.

Coefficient token tree 700 may be used to encode or decode token t[i] by using a binary arithmetic coding engine (eg, by entropy encoding stage 408 of FIG. 4 ). The coefficient token tree 700 is traversed starting at the root node 701 (ie, the node marked A). Traversing the coefficient token tree generates a bit string (codeword) to be encoded into a bitstream using, for example, binary arithmetic coding. The bit string is a representation of the current coefficient (ie, the quantized transform coefficient being encoded).

[0078] If the current coefficient is zero and there are no more non-zero values for the remaining transform coefficients, the token 702 (ie, EOB_TOKEN) is added to the bitstream. This is the case, for example, for the transform coefficients at scan order position 12 in FIG. 6 . On the other hand, if the current coefficient is non-zero, or if there is a non-zero value among any remaining coefficients of the current block, a "1" bit is added to the codeword, and the traversal is performed at node 703 (i.e., node marked B). At Node B, the current coefficient is tested to see if it is equal to zero. If so, the left branch is taken and, accordingly, a token 704 representing the value ZERO_TOKEN and bit “0” is added to the codeword. Otherwise, a bit "1" is added to the codeword, and the traversal passes to node C. At node C, the current coefficient is tested to see if it is greater than 1. If the current coefficient is equal to 1, the left branch is taken and a token 706 representing the value ONE_TOKEN is added to the bitstream (ie, a “0” bit is added to the codeword). , the traversal goes to node D and checks the value of the current coefficient against the value 4. If the current coefficient is less than or equal to 4, the traversal goes to node E and a "0" bit is added to the codeword. At E, a test may be made for equality with the value “2.” If true, a token 706 representing the value “2” is added to the bitstream (ie, bit “0” is added to the codeword). Otherwise, at node F, the current coefficient is the value “3” or the value “4”, and the token 710 (ie, “0” is added to the codeword) or token 712 (ie bit “1”). added to this codeword) as appropriate against the bitstream, and so on.

In essence, a “0” bit is added to the codeword upon traversal to the left child node, and a “1” bit is added to the codeword upon traversal to the right child node. A similar process is performed by the decoder when decoding a codeword from a compressed bitstream. The decoder reads the bits from the bitstream. When the bit is "1", the coefficient token tree is traversed to the right, and when the bit is "0", the tree is traversed to the left. The decoder then reads the next bit and repeats the process until a traversal of the tree reaches a leaf node (ie token). As an example, to encode the token t[i] = THREE_TOKEN starting from the root node (ie, root node 701 ), the binary string 111010 is encoded. As another example, decoding codeword 11100 results in the token TWO_TOKEN.

Note that the correspondence between the “0” and “1” bits for the left and right child nodes is merely a rule used to describe the encoding and decoding processes. In some implementations, a different rule may be used, for example, "1" corresponds to a left child node, and "0" corresponds to a right child node. As long as both the encoder and decoder adopt the same rules, the processes described herein apply.

[0081] Since EOB_TOKEN is possible only after non-zero coefficients, when u[i-1] is zero (ie, when the quantized transform coefficient at position i-1 of 1D array u is equal to zero), The decoder can infer that the first bit must be 1. When traversing the tree, zero transform coefficients (eg, the transform coefficients at zig-zag scan order position 1 in FIG. 6) followed by transform coefficients (eg, at zig-zag scan order position 2 in FIG. 6) transform coefficient), the first bit should be 1, since the traversal needs to move from the root node 701 to the node 703.

Accordingly, the binary flag checkEob may be used to instruct the encoder and decoder to skip encoding and decoding of the first bit following from the root node in the coefficient token tree 700 . In effect, when the binary flag checkEob is zero (ie, indicating that the root node should not be checked), the root node 701 of the coefficient token tree 700 is skipped and node 703 is to be visited for traversal. It becomes the first node of the coefficient token tree 700 . That is, when the root node 701 is skipped, the encoder may skip encoding, the decoder may skip decoding, and infer the first bit (ie, binary bit “1”) of the encoded string. have.

[0083] When starting to encode or decode a block, the binary flag checkEob may be initialized to 1 (ie, indicating that the root node should be checked). The following steps illustrate an example process for decoding quantized transform coefficients in an NxN block.

[0084] In step 1, the binary flag checkEob is set to zero (ie, checkEob = 0), and the index i is also set to zero (ie, i = 0).

[0085] In step 2, (1) use the entire coefficient token tree (ie, starting at the root node 701 of the coefficient token tree 700) if the binary flag checkEob is equal to 1; or (2) the token t[i] is decoded by using a partial tree (eg, starting at node 703 ) where EOB_TOKEN is skipped if checkEob is equal to 0.

[0086] In step 3, if token t[i] = EOB_TOKEN, the quantized transform coefficients u[i], . . . , u[N*N-1] are all zeros, and the decoding process is terminated; Otherwise, if necessary (ie, t[i] is not equal to ZERO_TOKEN), additional bits may be decoded and u[i] may be reconstructed.

[0087] In step 4, if u[i] is equal to zero, the binary flag checkEob is set to 1, otherwise checkEob is set to 0. That is, checkEob may be set to a value (u[i]! = 0).

In step 5, the index i is incremented (ie, i = i + 1).

[0089] In step 6, steps 2 - 5 are repeated until all quantized transform coefficients are decoded (ie, index i = N*N) or until EOB_TOKEN is decoded.

[0090] In step 2 above, decoding the token t[i] comprises determining the context ctx, determining a binary probability distribution (ie, model) from the context ctx, and using the determined probability distributions to coefficient using the Boolean arithmetic code to decode the path from the root node to the leaf node of the token tree 700 . The context ctx may be determined using the method of context derivation. The method of context derivation is to determine the context ctx, block size, plane type (ie luminance or chrominance), position i and previously decoded tokens t[0], . . . , t[i-1] may be used. Other criteria may be used to determine the context ctx. A binary probability distribution may be determined for any internal node of the coefficient token tree 700 starting from the root node 701 when checkEOB = 1 or starting from the node 703 when checkEOB = 0.

[0091] In some encoding systems, given the context ctx, the probability used to encode or decode token t[i] may be fixed and may not be adapted to a picture (ie, a frame). For example, the probability may be a default value defined for a given context ctx, or the probability may be coded (ie, signaled) as part of a frame header for that frame. It can be expensive to code the probabilities for every respective context in the coding of a frame. Thus, the encoder may analyze, for each context, whether it is beneficial to code the context's associated probability in the frame header, and may signal its determination to the decoder using a binary flag. Moreover, coding probabilities for a context may use prediction to reduce cost (eg, cost of bit rate), where the prediction may be derived from probabilities of the same context within a previously decoded frame.

8 is a diagram of an example of a tree 800 for binarizing a quantized transform coefficient, in accordance with implementations of the present disclosure. Tree 800 is a binary tree that may be used to binarize quantized transform coefficients in some video coding systems. Tree 800 may be used by a video coding system that uses the steps of binarization, context modeling, and binary arithmetic coding for encoding and decoding of quantized transform coefficients. The process may be referred to as context-adaptive binary arithmetic coding (CABAC). For example, to code the quantized transform coefficient x, the coding system may perform the following steps. The quantized transform coefficient x may be any of the coefficients of the quantized transform block 604 of FIG. 6 (eg, coefficient 608 ).

In the binarization step, the coefficient x is first binarized into a binary string using the tree 800 . The binarization process may binarize the unsigned value of the coefficient x. For example, binarizing coefficient 628 (ie, value -1) binarizes value 1 . This results in traversal of tree 800 and creation of binary string 10 . Each of the bits of the binary string 10 is referred to as a bin.

[0094] In the context derivation step, for each bin to be coded, a context is derived. The context includes information such as block size, plane type (i.e., luminance or chrominance), block position of coefficient x, and previously decoded coefficients (e.g., left and/or above neighbor coefficients (using if possible))). Other information may be used to derive the context.

[0095] In the binary arithmetic coding step, given a context, a bin is coded into a binary codeword, eg, using a binary arithmetic coding engine, along with a probability value associated with the context.

[0096] The steps of coding the transform coefficients may include what is referred to as a context update. In the context update step, after the bin is coded, the probability associated with the context is updated to reflect the value of the bin.

[0097] To code (ie, encode or decode) ^{a sequence x n of length n, a mixture of probabilistic models is now described.} For simplicity, two models are used. However, the present disclosure is not so limited, and any number of models may be mixed.

-Log [0098] binary arithmetic coding engine given the sequence x ⁿ probability of p (x ⁿ⁾ of symbols, designed preferred entropy coding engine, for example, is good from the probability p (x ⁿ⁾ the length (p (x ⁿ⁾ ) to create a binary string. Since the length of a string is an integer, “ ^{a binary string of length -log(p(x n} ))” means a binary string whose length is the smallest integer greater than -log(p(x ^{n )).} Here, when referring to a sequence of symbols, a superscript of i refers to a sequence having a length of i symbols, and a subscript of i refers to a symbol at position i in the sequence. For example, x ⁵ refers to a sequence of 5 symbols, such as 11010; On the other hand, x ₅ refers to the symbol of the fifth position, such as the last 0 in the sequence 11010. Thus, the sequence x ⁿ is x ⁿ = x ₁ x ₂ ... It can be expressed as x _{n .}

As used herein, probability values such as probability p(x ^{i ) of subsequence x i} may have floating-point or fixed-point representations. Thus, operations applied to these values may use floating-point arithmetic or fixed-point arithmetic.

[00100] Given two probabilities p ₁ (x ⁿ ) and p ₂ (x ⁿ _{) such that p 1} (x ⁿ ) < p ₂ (x ⁿ ), the probability p ₁ (x ⁿ ) is the probability p ₂ ( x ⁿ ) resulting in a codeword not shorter than That is, a smaller probability typically produces a longer codeword than a larger probability.

[00101] In video coding, the underlying probabilistic model from which symbols are emitted is typically unknown and/or likely too complex or too expensive to fully describe. Therefore, designing a good model for use in entropy coding can be a difficult problem in video coding. For example, a model that works well for one sequence may perform poorly on another. That is, given a first model and a second model, some sequences may be better compressed using the first model, while other sequences may be better compressed using the second model.

In some video systems, it is possible to code an optimal model for encoding a sequence (ie, a signal in an encoded bitstream). For example, given a sequence to be encoded, the video system may encode the sequence according to all or a subset of the available models, and then select the model that gives the best compression result. That is, it is possible to code the selection of a particular model among a set of more than one model for a sequence. In such a system, a two-pass process can be performed implicitly or explicitly: the first pass is to determine the optimal model, and the second pass is to encode using the optimal model. For example, a two-pass process may not be feasible in real-time applications and other delay-sensitive applications.

As mentioned above, multiple models (ie, models 1, ..., M) may be available for entropy coding. To allow a sequence of symbols to be compressed without loss of information, mixing a finite number of models for arithmetic coding may be as good as choosing the one asymptotically best. This comes from the fact that the log function is a concave function and the -log function is a convex function.

[00104] From the above, and a finite sequence of length n x ⁿ = x ₁ x ₂ ... For x _n , inequality (1) is:

[00105] In the inequality (1), w _k denotes the weighting factor of the kth model, and p _k (x ^{n ) denotes} the joint probability of x n given by the model k. As described above, given as inputs a probability p _k (x ⁿ ) (ie a probability given by a model k of a ^{sequence x n ) and x n} , the entropy coding engine ^{converts x n} to -logp _k (x ⁿ ) It can be mapped to a binary codeword of approximately the same length as .

)을 행한 후에 선형 합의 로그를 행하는 것은 모델들 1, …, M의 확률들의 로그들(logp_k(xⁿ))을 행한 후에 동일한 가중 인자들{w_k}을 사용하여 선형 합을 수행하는 것보다 항상 작거나 같다는 것이다. 즉, 부등식의 좌측은 항상 부등식의 우측 이하이다. [00106] In inequality (1), the linear (i.e. weighted) sum of probabilities for the available models (i.e.,

), then doing logarithms of the linear sum is the model 1, ... , is always less than or equal to performing the linear summation using the same weighting factors {w _{k } after doing logp k} (x ⁿ )) of the probabilities of M. That is, the left side of the inequality is always less than or equal to the right side of the inequality.

[00107] Also, from inequality (1), given M models, before entropy coding the symbol, models 1, ... , it becomes more advantageous to mix the probabilities of M. That is, it may be advantageous to mix the probabilities of multiple models before entropy coding, rather than selecting models according to probabilities and using each model to individually code a sequence of bits. Mixing separate models has the potential to improve compression performance (ie, reduce compression ratio), and is no worse than choosing and coding the best model and then coding a sequence using the selected model.

[00108] The probability p _k (x ⁿ ) is the joint probability of the ^{sequence x n.} Mixing has been found of limited use in video coding, at least if used, because co-coding x ^{n can result in significant delays in processing and high computational complexity.}

[00109] For any subsequence of length i of ^{sequence x n with} 1 ≤ i ≤ n _{, probability p k} (x ⁱ ) denotes the probability of ^{subsequence x i} estimated by using model k, where k = It is 1,2. Using the corresponding weighting factor w _k for each model, the two models can be mixed using equation (2).

는 서브시퀀스 xⁱ의 혼합 확률이다. 따라서, 혼합은 각각의 서브시퀀스 xⁱ에 대해 부분(또는 중간) 결과들을 생성할 수 있다. 서브시퀀스 xⁱ는 xⁱ = x₁ x₂ x₃ … x_i이다. 제1 모델(즉, k = 1)은 서브시퀀스 확률 p₁(xⁱ)을 생성하고; 제2 모델(즉, k = 2)은 서브시퀀스 확률 p₂(xⁱ)를 생성한다.[00110] In equation (2),

is the mixing probability of the subsequence x ^{i .} Thus, mixing may produce partial (or intermediate) results for ^{each subsequence x i .} Subsequence x ⁱ is x ⁱ = x ₁ x ₂ x ₃ … x _i . The first model (ie, k = 1) produces a subsequence probability p ₁ (x ⁱ ); The second model (ie, k = 2) produces a subsequence probability p ₂ (x ⁱ ).

[00111] In the example, and as it may not be known, a simple mixture may be used a priori as to which model should have priority. For example, a uniform weight may be used. That is, the weighting factors w _k may be chosen such that _{w k = 1/2.} Therefore, equation (2) can be rewritten as:

는 서브시퀀스의 확률이다. 그러나, 산술 코딩은 심벌 단위에 기초하여(즉, 심벌들의 시퀀스들에 기초하지 않음) 수행된다. 따라서, 혼합 확률

는 엔트로피 코딩을 위해 직접 사용될 수 없다. 이는 혼합 확률

를 아래에서 설명되는 바와 같은 조건부 확률들의 곱으로 변환함으로써 해결될 수 있다. 혼합 확률

자체는 조건부 확률이라는 것이 또한 주의되며, 이는 이전 심벌들이 서브시퀀스 x^i-1을 야기한다면, 포지션 i에서 특정 값을 갖는 심벌의 확률이다. 즉, 혼합 확률

는 방정식 (4)에 의해 주어질 수 있다:[00112] Mixed Probability

is the probability of the subsequence. However, arithmetic coding is performed on a per-symbol basis (ie, not on sequences of symbols). Therefore, mixed probability

cannot be used directly for entropy coding. This is a mixed probability

can be solved by transforming n into a product of conditional probabilities as described below. mixed probability

It is also noted that itself is a conditional probability, which is the probability of a symbol having a certain value at position i if the ^{previous symbols result in a subsequence x i-1 .} i.e. mixed probability

can be given by equation (4):

[00113] Use the basic conditional probability formula P(A│B) = P(A∩B)/P(B), where P(A∩B) is the probability that both events A and B will occur, Equation (4) can be rewritten as Equation (5).

[00114] It is noted that since subsequence x ⁱ contains subsequence x ^i-1 and has symbol x _i , the mixing probability that both _{x i} and x ^i-1 occurs is equal to the mixing probability of only ^{x i} .

[00115] Equation (5) can be rewritten using equation (3). That is, each of the subsequence mixing probabilities (ie, numerator and denominator) of equation (5) can be rewritten with respect to model probabilities. Equation (5) can be rewritten as Equation (6).

및

)를 승산하여, 방정식 (7)이 획득된다:[00116] A factor equal to 1 each in the first and second quantities in equation (6) (i.e., each

and

), the equation (7) is obtained:

[00117] Equation (7) can be written as Equation (8).

)을 사용하여 시퀀스가 인코딩(또는 디코딩)된다.[00118] _{It is noteworthy that the conditional probabilities of p 1} (x _i | ^{x i-1} ) and p ₂ (x _i | ^{x i-1} ) are available as a result of encoding of the sequence up to the i-th symbol. These conditional probabilities are available because entropy encoding encodes one symbol at a time and produces a probability for the codeword (growing up to and including _{x i ) for every each symbol.} In implementations according to the present disclosure, the conditional probabilities are mixed, and then the mixed probabilities (ie,

) to encode (or decode) the sequence.

및

와 각각 동일한 가중치들이며, p₁(x_i│x^i-1) 및 p₂(x_i│x^i-1)는

및

과 각각 동일하다. 따라서, 혼합 확률

는 이제 제1 모델의 조건부 확률(즉, p₁(x_i│x^i-1))과 제2 모델의 조건부 확률(즉, p₂(x_i │x^i-1))의 선형 조합으로서 표현되고, 여기서, 조건부 확률들 각각은 각각의 가중 인자와 승산된다. [00119] In equation (8), w _i,1 and w _i,2 are

and

are the same weights as , respectively, and p ₁ (x _i │x ^i-1 ) and p ₂ (x _i │x ^i-1 ) are

and

are the same as each Therefore, mixed probability

is now expressed as a linear combination of the conditional probability of the first model (ie p ₁ (x _i | ^{x i-1} )) and the conditional probability of the second model (ie p ₂ (x _i | ^{x i-1 ))} where each of the conditional probabilities is multiplied by a respective weighting factor.

[00120] When the joint distributions were mixed using equation (3), uniform weighting factors (ie, 1/2) were used. However, when conditional probabilities are mixed (as in equation (8)), the weights (i.e. w _i,1 for the first model and w _i,2 for the second model) may no longer be uniform. have. Weights for the conditional probability of the first model, w _{i, 1} are given claim by x ^i-1 joint probability and the second model is given by a combination of x ^i-1, the probability given by the first model, the first model x It is equal to dividing by the sum of the joint probabilities of ^i-1. The same is true for the _{weight w i,2 .} In equation (8), for a subsequence x ^i-1 , the first model gives a first probability, the second model gives a second probability, and x ^i-1 gives the conditional probability of a given x _{i .} The weighting factor is equal to the probability given by each of the first model and the second model divided by the sum of the joint probabilities given by both models. That is, in a mixture of conditional probabilities, for example, if the first model ^{gives a higher probability for subsequence x i-1} , the first model has a higher weighting factor (i.e., the weighting factor of the second model) weight w _i,1 ).

[00121] The joint probabilities are real numbers, and _{the calculation of the weights w i,1} and w _i,2 involves division of the real numbers. Thus, _{computing the weights w i,1} and w _i,2 can be complex and expensive. It is desirable to approximate the weights w _i,1 and w _i,2 to fixed-point representations, so that, for example, the exact number of bits representing each of the weights can be known and division operations to be avoided. can

As described above, there is a correlation and/or relationship between the probability of the codeword and the length of bits the codeword generates using the probability. That is, the length of the codeword (ie the number of bits) is _{given by -log 2} (p). The lengths of the codewords generated by each model can be used to approximate the _{weights w i,1} and w _{i,2 .} That is, -log(p _k (x ^i-1 )) is the _{codeword length l k} (x ^i- ) in bits resulting from using model k(k = 1, 2) to encode ^{x i-1 . 1} ) can be approximated by Thus, the weight w _i,1 (and for the weight w _i,2 ) can be approximated using equation (9).

를 제거함으로써 결과로 나올 수 있다. [00123] When l ₂ (i-1) is _{equal to l 1} (i-1), w _i,1 = w _i,2 = 0.5. Without loss of generality, standing, l _{1 (i-1)} When more than the small household l ₂ (i-1), equation (9) from the denominator and numerator After expanding the denominator

can be obtained by removing

_{[00124] To determine a length l k} (x ⁱ ) according to a model k of a subsequence of length i, a virtual encoding process can be used. A virtual encoding process is a process that performs coding steps but does not generate actual codewords or output bits into an encoded bitstream. _{Since the purpose of some applications is to estimate l k} (x ⁱ ), which is interpreted as bitrate (or simply rate), the virtual encoding process may be considered or referred to as a rate estimation process. A virtual encoding process using a probabilistic model computes or estimates the codeword length for a sequence. The codeword length may be determined (ie, measured) with or without generating a codeword. For example, at time instance i, ^{coding the sequence x i-1} using the first model produces a codeword of length l ₁ (i-1), and using the second model produces a codeword of length l ₂ ( The codeword of i-1) is generated. In an example, multiple virtual encoders may be available and executed in parallel. For example, a standard rate estimator for an arithmetic encoder may be available for each model. Each rate estimator may provide (or may be used to provide) an estimate of the length of a codeword that may be generated by the encoder for a subsequence given by the model.

Given two competing models at time instance i, if the first model provides fewer bits than the second model, the weight assigned to the first model (using equation 9) is at position x _i - ₁ will be greater than the weight assigned to the second model for the sequence up to the symbol of . After all (ie, when ^{encoding of sequence x n} is done using mixed probabilities), the winning model (ie, the model with higher weight) is the model that produces fewer bits, which is the result of the desired compression.

[00126] The weight w _i,1 can be approximated (in equation (9)) using a power of 2 and computed efficiently accordingly.

이다. 이는 1+r+r²+…에 의해 주어진 기하급수로서 인식되고, 여기서, 공비

이다. 따라서, 가중치 w_i,1은 방정식 (10)을 사용하여 근사화될 수 있다.[00127] The weight w _i,1 can be further simplified. The right-hand side of equation (9) is of the form 1/(1-r), where

am. This is 1+r+r ² +… Recognized as an exponential given by , where,

am. Thus, the weight w _i,1 can be approximated using equation (10).

[00128] Thus, w _i,1 * p ₁ (x _i | ^{x i-1} ) in equation (8) can be rewritten as in equation (11).

은 p₁(x_i│x^i-1)이 고정-소수점 표현을 갖는 경우들에서 시프트들을 사용함으로써 효율적으로 컴퓨팅될 수 있다. 또한, p₁(x_i │ x^i-1)이 고정-소수점 표현을 갖는 경우, 방정식 (11)의 무한 합은 유한 수의 항들의 합으로 절단될 수 있다. 예를 들어, p₁(x_i│x^i-1)이 8-비트 표현을 갖는 경우, 합은 처음 8개의 항들만을 유지하도록 절단될 수 있으며,

인 경우(즉, 이들이 적어도 하나의 비트만큼 상이한 경우), 임의의 j ≥ 8에 대해,

이기 때문에,

이 된다.

인 경우(즉, 이들이 하나 초과의 비트만큼 상이한 경우), 임의의 j ≥ j^*(j^* < 8)에 대해,

이다. 그에 따라, 처음 j^*개의 항들만이 w_i,l(xⁱ│x^i-1)을 컴퓨팅할 필요가 있다.[00129] In equation (11),

can be computed efficiently by using shifts in cases where p ₁ (x _i | ^{x i-1 ) has a fixed-point representation.} Also, if p ₁ (x _i │ x ^i-1 ) has a fixed-point representation, the infinite sum of equation (11) can be truncated to the sum of a finite number of terms. For example, if p ₁ (x _i | ^{x i-1} ) has an 8-bit representation, the sum can be truncated to keep only the first 8 terms,

(i.e. if they differ by at least one bit), for any j ≥ 8,

because it is,

becomes this

(i.e., if they differ by more than one bit), then for any j ≥ j ^* (j ^* < 8),

am. Accordingly, only the first j ^* terms need to compute _{w i,l} (x ⁱ | ^{x i-1 ).}

[00130] The weight w _i,2 may be computed using equation (12).

[00131] The quantity w _i,2 * p ₂ (x ⁱ |x ^i-1 ) in equation (8) can be computed using equation (13).

[00132] As in equation (11), when p ₂ (x _i |x ^i-1 ) has a fixed-point representation, by truncating the infinite sum to a finite sum, the right side of equation (13) can be simplified have.

As described above, mixing of the joint probabilities of models may use a simple uniform mixing, since it may not be known a priori as to which model provides better compression. A uniform mix of joint probabilities uses conditional probabilities and results in the selection of a winning model (ie, a model with a higher weight).

9 is a flow diagram of a process 900 for encoding a sequence of symbols, according to an implementation of the present disclosure. Process 900 may receive a sequence of symbols of size n. The sequence may be denoted by ^{x n .} Receiving may mean generating, determining, or receiving in any manner. In an example, the sequence of symbols may represent a quantized transform coefficient as received at the entropy encoding stage 408 from the quantization stage 406 of FIG. 4 . In an example, the sequence of symbols may be a token, such as the token described with respect to FIG. 7 . In an example, the sequence of symbols may be a binarized value, such as the binarized value described with respect to FIG. 8 . The sequence of symbols may be any sequence of symbols encoded based on a probabilistic model.

Process 900 may be implemented in an encoder, such as encoder 400 of FIG. 4 . Process 900 may be implemented as a software program that may be executed by computing devices, such as, for example, transmitting station 102 . A software program may include machine-readable instructions, which may be stored in a memory, such as memory 204 or secondary storage 214 , and executed by a processor, such as CPU 202 . may cause the computing device to perform process 900 . In at least some implementations, process 900 may be performed in whole or in part by entropy encoding stage 408 of encoder 400 of FIG. 4 .

The process 900 uses at least two probabilistic models to encode ^{the sequence x n of symbols.} Process 900 may use any number of probabilistic models. However, for simplicity, only two models (ie, the first model and the second model) are used to illustrate the process 900 . Process 900 encodes each of the symbols of the sequence of symbols by mixing the probabilities of the first model and the second model.

At 902 , process 900 sets counter i to zero, first subsequence length (ie, first length l ₁ ) to zero, and second subsequence length (ie, second length l ₂ ) is initialized to 0. A counter i is used for each symbol of the ^{sequence x n .} The first length l ₁ and the second length l ₂ are as described above. That is, the first length l ₁ and the second length l ₂ may correspond to lengths of codewords generated by the arithmetic coding engines using the first model and the second model, respectively.

At 904 , the process 900 determines the conditional probabilities p ₁ (x _i | ^{x i-1} ) and p ₂ (x _i | ^{x i-1} ) as described above. The conditional probability p ₁ (x _i | ^{x i-1} ) is the symbol at position i of the sequence of symbols given the probability of the ^{subsequence x i-1} (ie _{the subsequence up to and including symbol x i ).} is the conditional probability of The same is true for _{p 2} (x _i | ^{x i-1 ).}

을 컴퓨팅한다. 프로세스(900)는 위의 방정식 (4)에 설명된 혼합 확률을 결정할 수 있다. 프로세스(900)는 방정식들 8, 11 및 13을 사용하여 혼합 확률을 컴퓨팅할 수 있다. 908에서, 프로세스(900)는 컴퓨팅된 혼합 조건부 확률을 사용하여 심벌 x_i를 인코딩한다.[00139] At 906, the process 900 determines the mixing probability for _{symbol x i}

to compute Process 900 may determine the mixing probability described in equation (4) above. Process 900 may compute the mixing probability using equations 8, 11 and 13. At 908 , process 900 encodes _{the symbol x i} using the computed mixed conditional probability.

At 910 , the process 900 updates _{the first length l 1} and the second length l _{2 .} As described above, virtual arithmetic encoders may be used at 910 . The first length l ₁ is updated to include the additional codeword length (ie bits) added to the virtual codeword added by the first model when encoding the symbol x _{i .} The second length l ₂ is updated to include the additional codeword length (ie, bits) added to the virtual codeword added by the second model when encoding the symbol x _{i .} Process 900 computes, respectively, l ₁ = l ₁ -log(p ₁ (x _i |x ^i-1 )) and l ₂ = l ₂ -log(p ₂ (x _i |x ^i-1 )) to update the first length l ₁ and the second length l _{2 .} In an implementation, the values -log(p ₁ (x _i |x ^i-1 )) and -log(p ₂ (x _i |x ^i-1 )) may be computed and/or approximated by using a lookup table. The probability ^{_{p 1 (x i │x i-}} 1) and ^{_{p 2 (x i | x i}} -1) will note that the probability between 0 and 1. If p ₁ (x _i |x ^i-1 ) and p ₂ (x _i ^{|x i-1} ) are each expressed and/or approximated using an 8-bit integer (eg, they represent fixed-point representations ), -log(p ₁ (x _i |x ^i-1 )) and -log(p ₂ (x _i |x ^i-1 )) both yield a lookup table that takes 8-bit integers as inputs. can be estimated using , where each input corresponds to a probability value. In general, the size of the look-up table is ^{_{p 1 (x i │x i-}} 1) and ^{_{p 2 (x i | x i}} -1) depends on the width of the fixed-point representation. That is, the larger the width, the higher the accuracy when estimating _{-log(p 1} (x _i |x ^i-1 )) and -log(p ₂ (x _i |x ^{i-1 )).}

At 912 , counter i is incremented such that the _{next symbol x i +1 is processed.} At 914, if all symbols have been processed (ie, i = n + 1), the process ends. Otherwise, the process returns to 904 to process the next symbol.

10 is a flow diagram of a process 1000 for decoding a sequence of symbols, according to an implementation of the present disclosure. Process 1000 may be implemented in a decoder, such as decoder 500 . Process 1000 may be implemented by a receiving station. Process 900 may be implemented, for example, as a software program that may be executed by computing devices. A software program may include machine-readable instructions, which may be stored in a memory, such as memory 204 or secondary storage 214 , and executed by a processor, such as CPU 202 . may cause the computing device to perform process 900 . Process 900 may be implemented using specialized hardware or firmware. Some computing devices may have multiple memories, multiple processors, or both. The steps or operations of process 1000 may be distributed using different processors, memories, or both. Use of the terms "processor" or "memory" in the singular refers to a plurality of processors or a plurality of computing devices that may be used in performing some or all of the recited steps, as well as one processor or computing devices having one memory. devices having memories.

)을 사용하여 인코딩된 비트스트림으로부터 심벌 x_i를 디코딩한다. The process 1000 may be used to decode a sequence of symbols from an encoded bitstream. For example, process 1000 may receive an encoded bitstream, such as compressed bitstream 420 of FIG. 5 . Process 1000 may include steps similar to steps 902-906 and 910-914 as process 900 . Descriptions of similar steps are omitted. Instead of step 908 , process 1000 includes step 1002 . At step 1002, process 1000 computes the mixed conditional probability (i.e.,

) to decode the _{symbol x i} from the encoded bitstream.

In some implementations of processes 900 or 1000 , step 906 is performed every k>1 steps to further reduce (eg, reduce) computational complexity or improve throughput. can be performed. Throughput can be measured as the number of symbols processed (coded or decoded) in one clock cycle. For example, if k = 2, step 906 may be performed only when i is odd or even, but not both. In another implementation of processes 900 or 1000, step 906 may be performed on a predefined subset of all possible indices of i.

). [00145] The foregoing has described the use of uniform weights of models. However, implementations according to the present disclosure may use non-uniform prior weights. In non-uniform weights using M models, _{at least some of the weights w k} may be set to values not equal to 1/M (i.e.,

).

)를 가정하면, 가중치들 w_i,k는 공식 (14)를 사용하여 근사화될 수 있다.[00146] For simplicity, the foregoing (eg, processes 900 and 1000 ) describes the use of two models: a first model and a second model. However, implementations according to the present disclosure may be extended to any number of models. For example, for the number of models M ≥ 2, and for uniform weighting factors w _k (i.e.,

), the weights w _i,k can be approximated using formula (14).

[00147] In Equation 14, l _k (x ^i-1 ) denotes the codeword length in bits resulting from using the model k(1 ≤ k ≤ M) to encode the ^{subsequence x i-1 .} indicates.

[00148] A binary tree may be used to compute (ie, determine, generate, etc.) conditional probabilities when more than two models are mixed. That is, the factors w _i,k p _k (x _i |x ^i-1 ) of equation (8) can be recursively computed using the process described above. Computing recursively means combining the probabilities of two models at a time to produce intermediate conditional probabilities. The intermediate conditional probabilities are then combined two at a time. If the number of models M is a power of two (ie, M = 2 ^m ), then the factors w _i , kp _k (x _i |x ^i-1 ) of equation (8) are as described with respect to FIG. 11 . It can be computed recursively by applying the processes described above on the whole binary tree.

11 is a diagram of an example of a binary tree 1100 of conditional probabilities, according to an implementation of the present disclosure. In the binary tree 1100, eight models are mixed. The probabilities of the eight models are p_1 to p_8. All of the respective two probabilities are mixed first. For example, probabilities 1102 and 1104 are mixed as described above to produce intermediate conditional probability 1106, which intermediate conditional probability 1106 is then combined with intermediate conditional probability 1108 to form an intermediate conditional probability 1106. Probability 1110 is generated, and so on until the final conditional probability 1112 is computed. The final conditional probability 1112 may be used for encoding and/or decoding. For example, the final conditional probability 1112 may be used at 908 of process 900 and/or 1002 of process 1000 .

The process described with respect to FIG. 11 may be used, for example, in situations where some models are known to be more useful than others. Uniform weights may be undesirable if some models are known to be more useful than others. To assign more weights to one model, the model can be replicated in the tree.

Referring to FIG. 11 as an example, it is known that models p_1 to p_6 and p_8 may be distinct, and p_6 is more useful than other models. Since p_6 is more useful, p_6 can be duplicated in the tree: p_7 is a duplicate of p_6. Thus, a model with probability p_6 is assigned a double weight in the mix for entropy encoding.

인 것으로 가정한다. 본 개시내용에 따른 구현들은, 모델 세트를 4개의 모델들의 세트로 확장할 수 있으며, 여기서, 제1 모델은 모델 A에 대응하고, 나머지 3개의 모델들은 모델 B에 대응하며, 4개의 모델들에 대한 이전 가중치는

이다.[00152] As another example, for example, there are two models, model A and model B, and the previous weights for the two models are

is assumed to be Implementations according to the present disclosure may extend a model set to a set of four models, where the first model corresponds to model A, the remaining three models correspond to model B, and the four models correspond to The previous weight for

am.

[00153] In the foregoing, fixed sources are described. A fixed source means that the mixture for _{symbol x i} determines _{w i,k} using all the histories of ^{subsequence x i-1 .} Thus, the statistics do not vary across the source of the coding process. However, in cases where the sources may be non-fixed, implementations according to the present disclosure may use a sliding window to adapt to local statistics for better compression performance. The sliding window is a length L of bits indicating the number of previous bits (ie the probabilities of the number of previous bits) to be used in the mixing process. That is, the sliding window represents how much back into the sequence to recall: only the symbols inside the sliding window are used to estimate the weighting factors. More specifically, only the probabilities of these symbols inside the sliding window are used to estimate the weighting factors.

를 사용하는 대신에,

가 사용되며, 여기서 길이 L ≥ 1은 슬라이딩 윈도우의 길이이고, 여기서, x_i-L … x_i-1은 비트 i-L에서 시작하여 비트 i-l에서 끝나는 서브시퀀스이다. 길이 L이 알려진 경우, 본 개시내용에 따른 프로세스는 2개의 모델들에 대해 다음의 단계들을 수행할 수 있다.[00154] Thus, to code _{x i}

Instead of using

is used, where the length L ≥ 1 is the length of the sliding window, where x _iL ... x _i-1 is a subsequence starting at bit iL and ending at bit il. When the length L is known, the process according to the present disclosure may perform the following steps for the two models.

[00155] In step 1, i = 1, l ₁ = 0, l ₂ = 0 is initialized. Step 1 may be as described with respect to 902 of FIG. 9 . In step 1, the process also _{initializes l 1,-L} = 0 and l _2,-L = 0.

및

를 컴퓨팅한다.[00156] In step 2, the process is performed according to the first model and the second model

and

to compute

을 컴퓨팅한다.[00157] In step 3, the process calculates the mixing probability according to equations (15) and (16)

to compute

를 사용하여 x_i를 (인코더에 의해 구현될 때) 인코딩 또는 (디코더에 의해 구현될 때) 디코딩한다.[00158] In step 4, the process

is used to encode (when implemented by an encoder) or decode (when implemented by a decoder) _{x i .}

로 업데이트하고, l₂를

로 업데이트한다. 프로세스가 윈도우 외부에서 인코딩/디코딩하고 있다면(즉, i > L), 프로세스는

및

를 업데이트한다.[00159] In step 5, the process takes l ₁

update to , and change l ₂ to

update to If the process is encoding/decoding outside the window (i.e. i > L), the process

and

update

[00160] In step 6, i is incremented by one (ie, i = i+1).

[00161] In step 7, the process ^{repeats steps 2-6 until all bits of the sequence x n} have been processed (ie, i = n+1).

이고,

이다. 따라서,

는 x_1-L…x_i-1을 코딩하기 위해 제1 모델을 사용하여 생성된 코드워드 길이로서 간주될 수 있고,

은 x_1-L…x_i-1을 코딩하기 위해 제2 모델을 사용하여 생성된 코드워드 길이로서 간주될 수 있다.[00162] In the sliding window described above,

ego,

am. thus,

is x _1-L … can be considered as the codeword length generated using the first model to code x _{i-1 ,}

Silver x _1-L … It can be considered as the codeword length generated using the second model to code x _{i-1 .}

12 is a flow diagram of a process 1200 for entropy coding a sequence of symbols, according to an implementation of the present disclosure. The sequence may be as described above for ^{sequences x n .} Process 1200 may be implemented by an encoder or decoder. When implemented by an encoder, "coding" means encoding into an encoded bitstream, such as compressed bitstream 420 of FIG. When implemented by a decoder, “coding” means decoding from an encoded bitstream, such as compressed bitstream 420 of FIG. 5 .

When encoded by an encoder, process 1200 may receive a sequence of symbols from a quantization step, such as quantization stage 406 of FIG. 4 . In another example, process 1200 may receive a value to be encoded (eg, a quantized transform coefficient) and generate a sequence of symbols from the received value.

At 1202 , the process 1200 selects models to be blended. The models may include a first model and a second model. As used herein, “selection” means identifying, organizing, determining, specifying, or otherwise selecting in any way whatsoever.

[00166] At least for a symbol (eg, x _i ), at a position (eg, i) of the symbols, the process 1200 includes using the first model and the second model to determine a mixing probability Steps including 1204-1208 are performed. Steps 1204 - 1208 may be performed for all symbols of the sequence of symbols.

At 1204 , the process 1200 determines, using the first model, a first conditional probability for encoding the symbol. The first conditional probability is the conditional probability of a symbol given a subsequence of the sequence. In an example, a subsequence of a sequence may mean ^{a subsequence x i-1 .} In another example where a sliding window is used, the subsequence of the sequence consists of a predetermined number of symbols of the sequence prior to the position. The predetermined number of symbols may be as described for the sliding window length L. Thus, the subsequence of the sequence is subsequence x _iL ... x _i-1 . At 1206 , the process 1200 determines, using the second model, a second conditional probability for encoding the symbol. The second conditional probability is the conditional probability of the symbol given the subsequence as described with respect to 1204 .

At 1208 , the process 1200 determines a mixing probability for encoding the symbol using the first conditional probability and the second conditional probability. The mixing probability may be as described for 906 in FIG. 9 . The first conditional probability and the second conditional probability may be combined using a linear combination using the first weight and the second weight. In an implementation, at least the first weight may be determined (ie, approximated) using virtual arithmetic coding to determine a length for encoding a subsequence of the sequence up to symbols. The first weight may be determined using the length. In an example, determining a weight (eg, a first weight and/or a second weight) includes determining a rate resulting from encoding a subsequence of the sequence up to symbols, and using the determined rate to determine the first weight may include determining In an example, the rate may be determined using a rate estimator. In an example, the rate estimator may be a virtual arithmetic encoder. In an example, determining the rate may include looking up a table (eg, a lookup table) with the inputs as probability values.

At 1210 , process 1200 codes the symbol using mixing probabilities, for example, as described with respect to 908 (when implemented by an encoder) and 1002 (when implemented by a decoder). .

In an implementation of process 1200 , the model may include a third model and a fourth model, wherein determining the mixing probability using the first model and the second model comprises: the first model and the second model mixing to produce a first intermediate conditional probability, mixing the third model and the fourth model to produce a second intermediate conditional probability, and mixing the first intermediate conditional probability and the second intermediate conditional probability, generating a conditional probability to be used to encode In an implementation, the first model and the fourth model are the same model.

[00171] A technique known as context-tree weighting (CTW) is a lossless data compression algorithm that uses blending. Length for coding the n binary sequence x ⁿ of, CTW is 2 ^K of a probability function of p _i (x ⁿ⁾ linear mixed as a probability function p (x ⁿ⁾ the estimated and each is finite memory a binary tree sources thereof are assumed and have the same weighting factor. In contrast, implementations according to the present disclosure may work with any models. Also, the per-symbol weighting factor operation described herein can use length functions to approximate the probabilities of the subsequence, which is much simplified compared to existing solutions of maintaining and computing joint probabilities.

[00172] As mentioned above, a major design challenge or problem in context modeling is to strike a balance between two conflicting objectives: 1) improving compression performance by adding more contexts. and 2) reducing the overhead cost associated with contexts.

[00173] Using the coefficient token tree 700 as a non-limiting example, a mathematical analysis is now given of the effect of the number of contexts in a coding system and the relationship between the number of contexts and coding performance.

(즉, 콘텍스트 c 하에서 토큰 i가 프레임에 나타난 횟수를 콘텍스트 c가 나타난 횟수로 제산한 것)에 의해 주어질 수 있다. 확률 분포 P_c 및 Q_c는 각각, 토큰을 코딩하는데 사용되는 코딩 분포 및 실제 분포로서 지칭될 수 있다.[00174] For context c, let P _c = (P _c,0 , ..., P _c,11 ) denote the probability distribution obtained from the context, where P _c,i is i = 0, ... , represents the probability of token i for 10 (ie, tokens listed in Table 1), and P _c,11 represents the probability of EOB_TOKEN. For convenience, EOB_TOKEN is referred to as token 11. Now suppose that context c appears in the frame and is _{used n c} times. For example, a context “appears” when conditions associated with the context are met and/or is available for the frame. A context is “used” when, for example, a probability distribution associated with the context is used for coding of at least one block of a frame. Let Q _c = (q _c,0 , ..., q _c,11 ) represent the empirical (ie, observed) distribution of coefficient tokens under context c. That is, q _c,i represents the number of times token i appears in a frame under context c,

(ie, the number of times token i appeared in a frame under context c divided by the number of times context c appeared). The probability distributions P _c and Q _c may be referred to as the coding distribution and the actual distribution used to code the token, respectively.

에 의해 주어질 수 있다. 실제 분포 Q_c,

, 로그 법칙 로그(분수) = 로그(분자) - 로그(분모)를 사용하여, 달성 가능한 압축 성능이 방정식 (17)에서와 같이 감소될 수 있다.[00175] _{Given a coding distribution P c} , the compression performance achievable using arithmetic coding is

can be given by true distribution Q _c ,

, logarithm Using log(fraction) = log(numerator) - log(denominator), the achievable compression performance can be reduced as in equation (17).

은 실제 분포 Q_c의 엔트로피 H(Q_c)로서 인식될 수 있다. 방정식 (1)의 우측의 두 번째 항

은 분포들 P_c와 Q_c 사이의 동일한 알파벳(예를 들어, 계수 토큰 트리(700)의 토큰들) 상에 정의된 쿨백-라이블러(KL) 발산 또는 상대적 엔트로피로서 인식될 수 있다. KL 발산은 D(Q_c||P_c)로 표시될 수 있다. 따라서, 산술 코딩을 사용하여 달성 가능한 압축 성능은 방정식 (18)을 사용하여 다시 기재될 수 있다.[00176] The first term on the right side of equation (17)

can be recognized as the entropy H(Q _c ) of the actual distribution Q _{c .} second term from the right of equation (1)

can be recognized as a Kullback-Leibler (KL) divergence or relative entropy defined on the same alphabet (eg, tokens of coefficient token tree 700 ) between distributions P _c and Q _{c .} The KL divergence can be expressed as _{D(Q c} ||P _{c ).} Thus, the compression performance achievable using arithmetic coding can be rewritten using equation (18).

[00177] The second term (ie, D(Q _c ||P _c )), instead of using the most optimal probability distribution (ie, the actual distribution Q _c ), gives the other less optimal probability distribution (ie, the coding distribution) Shows the loss of compression performance when using _{P c ).} If there are differences between the actual probability distribution and the coding probability distribution, compression performance loss occurs. The loss increases linearly as the sequence length is encoded.

[00178] Equation (18) can be used as a basis for the design of compression algorithms. That is, the compression algorithm is analyzed using equation (18). The design of context modeling has a direct impact on compression performance. Thus, a good design of context modeling (ie, optimal selection of contexts) results in a good compression algorithm. With optimal context modeling, the first term Η(Q _c ) and the second term D(Q _c ||P _c ) are minimized.

[00179] Both terms of equation (18) (ie, n _c Η(Q _c ) and n _c D(Q _c ||P _c )) increase linearly with the number of occurrences n _{c of the context c.} It can be appreciated that in order to improve the compression performance of entropy coding, the two terms of Η(Q _c ) and D(Q _c ||P _c ) in equation (18) should be made as small as possible.

[00 180] Since the second term D (Q _c || P _c) is always non-negative value, if the actual distribution and the distribution of the equivalent coding, and only in that case (i.e., Q _c ≡ P _c), D (Q _c ||P _c ) = 0, and the first term (ie, n _c Η(Q _c )) is the absolute theoretical lower bound for any compression algorithm. As a matter of different ways, given a sequence of n _c Q _c has a probability distribution, the best possible compression is given by H n _c (Q _c), other probability distributions may not provide better compression.

[00 181] Accordingly, to achieve good compression performance, distributed coding (P _c) is preferably as close as possible to the actual distribution (Q _c). In the same context, the actual distributions are changed from one frame to another. Accordingly, the coding distribution P _c must be adapted to _{the actual distribution Q c} of a given frame to be decoded. Since the frame has not yet been decoded, the decoder does not know how to adjust the _{coding distribution P c .}

Instead, the adjusted coding distribution P _c may be signaled by the encoder. For example, the encoder may encode the _{adjusted coding distribution P c} in the frame header of the frame to be decoded. Encoding the adjusted coding distribution P _c may mean that the encoder encodes the token probabilities P _{c,i of the coding distribution P c} .

Assume that the cost in bits (or more precisely in partial bits) for encoding token probabilities P _{c,i is lowered by the bit cost ε > 0.} That is, the bit cost ε is the minimum number of bits required to encode the _{token probability P c,i .}

)이므로, 이의 자유도는 알파벳 사이즈(예를 들어, 12개의 토큰들) 마이너스 1과 동일하다. 따라서, 비트 비용 11ε/n_c에서 12(토큰들의 수에 대응함) 대신에 11이 있다.[00184] For context c, the total bit cost amortized for the frame coding the _{coding distribution P c} including the 12 tokens of Table 1 and the probabilities of EOB_TOKEN may be given by _{11ε/n c .} . The total bit cost is _{inversely proportional to n c} and increases linearly with the alphabet size (eg, number of tokens). If the coding distribution P _c is a probability distribution (i.e.,

), so its degree of freedom is equal to the alphabetic size (eg, 12 tokens) minus one. Thus, there is 11 instead of 12 (corresponding to the number of tokens) at the bit cost 11ε/n _{c .}

Let C denote the set of all contexts used for transform coefficient coding. EOB_TOKEN and A probability corresponding to each token of the coefficient token tree 700 may be encoded. Since there are 12 tokens, the total bit cost of the coding probability distributions obtained from the contexts of the set C amortized for the frame is given by equation (19).

[00186] In equation (19), |C| is the cardinality of the set C, and n is the number of tokens in the frame. Equation (19) indicates that each additional context may add a normalized cost of at least 11ε/n bits per token. The right-hand representation of equation (19) increases linearly with the number of contexts (ie, the size of set C). Thus, reducing the number of contexts (ie, smaller set C) can reduce overhead. However, there remains a case where 11 probabilities are encoded for every context, 11 corresponding to the number of tokens (12) minus 1. Using selective mixing for entropy coding, the number of probabilities to be encoded can be reduced for some contexts, as described below. For example, given a coefficient token tree 700, instead of encoding 11 probabilities, less than 11 are coded, thereby reducing overhead bits associated with coding distributions in frame headers.

As noted above, reducing the number of contexts (ie, smaller set C) may reduce overhead. However, analysis of the first term in equation (18), ie entropy Η(Q _c ), indicates that reducing the number of contexts is undesirable.

[00188] Entropy Η(Q _c ) is a concave function. This in turn, and as given by inequality (20), if we take a linear combination of the two distributions M and M', then the entropy of the linear combination of the two distributions M and M' (i.e., to the left of the inequality) is means to be greater than or equal to the linear sum of the entropies of the individual distributions (ie, to the right of the inequality). If the two distributions M and M' are different, inequality (20) becomes a strict inequality.

[00189] Given inequality (20), it can be concluded that, in order to minimize the first term in equation (18), it is desirable to increase the number of distinct distributions, which in turn leads to the number of distinct contexts. means to increase This is because by increasing the number of contexts, the left side of inequality (20) can be decomposed into the right side. Decomposition can improve overall compression performance.

[00190] In summary, in order to improve the compression performance, analysis of the second terms of equations (18) and (19) leads to the conclusion that it is desirable to reduce the number of contexts; On the other hand, analysis of the first term of equation (18) and inequality (20) leads to the conclusion that it is desirable to increase the number of contexts to improve the compression performance. Using selective mixing for entropy coding, the number of contexts can be increased and the overhead associated with every additional context can be reduced or limited, as described below. For example, and referring to the coefficient token tree 700 of FIG. 7 , the addition of context does not add 11 probability values.

[00191] The following observations can be made.

1) when coding the transform coefficients, when the context c is determined, the coding distribution P _c associated with the context c is used to code the tokens for the transform coefficients,

2) the multiplication factor of 11 in equation (19) is equal to the size of the alphabet of coefficient tokens minus 1,

3) If context c is split into _{two separate contexts c 0} and c _{1 , the number of times context c 0} appears and the number of times context c ₁ appears are equal to the number of times context c appears (i.e., n _c = n _c0 + n _c1 ),

4) if context c is _{split into two separate contexts c 0} and c ₁ , the corresponding actual distributions Q _c0 and Q _c1 must be sufficiently different,

5) For a given context c, the number of times n _c,i of a token i appears in a frame under context c must be large enough to guarantee sufficient accuracy in the probability estimation for all i.

_{[00192] Given two distributions Q c0} and Q _c1 that differ only in some indices but are similar or identical in other indices, implementations of the present disclosure only for token indices where _{Q c0} and Q _{c1 are different,} Context c may be split into, for example, two contexts c ₀ and c _{1 .} In other words, each new context introduced may cost less than _{11ε/n c bits/token.} For example, if the context fits 4 tokens, the cost is 3ε/n _c .

13 is a flow diagram of a process 1300 for coding transform coefficients using an alphabet of transform coefficient tokens, according to an implementation of the present disclosure. Process 1300 codes (ie, encodes or decodes) a current transform coefficient using two or more probability distributions. Process 1300 may code a token indicating a current transform coefficient. Tokens may be determined or selected using a coefficient tree, such as coefficient token tree 700 of FIG. 7 . Thus, the alphabet contains leaf nodes (ie, tokens) of the coefficient tree.

Process 1300 may be used by or in conjunction with a process of coding coefficients of a transform block according to a scan order. Current transform coefficients may be scanned in the i position in the scanning sequence, it may be in the conversion coefficient block to the position (r _i, c _i).

The process 1300 selects a first probability distribution corresponding to a first context, selects a second probability distribution corresponding to a second context, and, for some transform coefficient tokens, the first probability distribution and the second probability distribution. By mixing the two probability distributions, a mixing probability for coding a transform coefficient token among some transform coefficient tokens may be generated.

Process 1300 may be implemented in an encoder, such as encoder 400 of FIG. 4 . Process 1300 may be implemented as a software program that may be executed by computing devices, such as, for example, transmitting station 102 . A software program may include machine-readable instructions, which may be stored in a memory, such as memory 204 or secondary storage 214 , and executed by a processor, such as CPU 202 . may cause the computing device to perform process 1300 . In at least some implementations, process 1300 may be performed in whole or in part by entropy encoding stage 408 of encoder 400 of FIG. 4 .

Process 1300 may be implemented in a decoder, such as decoder 500 of FIG. 5 . Process 1300 may be implemented as a software program that may be executed by computing devices, such as, for example, receiving station 106 . A software program may include machine-readable instructions, which may be stored in a memory, such as memory 204 or secondary storage 214 , and executed by a processor, such as CPU 202 . may cause the computing device to perform process 1300 . In at least some implementations, process 1300 may be performed in whole or in part by entropy decoding stage 502 of decoder 500 of FIG. 5 .

When process 1300 is implemented by an encoder, “coding” means encoding into an encoded bitstream, such as compressed bitstream 420 of FIG. 4 . When implemented by a decoder, “coding” means decoding from an encoded bitstream, such as compressed bitstream 420 of FIG. 5 .

At 1302 , the process 1300 selects a first probability distribution. As used in this disclosure, “selection” means obtaining, identifying, organizing, determining, specifying, or otherwise selecting in any way whatsoever.

In an example, process 1300 may first derive a first context and select a first probability distribution corresponding to the first context. For example, the context may include: transform block size, transform block shape (eg, square or rectangular), color component or planar type (ie, luminance or chrominance), scan position i of the current transform coefficient, and previously It may be derived using one or more of the coded tokens. For example, for the scan order 602 of FIG. 6 , the previously coded coefficients may be the left neighbor coefficient and the top neighbor coefficient of the current transform coefficient. Other information may be used to derive the first context.

In an example, a first probability distribution may be defined for all tokens of the alphabet. That is, the probability distribution includes a probability value for each of the tokens of the alphabet. Using the tokens of the coefficient token tree 700, it is assumed that the alphabet set E represents the alphabet of the coefficient tokens. Thus, the alphabet set E is given by E = {EOB_TOKEN, ZERO_TOKEN, ONE_TOKEN, TWO_TOKEN, THREE_TOKEN, FOUR_TOKEN, DCT_VAL_CAT1, DCT_VAL_CAT2, DCT_VAL_CAT3, DCT_VAL_CAT4, DCT_VAL_CAT4, DCT_VAL_CAT6} The first probability distribution may include a probability value for each of the tokens of the alphabet set E. In another example, the probability distribution may include probability values for some of the tokens of the alphabet. In an example, the first probability distribution may be a coding distribution as described above with respect to the _{coding distribution (P c ).}

At 1304 , the process 1300 selects a second probability distribution. In an example, process 1300 may derive a second context and select a second probability distribution corresponding to the second context.

[00203] A second probability distribution may be defined for the partitioning of tokens. Using the tokens of the coefficient token tree 700 of FIG. 7 as an illustrative example, the partition may correspond to a non-obvious partition of the alphabet set E. For example, the non-self-name partitioning F _E may be F _E = {{EOB_TOKEN}, {ZERO_TOKEN}, {ONE_TOKEN, TWO_TOKEN, THREE_TOKEN, FOUR_TOKEN, DCT_VAL_CAT1, DCT_VAL_CAT2, DCT_VAL_CAT3, DCT_VAL_CAT2, DCT_VAL_CAT3, DCT_VAL_CAT3, DCT_VAL_CAT4}. That is, the non-self-name partition F _E partitions the alphabet set E into three non-overlapping subsets: {EOB_TOKEN}, {ZERO_TOKEN}, and a set containing all other tokens. Accordingly, the second probability distribution includes probability values for the elements of the partition.

In the example of the non-obvious partition F _E , the second probability distribution may include three probability values. Since the non-obvious partition F _E contains only 3 elements, the second context adds an overhead of 2ε/n bits/token, which is a new context that determines the probability distribution for the alphabet E (i.e., the second This is significantly less than the overhead of about 11ε/n bits/token added by a context equal to 1 context).

[00205] When the second context targets a subset of tokens of the alphabet E, the amount of overhead associated with the added second context is limited. The added second context incurs much less overhead than the added first context.

In an example, the second context may be a context targeting tokens of alphabet set E that are used more frequently than other nodes. Targeting more frequently used tokens can improve the coding (eg, compression) performance of these tokens. For example, and referring back to the coefficient token tree 700 of FIG. 7 , among the inner nodes (eg, nodes AK ), when a root node 701 and a node 703 code transform coefficients These are the most frequently used nodes. When traversing the tree to encode transform coefficients, the lower the inner node in the tree is, the less frequently the node is traversed. That is, the lower the node is in the tree, the fewer times the inner node is used to code the transform coefficients. Thus, adding contexts (which is desirable if there is no overhead as described above) may be limited to adding contexts for the most frequently used tokens.

In an example, the second context may be an actual distribution as described with respect to the _{actual distribution (Q c ).} In the example, the probability that the token for the current coefficient (ie, the coefficient at the coefficient position (r _i , c _i ) and corresponding to the scan position i) is zero (ie, t _i = ZERO_TOKEN) is the coefficient position (r _i , c ) _{By leveraging the well-known fact that i} ) is closely correlated with the number of zeros in its immediate neighboring 2D (two-dimensional) neighborhood, a second context can be derived. In the example, the second context may be derived by using the neighboring template fixed to a position coefficient (r _i, c _i). A neighbor template may mark, contain, specify, etc., coefficient locations that make up a neighbor. The neighbor template may be formed based on the scan order.

14 is a diagram of neighbor templates 1400 and 1450 for deriving a context, in accordance with implementations of the present disclosure. The neighbor template contains locations (ie, neighbor locations) of coefficients coded before the current coefficient. Accordingly, the values for these coefficients are available for coding the current coefficient. A neighbor template may include any number of locations. Neighbor templates can have any shape. For example, the neighbor template need not be contiguous or contain contiguous locations.

[00209] Neighbor template 1400 illustrates a neighbor template that may be used with a forward scan order. The forward scan order, like the scan order 602 of FIG. 6 , is a scan order from the top left corner to the bottom right corner of the transform block. Neighbor template 1400 illustrates a neighbor template 1404 and a current coefficient 1402 that include positions of five shading coefficients denoted a-e. A neighbor template may contain more or fewer count locations. In an example, the values a-e may indicate whether the respective coefficients are zero or non-zero. Thus, the values a-e may be binary values.

[00210] Neighbor template 1450 illustrates a neighbor template that may be used with a reverse scan order. The reverse scan order is, for example, a scan order going from the right-bottom corner to the top-left corner of the transform block. Neighbor template 1450 illustrates a neighbor template 1454 and a current coefficient 1452 that include positions of nine shadow coefficients denoted a-i. However, as indicated above, the neighbor template may contain more or fewer coefficient positions.

In an example, the second context may be derived based on a number of zero coefficients in the neighbor template. For example, and using the neighbor template 1400 , the context from the set of context values {0, 1, 2, 3} based on the formula (a + b + c + d + e + 1) >> 1 A value may be selected, where each of the values ae is a value of 0 or 1 and ">> 1" is a bit-shift of the sum (a + b + c + d + e + 1) by one bit . In an example, a value of 0 may indicate that the coefficient at that location is a zero coefficient, and a value of 1 may indicate that the coefficient is non-zero. For example, if all of the neighboring template coefficients are zero, the numbered context may be selected; If exactly one or exactly two of the neighboring template coefficients are non-zero, the context numbered 1 is selected, and so on. Other values and semantics are possible.

Referring back to FIG. 13 , in response to determining that the second probability distribution includes a probability for the transform coefficient token, at 1306 , the process 1300 proceeds to 1308 . In an implementation, the process 1300 can include the process 1300 proceeding to 1312 if the second probability distribution does not include a probability for the transform coefficient token.

In an example, the second probability distribution includes a probability for the transform coefficient token when the transform coefficient token is included in a singleton element of the partition. For example, it is determined that the non-obvious partition F _E described above includes the probability for EOB_TOKEN, because EOB_TOKEN is included in the singleton element {EOB_TOKEN} of the _{non-obvious partition F E .} For the above, a singleton element is a subset of the alphabet set E containing only one element. Thus, the second probability distribution is not determined to include, for example, the probability for FOUR_TOKEN, since FOUR_TOKEN is not included in the singleton element of the _{non-obvious partition F E .}

As indicated above, a first context may be used to obtain a first probability distribution, which may be a probability distribution for alphabet set E, and a second context may be used to obtain a second probability defined for a _{non-obvious partition F E .} It can be used to obtain a distribution. Referring to coefficient token tree 700 , in an example, a first context may be used to determine a binary probability distribution for coding (ie, encoding or decoding) binary decisions at all internal nodes, and a second context may only be It can be used to determine binary distributions at two inner nodes: the root node 701 and its right child node (ie node 703 ).

At 1308 , the process 1300 mixes the first probability distribution and the second probability distribution to generate a mixed probability. At 1310 , process 1330 entropy codes the transform coefficient token using the mixing probability.

[00216] Given a non-obvious partition F _E , by mixing a distribution obtained from a first context (ie, a first probability distribution) and a distribution obtained from a second context (ie, a second probability distribution), two Coding distributions for the inner nodes (ie, root node 701 and node 703 ) may be obtained. Thus, the probability distribution for coding the token need not be chosen a priori; Rather, as described above, mixing may result in the best combination.

[00217] Mixing may be as described above with respect to FIGS. 9-12. In an example, process 1300 determines, using a first probability distribution, a first conditional probability for decoding a transform coefficient token, and using a second probability distribution, a second conditional probability for decoding a transform coefficient token. The mixing probability may be generated by determining the probability and using the first conditional probability and the second conditional probability to determine the mixing probability.

As an example, using a token tree such as coefficient token tree 700 of FIG. 7 , the first conditional probability distribution may be a conditional probability distribution at an inner node. The conditional probability distribution at the inner node is the probability of selecting a child node (i.e., the left child or the right child) of the inner node given a first context determined from the coded history (i.e., previously coded coefficients) and side information. is the distribution Examples of side information include a plane type (eg, luminance, chrominance, etc.), a transform size (ie, transform block size), and a transform type (eg, DCT, ADST, etc.). Other ancillary information may be available. The second conditional probability distribution is a conditional probability distribution at the same inner node given a second context determined from the coded history and side information. The first context and the second context may be derived using different information and different side information in the coded history.

[00219] Using the non-obvious partition F _E as an example, the first conditional probability distribution may be a conditional probability distribution for the non-obvious partition F _E given a first context determined from the coded history and side information; The second conditional probability distribution may be a conditional probability distribution for _{F E} given a second context determined from the coded history and other or the same side information.

에 의해 주어질 수 있다. F_E가 알파벳 세트 E의 비-자명 분할이기 때문에, 확률 값들의 선택적 혼합은 알파벳 세트 E의 엘리먼트들 e에 대해 본질적으로 실행 또는 수행된다. [00 220] If the first context to determine the probability distribution P of the alphabet set of E, the probability distribution Q of the F _E is, for any of the elements e of the F _E, the probability Q (e) of the element e is an element Sum of probabilities of all tokens in e (e being a set of tokens):

can be given by Since F _E is a non-obvious partition of alphabet set E, selective mixing of probability values is essentially performed or performed for elements e of alphabet set E.

At 1312 , under the condition that the second probability distribution does not include a probability for the transform coefficient token, the process 1300 uses the first probability distribution to entropy code the current transform coefficient token. That is, for the remaining internal nodes (ie, nodes not included in the singleton of partition E), coding distributions may be obtained from the first context. That is, the first probability distribution may be used to entropy code the remaining coefficients.

In summary, selective mixing of a first probability distribution and a second probability distribution may be used for a subset of tokens used to code the transform coefficients. In an example, the tokens correspond to internal nodes of the coefficient token tree. For example, selective mixing can only be used for internal nodes that are used more frequently (ie, nodes that are frequently-used) than other internal nodes (ie, nodes that are not frequently-used). In an example, more frequently used internal nodes may be given as a list of tokens corresponding to these internal nodes. In another example, the more frequently used internal nodes may be singletons _{of the non-obvious partition F E .} If mixing is not used for the inner node, the first probability distribution may be used as the coding distribution. Thus, mixing is selectively applied to some nodes: the first and second distributions are mixed for some internal nodes (eg, frequently-used nodes), and the first distribution is applied to other internal nodes ( For example, it is used to code infrequently-used nodes).

In the example above, the alphabet set E has been partitioned into a _{non-obvious partition F E .} Accordingly, tokens of alphabet set E are considered unrelated and distinct. That is, although the tokens of the coefficient token tree 700 are used to illustrate the process 1300 , the split treats the tokens as unrelated and distinct tokens. That is, partition E does not leverage the tree structure and can be used with any alphabet set.

In another example, if available, the tree structure of tokens may be used to select a second probability distribution. A tree structure (such as coefficient token tree 700 ) may relate one token to another token by its hierarchy. Accordingly, the second probability distribution may be a probability distribution defined in some internal nodes of the coefficient token tree.

For example, more frequently used internal nodes may be nodes closer to the root node than other internal nodes. For example, in the coefficient token tree 700, the node marked C is closer to the root node 701 than the node marked K, which means that a traversal from the root node is more likely to arrive at the node marked K than it is to the node marked K. This is because fewer hops are needed to reach the node.

In an example, selective mixing may be used for internal nodes that are within (or less than) a predetermined number of hops from the root node. For example, if the predetermined number of hops is two, selective mixing may be used for internal nodes denoted A (ie, root node 701 ), node 703 , and node denoted C. Accordingly, whether an internal node is "frequently used" may be determined based on the proximity of the internal node to the root node. The internal node corresponding to the token is “used” when decisions related to the token are also coded, eg, in the process of coding another token.

[00227] The probability of coding the token of some internal nodes (ie, the sequence x ⁿ generated by traversing the tree) may be determined as described with respect to FIG. 9 by mixing the first probability distribution and the second probability distribution. That is, for inner nodes having both distributions from the first probability distribution and the second probability distribution, a mixed probability may be obtained for entropy coding the current coefficient. For all other inner nodes, the first probability distribution is used to entropy code the current coefficient.

If k is the number of internal nodes affected by the second context, the second context adds approximately kε/n bits/token, while the first context is for tokens of the coefficient token tree 700 Add 11ε/n bits/token.

By using selective mixing, the set C of available contexts in the coding system can be divided into _{a first set C 0} and a second set C _{1 .} Using the alphabet E of coefficient tokens as an example, the first set c ₀ can be derived from context information affecting the overall distribution for the alphabet E, and the contexts in the set C ₁ are only part of the overall distribution for the alphabet E It can be derived from contextual information that affects it. Different contexts in set C ₁ may target different partitions of the alphabet E. If a coefficient tree is available, _{different contexts in set C 1} may target different internal nodes of the tree. For example, _{some contexts in set C 1} may target the root node in the coefficient token tree. For example, _{some contexts in set C 1} may target an internal node that splits ZERO_TOKEN from other tokens. For example, _{some contexts in set C 1} may target an internal node that splits ONE_TOKEN from other tokens. Thus, instead of maintaining hundreds or thousands of contexts for all tokens of the alphabet in a coding system, a smaller subset may be maintained for all tokens, with another set of contexts being important, critical, or more frequent. It is possible to target tokens that can be considered to be widely used.

Aspects of encoding and decoding described above illustrate some examples of encoding and decoding techniques. However, it will be understood that encoding and decoding as used in the claims may mean compression, decompression, transformation, or any other processing or alteration of data.

[0231] The word "example" or "implementation" is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as an "example" or "implementation" will not necessarily be construed as preferred or advantageous over other aspects or designs. Rather, use of the word "example" or "implementation" is intended to present concepts in a concrete manner. As used herein, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless otherwise specified by context or clearly indicated from the context, the statement "X includes A or B" is intended to mean any of its natural inclusive permutations. That is, if X contains A; X comprises B; or X includes both A and B, then "X includes A or B" is satisfied under any of the preceding instances. Moreover, "a" or "a", as used in this application and the appended claims, should generally be construed to mean "one or more," unless otherwise specified or clearly indicated by context to indicate that the singular form is indicated. . Moreover, the terms “implementation” or “an implementation” throughout are not intended to mean the same embodiment or implementation unless so described.

[0232] Algorithms, methods, instructions, etc. stored thereon and/or executed by the transmitting station 102 and/or the receiving station 106 (and the encoder 400 and decoder 500) ) may be implemented in hardware, software, or any combination thereof. Hardware may include, for example, computers, intellectual property (IP) cores, application-specific integrated circuits (ASICs), programmable logic arrays, optical processors, programmable logic controllers, microcode, microcontrollers, servers. , microprocessors, digital signal processors, or any other suitable circuitry. In the claims, the term "processor" should be understood to include any of the foregoing hardware, alone or in combination. The terms "signal" and "data" are used interchangeably. Also, portions of the transmitting station 102 and the receiving station 106 are not necessarily implemented in the same manner.

Further, in an aspect, for example, the transmitting station 102 or the receiving station 106 is a computer program that, when executed, performs any of the individual methods, algorithms, and/or instructions described herein. It can be implemented using a general-purpose computer or general-purpose processor having In addition, or alternatively, a special purpose computer/processor may be utilized, which may include, for example, other hardware for performing any of the methods, algorithms, or instructions described herein.

[0234] The transmitting station 102 and the receiving station 106 may be implemented, for example, on computers of a videoconferencing system. Alternatively, the transmitting station 102 may be implemented on a server, and the receiving station 106 may be implemented on a device separate from the server, such as a handheld communication device. In this case, the transmitting station 102 may use the encoder 400 to encode the content into an encoded video signal and transmit the encoded video signal to the communication device. The communication device, in turn, may then decode the encoded video signal using the decoder 500 . Alternatively, the communication device may decode content stored locally on the communication device, such as content not transmitted by the transmitting station 102 . Other transmitting station 102 and receiving station 106 implementation schemes are available. For example, the receiving station 106 may be a general stationary personal computer rather than a portable communication device, and/or the device including the encoder 400 may also include a decoder 500 .

[0235] Further, all or some implementations of the present disclosure may take the form of a computer program product, eg, accessible from a tangible computer-usable or computer-readable medium. A computer-usable or computer-readable medium may be, for example, any device capable of tangibly containing, storing, communicating, or transmitting a program for use by or in connection with any processor. The medium may be, for example, an electronic, magnetic, optical, electromagnetic or semiconductor device. Other suitable media are also available.

[0236] The above-described embodiments, implementations, and aspects have been described to enable an easy understanding of the disclosure and not to limit the disclosure. To the contrary, this disclosure is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims, which scope is to be accorded the broadest interpretation permitted under law to include all such modifications and equivalent arrangements.

Claims (21)

An apparatus for decoding transform coefficients using an alphabet of transform coefficient tokens, comprising:
each token represents a respective transform coefficient value and the alphabet forms a set of tokens,
The device comprises a processor;
The processor is:
to entropy decode a transform coefficient token, select a first probability distribution corresponding to a first context, wherein the first probability distribution is defined for all tokens of the alphabet;
to entropy decode the transform coefficient token, select a second probability distribution corresponding to a second context, wherein the second probability distribution is defined for a non-trivial partition of the tokens, the token the non-obvious partitioning of splits the alphabet into more than one non-overlapping subsets of the tokens; and
In response to determining that the transform coefficient token is included in a singleton element of the non-obvious partition, the singleton element being a subset that includes only one element of the non-overlapping subsets. ,
mixing the first probability distribution and the second probability distribution to produce a mixed probability, and
entropy decode the transform coefficient token from an encoded bitstream, using the mixing probability.
composed,
An apparatus for decoding transform coefficients. According to claim 1,
The processor is:
use the first probability distribution to entropy decode the transform coefficient token from the encoded bitstream under the condition that the transform coefficient token is not included in the singleton element of the non-obvious partition.
composed,
An apparatus for decoding transform coefficients. 3. The method according to claim 1 or 2,
wherein the first probability distribution is a probability distribution obtained from the first context;
An apparatus for decoding transform coefficients. 3. The method according to claim 1 or 2,
wherein the second probability distribution is the observed distribution of the tokens;
An apparatus for decoding transform coefficients. According to claim 1,
Mixing the first probability distribution and the second probability distribution to entropy decode the transform coefficient token from the encoded bitstream comprises:
determining, using the first probability distribution, a first conditional probability for decoding the transform coefficient token, wherein the first conditional probability is a conditional probability of the transform coefficient token given other transform coefficient tokens of the alphabet; ;
determining, using the second probability distribution, a second conditional probability for decoding the transform coefficient token, the second conditional probability being a singleton element of the non-obvious partition given other elements of the non-obvious partition is the conditional probability of −; and
determining a mixing probability for decoding the transform coefficient token using the first conditional probability and the second conditional probability
comprising,
An apparatus for decoding transform coefficients. 3. The method according to claim 1 or 2,
A transform coefficient corresponding to the transform coefficient token is at a location of a transform block, and
wherein the second context is determined using a number of zero coefficients in locations neighboring the location.
An apparatus for decoding transform coefficients. 7. The method of claim 6,
The locations neighboring the location are based on scan order,
An apparatus for decoding transform coefficients. 3. The method according to claim 1 or 2,
the alphabet of tokens is organized into a coefficient token tree;
the first probability distribution is defined for inner nodes of the coefficient token tree;
the second probability distribution is defined for some but not all internal nodes of the coefficient token tree;
wherein entropy decoding the transform coefficient token from the encoded bitstream comprises decoding, using the mixing probability, a first decision related to a first inner node of the coefficient token tree;
An apparatus for decoding transform coefficients. A method for coding transform coefficients using an alphabet of tokens, comprising:
each token represents a respective transform coefficient value and the alphabet forms a set of tokens,
The method is:
selecting a first probability distribution corresponding to a first context to entropy code the token of the transform coefficient, wherein the first probability distribution is defined for some tokens of the alphabet;
selecting a second probability distribution corresponding to a second context to entropy code the token, wherein the second probability distribution is defined for a non-obvious partition of the tokens, wherein the non-obvious partition of the tokens is partitioning the alphabet into more than one non-overlapping subsets of the tokens; and
in response to determining that the first probability distribution comprises a probability for the token and the second probability distribution comprises a second probability for the token;
mixing the first probability distribution and the second probability distribution to produce a mixed probability; and
coding the token using the mixing probability.
containing,
A method for coding transform coefficients. 10. The method of claim 9,
using the first probability distribution to entropy code the token under the condition that the second probability distribution does not include a probability for the token.
A method for coding transform coefficients. 11. The method of claim 9 or 10,
wherein the first probability distribution is a probability distribution obtained from the first context;
A method for coding transform coefficients. 11. The method of claim 9 or 10,
wherein the second probability distribution is the observed distribution of the tokens;
A method for coding transform coefficients. 11. The method of claim 9 or 10,
Determining that the second probability distribution includes a probability for the token comprises:
determining that the token is included in the singleton element of the non-obvious partition;
wherein the singleton element is a subset including only one element of the non-overlapping subsets;
A method for coding transform coefficients. 14. The method of claim 13,
To entropy code the token, mixing the first probability distribution and the second probability distribution comprises:
determining, using the first probability distribution, a first conditional probability for coding the token, wherein the first conditional probability is a conditional probability of the token relative to other tokens of the alphabet;
determining, using the second probability distribution, a second conditional probability for coding the token, wherein the second conditional probability is of a singleton element of the non-obvious partition relative to other elements of the non-obvious partition. conditional probability ―; and
determining a mixing probability for coding the token using the first conditional probability and the second conditional probability
comprising,
A method for coding transform coefficients. 11. The method of claim 9 or 10,
The transform coefficient is at a position, and
wherein the second context is determined using a number of zero coefficients in neighboring locations;
A method for coding transform coefficients. 16. The method of claim 15,
the neighboring locations are based on scan order,
A method for coding transform coefficients. An apparatus for decoding transform coefficients using an alphabet of tokens organized into a coefficient token tree, comprising:
including a processor;
The processor is:
select a first probability distribution corresponding to a first context, wherein the first probability distribution is defined for internal nodes of the coefficient token tree;
select a second probability distribution corresponding to a second context, wherein the second probability distribution is defined for some but not all internal nodes of the coefficient token tree; and
to decode a token by decoding a first decision related to a first inner node of the coefficient token tree, using the mixed probability.
composed,
wherein the mixing probability is generated by mixing the first probability distribution and the second probability distribution;
An apparatus for decoding transform coefficients. 18. The method of claim 17,
Decoding the token is:
decoding a second decision related to a second inner node of the coefficient token tree using the first probability distribution;
An apparatus for decoding transform coefficients. 19. The method of claim 18,
the first internal node is closer to the root node of the token tree than the second internal node;
An apparatus for decoding transform coefficients. 20. The method according to any one of claims 17 to 19,
wherein the first internal node marks an end-of-block representing the last non-zero coefficient for a given scan order;
An apparatus for decoding transform coefficients. delete

Images