Image Anal Stereol 2003;22:11-19 Original Research Paper
THE EULER NUMBER OF DISCRETISED SETS - SURPRISING RESULTS IN THREE DIMENSIONS
Joachim Ohser1, Werner Nagel2 and Katja Schladitz1
Fraunhofer-Institut fu¨r Techno- und Wirtschaftsmathematik, Gottlieb-Daimler-Straße, 67663 Kaiserslautern, 2Friedrich-Schiller-Universita¨t Jena, Fakulta¨t fu¨r Mathematik und Informatik, 07740 Jena e-mail: ohser@itwm.fhg.de
(Accepted February 26, 2003)
ABSTRACT
The problem of estimating the Euler-Poincare characteristic (Euler number for short) of a set in the 3d Euclidean space is considered, given that this set is observed in the points of a lattice. In this situation, which is typical in image analysis, the choice of an appropriate data-based discretisation of the set is crucial. Four versions of a discretisation method which is based on the notion of adjacency systems are presented; these versions are referred to as (14.1,14.1), (14.2,14.2), (6,26), and (26,6). A comparative assessment of the four approaches is performed with respect to the systematic error occuring in application to Boolean models. It is a surprising result that, except for (26,6), the estimators yield infinitely large systematic errors when the lattice spacing goes to zero. Furthermore, the measurements of the Euler number from 3d data of autoclaved aerated concrete illustrate the influence of the choice of adjacency and the behaviour of the estimators.
Keywords: Euler-Poincare characteristic, discretisation, binary image, neighbourhood, adjacency, Boolean model, systematic error.
INTRODUCTION
In materials’ science, as well as in other research fields, the Euler number (or its density) is used as a characteristic describing the connectivity of the components (constituents) of a composite material or the pore space of a porous medium, see Levitz (2002) and Ohser and Mu¨cklich (2000).
From a theoretical point of view the Euler-Poincare characteristic %n{X), or Euler number for short, of an n-dimensional set X in the Euclidean space Mn is a basic quantity of integral geometry. By means of Crofton’s intersection formulae, the quermassintegrals (Minkowski functionals or intrinsic volumes) can be expressed in terms of the Euler numbers %k defined on sections of X with k-dimensional planes, k = 0,...,n— 1, see Schneider and Weil (2000). This is the basis of the measurement of the quermassintegrals in image analysis. Definitions and properties of the Euler number are recalled in section “The Euler number of a set”.
In the context of image analysis it is usually assumed that the setX is observed on a point lattice n. The intersection Xnn is the mathematical expression for the observable information about X. In practical applications we consider the lattice n restricted to a bounded window W C n. Let 1 X denote the characteristic function of X. The set {(x, 1 X(x)) : x G W n n } is said to be the (binary) image of X observed in W, and the elements of the image are called pixels.
There are two ways of considering digital images of this type. One way is based on discrete (lattice) geometry, in particular integral geometry on the lattice and introduction of discrete Minkowski functionals; see Voss (1993). In the present paper the alternative view is taken, namely that the analysis of the discretised image aims at a good approximation of parameters or features of the original (i.e. non-discretised) setX in Euclidean space, see Serra (1982) for a systematic introduction.
The properties of the discretisation depend heavily on the chosen connectivity, that is the rule according to which the neighbours of a given foreground or background pixel are found. In image analysis, object and background are usually endowed with different connectivities (neighbourhoods) in order to ensure a digital Jordan surface theorem. Typical pairs are (6,26) and (6,18), see e.g. Kong and Rosenfeld (1989); Lee et al. (1991); Lohmann (1998). In this notation, the first component of a pair indicates the number of neighbours a lattice point is connected to if this lattice point belongs to the foreground and the second component denotes the number of used connections to neighbours if the lattice point belongs to the complement (the background). Most algorithms for determining the Euler number in 3d like Serra’s marching cube algorithm Serra (1969); Lee et al. (1991) work with 6 connectivity of the object and 26 connectivity of the background or vice versa, see (Kong and Rosenfeld, 1989, Section 8) and (Lohmann,
11
Ohser J et al: Euler number of discretised sets
1998, Section 3.1.2) for surveys and the references in Ohser et al. (2002b).
Here we follow Ohser et al. (2002b) and use adjacencies based on tessellations to describe the connectivity unambiguously. It was shown in Ohser et al. (2002b) that (14.1,14.1), (14.2,14.2), (6,26), and (26,6) are pairs of complementary adjacencies. That means, their use for foreground and background, respectively, ensures that the values of the Euler numbers for discretised sets and their complements fulfill a consistency relation, i.e. in 3d that both values are identical.
Fig. 1. Microstructure of two specimens of autoclaved aereted concrete (AAC). (a) 320 x 330 x 330 pixels, arranged in a simple cubic lattice of spacing 31 /im. (b) 450 x 500 x 230 pixels of uniform spacing 17/im. Both visualisations show the solid matter of the porous media.
The exact definitions of the adjacencies and the discretisations which they induce are given in section “Discretisation with respect to adjacency”.
In section “Approximation of the Euler number” we show how to approximate the Euler number of X using its discretisation. After recalling the consistency relation in section “Consistency”, we provide in section “Estimation of the density of the Euler number” the estimator for the density of the Euler number of a random closed set based on the discretisation w.r.t. a pair of complementary adjacencies.
The study of real data from samples of autoclaved aerated concrete (AAC) shows that the estimated value of the Euler number can depend considerably on the chosen adjacency (neighbourhood) system. Therefore, in section “Boolean models”, the systematic error for the four estimators, applied to a Boolean model, is calculated. This follows the method applied by Serra (1982), who determined the errors for several neighbourhoods in 2d and for (26,6) in 3d. He already stated that there is a non-negligible systematic error which does not vanish when the lattice spacing c (i.e. the resolution of the equipment for imaging) goes to zero. The results in the present paper show that surprisingly the asymptotic behaviour is much worse for (14.1,14.1), (14.2,14.2) and (6,26). The systematic error even diverges to (minus) infinity for c approaching zero. Fig. 3 in section “Boolean models” illustrates that none of the four adjacencies yields a uniformly best estimator. It depends highly on the parameters of the Boolean model which adjacency performs best. In section “The connectivity of the pore space of AAC” numeric results are presented which show that for practicable resolutions of images the Euler number can be estimated reasonably. In particular for the image in Fig. 1b the estimators based on the four considered pairs of adjacencies do not differ considerably.
THE EULER NUMBER OF A SET
To begin with we recall some facts concerning the Euler number in order to have a comprehensive but also mathematically solid base.
There are several equivalent definitions of the Euler number of a set, see the books of Hadwiger (1957), Matheron (1975), Schneider (1993), and Serra (1982), and Weil’s paper (Weil, 2000).
One way to introduce of the Euler number %n in n is to fix the values
Xn(0/) = 0    and   f(X0) = 1
12
Image Anal Stereol 2003;22:11-19
for any convex bodyX0, and to define the continuation to finite unions of convex bodies by additivity, namely
Xn(Xx uX2) = xn X) +xn{X2) - xniXx nX,)
for convex bodies Xl ,X2.
Generally, for finite unions, this additivity is expressed by a so-called inclusion-exclusion formula. The class of finite unions of convex bodies is referred to as the convex ring or the class of polyconvex sets.
On the convex ring, #n(X) can equivalently be introduced by Hadwiger's recursive definition, see Ohser et al. (2002b). This is the basis for determining the Euler number by counting tangent points of the set X. Let Xc and X denote the complement of X and the topological closure of X, respectively. Hadwiger’s recursive definition can be used for defining Xn(Xc) too, where X is from the convex ring.
For the Euler number of a polytope P, i.e. the convex hull of a finite set of points, see Schneider (1993), the mentioned definitions are coherent with the Euler-Poincare formula in terms of numbers of the lower-dimensional faces of .P. For k = 0,...,n denote by ^k(P) the set of all k-faces of P. In particular, ^°(P) is the set of vertices, ^X(P) the set of edges, ^n-\P) the set of facets, and 3?n(P) is the polytope itself, &n(P) = {P}. Furthermore, let #^k(P) be the number of elements in ,^k(P). Then the Euler number of P can be written as
xn(P)=n(-i)k#^k(P)-     (i)
For a polytope, the Euler-Poincare formula yields that the right hand side equals 1, see (Webster, 1994, Theorem 3.5.1). Formula (1) can be additively extended to the case when P is a finite union of polytopes, i.e. when P is a polyhedron, see also (Jernot etal, 2001, Section 4).
Another aspect, which is of particular importance in image analysis, is the relation between the Euler numbers of the ‘object’, #n(X), and of the ‘background’, %n Xc)-
Under some weak conditions for the set X we get the important relationship
f(Xc)=(-inv(X).        (2)
The consistency relation (2) was shown in Ohser et al. (2002b) (and already in (Lang et al, 2001, Appendix) for those bounded sets X for which both X n B and Xc n B belong to the convex ring for all convex bodies B). A more general version of the assertion of the theorem is proven in Rataj and Zähle (2002). Finally, we remark that (2) is obvious for compact X with nonempty interior. In this case #n(X) = 1 and
xn(X~c) = (-\)n+l.
DISCRETISATION WITH RESPECT TO ADJACENCY
Roughly speaking, discretisation of a set X C n means the approximation of X by a polyhedral set due to observations on a point lattice.
We consider a cubic lattice L3 = cl? (where Z denotes the set of integers) in the 3d space. In our approach, the discretisation is based on polytopes which are parts of the lattice cells. In Ohser et al. (2002b) we developed the corresponding definitions systematically with respect to certain types of tessellations of the lattice cells. Denote by C = [0,c)3,c > 0 the half-open unit cell of the lattice. Obviously Ux£l3 C+ x) = K3, i.e. the cells are spacefilling. In order to define an adjacency system we_ endow C with a set of convex polytopes Pl,...,Pm C C with ^°(Pi C L3, i.e. the vertices of Pi must be lattice points that is points, where the sets X and Xc can be observed. All the other cells C + x are endowed with polytopes which are the translates Pl + x,... ,Pm + x where x G L3.
The adjacency system based on the set of polytopes 3? = {Pj,... ,Pm} is defined as
3
F(&) = \J #¦k(&>)                    (3)
k=0
m
with        &k&)= J \j&kPi + x).
xeL3 i=1
This formal expression means that an adjacency system is formed by the polytopes Pi + x and all their lower-dimensional faces. Thus an adjacency system is already determined by a set & = {Pj,...,Pm} of polytopes.
Now we list four systems which are of particular interest. We skip all considerations of the question which additional properties a reasonable adjacency system should have, see Ohser et al. (2002b) for more details. The vertices of the basic cell C are denoted by x0,...,x7 given by x0 = (0,0,0), xl = (c,0,0), x2 = (0,c,0),x3 = (c,c,0),x4 = (0,0,c),x5 = (c,0,c), x6 = (0,c,c), andx7 = (c,c,c).
(i)   For  the   6-adjacency  (well   known  as  the_6-neighbourhood in 3d image analysis): ^6 = {C}.
13
Ohser J et al: Euler number of discretised sets
(ii) For the 14.1-adjacency: &>ul = {P,...,P} with the six congruent tetrahedra which are convex hulls of vertices of C:
Px = conv({x0,xl,x3,x1}) P2 = conv({x0,xl,x5,x7}) P3 = conv({x0,x2,x3,x7}) P4 = conv({x0,x2,x6,x7}) P5 = conv({x0,x4,x5,x7}) P6 = conv({x0,x4,x6,x7})
see Fig. 2a.
(iii) For the 14.2-adjacency: ^U2 the six tetrahedra
{Pv...,P6}wiih
P1=cow({x0,x1,x3,xs}) P2 = conv({x0,x2,x3,x7}) P3 = conv({x0,x2,x4,x7}) P4 = conv({x0,x3,x5,x7}) P5 = conv({x0,x4,x5,x7}) P6 = conv({x2,x4,x6,x7})
which tessellate the unit cell as shown in Fig. 2b.
(iv) For the 26-adjacency (corresponding to the 26-neighbourhood): ^26 = {conv(^) : "V C {x0,... ,x7}}, i.e. the system of the convex hulls of all subsets of the set of vertices of C
APPROXIMATION OF THE EULER NUMBER
Our approach to the definition of adjacency systems (instead of the neighbourhood graphs used in image analysis) and of the corresponding discretisation of sets is suited to the application of the Euler-Poincare formula (1) to polygonal sets. The Euler number %n{X) can be approximated by the Euler number of the discretisation
Xn^{&)Y\X) =  n{-\)H{&k{&)Y\X),       (5)
see also (Jernot etal, 2001, (4)).
For several considerations it is useful to have a ‘local version’ of this approximation based on the single cells C+x, x G n. In order to ensure that each k-face is counted only once, we have to apply some kind of edge correction. We choose weighting each k-face with -. Here m is the number of closed lattice cells
m
containing the k-face. Formally, for £ > k let ^k r\X be the set of all k-faces F G &k(&>) nX with:
(i)  There is an £-face Fe G &l (C) such that F CFe and
(ii) there is no j-face Fj G ^j{C), j <t,Fjj^F such that F C Fj,
Then (5) can be rewritten as
a)
Fig. 2. The tessellation of the unit cell defining (a) the 14.1 and (b) the 14.2 neighbourhood.
For short, we will write F6 instead of F(^6), and analogously for the other adjacencies. For a given set & the adjacency system F(^) provides the elements (‘bricks’) for discretisation. The discretisation of X with respect to the adjacency W(&) is defined as
Fi
nX = {F£F(#):#°(F)CX},     (4)
i.e. a ‘brick’ F of the adjacency system belongs to the discretisation of X if and only if all the vertices of F (and not necessarily the whole set F) belong to X.
^(F(^)nX) = X X(-i)^-n#(^nX x),
xen k=0             t=k
(6)
with X_x = X — x, the translation of X by —x. For the 3d cuboidal lattice the interpretation of the weights is as follows: All vertices J^0,0 nX get weight 1/8. The edges J^1'1 \1X (edges of the cubes), J^1'2 nX (face diagonals), and ^1'3 r\X (spatial diagonal) get 1/4, 1/2, and 1, respectively. The faces ^02'2 nXand ^2'3 n X are equipped with 1/2 and 1, respectively, and all cells ^03'3 r\X with 1. The formula can be proven rigorously with the help of the inclusion-exclusion principle (i.e. the additivity of the Euler number).
Eq. (6) can easily be implemented. For details of the algorithm see Ohser et al. (2002b).
CONSISTENCY
It is a usual requirement in image analysis that any adjacency for the ‘object’ X has to be consistent with an appropriate ‘complementary adjacency’ used for the ‘background’ Xc. In 2d image analysis it is well known that the ‘background’ has to be treated with the 4-neighbourhood if the 8-neighbourhood is used for the ‘object’, and vice versa in order for
14
Image Anal Stereol 2003;22:11-19
a discrete Jordan curve theorem to hold. In 3d, the 6-neighbourhood is usually combined with the 26-neighbourhood but (6,18) is consistent with a discrete Jordan surface theorem, too, see e.g. Herman (1992). Our criterion is consistency (2) for the approximations of the Euler number in 3d.
Assume that the adjacency systems F and Fc are used for the discretisation of X and of Xc, respectively. Then methods of approximating the corresponding Euler numbers can be illustrated by the following scheme:
X^XnL3 ^FnX-^>^3(FnX) ^x3(X).
Xc^XcnLJ
¥r nXc
¦^>f(FcnXc
.,x\Xc
The pair (F,c) of adjacency systems is called complementary if for all bounded sets Xet3
(i) Ff)Fc = 9 for all F G FnX and Fc e Fc nXc and
(n)x3(¥nX)=x3(¥cnXc).
An adjacency system F(^)  is said to be self-complementary if
X3 (F(&>) nXc) = x3 (F(^) nX)
for all X. Self-complementarity implies that ‘object’ and ‘background’ are discretised with one and the same method. As it has been shown in Ohser et al. (2002b) the following pairs are pairs of complementary adjacency systems:
(FÄ,E
6 ! K 26 )i
Ä4.1,F14.l),
(^14.2,^14.2 ).
(f26,f6;
In Ohser et al. (2002b) sufficient conditions have been given for a setX which guarantee that x3 (F( ^1) n X) = ^3(X), i.e. that the discretised set has the same Euler number as the original set. These conditions imply that X has to be morphologically open and closed (see Serra (1982) for these concepts) with respect to the segments occurring in the adjacency systems used.
Complementary adjacency systems of n are considered in Ohser et al. (2002b).
ESTIMATION OF THE DENSITY OF THE EULER NUMBER
Consider now a random closed set 5 in n which is assumed to be macroscopically homogeneous (i.e. stationary). The density XV of the Euler number can be introduced by
XV
lim
Yo\{rW)
(7)
where vol(-) denotes n-dimensional volume and W a compact convex observation window with \o\(W) > 0.
Assume now that a pair (F, Fc) of complementary adjacency systems is used to estimate the Euler number of a realisation of 5 and that the ‘local version’ of the algorithm according to formula (6) is applied. The density of the Euler number can be estimated from the set 5 observed in W using
XV
1
#(n nW0)vo\(C)
X   X(-i)^n#(^ns_x)   (8)
xen)W0k=0             £=k
where W0 is the reduced window, W0 = WqC, and C = -C, the reflection in 0. Notice that #(n n W0) vol(C) « volW). Furthermore, we remark that the estimator^ may be biased but it is free of edge effects.
The   expectation   of   XVi^)   is,   due   to   the homogeneity of 5,
^XV
vol(C)
£(-lk£2^n  £  P(Jf°(F)n3c = 0).
k=0             l=k         FE&kl
From the complementarity of F and Fc, in particular (ii), and from (2) it follows that
^XV
(-1
\n+i
vol(C)
X(-lkX2^n   £  P(#°(F)nS = 0)    (9) i=k       Fe&kl
k=0
where the &§kc are defined analogously to &§k but with respect to Fc.
As the study of sandstone images in Ohser et al. (2002b) shows, there are relevant applications where the structure is so tiny, compared to the resolution of the discretised image, that the approximation of the Euler number does not provide the true value and considerably depends on the chosen discretisation. Therefore, it is important to assess the estimators which are based on different adjacency systems. One important criterion of quality is the systematic error (bias). Until now, there are no results concerning the error for arbitrary random sets.
15
Ohser J et al: Euler number of discretised sets
BOOLEAN MODELS
For the special case of a Boolean model, explicit formulas and numerical values can be derived, which describe the systematic error of the estimators of the Euler number with respect to the chosen adjacency. Serra (1982) studied the asymptotic behaviour of the bias for the (8,4)-adjacency and the hexagonal grid in two dimensions and for the pair (26,6) in 3d. Using Serra’s ideas, we compare the (14.1,14.1)- and (14.2,14.2)- with the (26,6)- and the (6,26)-adjacency systems.
Homogeneous Boolean models in n
Let O = {x 1,x2,...n denote a homogeneous Poisson point field in W with point density A > 0 (the point field of ‘germs’) and S1, 32,... a sequence of independent and identically distributed (i.i.d.) random compact convex sets (‘grains’ or ‘particles’) with nonempty interior and independent of O. The corresponding (macroscopically) homogeneous Boolean model is defined as the random closed set
s = U(si+xi)-
i=1
For more detailed definition and explanation see Matheron (1975), Ohser and Mu¨cklich (2000), Schneider and Weil (2000), Serra (1982), Stoyan etal. (1995).
Notice that with probability one the intersection of two grains is either empty or has nonempty interior, i.e. Eq. (2) can be applied and (9) holds. The probability occuring on the right-hand side of (9) can be calculated on the basis of the well known formula for Boolean models (see the books cited above),
P(KnS = 0/) = exp{-AEvol(S1ffiK}       (10)
for all compact K C n, where © denotes Minkowski addition. This yields
^V(S)
¦1
in1
vol(C)
X(-1kl2nXexp{-^Evol(? 1
e=k     Fe#kl
k=0
(11)
It seems to be very tedious to perform an exact calculation of
if F has more than two vertices, even in the simplest case that S1 is a ball with random diameter. In order to make the calculation feasible, we follow Serra (1982) in using the approximation
0(F)ns = 0/)«P(Fns = 0/)
forF<EFc, (12)
i.e. the set of vertices ^0(F) is replaced by its convex hull, the set F itself. The probabilities ¥(F n 5 = 0/) can be calculated easily with the help of the Steiner formula (see e.g. Serra (1982), Schneider and Weil (2000)). The approximation (12) seems rather rough at first glance. However, we will see that at least in the cases we examined here, the error induced by (12) is negligible. To assess the overall approximation error in (9) we have to examine
lim
1
0 vol(C)
[p(^0(F)n3 = 0/)-P(Fn3 = 0/)]
(13)
which e.g. does not tend to 0 if F is a line segment. Nevertheless, in the 3d case for (26,6), (14.1,14.1), (14.2,14.2), and (6,26) we have
lim-1i(-1)kŽ2'-3X  [P(^0 F)ns = 0/)
0,c
-P(Ff~l3 = 0/)] =0. (14)
The proof consists of three steps. First, we split the contribution to the approximation error of each element (edge, face or polyhedron) of an adjacency into a part due to its edges and a ‘true’ facial part. Second, observe that only the linear terms in the series expansion of (13) have to be taken into account. Finally, due to the special properties of tessellations, the individual contributions cancel when plugged into the alternating sum. See (Ohser et al, 2002a, Appendix B) for the detailed proof.
The 3d case
There are explicit formulas for the density of the Euler number of the Boolean model first published in Miles (1976). However, it should be noted that in particular for the isotropic 3d case, the formulas given in the literature differ (due to errors in calculation). In (Schneider and Weil, 2000, Korollar 5.4.5), one finds for 3d Boolean models
vol(31©^0(F))=vol(     (J    (31+;
ixe0(F)
XV
-XV ¯
4n          384
(15)
16
Image Anal Stereol 2003;22:11-19
In this formula V, S and M denote the mean value of the volume, of the surface area, and of the integral of the mean curvature, respectively, of the typical particle H1. For the particular case where the ‘particles’ are balls of constant diameter d,Ei = Bd, we obtain
XV = e-xV[X-u2X2V + u3X3V2]          (16)
with
37^
32
V :
K
6<
The particular case of a 3d Boolean model with balls of constant diameter is studied now in detail. Explicit but rather long formulas for the expectation EfV based on the approximation (12) are given in (Ohser et al, 2002a, Appendix A.3). As it is shown there, E^ can be expressed in terms of the volume density VV of the Boolean model and the ratio ß of the diameter and the lattice spacing,
^TV~fVViß)
V
1
,-xV
c
We use the symbol « to indicate that the computation of fVV,ß) is based on the approximation (12). These calculations allow a comparison of the four estimators (corresponding to the four pairs of adjacencies considered here) with respect to the approximate
1.0 0.5
0.1
0.05
0.01
0.005
0.002
i------1—r
0      0.3
0.5
0.7
V„
0.9
Fig. 3. Best estimators of' XV for the Boolean models with balls of fixed diameters d and varying volume density VV. This graph shows the regions of the parameter space {VV,1/ß) : 0 < VV < 1,0.002 < 1/ß < 1} where the estimators ofXV have the smallest bias; red for (6,26), green for (14.4,14.1), blue for (14.2,14.2), and yellow for (26,6). In the shaded regions, the relative bias \^XVlXV ~ 1 is larger than
systematic error \fVV,ß) — XV
graph in Fig. 3 shows in which region of the parameter space which of the four estimators behaves best.
The approximation (12) also allows to consider the limit of the systematic error for the lattice spacing c —> 0. Taylor expansion offVV,d/c) for c provides
7j£~ — XV\. The      20 % if^XV is approximated using (17).
The limits of EXV as c —> 0 are surprising. It is easy to see that for u 1 > 0 the right-hand side of (17) is divergent. More precisely, for the adjacency (26,6) the limit of the bias of the estimator XV is
^XV ~ e~XV [*> - (u1ß + u2)X2V + u3X3V2] +
o(c
(17)
limpXV-XV]=eXV[-
-v2l2V + v3X3V2]
(18)
where numerical values for the coefficients u1,u2, and u3 are given in Table 1. Notice that the right-hand side of (17) is of a similar structure as the one of (16). Details on the derivation of (17) as well as analytical expressions for the coefficients can be found in (Ohser et al., 2002a, Appendix A). Furthermore, we remark that the result for (26,6) coincides with that of Serra (1982, p. 557), up to a difference in the coefficient u2.
where v2 and v3 can be computed from the values given in Table 1, v2 = 32, v3 = 0.841870... This means that the for (26,6) the estimator of XV is not asymptotically unbiased. For (14.1,14.1), (14.2,14.2), and (6,26) we even get a worse result
lim [ES
c-s-0
¦XV]
(19)
Table 1. Numerical values of the coefficients u1, u2, and u3 for Eqs. (16) and (17).
Equation	adjacency	u1	u2	u3
(16)	-	-	3	0.925 277 ...
(17)	(26,6)	0	4.5	1.767147...
(17)	(14.1,14.1)	0.023 515...	3.942939...	1.444278...
(17)	(14.2,14.2)	0.062098...	4.809625...	1.782345...
(17)	(6,26)	0.007718..	3.284248...	1.068 663 ...
17
Ohser J et al: Euler number of discretised sets
The   considerations  at the   end   of subsection
“Homogeneous Boolean models in     n” show that
these results are not affected by the  approximation (12).
THE CONNECTIVITY OF THE PORE SPACE OF AAC
As an application we consider the density of the Euler number of the pore space of autoclaved aerated concrete (AAC). The data of the two specimens shown in Fig. 1 are given as 3d images obtained by X-ray microtomography (XCT). The pore space of these microstructures can be modelled as a macroscopically homogeneous random set 5.
Table 2 shows that experimental values for XV can depend highly on the chosen adjacency. Differences in the measurement values are a consequence of the tiny parts (compared to the resolution of the imaging equipment) of the microstructures. This means that, e.g., there occur pairs of adjacent lattice points which both belong to the complement 5c but they are separated by a small connection of solid matter 5 in between. This property can be formally expressed as morphological non-regularity of the set 5, see Ohser etal. (2002b).
In practical applications, the Euler number should be measured with respect to several adjacencies. Then the differences between the results provide an impression of the bias of the measurements.
DISCUSSION
The general approach to the discretisation of a set Xd3, when observations on a lattice L3 are given, is based on the construction of a polyhedron in each of the lattice cells. Intuitive arguments suggest, that the approximation is improved, if the elements used for this construction are smaller parts of the cells. Thus one can expect a better adaptation of the discretised set to the original one, if (as it is done in (14.1,14.1) or (14.2,14.2), respectively) tetrahedra and triangles are used as elements, rather than the whole cells and faces. Moreover, the best fit of the discretisation
of the complementary set Xc seems to be provided by (6,26) where in each cell the convex hull of the complementary set is used. This was a main motivation (additional to self-consistency) for us to introduce the new 14-neighbourhoods in Ohser et al. (2002b).
This intuition is supported by considerations in two dimensions: There the systematic error when estimating the Euler number of the complement of a Boolean model (with discs of constant radius) is reduced if the 6-neighbourhood is used instead of the 4-neighbourhood of the complementary set. (Serra (1982, pp. 493/494) had similar results when he compared the 4-neighbourhood with the hexagonal grid.) Thus the asymptotic results presented in (18) and (19) are quite surprising from an intuitive point of view: The rather ‘rough’ discretisation with the 6-neighbourhood (of the complementary set) is the only one of the considered adjacencies which provides an asymptotically finite systematic error. The other three adjacencies lead to larger and larger errors if the lattice constant c decreases to zero. Nevertheless, for realistic lateral resolution (c = d/10. ..d/5, i.e. about 5 to 10 pixels per diameter), the use of 14.1 or 14.2 can lead to better results than that of the other adjacencies, see Fig. 3.
Our results shed some light on the structure of the complement of a Boolean model in M3. This structure is complicated, tiny, and far from being morphologically regular w.r.t. the lattice cell, see Ohser et al. (2002b). The present study shows that for this type of set there can occur unexpected effects when the Euler number is estimated. The ‘rough’ 6-neighbourhood misses a lot of the features of the structure. The more sensitive 14- and 26-neighbourhoods miss less. However, this can still worsen the estimator of the Euler number. Fig. 3 shows that it is not possible to choose an optimal adjacency. Even for small ranges for the parameters all four adjacencies can occur as the optimal one. Moreover, even when the optimal adjacency is used, the error can be considerable. Nevertheless, notice that formula (17) can be understood as a ‘discrete adaptation’ of Miles’ formula (15) or (16), respectively, and thus it links the estimator XV with other characteristics of the Boolean model.
Table 2. Experimental data for the solid matter of AAC specimens, estimates of the volume density VV and \ density of the Euler number XV w.r.t. four pairs of complementary adjacency systems.
AAC specimen (pore space)
s171b, Fig. 1a s177b,Fig. 1b
V V [%]
59 86
,-3l
(f6,f26;
XV mm ~
(14.1 '14.1 )       (,14.2'14.2J
4.58 -58.13
-0.17 -58.36
-2.32 -63.83
(F26,F(
-4.57 -59.11
18
Image Anal Stereol 2003;22:11-19
ACKNOWLEDGEMENTS
We are indebted to E. Schlegel for supplying the AAC specimens and S. Gondrom for the XCT scans. We also thank the referees for their helpful comments.
REFERENCES
Hadwiger H (1957). Vorlesungen über Inhalt, Oberflache und Isoperimetrie. Heidelberg: Springer.
Herman   GT   (1992).   Discrete   multidimensional   Jordan
surfaces. Graph Models Image Process 54:507-15.
Jernot JP, Jouanot-Chesney P, Lantuéjoul C (2001). Evaluating the Euler-Poincaré characteristic of a set using a spatial tesselation. Image Anal Stereol 20:149-52.
Kong TY, Rosenfeld A (1989). Digital topology: introduction and survey. Comput Vision Graphics Image Process 48:357-93.
Lang C, Ohser J, Hilfer R (2001). On the analysis of spatial binary images. J Microsc 202:1-12.
Lee C, Poston T, Rosenfeld A (1991). Winding and Euler numbers for 2d and 3d digital images. CVGIP Graph Models Image Process 53:522-37.
Levitz PE (2002). Generic methods for the characterization of porous materials. In: Schuth F, Sing KSW, Weitkamp J, eds. Handbook of Porous Solids, vol. 1. Weinheim: Wiley-VCH, 37-80.
Lohmann G (1998). Volumetric image analysis. Chichester, New York: Wiley-Teubner.
Matheron G (1975). Random sets and integral geometry. New York: J. Wiley & Sons.
Miles RE (1976). Estimating aggregate and overall characteristics from thick sections by transmission microscopy. J Microsc 107:227-33.
Ohser J, Mücklich F (2000). Statistical analysis of microstructures in materials science. Chichester, New York: J. Wiley & Sons.
Ohser J, Nagel W, Schladitz K (2002a). The Euler number of discretised sets - surprising results in three dimensions. Tech. rep., Fraunhofer ITWM, Kaiserslautern. http://www.itwm.fhg.de/mab/employees/ohser/index_en.php.
Ohser J, Nagel W, Schladitz K (2002b). The Euler number of discretized sets - on the choice of adjacency in homogeneous lattices. In: Mecke KR, Stoyan D, eds. Morphology of Condensed Matter. Heidelberg: Springer.
Rataj J, Zähle M (2002). Normal cycles of Lipschitz manifolds by approximation with parallel sets. Differential Geometry and its Applications.
Schneider R (1993). Convex Bodies. The Brunn-Minkowski theory. Cambridge: Cambridge University Press.
Schneider R, Weil W (2000). Stochastische Geometrie. Stuttgart, Leipzig: Teubner.
Serra J (1969). Introduction à la Morphologie Mathématique. Fontainebleau: Cahiers du Centre de Morphologie Mathématique, Booklet No. 3, E.N.S.M.P.
Serra J (1982). Image analysis and mathematical morphology, vol. 1. London: Academic Press.
Stoyan D, Kendall WS, Mecke J (1995). Stochastic geometry and its applications, 2nd ed. Chichester: J. Wiley & Sons.
Voss K (1993). Discrete images, objects and functions in Zn. Heidelberg, New York: Springer.
Webster RJ (1994). Convexity. New York: Oxford University Press.
Weil W (2000). Mixed measures and homogeneous Boolean models. In: Mecke KR, Stoyan D, eds. Statistical Physics and Spatial Statistics. Heidelberg: Springer.