Object Identification in Binary Tomographic Images Using GPGPUs

Object Identification in Binary Tomographic Images Using GPGPUs

Bruno Preto (Department of Informatics, Universidade Nova de Lisboa, Caparica, Portugal), Fernando Birra (Department of Informatics, Universidade Nova de Lisboa, Caparica, Portugal), Adriano Lopes (Department of Informatics, Universidade Nova de Lisboa, Caparica, Portugal) and Pedro Medeiros (Department of Informatics, Universidade Nova de Lisboa, Caparica, Portugal)
DOI: 10.4018/ijcicg.2013070103


The authors present a hybrid OpenCL CPU/GPU algorithm for identification of connected structures inside black and white 3D scientific data. This algorithm exploits parallelism both at CPU and GPGPU levels, but the work is predominantly done in GPUs. The underlying context of this work is the structural characterization of composite materials via tomography. The algorithm allows us to later infer location and morphology of objects inside composite materials. Moreover, execution times are very low thus allowing us to process large data sets, but within acceptable running times. Intermediate solutions are computed independently over a partition of the spatial domain, following the data parallelism paradigm, and then integrated both at GPU and CPU levels, using parallel multi-cores. The authors consistently explore parallelism both at the CPU level, by allowing the CPU stage to run in multiple concurrent threads, and at the GPU level with massive parallelism and concurrent data transfers and kernel executions.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 2 Issues (2020): Forthcoming, Available for Pre-Order
Volume 10: 1 Issue (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing