Image Anal Stereol 2012;31:163-174
Original Research Paper
3D GEOMETRIC CHARACTERIZATION OF PARTICLES APPLIED TO TECHNICAL CLEANLINESS
Irene Vecchiob'\ Katja Schladitz1, Michael Godehardt1 and Markus J. Heneka2
Fraunhofer Institut für Techno- und Wirtschaftsmathematik (ITWM), 67663 Kaiserslautern, Germany; 2RJL Micro&Analytic, 76689 Karlsdorf-Neuthard, Germany
e-mail: irene.vecchio@itwm.fraunhofer.de, katja.schladitz@itwm.fraunhofer.de, michael.godehardt@itwm.fraunhofer.de, analytic@rjl-micro.de
(Received May 31, 2012; revised October 8, 2012; accepted October 10, 2012)
ABSTRACT
During production of mechanical components, residual dirt collects on the surfaces, thus creating a contamination that affects the durability of the assembled products. Residual particles are currently analyzed based on microscopic 2D images. However, the particle's shape is decisive for the damage it can cause, yet can not be judged reliably from 2D data. Micro-computed tomography allows to capture the complex spatial structures of thousands of particles simultaneously. Now new methods to characterize three dimensional shapes are needed to establish 3D cleanliness analysis. In this work, unambiguously indicative geometric features are defined and it is investigated how they can yield a reliable classification in three typical classes: fibers, chips and granules. Finally, the efficiency of the proposed method is proved by analyzing samples of real dirt particles.
Keywords: classification, computed tomography, intrinsic volumes, minimum bounding box, shape factor.
INTRODUCTION
Technical cleanliness refers to the task of ensuring a certain level of cleanliness in manufacturing industry. Residual dirt particles collecting on the surface of mechanical components are unavoidable during production. The expected performance and durability of the assembled products can significantly decrease due to the presence of contaminants, thus it is necessary to investigate the cleanliness level of the surfaces of single components on the factory line. Internationally agreed standards as VDA-19 and ISO-16232 contain the basic rules for quantitative and qualitative inspection of contaminants. Typically, the dirt particles are imaged microscopically and analyzed based on the resulting two-dimensional images. More precise analyses can be performed if the whole three dimensional shape is captured. Micro computed tomography (|CT) offers exactly this possibility. A thorough geometric characterization of the three-dimensional shapes helps the manufacturers to identify potentially dangerous dirt particles.
In various application fields, the form of particles conveys very interesting information. For example, chemical reactions generating cellular or molecular particles can be better understood by looking at their shapes (see Merson-Davies and Odds, 1989 or Landry etal., 1999). In geology (Kaminski etal., 2008), hydrodynamics (Stuckrath etal., 2006),
mechanical engineering (Lin and Miller, 2005) and several other applied sciences, a detailed description of particle shapes is of crucial importance. Our methods for characterizing shapes can be applied in all cases where volume images of particles are available.
For what concerns planar objects, several geometric features had been defined (see for instance Stoyan and Stoyan, 1994, for a purely theoretical overview, and ASTM F1877, 2003, which deals with an application to contaminating particles characterization). Nevertheless, when observing 2D images of real objects, only a projection on a plane is visible, thus essential information is lost. On the other hand, by increasing the dimension, also the complexity of the estimations grow. In this paper, we aim at rigorously defining parameters that describe 3D shapes and at suggesting how to efficiently estimate them from given volume data.
Besides parameters to characterize 2D shapes, ASTM F1877 (2003) introduces a classification of planar particles, too. Two classes of objects can be naturally distinguished by comparing the two dimensions. Granular shapes are those with comparable length and width, while fibers or needles have typically length much larger than the width. If the third dimension is also available, that is the thickness of the object, then another class can be recognized, i.e., chips. Our work includes the introduction of
techniques to perform a reliable classification on the basis of the estimated features.
To conclude, we will apply the proposed methodology to a dataset of dirt particles from automotive industry and discuss the results.
PARTICLE FEATURES
In this section, we define a wide collection of parameters describing particle shapes in 3D. We proceed generalizing the features introduced in (ASTM F1877 , 2003) and enrich them with other morphological parameters that better apply to the spatial context.
Basic measures for the size of 2D particles are area, perimeter and Feret diameters. In addition, ASTM F1877 (2003) proposes the equivalent circle diameter and the length of the medial axis as measures of the size of the particle. From the size measures, shape factors are derived. One is for example the roundness, i.e., the normalized ratio of area and maximal diameter.
Our goal is to measure and characterize real objects, that is compact simply connected bodies in R3 with non-empty interior. What we observe, though, are only their digital images. In other words, we estimate the features of an object X, starting from the polyhedral set X resulting from digitization w. r. t. an adjacency system in 3D (cf. Ohser and Schladnitz, 2009, Chapter 3). Therefore, the geometric parameters will be defined in continuous Euclidean space (real world), but the algorithms are implemented in discrete space (images). An analysis of the error due to discretization is provided in the following.
Throughout, by an image we understand a three-dimensional orthogonal lattice in which each lattice vertex is a pixel, or voxel. In this section, we assume to deal with one particle at a time in a binary image, that is each pixel is either black (background) or white (foreground). The object X is thus a finite collection of pixels.
INTRINSIC VOLUMES AND ISOPERIMETRIC SHAPE FACTORS
In first instance, we consider the intrinsic volumes of compact sets (Ohser and Miicklich, 2000), a basic set of object characteristics. These are: volume V, surface area S, integral of mean curvature M and Euler number %. The integral of mean curvature has dimension one and, for convex particles, is proportional to the mean width. The Euler number,
also known as the Euler-Poincare characteristic, conveys topological properties of a set. It equals 1 for convex bodies and can be extended additively to the convex ring of unions of convex bodies. The 3D Euler number is the sum of the number of connected components minus the number of tunnels plus the number of holes. An object with a hole, separates the background in two connected components. In fact a hole is a hollowness inside the object, such as the inside of an empty eggshell with a certain thickness. A tunnel, in contrast, refers to a passage as in a torus or the handle of a cup, thus allowing the background to be connected. If a "fill-holes" algorithm is applied to the binary image, then the Euler number of an object returns the number of tunnels.
From the intrinsic volumes, a set of shape factors is deduced, (Stoyan et al, 1995):
Definition 1. Let V = V(X), S = S{X) andM = M{X) be the intrinsic volumes of a compact body X with nonempty interior, then
f\ = 60c
V	, V	S
—, /2 = 487T —/3=47!^ v/^3 Jl	M3 J	M2
are the isoperimetric shape factors of X.
All shape factors are normalized to 1 for balls. /1 takes values between 0 and 1, while /2 and /3 are smaller or equal to 1 only for convex objects. Deviations from 1 describe deviations from the spherical shape. In fact, the first shape factor /1 is also called sphericity (Parra-Denis et al,, 2008). Values for some reference cylinders are presented in Table 1. Being derived by the isoperimetric inequalities in the general setting of mixed Minkowski volumes (Schneider, 1993), these three parameters are a complete set. Moreover, other factors obtained by combinations of the intrinsic volumes would carry redundant information. Nevertheless, motivated by special applications, in the literature one can find such indices as, for instance, the compacity factor (Parra-Denis et al, 2008), describing deviations from the cubic shape:
3V2
/c=6V
(1)
Algorithms to estimate the intrinsic volumes on discrete data are recalled in (Ohser and Schladnitz, 2009). Depending non the least on the image resolution, these estimators embed in themselves a significant approximation. Besides, being defined as ratios yields an additional source of error. Nevertheless, in Ohser et al. (2002) it is proved that the estimates of the intrinsic volumes are unbiased for
compact sets being morphologically regular w. r. t. all line segments connecting vertices of the lattice unit cell, see also Ohser and Schladnitz (2009, Theorem 3.1). In Montero and Bribiesca (2009), an overview on numerical problems as well as possible solutions for their approximation is outlined.
SIZE: LENGTH, WIDTH, AND THICKNESS
The volume measures the mass of a particle, but yields no information about its distribution in space. What is needed, is the size of a particle consisting of three measures of the extension of the particle in three suitable orthogonal directions. The longest is the length of the particle. The size can be measured using Feret diameters or calipers (ASTM D4791 ,2010), that is by measuring the distance between two parallel lines enclosing the particle between them. Generalizing this concept, one can consider Euclidean distances between pairs of points of the particle. The longest of these measures is the maximal Feret diameter (Fig. lb). The maximal Feret diameter of a cube is thus the length of its spatial diagonal. However, this does not meet the intuitive idea of the length and size of a particle, for which the size of a cube should correspond to the length of its edges. To obtain this, we define the following:
Definition 2. Call C C M3 a cuboid with arbitrary orientation (w. a. o.) if there exist Xi, yi, zi € M for i 1,2 and a rotation 6 <G SO(M.3) such that C = 6Co with Co = [a'i,a'2] x [vi,v2] x [21,22]- The minimum volume bounding box (MVBB) of X as above, is a cuboid w. a. o. C such that:
-	xc c,
-	vol(C) < vol(C') for all cuboids w. a. o. C's. t.
XCC'.
Then the size ofX is given by the lengths of the edges of C. Sorted in decreasing order, these are length I, width w and thickness t.
In Fig. la, the size of a chip-like ellipsoid is represented. The MVBB of an object is not unique. In fact, for a sphere it is a cube with edge length equal to the diameter and arbitrary orientation. Nevertheless, the size depends only on the measure of the edges, not on their directions. Uniqueness of the measures length, width and thickness is expected to hold, though a rigorous proof is subject of further research.
(b)
Fig. 1: Size features, (a) Size of an ellipsoid and its minimum volume bounding box. (b) Maximal Feret diameter (blue), elongation path (green) and circle realizing the inner diameter (red).
An exact algorithm to compute the MVBB was proposed in O'Rourke (1985), but it is of cubic complexity in the number of points of the particle. Since this computational cost is in general too high for applications, we rather apply an algorithm which only approximates the real minimum volume bounding box, but in nearly linear time. We follow the work of Barequet and Har-Peled (2001) with some changes to further improve the efficiency. The algorithm is based on two main ideas:
1.	the MVBB of a particle is the same as the MVBB of its convex hull;
2.	it is cheap to compute the MVBB with an edge on a fixed direction.
For 1, the convex hull is computed with an implementation of the QuickHull algorithm (de Berg et al,, 2008), which is an exact computation. In this way, the number of input points is significantly reduced without any loss in precision. For example the ellipsoid in Fig. la is formed by almost 5-105 points, while its convex hull has only 655 vertices. In Barequet and Har-Peled (2001) it is proved that it is enough to test a relative small set of directions. Then, thanks to 2, the MVBB for each direction is fast computed. The volume deviation to the exact
MVBB depends on the number of test directions and can be decreased arbitrarily by increasing the number of directions.
The computation of the convex hull is also useful to calculate another shape parameter, namely the convexity factor. It is the ratio between the volume of the particle and the volume of its convex hull. Equal to 1 for convex particles and otherwise smaller, it tells how far a particle is from being convex.
SIZE: ELONGATION AND INNER DIAMETER
Length, width, and thickness do not describe exhaustively the size of a particle, especially if non-convex. We are interested in measuring, for example, the length of an unwound fiber. Heuristically, it is the curve length of the shortest path within the particle connecting its end points. Formally (cf. Lantuejoul and Maisonneuve, 1984):
Definition 3. The geodesic arc between two points x and y in the body X is the shortest continuous path within X; its length is the geodesic distance between x and y. The length of the longest among these paths is the geodesic length or elongation of X.
The elongation path is represented with other features in Fig. 1b.
As for the MVBB, the points realizing the elongation are not unique, e.g., for star shaped objects, including sphere and cube. Its value is, however, unique. Furthermore, this definition is robust: if a particle is slightly deformed, the elongation varies minimally. The estimation is based on a two-step procedure. Given a starting point, the geodesic distances to all other points in the particle are computed. A point realizing the maximum is taken as the new starting point. Again, the distances to all other points are computed. The value of the maximum so obtained is also the maximum length of the geodesic paths among all possible pairs of points. The computation of the geodesic distance is based on the algorithm presented in Petres et al. (2005).
If the object has a hole or a tunnel, the two-step procedure might fail to return the elongation. In fact, depending on the starting point, only a local maximum is found. Thus, in case the Euler number of the object is not 1, multiple starting points have to be tested. Moreover, it is possible to "close" holes inside a particle by applying a fill-hole algorithm. By comparing the elongation estimated on the original particle and on the processed one, one can have a measure of the extension of the hole. Furthermore, in
the application to technical cleanliness only the outer shape is interesting, thus it is suitable to apply the fill-hole algorithm to all particles in the preprocessing step.
To compare particles, it is helpful to define another shape factor (Parra-Denis et al., 2008):
Definition 4. Let Lg be the elongation of X, then the elongation index is
Ig
A
6V
(2)
It equals 1 for spheres and gets larger, the more elongated a particle is, where by elongated we understand thin and long, no matter how arranged in space.
It is interesting to have an estimate of the actual thickness of a fiber as well as its length.
Definition 5. The diameter of the largest ball completely contained in X is the inner diameter or maximal local thickness of X.
Besides estimating the thickness of a particle, this parameter can also be interpreted as a measure of the largest core (see Fig. 1b). Thinking of cleanliness applications, this suggests the minimal fineness a filter should have to prevent a particle from passing through. We estimate the inner diameter on the digital image of X as the maximum of the Euclidean distance transform (EDT) of the particle. In fact, this map assigns to each foreground pixel the distance to the nearest background pixel (see Ohser and Schladnitz, 2009 for a formal definition and the available algorithms).
The geometric interpretation differs if the particle has a hole. For example, the inner diameter of a hollow eggshell is the maximal thickness of the shell, which does not yield information on the core of the particle as a whole. Again, the application of a fill-hole algorithm allows to obviate this issue.
CORRELATION ANALYSIS
The parameters introduced cover a wide range of features characterizing particle shape and size. Although some are clearly defined independently from the others, they might be correlated. Their correlation is studied by visualizing the pairwise covariance matrix of the features estimated on a sample of 486 dirt particles (Fig. 2). Volume and surface area are linearly correlated, implying the correlation of the isoperimetric shape factors f2 and f3. Also the correlation of length and elongation is linear. This suggests that each particle has a rather regular form: no strongly twisted fiber or rounded or bended chip occur in the sample. The other features do not present significant correlation.
Further analysis on the parameters' redundancy can be performed by means of principal component analysis (cf. Parra-Denis et al., 2008). However, in our application field, an accurate description of the particle is needed to identify the risk their presence implies, thus all parameters are interesting.
ESTIMATION ERROR
In this section, we analyze the error in estimating the parameters on a discrete object observed on a lattice. Cylinders are chosen as reference objects. We consider three aspect ratios corresponding to the different classes: 1:10 for fibers, 10:1 for chips and 1:1 for granules. For each class, volumes vary from
about 50 pixels to 20000. Here, the unit "pixel" is used for the volume of unit cell of the lattice the image is defined on. That is, pixel is just (lattice spacing)3 assuming equal lateral resolution in all three coordinate directions. In Table 1, the estimated values of the features of one cylinder for each class are displayed. We chose volumes around 2 000 pixels as it is a typical size of large dirt particles in real samples (cf. Table 2). The relative errors in the table suggest how much the estimations differ from the theoretical value. This depends on the size, position and orientation of the cylinder. Note that the discretization chosen for the cylinders plays a big role in all the feature estimations, too. To reduce this effect, diameters and heights of the
0 2000 0.2 0.8
V ■	i 1 y	■ •A •	■ •	■ •• •
M /	S	•• ■•w		M
P' .	• ■	f_1	/	
	i	/	f_2	y
k. •	* fie .i •	f ■	»	f_3
— • - • • r m	• • • r		■	• • • ■
f	• 1 f			
«	fi •	* •	•	■
r	r	X.	•*	
• • T 1 1 1 1	• • ^	t ■ ••• -VyvS		■ • Vi* i m i i r i
0 6000	0.4 0.7 1.0	0.4 0.8
10 40 7 i i 11 i i	0		5 15 1 ' ' J '		m	24 i ' ' ' i.
• • jï-		• .	v.		•• A-	
• • A-		• • • ✓	•		« • • A	•
K V			% % «S-		V V.	ft • : s,_ %
* «		•	* •		■	m •
length ■		• • • • . * r	• •		• • / / ■	• & m
		width	• jjp			
Jfè-*			thick ■			S' m i
/		î • . ¡¡fi'			elong	î • îh "z
• r-		• t T\\ 1 1 1 1 5 20 35	• r		ril 11111 10 40 70	inn_diam
Fig. 2: Correlation matrix of volume V, surface area S, isoperimetric shape factors f\, f2 and f3, MVBB length, width, and thickness, elongation, and inner diameter. All measurements in pixels assuming lattice spacing = 1.
cylinders are always chosen as integer numbers. Moreover, to systematically analyze the estimation algorithms, instead of considering one cylinder for each size, we sample random rotations of the axis and shifts in the lattice distance, that is, the particles are in general position w. r. t. the lattice in the sense of Ohser and Miicklich (2000). The means of the estimations are compared with the well known theoretical values of the features for each size. In Fig. 3, the relative errors are plotted.
Asymptotic convergence of the estimators of the intrinsic volumes is guaranteed by the rotations and translations within the lattice of the cylinders with increasing resolution (cf. Ohser el a I., 2002). The relative error of theoretical and estimated surface area is shown in Fig. 3a. It converges to zero as expected. The relative error for the first isoperimetric shape factor, Fig. 3b, shows the same trend, but with larger values. This is due to the ratio of volume and surface area, which yields an additional source of approximation.
For what concerns the MVBB, only the error regarding the length is represented (Fig. 3c), which is also the largest compared to width and thickness.
For small objects, it is rather large (around 20% for granules and chips), but decreases significantly as the cylinder size increases. Length, width and thickness are in most cases overestimated. This comes from the definition of the MVBB, i.e., a box containing the object completely. In the algorithm, we used a grid of 103 nodes, yielding 840 different test directions. By increasing the fineness of the grid, the estimation can be further improved.
Maximal Feret diameter and elongation are both equal to the spatial diagonal of the cylinder. Despite being estimated with very different methods, their values differ by less than 2 pixels in the worst case. In general, the elongation is larger and the corresponding relative error (Fig. 3e), converges more slowly than the one of the maximal Feret diameter (Fig. 3d).
The best estimation of the inner diameter is obtained for fibers, see Fig. 3f. In fact, for these long and thin cylinders, the inner diameter is the diameter of the cylinder, which is much smaller than the height, allowing an exact estimation for some values of the cylinder radius. For granular and chip-like cylinders, instead, the relative error is averagely larger, but still converging to zero as the volume increases.
Table 1: Particle features with relative errors of a fibrous, a chip-like, and a granular cylinder with arbitrary position and orientation. The features are estimated from the images. The theoretical values for radius and height (r, h) are (3, 60), (15, 3), and (7, 14), respectively. Images and computation of characteristics with MAVIparticle (Fraunhofer ITWM, 2012).
volume [px]	1889	±	11.35%	2 053	±	3.18%	2 155	±	0.001%
surface area [px]	1 209.69	±	1.87%	1582.06	±	6.74%	895.81	±	3.01%
shape factor f\	0.48	±	0.08%	0.35	±	7.50%	0.85	±	4.71%
shape factor /2	0.10	±	3.48%	0.26	±	8.46%	0.71	±	5.07%
shape factor /3	0.35	±	2.36%	0.83	±	8.91%	0.88	±	4.92%
length [px]	60.82	±	1.36%	30.64	±	2.15%	15.42	±	10.15%
width [px]	8.59	±	43.17%	30.18	±	0.58%	14.87	±	6.18%
thickness [px]	5.81	±	3.17%	4.12	±	37.34%	14.12	±	0.83%
max Feret diam [px]	60.88	±	0.98%	30.87	±	2.40%	20.87	±	5.43%
elongation [px]	62.55	±	4.25%	33.79	±	12.07%	20.60	±	4.04%
elongation index	74.55	±	9.22%	9.84	±	4.54%	2.13	±	12.74%
inner diameter [px]	6.63	±	10.55%	3.46	±	15.47%	13.30	±	4.99%
(e) Elongation.
(f) Inner diameter.
Fig. 3: Relative error for the features estimation on three sets of cylinder with aspect ratios 1:1 (red), 10:1 (blue) and 10:1 (green), from top to bottom respectively, randomly rotated and shifted w. r. t. the lattice. On the x-axis, the volumes are represented.
CLASSIFICATION
ASTM F1877 (2003) provides a qualitative guideline to classify particles according to their shape. This classification is performed by looking at the photographs of the particles, hence human vision can easily deduce from perspective and shading effects how the particles are shaped in 3D. Here instead, we aim at making the classification systematic by exploiting the parameters previously defined.
In 2D, it is natural to identify two classes of particles: fibers, long and thin, and granules, large in both dimensions. These classes are also the ones recognized in technical cleanliness. Adding one dimension, a third class of objects can be distinguished. In fact, a granule in 2D, can be "flat", i.e., have small thickness, or be about as thick as it is large. We call the flat objects chips, while the others are three-dimensional granules. Again fibers are all those long and thin particles. These heuristical definitions are based on the aspect ratios of the particles. Thus we can easily formalize them for convex objects, by referring to the measure of size stated in Def. 2:
Definition 6. Let X be a convex compact body with length l, width w, and thickness t, then
-	ifl~w~t —> X is a granule,
-	ifl^w^torl^w^t —> X is a chip,
-	ifl^w^t —> X is a fiber.
This definition yields the classification first introduced by Zingg (1935) to classify rocks. The classification can be easily visualized via the Zingg-diagram, Fig. 4a. In mineralogy, two measures differ if the ratio of the smaller over the bigger one is larger than 2/3. However, this threshold may vary depending on the application field. Typically in technical cleanliness, particles are considered fibrous if their aspect ratio is 10 : 1.
When it comes to non-convex particles, however, the measures of /, w, and t as computed on the MVBB can not be interpreted as measures of the real size of the particles, thus the Zingg-classification could fail. Although no formal definition is given in the case of non-convex particles, the three classes fiber, chip, and granule, can still be used. For example in Fig. 4b, the first particle is a chip, followed by three twisted fibers. In fact, if unwound, these fibers have length ten times larger than width and thickness. It seems reasonable to use the measures of elongation and inner diameter to achieve a classification for these particles analogous
Fig. 4: Classification based on the size, (a) Zingg-diagram with thresholds at2/3.(b) Particles for which this classification fails. Bounding boxes to enhance visualizations, do not correspond to the MVBB.
to the Zingg-diagram. Define the aspect ratio as inner diameter over elongation, thus it is a number smaller or equal 1. The values for the three cylinders used as reference for fibers, chips, and granules, are 0.09,0.20, and 0.71, respectively. They are sufficiently different. However, these are simple shapes in which the elongation is the space diagonal and two dimensions are identical. The limit of a criterion based on this index is that it only considers two dimensions to describe the three-dimensional size of particles, thus it can not suffice to classify complex shapes.
In order to classify all types of particles, we investigate the behavior of the shape features. The interpretation of the isoperimetric shape factors suggests that their values for long and thin objects differ from their values for granular ones. In order to investigate this, a sample of reference particles with random size and random orientation is simulated. The sample includes about 750 particles, namely ellipsoids, cuboids, cylinders, rounded chips, arcs of tori and arcs of helices. Examples of these particles are those in Fig. 4b, but with different size, orientation, and more or less rounded. Rounded chips are defined as
Fig. 5: Isoperimetric shape factors, f\, /2 and /3, plotted against volume of the simulated particles. Each color represents a class: green for fibers, blue for chips and red for granules.
cuboids curved around a cylinder, with various radii. To classify these particles, we refer to the size of the cuboid. Arc of tori and helices are defined as an arc of a circumference or arc of a helix, respectively, each cut at various random angles, dilated with a sphere of random radius. The length is thus computed as the curve length of the arc, while width and thickness correspond to the radius. The aspect ratios vary randomly according to the standards in technical cleanliness:
-	granules: w/l € [0.7,1], t/w € [0.7,1];
-	chips: w/l € [0.15,0.6], t/w € [0.05,1];
-	fibers: w/l € [0.05,0.09], t/w € [0.7,1],
While the classes are known from the analytical description of the shapes, the features are estimated from their digitized imaged. In Fig. 5, graphs for the estimated isoperimetric shape factors are plotted against the increasing volume of the particles, with different colors for each class. For sufficiently large volumes, the values of the shape factors significantly differ for each class. Based on this sample, the classification can be accomplished as follows:
1.	/3 < 0.5 and /2 < 0.1 fiber,
2.	if not fiber and /1 < 0.7 and f2 < 0.4 — chip,
3.	if not fiber and not chip —> granule.
For each class, we consider two shape factors so that the errors due to the estimations on digitized images can be compensated. In fact, real particles are not as smooth as the reference ones we simulated. However, since we restrict to large particles that typically do not have an inner structure, this type of error is not expected to affect the classification, as discussed in the
previous section. Note that these thresholds are chosen with respect to the application to technical cleanliness. In other fields, the ratio length over width that defines a fiber, for example, could change, hence also the thresholds determining this classification should be adapted. The elognation index also gives a measure of the shape of the particles and is independent of the isoperimetric shape factors. Although alone it is not informative enough to be exploited for classification, it can be used to validate the classification of non-convex particles.
For what concerns small volumes, it is sensible to rely on the classification based on the size. Indeed, the space configuration of a small particle, in general, can not be such to induce length, width, and thickness of a wrong class. We suggest to set this threshold at 400 pixels. Nonetheless, for very small objects, the discretization errors are too high and the classification is not interesting. Thus, we will not classify particles constituted by less than 64 pixels. This threshold is chosen because a cube formed of 64 pixels has edges only 4 pixels long, thence, averagely, there is not enough freedom to arrange the pixels in a wide variety of shapes.
With all the features we collected, it is also possible to perform a cluster classification. For example this method is applied in (Parra-Denis et al, 2008) to classify the complex shapes of intermetallic particles originating from the solidification process of aluminum alloys. However, due to the application in technical cleanliness, we aim at globally defining the three classes of typical 3D shapes. Therefore, a threshold classification is preferable.
Fig. 6: 3D reconstruction of a sample of dirt particles (red) on the rolled filter membrane (blue). Binarization from a \\,CT image realized by RJL Micro&Analytic with a Sky Scan device. Pixel size 9.88 \\m. Image size 10.86 x 10.86 x 2.96 mm. Visualization by MAVIparticle (Fraunhofer ITWM, 2012).
APPLICATION TO TECHNICAL CLEANLINESS
The cleanliness level of mechanical components must be tested on the factory line. The dirt particles are collected from their surfaces on a filter membrane. This is then rolled and inserted in a plastic cylinder to be imaged via micro computed tomography (|J,CT). Often, instead of plastic, a steel cylinder is used as a container. Its gray value in the jj,CT image can be exploited to calibrate the material composition of the particles in the sample.
The tomographic image is segmented via thresholding. A volume rendering is displayed in Fig. 6. The rolled filter membrane is clearly visible, in blue, while only a few dirt particles can be recognized, rendered in red.
In order to have a representative sample, we consider a large dataset consisting of 1061 particles. The mean volume is 2.49-106)j,m3 (259 pixels). Applying the thresholds suggested in the previous section, the particles are labeled as 'small', 'medium', and 'large' depending on their volumes in pixels, resulting in 469 small, 406 medium, and 186 large particles. The small particles will not be further analyzed. We classify medium and large particles according to the minimum volume bounding box and to the isoperimetric shape factors, respectively. Despite
the particles shapes are not as regular as the sample particles above considered, the geometric parameters are estimated reliably.
In Fig. 7a, the aspect ratios of the MVBB of the medium particles are drawn in the Zingg-diagram. The thresholds are imposed by technical cleanliness requirements: thickness over width smaller than 2/3 means comparable dimensions and length over width smaller than 1/10 defines fibers. With these thresholds, there are 216 granular particles, 190 chips and no fibers among the medium particles in the sample. For what concerns the large particles, instead, we consider the
ra c 0) !c
'S ä
o
o -
0	2/3	1
thickness/width
(a) Zingg-diagram of the medium particles.
in ö
o
■;= in
a d
Q.
if)
in
CM ö
o -
0	2.5e21	5.0e21	7.5e21	1.0e21
volume [um]
(b) Isoperimetric shape factor f\ of large particles plotted over the volume.
Fig. 7: Classification of dirt particles in the sample. Each color represents a class: green for fibers, blue for chips and red for granules.
Chips
♦» U	• .... . t
♦ * ♦<"• «V	• A
.. v •••*.« V . *
Granules
Fibers
■
Ik*..
• •
Table 2: Features of three large particles from the sample in Fig. 6. Images and computation of characteristics with MAVIparticle (Fraunhofer ITWM, 2012).
s *
pixel size = 9.88 jam	fiber	chip	granule
mean gray value	264	48.47	410
volume [px]	823	2968	1 023
volume [jam3]	793 726	2 862429	986612
Euler number	1	1	1
shape factor f1	0.48	0.56	0.86
shape factor f2	0.19	0.33	0.73
shape factor f3	0.44	0.69	0.89
length [jam]	341.18	393.81	149.05
width [j m]	86.44	160.56	132.93
thickness [jam]	49.14	74.44	91.45
elongation [jam]	340.86	398.56	166.38
elongation index	26.12	11.58	2.44
inner diameter [jam]	4.47	7.21	9.17
convexity factor	0.91	0.95	0.97
isoperimetric shape factors. In Fig. 7b, fi is plotted against the volume. The classification, which accounts all three isoperimetric shape factors, is represented by the colors. There are 9 fibers, 66 chips and 111 granules. The largest particles in the sample are fibers, as typical in dirt particles samples.
Gathering all the data regarding medium and large particles, the sample is composed of 55.2% granules, 43.3% chips, and only 1.5% fibers. Though fewer, fibers constitute 13.7% of the total volume.
The sample can be further characterized by means of the other features. All particles have Euler number equal to 1, before and after applying a fill-hole algorithm. This means that no particles have holes or tunnels. Moreover, it is interesting to investigate the degree of straightness of the large fibers in the sample: length and elongation or thickness and maximal local thickness can be compared to see if the fibers are twisted. If the convexity factor is much smaller than 1, then the fiber is curved, the more it is, the larger the elongation index will be.
In Table 2, three of the largest particles in the sample, one for each class, are shown together with their features. The classification is based on the isoperimetric shape factors, since they are all
large particles. Moreover, the elongation index is also typically different for each particle, being 10 times larger for the fiber than for the granule. None of the particles presents a concavity. The relative small value of the convex factor of the fiber is due to surface roughness. The mean gray values of the particles vary strongly, indicating different material compositions.
CONCLUSION
Spanning from classical geometric methods via mathematical morphology to stochastic geometry, a variety of shape and size descriptors has been collected. In particular, we proposed a collection of features for 3D objects that naturally and unambiguously generalize the parameters presented in (ASTM F1877 , 2003) and complete them with spatial characterizations.
In addition to characterization, we also suggested how to use these parameters to classify arbitrary objects. The first approach we proposed is directly derived from the classes' definition. The classification is obtained by plotting the size of the MVBB of the particles in the Zingg-diagram. Alternatively, particles
can be classified based on the isoperimetric shape factors. Furthermore, these two methodologies can be merged to classify particles depending on their volumes.
In the last section, the particle characterization is applied in the field of technical cleanliness. The features can be reliably and efficiently estimated from tomographic images of the particles. A classification for medium and large particles is achieved. As a result, the residual dirt can be analyzed and the danger that it can cause can be estimated.
Nevertheless, technical cleanliness is not the only possible application field. Indeed, the parameters proposed are well defined for any type of three dimensional object and can therefore be used in other application scenarios. Once the geometric features of the objects are calculated, the thresholds yielding the classification can be adapted as desired.
ACKNOWLEDGMENT
This paper summarizes results of the projects KF 227 4801 RR9 and KF 228 2001 RR9 ParSiDi-3D, a cooperation between the Image Processing department of Fraunhofer ITWM and RJL Micro&Analytic, funded by the German Federal Ministry of Economics and Technology. Irene Vecchio acknowledges support by the Deutsch-Franzosische Hochschule (DFH).
REFERENCES
ASTM D4791 (2010). Standard test method for flat particles, elongated particles, or flat and elongated particles in coarse aggregate. American Society for Testing and Materials. ASTM F1877 (2003). Standard practice for characterization of particles. American Society for Testing and Materials.
Barequet G, Har-Peled S (2001). Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J Algorithm 38:82-91.
de Berg M, Cheong O, van Kreveld M, Overmars M (2008). Computational geometry: Algorithms and application. Springer.
Fraunhofer ITWM, Department of Image Processing (2012). MAVIparticle - modular algorithms for volume images - particle analysis. http://www.mavi-3d.de/. Kaminski S, Kaminska D, Trzcinski J (2008). Grain size and three-dimensional particle shape - automatic analysis with application of optical electronic AWK 3D analyzer. In: Proc 11th Baltic Sea Geotech Conf. Gdansk, Poland.
Landry ME, Blanchard CR, Mabrey JD, Wang X, Agrawal CM (1999). Morphology of in vitro generated ultrahigh molecular weight polyethylene wear particles as a function of contact conditions and material parameters. J Biomed Mater Res 48:61-9.
Lantuejoul C, Maisonneuve F (1984). Geodesic methods in quantitative image analysis. Pattern Recogn 17:177-87.
Lin C, Miller J (2005). 3D characterization and analysis of particle shape using X-ray microtomography (XMT). Powder Technology 154:61-9.
Merson-Davies LA, Odds FC (1989). A morphology index for characterization of cell shape in Candida albicans. J Gen Appl Microbiol 135:3143-52.
Montero RS, Bribiesca E (2009). State of the art of compactness and circularity measures. Int Math Forum 4:1305-35.
Ohser J, Mucklich F (2000). Statistical analysis of microstructures in materials science. Chichester, New York: Wiley.
Ohser J, Nagel W, Schladitz K (2002). The Euler number of discretized sets - on the choice of Adjacency in homogeneous lattices. In: Mecke KR, Stoyan D, eds. Morphology of Condensed Matter. Lect Notes Phys 600:275-98.
Ohser J, Schladitz K (2009). 3D images of materials structures - Processing and analysis. Weinheim: Wiley VCH.
O'Rourke J (1985). Finding minimal enclosing boxes. Int J Parallel Prog 14:183-99..
Parra-Denis E, Barat C, Jeulin D, Ducottet C (2008). 3D complex shape characterization by statistical analysis: Application to aluminium alloys. Mater Charact 59:338-43.
Petres C, Pailhas Y, Petillot Y, Lane D (2005). Underwater path planing using fast marching algorithms. In: Oceans 2005 - Europe, vol. 2.
Schneider R (1993). Convex bodies: The Brunn-Minkowski theory. Cambridge University Press.
Stoyan D, Kendall WS, Mecke J (1995). Stochastic Geometry and its Applications, 2nd Ed. Chichester: Wiley.
Stoyan D, Stoyan H (1994). Fractals, random shapes and point fields. Chichester: Wiley.
Stuckrath T, Volker G, Meng J (2006). Classification of shape and underwater motion properties of rock. In: 3rd Chinese-German joint symposium on coastal and ocean engineering. China: Tainan.
Zingg T (1935). Beitrag zur Schotteranalyse. Zurich: Mineralogische und Petrologische Mitteilungen 15.