JPH08172534A - Coder and its method - Google Patents

Abstract

PURPOSE: To attain high speed processing by dividing a storage means used to estimate an incidence probability of a coded object picture element and updating other storage content for a period when one storage content is being read. CONSTITUTION: An address storage section A1 and an address storage section B2 provide an output of an incidence probability of a coded object picture element based on sets of address information 9, 10 representing reference picture element information (symbol information) of the coded object picture element. A selector 4 selects the incidence probability for each prescribed period and an arithmetic coding section 3 conducts arithmetic coding processing. The address storage section A1 and the address storage section B2 update their own content independently of each other based on updated data 12.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a coding apparatus and method, for example, a coding apparatus which performs coding and decoding by utilizing a memory access method.

[0002]

2. Description of the Related Art The recent development of image processing apparatuses has been remarkable, and many image processing apparatuses capable of processing color images have been commercialized. Particularly in color image processing technology, the technology for encoding / decoding image data is important because of its enormous amount of data.

Various methods have been proposed and put into practical use as image data encoding methods. Among them, the arithmetic encoding method is such that the encoding parameter is changed while the encoding parameter is locally applied to the pixel information source at that time. This is useful in that dynamic adaptation that dynamically changes to adapt to physical properties can be performed relatively easily. In other words, in a system that handles images of various properties and a system that handles images in which the statistical properties greatly change depending on the part of the image, it is extremely effective to perform efficient encoding with the same algorithm. It is valid. For example, dynamic adaptation is possible by estimating local statistical properties from already-encoded pixels and sequentially changing encoding parameters based on the estimated statistical properties.

The arithmetic coding method will be described below with reference to the drawings.

ISO / IEC Committee Draft 115
As described in No. 44, in the conventional arithmetic coding method, the probability line is divided into sections according to the appearance probability of the symbol series, and the binary fractional value indicating the position in the divided section is given to the series. Is the code for. That is, the encoding is performed according to the probability of occurrence of each pixel. The estimation of the appearance probability of each pixel is realized by a learning function that is appropriately updated according to the appearance process of each pixel.

FIG. 3 shows a configuration example of a conventional arithmetic coding device. In FIG. 3, reference numeral 109 is a scanner for inputting image data, 110 is an image memory for temporarily storing the input image data, and 111 is the corresponding address information 1 of an address storage unit 100, which will be described later, for each pixel of each image data.
This is an address conversion unit for converting the address into 03. An address storage unit 100 stores arithmetic parameter information 107 indicating the address information of the arithmetic parameter ROM 106 and estimated symbol information 105. Reference numeral 106 denotes an arithmetic parameter ROM, in which the appearance probability 104 is stored in advance corresponding to the arithmetic parameter (address). An arithmetic coding unit 101 performs arithmetic coding based on the appearance probability 104 and the estimated symbol information 105 to generate coded data 10
2 is output.

The address information 103 input to the address storage unit 100 is address data for reading arbitrary arithmetic parameter information 107 and estimated symbol information 105 in the address storage unit 100.
The content of 0 (arithmetic parameter information 107 and estimated symbol information 105) is the update data 10 from the control unit (not shown).
8 updated.

Next, referring to FIG. 4, the address conversion unit 1
A method of determining the address information 103 in 11 will be described.

In FIG. 4A, each square represents one binary pixel, and a circle overlapping four pixels represents a pixel obtained by reducing the four pixels based on a predetermined reduction algorithm. still,
For the following description, h11 to h16 and h21 to h2 are assigned to each pixel.
6, h31 to h36, L11 to L13, L21 to L23 for each reduced pixel
As such, reference numerals are attached.

First, in FIG. 4A, h13 is a pixel to be coded. Arithmetic encoding is performed based on what kind of symbol the pixel h13 is and what the appearance probability of the symbol is. Each estimation regarding the pixel h13 is performed according to the past appearance situation, but is realized by referring to each pixel (symbol) existing around the pixel h13.

For example, six pixels (h11, h12, h22 to h22 other than the pixel h13 in the area surrounded by the thick line shown in FIG. 4A).
h24, h33) and four reduced pixels (L11, L12, L2)
The address information 103 is composed of 1, L22).

The address storage device 10 is provided with arbitrary and independent address information 103 composed of these pixel groups.
An arbitrary address within 0 can be designated, and reading is performed.

In the case shown in FIG. 4A, each pixel has a binary value, so that the value that the address information 103 can take is 2 to the 10th power, that is, 1024 values.

Next, in FIG. 4B, unlike the case of FIG. 4A described above, consider the case where the pixel h14 is the pixel to be coded. That is, in FIG. 4A, the description has been made on the case of encoding the pixel h13 located at the upper left of the reduced pixel L22, but in FIG. 4B, it is located at the upper right of the reduced pixel L22. Consider the case of encoding pixel h14.

In the case of FIG. 4B, the relative positional relationship between the symbol of the pixel h14 and each pixel referred to in order to estimate its appearance probability is different from that of FIG. 4A. In FIG. 4B, in order to estimate the symbol of the pixel h14 and its appearance probability, the peripheral pixel h12 surrounded by a thick line,
Reference is made to h13, h23 to h25, h34, L12, L13, L22, and L23. As described above, the pixel to be referred to differs depending on the relative positional relationship of the reduced pixel such as L22 with respect to the encoding target pixel, because there is only one reduced pixel among the four pixels before reduction.

Hereinafter, the case where the pixel to be coded has the positional relationship shown in FIG. 4A is called phase 0, and the case where the pixel has the positional relationship shown in FIG. 4B is called phase 1.

Therefore, the address information 103 input to the address storage section 100 needs to include not only the address by the reference pixel described above but also phase information (phase 0 or phase 1).

The conventional arithmetic coding procedure will be described again with reference to FIG.

First, the image data read by the scanner 109 is temporarily stored in the image memory 110, the address conversion unit 111 forms the address information 103 by the pixel value and the phase information for each pixel, and the address storage unit 100. To enter. The address storage unit 100 outputs the arithmetic parameter information 107 to the arithmetic parameter ROM 106 and the estimated symbol information 105 to the arithmetic encoding unit 101 according to the input address information 103. In the arithmetic parameter ROM 106, the arithmetic parameter information 107
Outputs the corresponding appearance probability 104 of the pixel to be encoded. Then, the arithmetic encoding unit 101 performs arithmetic encoding based on the estimated symbol information 105 and the appearance probability 104, and outputs encoded data 102 as appropriate.

The control unit (not shown) is the arithmetic coding unit 1.
When it is detected that the compression rate at 01 is low,
The control unit outputs update data 108 for updating the estimated symbol information 105 and the arithmetic parameter information 107 stored in the address storage unit 100 in order to increase the compression rate. Then, the address storage unit 100 is updated based on the update data 108 to prepare for encoding the next pixel. That is, learning can be performed. The update data 108 is written in the address indicated by the address information 103 on the address storage unit 100.

After that, by repeating the above-mentioned processing, arithmetic coding of a series of pixel columns is performed.

[0022]

However, in the above-mentioned conventional example, when the compression ratio is not good, the address storage unit 100 is frequently updated, and the contents of the address storage unit 100 are updated by the update data 108. Since the exclusive control is performed during the period, the estimated symbol 105 and the arithmetic parameter information 107 for encoding the next pixel could not be read. Therefore, there is a drawback that the encoding processing speed decreases.

In addition, the address storage unit 10 is selected according to the compression ratio.
Since the update frequency of 0 is different, the encoding processing speed changes according to the compression rate and is not constant. However, the input speed of the image data by the scanner 109 is constant, and since the next pixel cannot be processed when the address storage unit 100 is updated, the image memory 110 that temporarily stores the image data is read from the scanner 109. Was indispensable in order to synchronize the input of and the output to the subsequent address storage unit 100. Therefore, it was difficult to achieve cost reduction.

The present invention has been made to solve the above-mentioned problems, and in order to solve the above-mentioned problems, the storage means for estimating the appearance probability of the pixel to be coded is divided, and one of the memories is stored. An object of the present invention is to provide an encoding device and method that can perform high-speed processing at low cost by updating the other stored content while the content is being read.

[0025]

In order to achieve the above-mentioned object, the present invention comprises the following constitutions.

That is, based on the plurality of estimating means for estimating the appearance probability of the pixel to be coded, the selecting means for selecting one of the plurality of estimating means, and the appearance probability by the selected estimating means. Coding means for performing arithmetic coding is provided, and the estimation contents of the plurality of estimation means are independently updated.

For example, the plurality of estimating means are characterized in that the appearance probabilities of the encoding target pixels are updated according to the encoded reference pixels.

For example, the plurality of estimating means are memories, and the appearance probability is stored for each symbol of the pixel to be encoded.

For example, the plurality of estimating means are classified according to phase information of the pixel to be encoded with respect to the reference pixel.

For example, the plurality of estimating means are updated at a predetermined cycle.

For example, the plurality of estimating means are updated when the encoding efficiency in the encoding means decreases.

[0032]

With the above configuration, the storage means for estimating the appearance probability of the pixel to be encoded according to the phase of the reference pixel with respect to the reference pixel is divided, and the storage content of one is updated while the storage content of one is being read. There is a unique effect that can be done.

[0033]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A feature of the present invention is that an address storage unit for storing data for specifying estimated symbols, appearance probabilities, etc.
It is divided into address groups that are periodically referred to, and while reading data from a certain group, it is possible to write update data to another group.

An embodiment according to the present invention will be described in detail below with reference to the drawings.

<First Embodiment> In the arithmetic coding of the present embodiment, a peripheral pixel group referred to for coding a pixel to be coded is the same as that shown in FIG. 4 shown in the conventional example. Therefore,
Two types, phase 0 and phase 1, are assumed.

FIG. 1 shows a block configuration of the arithmetic coding apparatus in this embodiment.

Reference numeral 13 is a scanner for inputting image data, and 1
Reference numeral 4 denotes an address conversion unit that generates address information 9 and 10 for each phase of each pixel of the input image data, similarly to the conventional example. The scanner 13 is not particularly limited to the scanner as long as it can input image data.

1 is the address storage unit A for processing the pixel having the phase 0 described above, 2 is the address storage unit B for processing the pixel having the phase 1 described above, 3 is the arithmetic coding unit, 4 is the It is a selector. The arithmetic encoding unit 3 is assumed to include an arithmetic parameter ROM that stores the appearance probability.

The address storage unit A1 receives the address information 9 when the pixel to be coded has a phase of 0 and inputs the information indicating the appearance probability of the pixel to be coded and the phase information as in the conventional example described above. Output as signal 6. Similarly, the address storage unit B2 receives the address information 10 when the encoding target pixel is in phase 1, and outputs the information indicating the appearance probability of the encoding target pixel and the phase information as a signal 7.

The output signal 6 of the address storage unit A1 and the output signal 7 of the address storage unit B2 are input to the selector 4, one of them is selected by the control signal 5, and output as a signal 11. The output signal 11 (the signal 6 or the signal 7) from the selector 4 is input to the arithmetic coding unit 3, performs the conventional arithmetic coding, and outputs the coded data 8.

The contents of the address storage unit A1 or the address storage unit B2 are the update data 1 from the control unit (not shown).
2, the address indicated by the address information 9 or 10 can be updated.

FIG. 2 shows a timing chart in the above-described coding apparatus of this embodiment. Note that periods 1 to 9 shown in FIG. 2 indicate one cycle of a pixel clock (not shown), and the selector 4 outputs the signal 6 at the L level of the control signal 5.
The signal 7 is selected at the H level.

In the period 1 shown in FIG. 2, when the address information 9 (corresponding to the phase 0) is input as "a1" to the address storage unit A1, the signal 6 including the estimated symbol and the appearance probability information is regarded as "b1". Is output.

Then, the selector 4 selects the signal 6 by the control signal 5, so that the output signal 11 of the selector 4 becomes "b1". The arithmetic coding unit 3 receives the input signal 1
Based on 1, arithmetic coding processing is performed.

Next, in the period 2, the address information 10 (corresponding to phase 1) is "a'1" in the address memory B2.
When it is input at, the signal 7 including the estimated symbol and the appearance probability information is output as “b′1”.

Then, the selector 4 selects the signal 7 by the control signal 5, so that the output signal 11 of the selector 4 becomes "b'1". The arithmetic encoding unit 3 performs arithmetic encoding processing based on the input signal 11.

On the other hand, the content of the address information 9 input to the address storage unit A1 retains "a1" even in the period 2. Therefore, the content of the address "a1" in the address storage unit A1 (estimated symbol and If it is necessary to update the appearance probability information), in period 2,
It can be updated by the update data 12. Since new reading from another address (“a2”) of the address storage unit A1 is performed in the period 3, even if exclusive control is applied to update the contents of the address storage unit A1 in the period 2, the timing is There is no problem.

Then, based on the signal 6 consisting of the estimated symbol and the appearance probability information read from the address storage unit A1 in the period 3, the arithmetic coding unit 3 similarly performs the arithmetic coding, and the address storage unit B2 stores it. When it is necessary to update the content indicated by the address “b1”, the update data 12 is similarly updated in the period 3.

Hereinafter, arithmetic coding of all image data is performed by repeating the above-mentioned processing.

As described above, in this embodiment, the update timing is adjusted by dividing the address storage unit into two. Therefore, the processing efficiency greatly changes depending on the division method of the address storage unit. As is clear from the timing chart of FIG. 2, the address storage unit A
It is most efficient that the reference timings of 1 and the address storage unit B2 are alternated, but an optimal division method may be adopted according to the characteristics of the processing system.

In the present embodiment, an example in which the selector 4 is used to control the signal input to the arithmetic coding unit 3 has been described, but the present invention is not limited to this example, and is optimal. If the estimated symbols and the appearance probability information can be input to the arithmetic coding unit 3, the gist of the present invention is satisfied.

As described above, according to the present embodiment, the address storage unit for storing the data for specifying the estimated symbol, the appearance probability, etc. is divided into address groups which are periodically referred to, The update data can be written in the other group while the reading is performed in the one group, and high-speed processing can be performed.

<Other Embodiments> In the above-described first embodiment, an example in which the address storage unit is divided into two phases has been described, but it is of course possible to divide the address storage unit into two or more phases. Absent. In addition, although the division according to the phase is performed in the first embodiment, if the address information input to the address storage unit has periodicity, it is not limited to the division according to the phase, and the address storage unit may be divided according to the period. The same effect as that of the first embodiment can be obtained.

In the first embodiment described above, the estimated symbol and the appearance probability information are stored in each address storage unit. However, as shown in FIG. 5, for example, between the selector 4 and the arithmetic coding unit 3. By including the decoder 13 in the above, the estimated symbol and the appearance probability information stored in the address storage unit A1 and the address storage unit B2 can be compressed or encoded data. This makes it possible to reduce the capacity of the address storage unit. Of course, the insertion positions of the decoder 13 may be, for example, between the address storage unit A1 and the selector 4 and between the address storage unit B2 and the selector 4.

Further, in the above-described first embodiment, it is desirable to configure the apparatus so that the encoding process can be performed by only one address storage unit even when the input address information has no periodicity.

Further, when updating the contents of the address storage unit, the same address information may be input to a plurality of address storage units so that each address can be updated at the same timing.

The present invention may be applied to a system composed of a plurality of devices or an apparatus composed of one device. Further, it goes without saying that the present invention can be applied to the case where it is achieved by supplying a program to a system or an apparatus.

[0058]

As described above, according to the present invention, the storage means for estimating the appearance probability of the pixel to be coded is divided according to the phase of the reference pixel with respect to the reference pixel, and one of the stored contents is read. By allowing the other stored content to be updated during the period, the learning effect is enhanced, the compression rate is improved, and high-speed processing is possible.

Further, it is not necessary to temporarily store the input image data in order to synchronize the image data input unit and the encoding unit, and the image memory provided in the apparatus is not necessarily required, which is cost effective. It is possible to realize an advantageous configuration.

[0060]

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration example of an encoding device according to an embodiment of the present invention.

FIG. 2 is a timing chart of encoding processing in the encoding device of the present embodiment.

FIG. 3 is a block diagram showing a configuration example of a conventional encoding device that performs arithmetic encoding.

FIG. 4 is a diagram showing a positional relationship between an encoding target pixel and a reference pixel in a conventional encoding device.

FIG. 5 is a block diagram showing another configuration example of the encoding device according to the present embodiment.

[Explanation of symbols]

 1 Address Storage Unit A 2 Address Storage Unit B 3 Arithmetic Coding Unit 4 Selector 13,109 Scanner 14,111 Address Conversion Unit 110 Image Memory

Claims (11)

[Claims] 1. A plurality of estimating means for estimating an appearance probability of a pixel to be encoded, a selecting means for selecting one of the plurality of estimating means, and an appearance probability by the selected estimating means. An encoding device, comprising: an encoding unit that performs arithmetic encoding, wherein the plurality of estimating units update their estimation contents independently of each other. 2. The encoding apparatus according to claim 1, wherein the plurality of estimation means update the appearance probability of the encoding target pixel according to the encoded reference pixel. 3. The encoding apparatus according to claim 2, wherein the plurality of estimating units are memories and store the appearance probability for each symbol of the encoding target pixel. 4. The encoding apparatus according to claim 1, wherein the plurality of estimating units are classified according to phase information of an encoding target pixel with respect to the reference pixel. 5. The encoding device according to claim 1, wherein the plurality of estimating means are updated at a predetermined cycle. 6. The encoding apparatus according to claim 1, wherein the plurality of estimation units are updated when the encoding efficiency of the encoding unit decreases. 7. Based on a plurality of estimation steps for estimating the appearance probability of a pixel to be coded, a selection step for selecting one of the plurality of estimation steps, and an appearance probability by the selected estimation step. An encoding method for performing arithmetic encoding, wherein the estimation contents of the plurality of estimation steps are independently updated. 8. The encoding method according to claim 7, wherein in the plurality of estimation steps, the appearance probability of the encoding target pixel is updated according to the encoded reference pixel. 9. The encoding method according to claim 7, wherein the plurality of estimation steps are classified according to phase information of an encoding target pixel with respect to the reference pixel. 10. The encoding method according to claim 7, wherein the plurality of estimation steps are updated at a predetermined cycle. 11. The encoding method according to claim 7, wherein the plurality of estimation steps are updated when the encoding efficiency in the encoding step decreases.