# CoDA: Interactive Segmentation and Morphological Analysis of Dendroid
Structures Exemplified on Stony Cold-Water Corals

Kira Schmitt, Jürgen Titschack, and Daniel Baum  0009-0000-0385-0404
0000-0001-9373-9688 0000-0003-1550-7245

###### Abstract

Dendroid stony corals build highly complex colonies that develop from a single
coral polyp sitting in a cup-like skeleton, called corallite, by asexual
reproduction, resulting in a tree-like branching pattern of its skeleton.
Despite their beauty and ecological importance as reef builders in tropical
shallow-water reefs as well as in cold-water coral mounds in the deep ocean,
systematic studies investigating the ontogenetic morphological development of
such coral colonies are largely missing. One reason for this is the sheer
number of corallites – up to several thousands in a single coral colony.
Another limiting factor, especially for the analysis of dendroid cold-water
corals, is the existence of many secondary joints in the ideally tree-like
structure that make a reconstruction of the skeleton tree extremely tedious.

Herein, we present _CoDA_ , the _Co_ ral _D_ endroid structure _A_ nalyzer, a
visual analytics suite that allows for the first time to investigate the
ontogenetic morphological development of complex dendroid coral colonies,
exemplified on three important framework-forming dendroid cold-water corals:
Lophelia pertusa (Linnaeus, 1758), Madrepora oculata (Linnaeus, 1758), and
Goniocorella dumosa (Alcock, 1902). Input to _CoDA_ is an initial instance
segmentation of the coral polyp cavities (calices), from which it estimates
the skeleton tree of the colony and extracts classical morphological
measurements and advanced shape features of the individual corallites. _CoDA_
also works as a proofreading and error correction tool by helping to identify
wrong parts in the skeleton tree and providing tools to quickly correct these
errors. The final skeleton tree enables the derivation of additional
information about the calices/corallite instances that otherwise could not be
obtained, including their ontogenetic generation and branching patterns – the
basis of a fully quantitative statistical analysis of the coral colony
morphology. Part of _CoDA_ is _CoDA.Graph_ , a feature-rich link-and-brush
user interface for visualizing the extracted features and 2D graph layouts of
the skeleton tree, enabling the real-time exploration of complex coral
colonies and their building blocks, the individual corallites and branches.

In the future, we expect _CoDA_ to greatly facilitate the analysis of large
stony corals of different species and morphotypes, as well as other dendroid
structures, enabling new insights into the influence of genetic and
environmental factors on their ontogenetic morphological development.

###### Index Terms:

Image processing, data visualization, biological systems.

Figure 1:  _CoDA_ enables the analysis and visual exploration of the
ontogenetic morphological development of dendroid cold-water corals. _(a)_ The
analysis starts with a computed-tomography (CT) image of the cold-water coral
(CWC). _(b, c)_ The polyp-cavity (calyx) segmentation [39, 3, 44] is the basis
for the subsequent calyx/corallite instance segmentation. _(d)_ Within the
_CoDA_ framework, a skeleton tree, describing the mother-daughter corallite
relationship within a colony, is fitted to the corals. _(e, f)_ The skeleton
tree is visualized as graph layout in _CoDA.Graph_ , our 2D visualization
suite that augments _CoDA_ with abstract, linked views, allowing the user to
explore the colony and to focus on specific subsets of the tree during the
analysis, e.g., on the descendants or ancestors of a calyx/corallite. _(g, h)_
Traditional plots and views, e.g., scatter plot matrices (SPLOMs) and
spreadsheets available in _CoDA.Graph_ , complement _CoDA_ ’s exploration and
analysis capabilities.

##  I Introduction

(a)

(b)

(c)

Figure 2:  _(a)_ The schematic depicts the typical parts of a cold-water coral
colony (CC BY 4.0 Deed [39]). The terms _calyx_ and _calice_ (in the
schematic) can be used interchangeably and refer to the same part. We prefer
_calyx_ in the singular, while the plural is _calices_. _(b)_ The photo shows
the _SaM-ID43148 (III)_ cold-water coral colony specimen. It is particularly
large compared to other datasets and contains several colony fragments. Its
dense structure makes the analysis and visual exploration particularly
challenging without adequate tools. _(c)_ The photo shows the _NIWA-148046
(V)_ cold-water coral colony specimen. Its morphology differs from the other
corals presented in this paper as the cavities resemble more a cylinder than a
cone.

Complex dendroidal structures are widespread in nature and commonly formed by
various organisms comprising plants, e.g., trees, grass, including their
roots, coralline algae (e.g.,[35, 22, 24, 46, 27, 10]), and (marine) animals,
e.g., corals, including the herein investigated cold-water corals (CWC), or
bryozoans ([22, 30, 1]). Often, these organisms are key players in ecosystems,
such as trees in forests or corals in coral reefs, by forming multiple
ecological niches beneficial for other organisms, so that these ecosystems
represent biodiversity hotspots and provide important ecosystem services
(e.g., [42, 2, 13, 21]).

Coral colonies consist of multiple coral polyps that originate from asexual
budding. Each polyp produces a skeleton called corallite with a central
cavity, called calyx, in which it lives (2(a)). Coral colonies exhibit various
shapes (e.g., encrusting, hemispherical, tabular, corymbose and branching;
[14]) but colonial stony (scleactinian) cold-water corals are predominantly
branching (dendroidal; [33]). Some dendroid cold-water corals commonly show
secondary joints, regions in the colony where two different coral branches
have grown together, and skeletal strengthening as well as further associated
secondary joints related to the presence of worms of the genus Eunice [29].
Both represent important features in the analysis of cold-water coral colonies
as they influence significantly the morphology of the colonies, which is the
result of the interaction of the organism with its ambient environment.
However, an in-depth understanding of this interaction is often hindered by
the limited methodologies to characterize three-dimensional morphologies.
Often, morphologies are only qualitatively described (e.g., for CWC: [20, 9,
11]) or characterized by some basic measurements (e.g., for CWC: [37, 36]).

This work presents a new visual analytics suite called _CoDA_ that allows a
detailed three-dimensional quantitative assessment of dendroidal structures. A
major component of _CoDA_ is _CoDA.Graph_ , a browser-based application for
showing 2D plots like scatter plots, SPLOMs, maps and graph layouts.
_CoDA.Graph_ is not only suited for the analysis of CWCs but any kind of
dendroid structures. We tested _CoDA_ on colony fragments of the reef-forming
CWCs Lophelia pertusa, Madrepora oculata and Goniocorella dumosa. An overview
of the analysis workflow using _CoDA_ is shown in Figure 1. Note that in this
work, we visualize all binary and instance segmentations as voxelized data for
two reasons: (1) It gives the reader a better feeling for the resolution of
the data. (2) It is the one used in _CoDA_ as it is more interactive than
using a surface representation that needs recomputation with each change.

###  I-A Related work

Skeleton graphs and center line trees [38, 18] are well established tools in
the image processing community and provide a good first impression of the
growth of a coral colony. However, they are purely based on topological
measures and do not take into account the actual, biological relationship.
They are thus not suited for a proper ontogenetic analysis. The work on _CoDA_
is motivated by the desire to obtain a _directed_ skeleton graph in which the
edges coincide with the mother-daughter relationships between adjacent
corallites and in which each vertex corresponds to a corallite. For similar
reasons, contact graphs [31], as they occur in the analysis of particle and
fibre systems, are not suited for the ontogenetic analysis.

Our 2D analytics platform _CoDA.Graph_ is inspired by _dExplorer_ [12], an
interactive platform for spine analysis. It allows the extraction of many
morphological features and their visualization in a single application.
However, with regard to the analysis of CWC colonies, we are interested in
different features, both for individual corallites as well as morphological
features of the entire coral colony. Most importantly, we are interested in
the visualization and exploration of the relationships within a colony.

The visualization and modification of the graph structures are based on the
work of Dercksen et al. [15], in which they deal with the tracing and
visualization of 3D dendrite and axon morphologies. We apply many of the
presented ideas, especially the manual tools for editing the spatial graphs,
in our analysis pipeline, extend and adjust them to our use case. Dercksen et
al. construct the edges by tracing the dendrites in the image. For coral
colonies, this is not possible, as there is no unique path visible in the
image that connects mother and daughter corallites (2(a)). Additionally, the
edges in the dendrite graph are again undirected whereas the orientation of
the edges carry important information in our application.

###  I-B Data

This paper explores five specimens of, in total, three different species of
cold-water corals with different morphologies. All specimens vary greatly in
size, so that we not only test the developed methods for small samples, but
also for large ones with almost 2000 corallites. We consider the following
specimens:

  1. (I)

sample _A2W_ of the species Lophelia pertusa with elongated corallites and an
open, bushy colony morphology, collected from Leksa reef, Norway
($63.61\degree\,\text{N}$ $9.38\degree\,\text{E}$ and 157m water depth);

  2. (II)

sample _C1W_ of the species Lophelia pertusa with elongated corallites and an
open, bushy colony morphology, collected from Sula reef, Norway
($64.11\degree\,\text{N}$ $8.12\degree\,\text{E}$ in 303m depth);

  3. (III)

sample _SaM-ID43148_ of the species Lophelia pertusa with slender corallites
and a columnar colony morphotype, collected near the Gondola Slide, southeast
of the Gargano Promontory in the Adriatic Sea, (stations 167/168; GeoB11207;
$41.72\degree\,\text{N}$ $17.05\degree\,\text{E}$, approximately in 700m water
depth; [19]), shown in 2(b);

  4. (IV)

sample _GeoB12747-1_ of the species Madrepora oculata with its typical zigzag
corallite arrangement, forming a fragile, predominantly fan-shaped colony
morphology, collected from Meknes mud vulcano, Gulf of Cadiz during Pelagia
cruise 64PE284 [26] ($34.99\degree\,\text{N}$ $7.07\degree\,\text{W}$ in 714m
depth);

  5. (V)

and sample _NIWA-148046_ of the species Goniocorella dumosa with its tube-like
corallites and bushy colony morphology, collected from Chatham Rise, New
Zealand ($43.37\degree\,\text{S}$ $179.45\degree\,\text{E}$ in approximately
400m water depth), shown in 2(c).

The CT scans were performed at Klinikum Bremen-Mitte with the same protocol as
described in Schmitt et al. ([39], specimens (I), (II) and (IV) with the
Toshiba Aquilion 64 device, and specimens (III) and (V) with the Philips
Brilliance iCT Elite 256 device). The qualitative classification scheme of
Sanna et al. [37] was used to determine colony morphotypes. More information
regarding meta data and results are provided in Table I.

###  I-C Contributions

Our contributions are as follows.

  * •

A domain-specific framework for the semi-automatic ontogenetic and
morphological analysis of cold-water coral colonies, potentially suitable for
other dendroidal structures.

  * •

A linked dendrogram and state-of-the-art graph layouts for the coral colonies
that provide an abstract, unobtrusive view of the colonies’ growth patterns;
it also provides multiple selection tools for exploring the ancestry of
individual corals and their ontogenetic development.

  * •

A heuristic for orienting cold-water coral calices/corallites, and other cone-
shaped structures, that approximates their centerlines by parabolas; a further
heuristic that uses the orientation information to estimate the skeleton tree
of coral colonies.

  * •

A proofreading mechanism for the instance segmentation of the
calices/corallites and their adjacency, which avoids occlusions and guides the
user in a coherent way through all instances, even in very large colonies.

  * •

A tool set for jointly correcting over-segmentations, under-segmentations and
wrong adjacencies in the instance segmentation and the attached graph, in a
systematic manner without having to start all over again.

  * •

A simple mechanism for linking and brushing between different applications
using a simple _.csv_ file-based interface, that allows the seamless
integration of _CoDA.Graph_ into other visualization tools.

The remainder of the paper is structured as follows: In section II, we give an
overview of the segmentation workflow, the fitting of the colony skeleton
graph and our tools for jointly refining the calyx instance segmentation and
the skeleton graph. In section III, we present the visual analysis tool
_CoDA.Graph_ , describe its architecture, its features and its integration
into other visualization platforms. In section IV, we apply the segmentation
workflow to five different coral specimens of three cold-water coral taxa,
explore the results with _CoDA_ , describe the overall workflow and experience
while processing the samples.

##  II Segmentation Workflow

Input to our segmentation pipeline is a 3D image resulting from scanning
individual specimens containing one or several coral colony fragments using
computed tomography. An iso-surface rendering of such a 3D image is shown in
Figure 1a.

###  II-A Initial Calyx Segmentation

Figure 3:  _(a)_ The initial contour-tree-based instance segmentation of the
polyp-cavity (calyx) segmentation has 153 instances and involves a trade-off
between the over-segmentation of large, adult corallites and the under-
segmentation of small, young corallites. _(b)_ The final, manually corrected
instance segmentation contains only 114 calices.

The first step in the processing of a 3D image containing coral colonies is
the computation of the _calyx (polyp cavity) segmentation_. This is
accomplished with the ambient occlusion and ambient curvature-based method
developed by Schmitt et al. [39], which makes use of two observations.
Firstly, the cavities are more occluded than regions outside the skeleton [3,
44]. Secondly, coral cavities are mostly convex on the outside and concave on
the inside. Combining both information in a statistical model for background
and foreground, i.e., cavity and non-cavity, gives a soft segmentation of the
polyp cavities (calices). The final segmentation is then obtained by computing
a minimal partition of the soft segmentation. The result for a small colony
fragment is shown in Figure 1b.

In the next step, the initial calyx instance segmentation is computed by a
classical contour-tree segmentation [5] on the random-walk distance transform
[23] of the calyx segmentation. Although a classical Euclidean distance
transform may be used as well, we share the findings of Baum et al. [4] that
the random-walk distance transform yields slightly better results for the
calyx instance segmentation. The persistence value in the contour-tree
segmentation is interactively chosen such that most of the small, young corals
are segmented correctly. This choice, however, comes with an over-segmentation
of larger, adult corals. We find this tradeoff easier to work with than the
other way around, since over-segmentations are easier to spot and correct. The
initial calyx instance segmentation of the same colony fragment as in Figure
1b is shown in Figure 3a.

At this point, the initial calyx instance segmentation can already be refined
with the tools described in subsection II-C. The final result is depicted in
Figure 3b.

###  II-B Automatic Colony-Tree Computation

Figure 4:  _(a)_ The corallite mask is obtained by propagating the calyx
instance segmentation onto the skeleton mask. _(b)_ The region adjacency graph
of the corallite instance segmentation (a) contains a vertex for each label
(coral) and an edge for all labels sharing a border. Highlighted are edges
that are _not_ part of the colony tree and must be removed. _(c)_ Parabolas
are fitted to the calyx instance segmentation, allowing to orient each
corallite from bottom to top. _(d)_ The scatter plot shows the distribution of
the voxel distances $\lVert\gamma\left(t_{i}\right)-x_{i}\rVert$ to the fitted
parabola of a calyx and its skew that is used to orient it.

Among other information, we are particularly interested in the skeleton tree
that describes the mother-daughter corallite relationship in a coral colony,
that is, a graph with a vertex for each corallite and a directed edge going
from the mother corallite to the daughter corallite. Since corals reproduce
asexually within a colony, the graph will be a tree.

The automatic tree computation starts by propagating the calyx instance
segmentation, like the one shown in Figure 3b, onto the corals skeleton. The
propagation algorithm assigns each voxel in the skeleton mask the label of the
closest calyx. The result is a corallite instance segmentation as the one
shown in Figure 4a.

Scanning through the corallite instance segmentation and tracking which
instances touch each other yields a region adjacency graph (RAG) as shown in
Figure 4b. This graph has one vertex for each corallite and one edge for each
pair of neighbouring corallites. Unfortunately, the region adjacency graph is
too large in the sense that it also contains edges between corallites that are
adjacent but do not describe a proper mother-daughter relationship.

In order to prune these superfluous edges, we first orient the corallites. We
start by fitting a parabola to the point cloud given by all voxels occupied by
the corresponding calyx. Let $\mathcal{V}\subset\mathbb{R}^{3}$ denote the
point cloud of voxels belonging to a calyx. Then we seek to find a rotation
matrix $R\in O(3)$, an anchor point $a\in\mathbb{R}^{3}$, the curvature of the
parabola $\alpha\in\mathbb{R}_{\geq 0}$, as well as the curve parameters
$t_{x}\in\mathbb{R}$ for all $x\in\mathcal{V}$, such that the distance between
the spatial parabola

$\gamma(t)=R\begin{pmatrix}t\\\ \alpha t^{2}\\\ 0\end{pmatrix}+a$

and the calyx point cloud is minimized. In more formal terms:

$\min_{\begin{subarray}{c}R\in O(3)\\\ a\in\mathbb{R}^{3}\\\
\alpha\in\mathbb{R}\\\
t_{x}\in\mathbb{R}^{3}\end{subarray}}\sum_{x\in\mathcal{V}}\left\lVert\gamma(t_{x})-x\right\rVert_{2}^{2}.$

In short, the parameters are initialized by first computing a principal
component analysis (PCA) and projecting all voxels onto the first two
principal axes. The rotation matrix coincides, up to the sign of the last
column, with the projection matrix of the PCA, while the anchor and curve
parameters are found by linear regression. The parameters are then refined by
alternating the minimization with respect to the parabola parameters $t_{x}$
and all other parameters. Figure 4c shows the parabola fit for the A2W
specimen.

The parabola fit is finalized by swapping the start
$t_{\text{min}}=\min_{x\in\mathcal{V}}t_{x}$ and end
$t_{\text{max}}=\max_{x\in\mathcal{V}}t_{x}$, if necessary, such that more
points in the point cloud project onto the second half of the parabola, i.e.,

$\underbrace{\left\lvert\\{t_{x}:t_{x}<t_{\text{mid}}\right\\}\rvert}_{\text{number
of points in first half}}\leq\underbrace{\left\lvert\\{t_{x}:t_{x}\geq
t_{\text{mid}}\right\\}\rvert}_{\text{number of points in second half}},$

with $t_{\text{mid}}=\frac{t_{\text{min}}+t_{\text{max}}}{2}$. This condition
is inspired by the observation that the coral grows in breadth. Figure 4d
shows the distribution of the parameters $t_{x}$ and the distance of the voxel
$x$ to the parabola for a single calyx.

Based on the oriented parabola, a simple measure describing whether a voxel is
closer to the bottom or top of a calyx is defined as

$h(x)=\begin{cases}0&,\quad\text{if }t_{x}<t_{\text{min}}\\\
\frac{t_{x}-t_{\text{min}}}{t_{\text{max}}-t_{\text{min}}}&,\quad\text{if
}t_{\text{min}}\leq t_{x}\leq t_{\text{max}}\\\ 1&,\quad\text{if
}t_{x}>t_{\text{max}}\\\ \end{cases},$

where $t_{x}$ again minimizes the distance of $x$ to the parabola, i.e.,

$t_{x}=\mathrm{argmin}_{t\in\mathbb{R}}\lVert\gamma(t)-x\rVert_{2}^{2}.$

An edge $e=(A,B)$ connecting two calices _A_ and _B_ in the region adjacency
graph is now oriented such that

$h_{A}\left(x_{A}\right)\geq h_{B}\left(x_{B}\right),$ (1)

where $x_{A}\in V_{A}$ is the closest point in calyx A to calyx B, and
$x_{B}\in V_{B}$ is analogously the closest point in calyx B to calyx A:

$\lVert x_{A}-x_{B}\rVert_{2}=\text{dist}(V_{A},V_{B}).$

These points are easily obtained by tracking the touching points during the
corallite instance segmentation. The condition Equation 1 orients the edges
such that they start at the top of the source corallite (mother) and end at
the bottom of the target corallite (daughter).

Most of the remaining superfluous edges connect daughters of the same mother
corallite, giving rise to the following configuration:

[-¿,shorten ¿=2pt,auto,node distance=2cm,thick,main
node/.style=circle,draw,font=] [main node] (1) [minimum size=1cm]A; [main
node] (2) [minimum size=1cm, below left of=1] $\text{B}_{1}$; [main node] (3)
[minimum size=1cm, below right of=1] $\text{B}_{2}$;

(1) – (2); (1) – (3); [dashed,color=red] (2) – (3);

A simplification procedure prunes the edge between the daughters
$\text{B}_{1}$ and $\text{B}_{2}$.

The pruned graph already gives a good estimate for the skeleton tree. However,
it may still contain edges for _secondary joints_. Formally, secondary joints
are constituted by the subset of edges within the region adjacency graph that
are not part of the skeleton tree.

The automatically computed skeleton graph and the final skeleton tree, after
manual refinement of the skeleton graph, are shown in Figure 5.

Figure 5:  _(a)_ After orienting the edges and pruning daughter-daughter
relationships, the graph is much cleaner compared to Figure 4b but still
contains some wrong edges, highlighted in red, and wrongly oriented edges,
highlighted in green. In total, it has 115 edges. _(b)_ The final result after
manual refinement by the user is a graph consisting of five trees, each
describing the ancestry in a single colony, and has 109 edges.

###  II-C Refinement Tools

Figure 6:  The images show the workflow of correcting an over-segmentation
obtained by the initial contour-tree segmentation. _(a)_ The initial state is
shown. The exceptionally strongly bent corallite is separated in two segments
that are joined by an edge and an additional secondary joint that connects
them to the coral on the left. _(b)_ The corals are merged by marking the two
segments with a small scribble, shown in green. _(c)_ The merge tool preserves
outgoing edges, so that the secondary joint needs to be removed in an
additional step by marking it. _(d)_ The final result shows the correct coral
segmentation and connectivity.

The initial instance segmentation of the colony into calices and the
associated skeleton graph are not perfect, that is, they may still have errors
which require manual intervention. _CoDA_ provides suitable tools for
correcting over-segmentations, under-segmentations, wrongly oriented edges, as
well as adding missing and removing superfluous edges. All operations acting
on the instance segmentation keep the skeleton graph in sync by inserting or
removing edges and vertices when needed.

Over-segmentations are corrected with the merge tool as shown in Figure 6. The
user marks the instances that should be merged by drawing a line over them.
The voxels in the touched connected components are then collected and assigned
to a new, common label. Their vertices in the spatial graph are merged as well
and internal edges are removed while keeping the edges to non-affected
vertices.

Under-segmentations are corrected by drawing a cutting line across the
instance that is too large. We fit a plane to the line and the viewing
direction, and assign each half-space of the connected component a new label
ID, resulting in a clean, scissor-like cut into two segments. The edges of the
original calyx are distributed between the two new instances such that they
maximize the orientation condition stated in Equation 1. Additionally, a new
edge is inserted between the two new components. If no orientation of the view
allows a clear cut, then the merge and cut tools can be used multiple times
until a satisfactory result is achieved.

The vertices of the graph can only be changed by merging, cutting or
reassigning the labels of the instance segmentation. With the help of graph
editing tools, the user can add missing edges by selecting the source and
target vertices in the 3D view. Similarly, superfluous edges are removed by
selecting the edge itself and deleting it (Figure 6c) as part of the merge
workflow, or by selecting the source and target vertices and disconnecting
them.

From time to time, the heuristic described in subsection II-B yields incorrect
orientations, especially for small corals and for calices where top and bottom
are close by. In those cases, the direction of the adjacent edges can be
corrected by selecting and flipping them.

###  II-D Proofreading

Proofreading in _CoDA_ consists of two steps. The first step concerns the
calyx instance segmentation itself. Here, a major part of wrongly segmented
calices are identified by looking at the feature plots in _CoDA.Graph_ , e.g.,
for volume, surface area, length or the mean distance to the parabolas. Once
all outliers are taken care of, a step-through process presents the user with
all coral instances one after the other. Initially, all instances are marked
as _unseen_. The user then either marks them as _good_ or corrects them with
the proper refinement tools described in subsection II-C. After refinement,
all affected calyx instances are again marked as _unseen_ and placed into the
proofreading queue.

Problems with occlusions, for example in inner, dense areas of a colony, are
taken care of by showing only the closest, adjacent corals by cropping to a
centered region of interest (RoI). Notably, the order in which the user steps
through the instances is not random but visits the next, closest, unchecked
calyx. Thus larger jumps within the 3D volume image are avoided. The camera of
the view is aligned with the principal axes of the calyx to obtain a
standardized view.

Figure 7:  The initial graph computed with the method described in subsection
II-B usually contains superfluous and wrongly oriented edges. Several visual
hints are provided to easily identify these edges. _(a)_ The shortest cycle in
the graph is highlighted so that the user can quickly trace back superfluous
edges, e.g., secondary joints, and remove them. _(b)_ Also, each
calyx/corallite can have at most one predecessor. This fact is used by the in-
degree visual hint that shows the number of incoming edges a calyx/corallite
(vertex) has.

The second proofreading step concerns the edges of the skeleton graph. The
cycle detection highlights the shortest cycle in the graph which can be traced
to find and remove the edge that was caused by a secondary joint. Each vertex
must also have an in-degree of at most one since each calyx/corallite can have
only one or no predecessor. These two hints are the most helpful for
identifying wrong edges and are shown in Figure 7. Other helpful features
during this proofreading stage are the edge orientation criterion in Equation
1, the budding angles, edge lengths or contact area widths. It is important to
note that the visual hints only work for calices and edges that are in the
current segmentation, and that we cannot add visual hints for edges that are
not there anymore, once they have been removed. Thus, also for this step, we
prefer that the initial instance segmentation is an over-segmentation and
contains more calices as well as more edges due to secondary joints.

Similarly to the proofreading of the calyx instance segmentation, the user is
provided with a step-by-step tool for proofreading all edges. This guides the
user through all vertices (calices). The user marks a vertex as _good_ if all
edges starting or ending in the vertex are correct and none are missing.

The proofreading state is just another attribute of the vertices and edges and
can thus also be used as source for the color- and glyph-map. This allows the
user to easily see which vertices and edges are still marked as _unseen_ or as
already been taken care of.

##  III Implementation

The whole proofreading, analysis and exploration framework is implemented
within two different software stacks that communicate via a simple file-based
mechanism. The image processing and refinement tools are implemented in Amira
[41] and are available as custom modules and extensions to the built-in 3D
visual analysis tools. Within Amira, _aggregated_ features are extracted for
the individual calices and related corallites, as well as their relationships,
and are exported to _CoDA.Graph_ , a web application written in Python using
the Bokeh [8] library. _CoDA.Graph_ extends Amira by a rich set of classical
2D visualizations like SPLOMs, scatter plots, histograms, and graph layouts.

###  III-A Linking between Amira and CoDA.Graph

Figure 8:  _CoDA.Graph_ and Amira communicate over a simple file-based
protocol with a canonical naming scheme. In this example, the _lasso
selection_ in _CoDA.Graph_ is propagated to Amira, resulting in a filtered
view in which only the selected vertices are visible in the spatial graph
visualization, as well as the selected calices in the volume visualization.

_CoDA.Graph_ and Amira are entirely decoupled and can be used independently.
However, to facilitate an interactive and seamless exploration of the data, a
simple communication protocol based on .csv files and a canonical naming
scheme is implemented.

On startup, a temporary folder with a known prefix amira_coda_{random_number}/
is created by Amira. _CoDA.Graph_ automatically detects folders with this
prefix and watches their content. Whenever a file in the shared folder is
created, deleted or modified, the change is detected automatically by both
Amira and _CoDA_ , which will trigger a reload of the respective spreadsheets.
To avoid race conditions or undefined behaviour, a spreadsheet is only ever
written to by either Amira or _CoDA_ and read by the other, never by both. The
origin of the data is again indicated with a prefix.

  * •

amira_vertex_{name}.csv
A spreadsheet with features exported from Amira in which each row contains
data for one vertex (calyx/corallite). All vertex spreadsheets must have the
same number of rows.

  * •

amira_edge_{name}.csv
A spreadsheet with features exported from Amira in which each row contains
data for one edge. All edge spreadsheets must have the same number of rows.
Additionally, at least one spreadsheet must have two columns with the index of
the start and end vertices.

  * •

amira_vertex_colormap.csv
A spreadsheet with the current color for every vertex (calyx/corallite). The
colormap can be used in _CoDA.Graph_ so that the user is presented with the
same color scheme in all views.

  * •

amira_edge_colormap.csv
The same as amira_vertex_colormap.csv but here, each row contains the color
for an edge.

  * •

coda_vertex_selection.csv
A spreadsheet containing a single column in which each row indicates whether a
vertex is currently selected in _CoDA.Graph_ or not. This information is used
in Amira to show the currently selected calices/corallites in _CoDA.Graph_ ,
enabling a seamless link-and-brush experience.

  * •

coda_edge_selection.csv
The same as cora_edge_selection.csv but each row indicates if an edge is
currently selected in _CoDA.Graph_ or not.

  * •

coda_vertex_colormap.csv
The same as amira_vertex_colormap.csv but the colors are the ones displayed in
_CoDA.Graph_.

  * •

coda_edge_colormap.csv
The same as amira_edge_colormap.csv but the colors are the ones displayed in
_CoDA.Graph_.

The data flow is visualized in Figure 8.

At this point, it is worth mentioning that the naming scheme and choice of
.csv files for the communication make it easy to use _CoDA.Graph_ without
Amira. Similarly, an integration of _CoDA.Graph_ into other applications is
just a matter of adhering to the naming scheme within the shared folder.

###  III-B Views and Panels

_CoDA.Graph_ is implemented in Bokeh [8] and thus browser-based. It consists
of up to three panels: A control panel and up to two viewer panels.

The leftmost panel is the control panel (Figure 1h) and allows the user to
change parameters such as the colormap, glyphmap, size and opacity for both
edges and vertices. These visual settings are used inside all views, which
gives a uniform impression. Additional controls allow the user to choose the
current visualization type for each view, e.g., a graph layout for the left
and a scatter plot for the right view. Each view type has its own settings
which are also shown in the control panel. For example, the scatter plot view
has a control for choosing the column containing the features of the $x$-axis
and another one for choosing the features on the $y$-axis. _CoDA.Graph_ aims
to be as simple as possible and thus tries to reduce the number of controls
available to the user or use sensible presets whenever possible.

All classical plots are available, that is, _scatter plots_ , _histograms_ ,
_SPLOMs_ and _petal (wedge) plots_. Additionally, _CoDA.Graph_ provides a _map
view_ with the option for different tile providers and locations of the
datasets. A map view showing the location of the five datasets considered in
this paper is shown in Figure 13. The _graph view_ shows a layout computed
with any of the algorithms provided by the Graphviz [17] library. If the
loaded graph is a tree, the view defaults to the _dot_ view, so that a
dendrogram of the generations is shown.

_CoDA.Graph_ also provides functional views for _PCA_ and _UMAP_ [28], two of
the most popular techniques for dimensionality reduction. Upon opening the
view, the user chooses the features subject to the dimensionality reduction
and views the result directly in a SPLOM.

The raw data can be viewed with the _spreadsheet_ view (Figure 1h) and simple
statistics like the data range, standard variance and quantiles are available
in the _statistics_ view.

###  III-C Exploration and Selection Tools

Figure 9:  Depicted are several selections available in _CoDA.Graph_ and their
linked 3D views. The calices are colored by their generation and the
dendrogram is computed with the _dot_ graph layout. _(a.1, a.2)_ The
descendant selection tool selects the whole sub-tree of a vertex, i.e., all
descendants of the corallite represented by the vertex. _(b.1, b.2)_ The
ancestor selection tool selects all ancestors of a single corallite. Here, the
user clicked onto the circled, blue vertex. The path of the ancestors through
the colony is clearly visible in the filtered 3D view. _(c.1, c2)_ The largest
of three colonies present in this specimen was selected using the connected
component tool by clicking on one of the points belonging to the connected
component. _(d.1, d.2)_ The image shows a selection in _CoDA.Graph_ with the
box selection tool. Due to the graph layout, the box selection tool is
perfectly suited for selecting several generations at once. Here, the
selection box is coloured in green and encapsulates the youngest three
generations of all colonies. _(d.3)_ All views are linked, allowing the user
to explore a hypothesis about the data in real-time. The SPLOM views show the
volume, area and length of the calices. All corals that are not in the
selection above _(d.1)_ are muted, eventually confirming the hypothesis that
the youngest corals are not fully grown yet and will need up to four
generations to mature.

Selections can be made in any of the _CoDA.Graph_ views and will be propagated
to Amira. Bokeh comes with several useful selection tools out of the box, for
example, the lasso, box and tap selection tools, which already allow for a
freehand, unconstrained selection in all views.

For the ontogenetic analysis and exploration of the spatial growth patterns of
the coral colonies, we implemented custom tools in the graph view. The
_descendant_ selection tool selects the sub-tree containing all descendants of
the selected calyx/corallite; the _ancestor_ selection tool selects all
ancestors of a single corallite; and the _connected component_ selection tool
selects all corallites within a connected component, which are all
calices/corallites within the same colony fragment. These tools allow the
exploration of a corallite’s ancestry within a specimen and to focus on a
single colony fragment within a dataset. An overview of the selection tools is
shown in Figure 9.

##  IV Case studies

In order to showcase the suitability of _CoDA_ for the analysis of coral
colonies, case studies are presented using the five specimens described in
subsection I-B. The chosen samples differ in size, corallite number, and
corallite and colony morphology, so that the study covers many use cases.

###  IV-A Segmentation

TABLE I:  For each of the specimens investigated in this paper, this table summarizes a lot of information about their processing and the specimens themselves. The table shows the species, scanning resolution and some simple, yet meaningful statistics extracted from the skeleton graph, e.g., the total number of colony fragments, calices/corallites and number of buddings. Listed are also the changes in the colony skeleton graph at different processing stages. The number of vertices coincides with the number of calices/corallites in each specimen. The pruning step from the RAG to the initial colony skeleton graph computed with the method described in subsection II-A greatly reduces the number of wrong edges. For correct edges, i.e., edges that are in the final instance segmentation, the automatic orientation produces mainly the correct orientation and fails only for very few edges.  Sample |  (I) A2W |  (II) C1W |  (III) SaM-ID43148 |  (IV) GeoB127471-1 |  (V) NIWA-148046
---|---|---|---|---|---
Species | Lophelia pertusa | Lophelia pertusa | Lophelia pertusa | Madrepora oculata | Goniocorella dumosa
Voxels | $257\times 237\times 392$ | $275\times 145\times 276$ | $1024\times 729\times 1215$ | $279\times 115\times 335$ | $829\times 455\times 317$
Resolution $[\text{mm}^{3}]$ | $0.351\times 0.351\times 0.3$ | $0.351\times 0.351\times 0.3$ | $0.3125\times 0.3125\times 0.3$ | $0.351\times 0.351\times 0.3$ | $0.146\times 0.146\times 0.3$
Colony fragments | 5 | 1 | 67 | 1 | 9
Calices/Corallites | 114 | 30 | 1725 | 66 | 262
Buddings |  |  |  |  |
Median | 1 | 1 | 1 | 1 | 0
75% Quantile | 2 | 2 | 2 | 2 | 1
Maximum | 4 | 4 | 7 | 3 | 20
Edges |  |  |  |  |
RAG | 148 | 36 | 3592 | 86 | 409
Initialisation | 115 | 29 | 2152 | 67 | 361
Final | 109 | 29 | 1658 | 65 | 253
RAG $\rightarrow$ Initialisation (automatic) |  |  |  |  |
Computation time | 25s | 9s | 420s | 5s | 86s
Unchanged edges | 68 | 0 | 734 | 29 | 218
Pruned edges | 32 | 7 | 1440 | 19 | 48
Initialisation $\rightarrow$ Final (manual) |  |  |  |  |
Unchanged edges | 107 | 29 | 1378 | 55 | 172
Removed edges | 8 | 0 | 711 | 9 | 125
Added edges | 2 | 0 | 217 | 7 | 17
Flipped edges | 0 | 0 | 63 | 3 | 64

Figure 10:  The segmentation results are shown for the Lophelia pertusa C1W
(II) specimen on the left side and for the Madrepora oculata GeoB127471-1 (IV)
specimen on the right side. Both consist of a single colony with C1W (II)
having 30 calices/corallites and GeoB127471-1 (IV) having 66
calices/corallites. The calyx instance segmentation is shown in  _(a.1, a.2)_
; the colony skeleton tree, colored by the generation, in  _(b.1, b.2)_ ; and
the corresponding dendrogram in  _(c.1, c.2)_.  Figure 11:  The processing of
the Goniocorella dumosa _NIWA-148046 (V)_ specimen is complicated by its
completely different inner structure of the colony to other reef-forming stony
corals such as Lophelia pertusa and Madrepora oculata. _(a)_ The corallites of
_Goniocorella dumosa_ are tube-shaped and build intermediate floors
(dissepiments) in regular intervals, leading to an over-segmentation in the
contour-tree segmentation. _(b)_ The parabola fitting procedure also works for
the large super-segments incorporating all segments belonging to a single
corallite. _(c)_ The image shows a rendering of all 262 calices that belong to
the 9 colony fragments present in the specimen. _(d, e)_ The images depict the
calices colored by their generation and the underlying skeleton trees. _(f)_
The plot shows an abstract graph layout of the skeleton trees computed with
the _two-pi_ [47] layout algorithm.  Figure 12:  The images show the results
for the Lophelia pertusa _SaM-ID43148 (III)_ specimen, the largest one in our
case studies made up of in total 66 colony fragments and 1724
calices/corallites. _(a)_ shows the final skeleton graph; _(b)_ shows the
calyx instance segmentation; _(c)_ shows the calices colored by their
generation; and _(d)_ shows the corals colored by their connected component,
i.e., the colony fragment they belong to; _(e)_ shows the dendrograms computed
with the _dot_ graph layout algorithm implemented in _CoDA.Graph_ using the
Graphviz [17] library.

The initial instance segmentation was carried out similarly for all specimens
and follows the workflow and recommendations from section II. Separating a
segment into two segments may require multiple cuts and subsequent merges
since it is sometimes hard to find a cutting plane that separates both
segments clearly, while merging two segments only requires a scribble roughly
drawn on top of them. Additionally, we find over-segmentations easier to spot
than under-segmentations. Two segments differ in color, while an under-
segmented area is only recognizable by its shape or as an outlier in one of
the morphological feature plots.

The comparatively small specimens of Lophelia pertusa, _A2W (I)_ , _C1W (II)_
, and Madrepora oculata, _GeoB12747-1 (IV)_ , were processed almost fully
automatically; the whole process from calyx segmentation to the final colony-
tree and instance segmentation took no longer than an hour each. These
specimens contain 114, 30 and 64 individual calices/corallites, respectively.
The fact that these specimens only contain a few or no secondary joints
simplified the processing and manual interaction. Due to their small size and
morphology, the calices/corallites do not occlude others within the colony and
it was possible to obtain a perfect segmentation without using the RoI
centering and cropping tool in the proofreader.

The instance segmentation, skeleton-tree computation and proofreading of the
largest sample, _SaM-ID43148 (III)_ , which motivated the development of
_CoDA_ , took longer than every other specimen with roughly two working weeks.
After the initial, contour-tree-based calyx instance segmentation, we used
_CoDA.Graph_ to filter small instances with less than $0.5\mathrm{mm}^{3}$ and
removed them. Such small cavities belong to small holes in the ambient
occlusion mask that is used to obtain the polyp-cavity segmentation on which
the calyx instance segmentation is based on, or artefacts due to the scanning
resolution. Even if they belong to young corallites, they are too small to be
part of a meaningful morphological analysis, so that they would be discarded
from further analysis anyway. Next, we examined the initial calyx instance
segmentation with the 3D visualizations and corrected all segments that we
could spot at first glance. Afterwards, we switched to the proofreading tool
for the correction and validation of the calyx instance segmentation.
Especially the canonical view with the automatically centered RoI proved to be
useful in the inner, dense areas of the specimen. Notably, the calyx
segmentation contained many tubes of _Eunice_ worms, which had to be removed.
Using the proofread instance segmentation, we computed the initial colony
skeleton graph and pruned secondary joints with help of the cycle detection
tool, of which _SaM-ID43148 (III)_ contains many. A second proofreading was
carried out, in which a few errors that we missed earlier were corrected, both
in the calyx instance segmentation, as well as the colony-tree graph. The
final instance segmentation contains 1724 individual corals, 1658 edges and 66
colony fragments.

The processing of the Goniocorella dumosa specimen _NIWA-148046 (V)_ proved to
be more involved than the others due to its fundamental different morphology.
Each corallite of this species has intermediate floors (dissepiments) and
budding occurs multiple times during corallite growth. Hence, a single
corallite corresponds to multiple calyx subcavities. Figure 11a shows an iso-
surface rendering and a slice of the original CT intensity image of such a
region. In addition to the unique growth pattern, the calyx subcavities are
more cylindrical in shape, other than _Lophelia pertusa_ or Madrepora oculata,
which are more conic. Thus, they do not exhibit a strong anisotropy in growth
direction which hampered the automatic computation of their orientation and
the subsequent automatic estimation of the coral colony tree. Contrary to the
other corals, here, we used the Euclidean distance transform as scalar field
for the contour-tree segmentation, which gave slightly better results due to
the more cylindrical shape and already good separated calyx subcavities due to
the intermediate floors. The major bottleneck in the proofreading and
refinement of this specimen was the merging of the many calyx subcavities
belonging to the same corallites. From start to end, the first refinement and
proofreading process took roughly two work days and resulted in an instance
segmentation with 262 corallites.

###  IV-B Visual Exploration

After finishing the segmentation of all specimens, we started the visual
exploration by trying to confirm some basic hypotheses and questions.

The SPLOM plots of the volume and surface area of both calices and corallites
colored by their generations showed us that the corals need a growth-period of
up to four generations to reach their adult stage, visible in Figure 9d.3
since they are predominantly smaller in size and length than the older
generations. After this period, morphological features are indistinguishable
even in different branches of the same colony and between colony fragments in
the same specimen.

The dendrograms also showed a skeleton tree that grows more in breadth rather
than in depth for the _Lophelia pertusa_ specimens compared to the _Madrepora
oculata_ specimen. Taking a look at the statistics panel, we could also see
that the maximum number of buds (three) in the _Madrepora oculata_ specimen is
lower than the maximum number of buds (seven) in the _Lophelia pertusa_
specimens. Note that these are first impression on morphological differences
between two species that must be confirmed by the analysis of many more
specimens.

In all cases, the colony-tree graph revealed more components, i.e., colony
fragments, within a single specimen than identified by looking at the real
specimens or the CT images.

By coloring the calices depending on their colony fragment in the _SaM-ID43148
(III)_ sample, we can easily make out the principal directions of growth
visually, as shown in Figure 12d. While younger generations tend to start
growing in a flat area near the ocean floor into many directions, all later
generations tend to follow the same direction towards the top left corner in
the image.

Figure 13:  _CoDA.Graph_ has built-in support for the analysis of multiple
datasets at once by concatenating spreadsheets with the same name. _(a, b)_
The images show the location of five different datasets on a world map and a
zoomed view. The location, i.e., latitude and longitude, are simply given as
columns in one of the vertex-feature spreadsheets. (Tiles CC Esri – Source:
Esri, i-cubed, USDA, USGS, AEX, GeoEye, Getmapping, Aerogrid, IGN, IGP, UPR-
EGP, and the GIS User Community) _(c)_ The scatter plot shows surface area and
volume of all corals. The color in _CoDA.Graph_ is chosen based on the
specimen ID so that the different locations are visually distinguishable.

_CoDA.Graph_ also allows the exploration of multiple colonies at once. We use
this feature of _CoDA.Graph_ to compare the morphology and the ontogenetic
development between different specimens/species. All datasets are annotated
with location attributes and their ID, which we use to compare the
morphologies with respect to their species and location. As shown in Figure
13, the scatter plot of the calyx volume and calyx surface area reveal
different growth patterns and shapes for different species. The same plot also
reveals that the correlation between volume and surface area depends on the
species.

###  IV-C Performance

All analyses and explorations presented here were performed on a desktop PC
with the following configuration: CPU: Intel Core i9-10920X CPU; GPU Nvidia
GeForce RTX 3090, 24 GiB VRAM; Memory: 128 GiB DDR4.

The linking and brushing within _CoDA.Graph_ works for all specimens without
noticeable lags. This is mainly due to the efficient implementation provided
by _Bokeh_ , and the limited number of calices/corallites and thus rows in the
spreadsheets.

The file IO required to pass data between Amira and _CoDA.Graph_ is also not a
bottleneck for the colony sizes considered here, since it happens inside
temporary directories which are usually mounted directly in-memory.
Furthermore, the .csv file format is so simple, that loading and saving
spreadsheets is not a concern.

The update of the 3D visualization in Amira however required a few seconds for
the small corals like _C1W (II)_ and up to 20s for _SaM-ID43148 (III)_ ,
depending on the number of 3D visualizations that are shown at the same time,
e.g., the filtered calyx instance segmentation overlayed with the skeleton-
tree and an iso-surface rendering of the original CT scan. When the plugins in
Amira detect a change inside the shared directory, the _.csv_ are loaded and
parsed, followed by the generation of a new, filtered volume scalar field.
This scalar field is then uploaded to the graphics card before it is finally
rendered. After that, the volume can be explored at interactive frame rates.
Although the filtering could happen directly inside the shaders, making it
only necessary to upload the indices of the selection to the graphics card,
this would have required more effort and changes to Amira than just adding a
new plugin.

##  V Discussion

Three-dimensional dendroidal structures are quite common in nature (e.g.,
trees, coral frameworks) and structure habitats, such as forests or coral
reefs, increase their complexity which results in an increase of ecological
niches and consequently enhanced biodiversity (e.g., [32, 25]). While the
provided ecological niches and biodiversity in these habitats are quite well
studied, the influence of the actual shape of the three-dimensional dendroidal
organisms on the habitat complexity, the ecological niches and biodiversity
are nearly unstudied. One reason for this lack of knowledge is the
predominantly qualitative or semi-quantitative description of these complex
structures. The herein presented _CoDA_ framework provides tools to assess
such structures.

Currently, the presented segmentation pipeline and tools are optimised for
dendroidal cold-water coral colonies with different corallite and colony
morphologies. Even though the development process used only specimens of
Lophelia pertusa, _CoDA_ works well for two other cold-water coral species,
i.e., Madrepora oculata and Goniocorella dumosa. However, the different
corallite morphology of Goniocorella dumosa with its tube-shaped corallites
with multiple intermediate floors (dissepiments) [40] compared to the cone-
shaped corallites of Lophelia pertusa and Madrepora oculata) clearly shows the
sensitivity of the colony skeleton-tree construction on the calyx/corallite
instance segmentation and the subsequent ontogenetic interpretation of the
results. In Lophelia pertusa and Madrepora oculata, corallite budding occurs
at a specific time of corallite development and usually is a single or double
budding (maximal budding up to 7, see Table I). Budding numbers greater than
two occur predominantly in Goniocorella dumosa. Its tube-shaped corallites
exhibit up to $>20$ consecutive budding events (Figure 11, Figure S1), which
has fundamental importance for the ontogenetic interpretation of its colony
skeleton tree. For an ontogenetic analysis of a colony skeleton tree of
Goniocorella dumosa, the calyx/corallite instance segmentation should not be
based on the complete corallites (as shown herein) but on the calyx subvolumes
enclosed by the intermediate floors (dissepiments; Figure 11a).

After a meaningful calyx/corallite instance segmentation, the biggest
challenge and prerequisite for the ontogenetic analysis of coral colonies is
the correct reconstruction of the colony skeleton tree. A single wrong edge
will cause the generation number in a whole branch to be wrong and multiple
errors will accumulate fast. With _CoDA_ , we now have a systematic approach
and intuitive tools at hand for correcting and proofreading the colony
skeleton tree so that the number of errors can be minimized.

Having proofread data for the calyx/corallite instance segmentations and
methods to compute it in a timely manner enable us to gather enough training
data to leverage machine learning methods, for example, a simple convolutional
neural network like a U-Net [34], for learning the corallite borders. The
application of this may reduce the number of initial errors such that manual
correction of errors will require less time. Up until now, no sufficient
training data had been available. The coral colony datasets analyzed within
this paper comprise almost 2200 corallites and their adjacencies, making it
already a feasible training dataset for modern machine learning methods.

The initial automatic colony skeleton graph computation greatly reduces the
amount of superfluous edges in the region adjacency graph. However, some edges
are falsely removed, mostly in dense areas within a colony with many secondary
joints. Often, these regions are interesting by themselves so that a closer
look and manual introspection is required nonetheless. Similarly to the
proofread calyx/corallite instance segmentations, the now available colony
skeleton trees can be used to bootstrap other methods for classifying the
adjacency between corallites, e.g., deep learning-based methods, which will
work directly on the original image data and will potentially be able to
identify the corallite orientation and mother-daughter relationship as well as
the secondary joints even more accurately. Another option might be to employ
graph neural networks for link prediction [48].

The parabolas fitted to the calices are not only useful for the colony
skeleton tree computation, but provide new morphological features. For
example, the mean, standard deviation and skew of the distance distribution
give a simple description for the anisotropy of a calyx, that is, the skew of
the distribution will be larger for a cone-shaped calyx than for a tubular-
shaped one. Each parabola itself provides a robust estimate for the calyx (and
corallite) centerline, its curvature provides a measure for the bending of the
calyx/corallite, and the arc length provides a better estimate for the calyx’
length than the one based on principal axes (PCA).

Although _CoDA.Graph_ provides only minor contributions on its own, it
combines many proven visualization techniques with a simple user interface and
allows the exploration of cold-water corals in a novel, intuitive way. Being
able to take a look at the region in the original volume image on which a data
point in a plot is based on, may it be a classical measurement or otherwise
computed feature, proved to be a very handy and convenient tool during the
exploration and analysis of the coral colonies. Especially the linked 3D
visualization in Amira and the 2D graph-layout in _CoDA.Graph_ were remarkably
useful during the analysis of the corallite ancestry and provided a way to
explore the relationships that would not have been possible within a single 2D
or 3D visualization.

##  VI Conclusion and Future Work

This study provides the technological basis to study complex three-dimensional
dendroidal structures systematically. Exemplified on dendroid stony cold-water
corals, _CoDA_ and _CoDA.Graph_ are capable to disassemble fragments of
dendroidal coral colonies into their principle building blocks (corallites)
and construct an ontogenetic meaningful colony skeleton graph – the basis for
a quantitative and reproducible analysis of the corallite and coral-colony
morphology. Based on this decomposition of coral colonies, an automated
classification of colonial cold-water corals, the investigation of intra- and
interspecies coral morphoplasticity, local or regional spatial preferences of
the distribution of specific morphologies, environmental influences on the
coral morphology and its influence of reef-forming capacity of specific
morphologies become possible, previously hindered by the qualitative to semi-
quantitative acquisition of morphological data of cold-water corals. Our next
goal is the statistical and morphological analysis of the most important reef-
forming cold-water coral colonies to provide an automated CT-based species
identification and investigate similarities and differences in their
ontogenetic colony formation, corallite and coral colony morphology and their
species-specific morphoplasticity.

The preliminary results presented herein regarding the quantifiable
morphological differences between species (Figure 13), are already very
promising. However, these analyses must currently be restricted to younger
parts of colonies as older parts are impacted by bioerosion, especially by
bioeroding sponges that produce large cavities that change the shape of the
coral skeleton considerably (e.g., [6, 7]). To overcome this restriction, we
plan to use the data gathered from the analysis of intact coral colonies, like
the ones presented in this paper, to develop and validate methods that deal
with bioerosion-altered coral skeletons. Furthermore, the software provides
the first step to investigate cold-water coral deposits in more detail. So
far, CT scans of sediment cores retrieved from cold-water coral reefs/mounds
were only used to reconstruct the coral content, the coral clast size and the
clast orientation ([16, 43, 45]). The incorporation of morphological analyses
into these analyses following the approach of _CoDA_ will potentially allow
the differentiation of coral species and identification of specific coral
morphotypes, which will considerably improve the reconstruction of the
temporal development of these cold-water coral reefs/mounds.

We make _CoDA.Graph_ available to the public in the hope that it is not only
useful for the visual analysis of cold-water coral colonies but also for other
dendroid organisms and objects with an inherent tree-like structure.

##  VII Data and Code Availability

The most recent version of _CoDA.Graph_ is available at
https://github.com/zibamira/CTCoral_CoDA. The repository contains the
documentation for the link and brush interface described in subsection III-A,
as well as some of the extracted features for the _A2W (I)_ specimen.

Additionally, we provide the source code for the Amira modules interfacing
with _CoDA.Graph_ at https://github.com/zibamira/CTCoral_hxcoda, the shared
library for Amira 2024.core is also provided.

The original CT scans used in this paper as well as the final segmentation
results and the spreadsheets with the computed features are available in the
the PANGEA data repository.

  1. (I)

_A2W_
Submitted.

  2. (II)

_C1W_
https://doi.pangaea.de/10.1594/PANGAEA.947276

  3. (III)

_SaM-ID43148_
https://doi.pangaea.de/10.1594/PANGAEA.947300

  4. (IV)

_GeoB127471-1_
https://doi.pangaea.de/10.1594/PANGAEA.947334

  5. (V)

_NIWA-148046_
Submitted.

## Acknowledgements

Arne-Jörn Lemke and Christian Timann, Klinikum Bremen-Mitte, Gesundheit Nord
(Bremen), are acknowledged for performing the CT scans and their support
during the measurements. We thank Claudia Wienberg (MARUM) for providing
access to the _GeoB12738-1_ specimen, and André Freiwald and Giovanni Sanna
(both Senckenberg am Meer) for providing access to _SaM-ID43148_. Armin Form
(GEOMAR) is acknowledged for providing CT scans of the specimens _C1W_ and
_A2W_ (BMBF project BIOACID II (FKZ 03F0655A)). Furthermore, we thank the
nautical and scientific crews and especially the chief scientists of RV
POSEIDON cruise POS455, PV PELAGIA cruise 64PE284, and RV METEOR cruise M70-1
during which the samples were retrieved. Di Tracey and Sadie Mills (both from
the National Institute of Water and Atmospheric Research (NIWA, New Zealand)
and the NIWA Invertebrate Collection, are gratefully acknowledged for
providing the Goniocorella dumosa colony NIWA-148046. The specimen was
collected by NIWA as part of their research project “Resilience Of deep-sea
Benthic fauna to the Effects of Sedimentation” (ROBES) funded by the New
Zealand Ministry of Business, Innovation and Employment (MBIE). Furthermore,
we thank Leiss Abdal Al for helping with the segmentation of the _SaM-
ID-43148_ specimen. The work in this paper is part of the project “CTcoral –
CyberTaxonomic Classification and Morphological Characterisation of Cold-Water
Corals” funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation; Ba5042/6-1; Ti706/6-1) as project 490665120.

## References

  * [1] Katerina Achilleos and Abigail M. Smith.  Proof of concept for measuring growth of shelf marine calcifiers: ‘a bryozoan odyssey’.  Marine and Freshwater Research, 74(14):1262–1273, 2023.
  * [2] Claire W. Armstrong, Naomi S. Foley, Viktoria Kahui, and Anthony Grehan.  Cold water coral reef management from an ecosystem service perspective.  Marine Policy, 50:126–134, 2014.
  * [3] Daniel Baum and Jürgen Titschack.  Cavity and Pore Segmentation in 3D Images with Ambient Occlusion.  In Enrico Bertini, Niklas Elmqvist, and Thomas Wischgoll, editors, EuroVis 2016 - Short Papers. The Eurographics Association, 2016.
  * [4] Daniel Baum, James C Weaver, Igor Zlotnikov, David Knötel, Lara Tomholt, and Mason N Dean.  High-throughput segmentation of tiled biological structures using random-walk distance transforms.  Integrative and Comparative Biology, 59(6):1700–1712, 2019.
  * [5] Serge Beucher and Christian Lantuéjoul.  Use of watersheds in contour detection.  volume 132, 01 1979.
  * [6] L. Beuck and A. Freiwald.  Bioerosion patterns in a deep-water Lophelia pertusa (Sleractinia) thicket (Propeller Mound, northern Porcupine Seabight), volume 1 of Erlangen Earth Conference Series, pages 915–936.  Springer, Berlin, 2005.
  * [7] Lydia Beuck, Agostina Vertino, Elizaveta Stepina, Marek Karolczak, and Olaf Pfannkuche.  Skeletal response of lophelia pertusa (scleractinia) to bioeroding sponge infestation visualised with micro-computed tomography.  Facies, 53:157–176, 2007.
  * [8] Bokeh Development Team.  Bokeh: Python library for interactive visualization, 2018.
  * [9] Sandra Brooke and Craig M. Young.  In situ measurement of survival and growth of lophelia pertusa in the northern gulf of mexico.  Marine Ecology Progress Series, 397:153–161, 2009.
  * [10] Andrea Cabrito, Silvia de Juan, Hilmar Hinz, and Francesc Maynou.  Morphological insights into the three-dimensional complexity of rhodolith beds.  Marine Biology, 171(6):127, 2024.
  * [11] L. Chapron, N. Le Bris, X. Durrieu de Madron, E. Peru, P. E. Galand, and F. Lartaud.  Long term monitoring of cold-water coral growth shows response to episodic meteorological events in the nw mediterranean.  Deep Sea Research Part I: Oceanographic Research Papers, 160:103255, 2020.
  * [12] JunYoung Choi, Sang-Eun Lee, YeIn Lee, Eunji Cho, Sunghoe Chang, and Won-Ki Jeong.  Dxplorer: A unified visualization framework for interactive dendritic spine analysis using 3d morphological features.  IEEE Transactions on Visualization and Computer Graphics, 29(2):1424–1437, 2023.
  * [13] Erik E. Cordes, Amanda W. J. Demopoulos, Andrew J. Davies, Ryan Gasbarro, Alexandria C. Rhoads, Elizabeth Lobecker, Derek Sowers, Jason D. Chaytor, Cheryl L. Morrison, Alexis M. Weinnig, Sandra Brooke, Jay J. Lunden, Furu Mienis, Samantha B. Joye, Andrea M. Quattrini, Tracey T. Sutton, Catherine S. McFadden, Jill R. Bourque, Jennifer P. McClain-Counts, Brian D. Andrews, Melissa J. Betters, Peter J. Etnoyer, Gary A. Wolff, Bernie B. Bernard, James M. Brooks, Michael K. Rasser, and Caitlin Adams.  Expanding our view of the cold-water coral niche and accounting of the ecosystem services of the reef habitat.  Scientific Reports, 13(1):19482, 2023.
  * [14] Anna K. Cresswell, Damian P. Thomson, Michael D. E. Haywood, and Michael Renton.  Frequent hydrodynamic disturbances decrease the morphological diversity and structural complexity of 3d simulated coral communities.  Coral Reefs, 39(4):1147–1161, 2020.
  * [15] Vincent Dercksen, Hans-Christian Hege, and Marcel Oberlaender.  The filament editor: An interactive software environment for visualization, proof-editing and analysis of 3d neuron morphology.  Neuroinformatics, 12, 12 2013.
  * [16] Mélanie Douarin, Daniel J. Sinclair, Mary Elliot, Lea-Anne Henry, David Long, Freya Mitchison, and J. Murray Roberts.  Changes in fossil assemblage in sediment cores from mingulay reef complex (ne atlantic): Implications for coral reef build-up.  Deep-Sea Research Part II: Topical Studies in Oceanography, 99:286–296, 2014.
  * [17] John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C. North, and Gordon Woodhull.  Graphviz— open source graph drawing tools.  In Petra Mutzel, Michael Jünger, and Sebastian Leipert, editors, Graph Drawing, pages 483–484, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
  * [18] C. Fouard, G. Malandain, S. Prohaska, and M. Westerhoff.  Blockwise processing applied to brain microvascular network study.  IEEE Transactions on Medical Imaging, 25(10):1319–1328, 2006.
  * [19] A Freiwald and R Henrich.  The sula reef project. unpublished cruise report of r/v victor hensen cruise vh94-95.  Report, 1995.
  * [20] A. Freiwald, R. Henrich, and J. Pätzold.  Anatomy of a deep-water coral reef mound from Stjernsund, West-Finnmark, northern Norway, volume 56 of SEPM Special Publication, pages 141–161.  SEPM (Society for Sedimentary Geology), Tulsa, 1997.
  * [21] Vinicius J. Giglio, Anaide W. Aued, Cesar A. M. M. Cordeiro, Linda Eggertsen, Débora S. Ferrari, Leandra R. Gonçalves, Natalia Hanazaki, Osmar J. Luiz, André L. Luza, Thiago C. Mendes, Hudson T. Pinheiro, Bárbara Segal, Luiza S. Waechter, and Mariana G. Bender.  A global systematic literature review of ecosystem services in reef environments.  Environmental Management, 73(3):634–645, 2024.
  * [22] Mathieu Gonin, Isai Salas-González, David Gopaulchan, Juan P. Frene, Stijn Roden, Bram Van de Poel, David E. Salt, and Gabriel Castrillo.  Plant microbiota controls an alternative root branching regulatory mechanism in plants.  Proceedings of the National Academy of Sciences, 120(15):e2301054120, 2023.
  * [23] L. Gorelick, M. Galun, E. Sharon, R. Basri, and A. Brandt.  Shape representation and classification using the poisson equation.  In Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004., volume 2, pages II–II, 2004.
  * [24] Dirk Granse, Jürgen Titschack, Malika Ainouche, Kai Jensen, and Ketil Koop-Jakobsen.  Subsurface aeration of tidal wetland soils: Root-system structure and aerenchyma connectivity in spartina (poaceae).  Science of The Total Environment, 802:149771, 2022.
  * [25] Siria Gámez and Nyeema C. Harris.  Conceptualizing the 3d niche and vertical space use.  Trends in Ecology & Evolution, 37(11):953–962, 2022.  doi: 10.1016/j.tree.2022.06.012.
  * [26] D. Hebbeln.  Report and preliminary results of rv pelagia cruise 64pe284. cold-water corals in the gulf of cádiz and on coral patch seamount (ne atlantic). portimão - portimão, 18.02. - 09.03.2008, 2008.
  * [27] Emily Rebecca Lines, Fabian Jörg Fischer, Harry Jon Foord Owen, and Tommaso Jucker.  The shape of trees: Reimagining forest ecology in three dimensions with remote sensing.  Journal of Ecology, 110(8):1730–1745, 2022.
  * [28] Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger.  Umap: Uniform manifold approximation and projection.  Journal of Open Source Software, 3(29):861, 2018.
  * [29] Christina E. Mueller, Tomas Lundälv, Jack J. Middelburg, and Dick van Oevelen.  The symbiosis between lophelia pertusa and eunice norvegica stimulates coral calcification and worm assimilation.  PLOS ONE, 8:e58660, 2013.
  * [30] Covadonga Orejas and Carlos Jiménez.  The Builders of the Oceans – Part I: Coral Architecture from the Tropics to the Poles, from the Shallow to the Deep, pages 627–655.  Springer International Publishing, Cham, 2017.
  * [31] Karran Pandey, Talha Bin Masood, Saurabh Singh, Ingrid Hotz, Vijay Natarajan, and Tejas Murthy.  Morse theory-based segmentation and fabric quantification of granular materials.  Granular Matter, 24, 02 2022.
  * [32] Daniel R. Pygas, Renata Ferrari, and Will F. Figueira.  Review and meta-analysis of the importance of remotely sensed habitat structural complexity in marine ecology.  Estuarine, Coastal and Shelf Science, 235:106468, 2020.
  * [33] J.M. Roberts, A.J. Wheeler, A. Freiwald, and S. Cairns.  Cold-Water Corals: The Biology and Geology of Deep-Sea Coral Habitats.  Cambridge University Press, Cambridge, 2009.
  * [34] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Nassir Navab, Joachim Hornegger, William M. Wells, and Alejandro F. Frangi, editors, Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, pages 234–241, Cham, 2015. Springer International Publishing.
  * [35] Anita Roth-Nebelsick, Tatiana Miranda, Martin Ebner, Wilfried Konrad, and Christopher Traiser.  From tree to architecture: how functional morphology of arborescence connects plant biology, evolution and physics.  Palaeobiodiversity and Palaeoenvironments, 101:267–284, 2021.
  * [36] Giovanni Sanna, Janina V. Büscher, and André Freiwald.  Cold-water coral framework architecture is selectively shaped by bottom current flow.  Coral Reefs, 2023.
  * [37] Giovanni Sanna and André Freiwald.  Deciphering the composite morphological diversity of Lophelia pertusa, a cosmopolitan deep-water ecosystem engineer.  Ecosphere, 12(11):e03802, 2021.
  * [38] Mie Sato, Ingmar Bitter, Michael Bender, Arie Kaufman, and Masayuki Nakajima.  Teasar: Tree-structure extraction algorithm for accurate and robust skeletons.  volume 54, pages 281 – 449, 02 2000.
  * [39] Kira Schmitt, Jürgen Titschack, and Daniel Baum.  Polyp-Cavity Segmentation of Cold-Water Corals guided by Ambient Occlusion and Ambient Curvature.  In Renata G. Raidou, Björn Sommer, Torsten W. Kuhlen, Michael Krone, Thomas Schultz, and Hsiang-Yun Wu, editors, Eurographics Workshop on Visual Computing for Biology and Medicine. The Eurographics Association, 2022\.
  * [40] Donald F. Squires.  Scleractinian corals from the norfolk island cable.  Records of the Auckland Institute and Museum, 5(3/4):195–201, 1960\.
  * [41] Detlev Stalling, Malte Westerhoff, and Hans-Christian Hege.  Amira: a highly interactive system for visual data analysis.  In The Visualization Handbook, pages 749–767. Elsevier, 2005.
  * [42] Fitalew Agimass Taye, Maja Vinde Folkersen, Christopher M. Fleming, Andrew Buckwell, Brendan Mackey, K. C. Diwakar, Dung Le, Syezlin Hasan, and Chantal Saint Ange.  The economic values of global forest ecosystem services: A meta-analysis.  Ecological Economics, 189:107145, 2021.
  * [43] J. Titschack, D. Baum, R. De Pol Holz, M. López Correa, N. Forster, S. Flögel, D. Hebbeln, and A Freiwald.  Aggradation and carbonate accumulation of holocene norwegian cold-water coral reefs.  Sedimentology, 62:1873–1898, 2015.
  * [44] Jürgen Titschack, Daniel Baum, Kei Matsuyama, Karin Boos, Claudia Färber, W-A Kahl, Karsten Ehrig, Dietmar Meinel, Carmen Soriano, and Stuart R Stock.  Ambient occlusion–a powerful algorithm to segment shell and skeletal intrapores in computed tomography data.  Computers & Geosciences, 115:75–87, 2018.
  * [45] Jürgen Titschack, Hiske G. Fink, Daniel Baum, Claudia Wienberg, Dierk Hebbeln, and André Freiwald.  Mediterranean cold-water corals – an important regional carbonate factory?  The Depositional Record, 2(1):74–96, 2016.
  * [46] J. B. van Hulzen, J. van Soelen, and T. J. Bouma.  Morphological variation and habitat modification are strongly correlated for the autogenic ecosystem engineerspartina anglica (common cordgrass).  Estuaries and Coasts, 30(1):3–11, 2007.
  * [47] Graham J. Wills.  Nicheworks — interactive visualization of very large graphs.  In Giuseppe DiBattista, editor, Graph Drawing, pages 403–414, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
  * [48] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  Advances in neural information processing systems, 31, 2018.

Kira Schmitt received her B.Sc. and M.Sc. degree in mathematics with a minor
in computer science from the Technical University of Kaiserslautern (RPTU).
She worked at the Fraunhofer Institute for Industrial Mathematics during her
studies and gained a strong interest in image processing and visualization.
Now, she develops methods for the automatic analysis of cold-water corals
based on CT images as a full time researcher at the Zuse Institute Berlin as
part of her Ph.D. thesis. A project that combines her interests in image
processing, nature and the ocean life. E-Mail<EMAIL_ADDRESS>
---
Jürgen Titschack is carbonate sedimentologist at Marum - Center for Marine
Environmental Science, University of Bremen specialised in non-tropical
carbonate systems. He is interested in the integration of sedimentological,
geochemical and palaeontological datasets of cold-water coral systems and
island shelve carbonates to investigate their fate during climatic changes,
and the development and application of computed tomography-based methodologies
for the analysis of biogenic skeletons, shells, traces and, as well as within,
sediment cores. E-Mail<EMAIL_ADDRESS>
---
Daniel Baum studied computer science at Humboldt University Berlin (HUB),
Germany, and the University of Edinburgh, Scotland. He received his MS degree
from HUB and his PhD degree from Freie Universität Berlin, Germany. During his
PhD, he worked in the field of molecular visualization and similarity. Later,
his research interests shifted towards image analysis. He is head of the
research group Visual Data Analysis at Zuse Institute Berlin (ZIB), where he
leads quite diverse projects from neurobiology to meteorology to the virtual
unfolding of ancient written documents and the analysis of cold-water corals.
E-mail<EMAIL_ADDRESS>
---

## Supplementary Materials

Figure S1:  The image shows the dendrogram for the _NIWA-148046_ specimen,
also shown in Figure 11. For this species, the skeleton-tree does not
correspond to the ontogenetic development, since it does not take into account
the consecutive budding during corallite growth. An instance segmentation
based on the calyx subvolumes (cavities between intermediate floors
(dissepiments)) might likely allow the construction of an ontogenetically
meaningful skeleton tree.  Figure S2:  The images depict the workflow of
removing secondary joints. _(a)_ A region with multiple secondary joints,
highlighted in red in (b) and (c). Here, multiple coral branches are grown
together. _(b, c)_ The skeleton graph contains the secondary joints as
superfluous edges (red) that must be removed. The iso-surface rendering of the
coral CT-scan is important for deciding whether an edge is a secondary joint
or not. The user may make use of different visualizations in this step. Then,
the secondary joints are marked and removed. _(d)_ The image shows the final
result without secondary joints.  Figure S3:  The images show some
representative regions of the _SaM-ID43148_ specimen responsible for the
difficulties involved in its analysis. The specimen contains many tubes
belonging to _Eunice_ worms which have to be removed during the segmentation,
one is highlighted in green in images _(a)_ and _(b)_ , and one is prominently
shown in image _(d)_. Some are very similar in shape to the _Lophelia pertusa_
corallites, making it hard to identify them automatic. The density of the
corallites and the number of secondary joints impose additional difficulties
onto the segmentation and proofreading process.  Figure S4:  The images show
different selections for the Lophelia pertusa specimen _SaM-ID43148_ ,
similarly to the selections in Figure 9. _(a)_ The dendrogram shows the
selection of the longest ancestry path and the 3D visualization of the calices
belonging to it. _(b)_ The largest colony fragment is selected in the
dendrogram (left) and visualized on the right side. _(c)_ The three youngest
generations are selected so that the 3D visualization gives an impression of
(relative) location of the colony fragments present in the specimen.