Reducing the Effects of Noise in Image Reconstruction

Fourier spectral methods have proven to be powerful tools that are frequently employed in image reconstruction. However, since images can be typically viewed as piecewise smooth functions, the Gibbs phenomenon often hinders accurate reconstruction. Recently, numerical edge detection and reconstruction methods have been developed that effectively reduce the Gibbs oscillations while maintaining high resolution accuracy at the edges. While the Gibbs phenomenon is a standard obstacle for the recovery of all piecewise smooth functions, in many image reconstruction problems there is the additional impediment of random noise existing within the spectral data. This paper addresses the issue of noise in image reconstruction and its effects on the ability to locate the edges and recover the image. The resulting numerical method not only recovers piecewise smooth functions with very high accuracy, but it is also robust in the presence of noise.     

Inverse Polynomial Reconstruction of Two Dimensional Fourier Images

The Gibbs phenomenon is intrinsic to the Fourier representation for discontinous problems. The inverse polynomial reconstruction method (IPRM) was proposed for the resolution of the Gibbs phenomenon in previous papers [Shizgal, B. D., and Jung, J.-H. (2003) and Jung, J.-H., and Shizgal, B. D. (2004)] providing spectral convergence for one dimensional global and local reconstructions. The inverse method involves the expansion of the unknown function in polynomials such that the residue between the Fourier representations of the final representation and the unknown function is orthogonal to the Fourier or polynomial spaces. The main goal of this work is to show that the one dimensional inverse method can be applied successfully to reconstruct two dimensional Fourier images. The two dimensional reconstruction is implemented globally with high accuracy when the function is analytic inside the given domain. If the function is piecewise analytic and the local reconstruction is sought, the inverse method is applied slice by slice. That is, the one dimensional inverse method is applied to remove the Gibbs oscillations in one direction and then it is applied in the other direction to remove the remaining Gibbs oscillations. It is shown that the inverse method is exact if the two-dimensional function to be reconstructed is a piecewise polynomial. The two-dimensional Shepp–Logan phantom image of the human brain is used as a preliminary study of the inverse method for two dimensional Fourier image reconstruction. The image is reconstructed with high accuracy with the inverse method     

Reconstruction of Piecewise Smooth Functions from Non-uniform Grid Point Data

Spectral series expansions of piecewise smooth functions are known to yield poor results, with spurious oscillations forming near the jump discontinuities and reduced convergence throughout the interval of approximation. The spectral reprojection method, most notably the Gegenbauer reconstruction method, can restore exponential convergence to piecewise smooth function approximations from their (pseudo-)spectral coefficients. Difficulties may arise due to numerical robustness and ill-conditioning of the reprojection basis polynomials, however. This paper considers non-classical orthogonal polynomials as reprojection bases for a general order (finite or spectral) reconstruction of piecewise smooth functions. Furthermore, when the given data are discrete grid point values, the reprojection polynomials are constructed to be orthogonal in the discrete sense, rather than by the usual continuous inner product. No calculation of optimal quadrature points is therefore needed. This adaptation suggests a method to approximate piecewise smooth functions from discrete non-uniform data, and results in a one-dimensional approximation that is accurate and numerically robust.      

Image Reconstruction from Fourier Data Using Sparsity of Edges

Data of piecewise smooth images are sometimes acquired as Fourier samples. Standard reconstruction techniques yield the Gibbs phenomenon, causing spurious oscillations at jump discontinuities and an overall reduced rate of convergence to first order away from the jumps. Filtering is an inexpensive way to improve the rate of convergence away from the discontinuities, but it has the adverse side effect of blurring the approximation at the jump locations. On the flip side, high resolution post processing algorithms are often computationally cost prohibitive and also require explicit knowledge of all jump locations. Recent convex optimization algorithms using \(l^1\) regularization exploit the expected sparsity of some features of the image. Wavelets or finite differences are often used to generate the corresponding sparsifying transform and work well for piecewise constant images. They are less useful when there is more variation in the image, however. In this paper we develop a convex optimization algorithm that exploits the sparsity in the edges of the underlying image. We use the polynomial annihilation edge detection method to generate the corresponding sparsifying transform. Our method successfully reduces the Gibbs phenomenon with only minimal blurring at the discontinuities while retaining a high rate of convergence in smooth regions.     

Recovering Exponential Accuracy from Non-harmonic Fourier Data Through Spectral Reprojection

Spectral reprojection techniques make possible the recovery of exponential accuracy from the partial Fourier sum of a piecewise-analytic function, essentially conquering the Gibbs phenomenon for this class of functions. This paper extends this result to non-harmonic partial sums, proving that spectral reprojection can reduce the Gibbs phenomenon in non-harmonic reconstruction as well as remove reconstruction artifacts due to erratic sampling. We are particularly interested in the case where the Fourier samples form a frame. These techniques are motivated by a desire to improve the quality of images reconstructed from non-uniform Fourier data, such as magnetic resonance (MR) images.     

Detecting Edges from Non-uniform Fourier Data Using Fourier Frames

Edge detection plays an important role in identifying regions of interest in an underlying signal or image. In some applications, such as magnetic resonance imaging (MRI) or synthetic aperture radar (SAR), data are sampled in the Fourier domain. Many algorithms have been developed to efficiently extract edges of images when uniform Fourier data are acquired. However, in cases where the data are sampled non-uniformly, such as in non-Cartesian MRI or SAR, standard inverse Fourier transformation techniques are no longer suitable. Methods exist for handling these types of sampling patterns, but are often ill-equipped for cases where data are highly non-uniform or when the data are corrupted or otherwise not usable in certain parts of the frequency domain. This investigation further develops an existing approach to discontinuity detection, and involves the use of concentration factors. Previous research shows that the concentration factor technique can successfully determine jump discontinuities in non-uniform data. However, as the distribution diverges further away from uniformity so does the efficacy of the identification. Thus we propose a method that employs the finite Fourier approximation to specifically tailor the design of concentration factors. We also adapt the algorithm to incorporate appropriate smoothness assumptions in the piecewise smooth regions of the function. Numerical results indicate that our new design method produces concentration factors which can more precisely identify jump locations than those previously developed in both one and two dimensions.     

基于Chebyshev多项式的消除Gibbs伪影的快速算法

在磁共振成像中通常通过减少相位编码次数来缩短数据采集时间，这样只能得到部分原始k空间数据，运用傅里叶变换成像时会在图像中产生常见的Gibbs环状伪影。Gegenbauer重建方法是一种能够有效消除Gibbs环状伪影并能保持高分辨率的图像重建方法，但是这种方法的缺点在于重建时间长且参数选择必须满足严格的限制且对图像重建质量影响较大。本文提出的基于Chebyshev多项式的逆多项式重建方法是针对Gegenbauer方法的改进算法，在改进原有算法不足的同时有效提高了重建精度。实验结果验证了该算法的有效性。     

Edge Detection from Non-Uniform Fourier Data Using the Convolutional Gridding Algorithm

Detecting edges in images from a finite sampling of Fourier data is important in a variety of applications. For example, internal edge information can be used to identify tissue boundaries of the brain in a magnetic resonance imaging (MRI) scan, which is an essential part of clinical diagnosis. Likewise, it can also be used to identify targets from synthetic aperture radar data. Edge information is also critical in determining regions of smoothness so that high resolution reconstruction algorithms, i.e. those that do not “smear over” the internal boundaries of an image, can be applied. In some applications, such as MRI, the sampling patterns may be designed to oversample the low frequency while more sparsely sampling the high frequency modes. This type of non-uniform sampling creates additional difficulties in processing the image. In particular, there is no fast reconstruction algorithm, since the FFT is not applicable. However, interpolating such highly non-uniform Fourier data to the uniform coefficients (so that the FFT can be employed) may introduce large errors in the high frequency modes, which is especially problematic for edge detection. Convolutional gridding, also referred to as the non-uniform FFT, is a forward method that uses a convolution process to obtain uniform Fourier data so that the FFT can be directly applied to recover the underlying image. Carefully chosen parameters ensure that the algorithm retains accuracy in the high frequency coefficients. Similarly, the convolutional gridding edge detection algorithm developed in this paper provides an efficient and robust way to calculate edges. We demonstrate our technique in one and two dimensional examples.     

一种适用于真实人体数据能有效消除Gibbs伪影的MR重建新算法

Gibbs振铃是在磁共振成像中常见的主要存在于组织边缘处的一种伪影,它是在采用部分k空间数据进行图像重建时产生的.Gegenbauer重建方法能够有效消除Gibbs环状伪影并能保持图像高分辨率,但重建时间长且参数的选择对重建结果影响很大.文中引入逆多项式方法对Gegenbauer重建方法进行了改进,同时以Chebyshev多项式替代Gegenbauer多项式,免去了参数的人为选择,提高了重建精度并加快了速度.由于上述方法是针对连续区间讨论的,因此如何通过边缘检测准确地划分连续子区间显得尤为重要.文中提出的频域滤波边缘检测法能得到准确的边缘检测结果,有效地提高了文中方法对具有复杂组织结构的真实人体MR数据重建的精度,使其更具实用性.     

Parameter Optimization and Reduction of Round Off Error for the Gegenbauer Reconstruction Method

The Gegenbauer reconstruction method has been successfully implemented to reconstruct piecewise smooth functions by both reducing the effects of the Gibbs phenomenon and maintaining high resolution in its approximation. However, it has been noticed in some applications that the method fails to converge. This paper shows that the lack of convergence results from both poor choices of the parameters associated with the method, as well as numerical round off error. The Gegenbauer polynomials can have very large amplitudes, particularly near the endpoints x=±1, and hence the approximation requires that the corresponding computed Gegenbauer coefficients be extremely small to obtain spectral convergence. As is demonstrated here, numerical round off error interferes with the ability of the computed coefficients to decay properly, and hence affects the method's overall convergence. This paper addresses both parameter optimization and reduction of the round off error for the Gegenbauer reconstruction method, and constructs a viable black box method for choosing parameters that guarantee both theoretical and numerical convergence, even at the jump discontinuities. Validation of the Gegenbauer reconstruction method through a-posteriori estimates is also provided.     

一种空域和频域相结合的图像消噪方法

提出一种基于非均匀剖分和V变换相结合的图像消噪新方法。非均匀剖分逼近在空域上视像素的灰度值为拟合数据,依据最小二乘法原理,对含噪图像进行非均匀三角剖分,使图像表示为一个分片多项式,它能保持图像的边缘及细节特征,并通过对剖分精度的控制来实现图像的消噪;V系统是一类L2[0,1]空间上的完备正交系,具有多小波的多分辨特性,利用相应的V变换将图像变换到频域,通过对高频低频的系数处理来达到消噪的目的。结合非均匀剖分逼近和V变换两者的优势,将两个方法的消噪结果加权平均,得到一种新的消噪方法。实验结果表明了该方法的消噪效果比很多经典方法更好。     

A Hybrid Approach to Spectral Reconstruction of Piecewise Smooth Functions

Consider a piecewise smooth function for which the (pseudo-)spectral coefficients are given. It is well known that while spectral partial sums yield exponentially convergent approximations for smooth functions, the results for piecewise smooth functions are poor, with spurious oscillations developing near the discontinuities and a much reduced overall convergence rate. This behavior, known as the Gibbs phenomenon, is considered as one of the major drawbacks in the application of spectral methods. Various types of reconstruction methods developed for the recovery of piecewise smooth functions have met with varying degrees of success. The Gegenbauer reconstruction method, originally proposed by Gottlieb et al. has the particularly impressive ability to reconstruct piecewise analytic functions with exponential convergence up to the points of discontinuity. However, it has been sharply criticized for its high cost and susceptibility to round-off error. In this paper, a new approach to Gegenbauer reconstruction is considered, resulting in a reconstruction method that is less computationally intensive and costly, yet still enjoys superior convergence. The idea is to create a procedure that combines the well known exponential filtering method in smooth regions away from the discontinuities with the Gegenbauer reconstruction method in regions close to the discontinuities. This hybrid approach benefits from both the simplicity of exponential filtering and the high resolution properties of the Gegenbauer reconstruction method. Additionally, a new way of computing the Gegenbauer coefficients from Jacobian polynomial expansions is introduced that is both more cost effective and less prone to round-off errors.     

基于惩罚最大似然优化模型的各向异性约束磁共振成像方法

传统磁共振(MR)傅里叶成像方法由于傅里叶不确定性,k空间扩展编码采样长度能提高图像空间分辨率,但是以降低图像信噪比为代价.提出基于最大似然优化模型的各向异性约束MR成像新方法,将离散傅里叶变换模型改进为惩罚约束函数的最优值搜索问题.利用医学结构的先验信息,将正则化惩罚运算细化至平滑区域、边界邻域、边界和边界的方向.实验结果表明,该方法不但能扩展k空间高频数据采样长度同时有效降低高斯噪声,而且能克服现有相关约束成像方法的二次模糊和Gibbs环状伪影.     

Reconstruction of volume data with quadratic super splines

We propose a new approach to reconstruct nondiscrete models from gridded volume samples. As a model, we use quadratic trivariate super splines on a uniform tetrahedral partition. We discuss the smoothness and approximation properties of our model and compare to alternative piecewise polynomial constructions. We observe, as a nonstandard phenomenon, that the derivatives of our splines yield optimal approximation order for smooth data, while the theoretical error of the values is nearly optimal due to the averaging rules. Our approach enables efficient reconstruction and visualization of the data. As the piecewise polynomials are of the lowest possible total degree two, we can efficiently determine exact ray intersections with an isosurface for ray-casting. Moreover, the optimal approximation properties of the derivatives allow us to simply sample the necessary gradients directly from the polynomial pieces of the splines. Our results confirm the efficiency of the quasi-interpolating method and demonstrate high visual quality for rendered isosurfaces.     

Gibbs Phenomena

In this note we show that when a discontinuous initial value problem for a scalar hyperbolic equation in one space variable is approximated by a difference scheme that is more than first order accurate; it leads to overshoots analogous to the Gibbs phenomenon when discontinuous functions are approximated by sections of Fourier series. A hybrid scheme due to Harten and Zwass removes the overshoots. Similar phenomena occur when solving schemes of hyperbolic equations.To David Gottlieb, master of scientific computation, subtle numerical analyst, Mensch extraordinaire.     

Sparsity Enforcing Edge Detection Method for Blurred and Noisy Fourier data

We present a new method for estimating the edges in a piecewise smooth function from blurred and noisy Fourier data. The proposed method is constructed by combining the so called concentration factor edge detection method, which uses a finite number of Fourier coefficients to approximate the jump function of a piecewise smooth function, with compressed sensing ideas. Due to the global nature of the concentration factor method, Gibbs oscillations feature prominently near the jump discontinuities. This can cause the misidentification of edges when simple thresholding techniques are used. In fact, the true jump function is sparse, i.e. zero almost everywhere with non-zero values only at the edge locations. Hence we adopt an idea from compressed sensing and propose a method that uses a regularized deconvolution to remove the artifacts. Our new method is fast, in the sense that it only needs the solution of a single l ₁ minimization. Numerical examples demonstrate the accuracy and robustness of the method in the presence of noise and blur.     

用线性神经网络映射光学过程层析成像的逆问题

过程层析成像 (Process tomography)的逆问题也称为成像算法 ,它不仅需要反映被测物质与激励场的相互作用原理 ,而且应与传感器的空间阵列结构相匹配 .成像算法的性能好坏 (包括图象质量和每帧计算需时 )是过程层析成像技术能否应用于工业过程监控系统的关键问题之一 .为了得到性能良好的重建图象 ,提出了一种线性神经网络图象重建算法 .该算法首先通过建立光学层析成像的正问题和逆问题的线性化模型来求解正问题 ,以得出图象和投影的关系模式对 ,然后将其用于训练和构造线性神经网络 ;最后使用训练好的线性神经网络来映射光学层析成像的逆问题 .实验表明 ,该方法具有较高的图象质量和极高的成像实时性 ,是一种性能良好的图象重建算法     

Practical box splines for reconstruction on the body centered cubic lattice

We introduce a family of box splines for efficient, accurate and smooth reconstruction of volumetric data sampled on the Body Centered Cubic (BCC) lattice, which is the favorable volumetric sampling pattern due to its optimal spectral sphere packing property. First, we construct a box spline based on the four principal directions of the BCC lattice that allows for a linear C(0) reconstruction. Then, the design is extended for higher degrees of continuity. We derive the explicit piecewise polynomial representation of the C(0) and C(2) box splines that are useful for practical reconstruction applications. We further demonstrate that approximation in the shift-invariant space---generated by BCC-lattice shifts of these box splines---is {twice} as efficient as using the tensor-product B-spline solutions on the Cartesian lattice (with comparable smoothness and approximation order, and with the same sampling density). Practical evidence is provided demonstrating that not only the BCC lattice is generally a more accurate sampling pattern, but also allows for extremely efficient reconstructions that outperform tensor-product Cartesian reconstructions.     

基于SIFT的POCS图像超分辨率重建

针对传统的POCS图像超分辨率重建算法中广泛使用的基于改进的Keren配准算法,对于序列帧间存在剪切和非均匀尺度变换现象时,很难做到精确的亚像素级配准,文中讨论了一种基于SIFT算法的POCS序列图像超分辨率重建算法。首先利用SIFT算法提取序列帧与参考帧间的SIFT关键点对,随后选取匹配关键点对,通过RANSAC去除误配点的同时估算出六参数仿射变换参数,最后使用POCS重建算法得到最终的重建结果。实验结果表明：该方法能有效地解决因运动估计不准而引起的重建图像效果不好的问题,特别是在序列帧间存在剪切和非均匀尺度变换现象时,重建效果明显好于传统的POCS算法,具有更强适应性。     

Detection of Edges in Spectral Data III—Refinement of the Concentration Method

Edge detection from Fourier spectral data is important in many applications including image processing and the post-processing of solutions to numerical partial differential equations. The concentration method, introduced by Gelb and Tadmor in 1999, locates jump discontinuities in piecewise smooth functions from their Fourier spectral data. However, as is true for all global techniques, the method yields strong oscillations near the jump discontinuities, which makes it difficult to distinguish true discontinuities from artificial oscillations. This paper introduces refinements to the concentration method to reduce the oscillations. These refinements also improve the results in noisy environments. One technique adds filtering to the concentration method. Another uses convolution to determine the strongest correlations between the waveform produced by the concentration method and the one produced by the jump function approximation of an indicator function. A zero crossing based concentration factor, which creates a more localized formulation of the jump function approximation, is also introduced. Finally, the effects of zero-mean white Gaussian noise on the refined concentration method are analyzed. The investigation confirms that by applying the refined techniques, the variance of the concentration method is significantly reduced in the presence of noise. This work was partially supported by NSF grants CNS 0324957, DMS 0510813, DMS 0652833, and NIH grant EB 025533-01 (AG).