Lossless transform coding system for digital signals

Details Lossless transform coding system for digital signals Lossless transform coding system for digital signals

1998-08-03

2001-01-16

Tran, Phuoc (Department: 2721)

Image analysis

Image transformation or preprocessing

Reexamination Certificate

active

06175661

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to transform coding for digital signals, and more particularly to coding for video signals.
2. Description of the Related Art
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 first to obtain transform coefficients and then the transform coefficients are coded. By suitable selection of the base of the linear transform taking statistical characteristics of the signals into consideration, compression coding can be realized. It is known that a coding system which employs discrete cosine transform as such linear transform can achieve the highest compression coding of signals which conform to a highly correlated Markov probability model, and is utilized widely for international standardized systems.
While the discrete cosine transform is useful to achieve high compression coding in this manner, since it uses real numbers for the base of the transform, in order to realize lossless reversible coding, the quantization step size must be set small. This, however, gives rise to a disadvantage that the coding efficiency is deteriorated.
A system which achieve reversible coding such as discrete cosine transform without such deterioration in coding efficiency have been proposed. It is a “Lossless Transform Coding System for Digital Signals” proposed precedently by Mutsumi Ohta, one of the inventors of the present invention. In this system, reversible quantization is performed taking a discrete structure of transform coefficients using an integer matrix to which the transform is approximated to achieve reversible coding. In the following, the principle of this system is described.
According to the system, a transform matrix is multiplied by fixed numbers for individual rows and half-adjusted to obtain another matrix whose elements are integers, and then, integer N-element original signal vectors (x
0
, . . . , x
N−1
) are transformed with the integer matrix to obtain vectors (hereinafter referred to as transform points) (X
0
, . . . , X
N−1
) in a transform domain. While reversible coding can be achieved by the transform, since the density of the transform points is given by a reciprocal number 1/D to the determinant D of the integer matrix used for the transform, as the value of D increases, the number of useless integer points which do not make transform points in the transform domain increases, resulting in deterioration of the coding efficiency.
In order to eliminate such redundancies, reversible quantization is performed taking a discrete structure of transform points into consideration. It can be proved that the transform point structure has a period D with regard to each axis. Therefore, if the quantization periods of the individual axes which are multiples of D are represented by (d
0
, . . . , d
N−1
) and reversible quantization in regions of 0≦X
0
≦d
0
−1, . . . 0≦X
N−1
≦d
N−1
−1 around the origin is defined artificially, then reversible quantization of an arbitrary transform point can be performed making use of the periodicity.
First, (X
0
, . . . X
N−1
) are divided by the quantization periods (d
0
, . . . , d
N−1
) to obtain quotients (a
0
, . . . , a
N−1
) and remainders (r
0
, . . . r
N−1
), respectively, and the quantization defined as above is performed for the remainders (r
0
, . . . r
N−1
) to obtain quantization values (q
0
, . . . , q
N−1
) of the remainders (r
0
, . . . , r
N−1
), respectively. Then, calculation given by the following expression is performed to obtain quantization values (Q
0
. . . Q
N−1
) of the transform points:
Q
i
=a
i
m
i
+q
i
(
i=
0, . . .
N−
1)  (1)
where m
i
(i=0, 1, . . . , N−1) is a width (range) of the possible values as q
i
. The redundancies of the transform points can be removed by quantization using the technique described above.
On the other hand, in inverse transform, (Q
0
, . . . , Q
N−1
) are first divided by (m
0
, . . . , m
N−1
) to obtain quotients (a
0
, . . . , a
N−1
) and remainders (q
0
, . . . , q
N−1
), respectively. Then, dequantization is performed for the remainders (q
0
, . . . , q
N−1
) to obtain (r
0
, . . . , r
N−1
). Then, calculation given by the following expression:
X
i
=a
i
d
i
+r
i
(
i=
0
, . . . , N−
1)  (2)
is performed, thereby achieving reversible dequantization. After the dequantization, the transform points (X
0
, . . . , X
N−1
) are linearly transformed with an inverse matrix to the original integer matrix to obtain the original signals (x
0
, . . . , x
N−1
).
In two-element discrete cosine transform, a matrix is approximated with
[
1
1
1
-
1
]
(
3
)
In this instance, since the determinant D is D=2, if reversible quantization is set in a basic region of 2×2, 4×4, 8×8, 16×8 or the like, reversible quantization for all inputs can be performed using the method described above.
In four-element discrete cosine transform, a matrix can be approximated, using suitable integers c
2
, c
4
and c
6
, with a matrix transform of
[
X
0
X
1
X
2
X
3
]
=
[
c
4
c
4
c
4
c
4
c
2
c
6
-
c
6
-
c
2
c
4
-
c
4
-
c
4
c
4
c
6
-
c
2
c
2
-
c
6
]
⁢
 
[
x
0
x
1
x
2
x
3
]
(
4
)
In this instance, an applicable high speed calculation method is available and can decompose the matrix transform into four 2×2 matrix transforms given by
[
x
0
+
x
3
x
0
-
x
3
]
=
[
1
1
1
-
1
]
⁢
 
[
x
0
x
3
]
(
5
)
[
x
1
+
x
2
x
1
-
x
2
]
=
[
1
1
1
-
1
]
⁢
 
[
x
1
x
2
]
(
6
)
[
X
0
X
2
]
=
[
c
4
c
4
c
4
-
c
4
]
⁢
 
[
x
0
+
x
3
x
1
+
x
2
]
(
7
)
[
X
1
X
3
]
=
[
c
2
c
6
c
6
-
c
2
]
⁢
 
[
x
0
-
x
3
x
1
-
x
2
]
(
8
)
By applying the method described above to the individual transforms, reversible transform free from redundancies can be achieved readily.
In eight-element discrete cosine transform, a matrix can be approximated, using suitable integers c
1
, c
2
, c
3
, c
4
, c
5
, c
6
and c
7
, with a matrix transform of
[
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
]
(
9
)
Also in this instance, an applicable high speed calculation method is available and can decompose the matrix transform into matrix transforms given by
[
x
0
+
x
7
x
0
-
x
7
]
=
[
1
1
1
-
1
]
⁢
 
[
x
0
x
7
]
(
10
)
[
x
1
+
x
6
x
1
-
x
6
]
=
[
1
1
1
-
1
]
⁢
 
[
x
1
x
6
]
(
11
)
[
x
2
+
x
5
x
2
-
x
5
]
=
[
1
1
1
-
1
]
⁢
 
[
x
2
x
5
]
(
12
)
[
x
3
+
x
4
x
3
-
x
4
]
=
[
1
1
1
-
1
]
⁢
 
[
x
3
x
4
]
(
13
)
[
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
]
(
14
)
[
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
]
(
15
)
[
X
0
X
4
]
=
[
c
4
c
4
c
4
-
c
4
]
⁢
 
[
x
0
+
x
7
+
x
3
+
x
4
x
1
+
x
6
+
x
2
+
x
5
]
(
16
)
[
X
2
X
6
]
=
[
c
2
c
6
c
6
-
c
2
]
⁢
 
[
x
0
+
x
7
-
x
3
-
x
4
x
1
+
x
6
-
x
2
-
x
5
]
(
17
)
[
X
1
X
7
X
3
X
5
]
=
[
c
1
c
7
c
3
c
5
c
7
-
c
1
-
c
5
c
3
c
3
-
c
5
-
c
7
-
c
1
c
5
c
3
-
c
1
c
7
]
⁢
 
[
x
0
-
x
7
x
3
-
x
4
x
1
-
x
6
x
2
-
x
5
]
(
18
)
Since the first eight transforms given by the expressions (10) to (17) are 2×2 matrix transforms, the method described above can be applied readily to them. However, the last 4×4 matrix transform given by the expression (18) requires such a large region for definition of quantization that a practical circuit for it cannot be realized. In particular, the determinant D of the matrix of the expression (18) is given by
D

Affiliated with

Also associated with

Rating

Lossless transform coding system for digital signals 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 for digital signals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossless transform coding system for digital signals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2507166