I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms.

I'll try to explain my problem as much as I can.

The project has three main components; A computer, a Data-show and a webcam.

The teacher will plug the data-show in the computer and the computer screen will appear on the wall of the classroom to all students.

The main purpose of the project is to turn the image of the screen displayed on the classroom wall into interactive screen; when the teacher tabs with his finger on an image of a Button displayed on the wall, the webcam that is connected to the computer will capture the position of the teacher's finger and find his (x,y) coordinates for a reference point on the wall, and raise a click event in the related (x,y) position on the screen.

The screen of the computer has two dimensions; Width->X and Height->Y. And for every point in the screen such as P, it could be located on the screen using two numbers (Px,Py), where Px is the distance between the point P and the left side of the screen, and Py is the distance between the point P and the top side of the screen. In other words, the reference for all points in the screen is the top left corner of the screen.

The data-show will display an irregular Quadrilateral shape of the screen on the wall. the shapes will not be regular squares or rectangles due to the angle that the teacher puts the data-show in. What I'm asking for are the equations that will calculate the (x,y) point on the screen that represents the (x,y) tapped point on the wall.

There is mainly four shapes the data-show may display on the wall. For each shape of them the only known things are the coordinates of the four angles(corners) of the quadrilateral shape.

1. an optimal rectangle

The displayed image on wall has a very low chance to shape an optimal rectangle, but it's the basic shape that could be formed.

Suppose that the red point P'(Px',Py') represents the coordinates of the place the teacher tapped on with his finger.

To get the original (Px,Py) coordinates from the point (Px',Py') on the wall, I can do the following.

1. Calculate the width->X' and the height->Y' of the displayed image by the law of distance between two points.

2. find the ratio between X&X', and between Y&Y'. I'll call the first ratio rx and the second ratio ry.

3. Multiply Px' by rx to get Px, and multiply Py' by ry to get Py.

2. an optimal trapezoidal.

The displayed image on wall could also shape an optimal trapezoidal. I asked some of my friends from the applied mathematics college to help me to find the two equations to find the original coordinates of the point, and they did some calculations and came out with these two equations;

In this shape

To find X:

and to find Y I can use the same way used in the rectangle; finding the ratio between Y and the height of the trapezoidal H.

3. an irregular quadrilateral.

My question is about this shape, the data-show in most times will shape an irregular shape. Imagine this shape like

None of the shape's lines is vertical or horizontal, all lines may have different lengths and they may have different angels from each other.

My question is

I'm searching for equations that will find the original P(x,y) point of the point P'(X',Y'). Things I know are the coordinates of the points P1, P2, P3, P4, P'

What are those equations? and how are they derived?

Solution 1:

A common way to do this is to find a planar perspective transformation that “warps” the rectangle into the image quadrilateral and then use its inverse to map points on the image back to the rectangle. There are software libraries that include this as standard functionality.

If you want to code this up for yourself, it’s not terribly difficult to work out the necessary mapping. Without going into the detailed derivation, a general planar perspective transformation can be represented (in homogeneous coordinates) by a matrix of the form $$ M=\pmatrix{m_{00} & m_{01} & m_{02} \\ m_{10} & m_{11} & m_{12} \\ m_{20} & m_{21} & 1}, $$ which corresponds to the mapping $$\begin{align} x' &= {m_{00}x+m_{01}y+m_{02} \over m_{20}+m_{21}+1} \\ y' &= {m_{10}x+m_{11}y+m_{12} \over m_{20}+m_{21}+1}. \end{align}$$ Given a set of corner-to-corner correspondences between a pair of quadrilaterals, the eight coefficients can by found by solving a system of linear equations.

If one of the quads is a rectangle aligned with the coordinate axes, this transformation can be built up in stages, which can be more convenient for implementation in software. Assuming that we have the matrix $A$ which maps from the unit square to the quadrilateral, the rectangle-to-quadrilateral transformation can be derived by composing it with suitable translation and scaling transformations: $$ M = A\cdot S\left(\frac1w,\frac1h\right)\cdot T(-x_{LL},-y_{LL}). $$ The inverse map is then $$ M^{-1}=T(x_{LL},y_{LL})\cdot S(w,h)\cdot A^{-1} = \pmatrix{w&0&x_{LL} \\ 0&h&y_{LL} \\ 0&0&1 }\cdot A^{-1}, $$ where $(x_{LL},y_{LL})$ are the coordinates of the rectangle’s lower-left corner. Left-handed coordinate systems can be accommodated by throwing in the appropriate reflections, and skew rectangles can be dealt with by adding a rotation to the transformation cascade.

Now, it’s just a matter of finding the matrix $A$. Let the corners of the quadrilateral be given by the points $q_i'$, and map the corners of the unit square to them as follows: $$\begin{align} (0,0)&\mapsto q_0' \\ (1,0)&\mapsto q_1' \\ (0,1)&\mapsto q_2' \\ (1,1)&\mapsto q_3'. \end{align}$$ Solving the resulting system of equations is tedious, but straightforward. One form of the solution is as follows: $$\begin{align} a_{00} &= a_{20}x_1'+\Delta x_{10} \\ a_{10} &= a_{20}y_1'+\Delta y_{10} \\ a_{20} &= {\omega(\Delta_{10},\Delta_{32})+\omega(\Delta_{20},\Delta_{32})-\omega(\Delta_{30},\Delta_{32}) \over \omega(\Delta_{31},\Delta_{32})} \\ a_{01} &= a_{21}x_2'+\Delta x_{20} \\ a_{11} &= a_{21}y_2'+\Delta y_{20} \\ a_{21} &= -{\omega(\Delta_{10},\Delta_{31})+\omega(\Delta_{20},\Delta_{31})-\omega(\Delta_{30},\Delta_{31}) \over \omega(\Delta_{31},\Delta_{32})} \\ a_{02} &= x_0' \\ a_{12} &= y_0', \\ \end{align}$$ where $\Delta_{ij}=q_i'-q_j'$, $\Delta x_{ij}$ and $\Delta y_{ij}$ are the corresponding coordinate deltas, and $\omega$ is the symplectic form $\omega(\mathbf u, \mathbf v) = u_xv_y-u_yv_x$. (That this looks like a lot of cross products is no coincidence—there’s a geometric interpretation of the solution as the intersection of various planes.)

Since you’re mainly interested in mapping from a quadrilateral to a rectangle, it might be more efficient, and probably more computationally stable, to compute $A^{-1}$ directly from the corner coordinates. It’s similar to the solution for the other direction, but I’ll leave that calculation to you.