#  The Connectedness Homomorphism between Discrete Morse Complexes

Chong Zheng  Faculty of Science and Engineering, Waseda University, Ohkubo,
Shinkuju-ku, Tokyo, 169-8555 Japan<EMAIL_ADDRESS>
###### Abstract.

Given two discrete Morse functions on a simplicial complex, we introduce the
connectedness homomorphism between the corresponding discrete Morse complexes.
This concept leads to a novel framework for studying the connectedness in
discrete Morse theory at the chain complex level. In particular, we apply it
to describe a discrete analogy to ‘cusp-degeneration’ of Morse complexes. A
precise comparison between smooth case and our discrete cases is also given.

###### Key words and phrases:

Discrete Morse theory, Connectedness, Connectedness homomorphism, Birth-death
transitions.

##  1\. Introduction

Let $K$ be a finite simplicial complex, with $f_{1},f_{2}:K\to\mathbb{R}$
representing two distinct  discrete Morse functions on $K$. In our previous
paper [17], we have studied the (strong) connectedness  between an
$f_{1}$-critical simplex $\tilde{\sigma}_{1}$ and an $f_{2}$-critical simplex
$\tilde{\sigma}_{2}$, which characterizes the structure of the gradient vector
fields on $K$ existing between these two simplices.

Namely, at simplicial complex level, we study the uniqueness of gradient path,
the uniqueness and the quantity of strong connectedness, and their correlation
with the Betti numbers and the Euler number of $K$ [17, 18]. Note that the
concept was inspired by a similar one in King-Knudson-Mramor Kosta [11], but
there are some crucial differences (see Section 2.3).

In this paper, our primary aim is to establish a theoretical framework for
understanding the connectedness between discrete Morse functions $f_{1}$ and
$f_{2}$ at the chain complex level. First, we define the connectedness
homomorphism  between two discrete Morse complexes corresponding to $f_{1}$
and $f_{2}$, derived from the simplex connectedness between corresponding
critical simplices. Then, we explore some fundamental properties of
connectedness homomorphisms In particular, using these properties, we give an
appropriate description of a discrete analogy, called birth-death transition,
to the cusp-degeneration of critical points of smooth Morse function in Cerf
theory [5]. In case of smooth Morse theory, Laudenbach [14] described the
change of smooth Morse complexes before and after a cusp-degeneration. We
demonstrate that a similar description is applicable within the context of
discrete Morse functions. Hence, through Gallais [9] and Benedetti [3], our
results recover the main results of [14] but also work for a wider context of
any simplicial complexes. This is one of the initial steps in seeking for a
discrete analogue to smooth Cerf theory.

In Section 2, we provide a concise overview of the preliminaries, including
the fundamentals of discrete Morse theory which are introduced by Forman [7,
8], as well as the concepts of connectedness and strong connectedness of [17].
In Section 3, we introduce the connectedness homomorphism between two discrete
Morse complexes, and investigate some fundamental properties of it. In section
4, we apply the connectedness homomorphism to describe the birth-death
transition of the discrete Morse complexes, especially, in Theorem 4.2, we
prove that when the connectedness homomorphisms are birth-death transitions,
they are chain maps. Furthermore, we establish a clear relationship between
the cusp-degeneration in smooth case and that in our discrete case in
Proposition 4.5.

##  2\. Preliminaries

This section presents fundamental concepts for this paper.

###  2.1. Discrete Morse Functions and Gradient Vector Fields

For a comprehensive understanding of discrete Morse theory  and discrete Morse
homology, one may refer to [7, 8, 13, 16].

Let $K$ be a simplicial complex, $K_{p}$ be the set of $p$-dimensional
simplices. We use $\sigma^{(p)}$ to represent a $p$-dimensional simplex. When
the context is clear, we omit the superscript $p$. Notations $\tau\prec\sigma$
and $\tau\succ\sigma$ are used to denote $\tau$ is a face of $\sigma$ and
$\sigma$ is a face of $\tau$, respectively.

A discrete Morse function $f:K\to\mathbb{R}$ satisfies for all $\sigma\in
K_{p}$,

  1. (1)

$\displaystyle\\#\\{\tau^{(p+1)}\succ\sigma\,|\,f(\tau)\leq f(\sigma)\\}\leq
1;$

  2. (2)

$\displaystyle\\#\\{v^{(p-1)}\prec\sigma\,|\,f(\sigma)\leq f(v)\\}\leq 1,$

where $\\#$ denotes the cardinality of a set.

We say a simplex $\sigma^{(p)}$ is a critical $p$-dimensional simplex (of $f$)
if

  1. (1)

$\displaystyle\\#\\{\tau^{(p+1)}\succ\sigma\,|\,f(\tau)\leq f(\sigma)\\}=0;$

  2. (2)

$\displaystyle\\#\\{v^{(p-1)}\prec\sigma\,|\,f(\sigma)\leq f(v)\\}=0.$

If $\sigma$ is a critical simplex, then we call $f(\sigma)$ a critical value
of $f$. Conversely, if a simplex $\sigma$ is not critical, then we say that
$\sigma$ is a non-critical simplex, and $f(\sigma)$ is a non-critical value.
We define

$Cr_{q}(f):=\\{\sigma\in K_{q}\,|\,\sigma^{(q)}\text{ is
}f\text{-critical}\\}$

be the set of $q$-dimensional $f$-critical simplices.

A gradient vector field $V$ corresponding to $f$ is the collection of pairs
$(\alpha^{(p)},\beta^{(p+1)})$ satisfying $\alpha\prec\beta$ and
$f(\alpha)\geq f(\beta)$. We call such a pair $(\alpha,\beta)$ a gradient
pair.

A gradient $V$-path is a sequence of simplices

$\alpha_{0}^{(p)},\beta_{0}^{(p+1)},\alpha_{1}^{(p)},\beta_{1}^{(p+1)},\cdots,\beta_{r}^{(p+1)},\alpha_{r+1}^{(p)}$

such that for each $i=0,\cdots,r$, $(\alpha^{(p)},\beta^{(p+1)})\in V$ and
$\beta_{i}^{(p+1)}\succ\alpha_{i+1}^{(p)}\neq\alpha_{i}^{(p)}.$

We denote a gradient $V$-path $\gamma$ consisting of $p$ and
$(p+1)$-dimensional simplices from $\alpha_{0}^{(p)}$ to $\alpha_{r+1}^{(p)}$
by

$\gamma:\alpha_{0}^{(p)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V(p,p+1)}}{\scriptscriptstyle}}\alpha_{r+1}^{(p)}.$

Note that we can also take any $(p+1)$-dimensional simplex $\beta_{0}^{(p+1)}$
as the starting simplex, and $\beta_{r}^{(p+1)}$ as the ending simplex. Thus,
we can denote the corresponding path consisting of $p$ and $(p+1)$-dimensional
simplices by

$\gamma:\beta_{0}^{(p+1)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V(p,p+1)}}{\scriptscriptstyle}}\beta_{r}^{(p+1)}.$

###  2.2. Morse Complexes and Discrete Morse Complexes

For details of Morse theory and Morse complexes, one may refer to [15, 10].
Let $M$ be a compact manifold and $\phi:M\to\mathbb{R}$ be a Morse function.
The Morse complex has chain groups  $S_{i}^{\phi}(M)$ as the span of the
critical points of index $i$. The boundary homomorphisms
$\partial_{i}^{\phi}:S_{i}^{\phi}\to S_{i-1}^{\phi}$ are defined in terms of
the gradient flow lines of $-\nabla\phi$. More precisely, let $p$ be a
critical point of $\phi$ of index $i$, then
$\partial_{i}^{\phi}(p):=\sum_{\gamma}m(\gamma)\gamma(p),$ where $\gamma(p)$
is a flow from $p$ to a critical point of index $i-1$; and $m(\gamma)=\pm 1$
depending on the orientation. The Morse complex is defined as
$\\{S_{\ast}^{\phi}(M),\partial^{\phi}_{\ast}\\}$, and is isomorphic to the
ordinary homology.

A discrete version of Morse-Smale complex is first constructed by Forman [7].
As a discrete analogy to the Morse complex in ordinary Morse theory, the
$q$-dimensional chain groups are obtained by spanning $q$-dimensional critical
simplices, and the boundary homomorphisms are obtained by the gradient flows
between simplices of consecutive dimensions. Precise definitions are given as
follows.

From now on, we suppose that each simplex of $K$ is oriented. Then, given
simplices $\alpha^{(q-1)}\prec\sigma^{(q)}$, we use $[\sigma:\alpha]$ to
represent the incidence number of $\sigma$ and $\alpha$; $[\sigma:\alpha]=\pm
1$.

Let $f:K\to\mathbb{R}$ be a discrete Morse function. We first define the chain
group of discrete Morse complex $C_{q}^{f}=C_{q}^{f}(K)$ as the free Abelian
group generated by $\sigma_{i}\in Cr_{q}(f)$, and the $q$-th boundary
homomorphism $\partial_{q}^{f}:C_{q}^{f}\to C_{q-1}^{f}$ is defined as the
linear extension of

$\partial_{q}^{f}(\sigma_{i}):=\sum_{\alpha\in
Cr_{q-1}(f)}n^{f}(\sigma_{i},\alpha)\alpha.$

Here, $n^{f}(\sigma_{i},\alpha)$ is given by

$n^{f}(\sigma_{i},\alpha):=\sum_{\gamma}m(\gamma),$

where $\gamma$ runs over all gradient paths
$\sigma_{i}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V(q-1,q)$}}{$\scriptscriptstyle$}}\alpha$,
$m(\gamma):=[\sigma_{i}:\tilde{\alpha}]$ and $\tilde{\alpha}$ is the maximal
face of $\sigma_{i}$ in $\gamma$. We call $n^{f}(\sigma_{i},\alpha)$ the
connectedness coefficient  between $\sigma_{i}$ and $\alpha$. In particular,
$\partial_{0}^{f}$ is defined as the zero homomorphism.

It is known that $\partial^{f}\circ\partial^{f}=0$ [7, Theorem 7.1]. Hence,
$\\{C_{\ast}^{f},\partial_{\ast}^{f}\\}$ forms the discrete Morse chain
complex, and the discrete Morse homology is defined as

$H_{\ast}:=\frac{\text{Ker}\partial^{f}_{\ast}}{\text{Im}\partial^{f}_{\ast}}.$

Furthermore, discrete Morse homology is isomorphic to the ordinary homology
[7, Theorem 7.1].

###  2.3. $\partial$-Connectedness and Strong Connectedness of Critical
simplices

Let $f_{1},f_{2}:K\to\mathbb{R}$ be two different discrete Morse functions on
$K$, and $V_{1}$, $V_{2}$ be the corresponding gradient vector field,
respectively. For $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$ and
$\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$, we say that $\tilde{\sigma}_{1}$ is
$\partial$-connected to $\tilde{\sigma}_{2}$ if

  * •

when $q\neq 0$, there is an $f_{1}$-gradient path

$\tilde{\sigma}_{1}^{(q)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V_{1}(q-1,q)}}{\scriptscriptstyle}}\tilde{\sigma}_{2}^{(q)};$

  * •

when $q=0$, there is an $f_{2}$-gradient path

$\tilde{\sigma}_{1}^{(0)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V_{2}(0,1)}}{\scriptscriptstyle}}\tilde{\sigma}_{2}^{(0)}.$

We call this relationship $\partial$-connectedness, and denote it by
$\tilde{\sigma}_{1}\to\tilde{\sigma}_{2}.$ From now, when the context is
clear, we only call this the connectedness between simplices.

Furthermore, we say that $\tilde{\sigma}_{1}$ is strongly connected to
$\tilde{\sigma}_{2}$ if $\tilde{\sigma}_{1}$ is connected to
$\tilde{\sigma}_{2}$ and $\tilde{\sigma}_{2}$ is connected to
$\tilde{\sigma}_{1}$, denoted by
$\tilde{\sigma}_{1}\leftrightarrow\tilde{\sigma}_{2}$.

We remark that $0$-dimensional connectedness from $\tilde{\sigma}_{1}$ to
$\tilde{\sigma}_{2}$ involves the gradient paths on $V_{2}$ that is different
from other dimensional cases. Fundamental properties of $0$-dimensional
simplex connectedness are studied in our previous paper [17]. With regard to
the (strong) $\partial$-connectedness, several properties including the
relationship between the strong connectedness number and the Euler
characteristic, are investigated in [17, Section 4].

Also, we note that our definition of $\partial$-connectedness is motivated by
a similar proceeding notion introduced in [11]. However, it is important to
note that the two definitions are not identical for general cases. Compared
with the connectedness in [11], which consists of three consecutive
dimensions, the $\partial$-connectedness in this paper specifies a
“direction”, thus only two dimensions are involved.

##  3\. The connectedness homomorphism between discrete Morse complexes

In this section, we construct the connectedness homomorphism between discrete
Morse complexes of the same simplicial complex.

###  3.1. Connectedness Homomorphisms

Suppose that we are given discrete Morse functions
$f_{1},f_{2}:K\to\mathbb{R}$ on a simplicial complex $K$. Let $m$ be the
dimension of $K$. We denote the discrete Morse complexes by
$\\{C_{\ast}^{f_{1}}=C_{\ast}^{f_{1}}(K),\partial_{\ast}^{f_{1}}\\}$ and
$\\{C_{\ast}^{f_{2}}=C_{\ast}^{f_{2}}(K),\partial_{\ast}^{f_{2}}\\}$
corresponding to $f_{1}$ and $f_{2}$, respectively.

######  Definition 3.1.

Let $q=1,2\ldots,m$. The $q$-dimensional connectedness homomorphism from
$C_{q}^{f_{1}}$ to $C_{q}^{f_{2}}$

$h_{q}:C_{q}^{f_{1}}\to C_{q}^{f_{2}}$

is defined as the linear extension of

$h_{q}(\tilde{\sigma}_{1}):=\sum_{\sigma_{j}\in
Cr_{q}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\sigma_{j},$

where $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$.

In particular, when $q=0$, we use $\tilde{v}_{1}$ to denote a $0$-dimensional
$f_{1}$-critical simplex, and the $0$-dimensional connectedness homomorphism
$h_{0}:C_{0}^{f_{1}}\to C_{0}^{f_{2}}$ is defined as the linear extension of

$h_{0}(\tilde{v}_{1}):=\sum_{v_{j}\in
Cr_{0}(f_{2})}n^{f_{2}}(\tilde{v}_{1},v_{j})v_{j}.$

Note that the connectedness coefficient $n^{f_{2}}(\tilde{v}_{1},v_{j})$ is
associated with the connectedness from $\tilde{v}_{1}$ to $v_{j}$, which is on
the gradient vector field $V_{2}$ obtained from $f_{2}$. Technically, when
$\tilde{\sigma}_{1}=\tilde{\sigma}_{2}$, we let

$n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})=n^{f_{2}}(\tilde{\sigma}_{2},\tilde{\sigma}_{1})=1.$

On the other hand, we can also define the connectedness homomorphism from
$C_{q}^{f_{2}}$ to $C_{q}^{f_{1}}$ with a parallel way as

$g_{q}:C_{q}^{f_{2}}\to C_{q}^{f_{1}}.$

Thus, we can use the diagram in Figure 1 to denote the connectedness
homomorphisms and the boundary homomorphisms of the two chain complexes.

${{\vdots}}$${{\vdots}}$${{\vdots}}$${{C_{q+1}^{f_{1}}}}$${{C_{q+1}^{f_{2}}}}$${{C_{q+1}^{f_{1}}}}$${{C_{q}^{f_{1}}}}$${{C_{q}^{f_{2}}}}$${{C_{q}^{f_{1}}}}$${{C_{q-1}^{f_{1}}}}$${{C_{q-1}^{f_{2}}}}$${{C_{q-1}^{f_{1}}}}$${{\vdots}}$${{\vdots}}$${{\vdots}}$$\scriptstyle{h_{q+1}}$$\scriptstyle{\partial_{q+1}^{f_{1}}}$$\scriptstyle{\partial_{q+1}^{f_{2}}}$$\scriptstyle{g_{q+1}}$$\scriptstyle{\partial_{q+1}^{f_{1}}}$$\scriptstyle{h_{q}}$$\scriptstyle{\partial_{q}^{f_{1}}}$$\scriptstyle{\partial_{q}^{f_{2}}}$$\scriptstyle{g_{q}}$$\scriptstyle{\partial_{q}^{f_{1}}}$$\scriptstyle{h_{q-1}}$$\scriptstyle{g_{q-1}}$
Figure 1. Connectedness homomorphisms and the boundary homomorphisms.

Regarding to the connectedness homomorphism, it is natural to ask the follows:

  1. (1)

Under what conditions $h=\\{h_{q}\\}_{q}$ and $g=\\{g_{q}\\}_{q}$ are chain
maps? $h$ is called a chain map if for any $q>0$, $\partial^{f_{2}}_{q}\circ
h_{q}=h_{q-1}\circ\partial^{f_{1}}_{q}$. It is equivalent to that the diagram
in Figure 1 is commutative.

  2. (2)

Under what conditions $h$ and $g$ are inverse to each other, i.e. $h\circ
g=g\circ h=\text{id}$?

  3. (3)

Under what conditions $h$ and $g$ are faithful connectedness homomorphisms?
(See Definition 3.5)

In the following subsections, we give and explain partial solutions to those
questions. A more general answer to those questions requires a comprehensive
understanding of connectedness at the simplicial level, thus more discussion
will be given in [18].

We begin with directly computing the equation of chain map by employing the
definition. The following fundamental but important necessary and sufficient
condition to make $h$ a chain map is straightforward by simple computations.

######  Proposition 3.2.

The following $(1)$ and $(2)$ are equivalent:

  1. (1)

$h$ is a chain map.

  2. (2)

For any $q>1$ and any $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$,

$\displaystyle\sum_{\sigma_{j}\in
Cr_{q}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\sum_{\alpha_{i}\in
Cr_{q-1}(f_{2})}n^{f_{2}}(\sigma_{j},\alpha_{i})\alpha_{i}=$
$\displaystyle\sum_{\alpha_{\ell}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{\ell})\sum_{\alpha_{i}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\alpha_{\ell},\alpha_{i})\alpha_{i};$

and for $q=1,$

$\displaystyle\sum_{\sigma_{j}\in
Cr_{1}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\sum_{\alpha_{i}\in
Cr_{0}(f_{1})}n^{f_{2}}(\sigma_{j},\alpha_{i})\alpha_{i}=$
$\displaystyle\sum_{\alpha_{\ell}\in
Cr_{0}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{\ell})\sum_{\alpha_{i}\in
Cr_{0}(f_{2})}n^{f_{2}}(\alpha_{\ell},\alpha_{i})\alpha_{i}.$

###### Proof.

We calculate both sides for any $q>1$ and $\tilde{\sigma}_{1}\in
Cr_{q}(f_{1})$:

$\displaystyle\partial^{f_{2}}\circ h_{q}(\tilde{\sigma}_{1})$
$\displaystyle=\partial^{f_{2}}(\sum_{\sigma_{j}\in
Cr_{q}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\sigma_{j})$
$\displaystyle=\sum_{\sigma_{j}\in
Cr_{q}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\partial^{f_{2}}(\sigma_{j})$
$\displaystyle=\sum_{\sigma_{j}\in
Cr_{q}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\sigma_{j})\sum_{\alpha_{i}\in
Cr_{q-1}(f_{2})}n^{f_{2}}(\sigma_{j},\alpha_{i})\alpha_{i},$

and

$\displaystyle h_{q-1}\circ\partial^{f_{1}}(\tilde{\sigma}_{1})$
$\displaystyle=h_{q-1}(\sum_{\alpha_{\ell}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{\ell})\alpha_{\ell})$
$\displaystyle=\sum_{\alpha_{\ell}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{\ell})h_{q-1}(\alpha_{\ell})$
$\displaystyle=\sum_{\alpha_{\ell}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{\ell})\sum_{\alpha_{i}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\alpha_{\ell},\alpha_{i})\alpha_{i}.$

We omit the proof for the case $q=1$, as it can be derived through similar
computations.

∎

###  3.2.  Connectedness and Connectedness Homomorphism

In this subsection, we discuss the relationship between the connectedness of
critical simplices and the connectedness homomorphism.

The connectedness between two critical simplices only depends on the presence
of discrete gradient flows. In contrast, the derivation of the connectedness
homomorphism, as informed by the connectedness coefficient, needs not only the
verification of connectedness but also an understanding of the quantity and
the orientation of such connectedness. Hence, it is notably to remark that the
relationship between simplex connectedness and the connectedness homomorphism
is significantly influenced by the choice of the coefficient in the
calculation of the connectedness coefficient.

The number of gradient paths connecting $\sigma_{1}$ to $\sigma_{2}$ is
essential for determining the connectedness coefficient
$n^{f_{1}}(\sigma_{1},\sigma_{2})$. When there are multiple such gradient
paths, those paths form cycles within the simplicial complex. Although the
isomorphism between discrete Morse homology and ordinary (simplicial) homology
is natural, the geometric information contained in those two kinds of cycles
are different. A discrete Morse cycle always contains a simplicial cycle.
However, a simplicial cycle may not contain a discrete Morse cycle.

The following lemma shows a fundamental relationship between those cycles and
$\sigma_{2}$.

######  Lemma 3.3.

Suppose that the $V_{1}$-gradient paths connecting $\sigma_{1}\in
Cr_{q}(f_{1})$ to $\sigma_{2}\in Cr_{q}(f_{2})$ form cycles within $K$. Then,
$\sigma_{2}$ does not participate in any cycle.

###### Proof.

A straightforward fact from the definition of connectedness is that if
$\sigma_{1}$ is connected to $\sigma_{2}$ and $\sigma_{1}\neq\sigma_{2}$, then
$\sigma_{2}$ is not critical with respective to $f_{1}$. Thus, by the
definition of discrete Morse function, there exists only one
$\alpha_{2}^{(q-1)}\prec\sigma_{2}$ that is in the $V_{1}$-gradient pair
$(\alpha_{2},\sigma_{2})$. Consequently, $\sigma_{2}$ can not participate in
any of the cycles.

∎

Since for each gradient path

$\gamma:\sigma_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V_{1}(q-1,q)}}{\scriptscriptstyle}}\sigma_{2},$

$m(\gamma)$ equals $\pm 1$, the parity (odd or even) of the number of such
gradient paths depends on the connectedness coefficient. More precisely,

  * •

$n^{f_{1}}(\sigma_{1},\sigma_{2})=0$ implies the number of gradient paths is
even; and

  * •

$|n^{f_{1}}(\sigma_{1},\sigma_{2})|=1$ implies the number of gradient paths is
odd, where $|\cdot|$ denotes the absolute value.

On the contrary, the validity of these statements may be false due to the
potential presence of torsion in $K$. However, if calculations are performed
using coefficient $\mathbb{Z}_{2}$, then the converse of above statements
holds true. On the other hand, when the homology of $K$ consists of torsion
element, the connectedness coefficient $|n^{f_{1}}(\sigma_{1},\sigma_{2})|$
may equal to $k>1$.

Also, $n^{f_{1}}(\sigma_{1},\sigma_{2})\neq 0$ implies $\sigma_{1}$ is
connected to $\sigma_{2}$. However, the converse does not hold.

###  3.3. Faithful Homomorphisms

In further investigations and applications of the connectedness between
$f_{1}$ and $f_{2}$, it is necessary to first establish both connectedness
homomorphisms $h$ and $g$ as chain maps. The concepts of weak faithfulness and
faithfulness are introduced to create a locally one-to-one correspondence of
simplex connectedness, which is the case when $\tilde{\sigma}_{1}$ is only
connected to one $\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$ in Proposition 3.2 (2).

######  Definition 3.4.

Let $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$ and $\tilde{\sigma}_{2}\in
Cr_{q}(f_{2})$. We say $\tilde{\sigma}_{1}$ is weakly faithful to
$\tilde{\sigma}_{2}$ if

$h_{q}(\tilde{\sigma}_{1})=n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})\tilde{\sigma}_{2},$

where $n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})\neq 0$.

Note that when $q=0$, the connectedness coefficient is associated with
$f_{2}$.

Let $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$ and $\tilde{\sigma}_{2}\in
Cr_{q}(f_{2})$ be weakly faithful to each other. When the computations are
performed with coefficient $\mathbb{Z}_{2}$, then
$n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})=n^{f_{2}}(\tilde{\sigma}_{2},\tilde{\sigma}_{1})=1.$

Next, we define a stronger correspondence between $\tilde{\sigma}_{1}$ and
$\tilde{\sigma}_{2}$ than the weak faithfulness as follows.

######  Definition 3.5.

Let $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$ and $\tilde{\sigma}_{2}\in
Cr_{q}(f_{2})$. We say $\tilde{\sigma}_{1}$ is  faithful to
$\tilde{\sigma}_{2}$ if $\tilde{\sigma}_{1}$ is weakly faithful to
$\tilde{\sigma}_{2}$, and

$\sum_{\alpha_{1}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{1})\sum_{\alpha_{2}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\alpha_{1},\alpha_{2})\alpha_{2}=\sum_{\alpha_{2}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})n^{f_{2}}(\tilde{\sigma_{2}},\alpha_{2})\alpha_{2}.$

If for any $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$, there exists
$\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$ such that $\tilde{\sigma}_{1}$ is
faithful to $\tilde{\sigma}_{2}$, then we call $h_{q}$ a faithful
homomorphism. Furthermore, if any $q\in\mathbb{N}$, $h_{q}$ is faithful, then
we say $h$ is faithful.

With regard to the zero-dimensional connectedness homomorphism $h_{0}$, we
present the following proposition to show a basic property of $h_{0}$.

######  Proposition 3.6.

$h_{0}$ is a faithful homomorphism.

###### Proof.

By the definition of discrete Morse function, it is easy to see that for any
vertex $v_{1}\in Cr_{0}(f_{1})$, there exists a unique corresponding vertex
$v_{2}\in Cr_{0}(f_{2})$ such that $v_{1}$ is connected to $v_{2}$, implying
$h_{0}(v_{1})=\pm v_{2}$. Therefore, $h_{0}$ is faithful. ∎

The above proof also demonstrates that $h_{0}$ is injective. Furthermore,
under the consideration of coefficient $\mathbb{Z}_{2}$, $h_{0}$ can be
regarded as a well-defined mapping between the sets of critical vertices
$Cr_{0}(f_{1})$ and $Cr_{0}(f_{2})$.

######  Proposition 3.7.

Let $f_{1},f_{2}:K\to\mathbb{R}$ be discrete Morse functions and
$h_{q}:C_{q}^{f_{1}}(K)\to C_{q}^{f_{2}}(K)$ be the connectedness
homomorphisms. If $h$ is faithful, then $h$ is a chain map.

###### Proof.

For any $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$, suppose that
$\tilde{\sigma}_{1}$ is faithful to $\tilde{\sigma}_{2}$. We compute that

$\partial_{q}^{f_{2}}\circ h_{q}(\tilde{\sigma}_{1})=\sum_{\alpha_{2}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})n^{f_{2}}(\tilde{\sigma_{2}},\alpha_{2})\alpha_{2}.$

Also,

$h_{q-1}\circ\partial_{q}^{f_{1}}(\tilde{\sigma}_{1})=\sum_{\alpha_{1}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{1})\sum_{\alpha_{2}\in
Cr_{q-1}(f_{2})}n^{f_{1}}(\alpha_{1},\alpha_{2})\alpha_{2}.$

Therefore, by Definition 3.5, $h$ is a chain map.

∎

###  3.4. The Connectedness Homomorphism of Optimal Discrete Morse functions

The concept of faithfulness is introduced to establish a local one-to-one
correspondence between two gradient vector fields similar to the optimal
discrete Morse function case. Recall that, a discrete Morse function
$f:K\to\mathbb{R}$ is called optimal if for any $q\in\mathbb{N}$,
$\\#Cr_{q}(f)=\beta_{q}(K)$ [2].

######  Lemma 3.8.

Let $f_{1},f_{2}:K\to\mathbb{R}$ be optimal discrete Morse functions. For any
$\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$, there exists a unique
$\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$ such that $\tilde{\sigma}_{1}$ and
$\tilde{\sigma}_{2}$ are weakly faithful to each other.

###### Proof.

First, we note that any $q$-dimensional representative chain (of simplicial
homology) consists of at least one $q$-dimensional critical simplex. This fact
simply follows from the isomorphism between discrete Morse homology and
simplicial homology, and the discrete Morse inequalities.

Since $f_{1}$ is optimal, $\tilde{\sigma}_{1}$ corresponds to a
$q$-dimensional homology class $[h]$. The $f_{1}$-gradient flows starting from
$\tilde{\sigma}_{1}$ cover the whole cycle and flow to every $q$-dimensional
simplex in the cycle only once. Additionally, there exists a unique
$\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$ in the cycle, because $f_{2}$ is
optimal. Thus,

$h_{q}(\tilde{\sigma}_{1})=n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\sigma}_{2})\tilde{\sigma}_{2}=\pm\tilde{\sigma}_{1}.$

A parallel discussion to $g_{q}(\tilde{\sigma}_{2})$ completes the proof.

∎

######  Proposition 3.9.

If $f_{1},f_{2}:K\to\mathbb{R}$ are optimal discrete Morse functions, then $h$
and $g$ are faithful homomorphisms.

###### Proof.

When $f_{1}$ is optimal, for any $\tilde{\sigma}_{1}\in Cr_{q}(f_{1})$, the
Morse boundary

$\partial^{f_{1}}_{q}(\tilde{\sigma}_{1})=\sum_{\alpha_{1}\in
Cr_{q-1}(f_{1})}n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{1})\alpha_{i}=0.$

Thus, the coefficient $n^{f_{1}}(\tilde{\sigma}_{1},\alpha_{1})=0$, for each
$\alpha_{1}\in Cr_{q-1}(f_{1})$.

According to Lemma 3.8, there exists $\tilde{\sigma}_{2}\in Cr_{q}(f_{2})$
such that $\tilde{\sigma}_{1}$ is weakly faithful to $\tilde{\sigma}_{2}$.
Thus, we compute $\partial_{q}^{f_{2}}\circ
h_{q}(\tilde{\sigma}_{1})=h_{q-1}\circ\partial_{q}^{f_{1}}(\tilde{\sigma}_{1})=0.$

Therefore, $h$ is a faithful homomorphism. ∎

######  Corollary 3.10.

Let $f_{1}$ and $f_{2}$ be optimal discrete Morse functions. The following
statements hold true:

  1. (1)

$h$ and $g$ are chain maps;

  2. (2)

$h\circ g=g\circ h=\text{id}$.

The connectedness homomorphisms between optimal functions are particular cases
of faithfulness connectedness homomorphisms. Generally, if
$\tilde{\sigma}_{1}$ and $\tilde{\sigma}_{2}$ are faithful to each other, then
the connectedness coefficients
$n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\alpha}_{1})$ and
$n^{f_{2}}(\tilde{\sigma}_{2},\tilde{\alpha}_{2})$ are $0$, $1$ or $k>1$. When
discrete Morse functions $f_{1}$, $f_{2}$ are optimal, every connectedness
coefficient $n^{f_{1}}(\tilde{\sigma}_{1},\tilde{\alpha}_{1})$ equals $0$.

##  4\. Modification of the Discrete Morse complex near a birth-death point
via the connectedness homomorphism

While discrete Morse theory and ordinary Morse theory share many analogous
concepts, the definition of a critical simplex within discrete Morse theory
presents unique challenges, especially in the context of depicting a
“degenerate critical simplex”. In ordinary Morse theory, the analysis of a
degenerate critical point often involves a perturbation strategy. A
perturbation strategy aims to split the degenerate critical point into a pair
of distinct, non-degenerate critical points, thus facilitating further
investigation. We seek for a discrete analogy.

###  4.1. Birth-Death Transition of Discrete Morse Complexes

Now, let $f_{1},f_{2}$ be two discrete Morse functions different from a pair
of birth-death point. We then apply the connectedness homomorphisms between
$\\{C_{\ast}^{f_{1}}(K),\partial_{\ast}^{f_{1}}\\}$ and
$\\{C_{\ast}^{f_{2}}(K),\partial_{\ast}^{f_{2}}\\}$ to feature a discrete
version of the degeneration of critical points in the smooth case. This is a
fundamental yet natural scenario to explore before we consider about the
elementary cobordism of discrete Morse theory.

We initiate our exploration by defining the context in terms of discrete Morse
theory. This involves assuming that the chain complexes
$\\{C_{\ast}^{f_{1}}(K),\partial_{\ast}^{f_{1}}\\}$ and
$\\{C_{\ast}^{f_{2}}(K),\partial_{\ast}^{f_{2}}\\}$ satisfy the following
assumptions:

We fix a dimension $i$. Regarding to the number of $i$-dimensional simplices,
we assume

$\\#Cr_{i}(f_{1})=\\#Cr_{i}(f_{2})-1;$
$\\#Cr_{i-1}(f_{1})=\\#Cr_{i-1}(f_{2})-1.$

For dimension $q\neq i,i-1$, we assume that

$\\#Cr_{q}(f_{1})=\\#Cr_{q}(f_{2}).$

We denote the two redundant simplices $\tilde{\sigma}\in Cr_{i}(f_{2})$ and
$\tilde{\alpha}\in Cr_{i-1}(f_{2})$, and suppose that

$n^{f_{2}}(\tilde{\sigma},\tilde{\alpha})=k,$

where $k\in\mathbb{Z}$.

Regarding to the connectedness homomorphisms, we assume that for any
$\delta_{1}\in Cr_{q}(f_{1})$,

$h_{q}(\delta_{1})=\begin{cases}\delta_{1},&\text{ if }q\neq i;\\\
\delta_{1}+n^{f_{1}}(\delta_{1},\tilde{\sigma})\tilde{\sigma},&\text{ if
}q=i.\par\par\end{cases}$

On the other hand, for any $f_{2}$-critical simplex $\delta_{2}$, we let

$g_{q}(\delta_{2})=\begin{cases}\delta_{2},&\text{ if
}\delta_{2}\neq\tilde{\sigma},\tilde{\alpha};\\\ 0,&\text{ if
}\delta_{2}=\tilde{\sigma};\\\ \displaystyle-\sum_{\alpha\in
Cr_{i-1}(f_{1})}n^{f_{2}}(\tilde{\alpha},\alpha)\alpha,&\text{ if
}\delta_{2}=\tilde{\alpha}.\par\par\end{cases}$

Regarding to the boundary homomorphisms, we assume the following equations (1)
to (5) hold.

Namely, when $q\neq i,i+1\text{ and }\delta\neq\tilde{\alpha},$

(1) $\partial^{f_{1}}_{q}(\delta)=\partial^{f_{2}}_{q}(\delta).$

For any $\tau\in Cr_{i+1}(f_{2})$,

(2) $\partial_{i+1}^{f_{2}}(\tau)=\partial_{i+1}^{f_{1}}(\tau)+\sum_{\sigma\in
Cr_{i}(f_{1})}n^{f_{1}}(\tau,\sigma)\cdot
n^{f_{1}}(\sigma,\tilde{\sigma})\tilde{\sigma}.$

For any $\sigma\in Cr_{i}(f_{2})$ and $\sigma\neq\tilde{\sigma}$,

(3)
$\partial_{i}^{f_{2}}(\sigma)=\partial_{i}^{f_{1}}(\sigma)-n^{f_{1}}(\sigma,\tilde{\sigma})(k\tilde{\alpha}+\sum_{\alpha\in
Cr_{i-1}(f_{1})}k\cdot n^{f_{2}}(\tilde{\alpha},\alpha)\alpha).$

(4) $\partial_{i}^{f_{2}}(\tilde{\sigma})=k\tilde{\alpha}+\sum_{\alpha\in
Cr_{i-1}(f_{1})}k\cdot n^{f_{2}}(\tilde{\alpha},\alpha)\alpha.$

(5) $\partial_{i-1}^{f_{2}}(\tilde{\alpha})=\sum_{\alpha\in
Cr_{i-1}(f_{2})}n^{f_{2}}(\tilde{\alpha},\alpha)\sum_{\omega\in
Cr_{i-2}(f_{1})}n^{f_{1}}(\alpha,\omega)\omega.$

We can check that the above assumptions occur when we cancel the pair of
critical simplices $(\tilde{\sigma},\tilde{\alpha})$.

######  Definition 4.1.

Under the conditions specified, we call $h$ a birth transition and $g$ a death
transition. Particularly, when $k=1$, $h$ and $g$ are called the birth
transition of cusp type and the death transition of cusp type, respectively.

Note that in smooth case, $g$ corresponds to the cusp degeneration in Cerf
theory, where neighboring two critical points are cancelled at a cusp [5, 1].
See also Section 4.3.

######  Theorem 4.2.

Let $f_{1},f_{2}:K\to\mathbb{R}$ be discrete Morse functions, and $h$ and $g$
be the corresponding connectedness homomorphisms. If $h$ and $g$ are a birth
and death transition, respectively, then both $h$ and $g$ are chain maps.

###### Proof.

To prove $h$ is a chain map, we need to show for any $\delta\in
Cr_{q}(f_{1})$,

($*$) $\partial_{q}^{f_{2}}\circ
h_{q}(\delta)=h_{q-1}\circ\partial_{q}^{f_{1}}(\delta).$

We note that when $q\neq i-1,i$, $\delta$ is also $f_{2}$-critical, and
$h_{q}(\delta)=g_{q}(\delta)=\delta.$ Thus, if $q\neq i-1,i,i+1$, then by
Equation 1, $\partial_{q}^{f_{2}}\circ
h_{q}=\partial_{q}^{f_{1}}=\text{id}\circ\partial_{q}^{f_{1}}=h_{q-1}\circ\partial_{q}^{f_{1}}.$

When $q=i+1$, for any $\tau\in Cr_{i+1}(f_{1})$, by Equations 1 and 2, we see

$\displaystyle\partial_{i+1}^{f_{2}}\circ h_{q}(\tau)$
$\displaystyle=\partial_{i+1}^{f_{2}}(\tau)=\sum_{\sigma\in
Cr_{i}(f_{1})}n^{f_{1}}(\tau,\sigma)\sigma+\sum_{\sigma\in
Cr_{i}(f_{1})}n^{f_{1}}(\tau,\sigma)\cdot
n^{f_{1}}(\sigma,\tilde{\sigma})\tilde{\sigma}.$
$\displaystyle=h_{i}(\sum_{\sigma\in
Cr_{i}(f_{1})}n^{f_{1}}(\tau,\sigma)\sigma)=h_{i}\circ\partial_{i+1}^{f_{1}}(\tau).$

Also, when $q=i$, for any $\sigma\in Cr_{i}(f_{1})$, Equations 3 and 4 imply

$\displaystyle\partial_{i}^{f_{2}}\circ h_{i}(\sigma)$
$\displaystyle=\partial_{i}^{f_{2}}(\sigma+n^{f_{1}}(\sigma,\tilde{\sigma})\tilde{\sigma})$
$\displaystyle=\partial_{i}^{f_{1}}(\sigma)-n^{f_{1}}(\sigma,\tilde{\sigma})(k\tilde{\alpha}+\sum_{\alpha\in
Cr_{i-1}(f_{1})}n^{f_{2}}(\tilde{\alpha},\alpha)\alpha)$
$\displaystyle+n^{f_{1}}(\sigma,\tilde{\sigma})(k\tilde{\alpha}+\sum_{\alpha\in
Cr_{i-1}(f_{1})}n^{f_{2}}(\tilde{\alpha},\alpha)\alpha)$
$\displaystyle=\partial_{i}^{f_{1}}(\sigma)=h_{i-1}\circ\partial^{f_{1}}_{i}(\sigma).$

Finally, when $q=i-1$, $*$ ‣ 4.1 holds trivially because $h_{i-1}$ and
$h_{i-2}$ are identities, and $\partial^{f_{1}}_{i-1}=\partial^{f_{2}}_{i-1}$.
Therefore, $h$ is a chain map.

We omit the parallel proof applied to the connectedness homomorphism $g$ to
prove that $g$ is a chain map.

∎

With regard to the birth-death transitions, we remark the following
statements.

  * •

$g\circ h=\text{id}.$ Also, $h\circ g(\delta_{2})=\text{id}$, for any
$\delta_{2}\neq\tilde{\sigma}$ or $\tilde{\alpha}$.

  * •

$h$ and $g$ are chain-homotopy inverses to each other, that is, $g\circ h$ and
$h\circ g$ are chain homotopic to the identities.

  * •

In Definition 4.1, for convenience, we assumed that any $f_{2}$-critical
simplex $\delta_{2}$ distinct from $\tilde{\sigma}$ or $\tilde{\alpha}$ is
also $f_{1}$-critical, implying $h_{q}=g_{q}=\text{id}_{q}$, for $q\neq i$.
However, these identical simplices can be extended to a pair of $f_{1}$ and
$f_{2}$-critical simplices, which are faithful to each other. See Example 2 in
Section 4.3.

In discrete Morse theory, the set of all discrete Morse functions on a
simplicial complex is typically studied by defining an equivalence relation:
discrete Morse functions $f_{1}$ and $f_{2}$ are equivalent if their
corresponding gradient vector fields $V_{1}$ and $V_{2}$ are identical as
sets. This definition ignores the numerical values of the discrete Morse
functions, instead focusing on the order of values within each simplex’s
neighborhood. Also, the gradient vector fields form a simplicial complex, as
initially studied in [6]. Furthermore, when $K$ is a graph, the simplicial
complex is the complex of rooted forests, introduced in [12].

######  Lemma 4.3.

Let $f_{1},f_{2}:K\to\mathbb{R}$ be discrete Morse functions and $V_{1},V_{2}$
be the corresponding gradient vector field, respectively. Then, $V_{1}=V_{2}$
if and only if $h=g=\text{id}.$

###### Proof.

Suppose $V_{1}=V_{2}$. It is easy to see that for any $\sigma_{1}$,
$h_{q}(\sigma_{1})=\sigma_{1}=g_{q}(\sigma_{1})$, because there is no gradient
path between two $q$-dimensional critical simplices.

The proof for the other side is trivial. ∎

Next, we use the connectedness homomorphisms to define the function
connectedness between two discrete Morse functions.

######  Definition 4.4.

We say $f_{1}$ is connected to $f_{2}$ if both $h$ and $g$ are chain maps,
denoted $f_{1}\leftrightarrow f_{2}$.

Note that neither the simplex connectedness nor the function connectedness is
an equivalence relation due to the absence of the transitive property. To
illustrate, let $f_{1},f_{2},f_{3}:K\to\mathbb{R}$ be discrete Morse functions
and $\sigma_{i}\in Cr_{q}(f_{i}),$ $i=1,2,3,$ represent critical simplices
corresponding to each function. The presence of connectedness
$\sigma_{1}\to\sigma_{2}$ and $\sigma_{2}\to\sigma_{3}$ does not necessarily
imply the strong connectedness $\sigma_{1}\to\sigma_{3}$. Alternatively,
expressed in terms of the connectedness coefficient,
$n^{f_{1}}(\sigma_{1},\sigma_{3})\neq n^{f_{1}}(\sigma_{1},\sigma_{2})\cdot
n^{f_{2}}(\sigma_{2},\sigma_{3}).$

######  Definition 4.5.

Let $f_{1},f_{2},\ldots,f_{n}:K\to\mathbb{R}$ be a sequence of discrete Morse
functions, and $C_{\ast}^{f_{1}},C_{\ast}^{f_{2}},\ldots,C_{\ast}^{f_{n}}$ be
the corresponding discrete Morse complexes. If for each $i=1,2,\cdots,n-1$,
the connectedness homomorphisms $h^{i}_{\ast}:C_{\ast}^{f_{i}}\to
C_{\ast}^{f_{i+1}}$ is either a birth transition or a death transition, then
we call the sequence of discrete Morse functions a birth-death transition
sequence, and any two discrete Morse functions $f_{j}$ and $f_{k}$ are called
transitively connected.

###  4.2. Comparison of Degenerations in Smooth and Discrete Cases.

In [14], Laudenbach studies the modification of a smooth Morse complex near a
degenerated critical point. Notably, under certain conditions, Laudenbach
establishes a composition of homomorphisms connecting two smooth Morse
complexes, obtained by the Morse functions before and after the degeneration.

Figure 2 presents a diagram illustrating the relationship between the smooth
degeneration and the connectedness homomorphisms $h$ and $g$. Within this
context, let $M$ be a smooth manifold, $\phi_{1},\phi_{2}:M\to\mathbb{R}$ be
Morse functions. The homomorphisms 1 are constructed in Laudenbach [14,
Section f] to represent the transformation before and after the degeneration;
and the discretization homomorphisms 2 are first derived by Gallais [9,
Theorem 3.1] and then improved by Benedetti [3, Main Theorem A], as noted in
Proposition 4.6 below.

${S_{q}^{\phi_{1}}(M)}$${S_{q}^{\phi_{2}}(M)}$${C_{q}^{f_{1}}(T)}$${C_{q}^{f_{2}}(T)}$$\scriptstyle{1}$$\scriptstyle{2}$$\scriptstyle{2}$$\scriptstyle{h_{q}}$$\scriptstyle{g_{q}}$
Figure 2. Comparison of the smooth and discrete cases.

######  Proposition 4.6 (Main Theorem A of Benedetti [3]).

Let $M$ be a smooth manifold and $\phi:M\to\mathbb{R}$ be a generic Morse
function. For any PL triangulation $T$ of $M$, there exist an integer $r$ and
a discrete Morse function $f$ on the $r$-th derived subdivision $T^{r}$ of $T$
such that the smooth Morse complex is isomorphic to the discrete Morse complex
obtained by $T^{r}$ and $f$.

######  Proposition 4.7.

The diagram in Figure 2 is commutative.

Proposition 4.7 follows from the followings: homomorphisms 1 are chain maps;
homomorphisms 2 are isomorphisms; and by Theorem 4.2, $h$ and $g$ are chain
maps. For the detailed constructions of 1, 2 and the proofs, one may refer to
the papers.

Hence, a relationship between smooth degenerations and discrete birth-death
transitions can be established through the composition of the homomorphisms.
With regard to the relationship, we make the following remarks:

  * •

The reverse process of this construction is not universally feasible. That is,
for a given triangulation $T$ of some smooth manifold $M$ and a discrete Morse
function $f:T\to\mathbb{R}$, it may not be possible to associate $f$ to a
smooth Morse function on $M$ such that the Morse complex and the discrete
Morse complex are isomorphic. (See [3, Main Theorem B])

  * •

Our Definition 4.1 employs general simplicial complexes $K$, thus containing
the cases of the results obtained by the diagram of Figure 2, in which $T$ is
a triangulation of some smooth manifold. This is exemplified in Example 2 of
Section 4.3.

Additionally, we remark that some useful discussions about the simplex
connectedness of subdivision are addressed [11, Section 4].

###  4.3.  Examples of Birth-Death Transition.

For a smooth function $\phi$ on a manifold with a parameter $\lambda$, the
cusp degeneration can be described by the normal form:

$\phi(\mathbf{x},\lambda)=x_{1}^{3}+\lambda x_{1}\pm x_{2}^{2}\pm\cdots\pm
x_{m}^{2}.$

Thus, to study this bifurcation generally, it is essential to understand the
one-dimensional case. We consider the corresponding discrete settings as
follows.

### Example 1.

The following example illustrates the modification of a discrete Morse complex
near a birth-death point through the connectedness homomorphism. Figure 3
depicts two continuous functions, $\phi_{1}$ and $\phi_{2}$, defined over the
same interval $I=[-5,5].$

$\phi_{1}$ and $\phi_{2}$ are used to denote the transformation before and
after a cusp degeneration. Besides the endpoints of the interval, function
$\phi_{1}$ consists of two critical points; and $\phi_{2}$ consists of four
critical points.

$-4$$-2$$2$$4$$x$$\phi_{1}(x)$

(a) Morse function $\phi_{1}$.

$-4$$-2$$2$$4$$x$$\phi_{2}(x)$

(b) Morse function $\phi_{2}$.

Figure 3. Two Morse functions on the interval $I$.

Figure 4 displays the triangulation of the interval $I$ into a one-dimensional
simplicial complex $K$. Also, continuous functions $\phi_{1}$ and $\phi_{2}$
are represented by discrete functions $f_{1}$ and $f_{2}$ in (a) and (b) of
Figure 4. One can check that both of them are discrete Morse functions. Red
vertices and edges denote critical simplices with respect to each discrete
Morse function. Arrows from $0$-dimensional simplices to $1$-dimensional
simplices represent the gradient pairs.

For discrete Morse function $f_{1}$, there are two $0$-dimensional critical
simplices and one $1$-dimensional critical simplex, labeled as
$v_{1}^{1},v_{1}^{2}$ and $e_{1}^{1}$. For discrete Morse function $f_{2}$,
there are three $0$-dimensional critical simplices and two $1$-dimensional
critical simplices, labeled as $v_{2}^{1},v_{2}^{2},v_{2}^{3},e_{2}^{1}$ and
$e_{2}^{2}$.

Next, we consider the homomorphisms $h_{q}:C_{q}^{f_{1}}(K)\to
C_{q}^{f_{2}}(K)$ and $g_{q}:C_{q}^{f_{2}}(K)\to C_{q}^{f_{1}}(K),$ for
$q=0,1$. One can check by the definition, $h$ and $g$ are birth and death
transitions corresponding to the $f_{2}$-critical simplices pair
$(e_{2}^{2},v_{2}^{2})$. Simple computations in mod 2 allow us to conclude
that $h_{1}(e_{1}^{1})=e_{2}^{1}+e_{2}^{2}$; $h_{0}(v_{1}^{1})=v_{2}^{1}$;
$h_{0}(v_{1}^{2})=v_{2}^{3}$. Boundary computations confirm that $h$ is a
chain map:

$\partial^{f_{2}}\circ
h_{1}(e_{1}^{1})=v_{2}^{1}+v_{2}^{3}=h_{0}\circ\partial^{f_{1}}(e_{1}^{1}).$

Additionally, similar computations for $g$ confirm that $g$ is also a chain
map.

$v_{1}^{2}$$v_{1}^{1}$$e^{1}_{1}$

(a) Discrete Morse function $f_{1}$.

$v_{2}^{1}$$v_{2}^{3}$$v_{2}^{2}$$e^{1}_{2}$$e^{2}_{2}$

(b) Discrete Morse function $f_{2}$.

Figure 4. Two discrete Morse functions on the triangulation of $I$.

### Example 2.

In Proposition 4.5, we showed that the birth-death transitions on a
triangulation $T$ of a smooth manifold $M$ can be realized through the
composition of homomorphisms mentioned in Figure 2. However, Theorem 4.2
contains this result as $K$ in Theorem 4.2 represents a general simplicial
complex. We illustrate this fact with the following example.

Figure 5 visually depicts a birth-death transition of the cusp type on a
simplicial complex $K$, which is not a triangulation of any smooth manifold.
Note that although $e_{1}^{1}\neq e_{2}^{1}$, $e_{1}^{1}$ and $e_{2}^{1}$ are
faithful to each other; and $v_{1}^{1}$ and $v_{2}^{2}$ are faithful to each
other, as well. We let $(e_{2}^{2},v_{2}^{1})$ be the pair of $f_{2}$-critical
simplices to be cancelled. Then, $h$ and $g$ are birth-death transitions.

That $h$ is a chain map follows from $f_{1}$ is optimal. For $g$, we compute
that $g_{0}(v_{2}^{1})=g_{0}(v_{2}^{2})=v_{1}^{1}$;
$g_{1}(e_{2}^{1})=e_{1}^{1}$, $g_{1}(e_{2}^{2})=0$. Furthermore,
$\partial_{1}^{f_{2}}(e_{2}^{1})=0$ and
$\partial_{1}^{f_{2}}(e_{2}^{2})=v_{2}^{1}+v_{2}^{2}$ in mod $2$.
Consequently,
$g_{0}\circ\partial_{1}^{f_{2}}(e_{2}^{1})=0=\partial^{f_{1}}_{0}\circ
g_{1}(e_{2}^{1});$ and
$g_{0}\circ\partial_{1}^{f_{2}}(e_{2}^{2})=0=\partial^{f_{1}}_{0}\circ
g_{1}(e_{2}^{2}).$ Hence, $g$ is also a chain map.

Note that the choice of critical simplices for cancellation is not necessarily
unique and depends on the orientation of $K$. In this scenario, we can choose
to cancel either the pair $(e_{2}^{2},v_{2}^{1})$ or $(e_{2}^{2},v_{2}^{2})$.
However, regardless of the choice made, the remaining $0$-dimensional simplex
remains strongly connected to $v_{1}^{1}$, and $h$ and $g$ remain to be birth
and death transitions.

Compared with Example 1, the simplicial complex in Example 2 is not locally
Euclidean. However, our focus should rather be on the gradient vector fields
defined on this simplcial complex. We can decompose the gradient vector fields
into a set of gradient paths (See [17, Example 4.9] as an example). Thus, as a
basic fact of discrete Morse theory [7, Theorem 3.5], any gradient path does
not include cycles, thus ensuring each gradient path is “locally Euclidean.
Consequently, the structure of gradient vector fields in Example 2 can be
described as a union of the type of triangulations in Example 1.

$v_{1}^{1}$$e_{1}^{1}$

(a) Discrete Morse function $f_{1}$.

$v_{2}^{1}$$v_{2}^{2}$$e_{2}^{2}$$e_{2}^{1}$

(b) Discrete Morse function $f_{2}$.

Figure 5. A birth-death transition on a simplicial complex that is not a
triangulation of a smooth manifold.

### Remarks and Future Work

One of our long-term goal of this series of work is to establish a discrete
version of Cerf theory, which is introduced in [5].

The core of Cerf theory is the Cerf diagram, which visually represents the
critical value changes of a generic one-parameter family of functions on a
manifold. This is pivotal for understanding bifurcations and the structural
stability of function spaces. The theory notably applies to gradient vector
fields and their trajectories, studying how critical points can be created or
eliminated through perturbations, known as births and deaths in the context of
smooth Morse theory.

Some discrete counterparts have been considered, e.g., Chari-Joswig [6], King-
Knudson-Mramor Kosta [11]. Also recently, there appeared other attempts for
discussing a discrete analogy to the smooth Cerf theory, such as Brüggemann
[4]. Our approach offers a distinct advantage through the concepts of simplex
connectedness and function connectedness, which may lead to more direct
geometric understanding: by subdivisions of the gradient vector fields, we
describe a discrete analogy of degenerations of degenerated critical simplices
[19].

## References

  * [1] V. I. Arnold , V. V. Goryunov , O. V. Lyashko , V. A. Vasil’ev, Singularity Theory I. Springer Berlin, Heidelberg (1998).
  * [2] R. Ayala, L.M. Fernández, D. Fernández-Ternero, J.A. Vilches, Discrete Morse theory on graphs. Topology and its Applications 156 (2009), 3091–3100.
  * [3] B. Benedetti, Smoothing discrete Morse theory, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) Vol. XVI (2016), 335-368.
  * [4] J. Brüggemann, On The Moduli Space of Discrete Morse Functions, arXiv:2312.14032.
  * [5] J. Cerf, La stratification naturelle des espaces de fonctions différentiables réelles et le théorème de la pseudo-isotopie. Publications Mathématiques de l’IHÉS, Tome 39 (1970), pp. 5-173.
  * [6] M. K. Chari, M. Joswig, Complexes of discrete Morse functions, Discrete Mathematics 302 (2005) 39-51.
  * [7] R. Forman, A User’s Guide to Discrete Morse Theory. Seminaire Lotharingien de Combinatoire 48 (2002), Article B48c.
  * [8] R. Forman, Morse Theory for Cell Complexes. Advances in Mathematics 134, (1998), 90-145.
  * [9] E. Gallais, Combinatorial realization of the thom-smale complex via discrete Morse theory, Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, pp.229–252.
  * [10] M. Guest, Morse theory in the 1990’s, arXiv:math/0104155.
  * [11] H. King, K. Knudson, N.Mramor Kosta, Birth and death in discrete Morse theory, J. Symb. Comput. 78 (2017) 41–60.
  * [12] D. N. Kozlov, Complexes of directed trees, J. Comb. Theory Ser. A 88 (1) (1999) 112–122.
  * [13] D. N. Kozlov, Organized Collapse: An Introduction to Discrete Morse Theory, Graduate Studies in Mathematics, 207. American Mathematical Society, Providence, RI, 2020.
  * [14] F. Laudenbach, Appendix. On the Thom-Smale complex, Astérisque, tome 205 (1992), 219-233.
  * [15] J. Milnor, Morse theory. Annals of Mathematics Studies, No. 51, Princeton University Press, Princeton, N.J., 1963.
  * [16] N. A. Scoville, Discrete Morse Theory. Student Mathematical Library vol. 90, American Mathematical Society, Providence, RI, 2020.
  * [17] C. Zheng, Persistent pairs and strong connectedness in discrete Morse functions on simplicial complex i@, Topology and its Applications. https://doi.org/10.1016/j.topol.2024.108844.
  * [18] C. Zheng, Connectedness in discrete Morse functions on simplicial complex ii@, in preparation.
  * [19] C. Zheng, in preparation.


11institutetext: EPITA Research and Development Lab. (LRDE), EPITA, France
22institutetext: Univ. Gustave Eiffel, IGN-ENSG, LaSTIG, France
33institutetext: LaDéHiS, CRH, EHESS, France44institutetext: L3i, University
of La Rochelle, France55institutetext: Liris, INSA-Lyon,
France66institutetext: Department of Computer Science and Engineering,
University of West Bohemia, Univerzitní, Pilsen, Czech
Republic77institutetext: NTIS - New Technologies for the Information Society,
University of West Bohemia, Univerzitní, Pilsen, Czech Republic

# ICDAR 2021 Competition on
Historical Map Segmentation††thanks: This work was partially funded by the
French National Research Agency (ANR): Project SoDuCo, grant ANR-18-CE38-0013.
We thank the City of Paris for granting us with the permission to use and
reproduce the atlases used in this work.

Joseph Chazalon 11 0000-0002-3757-074X Edwin Carlinet 11 0000-0001-5737-5266
Yizi Chen 1122 0000-0003-1637-0092 Julien Perret 2233 0000-0002-0685-0730
Bertrand Duménieu 33 0000-0002-2517-2058 Clément Mallet 22 0000-0002-2675-165X
Thierry Géraud 11 0000-0002-0380-7948
Vincent Nguyen 4455 0000-0003-2271-6918 Nam Nguyen 44
Josef Baloun 6677 0000-0003-1923-5355 Ladislav Lenc 6677 0000-0002-1066-7269
Pavel Král 6677 0000-0002-3096-675X

###### Abstract

This paper presents the final results of the ICDAR 2021 Competition on
Historical Map Segmentation (MapSeg), encouraging research on a series of
historical atlases of Paris, France, drawn at 1/5000 scale between 1894 and
1937. The competition featured three tasks, awarded separately. Task 1
consists in detecting building blocks and was won by the L3IRIS team using a
DenseNet-121 network trained in a weakly supervised fashion. This task is
evaluated on 3 large images containing hundreds of shapes to detect. Task 2
consists in segmenting map content from the larger map sheet, and was won by
the UWB team using a U-Net-like FCN combined with a binarization method to
increase detection edge accuracy. Task 3 consists in locating intersection
points of geo-referencing lines, and was also won by the UWB team who used a
dedicated pipeline combining binarization, line detection with Hough
transform, candidate filtering, and template matching for intersection
refinement. Tasks 2 and 3 are evaluated on 95 map sheets with complex content.
Dataset, evaluation tools and results are available under permissive licensing
at https://icdar21-mapseg.github.io/.

###### Keywords:

Historical Maps Map Vectorization Competition

##  1 Introduction

Figure 1: Sample map sheet. Original size: 11136$\times$7711 pixels.

Figure 2: Some map-related challenges (_left_): visual polysemy, planimetric
overlap, text overlap… and some document-related challenges (_right_): damaged
paper, non-straight lines, image compression, handwritten text…

Motivation  This competition consists in solving several challenges which
arise during the processing of images of historical maps. In the Western
world, the rapid development of geodesy and cartography from the $18^{th}$
century resulted in massive production of topographic maps at various scales.
City maps are of utter interest. They contain rich, detailed, and often
geometrically accurate representations of numerous geographical entities.
Recovering spatial and semantic information represented in old maps requires a
so-called vectorization process. Vectorizing maps consists in transforming
rasterized graphical representations of geographic entities (often maps) into
instanced geographic data (or vector data), that can be subsequently
manipulated (using Geographic Information Systems). This is a key challenge
today to better preserve, analyze and disseminate content for numerous spatial
and spatio-temporal analysis purposes.

Tasks  From a document analysis and recognition (DAR) perspective, full map
vectorization covers a wide range of challenges, from content separation to
text recognition. _MapSeg_ focuses on 3 critical steps of this process.  (i)
Hierarchical information extraction, and more specifically the _detection of
building blocks_ which form a core layer of map content. This is addressed in
_Task 1_.  (ii) _Map content segmentation_ , which needs to be performed very
early in the processing pipeline to separate meta-data like titles, legends
and other elements from core map content. This is addressed in _Task 2_.
(iii) Geo-referencing, i.e. mapping historical coordinate system into a recent
reference coordinate system. Automating this process requires the detection of
well-referenced points, and we are particularly interested in detecting
_intersection points between graticule lines_ for this purpose. This is
addressed in _Task 3_.

Dataset  _MapSeg_ dataset is extracted from a series of 9 atlases of the City
of Paris111 Atlas municipal des vingt arrondissements de Paris. 1894, 1895,
1898, 1905, 1909, 1912, 1925, 1929, and 1937. Bibliothèque de l’Hôtel de
Ville. City of Paris. France. Online resources for the 1925 atlas:
https://bibliotheques-specialisees.paris.fr/ark:/73873/pf0000935524.  produced
between 1894 and 1937 by the Map Service (_“Service du plan”_) of the City of
Paris, France, for the purpose of urban management and planning. For each
year, a set of approximately 20 sheets forms a tiled view of the city, drawn
at 1/5000 scale using trigonometric triangulation. Figure 1 is an example of
such sheet. Such maps are highly detailed and very accurate even by modern
standards. This material provides a very valuable resource for historians and
a rich body of scientific challenges for the document analysis and recognition
(DAR) community: map-related challenges (fig. 2, _left_) and document-related
ones (fig. 2, _right_). The actual dataset is built from a selection of 132
map sheets extracted from these atlases. Annotation was performed manually by
trained annotators and required 400 hours of manual work to annotate the 5
sheets of the dataset for Task 1 and 100 hours to annotate the 127 sheets for
Tasks 2 and 3. A special care was observed to minimize the spatial and, to
some extent, temporal overlap between train, validation and test sets: except
for Task 1 which contains districts 1 and 2 both in train and test sets (from
different atlases to assess the potential for the exploitation of information
redundancy over time), each district is either in the training, the validation
or the test set. This is particularly important for Tasks 2 and 3 as the
general organization of the map sheets are very similar for sheets
representing the same area.

Competition Protocol  The MapSeg challenge ran from November 2020 to April
2021. Participants were provided with training and validation sets for each 3
tasks by November 2020. The test phase for Task 1 started with the release of
test data on April 5th, 2021 and ended in April 9th. The test phase for Tasks
2 and 3 started with the release of test data on April 12th, 2021 and ended in
April 16th. Participants were requested to submit the results produced by
their methods (at most 2) over the test images, computed by themselves.

Open Data, Tools and Results  To improve the reliability of the evaluation and
competition transparency, evaluation tools were released (executable and open
source code) early in the competition, so participants were able to evaluate
their methods on the validation set using exactly the same tools as the
organizers on the test set. More generally, all competition material is made
available under very permissive licenses at https://icdar21-mapseg.github.io/:
dataset with ground truth, evaluation tools and participants results can be
downloaded, inspected, copied and modified.

Participants  The following teams took part in the competition.

CMM Team:

Team: Mateus Sangalli, Beatriz Marcotegui, José Marcio Martins Da Cruz,
Santiago Velasco-Forero, Samy Blusseau; Institutions: Center for Mathematical
Morphology, Mines ParisTech, PSL Research University, France; Extra material:
morphological library Smil: http://smil.cmm.minesparis.psl.eu; code:
https://github.com/MinesParis-MorphoMath.

IRISA Team:

Competitor: Aurélie Lemaitre; Institutions: IRISA/Université Rennes 2, Rennes,
France; Extra material: http://www.irisa.fr/intuidoc/.

L3IRIS Team:

Team: Vincent Nguyen and Nam Nguyen; Institutions: L3i, University of La
Rochelle, France; Liris, INSA-Lyon, France; Extra material:
https://gitlab.univ-lr.fr/nnguye02/weakbiseg.

UWB Team:

Team: Josef Baloun, Ladislav Lenc and Pavel Král; Institutions: Department of
Computer Science and Engineering, University of West Bohemia, Univerzitní,
Pilsen, Czech Republic; NTIS - New Technologies for the Information Society,
University of West Bohemia, Univerzitní, Pilsen, Czech Republic; Extra
material: https://gitlab.kiv.zcu.cz/balounj/21˙icdar˙mapseg˙competition.

WWU Team:

Team: Sufian Zaabalawi, Benjamin Risse; Institution: Münster University,
Germany; Extra material: Project on automatic vectorization of historical
cadastral maps: https://dhistory.hypotheses.org/346.

##  2 Task 1: Detect Building Blocks

This task consists in detecting a set of closed shapes (building blocks) in
the map image. Building blocks are coarser map objects which can regroup
several elements. Detecting these objects is a critical step in the
digitization of historical maps because it provides essential components of a
city. Each building block is symbolized by a closed shape which can enclose
other objects and lines. Building blocks are surrounded by streets, rivers
fortification wall or others, and are never directly connected. Building
blocks can sometimes be reduced to a single spacial building, symbolized by
diagonal hatched areas. Given the image of a complete map sheet and a mask of
the map area, participants had to detect each building block as illustrated in
fig. 3.

Figure 3: Input (_left_) and output (_right_ , orange overlay) image excerpts
for task 1.

###  2.1 Dataset

Inputs form a set of JPEG RGB images which are quite large ($\approx
8000\times 8000$ pixels). They are complete map sheet images as illustrated in
fig. 1, cropped to the relevant area (using the ground truth from Task 2).
Remaining non-relevant pixels were replaced by black pixels. Expected output
for this task is a binary mask of the building blocks: pixels falling inside a
building block must be marked with value 255, and other pixels must be marked
with value 0. The dataset is separated as follows: the train set contains 1
image (sheet 1 of 1925 atlas — 903 building blocks), the validation set
contains 1 image (sheet 14 of 1925 atlas — 659 building blocks), and the test
set contains 3 images (sheet 1 of 1898 atlas, sheet 3 of 1898 and 1925 atlases
— 827, 787 and 828 building blocks).

###  2.2 Evaluation Protocol

Map vectorization requires an accurate detection of shape boundaries. In order
to assess both the detection and segmentation quality of the target shapes,
and therefore to avoid relying only on pixel-wise accuracy, we use the COCO
Panoptic Quality (PQ) score [8] which is based on an instance segmentation
metric. This indicator is computed as follows:

${\text{PQ}}=\underbrace{\frac{\sum_{(p,g)\in
TP}\text{IoU}(p,g)}{\vphantom{\frac{1}{2}}|TP|}}_{\text{segmentation quality
(SQ)}}\times\underbrace{\frac{|TP|}{|TP|+\frac{1}{2}|FP|+\frac{1}{2}|FN|}}_{\text{recognition
quality (RQ)}}$

where $TP$ is the set of matching pairs $(p,g)\in(P\times G)$ between
predictions ($P$) and reference ($G$), $FP$ is the set of unmatched predicted
shapes, and $FN$ is the set of unmatched reference shapes. Shapes are
considered as matching when:

$\text{IoU}(p,g)=\frac{p\cap g}{p\cup g}>0.5.$

COCO SQ (segmentation quality) is the mean IoU between matching shapes:
matching shapes in reference and prediction have an IoU $>$ 0.5. COCO RQ
(detection/recognition quality) is detection F-score for shape: a predicted
shape is a true positive if it as an IoU $>$ 0.5 with a reference shape. The
resulting COCO PQ indicator ranges from 0 (worst) to 1 (perfect). An alternate
formulation of this metric is to consider it as the integral of the detection
F-score over all possible IoU thresholds between 0 and 1 [4]. We also report
the “F-Score vs IoU threshold” curves for each method to better assess their
behavior.

###  2.3 Method descriptions

####  2.3.1 L3IRIS — _Winning Method_

From previous experiments, the L3IRIS team reports that both semantic
segmentation and instance segmentation approaches led to moderate results,
mainly because of the amount of available data. Instead of trying to detect
building blocks directly, they reversed the problem and tried to detect non-
building-blocks as a binary semantic segmentation problem which facilitated
the training process. Additionally, they considered the problem in a
semi/weakly supervised setting where training data includes 2 images
(val+train): the label is available for one image and is missing for the other
image. Their binary segmentation model relies on a DenseNet-121 [7] backbone
and is trained using the weakly supervised learning method from [12]. Input is
processed as 480$\times$480 tiles. During training, tiles are generated by
random crops and augmented with standard perturbations: noise, rotation, gray,
scale, etc. Some post-processing techniques like morphological operators are
used to refine the final mask (open the lightly connected blocks and fill
holes). The parameter for the post-processing step is selected based on the
results on the validation image. Training output is a single models; not
ensemble technique is used. The weakly supervised training enables the
training of a segmentation network in a setting where only a subset of the
training objects are labelled. The overcome the problem of missing labels, the
L3IRIS team uses two energy maps $w+$ et $w-$ which represent the certainty
that a pixel being positive (object’s pixel) or negative (background pixel).
These two energy maps are evolved during the training at each epoch based on
prediction scores in multiple past epochs. This technique implicitly minimizes
the entropy of the predictions on unlabeled data which can help to boost the
performance of the model [5]. For Task 1, they considered labeled images (from
training set) and unlabeled ones (from validation set) for which the label was
retained for validation. The two energy maps are applied only for images from
the validation set.

####  2.3.2 CMM

Method 1 This method combines two parallel sub-methods, named 1A and 1B. In
both sub-methods, the RGB images are first processed by a U-Net [14] trained
to find edges of the blocks. Then, a morphological processing is applied to
the image of edges in order to segment the building blocks. Finally, the
results of both sub-methods are combined to produce a unique output. In method
1A, the U-Net is trained with data augmentation that uses random rotations,
reflections, occlusion by vertical and horizontal lines and color changes. The
loss function penalizes possible false positive pixels (chosen based on the
distance from edge pixels in the color space) with a higher cost. To segment
the blocks, first a top-hat operator is applied to remove large vertical and
horizontal lines and an anisotropic closing [3] is used to remove holes in the
edges. Edges are binarized by a hysteresis threshold and building blocks are
obtained by a fill-holes operator followed by some post-processing. The result
is a clean segmentation, but with some relatively large empty regions. In
method 1B, the U-Net is trained using the same augmentation process, but the
loss function weights errors to compensate class imbalance. Method 2
(described hereafter) is applied to the inverse of the edges obtained by this
second U-Net. To combine both methods, a closing by a large structuring
element is used to find the dense regions in the output of 1A, the complement
of which are the empty regions of 1A. The final output is equal to 1A in the
dense region and to 1B in the empty regions.

Method 2 This method is fully morphological. It works on a gray-level image,
obtained by computing the luminance from the RGB color image. The main steps
are the following:  (i) _Area closing_ with 1000 pixels as area threshold;
this step aims at _removing small dark components_ such as letters.  (ii)
_Inversion of contrast_ of the resulting image followed by a _fill-holes_
operator; The result of this step is an image where most blocks appear as flat
zones, and so do large portions of streets.  (iii) The _morphological
gradient_ of the previous image is computed and then _reconstructed by
erosion_ starting from markers chosen as the minima with dynamic not smaller
than $h=2$. This produces a new, simplified, gradient image.  (iv) The
_watershed transform_ is applied to the latter image, yielding a labelled
image.  (v) A _filtering of labelled components_ removes (that is, sets to
zero) components smaller than 2000 pixels and larger than 1M pixels; and also
removes the components with area smaller than $0.3$ times the area of their
bounding box (this removes large star-shaped street components). All kept
components are set to 255 to produce a binary image.  (vi) A _fill-holes_
operator is applied to the latter binary image.  (vii) _Removal of river
components_ : A mask of the river is computed by a morphological algorithm
based on a large opening followed by a much larger closing, a threshold and
further refinements. Components with an intersection of at least 60% of their
area with the river mask are removed.

####  2.3.3 WWU

Method 1 This method relies on a binary semantic segmentation U-Net [14]
trained with Dice loss on a manual selection of 2000 image patches of size
256$\times$256$\times$3 covering representative map areas. The binary
segmentation ground truth is directly used as target. This U-Net architecture
uses 5 blocks and each convolutional layer has a 3$\times$3 kernel filter with
no padding. The expending path uses transpose convolutions with 2$\times$
stride. Intermediate activations use RELU and the final activation is a
sigmoid.

Method 2 This method relies on a Deep Distance transform. The binary label
image is first transformed into a Euclidean _distance transform map_ (DTM),
which highlights the inner region of the building blocks more than the outer
edges. Like for method 1, 2000 training patch pairs of size 256$\times$256 are
generated. The U-Net architecture is similar to the previous method, except
that the loss function is the mean square error loss (MSE) and the prediction
is a DTM. This DTM is then thresholded and a watershed transform is used to
fill regions of interest and extract building block shapes.

###  2.4 Results and discussion

Rank | Team (method) | COCO PQ (%) $\uparrow$
---|---|---
1 | L3IRIS | 74.1
2 | CMM (1) | 62.6
3 | CMM (2) | 44.0
4 | WWU (1) | 06.4
5 | WWU (2) | 04.2

Figure 4: Final COCO PQ scores for Task 1 (_left_) — score ranges from 0
(worst) to 100% (best), and plot of the F-Score for each threshold between 0.5
and 1 (_right_). COCO PQ is the area under this curve plus $\frac{1}{2}$ times
the intersect at 0.5.

Results and ranking of each submitted method is given in fig. 4: table on the
left summarizes the COCO PQ indicators we computed and the plot on the right
illustrates the evolution of the retrieval F-Score for each possible IoU
threshold between 0.5 and 1. While the WWU 1 and 2 approaches get low scores,
it must be noted that this is due to local connections between shapes which
led to a strong penalty with the COCO PQ metric. As they implement very
natural ways to tackle such problem, they provide a very valuable performance
baseline. CMM method 2 is fully morphological and suffers from an insufficient
filtering of noise content, while CMM method 1 gets much better results by
combining edge filtering using some fully convolutional network with
morphological filtering. L3IRIS winning approach improves over this workflow
by leveraging weakly-supervised training followed by some morphological post-
processing.

##  3 Task 2: Segment Map Content Area

This task consists in segmenting the map content from the rest of the sheet.
This is a rather classical document analysis task as it consists in focusing
on the relevant area in order to perform a dedicated analysis. In our case,
Task 1 would be the following stage in the pipeline. Given the image of a
complete map sheet (illustrated in fig. 1), participants had to locate the
boundary of the map content, as illustrated in fig. 5.

Figure 5: Illustration of expected outputs for Task 2: green area is the map
content and red hatched area is the background.

###  3.1 Dataset

The inputs form a set of JPEG RGB images which are quite large ($\approx
10000\times 10000$ pixels). They are complete map sheet images. Expected
output for this task is a binary mask of the map content area: pixels
belonging to map contents are marked with value 255 and other pixels are
marked with value 0. The dataset is separated as follows: the train set
contains 26 images, the validation set contains 6 images, and the test set
contains 95 images. As in the atlas series we have multiple occurrences of
similar sheets representing the same area, we made sure that each sheet
appeared in only one set.

###  3.2 Evaluation Protocol

We evaluated the quality of the segmentation using the Hausdorff distance
between the ground-truth shape and the predicted one. This measure has the
advantage over the IoU, Jaccard index and other area measures that it keeps a
good “contrast” between results in the case of large objects (because there is
no normalization by the area). More specifically, we use the “Hausdorff 95”
variant which discards the 5 percentiles of higher values (assumed to be
outliers) to produce a more stable measure. Finally, we averaged indicators
for all individual map images to produce a global indicator. The resulting
measure is an error measure which ranges from 0 (best) to a large value
depending on image size.

###  3.3 Method descriptions

####  3.3.1 UWB — _Winning Method_

This method is based on the U-Net-like fully convolutional networked used in
[1]. This network takes a whole downsampled page as an input and predicts the
border of the expected area. Border training samples were generated from the
original ground truth (GT) files. The values are computed using a Gaussian
function, where $\sigma=50$ and the distance from border is used. Training is
performed using the training set and augmentation (mirroring, rotation and
random distortion) [2] to increase the amount of the training samples. To
improve the location of the detected border, a binarized image is generated
using a recursive Otsu filter [13] followed by the removal of small
components. Network prediction and the binarized image are post-processed and
combined with the use of connected components and morphological operations,
which parameters are calibrated on the validation set. The result of the
process is the predicted mask of a map content area.

####  3.3.2 CMM

This method assumes that the area of interest is characterized by the presence
of black lines connected to each other all over the map. These connections
being due either to the external frame, graticule lines, streets, or text
superimposed to the map. Thus, the main idea is detecting black lines and
reconstructing them from a predefined rectangle marker in the center of the
image. The method is implemented with the following steps.  (i) Eliminate map
margin ($M$) detected by the quasi-flat zone algorithm and removed from the
whole image ($I_{0}$): $I=I_{0}-M$.  (ii) Then, black lines ($B$), are
extracted by a thresholded black-top-hat ($B=Otsu(I-\varphi(I))$)  (iii) A
white rectangle ($R$) is drawn centered in the middle of the image and of
dimensions $\frac{W}{2}\times\frac{H}{2}$, with $W$ and $H$ the image width
and height respectively.  (iv) Black lines $B$ are reconstructed by dilation
from the centered rectangle: $B_{s}=Build(R,B)$. Several dark frames surround
the map. Only the inner one is connected to the drawn rectangle $R$ and
delimits the area of interest.  (v) The frame (black line surrounding the map)
may not be complete due to lack of contrast or noise. A watershed is applied
to the inverse of the distance function in order to close the contour with
$markers=R\,\cup\,border$. The region corresponding to marker $R$ becomes the
area of interest.  (vi) Finally, legends are removed from the area of
interest. Legends are the regions from the inverse of $B_{s}$ that are
rectangular and close to the border of the area of interest.

####  3.3.3 IRISA

This approach is entirely based on a grammatical rule-based system [9] which
combines visual clues of line segments extracted in the document at various
levels of a spatial pyramid. The line segment extractor, based on a multi-
scale Kalman filtering [10], is fast and robust to noise, and can deal with
slope and curvature. Border detection is performed in two steps:  (i) Line
segments are first extracted at low resolution level (scale 1:16) to provides
visual clues on the presence of the double rulings outside the map region.
Then, the coarse enclosing rectangle is detected using a set of grammar rules.
(ii) Line segments are extracted at medium resolution level (scale 1:2) to
detect parts of contours of the maps, and of title regions. Another set of
grammar rules are then used to describe and detect the rectangular contour
with smaller rectangle (title and legend) in the corners.  The performance is
this approach is limited by the grammar rules which do not consider, though it
would be possible, the fact that the map content may lay outside the
rectangular region, nor it considers that some legend components may not be
located at the corners of the map.

####  3.3.4 L3IRIS

This approach leverages the cutting edge few-shot learning technique HSNet
[11] for image segmentation, in order to cope with the limited amount of
training data. With this architecture, the prediction of a new image (query
image) will be based on the trained model and a training image (support
image). In practice, the L3IRIS team trained the HSNet [11] from scratch with
a Resnet 50 backbone from available data to predict the content area in the
input map with 512$\times$512 image input. Because post-processing techniques
to smooth and fill edges did not improve the evaluation error, the authors
kept the results from the single trained model as the final predicted maps.

###  3.4 Results and discussion

Rank | Team | Hausdorff 95 (pix.) $\downarrow$
---|---|---
1 | UWB | 19
2 | CMM | 85
3 | IRISA | 112
4 | L3IRIS | 126

Figure 6: Final Hausdorff 95 errors for Task 2 (_left_) — values range from 0
pixels (best) to arbitrarily large values, and error distribution for all test
images (_right_).

Results and ranking of each submitted method is given in fig. 6: table on the
left summarizes the Hausdorff 95 indicators we computed and the plot on the
right illustrates the error distribution (in log scale) for all test images.
The L3IRIS method, based on a single FCN leveraging recent few-shot learning
technique produces overly smoothed masks. The IRISA method, based on a robust
line segment detector embedded in a rule-based system, was penalized by unseen
frame configurations. However, it produced very accurate results for know
configurations. The CMM approach, based on morphological processing, also
produced very accurate frame detection and generalized better. The remaining
errors are due to missed regions considered as background close to the
boundary. The UWB winning method, finally, efficiently combines a coarse map
content detection thanks to a deep network, with a re-adjustment of detected
boundaries using a recursive Otsu binarization and some morphological post-
processing.

##  4 Task 3: Locate Graticule Lines Intersections

This task consists in locating the intersection points of graticule lines.
Graticule lines are lines indicating the North/South/East/West major
coordinates in the map. They are drawn every 1000 meters in each direction and
overlap with the rest of the map content. Their intersections are very useful
to geo-reference the map image, i.e. for projecting map content in a modern
geographical coordinate reference system. Given the image of a complete map
sheet, participants had to locate the intersection points of such lines, as
illustrated in fig. 7.

Figure 7: Illustration of expected outputs for Task 3: dashed green lines are
the graticule lines and red dots are the intersections points to locate.

###  4.1 Dataset

The inputs for this task are exactly the same as Task 2. Expected output for
this task is, for each input image, the list intersection coordinates. The
dataset is separated exactly as for Task 2 in terms of train, validation and
test sets.

###  4.2 Evaluation Protocol

For each map sheet, we compared the predicted coordinates with the expected
ones. We used an indicator which considers detection and localization accuracy
simultaneously, like what we did for Task 1. A predicted point was considered
as a correct detection if it was the closest predicted point of a ground truth
(expected) point and if the distance between the expected point and the
predicted one is smaller than a given threshold. We considered all possible
thresholds between 0 and 50 pixels, which roughly corresponds to 20 meters for
these map images, and is an upper limit over which the registration would be
seriously disrupted. In practice, we computed for each map sheet and for each
possible threshold the number of correct predictions, the number of incorrect
ones and the number of expected elements. This allowed us to plot the
$F_{\beta}$ score vs threshold curve for a range of thresholds. We set
$\beta=0.5$ to weights recall lower than precision because for this task it
takes several good detections to correct a wrong one in the final
registration. The area under this “$F_{0.5}$ score vs threshold” curve was
used as performance indicator; such indicator blends two indicators: point
detection and spatial accuracy. Finally, we computed the average of the
measures for all individual map images to produce a global indicator. The
resulting measure is a value between 0 (worst) and 1 (best).

###  4.3 Method descriptions

####  4.3.1 UWB — _Winning Method_

This method is based on three main steps.  (i) First, a binary image is
generated using the recursive Otsu approach described in section 3.3.1. This
image is then masked using the map content area predicted for Task 2.  (ii)
Graticule lines are then detected a Hough Line Transform. While the
accumulator bins contain a lot of noise, the following heuristics were used to
filter the candidates: graticule lines are assumed to be straight, to be
equally spaced and either parallel or perpendicular, and there should be at
least four lines in each image. To enable finding, filtering, correcting,
fixing and rating peak groups that represents each graticule line in Hough
accumulator, each candidate contains information about its rating, angle and
distance between lines. Rating and distance information is used to select the
best configuration.  (iii) Intersections are finally coarsely estimated from
the intersections between Hough lines, then corrected and filtered using the
predicted mask from the Task 2, using some template matching with a cross
rotated by the corresponding angle.  The approach does not require any
learning and the parameters are calibrated using both train and validation
subsets.

####  4.3.2 IRISA

This method is based on two main steps.  (i) The same line segment detector as
the one used by the IRISA team for Task 2 (section 3.3.3) is used to detect
candidates. This results in a large amount of false positives with segments
detected in many map objects.  (ii) The DMOS rule grammar system [9] is used
to efficiently filter candidates using a dedicated set of rules. Such rules
enable the integration of constraints like perpendicularity or regular spacing
between the lines, and the exploration of the hypothesis space thanks to the
efficient back-tracking of the underlying logical programming framework.

####  4.3.3 CMM

This method combines morphological processing and the Radon transform.
Morphological operators can be disturbed by noise disconnecting long lines
while the Radon transform can integrate the contribution of short segments
that may correspond to a fine texture. The process consists in the following
six steps.  (i) First, the image is sub-sampled by a factor 10 in order to
speed up the process and to make it more robust to potential line
discontinuities. An erosion of size 10 is applied before sub-sampling to
preserve black lines.  (ii) Then the frame is detected. Oriented gradients
combined with morphological filters are used for this purpose, inspired by the
method proposed in [6] for building façade analysis.  (iii) Line directions
are then found. Directional closings from 0 to 30 degrees with a step of 1
degree, followed by black top-hat and Otsu threshold are applied. The angle
leading to the longest detected line is selected.  (iv) The Radon transform of
the previous black top-hat at the selected direction and its orthogonal are
computed. Line locations correspond to the maxima of the Radon transform.  (v)
Lines are equally spaced in the map. The period of this grid is obtained as
the maximum of the autocorrelation of the Radon transform. Equidistant lines
are added on the whole map, whether they have been detected by the Radon
transform or not. Applied to both directions, this generates the graticule
lines.  (vi) Finally a refinement is applied to localize precisely the line
intersections at the full scale. In the neighborhood of each detected
intersection, a closing is applied with a cross structuring element (with
lines of length 20) at the previously detected orientations. The minimum of
the resulting image provides the precise location of the intersection. If the
contrast of the resulting closing is too low ($<10$), the point is inferred
from the other points that were successfully found in the refinement step on
the corresponding intersecting lines.

####  4.3.4 L3IRIS

This method is based on a deep intersection detector followed by a filtering
technique based on a Hough transform. The process consists in the following
five steps.  (i) First, cross signs (all the points that are similar to the
target points) are detected using a U-Net model [14] for point segmentation,
trained with the 26 training images. The ground truth was generated by drawing
a circle at each point’s location over a zero background. The resulting model
detects many points, among which the target points.  (ii) From these
candidates, a Hough transform is used (with additional heuristics) to detect
graticule lines. The parameters of the Hough transform are selected
automatically based on the number of final points in the last step.  (iii) A
clustering algorithm is then used to select line candidates forming a regular
grid (parallel and orthogonal lines).  (iv) Finally, intersections between
these lines are filtered using the predicted mask from Task 2 (section 3.3.4)
to get the final set of points.

###  4.4 Results and discussion

Rank | Team | Detection score (%) $\uparrow$
---|---|---
1 | UWB | 92.5
2 | IRISA | 89.2
3 | CMM | 86.6
4 | L3IRIS | 73.6

Figure 8: Final detection score for Task 3 (_left_) — score ranges from 0
(worst) to 100 (best), and plot of the $F_{\beta=0.5}$ value for each distance
threshold (_right_) — normalized by the maximum distance of 50 pixels.

Results and ranking of each submitted method is given in fig. 8: table on the
left summarizes the detection score we computed and the plot on the right
illustrates the evolution of the retrieval $F_{\beta}$ score for each possible
normalized distance threshold. The L3IRIS approach is penalized by a lack of
local confirmation of intersection hypothesis, leading to false positives,
misses, and sub-optimal location. The CMM approach produced very accurate
detections thanks to morphological filters, but the Radon transform seems to
generate extra hypothesis or discard groups of them and therefore has some
stability issues. The IRISA approach performed globally very well thanks to is
robust line segment detector and its rule-based system, despite some false
positives. The UWB winning approach, finally, efficiently combined a binary
preprocessing with a coarse Hough transform and a final refinement leading to
superior accuracy.

##  5 Conclusion

This competition succeeded in advancing the state of the art on historical
atlas vectorization, and we thank all participants for their great
submissions. Shape extraction (Task 1) still require some progress to automate
the process completely. Map content detection (Task 2) and graticule line
detection (Task 3) are almost solved by proposed approaches. Future work will
need to improve on shape detection, and start to tackle shape classification
and text recognition.

## References

  * [1] Baloun, J., Král, P., Lenc, L.: Chronseg: Novel dataset for segmentation of handwritten historical chronicles. In: Proc. of the 13th International Conference on Agents and Artificial Intelligence (ICAART). pp. 314–322 (2021)
  * [2] Bloice, M.D., Roth, P.M., Holzinger, A.: Biomedical image augmentation using Augmentor. Bioinformatics 35(21), 4522–4524 (2019)
  * [3] Blusseau, S., Velasco-Forero, S., Angulo, J., Bloch, I.: Tropical and morphological operators for signal processing on graphs. In: Proc. of the 25th IEEE International Conference on Image Processing (ICIP). pp. 1198–1202 (2018)
  * [4] Chazalon, J., Carlinet, E.: Revisiting the coco panoptic metric to enable visual and qualitative analysis of historical map instance segmentation. In: 16th International Conference on Document Analysis and Recognition (ICDAR) (2021), to appear
  * [5] Grandvalet, Y., Bengio, Y.: Semi-supervised learning by entropy minimization. In: Proc. of the 17th International Conference on Neural Information Processing Systems (NIPS). pp. 529–536 (2004)
  * [6] Hernández, J., Marcotegui, B.: Morphological segmentation of building façade images. In: Proc. of the 16th International Conference on Image Processing (ICIP). pp. 4029–4032. IEEE (2009)
  * [7] Huang, G., Liu, Z., Van Der Maaten, L., Weinberger, K.Q.: Densely connected convolutional networks. In: Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 4700–4708 (2017)
  * [8] Kirillov, A., He, K., Girshick, R., Rother, C., Dollár, P.: Panoptic segmentation. In: Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 9404–9413 (2019)
  * [9] Lemaitre, A., Camillerapp, J., Coüasnon, B.: Multiresolution cooperation makes easier document structure recognition. International Journal on Document Analysis and Recognition (IJDAR) 11(2), 97–109 (2008)
  * [10] Leplumey, I., Camillerapp, J., Queguiner, C.: Kalman filter contributions towards document segmentation. In: International Conference on Document Analysis and Recognition (ICDAR). p. 765–769 (1995)
  * [11] Min, J., Kang, D., Cho, M.: Hypercorrelation squeeze for few-shot segmentation. arXiv preprint arXiv:2104.01538 (2021)
  * [12] Nguyen, N., Rigaud, C., Revel, A., Burie, J.: A learning approach with incomplete pixel-level labels for deep neural networks. Neural Networks 130, 111–125 (2020)
  * [13] Nina, O., Morse, B., Barrett, W.: A recursive otsu thresholding method for scanned document binarization. In: 2011 IEEE Workshop on Applications of Computer Vision (WACV). pp. 307–314. IEEE (2011)
  * [14] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI). pp. 234–241. Springer (2015)