Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
1999-11-09
2001-07-24
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
Reexamination Certificate
active
06265997
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an arithmetic-encoding device and an arithmetic decoding device for compressing and decompressing image information.
2. Discussion of the Background
In recent years, a size of image information processed in an image processing apparatus, such as a digital photocopier and a facsimile machine, has increased as an image resolution and quantity of information per pixel have increased. Accordingly, to process such a large quantity of image information, an increase in the operational speed of the image processing has become important. Further, reducing a transmission time of image information among plural image processing apparatuses has also become important. Thus, a technique for effectively compressing image information, and thereby reducing the transmission time of the image information, is attracting attention.
As image information compression methods for a facsimile transmission system, the Modified Huffman (MH) coding method, the Modified READ (MR) coding method and the Modified MR (MMR) coding method are commonly used. Any of these coding methods achieve a high data compression ratio for a text image and a line image. However, these methods achieve a low data compression ratio for a graphic image, such as a continuous-toned photographic image or a half-toned photographic image processed by a dither-processing method. On the other hand, an arithmetic coding method as a representative example of entropy coding methods is known as an effective data compression method for both a text image and a graphic image.
A known example of the arithmetic coding methods is a QM-coder method, which is standardized as ISO/IEC 11544 by the Telecommunication Standardization Sector of the International Telecommunication Union (ITU-T) and the International Standard Organization (ISO). The QM-coder method generally achieves a high data compression ratio, which is almost close to a limitation that is theoretically obtained, for both a text image and a graphic image. In the arithmetic coding method, a probable symbol, which is a less probable symbol (LPS) or a more probable symbol (MPS), for each of target pixels included in image information is predicted. Further, an occurrence probability of the probable symbol is predicted. Then, the target pixel is encoded according to the symbol information and the occurrence probability information. Therefore, an overall data compression ratio of the image information is high when each hit rate of the prediction for all of the target pixels in the image information is high.
FIG. 1
is a block diagram illustrating a structure of a background QM-coder
20
. In
FIG. 1
, the QM-coder
20
includes a template
21
, a probability estimator
22
and an arithmetic encoder
23
. The template
21
receives image information (denoted as IMAGE INFORMATION) and successively generates reference pixel information (denoted as REFERENCE PIXEL INFORMATION) and target pixel information (denoted as TARGET PIXEL INFORMATION) with respect to each of the target pixels in the image information.
The probability estimator
22
generates symbol information (denoted as SYMBOL INFORMATION), which is a less probable symbol (LPS) or a more probable symbol (MPS). The probability estimator
22
also generates an estimated occurrence probability of the probable symbol (denoted as ESTIMATED OCCURRENCE PROBABILITY). The symbol information and the estimated occurrence probability are generated according to the target pixel information, the reference pixel information and renewing information for an estimating occurrence probability of the probable symbol (denoted as RENEWING INFORMATION FOR PROBABILITY), which is feedback information sent from the arithmetic encoder
23
as described below.
The arithmetic encoder
23
generates encoded information (denoted as ENCODED INFORMATION) according to the symbol information and the estimated occurrence probability and outputs the encoded information to, for example, a transmission line in a facsimile network system. The arithmetic encoder
23
also generates the renewing information for estimating occurrence probability of a probable symbol and sends the renewing information to the probability estimator
22
to estimate and enhance occurrence probabilities of probable symbols for subsequent target pixels to be encoded.
As described above, the symbol information and the occurrence probability are estimated and then renewed by the probability estimator
22
according to the feedback renewing information so that the occurrence probability of a probable symbol is generally enhanced in proportion to the encoded number of target pixels. As an example, Japanese Laid-open Patent Publication No. 1-222576 describes an arithmetic-encoding method where an occurrence probability of a less probable symbol (LPS) of a picture signal is approximated by a sum of 2's power to enhance the occurrence probability of the probable symbol.
In general, the arithmetic coding method achieves a high data compression ratio, but requires a relatively long processing time to encode and decode image information. For example, the QM-coder method generally achieves a higher data compression ratio than the MH method, which is as an example of a run-length data compression method, However, the QM-coder method requires more operational time to encode and decode image information than the MH method. Consequently, in a facsimile transmission system, for example, an overall operational time to encode image information, transmit the encoded data and decode the encoded data by the MH method is generally shorter than that required by the QM-coder method. Therefore, despite a high data compression ratio of the QM-coder method, the QM-coder method cannot always take full advantage of the compression ratio in an image information system, such as a facsimile network system.
As described above, in the QM-coder method, a target pixel is estimated as either a less probable symbol (LPS) or a more probable symbol (MPS) and an occurrence probability is estimated. Then, the target pixel is encoded according to the estimated probable symbol and the estimated occurrence probability. During the above estimation process, occurrence probabilities of the probable symbols are adaptively renewed as necessary based on a statistic operation according to the feedback signal (denoted as RENEWING INFORMATION FOR PROBABILITY in FIG.
1
), to enhance the estimated occurrence probabilities of probable symbols for subsequent target pixels to be encoded. That is, the subsequent target pixels are encoded only after the feedback signal is input to the probability estimator
22
. In other words, unless an encoding process for a previous target pixel has been completed, a probability estimation process for a following target pixel cannot be started. Therefore, the operational time for encoding requires a relatively long time.
In addition, because the encoding operation of the QM-coder requires the above-described feedback operation, a so-called “pipeline processing circuit,” in which data is input to an input terminal and advanced through a plurality of processing units toward an output terminal in one direction, cannot be applied to an encoding operation of the QM-coder. Therefore, further accelerating of the encoding operation is difficult.
SUMMARY OF THE INVENTION
Accordingly, one object of the present invention is to solve the above and other problems.
Another object of the present invention is to provide a novel arithmetic-encoding device that provides a high speed encoding operation for image information without losing advantages achieved by other data compression methods.
Yet another object of the present invention is to provide a novel arithmetic-decoding device that provides a high speed decoding operation for arithmetically encoding image information without losing advantages achieved by other data compression methods.
To achieve these and other objects, the present invention provides a novel arithmetic-encoding device including
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
Ricoh & Company, Ltd.
Young Brian
LandOfFree
Arithmetic-encoding device and an arithmetic-decoding device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic-encoding device and an arithmetic-decoding device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic-encoding device and an arithmetic-decoding device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444450