Algorithms for recognizing planar polygonal configurations using perspective images

A simplified abstraction of the problem of recognizing planar arrangements of objects using camera pictures taken from unknown positions is considered. A set of polygons in planes is called a planar polygonal configuration. Given perspective images P and Q corresponding to planar polygonal configurations, the matching problem is to determine if P and Q correspond to the same configuration. An optimal θ (n log n) time algorithm is presented to solve this problem, where n is the total number of vertices of polygons in each image. The algorithm is obtained by combining ideas of cross ratios, which are well known to be invariant under perspective projections, and the first fundamental theorem of perspective projections. This algorithm has been implemented and tested with satisfactory results