Abstract
Denoising is an essential ingredient of any data processing task because real data are usually contaminated by some amount of uncertainty, error or noise. The ultimate objective in this study is to handle the multiresolution denoising of an arbitrarily spaced multidimensional data set contaminated with arbitrary noise. Denoising is closely related to function estimation from noisy samples, which is best achieved by complexity control in a structured function space. Multiresolution analysis and wavelets provide a suitable structured space for function estimation. However, conventional wavelet decompositions, such as the fast wavelet transform, are designed for regularly spaced data. Furthermore, the projection and lifting scheme approaches for dealing with irregular data cannot be easily extended to higher dimensions and their application to denoising is not straightforward. In contrast, the least squares wavelet decomposition offers a method for direct decomposition and denoising of multidimensional irregularly spaced data. We show that the frequently applied level by level multiresolution least squares wavelet decomposition suffers from gross interpolation error in the case of irregularly spaced data. The simultaneous least squares wavelet decomposition, with careful wavelet selection, is proposed to overcome this problem. Conventional wavelet domain denoising techniques, such as global and level dependent thresholding, work well for regularly spaced data but more sophisticated coefficient dependent thresholding is required for irregularly spaced data. We propose a new data domain denoising method for Gaussian noise, referred to as the Local Goodness of Fit (LGF) algorithm, which is based on the local application of the conventional goodness of fit measure in a multiresolution structure. We show that the combination of the simultaneous least squares wavelet decomposition and the LGF denoising algorithm is superior to the projection and coefficient dependent thresholding and can handle arbitrarily spaced multidimensional data contaminated with independent, but not necessarily identically distributed, Gaussian noise. For denoising of data contaminated with outliers and/or non-Gaussian long tail noise, the decomposition methods based on mean estimation are not robust. We develop a new robust multiresolution decomposition, based on median estimation in a dyadic multiresolution structure, referred to as the Interpolated Block Median Decomposition (IBMD). The IBMD method overcomes the limitations of existing median preserving transforms and can handle multidimensional irregularly spaced data of arbitrary size. Thresholding methods for the coefficients of robust median preserving decompositions are currently limited to regular data contaminated with noise drawn independently and identically from a known symmetric distribution. To overcome these serious limitations, we develop a fundamentally new data domain robust multiresolution denoising procedure, called the Local Balance of Fit (LBF) algorithm, which is based on local balancing of the data points above and below the denoised function in a dyadic multiresolution structure. The LBF algorithm, which was inspired by the intuitive denoising style carried out by a human operator, is a distribution free method that can handle any arbitrary noise without a priori knowledge or estimation of the noise distribution. The combination of the robust IBMD decomposition and the LBF denoising algorithm can effectively handle a wide spectrum of denoising applications involving multidimensional arbitrarily spaced data contaminated with arbitrary and unknown noise. The only limitation is that the noise samples must be independent or uncorrelated.