Compressing/decompressing bitmap by performing exclusive- or operation setting differential encoding of first and previous row therewith outputting run-length encoding of row

• US 6,304,928 B1
• Filed: 07/01/1998
• Issued: 10/16/2001
• Est. Priority Date: 07/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Picturetel Corporation (HP Inc.), Microsoft Corporation
• Inventors: MacFarquhar, Roderick F., Pollitt, Alex J., Batty, John P., Downes, Anthony M., Hughes, Kenneth P., Mairs, Christopher J., Berry, Mark E.
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): Peyton, Tammara
• Application Number:
  US09/108,881
• Time in Patent Office: 1,203 Days
• Field of Search: 710/68, 709/247, 345/200, 345/201, 345/202, 345/415, 348/416, 382/234, 358/261.1, 358/261.2
• US Class Current: 710/68
• CPC Class Codes: G06F 3/1462 with means for detecting differences between the image stored in the host and the images displayed on the remote displays
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A method and system for compressing bitmap data in a system for sharing an application running on a host computer with a remote computer, wherein the shared application'"'"'s screen output is simultaneously displayed on both computers. Simultaneous display of screen output is achieved by efficiently transmitting display data between the host computer and the remote computer. When a font used by the host computer for displaying text is not available on the remote computer, the host computer sends a bitmap representation of the text for display, rather than the text itself. Bitmap representations are cached by the remote computer, so that the same bitmap representation need not be repeatedly transmitted from the host computer to the remote computer. Bitmap representations are compressed by the host computer prior to transmission, transmitted, then decompressed by the remote computer.

Claims

1. A method in a computer system for compressing a bitmap, the bitmap having data organized into rows, each row having a number of bits, each bit having a 0-bit value or a 1-bit value, the method comprising:

outputting an indication of the value of each bit in a first row of data; and

for each subsequent row of the bitmap,

generating an interim row having the number of bits by performing an exclusive OR operation on the row, thereby setting the bit value of each bit in the interim row to a differential encoding of a corresponding bit in the row and of a corresponding bit in a previous row; and

outputting a run-length encoding of the bits of the interim row.

2. The method of claim 1 wherein the outputting of the indication of the value of each bit in the first row of data includes outputting a run-length encoding of the bits of the first row of data.

3. The method of claim 1 wherein the previous row is the immediately previous row.

4. The method of claim 1 wherein the run-length encoding encodes a run of 0-bit values as the length of the run.

5. The method of claim 1 wherein the run-length encoding encodes a run of a repeating group of bit values as an indication of the group followed by the length of the run.

6. The method of claim 5 wherein the group of bit values indicates color of a pixel.

7. The method of claim 1 wherein the run-length encoding encodes a run comprising a group of 0-bit values and a group of non-zero bit values as an indication of the group of non-zero bit values and a data array indicating position of the groups in the run.

8. The method of claim 7 wherein the groups of bit values indicate color of a pixel.

9. The method of claim 1 wherein the run-length encoding encodes a run comprising alternating two groups of bit values as an indication of the two groups and the length of the run.

10. The method of claim 9 wherein the groups of bit values indicate color of a pixel.

11. The method of claim 1 wherein the run-length encoding encodes a run of 0-bit values as the length of the run, encodes a run of a repeating group of bit values as an indication of the group followed by the length of the run, encodes a run comprising a group of 0-bit values and a group of non-zero bit values as an indication of the group of non-zero bit values and a data array indicating position of the groups in the run, and encodes a run comprising alternating two groups of bit values as an indication of the two groups and the length of the run.

12. The method of claim 11 wherein the groups of bit values indicates color of a pixel.

24. The computer-readable storage device of claim 7 wherein the groups of bit values indicate color of a pixel.

13. A method in a computer system for decompressing a compressed bitmap, the bitmap having data organized into rows, each row having a number of bits, each bit having a 0-bit value or a 1-bit value, the compressed bitmap including an indication of the value of each bit in the first row of data and for each subsequent row of the bitmap, a run-length encoding of bit values of an interim row previously generated by performing an exclusive OR differential encoding routine on the a corresponding bit in the row and of a corresponding bit in a previous row, the method comprising:

outputting an indication of the value of each bit in the first row; and

for each subsequent row of the bitmap,

generating an interim row represented by the run-length encoding for that row; and

outputting a reversal of the exclusive OR differential encoding of the bit value for each bit of the interim row with a previous row.

14. The method of claim 13 wherein the indication of the value of each bit in the first row is a run-length encoding of the bits of the first row of data.

15. The method of claim 13 wherein the previous row is the immediately previous row.

16. The method of claim 13 wherein the run-length encoding encodes a run of 0-bit values as the length of the run, encodes a run of a repeating group of bit values as an indication of the group followed by the length of the run, encodes a run comprising a group of 0-bit values and a group of non-zero bit values as an indication of the group of non-zero bit values and a data array indicating position of the groups in the run, and encodes a run comprising alternating two groups of bit values as an indication of the two groups and the length of the run.

17. The method of claim 16 wherein the groups of bit values indicate color of a pixel.

18. A computer-readable storage device containing instructions for controlling a computer system to compress a bitmap, the bitmap having data organized into rows, each row having a number of bits, each bit having a 0-bit value or a 1-bit value, by:

outputting a run-length encoding of the first row of data;

for each row of the bitmap except for the first row, generating an interim row having the number of bits by setting the bit value of each bit in the interim row to the exclusive-OR of a corresponding bit in the row and of a corresponding bit in a previous row; and

outputting a run-length encoding for each interim row of data.

19. The computer-readable storage device of claim 18 wherein the previous row is the immediately previous row.

20. The computer-readable storage device of claim 18 wherein the run-length encoding encodes a run of 0-bit values as the length of the run.

21. The computer-readable storage device of claim 18 wherein the run-length encoding encodes a run of a repeating group of bit values as an indication of the group followed by the length of the run.

22. The computer-readable storage device of claim 21 wherein the group of bit values indicates color of a pixel.

23. The computer-readable storage device of claim 18 wherein the run-length encoding encodes a run comprising a group of 0-bit values and a group of non-zero bit values as an indication of the group of non-zero bit values and a data array indicating position of the groups in the run.

25. The computer-readable storage device of claim 18 wherein the run-length encoding encodes a run comprising alternating two groups of bit values as an indication of the two groups and the length of the run.

26. The computer-readable storage device of claim 25 wherein the groups of bit values indicate color of a pixel.

27. The computer-readable storage device of claim 18 wherein the run-length encoding encodes a run of 0-bit values as the length of the run, encodes a run of a repeating group of bit values as an indication of the group followed by the length of the run, encodes a run comprising a group of 0-bit values and a group of non-zero bit values as an indication of the group of non-zero bit values and a data array indicating position of the groups in the run, and encodes a run comprising alternating two groups of bit values as an indication of the two groups and the length of the run.

28. The computer-readable storage device of claim 27 wherein the groups of bit values indicates color of a pixel.

29. A computer system for compressing a bitmap, the bitmap having data organized into row, each row having a number of bits, each bit having a 0-bit value or a 1-bit value, comprising:

a first component that outputs an indication of the value of each bit in the first row of data; and

a second component that, for each other row of the bitmap, generates an interim row having the number of bits by performing an exclusive OR operation on the row, thereby setting the bit value of each bit in the interim row to a differential encoding of a corresponding bit in the row and of a corresponding bit in a previous row and outputs a run-length encoding of the bits of the interim row of data.

30. The computer system of claim 29 wherein the outputting of the indication of the value of each bit in first row of data includes outputting a run-length encoding of the bits of the first row of data.

31. The computer system of claim 29 wherein the previous row is the immediately previous row.

32. A computer-readable medium containing a compressed bitmap, the bitmap having data organized into rows, each row having bits, each bit having a 0-bit value or a 1-bit value, comprising:

an indication of the value of each bit in a first row of data; and

for each other row of data, a run-length encoding of bits that were generated by performing an exclusive OR operation on the row to differentially encode a corresponding bit in the row and a corresponding bit of another row.

33. The computer-readable medium of claim 32 wherein the indications of the value of each bit in the first row of data is run-length encoded.

34. The computer-readable medium of claim 32 wherein the other row is an immediately previous row.