Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
2001-03-23
2004-12-14
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Predictive coding
Reexamination Certificate
active
06832005
ABSTRACT:
BACKGROUND
1. Technical Field
The invention is related to the encoding and subsequent decoding of bi-level images, and more particularly to a system and process for encoding and decoding bi-level images that uses two context-based adaptive modules: 1) an adaptive predictor controlled by low-resolution probability estimates that is used to map the original pixels explicitly into prediction error pixels, and 2) a backward-adaptive Run-Length-Rice (RLR) coder that encodes the prediction error pixels.
2. Background Art
Bi-level images are quite common in digital document processing, because they offer the potential for a compact representation of black-and-white documents containing texts and drawings. In such images, their picture elements (pixels) can be seen as coming from a binary source (e.g., white=“0” and black=“1”). Since they usually contain a lot of white space and repeated ink patterns, one basic approach to efficiently encode such images is to scan them in raster order, e.g., from top to bottom and left to right, and encode each pixel via adaptive arithmetic coding (AC), whose state (or probability table) is controlled by a context formed by the values of the pixels in a small template enclosing previously encoded pixels [1]. That idea is the basis of most modern bi-level image compression systems.
Facsimile images are usually transmitted using the old CCITT standards T.4 and T.6, which are usually referred to as Group 3 and Group 4 respectively. G3 usually encodes images with a modified Huffman (MH) code (i.e., Huffman coding on runs of black or white pixels), and G4 uses MMR coding. MH and MMR are not as efficient as context-adaptive AC, but are simpler to implement. Over time, G3 and G4 evolved to include encoding via JBIG (also known as recommendation T.82). JBIG uses the context-adaptive AC, with adaptive templates and the efficient QM binary arithmetic encoder [2]. The JBIG-2 standard extends JBIG by including pattern matching for text and halftone data, as well as soft pattern matching (SPM) [3] for lossy encoding. The JB2 encoder [4] is also based on SPM, but uses the Z-coder for binary encoding. JBIG, JBIG-2 and JB2 can provide a significant improvement in compression performance over G4.
Although arithmetic coding is usually the choice when high compression performance is desired, comparable performance can be achieved by appropriate refinements to run-length (RL) coders. The Z-coder and the adaptive TRL coder are examples of efficient RL variants.
It is noted that in this background section and in the remainder of the specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, “reference [1]” or simply “[1]”. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.
SUMMARY
The present invention is directed at a new bi-level image encoding and decoding system and process that does not use arithmetic coding, but whose performance is close to that of state-of-the-art coders such as JBIG, JBIG-2, and JB2. In general, the present bi-level coder (BLC) uses two context-based adaptive modules: 1) an adaptive predictor controlled by low-resolution probability estimates that is used to map the original pixels explicitly into prediction error pixels, and 2) a backward-adaptive Run-Length-Rice (RLR) coder that encodes the prediction error pixels. That's contrary to the usual approach where the context-dependent probability estimate controls both pixel prediction and adaptive entropy coding. Due to its simplicity, in many applications BLC may be a better choice other current coders.
The bi-level image compression encoding begins with a pixel prediction and prediction error generation procedure. Pixel prediction generally entails predicting the value of a pixel (e.g., either 0 or 1) based on surrounding pixels. More particularly, pixel prediction is accomplished by computing context-dependent probability estimates. A context is essentially a neighborhood of previously encoded pixels forming a pattern referred to as a template. Any standard template can be adopted for the purposes of the present invention. The context can be viewed as vector list of a prescribed number of pixel values in raster order. These values form a binary word that uniquely identifies the context. This binary word is referred to as a context index.
The context-dependent probability estimates are computed by first creating and initializing a pixel probability table. This is accomplished by assigning an initial probability to each of the possible context indexes. Preferably, the initial probability would be 0.5 (i.e., an equal possibility that the pixel associated with the context index is black or white). The probability value is however scaled to prevent any round-off problems between the encoder and decoder. Preferably, the scaling is done by choosing an integer number representing a probability of 100% that a pixel is white. For example, in tested embodiments of the present invention the number “8” was employed. Thus, the scaled probability representing the aforementioned initial value would be “4”.
For each pixel in raster order, the context index associated with the pattern of previously encoded pixels is identified and the scaled probability read from the table. If the probability is 0.5 or above (i.e., a scaled probability of 4 or above in the example given above), then the pixel under consideration is predicted to be white and assigned the appropriate binary value (e.g., preferably a “0” pixel value). Note that the first time each context index is encountered, the prediction will always be a white pixel since a scaled probability of 4 was initially assigned to each context index in the table. The scaled prediction value is then adjusted by increasing it by a prescribed amount (e.g., by one) if the pixel just predicted was deemed to be white, or decreasing it by a prescribed amount (e.g., by one) if the pixel was predicted to be black. The results of the scaled probability adjustment operation are truncated to a zero value if it falls below zero, and to the maximum scaled probability value minus one if it falls above that value. Thus, the probabilities will vary depending on the image being encoded and what pixel location is being predicted. This is referred to as backward adaptive pixel prediction, since the decoder can perform the same adjustments to the probability estimates without the need for explicit context probability information to be sent to the decoder.
The prediction error is computed next. Essentially, the prediction error is computed by comparing the predicted pixel value of either black or white for each pixel in the bi-level image to the actual pixel. Then, only data concerning those predictions that are incorrect need be transmitted. In most cases, the prediction will be correct, so a considerable savings in the amount of data can be realized. This works because as will be described later, the decoder performs the same prediction process and will get the same results including the errors. Thus, all the decoder needs to know is which of the predicted pixel values are in error so they can be changed from white to black or black to white, as the case may be, to reconstruct the image. The prediction error is specifically computed using a binary technique such that the actual value of each pixel in the image is compared to its predicted value using exclusive OR logic. Thus, if the actual pixel value matches the predicted value (e.g., both are 0's or both are 1's), then a “0” is assigned to that pixel location as part of a so-called prediction error image. However, if the actual pixel value is different from the predicted value, then a “1” is assigned to the associated pixel location in the prediction error image.
The next phase of the bi-level image encoding involves the use of a cont
Couso Jose L.
Lyon Richard T.
Lyon & Harr LLP
Microsoft Corporation
LandOfFree
Adaptive encoding and decoding of bi-level 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 Adaptive encoding and decoding of bi-level images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive encoding and decoding of bi-level images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329454