Find Connected Components in a binary Image

connectedComponents computes the connected components (i.e. areas of contiguous non-zero pixels) of a binary image.

Usage

connectedComponents(
  image,
  connectivity = 8,
  algorithm = "bolelli",
  table = TRUE,
  stats = TRUE,
  target = "new"
)

Arguments

image

An an 8-bit (8U) single-channel Image object.

connectivity

The connectivity neighborhood to decide whether 2 pixels are contiguous. This parameter can take two values:

4:: the neighborhood of a pixel are the four pixels located above (north), below (south), to the left (west) and right (east) of the pixel.
8 (the default):: the neighborhood of a pixel includes the four 4-neighbors and the four pixels along the diagonal directions (northeast, northwest, southeast, and southwest).

algorithm

A character string specifying the connected components labeling algorithm to use. This parameter can take six values:

"grana"/"BBDT":: BBDT algorithm for 8-way connectivity, SAUF algorithm for 4-way connectivity.
"wu"/"SAUF":: SAUF algorithm for 8-way connectivity, SAUF algorithm for 4-way connectivity.
"bolelli"/"spaghetti" (the default):: Spaghetti algorithm for 8-way connectivity, Spaghetti4C algorithm for 4-way connectivity.

table

A boolean indicating whether the coordinates of the pixels of each component should be returned.

stats

A boolean indicating whether the statistics of the connected components should be returned.

target

The location where the results should be stored. It can take 2 values:

"new":: a new Image object is created and the results are stored inside (the default).
An Image object:: the results are stored in another existing Image object. In this case, target must be a single channel image with a 16U or 32S bit depth. Note that this will replace the content of target.

Value

A list with 1 to 4 items:

n:: the number of connected components in the image. It is always returned.
table:: if table=TRUE, a matrix with 3 columns representing the identity of the connected components (label), and the x-y coordinates of the pixels they are composed of.
stats:: if stats=TRUE, a matrix with 8 columns representing the identity of the connected components (label), the x-y coordinates of their centroidd, the left and top coordinates of their bounding boxes, the width and height of their bounding boxes, and their surface areas in pixels.
labels:: if target="new" a 32S single-channel image in which each pixel of each connected component is represented by the identity number of the component, and the background pixels by zero.

References

Costantino Grana, Daniele Borghesani, and Rita Cucchiara. Optimized Block-Based Connected Components Labeling With Decision Trees. IEEE Transactions on Image Processing, 19(6):1596–1609, 2010.

Kesheng Wu, Ekow Otoo, and Kenji Suzuki. Optimizing two-pass connected-component labeling algorithms. Pattern Analysis and Applications, 12(2):117–135, Jun 2009.

Federico Bolelli, Michele Cancilla, and Costantino Grana. Two More Strategies to Speed Up Connected Components Labeling Algorithms. In Image Analysis and Processing - ICIAP 2017, volume 10485, pages 48–58. Springer, 2017.

Federico Bolelli, Stefano Allegretti, Lorenzo Baraldi, and Costantino Grana. Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Connected Components Labeling. IEEE Transactions on Image Processing, 29(1):1999–2012, 2019.

Federico Bolelli, Stefano Allegretti, and Costantino Grana. One dag to rule them all. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.

Author

Simon Garnier, garnier@njit.edu

Examples