JP3308940B2 - Encoding method and decoding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] The present invention relates to an encoding method and a decoding method.

[0002]

2. Description of the Related Art A method in which a binary image is modeled by a Markov information source, a coded symbol is predicted according to the state of surrounding pixels, and a prediction result is arithmetically coded exhibits the best characteristics in terms of compression ratio. It has been known. QM-coder (arithmetic code decoder) adopted in JBIG (ITU recommendation T.82)
Is an example.

[0003] Such a method is based on context generation,
Estimation of symbol occurrence probability information and arithmetic coding operation are repeated for each symbol to perform coding and decoding, and efficient compression can be performed.

FIG. 16 shows a main configuration of the QM-coder.

As shown in the figure, a QM-coder includes a context generation unit 200 and a context table (RAM) 210.
, A probability estimating unit 220, and an arithmetic encoder 230, and operate as follows.

First, in the context generation unit 200,
1024 states created by the 10 surrounding pixels of the encoded pixel are detected. Each state is called a context (s), and a predicted value MPS (s) of a dominant symbol and a probability estimating unit 22 for each context.
A state number of 0 is read from the context table 210 and output to the probability estimation unit 220. Probability estimating section 220 outputs region width Qe (s) to arithmetic encoder 230 from these pieces of information. Arithmetic encoder 230 performs an arithmetic encoding operation from the encoded symbol value, predicted value MPS (s) of the superior symbol, and region width Qe (s) corresponding to the generation probability of the inferior symbol.

Next, the arithmetic code operation will be described with reference to FIG.

In arithmetic coding, a number line having an initial value of 0 to 1 is divided into an area width of a dominant symbol (MPS) and an area width of a recessive symbol (LPS). In the QM-coder, the LPS width is assigned above the number line, and the MPS width is assigned below. The width obtained by adding the two region widths is called an agent, and is hereinafter referred to as “Areg”.

FIG. 17 shows a state of area division for "0100". In the figure, A (X) represents the width of the area corresponding to the symbol sequence X. For example, the subsection A (0100) is
It corresponds to the symbol sequence “0100” and the generation probability. The encoding target symbol sequence is made to correspond to a representative point in the divided area. The representative point is set at the bottom of the partial section. The register indicating this representative point is called a code register.
Described as "Creg".

When the coded symbol and the predicted value are the same, the MPS width is selected for coding the next symbol;
PS width is selected. As described above, a representative point is provided in this area width, and the binary decimal point represents a code.

In the arithmetic coding operation, the area width is "predetermined value".
When the value is less than 2, the doubling process is repeated until the value becomes equal to or more than a predetermined value in order to prevent a decrease in precision of the decimal point (this process is called a normalization process). Here, the “predetermined value” is 1/2 of the initial value.

The normalization process is also performed when LPS is encoded. In the normalization processing, the state transition of the probability estimating unit is updated, and the value of Qe (s) differs from the next symbol, whereby a value more suitable for the probability distribution of the information source is selected.

The MPS width is large, and the LPS width Qe (s) is assigned a value smaller than the MPS width. In MPS encoding, 1
The value of the agent (Areg) after encoding the symbol is a value obtained by subtracting the LPS width Qe (s) from the agent (Areg) before encoding (that is, Areg-Qe (s)). Normalization processing is not performed until this value becomes 1/2 of the initial value.

When the MPS is continuous and the context is the same, the prediction condition of each symbol does not change.
-Computation can be performed collectively for a predetermined n symbols such as n × Qe (s). Such a collective encoding system is disclosed in Japanese Patent Publication No. Hei 7-95693 (encoding / decoding device).

[0015]

However, the above-described batch encoding method (Japanese Patent Publication No. Hei 7-95693) discloses that the batch coding is performed only when the condition of the batch processing is satisfied for a predetermined number of symbols. And speeding up is possible only under specific conditions. Actually, an image pattern that may satisfy such a condition has the same context due to the horizontal movement of the pixel arrangement, and therefore, is different from the reference pixel.
MPS is limited to all white, all black, and horizontal stripes. Since the occurrence frequency of the horizontal stripe pattern and the all-black pattern is low, it is considered that it is practically effective to encode the all-white portion in the image.

However, the whole white portion in the image is the space between characters, the space between lines, left and right margins, and the like, and the size of the whole white portion greatly changes depending on the resolution and the type of the image. Also, when the number of collective processing symbols is increased in the error diffusion image, the frequency of satisfying the collective processing condition becomes extremely low, and the effect of speeding up is hardly recognized.

The present invention has been made based on such considerations, and provides an encoding / decoding method and apparatus capable of performing high-speed processing flexibly in response to various images and local states of the images. The purpose is to do.

[0018]

SUMMARY OF THE INVENTION The present invention has been made in order to solve the above-mentioned problem, and the number of consecutively processed symbols is variable in accordance with the local situation of an image. The configuration is such that the effect of speeding up can be obtained.

That is, in the present invention, attention is paid to the fact that there is always blank space between lines in a character image, the character information portion is distinguished from the line space portion, and the number of consecutively processed symbols is set sufficiently large in the line space portion. In this case, the speed of the encoding process is greatly increased. In a document image, the proportion of white lines between lines in the entire image is considerably high. Therefore, by processing this portion at high speed, the overall processing speed can be increased.

In addition, character information (or halftone)
Is configured so that the maximum number of symbols can be selected within the range of the number of symbols predetermined for each symbol encoding by the plurality of consecutive processing symbol number determination means, and according to the local property of the image. The processing efficiency can be further improved by flexibly changing the number of consecutive processing symbols.

[0021]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS In a first embodiment of the encoding method of the present invention, if it is detected that both an encoding line and a reference line are white lines, the non-white lines are collectively encoded. The coding lines are collectively coded with a larger number of symbols than the number of symbols used for decoding.

By detecting all white lines before encoding, line spacing and character lines are distinguished, and since the line spacing is known to be entirely white, normal encoding is performed without performing. The encoding is performed collectively (continuously) on a sufficiently large number of continuous symbols to speed up the processing.

According to a second aspect of the encoding method of the present invention, in the first aspect, for the non-white line, a plurality of symbols having a value smaller than the number of symbols when collectively encoding white lines are performed. From the number of symbols, one is selected according to the local property of the image to be encoded, and encoding is performed adaptively.

For non-white lines, adaptive batch encoding corresponding to the local properties of the image is performed to further improve the processing efficiency.

Further, in the first aspect of the decoding method of the present invention, when it is detected that the reference line is a white line, the number of symbols for performing the collective decoding on the non-white line The decoding lines are collectively decoded with a larger number of symbols. This allows
Significant speed-up of the decoding process is realized.

Further, in the second aspect of the decoding method of the present invention, for the non-white line, the number of symbols having a value smaller than the number of symbols when the white line is collectively decoded is selected from the plurality of symbols. One is selected according to the local property of the image to be decoded, and decoding is performed adaptively. Even for non-white lines, adaptive batch decoding corresponding to the local property of the image is performed to further improve the processing efficiency.

In a first aspect of the encoding apparatus of the present invention, a white line detecting section for detecting that both an encoded line and a reference line are white lines, and a white line is detected by the white line detecting means. In this case, it is determined whether or not the white line can be collectively encoded with a larger number of symbols than when collectively encoding a non-white line. A symbol processing determination unit that detects the number of symbols that can actually be collectively encoded among a plurality of predetermined symbol numbers having a smaller value than when performing the collective encoding on the white line, and detects When the second plurality of symbol processing determination units that select and output the largest one of the determined symbol numbers and the first plurality of symbol processing determination units determine that batch processing is possible. Selects the number of symbols for batch processing of white lines, and when the first multiple-symbol processing determination unit determines that batch processing is not possible or when encoding a non-white line, the second symbol And a coding unit for performing predictive coding with the number of symbols selected by the batch processing symbol number selection unit. Configuration.

When a white line is detected, it is determined whether batch processing is possible. Then, a batch processing dedicated to white lines is executed. , An adaptive batch process corresponding to the above is executed, thereby achieving extremely efficient encoding.

According to a second aspect of the encoding apparatus of the present invention, in the first aspect, the detection processing by the white line detection means and the encoding processing by the encoding unit are executed in parallel.

By performing the white line detection process independently of the encoding process (performed as a pre-process), a situation where the speed of the encoding process is reduced due to the white line detection does not occur.

Further, in the decoding apparatus of the present invention, similar to the encoding apparatus, the processing efficiency is improved by performing the batch processing dedicated to the white line or the adaptive processing for the non-white line, and the detection processing of the white line is performed. , Is performed independently of the encoding process to prevent delay in the encoding process.

The encoding / decoding device of the present invention is capable of high-speed processing, and is suitable for mounting on a communication device such as a multifunction facsimile machine that needs to read and compress a document at high speed. It contributes to functionalization.

Hereinafter, embodiments of the present invention will be specifically described with reference to the drawings.

FIG. 1A shows an image codec (arithmetic code decoder for binary image) according to an embodiment of the present invention.
FIG. 3 is a block diagram showing the configuration of FIG.

As shown, the image codec 102
The image input / output interface 1000 and the line memory 20
00, an arithmetic code decoding unit 3000, and a sequence control unit 4000 that controls the operation of each unit as a whole.

The image input / output interface 1000 outputs a read / write (R / W) control signal to the image memory 104, and stores the image data in the line memory 2000 at the time of encoding. On the other hand, at the time of decoding, the decoded data is transferred to the image memory 104.

The image input / output interface 1000
Is a data buffer 1100 and a white line detecting unit 11 for detecting that all image data for one line is white data.
10, and a header information creation unit 1500 that creates header information indicating that a white line is detected and adds the header information to the image data.

FIG. 1B shows a data format in which header information is added to one line of image data. That is, header information 1111 indicating whether or not the image data 1112 for one line is all white is added. Such data is sent from the image input / output interface 1000 to the line memory 2000.

The line memory 2000 has a sufficient capacity required for the encoding / decoding processing.

A sequence control unit 4000 for controlling the overall operation of the system reads the header information added to the image data stored in the line memory 2000, and reads a predetermined line (specifically, from the header information). If it is found that all data of two reference lines and one line to be encoded (total three lines) are white data (that is, all white lines: inter-line portions), the white line identification signal is arithmetically decoded. It sends it to the unit 3000 to notify it.

When the white line identification signal indicates that both the reference line and the line to be encoded are all white, the arithmetic code decoding unit 3000 collectively encodes a large number of symbols (special code for encoding a white line). Processing) to realize high-speed encoding. This makes it possible to process a white line between lines in a character image at extremely high speed. The white line detection at the time of decoding is performed inside the arithmetic code decoding unit 3000, as described later.

The detection of a white line in the image input / output interface 1000 and the processing in the arithmetic code decoder 3000 are executed in parallel. The detection of a white line by the image input / output interface 1000 is performed by the arithmetic code decoding unit 3000.
This is because if it is performed, the speed of the code decoding process is reduced. Therefore, a configuration is adopted in which information on the white line is acquired in advance before being input to the arithmetic code decoding unit 3000.

As described above, the arithmetic code decoding unit 3000 distinguishes an all white line (that is, an area between lines between characters) from a character area (including a halftone image area),
Special processing is performed for all white lines.

Further, the character area is adaptively coded (encoded) while appropriately changing the number of symbols to be collectively processed according to the local properties of the image. In this way, high-speed arithmetic coding (decoding) adapted to the input image is realized.

That is, when encoding a binary image as shown in FIG. 2, the number of symbols to be collectively processed in the space between lines (areas B and D) is greatly increased, and encoding is performed at high speed.
Character or halftone image part (areas A, C, E, F)
Then, adaptive encoding is executed while appropriately changing the number of symbols to be collectively processed according to each local property.

That is, in the present embodiment, the number of symbols to be collectively processed is determined according to the flow as shown in FIG. That is, first, it is determined whether or not the area is a white line (between lines) (step 12).
It is determined whether batch processing for 256 symbols predetermined for white line processing is possible (batch processing is not possible if normalization processing occurs) (step 14).
If it is determined that batch processing is possible, 256 symbols will be encoded at once.

On the other hand, if it is not a white line, or
If it is determined that batch processing of 256 symbols is not possible,
The number of symbols to be collectively processed is adaptively determined by a collectively processed symbol number determination circuit (described later) incorporated in arithmetic code decoding section 3000 (step 16). In this case, one of the symbol numbers “2”, “4”, “8”, and “16” is selected.

The image codec shown in FIG.
The configuration of each unit of 102 will be specifically described.

FIG. 4 is a block diagram showing the configuration of the image input / output interface 1000.

As shown, the image input / output interface 1000 includes an address control unit 1102, 1104, a timing control unit 1106, 1108, a data buffer 1100, a white line detection unit 1110, and a header information creation unit 1500. Having.

The white line detector 1110 is provided with a comparator 1200
, A counter 1300, a white line determination circuit 1400, and a header information creation unit 1500. That is, every time one line of data such as 16 bits is read, the white line is detected by comparing it with zero (white pixel value) by the comparator 1200, counting the number of times by the counter 1300, and determining the value in advance. The white line determination circuit 1400 determines whether or not the number of words is equal to the number of words in one line.

If it is determined that the line is a white line, the header information creating unit 1500 adds a bit indicating this to the header and writes the bit in a predetermined area on the line memory 2000.

FIG. 5 is a block diagram showing a configuration of arithmetic code decoding section 3000.

As shown, the arithmetic code decoding unit 3000
Has a context generator 3200, a multiple symbol processing determiner 3300, a context memory 3400, a white line detection circuit 3100, a probability estimator 3600, and an arithmetic encoder 3500.

The image data read from the line memory 2000 is input to the context generator 3200, and the index is determined by the value of the reference pixel having a predetermined arrangement.
Output (s). The context generator 3200 further outputs peripheral pixel data of the encoded symbol to the multiple symbol processing determiner 3300. Context memory
The 3400 is configured with 1024 bytes of RAM. In this context memory 3400, one byte is allocated to one context, and in each byte, the predicted value MPS (s) of the coded symbol represented by one bit and the state number 7 bits of the probability estimator 3600 are stored. Have been.

The probability estimator 3600 is a state transition table composed of a ROM. Probability estimator 3600 outputs the region width Qe (s) of the LPS to the arithmetic encoder.

Arithmetic encoder 3500 is used for encoding symbols, MPS
Using (s), Qe (s) and the number of consecutively processed symbols, which is the output signal of continuous symbol processing decision unit 3300, a plurality of symbols are collectively arithmetically encoded and a code data sequence is output.

The multi-symbol processing decision unit 3300 calculates the peripheral pixel data of the encoded symbol, the A register value Ar of the arithmetic encoder,
Using eg and Qe (s), the maximum value of the number of symbols that can be continuously processed within a predetermined range from the symbol is calculated. In the present embodiment, the maximum value is selected from “2 symbols”, “4 symbols”, “8 symbols”, “16 symbols”, and “256 symbols” (described later).

The white line detection circuit 3100 detects that the line restored at the time of decoding is a white line, adds the information to the header, and stores the data in the line memory 2000.
Write to The configuration of the white line detection circuit 3100 is the same as that of the white line detection unit 1110 in the image input / output interface 1000 shown in FIG.
Each time one word is restored, whether or not it is white data is counted. FIG. 6 shows the context generator 32.
It is a block diagram which shows the structure of 00.

As shown, the context generator 32
00 denotes three shift registers 3201 to 3203, an index generator 3204, and a timing control circuit 32 for controlling the whole.
It consists of 05.

The shift register is composed of 4 bytes. The shift register 3201 is for encoding / decoding lines, and the shift registers 3202 and 3203 are for reference lines. At the time of encoding, image data is read from the line memory 2000 and sequentially input to the least significant byte of the shift register. The bit position of the shift register is c-7 as shown.
It will be identified by symbols c23, b-7 to b23, and a-7 to a23.

First, the operation at the time of encoding will be described.

In the initial state, all registers are cleared.
Image data is read from the line memory and sequentially input to the least significant byte. Then, the first line to be encoded
The pixel is shifted to the left until the pixel is at the position of a0, and the lower byte is read from the memory and 3 bytes of image data are packed. Similarly, the first line of the reference line is located at b0 and c0.

At this time, a0 is a coded symbol (indicated by? In the figure), and a-2, a-1, b-2, b-1, b0, b1,.
The ten pixels at positions b2, c-1, and c0 are reference pixels. The above parts are shown by thick lines in FIG.

The index generator 3204 converts the reference pixel into a-
2, a-1, b-2, b-1, b0, b1, b2, c-1, c0. This 10-bit data becomes the index “s” for identifying the context. After the encoding of the encoded symbol "?", In the case of sequential processing, the entire shift register is shifted left by one bit to create a new context (FIG. 10).

At the time of decoding, the decoded symbol is written at the position of a0. In the sequential processing for each symbol, the shift register is shifted one bit to the left each time one symbol is decoded. The decoded data is written to the memory every 8 bits.

This data is stored in the shift registers a-7 to a-1.
Byte data. The overall operation timing such as input / output of image data and bit shift is controlled by the timing control circuit 32.
Controlled by 05.

Image data 3206 is output to multi-symbol processing determiner 3300 to determine whether the same context and MPS are continuous. The output image data is a-2 to a15, b-2 to b17, and c-1 to c16. FIG.
35 is a block diagram illustrating a configuration of a multiple symbol processing determiner 3300. FIG.

In this embodiment, only contexts in which the reference pixels are all white are subjected to continuous processing. As shown in the figure, the multiple-symbol processing determination unit 3300 includes a first consecutively processed symbol number determination unit 3340 for determining the number of collectively processed symbols in a character (or halftone) portion.
And a second consecutively processed symbol number determination unit 3310 (and a determination circuit 3320) for determining whether or not batch processing of 256 symbols for a white line (line-to-line) portion is possible.

That is, for the character line, the number of consecutively processed symbols is determined by the first continuously processed symbol number determination unit 3340. For the white line (between lines), the second continuous symbol number determination unit 3310 and the determination circuit 3320 determine whether or not continuous processing of a predetermined number of symbols is possible. The second consecutive processing symbol number determination unit 3310 includes an 8-bit shifter
3311, a subtractor 3312, and comparators 3313 and 3314.

In the second continuous processing symbol number determination section 3310, the white line (the fact that the coding line and the reference line are white pixels is already known by the operation of the image input / output interface 1000 in FIG. Continuity has already been detected), the following equations (1) and (2) determine whether or not batch processing of 256 symbols is possible.
Are determined at the same time. Areg 256 * Qe (s)> = 0x8000 (1) Coded symbol = MPS (s) ... (2) Note that 0x8000 in equation (1) is the initial value of Areg 0x100
It is 1/2 of 00 (hexadecimal notation) (see FIG. 9). Areg 256 * Q
If e (s) is smaller than this value, a normalization process is required. Therefore, it is necessary to satisfy Expression (1) to avoid the occurrence of the normalization process. Equation (2) means that the continuity of the MPS (that is, the predicted value) is also a condition for the batch processing.

The second continuous processing symbol number determination section 3310
The bit shifter 3311 calculates 256 * Qe (s), and subtracts
Calculates Areg 256 * Qe (s). And the comparator 331
At 3, it is determined whether the output value of the subtractor 3312 is 0x8000 or more.

Since it is known that the value of the encoded symbol is zero (the white pixel value is zero), the condition (2) can be determined by looking at MPS (s). The determination circuit 3320 performs these determinations.

A "judgment enable signal" is input as a control signal to the judging circuit 3320. If this signal is in the ON state, the judging circuit 3320 functions. When the number of pixels at the line end is less than 256, the determination enable signal is turned off. The determination enable signal is output from the sequence control unit 4000 in FIG. 1 (not shown). Also, at the time of decoding, whether or not batch processing of 256 symbols is possible is determined by whether or not the following equations (3) and (4) are simultaneously satisfied. Areg 256 * Qe (s)> = 0x8000 (3) Creg <Areg 256 * Qe (s) ... (4) Since the reference line is white, the continuity of the context has been detected. The condition of Expression (3) is determined in the same manner as in encoding. The condition of equation (4) is 256 * Qe (s) with 8-bit shifter 3311.
Is calculated, Areg 256 * Qe (s) is calculated by the subtractor 3312, and the output of the subtractor 3312 is calculated by the comparator 3314 as the value of the C register (Cr
eg) Determine if greater than.

If it is determined that 256 symbols can be collectively processed for a white line (inter-line portion), a determination circuit
The batch processing enable signal S1 for the white line output from the 3320 becomes active.

The selection circuit 3330 has the number of symbols (2, 4, 4) output from the first consecutively processed symbol number determination section 3340.
8 or 16) and a white line symbol 256 are input in parallel.

When the collective processing enable signal S1 for the white line is active, "256" is adopted as the collective processing symbol number, otherwise, the first consecutive processing symbol number determination unit 3340 The number of symbols to be output (any one of 2, 4, 8, and 16) is adopted. In this way, adaptive batch encoding / decoding processing as shown in FIG. 3 is realized.

Next, a specific configuration of the first determination unit 3340 for determining the number of collectively processed symbols on a character line will be described. FIG. 8 is a block diagram showing a configuration of the first continuously processed symbol number determination section 3340.

In the present embodiment, the candidates for a plurality of symbols that can be continuously processed are 2, 4, 8, and 16 symbols, and it is simultaneously determined whether or not batch processing (continuous processing) is possible for each number of symbols. , The number of symbols determined to be batch-processable is determined at the same time, and the maximum value is selected therefrom.

As shown in the figure, the first consecutive processing symbol number determination unit 3340 includes 1-bit shifters 3341 to 4 bit shifters 3344, subtractors 3345 to 3348, comparators 3349 to 3356,
Continuous processing symbol number judgment circuit 3357 and context / MP
S continuation determination circuit 3358 to 16 continuation determination circuit 3361 of S.

The shifters 3341 to 3344, the subtracters 3345 to 3348, and the comparators 3349 to 3356 have the same configuration as the second continuous processing determination circuit 3310 (FIG. 7) for the white line. In the first continuous processing symbol number determination circuit 3340, context / MPS determination circuits 3358 to 3361 are provided, and the continuity of the context (reference pixel) is determined at any time. In the case of the second consecutively processed symbol number determination circuit 3310, FIG.
White continuous (that is,
This is because the continuity of the context has already been determined, but the continuity of the context needs to be determined from time to time as there is no information previously obtained for the character line.

Hereinafter, a case will be described in which it is determined whether batch processing of 16 symbols is possible. The same applies to the case of batch processing determination for each of 2, 4, and 8 symbols.

The 4-bit shifter 3341, the subtractor 3342, and the comparator 3
343, comparator 3344, context / MPS 16 continuous judgment circuit 3
At 345, determination information as to whether or not continuous processing of 16 symbols is possible is generated and input to the continuous processing symbol number determination circuit 3357.

That is, when performing a batch (continuous) encoding process, the context (state of the reference pixel) is a predetermined pattern (for example, a state where all the pixels are white). And that the dominant symbol value (MPS) for the coded symbol is a predetermined pattern (that is, continuous). The reason for determining the continuity of MPS is that even if the reference pixels are the same, the MPS changes depending on the value of the pixel to be encoded, and in this case, batch processing cannot be performed.

The image data stored in the context generator 3200 described with reference to FIG. 6 is output to the first consecutive processing symbol number determination section 3340 to determine whether the same context and the MPS are continuous. . Here, the output image data is a-2 to a15, b-2 to b17, and c-1 to c16 in FIG.
Is the data at each bit position.

A detector corresponding to batch processing of 16 symbols includes a 4-bit shifter 3344, a subtractor 3348, a comparator 3355, a comparator 3356, and a 16-continuation determination circuit 3361 of context / MPS.
And

The 4-bit shifter 3344, subtractor 3348, comparator 3
355 and the comparator 3356 constitute a part for acquiring determination information for determining whether or not normalization processing is required when performing collective encoding processing. The comparator 3356 is used at the time of decoding. In addition, context / MPS 1
The six continuation determination circuit 3361 is a part that detects continuation of a predetermined pattern.

The 4-bit shifter 3344 has a region width Qe (s) of the LPS.
Is shifted 4 bits to the left and multiplied by 16. 16 * Qe shifter output
(s). The subtractor 3348 calculates Areg 16 * Qe (s). The comparator 3355 compares the value with 0x8000. 0x8000
Is 1/2 of the initial value of Areg 0x10000.

The output of the comparator 3355 is Areg 16 * Qe (s)> =
If it is 0x8000, it is "1", otherwise it is "0".
Here, if Areg 16 * Qe (s)> = 0x8000, normalization processing does not occur, and one of the conditions for continuous processing is satisfied. For example, in FIG. 9, the initial value Qe (s) of Areg
Is subtracted 16 times consecutively, the value of the agent is 0x80
When the value exceeds 00 (state P1 in FIG. 9), it is determined that batch processing is possible, and when the value is less than 0x8000 (state P1 in FIG. 9).
In 2), it is determined that batch processing is not possible.

On the other hand, the context / MPS 16 continuous judgment circuit
3361 refers to the image data and
It is determined whether S (s) is continuous 16 times. The image data referred to for this purpose is a-2 to a15, b-2 to b17, and c- in FIG.
Image data at each position of 1 to c16.

In this embodiment, these pixels are all “white”.
Alternatively, all are determined to be “black”. Since encoding of MPS is assumed, it is also a determination condition that MPS (s) matches the pixel value. Continuity of context means that
As shown in the figure, even if it is shifted right by one pixel,
This means that no change occurs in the reference pixel (X). Also MP
The fact that S (s) is continuous means that no change occurs even when the predicted value (?) Is also shifted right by one pixel as shown in FIG.

When all the judgment conditions are satisfied, the output signal of the context / MPS 16 continuation judgment circuit 3361 becomes "1",
Otherwise, it is "0". Output signal of comparator 3355 is "1"
And the context / MPS 16 continuation determination circuit 3361
Is "1", the number of consecutively processed symbols determination circuit 335
7 determines that continuous processing of 16 symbols is possible.

The same applies to the determination of continuous processing of 8, 4, and 2 symbols. The determination of these different symbol numbers is performed simultaneously (in parallel).

The continuous processing symbol number determination circuit 3357 selects the maximum value of the number of symbols that can be continuously processed from the four determination results. A logic circuit for performing such selection can be easily realized by a combination of input signals. The number of consecutive processing symbols selected is determined by the arithmetic encoder 3500 and the context generator.
Output to 3200.

FIG. 11 summarizes the adaptive variable processing of the number of symbols to be collectively processed as described above.

That is, first, it is determined whether or not the Qe is subtracted from the median (0x8000) or more when the Qe is subtracted in a lump (step 10). If yes, then context / M
The continuity of PS is determined (step 20), and if there is continuity, batch processing is performed (step 30). Meanwhile, step
If the answer is No in 10 or 20, sequential processing (processing for each symbol) is performed (step 40).

Next, the arithmetic encoder 3500 will be described.
FIG. 12 is a block diagram showing a configuration of the arithmetic encoder 3500.

As shown in the figure, the arithmetic decoder 3500 includes a sequence control section 3501 for controlling the operation in general, an A register 3502, a C register 3508, a shifter 3506, a Qe register 3507, an ALU 3503, A shifter 3504 and a serial / parallel converter 3505 are provided.

The arithmetic coding operation can be executed by a combination of addition, subtraction, and shift operation. Coded symbols and MPS (s)
Is input to the sequence control unit 3501, where it is determined whether the coded symbol matches MPS (s). If they match, encoding of the MPS symbol is performed; otherwise, encoding of the LPS symbol is performed.

FIG. 13 shows the procedure for encoding MPS (s). That is, in MPS encoding, the value A of the A register 3502
Let reg be Areg = Areg Qe (s) (step 300) and Areg
If> = 0x8000 (step 310), the process ends. Otherwise, compare Areg with Qe (s) (step 3
20) If Areg <Qe (s), then A = Qe (s), Creg = Creg
+ Areg (step 330).

Then, Areg> = 0x80 by normalization processing
The left shift is performed until it becomes 00 (step 340). At this time, the C register (Creg) 3508 in FIG. 12 also shifts to the left by the same number of bits. These operations can be executed by an ALU (arithmetic logic operation circuit) 3503 and a shifter 3504.

At this time, the bit data overflowing to the left is converted from the C register (Creg) 3508 to the serial / parallel converter 3505.
The code data bytes are converted into code data bytes. In step 310 of FIG. 13, if "No", no code is generated, and the code is output only when steps 320, 330, and 340 are executed. LPS encoding can also be performed by a combination of arithmetic and logical operations similar to MPS.

As shown in FIG. 12, the number of consecutive symbols is input to shifter 3506, which becomes the number of shift bits. Similarly, Qe (s) is input to shifter 3506 as data, and a value obtained by performing a left shift by the number of symbols is input to Qe register 3507. The encoding operation has been described above by replacing Qe (s) with the value of the Qe register in the above description. Next, decoding will be described. However, description common to encoding will be omitted.

FIG. 14 is a symbol decoding flow in the case of sequential processing. The batch decoding condition of the MPS will be described with reference to FIG.

In this flow, MPS (s) is always decoded when Creg <Areg is compared (step 410), and when Areg <0x8000 (step 420), no. In other cases, in the processing routine (not shown) of Cond_MPS_exchage (Step 430) or Cond_LPS_exchage (Step 450), the decoded symbol D becomes either MPS (s) or 1 MPS (s).

Assuming that the number of symbols to be decoded continuously is 16, the condition for passing the route where D = MPS (s) 16 times is as follows. Creg <Areg 16 * Qe (s) and Areg 16 * Qe (s) <0x8000 ... (5) If the context is the same for 16 symbols and the above condition is satisfied, 16 symbols can be restored as MPS (s) . This can be performed by performing a 16-bit left shift with MPS (s) set at the position of a0 in the shift register in FIG.

In FIG. 12, decoding of a symbol is performed by inputting 1-byte data from an external code memory (not shown) to a C register 3508 and comparing it with the value of an A register 3502. Although the details of the calculation are omitted, the restored symbol is sent from the sequence generator 3501 to the context generator 32.
Output to 00. The operation of determining the number of consecutively processed symbols in FIG. 8 is almost the same as that at the time of encoding. This determination is made by comparing Creg with Areg 16 * Qe (s) by the comparator 3356.

The determination of 2 symbols, 4 symbols, and 8 symbols is performed at the same time as in the case of 16 symbols, and at the same time at the time of encoding. The maximum number of symbols to be processed is selected by the continuous processing symbol number determination circuit 3357 based on these determination results and output to the arithmetic encoder.

As described above, for a character line, the maximum value of symbols that can be continuously processed within a predetermined range during encoding and decoding can be selected. Therefore, high-speed processing can be performed in accordance with changes in the image pattern and the resolution. In addition, since the number of consecutive symbols is assigned to each of the plurality of detectors and detected in parallel, and a maximum value is selected from each output, a hardware method is adopted.
There is also an advantage that high-speed processing is easily realized.

In the present embodiment, “no normalization processing” is one of the conditions for performing the batch processing, but this is not necessarily a condition. As described above, since the normalization process complicates the calculation, it is desirable to perform the batch process within a range where the normalization process does not occur.

By the way, when batch processing is performed even if normalization processing occurs, the following processing is performed.

As described above, in the batch processing, the value of Areg is changed to Areg−n * Qe (s) for the context (s).
And n symbols are calculated together. Here, when normalization occurs during encoding and decoding of n symbols, the value of Qe (s) is updated by a predetermined state transition of the probability estimator, and becomes Qe ′ (s). In such a case, Areg-
It cannot be simply calculated as n * Qe (s).

Therefore, in this case, the number of symbols until normalization occurs is calculated using Areg, Qe (s), 0x8000, and when it is set to n1, Areg is calculated as follows. Will be. Areg− {n1 * Qe (s) + (n−n1) * Qe ′ (s)} In this case, if n1 and (n−n1) are powers of 2, calculation is easy, but generally, Otherwise, a multiplier is needed instead of the shifter. Therefore, if there is room in the device configuration, the present invention can be applied to perform batch processing (continuous processing) even in such a case.

FIG. 15 relates to the above two embodiments.
FIG. 3 is a block diagram illustrating a hardware configuration of a facsimile apparatus equipped with a QM encoding / decoding circuit.

As shown, the facsimile apparatus includes a host processor 102, an MH / MR / MMR encoding / decoding circuit 103, an image processing circuit 104 for performing processing such as resolution conversion and enlargement / reduction, and a QM Encoding / decoding circuit 105
, An image line memory 106, a code memory 107, and a communication interface such as a modem (which functions as an interface for wired transmission using the telephone line 113 or the like) 108
, An image input device 111 such as a scanner, and an image recording / display device 112 such as a printer. Each block can exchange information with each other via internal buses 109 and 110. The above-described circuit configuration of the present invention is mounted on the QM encoding / decoding circuit 105.

By applying the present invention, high-speed arithmetic coding / decoding can be realized flexibly by adapting to the type of image, and in this respect, the function of the facsimile apparatus (communication apparatus) can be enhanced. In particular, in a facsimile multifunction peripheral or the like, it is necessary to compress a document at a high speed, and it is necessary for the speed of the compression process to follow the reading speed, and the effect of applying the present invention is great.

In the above description, the blank portion is described as “white line (or all white)”, but the same applies to “black line (all black)”. In addition, the technical idea of distinguishing line spacing from character lines and performing unique processing (adaptive processing) in each part is not only applied to arithmetic code decoding, but is modified and applied to other code decoding. Can be applied.

[0118]

As described above, in the present invention, character lines and white lines between lines are identified, and the white lines are collectively processed with a sufficiently large number of symbols as compared to the character lines, so that encoding / decoding is greatly improved. Can be faster.
The white line adaptive processing can speed up the image by about 20% for an image with many lines. For character lines, by selecting the maximum number of symbols within a predetermined range, batch processing adapted to the local state of the image can be performed.
By these synergistic effects, a flexible and high-speed adaptive encoding / decoding process, which has not been achieved in the past, is realized.

[Brief description of the drawings]

FIG. 1A is a block diagram illustrating an entire configuration of an image codec according to the present invention. FIG. 1B is a diagram illustrating a data format in which header information is added to one line of image data.

FIG. 2 is a diagram showing an example of an image to be encoded.

FIG. 3 is a flowchart showing a characteristic operation procedure in the image codec of FIG. 1;

FIG. 4 is a block diagram showing a specific configuration of an image input / output interface;

FIG. 5 is a block diagram showing a specific configuration of an arithmetic code decoder.

FIG. 6 is a block diagram showing a configuration of a context generator.

FIG. 7 is a block diagram showing a configuration of a multi-symbol processing determination unit.

FIG. 8 is a block diagram showing a configuration of a first continuously processed symbol number determination unit.

FIG. 9 is a diagram for explaining conditions for batch arithmetic coding;

FIG. 10 is a diagram for explaining a state in which a context and MPS are continuous.

FIG. 11 is a flowchart showing a procedure of an encoding process for a character line;

FIG. 12 is a block diagram illustrating a configuration of an arithmetic encoder.

FIG. 13 is a flowchart showing the procedure of MPS processing (symbol sequential processing) of the QM-coder.

FIG. 14 is a flowchart showing the procedure of symbol decoding processing (symbol sequential processing) of the QM-coder.

FIG. 15 is a block diagram showing a configuration of a facsimile device equipped with the encoding / decoding device of the present invention.

FIG. 16 is a block diagram showing a basic configuration of a QM coder.

FIG. 17 is a diagram for explaining the concept of arithmetic coding;

[Explanation of symbols]

 104 Image memory 102 Image codec 1000 Image input / output interface 1100 Data buffer 1110 White line detection unit 1111 Header information 1112 One line image data 1500 Header information creation unit 2000 Line memory 3000 Arithmetic code decoding unit 4000 Sequence control unit

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) H04N 1/41-1/419

Claims (10)

(57) [Claims] In an encoding method for predicting an encoded symbol based on a value of a reference pixel around the encoded symbol and encoding the prediction result, it is detected that both the encoded line and the reference line are white lines. In this case, the coding line is collectively coded with a larger number of symbols than the number of symbols used when performing collective decoding of non-white lines. 2. The method according to claim 1, wherein the non-white line is selected from a plurality of symbols having a value smaller than the number of symbols when collective encoding of white lines is performed, according to a local property of an image to be encoded. 2. The encoding method according to claim 1, wherein one of them is selected and encoding is performed adaptively. 3. A decoding method for predicting a decoded symbol based on a value of a reference pixel around the decoded symbol and decoding a result of the prediction, when it is detected that the reference line is a white line, A decoding method, wherein the decoding lines are collectively decoded with a larger number of symbols than when collectively decoding non-white lines. 4. A non-white line is selected from a plurality of symbols having a value smaller than the number of symbols when performing white line batch decoding according to the local property of an image to be decoded. 4. The decoding method according to claim 3, wherein one is selected and decoding is performed adaptively. 5. An encoding apparatus for predicting an encoded symbol based on a value of a reference pixel around the encoded symbol and encoding the prediction result, detects that both the encoded line and the reference line are white lines. When a white line is detected by the white line detection unit and the white line detection unit, the white lines are collectively collected with a larger number of symbols than the number of symbols when collectively encoding non-white lines. A first plurality of symbol processing determination unit that determines whether encoding is possible or not; and a predetermined number of symbols having a smaller value than when collective encoding is performed on the white line. , Detect the number of symbols that can be collectively encoded,
A second plural-symbol processing determination unit that selects and outputs the largest one of the detected number of symbols; and if the first multiple-symbol processing determination unit determines that batch processing is possible, The number of symbols for batch processing of white lines is selected, and when the first multiple symbol processing determination unit determines that batch processing is not possible or in the case of non-white line encoding, the second plurality of symbols are selected. A batch processing symbol number selection unit that selects the number of symbols output from the symbol processing determination unit; and an encoding unit that performs predictive encoding using the symbol number selected by the batch processing symbol number selection unit. An encoding device characterized by the above-mentioned. 6. The encoding apparatus according to claim 5, wherein the detection processing by the white line detection unit and the encoding processing by the encoding unit are performed in parallel. 7. A decoding apparatus for predicting a decoded symbol based on a value of a reference pixel around the decoded symbol and encoding the prediction result, comprising: a white line detecting unit for detecting that a reference line is a white line; When a white line is detected by the white line detection means, the white line can be collectively decoded with a larger number of symbols than the number of symbols when collectively decoding non-white lines. A first plural-symbol processing determination unit that determines whether or not it is possible; and, among the predetermined number of symbols having a smaller value than when performing the collective decoding for the white line, the collective decoding is performed. Detect the number of symbols that are actually possible,
A second plural-symbol processing determination unit that selects and outputs the largest one of the detected number of symbols; and if the first multiple-symbol processing determination unit determines that batch processing is possible, The number of symbols for batch processing of white lines is selected, and when the first multiple symbol processing determination unit determines that batch processing is not possible or in the case of non-white line encoding, the second plurality of symbols are selected. A batch processing symbol number selection unit for selecting the number of symbols output from the symbol processing determination unit; and a decoding unit for performing predictive decoding with the number of symbols selected by the batch processing symbol number selection unit. A decoding device characterized by the above-mentioned. 8. The decoding apparatus according to claim 7, wherein the detection processing by the white line detection unit and the encoding processing by the decoding unit are performed in parallel. 9. A communication device comprising the encoding device according to claim 5 or 6. 10. A communication device comprising the decoding device according to claim 7.