Nova Patents
EP0907288A2

Method and apparatus for fast image compression

Abstract

An image compression scheme uses a reversible transform, such as the Discrete Hartley Transform, to efficiently compress and expand image data for storage and retrieval of images in a digital format. The image data is divided into one or more image sets, each image set representing a rectangular array of pixel data from the image. Each image set is transformed using a reversible transform, such as the Hartley transform, into a set of coefficients which are then quantized and encoded using an entropy coder. The resultant coded data sets for each of the compressed image sets are then stored for subsequent expansion. Expansion of the stored data back into the image is essentially the reverse of the compression scheme.

EP0907288A2, drawing sheet 1
Sheet 1 of 31

Term

Term ended

Projected expiry passed 2 October 2018, 8 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

53 claims: 19 independent, 34 dependent

  1. 1
    A method for compressing an image, comprising the steps of:1. dividing the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: 1. transforming the image set into a set of coefficients using a reversible transform;2. quantizing each coefficient of the set of coefficients;and 3. coding each quantized coefficient of the set of coefficients in accordance with an entropy code.
  2. 2
    The method according to claims 1 or 13, wherein the reversible transform comprises a two-stage Hartley transform, said two-stage Hartley transform comprising, in any order, one pass of a one-dimensional row Hartley transform and one pass of a one-dimensional column Hartley transform.
  3. 5
    The method according claim 1, wherein the step of quantizing each coefficient of the set of coefficients comprises the substeps of:(a) determining the relative significance of the coefficient;and (b) retaining a number of bits used to represent the coefficient in accordance with its determined relative significance.
  4. 7
    The method according claim 1, wherein the image comprises components corresponding to color information.
  5. 13
    A method for restoring from compressed image data an image having at least one image set comprised of a two-dimensional array of pixels having a number of columns M and a number of rows N, comprising the steps of:1. decoding the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: 1. unquantizing the coefficients;2. inverse-transforming the unquantized coefficients into an image set using a reversible transform;and 3. combining each image set into the image.
  6. 18
    The method according to one or more of claims 13-17, wherein the step of decoding the compressed image data into at least one set of coefficients in accordance with an entropy code includes the substeps of:1. determining a code group corresponding to a code prefix by matching a prefix portion of the compressed image data against a set of known code prefixes associated with the entropy code;and 2. identifying the value of the coefficient within the determined code group by matching a suffix portion of the set of compressed image data against a set of known code suffixes associated with the entropy code.
  7. 19
    A method for compressing and restoring an image, comprising the steps of:1. compressing the image, including the substeps of: 1. dividing the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: (a) transforming the image set into a set of coefficients using a reversible transform;(b) quantizing each coefficient of the set of coefficients;and (c) coding each quantized coefficient of the set of coefficients in accordance with an entropy code;and 2. restoring the image, including the substeps of: 1. decoding the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: (a) unquantizing the coefficients;(b) inverse-transforming the unquantized coefficients into an image set using a reversible transform;and 3. combining each image set into the image.
  8. 20
    A system for compressing an image divisible into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N, comprising:1. a transformer that transforms each image set into a set of coefficients using a reversible transform;2. a quantizer that quantizes each coefficient,of the set of coefficients;and 3. a coder that encodes the set of quantized coefficients in accordance with an entropy code.
  9. 21
    The system or article according to one of claims 20, 25, 33, 36, 42 or 49, wherein the reversible transform comprises a two-stage Hartley transform, said two-stage Hartley transform comprising, in any order, one pass of a one-dimensional row Hartley transform and one pass of a one-dimensional column Hartley transform.
  10. 25
    A system for compressing an image, comprising a processor programmed to:1. divide the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: 1. transform the image set into a set of coefficients using a reversible transform;2. quantize each coefficient of the set of coefficients;and 3. code each quantized coefficient of the set of coefficients in accordance with an entropy code.
  11. 32
    The system or article according to claims 25 or 42, wherein the entropy code is obtained for an expected distribution of coefficients by:1. computing a canonical Huffman coding tree for the expected distribution of coefficients;2. combining all codes of equal length into a common code group;3. assigning to each code group a code prefix based upon the structure of the canonical Huffman coding tree;and 4. assigning a suffix to each separate symbol in the code group;or wherein the system further comprises memory for storing the coded quantized coefficients, or wherein the instructions, when executed by a processor, further cause the processor to store the coded quantized coefficients in a memory.
  12. 33
    A system for restoring from compressed image data an image having at least one image set comprised of a two-dimensional array of pixels having a number of columns M and a number of rows N, comprising:1. a decoder that decodes the compressed image data into at least one set of coefficients in accordance with an entropy code;2. a unquantizer that unquantizes each coefficient of each set of coefficients;and 3. an inverse-transformer that inverse-transforms each set of unquantized coefficients into an image set using a reversible transform.
  13. 36
    A system for restoring from compressed image data an image having at least one image set comprised of a two-dimensional array of pixels having a number of columns M and a number of rows N, comprising a processor programmed to:1. decode the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: 1. unquantize the coefficients;2. inverse-transform the unquantized coefficients into an image set using a reversible transform;and 3. combine each image set into the image.
  14. 40
    A system for compressing and restoring an image divisible into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N, comprising:1. a compressor, comprising: 1. a transformer that transforms each image set into a set of coefficients using a reversible transform;2. a quantizer that quantizes each coefficient of the set of coefficients;and 3. a coder that encodes the set of quantized coefficients in accordance with an entropy code;and 2. a restorer,comprising: 1. a decoder that decodes compressed image data into at least one set of coefficients in accordance with an entropy code;2. a unquantizer that unquantizes each coefficient of each set of coefficients;and 3. an inverse-transformer that inverse-transforms each set of unquantized coefficients into an image set using a reversible transform.
  15. 41
    A system for compressing and restoring an image, comprising a processor programmed to:1. compress the image by: 1. dividing the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: (a) transforming the image set into a set of coefficients using a reversible transform;(b) quantizing each coefficient of the set of coefficients;and (c) coding each quantized coefficient of the set of coefficients in accordance with an entropy code;and 2. restore the image by: 1. decoding the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: (a) unquantizing the coefficients;(b) inverse-transforming the unquantized coefficients into an image set using a reversible transform;and 3. combining each image set into the image.
  16. 42
    An article of manufacture comprising a computer-readable medium having stored thereon instructions for compressing an image, said instructions which, when executed by a processor, cause the processor to:1. divide the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: 1. transform the image set into a set of coefficients using a reversible transform;2. quantize each coefficient of the set of coefficients;and 3. code each quantized coefficient of the set of coefficients in accordance with an entropy code.
  17. 46
    The article of manufacture according to claims 42-45, wherein the image comprises components corresponding to color information.
  18. 49
    An article of manufacture comprising a computer-readable medium having stored thereon instructions for restoring from compressed image data an image having at least one image set comprised of a two-dimensional array of pixels having a number of columns M and a number of rows N, said instructions which, when executed by a processor, cause the processor to:1. decode the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: 1. unquantize the coefficients;2. inverse-transform the unquantized coefficients into an image set using a reversible transform;and 3. combine each image set into the image.
  19. 53
    An article of manufacture comprising a computer-readable medium having stored thereon instructions for compressing and restoring an image, said instructions which, when executed by a processor, cause the processor to:1. compress the image by: 1. dividing the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N;and 2. for each image set: (a) transforming the image set into a set of coefficients using a reversible transform;(b) quantizing each coefficient of the set of coefficients;and (c) coding each quantized coefficient of the set of coefficients in accordance with an entropy code;and 2. restore the image by: 1. decoding the compressed image data into at least one set of coefficients in accordance with an entropy code;2. for each set of coefficients: (a) unquantizing the coefficients: (b) inverse-transforming the unquantized coefficients into an image set using a reversible transform;and 3. combining each image set into the image.
Independent claims19