Document image compression system and method

Claim 2

In a discrete transform system having a transform compressor for compressing document image data arranged as a plurality of pixels, each pixel representing one of a plurality of gray levels, the transform compressor utilizing a plurality of transform coefficients to effect compression, a system for modifying the transform coefficients comprising: means for storing a plurality of modifier matrices, each matrix of said plurality comprising data for altering transform coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; means for estimating a packet size of memory space required to store the document image data for a given document after compression by the discrete transform system; means for supplying a desired target packet size; selection processor means coupled to the means for estimating and coupled to the means for supplying a desired packet size, and operative to select one of said plurality of matrices as a function of a packet size estimate and a function of desired target packet size; said selection processor being operative to select at least one first matrix if the estimated packet size is above the desired target packet size and operative to select at least one second matrix if the estimated packet size is not above the desired target packet size; and transmitting means for transmitting the selected one of said plurality of matrices to said transform compressor for use in altering the plurality of transform coefficients.

Claim 3

The improvement of claim 1 further comprising means for examining each pixel and generating a histogram of all pixels in the document image data; histogram processing means for generating a contrast reduction pixel conversion function and a gray level stretch pixel conversion function in accordance with preselected characteristics of the histogram; and means for combining the contrast reduction and gray level stretch conversion functions and applying a combined conversion function to the document image data and for transmitting converted image data to the means for estimating packet size.

Claim 4

The improvement of claim 2, wherein the contrast reduction pixel conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope less than unity for input pixel gray level values less than a predetermined contrast reduction protection value selected as a function of characteristics of the histogram, and wherein a converted output pixel gray level value is equal to a corresponding input pixel gray level value for input pixel gray level values equal to or greater than the contrast reduction protection value.

Claim 5

The improvement of claim 3, wherein the gray level stretch conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is a blackest value for all input pixel gray level values less than or equal to a predetermined black clip value selected as a function of characteristics of the histogram, a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope greater than unity for input pixel gray level values greater than the black clip value and less than a predetermined white clip value selected as a function of characteristics of the histogram, and a converted output pixel gray level value is a whitest value for all input pixel gray level values greater than or equal to the white clip value.

Claim 6

The improvement of claim 4, wherein the contrast reduction pixel conversion function and the gray level stretch conversion functions are combined and implemented as a look-up table.

Claim 7

The improvement of claim 3, wherein the contrast reduction protection value is a predetermined percentage of a gray level value corresponding to a preselected peak value of the histogram.

Claim 8

The improvement of claim 2, wherein the gray level stretch conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is a blackest value for all input pixel gray level values less than or equal to a predetermined back clip value selected as a function of characteristics of the histogram, a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope greater than unity for input pixel gray level values greater than the black clip value and less than a predetermined white clip value selected as a function of characteristics of the histogram, and a converted output pixel gray level value is a whitest value for all input pixel gray level values greater than or equal to the white clip value.

Claim 9

The improvement of claim 7, wherein the black clip value is determined by comparing a cumulative sum of histogram frequencies to a first preselected threshold value and a white clip value is determined by comparing a cumulative sum of histogram frequencies to a second preselected threshold value.

Claim 10

The improvement of claim 1, wherein the means for estimating comprises processor means for generating a running sum of absolute values of the plurality of transform coefficients.

Claim 11

The improvement of claim 9, wherein the discrete transform comprises a discrete cosine transform as defined by the Joint Photographic Experts Group Of The International Standards Organization.

Claim 12

The improvement of claim 1, wherein the means for estimating comprises a transform compressor utilizing a preselected test matrix of transform coefficient modifiers.

Claim 13

In a discrete transform compression method for compressing document image data arranged as a plurality of pixels, each representing one of a plurality of gray levels, wherein a plurality of transform frequency coefficients corresponding to the pixels are generated by a preselected transform function and the coefficients then quantized by a matrix of quantization values, the improvement comprising, for each document whose image data representation is to be compressed: a) storing a plurality of modifier matrices, each matrix of said plurality comprising data for altering transform frequency coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; b) estimating a packet size of memory space required to store the document image data after compression by the discrete transform technique; c) supplying a desired target packet size; d) selecting one of a plurality of matrices of quantization values, as a function of a packet size estimate and as a function of desired target packet size; e) applying said selected matrix to said transform frequency coefficients.

Claim 14

In a discrete transform compression method for compressing document image data arranged as a plurality of pixels, each representing one of a plurality of gray levels, wherein a plurality of transform frequency coefficients corresponding to the pixels are generated by a preselected transform function and the coefficients then quantized by a matrix of quantization values, the improvement comprising, for each document whose image data representation is to be compressed: a) storing a plurality of modifier matrices, each matrix of said plurality comprising data for altering transform frequency coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; b) estimating a packet size of memory space required to store the document image data after compression by the discrete transform technique; c) supplying a desired target packet size; d) selecting one of a plurality of matrices of quantization values, as a function of a packet size estimate and as a function of desired target packet size; e) applying said selected matrix to said transform frequency coefficients.

Claim 15

The improved method of claim 12, wherein the plurality of matrices are generated from a training set comprising a plurality of typical documents whose image data are to be compressed.

Claim 16

The improved method of claim 12, wherein the selection of the one of the plurality of matrices of quantization values is performed so as to maintain an average packet size of a series of document images within a predefined range of acceptable values.

Claim 17

The improved method of claim 12, further comprising preliminary steps of: (i) generating a histogram of all pixels in the document image data; (ii) generating a contrast reduction pixel conversion function and a gray level stretch conversion function in accordance with preselected characteristics of the histogram; and (iii) combining the contrast reduction and gray level stretch conversion functions and applying a combined conversion function to the document image data prior to estimating the packet size.

Claim 18

The image method of claim 15, wherein the contrast reduction pixel conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope less than unity for input pixel gray level values less than a predetermined contrast reduction protection value selected as a function of characteristics of the histogram, and wherein a converted output pixel gray level value is equal to a corresponding input pixel gray level value for input pixel gray level values equal to or greater than the contrast reduction protection value.

Claim 19

The improved method of claim 16, wherein the gray level stretch conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is a blackest value for all input pixel gray level values less than or equal to a predetermined black clip value selected as a function of characteristics of the histogram, a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope greater than unity for input pixel gray level values greater than the black clip value and less than a predetermined white clip value selected as a function of characteristics of the histogram, and a converted output pixel gray level value is a whitest value for all input pixel gray level values greater than or equal to the white clip value.

Claim 20

The improved method of claim 17, wherein the contrast reduction pixel conversion function and the gray level stretch conversion function are combined and implemented as a look-up table.

Claim 21

The improved method of claim 16, wherein the contrast reduction protection value is a predetermined percentage of a gray level value corresponding to a preselected peak value of the histogram.

Claim 22

The improved method of claim 19, wherein the slope of the linear function for pixel gray level values less than the contrast reduction protection value is empirically determined for a test set of documents of a class of documents to be compressed.

Claim 23

The improved method of claim 15, wherein the gray level stretch conversion function comprises a piece-wise linear function wherein a converted output pixel gray level value is a blackest value for all input pixel gray levels less than or equal to a predetermined black clip value selected as a function of characteristics of the histogram, a converted output pixel gray level value is related to a corresponding input pixel gray level value by a linear function having a slope greater than unity for input pixel gray level values greater than the black clip value and less than a predetermined white clip value selected as a function of characteristics of the histogram, and a converted output pixel gray level value is a whitest value for all input pixel gray level values greater than or equal to the white clip value.

Claim 24

The improved method of claim 21, wherein the black clip value is determined by comparing a cumulative sum of histogram frequencies to a first preselected threshold value and the white clip value is determined by comparing a cumulative sum of histogram frequencies to a second preselected threshold value.

Claim 25

The improved method of claim 12, wherein a packet size is estimated by generating a running sum of absolute values of the transform frequency coefficients.

Claim 26

The improved method of claim 12, wherein a packet size is estimated by actually compressing the document image data with the discrete transform compression method utilizing a preselected test matrix of quantization values.

Claim 27

The improved method of claim 12, wherein step b) comprises: 1) compressing the document image data utilizing a predetermined reference quantization matrix to obtain a reference document image packet size; 2) determining a target document image packet size utilizing a preselected transfer function applied to the reference document image packet size; 3) calculating, for each of the plurality of matrices of quantization values, an estimated document image packet size as a function of a number of pixels per document and the reference document image packet size; and 4) selecting a matrix of quantization values which yields an estimated document image packet size closest to, but not exceeding, the target document image packet size.

Claim 28

The improved method of claim 12, wherein the discrete transform comprises a discrete cosine transform as defined by the Joint Photographic Experts Group Of The International Standards Organization.

Claim 29

In a discrete transform system using a transform compressor for compressing document image data arranged as a plurality of pixels, each representing one of a plurality of gray levels, the transform including a plurality of transform coefficients, the improvement comprising: means for examining each pixel and generating a histogram of all pixels in the document image data; histogram processing means for generating a contrast reduction pixel conversion function and a gray level stretch pixel conversion function in accordance with preselected characteristics of the histogram; means for applying the contrast reduction and gray level stretch conversion functions to the document image data; means for storing a plurality of matrices of transform coefficient modifiers, each matrix of said plurality comprising data for altering transform coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; means for estimating a packet size of memory space required to store the document image data for a given document after compression by the discrete transform technique, the means for estimating coupled for receipt of the converted image data from the histogram processing means; means for supplying a desired target packet size; selection processor means coupled to the means for estimating and coupled to the means for supplying a desired packet size and operative to select at least a first one of said plurality of matrices of transform coefficient modifiers if the estimated packet size is above the desired target packet size and operative to select at least a second one of said plurality of matrices of transform coefficient modifiers if the estimated packet size is not above the desired target packet size; and transmitting means for transmitting the selected one of said plurality of matrices to said transform compressor for use in altering the plurality of transform coefficients.

Claim 30

In a discrete transform system using a transform compressor for compressing document image data arranged as a plurality of pixels, each representing one of a plurality of gray levels, the transform including a plurality of transform coefficients, the improvement comprising: means for examining each pixel and generating a histogram of all pixels in the document image data; histogram processing means for generating a contrast reduction pixel conversion function and a gray level stretch pixel conversion function in accordance with preselected characteristics of the histogram; means for applying the contrast reduction and gray level stretch conversion functions to the document image data; means for storing a plurality of matrices of transform coefficient modifiers, each matrix of said plurality comprising data for altering transform coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; means for estimating a packet size of memory space required to store the document image data for a given document after compression by the discrete transform technique, the means for estimating coupled for receipt of the converted image data from the histogram processing means; means for supplying a desired target packet size; selection processor means coupled to the means for estimating and coupled to the means for supplying a desired packet size and operative to select at least a first one of said plurality of matrices of transform coefficient modifiers if the estimated packet size is above the desired target packet size and operative to select at least a second one of said plurality of matrices of transform coefficient modifiers if the estimated packet size is not above the desired target packet size; and transmitting means for transmitting the selected one of said plurality of matrices to said transform compressor for use in altering the plurality of transform coefficients.

Claim 31

In a discrete transform compression method for compressing document image data arranged as a plurality of pixels each representing one of a plurality of gray levels, wherein a plurality of transform frequency coefficients corresponding to the pixels are generated by a preselected transform function and the coefficients then quantized by a matrix of quantization values, the improvement comprising, for each document whose image data representation is to be compressed, a) generating a histogram of all pixels in the document image data; b) generating a contrast reduction pixel conversion function and a gray level stretch conversion function in accordance with preselected characteristics of the histogram; c) applying the contrast reduction and gray level stretch conversion functions to the document image data; d) storing a plurality of modifier matrices, each matrix of said plurality comprising data for altering transform frequency coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; e) supplying a desired target packet size; f) estimating a packet size of memory space required to store the document image data after compression by the discrete transform technique; g) selecting one of a plurality of matrices of quantization values as a function of a packet size estimate and as a function of desired target packet size; h) applying said selected matrix to said transform frequency coefficients.

Claim 32

In a discrete transform compression method for compressing document image data arranged as a plurality of pixels each representing one of a plurality of gray levels, wherein a plurality of transform frequency coefficients corresponding to the pixels are generated by a preselected transform function and the coefficients then quantized by a matrix of quantization values, the improvement comprising, for each document whose image data representation is to be compressed, a) generating a histogram of all pixels in the document image data; b) generating a contrast reduction pixel conversion function and a gray level stretch conversion function in accordance with preselected characteristics of the histogram; c) applying the contrast reduction and gray level stretch conversion functions to the document image data; d) storing a plurality of modifier matrices, each matrix of said plurality comprising data for altering transform frequency coefficients, the data of each matrix being preselected to produce a different packet size for a given document image; e) supplying a desired target packet size; f) estimating a packet size of memory space required to store the document image data after compression by the discrete transform technique; g) selecting one of a plurality of matrices of quantization values as a function of a packet size estimate and as a function of desired target packet size; h) applying said selected matrix to said transform frequency coefficients.