Connected Component Labeling

Question

In OpenCV 3.0 there is a function called connectedComponent.

I know that it takes as input a binary image and returns the labels and the number of connected components, but what algorithm is used internally?

Answer 1

OpenCV is open source. You can look at the documentation and the source code.

You can choose 2 algorithms to perform connected component lablelling:

• CCL_WU: Based on

  "Two Strategies to Speed up Connected Components Algorithms", the SAUF (Scan array union find) variant using decision trees, Kesheng Wu, et al.

• CCL_GRANA: Based on

  "Optimized Block-based Connected Components Labeling with Decision Trees", Costantino Grana et al

  This works only for 8-connected components.

The default in OpenCV >= 3.2 (CCL_DEFAULT) uses Wu's algorithm for 4-connectivity, and Grana's algorithm for 8 connectivity.

In OpenCV 3.0.0 you use Wu's algorithm for both 4 and 8 connectivity, while in OpenCV >= 3.2 you can choose one of the 3 options, according to the fields connectivity and ccltype:

       \  connectivity   4    |   8
        \                     |
type     \                    |
                              |
CCL_DEFAULT              Wu   |  Grana
CCL_WU                   Wu   |  Wu
CCL_GRANA                Wu   |  Grana

Answer 2

You can read about connected component labeling algorithms in numerous sources

OpenCV implementation is here and contains this clue:

 //Based on "Two Strategies to Speed up Connected Components Algorithms", 
 //the SAUF (Scan array union find) variant
 //using decision trees
 //Kesheng Wu, et al

Article