Discrete Cosine and Sine Transforms (eBook)

General Properties, Fast Algorithms and Integer Approximations

Vladimir Britanak, K. R Rao, Patrick C. Yip (Autoren)

eBook Download: EPUB | PDF

2010 | 1. Auflage
368 Seiten
Elsevier Science (Verlag)
978-0-08-046464-0 (ISBN)

Infos

The Discrete Cosine Transform (DCT) is used in many applications by the scientific, engineering and research communities and in data compression in particular. Fast algorithms and applications of the DCT Type II (DCT-II) have become the heart of many established international image/video coding standards. Since then other forms of the DCT and Discrete Sine Transform (DST) have been investigated in detail.

This new edition presents the complete set of DCT and DST discrete trigonometric transforms, including their definitions, general mathematical properties, and relations to the optimal Karhunen-Lo?ve transform (KLT), with the emphasis on fast algorithms (one-dimensional and two-dimensional) and integer approximations of DCTs and DSTs for their efficient implementations in the integer domain. DCTs and DSTs are real-valued transforms that map integer-valued signals to floating-point coefficients. To eliminate the floating-point operations, various methods of integer approximations have been proposed to construct and flexibly generate a family of integer DCT and DST transforms with arbitrary accuracy and performance. The integer DCTs/DSTs with low-cost and low-powered implementation can replace the corresponding real-valued transforms in wireless and satellite communication systems as well as portable computing applications.

The book is essentially a detailed excursion on orthogonal/orthonormal DCT and DST matrices, their matrix factorizations and integer aproximations.

It is hoped that the book will serve as a valuable reference for industry, academia and research institutes in developing integer DCTs and DSTs as well as an inspiration source for further advanced research.

Key Features
- Presentation of the complete set of DCTs and DSTs in context of entire class of discrete unitary sinusoidal transforms: the origin, definitions, general mathematical properties, mutual relationships and relations to the optimal Karhunen-Lo?ve transform (KLT).
- Unified treatment with the fast implementations of DCTs and DSTs: the fast rotation-based algorithms derived in the form of recursive sparse matrix factorizations of a transform matrix including one- and two-dimensional cases.
- Detailed presentation of various methods and design approaches to integer approximation of DCTs and DSTs utilizing the basic concepts of linear algebra, matrix theory and matrix computations leading to their efficient multiplierless real-time implementations, or in general reversible integer-to-integer implementations.
- Comprehensive list of additional references reflecting recent/latest developments in the efficient implementations of DCTs and DSTs mainly one-, two-, three- and multi-dimensional fast DCT/DST algorithms including the recent active research topics for the time period from 1990 up to now.

---

The Discrete Cosine Transform (DCT) is used in many applications by the scientific, engineering and research communities and in data compression in particular. Fast algorithms and applications of the DCT Type II (DCT-II) have become the heart of many established international image/video coding standards. Since then other forms of the DCT and Discrete Sine Transform (DST) have been investigated in detail. This new edition presents the complete set of DCT and DST discrete trigonometric transforms, including their definitions, general mathematical properties, and relations to the optimal Karhunen-Loeve transform (KLT), with the emphasis on fast algorithms (one-dimensional and two-dimensional) and integer approximations of DCTs and DSTs for their efficient implementations in the integer domain. DCTs and DSTs are real-valued transforms that map integer-valued signals to floating-point coefficients. To eliminate the floating-point operations, various methods of integer approximations have been proposed to construct and flexibly generate a family of integer DCT and DST transforms with arbitrary accuracy and performance. The integer DCTs/DSTs with low-cost and low-powered implementation can replace the corresponding real-valued transforms in wireless and satellite communication systems as well as portable computing applications. The book is essentially a detailed excursion on orthogonal/orthonormal DCT and DST matrices, their matrix factorizations and integer aproximations. It is hoped that the book will serve as a valuable reference for industry, academia and research institutes in developing integer DCTs and DSTs as well as an inspiration source for further advanced research. Presentation of the complete set of DCTs and DSTs in context of entire class of discrete unitary sinusoidal transforms: the origin, definitions, general mathematical properties, mutual relationships and relations to the optimal Karhunen-Loeve transform (KLT) Unified treatment with the fast implementations of DCTs and DSTs: the fast rotation-based algorithms derived in the form of recursive sparse matrix factorizations of a transform matrix including one- and two-dimensional cases Detailed presentation of various methods and design approaches to integer approximation of DCTs and DSTs utilizing the basic concepts of linear algebra, matrix theory and matrix computations leading to their efficient multiplierless real-time implementations, or in general reversible integer-to-integer implementations Comprehensive list of additional references reflecting recent/latest developments in the efficient implementations of DCTs and DSTs mainly one-, two-, three- and multi-dimensional fast DCT/DST algorithms including the recent active research topics for the time period from 1990 up to now

Inhalt

Front Cover 1
Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations 4
Copyright Page 5
Contents 6
Preface 10
Acknowledgments 12
List of Acronyms 14
1 Discrete Cosine and Sine Transforms 16
1.1 Introduction 16
1.2 Organization of the book 17
1.3 Appendices 18
1.4 References 18
1.5 Additional references 18
References 20
2 Definitions and General Properties 31
2.1 Introduction 31
2.2 The FCT 32
(a) Inversion 33
(b) Linearity 33
(c) Scaling in time 33
(d) Shift in time 34
(e) Shift in frequency 34
(f) Differentiation in time 35
(g) Differentiation in frequency 35
(h) Asymptotic behavior 35
(i) Integration in time 36
(j) Integration in frequency 36
(k) Convolution in time 36
2.3 Some examples of the FCT 37
(a) The unit rectangular pulse 37
(b) The inverse quadratic function 37
(c) The exponential function 37
(d) The sinc function 38
(e) The decaying sine function 38
(f) Bessel function of the first kind 38
2.4 The FST 38
(a) Inversion 39
(b) Linearity 39
(c) Scaling in time 39
(d) Shift in time 40
(e) Shift in frequency 40
(f) Differentiating in time 40
(g) Differentiating in frequency 41
(h) Asymptotic behavior 41
(i) Integration in time 41
(j) Integration in frequency 41
(k) Convolution in time 41
2.5 Some examples of the FST 42
(a) The unit rectangular pulse 42
(b) The inverse quadratic function 42
(c) The exponential function 43
(d) The sinc function 43
(e) The decaying sine function 43
(f) Bessel function of the first kind 44
2.6 The DCTs 44
2.7 The DSTs 50
2.8 Properties of the DCTs and DSTs 53
(a) The unitarity property 53
(b) The linearity property 56
(c) The scaling in time property 56
(d) The shift in time property 56
(e) The difference property 59
2.9 Convolution properties 59
2.10 Summary 63
Problems and Exercises 63
References 64
3 The Karhunen–Loéve Transform and Optimal Decorrelation 66
3.1 Introduction 66
3.2 The KLT 67
3.3 Asymptotic equivalence of DCT-I and DCT-II to KLT 71
3.3.1 DCT-I 71
3.3.2 DCT II 75
3.4 Asymptotic equivalence and generation of discrete unitary transforms 77
3.4.1 The Hilbert–Schmidt norms of a matrix 77
3.4.2 Nets, classes and sections 78
3.4.3 Spectral representations and asymptotic equivalence 79
3.4.4 Gaussian quadrature and generation of transforms 81
3.5 Summary 85
Problems and Exercises 85
References 86
4 Fast DCT/DST Algorithms 88
4.1 Introduction 88
4.2 Orthogonal/orthonormal DCT/DST matrices: definitions, properties and relations 89
4.3 The explicit forms of orthonormal DCT/DST matrices 92
4.4 The fast rotation-based DCT/DST algorithms 96
4.4.1 The fast DCT-I and SCT algorithms 97
4.4.2 The fast DST-I and SST algorithms 104
4.4.3 The fast DCT-II/DST-II and DCT-III/DST-III algorithms 111
4.4.4 The fast DCT-IV/DST-IV algorithms 126
4.5 Fast 2-D DCT/DST algorithms 134
4.5.1 Existing fast direct 2-D DCT-II algorithms 134
4.5.2 The optimal 1-D 8-point and 2-D 8 × 8 DCT-II algorithms 139
4.5.3 Kronecker sum and product of matrices 140
4.5.4 Generating direct 2-D DCT/DST algorithms by structural approach 141
4.6 Summary 147
Problems and Exercises 147
References 151
5 Integer Discrete Cosine/Sine Transforms 156
5.1 Introduction 156
5.2 Plane rotation matrices: factorizations and notations 157
5.2.1 The determinant 158
5.2.2 Orthogonal/orthonormal matrices 158
5.2.3 Triangular matrices and algebra of triangular matrices 158
5.2.4 Absolute value of a matrix and matrix/vector norms 159
5.2.5 Elementary rotation matrices 161
5.2.6 Elementary transformations 162
5.2.7 QR, LU, LDU and PLUS factorizations 163
5.2.8 Matrix factorizations of Givens–Jacobi rotations and Householder reflections 168
5.2.9 Evaluating the determinants of DCT/DST matrices 176
5.3 Criteria for evaluating of approximated DCTs/DSTs 177
5.3.1 Mean-square error 177
5.3.2 Transform coding gain 178
5.3.3 Transform efficiency 178
5.4 Methods for integer approximation of DCTs/DSTs 178
5.4.1 C-matrix transform 180
5.4.2 Integer cosine/sine transforms 186
5.4.3 Generalized Chen transform 214
5.4.4 BinDCT/BinDST and IntDCT/IntDST 229
5.5 Other methods and approaches 259
5.5.1 Lossless DCT 260
5.5.2 Invertible integer DCTs 278
5.5.3 Reversible DCTs 291
5.5.4 Signed DCT square wave transform 300
5.6 Late additions with comments 304
5.6.1 PL[sub(1)] U L[sub(2)] factorization of transform matrices 304
5.6.2 The normalized integer transforms 304
5.6.3 The MDL computational structure 305
5.7 Summary 308
Problems and Exercises 309
References 314
Appendix A 320
A.1 Vector spaces 320
Problems and Exercises A.1 328
A.2 The matrix eigenvalue problem 329
Problems and Exercises A.2 339
A.3 Matrix decompositions 340
Problems and Exercises A.3 351
A.4 Signal and its representations 352
Index 360
A 360
B 360
C 360
D 360
E 361
F 361
G 362
H 362
I 362
J 362
K 362
L 362
M 363
N 363
O 363
P 363
Q 363
R 363
S 363
T 364
U 364
V 364
W 364
Z 364

Produkt-Details

• Erscheint lt. Verlag: 28.7.2010
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Technik ► Bauwesen
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Wirtschaft
• ISBN-10: 0-08-046464-5 / 0080464645
• ISBN-13: 978-0-08-046464-0 / 9780080464640