Computational complexity and precision control in transform-based digital media codec

(54) Title: COMPUTATIONAL COMPLEXITY AND (57) Summary: PRECISION CONTROL IN TRANSFORMED-BASED DIGITAL MEDIA CODEC (30) Unionist Priority: 06/29/2007 us 11 / 772,076, 02/21/2007 US 60 / 891,031, 02/21/2007 US 60 / 891,031.29 / 06/2007 US 11 / 772,076 (73) Owner (s): Microsoft Corporation (72) Inventor (s): Chengjie Tu, Shankar Regunathan, Sridhar Srinivasan (74) Attorney ( es): DANNEMANN, SIEMSEN, BIGLER & IPANEMA MOREIRA (86) International Request: pct US2008054473 of 20/02/2008 (87) International Publication: wo 2008 / i03766de 28/08/2008

<img file="BRPI0807465A2_D0001.tif" />

Second stage

First stage “COMPUTATIONAL COMPLEXITY AND PRECISION CONTROL IN TRANSFORMED BASED DIGITAL MEDIA CODEC”

BACKGROUND

Block transform based coding

Transform encoding is a compression technique used in many digital media compression systems (for example, audio, image and video). Uncompressed digital image and video are typically represented or captured as samples of image elements or colors at locations in an image or video frame arranged on a two-dimensional (2D) network. This is referred to as a spatial domain representation of the image or video. For example, a typical format for images consists of a sample stream of the 24-bit color image element arranged as a network. Each sample is a number representing color components at a pixel location on the network within a color space, such as RGB, or YIQ, among others. Various image and video systems can use several different colors, time resolutions and sampling space. Similarly, digital audio is typically represented as a stream of audio signal sampled over time. For example, a typical audio format consists of a stream of 16-bit amplitude samples of an audio signal taken at regular time intervals.

Digital audio, image and video signals can assume considerable transmission and storage capacity. Transform encoding reduces the size of digital audio, images and video by transforming the spatial domain representation of the signal into a frequency domain representation (or other similar transform domain), and thus reducing the resolution of certain generally less frequent frequency components. of the transformed domain representation. This generally produces much less noticeable degradation of the digital signal compared to reducing the color or spatial resolution of images or video in the spatial domain, or audio in the time domain.

More specifically, an encoder / decoder system based on a typical block transform 100 (also called a codec) shown in Figure 1 divides the pixels of the uncompressed digital image into two-dimensional blocks of fixed size (X_1f ..., X_n), each block possibly overlapping the other blocks. A linear transform 120 to 121 that does spatial frequency analysis is applied to each block, which converts the spaced samples within the block to a set of frequency coefficients (or transform) usually representing the digital signal strength in corresponding frequency bands over the block range. For understanding, transform coefficients can be selectively quantized 130 (that is, reduced in resolution, such as dropping less significant bits of the coefficient values ​​or otherwise mapping values ​​into a set of higher resolution number at a lesser resolution) , and also encoded in variable length or entropy 130 in a compressed data stream. In decoding, the transform coefficients inversely transform 170 to 171 to almost reconstruct the original spatial / color sample of the image / video signal (reconstructed blocks Χί ..... X_n).

Block transform 120 to 121 can be defined as a mathematical operation on a vector x of size N. Most often, the operation is a linear multiplication, producing the transform domain output y = Mx, M being the transform matrix. When the input data is arbitrarily long, it is segmented into vectors of size N and the block transform is applied to each segment. For the purpose of data compression, reversible block transforms are shown. In other words, the matrix M is invertible. In multiple dimensions (for example, for image and video), block transforms are typically implemented as separable operations. Matrix multiplication is applied separately over each dimension of the data (that is, both rows and columns).

For understanding, transform coefficients (vector components y) can be selectively quantized (ie reduced in resolution, such as dropping less significant bits of the coefficient values ​​or otherwise mapping values ​​into a higher resolution number set for a lower resolution), and also encoded in variable length or entropy in a compressed data stream.

When decoding at decoder 150, the inverse of these operations (decoding / entropy decoding 160 and inverse block transform 170-171) is applied to the decoder side 150, as shown in Figure 1. While reconstructing the data, the inverse matrix M¹ (inverse transform 170 to 171) is applied as a multiplier to the transform domain data. When applied to transform domain data, the inverse transform almost reconstructs digital media from spatial domain or frequency domain.

In many coding applications based on the block transform, the transform is reversibly desirable to support both lossy and lossless compressions depending on the quantization factor. Without quantization (usually represented as a quantization factor of 1) for example, a codec using a reversible transform can exactly reproduce the input data in the decoding. However, the requirement for reversibility in these applications restricts the choice of transforms by which the codec can be designated.

Many video and image compression systems, such as MPEG Media and Windows, among others, use transforms based on the Discrete Cosine Transform (DCT). DCT is known to have favorable energy-condensing properties that result in almost optimal data compression. In these compression systems, the inverse DCT (IDCT) is used in the reconstruction loops in both the encoder and the decoder of the compression system for individual image reconstruction blocks.

Quantization

Quantization is the primary mechanism for most image and video codecs to control compressed image quality and compression radius. According to a possible definition, quantization is a term used as a non-reversible approximation mapping function commonly used for lossy compression, in which there is a specified set of possible output values, and each member of the set of possible output values has an associated set of input values ​​that result in the selection of that specific output value. A variety of quantization techniques have been developed, including vector or scalar quantization, uniform or non-uniform, with or without a death zone, and adaptive or non-adaptive.

The quantization operation is essentially a polarized division by a quantization parameter QP that is performed on the encoder. The multiplication or inverse quantization operation is a multiplication by the QP performed in the decoder. These processes together introduce a loss in the original transform coefficient data, which appears as errors or compression artifacts in the decoded image.

summary

The following detailed description presents tools and techniques for controlling computational complexity and decoding accuracy with a digital media codec. In one aspect of the techniques, the encoded signals one of the precision scale or non-scale modes to use in the decoder. In scale precision mode, the input image is pre-multiplied (for example, by 8) in the encoder. The output at the decoder is also scaled through rounding division. In a non-scale precision mode, no such scale operations are applied. In the non-scale precision mode, the encoder and decoder can die with a smaller dynamic range for transform coefficient, and thus have less computational complexity.

In one aspect of the techniques, the codec can also signal the precision required to perform transform operations for the decoder. In an implementation, an element of the bitstream syntax signals employs a less accurate arithmetic operation for the transform in the decoder.

This summary is provided to introduce a selection of concepts in a simplified way which is further described below in the Detailed Description. This summary is not intended to identify key characteristics or essential characteristics of the claimed subject material, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. Additional features and advantages of the invention will be made apparent from the following detailed description of the modalities that proceed with reference to the attached drawings.

Brief Description of Drawings

Figure 1 is a block diagram of a codec based on the conventional block transform in the prior art.

Figure 2 is a flow diagram of a representative encoder incorporating the standard block encoding.

Figure 3 is a flow diagram of a representative decoder incorporating the standard block encoding.

Figure 4 is a diagram of the reverse wound transform including a core transform and post-filter operation (overlap) in an implementation of the encoder / decode representative of Figures 2 and 3.

Figure 5 is a diagram for identifying the input data points for transform operations.

Figure 6 is a block diagram of a suitable computing environment to implement the media encoder / decoder of Figures 2 and 3.

Detailed Description

The following description refers to techniques for controlling computational accuracy and complexity of a transform-based digital media codec. The following description describes an exemplary implementation of the techniques in the context of a digital media compression system or codec. The digital media system encodes digital media data in a compressed form for transmission or storage, and decodes the data for playback or other processing. For the sake of illustration, this exemplary compression system incorporating computational complexity and precision control is a video or image compression system. Alternatively, the techniques can also be incorporated into compression systems or codecs for other digital media data. Computational complexity techniques and precision control do not require the digital media compression system to encode compressed digital media data in a specific encoding format.

1. Encoder / Decoder

Figures 2 and 3 are a generalized diagram of the process employed in an encoder 200 and a representative two-dimensional (2D) data decoder 300. The diagrams present a generalized or simplified illustration of a compression system incorporating the 2D data encoder and decoder that implement compression using computational complexity and precision control techniques. In alternative compression systems that use control techniques, the processes are additional or smaller than those illustrated in this representative encoder and decoder can be used for the compression of 2D data. For example, some encoders / decoders may also include color conversion, color formats, scalable coding, lossless coding, macroblock modes, etc. The compression system (encoder and decoder) can provide lossy and / or lossless compression of 2D data, depending on the quantization that can be based on a quantization parameter ranging from lossless to lossy.

The 2D data encoder 200 produces a compressed bit stream 220 which is a more compact representation (for typical input) of 2D data 210 presented as input to the encoder. For example, the input of 2D data can be an image, a frame of a video sequence, or other data having two dimensions. The 2D data encoder divides a frame of the input data into blocks (usually illustrated in Figure 2 as partitioning 230), which in the illustrated implementation are non-overlapping 4x4 pixel blocks that form a regular pattern across the plane of the frame. These blocks are grouped into clusters, called macroblocks, which are 16 * 16 pixels in size in this representative encoder. In turn, macroblocks are grouped into regular structures called plates. The plates also form a regular pattern over the image, such that the plates in a horizontal line are of uniform height and aligned, and the plates in a vertical column are of uniform width and aligned. In the representative encoder, the plates can be any arbitrary size that is a multiplication of 16 in the horizontal and / or vertical direction. Alternative encoder implementations can divide the image into blocks, macroblocks, plates, or other units of other sizes and structures.

A “direct overlay operator 240 is applied to each edge between the blocks, after which each 4x4 block is transformed using a block transform 250. This block transform 250 can be the reversible, free-scale 2D transform described by Srinivasan, US Patent Application No. 11 / 015,707, entitled, Reversible Transform For Lossy And Lossless 2 -D Data Compression, filed December 17,

2004. Overlay operator 240 may be the reversible overlay operator described by Tu et al., US Patent Application No. 11 / 015,148, entitled, Reversible Overlap Operator for Efficient Lossless Data Compression, filed December 17, 2004; and by Tu et al., US Patent Application No. 11 / 035,991, entitled, Reversible 2-Dimensional Pre- / Post-Filtering For Lapped Biorthogonal Transform, filed January 14,

2005. Alternatively, the discrete cosine transform or other block transform and overlap operators can be used. Subsequent to the transform, the DC 260 coefficient of each 4x4 transform block is subjected to a similar processing chain (plate, direct overlap, followed by 4x4 block transform). The resulting DC transform coefficients and AC transform coefficients are quantized 270, entropy encoded 280 and packaged 290.

The decoder performs the reverse process. On the decoder side, the bits of transform coefficients are extracted 310 from their respective packets, from which the coefficients are decoded by themselves 320 and dequantized 330. The DC 340 coefficients are regenerated by applying an inverse transform, and the plane of DC coefficients are “inversely overlaid” using a smoothing operator applied across the edges of the DC block. Subsequently, the entire data is regenerated by applying the 4X4 350 reverse transform to the DC coefficients, and the decoded DC coefficients 342 of the bit stream. Finally, the block edges in the resulting image planes are filtered in 360 reverse overlay. This produces reconstructed 2D data output.

In an exemplary implementation, encoder 200 (Figure 2) compresses an input image into the compressed bit stream (for example, a file), and decoder 300 (Figure 3) reconstructs the original input or an approximation of it, based on whether the encoding employed is lossy or lossless. The encoding process involves the application of a direct wound (LT) transform discussed below, which is implemented with reversible two-dimensional pre- / post-filtering also described more fully below. The decoding process involves the application of the inverse winding transform (ILT) using reversible two-dimensional pre- / post-filtering.

The illustrated LT and ILT are reversed from each other, in an exact sense, and therefore can be collectively referred to as reversible rolled transforms. As a reversible transform, the LT / ILT pair can be used for lossless image compression.

The input data 210 compressed by the illustrated encoder 200 / decoder 300 can be images of various color formats (for example, RGB / YUV4: 4: 4, YUV4: 2: 2 or YUV4: 2: 0 color image format) . Typically, the input image always has a luminance component (Y).

If it is an RGB / YUV4: 4: 4, YUV4: 2: 2 or YUV4: 2: 0 image, the image also has chrominance components, such as a U component and a V component. The separate color planes or components images can have different spatial resolutions. In the case of an input image in the YUV 4: 2: 0 color format, for example, the U and V components are half the width and length of the y component.

As discussed above, the encoder 200 plates the input image or macroblock image. In an exemplary implementation, encoder 200 plates the input image in areas of 16X16 pixels (called “macroblocks) in the Y channel (which can be 16x16, 16x8 or 8x8 areas in the U and V channels depending on the color format). Each macroblock color plane is plated in regions or blocks of 4X4 ​​pixels. Therefore, a macroblock is made up of several color formats as follows for this exemplary encoder implementation:

1. For a grayscale image, each macroblock contains 16 blocks of 4x4 (Y) luminance.

2. For a YUV4: 2: 0 color image, each macroblock contains 16 4x4 Y blocks, and each 4 4x4 chrominance blocks (U and V).

3. For a color image of YUV4: 2: 2 format, each macroblock contains 16 4x4 Y blocks, and each 8 4x4 chrominance blocks (U and V).

4. For an RGB or YUV4: 4: 4 color image, each macroblock contains 16 blocks from each Y, U and V channel.

Likewise, after the transformation, a macroblock in this representative encoder 200 / decoder 300 has three frequency sub-bands: a DC sub-band (DC macroblock), a low-pass sub-band (low-pass macroblock), and the high-pass subband (high-pass macroblock). In the representative system, the low-pass and / or high-pass sub-bands in the bit stream - these sub-bands can be abandoned entirely.

In addition, compressed data can be packaged within the bit stream in one of two orders: special order and frequency order. For the spatial order, different sub-bands of the same macroblock within a plate are ordered together, and the resulting bit stream from each plate is recorded within a package. For the frequency order, the same sub-band from different macroblocks within a board is grouped together, so the bit stream of a board is recorded in three packets: a DC board pack, a pass-through packet low, and a high-pass card pack. In addition, there may be other layers.

Thus, for the representative system, an image is organized in the following “dimensions”:

Spatial dimension: Plate -&gt; Macrobloco;

Frequency Dimension: DC | low pass | high pass; and

Channel dimension: Luminance | Chrominance_0 | ChrominanceJ ... (for example, as Y | U | V).

The lines above signify a hierarchy, while the vertical bars signify partitioning.

Although the representative system organizes compressed digital media data in space, frequency and channel dimensions, the flexible quantization approach described here can be applied to alternative encoder / decoder systems that organize your data along smaller dimensions, additional or other. For example, the flexible quantization approach can be applied to coding using a larger number of frequency bands, other color channel formats (eg YIQ, RGB, etc.), additional image channels (eg for viewing stereo or other multiple camera arrangements).

2. Inverse and Coiled Transformed Core

Overview

In one implementation, of encoder 200 / decoder 300, the reverse transform on the decoder side takes the form of a two-level coiled transform. The steps are as follows:

• An inverse core transform (ICT) is applied to each 4x4 block corresponding to the reconstructed DC and low-pass coefficients arranged in a flat arrangement known as the DC plane.

• A post-filtering operation is optionally applied to the 4x4 areas evenly matched around the blocks in the DC plane. Additionally, a post-filter is applied to the 2x4 and 4x2 boundary areas, and the four 2x2 corner areas are left untouched.

• The resulting arrangement contains DC coefficients of the 4x4 blocks corresponding to the first transform level. The DC coefficients are copied (figuratively) in a larger arrangement, and the reconstructed high-pass coefficients populated in the remaining positions.

• An ICT is applied to each 4x4 block.

• a post-filter operation is optionally applied to the 4x4 areas eventually hit around the blocks in the DC plane. Additionally, a post-filter is applied to the 2x4 and 4x2 boundary areas, and the four 2x2 curve areas are left untouched.

This process is shown in Figure 4.

The application of post-filters is governed by an OVERLAPJNFO syntactic element in the compressed bit stream 220. OVERLAP_INFO can acquire three values:

• If OVERI_AP_INFO = 0, no post-filtering is performed.

• If OVERLAP_INFO = 1, only external post-filtering is performed.

• If OVERLAPJNFO = 2, both internal and external post-filtering are performed

Inverse Core Transform

The core transform (CT) is inspired by the conventionally known Discrete Cosine Transform 4x4 (DCT), it is still fundamentally different. The first different key is that DCT is linear while CT is non-linear. The second different key is that because it is defined in real numbers, DCT is not a lossy operation for the entire space. The CT is defined in whole numbers and is without loss in space. The third different key is that the DCT 2D is a separable operation. The CT is not separable by the project.

The entire reverse transform process can be recorded as the cascade of three elementary 2x2 transform operations, which are:

• Hadamard 2x2 Transform: T_h • Reverse Rotation ID: lnvT_odd • 2D Reverse Rotation: lnvT_odd_odd

These transforms are implemented as non-separable operations and are first described, followed by the description of the entire ICT.

Hadamard 2D Transform 2x2 T_h

The encoder / decoder implements the 2D 2x2 T_h Hadamard transform as shown in the pseudocode table. R is a rounding factor that can be set to 0 or 1 only. T_h is involuntary (ie, two applications of T_h in a data vector [abed] successful in recovering original values ​​of [abcd], R provided is unloaded between applications). T_h is T_h itself.

<img file="BRPI0807465A2_D0002.tif" />

1D Reverse Rotation lnvT_odd

The lossless inverse of T_odd is defined by the pseudo-code in the following table.

InvTodd (a, b, c, d) {í b + = d;

c · ** + a ((3 * b + 4) »3), b +« ((3 * a + 4) »3); C ({3 * 4 + 4) »3}, d + =« 3'c + 4) »3):

c - = «b * 1)» 1), d ~ {(a + 1}&gt; »1) d, b + = c;

a - * = d;

2D Reverse Rotation lnvT_odd_odd

2D reverse rotation lnvT_odd_odd is defined by the pseudo-code in the following table.

<img file="BRPI0807465A2_D0003.tif" />

ICP operations

The correspondence between 2X2 data and the previously listed pseudocode is shown in Figure 5. Color coding using gray levels to indicate the four data points is introduced here, to facilitate the description of the transform in the next section.

The ICT 4X4 2D point is constructed using T_h, T_odd inverse and T_odd_odd inverse. Note that the inverse T_h is T h itself. ICT consists of two stages, which are shown in the following pseudocode. Each stage consists of four 2x2 transforms that can be done in any arbitrary sequence, or concurrently, within the stage.

If the input data block is 4x4_IPCT_2ndStage () they are defined as:

abc efgijkm η od

hl

P.

4x4_IPCT_lstStage () and

T_h (ac, i. K). hvTjjddÈb, d j. l); _ _.

JnvT_oJd {e rr g, t&gt;)₍

I / T cdd ocdff hnp) TJi (3, d, m, p).

TJ-lM.s. *} Fie b η pi Th I th)

The 2x2_ICT function is the same as T_h.

Post-filtering overview

Four operators determine the post-filters used in the reverse wound transform. These are:

• 4x4 post filter • 4 point post filter • 2x2 post filter • 2 point post filter

The post-filter uses T_h, lnvT_odd__odd, invScale and invRotate. invRotate and invScale are defined in the tables below, respectively.

invRotate (a, b) {j:

<img file="BRPI0807465A2_D0004.tif" />

4x4 post filter

Primarily, the 4X4 post-filter is applied to all joints of the blocks (areas that eventually hit the 4 blocks) in all color planes when OVERLAP_INFO is 1 or 2. Also, the 4x4 filter is applied to all joints of the blocks in the DC plane for all planes when OVERLAP_INFO is 2, and only for the luma plane when OVERLAP_INFO is 2 and the color format is YUV 4: 2.0 or YUV 4: 2: 2.

abcdef 8 hijkl

If the input data block is, the post filter 4x4, 4x4 Post filter (a, b, c, d, e, f, g, h, i, j, k, 1, m, n, o, p ), is defined as in the following table:

mn

<img file="BRPI0807465A2_D0005.tif" />

4-point post-filter

4-point linear filters are applied to the border, hitting 2X4 and 4X2 areas at the image boundary. If the input data is [abc d], the 4-point post filter, 4 post-filter (a, b, c, d) are defined in the following table

4PostFilter (a, b, c, d * = çi „b +« e ”d _« «au n íruRcsate {e. D&gt;

________ c + »{] $&gt; + ij,

-K »·· 3 &amp;

b ““ Λ «s (tb ra + = gtr 3 + 13).» 5j _______

2X2 post filter

The 2X2 post-filter is applied to areas of hit blocks in the DC plane for the YUV 4: 2: 0 and YUV 42: 2 data chroma channels. If the input data is post-filter 2x2 2x2Post-filter (a, b, c, d), it is defined as the following table:

B.C

<img file="BRPI0807465A2_D0006.tif" />

2x2PostF »lter (ab, c, d) ______ d- = gs * c - * {&amp;&gt; * b +» i (a + áj »-&gt; 2 / b * wf $ a * 2]» £ ** »“ * &amp; »'V„

i- «e.

2-point post-filter

The 2-point post-filter is applied to the 2X1 and 1X2 limit samples that hit the blocks. The 2-point post-filter, post-filter2 (a, b) is defined in the following table

2PostFilter (a, b b + = {{B * 4i * »3X, hi

The precision signaling required to perform transform operations for the rolled transform described above can be performed on the header of a compressed image structure. In the exemplary implementation, LONG_WORD_FI_AG and NO_SCALED_FLAGS are syntactic elements transmitted in the compressed bit stream (for example, in the image header) to signal precision and computational complexity to be applied by the decoder.

3. Speech length and accuracy

The exemplary encoder / decoder performs integer operations. Additionally, the exemplary encoder / decoder supports lossless encoding and decoding. However, the primary machine precision required by the exemplary encoder / decoder is an integer.

However, integer operations defined in the exemplary encoder / decoder allow rounding errors for lossy encoding. These errors are small by design, however they cause abandonment in the rate distortion curve. For the improved coding performance ratio by reducing rounding errors, the exemplary encoder / decoder defines secondary machine precision. In this mode, the input is pre-multiplied by 8 (that is, left shifted by 3 bits) and the final output is divided by 8 with rounding (that is, right shifted by 3 bits). These operations are performed on the encoder screen and at the rear of the decoder, and are largely invisible to the rest of the processes. In addition, the quantization levels are scaled in the same way as a flow created with primary machine precision and decoded using the second machine precision (and vice versa) produces an acceptable image.

Secondary machine precision cannot be used when lossless compression is desired. The machine precision used in creating a compressed file is explicitly marked in the header.

Secondary machine precision is equivalent to using scale arithmetic in the codec, and therefore this mode is referred to as Scale. Primary machine precision is referred to as non-scale.

The exemplary encoder / decoder is designed to provide good encoding and decoding speed. A design goal of the exemplary encoder / decoder is that the data values ​​in both the encoder and decoder do not exceed 16 signed bits for an 8-bit input. (However, the intermediate operation within a transform stage can exceed this figure). This holds true for both machine precision modes.

Conversely, when secondary machine precision is chosen, the range of intermediate values ​​is expanded by 8 bits. Since the primary machine precision prevents pre-multiplication by 8, its range expansion is 8 - 3 = 5 bits.

The first exemplary encoder / decoder uses two different word lengths for intermediate values. These lengths are 16 and 32 bits.

Second Bitstream Syntax and Semantics Example

The second example of bitstream syntax and semantics is hierarchical and is comprised of the following layers: Image, Plate, Macrobloco and Block.

Image (IMAGE)

<td>IMAGE () {</td><td colspan="2">N</td><td>In</td>

<td></td><td>one bits</td><td colspan="2">scriptor</td>

<td>IMAGE_HEADER</td><td>V</td><td></td><td>stru</td>

<td></td><td>ariable</td><td>ct</td><td></td>

<td>bAlphaPlane - FALSE</td><td></td><td></td><td></td>

<td>EMAGEPLAXEHEADER</td><td>V</td><td></td><td>stru</td>

<td></td><td>ariable</td><td>ct</td><td></td>

<td>if (ALPHACHANNELFLAG) {</td><td></td><td></td><td></td>

<td>bAlphaPlane = TRUE</td><td></td><td></td><td></td>

<td>IMAGE_PLANE_HEADER</td><td>V</td><td></td><td>Str</td>

<td></td><td>ariable</td><td>uct</td><td></td>

<td>} INDEX_TABLE</td><td>V</td><td></td><td>stru</td>

<td></td><td>ariable</td><td>ct</td><td></td>

<td>T1LE</td><td>V</td><td></td><td>stru</td>

<td></td><td>ariable</td><td>ct</td><td></td>

Image Header (IMAGE_HEADER)

<td>IMAGEJHEADER () {</td><td colspan="2">N</td><td>Des</td>

<td></td><td>one bits</td><td colspan="2">cryptor</td>

<td>GDTSíGNATURE</td><td> 6 4</td><td>sbf</td><td>uh</td>

<td>RESERVEDI</td><td> 4</td><td>sbf</td><td>uh</td>

<td>RESERVED2</td><td> 4</td><td>sbf</td><td>uh</td>

<td>TIIJNGFLAG</td><td> 1</td><td></td><td>boo</td>

<img file="BRPI0807465A2_D0007.tif" />

<td></td><td colspan="2"> 1</td><td colspan="2">uh</td>

<td>FREQUENCYMODEBITSTREAMFLAG</td><td></td><td></td><td>sbf</td><td></td>

<td>IMAGE ORIENTATION</td><td></td><td> 3</td><td>sbf</td><td>uh</td>

<td>1NDEXTABLEPRESENTFLAG</td><td></td><td> 1</td><td>sbf</td><td>uh</td>

<td>OVERLAP INFO</td><td></td><td> 2</td><td>sbf</td><td>uh</td>

<td>SHORT HEADER FLAG</td><td></td><td> 1</td><td rowspan="4"> 1 1 1</td><td>boo</td>

<td>LONGWORDFLAG</td><td></td><td> 1</td><td>boo</td>

<td>WINDOWINGFLAG</td><td></td><td> 1</td><td>boo</td>

<td>TRIMFLEXBITSFLAG</td><td></td><td> 1</td><td>boo</td>

<td></td><td></td><td></td><td> 1</td><td></td>

<td>RESERVED3</td><td></td><td> 3</td><td>sbf</td><td>uh</td>

<td>ALPHACHANNELFLAG</td><td></td><td> 1</td><td> 1</td><td>boo</td>

<td>SOURCE CLR FMT</td><td></td><td> 4</td><td>sbf</td><td>uh</td>

<td>SOURCEBITDEPTH</td><td></td><td> 4</td><td>sbf</td><td>uh</td>

<td>If (SHORT HEADER FLAG) {</td><td></td><td></td><td></td><td></td>

<td>WIDTHMINUSl</td><td> 6</td><td> 1</td><td>sbf</td><td>uh</td>

<td>HEIGHTMINUS 1</td><td></td><td> 1</td><td></td><td>uh</td>

<td></td><td> 6</td><td></td><td>sbf</td><td></td>

<td>} else {</td><td></td><td></td><td></td><td></td>

<td>WIDTH_MINUS1</td><td> 2</td><td> 3</td><td>sbf</td><td>uh</td>

HEIGHTMINUSl}

if (TILING FLAG) {NUM_VERT_T1LES_MINUS 1

NUM_HORIZ_TILES_MINUS 1}

for (n = 0; n &lt;

NUM_VERT_TILES_MINUSl; n ++) {

If (SHORTHE ADERFLAG)

WIDTH_IN_MB_OF_TILE_MINUS1 [n] else

WIDTH_1N_MB_OF TILE_MINUS 1 [n] 6}

for (n = 0; n &lt;

NUM_HORIZ_TILES_MINUS1; n ++) {

If (SHORTHEADERFLAG)

HEIGHTJNMBOFTILEMINUS1 [n] else

HEIGHT IN MB OF TILE MINUS1 [n] 6}

if (WINDOWING_FLAG) {NUM_TOP_EXTRAPIXELS

NUMLEFT EXTRAPIXELS

NUM_BOTTOM_EXTRAPIXELS sbf uim sbf sbf uim uim sbf sbf uim uim sbf sbf uim uim sbf sbf uim uim sbf

NUMRIGHTEXTRAPIXELS uim sbf

IMAGE_PLANE_HEADER () {

CLR_FMT

NO_SCALED_FLAG

BANDS_PRESENT if (CLRJFMT == YUV444) {CHROMA_C ENTE RING COLORJNTERPRETATION}

Else if (CLRFMT == NCHANNEL) {NUM_CHANNELS_MINUS1 COLORJNTERPRETATION}

if (SOURCE_CLR_FMT == BAYER) {BAYER_PATTERN CHROMA_CENTERING_BAYER COLORJNTERPRETATION}

if (SOURCE_BITDEPTH and {BD16, BD16S, BD32, BD32S}) {

SHIFTBITS}

if (SOURCE_BITEPTH == BD32F) {LEN_MANTISSA EXP_BIAS}

DC_FRAME_UNIFORM if (DC_FRAME_UNIFORM) {DC_QP ()

Num bi ts

1 variable

Descriptor uimsbf bool uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf uimsbf bool struct if (BANDSJPRESENT! = SB_DC_ONLY) {

USE_DC_QP if (USE_DC_QP == FALSE) {LP_FRAME_UNIFORM if (LP_FRAME_UNIFORM) {bool bool

NUM_LP_QPS = 1

LP_QP () variable struct}

} if (BANDS_PRESENT! = SB_NO_HIGHPASS) {

USE_LP_QP 1 bool if (USE_LP_QP == FALSE) {

HP_FRAME_UNIFORM 1 bool if (HP_FRAME_UNIFORM) {

NUM_HP_QPS = 1

HP_QP () variable struct}

} }

}

FLUSH_BYTE variable}

Some elements of the bitstream selected from the second bitstream syntax and semantics example are defined below:

Long Word Flag (LONG_WORD_FLAG) (1 bit)

LONG_WORD_FLAG is a 1-bit syntax element and specifies whether 5 16-bit integers can be used for transform computations. In a second example of bitstream syntax, if LONG_WORD_FLAG = = 0 (FALSE), 16-bit integers and arrays can be used for the external stage of transform computations (intermediate operations within the transform (such as (3 * a + l) »l) are developed with greater accuracy). If LONG_WORD_FLAG = = TRUE, 32-bit integers and arrays must be used for transform computations.

Note: 32-bit arithmetic can be used to decode an image considering the value of LONG_WORD_FLAG. This element of syntax can be used by the decoder to choose the most efficient word length for implementation.

No Scale Arithmetic Flag (NO_SCALED_FLAG) (1 bit)

NO_SCALED_FLAG is a 1-bit syntax element that specifies whether the transform uses scale. If NO_SCALED_FLAG == 1, the scale must not be performed. If NO_SCALED_FLAG == 0, scale must be used. In this case, the scale must be performed by rounding the final stage output (color conversion) by 3 bits.

Note: NO_SCALED_FLAG should be set to TRUE if encoding without loss is desired, even if lossless encoding is used only for a sub19 region of an image. Lossy encoding can use both modes.

Note: The rate distortion performance for lossy encoding is superior to lossy encoding when the scale is used (ie, NO_SCALED_FLAG == FALSE), especially at low QPs.

4. Signaling and Use of Long Word Flag

An exemplary image format for the representative encoder / decoder to support a wide range of pixel formats, including high dynamic range and wide musical scale formats. Supported data types include unsigned integer, fixed point float and floating point float. The supported bit depths include eight, 16, 24 and 32 bits per color channel. The exemplary image format allows for lossless compression of images using up to 24 bits per color channel, and lossy image compression using up to 32 bits per color channel.

At the same time, the exemplary image format was designed to provide high quality images and compression efficiency and allows for low complexity encoding and decoding implementations.

To support low complexity implementation, the transformed into an exemplary image format was designed to minimize expansion in the dynamic range. The two-stage transform increases the dynamic range by only five bits. Therefore, if the image bit depth is eight bits per color channel, 1 arithmetic bits may be sufficient to perform all transform operations on the decoder. For other bit depths, higher precision arithmetic may be required for transform operations.

The computational complexity of decoding a specific bit stream can be reduced if the accuracy required for transform operations is known in the decoder. This information can be signaled to a decoder using a syntax element (for example, 1-bit flag in an image header). Described signaling techniques and syntax elements can reduce computational complexity in decoding bit streams.

In an exemplary implementation, the LONG_WORD_FLAG 1-bit syntax element is used. For example, if LONG_WORD_FLAG = = FALSE, 16-bit integers and arrays can be used for the external stage of transform computations and if LONG_WORD_FLAG == TRUE, 32-bit integers and arrays should be used for transform computations.

In an encoder / decoder implementation, transform operations in place can be performed on 16-bit-wide words, but intermediate operations within the transform (such as computing product 3 * a for an “elevation” step given by b + = (3 * to + l) »l)) are performed with high accuracy (for example, 18 bits or more precision). However, in this example, the intermediate transform values ​​a and b by themselves can be stored in 16-bit integers.

32-bit arithmetic can be used to decode an image considering the values ​​of the LONG_WORD_FLAG element. The LONG_WORD_FLAG element can be used by the encoder / decoder to choose the most efficient word length. For example, an encoder may choose to set the LONG_WORD_FLAG element to FALSE if it can verify that the 16-bit and 32-bit precision steps produce the same output value.

5. Signaling and use of NO_SCALED_FLAG

An example of a representative encoder / decode image format supports a wide pixel range, including high dynamic range and wide range formats at the same time, the representative encoder / decoder design optimizes image quality and compression efficiency and allows for low complexity and decoding implementations.

As discussed above, the representative encoder / decoder uses two transforms based on a hierarchical block, where all transform steps are integer operations. The small rounding errors present in these integer operations result in loss of compression efficiency during lossy compression. To combat this problem, an implementation of the representative encoder / decoder defines two different precision modes for decoder operations. scale mode and non-scale mode.

In scale precision mode, the input image is pre-multiplied by 8 (that is, shifted to the left by 3 bits), in the encoder, and the final output in the decoder is divided by 8 with rounding (that is, shifted to the left in 3 bits). Operation in scale accuracy mode minimizes rounding errors, and results in rate distortion performance.

In non-scale precision mode, there is no such scale. An encoder or decoder operating in non-scale precision mode, does not have to deal with a small dynamic range for transform coefficients, and thus has low computational complexity. However, there is a small penalty on compression efficiency to operate in this mode. Lossless coding (without quantification, that is, setting the Quantification Parameter or QP to 1) can only use the scale precision mode to ensure reversibility.

The precision mode used by the encoder to create a compressed file is explicitly signaled in the image header of the compressed bit stream 220 (figure 2) using the NO_SCALED_FLAG. It is recommended that the decoder 300 uses the same precision mode for its operations.

NO_SCALED_FLAG is a syntactic element in the image header that specifies the precision mode as follows:

If NO_SCALED_FLAG == TRUE, the non-scale mode should be used for decoder operation.

If NO_SCALED_FLAG == FALSE, scale should be used. In this case, the scale mode should be used for operation by rounding down the final stage output (color conversion) to 3 bits. The rate distortion performance for lossy encoding is superior when non-scale mode is used (ie, NO_SCALED_FLAG == FALSE), especially at low QPs. However, the computation complexity is lower when the non-scale mode is used for two reasons:

The expansion of smaller dynamic range in non-scale mode means that shorter words can be used for transform computations, especially in conjunction with LONG_WORD_FLAG. In VLSI implementations, the reduced dynamic range expansion means that the port logic that implements the most significant bits can be de-energized.

Scaling mode requires addition and shift of bit to right by 3 bits (implement rounding divided by 8) on the decoder side. On the decoder side, it requires a bit shift to the left by 3 bits. This is slightly more essentially computational than the full scale mode.

Additionally, the non-scale mode allows for the compression of more significant bits than the scale mode. For example, the non-scale mode allows lossy compression (and decompression) of up to 27 significant bits per example, using 32 arithmetic bits. In contrast, the scale mode allows the same for some 24 bits. This is due to the three additional bits of dynamic range introduced by the scaling process.

The data values ​​in the decoder do not exceed 16 bits signaled for an 8-bit input for both precision modes, (however, intermediate operation within a transform stage can exceed this figure).

Note: NO_SCALED_FLAG is set to TRUE by the encoder, if lossy encoding (QP = I) is desired, even if lossy encoding is required for only a sub-region of an image.

The encoder can use any mode for lossy compression. It is recommended that the decoder use the precision mode signaled by NO_SCALED_MODE for its operations. However, the quantification levels are scaled such that a flow created with the scale precision mode and decoded using the non-scale precision mode (and vice versa) produces an acceptable image and many cases.

6. Scale Arithmetic for Increased Accuracy

In a representative encoder / decode implementation, transforms (including color conversion) are integer transformed and implemented through a series of elevation steps. In these elevation steps, zeroing errors damage transform performance. For lossy compression cases, to minimize damage from zeroing errors and thus maximize transform performance, input data for a transform must be shifted to the left by many bits. However, another desired feature is if the input image is 8 bits, then the transform output should be within 16 bits. So the number of bits shifted to the left cannot be large. The representative decoder implements a scale arithmetic technique to achieve both objectives. The scale arithmetic technique maximizes transform performance by minimizing damage from zeroing errors, and further limits the output of each transform step to be within 16 bits if the input image is 8 bits. This makes simple 16-bit implementation possible.

The transforms used in the representative encoder / decode are integer transformed and implemented by elevation steps. Most transform steps involve shifting to the right, which introduces zeroing errors. A transform usually involves many elevation steps, and accumulated zeroing errors visibly damage transform performance.

One way to reduce the damage from zeroing errors is to shift the input data to the left before the transform in the decoder, and to shift the same number of bits after the transform (combined with quantization) to the right in the decoder. As described above, the representative encoder / decode has a two-stage transform structure: optional first stage overlay + first stage CT + optional second stage overlay + second stage CT. Experiments have shown that shifting to the left in 3 bits is necessary to minimize truncation errors. So that in cases of loss, before color conversion, input data can be shifted to the left in 3 bits, that is, multiplied or scaled by an 8 fact (for example, for the scale mode described above).

However, color conversion and transforms do expend data. If input data is shifted in 3 bits, the output of the second stage DCT 4x4 has a dynamic range of 17 bits, if the input data is 8 bits (output of each other transformed is still within 16 bits) this is undesirable as it avoids 16-bit implementation, a highly desirable feature. To achieve this, before the second stage CT 4x4, input data is shifted to the right and so that the output is also within 16 bits. Since the second stage CT 4x4 applies to only 1/6 of the data (the DC transform coefficients of the first stage DCT), and the data is already scaled by the first transform, so that damage from errors zero here are minimal.

Then, in cases with loss for 8-bit images, on the encoder side, input is shifted to the left by 3 bits before color conversion, and shifted to the right by 1 bit before the second stage CT 4x4. On the decoder side, the input is shifted to the left by 1 bit before the first 4x4 IDCT stage, and shifted to the right by 3 bits after color conversion.

7. Computing Environment

The processing techniques described above for computational complexity and precision signaling in a digital media codec can be performed in any of a variety of digital media encoding and / or decoding systems, including, among other examples, computers (of various factors) form, including server, desktop, laptop, handheld devices, etc.); digital media recorders and players; image and video capture devices (such as cameras, scanners, etc.) communication equipment (such as telephones, mobile phones, conference equipment, etc.); display, printing or other presentation devices; and etc. computational complexity and precision signaling techniques in a digital media codec can be implemented in hardware circuit assemblies, in firmware that controls digital media processing hardware, as well as in communication software that runs inside a computer or other environment computer, as shown in figure 6.

Figure 6 illustrates a generalized example of a computing environment (600) in which described modalities can be implemented. The computing environment (600) is not intended to suggest any limitations as well as the scope of use or functionality of the invention, as the present invention can be implemented in general purpose or special purpose computing environments.

Referring to figure 6, the computing environment (600) includes at least one processing unit (610) and memory (620). In figure 6, this most basic configuration (630) is included within a dotted line. The processing unit (610) executes computer-readable instructions and can be a virtual processor. In a multiprocessing system, multiple processing units execute instructions executable by computer, to increase processing power. The memory (620) can be volatile memory (for example, registers, cache, RAM), non-volatile memory (for example, ROM, EEPROM, flash memory, etc.), or some combination of the two. The memory (620) stores software (680) that implements the encoding / decoding of digital media described with computational complexity and precision signaling techniques.

A computing environment can have additional characteristics. For example, the computing environment (600) includes storage (640), one or more input devices (650), one or more output devices (660), and one or one or more communication connections (670). An interconnect mechanism (not shown) such as a bus, controller, or network interconnects the components of the computing environment (600). Typically, the operating system software (not shown) provides an operating environment for other software running in the computing environment (600), and coordinates activities of the components of the computing environment. (600).

The storage (640) can be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, CD-RWs, DVDs, or any other medium that can be used to store information and that can be accessed within the computing environment (600). The storage (640) stores instructions for the software (680) implementing the encoding / decoding of digital media described with computational complexity and precision signaling techniques.

Input devices (650) can be a touch input device such as a keyboard, mouse, pen, or indicator, a voice input device, a scanning device, or other device that provides input to the communication environment ( 600). For audio, the input devices (650) can be a sound card or similar device that accepts audio input in analog or digital form from a microphone or microphone array, or CD-ROM player that provides audio samples for the computing environment. The computing devices (660) can be a display, printer, speakers, CD recorder, or other device that provides output from the computing environment (600).

Communication connections (670) capable of communicating over a communication medium to another computing entity. The communication medium carries information such as computer-readable instructions, copied audio or video information, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of the characteristics established or altered in such a way as to encode information in the signal. For example, and not a limitation, communication media includes wired or wireless techniques implemented with an electric, optical, RF, infrared, acoustic, or other carrier.

The encoding / decoding of digital media described with flexible quantification techniques in this document can be described in the general context of computer-readable media. Computer-readable media is any available media that can be accessed within a communication environment. For example, and not limitation, with the communication environment (600), the computer-readable media includes memory (620), storage (640), communication media, and combinations of any of the above

The encoding / decoding of digital media described with computational complexity and precision signaling techniques in this document can be described in the general context of instructions executable by computer, such as those included in program modules, being executed in a computing environment in a actual target or virtual processor. Program modules generally include routines, programs, libraries, objects, classes, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The functionality of the program modules can be combined or divided between program modules as desired in various modalities. Computer executable instructions for program modules can be executed within a local or distributed computing environment.

For presentation purposes, the detailed description uses terms such as "determines", 10 "generates", "adjusts", and "applies" to describe computer operations in a computing environment. These terms are high-level abstractions for operations performed by a computer, and should not be confused with actions performed by a human being. Actual computer operations corresponding to these terms vary depending on the implementation.

In view of the many possible modalities to which the principles of the invention can be applied, all such modalities are claimed as invention as may be within the scope and spirit of the following claims and equivalents thereof.