<figure><img src="image_1.png" /></figure>

HAL
open science

# A Simple and Powerful Global Optimization for
Unsupervised Video Object Segmentation

Georgy Ponimatkin, Nermin Samet, Xiao Yang, Yuming Du, Renaud Marlet, Vincent Lepetit

► To cite this version:

Georgy Ponimatkin, Nermin Samet, Xiao Yang, Yuming Du, Renaud Marlet, et al.. A Simple and Powerful Global Optimization for Unsupervised Video Object Segmentation. IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), Jan 2023, Hawai, United States.
10.1109/wacv56688.2023.00584.1. hal-04323148

HAL Id: hal-04323148

https://hal.science/hal-04323148v1

Submitted on 8 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A Simple and Powerful Global Optimization for
Unsupervised Video Object Segmentation

Georgy Ponimatkin<fnref n="1" /> Nermin Samet<fnref n="1" /> Yang Xiao<fnref n="1" /> Yuming Du<fnref n="1" /> Renaud Marlet<fnref n="1" />,² Vincent Lepetit<fnref n="1" />

¹LIGM, Ecole des Ponts, Univ Gustave Eiffel, CNRS, Marne-la-Vallée, France ²Valeo.ai, Paris, France

georgy.ponimatkin@enpc.fr

Code and supplementary material: https://ponimatkin.github.io/ssl-vos

## Abstract

We propose a simple, yet powerful approach for unsupervised object segmentation in videos. We introduce an objective function whose minimum represents the mask of the main salient object over the input sequence. It only relies on independent image features and optical flows, which can be obtained using off-the-shelf self-supervised methods. It scales with the length of the sequence with no need for superpixels or sparsification, and it generalizes to different datasets without any specific training. This objective function can actually be derived from a form of spectral clustering applied to the entire video. Our method achieves on-par performance with the state of the art on standard benchmarks (DAVIS2016, SegTrack-v2, FBMS59), while being conceptually and practically much simpler.

## 1. Introduction

While the two research communities working on unsupervised video object segmentation [50, 1, 91, 49] and on object discovery [76, 87, 41, 67] often remain separated, they share the goal of segmenting objects in visual data without depending on manual labels for these objects. This ability is essential to autonomous systems for evolving and interacting in open world. It is also a fundamental problem for Computer Vision as humans have the ability to learn about new objects without guidance.

Object appearance and motion are important cues to achieve this task. However, many challenges remain: Objects can share similar appearance with the background, their visual appearance may not be uniform, and different parts can move in different directions. As a result, many methods still rely on some sort of supervision, at least for learning to extract visual features.

We present here a simple approach to unsupervised video object segmentation. It leverages recent progress on unsupervised learning in a simple but powerful, novel optimization scheme over the objects' masks. We start from

<figure><img src="image_3.png" /><figcaption>Figure 1: (a) Segmentation obtained by our spectral clustering formulation on the self-supervised image features from DINO [9] in a single frame. (b) Segmentation obtained using the same self-supervised image features and optical flow from ARFlow [46], but still from a single frame. (c) Final segmentation obtained with our complete method, after optimization on the full frame sequence, using the same features and optical flow estimated by ARFlow.</figcaption></figure>

self-supervised features such as DINO [9], MoCo-v3 [14], SWAV [8] or Barlow Twins [94] as the appearance cue, and the optical flow from methods such as RAFT [73] or ARFlow [46]. DINO, MoCo-v3, SWAV, Barlow Twins and ARFlow methods are “self-supervised” or “unsupervised”, in the sense that they do not use any manual annotations, making our method also entirely unsupervised.<fnref n="1" />

Used alone, the DINO features can already provide a surprisingly good segmentation of the objects, but still below the state of the art, in particular for videos. Yet, with our optimization scheme, we can reach a performance that is on par or even better than much more sophisticated methods.

Our optimization starts from an initial estimate for the object's mask in each frame of the input sequence. It then optimizes the masks over the whole video sequence. We show that our optimization function can be derived from spectral clustering over the video sequence. Yet, spectral clustering is difficult to make tractable for long sequences as it requires computing one of the eigenvectors of a huge matrix [65, 52]. To obtain a tractable problem, previous methods based on spectral clustering rely on superpixels [27] or graph sparsification [39]. However, superpixels may in-

<footnote n="1">¹The terminology is still fluctuating, as the DINO method is called “self-supervised” in the original paper, while ARFlow is called “unsupervised”. Throughout the paper, we will use self-supervised and unsupervised in the sense of “not using manual annotations”.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: **Generalization to new datasets.** Relying on spectral clustering rather than learning generalizes better to new datasets. (a) The learned method of [87] performs poorly on a new sequence. (b) Spectral clustering on the *same* optical flow performs significantly better, even without optimization. (c) Result of our complete method.</figcaption></figure>

troduce artefacts at object boundaries, and both superpix-
els and sparsification require careful parameter tuning. Be-
sides, even using fast methods to extract relevant eigenvec-
tors, such as Power Iteration Clustering (PIC) [44], the com-
plexity of these formulations is a *priori* quadratic in the
length of the sequence (depending however on sparsity).
In contrast, our method only needs eigenvectors computed
for each frame independently, based on image features and
optical flow for the frame, thus essentially scaling linearly
with the number of frames. In short, our approach yields a
tractable approximation of spectral clustering over the en-
tire sequence. Concretely, on videos from the DAVIS2016
dataset [60], our method is on average ~170× faster than
our full spectral clustering counterpart, i.e., TokenCut [82].

Importantly, for practical applications, our method can
be applied to different datasets without retraining. This is in
contrast with learning-based segmentation approaches. As
illustrated in Fig. 2, they do not generalize well to new data.

To summarize, our contribution is the derivation of a
novel objective function from spectral clustering, which
results in a simple and efficient optimization method for
object discovery and segmentation in videos. Moreover,
our method is arguably the first that relies purely on self-
supervised features, without the need of any manual an-
notation. Still, it outperforms previous methods on several
standard challenging datasets, including some methods that
only rely on supervised training. Last, it can directly be ap-
plied to different datasets, without any training or tuning.

## 2. Related Work

We discuss here works on object discovery and unsuper-
vised video object segmentation, as both are closely related
to our work. We also discuss works on unsupervised feature
learning, which we rely on for image feature extraction.

### 2.1. Object Discovery

Object discovery aims to localize the objects in images or
videos. Some works rely on a collection of images contain-
ing objects of the same class and localize these objects using

clustering [24], image matching [63, 16], topic discovery
[64, 68] or optimization for selecting region proposals [76].
One limitation of these works is that such a collection could
be difficult to obtain, and its quality would heavily impact
performance. Du *et al.* [22] proposes to discover and seg-
ment objects from unseen classes based on instance masks
predicted by models trained only on seen classes, while our
method does not need any supervision.

Recently, some works [48, 5, 28] adopt a bottom-up ap-
proach and segment the object in the images by exploiting
the similarity among pixel colors or patch features. These
works have only demonstrated their performance on syn-
thetic images and can be easily affected by image texture
or colors. In contrast, our approach aims to discover objects
using unlabeled in-the-wild videos without any supervision.

[87, 41] and [30] can also be considered as object dis-
covery methods, as their goal is to segment the primary
objects given some video sequences. [87, 41] propose to
use an attention-based network to compute the trajectory
embeddings from optical flow only. One major limitation
of [87, 41] is that optical flow is not sufficient to segment
static objects. Besides, even though [87, 41] do not require
any labeled data, they still have to train their network with
different strategies on different datasets, which makes it dif-
ficult to generalize, as show in Figure 2. As we will show
in Section 4, our method does not need any training and can
achieve good results on all the benchmarks.

IKE [30] proposes an iterative refinement approach: In the first stage, the videos are first fed into a graph module for mask initialization. Then, in the second stage, the initialized masks are used to train a segmentation network, whose predictions are used as initialization for the graph module in the first stage. In the first stage, optical flow is used to generate long-term space-time trajectories. Optical flow can be very noisy and thus it may be difficult to obtain long trajectories reliably in general. We will show in the Experiments section that our method can achieve better results compared to [30] while at the same time being simple. Some methods [87, 41, 90] are also presented as self-supervised or unsupervised while they actually rely on supervised optical flow methods such as RAFT [73]. In comparison, our method is able to achieve state-of-the-art performance while only using self-supervised optical flow learned from videos.

## 2.2. Unsupervised Video Object Segmentation

Given a video sequence, Unsupervised Video Object
Segmentation (UVOS) aims to consistently segment and
track the most salient objects in the video without any hu-
man intervention. The approaches for UVOS can be divided
into two categories depending on whether they need labeled
data or not. Methods such as [50, 91, 49, 1, 81, 56, 43, 77,
51, 59, 79, 70] use either labeled images or labeled videos
to train their networks for video segmentation. In addition, some works [96, 85, 89, 62, 95, 88, 37, 75, 15, 66, 36, 75] also exploit low-level cues such as object boundaries to get better mask predictions. One main limitation of these methods is that they rely heavily on their large-scale well-annotated training data, which can be hard to get in practice. In contrast, our proposed method is entirely self-supervised and does not need any labeled data.

There are also several works [25, 18, 57, 2, 4, 61, 38, 54, 69, 90, 80, 87, 92] that can segment the primary objects in the video without any labeled data. One major limitation of all these works is that they all consider that the pixels on the objects in the video share similar motion patterns, thus, their methods can fail when the objects are static or move with the same speed as the background, while our proposed method combines the appearance cues and the motion cues and can largely alleviate this issue.

Currently, DyStaB [89] is the best performing unsupervised method for video object segmentation. The method consists of three parts: A static model and a dynamic model (both based on DeepLab backend [10]), together with an inpainer network based on [90]. The three networks are jointly trained via an adversarial loss in an iterative fashion to obtain final segmentation results and a significant post-processing via CRF is utilized. In comparison, our approach does not require training—besides for the image features and optical flow that can be obtained out-of-the-shelf—while an adversarial loss can be difficult to train. More importantly, our approach is much simpler, while achieving a similar performance to DyStaB.

## 2.3. Self-Supervised Learning

Recent self-supervised approaches [84, 11, 21, 31, 13, 29, 9] propose to train a feature extraction network using an instance classification pipeline, which treats each image as a single class and trains the network to distinguish images cropped from a large image collection without any manual annotation. In particular, DINO [9] introduced an approach which makes a network trained in a self-supervised manner learn class-specific features.

Motivated by this ability, discovering objects in images using self-supervised features recently gained attention [82, 53, 67]. LOST [67] utilizes self-supervised features within a seed selection and expansion strategy and localizes the main object given an image. Closely related to LOST, TokenCut [82] and Deep Spectral Methods (DSM) [53] propose graph-based methods that use self-supervised transformer features to discover and segment salient objects. TokenCut [82] builds a graph where visual tokens are nodes and similarity scores between tokens are edges of a weighted graph. They formulate the segmentation problem as a normalized graph cut and solve it using spectral clustering with eigendecomposition. Similar to

TokenCut [82], inspired from traditional spectral segmentation methods, DSM [53] first constructs a Laplacian matrix which is a combination of color information and self-supervised transformer features. Next, the image is decomposed using the eigenvectors of the Laplacian matrix.

Our method is similar to these methods as we also aim to detect and segment salient objects based on a graph formulation. There are two key differences: (i) We aim to discover objects in videos rather than still frames and in order to ensure the temporal consistency, we extend the affinity matrix with optical flow to establish inter-frame connectivity; (ii) We introduce a novel method for optimizing on the entire video efficiently. Moreover, we show that using power iteration clustering [44] instead of full eigenvector decomposition for spectral clustering as we do results in significantly faster run time (0.1s/frame vs. 17s/frame).

# 3. Method

## 3.1. Method Overview

We consider a sequence of N video frames of size $H \times W$, where H and W are the number of rows and columns of a frame. The segmentation of the main salient object, in each frame p, is modeled as a soft, vectorized image mask $\mathbf{x}_p \in \mathbb{R}_+^{HW}$. The actual image mask at frame p is recovered by splitting the pixels into two clusters based on $\mathbf{x}_p$, separating the object of interest from the background.

We assume that we are given a rough mask estimate $\hat{\mathbf{x}}_p$ in each frame p, as well as functions $w_p^q(\mathbf{x}_p)$ warping a mask $\mathbf{x}_p$ in frame p to frame q using the optical flow from p to q. Then, the objective function we minimize is:

$$ \mathcal{L}(\{\mathbf{x}_p\}_p) = \sum_p \lambda \mathrm{CE}(\hat{\mathbf{x}}_p, \mathbf{x}_p) + \mathrm{CE}(\mathbf{x}_{p+1}, w_p^{p+1}(\mathbf{x}_p)) + \mathrm{CE}(\mathbf{x}_p, w_{p+1}^p(\mathbf{x}_{p+1})), \quad (1) $$

where $\mathrm{CE}(\cdot)$ denotes the cross-entropy.

Intuitively, $\mathrm{CE}(\hat{\mathbf{x}}_p, \mathbf{x}_p)$ expresses the deviation between a mask $\mathbf{x}_p$ and the initial mask estimate $\hat{\mathbf{x}}_p$; $\mathrm{CE}(\mathbf{x}_{p+1}, w_p^{p+1}(\mathbf{x}_p))$ expresses the deviation between mask $\mathbf{x}_{p+1}$ and the warping of mask $\mathbf{x}_p$ by flow $w_p^{p+1}$, and reciprocally for $\mathrm{CE}(\mathbf{x}_p, w_{p+1}^p(\mathbf{x}_{p+1}))$; finally, $\lambda$ is a constant weight to balance the significance of both kind of deviations (difference from initial mask vs flow discrepancy).

As illustrated in Figure 3, our objective function can be interpreted easily: The optimization starts from a first estimate of the mask for each frame of the sequence; it encourages the mask in frame p to align with the mask in frame $p+1$ after being warped by the optical flow from frame p to frame $p+1$, and vice versa, while keeping the masks close to their initialization.

This approach can in fact be derived from a formulation of the problem in terms of spectral clustering, which also provides a way to compute initial estimates $\hat{\mathbf{x}}_p$. We present this formulation and the derivation of our approach below.
<figure><img src="image_5.png" /><figcaption>Figure 3: **Overview of our approach.** Given a video sequence, starting from first estimates for the object masks obtained by spectral clustering on each image independently, we optimize the masks so that they remain close to the first estimates while being consistent with the optical flow. The objective function we optimize to retrieve the masks can be derived from spectral clustering applied to the video sequence. Our method can rely on self-supervised visual features only.</figcaption></figure>

## 3.2. Vanilla Spectral Clustering for Segmentation

We first briefly present spectral clustering, in the context of image segmentation as done in [65, 52], for example. We then discuss how it can be extended to video segmentation. The reader interested in more details about spectral clustering can refer to the tutorial in [78].

For image segmentation with spectral clustering, one considers an affinity matrix we will denote $\mathcal{A}$. Each row and each column of $\mathcal{A}$ corresponds to an image location. The coefficient $A_{ij} \ge 0$ on row $i$ and column $j$ should express how likely image location for row $i$ and image location for column $j$ belong to the same cluster. In the following, we will identify the row and column indices $i$ and $j$ with the corresponding image locations for simplicity.

According to spectral clustering theory, a good segmentation mask can be obtained from the second largest eigenvector $\mathbf{X}_2$ of the normalized affinity matrix $\mathcal{W}$ defined as

$$ \mathcal{W} = \mathcal{D}^{-1} \mathcal{A}, \qquad (2) $$

where $\mathcal{D} = \text{diag}(\{\sum_j A_{ij}\}_i)$ is the degree matrix. The coefficients of $\mathbf{X}_2$ correspond to image locations. By thresholding them, one obtains a binary mask for the segment.

To extend this approach to object segmentation in videos, we also start from an affinity matrix $\mathcal{A}$. Each row of $\mathcal{A}$, and each column, corresponds to an image location in a video frame. We will denote the coefficients of $\mathcal{A}$ with $A_{(pi)(qj)}$; $(pi)$ is a notation for the index of row corresponding to image location $i$ in frame $p$; similarly $(qj)$ is the index for column corresponding to image location $j$ in frame $q$. Coefficients $A_{(pi)(qj)}$ should express how likely image location $i$ in frame $p$ and image location $j$ in frame $q$ are to correspond to the same object. For this, we will use the similarity between their local image features and optical flow.

However, this results in a very large $\mathcal{A}$ matrix, and thus also a very large $\mathcal{W}$ matrix. of size $NHW \times NHW$, which is in the order of $10^9 \times 10^9$ for typical sequences in standard benchmarks. This is clearly too large in practice both

for storage and for eigenvector computation. Some methods exploit superpixels [27] or graph sparsification [39] to decrease the computational complexity, but it complicates the approach; our method is more direct and more scalable. Another approach [52] is to retrieve the second largest eigenvector $\mathbf{X}_2$ with the classical problem:

$$ \mathbf{X}_2 = \arg \max_{\mathbf{x}} \mathbf{X}^{\top} \mathcal{W} \mathbf{x} \text{ such that } \|\mathbf{x}\|_2 = 1, \quad (3) $$

which could be approximately but efficiently computed using Power Iteration Clustering (PIC) [44]. However, it still cannot be scaled for common video lengths.

Nevertheless, as described below, we draw on this approach: Instead of building $\mathcal{W}$ explicitly and struggling to compute its second largest eigenvector $\mathbf{X}_2$, we compute eigenvectors $\hat{\mathbf{x}}_p$ by PIC for each frame $p$ independently, for scalability. We use data that include inter-frame information to reinforce temporal consistency which leads to greater accuracy. This makes our initialization scheme similar to TokenCut [82], except that we utilize approximate eigenvector extraction instead of full spectral decomposition as well as inclusion of optical flow connectivity between adjacent frames. In Table 1(b), we show differences between using the baseline TokenCut method and our approximation without optical flow. These initial masks are refined using additional inter-frame consistency constraints, resulting in an optimization problem that is much more tractable than the originating spectral clustering problem.

In the following, we introduce a suitable affinity matrix $\mathcal{A}$, that we use in two ways: to efficiently compute good initial estimates $\hat{\mathbf{x}}_p$, and to derive the formulation in Eq. (1) as a simplification of term $\mathbf{X}^{\top} \mathcal{W} \mathbf{x}$ we wish to maximize.

## 3.3. Affinity Matrix for Video Object Segmentation

Our affinity matrix $\mathcal{A}$ relies both on object appearance features and on optical flow features:

**Appearance features.** For these, we use an image feature extractor that generates an appearance feature vector $\psi_p^i$ of
the object at location *i* of frame *p*. The idea is that the features at different locations of the same object should tend to look alike, while differing from the features located on other objects or on the background. Such appearance features can typically be learned using a dataset of annotated objects or, as in our case, using a self-supervised method such as DINO [9] or MoCo [14].

**Optical flow features.** We use an image flow extractor that yields the optical flow $\phi_{p,q}^i \in \mathbb{R}^2$ at location $i$ between frame $p$ and frame $q$: What is seen at location $i$ in frame $p$ is also seen at location $j = i + \phi_{p,q}^i$ in frame $q$. Such an optical flow can typically be obtained using various gradient-based formulations [26], or learned using a dataset of annotated flows [73, 71, 19, 34]. It can also be obtained, as in our case, using a self-supervised method such as ARFlow [46].

**Affinity matrix.** We define our affinity matrix as follows:

$$ \mathcal{A} = \begin{bmatrix} A_1 \ \bar{F}_1 & 0 & \dots & 0 \\ F_1 \ A_2 \ \bar{F}_2 & \ddots & \vdots & \\ 0 & F_2 \ A_3 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots \\ 0 & \dots & 0 & F_{N-1} \ A_N \end{bmatrix}. \quad (4) $$

Each block is a $HW \times HW$ matrix. It contains the affinities between image locations in a frame and image locations in the same frame or in another one. We detail below matrices $A_p$, $F_p$ and $\bar{F}_p$, and justify the use of 0 matrices.

**Matrices $A_p$.** Each matrix $A_p$ on the block diagonal of $\mathcal{A}$ contains the affinities between two image locations in the same frame $p$. It is based not only on object appearance features within frame $p$, but also on information from the preceding and succeeding frames $p-1$ and $p+1$. Concretely, we take the affinity $A_p^{i,j}$ between locations $i$ and $j$ in frame $p$ as the following combined similarity of their object appearance features and their forward and backward flows:

$$ A_p^{i,j} = \frac{1}{\alpha_\psi + 2\alpha_\phi} g_s \left( \alpha_\psi \langle \psi_p^i, \psi_p^j \rangle + \alpha_\phi \left( \langle \phi_{p,p+1}^i, \phi_{p,p+1}^j \rangle + \langle \phi_{p,p-1}^i, \phi_{p,p-1}^j \rangle \right) \right), \quad (5) $$

where $\alpha_\psi$ and $\alpha_\phi$ are relative weights, and $g_s(\cdot)$ is a thresholding function that zeroes values lower than $s$. We use $s > 0$ to guarantee that the coefficients of $A_p$ are positive.

**Matrices $F_p$ and $\bar{F}_p$.** Each matrix $F_p$ stores affinities between image locations in frame $p$ and image locations in frame $p+1$. Here, we only consider the optical flow between frames $p$ and $p+1$, and ignore the information given appearance features. (Using appearance features as well might improve the results, but it would lead to a much more complex optimization problem.) Two locations $i$ and $j$ in

frames $p$ and $p+1$ are likely to both belong to the same object or both lie on the background if the optical flow maps one to the other. In that case, their affinity $F_p^{i,j}$ should be large, close to 1; otherwise, we set it to 0. We thus take:

$$ F_p^{i,j} = \begin{cases} 1 & \text{if } i + |\phi_{p,p+1}^i| = j \\ 0 & \text{otherwise} \end{cases}, \quad (6) $$

where $|\phi|$ is the vector of nearest integers to $\phi$. $\bar{F}_p$ is defined likewise using the optical flow from frames $p+1$ to $p$.

If $\mathbf{x}$ denotes a 2D mask in vector form, then $F_p \mathbf{x}$ is “almost” the mask $w_p^{p+1}(\mathbf{x})$ after warping by the optical flow from frame $p$ to frame $p+1$, up to the integer discretization in Eq. (6). It also applies to $\bar{F}_p \mathbf{x}$ and $w_{p+1}^p(\mathbf{x})$.

The spectral clustering purist may notice that this expression for $F_p$ and $\bar{F}_p$ makes the affinity matrix $\mathcal{A}$ not symmetric. However, $\bar{F}_p$ is almost equal to $F_p^\top$; they are slightly different because (1) optical flow is not exactly a bijection, as some pixels can appear or disappear, and (2) the predicted flow from frame $p$ to $p+1$ is not exactly the inverse of the predicted flow from $p+1$ to $p$. In practice, we may consider that the affinity matrix $\mathcal{A}$ is “almost” symmetric.

**Matrices 0.** Matrices that do not belong to the tri-diagonal of matrix $\mathcal{A}$ contain affinities between image locations in two “distant”, i.e., non-consecutive frames. Here, we ignore the information provided by the appearance features and the optical flow, resulting in the zero matrix. Being able to exploit the appearance features would probably slightly improve the final segmentation, but would also make the optimization significantly less scalable and more complex. Ignoring the optical flow between distant frames is a safe thing to do anyway, as its estimation is likely unreliable.

## 3.4. Deriving the Objective Function

By expanding the term $\mathbf{X}^\top \mathbf{W} \mathbf{X}$ found in Eq. (3), using the definition of the normalized affinity matrix $\mathcal{W}$ in Eq. (2), the notation $\mathbf{X}$ for its second eigenvector, and the definition of the affinity matrix $\mathcal{A}$ in Eq. (4), we obtain:

$$ \mathbf{X}^\top \mathbf{W} \mathbf{X} = \sum_p \mathbf{x}_p^\top D_p^{-1} A_p \mathbf{x}_p + \sum_p \mathbf{x}_{p+1}^\top D_{p+1}^{-1} F_p \mathbf{x}_p + \sum_p \mathbf{x}_p^\top D_p^{-1} \bar{F}_p \mathbf{x}_{p+1}, \quad (7) $$

where the $D_p$ matrices are on the block diagonal of $\mathcal{D}$ and are themselves diagonal.

Computing this expression seemingly involves the products between matrices $A_p$, $F_p$ and vectors $\mathbf{x}_p$. It would require large amounts of memory and be prohibitively slow as these matrices are very large. However, we show that we do not need to store these matrices, nor do we need to compute these products for estimating masks $\mathbf{x}_p$.

The terms $\mathbf{x}_p^\top D_p^{-1} A_p \mathbf{x}_p$, when considered independently, lead to a spectral clustering problem per frame. The
second eigenvector $\hat{x}_p$ of matrix $W_p = D_p^{-1}A_p$ is in practice a good first estimate of $x_p$, thanks to the combination of the object appearance features and the optical flow.

In the supplementary material, we also show that when $x_p$ is close to $\hat{x}_p$, then:

$$x_p^\top D_p^{-1} A_p x_p \approx (\hat{x}_p)^\top x_p. \qquad (8)$$

Furthermore, as mentioned in Section 3.3, the terms $F_p x$ and $\bar{F}_p x$ are approximations of the warping of vector $x$ by the optical flow, i.e., $F_p x \approx w_p^{p+1}(x)$ and $\bar{F}_p x \approx w_p^p(x)$. As matrix $D_p$ is diagonal, we can compute efficiently the last two sums in Eq. (7) using

$$\begin{aligned} x_{p+1}^\top D_{p+1}^{-1} F_p x_p &= x_{p+1}^\top (d_{p+1} \odot w_p^{p+1}(x_p)), \\ x_p^\top D_p^{-1} F_p^\top x_{p+1} &= x_p^\top (d_p \odot w_{p+1}^p(x_{p+1})), \end{aligned} \qquad (9)$$

where $d_p$ denotes the vectorized coefficients on the diagonal of matrix $D_p^{-1}$ and $\odot$ is the element-wise product. The terms $d_p$ weight the warped masks. We noticed during our experiments that their influence was very limited, and we did not keep them in our objective function for simplicity.

Moreover, while spectral clustering is a powerful framework, it actually is an approximation as it relaxes the search for binary masks by looking for continuous values for the coefficients of $X$, instead of binary ones. To encourage the optimization to recover binary values, we use the cross-entropy (minimizing it) when measuring the similarity between masks, rather than the dot product (maximizing it).

From Eqs. (3), (7), (8), (9), we finally obtain the formulation in Eq. (1). In practice, to minimize $\mathcal{L}(\{x_p\}_p)$, and thus maximize the flow consistency while not deviating too much from initial estimates, we first compute the eigenvectors $\hat{x}_p$ and use them to initialize the vectors $x_p$. Note that since the $x_p$ vectors remain close to the $\hat{x}_p$ vectors, the norm of $X$ remain approximately constant during optimization and the unit constraint in Eq. (3) is approximately satisfied. After convergence of the minimization, the soft masks $x_p$ are discretized using $K$-means with $K=2$ to separate the object of interest from the background. Implementation details are provided in the supplementary material.

# 4. Experiments

In this section, we first introduce the implementation details of our method. Then we describe the datasets we use for comparison with other methods and make a comprehensive analysis of each component in our approach.

## 4.1. Datasets

We evaluate our model on three standard benchmarks in unsupervised video object segmentation: DAVIS2016, SegTrack-v2, and FBMS59. **DAVIS2016** [60] is a densely-annotated video object segmentation dataset, featuring 50

sequences and 3455 frames in total, captured in 1080p resolution at 24 FPS with precise annotation of a primary moving object at 480p. **SegTrack-v2** [42] is a densely-annotated dataset of 14 sequences with 976 frames in total. It sometimes features multiple objects in a single video and has multiple challenges such as motion blur, deformations, interactions, and objects being static. **FBMS59** [55, 4] is a dataset of 59 sequences with every 20-th frame being annotated, which yields 720 annotated frames in total. The dataset may involve multiple objects (some of which can be static), occlusions, and other challenging conditions. Since SegTrack-v2 and FBMS59 might feature multiple objects in one scene and since our method is interested in the main object segmentation, we merge the segmentation masks of the individual objects into one, similar to [35, 90, 87].

## 4.2. Metrics

**Jaccard ($\mathcal{J}$).** For all datasets, we evaluate them with the Jaccard metric $\mathcal{J}$, which measures the intersection-over-union between predicted masks and ground-truth masks.

**Contour accuracy ($\mathcal{F}$).** For the DAVIS2016 dataset, we also report contour accuracy. This measure treats the mask as a set of closed contours to calculate their precision and recall with respect to the annotation. The contour accuracy is then taken as $\mathcal{F} = \frac{2P_c R_c}{P_c + R_c}$ where $P_c$ is the contour precision and $R_c$ is the contour recall.

**Computational cost.** On an Nvidia V100, our initialization and optimization runs on average in $\sim 0.5$ s/frame, where initial eigenvector extraction takes $\sim 0.1$ s/frame and the optimization takes $\sim 0.4$ s/frame.

Optimization consumes $\sim 8$ GB of VRAM for typical sequences in DAVIS2016, and $\sim 20$ MFLOPS/frame.

## 4.3. Ablation and Parameter Study

In order to understand the different factors that contribute to the performance of our method, we conduct a series of ablation studies. Table 1 reports the importance of the different components of our pipeline. Note that we do not apply any post-processing in our ablation experiments to show direct gains by our method. We evaluate the different aspects of our method as detailed below.

**Initial masks $\hat{x}_p$ from appearance only.** We study applying spectral clustering to appearance features only. We consider recent self-supervised features: DINO [9], MoCo-v3 [14], SWAV [8] and Barlow Twins (BT) [94]. Table 1(a) compares how these appearance features affect our results. We obtain the best performance with DINO. The fact that DINO largely outperforms other self-supervised features, as also noted in [82, 53], remains to be understood, but is out of scope. We also note that our method can exploit any image features. Better feature extractors in the future could even improve our results further. Table 1(a) also shows that, in every case our optimization method improves the $\mathcal{J}$ met-
<table><caption>**Table 1:** Ablation experiments on DAVIS2016 for different optical flow and appearance features for the frame-based initialization and after optimization. (a) Effects of different self-supervised methods for appearance features. (b) Effects of optical flow and different optical flow methods on performance. We obtain all initial results using Spectral Clustering on each frame independently. “+Optimization” denotes the results after optimizing our objective function. No post processing is applied to the results. Our optimization approach consistently improves the segmentation results by a large margin for all appearance features, with or without optical flow for initializing the masks.</caption><thead><tr><th>(a) Different appearance features</th><th>(J↑)</th><th>(F↑)</th></tr></thead><tbody><tr><td>(BT [RN-50] + ARFlow)</td><td>53.5</td><td>30.3</td></tr><tr><td>(BT [RN-50] + ARFlow) + Optimization (Eq. (1))</td><td>59.5 (+6.0)</td><td>48.2 (+17.9)</td></tr><tr><td>(SWAV [RN-50] + ARFlow)</td><td>48.0</td><td>27.2</td></tr><tr><td>(SWAV [RN-50] + ARFlow) + Optimization (Eq. (1))</td><td>53.6 (+5.6)</td><td>46.0 (+18.8)</td></tr><tr><td>(MoCo-v3 [ViT] + ARFlow)</td><td>58.0</td><td>35.3</td></tr><tr><td>(MoCo-v3 [ViT] + ARFlow) + Optimization (Eq. (1))</td><td>64.2 (+6.2)</td><td>61.1 (+25.8)</td></tr><tr><td>(DINO [ViT] + ARFlow)</td><td>72.1</td><td>72.5</td></tr><tr><td>(DINO [ViT] + ARFlow) + Optimization (Eq. (1))</td><td>76.8 (+4.7)</td><td>77.0 (+4.5)</td></tr><tr><th>(b) Different optical flows</th><th>(J↑)</th><th>(F↑)</th></tr><tr><td>DINO</td><td>61.2</td><td>65.8</td></tr><tr><td>TokenCut [82]</td><td>62.7</td><td>62.3</td></tr><tr><td>DINO + Optimization (Eq. (1))</td><td>66.7 (+5.5)</td><td>70.4 (+4.6)</td></tr><tr><td>(DINO + RAFT)</td><td>70.7</td><td>72.9</td></tr><tr><td>(DINO + RAFT) + Optimization (Eq. (1))</td><td>75.3 (+4.6)</td><td>76.2 (+3.3)</td></tr><tr><td>(DINO + ARFlow)</td><td>72.1</td><td>72.5</td></tr><tr><td>(DINO + ARFlow) + Optimization (Eq. (1))</td><td>76.8 (+4.7)</td><td>77.0 (+4.5)</td></tr></tbody></table>

ric by the average value of +5.6% and the F metric by the average value of +16.6%. This ablation also shows one potential application of our method, which could serve as a way to benchmark fine-grained representation capacity of self-supervised features [83, 23]: Given frozen features and strictly predefined optical flow, one can “plug-in” new features and estimate how good the representation capacity is.

As it has the most similar (graph-based) formulation to ours, we also compare to TokenCut [82] applied to each frame independently, using the same DINO features. On David2016, our mask extraction from single frames (i.e., our initial masks $\hat{x}_p$) is 1.5 pt behind TokenCut on the J metric, while outperforming it on F by 3.5 pts, which shows that our initialization is better at detecting object boundaries on individual images. More importantly, we are ~ 170× faster than TokenCut [82] (0.1 s/frame vs. 17 s/frame).

**Initial masks $\hat{x}_p$ from both appearance and flow.** We apply spectral clustering on the combination of appearance features and optical flow, as in Eq. (5). We consider supervised RAFT and self-supervised ARFlow. Effects of adding the optical flow to our approach can be seen in Table 1(b). The addition of optical flow to the appearance features greatly improves single-frame clustering performance and gives us a good initialization for the object masks. (Two successive frames are used for computing the optical flow.)

**Masks $x_p$ optimized from different initial masks $\hat{x}_p$.**

<table><caption>**Table 2:** **Results of our approach.** We show the performance of our approach on three standard benchmarks for video object segmentation (DAVIS2016, SegTrack-v2, and FBMS59), where our approach achieves state-of-the-art results despite. We also provide a comparison with some supervised methods, where we achieve a performance comparable to some of them without using any supervision. Note that recent unsupervised methods (MoSeg, CIS, DyStaB and IKE) use supervised optical flow estimators such as RAFT [73], PWCNet [71] or FlowNet [20, 34].</caption><thead><tr><th rowspan="2">Method</th><th rowspan="2">Training on videos</th><th rowspan="2">Optical flow</th><th rowspan="2">Fully unsuperv.</th><th colspan="2">DAVIS</th><th colspan="2">STv2</th><th colspan="2">FBMS59</th></tr><tr><th>J↑</th><th>F↑</th><th>J↑</th><th>J↑</th></tr></thead><tbody><tr><td colspan="9"><strong>(Mostly) Unsupervised methods:</strong></td></tr><tr><td>CUT [38]</td><td></td><td>LDOF [3]</td><td>✓</td><td>55.2</td><td>55.2</td><td>54.3</td><td>57.2</td><td></td></tr><tr><td>FTS [57]</td><td></td><td>LDOF [72]</td><td>✓</td><td>55.8</td><td>51.1</td><td>47.8</td><td>47.7</td><td></td></tr><tr><td>AMD [47]</td><td>✓</td><td></td><td>✓</td><td>57.8</td><td>-</td><td>57.0</td><td>47.5</td><td></td></tr><tr><td>MoSeg [87]</td><td>✓</td><td>RAFT [73]</td><td></td><td>68.3</td><td>61.1</td><td>58.6</td><td>53.1</td><td></td></tr><tr><td>CIS [90]</td><td>✓</td><td>PWCNet [71]</td><td></td><td>71.5</td><td>70.5</td><td>62.0</td><td>63.5</td><td></td></tr><tr><td>DS [92]</td><td>✓</td><td>RAFT [73]</td><td></td><td>79.1</td><td>-</td><td>72.1</td><td>71.8</td><td></td></tr><tr><td>DyStaB [89]</td><td>✓</td><td>PWCNet [71]</td><td></td><td>80.0</td><td>-</td><td>74.2</td><td>73.2</td><td></td></tr><tr><td><strong>Ours</strong></td><td></td><td>ARFlow [46]</td><td>✓</td><td><strong>80.2</strong></td><td><strong>77.5</strong></td><td><strong>74.9</strong></td><td><strong>70.0</strong></td><td></td></tr><tr><td colspan="9"><strong>Supervised methods:</strong></td></tr><tr><td>NLC [25]</td><td></td><td>SIFTFlow [45]</td><td></td><td>55.1</td><td>52.3</td><td>67.2</td><td>51.5</td><td></td></tr><tr><td>SFL [15]</td><td>✓</td><td>FlowNetS [20]</td><td></td><td>67.4</td><td>66.7</td><td>-</td><td>-</td><td></td></tr><tr><td>FSEG [35]</td><td>✓</td><td></td><td></td><td>70.7</td><td>65.3</td><td>61.4</td><td>68.4</td><td></td></tr><tr><td>LVO [75]</td><td>✓</td><td>MP-Net [74]</td><td></td><td>75.9</td><td>72.1</td><td>57.3</td><td>65.1</td><td></td></tr><tr><td>ARP [40]</td><td></td><td>CPMFlow [32]</td><td></td><td>76.2</td><td>70.6</td><td>57.2</td><td>59.8</td><td></td></tr><tr><td>MSgStP [33]</td><td></td><td></td><td></td><td>77.6</td><td>-</td><td>70.1</td><td>60.8</td><td></td></tr><tr><td>MATNet [96]</td><td>✓</td><td>PWCNet [71]</td><td></td><td>82.4</td><td>80.7</td><td>-</td><td>-</td><td></td></tr><tr><td>DyStaB [89]</td><td>✓</td><td>PWCNet [71]</td><td></td><td>82.8</td><td>-</td><td><strong>74.2</strong></td><td><strong>75.8</strong></td><td></td></tr><tr><td>3DC-Seg [50]</td><td>✓</td><td></td><td></td><td>84.3</td><td>84.7</td><td>-</td><td>-</td><td></td></tr><tr><td>ViTAE [86]</td><td>✓</td><td></td><td></td><td>89.2</td><td>90.4</td><td>-</td><td>-</td><td></td></tr><tr><td>BATMAN [93]</td><td>✓</td><td>RAFT [73]</td><td></td><td><strong>90.7</strong></td><td><strong>94.2</strong></td><td>-</td><td>-</td><td></td></tr></tbody></table>

We present the effects of our global optimization on different appearance features and optical flows in Table 1. Our optimization gives an average boost of +4.9% over the single frame clustering, validating our approach in all cases.

**Number of flow steps.** We found (see full results in supp. mat.) that one flow step achieves the best performance, which supports our assumption of using a tridiagonal global affinity matrix: Even in the single flow step case, all frames are tied together via optical flow. Conversely, more steps might complicate the optimization due to the potentially noisier flow estimated between distant frames because of the larger displacements and additional occlusions.

**Cross-entropy vs. dot product.** In our objective function, we use the cross-entropy rather than the dot product between the masks. We compared the two options experimentally and found that using the cross-entropy indeed improves the masks that we recover. We provide the full results in the supplementary material.

## 4.4. Comparison to the State of the Art

Here, we use our best configuration (DINO [ViT] + ARFlow + Optimization). Following CIS [90] and DyStaB [89], we use a CRF as a post-processing step. Table 2 presents the performances of our method and several estab-
lished state-of-the-art unsupervised and supervised methods. Overall, our method performs on-par with the state-of-the-art methods on DAVIS2016 and it achieves the best performance on the STv2 dataset. Our method also has high contour accuracy *F*, which shows that our approach achieves high quality boundaries. Among unsupervised methods, our method outperforms all previous methods by achieving 80.2 *J* and 74.9 *J* scores on DAVIS2016 and STv2, respectively. Our method outperforms the SOTA method DyStaB albeit slightly, with a much simpler approach. Also note that, in contrast to recent unsupervised methods, our approach does not use any supervised component in the pipeline, including optical flow.

Table 2 shows the generalization ability of our method: Rather than training on a target dataset, we leverage general images features obtained from a network pretrained on a large dataset with no supervision. While it may not be optimal in some contexts due to different data distributions, we achieve an excellent performance on three different benchmarks, without training and reusing the exact same networks for feature extraction and flow computation.

Comparing ViT and CNN based methods is not straightforward as each of them has their own advantages. Although other methods do not exploit ViTs, the most recent ones do use advanced CNN networks, e.g., DeepLabv3 (used in DyStaB), one of the SOTA architectures for segmentation. Besides, while we rely only on pretrained networks, although possibly on large datasets (e.g., ImageNet for appearance, Sintel for flow), a number of other methods (supervised or unsupervised) are advantaged by the fact they train on the target datasets, hence on the task itself and using a data distribution closer to the test sets. Note that other methods in Table 2 also use extra data beyond the evaluated dataset, e.g., DyStaB uses ImageNet-pretrained weights to initialize its network, while AMD uses YoutubeVOS (a large video dataset) pretrained weights.

Figure 5 shows some failure cases of our approach. More examples are provided in the supplementary material. Note that some of those failure cases can be removed by further postprocessing, but we do not use it to keep our approach simple. We show examples of segmentation results by our method for qualitative visual inspection in Figure 4.

# 5. Conclusion

Our method consists of minimizing an objective function that is intuitive, simple to implement, and can be optimized efficiently. It can be derived from spectral clustering, which gives it solid theoretical ground. It could also be used to evaluate fine-grained capabilities of modern self-supervised representations, which is still a very active area of research [83, 23]. We hope that the simplicity of our method and its connection to spectral clustering will provide others with insights for future development.

<figure><img src="image_6.png" /><figcaption>DINO</figcaption></figure>

<caption>DINO + ARFlow</caption>

<caption>DINO + ARFlow + Opt</caption>

<caption>Ground Truth</caption>

<figure><img src="image_7.png" /><figcaption>Figure 5: **Failure cases.** Our approach has 3 main failure modes: *Oversegmentation* which is most often caused by multiple similar objects in the scene, imprecise masks due to *occlusion*, and *undersegmentation* in scenes with multiple objects which leads to the parts of the primary object not being segmented. In the last example, note that when we use DINO features, our clusters tend to group a single semantic class, which is the desired behavior for object discovery, rather than segment anything that moves. This is thus a failure case w.r.t. the benchmark, but not to the goal of object discovery.</figcaption></figure>

# Acknowledgments

This project was provided with computing HPC and storage resources by GENCI at IDRIS thanks to the grant 2021-AD011012997 on the supercomputer Jean Zay's V100 partition and supported in part by the Chistera IPalm project.
## References

[1] Ali Athar, Sabarinath Mahadevan, Aljosa Osep, Laura Leal-Taixé, and Bastian Leibe. Stem-Seg: Spatio-Temporal EM-beddings For Instance Segmentation in Videos. In *European Conference on Computer Vision (ECCV)*, 2020.

[2] Pia Bideau and Erik Learned-Miller. It's Moving! a Prob-abilistic Model for Causal Motion Segmentation in Moving Camera Videos. In *European Conference on Computer Vi-sion (ECCV)*, 2016.

[3] Thomas Brox and Jitendra Malik. Large Displacement Op-tical Flow: Descriptor Matching in Variational Motion Esti-mation. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 2010.

[4] Thomas Brox and Jitendra Malik. Object Segmentation by Long Term Analysis of Point Trajectories. In *European Con-ference on Computer Vision (ECCV)*, 2010.

[5] Christopher P. Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexan-der Lerchner. Monet: Unsupervised Scene Decomposition and Representation. In *arXiv Preprint*, 2019.

[6] Daniel J. Butler, Jonas Wulff, Garrett B. Stanley, and Michael J. Black. A Naturalistic Open Source Movie for Optical Flow Evaluation. In *European Conference on Com-puter Vision (ECCV)*, 2012.

[7] Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A Limited Memory Algorithm for Bound Constrained Optimization. *SIAM Journal on scientific computing*, 16(5), 1995.

[8] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Pi-otr Bojanowski, and Armand Joulin. Unsupervised Learn-ing of Visual Features by Contrasting Cluster Assignments. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2020.

[9] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. EMerging Properties in Self-Supervised Vision Transform-ers. In *International Conference on Computer Vision (ICCV)*, 2021.

[10] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Deeplab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 2017.

[11] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Ge-offrey Hinton. A Simple Framework for Contrastive Learn-ing of Visual Representations. In *International Conference on Machine Learning (ICML)*, 2020.

[12] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved Baselines with Momentum Contrastive Learning. In *arXiv Preprint*, 2020.

[13] Xinlei Chen and Kaiming He. Exploring Simple Siamese Representation Learning. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2021.

[14] Xinlei Chen, Saining Xie, and Kaiming He. An EMpirical Study of Training Self-Supervised Vision Transformers. In *arXiv Preprint*, 2021.

[15] Jingchun Cheng, Yi-Hsuan Tsai, Shengjin Wang, and Ming-Hsuan Yang. SegFlow: Joint Learning for Video Object Segmentation and Optical Flow. In *International Conference on Computer Vision (ICCV)*, 2017.

[16] Minsu Cho, Suha Kwak, Cordelia Schmid, and Jean Ponce. Unsupervised Object Discovery and Localization in the Wild: Part-Based Matching with Bottom-Up Region Propos-als. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2015.

[17] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The Cityscapes Dataset for Semantic Urban Scene Understanding. In *International Conference on Computer Vision and Pattern Recogni-tion (CVPR)*, 2016.

[18] Ioana Croitoru, Simion-Vlad Bogolin, and Marius Leordeanu. Unsupervised Learning from Video to De-tect Foreground Objects in Single Images. In *International Conference on Computer Vision (ICCV)*, 2017.

[19] Alexey Dosovitskiy, Philipp Fischer, Eddy Ilg, Philip Hausser, Caner Hazirbas, Vladimir Golkov, Patrick Van Der Smagt, Daniel Cremers, and Thomas Brox. Flownet: Learning Optical Flow with Convolutional Networks. In *International Conference on Computer Vision (ICCV)*, 2015.

[20] Alexey Dosovitskiy, Philipp Fischer, Eddy Ilg, Philip Hausser, Caner Hazirbas, Vladimir Golkov, Patrick Van Der Smagt, Daniel Cremers, and Thomas Brox. Flownet: Learning Optical Flow with Convolutional Networks. In *International Conference on Computer Vision (ICCV)*, 2015.

[21] Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Ried-miller, and Thomas Brox. Discriminative Unsupervised Fea-ture Learning with Convolutional Neural Networks. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2014.

[22] Yuming Du, Yang Xiao, and Vincent Lepetit. Learning to Better Segment Objects from Unseen Classes with Unla-beled Videos. In *International Conference on Computer Vi-sion (ICCV)*, 2021.

[23] Linus Ericsson, Henry Gouk, and Timothy M. Hospedales. How Well Do Self-Supervised Models Transfer? In *International Conference on Computer Vision and Pattern Recogni-tion (CVPR)*, 2021.

[24] Alon Faktor and Michal Irani. Clustering by Composi-tion": Unsupervised Discovery of Image Categories. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 36(6), 2013.

[25] Alon Faktor and Michal Irani. Video Segmentation by Non-Local Consensus Voting. In *British Machine Vision Confer-ence (BMVC)*, 2014.

[26] D. Fleet and Y. Weiss. *Optical Flow Estimation*. Springer US, 2006.

[27] Fabio Galasso, Roberto Cipolla, and Bernt Schiele. Video Segmentation with Superpixels. In *Asian Conference on Computer Vision (ACCV)*, 2012.

[28] Klaus Greff, Raphaël Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner. Multi-Object
Representation Learning with Iterative Variational Inference.
In *International Conference on Machine Learning (ICML)*, 2019.

[29] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap Your Own Latent: A New Approach to Self-Supervised Learning. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2020.

[30] Emanuela Haller, Adina Magda Florea, and Marius Leordeanu. Iterative Knowledge Exchange Between Deep Learning and Space-Time Spectral Clustering for Unsupervised Segmentation in Videos. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 2021.

[31] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum Contrast for Unsupervised Visual Representation Learning. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2020.

[32] Yinlin Hu, Rui Song, and Yunsong Li. Efficient Coarse-To-Fine Patchmatch for Large Displacement Optical Flow. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2016.

[33] Yuan-Ting Hu, Jia-Bin Huang, and Alexander G. Schwing. Unsupervised Video Object Segmentation Using Motion Saliency-Guided Spatio-Temporal Propagation. In *European Conference on Computer Vision (ECCV)*, 2018.

[34] E. Ilg, N. Mayer, T. Saikia, M. Keuper, A. Dosovitskiy, and T. Brox. FlowNet 2.0: Evolution of Optical Flow Estimation with Deep Networks. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[35] Suyog Jain, Bo Xiong, and Kristen Grauman. FusionSeg: Learning to Combine Motion and Appearance for Fully Automatic Segmentation of Generic Objects in Videos. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[36] Suyog Dutt Jain, Bo Xiong, and Kristen Grauman. FusionSeg: Learning to Combine Motion and Appearance for Fully Automatic Segmentation of Generic Objects in Videos. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[37] Ge-Peng Ji, Keren Fu, Zhe Wu, Deng-Ping Fan, Jianbing Shen, and Ling Shao. Full-Duplex Strategy for Video Object Segmentation. In *International Conference on Computer Vision (ICCV)*, 2021.

[38] Margret Keuper, Bjoern Andres, and Thomas Brox. Motion Trajectory Segmentation via Minimum Cost Multicuts. In *International Conference on Computer Vision (ICCV)*, 2015.

[39] Anna Khoreva, Fabio Galasso, Matthias Hein, and Bernt Schiele. Classifier-Based Graph Construction for Video Segmentation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2015.

[40] Yeong Jun Koh and Chang-Su Kim. Primary Object Segmentation in Videos Based on Region Augmentation and Reduction. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[41] Hala Lamdouar, Weidi Xie, and Andrew Zisserman. Segmenting Invisible Moving Objects. In *British Machine Vision Conference (BMVC)*, 2021.

[42] Fuxin Li, Taeyoung Kim, Ahmad Humayun, David Tsai, and James M. Rehg. Video Segmentation by Tracking Many Figure-Ground Segments. In *International Conference on Computer Vision (ICCV)*, 2013.

[43] Xiaoxiao Li and Chen Change Loy. Video Object Segmentation with Joint Re-Identification and Attention-Aware Mask Propagation. In *European Conference on Computer Vision (ECCV)*, 2018.

[44] Frank Lin and William W. Cohen. Power Iteration Clustering. In *International Conference on Machine Learning (ICML)*, 2010.

[45] Ce Liu and Others. *Beyond Pixels: Exploring New Representations and Applications for Motion Analysis*. PhD thesis, Massachusetts Institute of Technology, 2009.

[46] Liang Liu, Jiangning Zhang, Ruifei He, Yong Liu, Yabiao Wang, Ying Tai, Donghao Luo, Chengjie Wang, Jilin Li, and Feiyue Huang. Learning by Analogy: Reliable Supervision from Transformations for Unsupervised Optical Flow Estimation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2020.

[47] Runtao Liu, Zhirong Wu, Stella Yu, and Stephen Lin. The EMergence of Objectness: Learning Zero-Shot Segmentation from Videos. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2021.

[48] Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-Centric Learning with Slot Attention. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2020.

[49] Xiankai Lu, Wenguan Wang, Chao Ma, Jianbing Shen, Ling Shao, and Fatih Porikli. See More, Know More: Unsupervised Video Object Segmentation with Co-Attention Siamese Networks. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[50] Sabarinath Mahadevan, Ali Athar, Aljoša Ošep, Sebastian Hennen, Laura Leal-Taixé, and Bastian Leibe. Making a Case for 3D Convolutions for Object Segmentation in Videos. In *arXiv Preprint*, 2020.

[51] K.-K. Maninis, Sergi Caelles, Yuhua Chen, Jordi Pont-Tuset, Laura Leal-Taixé, Daniel Cremers, and Luc Van Gool. Video Object Segmentation Without Temporal Information. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 41(6), 2018.

[52] Marina Meila and Jianbo Shi. Learning Segmentation by Random Walks. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2001.

[53] Luke Melas-Kyriazi, Christian Rupprecht, Iro Laina, and Andrea Vedaldi. Deep Spectral Methods: A Surprisingly Strong Baseline for Unsupervised Semantic Segmentation and Localization. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2022.

[54] Peter Ochs and Thomas Brox. Object Segmentation in Video: A Hierarchical Variational Approach for Turning Point Trajectories into Dense Regions. In *International Conference on Computer Vision (ICCV)*, 2011.
[55] Peter Ochs, Jitendra Malik, and Thomas Brox. Segmentation of Moving Objects by Long Term Video Analysis. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 2014.

[56] Seoung Wug Oh, Joon-Young Lee, Ning Xu, and Seon Joo Kim. Video Object Segmentation Using Space-Time Memory Networks. In *International Conference on Computer Vision (ICCV)*, 2019.

[57] Anestis Papazoglou and Vittorio Ferrari. Fast Object Segmentation in Unconstrained Video. In *International Conference on Computer Vision (ICCV)*, 2013.

[58] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach Devito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In *International Conference on Neural Information Processing, 2019*.

[59] Federico Perazzi, Anna Khoreva, Rodrigo Benenson, Bernt Schiele, and Alexander Sorkine-Hornung. Learning Video Object Segmentation from Static Images. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[60] Federico Perazzi, Jordi Pont-Tuset, Brian Mcwilliams, Luc Van Gool, Markus Gross, and Alexander Sorkine-Hornung. A Benchmark Dataset and Evaluation Methodology for Video Object Segmentation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2016.

[61] Anurag Ranjan, Varun Jampani, Lukas Balles, Kihwan Kim, Deqing Sun, Jonas Wulff, and Michael J. Black. Competitive Collaboration: Joint Unsupervised Learning of Depth, Camera Motion, Optical Flow and Motion Segmentation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[62] Sucheng Ren, Wenxi Liu, Yongtuo Liu, Haoxin Chen, Guoqiang Han, and Shengfeng He. Reciprocal Transformations for Unsupervised Video Object Segmentation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2021.

[63] Michael Rubinstein, Armand Joulin, Johannes Kopf, and Ce Liu. Unsupervised Joint Object Discovery and Segmentation in Internet Images. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2013.

[64] Bryan C. Russell, William T. Freeman, Alexei A. Efros, Josef Sivic, and Andrew Zisserman. Using Multiple Segments to Discover Objects and Their Extent in Image Collections. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2006.

[65] Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. *IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)*, 2000.

[66] Mennatullah Siam, Chen Jiang, Steven Lu, Laura Petrich, Mahmoud Gamal, Mohamed Elhoseiny, and Martin Jagersand. Video Object Segmentation Using Teacher-Student Adaptation in a Human Robot Interaction (hri) Setting. In *International Conference on Robotics and Automation (ICRA)*, 2019.

[67] Oriane Siméoni, Gilles Puy, Huy V. Vo, Simon Roburin, Spyros Gidaris, Andrei Bursuc, Patrick Pérez, Renaud Marlet, and Jean Ponce. Localizing Objects with Self-Supervised Transformers and No Labels. In *British Machine Vision Conference (BMVC)*, 2021.

[68] Josef Sivic, Bryan C. Russell, Andrew Zisserman, William T. Freeman, and Alexei A. Efros. Unsupervised Discovery of Visual Object Class Hierarchies. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2008.

[69] Josef Sivic, Frederik Schaffalitzky, and Andrew Zisserman. Object Level Grouping for Video Shots. In *European Conference on Computer Vision (ECCV)*, 2004.

[70] Hongmei Song, Wenguan Wang, Sanyuan Zhao, Jianbing Shen, and Kin-Man Lam. Pyramid Dilated Deeper ConvLSTM for Video Salient Object Detection. In *European Conference on Computer Vision (ECCV)*, 2018.

[71] Deqing Sun, Xiaodong Yang, Ming-Yu Liu, and Jan Kautz. PWC-Net: CNNs For Optical Flow Using Pyramid, Warping, and Cost Volume. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2018.

[72] Narayanan Sundaram, Thomas Brox, and Kurt Keutzer. Dense Point Trajectories by Gpu-Accelerated Large Displacement Optical Flow. In *European Conference on Computer Vision (ECCV)*, 2010.

[73] Zachary Teed and Jia Deng. RAFT: Recurrent All-Pairs Field Transforms for Optical Flow. In *European Conference on Computer Vision (ECCV)*, 2020.

[74] Pavel Tokmakov, Karteek Alahari, and Cordelia Schmid. Learning Motion Patterns in Videos. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2017.

[75] Pavel Tokmakov, Karteek Alahari, and Cordelia Schmid. Learning Video Object Segmentation with Visual Memory. In *International Conference on Computer Vision (ICCV)*, 2017.

[76] Huy V. Vo, Francis Bach, Minsu Cho, Kai Han, Yann LeCun, Patrick Pérez, and Jean Ponce. Unsupervised Image Matching and Object Discovery as Optimization. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[77] Paul Voigtlaender and Bastian Leibe. Online Adaptation of Convolutional Neural Networks for Video Object Segmentation. In *arXiv Preprint*, 2017.

[78] Ulrike Von Luxburg. A Tutorial on Spectral Clustering. *Stat. Comput.*, 17(4), 2007.

[79] Wenguan Wang, Xiankai Lu, Jianbing Shen, David J. Cran-dall, and Ling Shao. Zero-Shot Video Object Segmentation via Attentive Graph Neural Networks. In *International Conference on Computer Vision (ICCV)*, 2019.

[80] Wenguan Wang, Jianbing Shen, and Fatih Porikli. Saliency-Aware Geodesic Video Object Segmentation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2015.

[81] Wenguan Wang, Hongmei Song, Shuyang Zhao, Jianbing Shen, Sanyuan Zhao, Steven CH Hoi, and Haibin Ling.
Learning Unsupervised Video Object Segmentation through Visual Attention. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[82] Yangtao Wang, Xi Shen, Shell Xu Hu, Yuan Yuan, James Crowley, and Dominique Vaufreydaz. Self-Supervised Transformers for Unsupervised Object Discovery Using Normalized Cut. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2022.

[83] Zhongdao Wang, Hengshuang Zhao, Ya-Li Li, Shengjin Wang, Philip Torr, and Luca Bertinetto. Do Different Tracking Tasks Require Different Appearance Models? In *Thirty-Fifth Conference on Neural Information Processing Systems*, 2021.

[84] Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised Feature Learning via Non-Parametric Instance Discrimination. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2018.

[85] Christopher Xie, Yu Xiang, Zaid Harchaoui, and Dieter Fox. Object Discovery in Videos as Foreground Motion Clustering. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[86] Yufei Xu, Qiming ZHANG, Jing Zhang, and Dacheng Tao. Vitae: Vision transformer advanced by exploring intrinsic inductive bias. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2021.

[87] Charig Yang, Hala Lamdouar, Erika Lu, Andrew Zisserman, and Weidi Xie. Self-Supervised Video Object Segmentation by Motion Grouping. In *International Conference on Computer Vision (ICCV)*, 2021.

[88] Shu Yang, Lu Zhang, Jinqing Qi, Huchuan Lu, Shuo Wang, and Xiaoxing Zhang. Learning Motion-Appearance Co-Attention for Zero-Shot Video Object Segmentation. In *International Conference on Computer Vision (ICCV)*, 2021.

[89] Yanchao Yang, Brian Lai, and Stefano Soatto. DyStaB: Unsupervised Object Segmentation via Dynamic-Static Bootstrapping. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2021.

[90] Yanchao Yang, Antonio Loquercio, Davide Scaramuzza, and Stefano Soatto. Unsupervised Moving Object Detection via Contextual Information Separation. In *International Conference on Computer Vision and Pattern Recognition (CVPR)*, 2019.

[91] Zhao Yang, Qiang Wang, Luca Bertinetto, Weiming Hu, Song Bai, and Philip HS Torr. Anchor Diffusion for Unsupervised Video Object Segmentation. In *International Conference on Computer Vision (ICCV)*, 2019.

[92] Vickie Ye, Zhengqi Li, Richard Tucker, Angjoo Kanazawa, and Noah Snavely. Deformable sprites for unsupervised video decomposition. In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, pages 2657-2666, June 2022.

[93] Ye Yu, Jialin Yuan, Gaurav Mittal, Li Fuxin, and Mei Chen. BATMAN: Bilateral Attention Transformer in Motion-Appearance Neighboring Space for Video Object Segmentation. In *ECCV*, 2022.

[94] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow Twins: Self-Supervised Learning via Redundancy Reduction. In *arXiv Preprint*, 2021.

[95] Kaihua Zhang, Zicheng Zhao, Dong Liu, Qingshan Liu, and Bo Liu. Deep Transport Network for Unsupervised Video Object Segmentation. In *International Conference on Computer Vision (ICCV)*, 2021.
[96] Tianfei Zhou, Shunzhou Wang, Yi Zhou, Yazhou Yao, Jianwu Li, and Ling Shao. Motion-Attentive Transition for Zero-Shot Video Object Segmentation. In *American Association for Artificial Intelligence Conference (AAAI)*, 2020.
## A. Supplementary material – Overview

In this supplementary material:

* we justify design choices and assumptions made in the main paper (Sections B-F);

* we show implementation details of our approach (Section G);

* we provide additional failure cases (Section H);

* we provide more qualitative results on DAVIS2016, SegTrack v2 and FBMS-59 (Section I).

## B. Justifying only using the flow between adjacent frames

Our formulation, in Eq. (1) of the main paper, only involves the optical flow between adjacent frames (forward and backward). As discussed in Section 3 of the main paper, it can be related to the tridiagonal affinity matrix $\mathcal{A}$ in Eq. (4). We remark at the end of Section 3.3 that we could have used a denser matrix correlating more faraway frames, but that the optical flow between frames that are distant in time is less reliable.

To validate our choice of only using the optical flow between adjacent frames, we consider here the following variant of our objective function, where we introduce warps between more distant frames (up to some constant $T$):

$$ \mathcal{L}(\{\mathbf{x}_p\}_{p}) = \sum_p \lambda \mathrm{CE}(\hat{\mathbf{x}}_p, \mathbf{x}_p) + \sum_{t=1}^{T} \mathrm{CE}(\mathbf{x}_{p+t}, w_p^{p+t}(\mathbf{x}_p)) + \mathrm{CE}(\mathbf{x}_p, w_{p+t}^p(\mathbf{x}_{p+t})), \quad (10) $$

<table><caption>Table 3: **Study of the distance between frames for flow consistency enforcement.** We consider different values of $T$ in Eq. (10) and evaluate on DAVIS2016 using our best configuration (DINO [ViT] + ARFlow + Opt) without CRF post-processing. The best performance is achieved for $T = 1$, coinciding with the tridiagonal matrix configuration.</caption><thead><tr><th rowspan="2">Max. frame distance<br>for optical flow</th><th colspan="2">DAVIS2016</th></tr><tr><th>J ↑</th><th>F ↑</th></tr></thead><tbody><tr><td>T = 1</td><td><strong>76.8</strong></td><td><strong>77.0</strong></td></tr><tr><td>T = 2</td><td>74.0</td><td>71.3</td></tr><tr><td>T = 3</td><td>67.1</td><td>61.8</td></tr></tbody></table>

Table 3 shows that using a time horizon of a single frame is not only enough but actually better than considering the optical flow between more distant frames. In fact, using the flow regarding only the preceding and the succeeding

frames already ties together all frames in the sequence. Additional terms with optical flows between more distant frames may actually introduce noise because of worse estimations due to larger displacements, deformations and occlusions.

## C. Using the cross-entropy vs the dot product

In Section 3.4 of the main paper, we replace the dot products

$$ (\hat{\mathbf{x}}_p)^T \mathbf{x}_p, \mathbf{x}_{p+1}^T w_p^{p+1}(\mathbf{x}_p), \text{ and } \mathbf{x}_p^T w_{p+1}^p(\mathbf{x}_{p+1}) $$

by cross-entropies, respectively:

$$ \mathrm{CE}(\hat{\mathbf{x}}_p, \mathbf{x}_p), \mathrm{CE}(\mathbf{x}_{p+1}, w_p^{p+1}(\mathbf{x}_p)), \text{ and } \mathrm{CE}(\mathbf{x}_p, w_{p+1}^p(\mathbf{x}_{p+1})). $$

This was motivated empirically, as we observed that the cross-entropy was providing a better performance. Table 4 reports the quantitative results of this experiment.

<table><caption>Table 4: **Dot product vs cross-entropy.** Using the cross-entropy between two vectors in our objective function rather than their dot product leads to a significant improvement of **+14.6%** in $\mathcal{J}$ and **+16.6%** in $\mathcal{F}$.</caption><thead><tr><th rowspan="2">Measurement of<br>mask deviation</th><th colspan="2">DAVIS2016</th></tr><tr><th>J ↑</th><th>F ↑</th></tr></thead><tbody><tr><td>Cross-entropy</td><td><strong>76.8</strong></td><td><strong>77.0</strong></td></tr><tr><td>Dot product</td><td>62.1</td><td>60.4</td></tr></tbody></table>

## D. On the Constant Norm Constraint in Eq. (3)

We estimate the second largest eigenvector of $\mathcal{W}$ via a maximization problem over a vector $\mathbf{X}$ under the constraint that $\|\mathbf{X}\|_2$ is constant, as stated in Eq. (3) in the main paper. At the end of Section 3.4, we claim that since the $\mathbf{x}_p$ vectors remain close to the $\hat{\mathbf{x}}_p$ vectors, $\|\mathbf{X}\|_2 = \sqrt{\sum_p (\|\hat{\mathbf{x}}_p\|_2)^2}$ remains approximately constant during optimization, thus satisfying the constraint in Eq. (3) up to a constant factor of $\sqrt{N}$.

Table 5 shows empirically that this constraint is indeed approximately met at each stage of the global optimization process.

## E. Approximation in Eq. (8)

In the main paper, we assumed the following approximation:

$$ \mathbf{x}_p^\top D_p^{-1} A_p \mathbf{x}_p \approx \hat{\mathbf{x}}_p^\top \mathbf{x}_p. \quad (11) $$
<table><caption>**Table 5: Study of the constant norm constraint approximation.** We study the average of $||\hat{x}_p||_2$ over all frames of all sequences in the DAVIS2016 dataset at each iteration of our global optimization (using L-BFGS). We observe that the deviations to the theoretical norm of 1 are small, which in turns means that our approach of not using any explicit constraint is valid.</caption><thead><tr><th>L-BFGS iteration number</th><th>Theoretical norm of x̂<sub>p</sub></th><th>Actual average norm of x̂<sub>p</sub></th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1.003</td></tr><tr><td>2</td><td>1</td><td>1.001</td></tr><tr><td>3</td><td>1</td><td>1.007</td></tr><tr><td>4</td><td>1</td><td>1.022</td></tr><tr><td>5</td><td>1</td><td>1.022</td></tr></tbody></table>

The derivation of this approximation is given below.

Since $W_p = D_p^{-1}A_p$ is a row-normalized stochastic matrix, the largest eigenvalue associated to its first eigenvector is 1. Besides, our initial mask estimate $\hat{x}_p$ is computed as the second largest eigenvector of $W_p$ via Power Iteration Clustering (PIC) [44]. According to [52, 44], if $K$ clusters are well-separated, then the significant eigenvalues of $W_p$, noted $\lambda_1 \ge \dots \ge \lambda_K$, are such that $\lambda_i/\lambda_1 \approx 1$ for all $i \in \{1, \dots, K\}$. Consequently, if the foreground object is well-separated from the background ($K \ge 2$), we may assume that $\lambda_2 \approx \lambda_1 = 1$. As $\hat{x}_p$ approximates the second largest eigenvector of $W_p$, we have:

$$W_p \hat{x}_p \approx \lambda_2 \hat{x}_p \approx \hat{x}_p. \qquad (12)$$

Therefore, considering also that $x_p$ deviates little from $\hat{x}_p$, i.e., $x_p \approx \hat{x}_p$, we have:

$$ \begin{aligned} & \mathbf{x}_p^\top D_p^{-1} A_p \mathbf{x}_p \\ &= \mathbf{x}_p^\top W_p \mathbf{x}_p \\ & \approx \mathbf{x}_p^\top W_p \hat{\mathbf{x}}_p \\ & \approx \mathbf{x}_p^\top \hat{\mathbf{x}}_p \\ &= \hat{\mathbf{x}}_p^\top \mathbf{x}_p. \end{aligned} \qquad (13) $$

## F. Dealing with Inaccurate Optical Flow

Our method relies on predicted optical flows. As they can be wrong or poor quality, they may introduce noise during the computation of the initial mask estimates and the optimization. In order to reduce the influence of this noise, we eliminate poor quality optical flow predictions. Given a predicted flow $\phi_{p,q}$, we first warp frame $q$ to frame $p$. Next, we calculate the difference image between frame $p$ and the reconstructed frame $\hat{p}$. The locations with high response on the difference image correspond to wrong or poor quality optical flow predictions. We use $k$-th percentile of the difference image as a threshold value to eliminate the

poor quality optical flow predictions. The locations under the calculated threshold value indicate where optical flow fails to produce the accurate flows. We exclude these optical flow predictions from both the computation of the initial mask estimates and the optimization. We experimentally set $k$ as 90-th percentile.

## G. Implementation Details

All our experiments are implemented with PyTorch [58]. We use the L-BFGS [7] with learning rate of 1 to optimize our objective function. The weight $\lambda$ in Eq. 1 is set to be 10.

We use DINO pretrained on ImageNet as appearance features. Due to their low resolution, we upscale the initial eigenvectors to the required resolution and run the full optimization pipeline. The optimized eigenvectors can be later either thresholded or clustered with $K$-means to obtain the final masks. We choose $K$-means as it is a more universal method that does not require finding threshold parameters. The final segments are then refined using CRF, as [90, 89].

We use the ARFlow model pretrained on the CityScapes [17] dataset in a self-supervised manner to predict optical flow. In ablation studies, we also use the RAFT model [73] for comparison, which is trained in a supervised manner with labeled data from the Sintel dataset [6].

## H. Additional Failure Cases

In Figure 6, we show more failure examples of our approach. The first row shows another example of oversegmentation, where flowing particles are being segmented as foreground. The second row shows undersegmentation. The last row shows the inability of our approach to capture very fine details, such as the thin cables of the paraglider.

## I. More Qualitative Results

On the next pages (Figures 7-19), we show more qualitative results of our approach, where we compare to the CIS [90] method, which is the third best self-supervised video object segmentation (VOS) method after ours, according to Table 2 in the main paper. (DyStab [89], which is the second best self-supervised VOS method, did not release code to rerun these experiments nor mask results).

Compared to CIS, our method is more successful at segmenting objects as a whole and capturing finer details of object boundaries.

## J. Use of Existing Datasets and Codes

For the experiments, we used several datasets that are freely available for research purpose:

* DAVIS 2016² [60] is under license CC BY-NC 4.0.

<footnote n="2">²https://davischallenge.org</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 6: **Failure cases.** Our approach has three main failure modes: over-segmentation in scenes with multiple objects, under-segmentation, and inability to capture very fine details.</figcaption></figure>

• SegTrack-v2³ [42] is under a custom non-commercial, research-only license, courtesy of Georgia Institute of Technology,

• FBMS-59⁴ [55, 4] is under a custom non-commercial, research-only license, courtesy of University of Freiburg.

To compute appearance and flow, we experimented with the following methods, whose code is freely available for research purpose:

• DINO⁵ [9] is under the Apache License 2.0.

• MoCov2⁶ [12] is under the CC BY-NC 4.0 license.

• ARFlow⁷ [46] is under the MIT License.

• RAFT⁸ [73] is under the BSD 3-Clause License.

## K. Societal Impact

We believe that our approach for the self-supervised discovery and segmentation of objects in videos has **very little potential for malicious uses** (including disinformation, surveillance, invasion of privacy, endangering security), in any case not more, e.g., than the hundreds of previously

published methods on supervised object detection and segmentation. Moreover, we are not bound nor promoting any dataset that would lead to unfairness in any sense.

Besides, the use of our method has a **very little environmental impact** as there is no training phase and as the optimization is relatively fast and in the same order of magnitude as other approaches.

<footnote n="3">³https://web engr oregonstate edu/~lif/ SegTrack2/dataset.html
⁴https://lmb informatik uni freiburg.de/ resources/datasets/moseg en.html
⁵https://github com/facebookresearch/dino
⁶https://github com/facebookresearch/moco
⁷https://github com/lliuz/ARFlow
⁸https://github com/princeton-vl/RAFT</footnote>
<figure><img src="image_9.png" /><figcaption>Figure 7: Segmentation in sample frames from videos in SegTrack v2.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 8: Segmentation in sample frames from videos in SegTrack v2.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 9: Segmentation in sample frames from videos in SegTrack v2.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 10: Segmentation in sample frames from videos in DAVIS 2016.</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 11: Segmentation in sample frames from videos in DAVIS 2016.</figcaption></figure>
<figure><img src="image_14.png" /></figure>

CIS [90]

Ours

Ground Truth

<caption>Figure 12: Segmentation in sample frames from videos in DAVIS 2016.</caption>
<figure><img src="image_15.png" /><figcaption>Figure 13: Segmentation in sample frames from videos in DAVIS 2016.</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Figure 14: Segmentation in sample frames from videos in DAVIS 2016.</figcaption></figure>
<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>
<figure><img src="image_36.png" /><figcaption>Figure 16: Segmentation in sample frames from videos in FBMS-59.</figcaption></figure>
<figure><img src="image_37.png" /><figcaption>Figure 17: Segmentation in sample frames from videos in FBMS-59.</figcaption></figure>
<figure><img src="image_38.png" /><figcaption>Figure 18: Segmentation in sample frames from videos in FBMS-59.</figcaption></figure>
<figure><img src="image_39.png" /><figcaption>Figure 19: Segmentation in sample frames from videos in FBMS-59.</figcaption></figure>