Abstract:
A method and apparatus for processing data using data compression. During compression, a relationship between a next data word and a previous data word is determined and that relationship is encoded into variable bit-length code words, the bit-length being inversely proportional to the probability of occurrence of the relationship between the data words. The encoded relationships are transmitted rather than the data words themselves. In one embodiment, a look-up table of code words is stored which is indexed according to the possible relationships. A relationship is determined between the previous and next data words and the relationship is matched to the index to find the corresponding code word in the look-up table. The corresponding code word is retrieved from the look-up table, is substituted for the relationship, and is transmitted.

Description:
BACKGROUND 
     The invention relates generally to information signal processing and more particularly, to data compression. 
     In cases where relatively large amounts of data must be transmitted over a transmission medium which cannot accommodate the data at the rate desired, a data compression technique may be considered. Such techniques compress the data to be transmitted into a smaller amount of data typically by identifying and replacing repetitive data with less data. This compressed data, if compressed enough, may then be transmitted at the rate desired. At the receiving end, the data is decompressed for use as required. Data compression permits more efficient use of the transmission process in that a higher density of data is transmitted in a given period of time. 
     For example, in the case of color video, a transmission rate of approximately 200 Mbits/sec is, in some cases, required. The use of lower transmission rates may adversely affect the ability to reconstruct a sufficient number of frames per second so that a real time picture is acceptable to the viewer. Various compression techniques have been used to transmit the color video information at reduced transmission rates. Some techniques, however, do not provide enough compression and the reduced transmission rate results in reconstructed frames presenting a poor quality picture. Some other techniques which use a higher transmission speed result in the loss of data thus the reconstructed picture is not an accurate representation of the original picture and may, in some cases, be noticeably distorted. 
     In the case of data storage, data compression may likewise be used to compress a unit of data into a smaller amount so that less storage space is used. This results in a greater density of data stored in the storage medium and more efficient use thereof. As with data transmission, loss of data is in many cases undesirable, thus a lossless data storage compression technique would be preferred. 
     One compression technique particularly applicable to color video data comprises the use of a code word having a color segment representing the three digital color components of a pixel and a length segment for the number of subsequent pixels having the same color components. Code words which follow this code word may indicate only changes in the color and in the length of pixels. One embodiment of such a code word has sixteen bits and includes color pixel data of three, four-bit segments totaling twelve bits. Each four-bit segment represents one of the three colors for the pixel. Also included in the code word is a four-bit segment containing the number of subsequent pixels to which this color data applies or &#34;length.&#34; This technique is referred to as a &#34;run length&#34; technique. Such a technique is described in detail in U.S. Pat. No. 4,847,677 entitled Video Telecommunication System And Method For Compressing And Decompressing Digital Color Video Data. 
     While the above-discussed compression technique represents a significant advance in the art, in some cases even greater data compression is desired. Such increased data compression should be lossless; that is, the system has the ability to recover the original data completely with no loss of original data. 
     A well known statistical data compression technique is that referred to as Huffman coding. Basically, the purpose of the Huffman coding technique is to reduce the average code length required to represent a data word. This is done by assigning the shortest code word to the most frequently occurring data word, longer code words to less frequently occurring data words and so on until the longest code word is assigned to the least frequently occurring data word. The Huffman codes are designed to be self-delimiting so that no shorter code word is duplicated as the beginning of the longer code word. Thus, no data word can be mistaken for another data word. This removes the need for delimiters such as spaces or additional delimiter code. In the case where there is an unequal distribution of data words, the overall effect of Huffman coding is that the number of bits required to represent the data is decreased and data compression results. While this technique has proved useful and has a number of applications, further compression than that available using this approach is desirable in some cases. 
     Those concerned with the transmission and storage of data have recognized the need for a data compression technique which provides even greater data compression yet has the ability to produce the original data without loss during decompression. The present invention fulfills those needs. 
     SUMMARY OF THE INVENTION 
     In accordance with the invention, a method and apparatus are provided for compressing and decompressing data. In the method and apparatus in accordance with the invention, a relational approach is used. During compression, a relationship between a next data word and a previous data word is determined and that relationship is encoded into a variable bit-length code word, the bit-length being inversely proportional to the probability of occurrence of the relationship between the data words. That is, a shorter bit-length code word is used for more frequently occurring relationships while a longer bit length code word is used for less frequently occurring relationships. The encoded relationships are transmitted rather than the data words themselves. A seed data word is provided to start the processing, and from that point, relationships between following words are encoded and transmitted. Thus, for the case where there is an unequal distribution of relationships, relationships having a higher frequency of occurrence will be represented by a substantially shortened bit-length code word with the overall effect of less data being transmitted or stored. The technique in accordance with the invention is lossless, that is, by means of decompressing the data in accordance with the invention, the original data can be recovered in its entirety. 
     A look-up table of code words is stored and is indexed according to the possible relationships. A relationship is determined between the previous and next data words and the relationship is matched to the index to find the corresponding code word in the look-up table. The corresponding code word is retrieved from the look-up table, is substituted for the relationship, and is transmitted. 
     Depending on the data being processed, the index words may be the relationships themselves. For example, in one embodiment, the relationship taken comprises subtracting the previous data word from the next data word and the difference is the index word in the look-up table. The code word corresponding to that difference is substituted for the relationship and transmitted. 
     In another embodiment, the relationship is the sequence of the words and their values. The look-up table is indexed by two indices, a first index is based on the possible values of the previous data word and the second index is based on the possible values of the next data word. The code words are selected in this table to correspond to the frequency of occurrence of the particular value of the next data word following the particular value of the previous data word. In this embodiment, the value of the previous data word is determined and matched to the first index of the look-up table. Then the value of the next data word is determined and matched to the second index of the look-up table. The indices are hierarchial in this embodiment with the first index being entered first, and from there, the second index may be entered. The code word corresponding to this double index is retrieved and substituted for the relationship and transmitted. 
     In the case of a color video run length word, a typical data word includes two segments, a length segment and a color segment. The length segment may be four bits and the color segment may be twelve bits in one embodiment. Data compression in accordance with the invention may occur in two parts in such a case. Two look-up tables are stored, one for the length data and one for the color data. The segments of the run length data are separated and may be processed in parallel. In regard to processing the relatively long color data segments, the color data segment of the previously occurring data word is subtracted from the color segment of the next occurring data word to result in a difference color word. The difference color word is used to enter the color data look-up table to locate a corresponding coded color word. 
     In regard to processing the relatively short length data segment, the length segment of the previously occurring data word is used to enter the length look-up table through a first index and the length data segment of the next occurring data word is used to proceed from the first index to a second index in the look-up table to locate the length code word. The located length code word is then retrieved. The coded color word is also retrieved as described above and is concatenated with the coded length word and the resulting concatenated code word is substituted for the relationship and is transmitted. 
     During decompression, the coded segments are separated, may be decompressed in parallel and are then combined into a color video run length word identical to the input word. 
     These and other objects and advantages of the invention will become apparent from the following more detailed description, when taken in conjunction with the accompanying drawings of illustrative embodiments. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 presents a data word comprising sixteen bits, twelve of which pertain to color and the remaining four of which pertain to length; 
     FIGS. 2A-B present a data processor using data compression in accordance with the principles of the invention showing a mode of continuous operation; 
     FIGS. 3A-B present the data processor of FIG. 2 in a start mode of operation; 
     FIGS. 4A-G are a look-up table with associated index for a difference relationship; 
     FIG. 5 is a look-up table with associated two hierarchical indices for a sequential relationship; and 
     FIGS. 6A-B are a diagram of a processor in accordance with the invention wherein the input data word comprises two segments which are split apart for separate but parallel processing. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the following description, like reference numerals will be used to refer to like or corresponding elements in the different figures of the drawings. In accordance with the invention, a method and apparatus are provided for processing data by determining a relationship between data, compressing that relationship through a statistical encoding technique, transmitting the encoded relationship, decompressing the relationship and recovering the original data. In decompressing the data in accordance with the invention, the compressed relationship is decompressed and applied to a stored previous data word to result in the decompressed data. 
     Referring now to the drawings, and particularly to FIG. 1, there is shown a color video &#34;run length&#34; data word 10 comprising sixteen bits, twelve of which comprise a color segment 12 and are used for representing the color components and four of which comprise the length segment 14 and are used as a length component. Although a color video application is described, it should be noted that the invention is not so limited and may be used in other applications. 
     Referring now to FIGS. 2A-B, a data processing apparatus 16 is presented. FIGS. 2A-B present the processor 16 in a continuing operation mode. FIGS. 3A-B present the processor 16 in a start mode and is discussed below. Input data 18 is provided by means such as an image capture engine of U.S. Pat. No. 4,847,677 and may take the form of the data word presented in FIG. 1. Although an encoded data word is shown in FIG. 1, the invention is not limited to such words. Input data words may take other forms, such as raw data. Input data words taking the form of encoded data may have configurations other than that shown in FIG. 1. For example, Huffman encoded data may be processed. Additionally, the term &#34;word&#34; is not meant to be used herein in a restrictive sense but is used merely to describe a specific item of data which includes a plurality of bits and may or may not be equal to the quantity of bits of another data &#34;word.&#34; 
     The input data words 18 indicated by X i , X i+1  through X n  are provided and are split into two copies by splitter 20. In the case shown in FIG. 2A, X i+1  is being provided as the input data word, the word X i  having been provided previously. The splitter 20 sends a copy of X i+1 , both to a memory 22 and to the relational operator 24. The memory is clocked by clock 26 and upon receiving X i+1 , stores it and outputs the previously stored data word X i . The relational operator 24 receives both X i  and X +i   1  and determines a relationship between them which is signified by the output symbol Δ i+1 . The particular relationship selected may take a plurality of forms depending upon the data being processed. For example, the relationship may be the difference between the two input data words or may be the particular sequence of the data words as will be described below in more detail. 
     The relationship Δ i+1  is received by an indexer 28 which then outputs a corresponding index word I i+1 . The index word is received by a look-up table 30 which then outputs a code word Y i+1  responsive to the index word and which represents the coded relationship between X i  and X i+1 . The code word Y i+1  is transmitted over a medium 32, for example over telephone lines to a receiving apparatus, or transmitted to a storage device such as a fixed disk. Upon receipt, or retrieval if stored on a disk, the code word Y i+1  is applied to an inverse look-up table 34 which outputs the actual relationship signified by the symbol Δ i+1 . The relationship Δ i+1  is applied to an inverse relational operator 36 along with the previous data word X i  which was stored in a memory 38 and is clocked out of the memory 38 by clock 40. The inverse relational operator 36 applies the relationship Δ i+1  to the previous data word X i  to result in the decompressed, next data word X i+1 . This decompressed next data word is then output as decompressed data 42 and is also stored in memory 38 for operation with the following relationship. 
     The above operation uses the relationship between input data words to achieve data compression. The relationship is compressed and transmitted, not the data word itself. When first starting the processor, there is no previous data word to use with the next data word. In accordance with one embodiment of the invention, a seed data word is provided. Referring now to FIG. 3A, input data word X 1  will be provided 18 to the splitter 20. This data word will be clocked into the memory 22 just as in FIG. 2A; however, the memory 22 in this case will output a seed data word X 0  which will operate as the previous data word. This seed data word X 0  is also stored in the memory 38 in the decompressing portion of the processor 16 and is applied to the inverse relational operator 36 as described for FIG. 2A. 
     In the preferred embodiment, the code words stored in the look-up table 30 are variable length words and are statistically selected such that relationships occurring at a higher frequency are assigned the shorter length code words while relationships occurring with a lower frequency are assigned longer length code words. The index words 28 are assigned accordingly. 
     In the embodiment shown in FIG. 1 where the input data words comprise a twelve-bit segment of color data and a four-bit segment of length data, these two segments may be processed separately and their indexing and look-up tables may differ. For example, the twelve-bit segments of color data themselves may be used as input words. The relational operator 24 takes a difference relationship between the color data segment of the next data word and the color data segment of the previous data word. That is, the previous color data segment is subtracted from the next color data segment and the difference is taken as the relationship (represented as Δ in FIGS. 2A-B and 3A-B). 
     Because the color segments are twelve bits, a look-up table containing all possible differences between two such segments may have 4096 separate difference entries. These difference entries may be the index words themselves and the look-up table contains a code word corresponding to each possible index word. As discussed above, the code words are selected on a probability bases with the shorter code words being assigned to the differences having a higher probability of occurrence. For example, in one embodiment, it was found that the most frequently occurring difference between two input color segments was zero. A code word of &#34;00&#34; was assigned to this difference. In many other cases, the difference occurs so seldomly that the difference itself is used as the code word with an added header of five bits, each of value &#34;one&#34; for a total of seventeen bits. The added header indicates to the inverse look-up table that the code word is not in code but is the value itself. Thus, the variable length string will range from two to seventeen bits in length in this embodiment. 
     It is possible to lessen the size of the look-up table from 4096 entries to a smaller number when the statistical analysis results in sparse entries in the table. Such a shrinking of the table was accomplished in one embodiment through the use of an encoder technique. The resulting table is shown in FIGS. 4A-G where the &#34;adr&#34; column is the index in hex format, the &#34;code&#34; column is the code word and the &#34;wid&#34; column is the number of bits in the resulting code word in accordance with the table below: 
     
         ______________________________________code width &#34;wid&#34;         no. of bits to be coded______________________________________0             21             52             63             74             95             126             not used7             17______________________________________ 
    
     A processing technique for determining the index word (&#34;adr&#34;) in FIGS. 4A-G is given in the appendix hereto. The appendix is in the C programming language. The terms &#34;dta --  r, dta --  g, and dta --  b&#34; represent red, green, and blue differences respectively. The term &#34;out --  codes&#34; refers to the output code word &#34;xyz&#34;. The variable &#34;xyz&#34; represents a twelve-bit difference. In case of the code word being equal to seven, which represents a seventeen-bit code to be sent, a five-bit header of all &#34;ones&#34; is concatenated with the twelve-bit difference. 
     Referring again to FIG. 1, the four-bit segment of length data may be used as the input data word itself. A relationship between the length segment of the next data word and the length segment of the previous data word is taken and a code word assigned from a look-up table. In one embodiment, the relationship of a sequence of values was used. That is, the look-up table had two indices, the first corresponding to all possible values of the length segment of the previous data word and the second index corresponding to all possible values of the length segment of the next data word. These sequences of values are taken as the relationship (indicated as Δ in FIGS. 2A-B and 3A-B) in this embodiment. Because the length segments are four bits, and there are two indices, a look-up table containing all possible combinations would contain sixteen tables each having sixteen different code words. Such a look-up table is shown in FIG. 5 in hex and binary formats. As with the look-up table for the color segments, a statistical analysis was performed in determining the code words for the sequences. The most frequently occurring sequences received the shortest code words while the less frequently occurring sequences received the longer code words. For example, it was found that a frequently occurring sequence is a previous data word having a length segment of &#34;e&#34; followed by a next data word having a length segment of &#34;e&#34;. The code word assigned is a single &#34;0&#34;. 
     Referring now to FIGS. 6A-B, in the case of color video run length data, the data processing in accordance with the invention may occur in two parts. The color video input data word is separated into the color data segment and the length segment by a separator 44. Both segments are processed 46 as described above and the relationships compressed, and these compressions may occur in parallel as shown. The compressed relationships may be concatenated 48 and transmitted or stored through the medium 32. The compressed relationships may be received from the medium 32 and the color relationship sefparated 50 from the length relationship. Decompression 52 of each relationship occurs in parallel as described above and the decompressed segments are combined to result in the color video run length data word. 
     The technique in accordance with the invention is lossless, that is, by means of decompressing the data in accordance with the invention, the original data can be recovered in its entirety. 
     The invention is not meant to be limited to single pixels and the input data words may be a video frame of data or a scan line of data or other data. Additionally, the computed difference may be taken between the present color bits and the previously processed color (horizontal correlation) or from the nearest color (positionally) on the previously processed line. 
     In regard to the start mode of the processor shown in FIGS. 3A-B, the starter length segment of four bits is set to hex 0e (decimal 14) in one embodiment. The starter color segment of twelve bits is set to hex 088 in one embodiment. 
     Thus there has been provided a new and useful data compression method and apparatus for use in processing data including transmitting and storing data. The combination of the invention permits increased data compression than that provided by prior techniques. It will be apparent from the foregoing that, while particular forms of the invention have been illustrated and described, various modifications can be made without departing from the spirit and scope of the invention. Accordingly, it is not intended that the invention be limited, except as by the appended claims.