Image Anal Stereol 2001;20:149-152 Original Research Paper
EVALUATING THE EULER-POINCARE CHARACTERISTIC OF A SET USING A SPATIAL TESSELLATION
J ean -P aul J ernot, P atricia J ouannot -C hesney and C hristian L antuejoul
1ISMRA, CRISMAT/ESCTM, 14050 Caen, France, 2Ecole des Mines, Centre de Geostatistique, 77305
Fontainebleau, France
e-mail: jernot@ismra.fr, jouannot@ismra.fr, lantu@cg.ensmp.fr
(Accepted October 19, 2001)
ABSTRACT
A new formula is established to evaluate the Euler-Poincare characteristic of a polyconvex subset X in d starting only from measurements of X in the cells of a tessellation. Simplifications occur whenX is a union of cells of the tessellation, leading to another formula that unifies and extends several classical digitization results.
Keywords: tessellation, Euler-Poincare characteristic, discretization.
INTRODUCTION                                                    I       I       I       I     I     I       I       I   .
Let X be a polyconvex subset (finite union of compact convex subsets) in d (usually d = 1,2 or 3). How can we evaluate the Euler-Poincare characteristic (EPC) of X when X is too large to be entirely contained in only one measurement field? An answer was given when the measurement fields are parallelotopes (Bhanu-Prasad et al, 1989). This paper gives a more general answer by assuming the measurement fields to be convex polytopes. A simple and natural way to introduce them is to consider them as the cells of a tessellation as in the next section. The formula for the EPC of X is then given in the following section and shown to generalize that of Bhanu-Prasad et al. Simplifications occur in the case when X is a union of cells of the tessellation. The formula thus derived has interesting consequences when the cells of the tessellation are interpreted as digitization cells. In this case, the formula obtained unifies and extends several classical digitization results (e.g. Serra, 1982).
TESSELLATION
A tessellation is a family (Zi, i G I of subsets in Wd that satisfies the following properties:
i)   All  Zi  are  convex polytopes  with  non-empty interior.
ii)  The interiors of the Zi ’s are pairwise disjoint.
iii) The union of the Zi ’s is   d.
iv) The family is locally finite: the number of Zi ’s hitting any bounded set is finite.
W?
Fig. 1. Examples of planar tessellations.
Each polytope Zi is called a cell. Depending on the problem addressed, a cell can be seen either as a measurement field or as a digitization cell. Because of i) and iv), a convex tessellation has a countable number of cells. Examples of tessellations include regular grids, the zones of influence of any infinite and locally finite population of points, the polytopes limited by any infinite and locally finite set of hyperplanes. Fig. 1 shows a few examples of planar tessellations.
A tessellation is usually handled via the intersections between its cells. The non-empty ones are called facets. Note that a facet is not necessarily a face of a polytope. For instance, the horizontal edges of the rectangles on top right of Fig. 1 are not facets. Note also that a facet can often be written in more than one way as an intersection of cells. For instance, a vertex on top left of Fig. 1 can be written as the intersection either of 4 rectangles or of 2 diagonally opposed rectangles. Let F be a facet. The dimension
149
Jernot JP et al: Evaluating the Euler-Poincare characteristic
of F, say dim,F, is defined as the dimension of the smallest affine subspace that contains F. It should not be mistaken with the order of F that is the number of cells that contains F. The set of all facets is denoted by J^.
REGIONAL MEASUREMENT
LetX be a polyconvex subset of M.d, and let (Zi, i e I) be a tessellation in M.d. Assume that its cells act as measurement fields. In order to evaluate the EPC N(X) of X, let us start with
N(X)    =   N(Xf]d)
=   N(Xn(UieIZi)
= N(uieI(XnZi).              (1)
Because the EPC is additive, N(X) can be rewritten N(X) =   X (-1# J-1NiXnZJ),        (2)
where # Jis the cardinality of J, and where ZJ = r\jeJZj. (Eq. (2) is a mere generalization of the standard formula N(X) = N(X D Zi + N(X n Zj - N(X n Zi n Zj) that holds if X is contained in the union of both cells Zi and Zj.) The next step is to group all ZJ ’s corresponding to the same facet. After some calculations (see Appendix 1), we obtain
N(X) =   ^(-1)d-dimFN(Xr}F).         (3)
Fig. 2. Example of regional measurement. The measurement fields are the cells of the tessellation. The EPC of the dark domain is N(X) = 14 - 23 + 10 = 1.
As an illustration, suppose that X is the dark domain of Fig. 2. This domain hits 14 facets of dimension 2 (cells), 23 facets of dimension 1 (edges) and 10 facets of dimension 0 (vertices). Moreover N(X(~]F) = 1 for each facet F hitting X. Accordingly, the EPC of X is N(X) = 14 - 23 + 10 = 1.
DISCRETIZATION
The same tessellation (Zi, i G I) is still considered, but from now on the setX is assumed to be a union of cells. One possible interpretation is to say thatX is a digitized set, the cells acting as ’pixels’ or digitization cells. (For practical purposes, we do not limit ourselves to regular tessellations). It can be shown that the EPC of X involves only the facets contained in X (see Appendix 2)
N(X) =   I(-1)dimF1FcX-              (4)
F£,¥
In the case where X is a cell of the tessellation, Eq. (4) is nothing but the usual Euler formula for polytopes (see Appendix 2)
1=   I(-1)dimF1FcX,                 (5)
Fe.ß'
whereas Eq. (3) gives
<-1)d = y (-1dimF1      .       (6)
FE,jf
Fig. 3. If X is a union of cells, then only the facets within it need to be considered. Eq. (4) gives N(X) = 9-45 + 36 = 0.
As an example, consider the shaded domain on Fig. 3. This domain contains 9 facets of dimension 2 (cells), 45 facets of dimension 1 (edges) and 36 facets of dimension 0 (vertices). Applying Eq. (4), we find that its EPC is equal to 9 — 45 + 36 = 0. Of course, the EPC of X could have been obtained as well starting from Eq. (3): N(X) = 27 - 63 + 36 = 0. Notice however that Eq. (3) produces more complicated coefficients than Eq. (4) for two reasons. Firstly, all facets hitting X and not only those contained in X are accounted for. The difference is already significant in the present two-dimensional case (27 cells instead of 9, and 62 edges instead of 45). It may be considerable for three-dimensional digitized
150
Image Anal Stereol 2001;20:149-152
sets. Secondly, the contribution of each facet is not always equal to 1 (e.g. the edge in the hole of X has a contribution equal to 2).
Eq. (4) reminds us ofthat used for measuring the EPC of sets digitized on regular grids (e.g. Serra, 1982) for the square, triangular and cubic grids). This is not surprising insofar as regular grids and tessellations can both be used for sampling a set. In the first case, the sampled set is countable and its topological properties are specified by a graph induced on the grid. In the second one, the set is approximated as a union of cells (Schmitt, 2000). It therefore still remains continuous. Its topological properties are specified by the neighbourhood relationships between the cells.
The various EPC formulae for digitized sets can simply be obtained by replacing each pixel of the digitized set by its zone of influence on the grid, taking the union of the zones of influence and applying Eq. (4) to the set obtained. This procedure works whatever the type of grid considered.
CONCLUSION
In this paper two formulae have been proposed for evaluating the EPC of continuous sets using tessellations. The first one is designed to cope with the problems associated with regional measurements. The second one provides a unifying framework for measuring the EPC on digitized sets. Both formulae are valid whatever the workspace dimension.
Although not explicitly mentioned in the paper, the formulae obtained can be extended to evaluate any additive functional on polyconvex sets (e.g. Minkowski functionals).
REFERENCES
Bhanu-Prasad et al. (1989). Unbiased estimation of the Euler-Poincare characteristic. Acta Stereol 8:101-6.
Schmitt M (2000). Random sets, sampling and connectivity. Geostat’2000. Somerset West (South Africa).
Serra   J   (1982).    Image    analysis   and   mathematical morphology. London: Academic Press.
Sommerville DMY (1958). An introduction to the geometry of n dimensions. New York: Dover Publications.
APPENDIX 1: PROOF OF EQ. (3)
Because of (2), we already know that the EPC of X can be written as
N(X)= X e(F)N(XnF)               (7)
with
JCI
It remains to show that the valuation e (F) is equal to (_1)d-dimF for each facet F. This is made by induction on the workspace dimension.
Suppose at first d = 1. If dimF = 1, then F is a cell and e(F) = (-1)1"1 = 1. If dimF = 0, then F is the intersection of two adjacent cells and e(F) = (-1)2-1 = — 1. In both cases, we have e(F) =
I__1 \d—dimF
Suppose now that the result is valid for tessellations in M.d~1. We want to establish it for tessellations in Rd. To achieve this goal, two cases are considered:
First case: dim F > 0
Then the (relative) interior of F contains at least two distinct points. Let H be their medial hyperplane. The tessellation 3? = (Zt,i G I) induces another tessellation T = (Z'i,i G I i in H, with Zi = ZiC\H, andI'= {i€I: ZinH^0/}.
Fig.   4.  Example   of a  tessellation  induced on  a hyperplane.
Note that FC\H is a facet of 2f'. Its valuation is e'(Ff\H) = EjcI(- 1)# J-1 1 ZJ<=FH. But the subsets J C I' such that Z'J = FC\H coincide with the subsets JcI such that ZJ = F. Accordingly, e'(FnH) = e (F). Moreover, we have e'(Fr\H) = (-1)d-1-dim(FnH) because of the induction assumption. Finally, the dimension ofFDH is dimF — 1. Consequently,
e(F)   =   e'(Fr\H)
—      (—1)d~ 1 -dim(FnH) _      / _1\d-1-(dimF-1
151
Jernot JP et al: Evaluating the Euler-Poincare characteristic
Second case: dim F = 0
In this case F is a vertex, say v. There exists a scalar 5 > 0 such that the hypersphere S with center v and radius <5 hits all facets that contain v (except {v} itself) and only them. The intersections of these facets and S are the faces of a hyperspherical polytope, on which the Euler-Poincare formula (Sommerville (1958)) can be applied

GDF
1-(-1)
(9)
(GO F means G D F and G^F). Using the fact that dim(G n S) = dim G — 1, we can derive
GeJ?
i d— dim G
GDF
1-(-1)d
(10)
Note also that the facets involved in the summation have their dimension strictly positive. According to the first case, this gives
X £(G) 1 GF
ggJ"
1-(-1)d
(11)
Now, the left hand side of this equation is very similar to what we get if we apply (5) with X = F. The only difference is that the facet F does not appear in the summation. Accordingly, we have 1 — e(F) = 1 — (—1)d, or equivalently
d—dim F
(12)
e(F) = {-1)d = (-1) which completes the proof.
APPENDIX 2: PROOF OF EQ. (4)
As a matter of fact, we are going to establish a more general result than Eq. (4): if X is a finite union of facets, then
N{X)
Feß"
\dim F
FcX ¦
(13)
Let us assume at first thatX is a facet. Then X can be seen as a convex polytope of ffi.dimX. Its faces are the facets of the tessellation that it contains. Applying the Euler formula, we obtain
1-(-1)
dimX
X(-1)
Feß
dim F
FCX '
(14)
(FCX means F C X and F +X). But 1 = N(X) and the term (—1)dimX corresponds to the facet F = X. Therefore the formula is valid for facets.
Assume now that X is a finite union of facets, say X = UjeJFj. Because N is additive, we have
N(X) =    £   (-1)# K-1N FK).          (15)
Each FK is either a facet or empty. In both cases, we can write
N(FK) =   X(-1)dimF1 F FK
Fe-9
(16)
Hence
N(X) =    £  (-1)# K"1 X(-1)dimF 1
0/LKCJ                   FeJ"
The summation order is now reversed
FCFK
(17)
N(X)   =     X(-1)dimF 1FCX    X    (-1   # K   1 1 FKDF-Feß                             0/KCJ
(18)
Now, let L = {l G J\Ft D F}. Note that FK D F if and only if K C L. Consequently we have
X (-1)# K-11 FK F = X (-1:
#K-1
(19)
Because the number of subsets of L with cardinality k is  # kL), the right-hand side is equal to
X   ("1)# K"1    =    XffV1)k"1       (20)
tKGL                               k=1 \k J
0/KCL
(-1+1)#L-1
1.
(21)
(22)
It then suffices to insert this result into Eq. (18) to get the desired result.
152