Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Cubical Homology Computation: Persistence on Images

3 minute read

Published:

TL;DR: A 2D image is a natural cubical complex: pixels are 2-cubes, edges between adjacent pixels are 1-cubes, and corners are 0-cubes. Filtering by pixel intensity gives a filtration whose persistence diagram captures topological features (connected components, loops, cavities) at all scales. Libraries like Cubical Ripser and GUDHI compute cubical persistence in O(n log n) for n pixels — far faster than building a Rips complex.

Cubical Complexes for Images

An elementary cube in \(\mathbb{R}^d\) is a product of intervals:

$$Q = I_1 \times I_2 \times \cdots \times I_d \quad \text{where each } I_k \in \{[a, a+1], \{a\}\}$$

The dimension of \(Q\) is the number of non-degenerate factors \([a, a+1]\). A cubical complex \(K\) is a finite set of elementary cubes closed under faces.

For a 2D image of size \(m \times n\):

  • 0-cubes (vertices): \(m \cdot n\) pixels.
  • 1-cubes (edges): horizontal and vertical edges between adjacent pixels.
  • 2-cubes (faces): unit squares between 4-adjacent pixels.

Total complex size: \(O(mn)\) — much smaller than the \(O(2^{mn})\) worst case for a full simplicial complex.

Sublevel Set Filtration

Given a scalar function \(f: \mathbb{R}^d \to \mathbb{R}\) (e.g., image intensity), the sublevel set filtration is:

\[K_t = \{Q \in K : f(Q) \leq t\}\]

where \(f(Q)\) for a cube \(Q\) is typically defined as \(\max_{v \in \text{vertices}(Q)} f(v)\) — the maximum vertex value. This ensures monotonicity: \(K_s \subseteq K_t\) whenever \(s \leq t\).

The superlevel set filtration (filtering by \(f(Q) \geq t\)) is used for detecting “dark blobs” in images.

Boundary Maps for Cubes

The cubical boundary map is analogous to the simplicial case. For a 2-cube \([a, a+1] \times [b, b+1]\):

\[\partial_2 Q = [a, a+1] \times \{b\} - [a, a+1] \times \{b+1\} + \{a\} \times [b, b+1] - \{a+1\} \times [b, b+1]\]

The sign conventions ensure \(\partial^2 = 0\), so cubical homology is well-defined.

Cubical Ripser

Cubical Ripser (Kaji et al. 2020) implements:

  1. Build the cubical filtration from pixel/voxel data.
  2. Apply the standard persistence algorithm with column reduction.
  3. Use the cohomology algorithm in the reverse direction for speedup.

Performance: On a \(256 \times 256\) image (65536 pixels), cubical persistence computation takes under 1 second. For a \(256^3\) volumetric image (~16 million voxels), it takes a few minutes — feasible for medical imaging workflows.

Applications

  • Medical imaging: persistence diagrams of CT/MRI scans detect structural features (vessels, lesions) across scales.
  • Materials science: 3D X-ray tomography of porous materials; the \(H_2\) diagram captures the birth/death of enclosed voids.
  • Texture analysis: \(H_0\) and \(H_1\) persistence features from sublevel set filtrations distinguish textures better than histogram-based features.
  • Change detection: comparing persistence diagrams of the same scene at different times detects structural changes.
Key Insight: Cubical homology computation benefits from the regular structure of grids: the boundary matrix is sparse (each cube has at most $$2d$$ faces), and sorting by function value is trivial. Cubical Ripser exploits this with bitwise operations and achieves near-linear time in practice. This makes cubical persistence practical for large 3D scientific datasets where Vietoris-Rips would be completely intractable.

References

  • S. Kaji, T. Sudo, K. Ahara, “Cubical Ripser: Software for Computing Persistent (Co)homology of Image and Volume Data,” arXiv:2005.12692, 2020.
  • T. Kaczynski, K. Mischaikow, M. Mrozek, Computational Homology, Springer, 2004.
  • GUDHI Library: gudhi.inria.fr

You May Also Enjoy

GAPE: Remember to Forget — Gated Adaptive Positional Encoding

4 minute read

Published:

GAPE is a drop-in RoPE augmentation that adds content-aware attention logit biases: a query-gate suppresses irrelevant distant context while a key-gate preserves salient distant tokens. Provably sharper attention and improved long-context robustness — no architecture changes needed.

PolyNSD: Polynomial Neural Sheaf Diffusion

4 minute read

Published:

PolyNSD replaces the NSD propagation operator with a degree-K Chebyshev polynomial in the normalised sheaf Laplacian, achieving SOTA on homo- and heterophilic benchmarks with only diagonal restriction maps and dramatically lower memory usage.

TDA in Materials Science: Topology of Structure and Phase

3 minute read

Published:

Persistent homology characterises the multi-scale structure of materials — from pore geometry in catalysts to glass transition in amorphous materials. H₀ captures connectivity, H₁ captures channels and rings, H₂ captures enclosed voids. These topological descriptors predict mechanical properties, adsorption capacity, and phase transitions more accurately than geometric averages.

TDA in Drug Discovery: Molecular Topology

3 minute read

Published:

Persistent homology provides multi-scale topological fingerprints of molecular structures — capturing rings, cavities, and protein pockets that traditional cheminformatics descriptors miss. Applications include binding site detection, ADMET property prediction, and protein-ligand interaction modelling.