JPS6026347B2 - Redundancy reduction coding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a redundancy suppression coding method for an image signal including halftones or a color image signal.

Digitally transmitting an image signal such as a facsimile while maintaining halftones requires a long transmission time.

For example, 4 bits are required to represent the intermediate tone of 1 Iso tone, so the transmission time in this case is four times that of the case of black and white binary.
Furthermore, storing image signals also requires a large storage capacity for the same reason. For this reason, it has been desired by the industry to shorten the transmission time and reduce the storage capacity by suppressing the redundancy of the image signal. As a redundancy suppression technology for image signals including intermediate recognition, methods such as delta modulation, which is used for the transmission of television images, have been used for a long time. There were drawbacks associated with this. This invention encodes information on change boundaries of individual quantized signal components of an image signal including halftones, that is, change boundaries of tatami-formed density levels, or change boundaries for each tone of a color image signal. The purpose is to obtain a high compression rate without deteriorating the image quality of the image signal. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described in detail below with reference to the drawings, focusing on embodiments in which the invention is applied to image signals including halftones. FIG. 1 is a diagram explaining the principle of an embodiment of the present invention, in which A is a coded scanning line to be coded, 8 is a reference scanning line, and is used to decode the image signal of the coded scanning line. assumes that the image signal of the reference scan line is known.

One area surrounded by a broken line in the figure represents one pixel, and the solid line partitions P,,P2,P3,Q,,Q on each scanning line
2 and Q indicate the boundaries of areas having image signals with the same content.
That is, in the case of a color image signal, there are boundaries for each color, and for a halftone image signal, there are boundaries for each density level. It is necessary to perform quantization in order to display an image that includes an intermediate image as a digital signal, but when the density level of each pixel of the original image is quantized, boundaries for each density level are generated on the image. For example, when representing 8 gradations from the 0th (white) level to the 7th (bad) level, if there is an area in the original image where the density gradually increases from white, then the A boundary occurs when moving to level 1 (the lowest density gray). The numbers written within the pixels in FIG. 1 represent the density level of each area sandwiched between these boundaries. Therefore, in the case of FIG. 1, in the encoded scanning line A, an area of density level 0 is followed by four pixels of density level 2, three pixels of density level 3, and then moves to an area of density level 4. . Similarly, in the reference scanning line B, three pixels of density level 1 and five pixels of density level 3 are lined up between the areas of density level 0 and density level 4.・
The entire image signal on the encoded scanning line A is given by the positions of boundaries Q, , Q2, Q, . In this case, it is known that by sequential processing encoding, redundant information can be omitted by correlating the image signal with a previously known reference scanning line B. A case in which encoding processing is performed from left to right will be described below. Therefore, the boundary states above the encoded scanning line A and the reference scanning line B are classified as follows. '1} First state (hereinafter referred to as S, state) 'a} is on the reference scan line with respect to the boundary Q on the encoding scan line, is to the left of the female Q, and is the closest boundary to Q or to the right of Q , and the boundary closest to Q (if there is a boundary directly above Q on the reference scanning line, this boundary), and [c} the density on the predetermined side of the boundary (here, the left side) A state in which the level (color in the case of a color image signal) is the same as the density level on the same side of the boundary Q on the encoded scanning line, and {d' there is no boundary on the encoded scanning line between that boundary and the boundary Q .

The condition ('d) is not necessarily required as described later, but is added for ease of understanding.) This can be explained using Figure 2. The boundary to the left and closest to Q is P, and the boundary to the right of Q and closest to Q is P2.

Therefore, the left side q of P,,P2. It is determined whether any of the concentration levels of b2 is the same as the concentration level of the left-leaning female of Q. If the density level of b, is the same as that of a, then P, and Q are in the corresponding S, state. If the density level of b2 is the same as that of a, then P2 and Q are in the corresponding S state. Further, if the density levels of b, , etc. are all different from the density level of a, Q is not in the S state. In this case, information indicating that the state is S, and Q
It is sufficient to give only the relative distance 1 between and P (boundary on the reference scanning line that satisfies the above condition for Q).

The display of 1 is the number of pixels that fall between P and Q (Lanrenkes)
It is convenient to give it as

Also, when Q is to the left of P, it is 1, < 0, and when it is to the right, it is 1
, > 0 (this may be determined in the opposite way). Hereinafter, this information will be denoted as S, (1,). This condition occurs when the same density level is connected from the encoded scan line to the reference scan line. Therefore, the boundaries of concentration levels are also connected. In the example of FIG. 1, P, , Q, and P3, Q3 are shown to be in the first state. That is, P, is closest to Q on the left side, and the concentration levels on the left side of P, , Q, are all the same at the 0th level.

Further, P3 corresponds to Q3 (in this case, the boundary to the right and the boundary to the left of Q are degenerated into one), and the density levels on the left side of P3 and Q3 are both the third level. Note that the S of P,,Q, is 1,=1,S of P3,Q3 in the state
, 1,=0 in the state. '21 Second state (hereinafter S
A state in which there is no boundary on the encoded scanning line that satisfies the first condition with respect to the boundary P on the reference scanning line.

This condition occurs when the density level on reference scan line B is not connected to encoded scan line A.

In the example of FIG. 1, the boundary P2 represents the S line. Note that for the S2 dog state, it is sufficient to provide only the information that the S2 big bear exists.

For example, in FIG. 2, to determine whether boundary P2 is in S, state or S〆Ookuma, pixels a, .
The object density level is compared with the density level on the left side Q of the boundary P2. If both are different, it is an S2 dog. '3}
Third state (hereinafter referred to as S vs. Okuma) A state where there is no boundary on the reference scanning line that satisfies the first condition with respect to the boundary Q on the encoded scanning line.

In this case, it is sufficient to provide information indicating the S3) state and information indicating the position of Q and the density level m of the area to the left of Q (represented by 13 and m, respectively).

13 can be expressed as a run length from a known boundary, but in order to shorten the code length, the run length from the boundary position in the previous state (if the previous state is S, the right border of the boundary pair) is required. It is best to express it in run length.

m may be given in a format that does not confuse the density level with other codes. In the example of FIG. 1, Q2 is in the S3 state and 1
3 is expressed as the run length from the previous state (P2 which is the S2 state) and becomes 13=2. The result of sequentially encoding the encoded scanning line A in FIG. 1 from left to right is expressed in symbols.
...S. (11), S2, S3 (2,2), S, (0)
...becomes...

That is, after the code identifying the S,, S2, and S3 states, S
,, In Sd Okuma, the information representing the boundary position may be further added with information giving the density level in the S3 state and encoded sequentially. To transmit or store this information digitally, binary codes of "1" and "0" are generally used. In this case, the code structure can be arbitrarily selected as long as each unit code can be identified, but in order to increase the compression rate, it is necessary to use state codes with a high probability of appearance, and run codes so that the average code length per unit pixel is as short as possible. It is desirable to shorten the length code and assign the code.

Table 1 shows an example of the code structure in this case.

In general image signals, S and state 1 are often small, so these are shortened and assigned codes. Table 1 (Note) ll assigns 042 to the absolute value symbol D (1). Z pieces L (m) is the run length of the concentration scale 1,, 12 where m is expressed in binary. There are various run length codes such as those used for binary image signals, but in the example in Table 1, the number of consecutive 0s with a 1 added at the end (this is written as D(1)) ).

S, '1 in status, S in case of IZ2, code 1 indicating status
100 or 1101 followed by (l1, -2l) zeros
, and add 1 at the end. In the S3 state, the code 1111 indicating the S3 state is followed by 13 consecutive 0s, followed by 1, and finally the code L(m) indicating the density level.
Attach. To represent L(m), 3 bits (
4 bits for 1 Iso tone, 5 bits for 3 Yoyo tone...)
Use to display the density level m in binary. That is, if the density level is 0, L(m) is 000, and if the density level is 1, it is 00.
1...If the density level is 7, it will be 111. The first one like this
FIG. 3 shows an example in which the encoded scanning line A in FIG. 1 is encoded using the code structure shown in the table.

However, since there are 8 gradations, L(m) is represented by 3 bits. Taking FIG. 3 as an example, this code can be decoded by the following procedure. First, it can be seen from "1001" that S, state is 1, = +1, but the boundary on the reference scanning line, which is the standard at this time, is the first P,
Therefore, the boundary Q on the encoded scanning line is shifted by one pixel to the right of P, and the density level of the area to the left of Q is the same as the area to the left of P, which is the 0th level. I understand that there is something. Next, from "111r, it is found that S2 is in the dog state, and it is found that there is no corresponding boundary at the next boundary P2 of P on the reference scanning line.Next, since it is known that it is the mother state from "111r," The code following it is D(1
2), it can be seen that L(m). From the sign D(12
) is “001” and 13=2.

Therefore, the next boundary position Q2 is shifted to the right by two pixels from the boundary position P2 in the immediately preceding state (S2). Also, the density level on the left side of Q2 is the code “01” of L(m) and the second
It can be seen that the level is Furthermore, from the “0” sign, S,
(0) state, but P2 is the previous state (S2
), it is known that there is no corresponding boundary, so the boundary on the reference scanning line that is the standard at this time is P3.
becomes. Therefore, the next boundary Q on the encoded scanning line is at the same position as P3, and the density level of the area to the left of Q3 is the same as that of the area to the left of P3, which is the third level. As described above, the information of the encoded scanning line in FIG. 1 is encoded as Z. FIGS. 4, 5, and 6 show other coded sequences based on the code structure shown in Table 1. The symbols in each figure are indicated using the symbol structure shown in Table 1. In this invention, when encoding one screen, the first step is to encode a binary image signal.
It is sufficient to send all the information for the scan line, and sequentially process the trillion scan lines using the processed scan line as a reference scan line. The first scanning line is 3 if there are 8 gradations for each pixel.
If one bit is accepted, all pixels may be transmitted using 4 bits, or redundancy may be suppressed using a one-dimensional encoding method. Alternatively, a scanning line of a specific image, such as a completely white image, may be assumed at the beginning of the screen, and this may be encoded as the first reference scanning line. The code structure shown in Table 1 is an example, and the code structure used in the present invention is not limited to this.

For example, S, the state is 1 is 0, soil 1.1, ≧2, 1, ≦12
The shape of the sign is changed by dividing it into 1, 0, ±
It is particularly shortened and assigned a code so that the case of 1 is suitable for cases where the probability of appearance is high, and it is not necessarily necessary to classify the cases in this way. Although the run length is expressed as a variable length string of 0s, it may also be a variable length string of 1s, or other run length codes such as Weyl code, or MH (in the case of internationally standardized binary images). Of course, it is also possible to use a black code (or a white code) of a motif (Huffman) code.
Further, the density level of the S illusion 8 state may be expressed by the difference in density level from the pixel adjacent to the left, or furthermore, a run-length code may be used to give the density level.

First to third states S, (1,), S2, S3 (13, m
), it is preferable to shorten the average code length per pixel to one with a high probability of appearance, and then assign the code. It is also possible to have a code configuration that does this. Table 2 shows another example of the code structure, and FIG. 7 shows an example of the code of the image in FIG. 1, which is displayed according to the code structure of Table 2.

In the above example, since the boundaries on the reference scanning line and the encoding scanning line are sequentially processed, the S state is limited to cases where there is no boundary on the encoding scanning line closer to the boundary on the corresponding reference scanning line. Therefore, although the density levels on the left side of the boundaries P3 and Q in FIG. 4 are the same, since there is a boundary Q2 between them, the S state does not occur. Table 2 (Note) L(m) is the concentration level expressed in binary. W(1) is the Weyl code as shown in Table 3. Table 3. Sign of W(Z) (Will code)×*...・
・ is a binary number, but this limitation is not necessarily necessary.

For example, this limitation can be removed by taking the run length from the immediately preceding (immediately left) boundary on the encoded scanning line for S, state 13. FIG. 8 shows an example in which the image shown in FIG. 4 is encoded using this method using the code structure shown in Table 1. That is, the boundary between P3 and Q forms the S state. Furthermore, S
, the condition that the corresponding boundary is on the reference scanning line and closest to the boundary Q to be encoded may be ignored.

However, in this case, the boundaries on the corresponding reference scanning line are other S,
, S2 or S3 state. Under these conditions, the fifth
FIG. 9 shows an example of encoding the image shown in the figure. In a case where the density of an actual image changes continuously, it is likely that the S2 or S3 state will occur twice in a row and the left and right sides thereof will have the same density level, as in the case of FIG. 6.

In that case, an encoding form may be adopted in which the code length becomes shorter when the S2 or S3 state occurs twice in succession.
For example, the S3 state can be expressed as the following S'3 state.

S'3 (1'3, 1''3, m') where 1'3: the value of 13 (run length from the previous state) of the left S3 state of consecutive S3 states.

However, if there is only one S3 state and it is not continuous, 1'3=
Set to 0.

1″: 13 of the S Ji Okuma on the right side in the continuous S3 state.

(run length between boundaries showing both S3 states) m': Concentration level indicated by the S3 state on the right side m.

(The density level of the area sandwiched between the boundaries indicated by both S3 states) However, on the left side of the boundary indicating the left S3 state (denoted as Q'), the boundary immediately to the left on the encoded scanning line (1'3 = 0) The density level in the area to the right of the boundary (if the case coincides with Q') is considered to be the same as the density level on the right side of the boundary indicated by the S3 state on the right.

Use this S'3 state instead of S3 state in Table 1 to convert S3 (1'3, 1''3, m) to 1111D (1'3)
○ When the image signals in Figures 4 and 6 are encoded by (1″3-1)L(m), the signals in Figures 10 and 11 are obtained, respectively.
It will look like the figure.

FIG. 12 shows a block diagram of the configuration of an embodiment of an encoder used in the present invention.

Line memories 11 and 12 each having a memory capacity for -scanning lines of the image signal fv are connected in series, and the output terminal of each line memory is connected to the input terminal of the identification circuit. The line memory 11 stores the contents of the encoded scanning line, and the line memory 12 stores the contents of the reference scanning line. Since these line memories handle multi-value signals, they can be composed of, for example, CCD multi-value memories. Each line memory 11 and 12 is connected to a clock generator 17.
The contents of the encoded scan line and the reference scan line are sequentially provided as inputs to the identification circuit 13 by shift pulses from the .

Identification circuit 13 according to the contents of line memories 11 and 12
identifies the states S, , S2, and S3 described above. The run length counter 14 detects the differential run length length of the states A, S, S, and the run length of the newly generated encoded line. In this case, when the identification circuit 13 detects a boundary on the encoded scanning line or the reference scanning line, the identification circuit 13 provides a set pulse fR to the run length counter 14, and the run length counter 14 detects a new run length. transition to the state where it is performed. Identification circuit 1
For the states S, , S2, S3 identified by 3, the code generator 15 receives the new concentration level signals of the states S, S2, S3 and the run length, S3 and corresponds to the code table of Table 1, for example. A code is generated and given as an input to a buffer memory 16 connected to its output terminal, and the code is temporarily stored in the buffer memory 16.

The buffer memory 16 is inserted to compensate for non-uniformity in information generation by the code generator 15 and to match the transmission line capacity. In this way, the contents of the encoded scanning line and the reference scanning line of the image signal fv are identified by the identification circuit 13,
For example, the code signal F corresponding to the code table shown in Table 1 is obtained at the output terminal of the buffer memory 16. A decoder that decodes this code signal F can be realized with a circuit configuration having a function opposite to that described above. Note that with the encoding method according to the present invention, the compression rate may not be very high depending on the content of the image signal, but for this reason, compared to other encoding methods such as one-dimensional encoding for each scanning line, The configuration may be such that the one with the shorter code length is selected and transmitted.

In this case, which encoding method has been selected can be identified by a method such as changing the synchronization signal. In the above description of the embodiments of the present invention, the redundancy suppression of image signals containing halftones has been mainly described, but the present invention can be similarly applied to the transmission or storage of color image signals.

In this case, the invention may be constructed by associating color types with density levels. That is, instead of density levels, 1 is red, 2
is green, and so on, by associating numbers representing each color tone. As explained in detail above, this invention makes it possible to suppress the redundancy of image signals including halftones or color image signals, etc. If this is applied to facsimile, the transmission time can be shortened, and image memo IJ' can be used. This makes it possible to reduce storage capacity.

In particular, since the encoding method according to the present invention is centered on run length, it has the advantage of increasing the compression rate when suppressing the redundancy of image information with many white areas, such as in facsimile originals. Furthermore, since the encoding method according to the present invention faithfully encodes the original picture signal, there is an advantage that there is no deterioration in image quality due to encoding as long as there is no coding error.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of the principle of an embodiment of the present invention, and FIG. 2 is a diagram showing an example of encoding in FIG. 1 using the code structure shown in Table 1.
Figures 3, 4, 5, and 6 are diagrams showing other encoding examples using the code structure shown in Table 1, and Figures 7 and 8 are diagrams of Figure 1 obtained under different conditions. Figures 9, 10 and 11 are diagrams showing encoding examples of Figures 3 and 5 under different conditions, respectively. Figure 12 is used in this invention. FIG. 2 is a block diagram showing the configuration of an embodiment of an encoder. A: encoded scanning line, B: reference scanning line, 11, 12: line memory, 13: identification circuit, 14: run length counter, 15: code generator, 16: buffer memory, 17:
clock generator. Ice diagram O 2 4〆 3 diagram Ice 4 Figure Juice 5 Offshore 6 title Ne 7 Soup 8 Figure Ice 9 diagram

Claims (1)

[Claims] 1 Regarding the change boundary of each quantized signal component (
1) A state in which the reference scanning line is connected to the encoding scanning line, (2) a state in which it exists on the reference scanning line but disappears without being connected to the encoding scanning line, and (3) a state in which it is on the reference scanning line. A state that is newly generated on the encoded scanning line without being connected to the coded scanning line is identified, and a state code indicating one of these states is formed. Add information about the position of the corresponding boundary on the line to the state code, and use only that state code in state (2),
In the state (3), the position of a newly generated boundary and the quantization information associated with the boundary are added to the state code to obtain an encoded signal. 2. The sequential processing redundancy suppression coding method according to claim 1, wherein the change boundaries of the individual quantized signal components are change boundaries of the quantized individual density levels. . 3. The sequential processing redundancy suppression coding method according to claim 1, wherein the change boundaries of the individual quantized signal components are change boundaries of individual different color tones.