Segmentation based entropy encoding and decoding

A system, method, and apparatus for encoding and decoding a video signal having at least one frame with a plurality of blocks are disclosed. The method disclosed includes, in one implementation, transforming coefficients in the plurality of blocks, quantizing the transformed coefficients, and ordering the quantized transform coefficients such that zero value coefficients and non-zero value coefficients are grouped together. The method also includes identifying at least one characteristic associated with at least one of the transform coefficients, an encoding process, or a quantization process, determining at least one threshold criteria for a segment, comparing the at least one threshold criteria for the segment with the at least one identified characteristic using a processor, and assigning the at least one block in the plurality of blocks to a segment based on the comparison.

TECHNICAL FIELD

The present invention relates in general to encoding and decoding and in particular to entropy encoding and decoding of video.

BACKGROUND

Digital video streams typically represent video using a sequence of frames (i.e. still images). An increasing number of applications today make use of digital video stream encoding for purposes other than traditional moving pictures (such as movies and video clips). For example, screen capture and screen casting applications generally represent the output of a computer monitor over time as a digital video stream, irrespective of the specialized nature of the content of the monitor. Typically, screen capture and screen casting digital video streams are encoded using video encoding techniques like those used for traditional moving pictures. To permit transmission of digital video streams while limiting bandwidth consumption, a number of video compression schemes have been devised.

SUMMARY

Embodiments of systems, methods, and apparatuses for encoding and decoding a video signal are disclosed herein. One aspect of the disclosed embodiments is a method for encoding a video signal having at least one frame with a plurality of blocks containing one or more coefficients. The method includes transforming the coefficients in the plurality of blocks and quantizing at least some of the transformed coefficients to generate zero value quantized coefficients and non-zero value quantized coefficients. The quantized transform coefficients are ordered in at least one of the plurality of blocks such that at least some zero value quantized coefficients are grouped together. At least one entropy-related characteristic, associated with the at least one block, is identified. The at least one block is assigned to the segment based on the at least one identified entropy-related characteristic. The at least one block is encoded.

Another aspect of the disclosed embodiments is a method for encoding a video signal having at least one frame with a plurality of blocks, wherein the method includes identifying at least one characteristic associated with at least one of the plurality of blocks, an encoding process, or a quantization process, transforming coefficients in the plurality of blocks, quantizing the transformed coefficients and ordering the quantized transform coefficients such that zero value coefficients and non-zero value coefficients are grouped together. The method also includes determining at least one threshold criteria for a segment, comparing the at least one threshold criteria for the segment with the at least one identified characteristic associated with at least one of the plurality of blocks using a processor and assigning the at least one block in the plurality of blocks to a segment based on the comparison. The at least one block is then encoded.

Another aspect of the disclosed embodiment is an apparatus for encoding a video signal having at least one frame with a plurality of blocks. The apparatus includes a memory and a processor in communication with the memory. The processor is configured to execute instructions stored in the memory. The instructions permit the processor to transform the coefficients in the plurality of blocks and quantize at least some of the transformed coefficients to generate zero value quantized coefficients and non-zero value quantized coefficients. The processor orders the quantized transform coefficients in at least one of the plurality of blocks such that at least some zero value quantized coefficients are grouped together. The processor identifies at least one entropy-related characteristic associated with the at least one block. The processor assigns the at least one block to a segment based on the at least one identified entropy-related characteristic. The processor encodes the at least one block.

DETAILED DESCRIPTION

Digital video is used for various purposes including, for example, remote business meetings via video conferencing, high definition video entertainment, video advertisements, and sharing of user-generated videos. As technology is evolving, users have higher expectations for video quality and expect high resolution video even when transmitted over communications channels having limited bandwidth.

Digital video streams can include formats such as VP8 and other VPx codecs, promulgated by Google Inc. of Mountain View, Calif., and H.264, a standard promulgated by ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG), including present and future versions thereof. H.264 is also known as MPEG-4 Part 10 or MPEG-4 AVC (formally, ISO/IEC 14496-10).

In encoding systems, data from the digital video stream is separated into frames and further separated into blocks of data in each frame. In some cases, data in these blocks are ordered such that non-zero value data and zero value data are grouped together. For some encoders such as some encoders using VP8 data format, each block within a frame contains a special end of block (EOB) token that indicates when the group of zero value data begins or when the final non-zero data occurs. This EOB data can be sent in the data stream to a decoder. While sending the EOB data may be cheaper than encoding a run of zero values for each block, there is still a cost incurred for almost every block which may account for a significant number of bits for each encoded frame. A system and method capable of reducing the amount of overhead data including EOB data can result in significant gains in compression efficiency.

FIG. 1is a schematic of a video encoder and decoder system10for still or dynamic video images. An exemplary transmitting station12can be, for example, a computer having an internal configuration of hardware including a processor such as a processor14. In this example, processor14is a central processing unit. Processor14controls the operations of the transmitting station12. The processor14is connected to the memory16by, for example, a memory bus. The memory16can be random access memory (RAM) or any other suitable memory device. The memory16can store data and program instructions which are used by the processor14. Other suitable implementations of transmitting station12are possible.

A network17connects the transmitting station12and a receiving station18for encoding and decoding of the video stream. Specifically, the video stream can be encoded in the transmitting station12and the encoded video stream can be decoded in the receiving station18. The network17can, for example, be the Internet. The network17can also be a local area network (LAN), wide area network (WAN), virtual private network (VPN), or any other means of transferring the video stream from transmitting station12.

The receiving station18, in one example, may be a computer having an internal configuration of hardware including a processor such as a processor20, which in this case is a central processing unit, and a memory22. The processor20controls the operations of the receiving station18. The processor20can be connected to the memory22by, for example, a memory bus. The memory22may be RAM or any other suitable memory device. The memory22stores data and program instructions which are used by the processor20. Other suitable implementations of the receiving station18are possible.

A display24configured to display a video stream can be connected to the receiving station18. The display24can be implemented in various ways, including with a liquid crystal display (LCD) or a cathode-ray tube (CRT). The display24can be configured to display a video stream decoded at the receiving station18.

Other implementations of the encoder and decoder system10are possible. For example, one implementation can omit the network17and/or the display24. In another implementation, a video stream can be encoded and then stored for transmission at a later time by the transmitting station12or any other device having memory. In another implementation, additional components may be added to the encoder and decoder system10. For example, a display or a video camera may be attached to transmitting station12to capture the video stream to be encoded. In one implementation, receiving station18includes display24. Although processors14and20are illustrated by single central processing units, the term “processor” encompasses a system with a single processing unit, a system with multiple processing units, and multiple systems with one or more processing units operating in parallel or otherwise to implement the disclosed embodiments. Although memories16and22are shown as single units, the term “memory” encompasses memory (including different kinds of memory) physically distributed across multiple units as appropriate, including for example the RAM used in connection with processors preforming the disclosed embodiments in parallel and network-based storage.

FIG. 2is a diagram a typical video stream30to be encoded and decoded. Video coding formats, such as VP8 or H.264, provide a defined hierarchy of layers for the video stream30. The video stream30includes a video sequence32. At the next level, the video sequence32includes a number of adjacent frames34. While three frames are depicted as the adjacent frames34, the video sequence32can include any number of adjacent frames. At the next level, the adjacent frames34can be further analyzed as individual frames, e.g., a single frame36. At the next level, the single frame36can be divided into a series of blocks38, which can contain data corresponding to, for example, a 16×16 pixel group of displayed pixels in the frame36. Each block38can contain luminance and chrominance data for the corresponding pixels. The blocks38can also be of any other suitable size such as 16×8 pixel groups, 8×16 pixel groups, or 4×4 pixel groups.

FIG. 3is a block diagram of an encoder40in accordance with one exemplary embodiment. In one exemplary embodiment, encoder40is implemented as software resident in memory16of transmitting station12. The software is executed by processor14to perform the operation of encoder40as described below. Encoder40encodes an input video stream30, and can be implemented, as described above, in the transmitting station12. The encoder40has 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 bitstream44: an intra/inter prediction stage46, a transform stage48, a quantization stage50, and an entropy encoding stage52. The entropy encoding stage52may also provide feedback to the quantization stage50to alter quantization or to provide updates to a segmentation map. The encoder40also includes a reconstruction path (shown by the dotted connection lines) to reconstruct a frame for encoding of further blocks. The encoder40has the following stages to perform the various functions in the reconstruction path: a dequantization stage54, an inverse transform stage56, a reconstruction stage58, and a loop filtering stage60. Other structural variations of encoder40can be used to encode input video stream30.

When the input video stream30is presented for encoding, each frame36within input video stream30is processed in units of blocks. At intra/inter prediction stage46, each block can be encoded using either intra-frame prediction (i.e., within a single frame) or inter-frame prediction (i.e. from frame to frame). In either case, a prediction block can be formed. 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.

Next, still referring toFIG. 3, the prediction block can be subtracted from the current block at the intra/inter prediction stage46to produce a residual block (residual). The transform stage48transforms the residual into 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”), and the Singular Value Decomposition Transform (“SVD”). 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 (i.e. DC) coefficient at the top-left of the matrix and the highest frequency coefficient at the bottom-right of the matrix.

The quantization stage50converts the transform coefficients into discrete quantum values, which are referred to as quantized transform coefficients or quantization levels. The quantized transform coefficients are then entropy encoded by the entropy encoding stage52. The entropy-encoded coefficients, together with the information required to decode the block, such as the type of prediction used, motion vectors, and quantizer value, are then output to the compressed bitstream44. The compressed bitstream44can be formatted using various techniques, such as run-length encoding (RLE) and zero-run coding.

In one exemplary embodiment, the reconstruction path inFIG. 3(shown by the dotted connection lines) can be used to ensure that both the encoder40and a decoder62(described below with reference toFIG. 4) use the same reference frames to decode the compressed bitstream44. 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 the dequantization stage54and inverse transforming the dequantized transform coefficients at an the inverse transform stage56in order to produce a derivative residual block (derivative residual). At the reconstruction stage58, the prediction block that was predicted at the intra/inter prediction stage46can be added to the derivative residual to create a reconstructed block. The loop filtering stage60can be applied to the reconstructed block to reduce distortion such as blocking artifacts.

Other variations of the encoder40can be used to encode compressed bitstream44. For example, a non-transform based encoder40can quantize the residual signal directly without the transform stage48.

The encoding process shown inFIG. 3can also include two iterations or “passes” of processing the video data. The first pass can be carried out by the encoder40using an encoding process that is less computationally intensive which gathers and stores information about the input video stream30for use in the second pass. In the second pass, represented as the solid line between the intra/inter prediction stage46and the entropy encoding stage52, the encoder40uses this information to optimize a later encoding, the final output of which may be the compressed bitstream44. For example, the encoder40may use this information to select parameters for encoding, locating key-frames, selecting coding modes used to encode blocks38, and allocating the number of bits to each frame36. Parameters for encoding such as coding modes, including prediction modes, can also be stored in the memory16and used to select a zero bin at the quantization stage50. The zero bin in some cases is a range of quantized coefficient values (e.g., −0.5 to +0.5) that will be rounded to zero prior to entropy encoding.

FIG. 4is a block diagram of a decoder62in accordance with another embodiment. The decoder62decodes a compressed bitstream44and can be implemented, as described above, in the receiving station18. In one exemplary embodiment, decoder62is implemented as software resident in memory22of receiving station18. The software is executed by processor20to perform the operation of decoder62as described below. The decoder62operates in a manner similar to the reconstruction path of the encoder40discussed above. In one exemplary embodiment, decoder62includes the following stages to perform various functions to produce an output video stream64from the compressed bitstream44: an entropy decoding stage66, a dequantization stage68, an inverse transform stage70, an intra/inter prediction stage72, a reconstruction stage74, a loop filter stage76, and a deblocking filter stage78. Other structural variations of decoder62can be used to decode the compressed bitstream44.

When the compressed bitstream44is presented for decoding, the data elements within the compressed bitstream44can be decoded by the entropy decoding stage66(using, for example, Context Adaptive Binary Arithmetic Decoding) to produce a set of quantized transform coefficients. The dequantization stage68dequantizes the quantized transform coefficients, and the inverse transform stage70inverse transforms the dequantized transform coefficients to produce a derivative residual that can be identical to that created by the reconstruction stage58in the encoder40. Using header information decoded from the compressed bitstream44, the decoder62can use the intra/inter prediction stage72to create the same prediction block as was created in the encoder40. At the reconstruction stage74, the prediction block can be added to the derivative residual to create a reconstructed block. The loop filter stage76can be applied to the reconstructed block to reduce blocking artifacts. The deblocking filter stage78can be applied to the reconstructed block to reduce blocking distortion, and the result is output as the output video stream64.

Other variations of decoder62can be used to decode the compressed bitstream44. For example, the decoder62can produce the output video stream64without the deblocking filter stage78.

FIG. 5is a schematic diagram of matrices of image data. The matrices are shown in 4×4 blocks as an example. Other block sizes, such as 8×8 or 16×16, are also possible. In the example shown inFIG. 5, matrix84is a 4×4 block of image sample data, such as luminosity or residual values after prediction. Matrix84is in this case the block of residual values obtained by subtracting a block of predicted values from a block of actual values as found in the input video stream30. Matrix86is an example 4×4 block of coefficients calculated by taking an arbitrary transform of matrix84. In practice, the transform can be performed using, for example, a DCT that transforms the image data found in matrix84into the frequency domain. In this example, matrix86could be the output of the transform stage48in the encoder40. The quantization stage50can remove the less visually significant high frequency data by dividing the coefficients in matrix86by an integer value. The results of quantization stage50are shown in matrix88. Because the quantization stage50removes coefficients with insignificant magnitudes, the image data contained in matrix88can be represented with a reduced number of coefficient values in one form of lossy compression.

After the quantization stage50, the transform coefficients may be re-ordered to group non-zero value coefficients together according to some aspects of a method in accordance with embodiments of this disclosure. An example scan order of the quantized coefficients of matrix88is shown in matrix110. The values of the quantized coefficients have been substituted with ordinal numbers showing each coefficient's place in the scan order. The optimum re-ordering path or scan order depends on the distribution of non-zero transform coefficients. In this case, the reordering path or scan order shown in matrix110inFIG. 5is a zig-zag order starting from the top left coefficient, labeled “0th,” and ending at the block labeled “15th.” Because the DCT transform process typically places higher magnitude coefficients in the upper left region and low magnitude or zero value coefficients in the lower right region, the output of this re-ordering process many times will result in an array of data values with a series of mostly non-zero coefficients at the start and a series of zero coefficients at the end so that some patterns are more easily recognizable for the entropy encoding stage52. Separating the zero and non-zero coefficients allows the array of data to be represented in a more compact manner. For example, the array may be represented as a series of (run, level) pairs where run indicates the number of zeros preceding a nonzero coefficient and level indicates the magnitude of a nonzero coefficient.

After the re-ordering process, the scanned coefficient values may be sent for entropy encoding at entropy encoding stage52. Referring again toFIG. 3, the entropy encoding stage52may use any number of entropy encoders including Huffman coding, arithmetic coding or context adaptive variable width coding, for example. In general, entropy encoders represent common or frequently used characters with fewer bits and represent uncommon characters with more bits, resulting in fewer bits used in total.

For example, using the coefficients contained in matrix88after being re-ordered in the scan order as shown in matrix110, the array of values would be [2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. After encoding, the data can be represented as 2,1,1, EOB. The EOB indicator tells the encoder that after the second 1 value, the remaining coefficients in the block are zero. In this way, the number of bytes needed to represent the data array can be reduced from 16 bytes to a smaller number of bytes.

In some cases, an EOB flag or indicator is used to indicate the occurrence of the last non-zero coefficient in a block. The EOB indicator permits the entropy encoding stage52to treat the coefficients following the EOB indicator as zero valued coefficients without using bits to represent zeros occurring after the EOB indicator.

Another example form of encoding, three-dimensional run-level encoding, can be used where each symbol encodes three quantities: run, level, and last. Last can indicate whether the level is the last non-zero value in the linear array. In an example of three-dimensional run-level encoding, the re-ordered array of values in matrix110could be represented as (0, 2, 0), (0, 1, 0), (0, 1, 1). Here, the 1 after the final run, level acts as an EOB indicator or flag that indicates that the final run, level is the last nonzero coefficient in the array of data for that particular block of data.

In one aspect of a disclosed embodiment, many blocks within a frame36will use an EOB indicator to indicate the position of the last non-zero quantized transform coefficient. In such embodiments, an EOB indicator is typically not necessary when the last quantized transform coefficient in a block is non-zero. Because of the nature of DCT transforms and quantization, this case rarely occurs except at very high data rates or quality levels. Accordingly, in most applications, because each block in a number of blocks38contained in a frame36typically uses an EOB indicator, EOB indicators can add a significant amount of data to a compression scheme thereby reducing the effectiveness of compression.

In accordance with one aspect of the disclosed embodiments, the encoder40assigns blocks38into segments according to at least one characteristic, which can be an entropy-related characteristic, such as for example, the position of the EOB indicator within an array of transformed and quantized data or the number of nonzero values occurring prior the EOB indicator. By “entropy-related” it is meant a characteristic of the quantized coefficients (including without limitation, the quantizing process used to generate the quantized coefficients or the underlying data represented in the coefficients) whose value or manipulation affects the coding efficiency of entropy encoding or other lossless encoding of those coefficients. The term coding efficiency includes the level of compression achieved, the processing efficiency of the encoding, or other metrics associated with the entropy or other lossless encoding scheme. The encoder40may also select segments according to any other characteristic associated with transform coefficients, the encoding process, or the quantization process. The segments may also be selected from several of these characteristics. Furthermore, these several characteristics may all be inputs for an algorithm executed in the memory16that provides an output used to determine a segmentation map.

In a simple example for illustrative purposes, the characteristic may only be the position of the EOB indicator. Referring again toFIG. 5and to matrix88and the scan order shown in matrix110, if the encoding scheme described above is implemented, the EOB indicator could be in a fourth position: 2, 1, 1, EOB. For clarity, the “end-of-block” position in this example is the position immediately following the last non-zero coefficient (except in the rare instance when the last non-zero coefficient is the last coefficient of the block, in which case the block has no end-of-block position). Assigning blocks with the same EOB position to the same segment allows the encoder40to automatically code all blocks in the segment with the assumption that each block in the segment has an EOB of four, for example. With this segmentation, blocks no longer need include the overhead of an EOB indicator. If a particular segment contains 50 blocks of data, and an EOB indicator is one bit of data, the EOB position for all blocks assigned to that segment can be communicated in fewer bits of data than if each block was required to include an EOB indicator.

Alternatively, a group of blocks can be assigned to a segment that indicates that the end-of-block is at a default position (such as four, for example). In such an embodiment, not every block within that segment may have an end-of-block at position four; some blocks may have an end-of-block at position two or three, for example. Thus, there may be a range of positions at which blocks within a segment end. In such cases, while the segment specifies the default end-of-block position, specific blocks assigned to the segment can include an EOB indicator in a lower position. Note that while a range of EOB positions within a block can be implemented (at the cost of having to include EOB indicators in blocks whose end-of-block position is short of the segment default), better performance can be achieved if all of the blocks in the segment have an end-of-block position that is no higher than the default end-of-block position specified by the segment. One reason why blocks within a segment may have different end-of-block positions is that the segment may be based on additional parameters besides end-of-block location. Therefore, it may be cost-effective to include blocks sharing one or more of those additional parameters within the segment, even though in regard to the end-of-block location additional coding in the form of EOB indicators is used for those blocks whose end-of-block position falls short of the segment default.

In some embodiments, as discussed above, the end-of-block location specified at the segment level can be a position in the scan order (such as the fourth position). Alternatively, the end-of-block condition can be specified at the segment level by indicating the number of non-zero coefficients in each block. The grouping process (seeFIG. 5and accompanying description) does not necessarily result in all non-zero coefficients followed by all zero coefficients. Rather, the grouping process may group coefficients so that initial coefficients are primarily (but not exclusive) non-zero coefficients and later coefficients are primarily (but not exclusively) zero coefficients. For example, typical coefficients could be 5,2,0,2,2,0,2,1,0,0, where zero and non-zero coefficients are interspersed. It is possible therefore to segment blocks by the number of non-zero coefficients, in which case blocks within the segment will likely have end-of-block positions falling within a range of end-of-block positions. In that case, in one implementation, the encoder counts the number of non-zero coefficients and determines that an end-of-block condition exists when the nthnon-zero coefficient is encountered, where n is the number of non-zero coefficients specified at the segment level.

FIG. 6shows a single frame600divided into blocks of data. The frame600could, for example, come from a video sequence of frames and be divided into blocks of pixel data as represented by the integers within the blocks of the example frame600.

FIG. 7depicts an exemplary process700of segmenting a frame, such as frame600, based on at least one characteristic such as an EOB indicator. Each time a new frame has been transformed at the transformation stage48and quantized at the quantization stage50, the encoder40can accept the new frame at step732and analyze the frame of quantized transform coefficients to identify at least one characteristic associated with each block in the frame at step734. The characteristic can be, for example, the position of the EOB indicator. The characteristic could also be other block characteristics such as quantizer level, motion vector data, block position with a frame, or transform coefficient data such as spatial frequency data or amplitude data. Once the at least one characteristic for segmentation is established at step734, segments may be broken up by threshold values represented by Thk, such that portions of a frame, such as the frame600shown inFIG. 6, can be divided into k segments where k can be any integer. A block could be identified and assigned to a segment with a single characteristic or could be identified and assigned to a segment based on several characteristics. Based on a comparison of the identified characteristic or characteristics with the threshold values Thk, step702assigns blocks to various segments.

For example, if each block in frame600contained a 4×4 matrix of coefficients such as matrix84, the EOB indicator could be one of 16 values as shown in matrix110. Accordingly, if the characteristic to be identified at step734is the position of the EOB indicator for each block, a given frame could assign each block to one of 16 segments according to an EOB threshold criteria for each segment such that a first segment, segment1, could have a threshold Th1, a second segment, segment2, could have a threshold Th2and so on up to a sixteenth segment, segment16, with a threshold of Th16. The threshold criteria for each segment can be determined through a process determined by a set of instructions stored in the memory16and executed in the processor14. In this aspect of a disclosed embodiment, each block will be assigned to a segment at step702. Alternatively, the encoder40may limit the number of possible segments to a subset of 16 segments such that some blocks remain unassigned to a segment.

Referring again toFIG. 6, a segmentation map602shows blocks from frame600being assigned to segments in accordance with embodiments described herein. Some blocks are not assigned to segments, such as blocks606and662, such that those blocks do not contain any segmentation designation on the segmentation map602.

Step702may cycle through all blocks in a frame in any predetermined order and compare each block in the frame with a first segment threshold Th1. For example, referring again toFIG. 6, the EOB position of a first block640in frame600can be compared with first threshold Th1for a first segment that contains blocks with an EOB position of 1. If first block640has an EOB at the first scan position, for example the 0th position shown in matrix110, then block640can be assigned to the first segment, segment1. If block640has an EOB at a different position, for example, the 11th position, block640can remain unassigned and the next block in a predetermined scan cycle order can be compared against Th1, e.g. block642. In one implementation, step702may repeat this process for 16 separate threshold values before continuing to step730or alternatively to step710. Steps730and710are further described below.

Alternatively, step702may assign each block to a segment based on a threshold comparison before cycling to the next block. For example, block640may be compared against each of the 16 thresholds and be assigned to a segment prior to cycling to the next block, e.g. block642. Step702may also use any other process capable of assigning blocks to segments based on at least one identified characteristic. For example, segments may be defined by an algorithm applied at the encoder40and decoder62or by segmentation of previously encoded frames. Furthermore, segmentation maps such as segmentation map602may persist from frame to frame with real time updates based on entropy encoding information fed back from the entropy encoding stage52as shown inFIG. 3rather than creating an entirely new segmentation map such as segmentation map602at step702for each frame.

In a second aspect of a disclosed embodiment, blocks may not contain a4x4set of quantized transform coefficients as in the first embodiment and as shown in matrix88. Rather, blocks may have a 16×16 set of coefficients such that each block contains 256 coefficients. Here, having a segment and threshold Thkfor each possible EOB position may cause process700as shown inFIG. 7to be computationally inefficient. Accordingly, each segment may contain multiple EOB positions. For example, if each block has 256 possible EOB positions, a first segment may include any block that has an EOB position from 1-16 while a second segment may include any block that has an EOB position from 16-32, and so on for all 256 positions.

Alternatively, some EOB coefficient positions may rarely be occupied, such as positions160-256, for example. Accordingly, only a subset of the possible EOB coefficient positions may be assigned to a segment. In one exemplary embodiment, shown inFIG. 6by the segmentation map602, only ten segments covering positions1-160are implemented. The EOB positions for each block are shown in frame600before segmentation. In this exemplary embodiment, blocks with EOB positions161-256may be left unassigned to a segment, e.g. as is shown in block606. For blocks with EOB positions161-256, such as606, each block may be individually encoded with an EOB indicator ranging from161-256at the entropy encoding stage52.

Referring again toFIG. 7, once a segmentation map602has been defined for a given frame at step702, the segmentation map602may be sent to the entropy encoding stage52at step710. One advantage of encoding a frame of image data according to a segmentation map is that for a large segment such as segment1covering EOB positions1-16and including block604, a large number of data blocks can be encoded without having to encode an EOB indicator for each block. Rather, for a given segment with n blocks, if an EOB indicator is one bit, for example, then n−1 bits of transmission data can be saved by the segmentation technique according to one aspect of a disclosed embodiment because only one EOB indicator per segment is required.

As indicated by dashed lines inFIG. 7, step730is optional in the process700. If step730is not included in the process700, once a segmentation determination for all blocks in a given frame is made in step702to create a segmentation map, the frame is encoded at the entropy encoding stage52according to step710. Once all segments are encoded for a given frame, the process700ends at step714and a new frame is accepted at step732. However, optional step730may be implemented in the process700to dynamically adjust the segmentation map602according to any factor, including characteristics related to transform coefficients, the encoding process, or the quantization process. Step730may also be used to perform testing on a segmentation map determined at step702to discern a cost/quality metric for the determined segmentation map.

Specifically, step706within step730may select individual blocks in a frame such as frame600inFIG. 6or a subset of blocks in the frame600such as blocks that have not yet been assigned to a segment in step702, e.g. block606. In either case, once a particular number of blocks has been selected at step706, step708determines if that block is within a predetermined proximity of a given segment threshold Thk. For example, referring again toFIG. 6, segment1has a segment threshold Thkof 16 and contains all blocks with an EOB indicator in coefficient positions1-16, including block604. Segment2has a segment threshold Thkof 32 and contains all blocks with an EOB indicator in coefficient positions17-32, including block608. Segment7has a segment threshold Thkof 112 and contains all blocks with an EOB indicator in coefficient positions97-112, including block660. Finally, segment10has a segment threshold Thkof 160 and contains all blocks with an EOB indicator in coefficient positions145-160, including block650. In the embodiment shown inFIG. 6and segmentation map602there are only ten possible segments. Here, blocks with an EOB indicator greater than 160 are not assigned to a segment at step702, including block606.

Referring to step708within step730, the proximity may be a dynamically determined or predetermined number. For example, if the predetermined proximity at step708is 2, block662with an EOB indicator position of161will be indicated as a block that is within a predetermined proximity of block650and hence be included in segment10. In one aspect of a disclosed embodiment, when a block is selected at step708, a determination is made as to whether the block should be included in the segment it is within a predetermined proximity of, or if the block should be excluded from the segment. In one aspect, this determination can be made by taking a quality metric, such as rate distortion, of frame600. For example, at step716, a rate distortion measurement can be taken of a first segmentation map602that include block662with block650in segment10. Step716can also take a second rate distortion measurement where block662remains amongst the unassigned blocks such as block606. Step716can then compare the measurements and alter the segmentation map602at step740if the quality measurement indicates an altered segmentation map would result in improved quality. However, if altering the segmentation map determined at step702does not result in improved quality, step710can encode the segmentation map determined at step702or perform an additional analysis at step720as shown inFIG. 7.

Step720within step730may perform the additional step of a cost/quality determination. The cost/quality determination may be a bit-cost analysis to determine if altering the segmentation map determined at step702provides a sufficient amount of bit savings prior to altering the segmentation map at step740. The additional cost/quality step720may perform any other form of testing or analysis known in the art to determine if the segmentation map determined at step702should be altered at step740or if the frame should be encoded at step710using the segmentation map determined at step702. The testing or analysis can be based upon one or more characteristics related to the encoding process. The determination can be made by a program or algorithm stored in the memory16and executed by the processor14.

If a block is not within a predetermined proximity of a segment, then the blocks may be encoded by the entropy encoding stage52at step710according to the segment map determined at step702, for example, according to segmentation map602. In the example segmentation map602, the segments including blocks604,606,608,650, and660may all be encoded by different coding schemes. For example the entropy encoding stage52may select from multiple encoding schemes including but not limited to various types of arithmetic coding, variable length coding, or context adaptive coding. The encoding schemes for each segment may be selected according to any characteristic related to the encoding process.

Although step734was discussed above with an EOB indicator as the identified characteristic, step734may identify several characteristics that are used alone or in combination to determine how blocks are assigned to various segments. For example, blocks may be assigned to segments based on inter-frame motion, such that blocks that contain similar motion vector information and similar EOB indicator positions are contained in the same segment. Identifying additional characteristics such as motion vector information for the segmentation process in step734may allow process700to more cheaply encode certain image characteristics that are less important to image quality as judged by the human visual system (HVS). For example, process700may assign more importance to blocks that include a high degree of movement such as block660in comparison with background blocks such as block604. For higher priority segments, process700may determine that step730should be skipped because including blocks that do not satisfy threshold criteria Thkcould prove more detrimental to video quality as determined by the HVS than would including blocks in a lower priority segment such as segment1including block604.

Furthermore, additional characteristics can help determine the EOB indicator position for a given block. For example, because segment1including block604is a background portion with little or no changes occurring between frames, the residual quantized transform coefficients are very likely to contain more zero coefficients than in segment7including block660which may include a relatively high degree of movement. Accordingly, the EOB indicator position for blocks in segment1, such as block604, is likely to be a low value such as 1-16, while the EOB indicator positions for blocks in segment7, such as block660, are more likely to occur much later in the block because the relatively unpredictable nature of the movement will result in a more complex residual signal with more non-zero quantized transform coefficients.

Accordingly, there can be one or several characteristics in place of or in addition to the EOB indicator position that is used to segment a given frame600. These characteristics may include but not limited to block location within a frame, frequency of assignment of particular blocks to particular segments in a frame, frequency of particular segment use, encoding scheme, quantizer level, zero bin size, motion vector data, coefficient amplitude data, or coefficient frequency data. Segmentation data can also include other entropy-related information including but not limited to segment-specific entropy coding behavior such as segment specific arithmetic encoder contexts that define the probability of each token (and hence how expensive different tokens are to encode). For example, a segment where the value “one” is common can have a segment-specific entropy context that makes a “one” cheaper to encode.

In some cases, the entropy, EOB position or other information is included for some segments but not others. Where the entropy, EOB position or other information is not included for a segment, the coefficients are encoded at the block level for the blocks in that segment.

Once the selected segmentation map is encoded at step710, the allocation of blocks to various segments can be explicitly coded in the compressed bitstream44or the allocation of blocks may be detected by the decoder62implicitly, based upon other information carried in the compressed bitstream44or determined algorithmically through analysis of the content or encoding choices in one or more previously encoded frames, for example.

The operation of encoding can be performed in many different ways and can produce a variety of encoded data formats. The above-described embodiments of encoding or decoding illustrate some exemplary encoding techniques. However, it shall be understood that encoding and decoding consistent with embodiments of this disclosure may include other transformations or change of data.

The embodiments of the transmitting station12and/or the receiving station18(and the algorithms, methods, instructions etc. stored thereon and/or executed thereby) can be realized in hardware, software, or any combination thereof. The hardware (such as processors14and20) can include, for example, 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 or other device capable of manipulating information. In the claims, the term “processor” should be understood as encompassing any the foregoing hardware, either singly or in combination. The terms “signal” and “data” are used interchangeably. Further, portions of transmitting station12and receiving station18do not necessarily have to be implemented in the same manner.

Further, in one embodiment, for example, the transmitting station12or the receiving station18can be implemented using a general purpose computer/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 specialized hardware for carrying out any of the methods, algorithms, or instructions described herein.

The transmitting station12and the receiving station18can, for example, be implemented on computers in a screen casting system. Alternatively, the transmitting station12can be implemented on a server and the receiving station18can be implemented on a device separate from the server, such as a hand-held communications device (e.g., a cell phone). In this instance, transmitting station12can encode content using an encoder40into 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 decoder62. Alternatively, the communications device can decode content stored locally on the communications device (i.e., content that was not transmitted by the transmitting station12). Other suitable transmitting station12and receiving station18implementation schemes are available. For example, the receiving station18can be a generally stationary personal computer rather than a portable communications device and/or a device including an encoder may also include a decoder.