Video coding using scatter-based scan tables

Scatter-based scan tables are used to encode and decode video streams. Scatter scan patterns transform coefficients between positions within a 2D array representing a block of a frame and positions within a 1D array for further encoding. By calculating a probability of whether a transform coefficient at a given position in a 2D array is non-zero, a scan order of the 2D array may be defined by a 1D array that groups the values most likely to be zero at the end of the 1D array for removal from a subsequent encoding process. This can reduce the amount of data in an encoded video stream. A decoder can use the same scatter scan pattern to rearrange a sequence of encoded transform coefficients in a 1D array into a 2D array for further decoding of an encoded block.

BACKGROUND

Digital video streams may represent video using a sequence of frames or still images. Digital video can be used for various applications including, for example, video conferencing, high definition video entertainment, video advertisements, or sharing of user-generated videos. A digital video stream can contain a large amount of data and 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.

BRIEF SUMMARY

This disclosure relates generally to encoding and decoding video data and more particularly relates to coding using scatter-based scan tables. According to one method described herein, decoding an encoded video stream includes identifying a one-dimensional (1D) transform coefficient array including a plurality of transform coefficients corresponding to a block of a frame of the encoded video stream, identifying a transform coefficient from the plurality of transform coefficients, including the transform coefficient in a two-dimensional (2D) transform coefficient array at a 2D array position based on a 1D array position of the transform coefficient in the 1D transform coefficient array and a probability associated with the 2D array position, wherein the probability is based on one or more video streams other than the encoded video stream, generating a decoded block based on the 2D transform coefficient array, and including the decoded block in a decoded video stream.

An example of an apparatus for decoding an encoded video stream described herein includes a memory and a processor. The processor is configured to execute instructions stored in the memory to identify a one-dimensional (1D) transform coefficient array including a plurality of transform coefficients corresponding to a block of a frame of the encoded video stream, identify a transform coefficient from the plurality of transform coefficients, include the transform coefficient in a two-dimensional (2D) transform coefficient array at a 2D array position based on a 1D array position of the transform coefficient in the 1D transform coefficient array and a probability associated with the 2D array position, wherein the probability is based on one or more video streams other than the encoded video stream, generate a decoded block based on the 2D transform coefficient array, and include the decoded block in a decoded video stream.

Variations in these and other aspects of the disclosure will be described in additional detail hereafter.

DETAILED DESCRIPTION

Compression schemes related to coding video streams may include breaking each image into blocks and generating an output digital video stream using one or more techniques to limit the information included in the output. A received encoded video stream can be decoded to re-create the blocks and the source images from the limited information. Encoding a video stream, or a portion thereof, such as a frame or a block, can include using transforms applied at the block level. Transforming the pixel data can permit quantization to reduce the number of states required to represent the data while avoiding some of the artifacts that can occur in the video data if quantization is applied to the pixels directly. Blocks having pixel or transform coefficient data will be referred to interchangeably as blocks or 2D arrays herein.

One example of transforming pixel data uses a transform such as a discrete cosine transform (DCT) or an asymmetric discrete sine transform (ADST) that concentrates higher values in the upper left-hand corner of the resulting 2D array. Transforming pixel data using hybrid transforms that combine asymmetric discrete sine transforms with discrete cosine transforms (ADST/DCT) or (DCT/ADST) can concentrate higher values along either the top row or left-hand column in addition to the upper left-hand corner. When quantized, the non-zero values are similarly concentrated. Zero values may also exist in the transformed block. Depending upon the size of the block, the original data and the quantizer value, the number of zero values when the transformed coefficients are quantized may include a majority of the array values. When describing transform coefficients herein, those transform coefficients may be quantized values unless otherwise stated.

One technique for compressing this data further includes selecting the 2D array of transform coefficients in a scan order or pattern. When the last non-zero coefficient is reached, the trailing zero transform coefficient values can be replaced with an end of block (EOB) token. This reduces the amount of zero values transmitted. Examples of scan patterns include a zigzag pattern and column- or row-based scan patterns described in more detail hereinafter. These scan patterns may be stored as tables for use by both an encoder and decoder indicating under what conditions a particular table is used. Such scan orders may be referred to herein as raster-based scan orders.

In contrast, the teachings herein describe the use of a scatter-based scan table that defines a scatter scan order that is not raster-based. The scatter-based scan table may be generated by calculating, for a large number of blocks from sample video streams, the probability that a given position in a block will yield a non-zero transform coefficient after the original block data is transformed and optionally quantized. The calculated probabilities are then ordered in rank order and a “scatter” scan pattern for the block is derived from the rank order of calculated probabilities. The calculated probabilities will differ based on, for example, the size of the block and the type of transforms used.

The scatter scan pattern may be used to convert a block comprising a 2D array of transform coefficients to a 1D array so that non-zero values will have a higher probability of being arranged at the beginning of the 1D array and zero values will have a higher probability of being arranged at the end of the 1D vector than if a sequential scan pattern were employed. This type of analysis and processing can be performed for each block size to be used in coding a video stream, including block of sizes 4×4, 8×8, 16×16 or 32×32 pixels, for example. The scatter scan patterns may be stored in both an encoder and a decoder to permit video streams to be encoded and subsequently decoded using the same scatter scan pattern without having to transmit the scatter scan patterns along with the encoded video stream. The scatter scan patterns may be stored in table form with index values indicating the block size and transform types associated with each pattern.

Scatter scan patterns can be distinguished from raster-based scan patterns, for example, according to the manner in which distance between adjacent transform coefficients can change between their positions in a 1D array and their positions in a 2D array. Distance can be defined as rectilinear or Manhattan distance, where distance is defined as the sum absolute differences of their Cartesian coordinates. For example, in a 2D array, pixels that are diagonally situated with respect to each other are a distance of two in rectilinear distance as measured in coordinate space. In a 1D array, the rectilinear distance is the absolute value of the difference in indices in the 1D array. Therefore, coefficients that are adjacent in a 1D array are a distance of one from each other.

In some raster-based scan patterns, for example row or column-based scan patterns, coefficients that are adjacent when arranged into the scan order with a distance of one between them most often have a distance of one between them in their positions in the original block arrangement. The exceptions are at the end a column or row. For a zig-zag scan pattern, coefficients that are adjacent when arranged into the scan order often have a distance of two between them with a distance of two between them in the original block arrangement. Alternatively, such coefficients have a distance of one in both the scan order arrangement and the original block arrangement. Scatter scan patterns, because the coefficients are based on probability instead of a set raster-based scan order based on 2D array position, can distribute coefficients such that a distance between a coefficient in a 1D array and each of its adjacent coefficient is less than two but the distance between the coefficient and each adjacent coefficient in the 2D array is at least two.

FIG. 1is a schematic of a video encoding and decoding system100in which aspects of the disclosure can be implemented. An exemplary transmitting station102can be, for example, a computer having an internal configuration of hardware including a processor such as a central processing unit (CPU)104and a memory106. CPU104is a controller for controlling the operations of transmitting station102. CPU104can be connected to the memory106by, for example, a memory bus. Memory106can be read only memory (ROM), random access memory (RAM) or any other suitable memory device. Memory106can store data and program instructions that are used by CPU104. Other suitable implementations of transmitting station102are possible. For example, the processing of transmitting station102can be distributed among multiple devices.

A network108connects transmitting station102and a receiving station110for encoding and decoding of the video stream. Specifically, the video stream can be encoded in transmitting station102and the encoded video stream can be decoded in receiving station110. Network108can be, for example, the Internet. Network108can also be a local area network (LAN), wide area network (WAN), virtual private network (VPN), a cellular telephone network or any other means of transferring the video stream from transmitting station102to, in this example, receiving station110.

Receiving station110can, in one example, be a computer having an internal configuration of hardware including a processor such as a CPU112and a memory114. CPU112is a controller for controlling the operations of receiving station110. CPU112can be connected to memory114by, for example, a memory bus. Memory114can be ROM, RAM or any other suitable memory device. Memory114can store data and program instructions that are used by CPU112. Other suitable implementations of receiving station110are possible. For example, the processing of receiving station110can be distributed among multiple devices.

A display116configured to display a video stream can be connected to receiving station110. Display116can be implemented in various ways, including by a liquid crystal display (LCD), a cathode-ray tube (CRT), or a light emitting diode display (LED), such as an OLED display. Display116is coupled to CPU112and can be configured to display a rendering118of the video stream decoded in receiving station110.

Other implementations of the encoder and decoder system100are also possible. For example, one implementation can omit network108and/or display116. In another implementation, a video stream can be encoded and then stored for transmission at a later time by receiving station110or any other device having memory. In one implementation, receiving station110receives (e.g., via network108, a computer bus, or some communication pathway) the encoded video stream and stores the video stream for later decoding. In another implementation, additional components can be added to the encoder and decoder system100. For example, a display or a video camera can be attached to transmitting station102to capture the video stream to be encoded.

FIG. 2is a diagram of an example video stream200to be encoded and decoded. Video stream200(also referred to herein as video data) includes a video sequence204. At the next level, video sequence204includes a number of adjacent frames206. While three frames are depicted in adjacent frames206, video sequence204can include any number of adjacent frames. Adjacent frames206can then be further subdivided into individual frames, e.g., a single frame208. Each frame208can capture a scene with one or more objects, such as people, background elements, graphics, text, a blank wall, or any other information.

At the next level, single frame208can be divided into a set of blocks210, which can contain data corresponding to, in some of the examples described below, a 8×8 pixel group in frame208. Block210can also be of any other suitable size such as a block of 16×8 pixels, a block of 8×8 pixels, a block of 16×16 pixels, a block of 4×4 pixels, or of any other size. Unless otherwise noted, the term ‘block’ can include a macroblock, a subblock (i.e., a subdivision of a macroblock), a segment, a slice, a residual block or any other portion of a frame. A frame, a block, a pixel, or a combination thereof can include display information, such as luminance information, chrominance information, or any other information that can be used to store, modify, communicate, or display the video stream or a portion thereof.

FIG. 3is a block diagram of an encoder300in accordance with an implementation of this disclosure. Encoder300can be implemented, as described above, in transmitting station102such as by providing a computer software program stored in memory106, for example. The computer software program can include machine instructions that, when executed by CPU104, cause transmitting station102to encode video data in the manner described inFIG. 3. Encoder300can also be implemented as specialized hardware in, for example, transmitting station102. Encoder300has the following stages to perform the various functions in a forward path (shown by the solid connection lines) to produce an encoded or a compressed video stream320using input video stream200: an intra/inter prediction stage304, a transform stage306, a quantization stage308, and an entropy encoding stage310. Encoder300may include a reconstruction path (shown by the dotted connection lines) to reconstruct a frame for encoding of future blocks. InFIG. 3, encoder300has the following stages to perform the various functions in the reconstruction path: a dequantization stage312, an inverse transform stage314, a reconstruction stage316, and a loop filtering stage318. Other structural variations of encoder300can be used to encode video stream200.

When video stream200is presented for encoding, each frame208within video stream200can be processed in units of blocks. Referring toFIG. 3, at intra/inter prediction stage304, each block can be encoded using either intra-frame prediction (also called intra prediction) or inter-frame prediction (also called inter prediction). In either case, a prediction block can be formed. The prediction block is then subtracted from the block to produce a residual block (also referred to herein as a residual).

Intra prediction and inter prediction are techniques used in image/video compression schemes. In the case of intra prediction, a prediction block can be formed from samples in the current frame that have been previously encoded and reconstructed. In the case of inter prediction, a prediction block can be formed from samples in one or more previously constructed reference frames, such as the last frame (i.e., the adjacent frame immediately before the current frame), the golden frame or a constructed or alternate frame. Various inter and intra prediction modes are available to intra/inter prediction stage304to obtain a prediction block that is most similar to the block to minimize the information to be encoded in the residual so as to later re-create the block.

Next, still referring toFIG. 3, transform stage306transforms the residual into a block of transform coefficients in, for example, the frequency domain. Examples of block-based transforms include the Karhunen-Loève Transform (KLT), the Discrete Cosine Transform (DCT), Walsh-Hadamard Transform (WHT), the Singular Value Decomposition Transform (SVD) and the Asymmetric Discrete Sine Transform (ADST). In one example, the DCT transforms the block into the frequency domain. In the case of DCT, the transform coefficient values are based on spatial frequency, with the lowest frequency (e.g., DC) coefficient at the top-left of the array and the highest frequency coefficient at the bottom-right of the array.

Quantization stage308converts the block of transform coefficients into discrete quantum values, which are referred to as quantized transform coefficients, using a quantizer value or quantization level. The quantized transform coefficients are then entropy encoded by entropy encoding stage310after they are arranged based on a scatter scan order as described herein. The entropy-encoded coefficients, together with other information used to decode the block, which can include for example the type of prediction used, motion vectors and quantization value, are then output to compressed stream320. Compressed video stream320can be formatted using various techniques, such as variable length encoding (VLC) and arithmetic coding. Compressed video stream320can also be referred to as an encoded video stream and the terms will be used interchangeably herein.

The reconstruction path inFIG. 3(shown by the dotted connection lines) can be used to provide both encoder300and a decoder400(described below) with the same reference frames to decode compressed video stream320. The reconstruction path performs functions that are similar to functions that take place during the decoding process that are discussed in more detail below, including dequantizing the quantized transform coefficients at dequantization stage312to generate dequantized transform coefficients and inverse transforming the dequantized transform coefficients at inverse transform stage314to produce a derivative residual block (i.e., derivative residual). At reconstruction stage316, the prediction block that was predicted at intra/inter prediction stage304can be added to the derivative residual to create a reconstructed block. In some implementations, loop filtering stage318can be applied to the reconstructed block to reduce distortion such as blocking artifacts.

Other variations of encoder300can be used. For example, a non-transform based encoder300can quantize one or more residual blocks directly without transform stage304. In another implementation, an encoder300can have quantization stage308and dequantization stage312combined into a single stage.

FIG. 4is a block diagram of a decoder400in accordance with implementations of this disclosure. Decoder400can be implemented, for example, in receiving station110, such as by providing a computer software program stored in memory for example. The computer software program can include machine instructions that, when executed by CPU112, cause receiving station110to decode video data in the manner described inFIG. 4. Decoder400can also be implemented as specialized hardware or firmware in, for example, transmitting station102or receiving station110.

Decoder400, similar to the reconstruction path of encoder300discussed above, includes in one example the following stages to perform various functions to produce an output video stream416from compressed video stream320: an entropy decoding stage402, a dequantization stage404, an inverse transform stage406, an intra/inter prediction stage408, a reconstruction stage410, a loop filtering stage412, and a deblocking filtering stage414. Other structural variations of decoder400can be used to decode compressed video stream320.

When compressed video stream320is presented for decoding, the data elements within compressed video stream320can be decoded by the entropy decoding stage402(using, for example, arithmetic coding) to produce a set of quantized transform coefficients. Dequantization stage404dequantizes the quantized transform coefficients and inverse transform stage406inverse transforms the dequantized transform coefficients to produce a derivative residual that can be identical to that created by reconstruction stage316in encoder300. Before applying the inverse transforms of inverse transform stage406, the coefficients are rearranged from a 1D array after entropy decoding to a 2D array using the scatter scan order as described in additional detail herein. Using header information decoded from compressed video stream320, decoder400can use intra/inter prediction stage408to create the same prediction block as was created in encoder300, e.g., at intra/inter prediction stage304. In the case of inter prediction, the reference frame from which the prediction block is generated may be transmitted in the video stream or constructed by the decoder using information contained within the video stream.

At reconstruction stage410, the prediction block can be added to the derivative residual to create a reconstructed block that can be identical to the block created by reconstruction stage316in encoder300. In some implementations, loop filtering stage412can be applied to the reconstructed block to reduce blocking artifacts. Deblocking filtering stage414can be applied to the reconstructed block to reduce blocking distortion, and the result is output as output video stream416. Output video stream416can also be referred to as a decoded video stream and the terms will be used interchangeably herein.

Other variations of decoder400can be used to decode compressed video stream320. For example, decoder400can produce output video stream416without deblocking filtering stage414.

FIG. 5is a flow diagram showing a process500for encoding a video stream in accordance with an implementation of this disclosure. Process500may also be referred to as a method of operation and can be implemented in an encoder such as encoder300(shown inFIG. 3). Process500may be implemented, for example, as a software program that can be executed by computing devices such as transmitting station102or receiving station110(shown inFIG. 1). For example, the software program can include machine-readable instructions that can be stored in a memory such as memory106or memory114, and that can be executed by a processor, such as CPU104, to cause the computing device to perform process500. Process500may also be implemented in whole or in part using specialized hardware or firmware.

For simplicity of explanation, process500is depicted and described as a series of steps. However, steps in accordance with this disclosure can occur in various orders and/or concurrently. Additionally, steps in accordance with this disclosure may occur with other steps not presented and described herein. Furthermore, not all illustrated steps may be required to implement a method in accordance with the disclosed subject matter. Some computing devices can have multiple memories, multiple processors, or both. The steps of process500can be distributed using different processors, memories, or both. Use of the terms “processor” or “memory” in the singular encompasses computing devices that have one processor or one memory as well as devices that have multiple processors or multiple memories that can each be used in the performance of some or all of the recited steps.

At step502, process500can identify a 2D array of transform coefficients including a plurality of transform coefficients corresponding to a block of a frame of the video stream to be encoded. The 2D array of transform coefficients can be formed by an encoder such as encoder300inFIG. 3. The 2D array of transform coefficients can be formed by transforming the pixels of a block of a frame using transforms as discussed in relation toFIG. 3. The 2D array of transform coefficients may be quantized transform coefficients fed into entropy encoding stage310ofFIG. 3.

At step504, a single transform coefficient is identified from the plurality of transform coefficients of the 2D array. In operation, an encoder can process each of the transform coefficients of the 2D array to form a 1D array of transform coefficients.

At step506, the transform coefficient identified at step504is included in the 1D array of transform coefficients at an array position based on the position of the transform coefficient in the 2D array and a probability associated with the array position. The probability associated with the 2D array position may be found in a scatter-based or scatter scan table as described briefly above. The scatter scan tables are described with reference toFIGS. 7A through 16.

FIGS. 7A, 7B and 7Care diagrams illustrating scan patterns for a 4×4 block700. Block700is a 4×4 block represented as a 2D array with the transform coefficient positions indicated on the array. The subscripts of the coefficients represent their positions in the array in an X-Y coordinate scheme. For example, the top-left corner block is represented by quantized transform coefficient C00. For further encoding (e.g., entropy coding) block700, the transform coefficients C00-C33are selected in a different sequential scan order. Two possible raster-based scan orders are shown inFIGS. 7B and 7C.FIG. 7Bindicates a zig-zag scan order702, andFIG. 7Cindicates a vertical scan order704. In each ofFIGS. 7B and 7C, the numbers illustrate the scan order for the given coefficient, where the value 1 indicates the first transform coefficient in each of zig-zag scan order702and vertical scan order704, the value 2 indicates the second transform coefficient in each of zig-zag scan order702and vertical scan order704, etc. Zig-zag scan order702of transform coefficients 00-15 is: C00-C01-C10-C20-C11-C02-C03-C12-C21-C30-C31-C22-C13-C23-C32-C33, for example. As mentioned briefly above, such raster-based scan orders may not result in a minimal number of transform coefficients before an EOB token may be assigned. That is, by using a raster-based scan order, one or more zero coefficients may be combined with the non-zero coefficients at the beginning of resulting sequence of transform coefficients instead of being grouped at the end of the sequence such that they made be replaced by a single EOB token. The placement of zero coefficients before the EOB token increases the number coefficients that are further encoded.

In contrast,FIGS. 8A-8Dare diagrams illustrating the use of a scatter-based scan table for a 4×4 block transformed using a first combination of transforms.FIG. 8Ashows percentages of non-zero coefficients represented by a 2D array800. The entries in array800show the probabilities (in percentages) that a transform coefficient at each position can have a non-zero value following the first combination of transforms and quantization. In this example, the first combination of transforms is a DCT/DCT combination or an ADS T/ADST combination. The probabilities are formed by processing one or more video streams, and desirably a large number of video streams, calculating transform coefficients for 4×4 blocks of frames of the one or more video streams subject to the first combination of transforms and calculating the percentage of non-zero values at each position of the resulting 4×4 blocks.

FIG. 8Bis a sequence of percentages drawn from the percentages of non-zero coefficients ofFIG. 8A. InFIG. 8B, the probabilities of 2D array800are re-ordered by decreasing order into the sequence or 1D array802so that the transform coefficients with the highest probability of being non-zero are near the beginning of 1D array802and the transform coefficients with the lowest probability of being non-zero are near the end of 1D array802. FIG.8C is a 1D array804illustrating a scatter scan order using 1D array802ofFIG. 8B. Using a 1D array of positions such as 1D array804to arrange transform coefficients from a 2D array to a 1D array can result in a 1D array where the transform coefficients near the beginning or left hand side of the 1D array have the highest probability of being non-zero and the transform coefficients near the end or right hand side of the 1D array have the lowest probability of being non-zero.

In cases where two or more positions in the 2D array such as array800have the same probability of being non-zero, a policy decision can determine which one will occur first in the 1D array such as 1D array804. One possible policy decision may be to identify the probability that would be encountered first if the 2D array were to be scanned using a zig-zag pattern, for example. Another could be to select the lower value position within the array. Any policy regarding positions having the same probability may be used as long as the mapping of the 2D array position to a 1D array position is same for both the encoder and decoder. 1D array804represents an entry in one or more scatter-based tables that may be indexed by block size and/or transform combination. In the case ofFIGS. 8A-8D, the block size is 4×4, and the transform combination is both DCT/DCT and ADST/ADST.FIG. 8Dis described below.

FIGS. 9A-9Care diagrams illustrating the use of a scatter-based scan table for a 4×4 block transformed using a second combination of transforms. In this case, the percentages ofFIG. 9Aform a 2D array900showing the probability that a transform coefficient at each position in a 4×4 block may have a non-zero value following transformation that applies DCT horizontally and ADST vertically. Similarly to the discussion above in relation toFIG. 8A, these probabilities are formed by processing one or more video streams, calculating quantized transform coefficients for 4×4 blocks of frames of the video streams that are subject to the second combination of transforms and calculating the percentages for each block position.FIG. 9B, likeFIG. 8B, is a 1D array902with the probabilities arranged in decreasing order so that the transform coefficients with the highest probability of being non-zero are near the beginning of 1D array902and the transform coefficients with the lowest probability of being non-zero are near the end of 1D array902.FIG. 9Cis a 1D array904illustrating a scatter scan order using 1D array902ofFIG. 9B. 1D array904represents another entry in one or more scatter-based tables that may be indexed by block size and/or transform combination. In the case ofFIGS. 9A-9C, the block size is 4×4, and the transform combination is ADST/DCT. The second combination of transforms may be used where, for example, a block is intra predicted using a vertical-based intra prediction mode. If relevant, that is, if the prediction mode makes a difference in the resulting 1D array, the entry may also be indexed by prediction mode.

FIGS. 10A-10Care diagrams illustrating the use of a scatter-based scan table for a 4×4 block transformed using a third combination of transforms. In this case, the percentages ofFIG. 10Aform a 2D array1000showing the probability that a transform coefficient at each position in a 4×4 block may have a non-zero value following transformation that applies ADST horizontally and DCT vertically. Similarly to the discussion above in relation toFIGS. 8A and 9A, these probabilities are formed by processing one or more video streams, calculating quantized transform coefficients for 4×4 blocks of frames that are subject to the third combination of transforms and calculating the percentages for each block position.FIG. 10B, likeFIGS. 8B and 9B, is a 1D array1002with the probabilities arranged in decreasing order so that the transform coefficients with the highest probability of being non-zero are near the beginning of 1D array1002and the transform coefficients with the lowest probability of being non-zero are near the end of 1D array1002.FIG. 10Cis a 1D array1004illustrating a scatter scan order using 1D array1002ofFIG. 10B. 1D array1004represents another entry in one or more scatter-based tables that may be indexed by block size and/or transform combination. In the case ofFIGS. 10A-10C, the block size is 4×4, and the transform combination is DCT/ADST. This third combination of transforms may be used when a horizontal-based intra prediction mode is used in one example, and the scatter-based table may also be indexed by prediction mode if relevant.

Blocks of other sizes than 4×4 may be used in accordance with the teachings herein as shown inFIGS. 11-17.FIGS. 11-13provide examples of the teachings herein applied to 8×8 blocks,FIGS. 14-16provide examples of the teachings herein applied to 16×16 blocks, andFIG. 17provides an example of the teachings herein applied to a 32×32 block.

FIG. 11is a diagram of percentages of non-zero coefficients for an 8×8 block transformed using the first combination of transforms. The first combination of transforms, in this example, is either DCT/DCT or ADST/ADST. The probabilities ofFIG. 11are values generated similarly to the process described above with respect toFIGS. 8A, 9A, 10A. In this case, those 8×8 residual blocks transformed using the first combination of transforms and then quantized from one or more sample video streams are used to generate the percentages ofFIG. 11. The transform coefficients in each location for the blocks that have non-zero values versus those that have zero values are used to generate the probabilities in each location ofFIG. 11. The 2D array ofFIG. 11may be used to generate an entry in one or more scatter-based scan tables as described above with respect toFIGS. 8B and 8C, 9B and 9C, and 10B and 10C. Index values for the entry may be an 8×8 block, the first combination of transforms and, if relevant, prediction mode.

FIG. 12is a diagram of percentages of non-zero coefficients for an 8×8 block transformed using the second combination of transforms. The second combination of transforms in this example, as described above, is ADST/DCT. The probabilities ofFIG. 12are values generated similarly to the process described above with respect toFIG. 11. The 2D array ofFIG. 12may be used to generate an entry in one or more scatter-based scan tables as described above with respect toFIGS. 8B and 8C, 9B and 9C, and 10B and 10C. Index values for the entry may be an 8×8 block, the second combination of transforms and, if relevant, prediction mode.

FIG. 13is a diagram of percentages of non-zero coefficients for an 8×8 block transformed using the third combination of transforms. The third combination of transforms, in this example, is DCT/ADST. The probabilities ofFIG. 13are values generated similarly to the process described above with respect toFIG. 11. The 2D array ofFIG. 13may be used to generate an entry in one or more scatter-based scan tables as described above with respect toFIGS. 8B and 8C, 9B and 9C, and 10B and 10C. Index values for the entry may be an 8×8 block, the third combination of transforms and, if relevant, the prediction mode.

FIG. 14is a diagram of percentages of non-zero coefficients for a 16×16 block transformed using the first combination of transforms.FIG. 15is a diagram of percentages of non-zero coefficients for a 16×16 block transformed using the second combination of transforms.FIG. 16is a diagram of percentages of non-zero coefficients for a 16×16 block transformed using the third combination of transforms.FIG. 17is a diagram of percentages of non-zero coefficients for a 16×16 block transformed using the first combination of transforms. The 2D arrays ofFIGS. 14-17may be generated and used as described above.

It is useful to note thatFIGS. 8A-16were generated using certain sets of blocks, prediction modes, transforms and quantization values. Accordingly, the 2D arrays and resulting 1D arrays are only examples of techniques for generating scatter-based scan table entries. Other block sizes, prediction modes, combinations of transforms and/or quantization values may be used. Further, since these examples are derived from certain sample video streams, other video streams may result in different values.

Referring again toFIG. 5, the one or more scatter-based scan tables generated as described above may be used in steps504and506. As mentioned above, a transform coefficient is identified from the 2D transform coefficient array formed from a residual block at step504. The identified transform coefficient is included in a 1D array of transform coefficients at an array position based on the position of the transform coefficient in the 2D array and a probability associated with the array position. This identification may be performed by selecting the appropriate table entry from a scatter-based scan table using the indices described above. For example, if the residual block is a 16×16 block transformed using ADST/DCT, a scan order such as that represented generated using the 2D array ofFIG. 15may be used to determine the position of each of the transform coefficients of the block for entropy encoding. In contrast, if the residual block is a 4×4 block transformed using DCT/DCT, a scan order such as that represented by 1D array804may be used to determine the position of each of the transform coefficients of the block for further encoding. In this latter example, if the transform coefficient is coefficient 03 in the 2D array of block700, for example, the transform coefficient is at the 9thposition in the resulting 1D array by reference to 1D array804. Such a transformation is applied to all transform coefficients associated with the current block.

At step508, process500generates an encoded block based on the 1D array formed at step506. The 1D array is formed by taking each transform coefficient of the 2D array and positioning it at a position in a 1D vector according to a scatter scan pattern based on the probability rank determined for its position in the 2D array as described above. The further encoding may include entropy encoding as described previously. A series of 1D arrays formed from 2D arrays of transform coefficients corresponding to each block of a frame can be further encoded by an encoder, such as encoder300, to form an encoded frame. The encoded block may be included in an encoded video bitstream at step510, generally with other encoded blocks of the frame. Note that no additional bits must be included in the encoded video bitstream to indicate which scatter scan pattern was used to encode each block of the frame. Which scatter scan pattern was used to encode each block of the frame may be identified by examination of bits that indicate, e.g., the block size, the prediction mode used to predict the block and the transform mode used to transform the block, thereby eliminating the need to add bits to the encoded video bitstream to identify the scatter scan pattern explicitly. At step512, the encoded video bitstream can be stored using storage devices described above in relation toFIG. 1or transmitted for decoding and subsequent viewing.

FIG. 6is a flow diagram of a process600for decoding blocks of frames of an encoded video bitstream in accordance with an implementation of this disclosure. Process600is also referred to as a method of operation and can be implemented in a decoder such as decoder400. Process600can be implemented, for example, as a software program that can be executed by computing devices such as transmitting station102or receiving station110. The software program may include machine-readable instructions that can be stored in a memory such as memory106or memory114, and that can be executed by a processor, such as CPU104, to cause the computing device to perform process600.

Process600can be implemented using specialized hardware or firmware. Some computing devices can have multiple memories, multiple processors, or both. The steps of process600can be distributed using different processors, memories, or both. Use of the terms “processor” or “memory” in the singular encompasses computing devices that have one processor or one memory as well as devices that have multiple processors or multiple memories that can each be used in the performance of some or all of the recited steps. For simplicity of explanation, process600is depicted and described as a series of steps. However, steps in accordance with this disclosure can occur in various orders and/or concurrently. Additionally, steps in accordance with this disclosure may occur with other steps not presented and described herein. Furthermore, not all illustrated steps may be required to implement a method in accordance with the disclosed subject matter.

Process600assumes that a bitstream of video data having multiple frames, each having multiple blocks, is being encoded using a video encoder such as video encoder300executing on a computing device such as transmitting station102. The video data or bitstream can be received by the computing device in any number of ways, such as by receiving the video data over a network, over a cable, or by reading the video data from a primary memory or other storage device, including a disk drive or removable media such as a CompactFlash (CF) card, Secure Digital (SD) card, or any other device capable of communicating video data. In some implementations, video data can be received from a video camera connected to the computing device operating the encoder. At least some of the blocks within frames are entropy coded using transform coefficients as described in more detail below.

At step602, process600can identify a 1D transform coefficient array including plurality of transform coefficients for a block of a frame of the encoded video bitstream. By identify, we can mean determine, calculate, select, distinguish or other identify in any manner whatsoever. This can occur during decoding a block of a frame of the encoded video bitstream. The encoded video bitstream can include partitions that include encoded blocks. The encoded blocks can be, for example, entropy decoded as described in relation to step402ofFIG. 4. Following entropy decoding, the plurality of transform coefficients can be included in a 1D array.

At step604, process600can identify a transform coefficient from the plurality of transform coefficients. This step indicates that each transform coefficient in the 1D array may be processed individually. In operation, a decoder may access the transform coefficients in order from the beginning of the 1D array to the end, identifying each transform coefficient in the 1D array. Once identified, the transform coefficient is included in a 2D array representing the block to be further decoded at step606. The position at which the identified transform coefficient is included in the 2D array is based on the position of the transform coefficient in the 1D array and a probability of the transform coefficient having a zero or non-zero value. If the probability is associated with a zero value, the sequence would remain the same based on arranging the probabilities in increasing order, instead of decreasing order. Step606may be performed by using the scatter scan pattern selected from one or more scatter-based scan tables described with respect toFIG. 5. As mentioned above, the scatter-based scan table(s) may be included in both the encoder and decoder before encoding and decoding video streams to eliminate the need to send the tables in the encoded video bitstream.

At the time a decoder receives an encoded video stream, bits included in the encoded video bitstream (e.g., in frame, partition or block headers) can indicate block size, prediction mode and/or transform mode. These values may be used as indices to select which scatter scan pattern within a scatter-based scan table was used to encode the block and therefore which scatter scan pattern to use to decode the block. Referring toFIG. 10, when the block to be decoded is a 4×4 block transformed using the third combination of transforms, in this example DCT/ADST, the scatter-based scan table would indicate 1D array1004as the sequence of the transform coefficients.

FIG. 18is a diagram of a two-dimensional array1800generated using the one-dimensional array1004ofFIG. 10C. As seen therein, the first transform coefficient of 1D array1004is included at position (0,0) of 2D array1800, the second transform coefficient of 1D array1004is included at position (1,0) of 2D array1800, the third transform coefficient of 1D array1004is included at position (2,0) of 2D array1800, the fourth transform coefficient of 1D array1004is included at position (0,1) of 2D array1800and so on. While not applicable in this example, the 1D array formed for the block to be encoded may be compressed by eliminating trailing zeros through the use of an EOB token described above. In such a case, the 1D array would have fewer values than the number of values in the 2D array that it is being arranged into using the scatter scan pattern. Since the trailing values are all zeros, after arranging all of the available values of the 1D array into the 2D array, any unfilled positions in the 2D array may be set to zero. This may simplify processing of an encoded block if an EOB token is detected.

Returning toFIG. 6, process600generates a decoded block at step608based on the 2D transform coefficient array formed at step606. By generate, we can mean develop, form, calculate, make, introduce or in any manner whatsoever generate. The 2D transform coefficient array formed at step608with transform coefficients restored to the positions at which they were originally placed when the 2D array was transformed and quantized by an encoder. In general, the decoded block may be generated by de-quantizing the transform coefficients (if originally quantized), inverse transforming the resulting 2D array to form, e.g., a residual, forming a prediction block for the current block and adding the prediction block to the residual to form the decoded current block. Following entropy decoding and scanning to arrange the series of 1D arrays representing each block of a frame into 2D arrays, the blocks of the frame can be further decoded as described in relation toFIG. 4to form a decoded frame.

At step610, the decoded block and frame can be included in a decoded video stream. By include we can mean add, append, combine, incorporate or otherwise include in any manner whatsoever. The decoded video stream can be viewed or stored for later viewing or processing.

The patterns of non-zero coefficient probabilities represented inFIGS. 8A, 9A, 10A and 11-17reveal at least one reason scatter scan patterns group zero coefficients more efficiently than sequential scan orders. That is, the distribution of non-zeroes around the DC coefficient is not based on a straight line from edge to edge around the DC coefficient. Rather, the distribution is a radial curve around the DC coefficient. Looking atFIG. 17, for example, the contour formed by the positions having a 1% probability of being non-zero versus positions having 0% probability of being non-zero starts at the 23rdposition along the top row of values and proceeds in an arc to the 32ndposition on the left-hand column. Raster-based scan orders, including zig-zag, column and row, all traverse the 2D array in basically straight lines, either along rows and columns or diagonally (zig-zag). In contrast, scatter scan patterns disclosed herein are capable of tracking any arrangement of probabilities to insure that coefficients having a low probability of being non-zero are all properly grouped regardless of the distribution of probabilities in the 2D array. Accordingly, over a number of blocks, the number of explicitly coded zero coefficients (that is, those before the EOB token) is reduced as compared to a raster-based scan order. It is also worth noting that, in all examples, vertical correlation (and thus “zero-ness”) is less than horizontal, thus the scatter-based scan tables have a slight vertical over horizontal bias in the resulting scan order.

By arranging transform coefficients into a 1D array for ordering within an encoded bitstream, there is an increased probability that the largest number of zero coefficients is grouped together at the end of the 1D array. In this way, the compression of a frame according to the teachings herein may be increased by maximizing the zero coefficients located before the EOB token, thus minimizing the zero coefficients located before the EOB token that need to be explicitly coded.

It is useful to note that, while the scan table is described generally as a table with entries corresponding to 1D arrays of transform coefficients with index values based on the transform size, etc., this is not necessary. Each 1D array may be stored as a separate scan table in the form of 2D array in raster-scan order that provides the position of the coefficient in the array. For example, 1D array804may be stored as 2D array806as shown inFIG. 8D.

One method and apparatus for encoding a video stream includes, for example, identifying a two-dimensional (2D) transform coefficient array including a plurality of transform coefficients corresponding to a block of a frame of the video stream, identifying a transform coefficient from the plurality of transform coefficients, including the transform coefficient in a one-dimensional (1D) transform coefficient array at a 1D array position based on 2D array position of the transform coefficient in the 2D transform coefficient array and a probability associated with the 2D array position, wherein the probability is based on one or more video streams other than the video stream, generating an encoded block based on the 1D transform coefficient array, and including the encoded block in an encoded video stream.

The aspects of encoding and decoding described above illustrate some exemplary encoding and decoding techniques. However, it is to be understood that encoding and decoding, as those terms are used in the claims, could mean compression, decompression, transformation, or any other processing or change of data.

Implementations of transmitting station102and/or receiving station110(and the algorithms, methods, instructions, etc., stored thereon and/or executed thereby, including by encoder300and decoder400) can be realized in hardware, software, or any combination thereof. The hardware can 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 circuit. In the claims, the term “processor” should be understood as encompassing any of the foregoing hardware, either singly or in combination. The terms “signal” and “data” are used interchangeably. Further, portions of transmitting station102and receiving station110do not necessarily have to be implemented in the same manner.

Further, in one aspect, for example, transmitting station102or receiving station110can be implemented using a general purpose computer or general purpose processor with a computer program that, when executed, carries out any of the respective methods, algorithms and/or instructions described herein. In addition or alternatively, for example, a special purpose computer/processor can be utilized which can contain other hardware for carrying out any of the methods, algorithms, or instructions described herein.

Transmitting station102and receiving station110can, for example, be implemented on computers in a video conferencing system. Alternatively, transmitting station102can be implemented on a server and receiving station110can be implemented on a device separate from the server, such as a hand-held communications device. In this instance, transmitting station102can encode content using an encoder300into an encoded video signal and transmit the encoded video signal to the communications device. In turn, the communications device can then decode the encoded video signal using a decoder400. Alternatively, the communications device can decode content stored locally on the communications device, for example, content that was not transmitted by transmitting station102. Other suitable transmitting station102and receiving station110implementation schemes are available. For example, receiving station110can be a generally stationary personal computer rather than a portable communications device and/or a device including an encoder300may also include a decoder400.