A labeling algorithm based on a forest of decision trees

摘要

Connected component labeling (CCL) is one of the most fundamental operations in image processing. CCL is a procedure for assigning a unique label to each connected component. It is a mandatory step between low-level and high-level image processing. In this work, a general method is given to improve the neighbourhood exploration in a two-scan labeling. The neighbourhood values are considered as commands of a decision table. This decision table can be represented as a decision tree. A block-based approach is proposed so that values of several pixels are given by one decision tree. This block-based approach can be extended to multiple connectivities, 2D and 3D. In a raster scan, already seen pixels can be exploited to generate smaller decision trees. New decision trees are automatically generated from every possible command. This process creates a decision forest that minimises the number of memory accesses. Experimental results show that this method is faster than the state-of-the-art labelling algorithms and require fewer memory accesses. The whole process can be generalised to any given connectivity.