Algorithms for Automatic Matching of Polygons or Closed Curves Derived from Different Images

Automation in 3-dimension (3D) object reconstruction is a relevant and challenging task, both from a practical and scientific point of view. This paper deals with two basic non-planar primitive objects—spatial polygons and 3D closed curves. To achieve 3D information from a pair of images, with known interior and exterior orientations, it is necessary to first extract t2D objects from each of the images separately, then match the objects to find homologues points between them, and finally reconstruct the 3D object. The matching problem between two objects derived from two different images, has a trivial solution: For each point in the first object the corresponding homologous point in the second object can be found by intersecting its epipolar line and the second object in the second image space. However, because extraction of objects in the image space is performed automatically, the process often fails. For example, when there are a number of intersections per point there is no intersection at all, or there are more points than those existing in the “real” 3D object. To overcome these difficulties, innovative algorithms designed to enable a maximal matching between polygons or closed curves and to find homologues points between them were developed. The algorithms are iterative and are based on the “overlapping criterion” between the objects. According to this criterion, projection of two polygons or closed curves from the image space to any planar surface using the real depths leads to a maximal matching between the objects. The suggested process is based on the well known optimization model called “adjustment by conditions.” One of the 2D polygons or closed curves is chosen as the static object and the other is the dynamic object. The unknowns in this model are the real depths of each point in the dynamic object. The points in the dynamic object are assigned a previously calculated average depth. In each iteration, these depths are updated until the conditional equation is optimized. During the iterations the dynamic object “slides” in the direction of the epipolar line in the image space of the static object. The “slide” rate is not constant because it depends on the varying depths of each point. The iteration process stops when the maximum overlap between the static and dynamic objects is achieved in the image space of the static object. In this paper, the algorithms, the experiments, and the results are detailed.