JP2885235B1 - Data compression method and machine readable recording medium recording compression program - Google Patents

Abstract

A high compression ratio is achieved regardless of the type of image. Each time one pixel value is input from an image to be compressed, a comparison unit compares the pixel value with the immediately preceding pixel value stored in a storage unit. Process values. If they do not match, if the value of the counter 14a is equal to or greater than 1, after outputting a coincidence code in which the number of continuations is set, the comparing means 15 outputs
Is checked to see if it matches any of the past pixel values, and if matched, outputs an index code that sets the index number of that pixel value, rewrites the storage means 17, and processes the next pixel value . If there is no match with the past data, the difference with the immediately preceding pixel value is obtained by the difference acquisition means 16, and if the difference value is equal to or less than a predetermined value, a difference code in which the difference value is set is output. An immediate code in which the pixel value itself is set is output, the storage unit 17 and the storage unit 18 are rewritten, and the next pixel value is processed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a data compression method, and more particularly to a lossless compression method.

[0002]

2. Description of the Related Art There are two types of compression methods for images, an irreversible compression method and a lossless compression method. The irreversible compression method can generally realize a high compression ratio, but cannot completely reproduce the original image because some distortion is added in the process of compression and expansion. On the other hand, the lossless compression method is generally inferior to the irreversible compression method in the compression ratio, but since it can faithfully reproduce the original image through the process of compression and decompression, it is awarded in fields where image quality degradation is not allowed. Have been. The present invention relates to this latter lossless compression.

As a reversible compression method for an image,
The following methods have been conventionally proposed or put into practical use.

(1) Difference method A method of reducing the entropy of information by taking a difference between pixels, as represented by the lossless mode (lossless mode) of JPEG, and then compressing the information by Huffman coding or arithmetic coding. . (2) Run-length method A method of compressing by recording the number of consecutive pixels having the same value (run-length) together with the pixel value, as represented by packbits (one of the compression methods of the TIFF format). . (3) Dictionary method As typified by the LZW method, a registered encoded pixel sequence that matches the input pixel sequence at the longest is retrieved from the dictionary, and is compressed by encoding using a dictionary reference number. .

[0005]

As described above, various methods have conventionally been known as lossless compression methods for images, but each has advantages and disadvantages. For example, the run-length method is simple in processing and has a good compression ratio for a specific image such as a binary image consisting of a simple and large area, but a natural image such as a photograph can hardly be compressed. Becomes incompressible. The dictionary method has a simple algorithm and is often used for file compression and the like. However, in principle, if the same pattern does not appear repeatedly, it cannot be compressed and may not be compressed. On the other hand, the difference method can uniformly compress the image among the three types of conventional methods regardless of the type of image. Inferior. Further, since the code length of the Huffman code / arithmetic code is variable in bit units, there is also a problem that data processing in bit units is required and processing becomes complicated.

The present invention has been proposed in view of such circumstances, and a first object of the present invention is to provide a compression method which provides the highest compression ratio among the above three conventional methods for various types of images. An object of the present invention is to provide a data compression method capable of obtaining a compression ratio comparable to that of the data compression method.

Another object of the present invention is to provide a data compression method that does not require data processing in bit units.

[0008]

In order to achieve the first object, the present invention provides a plurality of types of methods for reducing the information entropy of an image, and for each pixel, a method with the highest compression rate is used. Apply That is, a matching code that sets the number of times the same data value as the immediately preceding data value continues, a difference code that sets the difference between the immediately preceding data value, and the index of the processed data value stored in the past data storage unit. Using a total of four types of codes, an index code that sets a number and an immediate code that sets the data value itself, the data amount after compression is smaller for each data in order from the beginning of the data group to be compressed. The data compression is performed by selecting a certain code. More specifically, when an image is targeted, data is compressed by the following steps.

(A) a step of initializing the immediately preceding data storage means, the past data storage means and the continuous number counter (b) a step of inputting one pixel value from the image to be compressed (c) a pixel value input in step b And (d) when the number of consecutive times has reached the maximum value, the number of consecutive times is set when the number of consecutive times has reached the maximum value. Returning the coincidence code to initialize the continuous number counter, and then returning to step b. (E) When the comparison does not match in step c, if the consecutive number counter is other than the initial value, output the coincidence code that sets the number of consecutive times. And initializes the continuous number counter, searches the past data storage means for holding the pixel values which appeared in the past with an index number, and performs step searching. (F) When the index number is obtained in step e, an index code in which the index number is set is output, and the index code input in step b is obtained. (G) When the index number is not obtained in step e, the pixel value input in step b and the pixel value stored in the immediately preceding data storage unit are stored. (H) When the difference obtained in step g can be set to a difference code having a size smaller than the size of the immediate code set in the pixel value input in step b, the difference is obtained in step g. The difference code that sets the obtained difference is output. Otherwise, the immediate code that sets the pixel value input in step b is used. And force, also stored in the historical data storage means by a predetermined storage method stores the pixel values input in step b immediately before the data storage means, the flow returns to step b step

Further, in the present invention, in order to achieve the above-mentioned second object, all kinds of codes are byte-based codes.

Further, in the present invention, a plurality of types of difference codes having different maximum difference values that can be set are used as difference codes.

The present invention further has the following steps in order to achieve the first object and to enable high-speed decompression of compressed data. (I) Every time the processing of a predetermined number of pixels is completed, if the continuous number counter is other than the initial value, a coincidence code in which the number of continuous times is set is output, and the immediately preceding data storage means, past data storage means, and continuous number counter are output. To initialize and return to step b

[0013]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing an example of a data compression apparatus to which the present invention is applied. The data compression device 1 of this example includes functional units such as a control unit 11, a data input unit 12, a data output unit 13, a previous data comparison unit 14, a past data comparison unit 15, and a difference acquisition unit 16, , Storage means such as the immediately preceding data storage means 17 and the past data storage means 18. Further, it is connected to the image file 2, the compressed file 3, and the user input / output device 4.

The data input means 12 is means for inputting image data to be compressed from the image file 2. In this embodiment, the pixel values of the image data are represented by three 8-bit color values R, G, and B, respectively. The scanning order of the image, that is, the data input order is a so-called raster method in which the scanning is performed rightward from the leftmost pixel of the image, and when the rightmost pixel is reached, the scanning is performed rightward again from the left end of the next line. The input source of image data to be compressed is not limited to a file.

The immediately preceding data storage means 17 is a means for holding a pixel value immediately before the pixel value currently being processed.

The past data storage means 18 is a means for storing a plurality of types of pixel values which appeared in the past. In this embodiment, a maximum of eight pixel values are recorded as shown in FIG. In FIG. 2, E0 to E7 are entries, which are assigned index numbers 0 to 7, respectively. At the time of initialization, the columns of the pixel values of the entries E0 to E7 are all set to 0, and each time a pixel value to be stored appears, the entry E0 → E1 →.
And the pixel values are stored in order from the entry having the smallest index number. When a new pixel value is stored in a state where the pixel value is stored up to the entry E7 of the index number 7, the process returns to the entry E0 of the index number 0, and is reused again from the entry with the smallest index number. In other words, it overwrites.

The immediately preceding data comparing means 14 stores the pixel value inputted this time by the data input means 12 and the immediately preceding data storing means 1.
7 is a means for comparing with the immediately preceding pixel value stored in the memory 7. If they match, the internal continuous number counter 14
a is incremented by one. Continuous number counter 14
In this embodiment, a can be counted from an initial value of 0 to a maximum of 32.

The past data comparison means 15 stores the pixel value inputted this time by the data input means 12 and the past data storage means 1.
This is a means for comparing with the pixel values that have appeared in the past and stored in 8. The matching pixel value is stored in the past data storage unit 18.
, Its index number is retrieved.

The difference acquisition means 16 is provided with the data input means 12
Is a means for calculating a difference for each color value between the currently input pixel value and the immediately preceding pixel value stored in the immediately preceding data storage means 17.

The data output means 13 is means for outputting compressed data to the compressed file 3. The output destination of the compressed data is not limited to a file.

The control means 11 is a means for controlling the whole of the data compression apparatus 1. Based on the processing results of the immediately preceding data comparison means 14, the past data comparison means 15 and the difference acquisition means 16, the control means 11 controls the head of the image to be compressed. Data is compressed by selecting a code with a smaller data amount after compression for each pixel in order from the pixel, and the compressed data is output to the compressed file 3 through the data output unit 13.

FIG. 3 shows an example of the format of a compression code used in this embodiment. As shown in the figure, in the present embodiment, a 1-byte matching code (FIG. 7A), a 1-byte index code (FIG. 6B), a difference code of 1 byte, 2 bytes and 3 bytes ( (C) to (e) in FIG. 6, a total of six types of compression codes, that is, a 4-byte immediate code (f) in FIG. Each of them is data in units of bytes so that data processing in units of bits becomes unnecessary.

The immediate code shown in FIG. 3F is used when outputting an uncompressed pixel value itself, such as the first pixel of an image. The first byte contains a fixed bit string (11111000) indicating that the code is an immediate code, and
Each color value of R, G, B is put in the byte.

The matching code shown in FIG. 3A is used when compressing a portion where the same pixel value continues. 5th bit ~
The seventh bit contains a fixed bit string (110) indicating that the code is a coincidence code, and the length term is contained in a total of 5 bits from the 0th bit to the 4th bit. The length term indicates how many subsequent pixel values are the same as the immediately preceding pixel value. When 0, 0 indicates that one identical pixel continues, and 1 indicates that two identical pixels continue. ,..., The maximum value of 31 indicates that 32 same pixels as the immediately preceding pixel continue.

The index code shown in FIG. 3B is used when compressing the same pixel value as the pixel value stored in the past data storage means 18. The third to seventh bits contain a fixed bit sequence (11110) indicating that the code is an index code, and the index term is contained in a total of three bits from the 0th bit to the second bit. In the index item, the index number of the pixel value having the same value in the past data storage unit 18 is set.

The difference codes shown in FIGS. 3C to 3E are used for compressing a pixel value by a difference from the immediately preceding pixel value, and FIG. 3C shows a 1-byte 1-byte difference code. )
Is a 2-byte differential code in a 2-byte format, and (e) is a 3-byte differential code in a 3-byte format.

In the 1-byte differential code, a fixed bit (0) indicating that the code is a 1-byte differential code is inserted in the 7th bit, and the 5th and 6th bits have a total of 2 bits of the color value R. In the difference ΔR, the difference ΔG of the color value G is entered in a total of two bits of the third and fourth bits, and the difference ΔB of the color value B is entered in the three bits of the 0th bit to the second bit.

In the two-byte differential code, a fixed bit string (10) indicating that the code is a two-byte differential code is inserted into a total of two bits of the sixth and seventh bits of the first byte. The difference ΔR is a total of 5 bits of the first to fifth bits, and the difference ΔG is a total of 4 bits of the 0th bit of the first byte and the fifth to seventh bits of the subsequent byte.
However, the difference ΔB is entered in a total of 5 bits from the 0th bit to the 4th bit of the second byte.

In the 3-byte differential code, a fixed bit string (111) indicating that the code is a 3-byte differential code is added to a total of 4 bits from the fourth bit to the seventh bit of the first byte.
0) is inserted, and a difference ΔR is added to a total of 7 bits from the 0th bit to the 3rd bit of the 1st byte and the 5th to 7th bits of the following byte, and the byte following the 0th to 4th bits of the 2nd byte The difference ΔG is entered in a total of 6 bits of the seventh bit, and the difference ΔB is entered in a total of 7 bits of the 0th to 6th bits of the third byte.

When the differences ΔR, ΔG, and ΔB of R, G, and B from the immediately preceding pixel value can be expressed by 2, 2, and 3 bits or less, respectively, a 1-byte difference code is used.
If it can be represented by 4 or 5 bits or less, a 2-byte differential code is used, and if it can be represented by 7, 6, 7 bits or less, a 3-byte differential code is used.

FIG. 4 is a flowchart showing a processing example of the data compression apparatus 1 of FIG. Hereinafter, the operation of this embodiment will be described with reference to FIGS. When the data compression apparatus 1 is realized by a computer having a CPU and a memory, a compression program describing the processing shown in FIG. 4 is stored in a machine-readable recording medium such as a CD-ROM, a semiconductor memory, and a magnetic disk (FIG. 1). M1), the compressed program of the recording medium M1 is read by the computer, and the computer is controlled to operate so that the computer functions as the data compression device 1 of FIG.

When a compression request designating an image file 2 for storing image data to be compressed and a compression file 3 for storing a compressed image is input from the user input / output device 4 to the data compression device 1, the data compression device Under the control of the first control means 11, the processing shown in FIG. 4 is started.

First, the control means 11 initializes each part of the apparatus (S1). In this process, the pixel values in the immediately preceding data storage unit 17 and the past data storage unit 18 are all initialized to 0, and the continuous number counter 14 in the immediately preceding data comparison unit 14 is initialized.
a is also initialized to 0.

Next, the control means 11 includes a data input means 12
Is used to input the first pixel value from the image file 2 (S2). The input pixel value is transmitted to the control unit 11, the immediately preceding data comparison unit 14, the past data comparison unit 15, and the difference acquisition unit 16.

Since the control means 11 is the first pixel value after initialization (YES in S4), the control means 11 outputs an immediate code in which the transmitted pixel value is set to the data output means 13 (S4).
5) It is stored in the immediately preceding data storage unit 17 (S6), and further stored in the entry E0 of the index number 0 of the past data storage unit 18 (S7). Then, returning to step S2, the next pixel value is input. The data output means 13
Outputs the codes output from the control means 11 to the compressed file 3 collectively each time or when a predetermined amount is accumulated.

The second and subsequent pixel values may be compressed using the immediately preceding pixel value or the past pixel value.

First, the control means 11 reads from the immediately preceding data comparison means 14 the result of comparison between the currently input pixel value and the immediately preceding pixel value stored in the immediately preceding data storage means 17, and determines whether or not both match. Is determined (S8). If they match, the continuation number counter 14a is incremented by 1 (S9). Then, it is determined whether or not the count value of the consecutive number counter 14a after the increment has reached the maximum value (32 in this example) (S10). If not, the process returns to step S2 to process the next pixel value.
If the pixel value has reached the maximum value, that is, the same pixel value as the immediately preceding pixel value stored in the immediately preceding data storage unit 17 is equal to 32.
If the number of consecutive occurrences is found, a coincidence code in which the value (31) of the count value -1 is set in the length term of FIG. 3A is output to the data output means 13, and the value of the continuous number counter 14a is set to 0. (S11), and returns to step S2 to process the next pixel value.

On the other hand, if the currently input pixel value does not match the immediately preceding pixel value stored in the immediately preceding data storage means 17 (NO in S8), the control means 11 performs compression by another compression format. It is checked whether it is possible or not (S14, S1
5) Before that, it is checked whether or not the value of the continuous counter 14a is larger than 0 (S12).
The coincidence code in which the value of the count value -1 is set to the length term in FIG. 3A is output to the data output means 13, and the value of the continuous number counter 14a is initialized to 0 (S13).

In step S14, the result of comparison between the currently input pixel value and the past pixel value stored in the past data storage unit 18 is read from the past data comparison unit 15, and the currently input pixel value is compared with the currently input pixel value. It is determined whether there is matching past data. If there is a matching past data, the past data comparing unit 15 outputs the index number of the entry storing the matching pixel value.
The index code set in the Index item of (b) is output to the data output means 13. Then, the current pixel value is stored in the immediately preceding data storage unit 17 (S17), and the process returns to step S2 to process the next pixel value.

If the same pixel value does not exist among the pixel values that appeared in the past (NO in S14), it is checked whether or not the compression by the difference code is possible (S15). The control means 11 calculates the differences ΔR, ΔG, and ΔB for each color value between the current pixel value and the immediately preceding pixel value stored in the immediately preceding data storage means 17, which are obtained by the difference acquisition means 16, respectively, by 2, If it can be expressed in a few bits or less, it is determined that compression using a 1-byte difference code is possible, and the differences ΔR, Δ
The 1-byte differential code of FIG. 3C in which G and ΔB are set is output to the data output unit 13 (S18). Also, the difference Δ
If R, ΔG, and ΔB can be represented by 5 bits, 4 bits, and 5 bits or less, respectively, it is determined that compression using a 2-byte difference code is possible, and the differences ΔR, ΔG, and ΔB are set in FIG.
The byte difference code is output to the data output means 13 (S1
8). Further, the differences ΔR, ΔG, and ΔB are 7,
If the data can be expressed by 6 or 7 bits or less, it is determined that compression by the 3-byte differential code is possible, and the 3-byte differential code of FIG. 3E in which the differences ΔR, ΔG, and ΔB are set is output to the data output means 13 ( S18). In other cases, that is, when each of the differences ΔR, ΔG, and ΔB cannot be represented by 7, 6, or 7 bits or less, it is determined that the compression by the difference code is impossible, and FIG. ) Is output to the data output means 13 (S19).

When the difference code and the immediate code are output as described above, the current pixel value is stored in the immediately preceding data storage means 17 (S6) and the next index number of the past data storage means 18 is stored. Store in the entry (S
7). Then, returning to step S2, the next pixel value is input.

When the above processing is repeated and the processing is completed up to the last pixel in the image file 2 (YE in S3)
S), if the value of the continuous number counter 14a is larger than 0, a coincidence code in which the value of the counter value -1 is set to the length term in FIG. 3A is output (S20, S21), and the compression process ends.

FIG. 5 shows a measurement example of the compression ratio when some images are actually compressed using the data compression method according to the present embodiment and the conventional method. The conventional method is p
ackbits, LZW method, and JPEG (lossless mode) were used. Numerical values in the figure indicate “data amount after compression / original data amount”, and a smaller numerical value indicates a higher compression rate. Also, 1.00 indicates that compression is impossible. Here, image 1 is an image on a computer screen displaying two windows displaying character strings and an image diagram of a calculator and the like, and image 2 is an image of a certain homepage screen displayed on the computer screen. Yes, image 3 shows a Pho with a pocket watch on the open book with the lid open
The image 4 is a natural image obtained by photographing a landscape with a lake in the front and a forest in the back, and the image 5 is a pattern image in which a large number of stripe patterns are drawn. As shown in FIG. 5, according to the data compression method of this embodiment, various types of images can be compressed at the first or second highest compression ratio.

In the embodiment described above, as the application priority order of the compression codes, the matching code has the highest priority, the index code has the highest priority, and the difference code has been applied last. this is,
This is because, in the case of the present embodiment, the matching code is 1 byte, the index code is 1 byte, and the difference code is 3 bytes at the maximum. Therefore, this application priority order is an order that can further reduce the information amount. However, the number of bytes of each code is not limited to the above example, and various types can be adopted, and in that case, the application priority order of the compression codes can be changed. For example, when a 2-byte coincidence code with a 13-bit length term is used, where two identical pixel values are continuous, if it can be represented by an index code or a 1-byte difference code, that method is better. Since the amount of information is small, an index code or a one-byte difference code is applied with priority over a matching code.

Next, an embodiment of a data decompression method for decompressing an image compressed by the data compression method of the above embodiment and restoring the original image will be described.

FIG. 6 is a block diagram showing an example of a data decompression device to which the present invention is applied. The data decompression device 5 of this example includes a control unit 51, a data input unit 52, a data output unit 53, a continuous pixel output unit 54, a past data output unit 55, a difference data output unit 56, a selector 59- 1, 59-2 as well as storage means such as the immediately preceding data storage means 57 and the past data storage means 58. Further, it is connected to the compressed file 3, the decompressed file 6, and the user input / output device 7.

The data input means 52 is means for inputting compressed data to be restored from the compressed file 3. As described above, the compressed data is a one-byte matching code (FIG. 3).
(A)) 1-byte index code (FIG. 3
(B)) 1-byte, 2-byte, and 3-byte differential codes (FIGS. 3C to 3E) and 4-byte immediate codes (FIG.
(F)) is composed of a total of six types of compression codes.
The data input means 52 inputs these compression codes sequentially from the head of the compressed data. Code delimiters are in byte units, and the number of byte codes can be determined by the code identifier bits. That is, if the 7th bit of the read 1 byte is 0, it is a 1-byte differential code, and if the 7th and 6th bits are 1, 0, it is a 2-byte differential code.
If the first bit is 1,1,0, it is a 1-byte matching code, and if the seventh, sixth, fifth, and fourth bits are 1,1,1,0, then it is a three-byte differential code; If the fifth, fourth, and third bits are 1,1,1,1,0, it is an index code, and 7,6,5,4,3,2,1,0 is 1,1,1,
If it is 1,1,0,0,0, it is an immediate code. The input source of the compressed data to be restored is not limited to a file.

The immediately preceding data storage means 57 is a means for holding the pixel value restored immediately before.

The past data storage means 58 is a means for storing a plurality of types of pixel values restored in the past. The structure and the method of storing the pixel values therein are the same as those of the past data storage means 18 on the data compression apparatus side. is there. That is, in the case of the present embodiment, as shown in FIG. 2, up to eight pixel values are stored in the same order as in the data compression device.

The continuous pixel output means 54 is a decompression means of the coincidence code, and continuously converts the pixel value stored in the immediately preceding data storage means 57 by the value of the length term of the coincidence code input by the data input means 52 plus +1. And output.

The past data output means 55 is a means for expanding the index code, and reads out the pixel value stored in the past data storage means 58 corresponding to the index number indicated by the index code input by the data input means 52. Output.

The difference data output means 56 is a means for expanding the difference code. The difference data output means 56 converts ΔR, ΔG, and ΔB in the difference code inputted by the data input means 52 into the respective colors of the pixel values stored in the immediately preceding data storage means 57. The pixel values are restored by adding to the values R, G, and B and output.

The selector 59 # 1 is connected to the continuous pixel output means 5
4. To select any one of the pixel values output from the difference data output means 56 and the control means 51 based on the control signal from the control means 51, output the same to the selector 59-2, and store it as past data. To the past data storage means 58.

The selector 59-2 selects one of the pixel values output from the selector 59-1 and the past data output means 55 based on a control signal from the control means 51, and outputs the selected pixel value to the data output means 53. At the same time, the image data is output to the immediately preceding data storage unit 57 to be stored as the immediately preceding pixel value.

The data output means 53 is means for outputting the restored pixel values to the restored file 6. The output destination of the restored data is not limited to a file.

The control means 51 is a means for controlling the entire data decompression device 5.

FIG. 7 is a flowchart showing a processing example of the data decompression device 5 of FIG. Hereinafter, the operation of this embodiment will be described with reference to FIGS. When the data decompression device 5 is realized by a computer having a CPU and a memory, a decompression program describing the processing shown in FIG. 7 is stored in a machine-readable recording medium such as a CD-ROM, a semiconductor memory, or a magnetic disk (FIG. 6). M2), the decompression program of the recording medium M2 is read by the computer, and the computer is controlled to operate so that the computer functions as the data decompression device 5 in FIG.

When a decompression request designating a compressed file 3 for storing compressed data to be decompressed and a decompression file 6 for storing decompressed images is input from the user input / output device 7 to the data decompression device 5, the data decompression device 5 Under the control of the control means 51, the processing shown in FIG. 7 is started.

First, the control means 51 initializes each part of the apparatus (S31). In this process, all the pixel values in the immediately preceding data storage unit 57 and the past data storage unit 58 are initialized to 0.

Next, the control means 51 includes a data input means 52
Is used to input the first compression code from the compression file 3 (S32), and the type of the code is determined (S34 to S3).
6).

When the compression code is an immediate code (N in S36)
O), the pixel value itself set to the immediate code is sent from the control means 51 to the data output means 53 through the selectors 59-1 and 59-2, and output to the restoration file 6 (S3).
7). Then, the pixel value is stored as the immediately preceding pixel value in the immediately preceding data storage unit 57 (S38), and is stored in the past data storage unit 58 as one of the past data (S3).
9) Return to step S32 and input the next compression code.

When the compression code is a coincidence code (YE in S34)
S), the control means 51 transmits the coincidence code to the continuous pixel output means 54, and the continuous pixel output means 54 compares the pixel value stored in the immediately preceding data storage means 57 with the value of the length term of the coincidence code + 1. The selector 59-1 is continuously provided by the number.
And the control means 51 outputs the output to the selector 59-
The selected data is output to the restored file 6 through the data output means 53 (S40). Then, the pixel value is stored as the immediately preceding pixel value in the immediately preceding data storage unit 57 (S38), and is stored as one of the past data in the past data storage unit 58 (S39), and step S3 is performed.
Returning to step 2, the next compression code is input.

When the compression code is an index code (S3
5), the control means 51 transmits the index code to the past data output means 55, and the past data output means 55 is stored in the past data storage means 58 corresponding to the index number set for the index code. The read pixel value is read and output to the selector 59-2, and the control means 51 selects the output with the selector 59-2 and outputs it to the restored file 6 through the data output means 53 (S41). Then, the pixel value is stored as the immediately preceding pixel value in the immediately preceding data storage means 57 (S42), and the process proceeds to step S
Returning to step 32, the next compression code is input.

When the compression code is a difference code (YE in S36)
S), the control means 51 transmits the difference code to the difference data output means 56, and the difference data output means 56 adds the difference code to the R, G, B values of the pixel values stored in the immediately preceding data storage means 57. And outputs the pixel value obtained by adding ΔR, ΔG, and ΔB to the selector 59-1. The control means 51 selects the output with the selectors 59-1 and 59-2, and outputs the output to the restoration file 6 through the data output means 53. (S4
3). Then, the pixel value is stored as the immediately preceding pixel value in the immediately preceding data storage unit 57 (S38), and is stored in the past data storage unit 58 as one of the past data (S3).
9) Return to step S32 and input the next compression code.

When the above processing is repeated and the processing is completed up to the last compression code in the compressed file 3 (S33)
YES), and terminates the decompression processing.

FIG. 8 is a block diagram showing another example of the data compression apparatus to which the present invention is applied, and FIG. 9 is a flowchart showing an example of the processing. FIG. 1 shows a data compression apparatus 1 according to the present embodiment.
The difference from this data compression device is that each time pixel values for one line of the image to be compressed are processed, the immediately preceding pixel values and past data are initialized, which will be described later when the compressed file 3 is decompressed. In this way, the decompression process from the middle of the compressed data can be performed at high speed. For this purpose, the control means 11 is provided with a pixel number counter 11a for counting the number of pixels processed up to the present time.
Between steps S1 and S2, steps S22-
Changes such as insertion of S26 have been made. When the data compression apparatus 1 is realized by a computer having a CPU and a memory, a compression program describing the processing shown in FIG. 9 is stored in a machine-readable recording medium such as a CD-ROM, a semiconductor memory, or a magnetic disk (FIG. 8). M
1), the compression program of the recording medium M1 is read by the computer, and the computer is controlled to operate so that the computer functions as the data compression device 1 in FIG.

Hereinafter, the operation of this embodiment will be described focusing on differences from the data compression apparatus of the embodiment of FIG.

An image file 2 for storing image data to be compressed, a compressed file 3 for storing a compressed image, and a compression request designating the number of pixels L per line of the image are transmitted from the user input / output device 4 to the data compression device. 9 is started under the control of the control means 11 of the data compression device 1. The number of pixels L may be automatically obtained by scanning an image in the image file 3.

First, the control means 11 initializes each part of the apparatus (S1). In this process, the pixel values in the immediately preceding data storage unit 17 and the past data storage unit 18 are all initialized to 0, and the continuous number counter 1 in the immediately preceding data comparison unit 14 is reset.
4a is also initialized to 0, and the pixel number counter 11a
Is initialized to 0.

Next, the control means 11
Are used to sequentially input pixel values from the image file 2, and the same processing as in the data compression apparatus of FIG.
S21) In this embodiment, before processing one pixel value, the pixel number counter 11a is incremented by 1 (S22) to count the number of pixels that have been processed from initialization to the present. . And the pixel number counter 1
If the value of 1a has reached L + 1 (YE in S23)
S) Since the processing for one line has been completed, if the value of the continuous number counter 14a is greater than 0, a coincidence code in which the value of the count value -1 is set in the length term of FIG. (S24, S2)
5) If the value of the continuous number counter 14a is 0, the process S25 is skipped, and the process proceeds to step S26, where the immediately preceding data storage unit 17 and the past data storage unit 1 are respectively executed.
All the pixel values in 8 are initialized to 0, the continuous number counter 14a in the immediately preceding data comparison means 14 is initialized to 0, and the pixel number counter 11a is set to 1. Then, the process proceeds to step S2 to process the next pixel value.

As described above, when the pixel values for one line of the image are re-initialized each time the processing is completed, the compression ratio slightly deteriorates, but the decompression process from the middle of the compressed data can be performed at high speed. . Hereinafter, the processing at the time of decompression will be described.

FIG. 10 is a block diagram showing an example of a data decompression device for decompressing a compressed image in the image file 3 generated by the data compression device of FIG. The difference between the data decompression device 5 of this embodiment and the data decompression device of FIG.
When a decompression request is made from the user input / output device 7, when a line to be restored is specified, the line is caught and the function for actually restoring from the pixel values after that line is provided. . Therefore, a pixel counter 51a, a line counter 51b, and a cueing unit 51 are provided in the control unit 11, and the processing of the data decompression device is changed as shown in FIGS. When the data decompression device 5 is realized by a computer having a CPU and a memory, a decompression program describing the processing shown in FIGS. 11 and 12 is stored in a machine-readable recording medium such as a CD-ROM, a semiconductor memory, or a magnetic disk. (M2 in FIG. 10), the decompression program of the recording medium M2 is read by the computer, and the computer is controlled so as to function as the data decompression device 5 in FIG.

Hereinafter, the operation of this embodiment will be described focusing on differences from the data decompression device of the embodiment of FIG.

The user receives a decompression request specifying the compressed file 3 for storing the compressed data to be decompressed, the decompressed file 6 for storing the decompressed image, the number of pixels L per line, and if necessary, the decompression start line number m. I / O device 7
11 is input to the data decompression device 5, the process shown in FIG. 11 is started under the control of the control unit 51 of the data decompression device 5. The number of pixels per line may be recorded in the compressed file 3 at the time of compression, and may be read. The restoration start line number m designates the first line as the first line. For example, for the third line,
Let m = 3.

First, the control means 51 initializes each section of the apparatus (S51). In this process, the pixel values in the immediately preceding data storage unit 57 and the past data storage unit 58 are all initialized to 0, and the pixel number counter 51a and the line counter 51b are also initialized to 0.

Next, the control means 51 determines whether or not the restoration start line number has been designated (S52). If such designation has been made, the cueing means 51c causes the step S5 to proceed.
After executing the processing of 3 to S61, the process proceeds to the processing of FIG.
If there is no such designation, the process immediately proceeds to the process of FIG.

In the cueing process by the cueing means 51c, the data input means 52 reads out one code at a time from the first compression code of the compressed file 3 (S53), and if the compression code is a coincidence code (YES in S55). , The number-of-pixels counter 51 for the number of times of the value of the length term of the matching code + 1
a is incremented (S56), and for other compression codes, the pixel number counter 51a is incremented by 1 (S57). Then, the count value of the pixel number counter 51a after the increment is equal to the pixel number L for one line.
When the count reaches -1, the line counter 51b is incremented by 1 (S58, S59). When the count value of the line counter 51b reaches the restoration start line number m-1 (YES in S60), the cueing is completed. . Only the type of code is determined and the number of pixels to be restored is calculated, but the actual pixel value is not restored.
Note that if the processing up to the last compression code has been performed before YES is determined in step S60 (YES in S54),
The restoration start line number was specified incorrectly.
An error message is output to the user input / output device 7 (S
61).

The processing in FIG. 12 is almost the same as the processing in FIG. However, at the time of compression, since the immediately preceding pixel value and past data are initialized for each line, the number of restored pixels is counted using the pixel counter 51a also at the time of decompression (S7).
(1, S73) When the restoration to the last pixel of one line is completed (YES in S72, S74), the process returns to step S31, and the immediately preceding data storage unit 57 and the past data storage unit 5
All the pixel values in 8 are initialized to 0, and the pixel counter 51a is initialized to 0.

In the embodiment shown in FIGS. 8 and 10, the restoration from the head of an arbitrary line is enabled. However, the restoration from an arbitrary line of an arbitrary line is also possible. In this case, a restoration start line number is specified in addition to the restoration start line number, and after cueing to the specified restoration start line, the pixel values immediately before the restoration start line are not output, but as the immediately preceding pixel value and the past data. Normal processing for actually outputting the restored file 6 from the pixel on the restoration start line is performed instead of storing.

[0081]

As described above, according to the present invention, the following effects can be obtained.

A total of four kinds of codes, a match code, a difference code, an index code, and an immediate code, are selectively used, and a code that reduces the amount of data after compression is selected for each data in order from the beginning of the data group to be compressed. Since the data is compressed in such a manner, it is possible to obtain a compression rate comparable to that of the conventional method which provides the highest compression rate for various types of images.

In a configuration in which all kinds of codes are codes in byte units, data processing in bit units becomes unnecessary, and the processing amount is reduced accordingly.

In a configuration in which the immediately preceding pixel value or past data is initialized each time the processing of a predetermined number of pixels is completed, at the time of decompression, decompression processing from the middle of compressed data can be performed at high speed. it can.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of a data compression device to which the present invention has been applied.

FIG. 2 is a diagram illustrating a configuration example of a past data storage unit.

FIG. 3 is a format example of a compression code used in an embodiment of the present invention.

FIG. 4 is a flowchart illustrating a processing example of the data compression device in FIG. 1;

FIG. 5 is a diagram illustrating a measurement example of a compression ratio when some images are actually compressed using the data compression method according to the embodiment of the present invention and the conventional method.

FIG. 6 is a block diagram illustrating an example of a data decompression device to which the present invention has been applied.

FIG. 7 is a flowchart illustrating a processing example of the data decompression device of FIG. 6;

FIG. 8 is a block diagram showing another example of the data compression device to which the present invention is applied.

FIG. 9 is a flowchart illustrating a processing example of the data processing device of FIG. 8;

FIG. 10 is a block diagram showing another example of a data decompression device to which the present invention is applied.

FIG. 11 is a flowchart illustrating a processing example of the data decompression device of FIG. 10;

FIG. 12 is a flowchart illustrating a processing example of the data decompression device of FIG. 10;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Data compression device 11 ... Control means 12 ... Data input means 13 ... Data output means 14 ... Previous data comparison means 14a ... Continuous number counter 15 ... Past data comparison means 16 ... Difference acquisition means 17 ... Previous data storage means 18 ... Past Data storage means 2 ... Image file 3 ... Compressed file 4,7 ... User input / output device 5 ... Data decompression device 6 ... Decompression file

Continuation of the front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06T 1/00 H03M 7/30-7/50 H04N 1/41-1/419

Claims (9)

(57) [Claims] 1. A matching code that sets the number of times the same data value as the immediately preceding data value continues, a difference code that sets a difference between the immediately preceding data value, and processed data stored in the past data storage unit. Using a total of four types of codes, an index code that sets the index number of the value and an immediate code that sets the data value itself, the data amount after compression for each data in order from the top of the data group to be compressed A data compression method characterized by selecting a code having a smaller number of bits and compressing the data. 2. The data compression method according to claim 1, wherein all kinds of codes are byte-based codes. 3. The data compression method according to claim 1, wherein a plurality of types of difference codes having different maximum difference values that can be set are used as the difference codes. 4. A data compression method for compressing data by the following steps. (A) a step of initializing the immediately preceding data storage means, the past data storage means, and the continuous number counter (b) a step of inputting one pixel value from the image to be compressed (c) a pixel value input in step b and the immediately preceding data A step of comparing the pixel value stored in the storage means with the pixel value stored in the storage means. (D) In the case of a comparison match in step c, the continuous number counter is incremented. Return to step b after outputting and initializing the continuous number counter. (E) If the comparison does not match in step c, and if the continuous number counter is other than the initial value, then output a coincidence code that sets the number of consecutive times. After initializing the number counter, the past data storage means for holding the pixel values which appeared in the past with an index number is stored and inputted in step b. (F) When an index number is obtained in step e, an index code in which an index number is set is output, and the pixel value input in step b is obtained. (G) when the index number is not determined in step e, the pixel value input in step b and the pixel value stored in the immediately preceding data storage means are stored. (H) When the difference obtained in step g can be set to a difference code having a size smaller than the size of the immediate code in which the pixel value input in step b is set, the difference obtained in step g is The set difference code is output, and if not, an immediate code that sets the pixel value input in step b is output. The pixel values input in flop b also stored in the historical data storage means by a predetermined storage method stores just before the data storage means, the flow returns to step b step 5. (i) Each time the processing of a predetermined number of pixels is completed, if the number-of-continuations counter is other than the initial value, a coincidence code in which the number of continuations is set is output. 5. The data compression method according to claim 4, further comprising the step of initializing the means and the continuous number counter and returning to step b. 6. The data compression method according to claim 4, wherein each of the codes is a code in a byte unit. 7. The data compression method according to claim 4, wherein a plurality of types of difference codes having different maximum difference values that can be set are used as the difference codes. 8. A machine-readable recording medium on which a compression program for causing a computer to execute the following steps is recorded. (A) a step of initializing the immediately preceding data storage means, the past data storage means, and the continuous number counter (b) a step of inputting one pixel value from the image to be compressed (c) a pixel value input in step b and the immediately preceding data A step of comparing the pixel value stored in the storage means with the pixel value stored in the storage means. (D) In the case of a comparison match in step c, the continuous number counter is incremented. Return to step b after outputting and initializing the continuous number counter. (E) If the comparison does not match in step c, and if the continuous number counter is other than the initial value, then output a coincidence code that sets the number of consecutive times. After initializing the number counter, the past data storage means for holding the pixel values which appeared in the past with an index number is stored and inputted in step b. (F) When an index number is obtained in step e, an index code in which an index number is set is output, and the pixel value input in step b is obtained. (G) when the index number is not determined in step e, the pixel value input in step b and the pixel value stored in the immediately preceding data storage means are stored. (H) When the difference obtained in step g can be set to a difference code having a size smaller than the size of the immediate code in which the pixel value input in step b is set, the difference obtained in step g is The set difference code is output, and if not, an immediate code that sets the pixel value input in step b is output. The pixel values input in flop b also stored in the historical data storage means by a predetermined storage method stores just before the data storage means, the flow returns to step b step 9. A machine-readable recording medium recording a compression program according to claim 8, further causing the computer to execute the following steps. (I) Every time the processing of a predetermined number of pixels is completed, if the continuous number counter is other than the initial value, a coincidence code in which the number of continuous times is set is output, and the immediately preceding data storage means, past data storage means, and continuous number counter are output. To initialize and return to step b