Some properties and fast algorithms of slant transform in image processing

A first order stationary Markov process model has been considered for image processing problems. A relative performance measure of unitary transforms to image data has been defined. It has been proved that the slant transform is superior to Walsh-Hadamard transform in this relative performance measure for positive correlation under the assumed model. A lower bound of relative performance has also been found. Furthermore, fast algorithms for computing diagonal elements of any slant transformed matrix have been presented. Finally, it has been shown how slant transform can be modified to improve the relative performance.     

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.     

Automatic generation of fast discrete signal transforms

This paper presents an algorithm that derives fast versions for a broad class of discrete signal transforms symbolically. The class includes but is not limited to the discrete Fourier and the discrete trigonometric transforms. This is achieved by finding fast sparse matrix factorizations for the matrix representations of these transforms. Unlike previous methods, the algorithm is entirely automatic and uses the defining matrix as its sole input. The sparse matrix factorization algorithm consists of two steps: first, the “symmetry” of the matrix is computed in the form of a pair of group representations; second, the representations are stepwise decomposed, giving rise to a sparse factorization of the original transform matrix. We have successfully demonstrated the method by computing automatically efficient transforms in several important cases: for the DFT, we obtain the Cooley-Tukey (1965) FFT; for a class of transforms including the DCT, type II, the number of arithmetic operations for our fast transforms is the same as for the best-known algorithms. Our approach provides new insights and interpretations for the structure of these signal transforms and the question of why fast algorithms exist. The sparse matrix factorization algorithm is implemented within the software package AREP     

Computationally efficient systolic architecture for computing the discrete Fourier transform

A new high-performance systolic architecture for calculating the discrete Fourier transform (DFT) is described which is based on two levels of transform factorization. One level uses an index remapping that converts the direct transform into structured sets of arithmetically simple four-point transforms. Another level adds a row/column decomposition of the DFT. The architecture supports transform lengths that are not powers of two or based on products of coprime numbers. Compared to previous systolic implementations, the architecture is computationally more efficient and uses less hardware. It provides low latency as well as high throughput, and can do both one- and two-dimensional DFTs. An automated computer-aided design tool was used to find latency and throughput optimal designs that matched the target field programmable gate array structure and functionality.     

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.     

Variable-block-size lapped transforms

A structure for implementing lapped transforms with time-varying block sizes that allows full orthogonality of the transient transforms is presented. The formulation is based on a factorization of the transfer matrix into orthogonal factors. Such an approach can be viewed as a sequence of stages with variable-block-size transforms separated by sample-shuffling (delay) stages. Details and design examples for a first-order system are presented     

离散子波提升算法研究及其性能分析

论文基于矩阵变换和变换矩阵级联分解的思想,提出一种新的多相矩阵表示形式,对离散子波提升算法的机理进行了完整的理论分析,对子波提升算法和子波变换双通道滤波实现的理想重构条件进行了等价性证明,并利用互补滤波器组的对偶性提出一利新的子波提升分解算法的级联矩阵分解形式,使提升算法的机理解释更加完善,然后基于文中提出的矩阵级联分解形式,以(2,2)双正交子波变换为例说明了离散子波提升分解算法的实现,并就算法的可逆性、运算量和原位实现等问题进行了简要讨论。     

Fast Block Center Weighted Hadamard Transform

Motivated by the Hadamard transforms and center weighted Hadamard transforms, a new class of block center weighted Hadamard transforms (BCWHT) are proposed, which weights the region of midspatial frequencies of the signal more than the Hadamard transform. Based on the Kronecker product, direct sum operations, the identity matrix and recursive relations, the proposed one and 2-D fast BCWHTs algorithms through sparse matrix factorization are simply obtained.     

Family of order-4 four-level orthogonal transforms

A family of order-4 four-level orthogonal transforms is derived using a novel concept called dyadic symmetry. The well known order-4 discrete cosine, sine, Haar and slant transforms are members of this family. Comparison among transforms within this family shows that all these well known transforms can be exchanged with other members of the family giving either improved performance or reduced computational requirements.     

Matrix factorizations for reversible integer mapping

Reversible integer mapping is essential for lossless source coding by transformation. A general matrix factorization theory for reversible integer mapping of invertible linear transforms is developed. Concepts of the integer factor and the elementary reversible matrix (ERM) for integer mapping are introduced, and two forms of ERM-triangular ERM (TERM) and single-row ERM (SERM)-are studied. We prove that there exist some approaches to factorize a matrix into TERMs or SERMs if the transform is invertible and in a finite-dimensional space. The advantages of the integer implementations of an invertible linear transform are (i) mapping integers to integers, (ii) perfect reconstruction, and (iii) in-place calculation. We find that besides a possible permutation matrix, the TERM factorization of an N-by-N nonsingular matrix has at most three TERMs, and its SERM factorization has at most N+1 SERMs. The elementary structure of ERM transforms is the ladder structure. An executable factorization algorithm is also presented. Then, the computational complexity is compared, and some optimization approaches are proposed. The error bounds of the integer implementations are estimated as well. Finally, three ERM factorization examples of DFT, DCT, and DWT are given     

Reversible Resampling of Integer Signals

Except some extremely special cases, signal resampling was generally considered to be irreversible because of strong attenuation of high frequencies after interpolation. In this paper, we prove that signal resampling based on polynomial interpolation can be reversible even for integer signals, i.e., the original signal can be reconstructed losslessly from the resampled data. By using matrix factorization, we also propose a reversible method for uniform shifted resampling and uniform scaled and shifted resampling. The new factorization yields three elementary integer-reversible matrices. The method is actually a new way to compute linear transforms and a lossless integer implementation of linear transforms with the factor matrices. It can be applied to integer signals by in-place integer-reversible computation, which needs no auxiliary memory to keep the original sample data for the transformation during the process or for “undo” recovery after the process. Some examples of low-order resampling solutions are also presented in this paper and our experiments show that the resampling error relative to the original signal is comparable to that of the traditional irreversible resampling.      

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     

New transform using the Mersenne numbers

Number theoretic transforms (NTTs) find applications in the calculation of convolutions and correlations. They can perform these calculations without introducing additional noise in the processing due to rounding or truncation. Among all NTTs, Fermat and Mersenne number transforms have been given particular attention. However, the main drawback of these transforms is the inconvenient word length for the Fermat number transforms, and lack of fast algorithms for the Mersenne number transforms. The authors aim to introduce a new real transform defined modulo Mersenne numbers with long transform length equal to a power of two. This is achieved by dropping the condition that α_ should be ±2 and using a new definition for NTTs that departs from the usual Fourier-like definition. The new transform is suitable for fast algorithms. It has the cyclic convolution property and hence can be applied to the calculation of convolutions and correlations. The transform is extended to the two-dimensional case and then generalised to the multidimensional case. Examples are given for the one-dimensional and two-dimensional cases     

A Truncation method for computing slant transforms withapplications to image processing

A truncation method for computing the slant transform is presented. The slant transform truncation (STT) algorithm uses the divide and conquer principle of hierarchical data structures to factorize coherent image data into sparse subregions. In one dimension with a data array of size N=2ⁿ, the truncation method takes a time between O(N) and O(Nlog₂N), degenerating to the performance of the fast slant transform (FST) method in its worst case. In two dimensions, for a data array of size N×N, the one-dimensional truncation method is applied to each row, then to each column of the array, to compute the transform in a time between O(N²) and O(N²log₂N). Coherence is a fundamental characteristic of digital images and so the truncation method is superior to the FST method when computing slant transforms of digital images. Experimental results are presented to justify this assertion     

提升多小波变换及其在图像编码中的应用

多小波是一种新的小波．他在理论上所表现出来的优势以及他在应用领域所具有的潜力．使其受到高度重视。在短短的几年时间内，他在图像处理方面的应用已取得了一定的成效。提升方法不仅是现存小波变换的一种快速算法．而且是构造新的小波变换的一种工具。根据提升方法和多小波变换的特点，介绍了一种实现多小波变换的提升方法．并把这种提升多小波变换应用于图像处理，结果表明有很好的效果。     

Results on the factorization of multidimensional matrices for paraunitary filterbanks over the complex field

This paper undertakes the study of multidimensional finite impulse response (FIR) filterbanks. One way to design a filterbank is to factorize its polyphase matrices in terms of elementary building blocks that are fully parameterized. Factorization of one-dimensional (1-D) paraunitary (PU) filterbanks has been successfully accomplished, but its generalization to the multidimensional case has been an open problem. In this paper, a complete factorization for multichannel, two-dimensional (2-D), FIR PU filterbanks is presented. This factorization is based on considering a two-variable FIR PU matrix as a polynomial in one variable whose coefficients are matrices with entries from the ring of polynomials in the other variable. This representation allows the polyphase matrix to be treated as a one-variable matrix polynomial. To perform the factorization, the definition of paraunitariness is generalized to the ring of polynomials. In addition, a new degree-one building block in the ring setting is defined. This results in a building block that generates all two-variable FIR PU matrices. A similar approach is taken for PU matrices with higher dimensions. However, only a first-level factorization is always possible in such cases. Further factorization depends on the structure of the factors obtained in the first level.     

一种新的基于提升多小波变换的图像融合方法

多小波是一种新的小波,它在理论上所表现出来的优势以及它在应用领域所具有的潜力,使其受到高度重视。在短短的几年时间内,它在图像处理方面的应用已取得了一定的成效。提升方法不仅是现存小波变换的一种快速算法,而且是构造新的小波变换的一种工具。本文根据提升方法和多小波变换的特点,对多小波实现了提升变换,并把这种基于提升方法的多小波变换应用于图像融合,结果表明有更好的效果。     

Fast decimation-in-time algorithms for a family of discrete sine and cosine transforms

Fast decimation-in-time (DIT) algorithms for the various discrete cosine transforms (DCT) and discrete sine transforms (DST) are systematically developed, based on a radix-2 factorization of the transformation matrix. The results indicate these to be attractive alternatives to existing algorithms in terms of computational complexity and structural simplicity.Supported, in part, by NSERC Grant #A3635.     

Symmetric delay factorization: generalized framework forparaunitary filter banks

The symmetric delay factorization (SDF) was introduced to synthesize linear-phase paraunitary filter banks (LPPUFBs) with uniform order (i.e., filter length equal to NM for arbitrary N) and real-valued coefficients. The SDF presents the advantage of decomposing the polyphase transfer matrix (PTM) into only orthogonal matrices, even at the boundary of finite-duration signals, simplifying significantly the design of time-bounded filter banks (TBFBs) or of time-varying filter banks (TVFBs). However, the symmetric delay factorization applies only to LPPUFBs. On the other hand, lattice structures, as well as finite-size lattice structures, are proposed for classes of nonlinear-phase paraunitary filter banks, as the modulated lapped transform (MLT) and the extended tapped transform (ELT). This paper describes a new minimal and complete symmetric delay factorization valid for a larger class of paraunitary filter banks, encompassing paraunitary cosine modulated filter banks, with nonlinear phase basis functions, as well as for a set of LPPUFBs including the linear-phase lapped orthogonal transforms (LOTs) and the generalized tapped orthogonal transforms (GenLOTs). The derivations for filter banks with even and odd numbers of channels are formulated in a unified form. This approach opens new perspectives in the design of time-varying filter banks used for image and video compression, especially in the framework of region or object-based coding     

一种新型基于提升算法的二维离散小波变换结构的实现

在提升算法原理分析的基础上，设计出一种采用提升算法的二维离散小波变换结构，改变了传统的提升算法先行后列的运算方式，将行列运算操作结合起来进行，这样，相比于传统结构，在基本不增加硬件单元的前提下，变换时间减小为原来的75％左右，提高了硬件效率。