GEOMETRICAL PROPERTIES OF 3D DIGITIZED IMAGES - Fundamentals of Three-Dimensional Digital Image Processing - page 93

Fig. 4.11. Example of the triangulation method for calculating Euler number. Let
us consider a figure consisting of three voxels X, Y and Z shown here. Their values of
n k s in 4.7.1 are given as the table above corresponding to each type of connectivity.
For example, n 0 is the number of vertices in this figure. Each voxel (a cube) has
eight vertices. Therefore, the number of vertices in this figure n 0 is 24 (= 8 × 3 )
for the 6-c case. In the 26-c case, voxels X and Y are connected and the vertex V 1
is not a vertex of this figure. The edge e 1 is not the edge of the figure, because V 1
and e 1 are inside the figure in the 26-c case. For details, see [Gray71, Toriwaki02a].

Then, the amount of the contribution ∆ E ( V ) to the Euler number E at the

vertex V is given by,

∆ E ( V )= ∆n 0 − ∆n 1 + ∆n 2 − ∆n 3 . (4.41)

The Euler number E is obtained by adding ∆ E ( V ) of all vertexes in a 3D

object, that is,

=
V

E ∆ E ( V ) . (4.42)

The type of connectivity should be taken into consideration again in the sim-
ilar way as was presented in Fig. 4.11. An example is shown in Fig. 4.12.
The value of ∆

E ( V ) defined above is uniquely determined by the configu-

ration of 1-voxels in ( V ). Since there are 256 possible configurations and by

considering various symmetric relations it is known that only 22 among them
are different patterns, the value of ∆

S

( V ) for each configuration can be cal-
culated beforehand and stored in the form of a table. Thus, the computation
of the Euler number is reduced to the iterative table searches and additions.
All of possible 2

E

× ×

2 2 configurations are shown in Table 4.4 with values of

∆ E

( V ).
An ecient algorithm to find which pattern among these 22 cases a given

2 × 2 × 2 subpattern corresponds to is given as follows.

Algorithm 4.1. Denote the number of 1-voxels in S ( V )by n 0 . Then the value

of the contribution to the Euler number ( V )atthevertex V is determined

by the flowchart in Fig. 4.13 and Table 4.4.

E