Approximation & smoothing with RBFs

Introduction

It is not always desirable to exactly interpolate scattered data when a data set is contaminated with noise. A smooth approximation is often more useful. Even when data are not affected by noise, smoothing can be desirable to remove unwanted detail or to avoid aliasing when evaluating an RBF on a mesh or grid which is coarse relative to the detail present in the RBF. In this latter case, a low pass (i.e. anti-aliasing) filter can be used to prevent artefacts due to the RBF as being sub-sampled.

FastRBFTM offers both low pass filtering for smoothing RBFs and new techniques for fitting an approximating RBF to noisy data. It also offers mechanisms to cope with extreme outliers.

Noisy data

(a) Noisy 3D data 		approximating RBF

(b) RBF approximation 		High detail RBF

(a) High detail RBF 		Low detail smoothed RBF

(b) Low detail smoothed RBF

RBF approximation - fitting to noisy data

One way to approximate noisy data is to specify a fitting tolerance as described in the RBF FAQ. This inexact fitting process is exploited by the greedy fitter to achieve significant data reduction. Although there is an inherent tendacy with the greedy algorithm to favour absorption of lower frequencies before higher ones, resulting in a smoother surface, it does not enforce any optimality on the approximating RBF.

FastRBFTM now offers two approximation strategies for fitting to noisy data which optimise different criteria. These are

The error bar fitter finds the smoothest function within value ranges specified at the data points, while spline smoothing balances the smoothness of the fitted RBF against fidelity to the raw data. Of course, the low pass filter approach described below can also be used to further smooth an RBF after fitting with either of these techniques.

Low pass filtering

The Low Pass Filter (LPF) technique applies smoothing during RBF evaluation. The result of convolving an RBF with a smoothing kernel is computed analytically and the resulting expression evaluated, thus avoiding computationally intensive evaluations on a regular grid and computing the convolution integral by spatial or Fourier methods.

1D comparison of fitting techniques

The following example illustrates the various FastRBF fitting strategies for noisy data. A more practical surfacing comparison can be found in the links at the end of this FAQ.
Input data
(a) Input data 		Exact fit
(b) Exact fit 		Greedy fit
(c) ``Greedy'' fit
Low pass filter
(d) Exact fit after applying a low pass filter 		Spline smoothing
(e) Spline smoothing 		error bar fit
(f) Error bar fit

What is spline smoothing?

Spline smoothing trades smoothness of the fitted function against fidelity to the data and can be expressed by the following problem,

$\displaystyle \par Given a set of nodes $\{\vec{x}_i\}_{i=1}^{N}\subset\ensurem... ...rt^2 + \frac{1}{N} \sum_{i=1}^{N} \big( s(\vec{x}_i) - f_i \big)^2, \end{align}$

where $ \rho\geq{}0$ and $ \Vert\cdot\Vert$ denotes the smoothness penalty. The solution to this problem is also an RBF with weights $ \lambda_i$. In the case of the thin plate basic function, the smoothness penalty is the integral of the second derivatives of s. The parameter $ \rho$ controls the amount of smoothing. A value of zero results in an exact fit to the data. Increasing $ \rho$ increases the amount of smoothing relative to the average deviation from the data squared.

When modeling empirical data, we often want to control the deviation of the fitted function from the raw data since this is related to the accuracy of the measurement process, which is usually known. In the case of spline smoothing, the deviation at the data nodes is the product of $ \rho$ and the RBF weights $ \lambda_i$,

$\displaystyle s(\vec{x}_i) = \vec{f}_i + \rho\vec{\lambda}_i.$ (1.3)

What is error-bar fitting?

FastRBFTM's error bar fitter (or more correctly the smoothest restricted range fitter) finds the smoothest function which passes within an uncertainty range specified at each data point. The range of values at a point is specified by a lower limit and an upper limit. These are akin to error bars on the values being interpolated. The error bar fitter finds the smoothest function which passes within the error bars specified. A global error bar (tolerance) can be specified or a locally varying one. Furthermore, the upper and lower bounds need not be symmetric about the nominal data value.

What is low pass filtering?

Ideally a low pass filter (LPF) globally attenuates frequencies in the data higher than some cut-off frequency - the controlling parameter. An LPF can effectively remove noise when the noise can be distiguished from genuine signal on the basis of frequency alone. Strictly, this condition is rarely met. However, if the overlap between noise and signal in the frequency domain is small, then an LPF can be effective. In the spatial domain, the LPF is equivalent to performing a weighted moving average on gridded data, where the weights are determined by the filter kernel. The kernel used in FastRBFTM is similar to a Gaussian. The `Half Maximum' width of the Gaussian is related to the cut-off frequency. Note that the Gaussian, as with most actual LPFs, does not have a sharp cut-off frequency. In FastRBFTM LPF is realised very efficiently since the result of the convolution is determined analytically. We do not need gridded data, rather we can filter scattered data directly.

What is anti aliasing and what is the Nyquist sampling criterion?

The Nyquist sampling theorem says that we must evaluate an RBF at intervals no less frequent than twice the highest frequency present in the RBF. We should low pass filter an RBF to ensure that this criterion is met when evaluating an RBF on a grid or a mesh at lower frequency than the Nyquist limit. Put more intuitively, aliasing means that we have to be careful when we sample at an interval coarser than the finest detail in the underlying signal. In practice, anti-aliasing means that the frequencies in an RBF should be limited by applying an LPF with a cut-off frequency half that of the mesh or grid spacing, prior to evaluation. This is approximately equivalent to specifying that the width of the Gaussian kernel used by FastRBF corresponds to the mesh/grid spacing.

Aliasing means that an LPF may be appropriate when evaluating an RBF even if another smoothing technique has been used to fit the RBF.

What is the difference between low pass filtering and the approximation techniques of the error-bar fitter and spline smoothing?

Which technique should I use?

In some circumstances all three FastRBFTM methods can produce similar results (see the smoothing LIDAR surface comparison). Low Pass Filtering (LPF) is always appropriate when evaluating an RBF on a coarse grid/mesh relative to the frequencies present in the RBF. LPF is suited to a posteriori variation of smoothing. We can fit once then vary smoothing as required by subsequent applications. When smoothing to reduce noise, LPF assumes that noise is distinguishable by frequency alone. An accurate estimate of noise frequencies is therefore required if this assumption is applicable. High frequencies are globally attenuated. The degree of smoothing does not vary locally. The error-bar fit requires an accurate estimate of noise magnitude. Such estimates are common with most physical measured data and with laser scan (range) data. The technique can result in significant centre reduction, leading to a compact representation of the data. The degree of smoothing is easily varied throughout the data by varying the fit tolerance at each data point. Spline smoothing can produce the best results, but choosing the parameter which balances fit accuracy against smoothness can be difficult. It does not correspond to a simple physical interpretation like the previous methods. However, we have found that spline smoothing is the method most suited to certain types of geophysical data and generally very noisy scattered data.

Robustness to outliers

The FastRBFTM libraries also support a confidence parameter in all fitting modes. This parameter allows a user to enforce only a percentage of the fitting constraints, say 99% of them. This means that the most difficult to meet constraints (in our example the top 1%) are not met. This parameter gives the fitter robustness to extreme outliers in the data. It also results in considerable speed-up in the fitting process generally.

Examples of RBF smoothing and approximation

FastRBF FAQ