Data compression using matching pursuits

A method of data compression comprising:

• (a) applying by one or hardware encoders a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• (b) convolving by the one or hardware encoders the transform data set with each of a plurality of first one-dimensional basis functions to generate a corresponding plurality of convolved data sets;
• (c) determining by the one or hardware encoders a location in a first direction across all the convolved data sets, and a first basis function, representative of a greatest magnitude;
• (d) representing by the one or hardware encoders part of the transform data surrounding the said location with an atom derived from the first basis function corresponding to the greatest determined magnitude;
• (e) subtracting by the one or hardware encoders the atom from the transform data set to create a new data set;
• (f) repeatedly updating by the one or hardware encoders the convolved data sets by convolving any changed part of the transform data set with each of the plurality of first one-dimensional basis functions, and then re-applying steps (c) and (d);
• and
• (g) outputting by the one or hardware encoders as transform data coded versions of the atoms derived at step (d),
• wherein the data to be compressed represents video image data, wherein the transform decorrelates at least part of the transform data set better in one direction than in a perpendicular direction, and wherein a first algorithm is applied by carrying out a one-dimensional scan in a direction of greatest correlation.

A method of data compression comprising:

• (a) applying by one or hardware encoders a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• (b) convolving by the one or hardware encoders the transform data set with each of a plurality of first one-dimensional basis functions to generate a corresponding plurality of convolved data sets;
• (c) determining by the one or hardware encoders a first location in a first direction across all the convolved data sets, and a first basis function representative of a greatest magnitude;
• and representing by the one or hardware encoders part of the transform data surrounding the first location with a first atom derived from the first basis function corresponding to the greatest determined magnitude;
• (d) subtracting by the one or hardware encoders the first atom from the transform data set to create a new data set;
• (e) convolving by the one or hardware encoders the new data set with each of a plurality of second one-dimensional basis functions;
• (f) determining by the one or hardware encoders a second location in a second direction across all the convolved data sets, and a second basis function representative of a greatest magnitude;
• and representing by the one or hardware encoders part of the new data set surrounding the second location with a second atom derived from the second basis function corresponding to the greatest determined magnitude;
• (g) subtracting by the one or hardware encoders the second atom from the new data set to create a further new data set;
• (h) repeating by the one or hardware encoders step (b) with the further new data set, and then re-applying steps (c) to (f);
• and
• (i) outputting by the one or hardware encoders as quantized transform data coded versions of the atoms derived at steps (c) and (f),
• wherein the second basis function representative of the greatest magnitude is determined without further searching in the region of the second location.

A hardware coder for data compression comprising:

• a processor;
• means for applying a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• and
• means for coding the transform data set by applying one or more one-dimensional matching pursuits algorithms,
• wherein the transform is a frequency-separating transform, and wherein the transform decorrelates at least part of the transform data set better in one direction than in a perpendicular direction, and in which a first algorithm is applied by carrying out a one-dimensional scan in a direction of greatest correlation.

A hardware coder for data compression comprising:

• (a) means for applying a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• (b) means for convolving the transform data set with each of a plurality of first one-dimensional basis functions to generate a corresponding plurality of convolved data sets;
• (c) means for determining a location in a first direction across all the convolved data sets, and a first basis function representative of a greatest magnitude;
• (d) means for representing part of the transform data surrounding the said location with an atom derived from the first basis function corresponding to the greatest determined magnitude;
• (e) means for subtracting the atom from the transform data set to create a new data set;
• (f) means for repeatedly updating the convolved data sets by convolving any changed part of the transform data set with each of the plurality of first one-dimensional basis functions;
• (g) means for outputting as transform data coded versions of the derived atoms;
• and
• (h) a processor,
• wherein the data to be compressed represents video image data, wherein the transform decorrelates at least part of the transform data set better in one direction than in a perpendicular direction, and wherein a first algorithm is applied by carrying out a one-dimensional scan in a direction of greatest correlation.

A hardware coder for data compression comprising:

• a processor;
• means for applying a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• and
• means for coding the transform data set by applying one or more one-dimensional matching pursuits algorithms,
• wherein the algorithms are applied by sequential one-dimensional scans through the data, and wherein successive scans continue in the same direction until an atom is located of lower magnitude than atoms which have previously been located in scans in other directions, and in which the scan direction is then changed.

A hardware coder for data compression comprising:

• (a) means for applying a transform to multi-dimensional data to generate a multi-dimensional transform data set;
• (b) means for convolving the transform data set with each of a plurality of first one-dimensional basis functions to generate a corresponding plurality of convolved data sets;
• (c) means for determining a first location in a first direction across all the convolved data sets, and a first basis function representative of a greatest magnitude;
• and representing part of the transform data surrounding the first location with a first atom derived from the first basis function corresponding to the greatest determined magnitude;
• (d) means for subtracting the first atom from the transform data set to create a new data set;
• (e) means for convolving the new data set with each of a plurality of second one-dimensional basis functions;
• (f) means for determining a second location in a second direction across all the convolved data sets, and a second basis function representative of a greatest magnitude;
• and representing part of the new data set surrounding the second location with a second atom derived from the second basis function corresponding to the greatest determined magnitude;
• (g) means for subtracting the second atom from the new data set to create a further new data set;
• (h) means for repeating step (b) with the further new data set, and then re-applying steps (c) to (f);
• (i) means for outputting as transform data coded versions of the atoms derived at steps (c) and (f);
• and
• (j) a processor,
• wherein the second basis function representative of the greatest magnitude is determined without further searching in the region of the second location.