Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1995-12-04
2002-01-22
Au, Amelia M. (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C358S438000
Reexamination Certificate
active
06341178
ABSTRACT:
This invention relates generally to compression of binary images, and more particularly to the lossless precompression of binary images that are to be stored or transmitted at high resolutions.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND AND SUMMARY OF THE INVENTION
The present invention is related to the lossless precompression of binary images that are to be stored or transmitted at high resolutions. More specifically, the present invention employs an area-based compression technique that is appropriate for high resolution bit replicated images. The technique searches for regularly sized image regions of a common color and represents the areas in a coded fashion. The compression technique employed by the present invention enables high resolution images to be compressed and stored or transmitted at an image size approximating the size of an image typically obtained by lossless compression of the original bitmap binary image from which the high resolution image was generated. While most applicable to binary images, the technique can be applied to multiple bit per pixel gray scale images by treating each plane of individual bits as a binary image.
In many digital printing architectures (including printers, copiers, and multifunction machines) it is necessary to store precollated images in memory so that such images may be accessed and printed at a high bandwidth. This is opposed to the well-known practice of composing/collating the image “on-the-fly” which tends to result in slower printing speeds or the need for higher-speed hardware. However, there are drawbacks associated with the storage of image bitmaps in memory, hereafter referred to as electronic precollation memory (EPC). The primary drawback is that the size of the memory must be significant in order to store even moderate resolution images. For example, a full page binary image bitmap at 300 spots per inch (spi) requires approximately 1.05 megabytes (MB) of memory. The problem is only exacerbated by higher resolution printers. A 1200 spi printer will require approximately 16.83 MB to store the same image at the higher resolution. Thus, it is apparent that as the resolution of digital printers increases, there is an ever-growing need for improved compression techniques to reduce precollation memory requirements.
Heretofore, a number of patents and publications have disclosed compression techniques, the relevant portions of which may be briefly summarized as follows:
U.S. Pat. No. 5,144,682 to Nakamura, issued Sep. 1, 1992, discloses a method and apparatus for isolating an area corresponding to a character or word. Included therein is a compression treatment section for compressing the data of the original manuscript in a direction corresponding to that of the manuscript's character line and a compressed image buffer (a ring buffer) for storing the image data. The compression section performs an OR logic operation to accomplish proportional compression. Also described are thresholding and thinning compression methods. The area of connected picture elements is determined by a contour following operation (col. 4-5 & FIG.
4
). A rectangular area having an apex of the minimum main and subscanning addresses and another opposing apex of the maximum main and subscanning addresses is then extracted. However, this area is merely a representation of an area within the compressed image (col. 6, lines 1-7).
U.S. Pat. No. 5,204,756 to Chevion et al., issued Apr. 20, 1993, teaches a method for the compression and decompression of binary images. The invention accomplishes variable compression ratios through the use of lossy and lossless compression techniques, selected based upon an evaluation of the binary image at hand. After evaluating the image by dividing it into mutually exclusive segments (e.g., image or text segments), a raster-based compression technique is selected based upon the type of the image segment. The selection (determined by a compression ratio) is further influenced by a metric characterized as the relative widths of black or white intervals in the original text image.
U.S. Pat. No. 5,363,205 to Shou et al., issued Nov. 8, 1994, teaches an image compression method which successively diminishes in size the image to form a compressed image. In particular, a gray scale image is successively reduced by representing a 2×2 convolution by a pixel of its mean density.
J. Murray & W. vanRyper, in “Encyclopedia of Graphic File Formats,” O'Reilly & Assoc., July 1994, pp. 125-171 describe details of various publicly known data compression schemes. The publication is hereby incorporated by reference for its teachings relating to compression terminology and compression schemes.
D. Moitra, in “Finding a Minimal Cover for Binary Images: An Optimal Parallel Algorithm,” published Nov. 1, 1988 (Cornell University, Computer Science Department), teaches an algorithm for determining a minimal set of maximal squares to cover a binary image. The minimal set of black subsquares is intended to cover the black regions of the image using a set of overlapping squares. Described further is a cover graph which compactly represents the covering relationships between the squares.
SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a method, operating in an image processing system, for compressing a binary input image where the binary input image is represented as a regular array of binary image signals, comprising the steps of:
identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state;
determining the size of the orthogonally shaped region;
encoding the state and size of the orthogonally shaped region as a digital data word;
storing the digital data word representing the encoded shape and size in compression memory; and
repeating the above steps for each of a plurality of orthogonally shaped regions of binary image signals present within the binary input image.
In accordance with another aspect of the present invention, there is provided an image processing system, comprising:
image data memory for storing binary image signals;
a processor, operating in response to a set of preprogrammed instructions, for identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state, said processor further determining the size of the orthogonally shaped, two-dimensional region, encoding the state and size of the orthogonally shaped region as a digital data word, and outputting the encoded digital data word;
a lossless data compressor, responsive to the digital data word output by the processor, for applying lossless compression to the digital data word to produce compressed data therefrom; and
precollation memory for storing the compressed data produced by the lossless data compressor.
In accordance with yet another aspect of the present invention, there is provided a method, operating in an image processing system, for compressing a binary input image where the binary input image is represented as a regular array of binary image signals, comprising the steps of:
(a) identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state;
(b) determining the size of the orthogonally shaped region;
(c) encoding the state and size of the orthogonally shaped region as a digital data word;
(d) storing the digital data word representing the encoded shape and size in compression memory;
(e) repeating the above steps for each of a plurality of orthogonally shaped regions of binary image signals present within the binary input image to produce a precompressed image; and
(f) losslessly compressing the precompressed image to produce a compressed image.
One aspect of the inv
Au Amelia M.
Basch Duane C.
Johnson Tim
Xerox Corporation
LandOfFree
Method and apparatus for lossless precompression of binary... 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 lossless precompression of binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for lossless precompression of binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2821129