Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2000-08-23
2004-09-14
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Quantization
C382S245000, C382S246000, C382S247000, C341S106000, C358S426140, C375S240030, C375S240230
Reexamination Certificate
active
06792157
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to technology for encoding image data.
2. Description of the Related Art
First, encoding systems according to the prior art will be considered.
1. JPEG System
Known image data encoding systems include the Joint Photographic Coding Experts Group (JPEG), which is an international standard system. The JPEG system, as it is designed for mounting in a hardware form, takes a long processing time if executed on a software basis. The encoding process of the JPEG system is outlined below.
(1) Pixel value data are cut out in blocks each having eight pixels by eight lines from image data entered in the order of raster scanning;
(2) Pixel values in each cut-out block are subjected to discrete cosign transform (DCT);
(3) The resultant transform coefficient is subjected to linear quantization; and
(4) The resultant quantization index is subjected to Huffman's encoding.
Among these steps, the quantity of computation is particularly large for DCT. DCT can be accomplished by multiplying twice eight rows by eight columns. Therefore 16 rounds of product addition are needed per pixel.
Generally speaking, an irreversible encoding system is a technique to reduce the quantity of data without inviting visual deterioration in image quality by removing unnecessary redundant components in the reproduction of images. Redundant components can be broadly classified into redundancy in resolution and redundancy in gray-scale. The JPEG system achieves a high encoding efficiency by addressing both types of redundancy in combination.
In order to remove redundant components in resolution, relatively heavy processing loads are required, such as frequency conversion and space filtering. On the other hand, removal of redundant components in gray-scale requires only relatively light processing loads, such as quantization and discarding of lower-order bits. If an irreversible encoding system for removing only redundant components in gray-scale, the system can be expected to take no long processing time even if executed on a software basis.
2. BTC System
Systems focusing on redundant components in gray-scale include the block truncation coding (BTC) systems. One example is the BTC system disclosed in the Japanese Published Examined Patent Application NO. 8-2083. The process of encoding by the BTC system is outlined below.
(1) Pixel value data are cut out in blocks each having four pixels by four lines from image data entered in the order of raster scanning;
(2) The difference between the maximum and minimum values (dynamic range) is computed for the pixel values of each cut-out block;
(3) Blocks whose dynamic ranges are not broader than a predetermined first threshold are subjected to one-level quantization;
(4) Blocks whose dynamic ranges are broader than a predetermined second threshold are subjected to four-level quantization;
(5) All other blocks are subjected to two-level quantization;
(6) The quantization characteristics at each level are computation according to the pixel value of each block; and
(7) The computed quantization characteristics and quantization index are subjected to entropy encoding.
The BTC system is subject to less processing loads than the JPEG system, but it is liable to give rise to the following problems.
First, since the number of gray-scale levels for quantization is switched block by block, the blocks are susceptible to distortion. For instance, an input image whose density profile is shown in
FIG. 18
is considered. In the figure, the horizontal axis represents the positions of pixels, and the vertical axis and pixel values. This input image, when subjected to BTC encoding and BTC decoding, is turned into an output image whose density profile is shown in FIG.
19
. In this process, a level difference in pixel value arises on the boundary between blocks of 1 to 4 in pixel position including an edge and blocks of 5 to 8 in pixel position including no edge. In such a case, because of the characteristics of human vision, even a slight level difference is likely to be detected as a block-shaped distortion.
Second, there is an overhead for encoding and transmitting the quantization characteristics. The quantization characteristics have the number of quantization levels, the reference level and the level intervals. Where the gray-scale accuracy of input pixels is 8 [bits/pixel], the original data quantity of additional information is 1.6+8+8=17.6 [bits]. If the compression ratio of entropy encoding is 2, the quantity of additional information will be 8.8 [bits]. Since the data quantity of a block is 16 [Bytes], the ratio of the additional information will be about {fraction (1/14.5)}. The smaller the block size, the less likely the block distortion to occur, but this would mean a greater ratio of the additional information, and there is a practical limit to block size reduction.
Third, determining quantization characteristics block by block entails heavy processing loads. In order to determine quantization characteristics, the largest pixel value and the smallest pixel value in each block are found out. Further, to compute the reference level and the level intervals, the average of pixel values in each block are figured out. In particular where four-level quantization is chosen, division by three is required. Of these loads, that of calculating the largest and smallest values is especially heavy.
Fourth, the BTC system involves complex encoding and decoding units. The BTC system, as illustrated in
FIG. 20
, encodes quantization indexes computed block by block, put together into pages, and represented on a bit plane basis by a reversible binary encoding system, for instance the Modified Read (MMR) system, which is an international standard system. On the other hand, the additional information indicating the quantization characteristics is variable-length encoded block by block.
Since two different ways of processing, block processing and bit plane processing, are needed, the overall configuration of the system is made complex. To add, in
FIG. 20
, reference numeral
91
denotes a blocking unit;
93
, a quantization unit;
94
, a paging unit;
95
, a binary encoding unit; and
96
, a variable length encoding unit.
An overall approach according to the present invention will be described below.
1. Improvement of the BTC System
The challenge is to obtain an irreversible image encoding apparatus which is susceptible to less processing loads than the JPEG system, free from block distortion which the BTC system entails and can be realized in a simpler configuration than the BTC system.
An encoding system to obviate the shortcomings of the BTC system will be discussed below. First, quantization characteristics are switched pixel by pixel without blocking. Second, to dispense with the transmission of quantization characteristics as additional information, inverse quantized pixel values, i.e. pixel values whose number of gray-scale levels is limited, are encoded instead of encoding the quantization index. Third, in order to alleviate the load of determining the quantization characteristics, only pseudo-contours are taken note of.
2. Restrainng of Pseudo-contours
This system, since it involves the restriction of the number of gray-scale levels but no blocking, is free from block distortion. Only pseudo-contours need to be taken note of as a distortion attributable to encoding. The biggest challenge here is to work out a technique by which quantization can be carried out with the smallest possible number of gray-scale levels while restraining the generation of pseudo-contours.
The ease of pseudo-contour generation varies with the image pattern. For instance, in the part of an image pattern having edges, distortion is unlikely to be detected even if there is some quantization error. In contrast, in a uniform gray-scale part with little noise, even a slight quantization error is likely to be detected as a pseudo-contour. Even in the same gray-scale part, a high
Koshi Yutaka
Sekino Masanori
Shishido Shinji
So Ikken
Fuji 'Xerox Co., Ltd.
Hung Yubin
Mehta Bhavesh M.
Morgan & Lewis & Bockius, LLP
LandOfFree
Image encoding apparatus and quantization characteristics... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image encoding apparatus and quantization characteristics..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image encoding apparatus and quantization characteristics... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3228574