Nonuniform sampling and antialiasing in image representation

A unified approach to the representation and processing of a class of images which are not bandlimited but belong to the space of locally bandlimited signals is presented. A nonuniform sampling theorem (Clark et al, 1985) for functions belonging to this space is extended, and a class of nonstationary stochastic processes is considered. The space of locally bandlimited signals is shown to be a reproducing-kernel space. A generalized projection theorem can therefore be applied, yielding either a continuous or a discrete projection filter. The former can be used for image conditioning prior to nonuniform sampling, while the latter provides a general tool for image representation by nonuniform sampling schemes. The problem of finding the local bandwidth of a given signal, in order to generate an optimal sampling scheme, is addressed in the context of signal representation in the combined position-frequency space. The stochastic estimation of parameters which characterize the local bandwidth is discussed. Bounds on the error resulting from the utilization of nonexact position-varying signal parameters are derived     

A unified approach to optimal image interpolation problems based onlinear partial differential equation models

The unified approach to optimal image interpolation problems presented provides a constructive procedure for finding explicit and closed-form optimal solutions to image interpolation problems when the type of interpolation can be either spatial or temporal-spatial. The unknown image is reconstructed from a finite set of sampled data in such a way that a mean-square error is minimized by first expressing the solution in terms of the reproducing kernel of a related Hilbert space, and then constructing this kernel using the fundamental solution of an induced linear partial differential equation, or the Green's function of the corresponding self-adjoint operator. It is proved that in most cases, closed-form fundamental solutions (or Green's functions) for the corresponding linear partial differential operators can be found in the general image reconstruction problem described by a first- or second-order linear partial differential operator. An efficient method for obtaining the corresponding closed-form fundamental solutions (or Green's functions) of the operators is presented. A computer simulation demonstrates the reconstruction procedure.     

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.     

Consistent Sampling and Signal Recovery

An attractive formulation of the sampling problem is based on the principle of a consistent signal reconstruction. The requirement is that the reconstructed signal is indistinguishable from the input in the sense that it yields the exact same measurements. Such a system can be interpreted as an oblique projection onto a given reconstruction space. The standard formulation requires a one-to-one relationship between the input measurements and the reconstructed model. Unfortunately, this condition fails when the cross-correlation matrix between the analysis and reconstruction basis functions is not invertible; in particular, when there are less measurements than the number of reconstruction functions. In this paper, we propose an extension of consistent sampling that is applicable to those singular cases as well, and that yields a unique and well-defined solution. This solution also makes use of projection operators and has a geometric interpretation. The key idea is to exclude the null space of the sampling operator from the reconstruction space and to enforce consistency on its complement. We specify a class of consistent reconstruction algorithms corresponding to different choices of complementary reconstruction spaces. The formulation includes the Moore-Penrose generalized inverse, as well as other potentially more interesting reconstructions that preserve certain preferential signals. In particular, we display solutions that preserve polynomials or sinusoids, and therefore perform well in practical applications.     

On the Role of Exponential Splines in Image Interpolation

A Sobolev reproducing-kernel Hilbert space approach to image interpolation is introduced. The underlying kernels are exponential functions and are related to stochastic autoregressive image modeling. The corresponding image interpolants can be implemented effectively using compactly-supported exponential B-splines. A tight l₂ upper-bound on the interpolation error is then derived, suggesting that the proposed exponential functions are optimal in this regard. Experimental results indicate that the proposed interpolation approach with properly-tuned, signal-dependent weights outperforms currently available polynomial B-spline models of comparable order. Furthermore, a unified approach to image interpolation by ideal and nonideal sampling procedures is derived, suggesting that the proposed exponential kernels may have a significant role in image modeling as well. Our conclusion is that the proposed Sobolev-based approach could be instrumental and a preferred alternative in many interpolation tasks.     

采样理论中的正交变换问题

采样理论是信号处理教学的重要内容,从信号空间及投影角度出发,论证了 采样定理与傅里叶变换类似,都属于信号的正交变换过程,基于信号先验知识、采用不同内插函数的模数转换扩展了采样理论的应用范围,有助于加深对采样理论抽象概念的理解与掌握。     

New sampling scheme for region-of-interest tomography

The wavelet localization technique was previously applied to the study of region-of-interest (ROI) tomography. It achieves a significant saving in the required projections if only a small region of a tomographic image is of interest. In this paper, we first show that with the same sampling scheme, a simple interpolation applied to the samples can give a result at least as good as that using the original wavelet localization approach. It implies that the use of the wavelet transform is not the key to the reduction of the sampling requirement. In fact, the quality of the reconstructed ROI is largely determined by the structure of the sampling scheme. Rather than directly reducing the projection number, the use of the wavelet theory permits a clear understanding of how to achieve a good sampling pattern. Based on an error analysis using the wavelet theory, we further suggest a new sampling scheme such that the number of required projections in each angle is reduced in a multiresolution form. A new multiresolution interpolation algorithm is then used to interpolate the missing samples to obtain the full projections. As a result, more than 84% of projections are saved, as compared with the traditional approach, in reconstructing an ROI of 32×32 pixels in an image of 256×256 pixels. A series of simulations was performed to reconstruct different sizes of the ROI. All results show that the signal-to-error ratios of the reconstructed ROI are comparable with that using full projection data set     

A moment-based variational approach to tomographic reconstruction

We describe a variational framework for the tomographic reconstruction of an image from the maximum likelihood (ML) estimates of its orthogonal moments. We show how these estimated moments and their (correlated) error statistics can be computed directly, and in a linear fashion from given noisy and possibly sparse projection data. Moreover, thanks to the consistency properties of the Radon transform, this two-step approach (moment estimation followed by image reconstruction) can be viewed as a statistically optimal procedure. Furthermore, by focusing on the important role played by the moments of projection data, we immediately see the close connection between tomographic reconstruction of nonnegative valued images and the problem of nonparametric estimation of probability densities given estimates of their moments. Taking advantage of this connection, our proposed variational algorithm is based on the minimization of a cost functional composed of a term measuring the divergence between a given prior estimate of the image and the current estimate of the image and a second quadratic term based on the error incurred in the estimation of the moments of the underlying image from the noisy projection data. We show that an iterative refinement of this algorithm leads to a practical algorithm for the solution of the highly complex equality constrained divergence minimization problem. We show that this iterative refinement results in superior reconstructions of images from very noisy data as compared with the classical filtered back-projection (FBP) algorithm.     

Polyphase antialiasing in resampling of images.

Changing resolution of images is a common operation. It is also common to use simple, i.e., small, interpolation kernels satisfying some "smoothness" qualities that are determined in the spatial domain. Typical applications use linear interpolation or piecewise cubic interpolation. These are popular since the interpolation kernels are small and the results are acceptable. However, since the interpolation kernel, i.e., impulse response, has a finite and small length, the frequency domain characteristics are not good. Therefore, when we enlarge the image by a rational factor of (L/M), two effects usually appear and cause a noticeable degradation in the quality of the image. The first is jagged edges and the second is low-frequency modulation of high-frequency components, such as sampling noise. Both effects result from aliasing. Enlarging an image by a factor of (L/M) is represented by first interpolating the image on a grid L times finer than the original sampling grid, and then resampling it every M grid points. While the usual treatment of the aliasing created by the resampling operation is aimed toward improving the interpolation filter in the frequency domain, this paper suggests reducing the aliasing effects using a polyphase representation of the interpolation process and treating the polyphase filters separately. The suggested procedure is simple. A considerable reduction in the aliasing effects is obtained for a small interpolation kernel size. We discuss separable interpolation and so the analysis is conducted for the one-dimensional case.     

Sampling-50 years after Shannon

This paper presents an account of the current state of sampling, 50 years after Shannon's formulation of the sampling theorem. The emphasis is on regular sampling, where the grid is uniform. This topic has benefitted from a strong research revival during the past few years, thanks in part to the mathematical connections that were made with wavelet theory. To introduce the reader to the modern, Hilbert-space formulation, we reinterpret Shannon's sampling procedure as an orthogonal projection onto the subspace of band-limited functions. We then extend the standard sampling paradigm for a presentation of functions in the more general class of “shift-in-variant” function spaces, including splines and wavelets. Practically, this allows for simpler-and possibly more realistic-interpolation models, which can be used in conjunction with a much wider class of (anti-aliasing) prefilters that are not necessarily ideal low-pass. We summarize and discuss the results available for the determination of the approximation error and of the sampling rate when the input of the system is essentially arbitrary; e.g., nonbandlimited. We also review variations of sampling that can be understood from the same unifying perspective. These include wavelets, multiwavelets, Papoulis generalized sampling, finite elements, and frames. Irregular sampling and radial basis functions are briefly mentioned     

结合字典稀疏表示和非局部相似性的自适应压缩成像算法

如何以较少的观测值重构出高质量的图像是压缩成像系统的一个关键问题.本文根据图像块随机投影能量大小分布特点,提出了一种新的自适应采样方式以及针对自适应采样的有效重构算法.重构时利用了图像在字典下的稀疏表示原理和图像的非局部相似性先验知识.为实现图像的稀疏表示,文中构造了由多个方向字典和一个正交DCT字典组成的冗余字典,并用l1范数作为约束条件求解稀疏优化问题.由于充分利用了图像块的局部特性和图像的非局部特性,本文的压缩成像算法在低采样率下能重构出较高质量的图像.     

Continuous sampling in mutual-information registration.

Mutual information is a popular and widely used metric in retrospective image registration. This metric excels especially with multimodal data due to the minimal assumptions about the correspondence between the image intensities. In certain situations, the mutual-information metric is known to produce artifacts that rule out subsample registration accuracy. Various methods have been developed to mitigate these artifacts, including higher order kernels for smoother sampling of the metric. This study introduces a novel concept of continuous sampling to provide new insight into the mutual-information methods currently in use. In particular, the connection between the partial volume interpolation and the recently introduced higher order partial-volume-type kernels is revealed.     

Multiwavelet moments and projection prefilters

An efficient projection procedure is derived for use of orthogonal multiwavelets in the analysis of discrete data sequences. A family of simple prefilters corresponding to numerical quadrature evaluation of the projection integrals provides exact results for locally polynomial data. The full approximation order of the multiwavelet basis can thus always be enabled. For nonpolynomial signals, the prefilters provide approximations to the coefficients of the multiwavelet series whose convergence accelerates quickly with increase in sampling rate. Comparison is also made with previous time-invariant multiwavelet prefilters     

Genetic algorithms for a robust 3-D MR-CT registration

Presents an original usage of genetic algorithms as a robust search space sampler in an application to 3D medical image elastic registration. An overview of the standard steps of a registration algorithm is given. We focus on the genetic algorithm use, and particularly on the problem of extracting the optimal solution among the final genetic population. We provide an original encoding scheme relying on a structural approach of point matching and then point out the need for a local optimization process. We then illustrate the algorithm with a concrete registration example and assert the results with a direct multi-volume rendering tool. Finally, the algorithm is applied to the Vanderbilt medical image database to assert its robustness and in order to compare it with other techniques     

An optimum interpolation method applied to the resampling of NOAAAVHRR data

Two main problems must be solved in the geometric processing of satellite data: geometric registration and resampling. When the data must be geometrically registered over a reference map, and particularly when the output pixel size is not the same as the original pixel size, the quality of the resampling can determine the quality of the output, not only in the visual appearance of the image, but also in the numerically interpolated values when used in multitemporal or multisensor studies. The “optimum” interpolation algorithm for AVHRR data is defined over a 6×6 window in order to: consider overlapping effects among adjacent pixels. The response for each new pixel R(x, y) is determined as a linear combination of the response R _i(x_iy_i) of the surrounding pixels in the window (i=1,36). The weighting coefficients μ_i are calculated from the ground projection of the effective spatial response function for each AVHRR pixel, taking into account the particular viewing angle and geometry of the pixels on the ground. This method is intended to give an optimal interpolation of AVHRR scenes along all the scanline, in order to compensate for off-nadir radiometric alterations associated to the varying spatial resolution and the blurring introduced by the pixel overlaps. The optimum method, as mathematically defined, is highly expensive in CPU time. Then, a big effort is necessary to implement the algorithms so that they could be operationally applied. Two approaches are considered: a general numerical method and a pseudo-analytical approximation. A Landsat TM image corresponding to the same date of the AVHRR image is used to test the quality of the radiometric interpolation procedure     

Reconstruction of nonuniformly sampled images in spline spaces.

This paper presents a novel approach to the reconstruction of images from nonuniformly spaced samples. This problem is often encountered in digital image processing applications. Nonrecursive video coding with motion compensation, spatiotemporal interpolation of video sequences, and generation of new views in multicamera systems are three possible applications. We propose a new reconstruction algorithm based on a spline model for images. We use regularization, since this is an ill-posed inverse problem. We minimize a cost function composed of two terms: one related to the approximation error and the other related to the smoothness of the modeling function. All the processing is carried out in the space of spline coefficients; this space is discrete, although the problem itself is of a continuous nature. The coefficients of regularization and approximation filters are computed exactly by using the explicit expressions of B-spline functions in the time domain. The regularization is carried out locally, while the computation of the regularization factor accounts for the structure of the nonuniform sampling grid. The linear system of equations obtained is solved iteratively. Our results show a very good performance in motion-compensated interpolation applications.     

Projection space iteration reconstruction-reprojection

Recently, an iterative reconstruction-reprojection (IRR) algorithm has been suggested for application to limited view computed tomography (CT). In the IRR, the interpolation operation is performed in the object space during backprojection-reprojection. The errors associated with the interpolation degrade the reconstructed image and may cause divergence unless a large number of rays is used. In this paper, we propose a projection space iterative reconstruction-reprojection (PSIRR) algorithm based on backprojection-reprojection in the projection space. In the process of the backprojection-reprojection, iteration is performed with a single equation instead of multiple equations and interpolation is eliminated. Computer simulation results are presented, and image quality of the PSIRR algorithm shows a substantial improvement compared to the original IRR algorithm. In addition, the new algorithm was applied to ultrasonic attenuation CT using a sponge phantom.     

一种适合低信噪比投影栅的时空二维相移算法

提出了一种适合低信噪比投影栅的时空二维相移算法。首先设计四步相移正弦光栅条纹图,由DLP投影仪投影到待测物体表面,再由CCD相机采集受物体形貌调制的变形条纹图;然后对其中一幅变形条纹图进行傅里叶变换以确定抽样间隔,再对4幅相移条纹图用相移法求得条纹背景和调制幅度后,对每幅变形条纹图做归一化处理;对每幅相移条纹图在空间域进行下采样抽样和灰度插值,构建相移莫尔条纹图,得到多帧时空域相移条纹图;对多帧时空域相移条纹图按时空二维相移法处理求得莫尔相位,再将莫尔相位与抽样点相位叠加求和得到变形条纹图对应的相位数据;最后,以面膜作为样品进行了实验测量,结果表明,经典四步相移法重构的物体形貌出现明显失真,而本文方法能较好恢复物体的三维形貌。     

Projection based prefiltering for multiwavelet transforms

We introduce a method for initializing the multiwavelet decomposition algorithm. The initialization procedure is the orthogonal projection of the input signal into the space defined by the multiscaling function. The approach will always have a solution, places no restrictions on the input (except that it be contained within L₂ ), and can be implemented in a fast algorithm. We present the details of our approach and compare it with another proposed method of prefiltering     

Analysis and design of minimax-optimal interpolators

We consider a class of interpolation algorithms, including the least-squares optimal Yen (1956) interpolator, and we derive a closed-form expression for the interpolation error for interpolators of this type. The error depends on the eigenvalue distribution of a matrix that is specified for each set of sampling points. The error expression can be used to prove that the Yen interpolator is optimal. The implementation of the Yen algorithm suffers from numerical ill conditioning, forcing the use of a regularized, approximate solution. We suggest a new, approximate solution consisting of a sinc-kernel interpolator with specially chosen weighting coefficients. The newly designed sinc-kernel interpolator is compared with the usual sinc interpolator using Jacobian (area) weighting through numerical simulations. We show that the sinc interpolator with Jacobian weighting works well only when the sampling is nearly uniform. The newly designed sinc-kernel interpolator is shown to perform better than the sinc interpolator with Jacobian weighting