CA1336015C - Video compression algorithm - Google Patents
Video compression algorithmInfo
- Publication number
- CA1336015C CA1336015C CA 574357 CA574357A CA1336015C CA 1336015 C CA1336015 C CA 1336015C CA 574357 CA574357 CA 574357 CA 574357 A CA574357 A CA 574357A CA 1336015 C CA1336015 C CA 1336015C
- Authority
- CA
- Canada
- Prior art keywords
- row
- data
- binary state
- operation code
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
- H04N1/41—Bandwidth or redundancy reduction
- H04N1/411—Bandwidth or redundancy reduction for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures
- H04N1/413—Systems or arrangements allowing the picture to be reproduced without loss or modification of picture-information
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
- Image Processing (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
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.
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.
Description
1 R~CK~ROUND OF TH~ INVFNTION
1. Field of the Invention.
This invention relates to the field of video compresslon algorithms and, more specifically, to the field of compression algorithms for bit-mapped graphic displays.
1. Field of the Invention.
This invention relates to the field of video compresslon algorithms and, more specifically, to the field of compression algorithms for bit-mapped graphic displays.
2. Prior Art.
Numerous methods are known for compression of data in computer systems and for compression of data for video displays or bit-mapped graphic displays. However, each of these methods suffers from one or more of several disadvantages. A method is desired which allows data to be stored in a compacted form after it is received from a bit-mapped graphics display or other similar device. The data should be stored in a manner which enables it to be decoded with a minimum of resources being used in the decoding process. ln addition, the data should be stored in as compact of form as possible.
~ 3~6~1 5 SUMMARY OF THF. I~VF.NT~ON
A method of compressing video information from a bit-mapped graphics display or similar device is disclosed. The method reduces the number of bits which must be physically stored in order to store a video image. The main steps of the algorithm are enriching a bit-map of the video image in zeros and encoding the enriched image into runs of zeros and data bytes.
The enriching of the video image in zeros is done by performing an auto correlation (shifting and Exclusive ORing) for horizontal and vertical lines. The number of zeros resulting from each correlation is counted until it is d~termined which combination produces the richest zeros.
The bit-map of zero enriched lines is then encoded into runs of zeros and data bytes. Special cases, such as a row being all zeros or a row being all ones, are recognized and assigned a special code. In addition, special codes are assigned in the case of zero matching the row immediately prior to it or the row two rows prior to it. Special codes are also assigned to indicate that a code is repeated a number of times. Other uses of special codes will be seen in the detailed description of the present invention.
A method of reconstructing the compressed data ls also disclosed. This method reads the encoded data and recreates the uncompressed data. Various methods are included for ~' 1 3 ~ 6 G ~ ~
optimizing the speed of this process including the use of a table for decoding certain encoded data.
Accordingly, in one of its aspects, the present invention relates to a method of compressing information comprising the steps of:
enriching a bit-map of said information in a first binary state;
encoding said enriched bit-map;
whereby, said information is compressed.
Further aspects of the invention reside in providing a method of compressing information comprising the step of 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 words of data in said second row of data which are in said first binary state;
(v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
1 376~ ~ ~
(vi) performing a logical operation using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(vii) determining the number of words of data in said fourth row of data which are in said first binary state;
(viii) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (ix) repeating steps (vi) through (viii) for each of a second set of predetermined numbers.
In a further aspect, the present invention relates to 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 an Exclusive OR 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 words of data in said second row of data which are in said first binary state, and (v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(b) encoding said enriched bit-map;
(c) performing an Exclusive OR function using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(d) determining the number of words of data in said fourth row of data which are in said first binary state;
(e) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (f) repeating steps (c) through (e) for each of a second set of predetermined numbers.
In a still further aspect, the present invention relates to 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 B ~
... ...
~ 33 6~ 1 ~
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, and (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.
In another aspect, the present invention relates to 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; and deco~ing said information by reading a plurality of operation codes and reconstructing said bit-map from said operation codes.
, ~ J ~\~i ri 1 5 -In a further aspect, the present invention relates to a method of decompressing information comprising the step of:
(a) reading an operation code; and (b) if said operation code indicates the beginning of a first row of data, processing said operation code by:
(i) if said operation code indicates said first row of data is not compressed, copying said data, (ii) if said operation code indicates said first row of data is comprised of bits all of a first binary state, filling said first row with bits of said first binary state, (iii) if said operation code indicates said first row of data is comprised of bits all of a second binary state, filling said first row with bits of said second binary state, (iv) if said operation code indicates said first row of data repeats a block of data, filling said first row with duplicates of said block of data, and (v) if said operation code indicates said first row of data is identical to a second row of data, copying said second row.
. ..
-- RRTF.F nF.SCRIPTION OF THF. r)RA~INGS
Figure 1 is a flow chart describing steps involved in encoding video data as may be utilized by the present invention.
Figure 2(a) illustrates a display device with a blackened square in the center as may be compressed by the present invention.
Figure 2(b) illustrates the blackened square display after a first step of the compression as may be accomplished by the present invention.
Figure 2(c) illustrates the blackened square display after a second step of compression as may be accomplished by the present invention.
Figure 3 illustrates an address space of operation codes as may be utilized by the present invention.
Figure 4(a) illustrates rows of data as may be compressed by the present invention.
Figure 4(b) illustrates a step of Exclusive ORing to rows of data as may be accomplished by the present invention during compression of the data.
1 3 J ~S ~0 1 5 1 ~~ Figure 4(c) illustrates rows of data and associated compression codes as may be utilized by the present invention.
Figure 5 is a flow chart illustrating preliminary tests to be performed on rows of data during encoding as may be accomplished by the present invention.
Figure 6 is a flow chart illustrating a method of determining an optimum zero enriched method as may be utilized by the present invention.
Figure 7 is a flow chart illustrating a method of reconstructing video data from compressed data as may be utilized by the present invention.
.
Figure 8 is a flow chart illustrating a method of processing a beginning of row operation code as may be utilized by the present invention.
Figure 9 is a flow chart illustrating a process of decoding rows encoded by shifting and Exclusive ORing as may be utilized by the present invention.
1 3JG~1 5 1 D~TAITF~n nFSCRIPTION OF TH~ PRFS~T INVFNTION
A method of compressing and reconstructing video data ls described. In the following description, numerous speciflc details are set forth such as operation codes, speciflc steps, etc., in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well known structures and techniques have not been shown in detail in order not to unnecessarily obscure the present invention.
The present invention comprises a method of compressing video information, typically from a bit-mapped display or similar dev$ce and a method of reconstructing the compressed .
video information to allow redisplay of the data. The invention is based on the observation that a typical bit-mapped video image comprises a majority of either "white~
areas or patterns of data. A purely random pattern of white and dark areas on a bit-mapped video display is rare.
Therefore, the present invention takes advantage of these observations by further enriching a bit-map of a video image in zeros by performing an auto correlation of vertical and horizontal lines. The enrichment in zeros is due to the large amount of "white space" on the screen before the enrichment process and to the patterns which existed in the video image. The present invention attempts several different correlations, counting the number of zeros produced 1 by each correlatlon, and utilizes the correlation whlch produces the richest mlxture of zeros. The zero enriched display is then encoded and repetitive encoded combinations are recognized and assigned special codes to further compress S the data.
The present invention was disclosed under the Patent and Trademark Office's document disclosure program on August 7, 1986 through su~mission of computer program code and a statement describing the invention.
Referring now to Figure 1, a method for compressing data utilized by the preferred of the present invention is disclosed. The method first performs several prelim~nary tests, block 1, on each row input. These tests will be described in more detail in con~unction with Figure 5. The tests include testing lf a row is all zeros or if the row is all ones, etc. If any of the preliminary conditions are satisfied, branch 2, a code is stored and the next row ls accepted as input. If none of the preliminary conditions are satisfied, branch 3, several methods are tried to zero enrich the data, block 4. This will be discussed in more detai~ in connection with Figure 6. Next, the zero enriched row is encoded, block 5. A test is then done to determine lf the packed data uses less space than the unpacked information.
If it doesn't, branch 7, the unpacked information is stored, block 9. lf it does, branch 8, the packed informatlon is stored, block 10. The next row of data from the bit-mapped graphics dlsplay ls then sub~ected to the same process.
l Figure 2(a) illustrates an example of data which may be stored using the present invention. It will be obvious to one skilled in the art that the present invention is capable of handling any data displayed on a bit-mapped graph~cs display with varying degrees of effectiveness. Figure 2~a) illustrates a black rectangle 21 being displayed on a vldeo display. One method of compressing the data on Figure 2(a) is to Exclusively OR each row with the row above it.
The result is shown by Figure 2~b). Using an Exclusive OR process on each row of data on the display yields two lines; line 23 and line 24. Line 23 is in the same row as the top of the rectangle 21 of Figure 2(a). Line 24 is one row below the bottom of the rectangle 21.
Figure 2(c) illustrates the result of using a similar Exclusive OR process on the two lines 23 and 24 from Figure 2(b). Here the Exclusive OR process has occurred on vertical lines across the display, Exclusive ORing each vertical line with the vertical line to its left. The result is four pixels left black 26, 27, 28 and 29. Two of the pixels 26 and 29 are the left most pixels of the rows 23 and 24. The other two pixels 27 and 28, are in the vertical line adjacent to the right most pixels of lines 23 and 24. These Figures, 2~a), 2(b) and 2(c) are illustrative of the method used by the present invention for zero enriching bit-mapped data.
However, it will be seen that the preferred embodiment utilizes several variations on this method to optimize both storage and retrieval of the data.
1 33~0 1 5 .
1 The preferred embodiment of the present invention utilizes a set of 1-byte (8-bit) codes for compressing the data. These codes are further illustrated in connection with Figure 3. The codes can be broken down into five ma~or types, normal runs 31, miscellaneous codes 32, repeat codes 33, big data 34, and big zero 35. The normal run codes 31 utilize hexadecimal values 00-7F. The format of a normal run code in the preferred embodiment of the present invention is Odddzzzz, where ddd is a count of data bytes which follow this code byte and zzzz is a count of zeros between O and 15.
For example, a string of data consisting of eight zeros followed by 2 bytes of data, one being represented by hexadecimal FF or all black and the second byte being represented by AA or being gray may be encoded as hexadecimal 28 FF AA. Thus, four bytes of data have been compressed to three bytes of data.
.
A number of miscellaneous codes are utilized by the present invention for storing information about rows which have met the preliminary conditions discussed in con~unction with Figure 1 and Figure 5 and for storing information regarding which method yielded the optimum zero enriched row of data. The preferred embodiment of the present invention utilizes hexadecimal values 80-9F as indicated below for miscellaneous codes.
1 3 7 6 ~ 1 ~
.., MISCF.T.T.~NF.OUS CODFS
; DF SCRI PT I ON
$80 COULD NOT PACK
S81 ROW ALL ZE~OS
$82 ROW ALL ONS
$86 DUPLICATE 2 LINES ABOVE
$87 UNUSED
$88 dh, dv = 16, 0 $89 dh, dv = O, O
$8A dh, dv = O, 1 $8B dh, dv = O, 2 $8C dh, dv = 1, 0 $8D dh, dv = 1, 1 $8E dh, dv = 2, 2 $8F dh, dv = 8, 0 $90-9F UNUSED
Hexadecimal code ~0 indicates that data could not be packed without using more space than the original data. The unpacked data follows the code. Hexadecimal code 81 indicates the row consisted of all zeros. Hexadecimal code 82 indicates the row consisted of all ones. Hexadecimal code 83 indicates the row consisted of bytes of data which repeated. In this case, the code is followed with a single byte of data indicating the byte of data which repeats.
Hexadecimal 84 indicates this row repeats the same byte of data that was repeated in the previous row. Hexadecimal code 85 indicates this row is a duplicate of the row immediately above it. Hexadecimal 86 indicates this row is a duplicate of the row two rows above it. Hexadecimal 87 is currently not used in the preferred embodiment. Hexadecimal 88 through 8F indicate which of various horizontal deltas (dh) and vertical deltas ~dv) were utilized to yie~d the optimum zero 1 3~601~.~
1 - enriched row. In the preferred embodiment, hexadecimal codes 90 through 9F are currently not used.
Each of these miscellaneous codes 80 through 9F are utilized only when analyzing a row at the beginning of the row. Therefore, these codes are unused when storing data within a row a~d may be utilized for future expansion within a row.
Codes A0 through BF indicate the previous one byte operation code repeats zero to thirty-one times. The format for these codes is lOlnnnnn2 where nnnnn is a value between 10 and 311o. For example, if the previous op code was 81 and a repeat code of A6 is detected, six white lines will be displayed as a result.
Codes C0 through DF indicate a string of data bytes follows. The format of these codes, in binary, is lllddddd, where ddddd is a count of data bytes which follow divided by 8. For example, if a string of sixteen data bytes is to be represented, a code of hexadecimal C2 (16 - 8 = 2) is stored followed by the sixteen data bytes.
Codes E0 through FF indicate a string of zeros exist in the data. The format of this code is lllzzzzz, where zzzzz is a count of zeros divided by 16. For example, if a string of 160 zeros was found in a row of data a code of hexadecimal CA (160 - 16 = l01o or A16)is stored.
1 33 6 0 1 ~
l _ Figures 4~a) through 4~c) are illustrative of this method of encoding data. In Figure 4(a) a set of rows of data as may be compressed by the present invention is shown.
The data consists of a row of all zeros 41 followed by four rows 42 which would display as a blackened rectangle and another row of all zeros 43. The first row 41 may be represented with the code 81 for a row consisting of all zeros. Row 2 may be shifted l-bit to the right and exclusive OR'd with itself. This is shown in Figure 4(b). Row 2 44 is Exclusive OR'd with a copy of itself shifted l-bit to the right, row 45, yielding a result 46. This row is optimized in zeros. An operati~on code 8C is stored by the preferred embodiment of the present invention to indicate a delta of shifting horizontally right 1-bit and vertically 0-bits when performing the Exclusive OR process. Rows 3, 4, and 5 may be represented by code 85 indicating they are duplicates of the lines immediately above them. Row 6 may be represented by code 81 indicating it is all zeros. Figure 4(c) illustrates rows 1-6 and the resulting codes 50.
Referring to Figure 5, a flow chart illustrating the preliminary tests performed by the preferred embodiment of the present invention when compressing data is shown. A row is first tested to determine if it is all white or zeros and, if it is, branch 55 is taken and the code indicating it is all white is recorded.
Next, a test is performed to determine if the row is all black or ones and, if it is, branch 56 is taken and a code indicating it is all black is recorded.
1 3360 7 ~
1 Next, a test is done to determine if the row repeats the same byte of data across the entire row. If it does, branch 57 is taken. If branch 57 is taken, a test is done to see if the row repeats the same byte repeated by the previous row and, if so, branch 54 is taken and a code is stored indicating it repeats the same code. Otherwise a code is stored indicating it repeats a byte and that byte is stored.
~ext, a check is done to determine if the row matches the row previous to it and, if so, branch 58 is taken and a code is stored indicating the row is a duplicate of the row above it.
Next, a test is done to determine if the row matches the row two rows previous to it and, if it does, branch S9 is taken and a code is stored indicating the row ~atches the row two lines previous to it.
As previously discussed in connection with Figure 1, lf none of these preliminary conditions are satisfied a determination is made which of several methods of shifting and Exclusive ORing rows of data will produce a row which is optimized in zeros. Referring now to Figure 6, a flow chart for a process for determining an optimum zero enriched method as utilized by the preferred embodiment of the present invention is shown. This method consists of first initializing several variables including setting a variable, called bestcount, to the number of non-zero words in the current row, block 60. A determination is then made of ~ 3360 1 5 1 nonequal words between the current row and the immediately previous row, block 61. I~ this count of nonequal words is less than bestcount branch 62 is taken and zero is stored as the best horizontal delta, one is stored as the best vertical delta and the count is stored as bestcount. In other words, should this be the optimum method, the Exclusive OR process will be done using the row immediately preceding the current row and the current row as inputs without shiftinq the current row to the right. A check is then done to see if bestcount is less than a threshold value, the threshold value being computed as 2 plus the word count of the row buffer divided by 8. If bestcount is less than the threshold value, it is assumed that this is the optimum method for zero enriching this row of data. Otherwise, branch 75 is taken.
If either 63 or branch 75 is taken, the next step is to determine the count of nonequal words between the current row and the row two rows previous, block 64. If this count is less than bestcount, branch 65 is taken and 0 is stored as bestdh and 2 is stored as bestdv. The count is then stored as bestcount, block 76. If bestcount is less than the threshold value, branch 77 is taken and it is assumed that the optimum zero enriched method is using the row two rows above the current row and the current row as inputs to an Exclusive OR. Otherwise, branch 78 is taken.
If branch 66 or branch 78 is taken, a loop is performed to determine which of several vertical and horizontal delta combinations will yield the optimum zero enriched method. In the preferred embodiment of the present invention these 1 _ combinations include a horizontal delta of 1 with a vertlcal delta of O , in other words shifting the current row to the right one bit and using the shifted row and the current row as inputs to an Exclusive OR, a horizontal delta of 1 and a vertical delta of 1, a horizontal delta of 2 and a vertlcal delta of 2, a horizontal delta of 8 and a vertical delta of O
and a horizontal delta of 16 and a vertical of 0. For each of these combinations a count of non-zero words is determined, block 67. If this count is less than bestcount, branch 69, that combination is stored as the best~dh and bestdv. If the count is not less than bestcount, branch 70 the next dh, dv combination is attempted, branch 71. If there are no more dht dv combinations it is assumed that the currently stored bestdh and bestdv are the optimum for zero enriching this row.
~ igure 7 is a flow chart showing a process used for decoding the compressed video information as may be utilized by the present invention. First, several variables are initialized, block 81. This includes initializing a variable named repeatcount to 0. Next a loop is entered which is executed for each code stored for the video image. The first step is to determine if count repeat is greater than O and if it is, branch 82 the operation code is set to the previous operation code, i.e., the operation code is repeated and repeatcount is decremented, block 84. If repeatcount is equal to 0, branch 83, the next operation code is read, block 85. A check is then made to determine if this operation code indicates the beginning of a row of data. If it does not, branch 86, the row information is unpacked, block 88.
1 3 J ~ O 1 ~
1 If the code indicates this is the beginning of a row, branch 87 is taken. A test is done to determine if the operation code is a repeat operation code. If it is, branch 89, the repeatcount is set to the repeatcount of the repeat operation code and the next operation code is stored as the operation code to be repeated, bloc~ 91.
If the operation code does not equal the repeat operation code, branch 90 is taken and the processing of a beginning of row operation code is done, block 92. The processing of a beginning of row operation code will be more fully explained in conjunction with Figures 8 and 9. The data is then put into a buffer, block 93. A test is done to determine whether there are more operation codes to process.
If there are, branch 94 is taken. Otherwise, branch 9S is taken.
The processing of a beginning of row operation code as performed by the preferred embodiment of the present invention, is shown in Figure 8. The first step in processing a beginning of row ope~ation code is to test for a code that indicates the data is not compressed. If the data is not compressed, branch 101, the uncompressed data is copied into a buffer, block 110.
If the data is compressed, a test is done to determine if the operation code indicates the row should be filled with zeros (i.e., the row is white). If the row is to be filled with zeros, branch 102, an operation is done to fill the row 1 3 ~ 6 0 1 5 1 with zeros, block 111. Otherwise, a test is done to determine if the row should be filled with ones (i.e., the row is black). If so, branch 103 is taken and the row ls filled with ones, block 112.
s Otherwise, a check is done to determine if the code indicates a byte of data is repeated across the row. If so, branch 104 is taken and the gi~en byte of data is read and duplicated across the row, block 113. Next, a test is done to determine if the operation code indicates the byte of data repeated across the previous row should be repeated across this row. If so, branch 105 is taken and the byte of data is replicated across the row, block 114.
Otherwise, a test is done to determine if the current row is a duplicate of the row immediately above it and if so, branch 106 is taken. A copy of the immediately previous row is then made, block 115. Finally, a test is done to determine if the code indicates the row is an exact duplicate of the second row above it and, if so, branch 107 is taken.
In this case the second row above the current row is copied, block 116.
If all of the above tests fail, a series of tests are performed to determine what horizontal delta and vertical delta should be used in the shifting and Exclusive ORing process for this row, block 117.
After the current horizontal delta and the current vertical delta are set, the shifting and Exclusive ORing - ~ 3~01 5 1 process is executed. The first step is to determine the appropriate horizontal delta for the row of data and shift a copy of the row the delta number of bytes to the left. An Exclusive OR process is then performed using the shifted copy of the row and the original current row of data as inputs.
Next, tests are done to determine whether the resulting row should be Exclusive OR'd with either the immediately previous row or the row two rows previous.
Referring now to Figure 9, the preferred embodiment of the present invention f~rst checks to see if the horizontal delta for the current row is a l. If so branch 121 is taken.
A table is used by the preferred embodiment of the present invention, to tr~nslate the stored row of data into the row of data to be displayed. Use of the table increases the speed of processing the data. The table consists of the translated values for each possible encoded value. For example, ln the table at a relative offset of 14loa value lllo appears. This is because the value l11o (10112) shifted right one position (01012) used as input to an Exclusive OR
function with the other input being lllo yields as a result 141o (10112 XOR 10102 - 11102). Therefore, the encoded row will have a 141o translated back to an lllo using this table.
The table contains similar translation values at the appropriate offset addresses for other input values.
If the horizontal delta is a 2 ,branch 124 is taken and a similar table is used to obtain the translated codes, block 123. If the horizontal delta is equal to 8, branch 125 is taken and the row is shifted 8 bytes and subjected to an Exclusive OR process to obtain the original data. Finally, if the horizontal delta is equal to 16, branch 127 is taken and the row is shifted 16 bytes and subjected to an Exclusive OR process, block 128.
After processing the horizontal deltas a check is done to determine whether the vertical delta is equal to a one. If so, branch 130 is used. The current row and the row immediately previous are used as inputs to an Exclusive OR process to obtain the original value for the current row, block 131. Otherwise, a check is done to determine if the vertical delta is equal to a 2. If so, branch 132 is taken and the current row is Exclusive OR'd with two rows previous, the result being the original value for this row, block 133.
Thus, a method for compressing and decoding information, or more particularly video data from a bit-mapped graphics display, is disclosed.
It will be understood that, although various features of the invention have been described with respect to one or another of the embodiments of the invention, the various features and embodiments of the invention may be combined or used in conjunction with other features and embodiments of the invention as described and illustrated.
:
, ,~;;.
Numerous methods are known for compression of data in computer systems and for compression of data for video displays or bit-mapped graphic displays. However, each of these methods suffers from one or more of several disadvantages. A method is desired which allows data to be stored in a compacted form after it is received from a bit-mapped graphics display or other similar device. The data should be stored in a manner which enables it to be decoded with a minimum of resources being used in the decoding process. ln addition, the data should be stored in as compact of form as possible.
~ 3~6~1 5 SUMMARY OF THF. I~VF.NT~ON
A method of compressing video information from a bit-mapped graphics display or similar device is disclosed. The method reduces the number of bits which must be physically stored in order to store a video image. The main steps of the algorithm are enriching a bit-map of the video image in zeros and encoding the enriched image into runs of zeros and data bytes.
The enriching of the video image in zeros is done by performing an auto correlation (shifting and Exclusive ORing) for horizontal and vertical lines. The number of zeros resulting from each correlation is counted until it is d~termined which combination produces the richest zeros.
The bit-map of zero enriched lines is then encoded into runs of zeros and data bytes. Special cases, such as a row being all zeros or a row being all ones, are recognized and assigned a special code. In addition, special codes are assigned in the case of zero matching the row immediately prior to it or the row two rows prior to it. Special codes are also assigned to indicate that a code is repeated a number of times. Other uses of special codes will be seen in the detailed description of the present invention.
A method of reconstructing the compressed data ls also disclosed. This method reads the encoded data and recreates the uncompressed data. Various methods are included for ~' 1 3 ~ 6 G ~ ~
optimizing the speed of this process including the use of a table for decoding certain encoded data.
Accordingly, in one of its aspects, the present invention relates to a method of compressing information comprising the steps of:
enriching a bit-map of said information in a first binary state;
encoding said enriched bit-map;
whereby, said information is compressed.
Further aspects of the invention reside in providing a method of compressing information comprising the step of 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 words of data in said second row of data which are in said first binary state;
(v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
1 376~ ~ ~
(vi) performing a logical operation using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(vii) determining the number of words of data in said fourth row of data which are in said first binary state;
(viii) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (ix) repeating steps (vi) through (viii) for each of a second set of predetermined numbers.
In a further aspect, the present invention relates to 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 an Exclusive OR 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 words of data in said second row of data which are in said first binary state, and (v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(b) encoding said enriched bit-map;
(c) performing an Exclusive OR function using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(d) determining the number of words of data in said fourth row of data which are in said first binary state;
(e) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (f) repeating steps (c) through (e) for each of a second set of predetermined numbers.
In a still further aspect, the present invention relates to 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 B ~
... ...
~ 33 6~ 1 ~
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, and (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.
In another aspect, the present invention relates to 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; and deco~ing said information by reading a plurality of operation codes and reconstructing said bit-map from said operation codes.
, ~ J ~\~i ri 1 5 -In a further aspect, the present invention relates to a method of decompressing information comprising the step of:
(a) reading an operation code; and (b) if said operation code indicates the beginning of a first row of data, processing said operation code by:
(i) if said operation code indicates said first row of data is not compressed, copying said data, (ii) if said operation code indicates said first row of data is comprised of bits all of a first binary state, filling said first row with bits of said first binary state, (iii) if said operation code indicates said first row of data is comprised of bits all of a second binary state, filling said first row with bits of said second binary state, (iv) if said operation code indicates said first row of data repeats a block of data, filling said first row with duplicates of said block of data, and (v) if said operation code indicates said first row of data is identical to a second row of data, copying said second row.
. ..
-- RRTF.F nF.SCRIPTION OF THF. r)RA~INGS
Figure 1 is a flow chart describing steps involved in encoding video data as may be utilized by the present invention.
Figure 2(a) illustrates a display device with a blackened square in the center as may be compressed by the present invention.
Figure 2(b) illustrates the blackened square display after a first step of the compression as may be accomplished by the present invention.
Figure 2(c) illustrates the blackened square display after a second step of compression as may be accomplished by the present invention.
Figure 3 illustrates an address space of operation codes as may be utilized by the present invention.
Figure 4(a) illustrates rows of data as may be compressed by the present invention.
Figure 4(b) illustrates a step of Exclusive ORing to rows of data as may be accomplished by the present invention during compression of the data.
1 3 J ~S ~0 1 5 1 ~~ Figure 4(c) illustrates rows of data and associated compression codes as may be utilized by the present invention.
Figure 5 is a flow chart illustrating preliminary tests to be performed on rows of data during encoding as may be accomplished by the present invention.
Figure 6 is a flow chart illustrating a method of determining an optimum zero enriched method as may be utilized by the present invention.
Figure 7 is a flow chart illustrating a method of reconstructing video data from compressed data as may be utilized by the present invention.
.
Figure 8 is a flow chart illustrating a method of processing a beginning of row operation code as may be utilized by the present invention.
Figure 9 is a flow chart illustrating a process of decoding rows encoded by shifting and Exclusive ORing as may be utilized by the present invention.
1 3JG~1 5 1 D~TAITF~n nFSCRIPTION OF TH~ PRFS~T INVFNTION
A method of compressing and reconstructing video data ls described. In the following description, numerous speciflc details are set forth such as operation codes, speciflc steps, etc., in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well known structures and techniques have not been shown in detail in order not to unnecessarily obscure the present invention.
The present invention comprises a method of compressing video information, typically from a bit-mapped display or similar dev$ce and a method of reconstructing the compressed .
video information to allow redisplay of the data. The invention is based on the observation that a typical bit-mapped video image comprises a majority of either "white~
areas or patterns of data. A purely random pattern of white and dark areas on a bit-mapped video display is rare.
Therefore, the present invention takes advantage of these observations by further enriching a bit-map of a video image in zeros by performing an auto correlation of vertical and horizontal lines. The enrichment in zeros is due to the large amount of "white space" on the screen before the enrichment process and to the patterns which existed in the video image. The present invention attempts several different correlations, counting the number of zeros produced 1 by each correlatlon, and utilizes the correlation whlch produces the richest mlxture of zeros. The zero enriched display is then encoded and repetitive encoded combinations are recognized and assigned special codes to further compress S the data.
The present invention was disclosed under the Patent and Trademark Office's document disclosure program on August 7, 1986 through su~mission of computer program code and a statement describing the invention.
Referring now to Figure 1, a method for compressing data utilized by the preferred of the present invention is disclosed. The method first performs several prelim~nary tests, block 1, on each row input. These tests will be described in more detail in con~unction with Figure 5. The tests include testing lf a row is all zeros or if the row is all ones, etc. If any of the preliminary conditions are satisfied, branch 2, a code is stored and the next row ls accepted as input. If none of the preliminary conditions are satisfied, branch 3, several methods are tried to zero enrich the data, block 4. This will be discussed in more detai~ in connection with Figure 6. Next, the zero enriched row is encoded, block 5. A test is then done to determine lf the packed data uses less space than the unpacked information.
If it doesn't, branch 7, the unpacked information is stored, block 9. lf it does, branch 8, the packed informatlon is stored, block 10. The next row of data from the bit-mapped graphics dlsplay ls then sub~ected to the same process.
l Figure 2(a) illustrates an example of data which may be stored using the present invention. It will be obvious to one skilled in the art that the present invention is capable of handling any data displayed on a bit-mapped graph~cs display with varying degrees of effectiveness. Figure 2~a) illustrates a black rectangle 21 being displayed on a vldeo display. One method of compressing the data on Figure 2(a) is to Exclusively OR each row with the row above it.
The result is shown by Figure 2~b). Using an Exclusive OR process on each row of data on the display yields two lines; line 23 and line 24. Line 23 is in the same row as the top of the rectangle 21 of Figure 2(a). Line 24 is one row below the bottom of the rectangle 21.
Figure 2(c) illustrates the result of using a similar Exclusive OR process on the two lines 23 and 24 from Figure 2(b). Here the Exclusive OR process has occurred on vertical lines across the display, Exclusive ORing each vertical line with the vertical line to its left. The result is four pixels left black 26, 27, 28 and 29. Two of the pixels 26 and 29 are the left most pixels of the rows 23 and 24. The other two pixels 27 and 28, are in the vertical line adjacent to the right most pixels of lines 23 and 24. These Figures, 2~a), 2(b) and 2(c) are illustrative of the method used by the present invention for zero enriching bit-mapped data.
However, it will be seen that the preferred embodiment utilizes several variations on this method to optimize both storage and retrieval of the data.
1 33~0 1 5 .
1 The preferred embodiment of the present invention utilizes a set of 1-byte (8-bit) codes for compressing the data. These codes are further illustrated in connection with Figure 3. The codes can be broken down into five ma~or types, normal runs 31, miscellaneous codes 32, repeat codes 33, big data 34, and big zero 35. The normal run codes 31 utilize hexadecimal values 00-7F. The format of a normal run code in the preferred embodiment of the present invention is Odddzzzz, where ddd is a count of data bytes which follow this code byte and zzzz is a count of zeros between O and 15.
For example, a string of data consisting of eight zeros followed by 2 bytes of data, one being represented by hexadecimal FF or all black and the second byte being represented by AA or being gray may be encoded as hexadecimal 28 FF AA. Thus, four bytes of data have been compressed to three bytes of data.
.
A number of miscellaneous codes are utilized by the present invention for storing information about rows which have met the preliminary conditions discussed in con~unction with Figure 1 and Figure 5 and for storing information regarding which method yielded the optimum zero enriched row of data. The preferred embodiment of the present invention utilizes hexadecimal values 80-9F as indicated below for miscellaneous codes.
1 3 7 6 ~ 1 ~
.., MISCF.T.T.~NF.OUS CODFS
; DF SCRI PT I ON
$80 COULD NOT PACK
S81 ROW ALL ZE~OS
$82 ROW ALL ONS
$86 DUPLICATE 2 LINES ABOVE
$87 UNUSED
$88 dh, dv = 16, 0 $89 dh, dv = O, O
$8A dh, dv = O, 1 $8B dh, dv = O, 2 $8C dh, dv = 1, 0 $8D dh, dv = 1, 1 $8E dh, dv = 2, 2 $8F dh, dv = 8, 0 $90-9F UNUSED
Hexadecimal code ~0 indicates that data could not be packed without using more space than the original data. The unpacked data follows the code. Hexadecimal code 81 indicates the row consisted of all zeros. Hexadecimal code 82 indicates the row consisted of all ones. Hexadecimal code 83 indicates the row consisted of bytes of data which repeated. In this case, the code is followed with a single byte of data indicating the byte of data which repeats.
Hexadecimal 84 indicates this row repeats the same byte of data that was repeated in the previous row. Hexadecimal code 85 indicates this row is a duplicate of the row immediately above it. Hexadecimal 86 indicates this row is a duplicate of the row two rows above it. Hexadecimal 87 is currently not used in the preferred embodiment. Hexadecimal 88 through 8F indicate which of various horizontal deltas (dh) and vertical deltas ~dv) were utilized to yie~d the optimum zero 1 3~601~.~
1 - enriched row. In the preferred embodiment, hexadecimal codes 90 through 9F are currently not used.
Each of these miscellaneous codes 80 through 9F are utilized only when analyzing a row at the beginning of the row. Therefore, these codes are unused when storing data within a row a~d may be utilized for future expansion within a row.
Codes A0 through BF indicate the previous one byte operation code repeats zero to thirty-one times. The format for these codes is lOlnnnnn2 where nnnnn is a value between 10 and 311o. For example, if the previous op code was 81 and a repeat code of A6 is detected, six white lines will be displayed as a result.
Codes C0 through DF indicate a string of data bytes follows. The format of these codes, in binary, is lllddddd, where ddddd is a count of data bytes which follow divided by 8. For example, if a string of sixteen data bytes is to be represented, a code of hexadecimal C2 (16 - 8 = 2) is stored followed by the sixteen data bytes.
Codes E0 through FF indicate a string of zeros exist in the data. The format of this code is lllzzzzz, where zzzzz is a count of zeros divided by 16. For example, if a string of 160 zeros was found in a row of data a code of hexadecimal CA (160 - 16 = l01o or A16)is stored.
1 33 6 0 1 ~
l _ Figures 4~a) through 4~c) are illustrative of this method of encoding data. In Figure 4(a) a set of rows of data as may be compressed by the present invention is shown.
The data consists of a row of all zeros 41 followed by four rows 42 which would display as a blackened rectangle and another row of all zeros 43. The first row 41 may be represented with the code 81 for a row consisting of all zeros. Row 2 may be shifted l-bit to the right and exclusive OR'd with itself. This is shown in Figure 4(b). Row 2 44 is Exclusive OR'd with a copy of itself shifted l-bit to the right, row 45, yielding a result 46. This row is optimized in zeros. An operati~on code 8C is stored by the preferred embodiment of the present invention to indicate a delta of shifting horizontally right 1-bit and vertically 0-bits when performing the Exclusive OR process. Rows 3, 4, and 5 may be represented by code 85 indicating they are duplicates of the lines immediately above them. Row 6 may be represented by code 81 indicating it is all zeros. Figure 4(c) illustrates rows 1-6 and the resulting codes 50.
Referring to Figure 5, a flow chart illustrating the preliminary tests performed by the preferred embodiment of the present invention when compressing data is shown. A row is first tested to determine if it is all white or zeros and, if it is, branch 55 is taken and the code indicating it is all white is recorded.
Next, a test is performed to determine if the row is all black or ones and, if it is, branch 56 is taken and a code indicating it is all black is recorded.
1 3360 7 ~
1 Next, a test is done to determine if the row repeats the same byte of data across the entire row. If it does, branch 57 is taken. If branch 57 is taken, a test is done to see if the row repeats the same byte repeated by the previous row and, if so, branch 54 is taken and a code is stored indicating it repeats the same code. Otherwise a code is stored indicating it repeats a byte and that byte is stored.
~ext, a check is done to determine if the row matches the row previous to it and, if so, branch 58 is taken and a code is stored indicating the row is a duplicate of the row above it.
Next, a test is done to determine if the row matches the row two rows previous to it and, if it does, branch S9 is taken and a code is stored indicating the row ~atches the row two lines previous to it.
As previously discussed in connection with Figure 1, lf none of these preliminary conditions are satisfied a determination is made which of several methods of shifting and Exclusive ORing rows of data will produce a row which is optimized in zeros. Referring now to Figure 6, a flow chart for a process for determining an optimum zero enriched method as utilized by the preferred embodiment of the present invention is shown. This method consists of first initializing several variables including setting a variable, called bestcount, to the number of non-zero words in the current row, block 60. A determination is then made of ~ 3360 1 5 1 nonequal words between the current row and the immediately previous row, block 61. I~ this count of nonequal words is less than bestcount branch 62 is taken and zero is stored as the best horizontal delta, one is stored as the best vertical delta and the count is stored as bestcount. In other words, should this be the optimum method, the Exclusive OR process will be done using the row immediately preceding the current row and the current row as inputs without shiftinq the current row to the right. A check is then done to see if bestcount is less than a threshold value, the threshold value being computed as 2 plus the word count of the row buffer divided by 8. If bestcount is less than the threshold value, it is assumed that this is the optimum method for zero enriching this row of data. Otherwise, branch 75 is taken.
If either 63 or branch 75 is taken, the next step is to determine the count of nonequal words between the current row and the row two rows previous, block 64. If this count is less than bestcount, branch 65 is taken and 0 is stored as bestdh and 2 is stored as bestdv. The count is then stored as bestcount, block 76. If bestcount is less than the threshold value, branch 77 is taken and it is assumed that the optimum zero enriched method is using the row two rows above the current row and the current row as inputs to an Exclusive OR. Otherwise, branch 78 is taken.
If branch 66 or branch 78 is taken, a loop is performed to determine which of several vertical and horizontal delta combinations will yield the optimum zero enriched method. In the preferred embodiment of the present invention these 1 _ combinations include a horizontal delta of 1 with a vertlcal delta of O , in other words shifting the current row to the right one bit and using the shifted row and the current row as inputs to an Exclusive OR, a horizontal delta of 1 and a vertical delta of 1, a horizontal delta of 2 and a vertlcal delta of 2, a horizontal delta of 8 and a vertical delta of O
and a horizontal delta of 16 and a vertical of 0. For each of these combinations a count of non-zero words is determined, block 67. If this count is less than bestcount, branch 69, that combination is stored as the best~dh and bestdv. If the count is not less than bestcount, branch 70 the next dh, dv combination is attempted, branch 71. If there are no more dht dv combinations it is assumed that the currently stored bestdh and bestdv are the optimum for zero enriching this row.
~ igure 7 is a flow chart showing a process used for decoding the compressed video information as may be utilized by the present invention. First, several variables are initialized, block 81. This includes initializing a variable named repeatcount to 0. Next a loop is entered which is executed for each code stored for the video image. The first step is to determine if count repeat is greater than O and if it is, branch 82 the operation code is set to the previous operation code, i.e., the operation code is repeated and repeatcount is decremented, block 84. If repeatcount is equal to 0, branch 83, the next operation code is read, block 85. A check is then made to determine if this operation code indicates the beginning of a row of data. If it does not, branch 86, the row information is unpacked, block 88.
1 3 J ~ O 1 ~
1 If the code indicates this is the beginning of a row, branch 87 is taken. A test is done to determine if the operation code is a repeat operation code. If it is, branch 89, the repeatcount is set to the repeatcount of the repeat operation code and the next operation code is stored as the operation code to be repeated, bloc~ 91.
If the operation code does not equal the repeat operation code, branch 90 is taken and the processing of a beginning of row operation code is done, block 92. The processing of a beginning of row operation code will be more fully explained in conjunction with Figures 8 and 9. The data is then put into a buffer, block 93. A test is done to determine whether there are more operation codes to process.
If there are, branch 94 is taken. Otherwise, branch 9S is taken.
The processing of a beginning of row operation code as performed by the preferred embodiment of the present invention, is shown in Figure 8. The first step in processing a beginning of row ope~ation code is to test for a code that indicates the data is not compressed. If the data is not compressed, branch 101, the uncompressed data is copied into a buffer, block 110.
If the data is compressed, a test is done to determine if the operation code indicates the row should be filled with zeros (i.e., the row is white). If the row is to be filled with zeros, branch 102, an operation is done to fill the row 1 3 ~ 6 0 1 5 1 with zeros, block 111. Otherwise, a test is done to determine if the row should be filled with ones (i.e., the row is black). If so, branch 103 is taken and the row ls filled with ones, block 112.
s Otherwise, a check is done to determine if the code indicates a byte of data is repeated across the row. If so, branch 104 is taken and the gi~en byte of data is read and duplicated across the row, block 113. Next, a test is done to determine if the operation code indicates the byte of data repeated across the previous row should be repeated across this row. If so, branch 105 is taken and the byte of data is replicated across the row, block 114.
Otherwise, a test is done to determine if the current row is a duplicate of the row immediately above it and if so, branch 106 is taken. A copy of the immediately previous row is then made, block 115. Finally, a test is done to determine if the code indicates the row is an exact duplicate of the second row above it and, if so, branch 107 is taken.
In this case the second row above the current row is copied, block 116.
If all of the above tests fail, a series of tests are performed to determine what horizontal delta and vertical delta should be used in the shifting and Exclusive ORing process for this row, block 117.
After the current horizontal delta and the current vertical delta are set, the shifting and Exclusive ORing - ~ 3~01 5 1 process is executed. The first step is to determine the appropriate horizontal delta for the row of data and shift a copy of the row the delta number of bytes to the left. An Exclusive OR process is then performed using the shifted copy of the row and the original current row of data as inputs.
Next, tests are done to determine whether the resulting row should be Exclusive OR'd with either the immediately previous row or the row two rows previous.
Referring now to Figure 9, the preferred embodiment of the present invention f~rst checks to see if the horizontal delta for the current row is a l. If so branch 121 is taken.
A table is used by the preferred embodiment of the present invention, to tr~nslate the stored row of data into the row of data to be displayed. Use of the table increases the speed of processing the data. The table consists of the translated values for each possible encoded value. For example, ln the table at a relative offset of 14loa value lllo appears. This is because the value l11o (10112) shifted right one position (01012) used as input to an Exclusive OR
function with the other input being lllo yields as a result 141o (10112 XOR 10102 - 11102). Therefore, the encoded row will have a 141o translated back to an lllo using this table.
The table contains similar translation values at the appropriate offset addresses for other input values.
If the horizontal delta is a 2 ,branch 124 is taken and a similar table is used to obtain the translated codes, block 123. If the horizontal delta is equal to 8, branch 125 is taken and the row is shifted 8 bytes and subjected to an Exclusive OR process to obtain the original data. Finally, if the horizontal delta is equal to 16, branch 127 is taken and the row is shifted 16 bytes and subjected to an Exclusive OR process, block 128.
After processing the horizontal deltas a check is done to determine whether the vertical delta is equal to a one. If so, branch 130 is used. The current row and the row immediately previous are used as inputs to an Exclusive OR process to obtain the original value for the current row, block 131. Otherwise, a check is done to determine if the vertical delta is equal to a 2. If so, branch 132 is taken and the current row is Exclusive OR'd with two rows previous, the result being the original value for this row, block 133.
Thus, a method for compressing and decoding information, or more particularly video data from a bit-mapped graphics display, is disclosed.
It will be understood that, although various features of the invention have been described with respect to one or another of the embodiments of the invention, the various features and embodiments of the invention may be combined or used in conjunction with other features and embodiments of the invention as described and illustrated.
:
, ,~;;.
3 ~ 6 0 ~ ~
Although this disclosure has described and illustrated certain preferred embodiments of the invention, it is to be understood that the invention is not restricted to these particular embodiments. Rather, the invention includes all embodiments which are functional or mechanical equivalents of the specific embodiments and features that have been described and illustrated herein.
~ ~ s ~
Although this disclosure has described and illustrated certain preferred embodiments of the invention, it is to be understood that the invention is not restricted to these particular embodiments. Rather, the invention includes all embodiments which are functional or mechanical equivalents of the specific embodiments and features that have been described and illustrated herein.
~ ~ s ~
Claims (26)
1. A method of compressing information comprising the step of 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 words of data in said second row of data which are in said first binary state;
(v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(vi) performing a logical operation using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(vii) determining the number of words of data in said fourth row of data which are in said first binary state;
(viii) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (ix) repeating steps (vi) through (viii) for each of a set of predetermined numbers.
(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 words of data in said second row of data which are in said first binary state;
(v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(vi) performing a logical operation using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(vii) determining the number of words of data in said fourth row of data which are in said first binary state;
(viii) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (ix) repeating steps (vi) through (viii) for each of a set of predetermined numbers.
2. The method as recited in Claim 1, wherein said set of predetermined numbers comprises zero, one and two.
3. 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 an Exclusive OR 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 words of data in said second row of data which are in said first binary state, and (v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(b) encoding said enriched bit-map;
(c) performing an Exclusive OR function using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(d) determining the number of words of data in said fourth row of data which are in said first binary state;
(e) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (f) repeating steps (c) through (e) for each of a set of predetermined numbers.
(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 an Exclusive OR 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 words of data in said second row of data which are in said first binary state, and (v) if said number of words in said binary state is greater than a first value, storing said number of words as said first value and storing said predetermined number as a second value;
(b) encoding said enriched bit-map;
(c) performing an Exclusive OR function using as input said first row of data and a third row of data, said third row of data offset a predetermined number of rows from said first row of data, yielding a fourth row of data;
(d) determining the number of words of data in said fourth row of data which are in said first binary state;
(e) if said number of words in said first binary state are greater than a third value, storing said number of words as said third value and storing said predetermined number as a fourth value; and (f) repeating steps (c) through (e) for each of a set of predetermined numbers.
4. The method as recited in Claim 3, wherein said set of predetermined numbers comprises zero, one and two.
5. The method as recited in Claim 3, further comprising the step of decoding said encoded information by:
(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 indicates the beginning of said first row of data, processing said operation code by the steps of:
(i) if said operation code indicates the data is not compressed, copying the uncompressed data, (ii) 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, (iii) 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, (iv) if said operation code indicates the data repeats a block of data, filling said first row with duplicates of said block of data, and (v) 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; and (d) otherwise, unpacking said first row of data.
(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 indicates the beginning of said first row of data, processing said operation code by the steps of:
(i) if said operation code indicates the data is not compressed, copying the uncompressed data, (ii) 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, (iii) 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, (iv) if said operation code indicates the data repeats a block of data, filling said first row with duplicates of said block of data, and (v) 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; and (d) otherwise, unpacking said first row of data.
6. The method as recited in Claim 5, wherein said unpacking of said data comprises the step of using a table having predetermined values to unpack said data.
7. 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, and (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.
(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, and (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.
8. The method as recited in Claim 7, 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; and if one of said predetermined set of conditions is met, storing one of a first set of predetermined codes.
determining whether a first row of said bit-map meets one of a predetermined set of conditions; and if one of said predetermined set of conditions is met, storing one of a first set of predetermined codes.
9. The method as recited in Claim 8, 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.
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.
10. The method as recited in Claim 7, further comprising the step of decoding said encoded information.
11. The method as recited in Claim 10, 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.
(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.
12. The method as recited in Claim 11, 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; and (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.
(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; and (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.
13. The method as recited in Claim 12, wherein said unpacking of said data comprises the step of using a table having predetermined values to unpack said data.
14. The method as recited in Claim 7, 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.
15. The method as recited in Claim 7, wherein said first binary state is a low state.
16. The method as recited in Claim 7, wherein steps (i) through (v) are repeatedfor each of a first set of predetermined numbers.
17. The method as recited in Claim 7, wherein said logical function is an Exclusive OR function.
18. A method of compressing and reconstructing 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 acopy 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; and decoding said information by reading a plurality of operation codes and reconstructing said bit-map from said operation codes.
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 acopy 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; and decoding said information by reading a plurality of operation codes and reconstructing said bit-map from said operation codes.
19. The method as recited in Claim 18, 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 secondbinary 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.
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 secondbinary 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.
20. The method as recited in Claim 18, wherein said unpacking of said data comprises the step of using a translation table having predetermined values to unpack said data.
21. The method as recited in Claim 19, wherein said first binary state is a low state.
22. The method as recited in Claim 21, wherein said second binary state is a high state.
23. A method of decompressing information comprising the step of:
(a) reading an operation code; and (b) if said operation code indicates the beginning of a first row of data, processing said operation code by:
(i) if said operation code indicates said first row of data is not compressed, copying said data, (ii) if said operation code indicates said first row of data is comprised of bits all of a first binary state, filling said first row with bits of said first binary state, (iii) if said operation code indicates said first row of data is comprised of bits all of a second binary state, filling said first row with bits of said second binary state, (iv) if said operation code indicates said first row of data repeats a block of data, filling said first row with duplicates of said block of data, and (v) if said operation code indicates said first row of data is identical to a second row of data, copying said second row.
(a) reading an operation code; and (b) if said operation code indicates the beginning of a first row of data, processing said operation code by:
(i) if said operation code indicates said first row of data is not compressed, copying said data, (ii) if said operation code indicates said first row of data is comprised of bits all of a first binary state, filling said first row with bits of said first binary state, (iii) if said operation code indicates said first row of data is comprised of bits all of a second binary state, filling said first row with bits of said second binary state, (iv) if said operation code indicates said first row of data repeats a block of data, filling said first row with duplicates of said block of data, and (v) if said operation code indicates said first row of data is identical to a second row of data, copying said second row.
24. The method as recited in Claim 23, wherein said second row is a predetermined number of rows from said first row.
25. The method as recited in Claim 23, further comprising the step of unpacking said first row of data if said operation code does not indicate the beginning of a row.
26. The method as recited in Claim 25 wherein said step of unpacking comprises the step of using a table having predetermined values to unpack said data.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US8430987A | 1987-08-11 | 1987-08-11 | |
| US084,309 | 1987-08-11 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CA1336015C true CA1336015C (en) | 1995-06-20 |
Family
ID=22184140
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA 574357 Expired - Fee Related CA1336015C (en) | 1987-08-11 | 1988-08-10 | Video compression algorithm |
Country Status (8)
| Country | Link |
|---|---|
| JP (1) | JPS6467086A (en) |
| AU (1) | AU613938B2 (en) |
| CA (1) | CA1336015C (en) |
| DE (1) | DE3827131C2 (en) |
| FR (1) | FR2619461B1 (en) |
| GB (1) | GB2208059B (en) |
| HK (1) | HK26392A (en) |
| SG (1) | SG592G (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02122959A (en) * | 1988-11-01 | 1990-05-10 | Seiko Epson Corp | Character pattern data storage device and character pattern generation device |
| US5179711A (en) * | 1989-12-26 | 1993-01-12 | International Business Machines Corporation | Minimum identical consecutive run length data units compression method by searching consecutive data pair comparison results stored in a string |
| JPH05183765A (en) * | 1991-12-27 | 1993-07-23 | Canon Inc | Data processing system and device usable for the system |
| WO1997006602A1 (en) * | 1995-08-03 | 1997-02-20 | Eulmi, Sam, H. | Recursive data compression |
| EP3619810A4 (en) * | 2017-07-31 | 2020-12-23 | Hewlett-Packard Development Company, L.P. | Xor processing of voxels of three-dimensional models |
| CN117118456B (en) * | 2023-10-25 | 2024-01-26 | 山东德源电力科技股份有限公司 | Magnetic control switch control data processing method based on depth fusion |
Family Cites Families (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4058674A (en) * | 1973-03-27 | 1977-11-15 | Kabushiki Kaisha Ricoh | Graphic information compression method and system |
| GB1481226A (en) * | 1973-08-31 | 1977-07-27 | Kokusai Denshin Denwa Co Ltd | System for coding two-dimensional information |
| US4071855A (en) * | 1976-03-03 | 1978-01-31 | Xerox Corporation | Encoder and decoder for bandwidth compression |
| DE2615486C2 (en) * | 1976-04-09 | 1983-12-08 | Philips Patentverwaltung Gmbh, 2000 Hamburg | Method and arrangement for the transmission of facsimile image signals |
| CA1128646A (en) * | 1978-11-22 | 1982-07-27 | Yasuhiro Yamazaki | Coding method for facsimile signal |
| JPS57124970A (en) * | 1981-01-26 | 1982-08-04 | Fujitsu Ltd | Video information coding system |
| US4546385A (en) * | 1983-06-30 | 1985-10-08 | International Business Machines Corporation | Data compression method for graphics images |
| EP0132455A1 (en) * | 1983-07-29 | 1985-02-13 | DR.-ING. RUDOLF HELL GmbH | Method and apparatus for the high definition display of line graphics |
| EP0149124B1 (en) * | 1984-01-16 | 1990-10-31 | International Business Machines Corporation | Method for encoding and decoding a digital image |
| US4631521A (en) * | 1984-12-31 | 1986-12-23 | Wang Laboratories, Inc. | Method and apparatus for differential run-length coding |
| JPS6276364A (en) * | 1985-09-27 | 1987-04-08 | Matsushita Graphic Commun Syst Inc | Picture information communication equipment |
| ATE75571T1 (en) * | 1987-03-17 | 1992-05-15 | Digital Equipment Corp | SYSTEM FOR GENERATION OF DIVERTER IMAGES FROM CONTINUOUS TONE IMAGE DATA. |
-
1988
- 1988-06-22 GB GB8814862A patent/GB2208059B/en not_active Expired - Lifetime
- 1988-08-08 JP JP19781588A patent/JPS6467086A/en active Pending
- 1988-08-08 AU AU20492/88A patent/AU613938B2/en not_active Ceased
- 1988-08-09 FR FR8810746A patent/FR2619461B1/en not_active Expired - Fee Related
- 1988-08-10 DE DE19883827131 patent/DE3827131C2/en not_active Expired - Fee Related
- 1988-08-10 CA CA 574357 patent/CA1336015C/en not_active Expired - Fee Related
-
1992
- 1992-01-02 SG SG592A patent/SG592G/en unknown
- 1992-04-09 HK HK26392A patent/HK26392A/en not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| HK26392A (en) | 1992-04-16 |
| DE3827131A1 (en) | 1989-02-23 |
| GB2208059A (en) | 1989-02-15 |
| GB8814862D0 (en) | 1988-07-27 |
| SG592G (en) | 1992-05-15 |
| AU2049288A (en) | 1989-02-16 |
| AU613938B2 (en) | 1991-08-15 |
| DE3827131C2 (en) | 1997-05-15 |
| GB2208059B (en) | 1991-09-25 |
| FR2619461B1 (en) | 1994-04-01 |
| FR2619461A1 (en) | 1989-02-17 |
| JPS6467086A (en) | 1989-03-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5033105A (en) | Video compression algorithm | |
| US5627534A (en) | Dual stage compression of bit mapped image data using refined run length and LZ compression | |
| US5974179A (en) | Binary image data compression and decompression | |
| US5463701A (en) | System and method for pattern-matching with error control for image and video compression | |
| US5218431A (en) | Raster image lossless compression and decompression with dynamic color lookup and two dimensional area encoding | |
| CA1242799A (en) | On-the-fly data compression system | |
| JPH0746409A (en) | Method and apparatus for data compression and return to original state | |
| EP0702457A2 (en) | Method and apparatus for compressing and decompressing data | |
| JPH0576171U (en) | Data compression and data compression dissociation device | |
| JP4057650B2 (en) | Sliding window data compression system with large gap | |
| CA1336015C (en) | Video compression algorithm | |
| US4707729A (en) | System for the line-wise compression of binary data of a picture field in a compression device, decompression device for use in such a system, and display device including such a decompression device | |
| JPH10500273A (en) | Video image color encoding | |
| KR100573527B1 (en) | How to compress and restore graphic images | |
| US7230630B2 (en) | Graphics display systems with data compression and methods of performing data compression of graphics data | |
| KR900017009A (en) | DPCM code word generation method, color image data storage method, optical memory disk and display device | |
| EP0090140B1 (en) | Complex character generator utilizing byte scanning | |
| KR900701128A (en) | Method and system for compressing and decompressing statistically encoded digital color video data | |
| US20020081038A1 (en) | Graphic image coding | |
| US6317515B1 (en) | Method and apparatus for encoding and decoding a data stream using inferential techniques | |
| US7286264B2 (en) | None-of-the-above digital halftone compression and decompression | |
| US6028962A (en) | System and method for variable encoding based on image content | |
| US6456742B1 (en) | Method for image processing | |
| KR100292050B1 (en) | Data simulator of variable length decoder | |
| JP2798025B2 (en) | Video coding method and apparatus |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| MKLA | Lapsed |