[1]Haruhisa Oda

[1]Faculty of Medicine, The University of Tokyo, Hongo, Bunkyo-ku, 1130033,
Tokyo, Japan 2]Department of Physiological Chemistry and Metabolism, Graduate
School of Medicine, The University of Tokyo, Hongo, Bunkyo-ku, 1130033, Tokyo,
Japan 3]Isotope Science Center, The University of Tokyo, Yayoi, Bunkyo-ku,
1130032, Tokyo, Japan 4]Arithmer Inc., R&D Headquarters, Hongo, Bunkyo-ku,
1130033, Tokyo, Japan

# Novel definition and quantitative analysis of branch structure with
topological data analysis

<EMAIL_ADDRESS>Mayuko Kida  Yoichi Nakata  Hiroki
Kurihara  *  [  [  [

###### Abstract

While branching network structures abound in nature, their objective analysis
is more difficult than expected because existing quantitative methods often
rely on the subjective judgment of branch structures. This problem is
particularly pronounced when dealing with images comprising discrete
particles. Here we propose an objective framework for quantitative analysis of
branching networks by introducing the mathematical definitions for internal
and external structures based on topological data analysis, specifically,
persistent homology. We compare persistence diagrams constructed from images
with and without plots on the convex hull. The unchanged points in the two
diagrams are the internal structures and the difference between the two
diagrams is the external structures. We construct a mathematical theory for
our method and show that the internal structures have a monotonicity
relationship with respect to the plots on the convex hull, while the external
structures do not. This is the phenomenon related to the resolution of the
image. Our method can be applied to a wide range of branch structures in
biology, enabling objective analysis of numbers, spatial distributions, sizes,
and more. Additionally, our method has the potential to be combined with other
tools in topological data analysis, such as the generalized persistence
landscape.

###### keywords:

Persistent homology, Persistence landscape, Topological data analysis, Branch
structures

## Acknowledgements

This work was supported in part by JSPS KAKENHI Grant Numbers 19H01048 and
22H04991 (to H.K.).

##  1 Introduction

Branching network patterns are pervasive in nature, exhibiting their intricate
forms in diverse contexts. While a range of quantitative approaches has been
applied to study the branching network properties[1, 2], the recognition of
branching structures has often relied on subjective and intuitive judgments.
This challenge is particularly pronounced when dealing with original images
comprising discrete and punctate elements, as exemplified by microscopic
images of cellular nuclei composing blood and lymphatic vessels. The absence
of an objective framework for definitively discerning and quantifying branch
structures has hindered the advancement of rigorous numerical analyses. In the
present study, we give an objective framework that provides a mathematical
definition for branch structures based on topological data analysis (TDA),
particularly, persistent homology. We further develop a method to extract
information from branching structures in a way that can be used for
quantitative analysis.

Here, we should mention the term “branch” , which is often used for multiple
meanings in biological settings. In a broad sense, it refers to both the
protruding segments and the internal network structures. In a narrow sense, it
only means the protruding segments. In this manuscript, we will define the
internal and external structures that basically extract information on the
internal network structures and the protruding segments respectively.
Mathematically formal definitions of these structures will appear in the
Theory section.

Plotting points on the boundary of the convex hull of the image plays an
important role in this method. (In this paper, in order to avoid writing “ the
boundary of the convex hull" many times, we will just say “the convex hull".)
These points can be regarded as parameters of this method. In the “Theory”
section, we will mathematically explore how external and internal structures
behave under these parameters. We will see that internal structures have some
monotonicity relationship with respect to points on the convex hull, while
external structures do not. We give some explanations for these results. In
the “Results” section, we will apply our method to real images of lymph
vessels to see how it works. We will show some possible ways of quantitative
analysis including the use of persistence landscape. We will also deal with
the images of neurons and blood vessels to see that our method can be applied
to a wide range of branch structures that appear in biology. In the
“Discussion” section, we compare our method with other methods dealing with
some branch-like structures [3, 4]. We will see that these methods do not
directly give an answer to the problem of what branch is. Also, for future
applications to a broader range of image settings, we generalize persistence
landscape[5, 6] using 2 parameters and show that there are some
differentiability structures with respect to the 2 parameters. The calculation
of persistent homology is conducted using HomCloud (3.4.1)[7, 8]. The
calculation of the persistence landscape was conducted using the program code
by Katherine Benjamin available at https://gitlab.com/kfbenjamin/pysistence-
landscapes based on Bubenik(2017)[9]. The programs are written in Python
(version 3.7.9 and version 3.10.9). Note that image processing before the
persistent homological analysis is not the focus of this paper. Therefore, we
use binarized images which have already gone through several image processing
steps including manual noise reduction as our data.

##  2 Background

Here, we explain briefly the concepts of persistent homology and persistence
landscape. We only consider homology with coefficients in a field
$\mathbb{K}$. Suppose that we are given a point cloud $X$. From $X$, we create
some simplicial complex. In this paper, we use the Čech (alpha) complex. Let
$C(r)$ be the Čech complex at the radius $r$. Suppose that $C(r)$ changes at
the radii $r_{1}<\cdots<r_{i}<\cdots$. We define $C^{i}$ to be $C(r_{i})$. We
denote by $C^{i}_{n}$ the n-chains of $C^{i}$. From the definition of the Čech
complex, we have $C^{i}_{n}\subset C^{i+1}_{n}$ for all $i,n$. We get the
following commutative diagram with the horizontal arrows being the boundary
maps ($\partial$) and the vertical arrows being the inclusion maps ($\iota$)
induced by the above inclusion relationship.

$\setcounter{MaxMatrixCols}{11}\begin{CD}@V{}V{}V@V{}V{}V@V{}V{}V\\\
@>{}>{}>C^{i}_{n+1}@>{\partial}>{}>C^{i}_{n}@>{\partial}>{}>C^{i}_{n-1}@>{}>{}>\\\
@V{\iota}V{}V@V{\iota}V{}V@V{\iota}V{}V\\\
@>{}>{}>C^{i+1}_{n+1}@>{\partial}>{}>C^{i+1}_{n}@>{\partial}>{}>C^{i+1}_{n-1}@>{}>{}>\\\
@V{}V{}V@V{}V{}V@V{}V{}V\\\ \end{CD}$

From the horizontal part, we can define the n-th homology $H_{n}(C^{i})$. We
define $H_{n}(C)$ to be the direct sum
$\displaystyle\bigoplus_{i}H_{n}(C^{i})$. We introduce a grading to $H_{n}(C)$
by defining $x\cdot:H_{n}(C^{i})\rightarrow H_{n}(C^{i+1})$ as $x\cdot
m:=\iota_{*}(m)$ for $m\in H_{n}(C^{i})$. Here, $\iota_{*}$ is a homomorphism
between homology groups induced by inclusion maps. This grading makes
$H_{n}(C)$ into a $\mathbb{K}[x]$-graded module. We decompose this module by
structure theorem[10]. The result of this decomposition is visualized by
barcodes[11, 12], the collection of bars. The left ends of the bars are called
the births and the right ends of the bars are called the deaths. Persistence
diagram[13] is a 2-dimensional representation of a barcode. For each bar in a
barcode, we plot a point whose $x$-coordinate is the birth and whose
$y$-coordinate is the death of the bar. We regard the barcode as the set of
intervals $\\{I_{j}\\}$. Persistence landscape is the set of functions
$\\{\lambda_{k}(t)\\}_{k=1,2,\ldots}$ defined as $\lambda_{k}(t):=\sup(u\geq
0|\\#\\{j|[t-u,t+u]\subset I_{j}\\}\geq k)$.

##  3 Method

First, we explain the problem posed in the Introduction in more detail. In
Frye et al. (2018) [1], they analyze the lymphatic vessel using criteria such
as vessel diameter and branchpoints. These analyses are possible because they
are dealing with structures that “look like” branches. Applying these criteria
for the structures that do not look like branches (e.g. Fig. 1(a)) will be
misleading. Thus, we need to decide whether our structure is branch-like or
not before we use the criteria in Frye et al. [1], but this decision is
subjective. This also interrupts the comparison between a broader range of
vessel structures such as Fig. 1(a) and (b).

Figure 1: (a,b) Examples of the images of lymph vessels that we will analyze
in this paper

Since vessel structures have external parts and internal parts as we mentioned
in the Introduction, one good way out of this problem is to separately analyze
the external and internal parts. In Suchting et al. (2007) [2], they divide
the blood vessels into 2 parts: vascular front (external parts) and vascular
plexus (internal parts). In their images, the vessels form connected
components, which enables the simple distinction of internal/external
structures. On the other hand, our images are made of discrete cells. Thus, it
is necessary to define the internal and external structures objectively. Now,
we explain the motivations for persistent homological definitions of the
internal/external structures and the method to extract the information from
our images.

Figure 2: (a) The image of lymph vessels. We use the white points as a point
cloud. (b) The persistence diagram calculated from the original image of lymph
vessels. (c) The points on the convex hull of the image and the original
points. (d) The persistence diagram calculated from the points on the convex
hull and the points of the original image

From now on, we use 1-dimensional persistence diagrams unless otherwise
stated, because what we want to detect is a ring structure in 2D images. We
use the white points in the original image (Fig. 2(a)) as a point cloud. We
construct the persistence diagram from this image to get Fig. 2(b). Then we
plot some points on the convex hull of the image (Fig. 2(c)). These points on
the convex hull make the external structures (based on our intuition, not
defined yet) into ring structures that can be detected by persistent homology.
We construct the persistence diagram from this new point cloud to get Fig.
2(d). We consider that internal structures should not be affected by the
points on the convex hull, while external structures should be detected after
adding points on the convex hull. Therefore, we take the intersection of two
persistence diagrams as the internal structures. We choose points in the
latter diagram that are not in the former diagram and consider that they are
the external structures. We can change the results by changing the number of
points on the convex hull. If we want to compare different images, we should
fix the interval of the plots. The theory in the next section is about how the
external and internal structures behave when we change the plots on the convex
hull.

##  4 Theory

First, we give a formal definition of internal/external structures. Let
$PD_{1}(.)$ denote the 1-dimensional persistence diagram constructed from some
point cloud.

######  Definition 1.

Let $X$ be a point cloud and $U$ be a set of points on its convex hull. We
define the internal structure as $PD_{1}(X)\cap PD_{1}(X\cup U)$ and the
external structure as $PD_{1}(X\cup U)\backslash PD_{1}(X)$.

Intuitively, the more points we plot on the convex hull, the fewer internal
structures and the more external structures we will detect. We will see that
the former is true but the latter does not hold. This statement, as it stands,
is not mathematically sound, so we first make the mathematical meaning of this
statement clear.

Let $X$ be an initial point cloud (the input image in our settings) and
$U_{1},U_{2}$ be sets of points on the convex hull. Suppose that there is an
inclusion relationship between $U_{1}$ and $U_{2}$, namely, $\emptyset\subset
U_{1}\subset U_{2}$. In the following arguments, we will change the radius of
the complex used for persistent homology and the plots on the convex hull.
When we want to clarify which we are talking about, we will use the notation
like “at $r=r_{1}$” for radius and “at $U=U_{1}$” for plots on the convex hull
instead of “at $r_{1}$” or “at $U_{1}$”.

###  4.1 Internal structures

We focus on the internal structures. As we defined earlier, at $U=U_{1}$ and
$U_{2}$, the detected internal structures are $PD_{1}(X)\cap PD_{1}(X\cup
U_{1})$ and $PD_{1}(X)\cap PD_{1}(X\cup U_{2})$, respectively. The following
definition explains how we relate loops in the images to the points in
persistence diagrams. Here, given the points $a_{1},\ldots,a_{n}$, the loop
$[a_{1},\ldots,a_{n}]$ means $\langle a_{1},a_{2}\rangle+\cdots+\langle
a_{n},a_{1}\rangle$, where $\langle u,v\rangle$ represents a 1-simplex. For a
loop $L$, we denote by $[L]$ the equivalence class of $L$.

######  Definition 2.

We say that a loop $L$ can represent a bar $[b,d]$ if $[L]$ can serve as a
basis of the homology group of the bar at $r=b$.

We give an example in order to make clear the meaning of the following
expression: a loop’s equivalence class can serve as a basis of the homology
group at the birth of a bar. Figure 3 shows an image of a symmetric point
cloud. If we calculate persistent homology from the image, we get the barcode
shown in Fig. 3. The equivalence class of the loop constructed by all the
points in the point cloud can serve as a basis ($1\in\mathbb{K}$) of the
homology group at the birth of the longer bar. On the other hand both the
equivalence classes of two smaller loops (right and left) can serve as a basis
($(0,1)\in\mathbb{K}\oplus\mathbb{K}$) of the homology group at the birth of
the shorter bar.

Figure 3: An example to make clear the meaning of the expression: a loop’s
equivalence class can serve as a basis of the homology group at the birth of a
bar

######  Definition 3 (detectable internal structure).

A loop $L$ is called a detectable internal structure at $U$ if there exists a
point $p\in PD_{1}(X)\cap PD_{1}(X\cup U)$ such that $L$ can represent $p$
both for $PD_{1}(X)$ and $PD_{1}(X\cup U)$.

We now state the proposition which shows how the internal structure behaves
with respect to the points on the convex hull.

######  Proposition 1.

If a loop that is a detectable internal structure at $U=\emptyset$ is not a
detectable internal structure at $U=U_{1}$, then it is not a detectable
internal structure at $U=U_{2}$.

In the remaining part of this subsection, we will make some definitions and
statements for the proof of Prop. 1 and prove it. We first define the birth
and death for loops and linear combinations of loops in a similar way as in
Oda(2023)[14].

######  Definition 4 (birth and death for loops).

The birth of a loop or a linear combination of loops $L$ denoted by $B(L)$ is
$b$ if all the 1-simplex in the loop or the linear combination of loops are in
$C^{b}_{1}$ for the first time at $r=b$. The death of a loop or a linear
combination of loops $L$ denoted by $D(L)$ is $d$ if the loop or the linear
combination of loops is in the image of the boundary map for the first time at
$r=d$.

For a bar $Bar=[b,d]$, we denote the birth $b$ by $B(Bar)$ and death $d$ by
$D(Bar)$.

######  Definition 5.

We say that a loop or a linear combination of loops $L$ can be in a bar
$[b,d]$ if $B(L)\in[b,d)$ and $[L]$ can serve as a basis of the homology group
of the bar at $r=B(L)$.

Note that if a loop $L$ can be in a bar $[b,d]$, then $D(L)=d$.

######  Lemma 2.

Let $L,L^{\prime}$ be two loops or linear combinations of loops. Suppose that
$\exists k\in\mathbb{K}\backslash\\{0\\},L\sim kL^{\prime}$ at $r=c$. Let
$D(L)=D(L^{\prime})=d$. Let $B(L^{\prime})=b^{\prime}<c$. Then, for any $b$
such that $b^{\prime}<b<d$, $L$ cannot be in a bar $[b,d]$. Also, $L$ cannot
represent a bar $[b,d]$.

###### Proof.

$L^{\prime}$ can be written as the linear combination of loops whose
equivalence classes are the bases of homology groups of bars at
$r=b^{\prime}$. After $b^{\prime}$, the same linear combination of loops is
equivalent to $L^{\prime}$ at any radius. If all the bars’ deaths are less
than $d$, then $D(L^{\prime})<d$, which is a contradiction. In the linear
combination of the loops, we choose the ones whose death points are $d$ (this
set is not empty). We set all the other loops’ coefficients in the linear
combination to be $0$. There exists a positive number $\epsilon$ such that the
new linear combination is equivalent to $L^{\prime}$ after $d-\epsilon$. This
linear combination is also equivalent to $(1/k)L$ after
$\max\\{c,d-\epsilon\\}$. Suppose that $L$ can be in a bar $[b,d]$. Since
$b^{\prime}<b$, no loop in the new linear combination is chosen from the bar
$[b,d]$. This contradicts the fact that the bars are linearly independent at
any point. We can use the same argument if we suppose that $L$ can represent a
bar $[b,d]$. ∎

######  Lemma 3.

If a loop $L$ with $B(L)=b$ and $D(L)=d$ can represent a bar, then the bar is
$[b,d]$.

###### Proof.

Suppose that $L$ can represent a bar $[b^{\prime},d]$. It is impossible to
have $b^{\prime}<b$. Thus, the only possibility for $b\neq b^{\prime}$ is
$b<b^{\prime}(<d)$. $L\sim L$ at $r=b^{\prime}$. $B(L)$ is less than
$b^{\prime}$. Then, from Lem. 2, $L$ class represent a bar $[b^{\prime},d]$. ∎

From this, we can see that if a loop can represent a bar, then the loop can be
in the bar. Now, we will prove Prop. 1.

###### Proof of Prop. 1.

Suppose that a loop $L$ with $B(L)=b$ and $D(L)=d$ is a detectable internal
structure at $U=\emptyset$. From Lem. 3, $[b,d]$ is the only bar that $L$ can
represent. Therefore, $L$ not being a detectable internal structure at
$U=U_{1}$ means that at $U=U_{1}$, $L$ cannot represent the bar $[b,d]$. We
divide the proof into cases.

Case1: $L$ cannot be in a bar at $U=U_{1}$.
Case1-1: $B(L)=D(L)$.
Case1-2: $L$ can only be expressed as a linear combination of loops whose
equivalence classes are bases of homology groups of multiple bars.
Case2: $L$ can be in a bar at $U=U_{1}$.
Case2-1: The birth of the bar in Case2 must be smaller than $b$.
Case2-2: $D(L)\neq d$.

Note that when we increase the points in the point cloud, the birth of a loop
does not change and the death of a loop does not get large. Therefore, we see
that in Case 1-1 and Case 2-2, we get into the same situation at $U=U_{2}$.

When we deal with Case 1-2 and Case 2-1, we can assume that $D(L)=d$ at
$U=U_{1}$ and $U_{2}$, because otherwise, if $D(L)$ is not $d$ at $U=U_{1}$,
we can use a similar argument as in Case1-1 and Case2-2, and if $D(L)$ is not
$d$ at $U=U_{2}$, from Lem. 3, $L$ cannot represent a bar $[b,d]$.

First, we look at Case 2-1. Let $b^{\prime}$ be the birth of the bar that $L$
can be in. Let $L^{\prime}$ be the loop that can represent the bar
$[b^{\prime},d]$. At $U=U_{1}$, $L\sim kL^{\prime}$ at $r=b$, where
$k\in\mathbb{K}\backslash\\{0\\}$. Also, we have $B(L^{\prime})=b^{\prime}<b$.
These two properties also hold at $U=U_{2}$. Since $b^{\prime}<b<d$, from Lem.
2, $L$ cannot represent a bar $[b,d]$ at $U=U_{2}$.

Finally, we deal with Case 1-2. At $r=b$, take the loops $L_{1},\ldots,L_{k}$
where $[L_{i}]$s are bases of homology groups of multiple bars
$Bar_{1},\ldots,Bar_{k}$ such that $L=c_{1}L_{1}+\cdots+c_{k}L_{k}$, where
$c_{1},\ldots,c_{k}$ are coefficients. Since $D(L)=d$, $\max_{1\leq i\leq
k}(D(Bar_{i}))=d$. Define $I$ to be $I:=\\{1\leq i\leq k|D(Bar_{i})=d\\}$. If
there exists $i\in I$ such that $B(Bar_{i})=b$, then we can choose $[L]$ as a
basis of the homology group of $Bar_{i}$ instead of $[L_{i}]$, which is a
contradiction. Thus, $b^{\prime\prime}:=\max_{i\in I}(B(Bar_{i}))<b$. At
$r=b^{\prime\prime}$, take the loops $\\{L^{\prime\prime}_{i}\\}_{i\in I}$
where $[L^{\prime\prime}_{i}](i\in I)$ are bases of homology groups of
$Bar_{i}(i\in I)$. We can choose the coefficients $c^{\prime\prime}_{i}(i\in
I)$ such that $[c^{\prime\prime}_{i}L^{\prime\prime}_{i}]=[c_{i}L_{i}]$ at
$r=b$. Let $L^{\prime\prime}$ be $L^{\prime\prime}:=\sum_{i\in
I}c^{\prime\prime}_{i}L^{\prime\prime}_{i}$. There exists a sufficiently small
positive number $\epsilon$ such that $[L^{\prime\prime}]=[L]$ at
$r=d-\epsilon$. We also have $B(L^{\prime\prime})\leq
b^{\prime\prime}<d-\epsilon$. These two properties also hold at $U=U_{2}$.
Since $b^{\prime\prime}<b<d$, from Lem. 2, $L$ cannot represent a bar $[b,d]$
at $U=U_{2}$. ∎

This result can be understood as the monotonicity relationship with respect to
the plots on the convex hull.

###  4.2 External structures

Now, we deal with external structures. As we defined earlier, at $U=U_{1}$ and
$U_{2}$, the detected internal structures are $PD_{1}(X\cup U_{1})\backslash
PD_{1}(X)$ and $PD_{1}(X\cup U_{2})\backslash PD_{1}(X)$, respectively.

######  Definition 6.

A loop $L$ is called a detectable external structure at $U$ if there exists a
point $p\in PD_{1}(X\cup U)\backslash PD_{1}(X)$ such that $L$ can represent
$p$ for $PD_{1}(X\cup U)$.

For external structures, monotonicity relationships as in the internal
structures do not hold. This can be understood from Fig. 4. In Fig. 4(b), we
add a point on the left side of the image in Fig. 4(a). In Fig. 4(c), we add
points on the lower part of the image in addition to the point on the left
side. We calculate persistent homology for these three images. The barcodes
are shown in a way that makes it clear how the bases of the homology groups in
the bars are mapped when the radius changes. We will see that the large loop
which is a detectable external structure in Fig. 4(b) is not a detectable
external structure in Fig. 4(c).

Figure 4: (a) The original image and its barcode. (b) The original image plus
the point on the left opening and the resulting barcode. (c) The image in (b)
plus the points on the lower opening and the resulting barcode. The large loop
which is a detectable external structure in (b) cannot be a detectable
external structure in (c)

This phenomenon is related to the resolution of the image. If we look at the
original figure from far away, we only find the opening in the left part of
the image. Then, we will think that the right part of the figure is part of a
large external structure. On the other hand, if we take a close look at the
image, we will also find the opening in the lower part of the image.

##  5 Results

In the following part of the paper, the unit for the lengths is pixel unless
otherwise specified.

###  5.1 Lymph vessels

We first count the number of external/internal structures in the images of
lymph vessels. We plot points on the convex hull at the interval of 20. We
count the number of detected structures whose persistences are larger than 5.
The result is shown in Fig. 5. We plotted the circumcenter of the death
positions as in Oda et al. (2023) [15].

Figure 5: The result of detecting external/internal structures in the images
(red/blue points)

Since we have the information of positions of external/internal structures, we
can explore their spatial distributions. We can also extract their size
information from death points, which can be used, for example, for the
comparison of external and internal structure sizes.

Since we have constructed diagrams for external and internal structures, we
can also conduct more topological analyses of our results. For example, we can
focus on the internal structures and construct persistence landscapes from
them. We calculate the integral of the square of the first function in the
persistence landscape. The result is shown in Online Resource (Supplementary
Fig. S1). This could be understood as a measure of some kind of internal
complexity. Constructing these kinds of measures from diagrams and finding
biologically important ones will be interesting future work (See “Discussion”
section).

###  5.2 Neurons

Our method can be applied to a wide range of branch structures that appear in
biology. Here, we present an example of the analysis of branch structure in
neurons. Figure 6(a) shows the result of analyzing the image in Tschida et al.
(2012)[16] (Fig. 1 A, we used the image without the white arrow that is
available in https://medicalxpress.com/news/2012-03-deafening-affects-vocal-
nerve-cells.html.) The interval for the plots on the convex hull was 10, and
the threshold for the persistences was 2. We also analyzed the image in Desai-
Chowdhry et al. (2022)[17] (Fig. 1). The interval for the plots on the convex
hull was 15. If we set the threshold for the persistences to be 2, we get Fig.
6(b). If we want to detect only the long persisting internal structures, we
can increase the threshold of the persistence for the internal structure. As a
result, we get Fig. 6(c) (the threshold for internal structure is changed into
7).

Figure 6: (a) The result of analyzing the image of a neuron[16]. The detected
external/internal structures are plotted by red/blue points. (b,c)The result
of analyzing the image of a neuron[17]. We can increase the threshold of
persistence if we want to focus on the long persisting structures

###  5.3 Blood vessels

Now, we will apply our method to blood vessels in Liu et al. (2010)[18] (Fig.
2B left and right). Figure 7(a) shows the result of analyzing the two images
with the interval for the plots on the convex hull being 15 and the threshold
of the persistences being 2. We detect more internal structures in the left
image (Notch3(+/+)) compared to the right image (Notch3(-/-)). If we change
the threshold of the persistence for internal structure to 10, we detect fewer
internal structures in Notch3(+/+) than in Notch3(-/-) (Fig. 7(b)).

Figure 7: (a) The result of analyzing the images in Liu et al.[18]. More
internal structures are detected in the left image compared to the right
image. (b) The result of increasing the threshold of the persistences for the
internal structures. Now, we detect more internal structures in the right
image compared to the left image

##  6 Discussion

###  6.1 Comparison with non-TDA methods

In Thunbo et al. (2017)[3], they analyze the vessel using the area of white
points divided by the area of the convex hull. This method is reasonable
because they tried to analyze the density of the vessels. It is expected that
this method returns a larger value if we make the width of the vessels larger
without changing their shape. On the other hand, we aim to look at external
and internal structures. Thus, our method should not be affected greatly by
the change in the width of the vessels. We use model images in Online Resource
(Supplementary Fig. S2) to see this difference. Table 1 shows that the method
in Thunbo et al. (2017) is affected by the change in the width of vessels,
while our method is not. We set the interval of the plots on the convex hull
to be $3$ and the threshold for the persistence to be $0.5$.

method | model 1 | model 2 | model 3 | model 4 | model 5 | model 6 | model 7 | model 8
---|---|---|---|---|---|---|---|---
| vessel area
---
over convex hull
0.13 | 0.18 | 0.24 | 0.29 | 0.34 | 0.38 | 0.42 | 0.46
| number of external
---
/internal structure
determined with PH
10/11 | 9/11 | 10/11 | 9/11 | 11/11 | 10/10 | 10/12 | 10/12
Table 1: The method in Thunbo et al. (2017) is affected by the change in the
width of vessels, while our method is not. A model with a larger number has a
greater line width

Skeletonization is one of the standard methods to analyze branch or network-
like structures as in Carpentier et al. (2020)[4], where they analyze
angiogenesis. One of our purposes is to determine whether some structure is a
branch or not, but skeletonization makes everything into branch-like images.
Thus, this is not suited to our purpose.

Since the main part of our method is to define external and internal
structures, there is no such thing as “ground truth” or “expected result”.
Thus, it is impossible to give some statistical evaluation of our results
against them. Rather, it might be interesting as future works to create
several features based on our method and use them for images, for example,
created by a simulation of branch formation in order to find features that
express some kind of biological status.

###  6.2 Comparison with other TDA methods

TDA has been applied to analyze various biological structural patterns. When
we focus on branch structures, Reimann et al. (2017)[19] and Kanari et al.
(2018, 2019)[20, 21] deal with neuronal structures. Bendich et al. (2016)[22]
analyzes brain arteries and Jiang (2022)[23] analyzes retina blood vessels
using persistent homology. When we look for a wider range of patterns in
biology or medicine, Tanabe et al. (2021)[24] uses TDA for the CT images of
COPD, IPF, and CPFE, and Giansiracusa et al. (2019)[25] conducts fingerprint
classification with persistent homology. Thomas et al. (2021)[26] takes a
topological approach to C. elegans movement patterns. Also, there are various
related theoretical results such as Kanari et al. (2020)[27].

Our method adds to this existing TDA knowledge especially in the following
points:

  * •

We intentionally add points on the convex hull to define the internal and
external structures. Adding new points intentionally to the original data to
detect some desired structures is a novel way to use TDA.

  * •

We compare two different persistence diagrams and define new diagrams by
taking the intersection or difference between them. We also constructed
mathematical theories for these new diagrams. This, combined with the above
point, provides a novel framework for TDA itself as well as its new usage.

###  6.3 More discussions on the underlying idea of our framework

In the theory section, we explained how the internal and external structures
change under the change of the points on the convex hull. Now, the readers
might wonder whether the results of our framework (internal/external
structures) are extracting some intrinsic property of the original data. This
question is related to the underlying idea of our framework: the notion of
internal/external structures is not determined by the data alone but also by
our purposes. For example, we might want to limit our focus on the “very best"
internal structures or we might want to include some “intermediate"
structures.

To justify these subjective ideas, an objective and quantitative description
should be developed. Using our framework, we can explain the criteria used for
the internal/external structure distinction objectively and quantitatively,
e.g. “We plotted points on the convex hull of the images at the interval of
20." In Online Resource (Supplementary Fig. S3), we show an example of the
change of internal/external structures with respect to the plots on the convex
hull.

Our framework naturally connects to multiparameter persistence, and once its
data analysis framework (such as mapping the algebraic structures back to the
original data) is developed, it will improve our framework.

###  6.4 Generalized persistence landscape

Finally, we will introduce the generalized persistence landscape. Although we
do not use it in this paper, we will construct it for future applications. One
of the good points of the persistence landscape is that the process is
invertible. We can recover the persistence diagram from the persistence
landscape. The problem with persistence landscape is that, since it uses the
diagonal line as the baseline, it assumes the importance of the lengths of
bars. Sometimes, the important features of the data might not lie in long
bars[22]. Also, the fact that our method preserves the information on births
and so on allows us to expect that our method might work well with a tool that
makes it possible to focus on features other than persistence. We want to
generalize the persistence landscape in a way that meets this requirement and
at the same time preserves the invertibility. We define the generalized
persistence landscape as follows. Let
$R(\phi):\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ denote the rotation by
$\phi$ around the origin, and $T(d):\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$
denote the translation by $d$ along the $y$-axis. For a persistence diagram
$D$, we denote by $\lambda(D)$ the persistence landscape constructed from $D$.
For $X\subset\mathbb{R}^{2}$, $X_{+}:=\\{(x,y)\in X|x\leq y\\}$ and
$X_{-}:=\\{(x,y)\in X|x>y\\}$. Let $S:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$
denote the swapping of the coordinates ($(x,y)\mapsto(y,x)$).

######  Definition 7 (Generalized persistence landscape).

For a persistence diagram $D\subset\mathbb{R}^{2}$, the generalized
persistence landscape $G\lambda[\theta,y](D)$ is defined to be
$G\lambda[\theta,y](D):=\lambda((R(\pi/4-\theta)\circ
T(-y)(D))_{+})\cup\lambda(S((R(\pi/4-\theta)\circ T(-y)(D))_{-}))$. We
represent the elements of $\lambda((R(\pi/4-\theta)\circ T(-y)(D))_{+})$ as
$G\lambda_{1},G\lambda_{2},\ldots,G\lambda_{k},\ldots$ and the elements of
$\lambda(S((R(\pi/4-\theta)\circ T(-y)(D))_{-}))$ as
$G\lambda_{-1},G\lambda_{-2},\ldots,G\lambda_{-k},\ldots$.

This definition means that we change our baseline from the diagonal line to an
arbitrary line. See the example figure in Online Resource (Supplementary Fig.
S4).

Since $\lambda$, $R(\phi)$, and $T(d)$ are all invertible, we can recover the
persistence diagram from the generalized persistence landscape. The original
persistence landscape $\lambda$ is included in the generalized persistence
landscape as $G\lambda[\pi/4,0]$.

The concepts of linear combination, difference, and norm of persistence
landscapes can be extended to generalized persistence landscapes. The only
difference is that now we have functions with negative subscripts.

When we want to use the generalized persistence landscape for image
classification, we, for example, calculate the generalized persistence
landscape for each of the images, take the average landscape for each of the
groups, and calculate the distance of a landscape from the average landscapes.
We classify the landscape to the group whose average landscape is closest to
the input landscape. We change the parameters and see how the classification
result changes. This process goes along well with gradient descent in machine
learning because the distance between the landscape and the average landscape
is partially differentiable with respect to $\theta$ and $y$. We will prove
this in a more general setting. We use 2-norm for the distance. In the
following proposition, the rotation and translation are generalized as moving
points of the diagrams. Thus, the points in persistence diagrams can be in the
region $y\leq x$, and when we say persistence landscape, we mean
$G\lambda[\pi/4,0]$.

######  Proposition 4.

Suppose that we are given a persistence diagram $D$ and persistence diagrams
${D^{\prime}}^{j}(j=1,\ldots,N)$. For each of the points $p_{t}$ in the
persistence diagrams, we give constants $\alpha_{t},\beta_{t}$. We move each
of the points $p_{t}$ in the persistence diagrams by
$\alpha_{t}\epsilon+O(\epsilon^{2})$ along the $x$-axis and by
$\beta_{t}\epsilon+O(\epsilon^{2})$ along the $y$-axis. Let $\tilde{D}$ and
$\tilde{{D^{\prime}}^{j}}$ be the resulting diagrams. Define $d(\epsilon)$ to
be the distance between the landscape of $\tilde{D}$ and the average landscape
of $\tilde{{D^{\prime}}^{j}}$. Then, $d(\epsilon)$ is differentiable at
$\epsilon=0$.

###### Proof.

Let $\lambda_{i}(i=-k,\ldots,-1,1,\ldots,n)$ be the elements of persistence
landscape for $D$, and ${\lambda^{\prime}_{i}}^{j}$ be the elements of
persistence landscape for ${D^{\prime}}^{j}$. Let $\tilde{\lambda_{i}}$ and
$\tilde{{\lambda^{\prime}_{i}}^{j}}$ be the elements of corresponding
persistence landscapes after moving points. $d(0)$ can be written as

$d(0)=\frac{1}{N}\sqrt{\sum_{i=1}^{n}\int(\sum_{j=1}^{N}\lambda_{i}-{\lambda^{\prime}_{i}}^{j})^{2}dx+\sum_{i=-k}^{-1}\int(\sum_{j=1}^{N}\lambda_{i}-{\lambda^{\prime}_{i}}^{j})^{2}dx}$

$d(\epsilon)$ can be written similarly with tildes on lambdas. Choose
$\epsilon$ to be so small that for all $\lambda_{i}$ or
${\lambda^{\prime}_{i}}^{j}$ and corresponding $\tilde{\lambda_{i}}$ or
$\tilde{{\lambda^{\prime}_{i}}^{j}}$, the difference
$\epsilon_{i}=\lambda_{i}-\tilde{\lambda_{i}}$ or
${\epsilon^{\prime}}_{i}^{j}={\lambda^{\prime}_{i}}^{j}-\tilde{{\lambda^{\prime}_{i}}^{j}}$
satisfies the following: for all intervals where $\lambda_{i}$ or
${\lambda^{\prime}_{i}}^{j}$ does not bend, the slope of $\epsilon_{i}$ or
${\epsilon^{\prime}}_{i}^{j}$ is $0$ except for both ends whose width can be
written as $b\epsilon$, where $b$ is the constant determined by
$\alpha_{t},\beta_{t}$. The value of $\epsilon_{i}$ or
${\epsilon^{\prime}}_{i}^{j}$ where its slope is $0$ can be written as
$c\epsilon$, where $c$ is the constant determined by $\alpha_{t},\beta_{t}$.
We need to show that $(d(\epsilon)-d(0))/\epsilon$ converges when $\epsilon\to
0$. Since we have the following equality:

$\begin{split}\int(\sum_{j=1}^{N}\tilde{\lambda_{i}}-\tilde{{\lambda^{\prime}_{i}}^{j}})^{2}dx=&\int(\sum_{j=1}^{N}\lambda_{i}-{\lambda^{\prime}_{i}}^{j})^{2}dx+2\sum_{j=1}^{N}\sum_{s=1}^{N}\int(\lambda_{i}-{\lambda^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx\\\
&+\sum_{j=1}^{N}\sum_{s=1}^{N}\int(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx,\end{split}$

we can prove the statement by showing that the last 2 terms in the above
equality are of the form $const.\epsilon+O(\epsilon^{2})$.

We first deal with
$\int(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx$.
We have
$|\int(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx|\leq\int|\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j}||\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s}|dx$.
The maximum value of $|\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j}|$ can be
written as $r\epsilon$, where $r$ is a constant determined by
$\alpha_{t},\beta_{t}$. Also, the support of
$|\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j}||\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s}|$
has finite length. Therefore, we have
$|\int(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx|\leq
O(\epsilon^{2})$.

Next, we deal with
$\int(\lambda_{i}-{\lambda^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx$.
We calculate this integral for each of the intervals where $\lambda_{i}$ and
${\lambda^{\prime}_{i}}^{j}$ do not bend nor does their difference change
signs. Take one of such intervals $I$. On $I$, both $\lambda_{i}$ and
${\lambda^{\prime}_{i}}^{j}$ do not bend, which means that
$\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s}$ has slope $0$ except for the both
ends. The width of these ends and the maximum absolute value of
$\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s}$ at these ends can be bounded by
$u\epsilon$ and $v\epsilon$, where $u,v$ are constants independent of
$\epsilon$. The absolute value of $\lambda_{i}-{\lambda^{\prime}_{i}}^{j}$ on
$I$ is bounded by a constant $l$, which is independent of $\epsilon$. The
value of $\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s}$ where its slope is $0$ can
be written as $w\epsilon$, where $w$ is a constant independent of $\epsilon$.
Therefore, we can write

$\int(\lambda_{i}-{\lambda^{\prime}_{i}}^{j})(\epsilon_{i}-{\epsilon^{\prime}_{i}}^{s})dx=w\epsilon\int(\lambda_{i}-{\lambda^{\prime}_{i}}^{j})dx+\delta$

where $\delta$ is the error term bounded by $uvl\epsilon^{2}=O(\epsilon^{2})$.
Note that the interval of the integral $I$ is not affected by $\epsilon$,
which means that the first term on the right-hand side of the above equality
is of the form $const.\epsilon$. ∎

From Prop. 4, we get the following corollary.

######  Corollary 5.

Suppose that we are given a persistence diagram $D$ and persistence diagrams
${D^{\prime}}^{j}(j=1,\ldots,N)$. The distance between the generalized
persistence landscape $G\lambda[\theta,y](D)$ and the average of the
generalized persistence landscapes $G\lambda[\theta,y]({D^{\prime}}^{j})$ is
partially differentiable with respect to $\theta$ and $y$.

##  7 Conclusion

In this paper, we constructed the persistent homological definitions of
external and internal structures for discrete branch-like structures. Based on
this definition, we developed a method to detect external and internal
structures in the images. We also established mathematical theories explaining
the behavior of external and internal structures with respect to the points on
the convex hull. We showed that our method can detect external and internal
structures in a way that can be used for numerical analysis. As examples, we
counted the number of external/internal structures and also conducted an
internal structure analysis with persistence landscape. We showed that our
method can be applied to a wide range of branch structures that appear in
biology. We also explained the advantages of our method over other methods
using TDA. For future applications, we constructed the generalized persistence
landscape.

With these tools, we can develop various quantitative measures of
external/internal structures and search for the ones with biological
significance in specific contexts in future works. As for applications, we can
use our method for various “branch-like” structures to objectively analyze and
compare them.

## Statements and Declarations

### Data Availability

The datasets analyzed during the current study are available from the
corresponding author upon reasonable request.

### Code Availability

The program code and model images can be found in the following link.
https://drive.google.com/drive/folders/1sjPd2z_63iZEEInYAETRZKqUualA3plt?usp=sharing

### Competing Interests

None.

## Author contributions statement

H.O., M.K., and H.K. conceived the research idea. H.O. developed the lymph
vessel analysis method based on persistent homology, generalized persistence
landscape, and their theoretical backgrounds and drafted the manuscript. M.K.
took images of lymph vessels. Y.N. proofread the original manuscript, fixed
some ambiguous expressions, and introduced several symbols to make the
explanations clear. H.O., M.K., and H.K. discussed the biological aspects of
the method. H.O. and Y.N. discussed the mathematical aspects of the method.
H.K. supervised the experimental results. All authors reviewed the manuscript.

## References

  * [1] Frye, M. et al.: Matrix stiffness controls lymphatic vessel formation through regulation of a GATA2-dependent transcriptional program. Nat Commun. 9, 1511 (2018)
  * [2] Suchting, S. et al.: The Notch ligand Delta-like 4 negatively regulates endothelial tip cell formation and vessel branching. PNAS. 104, 3225–3230 (2007)
  * [3] Thunbo, M. Ø. et al.: CT angiography of the fetoplacental macrovasculature in normal pregnancies and in those complicated by fetal growth restriction. Placenta. 57, 313–314 (2017)
  * [4] Carpentier, G. et al.: Angiogenesis Analyzer for ImageJ-A comparative morphometric analysis of “Endothelial Tube Formation Assay” and “Fibrin Bead Assay”. Sci Rep. 10, 11568 (2020)
  * [5] Bubenik, P.: Statistical topological data analysis using persistence landscapes. J Mach Learn Res. 16, 77–102 (2015)
  * [6] Bubenik, P.: The persistence landscape and some of its properties. In: Baas, N., Carlsson, G., Quick, G., Szymik, M., Thaule, M. (eds) Topological Data Analysis. Abel Symposia, vol 15. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43408-3_4
  * [7] Obayashi, I.: HomCloud, data analysis package based on persistent homology (theory of biomathematics and its applications XVI -toward quantitative understanding for life sciences-). RIMS Kokyuroku. 2166, 103–107 (2020)
  * [8] Obayashi, I., Nakamura, T., Hiraoka, Y.: Persistent Homology Analysis for Materials Research and Persistent Homology Software: HomCloud. J Phys Soc Japan. 91, 091013 (2022)
  * [9] Bubenik, P., Dlotko, P.: A persistence landscapes toolbox for topological statistics. J Symb Comput. 78, 91–114 (2017)
  * [10] Zomorodian, A., Carlsson, G.: Computing Persistent Homology. Discrete Comput Geom. 33, 249–274 (2005)
  * [11] Collins, A., Zomorodian, A., Carlsson, G., Guibas, L. J.: A barcode shape descriptor for curve point cloud data. Comput Graph. 28, 881–894 (2004)
  * [12] Ghrist, R.: Barcodes: The persistent topology of data. Bull Am Math Soc. 45, 61–75 (2008)
  * [13] Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput Geom. 37, 103–120 (2007)
  * [14] Oda, H.: Counting and detecting figures using persistent homology. JSIAM Lett. 15, 33–36 (2023)
  * [15] Oda, H., Tonami, K., Nakata, Y., Takubo, N., Kurihara, H.: Persistent homological cell tracking technology. Sci Rep. 13, 10882 (2023)
  * [16] Tschida, K. A., Mooney, R.: Deafening drives cell-type-specific changes to dendritic spines in a sensorimotor nucleus important to learned vocalizations. Neuron. 73, 1028–1039 (2012)
  * [17] Desai-Chowdhry, P., Brummer, A. B., Savage, V. M. How axon and dendrite branching are guided by time, energy, and spatial constraints. Sci Rep. 12, 20810 (2022)
  * [18] Liu, H., Zhang, W., Kennard, S., Caldwell, R. B., Lilly, B. Notch3 is critical for proper angiogenesis and mural cell investment. Circ Res. 107, 860–870 (2010)
  * [19] Reimann, M. W. et al.: Cliques of Neurons Bound into Cavities Provide a Missing Link between Structure and Function. Front Comput Neurosci. 11, 48 (2017)
  * [20] Kanari, L. et al.: A Topological Representation of Branching Neuronal Morphologies. Neuroinform. 16, 3–13 (2018)
  * [21] Kanari, L. et al.: Objective Morphological Classification of Neocortical Pyramidal Cells. Cereb Cortex. 29, 1719–1735 (2019)
  * [22] Bendich, P., Marron, J. S., Miller, E., Pieloch, A., Skwerer, S.: Persistent homology analysis of brain artery trees. Ann Appl Stat. 10, 198–218 (2016)
  * [23] Jiang, Y.: Analysing retinal images using (extended) persistent homology. Master thesis, Australian National University (2022)
  * [24] Tanabe, N. et al.: A homological approach to a mathematical definition of pulmonary fibrosis and emphysema on computed tomography. J Appl Physiol. 131, 601–612 (2021)
  * [25] Giansiracusa, N., Giansiracusa, R., Moon, C. Persistent homology machine learning for fingerprint classification. 2019 18th IEEE International Conference on Machine Learning and Applications (ICMLA). 1219–1226 (2019)
  * [26] Thomas, A. et al.: Topological Data Analysis of C. elegans Locomotion and Behavior. Front Artif Intell. 4, 668395 (2021)
  * [27] Kanari, L., Garin, A., Hess, K. From trees to barcodes and back again: theoretical and statistical perspectives. Preprint at https://arxiv.org/abs/2010.11620 (2020)


* [103] J. Luiten, A. Osep, P. Dendorfer, P. Torr, A. Geiger, L. Leal-Taixe, and B. Leibe, “HOTA: A higher order metric for evaluating multi-object tracking,” _International Journal of Computer Vision_ , oct 2020.
  * [104] J. Philion, A. Kar, and S. Fidler, “Learning to evaluate perception models using planner-centric metrics,” in _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE, June 2020.
  * [105] Y. Guo, H. Caesar, O. Beijbom, J. Philion, and S. Fidler, “The efficacy of neural planning metrics: A meta-analysis of pkl on nuscenes,” _arXiv:2010.09350_ , Oct. 2020.
  * [106] J. Florbäck, L. Tornberg, and N. Mohammadiha, “Offline object matching and evaluation process for verification of autonomous driving,” in _IEEE 19th Int. Conf. on Intelligent Transportation Systems (ITSC)_ , Nov. 2016, pp. 107–112.
  * [107] D. Sondell and K. Svensson, “Matching vehicle sensors to reference sensors using machine learning methods,” Master’s thesis, Chalmers University of Technology, 2018.
  * [108] N. Hirsenkorn, T. Hanke, A. Rauch, B. Dehlink, R. Rasshofer, and E. Biebl, “A non-parametric approach for modeling sensor behavior,” in _16th International Radar Symposium (IRS)_ , June 2015, pp. 131–136.
  * [109] T. Hanke, N. Hirsenkorn, B. Dehlink, A. Rauch, R. Rasshofer, and E. Biebl, “Classification of sensor errors for the statistical simulation of environmental perception in automated driving systems,” in _IEEE 19th Int. Conf. on Intelligent Transportation Systems (ITSC)_. IEEE, 2016, pp. 643–648.
  * [110] R. Krajewski, M. Hoss, A. Meister, F. Thomsen, J. Bock, and L. Eckstein, “Using drones as reference sensors for neural-networks-based modeling of automotive perception errors,” in _IEEE Intelligent Vehicles Symposium (IV)_ , 2020.
  * [111] E. L. Zec, N. Mohammadiha, and A. Schliep, “Statistical sensor modelling for autonomous driving using autoregressive input-output HMMs,” in _21st Int. Conf. on Intelligent Transportation Systems (ITSC)_. IEEE, Nov. 2018.
  * [112] M. F. Holder, C. Linnhoff, P. Rosenberger, C. Popp, and H. Winner, “Modeling and simulation of radar sensor artifacts for virtual testing of autonomous driving,” in _9\. Tagung Automatisiertes Fahren_ , 2019.
  * [113] A. Schaermann, A. Rauch, N. Hirsenkorn, T. Hanke, R. Rasshofer, and E. Biebl, “Validation of vehicle environment sensor models,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2017, pp. 405–411.
  * [114] P. Rosenberger, J. T. Wendler, M. F. Holder, C. Linnhoff, M. Berghöfer, H. Winner, and M. Maurer, “Towards a generally accepted validation methodology for sensor models - challenges, metrics, and first results,” _Proc. of Graz Symposium Virtual Vehicle (GSVF)_ , 2019.
  * [115] M. F. Holder, J. R. Thielmann, P. Rosenberger, C. Linnhoff, and H. Winner, “How to evaluate synthetic radar data? Lessons learned from finding driveable space in virtual environments,” in _13\. Uni-DAS e.V. Workshop Fahrerassistenz und automatisiertes Fahren_ , 2020.
  * [116] R. Philipp, F. Schuldt, and F. Howar, “Functional decomposition of automated driving systems for the classification and evaluation of perceptual threats,” in _13\. Uni-DAS e.V. Workshop Fahrerassistenz und automatisiertes Fahren_ , 2020.
  * [117] A. Poddey, T. Brade, J. E. Stellet, and W. Branz, “On the validation of complex systems operating in open contexts,” _arXiv:1902.10517_ , 2019.
  * [118] R. Gansch and A. Adee, “System theoretic view on uncertainties,” in _2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, Mar. 2020.
  * [119] B. C. Hu, R. Salay, K. Czarnecki, M. Rahimi, G. Selim, and M. Chechik, “Towards requirements specification for machine-learned perception based on human performance,” in _IEEE 7th International Workshop on Artificial Intelligence for Requirements Engineering (AIRE)_. IEEE, Sept. 2020.
  * [120] A. Dokhanchi, H. B. Amor, J. V. Deshmukh, and G. Fainekos, “Evaluating perception systems for autonomous vehicles using quality temporal logic,” in _Runtime Verification_ , C. Colombo and M. Leucker, Eds. Cham: Springer International Publishing, 2018, pp. 409–416.
  * [121] A. Balakrishnan, A. G. Puranic, X. Qin, A. Dokhanchi, J. V. Deshmukh, H. B. Amor, and G. Fainekos, “Specifying and evaluating quality metrics for vision-based perception systems,” in _2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, Mar. 2019.
  * [122] V. Schönemann, H. Winner, G. Verhaeg, F. Tronci, and G. A. G. Padilla, “Fault tree-based derivation of safety requirements for automated driving on the example of cooperative valet parking,” 2019.
  * [123] C. Pek, S. Manzinger, M. Koschi, and M. Althoff, “Using online verification to prevent autonomous vehicles from causing accidents,” _Nature Machine Intelligence_ , vol. 2, no. 9, pp. 518–528, Sept. 2020.
  * [124] M. P. Naeini, G. F. Cooper, and M. Hauskrecht, “Obtaining well calibrated probabilities using bayesian binning,” in _Proc. of the AAAI Conf. on Artificial Intelligence_ , vol. 2015. NIH Public Access, 2015, pp. 2901–2907.
  * [125] V. Kuleshov, N. Fenner, and S. Ermon, “Accurate uncertainties for deep learning using calibrated regression,” _arXiv:1807.00263_ , 2018.
  * [126] F. K. Gustafsson, M. Danelljan, and T. B. Schon, “Evaluating scalable bayesian deep learning methods for robust computer vision,” in _Proc. of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2020.
  * [127] P. Junietz, F. Bonakdar, B. Klamann, and H. Winner, “Criticality metric for the safety validation of automated driving using model predictive trajectory optimization,” in _21st Int. Conf. on Intelligent Transportation Systems (ITSC)_. IEEE, Nov. 2018.
  * [128] A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr, “Basic concepts and taxonomy of dependable and secure computing,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 1, no. 1, pp. 11–33, Jan. 2004.
  * [129] E. Rocklage, H. Kraft, A. Karatas, and J. Seewig, “Automated scenario generation for regression testing of autonomous vehicles,” in _IEEE 20th Int. Conf. on Intelligent Transportation Systems (ITSC)_. IEEE, Oct. 2017.
  * [130] T. Menzel, G. Bagschik, and M. Maurer, “Scenarios for development, test and validation of automated vehicles,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, June 2018.
  * [131] C. Neurohr, L. Westhofen, M. Butz, M. Bollmann, U. Eberle, and R. Galbas, “Criticality analysis for the verification and validation of automated vehicles,” _IEEE Access_ , vol. 9, pp. 18 016–18 041, 2021.
  * [132] S. Khastgir, _Operational Design Domain (ODD) taxonomy for an automated driving system (ADS) – Specification_ , The British Standards Institution Std. PAS 1883:2020, 2020.
  * [133] ASAM e. V., “ASAM OpenODD,” 2020, accessed on 09/12/2020. [Online]. Available: https://www.asam.net/project-detail/asam-openodd/
  * [134] ——, “ASAM OpenXOntology,” 2020, accessed on 09/12/2020. [Online]. Available: https://www.asam.net/project-detail/asam-openxontology/
  * [135] F. Schuldt, “Ein Beitrag für den methodischen Test von automatisierten Fahrfunktionen mit Hilfe von virtuellen Umgebungen,” Ph.D. dissertation, TU Braunschweig, Apr. 2017. [Online]. Available: https://publikationsserver.tu-braunschweig.de/receive/dbbs˙mods˙00064747
  * [136] J. Bock, R. Krajewski, L. Eckstein, J. Klimke, J. Sauerbier, and A. Zlocki, “Data basis for scenario-based validation of had on highways,” in _27th Aachen Colloquium Automobile and Engine Technology_ , 2018.
  * [137] M. Scholtes, L. Westhofen, L. R. Turner, K. Lotto, M. Schuldes, H. Weber, N. Wagener, C. Neurohr, M. Bollmann, F. Körtke, J. Hiller, M. Hoss, J. Bock, and L. Eckstein, “6-layer model for a structured description and categorization of urban traffic and environment,” _arXiv:2012.06319_ , 2020\.
  * [138] C. van Driesten and T. Schaller, “Overall approach to standardize AD sensor interfaces: Simulation and real vehicle,” in _Fahrerassistenzsysteme 2018_ , T. Bertram, Ed. Wiesbaden: Springer Fachmedien Wiesbaden, 2019, pp. 47–55.
  * [139] ASAM e. V., “ASAM OpenSCENARIO,” 2021, accessed on 09/02/2021. [Online]. Available: https://www.asam.net/standards/detail/openscenario/
  * [140] T. Menzel, G. Bagschik, L. Isensee, A. Schomburg, and M. Maurer, “From functional to logical scenarios: Detailing a keyword-based scenario description for execution in a simulation environment,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, June 2019.
  * [141] C. Neurohr, L. Westhofen, T. Henning, T. de Graaff, E. Mohlmann, and E. Bode, “Fundamental considerations around scenario-based testing for automated driving,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, Oct. 2020.
  * [142] A. Pütz, A. Zlocki, J. Bock, and L. Eckstein, “System validation of highly automated vehicles with a database of relevant traffic scenarios,” in _12th ITS European Congr._ , vol. 1, 2017, pp. 19–22.
  * [143] R. Krajewski, T. Moers, D. Nerger, and L. Eckstein, “Data-driven maneuver modeling using generative adversarial networks and variational autoencoders for safety validation of highly automated vehicles,” in _21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, Nov. 2018.
  * [144] Hans-Peter Schoener, “Challenging highway scenarios beyond collision avoidance for autonomous vehicle certification,” _ResearchGate preprint_ , Nov. 2020.
  * [145] I. Kurzidem, A. Saad, and P. Schleiss, “A systematic approach to analyzing perception architectures in autonomous vehicles,” in _Model-Based Safety and Assessment_ , M. Zeller and K. Höfig, Eds. Cham: Springer International Publishing, 2020, pp. 149–162.
  * [146] R. Kuhn, R. Kacker, Y. Lei, and J. Hunter, “Combinatorial software testing,” _Computer_ , vol. 42, no. 7, pp. 94–96, Aug. 2009.
  * [147] C. Gladisch, C. Heinzemann, M. Herrmann, and M. Woehrle, “Leveraging combinatorial testing for safety-critical computer vision datasets,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2020.
  * [148] N. Weber, D. Frerichs, and U. Eberle, “A simulation-based, statistical approach for the derivation of concrete scenarios for the release of highly automated driving functions,” in _AmE - Automotive meets Electronics; 11th GMM-Symposium_ , Dortmund, Germany, 2020, pp. 1 – 6.
  * [149] Robosense, “RS-Reference - efficiently access massive and reliable ground truth data,” Online, Dec. 2020. [Online]. Available: http://www.robosense.ai/en/rslidar/RS-Reference
  * [150] ASAM e. V., “ASAM OpenLABEL,” 2020, accessed on 09/12/2020. [Online]. Available: https://www.asam.net/project-detail/scenario-storage-and-labelling/
  * [151] N. Scheiner, N. Appenrodt, J. Dickmann, and B. Sick, “Automated ground truth estimation of vulnerable road users in automotive radar data using GNSS,” in _IEEE MTT-S Int. Conf. on Microwaves for Intelligent Mobility (ICMIM)_. IEEE, Apr. 2019.
  * [152] V. Ho, K. Rauf, I. Passchier, F. Rijks, and T. Witsenboer, “Accuracy assessment of RTK GNSS based positioning systems for automated driving,” in _15th Workshop on Positioning, Navigation and Communications (WPNC)_. IEEE, Oct. 2018.
  * [153] M. Tahir, S. S. Afzal, M. S. Chughtai, and K. Ali, “On the accuracy of inter-vehicular range measurements using GNSS observables in a cooperative framework,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 2, pp. 682–691, Feb. 2019.
  * [154] J. S. Subirana, J. J. Zornoza, and M. Hernández-Pajares, “GNSS data processing. volume 1: Fundamentals and algorithms,” _ESA Communications ESTEC, PO Box_ , vol. 299, p. 2200, 2013.
  * [155] B. Lampe, T. Woopen, and L. Eckstein, “Collective Driving - Cloud Services for Automated Vehicles in UNICARagil,” in _28th Aachen Colloquium_ , Aachen, Germany, Oct. 2019.
  * [156] S. Knake-Langhorst, K. Gimm, T. Frankiewicz, and F. Köster, “Test site AIM – toolbox and enabler for applied research and development in traffic and mobility,” _Transportation Research Procedia_ , vol. 14, pp. 2197–2206, Dec. 2016.
  * [157] D. Notz, F. Becker, T. Kühbeck, and D. Watzenig, “Extraction and assessment of naturalistic human driving trajectories from infrastructure camera and radar sensors,” _arXiv:2004.01288_ , 2020.
  * [158] A. Krämmer, C. Schöller, D. Gulati, V. Lakshminarasimhan, F. Kurz, D. Rosenbaum, C. Lenz, and A. Knoll, “Providentia - a large-scale sensor system for the assistance of autonomous vehicles and its evaluation,” _arXiv:1906.06789_ , 2019.
  * [159] L. Kloeker, A. Kloeker, F. Thomsen, A. Erraji, and L. Eckstein, “Traffic detection using modular infrastructure sensors as a data basis for highly automated and connected driving,” _29\. Aachen Colloquium - Sustainable Mobility_ , vol. 29, no. 2, pp. 1835–1844, 2020.
  * [160] L. Kloeker, C. Geller, A. Kloeker, and L. Eckstein, “High-precision digital traffic recording with multi-lidar infrastructure sensor setups,” _arXiv:2006.12140_ , 2020.
  * [161] G. Guido, V. Gallelli, D. Rogano, and A. Vitale, “Evaluating the accuracy of vehicle tracking data obtained from unmanned aerial vehicles,” _International Journal of Transportation Science and Technology_ , vol. 5, no. 3, pp. 136 – 151, 2016, Unmanned Aerial Vehicles and Remote Sensing. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S2046043016300272
  * [162] F. Kruber, E. S. Morales, S. Chakraborty, and M. Botsch, “Vehicle position estimation with aerial imagery from unmanned aerial vehicles,” _arXiv:2004.08206_ , 2020.
  * [163] R. Krajewski, J. Bock, and L. Eckstein, “Drones as a tool for the development and safety validation of highly automated driving,” in _Aachener Kolloquium_ , 2019, pp. 1449–1462.
  * [164] F. Kurz, D. Waigand, P. Pekezou-Fouopi, E. Vig, C. Henry, N. Merkle, D. Rosenbaum, V. Gstaiger, S. Azimi, S. Auer, _et al._ , “DLRAD - a first look on the new vision and mapping benchmark dataset for autonomous driving,” _International Archives of the Photogrammetry, Remote Sensing & Spatial Information Sciences_, vol. 42, no. 1, 2018.
  * [165] F. Kurz, D. Rosenbaum, H. Runge, and P. Reinartz, “Validation of advanced driver assistance systems by airborne optical imagery,” _Proc. of Mobil.TUM_ , pp. 1–11, 2015.
  * [166] Z. Wang, D. Feng, Y. Zhou, W. Zhan, L. Rosenbaum, F. Timm, K. Dietmayer, and M. Tomizuka, “Inferring spatial uncertainty in object detection,” _arXiv:2003.03644_ , 2020.
  * [167] S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana, “Efficient formal safety analysis of neural networks,” _arXiv:1809.08098_ , Sept. 2018.
  * [168] S. A. Seshia, D. Sadigh, and S. S. Sastry, “Towards verified artificial intelligence,” _arXiv:1606.08514_ , 2020, v4 (after first version from 2016).
  * [169] M. Barbier, A. Renzaglia, J. Quilbeuf, L. Rummelhard, A. Paigwar, C. Laugier, A. Legay, J. Ibañez-Guzmán, and O. Simonin, “Validation of perception and decision-making systems for autonomous driving via statistical model checking,” in _IEEE Intelligent Vehicles Symposium (IV)_ , 2019, pp. 252–259.
  * [170] K. von Neumann-Cosel, “Virtual test drive: Simulation umfeldbasierter Fahrzeugfunktionen,” Dissertation, Technical University Munich, Munich, 2014\.
  * [171] D. Rao, P. Pathrose, F. Huening, and J. Sid, “An approach for validating safety of perception software in autonomous driving systems,” in _Model-Based Safety and Assessment_ , Y. Papadopoulos, K. Aslansefat, P. Katsaros, and M. Bozzano, Eds. Cham: Springer International Publishing, 2019, pp. 303–316.
  * [172] T. Myklebust, T. Stålhane, and G. Hanssen, “Agile safety case and DevOps for the automotive industry,” in _Proc. of the 30th European Safety and Reliability Conf. and the 15th Probabilistic Safety Assessment and Management Conf._ , Aug. 2020.
  * [173] P. Antonante, D. I. Spivak, and L. Carlone, “Monitoring and diagnosability of perception systems,” _arXiv:2011.07010_ , 2020, v3.
  * [174] T. Woopen, B. Lampe, T. Böddeker, L. Eckstein, A. Kampmann, B. Alrifaee, S. Kowalewski, D. Moormann, T. Stolte, I. Jatzkowski, M. Maurer, M. Möstl, R. Ernst, S. Ackermann, C. Amersbach, S. Leinen, H. Winner, D. Püllen, S. Katzenbeisser, M. Becker, C. Stiller, K. Furmans, K. Bengler, F. Diermeyer, M. Lienkamp, D. Keilhoff, H.-C. Reuss, M. Buchholz, K. Dietmayer, H. Lategahn, N. Siepenkötter, M. Elbs, E. v. Hinüber, M. Dupuis, and C. Hecker, “UNICARagil - Disruptive Modular Architectures for Agile, Automated Vehicle Concepts,” in _27th Aachen Colloquium_ , Aachen, Germany, Oct. 2018.
  * [175] M. Nolte, I. Jatzkowski, S. Ernst, and M. Maurer, “Supporting safe decision making through holistic system-level representations & monitoring – a summary and taxonomy of self-representation concepts for automated vehicles,” _arXiv:2007.13807_ , 2020.
  * [176] B. Lampe, R. van Kempen, T. Woopen, A. Kampmann, B. Alrifaee, and L. Eckstein, “Reducing uncertainty by fusing dynamic occupancy grid maps in a cloud-based collective environment model,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, Oct. 2020.
  * [177] H. Winner, _ADAS, Quo Vadis?_ Cham: Springer International Publishing, 2016, pp. 1557–1584. [Online]. Available: https://doi.org/10.1007/978-3-319-12352-3˙62
  * [178] S. Grubmuller, G. Stettinger, M. A. Sotelo, and D. Watzenig, “Fault-tolerant environmental perception architecture for robust automated driving,” in _IEEE Int. Conf. on Connected Vehicles and Expo (ICCVE)_. IEEE, Nov. 2019.