[Go back to main page.]

3D Shape Analysis for Connectomics: Different Shape Descriptors

The overarching objective is to come up with a shape descriptor which captures topological details (such as connections between two points in the shape, the distance between two points). For instance, in the Figure below, if we are to stretch out the two mitochondria (left and center columns), we will end up with a star looking shape (right column). So a desirable shape descriptor will be able to identify that the two mitochondria shown in this figure are similar in topology.

Left and Center Columns: Two mitochondrias with similar topologies but different shapes.
Right: A shape descriptor which captures topological details.

I implemented two such shape descriptors which I discuss below: (1) 2D Distance Tranform Profile, and (2) Heat Kernel Signature. The latter produced better results than the former, however it is not as intuitive a shape descriptor as the Reduced Graph, which we finally settled on.

1. K-Means Clustering on 2D Distance Transform Profile

Experiment

Intuition The simple intuition here is that since the organelle we are working with (mitochondria in particular) has a tubular structure across specimens in the dataset, perhaps we could use the thickness of that tube at each point along the tube's length, as a shape descriptor.

Process I followed the steps below for this approach:

  1. First compute the shadow of a 3D shape on XY plane.
  2. Compute the Distance Transform of this 2D shadow image. I used the medial_axis function in Scikit-Image. The Distance Transform is basically a measure of the "thickness" of a 2D shape.
    • Medial Axis is a 1 pixel wide "skeleton" inside a 2D shape with the property that it has more than one closest points on the boundary.
    • Distance Transform computes, for each point on the Medial Axis, the closest distance of that point from the 2D shape's boundary.
  3. Use the Distance Transform as a shape descriptor and compute K-Means clusters on the set of shapes. The value $k=5$ gave the most visually appealing results.

Results

The Figure below shows the clusters created for a subset of the Mitochondria dataset. We can observe that even this simple clustering method generates clusters with high intra-cluster homegeniety. That said, we can spot some errors, e.g. look at the mitochondria on top-right of Cluster 4. It clearly doesn't belong here. I was able to resolve such errors with the help of a better shape descriptor (the Heat Kernel Signature), which I discuss below.

Five clusters of mitochondria shapes created using K-means on 2D Distance Transform Profiles

2. Heat Kernel Signature1

Experiment

Intuition: If I place a heat source on the tip of my right hand's thumb, the amount of heat that travels to the corresponding point on my left thumb, in some time $T$, will be invariant under many different poses which my body can take (e.g. me standing with my hand stretched out or stretched up). The Heat Kernel Signature (HKS) is a shape descriptor proposed by Sun et al1 which is based on this invariance property of heat diffusion over a surface.

HKS Based Shape Matching: I implemented the HKS based shape matching algorithm proposed by Bronstein et al. in their paper "Shape google: Geometric words and expressions for invariant shape retrieval"2. The basic idea is to compute the HKS for each point of each shape in a set of shapes, and then learn an HKS "Vocabulary" of some size $V$. This is done by clusterin over the HKS' to create $V$ clusters, and use their centroids as words in the HKS Vocabulary. I used off-the shelf code for HKS generation, and implemented the clustering and shape retrieval parts myself.

Once an HKS Vocabulary has been learnt, we represent each shape as a Bag of Features. Specifically, let the Vocabulary be represented by: $$ \mathbb{V} = (p_1, \cdots, p_V) $$ Let the points in the shape be represented by $X$, and for each $x \in X$, let $\text{HKS}(x)$ denote the pointwise HKS. We want to represent each point $x$ by a feature descriptor $\theta(x) = (\theta_1(x), \cdots, \theta_V(x))$ where:

$$ \theta_i(x) = ce^{\frac{\lVert \text{HKS}(x) - p_i\rVert_2^2} {2\sigma^2}} $$

Here $c(x)$ is a normalization constant which ensures $\lVert \theta(x) \rVert_2 = 1$ and $\sigma$ is a hyperparameter. Finally, to get the Bag of Feature shape descriptor for the whole shape, I took the average of feature descriptors $\theta(x) \space \forall x \in X$.

Results

The Figure below shows the results from HKS based Bag of Feature clustering. I use a Vocabular of size 8 for this experiment. The left panel plots the shape descriptor $\theta$ (a vector of length 8) for the 8 mitochondria shown in the right panel. One can observe that all the specimens which look tubular in nature have a similar $\theta$ profile (shown in blue), while those which look spherical have profiles similar to each other (shown in red).

Furthermore, this approach correctly clusters specimen ID 643 (bottom right in the right panel), along with the other tubular mitochondrias (see its HKS Bag of Feature vector as the black dotted line in left panel). However this specimen was incorrectly clustered in Cluster 4 using the 2D Distance Transform Profile (see the plot above).

Left Panel: Shows HKS-Bag of Features shape descriptor using a size 8 Vocabulary for mitochondria specimen shown in the right panel.
Right Panel: Shows the 3D models of the eight mitochondria specimens.

References

  1. Jian Sun, Maks Ovsjanikov, Leonidas Guibas (2009) - A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion
  2. Alexander Bronstein, Michael Bronstein, Leonidas Guibas, Maks Ovsjanikov (2011) - Shape google: Geometric words and expressions for invariant shape retrieval