Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-10-02
2003-06-03
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S401000, C382S250000
Reexamination Certificate
active
06574648
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a DCT processor which realizes discrete cosine transform (hereinafter referred to as DCT) used for data compression such as image signal processing and, more particularly, to a DCT processor which performs at least one of DCT operation and inverse DCT operation for image data in unit blocks having different sizes.
BACKGROUND ART
DCT is generally used for data compression of an image signal or the like. In data compression for video, generally, data compression utilizing intra-frame (spatial) correlation and data compression utilizing inter-frame (temporal) correlation are performed, and DCT corresponds to the former. DCT is a kind of frequency conversion method, that is, data compression is performed by removing high-frequency components utilizing the characteristics of pixel values such that relatively large pixel values concentrate on low-frequency components after conversion although pixel values disperse at random before conversion.
In DCT, initially, one image is divided into a plurality of unit blocks each having a predetermined shape and comprising a predetermined number of pixels (e.g., 8×8), and DCT is performed on every unit block. Two-dimensional DCT is executed by performing one-dimensional DCT twice. For example, the result of one-dimensional DCT performed on a unit block along its column direction is subjected to one-dimensional DCT along its row direction.
Further, the image signal compressed by DCT is decompressed by inverse DCT.
Formulae (1) and (2) define two-dimensional DCT and two-dimensional inverse ICT for an N×N unit block, respectively.
X
⁡
(
u
,
v
)
=
2
/
N
·
C
⁡
(
u
)
·
⁢
C
⁢
(
v
)
·
∑
i
=
0
N
-
1
⁢
⁢
∑
j
=
0
N
-
1
⁢
⁢
x
⁡
(
i
,
j
)
⁢
⁢
cos
⁢
⁢
(
(
2
⁢
i
+
1
)
⁢
u
⁢
⁢
π
/
2
⁢
N
)
⁢
cos
⁢
⁢
(
(
2
⁢
j
+
1
)
⁢
v
⁢
⁢
π
/
2
⁢
N
)
&AutoLeftMatch;
formula
⁢
⁢
(
1
)
x
⁡
(
i
,
j
)
=
2
/
N
·
∑
u
=
0
N
-
1
⁢
⁢
∑
v
=
0
N
-
1
⁢
⁢
·
C
⁡
(
v
)
·
X
⁡
(
u
,
v
)
⁢
⁢
cos
(
⁢
(
2
⁢
i
+
1
)
⁢
⁢
u
⁢
⁢
π
/
2
⁢
N
)
⁢
⁢
cos
(
⁢
(
2
⁢
j
+
1
)
⁢
v
⁢
⁢
π
/
2
⁢
N
)
formula
⁢
⁢
(
2
)
Further, formula (3) defines one-dimensional DCT which is derived from formulae (1) and (2).
X
⁡
(
u
)
=
2
/
N
·
C
⁡
(
u
)
·
∑
i
=
0
N
-
1
⁢
⁢
x
⁡
(
i
)
⁢
cos
⁡
(
(
2
⁢
i
+
1
)
⁢
u
⁢
⁢
π
/
2
⁢
N
)
formula
⁢
⁢
(
3
)
In these formulae, x(i,j) (i,j=0,1,2, . . . ,N−1) indicates pixels, and X(u,v) (C(
0
)=1/{square root over ( )}2, C(u)=C(v)=1 (u,v=1,2, . . . ,N−1)) indicates transform coefficients.
When N=8, the matrix operation of the one-dimensional DCT matrix according to formula (3) is represented by
**N=8**
⁢
(
X0
X1
X2
X3
X4
X5
X6
X7
)
=
(
0.353553
0.353553
0.353553
0.353553
0.353553
0.353553
0.353553
0.353553
0.490393
0.415735
0.277785
0.097545
-
0.097545
-
0.277785
-
0.415735
-
0.490393
0.461940
0.191342
-
0.191342
-
0.461940
-
0.461940
-
0.191342
0.191342
0.461940
0.415735
-
0.097545
-
0.490393
-
0.277785
0.277785
0.490393
0.097545
-
0.415735
0.353553
-
0.353553
-
0.353553
0.353553
0.353553
-
0.353553
-
0.353553
0.353553
0.277785
-
0.490393
0.097545
0.415735
-
0.415735
-
0.097545
0.490393
-
0.277785
0.191342
-
0.461940
0.461940
-
0.191342
-
0.191342
0.461940
-
0.461940
0.191342
0.097545
-
0.277785
0.415735
-
0.490393
0.490393
-
0.415735
0.277785
-
0.097545
)
⁢
(
x0
x1
x2
x3
x4
x5
x6
x7
)
formula
⁢
⁢
(
4
)
When N=7, N=6, N=5, N=4, N=3, N=2, the matrix operations of the one-dimensional DCT are represented by
**N=7**
⁢
(
X0
X1
X2
X3
X4
X5
X6
)
=
(
0.377964
0.377964
0.377964
0.377964
0.377964
0.377964
0.377964
0.521121
0.417907
0.231921
0.000000
-
0.231921
-
0.417907
-
0.521121
0.481588
0.118942
-
0.333269
-
0.534522
-
0.333269
0.118942
0.481588
0.417907
-
0.231921
-
0.521121
-
0.000000
0.521121
0.231921
-
0.417907
0.333269
-
0.481588
-
0.118942
0.534522
-
0.118942
-
0.481588
0.333269
0.231921
-
0.521121
0.417907
0.000000
-
0.417907
0.521121
-
0.231921
0.118942
-
0.333269
0.481588
-
0.534522
0.481588
-
0.333269
0.118942
)
⁢
(
x0
x1
x2
x3
x4
x5
x6
)
formula
⁢
⁢
(
5
)
**N=6**
⁢
(
X0
X1
X2
X3
X4
X5
)
=
(
0.408248
0.408248
0.408248
0.408248
0.408248
0.408248
0.557678
0.408248
0.149429
-
0.149429
-
0.408248
-
0.557678
0.500000
0.000000
-
0.500000
-
0.500000
-
0.000000
0.500000
0.408248
-
0.408248
-
0.408248
0.408248
0.408248
-
0.408248
0.288675
-
0.577350
0.288675
0.288675
-
0.577350
0.288675
0.149429
-
0.408248
0.557678
-
0.577678
0.408248
-
0.149429
)
⁢
(
x0
x1
x2
x3
x4
x5
)
formula
⁢
⁢
(
6
)
**N=5**
⁢
(
X0
X1
X2
X3
X4
)
=
(
0.447214
0.447214
0.447214
0.447214
0.447214
0.601501
0.371748
0.000000
-
0.371748
-
0.601501
0.511667
-
0.195440
-
0.632456
-
0.195440
0.511667
0.371748
-
0.601501
-
0.000000
0.601501
-
0.371748
0.195440
-
0.511667
0.632456
-
0.511667
0.195440
)
⁢
(
x0
x1
x2
x3
x4
)
formula
⁢
⁢
(
7
)
**N=4**
⁢
(
X0
X1
X2
X3
)
=
(
0.500000
0.500000
0.500000
0.500000
0.635281
0.270598
-
0.270598
-
0.635281
0.500000
-
0.500000
-
0.500000
0.500000
0.270598
-
0.635281
0.635281
-
0.270598
)
⁢
(
x0
x1
x2
x3
)
formula
⁢
⁢
(
8
)
**N=3**
⁢
(
X0
X1
X2
)
=
(
0.577350
0.707107
0.408248
0.577350
0.000000
-
0.816497
0.577350
-
0.707107
0.408248
)
⁢
(
x0
x1
x2
)
formula
⁢
⁢
(
9
)
**N=2**
⁢
(
X0
X1
)
=
(
0.707107
0.707107
0.707107
-
0.707107
)
⁢
(
x0
x1
)
formula
⁢
⁢
(
10
)
On the other hand, the matrix operation of the one-dimensional inverse DCT in the case where N=8 is represented by
**N=8**
⁢
(
x0
x1
x2
x3
x4
x5
x6
x7
)
=
(
0.353553
0.490393
0.461940
0.415735
0.353553
0.277785
0.191342
0.097545
0.353553
0.415735
0.191342
-
0.097545
-
0.353553
-
0.490393
-
0.461940
-
0.277785
0.353553
0.277785
-
0.191342
-
0.490393
-
0.353553
0.097545
0.461940
0.415735
0.353553
0.097545
-
0.461940
-
0.277785
0.353553
0.415735
-
0.191342
-
0.490393
0.353553
-
0.097545
-
0.461940
0.277785
0.353553
-
0.415735
-
0.191342
0.490393
0.353553
-
0.277785
-
0.191342
0.490393
-
0.353553
-
0.097545
0.461940
-
0.415735
0.353553
-
0.415735
0.191342
0.097545
-
0.353553
0.490393
-
0.461940
0.277785
0.353553
-
0.490393
0.461940
-
0.415735
0.353553
-
0.277785
0.191342
-
0.097545
)
⁢
(
X0
X1
X2
X3
X4
X5
X6
X7
)
formula
⁢
⁢
(
11
)
⁢
When N=7, N=6, N=5, N=4, N=3, and N=2, the matrix operations of the one-dimensional inverse DCT are represented by
**N=7**
⁢
(
x0
x1
x2
x3
x4
x5
x6
)
=
(
0.377964
0.521121
0.481588
0.417907
0.333269
0.231921
0.118942
0.377964
0.417907
0.118942
-
0.231921
-
0.481588
-
0.521121
-
0.333269
0.377964
0.231921
-
0.333269
-
0.521121
-
0.118942
0.417907
0.481588
0.377964
0.000000
-
0.534522
-
0.000000
0.534522
0.000000
-
0.534522
0.377964
-
0.231921
-
0.333269
0.521121
-
0.118942
-
0.417907
0.481588
0.377964
-
0.417907
0.118942
0.231921
-
0.481588
0.521121
-
0.333269
0.377964
-
0.521121
0.481588
-
0.417907
0.333269
-
0.231921
0.118942
)
⁢
(
X0
X1
X2
X3
X4
X5
X6
)
formula
⁢
⁢
(
12
)
**N=6**
⁢
(
x0
x1
x2
x3
x4
x5
)
=
(
0.408248
0.557678
0.500000
0.408248
0.288675
0.149429
0.408248
0.408248
0.000000
-
0.408248
-
0.577350
-
0.408248
0.408248
0.149429
-
0.500000
-
0.408248
0.288675
0.557678
0.408248
-
0.149429
-
0.500000
0.408248
0.288675
-
0.577678
0.408248
-
0.408248
-
0.000000
0.408248
-
0.577350
0.408248
0.408248
-
0.557678
0.500000
-
0.408248
0.288675
-
0.149429
)
⁢
(
X0
X1
X2
X3
X4
X5
)
formula
⁢
⁢
(
13
)
**N=5**
Nakamura Tsuyoshi
Oohashi Masahiro
Malzahn David H.
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Dct arithmetic device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dct arithmetic device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dct arithmetic device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3123590