11institutetext: School of Biomedical Engineering & Imaging Sciences, King's
College London, UK 22institutetext: Guy’s and St Thomas' Hospital, London, UK.
33institutetext: British Heart Foundation Centre, King’s College London.
London, UK 44institutetext: Division of Heart and Lungs, University Medical
Center Utrecht, Netherlands 55institutetext: Royal Brompton Hospital (Guy’s
and St Thomas' NHS Foundation Trust), UK

# AI-enabled Assessment of Cardiac Systolic and Diastolic Function from
Echocardiography

Esther Puyol-Antón Bram Ruijsink Baldeep S. Sidhu Justin Gould Bradley Porter
Mark K. Elliott Vishal Mehta Haotian Gu Christopher A. Rinaldi Martin Cowie
Phil Chowienczyk Reza Razavi 1111 4 411 2 211 2 211 2 211 2 211 2 23311 2
25511 3 311 2 2 Andrew P. King 11

###### Abstract

Left ventricular (LV) function is an important factor in terms of patient
management, outcome, and long-term survival of patients with heart disease.
The most recently published clinical guidelines for heart failure recognise
that over reliance on only one measure of cardiac function (LV ejection
fraction) as a diagnostic and treatment stratification biomarker is
suboptimal. Recent advances in AI-based echocardiography analysis have shown
excellent results on automated estimation of LV volumes and LV ejection
fraction. However, from time-varying 2-D echocardiography acquisition, a
richer description of cardiac function can be obtained by estimating
functional biomarkers from the complete cardiac cycle. In this work we propose
for the first time an AI approach for deriving advanced biomarkers of systolic
and diastolic LV function from 2-D echocardiography based on segmentations of
the full cardiac cycle. These biomarkers will allow clinicians to obtain a
much richer picture of the heart in health and disease. The AI model is based
on the ’nn-Unet’ framework and was trained and tested using four different
databases. Results show excellent agreement between manual and automated
analysis and showcase the potential of the advanced systolic and diastolic
biomarkers for patient stratification. Finally, for a subset of 50 cases, we
perform a correlation analysis between clinical biomarkers derived from
echocardiography and cardiac magnetic resonance and we show a very strong
relationship between the two modalities.

###### Keywords:

Echocardiography Image segmentation Cardiac function Deep learning

##  1 Introduction

There has been much interest in the recent literature in using artificial
intelligence (AI), or more specifically deep learning (DL), to automate the
estimation of cardiac functional biomarkers from 2-D echocardiography images.
For example, [12] evaluated a number of encoder-decoder convolutional neural
network (CNN) architectures for multi-structure segmentation from apical 4-
and 2-chamber echocardiography images. Their models segmented the left
ventricle (LV) endo/epicardium and left atrium (LA) and used these
segmentations to estimate LV ejection fraction using the public CAMUS dataset.
Similarly, [13] proposed a CNN-based method to segment the LV from apical
4-chamber echocardiography cine acquisitions. This paper also described the
publicly available EchoNet Dynamic dataset, which contains ground truth
segmentations of the end diastole (ED) and end systole (ES) frames of the
videos. An alternative approach to estimating functional biomarkers is to
bypass the segmentation step and attempt to estimate the biomarkers directly
from the images. This approach to LV ejection fraction estimation was taken by
[1] and [13]. In [19] a more complete pipeline for echocardiography image
analysis was presented, incorporating view classification, CNN-based
segmentation and estimation of LV/LA volumes, LV mass, LV ejection fraction
and global longitudinal LV strain. The authors also demonstrated a CNN for
disease classification into 3 diagnostic classes. Another clinical pipeline
featuring extensive evaluation on multiple external datasets was presented in
[18]. This work featured estimation of LV and LA volumes at ED and ES as well
as LV ejection fraction, and a range of Doppler echocardiography derived
biomarkers.

However, despite the richness of available data from 2-D echocardiography,
which typically consists of a cine sequence of images covering one or more
complete heart beats, current methods have mostly focused on estimating
functional biomarkers from only 2 frames of this sequence (ED and ES). Even
when the complete sequence was used as input to the model [13], the biomarkers
estimated (e.g. LV ejection fraction) were limited to those based on only
these two frames. Clinically speaking, a much richer description of cardiac
function can be obtained by estimating functional biomarkers from the complete
cardiac cycle, resulting in biomarkers such as ejection and filling rates and
first-phase ejection fraction. These have been shown to be valuable biomarkers
for earlier detection and monitoring of disease [9, 16]. In cardiac magnetic
resonance (CMR) imaging, AI techniques have been proposed for automatically
estimating this richer set of biomarkers [17]. However, estimating them from
echocardiography has historically required a significant amount of expert
interaction, i.e. for contouring the boundaries of the LV myocardium over the
entire cardiac cycle.

In this work we present, for the first time, an AI approach for estimating a
much richer set of cardiac functional biomarkers from 2-D echocardiography.
The biomarkers describe both systolic and diastolic LV function, enabling us
to paint a much richer picture of the heart in health and disease.

##  2 Materials

Four datasets were used for the training and testing of our model for 2-D
echocardiography image analysis, and these are described below:
1\. EchoNet-Dynamic [13]: Apical 4-chamber (4Ch) echocardiography images were
acquired by skilled sonographers using IE33, Sonos, Acuson SC2000, Epiq 5G, or
Epiq 7C ultrasound machines on a cohort of 10,030 patients, split into 8,742
and 1,288 patients respectively, for the training and test sets. The
resolution of the echocardiography images was 600 $\times$ 600 or 768 $\times$
768 pixels depending on the ultrasound machine and the images were downsampled
by cubic interpolation using OpenCV into standardized 112 $\times$ 112 pixel
videos. For all subjects, the LV endocardial border was manually traced in the
ED and ES frames. For further details of the image acquisition protocol, see
[13].
2\. Cardiac Acquisitions for Multi-structure Ultrasound Segmentation (CAMUS)
[12]: The CAMUS dataset consists of clinical exams from 450 patients acquired
using GE Vivid E95 ultrasound scanners (GE Vingmed Ultrasound, Horten Norway)
with a GE M5S probe (GE Healthcare, US). This database was split into 400 and
50 patients respectively, for the training and test sets. Three cardiologists
manually delineated the LV endocardial, epicardial and LA borders in the ED
and ES frames using a semi-automatic tool. For further details of the image
acquisition protocol, see [12].
3\. GSTFT echocardiography database: This database contains 4Ch
echocardiography data acquired from a cohort of 62 heart failure with reduced
ejection fraction (HFrEF) patients imaged at Guy’s and St. Thomas’ Foundation
Trust (GSTFT). The study was approved by the London Research Ethics Committee
(11/LO/1232), all patients provided written informed consent for participation
and the research was conducted according to the Helsinki Declaration
guidelines on human research. This database was split into 50 and 12 subjects
respectively for training and test. The ultrasound machines used were Philips
IE33 and EPIQ 7C (Phillips Medical Systems, Andover, MA, USA) and the GE Vivid
E9 (General Electric Medical Health, Milwaukee, WI, USA), each equipped with a
matrix array transducer. The echocardiography images had an in-plane
resolution between 0.26x0.26mm2 and 0.62×0.62mm2. For all subjects, the
endocardial borders and the ultrasound cone were manually traced in the ED and
ES frames, and for the training database, four other random frames in the
cardiac cycle were manually segmented.
4\. GSTFT paired echocardiography and CMR database: This database contains
paired CMR and 4Ch echocardiography data for a cohort of 50 heart failure
patients acquired at GSTFT. This dataset was used only for testing the
proposed framework. The dataset has similar echocardiography image parameters
and patient characteristics to the GSTFT echocardiography database described
above. CMR imaging was carried out on multiple scanners: Siemens Aera 1.5T,
Siemens Biograph mMR 3T, Philips 1.5T Ingenia and Philips 1.5T and 3T Achieva,
and the cine short axis sequences had a slice thickness between 8 and 10 mm
and an in-plane resolution between 0.92x0.92mm2 and 2.4×2.4mm2.

##  3 Methods

An overview of the proposed framework is shown in Fig. 1. First, the trained
DL-based echocardiography segmentation model is applied to produce left
ventricle blood pool (LVBP) segmentations throughout the cardiac cycle. Next,
the LVBP volume curve is computed and finally the advanced biomarkers of
systolic and diastolic function are computed.

Figure 1: Overview of the proposed framework to segment the left ventricle
blood pool (LVBP) from echocardiography apical 4Ch images and to derive the
systolic and diastolic clinical biomarkers.

Pre-processing: For the GSTFT echocardiography database, an automated pre-
processing workflow was developed to remove identifying information and
eliminate any manual annotations on the images. First, a ‘nnU-Net’
segmentation network [13] was trained using the GSTFT database to detect the
ultrasound cone and remove any image information outside this cone. Second, we
used an inpainting and multiplicative denoising algorithm [3] to remove any
manual annotations present inside the image cone.
Echocardiography apical 4Ch segmentation: We used the ‘nnU-Net’ network [11]
for automatic segmentation of the LVBP from apical 4Ch echocardiography
images. The model was pre-trained using the training sets of the EchoNet-
Dynamic database [13] and the CAMUS database [12] with annotations at ED and
ES frames. To take into account the inter-vendor differences in intensity
distributions, the segmentation model was then fine-tuned using 300 GSTFT
images. At test time, the test sets of the GSTFT, EchoNet-Dynamic and CAMUS
databases were used for inference.

The nnU-Net segmentation network was trained and evaluated using a five-fold
cross validation on the training set. As in [11], the network was trained for
1,000 epochs, where one epoch is defined as an iteration over 250 mini-batches
(with a batch size of 30). Stochastic gradient descent with Nesterov momentum
($\mu$=0.99) and an initial learning rate of 0.01 was used for learning
network weights. The loss function used to train the ‘nnU-Net’ model was the
sum of cross entropy and Dice loss. Data augmentation was performed on the fly
and included techniques such as rotations, scaling, Gaussian noise, Gaussian
blur, brightness, contrast, simulation of low resolution, gamma correction and
mirroring. Please refer to [11] for more details of the network training.
Biomarker estimation: LVBP volume curves were calculated from the obtained
segmentations using the single-plane modified Simpson’s method of discs [7].
From the LVBP volume curves, the following clinical biomarkers were computed:
Standard clinical biomarkers: LVBP end-diastolic volume (EDV), end-systolic
volume (ESV) and ejection fraction (EF).
Advanced systolic/diastolic biomarkers: LVBP first-phase ejection fraction
(EF1), LVBP peak ejection rate (PER), LVBP peak filling rate (PFR).
Below we refer to the LVBP volume curves as $V(t)$, with $t$ representing the
acquisition time in milliseconds. Please refer to Fig. 1 for an illustration
of the following definitions.

The ED and ES frames were determined as the frames with maximum and minimum
LVBP volume respectively, and the EDV and ESV correspond to the volumes at
these frames. Based upon these, EF was computed using the standard formula:
$EF=100\times(EDV-ESV)/EDV$. EF1 can be defined as the percentage change in
LVBP volume from ED to the time of peak aortic valve (AV) flow [9, 10]. In the
absence of continuous wave Doppler AV flow images, the time of peak AV flow is
assumed to be equivalent to the time of the minimum first derivative of LVBP
volume in systole [9, 10], i.e.

$\displaystyle EF1=$ $\displaystyle 100\times(EDV-V1)/EDV,$ (1)
$\displaystyle\mbox{where~{}}V1=$ $\displaystyle V(t_{V1})$
$\displaystyle\mbox{~{}and~{}}t_{V1}=$
$\displaystyle\operatorname*{arg\,\min}_{t}dV/dt,t\in[t_{ED},\ldots t_{ES}]$

PER measures the slope of the ejection phase of the cardiac cycle. PER can be
computed as follows [2]:

$PER=\Delta_{t}\times\min(dV/dt),t\in[t_{ED},...t_{ES}]$ (2)

where $\Delta_{t}$ represents the time in milliseconds between consecutive
echocardiography frames.

PFR measures the slope of the rapid inflow phase of the cardiac cycle. PFR can
be computed as follows [2]:

$PFR=\Delta_{t}\times\max(dV/dt),t\in[t_{ES},\ldots t_{ED}]$ (3)

Evaluation: For quantitative assessment of the image segmentation model, we
used the Dice similarity coefficient (DSC), which quantifies the overlap
between an automated segmentation and a ground truth segmentation. We
evaluated the accuracy of the derived clinical biomarkers by computing the
absolute differences between automated and manual measurements, and by Bland-
Altman analysis and Pearson’s correlation analysis. To verify the significance
of the biases, paired t-tests versus zero values were applied.

##  4 Experiments

The proposed framework automatically generates segmentations of the LVBP over
the full cardiac cycle and estimates the standard and advanced
systolic/diastolic clinical biomarkers. Three sets of experiments were
performed to evaluate the framework’s performance. The first set of
experiments aimed to validate the segmentation model in terms of overlap
performance and clinical biomarker estimation, the second set of experiments
aimed to evaluate the utility of the biomarkers for patient stratification,
while the third set of experiments aimed to compare the biomarkers derived
from CMR and echocardiography data. Our implementation is publicly available
at https://github.com/estherpuyol/ASMUS_2022.git.

Experiment 1 - Comparative evaluation of the automated segmentation network:
The DSC between automated and manual segmentations (only ED and ES frames, for
which ground truths were available) for the test sets of all four databases
(databases 1-4 in Section 2) are summarised in the first block of Table 1.
These results are in line with previous published methods [13, 12]. The second
block of Table 1 shows the difference in standard clinical biomarker values
between automated segmentation and manual segmentation. Figure 2 shows the
Bland-Altman plots for agreement between the pipeline and manual analysis, and
Figure 3 shows a visual comparison between the automated and manual
segmentations for a set of test cases with high and low DSC. Note that this
experiment only focuses on the standard clinical biomarkers and not the
advanced systolic/diastolic biomarkers because of the lack of ground truth
segmentations at cardiac phases other than ED and ES.

Table 1: Comparative evaluation of the automated segmentation network. The
first block shows the Dice similarity coefficient (DSC) between automated
segmentation and manual segmentation for the four test sets, and the second
block shows the absolute differences for the standard clinical biomarkers for
the same test sets. All metrics are expressed as mean (STD).

DSC - Dice coefficient
---
Database |  ED |  ES
1\. EchoNet-Dynamic |  0.935 (0.03) |  0.926 (0.03)
2\. CAMUS |  0.931 (0.07) |  0.922 (0.06)
3\. GSTFT |  0.928 (0.03) |  0.919 (0.04)
4\. GSTFT paired |  0.920 (0.04) |  0.916 (0.04)

Absolute difference between auto and manual
---
Database |  EDV (mL) |  ESV (mL) |  EF (%)
1\. EchoNet-Dynamic |  8.9 (8.8) |  4.7 (4.8) |  1.4 (1.3)
2\. CAMUS |  9.3 (7.8) |  4.9 (4.5) |  1.5 (1.4)
3\. GSTFT |  10.2 (9.6) |  5.6 (4.5) |  1.9 (1.8)
4\. GSTFT paired |  10.8 (7.4) |  6.4 (4.8) |  1.8 (1.2)

Figure 2: Bland-Altman plots for the standard clinical biomarkers: Left
ventricular end-diastolic volume (EDV) and left ventricular end-systolic
volume (ESV); the red dotted lines show the limits of agreement. The p values
represent the difference in mean bias from zero using a paired t-test.  Figure
3: Qualitative visual assessment of automated segmentation. Illustration of
the segmentation results for each database for cases with high (top row) and
low (bottom row) DSC.

Experiment 2 - Analysis of biomarkers for patient stratification: In this
experiment we investigated the distribution of the clinical biomarkers for the
four different databases (databases 1-4 in Section 2). Table 2 shows the mean
and standard deviation (STD) for all the derived biomarkers, both standard and
advanced, and Figure 4 shows boxplots for only the advanced systolic/diastolic
biomarkers. The results show the ability of the proposed framework to robustly
derive advanced biomarkers of cardiac function for different databases with
significantly different populations. For example, the CAMUS and EchoNet-
Dynamic databases have mixed populations, with mainly healthy cases and cases
with mild HFrEF, while the GSTFT databases are composed mainly of patients
with severe HFrEF. Some differences between these groups can be observed in
the standard biomarkers, for example ejection fraction is lower in the GSTFT
group compared to the other groups. However, these differences are more marked
in the advanced systolic/diastolic biomarkers.

Table 2: Comparison between the clinical biomarkers on four different test
databases. End-diastolic volume (EDV), end-systolic volume (ESV), left
ventricular ejection fraction (EF), first-phase ejection fraction (EF1), peak
ejection rate (PER) and peak filling rate (PFR). All metrics are expressed as
mean (STD). Clinical biomarkers
---
Database | EDV (mL) | ESV (mL) | EF (%) | EF1 (%) | PER (mL/s) | PFR (mL/s)
1\. EchoNet-Dynamic | 92 (46) | 44 (36) | 55 (12) | 30 (8) | 350 (57) | 226 (117)
2\. CAMUS | 110 (41) | 56 (33) | 51 (13) | 24 (8) | 305 (108) | 270 (106)
3\. GSTFT | 203 (98) | 139 (03) | 30 (10) | 16 (7) | 266 (95) | 197 (95)
4\. GSTFT paired | 207 (55) | 148 (45) | 29 (7) | 16 (6) | 272 (108) | 209 (99)
Figure 4: Comparison of the advanced systolic/diastolic biomarkers for four
test databases. Blue corresponds to EchoNet, green to CAMUS and pink to GSTFT.

Experiment 3 - Comparison between CMR and echocardiography derived biomarkers:
The functional biomarkers derived from echocardiography were compared with
corresponding values derived from CMR using Pearson’s correlation and limits
of agreement (1.96xSD = 95% confidence intervals) determined by Bland-Altman
analysis [4]. A paired Student’s $t$-test was used to test for any
overestimation or underestimation between echocardiography and CMR in the
Bland-Altman analysis. As further validation, we compute the root mean square
error (RMSE) between the CMR and echocardiography biomarkers. Table 3 shows in
the first two rows the biomarkers estimated from the GSTFT paired
echocardiography and CMR database, and the third row the RMSE. The remaining
rows show the results of the correlation analysis. The CMR database was
analysed using a state-of-the-art automated cardiac functional quantification
framework [17].

Table 3: CMR and echocardiography derived biomarkers and correlation analysis.
End-diastolic volume (EDV), end-systolic volume (ESV), left ventricular
ejection fraction (EF), first-phase ejection fraction (EF1), peak ejection
rate (PER) and peak filling rate (PFR). Correlation coefficient (R), root mean
square error. p-value derived from the paired Student $t$-test. All clinical
biomarkers are expressed as mean (STD).  Derived clinical biomarkers
---
Database | EDV (mL) | ESV (mL) | EF (%) | EF1 (%) | PER (mL/s) | PFR (mL/s)
Echocardiography | 207 (55) | 148 (45) | 29 (7) | 18 (6) | 272 (108) | 209 (99)
CMR | 212 (54) | 146 (42) | 31 (8) | 18 (6) | 367 (139) | 280 (127)
RMSE | 29 | 18 | 6 | 4 | 133 | 93
Correlation Analysis between echocardiography and CMR
Parameter | EDV (mL) | ESV (mL) | EF (%) | EF1 (%) | PER (mL/s) | PFR (mL/s)
R | 0.86 | 0.92 | 0.79 | 0.77 | 0.74 | 0.88
p-value | 0.61 | 0.85 | 0.13 | 0.14 | 0.001 | 0.001

Correlation analysis showed a very strong relationship between CMR and
echocardiography for all biomarkers [6]. Bland-Altman analysis demonstrated no
significant difference (p $>$ 0.05 for all biomarkers except PER and PFR) for
the limits of agreement for echocardiography biomarkers in comparison with CMR
biomarkers. For the standard clinical biomarkers, the results are in line with
previous publications [8, 15].

##  5 Discussion

In this paper we have presented the first AI framework for automatically
estimating a range of advanced biomarkers of cardiac function. Specifically,
we estimate first phase ejection fraction (EF1), peak ejection rate (PER) and
peak filling rate (PFR). These biomarkers are different to the standard
functional biomarkers such as EDV, ESV and EF in that they make use of the
dynamic change in ventricular volumes throughout the cardiac cycle rather than
just two frames (ED and ES). As a result they have the potential to provide a
more complete description of cardiac function and this has been shown in
recent clinical studies [9, 16]. However, this also means that it is currently
not feasible to estimate them in clinical practice due to the labour-intensive
nature of the required manual segmentations. Our work has shown for the first
time that these biomarkers can be automatically estimated from
echocardiography images using deep learning.

Our proposed method achieves similar segmentation overlap performance to the
original EchoNet-Dynamic model [13], e.g. mean ED DSC is 0.929 (95% confidence
interval 0.926–0.935) vs 0.927 (95% confidence interval 0.925–0.928) in
EchoNet-Dynamic. For the standard clinical biomarkers, our method’s
performance is in line with results reported in the EchoNet-Dynamic and CAMUS
papers [13, 12], e.g. we achieved an absolute mean error for EDV of 8.9mL
compared to 9.5ml reported in the CAMUS paper, and an absolute mean error for
EF of 1.4% compared to 4.22% in the EchoNet-Dynamic paper.

We believe that this work is clinically important and timely. There is an
increasing acceptance in the clinical community that biomarkers such as EDV,
ESV and EF are not optimal for use in patient stratification in heart failure.
Current clinical guidelines [14] indicate that heart failure patients should
be stratified for treatment mainly using a single biomarker, EF. However, the
most recently published guidelines recognise the limitations of over-reliance
on only one measure of cardiac function. Using this stratification there is a
wide range of response to treatment - the hazard ratio for mortality for
pharmacological treatment for heart failure is 0.44, with a 95% confidence
interval of 0.26-0.66 [5]. This wide confidence interval highlights the need
for improved patient stratification in heart failure and new advanced
biomarkers of function are likely to play a significant role in this. As well
as demonstrating the robustness and accuracy of our framework (Experiments 1
and 3), in this paper we have demonstrated how these advanced biomarkers can
lead to better stratification in heart failure patients (Experiment 2).

This paper represents an important proof-of-concept, but it has its
limitations. reasonable frame rate ($\geq$ 20 frames/second). A lower frame
rate may cause difficulties in estimating the volume derivatives needed to
compute the advanced systolic/diastolic biomarkers. Future work will
investigate strategies for dealing with data with lower frame rates. In
addition, in future work we plan to perform a more thorough validation of our
framework using data with ground truth annotations throughout the cardiac
cycle. This would enable us to compute errors in the biomarker estimates
compared to ground truth values. We also plan to investigate a wider range of
advanced biomarkers from echocardiography data and more thoroughly investigate
their utility in heart failure patient stratification.

## Acknowledgements

This work was supported by the EPSRC (EP/R005516/1 and EP/P001009/1), the
Wellcome EPSRC Centre for Medical Engineering at the School of Biomedical
Engineering and Imaging Sciences, King's College London (WT 203148/Z/16/Z).
The authors acknowledge financial support (support) the National Institute for
Health Research (NIHR) Cardiovascular MedTech Co-operative award to the Guy’s
and St Thomas’ NHS Foundation Trust and the Department of Health National
Institute for Health Research (NIHR) comprehensive Biomedical Research Centre
award to Guy’s & St Thomas’ NHS Foundation Trust in partnership with King’s
College London

## References

  * [1] Asch, F.M., Poilvert, N., et al.: Automated echocardiographic quantification of left ventricular ejection fraction without volume measurements using a machine learning algorithm mimicking a human expert. Circulation: Cardiovascular Imaging 12(9), e009303 (2019)
  * [2] Bacharach, S.L., Green, M.V., Borer, J.S., et al.: Left-ventricular peak ejection rate, filling rate, and ejection fraction–frame rate requirements at rest and exercise: concise communication. Journal of nuclear medicine: official publication, Society of Nuclear Medicine 20(3), 189–193 (1979)
  * [3] Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D.B.: PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Graph. 28(3), 24 (2009)
  * [4] Bland, J.M., Altman, D.: Statistical methods for assessing agreement between two methods of clinical measurement. The lancet 327(8476), 307–310 (1986)
  * [5] Burnett, H., Earley, A., Voors, A.A., et al.: Thirty years of evidence on the efficacy of drug treatments for chronic heart failure with reduced ejection fraction. Circulation: Heart Failure 10(1), e003529 (2017)
  * [6] Doğan, N.Ö.: Bland-altman analysis: A paradigm to understand correlation and agreement. Turkish journal of emergency medicine 18(4), 139–141 (2018)
  * [7] Folland, E., Parisi, A., Moynihan, P., Jones, D.R., et al.: Assessment of left ventricular ejection fraction and volumes by real-time, two-dimensional echocardiography. a comparison of cineangiographic and radionuclide techniques. Circulation 60(4), 760–766 (1979)
  * [8] Greupner, J., Zimmermann, E., Grohmann, A., et al.: Head-to-head comparison of left ventricular function assessment with 64-row computed tomography, biplane left cineventriculography, and both 2-and 3-dimensional transthoracic echocardiography: comparison with magnetic resonance imaging as the reference standard. Journal of the American College of Cardiology 59(21), 1897–1907 (2012)
  * [9] Gu, H., Saeed, S., Boguslavskyi, A., et al.: First-phase ejection fraction is a powerful predictor of adverse events in asymptomatic patients with aortic stenosis and preserved total ejection fraction. JACC: Cardiovascular Imaging 12(1), 52–63 (2019)
  * [10] Gu, H., Sidhu, B.S., Fang, L., et al.: First-phase ejection fraction predicts response to cardiac resynchronization therapy and adverse outcomes. JACC: Cardiovascular Imaging 14(12), 2275–2285 (2021)
  * [11] Isensee, F., Jaeger, P.F., Kohl, S.A., et al.: nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation. Nature methods 18(2), 203–211 (2021)
  * [12] Leclerc, S., Smistad, E., Pedrosa, J., et al.: Deep learning for segmentation using an open large-scale dataset in 2D echocardiography. IEEE transactions on medical imaging 38(9), 2198–2210 (2019)
  * [13] Ouyang, D., He, B., Ghorbani, A., et al.: Video-based AI for beat-to-beat assessment of cardiac function. Nature 580(7802), 252–256 (2020)
  * [14] Ponikowski, P., Voors, A.A., Anker, S.D., Bueno, H., et al.: 2016 ESC Guidelines for the diagnosis and treatment of acute and chronic heart failure: The Task Force for the diagnosis and treatment of acute and chronic heart failure of the European Society of Cardiology (ESC) Developed with the special contribution of the Heart Failure Association (HFA) of the ESC. European Heart Journal 37(27), 2129–2200 (05 2016)
  * [15] Rigolli, M., Anandabaskaran, S., Christiansen, J.P., Whalley, G.A.: Bias associated with left ventricular quantification by multimodality imaging: a systematic review and meta-analysis. Open Heart 3(1), e000388 (2016)
  * [16] Rokey, R., Kuo, L., Zoghbi, W.A., Limacher, M., Quiñones, M.A.: Determination of parameters of left ventricular diastolic filling with pulsed Doppler echocardiography: comparison with cineangiography. Circulation 71(3), 543–550 (1985)
  * [17] Ruijsink, B., Puyol-Antón, E., Oksuz, I., et al.: Fully automated, quality-controlled cardiac analysis from CMR: validation and large-scale application to characterize cardiac function. Cardiovascular Imaging 13(3), 684–695 (2020)
  * [18] Tromp, J., Seekings, P.J., Hung, C.L., Iversen, M.B., et al.: Automated interpretation of systolic and diastolic function on the echocardiogram: a multicohort study. Lancet Digit Health 4(1), e46–e54 (2022)
  * [19] Zhang, J., Gajjala, S., Agrawal, P., et al.: Fully automated echocardiogram interpretation in clinical practice: feasibility and diagnostic accuracy. Circulation 138(16), 1623–1635 (2018)


# Topological and Geometric Reconstruction of Metric Graphs in
${\mathbb{R}}^{n}$

Brittany Terese Fasy  School of Computing, Montana State University
Department of Mathematical Sciences, Montana State University  Rafal
Komendarczyk  Department of Mathematics, Tulane University  Sushovan Majhi
Department of Mathematics, Tulane University  Carola Wenk  Department of
Computer Science, Tulane University

##  1 Introduction

In the last decade, estimation of topological and geometric features of an
unknown underlying space from a finite sample has received an increasing
attention in the field of computational topology and geometry. For example in
[9] the authors provide a reconstruction guarantee for the topology of an
embedded smooth n-manifold from a finite cover by balls of sufficiently small
radius around a dense enough finite sample. Random sampling is also considered
in [9], and estimates for the probability of reconstructing $M$ from a sample
are obtained. These estimates imply that with increasing sample size, the
probability of reconstructing $M$ tends to 1, thus we can recover $M$ almost
surely as the sample size increases to infinity. Also, curve and surface
reconstruction algorithms are discussed in [5]

In practice, not all manifolds are smoothly embedded, nor all spaces of
interest are topological manifolds. In [4], the authors show that the
homologies of a compact set $K$ of $\mathbb{R}^{n}$ can be obtained by
considering only the relevant homological features in the nerve of the
$\varepsilon$ radius balls around a sample that is $\varepsilon$ close to $K$
in the Hausdorff metric. An upper bound for the required $\varepsilon$
estimate is expressed in terms of weak feature size of $K$ (defined below).
The result of [4] works for non-manifolds, but it is limited to spaces that
have a positive weak feature size.

###  1.1 Background and related work

First, we outline a general approach to estimation of topology and geometry of
Euclidean compact sets from the union of balls centered around a finite set of
points densely sampled from the underlying space $K$. Let $S$ be a sample that
satisfies some density constraints, and let $\varepsilon$ be a radius that
depends on $K$. Then our goal lies to estimate the topology and geometry of
$K$ from $S^{\varepsilon}$. Here, $S^{\varepsilon}$ is the union of Euclidean
balls of radius $\varepsilon$ around $S$. Roughly speaking, one can expect to
capture the topological features of $K$ if $\varepsilon$ is chosen
proportional to the size of the features of $K$ and proportional to
$d_{H}(S,K)$, the Hausdorff distance between $S$ an $K$. If $\varepsilon$ is
too small or too large, then $S^{\varepsilon}$ may fail to capture the
topological features of $K$.

This suggests the following generic scheme:

  1. 1.

The underlying space $K$ should be a well-behaved space that would allow us to
choose an appropriate “feature size” $\tau$, that would restrict the radius
$\varepsilon$ not to be too big to capture even the smallest topological
feature of $K$.

  2. 2.

Having $\tau$, for any $\varepsilon<\tau$ one chooses a sample $S$ that
approximates our underlying space $K$ very closely, i.e.,
$d_{H}(S,K)<\varepsilon.$

  3. 3.

One then expects to estimate the topology and geometry of $K$ from
$S^{\varepsilon}$.

In [9] the authors show that for a smooth manifold $M$ embedded in
$\mathbb{R}^{n}$, $\tau_{n}$ can be chosen to be the maximal radius of the
embedded normal disk bundle of $M$. In Theorem 1.1, the authors show that
$\sqrt{\frac{3}{5}}\tau_{n}$ can be chosen to be a threshold for $\varepsilon$
to compute the homologies of $M$ from the union of balls around an
$\frac{\varepsilon}{2}$-dense sample $S$.

######  Theorem 1.1 (Deformation Retraction [9]).

Let $M$ be a manifold with injectivity radius $\tau_{n}$. Let $\overline{x}$
be any finite collection of points $x_{1},...,x_{n}\in\mathbb{R}^{N}$ such
that it is $\frac{\varepsilon}{2}$ dense in $M$, where
$\varepsilon<\sqrt{\frac{3}{5}}\tau_{n}$. Then, the union
$U=\cup_{i}B(x_{i},\varepsilon)$ deformation retracts onto $M$. Consequently,
the homology of $U$ equals homology of $M$.

We also mention the reconstruction results of [4] for compact sets $K$ in
$\mathbb{R}^{n}$. If $K$ admits a positive weak feature size (wfs) and
$\varepsilon<\frac{1}{4}\texttt{wfs}$, then a densely sampled set of points
can give us the right topology of $K$.

######  Theorem 1.2.

Let $K$ and $S$ be two compact sets of $\mathbb{R}^{n}$ such that
$0<\varepsilon<\frac{1}{4}\texttt{wfs}(K)$ and $d_{H}(K,S)<\varepsilon$. Then,

$H_{k}(K)\backsimeq Image(i),$

where $H_{k}$ denotes the $k$-th homology group and $i$ is the inclusion of
$S^{\varepsilon}$ in $S^{3\varepsilon}$.

###  1.2 Summary of results

The current paper is motivated by the following questions:

  1. 1.

Theorem 1.1 provides a reconstruction result when
$\varepsilon<\sqrt{\frac{3}{5}}\tau_{n}$. Does the result fail to hold when
$\sqrt{\frac{3}{5}}\tau_{n}<\varepsilon<\tau_{n}$?

  2. 2.

The result of [4] works for a compact space $K$ having a positive wfs. One can
easily find very simple 1-dimensional complexes, e.g. trees, that have zero
wfs. These spaces are often of interest in applications, for instance in road
network reconstruction problems [2].

  3. 3.

The feature size $\tau$ is defined for smooth manifolds. How can we define an
appropriate feature size when the space is not a smooth manifold, e.g., an
embedded simplicial complex.

We answer the first question positively in Theorem 2.1, addressing the case of
smooth curves in $\mathbb{R}^{2}$. Theorem 2.1 shows that
$\varepsilon<\tau_{n}$ is sufficient for the reconstruction. The second and
third questions are considered in the setting where $K$ is a metric graph
(later denoted by $G$) embedded in ${\mathbb{R}}^{n}$. In this setting, unlike
in the manifold case, it is generally not possible to choose a threshold
$\tau$ for the sampling parameter $\varepsilon$ so that $S^{\varepsilon}$ has
the same homotopy type as $K$, even if $S$ is an arbitrary dense sample, since
$S^{\varepsilon}$ will contain unnecessary “small” features (noise) that are
not present in $K$. In order to address this issue, we propose a different
notion of a feature size that we call geodesic feature size (denoted by
$\tau_{G}$). This new definition of feature size allows us to threshold the
sampling parameter $\varepsilon$, in the case of a metric graph $G$, and leads
to the reconstruction algorithm shown in Algorithm 1. In particular, we obtain
a simplicial complex $K^{\varepsilon}$ in $\mathbb{R}^{2}$, which is
$\varepsilon$-close to $G$ (in the sense of the Hausdorff distance) and which
deformation retracts onto $G$.

##  2 Reconstruction Results

###  2.1 Smooth Curve Reconstruction

######  Theorem 2.1 (Smooth Curve Reconstruction).

Let $M$ be a smooth curve in $\mathbb{R}^{2}$ without boundary and let $\tau$
be the injectivity radius. Let $\varepsilon\in(0,\tau]$ and let $S$ be a
finite subset of $M$ such that $M\subseteq S^{\varepsilon}$. Then, the medial
axis of $S^{\varepsilon}$ is homeomorphic to $M$.

From the result of [8], which shows that any bounded open subset of Euclidean
space is homotopy equivalent to its medial axis, we conclude that
$S^{\varepsilon}$ and $M$ are homotopy equivalent.

######  Remarks 2.2.

A deformation retraction constructed in [9], collapses $S^{\varepsilon}$ along
the normal lines $M$. The collapse is not well defined if the intersection of
$S^{\varepsilon}$ with a normal line has more than one connected component.
The condition $\varepsilon^{2}<\frac{3}{5}\tau_{n}^{2}$ (for a sample that is
$\frac{\varepsilon}{2}$-dense in $M$) guarantees that such intersections do
not happen and the deformation retraction is well-defined.

###### Sketch of proof..

Let $S$ satisfy the assumptions of Theorem 2.1. For brevity of exposition, we
assume that $M$ has one path-connected component. Then, we know that $M$ is,
in fact, the image of an injective, smooth map
$\gamma\colon[0,1]\to{\mathbb{R}}^{2}$ with $\gamma(0)=\gamma(1)$. Let us
denote the $\varepsilon$-tubular neighborhood of $M$ by $M^{\varepsilon}$.

Without loss of generality, assume that the sample points of
$S=\\{x_{1},x_{2},...,x_{k}\\}$ are enumerated with increasing preimages:
$\gamma^{-1}(x_{i})<\gamma^{-1}(x_{i+1})$ for all $i\in\\{1,2,\ldots k-1\\}$.
Then, these samples introduce a partition $\\{M_{i}\\}_{i=1}^{k}$ of the
manifold, where $M_{i}=\gamma([t_{i},t_{i+1}])$ and
$M_{k}=\gamma([t_{k},1])\cup\gamma([0,t_{1}])$. Let $\widehat{M}$ be the
piecewise linear curve obtained by connecting $x_{i}$’s in the respective
order and let $\widehat{M_{i}}=\overline{x_{i}x_{i+1}}$.

Since $\varepsilon<\tau$, each ball $B_{\varepsilon}(x_{i})$ intersects the
tubular neighborhood $M^{\varepsilon}$ at exactly at two points, say at
$u_{i}$ and $l_{i}$; see Figure 1. Let $N_{i}$ denote the normal
$\overline{u_{i}l_{i}}$ passing through $x_{i}$. Notice that these line
segments $\overline{u_{i}l_{i}}$ do not intersect. In fact, these normal lines
partition the tubular neighborhood into $k$ regions, where the $i$-th region,
denoted $M_{i}^{\varepsilon}$, is the one containing $M_{i}$.

Figure 1: The medial axis and region $M_{i}^{\varepsilon}$ defined by
consecutive sample points $x_{i}$ and $x_{i+1}$. The blue smooth curve is a
portion of our manifold $M$. The gray region is the tubular neighborhood
$M^{\varepsilon}$.

We will show that $\widehat{M}$ is homeomorphic to $M$. Observe that
$\widehat{M}$ is also the medial axis of $S^{\varepsilon}$. Restricting our
attention to $M_{i}^{\varepsilon}$, we define a homeomorphism between
$\widehat{M_{i}}$ and $M_{i}$, and extend it globally so that they retain
continuity since they agree on each $N_{i}$ by the pasting lemma.

We define a homeomorphism $\phi_{i}:\widehat{M_{i}}\to M_{i}$ for each
$M_{i}^{\varepsilon}$ in the following way. If we draw a perpendicular $L$ at
any point $z$ on $\widehat{M_{i}}$, we show that $L$ intersects $M_{i}$ at
exactly one point $y$ and define $\phi_{i}(x):=y$. As a consequence, $M_{i}$
is a continuous graph on $\widehat{M_{i}}$, hence a homeomorphism.

On the contrary, let’s assume that there exists a point $x$ on $M_{i}$ whose
normal $L$ intersects $M_{i}$ at at least two points $z_{1}$ and $z_{2}$. We
arrive at a contradiction by showing that there is a point $z$ on $M_{i}$ such
that the normal $T_{z}$ at $z$ is parallel to $\widehat{M_{i}}$.

Without loss of generality, we assume that $L$ cuts the manifold at both
$z_{1}$ and $z_{2}$. Note that $z_{1}$ and $z_{2}$ are points on the manifold
and tangents $T_{z_{1}}$ and $T_{z_{2}}$ are not parallel to $L$. By
continuity of the tangents of $M$, we conclude that there exists a point $z$
on $M_{i}$ such that $T_{z}$ is parallel to $L$. Consequently, the normal
$N_{z}$ at $z$ is parallel to $\widehat{M_{i}}$.

Figure 2: Contradiction in the proof of Theorem 2.1.

Now, we arrive at a contradiction in either of the following cases; see Figure
2.1 for an illustration.

Case 1: If $||x_{i+1}-x_{i}||\leq\varepsilon$, then the $\varepsilon$-radius
normal, $N_{z}\cap M^{\varepsilon}$, at $z$ intersects either $N_{i}$ or
$N_{i+1}$. This contradicts the fact that $\tau$ is the injectivity radius.

Case 2: If $||x_{i+1}-x_{i}||>\varepsilon$, then the $\varepsilon$-radius
normal, $N_{z}\cap M^{\varepsilon}$, at $z$ lies completely in the interior of
$M_{i}^{\varepsilon}$, which is a contradiction because the boundary of each
$\varepsilon$-radius normal lies on the boundary of the tubular neighborhood
$M^{\varepsilon}$ of the manifold.

Therefore, the function $\phi_{i}$ is a well-defined, invertible, continuous
map on a compact domain, hence a homeomorphism.

Since the $\phi_{i}$’s agree on the boundary of each $\widehat{M_{i}}$, we
glue them to obtain a global homeomorphism $\phi:\widehat{M}\to M$. This
completes the proof. ∎

###  2.2 Metric Graph Reconstruction

A weighted graph $G=(V,E)$ is said to be a _metric graph_ if the edge-weights
are all positive. Then, we can interpret the weights as lengths, and thus each
point $e\in E$ has a well-defined distance to the endpoints of $E$. We define
the length of a given continuous path in $G$ to be the total length of all
edges and partial edges in the path. Then, the distance function $d_{G}\colon
G\times G\to{\mathbb{R}}$ is defined to be the length of the shortest path
connecting two points; in words, $d_{G}$ is the geodesic distance in $G$.
Metric graphs were first introduced in [7], and have recently been studied in
[1, 6].

Below we list our assumptions about the underlying graph $G$ that we aim to
reconstruct.

######  Assumption 2.3.

$G$ is an embedded metric graph with straight line edges.
$V=\\{v_{1},v_{2},...,v_{n}\\}$ is the vertex set and
$E=\\{e_{1},e_{2},...,e_{m}\\}$ is the edge set.

######  Assumption 2.4.

The length of the smallest edge of $G$ is $l$.

######  Definition 2.5 (Nerve of a Cover).

Suppose $\mathcal{U}=\\{U_{\alpha}\\}_{\alpha\in\Lambda}$ is a cover of a
topological space $X$. We take $\Lambda$ to be the vertex set and form an
abstract simplicial complex $\mathcal{K}$ in the following way: if a $k$-way
intersection $U_{\alpha_{1}}\cap U_{\alpha_{2}}\cap...\cap U_{\alpha_{k}}$ is
non-empty, then $\\{\alpha_{1},\alpha_{2},...,\alpha_{k}\\}\in\mathcal{K}$.

$\mathcal{K}$ is then called the _nerve_ of the cover $\mathcal{U}$ and is
denoted by $\mathcal{N}(\mathcal{U})$.

######  Lemma 2.6 (Nerve Lemma [3]).

Suppose
$\mathcal{U}=\\{U_{\alpha}\\}_{\alpha\in\Lambda}$ is a “good” covering of $X$,
i.e., every $U_{\alpha}\in\mathcal{U}$ is contractible along with all non-
empty finite intersections of elements of $\mathcal{U}$. For such a good
covering $X$ has the same homotopy type as $\mathcal{N}(\mathcal{U})$.

We now propose our feature size that we call
Geodesic Feature Size (gfs).

######  Definition 2.7 (Geodesic Feature Size).

Let $G$ be an embedded metric graph. We define the Geodesic Feature Size (gfs)
$\boldsymbol{\tau_{G}}$ of $G$ to be the supremum of all $r>0$ having the
following property: for any $x$, $y\in G$, if $||x-y||<2r$ then
$d_{G}(x,y)<l$, where $l$ is the length of the smallest edge of $G$.

To motivate the above definition of gfs, we take a finite sample
$S=\\{x_{1},x_{2},\ldots,x_{k}\\}$ from $G$. Let
$\\{{\mathbb{B}}_{\varepsilon}(x)\\}_{x\in S}$ be a cover of $G$ and let
$\mathcal{K}_{1}=\mathcal{N}(S,\varepsilon)$ be its nerve, where
${\mathbb{B}}_{\varepsilon}(x)$ is the Euclidean $\varepsilon$-ball centered
at $x$. An edge $e$, between two vertices $x_{i}$ and $x_{j}$ in
$\mathcal{K}_{1}$, is called _transverse_ if $x_{i}$ and $x_{j}$ belong to two
different edges of $G$. If $\varepsilon<\tau_{G}$ and $e$ is transverse, then
the geodesic distance $d_{G}(x_{i},x_{j})<l$ and the geodesic on $G$ is
unique. This implies that there is at most one vertex $v$ of $G$ lying on this
geodesic. We call this geodesic the geodesic shadow of the edge $e$. The
threshold $\tau_{G}$ for $\varepsilon$ forces any transverse edge $e$ to be
within ${\mathbb{B}}_{\xi\epsilon}(v)$ around that vertex $v$, where
$\xi=\max\frac{1}{\sin{(\alpha/2)}}$, the maximum is taken over all acute
angles $\alpha$ between any pair of edges of $G$. The idea behind this
definition of gfs comes from our goal to estimate the diameter of non-trivial
1-cycles of $\mathcal{K}_{1}$ that are not present in $G$. These _noisy_ one-
cycles in $\mathcal{K}_{1}$ are formed by some of the transverse edges. We
also mention here without a proof that gfs is positive for the type of metric
graphs we are considering. In fact, we can show that $0<\tau_{G}\leq l/2$,
where $l$ is the length of the shortest edge in $G$.

We now state our main reconstruction theorem for embedded metric graphs. This
theorem proves the correctness of Algorithm 1 for computing the 1-dimensional
Betti number of $G$.

######  Theorem 2.8.

Let $\varepsilon<\frac{1}{\xi}\texttt{gfs}(G)$ and $S$ be a finite sample from
$G$ such that $S^{\varepsilon}\supseteq G$. Then,
$H_{1}(G)=i_{*}(H_{1}(S^{\varepsilon}))$, where $i$ is the inclusion map from
$S^{\varepsilon}\to S^{\xi\varepsilon}$, $H_{1}(\cdot)$ denotes the first
homology group in ${\mathbb{Z}}$ coefficients and $\xi$ is as defined above.

###### Sketch of proof..

Let $\mathcal{K}_{1}=\mathcal{N}(S,\varepsilon)$ and
$\mathcal{K}_{2}=\mathcal{N}(S,\xi\varepsilon)$. As $\xi>1$, it follows that
$\varepsilon<\texttt{gfs}(G)$. An application of the nerve lemma implies that
there is an injective homomorphism $\phi$ from $H_{1}(G)$ to
$H_{1}(\mathcal{K}_{1})$. In other words, $\mathcal{K}_{1}$ contains all the
non-trivial 1-cycles of $G$. Similarly, we can show that there also exists an
injective homomorphism from $H_{1}(G)$ to $H_{1}(\mathcal{K}_{2})$. We then
consider the induced homomorphism $i_{*}:H_{1}(K_{1})\to H_{1}(K_{2})$, where
$i:\mathcal{K}_{1}\to\mathcal{K}_{2}$. Finally, we show that
$H_{1}(\mathcal{K}_{1})=\phi(H_{1}(G))\oplus Ker~{}i_{*}$. Therefore,
$H_{1}(G)\simeq i_{*}(H_{1}(S^{\varepsilon}))$. ∎

We believe that it should be possible to find a simplicial complex with the
same homotopy type as $G$. We formulate this stronger result as follows:

######  Conjecture 2.9.

Let $\varepsilon<\frac{1}{2(2+\xi)}\texttt{gfs}(G)$ and $S$ be a finite sample
from $G$ such that each edge of $G$ can be covered by the union of
$\varepsilon$-balls centered at the sample points on the same edge. Then the
Vietoris-Rips complex $VR(S,d_{\varepsilon},2(1+\xi)\varepsilon)$, computed on
$S$ w.r.t. the geodesic metric on the 1-skeleton of $\mathcal{K}_{1}$ at a
scale of $2(1+\xi)$, has the same homotopy type as $G$.

######  Remarks 2.10.

The idea of collapsing the “small” 1-cycles in Algorithm 1 motivates us to add
a full simplex around each vertex whenever a subset of $S$ has a diameter
smaller than the estimated scale. That is precisely what the Vietoris-Rips
complex does on a finite metric space.

###  2.3 Discussion

To further extend our result, we also consider a probabilistic reconstruction,
as considered by the authors of [9]. Given a $(1-\delta)$ chance of correct
reconstruction, one can find the smallest sample size to guarantee the given
chance of recovery. Also, we can extend our definition of gfs to metric graphs
and obtain similar reconstruction results. Lastly, we also consider the
reconstruction question when samples that are drawn not exactly from our
underlying space, but from a close vicinity of it.

Data: The finite sample $S$ from the unknown metric graph $G$ and
$\varepsilon>0$

Result: one dimensional Betti number of $G$

1 Compute $\mathcal{K}_{1}$ Compute $\mathcal{K}_{2}$

2for  _non-trivial 1-cycle $\eta$ in $\mathcal{K}_{1}$_ do

3 if  _$\eta$ is trivial in $\mathcal{K}_{2}$_ then

4 Collapse $\eta$ in $\mathcal{K}_{1}$

5 end if

6

7 end for

8Compute remaining non-trivial cycles in $\mathcal{K}_{1}$;

Algorithm 1 Metric graph reconstruction from a finite sample.

##  3 Acknowledgments

The first, third, and fourth authors would like to acknowledge the generous
support of the National Science Foundation under grants CCF-1618469 and
CCF-1618605.

## References

  * [1] Aanjaneya, M., Chazal, F., Chen, D., Glisse, M., Guibas, L., and Morozov, D. Metric graph reconstruction from noisy data.  International Journal of Computational Geometry & Applications 22, 04 (2012), 305–325.
  * [2] Ahmed, M., Karagiorgou, S., Pfoser, D., and Wenk, C. Map Construction Algorithms.  Springer, 2015.
  * [3] Alexandroff, P. Über den allgemeinen dimensionsbegriff und seine beziehungen zur elementaren geometrischen anschauung.  Mathematische Annalen 98, 1 (March 1928), 617–635.
  * [4] Chazal, F., and Lieutier, A. Stability and computation of topological invariants of solids in $\mathbb{R}^{n}$.  Discrete & Computational Geometry 37, 4 (2007), 601–617.
  * [5] Dey, T. K. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics).  Cambridge University Press, New York, NY, USA, 2006.
  * [6] Gasparovic, E., Gommel, M., Purvine, E., Sazdanovic, R., Wang, B., Wang, Y., and Ziegelmeier, L. A complete characterization of the 1-dimensional intrinsic cech persistence diagrams for metric graphs.  Research in Computational Topology.  To appear; arXiv preprint arXiv:1702.07379.
  * [7] Kuchment, P. Quantum graphs: I. some basic structures.  Waves in Random Media 14, 1 (2004), S107–128.
  * [8] Lieutier, A. Any open bounded subset of $\mathbb{R}^{n}$ has the same homotopy type as its medial axis.  Computer-Aided Design 36, 11 (2004), 1029–1046.
  * [9] Niyogi, P., Smale, S., and Weinberger, S. Finding the homology of submanifolds with high confidence from random samples.  Discrete And Computational Geometry 39. 1-3 (2008), 419–441.