[Go back to main page.]

3D Shape Analysis for Connectomics: Reduced Graph Descriptor

The Figure below describes our pipeline for extracting the Reduced Graph representation from the 3D model of an organelle. We start with a 3D voxel representation of an organelle, and use an off-the-shelf implementation of the algorithm proposed by Kalman (2014)1 to extract its 3D skeleton (shown in panel (b) in the Figure below). The skeletonization algorithm can be intuitively thought of as chipping away with a chisel at the 3D voxel representation until the "thickness" is just one voxel, at the same time ensuring that the number of connected components in the shape does not change.

Now this Extracted Skeleton itself can be thought of as a grpahical representation of the shape with each voxel representing a node in the graph, with edges between adjacent voxels of length 1 unit. However the issue with using this as a descriptor is that:

  1. The skeleton contains a large number of voxels which can make computation expensive.
  2. The skeleton contains features such as branches which are negligible in length (compared to total path length) and tiny loops, which can be safely ignored without losing a general sense of the shape.

To overcome these issues, we proposed the Reduced Graph representation (panel (c) in the Figure), which I will discuss in detail below.

Pipeline for extraction of Reduced Graph from a 3D voxelized model.

Reduced Graph

The Extracted Skeleton graph $G$ contains a large number of vertices denoted by the set $V$. We define two subsets of $V$:

  • Junctions: $J = {v \in V : \text{degree}(v) > 2}$
  • Endpoints:$E = {v \in V : \text{degree}(v) = 1}$

We want to reduce the Skeleton Graph $G$ to the Reduced Graph $G_S$ whose set of vertices is $J \cup E$ (together referred to as the Key Nodes). Moreover we want $G_S$ to preserve topological features such as paths and distances (along the 3D Extracted Skeleton) between any pair of Key Nodes. Lastly, we want $G_S$ to preserve any cycles present in the Extracted Skeleton graph $G$ and also preserve multiple paths between any two Key Nodes.

Graph Reduction Algorithm

The algorithm consists of two stages: (1) Reduction, and (2) Pruning. An application of the algorithm on a Toy Graph follows below.

Reduction

To extract $G_S$ from $G$ while preserving the aforementioned desirable properties, we use a traversal which is a modified version of Breadth First Search, on the skeleton graph $G$. At each step of the traversal, we only enqueue Key Nodes to our traversal queue. That is, we initialize the queue with a Key Node, and while visiting a Key Node $v$, we only enqueue:

  1. Any Key Nodes which are adjacent to $v$, or
  2. any other Key Nodes which are connected to $v$ by a path in $G$ comprising only of non-Key Nodes (referred to as a Simple path).

While doing this traversal we keep track of two metrics (which could be used as edge weights in the Reduced Graph):

  1. The length of the path between any pair of Key Nodes.
  2. The "thickness" of the path between any pair of Key Nodes, where thickness of a path is the mean of Distance Transform of each edge in $G$ in the path.

Cycles We keep track of cycles in $G$ by noting that if we re-visit any Key Node, that indicates the presence of a cycle containing that Key Node.

Pruning

Once we have created the Reduced Graph $G_S$, it may still contain short branches or cycles with small circumference, which are not essential for capturing a sense of the shape. Therefore, we prune the graph by collapsing all edges and cycles which have a length below a certain threshold (a hyperparameter).

Application of the Graph Reduction algorithm on a toy graph.

References

  1. Palagyi, Kalman (2014) - A sequential 3d curve-thinning algorithm based on isthmuses.