Download Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations PDF

TitleDiscrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations
LanguageEnglish
File Size2.9 MB
Total Pages353
Table of Contents
                            sdarticle
sdarticle2
sdarticle3
sdarticle4
sdarticle5
sdarticle6
sdarticle7
sdarticle8
sdarticle9
sdarticle10
                        
Document Text Contents
Page 1

Prelims-P373624.tex 7/8/2006 13: 3 Page ix

Preface

Since the book, Discrete Cosine Transform by K. R. Rao and P. Yip (Academic Press,
Boston) was published in 1990, the discrete cosine transform (DCT) has increasingly
attracted the attention of scientific, engineering and research communities. The DCT is used
in many applications and in data compression in particular. This is due to the fact that the
DCT has excellent energy-packing capability and also approaches the statistically optimal
Karhunen–Loéve transform (KLT) in decorrrelating a signal. The development of various
fast algorithms for the efficient implementation of the DCT involving real arithmetic only,
further contributed to its popularity. In the last several years there have been significant
advances and developments in both theory and applications relating to transform processing
of signals. In particular, digital processing motivated the investigation of other forms of
DCTs for their integer approximations. International standards organizations (ISO/IEC
and ITU-T) have adopted the use of various forms of the integer DCT. At the same time,
the investigation of other forms of discrete sine transforms (DSTs) has made a similar
impact. There is therefore a need to extend the coverage to include these techniques. This
book is aimed at doing just that.

The authors have retained much of the basic theory of transforms and transform processing,
since the basic mathematics remains valid and valuable. The theory and fast algorithms
of the DCTs, as well as those for the DSTs, are dealt with in great detail. There is also an
appendix covering some of the fundamental mathematical aspects underlying the theory
of transforms. It is no exaggeration to say that applications using DCT are numerous and
it is with this in mind that the authors have decided not to include applications explicitly.
Readers of this book will either have practical problems requiring the use of DCT, or
want to examine the more general theory and techniques for future applications. There
is no practical way of comprehensively dealing with all possible applications. However,
it must be emphasized that implementation of the various transforms is considered an
integral part of our presentation. It is the authors’hope that readers will not only gain some
understanding of the various transforms, but also take this knowledge to apply to whatever
processing problems they may encounter.

The book Discrete Cosine and Sine Transforms: General properties, Fast algorithms and
Integer Approximations is aimed at both the novice and the expert. The fervent hopes and
aspirations of the authors are that the latest developments in the general DCT/DST field

ix

Page 2

Prelims-P373624.tex 7/8/2006 13: 3 Page x

x Preface

further lead into additional applications and also provide the incentive and inspiration to
further modify/customize these transforms with the overall motivation to improve their
efficiencies while retaining the simplicity in implementations.

V. Britanak
P. C. Yip

K. R. Rao

February 2006

Page 176

Ch05-P373624.tex 7/8/2006 13: 1 Page 171

Integer Discrete Cosine/Sine Transforms 171

Table 5.2. The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k).

CMT8 (a, b, c, d, e, f , g, h, i, j, k) Mults/adds Adds/shifts

CMT8 (13, 12, 5, 12, 0, 0, 12, 4, 3, 3, 4) 18/34 50/26
CMT8 (34, 30, 16, 31, 1, 7, 25, 13, 5, 19, 11) 20/38 64/32
CMT8 (39, 36, 15, 35, 2, 8, 30, 16, 6, 19, 14) 22/38 54/30

The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k) in terms of the
number of integer multiplications/additions and multiply-free implementation in the
form of additions/shifts with respect to the signal flow graph in Fig. 5.6 is shown in
Table 5.2.

Note 1: From the relation between DCT-II and DST-II matrices given by (4.11) the
fast SMT8 (a, b, c, d, e, f , g, h, i, j, k) for the DST-II computed via WHT can be easily
obtained.

Note 2: From the set of DCTs/DSTs (see Chapter 4), the symmetric cosine transform
(SCT) and symmetric sine transform (SST) defined by (4.9) and (4.10), respectively,
are EOTs and therefore they can be approximated by the same method. However, the
conversion matrix TN for SCT and SST in contrast to the DCT-II will have the following
structure [19]

TN =

U

(1)
N
2

0

0 U(2)N
2


,

i.e., the block matrices U(1)N
2

and U(2)N
2

are of the same order. Note that the SCT and SST do

not have a recursive structure. Consequently, the conversion matrix TN cannot be generated
recursively.

5.4.2 Integer cosine/sine transforms

In this section, we will discuss the method to integer approximation of the DCT-II matrix
originally reported in Refs. [25–37]. The main idea of the method was partially utilized
to construct the new CMTs in the previous section. In essence, the method is to directly
replace the real-valued elements of DCT-II matrix by integers as opposed to the CMT
case where the DCT-II matrix is approximated indirectly through the conversion matrix.
In general, the method can be applied to any DCT and DST [31, 33] although the integer
solutions may not always exist. The resulting integer transforms are referred to as integer
cosine/sine transforms of order N (ICTN /ISTN ).

Let AN be the real-valued DCT/DST matrix with elements {aij}, i, j = 0, 1, . . . , N − 1, and
ĀN its integer approximation with elements {āij}. The integer approximated ICTN /ISTN

Page 177

Ch05-P373624.tex 7/8/2006 13: 1 Page 172

172 Discrete Cosine and Sine Transforms

should satisfy the following additional properties [28, 33, 36, 37]:

• The orthogonality property: Rows (columns) of the integer transform matrix are
orthogonal to each other.

• The integer property: Elements of the approximated transform matrix are integers. In
fact, the elements are approximated by rational numbers, i.e., ratios of integers. The
unitary nature of these matrices prevents the elements to be just integers.

• The relationship with real-valued transform matrix:
(a) if |aij| ≥ |aik|, then |āij| ≥ |āik|, i, j, k = 0, 1, . . . , N − 1;
(b) sign(aij) = sign(āij), i, j = 0, 1, . . . , N − 1.

The orthogonality property ensures that the forward and inverse ICTN /ISTN have the
same transform structure. The integer property eliminates the need for many floating-
point arithmetic operations in computing the transform, since the elements of integer
transform matrix can be represented by finite number of bits. The orthogonal integer
transform matrix it can further be made orthonormal by multiplying it by an appropriate
diagonal matrix. The approximation method guarantees that all mathematical properties
and the recursive structure (if exists) are preserved in the integer approximated transform
matrix. This fact allows any existing fast algorithm to efficiently implement ICTN /ISTN .
Moreover, the energy packing ability and performance will be close to the original
transform. Thus, ICTsN /ISTsN are functionally compatible to corresponding real-valued
DCTs/DSTs.

The method at first is illustrated in detail on the approximation of DCT-II matrix for
N = 8 together with its possible improvements and simplifications. Since in the recursive
sparse matrix factorization (4.50), the DCT-II matrix CIIN requires DCT-II and DCT-IV
matrices of half size, the integer approximation of DCT-IV is also presented. Finally, the
construction of integer transforms for other DCTs and DSTs is discussed.

5.4.2.1 Integer approximation of DCT-II matrix CII8

In the following we describe all the steps to convert the real-valued DCT-II matrix CII8
to an integer matrix. Let CICT-IIN be the integer approximation of C

II
8 and ICT8-II be

resulting integer 8-point DCT-II. We will search for the approximated matrix CICT-II8 in
the form:

CICT-II8 = Q8 V8, (5.53)

where Q8 is a diagonal matrix with normalization factors on its main diagonal, and V8 is
an integer matrix (V8 is frequently called the prototype matrix). The procedure to construct
the approximated matrix CICT-II8 from the corresponding DCT-II matrix C

II
8 includes the

Page 352

Index-P373624.tex 7/8/2006 13: 4 Page 348

348 Index

M
Markov-1 process, 162
Matrix

Cross-indentity (reflection), 76
Diagonal odd-sign changing, 76
Eigenorthogonal, 143
Hermitian, 318
Involutory, 76
Non-eigenorthogonal, 143
Skew-Hermitian, 318
Symmetric positive definite, 327
Unitary, 318

Matrix eigenvalue problem, 314, 316
Matrix factorization

LDU, 150
LU, 150
PLUS, 151
QR, 149

Matrix norms, 144
1-norm, 145
�-norm, 145
Canonical, 145
Frobenius, 145, 336

MDCT/MDST, 1
Mean square error (MSE), 162
Methods for integer approximation of

DCTs/DSTs, 163
Minimum-adder representation, 221
Modulated lapped transform (MLT), 1
MPEG, 289
Multi-dimensional (MDL) structure, 290
Multiplicative irreducibility, 221

N
Net equivalence, 63
Nets, 63
Neumann boundary condition, 30
Normalization factor, 76
Normalized integer transforms, 289
N-point

Reversible transform, 278
SCT, 75
SST, 75

N-point zero mean signal, 52
N-section, 63

O
Odd DCT, 34
Odd DST, 38
Optimal 1-D 8-point DCT algorithm, 124
Optimal 2-D 8 × 8 DCT-II algorithm, 124
Orthogonal, 308

Basis functions, 51
DCT/DST, 74
EOT matrix factorization, 284

Factorizations of DCT-II and DCT-IV
matrices, 264

Matrices, 332
Transformations, 146

Orthogonality, 308
Orthonormal

Basis set, 310
DCT/DST, 74

Orthonormality, 39

P
Perfectly correlated signal, 61
Periodic signals, 339
Permutation matrix, 85, 102, 118, 245, 326
Plane rotation matrices, 142
PL1UL2 matrix factorization, 289
PLUS-based factorization of DCT matrices,

258
PLUS-based structure, 261
PLUS factorization algorithm, 152
PLUS matrix factorization, 151
Points of symmetry (POS), 44
Power signals, 338
Principal component analysis (PCA), 51
Pseudoinverse matrix, 333

Q
QR-based factorization of DCT matrices, 248
QR-based structure, 252, 253
QR matrix factorization, 149, 328
Quantization, 199, 219, 223, 340
Quantum computing, 5
Quasi-

Diagonal matrix, 290
Triangular (lower) matrices, 290
Triangular (upper) matrices, 290

R
Random signals, 338
Recursive sparse matrix factorizations

DCT-I, 84
DCT-II, 96
DCT-IV, 112
DST-I, 91

Reversible DCT, 276
Rotation-based DCT/DST, 81
Rotation matrix, 88,102
Rounding, 245
Rounding procedure, 266

S
Sampling theorem, 343
Scalar multiplication, 305
Scaled DCT-II, 99
Scaling in time, 18, 24, 41

Page 353

Index-P373624.tex 7/8/2006 13: 4 Page 349

Index 349

Section, 63
Shift

in Frequency, 19, 25
in Time, 19, 25, 41

Signal and its representation, 337
SignDCT, 285
Signed DCT square wave transform, 285
Similarity of matrices, 319
Similarity transformation, 56, 319
Sinc function, 23, 28
Sine transform

Discrete, 35
Symmetric, 75

Singular value decomposition (SVD), 334
Skew-circular convolution, 46
Spectral

Mapping, 317
Radius, 316
Shift, 317

Spectral representations and asymptotic
equivalence, 64

Spectrum, 316
Split-radix

DCT-I algorithm, 86
DCT-II algorithm, 108
DST-I algorithm, 94
FFT algorithm, 217

Strong norm, 62
Symmetric convolution, 44
Symmetric cosine transform (SCT), 75
Symmetric periodic sequence (SPS), 45
Symmetric sine transform (SST), 75

T
Tchebyshev polynomials, 58, 69
Toeplitz matrix, 38, 56, 69–70, 162
Trace of a matrix, 163, 317
Transform coding gain, 163

Transform efficiency, 163
Triangular matrices, 143

U
ULD

Factorization, 157
Structures, 158

ULU
Factorization, 155
Structures, 156

Unitarity property, 38
Unitary matrix, 318
Unit rectangular pulse, 22, 27
Unit vector, 145
Upper quasi-triangular matrices, 290

V
Vector addition, 305
Vector norms, 144

Euclidean or 2-norm, 145, 336
Maximum, 145
p–norms, 145

Vector space, 305
Complex, 306
Euclidean, 309
Real, 306

W
Walsh–Hadamard transform (WHT), 102
Weak norm, 62
Whole sample

Antisymmetric (WA), 45
Symmetric (WS), 45

WHT, 102

Z
Zero order Bessel function, 23, 29

Similer Documents