Image Processing Reference
In-Depth Information
C
1
C
2
C
3
B
B
C
3
C
1
C
2
(a)
(b)
FIGURE 1.20: (a) Connected components of foreground points (differently
colored) and background points (white) of the 2-D point set in a (4,8) grid,
and (b) corresponding adjacency tree. (See color insert.)
2. χ(S) = 1, if S is convex and not null.
3. For any two polyhedral sets S
1
and S
2
, the following property holds:
χ(S
1
S
2
) = χ(S
1
) + χ(S
2
)−χ(S
1
S
2
).
Following this definition, one can compute the Euler number of an arbi-
trary triangulation of S in 3-D as follows:
χ(S) = n
p
−n
e
+ n
f
−n
v
(1.6)
where n
p
, n
e
, n
f
, and n
v
denote numbers of points, edges, triangles, and
tetrahedra, respectively. In 2-D the above number can be found to be equiv-
alent to the difference between the the number of connected components and
holes for a polyhedral set. In 3-D it is equal to the sum of the number of
connected components and cavities minus the number of tunnels present in it.
For example, the Euler number of a hollow cube is 2, as it has one connected
component and a cavity. But the Euler number of a hollow prism is zero, as
it has a tunnel.
In a digital grid, Euler characteristics are defined by transforming a set
of digital points into an equivalent analog form. For a digital picture P =
(G
2
,m,n,S), its transformed topologically equivalent analog form T(P) is
obtained by taking the union of all the points in S, all the edges formed by a
pair of neighbors in S, and all the unit squares or unit right-angled triangles
depending upon the type of grid connectivity. For a (4,8) grid, it takes all
unit squares formed by points in S so that its sides are of unit length. On the
other hand, in (8,4) grid, it takes all the unit right an angled triangles, so