spatstat (version 1.56-1)

connected: Connected components

Description

Finds the topologically-connected components of a spatial object, such as the connected clumps of pixels in a binary image.

Usage

connected(X, …)
# S3 method for owin
connected(X, …, method="C")
# S3 method for im
connected(X, …, background = NA, method="C")

Arguments

X

A spatial object such as a pixel image (object of class "im") or a window (object of class "owin").

background

Optional. Treat pixels with this value as being part of the background.

method

String indicating the algorithm to be used. Either "C" or "interpreted". See Details.

…

Arguments passed to as.mask to determine the pixel resolution.

Value

A pixel image (object of class "im") with factor values. The levels of the factor correspond to the connected components.

Warnings

It may be hard to distinguish different components in the default plot because the colours of nearby components may be very similar. See the Examples for a randomised colour map.

The algorithm for method="interpreted" can be very slow for large images (or images where the connected components include a large number of pixels).

Details

The function connected is generic, with methods for pixel images (class "im") and windows (class "owin") described here. There are also methods for tessellations (connected.tess), point patterns (connected.ppp and connected.lpp), and linear networks (connected.linnet).

The functions described here compute the connected component transform (Rosenfeld and Pfalz, 1966) of a binary image or binary mask. The argument X is first converted into a pixel image with logical values. Then the algorithm identifies the connected components (topologically-connected clumps of pixels) in the foreground.

Two pixels belong to the same connected component if they have the value TRUE and if they are neighbours (in the 8-connected sense). This rule is applied repeatedly until it terminates. Then each connected component contains all the pixels that can be reached by stepping from neighbour to neighbour.

If method="C", the computation is performed by a compiled C language implementation of the classical algorithm of Rosenfeld and Pfalz (1966). If method="interpreted", the computation is performed by an R implementation of the algorithm of Park et al (2000).

The result is a factor-valued image, with levels that correspond to the connected components. The Examples show how to extract each connected component as a separate window object.

References

Park, J.-M., Looney, C.G. and Chen, H.-C. (2000) Fast connected component labeling algorithm using a divide and conquer technique. Pages 373-376 in S.Y. Shin (ed) Computers and Their Applications: Proceedings of the ISCA 15th International Conference on Computers and Their Applications, March 29-31, 2000, New Orleans, Louisiana USA. ISCA 2000, ISBN 1-880843-32-3.

Rosenfeld, A. and Pfalz, J.L. (1966) Sequential operations in digital processing. Journal of the Association for Computing Machinery 13 471-494.

See Also

connected.ppp, connected.tess, connected.lpp, connected.linnet, im.object, tess

Examples

# NOT RUN {
  d <- distmap(cells, dimyx=256)
  X <- levelset(d, 0.07)
  plot(X)
  Z <- connected(X)
  plot(Z)
  # or equivalently
  Z <- connected(d <= 0.07)

  # number of components
  nc <- length(levels(Z))
  # plot with randomised colour map
  plot(Z, col=hsv(h=sample(seq(0,1,length=nc), nc)))

  # how to extract the components as a list of windows
  W <- tiles(tess(image=Z))
# }