Obtain two dimensional linear space on trapezoid shape inside image frame

Question

In this image, the black frame is a frame of an image, and the trapezoid is a rectangular plane as seen by a camera.

I know the pixel coordinate of the 4 corners and can iterate through each pixel inside that trapezoid. Since I don't/cannot know the transformation/rotation vectors from camera to plane, I'd like to transform the pixels into [0,0] [1,1] coordinates according to the position inside that trapezoid, so that I choose a point inside the trapezoid and obtain some coordinates in the [0, 0] [1, 1] range.

By linear space, I mean create a number of values that range from 0 to 1 linearly. So, a unidimensional linear space from 0 to 1 in 100 steps would look like [0, 0.01, 0.02, 0.03 ... 1]. In this case, I'd like to do this but in two dimensions in the trapezoid. If this were a rectangle it would be trivial, I'm not sure there is a way to do this for a trapezoid.

For example, each point in the line of left side of the trapezoid would be always X=0, and y going from 0 to 1 linearly as you move "up" (though X coordinate actually changes in the image frame).

Answer 1

I've made an example in Javascript here. Below is an explanation of the mathematics behind it.

Name the points, clockwise, starting at (0, 0), A, B, C, D. Then we can define a point along the left side, Q, as a linear combination of A and B:

Qx = Ax * (1 - v) + Bx * v
Qy = Ay * (1 - v) + By * v

Or

Qx = Ax + dx1 * v
Qy = Ay + dy1 * v

Where dx1 = Bx - Ax and dy1 = By - Ay

And a point along the right side, R, as a linear combination of D and C:

Rx = Dx + dx2 * v
Ry = Dy + dy2 * v

Where dx2 = Cx - Dx and dy2 = Cy - Dy

We can then draw a line from Q to R. With v = 0, we have the line AD, with v = 1, we have the line BC. As v goes from 0 to 1, we get lines that cover the whole of the trapezoid (assuming it is convex).

So any point P inside the trapezoid can be a linear combination of Q and R:

Px = Qx * (1 - u) + Rx * u
Py = Qy * (1 - u) + Ry * u

So a point (Px, Py) can be written:

Px = (Ax + dx1 * v) * (1 - u) + (Dx + dx2 * v) * u
Py = (Ay + dy1 * v) * (1 - u) + (Dy + dy2 * v) * u

Now we have two equations in two unknowns.

Expand and collect vs

v = (Px - Ax + u.Ax - u.Dx) / (dx1 - u.dx1 + u.dx2)
v = (Py - Ay + u.Ay - u.Dy) / (dy1 - u.dy1 + u.dy2)

Some more substitutions to simplify the calculations:

dx3 = Ax - Dx
dy3 = Ay - Dy
dx4 = dx2 - dx1
dy4 = dy2 - dy1
dx5 = Px - Ax
dy5 = Py - Ay

To get:

v = (dx5 + u.dx3) / (dx1 + u.dx4)
v = (dy5 + u.dy3) / (dy1 + u.dy4)

Set them equal

(dx5 + u.dx3) / (dx1 + u.dx4) = (dy5 + u.dy3) / (dy1 + u.dy4)

Cross multiply

(dx5 + u.dx3) * (dy1 + u.dy4) = (dy5 + u.dy3) * (dx1 + u.dx4)

Expand

dx5 * dy1 + dx5 * dy4 * u + dx3 * dy1 * u + dx3 * dy4 * u^2 = dy5 * da1 + dy5 * dx4 * u + dy3 * dx1 * u + dy3 * dx4 * u^2

Collect terms

(dx3 * dy4 - dy3 * dx4)u^2 + (dx5 * dy4 - dy5 * dx4 + dx3 * dy1 - dy3 * dx1)u + dx5 * dy1 - dy5 * dx1 = 0

This is a quadratic of the form ax^2 + bx + c = 0 Solve with quadratic formula

a = dx3 * dy4 - dy3 * dx4
b = dx5 * dy4 - dy5 * dx4 + dx3 * dy1 - dy3 * dx1
c = dx5 * dy1 - dy5 * dx1;
determinant = b * b - 4 * a * c

If determinant >= 0

u = (-B + sqrt(determinant)) / (2 * A)

Then plug u back into this equation to get v:

v = (dx5 + u.dx3) / (dx1 + u.dx4)