\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the ICCV 2021 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for ICCV 2021.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.  

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\iccvfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
tech reports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a tech report for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the tech report as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the ICCV70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}
  
\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.

Page numbers should be included for review submissions but not for the 
final paper. Review submissions papers should have page numbers in the 
footer with numbers centered and .75 inches (1.905 cm) from the bottom 
of the page and start on the first page with the number 1.

Page numbers will be added by the publisher to all camera-ready papers 
prior to including them in the proceedings and before submitting the 
papers to IEEE Xplore. As such, your camera-ready submission should 
not include any page numbers. Page numbers should automatically be 
removed by uncommenting (if it's not already) the line
\begin{verbatim}
\end{verbatim}
near the beginning of the .tex file.

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centered.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the ICCV 2021 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}
 
Temporal action segmentation aims to classify each frame in an untrimmed video with an action label.
The task is a key step in understanding the structure of complex activities in videos. A recent study~\cite{shao2020tapos} also shows that the fine-grained sub-action segmentation can help many of other tasks such as action recognition and detection. Today's high performing solutions for temporal action segmentation require full frame-level supervision~\cite{mstcn,gcnactionseg,bcn}.  However, collecting per-frame annotations in untrimmed videos is extremely expensive and often impractical. 
Some recent work aim to overcome this by leveraging weak supervision to avoid the need of the full frame-level annotations~\cite{actionsetscvpr2020,setViterbi,nnviterbi}. 

These solutions, even though they do not use full supervision, still need some annotations that are costly to acquire, especially when expert knowledge on fine-grained atoms of activities (i.e., sub-actions) is required. Recently, temporal action segmentation in an unsupervised manner has received more attention~\cite{cvpr2019cnnrnn,kukleva2019unsupervisedtemporalembedding,cvpr2018}.
These solutions are clustering based and operate on extracted frame features. However, unsupervised temporal action segmentation is a very challenging problem. 
First, unlike in fully-supervised or weakly-supervised settings where at least the number or the order of the sub-actions are given, in unsupervised setting even the temporal order of sub-actions is unknown and needs to be estimated. 
Second, to parse long video sequences into sub-actions in a semantically meaningful way without any supervision requires a solution which not only extracts good visual representations for each individual frame, but also captures the temporal relations among frames and sub-actions. 
Today there are still no effective solutions to precisely estimate the temporal path of sub-actions, well capture the temporal characteristics in frame features, and model temporal correlations among sub-actions underlying the native structure of activities.
As a result, the performance of most today's unsupervised action segmentation solutions \cite{cvpr2019cnnrnn,kukleva2019unsupervisedtemporalembedding,cvpr2018} is still far from desired. 



In this work, we address above issues by firstly introducing self-supervised learning methods to extract frame-level feature representations that are usually more discriminative. 
While self-supervised learning has been widely exploited on other tasks such as image classification and action recognition~\cite{Deeo_Clustering,speednet,shufflelearn}, the application of it on action segmentation is unexploited.
We explore a few of today's most popular video based self-supervised learning approaches and show superior performance over the current state-of-the-art features in action segmentation. We further show that those self-supervised approaches that learn temporal characteristics outperform other self-supervised methods that focus on spatial transformation, which proves our assumption that modeling temporal relations is a key for accurately segmenting the frames into sub-actions. 

We then propose a Co-occurrence Action Parsing (CAP) algorithm to cluster the extracted features and decode the frames into sub-actions by considering both the temporal order of occurrence and the co-occurrence relations of sub-actions. These priors, calculated over the whole dataset, can statistically depict the natural structure of activities and will be injected into each video during inference.
Moreover, CAP is able to handle complex structures of activities and videos by taking multi-occurrence of sub-actions into account. Results show that with CAP, our solution not only achieves state-of-the-art (SOTA) for unsupervised action segmentation, and even outperforms some of the weakly-supervised approaches, but also is more generalizable to different scenarios. 


Besides evaluating our model on traditional action segmentation benchmarks such as Breakfast~\cite{breakfast}, Salad~\cite{salad}, we additionally test its performance on more challenging and recently emerging dataset FineGym~\cite{shao2020FineGym}. 
Actions in traditional benchmarks are well structured - they are goal-directed (actors have clear goals like ``making salad'' or ``preparing scrambled egg'') and can be decomposed into clear steps, with one step being as the prerequisite for another one (e.g., you have to ``get'' an egg before ``scramble'' it). However, actions in FineGym are with more complex structures - they are fast moving gymnastics related actions, where several actors may perform the same action multiple times in a single video. There are more similar fine-grained  sub-actions across different activities as well (for example: both `floor exercise' and `vault' event involves a lot of basic sub-action like `running' and `jumping'). Results show that our approach can achieve significant performance improvements on this challenging dataset, demonstrating the generalizability of our solution. To summarize, our main contributions are:
\begin{itemize}
    \item To the best of our knowledge, we are the first one to introduce the self-supervised feature representation learning in solving the unsupervised action segmentation problem. We study today's most popular video self-supervised learning approaches and show that self-supervised learning can bring notable improvement for unsupervised action segmentation;
   
    
    \item We propose a co-occurrence action parsing (CAP) algorithm, which takes into account the correlations and temporal locations of sub-actions calculated based on global statistics of all the videos, and is able to estimate the temporal path of sub-actions in a more precise and general way, and therefore outperforms today's solutions; 
   
    \item Our solution not only achieves SOTA performance on unsupervised action segmentation task (with an improvement up to 22\%) but also outperforms some weakly-supervised methods. We also study the action segmentation task on emerging and more challenging dataset that contains more complex activities structures and more similar fine-grained sub-actions. Results show that our solution can even achieve more improvement (up to 126.5\%) on it, demonstrating the effectiveness and generalizability of our solution. 
\end{itemize}


\input{relatedwork}


\begin{figure*}[htbp!]
\centerline{\includegraphics[scale=.45]{flowchart9.pdf}}
\caption{Overview of our approach.}
\label{fig:flowchart}
\end{figure*}

\section{Technical Approach}
\label{section:method}
Temporal action segmentation is a task to classify each frame in the video to a sub-action. Specifically, given $M$ videos,  each of them is represented by $X_m$ which contains $N_m$ frames. The task is to predict the action label $l_{mn} \in {1,...,K}$ for each video frame $x_{mn}$. In this paper, we study the task in an unsupervised setting, i.e., the label $l_{mn}$ for each frame is unknown during model training. 



Fig.~\ref{fig:flowchart} is an overview of our approach. Briefly: given a set of videos, our feature generation module extracts frame features with a self-supervised representation learning method. Extracted frame features are then sent to the co-occurrence action parsing (CAP) module, which clusters the frames and decodes them into segments of unlabeled sub-actions. Finally, the semantic action label is assigned to each cluster by using Hungarian algorithm~\cite{hungarianalgorithm}. We introduce each module in details in the following sections.  

    


\subsection{Feature Generation with Self-supervision}
\label{section:feature}

Our co-occurrence action parsing (CAP) module relies on the feature representation to have some semantic meaning so that the clustering step in our CAP module can effectively separate different semantic concepts in the video. In this work we explore a number of self-supervised feature leaning methods that have been developed for image and video classification tasks. We apply these methods for the task of video segmentation and study their relative effectiveness for that task v.s. the classification task they were designed for. Since one essential factor of the feature design for the temporal action segmentation is to capture the temporal characteristics, we want to further understand whether self-supervised learning methods built based on temporal augmentations (e.g, adjusting the frame rate, shuffling the frame or clip order, etc.) are also effective on temporal segmentation or not. 

With these questions in mind, we explore three of today's most popular video self-supervised learning methods and compare them with the feature designs used today in unsupervised action segmentation, including: IDT~\cite{idt},  FV~\cite{fishervector}, pre-trained I3D features~\cite{i3d}, and the continuous temporal features that achieves SOTA performance today~\cite{kukleva2019unsupervisedtemporalembedding}. Specifically, we study the following self-supervised methods: (1) \textit{SpeedNet}~\cite{speednet}, which augments the frame rate of the video and predict it; (2) \textit{ShuffleLearn}~\cite{shufflelearn}, which predict whether the order of frames in the sequence is shuffled or not; (3) \textit{RotationNet} ~\cite{rotationet}, which rotates the whole video sequence by several pre-defined degrees and predict which degree the video is rotated. Note that RotationNet is a method based on spatial augmentation, while Shuffle and Learn and SpeedNet are with temporal augmentation that are expected to have stronger temporal reasoning capability. Briefly we summarize the designs of these three methods in our work:   


\textit{SpeedNet}~\cite{speednet}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we pre-define four frame rate settings $[2, 4, 8, 15]$. Each time when we generate a clip we randomly select one out of these four settings. Note that we keep the number of frames in each clip as the same, hence the time-range of the clip varies according to the frame rate selected. We train the network to predict which frame-rate the clip is sampled from (i.e., a 4-way classification).

\textit{ShuffleLearn}~\cite{shufflelearn}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we random shuffle $M$ frames ($0<M<N$) in a random order. Each time when we generate the clip, we flip the coin to decide whether to shuffle it or not. We train the network to predict whether a clip is shuffled or not.


\textit{RotationNet}~\cite{rotationet}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we pre-define four rotation degree settings: $[0, 90, 180, 270]$. We also add some randomness when we rotate, i.e., in $[-30,30]$ degree. Each time when we generate clip we randomly select one out of these four settings and rotate the whole video sequence with the selected degree. We train the network to predict which of the settings is the rotation on (i.e., a 4-way classification).  

\textit{Importance of feature}. Finding an effective good feature for temporal action segmentation task is a non-trival task as we need insight and efforts to select good features and introduce them into action segmentation, and to demonstrate its superiorty over traditional features (Similar to applying GCN, LSTM, Transformers into specific vision tasks, which also requires some domain knowledge.) 




\subsection{Co-occurrence Action Parsing}

Our co-occurrence action parsing (CAP) algorithm consists of two steps: clustering and decoding. Extracted frame-level features from Section~\ref{section:feature} are first clustered. Since we don't have ground truth annotations on sub-actions, here we aim at generating a number of clusters, with each of them representing a unique but unlabeled sub-action. After clustering, we then generate three outputs: (1) a {\it video score matrix} that represents the predicting score of each frame to each cluster for the whole video; 
(2) a {\it co-occurrence matrix} that captures the chance of any pair of clusters co-existing in videos; and (3) a {\it cluster temporal location histogram} that captures the distribution of temporal locations of each cluster in videos. In decoding, we first apply the co-occurrence matrix onto the video score matrix to generate a {\it refined video score matrix}. Then we estimate a {\it temporal path} with the cluster temporal location histogram and decode the frames to final segments based on the temporal path. The overall algorithm can be seen in Fig.~\ref{fig:flowchart}. Below we introduce the clustering and decoding in details.  


\subsubsection{Clustering}
\label{sec:cluster}

Given an activity, and assuming there are $K$ different sub-actions
we extract all the frame-level features for all videos labeled with this activity, and cluster them into $K$ clusters using k-means. To get the probability of the frame $x_{mn}$ that belongs to the cluster $k$, we estimate a Gaussian distribution for each cluster $k \in K$ :
\begin{equation}
\label{eq:prob}
p(x_{mn}|k) = \mathcal{N} (x_{mn} ;\mu_k,\Sigma_k)
\end{equation} 
We generate three outputs from the clustering step: (1) video score matrix; (2) co-occurrence matrix and (3) cluster temporal location histogram.  

\textbf{Video score matrix}. Given a video $X_m$ that contains $N_m$ frames, we create a video score matrix $S_m \in \mathbb{R}^{K \times N_m}$ to hold the probabilities calculated from Eq.~(\ref{eq:prob}), where $K$ is the number of clusters. Each element $S_m[k,n]$, with $k\in \{1,2,..K\}$ and $n \in \{1,2,...N_m\}$ represents the probability of the $n$-th frame assigned to the cluster $k$. 


\textbf{Co-occurrence matrix}. The purpose of creating the co-occurrence matrix is to capture the correlations among sub-actions underlying the native structure of activities from the global video sets. Given an activity, there are usually strong correlations among its sub-actions across all videos. For example, in the activity ``Fried Egg'', ``fry egg'' always occurs with ``take egg''and ``crack egg''. While previous solutions do not build models to capture such global patterns, we leverage a co-occurrence matrix  to capture the co-existing relations among sub-actions. Note that, since we are dealing with an unsupervised setting, we don't have ground truth annotations on sub-actions, hence in the real implementation, what we calculate is the co-occurrence between two clusters $i$ and $j \in \{1,2, .., K\}$, instead of the real sub-actions. 
The way to generate the co-occurrence matrix is simple: for each pair of cluster $i$ and $j$, we iterate on all the videos and count the number of times that cluster $i$ and $j$ appear together in each video as $C(i,j)$. We also count the number of videos that contains the cluster $i$ as $C(i)$. To avoid the noise introduced by the clustering algorithm, we set a threshold $\tau_1$ in determining the appearance of a cluster, namely, while calculating the $C(i)$ and $C(i,j)$, only when the ratio of frames of class $i$ is larger than $\tau_1$, we count that class $i$ appears in the video.  
We then calculate a conditional occurrence probability as $ P(j|i) = C(i,j)/C(i)$, which represents the probability of cluster $j$ appears in a video given that cluster $i$ appears.
We calculate $P(i|j)$ for all pairs of clusters $(i, j)$ in this way and generate the $K\times K$ dimension co-occurrence matrix. Details are shown in Algorithm~\ref{alg:selection}. Since the co-occurrence matrix is learned from all videos, it is capturing the global patterns of the activity structures. The co-occurrence matrix is used for refining the video score matrix, which is introduced in Section~\ref{sec:decode}. 



\textbf{Cluster temporal location histogram}. The purpose of generating the cluster temporal location histogram is to estimate where each cluster generally locates in temporal dimension. Given the frames associated to each cluster from k-means, we compute the histogram of the temporal location for each cluster based on the timestamp of each frame in the video. Specifically, for a frame $x_{mn}$, i.e., the $n$-th frame in the video $X_m$, we calculate its relevant timestamp as $t_{x_{mn}} = n/N_m$, where $N_m$ is the total number of frames in video $X_m$. Then for each cluster $k$, we calculate the histogram on $t_{x_{mn}}$ for all the frames $x_{mn}$ from the videos that are clustered to $k$. The histogram indicates the potential temporal location of the cluster $k$ in the videos, and will be used for temporal path decoding introduced in Section~\ref{sec:decode}. Note that in real cases a sub-action can appear multiple times in different parts of videos, so each cluster might have more than one significant bin in the cluster temporal location histogram.   



\subsubsection{Decoding}
\label{sec:decode}

After clustering all the frames into $K$ clusters, the next step is to decode them into segments of the sub-actions. There are two main steps, namely, (1) refine the video score matrix with the co-occurrence matrix; (2) estimate the temporal path of the clusters and decode frames to segments. 




\textbf{Refining the video score matrix.} The first step in the decoding is to generate the refined video score matrix $R_m \in \mathbb{R}^{K \times N_m}$ for each video $X_m$. There are two main issues with directly using the original video score matrix $S_m$ in decoding: (1) the video score matrix is generated purely based on the frame feature representations, it does not capture any global patterns of the activity structures across all videos, and does not contain any correlation information among sub-actions; (2) the clustering is conducted on $K$ clusters, which is the total number of different sub-actions in the given activity. In many of cases, only a subset of $K$ will appear in each individual video due to the diversity of the activities being performed by different persons. 
Directly using video score matrix may lead to the issue of over-segmenting video to the non-existing classes in current video. To address these issues, we apply the co-occurrence matrix to refine the score matrix $S_m$. Specifically, we construct a {\it salience pool} to record the most ``salient'' clusters in a video. Given a video $X_m$ and for each cluster $k$, we first calculate the number of frames belonging to $k$ in the video, i.e., $c(k)$, and define the ratio of frames for cluster $k$ as $r(k)= c(k)/N_m$, where $N_m$ is the total number of frames in the video. We add the cluster $k_0$ with the largest $r(k)$ into the salience pool first. Then for the rest of clusters $k$, we weigh the ratio of frames as: 
\begin{equation}
\begin{aligned}
r'(k) = P(k_0|k) \cdot r(k), \\ 
\text{where } k \in 1,2,..., K, \text{and } k \neq k_0,
\end{aligned}
\end{equation} 
$P(k_0|k)$ is the conditional co-occurrence probability from the co-occurrence matrix calculated before. We set a threshold $\tau_2$ and select the cluster $k_1$ with the largest $r'(k)$. We add $k_1$ into the salience pool only if $r'(k_1) > \tau_2$. We keep iterating on this procedure by conditioning on
all clusters that has been added in the salience pool, until none of the ratio of frames from the rest of the clusters is above $\tau_2$.

Then we use the salience pool to calculate the refine video score matrix $R_m$. Since the salience pool is generated based on co-occurrence matrix, it brings the global information on the occurrence of clusters from all the videos. Clusters that are not in the salience pool should have lower chances to appear in the given video, hence we want to attenuate the scores of them. Assuming there are $K_s \subset K$ sub-actions in the salience pool, we introduce a decay factor $\eta$ to decay the probability scores of all the cluster $k \notin K_s$ for each frame in the video score matrix $S_m$, to generate the refined video score matrix $R_m$.  Details are in Algorithm~\ref{alg:selection}. The probabilistic update is inspired by Kalman filter where the new probability is updated based on the observation $P(k_0|k)$ and old probability $r(k)$. 

\begin{algorithm}[t]
\small
  \SetAlgoLined
  \KwData{Video score matrix $S_m$ for video $X_m$, with $S_m[k,n]_{k=1,n=1}^{K,N_m}$, number of clusters: $K$, thresholds: $\tau_1$,$\tau_2$, decay factor: $\eta$.}
  \KwResult{Co-occurrence matrix: $P(i,j)_{i,j=1}^K$,
  clusters in salience pool $\mathcal{C} = \{k_i\}_{i=1}^{K_s}$, where $K_s\ \subset K$, Refined video score matrix $R_m$, with scores $R_m[k,n]$.}
  - Compute the ratio of frames for each cluster in each video, if it is larger than $\tau_1$, we treat the specific cluster occur in the video. \\
  - Iterate all the videos, count the times each cluster appears $C(i)_{i=1}^K$, and the times different clusters co-occur together $C(i,j)_{i,j=1}^K$. Normalize to make it as conditional probability $P(j|i) = C(i,j) / C(i)$\\
  - Initialization:  $\mathcal{C} \leftarrow k_0 $. ($k_0$ is the cluster with the largest ratio of frames  $r(k_0)$ in current video.)\\
  \While{$len(\mathcal{C}) \leq K$}{
    1. For each remaining cluster $j$, update the ratio of frames with the cluster $i$ just added into the salience pool:
    $
       r(j) = P(i | j) \cdot r(j),
    $\\
    2. Choose the class: $k^* \leftarrow \mathrm{arg}\max_{j} r(j)  $. \\
    3. Update: $\mathcal{C} \leftarrow \mathcal{C} \cup \{k^*\}$,  if $r(k^*) > \tau_2 $, else break.
    }
  \For{$n \leq N_m$}{ 
   
    Decay probabilities in video score matrix $S_m$,  $R_m[k,n] = \eta S_m[k,n]$,  $\forall k \notin  \mathcal{C}$.
  }
  $-$ Return refined video score matrix: $R_m$.
  \caption{Generating the Co-occurrence Matrix and the Refined Video Score Matrix.}
  \label{alg:selection}
\end{algorithm}

\textbf{Estimating the temporal path and decoding.} Having the refined video score matrix, the final step is to decode the frame sequences into the sub-action segments. Assume that we have a known temporal path of the clusters $k_1 \rightarrow ... \rightarrow k_T$, then the decoding is to maximize the probability of the sequence following this path based on our refined video score matrix, i.e.,  
\begin{equation}
\label{eq:decode}
\hat{l}_{l}^{N_m} = {argmax}_{l_1,...,l_{N_m}}\prod^{N_m}_{n=1} p(x_{mn}|l_n ) p(l_n | l_{n-1}),
\end{equation} 
where, $p(x_{mn}|l_n=k)$ is the probability of the frame $x_{mn}$ belonging to the cluster $k$, obtained from the refined video score matrix, and $p(l_n | l_{n-1}) $ are the transition probabilities of moving from the label  $l_{n-1}$  at frame $n-1$ to the next label $l_n$ at frame $n$. Given a temporal path, Eq.~(\ref{eq:decode}) can be solved with a Viterbi algorithm \cite{viterbi}. 

The temporal path estimation is the key for the decoding. While in weakly-supervised action segmentation the temporal path (i.e, the order of sub-actions) is usually assumed to be known, in unsupervised setting it can only be estimated. Previous work~\cite{kukleva2019unsupervisedtemporalembedding} proposed an estimation of the temporal path that is limited to be strictly single directional and each sub-action can appear at most once in the path. Such a path may suit for dataset with simple activity structures, e.g., Breakfast~\cite{breakfast}, 
however, begins to fail when the structure of activities gets more complex. For instance, a single sub-action may occur multiple times, and the order of the sub-actions can be bi-directional (i.e., sub-action $i$ can go to sub-action $j$ and then go back to $i$). 


We design a {\it multi-occur temporal path} that is suitable for more general cases,
using the cluster temporal location histogram introduced in Section~\ref{sec:cluster}. We first set a global threshold $\theta$, and for each cluster, we only select the bins from temporal location histogram with counts (normalized to the total counts across all the bins) larger than $\theta$.
Then we merge the selected bins from all the clusters and sort them based on the temporal location associated with each bin. The order of bins with their corresponding cluster labels forms our temporal path. Our multi-occur temporal path has the following advantages: (1) it is able to capture the multi-time occurrence for each cluster as well as the bi-direction transition among different clusters, because more than one bins from each cluster can be selected; (2) by adjusting the global threshold, it can control the length of the generated temporal path.







\section{Experiments}
\label{section:experiments}


\paragraph{Datasets.} We evaluate our approach on two most widely used datasets in action segmentation: Breakfast~\cite{breakfast} and 50Salads~\cite{salad}, and an emerging fine-grained action dataset FineGym~\cite{shao2020FineGym}. \textbf{Breakfast}~\cite{breakfast} is a large-scale dataset that consists of ten different complex activities 
of performing common kitchen activities with approximately eight sub-actions
per activity class. The duration of the videos varies significantly, e.g. `coffee' has an average duration of 30 seconds while `cooking pancake' takes roughly 5 minutes. 
\textbf{50Salads}~\cite{salad} dataset contains 4.5 hours of different people performing a single complex activity, making mixed
salad. Compared to the other datasets, the videos are much longer with an average video length of 10k frames. We also observe that a single sub-action can occur multiple times along the video in this dataset, which seldom happens in Breakfast. \textbf{FineGym}~\cite{shao2020FineGym} is an emerging dataset provided with fine-grained sports action annotations. Though it is originally proposed for fine-grained action recognition, it contains rich hierarchical information including annotations of start and end for the fine-grained sub-actions, which is suitable for action segmentation evaluation.  These sports videos contain several athletes performing the same action 
and their replays. The structure of the videos are more complex and it includes many re-occurrences of a single sub-action, and includes more similar fine-grained sub-actions (up to 35), which makes the dataset more challenging for action segmentation than typical ones used today. We use Gym99 setting in original paper.
The statistics of it is listed in supplementary material. We select 20 as bin size and $\theta$ is set as 0.15. They are depending on native attributes of actions in the dataset.



 \begin{table}[t]
 {
 \centering
 \begin{tabular}{@{} c|c|c @{}} 
  \hline
   \textit{Breakfast} & MoF & F1 score\\ 
   \hline
   \multicolumn{3}{l}{\textbf{Unsupervised setting}}      \\
   \hline
         GMM \cite{cvpr2018}&  0.346 & - \\
         LSTM + AL \cite{cvpr2019cnnrnn}&  0.429* & - \\
         CTE \cite{kukleva2019unsupervisedtemporalembedding} &  0.418 & 0.264   \\ 
      
       Ours &  \textbf{0.511}  &  \textbf{0.392} \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Weakly-supervised setting}}      \\
   \hline
         Action Sets \cite{actionsetscvpr2018} & 0.284  & - \\
         NNviterbi \cite{nnviterbi}&  0.430  & - \\
         SCT \cite{actionsetscvpr2020} & 0.304  & - \\
         SetViterbi \cite{setViterbi} &  0.408 & -   \\ 
          EnergySeg \cite{energyweaklyactionseg} &  0.630  & -   \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Fully-supervised setting}}      \\
   \hline
         HTK \cite{htk} & 0.259  & - \\
         GTRM \cite{gcnactionseg} & 0.650& - \\
         MS-TCN \cite{mstcn}&  0.663 & - \\
         BCN \cite{bcn} &  0.704  & -   \\ 
       \hline
 \end{tabular}
 \caption{Results on Breakfast.} 
 \label{tab:actionsegmentationBreakfast}
 }
 \end{table}



\paragraph{Evaluation Metrics.} Following \cite{kukleva2019unsupervisedtemporalembedding} we use the Hungarian algorithm \cite{hungarianalgorithm} to get a one-to-one matching that maximizes the similarity between all the clusters and sub-action classes for all the videos in evaluation. 
We report frame-wise accuracy as the \textit{mean over frames (MoF)}, indicating the percentage of frames correctly labelled.  
We also report \textit{F1 score} the same as \cite{kukleva2019unsupervisedtemporalembedding} to measure the quality of the temporal segmentation. 



\subsection{Comparison with SOTA}

We compare our approach with SOTA solutions on Breakfast in Table~\ref{tab:actionsegmentationBreakfast}, 50Salads in Table~\ref{tab:actionsegmentationSalads} and FineGym in Table~\ref{tab:actionsegmentationFineGym}. For all the datasets, We use SpeedNet~\cite{speednet} trained on the Kinetics-400~\cite{i3d} as the feature for our CAP algorithm. Details on feature comparison can be referred to the Section~\ref{sec:abfeature}. We can see our method achieves SOTA performance on both Breakfast and 50Salads datasets under unsupervised setting, with around 22\% and 14\% improvement on MoF correspondingly. Our method on Breakfast even outperforms most of the weakly-supervised solutions.  








 \begin{table}[t]
 {
 \centering
 \begin{tabular}{@{} c|c|c @{}} 
  \hline
   \textit{50Salads} & MoF &F1 score\\ 
   \hline
   \multicolumn{3}{l}{\textbf{Unsupervised setting}}      \\
   \hline
         LSTM + AL \cite{cvpr2019cnnrnn}&  0.606* &  - \\
         CTE \cite{kukleva2019unsupervisedtemporalembedding} &  0.355 &  -   \\
       Ours &  \textbf{0.414} &  \textbf{0.303} \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Weakly-supervised setting}}      \\
   \hline
         NNviterbi \cite{nnviterbi}&  0.494 &  - \\
          EnergySeg \cite{energyweaklyactionseg} &  0.547  & -   \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Fully-supervised setting}}      \\
   \hline
         HTK \cite{htk} & 0.247 & \\
         GTRM \cite{gcnactionseg} & 0.826 & - \\
         MS-TCN \cite{mstcn}&  0.734 &  - \\
         BCN \cite{bcn} &  0.844 & -  \\ 
       \hline
 \end{tabular}
 \caption{Results on 50Salads. 
 Note that `*' uses a per-video instance cluster to ground-truth mapping, which uses additional video-level information, while we follow other work to use cluster to ground-truth mapping in a global manner in evaluation and do not use any additional information~\cite{vidalmata2020joint}.
 }

 \label{tab:actionsegmentationSalads}
 }
 \end{table}



 \begin{table}[t]
 {
 \centering
 \begin{tabular}{ @{} c|c|c @{}} 
  \hline 
   \textit{FineGym} & MoF & F1 score   \\ 
 \hline  
       Baseline~\cite{kukleva2019unsupervisedtemporalembedding} &  0.294  &  0.167   \\  
      
       Ours  &  \textbf{0.666} & \textbf{0.297}   \\  
       \hline
 \end{tabular}
 \caption{Results on FineGym.}
 \label{tab:actionsegmentationFineGym}
 }
 \end{table}


Since FineGym is new and we are the first to conduct action segmentation on it, there is no existing related results yet. We generate the baseline by running the SOTA apporach~\cite{kukleva2019unsupervisedtemporalembedding} on FineGym. We can see that on this emerging and more challenging dataset, our solution achieves even more improvement (127\% on MoF and 78\% on F1) comparing to the SOTA solution, demonstrating the effectiveness of our designed solution in handling videos with more complex structures. Overall the consistent improvement across all the benchmarks shows that our approach is able to be generalized to different cases. 




\subsection{Comparison of Feature Learning} 
\label{sec:abfeature}

We study three different self-supervised feature learning methods: (1) SpeedNet~\cite{speednet}, (2) RotationNet~\cite{rotationet}, and (3) ShuffleLearn~\cite{shufflelearn}, and compare the results on Breakfast dataset in Table~\ref{tab:differentmodelssinglecolumn}. All the numbers in the table are generated without using the co-occurrence matrix and the multi-occur temporal path, so that we can purely evaluate the effectiveness of features without bringing any additional factors.   



We conduct the experiments on self-supervised training (1) only on Kinetics dataset (i.e., (d) - (f)), (2) only on Breakfast dataset (i.e., (g) - (i)) and (3) first on Kinectics dataset and then on Breakfast dataset (i.e., (j) - (l)), to further explore that whether we need to train on target dataset (i.e., Breakfast in our case) to get a good feature representation for the task. From the table we can find that: 

(1) Based on experiment (a) - (l), we conclude that SpeedNet trained on Kinectics shown in (d) performs the best and gives better performance than SOTA as in (c); 

(2) Based on experiment (d) - (l), RotationNet consistently performs worse than SpeedNet and ShuffleLearn. This may due to the fact that RotationNet is using self-supervised signal from spatial dimension, which may lack of ability to model the temporal characteristics between frames. SpeedNet and ShuffleLearn, however, use temporal augmentation as the self-supervised signal, so that they may have stronger capability in modeling the temporal relations among frames and thus are more suitable for temporal action segmentation. The results also indicate that it is important to capture temporal relations among frames in feature learning for the segmentation task. In addition, SpeedNet, as one of the most emerging and successful video self-supervised learning approaches, consistently outperforms the ShuffleLearn, showing the effectiveness of it; 

(3) Based on experiment (b), (d), (e), (f), self-supervised features always perform better than classical I3D feature pre-trained on Kinetics. We argue that 
while the I3D feature trained for action recognition task optimizes feature representation on video clip level, self-supervised learning representation implicitly learns better frame-level representation and can better capture the temporal structure inside the clip;  


(4) Based on the experiments (d) - (l), we can see larger dataset like Kinetics can help build better self-supervised representation, while smaller ones contain less variety. It's not needed to use target dataset to get a good feature representation for the temporal action segmentation task. 



\begin{table}[t]
{
\centering
\begin{tabular}{@{} c|c|c|c@{}} 
 \hline
   & Feature Description  & MoF & F1\\ 
   \hline
   \multicolumn{4}{l}{\textbf{Baseline}}      \\
   \hline
  (a) &  IDT \cite{kukleva2019unsupervisedtemporalembedding} &      0.316 &    -   \\ 
  (b) &     K400 I3D  \cite{kukleva2019unsupervisedtemporalembedding}&      0.251 &  -     \\ 
  (c) &     CTE  \cite{kukleva2019unsupervisedtemporalembedding} &      0.418 &    0.264   \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised on K400}}      \\
   \hline
  (d) &    K400 SpeedNet &      \textbf{0.508} &    \textbf{0.391}   \\ 
  (e) &     K400 RotationNet &       0.328 &     0.317   \\ 
  (f) &      K400 shuffleLearn &    0.339    &   0.328     \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised on Breakfast}}      \\
   \hline
  (g) &     Breakfast SpeedNet &     0.344 &    0.327   \\ 
  (h) &      Breakfast  RotationNet&      0.307 &  0.319     \\ 
  (i) &      Breakfast shuffleLearn &      0.315 &      0.309 \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised first on K400, then on Breakfast}}      \\
   \hline
  (j) &      K400, Breakfast, SpeedNet &      \underline{0.501} &    \underline{0.337}   \\ 
  (k) &     K400, Breakfast, RotationNet &      0.279 &  0.290     \\ 
  (l) &      K400, Breakfast, shuffleLearn &      0.292 &    0.318   \\ 

 \hline
\end{tabular}
\caption{Comparison of features for temporal action segmentation.  `K400' denotes features trained on Kinetics \cite{i3d} dataset while `Breakfast' represents features trained on Breakfast \cite{breakfast} dataset. `SpeedNet', `RotationNet' and `ShuffleLearn' denote features trained using the self-supervised methods from \cite{speednet}, \cite{rotationet} and \cite{shufflelearn}. }
\label{tab:differentmodelssinglecolumn}
}
\end{table}







\begin{table}[t]
{
\begin{center}
\begin{tabular}{@{}  c | c  c c  | c | c @{}} 
 \hline 
 Dataset   & Feat & C-Matrix & M-T-Path & MoF & F1  \\ 
\hline  
 \multirow{4}{*}{\textit{Breakfast}}  &     &  &    &  0.418  & 0.264  \\  
    &  \checkmark  &   &    &  0.508  & 0.391  \\  
      
      & \checkmark &    \checkmark  &   
 &  0.511  & 0.392  \\  
        
         &  \checkmark &  \checkmark  &   \checkmark  &  \textbf{0.511}  &  \textbf{0.392} \\  
       \hline  
    \multirow{4}{*}{\textit{50Salads}} &      &   &    &  0.355  & -  \\  
    &   \checkmark   &   &    &  0.372  & 0.281  \\  
      
        & \checkmark &  \checkmark  &    &  0.378  &  0.290 \\  
        
          &   \checkmark  & \checkmark  & \checkmark  &  \textbf{0.414}  & \textbf{0.303}  \\  
          
        
        \hline  
    \multirow{4}{*}{\textit{FineGym}}      &          & &  &  0.294  &  0.167 \\  
    &      \checkmark    & &  &  0.425  &  0.246 \\  
      
         &  \checkmark &  \checkmark  &   &  0.442  &  0.248 \\  
        
          &   \checkmark   & \checkmark &  \checkmark  & 
          \textbf{0.666}  &  \textbf{0.297} \\  
         
         
     
     
      \hline  
\end{tabular}
\end{center}
\caption{Ablation study on all datasets. `Feat' denotes whether to use the SpeedNet feature trained on K400; `C-Matrix' denotes whether to use the  \textit{co-occurrence matrix} to refine the video score matrix; and `M-T-Path' denotes whether to use our designed \textit{multi-occur temporal path} in decoding. If none of them is selected then it's a baseline setting from~\cite{kukleva2019unsupervisedtemporalembedding}.} 
\label{tab:betterdecoding}
}
\end{table}

\subsection{Ablation Study on CAP} 

Next, we conduct ablation studies on our CAP algorithm. Two main units are investigated: (1) Co-occurrence Matrix; (2) Multi-occur Temporal Path. 

\textbf{Effectiveness of Co-occurrence Matrix.}
We evaluate the influence of using the co-occurrence matrix to refine the video score matrix in Table~\ref{tab:betterdecoding} on all datasets. From the table, our co-occurrence matrix brings performance improvement over using original video score on all of the three datasets and on both \textit{MoF} and \textit{F1}. 
The improvement on FineGym dataset is more notable than the other two, indicating the importance of using the co-occurrence matrix while handling more complex scenarios.



\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\textwidth}
   \centering
  \includegraphics[width=.95\linewidth]{quali3_2.pdf} 
  \caption{P24 friedegg sequence from Breakfast dataset. The semantics order are `background', `crack egg',`fry egg', `take plate', `put egg2plate', `background'.}
  \label{fig:qualitativec}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.48\textwidth}
   \centering
  \includegraphics[width=.95\linewidth]{quali4_2.pdf}
  \caption{P38 juice sequence from Breakfast dataset. The semantics order are `background', `cut orange', `squeeze orange',`take glass',`pour juice',`background'.}
  \label{fig:qualitatived}
\end{subfigure}
\caption{Two qualitative examples (a) and (b). The first row is the frame-wise ground-truth (x-axis stands for the time in the video while different sub-action classes are colorized differently); the second row is the prediction from \cite{kukleva2019unsupervisedtemporalembedding}; the third row is our prediction; and the fourth row is the uniform sampled 8 frames from the original video. Best viewed zoom in and in color.}
\label{fig:qualitativeall}
\end{figure}



\textbf{Effectiveness of Multi-occur Temporal Path.} We then assess the impact of using the proposed multi-occur temporal path in decoding. Results on all three datasets are in table~\ref{tab:betterdecoding}.  
We can see the designed multi-occur temporal path decoding improves both \textit{MoF} and \textit{F1} on 50Salads and FineGym, but does not on Breakfast.
We observe that the multi-occurrence of one sub-action in the same video happens more frequently in 50Salads and FineGym, while in Breakfast, most of the sub-actions only occur once in each video, therefore, the multi-occur temporal path is not as helpful on Breakfast as on the other datasets. It is worth to mention that our CAP algorithm actually generates an exact the same temporal path (with each sub-action occurring only once) automatically as turning off the function for the Breakfast, representing that the CAP algorithm is self-applicable to different scenarios.

\subsection{Qualitative Results}

Fig.~\ref{fig:qualitativeall} visualizes two examples from Breakfast dataset. From both Fig.~\ref{fig:qualitativec} and Fig.~\ref{fig:qualitatived} we can see that our CAP algorithm is able to effectively suppress the over-segmentation issue in baseline by introducing the co-occurrence relations among sub-actions in decoding.  



\section{Conclusion}
\label{section:concolusion}
In this work, we have shown that using self-supervised methods in feature learning can effectively improve the performance of unsupervised temporal action segmentation. We have also proposed a CAP algorithm that helps model the co-occurrence among sub-actions and can better handle complex activity structures in videos. 
Our approach has achieved SOTA performance on three public benchmarks in unsupervised setting, and even outperform several recently proposed weakly-supervised methods. The future direction can be leveraging the deep clustering approaches in further improving the accuracy of the task.  


\section*{Acknowledgement}
We thank reviewers for the 
valuable suggestions. Zhe Wang personally thanks Fanyi Xiao,  Bing Shuai and Uta Büchler for helpful discussion

{\small
\bibliographystyle{ieee_fullname}

\section{Related Work}
\label{section:relatedwork}



\textbf{Temporal action segmentation} is a task to classify each frame in an untrimmed video with a label of action. It is a key for understanding structures of complex activities. While current techniques have achieved great success on other action understanding tasks such as action recognition~\cite{i3d,feichtenhofer2019slowfast,feichtenhofer2016convolutional,tran2015learning,yang2020temporal,wang2016temporal,zhou2018temporal,lin2019tsm,wang2018non,gmmhmm} and action detection~\cite{lin2018bsn,zhao2017temporal,xu2017r,hou2017tube}, temporal action segmentation is still far from being well-explored. Today's high performing solutions for temporal action segmentation require full frame-level supervision~\cite{mstcn,gcnactionseg,htk,bcn,lea2016segmental,lea2017temporal}. 
However, acquiring annotations on fine-grained sub-actions for each frame is expensive. To reduce the amount of labeled data needed,~\cite{sstda} proposes a domain adaptation approach based on self-supervised auxiliary tasks and achieves good performance. More recent works focus on developing weakly-supervised solutions: instead of having supervision for every frame, only the list (with order information)~\cite{firstunsuper,energyweaklyactionseg,nnviterbi,Richard_2017_CVPR,ding2018weakly,huang2016connectionist,chang2019d3tw} or the set (without order information)~\cite{actionsetscvpr2020,setViterbi,actionsetscvpr2018} of the sub-actions are required during training. Other work uses script
or instructions for weak annotation~\cite{alayrac2016unsupervised}.


\textbf{Unsupervised temporal action segmentation} starts to receive growing interests these days, to further reduce the dependence on labeled data.~\cite{UnsuperProcLearn} builds a joint sequential subset selection method to produces a summary of the procedure key-steps in instructional videos.~\cite{cvpr2018} learns a function assigning sub-activity scores to frame features and models the distribution over sub-activity permutations by a Generalized Mallows Model.~\cite{cvpr2019cnnrnn} proposes a self-supervised predictive learning with recurrent neural networks (RNN) by utilizing features of adjacent frames to find the action boundaries.~\cite{kukleva2019unsupervisedtemporalembedding} proposes a combination of temporal embedding generated using a frame timestamp prediction network, feature clustering and Viterbi decoding for consistent frame-to-cluster assignment. However, these solutions do not take into account the semantic correlations among sub-actions and the re-occurrence of sub-actions in some complex activity structures.







\textbf{Self-supervised learning of visual representation} is a hot topic today, and has shown success in some of action understanding tasks~\cite{lstmunsupervisedfaeture,Deeo_Clustering,speednet,fernando2017self}.  Many different video properties have been used as supervision to build good representations, such as: cycle consistency between video frames \cite{xiaolongcvpr2019}; distinguishing between a video frame sequence and a shuffled version of it \cite{shufflelearn}; predicting the order of the shuffled clips \cite{cliporder}; solving space-time cubic puzzles \cite{spacetimecubicpuzzles}; classifying the speed of the video \cite{speednet,speednetMIT}; recognize the rotation of the video \cite{rotationet}. Another common task is predicting the future, either by predicting pixels of future frames \cite{motionnet}, or an embedding of a future video segment \cite{pdc}. While today's action segmentation solutions~\cite{mstcn,kukleva2019unsupervisedtemporalembedding,bcn} still mainly rely on hand-crafted features such as IDT~\cite{idt}, Fisher Vector (FV)~\cite{fishervector}, or pre-trained features such as I3D on Kinetics dataset~\cite{i3d}, we believe that introducing self-supervised methods in feature representation learning for unsupervised action segmentation can significantly boost the performance, as it can not only bring strong discriminative power to the features, but also bring a chance to improve the temporal characteristics of the features. 

\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the ICCV 2021 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for ICCV 2021.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.  

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\iccvfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
tech reports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a tech report for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the tech report as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the ICCV70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}
  
\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.

Page numbers should be included for review submissions but not for the 
final paper. Review submissions papers should have page numbers in the 
footer with numbers centered and .75 inches (1.905 cm) from the bottom 
of the page and start on the first page with the number 1.

Page numbers will be added by the publisher to all camera-ready papers 
prior to including them in the proceedings and before submitting the 
papers to IEEE Xplore. As such, your camera-ready submission should 
not include any page numbers. Page numbers should automatically be 
removed by uncommenting (if it's not already) the line
\begin{verbatim}
\end{verbatim}
near the beginning of the .tex file.

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centered.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the ICCV 2021 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}
 
Temporal action segmentation aims to classify each frame in an untrimmed video with an action label.
The task is a key step in understanding the structure of complex activities in videos. A recent study~\cite{shao2020tapos} also shows that the fine-grained sub-action segmentation can help many of other tasks such as action recognition and detection. Today's high performing solutions for temporal action segmentation require full frame-level supervision~\cite{mstcn,gcnactionseg,bcn}.  However, collecting per-frame annotations in untrimmed videos is extremely expensive and often impractical. 
Some recent work aim to overcome this by leveraging weak supervision to avoid the need of the full frame-level annotations~\cite{actionsetscvpr2020,setViterbi,nnviterbi}. 

These solutions, even though they do not use full supervision, still need some annotations that are costly to acquire, especially when expert knowledge on fine-grained atoms of activities (i.e., sub-actions) is required. Recently, temporal action segmentation in an unsupervised manner has received more attention~\cite{cvpr2019cnnrnn,kukleva2019unsupervisedtemporalembedding,cvpr2018}.
These solutions are clustering based and operate on extracted frame features. However, unsupervised temporal action segmentation is a very challenging problem. 
First, unlike in fully-supervised or weakly-supervised settings where at least the number or the order of the sub-actions are given, in unsupervised setting even the temporal order of sub-actions is unknown and needs to be estimated. 
Second, to parse long video sequences into sub-actions in a semantically meaningful way without any supervision requires a solution which not only extracts good visual representations for each individual frame, but also captures the temporal relations among frames and sub-actions. 
Today there are still no effective solutions to precisely estimate the temporal path of sub-actions, well capture the temporal characteristics in frame features, and model temporal correlations among sub-actions underlying the native structure of activities.
As a result, the performance of most today's unsupervised action segmentation solutions \cite{cvpr2019cnnrnn,kukleva2019unsupervisedtemporalembedding,cvpr2018} is still far from desired. 



In this work, we address above issues by firstly introducing self-supervised learning methods to extract frame-level feature representations that are usually more discriminative. 
While self-supervised learning has been widely exploited on other tasks such as image classification and action recognition~\cite{Deeo_Clustering,speednet,shufflelearn}, the application of it on action segmentation is unexploited.
We explore a few of today's most popular video based self-supervised learning approaches and show superior performance over the current state-of-the-art features in action segmentation. We further show that those self-supervised approaches that learn temporal characteristics outperform other self-supervised methods that focus on spatial transformation, which proves our assumption that modeling temporal relations is a key for accurately segmenting the frames into sub-actions. 

We then propose a Co-occurrence Action Parsing (CAP) algorithm to cluster the extracted features and decode the frames into sub-actions by considering both the temporal order of occurrence and the co-occurrence relations of sub-actions. These priors, calculated over the whole dataset, can statistically depict the natural structure of activities and will be injected into each video during inference.
Moreover, CAP is able to handle complex structures of activities and videos by taking multi-occurrence of sub-actions into account. Results show that with CAP, our solution not only achieves state-of-the-art (SOTA) for unsupervised action segmentation, and even outperforms some of the weakly-supervised approaches, but also is more generalizable to different scenarios. 


Besides evaluating our model on traditional action segmentation benchmarks such as Breakfast~\cite{breakfast}, Salad~\cite{salad}, we additionally test its performance on more challenging and recently emerging dataset FineGym~\cite{shao2020FineGym}. 
Actions in traditional benchmarks are well structured - they are goal-directed (actors have clear goals like ``making salad'' or ``preparing scrambled egg'') and can be decomposed into clear steps, with one step being as the prerequisite for another one (e.g., you have to ``get'' an egg before ``scramble'' it). However, actions in FineGym are with more complex structures - they are fast moving gymnastics related actions, where several actors may perform the same action multiple times in a single video. There are more similar fine-grained  sub-actions across different activities as well (for example: both `floor exercise' and `vault' event involves a lot of basic sub-action like `running' and `jumping'). Results show that our approach can achieve significant performance improvements on this challenging dataset, demonstrating the generalizability of our solution. To summarize, our main contributions are:
\begin{itemize}
    \item To the best of our knowledge, we are the first one to introduce the self-supervised feature representation learning in solving the unsupervised action segmentation problem. We study today's most popular video self-supervised learning approaches and show that self-supervised learning can bring notable improvement for unsupervised action segmentation;
   
    
    \item We propose a co-occurrence action parsing (CAP) algorithm, which takes into account the correlations and temporal locations of sub-actions calculated based on global statistics of all the videos, and is able to estimate the temporal path of sub-actions in a more precise and general way, and therefore outperforms today's solutions; 
   
    \item Our solution not only achieves SOTA performance on unsupervised action segmentation task (with an improvement up to 22\%) but also outperforms some weakly-supervised methods. We also study the action segmentation task on emerging and more challenging dataset that contains more complex activities structures and more similar fine-grained sub-actions. Results show that our solution can even achieve more improvement (up to 126.5\%) on it, demonstrating the effectiveness and generalizability of our solution. 
\end{itemize}


\input{relatedwork}


\begin{figure*}[htbp!]
\centerline{\includegraphics[scale=.45]{flowchart9.pdf}}
\caption{Overview of our approach.}
\label{fig:flowchart}
\end{figure*}

\section{Technical Approach}
\label{section:method}
Temporal action segmentation is a task to classify each frame in the video to a sub-action. Specifically, given $M$ videos,  each of them is represented by $X_m$ which contains $N_m$ frames. The task is to predict the action label $l_{mn} \in {1,...,K}$ for each video frame $x_{mn}$. In this paper, we study the task in an unsupervised setting, i.e., the label $l_{mn}$ for each frame is unknown during model training. 



Fig.~\ref{fig:flowchart} is an overview of our approach. Briefly: given a set of videos, our feature generation module extracts frame features with a self-supervised representation learning method. Extracted frame features are then sent to the co-occurrence action parsing (CAP) module, which clusters the frames and decodes them into segments of unlabeled sub-actions. Finally, the semantic action label is assigned to each cluster by using Hungarian algorithm~\cite{hungarianalgorithm}. We introduce each module in details in the following sections.  

    


\subsection{Feature Generation with Self-supervision}
\label{section:feature}

Our co-occurrence action parsing (CAP) module relies on the feature representation to have some semantic meaning so that the clustering step in our CAP module can effectively separate different semantic concepts in the video. In this work we explore a number of self-supervised feature leaning methods that have been developed for image and video classification tasks. We apply these methods for the task of video segmentation and study their relative effectiveness for that task v.s. the classification task they were designed for. Since one essential factor of the feature design for the temporal action segmentation is to capture the temporal characteristics, we want to further understand whether self-supervised learning methods built based on temporal augmentations (e.g, adjusting the frame rate, shuffling the frame or clip order, etc.) are also effective on temporal segmentation or not. 

With these questions in mind, we explore three of today's most popular video self-supervised learning methods and compare them with the feature designs used today in unsupervised action segmentation, including: IDT~\cite{idt},  FV~\cite{fishervector}, pre-trained I3D features~\cite{i3d}, and the continuous temporal features that achieves SOTA performance today~\cite{kukleva2019unsupervisedtemporalembedding}. Specifically, we study the following self-supervised methods: (1) \textit{SpeedNet}~\cite{speednet}, which augments the frame rate of the video and predict it; (2) \textit{ShuffleLearn}~\cite{shufflelearn}, which predict whether the order of frames in the sequence is shuffled or not; (3) \textit{RotationNet} ~\cite{rotationet}, which rotates the whole video sequence by several pre-defined degrees and predict which degree the video is rotated. Note that RotationNet is a method based on spatial augmentation, while Shuffle and Learn and SpeedNet are with temporal augmentation that are expected to have stronger temporal reasoning capability. Briefly we summarize the designs of these three methods in our work:   


\textit{SpeedNet}~\cite{speednet}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we pre-define four frame rate settings $[2, 4, 8, 15]$. Each time when we generate a clip we randomly select one out of these four settings. Note that we keep the number of frames in each clip as the same, hence the time-range of the clip varies according to the frame rate selected. We train the network to predict which frame-rate the clip is sampled from (i.e., a 4-way classification).

\textit{ShuffleLearn}~\cite{shufflelearn}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we random shuffle $M$ frames ($0<M<N$) in a random order. Each time when we generate the clip, we flip the coin to decide whether to shuffle it or not. We train the network to predict whether a clip is shuffled or not.


\textit{RotationNet}~\cite{rotationet}. Given a clip $C$ with fixed number of $N$ frames: $C$ = ($f_1, f_2, ..., f_N$), we pre-define four rotation degree settings: $[0, 90, 180, 270]$. We also add some randomness when we rotate, i.e., in $[-30,30]$ degree. Each time when we generate clip we randomly select one out of these four settings and rotate the whole video sequence with the selected degree. We train the network to predict which of the settings is the rotation on (i.e., a 4-way classification).  

\textit{Importance of feature}. Finding an effective good feature for temporal action segmentation task is a non-trival task as we need insight and efforts to select good features and introduce them into action segmentation, and to demonstrate its superiorty over traditional features (Similar to applying GCN, LSTM, Transformers into specific vision tasks, which also requires some domain knowledge.) 




\subsection{Co-occurrence Action Parsing}

Our co-occurrence action parsing (CAP) algorithm consists of two steps: clustering and decoding. Extracted frame-level features from Section~\ref{section:feature} are first clustered. Since we don't have ground truth annotations on sub-actions, here we aim at generating a number of clusters, with each of them representing a unique but unlabeled sub-action. After clustering, we then generate three outputs: (1) a {\it video score matrix} that represents the predicting score of each frame to each cluster for the whole video; 
(2) a {\it co-occurrence matrix} that captures the chance of any pair of clusters co-existing in videos; and (3) a {\it cluster temporal location histogram} that captures the distribution of temporal locations of each cluster in videos. In decoding, we first apply the co-occurrence matrix onto the video score matrix to generate a {\it refined video score matrix}. Then we estimate a {\it temporal path} with the cluster temporal location histogram and decode the frames to final segments based on the temporal path. The overall algorithm can be seen in Fig.~\ref{fig:flowchart}. Below we introduce the clustering and decoding in details.  


\subsubsection{Clustering}
\label{sec:cluster}

Given an activity, and assuming there are $K$ different sub-actions
we extract all the frame-level features for all videos labeled with this activity, and cluster them into $K$ clusters using k-means. To get the probability of the frame $x_{mn}$ that belongs to the cluster $k$, we estimate a Gaussian distribution for each cluster $k \in K$ :
\begin{equation}
\label{eq:prob}
p(x_{mn}|k) = \mathcal{N} (x_{mn} ;\mu_k,\Sigma_k)
\end{equation} 
We generate three outputs from the clustering step: (1) video score matrix; (2) co-occurrence matrix and (3) cluster temporal location histogram.  

\textbf{Video score matrix}. Given a video $X_m$ that contains $N_m$ frames, we create a video score matrix $S_m \in \mathbb{R}^{K \times N_m}$ to hold the probabilities calculated from Eq.~(\ref{eq:prob}), where $K$ is the number of clusters. Each element $S_m[k,n]$, with $k\in \{1,2,..K\}$ and $n \in \{1,2,...N_m\}$ represents the probability of the $n$-th frame assigned to the cluster $k$. 


\textbf{Co-occurrence matrix}. The purpose of creating the co-occurrence matrix is to capture the correlations among sub-actions underlying the native structure of activities from the global video sets. Given an activity, there are usually strong correlations among its sub-actions across all videos. For example, in the activity ``Fried Egg'', ``fry egg'' always occurs with ``take egg''and ``crack egg''. While previous solutions do not build models to capture such global patterns, we leverage a co-occurrence matrix  to capture the co-existing relations among sub-actions. Note that, since we are dealing with an unsupervised setting, we don't have ground truth annotations on sub-actions, hence in the real implementation, what we calculate is the co-occurrence between two clusters $i$ and $j \in \{1,2, .., K\}$, instead of the real sub-actions. 
The way to generate the co-occurrence matrix is simple: for each pair of cluster $i$ and $j$, we iterate on all the videos and count the number of times that cluster $i$ and $j$ appear together in each video as $C(i,j)$. We also count the number of videos that contains the cluster $i$ as $C(i)$. To avoid the noise introduced by the clustering algorithm, we set a threshold $\tau_1$ in determining the appearance of a cluster, namely, while calculating the $C(i)$ and $C(i,j)$, only when the ratio of frames of class $i$ is larger than $\tau_1$, we count that class $i$ appears in the video.  
We then calculate a conditional occurrence probability as $ P(j|i) = C(i,j)/C(i)$, which represents the probability of cluster $j$ appears in a video given that cluster $i$ appears.
We calculate $P(i|j)$ for all pairs of clusters $(i, j)$ in this way and generate the $K\times K$ dimension co-occurrence matrix. Details are shown in Algorithm~\ref{alg:selection}. Since the co-occurrence matrix is learned from all videos, it is capturing the global patterns of the activity structures. The co-occurrence matrix is used for refining the video score matrix, which is introduced in Section~\ref{sec:decode}. 



\textbf{Cluster temporal location histogram}. The purpose of generating the cluster temporal location histogram is to estimate where each cluster generally locates in temporal dimension. Given the frames associated to each cluster from k-means, we compute the histogram of the temporal location for each cluster based on the timestamp of each frame in the video. Specifically, for a frame $x_{mn}$, i.e., the $n$-th frame in the video $X_m$, we calculate its relevant timestamp as $t_{x_{mn}} = n/N_m$, where $N_m$ is the total number of frames in video $X_m$. Then for each cluster $k$, we calculate the histogram on $t_{x_{mn}}$ for all the frames $x_{mn}$ from the videos that are clustered to $k$. The histogram indicates the potential temporal location of the cluster $k$ in the videos, and will be used for temporal path decoding introduced in Section~\ref{sec:decode}. Note that in real cases a sub-action can appear multiple times in different parts of videos, so each cluster might have more than one significant bin in the cluster temporal location histogram.   



\subsubsection{Decoding}
\label{sec:decode}

After clustering all the frames into $K$ clusters, the next step is to decode them into segments of the sub-actions. There are two main steps, namely, (1) refine the video score matrix with the co-occurrence matrix; (2) estimate the temporal path of the clusters and decode frames to segments. 




\textbf{Refining the video score matrix.} The first step in the decoding is to generate the refined video score matrix $R_m \in \mathbb{R}^{K \times N_m}$ for each video $X_m$. There are two main issues with directly using the original video score matrix $S_m$ in decoding: (1) the video score matrix is generated purely based on the frame feature representations, it does not capture any global patterns of the activity structures across all videos, and does not contain any correlation information among sub-actions; (2) the clustering is conducted on $K$ clusters, which is the total number of different sub-actions in the given activity. In many of cases, only a subset of $K$ will appear in each individual video due to the diversity of the activities being performed by different persons. 
Directly using video score matrix may lead to the issue of over-segmenting video to the non-existing classes in current video. To address these issues, we apply the co-occurrence matrix to refine the score matrix $S_m$. Specifically, we construct a {\it salience pool} to record the most ``salient'' clusters in a video. Given a video $X_m$ and for each cluster $k$, we first calculate the number of frames belonging to $k$ in the video, i.e., $c(k)$, and define the ratio of frames for cluster $k$ as $r(k)= c(k)/N_m$, where $N_m$ is the total number of frames in the video. We add the cluster $k_0$ with the largest $r(k)$ into the salience pool first. Then for the rest of clusters $k$, we weigh the ratio of frames as: 
\begin{equation}
\begin{aligned}
r'(k) = P(k_0|k) \cdot r(k), \\ 
\text{where } k \in 1,2,..., K, \text{and } k \neq k_0,
\end{aligned}
\end{equation} 
$P(k_0|k)$ is the conditional co-occurrence probability from the co-occurrence matrix calculated before. We set a threshold $\tau_2$ and select the cluster $k_1$ with the largest $r'(k)$. We add $k_1$ into the salience pool only if $r'(k_1) > \tau_2$. We keep iterating on this procedure by conditioning on
all clusters that has been added in the salience pool, until none of the ratio of frames from the rest of the clusters is above $\tau_2$.

Then we use the salience pool to calculate the refine video score matrix $R_m$. Since the salience pool is generated based on co-occurrence matrix, it brings the global information on the occurrence of clusters from all the videos. Clusters that are not in the salience pool should have lower chances to appear in the given video, hence we want to attenuate the scores of them. Assuming there are $K_s \subset K$ sub-actions in the salience pool, we introduce a decay factor $\eta$ to decay the probability scores of all the cluster $k \notin K_s$ for each frame in the video score matrix $S_m$, to generate the refined video score matrix $R_m$.  Details are in Algorithm~\ref{alg:selection}. The probabilistic update is inspired by Kalman filter where the new probability is updated based on the observation $P(k_0|k)$ and old probability $r(k)$. 

\begin{algorithm}[t]
\small
  \SetAlgoLined
  \KwData{Video score matrix $S_m$ for video $X_m$, with $S_m[k,n]_{k=1,n=1}^{K,N_m}$, number of clusters: $K$, thresholds: $\tau_1$,$\tau_2$, decay factor: $\eta$.}
  \KwResult{Co-occurrence matrix: $P(i,j)_{i,j=1}^K$,
  clusters in salience pool $\mathcal{C} = \{k_i\}_{i=1}^{K_s}$, where $K_s\ \subset K$, Refined video score matrix $R_m$, with scores $R_m[k,n]$.}
  - Compute the ratio of frames for each cluster in each video, if it is larger than $\tau_1$, we treat the specific cluster occur in the video. \\
  - Iterate all the videos, count the times each cluster appears $C(i)_{i=1}^K$, and the times different clusters co-occur together $C(i,j)_{i,j=1}^K$. Normalize to make it as conditional probability $P(j|i) = C(i,j) / C(i)$\\
  - Initialization:  $\mathcal{C} \leftarrow k_0 $. ($k_0$ is the cluster with the largest ratio of frames  $r(k_0)$ in current video.)\\
  \While{$len(\mathcal{C}) \leq K$}{
    1. For each remaining cluster $j$, update the ratio of frames with the cluster $i$ just added into the salience pool:
    $
       r(j) = P(i | j) \cdot r(j),
    $\\
    2. Choose the class: $k^* \leftarrow \mathrm{arg}\max_{j} r(j)  $. \\
    3. Update: $\mathcal{C} \leftarrow \mathcal{C} \cup \{k^*\}$,  if $r(k^*) > \tau_2 $, else break.
    }
  \For{$n \leq N_m$}{ 
   
    Decay probabilities in video score matrix $S_m$,  $R_m[k,n] = \eta S_m[k,n]$,  $\forall k \notin  \mathcal{C}$.
  }
  $-$ Return refined video score matrix: $R_m$.
  \caption{Generating the Co-occurrence Matrix and the Refined Video Score Matrix.}
  \label{alg:selection}
\end{algorithm}

\textbf{Estimating the temporal path and decoding.} Having the refined video score matrix, the final step is to decode the frame sequences into the sub-action segments. Assume that we have a known temporal path of the clusters $k_1 \rightarrow ... \rightarrow k_T$, then the decoding is to maximize the probability of the sequence following this path based on our refined video score matrix, i.e.,  
\begin{equation}
\label{eq:decode}
\hat{l}_{l}^{N_m} = {argmax}_{l_1,...,l_{N_m}}\prod^{N_m}_{n=1} p(x_{mn}|l_n ) p(l_n | l_{n-1}),
\end{equation} 
where, $p(x_{mn}|l_n=k)$ is the probability of the frame $x_{mn}$ belonging to the cluster $k$, obtained from the refined video score matrix, and $p(l_n | l_{n-1}) $ are the transition probabilities of moving from the label  $l_{n-1}$  at frame $n-1$ to the next label $l_n$ at frame $n$. Given a temporal path, Eq.~(\ref{eq:decode}) can be solved with a Viterbi algorithm \cite{viterbi}. 

The temporal path estimation is the key for the decoding. While in weakly-supervised action segmentation the temporal path (i.e, the order of sub-actions) is usually assumed to be known, in unsupervised setting it can only be estimated. Previous work~\cite{kukleva2019unsupervisedtemporalembedding} proposed an estimation of the temporal path that is limited to be strictly single directional and each sub-action can appear at most once in the path. Such a path may suit for dataset with simple activity structures, e.g., Breakfast~\cite{breakfast}, 
however, begins to fail when the structure of activities gets more complex. For instance, a single sub-action may occur multiple times, and the order of the sub-actions can be bi-directional (i.e., sub-action $i$ can go to sub-action $j$ and then go back to $i$). 


We design a {\it multi-occur temporal path} that is suitable for more general cases,
using the cluster temporal location histogram introduced in Section~\ref{sec:cluster}. We first set a global threshold $\theta$, and for each cluster, we only select the bins from temporal location histogram with counts (normalized to the total counts across all the bins) larger than $\theta$.
Then we merge the selected bins from all the clusters and sort them based on the temporal location associated with each bin. The order of bins with their corresponding cluster labels forms our temporal path. Our multi-occur temporal path has the following advantages: (1) it is able to capture the multi-time occurrence for each cluster as well as the bi-direction transition among different clusters, because more than one bins from each cluster can be selected; (2) by adjusting the global threshold, it can control the length of the generated temporal path.







\section{Experiments}
\label{section:experiments}


\paragraph{Datasets.} We evaluate our approach on two most widely used datasets in action segmentation: Breakfast~\cite{breakfast} and 50Salads~\cite{salad}, and an emerging fine-grained action dataset FineGym~\cite{shao2020FineGym}. \textbf{Breakfast}~\cite{breakfast} is a large-scale dataset that consists of ten different complex activities 
of performing common kitchen activities with approximately eight sub-actions
per activity class. The duration of the videos varies significantly, e.g. `coffee' has an average duration of 30 seconds while `cooking pancake' takes roughly 5 minutes. 
\textbf{50Salads}~\cite{salad} dataset contains 4.5 hours of different people performing a single complex activity, making mixed
salad. Compared to the other datasets, the videos are much longer with an average video length of 10k frames. We also observe that a single sub-action can occur multiple times along the video in this dataset, which seldom happens in Breakfast. \textbf{FineGym}~\cite{shao2020FineGym} is an emerging dataset provided with fine-grained sports action annotations. Though it is originally proposed for fine-grained action recognition, it contains rich hierarchical information including annotations of start and end for the fine-grained sub-actions, which is suitable for action segmentation evaluation.  These sports videos contain several athletes performing the same action 
and their replays. The structure of the videos are more complex and it includes many re-occurrences of a single sub-action, and includes more similar fine-grained sub-actions (up to 35), which makes the dataset more challenging for action segmentation than typical ones used today. We use Gym99 setting in original paper.
The statistics of it is listed in supplementary material. We select 20 as bin size and $\theta$ is set as 0.15. They are depending on native attributes of actions in the dataset.



 \begin{table}[t]
 {
 \centering
 \begin{tabular}{@{} c|c|c @{}} 
  \hline
   \textit{Breakfast} & MoF & F1 score\\ 
   \hline
   \multicolumn{3}{l}{\textbf{Unsupervised setting}}      \\
   \hline
         GMM \cite{cvpr2018}&  0.346 & - \\
         LSTM + AL \cite{cvpr2019cnnrnn}&  0.429* & - \\
         CTE \cite{kukleva2019unsupervisedtemporalembedding} &  0.418 & 0.264   \\ 
      
       Ours &  \textbf{0.511}  &  \textbf{0.392} \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Weakly-supervised setting}}      \\
   \hline
         Action Sets \cite{actionsetscvpr2018} & 0.284  & - \\
         NNviterbi \cite{nnviterbi}&  0.430  & - \\
         SCT \cite{actionsetscvpr2020} & 0.304  & - \\
         SetViterbi \cite{setViterbi} &  0.408 & -   \\ 
          EnergySeg \cite{energyweaklyactionseg} &  0.630  & -   \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Fully-supervised setting}}      \\
   \hline
         HTK \cite{htk} & 0.259  & - \\
         GTRM \cite{gcnactionseg} & 0.650& - \\
         MS-TCN \cite{mstcn}&  0.663 & - \\
         BCN \cite{bcn} &  0.704  & -   \\ 
       \hline
 \end{tabular}
 \caption{Results on Breakfast.} 
 \label{tab:actionsegmentationBreakfast}
 }
 \end{table}



\paragraph{Evaluation Metrics.} Following \cite{kukleva2019unsupervisedtemporalembedding} we use the Hungarian algorithm \cite{hungarianalgorithm} to get a one-to-one matching that maximizes the similarity between all the clusters and sub-action classes for all the videos in evaluation. 
We report frame-wise accuracy as the \textit{mean over frames (MoF)}, indicating the percentage of frames correctly labelled.  
We also report \textit{F1 score} the same as \cite{kukleva2019unsupervisedtemporalembedding} to measure the quality of the temporal segmentation. 



\subsection{Comparison with SOTA}

We compare our approach with SOTA solutions on Breakfast in Table~\ref{tab:actionsegmentationBreakfast}, 50Salads in Table~\ref{tab:actionsegmentationSalads} and FineGym in Table~\ref{tab:actionsegmentationFineGym}. For all the datasets, We use SpeedNet~\cite{speednet} trained on the Kinetics-400~\cite{i3d} as the feature for our CAP algorithm. Details on feature comparison can be referred to the Section~\ref{sec:abfeature}. We can see our method achieves SOTA performance on both Breakfast and 50Salads datasets under unsupervised setting, with around 22\% and 14\% improvement on MoF correspondingly. Our method on Breakfast even outperforms most of the weakly-supervised solutions.  








 \begin{table}[t]
 {
 \centering
 \begin{tabular}{@{} c|c|c @{}} 
  \hline
   \textit{50Salads} & MoF &F1 score\\ 
   \hline
   \multicolumn{3}{l}{\textbf{Unsupervised setting}}      \\
   \hline
         LSTM + AL \cite{cvpr2019cnnrnn}&  0.606* &  - \\
         CTE \cite{kukleva2019unsupervisedtemporalembedding} &  0.355 &  -   \\
       Ours &  \textbf{0.414} &  \textbf{0.303} \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Weakly-supervised setting}}      \\
   \hline
         NNviterbi \cite{nnviterbi}&  0.494 &  - \\
          EnergySeg \cite{energyweaklyactionseg} &  0.547  & -   \\ 
       \hline
       \multicolumn{3}{l}{\textbf{Fully-supervised setting}}      \\
   \hline
         HTK \cite{htk} & 0.247 & \\
         GTRM \cite{gcnactionseg} & 0.826 & - \\
         MS-TCN \cite{mstcn}&  0.734 &  - \\
         BCN \cite{bcn} &  0.844 & -  \\ 
       \hline
 \end{tabular}
 \caption{Results on 50Salads. 
 Note that `*' uses a per-video instance cluster to ground-truth mapping, which uses additional video-level information, while we follow other work to use cluster to ground-truth mapping in a global manner in evaluation and do not use any additional information~\cite{vidalmata2020joint}.
 }

 \label{tab:actionsegmentationSalads}
 }
 \end{table}



 \begin{table}[t]
 {
 \centering
 \begin{tabular}{ @{} c|c|c @{}} 
  \hline 
   \textit{FineGym} & MoF & F1 score   \\ 
 \hline  
       Baseline~\cite{kukleva2019unsupervisedtemporalembedding} &  0.294  &  0.167   \\  
      
       Ours  &  \textbf{0.666} & \textbf{0.297}   \\  
       \hline
 \end{tabular}
 \caption{Results on FineGym.}
 \label{tab:actionsegmentationFineGym}
 }
 \end{table}


Since FineGym is new and we are the first to conduct action segmentation on it, there is no existing related results yet. We generate the baseline by running the SOTA apporach~\cite{kukleva2019unsupervisedtemporalembedding} on FineGym. We can see that on this emerging and more challenging dataset, our solution achieves even more improvement (127\% on MoF and 78\% on F1) comparing to the SOTA solution, demonstrating the effectiveness of our designed solution in handling videos with more complex structures. Overall the consistent improvement across all the benchmarks shows that our approach is able to be generalized to different cases. 




\subsection{Comparison of Feature Learning} 
\label{sec:abfeature}

We study three different self-supervised feature learning methods: (1) SpeedNet~\cite{speednet}, (2) RotationNet~\cite{rotationet}, and (3) ShuffleLearn~\cite{shufflelearn}, and compare the results on Breakfast dataset in Table~\ref{tab:differentmodelssinglecolumn}. All the numbers in the table are generated without using the co-occurrence matrix and the multi-occur temporal path, so that we can purely evaluate the effectiveness of features without bringing any additional factors.   



We conduct the experiments on self-supervised training (1) only on Kinetics dataset (i.e., (d) - (f)), (2) only on Breakfast dataset (i.e., (g) - (i)) and (3) first on Kinectics dataset and then on Breakfast dataset (i.e., (j) - (l)), to further explore that whether we need to train on target dataset (i.e., Breakfast in our case) to get a good feature representation for the task. From the table we can find that: 

(1) Based on experiment (a) - (l), we conclude that SpeedNet trained on Kinectics shown in (d) performs the best and gives better performance than SOTA as in (c); 

(2) Based on experiment (d) - (l), RotationNet consistently performs worse than SpeedNet and ShuffleLearn. This may due to the fact that RotationNet is using self-supervised signal from spatial dimension, which may lack of ability to model the temporal characteristics between frames. SpeedNet and ShuffleLearn, however, use temporal augmentation as the self-supervised signal, so that they may have stronger capability in modeling the temporal relations among frames and thus are more suitable for temporal action segmentation. The results also indicate that it is important to capture temporal relations among frames in feature learning for the segmentation task. In addition, SpeedNet, as one of the most emerging and successful video self-supervised learning approaches, consistently outperforms the ShuffleLearn, showing the effectiveness of it; 

(3) Based on experiment (b), (d), (e), (f), self-supervised features always perform better than classical I3D feature pre-trained on Kinetics. We argue that 
while the I3D feature trained for action recognition task optimizes feature representation on video clip level, self-supervised learning representation implicitly learns better frame-level representation and can better capture the temporal structure inside the clip;  


(4) Based on the experiments (d) - (l), we can see larger dataset like Kinetics can help build better self-supervised representation, while smaller ones contain less variety. It's not needed to use target dataset to get a good feature representation for the temporal action segmentation task. 



\begin{table}[t]
{
\centering
\begin{tabular}{@{} c|c|c|c@{}} 
 \hline
   & Feature Description  & MoF & F1\\ 
   \hline
   \multicolumn{4}{l}{\textbf{Baseline}}      \\
   \hline
  (a) &  IDT \cite{kukleva2019unsupervisedtemporalembedding} &      0.316 &    -   \\ 
  (b) &     K400 I3D  \cite{kukleva2019unsupervisedtemporalembedding}&      0.251 &  -     \\ 
  (c) &     CTE  \cite{kukleva2019unsupervisedtemporalembedding} &      0.418 &    0.264   \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised on K400}}      \\
   \hline
  (d) &    K400 SpeedNet &      \textbf{0.508} &    \textbf{0.391}   \\ 
  (e) &     K400 RotationNet &       0.328 &     0.317   \\ 
  (f) &      K400 shuffleLearn &    0.339    &   0.328     \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised on Breakfast}}      \\
   \hline
  (g) &     Breakfast SpeedNet &     0.344 &    0.327   \\ 
  (h) &      Breakfast  RotationNet&      0.307 &  0.319     \\ 
  (i) &      Breakfast shuffleLearn &      0.315 &      0.309 \\ 
  \hline
  \multicolumn{4}{l}{\textbf{Self-supervised first on K400, then on Breakfast}}      \\
   \hline
  (j) &      K400, Breakfast, SpeedNet &      \underline{0.501} &    \underline{0.337}   \\ 
  (k) &     K400, Breakfast, RotationNet &      0.279 &  0.290     \\ 
  (l) &      K400, Breakfast, shuffleLearn &      0.292 &    0.318   \\ 

 \hline
\end{tabular}
\caption{Comparison of features for temporal action segmentation.  `K400' denotes features trained on Kinetics \cite{i3d} dataset while `Breakfast' represents features trained on Breakfast \cite{breakfast} dataset. `SpeedNet', `RotationNet' and `ShuffleLearn' denote features trained using the self-supervised methods from \cite{speednet}, \cite{rotationet} and \cite{shufflelearn}. }
\label{tab:differentmodelssinglecolumn}
}
\end{table}







\begin{table}[t]
{
\begin{center}
\begin{tabular}{@{}  c | c  c c  | c | c @{}} 
 \hline 
 Dataset   & Feat & C-Matrix & M-T-Path & MoF & F1  \\ 
\hline  
 \multirow{4}{*}{\textit{Breakfast}}  &     &  &    &  0.418  & 0.264  \\  
    &  \checkmark  &   &    &  0.508  & 0.391  \\  
      
      & \checkmark &    \checkmark  &   
 &  0.511  & 0.392  \\  
        
         &  \checkmark &  \checkmark  &   \checkmark  &  \textbf{0.511}  &  \textbf{0.392} \\  
       \hline  
    \multirow{4}{*}{\textit{50Salads}} &      &   &    &  0.355  & -  \\  
    &   \checkmark   &   &    &  0.372  & 0.281  \\  
      
        & \checkmark &  \checkmark  &    &  0.378  &  0.290 \\  
        
          &   \checkmark  & \checkmark  & \checkmark  &  \textbf{0.414}  & \textbf{0.303}  \\  
          
        
        \hline  
    \multirow{4}{*}{\textit{FineGym}}      &          & &  &  0.294  &  0.167 \\  
    &      \checkmark    & &  &  0.425  &  0.246 \\  
      
         &  \checkmark &  \checkmark  &   &  0.442  &  0.248 \\  
        
          &   \checkmark   & \checkmark &  \checkmark  & 
          \textbf{0.666}  &  \textbf{0.297} \\  
         
         
     
     
      \hline  
\end{tabular}
\end{center}
\caption{Ablation study on all datasets. `Feat' denotes whether to use the SpeedNet feature trained on K400; `C-Matrix' denotes whether to use the  \textit{co-occurrence matrix} to refine the video score matrix; and `M-T-Path' denotes whether to use our designed \textit{multi-occur temporal path} in decoding. If none of them is selected then it's a baseline setting from~\cite{kukleva2019unsupervisedtemporalembedding}.} 
\label{tab:betterdecoding}
}
\end{table}

\subsection{Ablation Study on CAP} 

Next, we conduct ablation studies on our CAP algorithm. Two main units are investigated: (1) Co-occurrence Matrix; (2) Multi-occur Temporal Path. 

\textbf{Effectiveness of Co-occurrence Matrix.}
We evaluate the influence of using the co-occurrence matrix to refine the video score matrix in Table~\ref{tab:betterdecoding} on all datasets. From the table, our co-occurrence matrix brings performance improvement over using original video score on all of the three datasets and on both \textit{MoF} and \textit{F1}. 
The improvement on FineGym dataset is more notable than the other two, indicating the importance of using the co-occurrence matrix while handling more complex scenarios.



\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\textwidth}
   \centering
  \includegraphics[width=.95\linewidth]{quali3_2.pdf} 
  \caption{P24 friedegg sequence from Breakfast dataset. The semantics order are `background', `crack egg',`fry egg', `take plate', `put egg2plate', `background'.}
  \label{fig:qualitativec}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.48\textwidth}
   \centering
  \includegraphics[width=.95\linewidth]{quali4_2.pdf}
  \caption{P38 juice sequence from Breakfast dataset. The semantics order are `background', `cut orange', `squeeze orange',`take glass',`pour juice',`background'.}
  \label{fig:qualitatived}
\end{subfigure}
\caption{Two qualitative examples (a) and (b). The first row is the frame-wise ground-truth (x-axis stands for the time in the video while different sub-action classes are colorized differently); the second row is the prediction from \cite{kukleva2019unsupervisedtemporalembedding}; the third row is our prediction; and the fourth row is the uniform sampled 8 frames from the original video. Best viewed zoom in and in color.}
\label{fig:qualitativeall}
\end{figure}



\textbf{Effectiveness of Multi-occur Temporal Path.} We then assess the impact of using the proposed multi-occur temporal path in decoding. Results on all three datasets are in table~\ref{tab:betterdecoding}.  
We can see the designed multi-occur temporal path decoding improves both \textit{MoF} and \textit{F1} on 50Salads and FineGym, but does not on Breakfast.
We observe that the multi-occurrence of one sub-action in the same video happens more frequently in 50Salads and FineGym, while in Breakfast, most of the sub-actions only occur once in each video, therefore, the multi-occur temporal path is not as helpful on Breakfast as on the other datasets. It is worth to mention that our CAP algorithm actually generates an exact the same temporal path (with each sub-action occurring only once) automatically as turning off the function for the Breakfast, representing that the CAP algorithm is self-applicable to different scenarios.

\subsection{Qualitative Results}

Fig.~\ref{fig:qualitativeall} visualizes two examples from Breakfast dataset. From both Fig.~\ref{fig:qualitativec} and Fig.~\ref{fig:qualitatived} we can see that our CAP algorithm is able to effectively suppress the over-segmentation issue in baseline by introducing the co-occurrence relations among sub-actions in decoding.  



\section{Conclusion}
\label{section:concolusion}
In this work, we have shown that using self-supervised methods in feature learning can effectively improve the performance of unsupervised temporal action segmentation. We have also proposed a CAP algorithm that helps model the co-occurrence among sub-actions and can better handle complex activity structures in videos. 
Our approach has achieved SOTA performance on three public benchmarks in unsupervised setting, and even outperform several recently proposed weakly-supervised methods. The future direction can be leveraging the deep clustering approaches in further improving the accuracy of the task.  


\section*{Acknowledgement}
We thank reviewers for the 
valuable suggestions. Zhe Wang personally thanks Fanyi Xiao,  Bing Shuai and Uta Büchler for helpful discussion

{\small
\bibliographystyle{ieee_fullname}

\section{Related Work}
\label{section:relatedwork}



\textbf{Temporal action segmentation} is a task to classify each frame in an untrimmed video with a label of action. It is a key for understanding structures of complex activities. While current techniques have achieved great success on other action understanding tasks such as action recognition~\cite{i3d,feichtenhofer2019slowfast,feichtenhofer2016convolutional,tran2015learning,yang2020temporal,wang2016temporal,zhou2018temporal,lin2019tsm,wang2018non,gmmhmm} and action detection~\cite{lin2018bsn,zhao2017temporal,xu2017r,hou2017tube}, temporal action segmentation is still far from being well-explored. Today's high performing solutions for temporal action segmentation require full frame-level supervision~\cite{mstcn,gcnactionseg,htk,bcn,lea2016segmental,lea2017temporal}. 
However, acquiring annotations on fine-grained sub-actions for each frame is expensive. To reduce the amount of labeled data needed,~\cite{sstda} proposes a domain adaptation approach based on self-supervised auxiliary tasks and achieves good performance. More recent works focus on developing weakly-supervised solutions: instead of having supervision for every frame, only the list (with order information)~\cite{firstunsuper,energyweaklyactionseg,nnviterbi,Richard_2017_CVPR,ding2018weakly,huang2016connectionist,chang2019d3tw} or the set (without order information)~\cite{actionsetscvpr2020,setViterbi,actionsetscvpr2018} of the sub-actions are required during training. Other work uses script
or instructions for weak annotation~\cite{alayrac2016unsupervised}.


\textbf{Unsupervised temporal action segmentation} starts to receive growing interests these days, to further reduce the dependence on labeled data.~\cite{UnsuperProcLearn} builds a joint sequential subset selection method to produces a summary of the procedure key-steps in instructional videos.~\cite{cvpr2018} learns a function assigning sub-activity scores to frame features and models the distribution over sub-activity permutations by a Generalized Mallows Model.~\cite{cvpr2019cnnrnn} proposes a self-supervised predictive learning with recurrent neural networks (RNN) by utilizing features of adjacent frames to find the action boundaries.~\cite{kukleva2019unsupervisedtemporalembedding} proposes a combination of temporal embedding generated using a frame timestamp prediction network, feature clustering and Viterbi decoding for consistent frame-to-cluster assignment. However, these solutions do not take into account the semantic correlations among sub-actions and the re-occurrence of sub-actions in some complex activity structures.







\textbf{Self-supervised learning of visual representation} is a hot topic today, and has shown success in some of action understanding tasks~\cite{lstmunsupervisedfaeture,Deeo_Clustering,speednet,fernando2017self}.  Many different video properties have been used as supervision to build good representations, such as: cycle consistency between video frames \cite{xiaolongcvpr2019}; distinguishing between a video frame sequence and a shuffled version of it \cite{shufflelearn}; predicting the order of the shuffled clips \cite{cliporder}; solving space-time cubic puzzles \cite{spacetimecubicpuzzles}; classifying the speed of the video \cite{speednet,speednetMIT}; recognize the rotation of the video \cite{rotationet}. Another common task is predicting the future, either by predicting pixels of future frames \cite{motionnet}, or an embedding of a future video segment \cite{pdc}. While today's action segmentation solutions~\cite{mstcn,kukleva2019unsupervisedtemporalembedding,bcn} still mainly rely on hand-crafted features such as IDT~\cite{idt}, Fisher Vector (FV)~\cite{fishervector}, or pre-trained features such as I3D on Kinetics dataset~\cite{i3d}, we believe that introducing self-supervised methods in feature representation learning for unsupervised action segmentation can significantly boost the performance, as it can not only bring strong discriminative power to the features, but also bring a chance to improve the temporal characteristics of the features. 
