Adaptive encoding and decoding of bi-level images

• US 6,990,242 B2
• Filed: 11/12/2004
• Issued: 01/24/2006
• Est. Priority Date: 03/23/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US10/988,089
• Publication Number:
  US 20050089233A1
• Time in Patent Office: 438 Days
• Field of Search: 382/232, 382/233, 382/236, 382/238, 382244-247, 348/384.1, 348/394.1, 348/411.1, 348/412.1, 348/415.1, 348/417.1, 348/418.1, 348/422.1, 348/425.2, 358/426.01, 358/426.09, 358/426.13, 375/240.12, 375/240.27, 341/65, 341/94
• US Class Current: 382/238
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 1/417 using predictive or differential encoding

Abstract

A system and process for encoding and later decoding of bi-level images 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.

Claims

1. A process for encoding bi-level images, said process comprising:

for each pixel location in raster order in the bi-level image,

a predicting step for predicting a binary value for the pixel at a pixel location under consideration based on its context, wherein a context of a pixel refers to predicted values of a prescribed pattern of pixels preceding the pixel in raster order, said predicting step comprising,

an assigning step for assigning a prescribed initial probability value to each of a set of potential context indexes, wherein a context index is a binary word comprising previously predicted binary values of a prescribed pattern of pixels of the bi-level image preceding in raster order a pixel whose value is currently being predicted, and wherein the initial probability value indicates the probability that the pixel whose value is currently being predicted has a first binary value associated with a first of the two colors of the bi-level image based on the predicted values of the prescribed pattern of pixels preceding the pixel being predicted, and

for each pixel location in raster order in the bi-level image,

a computing step for computing the context index associated with the prescribed pattern of pixels preceding the pixel location under consideration, wherein pixel locations in the pattern that fall outside the bi-level image are considered to have the first binary value,

an identifying step for identifying the probability value assigned to the computed context index,

whenever the identified probability value indicates that the pixel location under consideration is more likely than not to have the first binary value, a second assigning step for assigning as the predicted pixel value for that location the first binary value, and

whenever the identified probability value indicates that the pixel location under consideration is not more likely than not to have the first binary value, a third assigning step for assigning as the predicted pixel value for that location the second binary value associated with a second of the two colors of the bi-level image, and

a determining step for determining whether the predicted pixel value matches the actual pixel value for the pixel location under consideration; and

a compressing step for compressing the data concerning at which pixel locations the predicted pixel values match and do not match the actual values using a context-dependent, backward adaptive, Run-Length-Rice encoding technique.

2. The process of claim 1, wherein the first assigning step for assigning a prescribed initial probability value to each of a set of potential context indexes, comprises assigning the same initial probability value to each context index, said initial probability being a number indicative of a 0.50 probability that the pixel value has the first binary value.

3. The process of claim 1, further comprising an adjusting step for adjusting the probability value assigned to the computed context index by increasing it by a prescribed amount if the predicted pixel value of the pixel location under consideration is assigned the first binary value and decreasing it by a prescribed amount if the predicted pixel value is assigned the second binary value.

4. The process of claim 3, wherein the probability values are scaled so as to range between 0 and prescribed maximum integer number, and wherein the adjusting step comprises making the adjustments in integer increments.

5. The process of claim 4, wherein the adjusting step further comprises:

whenever decreasing the scaled probability value would result in a value of less than 0, making the probability value 0; and

whenever increasing the scaled probability value would result in a value of greater than the prescribed maximum minus one, making the probability value equal to the prescribed maximum minus one.

6. A process for encoding bi-level images, comprising:

for each pixel location in raster order in the bi-level image,

a predicting step for predicting a binary value for the pixel at a pixel location under consideration based on its context, wherein a context of a pixel refers to predicted values of a prescribed pattern of pixels preceding the pixel in raster order, and

a determining step for determining whether the predicted pixel value matches the actual pixel value for the pixel location under consideration; and

a compressing step for compressing the data concerning at which pixel locations the predicted pixel values match and do not match the actual values using a context-dependent, backward adaptive, Run-Length-Rice encoding technique, wherein said compressing step comprises,

an assigning step for assigning a prescribed initial k value to each context index, wherein a k value is used to compute a number representing a string of consecutive, raster ordered, prediction error values having the first binary value,

an identifying step for identifying the k value assigned to the context index computed for the first pixel location in the bi-level image and subsequently for each pixel location that follows in raster order a pixel that triggered a codeword to be established, and

for each pixel location in the bi-level image beginning with the first and proceeding in raster order,

a second determining step for determining if the prediction error value assigned to the pixel location under consideration has the first or second binary value,

whenever the prediction error value assigned to the pixel location under consideration has the first value, steps for taking no action unless the number of preceding pixels locations for which no action has been taken equals the last-identified k value and if it does equal this k value establishing a first type of codeword by representing the number of preceding pixel locations for which no action has been taken with a single first value, and

whenever the prediction error value assigned to the pixel location under consideration has the second value, an establishing step for establishing a second type of codeword by representing the prediction error having the second value and the number of preceding pixel locations for which no action has been taken with a second value and a binary word indicating the number of preceding pixel locations for which no action has been taken.

7. The process of claim 6, further comprising a computing step for computing the number representing the string of consecutive, raster ordered, prediction error values having the first binary value from an assigned k value using the equation 2^k.

8. The process of claim 6, wherein the first assigning step comprises assigning the same initial k value to each context index, said initial k value being two.

9. The process of claim 6, further comprising, whenever a codeword is established, an adjusting step for adjusting the k value assigned to the context index associated with pixel location that begins the string of prediction error values represented by that codeword by increasing it by a prescribed amount if the codeword is of the first type and decreasing it by a prescribed amount if the codeword is of the second type.

10. The process of claim 9, wherein the k values are scaled by multiplying each by a prescribed scaling factor.

11. The process of claim 10, wherein the prescribed amount that the scaled k values are increased or decreased depends on how many times the k values has been adjusted from its initial value.

12. The process of claim 11, wherein the prescribed scaling factor equals 16, the prescribed amount that a k value is increased is 3, 3, 4, 5, and 6 for the first through fifth times it is consecutively increased, respectively, and 8 for each time it is consecutively increased after the fifth time.

13. The process of claim 11, the prescribed amount that a k value is decreased is 0, 3, 6, 6, 8 and 10 for the first through sixth times it is consecutively decreased, respectively, and 12 for each time it is consecutively decreased after the sixth time.

14. A process for decoding a bi-level image encoded by a process that reduces the image data to a series of codewords from which can be derived prediction error values indicating whether the pixel values of each pixel location in the bi-level image had a first binary value or a second binary value, said codewords coming in two types a first of which is a first value representing a number of pixel locations that have a first binary prediction error value and the second of which comprises a second value followed by a binary word that indicates the number of pixel locations preceding a location having a second binary prediction error value that exhibit the first binary prediction error value, said process comprising:

a receiving step for receiving the series of codewords;

for each pixel location in raster order in a restoration image of the encoded bi-level image;

a predicting step for predicting a binary value for the pixel at the pixel location under consideration based on its context, wherein a context of a pixel refers to predicted values of a prescribed pattern of pixels preceding the pixel in raster order, and

a deriving step for deriving a prediction error value for the pixel location under consideration from a received codeword;

a comparing step for comparing in raster order the prediction error assigned to a pixel location of the restoration image and the predicted pixel value for that location using an exclusive OR process such that whenever the prediction error value is the first binary value the corresponding predicted pixel value is not changed, and whenever the prediction error value is the second binary value the corresponding predicted pixel value is flipped to its opposite binary value; and

a designating step for designating the result of each prediction error and predicted pixel value comparison as a restored pixel value for the associated pixel location in the restoration image.

15. The process of claim 14, wherein the predicting step comprises:

an assigning step for assigning a prescribed initial probability value to each of a set of potential context indexes which is identical to those used in encoding the bi-level image, wherein a context index is a binary word comprising previously predicted binary values of a prescribed pattern of pixels of the bi-level image preceding in raster order a pixel whose value is currently being predicted, and wherein the initial probability value indicates the probability that the pixel whose value is currently being predicted has a first binary value associated with a first of the two colors of a restoration image of the encoded bi-level image based on the predicted values of the prescribed pattern of pixels preceding the pixel being predicted; and

for each pixel location in raster order in the restoration image of the encoded bi-level image upon receiving the first of the series of codewords,

a computing step for computing the context index associated with the prescribed pattern of pixels preceding the pixel location under consideration, wherein pixel locations in the pattern that fall outside the bi-level image are considered to have the first binary value,

an identifying step for identifying the probability value assigned to the computed context index,

whenever the identified probability value indicates that the pixel location under consideration is more likely than not to have the first binary value, a second assigning step for assigning as the predicted pixel value for that location the first binary value, and

whenever the identified probability value indicates that the pixel location under consideration is not more likely than not to have the first binary value, a third assigning step for assigning as the predicted pixel value for that location the second binary value associated with a second of the two colors of the bi-level image.

16. The process of claim 15, further comprising an adjusting step for adjusting the probability value assigned to the computed context index by increasing it by the prescribed amount used in encoding the bi-level image if the predicted pixel value of the pixel location under consideration is assigned the first binary value and decreasing it by the prescribed amount used in encoding the bi-level image if the predicted pixel value is assigned the second binary value.

17. The process of claim 16, wherein the probability values are scaled so as to range between 0 and a prescribed maximum integer number identical to that used in the encoding of the bi-level image, and wherein the adjusting step comprises:

making the adjustments in integer increments;

making the probability value 0, whenever decreasing the scaled probability value would result in a value of less than 0; and

making the probability value equal to the prescribed maximum minus one, whenever increasing the scaled probability value would result in a value of greater than the prescribed maximum minus one.

18. The process of claim 14, wherein the deriving step comprises:

an assigning step for assigning a prescribed initial k value to each context index that is identical to the value used in encoding the bi-level image, wherein a k value is used to compute a number representing a string of consecutive, raster ordered, prediction error values having the first binary value in the same manner employed in encoding the bi-level image being decoded;

a determining step for determining if the last-received codeword is of the first or second type;

whenever the last-received codeword is of the second type, a second assigning step for assigning prediction error values having the first binary value to the number of previously-unassigned pixel locations in a restoration of the encoded bi-level image in raster order starting with the earliest non-assigned location that are indicated by the binary word component of the codeword and assigning a prediction error value having the second binary value to the pixel location following those newly assigned pixel locations; and

whenever the last-received codeword is of the first type,

an identifying step for identifying the k value assigned to the context index associated with the earliest pixel location in the restoration image not yet assigned a prediction error value, and

a third assigning step for assigning prediction error values having the first binary value to the number of previously-unassigned pixel locations that are indicated by the identified k value in the restoration image in raster order starting with the earliest non-assigned location.

19. The process of claim 18, further comprising, upon completion of assigning prediction error values in connection with the processing of the last-received codeword, an adjusting step for adjusting the k value assigned to the context index associated with pixel location that begins the string of prediction error values just assigned by increasing the k value by a prescribed amount employed in the encoding of the bi-level image being decoded if the codeword is of the first type and decreasing the k value by a prescribed amount employed in the encoding of the bi-level image being decoded if the codeword is of the second type.

20. The process of claim 19, wherein the k values are scaled by multiplying each by a prescribed scaling factor employed in the encoding of the bi-level image being decoded.