A fibration model for $d$-dimensional image patches

Brad Nelson

Department of Statistics & CCAM
University of Chicago

AMS Special Session on Applied Topology
January 8, 2021


Thanks to Gunnar Carlsson for many discussions on the Klein bottle for image patches and possible extensions.

Funding I received while working on this topic

  • DoD through NDSEG fellowship
  • DOE through SLAC/Neutrino group
  • Unbox AI


  1. Image Patch Data
  2. Data Exploration
  3. Fibration Model
  4. Fibration-Assisted Visualization

Image Patch Data

2D: $\ell \times \ell$ pixel squares.

3D: $\ell \times \ell \times \ell$ voxel cubes.

Patches are sampled from natural (non-random) images, so there is structure in the data.

Filter for high-contrast, dense subsets.
k, p: take top p% ranked by distance to k-nearest neighbor.

2D Patch

Topology of Image Patches

Topology in the visual cortex

  • [T 95] Klein bottle model in stimulus maps.

Klein Bottle In Image Patches

Klein Bottle
Klein Bottle
Painting by Ron Estrin
Model proposed by Carlsson, Ishkhanov, de Silva, and Zomorodian [C+ 08]


  • Topological modeling of 3D image patch data.
  • Analyze a fiber bundle model that generalizes Klein bottle for 2D patches.
  • Use this to understand the distribution of patches in different data sets.


Van Hateren data set [vHvdS 98] - data base of 2D natural images.

BRATS MRI data set [BRATS]

Penobscot seismic interpetation data [Pen]

Van Hateren

Data Processing

Procedure used in [LPM 02]

  1. Sample random patches
  2. Take top 20% by contrast norm
  3. Mean-center and normalize contrast

Additional steps used for high-density regions [dSC 04, C+ 08]

  1. Compute distances to $k$-nearest neighbor
  2. Take $p$% by smallest distance

We'll visualize data using principal component embeddings.
Eigenpatches = principal components interpreted as patch.

Van Hateren, k=100 p=20

2-dimensional PCA embedding with eigenpatches.
VH 7x7 k100 p20 VH 7x7 k100 p20 VH 7x7 k100 p20
$7\times 7$ patches
Primary circle [dSC 04]
Primary Circle

Penobscot, k=30 p=40

2-dimensional PCA embedding with eigenpatches.

Penobscot k100 p40
$5\times 5\times 5$ patches
Secondary Circle [dSC 04] Secondary Circle

BRATS k=100 p=40

3-dimensional PCA embedding with eigenpatches.

Primary 2-sphere
$5\times 5\times 5$ patches


The model space $\cal K^d$

Consider $d$-dimensional patches.
We'll consider idealized patches as functions on the disk $D^d$
We'd like to capture primary spheres and secondary circles in a topological model.

Primary Circle

The primary $(d-1)$ sphere [dSC 04]:
$\{(v_\phi^T x) \mid v_\phi\in S^{d-1}\}$

The model space $\cal K^d$

Fix $v_\phi \in S^{d-1}$. A secondary circle [dSC 04]:
$\{\cos(\theta)(v_\phi^T x)^2 + \sin(\theta)(v_\phi^T x)\mid \theta \in [0,2\pi)\}$

Secondary Circle

Note that $v_\phi$ and $-v_\phi$ produce the same secondary circle.

The model space $\cal K^d$

$\mathcal{K}^d = \{ k(v_\phi, \theta; x) = \cos(\theta)(v_\phi^T x)^2 + \sin(\theta)(v_\phi^T x) \mid v_\phi\in S^{d-1}, \theta \in [0,2\pi) \}$
There is an identification $k(-v_\phi, -\theta;x) = k(v_\phi, \theta; x)$
Klein Bottle
$\mathcal{K}^2$ is a Klein bottle [C+ 08]. $\mathcal{K}^3$ is a $3$-dimensional manifold.

The Harris Map

Harris corner/edge detector [HS 88] analyzes eigenvalues of:
$M(x) = \sum_i \Delta(x_i) \Delta(x_i)^T$, $\Delta$ finite difference gradient.
Harris map $h: x\mapsto \text{MaxEigVec}(M(x))$

Harris Map

There is a sign/scale ambiguity for eigenvectors, so range is naturally $\mathbb{R}P^{d-1}$
We also see this ambiguity in our "secondary circles".

The Harris Map

Continuous limit
$M(f(x)) = \int_x dx\, \nabla(f(x))\nabla(f(x))^T$
For $k(v_\phi, \theta; x)\in \mathcal{K}^d$, $\nabla(k(x)) = k'(x) v_\phi$
so $M(k(x))$ is rank-1, and $h(k(v_\phi, \theta; x)) = [v_\phi]$

$\mathcal{K}^d$ is a fiber bundle over $\mathbb{R}P^{d-1}$
(non-trivial because of twist in identification)
The Harris map $h$ is a fibration for $\mathcal{K}^d$
Fibers $h^{-1}([v])$ are secondary circles.

Homology of $\cal K^d$

Because of fibration structure, we can use Leray-Serre spectral sequence to compute homology.
We'll use integer ($\mathbb{Z}$) coefficients, which can be used to obtain field coefficients.

$H_k(\mathcal{K}^d) = \begin{cases} \mathbb{Z} & k=0\\ \mathbb{Z}_2 \oplus \mathbb{Z}_2& 0 < k < d-1, k\, \text{odd}\\ \mathbb{Z} & k = d, d\, \text{odd}\\ \mathbb{Z}\oplus \mathbb{Z}_2 & k = d-1, d\, \text{even}\\ 0 & \text{otherwise} \end{cases}$

$H_\ast(\mathcal{K}^2) = (\mathbb{Z}, \mathbb{Z}\oplus \mathbb{Z}_2, 0)$
$H_\ast(\mathcal{K}^3) = (\mathbb{Z}, \mathbb{Z}_2\oplus \mathbb{Z}_2, 0, \mathbb{Z})$

See [N 20] Theorem 5.2.6 for detailed calculations.

Fibration-Assisted Visualization

3D patches are high dimensional (125 dimensions for 5x5x5).
PCA can visualize some simple structures.
$\mathcal{K}^3$ is a 3-dimensional manifold that captures more.

Visualize data using affine space of $\mathcal{K}^3$

  • $xy$-plane: Stereographic projection of $\mathbb{R}P^2$ base space
  • $z$-axis: $S^1$ fiber cut at $2\pi$

BRATS patches on $\cal K^3$

xy axis is stereographic projection from 3rd spherical coordinate
BRATS PD k=100, p=40: 2-sphere + circle (chord) BRATS PD projection onto $\mathcal{K}^3$

Penobscot patches on $\cal K^3$

xy axis is stereographic projection from 2nd spherical coordinate
Penobscot PD k=100, p=40: secondary circle Penobscot PD projection onto $\mathcal{K}^3$

Review & Future Directions

We've developed a model $\cal K^d$ to explain structures we see in image patch data.

  • Useful for interpreting subsets of the data.
  • Captures topology of high-dimensional data with small number of dimensions.

For additional details, see [N 20] "Parameterized Topological Data Analysis."

Potential applications: 3D compression, texture, neural nets [MSC 08, PC 14, GC 19]

If we have higher-dimensional patches, we could perform similar analyses.
Where would a 4-dimensional image come from?

Other applications where we might use a map:
Evasion [AC 14], Time series, Control systems.

Technical Credits


[N 20] B. Nelson. Parameterized Topological Data Analysis.
PhD Dissertation, Stanford University. 2020. (Link)

[A+ 20] Adams, Bush, Carr, Kassab, Mirth. A torus model for optical flow. 2020.
[AC 09] Adams, Carlsson. On the Nonlinear Statistics of Range Image Patches. 2009.
[AC 14] - Adams, Carlsson. Evasion Paths in Mobile Sensor Networks. 2015.
[BRATS] BRATS data set. https://www.med.upenn.edu/sbia/brats2018/registration.html
[C+ 08] Carlsson, Ishkhanov, de Silva, Zomorodian. On the Local Behavior of Spaces of Natural Images. 2008.
[dSC 04] de Silva, Carlsson. Topological estimation using witness complexes. 2004.
[GC 19] Gabrielsson, Carlsson. Exposition and Interpretation of the Topology of Neural Networks. 2019.
[LPM 02] Lee, Pedersen, Mumford. The Nonlinear Statistics of High-Contrast Patches in Natural Images. 2002.
[MSC 08] Maleki, Shahram, Carlsson. A Near Optimal Coder For Image Geometry With Adaptive Partitioning. 2008.
[PC 14] Perea, Carlsson. A Klein-Bottle-Based Dictionary for Texture Representation. 2014.
[Pen] Penobscot Interpretation Dataset. https://zenodo.org/record/1341774
[T 95] Tanaka. Topological Analysis of Point Singularities in Stimulus Preference Maps of the Primary Visual Cortex. 1995.
[vHvdS 98] van Hateren, van der Schaaf. Independent component filters of natural images compared with simple cells in primary visual cortex. 1998.