1,720,992 research outputs found
Invertible integer DCT algorithms
No full textAbstractInteger DCTs have important applications in lossless coding. In this paper, an integer DCT of radix-2 length n is understood to be a nonlinear, (left-)invertible mapping which acts on Zn and approximates the classical discrete cosine transform (DCT) of length n. In image compression, the DCT of type II (DCT-II) is of special interest. In this paper we present a new approach to invertible integer DCT-II and integer DCT-IV. Our method is based on a factorization of the cosine matrices of types II and IV into products of sparse, orthogonal matrices. Up to some permutations, each matrix factor is a block-diagonal matrix with blocks being orthogonal matrices of order 2. Hence one has to construct only integer transforms of length 2. We factorize an orthogonal matrix of order 2 into three lifting matrices and work with lifting steps and rounding-off. This allows the construction of new integer DCT algorithms. We give uniform bounds for the worst case difference between the results of exact DCT and the corresponding integer DCT. Finally, we present some numerical experiments for the integer DCT-II of length 8 and for the 2-dimensional integer DCT-II of size 8×8
Cardinal Hermite Spline Interpolation with Shifted Nodes
No full textGeneralized cardinal Hermite spline interpolation is considered. A special case of this problem is the classical cardinal Hermite spline interpolation with shifted nodes. By means of a corresponding symbol new representations of the cardinal Hermite fundamental splines can be given. Furthermore, a new efficient algorithm for the computation of the cardinal Hermite spline interpolant is obtained, which is mainly based on fast Fourier transform. This algorithm is shown to be also applicable to computing the periodic Hermite spline interpolant. In both cases we only use necessary and sufficient conditions for the existence and uniqueness of the corresponding Hermite spline interpolant
Fast and numerically stable algorithms for discrete cosine transforms
No full textAbstractIn this paper, we derive fast and numerically stable algorithms for discrete cosine transforms (DCT) of radix-2 length which are based on real factorizations of the corresponding cosine matrices into products of sparse, (almost) orthogonal matrices of simple structure. These algorithms are completely recursive, are simple to implement and use only permutations, scaling with 2, butterfly operations, and plane rotations/rotation–reflections. Our algorithms have low arithmetic costs which compare with known fast DCT algorithms. Further, a detailed analysis of the roundoff errors for the presented DCT algorithms shows their excellent numerical stability which outperforms a real fast DCT algorithm based on polynomial arithmetic
Numerical stability of fast trigonometric and orthogonal wavelet transforms
No full textFast trigonometric transforms and periodic orthogonal wavelet transforms are essential tools for numerous practical applications. It is very important that fast algorithms work stable in a floating point arithmetic. This survey paper presents recent results on the worst case analysis of roundoff errors occurring in floating point computation of fast Fourier transforms, fast cosine transforms, and periodic orthogonal wavelet transforms. All these algorithms realize matrix-vector products with unitary matrices. The results are mainly based on a factorization of a unitary matrix into a product of sparse, almost unitary matrices. It is shown that under certain conditions fast trigonometric and periodic orthogonal wavelet transforms can be remarkably stable
- …
