Article Preview
TopIntroduction
The identification of objects in the context of exploring scientific data is a research subject with application in many areas. To name a few, its applicability spans from the fields of materials science and computer vision to physics in general.
In this work, we are particularly interested in identifying objects from samples of composite materials obtained with micro-tomography. Once identified such objects, we then can characterize in detail their physical properties such as volume, surface area, form factor, orientation and structural integrity.
This goal closely relates to the problem of identifying which data elements belong to a particular connected object. This is a computational problem generally described as connected component labeling. For that purpose, the algorithms of type union-find are highly regarded as good solutions for the problem.
In graph theory, these algorithms provide the solution to the general question of whether two different nodes in an undirected graph are connected or not. In answering such question these algorithms can be used to compute all partitions of nodes that are connected with each other. The two fundamental operations are the union – that joins two disjoint partitions, connecting them – and the find operation – that discovers if two different nodes are connected.
For 2D and 3D images (or volumetric datasets), nodes are usually the pixels or voxels and connectivity can be defined along the faces, edges or vertices of samples sharing some common property (usually the same data value).
Figure 1 shows a possible outcome of connected component labeling applied to a 2D binary image using edge-connectivity. Data values are black and white, with white values representing the connected structures to be uniquely identified.
Figure 1. Connected-component labeling in a 2D binary image
Prior to the object identification itself, raw data samples are in general filtered. This pre-processing stage involves operations such as removal of noise, erosion and dilation. Among them, there is an important operation called segmentation, which collapses ranges of data values into a single distinct and representative value. Once applied, it will be guaranteed that some entities will have a common attribute or data value, which is a crucial property for the identification of connected entities further down the pipeline.
In analyzing composite materials, we usually are in the presence of 3 distinct data values: air, matrix and reinforcements, but it is very common to work with binary-segmented data where one of the values represents the structures to be analyzed, that is, matrix or reinforcements.
As each object will have been assigned with a unique label, one can easily find out their constituting entities allowing not only its easier visualization, but also the extraction of important information for the characterization of the object itself.
The organization of the remaining of the paper is as follows: the next section presents related work, focusing both sequential and parallel proposals; after that we present our solution in detail, as well as some optimizations we considered, followed by results. Finally, we draw some conclusions and identify further work directions.