[15
`United States Patent
`5,850,484
`[11] Patent Number:
`[45] Date of Patent: Dec. 15, 1998
`Beretta et al.
`
`
`
`US005850484A
`
`EuropeanPat. Off.
`........ GOOF 15/64
`9/1993
`0593159A2
`[54] TEXT AND IMAGE SHARPENINGOFJPEG
`
`COMPRESSED IMAGESIN THE
`. HO4N 7/30
`Japan .........
`3/1995
`07087491
`
`07143343—O/199S Japan vesescssersesserseesesseeseess HO4N 1/41
`FREQUENCY DOMAIN
`OTHER PUBLICATIONS
`
`[75]
`
`Inventors: Giordano Beretta, Palo Alto; Vasudev
`Bhaskaran, Mountain View;
`Konstantinos Konstantinides, San
`Jose, all of Calif.
`
`[73] Assignee: Hewlett-Packard Co., Palo Alto, Calif.
`
`[21] Appl. No.: 940,695
`
`[22]
`
`Filed:
`
`Sep. 30, 1997
`
`Related U.S. Application Data
`
`[63] Continuation of Ser. No. 411,369, Mar. 27, 1995, aban-
`doned.
`
`[58]
`
`[SU]
`Tmt, Che ieee ecccccecccsssseeecsscssennncescenuee G06K 9/36
`
`«+ 382/250; 382/251; 382/239;
`358/432; 348/404
`Field of Search oe 382/298, 233,
`382/251, 244, 232, 253, 250, 274, 252,
`238, 236, 166, 280, 270; 358/427, 426,
`432, 261.3, 448, 261.1, 433, 261.2, 430,
`458; 348/404, 432, 405, 433, 403, 391,
`384, 422, 393, 430, 394, 409, 395, 390
`
`[S6]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`. 358/432
`4,776,030 10/1988
`358/133
`4,780,761
`10/1988
`
`5,063,608
`11/1991 Siegel...........
`--. 382/56
`
`5,073,820 12/1991 Nakagawaet al.
`358/133
`7/1994 Ligtenberg ...
`-. 382/56
`§,333,212
`
`. 348/405
`5,410,352
`4/1995 Watanabe .
`- 358/432
`5,465,164
`11/1995 Sugiura ....
`
`...cecceceseeeseeseseeeeees 364/514 R
`5,488,570
`1/1996 Agarwal
`FOREIGN PATENT DOCUMENTS
`
`0444884A2
`0513520A2
`
`2/1991
`4/1992
`
`European Pat. Off.
`European Pat. Off.
`
`.
`
`....... HO4N 7/133
`
`G. B. Beretta et al., “Experience with the New Color
`Facsimile Standard”, ISCC Annual Meeting, Apr. 23-25,
`1995, pp. 1-7.
`Albert J. Ahumada, Jr. et al., “Luminance—Model—Based
`DCT Quantization for Color Image Comression”, Human
`Vision, Visual Processing, and Digital Display III, 1666,
`365-374, SPIE, 1992.
`
`(List continued on next page.)
`
`Primary Examiner—Jose L. Couso
`Assistant Examiner—Matthew C. Bella
`
`[57]
`
`ABSTRACT
`
`The text and image enhancing technique according to the
`invention is integrated into the decoding or inverse quanti-
`zationstep that is necessarily required by the JPEG standard.
`The invention integrates the two by using two different
`quantization tables: a first quantization table (Q,) for use in
`quantizing the image data during the compression step and
`a second quantization table used during the decode or
`inverse quantization during the decompression process. The
`second quantization table Q,, is related to the first quanti-
`zation table according to a predetermined function of the
`energy in a reference image and the energy in a scanned
`image. The energy of the reference image lost during the
`scanning process, as represented by the energy in the
`scanned image, is restored during the decompression pro-
`cess by appropriately scaling the second quantization table
`according to the predetermined function. The difference
`between the two tables,
`in particular the ratio of the two
`tables, determines the amount of image enhancing that is
`done in the two steps. By integrating the image enhancing
`and inverse quantization steps the method does not require
`any additional computations than already required for the
`compression and decompression processes.
`
`35 Claims, 7 Drawing Sheets
`
`GENERATE
`SELECT
`
`SCANNED
`REFERENCE
`
`
`IMAGE
`IMAGE
`
`70
`DETERMINE
`DETERMINE
`AVERAGE
`AVERAGE
`
`
`
`ENERGY
`ENERGY
`
`
`
`
`COMPUTE
`SCALING
`
`MATRIX
`
`OLYMPUS EX. 1014 - 1/18
`
`OLYMPUS EX. 1014 - 1/18
`
`

`

`
`5,850,484
`Page 2
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Kenneth R. Alexanderet al., “Spatial-Frequency Character-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`istics of Letters Identification”, J. Opt. Soc. Am. A, 11,9,
`2375-2382, 1994.
`
`
`Wen-HsiungChenet al., “Adaptive Coding of Monochrome
`
`
`
`
`
`
`
`and Color Images”, [EEE ‘lransactions on Communications,
`
`
`
`
`
`
`COM-25, 1285-1292, 1977.
`
`
`
`Bowonkoon Chitprasert et al., Human Visual Weighted
`
`
`
`
`
`
`Progressive Image Transmission,
`IEEE Transactions on
`
`
`
`
`
`Communications, COM—38, 7, 1040-1044, 1990.
`
`
`
`
`
`R. J. Clarke, Spectral Responses of the Discrete Cosine and
`
`
`
`
`
`
`
`
`
`
`Walsh-Hadamard Transforms, TEE Proc., 130, Part F,
`
`
`
`
`
`
`
`309-313, 1983.
`
`
`K.K. De Valois et al., Color—Luminance Masking Interac-
`
`
`
`
`
`
`
`tions, Seeing Contour and Colour, J.J. Kulikowski, C.M.
`
`
`
`
`
`
`
`
`Dickinson and I.J. Murray Editors, Pergamon Press, Oxford,
`
`
`
`
`
`
`
`
`1989.
`
`J. Raymond Edinger, Jr, “A Measure for Stairstepping in
`
`
`
`
`
`
`
`
`Digitized Text that Correlates with the Subjective Impres-
`
`
`
`
`
`
`
`sion of Quality”, IS&T’s Tenth International Congress on
`
`
`
`
`
`
`
`Advances in Non-ImpactPrinting Technologies, 552-558,
`
`
`
`
`
`1994.
`
`Yasushi Hoshino et al., Applicability of a Standardized
`
`
`
`
`
`
`
`Discrete Cosine Transform Coding Method to Character
`
`
`
`
`
`
`Images, J. Electronic Imaging, 1, 3, 322-327, 1992.
`
`
`
`
`
`
`
`
`Chansik Hwang et al., Human Visual System Weighted
`
`
`
`
`
`
`
`Progresscive Image ‘Iransmission Using Lapped Orthogonal
`
`
`
`
`
`Transform/Classified Vector Quantization, Optical Engi-
`
`
`
`
`neering, 32, 7, 1524-1530, 1993.
`
`
`
`
`
`International Organization for Standardization: Information
`
`
`
`
`Technology—Digital Compression and Coding of Continu-
`
`
`
`
`
`ous—Tone Still Images—Part 1: Requirements and Guide-
`
`
`
`
`
`
`lines, ISOMAEC IS 10918-1, Oct. 20, 1992.
`
`
`
`
`
`
`
`International Telecommunication Union: Amendments to
`
`
`
`
`
`ITU-T Rec. T.30 for Enabling Continuous—Tone Colour and
`
`
`
`
`
`
`
`
`Gray—Scale Modes for Group 3, COM 8-43-E, Question
`
`
`
`
`
`
`
`
`5/8, Mar. 1994.
`
`
`
`International Telecommunication Union: Amendments to
`
`
`
`
`
`ITU-T Rec. T-4 for Enabling Continuous—Time Colour and
`
`
`
`
`
`
`
`
`
`Gray—Scale Modes for Group 3, COM 8-44-E, Question
`
`
`
`
`
`
`
`
`5/8, Mar. 1994.
`
`
`
`Gordon E. Legge, “Reading: Effects of Contrast and Spatial
`
`
`
`
`
`
`
`
`Frequency”, Applicd Vision, OSA ‘lechnical Digest Serics,
`
`
`
`
`
`
`16, 90-93, 1989.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Gordon E. Leggeet al., Contrast Masking in HumanVision,
`
`
`
`
`
`
`
`
`
`J. Opt. Soc. Am., 70,12,1458-1471, 1980.
`
`
`
`
`
`
`David T.. Mclaren et al., “Removal of Subjective Redun-
`
`
`
`
`
`
`
`
`dancy from DCT-Coded Images”, IEE Proceedings-I, 138,
`
`
`
`
`
`
`5, 345-350, 1991.
`
`
`
`“Color-Facsimile
`System for
`al,
`I. Miyagawa
`et
`
`
`
`
`
`
`
`Mixed—Color Documents”, SID 94 Digest, 887-890, 1994.
`
`
`
`
`
`
`
`Kathy T. Mullen, “The Contrast Sensitivity of Human
`
`
`
`
`
`
`
`
`Colour Vision to Red—Green and Blue—Yellow Chromatic
`
`
`
`
`
`
`
`Gratings”, J. Physiol., 359, 381-400, 1985.
`
`
`
`
`
`
`Daivd H. Parish et al., “Object Spatial Frequencies, Retinal
`
`
`
`
`
`
`
`
`Spatial Frequencies, Noise, and the Efficiency of Letter
`
`
`
`
`
`
`
`Discrimination”, Vision Res., 31, 7/8, 1399-1415, 1991.
`
`
`
`
`
`
`
`Denis G. Pelli et al., “Visual Factors in Letter Identifica-
`
`
`
`
`
`
`
`
`
`tion’, IS&'l’s 47th Annual Conferenec/ICPS,p. 411, 1994.
`
`
`
`
`
`
`
`
`Heidi A. Peterson et al., An Improved Detection Model for
`
`
`
`
`
`
`
`
`
`
`DCICocfficicnt Quantization, Human Vision, Visual Pro-
`
`
`
`
`
`
`cessing, and Digital Display TV, 1913, 191-201, SPIE, 1993.
`
`
`
`
`
`
`
`
`
`L.
`de Queiroz
`al,
`“Human Visual
`Ricardo
`ct
`
`
`
`
`
`
`
`
`Sensitivity-Weighted Progressive
`Image Transmission
`
`
`
`
`Using the Lapped Orthogonal Transform”, J. Electronic
`
`
`
`
`
`
`
`Imaging, 1, 3, 328-338, 1992.
`
`
`
`
`
`Ricardo L. de Queiroz et al., Modulated Lapped Orthogonal
`
`
`
`
`
`
`
`
`
`Transforms in Image Coding, Digital Video Compression on
`
`
`
`
`
`
`
`
`Personal Computers: Algorithms and Technologies, 2187,
`
`
`
`
`
`
`80-91, SPIE, 1993.
`
`
`
`Robert J. Satranck ct al., “A Pereeptually ‘Tuned Sub—Band
`
`
`
`
`
`
`
`
`Image Coder with Image Dependent Quantization and
`
`
`
`
`
`
`Post-Quantization Data Compression”, Proc. ICASSP 89, 3,
`
`
`
`
`
`
`1945-1948, 1989.
`
`
`Robert J. Safranek, JPEG Compliant Encoder Utilizing
`
`
`
`
`
`
`Perceptually Based Quantization, Human Vision, Visual
`
`
`
`
`
`Processing, and Digital Display V, 1913, 117-126, SPIE,
`
`
`
`
`
`
`
`1993.
`
`Andrew B. Watson, DCT Quantization Matrices Visually
`
`
`
`
`
`
`Optimized for Individual Images, Human Vision, Visual
`
`
`
`
`
`
`Processing, and Digital Display IV, 1913, 202-216, SPIE,
`
`
`
`
`
`
`
`1993.
`
`
`
`
`
`
`
`
`
`
`Andrew B. Watsonet al., Discrete Cosine Transform (DCT)
`Basis Function Visibility: Effects of Viewing Distance and
`
`
`
`
`
`
`
`
`Contrast Masking, Human Vision, Visual Processing, and
`
`
`
`
`
`
`
`Digital Display
`2179,
`99-108,
`1994.
`V,
`SPIE,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OLYMPUS EX.1014 - 2/18
`
`HUAWEI EX. 1014 - 2/18
`
`OLYMPUS EX. 1014 - 2/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 1 of 7
`
`5,850,484
`
`SOURCE IMAGE
`
`RASTER TO
`BLOCK
`
`TRANSLATION
`
`FIG. 1
`(PRIOR ART)
`
` QUANTIZATION
`
`Q TABLES
`
`24
`
`30
`
`DATA
`
`
`
`
`
`
`
` ENTROPY
`
`CODING
`
` H TABLES
`
`COMPRESSED
`
`IMAGE DATA
`
`OLYMPUS EX.1014 - 3/18
`
`OLYMPUS EX. 1014 - 3/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 2 of 7
`
`S3a1gdvVLlO
`
`SaTaVLH
`
`SY30V3SH
`
`OFdrS3AT1dVLH
`
`SATEVLO
`
`5,850,484
`
`(LUVHOrdd)6VIA
`
`GSSSsaY¥dWoo
`
`ADVI
`
`VLVd
`
`NOISSSYdWOODadr
`
`ANISNA
`
`OLYMPUS EX.1014 - 4/18
`
`OLYMPUS EX. 1014 - 4/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 3 of 7
`
`5,850,484
`
`COMPRESSED
`
`IMAGE DATA
`
`
`HEADER
`EXTRACTION
`
`
`ENTROPY
`DECODING
`
`
`H TABLES
`
`INVERSE
`QUANTIZATION
`
`OQ TABLES
`
`
`
`
`FIG. 3
`(PRIOR ART)
`
`
`
`
`
`
`
`
`BLOCK TO
`
`RASTER
`TRANSLATION
`
`SOURCE IMAGE
`
`DATA
`
`OLYMPUS EX. 1014 - 5/18
`
`OLYMPUS EX. 1014 - 5/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 4 of 7
`
`5,850,484
`
`68
`64
`
`
`SELECT
`GENERATE
`
`REFERENCE
`SCANNED
`
`
`IMAGE
`
`IMAGE
`
`70
`
`
`
`
`
`
`
` DETERMINE
`DETERMINE
`
`AVERAGE
`AVERAGE
`
`
`ENERGY
`
`ENERGY
`
`
`
`
`
`
`COMPUTE
`SCALING
`
`MATRIX
`
`Q TABLE
`
`SCALE
`
`
`FIG. 4
`
`OLYMPUS EX. 1014 - 6/18
`
`OLYMPUS EX. 1014 - 6/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 5 of 7
`
`5,850,484
`
`98
`
`GDI
`
`Qs1Vv9oS
`
`Sa1dvVLO
`
`YAIVOS
`
`€8c8
`
`88
`
`SAdr
`
`SATEaVLOG3a1VOS
`
`SaT1adVlH 06
`DSAdr c6
` SYsd0V3SH
`SaTaV1LHSa1dvlO
`
`QasssayddWoo
`
`ADVI
`
`VLVd
`
`NOISSSYdWOD
`
`ANISNA
`
`OLYMPUS EX. 1014 - 7/18
`
`OLYMPUS EX. 1014 - 7/18
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`Sheet 6 of 7
`
`5,850,484
`
`COMPRESSED
`IMAGE DATA
`
`HEADER
`
`ENTROPY
`DECODING
`
`EXTRACTION
`
`100
`
`
`H TABLE
`
`SCALER
`
`SCALED
`
`Q TABLE
`
`102
`
`104
`
`INVERSE
`QUANTIZATION
`
`
`
`
`
`
`
`105
`
`106
`
`BLOCK TO
`RASTER
`
`TRANSLATION
`
`FIG. 6
`
`SOURCE IMAGE
`
`DATA
`
`OLYMPUS EX. 1014 - 8/18
`
`OLYMPUS EX. 1014 - 8/18
`
`

`

`U.S. Patent
`
`Dec. 15, 1998
`
`5,850,484
`
`IMAGE DOCUMENT
`
`REPRODUCED IMAGE
`
`SCANNER
`
`PRINTER
`
`CORRECTIONS &
`TRANS-
`
`FORMATIONS
`
`ENGINE
`
`CORRECTIONS &
`TRANS-
`FORMATIONS
`ENGINE
`
`JPEG
`COMPRESSION
`ENGINE
`
`JPEG
`DECOMPRESSION
`ENGINE
`
` Sheet 7 of 7
`
`G3/G4
`ENCAPSULATION
`ENGINE
`
`G3/G4
`
`DECODING
`ENGINE
`
`TRANSMISSION
`
`MEANS
`
`RECEIVING
`
`MEANS
`
`COMPRESSED
`IMAGE DATA
`
`COMPRESSED
`IMAGE DATA
`
`FIG. 7
`
`"4
`
`OLYMPUS EX. 1014 - 9/18
`
`OLYMPUS EX. 1014 - 9/18
`
`

`

`5,850,484
`
`
`
`
`2
`(2D) “spatial
`basis vectors are unique 2-dimensional
`
`
`
`
`
`
`
`waveforms,” which are the fundamental units in the DCT
`
`
`
`
`
`
`
`
`
`space. These basis vectors can be intuitively thought
`to
`
`
`
`
`
`
`
`
`
`represent unique images, wherein any source image can be
`
`
`
`
`
`
`
`
`
`decomposed into a weighted sum of these unique images.
`
`
`
`
`
`
`
`
`
`The discrete cosine transformer uses the forward discrete
`
`
`
`
`
`
`
`
`cosine (FDCT) function as shown below, hence the name.
`
`
`
`
`
`
`
`
`
`
`77
`1
`K=— cc] =
`=z sey):
`
`CH) of 33 @y)
`
`YWAMN=z
`
`
`
`10
`
`os
`
`
`
`(2x + 1k cos 2y + Tyla
`16
`16
`
`
`
`
`
`
`
`
`
`
`
`
`
`1
`TEXT AND IMAGE SHARPENING OF JPEG
`
`
`
`
`
`COMPRESSED IMAGESIN THE
`
`
`
`
`FREQUENCY DOMAIN
`
`
`CROSS REFERENCE TO RELATED
`
`
`
`APPLICATION
`
`
`
`
`
`
`
`This is a continuation of application Ser. No. 08/411,369
`
`
`
`
`
`
`
`
`filed on Mar. 27, 1995, now abandoned.
`
`
`
`
`
`
`
`RELATED APPLICATION DATA
`
`
`
`
`
`
`
`This application incorporates subject matter disclosed in
`
`
`
`
`
`
`commonly-assigned application entitled METHOD FOR
`
`
`
`
`SELECTING JPEG QUANTIZATION TABLES FOR
`
`
`
`
`LOW BANDWIDTH APPLICATIONS, Ser. No. 08/935,
`
`
`
`
`
`517, filed on even date herewith.
`
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘This invention relates to data compression using the JPEG
`
`
`
`
`
`
`
`
`
`compression standard for continuous-tonestill images, both *
`
`
`
`
`
`
`
`grayscale and color.
`
`
`
`A committee known as “JPEG,” which stands for “Joint
`
`
`
`
`
`
`
`
`
`Photographic Experts Group,”has establisheda standard for
`
`
`
`
`
`
`
`compressing continuous-tone still images, both grayscale
`
`
`
`
`
`
`and color. This standard represents a compromise between
`
`
`
`
`
`
`
`
`reproducible image quality and compressionrate. To achieve
`
`
`
`
`
`
`
`
`acceptable compressionrates, which refersto the ratio of the
`
`
`
`
`
`
`
`
`
`
`uncompressed image to the compressed image, the JPEG
`
`
`
`
`
`
`
`
`standard adopted a lossy compression technique. The lossy
`
`
`
`
`
`
`
`
`compression technique was required given the inordinate
`
`
`
`
`
`
`
`amount of data needed to represent a color image, on the
`
`
`
`
`
`
`
`
`
`
`
`order of 10 megabytes for a 200 dots per inch (DPI)
`
`
`
`
`
`
`
`
`
`
`
`8.5"x11" image. By carefully implementing the JPEG
`
`
`
`
`
`
`
`standard, however, the loss in the image can be confined to
`
`
`
`
`
`
`
`
`
`
`
`imperceptible areas of the image, which produces a percep-
`
`
`
`
`
`
`
`
`tually loss less uncompressed image. The achievable com-
`
`
`
`
`
`
`
`pression rates using this technique are in the range of 10:1
`
`
`
`
`
`
`
`
`
`
`to 50:1.
`
`
`FIG. 1 showsa block diagram of a typical implementation
`
`
`
`
`
`
`
`of the JPEG compression standard. ‘The block diagram will
`
`
`
`
`
`
`
`
`be referred to as a compression engine. The compression
`
`
`
`
`
`
`
`
`
`engine 10 operates on source image data, which represents
`
`
`
`
`
`
`
`a source image in a given color space such as CIELAB. The
`
`
`
`
`
`
`
`
`
`
`
`source image data has a certain resolution, which is deter-
`
`
`
`
`
`
`
`
`
`mined by how the image was captured. Each individual
`
`
`
`
`
`
`
`
`
`datum of the source image data represents an image pixel.
`
`
`
`
`
`
`
`
`
`
`The pixel further has a depth which is determined by the
`
`
`
`
`
`
`
`
`
`
`
`numberofbits used to represent the image pixel.
`
`
`
`
`
`
`
`
`
`The source image data is typically formatted as a raster 5
`
`
`
`
`
`
`
`
`
`
`stream of data. The compression technique, however,
`
`
`
`
`
`
`
`requires the data to be represented in blocks. These blocks
`
`
`
`
`
`
`
`
`
`
`represent a two-dimensional portion of the source image
`
`
`
`
`
`
`
`
`data. The JPEG standard uses 8x8 blocks of data. Therefore,
`
`
`
`
`
`
`
`
`
`
`a raster-to-block translation unit 12 translates the raster 5
`
`
`
`
`
`
`
`
`source image data into 8x8 blocks of source image data. The
`
`
`
`
`
`
`
`
`
`
`
`source image data is also shifted from unsigned integers to
`
`
`
`
`
`
`
`
`
`
`signed integers to put them into the proper format for the
`
`
`
`
`
`
`
`
`
`
`
`next stage in the compression process. These 8x8 blocks are
`
`
`
`
`
`
`
`
`
`
`then forwarded to a discrete cosine transformer 16 via bus
`
`
`
`
`
`
`
`
`
`
`14.
`
`The discrete cosine transformer 16 converts the source
`
`
`
`
`
`
`
`
`image data into transformed image data using the discrete
`
`
`
`
`
`
`
`
`
`cosine transform (DCT). The DCT,as is knowninthe art of
`
`
`
`
`
`
`
`
`
`
`
`
`image processing, decomposes the 8x8 block of source
`
`
`
`
`
`
`
`
`image data into 64 DCT elements or coefficients, each of
`
`
`
`
`
`
`
`
`
`
`which corresponds to a respective DCT basis vector. These
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`where:
`
`
`
`
`C(k), C()=1/"2 for k,l=0; and
`
`
`
`
`C(k), C()=1 otherwise
`
`
`
`The output of the transformer 16 is an 8x8 block of DCT
`
`
`
`
`
`
`
`
`
`
`
`elements or cocfficicnts, corresponding to the DCIbasis
`
`
`
`
`
`
`
`vectors. This block of transformed image data is then
`
`
`
`
`
`
`
`
`
`
`forwardedto a quantizer 20 over a bus 18. The quantizer 20
`
`
`
`
`
`
`
`
`quantizes the 64 DCT elements using a 64-element quanti-
`
`
`
`
`
`
`
`
`zation table 24, which must be specified as an input to the
`
`
`
`
`
`
`
`
`
`
`
`
`compression engine 10. Each element of the quantization
`
`
`
`
`
`
`
`
`table is an integer value from one to 255, which specifies the
`
`
`
`
`
`
`
`
`
`
`
`
`stepsize of the quantizer for the corresponding, DCT coef-
`
`
`
`
`
`
`
`
`ficient. The purpose of quantization is to achieve the maxi-
`
`
`
`
`
`
`
`
`
`mum amount of compression by representing DCT coeffi-
`
`
`
`
`
`
`
`cients with no greater precision than is necessary to achieve
`
`
`
`
`
`
`
`
`
`the desired image quality. Quantization is a many-to-onc
`
`
`
`
`
`
`
`mapping and, therefore, is fundamentally lossy. As men-
`
`
`
`
`
`
`
`tioned above, quantization tables have been designed which
`
`
`
`
`
`
`
`
`limit the lossiness to imperceptible aspects of the image so
`
`
`
`
`
`
`
`
`
`
`that the reproduced imageis not perceptuallydifferent from
`
`
`
`
`
`
`
`
`
`the source image.
`
`
`
`
`The quantizer 20 performs a simple division operation
`
`
`
`
`
`
`between each DCT coefficient and the corresponding quan-
`
`
`
`
`
`
`
`tization table element. The lossiness occurs because the
`
`
`
`
`
`
`
`quantizer 20 disregards any fractional remainder. Thus, the
`
`
`
`
`
`
`
`quantization function can be represented as shown in Equa-
`
`
`
`
`
`
`
`
`tion 2 below.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Yo[%,1] = Integer Round ( ae )
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`where Y(k,l) represents the (k,l)-th DCT element and Q(k,)
`
`
`
`
`
`
`
`
`represents the corresponding quantization table clement.
`
`
`
`
`
`
`To reconstruct the source image, this step is reversed, with
`
`
`
`
`
`
`
`
`
`the quantization table element being multiplied by the
`
`
`
`
`
`
`
`corresponding quantized DCTcoefficient. The inverse quan-
`
`
`
`
`
`
`tization step can be represented bythe following expression:
`
`
`
`
`
`
`
`
`
`YIKGFYAG] Olk A
`As should be apparent, the fractional part discarded during
`
`
`
`
`
`
`
`
`
`the quantization step is not restored. Thus, this information
`
`
`
`
`
`
`
`
`
`is lost forever. Because of the potential impact on the image
`
`
`
`
`
`
`
`
`
`
`
`quality of the quantization step, considerable effort has gone
`
`
`
`
`
`
`
`
`
`into designing the quantization tables. These efforts are
`
`
`
`
`
`
`
`
`described further below following a discussion of the final
`
`
`
`
`
`
`
`
`
`step in the JPEG compression technique.
`
`
`
`
`
`
`The final step of the JPEG standard is an entropy
`
`
`
`
`
`
`
`
`
`
`encoding, which is performed by an entropy encoder 28. The
`
`
`
`
`
`
`
`
`
`
`
`
`entrapy encoder 28 is coupled to the quantizer 20 via a bus
`
`
`
`
`
`
`
`
`
`
`22 for receiving the quantized image data therefrom. The
`
`
`
`
`
`
`
`
`
`entropy encoder achieves additional lossless compression by
`
`
`
`
`
`
`encoding the quantized DCT coefficients more compactly
`
`
`
`
`
`
`
`based on their statistical characteristics. The JPEG standard
`
`
`
`
`
`
`
`
`
`OLYMPUS EX.1014 - 10/18
`
`40
`
`45
`
`
`60
`
`65
`
`
`HUAWEI EX. 1014 - 10/18
`
`OLYMPUS EX. 1014 - 10/18
`
`

`

`5,850,484
`
`
`
`
`3
`specifies two entropy coding methods: Huffman coding and
`
`
`
`
`
`
`
`
`arithmetic coding. The compression engine of FIG. 1
`
`
`
`
`
`
`
`
`assumes Huffman coding is used. Huffman encoding,as is
`
`
`
`
`
`
`
`
`
`knownin the art, uses one or more sets of [Iuffman code
`
`
`
`
`
`
`
`
`
`
`
`
`tables 30. These tables may be predefined or computed
`
`
`
`
`
`
`
`
`
`specifically for a given image. Huffman encodingis a well
`
`
`
`
`
`
`
`
`
`
`known encoding technique that produces high levels of
`
`
`
`
`
`
`
`
`lossless compression. Accordingly,
`the operation of the
`
`
`
`
`
`
`
`entropy encoder 28 is not further described.
`
`
`
`
`
`
`
`Referring now to FIG. 2, a typical JPEG compressedfile
`
`
`
`
`
`
`
`
`
`
`
`is shown generally at 34. The compressed file includes a
`
`
`
`
`
`
`
`
`
`
`JPEG header 36,
`the quantization (Q) tables 38 and the
`
`
`
`
`
`
`
`
`
`
`
`Huffman (H) tables 40 used in the compression process, and
`
`
`
`
`
`
`
`
`the compressed image data 42 itself. From this compressed
`
`
`
`
`
`
`
`
`
`file 34 a perceptually indistinguishable version of the origi-
`
`
`
`
`
`
`
`
`nal source image can be extracted when an appropriate
`
`
`
`
`
`
`
`
`Q-table is used. This extraction process is described below
`
`
`
`
`
`
`
`
`with reference to FIG. 3.
`
`
`
`
`
`AJPEG decompression engine 43 is shown in FIG. 3. The
`
`
`
`
`
`
`
`
`
`
`decompression cngine essentially operates in reverse of the
`
`
`
`
`
`
`
`
`compression engine 10. The decompression engine receives
`
`
`
`
`
`
`
`the compressed image data al a header extraction unit 44,
`
`
`
`
`
`
`
`
`
`
`which extracts the H tables, Q tables, and compressed image
`
`
`
`
`
`
`
`
`
`
`data according to the information contained in the header.
`
`
`
`
`
`
`
`
`
`‘The H tables arc then stored in H tables 46 while the Q tables
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are stored in Q tables 48. The compressed image datais then
`
`
`
`
`
`
`
`
`
`
`
`sent to an entropy decoder 50 over a bus 52. The Entropy
`
`
`
`
`
`
`
`
`
`
`
`
`Decoder decodes the Huffman encoded compressed image
`
`
`
`
`
`
`
`data using the H tables 46. The output of the entropy decoder
`
`
`
`
`
`
`
`
`
`
`
`
`50 are the quantized DCT elements.
`
`
`
`
`
`
`The quantized DCT elements are then transmitted to an
`
`
`
`
`
`
`
`
`inverse quantizer 54 over a bus 56. The inverse quantizer 54
`
`
`
`
`
`
`
`
`
`multiplies the quantized DCT elements bythe corresponding
`
`
`
`
`
`
`
`quantization table elements found in Q tables 48. As
`
`
`
`
`
`
`
`
`described above,
`this inverse quantization step does not
`
`
`
`
`
`
`
`yicld the original source image data because the quantization
`
`
`
`
`
`
`
`
`step truncated or discarded the fractional remainder before
`
`
`
`
`
`
`
`transmission of the compressed image data.
`
`
`
`
`
`
`The inverse quantized DCT elementsare then passed to an
`
`
`
`
`
`
`
`
`
`
`
`inverse discrete cosine transformer (IDCT) 57 via bus 59,
`
`
`
`
`
`
`
`
`which transforms the data back into the time domain using
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the inverse discrete cosine transform (IDCT). The inverse
`transformeddata is then transferred to block-to-raster trans-
`
`
`
`
`
`
`
`lator 58 over a bus 60 where the blocks of DCT elementsare
`
`
`
`
`
`
`
`
`
`
`
`translated into a raster string of decompressed source image
`
`
`
`
`
`
`
`
`data. From the decompressed source image data, a facsimile
`
`
`
`
`
`
`
`
`of the original source image can be reconstructed The
`
`
`
`
`
`
`
`
`reconstructed source image, however, is not an exact repli-
`
`
`
`
`
`
`
`
`cation of the original source image. As described above, the
`
`
`
`
`
`
`
`
`
`
`quantization step produces some lossiness in the process of
`
`
`
`
`
`
`
`
`
`compressing the data. By carefully designing the quantiza-
`
`
`
`
`
`
`
`tion tables, however, the prior art mcthods have constrained
`
`
`
`
`
`
`
`
`
`the loss to visually imperceptible portions of the image.
`
`
`
`
`
`
`
`
`
`These methods, and their shorlcomings, are described
`
`
`
`
`
`
`
`below.
`
`The JPEG standard includes two examples of quantization
`
`
`
`
`
`
`
`tables, one for luminance channels and one for chrominance
`
`
`
`
`
`
`
`
`channels. See International Organization for Standardiza-
`
`
`
`
`
`tion: “Information technology—digital compression encod-
`
`
`
`
`ing of continuous-tonesstill images—part 1: Requirements
`
`
`
`
`
`
`
`and Guidelines,” ISO/IEC IS10918-1, Oct. 20, 1992. These
`
`
`
`
`
`
`
`
`tables are known as the K.1 and K.2 tables, respectively.
`
`
`
`
`
`
`
`
`
`
`These tables have been designed based on the perceptually
`
`
`
`
`
`
`
`
`
`lossless compression of color images represented in the
`
`
`
`
`
`
`
`
`YUVcolor space.
`
`
`
`These tables result in visually pleasing images, but yield
`
`
`
`
`
`
`
`
`a rather low compression ratio for certain applications. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`4
`compression ratio can be varied by setting a so-called
`
`
`
`
`
`
`
`
`
`Q-factor or scaling factor, which is essentially a uniform
`
`
`
`
`
`
`
`
`
`multiplicative parameter that
`is applied to each of the
`
`
`
`
`
`
`
`
`
`elements in the quantization tables. The larger the Q-factor
`
`
`
`
`
`
`
`
`
`the larger the achievable compression rate. Even if the
`
`
`
`
`
`
`
`
`
`original
`tables are carefully designed to be perceptually
`
`
`
`
`
`
`
`
`lossless, however, a large Q-factor will introduceartifacts in
`
`
`
`
`
`
`
`
`
`the reconstructed image, such as blockiness in areas of
`
`
`
`
`
`
`
`
`
`constant color or ringing in text-scale characters. Some of
`
`
`
`
`
`
`
`
`
`these artifacts can be effectively cancelled by post-
`
`
`
`
`
`
`
`processing of the reconstructed image by passing it through
`
`
`
`
`
`
`
`
`a tone reproduction curve correction stage, or by segmenting
`
`
`
`
`
`
`
`
`the image and processing the text separately. However, such
`
`
`
`
`
`
`
`
`methods easily introduce new artifacts. Therefore,
`these
`
`
`
`
`
`
`methods are not ideal.
`
`
`
`
`As a result of the inadequacy of the Q-factor approach,
`
`
`
`
`
`
`
`
`
`additional design methods for JPEG discrete quantization
`
`
`
`
`
`
`tables have been proposed. These methods can be catego-
`
`
`
`
`
`
`
`
`rized as cither perceptual, which means bascd on the human
`
`
`
`
`
`
`
`
`
`
`visual system (HVS)or based on information theorycriteria.
`
`
`
`
`
`
`
`
`
`‘These methods are also designated as being based on the
`
`
`
`
`
`
`
`
`
`
`removalof subjectiveor statistical redundancy, respectively.
`
`
`
`
`
`
`
`These methods are discussed in copending application
`
`
`
`
`
`
`
`entitled “Method for Selecting JPEG Quantization Tables
`
`
`
`
`
`
`
`for Low Bandwidth Applications,” commonly assigned to
`
`
`
`
`
`
`
`the present assignee, incorporated hercin by reference.
`
`
`
`
`
`
`
`Quantization is not the only cause of image degradation.
`
`
`
`
`
`
`
`
`
`The color source image data itself might be compromised.
`
`
`
`
`
`
`
`
`
`For scanned colored images, the visual quality of the image
`
`
`
`
`
`
`
`
`
`
`can be degraded because of the inherent limitations of color
`
`
`
`
`
`
`
`
`
`
`scanners. These limitations are mainly of two kinds: limited
`
`
`
`
`
`
`
`
`
`modulation transfer function (MTI") and misregistration.
`
`
`
`
`
`
`The modulation transfer function refers to the mathematical
`
`
`
`
`
`
`
`
`representation or transfer function of the scanning process.
`
`
`
`
`
`
`
`
`There are inherent limitations in representing the scanning
`
`
`
`
`
`
`
`
`process by the MTF andthese limitations are the main cause
`
`
`
`
`
`
`
`
`
`
`
`of pixcl aliasing, which produces fuzzy black text glyphs of
`
`
`
`
`
`
`
`
`
`
`grayish appearance. Misregistration, on the other hand,
`
`
`
`
`
`
`
`refersto the relative misalignmentof the scanner sensors for
`
`
`
`
`
`
`
`
`
`
`the various frequency bands. For example,
`the Hewlett
`
`
`
`
`
`
`
`
`Packard Scan Jet IIc™ has a color misregistration tolerance
`
`
`
`
`
`
`
`
`
`of +/-0.076 mm for red and blue with respect to green.‘his
`
`
`
`
`
`
`
`
`
`
`
`
`amount of misregistration is significant considering the size
`
`
`
`
`
`
`
`
`of an image pixel (e.g., 0.08 mm at 300 dots per inch (dpi).
`
`
`
`
`
`
`
`
`
`
`
`
`
`These limitations significantly degrade text
`in color
`
`
`
`
`
`
`
`images because sharp edges are very important for reading
`
`
`
`
`
`
`
`
`
`efficiency. The visual quality of text can be improved,
`
`
`
`
`
`
`
`
`
`however, using prior art edge enhancementtechniques. Edge
`
`
`
`
`
`
`
`
`enhancement can be performed in either the spatial or
`
`
`
`
`
`
`
`
`
`frequency domain. In the spatial domain (i.e., RGB), edge
`
`
`
`
`
`
`
`
`
`crispening can be performed by discrete convolution of the
`
`
`
`
`
`
`
`
`
`scanned image with an edge enhancement kemel. This
`
`
`
`
`
`
`
`
`approachis cquivalentto filtering the image with a high-pass
`
`
`
`
`
`
`
`
`
`filter. However, this technique is computationally intensive.
`
`
`
`
`
`
`
`An MxN convolution kernel, for example, requires MN
`
`
`
`
`
`
`
`
`multiplications and additions per pixel.
`
`
`
`
`
`For edge sharpening in the frequency domain, the full
`
`
`
`
`
`
`
`
`imageis first transformed into the frequency domain using
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the Fast Fourier Transform (FFT) or the Discrete Fourier
`Transform (DFT), lowfrequency components are dropped,
`
`
`
`
`
`
`and then the image is transformed back into the time
`
`
`
`
`
`
`
`
`
`domain. This frequency domain method, as with the spatial
`
`
`
`
`
`
`
`
`domain method,
`is also computationally intensive.
`
`
`
`
`
`Moreover,
`it uses a transformation different
`than that
`
`
`
`
`
`
`
`required by the JPEG standard.
`
`
`
`
`
`Accordingly,
`the need remains for a computationally
`
`
`
`
`
`
`efficient method for improving the visual quality of images,
`
`
`
`
`
`
`
`
`and in particular text, in scanned images.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`20
`
`
`
`25
`
`
`
`
`
`
`
`40
`
`
`
`45
`
`
`
`
`
`
`60
`
`
`
`65
`
`
`OLYMPUS EX. 1014 - 11/18
`
`HUAWEI EX. 1014 - 11/18
`
`OLYMPUS EX. 1014 - 11/18
`
`

`

`5,850,484
`
`
`
`
`5
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`The invention is a method of compressing and decom-
`
`
`
`
`
`
`
`
`pressing images which comprises using one quantization
`
`
`
`
`
`
`table (Q,-) for compressing the image and a second quanti-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`zation table (Q,) for decompressing the image. In general,
`compression and decompression are performed in conform-
`
`
`
`
`
`
`ance with the JPEG standard. The second quantization table
`
`
`
`
`
`
`
`
`Qn is related to the first quantization table according to the
`
`
`
`
`
`
`
`
`
`
`following general expression:
`
`
`
`On=SxOe+B,
`
`
`
`
`
`
`
`
`where S is a scaling matrix having cach clement S[k,l]
`
`
`
`
`
`
`
`
`
`formed according to the following expression:
`
`
`
`
`
`
`ST IPEVVVIAA
`
`
`
`
`
`
`
`
`
`
`where V* is a variance matrix of a reference image and V,
`
`
`
`
`
`
`
`
`
`
`
`is a variance matrix of a scanned image; and where B is a
`
`
`
`
`
`
`
`
`
`
`
`
`brightness matrix, which can include zero or non-zero
`
`
`
`
`
`
`
`
`clements. By using the scaling matrix $, the high-frequency
`
`
`
`
`
`
`
`
`
`components of the DCT elements can be “enhanced” with-
`
`
`
`
`
`
`
`
`oul any additional computational requirements. According
`
`
`
`
`
`to the invention,
`the quantization table Q,, is transmitted
`
`
`
`
`
`
`
`
`with the encoded quantized image data, and is used in
`
`
`
`
`
`
`
`
`
`decompression to recover the image.
`
`
`
`
`
`The reference image is a preselected continuous-tone
`
`
`
`
`
`
`
`image, either grayscale or color depending on the images to
`
`
`
`
`
`
`
`
`
`
`be processed. The reference image is rendered into a target
`
`
`
`
`
`
`
`
`
`
`image file. The target
`image file is not generated by a
`
`
`
`
`
`
`
`
`
`
`
`scanner, so the data therein is not compromised by anyof the
`
`
`
`
`
`
`
`
`
`
`
`
`inherent limitations of a color scanner. Thus, the variance of
`
`
`
`
`
`
`
`
`
`he target image data, whichis a statistical representation of
`
`
`
`
`
`
`
`
`
`he energy or frequency content of the image, retains the
`
`
`
`
`
`
`
`
`
`
`high-frequency components. The reference image can be
`
`
`
`
`
`
`
`any continuous-tone image, but in the preferred embodiment
`
`
`
`
`
`
`
`
`he reference image includes text with a scrif font because
`
`
`
`
`
`
`
`
`
`
`he serif font has good visual quality which the method
`
`
`
`
`
`
`
`
`
`
`preserves.
`
`The scanned image, although it can be any image, in the
`
`
`
`
`
`
`
`
`
`
`
`preferred embodimentis a printed version of the reference
`
`
`
`
`
`
`
`
`
`image. ‘hus, the variance of the scanned image represents
`
`
`
`
`
`
`
`
`
`he energy or frequency composition of the reference image
`
`
`
`
`
`
`
`
`
`but which is compromised by the inherent limitations of the
`
`
`
`
`
`
`
`
`
`
`scanner. The scaling matrix, therefore, boosts the frequency
`
`
`
`
`
`
`
`
`components that are compromised by the scanning process.
`
`
`
`
`
`
`
`
`A preferred embodiment of the invention is described
`
`
`
`
`
`
`
`
`herein in the context of a color facsimile (fax) machine. The
`
`
`
`
`
`
`
`
`
`
`color fax machine includes a scanner for rendering a color
`
`
`
`
`
`
`
`
`
`
`imageinto color source image data that represents the color
`
`
`
`
`
`
`
`
`
`
`image, a compression engine that compresses the color
`
`
`
`
`
`
`
`
`source image data to compressed image data, a means for
`
`
`
`
`
`
`
`
`
`
`encapsulating the compressed image data, and a mcans for
`
`
`
`
`
`
`
`
`
`transmitting the encapsulated data. The compression engine
`
`
`
`
`
`
`
`includes meansfor storing two quantization Lable