BAR CODE LABEL
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`us. PATENT APPLICATION
`
`SERIAL NUMBER
`
`08/411,369
`
`FILING DATE
`
`03/27/95
`
`GROUP ART UNIT
`
`2613
`
`GIORDANO BERETTA, PALO ALTO, CA; VASUDEV BHASKARAN, MOUNTAIN VIEW, CA;
`KONSTANTINOS KONSTANTINIDES, SAN JOSE, CA.
`
`APPLICANT
`
`**CONTINUING DATA*********************
`VERIFIED
`
`**FOREIGN/PCT APPLICATIONS************
`VERIFIED
`
`Date
`
`Certifying Officer
`
`that annexed hereto is a trye copy frqm. the records of the United States
`This is to certif
`Patent and Tra emark Office of the appllcatlon WthI‘l IS Identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`FOREIGN FILING LICENSE GRANTED 04/26/95
`
`SHEETS
`DRAWING
`
`7
`
`INDEPENDENT
`CLAIMS
`
`FILING FEE
`RECEIVED
`
`ATTORNEY DOCKET NO.
`
`.
`
`$1,158.00
`
`10940893
`
`RECORDS MANAGER
`LEGAL DEPARTMENT ZOBO
`HEWLETT PACKARD COMPANY
`P 0 BOX 10301
`PALO ALTO CA 94303-0890
`
`ADDRESS
`
`TEXT AND IMAGE SHARPENING OF JPEG COMPRESSED IMAGES IN THE FREQUENCY
`DOMAIN
`
`
`
`OLYMPUS EX. 1016 - 1/714
`
`

`

`BAH CODE LABEL
`
`mmwmwmm
`
`‘SEHMLNUMBEH _ *>J~
`
`. C’s/Q1136? ,
`
`,
`
`'
`
`-.,
`
`'. v-.
`
`,r
`
`{,.‘_;,V:"
`
`;‘
`
`.
`
`-j.j GROUPAhTUNn
`
`v-
`
`‘
`
`"l 1'
`
`-'
`
`5250's ,
`
`IGiORbANé_BERETTAJK?AE6;AL§O;
`KONSIANTINQs'KOquANTINIDEs;.
`
`.;,"_‘ **CONTINU]:N¢3.
`VERIFIEDVE f
`
`'»-"'3v
`
`U“‘" “
`
`‘
`
`'
`
`7 *fFOREICN/PCT’APfiLiCKfEONé¥*#*%¥*#f#ii"f"
`“'VER1FIED3
`'
`“
`-
`‘
`4
`
`I- "
`
`‘This'is iodér‘fif‘ ,tha‘f'fifihqxéd héfiib’i‘é firfifiéfiy‘pfiém ihé rec'd: s._of\.ffié.Ufiifé&'Stai’teé 3
`Patent and'Tra emark Offlpe qf'Ihe application which IS Identlfléd abbve':
`*
`_
`'
`Byauthorifioftila,',
`,
`1"
`-
`COMMISSIDNER 0F PATENTS THADEMAEKS _
`
`ponies:mung;Licgnsm’11cRANtEpsgog1/2ajéé
`V
`snaas‘v
`‘
`-
`,
`h
`~ =_»
`“
`‘s-‘
`* mmmm _3
`g_,uf
`gg}_
`i3-j3'
`
`_
`_
`V
`HUNGTEE .-':_"T ATTORNEYDUCKETNQ
`.'nmflwn;
`~ I,
`a
`.-
`
`_
`
`7H1;
`
`_Qf”’
`
`if}.
`
`'“Evnf }T<"§ .$1,158ibo:” f.ioéédaga H
`
`}MARGER":0HNS¢N‘MéchL¢M_sTchwiTZ".5“
`y;,-1030_sw MORRISON ST " '
`'
`'
`-: PORTLANonR 97205N‘: f
`
`V1"TEXT ANb IMAGE SHARPENING OF JPEG*COMP§ESSED IMAGES-IN THE FREQUENCY
`,DOMAIN “ '
`‘
`'-r” I
`'
`-v' -" 1" '
`"
`.
`-
`1
`.fi
`
`~
`
`Date
`
`>
`
`'
`
`-
`
`"
`
`.7
`
`Certifying-DRE”
`
`
`
`OLYMPUS EX. 1016 - 2/714
`
`

`

`HEWLETT-PACKARD COMPANY
`Legal Department, 2030
`r
`P.O. Box 10301
`Fan Alto, California 943030590
`
`g
`
`.
`
`»
`
`I
`g
`'
`PATEN A
`.
`ArronNEv DOCKET No.
`- 1 094893-1
`
`TO
`
`COMMISSIONER OF PATENTS AND'TRADEMARKS
`Washington, D.C. 20231
`Slr:
`
`Transmitted herewith fOrfiling under 37 CFR 1.53(b) is a(n):
`firefime
`V
`'
`flan, HQ?
`"
`*“
`[WW “’
`
`V
`
`V
`
`( ) Design
`(X) Utility
`.
`.
`.
`.
`(X) orIgInal patent applIcatIon,
`( )continuing application.
`( ), continuation-impart
`
`( )continuation or
`
`( )divisional
`
`or S/N
`
`filed
`
`INVENTOR(S): Giordano Beretta et al.
`
`TITLE:
`
`TEXT AND IMAGE SHARPENING 0F JPEG COMPRESSED IMAGES IN THE
`FREQUENCY DOMAIN
`
`Enclosed are:
`
`(X) The Declaration and Power of Attorney.
`(X)
`7
`sheets of ,(X) formal drawings
`
`) unsigned or partially signed
`(
`(X) signed
`.(
`)
`informal drawings
`(one set)
`
`(
`(
`
`) Information Disclosure Statement and Form PTO-1449
`) Priority document(s) () (Other)
`,
`
`(
`
`) Associate Power of Attorney
`(fee$
`
`)
`
`(1)
`FOR
`
`CLAIMS As FILED BY OTHER THAN A SMALL ENTITY
`(2)
`»
`(3)
`(4)
`»
`NUMBER FILED
`NUMBER EXTRA
`RATE
`
`(5)
`TOTALS
`
`TOTAL CLAIMS
`
`I
`
`INDEPENDENT
`CLAIMS
`ANY MULTIPLE
`DEPENDENT CLAIMS
`
`IIIIIIIIM$ 240
`
`X
`
`X
`
`$ 22
`
`$76
`
`
`
`to Deposit Account 08-2025. At any time during thependehcy of this application,
`1,158 I
`Charge :8
`please charge any fees required or credit any over payment to Deposit Account 08-2025 pursuant to 37 CFR
`1.25. Additionally please ’charge any fees to Deposit Account 08-2025 under 37 CFR 1.19. 1.20 and 1.21. A
`duplicate copy of this sheet is enclosed.
`'
`'l'l b |
`.
`6300
`u
`465
`Express Mal
`a e no T339
`Date of Deposit March 27 I 1995
`I hereby certify that this Is'being deposited with the
`United States Postal Service “Express Mail Post
`Office to Addressee' sen/ice under 37 CFFIu1..1_0 on
`the date indicated aboveand is addressed to the
`Commissioner
`of
`Patents
`and
`Trademarks,
`Washingt
`[0.0.20231;
`
`BASIC FEE: Design ( $3300.00 ); Utility ( $730.00)
`TOTAL FILING FEE
`
`TOTAL CHARGES TO DEPOSIT ACCOUNT
`
`N(dO
`
`I
`
`.
`Respectfully submmed'
`..
`_
`I
`Glordano Bereua et al'
`.V
`C, I!
`I
`
`By
`
`W
`
`.
`
`C. Douglass homes
`
`Attorney/Agent for Applicant(s)
`Reg. No.
`32,947
`Date: March 27 , 1995
`
`kivaM—W
`By
`Typed Name: Linda A. Iimura
`
`Rev 10/94 (Form 3.04)
`
`.
`
`- Attach as First Page to Transmitted Papers - Telephone N04 (415) 857'8129
`
`OLYMPUS EX. 1016 - 3/714
`
`

`

`Patent Application
`‘
`.
`~
`Attorney Docket Number 1094893-1
`
`TEXT AND IMAGE SHARPENING OF JPEG COM ESSED
`r
`I
`Is IN THE FREQUENCY DOMAIN
`
`‘
`
`C’l
`
`' RELATED APPLICATION DATA .
`
`Figure 1 shows a block diagram of a typical implementation of the
`
`invention relates to data compression using the JPEG
`This
`Compression standardvfor continuous -_tone still images, both grayscale
`and color.
`V
`I
`_
`g
`V
`~A cOmrnittee” known as "JPEG," whiCh stands for "Joint
`PhOtographic EXperts Group," hasestablished a standard for compressing
`continuous—tone still images, .b'Oth 'grayScale and color. _This standard
`represents a cOmpromise between reproducible image quality and
`compression rate." To achieve acceptable cOmpression rates, which refers
`to 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 Ofdata
`needed to represent a color imageron the order Of 10 megabytes for a 200
`dots per inch (DPI), 81.51" x 11" image” By carefully implementing the
`JPEG' standard, however, the loss in the image can be confined to
`imperceptible areas ofthe image, which produces a perceptually loss less
`. uncompressed . image. The achievable compression rates using this
`technique are in the range of 10:1 to 50:1.
`
`This application incorp0rates subject matter disclosed in commonly-
`assigned application entitled. METHOD FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTHAPPLICATIONS,
`_Ser. No. Wfifled on even date hereWith.
`
`,1
`
`. BACKGROUND OF THE INVENTION
`
`
`
`OLYMPUS EX. 1016 - 4/714
`
`

`

`2
`
`L
`
`Patent Application
`v
`Attemey Docket Number 1094893-1
`
`JPEGcompression standard. The block diagram will be referred to as a
`compression engine; The compression engine 10 operates on source image
`data, which represents a scurce image in a givencolor space such as
`CIELAB. The. source image data has a certain resolution, which is
`determined by. how the image was captured. Each individual datum of V
`the source image data represents an image pixel. The piXel further has
`a depth "which is determined by the number of bits-used to represent the
`image pixel.
`I
`L
`l
`The sourceimagedata is typically forfnatted as a raster stream
`of data. The compression technique, however, requires the data to be
`represented in blO‘cks. These blocks represent a two-dnnensional portion
`of the source image data. The JPEG standard uses .sxs bldcks of data.
`Therefore, a raster-to-block translation unit 12 translates the raster
`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.
`I.
`l
`‘
`V
`The discrete cosine transformer 16 converts the s0urce image data
`_ into transferrned image data using the discrete c0sine transform (DCT).
`
`function as Shown below, hence the name.
`
`The DCT, as is known in the art ofimage processing, decomposes the 8x8
`block of source image data into
`elements or coefiiCients, each of
`which corresp0nds to a respective DCT basis vector. These basis vectors
`are unique 2—dimensional (2D) "spatial waveforms," which are the
`fundamental, units in the
`space. These basis vectors can be
`intuitiver thoughtto 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 disorete cdsine (FDCT)
`
`OLYMPUS EX. 1016 - 5/714
`
`

`

`Patent Application
`_
`Attorney Docket Number 1094893—1
`
`f .
`
`~(2x.+1)k1:
`
`(2y+1)11t
`
`I YQik; 1] = IntegerRound(.—[_lg[fl])
`
`The Output of the transfcrmer 16 is an 8x8 block of DCT elements
`or coefficients, correspondingto the DCT basis vectors, This block of
`transformed image data is then forwarded to a quantizer 20 over. a bus
`18. The quantizer 2O quantizes the 64 DCT elements using a 64Lelement
`quantization table*24,~‘ which must be specified as an input the
`Compression engine 10, Eachelement of the quantization table is an
`integer value from one to 255, which specifies. the stepsize of the
`quantizer for the corresponding iDCT coefficient; The purpose of
`quantization is to achieve the maximum amount of compression by
`representing DCT coefficients with no greater precision than is necessary
`to achieve the desired image quality, QUantization is a many-to-one
`mapping and, therefore, is fundamentally lo'ssy.
`mentioned above,
`'quantiZation tables have been designed which limit the lossineSs to
`imperceptible aspects of the image so that the reproduced image is not
`perceptually different frOm the Source: image.
`>
`The quantizer 20 performs a simple division operation between each
`DCT cbefiicient and the corresponding quantization table element. The
`lossiness occurs because the quantizer 20 disregards any fractional
`
`1
`
`v
`
`7
`
`7
`
`Y[k,1] =- ECU‘IV) ° C(DLééSULY) 0 COST—COST
`
`where: C(k), C(l)'=. I/fii'orkJ = 0; and
`
`_ C(k), (3(1) = 10therwise
`
`remainder. Thus, the quantization function can be represented as shown
`
`in Equation 2 belOw.
`
`-
`
`OLYMPUS EX. 1016 - 6/714
`
`

`

`Y’[k, 1] = YQ[k,'1] QE[k, 1].
`
`the fractional part discarded during the
`As should. be apparent,
`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 goneinto designing the quantization tables.
`These .efi'Orts are described further below following a discussion of the
`
`4
`
`Patent Application
`.
`'
`Attorney Docket Number 1094893-1
`
`where Y(k,‘1) represents the (k,l)—th DCT element and Q(k,l) represents
`the corresponding quantizationtable element.
`To reconstruct the source image, this step; is reversed, with the
`quantization table element being multiplied by the corresponding
`quantized; DCT coefiiCient. The inverse quantization step can be
`represented by the follOwing expression:
`
`Referring now to' Fig. 2, a typical JPEG compressed file is shown
`
`‘
`final step in the JPEG compression technique.
`I,
`The final step of the JPEG standard is an entropy encoding, which
`is performed by an entropyencoder
`The entropy encoder 28 is coupled
`I 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 Specifies two entropy
`coding ‘ methodsi,
`' Huffman coding and arithmetic coding.
`The
`compression engine of Fig. 1 assumes Huffman coding is used. Huffman
`encoding, as
`knOWn in the art, uses one or more sets of Huffman code
`tables 30. These tables may be predefined or computed specifically for a
`given image. Hufl‘manenco’ding is a Well known encoding technique that
`produces high levels oflOssless Compression. Accordingly, the operation
`of the entropy encoder ‘28-'is not further deScribe‘d. ,
`
`OLYMPUS EX. 1016 - 7/714
`
`

`

`- 5
`
`Patent Application
`v
`Attorney Docket Number 1094893-1
`
`generally at 34. The compressed file includes a JPEG header 36, the
`quantization (Q)ltables 38 and the
`(H) tables 40 used in the
`compression process. and the compreSSed image data 42 itself. From this
`compressed file 34 aperceptually indistinguishable version ofthe original
`source image can be extracted When an appropriate Q-‘table is used. This
`
`elements are translated into a raster string ofdecompressed source image
`
`extraction process is described belovv with reference to Fig. 3.
`AV JPEG decompression engine 43 is shovvn in ' Fig. 3. The
`decompression engine essentially operates in reverse of the compression
`engine IQ. The decompression engine receives the compressed image data
`at 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
`tables are then stared in H tables 146 While the Q tables
`are stored in
`tables 48. The compressed image data is then sent to an
`entropy deCoder '50 over a‘bus 52. The'Entrop'y Decoder decodes the
`Huffman encoded campressed image data using ththables 46'. The
`output of the entropy decoder 50 are the quantized DCT elements.
`The quantized DCT elements are Vthen‘transmitted to an inverSe
`quantizer 54 over a bus 56. The inverse Quantizer 54'1multiplies the
`quantized DCTV elements by, the corresponding quantization table
`elements found in ‘ Q tables "48. As described above,
`this inverse
`quantization step does not yield theoriginal source image data because
`the quantization step truncated or discarded the fractional remainder
`before transmission of the compressed image data.
`I
`The inverse quantized DCT elements are then passed to an inverse
`discrete cosine transformer (IDCT) 57 via bus 59, which transforms the
`data backl’into the time domain using the inverse discrete cosine
`transform (IDCT). The inverse transformed data issthen transferred to
`block-to-raster translator 58' were bus 60. v'vhere the blocks of DCT
`
`OLYMPUS EX. 1016 - 8/714
`
`

`

`‘
`
`l
`
`Patent Application
`,
`.
`.
`Attorney Docket Number 1094893-1
`
`‘5
`
`a
`
`separately. However, such methods easily introduce new artifacts.
`
`data, From the‘deco'mp'r'e-ssed source image data, a facsimile of the
`original source image Can be. reconstructed The reconstructed source
`image, however, is not an exact replication of the Original source iinage.
`As desoribed above, the quantizationstep produces some lossiness in the
`process ofcompressing the data. By carefully designing the quantization
`tables, however, the prior art methods: have constrained» the loss to
`visually imperceptible portions of the image, These methods, and their
`shortcomings, are described belovv.
`V
`I
`The PEG standard includes two examples of quantization tables,
`one for' luminance channels and one for chrominance channels; See
`International Organization for-Standardization: “Information technology
`' - digital compression encoding'of continuous .- tones still images - part 1:
`Requirements and Guidelines, " ISO/IE0 1s10918—1, October 20,’ 1992.
`These tables are knovvn as the KI and -K.2,tab1es, respectively. These
`tables have been designed based-on the perceptually loss1ess compression
`of colOr images represented invthe YUV cOIOr space.
`‘ These tables result in visually,pleasingimages, but yield a rather
`low compression ratiofOr certain applications. The Compression ratio can
`be varied by setting a so-Icalled gQ-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
`vvill introduce artifacts in the reconstructed image, such as blockiness in
`areas of constant colOr or
`tent-scale characters. Some of these
`artifacts can be effectively cancelled _' by post-processing of
`the
`reconstructed image bypassing it thrOugh a tone reproduction curve
`' correction stage, or by segmenting the image and processing the text
`
`OLYMPUS EX. 1016 - 9/714
`
`

`

`7
`
`-
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`sharp edges arevery important for reading efficiency. The visual quality
`
`'
`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 categorized as either perceptual, which
`means based on the human visual system (HVS) or based on information
`theory Criteria. Thesemethods are also designated as being based on the
`removal of Subjective 0r statistical redundancy, respectively. These
`' methods are discussedin copending application entitled "Method for
`Selecting JPEG Quantization Tables for Low Bandwidth Applications,"
`commonly assigned to the present assignee, incorporated herein by
`reference.
`h
`I
`V
`‘
`Quantization is not theonly cause ofimage degradation. The color
`s'ource image data itself might be compromised. For scanned colored
`images, the visual quality cf the image can be degraded because of the
`inherent limitations of color soanners. These limitations are mainly of
`two kindsi
`limited ' modulation tranSfer. qunction (MTF)
`and
`misregistration,
`The . modulation tranSfer. function refers to the
`mathematical representation or transferfunction ofthe scanning process.
`There are inherent limitations in representing the soanningprocess by
`the MTF and these limitations are the main cause ofpixel aliasing, which
`produces fuZZy black text glyphs ofgrayish appearance, Misregistration,
`on the Other hand,- refers to the relative misalig‘nméntpdf the scanner
`sensOrs for the various frequencybands. For example, the Hewlett
`Packard scan Jet IIcTM has acolor misregistration tolerance of+/- 0.076
`mm for red and, blue with respect
`to green;
`V This amount of
`misregistration is signifiCant conSidering the. size ofan image pixel (e.g.,
`0.08 mm at 300 dots per inch (dpi)).
`1
`These limitations Significantly degrade text in color images because
`
`OLYMPUS EX. 1016 - 10/714
`
`

`

`8 i
`
`'
`
`Patent Application
`1
`‘
`Attorney Docket Number 1094893-1
`
`of text can be imprOVed, however, .jusing prior art edge enhancement
`techniques.‘ Edge enhancement can be perfornmd in‘either the spatial
`or frequency domain. ‘ Ii: the spatial domain ‘(i.e.; RIGB)‘, edge crispening
`can be performed by discrete Convolution of the'scanned image with an
`edge enhancement kernel. This approach is equivalent to filtering the
`image with a high-pass filter. However, this technique
`computationally
`intensive. An M x N cOnvolution kernel, for example, requires MN
`. multiplications and additionsper' pixel.
`‘
`V For edge sharpening in the frequency demain, the full image is first
`
`QD=SXQE~+Ba
`
`. transformed intothe frequency domain using the Fast Fourier Transform
`
`low frequency
`the Discrete Fourier Transform (DFT),
`(FFT) or
`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. cemputa‘tionally intensive;
`. Moreover,
`uses a
`tran’Sfonnation differentthan that required bythe JPEG standard.
`Accordingly; the need remains for a. computationally efficient
`method for improving the visual quality ofimages, and in particular text,
`
`in scanned images.
`
`* SUMMARY or THE INVENTION
`The invention is a methOd of compressing and decompressing
`images which comprises using one quantization table (QB) for compressing
`the image and a secOnd quantizatiOn tahle (QB) fOr decompressing the
`image;
`In general, compression and decOmpreSSion are performed in
`conformance with the JPEG'standard. The second quantization table Q;
`is relatedto the first quantization table aCCOrding tothe following general
`expression:
`
`OLYMPUS EX. 1016 - 11/714
`
`

`

`Patent Application
`_
`» Attorney Docket Number '1094893-1
`
`the frequency components that are compromiSedby the scanning process.
`
`where V* is a variance matrix of a reference image and Vy is a variance
`matrix of a scanned image; and where B is a brightness matrix, which
`can include zero or non-zero elements. By using the sealing matrix S, the
`high-frequency components of the. DCT elements can be "enhanced"
`Without any additional computational requirements. According to the
`invention; the» quantization table
`is transmitted With the encoded
`quantized imagedatmand used in: decompression to recover the image.
`Thereference image is a preselected Continuous-tone image, either
`grayscale
`color depending onthe images to be processed. The reference
`im'ageis renderedvinto a target image file. The target image file is not
`generated by a scanner, so the data therein is not compromiSed by any of
`the inherent limitations of a color scanner. Thus, the variance‘of the
`target image data, which is a statistical representation of the energy or
`frequency content of image, retains the high-frequency components.
`The reference image can be any continuous-tone image, but in the
`preferred embodiment the reference image includes text with a seriffont
`because the seriffonthas geod visual quality which thezmethod‘ preserves.
`The scanned image, although it can be any image, in the preferred
`embodiment is aprinted Version of the reference iinage.‘ Thus, the
`variance 'of the scanned image represents the energy or frequency
`compOSition .the-yreference image but which is compromiSed by the
`inherentilimitationsOfthe scanner. The Scaling matrix, therefore, boosts
`
`where S is a Scaling matrix having each element S[k,l] formed according
`to the following expression:
`
`S[k,1]2 ='V*[k,1'1/v-Y[k,1]
`
`
`
`OLYMPUS EX. 1016 - 12/714
`
`

`

`1 O
`
`v
`
`*
`
`Patent Application
`a
`_
`'
`Attorney Dbcket Number 1094893-1
`
`'
`
`A preferred embodirnent ofthe invention is deScribed herein in the
`context ofa color facsimile (fax) machine. The colorfax machine includes
`a scanner for renderinga color image‘into 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
`encapsulatingflie compressed image data, and a means for transmitting
`the encapsulated data. _ The compression engine includes means for
`storing two quantization tables. The first quantization table is used to
`quantize the image data transformed using the discrete cosine transform
`(DCT). The second quantization table is encapsulated withthe encoded
`
`Fig. 2 is a drawing of a typical format of a JPEG compressed file.
`
`between two locations, the machine transfers the images with higher
`quality than prior systems.
`I
`The second quantization table can be precomputed and stored'in the
`compression engine, in which case there are ’no additional computational
`requirements for the cOmpression engine. to implement the image
`enhancing method ofthe invention. This capability results in a lower cost
`color facsimile product, than is possible using the prior art image
`enhancement techniques.
`‘
`The-foregoing and other objects, features and advantages of the
`invention will become more readily apparent from-the following detailed
`description of a preferred embodiment of the invention which proceeds
`with reference'to the accompanying drawings.
`
`quantized image data for use in decOmpressing the image. The second
`quantization table is related.to the first quantization table in the manner
`described above. When used to transmit and receive color images
`
`BRIEF DESCRIPTION or THE DRAWINGS
`is a block diagram of a prior art JPEG compression engine.
`
`Fig.
`
`OLYMPUS EX. 1016 - 13/714
`
`

`

`1 1
`
`Patent Application
`I
`.
`Attorney Docket Number 1094893-1
`
`1'9—\
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
`‘
`'Ove‘rview‘v 9'iithe' Quantization PrOcess
`The text and image enhancing technique according to the invention
`is integrated into the decoding 'or inverse} quantization step that is
`necessarily required by the JPEG standard. The invention integrates the
`two
`two different quantiZation tables: a first quantization table I
`(QE) for use
`quantizing the image data during the compression step and
`a second quantization table (QB) for use during the decode or inverse
`quantization during the decompression process; The difference between
`the two tables, in particular theiratio oi‘ the two} tables,» determines the
`amount ofimage enhancing that is dOne in the two steps. By integrating
`the image enhancing'and inverse quantization steps, themethod does not
`require any additiOnal Computations than already required for the
`compression and decompression processes.
`V
`In order to understand the operation ofthe invention, the following
`mathematical derivation is necessary. Let Q; be the second quantization
`
`Fig. 3 is a block diagram ofa prior art JPEG decOmpression engine.
`4' is a flow chart of a method of forming a scaled quantization
`table according totheinvention. '
`_
`V
`5
`is a drawing I of a JPEG compressed file including a
`quantization table scaled according to the inventibn.
`.
`6 is a block diagram ofa JPEG decompression engine according
`to theinvention.- -
`machine including JPEG
`Fig Tie a block diagram of a color
`compression and decompression engines according to the invention.
`
`table used during the decoding or inverse quantization step. Then let QD
`be related to‘ the first quantization table Q5, used duringthe quantization
`step, by the following expression:
`
`OLYMPUS EX. 1016 - 14/714
`
`

`

`QD:(s_xQE)+B-
`
`‘j
`
`>
`
`-
`
`Patent Application
`_
`I
`d
`Attorney Docket. Number 1094893-1
`
`._(1)
`
`uncompre'ssedimage and the CompreSSed image. The following derivation
`
`_
`r
`table QD.
`The matrix B is a so-called brightness matrix because it can affect
`the brightness of_ the image by changingthe DC level of the DCT
`elements. ‘ The elements of the B matrix can include iero' or non-zero
`values depending on the
`brightness. For purpOSes ofthe following
`discussion and derivatiOn; however, it will be assumed that the B matrix
`contains hero, elements onlyto simplify the derivation.
`The text and image enhancing technique of the invention uses a
`variance matrix to represent the statistical properties of an image. The
`variancematrix is an M x M matrix, where each element in the variance
`matrix is equal to' the variance of a corresponding DCT coefficient over
`the entire image. The variance is computed in the traditional manner, as
`is knovVn in the art.
`i
`.The edge enhancement technique in essence tries to match the
`
`where 'S is a sealing matrix, which scales each element of the first
`quantization? . table Q3 to
`corresponding element
`in the . second
`quantization table Q). The scaling matrix S is not used in a true matrix
`multiplication;
`rather,_ the multiplication is an element-by-element
`multiplication. Each element in the first quantization table QE has a
`corresponding element in the scaling matrix S that When multiplied
`together produce the cerresponding element in the second‘quantization
`
`variance [matrix ofa decompressed image (Vy- [k,l]) with a variance matrix
`of a reference image (V*[k',l]); The technique tries to match the two by
`Scaling the quantization table in the manner described above. In order
`to do this,th'e method takes advantage of the relationship between the
`
`OLYMPUS EX. 1016 - 15/714
`
`

`

`Patent Application
`.
`,
`Attorney Docket Number 1094893-1
`
`Vvlk,1].=V*lk,11]
`
`-
`
`'
`
`(2)
`
`However, the decompressed irnage (Y’) is relatedto the original quantized
`
`image (YQ') by the following expresSion:
`
`will make this relationship clear.
`‘VLet V*_[k,1] denote thehvarianzce ofthe [k,l] frequency component of
`a referenCe image. Ideally; this image contains those critiCal attributes
`that‘the technique seeks to preserve, for example, text. This variance
`matrix is of an ideal or reference image in that it is not rendered into
`color source image data by ascanner but, instead; is rendered into its
`ideal form by software, described further below. Thus, the color source
`image data of the’reference iInage dOes not suffer from the image
`degradation due to the inherent limitations ofthe scanner. Therefore, the
`Variance ofthe reference imageretains the high-frequency characteristics
`ofthe original reference image.
`I
`The method produces a resulting decompressed image that has
`approximately the Same Variance as the variance. of the reference by
`modifying the quantization table. Thus, the method produces the
`following relationship:
`
`The vai‘ian'cebf the deCOmpressed'image (VY) can then be expressed by
`
`Wk 11: YQE‘Lk, 11 Qn[k,- 11
`
`.
`
`g
`
`(3)
`
`Substituting equation (1) into equation (3) yields the following equation
`below:
`
`Wk 1] '= Yoslk, 1] (sag 1] QE[k, 1])
`
`»
`
`(4)
`
`OLYMPUS EX. 1016 - 16/714
`
`

`

`Wk, 1] = var (Y’[k,' 1.1) ‘2 Va? (sac; 1] Y§g[k, i], Qa[k, 1])
`
`.
`
`(5)
`
`Reducing this expression yieldsthe following:
`
`Vvtk, 11=Sik;11VY[k, 11
`
`I
`
`'
`
`-
`
`,
`
`(6)
`
`where Vi represents the variance of the original uncompressed image.
`Substitutingvequation (6) into equation (2) yields the following
`relationship between the sealing matrix S and the variances of the
`' reference image (V*) and the original image (Vy)_:’
`
`'S[k, 112 =‘ V*[k, 11/ Vyuc, 1],
`
`5
`
`(7)
`
`Therefore, the scaling matriii S can be used to‘boost the variance
`of the JPEG CompreSSed image to that of the reference image by
`appropriate formation of the scaling‘matrix. This method is shown in a
`more generalized fashion in FIG.‘ 4.
`
`the following expreSsion:
`
`Patent Application
`»
`I
`Attorney Docket Number 10948934
`
`/
`
`Preferred Embodiment of the Method
`_
`_
`In FIG; ‘4, a. method 62 of forming a scaled quantization table
`according to the invention is shown. The first step 64 is to generate a
`reference image. This reference image, in the preferred embodiment,
`embodies certain Valued features or elementsthat the method seeks to
`preserve. In the preferred embodiment, these critical elements include
`highly readable text such .as those typefaces having a serif font? e.g.,
`Times Roman. The Selection ofthe reference image is important becauSe
`it is the frequency or energy characteristics of this image that the text
`
`OLYMPUS EX. 1016 - 17/714
`
`

`

`15 a
`
`Patent Applicatiim
`g _-
`-
`Attorney Docket Number 1094893-1
`
`quality of the reference image."
`
`image gsharpenin'g method is intended to preserve. Because the method
`is statistical, the result can be irhproVed by averaging over a number of
`typical images; Examples ofsuch typical images are those using different
`fonts ‘(e.g., léalatino and Devanagari), handwriting, short-hand,
`line
`drawings, Sohematics, bar codes, etc. These different images can further
`be categOrized in a number‘of 'classes.
`This generating step 64 is performed on a computer, typically using
`a word processor or desktop publishing application such as Adobe
`Illustrator or Microsoft Word. The image is entered into the computer
`and then rendered by the application into reference image data by the
`application. The reference image data will be‘in the appropriate color
`space, e.g.,
`or RGB,
`to allow the subsequent step to be
`performed. This process can be achieved by first rendering the image into
`anAdobe PostSCript file
`then rendered into a bitemapped color Source
`image data 'file‘ using DisplayPostscript, Alternatively, other ' page
`description languages can be used to describe the image such as the PCL
`language by Here‘tt-Packard and then rendered into a bit map by an
`appropriate rendering program,
`' Once the ‘reference imageis generated and rendered into reference
`image data, the average energy."0f the reference image is deterinined in
`Step 66. In the preferred embodimentthis step includes computing the
`varianCe matrix (V*) for the reference image data. ' The variance matrix,
`as is known in theart, statistically represents thefrequency components
`or energy contained in the image; Unlike a scanned image, the reference
`image does not saffer from any-of the inherent limitations of the color
`scanner because it is net Compromised by the misregistration and MTF
`limitations of the scanner. Accordingly,‘the variance for the reference
`image retains the high-frequency energy that is critical to the visual
`
`OLYMPUS EX. 1016 - 18/714
`
`

`

`l 6
`
`*
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`transmitted for use in the decompression process. This difference
`
`In Step 68; ascanned image is scanned or selected from one or more
`stored pre-scanned ilnages; This scanned image is one that suffers from
`the inherent limitation of the‘9ca‘nne'r. ‘ This scanned? image can be any
`image, but in the preferredembodiment it is a scanned version cf the
`reference iinagegenerated in step 64, of the same type of image used
`V to form an averaged reference image.
`As in step 66, theaverage energy of the scanned image is then
`determined
`step
`The average energy again is represented by a
`variance matrix Y) of'thescanned image.
`‘
`The variance matrix (V*) of the reference image and the variance
`matrix (Vy) of the sCanned image are then used to compute the scaling
`matrix S
`step 72. This stepinvolves solving equation (7) above for
`each element in the scaling matrix S.'
`i
`Finally, in step 74 the scaled version of the quantization table is
`calculated. This step is'a’simple element-by-element multiplication as
`represented by equation (1) above.
`7
`i
`The use of the scale table's is seen clearly with reference to FIG. 5.
`In FIG. 5, a first set of Q tables 76