CODEWITHSUNDEEP
algorithm
Peter Morris
Peter Morris

Reputation: 23234

Plotting a location into an irregular rectangle

I have 4 Point values: TopLeft, TopRight, BottomLeft, BottomRight. These define a 4 sided shape (like a distorted rectangle) on my monitor. These are the point a Tobii gaze device thinks I am looking at when in fact I am looking at the four corners of my monitor.

This picture shows a bitmap on the left representing my monitor, and the points the Tobii device tells me I am looking at when I am in fact looking at the corners of the screen. (It's a representation, not real).

Example

I want to use those four calibration points to take a screen X,Y position that is from an inaccurate gaze position and correct it so that it is positioned as per the image on the right.

Upvotes: 1

Views: 222

Answers (2)

javaLover
javaLover

Reputation: 6425

Edit: New solution for the edited question is at the end.

This problem is call bilinear interpolation.
Once you grasp the idea, it will be very easy and you would remember it for the rest of your life.
It would be quite long to post all detail here, but I will try.

First, I will name the point on the left to be (x,y) and the right to be (X,Y).

Let (x1,y1), (x1,y2), (x2,y1), (x2,y2) be the corner points on the left rectangle.

Secondly, let's split the problem into 2 bilinear interpolation problems:

  • want to find X
  • want to find Y

Let's find them one by one (X or Y).

Define : Qxx are the value of X or Y of the four corner in the right rectangle.

Suppose that we want to find the value of the unknown function f at the point (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).

The f(x,y) of your problem is X or Y in your question.

enter image description here

Then you interpolate f(x,y1) and f(x,y2) to be f(x,y) in the same way.

Finally, you will got X or Y=f(x,y)

Reference : All pictures/formulas/text here are copied from the wiki link (some with modification).

Edit: After the question has been edited, it become very different.
The new one is opposite, and it is called "inverse bilinear interpolation" which is far harder.
For more information, please read http://www.iquilezles.org/www/articles/ibilinear/ibilinear.htm

Upvotes: 3

Peter Webb
Peter Webb

Reputation: 691

You can define a unique Linear Transform using 6 equations. The 3 points which have to align provide those 6 equations, as each pair of matching points provides two equations in x and y.

If you want to pursue this, I can provide the matrix equation which defines the Linear Transform based on how it maps three points. You invert this matrix and it will provide the linear transform.

But having done that, the transform is completely specified. You have no control over where the corner points of the original quadrilateral will go. In general, you can't even define a linear transform to map one quadrilateral onto another; this gives 8 equations (2 for each corner) with only 6 unknowns. Its over-specified. In fact a Linear Transform must always map a rectangle to a parallelogram, so in general you can't define a Linear Transform which maps one quadrilateral to another.

So if it can't be a Linear Transform, can it be a non-Linear Transform? Well, yes, but non-Linear Transforms don't necessarily map straight lines to straight lines, so the mapped edges of the quadrilateral won't be straight. Or any other lines. And you still have 14 equations (2 for each point and corner) for which you have to invent some non-Linear transform with 14 unknowns.

So the problem as stated cannot be solved with a Linear Transform; its over specified. Using a non-Linear transform will require you to devise a non-Linear transform which has 14 free variables (vs the 6 in a Linear Transform), this will map the 7 points correctly but straight lines will no longer be straight. Adding this requirement in adds an infinite number of constraints (one for every point in the line) and you won't even be able to use continuous functions.

There may be some solution to what you are doing in terms of what you are really trying to do (ie the underlying application need), but as a mathematical problem it is unsolvable.

Let me know if you want the matrix equation to produce a Linear Transform based on how it transforms 3 points.

Upvotes: 0

Related Questions