`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`U«S- PATENT APPLICATION
`
`SERIAL NUMBER
`
`O8/411,369
`
`FILING DATE
`
`03/27/95
`
`GROUP ART UNIT
`
`2613
`
`GIORDANO BERETTA, PALO ALTO, CA; VASUDEV BI-IASKARAN, MOUNTAIN VIEW, CA;
`KONSTANTINOS KONSTANTINIDES, SAN JOSE, CA.
`
`APPLICANT
`
`**coNTINUIN(_; DATA~k*******-k*******~k****
`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 annexed hereto is _a tree 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. 1116 - 1/714
`
`
`
`WWWWWIIWm"W
`
`SEHMLNUMBEB
`
`, —_;~
`
`.
`
`V
`
`-E,
`
`’.‘V-;
`
`.-~
`
`. HuNenATE:».
`
`1.1-
`
`ETv
`
`_
`
`_,.f_, I
`
`V =;’_‘
`
`chobr£hfumrA
`
`.eiba‘SA_r&6
`-KONSTANTINQS 'K°Ns-?A.Fm:bEs;
`
`jjj.
`
`'
`
`‘
`..
`
`x’abm:'»:'v:gw-E¢;;';‘-'
`.
`*
`-V
`
`V
`
`-E
`
`VERIFIED.E:
`
`'
`
`»A E‘
`
`E
`
`’
`
`"
`
`”
`
`”
`
`- **EdREIGN/ECT APPLi¢AEioNs¥*£*%§#%%fi5i"V
`"’VERIFiEDi.
`‘
`"
`“é
`”"
`’”
`
`3 _F0REi¢1:\i'F'Ii;I_NGfj:3idENSE Q£{A1§I'TED:;‘O{L/2é{}9§ 1
`"
`
`_
`'¥>VE
`
`u
`
`__
`_
`ATTORNEYDDCKETND
`.
`.
`.
`.
`;
`
`HUNGFEE _-
`’ BECHVED-Q
`
`:
`
`:$;,i5a§6of” § 1o94ba93 1
`
`jMARGER.fi0HNS§NfMéC5LflDM"STOLOWiTZ";-1'
`., _1Q3o_sw MO3RISQN$ST_’T_‘
`E
`‘A '”
`PORTLAND OR 972o5",: ”
`
`.[ TEXT AND IMAGE SHARPENING OF JPEG=boMPkEssEn~1MAGEs.IN‘THE FREQUENCY
`.DOMAIN
`“
`'
`-«'
`=
`-
`-
`'
`A " "'
`.
`.-V
`.
`-
`
`This is-"to Acériif’ ',;ha£'}afihgxed h'e‘7'ré_£o--E _é_”tAr'l_i4'é c2‘§‘>i3‘/‘E‘1‘~r"t‘gL",r.r1'_ {hé ‘§"t§‘_<.:.<)‘i1<';ié-‘oA:f\:f_l1zE uriiiéci skates '
`‘ Patent a_nd‘Tra gmarlg Offlge <_J‘f“_the application which Is Identified abo've.--
`"
`‘
`'
`__
`‘
`"3Yauthdrit'vofti1e~', V
`is
`Q "
`»'
`V
`V
`V
`'
`‘
`’
`' “
`COMMISSIONER OF PATENTS A|_‘lDbTRA[b)EMAHl(S
`
`bats
`
`b
`
`E
`
`_“_
`
`I’
`
`.'E‘'
`
`.'; E
`
`1'
`
`I
`
`.¥._7'; cénflyfig ohker ,. -
`
`:
`
`HUAWEI EX. 1116 - 2/714
`
`
`
`HEWLETT-PACKARD COMPANY
`
`Legal Department, 20BO _
`P.O. Box 10301
`Palo Alto, caiiiomia 94303-0890
`
`V
`
`g
`
`0
`
`g
`
`_ P
`
`I
`.
`ATTORNEY DOCKET No.
`
`1 094893-1
`
`COMMISSIONER OF PATENTS ANDATRADEIVIARKS
`Washington, D.C. 20231
`’
`Sir:
`
`Transmitted herewith for filing under 37 CFR1.53(b) is a(n):
`I
`
`) Design
`(
`(X) Utility
`(x) originalpatent application,
`( ) continuing application.
`
`( ) continuation-in-part
`
`( )continuation or
`
`( )divisiona|
`
`of S/N
`
`tiled
`
`lNVENTOR(S): Giordano Beretta et al.
`
`TITLE:
`
`TEXT AND IMAGE SHARPENING OF JPEG' COMPRESSED IMAGES IN THE
`FREQUENCY DOMAIN
`‘
`
`Enclosed are:
`
`(X) The Declaration and Power-ofAttomey.
`(X)
`7
`sheets of (X) formal drawings
`
`) unsigned or partially signed
`(
`(X) signed
`.(
`)
`informal drawings
`(one set)
`
`(
`(
`
`) Information Disclosure Statement and Form PTO—1449
`) Priority document(s)
`(
`)
`(other)
`
`(
`
`) Associate Power of Attorney
`(fee$
`
`)
`
`'
`
`CLAIMS AS FJLED av OTHER THAN A SMALL ENTITY
`
`«
`
`(4)
`(1)
`(2)
`(3)
`FIATE
`. FOR ’
`NUMBER FILED
`NUMBER EXTRA
`$ 22
`T X
`INDEPENDENTM— X
`$ 76
`ANY MULTIPLE.
`“.1 $ 24°
`BASIC FEE: ‘Desigri( $3o'o.oo ); UtI|ity( $730.00)
`TOTAL FILING FEE
`
`-
`
`A
`
`(5)
`TOTALS
`
`$
`
`$
`$
`
`730
`
`V
`
`TOTAL CHARGES T0 DEPOSIT ACCOUNT
`
`to Deposit.Account 08-2025. At any time‘ during the pendency of this application,
`1,158
`Charge :1‘:
`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.
`
`ufixpress Mail‘ labelno.
`Date of Deposit March 27 I 1995
`
`I
`
`I hereby certify that this is’ being deposited with the
`United States Postal Service ‘Express Mail Post
`Office to Addresses‘ service under 37 CFR x1..‘I_0 on
`the date indicated aboveand is addressed tofthe
`Commissioner
`of
`Patents
`and
`Trademarks,
`Washinst
`1, D-C- 202314
`
`By §
`Typed Namei Linda A. llmura
`
`Respectfully submitted.
`
`Giordano Beretta et al.
`
`-
`C /. I
`3
`,
`
`By
`
`_
`
`C. Douglass homas
`
`Attorney/Agent for Applicant(s)
`Reg No-
`32.947
`Date:' March 27, 1995
`
`Fley 1o/94 (Form 3.04)
`
`- Attach as First Page to Transmitted Papers - Telephone N0-3 (415) 857'8129
`
`HUAWEI EX. 1116 - 3/714
`
`
`
`%-
`
`Patent Application
`,
`.
`~
`Attorney Docket Number 10948934
`
`g
`
`‘
`
`TEXT AND IMAGESHARPENING OFAJPEG Co
`D
`-
`N THE EREQUENCY DOMAIN
`.C’l 7
`RELATED APPLICATION DATA i
`This application incorporates subject matterdisclosed in commonly-
`assigned application entitled I METHOD , FOR SELECTING JPEG
`QUANTIZATION TABLES FOR Low BANDWIDTH APPLICATIONS,
`_Ser. No._ §[',7file.d on even date herewith.
`
`BACKGROUND OF THE INVENTION
`
`‘invention relates to data compression using the JPEG
`This
`compression standardvfor continuous -_tone still images, both grayscale
`and color.
`V
`V
`_
`I
`I
`_
`g
`A committee known as "JPEG," which stands
`for "Joint
`Photographic Experts Group," hasestablished a standard for compressing
`continuous-tone still images, both grayvscale 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 uncompressed image to the compressed image, the
`JPEG standard adopted a lossy, compression I technique. The lossy
`compression technique was required given the inordinate amount ofdata
`neededto represent a color i‘mage,:on the order of 10 megabytes for a 200
`dots per inch (DPI), 8,5" x 11" image- By carefully implementing the
`JPEG. standard, however, the loss in the image can be confined to
`imperceptible areas ofthe image, which produces a perceptually loss less
`. uncompressed. image. The achievable compression rates using this
`technique are in the range of 10:1 to 50:1.
`L
`_
`Figure
`shows a block diagram of a typical implementation of the
`
`HUAWEI EX. 1116 - 4/714
`
`
`
`2
`
`’
`
`Patent Application
`.
`"
`—
`Attorney Docket Number 10948934
`
`JPEG-compression standard._ The block diagram will be referred to as a
`compression engine"; The compression engine 10‘ operates on source image
`' data", which represents a source image in a givencolor space such as
`CIELAB. Thersource image data has a certain resolution, which is
`determined by how the image was captured. Each individual datum of V
`the source image data. represents an image pixel. The pixel further has
`a depth which is determined by the number of bits used to represent the
`image pixel;
`6
`6
`The sourceimagedata is typically formatted as a raster stream
`of data. The compression technique, however, requires the dataito be
`represented in
`These blocks represent a two-dimensional portion
`of the source image data. The JPEG standard uses 8x8 blocks of data.
`Therefore, a raster-to‘-block translation unit 12 translates the raster
`source image data it 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 the proper format for the next stage in the compression
`process. These 8X8 blocks’ are then forwarded to a discrete cosine
`transformer 16 via bus 14.
`‘I.
`V
`6
`The discrete cosine transformer 16 converts the source image data
`_ into transformed image data using the discrete cosine transform (DCT).
`The DCT, as is known in the art ofimage processing, decomposes the 8x8
`block of source image data into 64
`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
`space. These basis vectors can be
`intuitively thought to represent unique images, wherein any source image
`can be decomposed into a ‘weighted sum ofthese unique images. The
`discrete cosine transformer uses the forward, discrete cosine (FD_CT)
`function as shown below, hencethe name.
`'
`
`HUAWEI EX. 1116 - 5/714
`
`
`
`Patent Application
`_
`Attorney Docket Number 10948934
`
`g
`
`_
`
`.
`
`~
`
`_
`
`.
`
`V
`
`7
`
`7
`
`\
`
`‘
`
`x=0y-—-‘0
`
`Ylkyll =s %(_3(k) ' pC(1)[2i2S(X;Y) ‘ cos cos ]
`where: C(k), 0(1):. 1/\/'§_"i'ork,l = 0; and
`
`_ C(k), 0(1) = lotherwise
`
`The output of the transfonner 16 is an 8x8 block of DCT elements
`or coefficients, corresponding to theVDCT' basis vectors.’ This block of
`transformed image data is then forwarded to a quantizer 20 over a bus
`18, The quantizer
`quantizes the 64 DOT elements using a 64-element
`quantization Atab1e»24,v which must be specified as an input to the
`compression engine
`‘Eachelement of the quantization table is an
`integer value from one 1:, 255, which specifies the stepsize of the
`quantizer‘ for the __corresponding TDCT coefficient.i The purpose of
`quantization is toachieve thenhmaximum amount of compression by
`representing DCT_coefiicients with no greater precision than is necessary
`to achieve the desired image qua1ity_.V Quantization is a many-to—one
`mapping and, therefore‘, is fundamentally lossy.
`mentioned above,
`quantization tables havevbeen designed which limit the lossiness to
`imperceptible aspects of the image so that the reproduced image is not
`perceptually different from the source-rimage.
`V
`The quantizer 20 performs a simple division operation between each
`DCT coefficient and the corresponding quantization table element; The
`lossiness occurs because the quantizer '20v disregards any fractional
`remainder. Thus, the quantization function can be represented as shown
`
`in Equation 2 below.
`
`YQ[k; 1] = IntegerRound( )
`
`HUAWEI EX. 1116 - 6/714
`
`
`
`4
`
`Patent Application
`.
`Attorney Docket Number 10948934
`
`where Y(k,l) represents the ,(k,1)-tli DCT element land Q(k,1) represents
`the corresponding quoantizationvtable 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, 1] = YQ[l<, 11 QE[k, 1].
`
`the t 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 ofthe quantization
`step, considerable effort has go_ne,into designing the quantization tables.
`These efforts are described further below following a discussion of the
`final step in the JPE'G'ricompr_ession technique.
`_
`The final step of the JPEG standard is an entropy encoding, which
`A is performed by an’ entropy encoder 28. The entropy encoder 28 is 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 statistical characteristics. The JPEG standard specifies two entropy
`coding ‘ methods: ., Huffinan coding and arithmetic coding.
`The
`compression engine ofFig. 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. Huffman encoding is a well known encoding technique that
`produces high levels of lossless compression. Accordingly, the operation
`of the entropy encoder i28'is not further described. .
`I
`Referring now to Fig. 2, a typical JPEG compressed file is shown
`
`HUAWEI EX. 1116 - 7/714
`
`
`
`S
`
`l
`
`I
`
`Patent Application
`_
`Attorney Docket Number 10948934
`
`V
`
`generally at 34. The compressed file includes a JPEG header 36, the
`quantization (Q) tables 33 and the Huffman (H) tables 40 used in the
`compression process, and the compressed image data itself. From this
`compressed filer34 a perceptually indistinguishable version oftheporiginal
`source image can be extracted when an appropriate Q¥table is used. This
`extraction process is described belowwith reference to Fig.3.
`The
`T A: JPEG decompression engine 43 is shown in '_ Fig.
`decompression engine essentially operates in reverse ofthe compression
`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 contained in the _
`header. The H tables are then stored in H tables 346 while the Q tables
`are stored in
`tables 48; ‘The compressed image data is then sent to an
`c entropy decoder 50 over a bus 52. The'Entropy Decoder decodes the
`Huffman’ encoded compressed image data using thevl-I tables 46. The
`output of the entropy decoder 50 are the quantized
`elements.
`The qu’antized DCT elements are thentransmitted to an inverse
`quantizer’54 over a bus
`The inverse quantizer 54_/multiplies the
`quantized DCT elements
`the corresponding quantization table
`elements found in i ‘Q tables "_48.
`described above, this inverse
`quantization step does not yield thetoriginal source image data because
`the quantization step truncated or discarded the fractional remainder
`before transmission of the compressed image data.
`I
`The inverse quantized DCTelements are then passed to an inverse
`discrete cosine transformer (IDCT) 57 via bus 59,-. which transforms the
`data backp into‘ the time domain using the inverse discrete cosine
`transform (IDCT). The inverse transformed data isthen transferred to
`block-to-"raster translator 58 over 7a bus 60. where the blocks of DCT
`
`elements are translated into a raster string ofdecompressed source image
`
`HUAWEI EX. 1116 - 8/714
`
`
`
`6
`
`l
`
`l
`
`Patent Application
`.
`.
`d
`_l
`Attorney Docket Number 10948934
`
`data. From theldecompressed 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 image.
`As described above-, the quantizationstep produces some lossiness in the
`process ofcompressing the data. By carefully designing the quantization
`tables, however, the prior
`methodshave constrained, the loss to
`visuallyimperceptible portions of the image. These methods, and their
`shortcomings, are: described below.
`b
`_
`l
`The Jl-l‘EG_standard includes two examples. of quantization tables,
`one for luminance channels and one for chrominance channels. See
`International Organization forflstandardizationz "Information technology
`' - digital compression encodingof continuous - tones still images - part 1:
`Requirements and Cruidelines, " IHSO/IEC IS_10fl91'8_-1,‘pOctober go, 1992.
`These tables are known as the K.1 and -K.2,-tables, respectively. These
`tables have been designed basedon the perceptually lossless compression
`of color images represented invthe Y U V color space.
`‘ These tables result in ‘visuallypleasing images, but yield a rather
`low compression ratio-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 is applied to each of
`the elements in the quantization tables.. The larger the Q-factor the
`larger the achievable compression rate. Even if the original tables are
`carefully designed to be perceptually lossless, however, a large Q-factor
`will introduce artifacts in the reconstructed image, such as blockiness in
`areas ofconstant color or
`in tei:t—scale characters. Some ofthese
`artifacts _can_ be ‘ effectively cancelled _ by post-processing of
`the
`reconstructed image by passing it through a tone reproduction curve
`correction stage, orby segmenting the image and processing‘ the text
`separately. v However, such’ methods easily introduce new artifacts.
`
`HUAWEI EX. 1116 - 9/714
`
`
`
`7
`
`g
`
`Patent Application
`V
`Attorney Docket Number 10948934
`
`A
`'
`Thereforeythese methods are not ideal.
`As a result‘ of the inadequacy of the Q-factor approach, additional
`design methods a for JPEG ‘discrete quantization tables have been
`proposed. These methodsucan be categorized as either perceptual, which
`means based on the human Visual system (I-IVS) or based on information
`‘theory criteria. Theseamethods are also designated as being based on the
`removal of subjective or 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.
`T
`V
`A
`V
`Quantization is not theonly cause ofimage‘. degradation. The color
`source image data itself mightbe compromisedl, For scanned colored
`images, the visual quality of the image can bedegraded because of the
`inherent limitations of color scanners. These limitations are mainly of
`two
`liindsi
`l_imite'd_' modulationj
`transfer. "function
`(MTF) V and
`misregistration._
`The . modulation -transfer function refers to the
`mathematical representation or transferfunction ofthe scanning process. V
`There are inherent limitations
`representing the scanninigprocess by
`the MTF and these limitations are the main cause ofpixel aliasing, which
`produces fuzzy black text glyphs ofgrayish appearance. Misregistration,
`on the other hand; refers to theurelative misalignmentof the scanner
`sensors for the various frequency bands. For example, the Hewlett
`Packard Scan Jet How has a color misregistration tolerance of+/- 0.076
`mm for red and blue
`respect
`to green.--
`V This amount of
`misregistration is significant considering the size ofan image pixel (e.g.,
`0.03 mm at 300 dots per inch (dpi)).
`_
`A
`These limitations significantly degrade text color images because
`sharp edges are very important for reading efficiency. The visual quality
`
`HUAWEI EX. 1116 - 10/714
`
`
`
`‘8
`
`‘
`
`’
`
`~
`
`Patent Application
`-_
`‘
`_
`Attorney Docket Number 10948934
`
`of text can be improved, however, using prior art edge enhancement
`techniques. Edge enhancement can be performed inpeither the spatial
`or frequency domain. a In the spatial domainV_(i’.e., RGB)“, edge crispening
`can be performed by discrete convolution of thescanned image
`an
`edge enhancement kernel. This approach is equivalent to filtering the
`image with a high-pass’ filter. However, this technique is computationally
`intensive- An M X N convolution kernel, for example, requires MN
`multiplications and additions per‘ pixel.
`For edge sharpening in the frequency domain, the full image is first '
`transformedinto the frequency domain using the Fast Fourier Transform
`(FFT) or
`the Discrete ..Fourier Transform (l)FT),
`low frequency
`components are dropped, and then the image is,transfor1ned back into the
`time domain; This frequency domain method, as with the spatial domain
`method,
`also computationally intensive’;
`. Moreover, it uses a
`transformation different than that required by the J standard.
`Accordingly, the need remains for a, computationally efficient
`method for improving the visual quality ofimages, and in particular text,
`
`in scanned images.
`
`SUMMARY or THE lNVENTlON
`The invention is a method of compressing and decompressing
`images which comprises using one quantization table (Q3)for compressing
`the image and a second quantization table (QD)_for decompressing the
`image.
`In general, compression and decompression are performed in
`
`V conformance with the JPEGtstandard. The second quantization table QD
`is related to the first quantization table according to. the following general
`
`expression:
`
`Q1j=SXQE+B,
`
`HUAWEI EX. 1116 - 11/714
`
`
`
`Patent Application
`_
`» Attorney Docket Number 1094893-1
`
`where S is a scaling matrix having each element S[k,l] formed according
`to the following expression:
`
`.s[k,1]2 = 'V*[k,1]/Vy[k,‘1]
`
`Where V* is a variance matrix of a reference image and Vy is a variance
`matrix of a scanned image; and where
`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
`quantizevd irnagesdatagi
`is used in: decompression to recover the image.
`The. referencelimage is a preselected continuous-tone ‘image, either
`grayscale or color dependingon the images to be processed; The reference
`imageis renderedvinto a target image file. The target image file is not
`generated
`a scanner‘, solthe data therein is not compromised by any of ~
`the inherent limitations of a color scanner; Thus, the variance of the A
`target image data, which is a statistical representation of the energy or
`freauency content ofthe image, retains the high-frequency components.
`, The reference image can be any continuous-tone image, but in the
`preferred embodiment the reference image includes text with a seriffont
`because the seriffont has good visual quality which the method preserves.
`The scanned image, although it canbe any image, in the preferred
`embodiment is .a printed version‘ of the referencerimage; Thus, the
`variance of the scanned image represents the energy or frequency
`composition the-» reference image but which is compromised by the
`inherentlimitations ofthe scvannevr; The scaling matrix, therefore, boosts
`the frequency components that are ‘compromisediby the scanning process.
`
`HUAWEI EX. 1116 - 12/714
`
`
`
`1 O
`
`V
`
`Patent Application
`a
`_
`y
`T
`Attorney Docket Number 10943934.
`
`’
`
`‘
`
`A preferred e_mbodiment of the invention is described herein in the
`context ofa color facsimile (fax) machine. The color fax machine includes
`a scanner for renderingda color himageinto color source image datathat
`represents the color image’, a compression engine thatcompresses 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 table is used to
`quantize the image “data transformed using the discrete cosine transform
`(DCT). The second quantization table is encapsulated withthe encoded
`quantized image data for use in decompressing the image. The second
`quantization table is related.to the first quantization table in the manner
`described above; _When used to transmit and receive color images
`between two locations, the machine transfers the images with higher
`
`quality than prior psystems.
`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
`enhancingmethod ofthe invention. This capability results in a lower cost
`color facsimile product than is possible using the prior art image
`
`’ enhancement techniques.
`Theuforegoing and other objects, features and advantages of the
`invention will become more readily apparent from the following detailed
`description of a preferred embodiment ofthe invention which proceeds
`with referenceto the accompanying drawings. ‘
`ch
`
`BRIEF DESCRIPTION or THE DRAWINGS
`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.
`
`HUAWEI EX. 1116 - 13/714
`
`
`
`11
`
`Patent Application
`V
`.
`Attorney Docket Number 10948934
`
`Fig. 3 is a block diagram ofa prior art JPEG decompression engine.
`Fig. 4c is a flow chart of a method of forming a scaled quantization
`table according totheinvention.
`_
`F
`V
`5
`is a‘ drawing I of a JPEG compressed file including a
`quantization tablescaled according to the invention.
`A Fig. 6is a block diagramofa JPEG decompression engine according
`to theinvention.- -
`A
`machine including JPEG
`Fig 7 is a block diagram of a color
`compression and decompression engines according to the invention.
`
`DETAILED DESCRIPTION’ OF THE PREFERRED EMBODIMENT
`
`The text and image enhancing technique according to the invention
`is integrated into the ‘decoding ‘or inverse: quantization step that is
`necessarily required by the JPEG standard. The invention integrates the
`two
`using
`‘different quantization tablesza first quantization table A
`(QE) for use
`quantizing the image data during the compression step and
`a second quantization table (Qn)tfo.r use ‘during the decode or inverse
`quantization during the deeornpressionpprocessi The difference between
`the two tables, in particular the ratio of the two’ tables, determines the
`amount ofimage enhancing that is done in the two ‘steps; By integrating
`the image einhancingiand inverse quantization steps, themethod does not
`require anv additional computations than al-ready required for the
`compression and decompression processes..
`A
`'
`In order to understand the operation ofthe invention, the following
`mathematical derivation isnecessary. Let Q]; be the second quantization
`table used during the decoding orinverse quantization step. Then let QD
`be related to‘ the first quantization table Qg, used during the quantization
`step, by the following" expression:
`
`9
`
`HUAWEI EX. 1116 - 14/714
`
`
`
`~
`
`Patent Application
`_
`g
`Attorney Docket Number 10948934
`
`Q1$e=(9_§Ql..:‘)+B
`
`V
`
`to
`
`a
`
`(1)
`
`where ‘S is a scaling m'atr_ix, which scales ‘each element’ of the first
`quantization _table-
`to a Acorvrespondingi element
`in the . second
`quantization table Q3. The scaling matrixi'S is not used atrue matrix
`multiplication; rather,_ the multiplication is an element-by-element
`multiplication. Each element in the first quantization table QE has a
`corresponding element in the scaling matrix S that when multiplied
`together produce the ‘corresponding element in the second quantization
`table QD.
`'
`_
`The matrix B isja 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 zerovor non-zero
`values depending on the desire_d_brightness. For purposes ofthe following
`discussion and derivation;_ho_wever, it will be assumed that the B matrix
`contains zero elements onlvlto simplify the derivation.
`V
`The text and image enhancing.teclmiqu_e of the ‘invention uses a
`variance matrix to represent the statisticalproperties of an image. The
`varianceflmatrix is an
`x matrix, where each element in the variance
`matrix is equal to the variance. of a corresp'_onding DCT coefficient over
`
`A
`
`the entire image. The variance is computed in thetraditional manner, as
`is known in the art.
`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 describedabove. In order
`to do this, the method‘ takes advantage of the relationship between the
`uncom‘pressedima‘ge and the compressed image. The following derivation
`
`HUAWEI EX. 1116 - 15/714
`
`
`
`Patent Application
`.
`.[
`Attorney Docket Number 1094893-1
`
`will make this relationship clear.
`‘Let _V*_[k‘,l] ‘denote thevariance of the [k,l] frequency component of
`' a reference image. Ideally, thisimage contains those critical attributes
`that: the technique ‘seeks to preserve, for example, text. This variance
`matrix is of an ideal or reference image in that-itvis not rendered into
`color source image data by atscanner but, instead, is rendered into its
`ideal» form by software, described further below. Thus, the color source
`
`image data of the” reference image does not suffer from the image
`
`degradation due to the inherent limitations ofthe scanner. Therefore, the
`variance ofthe reference image retains the high-frequency characteristics
`ofthe original reference image.
`I
`The method produces a resulting decompressed image that has
`approximately the same variance as the Variance‘ of the reference by
`modifying the quantization table. Thus, the method produces the
`
`following relationship:
`
`Vrrk, 11,=,V*[k, 11
`
`
`
`
`
`<2) i
`
`, However, the decompressed image(Y’) is relatedito the original quantized
`image (Ya) by the following expression:
`
`’ iY’[k, 11= Yetk, 11 Qn[k,~ 11
`
`
`
`
`
`
`
`
`
`l
`
`(3)
`
`Substituting equation (1) into equation (3) yields the following equation
`below:
`
`Y’[1i,ll=YgE[l<,1](S[k,1] Q2[k,1])
`
`my
`
`
`
`e
`
`(4)
`
`The varianceof the decompressedfiinage (VY’) can then be expressed by
`
`HUAWEI EX. 1116 - 16/714
`
`
`
`Patent Application
`_
`Attorney Docket Number 10948934 ‘
`
`the following expression: M
`TVY‘-[k, 1] =Var_(Y’[k,’.1_])_(S.[_kV, 1] Y§g[k, 1]_dQE[k,V1]) ;
`
`’
`
`(5)
`
`Reducingthis expression fyieldsithe followingi
`
`(6)
`V
`T
`V
`vik, i1=‘ s2[k.1h]Vy[k,i11 h
`where Vy represents the variance ofthe originaluncompressed image.
`Substituting equation (6) into equation (2) yields the following‘
`relationship between the scaling matrix S and the variances of the
`reference imageA(V*) and the original image
`
`S[k; 1]? ¥‘V*[k._ 1_] / Vv[k, .1],
`
`‘
`
`V
`
`‘
`
`(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 s"calin'g_ma‘trix-. This method is shown in a
`more generalized fashion in FIG; 4.
`
`Preferred Embodiment of th ed‘ Metho"51
`_
`In FIG. 4, a method 62 of forming
`scaled quantization table
`according to the invention is shown. The first step 64 is to generate a
`[reference ‘image. This reference image, in the preferred embodiment,
`embodies certain valued features or elements that the method seeks to
`preserve. In the preferred embodiment, these critical_ elements include
`highly readable text such as those tfpefaces having a serif font, e.g.,
`Times Roman. The selection ofthe reference image is important because
`it is the frequency or energy characteristics‘, of this image that the text
`
`A;
`./’
`
`HUAWEI EX. 1116 - 17/714
`
`
`
`15
`~.
`
`,
`
`Patent Application
`.
`V
`*
`_
`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
`typical images; Ezlzainples "ofsuch typical images are those using. different
`fonts l(e.g.,l Palatine and Devanagari), handwriting, short-hand, line
`drawings, schematics, bar codes, etc. These different images can further
`be categorized in" a number ofclasses. .
`i
`This generating step 64 is performed on a computer, typically using
`a word processor or desktop publishing application such as Adobe
`Illustrator or Microsoft Word. The image is entered into the computer
`-and then rendered by the application into reference image data by the
`application. The reference image data will bé7i_n' the appropriate color
`space, e.g.,- CIELAB or RGB,
`to c 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 color source
`image data file‘ using l)cis:playPiostscriptc.:l Alternatively, other ' page
`description‘ languages can be used todescribe theimage such as the PCL
`language by Hewlett-Packard and then rendered into a bit map by an
`appropriate rendering program,‘
`i
`_
`A
`‘C)ncce_the r"efe'r'e_nce imagelis generated and rendered into reference
`image data, the average energy. of-vthe_ reference image is determined in
`step 66. ‘In the preferred embodiment, this step includes computing the
`yariance matrix "t) for the reference image data. ‘ The variance matrix,
`as is known in the art, statistically represents thefrequency components
`or energyccontainedin the image. Unlike a scanned image, the reference
`image does not suffer from any of the inherent limitations of the color
`scanner because it
`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 ofthe reference image.
`
`
`
`{ @?“”’
`
`HUAWEI EX. 1116 - 18/714
`
`
`
`1 6
`
`2
`
`‘ Patent Application
`.
`.
`‘Attorney Docket Number 10948934
`
`Instep 68, afscanned image is scanned or selected from one or more
`V
`V
`stored pre-scanned images; This scanned image is one that suffers from
`the inherent limitation of thebscanner. A This scanned image can be any
`image, _but in" the-preferreduembodiment it is a scanned version of the
`reference image generated in step 64,2 or of the same type of image used
`to form an averaged reference image.
`2
`As in step 66, the average energy’ of the scanned image is then
`determined in step 70. 2 The average energy again is represented by a
`variance matrix
`ofAthescanned image.
`The variance matrix (V*) of thereference image and the variance
`matrix (Vy) of the scanned image are then used to compute the scaling
`matrix Sin step 72. This stephinvolves solving equation (7) above for
`each element in the scaling matrix S.
`s
`Finally, in step 74 the scaled version of the quantizationtable is
`calculated. This step isasimple element-by-element multiplication as
`represented by ‘equation (1) above.
`I
`V
`The use of the scale tables is seen clearly with reference to FIG. 5.
`In FIG. 5, a first set of Q tables 76 is" provided to a JPEG com