Video compression algorithm

• US 5,335,299 A
• Filed: 05/02/1991
• Issued: 08/02/1994
• Est. Priority Date: 08/11/1987
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Atkinson, William
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/694,660
• Time in Patent Office: 1,188 Days
• Field of Search: 382/56, 382/8, 382/48, 382/21, 382/22, 382/47, 358/133, 358/261.1, 358/261.2, 358/261.7, 358/261.4, 358/426
• US Class Current: 382/244
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 1/413 Systems or arrangements allowing the picture to be reproduced without loss or modification of picture-information

Abstract

A method for encoding compressed graphics video information and decoding such information. The method consists of enriching the video information in zeros through shifting and Exclusive ORing video image with itself. A number of methods are attempted in the shifting and Exclusive ORing process in order to determine the method which yields the optimum zero enriched image. The zero enriched image is then encoded and the encoded information stored. Upon retrieval, the information is decoded and an Exclusive OR and shifting process is done to obtain the original video information.

Claims

1. A method of compressing information comprising the steps of:

(a) enriching a bit-map of said information in a first binary state by;

(i) copying a first row of said bit-map;

(ii) shifting said copy of said first row a predetermined number of bits in a first direction;

(iii) performing a logical operation using as input said first row of data and said copy of said first row of data yielding a second row of data;

(iv) determining the number of bits of data in said second row of data which are in said first binary state;

(v) if said number of bits in said binary state is greater than a first value, storing said number of bits as said first value and storing said predetermined number as a second value; and

(b) encoding said enriched bit-map.

2. The method, as recited by claim 1, wherein said encoding of said enriched bit-map comprises the steps of:

determining whether a first row of said bit-map meets one of a predetermined set of conditions;

if one of said predetermined set of conditions is met, storing one of a first set of predetermined codes.

3. The method, as recited by claim 2, wherein said predetermined set of conditions comprises:

determining if said first row is all in said first binary state;

determining if said first row is all in a second binary state;

determining if a first group of bits repeats in said first row; and

determining if said first row is identical to a second row of said bit-map.

4. The method, as recited by claim 1, further comprising the step of decoding said encoded information.

5. The method, as recited by claim 4, wherein said decoding of said encoded information comprises the steps of:

(a) reading an operation code;

(b) determining from said operation code whether the operation code indicates the beginning of a first row of data;

(c) if said operation code indicates the beginning of said first row of data, processing said operation code;

(d) otherwise, unpacking said first row of data.

6. The method, as recited in claim 5, wherein said processing a beginning of row operation code comprises the steps of:

(a) if said operation code indicates the data is not compressed, copying the uncompressed data;

(b) if said operation code indicates said first row is comprised of bits all of a first binary state, filling said first row with bits of said first binary state;

(c) if said operation code indicates said first row is comprised of bits all of a second binary state, filling said first row with bits of said second binary state;

(d) if said operation code indicates the data repeats a block of data, filling said first row with duplicates of said block of data;

(e) if said operation code indicates said first row is the same as a second row offset a predetermined number of rows from said first row, copying said second row.

7. The method, as recited in claim 6, wherein said unpacking of said data comprises the step of using a table having predetermined values to unpack said data.

8. The method, as recited by claim 1, wherein said encoding said enriched bit-map comprises the step of representing said enriched bit-map with codes representing runs of bits in said first binary state and runs of bits in a second binary state.

9. The method, as recited by claim 1, wherein said first binary state is a low state.

10. The method as recited by claim 1 wherein steps (i) through (v) are repeated for each of a first set of predetermined numbers.

11. The method as recited by claim 1 wherein said logical function is an Exclusive OR function.

12. A method of compressing and redisplaying video information from a bit-mapped display device comprising the steps of:

determining whether one of a first set of predetermined conditions is satisfied by a first row of data;

if one of said first set of predetermined conditions is satisfied storing one of a first set of codes;

enriching said bit-map of said information in a first binary state by shifting a copy of said bit map and performing an Exclusive OR function using said bit map and said shifted copy of said bit map as inputs to said Exclusive OR function;

encoding said enriched bit-map by representing said bit-map as runs of said first binary state and runs of a second binary state;

decoding said information by reading a plurality of operations codes and reconstructing said bit-map from said operation codes.

13. The method, as recited by claim 12, wherein said first set of predetermined conditions comprises:

determining if all bits in said first row of said information are in said first binary state;

determining if all bits of said first row of said information are in said second binary state;

determining if a first group of bits repeats in said first row; and

determining if said first row is identical to a second row of said bit-map.

14. The method, as recited by claim 13, wherein said first binary state is a low state.

15. The method, as recited by claim 14, wherein said second binary state is a high state.

16. The method, as recited by claim 12, wherein said unpacking of said data comprises the step of using a translation table having predetermined values to unpack said data.