5 December 2017 Computation of the area in the discrete plane: Green’s theorem revisited
Author Affiliations +
Abstract
The detection of the contour of a binary object is a common problem; however, the area of a region, and its moments, can be a significant parameter. In several metrology applications, the area of planar objects must be measured. The area is obtained by counting the pixels inside the contour or using a discrete version of Green’s formula. Unfortunately, we obtain the area enclosed by the polygonal line passing through the centers of the pixels along the contour. We present a modified version of Green’s theorem in the discrete plane, which allows for the computation of the exact area of a two-dimensional region in the class of polyominoes. Penalties are introduced and associated with each successive pair of Freeman displacements along the contour in an eight-connectivity system. The proposed equation is shown to be true and properties of the equation related to the topology of the regions are presented. The proposed approach is adapted for faster computation than the combinatorial approach proposed in the literature.
Chalifour, Nouboud, and Voisin: Computation of the area in the discrete plane: Green’s theorem revisited

1.

Introduction

Let us consider Ω to be a binary four-connected region with or without holes. We suppose that Ω is filled with white pixels and surrounded by black pixels. This class of regions is the well-known polyominoes.1 For such a region Ω, we propose an algorithm to identify its eight-connected, closed, and positively oriented contour Γ (black pixels). Second, we propose an exact equation to compute the area of Ω from the coordinates of the pixels in Γ. A simple way to obtain the area of such a region is to scan the region and to count the interior pixels inside the contour Γ. Otherwise, a corollary of Green’s theorem in the continuous plane2 states that if Ω is a closed and bounded region, surrounded by a simple closed path Γ, which is positively oriented and piecewise continuous, then the area A(Ω) of Ω is given by the following line integral:

(1)

A(Ω)=Ω1dxdy=12Γ(xdyydx).
The area of a discrete region is often computed from a discrete version of the last Eq. (1). This discrete equation is the well-known Pick’s theorem.3 The contour Γ will be an ordered set of pixels
Γ={P1,P2,,Pi,Pi+1,,PL,PL+1=P1},
where Pi=(xi,yi) are the coordinates associated with the center of the pixel Pi,i=1,,L+1. The integer L represents the number of pixels in Γ. The discrete version of Eq. (1) is given by the equation

(2)

A(Ω)=12i=1L[xi(yi+1yi)yi(xi+1xi)]=12i=1L[xiyi+1yixi+1].

Unfortunately, the area obtained with this equation corresponds to the one enclosed by the polygonal line passing through the center of each pixel along the contour. Consequently, the area is greater than the number of white pixels. For example, the unitary region shown in Fig. 1 has an area equal to two pixels when using Eq. (2). The area is overestimated because of the contribution of the pixels on the contour at the left of the straight line passing through the center of each pixel in the contour. To correct Eq. (2) in its discrete formulation, we introduce a penalty associated with each Freeman displacement from one pixel to its successor along the positively oriented outer contour Γ. The sum of these penalties will correspond to the difference between the real area and the estimate given by Eq. (2). Before introducing the contour algorithm and penalties, we will provide some definitions to specify the topology of the domains covered by our approach. Many authors have treated this topic in the context of digital images, in particular the research works of Rosenfeld.45.6.7.8

Fig. 1

Region with unitary surface and its contour.

JEI_26_6_063022_f001.png

Otherwise, a different version of the Green theorem9,10 based on the exterior edges of the contour’s pixels (boundary) of a polyomino is used to calculate discrete geometric parameters, such as the center of gravity and the moment of inertia of the polyomino. In these studies, the contour is the adjacent pixels of the polyomino that are four-connected, and the boundary is encoded by a four-letter alphabet. Our approach, adapted for pattern recognition aims, is different from this combinatorial approach. We will consider simply four-connected regions in the discrete plane (white pixels). Our approach is to extract simultaneously the contour (eight-connected black pixels) and the ordered list of Freman’s directions between each pair of successive pixels. These two topics are related in the calculation of the area. In Sec. 2, we describe the structures of a class of regions of interest, in Sec. 3 we present the construction of the oriented contour of such regions, and finally we present the equation for the computation of the area in Sec. 4 before the conclusion.

2.

Definitions

Let Ω be a four-connected region in the discrete plane. If the number of pixels in Ω is finite, then Ω is called a closed and bounded region; otherwise it is open on the world. The set Ωc is the complementary set in the discrete plane or in the image.

Definition 1

Let Ω be a four-connected, closed, and bounded set of pixels (white pixels) in the discrete plane; therefore, the contour Ω of Ω is the set of pixels (black pixels) in Ωc such that each pixel of Ω is adjacent (four-connectedness) to at least one pixel of Ω.

We recall that four-connectedness means edge connectivity; therefore, two pixels are four-connected if and only if they have a common edge. In this paper, we consider only simply connected regions. Otherwise, if a region contains holes, we can easily subtract the area of the holes from the region containing these holes.

Definition 2

The oriented contour Γ of Ω, or the contour, is an ordered rearrangement of the pixels in Ω such that Γ is a closed, eight-connected, and positively oriented (counterclockwise) path. We represent the contour by an ordered set of pixels

(3)

Γ={P1,P2,,Pi,Pi+1,,PL,PL+1=P1},
where P1 is any pixel in Γ.

Because of the orientation of the contour, the region Ω is at the left side of the oriented segment defined by any pair of successive pixels [Pi,Pi+1] along the contour. The choice of the counterclockwise orientation is in accordance with the Green’s theorem in vector calculus to ensure that the area is positive.

Definition 3

The oriented contour is said to be simple if PiPj, 1ijL.

The length L of an eight-connected contour is minimal when the contour is simple. Now, we consider topological structures to deal with regions having nonsimple contours as well and to extend the calculation of the area for a class of regions as large as possible. For this purpose, we introduce the definitions of a stem, branch, tree, and leaf connected to a stem. Subsequently, we will consider the juxtaposition of all these structures.

Definition 4

A stem in a contour Γ is a subset SΓ such that there exist two integers 1iL and k>0 such that

(4)

S={Pi,Pi+1,Pi+2,,Pi+k1,Pi+k,Pi+k+1,,Pi+2k1,Pi+2k},
where Pi+2kj=Pi+j,1jk, Pi+jPi+m,1jmk, and Pi=Pi+2k. The pixel Pi is called the root of the stem, and the pixel Pi+k is called the extremity of the stem.

A stem is like a single filament growing inside the region Ω [see Fig. 2(b)]. We now describe a branch in a contour as the union of many stems. One of these stems is identified as the principal stem on which all others stems are connected [see Fig. 2(d)]. All of these stems are disjoint, but many of these can have a common root on S0. A branch is well-defined in graph theory as a simple connected graph without any simple cycle. Here, the vertices in the graph are the pixels, and the edges are represented by the displacements.

Fig. 2

(a) Starting pixel, (b) stem, (c) root of a stem, (d) branch, (e) tree, (f) opened leaf at the extremity of a stem, and (g) branch with a closed leaf and two stems connected to the leaf.

JEI_26_6_063022_f002.png

Fig. 3

(a) Admissible pair of displacements, (b) nonadmissible pair of displacements (an eight-connectedness fails), and (c) admissible pair of displacements with backtracking successive displacements on a stem.

JEI_26_6_063022_f003.png

Definition 5

Let S0 be a fixed single stem in Γ with root R0Γ. Let Sj,j=1,,N, be N disjoint stems in Γ connected to S0 by a root RjS0. The union of the stems {Sj}j=0n is called a branch. The pixel R0 is called the root of the branch, and S0 is called the principal stem of the branch.

The choice of the principal stem is arbitrary. For instance, we can choose the longest as the principal stem. We define the union of branches as a tree.

Definition 6

Let T0 be a fixed stem in Γ with root R0Γ and let Bj,j=1,,N, be N disjoint branches in Γ with RjT0 the root of the branch Bj, then the union of all branches is called a tree. The stem T0 is called the trunk of the tree. The root R0 is called the root of the tree.

In the last definition, branches can have a common root. We add a last structure that can be included first at the end of a stem.

Definition 7

A leaf F in Ω is a set of pixels connected to the extremity of a stem in Γ. The set of the pixels of a leaf, including its contour, is a simply four-connected region. The contour Fc of a leaf is included in Γ.

A leaf is closed if its contour surrounds only black pixels; otherwise, it is open [see Fig. 2(f)]. The class C regions considered in this paper are those with stems, branches, trees, leaves, and all admissible combinations of these structures, and they are simply connected.

Definition 8

The principal contour of a region ΩC is the set of pixels in Γ that remains after the elimination of all stems, branches, trees, and leaf contours.

Proposition 1

Let Ω be a nonempty, bounded, and four-connected region; then Ω has a finite and closed four-connected outer contour Ω and a contour Γ.

Proof.

The outer contour Ω of Ω is the set of all pixels in Ωc adjacent by the edges to the pixels in Ω. Since Ω is bounded, Ω contains a finite number of pixels and consequently Ω is finite. If the contour Ω is not closed, then Ω is not bounded and we have a contradiction. We conclude that Γ exists as a rearrangement of Ω.   ∎

The extraction of the closed, eight-connected, and positively oriented contour Γ from the outer contour Ω of a four-connected region Ω and the associated sequence of successive and admissible displacements are presented below.

3.

Construction of the Oriented Contour

Now, we are ready to propose a new contour algorithm enabling us to construct the contour Γ (eight-connected, closed, and positively oriented) of a region ΩC. The algorithm presented in this section was introduced in Ref. 11 for the detection of the contour of “hydropsyche” nets in an environmental application in connection with toxicological studies. The algorithm contains three major steps: the identification of a starting pixel on the contour, the step-by-step construction of successive eight-connected pixels on the contour (see Fig. 3), and the ending of the process when connecting with the starting pixel. We first identify a set of potential starting pixels along the contour of Ω. In practice, we need one starting pixel for each connected component. The Freeman directions will be used as identifiers of the displacements along the contour. The Freeman codification is the standard one in an eight-connected topology; the value is 0 in the right direction and is increasing in a counterclockwise manner. A displacement is an oriented segment (counterclockwise) between two successive pixels along the contour. We will denote [Pa,Pb] an oriented segment, or vector, from the center of the pixel Pa to the center of the pixel Pb.

Definition 9

A black pixel Ps=(i,j) is called a potential starting pixel of a contour if the adjacent pixel with coordinates Pr=(i1,j+1) is black and if the pixel with coordinates Pt=(i,j+1) is white. The Freeman direction associated with the displacement from Ps to Pr is α=5. We denote S(Ω) the set of all potential starting pixels.

Proposition 2

Let ΩC and its contour Γ. There exist P1 and P2 in Γ such that the Freeman direction of the oriented segment [P1,P2] equals α=5 and such that P1S(Ω) has a unique pixel PLΓ as predecessor.

Proof.

Let Ps=(k,j) be the pixel with coordinates

j=minm{P=(i,m)Ω}k=minn{P=(n,j)Ω}.
Since Ω is bounded, then Ps exists. By the definition of Ps, we have P1=(k1,j) and P2=(k,j1) in Γ are the two successive candidate pixels with the Freeman direction equal to α=5. It is easy to show, or to illustrate, that the predecessor PL of P1 belongs to the exclusive set of coordinates {(k1,j+1),(k2,j),(k2,j+1),(k,j+1)}; otherwise, we have a contradiction because of the definition of Ps.   ∎

The last proposition confirms that we can start the detection of the contour with the specific starting pixel selected. Many other starting pixels are admissible. In the case of a region with many connected components, we switch off any pixel in S(Ω) encountered during the construction of a contour with the intent of individually constructing the contour of each component. When the set S(Ω) becomes empty, no component remains. Finally, when we reach the predecessor PL, the construction of the contour is stopped. Let P1 and P2 be the starting and second pixels identified previously, respectively, and let k=1.

At each step k1, we have to identify the pixel Pk+2 such that the oriented segment dk+1=[Pk+1,Pk+2] satisfies the two following conditions: (1) Pk+2 is a black pixel and (2) {P1,P2,,Pk,Pk+1,Pk+2} is the minimal eight-connected and counterclockwise-oriented chain of pixels on Γ, which minimizes the length (number of pixels) of all chains of black pixels belonging to Ω and linking P1 to Pk+2. Let dk=[Pk,Pk+1] the oriented segment on the contour issued from the step k1. Let αk be the Freeman direction associated with this displacement. We will prove that there exists one and only one pixel Pk+2 such that the preceding conditions are verified. The black pixel Pk+2Γ is chosen according to the knowledge of the direction αk between the preceding pixels. The choice of the pixel Pk+2 must respect the last two constraints. The enumeration of the potential patterns of distribution of white and black pixels in the neighborhood of Pk and Pk+1 will allow us to identify this unique pixel on an eight-connected contour. To select the pixel Pk+2, we covered all of the possible patterns (see Table 1) in the neighborhood of the pixels Pk and Pk+1 that respect the attributes of the contour. In Table 1, a value at the position (i,j) indicates that a displacement in the Freeman direction αk+1=j is admissible after a displacement in the direction αk=i along the contour. The meaning of the value in position (i,j) will be specified further on. For a given i=αk, there exists only one j=αk+1 that corresponds to a displacement along the contour such that the constraints are verified, then we can determine the unique Pk+2. In Fig. 4, we show in a minimal geometric representation all successive and admissible displacements. The other data associated with these representations will serve to explain penalties associated with these displacements.

Table 1

Penalty p(i,j) for each pair of successive and admissible displacements (i,j).

i/j01234567
00.50.251.00.750.750.5
10.750.50.50.251.01.00.75
20.750.50.50.251.00.75
31.00.750.750.50.50.251.0
41.00.750.750.50.50.25
51.01.00.750.750.50.50.25
61.00.750.750.50.50.25
70.50.251.01.00.750.750.5

Fig. 4

Successive and admissible pairs of displacements.

JEI_26_6_063022_f004.png

Given the pixels Pk and Pk+1 and displacement αk, we see from Table 1 that there are no more than seven directions to visit before choosing the next pixel Pk+2 and the direction αk+1, which is unique along the contour. Furthermore, we note that some opposite Freeman directions are admissible to take into account reverse displacements along the stems. Finally, since the starting pixel has a unique predecessor as shown in Proposition 2, the algorithm stops when we reach the first pixel P1. The next theorem summarizes the situation discussed above.

Theorem 1

Let ΩC be a nonempty region and let P1 and P2 be the two pixels found at the first step of the algorithm. Then,

  • 1. there exists a unique pixel P3Γ such that the sequence of pixels {P1,P2,P3} is positively oriented and α2 is equal to 6 or 7,

  • 2. for k>1, if Pk and Pk+1 are the two successive pixels in Γ, then there exists a unique pixel Pk+2Γ such that {Pk,Pk+1,Pk+3} is a positively oriented path in Γ.

Proof.

If α2 equals values other than 6 or 7, we have a contradiction in regard to the position of the pixel Ps, as defined in the proof of Proposition 2. The second part is a consequence of the proposed construction for Γ.   ∎

To prove the correctness of the proposed contour algorithm, some intermediary results are necessary. First, we show that the algorithm is finite. For this purpose, it is sufficient to show that a pixel on the contour is revisited at most a finite number of times. We will focus our argument on the geometry of stems and branches in the discrete plane.

Lemma 1

The extremity of a stem is at most the root of three other stems.

Proof.

The proof is based on geometric arguments. Figure 5 shows all geometric patterns combining a root of a stem connected to its predecessor in Γ. For each one of these patterns, we connected the maximum number of independent stems to the extremity of the main stem. Figure 6 shows all combinations (classes of equivalence under orthogonal rotations) when connecting stems to an extremity. We observe that only two or three stems can be connected.   ∎

Before moving on to the correctness of the algorithm, we present the next lemma.

Fig. 5

The set of patterns representing the extremity of a stem and its predecessor on a contour Γ. A black circle represents the extremity of a stem.

JEI_26_6_063022_f005.png

Fig. 6

Equivalent classes of patterns representing stems connected to the extremity of a stem (black circle). The pixel (k) is the predecessor of the extremity.

JEI_26_6_063022_f006.png

Fig. 7

The surface penalty p(0,1).

JEI_26_6_063022_f007.png

Lemma 2

If PkΓ is revisited at a step j>k (Pj=Pk), then αjαk.

Proof.

The only pixels revisited on Γ are pixels belonging to a stem and consequently to a branch or a tree. Let Pk be such a pixel. If Pk is not a root, then Pj+1=Pk1Pk+1 and then αkαj. If Pk is a root, then it is clearly visited at most a finite number of times.   ∎

We conclude that Pk is revisited at most a finite number of times. In conclusion, we have proved that the algorithm can be initialized and the contour is well-defined at each step. Also, we have proved that each pixel is visited at most a finite number of times along Γ and then the procedure is finite in time. Furthermore, the procedure is closed since the starting pixel is reached again because it has a unique predecessor. Finally, the proposed algorithm is correct.

4.

Green’s Formula for the Computation of the Area

In this section, we develop a new expression of the discrete Green’s identity for the computation of the area of a region ΩC. Let Γα={α1,α2,,αk,,αL} be the ordered chain of Freeman directions associated with the chain of oriented segments dk=[Pk,Pk+1] (k1) along the contour. Our objective is to remove systematically, for each pair of successive displacements [αk,αk+1](1kL), the additional surface area introduced when using Pick’s formula. For this purpose, we define for each successive displacement a penalty pk=p(αk,αk+1), and this value is subtracted from the corresponding term in the original Eq. (2) as we will see later. The penalty pk is calculated according to the next definition.

Definition 10

For k1, let Pk, Pk+1, and Pk+2 be three successive pixels in Γ and let αk and αk+1 be the Freeman directions associated with the oriented segments dk=[Pk,Pk+1] and dk+1=[Pk+1,Pk+2]. Let Pk+1* and Pk+2* be the two orthogonal projections of Pk+1 and Pk+2 on the adjacent edges in the direction of Ω, respectively, such that the angle between the oriented segments dk and [Pk+1,Pk+1*] (resp., [Pk+2,Pk+2*]) is acute. The penalty pk is the surface of the polygon with vertices {Pk+1*,Pk+1,Pk+2,Pk+2*} inside Pk+1Pk+2.

In Fig. 7, we illustrate the calculation of the penalty p(0,1) for the particular successive pair of displacements αk=0 and αk+1=1. Table 1 shows the values of these penalties calculated for all admissible and successive pairs of displacements. In Fig. 4, we can see the penalized area for each admissible pair of admissible displacement.

Before demonstrating the correctness of the modified Green’s formula (see Proposition 4), we prove the invariance under rotations of the penalty values.

Lemma 3

The penalty associated with a pair of admissible displacements along Γ is invariant under rotations.

Proof.

Let (i,j) be the indices of two successive and admissible displacements (0i,j7), then the rotation of (i,j) gives the pair (i,j) where i=(i+2)mod8 and j=(j+2)mod8. From Table 1, we verify that p(i,j)=p(i,j) for all pairs of displacements. We conclude that penalties are invariant under rotations.   ∎

At this time, we are able to propose a modified Green’s formula. First, we prove that the proposed equation computes the right area of a region with a simple contour without the presence of stems, branches, trees, and leaves. We will denote C0 such a region, and its contour will be called a simple contour.

Theorem 2

Let ΩC0 be a region and Γ its contour given by the sequence of pixels

[P1,P2,,Pk1,Pk,,PL,PL+1=P1],
where PiPj for 1ijL. The area of Ω is given by the following equation:

(5)

A(Ω)=12k=1L[xkyk+1ykxk+1]k=1Lp(αk,αk+1),
where p(αk,αk+1) is the penalty associated with two successive and admissible displacements dk=[Pk,Pk+1] and dk+1=[Pk+1,Pk+2] with Freeman directions αk and αk+1.

Proof.

We proceed by induction on the size n1 of the area of Ω. The only region with an area equal to 1 was shown in Fig. 1. If we suppose that the white pixel of this domain has coordinates (i,j), then its contour is given by the sequence of pixels {P1,P2,P3,P4,P5=P1} where P1=(i1,j),P2=(i,j1),P3=(i+1,j), and P4=(i,j+1). The Freeman directions associated with this contour are given by the sequence {5, 7, 1, 3}. If we calculate the area using the discrete Eq. (5), then

A=12k=14[xkyk+1ykxk+1]k=1Lp(αk,αk+1),=12[(i1)(j1)ij+ij(ji)(i+1)+(i+1)(j+1)ij+ij(j+1)(i1)][p(5,7)+p(7,1)+p(1,3)+p(3,5)]=12[4]1=1.
Let Ω*C0 be a region with an area equal to n+1 and Γ* its contour. Let us suppose that Eq. (5) is exact for all regions Ω with an area equal to n1 (mathematical induction on the integer n). The basic idea of the proof consists of eliminating PeΩ*, a pixel adjacent to the contour, and then applying the assumption to the resulting region Ω=Ω*{Pe}. We denote Γ the contour of Ω. If we remove such a pixel in Ω*, the contour Γ* is modified to become Γ. The resulting deformation of Γ* depends on the position of Pe along the contour. As shown in Fig. 8, if we switch off Pe=(i,j) from Ω*, then we obtain a local reconstruction of the contour passing through the pixel Pe

Unfortunately, to establish the proof we have to forecast all possible deformations of Γ* when eliminating a pixel PeΩ* adjacent to Γ*. In Fig. 9, we illustrate all patterns of deformations of Γ* obtained when eliminating a pixel Pe in Ω* with the constraint that the region must remain connected. We assert that any region Ω*C0 respects at least one of these patterns along its boundary following such an elimination. These equivalence classes of deformations of Γ* (patterns) are constructed taking into account orthogonal rotations and vertical and horizontal flips and were established by enumeration. The reorganization of the contour Γ* is represented by a dotted line passing through the pixel Pe. For each deformation, we first apply Eq. (5) to the contour Γ of the region Ω with an area equal to n, and subsequently we add the area eliminated following the reorganization of the original contour Γ*.

Fig. 8

Rearrangement of the contour.

JEI_26_6_063022_f008.png

Fig. 9

Patterns of a local rearrangement along a contour.

JEI_26_6_063022_f009.png

By a reorganization of the resulting algebraic expression, we obtain Eq. (5) for the region Ω* with an area equal to n+1. We will show this result only for the pattern shown in Fig. 8; the proof is similar for the other patterns (Fig. 9).

Let us consider Pe=(i,j) as the pixel removed from Ω*, and let us denote

Γ*=[P1,,PJ1,PJ,PJ+1,PJ+2,PJ+3,PJ+4,,PL,PL+1=P1].

If we remove Pe and if we apply the modified Green’s formula to the region Ω, then using the induction assumption and rewriting the terms involved in the deformation of the contour, we obtain the area of Ω

A(Ω)=n=12k=1J1[xkyk+1ykxk+1]+12[(i1)j(j1)i]+12[i(j+1)j(i1)]+12k=J+3L[xkyk+1ykxk+1]k=1J2p(αk,αk+1)p(6,7)p(7,1)p(1,1)k=J+4Lp(αk,αk+1),=12k=1J1[xkyk+1ykxk+1]+12k=J+4L[xkyk+1ykxk+1]k=1J2p(αk,αk+1)k=J+4Lp(αk,αk+1)+i1.

From the last equation, we have

n+1=12k=1J1[xkyk+1ykxk+1]+12k=J+4L[xkyk+1ykxk+1]k=1J2p(αk,αk+1)k=J+4Lp(αk,αk+1)+i.

Otherwise, if we apply Eq. (5) to Γ* and if we apply the last expression, we obtain the desired result

A(Ω*)=12k=1L[xkyk+1ykxk+1]k=1Lp(αk,αk+1),=12k=1J1[xkyk+1ykxk+1]+12k=J+4L[xkyk+1ykxk+1]+12[(i1)(j1)(j1)i+ij(j1)(i+1)+(i+1)(j+1)ji+i(j+1)(j+1)(i1)]k=1J2p(αk,αk+1)k=J+4Lp(αk,αk+1)p(6,6)p(6,7)p(7,1)p(1,2)+p(2,2),=12k=1J1[xkyk+1ykxk+1]+12k=J+4L[xkyk+1ykxk+1]k=1J2p(αk,αk+1)k=J+4Lp(αk,αk+1)+i=n+1.

In the last theorem, we supposed that the contour was simple. In this specific case, the enumeration of all classes of rearrangement of the contour allows us to bypass the combinatorial and the geometric complexity. To complete the demonstration, we will show the effect of a single stem in the computation of the area before extending the last theorem to a general region with multiple stems, branches, trees, and leaves.

Lemma 4

Let S0 be a stem given by the sequence of pixels

S0={P0,P1,,Pt1,Pt,Pt+1,,P2  t1,P2  t}
where P2t=P0 is the root of the stem. If Pj=(xj,xj+1), then the following identities are verified:

(6)

12j=02  t1[xjyj+1yjxj+1]=0,

(7)

j=02t1p(αj,αj+1)=t,

(8)

12j=02t1[xjyj+1yjxj+1]j=02t1p(αj,αj+1)=t,
where the constant t represents the number of pixels in the stem.

Proof

From the definition of a stem, we have

(9)

P2tj=Pj,j=0,,t1.

Since each pixel is visited twice in two opposite directions along the stem, the ordered list of Freeman directions along the stem can be rewritten as follows:

(10)

{α0,α1,,αt1,αt,αt+1,,α2  t1},
and these directions verify the next identity

(11)

αt+j=αtj1T,j=0,,(t1),
where αtj1T is the inverse direction of αtj1. With this notation, we can rewrite the equation at the left of Eq. (6)
12j=02t1[xjyj+1yjxj+1]=12j=0t1[xjyj+1yjxj+1]+12j=t2t1[xjyj+1yjxj+1]=12j=0t1[xjyj+1yjxj+1]12j=0t1[x2tjy2  t(j+1)y2  tjx2  t(j+1)].

Using the relation Eq. (9), the last summation verifies

12j=02t1[xjyj+1yjxj+1]=12j=0t1[xjyj+1yjxj+1]12j=0t1[xjyj+1yjxj+1]=0.

In conclusion, the first Eq. (6) is proved. Again, let us consider the Freeman directions along the stem

{[α0,α1],[α1,α2],,[αt2,αt1],[αt1,αt],[αt,αt+1],[αt+1,αt+2],,[α2  t2,α2  t1]}.

We observe from Table 1 that these penalties verify that

p(αt1j,αj)+p(αt1j,αt+j)=1,j=1,,(t1).

For the two particular displacements at the end of the stem, given by the segments at1=[Pt1,Pt] and at=[Pt,Pt+1], we have p(αt1,αt)=1. From these two last relations, we obtain the following identity:

j=02t1p(αj,αj+1)=j=0t2p(αj,αj+1)+p(αt1,αt)+j=t2t1p(αj,αj+1)=j=1t1{p(αt1i,αi)+p(αt1i,αt+i)}+p(αt1,αt)=j=1t11+p(αt1,αt)=(t1)+1=t.

The relation Eq. (7) is then verified. Finally, if we combine Eqs. (6) and (7), the last identity Eq. (8) is therefore proved.   ∎

From the last lemma, we conclude that the contribution of the pixels of a stem in the algebraic expression of the modified Green’s formula equals the number of pixels on the stem with a negative sign. Here is the following theorem.

Theorem 3

Let Ω be a region having a single stem, then the modified Green’s formula [Eq. (5)] applied to the contour gives the exact area of Ω.

Proof

Let us suppose that Ω has an area equal to n1 and let Γ be its contour. If Ω has only one stem, then the contour is given by the sequence

Γ={P1,P2,,Pi=P0s,P1s,,Pts,Pt+1s,,P2  t1s,P2  ts=Pi,Pi+2  t+1,,PL,PL+1=P1},
where P1 is the starting pixel. In this sequence, the stem is represented by the following subsequence of pixels:
Γa={Pi=P0s,P1s=Pi+1,,Pts=Pi+t,Pt+1s=Pi+t+1,,P2  t1s=Pi+2  t1,P2  ts=Pi+2  t.=Pi}.

The pixel Pi=P0s=P2ts is the root of the stem. Let Γp be the principal contour of Ω, which is defined by the subsequence of pixels

Γp={P1,P2,,Pi,Pi+2  t1,,PL,PL+1=P1}.
Let Ω* be the region surrounded by the principal contour Γp. If we apply the modified Green’s formula [Eq. (5)] to the region Ω, then we have the following algebraic decomposition based on the coordinates of the pixels in the contour Γ:
A(Ω)=12k=1L[xkyk+1ykxk+1]k=1Lp(αk,αk+1)=12k=1i1[xkyk+1ykxk+1]k=1i1p(αk,αk+1)+12k=ii+2t[xkyk+1ykxk+1]k=ii+2tp(αk,αk+1)+12k=i+2tL[xkyk+1ykxk+1]k=iLp(αk,αk+1).

In the last summation, we identify three terms

S1=12k=1i1[xkyk+1ykxk+1]k=1i1p(αk,αk+1),S2=12k=ii+2t[xkyk+1ykxk+1]k=ii+2tp(αk,αk+1),S3=12k=i+2tL[xkyk+1ykxk+1]k=iLp(αk,αk+1).
The sum S=S1+S3 corresponds to the area of the region Ω* surrounded by Γp; then we have S=n+t. Here, t is the number of distinct pixels on the stem. In addition, by Lemma 4, we see that S2=t. In conclusion, A(Ω)=S1+S2+S3=S+S2=n+tt=n.   ∎

It is possible to generalize the last proposition to regions with a branch in Ω.

Proposition 3

Let Ω be a region with a branch connected to the principal contour Γp. Let Γ be the contour of Ω

Γ={P1,,Pi,Pi+1,,P0b,P1b,,Pjb,,P2Nb=P0b,,PM=P1}.

Let B1 be the branch defined by the subsequence of pixels B1={P0b,P1b,,Pjb,,P2  Nb}. The pixel P0b=P2Nb is the root of the main stem on the branch, which is connected to Γp. Let us denote Pjb=(xjb,yjb) the coordinates of the j’th pixel in B1 and αjb be the Freeman direction associated with the oriented segment [Pjb,Pj+1b] for j=0,,2  N1. Thus, we have

(12)

12j=02N1[xjbyj+1byjbxj+1b]+12N1p(αjb,αj+1b)=N.

Proof.

We can split the expression [Eq. (12)] in such a way that we obtain a summation restricted to the pixels of the main stem and other individual summation for each secondary stem. Then, applying Lemma 4 at each summation we obtain the total number of pixels in B1 with a negative sign. The root P0a is not counted.   ∎

The proof of the Proposition 3 can be easily extended to regions with multiple branches and trees. To conclude this section, we extend the previous results to regions with leaves.

Proposition 4

Let a region ΩC and Γ its contour; suppose that Γ has only one leaf connected to the end of a stem S0 in Ω, then the area of Ω is given by the modified Green’s formula [Eq. (5)].

Proof.

The leaf can be closed or open. If the leaf is open, the interior of its leaf contour does not contain a subset of Ω. Let us consider the partition of the pixels in Γ

  • Γp: the set of all pixels in the principal contour of Ω,

  • Γa: the set of internal pixels in S0, and

  • Γb: the set of pixels in the leaf contour.

Since Γp is a simple contour, then by Theorem 2, the contribution of these pixels to Eq. (5) gives the area of the domain inside Γp. Otherwise, by Lemma 4, the contribution of the pixels in Γa gives, with a minus sign, the number of pixels in Γa. However, we can show that the contribution of the pixels in Γb is equal to the number of pixels in the leaf.

Let us denote {P1b,P2b,,PJb,PJ+1b=P1b} the subsequence of pixels defining the leaf contour, where Pjb=(xjb,yjb),j=1,,J are the coordinates of such a pixel and αjb is the Freeman direction of the segment [Pjb,Pj+1b]. Let us consider the two sums

(13)

S1b=12j=1J[xjbyj+1byjbxj+1b],S2b=j=1Jp(αjb,αj+1b).
The first sum S1b gives the area inside the polygonal line passing through the center of each pixel on the leaf contour with a negative sign since the path is clockwise. For instance, the sum S2b gives the black area outside the leaf contour, but within the leaf, with a negative sign. If we combine these two results, the modified Green’s formula will give the area inside the principal contour minus the length of the stem and the area occupied by the leaf.   ∎

The same result is valid for a region with a stem, branch, tree, or leaf. If we combine all of the arguments used in these proofs, then we conclude that the proposed equation is valid for all regions with any combination of these attributes. If we apply the original Eq. (2) and the modified or penalized Green’s formula to the region shown in Fig. 10, we obtain an area of 798 and 415 pixels (exact area). This numerical result confirms the importance of having a precise evaluation of the area.

Fig. 10

Region with multiple stems.

JEI_26_6_063022_f010.png

5.

Conclusion

We proposed and demonstrated a new algebraic expression of a fundamental corollary derived from Green’s formula applied to the computation of the area of a four-connected binary region. For this purpose, we introduced penalties associated with pairs of successive displacements along an eight-connected positively oriented contour. The correctness of the equation was formally proved for a general class of binary connected regions in the discrete plane. The modified Green’s formula was derived from geometric observations, but further research work will eventually establish the proposed approach as a consequence of a discrete vector calculus theory. We are extending these results (unpublished as of yet) to triangular and hexagonal mesh.

References

1. D. H. Redelmeier, “Counting polyominoes: yet another attack,” Discrete Math. 36, 191–203 (1981).DSMHA40012-365X http://dx.doi.org/10.1016/0012-365X(81)90237-5 Google Scholar

2. J. E Marsden and A. J. Tromba, Vector Calculus, 3rd ed., W.H. Freeman and Company, New York (1988). Google Scholar

3. J. M. Chassery and A. Montanvert, Géométrie Discrète en Analyse d’Images, Hermès, Paris (1991). Google Scholar

4. A. Rosenfeld, “Connectivity in digital pictures,” J. ACM 17(1), 146–160 (1970).JACOAH0004-5411 http://dx.doi.org/10.1145/321556.321570 Google Scholar

5. A. Rosenfeld, “Adjacency in digital pictures,” Inf. Control 26, 24–33 (1974).IFCNA40019-9958 http://dx.doi.org/10.1016/S0019-9958(74)90696-2 Google Scholar

6. A. Rosenfeld and R. A. Melter, Digital Geometry, Vol. 11, pp. 69–72, Springer-Verlag, New York (1989). Google Scholar

7. A. Rosenfeld and T. Y. Kong, “Connectedness of a set, its complement, and their common boundary,” Contemp. Math. 119, 125–128 (1991).CTMAEH1098-3627 http://dx.doi.org/10.1090/conm/119 Google Scholar

8. T. Yung Kong and A. Rosenfeld, Topological Algorithms for Digital Image Processing, Elsevier, North Holland (1996). Google Scholar

9. S. Brlek, G. Labelle and A. Lacasse, “Algorithms for polyominoes based on the discrete Green theorem,” Discrete Appl. Math. 147, 187–205 (2005).DAMADU0166-218X http://dx.doi.org/10.1016/j.dam.2004.09.011 Google Scholar

10. S. Brlek, G. Labelle and A. Lacasse, ““The discrete Green theorem and some applications in discrete geometry,” Theor. Comput. Sci. 346, 200–225 (2005).TCSCDI0304-3975 http://dx.doi.org/10.1016/j.tcs.2005.08.019 Google Scholar

11. A. Chalifour et al., “Analyse morphologique des filets de tricoptères: un problème d’écotoxicologie et de géométrie discrète,” in Proc. of the 11th Conf. on Vision Interface, Vancouver, British Columbia, Canada, pp. 479–486 (1998). Google Scholar

Biography

Alain Chalifour received his PhD in 1993 from the University of Montréal, Canada. The subject of his doctorate was the optimization of insecticide treatments in rivers using partial differential equations and finite-element methods. Since 1991, he has been a professor at the University of Québec at Trois-Rivières, Canada. His research interests include numerical analysis and optimization and computer vision applied to environmental applications.

Fathallah Nouboud received his BSc degree in mathematics and physics from the University of Marrakech, Morocco, his master’s degree in mathematics, and his PhD in computer science both from the University of Caen, France, in 1983, 1984, and 1988, respectively. His doctorate consisted of the design of a handwritten signature verification system. In 1989, he joined École Polytechnique Montréal as a researcher. In 1992, he became a professor at the University of Trois-Rivières, Canada. His research interests include computer vision and environmental applications.

Yvon Voisin received his PhD in 1993 from the University of Franche-Conté, France. Since 2005, he has been a full professor at the University of Burgundy, France. He is also a member of the Image Processing Group of the Laboratory Le2i (Laboratoire d’Electronique, Informatique et Image). His interests are the application of artificial vision, 3-D reconstruction, and motion analysis. He is also working on the application of artificial vision in biology and ecology.

© The Authors. Published by SPIE under a Creative Commons Attribution 3.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.
Alain Chalifour, Fathallah Nouboud, Yvon Voisin, "Computation of the area in the discrete plane: Green’s theorem revisited," Journal of Electronic Imaging 26(6), 063022 (5 December 2017). https://doi.org/10.1117/1.JEI.26.6.063022 Submission: Received 14 March 2017; Accepted 10 November 2017
Submission: Received 14 March 2017; Accepted 10 November 2017
JOURNAL ARTICLE
11 PAGES


SHARE
RELATED CONTENT


Back to Top