ML Anthology

Connected Component Labeling on Polymorphic Torus Architecture

Massimo Maresca, Hungwen Li, Mark A. Lavin
CVPR 1988 pp. 951-956
doi:10.1109/CVPR.1988.196347 /cvpr/1988/maresca1988cvpr-connected/

Abstract

A parallel algorithm is presented for labeling the connected components of multicolored digital images. The algorithm takes advantage of the bottom-up divide-and-conquer strategy applied in tree and pyramid architectures but only requires a mesh topology. To support nonlocal communication, where meshes perform poorly, the authors propose the polymorphic torus, a regular mesh interconnection network in which each node is able to dynamically interconnect its ports, depending on its own data. By having each node properly drive such an interconnection, communication links between processors get established and disconnected and, as a result, the effective network diameter is reduced. The proposed connected-component labeling algorithm requires O( square root n) steps for a square root n* square root n multicolored image of an n-processor polymorphic torus, which is the same performance achieved in a tree architecture with 2n-1 processors. The lower number of processors and the simpler topology of polymorphic torus (vs. tree) make it a very suitable approach to mesh augmentation for intermediate-level vision applications.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

CVPR Semantic Scholar

Cite

Text

Maresca et al. "Connected Component Labeling on Polymorphic Torus Architecture." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988. doi:10.1109/CVPR.1988.196347

Markdown

[Maresca et al. "Connected Component Labeling on Polymorphic Torus Architecture." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988.](https://mlanthology.org/cvpr/1988/maresca1988cvpr-connected/) doi:10.1109/CVPR.1988.196347

BibTeX

@inproceedings{maresca1988cvpr-connected,
  title     = {{Connected Component Labeling on Polymorphic Torus Architecture}},
  author    = {Maresca, Massimo and Li, Hungwen and Lavin, Mark A.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1988},
  pages     = {951-956},
  doi       = {10.1109/CVPR.1988.196347},
  url       = {https://mlanthology.org/cvpr/1988/maresca1988cvpr-connected/}
}