Efficient 3D Erosion Dilation Analysis by Sub-Pixel EDT

Abstract

The micro-structure of materials or natural substrates contributes significantly to macroscopic properties like mechanical strength or filtration performance. The intrinsic volumes or their densities are versatile geometric characteristics of micro-structures and can be estimated efficiently from 3D binary images whose foreground represents the structure of interest. A recent algorithm generalizes this approach to gray value images. That is, the intrinsic volumes are derived for each possible global gray value threshold in the image in a single pass through the image. Here, it is combined with a sub-pixel precise Euclidean distance transform enabling efficient so-called erosion dilation analysis. That means, the densities of the intrinsic volumes are simultaneously computed not only for the structure itself but also for all erosions and dilations by spherical structuring elements of this structure. That way, the algorithm reveals additional information on the local size of critical features of the structure or its complement. The algorithm’s power is demonstrated by means of computed tomography image data of rigid foams and stacks of scanning electron microscopies of nano-porous membrane layers sliced by a focused ion beam.

1 Introduction

The possibilities and the demand to spatially image materials micro-structures have grown tremendously during the last decade. Image sizes, complexity of the imaged structures, and detail of the analysis tasks grow at even higher speed, increasing the demand for time and memory efficient algorithms yielding quantitative structural information.

One very general image analysis tool are the intrinsic volumes. The intrinsic volumes, also known as Minkowski functionals or quermass integrals [1], are in some sense a basic set of geometric structural characteristics [2]. In 3D, they yield information about the volume, surface, mean and Gaussian curvatures of analyzed structures. Various other characteristics describing for instance shape [3] or structure specific features e. g. for open cell foams [4] can be derived. The densities of the intrinsic volumes, combined with erosions and dilations of the structure under consideration have been studied, e. g. to quantify connectivity [5]. Mecke [6] called them Minkowski functions.

For a given segmentation of the gray value image into the component of interest (foreground) and its complement (background), the intrinsic volumes can be efficiently derived from the resulting binary image by Ohser’s algorithm [7, 8]. In [9], we generalized Ohser’s approach to gray value images enabling fast simultaneous calculation of the intrinsic volumes for all possible threshold values in an integer gray value image.

2 Intrinsic Volumes, Euclidean Distance Transform, and Erosion Dilation Analysis

In this section, we summarize the previous work that is combined in the following Sect. 3 to yield a finer erosion dilation analysis than before as demonstrated by the examples in Sect. 4.

2.1 Intrinsic Volumes Estimated Based on 3D Binary Images

The intrinsic volumes (or their densities) are a widely used system of basic geometric characteristics for micro-structures, see e.g. [10,11,12,13,14]. In 3D, the four intrinsic volumes are volume V, surface area S, integral of mean curvature M, and Euler number $\chi$. For macroscopically homogeneous structures, the densities of the respective characteristics are used – volume fraction $V_V$, specific surface area $S_V$, and the densities of the integrals of mean curvature $M_V$ and of the Euler number $\chi _V$. From these basic characteristics, further descriptors can be derived. Here, we consider in addition to the densities of the intrinsic volumes the structure model index $\mathrm{SMI} = 12 V_V M_V / S^2_V$ that can be interpreted as a shape factor for a macroscopically homogeneous structure [3, 15].

These characteristics can be measured simultaneously and efficiently based on observations restricted to a compact window. The algorithmic idea goes back to [11] and was refined in [8, 16]: The local $2\times 2\times 2$ pixel configurations in a binary 3D image are coded in an 8bit gray value image of the same size by an appropriate convolution. The intrinsic volumes are then derived as scalar product of a suitable weight vector and the gray value histogram h of this image.

2.2 Intrinsic Volumes as Function of Gray Value Threshold in 3D Images

In [9], Ohser’s algorithm was generalized: The local black-or-white pixel configurations induced by thresholding a gray value image are efficiently collected and coded.

For the sake of self-containedness, we repeat the main idea of [9]: Consider the matrix of frequency vectors h(t) for each gray value threshold $t\in {\mathbb R}$. Observe that the contribution of a local $2\times 2\times 2$ pixel configuration $p=(p_1,\dots ,p_8)$ can change not more than eight times – each time one of the pixels’ gray values coincides with the threshold value. Write c(p, t) for the code of pixel configuration p after thresholding with threshold t. Create h(c, t) for all $c\in \{0,\dots ,255\},\ t\in \{0,\dots ,M+1\}$, where M is the image’s maximal gray value, by bookkeeping of changing codes for local pixel configurations, only. Thus $h(\cdot ,t)$ is the configuration frequency vector for the image thresholded at t.

2.3 Linear Time Euclidean Distance Transform

For a binary image representing a discretized realization of a random closed set X intersected by a cuboidal observation window W as foreground, the Euclidean distance transform (EDT) assigns each pixel x in the background $X^C\cap W$ the Euclidean distance to the foreground. Here, we use the signed version additionally assigning each foreground pixel $x\in X\cap W$ the Euclidean distance to the background.

Commonly used algorithms for calculating distance transforms measure the distances w.r.t. the interface of foreground and background. That is, a surface consisting of lattice points and defined by the chosen discrete adjacency.

Classical algorithms for calculating the exact EDT are based on propagating distances observed locally through several passes through the image, separating the coordinate directions. In 3D, this type of algorithm is due to [17]. Maurer and Raghavan [18] were the first to suggest a dimension reduction Voronoi based algorithm for exact Euclidean distances in 3D, linear in the number of image pixels.

2.4 Sub-pixel Precise Euclidean Distance Transform

EDT algorithms using dimension reduction approaches like [18,19,20], allow to use a boundary between lattice points as curve or surface of reference In these cases, distances smaller than one lattice spacing can be observed. Lindblad and Sladoje [21] derive this surface by linear interpolation of the neighbor pixel values and applying a threshold.

The general idea behind [18] is to iteratively process sub-images of successively increasing dimensions, first computing shortest distances within individual lines, then 2D slices, before finally obtaining total distances for the entire 3D image. This algorithm assumes that every lattice point outside of the object of interest counts as a Voronoi generator point to which distances get computed.

Lindblad and Sladoje [21] compute the distance to an object’s surface using sample points as generators that can deviate from lattice lines in one dimension. If the object is implicitly given as an iso-surface of an image, they propose to use linear interpolation between neighboring pixels to obtain the exact location of the surface point.

2.5 Erosion Dilation Analysis

The Minkowski functions as used e.g. in [6] are the intrinsic volumes of the parallel bodies $X\oplus B_r$ and $X\ominus B_r$, respectively, of the structure X with respect to a ball $B_r$ of radius r. That is, the intrinsic volumes of stepwise erosions/dilations of X with a spherical structuring element are considered as functions of the radius r. From these functions, 3D structural information can be directly derived. In particular the specific Euler number as a function of successive erosions was called connectivity function and used to evaluate bond sizes [5]. In [13], the Euler number combined with successive erosions was used to study the connectivity of firn from the B35 core, see also [8].

Morphological erosions and dilations with a spherical structuring element B can be readily obtained by thresholding the EDT image. More precisely, thresholding the EDT image using r is equivalent to an erosion or a dilation of the foreground X by a ball of radius $r\in {\mathbb R}_+$: $X\oplus B_r = \{x: EDT(X,x) < r\}$ and $X\ominus B_r = \{x: EDT(X,x) < -r\}$. The algorithm from [9] efficiently yields the intrinsic volumes of the parallel bodies $X\oplus B_r$ and $X\ominus B_r$.

3 Intrinsic Volumes on Sub-pixel EDT Images for Refined Erosion Dilation Analysis

Here we combine the approach from [21] with the fast algorithm for the precise EDT by [18] to achieve sub-pixel precision. For that, we modify the implementation of [18] by adding offsets to the intermediate distances computed during each line scan. These offsets represent the distance between the interpolated surface and the next lattice point. As long as they are smaller than the grid spacing, the original algorithm still works as intended.

We apply the sub-pixel precise EDT on an image with a threshold $t\in {\mathbb R}$, denoted by $EDT(X,x)_t$. Note, that t can take values which are in between values of the gray value domain. E.g. for 8 bit gray value images, t lies in [0, 255). For binary images, t lies in [0, 1). Applying $EDT(X,x)_t$ can be interpreted as calculating the distance to the (implicitly given) iso-surface corresponding to t, because the position of the distance generator is computed in each dimension via linear interpolation of the gray values of the two neighboring pixels. Changing this threshold results in virtually dilating/eroding the foreground.

In the following we apply this algorithm to binary images. We derive two different distance maps that can be interpreted as a lower and an upper bound of a central one. For the lower bound we have $EDT(X,x)_0 \le EDT(X,x)_t$ for each threshold value $t\in [0,1)$ and each background pixel $x\in X^C$. The upper bound is obtained as $EDT(X,x)_{1-\varepsilon }$ with $\varepsilon =0.01$. Note that we write $EDT(X,x)_1$ for short in the following. Additionally, we use a distance map w.r.t. a “central” boundary surface $EDT(X,\,\cdot \,)_{0.5}$. Note that $EDT(X,x)_0$ coincides exactly with the classical EDT(X, x).

Using this EDT algorithm with sub-pixel precision results in an erosion dilation analysis with improved precision, in particular near the surface, where the observed distance values are rather roughly discretized when applying classical EDT. This is particularly nice when the structure is not very well resolved by the image.

The densities of the intrinsic volumes and derived features for all distances from both the distance map of X as well as the bounding maps $EDT(X)_0$ and $EDT(X)_1$ can be used as an indicator of how reliable the analysis results are. More precisely, we use all distances occurring in the distance map, filter them such that consecutive distances differ by at least $1\%$ of the pixel spacing, and compute for each of those distances the intrinsic volumes.

Note that the structure model index should capture the “structure shape” for both solid structure and pore space. Thus, we switch to the SMI of the complement when eroding the solid structure. We have $S(X\cap W)=S(X^C\cap W)$ and $M(X\cap W)=-M(X^C\cap W)$. Thus, for $r>0$, we use in the following

$$\begin{aligned} \mathrm{SMI}^*(X\oplus B_r)= & {} \mathrm{SMI}(X\oplus B_r) \ \text{ and }\\ \mathrm{SMI}^*(X\ominus B_r)= & {} -12\frac{(V(W)-V((X\ominus B_r)\cap W))M((X\ominus B_r)\cap W)}{S^2((X\ominus B_r)\cap W)}. \end{aligned}$$

4 Application Examples

In this section, we apply the algorithm described in the previous Sect. 3 to 3D images of rigid foam samples and of samples from nano-porous membrane layers. Note that the choice is purely motivated by trying to find examples featuring several critical structure thicknesses like strut and wall thickness in the partially closed foams. Although both the considered rigid foams as well as the nano-porous membrane layers are made of ceramic materials, the algorithm is in no way restricted to or tailor-made for ceramic samples.

4.1 Nano-Porous ZrO$_2$ and Al$_2$O$_3$ Ceramics

We compare the structures of nano-porous ceramic samples generated by spin coating. Samples 1 and 2 consist of ZrO$_2$. In fact, sample 2 is the 1st layer of the nano-porous membrane investigated in [22]. Our sample 3 is the 2nd layer of this nano-porous membrane and consists of Al$_2$O$_3$. After spin coating, the samples are sintered at $1\,000$ and $1\,400\,^\circ$C, respectively.

Grain sizes in the range 10–100 nm prevent imaging the structures by computed tomography. Instead, sequential slicing by a focused ion beam (FIB) combined with imaging by scanning electron microscopy (SEM) – so-called FIB-SEM – is applied. Due to the slicing by the focused ion beam, images generated by FIB-SEM usually feature non-cubic voxels with the resolution in stack direction being considerably coarser than within the SEM images forming the stack. Hence, the sub-pixel precision approach can yield valuable bounds for the true values of characteristics.

For all three samples, the stacks of SEM images are aligned, desheared, and transformed in order to remove distortions introduced by the alignment as described in [22]. Interpolation onto an isotropic lattice results in sample 1 with $986\times 637\times 299$ pixels and lattice spacing $3\,$nm, sample 2 with $980\times 980\times 382$ pixels and lattice spacing $3\,$nm, and sample 3 with $205\times 205\times 165$ pixels and lattice spacing $20\,$nm. This interpolated version of sample 3 is called 3i with “i” for “isotropic” from now on. Additionally, we examine a larger non-interpolated version of sample 3, called sample 3a with “a” for “anisotropic”, with $716\times 168\times 225$ pixels and lattice spacings $20\,\mathrm{nm}\times 20\,\mathrm{nm}\times 16\,\mathrm{nm}$.

Sample 3 is then reconstructed solely based on the energy-selective backscatter electron (EsB) image stack by global gray value thresholding. Samples 1 and 2 are reconstructed by the combination of the secondary electron (SE) and the EsB image stacks by morphological reconstruction by dilation [23]: Both are binarized by global gray value thresholding. Subsequently, the EsB pore image is reconstructed by dilation with the pixelwise maximum of the two pore images as mask image. See [22] for more details (Fig. 1).

Fig. 1.

Renderings of the nano-porous ceramic samples 1–3. Visualized are $986\,\times \,637\,\times \,299$ pixels corresponding to a volume of $2.96\,$µm $\times \,1.91\,$µm $\times \,0.90\,$µm for sample 1, $360\,\times \,360\,\times \,190$ pixels corresponding to a volume of $2.97\,$µm$\,\times \,2.97\,$µm$\,\times \,1.14\,$µm for sample 2, and $205\,\times \,205\,\times \,165$ pixels corresponding to a volume of $4.1\,$µm $\times \,4.1\,$µm $\times \,3.3\,$µm for sample 3.

First, we compare the results of the erosion dilation analysis on the anisotropic versus the isotropized samples 3a and 3i to study the influence of the interpolation step. Figure 2 shows the results together with the respective bounds obtained from $EDT(X)_0$ and $EDT(X)_1$. The isotropized 3i is on the one hand less well resolved than 3a and on the other hand smoothed by the interpolation. Both effects reduce the specific surface area slightly, which is visible in Fig. 2(b). Also due to the smoothing, both dilations and erosions yield non-trivial results for a wider distance range. Apart from this, we do not observe significant differences between the interpolated and the non-interpolated version of the sample. Thus, we only report the results for the isotropic version in the following analysis.

Fig. 2.

Erosion dilation analysis results for the nano-porous ceramic sample 3, anisotropic and isotropic versions (3a and 3i) with bounds derived from $EDT(X)_0$ and $EDT(X)_1$.

Results of the erosion dilation analysis for the nano-porous ceramic samples are reported in Fig. 3. The solid structure of sample 2 is clearly finer than the one of samples 1 and 3 while the difference for the pores is not that pronounced, see Fig. 3. Note that the SMI* curves start to fluctuate strongly for larger erosion and dilation radii since there only a few pixels are left to contribute, and the strong erosion/dilation changes the structure of solid structure and pore space, respectively, drastically. In general, the SMI should be trusted only in the distance range where the volume fraction $V_V$ is between 2 and 98 %.

Fig. 3.

Erosion dilation analysis results for the nano-porous ceramic samples 1–3.

4.2 Ceramic Foams

We investigate ceramic foams used for filtering metal melts in casting. These filters are produced in large numbers and discarded when loaded. The samples considered here are produced by covering an open cell polymer foam with ceramic slurry, drying, and finally burning. The resulting filters feature a majority of open cells inherited from the polymer foam, some closed cell walls formed by the slurry, and hollow struts where the polymer foam was combusted. The micro-structure of such ceramic foam samples and its relation to the filtration properties has been studied in detail in [24, 25]. Here, we consider three samples produced from the same polymer foam but with varying deposition of the ceramic material resulting in varying flow properties. More precisely, samples C01 and C14 weigh the same but the water flow rate differs while it is equal for samples C14 and C20 whose weight differs, see Table 1 (Fig. 4).

Fig. 4.

Renderings of the ceramic foam samples C01, C14, and C20.

Table 1. Ceramic foam samples and their macroscopic properties.

The samples of dimensions $50\,\mathrm{mm}\,\times \,50\,\mathrm{mm}\,\times \,20\,\mathrm{mm}$ are imaged by micro-computed tomography at pixel size $34\,$µm. Here, we are interested in roughly resolved image data. Thus the images are subsampled to a lattice with spacing $102\,$µm. The solid component is segmented by global gray value thresholding using Otsu’s algorithm [26]. The struts are closed by connected component labeling and morphological closure. Thus, the Euler number density $\chi _V$ yields essentially the negative cell wall density as there is just one connected component and there are no holes.

Results of the erosion dilation analysis for these three samples are reported in Figs. 5, 6 and 7. As expected, we observe all significant local minima and maxima at the same arguments. This is due to the underlying identical polymer foam structure leaving the spatial distribution of the ceramic slurry as the differentiating feature. The solid volume fraction does not reveal significant differences, see Fig. 5(a). The specific surface area of both the eroded and the dilated structures indicates for small radii of the sphere least surface area for C01 and most for C14, see Fig. 6. This is more pronounced on the dilation side and becomes apparent only when looking closer at the dilation range up to $0.6\,$mm, see Fig. 6(b). The Euler number density singles out C14 when being dilated: $\chi _V$ for the dilated C14 is significantly smaller than for the other two samples, see Fig. 7(b). Thus, the dilated C14 contains more tunnels, that is open cell walls, than C01 and C20. This in turn indicates that C01 and C20 include smaller cell walls being closed by the dilation earlier than those in C14.

Nevertheless, none of the curves in Figs. 5, 6 and 7 seems to explain the different weights and water flow rates reported in Table 1. The structure model index reveals distance ranges, where a closer look seems worthwhile, see Fig. 5(b). Indeed, as indicated by the first peak of the dilation curve, C01 has more really large pores than the other two samples rendering a good explanation for the increased water flow rate: Erosion of the pore space with a ball of radius $r=1.8\,$mm, results in 117 connected components for C01, 20 for C14, and 51 for C20. These large pores comprise $0.011\%$ of the pore volume of C01, $0.002\%$ of the pore volume of C14, and $0.008\%$ of the pore volume of C20. If these large pores are reconstructed, they comprise $12\%$ of the pore volume for C01, $2\%$ for C14, and $5.4\%$ for C20.

Fig. 5.

Erosion dilation analysis results for the ceramic foam samples: solid volume fraction $V_V$ and structure model index.

Fig. 6.

Erosion dilation analysis results for the ceramic foam samples: specific surface area $S_V$ and close-up with envelopes derived from $EDT_0$ and $EDT_1$.

Fig. 7.

Erosion dilation analysis results for the ceramic foam samples: Euler number density $\chi _V$ and close-up with envelopes derived from $EDT_0$ and $EDT_1$.

5 Discussion

In this paper, we combined the efficient algorithm for calculating the intrinsic volumes for each possible gray value threshold in an integer valued image [9] with the linear time exact Euclidean distance transform from [18] and the sub-pixel precision approach of [21].

We applied it for efficient erosion dilation analysis of nano-porous ceramic membrane layers imaged by FIB-SEM and of ceramic foams imaged by micro-computed tomography. Both examples show, that interesting structural features and differences can be revealed that way at low effort for both preprocessing and the algorithm itself. Thus, it is very well suited for a screening step indicating the direction of further, more detailed analysis by methods dedicated to the specific type of structure of interest. Moreover, the sub-pixel precise EDT can yield bounds for the densities of the intrinsic volumes. This is helpful when studying differences between similar structures. It is particularly valuable in cases, where the resolution is close to being insufficient.

Furthermore, we see potential use in calculating the spherical contact distribution [1] more precisely.