Image encoding apparatus sensitive to tone variations

• US 5,414,527 A
• Filed: 08/13/1992
• Issued: 05/09/1995
• Est. Priority Date: 08/14/1991
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Suzuki, Kazuhiro, Koshi, Yutaka, Kunitake, Setsu, Kamizawa, Koh
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): VU, KIM Y
• Application Number:
  US07/928,718
• Time in Patent Office: 999 Days
• Field of Search: 358/261.3, 358/262.1, 358/426, 358/427, 358/429, 358/433, 358/138, 382/56, 348/420, 348/416
• US Class Current: 382/239
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An encoding system which prevents deterioration of a picture quality and provides a high encoding efficiency even when the size of a block is increased to enhance an encoding efficiency. An input image which is divided into blocks by a blocking unit, is supplied to a plurality of encoders which perform encoding in different numbers of tone levels respectively. Respective pieces of encoded image information from the respective encoders are supplied in common to a selector. A block classification unit determines the degree of the tone gradient of an input block and then outputs the classification result to the selector. The selector, in accordance with the block classification result, selects one of the respective pieces of the encoded image information and outputs the selected one as selected encoded image information. For example, when the tone varies greatly, there is selected the encoder which has a small number of tone levels and a high resolution.

Claims

1. An image encoding device comprising:

blocking means for sampling images and dividing each of said images into input blocks each including m×

n picture elements where m and n are positive integers, respectively;

block classifying means for classifying based on a number of tone levels and resolutions within said input blocks; and

a plurality of block truncation encoding means allocated such that the amount of codes of the tone levels and resolutions within said input blocks provides a given amount of codes in each of said input blocks, wherein said plurality of block truncation encoding means are switched in accordance with the results of said block classifying means to thereby execute their block truncation encoding operations,

wherein said block classifying means comprises;

locally decoding means for decoding two or more pieces of encoded information obtained by encoding said input blocks simultaneously or sequentially by said plurality of block truncation encoding means and

distortion computing means for obtaining an amount of truncation between said input blocks and a plurality of locally decoded blocks obtained by said locally decoding means, and

wherein the classified results of said input blocks are obtained from one of said plurality of locally decoded blocks which has the minimum distortion.

2. An image encoding device comprising:

blocking means for sampling images and dividing each of said images into input blocks each including m×

n picture elements where m and n are positive integers, respectively;

block classifying means for classifying based on a number of tone levels and resolutions within said input blocks; and

a plurality of block truncation encoding means allocated such that the amount of codes of the tone levels and resolutions within said input blocks provides a given amount of codes in each of said input blocks, wherein said plurality of block truncation encoding means are switched in accordance with the results of said block classifying means to thereby execute their block truncation encoding operations,

wherein when decoding said encoded information of said image encoding device, if the resolution information is selectively omitted in a given direction, then at least one picture element out of the decoded neighboring picture elements, which corresponds to said resolution information, is interpolated before said encoded information is reconstructed.

3. An image encoding device comprising:

blocking means for sampling images and dividing each of the images into input blocks each input block having m×

n picture elements where m and n are positive integers;

average value calculating means for obtaining an average value in each of said input blocks;

average value separating means for subtracting said average value obtained by said average value calculating means from each of said picture elements in each of said input blocks;

analyzing means for analyzing features, in a resolution direction and a tone level direction, of average value separated blocks obtained by said average value separating means;

mode deciding means, in accordance with the results obtained by said analyzing means, for deciding a picture element sub-sampling shape and a picture element sub-sampling ratio in a preset number of said average value separated blocks and a number of tone levels in said average value separated blocks independently of one another;

resolution truncation means for sub-sampling one of the picture elements in said average value separated blocks in accordance with the picture element sub-sampling shape and picture element sub-sampling ratio decided by said mode deciding means;

tone level truncation means for quantizing the picture elements in said average value separated blocks sub-sampled by said resolution truncation means by the number of tone levels decided by said mode deciding means; and

multiplexing means for multiplexing said average value from said average value calculating means, the decision result of said mode deciding means and the output of said tone level truncation means to thereby provide coded data.

4. An image encoding device as set forth in claim 3 wherein, when the features of said average value separated blocks in the resolution direction thereof is analyzed in said analyzing means, the amount of truncation between said average value separated blocks and each of sets of typical shape blocks each including m×

n picture elements where m and n are positive integers or each including picture elements in the number that is obtained by dividing m×

n by its positive integer ratio j where j is a positive integer, is found, the index of the typical shape block having the highest amount of truncation or the set of indexes of the typical shape blocks having the highest amount of truncation in each of said input blocks divided into j sets is considered as the first feature amount of said input blocks in the resolution direction thereof, at least said index or a ratio where said j sets of indexes coincide with each other is considered as a parameter representing the complexity of said average value separated blocks, and said complexity is considered as the second feature amount of said input blocks in said resolution direction thereof.

5. An image encoding device as set forth in claim 4, wherein, when the features of said average value separated blocks in the tone level direction thereof is analyzed in said analyzing means, the square average value separated blocks or a value obtained by averaging an absolute value of each of said picture element values is considered as a distribution value of said input blocks, the result of comparison of said distribution value with one or more kinds of threshold values is considered as a first feature amount in said tone level direction, a cumulative frequency distribution of the respective picture elements of said average value separation block is found, the form of said cumulative frequency distribution is corrected according to said distribution value and is then compared with predetermined one or more normalized distributions, and an index of the distribution coincident with or most approximate to said cumulative frequency distribution is considered as a second feature in said tone level direction.

6. An image encoding device as set forth in claim 5 wherein, when the picture element sub-sampling shape, picture element sub-sampling ratio and the number of tone levels of said input blocks are decided independently of one another by said mode deciding means, at first, previously prepared candidates for the picture element sub-sampling shape and picture element sub-sampling ratio of said average value separated blocks are found from the first and second feature amounts of said input blocks in the resolution direction thereof that can be found by said analyzing means, previously prepared candidates for the number of picture element tone levels of said average value separated blocks from the first and second feature amounts of said input blocks in the tone level direction thereof that can be found by said analyzing means independently of said first and second feature amounts in said resolution direction, and thereafter from sets of said candidates for said picture element sub-sampling shape and picture element sub-sampling ratio and said candidate for said number of tone levels there is selected one set which has a previously set constant compressibility to decide the picture element sub-sampling shape, picture element sub-sampling ratio and the number of tone levels of said input blocks, whereby the amount of codes can be controlled to a constant ratio in each of said input blocks.

7. An image encoding device as set forth in claim 5, wherein, when the picture element sub-sampling shape, picture element sub-sampling ratio and the number of tone levels of said input blocks are decided independently of one another by said mode deciding means, at first, previously prepared candidates for the picture element sub-sampling shape and picture element sub-sampling ratio of said average value separated blocks are found from the first and second feature amounts of resolution of said input blocks to be found by said analyzing means, a previously prepared candidate for the number of picture element tone levels of said average value separated blocks from the first and second feature amounts of said input blocks in the tone level direction thereof to be found by said analyzing means is found independently of said candidates, and thereafter from sets of said candidates for picture element sub-sampling shape and picture element sub-sampling ratio and said candidate for said number of tone levels there is selected one set which provides a previously set constant reconstructed image quality to decide the picture element sub-sampling shape, picture element sub-sampling ratio and number of tone levels, whereby the reproduction image can be controlled to a constant quality in each of said input blocks.

8. An image encoding device as set forth in claim 4, wherein, when the picture element sub-sampling shapes and picture element sub-sampling ratios of said plurality of average value separated blocks are previously set, the sets of the picture element sub-sampling shapes are set in a direction perpendicular to the direction in a two dimensional space of each of the sets of said typical shape blocks, and the sets of the picture element sub-sampling ratios of said average value separated blocks are set in accordance with the second feature amount in said resolution direction.

9. An image encoding device as set forth in claim 5 wherein, when picture elements in said average value separated blocks are quantized by said tone level approximating means from the decision results of said mode deciding means, at first, a dynamic range is derived from the maximum and minimum values of the picture element values in said average value separated blocks, the picture element values in said average value separated blocks are normalized in accordance with said dynamic range, one kind of non-linear quantized feature is selected from a plurality of previously prepared non-linear quantized features in accordance with the second feature amount in said tone level direction obtained by said analyzing means, said normalized picture element values in said average value separated blocks are quantized by the number of tone levels decided by said mode deciding means and at the same time the maximum and minimum values of the picture element values in said average value separated blocks are quantized by a given feature, and said quantized values are multiplexed into said coded data.

10. An image encoding device as set forth in claim 6 wherein, when picture elements in said average value separated blocks are quantized by said tone level approximating means from the decision results of said mode deciding means, at first, a dynamic range is found from the maximum and minimum values of the picture element values in said average value separated blocks, the picture element values in said average value separated blocks are normalized in accordance with said dynamic range, one kind of non-linear quantized feature is selected from a plurality of previously prepared non-linear quantized features in accordance with the second feature amount in said tone level direction obtained by said analyzing means, said normalized picture element values in said average value separated blocks are quantized by the number of tone levels decided by said mode deciding means and at the same time the maximum and minimum values of the picture element values in said average value separated blocks are quantized by a given feature, and said quantized values are multiplexed into said coded data.

11. An image encoding device as set forth in claim 7 wherein, when picture elements in said average value separated blocks are quantized by said tone level approximating means from the decision results of said mode deciding means, at first, a dynamic range is found from the average value separated blocks, the picture element values in said average value separated blocks are normalized in accordance with said dynamic range, one kind of non-linear quantized feature is selected from a plurality of previously prepared non-linear quantized features in accordance with the second feature amount in said tone level direction obtained by said analyzing means, said normalized picture element values in said average value separated blocks are quantized by the number of tone levels decided by said mode deciding means and at the same time the maximum and minimum values of the picture element values in said average value separated blocks are quantized by a given feature, and said quantized values are multiplexed to said coded data.

12. An image encoding device comprising:

first resolution changing means for sampling images and changing the resolutions of said images from a lower resolution toward a higher resolution sequentially into a predetermined resolution;

blocking means for dividing the images supplied from said first resolution changing means into blocks each including m×

n picture elements where m and n are positive integers;

first block encoding means for encoding said blocked images by said blocking means;

first locally decoding means for locally decoding said blocked images encoded by said first block encoding means;

second block encoding means for encoding said locally decoded blocked images decoded by said first locally decoding means in blocks as large as those in said first block encoding means or in blocks set so as to have a ratio of integer thereto in synchronization with the encoding operation of said first block encoding means;

memory means for storing said encoded locally decoded blocked images in a unit of images which have been converted sequentially into those of given resolutions;

second locally decoding means for decoding said encoded locally decoded blocked images stored in said memory means;

second resolution changing means for changing the resolutions of the encoded locally decoded blocked images supplied from said second locally decoding means into the resolutions that correspond to the resolutions of said first resolution changing means; and

subtracting means interposed between said first resolution changing means and said blocking means for subtracting said encoded locally decoded blocked images converted by said second resolution changing means from said images changed in resolution by said first resolution changing means.

13. An image encoding device as set forth in claim 12 wherein said first and second blocking means each comprises:

blocking means for sampling images and dividing each of the images into input blocks each including m×

n picture elements where m and n are positive integers;

average value calculating means for obtaining an average value in said input blocks;

average value separating means for subtracting said average value obtained by said average value calculating means from each of picture elements in said input blocks;

analyzing means for analyzing feature amounts, in resolution direction and a tone level direction, of average value separated blocks obtained by said average value separating means;

mode deciding means, in accordance with the results obtained by said analyzing means, for deciding a picture element sub-sampling shape and a picture element sub-sampling ratio in a preset number of said average value separated blocks and the number of tone levels of images in said average value separated blocks independently of one another,

resolution truncation means for sub-sampling a picture element in said average value separated blocks in accordance with the picture element sub-sampling shape and picture element sub-sampling ratio decided by said mode deciding means,

tone level truncation means for quantizing the picture elements in said average value separated blocks thinned out by said resolution approximating means by means of the number of tone levels decided by said mode deciding means; and

multiplexing means for multiplexing said average value from said average value calculating means, the decision result of said mode deciding means and the output of said tone level approximating means to thereby provide coded data.