(12) United States Patent
`de Queiroz et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US006334001B2
`US 6,334,001 B2
`Dec. 25, 2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`ITERATIVE SMOOTHING TECHNIQUE FOR
`PRE-PROCESSING MIXED RASTER
`CONTENT PlANES TO IMPROVE THE
`QUALITY OF A DECOMPRESSED IMAGE
`AND INCREASE DOCUMENT
`COMPRESSION RATIOS
`
`(75)
`
`Inventors: Ricardo L. de Queiroz, Pittsford;
`Reiner Eschbach, Webster; William A.
`Fuss; Robert R. Buckley, both of
`Rochester, all of NY (US)
`
`(73)
`
`Assignee: Xerox Corporation, Stamford, CT
`(US)
`
`( *)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/733,860
`
`(22) Filed:
`
`Dec. 7, 2000
`
`Related U.S. Application Data
`
`(62) Division of application No. 09/206,488, filed on Dec. 7,
`1998.
`
`Int. Cl? ....................................................... G06K 9/36
`(51)
`(52) U.S. Cl. ........................... 382/233; 382/250; 382/251
`(58) Field of Search ..................................... 382/199, 166,
`382/233, 243, 239, 250, 251, 232; 358/462,
`456; 375/240.08
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,359,676 * 10/1994 Fan ....................................... 382/233
`5,778,092 * 7/1998 Macleod eta!. ..................... 382/176
`5,864,638 * 1!1999 Ishizawa et a!. ..................... 382/270
`6,006,226 * 12/1999 Cullen et a!. ........................ 382/237
`
`* cited by examiner
`
`Primary Examiner-Jon Chang
`Assistant Examiner-Jingge Wu
`(74) Attorney, Agent, or Firm-Michelle W. Waites; Mark
`Z. Dudley
`
`(57)
`
`ABSTRACT
`
`A method and apparatus for compressing a mixed raster
`content image that represents a color or gray scale a docu(cid:173)
`ment is disclosed. The pixel map is decomposed into a
`three-plane representation-a reduced-resolution "upper"
`plane, a reduced-resolution "lower" plane, and a high(cid:173)
`resolution binary selector plane. An iterative smoothing
`technique is then used to pre-process the upper and lower
`planes using the information contained in the selector plane,
`thereby reducing the amount of data that will be subjected to
`further processing.
`
`12 Claims, 9 Drawing Sheets
`
`802
`
`804
`
`REPLACE N PIXELS
`WITH AVERAGE OF Y PIXELS
`
`PERFORM DCT ON
`REPLACEMENT BLOCK
`AND QUANTIZE RESULT
`
`I
`I
`r-------- -''------ ____ 806
`I
`I
`I
`1 REMOVE SOME HIGH FREQUENCY i .-
`
`NO
`
`812
`
`STOP?
`
`YES
`
`COEFFICIENTS
`
`1
`1
`I
`I
`I_--------,---------~
`I
`I
`
`INVERSE QUANTIZE AND INVERSE
`TRANSFORM REMAINING
`COEFFICIENTS TO OBTAIN
`PSEUDO-BLOCK
`
`REPLACE N PIXELS IN ORIGINAL
`BLOCK WITH VALUES IN SAME
`LOCATIONS IN PSEUDO-BLOCK
`
`808
`
`810
`
`Vedanti Systems Limited - Ex. 2019
`Page 1
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 1 of 9
`
`US 6,334,001 B2
`
`______ ___,~ 12
`
`.A: m//l
`Vl
`--·!~
`:
`:
`!
`!
`! }.-14
`!/~ [7
`FIG. 1
`
`;
`~
`~
`
`;
`}-16
`
`:
`
`I
`
`I
`
`I
`
`I
`
`1
`
`GENERATE
`LOWER
`PLANE
`
`COMPRESS
`LOWER
`PLANE
`
`OBTAIN ORIGINAL
`PIXEL MAP BLOCKS
`
`GENERATE
`SELECTOR
`PLANE
`
`GENERATE
`UPPER
`PLANE
`
`108
`
`104
`
`106
`
`COMPRESS
`UPPER
`PLANE
`
`112
`
`COMPRESS
`SELECTOR
`
`COMBINE
`PLANES
`
`FIG. 2
`
`Vedanti Systems Limited - Ex. 2019
`Page 2
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 2 of 9
`
`US 6,334,001 B2
`
`0 0 1 1 1 1 0 ~76
`0 1 1 1 1 0 0
`1 1 1 1 0 0 0 0
`1 1 1 0 0 0 0 0
`1 1 0 0 0 0 0 0
`1 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`
`FIG. 3
`
`y N N N N y ~ N N
`
`y
`y N N N N y
`y
`N N N N y
`y
`N N N y
`y
`y
`N N y
`y
`y
`y
`y
`y
`y
`N y
`y
`y
`y
`y
`y
`y
`y
`y
`y
`y
`y
`y
`
`y
`y
`y
`y
`y
`y
`y
`
`y
`y
`y
`y
`y
`y
`y
`
`302
`
`304
`
`y N ~
`
`y
`y
`y
`y
`y
`y
`y N N N
`N
`y N N N N
`y
`y
`y
`y N N N N N
`y
`y
`y
`y N N N N N N
`y N N N N N N N
`N N N N N N N N
`N N N N N N N N
`
`FIG. 4
`
`Vedanti Systems Limited - Ex. 2019
`Page 3
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 3 of 9
`
`US 6,334,001 B2
`
`MARK AND
`COUNT NUMBER
`OF "N" PELS IN
`INPUT BLOCK
`
`402
`
`4M
`
`NUMBER OF
`
`YES
`
`NO
`
`408
`
`NO
`
`4~
`,------__,___-----,
`COMPUTE
`BLOCKAVG.
`AAND OUTPUT
`BLOCK
`
`410
`
`REPLACE WHOLE
`BLOCK BY A BLOCK
`WITH A CONSTANT
`VALUE "A"
`
`412
`
`REPLACE "N" PELS
`WITH VALUES THAT
`ENHANCE
`COMPRESSION
`
`FIG. 5
`
`Vedanti Systems Limited - Ex. 2019
`Page 4
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 4 of 9
`
`US 6,334,001 B2
`
`MARK AND
`COUNT NUMBER
`OF "N" PELS IN
`INPUT BLOCK
`
`402
`
`404
`
`YES
`
`NUMBER OF
`
`406
`
`COMPUTE
`BLOCKAVG.
`AAND OUTPUT
`BLOCK
`
`408
`
`NUMBER OF
`
`YES
`
`REPLACE WHOLE
`BLOCK BY A BLOCK
`WITH A
`CONSTANT VALUE 11A 11
`
`414
`
`410
`
`416
`
`VAR < T
`
`NO
`
`REPLACE WHOLE
`YES
`r----+1 BLOCK BY A UNIFORM 1---...,...
`BLOCK
`
`412
`
`REPLACE "N" PELS
`WITH VALUES THAT
`ENHANCE
`DECOMPRESSION
`
`FIG. 6
`
`Vedanti Systems Limited - Ex. 2019
`Page 5
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 5 of 9
`
`US 6,334,001 B2
`
`402
`
`MARK AND
`COUNT NUMBER
`OF 11N" PELS IN
`INPUT BLOCK
`
`404
`
`606
`
`620
`
`NUMBER OF
`
`OUTPUT
`DATA
`
`610
`
`NUMBER OF
`
`OUTPUT BITSTRING
`RELATIVE TO 0 DC
`1-----.! DIFFERENCE AND EOB 1-------+t
`(01 0110 FOR DEFAULT
`LUMINANCE TABLES)
`
`VAR < T
`
`NO
`
`608
`
`COMPUTE
`AVERAGE OF
`Y PIXELS
`
`616
`SIMPLIFIED
`JPEG
`CODING
`IDC ONLY
`
`412
`
`612
`
`REPLACE "N" PELS
`WITH VALUE THAT
`ENHANCE
`COMPRESSION
`
`ENCODE BLOCK
`USING JPEG*
`
`FIG. 7
`
`Vedanti Systems Limited - Ex. 2019
`Page 6
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 6 of 9
`
`US 6,334,001 B2
`
`706
`
`REPLACE N LOCATION
`PELS THAT HAVE
`VERTICAL OR HORIZONTAL
`Y NEIGHBOR WITH AVERAGE
`OF Y NEIGHBORS
`
`MARK REPLACED N
`PELS WITH Y'S
`
`708
`
`702
`
`ALL
`LOCATIONS IN
`IMAGE BLOCK
`MAPY'S?
`
`NO
`:>-----......
`
`YES
`
`406
`
`OUTPUT
`BLOCK
`
`FIG. 8
`
`Vedanti Systems Limited - Ex. 2019
`Page 7
`
`

`
`U.S. Patent
`
`Dec. 25, 2001
`
`Sheet 7 of 9
`
`US 6,334,001 B2
`
`REPLACE N PIXELS
`WITH AVERAGE OF Y PIXELS
`
`804
`_)
`
`PERFORM DCT ON
`REPLACEMENT BLOCK
`AND QUANTIZE RESULT
`
`NO
`
`812
`
`STOP?
`
`YES
`
`406
`~OUTPUT
`BLOCK
`
`I
`I
`I
`r - - - - - - - - -"'- - - - - - - - - -~ 896
`I
`~~
`I REMOVE SOME HIGH FREQUENCY
`1
`COEFFICIENTS
`I
`1
`I
`I
`~---------,---------~
`I
`~
`INVERSE QUANTIZE AND INVERSE
`TRANSFORM REMAINING
`COEFFICIENTS TO OBTAIN
`PSEUDO-BLOCK
`
`808 LJ
`
`REPLACE N PIXELS IN ORIGINAL
`BLOCK WITH VALUES IN SAME
`LOCATIONS IN PSEUDO-BLOCK
`
`870
`
`lJ
`
`FIG. 9
`
`Vedanti Systems Limited - Ex. 2019
`Page 8
`
`

`
`U.S. Patent
`
`Dec. 25,2001
`
`Sheet 8 of 9
`
`US 6,334,001 B2
`
`0
`
`1 2 3 4 5 6 7
`1 2 3 4 5 6 7 8
`2 3 4 5 6 7 8 9
`3 4 5 6 7 8 9 10
`5 6 7 8 9 10 11
`4
`5 6 7 8 9 10 11 12
`6
`7 8 9 10 11 12 13
`8 9 10 11 12 13 14
`
`7
`
`FIG. 10
`
`Vedanti Systems Limited - Ex. 2019
`Page 9
`
`

`
`U.S. Patent
`
`Dec.25,2001
`
`Sheet 9 of 9
`
`US 6,334,001 B2
`
`""
`~ Cl::::
`w
`1-z
`Q2
`c...
`
`•II-
`
`~
`I
`----- '--------- -----
`\
`
`-
`
`I
`I
`I
`I
`\
`I
`'-I
`I
`I
`I
`I
`I
`
`..
`
`...
`
`L...
`
`...
`
`w
`u
`~<
`w u..
`V)~
`::::)W
`1-
`z
`
`V)
`V)
`
`~
`0
`w u
`0
`
`......
`......
`•
`
`~ --LL
`
`rf ~ c...
`
`0
`~
`u
`~
`
`~
`
`...
`
`..
`...
`
`~~
`o=>
`~0
`wO
`~~
`7
`' ,..
`L----- --------..P.----
`
`I
`I
`I
`I
`I
`
`LO
`
`0 ""
`
`Cl:::: w z
`z
`< u
`
`V)
`
`(
`
`(Y)
`
`Vedanti Systems Limited - Ex. 2019
`Page 10
`
`

`
`US 6,334,001 B2
`
`1
`ITERATIVE SMOOTHING TECHNIQUE FOR
`PRE-PROCESSING MIXED RASTER
`CONTENT PlANES TO IMPROVE THE
`QUALITY OF A DECOMPRESSED IMAGE
`AND INCREASE DOCUMENT
`COMPRESSION RATIOS
`
`This application is a divisional of application(s) Ser.
`No(s). 09/206,488 filed Dec. 7, 1998.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to image processing and,
`more particularly, to techniques for compressing the digital
`representation of a color document.
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`
`20
`
`Data contained in documents that has been scanned at
`high resolutions requires very large amounts of storage
`space. This data is typically subjected to some form of data
`compression in order to avoid the high costs that would be
`associated with storing it. "Lossless" compression methods
`such as Lempel-Ziv Welch (LZW) do not perform particu(cid:173)
`larly well on portions of the document that are scanned pixel
`maps; "lossy" methods such as JPEG work fairly well on 25
`continuous-tone pixel maps, but they do not work particu(cid:173)
`larly well on the parts of the document that contain text. To
`optimize image data compression, techniques, which can
`recognize the type of data being compressed, are needed.
`One approach to satisfy the compression needs of differ- 30
`ing types of data has been to use Mixed Raster Content
`(MRC) which involves separating a composite image---{)ne
`having text intermingled with color or gray scale
`information-into three planes, and separately applying an
`appropriate compression technique to each plane. An 35
`approach such as this is discussed in U.S. Pat. No. 5,778,092
`to MacLeod et al. issued Jul. 7, 1998, which discloses a
`technique for compressing a color or gray scale pixel map
`that represents a document. The pixel map is decomposed
`into a three-plane representation-a reduced-resolution 40
`foreground plane, a reduced-resolution background plane,
`and a high-resolution binary selector plane. The foreground
`plane contains the color or gray scale information of fore(cid:173)
`ground items such as text. The background plane contains
`the color or gray scale information for the "backgrounds" of 45
`the page and the continuous tone pictures that are contained
`on the page. The selector plane stores information for
`selecting from either the foreground plane or background
`plane during decompression.
`While the MRC technique has shown to be successful at 50
`separately processing planes, the segmentation process
`leaves data in both planes in the areas that will not be chosen
`by the selector plane. This often causes an increase in the
`number of bits that are required to encode the entire image,
`thereby decreasing its compression ratio. This results in 55
`inconveniences to the user of a printer, fax machine, scanner
`or other device in which the technique has been incorpo(cid:173)
`rated. For this reason, it is advantageous to somehow reduce
`the amount of data residing on each plane prior to process(cid:173)
`ing. The present invention is directed to using the informa- 60
`tion that is contained in the selector plane to aid in reducing
`the amount of data residing on the foreground and/or back(cid:173)
`ground planes. More specifically, the invention takes advan(cid:173)
`tage of the fact that when the selector plane designates a
`plane to provide information about a given pixel, the infor- 65
`mation on the other plane that pertains to the same pixel will
`not be used. The invention provides improved compression
`
`2
`of the multi -plane image by treating this useless data in the
`described manner.
`The following disclosures may be relevant to aspects of
`the present invention:
`U.S. Pat. No. 5,251,271 to Fling issued Oct. 5, 1993
`discloses a method for registering digitized multiplane color
`images. The method designates one plane as the reference
`plane and registers each of the other warped planes with the
`reference plane. Each plane comprises pixels representing
`luminosity values having scalar x and y coordinates repre(cid:173)
`senting positions in the horizontal and vertical directions,
`respectively, of the plane. The planes are divided into
`regions. Correlation values are calculated for regions within
`the divisional region of the reference plane with a plurality
`of regions offset from the corresponding warped divisional
`region. A warp error value is calculated for each pixel of
`each divisional region as a function of the scalar offset. The
`warp error values are interpolated and added to the current
`position of each pixel of the warped plane.
`Separate processing of various types of data contained in
`a document is disclosed in U.S. Pat. No. 5,060,980 to
`Johnson et al. issued Oct. 29, 1991 which describes a
`"forms" that includes user modifiable fields and an encoded
`description of the location, size, type, etc. of the fields to
`allow for direct programming of a form interpreter. Other
`information including the processing of the form, encoded
`data, etc. may be included in the encoded information. A
`system for creating forms carrying an encoded description of
`selected attributes of the fields includes means for selecting
`or creating fields and locating the fields on a form while
`generating, substantially simultaneously, the encoded
`description of the selected attributes. A form composer then
`allows merging of the form and its encoded description for
`printing or electronic transmission. A system for reading
`such forms includes a scanner, decoding device, and pro(cid:173)
`cessor. By reading such forms, data may be entered into or
`recalled from a data processing system, or a form interpreter
`may be programmed, locally or remotely, for subsequent
`handling of forms.
`U.S. Pat. No. 5,784,175 to Lee, issued Jul. 21, 1998
`discloses a video compression encoder process for com(cid:173)
`pressing digitized video signals representing display motion
`in video sequences of multiple image frames. The encoder
`process utilizes object-based video compression to improve
`the accuracy and versatility of encoding interframe motion
`and intraframe image features. Video information is com(cid:173)
`pressed relative to objects of arbitrary configurations, rather
`than fixed, regular arrays of pixels as in conventional video
`compression methods. This reduces the error components
`and thereby improves the compression efficiency and accu(cid:173)
`racy. As another benefit, object-based video compression of
`this invention provides interactive video editing capabilities
`for processing compressed video information.
`U.S. Pat. No. 5,303,313 to Mark et al. issued Apr. 12,
`1994 describes image compression based on symbol match(cid:173)
`ing. An image is "pre-compressed" prior to symbol match(cid:173)
`ing using run length encoding. Symbols are then extracted
`from the run length representation. A voting scheme is used
`in conjunction with a plurality of similarity tests to improve
`symbol matching accuracy. A template composition scheme
`wherein the template may be modified based on symbol
`matches is also disclosed.
`Concurrently filed U.S. patent application by DeQueiroz
`et al. identified as Ser. No. 09/206,487 entitled "Method and
`Apparatus for Pre-processing Mixed Raster Content Planes
`to Improve the Quality of a Decompressed Image and
`
`Vedanti Systems Limited - Ex. 2019
`Page 11
`
`

`
`3
`Increase Document Compression Ratios" and assigned to
`the assignee of the present invention discloses a technique
`for processing a color or gray scale pixel map representing
`a document is disclosed. The pixel map is decomposed into
`a three-plane representation, a reduced-resolution "upper"
`plane, a reduced-resolution "lower" plane, and a high(cid:173)
`resolution binary selector plane. The "upper" and "lower"
`planes contain the color or gray scale for the page as well as
`the continuous tone pictures that are contained on the page.
`The selector plane stores information for selecting from 10
`either the foreground plane or background plane during
`decompression. Information contained in the selector plane
`is first used to pre-process the upper and lower planes to
`reduce the amount of data on each of the other two planes
`that will be subjected to further processing. Each of the 15
`pre-processed planes is compressed using a compression
`technique optimal for the type of data that resides upon it.
`All of the references cited herein are incorporated by
`reference for their teachings.
`Accordingly, although known apparatus and processes are
`suitable for their intended purposes, a need remains for a
`method and apparatus that can efficiently process digital
`image data by separately compressing the various portions
`of a composite image.
`
`25
`
`US 6,334,001 B2
`
`4
`three MRC image planes, an upper plane, a lower plane, and
`a selector plane.
`FIG. 2 contains a flowchart illustrating the basic steps for
`compressing a document according to the present invention.
`FIG. 3 shows a detailed example of the typical contents of
`a selector plane for an 8x8 block of pixels.
`FIG. 4 shows a detailed example of an image plane map
`which corresponds to the selector map of FIG. 3.
`FIG. 5 depicts one embodiment of the present invention
`for pre-processing image planes.
`FIG. 6 illustrates another embodiment of the present
`invention for pre-processing image planes.
`FIG. 7 shows the manner in which a near non-destructive
`embodiment of the present invention may be used in con(cid:173)
`junction with a JPEG compression system to pre-process
`image planes for subsequent JPEG compression.
`FIGS. 8-10 contain detailed illustrations of an iterative
`smoothing technique that may be used in conjunction with
`20 the present invention.
`FIG. 11 illustrates a typical device in which the present
`invention may be implemented.
`
`DESCRIPTION OF THE INVENTION
`
`SUMMARY OF THE INVENTION
`
`In one embodiment of the invention, an iterative smooth(cid:173)
`ing technique for processing mixed raster content planes is
`disclosed, which includes the steps of replacing each image
`data signal on the image plane that does not correspond to
`the reconstruction identified locations with a signal equal to
`an average of all image data neighbor signals that corre(cid:173)
`spond to locations previously identified for reconstruction,
`wherein a neighbor signal is defined as an image data signal
`that is horizontally, vertically or diagonally adjacent to the
`image data signal; identifying all of the replaced image data
`signals as reconstruction image data signals in the image
`data plane map; outputting the image plane if all locations in
`the image plane map are reconstruction signals, and repeat(cid:173)
`ing the image data enhancing signal replacing step if less
`than all locations in the image plane map are reconstruction
`signals.
`In another embodiment of the invention an iterative
`smoothing technique for processing mixed raster content
`planes is disclosed, which includes the steps of replacing
`each image data signal on the image plane that does not
`correspond to the reconstruction identified locations with a
`signal equal to an average of all image data neighbor signals
`that correspond to locations previously identified for
`reconstruction, wherein a neighbor signal is defined as an
`image data signal that is horizontally, vertically or diago(cid:173)
`nally adjacent to the image data signal; applying a discrete
`cosine transformation to the image plane and quantizing the
`results of the transformation; inverse quantizing the trans(cid:173)
`formation results and performing an inverse discrete cosine
`transform thereon, thereby generating a pseudo-plane that
`has image data signals that lie in the same locations as
`signals in the image data plane; replacing each image data
`signal on the image data plane that does not correspond to
`a reconstruction identified location on the image data plane
`map with an image data signal on the pseudo-plane that lies
`in a same location.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 illustrates a composite image and includes an
`example of how such an image may be decomposed into
`
`The present invention is directed to a method and appa(cid:173)
`ratus for separately processing the various types of data
`contained in a composite image. While the invention is
`described in conjunction with a Mixed Raster Content
`30 (MRC) representation technique, those skilled in the art will
`recognize that it may be adapted for use with other methods
`and apparatus' and the invention is therefore, not limited to
`this description. The technique described herein is suitable
`for use in various devices required to store or transmit color
`35 or grayscale documents such as facsimile devices, image
`storage devices and the like. It should be noted that the
`examples and illustrations presented in the figures are in
`gray scale, but the same concepts apply to color documents
`and conversely, those portions of the invention that are
`40 described with reference to color documents apply equally
`to gray scale documents.
`A pixel map is one in which each pixel represents some
`"value" which indicates the color or, in the case of gray scale
`document, how light or dark the image is at that point. As
`45 those skilled in the art will appreciate, most pixel maps have
`values that are taken from a set of discrete, non-negative
`integers. For example, a typical gray-scale pixel map might
`have values ranging from 0, representing black, to 255,
`representing the whitest tone possible. The pixel maps of
`50 concern in the currently preferred embodiment are repre(cid:173)
`sentations of "scanned" images. That is, images which are
`created by digitizing light reflected off of physical media
`using a digital scanner. The term bitmap is used to mean a
`binary pixel map in which pixels can take one of two values,
`55 1 or 0. An example of a device that may be used to obtain
`such scanned images is illustrated in FIG. 11.
`Turning now to the drawings for a general description of
`the invention, as indicated in FIG. 1, pixel map 10 repre(cid:173)
`senting a color or gray-scale document is preferably decom-
`60 posed into a three plane page format. The document format
`is comprised of an upper plane 12, a lower plane 14, and a
`selector plane 16. Upper plane 12 and lower plane 14 are
`typically stored at the same bit depth and number of colors
`as the original pixel map 10, but usually at reduced resolu-
`65 tion. However as those skilled in the art will appreciate, the
`processing of planes can include a reduction in the bit depth
`or a palette color encoding. It is important to recognize that
`
`Vedanti Systems Limited - Ex. 2019
`Page 12
`
`

`
`US 6,334,001 B2
`
`5
`while the terms "upper" and "lower" are used to describe the
`planes on which data resides, it is not intended to limit the
`invention to any particular arrangement. Further, it is also
`possible to practice the invention with planes that are
`composed of multiple superimposed separations. If this is
`the case, it is possible to apply the present invention to all
`separations together or to each color separation individually.
`Processing typically occurs on a block by block basis,
`rather than by simultaneously processing all the image data.
`For example, if JPEG compression will be applied, 8x8 10
`blocks must be provided. That is, the image data must be
`separated into groups of 64 pixels, with 8 pixels extending
`in the horizontal direction and 8 pixels extending in the
`vertical direction. JPEG is merely an example of one com(cid:173)
`pression format that may be used with the present invention. 15
`The blocks may be organized in another configuration if
`required by the technique that will be used. After all blocks
`are processed, any or all three planes may be compressed
`using a method suitable for the type data residing thereon.
`Continuing with the example already provided, upper plane 20
`12 and lower plane 14 may be compressed and stored using
`JPEG, while selector plane 16 is compressed using a
`symbol-based compression format. It would be apparent to
`one of skill in the art to compress and store the planes using
`other formats that are suitable for the intended use of the 25
`document. For example, in the Color Facsimile arena, group
`4 (MMR) would preferably used for the selector plane, since
`the particular compression format used must be one of the
`approved formats (MMR, MR, MH, JPEG, JBIG, etc.) for
`facsimile data transmission.
`Lower plane 14 commonly contains both information that
`is pertinent to the background color of the page (including
`the color of tints, washes, etc.) and the continuous-tone
`pictures that are found on the page. Upper plane 12 com(cid:173)
`monly contains the "ink colors" of foreground items such as
`text. Selector plane 16 is typically stored at higher resolution
`than the upper and lower planes. Selector plane 16 is used
`to describe, for each pixel in the selector plane, whether to
`use the pixel value found in the lower plane or the upper
`plane during image reconstruction. If a "white" pixel in the
`selector plane (i.e. a logical zero value) means the pixel
`value should be taken from the corresponding pixel from the
`lower plane, a "black" pixel in the selector plane (i.e. a
`logical one value) means that the pixel value should be taken
`from the corresponding pixel from the upper plane.
`FIG. 2 contains a flowchart depicting the basic steps for
`compressing a document using an embodiment of the
`present invention. Blocks from an original pixel map 10---a
`pixel map representation of the original document to be
`compressed-are first obtained as indicated in step 102. This
`may be through scanning an original, by retrieving a stored
`pixel map representation of the document, or by converting
`an electronic or page description language representation of
`an original document into a pixel map representation. Pixel
`map 10 representation is then analyzed to generate the
`information for the three planes as indicated in steps
`104--108. Selector plane 16 is implicitly or explicitly com(cid:173)
`puted first, as indicated in step 104 and is used to create the
`other planes. Those skilled in the art will recognize that use
`of the phrase "implicitly or explicitly" refers to the fact that 60
`the invention does not require actual calculation and gen(cid:173)
`eration of selector plane 16. While selector plane 16 can be
`generated, the invention may be accomplished by simply
`moving pixels from one plane to another, and marking the
`pixels that have been moved. Technically, this calculates one
`plane such as lower plane 14 first, but simultaneously it
`implicitly calculates selector plane 16.
`
`6
`Selector plane 16 is typically a bitmap computed using a
`technique suitable for finding text or the like on original
`pixel map 10. What results is a bitmap where pixels have a
`1 value where they represent text and a 0 elsewhere. It
`should be noted that the term "text" refers to page objects
`that have text properties, such as sharp, high contrast edges,
`etc., including many other objects that to not qualify as
`"readable" text. Pixels are placed on either upper plane 12
`or lower plane 14 according to the data on selector plane 16.
`An upper plane 12, typically stored at a reduced resolution
`relative to original pixel map 10, contains color (or gray
`scale) information of upper items such as text is computed
`using selector plane as indicated in step 106. Briefly, creat-
`ing upper plane 12 involves creating an image containing the
`color of the objects (pixels) selected in the selector plane.
`Conceptually, the method can be viewed as pouring ink
`contents of the upper plane through a mask located on the
`selector plane onto the background of the lower plane. The
`ink colors are placed in a reduced-resolution "ink map" that
`will ultimately become upper plane 12. Without the present
`invention, the empty values are typically filled in with
`pre-computed ink colors.
`A lower plane 14, also typically stored at a lower reso(cid:173)
`lution than original pixel map 10, is then computed as
`indicated in step 108. In this step, one embodiment of the
`invention includes an image segmentation process that iden(cid:173)
`tifies the "image" or non-text portions. This information is
`used to create the reduced resolution lower map, which
`contains background color information as well as continuous
`tone image information. The result is an image that has all
`small, textlike features deleted, but which includes tints as
`well as color or gray scale data.
`Once the three planes have been generated, either or all of
`them may be compressed at steps 110-114 using a technique
`suitable for compressing the type of data that lies thereon.
`The compressed data representing each plane can be recom(cid:173)
`bined at step 116, after the necessary compression has taken
`place, in order to create a single representation of the data,
`for storage in a computer file, or transmission in a single
`channel. If case multiple transmission channels are available
`step 116 may not be necessary.
`The present invention includes a method and apparatus
`which pre-processes the data on upper plane 12 and lower
`45 plane 14 using the information contained on selector plane
`16. Turning now to FIG. 3, as stated earlier selector plane 16
`includes a pattern of zeros and ones, dispersed in an 8x8
`block. An 8x8 block such as that illustrated here corresponds
`to an 8x8 block of data that is provided by the compressor
`50 which, in the preferred embodiment of the invention, will be
`a JPEG compressor. If a compression technique that pro(cid:173)
`vides data in another configuration is used, selector plane 16
`will have the zeros and ones placed thereon, dispersed in a
`corresponding pattern. As stated earlier, it is assumed here
`55 that a 0 on selector plane 16 means that the pixel value
`should be taken from the corresponding pixel from the lower
`plane 14, while a 1 on the selector plane means that the pixel
`value should be taken from the corresponding pixel from
`upper plane 12.
`In the preferred embodiment of the present invention,
`when processing image planes that will be reduced for
`compression, the block size used in the pre-processing step
`may be enlarged to compensate for the reduction in image
`size, so that the final processed block size matches the block
`65 size used for compressing the image plane.
`Referring now to FIG. 4, image plane maps that identify
`the pixels in each block that will be used to reconstruct the
`
`30
`
`35
`
`40
`
`Vedanti Systems Limited - Ex. 2019
`Page 13
`
`

`
`US 6,334,001 B2
`
`10
`
`7
`final output image from the two planes is next created. For
`lower plane 14 map 304, is created wherein an "N" is placed
`in every location in which a 1 was located on selector plane
`16 to mark the pixels in the block that will not be used during
`image reconstruction. A "Y" is placed in those locations in
`which O's were located on selector plane 16 to show the
`pixels in the block that are to be retained for the output
`image. Similarly, for upper plane 12, map 302 is created and
`N's are placed in those locations which correspond toO's on
`selector plane 16, while Y's are placed in the locations that
`correspond to 1 's. Those skilled in the art will recognize that
`the second map generated may be created by simply invert(cid:173)
`ing the first map.
`In one embodiment of the invention, referred to as non(cid:173)
`destructive processing, retained ("Y" labeled) pixels are
`never modified. As indicated in FIG. 5, the first step 402 is
`to determine the number of locations in the block in the
`image plane map 302 or 304 that have been identified as
`disposable ("N" pixels). For simplicity, the invention will
`continue to be described with reference to a block in the
`lower plane 14. As shown in step 406, if no locations in
`image plane map 304 have been identified as N locations,
`the block is simply output as is. Note that the average "A"
`of the block is implicitly or explicitly computed before it is
`output in step 406. Those skilled in the art will recognize that
`average "A" could be obtained by be reusing the DC term of
`the JPEG compression, and that while an explicit calculation
`may occur, it is not necessary. On the other hand, if all
`locations in image plane map 304 have been identified as N
`locations, all of the pixels in the block that lie on lower plane
`14 can be set to a constant value. In one embodiment of the
`invention, the constant value is set equal to the average of all
`pixels values in the previously processed block, i.e. set to
`"A". Those skilled in the art will recognize that numerous
`methods can be used to calculate the most appropriate
`constant value, and that the invention is not limited to using
`this average. Lower plane 14 with its newly assigned values
`is then output at step 406.
`With continued reference to FIG. 5, if neither all nor none
`of the pixels on image plane map 304 in the block being
`processed have been identified as N pixels (i.e. the number
`of N identified pixels is not equal to either zero or the
`maximum value which, in the case of JPEG compression
`would be 64) all of the pixels in the block that correspond
`to Y locations on image plane map 304 are replaced with
`values that will enhance the compression of the block.
`Specifically, values placed on lower plane 14 will be those
`that will minimize the amount of data that will be generated
`during image compression. In the preferred embodiment of
`the invention, these values will be provided using an iter a-