JPH089165A - Binary image encoding device and binary image decoding device - Google Patents

Abstract

(57) [Summary] [Purpose] High encoding efficiency is obtained by setting an accurate augend according to the probability of symbol appearance. [Structure] In encoding, pixels are extracted from binary image data read into a line memory based on a template, and the values of a context and an encoded pixel of interest are obtained. Symbol appearance probabilities are obtained from the context and the count number of the coded pixel of interest, and they are converted into products of prime numbers by the prime number conversion table. The augend is expressed by the product of prime numbers, and each exponent is added when updating the augend. When the appearance probability inferior symbol appears, the lower bound value of the augend is obtained and a code is generated. In the decoding, pixels are extracted from the decoded data that has been read in the line memory and has been decoded so far, based on the template, and the context is obtained. A code at the time of appearance probability inferior symbol appearance is generated for reference and compared with encoded data to determine whether the decoded symbol is a dominant symbol or an inferior symbol, and to decode it.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION The present invention applies an arithmetic code to
The present invention relates to a binary image encoding / decoding device that encodes / decodes value image data.

[0002]

2. Description of the Related Art Binary image data encoding methods have been widely used for facsimiles. Among these encoding methods, there are those that sequentially encode (hereinafter referred to as “sequential”) and transmit images from top to bottom, or those that enable hierarchical (hereinafter referred to as “progressive”) encoding and transmission. . For the former, MH (Modifid Huffman), MR, MM
There is an R system, and the latter has a JBIG system. The latter is
Image database search, a new image communication service
It is an encoding method suitable for soft copy communication in which information is displayed using a display in front of the user, such as an audio graphics conference. The codes used in these coding methods are both called entropy coding and have the property of lossless coding. Huffman code, JBI in MH, MR and MMR systems
An arithmetic code is used in the G method. Since the arithmetic code is a non-block code, higher compression performance can be expected as compared with the Huffman code.

As an example of a binary image data encoding system to which a conventional arithmetic code is applied, a JBIG type arithmetic code will be described below with reference to the drawings.

The JBIG arithmetic coding is called a QM coder. In the QM coder, a fixed area allocation type (subtraction type) arithmetic code in which the augend operation is executed only by subtraction is used. Although the subtraction type arithmetic code has lower coding efficiency than the arithmetic code, it has an advantage that the code and the decoder are simple. In the JBIG method, binary image data is divided into stripes for encoding processing in order to support both sequential and progressive encoding. FIG. 22 shows a stripe. In FIG. 22, reference numeral 101 represents binary image data.
Further, 102, 103 and 104 represent stripes. Sequential decoding can be supported by preparing a memory buffer for at least one stripe on the decoder side. FIG. 23 shows a functional block diagram of a JBIG encoder. The encoder is 201 in FIG.
Difference hierarchy (layer) due to resolution reduction represented by 202
And the encoding process of the lowest resolution layer represented by 203.

FIG. 24 shows a functional block diagram of encoding processing of a reduced resolution layer. In FIG. 24, reference numeral 301 is a block for performing resolution reduction processing. In addition, 302 and 303 are Physical Predict
Ion (hereinafter referred to as TP), Determ-inist
It is called ic Prediction (hereinafter referred to as DP), and is a method for reducing the number of target pixels for arithmetic coding, which will be described later. TPVA if TP is performed
LUE outputs 0 or 1, and otherwise outputs 2 or 3. If DP is done, DPV
ALUE outputs 0 or 1, otherwise 2
Or 3 is output. In addition, in FIG.
04 is Adaptive Templates (hereinafter A
This is referred to as T), and the AT pixel of the model template, which will be described later, is replaced with the pixel at a position having a greater correlation. 305 is a model template. In the model template, a bit pattern (hereinafter referred to as “context”) is extracted by the pixels of the template. Three
Reference numeral 06 is a QM coder, which performs adaptive arithmetic coding. FIG. 25 shows a functional block diagram of the encoding process of the lowest resolution layer. In FIG. 25, 401 is Ty
It is a physical prediction (TP). Also, 402 is Adaptive Templates.
(AT), 403 is a model template, 404 is QM
It is a coder.

FIG. 26 shows an example of a model template used in the JBIG method. What is a model template?
This is the extraction range of the coded pixel of interest PIX necessary for coding and the pixels in a specific range around it. The pixel at the position 501 in FIG. 26 represents the coded pixel of interest. Further, a numerical representation of a combination of "0" and "1" of pixels around the coded pixel of interest represented by 502 in FIG. 26 is called a context CX. Figure 27 is JBI
7 shows a flow diagram of a G-type encoder. In step 1, initialization processing is performed. In Step 2, the coded pixel of interest PIX, context CX, TPV
Read ALUE and DPVALUE. In the conditional branch of step 3, TPVALUE ≠ 2or3 or DPVA
If LUE ≠ 2 or 3, go to step 5, otherwise go to step 4. ENCODE in step 4
Perform processing. In the conditional branch of step 5, if the stripe is completed, go to step 6; otherwise, go to step 2. In step 6, FLUSH processing is performed. FIG. 28 shows the structure of an augend register (hereinafter referred to as A register) and a code register (hereinafter referred to as C register) used in the JBIG method. The a bit in the A register is a bit (17 bits) representing the probability width.
The x bit (16 bits) in the C register is a bit in which an unfinished code is placed. b bit (8 bits)
Represents the position where the completed code is extracted in 8-bit units. When the symbols “0” and “1” of the coded pixel of interest are predicted based on the context, a symbol having a high appearance probability is called a dominant symbol MPS, and a symbol having a low appearance probability is called a recessive symbol LPS. Further, the probability state (status ST) of each context transits depending on whether the coded pixel of interest is MPS or LPS. The values of MPS (1 bit) and status ST (7 bits) corresponding to each context CX are stored in a memory or the like.

FIG. 29 shows a probability estimation table.
LSZ is the recessive symbol appearance probability corresponding to each status ST, NLPS is the value of the next ST when the LPS appears,
NMPS is the value of the next ST when MPS appears, SWT
CH represents whether MPS is inverted. Figure 30
Is a flow diagram of the ENCODE process. In the conditional branch of step 1, if the coded pixel of interest PIX and the value of the dominant symbol MPS corresponding to the context are the same, the process proceeds to step 3, and if not, the process proceeds to step 2.
In step 2, CODELPS processing is performed. Step 3
Then, CODEMPS processing is performed. Figure 31 is CODELP
The flow diagram of S processing is shown. A and C represent the values of the A register and the C register, respectively. In step 1, A = A-LSZ is performed. In the conditional branch of step 2, if A <LSZ, go to step 4, and if not, go to step 3. In step 3, C = C +
A, A = LSZ is performed. In the conditional branch of step 4, S
If WTCH = 1, go to step 6, otherwise go to step 5. In step 5, MPS = 1-M
Perform PS. In step 6, ST = NLPS is performed,
Perform RENORME processing.

FIG. 32 shows a flow diagram of the CODEMPS process. In step 1, A = A-LSZ
I do. In the conditional branch of step 2, A <0x8000
If so, go to step 3, and if not, end the process. In the conditional branch of step 3, if A <LSZ, go to step 4, and if not, go to step 5.
In step 4, C = C + A and A = LSZ are performed. In step 5, ST = NMPS is performed, and RENORME processing is performed. FIG. 33 shows a flow diagram of the RENORME process. In step 1, A = A << 1
(Shift 1 bit to the left), C = C << 1, CT = CT-
Do 1. In the conditional branch of step 2, if CT = 0, go to step 4, and if not, go to step 3. In step 3, BYTEOUT processing is performed. In the conditional branch of step 4, if A <0x8000, go to step 1; otherwise, end the process.

FIG. 34 shows a flow diagram of the BYTEOUT process. In step 1, TEMP = C
>> 19 (shift to the right by 19 bits). Step 2
In the conditional branch of, if TEMP = 0xff, step 3
Go to step 4, otherwise go to step 4. Step 3
Then, BUFFER = BUFFER + 1 is performed, and BUF
FER is output, 0x00 is output SC times, SC = 0,
Perform BUFFER = TEMP & 0xff. Step 4
In the conditional branch of, if TEMP = 0xff, step 5
If not, go to step 6. In step 5, SC = SC + 1 is performed. BUFF in step 6
ER is output, 0xff is output SC times, SC = 0, B
Perform UFFER = TEMP. In step 7, C = C
& 0x7ffff, CT = 8. Figure 35 is INIT
The flow diagram of ENC processing is shown. In the conditional branch of step 1, go to step 2 if it is just after the first stripe or reset of the current layer, otherwise go to step 3. In step 2, status ST = 0, MPS = 0 for all contexts
To In step 3, the status ST and MPS are set to the last value of the previous stripe of the current layer for all contexts. In step 4, SC = 0, A
= 0x10000, C = 0, CT = 11.

FIG. 36 shows a flow diagram of the FLUSH process. In Step 1, CLEARBITS
Processing, FINALWRITES processing is performed to remove the first 1 byte of the stripe encoded data (SCD).
Also, if desired, remove all 0x00 at the end of the SCD. FIG. 37 shows a flow diagram of the CLEARBITS process. In step 1, TEMP =
(A-1 + C) & 0xffff0000 is performed. In step 2, if TEMP <C, go to step 3, otherwise go to step 4. In step 3, C = TE
Perform MP + 0x8000. In step 4, C = TEM
Perform P. FIG. 38 shows a flow diagram of the FINALWRITES process. In step 1, C = C <
<Perform CT. In the conditional branch of step 2, C> 0xf
If fffff, go to step 3, otherwise go to step 4. In step 3, BUFFER + 1
Is output, and 0x00 is output SC times. In step 4, BUFFER is output and 0xff is output SC times. In step 5, (C >> 19) & 0xff is output and (C >> 11) & 0xff is output. The JBIG decoding is omitted. A more detailed description of the JBIG system and QM coder is given in, for example, "International Standard for Multimedia Coding" (published by Maruzen Co., Ltd.).

[0011]

In the arithmetic code, if a probability width (hereinafter referred to as Augend) can be set according to the probability of appearance of a symbol, extremely high coding efficiency can be obtained. However, the calculation of the Augend when the symbol is coded. In addition, there is a problem in calculation accuracy (the number of significant digits) due to the multiplication of the region width and the probability value and a problem that the code cannot be transmitted until the final symbol is known, which makes it difficult to put into practical use. Also,
In the subtraction type arithmetic code of the JBIG system, the arithmetic code is put into practical use by performing the Augend operation by simple subtraction. However, there is a problem in that the assumed probability of recessive symbols changes twice as the augend value of the augend register changes, so that the coding efficiency is lower than the original arithmetic code. In view of the above problems, the present invention provides a binary image encoding device and a binary image decoding device that solve this problem.

[0012]

According to a first aspect of the present invention, there is provided a binary image coding apparatus, which is a pixel to be coded (hereinafter referred to as a coded pixel of interest) and a specific position (hereinafter referred to as a template) around the coded pixel of interest. Means) for extracting pixels, white and black for each bit pattern (hereinafter referred to as context) by the pixels of the template, the number of appearances of each (hereinafter referred to as the number of symbol appearances), and the sum thereof (hereinafter referred to as context). The first storage means for counting the number of occurrences (referred to as the number of appearances) and storing it in the first memory, and the number of context appearances and the number of symbol appearances by a table reference or the like are a finite number of prime numbers (2, 3, 5, ...) Of the result approximated by the product using
A first conversion means for obtaining a power of each prime number (hereinafter referred to as a prime power sequence); a subtraction means for subtracting a prime power sequence of the context occurrence frequency from the prime power sequence of the symbol appearance frequency for each prime element , A second storage means for storing the result in a second memory, and a probability width (hereinafter referred to as "augend") as a prime power sequence by the conversion means, and a prime power sequence and augend of the symbol appearance probability at the time of updating the agend. An addition means for adding the prime power sequence of
Conversion means for converting the prime power sequence into an integer by a second table reference means, output means for outputting a bit length n of the code from the prime power sequence stored in the augend register by table reference, And a dividing means in which the integer value obtained by the converting means is a dividend, and 2 ⁻ⁿ is a divisor, and the binary image decoding device according to the second aspect of the present invention specifies the periphery of the pixel to be decoded. By means for extracting the pixel at the position, first storage means for counting the number of appearances of white, black, and each of the bit patterns by the pixels of the template, and the sum thereof, and storing the result in the first memory. A first conversion means for obtaining a power of each prime number as a result of approximating the number of context occurrences and the number of symbol appearances by a product using a finite number of prime numbers (2, 3, 5, ...). , Subtracting means for subtracting the prime power sequence of the number of times of occurrence of the context from the power series of the number of times of the symbol occurrence for each prime number element, the second storage means for storing the result in the second memory, and the augend by the conversion means. A prime exponent sequence, and an addition means for adding a prime exponent sequence of the symbol occurrence probability and an augmented prime exponent sequence for each prime number element at the time of updating the augend, and the prime exponent sequence to an integer by the second table reference device or the like. Conversion means for converting, output means for outputting the bit length n of the code from a sequence of prime powers stored in the augend register by table reference, and the integer value obtained by the second conversion means for the dividend 2 ^-n It is composed of a dividing means which is a divisor and a comparing means which compares the encoded data and the reference data.

[0013]

In the binary image coding / decoding device, the pixel of the template around the coded pixel of interest and the coded pixel of interest (or the decoded pixel) is extracted, and the context of the pixel of the template is obtained. The number of appearances of each context and the number of appearances of the symbol “0” and “1” appearing in the coded pixel of interest (or the decoded pixel) are counted and stored in the memory, and the number of appearances of the symbol is the dividend and the number of appearances of the context. When obtaining the symbol appearance probability by the division operation with the divisor as, the number of context appearances and the number of symbol appearances are set to a finite number of prime numbers (2, 3,
5 ,. ． ． ) Is used to represent each exponent of the symbol occurrence probability by subtracting each exponent of the context occurrence probability from each exponent of the symbol occurrence frequency. Each exponent is calculated and stored in a memory. And at the time of arithmetic coding,
When the symbol appearance probability of the coded pixel of interest is sequentially multiplied by the augend to update the augend, the augend is approximated by a product using a finite number of prime numbers (2, 3, 5, ...), and Representing only the powers of prime numbers by adding the powers of the symbol appearance probability to each powers of the augend, the augend is updated by the addition operation, each power is stored in the A register, and when the LPS appears. Only, the value obtained by adding each power number of the MPS appearance probability to each power number of the augend is stored in the C register, and the real value is obtained based on each power number stored in the C register and the corresponding prime numbers. calculates the bit length n of the arithmetic code by referring to the table by the number each should stored in the a register, the real value dividend, divides the 2 ^-n as divisor, the quotient as the code data Forces. Also, at the time of decoding, L
Depending on the PS appearance probability, the augend is updated in sequence,
Furthermore, a value obtained by adding each power of the MPS appearance probability to each power of the augend is stored in the C register, and a real value is obtained based on each power stored in the C register and the corresponding prime numbers. , The bit length n of the arithmetic code is calculated by referring to the table according to each power stored in the A register, and the real value of the C register is divided by the dividend 2 ^-n and the quotient is used for reference. If the data does not match by comparing the encoded data with the reference data, MP
S, if they match, LPS is output as decrypted data.

[0014]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 shows a functional block diagram of the embodiment. In FIG. 1, reference numeral 501 indicates a line memory. Binary image data for three lines is read into the line memory 501. The lines that are read are the line being encoded, the line before one, and the line before two. Fifty
Reference numeral 2 denotes pixel extraction processing. In the pixel extraction processing 502, pixels are extracted from the binary image data in the line memory based on a template described later, and the values of the context CX and the coded pixel of interest PIX are obtained. Reference numeral 503 indicates a counting process. In the count process 502, the number of appearances of the context CX extracted in the image extraction process, the number of times the symbol of the coded pixel of interest is “0”, and the number of times of “1” are counted and stored in the count value storage SRAM. Reference numeral 504 denotes a count value storage SRAM. Reference numeral 505 indicates a prime number conversion process. In the prime number conversion processing 505, symbol appearance probabilities are obtained based on each count value stored in the count value storage SRAM, converted into products of prime numbers by the prime number conversion table, and the exponents are stored in the appearance probability storage SRAM.
To be stored. Also, the MPS of the symbols “0” and “1”,
LPS is determined and MPS is stored. Reference numeral 506 denotes a prime number conversion table ROM. 507 is an appearance probability storage SR
It shows AM. Reference numeral 508 denotes register arithmetic processing. In the register calculation processing 508, the occurrence probability storage SRA
Multiplication processing is performed between the appearance probability stored in M and the A register representing the probability width (orgend). When LPS appears, the lower bound value is written in the C register. Reference numeral 509 indicates an A register. Reference numeral 510 indicates a C register. 51
Reference numeral 1 indicates a code length calculation process. Code length calculation processing 51
In the case of 1, the code length table is searched based on the value of the A register, and the bit length n of the precision required to represent the value of the A register is calculated. Reference numeral 512 denotes a code length table ROM.
Reference numeral 513 indicates a lower bound value calculation process. In the lower bound value calculation processing 513, the value of the C register is converted into a binary decimal based on the prime number table. Reference numeral 514 represents a prime number table ROM. Reference numeral 515 indicates a code generation means. The code generation means generates a code by dividing the lower bound by 2-n. 51
Reference numeral 6 indicates an output buffer. The code is stored in the output buffer once and then output from the upper bit side.

FIG. 2 shows pixels extracted by the template. The pixels extracted by the template are 601 in the figure.
The encoded pixel of interest PIX represented by and the surrounding pixel CXn represented by 602 in FIG. "0" of CXn pixel
The numerical value of the combination of "1" is the context C
X (10-bit value). n represents a pixel corresponding to the nth bit of the context. FIG. 3 shows a flow diagram of the encoder. In step 1, initialization processing is performed. In step 2, the coded pixel of interest PIX and the context CX are read. Step 3
Then, the appearance probability is calculated. In step 4, the augend calculation process is performed. In step 5, encoding processing is performed. In step 6, appearance frequency counting processing is performed. Step 7
In the conditional branch of, the processing is ended if the binary image data is completed, and if not, the process goes to step 2. FIG. 4 shows a flow diagram of the context count process. In step 1, CT (CX) = CT (CX) +
Do 1. In the conditional branch of step 2, if PIX = 0, go to step 3, otherwise go to step 4. In step 3, SYM0 (CX) = SYM0 (C
X) +1. At step 4, SYM1 (CX) = S
Perform YM1 (CX) +1.

FIG. 5 shows a flow diagram of the prime number conversion process. CT (CX) in the conditional branch of step 1
= 50, go to step 2, and if not, end the process. In step 2, i = 1 is performed. Step 3
Then P0 (CX, i) = PWR (SYM0 (CX),
i) -PWR (50, i), P1 (CX, i) = PWR
(SYM1 (CX), i) -PWR (50, i), i =
Perform i + 1. In the conditional branch of step 4, if i is larger than PRMNUM, which is the number of prime numbers, the process proceeds to step 3, and if not, the process proceeds to step 5. In the conditional branch of step 5, if SYM0 (CX) ≧ SYM1 (CX), go to step 6, and if not, go to step 7. In step 6, MPS (CX) = 0 is performed. In step 7, MPS (CX) = 1 is performed. C in step 8
T (CX) = 0, SYM0 (CX) = 0, SYM1 (C
X) = 0. FIG. 6 shows a flow diagram of the augend calculation process. In the conditional branch of step 1, if PIX = MPS (CX), go to step 2, and if not, go to step 3. MPS in step 2
Perform processing. In step 3, LPS processing is performed. FIG. 7 shows a flow diagram of MPS processing. In the conditional branch of step 1, if PIX = 0, go to step 2, and if not, go to step 5. In step 2, i = 1 is performed. In step 3, A (i) = A (i)-
Perform P0 (CX, i), i = i + 1. In the conditional branch of step 4, if i> PRMNUM, the process is terminated, and if not, the process proceeds to step 3. In step 5, i = 1 is performed. In step 6, A (i) = A (i) -P1 (C
X, i), i = i + 1. In the conditional branch of step 7, if i> PRMNUM, the process is terminated, and if not, the process proceeds to step 6.

FIG. 8 shows a flow diagram of the LPS processing. In the conditional branch of step 1, if PIX = 0, go to step 2, and if not, go to step 5. In step 2, i = 1 is performed. C in step 3
(I) = C (i) -P1 (CX, i), A (i) = A
(I) -P0 (CX, i), i = i + 1 is performed. In the conditional branch of step 4, if i> PRMNUM, the process is terminated, and if not, the process proceeds to step 3. In step 5, i = 1 is performed. In step 6, C (i) = C (i) -P
0 (CX, i), A (i) = A (i) -P1 (CX,
i) and i = i + 1. In the conditional branch of step 7, i
If it is> PRMNUM, the process is terminated. If not, go to step 6. FIG. 9 shows a flow diagram of the encoding process. In the conditional branch of step 1, PIX = M
If it is PS (CX), the process is terminated, and if not, go to step 2. In step 2, code length calculation processing is performed. In step 3, lower bound calculation processing is performed. Step 4
Then, C = C0 / 2- ⁿ is performed. In step 5, C is output. FIG. 10 shows a flow diagram of the code length calculation process. In step 1, j = 1 and n = 0 are performed. In step 2, n = n + CL (A (i), i) is performed. In step 3, j = j + 1 is performed. In the conditional branch of step 4, if i> PRMNUM, the process is ended, and if not so, the process goes to step 2.

FIG. 11 shows a flow diagram of the lower bound value calculation processing. In step 1, i = 1 is performed. In step 2, j = 1 is performed. In step 3, C0 = C0 *
Perform PRM (i). In step 4, j = j + 1 is performed. In the conditional branch of step 5, if j> A (i), go to step 6, otherwise go to step 2. In step 6, i = i + 1 is performed. In step 7, if i is larger than the number of prime numbers, the process is terminated, and if not, the process goes to step 1. FIG. 11 shows a flow diagram of the initialization process. PR the number of prime numbers in step 1
MNUM, substituting i-th prime number into PRM (i), CT (CX) = 0, SYM0 (CX) for all CX
= 0, SYM1 (CX) = 0, MPS (CX) = 0, and P0 (CX, 1) =-1, P0 (CX, i) = for all i = 2, 3, ... PRMNUM. 0, P1
(CX, 1) = − 1 and P1 (CX, i) = 0 are performed. FIG. 12 shows a prime number conversion table of this embodiment. In this embodiment, the prime numbers used are 2, 3, 5, and 7, and the number of prime numbers is 4. The 4-digit numbers in the table are powers of 2 and 3, respectively.
Represents the powers of 5, the powers of 5, and the powers of 7.

FIG. 13 shows a table for obtaining the code bit length n from the augend width when the LPS appears. n is a value satisfying 2 ⁻ⁿ ≦ Augend value <2 ^{− (n−1)} .
FIG. 14 shows a functional block diagram of the decoder of the embodiment. In FIG. 14, 701 indicates a line memory. Two lines of binary image data and decoded pixels are read into the line memory. The lines read are the line before the line being encoded and the line two lines before. Reference numeral 702 indicates a pixel extraction process.
In this pixel extraction processing 702, pixels are extracted from the binary image data in the line memory based on a template described later,
Get the value of context CX. Reference numeral 703 indicates a counting process. In this count processing 703, the number of appearances of the context CX extracted in the image extraction processing is counted,
The number of times the symbol of the decoded pixel is “0” and the number of times the symbol is “1” are counted and stored in the count value storage SRAM. FIG. 704 shows a count value storage SRAM.
Reference numeral 705 indicates a prime number conversion process. Prime number conversion processing 70
In 5, the symbol appearance probability is calculated based on each count value stored in the count value storage SRAM, converted into a product of prime numbers by the prime number conversion table, and the exponent is stored in the appearance probability storage SRAM. Also, the symbol "0",
The MPS and LPS of "1" are determined and the MPS is stored. 7
Reference numeral 06 denotes a prime number conversion table ROM. Reference numeral 707 denotes an appearance probability storage SRAM. Reference numeral 708 denotes a register calculation process. In this register calculation processing 708, multiplication processing of the appearance probability stored in the appearance probability storage SRAM and the A register representing the augend is performed. At the time of decoding, the lower bound value assuming LPS is always written in the C register. Reference numeral 709 indicates an A register. Reference numeral 710 indicates a C register. Reference numeral 711 indicates a code length calculation process. In this code length calculation processing 711, the code length table is searched based on the value of the A register, and the bit length n of the precision required to represent the value of the A register is calculated. Reference numeral 712 represents a code length table ROM. Reference numeral 713 indicates a lower bound value calculation process. In this lower bound value calculation processing 713, the value of the C register is converted into a binary decimal based on the prime number table. 71
Reference numeral 4 indicates a prime number table ROM. Reference numeral 715 indicates a code generation means. The code generation means 715 generates a reference code by dividing the lower bound value by 2 ⁻ⁿ . Reference numeral 716 represents a comparison means. This comparison means 716 compares the encoded data with the reference code, and if they match, LPS,
If they do not match, MPS is output. Reference numeral 717 indicates an output buffer. The decoded data is once stored in the output buffer and then output.

FIG. 16 shows a flow diagram of the decoder. In step 1, initialization processing is performed. In step 2, CX is read. In step 3, prime number conversion processing is performed. In step 4, the decoder augend process is performed. In step 5, code length calculation processing is performed. Step 6
Now read the encoded data. In step 7, lower bound calculation processing is performed. FIG. 17 shows a continuation of the flow diagram of the decoder. In step 8, the reference code CRE
F = C0 / 2- ⁿ is shown. In step 9, comparison processing is performed. In step 10, the decrypted data is output.
In step 11, counting processing is performed. In the conditional branch of step 12, if the decoding of the image data is completed, the process is ended, and if not, the process goes to step 2. FIG. 18 shows a flow diagram of the decoder augend process. In the conditional branch of step 1, MPS (CX) = 0
If so, go to step 2, else step 3
go to. In step 2, SYM0 processing is performed. In step 3, SYM1 processing is performed.

FIG. 19 shows the SYM0 process. In step 1, i = 1 is performed. In step 2, A (i) = A
(I) -P0 (CX, i), C (i) = A (i) -P1
(CX, i), i = i + 1 is performed. In the conditional branch of step 3, if i> PRMNUM, the process is terminated, and if not, the process proceeds to step 2. FIG. 20 shows the SYM1 process. In step 1, i = 1 is performed. In step 2, A (i) = A (i) -P0 (CX, i), C (i) = A
(I) -P1 (CX, i), i = i + 1 is performed. In the conditional branch of step 3, if i> PRMNUM, the process is terminated, and if not, the process proceeds to step 2. FIG. 21 shows the comparison process. In step 1, if CREF> C, go to step 2, otherwise go to step 3. In step 2, the decrypted data I = MPS is performed. Step 3
Then, the decrypted data I = LPS is performed.

[0022]

As described above, according to the present invention, the probability width can be accurately set in accordance with the symbol appearance probability by the addition operation as described above, so that the binary image data is arithmetically encoded / decoded with high encoding efficiency. can do.

[Brief description of drawings]

FIG. 1 is an encoder functional block diagram of an embodiment of a binary image encoding device according to the present invention.

FIG. 2 is an explanatory diagram of a template according to the embodiment of this invention.

FIG. 3 is a flow diagram of an encoder according to an embodiment of the present invention.

FIG. 4 is a flow diagram of context count processing in the embodiment of the present invention.

FIG. 5 is a flow diagram of a prime number conversion process in the embodiment of the present invention.

FIG. 6 is a flow diagram of an augend process in the example of the present invention.

FIG. 7 is a flow diagram of MPS processing in an embodiment of the present invention.

FIG. 8 is a flow diagram of LPS processing in the embodiment of the present invention.

FIG. 9 is a flow diagram of encoding processing according to the embodiment of the present invention.

FIG. 10 is a flow diagram of code length calculation processing in the embodiment of the present invention.

FIG. 11 is a flow diagram of a lower bound value calculation process in the embodiment of the present invention.

FIG. 12 is a flow diagram of initialization processing in the embodiment of the present invention.

FIG. 13 is a diagram showing a prime number conversion table in the embodiment of the present invention.

FIG. 14 is a diagram showing a code length calculation table in the embodiment of the present invention.

FIG. 15 is a functional block diagram of a decoder in the embodiment of the present invention.

FIG. 16 is a flow diagram of a decoder according to an embodiment of the present invention.

FIG. 17 is a flow diagram of a decoder according to an embodiment of the present invention.

FIG. 18 is a flow diagram of an augend process of the decoder according to the embodiment of the present invention.

FIG. 19 is a flow diagram of SYM0 processing in the embodiment of the present invention.

FIG. 20 is a flow diagram of SYM1 processing in the embodiment of the present invention.

FIG. 21 is a flow diagram of comparison processing in the example of the present invention.

FIG. 22 is an explanatory diagram of stripes in a conventional example.

FIG. 23 is a functional block diagram of a JBIG encoder in a conventional example.

FIG. 24 is a functional block diagram of a differential layer encoder in a conventional example.

FIG. 25 is a functional block diagram of a lowest resolution layer encoder in a conventional example.

FIG. 26 is an explanatory diagram of a model template in the conventional example.

FIG. 27 is a flow diagram of a JBIG encoder in a conventional example.

FIG. 28 is an explanatory diagram of an encoder register structure in a conventional example.

FIG. 29 is a diagram showing a JBIG probability estimation table in a conventional example.

FIG. 30 is a flow diagram of ENCODE processing in a conventional example.

FIG. 31 is a flow diagram of CODELPS processing in a conventional example.

FIG. 32 is a flow diagram of CODEMPS processing in a conventional example.

FIG. 33 is a flow diagram of RENORME processing in a conventional example.

FIG. 34 is a flow diagram of BYTEOUT processing in a conventional example.

FIG. 35 is a flow diagram of INITENC processing in a conventional example.

FIG. 36 is a flow diagram of FLUSH processing in a conventional example.

FIG. 37 is a flow diagram of CLEARBITS processing in the conventional example.

FIG. 38 is a flow diagram of FINALWRITES processing in the conventional example.

[Explanation of symbols]

 501, 701 Line memory 502, 702 Pixel extraction processing 503, 703 Count processing 504, 704 Count value storage SRAM 505, 705 Prime number conversion processing 506, 706 Prime number conversion table 507, 707 Appearance probability storage SRAM 508, 508 Register calculation processing 509, 709 A register 510, 710 C register 511, 711 Code length calculation processing 512, 712 Code length table ROM 513, 713 Lower bound value calculation processing 514, 714 Prime number table 515, 715 Code generation means 516, 717 Output buffer 716 Comparison means

Claims (2)

[Claims] 1. An encoding device for arithmetically encoding binary image data, comprising: a pixel to be encoded and an extraction means for extracting a pixel at a specific position around the pixel of interest to be encoded; A first storage unit that counts the number of appearances of each of white, black, and each of the bit patterns by pixels at specific peripheral positions and the sum thereof and stores the first memory in a first memory; To obtain the exponent of each prime number of the result obtained by approximating the number of appearances of the bit pattern by the pixel at the specific position and the number of appearances of white, black, and each for each bit pattern by a product using a finite number of prime numbers From the first conversion means and a sequence of prime powers of the number of appearances of white, black and each for each bit pattern, the number of appearances of the number of bit patterns by pixels at a specific position around the pixel of interest to be encoded A subtraction means for subtracting a sequence for each prime number element, a second storage means for storing the result of the subtraction means in a second memory, and a probability width as a prime power sequence by the conversion means for updating the probability width In this case, adding means for adding a prime power sequence of white, black, and appearance probability and a prime power sequence of probability width for each prime element for each bit pattern, and converting the prime power sequence into an integer by table reference means or the like. 2 conversion means, and the bit length n of the code from the sequence of prime powers stored in the probability width register by table reference or the like
2 is provided, and output means for outputting the integer value obtained by the second conversion means, and division means for making the dividend 2 ⁻ⁿ a divisor.
Value image encoding device. 2. A decoding device for arithmetically decoding binary image data, comprising: extracting means for extracting a pixel at a specific position around a pixel to be decoded; and a pixel at a specific position around a pixel of interest to be encoded. By the first storage means for counting the number of appearances of each of the white and black, each of the bit patterns, and the sum thereof in the first memory and the pixel at a specific position around the pixel of interest to be encoded by referring to a table or the like. First conversion means for obtaining a power of each prime number as a result of approximating the number of appearances of the bit pattern and the number of appearances of each of white, black, and each of the bit patterns by a product using a finite number of prime numbers; , White, black for each bit pattern, from the sequence of prime powers of the number of occurrences of each number, the sequence of prime powers of the number of bit pattern appearances by pixels at a specific position around the pixel of interest A subtraction means for calculating, a second storage means for storing the result of the subtraction means in a second memory, a probability width made into a prime power sequence by the conversion means, and a white space for each bit pattern when updating the probability width. , Black, addition means for adding a prime power sequence of the occurrence probability and a prime power sequence of the probability width for each prime element, second conversion means for converting the prime power sequence into an integer by a table reference means, etc. The bit length n of the code from the sequence of prime numbers stored in the width register by referring to a table or the like
Output means for outputting, a division means for dividing the integer value obtained by the second conversion means into a divisor, 2 ⁻ⁿ , and a comparison means for comparing the encoded data and the reference data. A binary image decoding device characterized by the above.