Energy Packing Efficiency for the Generalized Discrete Transforms

The concept of energy packing efficiency (EPE) of the Walsh-Hadamard transform (WHT) first proposed by Kitajima [1], is extended to other discrete orthogonal transforms. The concept as a criterion for evaluating the transforms is discussed. It is shown that the EPE is invariant for the generalized transforms as long as the ordering is the same.     

Eigenvalues and eigenvectors of generalized DFT, generalized DHT,DCT-IV and DST-IV matrices

In this paper, the eigenvalues and eigenvectors of the generalized discrete Fourier transform (GDFT), the generalized discrete Hartley transform (GDHT), the type-IV discrete cosine transform (DCT-IV), and the type-IV discrete sine transform (DST-IV) matrices are investigated in a unified framework. First, the eigenvalues and their multiplicities of the GDFT matrix are determined, and the theory of commuting matrices is applied to find the real, symmetric, orthogonal eigenvectors set that constitutes the discrete counterpart of Hermite Gaussian function. Then, the results of the GDFT matrix and the relationships among these four unitary transforms are used to find the eigenproperties of the GDHT, DCT-IV, and DST-IV matrices. Finally, the fractional versions of these four transforms are defined, and an image watermarking scheme is proposed to demonstrate the effectiveness of fractional transforms     

Transform domain adaptive linear phase filter

Describes a new adaptive linear-phase filter whose weights are updated by the normalized least-mean-square (LMS) algorithm in the transform domain. This algorithm provides a faster convergence rate compared with the time domain linear phase LMS algorithm. Various real-valued orthogonal transforms are investigated such as the discrete cosine transform (DCT), discrete Hartley transform (DHT), and power of two (PO2) transform, etc. By using the symmetry property of the transform matrix, an efficient implementation structure is proposed. A system identification example is presented to demonstrate its performance     

基于离散Tchebichef变换的多聚焦图像融合方法

基于变换技术的图像融合是多聚焦图像融合中常采用的方法,其过程是将图像转换到变换域按照一定的融合规则进行融合后再反变换回来,具有较强的抗噪能力,融合效果明显。该文提出一种基于离散Tchebichef正交多项式变换的多聚焦图像融合方法,首次将离散正交多项式变换应用到多聚焦图像融合领域。该方法成功地利用了图像的空间频率与其离散Tchebichef正交多项式变换系数之间的关系,通过离散正交多项式变换系数直接得到空间频率值,避免了将离散多项式变换系数变换到空域计算的过程。所提方法节省了融合时间,并提高了融合效果。     

On the approximation of the discrete Karhunen-Loeve transform for stationary processes

Suboptimal fast transforms are useful substitutes to the optimal Karhunen-Loève transform (KLT). The selection of an efficient approximation for the KLT must be done with respect to some performance criterion that might differ from one application to another. A general class of criterion functions including most of the commonly used performance measures is introduced. They are shown to be optimized by the KLT. Various properties of the eigenvectors of the symmetric Toeplitz covariance matrix of a wide sense stationary process are reviewed. Several transforms such as the complex or real, odd and even Fourier transforms (DFT, DOFT, DREFT, DROFT), the cosine and even sine transforms (DCT, DEST) are obtained from the decomposition of a symmetric Toeplitz matrix in the sum of a circulant and a skew circulant matrix. These transforms are compared on the basis of a general performance criterion and appear to be good substitutes for the optimal KLT. Finally, it is shown that these transforms are asymptotically equivalent in performances to the KLT of an arbitrary wide sense stationary process.     

Parallel vector processing of multidimensional orthogonal transforms for digital signal processing applications

This paper presents vector and parallel algorithms and implementations of one- and two-dimensional orthogonal transforms. The speed performances are evaluated on Cray X-MP/48 vector computer. The sinusoidal orthogonal transforms are computed using fast real Fourier transform (FFT) kernel. The non-sinusoidal orthogonal transform algorithms are derived by using direct factorizations of transform matrices. Concurrent processing is achieved by using the multitasking capability of Cray X-MP/48 to transform long data vectors and two-dimensional data vectors. The discrete orthogonal transforms discussed in this paper include: Fourier transform (DFT), cosine transform (DCT), sine transform (DST), Hartley transform (DHT), Walsh transform (DWHT) and Hadamard transform (DHDT). The factors affecting the speedup of vector and parallel processing of these transforms are considered. The vectorization techniques are illustrated by an FFT example.This work is supported in part by the National Science Foundation, Pittsburgh Supercomputing Center (grant number ECS-880012P) and by the PEW Science Education Program.     

Image and video processing using discrete fractional transforms

The mathematical transforms such as Fourier transform, wavelet transform and fractional Fourier transform have long been influential mathematical tools in information processing. These transforms process signal from time to frequency domain or in joint time–frequency domain. In this paper, with the aim to review a concise and self-reliant course, the discrete fractional transforms have been comprehensively and systematically treated from the signal processing point of view. Beginning from the definitions of fractional transforms, discrete fractional Fourier transforms, discrete fractional Cosine transforms and discrete fractional Hartley transforms, the paper discusses their applications in image and video compression and encryption. The significant features of discrete fractional transforms benefit from their extra degree of freedom that is provided by fractional orders. Comparison of performance states that discrete fractional Fourier transform is superior in compression, while discrete fractional cosine transform is better in encryption of image and video. Mean square error and peak signal-to-noise ratio with optimum fractional order are considered quality check parameters in image and video.     

VQ-adaptive block transform coding of images

Two new design techniques for adaptive orthogonal block transforms based on vector quantization (VQ) codebooks are presented. Both techniques start from reference vectors that are adapted to the characteristics of the signal to be coded, while using different methods to create orthogonal bases. The resulting transforms represent a signal coding tool that stands between a pure VQ scheme on one extreme and signal-independent, fixed block transformation-like discrete cosine transform (DCT) on the other. The proposed technique has superior compaction performance as compared to DCT both in the rendition of details of the image and in the peak signal-to-noise ratio (PSNR) figures.     

A new prefilter design for discrete multiwavelet transforms

In conventional wavelet transforms, prefiltering is not necessary due to the lowpass property of a scaling function. This is no longer true for multiwavelet transforms. A few research papers on the design of prefilters have appeared, but the existing prefilters are usually not orthogonal, which often causes problems in coding. Moreover, the condition on the prefilters was imposed based on the first-step discrete multiwavelet decomposition. We propose a new prefilter design that combines the ideas of the conventional wavelet transforms and multiwavelet transforms. The prefilters are orthogonal but nonmaximally decimated. They are derived from a very natural calculation of multiwavelet transform coefficients. In this new prefilter design, multiple step discrete multiwavelet decomposition is taken into account. Our numerical examples (by taking care of the redundant prefiltering) indicate that the energy compaction ratio with the Geronimo-Hardin-Massopust (1994) 2 wavelet transform and our new prefiltering is better than the one with Daubechies D₄ wavelet transform     

Multichannel transforms for signal/image processing

This paper presents a novel approach to the Fourier analysis of multichannel time series. Orthogonal matrix functions are introduced and are used in the definition of multichannel Fourier series of continuous-time periodic multichannel functions. Orthogonal transforms are proposed for discrete-time multichannel signals as well. It is proven that the orthogonal matrix functions are related to unitary transforms (e.g., discrete Hartley transform (DHT), Walsh-Hadamard transform), which are used for single-channel signal transformations. The discrete-time one-dimensional multichannel transforms proposed in this paper are related to two-dimensional single-channel transforms, notably to the discrete Fourier transform (DFT) and to the DHT. Therefore, fast algorithms for their computation can be easily constructed. Simulations on the use of discrete multichannel transforms on color image compression have also been performed.     

2-D and 1-D multipaired transforms: frequency-time type wavelets

A concept of multipaired unitary transforms is introduced. These kinds of transforms reveal the mathematical structure of Fourier transforms and can be considered intermediate unitary transforms when transferring processed data from the original real space of signals to the complex or frequency space of their images. Considering paired transforms, we analyze simultaneously the splitting of the multidimensional Fourier transform as well as the presentation of the processed multidimensional signal in the form of the short one-dimensional (1-D) “signals”, that determine such splitting. The main properties of the orthogonal system of paired functions are described, and the matrix decompositions of the Fourier and Hadamard transforms via the paired transforms are given. The multiplicative complexity of the two-dimensional (2-D) 2^r×2^r-point discrete Fourier transform by the paired transforms is 4^r/2(r-7/3)+8/3-12 (r>3), which shows the maximum splitting of the 5-D Fourier transform into the number of the short 1-D Fourier transforms. The 2-D paired transforms are not separable and represent themselves as frequency-time type wavelets for which two parameters are united: frequency and time. The decomposition of the signal is performed in a way that is different from the traditional Haar system of functions     

The GenLOT: generalized linear-phase lapped orthogonal transform

The general factorization of a linear-phase paraunitary filter bank (LPPUFB) is revisited. From this new perspective, a class of lapped orthogonal transforms with extended overlap (generalized linear-phase lapped orthogonal transforms (GenLOTs)) is developed as a subclass of the general class of LPPUFB. In this formulation, the discrete cosine transform (DCT) is the order-1 GenLOT, the lapped orthogonal transform is the order-2 GenLOT, and so on, for any filter length that is an integer multiple of the block size. The GenLOTs are based on the DCT and have fast implementation algorithms. The implementation of GenLOTs is explained, including the method to process finite-length signals. The degrees of freedom in the design of GenLOTs are described, and design examples are presented along with image compression tests     

Infinity-Norm Rotation Transforms

A new general paradigm of dynamic-range-preserving one-to-one mapping-infinity-norm rotations, analogous to the general 2-norm rotations, are proposed in this paper. Analogous to the well-known discrete cosine transforms, the linear 2-norm rotation transforms which preserve the 2-norm of the rotated vectors, the proposed infinity-norm rotation transforms are piecewise linear transforms which preserve the infinity-norm of vectors. Besides the advantages of perfect reversibility, in-place calculation and dynamic range preservation, the infinity-norm rotation transforms also have good energy-compact ability, which is suitable for signal compression and analysis. It can be implemented by shear transforms based on the 2-D rotation factorization of similar orthogonal transform matrices, such as DCT matrices. The performance of the new transforms is illustrated with 2-D patterns and histograms. Its good performance in lossy and lossless image compression, compared with other integer reversible transforms, is demonstrated in the experiments.     

Approximation power of biorthogonal wavelet expansions

This paper looks at the effect of the number of vanishing moments on the approximation power of wavelet expansions. The Strang-Fix conditions imply that the error for an orthogonal wavelet approximation at scale a=2^-i globally decays as a^N, where N is the order of the transform. This is why, for a given number of scales, higher order wavelet transforms usually result in better signal approximations. We prove that this result carries over for the general biorthogonal case and that the rate of decay of the error is determined by the order properties of the synthesis scaling function alone. We also derive asymptotic error formulas and show that biorthogonal wavelet transforms are equivalent to their corresponding orthogonal projector as the scale goes to zero. These results strengthen Sweldens earlier analysis and confirm that the approximation power of biorthogonal and (semi-)orthogonal wavelet expansions is essentially the same. Finally, we compare the asymptotic performance of various wavelet transforms and briefly discuss the advantages of splines. We also indicate how the smoothness of the basis functions is beneficial in reducing the approximation error     

Automating the modeling and optimization of the performance ofsignal transforms

Fast implementations of discrete signal transforms, such as the discrete Fourier transform (DFT), the Walsh-Hadamard transform (WHT), and the discrete trigonometric transforms (DTTs), can be viewed as factorizations of their corresponding transformation matrices. A given signal transform can have many different factorizations, with each factorization represented by a unique but mathematically equivalent formula. When implemented in code, these formulas can have significantly different running times on the same processor, sometimes differing by an order of magnitude. Further, the optimal implementations on various processors are often different. Given this complexity, a crucial problem is automating the modeling and optimization of the performance of signal transform implementations. To enable computer modeling of signal processing performance, we have developed and analyzed more than 15 feature sets to describe formulas representing specific transforms. Using some of these features and a limited set of training data, we have successfully trained neural networks to learn to accurately predict performance of formulas with error rates less than 5%. In the direction of optimization, we have developed a new stochastic evolutionary algorithm known as STEER that finds fast implementations of a variety of signal transforms. STEER is able to optimize completely new transforms specified by a user. We present results that show that STEER can find discrete cosine transform formulas that are 10-20% faster than what a dynamic programming search finds     

Fast algorithms of multidimensional discrete nonseparable𝒦-wave transforms

Fast algorithms for a wide class of nonseparable n-dimensional (n-D) discrete unitary 𝒦 transforms (DKTs) are introduced. They need fewer 1-D DKTs than in the case of the classical radix-2 FFT-type approach. The method utilizes a decomposition of the n-D K transform into the product of a new n-D discrete Radon transform and of a set of parallel/independ 1-D K transforms. If the n-D K transform has a separable kernel (e.g., the case of the discrete Fourier transform), our approach leads to decrease of multiplicative complexity by the factor of n, compared with the classical row/column separable approach     

Discrete fractional Fourier transform based on orthogonalprojections

The continuous fractional Fourier transform (FRFT) performs a spectrum rotation of signal in the time-frequency plane, and it becomes an important tool for time-varying signal analysis. A discrete fractional Fourier transform has been developed by Santhanam and McClellan (see ibid., vol.42, p.994-98, 1996) but its results do not match those of the corresponding continuous fractional Fourier transforms. We propose a new discrete fractional Fourier transform (DFRFT). The new DFRFT has DFT Hermite eigenvectors and retains the eigenvalue-eigenfunction relation as a continous FRFT. To obtain DFT Hermite eigenvectors, two orthogonal projection methods are introduced. Thus, the new DFRFT will provide similar transform and rotational properties as those of continuous fractional Fourier transforms. Moreover, the relationship between FRFT and the proposed DFRFT has been established in the same way as the conventional DFT-to-continuous-Fourier transform     

Sinusoidal transforms in OFDM systems

A method for using sinusoidal transforms as an alternative to the discrete Fourier transform (DFT) for orthogonal frequency division multiplexing (OFDM) wireless transmission methods is presented. These transforms satisfy the cyclic convolution properties of the DFT when used with a symmetric extension. Analysis of interference in OFDM systems reveals that under certain channel conditions or modulation constellations, throughput is enhanced when using sinusoidal transforms rather than the DFT.     

The Generalized Transform

Generalized transforms for decomposing a signal in terms of discrete orthogonal transformation are developed. General relationships for factoring the transform matrices into a product of sparse matrices are derived. Efficient algorithms for fast computation of these transforms is a consequence of these sparse matrices. The flow graphs and hence the sequence of computations are identical for all the transforms with only the multipliers as the variables for the different transforms.     

Novel Reversible Integer Fourier Transform With Control Bits

This paper presents a novel concept of the reversible integer discrete Fourier transform (RiDFT) of order 2^r, r > 2, when the transform is split by the paired representation into a minimum set of short transforms, i.e., transforms of orders 2^k, k < r. By means of the paired transform the signal is represented as a set of short signals which carry the spectral information of the signal at specific and disjoint sets of frequencies. The paired transform-based fast Fourier transform (FFT) involves a few operations of multiplication that can be approximated by integer transforms. Examples of 1-point transforms with one control bit are described. Control bits allow us to invert such approximations. Two control bits are required to perform the 8-point RiDFT, and 12 (or even 8) bits for the 16-point RiDFT of real inputs. The proposed forward and inverse RiDFTs are fast, and the computational complexity of these transforms is comparative with the complexity of the FFT. The 8-point direct and inverse RiDFTs are described in detail.