Multivariate

Multivariate interpolation, nearest-neighbor, bilinear, multilinear, bicubic, multicubic

View other versions (4)

Contents

Overview
Nearest-neighbor Interpolation
Bilinear Interpolation
Bicubic Interpolation
References
Page Comments

Overview

Multivariate interpolation is an area of data fitting which, as opposed to univariate interpolation which fitted two-dimensional data points, finds the surface that provides an exact fit to a series of multidimensional data points. It is called multivariate since the data points are supposed to be sampled from a function of several variables.

Formally speaking, consider a series of $\inline N$ distinct $\inline (d + 1)$ - dimensional data points $\inline (x_1, y_1)$ , $\inline (x_2, y_2), \ldots, (x_N, y_N)$ , where $\inline x_i := (x_i^1, x_i^2, \ldots, x_i^d)$ is a vector, for each $\inline i = 1, 2, \ldots, N$ . By interpolating these data points we mean finding a function $\inline f : \mathbb{R}^d \to \mathbb{R}$ such that:

$f(x_1) = y_1, \quad f(x_2) = y_2, \quad \ldots \quad f(x_N) = y_N.$

(2)

We will start by describing the most straightforward multivariate interpolation methods, to the more advanced. We start with the description of the method in 3D, and then explain how this generalizes to multidimensional space.

Nearest-neighbor Interpolation

This type of interpolation basically assigns to any point $\inline P(x, y)$ in the plane, the value of the closest data point to $\inline P$ . Formally, given a series of data points $\inline (x_i, y_i, z_i)$ , for $\inline i = 1, 2, \ldots, N$ , the corresponding nearest-neighbor interpolation function is given by

$f(x, y) = f(x^*, y^*)$

(3)

where $\inline (x^*, y^*)$ is the closest data point to $\inline (x, y)$ in the sense of Euclidean distance. In other words, $\inline (x^*, y^*)$ minimizes the following objective function

$\delta(x_i, y_i) := \sqrt{(x - x_i)^2 + (y - y_i)^2}$

(4)

where $\inline i = 1, 2, \ldots, N$ . The image below shows how nearest-neighbor interpolation is applied to a series of data points in the box $\inline [0, 3] \times [0, 3]$ .

MISSING IMAGE!

378/nearest2dinterpolexample__.png cannot be found in /users/378/nearest2dinterpolexample__.png. Please contact the submission author.

In general d-dimensional space, nearest-neighbor interpolation assigns to some point $\inline P(x_1, x_2, \ldots, x_d)$ the value of the closest data point $\inline P(x_1^*, x_2^*, \ldots, x_d^*)$ to $\inline P$ , i.e. the one which minimizes the objective function

$\delta(x_i^1, x_i^2, \ldots, x_i^d) := \sqrt{(x_1 - x_i^1)^2 + (x_2 - x_i^2)^2 + \ldots + (x_d - x_i^d)^2}$

(5)

for all $\inline i = 1, 2, \ldots, N$ , where $\inline (x_i^1, x_i^2, \ldots, x_i^d, y_i)$ are the given data points.

Bilinear Interpolation

This is a generalization of linear interpolation, from 2D to 3D data points. It is assumed that the given data points are distributed along an uniform grid, as are the points $\inline Q_{11}$ , $\inline Q_{12}$ , $\inline Q_{21}$ and $\inline Q_{22}$ in the image below.

MISSING IMAGE!

378/bilinear_interpolation.png cannot be found in /users/378/bilinear_interpolation.png. Please contact the submission author.

The aim is to estimate the value of the function $\inline f(x, y)$ (from which the data points have been sampled) at point $\inline P(x, y)$ in the above graph. In order to do this, let us define two auxiliary functions $\inline f_1, f_2 : \mathbb{R} \to \mathbb{R}$ through

$f_1(x) := f(x, y_1), \qquad f_2(x) := f(x, y_2)$

(6)

where the coordinates of $\inline Q_{ij}$ are $\inline (x_i, y_j)$ and $\inline z_{ij} := f(Q_{ij})$ .

The next thing is to do linear interpolation on the two-dimensional data points $\inline (x_1, z_{11})$ , $\inline (x_2, z_{21})$ and $\inline (x_1, z_{12})$ , $\inline (x_2, z_{22})$ correspondingly. In other words, the linear interpolation functions $\inline f_1$ , $\inline f_2$ can be given by:

$f_1(x) = \frac{x_2 - x}{x_2 - x_1} z_{11} + \frac{x - x_1}{x_2 - x_1} z_{21}\ \ , \qquad f_2(x) = \frac{x_2 - x}{x_2 - x_1} z_{12} + \frac{x - x_1}{x_2 - x_1} z_{22}$

(7)

All that is left is to do linear interpolation on the two-dimensional data points $\inline (y_1, f_1(x))$ and $\inline (y_2, f_2(x))$ , providing the desired formula for the interpolation function $\inline f(x, y)$

$f(x, y) = \frac{y_2 - y}{y_2 - y_1} f_1(x) + \frac{y - y_1}{y_2 - y_1} f_2(x)$

(8)

which, with the above notations, can be written:

$\begin{array}{rl} f(x, y) \approx \frac{\displaystyle 1}{\displaystyle (x_2 - x_1)(y_2 - y_1)} & \left[ z_{11} (x_2 - x)(y_2 - y) + z_{21} (x - x_1)(y_2 - y) + \right. \\ & \left. + z_{12} (x_2 - x)(y - y_1) + z_{22} (x - x_1)(y - y_1) \right] \end{array}$

(9)

This solves the problem of doing bilinear interpolation for a set of 4 three-dimensional points. If there are more than 4 points (they should however be a multiple of 2), then we repeat the above algorithm for each cell. The interpolation function over the entire domain is then defined in a piecewise manner on each cell, through the corresponding bilinear interpolation function for that cell.

The image below shows the values obtained by applying linear interpolation on the same series of data points as in the previous graph.

MISSING IMAGE!

378/bilinearinterpolexample__.png cannot be found in /users/378/bilinearinterpolexample__.png. Please contact the submission author.

Using the same reasoning as above, we are able to generalize linear interpolation from some $\inline d$ -dimensional space to $\inline (d + 1)$ -dimensional space, in a recursive manner, giving birth to multilinear interpolation. The concept of uniform grid also generalizes to multidimensional space, as seen in the article http://en.wikipedia.org/wiki/Honeycomb_(geometry) .

Bicubic Interpolation

Without loss of generality, consider that we are given the values of the points $\inline (0, 0)$ , $\inline (0, 1)$ , $\inline (1, 0)$ and $\inline (1, 1)$ , i.e. the corners of the unit box $\inline [0, 1] \times [0, 1]$ . Our aim is to find a bicubic function $\inline p(x, y)$ of the form

$p(x, y) := \sum_{i = 0}^3 \sum_{j = 0}^3 a_{ij} x^i y^j$

(10)

that provides an exact fit to the given data points. In order to determine $\inline p$ , we need to determine its coefficients $\inline \displaystyle a_{ij}$ . This is only possible if the values of the partial derivatives $\inline \displaystyle \frac{\partial f}{\partial x}$ , $\inline \displaystyle \frac{\partial f}{\partial x}$ and $\inline \displaystyle \frac{\partial^2 f}{\partial x \partial y}$ are know at each corner of the unit box. In this case, by writing the set of linear equations

$f(T) = p(T), \quad \frac{\partial f}{\partial x}(T) = \frac{\partial p}{\partial x}(T), \quad \frac{\partial f}{\partial y}(T) = \frac{\partial p}{\partial y}(T), \quad \frac{\partial^2 f}{\partial x \partial y}(T) = \frac{\partial^2 p}{\partial x \partial y}(T),$

(11)

for all $\inline T \in \{(0, 0), (0, 1), (1, 0), (1, 1)\}$ , we are able to find the coefficients $\inline \displaystyle a_{ij}$ and completely determine the bicubic interpolation function $\inline p$ . As in the case of bilinear interpolation, if there are more than 4 points, then we repeat the above algorithm for each cell. The bicubic interpolation function over the entire domain is then defined in a piecewise fashion on each cell, through the corresponding bicubic interpolation function for that cell. It is also required that all the partial derivatives match on the common boundary of each pair of cells.

The following image shows the values obtained using bicubic interpolation on the same series of data points as in the previous graphs.

MISSING IMAGE!

378/bicubicinterpolationexample__.png cannot be found in /users/378/bicubicinterpolationexample__.png. Please contact the submission author.

Generally, using bicubic instead of bilinear or nearest-neighbor interpolation results in smoother approximations and thus is more advantageous in image restoration techniques.

When generalizing this method to multidimensional space, the function $\inline p$ will be of the form

$p(x_1, x_2, \ldots, x_d) := \sum_{i_1 = 0}^d \sum_{i_2 = 0}^d \cdots \sum_{i_d = 0}^3 a_{i_1 i_2 \ldots i_d} x_1^{i_1} x_2^{i_2} \ldots x_d^{i_d}$

(12)

and of course several other partial derivatives may come into play. The resulting system, although large, will still be linear and will allow us to find the coefficients $\inline a_{i_1 i_2 \ldots i_d}$ of the cubic interpolation function $\inline p$ . This method is also called multicubic interpolation.

Lucian Bentea (September 2008)

Multivariate

Overview

Nearest-neighbor Interpolation

MISSING IMAGE!

Bilinear Interpolation

MISSING IMAGE!

MISSING IMAGE!

Bicubic Interpolation

MISSING IMAGE!

References