Finding the 4th point of quadrangle. (After perspective transform)

Question

There is an image of square, and to that image the perspective transform is applied.

So the perspective image of a square will be not a square but a quadrangle. The question:

If I know three corner points of the perspective image (quadrangle) then what will be the fourth corner point of the quadrangle?

The problem also arises because the corner points are given in the image space, not in the world coordinate system. So they have only two coordinates, for example: N1 = (x1, y1), N2 = (x2, y2), N3 = (x3, y3)

And I need to find N4 = (x4, y4) using information that the real image in world coordinates was a square before the perspective transformation was made.

Is it possible to find that 4th point? I think there will not be only one solution of this problem, but I want to know how many solutions we have and I want to get that solutions.

I have read almost the same problem here, but the author didn't say that it was a square before the transformation.

Answer 1

If all you know is the image coordinates after projection, then I don't think you can find coordinates of the fourth point. If you know the side of the square (e.g. 5m in 3D space), and image coordinates w.r.t. the center of projection (not just x,y pixel values but also distance of image plane from center of projection) then you could use any of the methods described in Haralick et. al. to find coordinates of the fourth point.

Answer 2

Suppose we use Wikipedia's example projective transform matrix, and assume you have four points p = {px,py,pz}, p+u, p+v, and p+u+v. Let's assume that the last one is the one you want to find, and u and v are the edge vectors of the square. After transforming, the points get mapped to p -> {px/pz, py/pz, 1}, p+u -> {(px+ux)/(pz+uz), (py+uy)/(pz+uz), 1}, and similarly for p+v and p+u+v. This is all assuming, of course, that neither u or v is in the nullspace of the transform (they are not "aligned toward the camera"). So you have 4 new coordinate pairs which are rational functions of the original real-space 3D coordinates. Your problem is essentially, how do you compute

(px+ux+vx)/(pz+uz+vz) and (py+uy+vy)/(pz+uz+vz)

from

px/pz, py/pz, (px+ux)/(pz+uz), (py+uy)/(pz+uz),
(px+vx)/(pz+vz), and (py+vy)/(pz+vz)

I don't think there is a way to do this. Also, this page seems to indicate any quadrilateral can be mapped to any other quadrilateral by a perspective transform, so it is likely that your problem is ill-posed.

Answer 3

In general, it is not possible. You want to determine an homography (a perspective transformation) between the plane where the original square lies and the image plane by using the knowledge of three correspondences between points but you need four correspondences between points in order to univocally determine a plane homography.

Example of the ambiguity: Let's suppose the original square has its vertices at the points with homogeneous coordinates [0, 0, 1], [1, 0, 1], [1, 1, 1], and [0, 1, 1]. Now consider two homographies given by the following matrices:

H1 = [1, -2, 0;
      0, -1, 0;
      0, -2, 1]

H2 = [-1, 2, 0;
       0, 1, 0;
      -2, 2, 1]

Both transformations leave the first three vertices invariant (remember that two points in a projective space are equal if and only if their vectors differ by a non-zero scale factor) but they transform the fourth vertex to different points.

Answer 4

But this problem has some solutions, I;ve heard that there are some methods of finding four possible fourth corners of quadrangle. So may be there are not many solutions of this task? And what additional information will be enough to find not many solutions of this problem? Also now I am reading about camera calibration, but I think that I will need to calibrate camera evry time to solve the problem. So even if I remember calibration parameters and make program that calibrates the camera automatically, what if camera's condition will change, and it's calibration parameters will also change? In this situation, the old camera parameters will not be correct.