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.     

Efficient algorithms for computing the 2-D hexagonal Fouriertransforms

In this paper, representations of the two-dimensional (2-D) signals are presented that reduce the computation of 2-D discrete hexagonal Fourier transforms (2-D DHFTs). The representations are based on the concept of the covering that reveals the mathematical structure of the transforms. Specifically, a set of unitary paired transforms is derived that splits the 2-D DHFT into a number of smaller one-dimensional (1-D) DFTs. Examples for the 8×4 and 16×8 hexagonal lattices are described in detail. The number of multiplications required for computing the 8×4- and 16×8-point DHFTs are equal 20 and 136, respectively. In the general N⩾8 case, the number of multiplications required to compute the 2N×N-point DHFT by the paired transforms equals N² (log N-1)+N     

An efficient Fourier method for 3-D radon inversion in exactcone-beam CT reconstruction

The radial derivative of the three-dimensional (3-D) radon transform of an object is an important intermediate result in many analytically exact cone-beam reconstruction algorithms. The authors briefly review Grangeat's (1991) approach for calculating radon derivative data from cone-beam projections and then present a new, efficient method for 3-D radon inversion, i.e., reconstruction of the image from the radial derivative of the 3-D radon transform, called direct Fourier inversion (DFI). The method is based directly on the 3-D Fourier slice theorem. From the 3-D radon derivative data, which is assumed to be sampled on a spherical grid, the 3-D Fourier transform of the object is calculated by performing fast Fourier transforms (FFTs) along radial lines in the radon space. Then, an interpolation is performed from the spherical to a Cartesian grid using a 3-D gridding step in the frequency domain. Finally, this 3-D Fourier transform is transformed back to the spatial domain via 3-D inverse FFT. The algorithm is computationally efficient with complexity in the order of N ³ log N. The authors have done reconstructions of simulated 3-D radon derivative data assuming sampling conditions and image quality requirements similar to those in medical computed tomography (CT)     

Algebraic signal processing theory: 2-D spatial hexagonal lattice.

We develop the framework for signal processing on a spatial, or undirected, 2-D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of z-transform, boundary conditions, filtering or convolution, spectrum, frequency response, and Fourier transform. In the finite case, the Fourier transform is called discrete triangle transform. Like the hexagonal lattice, this transform is nonseparable. The derivation of the framework makes it a natural extension of the algebraic signal processing theory that we recently introduced. Namely, we construct the proper signal models, given by polynomial algebras, bottom-up from a suitable definition of hexagonal space shifts using a procedure provided by the algebraic theory. These signal models, in turn, then provide all the basic signal processing concepts. The framework developed in this paper is related to Mersereau's early work on hexagonal lattices in the same way as the discrete cosine and sine transforms are related to the discrete Fourier transform-a fact that will be made rigorous in this paper.     

Multidimensional complex signals with single-orthant spectra

An extension of the notion of the analytical signal to multidimensional signals is presented. The real and imaginary parts of this signal are a linear combination of the original signal and of its complete and partial Hilbert transforms. Its Fourier image exists only in one orthant of the multidimensional frequency space. The orthant is a half-axis in one dimension, a quadrant in two dimensions, an octant in three dimensions, etc. A multidimensional complex signal makes it possible to introduce the definitions of instantaneous amplitude, instantaneous phase, and partial instantaneous complex frequencies (partial derivatives of the instantaneous phase) and to formulate a modulation theory of a multidimensional harmonic carrier. The 2-D equivalent of 1-D single-sideband modulation is defined and called single quadrant modulation. It is shown that the multidimensional complex signal with a signal orthant spectrum may be defined as a convolution of the real signal with the multidimensional complex delta distribution     

Fourier-based reconstruction for fully 3-D PET: optimization of interpolation parameters

Fourier-based approaches for three-dimensional (3-D) reconstruction are based on the relationship between the 3-D Fourier transform (FT) of the volume and the two-dimensional (2-D) FT of a parallel-ray projection of the volume. The critical step in the Fourier-based methods is the estimation of the samples of the 3-D transform of the image from the samples of the 2-D transforms of the projections on the planes through the origin of Fourier space, and vice versa for forward-projection (reprojection). The Fourier-based approaches have the potential for very fast reconstruction, but their straightforward implementation might lead to unsatisfactory results if careful attention is not paid to interpolation and weighting functions. In our previous work, we have investigated optimal interpolation parameters for the Fourier-based forward and back-projectors for iterative image reconstruction. The optimized interpolation kernels were shown to provide excellent quality comparable to the ideal sinc interpolator. This work presents an optimization of interpolation parameters of the 3-D direct Fourier method with Fourier reprojection (3D-FRP) for fully 3-D positron emission tomography (PET) data with incomplete oblique projections. The reprojection step is needed for the estimation (from an initial image) of the missing portions of the oblique data. In the 3D-FRP implementation, we use the gridding interpolation strategy, combined with proper weighting approaches in the transform and image domains. We have found that while the 3-D reprojection step requires similar optimal interpolation parameters as found in our previous studies on Fourier-based iterative approaches, the optimal interpolation parameters for the main 3D-FRP reconstruction stage are quite different. Our experimental results confirm that for the optimal interpolation parameters a very good image accuracy can be achieved even without any extra spectral oversampling, which is a common practice to decrease errors caused by interpolation in Fourier reconstruction.     

3-D vector radix algorithm for the 3-D new Mersenne numbertransform

Three-dimensional convolutions and correlations are used for three-dimensional image-processing applications. Their calculation involves extensive computation, which makes the use of fast transforms very advantageous. As the number of arithmetic operations is very large, the accumulation of rounding or truncation errors arising in the use of the fast Fourier and Hartley transforms tends to increase. Number theoretic transforms are calculated modulo an integer and hence they are not subject to these errors. Previously, a one-dimensional transform called the new Mersenne number transform (NMNT) was introduced and applied successfully to the calculation of 1-D convolutions/correlations. Unlike other Mersenne number transforms, the NMNT can handle long data sequences and has fast algorithms. In the paper, the 1-D definitions are first extended to the 3-D case in detail for use in 3-D image processing applications. The concept and derivation of the 3-D vector radix algorithm is then introduced for the fast calculation of the 3-D NMNT. The proposed algorithm is found to offer substantial savings over the row-column approach in terms of arithmetic operations. Examples are given showing the validity of both transform and algorithm     

An OFDM with 3-D signal mapper and 2-D IDFT modulator

In this letter, a novel orthogonal frequency division multiplexing (OFDM) is introduced. Here, a three-dimensional (3-D) signal mapper and two-dimensional (2-D) inverse discrete Fourier transform are used to allocate 3-D signals to OFDM subchannels and to modulate the signals, respectively. The minimum Euclidean distance of the 3-D mapper is much farther than that of the 2-D mapper if both mappers consisting of the same number of signal points are normalized to have the same average power. As a result, the proposed OFDM has significantly improved error performance when compared to the conventional one.     

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.     

Fast 2-D signal processing

Linear maps on a 2-D signal space are considered. Using recent results on fast linear transforms, several categories of fast-2-D maps are identified. The connections between fast processing and type of kernel separability are developed. Companion systolic architectures that efficiently realize the fast forms are discussed. The transfer functions of fast 2-D processors are analyzed and illustrated through examples     

2-D symmetry: theory and filter design applications

In this comprehensive review article, we present the theory of symmetry in two-dimensional (2-D) filter functions and in 2-D Fourier transforms. It is shown that when a filter frequency response possesses symmetry, the realization problem becomes relatively simple. Further, when the frequency response has no symmetry, there is a technique to decompose that frequency response into components each of which has the desired symmetry. This again reduces the complexity of two-dimensional filter design. A number of filter design examples are illustrated.     

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     

基于FTP的二维傅里叶变换的研究

傅里叶变换轮廓术(FTP)是三维物体形貌测量的重要方法,一维傅里叶变换可用于一般曲面相位解调,但对高频干扰和低频背景噪声敏感.连续应用一维傅里叶变换或反傅里叶变换可实现二维傅里叶变换,采用二维傅里叶变换,进行二维频谱分析,可用来分离和提取有用三维信息.具体实验验证表明,二维傅里叶变换能消除沿非栅线方向造成的灰度变化以及高频噪声,减小计算结果沿Y方向的波动,更好反映三维物体细节信息,提高相位解调的精度.     

An algorithm for calculation of the discrete cosine transform by paired transform

A new algorithm for splitting the one-dimensional (1-D) 2/sup r/-point discrete cosine transform (DCT) into a set of short 2/sup k/-point type-IV DCTs [k=1:(r-1)] is introduced. The splitting is performed by means of paired transformation that is defined by the paired representation of signals with respect to the cosine transform. A proposed method of calculating the 2/sup r/-point cosine transform requires 2/sup r-1/r multiplications and 2/sup r-1/(3r-2)+1 additions when r/spl ges/2.     

Algebraic Signal Processing Theory: Sampling for Infinite and Finite 1-D Space

We derive a signal processing framework, called space signal processing, that parallels time signal processing. As such, it comes in four versions (continuous/discrete, infinite/finite), each with its own notion of convolution and Fourier transform. As in time, these versions are connected by sampling theorems that we derive. In contrast to time, however, space signal processing is based on a different notion of shift, called space shift, which operates symmetrically. Our work rigorously connects known and novel concepts into a coherent framework; most importantly, it shows that the sixteen discrete cosine and sine transforms are the space equivalent of the discrete Fourier transform, and hence can be derived by sampling. The platform for our work is the algebraic signal processing theory, an axiomatic approach and generalization of linear signal processing that we recently introduced.     

Radix-2 × 2 × 2 algorithm for the 3-D discrete Hartleytransform

The discrete Hartley transform (DHT) has proved to be a valuable tool in digital signal/image processing and communications and has also attracted research interests in many multidimensional applications. Although many fast algorithms have been developed for the calculation of one- and two-dimensional (1-D and 2-D) DHT, the development of multidimensional algorithms in three and more dimensions is still unexplored and has not been given similar attention; hence, the multidimensional Hartley transform is usually calculated through the row-column approach. However, proper multidimensional algorithms can be more efficient than the row-column method and need to be developed. Therefore, it is the aim of this paper to introduce the concept and derivation of the three-dimensional (3-D) radix-2 × 2 × 2 algorithm for fast calculation of the 3-D discrete Hartley transform. The proposed algorithm is based on the principles of the divide-and-conquer approach applied directly in 3-D. It has a simple butterfly structure and has been found to offer significant savings in arithmetic operations compared with the row-column approach based on similar algorithms     

2—D Fourier Transform Method for Optical Measurement of 3—D Surface

A emthod of 2-D Fourier transform used in 3-D surface profilometry is proposed,analyzed and compared with 1-D Fourier transform method in theory and practical measuring result.It was proved that the 2-D Fourier transform method has more advantages over 1-D Fourier transform methodd in biggest crook-rate limits,accuracy and sensitivity of measuring.Styudy on measuring object surface details with large crook-rate changing accurately used new higher-power index low-pass filter of spatial frequency domain.A new method of automatic produced reference grating image and error-correcting is proposed.One undeform row of deform grating image is used to extend a complete reference grating image,and some error-correcting method is used to process the result to get accurate surface shape and the deflection of reference surface normal line deviated from the axle of camera.By this new method,one deform rectangle grating image is only used to get the 3-D shape accurately.     

A fast algorithm for the linear canonical transform

In recent years there has been a renewed interest in finding fast algorithms to compute accurately the linear canonical transform (LCT) of a given function. This is driven by the large number of applications of the LCT in optics and signal processing. The well-known integral transforms: Fourier, fractional Fourier, bilateral Laplace and Fresnel transforms are special cases of the LCT. In this paper we obtain an O(NlogN) algorithm to compute the LCT by using a chirp-FFT-chirp transformation yielded by a convergent quadrature formula for the fractional Fourier transform. This formula gives a unitary discrete LCT in closed form. In the case of the fractional Fourier transform the algorithm computes this transform for arbitrary complex values inside the unitary circle and not only at the boundary. This chirp-FFT-chirp transform approximates the ordinary Fourier transform more precisely than just the FFT, since it comes from a convergent procedure for non-periodic functions.     

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     

Ultrafast Analog Fourier Transform Using 2-D LC Lattice

We describe how a 2-D rectangular lattice of inductors and capacitors can serve as an analog Fourier transform device, generating an approximate discrete Fourier transform (DFT) of an arbitrary input vector of fixed length. The lattice displays diffractive and refractive effects and mimics the combined optical effects of a thin-slit aperture and lens. Diffraction theories in optics are usually derived for 3-D media, whereas our derivations proceed in 2-D. Analytical and numerical results show agreement between lattice output and the true DFT. Potentially, this lattice can be used for an extremely low latency and high throughput analog signal processing device. The lattice can be fabricated on-chip with frequency of operation of more than 10 GHz.