Timestamp-Supervised Action Segmentation from the Perspective of Clustering

1 Introduction

Recognizing and segmenting actions from long untrimmed videos is a challenging task. Action segmentation aims to classify actions for all frames in the video, resulting in several action segments. There have been many fully supervised approaches achieving good results. These approaches mainly use TCN [Farha and Gall, 2019; Li et al., 2020] or Transformer [Du et al., 2022] to model the long-term dependencies between frames. However, obtaining label sequences for long videos is costly. Researchers have proposed several weaker levels of supervision, e.g., set supervision [Richard et al., 2018a], transcript supervision [Kuehne et al., 2017], and timestamp supervision [Li et al., 2021]. Among them, timestamp supervision has the most promising performance.

As shown in Figure 1, timestamp supervision only labels one frame in each action segment. Compared to other weakly supervised setups, timestamp supervision provides temporal information that is crucial for action segmentation and therefore has better performance. However, it is surprising that timestamped supervision sometimes outperforms the fully supervised setup. The reason is that the boundaries of action segments are usually ambiguous, which might result in inconsistencies between labels labeled by different annotators under full supervision. For example, the frames near the boundary between action 'add oil' and action 'cut cheese' in Figure 1, can be classified as either action 'add oil' or action 'cut cheese'. We call the intervals close to the boundaries ambiguous intervals. In contrast, timestamp supervision usually labels the representative frame of an action, such as a frame near the middle of the action segment. The most popular method [Li et al., 2021] iteratively generates full pseudo-label sequences by detecting action changes, as shown in Figure 2 (a). However, this might lead to error accumulations, i.e. training with wrong pseudo-labels of ambiguous intervals will cause the model to deviate further from expectations. Therefore, we do not expect to generate pseudolabels for frames in ambiguous intervals at the beginning, as shown in Figure 2 (b). As the training progresses, we can gradually assign pseudo-labels with high certainty to ambiguous intervals based on the model outputs.

∗Corresponding author.

濫濝濨濜濣濩濨澔

濕濡濖濝濛濩濣濩濧澔濝濢濨濙濦濪濕濠濧

濕濡濖濝濛濩濣濩濧澔濝濢濨濙濦濪濕濠濧

We implement this idea from a clustering perspective by considering each action segment as a cluster. Our framework consists of two main parts, namely pseudo-label ensembling (PLE) and iterative clustering (IC). First, PLE generates high-quality pseudo-label sequences with ambiguous intervals in Figure 2 (b). Specifically, we utilize three different clustering algorithms to generate three full pseudolabel sequences for each video. For each frame, if the three algorithms generate inconsistent pseudo-labels, the frame belongs to the ambiguous interval. Frames in the ambiguous intervals have no pseudo-labels and therefore do not affect training. Afterward, IC gradually assigns the frames in ambiguous intervals to left or right action segments by feature clustering based on their distance from the surrounding cluster centers. During the iterative training, the model can generate better features, based on which propagating pseudo-labels to the ambiguous interval results in more consistent and accurate supervision. As this process involves feature clustering, we further introduce the clustering loss commonly used in deep clustering to help feature learning and clustering.

In summary, our main contributions are twofold: (1) We design a framework for timestamp-supervised action from the perspective of clustering. The framework mainly contains two novel algorithms, pseudo-label ensembling (PLE) and iterative clustering (IC), to address the negative impact of ambiguous intervals on training. Besides, we introduce the clustering loss. (2) Extensive experiments and ablation studies demonstrate the effectiveness of our framework and illustrate the impact of each component.

2 RelatedWork

Fully Supervised Action Segmentation. In the fully supervised setting, all the frames are labeled during training. To model the temporal dynamics, some researchers utilize graphical models and sequential models such as HMM [Tang et al., 2012; Kuehne et al., 2016], RNN [Singh et al., 2016]. With the development of deep learning, temporal convolutional networks (TCNs) have been successful due to their powerful temporal modeling ability [Lea et al., 2017; Farha and Gall, 2019; Li et al., 2020; Wang et al., 2020; Ishikawa et al., 2021]. Recently, ASFormer [Yi et al., 2021] and TUT [Du et al., 2022] have designed transformer-based architectures that outperform TCN-based models. In contrast

濫濝濨濜澔

to these methods, our framework is model agnostic and relies on timestamp supervision instead of full supervision.

Weakly Supervised Action Segmentation. Many works have attempted to explore weaker levels of supervision to reduce annotation costs. Transcript supervision provides ordered action lists. Some researchers introduce connectionist temporal classification [Huang et al., 2016], dynamic time warping [Chang et al., 2019], and energy-based learning [Li et al., 2019] to align the frame-wise outputs to transcripts. Other approaches utilize the Viterbi algorithm on the output probabilities to generate pseudo-label sequences [Kuehne et al., 2017; Richard et al., 2018b]. Another form of supervision, set supervision [Richard et al., 2018a; Fayyaz and Gall, 2020; Li and Todorovic, 2021], provides only the unordered action sets. However, these weakly supervised methods perform considerably worse than fully supervised approaches.

Timestamp-Supervised Action Segmentation. In action segmentation, Li et al. [2021] firstly proposed a timestampsupervised framework that detected action changes by the energy function and generated full pseudo-label sequences to train the segmentation model. Based on it, Khan et al. [2022] used learnable GNN instead of the energy function to obtain action boundaries, achieving better performance. UVAST [Behrmann et al., 2022] extended the K-medoids clustering algorithm to yield pseudo-labels for all frames. Rahaman et al. [2022] utilized the Expectation-Maximization algorithm to solve this problem. However, the loss function is still calculated on all frames to train the model during the Mstep. Different from these methods, we iteratively generate pseudo-label sequences with ambiguous intervals, rather than generating pseudo-labels for all frames.

Weakly Supervised Learning. When faced with the challenge of training samples lacking labels, one common approach is to assign pseudo-labels to all unlabeled samples and use them to train the model [Lee and others, 2013]. However, we do not generate pseudo-labels for all unlabeled frames, considering the presence of ambiguous intervals. Iscen et al. [2019] constructed a similarity graph among samples based on features to propagate labels, while we propagate labels by iterative clustering. There are also some works learning with coarse-grained labels [Qiang et al., 2023].

3 Methodology

3.1 ProblemDefinition

Given an input long video which is represented by a sequence of frame-wise visual features: X = [x1, · · · , xT ], where xt is the visual feature of the t-th frame. Our goal is to predict the action class label of each frame [ˆ c1, · · · , ˆ cT ]. Under timestamp supervision, only a single frame in each action segment is annotated. For a video having N action segments, timestamp supervision provides a set of annotated timestamps {cτ1 , · · · , cτN }, where the τn-th frame is in the n-th segment.

3.2 Overview

As shown in Figure 3, we design a novel framework for timestamp-supervised action segmentation, which contains pseudo-label ensembling (PLE) and iterative clustering (IC).

Given the visual features and timestamp labels of each video, PLE combines three different clustering algorithms to generate pseudo-label sequences, where the frames in ambiguous intervals have no pseudo-labels while other frames have. We regard PLE as a pre-processing step since it relies on only the visual features of frames. During the first training epoch in IC, we utilize the pseudo-label sequences generated by PLE to train the segmentation model. After training, we cluster the output features of the model. Specifically, we consider frames with the same pseudo-label to be in the same cluster, which means that an action segment is a cluster. The center vector of each cluster can be calculated based on the output features of all frames within the action segment. We classify the frames within ambiguous intervals according to the distances between their output features and surrounding cluster centers, which can propagate pseudo-labels and narrow down the ambiguous intervals. During the next training epoch, the model is trained by the updated pseudo-label sequences. We iterate this process for S epochs. The additional clustering loss gathers features of the same class. We describe PLE, IC, and the clustering loss in detail in the following subsections.

3.3 Pseudo-Label Ensembling

We find that action segmentation under timestamp supervision can be viewed as a special clustering problem. For a video containing N action segments, we can cluster the features of frames into N clusters. Since each timestamp will belong to a certain cluster, we label all frames in that cluster with the action label of the timestamp. In PLE, we ensemble three different clustering algorithms, including energy function [Li et al., 2021], constrained k-medoids [Behrmann et al., 2022], and temporal AGNES we propose.

Energy Function. Given frame-wise visual features and labeled timestamps in a video, the energy function aims to find action changes {b2, b3, ..., bN} by minimizing the variations of the features within each of two consecutive segments, as shown in Figure 2 (a).

Constrained K-medoids. Similar to the energy function, the constrained k-medoids algorithm also aims to find the temporal boundaries of each segment such that the accumulative distance of each cluster to the current cluster center is minimized. Different from the typical k-medoids algorithm, it forces the clusters to be temporally continuous.

Temporal AGNES. AGNES(AgglomerativeNesting) [Han and Kamber, 2006] is a bottom-up hierarchical clustering algorithm: each frame starts in its own cluster, and clusters are successively merged together. We propose temporal AGNES, which only merges temporally adjacent clusters. The clustering algorithm stops when the number of clusters equals the number of timestamps. The detailed steps of the temporal AGNES algorithm are shown in Appendix A.

PLE. For each video sample, we can generate three different full pseudo-label sequences by the above algorithms. The frames within ambiguous intervals are semantically ambiguous, and different clustering algorithms might assign different action labels to these frames. Inspired by ensembling learning [Dietterich, 2002], we take the intersection of these three pseudo-label sequences. If the three algorithms assign the same pseudo-label to a frame, then that frame is labeled as this action class; otherwise, the frame belongs to the ambiguous interval and has no pseudo-label. So we can obtain a pseudo-label sequence with ambiguous intervals, as shown in Figure 2 (b). The pseudo-label sequence generated by PLE achieves a trade-off between label rate and accuracy. Compared to the timestamp labels, it has a higher label rate. Compared to the full pseudo-label sequence generated by any clustering algorithm, it has a higher accuracy. More analysis can be found in Figure 4 and Table 4.

3.4 Iterative Clustering

From the perspective of clustering, IC iteratively generates pseudo-labels for frames within ambiguous intervals to up-

Algorithm 1 The iterative clustering algorithm

Input: visual features: [x1, x2, ..., xT ], pseudo-label sequence: [ˆ c1, ˆ c2, ..., ˆ cT ], timestamp supervision: {cτ1 , cτ2 , ..., cτN }, the number of epochs S, initial segmentation model: M Output: segmentation model after iterative training: M

• 1: [˜c1, ˜c2, ..., ˜cT ] ← [ˆ c1, ˆ c2, ..., ˆ cT ]
• 2: Obtain the sets of left and right action segment boundaries from the pseudo-label sequence: {l1, l2, ..., lN} and {r1, r2, ..., rN}
• 3: for epoch = 1, 2, ..., S do
• 4: [h1, ..., hT ] ← M([x1, ..., xT ])
• 5: for n = 1, 2, ..., N do
• 6: mn ← 1 rn-ln ∑rn t=ln ht
• 7: end for

8:

for n = 1, 2, ..., N - 1 do

• 9: while rn < ln+1 and d(hrn ,mn) < d(hrn ,mn+1) do 10: rn ← rn + 1
• 11: end while

• 13: ln+1 ← ln+1 - 1
• 14: end while
• 15: ln+1 ← ln+1 + 1
• 16: end for

17:

for n = 1, 2, ..., N do

• 19: end for
• 20: Train the model for one epoch with the pseudo-label sequence [˜c1, ..., ˜cT ], and obtain the new segmentation model Mafter parameter update

21: end for

date the pseudo-label sequences for training the segmentation model M. We clarify some notations before introducing IC in detail. xt and ht are the visual feature and output feature of the t-th frame, respectively. As shown in Figure 2, ln and rn are the left and right boundaries of the n-th action segment in the pseudo-label sequence. mn is the mean vector of all the output features in the n-th action segment, which is equivalent to the cluster center vector of the n-th cluster. Function d(·, ·) calculates the Euclidean distance between the output features of two frames.

The algorithm 1 summarizes the steps of our iterative clustering algorithm. Steps 4 to 20 describe the procedure for each epoch. First, the visual features of the video frames are fed into the segmentation model to generate output features (step 4). The center vector of each action cluster is calculated based on output features and the pseudo-label sequences from the previous epoch (steps 5-7). Afterward, for every ambiguous interval, we first iterate through each frame in the ambiguous interval from left to right and compare the distance between that frame and the center vectors of the adjacent left and right action clusters (steps 9-11). If it is closer to the center vector of the left cluster, the frame belongs to the left action segment. We stop the iteration when the frame is closer to the center vector of the right cluster, which means that the frame either belongs to the right action segment or remains in the ambiguous interval. This iterative process is pseudo-label propagation, which propagates the pseudo-labels from left to right to the frames in the ambiguous interval. Subsequently, we propagate the pseudo-labels from right to left (steps 12-

15), which is symmetric to the above process. After finishing pseudo-label propagation, the range of ambiguous intervals is reduced and the resulting supervision signal is more intensive. Finally, the segmentation model is trained by the new pseudo-label sequence (step 20).

3.5 Loss Function

During the training phase, we combine four different losses.

Classification Loss. We use a cross-entropy loss between the predicted action probabilities and the corresponding generated pseudo-labels:

where yt(cτn ) is the predicted probability that xt belongs to the cτn -th class, and the denominator of the former term, ∑Nn=1 (rn - ln), represents the total number of frames with pseudo-labels that contribute to the loss. It is worth noting that the frames within the ambiguous intervals have no pseudo-labels and are not calculated for cross-entropy loss.

Smoothing Loss. We use the truncated mean squared error [Farha and Gall, 2019] as the smoothing loss to improve over-segmentation errors:

(2)

where yt(c) is the predicted probability that xt belongs to the c-th class, and θ = 4 is a pre-set threshold. Besides, gradients are not calculated w.r.t. yt-1(c).

Confidence Loss. The confidence loss [Li et al., 2021] is specifically designed for action segmentation under timestamp supervision:

where 2(τN - τ1) is the number of frames that contributed to the loss. The loss encourages the model to predict higher probabilities for low-confident intervals surrounded by highconfident intervals while suppressing those high-confident regions that are far from the labeled timestamp.

Clustering Loss. To assist feature learning and clustering, we introduce a clustering loss commonly used in deep clustering, to distribute output features in the same action segment more compactly. IC aims to cluster similar features together and thus propagates pseudo-labels to frames within ambiguous intervals. As IC is similar to K-means clustering, we introduce the clustering loss [Yang et al., 2017] commonly used in deep clustering into action segmentation for the first time. It can be formulated as:

where mn = 1 rn-ln ∑rn-1 t=ln ht is the center vector of the n-th cluster. The loss encourages the high-level features of frames in the same cluster to be more compact so that the model is more discriminative for frames in different action segments.

The overall loss function during the training phase is a weighted sum of the above four losses:

where λ, β and γ are hyper-parameters.

4 Experiments

4.1 Datasets and EvaluationMetrics

We empirically evaluate the performance of the proposed framwork on the following three public datasets. The 50Salads dataset [Stein and McKenna, 2013] contains 50 top-view videos with 17 action classes. On average, each video lasts for about 6.4 minutes and has about 20 action instances. The GTEA dataset [Fathi et al., 2011] consists of 28 egocentric videos with 11 action classes. On average, there are about 20 action instances in each video. The Breakfast dataset [Kuehne et al., 2014] contains 1,712 third-person view videos with 48 action classes. On average, each video is composed of about 6 action instances. We perform fourfold cross-validation on the GTEA and Breakfast datasets, and five-fold cross-validation on the 50Salads dataset. For evaluation, we report the average of all the splits.

We also use the segmental F1 score at overlapping thresholds 10%, 25%, 50% (F1@10,25,50), segmental edit distance (Edit) measuring the difference between predicted segment paths and ground-truth segment paths, and frame-wise accuracy (Acc) as evaluation metrics.

4.2 Implementation Details

On all datasets, we represent each video as a sequence of visual features. We employ the I3D [Carreira and Zisserman, 2017] features provided in [Farha and Gall, 2019] as inputs. We utilize the same segmentation model following [Li et al., 2021], which has two parallel stages for the first stage with kernel sizes 3 and 5 and passes the sum of both outputs to the next stages. We train the model for 70 epochs with Adam optimizer [Kingma and Ba, 2014]. Similar to [Li et al., 2021], in the first 50 epochs, we only use the annotated timestamps to train to find a good initialization. Subsequently, we apply the IC algorithm to train for 20 epochs. We use the learning rate 0.0001 for Breakfast and 0.0005 for GTEA and 50Salads. We set λ, β, γ to 0.15, 0.075 and 0.15 respectively.

4.3 Comparison with the State-of-the-art

We compare our method with recent state-of-the-art approaches, including four fully supervised methods (MSTCN [Farha and Gall, 2019], MS-TCN++ [Li et al., 2020], BCN [Wang et al., 2020], ASRF [Ishikawa et al., 2021]), two transcript-supervised methods (NN-Viterbi [Richard et al., 2018b], CDFL [Li et al., 2019]), two set-supervised methods (SCT [Fayyaz and Gall, 2020], ACV [Li and Todorovic, 2021]), and two timestamp-supervised methods (Li et al. [2021], GCN [Khan et al., 2022]).

Results for three datasets are shown in Table 1, 2, 3. The best results are highlighted in bold. Under timestamp supervision, our method achieves state-of-the-art on all datasets. Besides, we find that our timestamp-supervised approach significantly outperforms all the set-supervised and transcriptsupervised methods by a large margin. Furthermore, our method is comparable to or even better than some fully supervised models such as MS-TCN on the 50Salads and Breakfast datasets. In particular, on the largest Breakfast dataset, the performance is even comparable to one of the most advanced fully supervised methods, BCN.

4.4 Ablation Study

Impact of Pseudo-Label Ensembling. Given timestamp supervision and frame-wise visual features, we generate pseudo-labels with different methods and evaluate them with label accuracy and label rate in Table 4. We find that our temporal AGNES algorithm outperforms the other two. In the penultimate row, we can obtain pseudo-labels with both a high label rate and high accuracy when we ensembling these three algorithms, i.e., PLE. In practice, we further divide the visual features into RGB features and optical flow features, and ensemble these two types of features separately to get the final results, which are listed in the last row. The final pseudo-labels achieve the highest accuracy and over 50% label rate. We visualize the generated pseudo-label sequences in Figure 4. The provided timestamp supervision signal is too sparse because the label rate is only 0.4%. We can generate full pseudo-label sequences by any clustering algorithm, but there are too many wrong labels. PLE makes a trade-off between the label rate and accuracy.

Ablations about Iterative Clustering. Iterative clustering (IC) is an important part of our framework for which we conduct detailed ablation studies. We use pseudo-label sequences updated by IC to train the model. We can also replace IC with other methods to generate pseudo-labels for training. In Table 5, we first generate pseudo-label sequences with and without ambiguous intervals by PLE and Temporal AGNES to train the model directly. The pseudo-label sequences depend only on the visual features and do not change during training. Therefore, these two methods have the worst performance. The methods in the last three rows of the table all iteratively update the pseudo-labels based on high-level features during training. Li et al. [2021] use the energy function to generate full pseudo-label sequences. The modified version of IC, called IC (Li et al.), uses the energy function to generate pseudo-labels for the frames within ambiguous intervals, which also yields full pseudo-label sequences. IC (Ours) generates pseudo-label sequences with ambiguous intervals to train the model and achieves the best results, which illustrates the importance of ambiguous intervals. As the training epoch increases, Figure 5 shows the variation of accuracy and label rate of pseudo-labels generated by energy function and IC. The accuracy of IC is always higher than that of Li et al., and the label rate of IC is increasing, indicating that the range of ambiguous intervals is decreasing.

Effect of ambiguous intervals. To further explore the effect of ambiguous intervals, we remove the labels of ambiguous intervals from these ground-truth label sequences under full supervision. Then we use the resulting label sequences with a certain unlabeled rate to train the model. Since the range of ambiguous intervals is decreasing during IC, we can record multiple sets of ambiguous intervals, which correspond to multiple label sequences with different unlabeled rates. As shown in Figure 6, the frames within the ambiguous intervals generated by PLE take up 48.1% of the total frames. So we can use the label sequences with an unlabeled rate of 48.1% to train the model. Similarly, the unlabeled rates of 5.7%, 0.8% and 0.09% represent the ambiguous intervals when IC runs to three intermediate epochs. The unlabeled rate of 0% represents full supervision. The model performs best when the unlabeled rate is 0.8%, which indicates that about 0.8% labels in ground-truth label sequences are ambiguous and useless. We should train the model without these labels instead of using all the labels. Our IC does not use the information in the ground truth, but still achieves comparable results to the setting of unlabeled rate 0.8% and outperforms the fully supervised setting.

Impact of the Clustering Loss. To verify the effectiveness of our proposed clustering loss, we train the segmentation model with and without it. The metrics for both settings on two datasets are presented in Table 6. Additionally, we show the TSNE visualization of output features in Figure 7. We observe that the model's output features become more discriminative with the help of clustering loss, leading to improvements in all metrics.

5 Conclusion

From the perspective of clustering, we propose pseudo-label ensembling and iterative clustering and introduce clustering loss to compose a framework for timestamp-supervised action segmentation. For the first time, we consider the ambiguity of action segment boundaries. Instead of directly generating pseudo-labels for all frames, our approach generates labels only for semantically explicit frames, which avoids the negative impact of inconsistent labels for ambiguous intervals at action segment boundaries. Experiments verify the effectiveness of our framework.

A Temporal AGNES

Algorithm 2 summarizes the steps of our clustering algorithm, which we call the temporal AGNES algorithm. Function dist(·, ·) calculates the Euclidean distance between visual features of two frames, and matrix D contains all the distances between any pair of frames. In contrast to the original AGNES algorithm, we make the following three changes. First, different timestamps should have distinct labels and cannot be merged. Therefore, we set the distance between different timestamp frame features to infinity to prevent them from being merged (step 9). Second, we only merge temporally adjacent clusters. Therefore, we only record and delete the boundaries of segments when merging two temporally contiguous clusters (step 3 and step 15). Third, since each action segment in the video contains a single timestamp, the algorithm stops when the number of clusters equals the number of timestamps (step 11). We utilize average linkage as the linkage criterion when merging clusters, i.e., the distance between a pair of clusters is determined by the average distance between frames (step 13 and step 14).

Algorithm 2 Temporal AGNES clustering algorithm

Input: visual features: [x1, x2, ..., xT ], timestamp supervision: {cτ1 , cτ2 , ..., cτN } Output: pseudo-label sequence: [ˆ c1, ˆ c2, ..., ˆ cT ] 1: q ← T 2: for i = 1, 2, ..., T do 3: bi, di ← i, dist(xi, xi+1) 4: for j = 1, 2, ..., T do 5: D[i, j] = dist(xi, xj) 6: end for 7: end for 8: for n = 1, 2, ...,N -1 do 9: D[τn, τn+1] ←∞ 10: end for 11: while q > N do 12: i = argminj dj 13: di-1 ← di-1∗(bi-bi-1)∗(bi+1-bi)+∑bi j=bi-1 ∑bi+2 k=bi+1 D[j,k] (bi-bi-1)∗(bi+2-bi) 14: di ← di∗(bi+2-bi+1)∗(bi+3-bi+2)+∑bi+1 j=bi ∑bi+3 k=bi+2 D[j,k] (bi+3-bi+2)∗(bi+2-bi) 15: delete bi+1, di+1 16: q ← q -1 17: end while 18: for n = 1, 2, ...,N do 19: [ˆ cbn , ˆ cbn+1, ..., ˆ cbn+1-1] ← [cτn , cτn , ..., cτn ] 20: end for

Acknowledgments

This work was supported by the 2022 Special Research Assistant Grant project E3YD5901.