How can I understand the equation for bicubic interpolation?

[Hypatio]

The wikipedia article on bicubic interpolation appears to describe how to arrive at an equation for bicubic interpolation, but I cannot decipher it. Using the derivatives described I don't understand how to arrive at the relevant equation from the coordinates of the point and the values of the points around it.

I don't understand why I can't understand this.

 

[SteamKing]

The wikipedia article on bicubic interpolation appears to describe how to arrive at an equation for bicubic interpolation, but I cannot decipher it. Using the derivatives described I don't understand how to arrive at the relevant equation from the coordinates of the point and the values of the points around it.

I don't understand why I can't understand this.

Your last point is a tough one to overcome.

But, getting back to bicubic interpolation, the algorithm here is trying to interpolate a surface, or a function f(x,y) = z, rather than the standard cubic interpolation algorithm, which tries to interpolate a simple function, f(x) = y.

Where one uses the derivative f'(x) in order to formulate boundary conditions necessary to provide a unique set of cubic interpolation parameters for the simple function f(x), in the bicubic interpolation of a surface f(x,y), then partial derivatives are required to provide boundary conditions to determine the unique bicubic interpolating parameters.

 

[Hypatio]

Your last point is a tough one to overcome.

But, getting back to bicubic interpolation, the algorithm here is trying to interpolate a surface, or a function f(x,y) = z, rather than the standard cubic interpolation algorithm, which tries to interpolate a simple function, f(x) = y.

Where one uses the derivative f'(x) in order to formulate boundary conditions necessary to provide a unique set of cubic interpolation parameters for the simple function f(x), in the bicubic interpolation of a surface f(x,y), then partial derivatives are required to provide boundary conditions to determine the unique bicubic interpolating parameters.

Yes but what is the equation? I don't understand how the equation

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

is expanded to something computationally explicit using the coefficients and derivatives given.

 

[SteamKing]

You have to expand the double summation (the big sigma thingies):

p(x,y) = a00 * x^0*y^0 + a10*x^1*y^0 + a20 * x^2 * y^0 + ... + a33*x^3*y^3

The coefficients a00, a10, etc. are found from the solution of the matrix equation
[A]{alpha} = {x}, where [A] is a 16x16 square matrix and {alpha} and {x} are 16x1 column vectors.

IMO, the Wiki article is written in a very straightforward fashion. Have you studied matrix algebra and systems of equations?

 

[Hypatio]

I have tried to study matrix algebra and systems of equations, but the notation has always seemed convoluted and highly non-intuitive to me, so it is difficult. So the article is probably clear and the trouble is mine.

Looking more closely I think I see how the 16 equations given are related to the inverse matrix (A^-1), but I do not understand how the values a_ij are related to the data.

For instance, part of the solution is the equation f(0,0)=p(0,0)=a_00, but what are these parameters? How do I get them from the known points? How do I get f(0,0) or p(0,0)? I would say that p(0,0) is simply the known at (0,0), but then I don't understand why p(1,0) is somehow equal to a_00+a_10+a_20+a_30...

Also, are the values of x and y between 0 and 3? And why does this algorithm only seem to use four points, when you should actually need 16 points?

 

[SteamKing]

Remember, the bicubic interpolation covers an area, rather than a line.

Look at the illustrations on the right hand side of the article. The area which the bicubic interpolates is 3 units wide by 3 units high. The lower left hand corner has coordinates (x,y) = (0,0) and the upper right hand side has coordinates (x,y) = (3,3)

The bicubic is formulated such that p(x,y) = f(x,y) exactly at each of the 16 points where x and y are integers, for instance, when x = 1 and y = 1.

To clear up the notation, f(x,y) represents a point on the surface to be interpolated, and a formula f(x,y) = some function of x and y may not be known.
However, by measurement or whatever, you know the values of f(x,y) at 16 points.
What you are trying to do is fit a surface to this data so that you can calculate f(x,y) at a random point of your choosing.

The interpolated function you derive from the bicubic procedure is p(x,y) which is what is used to calculate the value of the function f(x,y).

As a suggestion, I recommend you review cubic interpolation of a function y = f(x) thoroughly before you plunge into the bicubic procedure.

 

[Hypatio]

I've had no problem doing cubic interpolation. A scheme is given here, which is the type of algebraic solution I am trying to get for the bicubic case. I tried to find a matrix scheme like that given here for the bicubic case for cubic interpolation so that I could compare the operations, but can't find anything.

Looks like I am failing in two places:
1. I'm failing to see how the coefficients a_00, etc. are obtained from the matrix equation {alpha}=A^-1x since x=[f(0,0) f(1,0) f(0,1)...]^T, where f(x,y) is simply equal to some sum of the coefficients again. I don't see how to solve it unless I ignore them and simply say that f(0,0) etc. are the points.

2. I see how the first four equations are derived, but I don't understand where the derivatives come from. The expanded sum is

p(x,y)=a_{00}+a_{01}y+a_{02}y^2+a_{03}y^3+a_{10}x+a_{11}xy+a_{12}xy^2+a_{13}xy^3+a_{20}x^2+a_{21}x^2y+a_{22}x^2y^2+a_{23}x^2y^3+a_{30}x^3+a_{31}x^3y+a_{32}x^3y^2+a_{33}x^3y^3
If I take the derivative of all the terms (e.g. in x) I should have more terms, e.g.:

f_x(1,0)=p_x(1,0)=\frac{1}{x}a_{00}+a_{10}+2a_{20}+3a_{30}
But they give
f_x(1,0)=p_x(1,0)=a_{10}+2a_{20}+3a_{30}

 

[SteamKing]

To recapitulate from the article:

Suppose the function values f and the derivatives f_x, f_y and f_{xy} are known at the four corners (0,0), (1,0), (0,1), and (1,1) of the unit square. The interpolated surface can then be written:

p(x,y) = double sum formula

You have to know 4 values of the function f(x,y) to be interpolated PLUS 12 values of the derivatives of f(x,y) at the corner points.

The values of the bicubic interpolation and the function are the same at each or the four corners, thus p(x,y) = f(x,y), where x,y = 0 or 1

The values of a are determined by solving the matrix equation [A]{alpha}={x}

Now, the article has done part of the solution by specifying the inverse of [A]
which is what A^-1 = represents.

Then {alpha} = [A]^-1 {x} which is a 16x16 matrix multiplied by a 16x1 column vector

The values of [A]^-1 are given in the article, and the values of {x} are the known values of the function f(x,y) and its derivatives at the corner points.

 

[Hypatio]

Thanks for helping me think about this. It turns out I didn't fully understand that the function values f(x,y) including the derivatives needed to be found from the data, so I just used finite differences and now have a working algorithm.