Fast signal transforms with lifting steps
DCFirst Claim
1. An apparatus for coding, storing or transmitting, and decoding M×
- M sized blocks of digitally represented images, where M is an even number, comprisinga. a forward transform comprising i. a base transform having M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even;
ii. an equal normalization factor in each of the M channels selected to be dyadic-rational;
iii. a full-scale butterfly implemented as a series of lifting steps with a first set of dyadic rational coefficients;
iv. M/2 delay lines in the odd numbered channels;
v. a full-scale butterfly implemented as a series of lifting steps with said first set of dyadic rational coefficients; and
vi. a series of lifting steps in the odd numbered channels with a second specifically selected set of dyadic-rational coefficients;
b. means for transmission or storage of the transform output coefficients; and
c. an inverse transform comprising i. M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even;
ii. a series of inverse lifting steps in the odd numbered channels with said second set of specifically selected dyadic-rational coefficients;
iii. a full-scale butterfly implemented as a series of lifting steps with said first set of specifically selected dyadic-rational coefficients;
iv. M/2 delay lines in the even numbered channels;
v. a full-scale butterfly implemented as a series of lifting steps with said first set of specifically selected dyadic-rational coefficients;
vi. an equal denormalization factor in each of the M channels specifically selected to be dyadic-rational; and
vii. a base inverse transform having M channels numbered 0 through M−
1.
2 Assignments
Litigations
0 Petitions
Accused Products
Abstract
This invention introduces a class of multi-band linear phase lapped biorthogonal transforms with fast, VLSI-friendly implementations via lifting steps called the LiftLT. The transform is based on a lattice structure which robustly enforces both linear phase and perfect reconstruction properties. The lattice coefficients are parameterized as a series of lifting steps, providing fast, efficient in-place computation of the transform coefficients as well as the ability to map integers to integers. Our main motivation of the new transform is its application in image and video coding. Comparing to the popular 8×8 DCT, the 8×16 LiftLT only requires 1 more multiplication, 22 more additions, and 6 more shifting operations. However, image coding examples show that the LiftLT is far superior to the DCT in both objective and subjective coding performance. Thanks to properly designed overlapping basis functions, the LiftLT can completely eliminate annoying blocking artifacts. In fact, the novel LiftLT'"'"'s coding performance consistently surpasses that of the much more complex 9/7-tap biorthogonal wavelet with floating-point coefficients. More importantly, our transform'"'"'s block-based nature facilitates one-pass sequential block coding, region-of-interest coding/decoding as well as parallel processing.
31 Citations
39 Claims
-
1. An apparatus for coding, storing or transmitting, and decoding M×
- M sized blocks of digitally represented images, where M is an even number, comprising
a. a forward transform comprising i. a base transform having M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even;
ii. an equal normalization factor in each of the M channels selected to be dyadic-rational;
iii. a full-scale butterfly implemented as a series of lifting steps with a first set of dyadic rational coefficients;
iv. M/2 delay lines in the odd numbered channels;
v. a full-scale butterfly implemented as a series of lifting steps with said first set of dyadic rational coefficients; and
vi. a series of lifting steps in the odd numbered channels with a second specifically selected set of dyadic-rational coefficients;
b. means for transmission or storage of the transform output coefficients; and
c. an inverse transform comprising i. M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even;
ii. a series of inverse lifting steps in the odd numbered channels with said second set of specifically selected dyadic-rational coefficients;
iii. a full-scale butterfly implemented as a series of lifting steps with said first set of specifically selected dyadic-rational coefficients;
iv. M/2 delay lines in the even numbered channels;
v. a full-scale butterfly implemented as a series of lifting steps with said first set of specifically selected dyadic-rational coefficients;
vi. an equal denormalization factor in each of the M channels specifically selected to be dyadic-rational; and
vii. a base inverse transform having M channels numbered 0 through M−
1. - View Dependent Claims (2, 3, 4, 5, 6, 7, 11)
- M sized blocks of digitally represented images, where M is an even number, comprising
-
8. An apparatus for coding, compressing, storing or transmitting, and decoding a block of M×
- M intensities from a digital image selected by an M×
M window moving recursively over the image, comprising;a. an M×
M block transform comprising;
i. an initial stage ii. a normalizing factor in each channel b. a cascade comprising a plurality of dyadic rational lifting transforms, each of said plurality of dyadic rational lifting transforms comprising i. a first bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
ii. a bank of delay lines in a first group of M/2 alternating lines;
iii. a second bank of butterfly lifting steps with unitary coefficients, and iv. a bank of pairs of butterfly lifting steps with coefficients of 1/2 between M/2−
1 pairs of said M/2 alternating lines;
c. means for transmission or storage of the output coefficients of said M×
M block transform; and
d. an inverse transform comprising i. a cascade comprising a plurality of dyadic rational lifting transforms, each of said plurality of dyadic rational lifting transforms comprising a) a bank of pairs of butterfly lifting steps with coefficients of 1/2 between said M/2−
1 pairs of said M/2 alternating lines;
b) a first bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
c) a bank of delay lines in a second group of M/2 alternating lines, ;
andd) a second bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
ii. a de-scaling bank, ;
andiii. an inverse initial stage.
- M intensities from a digital image selected by an M×
-
9. A method of coding, storing or transmitting, and decoding M×
- M sized blocks of digitally represented images, where M is an even number a power of 2, comprising
a. transmitting the original picture signals to a coder, which effects the steps of i. converting the signals with a base transform having M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even, ;ii. normalizing the output of the preceding step with a dyadic rational normalization factor in each of said M channels;
iii. processing the output of the preceding step through two lifting steps with a first set of identical dyadic rational coefficients connecting each pair of adjacent numbered channels in a butterfly configuration;
iv. transmitting the resulting coefficients through M/2 delay lines in the odd numbered channels;
v. processing the output of the preceding step through two inverse lifting steps with the first set of dyadic rational coefficients connecting each pair of adjacent numbered channels in a butterfly configuration; and
vi. applying two lifting steps with a second set of identical dyadic rational coefficients connecting each pair of adjacent odd numbered channels to the output of the preceding step;
b. transmitting or storing the transform output coefficients;
c. receiving the transform output coefficients in a decoder; and
d. processing the output coefficients in a decoder, comprising the steps of i. receiving the coefficients in M channels numbered 0 through M−
1, half of said channel numbers being odd and half being even;
ii. applying two inverse lifting steps with dyadic rational coefficients connecting each pair of adjacent odd numbered channels;
iii. applying two lifting steps with dyadic rational coefficients connecting each pair of adjacent numbered channels in a butterfly configuration;
iv. transmitting the result of the preceding step through M/2 delay lines in the even numbered channels;
v. applying two inverse lifting steps with dyadic rational coefficients connecting each pair of adjacent numbered channels in a butterfly configuration;
vi. denormalizing the result of the preceding step with a dyadic rational inverse normalization factor in each of said M channels; and
vii. processing the result of the preceding step through a base inverse transform having M channels numbered 0 through M−
1.
- M sized blocks of digitally represented images, where M is an even number a power of 2, comprising
-
10. A method of coding, compressing, storing or transmitting, and decoding a block of M×
- M intensities from a digital image selected by an M×
M window moving recursively over the image, comprising the steps of;a. Processing the intensities in an M×
M block coder comprising the steps of;
i. processing the intensities through an initial stage;
ii. scaling the result of the preceding step in each channel;
b. processing the result of the preceding step through a cascade comprising a plurality of dyadic rational lifting transforms, each of said plurality of dyadic rational lifting transforms comprising i. a first bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
ii. a bank of delay lines in a first group of M/2 alternating lines;
iii. a second bank of butterfly lifting steps with unitary coefficients, and iv. a bank of pairs of butterfly lifting steps with coefficients of 1/2 between M/2−
1 pairs of said M/2 alternating lines;
c. transmitting or storing the output coefficients of said M×
M block coder;
d. receiving the output coefficients in a decoder; and
e. processing the output coefficients in the decoder, comprising the steps of i. processing the output coefficients through a cascade comprising a plurality of dyadic rational lifting transforms, each of said plurality of dyadic rational lifting transforms comprising a) a bank of pairs of butterfly lifting steps with coefficients of 1/2 between said M/2−
1 pairs of said M/2 alternating lines;
b) a first bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
c) a bank of delay lines in a second group of M/2 alternating lines;
d) a second bank of pairs of butterfly lifting steps with unitary coefficients between adjacent lines of said transform;
e) a de-scaling bank; and
f. processing the results of the preceding step in an inverse initial stage.
- M intensities from a digital image selected by an M×
-
12. A method of coding, storing or transmitting, and decoding a block of M×
- M intensities from a digital image selected by an M×
M window moving recursively over the image, comprising;a. processing the intensities in an M×
M block coder comprising the steps of;
i. processing the intensities through an initial stage;
ii. scaling the result of the preceding step in each channel;
b. processing the result of the preceding step through a transform coder using a method of processing blocks of samples of digital signals of integer length M comprising processing the digital samples of length M with an invertible linear transform of dimension M, said transform being representable as a cascade, using the steps, in arbitrary order, of;
i) at least one +/−
1 butterfly step,ii) at least one lifting step with rational complex coefficients, and iii) at least one scaling factor;
c. transmitting or storing the output coefficients of said M×
M block coder;
d. receiving the output coefficients in a decoder; and
e. processing the output coefficients in the decoder into a reconstructed image using the inverse of the coder of steps a. and b. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
- M intensities from a digital image selected by an M×
-
26. A method of coding, storing or transmitting, and decoding sequences of intensities of integer length M recursively selected from a time ordered string of intensities arising from electrical signals, the method comprising the steps of
a) recursively processing the sequences of intensities of integer length M with an invertible forward linear transform of dimension M, said transform being representable as a cascade using the steps, in a preselected arbitrary order, of: -
ii) at least one ±
1 butterfly step,iii) at least one lifting step with rational complex coefficients, and iv) applying at least one scaling factor;
b) compressing the resulting transform coefficients;
c) storing or transmitting the compressed transform coefficients;
d) receiving or recovering from storage the transmitted or stored compressed transform coefficients;
e) decompressing the received or recovered compressed transform coefficients; and
f) recursively processing the decompressed transform coefficients with the inverse of the forward linear transform of dimension M, said inverse transform being representable as a cascade using the steps, in the exact reverse order of the preselected arbitrary order, of;
ii) at least one inverse butterfly corresponding to each of the at least one ±
1 butterfly step;
iii) at least one inverse lifting step corresponding to each of the at least one lifting step with rational complex coefficients; and
,iv) applying at least on inverse scaling factor corresponding to the at least one scaling factor. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
Specification