AMS Special Session on Applied Topology

January 8, 2021

bnels.github.io/jmm2021

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

- Image Patch Data
- Data Exploration
- Fibration Model
- Fibration-Assisted Visualization

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.

- [LPM 02] find annulus when investigating patch statistics
- Preliminary topological investigations in [dSC 04]
- Klein bottle model proposed in [C+ 08]
- Compression [MSC 08] Texture recognition [PC 14] Neural nets [GC 19]
- Range images [AC 09] Flow [A+ 20]

Topology in the visual cortex

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

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]

Procedure used in [LPM 02]

- Sample random patches
- Take top 20% by contrast norm
- Mean-center and normalize contrast

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

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

We'll visualize data using principal component embeddings.

Eigenpatches = principal components interpreted as patch.

Eigenpatches = principal components interpreted as patch.

2-dimensional PCA embedding with eigenpatches.

$7\times 7$ patches

Primary circle [dSC 04]

2-dimensional PCA embedding with eigenpatches.

PCA 1

$5\times 5\times 5$ patches

PCA 2

PCA 1

PCA 3
Primary 2-sphere

$5\times 5\times 5$ patches

$5\times 5\times 5$ patches

PCA 2

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.

The primary $(d-1)$ sphere [dSC 04]:

$\{(v_\phi^T x) \mid v_\phi\in S^{d-1}\}$

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)\}$

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

$\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)$

$\mathcal{K}^2$ is a Klein bottle [C+ 08]. $\mathcal{K}^3$ is a $3$-dimensional manifold.

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))$

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".

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.

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_\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.

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$

xy axis is stereographic projection from 3rd spherical coordinate

k=100, p=40: 2-sphere + circle (chord)
projection onto $\mathcal{K}^3$

xy axis is stereographic projection from 2nd spherical coordinate

k=100, p=40: secondary circle
projection onto $\mathcal{K}^3$

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.

[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.

[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.