BAR CODE LABEL
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`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 20BO
`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 annexed hereto is e trye copy from_ the records of the United States
`This is to certif
`Patent and Tra emark Office of the application which is Identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Date
`
`Certifying Officer
`
`HUAWEI EX. 1016 - 1/714 A
`
`HUAWEI EX. 1016 - 1/714
`
`

`

`
`
`
`~
` : .”IIIIIIIIIIIIIIIIIIIIIIIIIIIImm"’
`
`_
`
`
`. FILING DATE
`SERIAL NUMBER _
`GIIUUEAIIIUIIIT '
`
`
`
`' 08/411,369 :-
`'
`5256‘s
`-'
`
`
`
`I "GIORDANO BERETTAKPALO'ALTO,
`‘.
`MOUNTAIN VIEWCA;
`,_VASUDEV BHASKARAN»
`
`
`
`APPLICANT
`'- KONSTANTINOS KONSTANTINIDES,
`,
`,
`sANJOSE,
`:
`
`
`
`**CONTINUING DATA*********************'
`'
`
`
`
`VERIFIED . * v' - ' -
`
`
`
`
`
`
`
` **FOREIGN/PCT APPLICATIONS************‘
`
`VERIFIED ‘
`
`-
`
`v
`
`,
`
`-
`
`~
`
`’
`
`
`
` FOREIGN FILING LICENSE GRANTED 04/26/95
`
` ‘
`
`
`, SHEETS ,
`A'I'l'OHNEYDUCKETND.‘
`
`‘
`FILING-FEE
`'
`‘ RECEIVED.
`
`:_.
`'DHAWING
`’
`'
`'~
`"
`
`
`337 .j_-:_ .7
`_ EIgisegOo-ij
`.7-_i_o'946893' I,
`
`_ f-MARGEE JOHNSON MCCOLLOM STOLOWITZ
`
`
`1030 sw MGRRISONST
`
`
`
`
`ADDRESS-
`: PORTLANDOR 97205, g:
`
`
`TEXT ANDIMAGE SHARPENING0F JPEGCOMPRESSED IMAGESIN THE FREQUENCY
`'
`DOMAIN
`I
`’
`‘
`-
`
`-
`
`
`
`
`This isIo .Gér'Iif I IhIaIaIInO-Iivtéd
`'rét‘ois a tIUé cOpyfm the recordsofthe Uhitéd StaIés 3
`Patent and Tra emark Office Ofthe EppiiCatiOn‘ Whc‘IhIs identified above »
`'
`
`
`By authority of the
`I,
`'
`-
`
`.COMMISSIDNEH 0F PATENTSAND TRADEMARKS
`.~
`
`
`
`
`» IJata- :1 CénIfyinII OIfIIwr -
`
`HUAWEI EX. 1016 - 2/714
`
`HUAWEI EX. 1016 - 2/714
`
`

`

`HEWLETT-PACKARD COMPANY
`Legal Department, 2030 _
`
`Palo Alto. California 9430341890
`
`
`
`PAT§£¥3$1C§T§O§
`mBox10301
`
`
`
`
`ATTORNEY DOCKET NO.
`
`- 1 094893-1
`
`. COMMISSIONER OF PATENTS AND TRADEMARKS
`Washington, D.C. 20231
`'
`Sir:
`
`Transmitted herewith fOrfiling under 37 CFFI 1.53(b) is a(n):
`'
`'
`
`
`
`) Design
`(
`(x) Utility
`(x) originalpatent application.
`( ) continuing application,
`
`( )continuation-in-part
`
`( )continuation or
`
`( )divisional
`
`Of S/N
`
`filed
`
`lNVENTOR(S): Giordano Beretta et al.
`
`TITLE:
`
`TEXT AND IMAGE SHARPENING OF JPEG' COMPRESSED IMAGES N THE
`FREQUENCY DOMAIN
`‘
`
`Enclosed are:
`
`) unsigned or partially signed
`(
`(X) signed
`(X) The Declaration and PowerofAttomey.
`.(
`)
`informal drawings
`(one set)
`(X)
`7
`sheets of (X) formal drawings
`(-
`) Information Disclosure Statement‘and Form PTO-1449
`(
`) Associate Power of Attorney
`(
`) Priority document(s) 1.)
`(Other)
`,
`(fee$
`
`)
`
`'
`
`(1)
`. FOR
`
`INDEPENDENT
`
`.
`
`CLAIMS AS FILED BY OTHER THAN A SMALL ENTITY
`(2)
`(3)
`NUMBER FILED
`NUMBER EXTRA
`
`,
`(4)
`RATE
`
`
`
`(5)
`TOTALS
`
`ANY MULTIPLE
`—” $ 24°
`
`
`'
`BASIC FEE: ‘Design( $300.00): Utility( $750.00)
`-
`TOTAL FILING FEE
`
`,
`
`TOTAL CHARGES To DEPOSIT ACCOUNT
`
`
`
`
`
`
`(At any time duringthependency of this application,
`to DepositAccount 08-2025.
`1,158 .
`Charge $
`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
`doplicate copy Of this sheet is enclosed. .
`
`
`
`
`
`0
`
`‘1(JO
`
`1,158
`
`1,153
`
`$
`
`$
`
`$
`
`———"—'—‘
`'Express Mail“ label no. T3396300465 .,
`Date of Deposit March 27 I 1995
`
`.
`
`l hereby certify that this is' being deposited with the
`United States Postal SeNice “Express Mail Post
`Office to Addressee- service .under 37 CF‘RI1.1__O on
`the date indicated above‘and is addressed to'the
`Commissioner
`of
`Patents
`and
`Trademarks,
`Washingt
`rD-C-20231'-
`
`By Qt, EM
`Typed Namei Linda A. limura
`
`Rev 10/94 (Form 3.04)
`
`,
`
`- Attach as First Page to Transmitted Papers -
`
`,
`Respectfully submitted
`
`I
`
`Giordano Beretta et al.
`.
`(7 fiS/
`1
`.
`
`By
`
`W
`
`.
`
`C. Douglass homas
`
`Attorney/Agent for Applicant(s)
`Reg. NO.
`32,947
`Date: March 27 , 1995
`
`Telephone No.2 (415) 857-8129
`
`HUAWEI EX. 1016 - 3/714
`
`HUAWEI EX. 1016 - 3/714
`
`

`

`
`
`
`33131369
`
`/fl
`
`l
`
`Patent Application
`A
`v
`Attorney Docket Number 10948934
`
`
`g
`IS IN THE FREQUENCY DOMAIN
`pl 7 ‘ RELATED APPLICATION DATA .
`This application incorporates subject matter disclosed in commonly-
`assigned application entitled. METHOD 1 FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTH‘APPLICATIONS,
`Ser. No, (a i359’1‘7filed on even date hereWith.
`
`. BACKGROUND OF THE INVENTION
`
`invention relates to data compression using the JPEG
`This
`'cOmpression standard for continuous- tone stillimages, both grayscale
`
`and color.
`‘
`g
`~A cOmmittee‘ knO‘Wn as: "JPEG," whiéh stands for "Joint
`PhOtographic EXperts Group," hasestablished a standard for compressing
`continuous-tone Still images, .bOth *grayscale and color. This standard
`represents a compromise between reproducible image quality and
`compression rate. To achieveacceptable Compressionrates, which refers
`to the ratio of the unC‘ompresSed1mage to the compressed image, the
`JPEG standardadopted a lossy compression teChnique. The lossy
`compression technique was required given the inordinate amount Ofdata
`I needed to represent a‘ color"Image, on the order Of 10 megabytes for a 200
`dots per inch (DPI) 8.5" x 11" i111age. By carefully implementing the
`JPEG Standard, hoWever, the loss in the image can be confined to
`imperceptible areas oftheImage, 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 ofa typical implementation Ofthe
`
`10
`
`15
`
`20
`
`25
`
`30
`
`HUAWEI EX. 1016 - 4/714
`
`HUAWEI EX. 1016 - 4/714
`
`

`

`
`
`
`
`, 2
`
`Patent Application
`,
`AttorneyDocket Number 1094893-1
`
`JPEGcompression standard The block diagram will be referred to as a
`Compression engine The cOmpression engine 10 operates on source image
`I data, Which represents a source image in a giVen. color space such as
`CIELAB. The source image data has a certain resolution, which is
`determined by how theimage was captured. Each individual datum of
`the source image data represents an image pixel. The pixel further has
`a depth Whichis determined by the number ofbits-used to represent the
`image pixel;
`L
`S
`The Source image data is typically formatted as a raster stream
`of data. The compreSSion technique, however, requires the data‘to be
`represented, in blocks. These blocks represent a two-dimensional portion
`of the source image data. The JPEG standard uses 81:8 blocks of data.
`Therefore, a rasterét0'-b10ck translation unit 12 translates the raster
`source image data into 8x8 blocks of source image data. I 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 transtrmer 16, converts the scurce image data
`_ into transformed image data using the discrete ecsine 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 corresponds 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 decomposedinto a Weighted sum of these unique images. The
`discrete Cosine transformer uses the forward disorete cosine (FDCT)
`function as shown below, hence the name.
`*
`
`v10-
`
`15
`
`20
`
`25
`
`
`
`HUAWEI EX. 1016 - 5/714
`
`HUAWEI EX. 1016 - 5/714
`
`

`

`
`
`
`
`3
`
`’
`
`Patent Application
`_
`Attorney Docket Number 1094893-1
`
`7
`
`7
`
`x=0 y~‘0
`
`(2x .-'l-1)k71:cOS (2y+ l)11c
`16
`16
`
`Y[k,1]=—C(k)oC(1)[228(x,y)ocos
`where: C(k), 0(1):l/ffork, l = 0; and
`C_(k), C(l)=1otherwiSe
`
`The Output of the transformer 16 is an 8x8 block of DCT elements
`or coefficients, corresponding to the DCT basis vectors This block of
`tranSforrned'1mage data'is then forWarded to a quantizer 20 over a bus
`18. The quantizer 2O quantizes the 64 DCT elements using a 64-element
`quantization table 24 which must be Specified as an input to the
`compression engine 10. Each element of the quantization table is an
`integer value from one to 255, which specifies the stepsize of the
`quantizer for the Corresponding DCT coefficient. The pm‘poseof
`quantization is to achieve the maximum amount of compression by
`representing DCTcoefficients with no greater precision than'1s necessary
`to achieve the desired image quality. Quantization is a many-to-one
`mapping and, therefore, is fundamentallylossy. As mentioned above,
`quantization tables havebee‘n designed Which limit the lossiness to
`imperceptible aspects of the image so that the reproduced image is not
`perceptually different frOm the SourCeimage.
`_
`V
`The quantizer20 performs a simple division operationbetween each
`DCT ocefiicient 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.
`
`10
`
`15
`
`20
`
`25
`
`I YQlk; 1] = IntegerRound(-Y:&il)
`
`HUAWEI EX. 1016 - 6/714
`
`HUAWEI EX. 1016 - 6/714
`
`

`

`
`
`
`
`4
`
`Patent Application
`.
`'
`Attorney Docket Number 1094893-1
`
`where Y(k'1) represents the (k,1)-th DCT elementand Q(k,l) represents
`the corresponding quantization table element.
`
`To reconstruct the source image, this step is reversed, with the
`quantization table element being multiplied by the corresponding
`quantized DCT chefii’cient. The inverse quantization step can be
`represented by the following expression;
`
`Y’[k, 1] = YQ[k,'1] (Mk, 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 theimage quality of the quantization
`step, considerable effort hasgone into designing the quantization tables.
`These efforts are described further below following a discussion of the
`
`.
`final step1n the JPEG compressiOn-technique.
`,
`The final step cf the JPEG standard1s an entropy encoding, which
`is performed by an entropy encoder 28. The entropy encoder 2818 coupled
`to the quantizer 20 via abus 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 statisticalcharacteristics. The JPEG standard Specifies two entropy
`coding ‘ methodsi, Huffman coding and arithmetic coding.
`The
`compression engine ofFig. 1 assUmes Hufi'man coding is used. Huffman
`encoding, as is known in the art, uses one or mere sets of Huffman code
`tables 30. These tables may be predefined or computed specifically for a
`given image. Huffman enc0ding'1s a well known encOding technique that
`produces high levels oflossless compression. Accordingly, the operation
`of the entropy encoder 28IS not further described.
`Referring now to Fig. 2, a typical JPEG compressed file is shown
`
`10
`
`15
`
`20
`
`'25
`
`\
`
`
`
`HUAWEI EX. 1016 - 7/714
`
`HUAWEI EX. 1016 - 7/714
`
`

`

`
`
`
`
`I
`
`_ 5
`
`Patent Application
`AttorneyDocket 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 usedin the
`compression process, and the compressed1mage data 42 itself. From this
`compressed file 34 a perceptuallyindistingmshable version oftheoriginal
`source image can be extracted when an appropriate Q-table'IS used. This
`extraction process is described beloW with reference to Fig. 3.
`_
`A JPEG decompression engine 43 is shown in_Fig. 3. The
`decompreSSion engine essentially operates1n reverse ofthe cempression
`engine 10. 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 contained111 the _
`header. The H tables are then stored1n H tables 46 while the Q tables
`are stored'1n Q tables 48. The compreSSed1mage data13 then sent to an
`entropy decoder 50 over a bus 52. TheEntropy Decoder decodes the
`HUffman encoded compressed'1mage data using the H tables 46. The
`output ofthe entropy decoder 50 are thequantized DCT elements.
`The quantized DCT elementsare then transmitted to an inverse
`quantizer 54 over a bus 56. The1nverse quantizer 54 multiplies the
`quantized DCT elements by the corresponding quantization table
`elements found in Q tables 48. 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 of the compressed'1mage data.
`The1nverse quantized DCT elements are then passed to an inverse
`discrete cosine transformer (IDCT) 57 via bus 59,-Which transforms the
`data back, into the time domain using the inverse discrete cosine
`transform (IDCT). The'1nverse tranSfomned dataisthen transferred to
`block-to—raster translator 58 OVer a bus 60. Where the blocks of DCT
`
`10,
`
`'
`
`15
`
`20
`
`25
`
`elements are translated into a raster string ofdecompressed sourCe image
`
`HUAWEI EX. 1016 - 8/714
`
`HUAWEI EX. 1016 - 8/714
`
`

`

`
`
`
`
`i
`
`i
`
`.
`
`'6
`
`10'
`
`15
`
`20
`
`25
`
`Patent Application
`.
`Attorney Docket Number 1094893-1
`data From the'deco'mpressed source image data, a facsimile of the
`original souICe image can be reconStructed The reconstructed source
`image however,1s not an exact replication cf the original source image.
`As described 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 loss to
`visuallyimperceptible portions of the'image, These methods, and their
`shortbom‘ings, 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'tiOn technology
`- digital cor'npreSsiOn encodingof centinuOus - tones still images - part 1:
`Requirements and Guidelines " ISO/IE0 1810918-1, October 20’ 1992
`These tables are knovV‘n as the K.1 and K.2 tables, respectively. These
`tables have been designed based on the perceptually loSsless compression
`of color'images representedin the YUV Color space.
`These tables result'1n visuallypleasing1mages, but yield a rather
`low compression ratio fer certain applications. The compression ratio can
`be varied by setting a so-called sQ-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 tablesare
`carefully designed to be perceptually loSsless, however, a large Q—factor
`will intrOduce artifacts'1n the reconstructed'Image, Such as blockiness'1n
`areas ofconstant color or ringing in text-scale character's. Some ofthese
`artifacts can be effectively cancelled by post-processing of the
`reconstructed image by passing it thrOugh a tone reproduction curve
`' correction Stage, 01‘ by segmenting the image and processing the text
`separately. , However, such methods easily introduce new artifacts.
`
`HUAWEI EX. 1016 - 9/714 1
`
`HUAWEI EX. 1016 - 9/714
`
`

`

`
`
`
`
`7
`
`-
`
`1
`
`Patent Application
`V
`Attemey Docket Number 1094893-1
`
`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 methodscan be categorized as either perceptual, which
`means based on the human visual sySteIn (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'IS not the.only cause ofimage degradation. The color
`s0urce image data itself mightbe compromised. For scanned colored
`images, the visual quality 0f thennage canbe degraded because of the
`inherent limitations of color scanners. These limitations are mainly of
`two kinds:
`limited modulation . transfer“.function (MTF)
`and
`misregistration. The medulation tranSfer function refers to the
`mathematical representation or transferfunction ofthe scanning process. .
`There are inherent limitations'1n representing the scanning proceSS by
`the MTF and these limitationsare the main cause ofpixel aliasing, which
`produces fuzzy black text glyphs ofgrayish appearance. Misregistration,
`on the other hand, refers to the relative misalignment cf 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
`misregistration15 Significant considering the size ofan image pixel (e.g..,
`0.08 mm at 300 dotsper inch (dpi)).
`These limitations significantly degrade text'1n color'images 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
`
`

`

`
`
`
`
`'8
`
`‘
`
`>
`
`.
`
`Patent Application
`1,
`‘
`_
`Attorney Docket Number 1094893-1
`
`of text can be imprdved, however, using prior art edge enhancement
`techniques. Edge enhancement can be performed1n either the spatial
`or frequency domain. In the spatial domain (ie.,RGB), edge crispening
`can be performed by discrete convolution of thescanned'unage with an
`edge enhancement kernel. This approachIS equivalent to filtering the
`image with a high-pass filter. HoweVer, this techniqueis computationally
`intensive. An M X N c0nvOlution kernel, for example, requires MN
`
`. multiplications and additionsper pixel.
`For edge sharpening1n the frequency demain, the full'Image is first '
`, transformed into thefrequencydomainusingtheFast FourierTransform
`(FFT) or
`the Discrete Fourier Transform (DFT),
`low frequency
`components are dropped, and thenthe1mage istransformed back into the
`time domain This frequenCy demain method, as with the spatial domain
`method,
`is also. cOmputationally intensive.
`. Moreover,
`it» uses a
`tranSformation differentthan that required by the 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
`i
`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 table (QD)_for decompressing the
`image.
`In general, compression and decOmpres'sion are performed in
`V Conformance with the JPEG'standard. The second quantization table QD
`is related to the first quantization table acc0rding tothe following general
`
`10
`
`.15
`
`'20
`
`25
`
`expreSsion:
`
`QD=SXQEV+By
`
`
`
`HUAWEI EX. 1016 - 11/714
`
`HUAWEI EX. 1016 - 11/714
`
`

`

`
`
`
`
`9
`
`' Patent Application
`'
`> Attorney Docket Number '1094893-1
`
`where S15 a sealing matrix having each element S[k,1] formed according
`
`to the following expression:
`
`S[k,1]2 = v*[k,1]/vY[k,11
`
`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 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 QD is transmitted With the. encoded
`quantizedimage data, and13 used1n decompression to recover the'image.
`Thereference1mage is a preselected continuous-tone'1mage, either
`grayscale or color depending on thennage‘s to be processed. The reference
`image is renderedinto a target image file. The target image file1s not
`generated by a scanner, sothe data therein'151 not compromised by any of
`the inherent limitations of a color scanner. Thus, the variance of the
`target image data, which15 a statistical representation of the energy or
`frequency content ofthe1mage, retains the high-frequency components
`. The reference image can be any continuous-tone image, but in the
`preferred embodiment the referenCeimage includes text with a senffont
`because the ser1ffont has good viSual quality which themethod preserves.
`The scanned'1mage, although it can be any image, in the preferred
`embodiment is a printed Version of the reference image. Thus, the
`variance cf the scanned image represents the energy or frequency
`composition 0f the reference image but which is compromised by the
`' inherentlimitations ofthe scanner.The scaling matrix, therefore, boosts
`the frequency components that are compromised by the scanning process.
`
`rm»
`
`f, L)
`
`HUAWEI EX. 1016 - 12/714
`
`HUAWEI EX. 1016 - 12/714
`
`

`

`
`
`
`
`1 0
`
`.
`
`Patent Application
`i
`Attorney Docket Number 1094893-1
`
`A preferred embodiment ofthe invention'1s deScribed herein'1n the
`context ofa color facsimile (fax) machine. The color fax machine includes
`a scanner for rendering a color'image into color source image data that
`
`'
`
`represents the color image, a compression engine 'thatcompresses the
`color source image data to compressed image data, a means for
`encapsulatingthe Compressed iinage data, and a means for transmitting
`the encapsulated data. The compression engine includes means for
`storing two quantization tables. The first quantization table'1s used to
`quantize theImagedata transformed using the discrete cosine transform
`(DCT). The second quantization table15 encapsulated withthe encoded
`
`quantized'Image data for use in decompressing theImage. The second
`quantization table is related to the first 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 thanpriorsystems.
`The secOnd quantization table can be precomputed and stored1n 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 resultsIn 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. 11s a block diagram of a prior art JPEG compression engine.
`Fig. 2 is a drawing of a typical format of a JPEG compressed file.
`
`HUAWEI EX. 1016 - 13/714
`
`HUAWEI EX. 1016 - 13/714
`
`

`

`
`
`
`
`1 1
`
`Patent Application
`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‘inventiOn.
`Fig. 6'18 a block diagram ofa JPEG decompressiOn engine according
`to the invention.-
`Fig 7 .is 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 of the Quantizatic‘m 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 theimage data during thecompression step and
`a second quantizationtable (infor use duringthe deCode or inVerse
`quantization during the decompression process, The difi‘erence between
`the two tables, in particular the ratio of the two tables, determines the
`amount ofunage enhancing that'1s dOne'1n the two steps. By integrating
`the'1mage enhancingand'mverse quantization steps, the method does not
`require any additidnal Computations than already required for the
`compression and decompression prOcesses.
`‘
`I
`In order to understand the operation cfthe 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 Q3, used during the quantization
`Step, by the following expression:
`
`10
`
`15
`
`20
`
`25
`
`HUAWEI EX. 1016 - 14/714
`
`HUAWEI EX. 1016 - 14/714
`
`

`

`
`
`
`
`1. 2
`
`.
`
`'
`
`Patent Application
`.
`'
`’
`1
`Attorney Docket Number 1094893-1
`
`Q;=(s_xQE-)+B
`
`j
`
`»
`
`_
`
`11)
`
`where S is a scaling matrix, which scales each element of the first
`quantization». table Q; to a corresponding element
`in the second
`quantization table Qp. The scaling matrix Sis not uSed'in atrue matrix
`multiplication; rather, the multiplicatiOn is an element-by-element
`multiplication. Each element1n the first quantization table QE has a
`corresponding element in ,the’ scaling matrix S that When multiplied
`together produce the corresponding elementin the second'quantization
`table' QB.
`.
`'
`The matrix B is 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 dependingon the desired brightness. Forpurposes ofthe following
`discussion and derivatiOn,_hoWever, it will be assumed that the B matrix
`contains zero elements only to Simplify the derivation.
`The text and'1mage enhancing technique of the invention uses a
`variance matrix to represent the statisticalproperties of an image. The
`variance matrix 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 known in the art.
`The edge enhancement technique in essence triesto match the
`variance matrix ofa decompressed image (V? [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'1n the manner described above. In order
`to do this, the method takes advantage of the relatiOnship between the
`uncompressed1mage and the compressed1mage. The following derivation
`
`10
`
`15
`
`20
`
`25
`
`._.—‘
`
`I
`
`z”
`
`HUAWEI EX. 1016 - 15/714
`
`HUAWEI EX. 1016 - 15/714
`
`

`

`
`
`
`
`. l 3
`
`Patent Application
`.
`Attorney Docket Number 1094893-1
`
`1 5
`
`10
`
`will make this relationship clear.
`Let V*_[k,1] denote thevariance ofthe [k,1] frequency component of
`' a referenceimage. Ideally, this'image Contains those critical attr1butes
`that the technique Seeks to preserve, for example, text. This variance
`matrix is of an ideal or reference'image in that itIS not rendered into
`color source image data by a scanner but, instead,1s rendered into its
`ideal form by softWare, described further below. Thus, the color source
`image data of the reference iniage dees not suffer frOm the image
`degradation due to the inherent limitations ofthe scanner. Therefore, the
`variance ofthe referenceimage retains the high-frequency characteristics
`of the original referenceimage.
`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:
`
`VY’[k, 11=V*1k,11
`
`-
`
`'
`
`(2)
`
`z
`
`.. However, the decOmpresSed'1mage(Y’)is related to the original quantized
`image (Yq) by the following expreSSion:
`
`20
`
`"Y’[k,1]‘=YQE“[1{,1]Qn[k,-ll
`
`.
`
`p
`
`(3)
`
`Substituting equation (1) into equation (3) yields the following equation
`
`25,
`
`below:
`
`Y’[k,l]=Y§1.:[k,1](S[k,1] Qs[k,1])
`
`(4)
`
`The variance cf the deCOmp'ressedi'ima'ge (VY') can then be expressed by
`
`HUAWEI EX. 1016 - 16/714
`
`HUAWEI EX. 1016 - 16/714
`
`

`

`
`
`
`
`14 V
`
`1
`
`V
`
`I V
`
`Patent Application
`I
`»
`’1
`‘
`Attorney‘Docket Number 10948934 ‘
`
`the following eXpreSSion:
`
`vrtk, 11 = var (m, 11) 1 varf(S_[k;l]Y¢1[k, 11,.Q11k.’11)
`
`Reducing this eXpressiOn yieldsthe following:
`
`Vy=[k, l]= S2[k-, llVy[k, l]
`
`'
`
`’
`
`,
`
`(5)
`
`(6)
`
`10
`
`15
`
`20
`
`25
`
`where V9 represents the variance of the original uncompressed image.
`Substituting equation (6) into equation (2) yields the following
`relationship between the scaling matrix S and the variances of the
`‘ reference1mage (V*) and the original1mage WY)
`
`'Stk;1]2:"'v*[k._1]/ wk, 1],
`
`..
`
`'
`
`.
`
`(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 scalingmatrix. This method1s shown'1n a
`more generalized fashion1n FIG. 4.
`
`_ Preferred Embodiment of the Method
`In FIG. 4, a method 62 0f forming a scaled quantization table
`according to the invention is shown. The first step 641s to generate a
`referenceImage. 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 SelectiO’n ofthe referenceimage is important becauSe
`it is the frequency or energy characteristics of this1mage that the text
`
`21/
`
`/‘
`
`
`
`HUAWEI EX. 1016 - 17/714
`
`HUAWEI EX. 1016 - 17/714
`
`

`

`
`
`
`
`._
`
`Patient Application
`:
`'
`'
`1 5
`Attorney Docket Number 1094893-1
`.
`image sharpening method'1s intended to preserve. Because the method
`is statistical, the result can be improved by averagingever a number of
`typical1mages. Examples ofsuch typicalimages are those usingdifferent
`fonts (e.g..,Palatino and Devanagari), handwriting, short-hand, line
`dravvings, schematics, bar codes, etc. These different1mages can further
`be categorized1n a number of 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'1mage is entered into the computer
`and then rendered by the application into reference'1mage 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 the1mage into
`an Adobe 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 desoribe the'image such as the PCL
`language by Hewlett Packard and then rendered into a bit map by an
`appropriate rendering program.
`oncethe reference1mageis generated and rendered into reference
`image data, the average energy of the reference'image is determined1n
`step 66. In the preferredembodiment, this step includes computing. the
`variance matrix (V*) fer the referenceimage data. The variance matrix,
`as is known'in theart, statistically represents the freqUency components
`or energy centained'1n the'1mage. Unlike a scanned'image, the reference
`image does not suffer from any of the inherent limitations of the color
`‘scanne‘r 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 ofthe referenceimage.
`
`5
`
`10
`
`_
`
`15
`
`20
`
`25
`
`.
`
`to
`
`HUAWEI EX. 1016 - 18/714
`
`HUAWEI EX. 1016 - 18/714
`
`

`

`
`
`
`
`l- 5
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`Instep 68, aScannednnage is scanned or selected from one or more
`stored pre-scannedImages. This scanned'Image is one that suffers from
`the inherent limitation of thescanner. This scanned1mage can be any
`image,but1n the- preferred embodiment it is a scanned version (if the
`referenceunagegenerated1n step 64, or of the same type of'1mage used
`to form an averaged referenceimage.
`As in step 66, theaverage energy of the scanned image is then
`determined'in step7O The average e