多维DFT的多维多项式变换与离散W变换算法

本文首先通过引进一种序列的重排技术将m(m2) 维离散Fourier变换 (m-D DFT)转化为一系列的一维广义离散Fourier变换(GDFT)的多重和.然后引入一维离散W变换(DWT)以及多维多项式变换(MD-PT)计算该多重和以减少冗余的算术运算,从而得到了高效的多维DFT算法,该算法与常用的行-列DFT算法相比,乘法仅约为行-列法的1/2m,而加法仅约为行-列法的(2m+1)/4m.对于2维DFT的计算,本文方法同单纯的多项式变换方法相比,乘法与加法分别减少50%与40%左右.另外,本文算法计算结构简单,易于编程实现,通过数值实验验证了本文算法的高效性.     

New fast algorithm for multidimensional type-IV DCT

The authors first propose an index mapping such that the type-IV m-dimensional discrete cosine transform (m-D DCT-IV) is turned into a sum involving a number of (m-1)-dimensional discrete cosine transforms ((m-1)-D DCTs). Then a polynomial transform is used for implementing the sum. Based on symmetrical properties, a refined fast polynomial transform algorithm is proposed for computing the polynomial transform. Compared to the row-column m-D DCT-IV algorithm, the proposed algorithm achieves remarkable savings in arithmetic operations. More precisely, the numbers of multiplications and additions for m-dimensional DCT-IV are nearly 1/m and (2m+1)/3m times those of the row-column method, respectively     

An Efficient Algorithm for the Computation of the Multidimensional Discrete Fourier Transform

In this paper, we propose a new approach for computing multidimensional Cooley-Tukey FFT's that is suitable for implementation on a variety of multiprocessor architectures. Our algorithm is derived in this paper from a Cooley decimation-in-time algorithm by using an appropriate indexing process and the tensor product properties. It is proved that the number of multiplications necessary to compute our proposed algorithm is significantly reduced while the number of additions remains almost identical to that of conventional Multidimensional FFT's (MFFT). Comparison results show the powerful performance of the proposed MFFT algorithm against the row-column FFT transform when data dimension M is large. Furthermore, this algorithm, presented in a simple matrix form, will be much easier to implement in practice. Connections of the proposed approach with well-known DFT algorithms are included in this paper and many variations of the proposed algorithm are also pointed out.     

Multidimensional polynomial transform algorithm formultidimensional discrete W transform

The multidimensional (MD) polynomial transform is used to convert the MD W transform (MDDWT) into a series of one-dimensional (1-D) W transforms (DWTs). Thus, a new polynomial transform algorithm for the MDDWT is obtained. The algorithm needs no operations on complex data. The number of multiplications for computing an r-dimensional DWT is only 1 times that of the commonly used row-column method. The number of additions is also reduced considerably     

A fast algorithm for computing multidimensional DCT on certain small sizes

This paper presents a new algorithm for the fast computation of multidimensional (m-D) discrete cosine transform (DCT) with size N/sub 1//spl times/N/sub 2//spl times//spl middot//spl middot//spl middot//spl times/N/sub m/, where N/sub i/ is a power of 2 and N/sub i//spl les/256, by using the tensor product decomposition of the transform matrix. It is shown that the m-D DCT or inverse discrete cosine transform (IDCT) on these small sizes can be computed using only one-dimensional (1-D) DCTs and additions and shifts. If all the dimensional sizes are the same, the total number of multiplications required for the algorithm is only 1/m times of that required for the conventional row-column method. We also introduce approaches for computing scaled DCTs in which the number of multiplications is considerably reduced.     

Multidimensional systolic arrays for the implementation of discreteFourier transforms

This paper presents an efficient technique for using a multidimensional systolic array to perform the multidimensional discrete Fourier transform (DFT). Extensions of the multidimensional systolic array suitable for fast Fourier transform (FFT) computations such as the prime-factor computation or the 2ⁿ-point decomposed computation of the one-dimensional (1-D) discrete Fourier transform are also presented. The essence of our technique is to combine two distinct types of semisystolic arrays into one truly systolic array. The resulting systolic array accepts streams of input data (i.e., it does not require any preloading), and it produces output data streams at the boundary of the array. No networks for intermediate spectrum transposition between constituent transforms are required. The systolic array has regular processing elements that contain a complex multiplier accumulator and a few registers and multiplexers. Simple and regular connections are required between the PEs     

Odd-Factor Algorithms for Multidimensional Discrete W Transform

New fast algorithms are proposed for the multidimensional type-II, -III, and -IV discrete W transforms. Detailed procedures of decomposition are given for the twoand three-dimensionalWtransform based on the use of odd factors in the transforms sizes. The proposed algorithms have a regular computational structure, support various transform lengths, and can be easily extended to higher-dimensional computations.     

New polynomial transform algorithm for multidimensional DCT

A new algorithm for the type-II multidimensional discrete cosine transform (MD-DCT) is proposed. Based on the polynomial transform, the rD-DCT with size N₁×N₂×···×N _r, where N_i is a power of 2, can be converted into a series of one dimensional (1-D) discrete cosine transforms (DCTs). The algorithm achieves considerable savings on the number of operations compared with the row-column method. For example, the number of multiplications for computing an r-dimensional DCT is only 1/r times that needed by the row-column method, and the number of additions is also reduced. Compared with other known polynomial transform algorithms for MD-DCT and the most recently presented algorithm for MD-DCT, the proposed one uses about the same number of operations. However, advantages such as better computational structure and flexibility in the choice of dimensional sizes can be achieved     

Multidimensional chirp algorithms for computing Fourier transforms

Continuous versions of the multidimensional chirp algorithms compute the function G(y)=F(My), where F(y) is the Fourier transform of a function f(x) of a vector variable x and M is an invertible matrix. Discrete versions of the algorithms compute values of F over the lattice L(2)=ML(1 ) from values of f over a lattice L(1), where L(2) need not contain the lattice reciprocal to L(1). If M is symmetric, the algorithms are multidimensional versions of the Bluestein chirp algorithm, which employs two pointwise multiplication operations (PMOs) and one convolution operation (CO). The discrete version may be efficiently implemented using fast algorithms to compute the convolutions. If M is not symmetric, three modifications are required. First, the Fourier transform is factored as the product of two Fresnel transforms. Second, the matrix M is factored as M=AB, where A and B are symmetric matrices. Third, the Fresnel transforms are modified by the matrices A and B and each modified transform is factored into a product of two PMOs and one CO.     

Multidimensional incremental parsing for universal source coding

A multidimensional incremental parsing algorithm (MDIP) for multidimensional discrete sources, as a generalization of the Lempel-Ziv coding algorithm, is investigated. It consists of three essential component schemes, maximum decimation matching, hierarchical structure of multidimensional source coding, and dictionary augmentation. As a counterpart of the longest match search in the Lempel-Ziv algorithm, two classes of maximum decimation matching are studied. Also, an underlying behavior of the dictionary augmentation scheme for estimating the source statistics is examined. For an m-dimensional source, m augmentative patches are appended into the dictionary at each coding epoch, thus requiring the transmission of a substantial amount of information to the decoder. The property of the hierarchical structure of the source coding algorithm resolves this issue by successively incorporating lower dimensional coding procedures in the scheme. In regard to universal lossy source coders, we propose two distortion functions, the local average distortion and the local minimax distortion with a set of threshold levels for each source symbol. For performance evaluation, we implemented three image compression algorithms based upon the MDIP; one is lossless and the others are lossy. The lossless image compression algorithm does not perform better than the Lempel-Ziv-Welch coding, but experimentally shows efficiency in capturing the source structure. The two lossy image compression algorithms are implemented using the two distortion functions, respectively. The algorithm based on the local average distortion is efficient at minimizing the signal distortion, but the images by the one with the local minimax distortion have a good perceptual fidelity among other compression algorithms. Our insights inspire future research on feature extraction of multidimensional discrete sources.     

多级多维离散小波变换的快速提升计算

提升方法是计算离散小波变换的有效手段,它由一系列的提升步和拉伸变换组成.在计算多级和多维离散小波变换时,现有方法在每一次小波分解的过程中都做完整的提升步计算和拉伸变换计算.我们发现该方法存在运算过程的冗余,为此本文提出了一种称之为后拉伸变换的提升方法,基本思想是计算完所有的提升步后,再统一进行拉伸变换.它能减少离散小波变换的乘法运算量.例如,对图像与视频压缩中应用广泛的Daubechies 9/7小波,做一维5级分解时与现有方法相比,乘法运算减少20%,而二维5级分解时,乘法运算减少28%.     

Multidimensional, mapping-based complex wavelet transforms.

Although the discrete wavelet transform (DWT) is a powerful tool for signal and image processing, it has three serious disadvantages: shift sensitivity, poor directionality, and lack of phase information. To overcome these disadvantages, we introduce multidimensional, mapping-based, complex wavelet transforms that consist of a mapping onto a complex function space followed by a DWT of the complex mapping. Unlike other popular transforms that also mitigate DWT shortcomings, the decoupled implementation of our transforms has two important advantages. First, the controllable redundancy of the mapping stage offers a balance between degree of shift sensitivity and transform redundancy. This allows us to create a directional, nonredundant, complex wavelet transform with potential benefits for image coding systems. To the best of our knowledge, no other complex wavelet transform is simultaneously directional and nonredundant. The second advantage of our approach is the flexibility to use any DWT in the transform implementation. As an example, we exploit this flexibility to create the complex double-density DWT: a shift-insensitive, directional, complex wavelet transform with a low redundancy of (3M - 1)/(2M - 1) in M dimensions. No other transform achieves all these properties at a lower redundancy, to the best of our knowledge. By exploiting the advantages of our multidimensional, mapping-based complex wavelet transforms in seismic signal-processing applications, we have demonstrated state-of-the-art results.     

Combined polynomial transform and radix-q algorithm for MD discreteW transform

The type-II r-dimensional discrete W transform (rD-DWT-II) with size q^l1×q^l2 ×···×^lr q where q is an odd prime number, is converted into a series of one-dimensional (1-D) reduced DWT-IIs by using the multidimensional polynomial transform and an index permutation. Then, a radix-q algorithm and a cyclic convolution algorithm are presented for the computation of the 1-D reduced DWT-IIs. The new fast algorithm substantially reduces the overall computational complexity compared with the row-column method. Especially, the number of multiplications required by the proposed algorithm for computing an rD-DWT-II is only 1/r times that needed by the commonly used row-column method     

Multidimensional Random Process Synthesis and Simulation

In thepaper, wide-sense stationary M-D (multidimensional)random processes, defined by their power spectral densities,are synthesised and simulated by using as an approximation M-Dmultisine random processes consisting of a sum of M>-Dsine components with deterministic amplitudes and random phaseshifts. On the basis of the power spectral density function andphase shifts chosen with some well defined random propertiesthe finite discrete Fourier transform of the M-Dmultisine random process is synthesised. The corresponding M-Dmultisine random process approximation is simulated by performingan inverse M-D finite Fourier transform of the synthesisedspectrum. Realisations of the synthesised and simulated randomprocess approximations may be obtained by using an M-Dfast Fourier transform algorithm. The properties of synthesisedM-D multisine random processes are discussed includingM-D white multisine random process.     

On Interframe Transform Coding

This paper is concerned with interframe coding of monochrome pictures using 3-dimensional transforms. First, an algorithm which enables the vector processing of 3-dimensional arrays is derived. Next, this algorithm is used in an interframe transform coding experiment. Picture data (6 bits/pel) is processed in (4 times 4 times 4) blocks using the Walsh-Hadamard transform (WHT), and the discrete cosine transform (DCT). The corresponding reconstructed pictures (1 bit/pel) are included.     

A Hybrid Compression Method for Integral Images Using Discrete Wavelet Transform and Discrete Cosine Transform

Integral imaging (II) is a promising three-dimensional (3-D) imaging technique that uses an array of diffractive or refractive optical elements to record the 3-D information on a conventional digital sensor. With II, the object information is recorded in the form of an array of subimages, each representing a slightly different perspective of the object In order to obtain high-quality 3-D images, digital sensors with a large number of pixels are required. Consequently, high-quality II involves recording and processing large amounts of data. In this paper, we present a compression method developed for the particular characteristics of the digitally recorded integral image. The compression algorithm is based on a hybrid technique implementing a four-dimensional transform combining the discrete wavelet transform and the discrete cosine transform. The proposed algorithm outperforms the baseline JPEG compression scheme applied to II and a previous compression method developed for II based on MPEG II.     

Multidimensional multirate filters and filter banks derived fromone-dimensional filters

A method by which every multidimensional (M-D) filter with an arbitrary parallelepiped-shaped passband support can be designed and implemented efficiently is presented. It is shown that all such filters can be designed starting from an appropriate one-dimensional prototype filter and performing a simple transformation. With D denoting the number of dimensions, the complexity of design and implementation of the M-D filter are reduced from O(N^D) to O(N). Using the polyphase technique, an implementation with complexity of only 2N is obtained in the two-dimensional. Even though the filters designed are in general nonseparable, they have separable polyphase components. One special application of this method is in M-D multirate signal processing, where filters with parallelepiped-shaped passbands are used in decimation, interpolation, and filter banks. Some generalizations and other applications of this approach, including M-D uniform discrete Fourier transform (DFT) quadrature mirror filter banks that achieve perfect reconstruction, are studied. Several design example are given     

Multidimensional fast-Fourier-transform algorithm

A multidimensional fast-Fourier-transform algorithm is developed for the computation of multidimensional Fourier and Fourier-like discrete transforms; it has considerably less multiplications than the conventional fast-Fourier-transform methods.     

Transform methods for seismic data compression

The authors consider the development and evaluation of transform coding algorithms for the storage of seismic signals. Transform coding algorithms are developed using the discrete Fourier transform (DFT), the discrete cosine transform (DCT), the Walsh-Hadamard transform (WHT), and the Karhunen-Loeve transform (KLT). These are evaluated and compared to a linear predictive coding algorithm for data rates ranging from 150 to 550 bit/s. The results reveal that sinusoidal transforms are well-suited for robust, low-rate seismic signal representation. In particular, it is shown that a DCT coding scheme reproduces faithfully the seismic waveform at approximately one-third of the original rate     

A Fast Computational Algorithm for the Discrete Sine Transform

A sparse-matrix factorization is developed for the discrete sine transform (DST). This factorization has a recursive structure and leads directly to an efficient algorithm for implementing the DST, a feature most desirable and very similar ot that of the DCT. This algorithm requires fewer arithmetic operations compared to that for the discrete cosine transform (DCT).