pose averaging; distributed optimization; multi-agent systems
Résumé :
[en] This paper addresses synchronization of Euclidean transformations over graphs. Synchronization in this context, unlike rendezvous or consensus, means that composite transformations over loops in the graph are equal to the identity. Given a set of non-synchronized transformations, the problem at hand is to find a set of synchronized transformations approximating well the non-synchronized transformations. This is formulated as a nonlinear least-squares optimization problem. We present a distributed synchronization algorithm that converges to the optimal solution to an approximation of the optimization problem. This approximation stems from a spectral relaxation of the rotational part on the one hand and from a separation between the rotations and the translations on the other. The method can be used to distributively improve the measurements obtained in sensor networks such as networks of cameras where pairwise relative transformations are measured. The convergence of the method is verified in numerical simulations.
Disciplines :
Ingénierie électrique & électronique
Auteur, co-auteur :
THUNBERG, Johan ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
GONCALVES, Jorge ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Bernard, Florian; Saarland Informatics Campus > Max Planck Institute for Informatics
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Distributed synchronization of euclidean transformations with guaranteed convergence
R. Aragues, C. Sagues, and Y. Mezouar, Parallel and Distributed Map Merging and Localization: Algorithms, Tools and Strategies for Robotic Networks. Springer, 2015.
R. Tron and R. Vidal, "Distributed 3-d localization of camera sensor networks from 2-d image measurements, " Transactions on Automatic Control, vol. 59, no. 12, pp. 3325-3340, 2014.
E. Montijano, D. Zhou, M. Schwager, and C. Sagues, "Distributed formation control without a global reference frame, " in American Control Conference (ACC), 2014. IEEE, 2014, pp. 3862-3867.
F. Bernard, J. Thunberg, A. Husch, L. Salamanca, P. Gemmar, F. Hertel, and J. Goncalves, "Transitively consistent and unbiased multiimage registration using numerically stable transformation synchronisation, " in MICCAI Workshop on Spectral Analysis in Medical Imaging (SAMI), 2015.
K. Arun, T. Huang, and S. Blostein, "Least-squares fitting of two 3- D point sets, " IEEE Transactions on Pattern Analysis and Machine Intelligence, no. 5, pp. 698-700, 1987.
J. Gower and G. Dijksterhuis, Procrustes problems. Oxford University Press Oxford, 2004, vol. 3.
P. Schonemann, "A generalized solution of the orthogonal procrustes problem, " Psychometrika, vol. 31, no. 1, pp. 1-10, Mar. 1966.
B. Horn, H. Hilden, and S. Negahdaripour, "Closed-form solution of absolute orientation using orthonormal matrices, " Journal of the Optical Society of America A, vol. 5, no. 7, p. 1127, 1988.
F. Bernard, J. Thunberg, P. Gemmar, F. Hertel, A. Husch, and J. Goncalves, "A Solution for Multi-Alignment by Transformation Synchronisation, " in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2015.
N. Boumal, "A riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints, " arXiv preprint arXiv:1506.00575, 2015.
V. Govindu, "Lie-algebraic averaging for globally consistent motion estimation, " in Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR. IEEE, 2004.
V. Govindu, "Robustness in motion averaging, " in Computer Vision-ACCV 2006. Springer, 2006, pp. 457-466.
V. Govindu and A. Pooja, "On averaging multiview relations for 3d scan registration, " Transactions on Image Processing, vol. 23, no. 3, pp. 1289-1302, 2014.
A. Bandeira, A. Singer, and D. Spielman, "A cheeger inequality for the graph connection laplacian, " SIAM Journal on Matrix Analysis and Applications, vol. 34, no. 4, pp. 1611-1630, 2013.
A. Singer, "Angular synchronization by eigenvectors and semidefinite programming, " Applied and computational harmonic analysis, vol. 30, no. 1, pp. 20-36, 2011.
L. Wang and A. Singer, "Exact and stable recovery of rotations for robust synchronization, " Information and Inference, p. iat005, 2013.
K. Chaudhury, Y. Khoo, and A. Singer, "Global registration of multiple point clouds using semidefinite programming, " arXiv.org, Jun. 2013.
R. Hadani and A. Singer, "Representation theoretic patterns in three dimensional Cryo-Electron Microscopy I: The intrinsic reconstitution algorithm, " Annals of mathematics, vol. 174, no. 2, p. 1219, 2011.
R. Hadani and A. Singer, "Representation Theoretic Patterns in Three-Dimensional Cryo- Electron Microscopy II-The Class Averaging Problem, " Foundations of computational mathematics (New York, N.Y.), vol. 11, no. 5, pp. 589-616, 2011.
A. Singer and Y. Shkolnisky, "Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming, " SIAM journal on imaging sciences, vol. 4, no. 2, pp. 543-572, Jun. 2011.
D. Pachauri, R. Kondor, and V. Singh, "Solving the multi-way matching problem by permutation synchronization, " in Advances in neural information processing systems, 2013, pp. 1860-1868.
M. Cucuringu, Y. Lipman, and A. Singer, "Sensor network localization by eigenvector synchronization over the euclidean group, " ACM Transactions on Sensor Networks (TOSN), vol. 8, no. 3, p. 19, 2012.
M. Cucuringu, A. Singer, and D. Cowburn, "Eigenvector synchronization, graph rigidity and the molecule problem, " Information and Inference, vol. 1, no. 1, pp. 21-67, 2012.
J. Thunberg, F. Bernard, and J. Goncalves, "Distributed methods for synchronization of orthogonal matrices over graphs, " Automatica, to appear, 2017.
R. Hartley, J. Trumpf, Y. Dai, and H. Li, "Rotation averaging, " International journal of computer vision, vol. 103, no. 3, pp. 267- 305, 2013.
J. Keller, "Closest unitary, orthogonal and hermitian operators to a given operator, " Mathematics Magazine, vol. 48, no. 4, pp. 192-197, 1975.
J. Thunberg, F. Bernard, and J. Goncalves, "On transitive consistency for linear invertible transformations between euclidean coordinate systems, " arXiv preprint arXiv:1509.00728, 2015.
