JP2594766B2 - Data compression method and data compression method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression method,
In particular, it relates to a reversible coded data compression method.

[0002]

2. Description of the Related Art Conventionally, this kind of data compression method has been used in transmission of a large amount of data such as image data in order to prevent the amount of data to be transmitted from becoming enormous. FIG. 4 is a block diagram showing one embodiment of the prior art, and FIG.
FIG. 4 is an explanatory diagram of one embodiment of a conventional data compression method.

Referring to FIG. 4, a conventional data compression method comprises a current raster data input means 401 for inputting original image data, and a run-length encoding means 402 for encoding a data code and outputting compressed image data. Is done.

[0004] The current raster data to be coded given to the current raster data input means 401 is supplied to a run length coding means 402. The current raster data is run-length compressed by the run-length encoding unit 402.
The first byte as an output code is composed of a flag indicating a data type (0: different data designation, 1: same data designation), and a length (00000000 to 1111111: consecutive number of bytes of the same data and different data-1). Have been. The second and subsequent bytes indicate codes of the same or different data. As described above, the compressed image data is output.

Next, a specific example will be described.

For example, as shown in FIG. 5, the current raster data 411 provided to the current raster data input means 401
Is supplied to the run-length encoding means 402. Then, the current raster data 411 is run-length compressed by the run-length encoding unit 402. In this specific example, the encoding code 412 of the part (a) of the current raster data 411 is used.
Is a flag "1" in which the first byte indicates the type of the same data.
And the length “0000100” (5-1), and the second
Represents a data code with the same byte. The encoding code 413 of the part (b) of the current raster data 411 is the first
The byte indicates the flag “0” indicating the type of the difference data and the length “0000010” (3-1), and the second and subsequent bytes indicate the different data code. Current raster data 4
Since the encoding code 414 of the portion (c) of 11 is 130-point continuous data, encoding is performed by dividing the data into two. The first byte indicates the flag “1” indicating the type of the same data and the length “1111111” (128-1), and the second byte indicates the same data code. In addition, the third byte has a flag “1” indicating the type of the same data and a length “0”.
0001 "(2-1), and the fourth byte represents the same data code. Therefore, the entire encoded code 415 in this specific example is a partial (a) encoded code 412.
And the part (b) encoding code 413 and the part (c) encoding code 414 are combined.

[0007] As described in detail in Japanese Patent Application Laid-Open No. 1-47173, as a more advanced conventional technique, there is a technique of performing image compression using exclusive OR means. FIG.
FIG. 2 is a block diagram of an image compression method using the exclusive OR means.

Exclusive OR operation unit 73 (EOR operation unit)
Are the current line read out from the corresponding addresses of the current line memory 71 and the previous line memory 72 in byte units and 1
An exclusive OR operation is performed between the binary image data of the immediately preceding line and the result is output in byte units. Encoding section 74
Analyzes the byte data output from the arithmetic unit 73,
Execute the encoding algorithm. The encoding algorithm determines whether each bit of the input byte data is all 0, all 1, or any of the other three modes, and further has the same mode as the mode of the byte data having the same mode. Encode in the byte data format using the continuous number of byte data.

[0009]

In this conventional data compression method, the same code portion that is continuous in the row direction is compressed. Therefore, long image data that is continuous in the row direction is compressed. Although a considerable compression rate can be obtained, there is a problem that a very high compression rate cannot be obtained for character data having a short length that is continuous in the line direction. Similarly, a data compression method using exclusive OR means is effective when the front and rear are completely the same or completely different. For example, there is a problem that a very high compression ratio cannot be obtained.

[0010]

According to a first aspect of the present invention, in a data compression method for encoding input original image data and outputting compressed image data, a current raster data input means for inputting the original image data includes: Raster data input means for inputting raster data one line before the current raster data; current raster data provided by the current raster data input means; and bytes of previous raster data provided by the previous raster data input means. First calculating means for calculating the number of matching code points in units, second calculating means for calculating the maximum number of identical code points in byte units in the current raster data, the first calculating means and the second calculating means The matching code points calculated by the calculating means are compared with the same code points, and if the matching code points are large, When the addition the matching code number with all cases of identity first cord number is large is selected raster data which is the largest same code in said current raster data to the raster initial data is large Deta first
When the byte is the first value and the number of the same code points is large, the first byte is the second value and the second byte is the raster initial data encoded code which is the most same code. Exclusive OR operation means for performing an exclusive OR operation of the raster initial data and the current raster data, and setting a byte of NULL data in the exclusive OR value to “0” and a byte other than the NULL data to “0”. Raster information generating means indicated in bits by 1 ", and raster information encoded code is generated by encoding the raster information obtained by the raster information generating means into 8 groups as one group and performing run length encoding. Raster information encoding means, and a run length code for a code other than the NULL data in the exclusive OR value Exclusive OR value encoding means for generating an exclusive OR value encoded code by performing the above operation, wherein the raster initial data encoded code, the raster information encoded code, and the exclusive OR value encoded code are provided. Are all coded codes.

According to a second aspect of the present invention, in a data compression method for encoding input original image data and outputting compressed image data, the original image data is input as current raster data, and then the current raster data is input. After inputting the raster data one line before the raster data as the previous raster data, the number of matching code points of the current raster data and the previous raster data in byte units and the maximum number of identical code points in byte units of the current raster data Is calculated, and the number of matching code points is compared with the number of the same code points. When the number of matching code points is large, the previous raster data is used. The raster data which is the code is selected as the raster initial data. Is a first value and if the number of identical codes is large, generates a raster initial data encoded code in which the first byte is a second value and a second byte is the most identical code, The exclusive-OR of the raster initial data and the current raster data is calculated, and the byte of NULL data in the exclusive-OR value is set to “0”, and the byte other than the NULL data is set to “1” as bit-by-bit raster information. And generating the raster information encoded code by encoding the raster information as a group of 8 bits and performing run length encoding, and performing run length encoding on the exclusive OR value other than the NULL data. Generating an exclusive OR value encoding code by using the raster initial data encoding code and the raster Characterized by a broadcast encoded code and the exclusive-OR value encoded code and all encoded code.

[0012]

Next, the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention, and FIGS. 2 and 3 are explanatory diagrams of the operation of the present invention.

Referring to FIG. 1, an embodiment of the present invention comprises a current raster data input means 1 for inputting original image data,
A previous raster data input means 2, a raster initial data setting means 3, an exclusive OR operation means 4 for taking an exclusive OR of the raster initial data and the current raster data, and converting the corresponding same code into NULL data; The system comprises a raster information creating unit 5 that indicates a change position of raster data in bit units, and a run-length encoding unit 6 that converts data codes into run-length codes and outputs compressed image data.

The raster initial data setting means 3 calculates the number of coincidence code points between the previous raster data and the current raster data, and the second calculation means calculates the maximum number of identical code points in the current raster data. 32 and the first
Is compared with the second calculating means 32. If the former is large, the previous raster data is used, and if the latter is large, raster data such that all are the same code in the current raster data is used as the initial raster data. Comparison and selection means 33 for selecting data.

The run-length encoding means 6 encodes the raster information into 8 bits as one group, and encodes the run-length into raster information encoding means 61;
An exclusive OR value encoding unit 62 that performs run-length encoding using the result obtained by the exclusive OR operation unit.

Next, the operation of this embodiment will be described with reference to FIGS.

The current raster data to be coded given to the current raster data input means 1 and the previous raster data given to the previous raster data input means 2 are supplied to a raster initial data setting means 3. Step (a): The first calculating means 31 calculates the score of the matching code at the corresponding position between the previous raster data and the current raster data. Step (b): The second calculating means 32 calculates the score of the same code having the highest frequency in the current raster data. Step (c): The comparison / selection unit 33 compares the scores obtained by the first calculation unit 31 and the second calculation unit 32,
If the former score is high, select the previous raster data as the initial raster data.If the latter score is high, select raster data such that all the codes in the raster data are the most frequent codes in the current raster data. Select as raster initial data and output.

In this way, the raster data obtained by the first calculation means is selected in the case of data having a strong relation between the preceding and succeeding raster data, and the second data is obtained in the case of the data having a strong relation in the next row. The raster initial data obtained by the calculation means is selected.

The output code is composed of (first byte) or (first byte + second byte). The first byte is
Raster initial data designation (00: previous raster data is used as raster initial data. 01: all raster data that is the most frequent code in the current raster data is used as raster initial data). The first byte is “0”
Only when the value is 1 ", the second byte exists and indicates the most frequent code in the current raster data. Step (d): The exclusive OR operation means 4 performs an exclusive OR operation on the raster initial data and the current raster data. Take the sum
A portion where the corresponding position is the same code is converted into a NULL code to generate an exclusive OR value.

Step (e): raster information creating means 5
Is NU as information indicating the change position of the exclusive OR value.
The LL code is represented by “0”, and the other LL code is represented by “1” in bit units to create raster information. The raster information and the exclusive OR value are supplied to the run length encoding means 6. Step (f): The raster information is encoded by the raster information encoding means 61 into 8 bits as one group, and run-length compressed. The first byte as an output code is a flag (0: different data designation,
1: Specify the same data) and Length (00000000)
1111111: the number of consecutive bytes of the same data and the different data-1) is configured in units of bits, and indicates that 8 bits are coded as one group. The second and subsequent bytes indicate that the raster information is coded as a group of 8 bits. Step (g): Exclusive OR data obtained by combining data codes other than NULL data of the exclusive OR value is run-length compressed by the exclusive OR value encoding means 62.
The first byte of the output code is the raster information encoding means 6.
Same as 1. The second and subsequent bytes indicate exclusive OR value data. The compressed image data is output as described above.

Next, a specific example will be described.

For example, as shown in FIG. 3, the previous raster data 311 and the current raster data 31 given by the current raster data input means 1 and the previous raster data input means 2 are provided.
2 is supplied to the raster initial data setting means 3. First, the first raster data 311 is calculated by the first calculating means 31.
And the corresponding code point at the corresponding position of the current raster data 312 and the second calculating means 32 calculates the highest frequency identical code point in the current raster data 312,
Each score is compared by the comparison and selection means 33, and raster initial data 313 is set. In this specific example, since the result (11 points) of the first calculation means 31 is larger than the result (2 points) of the second calculation means 32, the previous raster data 311 becomes the raster initial data 313 as it is. In the raster initial data encoding code 314, the raster initial data designation of the first byte is indicated by “00H”. There is no initial data code for the second byte.

Next, the exclusive OR operation means 4 takes the exclusive OR of the raster initial data 313 and the current raster data 312 to obtain an exclusive OR value 315. Then, the raster information creating means 5 creates raster information 316 in a bit unit such that the NULL code is "0" and the other codes are "1" in the exclusive OR value 315. The raster information 316 and the exclusive OR value 315 are supplied to the run length encoding means 6. First, the raster information 316 is coded by the raster information encoding unit 61 into 8 bits as one group, and is run-length compressed. In this specific example, the raster information 316 is “92
H, 41H. The first byte of the raster information encoding code 317 represents a flag “0” indicating the type of the difference data and a length “0000001” (2-1) in bit units, and is 8 bits. Is encoded as one group. The second and subsequent bytes indicate that the raster information 316 is encoded as 8 bits as one group.Next, an exclusive OR value 315 is an exclusive OR value. The value encoding means 62 converts the data into exclusive OR data 318 arranged in a format other than the NULL code and performs run length compression.In this specific example, the first byte of the exclusive OR value encoded code 319 is the same data. The flag “1” indicating the type of “1” and the length “0000100” (5-1) are expressed in bits, and 8 bits are coded as one group. Shown. The second byte represents the data code are identical. Hence, all the encoded code 320 in this specific example, the raster initial data coded code 314
, And a raster information encoding code 317 and an exclusive OR value encoding code 319.

As can be seen from the above-described embodiment, according to the present invention, in the case of data having a strong relationship between the preceding and following raster data, the raster initial data obtained by the first calculating means is selected. The compression ratio increases. Further, in the case of data having little relation between the preceding and succeeding raster data, if there is a relation in the same row even if the length continuous in the row direction is short, the raster initial data obtained by the second calculation means is selected. By doing so, the compression ratio increases.

[0026]

As described above, the data compression method according to the present invention compares the number of coincident code points of the current raster data and the previous raster data with the number of identical code points of the highest frequency in the current raster data. After setting the raster data as raster data such that the latter is the same code with the highest frequency in the current raster data if there are many, the exclusive OR of the initial raster data and the current raster data is taken and the corresponding Same code N
Since the data is converted into the UL data, the information on the change position of the raster data is indicated in units of bits, and the data code is run-length coded, the effect of enabling efficient data compression independent of the type of transmission data is achieved. There is.

[Brief description of the drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention.

FIG. 2 is an operation flowchart showing one embodiment of the present invention.

FIG. 3 is an operation explanatory diagram of the present invention.

FIG. 4 is a block diagram showing one embodiment of a conventional data compression method.

FIG. 5 is a diagram illustrating the operation of a conventional data compression method.

FIG. 6 is a block diagram showing another embodiment of the conventional data compression method.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Current raster data input means 2 Previous raster data input means 3 Raster initial data setting means 4 Exclusive OR operation means 5 Raster information creation means 6 Run length encoding means 31 First calculation means 32 Second calculation means 33 Comparison Selection means 61 Raster information encoding means 62 Exclusive OR value encoding means 71 Current line memory 72 Previous line memory 73 EOR operation unit 74 Encoding unit 311 Previous raster data 312 Current raster data 313 Raster initial data 314 Raster initial data coincidence Encoding code 315 Exclusive OR value 316 Raster information 317 Raster information encoding code 318 Exclusive OR data 319 Exclusive OR value encoding code 320 All encoding code 401 Current raster data input means 402 Run length encoding means 411Current raster data 412 Part (a) encoded code 413 Part (b) encoded code 414 Part (c) encoded code 415 Full encoded code

Claims (2)

(57) [Claims] 1. A data compression method for encoding input original image data and outputting compressed image data,
Current raster data input means for inputting the original image data, previous raster data input means for inputting raster data one line before the current raster data, and current raster data provided by the current raster data input means; First calculation means for calculating the number of coincidence code points in byte units of the previous raster data provided by the raster data input means, and second calculation for calculating the maximum number of identical code points in byte units in the current raster data Means,
The coincidence code points calculated by the first calculation means and the second calculation means are compared with the same code points. If the coincidence code points are large, the previous raster data and the same code points are compared. If there are many, the raster data that is the most same code in the current raster data is selected as the raster initial data, and if the number of matching code points is large, the first byte is the first value and the same code point is If the number is large, the first byte is a second value and the second byte is a raster initial data coded code in which the second byte is the most same code, and exclusive and exclusive of the raster initial data and the current raster data are generated. Exclusive OR operation means for performing an OR operation, and setting the byte of NULL data in the exclusive OR value to "0"
Raster information creating means for indicating bytes other than UL data in bits by "1"; and raster information obtained by encoding the raster information obtained by the raster information creating means into 8 groups as one group and run-length encoding. Raster information encoding means for generating an information encoding code; and the NUL in the exclusive OR value
Exclusive OR value encoding means for generating an exclusive OR value encoded code by run length encoding a code other than the L data, wherein the raster initial data encoded code and the raster information encoded code are provided. And a data compression method wherein the exclusive-OR value coding code is a full coding code. 2. A data compression method for encoding input original image data and outputting compressed image data,
After inputting the original image data as the current raster data, and then inputting the raster data one line before the current raster data as the previous raster data, matching the current raster data with the previous raster data in byte units The number of code points and the maximum number of identical code points in byte units in the current raster data are calculated, and the number of coincident code points is compared with the number of identical code points. If the number of code points is large, the raster data which is the most identical code in the current raster data is selected as the raster initial data, and if the number of matching code points is large, the first byte is the first value and the same When the number of code points is large, the first byte is the second value and the second byte is the most same code. A star initial data encoding code is generated, and then an exclusive OR of the raster initial data and the current raster data is taken, a byte of NULL data in the exclusive OR value is set to “0”, and a byte other than the NULL data is set. Are represented as raster information in bit units by “1”, the raster information is coded as a group of 8 bits, and run-length encoded to generate a raster information encoded code. An exclusive-OR code is generated by run-length coding a code other than the NULL data, and the raster initial data code, the raster information code, and the exclusive-OR code are generated. Is a fully coded code.