This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
This article is within the scope of WikiProject Computer graphics, a collaborative effort to improve the coverage of computer graphics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer graphicsWikipedia:WikiProject Computer graphicsTemplate:WikiProject Computer graphicscomputer graphics articles
This article has been given a rating which conflicts with the project-independent quality rating in the banner shell. Please resolve this conflict if possible.
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.
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)[reply]
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. Drf5n19:11, 24 September 2006 (UTC)[reply]
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?
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. safetycritical21:38, 17 May 2006 (UTC)[reply]
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)[reply]
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)[reply]
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.
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?... -- NIC113814:18, 25 August 2006 (UTC)[reply]
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)[reply]
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. Drf5n01:13, 25 September 2006 (UTC)[reply]
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)
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
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)[reply]
Contrary to what the name suggests, the bilinear interpolant is not linear; rather, it is a product of two linear functions:
Alternatively, the interpolant can be written as:
where,
Four equalities above, one for each constant, come from;
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.[edit]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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 ;]
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.
Inpiecewise 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
Inlinear 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
Innon-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 y0 and y1, the result (i.e. the weighted average) is y, and the weights of the values y0 and y1 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 y0 should be taken as (x1-x) instead of (x-x0), and conversely the weight of y1 should be taken as (x-x0) instead of (x1-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)[reply]
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)[reply]
Explanations or Derivation of the second Alternative formula[edit]
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)[reply]