3.5.1.2Boundary Diameter

The diameter of a boundary B is defined as

$Dia(B)=\underset{i,j}{\text{max}}[D(b_i,b_j)]b_i\in B,b_j\in B(3.17)$

where D is a distance measurement. The value of the diameter and the orientation of a line segment connecting the two extreme points that comprise the diameter (this line is called the major axis of the boundary) are useful descriptors of a boundary. The minor axis of a boundary is defined as the line perpendicular to the major axis, of such a length that a box passing through the outer four points, where the boundary is intersected with the two axes, completely encloses the boundary. This box is called the basic rectangle, and the ratio of the major to the minor axis is called the eccentricity of the boundary, which is also a useful descriptor.

One example of the diameter of a boundary is shown in Figure 3.25. Note that the diameter can be measured using different distance metrics (such as Euclidean, city-block, chessboard, etc.) and with different results.

3.5.1.3Boundary Curvature

The curvature of a curve is defined as the rate of the change of the slope. As the boundary is traversed in the clockwise direction, a vertex point p is said to be part of a convex segment if the change in the slope at p is nonnegative; otherwise, p is said to belong to a segment that is concave. In general, obtaining a reliable measurement of curvature at a point in a digital boundary is difficult because these boundaries tend to be locally “ragged.” However, using the difference between the slopes of adjacent boundary segments (which have been represented as straight lines) as a descriptor of the curvature at the point, where the segments intersect, sometimes has proven to be useful.

For 3-D images, surface curvature is defined by two maximum and minimum radii. If both are positive as viewed from “inside” the object bounded by the surface, the surface is convex. If both are negative, the surface is concave, and if they have opposite signs, the surface has a saddle curvature. Figure 3.26 shows one example for each case, where Figure 3.26(a) is for convex, Figure 3.26(b) is for concave, and Figure 3.26(c) is for saddle. The total integrated curvature for any closed surface around a simply connected object (no hole, bridge, etc., exist) is always 4π.

3.6.1.1Area of Object

The area of an object region provides a rough idea about the size of the region. It can be computed by counting the number of pixels in the region:

$A={\displaystyle \sum _{(x,y)\in R}1}(3.20)$

Given a polygon Q whose corners are discrete points, let R be the set of discrete points included in Q. Let NB be the number of discrete points that lie exactly on the polygonal line that forms the borders of Q and let NI be the number of interior points (i.e., non-border points) in Q. Then, |R| = NB + NI. The area of Q, denoted A(Q), is the number of unit squares (possibly fractional) that are contained within Q and is given by Marchand (2000)

$A(Q)=N_1+\frac{N_{\text{B}}}{2}-1(3.21)$

Consider the polygon Q shown in Figure 3.30(a). The border of Q is represented as a continuous bold line. Points in Q are represented by discs (black • and white °). Black discs represent border points (i.e., corners and points that lie exactly on the border of Q). Empty (white) discs represent interior points. Clearly, NI = 71 and NB = 10. Therefore, A(Q) = 75.

It is necessary to distinguish the area defined by a polygon Q and the area defined by the contour of P, which is defined from the border set B. Figure 3.30(b) illustrates the resulting contour obtained when 8-connectivity is considered in P and 4-connectivity is considered in Pc. The area of P is clearly 63. One can verify that the difference between this contour-enclosed set and A(Q) is exactly the area of the surface between the contour and Q (shaded area).

3.6.1.2Centroid of Object

It is often useful to have a rough idea of where an object region is in an image. Centroid indicates the mass center of an object and the coordinates of a centroid are given by

$\overline{x}=\frac{1}{A}{\displaystyle \sum _{(x,y)\in R}x}(3.22)$

$\overline{y}=\frac{1}{A}{\displaystyle \sum _{(x,y)\in R}y}(3.23)$

In cases when the scale of objects is relatively small compared to the distance between objects, the object regions can be approximately represented by a point located at the centroid.

For an irregular object, its centroid and geometric center are often different. One example is given in Figure 3.31, where the centroid is represented by a square, the intensity weighted centroid is represented by a star, and the geometric center determined by the circumscribed circle is represented by a round point.

3.6.1.3Region Density

Density (Densitometric) features are different from geometric features in that they must be computed based on both the original (grayscale) images and segmented images. Density is often represented in an image by gray levels. Commonly used region density features include maximum, minimum, mean, and average values as well as variance and other high order moments. They can be obtained from the gray-level histogram.

Several typical density feature descriptors are listed as follows:

3.6.1.4Invariant Moments

For a 2-D discrete region f(x, y), its (p + q)th moment is defined as (Gonzalez 2002)

$m_{pq}={\displaystyle \sum _x{\displaystyle \sum _y{x}^p{y}^{p}f\left(x,y\right)}}\left(3.28\right)$

It has been proven that mpq is uniquely determined by f(x, y). On the other hand, mpq also uniquely determines f(x, y).

The moments around the center of gravity are called central moments. The (p + q)th central moment is defined by

${\mu }_{pq}={\displaystyle \sum _x{\displaystyle \sum _y{\left(x-\overline{x}\right)}^p{\left(y-\overline{y}\right)}^{q}f\left(x,y\right)}}\left(3.29\right)$

where x = m10/m00 and ȳ = m01/m00 are just the centroid coordinates defined in eqs. (3.22) and (3.23). Sample values of the first five moments for some simple images (the coordinate center is at the center of the image, pixels have unit size) shown in Figure 3.32 are given in Table 3.3 (Tomita, 1990).

The normalized central moment (normalization with respect to object area) of f(x, y) is defined by

${\eta }_{pq}=\frac{{\mu }_{pq}}{{\mu }_{00}^{\gamma }}\text{where}\gamma =\frac{p+q}{2}+1,p+q=2,3,\mathrm{...}\left(3.30\right)$

Table 3.3: The first five moments for images shown in Figure 3.32.

The following seven moments that are invariants to translation, rotation, and scaling are composed by normalized second and third central moments:

${\varphi }_1={\eta }_{20}+{\eta }_{02}\left(3.31\right)$

${\varphi }_2={\left({\eta }_{20}={\eta }_{02}\right)}^2+4{\eta }_{11}^2\left(3.32\right)$

${\varphi }_3={\left({\eta }_{30}=3{\eta }_{12}\right)}^2+{\left(3{\eta }_{21}-{\eta }_{03}\right)}^2\left(3.33\right)$

${\varphi }_4={\left({\eta }_{30}+{\eta }_{12}\right)}^2+{\left({\eta }_{21}+{\eta }_{03}\right)}^2\left(3.34\right)$

$\begin{array}{c}{\varphi }_5=\left({\eta }_{30}-3{\eta }_{12}\right)\left({\eta }_{30}+{\eta }_{12}\right)\left[{\left({\eta }_{30}+{\eta }_{12}\right)}^2-3{\left({\eta }_{21}+{\eta }_{03}\right)}^2\right]\\ +\left(3{\eta }_{21}-{\eta }_{03}\right)\left({\eta }_{21}+{\eta }_{03}\right)\left[3{\left({\eta }_{03}+{\eta }_{12}\right)}^2-{\left({\eta }_{21}+{\eta }_{03}\right)}^2\right]\end{array}\left(3.35\right)$

${\varphi }_6=\left({\eta }_{20}-{\eta }_{02}\right)\left[{\left({\eta }_{30}+{\eta }_{12}\right)}^2-{\left({\eta }_{21}+{\eta }_{03}\right)}^2\right]+4{\eta }_{11}\left({\eta }_{30}+{\eta }_{12}\right)\left({\eta }_{21}+{\eta }_{03}\right)\left(3.36\right)$

$\begin{array}{c}{\varphi }_7=\left(3{\eta }_{21}-{\eta }_{03}\right)\left({\eta }_{30}+{\eta }_{12}\right)\left[{\left({\eta }_{30}+{\eta }_{12}\right)}^2-3{\left({\eta }_{21}+{\eta }_{03}\right)}^2\right]\\ +\left(3{\eta }_{12}-{\eta }_{30}\right)\left({\eta }_{21}+{\eta }_{03}\right)\left[3{\left({\eta }_{30}+{\eta }_{12}\right)}^2-{\left({\eta }_{21}+{\eta }_{03}\right)}^2\right]\end{array}\left(3.37\right)$

Figure 3.33 gives one example to show the invariance of the above seven invariant moments. In Figure 3.33, Figure 3.33(a) is the original test image, Figure 3.33(b) is that image after 45° rotation counterclockwise, Figure 3.33(c) is that image reduced to half size, and Figure 3.33(d) is the mirror image of Figure 3.33(a). The seven moments defined in eqs. (3.30–3.36) are computed for all four images, and the results are listed in Table 3.4. The four values for each moment are quite close with some small differences that can be allocated to round-off in computation.

Table 3.4: Some test results of invariant moments.

The above-discussed seven invariant moments are suitable for describing regions. They can also be used to describe the region boundary, but a modification is necessary (Yao, 1999). For a region f(x, y), under a scale change, x′ = kx, y′ = ky, its moments are multiplied by kpkqk2. The factor k2 is related to the area of an object. The center moments of f(x′, y′) become ${\mu }_{pq}={\mu }_{pq}{k}^{p+q+2}.$ The normalized moments are defined as

${\eta }_{pq}=\frac{{\mu }_{pq}}{{\left({\mu }_{00}\right)}^{\gamma }}\left(3.38\right)$

In order to make the normalized moments invariant to scaling, let ${{\eta }^{\prime }}_{pq}={\eta }_{pq},$ and then

$\gamma =\left(p+q+2\right)/2\left(3.39\right)$

For a boundary, scaling causes the change of the perimeter of the boundary. The change factor is not k2 but k. The center moments now become ${{\mu }^{\prime }}_{pq}={\mu }_{pq}{k}^{p+q+1}.$ In order to make the normalized moments invariant to scaling, let ${{\eta }^{\prime }}_{pq}={\eta }_{pq}$ and

$\gamma =p+q+1\left(3.40\right)$

3.6.2.1Euler Number and Euler Formula

Two topological properties that are useful for region description are the number of holes in the region and the number of connected components in the region (Gonzalez, 2002). The number of holes H and the number of connected components C in a 2-D region can be used to define the Euler number E:

$E=C-H\left(3.41\right)$

The Euler number is a topological property. The four letters shown in Figure 3.34 have Euler numbers equal to –1, 2, 1, and 0, respectively.

For an image containing Cn different connected foreground components and assuming that each foreground component Ci contains Hi holes (i. e., defines Hi extra components in the background), the Euler’s number (a more generalized version) associated with the image is calculated as

$E=C_n-{\displaystyle \sum _{i=1}^{C_n}{H}_i}\left(3.42\right)$

There are two Euler numbers for a binary image A, which are denoted E4(A) and E8(A) (Ritter, 2001). Each is distinguished by the connectivity used to determine the number of feature pixel components and the connectivity used to determine the number of non-feature pixel holes contained within the feature pixel connected components.

The 4-connected Euler number, E4(A), is defined to be the number of four-connected feature pixel components minus the number of 8-connected holes, which is given by

$E_4\left(A\right)=C_4\left(A\right)-H_8\left(A\right)\left(3.43\right)$

Here, C4(A) denotes the number of 4-connected feature components of A and H8(A) is the number of 8-connected holes within the feature components.

The 8-connected Euler number, E8(A), is defined by

$E_8\left(A\right)=C_8\left(A\right)-H_4\left(A\right)\left(3.44\right)$

where C8(A) denotes the number of 8-connected feature components of A and H4(A) is the number of 4-connected holes within the feature components.

Table 3.5 shows Euler numbers for some simple pixel configuration (Ritter, 2001).

Regions represented by straight-line segments (referred to as polygonal networks) have a particular simple interpretation in terms of the Euler number. Denoting the number of vertices by V, the number of edges by Q, and the number of faces by F, the following relationship can be derived, which is called the Euler formula,

$V-Q+F=E=C-H\left(3.45\right)$

The drawing in Figure 3.35 is an example of polygon network and has 26 vertices, 33 edges, 7 faces, 3 connected regions, and 3 holes. Therefore, its Euler number is 0.

Table 3.5: Examples of pixel configurations and Euler numbers.

3.6.2.2Euler Number in 3-D

Some terms need to be defined first (Lohmann, 1998). A cavity is a completely enclosed component of the background. A handle has sometimes been identified by the concept of a “tunnel,” which is a hole having two exits to the surface. The “number of handles” is also called the “number of tunnels,” “first Betti-Number,” or “genus.”

The genus counts the maximum number of non-separating cuts it can make through the object without producing more connected components, where a “cut” must fully penetrate the object. Figure 3.36 shows examples of such cuts. There are many numbers of separating and nonseparating cuts conceivable for this object. But once you have decided on one particular nonseparating cut, no further non-separating cuts are possible since any further cut will slice the object into two. Therefore, the genus for this object is one. An object consisting of two crossed rings has a genus of 2, because there are two nonseparating cuts possible, one for each component.

Now, the 3-D Euler number is defined as the number of connected components (C) plus the number of cavities (A) minus the genus (G):

$E=C+A-G\left(3.46\right)$

The Euler number is clearly a global feature of an object. However, it is possible to compute both the Euler number and the genus by purely local computations (i.e., by investigating small neighborhoods).

The genus of a digital object can be computed by investigating the surfaces that enclose the object and its cavities. If the object is digital, the enclosing surfaces consist of a fabric of polyhedral. Such surfaces are called netted surfaces. They are made by numbers of vertices (V), edges (Q), and faces (F) of voxels. The genus of a netted surface has the property given by

$2-2G=V-Q+F\left(3.47\right)$

In Figure 3.37, F = 32, Q = 64, and V = 32. So, 2 – 2G = 32 – 64 + 32 = 0, that is, G = 1.

Sometimes, it may happen that two closed netted surfaces meet at a single edge. Such edges are counted twice – once for each surface they belong to.

Each connected component and cavity is wrapped up in a netted surface Si. If there are M number of connected components and N number of cavities, the number of such surfaces will be M + N. Each of the closed surfaces encloses a single connected component or a single cavity. According to eq. (3.46), since Ei = 1 – Gi,

$2-2G_i-2-2\left(1-E_i\right)=2E_i\left(3.48\right)$

$2E={\displaystyle \sum _{i=1}^{M+N}2E_i}={\displaystyle \sum _{i=1}^{M+N}\left(2-2G_i\right)}={\displaystyle \sum _{i=1}^{M+N}{V}_i-}{Q}_i+F_i\left(3.49\right)$

Let S denote the image foreground, S′ denote its background, and Ek, k = 6, 26 denote the Euler number of a k-connected object, then the following two duality formulas exist

$E_6\left(S\right)=E_{26}\left(S^{\prime }\right)E_{26}\left(S\right)=E_6\left(S^{\prime }\right)\left(3.50\right)$