by Mariano Tepper, Pablo Musé, Andrés Almansa, Marta Mejail
Abstract:
Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka's algorithm by using nearest neighbors search structures to reduce significantly time and memory performances. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algorithms on large low-dimensional datasets by several orders of magnitude. Finally, to illustrate the usefulness of the proposed algorithm, we focus on a classical computer vision problem: image segmentation. We modify a state-of-the-art local graph-based clustering algorithm, thus permitting a global scene analysis.
Reference:
Boruvka Meets Nearest Neighbors (Mariano Tepper, Pablo Musé, Andrés Almansa, Marta Mejail), In (CIARP 2013) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (José Ruiz-Shulcloper, Gabriella Sanniti di Baja, eds.), Springer, 2013.
Bibtex Entry:
@inproceedings{Tepper2011b,
Abstract = {Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka's algorithm by using nearest neighbors search structures to reduce significantly time and memory performances. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algorithms on large low-dimensional datasets by several orders of magnitude. Finally, to illustrate the usefulness of the proposed algorithm, we focus on a classical computer vision problem: image segmentation. We modify a state-of-the-art local graph-based clustering algorithm, thus permitting a global scene analysis.},
Address = {CIARP 2013, Havana, Cuba},
Author = {Tepper, Mariano and Mus\'{e}, Pablo and Almansa, Andr\'{e}s and Mejail, Marta},
Booktitle = {(CIARP 2013) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications},
Chapter = {Lecture No},
Date-Added = {2015-02-18 16:43:18 +0000},
Date-Modified = {2015-02-18 16:43:18 +0000},
Doi = {10.1007/978-3-642-41827-3\_70},
Editor = {Ruiz-Shulcloper, Jos\'{e} and di Baja, Gabriella Sanniti},
Isbn = {978-3-642-41826-6},
Keywords = {Boruvka,global analysis,large datasets,minimum spanning tree,nearest neighbors search,type/conference},
Month = nov,
Pages = {560--567},
Publisher = {Springer},
Title = {{Boruvka Meets Nearest Neighbors}},
Url = {http://iie.fing.edu.uy/~pmuse/docs/papers/tepper\_2013\_CIARP.pdf},
Year = {2013},
Bdsk-Url-1 = {http://iie.fing.edu.uy/~pmuse/docs/papers/tepper%5C_2013%5C_CIARP.pdf},
Bdsk-Url-2 = {http://dx.doi.org/10.1007/978-3-642-41827-3%5C_70}}