|
1.IntroductionLet 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 of is given by the following line integral: 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 where are the coordinates associated with the center of the pixel . The integer represents the number of pixels in . The discrete version of Eq. (1) is given by the equationUnfortunately, 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.4–8 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.DefinitionsLet 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 is the complementary set in the discrete plane or in the image. Definition 1Let 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 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 2The 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 where 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 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. The length 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 4A stem in a contour is a subset such that there exist two integers and such that where , , and . The pixel is called the root of the stem, and the pixel 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 . 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. Definition 5Let be a fixed single stem in with root . Let , be disjoint stems in connected to by a root . The union of the stems is called a branch. The pixel is called the root of the branch, and 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 6Let be a fixed stem in with root and let , be disjoint branches in with the root of the branch , then the union of all branches is called a tree. The stem is called the trunk of the tree. The root 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 7A leaf 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 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 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 8The principal contour of a region is the set of pixels in that remains after the elimination of all stems, branches, trees, and leaf contours. Proposition 1Let 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 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 ContourNow, we are ready to propose a new contour algorithm enabling us to construct the contour (eight-connected, closed, and positively oriented) of a region . 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 an oriented segment, or vector, from the center of the pixel to the center of the pixel . Definition 9A black pixel is called a potential starting pixel of a contour if the adjacent pixel with coordinates is black and if the pixel with coordinates is white. The Freeman direction associated with the displacement from to is . We denote the set of all potential starting pixels. Proposition 2Let and its contour . There exist and in such that the Freeman direction of the oriented segment equals and such that has a unique pixel as predecessor. Proof.Let be the pixel with coordinates Since is bounded, then exists. By the definition of , we have and in are the two successive candidate pixels with the Freeman direction equal to . It is easy to show, or to illustrate, that the predecessor of belongs to the exclusive set of coordinates ; otherwise, we have a contradiction because of the definition of . ∎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 encountered during the construction of a contour with the intent of individually constructing the contour of each component. When the set becomes empty, no component remains. Finally, when we reach the predecessor , the construction of the contour is stopped. Let and be the starting and second pixels identified previously, respectively, and let . At each step , we have to identify the pixel such that the oriented segment satisfies the two following conditions: (1) is a black pixel and (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 to . Let the oriented segment on the contour issued from the step . Let be the Freeman direction associated with this displacement. We will prove that there exists one and only one pixel such that the preceding conditions are verified. The black pixel is chosen according to the knowledge of the direction between the preceding pixels. The choice of the pixel must respect the last two constraints. The enumeration of the potential patterns of distribution of white and black pixels in the neighborhood of and will allow us to identify this unique pixel on an eight-connected contour. To select the pixel , we covered all of the possible patterns (see Table 1) in the neighborhood of the pixels and that respect the attributes of the contour. In Table 1, a value at the position () indicates that a displacement in the Freeman direction is admissible after a displacement in the direction along the contour. The meaning of the value in position () will be specified further on. For a given , there exists only one that corresponds to a displacement along the contour such that the constraints are verified, then we can determine the unique . 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 1Penalty p(i,j) for each pair of successive and admissible displacements (i,j).
Given the pixels and and displacement , we see from Table 1 that there are no more than seven directions to visit before choosing the next pixel and the direction , 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 . The next theorem summarizes the situation discussed above. Theorem 1Let be a nonempty region and let and be the two pixels found at the first step of the algorithm. Then, Proof.If equals values other than 6 or 7, we have a contradiction in regard to the position of the pixel , 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. 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. Proof.The only pixels revisited on are pixels belonging to a stem and consequently to a branch or a tree. Let be such a pixel. If is not a root, then and then . If is a root, then it is clearly visited at most a finite number of times. ∎ We conclude that 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 AreaIn this section, we develop a new expression of the discrete Green’s identity for the computation of the area of a region . Let be the ordered chain of Freeman directions associated with the chain of oriented segments along the contour. Our objective is to remove systematically, for each pair of successive displacements , the additional surface area introduced when using Pick’s formula. For this purpose, we define for each successive displacement a penalty , and this value is subtracted from the corresponding term in the original Eq. (2) as we will see later. The penalty is calculated according to the next definition. Definition 10For , let , , and be three successive pixels in and let and be the Freeman directions associated with the oriented segments and . Let and be the two orthogonal projections of and on the adjacent edges in the direction of , respectively, such that the angle between the oriented segments and (resp., ) is acute. The penalty is the surface of the polygon with vertices inside . In Fig. 7, we illustrate the calculation of the penalty for the particular successive pair of displacements and . 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 3The penalty associated with a pair of admissible displacements along is invariant under rotations. Proof.Let be the indices of two successive and admissible displacements (), then the rotation of gives the pair where and . From Table 1, we verify that 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 such a region, and its contour will be called a simple contour. Theorem 2Let be a region and its contour given by the sequence of pixels where for . The area of is given by the following equation: where is the penalty associated with two successive and admissible displacements and with Freeman directions and .Proof.We proceed by induction on the size 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 , then its contour is given by the sequence of pixels where , and . 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 Let be a region with an area equal to and its contour. Let us suppose that Eq. (5) is exact for all regions with an area equal to (mathematical induction on the integer ). The basic idea of the proof consists of eliminating , a pixel adjacent to the contour, and then applying the assumption to the resulting region . 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 along the contour. As shown in Fig. 8, if we switch off from , then we obtain a local reconstruction of the contour passing through the pixelUnfortunately, to establish the proof we have to forecast all possible deformations of when eliminating a pixel adjacent to . In Fig. 9, we illustrate all patterns of deformations of obtained when eliminating a pixel in with the constraint that the region must remain connected. We assert that any region 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 . For each deformation, we first apply Eq. (5) to the contour of the region with an area equal to , and subsequently we add the area eliminated following the reorganization of the original contour . By a reorganization of the resulting algebraic expression, we obtain Eq. (5) for the region with an area equal to . 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 as the pixel removed from , and let us denote If we remove 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 From the last equation, we have Otherwise, if we apply Eq. (5) to and if we apply the last expression, we obtain the desired result 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 4Let be a stem given by the sequence of pixels where is the root of the stem. If , then the following identities are verified: where the constant represents the number of pixels in the stem.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: and these directions verify the next identity where is the inverse direction of . With this notation, we can rewrite the equation at the left of Eq. (6)Using the relation Eq. (9), the last summation verifies In conclusion, the first Eq. (6) is proved. Again, let us consider the Freeman directions along the stem We observe from Table 1 that these penalties verify that For the two particular displacements at the end of the stem, given by the segments and , we have . From these two last relations, we obtain the following identity: 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 3Let be a region having a single stem, then the modified Green’s formula [Eq. (5)] applied to the contour gives the exact area of . ProofLet us suppose that has an area equal to and let be its contour. If has only one stem, then the contour is given by the sequence where is the starting pixel. In this sequence, the stem is represented by the following subsequence of pixels:The pixel is the root of the stem. Let be the principal contour of , which is defined by the subsequence of pixels Let be the region surrounded by the principal contour . 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 :In the last summation, we identify three terms The sum corresponds to the area of the region surrounded by ; then we have . Here, is the number of distinct pixels on the stem. In addition, by Lemma 4, we see that . In conclusion, . ∎It is possible to generalize the last proposition to regions with a branch in . Proposition 3Let be a region with a branch connected to the principal contour . Let be the contour of Let be the branch defined by the subsequence of pixels . The pixel is the root of the main stem on the branch, which is connected to . Let us denote the coordinates of the ’th pixel in and be the Freeman direction associated with the oriented segment for . Thus, we have 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 with a negative sign. The root 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 4Let a region and its contour; suppose that has only one leaf connected to the end of a stem 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
Since is a simple contour, then by Theorem 2, the contribution of these pixels to Eq. (5) gives the area of the domain inside . Otherwise, by Lemma 4, the contribution of the pixels in gives, with a minus sign, the number of pixels in . However, we can show that the contribution of the pixels in is equal to the number of pixels in the leaf. Let us denote the subsequence of pixels defining the leaf contour, where are the coordinates of such a pixel and is the Freeman direction of the segment . Let us consider the two sums The first sum 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 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. 5.ConclusionWe 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. ReferencesD. H. Redelmeier,
“Counting polyominoes: yet another attack,”
Discrete Math., 36 191
–203
(1981). http://dx.doi.org/10.1016/0012-365X(81)90237-5 DSMHA4 0012-365X Google Scholar
J. E Marsden and A. J. Tromba, Vector Calculus, 3rd ed.W.H. Freeman and Company, New York
(1988). Google Scholar
J. M. Chassery and A. Montanvert, Géométrie Discrète en Analyse d’Images, Hermès, Paris
(1991). Google Scholar
A. Rosenfeld,
“Connectivity in digital pictures,”
J. ACM, 17
(1), 146
–160
(1970). http://dx.doi.org/10.1145/321556.321570 JACOAH 0004-5411 Google Scholar
A. Rosenfeld,
“Adjacency in digital pictures,”
Inf. Control, 26 24
–33
(1974). http://dx.doi.org/10.1016/S0019-9958(74)90696-2 IFCNA4 0019-9958 Google Scholar
A. Rosenfeld and R. A. Melter, Digital Geometry, 11 69
–72 Springer-Verlag, New York
(1989). Google Scholar
A. Rosenfeld and T. Y. Kong,
“Connectedness of a set, its complement, and their common boundary,”
Contemp. Math., 119 125
–128
(1991). http://dx.doi.org/10.1090/conm/119 CTMAEH 1098-3627 Google Scholar
T. Yung Kong and A. Rosenfeld, Topological Algorithms for Digital Image Processing, Elsevier, North Holland
(1996). Google Scholar
S. Brlek, G. Labelle and A. Lacasse,
“Algorithms for polyominoes based on the discrete Green theorem,”
Discrete Appl. Math., 147 187
–205
(2005). http://dx.doi.org/10.1016/j.dam.2004.09.011 DAMADU 0166-218X Google Scholar
S. Brlek, G. Labelle and A. Lacasse,
“The discrete Green theorem and some applications in discrete geometry,”
Theor. Comput. Sci., 346 200
–225
(2005). http://dx.doi.org/10.1016/j.tcs.2005.08.019 TCSCDI 0304-3975 Google Scholar
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,
479
–486
(1998). Google Scholar
BiographyAlain 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. |