00footnotetext: Support of the research by the Austrian Science Fund (FWF),
project I 4579-N, and the Czech Science Foundation (GAČR), project 20-09869L,
entitled “The many facets of orthomodularity”, as well as by ÖAD, project CZ
02/2019, entitled “Function algebras and ordered structures related to logic
and data fusion”, and, concerning the first author, by IGA, project PřF 2021
030, is gratefully acknowledged.

# Implication in finite posets with pseudocomplemented sections

Ivan Chajda and Helmut Länger

###### Abstract

It is well-known that relatively pseudocomplemented lattices can serve as an
algebraic semantics of intuitionistic logic. To extend the concept of relative
pseudocomplementation to non-distributive lattices, the first author
introduced so-called sectionally pseudocomplemented lattices, i.e. lattices
with top element $1$ where for every element $y$ the interval $[y,1]$, the so
called section, is pseudocomplemented. We extend this concept to posets with
top element. Our goal is to show that such a poset can be considered as an
algebraic semantics for a certain kind of more general intuitionistic logic
provided an implication is introduced as shown in the paper. We prove some
properties of such an implication. This implication is “unsharp” in the sense
that the value for given entries need not be a unique element, but may be a
subset of the poset in question. On the other hand, all of these values are as
high as possible. We show that this implication even determines the poset and
if a new operator $\odot$ is introduced in an “unsharp” way, such structure
forms an “unsharply” residuated poset.

AMS Subject Classification: 06A11, 06D15, 03B52, 03G10, 03B60

Keywords: Poset, section, relative pseudocomplement, poset with
pseudocomplemented sections, intuitionistic implication, unsharp implication,
unsharp conjunction, unsharp residuation

##  1 Introduction

Relatively pseudocomplemented lattices, often called Heyting algebras (see
e.g. [9] and [10]) or Brouwerian lattices (see e.g. [11]), arise from
intuitionistic logic and were first investigated by T. Skolem about 1920, see
also [8] and [1]. For a detailed development see e.g. [7]. Within this
context, the relative pseudocomplement $x*y$ of $x$ with respect to $y$ is
usually considered as intuitionistic implication, see e.g. [12] or [7].

Hence, in relatively pseudocomplemented lattices we define

$x\rightarrow y:=x*y.$

It is well-known that every finite pseudocomplemented lattice is distributive.
To extend investigations in intuitionistic logic also to the non-distributive
case, the first author introduced so-called sectionally pseudocomplemented
lattices, see [3] and [6]. These are lattices with a top element where for
every element $y$ and every element $x$ in the interval (so-called section)
$[y,1]$ there exists a pseudocomplement $x^{y}$ of $x$ with respect to $y$.
Putting

$x\rightarrow y:=(x\vee y)^{y}$ (1)

the situation becomes formally analogous to the case of relatively
pseudocomplemented lattices. For the typical case, consider the lattice
depicted in Figure 1:

$0$$a$$b$$c$$1$Fig. 1

It is evident that this lattice has pseudocomplemented sections, but the
lattice is neither relatively pseudocomplemented (since the relative
pseudocomplement of $c$ with respect to $a$ does not exist) nor distributive.

The operation tables for $x^{y}$ and $\rightarrow$ look as follows:

$\begin{array}[]{c|ccccc}x^{y}&0&a&b&c&1\\\ \hline\cr 0&1&-&-&-&-\\\
a&b&1&-&-&-\\\ b&c&-&1&-&-\\\ c&b&a&-&1&-\\\
1&0&a&b&c&1\end{array}\quad\quad\quad\begin{array}[]{c|ccccc}\rightarrow&0&a&b&c&1\\\
\hline\cr 0&1&1&1&1&1\\\ a&c&1&b&1&1\\\ b&c&a&1&c&1\\\ c&b&a&b&1&1\\\
1&0&a&b&c&1.\end{array}$

The notion of relatively pseudocomplemented lattices was extended to posets,
see e.g. [5]. It is useful when a reduct of intuitionistic logic is considered
where one studies only the connective implication but not other connectives
like disjunction or conjunction. Let us note that in intuitionistic logic, the
connectives implication, conjunction and disjunction are independent.

##  2 Posets with pseudocomplemented sections

To extend our study also to (not necessarily relatively pseudocomplemented)
posets with pseudocomplemented sections, let us introduce several necessary
concepts.

Let $(P,\leq)$ be a poset $a,b\in P$ and $A,B\subseteq P$. We say $A<B$ if
$x\leq y$ for all $x\in A$ and $y\in B$. Instead of $\\{a\\}<\\{b\\}$,
$\\{a\\}<B$ and $A<\\{b\\}$ we simply write $a<b$, $a<B$ and $A<b$,
respectively. Analogously we proceed with the relational symbols $\leq$, $>$
and $\geq$. Denote by

$L(A):=\\{x\in P\mid x\leq A\\}\text{ and }U(A):=\\{x\in P\mid A\leq x\\}$

the so-called lower and upper cone of $A$, respectively. Instead of
$L(\\{a\\})$, $L(\\{a,b\\})$, $L(A\cup\\{a\\})$, $L(A\cup B)$ and
$L\big{(}U(A)\big{)}$ we simply write $L(a)$, $L(a,b)$, $L(A,a)$, $L(A,B)$ and
$LU(A)$, respectively. Analogously, we proceed in similar cases. Denote the
set of all minimal and maximal elements of $A$ by $\operatorname{Min}A$ and
$\operatorname{Max}A$, respectively.

Recall that a pseudocomplemented poset is an ordered quadruple
$(P,\leq,{}^{*},0)$ where $(P,\leq,0)$ is a poset with bottom element $0$ and
∗ is a unary operation on $P$ such that for all $x\in P$, $x^{*}$ is the
greatest element of $(P,\leq)$ satisfying $L(x,x^{*})=0$. (Here and in the
following, we often identify singletons with their unique element.) This means
that $x\wedge x^{*}$ exists for each $x\in P$ and $x\wedge x^{*}=0$.

Let us mention that in every logic, both classical or non-classical, a
prominent role plays the logical connective implication. The reason is that
implication enables logical deduction, i.e. the derivation of new propositions
from given ones. In order to study a logic based on a poset, one cannot expect
that the result of implication will be uniquely determined. This means that
the result of the implication $x\rightarrow y$ for given elements $x$ and $y$
of a given poset $P$ would be a subset of $P$, not necessarily a singleton.
This is the reason why we will call such an implication “unsharp”. On the
other hand, we ask such an unsharp implication to satisfy the rules and
properties usually satisfied by an implication and, moreover, the results of
our implication should be as high as possible. We introduce such an unsharp
implication within the next section. In Proposition 2.4 we show that our
implication satisfies properties similar to those satisfied by the standard
implication. We also show that the values of results of our implication are
usually higher than those for implication of intuitionistic logic based on
relative pseudocomplementation. In the last section we introduce also an
unsharp connective conjunction which is connected with our implication via a
certain kind of adjointness.

######  Definition 2.1.

A finite poset with pseudocomplemented sections is an ordered quadruple
$\big{(}P,\leq,(^{y};y\in P),1\big{)}$ where $(P,\leq,1)$ is a finite poset
with top element $1$ and for every $y\in P$, $([y,1],\leq,{}^{y},y)$ is a
pseudocomplemented poset. For every $y\in P$ and every subset $B$ of $[y,1]$
put $B^{y}:=\\{b^{y}\mid b\in B\\}$. Finally, for all $x,y\in P$ define the
implication $x\rightarrow y$ as follows:

$x\rightarrow y:=\big{(}\operatorname{Min}U(x,y)\big{)}^{y}.$

A finite poset with $0$ and pseudocomplemented sections is an ordered
quintuple $\big{(}P,\leq,(^{y};y\in P),0,1\big{)}$ where
$\big{(}P,\leq,(^{y};y\in P),1\big{)}$ is a finite poset with
pseudocomplemented sections and $0$ is the bottom element of $(P,\leq)$.

Observe that because of $1\in U(x,y)$ we have
$\operatorname{Min}U(x,y)\neq\emptyset$.

######  Remark 2.2.

If $\big{(}P,\leq,(^{y};y\in P),1\big{)}$ is a finite poset with
pseudocomplemented sections, $b\in P$ and $a\in[b,1]$ then

$a^{b}=\max\\{x\in P\mid L(a,x)\cap[b,1]=b\\}.$

Hence, in general, $\rightarrow$ is not a binary operation on $P$ but an
operator assigning to each element of $P^{2}$ a non-empty subset of $P$. The
almost obvious relationship between the sectional pseudocomplementation and
the operator $\rightarrow$ is as follows.

######  Lemma 2.3.

Let $\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections and $a,b\in P$. Then the following hold:

  1. (i)

If $a\vee b$ exists in $(P,\leq)$ then $a\rightarrow b=(a\vee b)^{b}$,

  2. (ii)

if $b\leq a$ then $a\rightarrow b=a^{b}$.

###### Proof.

  1. (i)

If $a\vee b$ exists in $(P,\leq)$ then

$a\rightarrow
b=\big{(}\operatorname{Min}U(a,b)\big{)}^{b}=\big{(}\operatorname{Min}U(a\vee
b)\big{)}^{b}=(a\vee b)^{b}.$

  2. (ii)

if $b\leq a$ then because of (i) we have $a\rightarrow b=(a\vee b)^{b}=a^{b}$.

∎

In what follows we list some elementary but important properties of this
implication. We can see that these are analogous to know properties of
implication in classical and non-classical propositional calculus.

######  Proposition 2.4.

Let $\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections and $a,b\in P$. Then the following hold:

  1. (i)

$a\leq b$ if and only if $a\rightarrow b=1$,

  2. (ii)

if $a\vee b$ exists then $(a\vee b)\rightarrow b=a\rightarrow b$,

  3. (iii)

$1\rightarrow a=a$,

  4. (iv)

$a\leq b\rightarrow a$,

  5. (v)

$a\rightarrow(b\rightarrow a)=1$.

###### Proof.

  1. (i)

The following are equivalent:

$\displaystyle a$ $\displaystyle\leq b,$
$\displaystyle\operatorname{Min}U(a,b)$ $\displaystyle=b,$ $\displaystyle x$
$\displaystyle=b\text{ for all }x\in\operatorname{Min}U(a,b),$ $\displaystyle
x^{b}$ $\displaystyle=1\text{ for all }x\in\operatorname{Min}U(a,b),$
$\displaystyle\big{(}\operatorname{Min}U(a,b)\big{)}^{b}$ $\displaystyle=1,$
$\displaystyle a\rightarrow b$ $\displaystyle=1,$

  2. (ii)

if $a\vee b$ exists then

$(a\vee b)\rightarrow b=\big{(}\operatorname{Min}U(a\vee
b,b)\big{)}^{b}=\big{(}\operatorname{Min}U(a\vee
b)\big{)}^{b}=\big{(}\operatorname{Min}U(a,b)\big{)}^{b}=a\rightarrow b,$

  3. (iii)

$1\rightarrow
a=\big{(}\operatorname{Min}U(1,a)\big{)}^{a}=\big{(}\operatorname{Min}U(1)\big{)}^{a}=1^{a}=a,$

  4. (iv)

$a\leq\big{(}\operatorname{Min}U(b,a)\big{)}^{a}=b\rightarrow a$,

  5. (v)

this follows from (iii) and from (i) of Lemma 2.3.

∎

The next result shows that under appropriate assumptions our unsharp
implication satisfies important properties already known from standard
implication.

######  Proposition 2.5.

Let $\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections and $a,b,c\in P$. Then the following hold:

  1. (i)

If $a\leq b$ and $a\vee c$ exists in $(P,\leq)$ then $b\rightarrow c\leq
a\rightarrow c$,

  2. (ii)

if $a\vee b$ exists in $(P,\leq)$ then $a\leq(a\rightarrow b)\rightarrow b$,

  3. (iii)

if $a\vee b$ exists in $(P,\leq)$ then $a\rightarrow b=\big{(}(a\rightarrow
b)\rightarrow b\big{)}\rightarrow b$.

###### Proof.

  1. (i)

Since $a\vee c$ exists in $(P,\leq)$, we have $a\rightarrow c=(a\vee c)^{c}$
according to (i) of Lemma 2.3. Now, by (P2), everyone of the following
assertions implies the next one:

$\displaystyle a$ $\displaystyle\leq b,$ $\displaystyle U(b,c)$
$\displaystyle\subseteq U(a,c),$ $\displaystyle\operatorname{Min}U(b,c)$
$\displaystyle\subseteq U(a\vee c),$ $\displaystyle a\vee c$
$\displaystyle\leq x\text{ for all }x\in\operatorname{Min}U(b,c),$
$\displaystyle x^{c}$ $\displaystyle\leq(a\vee c)^{c}=a\rightarrow c\text{ for
all }x\in\operatorname{Min}U(b,c),$ $\displaystyle b\rightarrow c$
$\displaystyle=\big{(}\operatorname{Min}U(b,c)\big{)}^{c}\leq a\rightarrow c$

  2. (ii)

Because of (P3) and (i) and (ii) of Lemma 2.3 we have

$a\leq a\vee b\leq\big{(}(a\vee b)^{b}\big{)}^{b}=(a\rightarrow b)\rightarrow
b.$

  3. (iii)

Because of (i) of Lemma 2.3, (P4) and (ii) of Lemma 2.3 we have

$a\rightarrow b=(a\vee b)^{b}=\Big{(}\big{(}(a\vee
b)^{b}\big{)}^{b}\Big{)}^{b}=\big{(}(a\rightarrow b)\rightarrow
b\big{)}\rightarrow b.$

∎

Let $\mathbf{P}=(P,\leq)$ be a poset and $a,b\in P$. Recall the following
definitions.

  * •

The greatest element $x$ of $P$ satisfying $L(a,x)\subseteq L(b)$ is called
the relative pseudocomplement $a*b$ of $a$ with respect to $b$. The poset
$\mathbf{P}$ is called relatively pseudocomplemented if any two elements of
$P$ have a relative pseudocomplement, see [5] and [13].

  * •

The greatest element $x$ of $P$ satisfying $L(U(a,b),x)=L(b)$ is called the
sectional pseudocomplement $a\circ b$ of $a$ with respect to $b$. The poset
$\mathbf{P}$ is called sectionally pseudocomplemented if any two elements of
$P$ have a sectional pseudocomplement.

######  Remark 2.6.

Let $(P,\leq,1)$ be a poset with top element $1$ and $a,b\in P$ with $b\leq
a$. Further assume that the sectional pseudocomplement $a\circ b$ of $a$ with
respect to $b$ and the pseudocomplement of $a^{b}$ of $a$ in $[b,1]$ exist.
Then $a\circ b\leq a^{b}$.

###### Proof.

Since $b\in L(b)=L\big{(}U(a,b),a\circ b\big{)}$, we have $b\leq a\circ b$.
Moreover,

$L(a,a\circ b)\cap[b,1]=L\big{(}U(a),a\circ
b\big{)}\cap[b,1]=L\big{(}U(a,b),a\circ
b\big{)}\cap[b,1]=L(b)\cap[b,1]=\\{b\\}.$

Hence $a\circ b\leq a^{b}$. ∎

Let us note that the sectional pseudocomplement is not the same as the
pseudocomplement in the corresponding section. For example, consider the poset
depicted in Fig. 2. Then $a\notin[b,1]$. Thus the pseudocomplement of $a$ in
the section $[b,1]$, i.e. $a^{b}$, does not exist. On the other hand, the
sectional pseudocomplement $a\circ b$ of $a$ with respect to $b$ exists and is
equal to $b$ because $b$ is the greatest element $x$ satisfying
$L\big{(}U(a,b),x\big{)}=L(b)$ since $U(a,b)=\\{c,d,1\\}$. It is worth
noticing that $a\circ b$ differs from our unsharp implication $a\rightarrow b$
because $a\rightarrow b=\\{c,d\\}$.

######  Example 2.7.

The poset shown in Figure 2:

$0$$a$$b$$c$$d$$1$Fig. 2

has pseudocomplemented sections and is simultaneously relatively
pseudocomplemented. The tables for $x^{y}$, $\rightarrow$ and $*$ look as
follows:

$\begin{array}[]{c|cccccc}x^{y}&0&a&b&c&d&1\\\ \hline\cr 0&1&-&-&-&-&-\\\
a&b&1&-&-&-&-\\\ b&a&-&1&-&-&-\\\ c&0&d&d&1&-&-\\\ d&0&c&c&-&1&-\\\
1&0&a&b&c&d&1\end{array}\quad\begin{array}[]{c|cccccc}\rightarrow&0&a&b&c&d&1\\\
\hline\cr 0&1&1&1&1&1&1\\\ a&b&1&\\{c,d\\}&1&1&1\\\ b&a&\\{c,d\\}&1&1&1&1\\\
c&0&d&d&1&d&1\\\ d&0&c&c&c&1&1\\\
1&0&a&b&c&d&1\end{array}\quad\begin{array}[]{c|cccccc}*&0&a&b&c&d&1\\\
\hline\cr 0&1&1&1&1&1&1\\\ a&b&1&b&1&1&1\\\ b&a&a&1&1&1&1\\\ c&0&a&b&1&d&1\\\
d&0&a&b&c&1&1\\\ 1&0&a&b&c&d&1.\end{array}$

The intuitionistic implication, i.e. the relative pseudocomplement $*$ differs
from our “unsharp” implication $\rightarrow$, e.g. $a*b=b$ whereas
$a\rightarrow b=\\{c,d\\}$. Hence, although $a\rightarrow b$ is an “unsharp”
implication because its result is a two-element subset of $P$, its values $c$
and $d$ are greater than the value of intuitionistic implication $a*b$.

######  Example 2.8.

The poset shown in Figure 3:

$0$$a$$b$$c$$d$$e$$1$Fig. 3

has pseudocomplemented sections, but is not relatively pseudocomplemented
since the relative pseudocomplement of $b$ with respect to $a$ does not exist.
The tables for $x^{y}$ and $\rightarrow$ look as follows:

$\begin{array}[]{c|ccccccc}x^{y}&0&a&b&c&d&e&1\\\ \hline\cr 0&1&-&-&-&-&-&-\\\
a&c&1&-&-&-&-&-\\\ b&c&a&1&-&-&-&-\\\ c&b&-&-&1&-&-&-\\\ d&0&a&e&e&1&-&-\\\
e&0&a&d&d&-&1&-\\\
1&0&a&b&c&d&e&1.\end{array}\quad\quad\quad\begin{array}[]{c|ccccccc}\rightarrow&0&a&b&c&d&e&1\\\
\hline\cr 0&1&1&1&1&1&1&1\\\ a&c&1&1&\\{d,e\\}&1&1&1\\\
b&c&a&1&\\{d,e\\}&1&1&1\\\ c&b&a&\\{d,e\\}&1&1&1&1\\\ d&0&a&e&e&1&e&1\\\
e&0&a&d&d&d&1&1\\\ 1&0&a&b&c&d&e&1.\end{array}$

It is a question if, having an operator $\rightarrow$ on a finite set $A$, it
can be converted into a poset with pseudocomplemented sections. For this, we
introduce the following structure.

##  3 Implication algebras

Our next goal is to show that this unsharp implication in fact determines the
given finite poset with pseudocomplemented sections. For this purpose we
define the following concept.

######  Definition 3.1.

A finite I-algebra is an ordered triple $(A,\rightarrow,1)$ with a finite set
$A$, an operator $\rightarrow:A^{2}\rightarrow 2^{A}\setminus\\{\emptyset\\}$
and $1\in A$ satisfying the following conditions:

  1. (I1)

$x\rightarrow x\approx x\rightarrow 1\approx 1$,

  2. (I2)

$x\rightarrow y=y\rightarrow x=1\Rightarrow x=y$,

  3. (I3)

$x\rightarrow y=y\rightarrow z=1\Rightarrow x\rightarrow z=1$,

  4. (I4)

$y\rightarrow z=z\rightarrow x=z\rightarrow(x\rightarrow y)=1\Rightarrow z=y$,

  5. (I5)

$\big{(}y\rightarrow x=y\rightarrow u=1\text{ and }(y\rightarrow
z=z\rightarrow x=z\rightarrow u=1\Rightarrow z=y)\big{)}\Rightarrow
u\rightarrow(x\rightarrow y)=1$,

  6. (I6)

$x\rightarrow y=\\{z\rightarrow y\mid x\rightarrow z=y\rightarrow z=1,\text{
and }x\rightarrow u=y\rightarrow u=u\rightarrow z=1\Rightarrow u=z\\}$.

Now we can state and prove the following result.

######  Theorem 3.2.

Let $\mathbf{P}=\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections and put $x\rightarrow y:=\big{(}\min
U(x,y)\big{)}^{y}$ for all $x,y\in P$. Then
$\mathbb{I}(\mathbf{P}):=(P,\rightarrow,1)$ is a finite I-algebra.

###### Proof.

Let $a,b\in P$. According to (i) of Proposition 2.4, $a\leq b$ if and only if
$a\rightarrow b=1$, and according to (ii) of Lemma 2.3, $b\leq a$ implies
$a\rightarrow b=a^{b}$. Now (I1) follows since $\leq$ is reflexive and $1$ is
the top element of $(P,\leq)$, (I2) and (I3) follow by antisymmetry and
transitivity of $\leq$, respectively. Let $x,y,z,u\in P$. If $y\leq z\leq x$
and $z\leq x^{y}$ then $z\in L(x,x^{y})\cap[y,1]=\\{y\\}$, i.e. $z=y$ which
shows that (I4) holds. Now for $x,u\in[y,1]$ the following are equivalent:

$\displaystyle y\rightarrow z=z\rightarrow x=z\rightarrow u=1$
$\displaystyle\Rightarrow z=y,$ $\displaystyle z\in L(x,u)\cap[y,1]$
$\displaystyle\Rightarrow z=y,$ $\displaystyle L(x,u)\cap[y,1]$
$\displaystyle\subseteq\\{y\\},$ $\displaystyle L(x,u)\cap[y,1]$
$\displaystyle=\\{y\\}.$

Since for $x,u\in[y,1]$, $L(x,u)\cap[y,1]=\\{y\\}$ implies $u\leq x^{y}$, we
have (I5). Finally, (I6) follows from the definition of $\rightarrow$. ∎

However, also the converse of Theorem 3.2 is true, see the following result.

######  Theorem 3.3.

Let $\mathbf{A}=(A,\rightarrow,1)$ be a finite I-algebra and define

$\displaystyle x\leq y$ $\displaystyle:\Leftrightarrow x\rightarrow y=1,$
$\displaystyle x^{y}$ $\displaystyle:=x\rightarrow y\text{ whenever }y\leq x$

($x,y\in A$). Then $\mathbb{P}(\mathbf{A}):=\big{(}A,\leq,(^{y};y\in
A),1\big{)}$ is a finite poset with pseudocomplemented sections.

###### Proof.

Because of (I1) – (I3), $(A,\leq,1)$ is a finite poset with top element $1$,
because of (I4), $L(x,x^{y})\cap[y,1]\subseteq\\{y\\}$ for all $x,y\in I$ with
$y\leq x$ and hence $L(x,x^{y})\cap[y,1]=\\{y\\}$ for all $x,y\in I$ with
$y\leq x$, and because of (I5), $y\in A$, $x,u\in[y,1]$ and
$L(x,u)\cap[y,1]=\\{y\\}$ imply $u\leq x^{y}$. Hence for all $y\in A$,
$([y,1],\leq,{}^{y},y)$ is a pseudocomplemented poset. ∎

######  Remark 3.4.

In the above proof, condition (I6) of Definition 3.1 is not needed. We need
this condition in order to prove that the above described correspondence is
one-to-one.

Now we show that the assignments from Theorems 3.2 and 3.3 are mutually
inverse.

######  Theorem 3.5.

The correspondence described in Theorems 3.2 and 3.3 is one-to-one.

###### Proof.

Let $\mathbf{P}=\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections, put

$\displaystyle\mathbb{I}(\mathbf{P})$ $\displaystyle=(P,\rightarrow,1),$
$\displaystyle\mathbb{P}\big{(}\mathbb{I}(\mathbf{P})\big{)}$
$\displaystyle=\big{(}P,\leq^{\prime},(_{y};y\in P),1\big{)}$

and let $a,b\in P$. Then because of the definition of $\leq^{\prime}$ and (i)
of Proposition 2.4 the following are equivalent:

$\displaystyle a$ $\displaystyle\leq^{\prime}b,$ $\displaystyle a\rightarrow
b$ $\displaystyle=1,$ $\displaystyle a$ $\displaystyle\leq b.$

If $b\leq a$ then because of the definition of $a_{b}$ and (ii) of Lemma 2.3
we have $a_{b}=a\rightarrow b=a^{b}$ This shows
$\mathbb{P}\big{(}\mathbb{I}(\mathbf{P})\big{)}=\mathbf{P}$. Now let
$\mathbf{A}=(A,\rightarrow,1)$ be a finite I-algebra, put

$\displaystyle\mathbb{P}(\mathbf{A})$ $\displaystyle=\big{(}A,\leq,(^{y};y\in
I),1\big{)},$ $\displaystyle\mathbb{I}\big{(}\mathbb{P}(\mathbf{A})\big{)}$
$\displaystyle=(A,\Rightarrow,1)$

and let $a,b\in A$. Then

$a\Rightarrow b=\big{(}\operatorname{Min}U(a,b)\big{)}^{b}=\\{x^{b}\mid
a,b\leq x,\text{ and }a,b\leq y\leq x\text{ implies }y=x\\}=a\rightarrow b$

because of the definition of $\leq$ and (I6). This shows
$\mathbb{I}\big{(}\mathbb{P}(\mathbf{A})\big{)}=\mathbf{A}$. ∎

In every finite poset $\big{(}P,\leq,(^{y};y\in P),0,1\big{)}$ with $0$ and
pseudocomplemented sections one can define $\neg x:=x\rightarrow 0$ for all
$x\in P$. Observe that $\neg x=\max\\{y\in P\mid L(x,y)=0\\}$ for all $x\in P$
and hence $\neg x=x^{0}$ for all $x\in P$. Due to the fact that $\neg x$ is
the pseudocomplementation as defined usually (see e.g. [1] or [13]), it
satisfies the known properties as follows:

  1. (P1)

$\neg 0=1$ and $\neg 1=0$,

  2. (P2)

$x\leq y$ implies $\neg y\leq\neg x$,

  3. (P3)

$x\leq\neg\neg x$,

  4. (P4)

$\neg\neg\neg x=\neg x$.

######  Remark 3.6.

Condition (P2) expresses the fact that our negation and implication satisfy
the contraposition law, i.e.

$\text{if }x\rightarrow y=1\text{ then also }\neg y\rightarrow\neg x=1.$

At the end of this section we show that every bounded pseudocomplemented poset
contains a subposet where the unary negation ′ is a complementation. This is
in fact analogous to the Glivenko Theorem (see e.g. [2]) for
pseudocomplemented lattices.

######  Proposition 3.7.

Let $\mathbf{P}=(P,\leq,{}^{\prime},0,1)$ be a bounded pseudocomplemented
poset. Then $(P^{\prime},\leq,{}^{\prime},0,1)$ with
$P^{\prime}:=\\{x^{\prime}\mid x\in P\\}$ is a complemented poset.

###### Proof.

Clearly, $P^{\prime}=\\{x\in P\mid x^{\prime\prime}=x\\}$. Let $a,b\in
P^{\prime}$. Then $a^{\prime}\in P^{\prime}$. Moreover, $L(a,a^{\prime})=0$.
If $b\in U(a,a^{\prime})$ then $b^{\prime}\in
L(a^{\prime},a^{\prime\prime})=L(a,a^{\prime})=0$ and hence
$b=b^{\prime\prime}=0^{\prime}=1$. This shows $U(a,a^{\prime})=1$, i.e.
$a^{\prime}$ is a complement of $a$. ∎

######  Example 3.8.

If $(P,\leq,{}^{\prime},0,1)$ is the bounded pseudocomplemented poset of
Example 2.8 then the complemented poset $(P^{\prime},\leq,{}^{\prime},0,1)$ is
depicted in Figure 4:

$0$$b$$c$$1$Fig. 4

##  4 Adjointness of implication with unsharp conjunction

It is known that every relatively pseudocomplemented lattice is residuated, in
fact it is a “prototype” of a residuated lattice where the operation
multiplication is considered as the lattice meet and the relative
pseudocomplement as a residuum. As mentioned in the introduction, we define
sectionally pseudocomplemented lattices in the sake to extend the concept of
relative pseudocomplementation to non-distributive lattices. The question
concerning residuation in sectionally pseudocomplemented lattices was answered
by the authors and J. Kühr ([4]) as follows.

A lattice $\mathbf{L}=(L,\vee,\wedge,\odot,\rightarrow,1)$ with top element
$1$ and with two binary operations $\odot$ and $\rightarrow$ is called
relatively residuated if

  1. (i)

$(L,\odot,1)$ is a commutative groupoid with $1$,

  2. (ii)

$x\leq y$ implies $x\odot z\leq y\odot z$,

  3. (iii)

$(x\vee z)\odot(y\vee z)\leq z$ if and only if $x\vee z\leq y\rightarrow z$.

It is worth noticing that the class of relatively residuated lattices forms a
variety, see [4]. Namely, under condition (i), conditions (ii) and (iii) are
equivalent to the identities

  1. (iv)

$x\odot z\leq(x\vee y)\odot z$,

  2. (v)

$z\vee y\leq x\rightarrow\Big{(}\big{(}(x\vee y)\odot(z\vee y)\big{)}\vee
y\Big{)}$,

  3. (vi)

$(x\rightarrow y)\odot(x\vee y)\leq y$.

Unfortunately, we cannot adopt this definition for posets $(P,\leq)$ because
we cannot use the lattice operations and, moreover, our implication is not an
operation but an operator, i.e. its result need not be a singleton. However,
we can proceed as follows. Having in mind that $\rightarrow$ is unsharp, we
can introduce an unsharp connective conjunction as follows:

$x\odot y:=\operatorname{Max}L(x,y)$

and for non-singleton subsets $A,B$ of $P$ we define $A\odot
B:=\operatorname{Max}L(A,B)$. One can mention that this conjunction reaches
the maximal possible values for given entries $x$ and $y$. Moreover, the
operator $\odot$ is idempotent since for every $x\in P$ we have

$x\odot x=\operatorname{Max}L(x,x)=\operatorname{Max}L(x)=x.$

Now we can define the following concept.

######  Definition 4.1.

A poset $\mathbf{P}=(P,\leq,\odot,\rightarrow,1)$ with top element $1$ and two
operators $\odot$ and $\rightarrow$, both mappings from $P^{2}$ to $2^{P}$,
such that

  1. (i)

$\odot$ is commutative and associative and $x\odot 1\approx x$,

  2. (ii)

if $x\leq y$ and $z\in P$ then there exists some $t\in y\odot z$ with $x\odot
z\leq t$,

  3. (iii)

$z\in x\odot y$ if and only if $(z\leq x,y$ and $x\leq y\rightarrow z)$

will be called unsharply residuated. Condition (iii) will be called unsharp
adjointness. We call an unsharply residuated poset $\mathbf{P}$ divisible if
for all $x,y\in P$ with $x\geq y$ we have that $x\rightarrow y$ is a singleton
and $\big{(}x\odot(x\rightarrow y)\big{)}\cap[y,1]=\\{y\\}$.

We are going to show that finite posets with pseudocomplemented sections are
unsharply residuated and divisible.

######  Theorem 4.2.

Let $\big{(}P,\leq,(^{y};y\in P),1\big{)}$ be a finite poset with
pseudocomplemented sections and for $x,y\in P$ define

$\displaystyle x\odot y$ $\displaystyle:=\operatorname{Max}L(x,y),$
$\displaystyle x\rightarrow y$
$\displaystyle:=\big{(}\operatorname{Min}U(x,y)\big{)}^{y}.$

Then $(P,\leq,\odot,\rightarrow,1)$ is unsharply residuated and divisible.

###### Proof.

Let $a,b,c\in P$. Then

$a\odot 1=\operatorname{Max}L(a,1)=\operatorname{Max}L(a)=a$

and, clearly, $\odot$ is commutative. Moreover,

$\displaystyle(a\odot b)\odot c$
$\displaystyle=\operatorname{Max}L\big{(}\operatorname{Max}L(a,b),c\big{)}=\operatorname{Max}\Big{(}L\big{(}\operatorname{Max}L(a,b)\big{)}\cap
L(c)\Big{)}=$ $\displaystyle=\operatorname{Max}\big{(}L(a,b)\cap
L(c)\big{)}=\operatorname{Max}L(a,b,c)=\operatorname{Max}\big{(}L(a)\cap
L(b,c)\big{)}=$ $\displaystyle=\operatorname{Max}\Big{(}L(a)\cap
L\big{(}\operatorname{Max}L(b,c)\big{)}\Big{)}=\operatorname{Max}L\big{(}a,\operatorname{Max}L(b,c)\big{)}=a\odot(b\odot
c).$

Thus $\odot$ satisfies (i) of Definition 4.1. If $a\leq b$ then

$a\circ c=\operatorname{Max}L(a,c)\subseteq L(a,c)\subseteq L(b,c)$

and hence there exists some $d\in\operatorname{Max}L(b,c)$ with $a\odot c\leq
d$. This shows (ii) of Definition 4.1. Now unsharp adjointness remains to be
proved. Because of Lemma 2.3 (ii) the following are equivalent:

$\displaystyle c\in a\odot b,$ $\displaystyle c\in\operatorname{Max}L(a,b),$
$\displaystyle L(a,b)\cap[c,1]=\\{c\\},$ $\displaystyle c\leq a,b\text{ and
}a\leq b^{c},$ $\displaystyle c\leq a,b\text{ and }a\leq b\rightarrow c.$

Now assume $a\geq b$. Then $a\rightarrow b=a^{b}$ and

$\big{(}a\odot(a\rightarrow
b)\big{)}\cap[b,1]=\big{(}\operatorname{Max}L(a,a^{b})\big{)}\cap[b,1]\subseteq
L(a,a^{b})\cap[b,1]=\\{b\\}.$

On the other hand, $b\in L(a,a^{b})$ and if $b\leq c\in L(a,a^{b})$ then $c\in
L(a,a^{b})\cap[b,1]=\\{b\\}$, i.e. $c=b$. This shows that
$b\in\operatorname{Max}L(a,a^{b})$ and hence
$b\in\big{(}\operatorname{Max}L(a,a^{b})\big{)}\cap[b,1]$, thus

$\big{(}\operatorname{Max}L(a,a^{b})\big{)}\cap[b,1]=\\{b\\}.$

proving divisibility of $(P,\leq,\odot,\rightarrow,1)$. ∎

The divisibility has an essential influence on the logic for which the
considered unsharply residuated poset is an algebraic semantics. Namely, if we
know the truth values of $x$ and $x\rightarrow y$ and we know that $y\leq x$
then the truth value of $y$ is exactly the conjunction of $x$ and
$x\rightarrow y$, which is just the derivation rule Modus Ponens.

If an unsharply residuated poset is a lattice then clearly we have

$x\odot y=\operatorname{Max}L(x,y)=\operatorname{Max}L(x\wedge y)=x\wedge y$

and the fact that $z\leq x,y$ can be expressed by $x\vee z=x$ and $y\vee z=y$.
Then unsharp adjointness can be formulated as follows:

$(x\vee z)\odot(y\vee z)=z\text{ if and only if }x\vee z\leq(y\vee
z)\rightarrow z.$

However, by (ii) of Proposition 2.4 we know that

$(y\vee z)\rightarrow z=y\rightarrow z,$

and

$(x\vee z)\odot(y\vee z)\geq z$

automatically holds. Hence the left-hand side of (iii) is equivalent to
$(x\vee z)\odot(y\vee z)\leq z$. Altogether, we obtain

$(x\vee z)\odot(y\vee z)\leq z\text{ if and only if }x\vee z\leq y\rightarrow
z$

which is just relative adjointness as defined in [4] and mentioned above. This
means that Definition 4.1 is compatible with the corresponding definition for
lattices.

######  Example 4.3.

Let us consider the poset from Example 2.8. The table for $\odot$ looks as
follows:

$\begin{array}[]{c|ccccccc}\odot&0&a&b&c&d&e&1\\\ \hline\cr 0&0&0&0&0&0&0&0\\\
a&0&a&a&0&a&a&a\\\ b&0&a&b&0&b&b&b\\\ c&0&0&0&c&c&c&c\\\
d&0&a&b&c&d&\\{b,c\\}&d\\\ e&0&a&b&c&\\{b,c\\}&e&e\\\
1&0&a&b&c&d&e&1.\end{array}$

We can see that $d\odot e=\\{b,c\\}$ is not a singleton, and $b\in d\odot e$
implies $b\leq d,e$ and $d\leq d=e\rightarrow b$; also, conversely, $c\leq
e,d$ and $e\leq e=d\rightarrow c$ imply $c\in\\{b,c\\}=e\odot d$.

##  5 Conclusion

We constructed a binary operator on a finite poset with pseudocomplemented
sections which can serve as an unsharp implication. It satisfies important
properties required for implication in various sorts of propositional logics.
Moreover, a negation derived by means of this implication satisfies the
properties of implication in intuitionistic logic, thus our poset with this
unsharp implication can be recognized as an algebraic semantics of a general
case of intuitionistic logic. Moreover, an unsharp conjunction is introduced
having similar properties as those satisfied by the connective conjunction in
propositional calculus. This unsharp conjunction together with the mentioned
unsharp implication forms an adjoint pair. Hence, the logic based on such a
poset can be considered as a fairly general kind of substructural logic.

Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] R. Balbes, On free pseudo-complemented and relatively pseudo-complemented semi-lattices. Fund. Math. 78 (1973), 119–131.
  * [2] G. Birkhoff, Lattice Theory. AMS, Providence, R. I., 1979. ISBN 0-8218-1025-1.
  * [3] I. Chajda, An extension of relative pseudocomplementation to non-distributive lattices. Acta Sci. Math. (Szeged) 69 (2003), 491–496.
  * [4] I. Chajda, J. Kühr and H. Länger, Relatively residuated lattices and posets, Math. Slovaca 70 (2020), 239–250.
  * [5] I. Chajda, H. Länger and J. Paseka, Algebraic aspects of relatively pseudocomplemented posets. Order 37 (2020), 1–29.
  * [6] I. Chajda and S. Radeleczki, On varieties defined by pseudocomplemented nondistributive lattices. Publ. Math. Debrecen 63 (2003), 737–750.
  * [7] H. B. Curry, Foundations of Mathematical Logic. Dover, New York 1977.
  * [8] O. Frink, Pseudo-complements in semi-lattices. Duke Math. J. 29 (1962), 505–514.
  * [9] L. Iturrioz, Łukasiewicz and symmetrical Heyting algebras. Z. Math. Logik Grundlagen Math. 23 (1977), 131–136.
  * [10] P. Köhler, A subdirectly irreducible double Heyting algebra which is not simple. Algebra Universalis 10 (1980), 189–194.
  * [11] P. Köhler, Brouwerian semilattices. Trans. Amer. Math. Soc. 268 (1981), 103–126.
  * [12] W. C. Nemitz, Implicative semi-lattices. Trans. Amer. Math. Soc. 117 (1965), 128–142.
  * [13] P. V. Venkatanarasimhan, Pseudo-complements in posets. Proc. Amer. Math. Soc. 28 (1971), 9–17.

Authors’ addresses:

Ivan Chajda
Palacký University Olomouc
Faculty of Science
Department of Algebra and Geometry
17\. listopadu 12
771 46 Olomouc
Czech Republic
<EMAIL_ADDRESS>
Helmut Länger
TU Wien
Faculty of Mathematics and Geoinformation
Institute of Discrete Mathematics and Geometry
Wiedner Hauptstraße 8-10
1040 Vienna
Austria, and
Palacký University Olomouc
Faculty of Science
Department of Algebra and Geometry
17\. listopadu 12
771 46 Olomouc
Czech Republic
<EMAIL_ADDRESS>


# MUNet: Motion Uncertainty-aware Semi-supervised Video Object Segmentation

Jiadai Sun1∗, Yuxin Mao1∗, Yuchao Dai1∗∗, Yiran Zhong2, Jianyuan Wang2
1School of Electronics and Information, Northwestern Polytechnical University,
Xi’an, China
2SenseTime, Shanghai, China

###### Abstract

The task of semi-supervised video object segmentation (VOS) has been greatly
advanced and state-of-the-art performance has been made by dense matching-
based methods. The recent methods leverage space-time memory (STM) networks
and learn to retrieve relevant information from all available sources, where
the past frames with object masks form an external memory and the current
frame as the query is segmented using the mask information in the memory.
However, when forming the memory and performing matching, these methods only
exploit the appearance information while ignoring the motion information. In
this paper, we advocate the return of the _motion information_ and propose a
motion uncertainty-aware framework (MUNet) for semi-supervised VOS. First, we
propose an implicit method to learn the spatial correspondences between
neighboring frames, building upon a correlation cost volume. To handle the
challenging cases of occlusion and textureless regions during constructing
dense correspondences, we incorporate the uncertainty in dense matching and
achieve motion uncertainty-aware feature representation. Second, we introduce
a motion-aware spatial attention module to effectively fuse the motion feature
with the semantic feature. Comprehensive experiments on challenging benchmarks
show that using a small amount of data and combining it with powerful motion
information can bring a significant performance boost. We achieve ${76.5\%}$
$\mathcal{J}\&\mathcal{F}$ only using DAVIS17 for training, which
significantly outperforms the SOTA methods under the low-data protocol. The
code will be released.

###### keywords:

video object segmentation , uncertainty, motion estimation, self-supervised

mytitlenotemytitlenotefootnotetext: The first two authors contributed
equally.mytitlenotemytitlenotefootnotetext: Yuchao Dai<EMAIL_ADDRESS>is the corresponding author.

##  1 Introduction

Video object segmentation (VOS) aims at segmenting the foreground objects from
a given video with motion, which is a classic task in computer vision with
many applications, including surveillance, video compression, and motion
understanding _etc_. In this paper, we focus on the most practical and widely
studied setting, _i.e_., semi-supervised VOS [1, 2, 3, 4, 5], whereas the
scope is to segment target objects over video sequences only given the initial
mask of the first frame as prior and visual guidance. This is a challenging
problem because the target objects can be confused with similar instances of
the same category, and their appearance might vary drastically over time due
to scale change, pose changes, fast motion, truncation, blurry effects,
occlusions _etc_. Essentially, these challenges could not be addressed with
image appearance information only.

Recently, various deep learning based VOS approaches have been proposed [6,
7], which could be roughly categorized as propagation-based methods [8, 9, 10]
and feature matching based methods [4, 11, 1, 12, 13]. The former generally
formulate the task as object mask propagation, while the latter leverages
memory networks to retrieve relevant information. Nowadays, the feature
matching-based methods such as Space-Time Memory (STM) Networks [4, 1, 11, 14,
12, 13] have achieved state-of-the-art performance in VOS. The key to the
success lies in introducing the feature matching of historical frames using
non-local operations with a well-designed feature-memory-bank mechanism. They
conduct matching using all previous frames with the corresponding object
segmentation results through feature similarity query, and infer the object
mask of the current frame. However, these methods heavily rely on the matching
of object appearance between frames, while motion information, as the critical
feature between video frames, tends to be ignored. Prior to the success of
these feature matching-based methods, explicit motion modeling in the form of
dense optical flow have been exploited [15, 16, 8, 17, 18, 10, 19], where the
dense optical flow is pre-computed from optical flow estimation networks [20,
21, 22, 23, 24, 25, 26]. However, the explicit use of optical flow not only
requires additional large dataset (having a domain gap with VOS datasets)
training for an optical flow network but also cannot capture the critical
challenges in VOS, _i.e_., occlusion, textureless regions, fast motion, and
blurry effects.

Figure 1: Qualitative comparison with competing methods [1, 2, 3, 4] on three
sequences of DAVIS17 validation set. Through the implicit modeling of objects
motion and uncertainty, we can obtain more accurate results, especially in
multiple bodies movements (row#1,3) and thin lines (row#2). The inaccurate
parts are marked with a yellow dashed box.

In this paper, we advocate that VOS should not only rely on image appearance
similarity matching but also emphasize the essential motion information from
the video, which exists in any adjacent frames and will not disappear over
time. We propose a novel framework for semi-supervised VOS named MUNet that
embeds motion information into a single branch pipeline without a pre-computed
optical flow. Given a video sequence, MUNet uses a dense matching based method
with a feature-memory-bank to store both appearance and motion features, as
shown in Fig. 2. To avoid problems caused by explicitly using optical flow, we
propose a lightweight Motion Uncertainty-aware Layer (MU-Layer) to implicitly
model motion information from adjacent frames. Specifically, we use a cost
volume to model the displacement and motion uncertainty as a motion feature to
establish spatio-temporal relationships, which is calculated from high-level
semantic features of adjacent frames. In addition, we design a Motion-aware
Spatial Attention Module (MSAM) to effectively fuse the appearance feature and
the motion uncertainty-aware feature, then we use this module to guide the
segmentation of video sequences. Different from the two-stream methods that
need pre-computed optical flow as input, MUNet only requires the raw images
and does not need the supervision of optical flow, which greatly expands the
practicability and scope of application. Meanwhile, under the experimental
protocol using a small amount of data, the powerful motion information brings
a significant performance boost without complex tricks.

We conduct comprehensive experiments on DAVIS17 and YouTube-VOS18.
Experimental results show that our method achieves state-of-the-art accuracy
on the validation set of DAVIS17 ($\mathcal{J\&F}\ {76.5}\%$ ranks 1st under
protocol(1), ${81.1}\%$ ranks 2nd under protocol(2), ${78.1}\%$ ranks 1st
under protocol(3-1)), which exceeds all competing methods under the same
settings. We provide qualitative comparisons with four SOTA methods [1, 2, 3,
4] in Fig. 1. MUNet can accurately demarcate the boundaries of multiple
objects and does not overly cover or ignore small structures. As shown in Fig.
5, the MU-Layer can implicitly learn a reasonable uncertainty map and
displacement vector, and effectively activate the area of the moving object
through the motion-aware spatial attention module. Our main contributions are
summarized as follows.

  * •

To the best of our knowledge, we are the first to embed motion information
into an end-to-end VOS pipeline with a single branch and without a precomputed
optical flow.

  * •

We introduce the MU-Layer and MSAM to learn the motion features with
uncertainty, which provides critical information for VOS.

  * •

Experimental evaluation on benchmark datasets with wide protocols verifies the
superiority of our proposed method, where our method is competitive with the
existing SOTA methods, especially the best performance under low-data
protocols, _i.e_. (1), (3-1).

##  2 Related Work

In this section, we introduce previous works from two categories of VOS as
feature matching based methods and motion based methods.

Feature matching methods. STM[4] achieves great success, which performs dense
feature matching across the entire spatio-temporal volume of the video through
a dynamic memory bank, _i.e_. saves the spatio-temporal information of
previous frames. To alleviate the problem of missing samples and out-of-memory
crashes when processing long videos, AFB-URR[1] introduces the adaptive
feature bank to organize the object features by weighted averaging and
discards obsolete features by least frequently used index principle. STM-
Cycle[11] incorporates cycle consistency to mitigate the error propagation
problem. [14] proposes a global context module using attentions to reduce
temporal information and guide the segmentation. RANet[27] is a hybrid
strategy, integrating the insights of matching based and propagation based
methods to learn pixel-level similarity. KMN[13] and GraphMem[12] focus more
on memory bank optimization to achieve more accurate key-value matching, both
are accompanied by data augmentation, such as Hide-and-Seek and Label
Shuffling, and their performance will drop a lot if the augmentation is
removed. We agree that these schemes will also give us an improvement, but
this paper is dedicated to using simple motions to emphasize the essentials.
Besides, although these methods have used temporal information to improve
accuracy, they ignore the most essential motion information.

Motion-based methods. Such methods can be roughly classified as mask
propagation methods [8, 9, 10, 28] and two-stream methods [15, 18, 17, 16] .
The mask propagation methods start from an annotated frame and propagates
masks through the entire video sequence, and the propagation process is often
guided by optical flow. Two-stream architecture usually fuses feature between
appearance (RGB branch) and motion (optical flow branch).

However, such methods highly dependent on high-quality pre-inferenced optical
flow [20, 21, 22, 23, 24, 26], and the performance will be limited by the
generalization ability of optical flow network due to the fact that there is
no ground truth of optical flow in the common VOS task. RMNet [28] uses the
mask of the previous frame and pre-computed optical flow to generate the
attention mask for current frame, but different optical flow networks [20, 26]
are selected for different datasets. It also shows that this kind of methods
cannot escape the disadvantages of generalization. As for mask propagation
methods, they rely on temporal continuity from optical flow and spatio-
temporal context from the previous frames, this leads these methods are
difficult to deal with occlusions, rapid motion, and complex deformation of
objects, also meets performance drift over time once the propagation becomes
unreliable.

##  3 Motion Uncertainty-aware VOS

Given a video sequence with ${T}$ frames,
$\mathcal{I}_{t}\in\mathbb{R}^{H\times W\times 3}$, $t\in[1,T]$ is the $t$-th
frame RGB image, $\mathcal{M}_{t}\in\mathbb{R}^{H\times W\times 1}$ is the
ground truth object segmentation mask and $\widehat{\mathcal{{M}}}_{t}$
denotes the predicted object mask. Semi-supervised VOS aims to predict the
object masks of all following video frames with the first RGB image
$\mathcal{I}_{1}$ and its object annotation mask $\mathcal{M}_{1}$ as prior,
which can be formulated as
${\widehat{\mathcal{M}}_{t}}=\mathcal{H}_{\theta}([\mathcal{I}_{1},\mathcal{M}_{1}...\mathcal{I}_{t-1},\widehat{\mathcal{M}}_{t-1}],\mathcal{I}_{t})$,
where $\mathcal{H}_{\theta}$ is an object segmentation network with learnable
weights $\theta$.
$[\mathcal{I}_{1},\mathcal{M}_{1}...\mathcal{I}_{t-1},\widehat{\mathcal{M}}_{t-1}]$
denotes the historical frames before the current frame $t$ that can be used
directly or implicitly to infer the object mask.

Figure 2: MUNet architecture. First, we use Enc-Q and Enc-R to extract the
semantic features $\mathcal{F}^{s}_{t},\mathcal{F}^{s}_{t-1}$ of
$\mathcal{I}_{t},\mathcal{I}_{t-1}$ from image appearance. Then, we use MU-
Layer to calculate the motion feature $\mathcal{F}^{m}_{t}$, and feed it into
MSAM to guide and enhance the semantic feature $\mathcal{F}^{s}_{t}$. The
matching results of Key-value Matcher is fed into the Decoder to generate the
object mask $\widehat{\mathcal{M}}_{t}$, and the memory feature-bank is
updated dynamically over time.

###  3.1 Network Overview

Our MUNet is a pixel-level dense matching method. The network architecture as
illustrated in Fig. 2 consists of four seamless parts: 1) two encoders as
feature extractors, 2) a Motion Uncertainty-aware Layer (MU-Layer), 3) a
Motion-aware Spatial Attention Module (MSAM), and 4) a decoder with a feature
memory bank.

First, the reference image $\mathcal{I}_{t-1}$ and mask $\mathcal{M}_{t-1}$
are fed into the reference encoder Enc-R, the query image $\mathcal{I}_{t}$
and adjacent frame $\mathcal{I}_{t-1}$ are respectively input to query encoder
Enc-Q with shared weights. Second, the semantic features
$\mathcal{F}^{s}_{t-1},\mathcal{F}^{s}_{t}$ from Enc-Q are input to the MU-
Layer to obtain the motion feature $\mathcal{F}^{m}_{t}$, more details are
described in Sec. 3.2. Then, we use MSAM to take advantage of the motion
feature $\mathcal{F}^{m}_{t}$ from adjacent frames to enhance the semantic
feature embed by Enc-Q in Sec. 3.3.

In [4, 11, 1], the semantic features output by Enc-R and Enc-Q are directly
used for key-value embedding, where the keys are used for addressing and
matching, while the values are used to preserve feature information. This will
cause the query process to rely heavily on the similarity matching of
appearance semantic features, which may lead to appearance confusion and wrong
predictions caused by similar instances. Different from them, for a query
image, we use the motion enhanced feature from MASM for key-value embedding,
and obtain the key-value pairs $\\{k_{t}^{Q},v_{t}^{Q}\\}$ to match the most
similar features in the memory bank. The key-value pairs
$[\\{k_{1}^{R},v_{1}^{R}\\},...,\\{k_{t-1}^{R},v_{t-1}^{R}\\}]$ of historical
images are stored in memory bank, updated dynamically over time. Finally, the
matching results from memory bank are fed into decoder, and then output the
segmentation mask of each object. We use ResNet50[29] as the backbone of two
encoders. For the query encoder Enc-Q, we take the output feature map of
Layer-4 (res4) as a semantic feature
$\mathcal{F}^{s}_{t}\in\mathbb{R}^{(H/16)\times(W/16)\times 1024}$, where $H$
and $W$ are the height and width of raw image shape correspondingly. The
reference encoder Enc-R is slightly different from the vanilla ResNet50, which
takes the RGB image (3-channel) and its segmentation label mask (1-channel) as
inputs to extract object-level semantic feature.

###  3.2 Motion Uncertainty-aware Layer (MU-Layer)

Here we introduce MU-Layer, which establishes spatio-temporal relationships
based on the motion feature calculated from high-level semantic features of
adjacent frames. We construct a cost volume to model pixel-wise feature
similarity that indicates the rough motion.

Cost Volume. For semantic features
$\mathcal{F}^{s}_{t-1},\mathcal{F}^{s}_{t}\in\mathbb{R}^{H^{\prime}\times
W^{\prime}\times D}$ of reference and query images from Enc-Q, where
$H^{\prime},W^{\prime}$ indicates ${H}/{16},{W}/{16}$ of the input image
shape, $D$ is the feature dimension. In order to achieve lightweight
computing, we first reduce the feature dimension to ${D}/{4}$ by $1\times 1$
convolution. Then we define the correlation as
${\rm{\mathbf{C}}}\in\mathbb{R}^{U\times V\times H^{\prime}\times
W^{\prime}}$, which can be efficiently computed as cosine similarity between
each pixel in the $H^{\prime}\times W^{\prime}$ reference image with a set of
candidate targets in a $U\times V$ search window.

$\displaystyle{\rm{\mathbf{C}}}({\rm\mathbf{u}},{\rm\mathbf{x}})=\frac{\mathcal{F}^{s}_{t}({\rm\mathbf{x}})\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\mathcal{F}^{s}_{t-1}({\rm\mathbf{x}}+{\rm\mathbf{u}})}{\big{|}\big{|}\mathcal{F}^{s}_{t}({\rm\mathbf{x}})\big{|}\big{|}\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\big{|}\big{|}\mathcal{F}^{s}_{t-1}({\rm\mathbf{x}}+{\rm\mathbf{u}})\big{|}\big{|}},$
(1)

where ${\rm\mathbf{x}}\\!=\\!(x,y)$ is the source pixel coordinate,
${\rm\mathbf{u}}\\!=\\!(u,v)$ is the pixel displacement in search window. We
set window size as 25$\times$25.

Displacement Calculation. In order to implicitly represent the motion without
optical flow ground truth as supervision, we dig into the information
represented by cost volume and calculate the displacement with the highest
matching cost. We use a soft-argmin operator by
$\widehat{{\rm\mathbf{u}}}=\sum_{{\rm\mathbf{u}}\in\mathcal{U}}[{\rm\mathbf{u}}\times\sigma({-\rm\mathbf{C{(u,x)}}})]$
to solve these problems. $\sigma$ denotes the softmax function. We use 2D
softmax along the displacement hypothesis space of ${\rm\mathbf{u}}$ to
calculate the matching probability. Therefore, $\widehat{\mathbf{u}}$ is a
two-channel displacement vector.

Uncertainty Estimation. The last two dimensions of the cost volume represent
the correspondence between $\mathcal{F}^{s}_{t}({\rm\mathbf{x}})$ and
$\mathcal{F}^{s}_{t-1}({\rm\mathbf{x}}+{\rm\mathbf{u}})$ in all spatial
positions. Previously, we build pixel-wise displacement between features of
adjacent frames by soft-argmin, but it may fail in low texture, large motion,
and motion blur areas. To remedy this issue, we propose an uncertainty branch
to measure the matching confidence. We use the matching cost value of the
correlation matrix in each spatial position as a score to measure the matching
uncertainty of each pair of spatial correspondence. Specifically, we use max-
pooling to calculate the max value of coordinate $(x,y)$ as matching
uncertainty, which means the highest response in each spatial position of 4D
cost volume. We define uncertainty map ${\rm
U_{map}}\in\mathbb{R}^{H^{\prime}\times W^{\prime}}$ as,

$\displaystyle{\rm
U_{map}}(x,y)=\mathop{\max}\limits_{\\{u,v\\}}{\mathbf{C}}((u,v),(x,y)).$ (2)

As shown in Fig. 3, we randomly select a pixel $(x,y)$ in query image
$\mathcal{I}_{t}$, the red box is the corresponding search window in reference
image $\mathcal{I}_{t-1}$, and yellow line represents the correspondence
between two adjacent frames. Right subfigure indicates the local matching cost
of the search window, which will be spliced into the total uncertainty map
${\rm U_{map}^{t}}$ of image $\mathcal{I}_{t}$ as Eq. (2).

Figure 3: Uncertainty map calculation.

Motion Feature Representation. After getting motion information from cost
volume by soft-argmin and max-pooling, we also need a high-level motion
feature to achieve feature fusion with high-level semantic feature on an
equivalent level. Different from many two-stream based VOS methods[30, 31]
that directly use a deep encoder parallel with RGB encoder to encode motion
feature, we design a lightweight CNN model to project the original motion
information ($H^{\prime}\times W^{\prime}\times 3$) into a high-dimensional
feature space ($H^{\prime}\times W^{\prime}\times D$). How to use the motion
feature to enhance the semantic feature will be described in Sec. 3.3. Table 1
shows the structure of our lightweight motion feature representation network
in our proposed MU-Layer, which maps the original motion information
($H^{\prime}\times W^{\prime}\times 3$) into a high-dimensional feature space
($H^{\prime}\times W^{\prime}\times D$).

Layer |  $C_{in}$, |  $C_{out}$, |  $kernel$, | $stride$
---|---|---|---|---
1 | 3, | 3, | 7, | 1
2 | 3, | 16, | 1, | 1
3 | 16, | 16, | 3, | 1
4 | 16, | 32, | 1, | 1
5 | 32, | 32, | 3, | 1
6 | 32, | 32, | 1, | 1
7 | 32, | 64, | 3, | 1
8 | 64, | 1024, | 1, | 1

Table 1: Structure of the motion feature representation network. We uses 2D
convolution for lightweight computing, instead of using 3D convolution.

###  3.3 Motion-aware Spatial Attention Module (MSAM)

To enhance the semantic feature from Enc-Q by motion feature provided by the
former MU-Layer, a direct and simple way is fusing the motion feature with
semantic feature by element-wise add operation, as shown in the right of Fig.
2(a) and can be formulated as
$\mathcal{F}^{out}=\mathcal{F}^{s}+\mathcal{F}^{m}$, where
$\mathcal{F}^{m},\mathcal{F}^{s}$ denotes the motion and semantic feature
respectively, $\mathcal{F}^{out}$ is the fused feature, which is subsequently
used to embed the key-value pair of query image.

Considering that the motion information is different in each spatial position,
to use it more efficiently, we design a lightweight attention module to fuse
the motion feature and semantic feature. In this way, the semantic feature
from Enc-Q can be enhanced by the motion feature in some important regions of
motion. Thus, we exploit motion feature as spatial attention weights, as shown
in Fig. 2(b), and this module can be formulated as,

$\displaystyle\mathcal{F}^{out}=\mathcal{F}^{s}\otimes{\rm sigmoid}({\rm
Conv_{1\times 1}}(\mathcal{F}^{m}))+\mathcal{F}^{s},$ (3)

where $\otimes$ indicates the broadcast multiply, the shape of
$\mathcal{F}^{m}$ is $H^{\prime}\times W^{\prime}\times D$ and the output
channel of ${\rm Conv_{1\times 1}}$ is $1$. So after ${\rm Conv_{1\times 1}}$
and ${\rm sigmoid}$, we can get one-channel attention map with shape
$H^{\prime}\times W^{\prime}\times 1$.

###  3.4 Loss function

Cross-Entropy (CE) is most widely used in segmentation tasks. However, the CE
loss calculates the error of each pixel independently and treats all pixels
equally, which ignores the global structure of the image. Here we adopt the
Bootstrap Cross-Entropy loss (BsCE, $\mathcal{L}_{bsce}$) [32] to force
networks to focus on the hard and valuable pixels during training, and we
select top $40\%$ hardest pixels to carry out back propagation. Besides, we
use the mask-IoU loss ($\mathcal{L}_{miou}$) to optimize the global structure
instead of focusing on a single independent pixel, which is not affected by
the unbalanced distribution. Thus, we use the combination of
$\mathcal{L}_{bsce}$ and $\mathcal{L}_{miou}$ as supervision, which is
formulated as,

$\displaystyle\begin{aligned}
\mathcal{L}{(\widehat{\mathcal{M}}_{t},\mathcal{M}_{t})}&=\mathcal{L}_{bsce}\\!+\\!\lambda\mathcal{L}_{miou}\\\
&=\frac{1}{\phi(\Omega)}\\!\sum_{p\in\phi(\Omega)}\\!((1\\!-\\!\mathcal{M}_{t}^{p})\log(1\\!-\\!\widehat{\mathcal{M}}_{t}^{p})\\!+\\!\mathcal{M}_{t}^{p}\log(\widehat{\mathcal{M}}_{t}^{p}))\\\
&\quad+\lambda\left[1-\frac{\sum_{p\in\Omega}\min(\mathcal{\mathcal{M}}_{t}^{p},\widehat{\mathcal{M}}_{t}^{p})}{\sum_{p\in\Omega}\max(\mathcal{M}_{t}^{p},\widehat{\mathcal{M}}_{t}^{p})}\right],\end{aligned}$
(4)

where $\lambda$ is a trade-off parameter and we set $\lambda=1$ in all
experiments. $\Omega$ is the set of all pixel in the mask, and $\phi(\Omega)$
is the hardest region used for bootstrap CE loss. $\widehat{\mathcal{M}}_{t}$
denotes the predicted object mask and $\mathcal{M}_{t}$ is the ground truth.
We demonstrate the advantages of this combination of loss function in Table 4.

###  3.5 Implementation Details

We implement our model by PyTorch [33] with a single NVIDIA RTX 2080Ti GPU. We
use ResNet50 [29] as the feature extractor (Enc-Q, Enc-R), pretrained on
ImageNet. During training, we select 6 continuous frames per sequence as a
batch (one as reference frame and the other five as query frames). During
inference, we feed the video sequence frame by frame and do not use online
fine-tuning. We simply apply common data augmentation on current frames
including flip, color jitter and affine transformation. The input frames are
randomly resized and cropped into 400 $\times$ 400, and we use the raw image
size during inference. We minimize $\mathcal{L}_{bsce}$ and
$\mathcal{L}_{miou}$ by the AdamW [34] optimizer with default parameters
$\beta_{1}=0.9,\beta_{2}=0.999$. The initial learning rate is $2\times
10^{-5}$ and the weight decay is $0.5$.

##  4 Experiments

###  4.1 Datasets, Evaluation metrics, and Protocols

We train and evaluate our method on DAVIS 2017 [35] and YouTube-VOS 2018 [36]
datasets. Considering that many methods use extra static image datasets for
pre-training [37, 38, 39, 40, 41] or conduct fine-tuning, for a fair
comparison, we categorize and compare solutions based on whether they use
extra static datasets and online fine-tuning.

DAVIS 2017. The DAVIS17 dataset contains 120 video sequences in total, where
60 sequences are split for training, 30 for validation, and 30 for testing.
Each video contains one or several annotated objects to track. Each video
sequence has 25 to 104 annotated continuous frames.

Youtube-VOS 2018. The Youtube-VOS18 dataset contains 4453 videos with one or
more target objects, including 3471 videos for training (65 categories), 474
sequences for validation (additional 26 unseen categories). Each video
sequence has 20 to 180 discontinuous frames, where every 5 interval frames are
provided and annotated.

Evaluation metrics. Following the standard DAVIS protocol, we measure region
accuracy $\mathcal{J}$ by calculating average intersection-over-union (IoU),
and boundary accuracy $\mathcal{F}$ via bipartite matching between boundary
pixels. In addition, we compare inference speed by frames per second (FPS)
according to averaging FPS of each sequence on the validation set.

Figure 4: Dataset usage protocols.

Evaluation protocols. There are various training protocols for the existing
VOS methods. For a fair comparison with more methods, we train our model and
report the results under different data use protocols, including (1) only
using DAVIS17 for training, (2) jointly training on DAVIS17 and YouTube-VOS18,
(3) using static images [37, 38, 39, 40, 41] to pretrain and then fine-tuning
on DAVIS17 (3-1) or both jointly (3-2), more intuitively in Fig. 4. The
different training settings may cause unfair comparisons, such as using
different backbones (_e.g_. RestNet50, ResNet101), using well-designed data
augmentation methods (_e.g_. Hide-and-Seek, Label Shuffling, Balanced Random-
Crop), using different weight initialization (_e.g_. Mask-RCNN, DeepLab) and
whether performing online fine-tune on the test video or not, _etc_. Here, we
will report the detailed comparisons as fair as possible.

It is worth mentioning that, this low-data experimental setup greatly reduces
the training time and no longer requires a large amount of data to pretrain.
Although this is a smart way to initialize the network and improve the
$\mathcal{J}\&\mathcal{F}$ metric under protocol(3), researchers gradually
realize the shortcomings of this way, such as long training time. In our
setting, one epoch of pretraining under protocol(3) needs about 17 hours, and
the whole pretraining process may take 6$\sim$7 days in a single 2080Ti GPU.
The time of one epoch under protocol(2) is about 25 minutes and protocol(1) is
about 12 minutes. The training protocol(1) and (2) are lighter, _i.e_. less
time. We believe abandoning the pretraining phase by emphasizing own data
motion information is an improvement in the VOS field.

###  4.2 Quantitative Comparison

DAVIS17. Results on the DAVIS17 validation set are reported in Table 1. Our
method achieves 1st under training protocol(1) and protocol(3-1), and ranks
2nd under protocol(2). Under protocol(1), only using the DAVIS17 dataset for
training, our vanilla version achieves $\mathbf{75.0\%}$ on
$\mathcal{J}\&\mathcal{F}$, which outperforms all other methods. And a better
initialization by Mask-RCNN ResNet50 can boost the performance of our method
to $\mathbf{76.5\%}$ on $\mathcal{J}\&\mathcal{F}$, which significantly
outperforms STM($43.0\%$) by $36.5\%$ and CFBI($74.9\%$) by $1.4\%$. In
addition, when jointly training under protocol(2), ours achieves
$\mathbf{81.1\%}\ \mathcal{J}\&\mathcal{F}$, and the performance can increase
to $\mathbf{81.9\%}$ if using static images to pretrain. Ours surpasses most
competitors in Table 1, it is competitive and able to prove our superiority.

Methods | S | Y | $\bm{\mathcal{J}}$ | $\bm{\mathcal{F}}$ | $\bm{\mathcal{J}$\&$\mathcal{F}}$ | FPS
---|---|---|---|---|---|---
Protocol (1) | STM111In Table 1,1, “S”: static images for training, “Y”: Youtube-VOS18, and “O”: fine-tune on test strategy. † indicates using DeepLabv3-ResNet101 to initialize the backbone network, and ‡ means using Mask-RCNN-ResNet50. The best result is bold-faced, and the suboptimal result is underlined.  [4] |  |  | - | - | 43.0 | 6.25
OSMN [42] |  |  | 52.5 | 57.1 | 54.8 | -
OnAVOS [43] |  |  | 64.5 | 71.2 | 67.9 | 0.08
FRTM[3] |  |  | - | - | 68.8 | 21.9
FEELVOS[44] |  |  | 65.9 | 72.3 | 69.1 | 2.22
LWLVOS‡[45] |  |  | 72.2 | 76.3 | 74.3 | -
CFBI† [2] |  |  | 72.1 | 77.7 | 74.9 | 5.55
Ours |  |  | 72.4 | 77.8 | 75.0 | 6.42
| Ours-v2‡ |  |  | 74.5 | 78.5 | 76.5 | 6.42
Protocol (2) | A-GAME[46] |  | ✓ | 67.2 | 72.7 | 70.0 | 14.3
FEELVOS[44] |  | ✓ | 69.1 | 74.0 | 71.5 | 2.22
STM-cycle[11] |  | ✓ | 69.3 | 75.3 | 72.3 | 9.3
AFB-URR∗[1] |  | ✓ | 72.0 | 75.7 | 73.9 | -
PMVOS[47] |  | ✓ | 71.2 | 76.7 | 74.0 | -
FRTM[3] |  | ✓ | - | - | 76.7 | 21.9
CFBI† [2] |  | ✓ | 79.1 | 84.6 | 81.9 | 5.55
| Ours |  | ✓ | 78.3 | 83.9 | 81.1 | 6.42
Protocol (3-1) | RANet[27] | ✓ |  | 63.2 | 68.2 | 65.7 | 30.3
RGMP[9] | ✓ |  | 64.8 | 68.6 | 66.7 | 7.70
OSVOSS [48] | ✓ |  | 64.7 | 71.3 | 68.0 | 0.22
CINM[49] | ✓ |  | 67.2 | 74.2 | 70.7 | -
GC[50] | ✓ |  | 69.3 | 73.5 | 71.4 | -
STM[4] | ✓ |  | 69.2 | 74.0 | 71.6 | 6.25
AFB-URR[1] | ✓ |  | 73.0 | 76.1 | 74.6 | 6.18
RMNet[28] | ✓ |  | 72.8 | 77.2 | 75.0 | -
LCM[51] | ✓ |  | 73.1 | 77.2 | 75.2 | -
PReMVOS[52] | ✓ |  | 73.9 | 81.7 | 77.8 | 0.03
KMN[13] | ✓ |  | 74.2 | 77.8 | 76.0 | 8.33
| Ours | ✓ |  | 74.7 | 81.4 | 78.1 | 6.42
(3-2) | STM[4] | ✓ | ✓ | 79.2 | 84.3 | 81.8 | 6.25
GMVOS[12] | ✓ | ✓ | 80.2 | 85.2 | 82.8 | 5.00
KMN[13] | ✓ | ✓ | 80.0 | 85.6 | 82.8 | 8.33
RMNet[28] | ✓ | ✓ | 81.0 | 86.0 | 83.5 | -
LCM[51] | ✓ | ✓ | 80.5 | 86.5 | 83.5 | -
| Ours | ✓ | ✓ | 79.2 | 84.6 | 81.9 | 6.42

Table 2: Comparison on the DAVIS17 validation set.111In Table 1,1, “S”: static
images for training, “Y”: Youtube-VOS18, and “O”: fine-tune on test strategy.
† indicates using DeepLabv3-ResNet101 to initialize the backbone network, and
‡ means using Mask-RCNN-ResNet50. The best result is bold-faced, and the
suboptimal result is underlined.

YouTube-VOS18. We report the results on the YouTube-VOS18 validation set in
Table 1. The subscript $\mathcal{U}$ and $\mathcal{S}$ denote the unseen and
seen categories, $\mathcal{G}$ is the average of all four measures. Our method
with different training settings can achieve competitive results. Compared
with the baseline STM[4], the motion information brings $0.9\%$
($79.4\%$$\rightarrow$$80.3\%$) performance gain. Especially without
pretraining on static images, our mehtod brings $9.2\%$
($68.2\%$$\rightarrow$$77.4\%$) gain. In addition, we found the improvement on
YouTube is not as significant as DAVIS. The reason is that DAVIS consists of
continuous frames, while every 5 interval frames (discontinuous) are used in
YouTube. MULayer cannot effectively capture the long range motion information
without the optical flow ground truth supervision.

Methods | S | O | $\bm{\mathcal{J_{U}}}$ | $\bm{\mathcal{F_{U}}}$ | $\bm{\mathcal{J_{S}}}$ | $\bm{\mathcal{F_{S}}}$ | $\bm{\mathcal{G}}$
---|---|---|---|---|---|---|---
S2S[36] |  | ✓ | 55.5 | 61.2 | 71.0 | 70.0 | 64.4
PReMVOS[52] |  | ✓ | 56.6 | 63.7 | 71.4 | 75.9 | 66.9
STM-cycle[11] |  | ✓ | 62.8 | 71.9 | 72.2 | 76.3 | 70.8
MSK[8] | ✓ | ✓ | 45.0 | 47.9 | 59.9 | 59.5 | 53.1
OnAVOS [43] | ✓ | ✓ | 46.6 | 51.4 | 60.1 | 62.7 | 55.2
DMM-Net[53] | ✓ | ✓ | 50.6 | 57.4 | 60.3 | 50.6 | 58.0
RGMP[9] | ✓ |  | - | - | 59.5 | 45.2 | 53.8
OSVOS [54] | ✓ |  | 54.2 | 60.7 | 59.8 | 60.5 | 58.8
GC[50] | ✓ |  | 68.9 | 75.7 | 72.6 | 75.6 | 73.2
AFB-URR[1] | ✓ |  | 74.1 | 82.6 | 78.8 | 83.1 | 79.6
GMVOS[12] | ✓ |  | 74.0 | 80.9 | 80.7 | 85.1 | 80.2
LWLVOS‡[45] | ✓ |  | 76.4 | 84.4 | 80.4 | 84.9 | 81.5
KMN[13] | ✓ |  | 75.3 | 83.3 | 81.4 | 85.6 | 81.4
LCM[51] | ✓ |  | 75.7 | 83.4 | 82.2 | 86.7 | 82.0
STM[4] | ✓ |  | 72.8 | 80.9 | 79.7 | 84.2 | 79.4
Ours | ✓ |  | 75.1 | 83.4 | 79.0 | 83.5 | 80.3
A-GAME[46] |  |  | 60.8 | 66.2 | 67.8 | 69.5 | 66.1
FRTM[3] |  |  | 76.2 | 74.1 | 72.3 | 76.2 | 72.1
LWLVOS‡[45] |  |  | 75.6 | 84.4 | 78.3 | 82.3 | 80.2
CFBI† [2] |  |  | 75.3 | 83.4 | 81.1 | 85.8 | 81.4
RMNet[28] |  |  | 75.7 | 82.4 | 82.1 | 85.7 | 81.5
STM[4] |  |  | - | - | - | - | 68.2
Ours |  |  | 70.6 | 77.9 | 78.5 | 82.7 | 77.4

Table 3: Comparison on the YouTube-VOS18 validation set.11footnotemark: 1

###  4.3 Ablation Study

In this section, we conduct several ablation experiments on the DAVIS17
validation set via training protocol(2) in Fig. 4 to discuss the effectiveness
of our proposed modules. The baseline version of these experiments uses
ResNet50, without any proposed modules.

MU-Layer. We train a network without our MU-layer to study how it influences
the matching based methods. As shown in Table 4 (a) and (c), our proposed MU-
Layer can achieve $1.5\%$ ($76.5\%\to 78.0\%$) performance gain. We also
visualize the displacement and uncertainty map in Fig. 5 and Fig. 6, which
shows that our MU-Layer extracts reliable motion information.

Figure 5: Visualization of the displacement and uncertainty map. We project
the uncertainty map into a heat map and add it to the original image for
better visualization. Figure 6: Visualization of the uncertainty map of ours
on the DAVIS17 validation set. We project the uncertainty map into a heat map
and add it to the original image for better visualization. We select one frame
after every $1/4$ sequence length for visualization (frame-2 replace $0\%$).
It can be verified that the moving regions in the adjacent images are
activated with high uncertainty.

MASM. To evaluate the effectiveness of our fusion module, we report the result
of addition (f) and MASM (g) in Table 4, based on the complete structure (e).
The comparison shows that MASM improves the vanilla adding based fusion method
by $1.0\%$ ($80.1\%\to 81.1\%$) in $\mathcal{J}$&$\mathcal{F}$. We visualize
the spatial attention map of shape $H^{\prime}\times W^{\prime}\times 1$
before broadcast multiply and show it in Fig. 7. We can observe that the
attention map focuses on the salient area of the moving objects, which
demonstrates that MASM helps strengthen the object information.

Figure 7: Visualization of the attention map. We directly use the grayscale
image to display the one-channel attention map.

Segmentation Loss. We study how well-designed segmentation loss affects the
performance. The results of (a) and (b) are listed in Table 4, and the
performance drops with or without such loss. This provides us a strong
baseline and achieves better performance.

| Baseline and components | $\mathcal{J}$ | $\mathcal{F}$ |  $\mathcal{J}$&$\mathcal{F}$ | $\Delta$
---|---|---|---|---|---
(a) | w/o disp. (baseline) | 74.5 | 78.4 | 76.5 | -
(b) | \+ BsCE&IoU loss | 76.2 | 80.9 | 78.6 | +2.1
(c) | \+ disp. + uncertainty map | 75.9 | 80.1 | 78.0 | +1.5
(d) | \+ disp. + BsCE&IoU | 76.9 | 82.5 | 79.7 | +3.2
(e) | \+ disp. + BsCE&IoU + uncertainty | 78.3 | 83.9 | 81.1 | +4.6
(f) | All three cmpt. w [addition] | 77.9 | 82.3 | 80.1 | +3.6
(g) | All three cmpt. w [motion attention] | 78.3 | 83.9 | 81.1 | +4.6

Table 4: Ablation study of components. “disp”: displacement, “BsCE&IoU”: using
$\mathcal{L}_{bsce}\&\mathcal{L}_{miou}$ to supervise, “[addition]” and
“[motion attention]” is the fusion method.

###  4.4 Some Failure Cases

Here we provide some failure cases of our scheme in Fig. 8. After the previous
quantitative and qualitative comparisons, our solution has achieved great
success by exploiting the effective motion information. As common optical flow
networks cannot handle extremely complex/fast motions and large-scale
occlusion well, and there is no ground truth for supervision in our implicit
modeling method, we also have flaws in some extreme examples. However, our
method still outperforms other competing methods under these challenging
scenarios.

Figure 8: Some failure cases of ours. The left is the IoU per-frame over time.
From top to bottom on the right are the uncertainty map, the predicted masks,
and the ground truth. Figure 9: IoU per-frame over time of Ours, STM and AFB-
URR on five video sequences from DAVIS17 validation set. The last three
columns have multiple objects, while the first two columns have only a single
object. Since we effectively use the motion information between adjacent
frames, the IoU can remain high even in the latter part of the video
sequences. Figure 10: Visualization of the quantitative results of ours on
DAVIS17 validation set. We select one frame every $1/4$ sequence length for
visualization (frame-2 replace $0\%$).  Figure 11: Visualization of the
quantitative results of ours and AFB-URR on the YouTube-VOS18 validation set.

###  4.5 Qualitative Comparison

We give a qualitative comparison with some SOTA methods [1, 2, 3, 4] in Fig.
1. In soapbox#74 and scooter-black#42, our method can handle the boundaries
between objects well. In paragliding-launch#20, our method deals with moving
thin lines better. However, FRTM[3] lose parts of objects or over-cover the
thin object. AFB-URR[1] struggles with discrimination between different
objects and almost fails to detect small and thin objects.

In Fig. 9, we show how IoU changes over time by per-frame evaluation. Because
the motion information we used exists between any adjacent frames and will not
disappear over time, our methods can still maintain high IoU in the last 50%
frames. Compared with STM and AFB-URR, we have achieved more robust
segmentation. More qualitative results of ours are shown in Fig. 10. Thanks to
the accurate modeling of motion information, our method is robust to
occlusion, complex/large motion of row#1,2,4 and can distinguish the
small/thin objects in row#3. And in Fig. 11, we select 3 video sequences of
YouTube-VOS18 for visual comparison with AFB-URR[1].

##  5 Conclusion

In this work, we advocated the return of motion information in the state-of-
the-art dense-matching based semi-supervised VOS approaches. We proposed a
novel motion uncertainty-aware pipeline for semi-supervised VOS, where the
motion information is implicitly modeled. We implicitly built correlation
volume by matching pixel-pairs between the reference frame and the query
frame, enabling the learning of motion features. To address the challenging
cases of occlusion and textureless regions, we incorporated the motion
uncertainty into building dense correspondences. Furthermore, we proposed a
motion-enhanced module to effectively fuse the motion feature and the semantic
feature. Extensive experiments on benchmark datasets proved the superiority of
our proposed framework.

## Acknowledgements

This research was supported in part by the National Key Research and
Development Program of China under Grant 2018AAA0102803 and the National
Natural Science Foundation of China under Grants 61871325, 62001394 and
61901387.

## References

  * [1] Y. Liang, X. Li, N. Jafari, Q. Chen, Video object segmentation with adaptive feature bank and uncertain-region refinement, in: Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2020.
  * [2] Z. Yang, Y. Wei, Y. Yang, Collaborative video object segmentation by foreground-background integration, in: Proceedings of the European Conference on Computer Vision (ECCV), 2020.
  * [3] A. Robinson, F. J. Lawin, M. Danelljan, F. S. Khan, M. Felsberg, Learning fast and robust target models for video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [4] S. W. Oh, J.-Y. Lee, N. Xu, S. J. Kim, Video object segmentation using space-time memory networks, in: Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019, pp. 9226–9235.
  * [5] Y. Yin, D. Xu, X. Wang, L. Zhang, Agunet: Annotation-guided u-net for fast one-shot video object segmentation, Pattern Recognition 110 (2021) 107580.
  * [6] M. Sun, J. Xiao, E. G. Lim, Y. Xie, J. Feng, Adaptive roi generation for video object segmentation using reinforcement learning, Pattern Recognition 106 (2020) 107465.
  * [7] Z. Zhao, S. Zhao, J. Shen, Real-time and light-weighted unsupervised video object segmentation network, Pattern Recognition (2021) 108120.
  * [8] F. Perazzi, A. Khoreva, R. Benenson, B. Schiele, A.Sorkine-Hornung, Learning video object segmentation from static images, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [9] S. W. Oh, J.-Y. Lee, K. Sunkavalli, S. J. Kim, Fast video object segmentation by reference-guided mask propagation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 7376–7385.
  * [10] X. Li, Y. Qi, Z. Wang, K. Chen, Z. Liu, J. Shi, P. Luo, X. Tang, C. C. Loy, Video object segmentation with re-identification, in: The 2017 DAVIS Challenge on Video Object Segmentation - CVPR Workshops, 2017.
  * [11] Y. Li, N. Xu, P. Jinlong, J. See, L. Weiyao, Delving into the cyclic mechanism in semi-supervised video object segmentation, in: Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2020.
  * [12] X. Lu, W. Wang, D. Martin, T. Zhou, J. Shen, V. G. Luc, Video object segmentation with episodic graph memory networks, in: Proceedings of the European Conference on Computer Vision (ECCV), 2020.
  * [13] H. Seong, J. Hyun, E. Kim, Kernelized memory network for video object segmentation, in: Proceedings of the European Conference on Computer Vision (ECCV), 2020, pp. 629–645.
  * [14] Y. Li, Z. Shen, Y. Shan, Fast video object segmentation using the global context module, in: Proceedings of the European Conference on Computer Vision (ECCV), Springer, 2020, pp. 735–750.
  * [15] J. Cheng, Y.-H. Tsai, S. Wang, M.-H. Yang, Segflow: Joint learning for video object segmentation and optical flow, in: Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017, pp. 686–695.
  * [16] W.-D. Jang, C.-S. Kim, Online video object segmentation via convolutional trident network, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 5849–5858.
  * [17] A. Dave, P. Tokmakov, D. Ramanan, Towards segmenting anything that moves, in: Proceedings of the IEEE International Conference on Computer Vision Workshops (ICCVW), 2019.
  * [18] A. Khoreva, R. Benenson, E. Ilg, T. Brox, B. Schiele, Lucid data dreaming for object tracking, in: The 2017 DAVIS Challenge on Video Object Segmentation - CVPR Workshops, 2017.
  * [19] Y. Tian, G. Cheng, J. Gelernter, S. Yu, C. Song, B. Yang, Joint temporal context exploitation and active learning for video segmentation, Pattern Recognition 100 (2020) 107158.
  * [20] E. Ilg, N. Mayer, T. Saikia, M. Keuper, A. Dosovitskiy, T. Brox, Flownet 2.0: Evolution of optical flow estimation with deep networks, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 2462–2470.
  * [21] T.-W. Hui, X. Tang, C. C. Loy, Liteflownet: A lightweight convolutional neural network for optical flow estimation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 8981–8989.
  * [22] J. Revaud, P. Weinzaepfel, Z. Harchaoui, C. Schmid, Epicflow: Edge-preserving interpolation of correspondences for optical flow, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 1164–1172.
  * [23] Y. Hu, R. Song, Y. Li, Efficient coarse-to-fine patchmatch for large displacement optical flow, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 5704–5712.
  * [24] T. Kroeger, R. Timofte, D. Dai, L. Van Gool, Fast optical flow using dense inverse search, in: Proceedings of the European Conference on Computer Vision (ECCV), Springer, 2016, pp. 471–488.
  * [25] J. Wang, Y. Zhong, Y. Dai, K. Zhang, P. Ji, H. Li, Displacement-invariant matching cost learning for accurate optical flow estimation, arXiv preprint arXiv:2010.14851 (2020).
  * [26] Z. Teed, J. Deng, Raft: Recurrent all-pairs field transforms for optical flow, in: Proceedings of the European Conference on Computer Vision (ECCV), Springer, 2020, pp. 402–419.
  * [27] Z. Wang, J. Xu, L. Liu, F. Zhu, L. Shao, Ranet: Ranking attention network for fast video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 3977–3986.
  * [28] H. Xie, H. Yao, S. Zhou, S. Zhang, W. Sun, Efficient regional memory network for video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 1286–1295.
  * [29] K. He, X. Zhang, S. Ren, J. Sun, Deep residual learning for image recognition, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 770–778.
  * [30] H. Li, G. Chen, G. Li, Y. Yu, Motion guided attention for video salient object detection, in: Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019, pp. 7274–7283.
  * [31] T. Zhou, J. Li, S. Wang, R. Tao, J. Shen, Matnet: Motion-attentive transition network for zero-shot video object segmentation, IEEE Transactions on Image Processing (TIP) 29 (2020) 8326–8338.
  * [32] Z. Wu, C. Shen, A. v. d. Hengel, Bridging category-level and instance-level semantic image segmentation, arXiv preprint arXiv:1605.06885 (2016).
  * [33] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al., Pytorch: An imperative style, high-performance deep learning library, in: Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 8026–8037.
  * [34] I. Loshchilov, F. Hutter, Decoupled weight decay regularization, in: Proceedings of the The International Conference on Learning Representations (ICLR), 2019.
  * [35] J. Pont-Tuset, F. Perazzi, S. Caelles, P. Arbeláez, A. Sorkine-Hornung, L. Van Gool, The 2017 davis challenge on video object segmentation, arXiv preprint arXiv:1704.00675 (2017).
  * [36] N. Xu, L. Yang, Y. Fan, J. Yang, D. Yue, Y. Liang, B. Price, S. Cohen, T. Huang, Youtube-vos: Sequence-to-sequence video object segmentation, in: Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 585–601.
  * [37] M.-M. Cheng, N. J. Mitra, X. Huang, P. H. S. Torr, S.-M. Hu, Global contrast based salient region detection, IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI) 37 (3) (2015) 569–582.
  * [38] M. Everingham, L. Van Gool, C. K. Williams, J. Winn, A. Zisserman, The pascal visual object classes (voc) challenge, International Journal of Computer Vision (IJCV) 88 (2) (2010) 303–338.
  * [39] J. Shi, Q. Yan, L. Xu, J. Jia, Hierarchical image saliency detection on extended cssd, IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI) 38 (4) (2015) 717–729.
  * [40] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, C. L. Zitnick, Microsoft coco: Common objects in context, in: Proceedings of the European Conference on Computer Vision (ECCV), Springer, 2014, pp. 740–755.
  * [41] Y. Li, X. Hou, C. Koch, J. M. Rehg, A. L. Yuille, The secrets of salient object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014, pp. 280–287.
  * [42] L. Yang, Y. Wang, X. Xiong, J. Yang, A. K. Katsaggelos, Efficient video object segmentation via network modulation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 6499–6507.
  * [43] P. Voigtlaender, B. Leibe, Online adaptation of convolutional neural networks for video object segmentation, in: Proceedings of the British Machine Vision Conference (BMVC), 2017.
  * [44] P. Voigtlaender, Y. Chai, F. Schroff, H. Adam, B. Leibe, L.-C. Chen, Feelvos: Fast end-to-end embedding learning for video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 9481–9490.
  * [45] G. Bhat, F. J. Lawin, M. Danelljan, A. Robinson, M. Felsberg, L. Van Gool, R. Timofte, Learning what to learn for video object segmentation, in: Proceedings of the European Conference on Computer Vision (ECCV), 2020, pp. 777–794.
  * [46] J. Johnander, M. Danelljan, E. Brissman, F. S. Khan, M. Felsberg, A generative appearance model for end-to-end video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [47] S. Cho, H. Lee, S. Woo, S. Jang, S. Lee, Pmvos: Pixel-level matching-based video object segmentation, arXiv preprint arXiv:2009.08855 (2020).
  * [48] K.-K. Maninis, S. Caelles, Y. Chen, J. Pont-Tuset, L. Leal-Taixé, D. Cremers, L. Van Gool, Video object segmentation without temporal information, IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI) 41 (6) (2018) 1515–1530.
  * [49] L. Bao, B. Wu, W. Liu, Cnn in mrf: Video object segmentation via inference in a cnn-based higher-order spatio-temporal mrf, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 5977–5986.
  * [50] Y. Li, Z. Shen, Y. Shan, Fast video object segmentation using the global context module, in: Proceedings of the European Conference on Computer Vision (ECCV), Springer, 2020, pp. 735–750.
  * [51] L. Hu, P. Zhang, B. Zhang, P. Pan, Y. Xu, R. Jin, Learning position and target consistency for memory-based video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 4144–4154.
  * [52] J. Luiten, P. Voigtlaender, B. Leibe, Premvos: Proposal-generation, refinement and merging for video object segmentation, in: Proceedings of the Asian Conference on Computer Vision (ACCV), Springer, 2018, pp. 565–580.
  * [53] X. Zeng, R. Liao, L. Gu, Y. Xiong, S. Fidler, R. Urtasun, Dmm-net: Differentiable mask-matching network for video object segmentation, in: Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019, pp. 3929–3938.
  * [54] S. Caelles, K.-K. Maninis, J. Pont-Tuset, L. Leal-Taixé, D. Cremers, L. Van Gool, One-shot video object segmentation, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 221–230.