BAR CODE LABEL
`
`Ill“IIIIIIIIIlllllIlllHlIlHIIIHIIIIIIII
`
`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
`
`
`
`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
`
`that annqxed 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
`
`
`
`I
`
`Date
`
`Certifying Officer
`
`OLYMPUS EX. 1016 -1l714
`
`OLYMPUS EX. 1016 - 1/714
`
`

`

`BAH CODE LABEL
`
`
`fIIIIIIIIIIIIIIIHIUIIIIIIIIIIII
`_
`
`
`
`
`
`
`
`
`
`
`us FATENTAPPLICATION
`
`
`HMGMETIu
`
`‘SEHMLNUMBEH_.‘
`GROUPANTUNN
`
`
`
`
`‘ 08/4i11369-
`dé/ii/ésil‘*i
`fzsoégf
`
`
`
`GIORDANO _BERE'I'TAQ’ALOALTO,
`
`EVASUDEV”BHASKARAN,
`
`
`MOENTRIN VIEW CA;'
`' KONSTANTINOS KONSTANTINIDES,
`‘D“~I
`," 'v
`-
`.CA.‘ 1
`‘v
`‘
`-
`
`
` .;."_I **CONTINUING DATA*********************
`
`
`VERIEIED.
`
`"
`
`"
`
`-
`
`‘
`
`‘
`
`‘
`
` If **FOREIGN/PCT APPLICATIONS************ ‘7‘
`VERIFIED
`-
`
`
`
`
`'2 _EOREIGN Emma; EEdEN'SE"G'RANI‘T'EDJOfi/‘26j'95
`
`
`_
`V
`SHEETS'v .; "‘-
`
`
` FILING:FEE " I. ATTORNEY DOCKET ND.
`’ DRAWING '
`' HECHVED A
`7-':
` .$I,Isaiboi§ '[Ioéédaga I
`
`_ }MARGEE JOHNSONMCCOLLOM STOLOWITZ
`,
`.
`.7
`.
`,
`a
`
`
`
`..;1030_ sw M0RRIspN ST gir~i
`E'_I
`--
`1w:‘v
`_ ,_
`-: PORTLAND OR 97205fi‘: j
`=
`‘
`
`-h:
`ADDRESS
`
`'-
`
`'
`
`.
`
`-
`
`'
`
`3
`
` V1HTEXT ANE IMAGE SHARPENINEOF JPEG COMPRESSED IMAGESIN THE FREQUENCY
`
`
`,DOMAEN "
`-
`.,
`»
`-
`--
`
`
`This'Is To .dérfif thataim - 6 heretoIs a trué c6pyfrbm the recordsof the Unitéd States 1
`
`
`
`
`Patent and Tra einark Office of the aIppiicatiOn thdh'Is identifiéd above >
`'
`_
`
`
`
`By authority of tin;
`,
`-
`.
`
`COMMISSIDNER 0F PATENTS _AND TRADEMARKS
`-
`
`Date
`
`
`
` 7 :. Caflifyini DTiiEer I- > ‘
`
`OLYMPUS EX. 1016 - 2/714
`
`OLYMPUS EX. 1016 - 2/714
`
`

`

`HEWLETT-PACKARD COM FANY
`Legal Department, 2030
`,
`
`Palo Alto, California 943030590
`
`Marietta
`
`
`
`
`'
`
`'
`
`A'I'I'ORNEY DOCKET No.
`
`- 1 094893-1
`
`COMMISSIONER OF PATENTS AND'TRADEMARKS
`Washington, D.C. 20231
`Slr:
`
`Transmitted herewith fOr filing under 37 CFR 1 .53(b) is a(n):
`
`jggfifi‘fig
`
`"
`“a
`[WW ԡ~Ԥ9
`
`
`) 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
`(
`) Associate Power of Attorney
`
`) Priority document(s) (I (Other)
`,
`(fee$
`
`)
`
`CLAIMS As FILED BY OTHER THAN A SMALL ENTITY
`(2)
`»
`(3)
`(4)
`»
`NUMBER FILED
`NUMBER EXTRA
`RATE
`X $22
`
`(5)
`TOTALS
`
`X
`
`$76
`
`IIIIIIIIM$ 240
`
`(1)
`FOR
`
`TOTAL CLAIMS
`
`.
`
`INDEPENDENT
`CLAIMS
`ANY MULTIPLE
`DEPENDENT CLAIMS
`
`
`
`BASIC FEE: Design ( $3300.00 ); Utility ( $730.00)
`
`TOTAL FILING FEE
`
`N(dO
`
`1,153
`
`TOTAL CHARGES TO DEPOSIT ACCOUNT
`
`$
`
`1 ,158
`
`
`
`
`
`to Deposit Account 08-2025. At any time' during thefipendency 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.
`-
`'I" I b
`.
`63
`.
`00465
`Express Mai
`a el no T339
`Date of Deposit March 27 I 1995
`
`.
`
`_
`Respectfully SmeItted,
`
`I hereby certify that this Is'being deposited with the
`United States Postal Service IExpress Mail Post
`Office to Addressee' sen/ice under 37 CFR ._1 .10 on
`the date indicated aboveand is addressed to the
`Commissioner
`of
`Patents
`and
`Trademarks,
`Washingt
`,VD.C.20231-.
`
`By @@ kivaM—W
`Typed Name: Linda A. Iimura
`
`.
`
`By
`
`Giordano Beretta et al.
`..
`6' fi)1’
`I
`
`W
`
`C. Douglass homas
`
`Attorney/Agent for Applicant(s)
`Reg. No.
`32,947
`Date: March 27 , 1995
`
`Rey 10/94 (Form 3.04)
`
`- Attach as First Page to Transmitted Papers - Telephone N04 (415) 857'8129
`
`OLYMPUS EX. 1016 - 3/714
`
`OLYMPUS EX. 1016 - 3/714
`
`

`

`Attorney Docket Number 1094893-1
`
`1
`
`.
`
`‘
`
`Patent Application
`
`mass ,4
`
`
`'
`
`/ . 5
`[we 9
`
`'
`
`TEXT AND IMAGE SI-I‘ARPENING OF JPEG COM ESS_._
`
`
`'
`'8 IN THE FREQUENCY DOMAIN
`-'
`RELATED APPLICATION DATA .
`
`C“l 7
`
`.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`This application inCorPOrates subject matter disclosed in commonly-
`assigned application entitled. METHOD FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTH‘APPLICATIONS,
`_Ser. No. W7filed on even date hereWith.
`
`. BACKGROUND OF THE INVENTION
`
`invention relates to data compression using the JPEG
`This
`Compression standard for continuous- tone still'Images, both grayscale
`and color.
`V
`_
`,
`V
`~A cemmittee" known as "JPEG," whiCh stands for "Joint
`PhOtographic EXperts Group," hase'stablished a standard for compressing
`continuous—tone stillImages, bOth grayScale and color. This standard
`represents a cOmpromise between reproducible image quality and
`compression rate. To achieveECCeptablecompression rates, which refers
`to the ratio of the uncompreSSed'1mage 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'image, on the order Of 10 megabytes for a 200
`dots per inch (DPI) 85" x 11" image. By carefully implementing the
`JPEG Standard, however, the loss.1n 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.
`Figure 1 shows a block diagram of a typical implementation Of the
`
`
`
`OLYMPUS EX. 1016 - 4/714
`
`OLYMPUS EX. 1016 - 4/714
`
`

`

`
`
`
`
`2
`
`‘
`
`Patent Application
`Atttn'ney 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 sOurce image in a given. color space such as
`CIELAB. The source image data has a certain réSolution, whichis
`determined by how theimage 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 number of bits-used to represent the
`image pixel;
`I
`L
`l
`The, source_imagedata is typically forfnatted as a raster stream
`of data. The cOmpression technique, however, requires the data to be
`represented in bIO'cks. These blocks represent a two-dirtiensional pertion
`of the source image data. The JPEG standard uses .sxs blacks 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 theproper format for the next stage in the compression
`process. These 8X8 blocks are then’ forwarded to a di5crete cosine
`transformer 16 via bus 14.
`The discrete cosine transformer 16 converts the s0urce image data
`_ into transforrhedimage data using the discrete cesine transform (DCT).
`
`The DCT, as is known'1n the art of1mage processing, decomposes the 8x8
`block of source image data into 64 DOT elements or coefficients, 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 DCT space. These basis vectors can be
`intuitively 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 cesine (FDCT)
`function as shown below, hence the name.
`
`,10-
`
`15
`
`20
`
`25
`
`
`
`OLYMPUS EX. 1016 - 5/714
`
`OLYMPUS EX. 1016 - 5/714
`
`

`

`
`
`
`
`3
`
`‘
`
`’
`
`Patent Application
`_
`r
`Attorney Docket Number 10948934
`
`7
`
`7
`
`flu, .<2y+_1)11=
`22
`—
`Y[k,l]= 4C(k)0C(1)L=oy=OS(x,y)0cos
`16
`os
`16
`where: C(k), C(l)'=. I/fiforkd= 0; and
`
`_ C(k), (3(1) = 10therwise
`
`The Output of the transformer 16 is an 8x8 block of DCT elements
`or coefficients, Corresponding to the DCT basis vectors This block of
`transformed'1mage data13 then forwarded to a quantizer 20 over a bus
`18. The quantizer 2O quantizes the 64 DCT elements using a 64—element
`quantization tab1e24,~ which must be. specified as an input to 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 DCT coefficient. The purpose of
`quantization is to achieve the maximum amount of compression by
`representing DCT coefficients with no greater precision than15 necessary
`to achieve the desired image quality, Quantization is a many-to-one
`mapping and, therefore, is fundamentally lo'ssy. As mentioned above,
`Quantization tables have been designed 'which limit the lossines's to
`imperceptible aspects of the1mage so that the reproducedimage is not
`perceptually different frOm the Source image
`The quantizer 20 performs a simple division operationbetween each
`DCT cOefiicient and the corresponding quantization table element. The
`lossiness occurs because the quantizer 20 diSregards any fractional
`
`remainder. Thus, the quantization function can be represented as shown
`
`in Equation 2 belOW.
`
`10
`
`15
`
`20
`
`25
`
`I YQlk; 1] = IntegerRound(X[%]—)
`
`
`
`OLYMPUS EX. 1016 - 6I714
`
`OLYMPUS EX. 1016 - 6/714
`
`

`

`
`
`
`
`4
`
`Patent Application
`.
`'
`Attorney Docket Number 1094893-1
`
`where Y(k,‘l) 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:
`
`Y’[k, l] = Yq[k,'l] Qg[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 .effdrts 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 entropyencoder 28. The entropy encoder 28 is coupled
`to the quantizer 20 via a bus 22 for receiving the quantizedImage 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,
`' Hoffman coding and arithmetic coding.
`The
`compression engine of Fig. 1 assumes Huffman coding is used. Huffman
`encoding, as is 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 ofl05sless Compression. Accordingly, the operation
`of the entropy encoder ‘28-'is not further described. ,
`Referring now to' Fig. 2, a typical JPEG compressed file is shown
`
`10
`
`15
`
`20
`
`25
`
`E“.\
`
`OLYMPUS EX. 1016 - 7/714
`
`OLYMPUS EX. 1016 - 7/714
`
`

`

`
`
`
`
`. 5
`
`Patent Application
`Attorney Docket Number 1094893-1
`generally at 34. The compressed file includes a JPEG header 36, the
`quantization (Q) tables 38 and the Huffman (H) tables 40 used'1n the
`compression process, and the compreSSed'1mage data 42 itself. From this
`compressed file 34 a perceptually indistinguishable version ofthe original
`source image can be extracted when an appropriate Q-table'13 used. This
`extraction process is described below with reference to Fig. 3.
`._
`I
`A JPEG decompression engine 43 is shown in Fig. 3. The
`decompression engine essentially operates1n reverse ofthe compression
`engine 10. The decompression engine receives the compressedimage data
`at a header extraction unit 44, which extracts the H tables, Q tables, and
`compressed image data according to the information contained1n the
`header. The H tables are then stOredm H tables46 While the Q tables
`are stored111 Q tables 48. The CompreSSed'1mage data'1s then sent to an
`entropy deCoder '50 over a‘bus 52. The'Entrop'y Decoder decodes the
`Huffman encoded compressed'1mage data using the H tables 46. The
`output of the entropy decoder 50 are the quantized DCT elements.
`The quantized DCT elementsare then transmitted to an inverSe
`quantizer 54 over a bus 56. The inverse Quantizer 54 multiplies the
`quantized DCT elements by the corresponding quantization table
`elements found in Q tables 4.8 As described above,
`this inverse
`quantization step does not yield the original scurce‘ image data because
`the quantization step trhncated or discarded the fractional remainder
`before transmission of the compressed"1mage data.
`I Themverse quantized DCT elements are then passed to an inverse
`discrete cosine transformer (IDCT) 57 via bus 59, which transforms the
`data backrlinto the time domain using the inverse discrete cosine
`transform (IDCT); The inverse tranSforrned data issthen transferred to
`block-to-raster translator 58' (were bus 60. where the blocks of DCT
`
`elements are translated into a raster string ofdecompressed source image
`
`10,
`
`'
`
`15
`
`20
`
`25
`
`OLYMPUS EX. 1016 - 8/714
`
`OLYMPUS EX. 1016 - 8/714
`
`

`

`
`
`
`
`'6
`
`10
`
`'15
`
`20
`
`25
`
`l
`
`l
`
`Patent Application
`,
`Attorney Docket Number 1094893-1
`data. From the‘decompr'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 iJnage.
`As desoribed above, the quantizationstep produces some lossiness1n the
`process ofcompressmg the data. By carefully designing the quantization
`tables, however, the prior art methods have constrained the 1035 to
`visually imperceptible portions of the1mage, These methods, and their
`shortcomings, are described below.
`.
`The JPEG standard includes two examples of quantization tables,
`one for luminance channels and one for chrominance channels. See
`International Organizationfor-Standardization: "Informa'tibn technology
`' - digital compression encodingof continuous- tones still'1mages- part 1:
`Requirements and Guidelines, " ISO/IEO 1810918—1, October 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'1nthe YUV color space.
`These tables result1n visuallypleasingimages, but yield a rather
`low compression ratio-fer certain applications. The compression ratio can
`be varied by setting a so--called Q-factor or scaling factor, Which is
`essentially a uniform multiplicative parameter that1s 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 tablesare
`carefully designed to be perceptually lossless, hoWever, a large Q—factor
`will introduce artifacts'1n the reconstructedunage, Such as blockiness'm
`areas ofconstant color or ringing in text-scale characters. Some ofthese
`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
`separately. However, such methods easily introduce new artifacts.
`
`OLYMPUS EX. 1016 - 9/714
`
`OLYMPUS EX. 1016 - 9/714
`
`

`

`
`
`
`
`7
`
`-
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`Therefore, these methods are not ideal.
`As a result ofthe 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. These’methods are also designated as being based on the
`removal of Subjective 0r 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 herein by
`reference.
`Quantization'1s not the.only cause of1mage degradation. The color
`s'ource image data itself might be cOmpromised._ For scanned colored
`images, the visual quality cf the1mage canbe degraded because of the
`inherent limitations of color soanners. These limitations are mainly of
`two kinds:
`limited modulation tranSfer function (MTF)
`and
`misregistration.
`The . modulat1on transfer function refers to the
`mathematical representation or transferfunction ofthe scanning process.
`There are inherent limitations in representing the sCanning‘process by
`the MTF and these limitations are the main cause ofpixel aliasing, which
`produces fuziy black text glyphs ofgrayish appearance. Misregistration,
`on the Other hand,- refers to the relative misalig‘nméntdf the scanner
`sensOrs for the various frequency bands. For example, the Hewlett
`Packard scan Jet IIcTM has a color misregistration tolerance of+/- 0.076
`mm for red and blue with respect
`to green.-
`This amount of
`misregistration1s signifiCant considering the size ofan image pixel (e.g..,
`0.08 mm at 300 dots per inch (dpi)).
`.
`These limitations Significantly degrade text in color images because
`sharp edges arevery important for reading efficiency. The visual quality
`
`10
`
`15
`
`2O
`
`25
`
`
`
`OLYMPUS EX. 1016 -10I714
`
`OLYMPUS EX. 1016 - 10/714
`
`

`

`
`
`
`
`8 i
`
`'
`
`Patent Application
`1
`.
`Attorney Docket Number 1094893-1
`
`of text can be improved, however,using prior art edge enhancement
`techniques. Edge enhancement can be performedin either the spatial
`or frequency domain. In the spatial domain (1e., RGB) edge crispening
`can be performed by discrete convolution of thescanned'nnage with an
`edge enhancement kernel. This approach"is equivalent to filtering the
`image with a high-pass filter. However, this technique1s computationally
`intensive. An M x N cOnvolution kernel, for example, requires MN
`. multiplications and additions per pixel.
`For edge sharpening1n the frequency demain, the fullimage is first
`. transformed into.thefrequency domain usingtheFast FourierTransform
`(FFT) or
`the Discrete .,Fourier Transform (DFT),
`lbw frequency
`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. camputationally intensive;
`. Moreover, it uses a
`transformation differentthan that required bythé 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 OF THE INVENTION
`The invention is a method of compressing and decompressing
`images which comprises using onequantization table (QB) for compressing
`the image and a secOnd quantizatiOn table (QB) far decompressing the
`image.
`In general, compression and decompreSSion are performedin
`conformance with the JPEG'standard. The second quantization table Q;
`is relatedto the first quantization table aCCOrding tothe following general
`expression:
`
`10
`
`1.5
`
`'20
`
`25
`
`QD=SXQE~+B1
`
`OLYMPUS EX. 1016 - 11/714
`
`OLYMPUS EX. 1016 - 11/714
`
`

`

`
`
`
`
`9 V
`
`Patent Application
`'
`Attorney Docket Number 1-0948931
`
`where S is a Scaling matrix having each element S[k,l] formed according
`to the following expression:
`
`sum = 'V*[k,1'1/v-Y[k,1i
`
`10
`
`15
`
`20
`
`25
`
`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 additi0nal computational requirements. According to the
`invention, the“quantization table QD is transmitted With the encoded
`quantizedimagedata, and'is used'in decompression to recover the'image.
`Thereference1mage is a preselected Continuous-toneimage, either
`grayscale or color depending onthe'images to be processed. The reference
`image is rendered into a target image file. The target image file'is not
`generated by a scanner, Sothe 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 the image, retains the high-frequency components.
`The reference iinage can be any continuous-tone image, but in the
`preferred embodiment the referenceimage includes text with a seriffont
`because the seriffonthas goad visual quality which the method preserves.
`The scanned'image, although it can be any image, in the preferred
`embodiment is a printed Version of the reference image. Thus, the
`variance of the scanned image represents the energy or frequency
`composition of.theyreference image but which is comprOmised‘ by the
`inherentili‘mitationsOfthe scanner. The Scaling matrix, therefore, boosts
`the frequency components that are compromisedby the scanning process.
`
`
`
`
`
`OLYMPUS EX. 1016 - 12/714
`
`OLYMPUS EX. 1016 - 12/714
`
`

`

`
`
`
`
`1 0
`
`.
`
`Patent Application
`1
`'
`Attorney Docket Number 1094893-1
`
`*
`
`A preferred embodiment ofthe invention15 deScribed herein'1n the
`context ofa color facsimile (fax) machine. The colorfax maChjne includes
`a scanner for rendering a color'nnage 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
`encapsulatingthe compressed image data, and a means for transmitting
`the encapsulated data. The compression engine includes means for
`storing two quantization tables. The first quantization table1s used to
`quantize the'imagedata transformed using the discrete cosine transform
`(DCT). The second quantization tableis encapsulated withthe encoded
`
`quantized1mage data for use in decOmpressing theImage. The second
`quantization table111 relatedto the first quantization table1n the manner
`described above. When used to transmit and receive color images
`
`between two locations, the machine transfers the images with higher
`
`quality than priorsystems.
`The second quantization table can be precomputed and storedin 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.
`
`10
`
`15
`
`20
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`,
`Fig. 1 is a block diagram of a prior art JPEG compression engine.
`Fig. 2 is a drawing of a typical format of a JPEG compressed file.
`
`OLYMPUS EX. 1016 - 13/714
`
`OLYMPUS EX. 1016 - 13/714
`
`

`

`
`
`
`
`1 1
`
`Patent Application
`I
`Attorney Docket Number 1094893-1
`
`Fig. 3 is a block diagram ofa prior art JPEG decOmpression engine.
`Fig. 4 is a floW chart Of a method offorming a scaled quantization
`table according to the invention.
`Fig. 5
`is a drawing of a JPEG compressed file including a
`quantization table scaled according to the inventibn.
`. Fig. 6 is a block diagram ofa JPEG decompression engine according
`to theinvention.- -
`Fig 7is a block diagram of a color fax machine including JPEG
`compression and decompression engines according to the invention.
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
`Overview 9: the Quantization PrOcess
`The text and1mage 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 by using two different quantization tables: a first quantization table .
`(QE) for use in quantizing themage data during the compression step and
`a second quantization table (QB) for use during the decode or inverse
`quantization duringthe decompression process The difference between
`the two tablés,’1n particular the ratio of the two tables, determines the
`amount ofimage enhancing thatis dOne1n the two steps. By integrating
`the'nnage enhancingandmverse quantizatiOn steps, the method 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 derivation1s necessary. Let Q; be the second quantization
`
`table used during the decoding or' inverse quantization step. Then let QD
`be related to‘ the first quantization table Q'E, used duringthe quantization
`Step, by the following expression:
`
`10
`
`15
`
`20
`
`25
`
`1%
`
`
`
`OLYMPUS EX. 1016 - 14/714
`
`OLYMPUS EX. 1016 - 14/714
`
`

`

`
`
`
`
`‘
`
`.
`
`1.2
`,
`
`'
`
`V
`
`.
`
`Patent Application
`_
`.
`'
`’
`Attorney Docket. Number 1094893-1
`
`QD:(s_xQ..)+B-
`
`‘j
`
`>
`
`._(1)
`
`where 'S is a sealing matrix, which scales each element of the first
`quantization table QE to a corresponding element
`in the second
`quantization table QD. The scaling matrix S1s not used'1n a true matrix
`multiplication; rather, the multiplication is an element-by-element
`multiplication. Each elementin 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
`
`table QD.
`The matrix Bis a so-called brightness matrix because it can affect
`the brightness of the image by changing the DC level of the DCT
`elements. The elements of the B matrix can include zero or non-zero
`values depending on the desired brightness. Forpurpbses ofthe following
`discussion and derivatiOn, however, it will be assumed that the B matrix
`contains zero elements onlyto simplify the derivation.
`The text and1mage 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
`
`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
`uncompressedimage and the Compressed image. The following derivation
`
`10
`
`15
`
`.20
`
`25
`
`a/W
`
`OLYMPUS EX. 1016 - 15/714
`
`OLYMPUS EX. 1016 - 15/714
`
`

`

`
`
`
`
`. 13
`
`Attorney Docketlgifigzfljggfggfi
`
`will make this relationship clear.
`‘VLet V*_[k,1] denote thevariance ofthe [k,l] frequency component of
`a referenCe image. Ideally, this image contains those critiCal attributes
`thatthe 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 dees not suffer from the image
`degradation due to the inherent limitations ofthe scanner. Therefore, the
`Variance ofthe reference imageretains the high-frequency characteristiés
`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:
`
`Vvlk,1].=V*lk,lll
`
`-
`
`'
`
`(2)
`
`However, the decompressed irnage (Y’) is relatedto the original quantized
`
`image (YQ') by the following expreSSion:
`
`1Y’[k,ll= Ylek,llQu[k,-ll
`
`.
`
`.
`
`‘
`
`(3)
`
`Substituting equation (1) into equation (3) yields the following equation
`below:
`
`Y’[k, 1] '= Yam, 1] (S[k,‘ 1] Q2[k, 1])
`
`»
`
`(4)
`
`The vai‘ian‘cebf the denompr'essed'image (Vup) can then be expressed by
`
`10
`
`15
`
`20
`
`25
`
`“7“;
`
`It)...”
`
`’—
`
`OLYMPUS EX. 1016 - 16/714
`
`OLYMPUS EX. 1016 - 16/714
`
`

`

`
`
`
`
`1 4 I
`
`V
`
`V
`
`Patent Application
`»
`’
`Attorney Docket Number 1094893'-1
`
`the following expreSsion:
`vane, 11 = val? {rug 1.1)evva15 (S‘[_k,vl]i Yang, 11Qa[k, 1])
`
`.
`
`Reducingthis expression yields‘the following:
`Vvtk, 1] = Sang, l]lfy[k,11]
`,
`.
`‘
`.
`
`(5)
`
`,
`
`(6)
`
`10
`
`15
`
`20
`
`25
`
`where Vi represents the variance of the original, uncompressed image.
`Substitutingvequation (6) into. equation (2) yields the following
`relationship between the scaling matrix S and the variances of the
`' reference image (V*) and the original image (Vy)_:’
`
`'S[k, 112 =‘ v*[k. 11/ VY1k.11,
`
`*
`
`(7)
`
`Therefore, the scaling matrix 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 method18 shown'1n a
`more generalized fashion'1n FIG. 4.
`
`Preferred Embodiment of the Method
`_
`_
`In FIG. 4, a. method 62 of forming a scaled quantization table
`according to the invention is shdwn. The first step 641s to generate a
`reference image. This referenceimage, in the preferred embodiment,
`embodies certain Valued features or elements that 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 this1mage that the text
`
`
`
`11,
`
`OLYMPUS EX. 1016 - 17/714
`
`OLYMPUS EX. 1016 - 17/714
`
`

`

`
`
`
`
`1 5
`-
`
`l
`
`.
`
`Patent Application
`'
`'
`Attorney Docket Number 1094893-1
`
`image sharpening method'is intended to preserve. Because the method
`is statistical, the result can be imprOVed by averaging Over a number of
`typical1mages. Examples ofsuch typical1mages are those using different
`fonts (e.g., Palatino and DeVanagari), handwriting, short-hand,
`line
`draWings, schematics, bar codes, etc. These different images can further
`be categOrized1n a numberof classes.
`This generating step 64'1s 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 bein the appropriate color
`space, e.g.., CIELAB or RGB,
`to allow the subsequent step to be
`performed. This process can be achieved byfirst rendering the'image into
`an Adobe PostSCript file and then rendered into a bit-mapped colorsource
`image data file using DisplayPostscript Alternatively, other page
`description languages can be used to desoribe the'1mage such as the PCL
`language by Hewlett Packard and then rendered into a bit map by an
`appropriate rendering program.
`A
`Once the reference1mageis generated and rendered into reference
`image data, the average energyof the reference'image is deterinined1n
`step 66. In the preferred embodiment, this step includes computing the
`varianCe matrix (V*) fer the referenceimage data. The variance matrix,
`as is known1n theart, statistically represents thefrequency components
`or energy containedin the1mage. Unlike a scanned1mage, the reference
`image does not suffer 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
`quality of the referenceunage;
`
`10
`
`15
`
`20
`
`25
`
`OLYMPUS EX. 1016 - 18/714
`
`OLYMPUS EX. 1016 - 18/714
`
`

`

`
`
`
`
`l 6
`
`*
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`In Step 68, aScanned image is scanned or selected from one or more
`v
`‘
`stored pre-scannedimages. This scanned'1mage is one that suffers from
`the inherent limitation of the Scanner. This scanned'1mage can be