Sets of Points

Consider 2 photos P and Q. These can be viewed as sets of points P= {p1 , p2 ,..., pN } and Q={q1 , q2 ,..., qN } where the pi 's and qi's are points ( x , y ) in the plane. We first merge Q with P so that no point of Q lies on a point of P.

The crucial observation is the following:

Suppose there exists a position of P and Q such that we can find a one-to-one mapping f from P to Q, for which the lines defined by the pairs of points ( pi , f(pi )) are parallel (see figure 1).
Then it is possible to construct a set of points R={ ri }, i=1,...,N such that P and Q are orthogonal projections of R.

This can be done as follows:

1. Rotate the plane P so that P and Q are orthogonal.
2. Draw the lines Lp1,Lp2 ,...,LpN orthogonal to P passing through p1,p2 ,...,pN.
3. Similarly, draw the lines Lf(p1), Lf(p2) ,..., Lf(pN) orthogonal to Q passing through f (p1), f (p2) ,..., f (pN).
4. For all i=1,..,N, the line Lpi intersects Lf(pi) at a point ri .

It's clear that the set R={ ri }i=1,..,N satisfies our conditions (see figure 2).

The problem of constructing R can therefore be reduced to the one of finding the appropriate position for P and Q together with the bijection f.

We will first discuss the labelled case, that is the case where the bijection f is known.

Labelled case:

Given pairs of points (pi , qi=f(pi )), where i=1,...,N, we'd like to find a position of P for which the lines p1q1 , p2q2 ,..., pnqn are parallel. We proceed in the following manner:

Let's fix a point p* belonging to P, say p1. For all points pj in P, we rotate pj about p* by an angle t. Consider the lines pj qj ( j=1,...,N ). Their slopes will vary as the angle of rotation about p* changes.

Denote by sj ( t ) the slope functions of the lines joining pj and qj ( j=1,...,N ). We want to find a value of t for which the lines pj qj ( j=1,...,N ) are parallel.

This is true if and only if sj ( t ) = s for all j=1,...,N for some value of t and some constant s. How do we find t? We just pick a slope function, say s1 ( t ), and compute its intersections with the remaining n-1 slope functions. If a value t* of t that satisfies the above condition exists, then all n-1 functions must cross s1 ( t ) at a common point.

It can be shown that the functions sj ( t ) can be broken down into four alternately increasing and decreasing pieces. This implies that the maximum number of crossings between two such functions is 4 (constant). Therefore, checking for all possible intersections between s1 ( t ) and the remaining n-1 functions takes linear time and space.

Let's now consider the unlabelled case.

Unlabelled case:
The idea is essentially the same as for the labelled case, except that we now need to consider all possible combinations of points p and q, where p is in P and q is in Q. There are O( n2 ) such combinations. Hence, we now have O( n2 ) slope functions si j ( t ) corresponding to the O( n2 ) lines.

As before, we pick a slope function s1 1( t ) and compute for each of its four monotone (ie either increasing or decreasing) pieces its intersections with the remaining O( n2 ) functions. For each piece, we sort the resulting intersections in O ( n2 log n2 ) = O ( n2 log n ) to determine if n of them are repeated.

This whole procedure can therefore be accomplished in O ( n2 log n ) time and O ( n2 ) space.