A probabilistic algorithm is presented for finding correspondences across multiple images in systems with large numbers of
cameras and considerable overlap. The algorithm employs the theory of random graphs to provide an efficient probabilistic
algorithm that performs Wide-baseline Stereo (WBS) comparisons on a small number of image pairs, and then propagates correspondence
information among the cameras. A concrete mathematical analysis of its performance is given. The algorithm is extended to
handle false-positive and false-negative failures of the WBS computations. We characterize the detectability of the existence
of such failures, and propose an efficient method for this detection. Based on this, we propose a heuristic method for discarding
false matches, and demonstrate its effectiveness in reducing errors.
Since in many multi-camera applications cameras are attached to processors that handle local processing and communication,
it is natural to consider distributed solutions that make use of the local processors and do not use a central computer. Our algorithm is especially suited to
run in a distributed setting. If the local processors are sufficiently powerful, this allows an order of magnitude increase
in computational efficiency. More importantly, a distributed implementation provides strong robustness guarantees, and eliminates
the existence of a single point of failure that is inherent when the application is coordinated by a central computer. We
show how to efficiently overcome processor crashes and communication failures with a minimal reduction in the quality of the
algorithm’s results.
Keywords correspondence - wide baseline stereo - multi-view - distributed vision - random graphs - error correction - fault tolerance - distributed multi-camera system
This paper is an extension of Avidan et al. (2004), which appeared in ECCV-04.