Title: Triangulation without Correspondences 

Authors: Yong-Qing Cheng, Robert T. Collins, 
Allen R. Hanson, Edward M. Riseman 

Affiliation: Computer Vision Research Laboratory, Dept. of Computer Science,
University of Massachusetts, Box4610, Amherst, MA. 0l003-4610

Abstract:
This paper presents two different algorithms for reconstructing 3D points 
from two sets of noisy 2D image points without knowing  point correspondences 
given the corresponding poses from the two images. We first present a new way 
to form a 2D similarity function between two points from two images via 3D 
pseudo-intersection. Based on principles of proximity and exclusion, the  
first algorithm uses a new affinity measure between 2D image points from two 
different images and a competition scheme to establish image point 
correspondences and recover their corresponding 3D points simultaneously.  
Based on an optimal graph theoretic approach, the second algorithm uses the 
similarity function to construct a bipartite graph, builds a corresponding 
flow network, and finally finds a maximum network flow that determines  
the correspondences between two images. The two proposed algorithms have been 
applied to aerial images from the ARPA RADIUS project. Experimental results 
have shown that the proposed algorithms are robust.

Keywords: Triangulation, correspondences, matching, 3D reconstruction, 
          network flow, principles of proximity and exclusion.