Verification of photos

The reconstruction of photos is a variant of the reconstruction problem. We are now given a photo P of a set of points together with a set of points S in space. The verification process consists in determining whether P is a photo of S or not.

figure 4

If the photo and the set of points are both labelled, the verification can be done in O(n) time and space, using the following idea:
q1q2 is the projection of p1p2 so the direction of projection D is such that equation where alpha is the angle between D and p1p2, as illustrated below:
figure 5

In the space, you can easily notice that there still exists an infinite number of directions D that fit this statement. However, if we apply the same reasoning with p1p3, there remain at most 4 possible directions of projection. So the verification for each pipi+1 can be done in linear time.

 

Now, if both sets are unlabelled, the verification can be done in O(n3log(n)) time and linear space. To do it, we check the projection of the antipodal pairs. Here is an algorithm to illustrate it:

1. Find the diameter of the polygon Q on the photo. Label q1 and q2 the two ends of the diameter.
2. Find all antipodal pairs which have supporting planes with distance d( q1, q2).
3. For each pair of such supporting planes :
a. Compute the projection on a plane perpendicular to the supporting planes.
b. Translate that projection so that its diameter matches the diameter of Q.
c. If the projection coincides with Q, return true.

 

Note: Antipodal pairs in a convex polygon and rotating calipers:

Two vertices form an antipodal pair if there exist two parallel lines going through each of these points such that all the points of the polygon lie between these two lines.

Antipodal Pairs

The rotating calipers method is a method to find all antipodal pairs of a convex polygon, and therefore its diameter, in linear time. The idea is to use two parallel lines like calipers and to rotate them around the polygon.

Rotating Calipers