Excerpt
from the dissertation "A Parallel and Resource-Efficient Single Lookup
Connected Components Analysis Architecture for Reconfigurable Hardware",
Michael J. Klaiber, University of Stuttgart, Stuttgart 2016.
The usage of the term connected components labelling and its definition is quite consistent in the academic literature, whereas connected components analysis varies in terms of both, terminology and problem definition.
Rosenfeld et al. [102] define connected components labelling as the “[c]reation of a labeled image in which the positions associated with the same connected component of the binary input image have a unique label.” Shapiro et al. [112] define CCL as
an operator whose “input is a binary image and [...] output is a symbolic image in which the label assigned to each pixel is an integer uniquely identifying the connected component to which that pixel belongs.”
There is no consensus on the definition of connected components analysis in the
academic literature. It is often used interchangeably with CCL [37, 40]. A more
extensive definition is given by Shapiro et al. [112]: “Connected component analysis consists of connected component labelling of the black pixels followed by property measurement of the component regions and decision making.” The definition for connected components analysis used in the following chapters is more general, taking the thoughts expressed in [37, 40, 112] into account.
Definition 1. Connected components analysis derives one feature vector of each
connected component in a binary 2-D input image. A feature vector of a connected component is an n-tuple composed of functions of the component’s pattern [45].
The derivation of feature vectors does not necessarily require a fully labelled image. Figure 1.1 depicts an example for the input and output data of connected components analysis. The input for both CCL and CCA is a binary 2-D image. CCL assigns the same label to all pixels of one connected component. The output is, therefore, a 2-D array of labels - a labelled image. CCA derives the feature vector for each of the connected components in the input image, such as the bounding box or area of each connected component. Feature vectors can also be extracted from the output of CCL. However, this is an additional step which is not a part of CCL.
Figure 1.1: Definition of input and output data for connected components analysis.
[37] Y. Fu, X. Chen, and H. Gao, “A new connected component analysis algo- rithm based on max-tree,” in 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing. IEEE, 2009, pp. 843–844.
[40] C. Grana, D. Borghesani, P. Santinelli, and R. Cucchiara, “High performance connected components labeling on FPGA,” in Workshop on Database and Expert Systems Applications (DEXA), Sep 2010, pp. 221 –225.
[102] A. Rosenfeld and J. L. Pfaltz, “Sequential operations in digital picture pro- cessing,” Journal of the ACM, vol. 13, pp. 471–494, Oct 1966.
[112] L. G. Shapiro, “Connected component labeling and adjacency graph con- struction,” Machine Intelligence and Pattern Recognition, vol. 19, pp. 1–30, 1996.
(C) 2016 Michael J. Klaiber
