An analytic model for quantized discrete transform error

Almost every method currently used in the technology of multimedia compression is based on and operates by some type of quantized discrete transform. Due to quantization, there is a difference between the data before and after such a transform usage that can be calculated simply as the (R)MSE (root-mean-square-error) of one to another. In this work, we model any such (R)MSE estimate as a function of the transform itself, which is assumed to be given by its square matrix, of the quantization given by an array of divisors and, finally, of the source data statistics, which are given by the data means and covariances. The model has been designed for one- and two-dimensional transforms and can be applied to any of them, including DCT (discrete cosine transform), DWT (discrete Walsh transform), DFT (discrete Fourier transform), and wavelets. Trial calculations performed for the DCT II, DCT I, biorthogonal DCT I, Haar and Walsh transforms show that the results are very close to those predicted by the model.     

A class of discrete orthogonal transforms

For a given N-periodic sequence, a class of log₂N discrete orthogonal transforms ranging from Walsh-Hadamard transform to discrete Fourier transform (DFT) is defined. The power spectra invariant to circular shift of the sampled data for these transforms are developed. Phase spectra, analogous to that of the DFT, for all the discrete transforms are defined and developed. Recursive relations for generating the transform matrices are developed. Generalized expressions for factoring these transform matrices are provided. Based on these matrix factors, efficient algorithms for fast computation of the transform coefficients are developed. By introducing a number of zeros as the elements in the transform matrices, a modified version of the transforms is developed. By using these modified matrices, the power and phase spectra can be computed efficiently. These transforms can be used in the general area of information processing.     

Systolic implementation of real-valued discrete transforms via algebraic integer quantization

In this paper, we propose a novel approach for computing real-valued discrete transforms such as the discrete cosine transform (DCT) and the discrete Hartley transform (DHT). The approach is based on the algebraic integer encoding scheme. With the aid of this scheme, an error-free representation of the cos, sin, and cas functions becomes possible. For further complexity reduction, two different approximation methods are presented. Furthermore, for the implementation of these algorithms, a fully pipelined systolic architecture with O(N) throughput is proposed.     

Blind separation of audio signals using trigonometric transforms and wavelet denoising

This paper deals with the problem of blind separation of audio signals from noisy mixtures. It proposes the application of a blind separation algorithm on the discrete cosine transform (DCT) or the discrete sine transform (DST) of the mixed signals, instead of performing the separation on the mixtures in the time domain. Wavelet denoising of the noisy mixtures is recommended in this paper as a preprocessing step for noise reduction. Both the DCT and the DST have an energy compaction property, which concentrates most of the signal energy in a few coefficients in the transform domain, leaving most of the transform domain coefficients close to zero. As a result, the separation is performed on a few coefficients in the transform domain. Another advantage of signal separation in transform domains is that the effect of noise on the signals in the transform domains is smaller than that in the time domain due to the averaging effect of the transform equations, especially when the separation algorithm is preceded by a wavelet denoising step. The simulation results confirm the superiority of transform domain separation to time domain separation and the importance of the wavelet denoising step.     

H.264标准中的变换和量化研究

新一代视频压缩H.264标准,不同于以往的离散余弦变换(DCT),它是基于4×4离散余弦变换和量化,其算法能通过整型变换整数精确地进行计算,避免了"逆变换误差".执行变换系数量化过程不需要进行除法运算,只进行加法和移位运算,从而极大的降低了计算的复杂程度.     

A proposed secure multiple watermarking technique based on DWT,DCT and SVD for application in medicine

Multimedia Tools and Applications - In this paper, an algorithm for multiple watermarking based on discrete wavelet transforms (DWT), discrete cosine transform (DCT) and singular value...     

Fast Fourier Transform on FCC and BCC Lattices with Outputs on FCC and BCC Lattices Respectively

In this paper, we show fast Fourier transform (FFT) algorithms for efficient, non-redundant evaluations of discrete Fourier transforms (DFTs) on face-centered cubic (FCC) and body-centered cubic (BCC) lattices such that the corresponding DFT outputs are on FCC and BCC lattices, respectively. Furthermore, for each of those FFTs, we deduce the structures of its spatial (frequency respectively) domains that are contained in the Voronoi cell centered at 0 with respect to the DFT (inverse DFT respectively) associated sublattice.     

扩频通信抗干扰中的局部离散余弦变换技术

提出一种新的基于局部离散余弦变换(Local discrete cosine transform，LDCT)的时频域干扰抑制方法。与传统的块变换(Discrete cosine transform，DCT)不同，LDCT基函数具有良好的时域能量集中特性，可迅速捕获信号中的时变成分，有效跟踪信号时频结构的变化，实现时频平面的任意时间分割。仿真结果表明，基于LDCT的时频域信号处理方法可有效地抑制各种脉冲型时变干扰，明显改善系统性能。     

图像压缩中的快速方向离散余弦变换

传统的二维DCT(discrete cosine transform)无法稀疏表示除水平或垂直方向以外的边缘,而具有强方向表示能力的方向预测离散余弦变换(directional prediction DCT,简称DPDCT)计算复杂度又过高.针对这些问题,提出了一种快速方向离散余弦变换(fast directional discrete cosine transform,简称FDDCT).该算法沿给定的方向模式进行变换,避免了DPDCT中的插值运算,可以快速、稀疏地表示图像中各向异性边缘信息.此外,FDDCT通过设计块边界提升,在进一步集中边缘能量的同时保证了算法的完全重构.实验结果表明,FDDCT计算复杂度不超过DCT的1.4倍;采用同样的编码方法,基于FDDCT的压缩图像与基于DCT以及DPDCT的压缩图像相比,峰值信噪比可提高0.4dB~1.6dB,而且边缘细节更加清晰、完整.     

A jointly optimal fractal/DCT compression scheme

In this paper a hybrid fractal and discrete cosine transform (DCT) coder is developed. Drawing on the ability of DCT to remove inter-pixel redundancies and on the ability of fractal transforms to capitalize on long-range correlations within the image, the hybrid coder performs an operationally optimal, in the rate-distortion sense, bit allocation among coding parameters. An orthogonal basis framework is used within which an image segmentation and a hybrid block-based transform are selected jointly. The selection of coefficients in the DCT component of the overall block transform is made a part of the optimization procedure. A Lagrangian multiplier approach is used to optimize the hybrid transform parameters together with the segmentation. Differential encoding of the DC coefficient is employed, with the scanning path based on a 3rd-order Hilbert curve. Simulation results show a significant improvement in quality with respect to the JPEG standard, an approach based on optimization of DCT basis vectors, as well as, the purely fractal techniques.     

Computationally efficient 2D beamspace matrix pencil method for direction of arrival estimation

In this paper, we propose a new 2-dimensional beamspace matrix pencil (2D BMP) method for direction of arrival (DOA) estimation of plane wave signals using a uniform rectangular array (URA). Based on some a priori information about DOA, the proposed method transforms the complex signal subspace in 2D matrix pencil (2D MP) method [Y. Hua, Estimating two-dimensional frequencies by matrix enhancement and matrix pencil, IEEE Trans. Signal Process. 40 (9) (1992) 2267–2280] into a real and reduced dimensional beamspace using the discrete Fourier transform (DFT) matrix transformation. Consequently, the computational complexity is reduced (several times) in comparison with 2D MP method. Computer simulations are provided to show that 2D BMP method gives comparable performance in terms of average mean square error of the estimated DOA with lesser floating point operations as compared to the existing (MP) methods.     

二维离散分数余弦变换的改进形式

将一维离散余弦变换的变换核扩展到二维分数形式,得到Pei形式的二维离散分数余弦变换。通过整数阶余弦变换的线性叠加构造一种改进形式的二维离散分数余弦变换,并基于特征值和特征向量理论,分析2种离散分数余弦变换的周期关系。数值仿真结果表明,2种形式可以达到相同的变换结果,适用于图像编码、数字水印等领域。     

Fast, prime factor, discrete Fourier transform algorithms over GF(2) for 8 ? m ? 10

In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2^m − 1 points over GF(2^m), for 8 ? m ? 10. These new transform techniques can be used to decode Reed-Solomon (RS) codes of block length 2^m − 1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results.     

基于TMS320DM642平台的4×4DCT变换的实现与优化

针对离散余弦变换算法(DCT)的特点,通过对TI公司TMS320DM642 DSP平台的软件优化试验数据进行分析,实现了4×4DCT快速变换算法的优化,得到了优化后4×4DCT快速变换算法的库函数,该库函数可应用于现有的视频标准,能有效提高视频编解码的效率.     

What's that deal with the DCT?

Discrete cosine transforms (DCTs) and discrete Fourier transforms (DFTs) are reviewed in order to determine why DCTs are more popular for image compression than the easier-to-compute DFTs. DCT-based image compression takes advantage of the fact that most images do not have much energy in the high-frequency coefficients. It is suggested that DCTs are more popular because fewer DCT coefficients than DFT coefficients are needed to get a good approximation to a typical signal, since the higher-frequency coefficients are small in magnitude and can be more crudely quantized than the low-frequency coefficients     

Comparison of transform coding techniques for two-dimensional arbitrarily shaped images

Envisioned advanced multimedia video services include arbitrarily shaped (AS) image segments as well as regular rectangular images. Image segments of the TV weather report produced by the chromo-key technique [1] and image segments produced by video analysis and image segmentation [2–4] are typical examples of AS image segments. This paper explores efficient intraframe transform coding techniques for general two-dimensional (2D) AS image segments, treating the traditional rectangular images as a special case. In particular, we focus on the transform coding of the partially defined image blocks along the boundary of the AS image segments. We recognize two different approaches — thebrute force transform coding approach and theshape-adaptive transform coding approach. The former fills the uncovered area with the optimal redundant data such that the resulting transform spectrum is compact. A simple but efficient mirror image extension technique is proposed. Once augmented into full image blocks, these boundary blocks can be processed by traditional block-based transform techniques like the popular discrete cosine transform (DCT). In the second approach, we change either the transform basis or the coefficient calculation process adaptively based on the shape of the AS image segment. We propose an efficientshape-projected problem formulation to reduce the dimension of the problem. Existing coding algorithms, such as the orthogonal transform by Gilge [5] and the iterative coding by Kaup and Aach [6], can be interpreted intuitively. We also propose a new adaptive transform based on the same principle as that used in deriving the DCT from the optimal Karhunen-Loeve transform (KLT). We analyze the tradeoff relationship between compression performance, computational complexity, and codec complexity for different coding schemes. Simulation results show that complicated algorithms (e.g., iterative, adaptive) can improve the quality by 5–10 dB at some computational or hardware cost. Alternatively, the simple mirror image extension technique improves the quality by 3–4 dB without any overheads. The contributions of this paper lie in efficient problem formulations, new transform coding techniques, and numerical tradeoff analyses.     

General methods for L/M-fold resizing of compressed images using lapped transforms

Two general methods are proposed for the arbitrary L/M-fold resizing of compressed images using lapped transforms. These methods provide general resizing frameworks in the transform domain. In order to analyse the image size conversion technique using lapped transforms, the impulse responses and frequency responses for the overall system are derived and analysed. This theoretical analysis shows that the image resizing in the lapped transform domain provides much better characteristics than the conventional image resizing in the discrete cosine transform (DCT) domain. Specifically, by using lapped transforms, the proposed method reduces the blocking effect to a very low level for images which are compressed at low bit rates, since two neighbouring DCT blocks are used in the conversion process, instead of processing each block independently.     

Discrete Fourier transform and H∞ approximation

It is shown that uniform rational approximation of nonrational transfer functions can always be obtained by means of the discrete Fourier transform (DFT) as long as such approximants exist. Based on this fact, it is permissible to apply the fast Fourier transform (FFT) algorithm in carrying out rational approximations without being apprehensive of convergence. The DFT is used to obtain traditional approximations for transfer functions of infinite-dimensional systems. Justification is provided for using the DFT in such approximations. It is established that whenever a stable transfer function can be approximated uniformly on the right half-plane by a rational function, its approximants can always be recognized by means of a DFT     

An algebraic method for synthesizing fast algorithms of discrete cosine transform of arbitrary size

An algebraic method for synthesizing fast algorithms of the discrete cosine transform (DCT) of arbitrary size is proposed. The method is based on the polynomial algebra $\mathbb{F}{{[x]} \mathord{\left/ {\vphantom {{[x]} {p(x)}}} \right. \kern-0em} {p(x)}}$ associated with the DCT. The fast DCT algorithm comes as a result of the step-by-step decomposition of this algebra. In turn, the decomposition requires step-by-step factorization of the polynomial p(x). This problem is solved using Galois??s theory, which allows finding all the subfields of the splitting field of the polynomial p(x) where p(x) can be factorized.     

Representation of the Fourier Transform by Fourier Series

The analysis of the mathematical structure of the integral Fourier transform shows that the transform can be split and represented by certain sets of frequencies as coefficients of Fourier series of periodic functions in the interval . In this paper we describe such periodic functions for the one- and two-dimensional Fourier transforms. The approximation of the inverse Fourier transform by periodic functions is described. The application of the new representation is considered for the discrete Fourier transform, when the transform is split into a set of short and separable 1-D transforms, and the discrete signal is represented as a set of short signals. Properties of such representation, which is called the paired representation, are considered and the basis paired functions are described. An effective application of new forms of representation of a two-dimensional image by splitting-signals is described for image enhancement. It is shown that by processing only one splitting-signal, one can achieve an enhancement that may exceed results of traditional methods of image enhancement.