Algorithms for Recognizing Planar Polygonal Configurations Using Perspective Images

We consider a simplified abstraction of the problem of recognizing planar arrangements of objects using camera pictures taken from unknown positions. A set of polygons in plane 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. We present an optimal 0(nlogn) time algorithm to solve this problem, where n is the total number of vertices of polygons in each image. Our algorithm is obtained by combining the 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.