Browse Prior Art Database

Run Length Encoding of Documents Without Error Propagation

IP.com Disclosure Number: IPCOM000089749D
Original Publication Date: 1977-Dec-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 2 page(s) / 25K

Publishing Venue

IBM

Related People

Hehl, W: AUTHOR

Abstract

The compression of image data by encoding the length of black and white "runs", which are obtained by linearly scanning the document, has the disadvantage that one erroneous length resulting from transmission or storage retrieval will shift all subsequent runs, thus considerably affecting the reconstructed image.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 72% of the total text.

Page 1 of 2

Run Length Encoding of Documents Without Error Propagation

The compression of image data by encoding the length of black and white "runs", which are obtained by linearly scanning the document, has the disadvantage that one erroneous length resulting from transmission or storage retrieval will shift all subsequent runs, thus considerably affecting the reconstructed image.

It is proposed, therefore, to encode sum s(i) of all previously encountered run-lengths rather than individual lengths r(i). The latter lengths r(i) are restored by subtracting two adjacent sum values. To limit the digit number of the sums, a modulo-M addition of the lengths is performed, M being a conveniently chosen number of code words defining a maximum length (M-1) of runs. However, the particular choice of M does not limit the general validity of this encoding method for all kinds of documents.

In terms of formulae (B, B designating modulo-algebra) this means:

(Image Omitted)

Errors in sum values are thus confined to that pair of runs in which they actually occurred (see case I in example below).

If the errors encountered are such that the maximum length is exceeded (see case II in example below), the module-M calculation introduces errors of M bits. This can be avoided by choosing a modulo base M' > M (for the same maximum run-length M to be encoded); in the most general case, M' = 2M-1.

The modulo bases M may be chosen differently for black and white runs if the length statistics are diff...