Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1997-11-26
2001-08-07
Grant, II, Jerome (Department: 2624)
Image analysis
Image compression or coding
Lossless compression
C358S296000
Reexamination Certificate
active
06272256
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the compression of periodic halftoned digital images. More particularly, the invention concerns a way to increase the compression ratio obtained on periodic halftones using commonly known compression components, while reducing the time required to perform the compression.
2. Description of the Related Art
Data compression is a process of finding the most efficient way to represent a message in order to minimize the size of a message for transfer or storage. Data compression usually consists of two phases—choosing a model for the message source and designing an efficient coding system for the model.
A message generated by an information source may take on many possible forms depending upon the context in which the message was made, and the goal of compressed communication in general is to transmit the minimal encoded version of the original message such that the receiver of the message can still reconstruct it. For example, the information to be sent may be the results of a bicycle race. If the recipient of the message already knows the names and numbers of the cyclists, then all that must be transferred is the number of the cyclist that won. In another context, the number might mean something entirely different, such as the price of a dozen mangoes. Accordingly, the key to quick and effective compressed communication is minimizing the length of information that must be transferred to accurately send the correct message or in the case of a photograph, the correct image. Thus, the shortest representation of the source of the message—so that the message can be taken in context—and the message itself is critical to efficient compressed communications.
Generally, if each piece of information sent representing a message or image is not equally likely to occur it is more efficient on the average to allocate a short string to frequently occurring pieces of information and longer strings to less frequent pieces. Thus, Morse code allots the shortest string (a dot and pause) to the letter “e” because it appears most frequently in words, and allots a long string (dash, dash, dot, dot and pause) to the less frequently appearing letter “z.”
One important area in data compression is the compression of periodic halftoned bilevel digital (halftoned) images used predominantly to prepare continuous tone photographic images for bitonal printing. Continuous tone (e.g., monochrome) photographs are transformed into a bitonal (e.g., black/white) “halftoned” equivalent, which in digital form is represented as a bilevel (e.g., “1” or “0” valued) image. Numerous methods used primarily for textual image compression have been attempted for compressing such bilevel halftoned images. For example, one-dimensional schemes, such as Modified Huffman (MH) coding, or two-dimensional schemes, such as the Modified Relative Element Address Designate (MR)—commonly referred to as the CCITT Group 3 compression scheme—are simple and efficient but unable to effectively compress halftoned images.
The MR coding method exploits vertical correlation between scan lines in textual images by attempting to code all black/white pixel color changes (BW edges) and white/black pixel color changes (WB edges) in an image with respect to a given reference edge located directly above in a previous line. If such coding fails or is not reproductable at a decoder. the method changes to an MH coding method, which uses alternating sequential run-length coders for alternating black and white runs. Note that this also equates to coding alternating BW and WB edge positions.
The MMR or Modified MR two-dimensional compressor coding method, widely known as the CCITT Group 4 compression scheme removes some error protection overhead from the MR coding method but is still unable to effectively compress halftoned images.
The problem with these one- and two-dimensional coding schemes for halftoned encoding is that binary halftoned representations of continuous tone images have very different distributions of run size and occurrences of vertical references from the text or line drawing images for which these schemes were designed. As a result, the amount of data required to represent halftoned images in “compressed” form when these schemes are used, may actually be greater than the amount of data required to represent the original uncompressed image.
Recently, complex adaptive coding methods like various Ziv-Lempel algorithms and the arithmetic coding based Joint Bi-level Image Experts Group (JBIG) algorithm as set forth in
ITU
-
T Recommendation T
.82, “Information Technology—Coded Representation of Picture and Audio Information—Progressive Bi-level Image Compression,” have been developed which arc aimed at compressing both textual and halftoned images. Unlike static algorithms like MH, MR or MMR used for textual images, these adaptive algorithms can adjust to the more balanced white and black pixel probabilities and shorter run length characteristics of halftoned images. The problem is that these adaptive algorithms arc not simple nor fast enough to replace the above static algorithms in software. For example, the Ziv-Lempel algorithms build complex dictionaries or alternatively perform complex dictionary searches in real time. Typically, they also exploit byte-oriented characteristics rather than the bit-oriented characteristics of bitonal images. Although byte-processing makes the Ziv-Lempel algorithms faster in compressing bitonal images than adaptive arithmetic coding methods such as JBIG methods, these algorithms are not as fast as MH, MR or MMR. Furthermore, although JBIG will compress halftoned images much better than the Ziv-Lempel algorithms, it is even more complex and even slower in executing.
These above methods for compressing halftoned images constitute significant advances and enjoy widespread commercial success today. But what is needed is a simple and efficient method and apparatus for compressing halftoned images that increases compression ratios and decreases the time required to perform the compression over the commonly used MH, MR or MMR coding methods.
SUMMARY OF THE INVENTION
Broadly, the present invention concerns a method and apparatus incorporating a binary function correlation of pixel edges to compress periodic halftoned bitonal images. The invention efficiently compresses the images while increasing compression ratios over currently known methods and decreasing the time required to compress the data.
In one embodiment, the invention may be implemented to provide a method to compress and decompress the periodic halftoned digital (halftoned) images by horizontally encoding pixel edges located at least &tgr; pixels from a reference pixel edge in raster sequential image data. After the image is divided into lines of digital bits containing digital information indicative of binary values, the lines are encoded. A value for &tgr;—where &tgr; is independent of a width (W) of the image and represents the pixel distance or period between pixel value changes (edges)—is selected. Thereafter, most edges occurring among successive target pixels to be coded, are encoded with respect to designated reference pixel edges located &tgr;±n pixels earlier. This process. discussed in detail below, repeats until the entire image has been encoded.
In other versions, the method may include encoding groups of successive same valued target pixels where the pixel edge of each group is located &tgr;±n pixels from the edge of a designated reference pixel group. Or the method may include encoding groups of successive pixel edges where all pixel edges in the group occur exactly &tgr;±n pixels from their designated reference pixel edges.
In another embodiment, the invention may be implemented to provide an apparatus to compress and decompress a halftoned image. The apparatus may include an encoder, a decoder, multiple interfaces and a digital data processing apparatus for executing the method. Or the invention may be implemented by application spe
Arps Ronald Barthold
Constantinescu Mihail Corneliu
Baker Maxham Jester & Meador
Grant II Jerome
International Business Machines - Corporation
LandOfFree
Fast compression of periodic halftoned bitonal images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast compression of periodic halftoned bitonal images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast compression of periodic halftoned bitonal images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449962