5 December 2017 Computation of the area in the discrete plane: Green’s theorem revisited
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

Introduction

Let us consider $\mathrm{\Omega }$ to be a binary four-connected region with or without holes. We suppose that $\mathrm{\Omega }$ is filled with white pixels and surrounded by black pixels. This class of regions is the well-known polyominoes.1 For such a region $\mathrm{\Omega }$, we propose an algorithm to identify its eight-connected, closed, and positively oriented contour $\mathrm{\Gamma }$ (black pixels). Second, we propose an exact equation to compute the area of $\mathrm{\Omega }$ from the coordinates of the pixels in $\mathrm{\Gamma }$. 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 $\mathrm{\Gamma }$. Otherwise, a corollary of Green’s theorem in the continuous plane2 states that if $\mathrm{\Omega }$ is a closed and bounded region, surrounded by a simple closed path $\mathrm{\Gamma }$, which is positively oriented and piecewise continuous, then the area $A\left(\mathrm{\Omega }\right)$ of $\mathrm{\Omega }$ is given by the following line integral:

(1)

$A\left(\mathrm{\Omega }\right)={\iint }_{\mathrm{\Omega }}1\text{\hspace{0.17em}}\mathrm{d}x\mathrm{d}y=\frac{1}{2}{\oint }_{\mathrm{\Gamma }}\left(x\text{\hspace{0.17em}}\mathrm{d}y-y\text{\hspace{0.17em}}\mathrm{d}x\right).$
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 $\mathrm{\Gamma }$ will be an ordered set of pixels
$\mathrm{\Gamma }=\left\{{P}_{1},{P}_{2},\dots ,{P}_{i},{P}_{i+1},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right\},$
where ${P}_{i}=\left({x}_{i},{y}_{i}\right)$ are the coordinates associated with the center of the pixel ${P}_{i},i=1,\dots ,L+1$. The integer $L$ represents the number of pixels in $\mathrm{\Gamma }$. The discrete version of Eq. (1) is given by the equation

(2)

$\mathcal{A}\left(\mathrm{\Omega }\right)=\frac{1}{2}\sum _{i=1}^{L}\left[{x}_{i}\left({y}_{i+1}-{y}_{i}\right)-{y}_{i}\left({x}_{i+1}-{x}_{i}\right)\right]\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\sum _{i=1}^{L}\left[{x}_{i}{y}_{i+1}-{y}_{i}{x}_{i+1}\right].$

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 $\mathrm{\Gamma }$. 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.48

Fig. 1

Region with unitary surface and its contour.

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.

Definitions

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

Definition 1

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

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 $\mathrm{\Gamma }$ of $\mathrm{\Omega }$, or the contour, is an ordered rearrangement of the pixels in $\partial \mathrm{\Omega }$ such that $\mathrm{\Gamma }$ is a closed, eight-connected, and positively oriented (counterclockwise) path. We represent the contour by an ordered set of pixels

(3)

$\mathrm{\Gamma }=\left\{{P}_{1},{P}_{2},\dots ,{P}_{i},{P}_{i+1},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right\},$
where ${P}_{1}$ is any pixel in $\mathrm{\Gamma }$.

Because of the orientation of the contour, the region $\mathrm{\Omega }$ is at the left side of the oriented segment defined by any pair of successive pixels $\left[{P}_{i},{P}_{i+1}\right]$ 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 ${P}_{i}\ne {P}_{j}$, $1\le i\ne j\le L$.

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 $\mathrm{\Gamma }$ is a subset $S\subset \mathrm{\Gamma }$ such that there exist two integers $1\le i\le L$ and $k>0$ such that

(4)

$S=\left\{{P}_{i},{P}_{i+1},{P}_{i+2},\dots ,{P}_{i+k-1},{P}_{i+k},{P}_{i+k+1},\dots ,{P}_{i+2k-1},{P}_{i+2k}\right\},$
where ${P}_{i+2k-j}={P}_{i+j},1\le j\le k$, ${P}_{i+j}\ne {P}_{i+m},1\le j\ne m\le k$, and ${P}_{i}={P}_{i+2k}$. The pixel ${P}_{i}$ is called the root of the stem, and the pixel ${P}_{i+k}$ is called the extremity of the stem.

A stem is like a single filament growing inside the region $\mathrm{\Omega }$ [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 ${S}_{0}$. 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.

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.

Definition 5

Let ${S}_{0}$ be a fixed single stem in $\mathrm{\Gamma }$ with root ${R}_{0}\in \mathrm{\Gamma }$. Let ${S}_{j},j=1,\dots ,N$, be $N$ disjoint stems in $\mathrm{\Gamma }$ connected to ${S}_{0}$ by a root ${R}_{j}\in {S}_{0}$. The union of the stems ${\left\{{S}_{j}\right\}}_{j=0}^{n}$ is called a branch. The pixel ${R}_{0}$ is called the root of the branch, and ${S}_{0}$ 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 ${T}_{0}$ be a fixed stem in $\mathrm{\Gamma }$ with root ${R}_{0}\in \mathrm{\Gamma }$ and let ${B}_{j},j=1,\dots ,N$, be $N$ disjoint branches in $\mathrm{\Gamma }$ with ${R}_{j}\in {T}_{0}$ the root of the branch ${B}_{j}$, then the union of all branches is called a tree. The stem ${T}_{0}$ is called the trunk of the tree. The root ${R}_{0}$ 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 $\mathrm{\Omega }$ is a set of pixels connected to the extremity of a stem in $\mathrm{\Gamma }$. The set of the pixels of a leaf, including its contour, is a simply four-connected region. The contour ${F}_{c}$ of a leaf is included in $\mathrm{\Gamma }$.

A leaf is closed if its contour surrounds only black pixels; otherwise, it is open [see Fig. 2(f)]. The class $\mathcal{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 $\mathrm{\Omega }\in \mathcal{C}$ is the set of pixels in $\mathrm{\Gamma }$ that remains after the elimination of all stems, branches, trees, and leaf contours.

Proposition 1

Let $\mathrm{\Omega }$ be a nonempty, bounded, and four-connected region; then $\mathrm{\Omega }$ has a finite and closed four-connected outer contour $\partial \mathrm{\Omega }$ and a contour $\mathrm{\Gamma }$.

Proof.

The outer contour $\partial \mathrm{\Omega }$ of $\mathrm{\Omega }$ is the set of all pixels in ${\mathrm{\Omega }}^{c}$ adjacent by the edges to the pixels in $\mathrm{\Omega }$. Since $\mathrm{\Omega }$ is bounded, $\mathrm{\Omega }$ contains a finite number of pixels and consequently $\partial \mathrm{\Omega }$ is finite. If the contour $\partial \mathrm{\Omega }$ is not closed, then $\mathrm{\Omega }$ is not bounded and we have a contradiction. We conclude that $\mathrm{\Gamma }$ exists as a rearrangement of $\partial \mathrm{\Omega }$.   ∎

The extraction of the closed, eight-connected, and positively oriented contour $\mathrm{\Gamma }$ from the outer contour $\partial \mathrm{\Omega }$ of a four-connected region $\mathrm{\Omega }$ and the associated sequence of successive and admissible displacements are presented below.

Construction of the Oriented Contour

Now, we are ready to propose a new contour algorithm enabling us to construct the contour $\mathrm{\Gamma }$ (eight-connected, closed, and positively oriented) of a region $\mathrm{\Omega }\in \mathcal{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 $\mathrm{\Omega }$. 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 $\left[{P}_{a},{P}_{b}\right]$ an oriented segment, or vector, from the center of the pixel ${P}_{a}$ to the center of the pixel ${P}_{b}$.

Definition 9

A black pixel ${P}_{s}=\left(i,j\right)$ is called a potential starting pixel of a contour if the adjacent pixel with coordinates ${P}_{r}=\left(i-1,j+1\right)$ is black and if the pixel with coordinates ${P}_{t}=\left(i,j+1\right)$ is white. The Freeman direction associated with the displacement from ${P}_{s}$ to ${P}_{r}$ is $\alpha =5$. We denote $S\left(\mathrm{\Omega }\right)$ the set of all potential starting pixels.

Proposition 2

Let $\mathrm{\Omega }\in \mathcal{C}$ and its contour $\mathrm{\Gamma }$. There exist ${P}_{1}$ and ${P}_{2}$ in $\mathrm{\Gamma }$ such that the Freeman direction of the oriented segment $\left[{P}_{1},{P}_{2}\right]$ equals $\alpha =5$ and such that ${P}_{1}\in S\left(\mathrm{\Omega }\right)$ has a unique pixel ${P}_{L}\in \mathrm{\Gamma }$ as predecessor.

Proof.

Let ${P}_{s}=\left(k,j\right)$ be the pixel with coordinates

$j=\underset{m}{\mathrm{min}}\left\{P=\left(i,m\right)\in \mathrm{\Omega }\right\}\phantom{\rule[-0.0ex]{1em}{0.0ex}}k=\underset{n}{\mathrm{min}}\left\{P=\left(n,j\right)\in \mathrm{\Omega }\right\}.$
Since $\mathrm{\Omega }$ is bounded, then ${P}_{s}$ exists. By the definition of ${P}_{s}$, we have ${P}_{1}=\left(k-1,j\right)$ and ${P}_{2}=\left(k,j-1\right)$ in $\mathrm{\Gamma }$ are the two successive candidate pixels with the Freeman direction equal to $\alpha =5$. It is easy to show, or to illustrate, that the predecessor ${P}_{L}$ of ${P}_{1}$ belongs to the exclusive set of coordinates $\left\{\left(k-1,j+1\right),\left(k-2,j\right),\left(k-2,j+1\right),\left(k,j+1\right)\right\}$; otherwise, we have a contradiction because of the definition of ${P}_{s}$.   ∎

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\left(\mathrm{\Omega }\right)$ encountered during the construction of a contour with the intent of individually constructing the contour of each component. When the set $S\left(\mathrm{\Omega }\right)$ becomes empty, no component remains. Finally, when we reach the predecessor ${P}_{L}$, the construction of the contour is stopped. Let ${P}_{1}$ and ${P}_{2}$ be the starting and second pixels identified previously, respectively, and let $k=1$.

At each step $k\ge 1$, we have to identify the pixel ${P}_{k+2}$ such that the oriented segment ${d}_{k+1}=\left[{P}_{k+1},{P}_{k+2}\right]$ satisfies the two following conditions: (1) ${P}_{k+2}$ is a black pixel and (2) $\left\{{P}_{1},{P}_{2},\dots ,{P}_{k},{P}_{k+1},{P}_{k+2}\right\}$ is the minimal eight-connected and counterclockwise-oriented chain of pixels on $\mathrm{\Gamma }$, which minimizes the length (number of pixels) of all chains of black pixels belonging to $\partial \mathrm{\Omega }$ and linking ${P}_{1}$ to ${P}_{k+2}$. Let ${d}_{k}=\left[{P}_{k},{P}_{k+1}\right]$ the oriented segment on the contour issued from the step $k\ge 1$. Let ${\alpha }_{k}$ be the Freeman direction associated with this displacement. We will prove that there exists one and only one pixel ${P}_{k+2}$ such that the preceding conditions are verified. The black pixel ${P}_{k+2}\in \mathrm{\Gamma }$ is chosen according to the knowledge of the direction ${\alpha }_{k}$ between the preceding pixels. The choice of the pixel ${P}_{k+2}$ must respect the last two constraints. The enumeration of the potential patterns of distribution of white and black pixels in the neighborhood of ${P}_{k}$ and ${P}_{k+1}$ will allow us to identify this unique pixel on an eight-connected contour. To select the pixel ${P}_{k+2}$, we covered all of the possible patterns (see Table 1) in the neighborhood of the pixels ${P}_{k}$ and ${P}_{k+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 ${\alpha }_{k+1}=j$ is admissible after a displacement in the direction ${\alpha }_{k}=i$ along the contour. The meaning of the value in position ($i,j$) will be specified further on. For a given $i={\alpha }_{k}$, there exists only one $j={\alpha }_{k+1}$ that corresponds to a displacement along the contour such that the constraints are verified, then we can determine the unique ${P}_{k+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.

Given the pixels ${P}_{k}$ and ${P}_{k+1}$ and displacement ${\alpha }_{k}$, we see from Table 1 that there are no more than seven directions to visit before choosing the next pixel ${P}_{k+2}$ and the direction ${\alpha }_{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 ${P}_{1}$. The next theorem summarizes the situation discussed above.

Theorem 1

Let $\mathrm{\Omega }\in \mathcal{C}$ be a nonempty region and let ${P}_{1}$ and ${P}_{2}$ be the two pixels found at the first step of the algorithm. Then,

• 1. there exists a unique pixel ${P}_{3}\in \mathrm{\Gamma }$ such that the sequence of pixels $\left\{{P}_{1},{P}_{2},{P}_{3}\right\}$ is positively oriented and ${\alpha }_{2}$ is equal to 6 or 7,

• 2. for $k>1$, if ${P}_{k}$ and ${P}_{k+1}$ are the two successive pixels in $\mathrm{\Gamma }$, then there exists a unique pixel ${P}_{k+2}\in \mathrm{\Gamma }$ such that $\left\{{P}_{k},{P}_{k+1},{P}_{k+3}\right\}$ is a positively oriented path in $\mathrm{\Gamma }$.

Proof.

If ${\alpha }_{2}$ equals values other than 6 or 7, we have a contradiction in regard to the position of the pixel ${P}_{s}$, as defined in the proof of Proposition 2. The second part is a consequence of the proposed construction for $\mathrm{\Gamma }$.   ∎

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 $\mathrm{\Gamma }$. 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 $\mathrm{\Gamma }$. A black circle represents the extremity of a stem.

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.

Fig. 7

The surface penalty $p\left(0,1\right)$.

Lemma 2

If ${P}_{k}\in \mathrm{\Gamma }$ is revisited at a step $j>k$ (${P}_{j}={P}_{k}$), then ${\alpha }_{j}\ne {\alpha }_{k}$.

Proof.

The only pixels revisited on $\mathrm{\Gamma }$ are pixels belonging to a stem and consequently to a branch or a tree. Let ${P}_{k}$ be such a pixel. If ${P}_{k}$ is not a root, then ${P}_{j+1}={P}_{k-1}\ne {P}_{k+1}$ and then ${\alpha }_{k}\ne {\alpha }_{j}$. If ${P}_{k}$ is a root, then it is clearly visited at most a finite number of times.   ∎

We conclude that ${P}_{k}$ 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 $\mathrm{\Gamma }$ 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.

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 $\mathrm{\Omega }\in \mathcal{C}$. Let ${\mathrm{\Gamma }}_{\alpha }=\left\{{\alpha }_{1},{\alpha }_{2},\dots ,{\alpha }_{k},\dots ,{\alpha }_{L}\right\}$ be the ordered chain of Freeman directions associated with the chain of oriented segments ${d}_{k}=\left[{P}_{k},{P}_{k+1}\right]$ $\left(k\ge 1\right)$ along the contour. Our objective is to remove systematically, for each pair of successive displacements $\left[{\alpha }_{k},{\alpha }_{k+1}\right]\left(1\le k\le L\right)$, the additional surface area introduced when using Pick’s formula. For this purpose, we define for each successive displacement a penalty ${p}_{k}=p\left({\alpha }_{k},{\alpha }_{k+1}\right)$, and this value is subtracted from the corresponding term in the original Eq. (2) as we will see later. The penalty ${p}_{k}$ is calculated according to the next definition.

Definition 10

For $k\ge 1$, let ${P}_{k}$, ${P}_{k+1}$, and ${P}_{k+2}$ be three successive pixels in $\mathrm{\Gamma }$ and let ${\alpha }_{k}$ and ${\alpha }_{k+1}$ be the Freeman directions associated with the oriented segments ${d}_{k}=\left[{P}_{k},{P}_{k+1}\right]$ and ${d}_{k+1}=\left[{P}_{k+1},{P}_{k+2}\right]$. Let ${P}_{k+1}^{*}$ and ${P}_{k+2}^{*}$ be the two orthogonal projections of ${P}_{k+1}$ and ${P}_{k+2}$ on the adjacent edges in the direction of $\mathrm{\Omega }$, respectively, such that the angle between the oriented segments ${d}_{k}$ and $\left[{P}_{k+1},{P}_{k+1}^{*}\right]$ (resp., $\left[{P}_{k+2},{P}_{k+2}^{*}\right]$) is acute. The penalty ${p}_{k}$ is the surface of the polygon with vertices $\left\{{P}_{k+1}^{*},{P}_{k+1},{P}_{k+2},{P}_{k+2}^{*}\right\}$ inside ${P}_{k+1}\bigcup {P}_{k+2}$.

In Fig. 7, we illustrate the calculation of the penalty $p\left(0,1\right)$ for the particular successive pair of displacements ${\alpha }_{k}=0$ and ${\alpha }_{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 $\mathrm{\Gamma }$ is invariant under rotations.

Proof.

Let $\left(i,j\right)$ be the indices of two successive and admissible displacements ($0\le i,j\le 7$), then the rotation of $\left(i,j\right)$ gives the pair $\left({i}^{\prime },{j}^{\prime }\right)$ where ${i}^{\prime }=\left(i+2\right)\mathrm{mod}\text{\hspace{0.17em}}8$ and ${j}^{\prime }=\left(j+2\right)\mathrm{mod}\text{\hspace{0.17em}}8$. From Table 1, we verify that $p\left(i,j\right)=p\left({i}^{\prime },{j}^{\prime }\right)$ 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 ${\mathcal{C}}_{0}$ such a region, and its contour will be called a simple contour.

Theorem 2

Let $\mathrm{\Omega }\in {\mathcal{C}}_{0}$ be a region and $\mathrm{\Gamma }$ its contour given by the sequence of pixels

$\left[{P}_{1},{P}_{2},\dots ,{P}_{k-1},{P}_{k},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right],$
where ${P}_{i}\ne {P}_{j}$ for $1\le i\ne j\le L$. The area of $\mathrm{\Omega }$ is given by the following equation:

(5)

$A\left(\mathrm{\Omega }\right)=\frac{1}{2}\sum _{k=1}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right),$
where $p\left({\alpha }_{k},{\alpha }_{k+1}\right)$ is the penalty associated with two successive and admissible displacements ${d}_{k}=\left[{P}_{k},{P}_{k+1}\right]$ and ${d}_{k+1}=\left[{P}_{k+1},{P}_{k+2}\right]$ with Freeman directions ${\alpha }_{k}$ and ${\alpha }_{k+1}$.

Proof.

We proceed by induction on the size $n\ge 1$ of the area of $\mathrm{\Omega }$. 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 $\left(i,j\right)$, then its contour is given by the sequence of pixels $\left\{{P}_{1},{P}_{2},{P}_{3},{P}_{4},{P}_{5}={P}_{1}\right\}$ where ${P}_{1}=\left(i-1,j\right),{P}_{2}=\left(i,j-1\right),{P}_{3}=\left(i+1,j\right)$, and ${P}_{4}=\left(i,j+1\right)$. 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=\frac{1}{2}\sum _{k=1}^{4}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right),\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\left[\left(i-1\right)\left(j-1\right)-ij+ij-\left(j-i\right)\left(i+1\right) \phantom{\rule{0ex}{0ex}}+\left(i+1\right)\left(j+1\right)-ij+ij-\left(j+1\right)\left(i-1\right)\right] \phantom{\rule{0ex}{0ex}}-\left[p\left(5,7\right)+p\left(7,1\right)+p\left(1,3\right)+p\left(3,5\right)\right]\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\left[4\right]-1=1.$
Let ${\mathrm{\Omega }}^{*}\in {\mathcal{C}}_{0}$ be a region with an area equal to $n+1$ and ${\mathrm{\Gamma }}^{*}$ its contour. Let us suppose that Eq. (5) is exact for all regions $\mathrm{\Omega }$ with an area equal to $n\ge 1$ (mathematical induction on the integer $n$). The basic idea of the proof consists of eliminating ${P}_{e}\in {\mathrm{\Omega }}^{*}$, a pixel adjacent to the contour, and then applying the assumption to the resulting region $\mathrm{\Omega }={\mathrm{\Omega }}^{*}-\left\{{P}_{e}\right\}$. We denote $\mathrm{\Gamma }$ the contour of $\mathrm{\Omega }$. If we remove such a pixel in ${\mathrm{\Omega }}^{*}$, the contour ${\mathrm{\Gamma }}^{*}$ is modified to become $\mathrm{\Gamma }$. The resulting deformation of ${\mathrm{\Gamma }}^{*}$ depends on the position of ${P}_{e}$ along the contour. As shown in Fig. 8, if we switch off ${P}_{e}=\left(i,j\right)$ from ${\mathrm{\Omega }}^{*}$, then we obtain a local reconstruction of the contour passing through the pixel ${P}_{e}$

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

Fig. 8

Rearrangement of the contour.

Fig. 9

Patterns of a local rearrangement along a contour.

By a reorganization of the resulting algebraic expression, we obtain Eq. (5) for the region ${\mathrm{\Omega }}^{*}$ 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 ${P}_{e}=\left(i,j\right)$ as the pixel removed from ${\mathrm{\Omega }}^{*}$, and let us denote

${\mathrm{\Gamma }}^{*}=\left[{P}_{1},\dots ,{P}_{J-1},{P}_{J},{P}_{J+1},{P}_{J+2},{P}_{J+3},\phantom{\rule{0ex}{0ex}}{P}_{J+4},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right].$

If we remove ${P}_{e}$ and if we apply the modified Green’s formula to the region $\mathrm{\Omega }$, then using the induction assumption and rewriting the terms involved in the deformation of the contour, we obtain the area of $\mathrm{\Omega }$

$A\left(\mathrm{\Omega }\right)=n=\frac{1}{2}\sum _{k=1}^{J-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\left[\left(i-1\right)j-\left(j-1\right)i\right]+\frac{1}{2}\left[i\left(j+1\right)-j\left(i-1\right)\right]\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\sum _{k=J+3}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{J-2}p\left({\alpha }_{k},{\alpha }_{k+1}\right)\phantom{\rule{0ex}{0ex}}-p\left(6,7\right)-p\left(7,1\right)-p\left(1,1\right)-\sum _{k=J+4}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right),\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\sum _{k=1}^{J-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]+\frac{1}{2}\sum _{k=J+4}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]\phantom{\rule{0ex}{0ex}}-\sum _{k=1}^{J-2}p\left({\alpha }_{k},{\alpha }_{k+1}\right)-\sum _{k=J+4}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right)+i-1.$

From the last equation, we have

$n+1=\frac{1}{2}\sum _{k=1}^{J-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]+\frac{1}{2}\sum _{k=J+4}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]\phantom{\rule{0ex}{0ex}}-\sum _{k=1}^{J-2}p\left({\alpha }_{k},{\alpha }_{k+1}\right)-\sum _{k=J+4}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right)+i.$

Otherwise, if we apply Eq. (5) to ${\mathrm{\Gamma }}^{*}$ and if we apply the last expression, we obtain the desired result

$A\left({\mathrm{\Omega }}^{*}\right)=\frac{1}{2}\sum _{k=1}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right),\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\sum _{k=1}^{J-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]+\frac{1}{2}\sum _{k=J+4}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\left[\left(i-1\right)\left(j-1\right)-\left(j-1\right)i+ij-\left(j-1\right)\left(i+1\right)\phantom{\rule{0ex}{0ex}}+\left(i+1\right)\left(j+1\right)-ji+i\left(j+1\right)-\left(j+1\right)\left(i-1\right)\right]\phantom{\rule{0ex}{0ex}}-\sum _{k=1}^{J-2}p\left({\alpha }_{k},{\alpha }_{k+1}\right)-\sum _{k=J+4}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right)\phantom{\rule{0ex}{0ex}}-p\left(6,6\right)-p\left(6,7\right)-p\left(7,1\right)-p\left(1,2\right)+p\left(2,2\right),\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\sum _{k=1}^{J-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]+\frac{1}{2}\sum _{k=J+4}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{J-2}p\left({\alpha }_{k},{\alpha }_{k+1}\right)-\sum _{k=J+4}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right)+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 ${S}_{0}$ be a stem given by the sequence of pixels

${S}_{0}=\left\{{P}_{0},{P}_{1},\dots ,{P}_{t-1},{P}_{t},{P}_{t+1},\dots ,{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-1},{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t}\right\}$
where ${P}_{2t}={P}_{0}$ is the root of the stem. If ${P}_{j}=\left({x}_{j},{x}_{j+1}\right)$, then the following identities are verified:

(6)

$\frac{1}{2}\sum _{j=0}^{2\text{\hspace{0.17em}\hspace{0.17em}}t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]=0,$

(7)

$\sum _{j=0}^{2t-1}p\left({\alpha }_{j},{\alpha }_{j+1}\right)=t,$

(8)

$\frac{1}{2}\sum _{j=0}^{2t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]-\sum _{j=0}^{2t-1}p\left({\alpha }_{j},{\alpha }_{j+1}\right)=-t,$
where the constant $t$ represents the number of pixels in the stem.

Proof

From the definition of a stem, we have

(9)

${P}_{2t-j}={P}_{j},\phantom{\rule[-0.0ex]{1em}{0.0ex}}j=0,\dots ,t-1.$

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)

$\left\{{\alpha }_{0},{\alpha }_{1},\dots ,{\alpha }_{t-1},{\alpha }_{t},{\alpha }_{t+1},\dots ,{\alpha }_{2\text{\hspace{0.17em}\hspace{0.17em}}t-1}\right\},$
and these directions verify the next identity

(11)

${\alpha }_{t+j}={\alpha }_{t-j-1}^{T},\phantom{\rule[-0.0ex]{1em}{0.0ex}}j=0,\dots ,\left(t-1\right),$
where ${\alpha }_{t-j-1}^{T}$ is the inverse direction of ${\alpha }_{t-j-1}$. With this notation, we can rewrite the equation at the left of Eq. (6)
$\frac{1}{2}\sum _{j=0}^{2t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]=\frac{1}{2}\sum _{j=0}^{t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\sum _{j=t}^{2t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]=\frac{1}{2}\sum _{j=0}^{t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]-\frac{1}{2}\sum _{j=0}^{t-1}\left[{x}_{2t-j}{y}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-\left(j+1\right)}-{y}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-j}{x}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-\left(j+1\right)}\right].$

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

$\frac{1}{2}\sum _{j=0}^{2t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]=\frac{1}{2}\sum _{j=0}^{t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]-\frac{1}{2}\sum _{j=0}^{t-1}\left[{x}_{j}{y}_{j+1}-{y}_{j}{x}_{j+1}\right]=0.$

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

$\left\{\left[{\alpha }_{0},{\alpha }_{1}\right],\left[{\alpha }_{1},{\alpha }_{2}\right],\dots ,\left[{\alpha }_{t-2},{\alpha }_{t-1}\right],\left[{\alpha }_{t-1},{\alpha }_{t}\right],\left[{\alpha }_{t},{\alpha }_{t+1}\right],\phantom{\rule{0ex}{0ex}}\left[{\alpha }_{t+1},{\alpha }_{t+2}\right],\dots ,\left[{\alpha }_{2\text{\hspace{0.17em}\hspace{0.17em}}t-2},{\alpha }_{2\text{\hspace{0.17em}\hspace{0.17em}}t-1}\right]\right\}.$

We observe from Table 1 that these penalties verify that

$p\left({\alpha }_{t-1-j},{\alpha }_{j}\right)+p\left({\alpha }_{t-1-j},{\alpha }_{t+j}\right)=1,\phantom{\rule[-0.0ex]{1em}{0.0ex}}j=1,\dots ,\left(t-1\right).$

For the two particular displacements at the end of the stem, given by the segments ${a}_{t-1}=\left[{P}_{t-1},{P}_{t}\right]$ and ${a}_{t}=\left[{P}_{t},{P}_{t+1}\right]$, we have $p\left({\alpha }_{t-1},{\alpha }_{t}\right)=1$. From these two last relations, we obtain the following identity:

$\sum _{j=0}^{2t-1}p\left({\alpha }_{j},{\alpha }_{j+1}\right)=\sum _{j=0}^{t-2}p\left({\alpha }_{j},{\alpha }_{j+1}\right)+p\left({\alpha }_{t-1},{\alpha }_{t}\right)+\sum _{j=t}^{2t-1}p\left({\alpha }_{j},{\alpha }_{j+1}\right)=\sum _{j=1}^{t-1}\left\{p\left({\alpha }_{t-1-i},{\alpha }_{i}\right)+p\left({\alpha }_{t-1-i},{\alpha }_{t+i}\right)\right\}\phantom{\rule{0ex}{0ex}}+p\left({\alpha }_{t-1},{\alpha }_{t}\right)=\sum _{j=1}^{t-1}1+p\left({\alpha }_{t-1},{\alpha }_{t}\right)=\left(t-1\right)+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 $\mathrm{\Omega }$ be a region having a single stem, then the modified Green’s formula [Eq. (5)] applied to the contour gives the exact area of $\mathrm{\Omega }$.

Proof

Let us suppose that $\mathrm{\Omega }$ has an area equal to $n\ge 1$ and let $\mathrm{\Gamma }$ be its contour. If $\mathrm{\Omega }$ has only one stem, then the contour is given by the sequence

$\mathrm{\Gamma }=\left\{{P}_{1},{P}_{2},\dots ,{P}_{i}={P}_{0}^{s},{P}_{1}^{s},\dots ,{P}_{t}^{s},{P}_{t+1}^{s},\dots ,{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-1}^{s},{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t}^{s}={P}_{i},{P}_{i+2\text{\hspace{0.17em}\hspace{0.17em}}t+1},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right\},$
where ${P}_{1}$ is the starting pixel. In this sequence, the stem is represented by the following subsequence of pixels:
${\mathrm{\Gamma }}_{a}=\left\{{P}_{i}={P}_{0}^{s},{P}_{1}^{s}={P}_{i+1},\dots ,{P}_{t}^{s}={P}_{i+t},{P}_{t+1}^{s}\phantom{\rule{0ex}{0ex}}={P}_{i+t+1},\dots ,{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t-1}^{s}={P}_{i+2\text{\hspace{0.17em}\hspace{0.17em}}t-1},{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}t}^{s}={P}_{i+2\text{\hspace{0.17em}\hspace{0.17em}}t}.={P}_{i}\right\}.$

The pixel ${P}_{i}={P}_{0}^{s}={P}_{2t}^{s}$ is the root of the stem. Let ${\mathrm{\Gamma }}_{p}$ be the principal contour of $\mathrm{\Omega }$, which is defined by the subsequence of pixels

${\mathrm{\Gamma }}_{p}=\left\{{P}_{1},{P}_{2},\dots ,{P}_{i},{P}_{i+2\text{\hspace{0.17em}\hspace{0.17em}}t-1},\dots ,{P}_{L},{P}_{L+1}={P}_{1}\right\}.$
Let ${\mathrm{\Omega }}^{*}$ be the region surrounded by the principal contour ${\mathrm{\Gamma }}_{p}$. If we apply the modified Green’s formula [Eq. (5)] to the region $\mathrm{\Omega }$, then we have the following algebraic decomposition based on the coordinates of the pixels in the contour $\mathrm{\Gamma }$:
$A\left(\mathrm{\Omega }\right)=\frac{1}{2}\sum _{k=1}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right)\phantom{\rule{0ex}{0ex}}=\frac{1}{2}\sum _{k=1}^{i-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{i-1}p\left({\alpha }_{k},{\alpha }_{k+1}\right)\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\sum _{k=i}^{i+2t}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=i}^{i+2\text{\hspace{0.17em}}t}p\left({\alpha }_{k},{\alpha }_{k+1}\right)\phantom{\rule{0ex}{0ex}}+\frac{1}{2}\sum _{k=i+2t}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=i}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right).$

In the last summation, we identify three terms

${S}_{1}=\frac{1}{2}\sum _{k=1}^{i-1}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=1}^{i-1}p\left({\alpha }_{k},{\alpha }_{k+1}\right),\phantom{\rule{0ex}{0ex}}{S}_{2}=\frac{1}{2}\sum _{k=i}^{i+2t}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=i}^{i+2t}p\left({\alpha }_{k},{\alpha }_{k+1}\right),\phantom{\rule{0ex}{0ex}}{S}_{3}=\frac{1}{2}\sum _{k=i+2t}^{L}\left[{x}_{k}{y}_{k+1}-{y}_{k}{x}_{k+1}\right]-\sum _{k=i}^{L}p\left({\alpha }_{k},{\alpha }_{k+1}\right).$
The sum $S={S}_{1}+{S}_{3}$ corresponds to the area of the region ${\mathrm{\Omega }}^{*}$ surrounded by ${\mathrm{\Gamma }}_{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 ${S}_{2}=-t$. In conclusion, $A\left(\mathrm{\Omega }\right)={S}_{1}+{S}_{2}+{S}_{3}=S+{S}_{2}=n+t-t=n$.   ∎

It is possible to generalize the last proposition to regions with a branch in $\mathrm{\Omega }$.

Proposition 3

Let $\mathrm{\Omega }$ be a region with a branch connected to the principal contour ${\mathrm{\Gamma }}_{p}$. Let $\mathrm{\Gamma }$ be the contour of $\mathrm{\Omega }$

$\mathrm{\Gamma }=\left\{{P}_{1},\dots ,{P}_{i},{P}_{i+1},\dots ,{P}_{0}^{b},{P}_{1}^{b},\dots ,{P}_{j}^{b},\dots ,\phantom{\rule{0ex}{0ex}}{P}_{2N}^{b}={P}_{0}^{b},\dots ,{P}_{M}={P}_{1}\right\}.$

Let ${B}_{1}$ be the branch defined by the subsequence of pixels ${B}_{1}=\left\{{P}_{0}^{b},{P}_{1}^{b},\dots ,{P}_{j}^{b},\dots ,{P}_{2\text{\hspace{0.17em}\hspace{0.17em}}N}^{b}\right\}$. The pixel ${P}_{0}^{b}={P}_{2N}^{b}$ is the root of the main stem on the branch, which is connected to ${\mathrm{\Gamma }}_{p}$. Let us denote ${P}_{j}^{b}=\left({x}_{j}^{b},{y}_{j}^{b}\right)$ the coordinates of the $j$’th pixel in ${B}_{1}$ and ${\alpha }_{j}^{b}$ be the Freeman direction associated with the oriented segment $\left[{P}_{j}^{b},{P}_{j+1}^{b}\right]$ for $j=0,\dots ,2\text{\hspace{0.17em}\hspace{0.17em}}N-1$. Thus, we have

(12)

$\frac{1}{2}\sum _{j=0}^{2N-1}\left[{x}_{j}^{b}{y}_{j+1}^{b}-{y}_{j}^{b}{x}_{j+1}^{b}\right]+\sum _{1}^{2N-1}p\left({\alpha }_{j}^{b},{\alpha }_{j+1}^{b}\right)=-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 ${B}_{1}$ with a negative sign. The root ${P}_{0}^{a}$ 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 $\mathrm{\Omega }\in \mathcal{C}$ and $\mathrm{\Gamma }$ its contour; suppose that $\mathrm{\Gamma }$ has only one leaf connected to the end of a stem ${S}_{0}$ in $\mathrm{\Omega }$, then the area of $\mathrm{\Omega }$ 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 $\mathrm{\Omega }$. Let us consider the partition of the pixels in $\mathrm{\Gamma }$

• ${\mathrm{\Gamma }}_{p}$: the set of all pixels in the principal contour of $\mathrm{\Omega }$,

• ${\mathrm{\Gamma }}_{a}$: the set of internal pixels in ${S}_{0}$, and

• ${\mathrm{\Gamma }}_{b}$: the set of pixels in the leaf contour.

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

Let us denote $\left\{{P}_{1}^{b},{P}_{2}^{b},\dots ,{P}_{J}^{b},{P}_{J+1}^{b}={P}_{1}^{b}\right\}$ the subsequence of pixels defining the leaf contour, where ${P}_{j}^{b}=\left({x}_{j}^{b},{y}_{j}^{b}\right),j=1,\dots ,J$ are the coordinates of such a pixel and ${\alpha }_{j}^{b}$ is the Freeman direction of the segment $\left[{P}_{j}^{b},{P}_{j+1}^{b}\right]$. Let us consider the two sums

(13)

${S}_{1}^{b}=\frac{1}{2}\sum _{j=1}^{J}\left[{x}_{j}^{b}{y}_{j+1}^{b}-{y}_{j}^{b}{x}_{j+1}^{b}\right],\phantom{\rule[-0.0ex]{1em}{0.0ex}}{S}_{2}^{b}=-\sum _{j=1}^{J}p\left({\alpha }_{j}^{b},{\alpha }_{j+1}^{b}\right).$
The first sum ${S}_{1}^{b}$ 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 ${S}_{2}^{b}$ 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.

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, Alain Chalifour, Fathallah Nouboud, Fathallah Nouboud, Yvon Voisin, 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
Received: 14 March 2017; Accepted: 10 November 2017; Published: 5 December 2017
JOURNAL ARTICLE
11 PAGES

SHARE
KEYWORDS