Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1998-12-22
2001-11-27
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Adaptive coding
C382S176000, C358S001150, C358S462000
Reexamination Certificate
active
06324305
ABSTRACT:
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.
BACKGROUND OF THE INVENTION
Documents scanned at high resolutions require very large amounts of storage space. Instead of being stored as is, the data is typically subjected to some form of data compression in order to reduce its volume, and thereby avoid the high costs associated with storing it. “Lossless” compression methods such as Lempel-Ziv (LZ) do not perform particularly well on scanned pixel maps. While “lossy” methods such as JPEG work fairly well on continuous-tone pixel maps, they do not work particularly well on the parts of the page containing 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 differing types of data has been to use the Mixed Raster Content (MRC) format to describe the image. The image—a composite image having text intermingled with color or gray scale information—is segmented into two or more planes, generally referred to as the upper and lower plane, and a selector plane is generated to indicate, for each pixel, which of the image planes contains the actual image data that should be used to reconstruct the final output image. Segmenting the planes in this manner can improve the compression of the image because the data can be arranged such that the planes are smoother and more compressible than the original image. Segmentation also allows different compression methods to be applied to the different planes. Thus, a compression technique that is most appropriate for the data residing thereon can be applied to each plane.
An approach such as this is discussed in U.S. Pat. No. 5,778,092 to MacLeod et al. issued Jul. 7, 1998, the contents of which are hereby incorporated by reference. U.S. Pat. No. 5,778,092 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 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 foreground items such as text. The background plane contains the color or gray scale information for the “background” of 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.
When an MRC technique is used to compress a color digital image, the upper and lower planes are typically compressed using both lossy and lossless techniques, with the lossy compression being directed to entire pixel blocks and lossless compression applied to individual pixels. In other words, for each plane every pixel block is either subjected to lossless compression (which is appropriate for smooth, low-noise data) or to lossy compression (more appropriate for scanned pictorial data), possibly followed by overriding of certain designated pixels with values that have been obtained using a lossless compression technique.
While MRC has shown to be successful at separately processing data once it has been placed on these separate planes, subjecting an entire block of pixels to lossy compression, then applying a lossless technique to some pixels in the block and replacing the appropriate values is very inefficient, and often causes an increase in the number of bits that are required to encode the entire image, thereby lengthening the amount of time in which full processing of the image will take place. This results in inconveniences to the user of a printer, fax machine, scanner or other device in which the technique has been incorporated. Processing images at low speed in printers and copiers results in reduced output speeds, which is undesirable and often unacceptable in today's office environment. In fax machines, image processing at slow speeds could require the addition of very large buffers and/or very fast modems in order to prevent the modem from disconnecting before the entire image is transmitted since the modem can remain idle for lengthy periods of time while waiting for image data to be processed. For this reason, it is advantageous to somehow reduce the amount of data residing on each plane prior to processing.
The present invention is directed to segmenting and then compressing color image data using the MRC format. The segmenting embodiments of the invention are directed to separating the original image data into two planes based upon the manner in which the data should subsequently be compressed. Compression embodiments are directed to compressing the data on the segmented planes using an appropriate technique. The compressed planes are then combined to produce the final output image. The compression technique will either have one selector plane for the entire image (image-wise segmentation), or one per separation (separation-wise segmentation).
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 multi-plane 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 representing 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 “form” 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 processor. 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 compressing 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 compressed 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 accuracy. 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
Buckley Robert R.
Crean Peter A.
Holladay Thomas M.
Klassen R. Victor
Zeck Norman W.
Chen Wenpeng
Costello Mark
Dudley Mark Z.
Xerox Corporation
LandOfFree
Method and apparatus for segmenting a composite image into... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for segmenting a composite image into..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for segmenting a composite image into... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2589966