Probabilistic Multi-view Correspondence in a Distributed Setting with No Central Server

We present a probabilistic algorithm for finding correspondences across multiple images. The algorithm runs in a distributed setting, where each camera is attached to a separate computing unit, and the cameras communicate over a network. No central computer is involved in the computation. The algorithm runs with low computational and communication cost. Our distributed algorithm assumes access to a standard pairwise wide-baseline stereo matching algorithm ($\mathcal{WBS}$) and our goal is to minimize the number of images transmitted over the network, as well as the number of times the $\mathcal{WBS}$ is computed. We employ the theory of random graphs to provide an efficient probabilistic algorithm that performs $\mathcal{WBS}$ on a small number of image pairs, followed by a correspondence propagation phase. The heart of the paper is a theoretical analysis of the number of times $\mathcal{WBS}$ must be performed to ensure that an overwhelming portion of the correspondence information is extracted. The analysis is extended to show how to combat computer and communication failures, which are expected to occur in such settings, as well as correspondence misses. This analysis yields an efficient distributed algorithm, but it can also be used to improve the performance of centralized algorithms for correspondence.