JPH0884260A - Two-dimensional image data compression method and decompression method - Google Patents

Abstract

(57) [Summary] [Object] To provide a data compression method and an expansion method for increasing the data compression rate of image data and for high-speed compression and expansion. [Structure] A dictionary buffer 6 for holding the data of the immediately preceding line, a buffer 16 for extracting a compression target subsequence from the current line within a range of the maximum detection sequence length N, and a data sequence same as the compression target subsequence from the dictionary buffer 6 A comparator 7 for detecting
When the same data string is detected, the number of pixels in one line is H, the position of the target pixel on the current line is x, T = 0 when x = 0, and T = when 1 ≦ x ≦ H−N 1, H-N + 1 ≤
When x ≦ H−1, T = x−H + N + 1 is set, a table corresponding to each value of T is selected / referenced from the table group 70, and according to the position and length of the data string on the immediately preceding line. A code generator 8 for outputting a code is provided.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression system and a decompression system for two-dimensional image data.

[0002]

2. Description of the Related Art Conventional image compression methods include an irreversible data compression method and a reversible data compression method. The discrete cosine transform (DC
The lossy data compression method such as JPEG or MPEG using T) cannot be used because information loss occurs when compressing image data using a color code (call code of color palette). A typical method of the latter reversible data compression method is a method of performing data compression using run length of information (run length compression), and performing frequent data registration in a dictionary to perform data compression. It is a method (dictionary compression). The latter method is IE
EE Transactions on Information Theory IT-24, pp.5
Ziv and Lempel's article "Compr.
ession of Individual Sequenes via Variable Rate Co
ding ".

[0003]

Each of the above compression methods has the following problems. The run-length compression is effective for image data that contains a large amount of the same continuous information, but is ineffective for image data that is not so, and the compression effect may not appear at all.

The dictionary compression is effective for image data having a high hit ratio to the dictionary, but is not effective for image data which is not so. Further, since the hit rate depends on the storage capacity for storing the dictionary, if a high hit rate is desired, a large-capacity storage location is required. Furthermore,
Having a large-capacity dictionary increases the number of dictionary lookups,
The compression speed decreases. Therefore, the present invention compensates for the problems of the above-described compression method, increases the data compression rate of image data, reduces the amount of information, and enables high-speed compression, and expands the compressed data at high speed. It is an object of the present invention to provide a decompression method that can be performed.

[0005]

In order to achieve the above object, in the data compression method of the present invention, two scans are sequentially performed.
Refer to the data of the previous line for 3D image data,
In the compression method of the two-dimensional image data, the compression process is performed when the same partial data string as at least one pixel is detected in the current line for at least one pixel.
The number of pixels in a line is H, the maximum detection column length of the partial data string is N (1 ≦ N ≦ H), and the position of the pixel of interest from the first pixel on the current line is x (0 ≦ x ≦ H−1). And x
= 0, T = 0, 1 ≦ x ≦ H−N, T = 1,
When H−N + 1 ≦ x ≦ H−1, T = x−H + N + 1,
And a table in which a different code is assigned to each value of T according to the relative position of the leading pixel of the partial data string and the target pixel on the immediately preceding line and the length of the partial data string. When a partial data string which is prepared and is the same as the immediately preceding line for at least one pixel is detected, the value of T is obtained based on the position x of the pixel of interest from the first pixel on the current line, and The corresponding table is selected based on the value of T, and a code corresponding to the head position and length of the partial data string on the immediately preceding line is output.

In the data decompression method of the present invention, when the data of the immediately preceding line is referred to for the sequentially scanned two-dimensional image data, and the same partial data string as at least one pixel is detected in the current line for at least one pixel. As the compressed data of the overlapping portion, the number of pixels in one line of the two-dimensional image data is H, the maximum detection column length of the partial data sequence is N (1 ≦ N ≦ H), The position from the first pixel of x is set to x (0 ≦ x ≦ H−1), and x =
0 = 0, T = 0, 1 ≦ x ≦ H−N, T = 1, H
When −N + 1 ≦ x ≦ H−1, T = x−H + N + 1, and for each value of T, the relative position between the leading pixel of the partial data string and the target pixel on the immediately preceding line, and the length. Is a decompression method for two-dimensional image compression data that is sequentially input with different codes assigned according to the above. At least the decompressed data of the immediately preceding line is held in a buffer, and on the current line of the pixel of interest to be decompressed. The value of T is obtained based on the position x at, and based on the value of T, a table prepared for each value of T and assigned different codes according to the relative position and the length is selected. Select the corresponding table, extract the code from the input compressed data, refer to the table selected based on this code, for the data of the input current line,
Data of the length of the partial data string following the bit corresponding to the head position of the partial data string is extracted from the buffer and output as decompressed data.

Further, a data compression apparatus for realizing the above-mentioned data compression method is provided with a reference memory means for holding data of one line before for sequentially input two-dimensional image data and an input current line signal. Buffer means for extracting a plurality of continuous data strings within a predetermined length range and storing them as compression target partial data strings, and data stored in the reference memory means for the target pixel of the compression target partial data strings. Scan comparing means for detecting whether or not the same partial data string as the subsequent partial data string exists, and when the scan comparing means detects the same partial data string, the previous one line stored in the reference memory means is detected. The relative position between the first pixel of the partial data string and the target pixel on the data and the length of the partial data string are obtained, and the number of pixels of one line of the two-dimensional image data is set to H. The maximum detection sequence length of the partial data string N (1 ≦ N ≦ H), the position of the head pixel on the current line of the pixel of interest with the x (0 ≦ x ≦ H-1), x =
0 = 0, T = 0, 1 ≦ x ≦ H−N, T = 1, H
When -N + 1 ≤ x ≤ H-1, T = x-H + N + 1, and a table prepared for each value of T, to which different codes are assigned according to the relative position and the length of the partial data string. Code generation means for outputting the corresponding code as compressed data of the partial data string of the current line.

Further, a data decompression device for realizing the above-mentioned data decompression method refers to immediately preceding data with respect to sequentially input two-dimensional image data, and presents a partial data string which is the same as the immediately preceding line for at least one pixel or more to the current line. When detected, the number of pixels in one line of the two-dimensional image data is H, the maximum detection column length of the partial data sequence is N (1 ≦ N ≦ H), and the current pixel of interest is present as the compressed data of the overlapping portion. The position on the line from the first pixel is set to x (0 ≦ x ≦ H−1), and when x = 0, T = 0, and when 1 ≦ x ≦ H−N, T = 1, H−. When N + 1 ≦ x ≦ H−1, T = x−H
+ N + 1, and for each value of T, two-dimensional image compression data in which different codes are sequentially input according to the relative position between the leading pixel of the partial data string and the target pixel on the immediately preceding line and the length. Of the decompressing device, buffer memory means for holding decompressed data of one line before, and the head of the partial data string on the immediately preceding line prepared for each value of T according to the code. Based on the inverse conversion table to which the relative position of the pixel and the pixel of interest and the length of the partial data string are assigned, and the position x of the pixel of interest of the compressed data to be expanded from the first pixel on the current line Obtain the value of T, select the inverse conversion table corresponding to the value of T, extract the code from the input data, and refer to the inverse conversion table selected based on the code. Then, the data of the starting position and the length of the partial data string on the immediately preceding line is taken out from the inverse conversion table, and the partial data string following the bit corresponding to the starting position of the partial data string is extracted from the buffer memory means. Decoding means for extracting data for the length and outputting it as decompressed data.

[0009]

In order to facilitate understanding of the present invention, the principle of the present invention will be described with reference to the drawings. In the present invention, the property that a pixel having image data is similar to a pixel group in the vicinity is used, and in the two-dimensional image data (shown in FIG. 1) that is sequentially scanned, the data of the immediately preceding line is stored as reference data (which is stored). The buffer is called "dictionary" 1.). Then, the dictionary 1 of the immediately preceding line is referred to, and it is detected whether or not the dictionary 1 has the same partial column as the partial column 2 on the line data to be compressed for at least one pixel.

When a subsequence matching the compression target subsequence 2 is detected in the dictionary 1, the compression target subsequence 2 is as long as possible within a preset maximum detection sequence length N (here, N = 8). The subsequence 3 that matches with is detected. Next, the number of pixels in one line of the two-dimensional image data is H, and the position of the pixel of interest (the leading pixel of the compression target partial sequence) on the current line is x (0
≦ x ≦ H−1), and when x = 0, T = 0,
When 1 ≦ x ≦ H−N, T = 1, H−N + 1 ≦ x ≦ H−
When 1 is set, T = x−H + N + 1, and the relative position between the head pixel and the target pixel of the partial row on the immediately preceding line, which is prepared for each value of T, and the length of the partial row on the immediately preceding line. From the table to which different codes are assigned in accordance with the above, the value of T obtained based on the position x (here, x = 0) of the target pixel 5 from the first pixel on the current line (here, T =
The table corresponding to (0) is selected and referred to. Then, data compression is performed by outputting a code corresponding to the head position 4 of the partial string 3 on the dictionary 1 and the length of the partial string 3 (here, 5 dots). At this time, it is desirable to limit the reference range for the dictionary 1 to a range in which the degree of similarity between the compression target subsequence 2 and the subsequence on the dictionary 1 is high. Further, the maximum detection row length N is set to a large value when the same partial row existing on an adjacent line in the two-dimensional image data is relatively long and a small value when it is short in order to improve the compression / decompression speed. It is desirable to do. However, if N is set to an extremely large value, the number of tables will increase, and rather compression
The extension speed decreases. On the other hand, if N is set to an extremely small value, the number of tables decreases, but the length of the subsequence to be referred to is short, so the compression rate decreases. Although FIG. 1 shows two-dimensional image data in which the number of pixels H in one line is 16 dots, if the maximum detection column length N <the number of pixels H in one line, the range of possible values of T is one line. Number of pixels H
It is constant regardless of the value of. That is, the possible values of T are 0 ≦ T ≦ x−H + N + 1, but the maximum possible value of the position x on the current line of the pixel of interest is H−1, so that 0 ≦ T ≦ N after all. Become. Therefore, even when the number of pixels H of one line of the two-dimensional image data is increased, the number of tables is always N + 1 (here, N = 8, so the number of tables is always 9).

If the dictionary 1 cannot detect a subsequence that matches the compression subsequence 2, run length compression or the like is applied to the compression subsequence 2. When the run length compression is applied, the run length table, which is prepared for each value of T described above and to which different codes are assigned according to the length of the same continuous data, is used on the current line of the pixel of interest. It is desirable to perform the data compression by selecting and referring to the run length table corresponding to the value of T obtained based on the position x from the first pixel in (3) and outputting the corresponding code. At this time, the code stored in the run length table must be different from the code stored in the above table. Further, the codes stored in the table and the run length table are not fixed length codes, but are preferably variable length codes in order to allocate a short code to data with a high probability of occurrence and to increase the compression rate.

According to the present invention, as described above, the capacity of the dictionary is very small because it is sufficient to store only the immediately preceding line. Further, since the dictionary is referred to within the range of high similarity and the substring as long as possible within the range of the maximum detected column length N is used, the compression rate is high and the compression and decompression can be processed at high speed. is there. Further, since the prepared table is always the maximum detection column length N + 1 regardless of the number of pixels in one line of the two-dimensional image data, when the number of pixels in one line of the two-dimensional image data is increased, the capacity of the table increases. It is possible to prevent a decrease in processing speed. Further, by applying run length compression or the like to the first line of the image data or the partial sequence that cannot be referred to the dictionary, a higher compression rate can be obtained.

[0013]

Embodiments of the present invention will be described below in detail with reference to FIGS. FIG. 2 is a configuration example of the data compression circuit of the present invention. FIG. 3 is a flow chart of the data compression algorithm of the present invention. In FIG. 2, 5 is a line buffer, 6 is a dictionary buffer for holding data of one line before, 7 is a comparator, 8 is a code generator, 9 is an adder, 10 is a pointer, 11 is a relative position counter, and 12 is Pointer buffer, 13 length counter, 14 relative position / length buffer, 15 selector, 16 partial column buffer, 70
Is a table group in which the tables shown in FIGS. 6 to 14 are prepared, 17 is an input signal line to the line buffer, 18 is an input signal line to the dictionary buffer, and 19 is a code output line. In the tables shown in FIGS. 6 to 14, T is determined based on the position of the pixel of interest (the start pixel of the compression target partial sequence is defined) on the current line from the start pixel (the value of T will be described later. Yes) is prepared for each value. In each table, in the two-dimensional image data sequentially input through the input signal line 17 to the line buffer, the relative position between the head pixel and the target pixel of the same partial data string as the compression target partial string on the immediately preceding line, Different codes are assigned and stored according to the length of the compression target subsequence.

Next, an outline of the operation of the data compression circuit configured as described above will be described based on the flow of FIG. First, in process 20, the number of pixels H of one line of two-dimensional image data is input to the code generator 8. Next, in process 21, the pointer 10 is initialized, the data pushed out from the line buffer 5 through the dictionary buffer input signal line 18 is stored in the dictionary buffer 6, and then the sequentially input two-dimensional image data is input into the line buffer input signal line 17. Through the line buffer 5 (process 22).

Next, a preset maximum detection column length N (1
The longest substring in the dictionary that matches the search target subsequence (defining the data of consecutive pixels selected from the data of the current line stored in the line buffer 5 in this way) within the range of ≦ N ≦ H) Is searched (process 23).
It should be noted that the maximum detection row length N is used when the same partial row existing on an adjacent line is relatively long in the two-dimensional image data sequentially input through the line buffer input signal line 17 in order to improve the compression / expansion speed. Is larger,
When it is short, it is desirable to set it small. However, if N is set to an extremely large value, the number of tables increases, and the compression / decompression speed decreases on the contrary. On the other hand, if N is set to an extremely small value, the number of tables decreases, but the length of the subsequence to be referred to becomes short, so the compression rate decreases. In this embodiment, N = 8. This longest subsequence search is shown in Figure 3.
Although a single flow is shown as process 23 in FIG. The concept of searching the longest subsequence is 16 × 8
An example will be described with reference to FIG. In the present embodiment, it is determined whether or not the same subsequence as the search target subsequence exists in the line one line before the search target subsequence by -1 from the head pixel position of the search target subsequence ( Position +1 advanced from relative position -1) (relative position +
(Defined as 1), it is determined by searching whether or not the same pixel as the leading pixel of the search target partial sequence exists. Then, when the same pixel row exists within the range shifted by one pixel on the left and right one line before, the compression of the process 23 is performed.

In terms of FIG. 4A, (1) relative position -1
For example, the partial column “55” following “5” in the third row and first column
There is 4 ". Since this partial string "554" is the same data string as the partial string "554" following "0" in the 0th column of the second row, it is determined that the same partial string exists at a position shifted by one pixel to the left. (2) As an example of the relative position 0, there is a partial column "34" following "3" in the first row and fourth column. This subsequence “3
Since “4” is the same data string as the partial string “34” that follows “3” in the fourth column of the 0th row, it is determined that the same partial string exists at a position shifted by 0 pixel. (3) As an example of the relative position + 1, there is a partial column "55434" following "5" in the second row and the 0th column. This partial column “55434” is the first row and first column “5”
Since it is the same data string as the partial string "55434" that follows, it is determined that the same partial string exists at the position shifted by one pixel to the right.

In the process 23, first, the data of the pointer 10 is stored in the pointer buffer 12, and the relative position counter 1
Initialize 1. Next, the data for one pixel is fetched from the line buffer 5 pointed by the pointer 10 into the partial column buffer 16. Line buffer 5 to partial column buffer 16
Whether or not there is a matching pixel for the pixel at the relative position −1, the pixel at the relative position 0, and the pixel at the relative position +1 stored in the dictionary buffer for the pixel data of the current line captured in If no search is made, a length “0” is written in the relative position / length buffer 14 for each relative position, and the process proceeds to step 24. In FIG. 4A, 1
Since “4” in row 3 column is 0 row 2 column, 0 row 3 column is “2”, and 0 row 4 column is “3”, the relative position / length buffer 14 has a point (1, 3). ), "0" is written as the length data for all the relative positions -1, 0, and +1. If there is a matching pixel, the pointer 10 and the length counter 15 are incremented, and the data of the adjacent pixel is fetched into the partial column buffer 16. At this time, pointer buffer 1
In 2, there is left the start address of the search target subsequence being searched in this search.

The first pixel of the search target subsequence has a relative position of -1.
If a match is found with respect to the next pixel, the data of the pixel at the relative position -1 of the data one line before is compared with the pixel fetched into the partial column buffer 16, and the match with the relative position 0 is found. If found, the data of the pixel at the relative position 0 of the data one line before is compared with the pixel fetched in the sub-sequence buffer 16 for the adjacent pixel, and if a match is found at the relative position +1 For the adjacent pixel, the data of the pixel at the relative position +1 of the data one line before is compared with the pixel fetched in the partial column buffer 16. If the respective comparison results show a match, the adjacent pixel pointer 10 is further incremented, the data of the adjacent pixel is fetched into the partial column buffer 16, the length counter 15 is incremented, and the respective comparison results are The process is repeated until they do not match or the count value of the length counter 15 reaches the maximum detection column length N (N = 8 in this embodiment). As a result, when the comparison results do not match, the value counted by the length counter 15 at the time when they do not match is measured as the length L of the partial data string having the same data string in the data one line before. Further, when the count value of the length counter 15 reaches the maximum detection column length N, the value of the maximum detection column length N is set as the length L of the partial data sequence having the same data sequence in the data one line before. To be measured. This length information is counted for each of relative position-1, relative position 0, and relative position + 1. That is, after the length L is counted for the relative position −1 as described above, the length L is stored as length information for the relative position −1 in the column of the relative position −1 of the relative position / length buffer 14. Remember. Next, in order to perform a search for the relative position 0, the start address of the search target partial string temporarily stored in the pointer buffer 12 is returned to the pixel pointer 10, the relative position counter 11 is incremented, and the search target partial string Similarly, the data at the relative position 0 does not match the data on the right of the start address, or the comparison is performed while incrementing the pointer 10 until the count value of the length counter 15 reaches the maximum detection column length N. Information L is obtained. Then, the same search is performed for the relative position +1.

Considering a partial column having "5" in the 2nd row and 0th column as the leading pixel in FIG. 4A, since this pixel is the beginning of the line, there is no data at the relative position -1 of the previous line. Therefore, for the relative position -1, the length L becomes 0. As for the relative position 0, since "5" exists in the 1st row and 0th column, the length counter 13 is incremented and the 2nd row and 1st column data "5" adjacent to the 2nd row and 0th column "5" is a partial column. It is fetched in the buffer 16 and compared with "5" in 1 row and 1 column.
Since this also matches, the length counter 13 is incremented, and the data “4” of 2 rows and 2 columns adjacent to “5” of 2 rows and 1 column is fetched into the partial column buffer 16 and 1 row and 2
Compared to column "5". This does not match. At this time, the value of the length counter 13 is "2", and the maximum partial column length N = 8 has not been reached. Therefore, "5" in row 2 and column 0
The length L with respect to the relative position 0 of the partial sequence having
Is 2.

For a partial column having "5" in the 2nd row and 0th column as the leading pixel, "5" exists in the 1st row and 1st column and coincides with the leading pixel. Therefore, the adjacent pixel is also compared at the relative position +1. The adjacent data “5” of 2 rows and 1 column of “5” of 2 rows and 0 column is fetched into the partial column buffer 16 and the relative position +
1 is compared with “5” in the 1st row and the 2nd column. Since they coincide with each other, if the pixels on the right side are sequentially fetched and the comparison is continued, there is a disagreement when the comparison of “3” at 2 rows and 5 columns and “1” at 1 row and 6 columns is performed. The value of the length counter 13 at this time is "5", and the maximum partial column length N = 8 has not been reached. Therefore,
Relative position 1 of the partial column with "5" in the 2nd row and 0th column as the first pixel
Has a length L of 5.

As described above, as the length L of the partial column having "5" in the 2nd row and 0th column as the leading pixel, L (relative position -1) =
Three of 0, L (relative position 0) = 2, L (relative position + 1) = 5 will be stored in the relative position / length buffer 14. Of these, the longest substring whose length L is 5 is selected. In the case of FIG. 4A, as shown in FIG. 4B, the subsequence a (55) indicates the same subsequence at relative position 0, and the subsequence b
(55434) indicates the same partial sequence at relative position +1. Since the subsequence a has a length of 2 and the subsequence b has a length of 5, the subsequence b having high compression efficiency is selected.

That is, the process shifts from the process 24 to the process 25, and the position of the pixel of interest stored in the pointer buffer 12 on the current line is stored in the relative position / length buffer 14 as x. The length of the longest data is y and the value obtained by adding 2 to the relative position of the longest data is z, and these x, y and z are input to the code generator 8.

In step 28, the code generator 8 obtains the value of T from the position x of the target pixel on the current line. The value of T is
When x = 0, T = 0, and when 1 ≦ x ≦ H−N, T =
1, when H−N + 1 ≦ x ≦ H−1, T = x−H + N +
It is 1. Here, H is the number of pixels of one line of the two-dimensional image data input to the code generator 8 in process 20, and N is the preset maximum detection column length. As described above, in this embodiment, H = 16, and since N = 8 was set in advance, the value of T is T = 0 when x = 0 (process 29),
When 1 ≦ x ≦ 8, T = 1 (processing 30), 9 ≦ x ≦ 15
In case of, T = x−7 (process 31).

In process 32, the code generator 8 selects and refers to the corresponding table from the table group 70 based on the value of T obtained from the position x of the target pixel on the current line, and refers to the data. A code corresponding to the length y and the value z obtained by adding 2 to the relative position to the length y is output through the code output line 19.

If all the lengths stored in the relative position / length buffer 14 are 0 in the process 24, that is, if no matching subsequence is found in the dictionary, the process 24 is performed. The process moves to step 26, and run length compression is performed. That is, a partial column in which the same pixel on the current line is continuous as long as possible within the range of the maximum detection column length N (N = 8 in this embodiment) is searched. First, the pointer 10
The data in the line buffer 5 pointed to by the partial column buffer 16
To the line buffer 5
The data of is input to the comparator 7 through the selector 15,
The data is compared with the data in the partial column buffer 16. If they match as a result of the comparison, the length counter 13 is incremented,
The data pointed to by the next pointer 10 is input to the comparator 7 through the selector 15 and compared with the data in the partial column buffer 16. And the result of comparison becomes inconsistent, or
Until the count value of the length counter 15 reaches the maximum detected column length N, the pointer 10 is advanced one by one and the comparison with the data of the partial column buffer 16 is repeated. As a result, when the comparison results do not match, the value counted by the length counter 15 at the time when they do not match is measured as the length L of the partial data string in which the same pixel on the current line is continuous, When the count value of the length counter 15 reaches the maximum detection column length N, the value of the maximum detection column length N is measured as the length L of the partial data sequence in which the same pixel on the current line is continuous.

Next, in process 27, the pointer buffer 12
Where x is the position of the pixel of interest stored in the current line on the current line, and y and z are the lengths of the partial data strings in which the same pixel counted by the length counter 13 is 0.
The data stored in the subsequence buffer 16 is input to the code generator 8 together with the values of y and z.

Next, based on the value of T obtained from the position x of the target pixel on the current line, the corresponding table is selected from the table group 70 and referred to, and the data lengths y and z =
Code corresponding to 0 and raw data to be repeated,
It is output through the code output line 19 (process 32).

The above operations are repeated up to the final line of the two-dimensional image data through the process 33 and the process 34 to compress and encode the data.

Next, the data compression process of the 16 × 8 image data shown in FIG. 4 will be described. Each data shall be represented by 4 bits. Hereinafter, for convenience, the coordinates of the image data will be represented by (column, row), and the encoded code will be represented by {T, relative position, length} or [T, data type, length]. . That is, the portion enclosed by curly brackets {} is the portion where compression according to the present invention is performed, and the portion enclosed by key brackets [] indicates the portion where run length compression is performed. Here, T is a value obtained from the position x of the target pixel on the current line in the process 28. That is, in the present embodiment, when the pixel of interest is located in the 0th column, T
= 0, T = 1 when located in the 1st to 8th columns, T = 2 when located in the 9th column, T = 3 when located in the A column, T = 4 when located in the B column If it is located in column C, T =
When located in the 5, D column, T = 6; when located in the E column, T = 7; and when located in the F column, T = 8.

For example, the code column of the pixel of interest is 0, the relative position is 1, and the length is 3, the code code is {0, 1, 3}, the column of the pixel of interest is 1, the type of data is 5, and the length is 2. The code code of is [1, 5, 2]. In addition, the coordinates of the pixel of interest are (x, y)
Then, the dictionary reference range is relative position (x-1, y-1), (x, y
y-1) and (x + 1, y-1). First, in the case of FIG.
Since there is no dictionary to refer to in the line, run length compression is performed. Since the data of the image data (0,0) to (3,0) is the same as 2, the code is [0,2,4].
Since there is only one 3 in (4, 0), the code is [1, 3, 1]
Becomes Since the data from (5,0) to (7,0) is the same as 4, the code is [1,4,3]. Since there is only one 6 in (8,0), the code is [1,6,1]. (9,
Since the data of 0) and (A, 0) are the same in C, the code is [2, C, 2]. Since the data of (B, 0) and (C, 0) is the same as 6, the code is [4,6,2].
Since the data from (D, 0) to (F, 0) is the same as 3, the code is [6, 3, 3]. Therefore, the code of the 0th line is [0, 2, 4] [1, as shown in the 0th line of FIG.
3,1] [1,4,3] [1,6,1] [2, C, 2]
[4, 6, 2] [6, 3, 3].

In the processing of the first line in FIG. 4A, the 0th line is treated as a dictionary. Since (0,1) and (0,0) are compared and do not match, the next comparison is made with (0,1) and (1,0), which also does not match, so there is no matching subsequence in the dictionary. Then, run length compression is applied. Since the data from (0,1) to (2,1) is the same as 5, the code is [0,
5, 3]. 4 in (3,1) is (2,0), (3,1)
Since it does not match either 0) or (4,0), run length compression is applied and the code becomes [1,4,1].
3 in (4,1) is (3,0), (4,0), (5,0)
Matches (4,0) in (4,1) to (5,1)
Since (4,0) to (5,0) in the dictionary match, the code is {1,0,2}. Since (6,1) and (7,1) do not match with the dictionary data, the codes are [1,1,1] and [1,3,1], respectively. (8,1)
C of (7,0), (8,0), matches (9,0) in (9,0), and (8,1) to (9,1) and (9,0) in the dictionary. ) To (A, 0) match, the code is {1,1,2}. C of (A, 1) is (9,0),
(A, 0), (9,0) in (B, 0) and (A,
0). Here, (B, 1) and (A, 0) do not match, but (A, 1) to (C, 1) and (A,
Since 0) to (C, 0) match, the code is {3, 0,
3}. 6 of (D, 1) is (C, 0), (D,
0), (E, 0) in (C, 0), and (D,
1) to (F, 1) and dictionary (C, 0) to (E, 0)
Match, so the code is {6, -1, 3}. Therefore, the code in the first line is as shown in the first line in FIG.
[0,5,3] [3,4,1] {4,0,2} [6
1,1] [7,3,1].

In the process of the second line in FIG. 4A, the first line is treated as a dictionary. (0,2) is the dictionary (0,
1) matches the dictionary (1, 1) at the relative position 1, but if the relative position is 0, the length of the matching substring is (0,
1) to (1, 1) and 2, but in the case of the relative position 1, the lengths of the matching substrings of the dictionary are (1, 1) to (5.
1) and 5, and the subsequence of the dictionary at relative position 1 is longer, the code is {0, 1, 5}, and if the above process is repeated until the last line, the image data of FIG. A code string of 5 is obtained.

Next, the code strings in FIG. 5 will be assigned to actual codes using the tables shown in FIGS. 6 to 14. 6 to 14 show values of y and z prepared for each value of T.
9 shows a table in which different codes are assigned depending on the value of. Here, T is a value obtained from the position x of the target pixel on the current line in process 28, and y and z are process 25 or process 2.
7 is a value input to the code generator 8 in y, y is the length of the substring to be compressed, z is 0 when the code string is enclosed in key brackets [], that is, 0 in the case of run length compression, When the code string is enclosed in braces {}, that is, in the case of dictionary compression according to the present invention, it is a value obtained by adding 2 to the relative position.

The code stored in each table is not a fixed length code but a variable length code in order to assign a short code to data with a high probability of occurrence to increase the compression rate. still,
The reason why the table is prepared for each value of T is as follows.
In principle, only one table may be prepared. But,
When the tables are put together, different codes must be assigned according to all possible values of y and z.
By the way, the values that can be taken by y and z differ depending on the position x from the first pixel on the current line of the pixel of interest. For example, the maximum value of y in each table is the bit string length from the pixel of interest to the pixel located at the end of the current line. When x = 0, z = 1 (when the relative position is -1)
There is no need to assign a code to. Therefore, if the tables are combined into one, the code redundancy increases. On the other hand, when a table is prepared for each position x from the first pixel on the current line of the target pixel, the maximum value of y in each table is set to the bit string length from the target pixel to the pixel located at the last end of the current line. By limiting, code redundancy can be improved. However, when the number of pixels H of one line of the two-dimensional image data is increased, a new table has to be added, and the capacity of the table increases, so that the compression / expansion speed decreases. Therefore, in the present embodiment, the maximum detection sequence length N of the compression target partial sequence is set in advance.
When x = 0, it is not necessary to assign a code to z = 1. Therefore, a dedicated table is prepared, and if 1 ≦ x ≦ H−N, y is set.
Since all the maximum values that can be taken are N and the values that z can take are all 0 to 3, one table is prepared collectively, and the possible values of z are H-N + 1 ≦ x ≦ H−1. Although all are 0 to 3, the maximum possible value of y is the bit string length from the pixel of interest to the pixel located at the final end of the current line, so a dedicated table was prepared for each value of x. That is, T = 0 when x = 0, T = 1 when 1 ≦ x ≦ H−N, and T = x−H + when H−N + 1 ≦ x ≦ H−1.
N + 1, and a table was prepared for each value of T. By setting the value of T in this way, the range of possible values of T becomes constant regardless of the value of the number of pixels H of one line if the maximum detection column length N <the number of pixels H of one line. . That is, the possible values of T are 0 ≦ T ≦ x−H + N +
Although it is 1, the maximum possible value of the position x on the current line of the target pixel is H−1, so that 0 ≦ T ≦ N is satisfied. Therefore, even when the number of pixels H of one line of the two-dimensional image data is increased, the number of tables is always N + 1, so that it is possible to prevent the table capacity from increasing and the compression / decompression speed to decrease. it can.

Further, in the present embodiment, since the image data is compressed, in the case of the dictionary compression, the data immediately before the line having the pixel of interest and adjacent to the pixel of interest (relative position is -1, The size of the table is reduced by performing dictionary compression only on (0, +1 data). Thereby, a high compression rate can be expected. The table prepared in the table group 70 must be a table of Huffman code configured in advance for data to be compressed / decompressed, or a table that is optimized to reduce redundancy with compression / decompression. Is desirable. 6 to 14, the hyphen "-"
The ones indicated by means that variable length codes are not assigned.

First, based on the value of T, one of the tables shown in FIGS. 6 to 14 is selected.
For example, when encoding [0,2,4], the table of T = 0 shown in FIG. 6 is selected, and when encoding {1, -1,1,}, the table of T = 1 shown in FIG. 7 is selected. Select a table.
Next, a code corresponding to the values of y and z is selected from the selected table. For example, when encoding [0,2,4], y = 4, z is obtained from the table of T = 0 shown in FIG.
Select the code 0110110111 according to = 0, {1, -1,
1} is coded, the code 0111 corresponding to y = 1 and z = 1 is selected from the T = 1 table shown in FIG. still,
When z = 0, that is, when run-length compression is performed, raw data to be repeated after the code selected from the table (in the present embodiment, 4-bit fixed color code information. In some cases, it may be the luminance data of). For example, [0,
[2, 4] is encoded, the code 011011 corresponding to y = 4 and z = 0 selected from the table of T = 0 shown in FIG.
After 0111, 0010 is added. Therefore, [0,
The code of [2, 4] is 01101101110010.

The result of converting the code string of FIG. 5 into an actual code is shown in FIG. 15. The image data capacity of FIG. 4 is 512 bits, whereas the data capacity of FIG. 15 is 404 bits. The algorithm of the present invention can be used to compress the original image data to 78.9%.

Next, the procedure for decompressing the code compressed by the above method will be described with reference to FIGS. FIG. 16 is a configuration example of the decompression circuit, and FIGS. 17 and 18 are flowcharts of the data decompression algorithm. In FIG. 16, 29 is an input buffer, 30 is a decoder, 32 is a mode register, 33 is a data register, 34 is a relative position register,
Reference numeral 35 is a dictionary address calculation unit, 36 is a selector, 37 is a length counter, 38 is an X and Y counter for specifying the position of the data to be expanded in the two-dimensional space, and 39 is data to be referred when the dictionary is copied. Created dictionary buffer, 71 is T
Table 43 is prepared for each value of, 43 is an input signal line to the input buffer 29, and 44 is an output signal line. The value of T in the table group 71 is shown in FIG. 3 when the position on the X coordinate of the pixel of interest specified by the X, Y counter 38 (the leading pixel of the partial string to be expanded) is x. It is obtained by the same method as the process 28 of the flow. In each table, the same information as the table shown in FIGS. 6 to 14 is stored for each value of T obtained based on the position x on the X coordinate of the pixel of interest. Also, there is no limitation on the value on the Y coordinate that the X, Y counter 38 can take, but the value on the X coordinate is 0 to H when the number of pixels of one line of the two-dimensional image data to be expanded is H. Limited to -1. In the present embodiment, since the number of pixels H of one line of the two-dimensional image data is 16, the value on the X coordinate that the X, Y counter 38 can take is 0 to 15.

Next, an outline of the operation of the decompression circuit configured as described above will be shown. First, the number of pixels H of one line of the two-dimensional image data to be expanded in the process 44 is input to the X, Y counter 38 and the decoder 30. Next, after the X and Y counter 38 is initialized in the process 45, the compressed data is fetched into the input buffer 29 through the input signal line 43 (process 46). In the second and subsequent expansion processes, the compressed data is fetched after the unprocessed bit string of the data stored in the input buffer 29. The input buffer 29 is composed of a FIFO, a shift register and the like. In the process 47, it is determined whether or not the bit string length stored in the input buffer 29 is 15 bits or more.
This is because the bit string length passed from the input buffer 29 to the decoder 11 must be equal to or longer than the longest bit string length of the data compressed by the data compression circuit. In the compression method according to the present embodiment, when the run length compression is performed and the code selected from the tables shown in FIGS. 6 to 14 is 11 bits, the raw data (4
By adding (fixed bit), the bit string length becomes the longest 15 bits. When the length of the bit string stored in the input buffer 29 is 15 bits or more, the process proceeds to step 48, and when it is less than 15 bits, the process returns to step 46.

In the process 48, the 15-bit portion from the beginning of the bit string stored in the input buffer 29 is decoded by the decoder 30.
Pass to. The decoder 30 determines the position x on the X coordinate of the pixel of interest specified by the X, Y counter 38, and the number of pixels H of one line of the two-dimensional image data to be expanded input in the process 44 (in this embodiment, H). H = 16) and the maximum detection column length N (N = 8 in this embodiment) used in the compression circuit, the value of T is obtained by the same method as the process 28 of the flow shown in FIG. A table corresponding to the value of T is selected from the group 71. Then, a variable length code having the longest matching bit string length from the head position with the received bit string is searched from the selected table. For example, in the 0th row of the code string shown in FIG. 15, when data 011011011100101 from the first position to the 15th bit is passed from the input buffer 29 to the decoder 30, the X coordinate of the pixel of interest specified by the X, Y counter 38. The value of T obtained from the position x above (in this case, x = 0, so T =
On the basis of (0), a table in which the same information as the table shown in FIG. 6 is stored is selected from the table group 71. Then, all the variable length codes held in the selected table are compared with the input data 011011011100101 bit by bit from the first bit, and the variable length codes which have been matched until just before any variable length code does not match are The desired variable length code hidden in the bit input data. That is, the variable length code having the longest matching bit string length from the head position of the input data is searched from the table. In this case, as can be inferred from FIG. 6, a variable length code 0110110111 having a run length mode as the decompression mode and a length of 4 is searched. Also, in the second row of the code string shown in FIG. 15, data 011011100111 from the start position to the 15th bit.
When 100 is passed from the input buffer 29 to the decoder 30, the value of T obtained from the position x on the X coordinate of the pixel of interest specified by the X, Y counter 38 (in this case, x =
On the basis of (T = 0, T = 0), a table in which the same information as the table shown in FIG. 6 is stored is selected from the table group 71. Then, the variable length code having the longest matching bit string length from the start position with the data 011011100111100 is searched from the selected table. In this case,
As can be inferred from the above, the variable length code 01101110 having the expansion mode as the dictionary copy mode, the relative position 1 and the length 5 is searched.

In process 49, the decoder 30 sets a mode flag in the mode register 32 for identifying the run length mode or the dictionary copy mode based on the variable length code retrieved from the selected table. , The length data is output to the length counter 37, and the relative position data is output to the relative position register 34 when the mode flag is the dictionary copy mode. Also, the decoder 30 outputs the decoded bit string length to the input buffer 29, and outputs the raw data to the data register 33 when the mode flag is the run length mode. For example, in the 0th row of the code string shown in FIG. 15, when the data 011011011100101 from the first position to the 15th bit is passed from the input buffer 29 to the decoder 30, the parameter of the variable length code 0110110111 found in the process 48 is The extension mode is the run length mode and the length is 4. Therefore, the decoder 30 sets the mode flag of the run length mode in the mode register 32, and the value 4 of the length data in the length counter 37.
In addition, the 4-bit part 0010 (raw data) following the variable length code 0110110111 retrieved in the process 48 is stored in the data register 33.
And the bit string length (10
14 bits (decoded bit string length) obtained by adding the bit string length of raw data (fixed to 4 bits) to (bit) are output to the input buffer 29. Further, in the second row of the code string shown in FIG.
When 11100111100 is passed from the input buffer 29 to the decoder 30, the variable length code 011011 searched in the process 48 is obtained.
For each of the 10 parameters, the expansion mode is the dictionary copy mode,
The relative position is 1 and the length is 5. Therefore, the decoder 30 sets the mode flag of the dictionary copy mode in the mode register 32, the value 5 of the length data in the length counter 37,
The value 1 of the relative position data is stored in the relative position register 34, and the retrieved bit string length of the variable length code 01101110, 8 bits (decoded bit string length), is input to the input buffer 2.
Output to 9. It should be noted that the decoded bit string length is output to the input buffer 29 because the unprocessed bit string in the data stored in the input buffer 29 is output after the decoder 30
This is to add data having the same bit string length as the bit string length decoded in.

When the mode flag output from the decoder 30 is the run length mode, the process 5 is executed through the process 50.
If the dictionary copy mode is selected, the process proceeds to step 53 through step 50. The mode flag output from the decoder 30 is held in the mode register 32 until one expansion operation is completed. Then, when one decompression operation is completed, the new mode flag output from the decoder 30 is held in the mode register 32, and the next decompression operation is started.

In the process 51, the run length mode expansion process is performed. In the extension processing of run length mode,
As shown in FIG. 20, the relative position register 34 and the dictionary address calculator 35 do not operate. First, the data register 33 holds the raw data output from the decoder 30, and the length counter 37 loads the length data output from the decoder 30 as an initial value. Next, based on the run-length mode flag held in the mode register 32, the raw data held in the data register 33 is output to the output signal line 44 via the selector 36 (operation 1). Next, in order to create a dictionary to be referred to when the next line data is expanded, the same data as the output data corresponds to the X, Y coordinate values specified by the X, Y counter 38 of the dictionary buffer 39. The address is registered (operation 2), the length counter 37 is decremented (operation 3), and the X coordinate value of the X, Y counter 38 is updated by 1 (operation 4). In the case of this embodiment, as described above,
The possible range of the X coordinate value of the X, Y counter 38 is 0 to 1.
It is 5. Therefore, when the X coordinate value of the X, Y counter 38 is 15, the X coordinate value becomes 0 when one X coordinate value is updated.
And the Y coordinate value is updated by one. In the process 52, the above operations 1 to 4 are repeated until the value of the length counter 37 becomes zero. As a result, decompressed data in which the raw data output from the decoder 30 is continuous by the length data output from the decoder 30 is generated.

In process 53, the dictionary copy mode expansion process is performed. It should be noted that in the expansion processing in the dictionary copy mode, as shown in FIG.
As shown at 0, the data register 33 does not work. First, the relative position register 53 holds the relative position data output from the decoder 30, and the length counter 37
Loads the length data output from the decoder 30 as an initial value. Next, the dictionary address calculation unit 35
Based on the X coordinate value specified by the X, Y counter 38 and the relative position data held in the relative position register 53, the address of the data to be referred to among the data stored in the dictionary buffer 39 is obtained (operation 5). Then, based on the dictionary copy mode flag held in the mode register 32, the data of the address specified by the dictionary address calculation unit 35 among the data stored in the dictionary buffer 39 is output to the output signal line 44 via the selector 36. Output (operation 6). Next, in order to create a dictionary to be referred to when the next line data is expanded, the same data as the output data corresponds to the X, Y coordinate values specified by the X, Y counter 38 of the dictionary buffer 39. The address is registered (operation 7), the length counter 37 is decremented (operation 8), and the X coordinate value of the X, Y counter 38 is updated by 1 (operation 9). In process 54, the above operations 5 to 9 are performed.
Repeat until the value of the length counter 37 becomes zero. As a result, decompressed data in which the data copied from the dictionary buffer 39 is continuous by the length data output from the decoder 30 is generated.

In the process 55, the bit string decoded by the decoder 30 from the head of the bit string stored in the input buffer 29 is discarded. Then, if there is still data to be decompressed, the process returns to the process 47, and if not, the flow ends (process 56).

In the above-described embodiment of compression, the longest subsequence existing in the dictionary within the range of the maximum detected sequence length N is searched from the dictionary reference range and coded, but in addition, it exists in the dictionary. When the longest subsequence is divided into a plurality of subsequences and then combined with other subsequences to create a subsequence within the range of the maximum detected sequence length N, and when compressing this, a non-longest subsequence A case may be considered in which, by combining columns, a partial column is created within the range of the maximum detected column length N and this is compressed.

In the former case, for example, the partial sequence b in FIG. 4B is divided into two partial sequences c "5543" and partial sequence d "4" in FIG. 4C, and the partial sequence d "4" is obtained. And "3" in 2 rows and 5 columns
Are combined to form a subsequence e “43”. The code of the subsequence c is {0, 1, 4}, and the subsequence e "43" is the same as "43" following one row and four columns one line before, so the code is {1,
-1,2}. Therefore, the codes in the second line are {0, 1,
4} {1, -1,2} [1,5,1] [1,4,1]
{1,0,3} [4,5,2] [6, A, 3] (this code is code a). In the latter case, for example, 2
In the row 0 column, the partial column “55” at the relative position 0 is selected, and in the 2nd row 2 column, the partial column “434” at the relative position +1 is selected.
As a result, the code in the second line is {0,0,2} {1,
1,3} {1, -1,1} [1,5,1] [1,4
1] {1,0,3} [4,5,2] [6, A, 3] (this code is code b).

Here, FIG. 4 shown in the above-mentioned compression embodiment.
The code for the second line in (a) has three patterns including the embodiment. The code on the second line in FIG. 5 is code c. When these codes a, b, and c are assigned to the actual codes shown in FIGS. 6 to 14, the code a is 49 bits,
Since the code b is 50 bits and the code c is 48 bits, the efficiency of the code c is good. However, when codes other than those shown in the tables of FIGS. 6 to 14 are assigned to the codes a, b, and c, different results are obtained, and the code a or the code b may be the shortest code. . Therefore, it is not always best to search for and encode the longest subsequence within the range of the maximum detection sequence length N, and the combination of subsequences in the dictionary that is the shortest when the actual code is assigned is the maximum detection sequence length. It is preferable to make it within the range of N and select it.

Even if the way of combining the partial strings in the dictionary is changed so that the code becomes the shortest as described above, the coding rule (the value of T obtained from the position x of the target pixel on the current line and , The head position of the same subsequence on the immediately preceding line and the length are not changed), the data decompression method is not affected.

[0050]

As described above in detail, according to the present invention, the capacity of the dictionary is very small because it is necessary to store only the immediately preceding line, and the dictionary is referred to within a range of high similarity.
Since a subsequence as long as possible within the range of the maximum detection sequence length is referred to, the compression rate is high and the compression and decompression can be processed at high speed. Further, the number of pixels in one line of the two-dimensional image data is H, the maximum detection column length is N (1 ≦ N ≦ H), and the position of the target pixel on the current line from the first pixel is x (0 ≦
x ≦ H−1), and when x = 0, T = 0, 1
When ≦ x ≦ H−N, T = 1, H−N + 1 ≦ x ≦ H−1
In the case of, T = x−H + N + 1, and for each value of T, the relative position between the leading pixel of the subsequence on the immediately preceding line and the target pixel and the length of the subsequence on the immediately preceding line are determined. A table to which different codes are assigned is prepared, the value of T is obtained based on the position x of the pixel of interest from the head pixel on the current line, and the relative position and the portion are selected from the table selected according to this value of T. Data compression is performed by outputting a code according to the length of the column, so that each table has a Huffman code table configured in advance according to the data to be compressed / decompressed, or redundancy is reduced with compression / decompression. By using a table that is optimized as described above, a higher compression rate can be obtained. Furthermore, by applying run-length compression or the like to the first line of the image data or the partial sequence that cannot be referred to the dictionary, a higher compression rate can be obtained. In addition, since the value that T can take is always 0 ≦ T ≦ maximum detection column length N, when the number H of pixels in one line of the two-dimensional image data is increased, the capacity of the table increases and compression / compression occurs.
It is possible to prevent the extension speed from decreasing.

[Brief description of drawings]

FIG. 1 is an explanatory diagram showing two-dimensional image data.

FIG. 2 is a diagram illustrating a configuration example of a data compression circuit.

FIG. 3 is a diagram for explaining a flow of a data compression operation.

FIG. 4 is an explanatory diagram showing image data before compression.

FIG. 5 is an explanatory diagram showing image data after compression.

FIG. 6 is a diagram showing a table of T = 0.

FIG. 7 is a diagram showing a table of T = 1.

FIG. 8 is a diagram showing a table of T = 2.

FIG. 9 is a diagram showing a table of T = 3.

FIG. 10 is a diagram showing a table of T = 4.

FIG. 11 is a diagram showing a table of T = 5.

FIG. 12 is a diagram showing a table of T = 6.

FIG. 13 is a diagram showing a table of T = 7.

FIG. 14 is a diagram showing a table of T = 8.

FIG. 15 is an explanatory diagram showing compressed image data to which actual codes are assigned.

FIG. 16 is a diagram showing a configuration example of a data expansion circuit.

FIG. 17 is a diagram for explaining the flow of a data decompression operation.

FIG. 18 is a diagram for explaining the flow of a data decompression operation.

FIG. 19 is a diagram for explaining the operation of the data decompression circuit in the run length mode.

FIG. 20 is a diagram for explaining the operation of the data expansion circuit in the dictionary copy mode.

[Explanation of symbols]

 1 dictionary 2 compression target partial sequence 3 partial sequence on dictionary 4 start position 5 target pixel 17 line buffer input signal line 18 dictionary buffer input signal line 19 code output signal line 43 input signal line 44 output signal line

─────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] November 25, 1994

[Procedure Amendment 1]

[Document name to be amended] Statement

[Correction target item name] 0031

[Correction method] Change

[Correction content]

In the processing of the first line in FIG. 4A, the 0th line is treated as a dictionary. Since (0,1) and (0,0) are compared and do not match, the next comparison is made with (0,1) and (1,0), which also does not match, so there is no matching subsequence in the dictionary. Then, run length compression is applied. Since the data from (0,1) to (2,1) is the same as 5, the code is [0,
5, 3]. 4 in (3,1) is (2,0), (3,1)
Since it does not match either 0) or (4,0), run length compression is applied and the code becomes [1,4,1].
3 in (4,1) is (3,0), (4,0), (5,0)
Matches (4,0) in (4,1) to (5,1)
Since (4,0) to (5,0) in the dictionary match, the code is {1,0,2}. Since (6,1) and (7,1) do not match with the dictionary data, the codes are [1,1,1] and [1,3,1], respectively. (8,1)
C of (7,0), (8,0), matches (9,0) in (9,0), and (8,1) to (9,1) and (9,0) in the dictionary. ) To (A, 0) match, the code is {1,1,2}. C of (A, 1) is (9,0),
(A, 0), (9,0) in (B, 0) and (A,
0). Here, (B, 1) and (A, 0) do not match, but (A, 1) to (C, 1) and (A,
Since 0) to (C, 0) match, the code is {3, 0,
3}. 6 of (D, 1) is (C, 0), (D,
0), (E, 0) in (C, 0), and (D,
1) to (F, 1) and dictionary (C, 0) to (E, 0)
Match, so the code is {6, -1, 3}. Therefore, the code in the first line is as shown in the first line in FIG.
[0,5,3] [1,4,1] {1,0,2} [1,
1,1] [1,3,1] {1,1,2} {3,0,3}
It becomes {6, -1,3} .

Claims (14)

[Claims] 1. A two-dimensional compression process is performed when the data of the immediately preceding line is referred to for sequentially scanned two-dimensional image data and a partial data string which is the same as the immediately preceding line by at least one pixel is detected in the current line. In the image data compression method, the number of pixels in one line of the two-dimensional image data is H, the maximum detection column length of the partial data sequence is N (1 ≦ N ≦ H), and the first pixel of the target pixel on the current line From x to x (0 ≦ x ≦
H-1), and when x = 0, T = 0, 1 ≦ x
When ≦ H−N, T = 1, and when H−N + 1 ≦ x ≦ H−1, T = x−H + N + 1. For each value of T, the beginning of the partial data string on the immediately preceding line. A table to which different codes are assigned according to the relative position of the pixel and the pixel of interest and the length of the partial data string is prepared, and the same partial data string is detected in the current line as at least one pixel or more from the immediately preceding line. In this case, the value of T is obtained based on the position x of the pixel of interest on the current line, the corresponding table is selected based on the value of T, and the start position of the partial data string on the immediately previous line is selected. A data compression method that outputs a code according to the length. 2. The invention according to claim 1, wherein the table is at least the same pixel position as a relative position between the target pixel of the input data of the current line and the head pixel of the same partial data string one line before, If it shifts to the left by one pixel,
And a code for three different cases in which one pixel is shifted to the right, are stored as variable-length codes. 3. The invention according to claim 1 or 2, wherein if the same partial data string as the immediately preceding line cannot be detected in the current line, the length of continuous identical data prepared for each value of T A data compression method characterized in that a corresponding code is output by referring to a run length table to which a different code is assigned according to the size. 4. The data compression method according to claim 3, wherein a code different from the code stored in the run length table is assigned to the code stored in the run length table. 5. The invention according to claim 4, wherein the table and the run-length table are integrated and the relative position is the same pixel position, or the pixel is shifted to the left by one pixel,
Codes of the same partial data string length in three different cases when shifted to the right by one pixel and codes of the same continuous data length in the case of run length are stored as different variable length codes. A data compression method characterized in that 6. When the data of the immediately preceding line is referred to for sequentially scanned two-dimensional image data and a partial data string that is the same as the immediately preceding line for at least one pixel or more is detected in the current line, compression of the overlapping part is performed. As data, 2
The number of pixels in one line of the dimensional image data is H, the maximum detection column length of the partial data column is N (1 ≦ N ≦ H), and the position of the target pixel on the current line from the first pixel is x (0 ≦ x ≤H-
1), and when x = 0, T = 0, 1 ≦ x ≦ H
In the case of −N, T = 1, and in the case of H−N + 1 ≦ x ≦ H−1, T = x−H + N + 1, and for each value of T, the head pixel of the partial data string on the immediately preceding line and the above This is a decompression method for two-dimensional image compression data in which different codes are sequentially input according to the relative position with respect to the pixel of interest and the length, and at least the decompressed data of the immediately preceding line is held in a buffer to try to decompress Position x of the target pixel on the current line
The value of T is obtained based on the value of T, and based on the value of T, a corresponding table is prepared from a table prepared for each value of T and to which different codes are assigned according to the relative position and the length. Select and extract the code from the input compressed data, refer to the table selected based on this code, and input the current line data from the buffer to the beginning position of the partial data string. A data decompression method, wherein data corresponding to the length of the partial data string following the corresponding bit is extracted and output as decompression data. 7. The transmission side sequentially scans 2
Refer to the data of the previous line for 3D image data,
When a partial data string that is the same as the previous line and at least one pixel is detected in the current line, the relative position between the leading pixel of the partial data string on the previous line and the target pixel on the current line, and the partial data The column length is obtained, the number of pixels in one line of the two-dimensional image data is H, the maximum detected column length of the partial data column is N (1 ≦ N ≦ H), and the position of the target pixel on the current line is x (0 ≦ x ≦ H−1), and T = 0 when x = 0, and T when 1 ≦ x ≦ H−N.
= 1 and H-N + 1≤x≤H-1, T = x-H + N
+1 and refers to a table prepared for each value of T, to which different codes are assigned according to the relative position and the length, outputs the corresponding code as compressed data, and at least at the receiving side. The decompressed data of the immediately preceding line is held in the buffer, and the value of T is obtained based on the position x from the head pixel on the current line of the pixel of interest of the compressed data to be decompressed,
The table corresponding to the value of T is selected, the code is extracted from the input compressed data, the table selected based on this code is referred to, and the data of the input current line is extracted from the table. A data compression / decompression method, wherein data corresponding to the length of the partial data string following the bit corresponding to the head position of the partial data string is extracted from the buffer and output as decompressed data. 8. The table according to claim 7, wherein the table is at least one pixel left when the target pixel of the input data of the current line and the leading pixel of the same partial data string one line before are at least at the same pixel position. A data compression / decompression method characterized in that codes for three different cases are stored, which are different in the case of shifting to, and in the case of shifting to the right by one pixel. 9. A reference memory means for holding data of one line before for sequentially input two-dimensional image data, and a plurality of consecutive memory devices within a predetermined length from the input current line signal. Buffer means for extracting a data string and storing it as a compression target partial data string, and data stored in the reference memory means has a partial data string that is the same as the partial data string following the pixel of interest of the compression target partial data string. And a first pixel of the partial data string on the data one line before stored in the reference memory means when the scanning and comparing means detects the same partial data string. The relative position with respect to the pixel of interest and the length of the partial data string are obtained, the number of pixels in one line of the two-dimensional image data is H, and the maximum detection string length of the partial data string is N (1 ≦ N ≦ H ) , The position of the pixel of interest from the first pixel on the current line is x (0 ≦ x ≦ H−
1), and when x = 0, T = 0, 1 ≦ x ≦ H
When N, T = 1, and when H−N + 1 ≦ x ≦ H−1, T = x−H + N + 1, and the relative position and the length of the partial data string prepared for each value of T. A data compression apparatus comprising: a code generation unit that refers to a table to which a different code is assigned in accordance with the above, and outputs the corresponding code as compressed data of the partial data string of the current line. 10. The table according to claim 9, wherein the table is
The relative position between the pixel of interest of the input data of the current line and the leading pixel of the same partial data string one line before is at least the same pixel position, one pixel left, and one pixel right different. A data compression device in which variable-length code codes for three cases are stored. 11. The method according to claim 9 or 10, wherein when the same partial data string as that of the immediately preceding line cannot be detected in the current line, the length of continuous identical data prepared for each value of T is changed. The data compression device is characterized by referring to a run length table to which different variable-length code codes are assigned and outputting the corresponding code. 12. The variable length code code stored in the run length table is assigned a variable length code code different from the variable length code code stored in the table. Data compression device. 13. When the immediately preceding data is referred to for sequentially input two-dimensional image data and a partial data string that is the same as the immediately preceding line by at least one pixel or more is detected in the current line, the compressed data of the overlapping part is obtained. , The number of pixels in one line of the two-dimensional image data is H, the maximum detection column length of the partial data column is N (1 ≦ N ≦ H), and the position of the target pixel on the current line from the first pixel is x ( 0 ≦ x ≦ H−1), T = 0 when x = 0, T = 1 when 1 ≦ x ≦ H−N, and T = when H−N + 1 ≦ x ≦ H−1. x-H
+ N + 1, and for each value of T, two-dimensional image compression data in which different codes are sequentially input according to the relative position between the leading pixel of the partial data string and the target pixel on the immediately preceding line and the length. A buffer memory means for holding the decompressed data of one line before, and the head of the partial data string on the immediately preceding line prepared for each value of T according to the code. Based on the inverse conversion table to which the relative position between the pixel and the target pixel and the length of the partial data string are assigned, and the position x of the target pixel of the compressed data to be expanded from the first pixel on the current line The value of T is obtained, the inverse conversion table corresponding to the value of T is selected, the code is extracted from the input data, and the inverse conversion table selected based on the code is selected. The data of the starting position and the length of the partial data string on the immediately preceding line is taken out from the inverse conversion table, and the partial data string following the bit corresponding to the starting position of the partial data string from the buffer memory means. A data decompression device, comprising: a decoding unit that extracts data corresponding to the length and outputs the decompressed data as decompression data. 14. When the data of the immediately preceding line is referred to for sequentially input two-dimensional image data and a partial data string which is the same as that of the immediately preceding line by at least one pixel or more is detected in the current line, an overlapping part is detected. 2 as the compressed data
The number of pixels in one line of the dimensional image data is H, the maximum detection column length of the partial data column is N (1 ≦ N ≦ H), and the position of the target pixel on the current line from the first pixel is x (0 ≦ x ≤H-
1), and when x = 0, T = 0, 1 ≦ x ≦ H
In the case of −N, T = 1, and in the case of H−N + 1 ≦ x ≦ H−1, T = x−H + N + 1, and for each value of T, the head pixel of the partial data string on the immediately preceding line and the above If different codes are sequentially input according to the relative position with respect to the pixel of interest and the length, and if the same partial data string as the previous line cannot be detected in the current line, the above-mentioned T A two-dimensional image compression data decompression device in which different codes and the same data are sequentially input according to the length of consecutive identical data for each value of, and the current pixel of interest of the compressed data to be decompressed. A counter for counting the position x from the first pixel on the line, a buffer memory means for holding the decompressed data one line before, and a previous code corresponding to the input code prepared for each value of T line At the relative position between the first pixel of the partial data string and the pixel of interest, and the data of the length of the partial data string, or an inverse conversion table to which the run length is assigned, and is counted by the count value of the counter. The value of T is obtained based on the position x of the pixel of interest from the first pixel on the current line, the inverse conversion table corresponding to the value of T is selected, and the code is extracted from the input data. Then, the inverse conversion table selected based on the code is referred to, and a mode flag for identifying whether or not the same partial data string as the immediately preceding line is detected in the current line is output from the inverse conversion table. When a decoder that retrieves data of relative position and length, or data of the same continuous data length, and the same partial data string as the previous line is detected on the current line First decoding means for extracting data of the length of the partial data string following the bit corresponding to the relative position from the buffer memory means and outputting it as decompressed data; A second decoding means for continuously outputting the data following the code by the length of the same continuous data when the data string cannot be detected;