`
`cr U.S. PATENT APPLICATION
`
`SERIAL NUMBER
`
`08/411, 369
`
`FILING DATE
`
`03/27/95
`
`GROUP ART UNIT
`
`2613
`
`APPLICANT
`
`GIORDANO BERETTA, PALO ALTO, CA; VASUDEV BHASKARAN, MOUNTAIN VIEW, CA;
`KONSTANTINOS KONSTANTINIDES, SAN JOSE, CA.
`
`XXCONTINUING DATAS #84 ERR AAR RAMEE KEE
`VERIFIED
`
`_ **FOREIGN/PCT APPLICATIONS**** eek x ARK
`VERIFIED
`
`FOREIGN FILING LICENSE GRANTED 04/26/95
`
`TOTAL
`
`INDEPENDENT
`CLAIMS
`
`ATTORNEY DOCKET No.
`
`36
`
`.
`
`$1,158.00
`
`10940893
`
`ADDRESS
`
`RECORDS MANAGER
`LEGAL DEPARTMENT 20B0
`HEWLETT PACKARD COMPANY
`PO BOX 10301
`PALO ALTO CA
`
`94303-0890
`
`TEXT AND IMAGE SHARPENING OF JPEG COMPRESSED IMAGES IN THE FREQUENCY
`DOMAIN
`
`Certifying Officer
`
`This is to certify that annexed hereto is a true copy fromthe records of the United States
`Patent and Trademark Office of the application which is identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Date
`
`~HUAWEI EX. 1016 - 1/714
`
`HUAWEI EX. 1016 - 1/714
`
`
`
`
`
`
` un|
`
`
` | SERIAL NUMBER ©
` GROUP ART UNIT
`| FILING DATE:
`
`
`
`-08/411,369.
`©2608
`GeouwzainRecA
`
`
` ~ GIORDANOaeanto,) AFVASUDEV._BHASKARAN,
`APPLICANT
`
`: KONSTANTINOS KONSTANTINIDES
`
`
`
`s +-cowerirNe. DATAnian
`
`
`VERIFIED » os ane
`
`
`
`
`;
`
` © rszonszen/zctAPPLICATIONS*tasatasanie
`
`_VERIFIED
`
`.
`
`an
`
`
`
`FOREIGNFILING,LICENSEGRANTED04/26/95DA Rs
`
`"| RECEIVED. ~~ PATTORNEY DOCKETNO,
`PUNGHE..
`
`
` $1,158.00° “10940893",
`
`“MARGERJOHNSON “HCCOLLOM-STOLOWIT2”
`
`ADDRESS
`
`
`
`»:. 1030 SW MORRISON. ST 080...
`.° PORTLAND OR 97205-
`
`TEXT AND IMAGE SHARPENING‘OF JPEG:‘COMPRESSED. IMAGES-IN THE“FREQUENCY
`
`DOMAIN . woe .
`
`
`
`
`- ‘
`
`‘This is‘to certify thataiinexéd
`retoisa trie copyfrom the records:oftheUnitedStates
`
`
`
`
`Patent and:Tra emark OfficeOF.the> application witich is identified above,
`
`
`
`" By authorityof the
`.
`“COMMISSIONER OFPATENTSAND ADEA.
`
` Date.
`*~ Certifying Officer ied
`
`HUAWEI EX. 1016 - 2/714
`
`HUAWEI EX. 1016 - 2/714
`
`
`
`HEWLETT-PACKARD.COMPANY
`Legal Department, 20BO |
`
`Palo Alto, California 94303-0890 ATTORNEY DOCKET No,_1094893-1
`
`ard:411369
`LegalDepart
`
`
`
`
`. COMMISSIONER OF PATENTS AND ‘TRADEMARKS
`Washington; D.C. 20231
`,
`Sir:
`
`Transmitted herewith forfiling under 37 CFR.1.53(b) is a(n): (<) Utility—() Design
`X) original patent application,
`( ) continuing application,
`( ). continuation-in-part
`{
`) continuationor
`(_) divisional
`of S/N
`filed
`
`
`
`INVENTOR(S): GiordanoBeretta etal.
`
`TITLE:
`
`TEXT AND IMAGE SHARPENING OF. JPEG COMPRESSED IMAGES IN THE
`FREQUENCY. DOMAIN
`
`Enclosedare:
`) unsignedor partially signed
`(
` (X) signed.
`(xX) The Declaration and Power of Attorney.
`-.(
`)
`informal drawings
`(one set)
`(X)
`_7
`sheets of (X) formal drawings:
`( ) Information Disclosure Statementand Form PTO-1449
`(
`) Associate Powerof Attorney
`() Priority document(s) () (Other
`_
`(fee $
`
`)
`
`CLAIMS AS.FILED BY OTHER THAN A SMALL ENTITY
`()
`:
`)
`(4).
`NUMBERFILED
`NUMBER EXTRA
`RATE
`
`a mS
`
`(1)
`/ FOR
`TOTAL CLAIMS
`
`INDEPENDENT
`CLAIMS
`
`ANY MULTIPLE.
`DEPENDENT.CLAIMS
`
`6)
`TOTALS
`
`wn Jce>)
`
`An
`
`‘Jo
`
`
`
`
`
`
`
`
`
`
`
`:
`
`-
`
`TOTAL.FILING FEE
`
`TOTAL CHARGES TO DEPOSIT. ACCOUNT
`
`'
`
`$
`
`1,158
`
`to Deposit Account 08-2025...At any timeduring the pendency of this application,
`1,158 _
`Charge $
`please charge any fees required or credit any.over paymentto 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. -
`.
`"
`il" |
`y
`65.
`Respectfully submitted,
`Express Mail"
`label_no. TB39630041
`Date of Deposit. March 27, 1995
`Giordano Berettaetal.
`| -herebycertify that this is being deposited with the
`United States: Postal
`‘Service “Express .Mail-.Post
`.
`C A
`Office: to. Addressee" service under 37 CFR.1.10 on
`we
`#
`|
`By
`the date indicated. above and is addressed to.the
`
`
`Commissioner -of.Patents and Trademarks,
`
`Washington, D.C.:20231,
`C. Douglass Thomas
`By Lalit ren
` Attorney/Agent.for Applicant(s)
`Typed Name?LindaA. limura
`Reg. No.
`32,947
`Date: March 27, 1995
`TelephoneNo.: (415) 857-8129
`
`Rev 10/94 (Form 3.04)
`
`- Attach as First Page to Transmitted Papers -
`
`_
`
`HUAWEI EX. 1016 - 3/714
`
`HUAWEI EX. 1016 - 3/714
`
`
`
`
`guise 4%
`
`1
`
`AttorneyDocketNumber 1094893-1
`
`Patent Application
`
`-.
`
` 5
`
`G04
`
`
`.
`IN THE FREQUENCY DOMAIN
`
`e 7 | aAPPLICATIONDATA -
`This applicationincorporates subjectmatterdisclosedincommonly-
`assigned application entitled . METHOD. FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTHAPPLICATIONS,
`Ser. No. oe GSESi7filed on even date herewith.
`
`- BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`20
`
`25
`
`30
`
`invention rélates to data compression using the JPEG
`This
`: compression standard for continuous- tone still images, both grayscale
`and color.
`|
`;
`.
`A committee known as "JPEG," which stands. for "Joint
`PhotographicExperts Group," hasestablished a standardfor compressing
`continuous-tone still iimages, both grayscale and color. This standard
`represents a compromise between reproducible image quality and
`compression rate. To achieve:acceptable compressionrates, which refers
`to the ratio of the uncompressediimage to the compressed image, the
`JPEG standard.adopted a lossy compression technique. The lossy
`compressiontechnique was required given the inordinate amount ofdata
`| neededto represent a color image, on the order of 10 megabytesfor a 200
`dots.per inch (DPI)8.5" x11" image. By carefully implementing the
`JPEG standard, however, the loss in theimage can be confined to
`imperceptible areas ofthe iimage, which produces a perceptuallyloss 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 diagramofa typical implementation ofthe
`
`f
`
`7é NX
`
`HUAWEI EX. 1016 - 4/714
`
`HUAWEI EX. 1016 - 4/714
`
`
`
`
`
`
`
`a2
`
`Patent Application
`Attorney.Docket Number 1094893-1
`JPEG.compressionstandard.Theblock diagram will be referred to as a
`compressionengine. The compressionengine 10operates on sourceimage
`- data, which represents a source image ina given. color space such as
`CIELAB. The source image data has a certain resolution, which is
`determined by how theiimage was captured. Each individual datumof |
`the source image data represents an image pixel. The pixel further has
`a depth whichis determined by the numberofbitsused to represent the
`imagepixel.
`|
`‘The source image data.
`is: typically formatted as a raster stream
`of data. The compression technique, however; requires the datato be
`representedin blocks. These blocksrepresent 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
`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 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 knowniin the art ofiimage processing, decomposesthe 8x8
`block of sourceimage data into 64 DCT elements or coefficients, each of
`which correspondsto 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 representuniqueimages, wherein any sourceimage
`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.
`-
`
`“105:
`
`15
`
`20
`
`25
`
`
`
`HUAWEI EX. 1016 - 5/714
`
`HUAWEI EX. 1016 - 5/714
`
`
`
`
`
`
`
`7
`
`7
`
`,
`
`x=0y=0
`
`:
`
`Y[k,1] =qocolZsaSp
`where: Cdk), ca)=“yr/Btork,1 = 0; and
`C00), cq)= J otherwise
`The outputof the transformer 16is an 8x8 block of DCT elements
`or coefficients, corresponding to. the DCT basis vectors. This block of
`transformediimage data is then forwarded to a quantizer 20 over a bus
`18. The quantizer 20 quantizes the 64 DCT elements using a 64-element
`quantization table 24, which must be specified as an input to the
`compression engine 10. Eachelement of the quantization table is an
`integer value from ore 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
`representingDCTcoefficientswithnogreaterprecisionthanis necessary
`to achieve the desired image quality. Quantization is a many-to-one
`mapping and, therefore,iis fundamentally lossy. As 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 sourceimage,
`_
`|
`Thequantizer20 performs a simple divisionoperationbetweeneach
`DCTcoefficient and the corresponding quantization table element. The
`lossiness occurs: because the quantizer 20 disregards any fractional
`remainder. Thus,the quantization function canbe represented as shown
`in Equation 2 below.
`
`3
`
`,
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`(2y+1)In
`16
`
`10
`
`15
`
`20
`
`25
`
`| Yolk] = IntegerRound(HE!L)
`
`HUAWEI EX. 1016 - 6/714
`
`HUAWEI EX. 1016 - 6/714
`
`
`
`
`
`
`
`4
`
`Patent Application
`:
`Attorney Docket Number 1094893-1
`where Y(k,]) represents the (k,1)-th DCT element and Q(k,) 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 coefficient.. The inverse quantization step can be
`represented by the following expression:
`
`Yk, 1] = Yolk,1] Qelk, 1.
`
`10
`
`16
`
`20
`
`25
`
`the fractional part discarded during the
`As should. be apparent,
`quantization step ig not restored. Thus, this information is lost forever.
`Becauseofthe potential impact on theiimage quality ofthe quantization
`step, considerable effort has gone into designingthe quantizationtables.
`These efforts are described further below following a discussion of the
`final step iin the JPEG compressiontechnique.
`_.
`The final step ofthe JPEG standardiis an entropy éncoding, which
`is performed by an entropy encoder 28. ‘The entropy encoder 28is coupled
`to the quantizer 20 via abus 22 for receiving the quantized image data
`therefrom. The entropy encoderachieves additional lossless compression
`by encoding the quantized DCTcoefficients more compactly based on
`their statistical characteristics. The JPEG standardspecifies two entropy
`coding methods: Huffman coding and arithmetic coding.
`The
`compression engine ofFig. 1 assumes Huffmancoding is used. Huffman
`encoding, as is known in the art, usés one or more sets of Huffman code
`tables 30. These tables may be predefined or computed specifically for a
`givenimage. Huffman encoding is awellknown encodingtechnique that
`produces high levelsoflossless compression.. Accordingly, the operation
`of the entropy encoder 28 is not further described.
`Referring now toFig. 2, a typical JPEG compressed file is shown
`
`
`
`HUAWEI EX. 1016 - 7/714
`
`ae
`
`e
`
`HUAWEI EX. 1016 - 7/714
`
`
`
`
`
`
`
`5
`
`5
`,
`PatentApplication
`AttorneyDocketNumber 1094893-1
`generally at34. 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 compressediimage data42 itself. From this
`compressedfile34 aperceptuallyindistinguishableversionoftheoriginal
`source image can be extracted when an appropriate Q-table iis used. This
`extraction process is described below with reference to Fig. 3.
`AJPEG decompression engine 43 is shown in’Fig. 3. The
`decompression engine essentially operatesirin reverse ofthe compression
`engine 10. The decompression engine receives the compressediimage data
`10 ata header extraction unit 44, which extracts the H tables, Q tables, and
`compressed image data according to the information contained iin the
`header. The H tables are then storediin H tables 46 while the Q tables
`are stored iinQ tables 48. The compressediimage data iis then sent to an
`entropy decoder 50 over a bus 52.. TheEntropy Decoder decodes the
`Huffman encoded compressediimage data using theH tables 46; The
`output ofthe entropy decoder50 are thequantized DCT elements.
`The quantized DCT élementsare then transmitted to an inverse
`quantizer 54 over a bus 56.
`‘Theinverse quantizer 54multiplies the
`quantized DCT elements by the corresponding quantization table
`elements found in “Q tables8. As described above, this inverse
`quantization step does not yield the original source image data because
`the quantization step truncated or discarded the fractional remainder
`before transmission ofthe compressediimagedata.
`Theiinverse quantized DCT elements are then passed to an inverse
`2.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 iinverse transformed data isthen transferred to
`block-to-raster translator 58° over a bus 60. where the blocks of DCT
`elementsare translated into a raster string ofdecompressed source image
`
`15
`
`|
`
`20
`
`HUAWEI EX. 1016 - 8/714
`
`HUAWEI EX. 1016 - 8/714
`
`
`
`
`
`
`
`6
`7
`Patent Application
`Attorney Docket Number 1094893-1
`data.. From the decompressed source image data, a facsimile of the
`original source image can be.reconstructed The reconstructed source
`image, however,iis not.an exact replication ofthe original source image.
`As described 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 ofthe iimage. Thesé methods, and their
`shortcomings, aredescribed below.
`The JPEGstandard includes two examples ofquantization tables,
`one for luminance channels and one for chrominance channels. See
`International OrganizationforStandardization: "Information technology
`- digital compression encodingof continuous- tonesstill images- part 1:
`Requirements and. Guidelines, "ISOAEC 1S10918-1, October 20, 1992.
`These tables are known as the K.1 and K.2.tables, respectively. These
`tableshavebeen designedbased'ontheperceptuallylossless compression
`of color images representediin the YUV color space.
`,
`These tables result in visually.pleasingiimages, but yield a rather
`low compressionratio for 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 that isapplied 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 introduce artifacts in the reconstructediimage, such as blockinessiin
`areas ofconstant color or ringing in text-scale characters. Someofthese
`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.
`
`10
`
`15
`
`20
`
`25
`
`HUAWEI EX. 1016 - 9/714 |
`
`HUAWEI EX. 1016 - 9/714
`
`
`
`
`
`
`
`7
`
`.
`
`/
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`Therefore, these methods are not ideal.
`As a resultof the inadequacy of the Q-factor approach, additional
`design methodsfor. JPEG discrete quantization tables ‘have. been
`proposed. These methodscan 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 beingbased on the
`removal of subjective or statistical redundancy, respectively,
`-These
`methods are discussed in copending application entitled "Method for
`Selecting J.PEG Quantization Tables for Low Bandwidth Applications,"
`commonly. assigned to the present assignee, incorporated herein by
`reference.
`|
`.
`Quantizationiis not the.only cause ofimage degradation.. The color
`source image data itself mightbe compromised. For ‘scanned colored
`images, the visualqualityof the iimage canbe degraded because ofthe
`inherent limitations of color scanners. These limitations are mainly of
`two kinds:
`limited modulation _ transfer.function (MTF).
`and
`misregistration.
`The modulation. transfer function refers to the
`mathematical representation ortransferfunction ofthe scanningprocess,
`There are inherent limitations inrepresenting the scanningprocess ‘by
`the MIF and these limitations are themain cause ofpixel aliasing, which
`produces fuzzyblacktext glyphs ofgrayish appearance. Misregistration,
`on the other hand, refers to the relative misalignment of the scanner
`sensorsfor the various frequency bands. For example, the Hewlett
`Packard ScanJet TIc™ has a color misregistration tolerance of+/- 0.076
`mm.
`for red. and blue with respect
`to green:
`This amount of
`misregistration iis significant considering thesize ofan imagepixel(e.g.,
`0.08 mmat 300 dotsper inch (dpi)).
`These limitations significantlydegrade textiin coloriimages because
`sharp «edges are very important for reading efficiency. The visual quality
`
`10
`
`15
`
`20
`
`25
`
`HUAWEI EX. 1016 - 10/714
`
`HUAWEI EX. 1016 - 10/714
`
`
`
`
`
`
`
`:
`
`3
`vs
`Patent Application
`:
`Attorney Docket Number 1094898-1
`oftext. can be improved, however, using prior art ‘edge enhancement
`techniques. Edge enhancement can be performediineither the spatial
`or frequency domain. “In the spatial domainGe., RGB), edge crispening
`can be performed by discrete convolution of thescannediimage with an
`edge enhancement kernel. This approachiis equivalent to filtering the
`image with ahigh-pass filter. However, this technique iis computationally
`intensive... An M:x.N convolution kernel, for example, requires MN
`_ multiplications and additionsper pixel:
`For edge sharpeningiin the frequency domain, the full iimageisfirst
`transformedintothefrequency.domainusingtheFastFourierTransform
`(FFT) or
`the Discrete Fourier Transform (DFT),
`low...
`frequency
`components are dropped, andthentheimageistransformedbackinto the
`time domain. This frequency domain method;as with the spatial domain
`method,
`is also. computationally intensive.
`: Moreover, it uses a
`transformation differentthan that required bythe JPEG standard.
`Accordingly, the need -Temains ‘for a. computationally efficient
`method for improving the visual quality ofimages, and in particular text,
`in scanned images.
`
`_- SUMMARYOF THE INVENTION
`The invention is a method of. compressing. and decompressing
`images which comprises usingone quantization table (Qe)forcompressing
`the image and a second quantization table (Q,) for decompressing the
`image.
`In general, compression: and decompression are performed in
`. conformance with the JPEGstandard. The second quantization table Qp
`is related to the first quantization table accordingtothe following general
`
`10
`
`15
`
`“20
`
`25
`
`expression:
`
`Qo=SxQe+B,
`
`HUAWEI EX. 1016 - 11/714
`
`
`
`HUAWEI EX. 1016 - 11/714
`
`
`
`
`
`
`
`9
`
`~ Patent Application
`Attorney Docket Number 1094893-1
`
`where Sisa scaling matrix having each element Sik,1] formed according
`to the following expression:
`
`S[k,ll? = Vlk,1VVolk,1]
`
`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 z6ro or non-zero elements. By usingthe scaling 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 Q, is transmitted with the. encoded
`quantizediimage data,andiis used iin decompressionto recoverthe image.
`Thereferenceiimage isa preselected continuous-toneiimage, either
`grayscale orcolordepending on theiimages tobe processed. The reference
`imageis rendered.into a target image file. The target imagefile is not
`‘generated bya scanner, sothe data thereiniis not compromised by any of -
`the inherent limitations of acolor scanner. ‘Thus,. the variance ‘of the
`target image data, which iis a statistical representation ofthe energy or
`frequency content ofthe iimage, retains the high-frequency components.
`The reference image can be any continuous-tone image, but.in the
`preferred embodiment the referenceiimage includes text with a seriffont
`because the serif:fonthas goodvisual qualitywhichthemethod preserves.
`The scanned image, although it canbe any image,in the preferred
`embodiment isa.printed version of the reference image. Thus, the
`variance of the scanned image represents the energy or frequency
`composition ofthe: reference image but whichis compromised by the
`inherentlimitationsofthe scanner.~The scalingmatrix, therefore, boosts
`the frequency components that arecompromised bythe scanningprocess.
`
`HUAWEI EX. 1016 - 12/714
`
`HUAWEI EX. 1016 - 12/714
`
`
`
`
`
`
`
`.
`
`10
`
`Patent Application
`‘Attorney Docket Number 1094893-1
`A preferred embodiment ofthe invention is described herein in the
`context ofa color facsimile (fax) miachirie. The colorfaxmachine includes
`a scanner for rendering a color imageinto color source image datathat
`represents the color iimage, a compression engine that.compresses the
`color source image data to compressed image data, a means for
`encapsulating.the compressed imagedata, and a meansfor transmitting
`the encapsulated data. The compression engine includes. means for
`storing two quantizationtables: Thefirst quantization table.is used to
`quantize the imagedata transformed using the discrete cosine transform
`(DCT).
`‘The second quantization table is encapsulated withthe encoded
`quantizediimage data for use in decompressing the image. The second
`quantization tableis related to thefirst quantization table in the manner
`described above. When used to transmit and receive color images
`between two locations, the machine transfers the images with higher
`quality than‘prior.systems.
`,
`The second quantization table canbe precomputed andstoredinthe
`compression engine,in which case there are ho additional computational
`requirements for the éornipression engine to implement the image
`enhancing methodofthe invention. This capability results in a lower cost
`color facsimile product than is possible using the prior. art image
`enhancementtechniques.
`The foregoing and other objects, features and advantages of the
`invention will become morereadily apparent fromthe following detailed
`description of a preferred embodiment of the invention which proceeds
`with referenceto the accompanying drawings.
`
`10
`
`15
`
`20
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Fig. Lisa block diagram of a prior art JPEG compression engine.
`Fig. 2 is a drawing ofa typical format of a JPEG compressedfile.
`
`HUAWEI EX. 1016 - 13/714
`
`HUAWEI EX. 1016 - 13/714
`
`
`
`
`
`
`
`11
`
`Patent Application
`Attorney Docket Number 1094893-1
`Fig. 3 is ablock diagram ofa prior artJPEG decompression engine.
`Fig. 4-is a flow chart ofa method offorming a scaled quantization
`table according to.the invention.
`Fig. 5
`isa"drawing of a JPEG corriprésged file including a
`quantization table scaled according to theinvention.
`Fig. 6is.ablockdiagram ofaJPEG decompression engine according
`to the invention.
`Fig 7.is a block diagram of a color fax machine5
`including JPEG
`compression and decompression engines according to the invention.
`DETAILED DESCRIPTION OF.THE PREFERRED EMBODIMENT
`"Overview ofthe Quantization Process
`The text andiimage enhancingtechnique accordingto the invention
`is integrated into the decoding ‘orinverse quantization step that is
`necessarilyrequiredbythedPEGstandard. The invention integrates the
`two by using twodifferent quantization tables:a first quantization table
`(Qs) for use in quantizingtheiimage data during thecompression step and
`a second quantization table (Qn)for use during the decode or inverse
`quantization during the decompression process. The difference between
`the two tables, in particular theratio of the two tables, determines the
`amount ofiimage enhancing thatiis done inthe two steps. By integrating
`the image enhancingandiinverse quantization steps, themethod does not
`require any additional computations than already required for the
`compression and decompression processes..
`a
`In order to understand the operation ofthe invention, the following
`mathematical derivationiisnecessary. Let Qp be the second quantization
`table used during the decoding orinverse quantization step. Then let Qp
`be related to the first quantization table Qi, used during the quantization
`step,by the following expression:
`
`10
`
`15
`
`20
`
`95
`
`HUAWEI EX. 1016 - 14/714
`
`HUAWEI EX. 1016 - 14/714
`
`
`
`
`
`
`
`13
`
`x
`
`Soe.
`Patent Application
`AttorneyDocketNumber 1094893-1
`
`Qo = (Sx Qe) +B a
`
`|
`
`@
`
`where S is a scaling matrix, which scales each elementof the first
`quantization.table. Qs to a: corresponding element
`in the. second
`quantization table Qp. The scaling matrix 9 iis not usediin atrue matrix
`multiplication; rather, the multiplication is’ an element-by-element
`multiplication. Each element in‘the first quantization. table Qs has a
`corresponding element in. the. scaling matrix S that when multiplied
`together produce. the corresponding element in the secondquantization
`tablé Qp.
`oe
`The matrix Bisa so-called brightness1matrix becauseit can affect
`the brightness of the image by changing.the DC level of the DCT
`elements. The ‘elements ofthe B matrix can include zero or non-zero
`values dependingon.the desiredbrightness. For]purposes ofthefollowing
`discussion and derivation,however, it will be assumed that the B matrix
`contains-zero elements only to simplify the derivation.
`The text and iimage enhancing technique of the invention uses a
`variance matrix to represent the statisticalproperties of an image. The
`variance matrix isan Mx M matrix, where each element in the variance
`matrix is equal to the varianceof a corresponding DCT coefficient over
`the entire image. The varianceis computed in the traditional manner, as
`_is knownin the art.
`The edge enhancement technique in essence tries to match the
`variance matrix ofa decompressed image (Vy [k,]]) with avariance matrix
`of a reference image (V*({k,1]); The technique tries to matchthe two by
`scaling the quantization table. in the manner described above. In order
`to do this,the method takes advantage of the relationship between the
`uncompressediimage and the compressed image. The following derivation
`
`~
`
`10
`
`15
`
`20
`
`25
`
`a ,
`
`“
`
`HUAWEI EX. 1016 - 15/714
`
`HUAWEI EX. 1016 - 15/714
`
`
`
`
`
`
`
`“13
`
`Patent Application
`:
`Attorney Docket Number 1094893-1
`
`“5
`
`will make this relationship clear.
`‘Let V*(k,1] denote the variance ofthe [k;1] frequency componentof
`a reference iimage. Ideally, this image contains thosecritical attributes
`that the technique seeks to. preserve, for example, text. This variance
`matrix is of an ideal or reference iimage in that:it-is not rendered into
`color source image data by a scannerbut, instead,iis rendered into its
`ideal form by software, described further below. ‘Thus, the color source
`image data of the reference image does notsuffer from the image
`degradation dueto the inherentlimitationsofthe scanner. Therefore, the
`varianceofthereferenceiimageretainsthehigh-frequencycharacteristics
`ofthe original referenceiimage.
`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
`15 following relationship:
`
`10
`
`Volk,=Vk,
`
`|
`
`(2)
`
`cy However; the decompréssed image (Y) is related to the original quantized
`image (Yq) by the following expression:
`
`20.
`
`Yk, I= Yoslk, 1 Qolk,
`|
`(3)
`Substituting equation (1) into equation (3) yields the following equation
`25..below:
`
`Yiik, I= Youlk, 1(S0k, Qik, ID
`
`(4)
`
`The variance of the decompréssedimage (Vy) can then be expressed by
`
`HUAWEI EX. 1016 - 16/714
`
`HUAWEI EX. 1016 - 16/714
`
`
`
`
`
`
`
`the following expression:
`
`| 14 |
`
`ao
`
`"PatentApplication
`i
`AttorneyDocketNumber 1094893-1 -
`
`Velk, 1] = Var (YI, I) = Var (Sik, 1] Youlk, 1Qelk,ID
`
`(5)
`
`Reducing this expression yieldsthe following:
`(6)
`—
`Volk,We Sik, q] Vylk, Wy
`where Vy represents the varianceof the original uncompressed image.
`Substitutingequation (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 (Wy): :
`(7)
`‘SIk, I=Vell11/Volk, I, a
`Therefore, the scaling matrix S can beused to: boost the variance
`of the JPEG compressed image. to that of the reference image by
`appropriate formation ofthe scalingmatrix. This methodiis showniina
`more generalized.fashioniin. FIG:.4,
`
`- Preferred Embodiment ofthe Method
`In FIG. 4, a method 62 of forming a scaled quantization table
`according to the invention is shown. Thefirst step 64 is to generate a
`referenceiimage. This referenceiimage, in the preferred embodiment,
`embodies certainvalued 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 iimage is important because
`it is the frequency or energy characteristics. of this image that. the text
`
`10
`
`15
`
`20
`
`25
`
`5
`
`
`
`HUAWEI EX. 1016 - 17/714
`
`HUAWEI EX. 1016 - 17/714
`
`
`
`
`
`
`
`Patent Application
`a
`415
`.
`AttorneyDocketNumber 1094898-1
`:
`image sharpening methodiis intended to preserve. Because the method
`is statistical, the result can be improved by averagingover a number of
`typicalimages. Examples ofsuch typical images are those usingdifferent
`fonts (e.g., Palatino and Devanagari), handwriting, short-hand, line
`drawings, schematics, 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
`andthen rendered by the application into referenceiimage data by the
`application. The réference image data will bein the appropriate color
`space, @.g., CIELAB or RGB,
`to allow the subsequent step to be
`performed. This process.canbe achievedbyfirstrenderingthe imageinto
`anAdobe Postscript file and then rendered into a bit-mapped color source
`image data file using DisplayPostscript. Alternatively, other page
`description languages can be used to describe theiimage such as the PCL
`language by Hewlett:Packard and then rendered into a bit map by aan
`appropriate rendering program.
`‘Oncethe referenceiimage‘is generatedand rendered into reference
`image data, the average energyof the referenceiimage is determinedin
`step 66. In the preferred embodiment,this step includes computingthe
`variance matrix (V*) for the reference image data. -The variance matrix,
`as. is knownin theart, statistically represents thefrequency components
`or energy containediin the image. Unlike a scannediimage, the reference
`image does not suffer from any of the inherent limitations of the color
`scanner because itiis not 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 referenceiimage.
`
`5
`
`10
`
`15
`
`20
`
`2.
`
`co
`
`HUAWEI EX. 1016 - 18/714
`
`HUAWEI EX. 1016 - 18/714
`
`
`
`
`
`
`
`16
`PatentApplication
`Attorney Docket Number 1094893-1
`In’step 68; a:‘scanned iimage is scanned or selected from one ormore
`stored pre--scaninediimages. This scannediimage is one that suffers from
`the inherent limitation of the’scanner. This scannediimage can be any
`image,but in the.preferred:embodiment itis a scanned version of the
`referenceiimagegenerated. in step 64, orofthe same type ofimage used
`to form an averaged referenceiimage.
`As in step 66, theaverage energy of the scanned image is then
`determined in step70:. The average energy again is represented by a
`variance matrix wv.) ofthescannediimage.
`.
`~The variance matrix (V*) of thereferenceiimage and the variance
`matrix (Vy) of the scannediimage are then used to compute the scaling
`matrix Sin step 72, This stepinvolves solving equation (7) above for
`each element in the scaling matrix S.
`Finally, in step 74 the scaled version of the quantization table is
`calculated. This step isa simple element-by-element multiplication as
`represented by equation (1) above.
`The useof the scale tables is seen clearly with reference to FIG.5.
`In FIG. 5a first sat ofQ tables a6 is provided to aJPEG compression
`engine 78, whichcompresses theiimage data in accordance with the JPEG
`com