Multidimensional Signal Reconstruction

Often in multidimensional signal processing, the need arises to decompose signals into different frequency bands, which after some processing has to be combined to reconstruct the original signal. This article defines the need for reconstruction, issues faced and some of the common available approaches for reconstructing multi-dimensional signals.
Motivation and Applications
In many signal processing applications, it is convenient to decompose a signal into a more suitable form for processing. For instance, in image transform coding, an image is commonly decomposed using a discrete cosine transform operation. This representation of an image may be more convenient for data rate reduction.
Analysis
The original signal is analysed by breaking down the signal into elementary components, that describes the characteristic properties of that signal.
Synthesis
If the elementary components of the signal are known, the reconstruction of the signal from these elementary components or construction of a reasonable approximation of the original signal can be a challenge.
Methods of Reconstruction
Perfect reconstruction is a process by which a signal is completely recovered after being separated into various frequency bands. This article describes three approaches that can be used for signal reconstruction. The process of analysis and synthesis can be performed by using a series of filters, known as Filter banks. Filters in a multidimensional filter bank represented by multivariate polynomials have common zeros that are different in nature from their 1-D counterparts. For perfect reconstruction, these filter banks are required to possess linear phase. The design, construction and implementation of these filter banks can be a challenge. The first two approaches explain different methods that can be used to construct these filter banks.
The third approach is a based on data acquisition. This approach leads to signal reconstruction with a decreased Mean Squared Error.
Multidimensional Linear Phase Filter Bank based on Lattice structure

In this approach, the filter banks are designed and implemented via lattice structure. A lattice structure is said to be minimal if it employs the smallest number of delays for the implementation. A minimal lattice structure provides the fastest response to input signals. The lattice structure for the linear phase filter bank would have a filter support <math>\Bbb N</math>(M£) where M is the decimation matrix, £ is a positive integer diagonal matrix, and <math>\Bbb N(N)</math> denotes the set of integer vectors in the fundamental parallelepiped of the matrix N. If £ is chosen to be non-integer positive diagonal matrix instead of only positive integer ones, the corresponding lattice structure would provide more choices of filter banks, offering better trade-off between filter support and filter performance. Such filter banks are called generalized-support linear phase perfect reconstruction filter banks.
The properties of the filter bank include perfect reconstruction, linear phase and causality. Different representative elements in <math>\Bbb N(M)</math> may play different roles for a Filter bank to have linear phase property, hence it is useful to partition <math>\Bbb N(M)</math> into different groups such that each group gathers the representative elements playing the same role. If b is defined as a decimal number of binary vector B, M(b) is called the sub decimation matrix of M, and s(b) the sub-parallelepiped. All the representative elements, i.e. the parallelepiped N (M), are partitioned into 2-dimensional sets, i.e. the sub-parallelepipeds s(b), b = 0,··· , 2M − 1. Hence, we have <math>\Bbb N</math>(M) = s(0) ∪ s(1) ∪ s(2) ∪ s(3). Hence, the filter bank has the perfect reconstruction and linear phase properties.

Advantages:
* This method provides filter bandwidth fast and robust implementation, as well as structural possession of desired properties such as linear phase and perfect reconstruction.
*The linear phase property prevents the phase distortion in the reconstructed image and video signals. The perfect reconstruction property gives lossless representation of signals.
*This provides a good choice of filter banks therefore offering better trade-off between filter support and filter performance.
*this method is fast-computable, VLSI-friendly, and hence can be valuable in fast real-time or low-cost, low-power signal processing applications.
Disadvantages:
*The filter bank is restricted to be critically-sampled.
*The analysis polyphase matrix has to be causal i.e. there cannot exist any negative delays.
Multidimensional Filter Bank Signal Reconstruction from Multichannel Acquisition using Sampling Matrix
Instead of taking all the data and applying multi-channel deconvolution, the collected data set is first reduced by an integer M x M uniform sampling matrix D which is applied to each channel.
If M is the dimension of signal, N is the number of channels, D an M × M sampling matrix with integer, and P is the sampling factor at each channel i.e. determinant of D, by polyphase decomposition, the analysis and synthesis parts can be represented by an N × P matrix H and P × N matrix G. The sampling factor has to be as large as possible, because it would give a minimum collected data set. A sufficient algorithm is to obtain maximal D and FIR synthesis matrix G
such that perfect reconstruction condition holds.

In 1-D signal is a scalar, a linear search on sampling factors can be performed. However, in Multidimentional case, there are infinitely many matrices with a given sampling factor which can be addressed using the Hermite normal form and the Smith normal form.
When the dimension of signal is greater than one, there are infinitely many sampling matrices with the same sampling rate P. Given an M × M nonsingular integer valued matrix D, there exists an M×M unimodular matrix K such that DK = H, the Hermite normal form which shows that there is only a finite number of representative sampling matrices for the given up to equivalence classes. Next, by applying the Smith normal form, an input is obtained to compute the analysis polyphase matrix. There are many algorithms for efficiently computing the Smith normal form. Thus, having a particular synthesis matrix, an optimal solution can be found for a given design criterion.
Advantages:
*Higher efficiency and compactness of storage and computation of the matrix compared to lattice structure.
Disadvantages:
*The analysis decomposition matrix H has to be a polynomial left invertible matrix.
Fast Sparse Reconstruction
Real world signals of interest are usually sparse or compressible on a specific basis, and consequently the emerging compressive sensing can be applied to recover sparse signals with fewer measurements than the requirement of Nyquist sampling, and hence compressive sensing can be used to reduce the cost of data acquisition. Most of the existing compressive sensing works involve 1D signals, vectors or 2D signals, matrices. However, signals often admit multidimensional structures, and usually each dimension has a particular meaning. For example, hyperspectral imaging sensors acquire 2D images, and the product data from a hyperspectral sensor are intrinsically stored in a multidimensional array, also known as a 'tensor'. Tensors can be converted into vectors, and the multidimensional compressed sensing problem can be recast as a standard 1-D case. Since multidimensional signals contain more information, they come with higher data acquisition cost.
However, instead of reconstructing the whole set of measurements at once, application of an initialization strategy like an iterative algorithm can be applied to dimensions not involved in the measurement process. At each iteration, if a reliable prediction can be made, a prediction error in the linear measurement domain can be calculated by subtracting this "predicted measurement" from the original measurement row. Adding the error to this predicted measurement provides a new estimate Since the new estimate is more accurate than the old one, the process can be repeated by estimating a new, more accurate prediction. If the prediction of the row is accurate enough, the prediction error is going to be more compressible than the original vector. As a consequence, for an equal number of measurements, the Signal reconstruction will yield lower a Mean Squared Error.
Advantages
*It can be applied to recover sparse signals with fewer measurements than the requirement of Nyquist sampling, and hence compressed sensing can be used to reduce the cost of data acquisition.
*This approach provides high performance and has many potential applications such as video restoration and storage and texture expression.
*It work well for sparse data even if in the heavy noisy case.
Disadvantages
*The construction of compressed sensing based hardware can be a great challenge.

Main Menu

See Also

Main Menu