Reversible transform for lossy and lossless 2-D data compression
AssigneeMicrosoft Corporation
InventorSridhar Srinivasan
Life of this patent
Estimating the term…
Abstract
A 2D transform and its inverse have an implementation as a sequence of lifting steps arranged for reduced computational complexity (i.e., reducing a number of non-trivial operations). This transform pair has energy compaction properties similar to the discrete cosine transform (DCT), and is also lossless and scale-free. As compared to a separable DCT transform implemented as 1D DCT transforms applied separably to rows and columns of a 2D data block, the transforms operations are re-arranged into a cascade of elementary transforms, including the 2×2 Hadamard transform, and 2×2 transforms incorporating lifting rotations. These elementary transforms have implementations as a sequence of lifting operations.
Claims20
A method of performing a reversible, scale-free 2-dimensional block transform defined as a 1-dimensional transform applied horizontally and vertically on a 2-dimensional block of digital media data, the method comprising:
- in each of two or more stages interleaving operations from the horizontal and vertical 1-dimensional transforms, applying the operations in the respective stage re-arranged as a set of elementary transforms implemented as lifting steps to independent subsets of values in the 2-dimensional block.
The method of claim 3 wherein the 4-value subsets comprise:
- a group of four values at corners of the 2-dimensional block;
- a group of four values in a center of the 2-dimensional block;
- a group of four values at horizontal edge centers of the 2-dimensional block;
- and
- a group of four values at vertical edge centers of the 2-dimensional block.
An encoder of a lossy/lossless compression system for performing lossy/lossless compression of 2-dimensional digital media data with block transform-based coding using a reversible, scale-free 2-dimensional transform defined as a 4-point transform applied vertically and horizontally to 2-dimensional blocks of the digital media data, the encoder comprising:
- a buffer memory for buffering 2-dimensional digital media data to be encoded;
- a processor for applying the transform to 2-dimensional blocks of the digital media data by, in each of two or more stages interleaving operations from the horizontal and vertical 1-dimensional 4-point transform, applying the operations in the respective stage re-arranged as a set of elementary 2×2 transforms implemented as lifting steps to independent 4 value subsets in the 2-dimensional block.
Dependencies are inferred from the claim text.