JPS646589B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an image data compression method, and particularly to an image data compression method suitable for use when temporarily storing image data in a high-speed image output device such as a laser printer. Conventionally, as a method for encoding facsimile signals, a compression method has been proposed that utilizes correlation in the sub-scanning direction (direction perpendicular to the scanning line) in addition to correlation in the main scanning direction (scanning line direction). The change point address encoding method described in No. 58406 is one example. This change point address encoding method focuses on each change point of the scanning line (image signal) to be encoded from white to black or vice versa (among these change points, the change point that is currently being encoded is Q)
If point Q can be expressed as a deviation from the corresponding changing point on the immediately preceding scanning line in comparison with a similar changing point on the scanning line immediately before the above scanning line (this can be determined by whether or not a specific condition is satisfied) Specify the address of the changing point Q by the amount of left and right deviation from the address of the corresponding changing point, and if there is no correlation and it should be an independent changing point, specify the previous opposite changing point on the same scanning line (Q from white). If it is a point of change from black to white, a method is used in which the address of point Q is specified by the run length from the point of change from black to white. FIG. 1 is a diagram for explaining an example of this encoding, in which small sections with hatching represent black pixels, and small sections without hatching represent white pixels. Q, P ₀ , P ₁ , P ₂ etc. shown in the figure are changing points, and up to the changing point P ₀ are encoded,
Assume that the address of the change point Q is encoded. First, define the shift change point. In Figure 1, P ₀ ,
P ₁ , P _{2 .} . . are determined for the encoding change point Q as follows. P ₀ : A change point immediately before the encoding change point Q. If there is no such change point, it is the first pixel of the scanning line. P ₁ : On the scanning line (this is called the reference scanning line) immediately before the scanning line (encoding scanning line) that includes Q and P ₀ , it is on the right side of P ₀ and has information change in the same direction as Q. The first change. P ₂ : Has information change in the same direction as Q,
The next change point of P ₁ . P ₃ : Has information change in the same direction as Q,
The next change point of P ₂ . The same applies below. However, if there is no such change point for Pi (i≧1), the pixel next to the last pixel of the scanning line is set as Pi. In this way, reference change points such as P ₀ , P ₁ , P ₂ , etc. are defined for encoding change points, and these change points are called reference change points. Next, the sign change point is divided into a shift change point and other change points, that is, a new change point. The deviation change point is defined as follows, with a group of pixels having consecutive identical information being called a run. That is, there is a run of the same information on the immediately preceding scanning line that overlaps with the run starting at that encoding change point, and this overlapping run of the same information overlaps with a run of the same information immediately before the run that includes the encoding change point. The encoding change point where the difference is not the same is defined as the deviation change point. For example, in the example in Figure 1, the change point Q in (a) to (c) is a change point, but the change point Q in (d) does not have a run with the same information that overlaps the run that includes it on the previous scanning line. Therefore, it is not a shift change point. In addition, at the change point Q in (e), there is a run of the same information that overlaps with the run that includes it on the immediately preceding scanning line, but this overlapping run of the same information also overlaps with a run of the same information that immediately precedes the run that includes the change point Q. Therefore, it is not a point of change. For the deviation change points classified in this way, in order to encode the address information of the deviation change points, the reference change point is a number representing which change among P ₁ , P ₂ ...P _o , and its value. The distance (number of pixels) from the reference change point to the deviation change point is actually encoded. 1st
In the examples in Figures (a) to (c), (a) 1,+1 (b) 1,-2 (c) 2,+1. Here, the unsigned numbers such as 1 and 2 represent that the reference change points are _P1 and _P2, respectively, and the following numbers with + or - represent the distance. However, + indicates that the change point Q is on the right side or the same position as the reference change point, and -
means that the change point Q is on the left side of the reference change point. For changing points that are not deviation changing points, fix the reference changing point as P ₀ and set the changing point Q
The address information is encoded using the distance (number of pixels) from the change point P ₀ to the change point Q.
This is the same as normal run-length encoding. In the method described above, the reference point of the deviation change point is
Although the selection is made from among P ₁ , P ₂ . . . P _i (i>2), it is also possible to simplify this and fix it to P ₁ .
This eliminates the need for address information for selecting the reference change point. Further, some codes (pass mode codes) having the meaning of shifting the reference point one by one may be inserted. Conventionally, in order to restore such compression encoding, the restored scan line was generally temporarily stored in a shift register as is, so the restoration was performed by storing the restored scan line in the shift register corresponding to the change point of the scan line currently being restored. Restoring one scanning line requires at least the time to shift all pixels of the restored scanning line data as the time required to find the relative address with respect to the reference change point of the restored scanning line. Further, time for address calculation proportional to the change point was also required. FIG. 2 shows a conventional example of a compressed data restoration method using this type of change point relative addressing method. In the figure, facsimile image data that has been compressed and variable-length coded from a compressed data memory 1 based on the above definition is input into a code equal-length coder 2, where it is converted into equal-length codes to facilitate processing. When the change point to be restored is a shift change, the information for selecting the reference change point and the length of the shift are output, and when the change point is a new change point, the distance from the previous change point is output. In this case, a reference scanning line shift register 3 that stores already decoded reference scanning lines and can shift them in both directions is provided, and a shift pulse is generated from a shift pulse generation circuit 6 based on the information on the shift change point to perform the reference scanning. Shift line shift register 3. In this case, the shift pulse generation circuit 6 is operated until the change detection circuit 5 detects that the information of the pixel at the exit of the reference scanning line shift register 3 is a change point different from the information of the immediately preceding pixel. Therefore, the reference scanning line address counting circuit 4 that counts the output pulses of the shift pulse generator 6 counts the address of the change point at the exit. The changing point address of this reference scanning line, together with the length of the deviation obtained from the equalizing circuit, is input into an adding/subtracting circuit 7 for addition and subtraction, and the result is stored in the next changing point address memory 9 of the decoded scanning line. On the other hand, as for the above-mentioned new change point information, the address of the change point immediately before the encoding change point is stored, as will be described later. Together with the address from the decoded scanning line address counting circuit 11, it is input into an adder circuit 8 and added, and the result is input into the next change point address memory 9 of the decoded scan line. Next, the contents of the next change point address memory 9 of this decoded scanning line are written to the decoded scanning line writing circuit 10, and this output causes the decoded scanning line address counting circuit 1
At step 1, addresses corresponding to the reference scanning line address counting circuit 4 are counted, and the restored image information is stored in the decoded scanning line memory 12. The contents of this decoded scanline memory 12 are shifted into the reference scanline shift register 3 to provide restored image information for the next reference scanline. It is clear that with the above configuration, it takes at least the time to completely shift all pixels and the address calculation time proportional to the number of change points each time. When restoring an image via a relatively low-speed information transfer path and image output device, such as a facsimile device, this processing time can be absorbed using an appropriate buffer memory device, and is not a problem. . However, in high-speed image output devices such as laser printers that output hundreds to tens of millions of pixels per second, the processing time described above cannot be ignored. The user is forced to wait for the input, causing problems that impede the high-speed performance of the image output device. An object of the present invention is to provide an image data compression method suitable for high-speed restoration processing that can eliminate such problems.
Compression means for converting two-dimensional pixel data into compressed data in units of scanning lines, calculation means for calculating the data length of the compressed data, and first detection for detecting that the data length is greater than or equal to a predetermined value. means and
comprising a counting means for counting black and white change points of the scanning line to be compressed, and a second detecting means for detecting that the count value of the counting means is equal to or greater than a predetermined value, If either of the detection means detects that the value is greater than or equal to a predetermined value,
When raw pixel data is sent as compressed data of the scanning line, and both the first and second detection means do not detect that the pixel data is equal to or greater than a predetermined value, the compressed data compressed by the compression means is compressed by the compression means. This is achieved by an image data compression method characterized by transmitting data, and one embodiment thereof will be described in detail below with reference to the drawings. FIG. 2 is a block diagram showing an embodiment of the present invention. In FIG. 2, 13 is an input terminal for inputting the read secondary image signal, 14 is a memory for temporarily storing the input two-dimensional image signal, and 15a, 15b (hereinafter a)
corresponds to the encoded scanning line and b corresponds to the reference scanning line) is a shift register (15) that stores information for one scanning line.
b is a bidirectional shift register), 16a and 16b are change registers that receive the pixel information stored in the shift registers 15a and 15b one pixel (one bit) at a time and detect whether the pixel information is different from the previous pixel information. The point detection circuit 17a is a run length counting circuit that counts the number of pixels (run length) from when the change point detection circuit 16a detects a change point to when the next change point is detected. 18a, 18
b is the number of times each shift register 15a, 15b has been shifted, that is, each shift register 15a, 15b
18b is a reversible counting circuit which indicates the number of the pixel at the exit of each scanning line counting from the left end of each scanning line (this is called an absolute address). 19 is a shift pulse generation circuit that generates shift pulses etc. for the shift registers 15a and 15b;
20 is a register that temporarily stores the run length information obtained by the run length counting circuit 17a, 21 is a gate, 22 is a variable length encoding circuit that performs variable length encoding as shown in Table 1, and 23 is information compressed at a constant speed. A buffer memory 24 temporarily stores encoded information in order to send out the buffer memory 23 or memory 1.
A selector circuit selectively passes one of the four outputs, and 25 is an output terminal. 26 is a counting circuit that counts the output of the change point detection circuit 16a, 27 is an accumulation circuit that cumulatively adds the output bit width of the variable length encoding circuit 22, 28 and 29 are comparison circuits, and 30 is a constant memory that outputs a constant value. ,3
1 is the or gate.

【table】

【table】

Claims (1)

[Claims] 1. Compression means for converting two-dimensional pixel data into compressed data in units of scanning lines, calculation means for calculating the data length of the compressed data, and a first means for detecting that the data length is equal to or larger than a predetermined value. a detection means, a counting means for counting black and white change points of the scanning line to be compressed, and a second detection means for detecting that the counted value of the counting means is equal to or greater than a predetermined value, When either one of the first and second detection means detects that the value is equal to or greater than a predetermined value, raw pixel data is sent as compressed data of the scanning line, and the first and second detection means An image data compression method characterized in that, if it is not detected that both of the values are greater than a predetermined value, compressed data compressed by the compression means is sent out.