Transformation of coordinate set
I can't help with the fisheye lens issue, but assuming that effect isn't too large, the mapping between the above images is a perspective transformation.

We can transform a point on the plane $z=1$ into 3D space using a $3\times 3$ matrix.

$$\left( \begin{array}{c} X\\ Y\\  Z\\ \end{array} \right) =
\left( \begin{array}{c} s_x\ \ h_x\ \ t_x \\ 
                         h_y\ \ s_y\ \ t_y \\
                         p_x\ \ p_y\ \   1 \\ \end{array} \right)
\left( \begin{array}{c} x\\ y\\  1\\ \end{array} \right)$$


$s$ is scaling
$h$ is shearing
$t$ is translation
$p$ is perspective tilting (positive number means positive side tilts away)


We can project this object in 3D space back onto the plane $z=1$ simply by dividing the coordinates by $Z$. This maps every point in space to the intersection of the plane $z=1$ and the line connecting the point and the origin. This is basically the process of taking a photograph.

$$X_{proj} = X/Z$$
$$Y_{proj} = Y/Z$$

What we want to do is find the reverse transformation that takes us from the projected coordinates back to the original coordinates where the points only existed in the plane $z=1$.

It turns out that we can solve for all of the transformation parameters using 4 points (the four corners of a rectangle, for example) and solving the following system of equations (see here for the derivation and some example MATLAB code).



Making certain assumptions like the object not changing size or shape ($s_x=s_y=1$, $h_x=h_y=0$) can simplify these equations.