Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2002-08-28
2003-11-18
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C382S233000
Reexamination Certificate
active
06650786
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image encoding/decoding apparatus, and more particularly to lossy coding with respect to multi-level input images.
2. Description of the Related Art
Since images generally comprise very large volumes of data, the images are generally compressed by encoding during storage and transmission. If the image data subject to image encoding at that time is largely classified into two types, the image data can be classified into, for example, natural images and artificial images.
The former type is one in which actually existing images have been converted into digital data by some means. For instance, an image which is obtained by reading a photograph by a scanner or by capturing a scene by a digital camera corresponds to this type. The latter type is one in which images which do not actually exist are generated as digital data by some means. For instance, computer graphics and a document which is prepared by a word processor correspond to this type. Hereafter, natural images and artificial images are used under these definitions.
Generally, as for natural images, noise tends to be superposed thereon during digital transform, and their high-frequency components tend to degrade. As a result, the resultant data has a large amount of information in low-order bits, and the number of colors used is also large. In addition, if natural images are subjected to frequency analysis, components are liable to concentrate on a low-frequency region, and a high-frequency region attenuates.
On the other hand, in the case of artificial images, the amount of information in low-order bits is not large excluding a case in which noise is intentionally added thereto, and colors which are used are also liable to concentrate on particular colors. In addition, since edges, fine lines, and the like are depicted sharply, a large amount of important information is included in a high-frequency region as well.
Two experimental examples for confirming the above fact are shown in
FIGS. 26
to
18
. As a first experiment, values in which the square roots of mean squares of coefficients obtained by discrete cosine transform (DCT) processing were individually determined were examined with respect to a number of images. The results in which the square roots were added for the respective eight areas shown in
FIG. 26
are shown in the part b) of the same drawing. Since the DCT coefficients are expressed in such a manner that the frequency increases from upper left toward lower right, in
FIG. 26
the right-hand side of the x-axis corresponds to a high frequency. As is apparent from the drawing, in the case of natural images, components decrease as the frequency becomes higher, whereas, in the case of artificial images, components are distributed in spite of the frequency.
In a second experiment, adjacent pixel values were fetched from an image, and the statistics of the result of subtraction of a left-hand pixel value from a right-hand pixel value was gathered. Hereinafter, this value is referred to as “a previous value differential”.
FIG. 28
shows the results of the second experiment. As is apparent from the drawing, in artificial images, the previous value differential is concentrated in 0 in comparison with natural images. This shows that the prediction accuracy in the prediction of the previous value for predicting the right-hand pixel value from the left-hand pixel value becomes high.
Hereafter, image encoding techniques which are effective for natural images and artificial images will be respectively described as first and second conventional examples.
First, a description will be given of a conventional encoding technique with respect to natural images as a first conventional example. Since a natural image inherently contains a large amount of information, it becomes necessary to quantize the information by some technique. Therefore, if consideration is given to the efficiency of quantization, since, in the case of a natural image, frequency components are concentrated in a low-frequency region, quantization in which average errors are made small can be realized by quantizing a low-frequency region finely and quantizing a high-frequency region coarsely. That is, it is possible to minimize the effect on image quality and reduce the amount of information efficiently.
Frequency transform coding, which is one technique of image encoding, makes use of this characteristic, effects frequency transform of an input image, and coarsely quantizes information in high-frequency, in particular. As a typical example of frequency transform coding, it is possible to cite the DCT method of Joint Photographic Experts Group (JPEG), which is an international standard. Hereafter, a description will be given of the JPEG-DCT method as a first conventional example.
Before describing the first conventional example, a description will be given of DCT. The DCT which is used in image encoding is called two-dimensional DCT, to be accurate, and is obtained by independently processing two one-dimensional DCT in the horizontal direction and the vertical direction. According to “kara seishi gazo no kokusai fugouka houshiki _JPEG arugorizumu
13
(International standard encoding method for color still image: JPEG Algorithm)” (Endoh,
Interface,
1991. 12, pp. 160-182), if an image block subject to transformation is written as x(m, n) and a transformed coefficient block as y(u, v), an 8×8 DCT transformation formula and an inverse transformation formula for an 8-bit image can be written as follows.
[
Mathematical
Formula
1
]
y
(
u
,
v
)
=
c
(
u
)
c
(
v
)
4
∑
m
=
0
7
∑
n
=
0
7
(
x
(
m
,
n
)
-
128
)
cos
(
2
m
+
1
)
u
π
16
cos
(
2
n
+
1
)
v
π
16
(
1
)
x
(
m
,
n
)
=
1
4
∑
u
=
0
7
∑
v
=
0
7
c
(
u
)
c
(
v
)
y
(
u
,
v
)
cos
(
2
m
+
1
)
u
π
16
cos
(
2
n
+
1
)
v
π
16
+
128
w
h
e
r
e
c
(
u
)
,
c
(
v
)
=
1
2
(
u
,
v
=
0
)
=
1
a
n
d
o
t
h
e
r
s
&AutoLeftMatch;
(
2
)
FIGS. 29 and 30
are an image lossy encoding apparatus and an image lossy decoding apparatus, respectively, in accordance with the first conventional example. These drawings are partially taken from
FIG. 3
on page 163 of “kara seishi gazo no kokusai fugouka houshiki _JPEG arugorizumu_(International standard encoding method for color still image: JPEG Algorithm)” (ibid.), and terms are modified. In
FIGS. 29 and 30
, reference numeral
10
denotes an image input unit;
20
, a DCT unit;
35
, a coefficient quantizing unit;
45
, coefficient output unit;
110
, input image data;
120
, coefficient data;
170
, quantized coefficient data;
225
, a coefficient input unit;
240
, an inverse DCT unit;
250
, a decoded-image output unit;
260
, a coefficient inversely-quantizing unit;
320
, decoded image data; and
330
, inversely-quantized coefficient data.
A description will be given of the various units shown in
FIGS. 29 and 30
. The encoding apparatus in
FIG. 29
has the following configuration. The image input unit
10
receives as its input an image from an external circuit, and sends the same to the DCT unit
20
as the input image data
110
. The DCT unit
20
effects DCT processing with respect to the input image data
110
, and sends the result to the coefficient quantizing unit
30
as the coefficient data
120
. The coefficient quantizing unit
30
effects quantization processing with respect to the coefficient data
120
in a predetermined method, and sends the result to a coefficient output unit
Kimura Shun-ichi
Koshi Yutaka
So Ikken
Yokose Taro
Boudreau Leo
Fuji 'Xerox Co., Ltd.
Oliff & Berridg,e PLC
Sherali Ishrat
LandOfFree
Image encoding apparatus and image decoding apparatus 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 image decoding apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image encoding apparatus and image decoding apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3155252