US5455874A — Continuous-tone image compression

Claim 1

Independent Claim 82 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 2

Dependent Claim 82 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 3

Dependent Claim 19 words

The apparatus of claim 1 wherein said lapped orthogonal transform uses only multiplier values which are powers of 2.

Claim 4

Dependent Claim 19 words

The apparatus of claim 2 wherein said lapped orthogonal transform uses multiplier values of ±1, ±2, ±4, and ±8.

Claim 5

Dependent Claim 35 words

The apparatus of claim 3 wherein said lapped orthogonal transform is based on successive transformations of blocks of data and includes inter-block and intra-block computations, and wherein transformations of blocks reuse inter-block and intra-block computations.

Claim 6

Dependent Claim 26 words

The apparatus of claim 1 further comprising factoring the coefficients into at least two groups, and applying the quantizing and coding independently to the respective groups.

Claim 7

Dependent Claim 11 words

The apparatus of claim 1 wherein said coding comprises entropy coding.

Claim 8

Dependent Claim 12 words

The apparatus of claim 6 wherein said entropy coding comprises arithmetic coding.

Claim 9

Dependent Claim 13 words

The apparatus of claim 7 wherein said arithmetic coding is conditioned on contexts.

Claim 10

Dependent Claim 91 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which computes all transform coefficients by means only of bit shifts, negations, and adds.

Claim 11

Dependent Claim 91 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which computes all transform coefficients by means only of bit shifts, negations, and adds.

Claim 12

Dependent Claim 87 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which uses only multiplier values which are powers of 2.

Claim 13

Dependent Claim 87 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which uses only multiplier values which are powers of 2.

Claim 14

Dependent Claim 19 words

The apparatus of claim 10 wherein said lapped orthogonal transform uses multiplier values of ±1, ±2, ±4, and ±8.

Claim 15

Dependent Claim 97 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which is based on successive transformations of blocks of data, and wherein transformations of blocks reuse inter-block and/or intra-block computations.

Claim 16

Dependent Claim 97 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming the original data file to a transform file of coefficients, means for factoring the coefficients into at least two groups, and a quantizer/coder for vector quantizing each of said groups of transform coefficients separately after factoring, and for coding the groups of transform coefficients separately and wherein said transform comprises a lapped orthogonal transform which is based on successive transformations of blocks of data, and wherein transformations of blocks reuse inter-block and/or intra-block computations.

Claim 17

Dependent Claim 142 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming, by a lapped orthogonal transform which uses only multiplier values of ±1, ±2, ±4, and ±8, the original data file to generate a transform file of coefficients, means for factoring the coefficients into at least two groups, a quantizer for quantizing independently the respective groups of transform coefficients to generate corresponding groups of quantized values, and a coder for arithmetic coding independently the groups of quantized values, based on contexts, to generate the compressed data file, the lapped orthogonal transform being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds, the lapped orthogonal transform being based on successive transformations of blocks of data and wherein transformations of blocks reuse inter-block and/or intra-block computations.

Claim 18

Dependent Claim 142 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a transformer for transforming, by a lapped orthogonal transform which uses only multiplier values of ±1, ±2, ±4, and ±8, the original data file to generate a transform file of coefficients, means for factoring the coefficients into at least two groups, a quantizer for quantizing independently the respective groups of transform coefficients to generate corresponding groups of quantized values, and a coder for arithmetic coding independently the groups of quantized values, based on contexts, to generate the compressed data file, the lapped orthogonal transform being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds, the lapped orthogonal transform being based on successive transformations of blocks of data and wherein transformations of blocks reuse inter-block and/or intra-block computations.

Claim 19

Dependent Claim 95 words

Apparatus for processing a continuous-tone image for later reconstruction, comprising means for acquiring from the image an original data file of digital data values representing continuous-tone information in the image, a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the lapped orthogonal transform being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 20

Dependent Claim 95 words

Apparatus for processing a continuous-tone image for later reconstruction, comprising means for acquiring from the image an original data file of digital data values representing continuous-tone information in the image, a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the lapped orthogonal transform being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 21

Dependent Claim 155 words

Apparatus for reconstructing an original data file used to represent a continuous-tone image from a compressed data file of the kind generated by a device having a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds, the apparatus comprising a decoder for decoding the compressed data file to generate the quantized values, means for deriving the transform coefficients from the quantized values, a transformer for inverse transforming by an inverse lapped orthogonal transform the compressed data file to generate the transform file of coefficients, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 22

Dependent Claim 155 words

Apparatus for reconstructing an original data file used to represent a continuous-tone image from a compressed data file of the kind generated by a device having a transformer for transforming by a lapped orthogonal transform the original data file to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients to generate quantized values, and a coder for coding the quantized values to generate the compressed data file, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds, the apparatus comprising a decoder for decoding the compressed data file to generate the quantized values, means for deriving the transform coefficients from the quantized values, a transformer for inverse transforming by an inverse lapped orthogonal transform the compressed data file to generate the transform file of coefficients, the transformer being arranged to compute all transform coefficients by means only of bit shifts, negations, and adds.

Claim 23

Dependent Claim 73 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a lapped orthogonal transform device for transforming the original file of data to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients, and a coder for encoding the quantized values to generate the compressed data file, the lapped orthogonal transform device consisting of bit shifting, negation, and addition computational elements.

Claim 24

Dependent Claim 73 words

Apparatus for generating a compressed data file from an original data file used to represent a continuous-tone image, comprising a lapped orthogonal transform device for transforming the original file of data to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients, and a coder for encoding the quantized values to generate the compressed data file, the lapped orthogonal transform device consisting of bit shifting, negation, and addition computational elements.

Claim 25

Dependent Claim 88 words

Apparatus for processing a continuous-tone image for later reconstruction, comprising a camera or scanner for acquiring from the image an original data file of digital data values representing continuous-tone information in the image, a transform device for transforming by a lapped orthogonal transform the original file of data to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients, and an encoder for coding the quantized values to generate the compressed data file, the transform device consisting of bit shifting, negation, and addition computational elements.

Claim 26

Dependent Claim 88 words

Apparatus for processing a continuous-tone image for later reconstruction, comprising a camera or scanner for acquiring from the image an original data file of digital data values representing continuous-tone information in the image, a transform device for transforming by a lapped orthogonal transform the original file of data to generate a transform file of coefficients, a quantizer for quantizing the transform coefficients, and an encoder for coding the quantized values to generate the compressed data file, the transform device consisting of bit shifting, negation, and addition computational elements.

Claim 27

Dependent Claim 110 words

Apparatus for converting an RGB pixel data file used to represent a color image expressed in RGB color space points, wherein each RGB point includes R, G, and B components, to a YUV pixel data file used to represent said color image in YUV color space points, wherein each YUV point includes Y, U, and V signal components, for subsequent processing in YUV format comprising means for representing each R, G, and B component as a non-negative 8-bit integer, and a converter for converting said R, G, and B components to Y, U, and V components using only bit shifts and additions and no more than a single division operation.

Claim 28

Dependent Claim 110 words

Apparatus for converting an RGB pixel data file used to represent a color image expressed in RGB color space points, wherein each RGB point includes R, G, and B components, to a YUV pixel data file used to represent said color image in YUV color space points, wherein each YUV point includes Y, U, and V signal components, for subsequent processing in YUV format comprising means for representing each R, G, and B component as a non-negative 8-bit integer, and a converter for converting said R, G, and B components to Y, U, and V components using only bit shifts and additions and no more than a single division operation.

Claim 29

Dependent Claim 47 words

The apparatus of claim 18 wherein said converting of said R, G, and B components to said Y, U, and V components is done in accordance with the following relationships between said R, G, and B components and said Y, U, and V components: Y=(R+4G+B+3)/6 U=(R-2G+B+2)/4+128 V=(R-B+1)/2+128

Claim 30

Dependent Claim 43 words

The apparatus of claim 18 further comprising reconverting the YUV pixel data file to an RGB pixel data file corresponding to said color image expressed in RGB color space points by performing only multiplications, additions, shifts and no more than a single division.

Claim 31

Dependent Claim 35 words

The apparatus of claim 20 wherein said reconversion is done in accordance with the following relationships between said R, G, and B components and said Y, U, and V components: U'=[4(U-128)+1]/3 V'=V-128 R=Y+U'+V' G=Y-U'/2 B=Y+U'-V.'

Claim 32

Dependent Claim 86 words

Apparatus for generating a set of centroids to serve as a codebook for use in vector quantization of data corresponding to a continuous-tone image comprising means for applying PNN and LBG procedures to create centroids, a counter for counting the number of vectors which quantize to each centroid, an updater for updating the centroids by reapplying the PNN and LBG procedures to input data which includes the previously generated centroids each applied with a weight based on the number of vectors which quantized to that centroid.

Claim 33

Dependent Claim 86 words

Apparatus for generating a set of centroids to serve as a codebook for use in vector quantization of data corresponding to a continuous-tone image comprising means for applying PNN and LBG procedures to create centroids, a counter for counting the number of vectors which quantize to each centroid, an updater for updating the centroids by reapplying the PNN and LBG procedures to input data which includes the previously generated centroids each applied with a weight based on the number of vectors which quantized to that centroid.

Claim 34

Dependent Claim 16 words

The apparatus of claim 22 wherein said updating step results in a reduced number of centroids.

Claim 35

Independent Claim 188 words

A method of processing a continuous-tone image comprising using a camera or scanner to derive digital data signals representing the image, temporarily storing the digital data signals in a tangible storage medium as an original data file, retrieving the original data file from the storage medium, transforming, by a lapped orthogonal transform using only bit shifts, negations, and adds, the original data file to generate a transform file of coefficients, quantizing the transform coefficients to generate quantized data values, coding the quantized values to generate a compressed data file, storing the compressed data file on a tangible storage medium using digital signals or transmitting the compressed data file on a tangible communication medium using digital signals, receiving or retrieving the compressed data file, decoding the compressed data file to generate quantized values, deriving transform coefficients from the quantized values, inverse transforming by an inverse lapped orthogonal transform using only bit shifts, negations, and adds, the compressed data file to generate a transform file of coefficients, reconstructing the original data file from the transform file of coefficients, and using a printing or display device to regenerate the continuous-tone image.

Claim 36

Independent Claim 188 words

A method of processing a continuous-tone image comprising using a camera or scanner to derive digital data signals representing the image, temporarily storing the digital data signals in a tangible storage medium as an original data file, retrieving the original data file from the storage medium, transforming, by a lapped orthogonal transform using only bit shifts, negations, and adds, the original data file to generate a transform file of coefficients, quantizing the transform coefficients to generate quantized data values, coding the quantized values to generate a compressed data file, storing the compressed data file on a tangible storage medium using digital signals or transmitting the compressed data file on a tangible communication medium using digital signals, receiving or retrieving the compressed data file, decoding the compressed data file to generate quantized values, deriving transform coefficients from the quantized values, inverse transforming by an inverse lapped orthogonal transform using only bit shifts, negations, and adds, the compressed data file to generate a transform file of coefficients, reconstructing the original data file from the transform file of coefficients, and using a printing or display device to regenerate the continuous-tone image.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-10-02	1999-04-03	1999-10-03	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-10-02	2003-04-03	2003-10-03	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-10-02	2007-04-03	2007-10-03	$7700.00	Window Closed / Lapsed

Continuous-tone image compression

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag