6533b86efe1ef96bd12cc65e

RESEARCH PRODUCT

A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES

Rosalia RendaVito Di GesùFranco Chiavetta

subject

Connected componentDegree (graph theory)Artificial IntelligenceDiscrete spaceBinary imageVisibility (geometry)Parallel algorithmComputer Vision and Pattern RecognitionTime complexityAlgorithmSoftwareMathematicsCylindrical algebraic decomposition

description

In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.

yearjournalcountryeditionlanguage
1992-08-01International Journal of Pattern Recognition and Artificial Intelligence
https://doi.org/10.1142/s0218001492000205