`
`IllHilllltllllillllllllllllllllfllllllllllllllll
`
`U-s- PATENT APPLICATION
`
`SERIAL NUMBER
`
`O8/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
`
`**CQNTINUI]_\]'G DATA**********~k*-k~Jr*******
`VERIFIED
`
`-**FOREIGN/PCT APPLICATIONS************
`VERIFIED
`
`FOREIGN FILING LICENSE GRANTED O4/26/95
`
`SHEETS
`DRAWING
`
`7
`
`INDEPENDENT
`CLAIMS
`
`FILING FEE
`RECEIVED
`
`ATTORNEY DOCKET NO.
`
`.
`
`$1,158.00
`
`10940893
`
`RECORDS MANAGER
`LEGAL DEPARTMENT 2OBO
`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 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
`
`
`
`WM11111:Iunmmullunllllunlaullz
`
`
`
`SEHIALINUMBEB ‘_
`
`‘ oa/4ii,369vi-
`
`. FIIINEDATE
`
`.
`
`vo~3/57/§s’ -V T
`
`‘
`
`‘
`
`E qionsms _1’a.§z_:.éT’_z-1'L'\'._,-&:»z’;Lc§%f;‘;:.j%aE;+_'-c»);
`I KoNs1jAN1fIp_Io_s 'KoNsfpA_F'i'INIDEs;
`
`**¢o31ku-1jqUm'G.
`VERIFIED
`_E
`
`V‘
`
`**'F.C)REI'_GN/PCT :A1$i='Lid2xTibNé¥*vé.»~*él'w;-*w*. V‘
`‘ VERI'FIED _
`
`b
`
`‘
`
`EHDUEAEIDNIT ' E_
`
`V
`
`.
`
`Ems
`
`<
`
`‘-
`
`:1 MERGER" 'qoHNsc)N 'Mé<':o'LI;cM_:s'1'oLdwi*I‘2"1- 5 f "
`1C)30_SW.MpRRISQN.'ST
`'
`'
`E
`'
`-
`; PORTLANDOR 9'7_2'o5,- 3:
`
`EILINEEEE
`' HECElVED-
`
`V. "
`
`AUUHNEY DOC:KET ND.
`
`'
`
`_$;,i5e§6oE
`
`f[ioé46893EE
`
`’ TEXT AN15 ‘JIMAGE Si-IA'RPEf\IIN'G”~0F JPE§G’v"‘(!'OM15fRES$ED-’IMAGiE§S4-IN ‘THE ‘FREQUENCY’
`' DOMAIN
`
`ihé reci5‘r_a§*.'o%?¢}{é _Uhitéd_' s'tates 1
`‘.'rét‘o"ié 5 _£r'u’é ’cc_’:py.f’r' m‘
`‘This is-"to .dér'fif' ',th"at"fariné§$£éd
`Patent an_c:i‘-'l'Tra
`g_h1arl_< Offipe 9'f'jthe applicatiofi which is identifiéd ab’p'vé.'
`»
` Byauthdrit'}5ofIi1e
`'-
`' -
`'
`COMMISSIONER OF PATENTS AND>THA[>}EMAHKS
`
`bate.
`
`b
`
`-
`
`ceniryiniioifieer
`
`.
`
`I
`
`HUAWEI EX. 1016 - 2/714
`
`
`
`;*.,,,Ev.:.L.§::.::\.:,:<:~;I;g°gMPA~*
`
`P.0. Box 10301
`Palo Ana, California 9430341890
`
`
`
`
`
`. COMMISSIONER OF PATENTS AND TRADEMARKS
`Washington, D.C. 20231
`Slr:
`
`
`
`V
`.
`AT|'OFl_NEY DOCKET No.
`
`,
`
`.=ITEN{I$IEIc‘?l§o%
`
`~ 1 094893-1
`
`(
`
`) Design
`
`(x) originalpatent application,
`( ) continuing application,
`
`( )continuation-in-part
`
`( )continuation or
`
`( )divisional
`
`or S/N
`
`filed
`
`lNVENTOR(S): Giordano Beretta et al.
`
`TITLE:
`
`TEXT AND IMAGE SHARPENING OF JPEG COMPRESSED IMAGES IN THE
`FREQUENCY DOMAIN
`‘
`
`Enclosed are:
`
`) unsigned or partially signed
`(
`(X) signed
`(X) The Declaration and Power—of_Attorney.
`.(
`informal drawings
`(one set)
`(X)
`7
`sheets of (X) formal drawings
`(I
`) Information Disclosure Statementgand Form PTO-1449
`(
`) Associate Power of Attorney
`(
`) Priority document(s)
`(A)
`(Other)
`.
`(fee$
`
`)
`
`-
`
`«
`
`CLAIMS AS FILED ev OTHER THAN A SMALL ENTITY
`(2)
`(3)
`»
`(4)
`(1)
`RATE
`. FOR
`NUMBER FILED
`NUMBEF; Ex'mA
`$ 22
`T X
`INDEPENDENTM X
`$ 76
`ANY MULTIPLE.
`"41 $2“
`'
`BASIC FEE: Design( $300.00 ); Uti|ity( $750.00)
`
`-
`
`V
`
`TOTAL FILING FEE
`
`TOTAL CHARGES T0 DEPOSIT ACCOUNT
`
`(5)
`TOTALS
`
`$
`
`$
`
`$
`
`$
`
`(JNO0'!
`
`1,153
`
`1,1 53
`
`to D_eposit.Account 08v-2025. At any time‘ during_the_pendency of this application,
`1,158 A,
`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 Deposut Account 08-2025 under 37 CFR 1.19, 1.20 and 1.21. A
`duplicate copy of this sheet is enclosed. A
`
`I
`
`‘Express Mail‘ labeln I
`Date of Deposit March 27 , 1995
`I hereby certify that this is being deposited with the
`United States Postal Service ‘Express Mail Post
`Office to Addresses‘ service .under 37 CFR 11.10 on
`the date indicated aboveend is addressed tofthe
`Commissioner
`of
`Patents
`and
`Trademarks,
`Washingt
`.,D-C-20231'-
`
`By u §
`Typed Namei Linda A. limura
`
`Respectfully submitted’
`‘_
`.
`Giordano Beretta et al.
`
`~
`C7 I
`I
`,
`
`By
`
`"c'o/
`
`_
`
`C. Douglass homas
`
`Attorney/Agent for Applicant(s)
`R99 N0-
`32.947
`Date: March 27, 1995
`
`Rev 10/94 (Form 3.04)
`
`- Attach as First Page to Transmitted Papers - Telephone No-3 (415) 857'8129
`
`HUAWEI EX. 1016 - 3/714
`
`
`
`Patent Application
`,
`v
`’
`Attorney Docket Number 1094893-1
`
`‘
`
`TEXT AND IMAGE‘SHARPENING OFAJPEG COM
`E
`A
`is IN THE FREQUENCY DOMAIN
`.917 ‘ RELATED APPLICATION DATA —l
`This application incorporates subject matter disclosed in commonly-
`assigned application entitled ] METHOD 1 FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTHAPPLICATIONS,
`Ser. No, (Q 2365[’,7f'1led on even date herewith.
`
`l
`
`,
`
`. EAOKGROUND OF THE INVENTION
`
`‘invention relates to data compression using the JPEG
`This
`compression standard for continuous - tone still images, both grayscale
`and color.
`E
`M
`_A
`I
`q
`_A committee‘ known as "JPEG," which stands V for "Joint
`Photographic Experts Group," hlasestablished a standard for compressing
`continuous—tOne still images, both Igrayscale and color. _This standard
`represents a compromise between reproducible image quality and
`compression rate. To achieveacceptable compression» rates, which refers
`to the ratio of the uncompressed image to the iconipressed. image, the
`JPEG standard adopted a lossy compression I technique. The lossy
`compression technique was required given the inordinate amount ofdata
`A needed to represent a color image, 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 lossin the image can be confined to
`imperceptible areas of the image, which produces a perceptually loss less
`. uncompressed.image. The achievable compression rates using this
`technique are in the range of 10:1 to 50:1.
`_
`_
`Figure
`shovvs ablock diagram of’ a typical implementation of the
`
`HUAWEI EX. 1016 - 4/714
`
`
`
`V 2
`
`Patent Application
`.
`_
`V
`Attorney.Docket Number 10948934
`
`JPEG-compression standard.‘_ The_ block diagram will be referred to as a
`compression engine;
`compression engine 10‘ operates on source image
`' data", which represe_nts a source image in a given.color space such as
`CIELAB. The ‘source image data has a certain resolution, which is
`determined by how the usage 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 ofbitsused to represent the
`image pixel;
`T
`be
`The source image data is typically formatted as a raster stream
`of data. The compression technique, however, requires the dataito be
`represented. in blocks. These blocks represent a two-dimensional portion
`of the source image data. The JPEG standard uses 828 blocks of data.
`Therefore, a" raster-to‘-block translation unit
`translates the raster
`source image data into '81r8 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 8:8 blocks are then forwarded to a discrete cosine
`transformer 16 via bus 14.
`1
`I
`V
`r
`A 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
`(21)) "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 discrete cosine (FDCT)
`function as shown below, hence the name.
`’
`
`HUAWEI EX. 1016 - 5/714
`
`
`
`Patent Application
`_
`Attorney Docket Number 10948934
`
`V
`
`A
`
`A.
`
`7
`
`7
`
`»
`
`_
`
`_
`
`.
`
`.
`
`Y[k,1] = good - C(1)[2‘2S(x;y) - cos cos
`
`.
`
`,
`
`i
`
`x=0y=0
`
`-
`
`where: C(k), C(l) =2 1/\/.ffo'rk,l = O; and
`
`p cm, 0(1) ; lotherwise
`
`The output of the transfonner 16 is an 8x8 block of DCT elements
`or coefficients, correspondingitoi theVDC'I‘ basis vectors.’ This block of
`transformed image data is then forwarded to a quantizer 20 over a bus
`18. The quantizer
`quantizes the 64 DCT elements using a 64-element
`quantization AtabIe~24‘,i 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 stepisize of the
`quantizer for the corresponding DCT. coefficienti The purpose of
`quantization is to ~‘ achieve the ‘maximum amount_ of compression by
`representing DCT_coefficients with no greater precision than is necessary
`to achieve the Vdesired image quality. Quantization is a many-to-one
`mapping and, therefore, is fundiamentallyilossy. As mentioned above,
`"quantization tables havebeen designed which limit the lossiness to
`imperceptible aspects of the image so that the reproduced image is not
`perceptually different from the sourceaimage.
`_
`V
`k
`The quantizer 20 performs a simple division operation between each
`DCT coefiicient and the corresponding quantization table element. The
`lossiness occurs because_ the quantizer '20i disregards any fractional
`remainder. _Thus,_ the quantization function canbe represented as shown
`
`in Equation 2 below.
`
`HUAWEI EX. 1016 - 6/714
`
`
`
`4
`
`Patent Application
`.
`'
`Attorney Docket Number 1094893-1
`
`where Y(k,l) represents the A(k,1)-thi DCT elernentdand Q(k,l) represents
`the corresponding quantizationtable “element.
`To reconstruct the source image, this step is reversed, with the
`quantization table element being multiplied by the corresponding
`quantized DCT coefficient. The inverse quantization step can be
`represented by the following expression:
`
`Y’[k, 1] = YQ[‘].{,‘:l] QE[k, 1].
`
`the fractional part discarded during the
`As should be apparent,
`quantization step is not restored. Thus, this information is lost forever.
`Because of the potential impact on the image quality of the quantization
`step, considerable effort has gone into designing the quantization tables.
`These efforts are described further below following a discussion of the
`
`_
`final step in the JPEG compression-technique.o
`V
`V The final step of the PEG standard is an entropy encoding, which
`is performed by an entropy encoder 28. The entropy encoder 28 is coupled
`to the quantizer 20 via abus 22 for receiving the quantizedimage data
`therefrom. The entropy encoder _-achieves additional lossless compression
`by encoding the quantized DCT coefficients "more compactly based on
`their statistical characteristics. The JPEG standard specifies two entropy
`coding ‘ methodsi. Huffman coding and arithmetic coding.
`The
`compression engine ofFig. 1 assumes I-Iluffman coding is used. Huffman
`encoding, as is known in the art, uses one or more sets of Huffman code
`tables These tables may be predefined or computed specifically for a
`given" image. Huffman encoding is a well known encoding technique that
`produces high levelsioflossless compression- Accordingly, the operation
`of the entropy encoder l28"is not further described. .
`I
`Referring now to‘ Fig. 2, a typical JPEG compressed file is shown
`
`HUAWEI EX. 1016 - 7/714
`
`
`
`Patent Application
`ttorney Docket Number 1094893-1
`
`,A
`
`.5
`
`header 36, the
`generally at 34. The compressed file includes a
`quantization (Q)‘tables 38 and the Huffman (H) tables 40 used in the
`compression process, and the compressed image data'42 itself. From this
`compressed file 34 a perceptually indistinguishable version oftheoriginal
`source image can be extracted when an appropriate Q-table is used. This
`extraction process is described belovv with reference to Fig. 3.
`The
`A.‘ JPEG decompression engine 43 is shown in '_ Fig.
`decompression engine essentially operates in reverse of the 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 _46 While the Q tables
`are stored in Q tables 48. The compressed image data is then sent
`an
`entropy. decoder 50 over a bus 52. The'Entropy _Decoder decodes the
`Huffman encoded compressed image data using the_H_tables 46. The
`output of the entropy decoder 50 are thequantized
`elements.
`The quantized DCT elementslare thentransmitted to an inverse
`quantizer’54 over a bus
`The inverse quantizer 54Hmu1tip1ies the
`quantized DCT elements
`the corresponding quantization table
`elements found in 4 ‘Q tables "48.
`described above, this inverse
`quantization step does _net yield the original source image data because
`the quantization step truncated or discarded the fractional remainder
`before transmission of the compressed image data.
`b
`A
`The inverse quantized DCT elements are then passed to an inverse
`discrete cosine transformer (IDCT) 57 ‘via bus 59,.-ivvhich transforms the
`data back into the time domain using the inverse discrete -cosine
`transform (IDCT); The inverse transformed data issthen transferred to
`block-to-raster translator 58 over 7a bus 60. vvhere the blocks of DCT
`
`elements are translated into a raster string ofdecompressed source image
`
`HUAWEI EX. 1016 - 8/714
`
`
`
`5
`
`Pate/ntAp’p1ication
`_.
`.
`A
`Attorney Docket Number 1094893-1
`
`data._ From theldecompressed source image data, a facsimile of the
`original source image’ can be..reconstrlucted 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 art methodsl have constrained» the loss to
`visually.imperceptible portions of the image. These methods, and their
`shortcomings, are described below.
`i
`_
`i
`V
`The
`standard‘ includes two examples of quantization tables,
`one for‘ luminance channels and one for chrominance channels. See
`International Organizationfor Standardization: "Information technology
`- digital compression encodi'ng‘of continuous - tones still images - part 1:
`"Requirements and Guidelines’, " ISO/IEC 1s1o9i8.1, October 20. 1992.
`These tables are known as the K.1 and -K.2 tables, respectively. These
`tables have been designed based on the perceptually lossless compression
`of color images represented in the 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 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 iQ-factor
`will introduce artifacts in the reconstructed image, such as blockiness in
`areas of constant color or
`teizt-‘scale characters. Some ofthese
`artifacts _d can be effectively. cancelled _’ by post-processing of the
`reconstructed image by passing it through a tone reproduction curve
`' correotion stage, "or by segmenting the image and processing the text
`separately. v However, such methods easily introduce new artifacts.
`
`HUAWEI EX. 1016 - 9/714
`
`
`
`7
`
`-
`
`g
`
`Patent Application
`V
`Attorney 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 methods can be categorized as either perceptual, which
`means based on the human visual system (I-IVS) or based on information
`theory criteria. Thesemethods 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 J Quantization Tables for Low Bandwidth Applications,"
`commonly_ assigned to the present assignee, incorporated herein by
`reference.
`a
`A
`V
`T
`Quantization is not theonly cause ofimage‘ degradation. . The color
`source image data itself mightbe compromised. . For scanned colored
`images, the visual quality of the image can ‘be degraded“ because of the
`inherent limitations of color scanners. These limitations are mainly of
`two
`lzindsi
`l_imited_ modulation‘, transfer *1 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 scanning process 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 therelative misalignment of 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.08 inn}: 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. 1016 - 10/714
`
`
`
`'8
`
`‘
`
`’
`
`-
`
`Patent Application
`1,
`q
`_
`Attorney Docket Number 10948934
`
`of text can be improved, however, ‘using prior art ledge enhancement
`techniques.‘ Edge enhancement can be perfonned inpeither the spatial
`or frequency domain.‘ In the spatial domain _(i’.e. RGB)'i_, edge crispening
`can be performed 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
`computationally
`intensive. An M x N convolution kernel, for example, requires MN
`_ mtfltiplications and additionsper pixel.
`.
`V For edge sharpening in the frequency domain, the full image is first ’
`. transformed into the frequencydomain using the‘ Fast Fourier Transform
`(FFT) or
`the Discrete , Fourier Transform (DFT),
`low frequency
`components are dropped, and thenthe image istransformed back into 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 by the J standard.
`Accordingly, the need remains for a, computationally efficient
`method for improving the visual quality ofimages, and
`particular text,
`
`in scanned images.
`
`* SUMMARY on THE lNVENTlON
`i
`The invention is a method of compressing and decompressing
`imageswhich comprises using one quantization table (QB) 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 JPEGstandard. The second quantization table QD
`is related to the first quantization table according tothe following general
`
`expression:
`
`QD=SxQEi+Bs
`
`HUAWEI EX. 1016 - 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,1l/Virlkyill
`
`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
`is transmitted with theencoded
`quantized
`data,~and is used in decompression to recover the image.
`Thereferenceimage is a preselected continjuouis-tone image, either
`grayscale or color depending on the images to be processed; The reference
`irnageis renderedvinto a target image file. The target image file is not
`‘generated
`a scanner, sothe data therein is not compromised by any of »
`the inherent limitations of acolor scanner. Thus, the variance ‘of the
`target image data, which is a statistical representation of the energy or
`frequency content ofthe image, retains the high-frequency _co'mponents.
`, 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 themethod preserves.
`The scanned image, although it canbe any image, in the preferred
`embodiment is .av.printed' version of the reference image. Thus, the
`variance of the scanned image represents the energy or frequency
`composition of_ the reference image but which is compromised‘ by the
`‘ inherentlirnitations ofthe scanner; The scaling matrix, therefore, boosts
`the frequency components that are compromised by the scanning process.
`
`/“W.
`
`K L)
`
`HUAWEI EX. 1016 - 12/714
`
`
`
`1 0
`
`V
`
`Patent Applicafion
`T
`l
`q
`T
`Attorney Docket Number 10948934
`
`‘
`
`A preferred embodiment ofthe invention is described herein in the
`context of a color facsimile (fax) machine. The colorfax machine includes
`a scanner for rendering a color eimageinto 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.
`I
`The second quantization table can be precomputed and storedin the
`compression engine. in which case there are no additional computational
`requirements for the compression. engine‘ to implement the image
`enhancing method ofthe invention. This capability results in a lower cost
`color facsimile product, than is possible using the prior art image
`
`enhancement techniques.
`V The foregoing and other objects, features and advantages of the
`invention will become more readily apparent’ froinlthe following detailed
`description of a preferred embodiment of the invention which proceeds
`with reference‘ to the accompanying drawings. ‘
`
`_BRIEF DESCRIPTION ‘QF THE DRAWINGS
`is a block diagram of a prior art JPEG compression engine.
`Fig.
`Fig; 2 is a drawing of a typical format of a JPEG compressed file.
`
`HUAWEI EX. 1016 - 13/714
`
`
`
`1 l
`
`Patent Application
`2
`Attorney Docket Number 1094893-1
`
`a block diagram ofa prior art JPEG decompression engine.
`Fig. 3
`_Fig. 4c is a flow chart of a method of forming a scaled quantization
`table according tothe invention. I
`I
`5
`is a‘ drawing of a JPEG compressed file including a
`quantization table scaled according to theinvention.
`A Fig. 6 is a block diagramuofa JPEG decompression engine according
`to theinvention.- -
`I
`A
`machine including JPEG
`Fig 7.is a block diagram of a color
`compression and decompression engines according to the invention.
`
`EMBODIMENT
`DETAILED DESCRIPTION
`f ‘Ovenrvieyz:I of the Quantization Process
`The text and image enhancing technique according to the invention
`is integrated into the "decoding ‘or inverse quantization step that is
`necessaril}? required by the JPEG standard. Theinvention integrates the
`two
`using
`‘different quantization tablesra first quantization table
`(QE) for use
`quantizing the image data during theicompression step and
`a second quantization table (QD)Vfor use ‘during the decode or inverse
`quantization during the decompression process._ The diflerence between
`the two tables, in particular theiratio of the two tables, determines the
`amount ofimage enhancing that is done in the two steps. By integrating
`the image enhancingand inverse quantization steps, the_method does not
`require any additional computations than already required for the
`compression and decompression processes.
`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 Q3, used during the quantization
`step, by the following" expression:
`
`HUAWEI EX. 1016 - 14/714
`
`
`
`Patent Application
`—
`g
`’
`»
`. Attorney Docket Number 10948934
`
`Qfig(S_xQe.l+B
`
`T
`
`‘:
`
`~
`
`-
`
`_(1)
`
`where ‘S is a scaling matrix, which scales each element’ of the first
`quantization’ tablet Q3 to ‘a = corresponding’ element
`in the . second
`quantization table Q3. The scaling matrix is not used "in atrue matrix
`multiplication; rather, the multiplication is an element-by-element
`multiplication. Each element in" the first q_uan.tizatiion;table QE has a
`corresponding element in _the' scaling matrix S that when multiplied
`together produce the ‘corresponding elementin the secondquantization
`table QB.
`A
`'
`-The matrix B is" a so-called brightness matrix because it can affect
`the brightness of_ the image by changingthe DC level of the DCT
`elements. The “elements of the matrix can include aero or non-zero
`values depending on the desired brightness. For purposes ofthe following
`discussion and qderivationthowever, it will be assumed that the B matrix
`contains Zero elements only to simplify the derivation.
`The text and image enhancing technique of the invention uses a
`variance matrix to represent the ‘statisticaliproperties of an image. The
`variance matrix is an M x matrix, where each element in the variance
`matrix is equal to" the variance. of a corresp'_onding 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 (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 describedvabove. In order
`to do this,i the method‘ takes advantage of the relationship between the
`uncompressedirnage and the compressed image. The following derivation
`
`A
`
`a
`
`._..+ I
`
`W.//Wt
`
`HUAWEI EX. 1016 - 15/714
`
`
`
`Patent Application
`,
`Attorney Docket Number 1094893-1
`
`relationship clear.
`will make
`‘Let V*_[k,l] ‘denote the variance of the [k,l] frequency component of
`' a reference image. Ideally, this image contains those critical attributes
`that the technique seeks to preserve, for example, text. This variance
`matrix is of an ideal or reference image in that-itis, not rendered into‘
`color source image data by a scanner but, instead, is rendered into its
`ideal form by software, described further below. Thus, the color source
`image data of thereference 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:
`
`Vytk, 1] =oV*tk,i1’
`
`
`
`(2)
`
`z
`
`,_ However, the decompressed image (Y’) is related to the original quantized
`image (Yq) by the following expression:
`
`“dY’[k, 11=Ystk,11 Qn[k,11
`
`
`
`
`
`‘
`
`(3)
`
`Substituting equation (1) into equation (3) yields the following equation
`below:
`
`Y’[k, 11 = Yrs-:[k,1](S[k,1] Qs[k,1])
`
`T _
`
`(4)
`
`The variance of the decompressedfimage (Vy-) can then be expressed by
`
`HUAWEI EX. 1016 - 16/714
`
`
`
`Patent Application
`»
`_
`Attorney Docket Number 10948934 ‘
`
`the following expression:
`
`vdk, 11 = Var (wk, 11) 2 Vétrf<SLk,'1]Yd§[k, 11Qdk,11>
`
`Reducing this expression iyieldsthe following:
`
`Vy;[k,g1] : S2[k-,1]Vy[k,1]
`
`c
`
`
`
`d
`
`(5)
`
`(6)
`
`represents the variance of the original uncompressed image.
`where
`Substituting equation (6) into equation (2) yields the following
`relationship between the scaling matrix S and the variances of the
`S reference image(V*) and the original image
`S‘
`
`'S[l{, l]2 £V*[k,_l]/ V§[k, 1],
`
`~
`
`V
`
`‘
`
`(7)
`
`Therefore, the scaling ‘matrii: S can be _used to boost the variance
`of the JPEG compressed image V to that of the reference image by
`appropriate formation of the scalingmatrix-. This method is shown in a
`more generalized fashion in FIG.i 4.
`
`l Preferred Embodiment of the Method
`_
`_
`In FIG; 4, a‘ method 6.2 of forming a scaled Quantization table
`according to the invention is shown. T The first step (34 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 typefaces having a serif font, e.g.,
`Times Roman. The selection the reference image is important because
`it is the frequency or energy characteristicsv. of this image that the text
`
`HUAWEI EX. 1016 - 17/714
`
`
`
`1 5
`.
`
`,
`.1
`r
`V
`"
`Patent Application
`Attorney Docket Number 1094893-1
`
`image sharpening method is intended to preserve. Because the method
`is statistical, the result can be improved by averagingover a number of
`typical images.‘ Ezlcainples 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.
`a
`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 belin the appropriate color
`space, e.g.,-
`or RGB,
`to allow the A subsequent step to be
`performed. This process can be achieved by first rendering the image into
`an_Adobe Postscript file and then rendered into a bit-mapped color source
`image data ‘file using l)is:p1ayPostscript., V Alternatively, other I page
`description‘ languages can be used to describe thelimage such as the PCL
`language by Hewlett-Packard
`then rendered into a bit map by an
`appropriate rendering program.
`i
`lC)nc'el_thé ‘reference iinageis generated and rendered into reference
`image data, the average energy. ofthe reference image is determined in
`step 66; ‘In the preferred ,embodimentj,'this step includes computing. the
`variance matrix *9) for the reference image data. A The variance matrix,
`as is known the art, statistically represents thefrequency components
`or energy contained in the image. Unlike a scanned image, the reference
`image does not suffer from any of the inherent limitations of the color
`scanner because it is 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. 1016 - 18/714
`
`
`
`1 6
`
`I
`
`‘ Patent Application
`.
`.
`‘Attorney Docket Number 10948934
`
`Instep 68; alscanned image is scanned or selected from one or more
`V
`stored pre-scanned images. This scanned image is one that suffers from
`the inherent limitation of the scanner. 1 This scanned image can be any
`image, _but in the-preferred. embodiment it is a scanned version of the
`reference» imagegenerated in step 64,
`of the same type of image used
`to form an averaged reference image.
`As in step
`the average energy of the scanned image is then
`determined
`stepr7 The average energy again is represented by a
`variance matrix Y) ofthescanned image.
`I
`A The variance matrix (V*) of thereference image and the variance
`matrix (Vy) of the scanned image are then used to compute the scaling
`_m_at_rix Sin step 72. This stepinvolves solving equation (7) above for
`each element in the scaling matrix S.
`Finally, in step 74 thegscaled version of the quantization table is
`calculated. This step isa simple element-by-element multiplication as
`represented by equation (1) above.
`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 compression
`engine 78, which compresses the image data accordance with the JPEG
`compression standard.
`The compression engine 78 performs the
`quantization step using the Q tables 76. The compression engine 78 also
`"