Source: http://www.google.com/patents/US8036274?dq=patent:+7360079
Timestamp: 2017-06-29 15:22:21
Document Index: 737788799

Matched Legal Cases: ['Application No. 2008105020', 'Application No. 565534', 'Application No. 565534', 'Application No. 2006280180', 'Application No. 2006280180', 'Application No. 200680029306', 'art 2', 'art 2', 'Application No. 2008', 'Application No. 200680029306', 'Application No. 200680029306', 'Application No. 2008105020']

Patent US8036274 - SIMD lapped transform-based digital media encoding/decoding - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA block transform-based digital media codec achieves faster performance by re-mapping components of the digital media data into vectors or parallel units on which many operations of the transforms can be performed on a parallel or single-instruction, multiple data (SIMD) basis. In the case of a one-dimensional...http://www.google.com/patents/US8036274?utm_source=gb-gplus-sharePatent US8036274 - SIMD lapped transform-based digital media encoding/decodingAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8036274 B2Publication typeGrantApplication numberUS 11/203,644Publication dateOct 11, 2011Filing dateAug 12, 2005Priority dateAug 12, 2005Fee statusPaidAlso published asCA2617888A1, CA2617888C, CN101243460A, CN101243460B, CN102065294A, CN102065294B, EP1913521A2, US20070036225, WO2007021615A2, WO2007021615A3Publication number11203644, 203644, US 8036274 B2, US 8036274B2, US-B2-8036274, US8036274 B2, US8036274B2InventorsSridhar Srinivasan, Chengjie Tu, Parker ShawOriginal AssigneeMicrosoft CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (101), Non-Patent Citations (92), Referenced by (4), Classifications (11), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetSIMD lapped transform-based digital media encoding/decoding
US 8036274 B2Abstract
A block transform-based digital media codec achieves faster performance by re-mapping components of the digital media data into vectors or parallel units on which many operations of the transforms can be performed on a parallel or single-instruction, multiple data (SIMD) basis. In the case of a one-dimensional lapped biorthogonal transform, the digital media data components are re-mapped into vectors on which butterfly stages of both overlap pre-/post-filter and block transform portions of the lapped transform can be performed on a SIMD basis. In the case of a two-dimensional lapped biorthogonal transform, the digital media data components are re-mapped into vectors on which a Hadamard operator of both overlap pre-/post-filter and block transform can be performed on a SIMD basis.
re-mapping components of blocks of input digital media data into a set of vectors on which operations of a lapped transform can be applied across the components of blocks on a single instruction, multiple data basis;
applying the lapped transform to blocks of the digital media data to produce a set of transform coefficients for the respective blocks, wherein applying the lapped transform comprises performing at least one operation on a single instruction, multiple data basis on the vectors of components for a block; and
encoding the transform coefficients in a compressed bitstream,
wherein the lapped transform is a lapped biorthogonal transform comprising an overlap filter and a block transform, the block transform being applied to blocks of the input digital media data and the overlap filter being applied to overlap areas overlapping adjoining blocks,
wherein said re-mapping groups components into vectors on which at least one operation of the overlap filter and at least one operation of the block transform can be applied across the components on a single instruction, multiple-data basis, and
wherein said applying the lapped transform comprises applying at least one operation of the overlap filter and at least one operation of the block transform on a single instruction, multiple data basis on the vectors.
2. The method of claim 1, wherein the at least one operation of the overlap filter and the at least one operation of the block transform each comprise a 2×2 Hadamard transform.
3. The method of claim 1, wherein the overlap filter and the block transform each comprise a rotation operation applied to the components on a sequential instruction basis.
4. The method of claim 1, wherein the vectors are 4-component vectors.
5. A method of encoding digital media data, the method comprising:
wherein the lapped transform is a one-dimensional lapped transform comprising an overlap filter and block transform, the block transform being applied to blocks of the input digital media data and the overlap filter being applied to overlap areas overlapping adjoining blocks,
6. A method of decoding digital media data encoded according to the method of claim 1, the decoding method further comprising:
decoding the transform coefficients from the compressed bitstream;
ordering the decoded transform coefficients in an arrangement of vectors on which operations of an inverse of the lapped transform can be applied across the transform coefficients on a single instruction, multiple data basis;
applying the inverse of the lapped transform to blocks of the decoded transform coefficients to reconstruct a representation of the digital media data in blocks, wherein applying the inverse of the lapped transform comprises performing at least one operation on a single instruction, multiple data basis on the vectors of transform coefficients; and
re-mapping components of the vectors to an initial arrangement of the digital media data.
7. The method of claim 5, wherein the at least one operation of the overlap filter and the at least one operation of the block transform each comprise a butterfly stage.
8. The method of claim 5, wherein the overlap filter and the block transform each comprise a rotation operation applied to the components on a sequential instruction basis.
9. The method of claim 5, wherein the vectors are 2-component vectors.
10. The method of claim 5, wherein the digital media data is two-dimensional data, the method further comprising:
performing said re-mapping and applying the lapped transform to rows of the two-dimensional media data; and
performing said re-mapping and applying the lapped transform to columns of the two-dimensional media data.
order elements of blocks of digital media data to/from a set of vectors on which at least some operations of a lapped transform can be applied across the components of blocks on a single instruction, multiple data basis;
apply the lapped transform to the blocks of the digital media data, wherein applying the lapped transform comprises performing the at least some operations on the single instruction, multiple data basis on the vectors for the blocks; and
encode/decode the digital media data to/from a compressed bitstream,
wherein the lapped transform is a lapped biorthogonal transform having a block transform applied to adjacent blocks of the digital media data and an overlap filter applied on overlap areas straddling the adjacent blocks, and wherein said processor orders the elements of the blocks into vectors on which at least some operations of both the overlap filter and the lapped transform can be applied on the single instruction, multiple data basis.
12. The digital media encoder and/or decoder of claim 11 wherein the lapped biorthogonal transform is one-dimensional, and wherein the overlap filter and the block transform each comprise butterfly stages whose operations are applied to the vectors on the single instruction, multiple data basis.
13. The digital media encoder and/or decoder of claim 11 wherein the lapped biorthogonal transform is two-dimensional, and wherein the overlap filter and the block transform each comprise 2×2 Hadamard transforms whose operations are applied to the vectors on the single instruction, multiple data basis.
14. The digital media encoder and/or decoder of claim 11 wherein the processor is further programmed to perform said ordering of elements during a stage of color conversion of the digital media data between color formats.
15. At least one computer-readable storage device storing a computer-executable digital media processing program which when executed by a computer causes the computer to perform a method of processing digital media data, the method comprising:
re-mapping components of blocks of digital media data into a set of vectors on which operations of a lapped transform can be applied across the components of blocks on a single instruction, multiple data basis;
applying the lapped transform to blocks of the digital media data to produce a set of transform coefficients for the respective blocks, wherein applying the lapped transform comprises performing at least some operations on a single instruction, multiple data basis on the vectors of components for a block; and
encoding/decoding the digital media data to/from a compressed bitstream,
wherein the lapped transform is a lapped biorthogonal transform comprising an overlap filter and a block transform, and wherein said applying the lapped transform comprises performing at least some operations of both the overlap filter and block transform on a single instruction, multiple data basis on the vectors.
16. The at least one computer-readable storage device of claim 15 wherein said applying the lapped transform comprises performing at least some rotation operations of both the overlap filter and block transform on a sequential basis.
17. A method of decoding digital media, the method comprising:
decoding transform coefficients from a compressed bitstream;
ordering the decoded transform coefficients into an arrangement of vectors on which operations of an inverse of a lapped transform can be applied across the transform coefficients on a single instruction, multiple data basis;
applying the inverse of the lapped transform to blocks of the decoded transform coefficients to reconstruct a representation of the digital media data, wherein applying the inverse of the lapped transform comprises performing at least one operation on a single instruction, multiple data basis on the vectors of the transform coefficients; and
re-mapping components of the vectors to an initial arrangement of the digital media data,
wherein the inverse of the lapped transform is an inverse of a lapped biorthogonal transform comprising an inverse overlap filter and an inverse block transform, the inverse block transform being applied to blocks of the digital media data and the inverse overlap filter being applied to overlap areas overlapping adjoining blocks, and
wherein said applying the inverse of the lapped transform comprises applying at least one operation of the inverse overlap filter and at least one operation of the inverse block transform on a single instruction, multiple data basis on the vectors.
18. The method of claim 17, wherein the at least one operation of the inverse overlap filter and the at least one operation of the inverse block transform each comprise a 2×2 Hadamard transform.
19. The method of claim 17, wherein the inverse overlap filter and the inverse block transform each comprise a rotation operation applied to the components on a sequential instruction basis.
20. The method of claim 17, wherein the vectors are 4-component vectors.
21. A method of decoding digital media, the method comprising:
wherein the inverse of the lapped transform is an inverse of a one-dimensional lapped transform comprising an inverse overlap filter and inverse block transform, the inverse block transform being applied to blocks of the input digital media data and the inverse overlap filter being applied to overlap areas overlapping adjoining blocks, and
22. The method of claim 21, wherein the at least one operation of the inverse overlap filter and the at least one operation of the inverse block transform each comprise a butterfly stage.
23. The method of claim 21, wherein the inverse overlap filter and the inverse block transform each comprise a rotation operation applied to the components on a sequential instruction basis.
24. The method of claim 21, wherein the vectors are 2-component vectors. Description
More specifically, a typical block transform-based codec 100 shown in FIG. 1 divides the uncompressed digital image's pixels into fixed-size two dimensional blocks (X1, . . . Xn), each block possibly overlapping with other blocks. A linear transform 120-121 that does spatial-frequency analysis is applied to each block, which converts the spaced samples within the block to a set of frequency (or transform) coefficients generally representing the strength of the digital signal in corresponding frequency bands over the block interval. For compression, the transform coefficients may be selectively quantized 130 (i.e., reduced in resolution, such as by dropping least significant bits of the coefficient values or otherwise mapping values in a higher resolution number set to a lower resolution), and also entropy or variable-length coded 130 into a compressed data stream. At decoding, the transform coefficients will inversely transform 170-171 to nearly reconstruct the original color/spatial sampled image/video signal (reconstructed blocks {circumflex over (X)}1, . . . {circumflex over (X)}n) The block transform 120-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=M x, M being the transform matrix. When the input data is arbitrarily long, it is segmented into N sized vectors and a block transform is applied to each segment. For the purpose of data compression, reversible block transforms are chosen. In other words, the matrix M is invertible. In multiple dimensions (e.g., for image and video), block transforms are typically implemented as separable operations. The matrix multiplication is applied separably along each dimension of the data (i.e., both rows and columns).
In the above described block transform-based coding systems, a block transform is a finite length (typically a short length such as 4 or 8) transform that is applied in succession to non-overlapping adjacent blocks of the input signal or image. Thus, signal components straddling block boundaries do not influence the transform of the block across the boundary. Due to quantization of the high frequency components for compression of data, use of block transforms can introduce perceptible artifacts at block boundaries, or blockiness. Blockiness is apparent in highly compressed JPEG images and shows up as square blocks or staircase shapes in the image. In audio, blockiness leads to periodic popping noise. Neither of these is a tolerable artifact.
The lapped transform (LT 210 illustrated in FIG. 2) is an alternative means of representing a signal or image that does not suffer from sharp blockiness. In a lapped transform, the input signal components influencing each transform coefficient set are larger than the size of the transform output block. For instance in a 1D case, 8 successive signal components may influence the 4 point transform. Likewise for images, an 8×8 area may influence a 4×4 transform block.
Lapped transforms may be formulated in one of two ways. One classical formulation of a lapped transform is a series of block transforms followed by a series of frequency mixers. The block transforms are aligned to the regular grid of N points (N being the transform size), whereas the frequency mixers are spaced symmetrically across the block boundaries. An alternative formulation has a pre filtering operation performed across block edges followed by a block transform.
Inverses of lapped transforms (e.g., ILT 220 of FIG. 2) generally are straightforward to compute and implement. The signal flow graph is reversed, with each elementary operation being inverted. One classical formulation of an inverse lapped transform is a series of frequency mixers followed by a series of block transforms. An alternative formulation comprises a series of block transforms followed by post-filtering operations applied across block boundaries.
In either formulation of lapped transforms, the key components are (i) block transforms and (ii) operators straddling blocks, which may be frequency mixers, pre- or post-filters. These operators (ii) are referred to collectively as overlap filters.
Lapped orthogonal transforms (LOTs) are a subclass of lapped transforms. These have the property that the forward and inverse transforms are transposes. From the compression standpoint, the subclass lapped biorthogonal transforms are more interesting since they can achieve better PSNR than LOTs. Biorthogonality refers to the analysis and synthesis basis functions being biorthogonal (i.e. mutually orthogonal).
A digital media coding and decoding technique and realization of the technique in a digital media codec described herein achieves speed-up of the transform used for encoding and decoding. This technique reformulates a lapped (or other) transform as a set of operations that are largely single instruction, multiple data (SIMD) friendly. This is achieved by remapping the input and output sampling grids of the lapped transform. By this remapping, the input data can be grouped into “vectors” or parallel units. With this rearrangement, many of the lapped transform steps can be executed as vector operations. The few remaining operations that are not vectorizable are performed on the vector components in a sequential manner.
FIG. 2 is a flow diagram illustrating an example of a lapped transform.
FIG. 3 is a flow diagram of a representative encoder incorporating the adaptive coding of wide range coefficients.
FIG. 4 is a flow diagram of a decoder incorporating the decoding of adaptively coded wide range coefficients.
FIG. 5 is a flow diagram illustrating an example lapped transform formulation as a pre-filter (or overlap operator) and block transform, where the pre-filter is applied across input boundaries or block edges of the block transform.
FIG. 6 is a signal flow graph of a representative lapped transform having the pre-filter and block transform formulation of FIG. 5.
FIG. 7 is a signal flow graph of a parallelized SIMD version of a representative lapped biorthogonal transform having the pre-filter and block transform formulation of FIG. 6.
FIG. 8 is a diagram illustrating grouping of one-dimensional data into 2-component vectors used in the parallelized SIMD version of the one-dimensional lapped biorthogonal transform of FIG. 7.
FIG. 9 is a vector signal flow graph of the one-dimensional lapped biorthogonal transform of FIG. 7.
FIG. 10 is a diagram illustrating grouping of two-dimensional data into 4-component vectors used in the parallelized SIMD version of the two-dimensional lapped biorthogonal transform.
FIG. 11 is a diagram illustrating a vector notation for the two-dimensional data as per the grouping into vectors as shown in FIG. 10 FIG. 12 is a diagram illustrating pixel components in the two-dimensional data and corresponding parallelized component vectors over which an overlap operator (pre-filter) portion of the two-dimensional lapped biorthogonal transform is applied, and to which a 2×2 Hadamard operator portion of the overlap operator is applied.
FIG. 13 is a diagram illustrating pixel components in the two-dimensional data and corresponding parallelized component vectors over which a block transform portion of the two-dimensional lapped biorthogonal transform is applied, and to which a 2×2 Hadamard operator portion of that block transform is applied.
FIG. 14 is a diagram illustrating an overlap operator of the two-dimensional lapped biorthogonal transform.
FIG. 15 is a flow diagram illustrating a process implementing the overlap operator of the parallelized two-dimensional lapped biorthogonal transform.
FIG. 16 is a flow diagram illustrating a process implementing the block transform of the parallelized two-dimensional lapped biorthogonal transform.
FIG. 17 is a block diagram of a suitable computing environment for implementing the parallelized SIMD version of the representative encoder/decoder of FIGS. 3 and 4.
The following description relates to coding and decoding techniques that provide a faster implementation of lapped transform as parallelized or SIMD operations [hereafter “transform parallelization technique”]. The following description describes an example implementation of the technique in the context of a digital media compression system or codec. The digital media system codes digital media data in a compressed form for transmission or storage, and decodes the data for playback or other processing. For purposes of illustration, this exemplary compression system incorporating this transform parallelization technique is an image or video compression system. Alternatively, the technique also can be incorporated into compression systems or codecs for other 2D data. The transform parallelization technique does not require that the digital media compression system encodes the compressed digital media data in a particular coding format.
FIGS. 3 and 4 are a generalized diagram of the processes employed in a representative 2-dimensional (2D) data encoder 300 and decoder 400. The diagrams present a generalized or simplified illustration of a compression system incorporating the 2D data encoder and decoder that implement the transform parallelization technique. In alternative compression systems using the transform parallelization technique, additional or fewer processes than those illustrated in this representative encoder and decoder can be used for the 2D data compression. 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 lossless and/or lossy compression of the 2D data, depending on the quantization which may be based on a quantization parameter varying from lossless to lossy.
The 2D data encoder 300 produces a compressed bitstream 320 that is a more compact representation (for typical input) of 2D data 310 presented as input to the encoder. For example, the 2D data input can be an image, a frame of a video sequence, or other data having two dimensions. The 2D data encoder tiles 330 the input data into macroblocks, which are 16×16 pixels in size in this representative encoder. The 2D data encoder further tiles each macroblock into 4×4 blocks. A “forward overlap” operator 340 is applied to each edge between blocks, after which each 4×4 block is transformed using a block transform 350. This block transform 350 can be the reversible, scale-free 2D transform described by Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004, the disclosure of which is hereby incorporated herein by reference. The overlap operator 340 can be the reversible overlap operator described by Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004, the disclosure of which is hereby incorporated herein by reference; and by Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005, the disclosure of which is hereby incorporated herein by reference. The overlap operator and transform together effect a lapped biorthogonal transform. Alternatively, the discrete cosine transform or other block transforms and overlap operators can be used. Subsequent to the transform, the DC coefficient 360 of each 4×4 transform block is subject to a similar processing chain (tiling, forward overlap, followed by 4×4 block transform). The resulting DC transform coefficients and the AC transform coefficients are quantized 370, entropy coded 380 and packetized 390.
The decoder performs the reverse process. On the decoder side, the transform coefficient bits are extracted 410 from their respective packets, from which the coefficients are themselves decoded 420 and dequantized 430. The DC coefficients 440 are regenerated by applying an inverse transform, and the plane of DC coefficients is “inverse overlapped” using a suitable smoothing operator applied across the DC block edges. Subsequently, the entire data is regenerated by applying the 4×4 inverse transform 450 to the DC coefficients, and the AC coefficients 442 decoded from the bitstream. Finally, the block edges in the resulting image planes are inverse overlap filtered 460. This produces a reconstructed 2D data output.
In an exemplary implementation, the encoder 300 (FIG. 3) compresses an input image into the compressed bitstream 320 (e.g., a file), and the decoder 400 (FIG. 4) reconstructs the original input or an approximation thereof, based on whether lossless or lossy coding is employed. The process of encoding involves the application of a forward lapped transform (LT) discussed below, which is implemented with reversible 2-dimensional pre-/post-filtering also described more fully below. The decoding process involves the application of the inverse lapped transform (ILT) using the reversible 2-dimensional pre-/post-filtering.
The input data 310 compressed by the illustrated encoder 300/decoder 400 can be images of various color formats (e.g., RGB/YUV4:4:4, YUV4:2:2 or YUV4:2:0 color image formats). Typically, the input image always has a luminance (Y) component. If it is a 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 of the image can have different spatial resolutions. In case of an input image in the YUV 4:2:0 color format for example, the U and V components have half of the width and height of the Y component.
As discussed above, the encoder 300 tiles the input image or picture into macroblocks. In an exemplary implementation, the encoder 300 tiles the input image into 16×16 macroblocks in the Y channel (which may be 16×16, 16×8 or 8×8 areas in the U and V channels depending on the color format). Each macroblock color plane is tiled into 4×4 regions or blocks. Therefore, a macroblock is composed for the various color formats in the following manner for this exemplary encoder implementation:
1. For a grayscale image, each macroblock contains 16 4×4 luminance (Y) blocks. 2. For a YUV4:2:0 format color image, each macroblock contains 16 4×4 Y blocks, and 4 each 4×4 chrominance (U and V) blocks. 3. For a YUV4:2:2 format color image, each macroblock contains 16 4×4 Y blocks, and 8 each 4×4 chrominance (U and V) blocks. 4. For a RGB or YUV4:4:4 color image, each macroblock contains 16 blocks each of Y, U and V channels. 2. Fast SIMD Lapped Biorthogonal Transform Overview
One of the more computationally complex operations in the above-described representative encoder 300 (FIG. 3) and decoder 400 (FIG. 4) is the lapped biorthogonal transform. The complexity of this operation impacts the performance of both the encoder and the decoder.
The implementation of the lapped biorthogonal transform that is described in the patent applications (Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004; Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005) is designed to minimize complexity. However, the transform parallelization techniques described herein achieve a further speed-up by formulating the lapped transform operations in a SIMD (single instruction, multiple data) or parallel-instruction friendly manner. The SIMD operations can be used to compute multiple instructions in parallel. Such SIMD instructions are supported on a variety of processors, including the Pentium® family processors from Intel, various x86-compatible processors from AMD, PowerPC® and a variety of other DSPs (digital signal processors).
The transform parallelization technique described herein reformulates a lapped (or other) transform as a set of operations that are largely SIMD friendly. This is achieved by remapping the input and output sampling grids of the lapped transform. By this remapping, the input data can be grouped into “vectors” or parallel units. With this rearrangement, many of the lapped transform steps can be executed as vector operations. The few remaining operations that are not vectorizable are performed on the vector components in a sequential manner.
Although the technique can be applied to lapped transforms in general, a specific application of the technique to the lapped biorthogonal transform of the representative encoder and decoder (i.e., the lapped biorthogonal transform detailed in the above-listed patent applications) is discussed herein below for purposes of illustration. The transform parallelization technique remaps and groups the input sampling grid or lattice of the representative lapped biorthogonal transform such that each group of data samples can be treated as a vector for many of the operations implementing the lapped transform. In this particular lapped biorthogonal transform example, the techniques are applied to formulate SIMD-friendly versions of 4-point overlap operators and 4-point block transforms, but the techniques can be generalized to other transform lengths as well. Further, the technique alternatively can be applied to create SIMD or parallel instruction versions of other lapped transform realizations.
The following sections detail both one- and two-dimensional SIMD-friendly implementations of the representative lapped biorthogonal transform. In the one dimensional case, two elements may be grouped together into a vector, and many of the 1D lapped transform operations may be performed using vector operations. In the two dimensional case, two or four elements may be grouped together into a vector, and many of the lapped transform operations may be performed using vector operations.
These vectorization techniques are equally applicable to the forward and inverse transforms (used by the encoder and decoder, respectively).
2.1 SIMD Realization of One-Dimensional Lapped Biorthogonal Transform
With reference to FIG. 5, consider a general case of a lapped transform 500 formulated as a pre-filter (overlap operator) 510 and block transform 520. In the illustrated example case, the block transform 520 has a block size of 4, and the pre-filter 510 has an overlap size of 4 as well. The overlap size is defined as the pre/post filter length. Thus, if the data sequence is numbered x0, x1, x2, x3, etc., the lapped transform 500 proceeds as follows:
1. The pre-filter 510 is applied to each set of input data [x4i+2, x4i+3, x4i+4, x4i+5]; and 2. The block transform 520 is applied to each set [x4i, x4i+1, x4i+2, x4i+3].
In alternative implementations, the lapped transform can be defined with other, different block transform size and overlap size.
FIG. 6 illustrates a more specific example of a lapped biorthogonal transform 600 that has the pre-filter and block transform formulation as illustrated in FIG. 5. The lapped biorthogonal transform 600 is that described above as being used in the representative encoder 300 (FIG. 3) and decoder 400 (FIG. 4), whose implementation is detailed more specifically in the patent applications: Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004; Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005. For simplicity, the pre-filter and block transform of the encoder 300 are depicted in FIG. 6. The post-filter and inverse block transform of the inverse lapped transform for the decoder is an inverse of the forward lapped transform 600. As shown in FIG. 6, the pre-filter has an implementation as a set of butterfly or lifting step operations organized as a first butterfly stage 610, rotation/scaling 620, and second butterfly stage 630. The block transform has an implementation as a third butterfly stage 640 and a rotation 650.
One way to parallelize operations for realization using SIMD instructions is by simply grouping together like-indexed signal components across blocks. In other words, the components of the form x4i+j for some j are grouped together. For the specific lapped biorthogonal transform 600 example considered here, vectors of 2 components can be: [x14 x18], [x15 x19], [x16 x20], and [x17 x21].
This grouping works well for the pre-filter. However for the block transform, the vectors [x14 x18] and [x16 x20] straddle three, and not two blocks. This means that this grouping cannot be used to achieve overall speed up the lapped transform. At the transform stage, the desired grouping is different: [x16 x20], [x17 x21], [x18 x22], and [x19 x23].
Comparing the desired groupings for the pre-filter and block transform, it can be seen that two of the vectors are common to both groupings (i.e., [x16 x20] and [x17 x21]). However, the remaining two vectors are different between the groupings, which would necessitate regrouping of vectors between the pre-filter and block transform. This is not a desirable solution.
On the other hand, the transform parallelization technique presents an alternative way to parallelize the 1D lapped transform. With the alternative technique, a permutation is added between certain components before or after the lapped transform, such that the groupings of components into SIMD instruction vectors are common to both the pre-filter and block transform stages.
FIG. 7 shows a modified realization 700 of the lapped biorthogonal transform of FIG. 6, which has been parallelized according to the transform parallelization technique described herein. This modified lapped transform realization 700 is functionally identical to the lapped biorthogonal transform implementation 600 of FIG. 6, but includes a twist or permutation 710 of components in the first stage, followed by a slightly different network of butterflies 720, 740 and 750. These butterfly stages can be implemented in parallel with 2 component vectors, since for these stages odd components interact only with odd components and even components interact only with even components. Further, the operations for odd components and even components are identical in these stages. Thus, grouping of adjacent odd and even components realizes a parallel implementation.
Nevertheless, some of the stages of the SIMD realization 700 of the lapped biorthogonal transform still are not parallelizable. The rotation/scaling step 730 in the pre-filter, and the rotation step 760 in the block transform are implemented sequentially.
FIG. 9 depicts a realization 900 of the lapped biorthogonal transform 700 (FIG. 7) using the arrangement of the data into 2-component vectors as shown in FIG. 8. In FIG. 9, the data paths are 2-component vector valued, and the bold arrows are in-vector operations (i.e., operations between components of the same vector). The vector grouping shown in FIG. 8 is used for the input, which is based on the following component-to-vector mapping rule:
v 2i =[x 4i x 4i+1]
v 2i+1 =[x 4i+3 X 4i+2]
This mapping groups the original signal into 2-component vectors, to which SIMD arithmetic is applied for many of the lapped transform steps, and sequential processing is applied for the remaining steps.
2.2 SIMD Realization of Two-Dimensional Lapped Biorthogonal Transform
The 2-dimensional lapped biorthogonal transform (2D LBT) can be implemented using the 1-dimensional lapped biorthogonal transform (1D LBT) just described. In such implementation, the 1D LBT is applied to each row of the image followed by a 1D LBT applied to each column (or vice versa). In this case, two types of vectorization techniques may be used:
1. In the first type of vectorization, the same grouping used in the 1D LBT (as described in section 2.1 above) may be used for both the horizontal and vertical transforms. 2. In the second type of vectorization, the vectors may be formed by grouping together like-indexed components of multiple rows while implementing the 1D LBT along rows, and by grouping together like-indexed components of multiple columns while implementing the 1D LBT along columns. In both these techniques, the vectorization changes between the row and column transforms. This incurs an additional cost of remapping from one vectorization format to another during the computation of the transform, which may be expensive. An alternative vectorization technique that does not involve reshuffling between transform stages is described below.
Further, the 2D LBT described in the above listed patent applications (i.e., Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005) implements the LBT directly in 2 dimensions. This transform cannot be separated into two 1D operations.
For a parallelized SIMD version of this direct 2D LBT implementation (and also for the separable 2D implementation), a bidirectionally twisted remapping 1000-1001 is first applied as shown in FIG. 10. Each 4×4 block of pixels within an area 1010 is mapped 1000-1001 into four 4-component vectors within area 1020, such that each vector contains pixels from the 2×2 sub-blocks of the 4×4 block. The ordering of components within vectors follows a two dimensional extension of the 1D remapping (the permutation 710 shown in FIG. 7) described above. FIG. 11 shows a vector notation 1100 for the resulting set of 4-component vectors in area 1020.
The 4-component vectors thus formed have the property that groups of 4 pixels to which Hadamard transforms are applied either in the overlap operator stage or in the block transform stage of the direct 2D LBT are aligned in the same position within the vectors. This is illustrated in FIG. 12 for the overlap operator and in FIG. 13 for the Photon Core Transform, and is explained in detail below.
2.2.1 Parallel Implementation of the Overlap Operator in the SIMD Realization of Two-Dimensional Lapped Biorthogonal Transform
With reference again to FIG. 5, the overlap operator (pre-filter 510) in a lapped transform is applied across block boundaries. This may be done either before or after the block transform 520.
In the case of the 2D LBT implementation described in the above-listed patent applications (i.e., Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005), the overlap operator is applied prior to the block transform on the encoder side. Likewise, it is applied after the inverse block transform on the decoder side. Disregarding the special cases at boundaries of the image, the overlap operator is applied to a 4×4 area straddling 4 4×4 blocks.
With reference to FIG. 14, the overlap operator 1400 of this 2D LBT implementation consists of two 2×2 Hadamard transforms 1410 applied to quads of pixels located symmetrically in the grid, followed by a rotation & scaling stage 1420, and 1430, followed by another 2×2 Hadamard transform 1440 applied to the same pixel quads. Details of the operations are presented by Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005. A further simplification can be used in the 2D LBT formulation as described in this patent application, where the scaling stage and one of the 2×2 Hadamard stages cancel out some operations.
For the parallelized SIMD version of this overlap operator, the same vectorization procedure described in section 2.2 above and shown in FIGS. 10 and 11 is first applied. With reference to FIG. 15, the parallelized SIMD version of the overlap operator based on this vectorized data is implemented according to the following process 1500:
1. As indicated at action 1510, the image or other 2 dimensional data working area is vectorized into 4-component vectors as shown in FIGS. 10 and 11. 2. The overlap operation in actions 1520-1570 is performed on each 4×4 overlap area straddling 4 4×4 blocks 1200 over the image, as illustrated in FIG. 12. For this operation, the vectors identified as [v3 v6 v9 v12] using the vector notation shown in FIG. 11 are used. These steps are repeated for all such areas. 3. First, the 2×2 Hadamard operation is performed among these 4 vectors at action 1530. 4. For the next action 1540, the scaling operation (which is detailed in the patent applications: Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005) is performed between the vectors v3 and v12. 5. Rotations 1550 are performed within components of the vectors, v6, v9 and v12. These are mostly sequential operations that largely do not exploit parallelism of data. 6. Finally, the 2×2 Hadamard operation is again performed at action 1560 among the four vectors [v3 v6 v9 v12] of the overlap area. In the process 1500, the above operations are performed in-place on the indicated vectors. Further, in practice, there are some cancellations between the steps 3 and 4 above which lead to further simplifications, as detailed in the patent applications: Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005.
2.2.2 Parallel Implementation of the Block Transform in the SIMD Realization of Two-Dimensional Lapped Biorthogonal Transform
After the overlap operator is applied to all 2×2 subblocks within a block, the 4×4 block 1300 (FIG. 13) is ready to be block transformed. The block transform operation keeps the same vectorization—hence it is not necessary to shuffle data between the overlap and block transform operations.
With reference to FIG. 16, the parallel implementation of the block transform is performed according to the following process 1600. The process begins with the image or working area still vectorized by the action 1510 (FIG. 15) for the overlap operator as shown in FIGS. 10 and 11. On the other hand, in instances where the block transform is being applied to the 2D data alone without the overlap operator process 1500 being first applied, the process 1600 instead begins by performing the action 1510 to provide the same vectorization.
1. In the loop of actions 1610-1640, the transform is applied to each 4×4 block 1300 of the image. For example, the vectors [v0 v1 v2 v3] shown in FIG. 13 are used for the top left block. These steps are repeated for all blocks. 2. At a first action 1620, the 2×2 Hadamard operation is performed among these 4 vectors. 3. At next action 1630, rotations are performed within components of the vectors, v0, v1, v2 and v3. These are mostly sequential operations that largely do not exploit parallelism of data. The rotations performed are as detailed in the patent applications: Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004; and Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005. In alternative implementations of the SIMD lapped transform, the transform operations applied to the vectors of the block can be those of other DCT-like transforms (instead of the reversible transform described in the above-listed patent applications).
For both the overlap operator 1500 and transform 1600 processes, a four way 2×2 Hadamard transform is a fundamental and repeated operation. With the data components ordered by the vectorization illustrated in FIGS. 10 and 11, the 2×2 Hadamard is easily performed as SIMD instructions operating on these vectors. Further, for the overlap operator, the scaling operation likewise can be performed as SIMD instructions that operate on these vectors. The rotations (actions 1550, 1630) are partially parallelizable. This is so because some of the rotations involved are identical 1D operations that are performed for two pairs of data points within the 4 component vector. These rotations can also be parallelized with multiply and shift operations.
Due to reordering of data components in the vectors, the final output of the transform is also re-ordered. This is typically not an issue because the transform is scanned to order the coefficients as a list for output by the encoder in the compressed bitstream. In the parallel implementation, the scan array takes into account re-ordering and has no negative impact on the algorithm complexity.
The same parallelization technique holds for the inverse lapped biorthogonal transform, except the order of block transform and overlap operator is reversed, and the order of actions 1530-1560 and 1620-1630 in the respective process is reversed. The reordered scan pattern is used to populate the input data array, and the output is afterwards remapped in a manner inverse to the mapping shown in FIG. 10.
The parallelization technique also holds for alternative implementations using other versions of lapped orthogonal/biorthogonal transforms. As noted in the discussion of the block transform process 1600, the parallelization may be used for block transforms by themselves (i.e. without the overlap operator) as well. Transform and overlap sizes other than 4, and dimensions greater than 2 may also be accommodated with straightforward extension of the parallelization logic.
The cost of vectorization is minimized by performing the remapping to the twisted lattice on the encoder, and remapping from the twisted lattice on the decoder, during the stage of color conversion. Color conversion in the decoder is generally implemented sequentially due to several reasons including (i) multitude of color formats, (ii) lack of word alignment due to 24 bit pixel boundaries of many color formats, (iii) need to perform clipping on decoder side, and etc. The additional cost of remapping over and above color conversion is minimal and facilitates use of this parallelization technique for overall performance improvement. Further, when the input image is presented in a rotated and/or laterally inverted orientation or when the output image is desired in a rotated and/or laterally inverted orientation, this can be achieved with almost no increase in the overall computational complexity.
The above described representative encoder 300 (FIG. 3) and decoder 400 (FIG. 4) incorporating the Lapped Biorthogonal Transform implemented using the transform parallelization techniques can be performed on any of a variety of devices in which digital media signal processing is performed, including among other examples, computers; image and video recording, transmission and receiving equipment; portable video players; video conferencing; and etc. The digital media coding techniques can be implemented in hardware circuitry, as well as in digital media processing software executing within a computer or other computing environment, such as shown in FIG. 17.
With reference to FIG. 17, the computing environment (1700) includes at least one processing unit (1710) and memory (1720). In FIG. 17, this most basic configuration (1730) is included within a dashed line. The processing unit (1710) executes computer-executable instructions and may be a real or a virtual processor. In a multi-processing system, multiple processing units execute computer-executable instructions to increase processing power. The memory (1720) may be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two. The memory (1720) stores software (1780) implementing the described digital media encoding/decoding and transform parallelization techniques.
The storage (1740) may be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, CD-RWs, DVDs, or any other medium which can be used to store information and which can be accessed within the computing environment (1700). The storage (1740) stores instructions for the software (1780) implementing the described encoder/decoder using the transform parallelization techniques.
The input device(s) (1750) may be a touch input device such as a keyboard, mouse, pen, or trackball, a voice input device, a scanning device, or another device that provides input to the computing environment (1700). For audio, the input device(s) (1750) may be a sound card or similar device that accepts audio input in analog or digital form, or a CD-ROM reader that provides audio samples to the computing environment. The output device(s) (1760) may be a display, printer, speaker, CD-writer, or another device that provides output from the computing environment (1700).
The digital media processing techniques herein can be described in the general context of computer-readable media. Computer-readable media are any available media that can be accessed within a computing environment. By way of example, and not limitation, with the computing environment (1700), computer-readable media include memory (1720), storage (1740), communication media, and combinations of any of the above.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4754492Jun 3, 1985Jun 28, 1988Picturetel CorporationMethod and system for adapting a digitized signal processing system for block processing with minimal blocking artifactsUS5297236Jun 5, 1991Mar 22, 1994Dolby Laboratories Licensing CorporationLow computational-complexity digital filter bank for encoder, decoder, and encoder/decoderUS5311310Dec 1, 1992May 10, 1994Bell Communications Research, Inc.High efficiency coder and method employing overlapped motion compensation and perfect reconstruction filter banksUS5384849May 18, 1993Jan 24, 1995Samsung Electronics Co., Ltd.Apparatus and method for encoding/decoding data including the suppression of blocking artifactsUS5805739Apr 2, 1996Sep 8, 1998Picturetel CorporationLapped orthogonal vector quantizationUS5822000Dec 20, 1996Oct 13, 1998Daewoo Electronics, Co., Ltd.Video encoding using rearrangement of transform coefficients and inter-block correlationUS5850294Dec 18, 1995Dec 15, 1998Lucent Technologies Inc.Method and apparatus for post-processing imagesUS5859788Aug 15, 1997Jan 12, 1999The Aerospace CorporationModulated lapped transform methodUS5933522Aug 20, 1997Aug 3, 1999Nec CorporationSpecific part searching method and device for memory LSIUS5933541Aug 16, 1996Aug 3, 1999Siemens AktiengesellschaftMethod for processing decoded picture blocks in a block-based method of picture codingUS5970173Jun 4, 1996Oct 19, 1999Microsoft CorporationImage compression and affine transformation for image motion compensationUS5973755Apr 4, 1997Oct 26, 1999Microsoft CorporationVideo encoder and decoder using bilinear motion compensation and lapped orthogonal transformsUS5982459Jun 11, 1997Nov 9, 19998×8, Inc.Integrated multimedia communications processor and codecUS6011625Jul 8, 1998Jan 4, 2000Lockheed Martin CorporationMethod for phase unwrapping in imaging systemsUS6029126Jun 30, 1998Feb 22, 2000Microsoft CorporationScalable audio coder and decoderUS6064776Oct 24, 1996May 16, 2000Kabushiki Kaisha ToshibaImage processing apparatusUS6073153Jun 3, 1998Jun 6, 2000Microsoft CorporationFast system and method for computing modulated lapped transformsUS6101279Jun 5, 1998Aug 8, 2000Wisconsin Alumni Research FoundationImage compression system using block transforms and tree-type coefficient truncationUS6115689May 27, 1998Sep 5, 2000Microsoft CorporationScalable audio coder and decoderUS6154762Jun 3, 1998Nov 28, 2000Microsoft CorporationFast system and method for computing modulated lapped transformsUS6219458Jul 30, 1999Apr 17, 2001Ricoh Co., Ltd.Overlapped reversible transforms for unified lossless/lossy compressionUS6249610Jun 17, 1997Jun 19, 2001Matsushita Electric Industrial Co., Ltd.Apparatus and method for coding a picture and apparatus and method for decoding a pictureUS6253165Jun 30, 1998Jun 26, 2001Microsoft CorporationSystem and method for modeling probability distribution functions of transform coefficients of encoded signalUS6307887May 30, 2000Oct 23, 2001Microsoft CorporationVideo encoder and decoder using bilinear motion compensation and lapped orthogonal transformsUS6324560May 2, 2000Nov 27, 2001Microsoft CorporationFast system and method for computing modulated lapped transformsUS6370502May 27, 1999Apr 9, 2002America Online, Inc.Method and system for reduction of quantization-induced block-discontinuities and general purpose audio codecUS6393061May 15, 1998May 21, 2002Hughes Electronics CorporationMethod for reducing blocking artifacts in digital imagesUS6393156Jan 6, 1999May 21, 2002Truong Q. NguyenEnhanced transform compatibility for standardized data compressionUS6421464 *Dec 16, 1998Jul 16, 2002Fastvdo LlcFast lapped image transforms using lifting stepsUS6487574Feb 26, 1999Nov 26, 2002Microsoft Corp.System and method for producing modulated complex lapped transformsUS6496795May 5, 1999Dec 17, 2002Microsoft CorporationModulated complex lapped transform for integrated signal enhancement and codingUS6728315Dec 6, 2002Apr 27, 2004Apple Computer, Inc.Method and apparatus for variable accuracy inter-picture timing specification for digital video encoding with reduced requirements for division operationsUS6728316Sep 7, 2001Apr 27, 2004Koninklijke Philips Electronics N.V.Video coding methodUS6763068Dec 28, 2001Jul 13, 2004Nokia CorporationMethod and apparatus for selecting macroblock quantization parameters in a video encoderUS6771828Mar 3, 2000Aug 3, 2004Microsoft CorporationSystem and method for progessively transform coding digital dataUS6771829Oct 23, 2000Aug 3, 2004Fastvdo LlcMethod for local zerotree image codingUS6832232 *Jul 10, 2000Dec 14, 2004Advanced Micro Devices, Inc.Dual-block inverse discrete cosine transform methodUS6865229Dec 14, 1999Mar 8, 2005Koninklijke Philips Electronics N.V.Method and apparatus for reducing the “blocky picture” effect in MPEG decoded imagesUS7006699Mar 27, 2002Feb 28, 2006Microsoft CorporationSystem and method for progressively transforming and coding digital dataUS7027654Aug 15, 2002Apr 11, 2006On2 TechnologiesVideo compression systemUS7050504Dec 5, 2002May 23, 2006Ub Video, Inc.Low-complexity deblocking filterUS7106797Apr 12, 2005Sep 12, 2006Microsoft CorporationBlock transform and quantization for image and video codingUS7110610Aug 30, 2005Sep 19, 2006Microsoft CorporationSystem and method for progressively transforming and coding digital dataUS7116834Aug 18, 2005Oct 3, 2006Microsoft CorporationSystem and method for progressively transforming and coding digital dataUS7120297Jun 26, 2002Oct 10, 2006Microsoft CorporationSegmented layered image systemUS7155065Aug 21, 2006Dec 26, 2006Microsoft CorporationSystem and method for progressively transforming and coding digital dataUS7167522Feb 27, 2003Jan 23, 2007Texas Instruments IncorporatedVideo deblocking filterUS7181403Mar 9, 2005Feb 20, 2007America Online, Inc.Method and system for reduction of quantization-induced block-discontinuities and general purpose audio codecUS7275036Oct 15, 2004Sep 25, 2007Fraunhofer-Gesellschaft Zur Foerderung Der Angewandten Forschung E.V.Apparatus and method for coding a time-discrete audio signal to obtain coded audio data and for decoding coded audio dataUS7305139Jan 14, 2005Dec 4, 2007Microsoft CorporationReversible 2-dimensional pre-/post-filtering for lapped biorthogonal transformUS7315822Feb 20, 2004Jan 1, 2008Microsoft Corp.System and method for a media codec employing a reversible transform obtained via matrix liftingUS7412102Aug 31, 2004Aug 12, 2008Microsoft CorporationInterlace frame lapped transformUS7428342Dec 17, 2004Sep 23, 2008Microsoft CorporationReversible overlap operator for efficient lossless data compressionUS7460993Dec 14, 2001Dec 2, 2008Microsoft CorporationAdaptive window-size selection in transform codingUS7471726Jul 15, 2003Dec 30, 2008Microsoft CorporationSpatial-domain lapped transform in digital media compressionUS7471850Dec 17, 2004Dec 30, 2008Microsoft CorporationReversible transform for lossy and lossless 2-D data compressionUS7551789Sep 4, 2008Jun 23, 2009Microsoft CorporationReversible overlap operator for efficient lossless data compressionUS20020110280 *Dec 19, 2001Aug 15, 2002Adityo PrakashAdaptive transformsUS20020118748Jun 27, 2001Aug 29, 2002Hideki InomataPicture coding apparatus, and picture coding methodUS20020118759Sep 7, 2001Aug 29, 2002Raffi EnficiaudVideo coding methodUS20030128756Dec 28, 2001Jul 10, 2003Nokia CorporationMethod and apparatus for selecting macroblock quantization parameters in a video encoderUS20030152146Dec 17, 2002Aug 14, 2003Microsoft CorporationMotion compensation loop with filteringUS20030185439 *Mar 27, 2002Oct 2, 2003Malvar Henrique S.System and method for progressively transforming and coding digital dataUS20030187634Mar 28, 2002Oct 2, 2003Jin LiSystem and method for embedded audio coding with implicit auditory maskingUS20030206582Feb 28, 2003Nov 6, 2003Microsoft Corporation2-D transforms for image and video codingUS20040167757Feb 18, 2004Aug 26, 2004Robert StruijsMethod for the numerical simulation of a physical phenomenon with a preferential directionUS20040170302Feb 19, 2004Sep 2, 2004Ken MusethLevel set surface editing operatorsUS20050013359Jul 15, 2003Jan 20, 2005Microsoft CorporationSpatial-domain lapped transform in digital media compressionUS20050083216Feb 20, 2004Apr 21, 2005Microsoft CorporationSystem and method for a media codec employing a reversible transform obtained via matrix liftingUS20050231396May 12, 2003Oct 20, 2005Scala Technology LimitedAudio compressionUS20060114993May 10, 2005Jun 1, 2006Microsoft CorporationSpatial scalability in 3D sub-band decoding of SDMCTF-encoded videoUS20060133682Dec 17, 2004Jun 22, 2006Microsoft CorporationReversible overlap operator for efficient lossless data compressionUS20060133684Jan 14, 2005Jun 22, 2006Microsoft CorporationReversible 2-dimensional pre-/post-filtering for lapped biorthogonal transformUS20060291734Jun 27, 2005Dec 28, 2006Hou Hsieh SShared haar wavelet transformUS20060291735Jun 27, 2005Dec 28, 2006Hou Hsieh SExtended haar transformUS20060291736Jun 27, 2005Dec 28, 2006Hou Hsieh SHaar wavelet transform embedded lossless type II discrete cosine transformUS20060293881Jun 27, 2005Dec 28, 2006Hou Hsieh SHaar wavelet transform embedded lossless type IV discrete cosine transformUS20080075377Sep 4, 2007Mar 27, 2008Topiwala Pankaj NFast lapped image transforms using lifting stepsUS20090299754May 30, 2008Dec 3, 2009Microsoft CorporationFactorization of overlapping tranforms into two block transformsAU7351001A Title not availableEP0467054B1May 28, 1991Aug 21, 1996Nec CorporationCoding and decoding methods for a picture signal using overlapping blocks having variable block sizes and apparatuses thereforEP1202219A1Oct 30, 2000May 2, 2002Fast Video, LLCFast lapped image transformsJP2002182693A Title not availableJP2002304624A Title not availableJP2003283840A Title not availableJP2003298846A Title not availableJP2003324757A Title not availableJP2004201047A Title not availableJPH0583141A Title not availableJPH0591459A Title not availableJPH1188701A Title not availableJPH06290262A Title not availableJPH11203271A Title not availableKR20040050888A Title not availableKR20060083125A Title not availableKR20060092826A Title not availableRU2194361C2 Title not availableWO2002007438A1Jul 17, 2001Jan 24, 2002Trustees Of Boston UniversityGeneralized lapped biorthogonal transform embedded inverse discrete cosine transform and low bit rate video sequence coding artifact removalWO2003038752A1Oct 10, 2002May 8, 2003Sony CorporationNon-flat image processing apparatus, image processing method, recording medium, and computer programWO2003053066A1Dec 16, 2002Jun 26, 2003Microsoft CorporationSkip macroblock codingWO2007021615A2Aug 3, 2006Feb 22, 2007Microsoft CorporationSimd lapped transform-based digital media encoding/decoding* Cited by examinerNon-Patent CitationsReference1"H.264 & IPTV Over DSL-Enabling New Telco Revenue Opportunities," White Paper, Intel/Envivio, available at http://www.envivio.com/images/products/H264whitepaper.pdf (May 15, 2004), 12 pp.2"H.264 & IPTV Over DSL—Enabling New Telco Revenue Opportunities," White Paper, Intel/Envivio, available at http://www.envivio.com/images/products/H264whitepaper.pdf (May 15, 2004), 12 pp.3Adams, "Generalized Reversible Integer-to-Integer Transform Framework," 2003 IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing, vol. 2, Aug. 2003, pp. 1000-1003.4Ahmed et al., "Discrete Cosine Transform," IEEE Transactions on Computers, C-23 (Jan. 1974), pp. 90-93.5Apostolopoulos et al., "Post-processing for very low bit-rate video compression," IEEE Trans. Image Processing, vol. 8, pp. 1125-1129 (Aug. 1999).6Arai et al., "A Fast DCT-SQ Scheme for Images," The Trans. of the IEICE, vol. E 71, No. 11, pp. 1095-1097 (Nov. 1988).7Bhaskaran et al., "Image and Video Compression Standards Algorithms and Architectures," 2nd ed., 1997, pp. 192-194.8Cham, "Development of integer cosine transforms by the principle of dyadic symmetry," IEE Proc., vol. 136, Pt. 1, No. 4, pp. 276-282 (Aug. 1989).9Chen et al., "A Fast Computational Algorithm for the Discrete Cosine Transform," IEEE Trans. on Communications, vol. COM-25, No. 9, pp. 1004-1009 (Sep. 1977).10Cheng et al., "New family of lapped biorthogonal transform via lifting steps," IEE Proc. Vision, Image and Signal Processing, vol. 149, No. 2, pp. 91-96 (Apr. 2002).11Costa et al., "Efficient Run-Length Encoding of Binary Sources with Unknown Statistics", Technical Report No. MSR-TR-2003-95, pp. 1-10, Microsoft Research, Microsoft Corporation (Dec. 2003).12de Queiroz et al., "Lapped transforms for image compression," The Handbook on Transforms and Data Compression, CRC Press, pp. 197-265 (Oct. 2000).13de Queiroz et al., "Time-Varying Lapped Transforms and Wavelet Packets," IEEE Transactions on Signal Processing, vol. 41, No. 12, pp. 3293-3305 (1993).14Decision on Grant dated Mar. 3, 2011, from Russian Patent Application No. 2008105020 (with English translation), 22 pp.15Examination Report dated Feb. 21, 2011, from New Zealand Patent Application No. 565534, 2 pp.16Examination Report dated Sep. 24, 2009, from New Zealand Patent Application No. 565534, 2 pp.17Examiner's First Report dated Oct. 22, 2010, from Australian Patent Application No. 2006280180, 2 pp.18Examiner's Report No. 2 dated Mar. 7, 2011, from Australian Patent Application No. 2006280180, 1 pp.19First Office Action dated Nov. 20, 2009, from Chinese Patent Application No. 200680029306.3, 8 pp.20Fukuma et al., "Lossless 8-point fast discrete cosine transform using lossless hadamard transform," Technical Report of IEICE, vol. 99, No. 399, pp. 37-44 (Oct. 29, 1999) (with English abstract).21Gangaputra et al., "Adaptive Pre- and Post-Filtering for Block Based Systems," IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, vol. 4, pp. IV-3297 through IV-3300 (May 2002).22Goel et al., "Pre-processing for MPEG Compression Using Adaptive Spatial Filtering," Proceedings of 1995 IEEE International Conference on Consumer Electronics, 1995, pp. 246-247.23Hao et al., "Matrix Factorizations for Reversible Integer Mapping," IEEE Transactions on Signal Processing, vol. 49, Issue 10, Oct. 2001, pp. 2314-2324.24Hohl, "An 8×8 Discrete Cosine Transform Implementation on the TMS320C25 or the TMS320C30," Texas Instruments Application Report SPRA115, pp. 1-25 (1990) http://focus.ti.com/lit/an/spra115/spra115.pdf [Downloaded from the World Wide Web on Dec. 28, 2005].25Hui et al., "An Integer Hierarchy Lapped Biorthogonal Transform via Lifting Steps and Application in Image Coding," IEEE Int'l Conf. on Signal Processing, vol. 1, pp. 664-667 (Aug. 2002).26Intel Corporation, "Using MMX(TM) Instructions in a Fast iDCT Algorithm for MPEG Decoding," 21 pp. (Mar. 1996).27Intel Corporation, "Using MMX™ Instructions in a Fast iDCT Algorithm for MPEG Decoding," 21 pp. (Mar. 1996).28Intel Corporation, "Using Streaming SIMD Extensions in a Fast DCT Algorithm for MPEG Encoding," Version 1.2, 11 pp. (Jan. 1999).29International Search Report and Written Opinion for PCT/US06/30565.30International Search Report for PCT/US04/28969, completed Jul. 11, 2006, 4 pp.31International Search Report for PCT/US2009/044983 dated Jan. 7, 2010, 10 pp.32ISO/IEC 14496-2, "Coding of Audio-Visual Object-Part 2: Visual," Third Edition, pp. 1-727, (Jun. 2004).33ISO/IEC 14496-2, "Coding of Audio-Visual Object—Part 2: Visual," Third Edition, pp. 1-727, (Jun. 2004).34ISO/IEC JTC1/SC29/WG11 N4668, "Coding of Moving Pictures and Audio," Title: MPEG-4 Overview-(V.21-Jeju Version), Editor: Rob Koenen (rob.koenen@m4if.org), available at http://www.chiariglione.org/mpeg/standards/mpeg-4/mpeg-4.htm (Mar. 2002), 66 pp.35ISO/IEC JTC1/SC29/WG11 N4668, "Coding of Moving Pictures and Audio," Title: MPEG-4 Overview—(V.21—Jeju Version), Editor: Rob Koenen (rob.koenen@m4if.org), available at http://www.chiariglione.org/mpeg/standards/mpeg-4/mpeg-4.htm (Mar. 2002), 66 pp.36ISO/IEC, "Information Technology-Coding of Audio-Visual Objects: Visual, ISO/IEC 14496-2, Committee Draft," 330 pp. (1998).37ISO/IEC, "Information Technology—Coding of Audio-Visual Objects: Visual, ISO/IEC 14496-2, Committee Draft," 330 pp. (1998).38ISO/IEC, "ISO/IEC 11172-2: Information Technology-Coding of Moving Pictures and Associated Audio for Storage Media at up to About 1.5 Mbit/s," 122 pp. (1993).39ISO/IEC, "ISO/IEC 11172-2: Information Technology—Coding of Moving Pictures and Associated Audio for Storage Media at up to About 1.5 Mbit/s," 122 pp. (1993).40ITU-T Recommendation H.264, "Series H: Audiovisual and Multimedia Systems, Infrastructure of Audiovisual Services-Coding of Moving Video," International Telecommunication Union, pp. 1-262 (May 2003).41ITU-T Recommendation H.264, "Series H: Audiovisual and Multimedia Systems, Infrastructure of Audiovisual Services—Coding of Moving Video," International Telecommunication Union, pp. 1-262 (May 2003).42ITU-T Recommendation T.800, "Series T: Terminals for Telematic Services," International Telecommunication Union, pp. 1-194 (Aug. 2002).43ITU-T, "ITU-T Recommendation H.261: Video Codec for Audiovisual Services at p x 64 kbits," 28 pp. (1993).44ITU-T, "ITU-T Recommendation H.262: Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video," 218 pp. (1995).45ITU-T, "ITU-T Recommendation H.262: Information Technology—Generic Coding of Moving Pictures and Associated Audio Information: Video," 218 pp. (1995).46ITU-T, "ITU-T Recommendation H.263: Video Codingk for Low Bit Rate Communication," 167 pp. (1998).47Jain, "Fundamentals of Digital Image Processing," Chapters 2, 5, and 11, Prentice Hall, 189 pp. (1989).48Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, "Joint Final Committee Draft (JFCD) of Joint Video Specification," JVT-D157, 207 pp. (Aug. 2002).49Klausutis et al., "Variable Block Size Adaptive Lapped Transform-based Image Coding," 1997 International Conference on Image Processing (ICIP '97), vol. 3, pp. 686-689 (1997).50List et al., "Adaptive deblocking filter," IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, No. 7, pp. 614-619 (Jul. 2003).51Malvar, "Biorthogonal and Nonuniform Lapped Transforms for Transform Coding with Reduced Blocking and Ringing Artifacts," appeared in IEEE Transactions on Signal Processing, Special Issue on Multirate Systems, Filter Banks, Wavelets, and Applications, vol. 46, 29 pp. (1998).52Malvar, "Extended Lapped Transforms: Fast Algorithms and Applications," ICASSP, vol. 3, pp. 1797-1800, Apr. 14-17, 1991.53Malvar, "Fast Progressive Image Coding without Wavelets", IEEE Data Compression Conference, Snowbird, Utah, 10 pp. (Mar. 2000).54Malvar, "Lapped Biorthogonal Transforms for Transform Coding with Reduced Blocking and Ringing Artifacts," IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 2421-2424 (Apr. 1997).55Malvar, "Lapped Transforms for Efficient Transform/Subband Coding," IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 38, No. 6, pp. 969-978 (1990).56Malvar, "Signal Processing With Lapped Transforms," Norwood, MA: Artech House, pp. 175-219, 264-273, and 353-357 (1992).57Malvar, "Signal Processing with Lapped Transforms," pp. 143-173, and 265-273 (1992).58Microsoft Corporation, "Microsoft Debuts New Windows Media Player 9 Series, Redefining Digital Media on the PC," 4 pp. (Sep. 4, 2002) [Downloaded from the World Wide Web on May 14, 2004].59Mook, "Next-Gen Windows Media Player Leaks to the Web," BetaNews, 17 pp. (Jul. 19, 2002) [Downloaded from the World Wide Web on Aug. 8, 2003].60Muramatsu et al., "The two-dimensional lapped Hadamard transform," IEEE Proc. on Circuits and Systems, vol. 5, pp. 86-89 (May 1998).61Murata et al., "Fast 2D IDCT Implementation with Multimedia Instructions for a Software MPEG2 Decoder," IEEE Conf. Acoustics, Speech and Signal Processing, vol. 5, 4 pp. (May 1998).62Notice of Rejection dated Dec. 7, 2010, from Japanese Patent Application No. 2008-526093 (with English translation), 9 pp.63Notice on Grant of Patent dated Aug. 31, 2010, from Chinese Patent Application No. 200680029306.3, 4 pp.64Notice on the Second Office Action dated May 25, 2010, from Chinese Patent Application No. 200680029306.3, 8 pp.65Office action dated Aug. 9, 2010, from Mexican Patent Application No. MX/a/2008/001853, 2 pp.66Office action dated Nov. 24, 2010, from Russian Patent Application No. 2008105020, 4 pp.67Ostermann et al., "Video Coding with H.264/AVC", IEEE Circuits and Systems Magazine, First Quarter 2004 (retrieved on Apr. 14, 2007), retrieved from the internet .68Ostermann et al., "Video Coding with H.264/AVC", IEEE Circuits and Systems Magazine, First Quarter 2004 (retrieved on Apr. 14, 2007), retrieved from the internet <URL:http://ieeexplore.ieee.org>.69 *Ostermann, J, Bormans, J., List, P., Marpe, D., Narroschke, M., Pereira, F., Stockhammer,T., Wedl, T., "Video Coding with H.264/AVC: Tools, Performance, and Complexity", IEEE Circuits and Systems Magazine, First Quarter 2004.70Paeth, "A Fast Algorithm for General Raster Rotation," Proceedings of Graphics Interface '86, pp. 77-81, May 1986.71Park et al., "A post processing method for reducing quantization effects in low bit-rate moving picture coding," IEEE Trans. Circuits Syst., Video Technol., vol. 9, pp. 161-171 (Feb. 1999).72Printouts of FTP directories from http://ftp3.itu.ch, 8 pp. (downloaded from the World Wide Web on Sep. 20, 2005).73Proposed SMPTE Standard for Television: VC-1 Compressed Video Bitstream Format and Decoding Process, pp. 1-500, (Aug. 2005).74Rao et al., "Techniques and Standards for Image, Video, and Audio Coding," Englewood Cliffs, NJ: Prentice-Hall (1996).75Reader, "History of MPEG Video Compression-Ver. 4.0," 99 pp. (document marked Dec. 16, 2003), 21 pp.76Reader, "History of MPEG Video Compression—Ver. 4.0," 99 pp. (document marked Dec. 16, 2003), 21 pp.77Shlien, "The Modulated Lapped Transform, Its Time-Varying Forms, and Its Applications to Audio Coding Standards," IEEE Transactions on Speech and Audio Processing, vol. 5, No. 4, pp. 359-366 (Jul. 1997).78Srinivasan et al., "Windows Media Video 9: overview and applications," Signal Processing Image Communication, vol. 19, No. 9, pp. 851-875 (Oct. 2004).79Substantive Examination Adverse Report dated Jun. 19, 2009, from Malaysian Patent Application No. PI20063565, 4 pp.80Tanaka et al., "A Rotation Method for Raster Image Using Skew Transformation," Proc IEEE Conf on Computer Vision and Pattern Recognition, pp. 272-277, Jun. 1986.81Tran et al., "Lapped Transform Based Video Coding," Proc. SPIE Applicat. Digital Image Processing XXIV, San Diego, CA, pp. 319-333 (Aug. 2001).82Tran et al., "Lapped Transform via Time-Domain Pre- and Post-Filtering," IEEE Transactions on Signal Processing, vol. 51, No. 6, pp. 1557-1571 (Jun. 2003).83Tran et al., "Regularity-constrained pre- and post-filtering for block DCT-based systems,", IEEE Trans. on Signal Processing, vol. 51, No. 10, pp. 2568-2581 (Oct. 2003).84Tran et al., Lapped Transform via Time-Domain Pre- and Post-Filtering, IEEE Transactions on Signal Processing, vol. 51, No. 6, Jun. 2003 (retrieved on Apr. 15, 2007), retrieved from the internet <URL:http://ieeexplore.ieee.org> 2, 7, 11, 15.85Tran et al., Lapped Transform via Time-Domain Pre- and Post-Filtering, IEEE Transactions on Signal Processing, vol. 51, No. 6, Jun. 2003 (retrieved on Apr. 15, 2007), retrieved from the internet 2, 7, 11, 15.86Tran, "Lapped Transform via Time-Domain Pre- and Post-Processing," 2001 Conference on Information Sciences and Systems, The Johns Hopkins University (Mar. 21-23, 2001).87 *Tran,T., Liang, J. and Tu, C, "Lapped Transform via Time-Domain Pre- and Post-Filtering", IEEE Transactions on Signal Processing, vol. 51, No. 6, Jun. 2003.88Tu et al., "Context-Based Entropy Coding of Block Transform Coefficients for Image Processing," IEEE Transactions on Image Processing, vol. 11, No. 11, pp. 1271-1283 (Nov. 2002).89U.S. Appl. No. 60/341,674, filed Dec. 2001, Lee et al.90U.S. Appl. No. 60/488,710, filed Jul. 2003, Srinivasan et al.91Wang et al., "Interlace Coding Tools for H.26L Video Coding," ITU, VCEG-O37, 20 pp. (Nov. 2001).92Wien, "Variable Block-Size Transforms for Hybrid Video Coding," Dissertation, 182 pp. (Feb. 2004).* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8285774 *Jul 22, 2008Oct 9, 2012Novatek Microelectronics Corp.Operation method and apparatus for performing overlap filter and core transformUS9319065 *Mar 15, 2012Apr 19, 2016Nokia Technologies OyEncoding and decoding of dataUS20090240754 *Jul 22, 2008Sep 24, 2009Novatek Microelectronics Corp.Operation method and apparatus for performing overlap filter and core transformUS20150311916 *Mar 15, 2012Oct 29, 2015Nokia CorporationEncoding and decoding of data* Cited by examinerClassifications U.S. Classification375/240.18, 708/401International ClassificationH04N11/04, H04N11/02, H04N7/12Cooperative ClassificationG06F17/147, H04N19/436, H04N19/63, H04N19/42European ClassificationH04N7/26H30D2, H04N7/26L6Legal EventsDateCodeEventDescriptionAug 24, 2005ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SRINIVASAN, SRIDHAR;TU, CHENGJIE;SHAW, PARKER;REEL/FRAME:016447/0027Effective date: 20050812Dec 9, 2014ASAssignmentOwner name: MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MICROSOFT CORPORATION;REEL/FRAME:034543/0001Effective date: 20141014Mar 25, 2015FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services