Abstract
In this paper, we define a new flavour of well-composedness, called strong Euler well-composedness. In the general setting of regular cell complexes, a regular cell complex of dimension n is strongly Euler well-composed if the Euler characteristic of the link of each boundary cell is 1, which is the Euler characteristic of an \((n-1)\)-dimensional ball. Working in the particular setting of cubical complexes canonically associated with \(n\)D pictures, we formally prove in this paper that strong Euler well-composedness implies digital well-composedness in any dimension \(n\ge 2\) and that the converse is not true when \(n\ge 4\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The concept of well-composedness of a digital set (also called picture) was first introduced in Latecki et al. (1995) for two-dimensional (2D) pictures and extended later in Latecki (1997) for three-dimensional (3D) pictures: a well-composed picture satisfies that its continuous analog has a boundary surface that is a manifold. The concept is described in terms of forbidden subsets (also called critical configurations) for which the picture is not well-composed. 3D well-composed pictures may have some computational advantages regarding the application of several algorithms in computer vision, computer graphics and image processing (Siqueira et al. 2005; Boutry et al. 2018). For example, the topology of a given 2D picture can be preserved by rigid transformations thanks to well-composedness; topology-preserving front propagation can lead to well-composed segmentation; Euler numbers of 2D pictures can be computed locally thanks to well-composedness; well-composed Jordan curves are known to separate the digital plane; the boundary of the continuous analog of a well-composed 3D picture is a manifold. Furthermore, numerous applications related to well-composed pictures exist: the Marching Cubes Algorithm (Siqueira et al. 2008) has no ambiguous cases on well-composed pictures (no hole problem occurs), we can obtain thin topological maps on pictures thanks to well-composedness (Marchadier et al. 2004) and the tree of shapes is well-defined (Géraud et al. 2013). Regarding the new flavour of strong Euler well-composedness introduced in this paper, there is no known application so far. Nevertheless, since strong Euler well-composedness can be defined on regular cell complexes and because it implies DWCness on cubical grids, we think that this flavour of well-composedness could be used in wider applications such as, for example, the computation of thin topological maps on regular cell complexes.
In general, pictures are not a priori well-composed. Nevertheless, there are several “repairing” methods for turning them into well-composed pictures (see, for example, Boutry et al. 2015a, b; Lachaud and Montanvert 2000; Latecki 1998; Siqueira et al. 2008; Stelldinger and Latecki 2006).
In Boutry et al. (2015b), the concept of well-composedness and critical configuration was extended to any dimension \(n\ge 2\). Then, an \(n\)D picture is continuously well-composed if its continuous analog has a boundary surface that is an \((n-1)\)D manifold, whereas an \(n\)D picture is digitally well-composed if it does not contain any critical configuration.
Equivalences between different flavours of well-composedness have been studied in Boutry et al. (2018), namely: continuous well-composedness (CWCness), digital well-composedness (DWCness), well-composedness in the Alexandrov sense (AWCness), well-composedness based on the equivalence of connectivities (EWCness) and well-composedness on arbitrary grids (AGWCness). More specifically, it is well-known that AWCness, CWCness, DWCness and EWCness are equivalent in 2D. In 3D, only AWCness, CWCness, and DWCness are equivalent. No link between AGWCness and other flavours of well-composedness is known. For pictures of dimension \(n\ge 4\), our knowledge of the logical relationships between CWCness, DWCness and EWCness is very incomplete, though it has been shown that AWCness is equivalent to DWCness (see Boutry et al. 2020c) and that DWCness implies EWCness (see Boutry et al. 2015b). Recently, in Boutry et al. (2020b), a counterexample in 4D has been given to prove that DWCness does not imply CWCness, which the authors consider to be an important result since it breaks with the idea that all the different flavours of well-composedness are equivalent.
In Gonzalez-Diaz et al. (2015, 2017), Boutry et al. (2019), we defined another flavour of well-composedness called self-dual weak well-composedness (swWCness) that extends the notion of DWCness to any regular cell complex. Roughly speaking, a regular cell complex is a topological space made up of a collection of k-cells (homeomorphicFootnote 1 to k-dimensional balls) glued together by their boundaries. A regular cell complex satisfying that any of its k-cell is a k-dimensional cube is referred to as a cubical complex. A cubical complex Q(I) can always be associated with any \(n\)D picture I (we will see later how to construct Q(I) from I). We say that a regular cell complex K(I) is a cell complex over I if there exists a deformation retraction from K(I) to Q(I). Besides, K(I) is said to be weakly well-composed if, for each vertex v on the boundary of K(I), the set of n-cells of K(I) incident to v are face-connected. In Gonzalez-Diaz et al. (2015, 2017), Boutry et al. (2019), we also developed a topological method for repairing the cubical complex Q(I) canonically associated with an \(n\)D picture I not being DWC. Such a method constructs a “simplicial decomposition” \(\big (P_S(I)\), \(P_S(bI)\big )\) of I, where bI is I’s complement (an \(n\)D picture that is precisely defined in Definition 1), and where \(P_S(I)\) and \(P_S(bI)\) satisfy the following conditions:
-
(1)
\(P_S(I)\) is a cell complex over I, \(P_S(bI)\) is a cell complex over bI, and
-
(2)
\(P_S(I)\) and \(P_S(bI)\) are weakly well-composed, that is, \(\big (P_S(I)\), \(P_S(bI)\big )\) is self-dual weakly well-composed.
As it is shown in Boutry et al. (2019), in the setting of cubical complexes canonically associated with \(n\)D pictures, swWCness is equivalent to DWCness for all \(n\ge 2\). Our ultimate goal is to prove that our topological reparation method provides CWC regular cell complexes.
Since, according to us, such a goal is not reachable yet, in Boutry et al. (2020a), we proposed an intermediary flavour of well-composedness, called Euler well-composedness (\(\chi \)WCness). The cell complex K(I) over I is \(\chi \)WC if the Euler characteristic of the link of each vertex of the boundary of K(I) is equal to 1, which is the Euler characteristic of an \((n-1)\)-dimensional ball. Although partial results regarding \(\chi \)WCness for \(n\)D pictures (in the case of \(n=2,3,4\)) were given in Boutry et al. (2020a), we have observed that, in general, \(\chi \)WCness does not imply DWCness. For example, consider the 4D picture I in Fig. 1, whose foreground is the set of points \(F_I=\{(0, 1, 0, 0)\), (0, 0, 0, 0), (0, 0, 1, 0), (1, 0, 1, 0), (1, 1, 1, 0), (0, 2, 0, 0), (0, 2, 1, 0), \((1, 2, 1,0)\}\). Clearly, I contains the 2D critical configuration \(\{p,p'\}\) where \(p=(0,1,0,0)\) and \(p'=(1,1,1,0)\), while it can be shown that Q(I) is \(\chi \)WC. This is established below in the proof of Lemma 3. That proof also shows that Q(bI) is \(\chi \)WC. It follows from the \(\chi \)WCness of Q(I) and Q(bI) in this example that Theorem 4 of Boutry et al. (2020a) is actually incorrect – its computer-assisted “proof” was unfortunately flawed. The fact that a 4D picture I need not be DWC even if both of Q(I) and Q(bI) are \(\chi \)WC is a significant weakness of the concept of \(\chi \)WCness.
Accordingly, the present paper will introduce a new flavour of well-composedness called strong Euler well-composedness (\(\overset{+}{\chi }\)WCness), which is a concept more restrictive than the one of \(\chi \)WCness given in Boutry et al. (2020a), with the aim of proving that \(\overset{+}{\chi }\)WCness implies DWCness in any dimension \(n\ge 2\), even though the converse is not true in any dimension \(n\ge 4\). The authors are convinced that CWCness implies \(\overset{+}{\chi }\)WCness, but do not have a rigorous proof of this at the moment. In such a case, \(\overset{+}{\chi }\)WCness would be an effectively computable property useful to detect cases in which the cubical complex canonically associated with a DWC picture is not CWC.
The plan is the following: Sect. 2 recalls the background needed to understand the rest of the paper. Section 3 introduces the concept of strong Euler well-composedness. Section 4 shows that strong Euler well-composedness implies digital well-composedness. Section 5 shows that the converse is not true. Finally, Sect. 6 concludes the paper.
2 Background
First, let us introduce the concept of n-dimensional digital sets (also called \(n\)D pictures), taken from the field of digital geometry.
Definition 1
(\(n\)D picture) Let \(n\ge 1\) be an integer and \({\mathbb {Z}} ^n\) the set of points with integer coordinates in \({\mathbb {R}}^n\). An \(n\)D picture is a pair \(I=({\mathbb {Z}} ^n,F_I)\), where \(F_I\) is a subset of \({\mathbb {Z}} ^n\). The set \(F_I\) is called the foreground of I and the set \({\mathbb {Z}} ^n{\setminus } F_I\) the background of I. The complement of I is defined as the \(n\)D picture \(bI=({\mathbb {Z}} ^n,{\mathbb {Z}} ^n{\setminus } F_I)\).
We say that a property P of \(n\)D pictures is self-dual if an \(n\)D picture I has property P whenever the picture bI has property P.
In Boutry et al. (2015b), the concept of block was introduced to extend the notion of DWCness to any dimension. Given a point \(z \in {\mathbb {Z}} ^n\) and a family of vectors \({\mathcal {F}} = \{f^1, \dots , f^k\} \subseteq {\mathcal {B}} \) (where \({\mathcal {B}} = \{e^1, \dots , e^n\}\) is the canonical basis of \({\mathbb {Z}} ^n\)), the k-block associated with the pair \((z,{\mathcal {F}})\) is the set defined as:
Thus, a 0-block is a point, a 1-block is a set of two points in \({\mathbb {Z}} ^n\) on an unit edge, a 2-block is a set of four points on a unit square, and so on. A subset \(B \subset {\mathbb {Z}} ^n\) is called a block if there exists a couple \((z,{\mathcal {F}}) \in {\mathbb {Z}} ^n \times {\mathcal {P}} ({\mathcal {B}})\) (where \({\mathcal {P}} ({\mathcal {B}})\) represents the set of all the subsets of \({\mathcal {B}} \)), such that \(B = B(z,{\mathcal {F}})\).
Definition 2
(antagonists) Two points p, q belonging to a block B are said to be antagonists in B if their distance is equal to the maximum distance using the \(L^1\)-normFootnote 2 between two points in B, that is, \(\Vert p - q\Vert _1 = \max \big \{\Vert r - s\Vert _1\) : \(r,s \in B \big \}\).
Remark 1
The antagonist of a point p in a block B containing p exists and is unique.
Notice that when two points \((x_1,\dots ,x_n)\) and \((y_1,\dots ,y_n)\) in \({\mathbb {Z}} ^n\) are antagonists in a k-block with \(k \in \llbracket 0,n \rrbracket \) then there is a set \(\{i_1,\dots ,i_{k}\}\subseteq \llbracket 1,n \rrbracket \) such that \(|x_i-y_i|=1\) for \(i\in \{i_1,\dots ,i_{k}\}\) and \(x_i=y_i\) otherwise.
Definition 3
(critical configuration) Let \(I=({\mathbb {Z}} ^n, F_I)\) be an \(n\)D picture and B a k-block with \(k \in \llbracket 2,n \rrbracket \). We say that I contains a critical configuration in the block B if \(F_I \cap B = \{p,p'\}\) or \(F_I \cap B = B {\setminus } \{p,p'\}\), with \(p,p'\) being antagonists in B.
The above concept of critical configuration is used to define the notion of DWCness, based on local patterns, in any dimension.
Definition 4
(digital well-composedness) An \(n\)D picture is said to be digitally well-composed (DWC) if it does not contain any critical configuration in any block.
Notice that the above definition of digital well-composedness is self-dual.
Roughly speaking, an \(n\)D cubical complex Q is a special kind of regular cell complex made up of a collection of n-dimensional cubes glued together by their boundaries (faces). If a k-dimensional cube (k-cell) \(\mu \in Q\) is a face of an \(\ell \)-dimensional cube (\(\ell \)-cell) \(\sigma \in Q\) and \(k<\ell \) then \(\mu \) is said to be a proper face of \(\sigma \) and \(\sigma \) a proper coface of \(\mu \). A maximal cell of Q is not a proper face of any other cell of Q. The next definition states how an \(n\)D cubical complex can always be associated with an \(n\)D picture.
Definition 5
(cubical complex canonically associated with an \(n\)D picture) The cubical complex Q(I) canonically associated with an \(n\)D picture \(I=({\mathbb {Z}} ^n\), \(F_I)\) is the \(n\)D cubical complex whose maximal cells are n-dimensional unit cubes centered at each point in \(F_I\) and whose \((n-1)\)-faces are \((n-1)\)-dimensional unit cubes parallel to the coordinate hyperplanes.
Figure 2 shows, from left to right, the cubical complexes canonically associated with a 2D picture and a 3D picture that each have two foreground points.
Notice that each cell in the cubical complex Q(I) is uniquely determined by the coordinates of its barycenter. This way, each n-dimensional cube can be encoded by its barycenter, which is a point \(p\in {\mathbb {Z}} ^n\); its \((n-1)\)-faces by points under the form \(p{\pm } \frac{1}{2}e^i\), with \(e^i\in {\mathcal {B}} = \{e^1, \dots , e^n\}\); in general, its k-faces can be encoded by points under the form \(p+ \sum _{i\in \{i_1,\ldots , i_{n-k}\}}\lambda _i\,e^i\), where \(\{i_1,\ldots , i_{n-k}\}\) is a set of \(n-k\) different indices in \(\llbracket 1,n \rrbracket \) and \(\lambda _i\in \{\pm \frac{1}{2}\}\). That is, k-cells are represented by points with k integer coordinates and \(n-k\) coordinates that are odd multiples of \(\frac{1}{2}\).
Remark 2
In the sequel, we will identify a k-cell of Q(I) with its barycenter, if no confusion may arise. Besides, from now on, when needed and for the sake of simplicity, a point p in \({\mathbb {R}} ^n\) will be expressed as Cartesian products of its coordinates:
Besides, when a coordinate is repeated k times, we will write \((p_1,{\mathop {\dots }\limits ^{k}},p_1)=(p_1)^k\). These notations could be combined. For example:
The boundary surface of an \(n\)D cubical complex Q, denoted by \(\partial Q\), is the \((n-1)\)D cubical complex composed by the \((n-1)\)-dimensional cubes that are proper faces of exactly one maximal cell of Q, together with all their faces. See Fig. 3 for toy examples.
The underlying space of an \(n\)D cubical complex Q, i.e., the union of the n-dimensional cubes of Q as subspaces of \({\mathbb {R}} ^n\), will be denoted by |Q|. An \(n\)D cubical complex Q is said to be (continuously) well-composed (CWC) if \(|\partial Q|\) is an \((n-1)\)D manifold, that is, each point of \(|\partial Q|\) has a neighborhood in \(|\partial Q|\) homeomorphic to \({\mathbb {R}} ^{n-1}\).
3 Introducing the concept of strong Euler well-composedness
In this section, we introduce a new concept of Euler well-composedness that is more restrictive than the one given in Boutry et al. (2020a).
Definition 6
(Euler characteristic) Let S be a finite set of cells. Let \(a_k\) denote the number of k-cells of S. The Euler characteristic of S is defined as:
Recall that the Euler characteristic of a regular cell complex depends only on its underlying space’s homotopy type (Hatcher 2002, p. 146).
Although the following concepts could be defined on regular cell complexes without problem, we will define them in terms of \(n\)D cubical complexes, since that will be our context.
Definition 7
(star and link) (Edelsbrunner and Harer 2010) Let \(\sigma \) be a cell of a given \(n\)D cubical complex Q. Then,
-
The closure of \(\sigma \), denoted \(\mathrm {Cl}\,( \sigma )\), is the set of cells having \( \sigma \) as a coface.Footnote 3 By extension, the closure of a set of cells is the union of the closure of each cell in the set.
-
The star in Q of \(\sigma \), denoted \({\mathrm {St}}_Q ( \sigma )\), is the set of cells of Q having \( \sigma \) as a face.Footnote 4 By extension, the star in Q of a set of cells is the union of the star in Q of each cell in the set.
-
The link in Q of \(\sigma \), denoted \(\mathrm {Lk} _Q (\sigma )\), is the closure of the star in Q of \( \sigma \) minus the star in Q of the closure of \( \sigma \), that is, \(\mathrm {Cl}\,\mathrm {St} _Q (\sigma ){\setminus } {\mathrm {St}}_Q\mathrm {Cl}\,(\sigma )\). In other words, \(\mathrm {Lk} _Q (\sigma )\) is the set of cells in Q that share a coface but no face with \(\sigma \).
We need now to extend the notion of \(\chi \)-critical vertex given in Boutry et al. (2020a) to the notion of \(\chi \)-critical cell.
Definition 8
(\({{{\chi }}}\)-critical cell) Let Q be an \(n\)D cubical complex, \(n \ge 2\). A cell \(\sigma \in \partial Q\) is \(\chi \)-critical for Q if:
where \({\mathbb {B}}^{n-1} \) is an \((n-1)\)-dimensional ball.
For example, in all the cases of Fig. 4 except for case (c), the vertex v is a \(\chi \)-critical vertex for Q(I). Nevertheless, in case (c), the edge e is \(\chi \)-critical for Q(I).
Remark 3
Let Q(I) be the cubical complex canonically associated with an \(n\)D picture I, \(n \ge 1\). Let v be a vertex (0-cell) of Q(I). Then, \(\chi (\mathrm {Cl}\,\mathrm {St} _{Q(I)}(v){)}=1\) since \(|\mathrm {Cl}\,\mathrm {St} _{Q(I)}(v)|\) is contractible.Footnote 5 Besides, \({\mathrm {St}}_{Q(I)}\mathrm {Cl}\,(v)={\mathrm {St}}_{Q(I)} (v)\subseteq \mathrm {Cl}\,\mathrm {St} _{Q(I)}(v)\) since \(\mathrm {Cl}\,v=\{v\}\). Therefore,
The result below extends Remark 3 to k-cells with \(k\ge 0\).
Lemma 1
Let Q(I) be a cubical complex canonically associated with an \(n\)D picture I and let \(\sigma \) be a k-cell of Q(I) with \(k< n\), then:
Proof
We will proceed by induction. If \(k=0\), then Eq. (2) coincides with Eq. (1). Let \(k>0\). Using the notation given in Remark 2, we can assume, without loss of generality, that
Let \(I_0\) be the picture such that \(F_{I_0} = F_I\cap ((0)\times {\mathbb {Z}} ^{N-1})\). Then \(F_{I_0}=(0)\times F_J\) for some \((n-1)\)D picture J. Let
Then \(\sigma =(0)\times \sigma '\) and \(\sigma '\) is a \((k-1)\)-cell of Q(J). Now,
and \({\mathrm {St}}_{Q(I_0)}(\sigma )={\mathrm {St}}_{Q(I)}(\sigma )\). Similarly,
Then, it is satisfied that \({\mathrm {St}}_{Q(I)}(\sigma )=(0)\times {\mathrm {St}}_{Q(J)}(\sigma ')\), which indicates that
Now, let us prove that \(\chi \big (\mathrm {Lk} _{Q(I)} (\sigma )\big )=\chi \big (\mathrm {Lk} _{Q(J)} (\sigma ')\big )\). Readily,
Besides, \(\mathrm {Cl}\,(\sigma )=\left\{ (0),\left( \frac{1}{2}\right) ,\left( -\frac{1}{2}\right) \right\} \times \mathrm {Cl}\,(\sigma ')\) and then
from which we conclude that \(\mathrm {Lk} _{Q(I)}(\sigma )=\left\{ (0),\left( \frac{1}{2}\right) ,\left( -\frac{1}{2}\right) \right\} \times \mathrm {Lk} _{Q(J)}(\sigma ')\). Then,
Now, assuming by induction that \(\chi \big (\mathrm {Lk} _{Q(J)} (\sigma ')\big )=1-(-1)^{k-1}\chi \big ({\mathrm {St}}_{Q(J)} (\sigma '))\) then
concluding the proof. \(\square \)
It follows from Lemma 1 that a cell \(\sigma \in \partial Q(I)\) is \(\chi \)-critical for Q(I) if and only if:
Notice that, following the same arguments as in the proof of Lemma 1, we can express the star and the link of any k-cell \(\sigma \) of Q(I) (\(0< k< n\)) in terms of the star and the link of a vertex v of Q(J), where J is an \((n-k)\)-dimensional “slice” of I and we have that \(\chi \big ({\mathrm {St}}_{Q(I)}(\sigma )\big ) = (-1)^k\chi \big ({\mathrm {St}}_{Q(J)}(v)\big )\) and, therefore, \(\chi \big (\mathrm {Lk} _{Q(I)}(\sigma )\big ) = \chi \big (\mathrm {Lk} _{Q(J)}(v)\big )\).
Remark 4
Let Q(I) be the cubical complex canonically associated with an \(n\)D picture I, \(n \ge 2\). Then, for any vertex \(v\in \partial Q(I)\), there exist \(2^k \left( {\begin{array}{c}n\\ k\end{array}}\right) \) k-cells in \({\mathrm {St}}_{Q(I) \cup Q(bI)}(v)\). Hence,
Besides, since \(\chi \big ({\mathrm {St}}_{Q(I)}(v)\big )= \chi \big ({\mathrm {St}}_{Q(I) \cup Q(bI)}(v)\big )-\chi \big ({\mathrm {St}}_{Q(I) \cup Q(bI)}(v){\setminus } {\mathrm {St}}_{Q(I)}(v)\big )\) then:
Moreover, if \(\sigma \) is an r-cell of \(\partial Q(I)\) then for \(0 \le k \le n-r\) the number of \((r + k)\)-cells in \({\mathrm {St}}_{Q(I)\cup Q(bI)}(\sigma )\) is \(2^k \big (\begin{matrix}n-r\\ k\end{matrix}\big )\), and
Then,
Definition 9
(strong Euler well-composedness) An \(n\)D cubical complex is Euler well-composed (\(\chi \)WC) if it has no \(\chi \)-critical vertices (Boutry et al. 2020a). It is strongly Euler well-composed (\(\overset{+}{\chi }\)WC) if it has no \(\chi \)-critical cells.
Observe that the definition of \(\overset{+}{\chi }\)WCness is more restrictive than the definition of \(\chi \)WCness given in Boutry et al. (2020a) in the sense that we do not only check if there are \(\chi \)-critical vertices (or 0-cells) but we also check if there are \(\chi \)-critical k-cells for any \(k\in {\mathbb {Z}} \). With the following lemma, we can conclude that \(\overset{+}{\chi }\)WCness and DWCness are equivalent when we deal with cubical complexes canonically associated with \(n\)D pictures for \(n=2, 3\).
Lemma 2
Let Q(I) be the cubical complex canonically associated with an \(n\)D picture I for \(n=2,3\). Then Q(I) has no \(\chi \)-critical cells if and only if I is DWC.
Proof
We have verified by computer search that there are no counterexamples to this lemma. \(\square \)
With the following result, we can conclude that the definition of s\(\chi \)WCness given in Boutry et al. (2020a) is weaker than the definition of \(\overset{+}{\chi }\)WCness given in this paper for \(n\)D pictures with \(n\ge 4\), that is, s\(\chi \)WCness does not imply \(\overset{+}{\chi }\)WCness for \(n\)D pictures with \(n\ge 4\).
Lemma 3
The fact that neither Q(I) nor Q(bI) has \(\chi \)-critical vertices does not imply that Q(I) has no \(\chi \)-critical cells for any \(n\)D picture I with \(n\ge 4\).
Proof
Let us compute a counterexample for the statement presented above. Consider the cubical complex Q(I) canonically associated with an \(n\)D picture \(I=({\mathbb {Z}} ^n,F_I)\) with \(n\ge 4\), such that \(F_I=\{(0,1,0), (0,0,0),(0,0,1),(1,0,1),(1,1,1)\), \((0,2,0),(0,2,1),(1,2,1)\}\times (0)^{n-3}\) (see Fig. 1). Then, the set of n-cells of Q(I) incident to the \((n-3)\)-cell
is:
(see Fig. 5). Observe that \(\sigma \in \partial Q(I)\) and \({\mathrm {St}}_{Q(I)}(\sigma ) \) is the set:
Then,
Therefore, \(\sigma \) is a \(\chi \)-critical \((n-3)\)-cell for Q(I) (with \(n-3\ge 1\)), so Q(I) is not \(\overset{+}{\chi }\)WC.
Now, let us prove that none of the vertices of \(\partial Q(I)\) are \(\chi \)-critical for Q(I) or Q(bI). That is, let us prove that if \(v\in \partial Q(I)\) then \(\chi \big ({\mathrm {St}}_{Q(I)}(v)\big )=0=\chi \big ({\mathrm {St}}_{Q(bI)}(v)\big )\).
First, let us see that \(\chi \big ({\mathrm {St}}_{Q(I)}(v)\big )=0\).
Let \(x_n\) be the last coordinate of v (then \(x_n=\pm \frac{1}{2}\)). Let
and
Then, \({\mathrm {St}}_{Q(I)}(v)=A\sqcup B\). Let \(f:A\rightarrow B\) such that \(f(\sigma )=(y_1,\dots ,y_{n-1},x_n)\) for each \(\sigma =(y_1,\dots ,y_{n-1},0)\in A\). Then, \(\chi (\{f(\sigma )\})=-\chi (\{\sigma \})\) for any \(\sigma \in A\) since the dimension of \(f(\sigma )\) is one less than the dimension of \(\sigma \). Therefore,
Second, let us see that \(\chi \big ({\mathrm {St}}_{Q(bI)}(v)\big )=0\).
Let us observe that \({\mathrm {St}}_{Q(I)\cup Q(bI)}(v){\setminus } {\mathrm {St}}_{ Q(bI)}(v)\) is isometric to one of the following sets:
An intuition of this last assertion can be obtained by looking at Fig. 6 where each colored point represents a set of \(2^{n-3}\) vertices of \(\partial Q(I)\) that have the same first three coordinates, and for every vertex v in that set the point’s color indicates which set \(A_i\) the set \({\mathrm {St}}_{Q(I)\cup Q(bI)}(v){\setminus } {\mathrm {St}}_{ Q(bI)}(v)\subset {\mathrm {St}}_{Q(I)}(v)\) is isometric to. In all cases,
Finally, by Remark 4,
\(\square \)
Definition 10
(self-dual strong Euler well-composedness) The cubical complex Q(I) canonically associated with an \(n\)D picture I is self-dual strongly Euler well-composed (s\(\overset{+}{\chi }\)WC) if both Q(I) and Q(bI) are \(\overset{+}{\chi }\)WC.
Lemma 4
If Q(I) is s\(\overset{+}{\chi }\)WC then, for any vertex v of \(\partial Q(I)\), the following equation is satisfied:
or, equivalently,
Proof
Let us assume that
that is,
Now, since
then, using Remark 4, we conclude that:
\(\square \)
Nevertheless, the converse is not true.
Lemma 5
The fact that \(\chi \big ({\mathrm {St}}_{\partial Q(I)}(v)\big )=(-1)^{n-1}\) for any vertex \(v\in \partial Q(I)\) does not imply that Q(I) is \(\chi \)WC nor that I is DWC.
Proof
Case (b) of Fig. 4 is a simple counterexample. In that case, we have that \(\chi \big ({\mathrm {St}}_{\partial Q(I)}(v)\big )=(-1)^{n-1}\) but \(\chi \big ({\mathrm {St}}_{Q(I)}(v)\big )=-1 \ne 0\). Besides, case (b) of Fig. 4 is not DWC.
In the next section, we will prove our main result, that is, \(\overset{+}{\chi }\)WCness implies DWCness in any dimension \(n\ge 2\) although the converse is not true when \(n\ge 4\). Therefore, in principle, we do not need the concept of self-dual \(\overset{+}{\chi }\)WCness for our purpose. We end this section with the open question of whether self-dual strong Euler well-composedness is in fact equivalent to strong Euler well-composedness.
4 Strong Euler well-composedness implies digital well-composedness
Let us now see one of the two main results of the paper, stating that \(\overset{+}{\chi }\)WCness implies DWCness for any \(n\)D picture with \(n\ge 2\).
Theorem 1
Strong Euler well-composedness implies digital well-composedness in \(n\)D for \(n\ge 2\).
Proof
Let us prove that not DWCness implies not \(\overset{+}{\chi }\)WCness. Let \(I=({\mathbb {Z}} ^n,F_I)\) be an \(n\)D picture with \(n\ge 2\), and let k be an integer in \(\llbracket 0,n-2 \rrbracket \). Let \(\{p,p'\}\) be two antagonists in an \((n-k)\)-block B that yields a critical configuration for I.
Let us assume, first, that \(F_I \cap B = \{p,p'\}\), that is, it is a critical configuration. Then \(\frac{p+p'}{2}\) encodes a k-cell \(\sigma \) in \(\partial Q(I)\). Let us prove that \(\sigma \) is a \(\chi \)-critical cell for Q(I), that is, let us prove that \(\chi \big (\mathrm {Lk} _{Q(I)}(\sigma )\big )\ne 1\). First, observe that \(\mathrm {Lk} _{Q(I)}(\sigma )=L(p)\sqcup L(p')\) where, for \(q=p,p'\),
Now, since \(\chi (L(p))=\chi (L(p'))\), then
and then \(\sigma \) is \(\chi \)-critical for Q(I). In the other case, where \(B{\setminus } F_I=\{p,p'\}\), when \(\sigma \) is the k-cell centered at \(\frac{p+p'}{2}\), the set \({\mathrm {St}}_{Q(I)\cup Q(bI)}(\sigma ){\setminus } {\mathrm {St}}_{Q(I)}(\sigma )\) consists just of the two n-cells centered at p and \(p'\). Hence, \(\chi \big ({\mathrm {St}}_{Q(I)\cup Q(bI)}(\sigma ){\setminus } {\mathrm {St}}_{Q(I)}(\sigma )\big )=2(-1)^n\) and, by Remark 4,
so \(\chi \big ({\mathrm {St}}_{Q(I)}(\sigma )\big )=(-1)^{n+1}\ne 0\) and then \(\sigma \) is \(\chi \)-critical for Q(I). \(\square \)
5 Digital well-composedness does not imply (strong) Euler well-composedness
Let us see next, an example of an \(n\)D picture (\(n\ge 4\)) that is digital well-composed but not Euler well-composed, showing that DWCness does not imply \(\chi \)WCness and, therefore, DWCness does not imply \(\overset{+}{\chi }\)WCness.
Theorem 2
DWCness does not imply \(\chi \)WCness for any dimension \(n\ge 4\).
Proof
Let us fix \(n\ge 4\). We will give an example of an \(n\)D picture \(I_n=({\mathbb {Z}} ^n,F_{I_n})\) (see Fig. 7) such that \(I_n\) is DWC but \(Q(I_n)\) is not \(\chi \)WC. Let
To prove that \(I_n\) is DWC we only have to check that it does not contain any critical configuration. This has been checked in Boutry et al. (2020a) when \(n=4\) and the same reasoning can be extended to \(n\)D for \(n>4\).
Now, observe that the set of n-cubes of \(Q(I_n)\) encoded by \(F_{I_n}\) are incident to the vertex \(v=\left( \frac{1}{2}\right) ^n\in \partial Q(I)\). Then, to prove that \(Q(I_n)\) is not \(\chi \)WC, it is enough to check that \(\chi \big ( {\mathrm {St}}_{Q(I_n)} (v)\big )\ne 0\).
Let us see that the counterexample works in 4D. In that case, \(v=(\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})\) and the hypercubes in \({\mathrm {St}}_{Q(I_4)} (v)\) are encoded by the points (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 0) and (1, 0, 0, 0). Then, it is easy to check that \(\chi \big ({\mathrm {St}}_{Q(I_4)} (v)\big )=1-8+24-24+8=1\ne 0\), so \(Q(I_4)\) is not \(\chi \)WC. Another way to see that Theorem 2 holds when \(n = 4\) is that \({\mathrm {St}}_{Q(I_4)\cup Q(bI_4)} (v){\setminus } {\mathrm {St}}_{Q(I_4)} (v)=A\sqcup B\) where A is composed by the eight 3-cells centered at the barycenters of the eight edges that joint two gray points of Fig. 7 and B is composed by the eight 4-cells centered at the eight grey points. Then,
and hence, by Remark 4,
Consider the general case \(n>4\). Let \(d\in \llbracket 0,n \rrbracket \). Let us denote by \(a_{(d,n)}\) the number of d-cells incident to v in the \(n\)D cubical complex \(Q(I_n)\). Then,
-
\(a_{(0,n)}=1\),
-
\(a_{(d,n)}=2 a_{(d-1,n-1)}+a_{(d,n-1)}\) for \(d\in \llbracket 1,n-1 \rrbracket \) because a d-cell in \(Q(I_n)\) is constructed by adding an extra coordinate of 0 or 1 at the end to the list of coordinates of a point encoding a \((d-1)\)-cell in \(Q(I_{n-1})\) or adding the coordinate \(\frac{1}{2}\) at the end of the list of coordinates of a point encoding a d-cell in \(Q(I_{n-1})\),
-
\(a_{(n,n)}= 2a_{(n-1,n-1)}\).
Therefore,
Since \(\chi \big ({\mathrm {St}}_{Q(I_4)} (v)\big )=1\) then
So, \(Q(I_n)\) is not \(\chi \)WC. \(\square \)
Corollary 1
DWCness does not imply \(\overset{+}{\chi }\)WCness for any dimension \(n\ge 4\).
We finish this section with a table summarising the main results obtained so far regarding the concepts of DWCness and \(\overset{+}{\chi }\)WCness:
\(n=2,3\) | DWCness \(\longleftrightarrow \) \(\overset{+}{\chi }\)WCness |
\(n\ge 4\) | DWCness \(\begin{array}{l}\;\;\nrightarrow \\ \longleftarrow \end{array}\) \(\overset{+}{\chi }\)WCness |
6 Conclusions and future works
In this paper, we have provided a new flavour of well-composedness, called strong Euler well-composedness, that is more restrictive than the definition of Euler well-composedness given in Boutry et al. (2020a). We have proven two fundamental properties: first, strong Euler well-composedness implies digital well-composedness in any dimension \(n \ge 2\); second, the converse is not true: digital well-composedness does not imply strong Euler well-composedness as soon as we are in dimension \(n \ge 4\).
As a future work, we plan to prove that the definition of \(\overset{+}{\chi }\)WCness provided in this paper is robust to cubical barycentric subdivisions. Observe that a cubical barycentric subdivision of Q(I) is the \(n\)D cubical complex canonically associated with the linear interpolation of the \(n\)D picture I in all the possible directions \(e^i\), being \(\{e^1,\dots ,e^n\}\) the canonical basis of \({\mathbb {Z}} ^n\). This is another reason why we believe that it is a better choice to define well-composedness based on \(\chi \)-critical cells and not only on \(\chi \)-critical vertices as it was done in Boutry et al. (2020a).
We also plan to prove that if we apply the reparation method given in Gonzalez-Diaz et al. (2015, 2017), Boutry et al. (2019) to any \(\chi \)-critical cell, then \(P_S(I)\) (i.e., the simplicial subdivision of the “repaired complex” P(I)) is \(\overset{+}{\chi }\)WC, going a step forward to our ultimate goal that is to prove that P(I) is a CWC regular cell complex.
Data availability
The datasets generated during the current study are available in the github repository, https://github.com/Cimagroup/Strong-Euler-Well-Composed.
Notes
Two topological spaces are homeomorphic if there exists a biyective bicontinuous function between them.
The \(L^1\)-norm of a vector \(\alpha =(\alpha _1,\dots ,\alpha _n)\) is \(||\alpha ||_1=\sum _{i\in \llbracket 1,n \rrbracket }|\alpha _i|\).
Observe that \(\sigma \in \mathrm {Cl}\,( \sigma )\) since \(\sigma \) is considered to be a coface of itself.
Observe that \(\sigma \in {\mathrm {St}}_Q ( \sigma )\) since \(\sigma \) is considered to be a face of itself.
A topological space is contractible if it is homotopy equivalent to a point (Hatcher 2002, p. 2).
References
Boutry N, Géraud T, Najman L (2015) How to make \(n\)D images well-composed without interpolation. In: 2015 IEEE international conference on image processing (ICIP). IEEE, pp 2149–2153
Boutry N, Géraud T, Najman L (2015) How to make \(n\)D functions digitally well-composed in a self-dual way. In: International symposium on mathematical morphology and its applications to signal and image processing, lecture notes in computer science, vol 9082. Springer, pp 561–572
Boutry N, Géraud T, Najman L (2018) A tutorial on well-composedness. J Math Imaging Vis 60(3):443–478
Boutry N, Gonzalez-Diaz R, Jimenez MJ (2019) Weakly well-composed cell complexes over \(n\)D pictures. Inf Sci 499:62–83
Boutry N, Gonzalez-Diaz R, Jimenez MJ, Paluzo-Hildago E (2020) Euler well-composedness. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16–18, 2020, lecture notes in computer science, vol 12148. Springer, pp 3–19
Boutry N, Gonzalez-Diaz R, Najman L, Géraud T (2020) A 4d counter-example showing that DWCness does not imply CWCness in \(n\)D. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16–18, 2020, lecture notes in computer science, vol 12148. Springer, pp 73–87
Boutry N, Najman L, Géraud T (2020) Equivalence between digital well-composedness and well-composedness in the sense of Alexandrov on n-d cubical grids. J Math Imaging Vis 62:1285–1333
Edelsbrunner H, Harer J (2010) Computational topology: an introduction. American Mathematical Society, Providence
Géraud T, Carlinet E, Crozet S, Najman L (2013) A quasi-linear algorithm to compute the tree of shapes of \(n\)D images. In: International symposium on mathematical morphology and its applications to signal and image processing. Springer, pp 98–110
Gonzalez-Diaz R, Jimenez MJ, Medrano B (2015) 3D well-composed polyhedral complexes. Discrete Appl Math 183:59–77
Gonzalez-Diaz R, Jimenez MJ, Medrano B (2017) Efficiently storing well-composed polyhedral complexes computed over 3D binary images. J Math Imaging Vis 59(1):106–122
Hatcher A (2002) Algebraic topology. Cambridge University Press, Cambridge
Lachaud JO, Montanvert A (2000) Continuous analogs of digital boundaries: a topological approach to iso-surfaces. Graph Models 62(3):129–164
Latecki LJ (1997) 3D well-composed pictures. Graph Models Image Process 59(3):164–172
Latecki LJ (1998) Discrete representation of spatial objects in computer vision. Kluwer Academic, Dordrecht
Latecki L, Eckhardt U, Rosenfeld A (1995) Well-composed sets. CVIU 61(1):70–83
Marchadier J, Arquès D, Michelin S (2004) Thinning grayscale well-composed images. Pattern Recognit Lett 25(5):581–590
Siqueira M, Latecki LJ, Gallier J (2005) Making 3d binary digital images well-composed. In: SPIE, vision geometry XIII, vol 5675. International Society for Optics and Photonics, pp 150–164
Siqueira M, Latecki L, Tustison N, Gallier J, Gee J (2008) Topological repairing of \(3\)D digital images. J Math Imaging Vis 30:249–274
Stelldinger P, Latecki LJ (2006) 3D object digitization: majority interpolation and marching cubes. In: 18th international conference on pattern recognition, vol 2. IEEE, pp 1173–1176
Acknowledgements
We are really grateful to the reviewers for their suggestions and comments.
Funding
Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Author names are listed in alphabetical order. This work has been partially supported by Grant PID2019- 107339GB-I00 funded by MCIN/AEI/10.13039/501100011033 and Grant P20_01145 funded by Agencia Andaluza del Conocimiento.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Boutry, N., Gonzalez-Diaz, R., Jimenez, MJ. et al. Strong Euler well-composedness. J Comb Optim 44, 3038–3055 (2022). https://doi.org/10.1007/s10878-021-00837-8
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-021-00837-8