Zigvid

From Frames to Features: Scalable Zigzag Persistence for Binary Video

David Lanners

Preprint · 2026

[arXiv] · [code] · [read more] · [demo]

This paper develops a state-of-the-art method for tracking topological features in binary video using zigzag persistence, outperforming existing approaches by orders of magnitude. The computation is embarrassingly parallel across video frames, giving the method excellent scaling properties. In practice, this makes it possible to track the topology of 4K video in real time on consumer hardware.

A binary video can be viewed as a sequence of frames

\[I_1, I_2, \ldots, I_T,\]

whose topology changes over time. We want to track features such as connected components and holes as they appear, disappear, merge, and split.

The difficulty is that consecutive frames are generally not related by canonical maps such as inclusion maps, so ordinary persistent homology does not apply directly. To fix this, we insert an interpolation frame between each pair of consecutive frames. This can be chosen to be either their union or their intersection. For the union construction, for example, we obtain

\[I_1 \hookrightarrow I_1 \vee I_2 \hookleftarrow I_2 \hookrightarrow I_2 \vee I_3 \hookleftarrow I_3 \hookrightarrow \cdots,\]

where \(I_i \vee I_{i+1}\) denotes the pixelwise maximum, equivalently the union of the two binary images.

To turn each binary image into a topological space, we choose either 4-connectivity or 8-connectivity on the pixel grid. Applying homology then associates a vector space to every frame and a linear map to every inclusion,

\[H_k(I_1) \to H_k(I_1 \vee I_2) \leftarrow H_k(I_2) \to H_k(I_2 \vee I_3) \leftarrow \cdots.\]

This is a zigzag persistence module. These are a generalisation of ordinary persistence modules, but the arrows are allowed to point in both directions. This extra flexibility is exactly what makes zigzag persistence well suited to time-dependent data such as video, where objects may both enter and leave from one frame to the next.

Just as in ordinary persistent homology, a zigzag module decomposes into interval modules. Its associated barcode therefore records the lifetimes of topological features through the video.

Exploiting low-dimensional structure

A general-purpose approach now represents each binary frame by a cubical complex and computes the induced maps on homology. However, at high resolutions the resulting complexes become enormous: a single 4K frame already contains millions of pixels, and a video may consist of thousands of such frames. Applying generic zigzag-persistence algorithms directly to these complexes therefore quickly becomes computationally prohibitive.

The key observation of this paper is that, in two dimensions, we do not need to retain all of this information. For \(H_0\), only the connected components of each frame and the way they map between consecutive frames matter. We can therefore collapse every frame to its connected components and record their evolution in a much smaller graph. These graphs encoding the connected components dynamics are called formigrams and an example can be seen above.

For \(H_1\), we use planar Alexander duality. Holes in a binary foreground image correspond to bounded connected components of its complement. Computing one-dimensional homology can therefore be reduced to another connected-component problem. As a result, both \(H_0\) and \(H_1\) can be handled using the same pipeline.

Complexity and scalability

Constructing the formigrams is linear in the number of pixels processed. Once the formigrams are built, the (decorated) zigzag barcode can be recovered using a near-linear \(n\log(n)\) zigzag decomposition algorithm by Dey ann Hou.

The computation of the graphs is also naturally parallel: connected-component calculations for different frames and frame pairs can be carried out independently before the resulting information is assembled into the formigrams.

Performance Comparison

Compared with a general-purpose cubical-complex pipeline [ImageZigZag], the method is faster by several orders of magnitude, with the speedup increasing as the image resolution grows. At \(180\times180\) pixels, the benchmark shows a speedup of nearly \(7000\times\).

Parallel Scaling

The connected-component computations are embarrassingly parallel across frames and interpolation frames, so the method benefits strongly from additional CPU threads. On a 30-second 4K video at 30 fps, the runtime drops from about 125 seconds on one thread to about 21 seconds on nine threads.

Zigvid

The method is implemented in [Zigvid], a Rust library with Python bindings for computing decorated \(H_0\) and \(H_1\) zigzag persistence barcodes of binary video.

Zigvid supports:

• \(4\)-connectivity and \(8\)-connectivity,
• union and intersection zigzags,
• \(H_0\) and \(H_1\),
• decorated birth, death, merge, and split information,
• multithreaded computation.