A labeling algorithm based on a forest of decision trees
- PDF / 2,004,115 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 53 Downloads / 219 Views
ORIGINAL RESEARCH PAPER
A labeling algorithm based on a forest of decision trees T. Chabardès1,2 · P. Dokládal1 · M. Bilodeau1 Received: 20 February 2019 / Accepted: 5 September 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract 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. Keywords Connected component labelling · Algorithm · Decision tree · Optimisation
1 Introduction Due to its importance in vision, connected component labeling (CCL) has a long history of research efforts. The first algorithms were proposed more than 50 years ago. The CCL algorithms can be grouped into three categories, based on the methodology adopted for the scan over the image: • Two-scan [11, 17–19, 24, 28, 29, 31, 35]: A first raster
scan of the image is made producing redundant labels. Redundancies are stored in an equivalence table and solved so that all redundant set of labels are linked to one final label. A final scan updates the labels produced by the first scan, exploiting the solved equivalence table. • Multi-scan [16, 33]: In two-scan algorithms, the equivalence table requires significant memory. To solve these limitations, multi-scan algorithms were proposed as an * T. Chabardès [email protected] 1
PSL Research University-MINES ParisTech-CMM, Center for Mathematical Morphology, 35 rue Saint Honoré, Fontainebleau, France
Present Address: Terra3D, 36 Boulevard de la Bastille, 75012 Paris, France
2
alternative. By iteratively performing forward and backward raster scan passes, the equivalences are solved without the use of an equivalence table. • Contour tracing CT [4, 5, 8, 9, 22, 26]: Those approaches exploit the inner contour of the objects and require only one scan of the input image and less reads to produce the final labelled image. Grana et al. [14] offers a complete review of the history of the different approaches from the Rosenfeld’s algorithm [28] until the He’s algorithm [18]. In Fig. 1, timelines from Grana et al. [14] are sh
Data Loading...
