Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.6k views
in Technique[技术] by (71.8m points)

algorithm - Bilinear interpolation with non-aligned input points

I have a non-grid-aligned set of input values associated with grid-aligned output values. Given a new input value I want to find the output:

                                  Four points in a rectangle with inputs varying on each axis, but outputs representing rectangular inputs.

(These are X,Y coordinates, calibrating an imprecise not-square eye-tracking input device to exact locations on screen.)

This looks like Bilinear Interpolation, but my input values are not grid-aligned. Given an input, how can I figure out a reasonable output value?


Answer: In this case where I have sets of input and output points, what is actually needed is to perform inverse bilinear interpolation to find the U,V coordinates of the input point within the quad, and then perform normal bilinear interpolation (as described in Nico's answer below) on the output quad using those U,V coordinates.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You can bilinearly interpolate in any convex tetragon. A cartesian grid is just a bit simpler because the calculation of interpolation parameters is trivial. In the general case you interpolate as follows:

parameters alpha, beta
interpolated value = (1 - alpha) * ((1 - beta) * p1 + beta * p2) + alpha * ((1 - beta) * p3 + beta * p4)

In order to calculate the parameters, you have to solve a system of equations. Put your input values in the places of p1 through p4 and solve for alpha and beta.

Then put your output values in the places of p1 through p4 and use the calculated parameters to calculate the final interpolated output value.

For a regular grid, the parameter calculation comes down to:

alpha = x / cell width
beta  = y / cell height

which automatically solves the equations.

Here is a sample interpolation for alpha=0.3 and beta=0.6

Sample interpolation

Actually, the equations can be solved analytically. However, the formulae are quite ugly. Therefore, iterative methods are probably nicer. There are two solutions for the system of equations. You need to pick the solution where both parameters are in [0, 1].

First solution:

alpha = -(b e - a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) +
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)    
beta  = (b e - a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c f - 2 b g)

where

a = -p1.x + p3.x
b = -p1.x + p2.x
c = p1.x - p2.x - p3.x + p4.x
d = center.x - p1.x
e = -p1.y + p3.y
f = -p1.y + p2.y
g = p1.y - p2.y - p3.y + p4.y
h = center.y - p1.y

Second solution:

alpha = (-b e + a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)
beta  = -((-b e + a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/( 2 c f - 2 b g))

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...