Real time data compression/decompression scheme for facsimile transmission system

• US 4,360,840 A
• Filed: 05/13/1980
• Issued: 11/23/1982
• Est. Priority Date: 05/13/1980
• Status: Expired due to Term

• Current Assignee: e-CRM Trust
• Original Assignee: AM International Incorporated (Paragon Corporate Holdings, Inc.)
• Inventors: Barrett, Frederick C., Wolfrum, Larry M.
• Primary Examiner(s): BRITTON, HOWARD W
• Application Number:
  US06/149,362
• Time in Patent Office: 924 Days
• Field of Search: 358/261, 358/260, 340/347 DD
• US Class Current: 358/426.12
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
• CPC Class Codes: H04N 1/419 in which encoding of the length of a succession of picture-elements of the same value along a scanning line is the only encoding step H04N1/4135 - H04N1/417 take precedence

Abstract

A graphic image represented by a two-level pel-to-pel definition is compressed by one-dimensional redundancy reduction coding using an entropy preserving algorithm which allows for real time reduction of the pel-to-pel data without any loss in image resolution. The compressed data is concatenated for transmission and then separated and decoded back to a pel-to-pel format for defining a facsimile image.

Claims

1. A method of one-dimensional redundancy reduction coding, transmission and decoding of binary image data by use of an entropy preserving algorithm, the image data of the type including two-level pel representation of an image to be transmitted, comprising the steps of:

(a) generating an image definition comprising a serial stream of binary data bits, each bit representing a single pel of either a first level or a second level;

(b) assigning a predetermined binary code N having a number of data bits n representing a runlength of consecutive pels of a single level;

(c) assigning a prefix P for defining with N a codeword representation of a runlength, the prefix P having a number of data bits p, whereby the total number of data bits representing each runlength of pels is defined by a codeword comprising a prefix P and a code N having (p+n) data bits;

(d) concatenating consecutive codewords;

(e) framing the concatenated codewords into output words W each having a fixed, predetermined number of data bits w;

(f) transmitting the output words; and

(g) receiving and decoding the transmitted output words for generating therefrom a serial stream of data bits, each bit representing a single pel of one of said levels, by searching in said output words for the prefix P associated with a codeword and identifying therefrom the (p+n) bits associated therewith.

2. The method of claim 1, wherein the step of concatenating consecutive codewords comprises:

(a) framing the first w bits of a first group of consecutive codewords to define an output word;

(b) preserving any residue bits r in said first group of consecutive codewords in excess of the first w bits; and

(c) framing said residue bits with the first (w-r) bits of a second group of consecutive codewords to define another output word.

3. The method of claim 2, wherein the step of decoding the transmitted output words comprises:

(a) identifying a codeword comprising (p+n) bits in the output words; and

(b) generating a corresponding serial stream of binary bits, each bit representing a single pel in a runlength of pels of one of said two levels.

4. The method of claim 3, wherein the steps of decoding the transmitted output words further comprises:

(a) locating the prefix P associated with each codeword in said output words;

(b) framing the (p+n) bits defined by the prefix P and associated with the corresponding codeword; and

(c) generating the corresponding serial stream of binary data bits defined by the n bits identifying the code N in said (p+n) bits.

5. The method of claim 1, wherein w is an arbitrary number.

6. The method of claim 1, wherein p is proportional to n.

7. The method of claim 6 where n is an arbitrary number of from two to n bits and wherein p is equal to the quantity (n-2).

8. The method of claim 1 wherein the first runlength of each data image is arbitrarily defined as a runlength of a predetermined one of said pel levels.

9. The method of claim 8, wherein each code N represents runlengths of either of said pel levels.

10. The method of claim 9, including the steps of setting an arbitrary limit on the consecutive number of pels of one level in a runlength, defined by a single codeword and assigning a unique code to a runlength having a number of pels in excess of the limit for indicating that the runlength of pels is defined by a plurality of consecutive codewords defining consecutive runlengths of the same pel level.

11. The method of claim 1, wherein the binary image data is generated by a raster scan device adapted for optically scanning an image on a sheet document.

12. The method of claim 11, wherein the scanner defines the image as a plurality of pels for each line of scan and wherein the first runlength of each line is arbitrarily defined as a runlength of a predetermined one of said pel levels.

13. The method of claim 11, including the step of defining on the sheet document a predetermined image area to be scanned.

14. An apparatus for one-dimensional redundancy reduction coding, transmitting and decoding binary data by use of an entropy preserving algorithm, the data representing an image in a plurality of two-level pels, comprising:

(a) means for generating an image definition comprising a serial stream of binary data bits, each bit representing a single pel of either a first level or a second level;

(b) means for defining the boundaries between runs of consecutive pels of the same level by using an entropy preserving algorithm, wherein there is further;

(i) means for assigning a predetermined binary code N having a number of data bits n representing a runlength of consecutive pels of a single level;

(ii) means for assigning a prefix P for defining with N a codeword representation of a runlength, the prefix P having a number of data bits p, whereby the total number of data bits representing each runlength of pels is defined by a codeword comprising a prefix P and a code N having (p+n) data bits;

(c) means dependent on said boundaries for generating a binary codeword representing each of said runs;

(d) means for concatenating the first w bits of a first group of consecutive codewords to define an output word;

(e) means for separating and storing any residue bits r in the first group of codewords in excess of w bits;

(f) means for defining another output word from the next subsequent group of codewords by concatenating the first (w-r) bits of said group with the residue bits r of the first group of codewords;

(g) means for transmitting the output words; and

(h) means for extracting the codewords from said output words for reformation of the image in pel-to-pel format.

15. The apparatus of claim 14, wherein the output words include a predetermined, arbitrary number of data bits w, wherein the codewords contain from 2 to n bits, and wherein w is not required to be a whole number multiple of n.

16. The apparatus of claim 15, further including:

(a) means for concatenating the first w bits of a first group of consecutive codewords to define an output word;

(b) means for separating and storing any residue bits r in the first group of codewords in excess of w bits; and

(c) means for defining another output word from the next subsequent group of codewords by concatenating the first (w-r) bits of said group with the residue bits r of the first group of codewords.

17. The apparatus of claim 15, the means for decoding further comprising means for extracting whole codewords from one or more output words.

18. The apparatus of claim 14 wherein the means for generating an image definition comprises a raster scanner for optically scanning an image on a sheet document.