FeatureLego: Volume Exploration Using Exhaustive Clustering of Super-Voxels

Shreeraj Jadhav, Saad Nadeem, Arie Kaufman

Abstract

We present a volume exploration framework, FeatureLego, that uses a novel voxel clustering approach for efficient selection of semantic features. We partition the input volume into a set of compact super-voxels that represent the finest selection granularity. We then perform an exhaustive clustering of these super-voxels using a graph-based clustering method. Unlike the prevalent brute-force parameter sampling approaches, we propose an efficient algorithm to perform this exhaustive clustering. By computing an exhaustive set of clusters, we aim to capture as many boundaries as possible and ensure that the user has sufficient options for efficiently selecting semantically relevant features. Furthermore, we merge all the computed clusters into a single tree of meta-clusters that can be used for hierarchical exploration. We implement an intuitive user-interface to interactively explore volumes using our clustering approach. Finally, we show the effectiveness of our framework on multiple real-world datasets of different modalities.

Introduction

Exploring 3D volumetric data, such as medical CT and MRI scans, to identify specific "semantic features" (like a pancreas or a specific bone) is a notoriously difficult task. Standard techniques often rely on clustering voxels based on intensity histograms, which frequently fail to separate different materials with similar intensities or those that are physically touching.

Traditionally, researchers have had to manually tune clustering parameters—guessing a value, checking the result, and repeating the process. This trial-and-error approach is time-consuming and prone to missing critical boundaries. FeatureLego addresses this by replacing parameter guesswork with an efficient, exhaustive clustering algorithm that pre-calculates every possible semantic feature boundary and organizes them into a hierarchical "meta-cluster tree."

Methods

The FeatureLego pipeline consists of five primary stages designed to move from raw data to interactive visualization:

  1. Super-Voxel Partitioning: The system groups raw voxels into "super-voxels" using a 3D extension of the SLIC (Simple Linear Iterative Clustering) algorithm. This reduces complexity from millions of voxels to a few thousand manageable "atomic" units.
  2. Exhaustive FH Clustering: The core innovation is an algorithm that performs exhaustive clustering using the Felzenszwalb and Huttenlocher (FH) graph-based method. Instead of sampling random parameters, the system tracks "maximal contiguous intervals" of the parameter $k$ where the clustering output remains identical.
  3. Cluster Overlapping Regions: Because exhaustive clustering produces thousands of regions, many of which overlap, the system groups them into "meta-clusters" using Jaccard distance and a Minimal Spanning Tree (MST) approach.
  4. Meta-Cluster Tree Construction: These meta-clusters are arranged into a tree based on containment (e.g., a "kidney" cluster is contained within an "abdominal cavity" cluster).
  5. Semantic Feature Selection: Users navigate this tree via an exploration interface to select and colorize features using transfer functions.
The five-step FeatureLego pipeline for volume exploration.

Key Insights and Ideas

The "Interval Tracking" Logic

The most significant technical contribution is the realization that FH clustering is monotonic relative to its parameter $k$. By calculating the exact point where an edge "collapses" to merge two regions, the algorithm can jump through the parameter space, guaranteed to never miss a unique clustering result while avoiding redundant calculations.

Meta-Clusters as Navigation Nodes

By merging overlapping results into meta-clusters, the system creates a manageable hierarchy. Each meta-cluster becomes a node in a tree, mirroring the natural anatomical structure of biological data. This makes the user interface intuitive for medical professionals, allowing them to "drill down" from large cavities to specific organs.

Conceptual overview of super-voxel partitioning, exhaustive clustering, and meta-cluster tree construction.

Results and Discussion

The authors evaluated FeatureLego on seven real-world datasets, including MRI scans of tomatoes and knees, and CT scans of the chest, abdomen, and teeth.

  • Superior Feature Separation: In the Tooth dataset, FeatureLego successfully separated the enamel, dentine, and root canals—a task where traditional "normalized-cut" methods often produce fragmented or merged results.
  • Efficiency and Scalability: Exhaustive clustering for a complex Knee MRI dataset took only 7.3 minutes on a standard desktop. For the massive Abdominal CT, the system reduced 117 million potential regions into a navigable tree of roughly 127,000 nodes.
  • Limitations: The success of the feature selection depends on the initial super-voxel size; if super-voxels are too large, fine details may be lost. Additionally, memory consumption for large datasets can be high, with the Abdominal CT requiring 23GB of RAM.

Future work will focus on scaling the framework to even larger datasets, such as high-resolution microscopy, through advanced data compression or out-of-core processing.

Summary updated

Abstract

We present a volume exploration framework, FeatureLego, that uses a novel voxel clustering approach for efficient selection of semantic features. We partition the input volume into a set of compact super-voxels that represent the finest selection granularity. We then perform an exhaustive clustering of these super-voxels using a graph-based clustering method. Unlike the prevalent brute-force parameter sampling approaches, we propose an efficient algorithm to perform this exhaustive clustering. By computing an exhaustive set of clusters, we aim to capture as many boundaries as possible and ensure that the user has sufficient options for efficiently selecting semantically relevant features. Furthermore, we merge all the computed clusters into a single tree of meta-clusters that can be used for hierarchical exploration. We implement an intuitive user-interface to interactively explore volumes using our clustering approach. Finally, we show the effectiveness of our framework on multiple real-world datasets of different modalities.
BibTeX
@article{jadhav2019featurelego,
  author = {Shreeraj Jadhav and Saad Nadeem and Arie Kaufman},
  title = {{FeatureLego: Volume Exploration Using Exhaustive Clustering of Super-Voxels}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2019},
  doi = {10.1109/tvcg.2018.2856744},
}
Figure