Publication Details
Bart Truyen, Ilse Ravyse, Cosmin Oancea, Ciprian Ionescu, Jan Cornelis

Book Anthology


A number of image acquisition equipment (such as space-born sensors, laser ranging, stereo imaging) can generate image data that do not need to be represented by a uniform spatial distribution. Even when dealing with regular grids, scattered data are typically obtained as the result of a selective processing based on a local criterion such as curvature, gradient, ... Data comprise both the spatial coordinate(s) and the corresponding attribute(s), which may be scalar or multidimensional. Surface fitting of scattered data by means of global polynomials is a notoriously difficult problem and often produces a wildly oscillating result. A potential attractive perspective would be to distribute basis functions freely over the convex hull of the data (which could consist of grey values, spatial coordinates or combinations of both) so as to obtain a pleasantly looking surface that obeys the interpolation conditions. It is well known, however, that non-adaptive methods are unsuitable in general for interpolation of scattered data, because there always exist data distributions leading to singular problems. This can obviously arise with piecewise basis functions, such as splines, if there is a void of sufficient size. It can also happen with any other basis even for data exhibiting no obvious degeneration of distribution (e.g. co-linearity, ...). This problem is not associated with the particular basis functions, and so the use of (pseudo-) orthogonal basis functions, encompassing wavelets does not solve this problem. Instead the interpolation function should be chosen from a linear space that depends on the position of the data points itself. Finite element (FE) tessellations are based on the concept of using C1 finite element functions on a triangulation of the convex hull of the point set. However, the use of a FE tessellation is considered less suited. Indeed, unlike the design problem where only bound constraints are specified, the interpolation problem almost completely specifies the tessellation in the sense that one has only restricted control over the shape of the individual triangles such that very obtuse angles commonly occur near the boundary of the convex hull. This cannot be avoided without abandoning the convex hull, or adding imaginary points. The latter lead to similar problems as the non-adaptive methods. The data dependency of the basis functions can also be introduced by using radial basis functions. Interpolation by radial basis functions has the property that polynomials are recovered by the process, whenever there exists a unique solution. It has been shown that "thin plate" splines, B-splines, and a multi-dimensional generalisation of the natural spline, termed "surface splines", are all obtained as special cases of radial function interpolation. While for surface splines, the defining variational principle guarantees the existence of a unique interpolating surface under a geometrical condition on the data points, results of the same nature for other radial functions were derived based on the classical concept of conditional positive definite functions. A major deficiency of the method of interpolation by radial functions is that the resulting linear system for determining the interpolant, although proven to be non-singular, becomes "numerically singular" as the number of points increases.