OPEL: Optimal Transport Guided ProcedurE Learning

Thanks for your encouraging feedback. Please find the answers to your specific comments:

Explanation of priors: The concept of the Optimality Prior is crucial when dealing with video alignment, especially in challenging scenarios. When two videos are perfectly aligned (case 1 of Fig. 2B), the $\hat{T}$ becomes strictly diagonal. However, the real value of the optimality prior emerges in more complex situations, such as speed variation, non-monotonicity, etc.

Speed variation: Consider the scenario in Fig. 2B, case 3: video 1, shown at the top, takes two frames to complete task A, while video 2, displayed on the left, completes task A in one frame. Here, both frames 1 and 2 from video 1 should be aligned with frame 1 of video 2. The optimality prior enables this alignment, as depicted by the blue curve in Fig. 2C and explained by Eqn. 2. The procedure involves finding, for each frame $i$ from video 2, the closest matching frame from video 1 based on feature similarity, even if the corresponding frame $j$ from video 1 has a different index. In Fig. 2C, for example, frame $j$ from video 1 has the highest likelihood of aligning with frame $i$ from video 2, with the assignment likelihood decaying exponentially for frames further away from $j$.

The optimality prior also addresses non-monotonic cases (Fig. 2B, case 4). Here, though the first two frames from video 1 align with those in video 2, the third frame of video 1 reverts to an earlier task A. To correctly align this frame, it must be matched with its closest counterpart in video 2, which is frame 1 in this case. The optimality prior facilitates this by aligning non-monotonic frames that share a higher feature-wise match (similar to Fig. 2C).

However, relying solely on the optimality prior is insufficient because it overlooks the temporal ordering inherent in videos, which is crucial for maintaining temporal coherence. As discussed in the regularization section on page 4 of our paper and illustrated in Fig. R4 (rebuttal pdf), optimizing only for optimality can result in temporal incoherence. Proper alignment should account for the temporal relationship between frames, ensuring that corresponding frames in one sequence align closely with adjacent frames in the other.

This necessity leads to a second critical factor: the Temporal Prior. Unlike the optimality prior, which seeks the best feature match regardless of temporal distance, the temporal prior promotes alignment between frames that are temporally adjacent, thereby preserving the overall temporal coherence. Similar coherence based concepts have been utilized in other temporal alignment works, such as TCC [a], and contrastive regularization [b]. This temporal prior encourages the alignment matrix to exhibit peak values along the diagonal, with diminishing values away from the diagonal; we model this with a Laplace distribution (Eqn. 3 and the red curve in Fig. 2C).

Essentially, there are 2 factors in play- (i) optimality which tries to find the best match between frames irrespective of their temporal distance (which may result in temporally incoherent alignment), (ii) the temporal factor which promotes transport between nearby frames without considering their feature matching. We hypothesize (and later validate with results) that the optimal solution requires a balance between both, and therefore propose to merge these two priors addressing the above factors, as expressed in Eqn. 4. This combined prior ensures accurate alignment between videos considering all the factors, as further illustrated in Fig. 2D and supported by the results in Table 5 of the main paper.

When the starting of actions is different (case 2, Fig. 2B), video 2 has a background frame to start when video 1 starts doing task A. As mentioned in page 5 of our paper, we introduce a 'virtual frame' to handle such cases. Even in this case, the combined prior comes into play as we assign any frame to the virtual frame if the likelihood of that frame aligning with any other task-related frames from the other video falls below a predefined threshold. This phenomenon is also illustrated in Fig. 4(B) of the main paper.

Laplace distribution: As shown in appendix Table A6 (main paper), Laplace as a prior outperforms other distributions. To analyze this, we plot the distributions in Fig. R3 (rebuttal pdf). Note, we use the same distribution for optimality as well as temporal priors.

For the optimality prior, the x-axis is the difference of frames in the feature space (1-d representation for illustration purposes), and the y-axis denotes the corresponding probability of alignment. We want the point representing the most likely alignment (as per $\hat{T}$) to have the highest likelihood, while the assignment probability should exponentially decay further away. The graph clearly shows that the Laplace distribution captures this behavior suitably compared to Uniform and Gaussian. Similarly, for the temporal prior, the x-axis denotes the temporal distance between the frames, and the y-axis denotes the corresponding probability of alignment. The graph shows that Laplace distribution facilitates alignment of the frames when they are temporally aligned (close to center), and its long tail distribution enables better correlation of non-monotonic frames compared to Gaussian or Uniform. As a result, as shown in Fig. R3, even at far away locations from the center (temporally distant frames), alignment is possible if indeed these frames have a high match feature-wise. In this case, the Laplace temporal prior provides non-zero probability to that far away frame (due to its long tail) unlike other distributions and the optimality prior gives a large score (due to feature match), resulting in improved handling of non-monotonicity.

Refs:

[a] Dwibedi et al. Temporal cycle-consistency learning. CVPR 2019.

[b] Haresh et al. Learning by aligning videos in time. CVPR 2021.

Thanks for your encouraging feedback. Please find answers to your specific comments:

Presentation: We agree that the equations are too dense in Section 3, and the formulations can be simplified. We will update accordingly as per the reviewer’s suggestion during revision.

The V1 to V4 in Fig. 1 are from four different videos, while the frames from the same video are shown in x-axis. We apologize for the ambiguity of background frames vs redundant frames; the Fig.1 has been updated as Fig. R1 (rebuttal pdf). Both refer to frames not directly related to any key-step (hence, do not belong to any cluster) and thus are clustered together as a background cluster (Fig. R1, right). So, we remove the term redundant frames for clarity.

PL vs AS: Procedure learning (PL) and action segmentation (AS) are related but not the same. PL, when applied to a set of videos of the same task, involves 2 primary steps: (a) assigning each frame to 1 of the k key-steps (including background elements), (b) determining the logical sequence of the key-steps to complete the task. As illustrated in Fig. 1, PL addresses multiple videos of a given task, enabling the identification of repetitive key-steps across these videos [a, b]. In contrast, AS [c] focuses on a single video, thereby lacking the ability to discern repetitive key-steps across videos. Additionally, AS does not consider the sequence of individual events, which is often crucial for accurately identifying procedures. For instance, AS fails to capture the variations in the order of key-steps, such as those observed between V1 and V2 in Fig. 1.

In our work, the OPEL loss is used to train a representation learning algorithm to obtain an embedding space where similar frames are located close by. Then, as described in the ‘Clustering and Key-step Ordering’ part of page 6 of the main paper, these key-steps are clustered, and their sequential order is determined. A PyTorch function (with a toy example) is provided in codeblock R1 of the rebuttal pdf to illustrate this process of finding the sequential order (part b from the definition of PL given above) of the frame-wise key-step predictions (output from part a from the above PL definition).

Problem formulation: Given a set of videos of the same task (e.g. making brownies), PL aims to find the constituent key-steps (e.g. break egg, mix contents, add oil, mix egg) and their sequential order (break egg --> mix egg --> add water --> add oil --> mix contents).

During training: Inputs are untrimmed and unlabeled videos. We train with pairs of videos at a time (formulation detailed in Section 3 of the main paper). Output is the frames clustered into different key steps and their sequential order. For evaluation metrics, we use framewise cluster predictions, following other SOTA works [a,b,d].

During inference: Input: a single video, $P = \left[p_1,\ p_2,\ .\ .\ .\ ,\ p_N\right]$ Output: Assign each frame to a phase using trained model $f_{\theta}∶ f_{\theta}(p_i)= l_i$, where $l_i ∈ {c}^k_{c=1}$, represents the key-step corresponding to the phase of each frame $p_i$ in the video P.

From all $l_i$, we determine the sequential order of the sub-tasks (eg: 0,3,2,4,1...). Note, the cluster number is arbitrary, each of them denoting a key-step. We provide a PyTorch code to illustrate this process of finding the sequential order in codeblock R1 of the rebuttal pdf.

Choice of k: In unsupervised PL, k is not set during training (learning of the embeddings), rather k is used during inference only to fix the no. of output clusters, and each frame of the video being inferred is mapped to one of those k clusters. Now, an output video may not contain that exact k number of key-steps (e.g. in making a sandwich, steps such as adding jelly, butter etc. may be present in some videos, while absent in others).

We obtain best results with k=7 (Table 7), consistent with other SOTA methods on the same datasets [a,b,d]. We agree that based on the dataset, the average number of steps for each task may be > or < k. If it exceeds k, some steps get merged, e.g., for PC Disassembly, though the ground-truth number of steps is 9, 3 are quite similar (remove hard disk, remove motherboard, remove RAM); effectively making them quite close in the feature space. As a result, choosing k=7 results in these 3 key-steps getting merged. When the average number of key-steps becomes < k, each subtask gets split into multiple smaller clusters with very similar embeddings. This phenomenon is illustrated in Fig. R2 (rebuttal pdf), where a larger k might result in several split clusters of small windows (blue and red boxes in Fig. R2).

Note, this demarcation of subtasks (no. of clusters) varies from task to task, dataset to dataset and is subjective as some may consider semantically similar tasks (e.g. pouring oil vs water) to be same subtask, while others may consider it different. So, for best performance, k might be adjusted task-wise (using methods such as the elbow method, AIC criterion). However, optimizing for task-wise k is not the goal of this work; our contribution is on the OT-based learning and the clustering is only used as an inference post-processing step. So for fair comparison, we experiment with some reasonable values of k (following prior art [a,b,d]) and consistently outperform them across all k and all datasets with similar trends.

We report additional ablation on varying k in the rebuttal pdf, Table R1. We find that the performance degrades as k is increased from $7\to10\to12\to15$, thus overall k=7 provides the best performance. Note, our contribution is on the OT-based learning, the clustering is only used as an inference post-processing step. Overall, we achieve similar trends for varying k w.r.t. SOTA works [a,b,d].

[a] Bansal et al. ECCV 2022

[b] Bansal et al. WACV 2024

[c] Kumar et al. CVPR, 2022

[d] Shah et al. ICCV, 2023

Thanks for your encouraging and insightful feedback. Please find the answers to your specific comments:

Comparison with AS methods: Procedure learning (PL) and action segmentation (AS) are related but not the same. PL, when applied to a set of instructional videos depicting the same task, involves two primary steps: (i) assigning each video frame to one of the k key-steps (including background elements), and (ii) determining the logical sequence of these key-steps necessary to complete the task. As illustrated in Fig. 1 of the main paper, PL addresses multiple videos of a given task, enabling the identification of repetitive key-steps across these videos [i, j]. In contrast, AS [k] focuses on a single video, thereby lacking the ability to discern repetitive key-steps across different videos.

Despite the differences between PL and AS, as per the reviewer's suggestion, we compare our approach against existing SOTA unsupervised AS models [a-f] and present the results in Table X below. Our model demonstrates a significant performance improvement compared to these works. In [b, f], authors report a high recall score for CrossTask as it assigns majority of the frames to a single key-step - a phenomenon also reported by [j]. While achieving high recall is important for ensuring that most positive instances are correctly identified, it can result in a greater number of false positives, which in turn lowers precision and leads to undesirable results. Therefore, it is crucial to balance recall with precision to develop an effective model. This balance is reflected in the superior performance of our model, as evidenced by the F1-score results across various benchmarks. Note in the Table X, our approach is compared with SOTA Unsupervised AS methods for only third-person datasets, as these do not report any result on egocentric datasets.

Table X: Comparison of our approach with SOTA Unsupervised Action Segmentation methods. Note '-' denotes authors have not provided any data on those metrics.

Temporal Alignment methods: According to the reviewer's suggestion, we have included additional comparisons with temporal alignment techniques in Table Y. Specifically, we have compared our model with methods like TCC [g] and LAV [h], which incorporate temporal cycle consistency (TCC) and dynamic time warping (DTW), respectively. Other methods like CnC [i] uses TC3I (TCC + contrastive inverse difference moment, C-IDM) as the loss function while GPL [j] uses graph-based representation for temporal alignment. Our results clearly demonstrate the efficacy of our approach compared to these established methods, further validating the effectiveness of our model in maintaining temporal alignment while delivering superior PL performance. Note, in Table Y, our approach is compared with SOTA Unsupervised Temporal alignment methods for only egocentric (first-person) datasets, as these do not report any result on third-person datasets.

Table Y: Comparison of our approach with existing Unsupervised Temporal Alignment methods.

Thanks again for the suggestions to strengthen our paper, looking forward to your kind consideration.

Refs.:

[a] Elhamifar et al. Unsupervised Procedure Learning via Joint Dynamic Summarization, ICCV 2019.

[b] Elhamifar et al. Self-supervised multi-task procedure learning from instructional videos, ECCV 2020.

[c] Fried et al. Learning to segment actions from observation and narration, ACL 2020.

[d] Shen et al. Learning to segment actions from visual and language instructions via differentiable weak sequence alignment, CVPR 2021.

[e] Dvornik et al. Flow Graph to Video Grounding for Weakly-Supervised Multi-step Localization, ECCV 2022.

[f] Dvornik et al. StepFormer: Self-supervised Step Discovery and Localization in Instructional Videos, CVPR 2023.

[g] Dwibedi et al. Temporal cycle-consistency learning, CVPR 2019.

[h] Haresh et al. Learning by aligning videos in time, CVPR 2021.

[i] Bansal et al. My view is the best view: Procedure learning from egocentric videos. ECCV 2022.

[j] Bansal et al. United we stand, divided we fall: Unitygraph for unsupervised procedure learning from video. WACV 2024.

[k] Kumar et al. Unsupervised Action Segmentation by Joint Representation Learning and Online Clustering. CVPR, 2022.

Thanks for your encouraging and insightful feedback. Please find the answers to your specific comments. Also please refer to our overall rebuttal response to all reviewers and the corresponding pdf containing additional figures and tables to support our claims.

Method factors: The reviewer correctly points out that all the components are not equally critical for OPEL’s performance. We show the contributions of each factor individually to analyze their effect on the overall result in Table 5. Comparing row 3 with row 9, we observe, the priors jointly play a critical role; as without them (row 3), the F1 and IoU scores drop by ~5 points. Specifically, the optimality prior has a significant impact (~2 point), while the temporal prior affects the score by ~1 point. Similar to the combined priors, the intra and inter-video contrastive losses together (see row 6 vs row 9) have a significant effect (~3.5 points) on the overall performance. The individual effect of virtual frame is negligible as it only plays a role in case of excessive background frames - a scenario that is not prevalent in most datasets. Furthermore, due to the IDM structure of $M\left(\hat{T}\right)$, the $\hat{T}$ and $\hat{Q}$ are similar by formulation. This results in $KL\left(\hat{T}\ \parallel\hat{Q}\right)$ to be already small. As a consequence, adding the KL divergence as a standalone loss component in the proposed pipeline has a minimal impact. Overall, while some loss components may have a smaller individual impact, they do contribute to performance improvements, even if incrementally. Therefore, our proposed approach incorporates all of them to achieve the best possible results. We are encouraged with the reviewer's note - the provided ablation study improves the clarity of what is important in this method.

Writing: The equations are an integral part in explaining the proposed approach and the different loss terms. But we agree that the page 6 is too dense, and the formulations can be simplified to improve readability. We will update the notations and improve the overall writing as per the reviewer’s suggestion during revision.

Effect of k: Note, we obtain best results with k=7 (Table 7), and performance drops sharply as k goes from 7 to 10. This observation is consistent with all the other SOTA methods on the same datasets [a, b, c]. We hypothesize that k=7 works best as it is the optimal number of clusters considering the average number of distinct key-steps (subtasks) of the datasets. For example, for PC Disassembly, although the ground-truth (GT) number of steps is 9, 3 steps are quite similar (remove hard disk, remove motherboard, remove RAM), effectively making them quite close in the feature space. This results in k=7 being a better estimation of the cluster number with distinct steps. Note, this demarcation of subtasks (hence, number of clusters) is subjective and varies from dataset to dataset as well as from task to task; as some may consider semantically similar tasks (e.g. pouring oil vs water) to be one subtask, while others may consider it different. As k becomes larger than the actual distinctive number of clusters, each subtask gets split into multiple clusters with very similar embeddings, which upon comparison with GT leads to inferior results. This phenomenon is illustrated in Fig. R2 (see rebuttal pdf), where a larger k might result in several erroneous clusters with very small windows (blue and red boxes in Fig. R2). This leads to large fluctuations (jittery predictions) within a single GT phase, thus deteriorating the overall performance.

Secondly, the anomalous trend (k = 12 being slightly worse than 10 and 15) might be a dataset (PC Assembly) specific issue and not unique to our approach, as a similar trend for this dataset has been reported in [a, b]. However, for PC Disassembly and other datasets (reported as additional results in the rebuttal pdf, Table R1), we consistently find that the performance degrades as k is increased from 10 $\to$ 12 $\to$ 15. Note, that our contribution is on the optimal transport (OT)-based representation learning, the clustering is only used as an inference post-processing step. Overall, we achieve similar trends with respect to the SOTA works but consistently outperform them across all k and datasets.

Refs.:

[a] Bansal et al. My view is the best view: Procedure learning from egocentric videos. ECCV 2022.

[b] Bansal et al. United we stand, divided we fall: Unitygraph for unsupervised procedure learning from video. WACV 2024.

[c] Shah et al. Steps: Self-supervised key step extraction and localization from unlabeled procedural videos. ICCV, 2023.