Compression and expansion methods and apparatus

• US 6,061,473 A
• Filed: 04/18/1997
• Issued: 05/09/2000
• Est. Priority Date: 05/17/1996
• Status: Expired due to Fees

• Current Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Original Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Inventors: Chen, Liming, Asada, Osamu
• Primary Examiner(s): Couso, Yon J.
• Application Number:
  US08/844,528
• Time in Patent Office: 1,117 Days
• Field of Search: 382/235, 382/237, 382/239, 382/244, 358/261.2, 358/426, 358/429, 358/430, 358/433, 358/459, 358/404, 358/436, 358/435, 358/438, 395/115, 345/203
• US Class Current: 382/235
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A compression and encoding system for bi-level image data determines the available memory capacity of a receiving device, then compresses and encodes the image data with successively increasing compression ratios until encoded data not exceeding the memory capacity of the receiving device are obtained. Preferably, the image is divided into rectangular blocks, and successive bit planes are generated on the basis of the number of dark picture elements in each block, and on the basis of adjacency relationships among like-valued picture elements in each block. Feedback may be employed to adjust the darkness of certain compressed blocks according to the darkness of the preceding block.

Claims

1. A method of compressing image data for transmission from a first device to a second device which is physically separate from but connected to the first device, the second device having a limited memory capacity, comprising the steps of:

(a) querying said second device, thereby determining an available memory capacity of said second device;

(b) encoding and storing said image data to obtain first encoded data;

(c) comparing an amount of said first encoded data with said available memory capacity;

(d) transmitting said first encoded data to said second device if the amount of said first encoded data does not exceed said available memory capacity;

(e) compressing said image data with a certain compression ratio to obtain compressed data, if the amount of said first encoded data exceeds said available memory capacity;

(f) encoding said compressed data to obtain second encoded data;

(g) comparing the amount of said second encoded data with said available memory capacity;

(h) transmitting said second encoded data to said second device if the amount of said second encoded data does not exceed said available memory capacity; and

(i) repeating said steps (e), (f), (g), and (h), with successively increasing compression ratios in said step (e), if the amount of said second encoded data exceeds said available memory capacity, until the amount of second encoded data does not exceed said available memory capacity.

2. The method of claim 1, wherein said image data are bi-level image data, and said step (e) comprises the further steps of:

(j) arranging said bi-level image data into blocks, each block being a two-by-two block with four data bits;

(k) counting bits having a certain value, thereby determining a weight of each said block;

(l) detecting horizontal, vertical, and diagonal adjacency relationships among like-valued bits in each said block;

(m) generating, from each said block, at least one bit with a value responsive to the weight of said block; and

(n) generating, from blocks having a certain weight, at least one subsequent bit having a value responsive to said adjacency relationships.

3. The method of claim 2, comprising the further step of:

(o) adjusting the weight determined in said step (k) according to the weight of a preceding block.

4. The method of claim 2, wherein said step (i) comprises the further step of:

(p) discarding bits generated in said step (e), thereby increasing said compression ratio.

5. The method of claim 4, wherein said step (p) always leaves undiscarded at least one bit having a value responsive to said weight.

6. The method of claim 2, wherein increasing weights indicate increasing darkness, and said step (m) generates, for each said block, a most significant bit indicating whether said block has at least a certain threshold weight.

7. The method of claim 6, comprising the further step of:

(q) increasing the weight determined in said step (k) when the most significant bit generated in said step (m) from a preceding block indicates that said preceding block had at least said threshold weight.

8. A compression and encoding apparatus for preparing image data for transmission from a sending device to a receiving device which is physically separate from but connected to the sending device, the receiving device having a limited memory capacity, comprising:

a plurality of data compressors, for compressing said image data with different compression ratios, thereby generating compressed data;

a selector coupled to said data compressors, for selecting the compressed data generated by one of said data compressors, responsive to a control signal;

an encoder coupled to said selector, for encoding the compressed data selected by said selector, thereby generating encoded data;

an encoded data memory coupled to said coder, for storing said encoded data; and

a memory checker coupled to said encoded data memory, for comparing the amount of said encoded data with an available memory capacity in said receiving device, and generating said control signal, thereby causing said selector to select compressed data that have been compressed with successively increasing compression ratios, until the amount of said encoded data does not exceed said available memory capacity.

9. The apparatus of claim 8, further comprising a plurality of compressed data memories coupled to respective data compressors, for storing the compressed data generated by said data compressors, and providing said compressed data to said selector.

10. The apparatus of claim 8, wherein said memory checker sends said control signal to said receiving device.

11. A data compressor for compressing bi-level image data, comprising:

a block formatter for arranging said bi-level image data into two-by-two blocks;

a counter coupled to said block formatter, for counting said bits having a certain value, thereby determining a weight of each said block;

an adjacency detector coupled to said block formatter, for detecting horizontal, vertical, and diagonal adjacency relationships among like-valued bits in the two-by-two image area represented by each said block;

a compressed pattern generator coupled to said counter, for generating, from each said block, at least one bit with a value responsive to the weight of said block, and for generating, from blocks having a certain weight, at least one subsequent bit having a value responsive to said adjacency relationships; and

a bit selector coupled to said compressed pattern generator, for selecting, as compressed image data, at least one bit generated by said compressed pattern generator for each said block.

12. The data compressor of claim 11, wherein for each said block, said bit selector begins by selecting at least one most significant bit generated responsive to said weight.

13. The data compressor of claim 11, wherein said bit selector first selects one bit for every said block, then selects one more bit for every said block, then continues in like manner, selecting bits one at a time per block, until a desired number of bits per block have been selected.

14. The data compressor of claim 11, wherein increasing weights indicate increasing darkness, and said compressed pattern generator generates, for each said block, a most significant bit indicating whether said block has at least a certain threshold weight.

15. The data compressor of claim 14, wherein said threshold value is two.

16. The data compressor of claim 11, wherein said compressed pattern generator generates, for each block having a weight of at least two, two subsequent bits collectively having a first value if said weight is equal to two and said adjacency relationships are vertical, a second value if said weight is equal to two and said adjacency relationships are horizontal, a third value if said weight is equal to two and said adjacency relationships are diagonal, and a fourth value if said weight is greater than two.

17. The data compressor of claim 11, wherein said compressed pattern generator generates, for each said block, two bits responsive to said weight.

18. The data compressor of claim 17, wherein said compressed pattern generator generates, for each said block, two subsequent bits, said two subsequent bits being generated responsive to said adjacency relationships when said weight is two.

19. The data compressor of claim 11, also comprising a feedback unit coupled to said counter, for supplying said counter with a value responsive to the weight of each said block, for use by said counter in calculating the weight of a next block.

20. The data compressor of claim 19, wherein increasing weights represent increasing darkness, and the value supplied by said feedback unit indicates whether said weight is less than two.

21. The apparatus of claim 20, wherein said counter uses the value supplied by said feedback unit only when the weight of said next block is equal to one.

22. The apparatus of claim 21 wherein, when said value indicates a weight not less than two and the weight of said next block is equal to one, said counter increases the weight of said next block from one to two.

23. A compression and encoding apparatus for preparing bi-level image data for transmission from a sending device to a receiving device which is physically separate from but connected to the sending device, the receiving device having a limited memory capacity, comprising:

a data compressor, for compressing said bi-level image data with different compression ratios, responsive to a control signal, thereby generating compressed data;

an encoder coupled to said data compressor, for encoding said compressed data, thereby generating encoded data;

an encoded data memory in said sending device coupled to said encoder, for storing said encoded data; and

a memory checker coupled to said encoded data memory, for comparing the amount of said encoded data with an available memory capacity in said receiving device, and generating said control signal, thereby causing said data compressor to generate compressed data that have been compressed with successively increasing compression ratios, until the amount of said encoded data does not exceed said available memory capacity;

wherein said data compressor comprises;

a block formatter for arranging said bi-level image data into two-by-two blocks, each block representing a two-by-two image area;

a counter for counting bits having a certain value, thereby determining a weight of each said block;

an adjacency detector for detecting horizontal, vertical, and diagonal adjacency relationships among like-valued bits in the image area represented by each said block;

a compressed pattern generator for generating, from each said block at least one bit with a value responsive to the weight of said block, and for generating, from blocks having a certain weight, at least one subsequent bit having a value responsive to said adjacency relationships; and

a bit selector for selecting, as compressed image data, at least one bit generated by said compressed pattern generator for each said block.

24. The apparatus of claim 23, wherein said compressed data comprise a number of bits varying from one bit to four bits per block, responsive to said control signal.

25. A decoding and expanding apparatus for decoding and expanding compressively coded image data, comprising:

an interface unit for receiving said compressively coded image data and receiving information specifying a compression ratio from a device physically separate from but connected to said decoding and expanding apparatus;

a receiving memory coupled to said interface unit, for storing said compressively coded image data;

a decoder coupled to said receiving memory, for decoding said compressively coded image data, thereby generating decoded data;

a plurality of data expanders coupled to said decoder, for expanding said decoded data with different expansion ratios, thereby generating expanded image data;

a selector coupled to said data expanders, for selecting the expanded image data generated by one of said data expanders, responsive to said compression ratio; and

an output unit coupled to said selector, for outputting the expanded image data selected by said selector.

26. The decoding and expanding apparatus of claim 25, wherein said interface unit receives successive encoded bit planes.

27. The decoding and expanding apparatus of claim 26, wherein said data expanders expand said decoded data by interleaving said bit planes responsive to said information specifying a compression ratio.

28. The decoding and expanding apparatus of claim 27, wherein said data expanders assign different resolutions to said expanded image data in one direction, responsive to said information specifying a compression ratio, while leaving the resolution of said expanded image data constant in another direction.