A Walk Inside Slope Region
Hierarchy
DISSERTATION
submitted in partial fulfillment of the requirements for the degree of
Doktor der Technischen Wissenschaften
by
M. Tech. Darshan Batavia
Registration Number 11802315
to the Faculty of Informatics
at the TU Wien
Advisor: O.Univ.Prof. Dipl.Ing. Dr.techn. Walter Kropatsch
The dissertation has been reviewed by:
Prof. Luc Brun Asso. Prof. Benoît Gaüzère
Vienna, 23rd June, 2022
Darshan Batavia
Technische Universität Wien
A-1040 Wien Karlsplatz 13 Tel. +43-1-58801-0 www.tuwien.at

Erklärung zur Verfassung der
Arbeit
M. Tech. Darshan Batavia
Hiermit erkläre ich, dass ich diese Arbeit selbständig verfasst habe, dass ich die verwen-
deten Quellen und Hilfsmittel vollständig angegeben habe und dass ich die Stellen der
Arbeit – einschließlich Tabellen, Karten und Abbildungen –, die anderen Werken oder
dem Internet im Wortlaut oder dem Sinn nach entnommen sind, auf jeden Fall unter
Angabe der Quelle als Entlehnung kenntlich gemacht habe.
Wien, 23. Juni 2022
Darshan Batavia
iii

Acknowledgements
I would like to dedicate my thesis to my beloved grandfather Eng. Jeshtarambhai Batavia,
who is no longer with us, but continuously inspires me. He bestowed his life lessons on me
and made me understand the power of the 3D: Dedication, Devotion, and Determination
in our life.
I would like to express my sincere gratitude to my supervisor Prof. Walter Kropatsch for
his continuous support and guidance throughout my Ph.D. study and research. Thanks for
the endless patience, motivation, and contributions in brainstorming sessions that made
me a researcher, and presenter. Deep appreciation goes to my permanent collaborator
Rocio Gonzalez-Diaz. Discussions with her have always been very enthusiastic. She
remained as my first point of contact for multiple researches we published together.
This thesis might have taken longer without your pivotal contributions. I thank my
colleagues and PRIP members especially Aysylu Gabdulkhakova, Jiri Hladuvka, and
Rocio Moreno-Casablanca, for their encouragement, insightful comments, critiques, and
suggestions.
Last but not least, I would like to thank my parents Mr. Naresh Batavia and Mrs. Niyati
Batavia for their constant support and understanding from another part of the world.
Their sacrifice is commendable for letting their single child work abroad and hardly
spend one month every year with me. Special thanks to my partner Siddhida Kabara
for patience, understanding, continuous encouragement, and love especially during the
downtime of my research journey. I take the opportunity to thank my cousin Keval
Thakkar for his care and support during the start of this journey.
I also place on record, my sense of gratitude to all who, directly and indirectly, have lend
their helping hand in this journey.
v

Abstract
This cumulative thesis presents research from five selected publications in the field of
topology preservation in images using irregular graph pyramids. Preserving the structure
and the topology of data is a thorough research problem in the field of image analysis
and representation, with ample applications.
The thesis introduces a monotonically connected topological subspace called Slope region
from previous research. The theoretical contribution of this thesis focuses on the charac-
teristics and generalization of the slope regions. It enumerates the salient features of the
slope regions for its identification.
From the representation and modeling point of view, the core contribution consists of the
origination of the inner boundary (or the folded boundary) and the outer boundary. The
inner boundary of the slope region helps to incorporate the holes that are geometrically
encapsulated by the outer boundary of the slope region but is topologically excluded from
the interior of the slope region. This helps to model the slope region as homeomorphic
to a disc. The presence and modeling of holes marks as one of the important distinctions
between the proposed slope regions and the previously existing topological subspace.
The slope regions are generalized into two prototypes depending on the components of
the slope region and irrespective of the geometric features like the size and shape of the
regions.
From the implementing point of view, the thesis proposes an algorithm to build a hierarchy
of the slope region over the 4-neighbourhood Region Adjacency Graph (RAG) of an
image. Another core contribution of this thesis deals with the dual of the RAG, its
significance, and utilization in merging the adjacent slope regions. The slope region
hierarchy decomposes the image into slope regions while preserving its topology. The top
level of the hierarchy reveals the structure of the image that consists of the critical points
and the connections between them. The results from the implementation suggest that
an image is a combination of its structure and a few colors. The proposed hierarchical
algorithm has the computational complexity of O(log d).
Finally, the last goal of this thesis is to exploit the link between the proposed ingeniously
designed algorithm and machine learning. This goal is achieved by deriving an objective
function that simplifies a few of the many steps in the proposed algorithm and opens the
domain of learning an irregular image pyramid.
vii

Kurzfassung
Diese kumulative Dissertation präsentiert Forschungsergebnisse aus fünf ausgewählten
Veröffentlichungen auf dem Gebiet der Topologieerhaltung in Bildern unter Verwendung
unregelmäßiger Graphenpyramiden. Die Erhaltung der Struktur und der Topologie von
Daten ist ein grundlegendes Forschungsproblem auf dem Gebiet der Bildanalyse und
Repräsentation mit zahlreichen Anwendungen.
In dieser Arbeit wird ein monoton verbundener topologischer Unterraum, die so genann-
te slope-Region, aus früheren Forschungsarbeiten eingeführt. Der theoretische Beitrag
dieser Arbeit konzentriert sich auf die Eigenschaften und die Verallgemeinerung der
slope-Regionen. Es werden die hervorstechenden Merkmale der slope-Regionen für ihre
Identifizierung aufgezählt.
Aus der Sicht der Repräsentation und der Modellierung besteht der Kernbeitrag in der
Entstehung der inneren Grenze (oder der gefalteten Grenze) und der äußeren Grenze. Die
innere Begrenzung der slope-Region hilft dabei, die Löcher einzubeziehen, die geometrisch
von der äußeren Begrenzung der slope-Region eingeschlossen sind, aber topologisch vom
Inneren der slope-Region ausgenommen sind. Dies trägt dazu bei, die slope-Region als
homöomorph zu einer Scheibe zu modellieren. Das Vorhandensein und die Modellierung
von Löchern ist einer der wichtigsten Unterschiede zwischen den vorgeschlagenen slope-
Regionen und dem zuvor existierenden topologischen Unterraum.
Die slope-Regionen werden in zwei Prototypen verallgemeinert, abhängig von den Kom-
ponenten der slope-Region und unabhängig von den geometrischen Merkmalen wie Größe
und Form der Regionen.
Aus der Sicht der Implementierung schlägt die Arbeit einen Algorithmus vor, um eine
Hierarchie der slope-Regionen über Regions-Adjazenz-Graphen (RAG) eines Bildes basie-
rend auf der 4-Nachbarschaft aufzubauen. Ein weiterer zentraler Beitrag dieser Arbeit
befasst sich mit dem Dualen des RAG, seiner Bedeutung und seiner Verwendung bei der
Zusammenführung der benachbarten slope-Regionen. Die Hierarchie der slope-Regionen
zerlegt das Bild in slope-Regionen, wobei seine Topologie erhalten bleibt. Die oberste
Ebene der Hierarchie offenbart die Struktur des Bildes, die aus den kritischen Punkten
und den Verbindungen zwischen ihnen besteht. Die Ergebnisse der Implementierung legen
nahe, dass ein Bild eine Kombination aus seiner Struktur und einigen Farben ist. Der
vorgeschlagene hierarchische Algorithmus hat eine Berechnungskomplexität von O(log d).
ix
Schließlich ist das letzte Ziel dieser Arbeit, die Verbindung zwischen dem vorgeschlagenen
Algorithmus und maschinellem Lernen zu nutzen. Dieses Ziel wird durch die Ableitung
einer Zielfunktion erreicht, die einige der vielen Schritte im vorgeschlagenen Algorithmus
vereinfacht und den Bereich des Lernens einer unregelmäßigen Bildpyramide eröffnet.Diese
kumulative Dissertation präsentiert Forschungsergebnisse aus fünf ausgewählten Ver-
öffentlichungen auf dem Gebiet der Topologieerhaltung in Bildern unter Verwendung
unregelmäßiger Graphenpyramiden. Die Erhaltung der Struktur und der Topologie von
Daten ist ein grundlegendes Forschungsproblem auf dem Gebiet der Bildanalyse und
Repräsentation mit zahlreichen Anwendungen.
In dieser Arbeit wird ein monoton verbundener topologischer Unterraum, die so genann-
te slope-Region, aus früheren Forschungsarbeiten eingeführt. Der theoretische Beitrag
dieser Arbeit konzentriert sich auf die Eigenschaften und die Verallgemeinerung der
slope-Regionen. Es werden die hervorstechenden Merkmale der slope-Regionen für ihre
Identifizierung aufgezählt.
Aus der Sicht der Repräsentation und der Modellierung besteht der Kernbeitrag in der
Entstehung der inneren Grenze (oder der gefalteten Grenze) und der äußeren Grenze. Die
innere Begrenzung der slope-Region hilft dabei, die Löcher einzubeziehen, die geometrisch
von der äußeren Begrenzung der slope region eingeschlossen sind, aber topologisch vom
Inneren der slope-Region ausgenommen sind. Dies trägt dazu bei, die slope-Region als
homöomorph zu einer Scheibe zu modellieren. Das Vorhandensein und die Modellierung
von Löchern ist einer der wichtigsten Unterschiede zwischen den vorgeschlagenen slope-
Regionen und dem zuvor existierenden topologischen Unterraum.
Die slope-Regionen werden in zwei Prototypen verallgemeinert, abhängig von den Kom-
ponenten der slope-Region und unabhängig von den geometrischen Merkmalen wie Größe
und Form der Regionen.
Aus der Sicht der Implementierung schlägt die Arbeit einen Algorithmus vor, um eine
Hierarchie der slope-Regionen über Regions-Adjazenz-Graphen (RAG) eines Bildes basie-
rend auf der 4-Nachbarschaft aufzubauen. Ein weiterer zentraler Beitrag dieser Arbeit
befasst sich mit dem Dualen des RAG, seiner Bedeutung und seiner Verwendung bei der
Zusammenführung der benachbarten slope-Regionen. Die Hierarchie der slope-Regionen
zerlegt das Bild in slope-Regionen, wobei seine Topologie erhalten bleibt. Die oberste
Ebene der Hierarchie offenbart die Struktur des Bildes, die aus den kritischen Punkten
und den Verbindungen zwischen ihnen besteht. Die Ergebnisse der Implementierung legen
nahe, dass ein Bild eine Kombination aus seiner Struktur und einigen Farben ist. Der
vorgeschlagene hierarchische Algorithmus hat eine Berechnungskomplexität von O(log d).
Schließlich ist das letzte Ziel dieser Arbeit, die Verbindung zwischen dem vorgeschlagenen
Algorithmus und maschinellem Lernen zu nutzen. Dieses Ziel wird durch die Ableitung
einer Zielfunktion erreicht, die einige der vielen Schritte im vorgeschlagenen Algorithmus
vereinfacht und den Bereich des Lernens einer unregelmäßigen Bildpyramide eröffnet.
Contents
Abstract vii
Kurzfassung ix
Contents xi
1 Introduction to Topology and Irregular Image Pyramid 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
I First Part 7
2 Basics of Slope region hierarchy 9
2.1 Graph-based image representation . . . . . . . . . . . . . . . . . . . . 9
2.2 Graph-based irregular image pyramid . . . . . . . . . . . . . . . . . . 10
2.3 Combinatorial maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Cellular Decomposition and Cellular Complex . . . . . . . . . . . . . . 16
2.5 Categories of vertices, paths and regions . . . . . . . . . . . . . . . . . 18
2.6 Slope complex and properties of the Slope regions . . . . . . . . . . . 23
2.7 Preserving the structure and the topology of an image. . . . . . . . . . 28
3 Merging of slope regions 29
3.1 Motivation and Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Boundary Adjacency Graph (BAG) . . . . . . . . . . . . . . . . . . . . 30
3.3 Paper A - Congratulations! Dual Graphs Are Now Orientated! . . . . 31
4 Characterization and Generalization of slope regions 35
4.1 Motivation and Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Paper B - Partitioning 2D Images into Prototypes of Slope Region. . . 36
4.3 Paper C - Characterizing slope regions. . . . . . . . . . . . . . . . . . 37
5 Experiments and Results 41
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
xi
5.2 Paper D - Image = structure + few colors . . . . . . . . . . . . . . . . 42
5.3 Paper E - A Step Towards Learning Contraction Kernels for Irregular
Image Pyramid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6 Concluding Remarks 49
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Bibliography 53
Second Part 59
Paper A
Congratulations! Dual Graphs Are Now Orientated! 61
Paper B
Partitioning 2D Images into Prototypes of Slope Region 63
Paper C
Characterizing slope regions 65
Paper D
Image = Structure + Few Colors 67
Paper E
A step towards learning Contraction Kernels for Irregular Pyramids 69
List of Figures 70
List of Tables 71
Appendix
Curriculum Vitae 73
CHAPTER 1
Introduction to Topology and
Irregular Image Pyramid
In Einstein’s general relativity the structure of space can change but not
its topology. Topology is the property of something that doesn’t change
when you bend it or stretch it as long as you don’t break anything.
Edward Witten
1.1 Motivation
The concept of topology revolves around the notion that there is an idea of proximity
and the spatial relation between the elements of a set. Unlike the geometrical properties,
for example, the shape and size of an object, the topological properties remain unchanged
even after geometrical deformations like twist, stretch, rotate, etc. In formal terminology,
the topological properties are invariant under the continuous transformations of the space.
This makes them more significant for the applications that require the adjacency relations
between the elements of a set. The topological properties encapsulate the qualitative
signatures like the genus of the surface, the number of connected components or holes.
The famous metaphor in the field of topology states- ‘the mug and the donut are one
and the same’. This equivalence relation is due to the fact that both the mug and the
donut have a single hole in them. Moreover, topological features are not bounded by
coordinate systems [Car09]. Although we often receive data in the form of vectors or real
numbers in a coordinate system, the study of topology deals with the intrinsic properties
of the objects. This makes the topological features more robust and vital for various
applications.
1
1. Introduction to Topology and Irregular Image Pyramid
Topology is subconsciously involved in our daily-life problems like (a) the process of
untangling a tangled earphone wire corresponds to reducing the number of holes created
by the wire, and in contrast, (b) planting a knot of a shoelace that increases the number
of holes. Besides, topology has been used in multiple applications across the different
fields of science:
1. Image analysis and segmentation [WZS+15, ZL21]
2. Shape matching [PSO18] and object recognition [MGGR13]
3. Image classification [DMV17]
4. Robot path planning and analysing [LLS19, SUDA20]
5. Medical image segmentation and modeling [LGB+20, DCL20]
6. Relation between structure, shape and topology of the molecules in chemistry [GCV20]
7. Topology preservation in combination with machine learning [HKNU17]
The structure and the topological properties provide the key insights into the intrinsic
relationship within the data and assist in the extraction of the relevant features of possibly
complex/high dimensional data. Therefore, preservation of the topological properties is
a crucial issue in data analysis.
Our visual system is tuned to process structures typically found in the world. Borders,
corners, and edges are some of the structural features that are processed to give a
meaningful outcome. But machines do not possess this capability. The topology and the
structure of the image help the machines to understand and process the digital images.
The terms structure and topology are quite interconnected. They form a mathematical
basis for image processing operations like image thinning, border following, and connected
component labeling. This can be illustrated by a simple example: topologically speaking,
donut and the mug are the same, until a bite of donut disconnects its boundaries. The
disconnected boundary no more encapsulates the hole making it topologically different
from the mug. The boundary is a structural feature and its modification leads to change
the topology of the object.
The computation of the structure obeying a topological property is complemented with
the concept of cellular decomposition. In topology, cellular decomposition deals with the
decomposition of a manifold (cellular complex) as the disjoint union of the cells that
possess certain topological properties. Narrowing down to images, cell decomposition
is similar to image segmentation where the individual segments comply with a feature
(for example same object) or a topological property. The pioneering work of Kovalevsky
[Kov89] is one of the earliest research that intends to employ the concept of the cellular
complexes in the field of image processing. [EHNP03, LPZ+20] are some of the researches
that use the concept of cellular decomposition while simultaneously preserving the
topological properties of 2D surfaces.
Besides preservation of the structure and the topology, the following are the factors that
determine the practicability of the approach:
2
1.2. Outline
• Restrictions on input data
The approach should be applicable on a wide range of input data that has as less
restrictions as possible (ideally no restrictions).
• Efficient computation
Establishing the topological relations and deriving the structure from the input
data should be done efficiently.
• Identifying the characteristics
It is important to enumerate the typical characteristics of the structure that are
necessary for the existence of the required topological property. It also helps to
realize the structurally irrelevant and redundant data.
• Compact representation
Elimination of the data that does not contribute to the structure and the topology
of the data assists in achieving a compact representation.
• Generalization
Structures adhering to a topological property may exist in different sizes and shapes.
This necessitates the generalization of the properties irrespective of the size and
the shape but rather depending on the characteristics and features of the structure.
• Potential for learning
With the surge of learning-based algorithms in the last decade, the potential to
learn and compute the structure makes it more practicable.
This thesis presents a hierarchical approach for the decomposition of the 2D surface
(specifically image surface) into cells called as slope region (see Section 2.5.3). The
publications included in this thesis attempt to answer the points mentioned above that
determine the practicability of the slope region hierarchy to preserve the structure and
topology of images. Besides, from the application point of view, the results presented in
this thesis exhibit that an image is nothing but a combination of its structure and a few
colors. By preserving the structure of the input image, a comparable output image can
be produced with the lower number of colors on the palette.
1.2 Outline
This thesis is a cumulative doctoral thesis and is divided into three major parts in addition
to this brief introductory chapter.
1.2.1 Part 1: Basics of slope region hierarchy and its representation
Chapter 1 briefly explains the concept of (a) the region adjacency graph (RAG) and the
irregular graph pyramids that are used for the representation of an image pyramid, (b)
the combinatorial map data structure to store the graphs for implementation, and (c)
3
1. Introduction to Topology and Irregular Image Pyramid
other important definitions related to the slope region hierarchy, required to understand
the publications in Part 2. Chapter 2 introduces the concept of merging the slope
regions by eliminating a common boundary that is structurally redundant. This is
relevant for Paper A that aids in achieving a compact representation. Chapter 3 describes
the properties of the slope region relevant for Paper B and Paper C dealing with the
generalization and characterization of the slope regions. Chapter 4 discusses the algorithm
and result of decomposing the image into slope regions and constructing a slope region
hierarchy mentioned in Paper D. Further it discusses the potential approach for learning
described in Paper E.
1.2.2 Part 2: Selected Publications
Part 2 consists of 5 papers from my publications. These five papers cover the most impor-
tant research built on the fundamentals described in [KCBGD19a] and [KCBGD19b]. All
the five papers are peer-reviewed, accepted and published in proceedings of international
workshop/conference (Paper A, B, D, E) or as an article in international journal (Paper
C).
1.2.2.1 Contributions
I served as the first author in 4 (Paper A, B, D, E) out of the 5 selected publications
and I served as the second author in the remaining 1 (Paper C). This section describes
the contributions of Walter G. Kropatsch, Rocio Gonzalez-Diaz, Jiri Hladuvka, Rocio
Moreno-Casablanca and myself to the selected papers of this cumulative thesis.
My contributions: As the first author, I was the main source of the ideas and the
developed methods presented in the Paper A, B, D, E ([BKCGD19, BJK19, BGDK20,
BGDK22]). For Paper A, I formulated the definition of the orientation of the edges in the
Boundary Adjacent graph (BAG) and further used it for determining the removal kernel.
For Paper B, I adapted the existing prototype of the slope region from our previous
publication [KCBGD19a]. The second prototype of the slope region and upgrades of
modelling the holes on monotonic paths in the previously existing prototypes were my
major contributions. As a co-author in Paper C, I was responsible to generating results
and explanation of the prototype of the slope regions in relation to the characterization
of the slope region. Besides, I supported in the writing of the some proofs for presented
Theorems and Lemmas in Paper C. For Paper D, I adapted the existing implementation
of the Topology preserving irregular image pyramid of the Pattern Recognition and
Image Processing (PRIP) group. Implementation of the algorithm in parallel to reduce
computation time and upgrades in the pipeline of the algorithm was solely done by myself
from scratch. The derivation of the objective function, its explanation and the results in
Paper E are majorly contributed by me.
Contributions of Walter G. Kropatsch: As my mentor (Doktorvater) and head of
the Pattern Recognition and Image Processing (PRIP) research group, he was involved in
all my research activities through my PhD. Topology preserving irregular image pyramid
4
1.2. Outline
is a long term research topic of Walter G. Kropatsch. Therefore, he supported me with
his in-depth knowledge during the development of the ideas leading to publications. He
supported me in solving difficult problems, and provided me valuable feedback for all the
written text (reports and papers). He constantly guided me by giving idea for possible
future work.
Contributions of Rocio Gonzalez-Diaz: As a collaborator of PRIP research group
from a long time, Rocio Gonzalez-Diaz helped me majorly in the mathematical formulation
of the scientific writing. Besides, as the first author of Paper C, she initiated the idea
of presenting the necessary and the sufficient conditions for the existence of the slope
regions. I would respectfully honor her as my second mentor for guiding me through
discussions of new ideas and giving valuable feedback about my scientific writings.
Contributions of Rocio Moreno-Casablanca and Jiri Hladuvka: As the co-
authors of the selected papers (Paper A, B, and C) both Rocio Moreno-Casablanca and
Jiri Hladuvka contributed by proof reading the paper and providing the feedback to
improve the readability of the papers. Rocio Moreno-Casablanca also contributed in
some illustrations and proof presented in Paper C.
1.2.3 Part 2: Appendix
The appendix includes my curriculum vitae and a complete list of my publications.
5

Part I
First Part
7

CHAPTER 2
Basics of Slope region hierarchy
Topology is the science of fundamental pattern and structural
relationships of event constellations.
R. Buckminster Fuller
This chapter gives the relevant terminologies that are required to understand the publica-
tions in Part 2. It starts with the explanation of graph-based representation and the basic
graph operations for the construction of the irregular pyramids. Section 2.3 explains the
concept of the combinatorial map which is used as the data structure that implicitly
encodes the structure and is used for implementation purposes. Section 2.4 gives the
relation between the cellular decomposition and the proposed hierarchy based approach.
Lastly, Section 2.5 provides the basic definitions and the key concept of this thesis: the
slope region hierarchy and the slope complex required for the selected publications.
2.1 Graph-based image representation
Graph-based representations are an elegant way of representing images. Especially, when
the aim is to preserve the structure and the topology of the image, the representation
should not be bounded by the discrete coordinate system. A digital image P can be
visually perceived as a sampled version of a geographical terrain model which is a 2.5D
continuous surface by defining the height (gray-value pixel intensity) map g : R2 → R.
The digital image P can be efficiently represented by a dual pair of plane graphs. The
neighborhood graph G = (V, E) is formed by vertices v ∈ V corresponding to pixels p ∈ P
connected to the 4-adjacent neighbours by edges e ∈ E. Assuming each pixel is a separate
region, the 4-adjacent neighborhood graph is same as the Region Adjacency Graph
(RAG). The dual of the RAG is the Boundary Adjacency Graph (BAG) G = ( V , E)
where a vertex v ∈ V of BAG corresponds to a face formed by the intersection of the
9
2. Basics of Slope region hierarchy
boundary segments in the RAG G and the edges e ∈ E correspond to the boundary
separating the faces in the RAG G [Die97, Sec. 4.6]. We use a 4-neighbor RAG and not an
8-neighbor RAG to prevent violation of Jordan’s curve theorem. For more details, please
refer [MDC+19, Subsection 1.2.1]. The gray value of the pixel p is visually conceived
as the height of the surface and it is denoted by g(p) = g(v) where v ∈ V is a vertex
corresponding to the pixel p.
Note: Since the later part of the thesis discusses the merging of the pixel into regions
and their adjacency relations, we prefer to call it as the region adjacency graph instead
of the neighborhood graph.
Definition 1 (Orientation of an edge in RAG) The orientation of an edge e(v, w) ∈
E in the RAG G = (V, E) is directed from vertex v ∈ V to vertex w ∈ V iff g(v) > g(w),
and for g(v) = g(w) the edge is not oriented.
The edge e ∈ E connecting two vertices v, w ∈ V is non-oriented if g(v) = g(w). Note that
we define the orientation of edges by considering only the gray values of the corresponding
vertices as a feature. The theory stated in this document remains valid for higher
dimensional feature vectors provided that their ordering is defined.
2.2 Graph-based irregular image pyramid
Regular image pyramids first introduced by Burt et al. [BHR81] are defined as a sequence
of copies of an original image in which the resolution is decreased in regular steps. The
reduction factor between the two consecutive levels of the regular image pyramid is
determined by the reduction window and the overlap. A reduction window relates each
region (one pixel) on level n of the pyramid with a set of regions ( fixed dimension
typically 3 or 5 × 5 grid) in level (n − 1) of the pyramid. Therefore a regular pyramid
with a fixed reduction window has a fixed reduction factor [BK01]. But regular pyramids
are incapable of preserving the topological structure of the image, leading to structural
inaccuracies during the construction of the pyramid [SMK10]. The irregular pyramids
were introduced to overcome this drawback of the regular pyramid [Tes91]. An irregular
pyramid is defined as a stack of successively reduced graphs, where each graph is built
from the selected vertices (surviving vertices) and edges (surviving edges) of the graph
below. Thus neither the reduction factor between the adjacent levels is fixed nor is the
number of levels. The irregular graph pyramids facilitate the selection of the relevant
features and the elimination of irrelevant information that helps to analyze the data at
multiple resolutions. Since irregular pyramids do not use the fixed reduction window, they
are not bounded by the coordinate system and have potential to represent unstructured
data.
10
2.2. Graph-based irregular image pyramid
2.2.1 Graph operations
The reduction of the graph from the base level to the higher levels is produced by applying
basic graph operations: edge contraction and edge removal operations [Kro98]. This
subsection is dedicated to the explanation of the two graph operations (edge contraction
and removal) responsible for the bottom-up construction of the pyramid (REDUCE),
followed by the explanation of their reverse operation for the top-down expansion of the
higher level of the pyramid (EXPAND).
Edge contraction operation
Let G = (V, E) be a graph containing an edge e = (u, v) with u ̸= v and u, v ∈ V . Let f
be a function that maps every vertex V \ {u, v} to itself, and otherwise, maps it to a new
vertex w. The contraction of e results in a new graph G′ = (V ′, E′), where E′ = E \ {e},
V ′ = (V \ {u, v}) {w} such that ∀x ∈ V, x′ = f(x) ∈ V ′; and for all edges e(u, x) ∈ E
and e(v, x) ∈ E where x ∈ V maps to e′(w, x) ∈ E′ where w, x ∈ V ′.
In simple terms, given a graph G = (V, E) the edge contraction operation of edge
e(u, v) ∈ E where u, v ∈ V results in a new graph G′ = (V ′, E′) where the edge e is
removed and its two incident vertices u, v ∈ V are merged into a new vertex w ∈ V ′,
where the edges incident to w correspond to an edge incident to either u or v in G.
Figure 2.1 shows an example of edge contraction operation. The edges are non-oriented
on purpose to avoid the confusion between the orientation of an edge (Def. 1) and vertex
u merging with vertex v or vice-versa.
Figure 2.1: An example of edge contraction operation.
Edge removal operation
Let G = (V, E) be a graph containing an edge e = (u, v). Let f be a function that maps
every vertex V to itself. The removal of e results in a new graph G′ = (V ′, E′), where
E′ = E \ {e}, V ′ = V such that ∀x ∈ V, x′ = f(x) ∈ V ′.
In simple terms, given a graph G = (V, E) the edge removal operation of edge e(u, v) ∈ E
where u, v ∈ V results in a new graph G′ = (V ′, E′) where the edge e connecting the two
vertices u, v is removed without altering the vertex set V and other edge connections.
Figure 2.2 shows an example of edge removal operation.
The Edge contraction operation preserves the connectivity while simultaneously reducing
the graph. Therefore the edge contraction operation is a convenient tool for building a
topology preserving irregular image pyramid.
11
2. Basics of Slope region hierarchy
Figure 2.2: An example of edge removal operation.
2.2.2 Inverse of the edge contraction and edge removal operations
The inverse of the edge contraction and edge removal is called edge de-contraction and
edge insertion respectively. Intuitively, an edge de-contraction on graph G = (V, E) is
equivalent to splitting a vertex w ∈ V into two connected vertices u, v ∈ V ′ and adding
the edge e(u, v) ∈ E′ resulting in an expanded graph G′ = (V ′, E′). The cardinality of
both- the vertex set and edge set increases by one after an edge de-contraction operation.
Similarly, an edge insertion operation on graph G = (V, E) is equivalent to adding an
edge e(u, v) ∈ E′ between the two vertices u, v ∈ V resulting in an expanded graph
G′ = (V, E′). The cardinality of the edge set increases by one after an edge insertion
operation, while the cardinality of the vertex set remains unchanged.
2.2.3 Graph-based Irregular Image pyramid
Table 2.1 and Table 2.2 describes the consequence of a single edge contraction and a single
edge removal operation on the graph G = (V, E) respectively. Both operations result
in reducing the cardinality of the edge set by one. Additionally, the edge contraction
operations also reduce the vertex cardinality and the degree of respective face by one. Both
operations result in the reduced size of the graph. Multiple number of edge contraction
and edge removals can be performed simultaneously. By successively performing the edge
operations, a stack of reduced graphs called irregular graph pyramid is obtained.
Table 2.1: Consequences of edge contraction operation on graph G = (V, E)
Edge contraction operation
cardinality of edges set |E′| = |E| − 1
cardinality of vertex set |V ′| = |V | − 1
degree of new vertex w ∈ V ′ deg(w) = deg(u) + deg(v) − 2
number of faces |F ′| = |F |
Let G0(V0, E0) be the Region Adjacency Graph corresponding to an image P . The
stack of graphs Gk, k ∈ [0, 1, 2, . . . , n] produced by successive graph operations is called
graph-based irregular image pyramid. The graph G0 is termed as the base of the pyramid
and the graph Gn is the top of the pyramid, while k corresponds to the level of the
12
2.3. Combinatorial maps
Table 2.2: Consequences of edge removal operation on graph G = (V, E)
Edge removal operation
cardinality of edges set |E′| = |E| − 1
cardinality of vertex set |V ′| = |V |
degree of new vertex not applicable
number of faces |F ′| = |F | − 1
pyramid. The set of edges selected for the contraction and the removal operation is
termed as the contraction kernel and the removal kernel respectively. The contraction
kernel and the reduction kernel determine the survival of the vertices and edges in the
graph pyramid. The selection of the contraction kernel and the removal kernel are the
most crucial task that helps to construct the desired irregular pyramid. The research
presented in the Paper D (Section 5.2.1) deals with the selection of the contraction kernel,
while Paper A (Section 3.3) deals with the selection of the removal kernel depending
on the features of the image. Section 5.2.1.1 is dedicated for the reduction function
that determines the gray value g(w) of the resulting vertex w ∈ Gk after a contraction
operation of edge e(u, v) ∈ Gk−1. It also discusses the expansion function which is the
inverse of the reduction function and is used during a de-contraction operation.
2.3 Combinatorial maps
After a brief explanation of graph-based representations, this section delivers the data
structure to store the graphs. The selection of the data structure is a crucial task because
a lot of factors like computational speed, the possibility of parallel computing, required
storage memory, and encoding of the graph properties depend on the data structure.
Amongst all the methods of storing graphs, the most common methods are adjacency
matrix, adjacency list, edge list, generalized maps, combinatorial maps, incident matrix,
etc. Every method has its pros and cons which affects its efficiency depending on the
application.
This research aims to construct an irregular image pyramid that preserves the topology
of the image, where the structure of the image represented by the graph is required to
be encoded. The edge contraction operation may result in formation of multiple edges,
self-loops, inclusions, pending edges, beneficial for representing the structure of an image.
Adjacency list, adjacency matrix, and incident matrix are not capable of encoding the
structural information. On the other hand, combinatorial maps and generalized maps
are capable of modeling the topological structures [Lie91]. Hence combinatorial maps
are preferred as the data structure for the construction of the irregular image pyramids
that encode the structural information of the image [BK01, KHI07]. Similar to the graph
pyramids, the stack of combinatorial maps will form a combinatorial pyramid.
13
2. Basics of Slope region hierarchy
Definition 2 (Combinatorial Map) A combinatorial map is a triplet C = (D, α, σ),
where:
• D is a finite set of darts,
• α is an involution on the set D, and
• σ is a permutation on the set D.
In a combinatorial map, each edge in the graph is represented by two half edges called
darts d1 and d2 connected by the involution α(d1) = d2 and α(d2) = d1. Consequently
the relationship α(α(d)) = d holds true for all the darts in the combinatorial map.
Definition 3 ((α)-orbit) An edge in a combinatorial map is a set of two darts that
combine to form an (α)-orbit denoted by α∗-orbit.
The σ permutation relates each dart with the following dart around the same vertex in the
clockwise or counter-clockwise direction. The direction of the encoding is implementation-
specific. For all the further uses of the permutation relationship in this document,
we assume the σ permutation of a dart is the following dart around the vertex in a
counter-clockwise direction. Figure 2.3 shows examples of σ relations with orange
arrows and an example of α relation in blue arrow. The sequence of darts while traversing
around a vertex starting from dart d is called a (sigma)-orbit denoted by σ∗(d). The
inverse function of the permutation σ is called an inverse permutation σ−1. The inverse
permutation of a dart is the following dart around the vertex in a clockwise direction.
If σ(d1) = d2, then σ−1(d2) = d1.
The dual of the graph is implicitly encoded in the combinatorial map [Har69]. The dual
permutation φ is defined as φ = σ ◦ α for counter-clockwise direction of σ permutation
(and φ = α ◦ σ for clockwise direction of σ permutation). Thus the dual C of the
combinatorial map C = (D, α, σ) is defined as C = (D, α, φ), and it can be constructed
using the combination of the α and σ.
Figure 2.3 shows a simple graph encoded into a combinatorial map where each edge is
represented by two darts. Table 2.3 displays the encoding of the adjacency relations from
Fig. 2.3 into the σ permutation and the α involution.
Brun and Kropatsch [BK99] defined approaches to compute the special cases of edges
(multiple edges, empty self-loops, self-loops, pendant dart, etc) in a graph with help of σ
and α in a combinatorial map.
Example: The Combinatorial maps encode the adjacency relations and structure of the
objects and not the geometrical embedding in the plane. This can be explained with a
very interesting and realistic example that everyone can relate with:
Often while using the navigation systems (e.g., Google maps), at the roundabout, the
14
2.3. Combinatorial maps
Figure 2.3: An example of a simple graph encoded as combinatorial map.
D 1 2 3 4 5 6 7 8 9 10 11 12
α 2 1 4 3 6 5 8 7 10 9 12 11
σ 10 11 2 7 4 6 5 12 8 1 3 9
φ 9 12 1 8 3 5 6 11 7 2 4 10
Table 2.3: Encoding adjacency relations into σ permutation and α involution of combina-
torial maps.
navigation system announces the ‘number of exit’ instead of announcing the geometrical
direction (e.g., right, left, straight, etc). Apparently, the ‘number of exit’ is exactly
the same as the number of σ permutations if the exit roads from the roundabout are
imagined as edges (Figure 2.4).
"Take the forth exit from the roundabout" "exit = σ(σ(σ(σ(current road))))"
Figure 2.4: Correspondence between combinatorial map and navigation system.
15
2. Basics of Slope region hierarchy
2.3.1 Independent edges in Combinatorial maps
In a combinatorial map, the edge operations are performed by modifying the permutations
and the inverse permutations of the respective darts. The contraction or removal of an
edge e associated with darts d1 and d2 will require modifications in the permutations
of four other darts: σ(d1), σ−1(d1), σ(d2), σ−1(d2). Thus the edge e (darts d1 and d2)
is dependent on four other darts termed dependent set. While using the combinatorial
map, the edge operations cannot be performed simultaneously (in parallel) on edge e and
the edges associated with the darts in the dependent set of e. Besides these four edges
associated with the darts in the dependent set, the remaining edges are combinatorially
independent of edge e.
2.4 Cellular Decomposition and Cellular Complex
A continuous function f : M → N where M and N are topological spaces (or Metric
spaces) is homeomorphic if the function has a one-to-one onto mapping and its inverse
is also continuous. Homeomorphism (topological isomorphism) is a function that captures
the topological properties of a given space. It establishes the relationship between the two
spaces based on the topological features and independent of the geometrical properties
like size and shape. In topological terminologies, the equivalence relation between the
mug and the donut is expressed as homeomorphism.
In general, a n-cell is a n dimensional subspace that is homeomorphic to n-balls (n
dimensional ball). For ease of imagination, let us limit the number of dimensions. A
3-cell is a volume that is homeomorphic to a 3D ball (sphere). Similarly, a 2-cell and a
1-cell are homeomorphic to a disc and an arc. A 0-cell corresponds to a point. This is
analogous to graphs and can be associated with the graphs for an intuitive understanding
of cellular decomposition. In graphs, the 0-cells, the 1-cells, and the 2-cells correspond to
the vertices, the edges, and the faces of the graph. The faces (2-cells) are bounded by
the edges (1-cells) and the edges are bounded by the vertices (0-cells).
A cellular decomposition is a process of partitioning a nD manifold into a disjoint union
of nD cells. Such a partition involves contribution of kD cells, where k ∈ [0, 1, . . . , n − 1].
Conversely, the cellular complex is topological spaces that is constructed by gluing (union)
the cells.
2.4.1 Relating cellular decomposition with irregular image pyramids
A digital image P can be perceived as a sample version of a surface S → R2 as shown
in Figure 2.5. In the similar fashion, the 4-adjacent neighborhood graph G of image P
represents the surface S. The points of S are associated with vertices in G and simple
arcs connecting two points on S are associated with edges in G. A face of the graph G
corresponds to a connected surface, being a closed subset of S as shown in Figure 2.5
and Fig. 2.6.
16
2.4. Cellular Decomposition and Cellular Complex
(a) (b)
Figure 2.5: Digital image and its corresponding 2.5D continuous surface.
Figure 2.6: Low frequency sampling of digital image in Fig. 2.5(a), and its corresponding
pair of dual graphs (RAG and BAG).
17
2. Basics of Slope region hierarchy
One can imagine that the graph embedding results in a cellular decomposition of the
image surface into a disjoint union of image patches (2-cells). Conversely, gluing the
image patches (2-cells) results in an image surface (cellular complex). For instance, the
vertex in the RAG with black and white color in Figure 2.6 is associated with the local
minimum and the local maximum (0-cells) of the surface in the Figure 2.5(b). The region
(2-cell) of the digital image and the continuous surface highlighted with red (Figure 2.5)
is represented by the highlighted face in RAG bounded by 4-vertices and 4 edges in
Figure 2.6. The same is represented by a single vertex highlighted with black circle
in the BAG. The incident edges marked in black, preserve the connectivity with the
adjacent vertices (in BAG) that represent 2-cells in the corresponding image/surface.
The same concept is applicable for non-grid and irregular graphs that appear during the
construction of graph-based irregular image pyramid.
This thesis presents a similar approach for the decomposition of the image surfaces
into cells called slope region (Section 2.5.3). The points inside the slope region obey
a specific spatial relationship. The proposed algorithm processes the input image to
produce the output as decomposition of the image surface in the minimal number of slope
regions. This is achieved by the graph-based irregular image pyramid, where the vertices
corresponding to the relevant pixels and the connections between them are preserved.
After eliminating all the irrelevant vertices and edges, the graph at the top level of the
pyramid displays the structure of the image.
Alternatively, the process can be comprehended as gluing the image patches (2-cells) to
construct a cellular complex called Slope complex (Section 2.6), whose cells classify as
slope regions.
2.5 Categories of vertices, paths and regions
This section starts with defining the various categories of 0-cells (vertices) and the 1-cells
(edges / paths). It is in continuation with the explanation of the graph-based image
representation and the orientation of the edge in RAG (Section 2.1). Using the categories
of 0-cells and 1-cells, the section introduces the slope regions (2-cells) and their properties.
2.5.1 Local Binary Patterns (LBPs) for vertex categorization
Ojala et al. [OPH96] introduced Local Binary Patterns (LBP), which evolved as one
of the most studied texture descriptors. Originally LBP codes (texture descriptors) are
8-bit binary codes produced by thresholding the gray values in the peripheral of the pixel.
There exist several variants of the LBP depending on the following two parameters: (a)
the radius of periphery around the point of consideration, and (b) the number of samples.
The implementation of 4 bit LBP (considering 4 samples at radius 1) is only applicable
to the 4-adjacent neighborhood graph of the image, with a grid structure that initiates
the base level of the irregular image pyramid. But at the higher levels of the pyramid,
18
2.5. Categories of vertices, paths and regions
Figure 2.7: Encoding orientation of edges and bit switches.
the degree of a vertex is not limited to four. Moreover, the number of neighbors vary for
each vertex after successive edge contraction and edge removal operations. To maintain
generality and relevance for the higher level of the pyramids with irregular structures,
the LBP categories are defined based on the orientation of the incident edges.
The incident edges that are oriented outward are encoded as 1 while the incident edges
that are oriented inward are encoded as 0. Traversing the edges in a clockwise or
counterclockwise direction will result in a sequence of bits called LBP code. The number
of switches from zero to one or from one to zero in the LBP code is termed as bit
switches. Note that the non-oriented edges are not encoded into bits. The presence of
the non-oriented edge does not impact the LBP category of the vertex and they can be
ignored. The impact of presence of the non-oriented edges are discussed later in Def. 10
and Def. 12.
Fig. 2.7 shows an example of a vertex with degree 6 and the encoding of the edge
orientations into bits. In the example, The LBP code starts from the edge highlighted
in red and then traverse the following edges in the counter-clockwise direction. The
right side of the figure shows the number of bit switches in the bit sequence. Unlike the
example in Figure 2.7, if the first bit and the last bit does not match, then there is an
addition in the number of bit switches by one.
The categorization of the vertex into critical (the local maximum, the local minimum,
the saddles) and the non-critical (the slope points) is defined below based on the number
of bit switches in the LBP code. This eliminates the fixed sample size and depends on
the orientation of the incident edges making it applicable irrespective of the degree of a
vertex.
Definition 4 (Local maximum) A vertex v in graph G is a local maximum ⊕ if its
LBP code consists of only 1s.
19
2. Basics of Slope region hierarchy
Definition 5 (Local minimum) A vertex v in graph G is a local minimum ⊖ if its
LBP code consists of only 0s.
The term local extremum refers to the local minimum or the local maximum.
Definition 6 (Saddle vertex) A vertex v in graph G is a saddle vertex if the LBP
code has a number of bit switches greater than 2.
Definition 7 (Slope vertex) A vertex v in graph G is a slope vertex if the LBP code
has exactly 2 bit switches
Following are the LBP codes of the 4 classes of vertices v ∈ V as defined above for a
4-adjacency neighbourhood graph G = (V, E):
• Maximum: [1111],
• Minimum: [0000],
• Saddle vertex: [1010], [0101], and
• Slope vertex: [1100], [0110], [0011], [1001], [1000], [0100], [0010], [0001], [0111],
[1011], [1101], [1110].
2.5.2 Categorization of paths
After defining the categories of vertex, this subsection defines the categories of paths of
the graphs.
Definition 8 (Path) A path π is a non-empty sub-graph of G, consisting of an alter-
nating sequence of vertices and edges π = v1, e(v1, v2), v2, . . . , e(vr−1, vr), vr.
A path of a graph may consist of both oriented and non-oriented edges. For further use,
the path joining vertex v1 and vr is denoted as π(v1, vr).
Definition 9 (Monotonic path) A path π(v1, vr) is monotonic if all the oriented edges
(vi, vi+1), i ∈ [1, r − 1] have the same orientation.
Definition 10 (Level curve) A path π is a level curve if it is composed of non-oriented
edges only.
20
2.5. Categories of vertices, paths and regions
LBP category example of surface mesh corresponding vertex
local maximum
✐✻✲
❄
✛ +
local minimum
✐− ✛
✻
✲
❄
saddle vertex
✐× ✲
✻
✛
❄
slope vertex
✐✲✛
❄
❄
Table 2.4: LBP categories of vertices with their corresponding surface illustrations.
A monotonic path connects vertices in an order such that the gray value of the vertices
is either non-decreasing or non-increasing. All the vertices with the same gray value are
connected by level curves. A monotonic path π(v1, vr) can be further extended by adding
an edge orientated in the same direction as the direction of the monotonic path π(v1, vr).
A monotonic path that cannot be further extended is called a maximal monotonic
path.
Remark 1 The endpoints of a maximal monotonic path will always be a local extremum.
The concept of monotonic paths is very similar to the concept of integral lines defined
in [EHZ03]. There is a very subtle difference between these two terminologies. A level
curve can be a part of a monotonic path, but it cannot be a part of an integral line.
An integral line consists of strictly increasing or decreasing function values, while a
monotonic path consists of non-decreasing or non-increasing function values respectively.
21
2. Basics of Slope region hierarchy
2.5.3 Categorization of a region
A face of the surface embedded graph plane G corresponds to a connected surface, being
a closed subset of S → R2, bounded by the curves represented by the edges that surround
the corresponding face in the graph G.
Definition 11 (Slope region) A face in a surface embedded plane graph G is a slope
region S if all the pairs of points in the face can be connected by a continuous monotonic
curve inside the face.
Definition 12 (Plateau region) A face in a surface embedded plane graph G is a
plateau region if all the points in the face can be connected by a level curve inside the
face.
In simple words, a face in a surface embedded plane graph G is a plateau region if all the
points inside the face have the same gray value.
For example, Figure 2.8(a) shows a sample image with white background and a grey
colored foreground object. Figure 2.8(b) shows its corresponding RAG. The plateau
region is highlighted in grey color, which is composed of a connected subgraph and the
faces encapsulated by the subgraph with the same gray value. Since the edges that
compose the plateau region are non-oriented, the the LBP categorization of the individual
vertices of the plateau region is not defined at the base level G0 of the pyramid. At
higher levels of the pyramid, the plateau region will shrink to a single vertex due to the
successive contraction operations as shown in Figure 2.8(c). The LBP categorization for
plateau region is computed for the vertex that represents the plateau region at a higher
level of the pyramid. The spatial receptive field of the vertex representing the plateau
region consists of a bounded connected surface L, being a closed subset of the surface
S → R2, where g(l) = c, ∀l ∈ L. The vertex representing the plateau region could then
be categorized as a local maximum, a local minimum, a saddle, or a slope, depending on
its neighborhood.
Definition 13 (Saddle region) A face in a surface embedded plane graph G is a saddle
region if there exist pairs of points in the face that cannot be connected by a continuous
monotonic curve inside the face.
From the literature, a non-well-composed configuration (defined in [LER95]) is a similar
term as that of a saddle region. The pixel configuration in Figure. 2.9(a) is a non-well-
composed configuration if g(a) < g(b), g(a) < g(d), g(c) < g(b), g(c) < g(d). Figure 2.9(b)
is the neighbourhood graph for the pixel configuration in Figure 2.9(a) with oriented
edges for better visualization. A 2D image is called well-composed [LER95] if it does not
contain the non-well-composed configuration as shown in Figure 2.9(a).
22
2.6. Slope complex and properties of the Slope regions
Figure 2.8: Plateau region and its vertex representation.
✒✑✓✏
✒✑✓✏
✒✑✓✏
✒✑✓✏
a b
cd
✛
✲
❄
✻
✒✑✓✏
✒✑✓✏
✒✑✓✏
✒✑✓✏
a b
cd
✒✑✓✏
r
✛
✲
❄
✻
■
❘
✒
✠
(a) (b) (c)
Figure 2.9: Inserting a hidden saddle.
The non-well composed configuration signifies the presence of a saddle point that is not
captured by the digital image. These hidden saddle points are inserted in order to convert
the non-well composed configurations into the well composed configuration. A hidden
saddle as a vertex r adjacent to vertices a, b, c and d such that max(g(a), g(c)) < g(r) <
min(g(b), g(d)) as shown in Figure 2.9(c). The non-well-composed configurations occur
when the sampling frequency (used to sample the landscape for the digital image) is
lower than the Nyquist criterion i.e., the minimum distance between any two critical
points. After the insertion of the saddle vertex r, the number of bit switches does not
change for the vertices a, b, c and d, and hence the LBP category of those vertices will
remain unchanged. Note: at this stage, no structural information is added or removed.
2.6 Slope complex and properties of the Slope regions
Definition 14 (Slope complex) A cell decomposition of a continuous surface is a
slope complex if all its 2-cells are slope regions.
23
2. Basics of Slope region hierarchy
2.6.1 What makes slope complex decomposition special?
According to the survey [RM02], the authors have categorized the research on mathemat-
ical treatment of surfaces into four main categories:
• Theoretical design of the surface
• Method used feature identification / extraction
• Generalization (simplification and smoothing techniques)
• Applications
For convenience, we compare the proposed approach of slope complex decomposition
with other methods in these four categories.
The theoretical design of surfaces has been an integral part of all the researches. There is
an extensive research on the Morse-Smale complex (MS complex) and its decomposition.
The MS complexes are built using a real-valued smooth map over the surface, with
non-degenerate critical points. Edelsbrunner et al. [EHZ03] presents a remarkable work
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. The
concept of the integral lines has great similarity to the monotonic curves of our approach
although monotonic curves are geometrically less constrained. Moreover, the plateau
regions that form the extrema (non-degenerate critical point) are excluded from the MS
complex, but they are considered in the slope complex.
Decomposition using the watershed [BL79] is another popular algorithm that is categorized
under theoretical design. Intuitively, a drop of water flowing on a topographic terrain
follows the nearest minimum. The nearest minimum is the one that lies at the end of
the path on the steepest descent. The watershed algorithm decomposes the complex
following the same steepest descent. On the other hand, a slope region is composed of
continuous paths with a non-negative gradient connecting a point to the local extrema
inside the slope region. This is simple to visualize by replacing the drop of water with a
beginner skier skiing downhill. The skier is suggested to maneuver through the slope
with a lower gradient and not to get hold of the steepest descent. As a consequence, the
watershed algorithm provides a unique solution while the decomposition of the surface
into slope regions results in non-unique solutions with the flexibility of maneuvering the
boundaries.
The term features is associated with the critical points, the ridges, and the channels of
the surface. The features can be identified by observing the contour maps or the water
flow direction [Woo98]. The use of second-order derivatives and the Hessian matrix is the
most popular approach for detecting the critical points of a surface. Though there exists
ambiguity while dealing with non-degenerate critical points. This thesis proposes the
use of Local Binary Patterns (LBPs) [OPH96] (Section 2.5.1) to determine the critical
points with a few benefits such as avoiding calculations of derivatives.
24
2.6. Slope complex and properties of the Slope regions
Other closely related approaches include the use of Reeb graphs [Ree46] that reflects the
evolution and connection between the adjacent level sets of a real-valued function on a
manifold. Marzantowicz et al. [MSK15] used Reeb graphs for the representation of a
sub-complex of a manifold. The authors characterized the Reeb graphs for functions g on
manifolds M with concrete properties. For example, if M has a finite fundamental group,
then the Reeb graph of g is a tree. In contrast, for the decomposition of a slope complex
into slope regions, the considerations are focused on the monotonic paths bounding the
slope regions. The pair of monotonic paths bounding the slope regions implicitly encodes
the evolution of the contour lines. Though there is a subtle similarity between the Reeb
graphs and the proposed method: in both the cases, the topology of the surface contour
changes at the critical points of the surfaces. For detailed explanation see Section 2.7.
With help of persistence homology [EH+08], both the methods can be extended for
simplification of the topology.
From the application point of view, the decomposition of a digital image into cells can
be considered an over-segmentation of the image. Morphological watersheds and Voronoi
tessellations are popular approaches for obtaining an approximation of the segmentation.
These methods are widely used for the segmentation of cells, cell membranes, and organs
like lungs in medical images. Authors in [FDCAM11] used the Voronoi tessellations
to first obtain an approximation of segmentation and then deformed the segmentation
boundary using handcrafted features to reduce the error. In [CCK+18] the author
proposed an algorithm for hierarchical segmentation of an image. They first obtain an
over-segmentation of the image and then successively merged the adjacent segments
depending on the distance (dissimilarity measure) between the segments. This is similar
to the superpixel hierarchy first introduced by Ren and Malik [RM03]. Superpixel is a
cluster of pixels similar in color and other low-level properties. Superpixel algorithms
like [WYG+18] are computationally inexpensive and are also compatible with learning-
based approaches. Besides, they are a good substitute for over-segmentation, since
they provide flexibility to choose the number of segments and the area of segments
(pixels in each superpixel) depending on the chosen algorithm. However, neither of these
approaches provides a topological overview now they guarantee structure preservation.
The decomposition of the digital images into the slope regions is bound to retain the
critical points, the topology, and the structure of the image (see Chapter 5 for more
details on experiments and results). Therefore obtaining image segments that defy the
structure of the image is beyond the scope of this thesis. Though extensions such as
merging of slope regions depending on their distance (dissimilarity measure) can be
applied to obtain better segmentation results.
2.6.2 Components and Properties of slope regions
This subsection explains the components and the properties of the slope region pre-
sented in [KCBGD19a, KCBGD19b, BKGDC19], that forms the basis for the selected
publications.
25
2. Basics of Slope region hierarchy
For better understanding, the components of the slope region are explained in three
parts:
• 0-cells: the local maximum, the local minimum.
• 1-cells: inner boundary, outer boundary and the boundary of the slope region.
• 2-cells: holes
The local extrema (the local maximum and the local minimum) defined in Def. 4 and
Def. 5 are also denoted by 2 − max and 2 − min respectively where n in n − max and
n−min refers to the dimension. While considering the local extrema on a curve (example:
boundary of slope region), the extrema are denoted by 1 − max and 1 − min.
Let D(p, r) ⊂ R2 be a disc centered at point p ∈ R2 with radius r > 0. The interior
int(D) of D is a set of points {q ∈ R2, such that distance d(p, q) < r}. The boundary
δD of the disk D is a continuous closed curve δD : D \ int(D). The boundary δD is a
set of points {q ∈ R2 such that distance d(p, q) = r}.
Let R be a region obtained as the image of a continuous surjective map f : D → R.
The set of points in image im(f |int(D)) is the interior int(R) of region R and the set of
points in image im(f |δD) is the boundary δR of the region R. The interior int(R) is
homeomorphic to the disc.
Definition 15 (Outer boundary of a region) The outer boundary of the region R ⊂
R2 is a simple continuous closed curve π(0, 1) → R that divides R2 in two connected
components: one containing R bounded by π and one unbounded.
The outer boundary of a region R lies in the boundary δR but is not necessarily
homeomorphic to δD. The above mentioned definitions of the interior of the region
int(R), boundary δR, and the outer boundary of R can be defined for a slope region S
by replacing the term "region R" with the term "slope region S".
A set of points H ∈ R2 is a hole in the slope region S ∈ R2 iff H is (geometrically) within
the outer boundary of the slope region S and no monotonic path exist between points
h ∈ H and s ∈ S.
The components present (geometrically) inside the outer boundary of the slope region S
are connected to the outer boundary using the concept of inner boundary (also known as
folded boundary). Figure 2.10 shows the significance of the inner boundary by displaying
the difference between the two regions surrounding holes, (a) with the inner boundary
and (b) without the inner boundary. In Fig. 2.10 (b), the outer boundary encapsulates
the geometrical interior which is the union of the region of interest shaded in ‘blue’ and
the holes (components) highlighted with green boundaries. In this case, the region of
interest has 2 holes and is not homeomorphic to a disc. In comparison, the boundary in
26
2.6. Slope complex and properties of the Slope regions
Fig. 2.10 (a) is a union of two, the outer boundary and the inner boundary. The inner
boundary surrounds the hole and it is connected to the outer boundary at points m and
n respectively. The two connections π(m, c) and π(c, m) between a hole and the outer
boundary assist in a complete traversal of the boundary. But both the paths π(m, c) and
π(c, m) coincide each other and are composed of the same geometrical points including
the endpoints. The inner boundary makes sure that the components are excluded from
the region of interest. Thus the interior int(R is homeomorphic to a disc in Fig. 2.10 (a).
(a) (b)
Figure 2.10: Significance of inner boundary.
Intuitively, one can imagine an ideal inflated balloon that does not tear apart with
external force. The surface of the balloon acts as the outer boundary. By pressing a
needle on a single point in the outer boundary, the surface of the balloon takes the shape
of the needle and encapsulates it in between the folded (inner) boundary. Now the needle
is in a space that is bounded by the outer boundary, i.e. geometrically inside the outer
boundary. But topologically, the needle is outside the surface of the balloon making
the balloon homeomorphic to a sphere. A similar example in a lower dimension will be
applicable for the concept of the folded boundary and homeomorphism between slope
regions and a disc.
Following are the important properties of the slope region:
Remark 2 [KCBGD19a, Lemma 1] The boundary of the slope region is composed by
either a level curve or two monotonic paths connecting a 1-max and a 1-min.
27
2. Basics of Slope region hierarchy
Remark 3 [KCBGD19a, Lemma 2] The boundary of a slope region may contain as
inner boundary points a 2 − max and a 2 − min, both simultaneously, but never a saddle
point.
Contraction of forest of saddles
A connected sub-graph with all the vertices classified as saddle vertices is called a forest
of saddles. The contraction of the forest of saddles is equivalent to the concept of folding
and unfolding of monkey saddles explained by Edelsbrunner et al. [EHZ03].
Remark 4 [KCBGD19a, Lemma 5] The number of slope regions remains the same if
all edges between the saddle points are contracted.
2.7 Preserving the structure and the topology of an image.
As stated previously, a digital image can be perceived as a geographical terrain model of
2.5D surface where the height of the surface corresponds to the intensity of the respective
pixel. For a function g : R2 → R, the critical point is a value in its domain where the
gradient is undefined or equal to zero. The surface contours changes its topology at the
critical points of the surface. For example, the surface contours will collapse to a point
at a non-degenerated extremum and multiple contours will intersect at a saddle point.
Therefore, by preserving the critical points and their function values the topology of the
image is preserved.
The publications mentioned in the thesis deal with the construction of the irregular image
pyramid that preserves the critical points and the connections between them. The top
level of the pyramid consisting of a graph of critical points reveal the structure of the
image. The graph operations are performed such that all the face in the graph at the top
level of the pyramid adhere to properties of slope regions. Paper B and Paper C exploit
the characteristics of the slope regions. Paper A aims for merging of the slope regions,
while Paper D provides the algorithm and results from the proposed method.
28
CHAPTER 3
Merging of slope regions
This chapter is about merging the slope regions during the construction of an irregular
image pyramid to achieve a compact representation. Section 3.1 provides the motivation
of the proposed approach and Section 3.2 explains the Boundary Adjacency Graph (BAG)
which serves as the basis for the proposed research. Section 3.3 summarizes the selected
publication Paper A.
3.1 Motivation and Concept
A compact structural representation is one of the factors that determine the practicability
of the topology-preserving image pyramid. Technically speaking, after the insertion of
the hidden saddle vertices, all the non-well-composed configurations are converted to
the well-composed configuration (Section 2.5.3, Def. 13). This means that the image
surface is divided into slope regions, since the well-composed configurations comply to
the Definition 11 of the slope region. But neither it provides any useful information
about the structure of the image nor it is the best representation possible.
Helman et al. [HH91] shows that extraction of the desired structural information before
visualizing it helps reduce the storage requirements. They concluded that the surface
representation required about one-tenth the storage of the full data set. Concerning the
concept of topology preserving irregular pyramids, a compact structure can be acquired
by decomposing the image surface into a minimal number of slope regions. Eliminating
the slope vertices is one factor to achieve the goal, but it is not sufficient. The other factor
is the elimination (removal) of structurally irrelevant edges and merging the slope regions.
A structurally irrelevant edge can be described as the edge that does not contribute to
the structure and the topology. That means the merging of the slope regions should
not create a saddle region. Paper A employs the Boundary Adjacency Graph (BAG) to
derive a set of rules to determine the edges/paths that can be removed in order to merge
the slope regions without creating a saddle region.
29
3. Merging of slope regions
3.2 Boundary Adjacency Graph (BAG)
Note: In Paper A, the Region Adjacency Graph (RAG) is referred to as the primal graph.
The dual of the RAG G = (V, E) is the Boundary Adjacency Graph G = ( V , E), where
V and E corresponds to the vertex set and the edge set in G. The vertex v ∈ V
associates with a face in G while the edge e ∈ E associates with the common boundary
between the two adjacent faces.
Definition 16 (Orientation of an edge in BAG) The orientation of an edge e ∈
E in graph G is from vr to vl, where vr and vl are the vertices in G corresponding
to the faces on the right and the left side of the respective edge e in G while walking in
the direction of orientation of e.
A edge e ∈ E in G is not oriented if the corresponding edge e ∈ E in G is also
non-oriented.
3.2.1 Consequence of the graph operations on BAG
Following the duality property, the consequence of the graph operations (Section 2.2.1)
performed on the RAG can be realized in the BAG. The edge contraction operation in
the RAG merging two vertices corresponds to the edge removal operation which between
the two respective regions in the BAG. Similarly, the edge removal operation in the RAG
corresponds to the edge contraction operation in the BAG.
Following are the consequence of the graph operations on the BAG.
Table 3.1: Consequences on RAG G due of edge contraction in G = ( V , E)
Edge contraction in G
cardinality of edges set |E′| = |E| − 1
cardinality of vertex set |V ′| = |V |
degree of new vertex not applicable
number of faces |F ′| = |F | − 1
3.2.2 LBP categorisation of vertices in BAG
Following the method of LBP categorization of the vertices in RAG as mentioned in
Section 2.5.1, the vertices of the BAG can be categorized into either of the two possible
classes:
• The slope vertex - associated with the slope region in the RAG.
• The saddle vertex - associated with the saddle region in the RAG.
30
3.3. Paper A - Congratulations! Dual Graphs Are Now Orientated!
Table 3.2: Consequences on RAG G due of edge removal in G = ( V , E)
Edge removal in G
cardinality of edges set |E′| = |E| − 1
cardinality of vertex set |V ′| = |V | − 1
degree of new vertex w ∈ V ′ deg(w) = deg(u) + deg(v) − 2
number of faces |F ′| = |F |
3.3 Paper A - Congratulations! Dual Graphs Are Now
Orientated!
"Congratulations! Dual Graphs Are Now Orientated!". Batavia, D., Kropatsch, W. G.,
Casablanca, R. M., & Gonzalez-Diaz, R. (2019, June). In International Workshop on
Graph-Based Representations in Pattern Recognition (pp. 131-140). Springer, Cham.
3.3.1 Merging adjacent slope regions
This paper proposes a novel method of identifying structurally irrelevant edges that
are eligible for the removal kernel in RAG. It defines the orientation of the boundary
adjacency graph concerning the orientation of the edges in the RAG. The rules for
identifying the irrelevant edges were inspired by observing the orientation of the edges
incident on the vertices in the BAG corresponding regions to be merged in the RAG.
Two adjacent regions sharing the common boundary in the RAG may occur in arbitrary
shape and size. Hence the rules for identifying whether the slope regions can be merged
or not should be based on the features that are independent of the size and shape of the
regions. The features used in Paper A for deriving the rules are: (a) the location of the
2-max and the 2-min on the boundary of the slope regions and (b) their connections with
the common boundary. The paper enumerates all the possible combinations that may
occur with these features.
Following is a hypothetical example that best explains the merging of the adjacent slope
regions. Assume that a graph-based irregular image pyramid algorithm is applied to
the image in Figure 3.1(a). The goal of the algorithm is to preserve the critical points
and display the structure of the image with the least number of slope regions. At a
certain level of the pyramid, assume that the algorithm produces a graph as shown in
Figure 3.1(b). The vertex marked with the +, −, and S symbol are associated with
the local maximum, the local minimum, and the slope vertex respectively. The vertex
marked with {S, +} acts as a slope vertex for face F1 and as a local maximum for face
F2. Similarly, the vertex marked with {−, S} acts as a local minimum for face F1 and as
a slope vertex for face F2. All the remaining (randomly placed) vertices in blue color
are slope vertices. The two adjacent faces F1 and F2 satisfy all the conditions required
for a slope region. The removal of path π({S, +}, {−, S}) will result in merging of the
31
3. Merging of slope regions
two slope region F1 and F2. In this particular case, the merged face F as shown in
Figure 3.1(c) satisfies the conditions of slope region. Hence, the path π({S, +}, {−, S})
is structurally irrelevant. One can observe that the critical points (in our case vertices
{S, +} and {−, S}) are eliminated in pairs. This is validated by a similar observation by
Jan Koenderink in [Koe84]. Paper A explains the details of determining the structurally
irrelevant edges/paths that can be removed, such that the resulting merged face will
satisfy the conditions of the slope region.
(a) (b) (c)
Figure 3.1: Example of merging two adjacent slope regions.
The use of the BAG simplifies the implementation of this approach. The approach
mentioned in Paper A was employed in the Topology preserving Irregular Image Pyramid
(TIIP) algorithm described in Paper D for determining the removal kernel.
3.3.2 Potential use cases for implementation.
The very first instant where the proposed approach can be applied is after the insertion
of the hidden saddle vertices. Insertion of the single hidden saddle vertex makes the
addition of one vertex and four incident edges to the graph. Figure 3.2(a) shows an
example of such configuration with other edges incident on the vertices, assuming that
the non-well composed configuration is not on the boundary of the image.
According to the proposed method, the four edges (a, b), (b, c), (c, d), (a, d) originally
bounding the face of the non-well composed configuration will be eligible for removal.
This will reduce the storage requirement by four edges per saddle point insertion.
Moreover, if the combinatorial map is used as a data structure, all the redundant edges
(generated due to insertion of the hidden saddles) are independent of each other. Hence
these edges can be removed in parallel with the algorithmic complexity of O(1).
Fig.3.3 shows an image of size 312×481 from Berkeley image segmentation dataset [MFTM01].
The neighbourhood graph at the base level contains 154401 vertices and 308000 edges.
Following the proposed method, and ignoring the edges with contrast c(e) = 0, there
are 218553 number of structurally redundant edges at the base level of the pyramid.
The edges with contrast c(e) = 0 are ignored as they are eligible for the edge contrac-
tion operation. All the structurally redundant edges are eligible for the removal kernel.
Although it must be noted that the proposed method operates on two adjacent slope
32
3.3. Paper A - Congratulations! Dual Graphs Are Now Orientated!
❦
❦
❦
❦
a b
cd
❦r
✛
✲
❄
✻
■
❘
✒
✠
❦
❦
❦
❦
a b
cd
❦r■
❘
✒
✠
(a) (b)
Figure 3.2: Removing redundant edges after insertion of a hidden saddle vertex.
regions locally. A slope region is not guaranteed by merging more than 2 slope regions
simultaneously. In other words, two edges bounding a single slope region cannot be
removed simultaneously. Therefore, even though the number of edges eligible for removal
operation is considerably higher, the actual size of the removal kernel is bounded by half
the number of faces (|F |/2).
Figure 3.3: Image 160068 from [MFTM01] containing 308000 edges eligible for the
removal kernel at the base level of the pyramid.
33

CHAPTER 4
Characterization and
Generalization of slope regions
This chapter is about the identification of the important characteristic of the slope regions
and their generalization. Section 4.1 states the motivation for the research in Paper B
and Paper C. Section 4.2.1 summarizes Paper B that explains the two prototypes of the
slope region. Section 4.3.1 outlines Paper C which deals specifically with identifying the
properties that are necessary for the existence of the slope region.
4.1 Motivation and Concept
Theoretically, the slope regions have a simple definition based on the monotonic con-
nectivity of the elements inside the slope region (refer Def. 11). Although the intrinsic
relationship between the points inside the slope region remains the same, the slope regions
may appear in different sizes, shapes, and properties. For the identification of the slope
region, it is impractical to enumerate all the pairs of points and their connections to
determine whether a region is a slope region or not. In formal terms, a region must
comply with certain characteristics that are sufficient to classify the region as a slope
region. Paper C formally proves the necessary and sufficient conditions for the existence
of the slope region.
Slope regions may consist of different types and a different number of components (local
extremum, holes). The modeling of the slope regions depends on these components
and the connections between them. To simplify this process, Paper B discusses the
generalization of the slope regions by explaining the two prototypes of the slope region.
Paper B proves that a slope region can be classified into either of the two prototypes.
Relating it with image processing, an image can be modeled as a combination of the two
prototypes by partitioning the image surface into slope regions.
35
4. Characterization and Generalization of slope regions
4.2 Paper B - Partitioning 2D Images into Prototypes of
Slope Region.
"Partitioning 2D Images into Prototypes of Slope Region." Batavia, D., Hladůvka, J., &
Kropatsch, W. G. (2019, September). In International Conference on Computer Analysis
of Images and Patterns (pp. 363-374). Springer, Cham.
4.2.1 Prototypes of slope region
Several combinations of local maximum, local minimum, holes, outer boundary, and inner
boundary can be imagined to construct a slope region. But the intrinsic properties and
the flow of the contour field inside the slope region do not differ much. The main goal of
Paper B is to exploit the surface properties of the slope region and introduce the two
prototypes that are the generalization of the different slope regions. A prototype of a
slope region is a graphical representation including all the possible components that a
slope region may consist of. The two prototypes described are: (a) Prototype 1 (inclined
slope region) and (b) Prototype 0 (horizontal slope region).
The prototypes help to model the following components and their connection with the
boundary:
1. monotonic path connecting the local extremum and the outer boundary
2. connection of holes in the region with the outer boundary
3. connection of holes on the monotonic path connecting the local extremum and the
outer boundary
In all the above cases, the inner boundary connects the component with the outer
boundary such that the holes are excluded from the topological interior of the slope
region. This makes the slope region homeomorphic to a disc. The later part of the paper
explains the modeling of multiple monotonic paths on a single monotonic path connecting
a local extremum and the outer boundary.
The last part of the selected publication focuses on the consequence of the presence of a
saddle point on the boundary of the slope region. It emphasizes the significance that a
saddle point on the boundary of a slope region (denoted as S1) guarantees the presence
of at least one more slope region adjacent to the slope region S1.
4.2.2 Similarity and differences between the Prototypes
In this section, we discuss the similarities and differences between the two prototypes
and the different types of holes. The majority of the components, namely the local
maximum, the local minimum, and the holes are the same in both the prototypes of the
slope region. The outer boundary accounts for the major difference between the two
36
4.3. Paper C - Characterizing slope regions.
prototypes from the graph-representation point of view. Prototype 1 corresponding to
the inclined slope region has an oriented outer boundary that associates with the two
monotonic paths. On the other hand, Prototype 0 corresponding to the horizontal slope
region has a non-oriented outer boundary associated with a closed level curve. Besides
the difference in the graph representation, there is a major difference in the flow of surface
contours inside the slope region. In Prototype 1, the contour lines (surface contours)
connecting the outer boundary have a gradient-like pattern such that there is a uniform
inequality between the adjacent contours. In contrast, the contour lines connecting the
outer boundary of prototype 0 have the same gray value throughout the slope region.
In simple words, one can imagine that the components engraved on an inclined plane result
in Prototype 1, and components engraved on a horizontal plane results in Prototype 0.
The holes are modeled such that the boundary of a hole is always a level curve. As a
consequence, the holes (irrespective of their type) always comply with Prototype 0.
Chapter 5 discusses the algorithm to decompose images into slope regions. But, by
knowing the fact that the slope region prototypes are the generalization of slope regions,
the two prototypes span the image. Alternatively, a slope complex (image surface) can
be constructed by combining the prototypes of the slope region.
4.3 Paper C - Characterizing slope regions.
"Characterizing slope regions." Gonzalez-Diaz, R., Batavia, D., Casablanca, R. M., &
Kropatsch, W. G. (2021). Journal of Combinatorial Optimization, (pp. 1-20), Springer.
4.3.1 Characteristics of a slope region
An image can be visualized as a 2.5D continuous surface defined by a continuous height
map (pixel-intensity map) is denoted by h : R2 → R. For the remaining of the thesis and
selected publications, the gray value pixel intensity map is denoted by g : R2 → R.
The paper begins with a clear distinction between the interior and the topological
interior of the slope region. It emphasizes the fact that the interior of the slope region is
homeomorphic to a disc besides the fact that the slope region geometrically encapsulates
the holes. It also explains the difference between the boundaries (the inner and the outer
boundary) and the frontier of the slope region.
The formal proof of the necessary conditions that a slope region must satisfy consists
of two parts: (a) constraints on the interior of the slope region and (b) the constraints
on the boundary of the slope region. Similarly, the Paper mentions three conditions
that a region needs to satisfy to be categorized as a slope region. The necessary and the
sufficient conditions are based on a simple checklist based on the:
1. presence of saddles inside the slope region
37
4. Characterization and Generalization of slope regions
2. presence of R-max and R-min (local maximum and local minimum with respect to
the region) inside the slope region.
3. classification of boundary as monotonic paths or level curves.
The above enumerations are associated with the key characteristic of the slope region
and are independent of the size, shape, and number of components inside the slope
region. The components mentioned in the enumeration play a major role in defining
the topology of the region. Moreover, the identification of the slope region is simplified
without scrutinizing the relationship between the points inside the slope region.
The later part of the paper explains the modeling of the slope region as homeomorphic
to a disc and the modeling of holes as explained in Paper B.
4.3.2 Non-unique decomposition into slope regions
The final part of Paper C (refer Fig. 4.1) displays the decomposition of a single image
into different combinations of the slope region. It expresses the flexibility offered by the
slope regions while decomposing an image, unlike the unique solution that is provided by
the watershed decomposition. This flexibility can be explained by continuing the example
of a beginner skiing downhill (see Section 2.6.1) and the path of water flowing downhill.
The path of the water flowing downhill is predictable and unique like the gradient descent.
The path of a beginner skier is not predictable and has multiple numbers of the monotonic
path to choose from while skiing downhill. These paths are associated with an edge (or
path) that decomposes the surface into regions. Similarly, the boundary of the slope
region can be optimized to achieve same desired results such as decomposition of an
image without holes, decomposition with a maximum number of holes, or decomposition
such that the regions are approximately of the same size, and amongst others. This could
be useful for applications like object matching using the structure of the object derived
by fixing the constraints for optimization.
38
4.3. Paper C - Characterizing slope regions.
(a) (b)
(c) (d)
Figure 4.1: (a) A digital image and, with the local minima, local maxima and saddle
plateaus surrounded, respectively, by blue, red and green closed curves. (b), (c) and (d)
Different slope-region decomposition of the same image. Reprinted from [GDBCK21]
with permission from Springer.
39

CHAPTER 5
Experiments and Results
This first part of this chapter (Section 5.2) discusses the Topology preserving Irregular
Image Pyramid (TIIP) algorithm mentioned in Paper D and the important results of
its implementation. The second part (Section 5.3) guides us through the solution that is
considered as a link between the ingeniously designed rules in the TIIP algorithm and
machine learning described in Paper E.
5.1 Motivation
This chapter focuses on the efficient computation of the slope region hierarchy using
a handcrafted method and discusses a potential extension towards a learning based
approach. Paper D describes the TIIP algorithm built on the foundation of the theory
mentioned in the previous chapters. The major motivation of implementing the TIIP
algorithm was to discover the importance of preserving the structure and the topology
of an image in image representation. Another aim was to achieve non-unique solutions
for decomposing an image into slope regions. This opens the possibility to optimize the
decomposition based on the different aspects such as the area or the slope regions, or the
common boundary between the two slope regions.
The TIIP algorithm consists of several ingeniously designed rules. These rules can be
satisfied by various implementation methods. Any modification in the implementation
method requires a deep understanding of the implementation. To avoid this, Paper E
focuses on deriving an objective function as a first step to learn a few of the many
ingeniously designed handcrafted rules. Besides, this rules are not comprehensible by
the computers, whereas the objective functions can be interpreted and processed by the
computers.
41
5. Experiments and Results
5.2 Paper D - Image = structure + few colors
"Image= structure+ few colors". Batavia, D., Gonzalez-Diaz, R., & Kropatsch, W. G.
(2021, January). In Joint IAPR International Workshops on Statistical Techniques in
Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR)
(pp. 365-375). Springer, Cham.
5.2.1 Topology preserving Irregular Image pyramid algorithm
The proposed Topology preserving Irregular Image Pyramid (TIIP) algorithm in Paper D
uses the edge contraction and the edge removal operation (Section 2.2.1) to build an
irregular image pyramid over the 4-adjacent neighborhood graph of an image. It uses the
combinatorial map (Section 2.3) as the data structure. A combinatorial map facilitates
the execution of multiple number of edge contractions and removals in parallel, provided
that the edges are combinatorially independent (Section 2.3.1). The parallel complexity
of the TIIP algorithm for building the irregular image pyramid is O(log d) where d is the
diameter of the largest object in the image. Broadly speaking, The TIIP algorithm is
based on the three fundamental rules as follows:
• Edges with the lower contrast are given priority for the edge contraction over the
edges with higher contrast.
• During the edge contraction operation, the critical vertices always survive.
• The edge removal operation should not generate disconnected graphs.
The edge contraction operation abide to a handcrafted pipeline in the following order:
1. Contraction of level curves on the boundary of the image.
2. Contraction of edges with contrast c(e) = 0 and LBP categorization of the plateau
regions.
3. Contraction of the remaining edges with contrast c(e) > 0.
Section 2 of Paper D explains the details of the algorithm and reasons for each enumeration
in the above handcrafted pipeline. The top level of the pyramid is a graph of critical
points and their connections that retains the structure of the input image. Therefore,
the number of vertices at the top level of the pyramid depends on the input image. The
number of critical vertices can be high for an image with high texture information, while
the number of critical vertices will be lower for smooth images like depth-map images.
Referring to the Barkeley image segmentation dataset [MFTM01], typically the top level
of the pyramid consists of approximately 12-30% of the vertices in the base level. The
top-down expansion of the pyramid using the structure and the color values of the critical
vertices results in the reconstructed image. The reconstructed image preserves the high
42
5.2. Paper D - Image = structure + few colors
frequency texture information of the original image, while a pastelization effect can be
observed in the regions with low contrast.
(a) Original image
(b) Reconstructed image from 12.9% of vertices at the top level of the pyramid.
Figure 5.1: Original and reconstructed image using the TIIP algorithm. Reprinted
from [BGDK20] with permission from Springer.
Fig 5.1(a) displays the original image (number 43074) from the Berkeley image segmenta-
tion dataset [MFTM01]. Fig. 5.1(b) shows the reconstructed image from the top level of
the pyramid consisting of 12.9% of vertices in the base of the pyramid. The reconstructed
image preserves the high frequency textures and the structural information present in the
original image, with very few artifacts. It confirms that the an image is a combination of
its structure and a few colors associated with the critical vertices. Further results and
statistical information related to the implementation for 30 different images from the
43
5. Experiments and Results
Berkeley image segmentation dataset [MFTM01] can be found in the Technical Report1
5.2.1.1 Reduction function and Expansion function
The reduction function is responsible for determining the gray value of the merged vertex
after the edge contraction operation. In contrast, the expansion function is responsible
for determining the gray values during the de-contraction operation, which is the inverse
operation of the edge contraction. The reduction function and the expansion function
play an important role during the construction and expansion of the irregular image
pyramid. Selecting an optimal reduction and expansion function may help to improve
the quality of the reconstructed image.
Averaging the gray values is one of the simplest example of the reduction function. By
averaging, the gray value g(w) of the merged vertex w after contracting the edge e(u, v)
will result in g(w) = (g(u) + g(v))/2. But this may result in changes to the orientation
of the edges initially incident to vertex u and v. Moreover, following the proposed TIIP
algorithm, the top level of the pyramid consists of critical vertices only and the gray
values of the critical vertices are preserved. Hence the reduction function does not play
an important role as the gray values of the critical vertices do not change. In simple
words, after contracting the edge e(u, v) the reduction function in the TIIP algorithm
follows:
• g(w) = g(u) if vertices u, v are non-critical vertices and vertex u is the randomly
selected surviving vertex.
• g(w) = g(u) where vertex u is a critical and vertex v is non-critical.
The expansion function is rather more interesting, and it may prove helpful in generating
reconstructed images that are nearly identical to the original image. In contrast to the
reduction function, the expansion function determines the gray value of vertex u and
v after de-contraction of vertex w. The de-contraction operation of vertex w results in
two vertices u and v connected by an edge e(u, v). The incident edges on vertex w are
divided between the vertices u and v depending on the structure. The simplest expansion
function is inheritance, where g(u) = g(v) = g(w). The implementation in Paper D
follows the inheritance expansion function. This works well for the binary images but
one can think of better options for gray scale and colored images.
In the case of a gray scale image, we know that the TIIP algorithm follows the fundamental
rule of giving priority to the edges with lower contrast for the edge contraction operation.
In simple words, the edges with the lowest contrast get contracted before the edges with
relatively higher contrast. In contrast, during the top-down expansion of the pyramid,
the edges with relatively higher contrast are de-contracted prior to the edges with low
contrast. The process of de-contraction follows the first come last served policy for the
1https://www.prip.tuwien.ac.at/people/darshan/more/publications/7TR.pdf
44
5.3. Paper E - A Step Towards Learning Contraction Kernels for Irregular Image Pyramid
contracted edges. Besides, at the top level of the pyramid, the paths connecting the
extrema are maximal monotonic paths only. Knowing the gray values of the end points of
the maximal monotonic path, non-linear interpolation could possibly be a better option
for determining the gray values during the de-contraction process. Though this claim
largely depends on the data, length of the maximal monotonic path and the contrast
across the endpoints of the monotonic path. Further experiments and research related to
the expansion function is left for the future work.
5.3 Paper E - A Step Towards Learning Contraction
Kernels for Irregular Image Pyramid
"A Step Towards Learning Contraction Kernels for Irregular Image Pyramid". Batavia,
D., Gonzalez-Diaz, R. and Kropatsch, W. In Proceedings of the 11th International
Conference on Pattern Recognition Applications and Methods (ICPRAM 2022), volume
1, (pp. 60-70), INSTICC, SciTePress, February 2022.
5.3.1 A step towards learning the contraction kernel
The ingeniously designed pipeline in the TIIP algorithm is responsible for prioritizing the
eligibility of the edges for the contraction operation. The actual selection of the contraction
kernel relies on the combinatorial dependencies between the eligible edges. In simple
words, the edges inside the plateau region (c(e) = 0) are given priority over the edges
with contrast c(e) > 0. The contraction process of edges with c(e) > 0 starts after all the
plateau regions are collapsed to their respective representative vertex. But depending on
the input data, there can be edges e(u, v) with c(e) > 0 that are independent of the edges
inside the plateau regions. Here, an edge e(u, v) is independent of the plateau region
L iff the closest distance d between the two vertices min(d(u, w), d(v, w)) ≥ 2, where
w ∈ L. Contraction of such independent edges with c(e) > 0 simultaneously with the
plateau region do not conflict the contraction of the plateau region or the categorization
of the plateau region (Def. 12 in Section 2.5.3). By doing so, a larger contraction kernel
can be computed that would lower the height of the pyramid. Paper E presents an
objective function that prioritizes the eligibility of the edges for the contraction operation
irrespective of the pipeline mentioned in Paper D.
The objective function is majorly based on the cost of the contraction kernel. The cost
of the contraction kernel is a combination of (a) the sum of the cost of the edges inside
the contraction kernel and (b) the size of the contraction kernel. The two parameters in
the cost function, namely the multiplier m and the Lagrange multiple λ, that allow to
control the cost of the contraction kernel. The cost of an edge e is a revamped version of
its contrast c(e) controlled by a multiplier m. While the size of the contraction kernel is
altered with the help of a Lagrange multiplier λ. The target of the objective function
is to realize the largest contraction kernel with the lowest cost from a set of possible
contraction kernels. The values of the parameters m and λ can be learned for a particular
dataset or can be adjusted to achieve a particular size and cost of the contraction kernel
45
5. Experiments and Results
for constructing a desirable irregular image pyramid. Meanwhile, the set of the potential
contraction kernel can be computed with the help of the dictionary of the connected
components of the contraction kernel.
One can claim that if the equivalent contraction kernel (a combination of two or more
contraction kernels) is optimal, then the individual contraction kernel at each level of
the pyramid will also be optimal. It would be a difficult task to prove this claim, but it
may assist in learning an optimal equivalent contraction kernel instead of individually
realizing the contraction kernels at each level of the pyramid.
5.3.2 Consequence of parameter values of the objective function
Paper E presents the results of connected component labelling (CCL) for justifying the
claim of adjusting the size and the cost of the contraction kernel by tuning the values
of the parameters (m and λ). Binary images after Gaussian blurring are used as input
(Fig. 5.2 (a)) and the outputs are the CCL (Fig. 5.2 (b)-(d)) that can be achieved by
varying the values of the parameters m and λ. By varying the values of the parameters,
the number of the edges eligible for the contraction changes and eventually will affect
the connected component labelling. In Fig. 5.2b, the number of connected components
(# CC) is 126 and the parameters are sensitive of the slightest contrast that is caused
due to Gaussian blur. The parameters for CCL in Fig. 5.2c are less sensitive to the
small contrast changes and results in 66 connected components. After further tuning
the parameters, the number of connected components can be lowered to 6 as shows in
Fig. 5.2d. Coincidentally the CCL in Fig. 5.2d matches with the CCL of the original
binary image without blurring. Note that the presented application is to show the changes
in the edges eligible for the contraction operation and its effect on CCL by tuning the
parameters. Image deblurring is not the ultimate goal of this application. The proposal
for the future work is to learn the parameter values for a training set and apply it over the
test set. The framework of the proposed approach is simple and it does not consist of the
convolution layers and activation functions present in deep neural networks. Therefore
the proposed approach might simplify the process of understanding the learning process.
Refer Technical Report2 for further experiments and statistical information that verifying
the claims in Paper E.
2https://www.prip.tuwien.ac.at/people/darshan/more/publications/9TR.pdf
46
5.3. Paper E - A Step Towards Learning Contraction Kernels for Irregular Image Pyramid
(a) input image after Gaussian blur
with std. dev. = 0.6
(b)
#CC = 126 for m = 0.15 and λ = 15
(c) #CC = 66 for m = 0.05 and λ = 25 (d) #CC = 6 for m = 0.01 and λ = 45
Figure 5.2: Connected component labelling of blurred binary image with different value
of parameter m and λ. Reprinted from [BGDK22] wih permission from SCITEPRESS.
47

CHAPTER 6
Concluding Remarks
In this concluding chapter the original contributions of this thesis are summarized and
possible future work is presented.
6.1 Conclusion
The theoretical contributions of this cumulative thesis are focused on the characterization,
representation, and generalization of the Slope regions. Paper C explains the important
characteristics of the slope region and the necessary conditions that a region should
satisfy to be categorized as a slope region. It also discusses various properties of the slope
region that helps to identify whether a region is a slope region or not. Paper B generalizes
the slope regions into two prototypes of the slope region. Irrespective of the geometrical
properties (like size, and shape) of the slope region and presence/absence/multiple
occurrences of the components of the slope region (the local maximum, the local minimum,
holes), every slope region can be categorized into either of the two prototypes of the
slope region. Moreover, Paper B introduces the novel concept of the inner boundary
(or the folded boundary) and makes a clear distinction between the inner boundary,
and the outer boundary. The concept of inner boundary is used to model the holes
that are geometrically encapsulated by the outer boundary of the slope region but are
topologically excluded from the interior of the slope region. The exclusion of holes from
the interior makes the slope region homeomorphic to a disc.
Using the properties of the slope region, Paper A introduces a method to detect the
structurally redundant connections (common boundary) between the adjacent slope
regions. Removal of the structurally redundant common boundary will combine the
two slope regions to form a merged slope region. The set of redundant connections is
a superset of the removal kernel. Besides, Paper A defines the orientation of the edges
in the Boundary adjacency graph (BAG) and discusses the vertices categories in the
BAG. The proposed approach for detecting the redundant edges is inspired by the vertex
49
6. Concluding Remarks
categories in the BAG. The approach is independent of the size and shape of the slope
regions. Since it relies on the local properties of the pair of slope regions, it can be
implemented in parallel. Removal of the redundant connections helps to lower the storage
memory, assists in a compact representation, and increases the efficiency of building the
slope region hierarchy.
Paper D describes an algorithm to build the hierarchy of the slope regions over a 4-
adjacent neighborhood graph of an image. It is recommended to use the combinatorial
map as the data structure, as it has the ability to capture the structure and allow parallel
processing. The parallel complexity of the algorithm is O(log d) where d is the diameter
of the largest object in the image. The top level of the pyramid consists of critical vertices
and connections between them. It preserves the structure and topology of the image.
The reconstructed image from the top level of the pyramid, suggests that an image is a
combination of its structure and a few colors that are associated with the critical points.
Paper E attempts to link the handcrafted algorithm from Paper D with the learning based
approaches broadening the scope of the concept. Paper E defines the cost of a contraction
kernel which depends on the cost of the edges in the contraction kernel and the size of the
contraction kernel. The objective function based on the cost of the contraction kernel is
responsible for finding the largest contraction kernel with minimal cost. Besides, Paper E
introduces a novel concept- the dictionary of connected components of the contraction
kernel. It claims that an optimal contraction kernel can be learned by combining the
dictionary of the connected components and the proposed objective function. This step
is envisioned as a step towards learning the contraction kernels for an irregular image
pyramid.
6.2 Future Work
The proposed theory on Slope complex and decomposition of surfaces into slope regions
is limited to 2-dimensional space only. I plan to extend the theory to higher dimensions.
By using the induction technique, the characteristics and properties of a slope region can
be proved for the nD slope manifold.
There is space for improvement in the quality of the reconstructed images. Better
reduction and expansion functions can be derived by incorporating the information from
the input data and analyzing it.
The top level of the pyramid consists of critical points only and the connections between
them can be further reduced by eliminating insignificant critical vertices. Eliminating the
critical points will simplify the topology and the structure of the image. It will assist in
a further compact representation, though the original topology and the structure of the
image will not be preserved anymore. This requires knowledge from the field of persistent
homology, a tool in computational topology which is responsible to measure and order
the topological features of the data.
50
6.2. Future Work
In the field of mathematics and graph theory, the Graph Edit Distance (GED) is commonly
used to measure the similarity between the two graphs. It depends on the insertion and
deletion of the edges and vertices. The concept of graph edit distance can be extended
to pyramid edit distance with the help of the cost of the contraction kernel defined in
Paper E.
Last but not least, the link between the TIIP algorithm and machine learning can be
further exploited to learn the contraction kernels for an irregular image pyramid. It opens
up the field of learning the pyramid to achieve better application specific results. Unlike
the commonly used CNN’s, the irregular image pyramids do not require convolution
layers and activation functions. This makes the framework easy to understand and may
help to reveal the features learned by the machine.
51

Bibliography
[BGDK20] Darshan Batavia, Rocio Gonzalez-Diaz, and Walter G Kropatsch. Image
= structure + few colors. In Structural, Syntactic, and Statistical Pattern
Recognition - Joint IAPR International Workshops, S+SSPR 2020, Padua,
Italy, January 21-22, 2021, Proceedings, volume 12644 of Lecture Notes in
Computer Science, pages 365–375. Springer, 2020.
[BGDK22] Darshan Batavia, Rocio Gonzalez-Diaz, and Walter G. Kropatsch. A step
towards learning contraction kernels for irregular pyramids. In Proceedings
of the 11th International Conference on Pattern Recognition Applications
and Methods - ICPRAM, volume 1, pages 60–70. INSTICC, SciTePress,
February 2022.
[BHR81] Peter J Burt, Tsai-Hong Hong, and Azriel Rosenfeld. Segmentation and
estimation of image region properties through cooperative hierarchial
computation. IEEE Transactions on Systems, Man, and Cybernetics,
11(12):802–809, 1981.
[BJK19] Darshan Batavia, Hladůvka Jiří, and Walter G Kropatsch. Partitioning
2D Images into Prototypes of Slope Region. In International Conference
on Computer Analysis of Images and Patterns, Lecture Notes in Computer
Science, pages 363–374. Springer, 2019.
[BK99] Luc Brun and Walter G. Kropatsch. Dual Contraction of Combinatorial
Maps. In Walter G. Kropatsch and Jean-Michel Jolion, editors, 2nd
IAPR-TC-15 Workshop on Graph-based Representation, pages 145–154.
OCG-Schriftenreihe, Österreichische Computer Gesellschaft, 1999. Band
126.
[BK01] Luc Brun and Walter Kropatsch. Introduction to combinatorial pyramids.
In Digital and image geometry, pages 108–128. Springer, 2001.
[BKCGD19] Darshan Batavia, Walter G Kropatsch, Rocio M Casablanca, and Ro-
cio Gonzalez-Diaz. Congratulations! dual graphs are now orientated!
In International Workshop on Graph-Based Representations in Pattern
Recognition, Lecture Notes in Computer Science, pages 131–140. Springer,
2019.
53
[BKGDC19] Darshan Batavia, Walter G. Kropatsch, Rocio Gonzalez-Diaz, and Rocio M.
Casblanca. Counting slope regions in surface graphs. In Peter M. Roth
Friedrich Fraundorfer and Fabian Schenk, editors, Computer Vision Winter
Workshop., pages 42–50. TU Graz, 2019.
[BL79] S Beucher and C Lantuejoul. International workshop on image processing:
Real-time edge and motion detection/estimation, 1979.
[Car09] Gunnar Carlsson. Topology and data. Bulletin of the American Mathe-
matical Society, 46(2):255–308, 2009.
[CCK+18] EJY Cayllahua Cahuina, Jean Cousty, Yukiko Kenmochi, A De Albu-
querque Araújo, and Guillermo Cámara-Chávez. Algorithms for hierarchi-
cal segmentation based on the felzenszwalb-huttenlocher dissimilarity. In
International Conference on Pattern Recognition and Artificial Intelligence,
2018.
[DCL20] Rafat Damseh, Farida Cheriet, and Frederic Lesage. Modeling the topology
of cerebral microvessels via geometric graph contraction. In 2020 IEEE 17th
International Symposium on Biomedical Imaging (ISBI), pages 1004–1008.
IEEE, 2020.
[Die97] Reinhard Diestel. Graph theory. 1997. Grad. Texts in Math, 1997.
[DMV17] Tamal Dey, Sayan Mandal, and William Varcho. Improved image classifi-
cation using topological persistence. In Proceedings of the conference on
Vision, Modeling and Visualization, pages 161–168, 2017.
[EH+08] Herbert Edelsbrunner, John Harer, et al. Persistent homology-a survey.
Contemporary mathematics, 453:257–282, 2008.
[EHNP03] Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci.
Morse-smale complexes for piecewise linear 3-manifolds. In Proceedings
of the nineteenth annual symposium on Computational geometry, pages
361–370. ACM, 2003.
[EHZ03] Herbert Edelsbrunner, John Harer, and Afra Zomorodian. Hierarchical
morse-smale complexes for piecewise linear 2-manifolds. Discrete and
computational Geometry, 30(1):87–107, 2003.
[FDCAM11] Elisa Ficarra, Santa Di Cataldo, Andrea Acquaviva, and Enrico Macii.
Automated segmentation of cells with ihc membrane staining. IEEE
Transactions on Biomedical Engineering, 58(5):1421–1429, 2011.
[GCV20] Elena Ghibaudi, Luigi Cerruti, and Giovanni Villani. Structure, shape,
topology: entangled concepts in molecular chemistry. Foundations of
chemistry, 22(2):279–307, 2020.
54
[GDBCK21] Rocio Gonzalez-Diaz, Darshan Batavia, Rocio M Casablanca, and Wal-
ter G Kropatsch. Characterizing slope regions. Journal of Combinatorial
Optimization, pages 1–20, 2021.
[Har69] Frank Harary. Graph theory, addison. Reading, MA, 1969.
[HH91] J.L. Helman and L. Hesselink. Visualizing vector field topology in fluid
flows. IEEE Computer Graphics and Applications, 11(3):36–46, 1991.
[HKNU17] Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl.
Deep learning with topological signatures. NIPS’17, page 1633–1643, Red
Hook, NY, USA, 2017. Curran Associates Inc.
[KCBGD19a] Walter G Kropatsch, Rocio M Casablanca, Darshan Batavia, and Rocio
Gonzalez-Diaz. Computing and reducing slope complexes. In International
Workshop on Computational Topology in Image Context, LNCS, pages
12–25. Springer, 2019.
[KCBGD19b] Walter G Kropatsch, Rocio M Casablanca, Darshan Batavia, and Rocio
Gonzalez-Diaz. On the space between critical points. In International
Conference on Discrete Geometry for Computer Imagery, LNCS, pages
115–126. Springer, 2019.
[KHI07] Walter G Kropatsch, Yll Haxhimusa, and Adrian Ion. Multiresolution
image segmentations in graph pyramids. In Applied Graph Theory in
Computer Vision and Pattern Recognition, pages 3–41. Springer, 2007.
[Koe84] Jan J Koenderink. The structure of images. Biological cybernetics,
50(5):363–370, 1984.
[Kov89] Vladimir A Kovalevsky. Finite topology as applied to image analysis.
Computer vision, graphics, and image processing, 46(2):141–161, 1989.
[Kro98] Walter G Kropatsch. Equivalent weighting functions to equivalent contrac-
tion kernels. In Sixth International Workshop on Digital Image Processing
and Computer Graphics: Applications in Humanities and Natural Sci-
ences, volume 3346, pages 310–320. International Society for Optics and
Photonics, 1998.
[LER95] Longin Latecki, Ulrich Eckhardt, and Azriel Rosenfeld. Well-composed
sets. Computer Vision and Image Understanding, 61(1):70–83, 1995.
[LGB+20] Wenqi Lu, Simon Graham, Mohsin Bilal, Nasir Rajpoot, and Fayyaz
Minhas. Capturing cellular topology in multi-gigapixel pathology images.
In Proceedings of the IEEE/CVF Conference on Computer Vision and
Pattern Recognition Workshops, pages 260–261, 2020.
55
[Lie91] Pascal Lienhardt. Topological models for boundary representation: a
comparison with n-dimensional generalized maps. Computer-aided design,
23(1):59–82, 1991.
[LLS19] Baotong Li, Honglei Liu, and Wenjun Su. Topology optimization techniques
for mobile robot path planning. Applied Soft Computing, 78:528–544, 2019.
[LPZ+20] S. Lou, L. Pagani, W. Zeng, X. Jiang, and P.J. Scott. Watershed segmen-
tation of topographical features on freeform surfaces and its application
to additively manufactured surfaces. Precision Engineering, 63:177–186,
2020.
[MDC+19] Jayanta Mukhopadhyay, Partha Pratim Das, Samiran Chattopadhyay,
Partha Bhowmick, and Biswa Nath Chatterji. Digital geometry in image
processing. Chapman and Hall/CRC, 2019.
[MFTM01] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A
database of human segmented natural images and its application to eval-
uating segmentation algorithms and measuring ecological statistics. In
Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE Interna-
tional Conference on, volume 2, pages 416–423. IEEE, 2001.
[MGGR13] Annette Morales-González and Edel B García-Reyes. Simple object recog-
nition based on spatial relations and visual features represented using
irregular pyramids. Multimedia tools and applications, 63(3):875–897,
2013.
[MSK15] Wacław Marzantowicz, Nelson Silva, and Marek Kaluba. On representation
of the reeb graph as a sub-complex of manifold. Topological Methods in
Nonlinear Analysis, 45(1):287–308, Mar. 2015.
[OPH96] Timo Ojala, Matti Pietikäinen, and David Harwood. A comparative study
of texture measures with classification based on featured distributions.
Pattern recognition, 29(1):51–59, 1996.
[PSO18] Adrien Poulenard, Primoz Skraba, and Maks Ovsjanikov. Topological func-
tion optimization for continuous shape matching. In Computer Graphics
Forum, volume 37, pages 13–25. Wiley Online Library, 2018.
[Ree46] Georges Reeb. Sur les points singuliers d’une forme de pfaff completement
integrable ou d’une fonction numerique [on the singular points of a com-
pletely integrable pfaff form or of a numerical function]. Comptes Rendus
Acad. Sciences Paris, 222:847–849, 1946.
[RM02] Sanjay Rana and Jeremy Morley. Surface networks. 2002.
56
[RM03] Xiaofeng Ren and Jitendra Malik. Learning a classification model for
segmentation. In Computer Vision, IEEE International Conference on,
volume 2, pages 10–10. IEEE Computer Society, 2003.
[SMK10] Dan Shao, LA Mateos, and WG Kropatsch. Irregular laplacian graph
pyramid. In Computer Vision Winter Workshop 2010 (Nove Hrady, Czech
Republic: Czech Pattern Recognition Society), 2010.
[SUDA20] Read Sandström, Diane Uwacu, Jory Denny, and Nancy M Amato.
Topology-guided roadmap construction with dynamic region sampling.
IEEE Robotics and Automation Letters, 5(4):6161–6168, 2020.
[Tes91] Using Irregular Tessellations. Hierarchical image analysis using irregu-
lar tessellations. IEEE transactions on pattern analysis and machine
intelligence, 13(4):307, 1991.
[Woo98] Joseph Wood. Modelling the continuity of surface form using digital
elevation models. In Proceedings of the 8th international symposium on
spatial data handling, pages 725–736. Vancouver, 1998.
[WYG+18] Xing Wei, Qingxiong Yang, Yihong Gong, Narendra Ahuja, and Ming-
Hsuan Yang. Superpixel hierarchy. IEEE Transactions on Image Processing,
27(10):4838–4849, 2018.
[WZS+15] Jarrell Waggoner, Youjie Zhou, Jeff Simmons, Marc De Graef, and Song
Wang. Topology-preserving multi-label image segmentation. In 2015 IEEE
Winter Conference on Applications of Computer Vision, pages 1084–1091.
IEEE, 2015.
[ZL21] Daoping Zhang and Lok Ming Lui. Topology-preserving 3d image seg-
mentation based on hyperelastic regularization. Journal of Scientific
Computing, 87(3):1–33, 2021.
57

Second Part
59

Paper A
Congratulations! Dual Graphs
Are Now Orientated!
Published in [BKCGD19] by Springer Nature.
Important notice: This is the electronic version of my thesis. It does not include
the selected papers in Second Part, but only their references.
61

Paper B
Partitioning 2D Images into
Prototypes of Slope Region
Published in [BJK19] by Springer Nature.
Important notice: This is the electronic version of my thesis. It does not include
the selected papers in Second Part, but only their references.
63

Paper C
Characterizing slope regions
Published in [GDBCK21] as an open access article by Journal of Combinatorial
Optimization, Springer
Important notice: This is the electronic version of my thesis. It does not include
the selected papers in Second Part, but only their references.
65

Paper D
Image = Structure + Few Colors
Published in [BGDK20] by Springer Nature.
Important notice: This is the electronic version of my thesis. It does not include
the selected papers in Second Part, but only their references.
67

Paper E
A step towards learning
Contraction Kernels for Irregular
Pyramids
Published in [BGDK22] by SCITEPRESS.
Important notice: This is the electronic version of my thesis. It does not include
the selected papers in Second Part, but only their references.
69
List of Figures
2.1 An example of edge contraction operation. . . . . . . . . . . . . . . . . . . 11
2.2 An example of edge removal operation. . . . . . . . . . . . . . . . . . . . . 12
2.3 An example of a simple graph encoded as combinatorial map. . . . . . . . 15
2.4 Correspondence between combinatorial map and navigation system. . . . 15
2.5 Digital image and its corresponding 2.5D continuous surface. . . . . . . . 17
2.6 Low frequency sampling of digital image in Fig. 2.5(a), and its corresponding
pair of dual graphs (RAG and BAG). . . . . . . . . . . . . . . . . . . . . 17
2.7 Encoding orientation of edges and bit switches. . . . . . . . . . . . . . . . 19
2.8 Plateau region and its vertex representation. . . . . . . . . . . . . . . . . 23
2.9 Inserting a hidden saddle. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.10 Significance of inner boundary. . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1 Example of merging two adjacent slope regions. . . . . . . . . . . . . . . . 32
3.2 Removing redundant edges after insertion of a hidden saddle vertex. . . . 33
3.3 Image 160068 from [MFTM01] containing 308000 edges eligible for the removal
kernel at the base level of the pyramid. . . . . . . . . . . . . . . . . . . . 33
4.1 (a) A digital image and, with the local minima, local maxima and saddle
plateaus surrounded, respectively, by blue, red and green closed curves. (b),
(c) and (d) Different slope-region decomposition of the same image. Reprinted
from [GDBCK21] with permission from Springer. . . . . . . . . . . . . . . 39
5.1 Original and reconstructed image using the TIIP algorithm. Reprinted
from [BGDK20] with permission from Springer. . . . . . . . . . . . . . . . 43
5.2 Connected component labelling of blurred binary image with different value
of parameter m and λ. Reprinted from [BGDK22] wih permission from
SCITEPRESS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
70
List of Tables
2.1 Consequences of edge contraction operation on graph G = (V, E) . . . . . 12
2.2 Consequences of edge removal operation on graph G = (V, E) . . . . . . . 13
2.3 Encoding adjacency relations into σ permutation and α involution of combi-
natorial maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 LBP categories of vertices with their corresponding surface illustrations. . 21
3.1 Consequences on RAG G due of edge contraction in G = ( V , E) . . . . 30
3.2 Consequences on RAG G due of edge removal in G = ( V , E) . . . . . . 31
71

Appendix
Curriculum Vitae
73

1Darshan Batavia
Curriculum Vitae
Personal Details
Name Darshan Batavia
Date of Birth June 3, 1994
Place of Birth Thane, India
Nationality India
Email address darshan@prip.tuwien.ac.at / bataviadarshan755@gmail.com
Home page: https://www.prip.tuwien.ac.at/people/darshan/more/home.html
Education Details
PhD (Computer Science – Pattern recognition and Image Processing) (since June 2018)
Technical University Vienna (TU Wien), Vienna, Austria.
MTech (Signal Processing) (2015 – 2017)
Dhirubhai Ambani Institute of Information and Communication Technology, Gujarat, India.
Qualified GATE 2015 with All India Rank – 3867 (2015)
Bachelor of Engineering. Electronics and Telecommunication (2011 – 2015)
Sinhgad Institute of Technology, Lonavala, Maharashtra, India.
Higher Secondary School (2009 – 2011)
Pune University
SSC Board (10th grade exams) (2009)
Publications
Darshan Batavia, and Aditya Tatu. Estimating graph topology from sparse graph signals with an 
application to image denoising. In 2017 IEEE 19th International Workshop on Multimedia Signal 
Processing (MMSP) (pp. 1-6). IEEE, October 2017.
Walter G Kropatsch, Rocio M Casablanca, Darshan Batavia, and Rocio Gonzalez-Diaz. Computing 
and reducing slope complexes. In International Workshop on Computational Topology in Image 
Context, LNCS, pages 12–25. Springer, 2019. 
Darshan Batavia, Walter G. Kropatsch, Rocio Gonzalez-Diaz, and Rocio M. Casblanca. Counting 
slope regions in surface graphs. In Computer Vision Winter Workshop., pages 42–50. TU Graz, 
2019.
Walter G Kropatsch, Rocio M Casablanca, Darshan Batavia, and Rocio Gonzalez-Diaz. On the 
space between critical points. In International Conference on Discrete Geometry for Computer 
Imagery, LNCS, pages 115–126. Springer, 2019. 
2Darshan Batavia
Darshan Batavia, Walter G Kropatsch, Rocio M Casablanca, and Rocio Gonzalez-Diaz. 
Congratulations! dual graphs are now orientated! In International Workshop on Graph-Based 
Representations in Pattern Recognition, Lecture Notes in Computer Science, pages 131–140. 
Springer, 2019
Darshan Batavia, Hladůvka Jiří, and Walter G Kropatsch. Partitioning 2D Images into Prototypes of 
Slope Region. In International Conference on Computer Analysis of Images and Patterns, Lecture 
Notes in Computer Science, pages 363–374. Springer, 2019 
Darshan Batavia, Rocio Gonzalez-Diaz, and Walter G Kropatsch. Image = structure + few colors. In 
Structural, Syntactic, and Statistical Pattern Recognition – Joint IAPR International Workshops, 
S+SSPR 2020, Padua, Italy, January 21-22, 2021, Proceedings, volume 12644 of Lecture Notes in 
Computer Science, pages 365–375. Springer, 2020. 
Gonzalez-Diaz, R., Batavia, D., Casablanca, R.M. and Kropatsch, W.G., 2021. Characterizing slope 
regions. Journal of Combinatorial Optimization, pp.1-20. 
Darshan Batavia, Rocio Gonzalez-Diaz, and Walter G. Kropatsch. A step towards learning 
contraction kernels for irregular pyramids. In Proceedings of the 11th International Conference on 
Pattern Recognition Applications and Methods – ICPRAM, volume 1, pages 60–70. INSTICC, 
SciTePress, February 2022. 
Career History
 Teaching Assistant – DAIICT (2015 – 2017)
 University Assistant in TU Wien (June 2018 – May 2022)
Career Related Activity
 Reviewer in International Conference on Pattern Recognition 2022
 Reviewer in The Visual Computing Journal 2022
 Reviewer in Applications of Intelligent Systems 2019
77