Talk:Bilinear interpolation

Rewrite

I think that this article explains the topic in not the best way and I propose a major rewrite.

The idea of explaining the method using the "capital-H" (or capital-I) shape may help less mathematically skilled readers, but overcomplicates it, IMHO. After reading (and before some thinking) I was left with the impression that three separate linear operations were required, but the meaning of the intermediates was not explained.

I would describe the process as a weighted average of the four nearest points, with the weights being determined by the areas of the four rectangles divided by their sum. This sum is the area of the rectangle QQQQ.

Even if you don't like my alternative interpretation, it'd be easier to read if 1/( (x2-x1)(y2-y1) ) were in a sigle term at the start.

thoughts? TomViza 02:24, 19 January 2006 (UTC)

I like your idea of coupling the areas with the weights very much. It is easy to see it as a generalization of the one-dimensional case, where the weights are determined by the distances. I agree that this will be less complicated than the H-shape.

However, explaining bilinear interpolation as successive 1d linear interpolations also has its advantages. It explains the name (you do first an interpolation in the x-direction and then one in the y-direction) and it points to an easy way to do an error analysis.

So, what do you think of the following outline: First give the formula and your area-based explanation and then say that the formula can also be derived via the H-shape. -- Jitse Niesen (talk) 13:27, 19 January 2006 (UTC)

I think it is an excellent formulation for interpretation -- the weights of each corner are proportional to the area of the opposing sub-rectangle. The (x2-x1)(y2-y1) term is the area of the whole rectangle, and, for instance, the (x-x1)(y-y1) is the area of the rectangle opposite Q_22. That would hold to higher dimensions: In trilinear, the weights of each component are proportional to the size of the opposing volume. Back down to the univariate linear, case, the weight of each extreme is proportional to the distance opposite the extreme. Conceptually, it seems equivalent to the Barycentric_coordinates_(mathematics) interpolation often used in Finite_element_analysis.

Also, the 'four nearest points' idea works this way only if the points are on a regular grid. If the points are irregular, one violates the first assumption on the page. Drf5n 19:11, 24 September 2006 (UTC)

Error in matrix formulation

I think there is an error in the matrix formulation. Product of 2x2 and 1x2?

Yes, you're right. Thanks for the notice. The error is now fixed. -- Jitse Niesen (talk) 05:53, 20 April 2006 (UTC)

Error in Big equations

On using this page to check some interpolations we noticed that some minus signs should be plus signs. These have been changed. Otherwise this page is excellent. How about something similar in the tri-linear equations page?

Are you sure? The formula used to be:

$f(x,y)\approx {\frac {f(Q_{11})}{(x_{1}-x_{2})(y_{1}-y_{2})}}(x-x_{2})(y-y_{2})-{\frac {f(Q_{21})}{(x_{1}-x_{2})(y_{1}-y_{2})}}(x-x_{1})(y-y_{2})$

${}-{\frac {f(Q_{12})}{(x_{1}-x_{2})(y_{1}-y_{2})}}(x-x_{2})(y-y_{1})+{\frac {f(Q_{22})}{(x_{1}-x_{2})(y_{1}-y_{2})}}(x-x_{1})(y-y_{1}).$

Substituing $(x,y)=(x_{1},y_{2})$, the right-hand side evaluates to

$-{\frac {f(Q_{12})}{(x_{1}-x_{2})(y_{1}-y_{2})}}(x_{1}-x_{2})(y_{2}-y_{1})=f(Q_{12}).$

So the minus sign seems correct to me.

It would be great if you could edit the trilinear interpolation page along similar lines. -- Jitse Niesen (talk) 04:09, 17 May 2006 (UTC)

(continued)

We did a test in a spread sheet - with all plus signs the answers were correct - minus signs would have given an incorrect answer. If the f(p) equation is plugged into the the f(R1) and f(R2) equations then minus signs do not seem to occur. We could be wrong though .. :-) I can provide a link to a page with a C code listing showing all plus signs - but I'm not sure if such links are allowed on these pages. I won't change the page. safetycritical 21:38, 17 May 2006 (UTC)

Of course, I could also be wrong. Please post the link, or email the code to me directly (you can find my email address by going to my user page and following the link to my home page). -- Jitse Niesen (talk) 03:43, 18 May 2006 (UTC)

Better form of equation

Wouldn't it be much more intuitive to replace

$f(x,y)\approx f(0,0)\,(x-1)(y-1)-f(1,0)\,x(y-1)-f(0,1)\,(x-1)y+f(1,1)xy.$

with

$f(x,y)\approx f(0,0)\,(1-x)(1-y)+f(1,0)\,x(1-y)+f(0,1)\,(1-x)y+f(1,1)xy.$

You're probably right. I modified the formulas to avoid negative quantities like x − 1. I hope I did not introduce errors in the process. -- Jitse Niesen (talk) 04:50, 22 May 2006 (UTC)

Maybe it's just me, but I find this way easier because in this case the (1 − x) and (1 − y) represent the weights on the pixels, and this way the alternate weights ( (1 − x) and x ) add up to 1.

Linearities

Hi there...

The text mentions the fact that "the interpolant is not linear", but have you ever seen a linear interpolant?... Linear in relation to what, after all??

I don't know why this phrase is bothering me... Perhaps because I also want to include a dicussion on the fact that this non-linear interpolant actually generates a linear filter that will be used to process the image (as you all know). Wat do you think?... -- NIC1138 14:18, 25 August 2006 (UTC)

The interpolant is the function f, which is a linear function. So "the interpolant is not linear" means nonlinear with respect to the arguments of f, which are x and y.

If the phrase is bothering you, then perhaps you could try reformulating it? By the way, I don't know that this non-linear interpolant actually generates a linear filter that will be used to process the image. Different editors come from different backgrounds, and I don't do image manipulation. Please do add something about this application. -- Jitse Niesen (talk) 14:54, 25 August 2006 (UTC)

Applying the interpolation is a linear transform of the input variables (Q_**), but the surface between the points is not a plane. Three points specify a plane, and the fourth would require some sort of curvature. If you were interpolating on a triangle by finding the point on the plane defined by the triangle, then you'd have a linear interpolant. Drf5n 01:13, 25 September 2006 (UTC)

Of course it's not linear, it's bilinear. Bilinear means it's linear in terms of either its arguments. Rather like the use in Bilinear form. The name does not suggest linearity just because it contains the latter's adjective form. unregistered.user 5:38, 30 September 2009 (UTC) —Preceding unsigned comment added by 137.189.90.241 (talk)

Excel Bilinear Interpolation Function

It would seem useful to include software code for many of these excellent mathematical explanations/algorithms. I've included here an Excel user function I wrote yesterday that should work with nearly any 2D table in Excel. The algorithm is based on the algorithm on the main page. There has been very little testing so take this as a starting point.

   Public Function Interp2D(ByVal x As Double, ByVal y As Double, ByVal rgTable As Range) As Double
       '**** Interp2D BILINEAR INTERPOLATION FUNCTION ****
       '(From http://en.wikipedia.org/wiki/Bilinear_interpolation)
       'In mathematics, bilinear interpolation is an extension of linear interpolation
       'for interpolating functions of two variables. The key idea is to perform linear
       'interpolation first in one direction, and then in the other direction.
       '
       'Suppose that we want to find the value of the unknown function f at
       'the point P = (x, y). It is assumed that we know the value of f at the four
       'points Q11 = (x1, y1), Q12 = (x1, y2), Q21 = (x2, y1), and Q22 = (x2, y2).
       '
       'We first do linear interpolation in the x-direction. This yields
       '
       ' f(R1) = (x2 - x)/(x2 - x1) * f(Q11) + (x - x1)/(x2 - x1)*f(Q21)
       '   where R1 = (x, y1)
       'and
       ' f(R2) = (x2 - x)/(x2 - x1) * f(Q12) + (x - x1)/(x2 - x1)*f(Q22)
       '   where R2 = (x, y2)
       '
       'We then proceed by interpolating in the y-direction.
       '
       ' f(P) = (y2 - y)/(y2-y1) * f(R1) + (y - y1)/(y2 - y1) * f(R2)
       '   where P = (x, y)
       '
       'Constraints:
       '   x is a Double and xHeaderRowMinValue <= x <= xHeaderRowMaxValue
       '   y is a Double and yHeaderColumnMinValue <= y <= yHeaderColumnMaxValue
       '   rgTable is an Excel range, specified in the normal Excel way
       '       The range should be a rectangle including the xHeader Row,
       '        the yHeaderRow, and all of the data table.
       '   xHeaderRow values increase to the right
       '   yHeaderColumn values increase downward
       
       Const minPositiveDouble As Double = 4.94065645841247E-324
       Const maxPositiveDouble As Double = 1.7976931348623E+308
       Const Epsilon As Double = 0.0001  'Tolerable error allowed
       
       Dim rgXHdr, rgYHdr, rgXYData As Range
       Dim xHdr(), yHdr(), xyData() As Double  'Array sizes still unknown
       Dim xHdrMin, xHdrMax, yHdrMin, yHdrMax As Double
       
       Dim x1, x2, y1, y2, ixX1, ixX2, ixY1, ixY2, fQ11, fQ12, fQ21, fQ22, fR1, fR2, fP As Double
       Dim row, col As Range
       Dim i, j As Integer
       Dim t As Variant
           
       'Get xHeaderRow, and set up array to hold values
       Set rgXHdr = rgTable.Offset(0, 1).Resize(1, rgTable.columns.Count - 1)
       ReDim xHdr(rgXHdr.columns.Count - 1)    'Size the array
       
       'Find min/max limits for xHeaderRow, and read values into array
       '  Assumes minimum xHeader value is 0, ie no negative numbers
       xHdrMin = maxPositiveDouble
       xHdrMax = 0
       i = 0
       For Each col In rgXHdr.columns
           If xHdrMax < col.Cells(1, 1).Value Then
               xHdrMax = col.Cells(1, 1).Value
           End If
           
           If xHdrMin > col.Cells(1, 1).Value Then
               xHdrMin = col.Cells(1, 1).Value
           End If
           
           xHdr(i) = col.Cells(1, 1).Value
           i = i + 1
       Next
   
       'Get yHeaderColumn, and set up array to hold values
       Set rgYHdr = rgTable.Offset(1, 0).Resize(rgTable.rows.Count - 1, 1)
       ReDim yHdr(rgYHdr.rows.Count - 1)    'Size the array
       
       'Find min/max limits for yHeaderColumn, and read values into array
       '  Assumes minimum yHeader value is 0, ie no negative numbers
       yHdrMin = maxPositiveDouble
       yHdrMax = 0
       i = 0
       For Each row In rgYHdr.rows
           If yHdrMax < row.Cells(1, 1).Value Then
               yHdrMax = row.Cells(1, 1).Value
           End If
           
           If yHdrMin > row.Cells(1, 1).Value Then
               yHdrMin = row.Cells(1, 1).Value
           End If
           
           yHdr(i) = row.Cells(1, 1).Value
           i = i + 1
       Next
       
       'Verify that x & y are in proper range,
       '  after allowing for Epsilon differences in values
       If x < xHdrMin And x >= xHdrMin - Epsilon Then
               x = xHdrMin
       End If
       If x > xHdrMax And x <= xHdrMax + Epsilon Then
               x = xHdrMax
       End If
       If y < yHdrMin And y >= yHdrMin - Epsilon Then
               y = yHdrMin
       End If
       If y > yHdrMax And y <= yHdrMax + Epsilon Then
               y = yHdrMax
       End If
       
       If x < xHdrMin Or x > xHdrMax Or y < yHdrMin Or y > yHdrMax Then
           MsgBox ("Interp2D: x or y value out of range: x= " & x & " y= " & y)
           End
       End If
           
       'Get xyData, and set up array to hold values
       Set rgXYData = rgTable.Offset(1, 1).Resize(rgTable.rows.Count - 1, rgTable.columns.Count - 1)
       ReDim xyData(rgXYData.columns.Count - 1, rgXYData.rows.Count - 1)    'Size the 2D array
       
       'Read Excel table values into xyData array
       i = 0
       For Each col In rgXYData.columns
           j = 0
           For Each row In col.rows
               xyData(i, j) = row.Cells(1, 1).Value
               j = j + 1
           Next
           i = i + 1
       Next
       
       'Find x1, x2, and corresponding indices ixX1, ixX2 in xHdr
       i = 0
       x1 = xHdrMin
       x2 = xHdrMin
       ixX1 = 0
       ixX2 = 0
       For Each t In xHdr
           If x = t Then
               x1 = t
               x2 = t
               ixX1 = i
               ixX2 = i
               Exit For
           ElseIf x > t Then
               x1 = t
               x2 = xHdr(i + 1)
               ixX1 = i
               ixX2 = i + 1
           End If
           i = i + 1
       Next
       
       'Find y1, y2, and corresponding indices ixY1, ixY2 in yHdr
       i = 0
       y1 = yHdrMin
       y2 = yHdrMin
       ixY1 = 0
       ixY2 = 0
       For Each t In yHdr
           If y = t Then
               y1 = t
               y2 = t
               ixY1 = i
               ixY2 = i
               Exit For
           ElseIf y > t Then
               y1 = t
               y2 = yHdr(i + 1)
               ixY1 = i
               ixY2 = i + 1
           End If
           i = i + 1
       Next
       
       'Get fQ11, fQ12, fQ21, fQ22
       fQ11 = xyData(ixX1, ixY1)
       fQ12 = xyData(ixX1, ixY2)
       fQ21 = xyData(ixX2, ixY1)
       fQ22 = xyData(ixX2, ixY2)
       
       'Get f(R1) and f(R2)
       If x1 = x2 Then
           fR1 = fQ11
           fR2 = fQ12
       Else
           fR1 = ((x2 - x) / (x2 - x1)) * fQ11 + ((x - x1) / (x2 - x1)) * fQ21
           fR2 = ((x2 - x) / (x2 - x1)) * fQ12 + ((x - x1) / (x2 - x1)) * fQ22
       End If
       
       'Get f(P)
       If y1 = y2 Then
           fP = fR1
       Else
           fP = ((y2 - y) / (y2 - y1)) * fR1 + ((y - y1) / (y2 - y1)) * fR2
       End If
           
       Interp2D = fP
       
   End Function

No citations

This article does not cite any references or sources. (difficult when I'm trying to find references for my coursework) Ms331 (talk) 22:35, 23 April 2008 (UTC)

Bad Image for Example

The palm tree image is very rough to start with. Can someone do this with a better original image?daviddoria (talk) 20:23, 19 September 2008 (UTC)

Revert

How would one put the page back to what it was before there were a lot of failed parsings?

error in linear product expression

you need 4 constants

the expression z=(a1+a2x)(a3+a4y) does not since a1 and a3 factor out leaving 3 constants

No, these in fact are four independent constants --Pot (talk) 00:59, 4 April 2010 (UTC)

the correct expression is

z=A(1+Bu)(1+Ct)+D with u,t the normalized coordinates

the 4 corners are z1=z(0,0), z2=z(1,0), z3=z(1,1), z4=z(0,1) and

A=(z2-z1)(z4-z1)/(z3+z1-z4-z2)

B=(z2-z1)/A

C=(z4-z1)/A

D=z1-A

Jdf6042 (talk) 14:51, 3 April 2010 (UTC)

Response to Pot- The geneal expression z=b1+b2*x+b3*y+b4*x*y does not factor into an expression like

z=(a1+a2*x)(a3+a4*y)unless b1*b4=b2*b3.

If z=A(1+Bu)(1+Ct)+D then in terms of b1,b2,b3,b4

A=b2*b3/b4

B=b4/b3

C=b4/b2

D=b1-b2*b3/b4

thus,

z=(b2*b3/b4)*[1+(b4/b3)*u][1+(b4/b2)*t]+(b1-b2*b3/b4)

with

b1=z(0,0)

b2=z(1,0)-z(0,0)

b3=z(0,1)-z(0,0)

b4=z(0,0)-z(1,0)-z(0,1)+z(1,1)

Jdf6042 (talk) 21:07, 11 July 2010 (UTC)

So? --Pot (talk) 14:12, 12 July 2010 (UTC)

I agree. The formula (a1 x + a2)(a3 y + a4) is incorrect.

For example in the case of f(0,0) = 0, f(0,1) = f(1,0) = 1, f(1, 1) = 2,

the result of interpolation is f(x,y) = x + y, which cannot be written in the form of (a1 x + a2)(a3 y + a4).

--Lzn11 (talk) 12:32, 16 August 2012 (UTC)

Contrary to what the name suggests, the bilinear interpolant is not linear; rather, it is a product of two linear functions:

$(a_{1}x+a_{2})(a_{3}y+a_{4})=a_{2}a_{4}+a_{1}a_{4}x+a_{2}a_{3}y+a_{1}a_{3}xy\,$

Alternatively, the interpolant can be written as:

$b_{1}+b_{2}x+b_{3}y+b_{4}xy\,$

where,

$b_{1}=a_{2}a_{4}=f(0,0)\,$

$b_{2}=a_{1}a_{4}=f(1,0)-f(0,0)\,$

$b_{3}=a_{2}a_{3}=f(0,1)-f(0,0)\,$

$b_{4}=a_{1}a_{3}=f(0,0)-f(1,0)-f(0,1)+f(1,1).\,$

Four equalities above, one for each constant, come from;

$f(x,y)\approx f(0,0)\,(1-x)(1-y)+f(1,0)\,x(1-y)+f(0,1)\,(1-x)y+f(1,1)xy.$

Like you said, the result of interpolation is x+y indeed, and the form that you said was not definitive for the situation is the very form you used to find the result of interpolation actually.

Error in example picture: Bilinear interpolation in grayscale values.

The correct value should be 146.1, not 139.5 —Preceding unsigned comment added by Skogkatten (talk • contribs) 12:41, 18 November 2010 (UTC)

I agree. Good catch. —Ben FrantzDale (talk) 13:11, 18 November 2010 (UTC)

Also, this example has an inverted y axis which leads to difficulties when trying to apply the formulas above.

Minor(Hobby_Coder_Nitpick). In case the example+image are ever changed/updated. Suggest to not use a example value which is right in the middle. Like 14.5 in this case. (Related to code writing based on the given example value data, as it allows for seemingly right, but still wrong, code to output the right value.) --MvGulik (talk) 05:38, 27 June 2015 (UTC)

I don't get it.

Could someone please explain what f(Q11), f(Q12), f(Q21), and f(Q22) actually are? Everything else is explicitly defined, but I have no idea what the function for these points is calculating. In other words, f(Q??) = ??? --61.194.119.130 (talk) 01:58, 30 May 2011 (UTC)

Ok, I figured it out. It is the value at the points Q11..Q22.--61.194.119.130 (talk) 02:00, 30 May 2011 (UTC)

Curvilinear grids?

The intro states bilinear interpolation applies to regular grids while in fact it can also apply to curvilinear grids, although it has to interpolate all four edges, rather than just 2 edges. I don't have any sources for this. Tom Ruen (talk) 02:56, 3 December 2011 (UTC)

curvilinear grid

Bilinear interpolated

NOT bilinearly interpolated

Here's the formula I use for bilinear interpolation of a quadrilateral region bounded by curved edges. The position is parametrized by [u,v], each going 0 to 1, with 4 corner positions A,B,C,D, and 4 edge curves e(u), f(v), g(v), and h(u). Tom Ruen (talk) 03:56, 16 December 2011 (UTC)

Please simplify this page

I do not understand anything from the page, and I need to know how to perform Bilinear Interpolation on a calculator, but the page isn't helping me. — Preceding unsigned comment added by 86.133.88.157 (talk) 16:41, 16 July 2013 (UTC)

The article is well written I think. Examples and figures are pretty cool. The figure illustrating the geometric visualisation is fantastic.

Bilinear interpolation is not a good starting point to understand interpolation. And, it is a horrible starting point to understand computer graphics ;]

You said you didn't understand anything. I suggest you start with weighted averaging, and continue with linear interpolation and interpolation

Interpolation is synonymous with estimation and approximation

A problem definition would be:

You have a set of data but you need more data in the same range

You either don't have the original function that was used to generate the data, or you have it but it is too complex and thus inefficient to evaluate with the resources at hand

In either case, you need a new function to generate new data

As long as you are not using the original function, the data you will generate will be estimated/approximated/interpolated data

The function that you will use to generate new data is called interpolant

There are three kinds of interpolation operations depending on the form of the interpolant used: piecewise constant interpolation, linear interpolation and non-linear interpolation.

In piecewise constant interpolation, you assume that the two known data points and the new data point between the two are connected by a line having a zero slope, and thus the interpolant is y=b

In linear interpolation, you assume that the three points are connected by a line having a non-zero slope, and thus the interpolant is y=mx+b

In non-linear interpolation, you assume that the three points are connected by a curve (varying slope), and thus the interpolant is a polynomial of degree two or more

Consider 2D Cartesian space: Linear interpolation can be interpreted as a weighted averaging operation, where the values to be averaged are y₀ and y₁, the result (i.e. the weighted average) is y, and the weights of the values y₀ and y₁ are determined by their relative distances to y on the x-axis. However, note that the weights are inversely proportional to the distances on the x-axis, i.e. the weight of y₀ should be taken as (x₁-x) instead of (x-x₀), and conversely the weight of y₁ should be taken as (x-x₀) instead of (x₁-x), because the weighted average should be closer to the value whose weight is larger. This is linear interpolation in 2D space.

Regardless of the depth (i.e. number of dimensions) of the space in which points are defined, linear interpolation operation is a one dimensional operation; essentially you generate a third point between two known points, all three being on a line.

Bilinear and trilinear interpolations are compound interpolation operations, that consist of multiple linear interpolations along the grid lines, performed on 2D and 3D grids respectively. They are linear only on the grid lines whereas they are non-linear between the grid lines. They can be referred to as grid interpolation operations.

Bilinear interpolation is a compound interpolation operation that consists of three consecutive interpolation operations that are done on two dimensional (2D) grids.

Trilinear interpolation is a compound interpolation operation that consists of seven linear interpolations (two bilinear interpolations followed by a linear interpolation) that are done in three dimensional grids.

Compound interpolation operations, whether bilinear or trilinear, are defined by functions that have the same depth as the space in which points are defined, e.g. a compound interpolation operation performed in a 2D grid (i.e. bilinear interpolation), requires an interpolant of degree two, and a compound interpolation operation in a 3D grid (i.e. trilinear interpolation) requires an interpolant of degree three. Performing one linear interpolation on each dimension of the space you are working in is how the interpolant is defined for these 'grid interpolation operations'. — Preceding unsigned comment added by 85.110.50.54 (talk) 05:56, 13 November 2013 (UTC)

bilinear vs. bicubic

Removed assertion that bicubic interpolation was superior to bilinear for various things including "edge halos" which is untrue. See The myth of infinite detail: Bilinear vs. Bicubic and closely compare the example images. Basically, bicubic is great if you like 135° angles and terrible if you don't like edge halos. Foogus (talk) 23:32, 27 October 2015 (UTC)

Non-rectilinear quadrilaterals

Does the alternate algorithm (assuming the final functional form, and solving the matrix to find the weights) also trivially generalise to individual (convex) non-rectilinear quadrilaterals? (And what about convex quadrilateral meshes?) Cesiumfrog (talk) 23:39, 9 February 2017 (UTC)

treatment of edge cases

Notable omission in the article is what if any conventions exist for dealing with edge cases. — Preceding unsigned comment added by Norlesh (talk • contribs) 07:26, 1 December 2019 (UTC)

Which edge cases? Sampling at the edges of the image? I'd say that there's no convention for this because of the ad hoc nature of this problem. BernardoSulzbach (talk) 18:18, 6 December 2019 (UTC)

Explanations or Derivation of the second Alternative formula

I found the formula with b_xx coefficients would be very useful, but I couldn’t figure out how is the derivation done with only the final formula provided. It might be a lot better to add more information and explanation of that formula. :-) 1.36.219.240 (talk) 20:04, 7 May 2020 (UTC)

Formula error

The matrix formula for unit square interpolation has x and y transposed. Shg4421 (talk) 20:08, 19 July 2021 (UTC)