Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-10-20
2002-07-02
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Transform coding
Reexamination Certificate
active
06415060
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to transform coding for digital signals, and more particularly to coding of picture signals.
2. Description of the Related Art
Conventionally, a linear transform coding system is known as a coding system for an audio or video signal. In the linear transform coding system, a plurality of discrete signals are linearly transformed collectively and resulting transform coefficients are coded, and compression coding can be achieved by selecting the base of the transform taking statistical characters of the signal into consideration. It is known that a coding system which employs discrete cosine transform for the linear transform can realize high compression coding for a signal which behaves in accordance with a Markovian model, and is utilized widely for international standardized systems.
While the discrete cosine transform is useful for realization of high compression coding, since the base of the transform is a real number, it is disadvantageous in that, in order to realize reversible coding, the quantization step size must be small, which results in deterioration of the coding efficiency.
A system which realizes reversible coding of discrete cosine transform without deterioration of the coding efficiency has been proposed by the inventor of the invention of the present application. The system modifies the discrete cosine transform so as to allow reversible transform. The system has two characteristics: one is to approximate the discrete cosine transform with linear transform with an integer matrix, and the other is to remove redundancies included between transform coefficients by reversible quantization.
In the following, a principle of eight-element reversible cosine transform according to the system described above is described. The original eight-element discrete cosine transform according to the international standards transforms an original signal vector (x
0
, x
1
, . . . , x
7
) into transform coefficients (X
0
, X
1
, . . . , X
7
) in accordance with the following expression (1):
[
X
0
X
1
X
2
X
3
X
4
X
5
X
6
X
7
]
=
[
c
4
c
4
c
4
c
4
c
4
c
4
c
4
c
4
c
1
c
3
c
5
c
7
-
c
7
-
c
5
-
c
3
-
c
1
c
2
c
6
-
c
6
-
c
2
-
c
2
-
c
6
c
6
c
2
c
3
-
c
7
-
c
1
-
c
5
c
5
c
1
c
7
-
c
3
c
4
-
c
4
-
c
4
c
4
c
4
-
c
4
-
c
4
c
4
c
5
-
c
1
c
7
c
3
-
c
3
-
c
7
c
1
-
c
5
c
6
-
c
2
c
2
-
c
6
-
c
6
c
2
-
c
2
c
6
c
7
-
c
5
c
3
-
c
1
c
1
-
c
3
c
5
-
c
7
]
[
x
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
]
(
1
)
where c
1
, . . . , c
7
are represented by the following expression (2)
c
k
=
cos
(
k
π
16
)
(
2
)
In this eight-element reversible discrete cosine transform, the eight-element discrete cosine transform represented by the expression (1) is approximated with a transform of the following expression (3):
[
X
0
X
1
X
2
X
3
X
4
X
5
X
6
X
7
]
=
[
a
4
a
4
a
4
a
4
a
4
a
4
a
4
a
4
a
1
a
3
a
5
a
7
-
a
7
-
a
5
-
a
3
-
a
1
a
2
a
6
-
a
6
-
a
2
-
a
2
-
a
6
a
6
a
2
a
3
-
a
7
-
a
1
-
a
5
a
5
a
1
a
7
-
a
3
a
4
-
a
4
-
a
4
a
4
a
4
-
a
4
-
a
4
a
4
a
5
-
a
1
a
7
a
3
-
a
3
-
a
7
a
1
-
a
5
a
6
-
a
2
a
2
-
a
6
-
a
6
a
2
-
a
2
a
6
a
7
-
a
5
a
3
-
a
1
a
1
-
a
3
a
5
-
a
7
]
[
x
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
]
(
3
)
where a
1
, . . . , a
7
are natural numbers. The values a
1
, . . . a
7
are obtained by multiplying each row vector of the discrete cosine transform by a certain number and rounding the products into integers. (X
0
, . . . , X
7
) obtained based on the expression (3) have values near to the original discrete cosine transform coefficients except that they are multiplied by the certain number.
However, the transform coefficients X
0
, . . . , X
7
obtained based on the expression (3) are not independent of each other, but have redundancies. Where the absolute value of the determinant of a transform matrix is represented by D, the density of points which may be taken in the transform domain is 1/D. In other words, the ratio of the points which may be taken in the transform region from among all integer lattice points is 1/D, and the remaining points of the ratio 1-1/D are wasteful points which cannot be taken actually. To use those wasteful points also as an object for coding makes a cause of decreasing the efficiency of compression coding.
Thus, in order to remove the redundancies, reversible coding is performed. However, since it is difficult to define a reversible transform directly in an eight-element space, the expression (3) is decomposed in accordance with a fast calculation scheme and reversible quantization is performed for results of the individual partial transforms.
The transform of the expression (3) can be decomposed into the following expressions (4) to (10):
[
x
0
+
x
7
x
0
-
x
7
]
=
[
1
1
1
-
1
]
[
x
0
x
7
]
(
4
)
[
x
1
+
x
6
x
1
-
x
6
]
=
[
1
1
1
-
1
]
[
x
1
x
6
]
(
5
)
[
x
2
+
x
5
x
2
-
x
5
]
=
[
1
1
1
-
1
]
[
x
2
x
5
]
(
6
)
[
x
3
+
x
4
x
3
-
x
4
]
=
[
1
1
1
-
1
]
[
x
3
x
4
]
(
7
)
[
x
0
+
x
7
+
x
3
+
x
4
x
0
+
x
7
-
x
3
-
x
4
]
=
[
1
1
1
-
1
]
[
x
0
+
x
7
x
4
+
x
3
]
(
8
)
[
x
1
+
x
6
+
x
2
+
x
5
x
1
+
x
6
-
x
2
-
x
5
]
=
[
1
1
1
-
1
]
[
x
1
+
x
6
x
2
+
x
5
]
(
9
)
[
X
0
X
4
]
=
[
1
1
1
-
1
]
[
x
0
+
x
7
+
x
3
+
x
4
x
1
+
x
6
+
x
2
+
x
5
]
(
10
)
[
X
2
X
6
]
=
[
a
2
a
6
a
6
-
a
2
]
[
x
0
+
x
7
-
x
3
-
x
4
x
1
+
x
6
-
x
2
-
x
5
]
(
11
)
[
X
1
X
7
X
3
X
5
]
=
[
a
1
a
7
a
3
a
5
a
7
-
a
1
-
a
5
a
3
a
3
-
a
5
-
a
7
-
a
1
a
5
a
3
-
a
1
a
7
]
[
x
0
-
x
7
x
3
-
x
4
x
1
-
x
6
x
2
-
x
5
]
(
12
)
It is to be noted that, in the expression (10), a
4
=1. This is because the matrix of the expression (10) only includes a
4
and there is no problem if it is assumed that a
4
=1. In this manner, the expression (3) can be decomposed into eight 2×2 matrix transforms and one 4×4 matrix transform. Redundancies are produced in the individual transforms. For example, in the transform of the expression (4), since the absolute value of the determinant of the transform matrix is 2, integer vector values which may possibly be taken as a transform results are ½ the entire integer vector values. The redundancies produced in the individual transforms in this manner are removed for the individual transforms. To this end, for each transform, a result of the transform is reversibly transformed as seen in FIG.
22
. Referring to
FIG. 22
, reference numerals
160
to
167
denote each a transformer for a 2×2 matrix, and
168
denotes a transformer for a 4×4 matrix.
Here, comparison between an eight-element reversible discrete cosine transform and the original discrete cosine transform is described. Similarly as in
FIG. 22
, also the original eight-element discrete cosine transform can be decomposed as seen in FIG.
24
. In
FIG. 24
, transform matrices of individual 2×2 and 4×4 transforms are normalized so that they may correspond to those in FIG.
22
. From comparison between
FIGS. 22 and 24
, it can be seen that the transformer
160
and a transformer
180
, the transformer
161
and a transformer
181
, the transformer
162
and a transformer
182
, the transformer
163
and a transformer
183
, the transformer
164
and a transformer
184
, the transformer
165
and a transformer
185
, the transformer
166
and a transformer
186
, the transformer
167
and a transformer
187
, and the transformer
168
and a transformer
188
correspond to each other. If results obtained by the corresponding transforms are equal, then also transform coefficients obtained finally have substantially equal values. As hereinafter described, this is important when the compatibility between an eight-element reversible discrete cosine transform and the original eight-element discrete cosine transform is considered. It is to be noted that, as can be seen from the comparison between the transforms, the portion of the discrete cosine transform which corresponds to normalization of the base is replaced by reversible quantization in the reversible discrete cosine transform. Consequently, it is important how to make a result of reversible quan
Foley & Lardner
Johnson Timothy M.
Nec Corporation
LandOfFree
Lossless transform coding system having compatibility with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lossless transform coding system having compatibility with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossless transform coding system having compatibility with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2832267