`
`cnn U.S. PATENT APPLICATION
`
`SERIAL NUMBER
`
`08/411,369
`
`FILING DATE
`
`03/27/95
`
`GROUP ART UNIT
`
`2613
`
`APPLICANT
`
`GIORDANO BERETTA, PALO ALTO, CA; VASUDEV BHASKARAN, MOUNTAIN VIEW, CA;
`KONSTANTINOS KONSTANTINIDES, SAN JOSE, CA,
`
`CONTINUING DATARS #8 RRR KA AKER KEKE
`VERIFIED
`
`**POREIGN/PCT APPLICATIONS * *## eek x HR H
`VERIFIED
`
`Certifying Officer
`
`FOREIGN FILING LICENSE GRANTED 04/26/95
`
`INDEPENDENT
`CLAIMS
`
`ATTORNEY DOCKET NO.
`
`$1,158.00
`
`10940893
`
`ADDRESS
`
`RECORDS MANAGER
`LEGAL DEPARTMENT 20BO
`HEWLETT PACKARD COMPANY
`P O BOX 10301
`PALO ALTO CA 94303-0890
`
`TEXT AND IMAGE SHARPENING OF JPEG COMPRESSED IMAGES IN THE FREQUENCY
`DOMAIN
`
`that annexed hereto is a true copy fromthe records of the United States
`This is to certify
`Patent and Trademark Office of the application which is identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Date
`
`
`
`\
`
`~OLYMPUSEx. 1016 - 1/714
`
`OLYMPUS EX. 1016 - 1/714
`
`
`
`BAR Cone TABEL
`
`
`eT
`
`
`
`
`
`-_U.S. PATENTAPPLICATION
`
`
`FLUNG DATE.
`[ SERIAL NUMBER
`
` GROUP ART UNIT
`
`
`
`
` | cefasieae a “2608 [eee
`
`
`
`
`APPLICANT
`
` _@tORDANOSa‘ALTO,) aii (Houwenrvoen) Ca;
`-vasubRy.1BHASKARAN,t
`
`: KONSTANTINOS RORSPANTITORS;(8
`:
`:
`)cae
`
`
`
`- *sconrmNUiNG DATAWIrnEkaRREEE,
`
`
`cos
`VERIFIED -
`ue
`
`
` - sePoRETON/Pot APPLICATIONS#*+e+hieeeninms
`(VERIFIED|
`
`
`'. FOREIGN PILING LICENSE GRANTED 04/26/95...
`
`
`“s:
`{ATTORNEY DOCKETNO,
`
`“ 10940893.
`
`
`“MARGERJOHNSON|MCCOLLOMSTOLOWLT2"
`
`
`
`--.1030 SW MORRISON. ST |
`
`ADDRESS©.
`.° PORTLAND. OR 97205 t
` “TEXT AND IMAGE. SHARPENING'‘OF JPEG”COMPRESSED IMAGES-IN THE FREQUENCY
`
`- . . : .
`
`‘DOMAIN
`
`
`
`
`This'ig te certify thata‘afinexéd heretois a true copy:From the tecordsofthe United States|
`
`
`
`
`a
`Patent and:Tra lemarkOfficeoftheapplication whichiis identified above,
`:
`
`
`
`
`By authority of the,
`:
`:
`COMMISSIONER oF PATENTSanoTRADEMARKS :
`
` Date + Certifying Ottiver eee
`
`
`
`
`OLYMPUS EX.1016 - 2/714
`
`OLYMPUS EX. 1016 - 2/714
`
`
`
`elon
`earlAAAS
`
`HEWLETT-PACKARD COMPANY
`Legal Department, 2080
`Palo Alto, California 94303-0890
`ATTORNEY DOCKET NO.
`_..1094893-1
`
`
`
`
`ue
`
`
`
`COMMISSIONER OF PATENTS AND:TRADEMARKS
`Washington, D.C. 20231
`Sir:
`Transmitted herewith forfiling under 37 CFR 1.53(b) is a(n):
`.
`
`
`
`.() Design
`(x) Utility
`(x) original patent application,
`(
`) continuing application,
`
`( } continuation-in-part
`() continuation or
`(_) divisional
`of S/N
`filed
`
`INVENTOR(S): Giordano Berettaetal.
`TITLE:
`TEXT AND IMAGE SHARPENING OF JPEG COMPRESSED IMAGES IN THE
`FREQUENCY: DOMAIN
`
`Enclosed are:
`(_) unsigned orpartially signed
`(X) signed...
`(X). The Declaration and Power of Attorney.”
`-(
`)
`informal drawings
`(one set)
`(X)
`_7
`sheets of (X) formal drawings.
`( ) Information Disclosure Statementand Form PTO-1449
`(
`) Associate Powerof Attorney
`(_) Priority document(s)
`( )._(Cthen_
`(fee $
`
`)
`
`
`
`
`coe|a-sf1 [x sw} 7
`
`oeTEOoLT $ 240|so
`
`BASIC FEE: Design ( $300.00 ); Utility ( $730.00)
`$ 730
`
`
`
`CLAIMS AS.FILED BY OTHER THAN A SMALL ENTITY
`
`(1)
`FOR
`
`2)
`NUMBER FILED
`
`:
`
`@)
`NUMBER EXTRA
`
`(4).
`RATE
`
`(6)
`TOTALS
`
`TOTAL CLAIMS.
`
`|
`
`INDEPENDENT
`
`ANY MULTIPLE,
`
`.
`
`TOTAL CHARGES TO DEPOSIT ACCOUNT
`
`$
`
`1,158
`
`
`
`
`
`
`
`
`
`
`
`
`Charge $ 1,158_to Deposit. Account 08-2025... At any timeduring the pendency ofthis application,
`
`please charge any. fees required or credit any over paymentto Deposit Account 08-2025 pursuant to 37 CFR
`1.25. Additionally please charge any fees to Deposit Account 08-2025 under'37.CFR.1.19, 1.20 and 1.21. A
`duplicate copy-of this sheet is‘enclosed.
`oe
`"
`i" label
`_no.
`630!
`.
`Express-Mail"
`label no. TB396300465
`Date of Deposit. March 27, 1995
`
`»
`Respectfully submitted,
`Giordano Beretta etal.
`
`I-hereby certify that this Is being deposited with-the
`United: States Postal’
`‘Service "Express -Mail
`-Post
`Wty
`’
`By
`the. date indicated: above and is. addressed tothe
`
`Commissioner-of. and=Trademarks,Patents’
`
`Washingign,D.C. 20231,
`C. Douglass Thomas
`
`Office:to Addressee" service under 37 CFR.1.10 on
`By <nQ beeicr-
`Typed Name: Linda A. limura
`
`C Ap Mi.
`Attorney/AgentforApplicant(s)
`Reg. No.
`32,947
`Date: March 27, 1995
`- Attach as First Page to Transmitted Papers- Telephone No.: (415) 857-8129
`
`Rev 10/94 (Form 3.04)
`
`.
`
`OLYMPUS EX.1016 - 3/714
`
`OLYMPUS EX. 1016 - 3/714
`
`
`
`Attorney Docket Number 1094893-1
`
`pins 7
`
`
`1
`
`Patent Application
`
`TEXTAND IMAGE SHARPENING OF JPEG com ESSED_
`
`,
`{ES IN THE FREQUENCY DOMAIN
`
`ps q
`C 7
`RELATED APPLICATION DATA.
`ced
`woe
`This application incorporates subject matter disclosed in commonly-
`assigned application entitled . METHOD FOR SELECTING JPEG
`QUANTIZATION TABLES FOR LOW BANDWIDTHAPPLICATIONS,
`10
`Ser. No.ay236si7filed on even date herewith.
`
`|
`
`- BACKGROUND OF THE INVENTION
`
`15
`
`20
`
`25
`
`30.
`
`invention relates to data compression using the JPEG
`This
`compression standardfor continuous-tone still images, both grayscale
`and color.
`.
`A committee: known as "JPEG,"which stands. for "Joint
`PhotographicExperts Group,”hasestablished astandardforcompressing
` continuous-tonestill iimages, both grayscale 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 uncompressediimage to the compressed. image, the
`JPEG: standard adopted a lossy compression technique. The lossy
`compression techniquewas required giventhe inordinate amountofdata
`needed to representa coloriimage,on the order of 10 megabytes for a 200
`dots per inch (DPI). 8.5" 11" image. By. carefully implementing the
`JPEG standard, however, the loss iin the image: can.be. confined to
`imperceptible areas ofthe image, which produces a perceptually lossless
`. uncompressed. image. The achievable compression rates using this
`technique are in the range of 10:1 to 50:1.
`Figure 1 shows a block diagramofa typical implementation ofthe
`
`
`
`OLYMPUS EX.1016 - 4/714
`
`OLYMPUS EX. 1016 - 4/714
`
`
`
`
`
`
`
`2
`
`Patent Application
`:
`Attorney Docket Number 1094893-1
`JPEG.compressionstandard. The block diagram will be referred to asa
`compressionengine. The compressionengine 10 operates on sourceimage
`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 byhow theiimage was captured. Each individual datum of ©
`the source image data represents an image pixel. The pixel further has
`a depth whichis determined by the numberofbitsused to represent the
`imagepixel.
`|
`|
`|
`‘Thesourceimagedata.
`is typically formatted as a raster stream
`of data. The compression technique, however, requires the data to be
`represented in blocks. These blocksrepresent a two-dimensional portion
`of thesource image data. The JPEG standard uses 8x8 blocks ofdata.
`Therefore, a raster-toto-block translation unit 12 translates the raster
`source image data into 8x8 blocks of source image data. The source
`image data iis 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.
`‘The discreté cosine transformer 16 convertsthe source image data
`_ into transformed image data using the discrete cosine transform (DCT).
`The DCT,as is knownin the art ofimage processing, decomposesthe 8x8
`block of source image data into 64 DCT elements or coefficients, each of
`which. correspondstoa 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 thought:to represent unique images, wherein any source image
`can be decomposed. into a weighted sumofthese unique images. The
`discrete cosine transformer uses the forward discrete cosine (FDCT)
`function as shown below, hence the name.
`
`10°:
`
`15
`
`20
`
`25
`
`
`
`OLYMPUS EX.1016 - 5/714
`
`OLYMPUS EX. 1016 - 5/714
`
`
`
`
`
`
`
`3
`
`,
`
`
`
`Peo
`
`
`
`where: C(k), ca) = 1/-/itorks|
`
`»> 6 16- xsi,,y+iinY[k,1] =.jo)cosy)©cos
`== 0; and
`
`Patent Application
`|
`Attorney Docket Number 1094893-1
`
`
`
`~-C(k), C(1) = 1 otherwise
`
`The output ofthe transformer 16 is an 8x8 block of DCT elements
`or coefficients, correspondingto the DCT basis vectors. This block of
`transformediimage datais then forwarded to a quantizer 20 over a bus
`18. The quantizer 20 quantizes the 64 DCT elements using a 64-element
`quantization table 24, which must be. specified as. an input to the
`compression engine 10. Eachelement of the quantization table is an
`integer value from one to 255, which specifies. the stepsize of the
`quantizer for the corresponding DCT coefficient. The purpose. of
`quantization. is to achieve the: maximum amount of compression by
`representing DCT coefficients with no greaterprecisionthanis necessary
`to achieve’ the desired image. quality. Quantization is a many-to-one
`mapping and, therefore, is fundamentally lossy. As mentioned above,
`quantization tables have been. designed which limit the lossiness to
`imperceptible aspects of the iimage so that the reproduced imageis not
`perceptually different from the source. image.
`Thequantizer20performsasimpledivisionoperationbetweeneach
`DCTcoefficient and the corresponding quantization table element. The
`lossiness occurs because the quantizer 20 disregards any fractional
`remainder. Thus,the quantization function can be represented as shown
`_in Equation 2 below.
`
`10
`
`15
`
`20
`
`25
`
`| Yolk] = IntegerRound(#11)
`
`
`
`OLYMPUS EX.1016 - 6/714
`
`OLYMPUS EX. 1016 - 6/714
`
`
`
`
`
`
`
`4
`
`Patent Application
`:
`Attorney Docket Number 1094898-1
`where Y(k,]) represents the (k,1)-th DCT element and Q(k,D 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 thefollowing expression:
`
`Yk, 1) = Yelk; 1)-Qefk, 11.
`
`the fractional. part. discarded during the
`As shouldbe apparent,
`quantization step is not restored. Thus,this informationis lost forever.
`Becauseofthe potential impact on the image quality of the quantization
`step, considerable effort has goneinto designing the quantization tables.
`These efforts are described further below following a discussion of the
`final step in the JPEG compression technique.
`The final step ofthe JPEG standardis an entropy encoding, which
`is performed by an entropyencoder 28. The entropy encoder 28 is coupled
`to the quantizer 20 via a bus 22 for receiving the quantizediimage data
`therefrom. The entropy encoderachieves additional lossless compression
`by encoding the quantized DCTcoefficients more compactly based on
`their statistical characteristics. TheJPEG standard specifies two entropy
`coding methods:.
`“Huffman coding and arithmetic coding.
`The
`compression engine ofFig. 1 assumes Huffmancodingis used. Huffman
`encoding, as is knownin the art, uses one or more sets of Huffman code
`tables 30. These tables may be predefined or computed specifically for a
`givenimage. Huffmanencoding is a well known encoding technique that
`produces high levels oflossless compression. Accordingly, the operation
`of the entropy encoder 28is not further described. |
`Referring now. toFig: 2,-a typical JPEG comipressedfile is shown
`
`10
`
`16
`
`20
`
`25
`
`ie
`
`OLYMPUS EX.1016 - 7/714
`
`OLYMPUS EX. 1016 - 7/714
`
`
`
`
`
`
`
`. 5
`
`Patent Application
`AttorneyDocketNumber 1094893-1
`generally at 34. The compressedfile includes a JPEG header 36, the
`quantization (Q) tables 38 and the Huffman (H) tables 40 used in the
`compression process, and the compressediimage data 42 itself. From this
`compressedfile34aperceptuallyindistinguishableversionofthe original
`source image can be extracted when an appropriate Q-table iis 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 operatesiin reverse ofthe compression
`engine 10. The decompression engine receives the compressed iimage data
`at a header extraction unit 44, which extracts the H tables, Q tables, and
`compressed image data according to the information containediin the
`header. The H tables are then storediin H tables:-46 while the Q tables
`are stored in Q tables 48.
`.The compressediimage data is then sent to an
`entropy decoder 50 over a bus 52. The Entropy Decoder decodes the
`Huffman encoded compressediimage data using the H tables 46. The
`output ofthe entropy decoder 50 are the quantized DCT elements:
`The quantized DCT elements are then transmitted to an inverse
`quantizer 54 over a bus. 56.. Theinverse quantizer 54multiplies the
`quantized DCT elements by the corresponding quantization table
`elements found in Q 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 ofthe compressediimage data.
`The inverse quantized DCT elementsare then passed to an inverse
`discrete cosine transformer (IDCT) 57 via bus 59, which transforms the
`data backinto the time domain using the inverse discrete cosine
`transform (IDCT). The inverse transformed data isthen transferredto
`block-to-raster translator 58 over a bus 60. where the blocks of DCT
`elements are translated into a raster string ofdecompressed source image
`
`10
`
`15
`
`20
`
`25
`
`OLYMPUS EX.1016 - 8/714
`
`OLYMPUS EX. 1016 - 8/714
`
`
`
`
`
`
`
`6
`~
`Patent Application
`Attorney Docket Number 1094893-1
`data. From the ‘decompressed source image data, a facsimile of the
`original source image can be.reconstructed The reconstructed source
`image, however,iis not an exact replication ofthe original source image.
`As described above,the quantizationstep produces some lossinessiin the
`process ofcompressingthe data. By carefully designingthe quantization
`tables, however, the prior art methods have constrained the loss to
`visually imperceptible portions oftheiimage. These methods, and their
`shortcomings, are described below.
`The JPEG standard includes two examplesof quantization tables,
`one for luminance channels and one ‘for chrominance channels, See
`International OrganizationforStandardization: "Information technology
`-» digital compression encodingof continuous- tones still images- part 1:
`Requirements and. Guidelines, " ISOAEC 1810918-1, October 20, 1992.
`These:tables are known as the K.land K.2tables, respectively. .These
`tables havebeen designedbasedontheperceptuallylossless compression
`of color images representediinthe YUV color space.
`‘These tables result in visuallypleasingiimages, but yield a rather
`low compression ratiofor 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 desighed to be perceptually lossless, however, a large Q-factor
`will introduce artifacts in the reconstructediimage, such as blockinessiin
`areasofconstant color or ringing in text-scale characters. Someofthese
`artifacts can be effectively cancelled by post-processing of
`the
`reconstructed image by:passing it through a tone reproduction curve
`correction stage, orby segmenting the image and processing the text
`separately. However, such methods easily introduce new artifacts.
`
`10
`
`45
`
`20
`
`25
`
`OLYMPUS EX.1016 - 9/714
`
`OLYMPUS EX. 1016 - 9/714
`
`
`
`Therefore, these methodsare notideal.
`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 categorizedas either perceptual, which
`means based on the humanvisual system (HVS) or based on information
`theorycriteria. Thesemethods are also designated ag 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 forLow Bandwidth Applications,"
`commonly assigned to the present assignee, incorporated herein by
`reference.
`.
`.
`Quantization iis not the-only causeofimage degradation. The color
`source image data itself might be compromised. . For scanned colored
`images, the visualquality of the iimage canbe degraded because ofthe
`inherent limitations of color scanners. These limitations are mainly of
`15,
`
`two.kinds: limited ° modulation: transfer. function (MTF) and
`
`misregistration.
`The. modulation transfer function refers to the
`mathematical representationortransferfunctionofthe scanningprocess.
`There are inherent limitations in representing the seanningprocess by
`the MTF and these limitationsare the main causeofpixel aliasing,which
`producesfuzzy black text alyphs ofgrayish appearance. Misregistration,
`on the other hand; refers to the relative misalignmentof the scanner
`sensorsfor the various frequency. bands. For example, the Hewlett
`Packard Scan Jet IIc™ has a color misregistration tolerance of+/- 0.076
`mm.
`for. red and. blue with respect.
`to. green:
`| This amount of
`misregistrationis significant considering thesize ofan imagepixel(e.g.,
`0.08 mm at 300 dots per inch (dpi).
`These limitations significantlydegrade text in colorimages because
`sharp edges arevery importantfor reading efficiency. The visual quality
`
`10
`
`20
`
`25
`
`
`
`
`
`7
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`
`
`OLYMPUS EX. 1016 - 10/714
`
`OLYMPUS EX. 1016 - 10/714
`
`
`
`
`
`
`
`g
`’
`PatentApplication
`:
`Attorney Docket Number 1094893-1
`of text can be improved, however,‘using prior art edge. enhancement
`techniques. Edge enhancementcan be performediineither the spatial
`or frequency domain. In the spatial domain Ge.,RGB), edge crispening
`can be performed by discrete convolution ofthescannediimage with an
`edge enhancement kernel, This approachiis equivalent to filtering the
`image with a high-pass filter. However,this technique is computationally
`intensive. An Mx N convolution kernel, for example, requires MN
`. multiplications and additions: per pixel.
`For edge sharpeningin the frequency domain, the full imageis first
`. transformedintothefrequencydomainusingtheFastFourierTransform
`(FFT) or
`theDiscrete Fourier Transform (DFD,
`low.
`frequency
`components are dropped, and then the imageis transformed back into the
`time domain. This frequencydomainmethod, as with the spatial domain
`method,
`is also. computationally intensive.
`: Moreover, it uses a
`transformation. differentthan that required bythe JPEG standard.
`Accordingly, the need remains for a. computationally efficient
`methodfor improvingthe visual quality ofimages, and in particular text,
`in scanned images.
`
`_ SUMMARYOFTHE INVENTION
`The invention is a method of compressing and decompressing
`imageswhichcomprises usingonequantizationtable (Qe)forcompressing
`the image and a second quantization table (Qp) for décompressing the
`image.
`In general, compression and decompression are performed in
`conformance with the JPEGstandard. The second quantization table Qp
`is relatedto the first quantization table accordingto.the following general
`expression:
`
`10
`
`15
`
`20
`
`25
`
`Q=SxQe+B,
`
`OLYMPUS EX. 1016 - 11/714
`
`OLYMPUS EX. 1016 - 11/714
`
`
`
`
`
`
`
`9
`
`Patent Application
`.
`° Attorney Docket Number 1094893-1
`
`where Sisa scaling matrix having each element S[k] formed according
`to:the following expression:
`
`S[k,= V*0k,1/Vv0k,1I
`
`10
`
`15
`
`20
`
`25
`
`where V* is a variance matrix of a reference image and Vyis a variance
`matiix 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, thequantization table Qp is transmitted with the encoded
`quantizediimagedata,andiis usediindecompression to recover the image.
`The.referenceiimage isa preselected continuous-toneiimage,either
`grayscale or color depending on.theiimages to be processed. The reference
`imageis renderedinto a target image file. The target imagefile is not
`generated by ascanner,80the data therein is not compromisedby. anyof
`the inherent limitations of a color scanner. Thus, the variance of the
`target image data, which is a statistical representation of the energy or
`frequency contentofthe image, retains the high-frequency components.
`The reference image can be any continuous-tone image, but.in the
`preferred embodiment the reference iimage includes text witha seriffont
`becausethe seriffonthas goodvisual qualitywhichthemethod preserves.
`The scannediimage, although it can be any image, in the preferred
`embodiment is aprinted version of the reference image. Thus, the
`variance of the scanned image represents the energy or frequency
`composition ofthe:reference image but which is compromisedby the
`inherentlimitationsofthe scanner. The scalingmatrix, therefore, boosts
`the frequency components thatéaré compromisedby the scanningprocess.
`
`
`
`
`
`OLYMPUS EX. 1016 - 12/714
`
`OLYMPUS EX. 1016 - 12/714
`
`
`
`
`
`
`
`:
`
`10
`
`Patent Application
`,
`Attorney Docket Number 1094893-1
`A preferred embodiment ofthe invention is described herein in the
`context ofa color facsimile (fax) machine. The colorfax machine includes
`a scannerfor renderinga color imageinto color source image data that
`represents the color image, a compression engine that compresses the
`color source image data to compressed image data, a means for
`encapsulatingthe compressed image data, anda 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 transformied using the discrete cosine transform
`(DCT).. The secotid quantization table is encapsulated with the encoded
`quantized image data for use in decompressing the image. The second
`quantization tableis relatedto 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
`qualitythanprior.systems.
`,
`The second quantization table canbeprecomputed and storedinthe
`compression engine, in which casethere areho additional computational
`requirements for the compression engine to implement the image
`enhancing methodofthe invention. This capability results in a lower cost
`color facsimile product than is possible using the prior: art image
`enhancement techniques.
`The foregoing and other objects, features and advantages of the
`invention will become more readily apparent fromthe following detailed
`description of a preferred embodiment of the invention which proceeds
`with referenceto the accompanying drawings.
`
`~
`
`10
`
`15
`
`20
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Fig. 1 is a blockdiagram of a prior art JPEG. compression engine.
`Fig. 2 is a drawingof a typical format of a JPEG compressedfile.
`
`OLYMPUS EX. 1016 - 13/714
`
`OLYMPUS EX. 1016 - 13/714
`
`
`
`
`
`
`
`114
`
`Patent Application
`,
`Attorney Docket Numbér 1094893-1
`Fig. 3 isa block diagram ofa prior art JPEG decompression engine.
`Fig. 4isa flow chart ofa method offorming a scaled quantization
`table according tothe invention.
`Fig. 5
`isa“drawing of a JPEG conipréased file including a
`quantization table scaled according to the invention.
`Fig. 6 isa block diagram ofa JPEG decompression engine according
`to the invention.
`Fig 7.is a block diagram ofa color fax machine including JPEG
`compression and decompression engines according to the invention.
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
`- Overview ofthe Quantization Process
`The text andiimage enhancingtechnique accordingto the invention
`is integrated into the decoding or inverse quantization step that is
`necessarilyrequiredbythe JPEG standard. The invention integrates the
`two by using twodifferent quantization tables: a first quantization table —
`(Q,) for use in quantizing theiimage data during the compression step and
`a second quantization table (Qn)for use during the decode or inverse
`. quantization during the decompression process. The difference between
`the two tables, in particular the ratio of the twotables, determines the
`amount of iimage enhancing thatiis done in the two steps. By integrating
`the image enhancingand inverse quantization steps, themethod 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 is necessary. Let Qp be the second quantization
`‘table used during the decoding orinverse quantization step. Then let Qp
`be related to thefirst quantization table Qi, used duringthe quantization
`step, by the following expression:
`
`10
`
`15
`
`20
`
`25
`
`>
`
`
`
`OLYMPUS EX. 1016 - 14/714
`
`OLYMPUS EX. 1016 - 14/714
`
`
`
`
`
`
`
`* 1)
`‘
`
`“
`
`Patent Application
`nr
`“Attorney Docket. Number 1094893-1
`
`Q=SxQ+Bo
`
`—
`
`where S is a scaling matrix, which scales each elementof the first
`quantization table Qz to a corresponding element
`in the . second
`quantization table Qp. The scaling matrix Sis not used in.a true matrix
`multiplication; rather, the multiplication is’ an element-by-element
`multiplication. Each element inthe first quantization table Qs has a
`corresponding element in. the. scaling matrix S that. when multiplied
`together produce the corresponding element in the secondquantization
`table Qp:
`
`The matrix Bisa so-called brightness matrix becauseit 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 dependingonthe desiredbrightness. For}purposes ofthefollowing
`discussion and derivation, however, it will be assumedthat the B matrix
`containszero. elements onlyto simplify the derivation.
`The text and image enhancing technique of the invention uses a
`variance matrix to represent the statistical properties of an image. The
`variancematrix isanMxM matrix, where each elementin the variance
`matrix is equal tothe varianceofa corresponding DCTcoefficient over
`the entire image. The variance is computedin the traditional manner,as
`is known in theart.
`|
`The edge enhancement technique in essence tries to match the
`variance matrix ofa decompressed image (Vy [k,]]) with a variance matrix
`of a reference image (V*[k,l]).
`‘The technique tries to match the two by
`scaling the quantization table in the manner. described above. In order
`to do this, the methodtakes advantage of the relationship between the
`uncompressedimage and the compressed image. Thefollowing derivation
`
`~
`
`10
`
`15
`
`20
`
`25
`
`as
`
`OLYMPUS EX. 1016 - 15/714
`
`OLYMPUS EX. 1016 - 15/714
`
`
`
`
`
`
`
`13
`
`thewDeckst Nemnber1084800-1
`
`will make this relationshipclear.
`Let V*Lk,1] denote thevarianceofthe [k,1] frequency component of
`a reference.iimage. ‘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 iimage in that it.is not rendered into:
`color source image data by. ascanner but, instead, iis 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 inherentlimitations ofthe scanner. Therefore, the
`varianceofthereferenceiimageretainsthehigh-frequencycharacteristics
`of the original referenceiimage:
`The method produces:a resulting decompressed image that has
`approximately ‘the same variance as the variance of the reference by
`modifying the quantization table. Thus, the method produces the
`following relationship:
`
`Veik, I]= V*Lk, 1
`
`:
`
`:
`
`(2)
`
`However, the decompréssed image(Y’)is relatedto theoriginal quantized
`image(Yq) by the following expression:
`
`Yk, 1]= Youlk, 1] Qolk, 1] ae
`
`|
`
`8)
`
`Substituting equation (1) into equation (3) yields the following equation
`below:
`
`Yk, 1] = Yoelk, 1 (Sts, 1 Qellk, ID
`
`,
`
`(4)
`
`The variance of the decompréssedimage (Vy) can then be expressed by
`
`10
`
`15
`
`20
`
`25
`
`ears
`
`om
`
`OLYMPUS EX. 1016 - 16/714
`
`OLYMPUS EX. 1016 - 16/714
`
`
`
`
`
`
`
`14 :
`
`PatentApplication
`Attorney Docket Number 1094898-1
`
`the following expression:
`wb =VarateI)=Var(Stk,1Yolk, aQk, )
`Reducingthis expression yieldsthe following:
`3)
`Volk, 11 = Sf, 1deci os
`where Vy represents the vatianes ofthe originaluncompressed image.
`Substituting: equation (6) into equation (2) yields the following
`relationship between the scaling matrix'S and the variances of the
`reference image (V*) and the original image (Vy):
`
`‘Sk, IP = V*Lk, 11/7 Vek, I
`
`7)
`
`Therefore, the scaling matrix S can be used toboost the variance
`of the JPEG compressed image to that of the reference image by
`appropriate formation ofthe scaling,matrix. This methodiis shown in.a
`more generalizedfashion in FIG: 4.
`Preferred Embodimentofthe Method
`In. FIG..4, a method 62 of forming a scaled quantization table
`according to the invention is, shown. Thefirst step 64 is to generate a
`reference image. This referenceiimage, in the preferred embodiment,
`embodies certainvalued featuresor elementsthat the method seeksto
`preserve. In the preferred embodiment, these critical elements include
`highly readable text such as those typefaces having a. serif font, e.g.,
`Times Roman. The selection ofthe referenceiimage is important because
`it.is the frequency or energy characteristics. of this image that. the text
`aPe
`
`10
`
`15
`
`20
`
`25
`
`a
`
`a
`
`
`
`OLYMPUS EX. 1016 - 17/714
`
`OLYMPUS EX. 1016 - 17/714
`
`
`
`
`
`
`
`15
`mo
`Patent Application
`:
`:
`Attorney Docket Number 1094893-1
`imagesharpening méthodiis intended to preserve. Because the method
`ig statistical, the result can be improved by averaging over a number of
`typical iimages. Examples ofsuchtypical images arethose usingdifferent
`fonts (e.g.,- Palatino and Devanagari), handwriting, short-hand,
`line
`drawings, schematics, bar codes, etc. These different images can further
`be categorized iina number’ofclasses.
`This generating step 64 is performed on a computer, typicallyusing
`a wordprocessor or desktop publishing application such as Adobe
`Illustrator or Microsoft Word: The image is entered into the computer
`and then rendered by the application into reference image data by the
`application. The reference image data will bein the appropriate color
`space, e.g.; CIELAB or RGB,
`to allow. the subsequent step to be
`performed. Thisprocess canbe achievedbyfirstrenderingthe image into
`anAdobe Postscriptfile and then rendered into abit-mapped color source
`image data file using DisplayPostscript. Alternatively, other page
`description languages can bé used to describe theiimage such as the PCL
`language by Hewlett Packard: and then rendered into a bit map by an
`appropriate rendering program.
`!
`Once thereferenceiimageis generated and rendered into reference
`image data, the average energyofthe referenceiimage is determined in
`step 66. In the preferred embodiment,this step includes computing the
`variance matrix (V*) for the referenceiimage data. The variance matrix,
`asis knowniin theart, statistically represents thefrequency components
`or energy containediin the image. Unlike a scanned image, the reference
`image does not suffer from any of the inherentlimitations of the color
`scanner because itiis not compromised by. the misregistration and MTF
`limitations ofthe scanner: Accordingly,the variance for the reference
`image retains the high-frequency energy that is critical to the visual
`quality of the reference image.
`
`10,
`
`15
`
`20
`
`25
`
`Oo
`
`OLYMPUS EX. 1016 - 18/714
`
`OLYMPUS EX. 1016 - 18/714
`
`
`
`
`
`
`
`i6
`
`:
`
`Patent Application
`Attorney Docket Number 1094893-1
`
`Instep 68; ascanned image is scanned or selected from one or more
`“
`stored pre-scannediimages: This scanned image is one that suffers from
`the inherent limitation of the scanner.. This scannediimage can be any
`image, but in the preferred. embodiment it'is.a scanned version of the
`referenceiimagegenerated. in step 64, orofthe same type ofimage used
`to forman averaged reference image.
`As in step 66, theaverage energy of the scannedimage is then
`determined in step 70. The average energy again is represented by a
`variance matrix wvy) ofthescanned image.
`The variance matrix (V*) of the reference image and the variance
`matrix (Vy) of the scannediimage are then used to compute the scaling
`matrix S in step 72. This stepinvolves solving equation (7) above for
`each elementiin the scaling matrix S.
`|
`Finally,iin step 74 thescaled version of the quantization table is
`calculated. This step isasimple element-by-element multiplication as
`represented by equation (1) above.
`The use ofthe scale tables is seen clearly w