Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Baumberg, A.: Reliable feature matching across widely separated views. In: Proc. of IEEE Computer Vision and Pattern Recognition, vol. I, pp. 774–781 (2000)
Bernstein, P.A., Hadzilacos, V., Goodman, N.: Concurrency control and recovery in database systems. Addison-Wesley, Reading (1987)
Bollobas, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)
Bollobas, B., Thomason, A.G.: Random graphs of small order (1985)
Brumitt, B., Krumm, J., Meyers, B., Shafers, S.: Ubiquitous computing and the role of geometry (2000)
Chetverikov, D., Matas, J.: Periodic textures as distinguished regions for wide-baseline stereo correspondence. Texture, 25–30 (2002)
Collins, R., Lipton, A., Kanade, T., Fujiyoshi, H., Duggins, D., Tsin, Y., Tolliver, D., Enomoto, N., Hasegawa, O.: A system for video surveillance and monitoring. CMU-RI-TR (2000)
Collins, R., Tsin, Y.: Calibration of an outdoor active camera system. In: Proc. of IEEE Computer Vision and Pattern Recognition, pp. 528–534 (1999)
Erdos, P., Renyi, A.: On random graphs 1 (1959)
Ferrari, V., Tuytelaars, T., Gool, L.V.: Wide-baseline muliple-view correspondences. In: Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (June 2003)
Karuppiah, D., Zhu, Z., Shenoy, P., Riseman, E.: A fault-tolerant distributed vision system architecture for object tracking in a smart room. In: Schiele, B., Sagerer, G. (eds.) ICVS 2001. LNCS, vol. 2095, p. 201. Springer, Heidelberg (2001)
Levi, N., Werman, M.: The viewing graph. In: Proc. of IEEE Computer Vision and Pattern Recognition (2003)
Lopez de Ipina, D., Mendonca, P.R.S., Hopper, A.: Trip: a low-cost vision-based location system for ubiquitous computing. Personal and Ubiquitous Computing Journal 6 (2002)
Lynch, N.A.: Distributed Algorithms. MIT Press, Cambridge (1996)
Matas, J., Burianek, J., Kittler, J.: Object recognition using the invariant pixel-set signature. In: The British Machine Vision Conference (2000)
Narayanan, P.J.: Virtualized reality: Concepts and early results. In: The IEEE Workshop on the Representation of Visual Scenes (in conjunction with ICCV 1995) (1995)
Pritchett, P., Zisserman, A.: Wide baseline stereo matching. In: Proc. International Conference on Computer Vision, pp. 754–760 (1998)
Mullender, S. (ed.): Distributed Systems. Addison-Wesley, Reading (1993)
Saito, H., Baba, S., Kimura, M., Vedula, S., Kanade, T.: Appearance based virtual view generation of temporally-varying events from multi-camera images in the 3d room. In: Proc. of Second International Conference on 3-D Digital Imaging and Modeling (1999)
Schaffalitzky, F., Zisserman, A.: Viewpoint invariant texture matching and wide baseline stereo. In: Proc. International Conference on Computer Vision, vol. II, pp. 636–643 (2001)
Schaffalitzky, F., Zisserman, A.: Multi-view matching for unordered image sets, or how do I organize my holiday snaps? In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002. LNCS, vol. 2350, pp. 414–431. Springer, Heidelberg (2002)
Tanenbaum, A.S., van Steen, M.: Distributed Systems Principles and Paradigms. Pearson Education publisher, London (2001)
Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W.: Bundle adjustment – a modern synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds.) ICCV-WS 1999. LNCS, vol. 1883, pp. 298–372. Springer, Heidelberg (1999)
Tuytelaars, T., Van Gool, L.: Wide baseline stereo matching based on local, affinely invariant regions. In: The British Machine Vision Conference (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avidan, S., Moses, Y., Moses, Y. (2004). Probabilistic Multi-view Correspondence in a Distributed Setting with No Central Server. In: Pajdla, T., Matas, J. (eds) Computer Vision - ECCV 2004. ECCV 2004. Lecture Notes in Computer Science, vol 3024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24673-2_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-24673-2_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21981-1
Online ISBN: 978-3-540-24673-2
eBook Packages: Springer Book Archive