JP3484900B2 - Image data encoding device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image data encoding apparatus for compressing image data, and in particular, compresses multi-valued image data such as photographs by binarizing it by pseudo halftoning. The present invention also relates to a suitable image data encoding device.

[0002]

2. Description of the Related Art As one of binary image coding techniques, there is a predictive coding method in which the state of a pixel of interest is predicted from surrounding pixels and the predicted result is coded. In predictive coding, surrounding pixels that are considered to have a correlation with the pixel of interest are used for prediction as Markov information sources. The simplest prediction method is to determine the match with the pixel immediately before the pixel of interest,
There is a method of encoding based on the length of a portion where white pixels or black pixels continue.

A random dither method such as an error diffusion method or a minimum mean error method is known as a method for converting a multi-valued image signal such as a photograph into a binary image and reproducing the gradation in a pseudo manner. However, since the signal sequence binarized by the random dither method has no periodicity and white and black appear at random, the above-described prediction method for determining the coincidence with the immediately preceding pixel is sufficient. The compression ratio cannot be obtained.

As a method of improving the compression efficiency for a signal sequence binarized by such a random dither method,
For example, as described in Japanese Patent Application Laid-Open No. 4-239271, a state value formed by a combination of signal values of a region including a plurality of pixels adjacent to or adjacent to a target pixel is input as an address to a prediction table and output. The prediction value is used to generate prediction error data.

An arithmetic coding method is one of the methods for coding the prediction error data. The arithmetic coding method is, for example, as disclosed in Japanese Patent Publication No. 1-17295.
The area on the number line is divided according to the occurrence probabilities of 1 and 0 of the input symbol, and the area is selected according to the value of the input symbol. At this time, a symbol (predominant symbol) that matches the prediction is set to MPS (More probable Sy).
mbol), L that is a non-matching symbol (recessive symbol)
It is called PS (Less probable Symbol).

FIG. 5 is a conceptual diagram of arithmetic coding. The hatched areas are the effective areas after the symbol coding is completed. In the initial state, the effective area is the [0, 1) section, and the area width LSZ (0) when LPS occurs is set. 1-LSZ (0) is the region width when MPS occurs. Here, the MPS is when the symbol is “0”,
When it is "1", it is set as LPS. In FIG. 5, the probability value is 2
It is shown in a decimal number.

In FIG. 5, since the first input symbol is "0", the effective area is changed to that shown in FIG.
The hatched area in (A). Then, a new area width LSZ (1) that divides the effective area into areas when LPS occurs and when MPS occurs is set. When the next symbol is "1", the occurrence of LPS causes
The hatched area in (B) is the effective area. Similarly, when the third symbol is “0”, the hatched area in FIG. 5C is the effective area, and when the fourth symbol is “1”, the area shown in FIG.
The hatched area in (D) is the effective area.

The output code is represented by C. The code for the input symbol string “0101” is shown in FIG.
It may be one point in the effective area in (D). Here, the basis of the effective area, that is, the smallest value C (3) of the effective area is represented as a code and output.

In arithmetic coding, in the process of coding,
Since one point in the effective area is used as a code, if the area is made large, the effective digits decrease and the code amount decreases. In other words, by reducing the value of LSZ as much as possible when MPS occurs and increasing the value of LSZ as much as possible when LPS occurs, it is possible to secure a large effective area and reduce the code amount.

As described above, highly efficient coding can be realized by changing the estimated probability of occurrence of MPS and LPS according to the predictive predictive value or the like. For example, JP-A-2-285
In Japanese Patent No. 776, an image to be coded is provided by assigning an index that changes according to the appearance history of the pixel value of the pixel of interest for each state value and performing arithmetic coding using a coding parameter corresponding to the index. Efficient encoding that is suitable for the characteristics of. As the encoding parameter, the predicted value and the LSZ value are adaptively changed.

FIG. 6 is a block diagram showing an example of a conventional coding apparatus. In the figure, 1 is an image signal, 2 is a line memory, 3 is a line memory output, 4 is a state determination circuit, 5 is a state signal, 6 is a probability state storage memory, 7 is an index,
8 is a dominant symbol, 9 is a coding parameter table, 1
0 is an encoding parameter, 11 is an index update circuit,
12 is a new dominant symbol, 13 is a new index, 14 is an EX-NOR circuit, 15 is a prediction signal, 16 is an arithmetic encoder, 17 is a code, 18 is a transition destination index table,
19 is a transition destination index, 20, 21, 22, 23,
Reference numerals 24 and 25 are flip-flops.

The binary image signal 1 is input to the line memory 2 and holds data for a plurality of lines. The line memory output 3 from here is input to the state determination circuit 4. The state determination circuit 4 determines the state to which the target pixel belongs from the respective values of the target pixel and the adjacent or adjacent pixel groups. Figure 7
FIG. 3 is an explanatory diagram of an example of a pixel referred to by a state determination circuit. When P is a pixel of interest, reference pixels X _{9 to} X ₀ adjacent to or adjacent to the pixel P can be referred to. The pixel to be referred to is not limited to the pattern shown in FIG. Also, the pixel to be dynamically referenced may be changed.

The state signal 5 (CX) representing the state to which the pixel of interest belongs, which is determined by the state determining circuit 4, is input to the stochastic state storage memory 6 via the flip-flop 20.
FIG. 8 is an explanatory diagram of an example of the contents of the probability state storage memory. In the example shown in FIG. 8, the probability state storage memory 6 makes a transition for each state represented by the state signal 5 (CX) depending on the symbol (dominant symbol MPS) that is likely to appear and the appearance history of the pixel value of the target pixel. The index (ST) is stored. The status signal 5 (CX) is shown in binary, but in this example, the reference pixels X _{9 to} X shown in FIG. 7 are used.
It is shown corresponding to each pixel value of ₀ . For example, if only the value of the reference pixel X ₀ is “1” and the other reference pixels are “0”, the status signal 5 (CX) is “0000”.
000001 ”is given to the stochastic state storage memory 6, and M
PS "1" and index "2" are obtained.

M read from the stochastic state storage memory 6
In the EX-NOR circuit 14, the PS8 is compared with the image signal 1 input through the flip-flop 21, that is, the value of the pixel of interest, and outputs a prediction signal 15 that is 1 when they match and 0 when they do not match. . On the other hand, the index 7 (ST) is input to the coding parameter table 9. FIG. 9 is an explanatory diagram of an example of the encoding parameter table. The coding parameter table 9 stores coding parameters corresponding to the index 7 (ST). In the example shown in FIG. 9, the appearance probability LSZ of a symbol (inferior symbol LPS) that is unlikely to appear is stored as an encoding parameter. For example, when the state is "2", "0x1114" is obtained as the LSZ. Here, the numerical value starting with "0x" is a hexadecimal number. Coding parameter 10 read from coding parameter table 9 corresponding to input index 7 (ST)
(LSZ) is used by the arithmetic encoder 16.

The transition destination index table 18 supplies to the index update circuit 11 the transition destination index 19 which has the possibility of the next transition from the current index. FIG. 10 is an explanatory diagram of an example of the transition destination index table. In the transition destination index table shown in FIG. 10, corresponding to index 7 (ST), there is a possibility of transition (MPS transition) when the image signal matches MPS, and transition when it does not match. Index NL that has the possibility of (LPS transition)
PS is stored. In addition, a flag indicating whether or not the MPS value held in the probability state storage memory 6 can be updated may be added. The transition destination index table 18 outputs the index NMPS and the index NLPS as the transition destination index 19 to the index update circuit 11 according to the index 7 (ST) output from the probability state storage memory 6.

In the index update circuit 11, the prediction signal 1
5 and LSZ 10 are used to determine whether to rewrite the stochastic state storage memory 6 according to a certain condition. When rewriting the probability state storage memory 6, the index NMPS or the index NLPS of the transition destination indexes 19 given from the transition destination index table 18 is selected according to the prediction signal 15 and is set as the new index 13. Further, the new dominant symbol 12 is generated and output according to the MPS 8 output from the probability state storage memory 6. New dominant symbol 12 and new index 13
Are latched by flip-flops 22 and 23, respectively, and the contents of the probability state storage memory 6 are rewritten at the next clock.

The algorithm of the index update circuit 11 differs depending on the encoding method, but for example, ISO115.
In the so-called JBIG method recommended by S.44, the probability state storage memory 6 is rewritten when normalizing the augent register A used in arithmetic coding. Normalization means that the value of the orient register A is 0.5 <A <
It is an operation to shift a register so that it falls within the range of 1.0.

The arithmetic encoder 16 performs arithmetic encoding using the prediction signal 15 and the LSZ 10 input via the flip-flops 24 and 25, respectively, and the reference numeral 17
Is output.

The operation of the above coding apparatus will be described by using a specific example. FIG. 11 is an explanatory diagram of a specific example of input image data. In FIG. 11, only the image data 1 of the portion shown in FIG. 7 is shown. As shown in FIG.
Status signal 5 (CX) is "0000000011" (X ₉
˜X ₀ ), consider the case where the pixel of interest P is 1. It is assumed that the stochastic state storage memory 6, the coding parameter table 9, and the transition destination index table 18 have the contents shown in FIGS. 8, 9, and 10, respectively.

First, "000" is given as the status signal 5 (CX).
“0000011” is input to the probability state storage memory 6. At this time, the state signal 5 is stored in the probability state storage memory 6.
Corresponding to (CX) "0000000011", MPS "0" and index "80" are stored as shown in FIG. The index “80” read from the stochastic state storage memory 6 is the encoding parameter table 9
And the transition destination index table 18 are input.
Next, the index “8” of the encoding parameter table 9
0 ”is referred to, LSZ“ 0x5832 ”is read out, and output to the arithmetic encoder 16.

At this time, although the value of the pixel of interest P is "1", MP read from the encoding parameter table 9
Since S is "0", it means that LPS has occurred. When LPS occurs, this LSZ basically becomes the next effective area. Since LSZ is usually less than 0.5, normalization is performed so as to be 0.5 or more and less than 1. The index update circuit 11 sets the NLPS value “80” corresponding to the index “80” in the transition destination index table 18 as the new index 13,
State signal 5 (CX) “0000 of probability state storage memory 6
It is overwritten as an index corresponding to "000011". Also, the MPS is inverted and the new superior symbol 12 becomes "1", and the status signal 5 (CX) "00000000".
11 ”is overwritten as the MPS corresponding to. 12
FIG. 7 is an explanatory diagram of a specific example of the stochastic state storage memory 6 after rewriting. In this way, as shown in FIG. 12, the state signal 5 (CX) “000000” of the stochastic state storage memory 6 is set.
The MPS and index corresponding to "0011" are rewritten. The rewritten probability state storage memory 6 is used to predict the next image data 1. When the same context is input next, the predicted value is 1.

Although LPS occurs in this example, if MPS occurs, the index in the probability state storage memory 6 is rewritten to NMPS "81" in the transition destination index table 18 when normalization is performed. After the rewriting, when the same state signal 5 (CX) is input next time, the index is “81”, and the LSZ at this time is as shown in FIG.
Becomes “0x4d1c”. This value is smaller than LSZ “0x5832” at the time of index “80”, that is, the probability that LPS will occur is small. This is because the prediction at the same state signal 5 (CX) of the previous time was correct. Therefore, when the same state signal 5 (CX) is input next time, the region width when the MPS occurs is widened and the prediction is performed again. When it hits, the effective area can be widened, and the final effective area can be increased and the code amount can be reduced.

According to such a circuit, since the coding is performed while rewriting the contents of the probability state storage memory 6, it is possible to reduce the code amount by arithmetic coding and realize highly efficient coding. However, in the above-described encoding device, the probability state storage memory 6, the encoding parameter table 9, the transition destination index table 19, and the index updating circuit 11 exist between the flip-flop 20 and the flip-flops 22 and 23, and these circuits are provided. The total of the delay times of the above decides the operation speed of the entire encoding device. For example, a maximum of 12 ns for reading the probability state storage memory 6, a maximum of 13 ns for reading the coding parameter table 9 and the transition destination index table 19,
If the index update circuit 11 has a maximum delay of about 25 ns, the entire encoding device has a delay of 20 MH.
Only works at z.

As a method generally used to increase the operation speed, it is known that among the processes, those processes that can be executed independently are pipelined and executed in parallel. However, in the conventional encoding device shown in FIG. 6, as shown in the above-described specific example, the contents of the probability state storage memory 6 also change when the index is updated, so that the flip-flop 20 and the flip-flop 20 are not changed. Could not be further pipelined between
There is a problem that it is difficult to improve the operation speed of the encoding device.

[0025]

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned circumstances, and the reading of the coding parameter table of the coding apparatus and the change of the index can be pipelined, and the coding can be performed at high speed. It is an object of the present invention to provide an image data encoding device that can be used.

[0026]

According to a first aspect of the present invention, in an image data encoding device, a memory for sequentially storing input binary image signals, and one of the binary image signals are stored.
One pixel of interest is defined as a pixel of interest signal, and the pixel of interest is classified by a state value consisting of a combination of values of a plurality of binary image signals adjacent to or adjacent to the pixel of interest stored in the memory, and a specific pixel value appears for each state value A probability state storage memory that stores an index that is appropriately updated corresponding to a probability; a first parameter holding unit that supplies a first parameter corresponding to the index stored in the probability state storage memory; Second parameter holding means for supplying a second parameter corresponding to at least one index whose index may be updated; updating means for updating the index stored in the stochastic state storage memory; If the state value is equal to the immediately preceding state value and the index is updated by the updating means, Selecting means for selecting one of the outputs of the second parameter holding means and for selecting the output of the first parameter holding means in other cases, and arithmetic for arithmetically encoding the image signal according to the parameter selected by the selecting means It is characterized by having an encoder.

According to a second aspect of the present invention, in the image data encoding apparatus according to the first aspect, the second parameter holding means may receive the index as an address and update the index. It is a storage device in which two parameters corresponding to two indexes are stored at the address.

According to a third aspect of the present invention, in the image data encoding apparatus according to the first aspect, the second parameter holding means is one of a plurality of indexes in which the index may be updated. One is a memory device in which one is selectively input as an address and a parameter corresponding to the selected index is stored in the address.

[0029]

1 is a block diagram showing a first embodiment of an image data coding apparatus according to the present invention. In the figure,
The same parts as those in FIG. 6 are designated by the same reference numerals and the description thereof will be omitted. 31 and 32 are selectors, 33 is a transition signal, 34 and 3
5 is an encoding parameter, 36 is a first encoding parameter table, 37 is a second encoding parameter table, 3
Reference numerals 8, 39 and 40 are flip-flops.

The first coding parameter table 36 is the same as the coding parameter table 9 in FIG. 6, and the coding parameter L corresponding to the index ST is used.
SZ is stored. In the first embodiment, a second coding parameter table 37 is provided in addition to the first coding parameter table 36. In the second encoding parameter table 35, the encoding parameter LSZ ′ corresponding to the transition destination index when the MPS transition is made from each index ST and the encoding parameter LS corresponding to the transition destination index when the LPS transition is made.
Z ”is stored. The selector 31 corresponds to the encoding parameter LSZ read from the first encoding parameter table 36 and the transition destination index when the MPS transition is read from the second encoding parameter table 37. Any one of the coding parameter LSZ ′ and the coding parameter LSZ ″ corresponding to the transition destination index in the case of LPS transition is set to the index updating circuit 1
Switching is performed according to the transition signal 33 output from 1. The selector 32 uses the dominant symbol 8 (MPS) output from the probability state storage memory 6 or the index update circuit 1.
One of the new dominant symbols 12 (MPS ') output from 1 is selected and input to the EX-NOR circuit 14.

The binary image signal 1 is input to the line memory 2 and the data for a plurality of lines is held. Line memory 3
By inputting the line memory output 3 from 1 to the state determining circuit 4, the state to which the pixel of interest in the image signal 1 belongs is determined. The status signal 5 (CX) representing the determined status is
It is input to the stochastic state storage memory 6 via the flip-flop 20. The state signal 5 (C
The dominant symbol MPS and the index ST are stored for each state represented by X).

The index 7 (ST) read from the probability state storage memory 6 is input to the first coding parameter table 36 and the second coding parameter table 35. From the first encoding parameter table 36, the encoding parameter 10 (LSZ) corresponding to the index 7 (ST) is output. Also, from the second encoding parameter table 35, the index 7 (ST)
To the encoding parameter 34 (LSZ ′) corresponding to the transition destination index when the MPS transition is made, and the encoding parameter 35 (LSZ ″) corresponding to the transition destination index when the LPS transition is made.
Of the outputs of the first coding parameter table 36 and the second coding parameter table 37, the status signal 5
(CX) is the status signal 5 (C
X) and the transition signal 33 output from the index update circuit 11 indicates an MPS transition, the encoding parameter 34 (LSZ ′) is set, and the state signal 5 (CX) is set in the immediately previous clock cycle. Same as the signal 5 (CX), the coding parameter 35 (LSZ ″) is selected when the transition signal 33 indicates the LPS transition, and the coding parameter 10 (LSZ) is selected otherwise, and the flip-flop 39 is selected. It is supplied to the index update circuit 11 and the arithmetic encoder 16 via the index update circuit 11.

The selector 32 selects the dominant symbol 8 (MPS) when the status signal 5 (CX) is different from the status signal 5 (CX) in the immediately previous clock cycle, and selects the dominant symbol 8 (MPS) otherwise. Select the new superior symbol 12 (MPS ') output from the EX-NO
Input to one of the R circuits 14. The image signal 1 input via the flip-flop 21 is input to the other input of the EX-NOR circuit 14. In the EX-NOR circuit 14, these two input signals are compared, and if they match, it is 1,
When they do not match, the prediction signal 15 which becomes 0 is output.

The transition destination index table 18 uses, as the transition destination index 19, the transition destination index NMPS when the MPS transition occurs and the transition destination index NLPS when the LPS transition occurs via the flip-flop 38. It is supplied to the index update circuit 11. The index update circuit 11 uses the prediction signal 15 and the coding parameter 1 selected by the selector 31.
0 (LSZ), the encoding parameter 34 (LSZ ′), or the encoding parameter 35 (LSZ ″) is used for the determination process, and the probability state storage memory 6 is stored under a certain condition.
The MPS and the index ST in the new dominant symbol 12 (MPS ') and the new index 13 (S
T '). The value of the new index 13 (ST ') is selected from the transition destination index 19 supplied from the transition destination index table 18 in advance. New dominant symbol 12 (MPS ') and new index 13
(ST ') is the flip-flops 22 and 23, respectively.
Are latched in and the contents of the stochastic state storage memory 6 are rewritten in the next clock cycle. Furthermore, a transition signal 33 indicating whether or not the index is updated and, if the update occurs, whether it is due to an MPS transition or an LPS transition.
Is output.

The arithmetic encoder 16 includes a flip-flop 40.
Of the prediction signal 15 input via the flip-flop 39 and the coding parameter 10 (LSZ) selected by the selector 31 input via the flip-flop 39, the coding parameter 34 (LSZ ′), and the coding parameter 35 (LS).
Z ″) is used to perform arithmetic encoding, and the code 1
7 is output.

FIG. 2 is a timing chart showing an example of the operation in the first embodiment of the image data coding apparatus of the present invention. First, the operation when the state signal 5 (CX) changes from the immediately previous clock cycle will be described using the operation for CX1 input in clock cycle 1.

CX1 which is the status signal 5 input in the clock cycle 1 is input to the stochastic state storage memory 6 in the clock cycle 2 and the index 7 corresponding to CX1.
ST1 is read as. The index STa corresponding to CX0 is updated in the immediately preceding clock cycle, but since CX0 and CX1 are different, the index ST1 of CX1 is not affected. ST1 is clock cycle 3
At the first encoding parameter table 36 and the second encoding parameter table 37, the encoding parameters LSZ1 corresponding to ST1 and the encoding parameters LSZ2 and ST1 when the MPS transition is made from the ST1 are performed. Then, the encoding parameter LSZc is output. The selector 31 selects LSZ1 from these and supplies it to the arithmetic encoder 16 in clock cycle 4. Further, in the clock cycle 3, assuming that the index update circuit 11 determines that, for example, an MPS transition has occurred, NMPS is selected from the transition destination index 19 and output as the new index ST2. The rewriting of the probability state storage memory 6 is performed in the clock cycle 4.

Next, the same CX as the immediately previous clock cycle
Is input and the MPS transition occurs in the immediately previous clock cycle, and the operation of rewriting the stochastic state storage memory 6 is performed, the C input in the clock cycle 2 is input.
The operation for X1 will be described. The CX1 input in the clock cycle 2 is input to the stochastic state storage memory 6 in the clock cycle 3. Since the MPS transition has occurred in the immediately previous clock cycle, the index corresponding to CX1 should be the updated index ST2. However, since the rewriting of the probability state storage memory 6 is performed in the clock cycle 4, the same ST1 as in the clock cycle 2 is read in the clock cycle 3. Therefore, in clock cycle 4, the coding parameters LSZ1 and ST1 are read from the first coding parameter table 36 and the second coding parameter table 37.
Parameter LSZ2 when the MPS transition is made from
And the encoding parameter LSZc at the time of the LPS transition from ST1 is read. The selector 31 selects the correct encoding parameter LSZ2 from these and supplies it to the arithmetic encoder 16 in clock cycle 5. At the same time, since the dominant symbol 8 output from the probability state storage memory 6 is before updating, the new dominant symbol 23 output from the index updating circuit 12 is selected by the selector 32, and the EX-NOR circuit 14 is selected. Predicted signal 1
5 is created and supplied to the arithmetic encoder 16. Here, in the clock cycle 4, the index update circuit 1
It is assumed that it is determined that the update does not occur in 1, and the probability state storage memory 6 is not rewritten.

Next, the same CX as the immediately previous clock cycle
Will be described, and the operation when neither MPS transition nor LPS transition occurs in the immediately previous clock cycle will be described using the operation for CX1 input in clock cycle 3. The CX1 input in the clock cycle 3 is input to the probability state storage memory 6 in the clock cycle 4. At this time, the index is rewritten to the correct index ST2 by the MPS transition of the clock cycle two before. ST2 is input to the first coding parameter table 36 and the second coding parameter table 37 at clock cycle 5, and the coding parameters LSZ2 corresponding to ST2 and the coding parameters LSZd and ST2 when the MPS transition is made from ST2. To LPS
The coding parameter LSZ3 at the time of the transition is output. The selector 31 selects LSZ2 from these,
It is supplied to the arithmetic encoder 16 in the clock cycle 6. Further, for example, in the clock cycle 5, when the index update circuit 11 determines that the LPS transition has occurred, the updated index ST3 is output. Rewriting of the stochastic state storage memory 6 is performed in the clock cycle 6.

Finally, the same CX as the immediately previous clock cycle
Is input and the LPS transition occurs in the immediately previous clock cycle, the operation for CX1 input in clock cycle 4 will be described. The CX1 input in the clock cycle 4 is input to the probability state storage memory 6 in the clock cycle 5. Since the LPS transition has occurred in the immediately previous clock cycle, the index corresponding to CX1 should be the updated index ST3. However, the probability state storage memory 6
Is rewritten in clock cycle 6, so in clock cycle 5, ST2, which is the same as clock cycle 4, is written.
Will be read. Therefore, in the clock cycle 6, the coding parameters LSZ2, the coding parameter LSZd at the time of the MPS transition from ST2 and the coding parameter LSZ3 at the time of the LPS transition from ST2 are read from the first and second coding parameter tables. The selector 31 selects the correct encoding parameter LSZ3 from these and supplies it to the arithmetic encoder 16 in clock cycle 7. At the same time, the dominant symbol 8 output from the stochastic state storage memory 6 has not been updated yet, so the new dominant symbol 23 output from the index update circuit 12 is selected by the selector 32 and EX-
Prediction signal 15 is created by NOR circuit 14 and arithmetic encoder 1
Supply to 6.

As described above, in the first embodiment, the first
The selector 31 is provided between the encoding parameter table 36 and the second encoding parameter table 37 and the index update circuit 11 to update the index of the probability state storage memory 6 and the second code of the encoding parameter being updated. By making it possible to read from the encoding parameter table 37 at the same time, it becomes possible to parallelize the encoding parameter reading process and the index updating process. This limits the operating speed of the encoder by
Probability state storage memory 6 and first encoding parameter table 36 or second encoding parameter table 37
Or the delay time of the index update circuit 11. For example, a maximum of 12 ns for reading the probability state storage memory 6, a maximum of 13 ns for reading the first encoding parameter table 36 or the second encoding parameter table 37, and the index updating circuit 11
Assuming that a maximum delay of about 25 ns occurs, the entire apparatus can operate at about 40 MHz, which enables high-speed processing as compared with the conventional encoding apparatus of 20 MHz.

FIG. 3 is a block diagram showing the second embodiment of the image data encoding apparatus of the present invention. In the figure, the same parts as those in FIG. 41 is a selector. The process from the input of the image signal 1 to the reading of the probability state storage memory 6, the output of the prediction signal 15, and the transition destination index table 18 are the same as those in the first embodiment. In this example, the second encoding parameter table 37 is the transition destination index table 18
NMPS that is the transition destination index 19 output from
Alternatively, one of the NLPS is selected by the selector 41 and input.

Similar to the first coding parameter table 36, the second coding parameter table 37 stores the coding parameter LSZ corresponding to the index ST. Further, the selector 41 selects NMPS when the prediction signal 15 is 1 out of NMPS and NLPS output from the transition destination index table 18, and N when it is 0.
LPS is selected and the second encoding parameter table 3
Supply to 7. Second encoding parameter table 37
Is the transition destination index 19 selected by the selector 41.
The encoding parameter 34 (LSZ ') is output according to NMPS or NLPS of the above.

In the first coding parameter table 36, the coding parameters LS corresponding to the index ST are stored.
Z is stored, and the coding parameter 10 (LSZ) corresponding to the index 7 (ST) is read. When the status signal 5 (CX) is the same as the status signal 5 (CX) in the immediately previous clock cycle and the transition signal 33 output from the index update circuit 11 indicates that the index update has occurred, the selector 31 , The encoding parameter 3 output from the second encoding parameter table 37
4 (LSZ '), otherwise encoding parameter 10
(LSZ) is selected and supplied to the index update circuit 11 and the arithmetic encoder 16 via the flip-flop 39.

The index update circuit 11 uses the prediction signal 1
5 and the coding parameter 10 (LSZ) or the coding parameter 34 (LS) selected by the selector 31.
Z ') is used to perform the determination process, and under certain conditions, the MPS and index ST are set as the new dominant symbol 12 (MPS') and the new index 13 respectively.
Update to (ST '). New index 13 (ST ')
The value of is selected from the index 19 supplied from the transition destination index table 18 in advance. New dominant symbol 12 (MPS ') and new index 13 (S
T ′) is latched by the flip-flops 22 and 23, respectively, and rewrites the contents of the stochastic state storage memory 6 in the next clock cycle. Further, a transition signal 33 indicating whether or not the index is updated is output.

Further, the arithmetic encoder 16 receives the prediction signal 15 input through the flip-flop 39 and the encoding parameter 10 (LS) selected by the selector 32, respectively.
Z) or the encoding parameter 34 (LSZ ') is used to perform arithmetic encoding, and the code 17 is output.

FIG. 4 is a timing chart showing an example of the operation of the second embodiment of the image data coding apparatus of the present invention. First, the operation when the status signal 5 (CX) changes from the immediately previous clock cycle will be described using the operation for CX1 input in clock cycle 1.

CX1 input in clock cycle 1
Is input to the probability state storage memory 6 in clock cycle 2, and the index ST1 corresponding to CX1 is read. Even if the index corresponding to CX0 is updated in the immediately preceding clock cycle, since the status signal 5 is different, it does not affect the index ST1 of CX1. ST
1 is input to the first encoding parameter table 36 at clock cycle 3 and outputs the encoding parameter LSZ1 corresponding to ST1. The selector 31 selects LSZ1 from the output LSZb of the second encoding parameter table 37 and the output LSZ1 from the first encoding parameter table 36, and in the clock cycle 4, the arithmetic encoder 1
Supply to 6. At the same time, the selector 32 causes the dominant symbol 8 (MP
S) and the new dominant symbol 23 (MPS ') output from the index update circuit 11
Select (MPS) and input to the EX-NOR circuit 14,
The prediction signal 15 is created and supplied to the arithmetic encoder 16. According to the prediction signal 15, the selector 41 selects NMPS or NLPS from the transition destination indexes 19 output from the transition destination index table 18 and supplies it to the second encoding parameter table 37. In clock cycle 3, the index update circuit 11 uses MP
It is determined that an S or LPS transition has occurred, and the updated index ST2 is output. Rewriting of the stochastic state storage memory 6 is performed in the clock cycle 4.

Next, the same CX as the immediately previous clock cycle
Is input and the MPS transition or LPS transition occurs in the immediately previous clock cycle to update the stochastic state storage memory 6, the operation for the CX1 input in clock cycle 2 will be described. The CX1 input in the clock cycle 2 is input to the stochastic state storage memory 6 in the clock cycle 3. Since the MPS transition or the LPS transition has occurred in the immediately previous clock cycle, the index corresponding to CX1 should be the updated index ST2. However, since the rewriting of the probability state storage memory 6 is performed in the clock cycle 4, the same ST1 as in the clock cycle 2 is read in the clock cycle 3. Therefore, in clock cycle 4, the first encoding parameter table 3
The encoding parameter LSZ1 is read from 6. On the other hand, the transition destination index ST2 in the immediately previous clock cycle is input to the second encoding parameter table 37, and the encoding parameter LS corresponding to ST2 is input.
Z2 is read. The selector 31 selects the correct encoding parameter LSZ2 from these and supplies it to the arithmetic encoder 16 in clock cycle 5. Also, selector 3
2 selects the new superior symbol 23 (MPS ') and EX-
Prediction signal 15 is created by NOR circuit 14 and arithmetic encoder 1
Supply to 6. Here, it is assumed that the index update circuit 11 determines that the update does not occur in the clock cycle 4. Therefore, it is assumed that the probability state storage memory 6 is not rewritten.

Next, the same CX as the immediately previous clock cycle
Will be described, and the operation when neither MPS transition nor LPS transition occurs in the immediately previous clock cycle will be described using the operation for CX1 input in clock cycle 3. The CX1 input in the clock cycle 3 is input to the probability state storage memory 6 in the clock cycle 4. At this time, the index is rewritten to the correct index ST2 by the MPS transition or LPS transition of the clock cycle two before. ST2 is input to the first encoding parameter table 36 in clock cycle 5 and outputs the encoding parameter LSZ2 corresponding to ST2. The selector 31 outputs the first encoding parameter LSZc output from the second encoding parameter table 37 and the first encoding parameter LSZc.
LSZ output from the encoding parameter table 36 of
LSZ2 is selected from 2 and supplied to the arithmetic encoder 16 in the clock cycle 6. In this case, selector 3
2 selects the superior symbol 8 (MPS) and EX-NOR
The circuit 14 produces the prediction signal 15 and supplies it to the arithmetic encoder 16.

As described above, also in the second embodiment, the first encoding parameter table 36, the second encoding parameter table 37, and the index updating circuit 11 are provided as in the first embodiment described above. Between selector 3
4, it is possible to parallelize the updating process of the probability state storage memory 6 and the reading process of the coding parameter by the second coding parameter table 37. As a result, the operation speed of the encoding device is limited by the sum of the stochastic state storage memory 6 and the read time of the first encoding parameter table 36 or the second encoding parameter table 37, or the index updating circuit 11. It becomes a delay time. For example, there is a maximum delay of 12 ns for reading the probability state storage memory 6, a maximum of 13 ns for reading the first coding parameter table 36 or the second coding parameter table 37, and a maximum delay of about 25 ns for the index updating circuit 11. If it occurs, the entire device can operate at about 40 MHz, which enables high-speed processing as compared with 20 MHz of the conventional encoding device.

In each of the above-mentioned embodiments, the flip-flop is not provided at the output of the stochastic state storage memory 6, but a new flip-flop may be provided to increase the number of pipeline stages.

[0053]

As is apparent from the above description, according to the present invention, the process of reading the coding parameter table and the process of changing the index can be performed in parallel, so that these processes can be pipelined. There is an effect that it is possible to realize an image data encoding device with a high processing speed.

[Brief description of drawings]

FIG. 1 is a configuration diagram showing a first embodiment of an image data encoding device of the present invention.

FIG. 2 is a timing chart showing an example of operation in the first embodiment of the image data encoding device of the present invention.

FIG. 3 is a configuration diagram showing a second embodiment of an image data encoding device of the present invention.

FIG. 4 is a timing chart showing an example of operation in the second embodiment of the image data encoding device of the present invention.

FIG. 5 is a conceptual diagram of arithmetic coding.

FIG. 6 is a block diagram showing an example of a conventional encoding device.

FIG. 7 is an explanatory diagram of an example of pixels referred to by a state determination circuit.

FIG. 8 is an explanatory diagram of an example of contents of a stochastic state storage memory.

FIG. 9 is an explanatory diagram of an example of an encoding parameter table.

FIG. 10 is an explanatory diagram of an example of a transition destination index table.

FIG. 11 is an explanatory diagram of a specific example of input image data.

FIG. 12 is an explanatory diagram of a specific example of the stochastic state storage memory 6 after rewriting.

[Explanation of Codes] 1 ... Image signal, 2 ... Line memory, 3 ... Line memory output, 4 ... State determination circuit, 5 ... State signal, 6 ... Stochastic state storage memory, 7 ... Index, 8 ... Dominant symbol, 9 ...
Coding parameter table, 10 ... Coding parameter,
11 ... Index update circuit, 12 ... New superior symbol,
13 ... New index, 14 ... EX-NOR circuit, 15
... prediction signal, 16 ... arithmetic encoder, 17 ... code, 18 ... transition destination index table, 19 ... transition destination index, 20, 21, 22, 23, 24, 25, 38, 3
9, 40 ... Flip-flops, 31, 32, 41 ... Selectors, 33 ... Transition signals, 34, 35 ... Encoding parameters, 36 ... First encoding parameter table, 37 ... Second encoding parameter table.

Claims (3)

(57) [Claims] 1. A memory for sequentially storing input binary image signals, and a plurality of binary images adjacent to or in proximity to a pixel of interest stored in the memory with one of the binary image signals as a pixel of interest signal. A probability state storage memory that classifies a pixel of interest according to a state value composed of a combination of signal values and stores an index that is appropriately updated corresponding to the appearance probability of a specific pixel value for each state value; A first parameter holding means for supplying a first parameter corresponding to the index stored in, and a second parameter for supplying at least one index with which the index may be updated. 2 parameter holding means, updating means for updating the index stored in the stochastic state storage memory, and the state value directly If it is equal to the previous state value and the index is updated by the updating means, one of the outputs of the second parameter holding means is selected; otherwise, the output of the first parameter holding means is selected. An image data coding apparatus comprising: a selecting unit and an arithmetic encoder that arithmetically codes an image signal according to a parameter selected by the selecting unit. 2. The second parameter holding means is a storage device in which the index is input as an address and two parameters corresponding to two indexes with which the index may be updated are stored in the address. The image data encoding device according to claim 1, wherein the image data encoding device is provided. 3. The second parameter holding unit is selectively input with one of a plurality of indexes in which the index may be updated as an address,
The image data encoding device according to claim 1, wherein the image data encoding device is a storage device that stores a parameter corresponding to the selected index at the address.