This is an RFC for the implementation of a multithreaded version of the connected component labeling algorithm.

Such algorithms have appeared in research papers since a few years ago. A common theme in these approaches is to divide the image into blocks (tiles or strips), and then:

1. Perform labeling within each block, in parallel;
2. Let the main (caller) thread process the equivalence labeling of "seams" between blocks;
3. Update the labeling in each block to the final labeling, in parallel.

The second step is single-threaded. As a result there is a synchronization barrier before and after the second step.

I ask this question here instead of OpenCV Answers because it is not a beginner question, and I believe this is a feature that will eventually be implemented in (contributed to) OpenCV. A second reason I ask this is because I have implemented a proprietary version of it for my employer. I have secured the permissions to make a separate implementation for OpenCV provided that the implementation details in the contributed version can be fully traced to research work that has already been published.

I am aware of the existing connected component labeling implementation in OpenCV and has studied the algorithm. However, it is too early for me to say whether I will be able to keep the best of both implementations.

One minor detail is that my current (proprietary) implementation uses a more flexible definition of connectivity, one which is traditionally termed "flat-zones CCL". This flexible definition allows caller to specify two predicates:

1. isForeground ( point ) -> bool
2. isConnected ( pointOne, pointTwo ) -> bool

The foreground predicate is given the pixel value, and returns whether it will be assigned a label. All non-foreground pixels will be given a nondescript pseudo-label.

If two pixels are adjacent (according 4 or 8 neighborhood), and both pixels are foreground, then the connectivity predicate will be invoked. The two pixels will be connected if and only if all these conditions are satisfied.

The current OpenCV implementation corresponds to the imposed restrictions that:

1. Image must be CV_8UC1 or CV_8SC1
2. isForeground is currently hard-coded as Image(row, col) != 0
3. isConnected must return true, i.e. two pixels which are both foreground and adjacent, must be connected by definition.

(Note: in the current OpenCV implementation, Wu's implementation defines foreground as Image(row, col) != 0, whereas Grana's implementation defines foreground as Image(row, col) > 0. This difference may be pose problem for CV_8SC1 input image type.)

The significance of this flexibility is that it allows for the possibility that two pixels which are both foreground to be disconnected, by a suitable choice of connectivity predicate. This flexibility is required in the implementation of some image processing algorithms.

On the other hand, this predicate flexibility is incompatible with some CCL optimization techniques, such as Grana et al. For this reason, users who provide isConnected predicate should indicate whether it is a trivial implementation (one that always return true), so that all optimization techniques can be applied.

The predicate will need to be supplied as a functor to a class template.

I haven't started working on this second implementation yet; so I would like to solicit some feedback about the desirability of this feature before I start. Please feel free to ask questions.

I understand that performance benchmarks will help make an informed decision. Please feel free to suggest performance benchmark scenarios that I should test for.