Characterizing slope regions

Journal of Combinatorial Optimization https://doi.org/10.1007/s10878-021-00783-5 Characterizing slope regions Rocio Gonzalez-Diaz1·Darshan Batavia2·RocioM.Casablanca 1· Walter G. Kropatsch2 Accepted: 8 July 2021 © The Author(s) 2021, corrected publication 2021 Abstract This paper provides a theoretical characterization of monotonically connected image surface regions, called slope regions. The characterization is given by several topological properties described in terms of critical points relative to the region. We formally prove the necessary and sufficient conditions that a region needs to satisfy to be a slope region. We also provide a prototype of slope regions which is general and contains, as particular cases, the prototypes studied and published in previous conference papers. Keywords Slope regions ·Topological characterization ·Critical points ·Height maps ·Cellular decomposition ·Slope complex 1 Introduction A digital image can be visualized as a 2.5D continuous surface by defining a continuous height (intensity) map h:R2→R. The set of points in the surface with same height are called level sets (Osher and Fedkiw 2003). The critical sets (local minima, local maxima and saddles) of the surface can be just points but, in general, they are connected level sets. Intuitively, preserving critical sets and their connectivity will preserve the structure of the space because, extrema (i.e., local minima and local maxima) are surrounded by closed level curves if not artificially interrupted by the boundary of the BRocio Gonzalez-Diaz [email protected] Darshan Batavia [email protected] Rocio M. Casablanca [email protected] Walter G. Kropatsch [email protected] 1Department of Applied Math I, University of Seville, Seville, Spain 2Pattern Recognition and Image Processing Group 193/03, TU Wien, Vienna, Austria 123 Journal of Combinatorial Optimization data. Level curves intersect exclusively at saddles. In terms of earth topography, the configuration of critical points connected by monotonic curves in the surface were discussed a long time ago in Cayley (1859), Maxwell (1870). The monotonic curves delineate surface patches, called slope regions, with the property that every pair of points inside such a patch can be connected by a monotonic curve. This way, slope regions may be seen as filling the space between the critical sets of the surface (see Kropatsch 2019b). A planar triangle is a simple example of a slope region and any triangular mesh partitions the surface into a set of slope regions. The space between critical sets of the surface can always be partitioned into slope regions. The corresponding decomposition of the surface with minimal number of slope regions preserving critical sets is called a minimal slope complex. In general, this partition is not unique and allows certain task and data-specific adaptations but every element of such a partition satisfies the requirements of the general prototype of slope regions given in this paper. First, such general prototype allows to check if a region-based partition (e.g. an image segmentation) is a valid slope complex (i.e., a cell decomposition of the surface where each 2-cell is a slope region) as we will see later. Second, it opens the door to set the grounds to construct a “slope grammar” describing all possible combinations of valid slope regions. Regarding related works, the concepts of integral lines and Morse-Smale (MS) complexes were previously defined in Edelsbrunner et al. (2003b), Edelsbrunner et al. (2003a) and Edelsbrunner and Harer (2009), with the intention to build a hierarchy of increasingly coarse MS complexes. In that case, the decomposition is made into regions of uniform flow using integral lines. Specifically, MS complexes are built using a real-valued smooth map over the surface, with non-degenerated critical points. We will see later that the concept of integral line has great similarity to the monotonic curves of our approach although monotonic curves are geometrically less constrained. Many efficient algorithms can be found in the literature to compute consistent MS complexes. For example, in Gyulassy et al. (2014), the authors presented an efficient algorithm to compute consistent MS complexes using a divide-and-conquer strategy for dealing with large data. In Sorgente et al. (2018), the authors introduced a novel algorithm using discrete gradient flow paths to decompose a 3D object into an atlas of disk-like charts. In Comic et al. (2010), the authors computed maximal cells of the ascending and descending Morse complexes through a watershed approach. Nevertheless, since the computation of slope complexes is not the goal of the paper, we only introduce here a first step to it and the comparison of slope complexes and MS-like complexes is left as future work. With respect to other closely related technique such as Reeb graphs and complexes, in Marzantowicz et al. (2015), the authors characterized the Reeb graphs for functions fon manifolds Mwith concrete properties. For example, if Mhas finite fundamental group, then the Reeb graph of fis a tree. Critical sets can appear in many different configurations. A catalogue of different configurations of the critical points and slope districts was discussed in Lee (1984). The author also provided visualizations of the “slope districts” (a simpler version of slope regions) using Critical Point Configuration Graphs constructed using peaks (local maxima), dales (local minima) and passes (saddle points). In Rosin (1995), the 123 Journal of Combinatorial Optimization authors described a technique for extracting the slope districts from smooth discrete images and produce a hierarchical description in terms of linked slope districts. Related conference publications published: In Kropatsch (2019a), given a 2D continuous surface, not necessarily being piecewise linear or smooth, we defined slope regions as simply connected components such that any two points in them are connected by a monotonic path, where the intersection between them are allowed. We introduced the concept of slope complexes which are particular cases of 2-dimensional (2D) CW-complexes in which each 2-cell is a slope region. From this start point, we proposed a prototype of slope regions with the constraint that their outer boundary is composed by exactly two monotonic curves. We explored how to create and reduce slope complexes, by describing a basic process to reduce the number of slope regions without affecting the bounding critical points, obtaining a simplified slope complex. The computation of slope complexes was made in Kropatsch (2019a) only in the case in which the height map is piecewise linear and slope regions are planar triangles obtained from a triangulation of a 2D continuous surface. In Cerman et al. (2016), we produced superpixel hierarchies (combinatorial graph pyramids) that are multiresolution segmentations of the given picture and where critical points are preserved along the pyramid. In Kropatsch (2019b), we approached the study of slope complexes from the point of view of the neighborhood graph of a digital picture. Its vertices can be interpolated to form a 2-manifold with critical points, where slopes and plateaus being the ones recognized by local binary patterns (LBPs). Neighborhood graph produces a cell decomposition of the manifold, where each 2-cell is a slope region. In Kropatsch (2019b), we showed that each level of the pyramid produces a slope complex. Slope complexes in different levels of the pyramid are always homeomorphic to disks. We also addressed the question whether there is a minimal number of slope regions that completely cover the 2.5D surface between a given set of critical points. We also provided a formula to count the minimum number of slope regions required to represent the surface, given the number of critical points. In Batavia et al. (2019b), we used the representation of a surface by a neighborhood (primal) graph and its dual, where the modifications in the primal graph are reflected in the dual. The vertices of such graphs are categorized into maximum, minimum, slope or saddle depending on the orientation of their incident edges. We introduced the orientation of the edges in the dual graph and showed that the LBP category of the dual vertex is consistent with the corresponding face in the primal graph, by providing an interpretation in the image context. Besides, we introduced a technique to orient monotonic paths with level curves in the primal graph and provided necessary and sufficient conditions for both primal and dual graph to merge two slope regions. In Batavia et al. (2019a), we introduced a second prototype with the aim of characterizing slope regions with the constraint that the outer boundary is a level curve. We provided necessary conditions for their existence and we showed that a well-composed 2D digital image can be partitioned into slope regions categorized into one of the two previously described prototypes. Finally, in Batavia et al. (2021), we proposed a Topology-preserving Irregular Image Pyramid (TIIP) algorithm including a hierarchical method to build an irregular image pyramid that preserves slopes regions. The algorithm operates on combinatorial maps which implicitly encode the structure of the image on the higher level of the pyramid with a compact representation. The use of combinatorial maps supports parallel pro- 123 Journal of Combinatorial Optimization Fig. 1 Example of an image Aand its reconstruction Fusing the TIIP algorithm introduced in Batavia et al. (2021). Observe that the reconstruction Dof the original background Blost information while the original fine details Care preserved in Eafter the reconstruction cessing with time complexity of O(log(d)), where dis the diameter (in pixels) of the largest region after the simplification is made. With the TIIP algorithm, we were able to reconstruct images using as few as 30% of the color values and the information stored on top of the pyramid, although preserving fine details including the texture of the image. An example of an original and reconstructed image is showed in Fig. 1. In this paper, necessary and sufficient conditions for a region to be slope are formally provided for the first time, obtaining a simple and complete characterization of slope regions and, as a consequence, a prototype for slope regions, which is general and complete. We also prove that prototypes described in previous papers are particular cases of our general prototype described here. Each result (Theorem, Lemma, Corollary) presented in this paper without a previous reference is original and new. From the application point of view, Cerman et al. (2016) provided an algorithm where the neighborhood graphs were used to represent a digital image. By a sequence of edge contraction and edge removal operations, we reduced the graph and stack them to form an irregular graph pyramid. Later, irregular graph pyramids were used for multi-resolution image segmentation. Similar approaches were used in Wei et al. (2018) for multi-resolution image segmentation using a super pixel hierarchy. The characterization of slope regions presented in this paper opens a door to design robust algorithms to compute slope regions that could be used for image processing tasks such as geometric modeling, or filtering on segments with particular topological properties. The paper is organized as follows. Section 2is devoted to present the main definitions and basic tools that will be used throughout this paper. We also introduce the concept of monotonic curves, which will be the key point and reference of our work. Section 3contains the theoretical results of the paper. We introduce the notion of slope regions, for which we use the concept of monotonic curves, and prove preliminary results which will lead us to obtain a complete characterization of the slope regions at the end of the section. In Sect. 4, we approach the study of cell decomposition through the use of slope regions and prove that there is a natural way to move from a slope region to a 2-cell. 123 Journal of Combinatorial Optimization Fig. 2 Level curves as part of a monotonic curve Section 5focuses on the general prototype of slope regions presented here for the first time, containing the prototypes published in previous conference papers as particular cases, with the aim of giving a combinatorial representation for such regions. Finally, Sect. 6concludes the paper. 2 Preliminaries Let us introduce several definitions based on a map h:R2→ Rwith the only requirement of hbeing continuous but not necessarily smooth. Acurve π:[0,1]→R2is a continuous map. It is simple if π|(0,1)is one-to-one. Otherwise, it is folded.Itismonotonic if there is no interval [a,b]⊂(0,1)being a 1-extremum. Let im πbe the set {p∈R2:p=π(t)for some t∈[0,1]}. Definition 1 (1-extrema)Letπ:[0,1]→R2be a curve and let [a,b]⊂[0,1]. Suppose that h(π(t)) =cfor some c∈Rand for all t∈[a,b]. Then, [a,b]is a 1- minimum (1-min) if there exists >0 such that c<h(π(s)) for all sin a neighborhood ((a−, b+)\[a,b])∩[0,1]. Similarly, [a,b]is a 1-maximum (1-max) if c>h(π(s)) for all s∈((a−, b+) \[a,b])∩[0,1]. Finally, [a,b]is a 1-extremum if it is a 1-max or a 1-min. If a=b, then [a,a]is a 1-extremum point. Definition 2 (level curve) A level curve γ:[0,1]→R2is a curve satisfying that there exists a constant c∈Rsuch that h(γ (t)) =c, for all t∈[0,1]. Observe that a level curve is a particular case of monotonic curve. A level curve can also be part of a monotonic curve. Observe that all curves considered in this paper (including level curves) are connected. Remark 1 A strictly monotonic curve, excluding level curves, is either increasing or decreasing. It is always bounded by a 1-max and a 1-min. This allows us to consider monotonic curves with a natural orientation. In our illustrations: an arrow from point a to point brepresents a monotonic curve with endpoints aand bsuch that h(a)>h(b). When the curve is exactly a level curve, no arrow is pictured. See Fig. 2. An example of monotonic curve is shown in Fig. 2. The intervals [0,x]and [y,1] are level-curve 1-extrema (1-max and 1-min respectively). Observe that no closed sub-interval of (0,1)can be a 1-extremum. 123 Journal of Combinatorial Optimization Adisk D of radius r>0 centered at a point p∈R2is the set D={q∈R2such that d(p,q)≤r}.The interior of Dis int(D)={q∈R2such that d(p,q)<r}and the boundary of Dis ∂D={q∈R2such that d(p,q)=r}. AsetX⊆R2is disconnected if there exist two open sets U1⊆R2and U2⊆R2 such that X1⊆U1,X2⊆U2,X=X1∪X2and U1∩U2=∅. Otherwise, Xis connected. The set Xis bounded if it is contained in a disk. Ahole of Xis a bounded connected component of R2\X.ThesetXis monotonically connected if it is connected and for any two different points pand qof Xthere exists a monotonic curve π:[0,1]→X, with π(0)=pand π(1)=q.Thetopological interior of X, denoted as topint(X), is defined as the largest open subset of X.The frontier of X, denoted as fr(X), is defined as X\topint(X). Definition 3 (plateau)Aplateau Pcis a bounded closed connected subset of R2 satisfying that h(p)=cfor all p∈Pc. Observe that a plateau Pccan be, for example, just a point in R2, a level curve or even the union of a set of level curves. A plateau may also contain holes. Definition 4 (categories of plateaus)LetPcbe a plateau. –Pcis a 2-minimum (2-min) if there exists a monotonically connected open set U⊆R2satisfying that Pc⊂Uand h(q)>cfor every q∈U\Pc. –Pcis a 2-maximum (2-max) if there exists a monotonically connected open set U⊆R2satisfying that Pc⊂Uand h(q)<cfor every q∈U\Pc. –Pcis a 2-saddle if for all open set U⊆R2satisfying that Pc⊂Uthen Uis not monotonically connected. A2-extremum is either a 2-min or a 2-max. A 2-critical plateau is either a 2-extremum or a 2-saddle. Let us recall that a homeomorphism is a bicontinuous bijective map. Now, let us introduce the concept of region. Definition 5 (region)LetRbe a subset of R2and let Dbe a disk. The subset Ris a region if it can be obtained as the image of a continuous surjective map f:D→ R(that is, R=im f) satisfying that f|∂Dis a continuous curve and f|int(D)is a homeomorphism. Observe that the same region Rcould be obtained using different continuous surjective maps f:D→R. Definition 6 (boundary, outer boundary and interior of a region)LetRbearegion obtained as the image of a continuous surjective map f:D→R. The set of points in im f|int(D), denoted as intf(R), is called the interior of R. Similarly, the set of points in im f|∂D, denoted by ∂fR, is called the boundary of R. See Fig. 3. The outer boundary of Ris the image of a simple curve π:[0,1]→∂fR, which divides the plane R2in two connected components, one, containing R, bounded by im πand one unbounded. 123 Journal of Combinatorial Optimization Fig. 3 A pictorial example of a continuous surjective map f from a disk Dto a region R.a The map frestricted to the boundary of D.bThe map f restricted to the interior of D (a) ∂R (b) int(R)(c) fr(R)(d) topint(R) Fig. 4 The boundary, the interior, the frontier, and the topological interior of a region R For the sake of simplicity, the interior and boundary of Rwill be denoted, respectively, as int(R)and ∂R, when it is not considered relevant to explicitly mention the function f. Besides, as we will see later, folded curves are needed for connecting the holes to the outer boundary. Definition 7 (plateau region) A region being a plateau is called a plateau region. Remark 2 Let Rbe a region. Then, int(R)lies in topint(R)and fr(R)lies in ∂R. Besides, int(R)is homeomorphic to a disk whereas topint(R)does not need to be. Finally, ∂Ris necessarily connected, whereas fr(R)is not. See Fig. 4. Definition 8 (categories of plateaus relative to a region)LetRbe a region and Pc⊂R a plateau then: –Pcis an R-minimum (R-min) if there exists an open set U⊆R2satisfying that U∩Ris monotonically connected, Pc⊂U∩Rand h(q)>cfor every q∈ U∩R\Pc. –Pcis an R-maximum (R-max) if there exists an open set U⊆R2satisfying that U∩Ris monotonically connected, Pc⊂U∩Rand h(q)<cfor every q∈U∩R\Pc.AnR-extremum is either an R-min or an R-max. Observe that an R-extremum that lies in the topological interior of Ris, in fact, a 2-extremum. Conversely, a 2-extremum lying in the frontier of Ris an R-extremum. 3 Slope regions In this section we formally introduce the concept of slope region and study several preliminary results required to prove the necessary and sufficient conditions that any 123 Journal of Combinatorial Optimization slope region needs to satisfy. As a main result, we provide and prove a complete and general characterization of slope regions. Definition 9 (slope region)Aslope region S is a monotonically connected region. Notice that a plateau region is a trivial and particular case of slope regions, due to all points in the plateau region are connected by level curves, which are monotonic curves. 3.1 Necessary conditions of slope regions Let us study properties that any slope region must satisfy. Theorem 1 If S is a slope region then S does not contain any 2-saddle in its topological interior and it is either a plateau region or it is a region with maximally one R-max and one R-min. Proof By definition of slope regions there exists a monotonic curve between any two points in S, which directly implies that Scannot contain 2-saddles in its topological interior. Since Sis not a plateau and it is closed and bounded, then Scontains, at least, one R-max and one R-min. Neither two R-maxima nor two R-minima can be connected by a monotonic curve in S, then Scannot contain neither two or more R-maxima, nor two or more R-minima.  Lemma 1 The boundary of a slope region S is always either a level curve or it contains exactly one 1-max and one 1-min. Proof If for all p∈∂Swe have that h(p)=c,forsomec∈R, then the proof is complete. Otherwise, ∂Sis a continuous non-level curve. Then, it has at least one 1-max Iand one 1-min J(recall that Iand Jcould be closed intervals or just points). Let us prove that ∂Shas exactly one 1-max and one 1-min. By contradiction, suppose that ∂Shas, for instance, another 1-max, denoted by I. Consider two points p∈I and p∈I. Assume that h(p)≤h(p). Since Sis a slope region then there exists a monotonic curve π:[0,1]→Sjoining pand p. Now, since Iis a 1-max, p∈Iwith h(p)≤h(p)and πis monotonic then, necessarily, there exist s,s∈[0,1]such that π(s), π(s)∈∂S,h(p)≤h(π(s)) ≤ h(π(s)) ≤h(p)and π((s,s)) lies in int(S). Therefore, π|[s,s]divides Sin, at least, two disjoint sets S1and S2, and hence, ∂Scan be divided in two different continuous curves π1:[0,1]→∂Sand π2:[0,1]→∂S, one lying in S1and the other lying in S2. Suppose that the 1-min Jlies in π1. Then, there exists another one 1- min Jlying in π2since π2is a continuous curve. Consider q∈Jand q∈J. Assume that h(q)≤h(q). Then, there exists a monotonic curve ˆπ:[0,1]→S between qand q. By similar reasoning as before, ˆπcrosses the interior of Sand, then, there exists a point r∈int(S)such that r∈im π∩im ˆπ. For such point r,wehave h(q)≤h(r)≤h(q)<h(p)≤h(r)≤h(p)which is a contradiction.  123 Journal of Combinatorial Optimization 3.2 Sufficient conditions of slope regions Let us prove that sufficient conditions for a region Rto be a slope region are: (a) Rdoes not contain any 2-saddle in its topological interior, (b) Ris either a plateau region or it contains one R-max and one R-min, and (c) ∂Ris either a level curve or it contains one 1-max and one 1-min. From now on, let cbe a value between the lowest and the highest h-values for the given continuous map h.LetLc={p∈Rsuch that h(p)=c}, being Ragiven region. The level set1Lccould be non-connected, so it might not be a plateau. Lemma 2 Let R be a region with no 2-saddle in its topological interior, and with, exactly, one R-max and one R-min. Let X =R\Lc. Then X =∅is composed by at most two connected components. Proof First, Ris not a plateau then X=∅.Let ¯ Xbe the closure2of X. Then, ¯ Xis a subset of R, since Ris closed. Moreover, since R=X∪Lcthen ¯ X\Xis a subset of Lc. By contradiction, suppose that Xis composed by more than two connected components, for instance, three connected components X1,X2and X3.Let ¯ Xibe the closure of Xifor i=1,2,3. Since ¯ Xi\Xiis a subset of Lcand ¯ XiLc, for i=1,2,3, then ¯ Xicannot be a plateau. An R-max (resp. R-min) relative to region ¯ Xiwill be denoted by ¯ Xi-max (resp. ¯ Xi-min), for i=1,2,3. Now, since each ¯ Xiis closed and bounded, then there is at least one ¯ Xi-min and one ¯ Xi-max, for i=1,2,3. Without loss of generality, suppose that an ¯ X1-max coincides with the R-max. Then the rest of the ¯ Xi-maxima cannot lie in Xi, for any i=1,2,3, since R only contains one R-max. Consequently, the rest of the ¯ Xi-maxima lie in ¯ Xi\Xi⊆Lc, for i=1,2,3. Similarly, the R-min can coincide with an ¯ X1-min, an ¯ X2-min or an ¯ X3-min. Without loss of generality, suppose that the R-min coincides with an ¯ X2-min. Then, by the same reason as above, the rest of the ¯ Xi-minima lie in Lc,fori=1,2,3. We conclude that one ¯ X3-max and one ¯ X3-min lie in Lcand no ¯ X3-extremum lies in X3. Then, necessarily, ¯ X3⊆Lc, which is a contradiction.  The previous lemma is used to prove that a level set contained in a region with specific constraints is always connected. Lemma 3 Let R be a region with exactly one R-max, one R-min and without any 2- saddle in its topological interior. Assume that the boundary of R, ∂R, is either a level curve or it contains exactly one 1-max and one 1-min. Then Lcis connected, where Lc={p∈R such that h(p)=c}. Proof Let X=R\Lc. By Lemma 2, we know that Xis composed by at most two connected components. First, observe that both, the R-max and the R-min, cannot belong to a same connected component of X, named Y, otherwise, there would exist a curve in Ybetween the R-max and the R-min and a point pin the curve satisfying that h(p)=cwhich is not possible since X∩Lc=∅. Now, the next two cases can be distinguished: 1Properties of level sets can be found in Sethian (1999). 2The closure of a set X⊆R2, denoted by ¯ X, is the smallest closed subset of R2containing X. 123 Journal of Combinatorial Optimization Fig. 7 A 2.5D mesh plot illustrating a “crater” and its prototype representation the same curve and, in that case, it must be a level curve. Otherwise, the resulting curve from the R-min to the R-max is not monotonic which is a necessary condition for the boundary of a slope region, as we proved in Sect. 3. The complete traversal along the boundary of the general prototype can be described as follows: (⊕,ˆa,h1,ˆ b,m1,e,m2,ˆ d,h4,ˆc,,ˇc,h3,ˇ d,m2,ˆg,p5,h5,p,h,p,h6,p5, ˆ f,m1,ˇ b,h2,ˇa,⊕). The paths responsible for connecting the elements ⊕,and holes to the outer boundary are a subset of the complete boundary of the slope region, and they are intuitively called as “the folding of the boundary”. “Folding” and“unfolding” has also been used in Edelsbrunner et al. (2003b) for treating degenerated saddle points. The general prototype presented in Fig. 5is a generalized version of Prototype 1 (“inclined slope region”) mentioned in Kropatsch (2019a). An example of a 2.5D mesh plot and its graphical representation corresponding to Prototype 1 is given in Fig. 6. Observe that there can be many holes (as mentioned above) inside the slope region and that the outer boundary of the region is surrounded by exactly two monotonic paths connecting the 1-max m1and the 1-min m2. Prototype 2 (“horizontal slope region”) mentioned in Batavia et al. (2019a) can also be obtained from the general prototype presented in Fig. 5, by replacing the monotonic paths in the outer boundary by paths representing level curves. In the general prototype, if the R-max ⊕(resp. R-min ) is absent, vertex m1(resp. m2) will become the R-max (resp. R-min). Besides, the absence of the R-max and the R-min together with the outer boundary of Rbeing a level curve, will result in a plateau region. To end up this part of the section, observe that the “crater” in Fig. 7is an example of a slope region that is not a MS manifold. The R-max and the R-min in Fig. 7are represented by one vertex and a closed level path attached. Intuitively, the R-max surrounds the crater and the R-min surrounds the foothill and coincides with the outer boundary of the region. Besides, the R-max and the R-min are connected by two monotonic paths in its prototype representation, being the complete boundary of the region described by the closed path (,b,ˆa,⊕,h,ˇa,). 5.1 Slopes in an image landscape Let us now consider the digital image pictured in Fig. 8and a 2.5D surface obtained by defining a continuous “height” (intensity) map h:R2→Rby interpolating the gray 123 Journal of Combinatorial Optimization Fig. 8 aA digital image and, with the local minima, local maxima and saddle plateaus surrounded, respectively, by blue, red and green closed curves. b–dDifferent slope-region decomposition of the same image level of the pixels. In the picture, the local minima, local maxima and saddle plateaus are surrounded, respectively, by a blue, red and green closed curve. The following examples of slope-region decomposition show both plateau regions and non-plateau slope regions Sconnecting R-max to R-min with folded boundaries forming monotonic paths. As per Corollary 1, a non-plateau slope region Scontains exactly one R-max and one R-min. Therefore, the minimum number of slope regions required to decompose the image is three (see, for example, Fig. 8b). Also for any sloperegion decomposition, either the saddle plateau is one region of the decomposition, or the saddle plateau is divided into respective slope regions (as shown by dashed lines in Fig. 8d). The main advantage of slope decomposition over watershed or MS decomposition is the flexibility to choose the size of the slope region and the receptive field of the local extrema. Also, unlike MS decomposition algorithms, we allow holes inside the slope region. Depending on the constraints for optimization, following are a few examples of slope-region decompositions: – Figure 8b. No holes. – Figure 8c. A slope region as large as possible (the yellow slope region surrounding the whole image with holes which indeed are slope regions). – Figure 8d. The local maximum has larger receptive field. 123 Journal of Combinatorial Optimization 6 Conclusions and future work In this paper, we have provided a complete characterization of monotonically connected regions, so-called slope regions, in terms of their main topological elements, namely, their critical points and the critical points on their boundary. Moreover, a decomposition of a 2.5D surface in slope regions preserves the arrangements between critical points of the surface. We have also provided a general prototype of slope regions, in terms of graphs, that fulfills the characterization presented here. For future work, we plan to extend the theory of slope regions to slope volumes and slope manifolds embedded in R3to exploit the topological properties of 3D spaces. The work can very well be compared with the concept of dyads and dendrites mentioned in Bertrand (2013) and Bertrand (2014). We also plan to work on persistence measures which will be useful to eliminate the insignificant critical points. Besides, we plan to prove that MS complexes can be seen as particular cases of slopes complexes. Finally, Cerman et al. (2016) can be considered as a first step in the computation of slope complexes and we plan to continue this work in the very near future. Regarding future applications, with the complete characterization of slope regions at hand, we could compute minimal slope complexes (slope complexes with minimal number of slope regions preserving critical points) and these minimal slope complexes could be used for robust image classification tasks, for example. Besides, notice that any hill-climbing optimization (such as back-propagation in neural networks) inside a slope region reaches the 2-max (if contained in the interior of the slope region). Consequently, iterative optimization on a given surface converges whenever the starting point is inside the slope region having the global maximum, even if there are other local maxima in the surface. Besides, since a decomposition of a 2.5D surface into slope regions endows topological and structural properties, such decomposition could be used for applications such as segmentation, object recognition or geometric modeling. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work has been partially supported by Ministerio de Ciencia e Innovación - Agencia Estatal de Investigación/10.13039/501100011033 under project PID2019-107339GB-I00 and the University of Seville. Availability of data and materials The datasets generated and analysed during the current study are available from the corresponding author on reasonable request. Declarations Conflict of interest The authors declare that they have no conflict of interest. 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 123 Journal of Combinatorial Optimization 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/. References Batavia D, Hladuvka J, Kropatsch WG (2019a) Partitioning 2D images into prototypes of slope region. In: International conference on computer analysis of images and patterns, vol LNCS-11678. Springer, pp 363–374 Batavia D, Kropatsch WG, Gonzalez-Diaz R, Casblanca RM (2019b) Congratulations! dual graphs are now orientated! In: International conference on on graph based representations, vol LNCS-11510. Springer, pp 131–140 Batavia D, Gonzalez-Diaz R, Kropatsch WG (2021) Image = structure + few colors. In: IAPR joint international workshops on statistical techniques in pattern recognition and structural and syntactic pattern recognition (S+SSPR 2020) (to appear) Bertrand G (2013) New structures based on completions. In: International conference on discrete geometry for computer imagery, pp 83–94 Bertrand G (2014) Completions and simple homotopy. In: International conference on discrete geometry for computer imagery, pp 63–74 Cayley A (1859) On contour and slope lines. Lond Edinb Dublin Philos Mag J Sci 18(120):264–268 Cerman M, Janusch I, Gonzalez-Diaz R, Kropatsch WG (2016) Topology-based image segmentation using lbp pyramids. Mach Vis Appl 27(8):1161–1174 Comic L, De Floriani L, Iuricich F (2010) Building morphological representations for 2D and 3D scalar fields. In: Puppo E, Brogni A, Floriani LD (eds) Eurographics Italian chapter conference 2010, pp 103–110 Edelsbrunner H, Harer J (2009) The persistent Morse complex segmentation of a 3-manifold. In: 3D physiological human workshop, pp 36–50 Edelsbrunner H, Harer J, Natarajan V, Pascucci V (2003a) Morse-Smale complexes for piecewise linear 3-manifolds. In: 19th symposium on computational geometry, pp 361–370 Edelsbrunner H, Harer J, Zomorodian A (2003b) Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete Comput Geom 30(1):87–107 Gyulassy A, Günther D, Levine JA, Tierny J, Pascucci V (2014) Conforming Morse-Smale complexes. IEEE Trans Visual Comput Graph 20(12):2595–2603 Hatcher A (2000) Algebraic topology. Cambridge University Press, Cambridge Kropatsch WG, Casablanca RM, Batavia D, Gonzalez-Diaz R (2019a) Computing and reducing slope complexes. In: International conference on computational topology in image context, vol LNCS- 11382. Springer, pp 12–25 Kropatsch WG, Casablanca RM, Batavia D, Gonzalez-Diaz R (2019b) On the space between critical points. In: International conference on discrete geometry for computer imagery, vol LNCS-11414. Springer, pp 115–126 Lee RN (1984) Two-dimensional critical point configuration graphs. IEEE Trans Pattern Anal Mach Intell 4:442–450 Marzantowicz W, Silva N, Kaluba M (2015) On representation of the reeb graph as a sub-complex of manifold. Topol Methods Nonlinear Anal 45(1):287. https://doi.org/10.12775/tmna.2015.015 Maxwell JC (1870) On hills and dales. Lond Edinb Dublin Philos Mag J Sci 40(269):421–427 Osher SJ, Fedkiw R (2003) Level set methods and dynamic implicit surfaces. In: Applied mathematical sciences, vol 153. Springer, Berlin Rosin PL (1995) Early image representation by slope districts. J Vis Commun Image Represent 6(3):228– 243 Sethian J (1999) Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. Cambridge University Press, Cambridge Sorgente T, Biasotti S, Livesu M, Spagnuolo M (2018) Topology-driven shape chartification. Comput Aided Geom Des 65:13–28 Wei X, Yang Q, Gong Y, Ahuja N, Yang MH (2018) Superpixel hierarchy. IEEE Trans Image Process 27(10):4838–4849 123 Journal of Combinatorial Optimization Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123