Unsupervised action segmentation takes a collection of untrimmed videos of the same task, such as a few hundred people making coffee, and labels every frame with one of $K$ steps, with no annotations. Current methods mostly treat each video as its own clustering problem, or assign frames to a small set of learned step prototypes. They then face a basic question: how do they know that cluster 3 in one video is the same step as cluster 5 in another? This proposal uses an older tool to answer it. Dynamic time warping (DTW) is a dynamic-programming method that finds the best order-preserving, speed-tolerant frame-to-frame matching between two sequences. If you warp one video onto another, the frames it pairs up are a vote that they show the same step. Each pairwise alignment is therefore a weak, local, permutation-free "base clustering" across two videos. Ensemble clustering is the literature on fusing many noisy partitions into one reliable partition, and it supplies the machinery to combine thousands of these votes into a single segmentation that is consistent across the whole collection.
The core claim is this: a sparse graph built only from many pairwise DTW alignments across videos, with each alignment weighted by its reliability, gives consistent step labels across videos. After graph partitioning, those labels should beat both per-video clustering and single-template alignment, especially where appearance cues are unreliable. The claim has a known weak point. DTW assumes the two sequences follow the same order, and real instructional videos permute, repeat, and skip steps. The proposal bets that ensemble aggregation absorbs this: order-violating pairs produce alignments that disagree with the majority and get down-weighted. The experiments are built to show where that bet fails.
What exists and what is missing
Three lines of work attack unsupervised segmentation. They differ in how they impose time structure.
TW-FINCH builds a first-nearest-neighbour merge hierarchy per video, with feature distances multiplied by a penalty on temporal distance. It reports 62.7% mean-over-frames accuracy (MoF) on Breakfast at 0.16 s per video on a CPU. Its authors say it struggles to link identical actions far apart in time, and it has no mechanism for sharing evidence across videos.
ASOT and TOT+TCL assign frames to prototypes with optimal transport. ASOT uses an order-agnostic fused Gromov-Wasserstein term. TOT imposes a fixed-order prior that its authors admit struggles with permutations and missing steps.
ASAL alternates a duration-aware hidden Markov model with a shuffle-discrimination task, but it starts from K-means and inherits its instability.
None of these compares videos to each other elastically. Each one matches frames either to other frames in the same video or to global prototypes.
The DTW line does compare sequences, but it is supervised or anchored to a reference. D3TW makes DTW differentiable and adds a discriminative margin against degenerate alignments, but it needs ordered transcripts. DP-DTW learns class prototypes under DTW, also with transcripts. FinePseudo checks pseudo-labels by soft-DTW "alignability" against a labelled gallery. We reuse two lessons from them. D3TW shows that unconstrained alignments collapse onto low-cost frames. FinePseudo shows that alignment captures phase structure that appearance misses. We drop their need for labels or references.
Ensemble clustering supplies the aggregation method. The median-partition view of Clustering aggregation and the co-occurrence approach to label switching justify turning alignments into pairwise co-membership evidence. Locally Weighted Ensemble Clustering motivates weighting each base partition by local reliability. The bipartite-graph formulation of Ultra-Scalable Spectral Clustering and Ensemble Clustering makes the final partition tractable without an $N^2$ matrix. All of that literature treats items as exchangeable. We apply it to items whose co-membership evidence comes from temporal alignment.
DTW-based clustering of daily routines (Decomposing Activities of Daily Living to Discover Routine Clusters) clusters whole sequences. We instead cluster frames using alignments as evidence. The research file lists no prior work that joins all three directions.
Research Program
For each activity, we take the frame features used by the baselines and temporally downsample them. Each video is paired with its $k$ nearest videos by a cheap global descriptor, starting with $k\approx 10$, so the number of pairs grows linearly with the collection.
Each pair is aligned with a DTW variant that has a "drop" state, so background or idiosyncratic frames can stay unmatched at a fixed cost instead of forcing degenerate many-to-one matches. We also run shapeDTW-style neighbourhood descriptors as a variant for robustness to noise from camera motion. To create the diversity that ensembles need, each pair is aligned under $V$ views: different feature streams, different descriptor window sizes, and a reversed-time pass. The spread of paths across views estimates the "alignment uncertainty" that Temporal Alignment for Video Action Recognition argues is inherent to human movement.
Each alignment path $\pi$ between videos $a$ and $b$ gets a reliability weight $\rho_\pi$. The weight combines the path's length-normalized cost with a cycle-consistency check: for sampled third videos $c$, composing the alignments $a\to c\to b$ should land near the direct path $a\to b$. This weighting is the key ingredient. It is how order-violating pairs lose influence.
The consensus graph has one node per frame $(a,t)$, meaning frame $t$ of video $a$. The weight between frames of different videos is
$$W_{(a,t),(b,s)} = \frac{1}{V}\sum_{v=1}^{V} \rho_{\pi_v}\,\mathbf{1}\big[(t,s)\in \pi_v\big],$$
where $\pi_v$ is the view-$v$ alignment of $a$ and $b$ and $\mathbf{1}[\cdot]$ is 1 when the path matches $t$ with $s$. Within a video, frame $t$ is linked to its temporal neighbours with a small fixed weight, which discourages flicker.
Because every path has only about $|a|+|b|$ entries, $W$ is sparse. We partition it into $K$ clusters with a bipartite spectral method in the style of Huang et al., using segment-level anchor nodes. That produces labels that are already consistent across videos. Optionally, these labels can seed ASOT-style self-training, which tests the separate claim from Gap 5 of the research file that a consensus initialization reduces drift.
Baselines
The naive reference is K-means over all frames of an activity with the same features, followed by global Hungarian matching. It shows what appearance alone gives, and the research file characterizes it as a noisy, flickering starting point.
The strongest per-video competitor is TW-FINCH, rerun with the authors' settings on our identical features. Its reported Breakfast result is 62.7% MoF (TW-FINCH).
The strongest cross-video, prototype-based competitors are ASOT and TOT+TCL. The reported figures are these. ASOT reports 52.9% MoF on YouTube Instructions and 37.4 F1 on 50Salads. TOT+TCL reports 45.3% MoF and 32.9 F1 on YouTube Instructions, 48.2 F1 on 50Salads at the eval granularity, and 53.4 F1 and 58.1% MoF on Desktop Assembly. The research file quotes no ASOT number on Breakfast or Desktop Assembly, so on those benchmarks we rely on our own reruns.
All methods receive the same features and the same $K$. They also get the same hyperparameter budget, a fixed number of configurations chosen on a held-out activity rather than on test activities.
Reported numbers can mix per-video and activity-level Hungarian matching. We therefore rerun every baseline under both protocols and compare only within a protocol.
The ablations target the key ingredients. "Ensemble without DTW" is a co-association consensus over many seeded K-means and TW-FINCH runs; it isolates whether alignment matters. "DTW without ensemble" aligns every video to one medoid or DTW-barycentre template and labels frames by the template position they match; it isolates whether aggregating many pairs matters. "Unweighted consensus" sets $\rho_\pi=1$; it isolates the reliability weighting. "Rigid alignment" replaces DTW with uniform rescaling.
Beating the field means two things. The method must exceed the best rerun baseline on activity-level MoF and F1 on at least three of the four benchmarks. The margins over the two single-ingredient ablations must also exceed seed-to-seed variation.
Why not just…?
Why not just ensemble many runs of an existing method? Seeded runs of TW-FINCH or ASOT, fused by co-association, are a real threat and an obvious first thing to try. Their weakness is that they share the same features and the same within-video view of time. Their errors are therefore correlated, the case where the ensemble literature warns that consensus reinforces bias rather than removing it. They also never produce direct evidence that two frames in different videos are the same step. The "ensemble without DTW" ablation tests this head-on. If it matches the full method, the alignment is not paying for its cost, and we would report that outcome as the result.
Why not just align everything to one template? A single reference, found by medoid selection or averaging, is cheaper and is what DP-DTW-style prototypes amount to without labels. But one template imposes one order on every video, the same weakness TOT+TCL concedes. Its errors also do not average out. The "DTW without ensemble" ablation, stratified by how much step order varies within each activity, should show the gap growing as order variability grows. If it does not grow, the pairwise ensemble is unnecessary.
Why not just use order-agnostic optimal transport like ASOT? ASOT does not assume order, and on activities with heavy permutation or repetition it may well win. Our method is monotonic within each pair and relies on cycle-consistency weighting to discard inconsistent pairs. We will report results per activity against a measure of order variability computed from the ground truth. We predict our method wins on activities with mostly consistent order and loses or ties on heavily permuted ones. If that crossover happens at low variability, the claim is weak, and a combination using ASOT with our consensus as initialization becomes the recommended pipeline.
Why not just rescale videos to a fixed length? DP-DTW reports that selecting frames by DTW alignment reaches 62.5% accuracy against 40.8% for uniform sampling. That suggests rigid matching confuses phases. The "rigid alignment" ablation checks whether the same holds for segmentation.
Proposed Experiments
We evaluate on Breakfast, YouTube Instructions, 50Salads (eval and mid granularities), and Desktop Assembly, using MoF, F1, and edit score under both matching protocols. Hollywood Extended serves as a stress test for scene cuts and camera motion. The decisive checks are these. First, the full method beats TW-FINCH and ASOT on activity-level MoF. Second, it beats both single-ingredient ablations. Third, removing the reliability weighting hurts most on high-permutation activities, which would show that the weighting absorbs order violations. Fourth, recurring actions far apart in time are linked more often than by TW-FINCH, measured as recall of same-label pairs more than 60 seconds apart. Fifth, seeding ASOT with our consensus reduces its variance across seeds.
We also report cost: wall-clock time per activity as a function of $k$ and $V$, against TW-FINCH's 0.16 s per video. This lets a reader judge whether any accuracy gain is worth the quadratic cost of each DTW pair.
References
- Temporally-Weighted Hierarchical Clustering for Unsupervised Action Segmentation
- Temporally Consistent Unbalanced Optimal Transport for Unsupervised Action Segmentation
- Unsupervised Action Segmentation by Joint Representation Learning and Online Clustering
- Action Shuffle Alternating Learning for Unsupervised Action Segmentation
- D3TW: Discriminative Differentiable Dynamic Time Warping for Weakly Supervised Action Alignment and Segmentation
- Learning Discriminative Prototypes With Dynamic Time Warping
- FinePseudo: Improving Pseudo-labelling Through Temporal-Alignablity for Semi-supervised Fine-Grained Action Recognition
- Clustering aggregation
- Locally Weighted Ensemble Clustering
- Ultra-Scalable Spectral Clustering and Ensemble Clustering
- Decomposing Activities of Daily Living to Discover Routine Clusters
- shapeDTW: shape Dynamic Time Warping
- Learning Temporal Alignment Uncertainty for Efficient Event Detection