# Sets of lines passing through one point each of three sets of points

H. A. Hakopian

_Department of Informatics and Applied Mathematics,_
_Yerevan State University,_
_Institute of Mathematics of NAS RA_

# On a result concerning algebraic curves passing
through $n$-independent nodes

H. A. Hakopian

_Department of Informatics and Applied Mathematics,_
_Yerevan State University,_
_Institute of Mathematics of NAS RA_

###### Abstract

Let a set of nodes $\mathcal{X}$ in the plane be $n$-independent, i.e., each
node has a fundamental polynomial of degree $n.$ Assume that
$\\#\mathcal{X}=d(n,n-3)+3=(n+1)+n+\cdots+5+3.$ In this paper we prove that
there are at most three linearly independent curves of degree less than or
equal to $n-1$ that pass through all the nodes of $\mathcal{X}.$ We provide a
characterization of the case when there are exactly three such curves. Namely,
we prove that then the set $\mathcal{X}$ has a very special construction:
either all its nodes belong to a curve of degree $n-2,$ or all its nodes but
three belong to a (maximal) curve of degree $n-3.$

This result complements a result established recently by H. Kloyan, D.
Voskanyan, and H. H. Note that the proofs of the two results are completely
different. MSC2010: 41A05, 41A63, 14H50.

Keywords: algebraic curve, maximal curve, fundamental polynomial,
$n$-independent nodes.

##  1 Introduction

Denote the space of all bivariate polynomials of total degree $\leq n$ by

$\Pi_{n}=\left\\{\sum_{i+j\leq n}a_{ij}x^{i}y^{j}\right\\}.$

We have that $N:=N_{n}:=\dim\Pi_{n}=(1/2)(n+1)(n+2).$

Denote by $\Pi$ the space of all bivariate polynomials.

A _plane algebraic curve_ is the zero set of some bivariate polynomial of
degree $\geq 1.$ To simplify notation, we shall use the same letter, say $p$,
to denote the polynomial $p\in\Pi$ and the curve given by the equation
$p(x,y)=0$. In particular, by $\ell$ we denote a linear polynomial from
$\Pi_{1}$ and the line defined by the equation $\ell(x,y)=0.$

Consider a set of $s$ distinct nodes
${\mathcal{X}}={\mathcal{X}}_{s}=\\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{s},y_{s})\\}.$
The problem of finding a polynomial $p\in\Pi_{n},$ which satisfies the
conditions

$p(x_{i},y_{i})=c_{i},\quad i=1,\ldots,s,$ (1)

is called interpolation problem.

Denote by $p\big{|}_{\mathcal{X}}$ the restriction of $p\in\Pi$ on
$\mathcal{X}.$

A polynomial $p\in\Pi_{n}$ is called a fundamental polynomial for a node
$A\in{\mathcal{X}}$ if $p(A)=1\ \ \text{and}\ \
p\big{|}_{{\mathcal{X}}\setminus\\{A\\}}=0.$

We denote this $n$-fundamental polynomial by
$p_{A}^{\star}:=p_{A,\mathcal{X}}^{\star}.$

######  Definition 1.1.

The interpolation problem with a set of nodes ${\mathcal{X}}_{s}$ is called
$n$-poised if for any data $(c_{1},\ldots,c_{s})$ there is a unique polynomial
$p\in\Pi_{n}$ satisfying the interpolation conditions (1).

A necessary condition of poisedness is $\\#{\mathcal{X}}_{s}=s=N.$

Now, let us consider the concept of $n$-independence (see [1, 3]).

######  Definition 1.2.

A set of nodes ${\mathcal{X}}_{s}$ is called $n$-independent, if all its nodes
have $n$-fundamental polynomials. Otherwise, it is called $n$-dependent.

Fundamental polynomials are linearly independent. Therefore a necessary
condition of $n$-independence for ${\mathcal{X}}_{s}$ is $s\leq N$.

In this paper we consider $n$-independence more generally. Namely, we admit
possibility to include in the $n$-independent set ${\mathcal{X}}_{s}$ a
_directional derivative node_ , denoted by $A^{(k)}.$ We have that
$p(A^{(k)}):=D_{\bf a}^{k}p(A),$ where $p\in\Pi,\ {\bf a}$ is a direction, and
$k\in\mathbb{N}.$ For a node $A^{(k)}$ we assume in addition that

$p\in\Pi_{n},\ p|_{\mathcal{X}}=0\implies D_{\bf a}^{i}p(A)=0,\
i=0,\ldots,k-1.$

The set $\mathcal{X}\cup\\{A^{(k)}\\}$ is $n$-independent means that
$\mathcal{X}$ is $n$-independent and the node $A^{(k)}$ has an $n$-fundamental
polynomial $p=p^{\star}_{A^{(k)}}:$

$p\in\Pi_{n},\ p|_{\mathcal{X}}=0,\ D_{\bf a}^{k}p(A)=1.$

We say that a node $A^{(k)}$ belongs to a curve $q$ if $D_{\bf a}^{i}p(A)=0,\
i=0,\ldots,k.$ In particular $A^{(k)}$ belongs to a line $\ell$ if $A\in\ell$
and ${\bf a}$ is the direction vector of $\ell.$

Let us mention, as it can be readily verified, that all the results we present
below concerning $n$-independent sets hold true for the above mentioned
generalization.

###  1.1 Some properties of $n$-independent nodes

Let us start with the following

######  Lemma 1.3 (Lemma 2.2, [6]).

Suppose that a set of nodes $\mathcal{X}$ is $n$-independent and a node
$A\notin\mathcal{X}$ has an $n$-fundamental polynomial with respect to the set
$\mathcal{X}\cup\\{A\\}.$ Then the latter set is $n$-independent too.

Denote the distance between the points $A$ and $B$ by $\rho(A,B).$ Let us
recall the following (see Rem. 1.14, [2])

######  Lemma 1.4.

Suppose that ${\mathcal{X}}_{s}=\\{A_{i}\\}_{i=1}^{s}$ is an $n$-independent
set. Then there is a number $\epsilon>0$ such that any set
${\mathcal{X}}_{s}^{\prime}=\\{A_{i}^{\prime}\\}_{i=1}^{s},$ with the property
that $\rho(A_{i},A_{i}^{\prime})<\epsilon,\ i=1,\ldots,s,$ is $n$-independent
too.

Next result concerns the extensions of $n$-independent sets.

######  Lemma 1.5 (Lemma 2.1, [3]).

Any $n$-independent set ${\mathcal{X}}$ with $\\#{\mathcal{X}}<N$ can be
enlarged to an $n$-poised set.

Denote the linear space of polynomials of total degree at most $n$ vanishing
on ${\mathcal{X}}$ by

${{\mathcal{P}}}_{n,{\mathcal{X}}}=\left\\{p\in\Pi_{n}:p\big{|}_{\mathcal{X}}=0\right\\}.$

The following two propositions are well-known (see, e.g., [3]).

######  Proposition 1.6.

For any node set ${\mathcal{X}}$ we have that

$\dim{{\mathcal{P}}}_{n,{\mathcal{X}}}=N-\\#{\mathcal{Y}},$

where ${\mathcal{Y}}$ is a maximal $n$-independent subset of ${\mathcal{X}}.$

######  Proposition 1.7.

If a polynomial $p\in\Pi_{n}$ vanishes at $n+1$ points of a line $\ell$, then
we have that $p=\ell r,$ where $r\in\Pi_{n-1}.$

In the sequel we will need the following

######  Proposition 1.8 (Prop. 1.10, [6]).

Let $\mathcal{X}$ be a set of nodes. Then the following two conditions are
equivalent:

i) ${{\mathcal{P}}}_{n,{\mathcal{X}}}=\\{0\\};$

ii) The node set $\mathcal{X}$ has an $n$-poised subset.

Set $d(n,k):=N_{n}-N_{n-k}=(1/2)k(2n+3-k).$ The following is a generalization
of Proposition 1.7.

######  Proposition 1.9 (Prop. 3.1, [8]).

Let $q$ be an algebraic curve of degree $k\leq n$ without multiple components.
Then the following hold:

$i)$ any subset of $q$ containing more than $d(n,k)$ nodes is $n$-dependent;

$ii)$ any subset ${\mathcal{X}}$ of $q$ containing exactly $d=d(n,k)$ nodes is
$n$-independent if and only if the following condition holds:

$p\in{\Pi_{n}}\quad\text{and}\quad p|_{\mathcal{X}}=0\Longrightarrow p=qr,\
\hbox{where}\ r\in\Pi_{n-k}.$ (2)

Thus, according to Proposition 1.9, $i)$, at most $d(n,k)$ nodes of
$\mathcal{X}$ can lie in a curve $q$ of degree $k\leq n$. This motivates the
following

######  Definition 1.10 (Def. 3.1, [8]).

Given an $n$-independent set of nodes $\mathcal{X}_{s}$ with $s\geq d(n,k).$ A
curve of degree $k\leq n$ passing through $d(n,k)$ points of $\mathcal{X}_{s}$
is called maximal.

We say that a node $A$ of an $n$-poised set ${\mathcal{X}}$ _uses_ a curve
$q\in\Pi_{k},$ if the latter divides the $n$-fundamental polynomial of $A,$
i.e., $p^{\star}_{A}=qr,\ r\in\Pi_{n-k}.$

Let us bring a characterization of maximal curves:

######  Proposition 1.11 (Prop. 3.3, [8]).

Let a node set ${\mathcal{X}}$ be $n$-independent. Then a curve $\mu$ of
degree $k,\ k\leq n,$ is a maximal curve if and only if

$p\in\Pi_{n},\ p|_{\mathcal{X}\cap\mu}=0\implies p=\mu q,\ q\in\Pi_{n-k}.$

Next result concerns maximal independent sets in curves.

######  Proposition 1.12 (Prop. 3.5, [7]).

Assume that $\sigma$ is an algebraic curve of degree $k$ without multiple
components and ${\mathcal{X}}_{s}\subset\sigma$ is any $n$-independent node
set of cardinality $s,\ s<d(n,k).$ Then the set ${\mathcal{X}}_{s}$ can be
extended to a maximal $n$-independent set ${\mathcal{X}}_{d}\subset\sigma$ of
cardinality $d=d(n,k)$.

Next result from Algebraic Geometry will be used in the sequel:

######  Theorem 1.13 (Th. 2.2, [9]).

If $\mathcal{C}$ is a curve of degree $n$ with no multiple components, then
through any point $O$ not in $\mathcal{C}$ there pass lines which intersect
$\mathcal{C}$ in $n$ distinct points.

Let us mention that, as it follows from the proof, if a line $\ell$ through
the point $O$ intersects $\mathcal{C}$ in $n$ distinct points then any line
through $O,$ sufficiently close to $\ell,$ has the same property.

Finally, let us present a well-known

######  Lemma 1.14.

Given $m$ linearly independent polynomials, $m\geq 2.$ Then for any point $A$
there are $m-1$ linearly independent polynomials, in their linear span,
vanishing at $A.$

##  2 A result and its complement

In this paper we complement the following

######  Theorem 2.1 (Thm. 2.5, [5]).

Assume that ${\mathcal{X}}$ is an $n$-independent set of $d(n,k-2)+3$ nodes
with $3\leq k\leq n-2.$ Then at most three linearly independent curves of
degree $\leq k$ may pass through all the nodes of ${\mathcal{X}}.$ Moreover,
there are such three curves for the set ${\mathcal{X}}$ if and only if all the
nodes of ${\mathcal{X}}$ lie in a curve of degree $k-1,$ or all the nodes of
${\mathcal{X}}$ but three lie in a (maximal) curve of degree $k-2.$

Namely, we prove that the above result is true also in the case $k=n-1:$

######  Proposition 2.2.

Assume that ${\mathcal{X}}$ is an $n$-independent set of $d(n,n-3)+3$ nodes,
$n\geq 4.$ Then at most three linearly independent curves of degree $\leq n-1$
may pass through all the nodes of ${\mathcal{X}}.$ Moreover, there are such
three curves for the set ${\mathcal{X}}$ if and only if all the nodes of
${\mathcal{X}}$ lie in a curve of degree $n-2,$ or all the nodes of
${\mathcal{X}}$ but three lie in a (maximal) curve of degree $n-3.$

In the sequel we will use the following

######  Theorem 2.3 (Th. 3, [4]).

Assume that ${\mathcal{X}}$ is an $n$-independent set of $d(n,k-2)+2$ nodes
with $3\leq k\leq n-1.$ Then at most four linearly independent curves of
degree $\leq k$ may pass through all the nodes of ${\mathcal{X}}.$ Moreover,
there are such four curves for the set ${\mathcal{X}}$ if and only if all the
nodes of ${\mathcal{X}}$ but two lie in a maximal curve of degree $k-2.$

##  3 Proof of Proposition 2.2

Assume by way of contradiction that there are four linearly independent curves
of degree $\leq n-1$ passing through all the nodes of the $n$-independent set
$\mathcal{X},$ with $\\#{\mathcal{X}}=d(n,n-3)+3.$ Then, according to Theorem
2.3, all the nodes of $\mathcal{X}$ but three belong to a maximal curve $\mu$
of degree $n-3.$ The curve $\mu$ is maximal and the remaining three nodes of
${\mathcal{X}},$ denoted by $A,B$ and $C,$ are outside of it:
$A,B,C\notin\mu.$ Hence we have that

${\mathcal{P}}_{n-1,{\mathcal{X}}}=\left\\{p\in\Pi_{n-1}:p_{\mathcal{X}}=0\right\\}=\left\\{{q\mu:q\in\Pi_{2}},\
q(A)=q(B)=q(C)=0\right\\}.$

Thus we get readily that

$\quad\dim{\mathcal{P}}_{n-1,{\mathcal{X}}}=\dim\left\\{{q\in\Pi_{2}}:q(A)=q(B)=q(C)=0\right\\}$
$=\dim{\mathcal{P}}_{2,\\{A,B,C\\}}\\\ =6-3=3,$ which contradicts our
assumption. Note that in the last equality we use Proposition 1.6 and the fact
that any three nodes are $2$-independent.

Now, let us verify the part “if”. By assuming that there is a curve $\sigma$
of degree $n-3$ passing through the nodes of $\mathcal{X}$ we find readily
three linearly independent curves of degree $\leq n-1:\ $
$\sigma,x\sigma,y\sigma,$ passing through $\mathcal{X}.$ While if we assume
that all the nodes of ${\mathcal{X}}$ but three lie in a curve $\mu$ of degree
$n-3$ then above evaluation shows that
$\dim{\mathcal{P}}_{n-1,{\mathcal{X}}}=3.$

Note that till here the proof was similar to the proof of Theorem 2.1 in [5].

Finally, let us verify the part “only if”. Denote the three curves passing
through all the nodes of the set ${\mathcal{X}}$ by
$\sigma_{1},\sigma_{2},\sigma_{3}.$ If one of them is of degree $n-2$ then the
conclusion of Theorem is satisfied and we are done. Thus, we may assume that
each curve is of exact degree $n-1$ and has no multiple components.

We start with two nodes $B_{1},B_{2}\notin{\mathcal{X}}$ for which the
following conditions are satisfied, where the line between $B_{1}$ and $B_{2}$
is denoted by $\ell_{12}.$

$i)$ The nodes $B_{1},B_{2}$ do not belong to the curves
$\sigma_{1},\sigma_{2},\sigma_{3}$;

$ii)$ The set ${\mathcal{X}}\cup\\{B_{1},B_{2}\\}$ is $n$-independent;

$iii)$ The line $\ell_{12}$ does not pass through any node from
${\mathcal{X}};$

$iv)$ The line $\ell_{12}$ intersects each of the curves
$\sigma_{1},\sigma_{2},\sigma_{3},$ at $n-1$ different points. Moreover, it
intersects any two different components of these curves at different points.

Let us verify that one can find such two nodes. Indeed, in view of Lemma 1.5,
we can start by choosing some nodes $B_{i}^{\prime},i=1,2,$ satisfying the
conditions $i)$ and $ii)$. Then, according to Lemma 1.4, for some positive
$\epsilon$ any two nodes in the $\epsilon$ neighborhoods of
$B_{i}^{\prime},i=1,2,$ respectively, satisfy the first two conditions.

Next, from these neighborhoods, in view of Theorem 1.13, we can choose the
nodes $B_{i},\ i=1,2,$ satisfying the condition $iii)$ and $iv)$ too. Let us
mention that to get the part “Moreover” of $iv)$ we apply Theorem 1.13 for the
curve consisting of all different components of the curves
$\sigma_{1},\sigma_{2},\sigma_{3}.$

In the proof of Proposition later we will need the following

######  Lemma 3.1.

Assume that the hypotheses of Proposition 2.2 hold and assume additionally
that at least one of the following conditions hold:

(a) A nontrivial linear combination of two polynomials from
$\\{\sigma_{1},\sigma_{2},\sigma_{3}\\},$ denoted by $s_{2},$ vanishes at
$B_{1}$ and $B_{2}:\ s_{2}(B_{1})=s_{2}(B_{2})=0.$

(b) A nontrivial linear combination of the polynomials
$\\{\sigma_{1},\sigma_{2},\sigma_{3}\\},$ denoted by $s_{3},$ vanishes at
$B_{1},B_{2},$ and
$B_{3}\in\ell_{12}:s_{3}(B_{1})=s_{3}(B_{2})=s_{3}(B_{3})=0,$ and the set
$\mathcal{X}^{\prime\prime\prime}:=\mathcal{X}\cup\\{B_{1},B_{2},B_{3}\\}$ is
$n$-independent;

Then we have that the statement of Proposition 2.2 holds.

###### Proof.

Let us start with (b). In view of Proposition 1.12 we can extend the set
$\mathcal{X}^{\prime\prime\prime}$ till a maximal $n$-independent set
${\mathcal{Y}}\subset s_{3},$ by adding $d(n,n-1)-(d(n,n-3)+3)-3=1$ node,
denoted by $B,$ i.e.,
$\mathcal{Y}=\mathcal{X}^{\prime\prime\prime}\cup\\{B\\}.$

Thus $s_{3}$ is a maximal curve of degree $n-1$ for the node set
$\mathcal{Y}.$

Then, in view of Lemma 1.14, we can find a nontrivial linear combination $s$
of $\sigma_{1},\sigma_{2},\sigma_{3},$ such that $s$ differs from $s_{3}$ and
vanishes on $\mathcal{X}\cup\\{B\\}.$

Now consider the polynomial $s\ell_{12}\in\Pi_{n},$ which vanishes on the node
set ${\mathcal{Y}}.$ By Proposition 1.11 we conclude that

$s\ell_{12}=s_{3}\ell,\ \hbox{where}\ \ell\in\Pi_{1}.$

The line $\ell_{12}$ differs from $\ell,$ since $s$ differs from $s_{3}.$
Therefore we get that

$s_{3}=\ell_{12}q,\ \hbox{where}\ q\in\Pi_{n-2}.$ (3)

Now, by using $iii),$ we obtain that $q|_{\mathcal{X}}=0.$ Hence the statement
of Proposition 2.2 holds.

(a) Assume, without loss of generality, that
$s_{2}:=c_{1}\sigma_{1}+c_{2}\sigma_{2},\ s_{2}\neq 0,$ and
$s_{2}(B_{1})=s_{2}(B_{2})=0.$

Let us show that there is a node $B_{3}\in\ell_{12}$ such that
$s_{2}(B_{3})\neq 0.$ Indeed, assume conversely that $s_{2}|_{\ell_{12}}=0.$
Then, by Proposition 1.7, we obtain that

$s_{2}=\ell_{12}q,\ q\in\Pi_{n-2},$

which finishes the proof in the same way as the relation (3).

Now, note that $s_{2}$ is a fundamental polynomial for
$B_{3}\in\mathcal{X}^{\prime\prime\prime}:=\mathcal{X}\cup\\{B_{1},B_{2},B_{3}\\}.$
By Lemma 1.3 the set $\mathcal{X}^{\prime\prime\prime}$ is is $n$-independent.

Then assume, in view of Lemma 1.14, that $s$ is a nontrivial linear
combination of $s_{2}$ and $\sigma_{3}$ such that $s(B_{3})=0,$ implying that
$s|_{\mathcal{X}^{\prime\prime\prime}}=0.$ Thus the hypothesis of (b) is
satisfied. ∎

Next, let us continue the proof of Proposition 2.2.

By using Lemma 1.14, consider a nontrivial linear combination of
$\sigma_{1},\sigma_{2},\sigma_{3},$ denoted by $s,$ that vanishes at $B_{1}$
and $B_{2}.$ Set
$\mathcal{X}^{\prime\prime}:=\mathcal{X}\cup\\{B_{1},B_{2}\\}.$

Denote the set of intersection points of the line $\ell_{12}$ and the curve
$s,\deg s=n-1,$ by $\mathcal{I}:=\ell_{12}\cap s.$ We have that
$\\#\mathcal{I}=n-1,$ counting also the multiplicities. Of course
$B_{1},B_{2}\in\mathcal{I}.$

Case 1. First consider the case when one of $B_{1},B_{2},$ say $B_{1},$ is a
multiple point of intersection, i.e., $D_{\bf a}s(B_{1})=0,$ where ${\bf a}$
is the direction vector of the line $\ell_{12}.$

Let us prove that the set
$\mathcal{Y}:=\mathcal{X}^{\prime\prime}\cup\\{B_{1}^{(1)}\\}=\mathcal{X}\cup\\{B_{1},B_{2},B_{1}^{(1)}\\}$
is $n$-independent, where $B_{1}^{(1)}$ means the directional derivative node
with the direction ${\bf a}$ at $B_{1}.$ According to Lemma 1.3 we need to
point out a fundamental polynomial $q\in\Pi_{n},$ for
$B_{1}^{(1)}\in\mathcal{Y},$ i.e., $q|_{\mathcal{X}^{\prime\prime}}=0$ and
$D_{\bf a}q(B_{1})\neq 0.$

For this end consider a nontrivial polynomial
$s_{0}:=c_{1}\sigma_{1}+c_{2}\sigma_{2},\ s_{0}\neq 0,$ which vanishes at
$B_{2}:\ s_{0}(B_{2})=0.$

In view of Lemma 3.1 we may assume that $s_{0}(B_{1})\neq 0.$

Then consider a line $\ell$ passing through $B_{1}$ with a direction vector
different from ${\bf a}.$ One can verify readily that the polynomial $q:=\ell
s_{0}$ is a desired polynomial. Indeed, we have that
$q|_{\mathcal{X}^{\prime\prime}}=0.$ Then we have that

$D_{\bf a}q(B_{1})=D_{\bf a}[\ell s_{0}](B_{1})$ $=(D_{\bf
a}\ell)(B_{1})s_{0}(B_{1})+\ell(B_{1})D_{\bf a}s_{0}(B_{1})=(D_{\bf
a}\ell)(B_{1})s_{0}(B_{1})\neq 0.$

Thus the set $\mathcal{Y}$ is $n$-independent and hence this case can be
proved in the same way as Lemma 3.1 (b).

Case 2. It remains to consider the case when both $B_{1}$ and $B_{2}$ are
simple points of intersection. We have that $\\#\mathcal{I}=n-1\geq 3.$
Consider another point of intersection of $\ell_{12}$ and $s:\
B\in\mathcal{I},\ B\neq B_{1},B_{2}.$

In view of Lemma 3.1, (b), we may assume the following

Assumption 1. _The set
$\mathcal{X}^{\prime\prime}\cup\\{B\\}=\mathcal{X}\cup\\{B_{1},B_{2},B\\}$ is
$n$-dependent._

This here means that $\ p\in\Pi_{n},\
p|_{\mathcal{X}^{\prime\prime}}=0\implies p(B)=0.$

Now consider two nontrivial linear combinations $s_{1},s_{2}$ of
$\sigma_{1},\sigma_{2}$ such that $s_{1}(B_{2})=s_{2}(B_{1})=0.$

By Lemma 3.1, (a), we get that $s_{i}(B_{i})\neq 0,\ i=1,2.$ Assume, without
loss of generality, that $s_{i}(B_{i})=1,\ i=1,2.$

Next let us show that $s_{i}(B)=0,\ i=1,2.$ Let say $i=1.$ Consider the
polynomial $q:=\ell s_{1}\in\Pi_{n},$ where the line $\ell$ passes through
$B_{1}$ and does not pass through $B.$ We have that $q(B_{1})=q(B_{2})=0.$ By
using Assumption 1 and Lemma 1.3 we get that $q(B)=0$ hence $s_{1}(B)=0.$

Now we are in a position to show that
$\sigma_{1}(B)=\sigma_{2}(B)=\sigma_{3}(B)=0.$

Let us show for example that $\sigma_{1}(B)=0.$

Consider the polynomial $p=\sigma_{1}-c_{1}s_{1}-c_{2}s_{2},$ where
$c_{i}=\sigma_{1}(B_{i}).$ We get readily that $p(B_{1})=p(B_{2})=0.$ Hence,
in view of Assumption 1, as above, we get that $p(B)=0.$ It remains to note
that $\sigma_{1}(B)=p(B)=0.$

Next suppose that the point $B$ is multiple:

$s(B)=D_{\bf a}s(B)=\ldots,D^{(k)}_{\bf a}s(B)=0,\ k\in\mathbb{N}.$

In view of Lemma 3.1, (b), we may assume the following

Assumption 2. _The set $\mathcal{X}^{\prime\prime}\cup\\{B^{(i)}\\},\
i=0,\ldots,k$ is $n$-dependent._

This here means that

$p\in\Pi_{n},\ p|_{\mathcal{X}^{\prime\prime}}=0\implies p(B)=D_{\bf
a}p(B)=\ldots=D^{(k)}_{\bf a}p(B)=0.$ (4)

Now consider the above defined polynomials $s_{1}$ and $s_{2}$ with

$s_{1}(B_{1})=1,s_{1}(B_{2})=s_{1}(B)=0,\ \
s_{2}(B_{2})=1,s_{2}(B_{1})=s_{1}(B)=0.$

By using induction on $k$ let us show that

$D^{(i)}_{\bf a}s_{j}(B)=0,\ i=0,1,\ldots,k,\ j=1,2.$ (5)

Let say $j=1.$ The first step of induction is the above considered case $k=0.$
Assume that the case of $k-1$ is true, i.e., the first $k$ equalities in (5)
hold. Let us prove the last one, i.e., $D^{(k)}_{\bf a}p(B)=0.$

Consider the polynomial $q:=s_{1}\ell\in\Pi_{n},$ where the line $\ell$ passes
through $B_{1}$ and does not pass through $B.$ We have that
$q(B_{1})=q(B_{2})=0.$ In view of Assumption 2 we get that

$0=D_{\bf a}^{(k)}[s_{1}\ell](B)=D^{(k)}_{\bf a}s_{1}(B)\ell(B)+kD_{\bf
a}^{(k-1)}s_{1}(B)D_{\bf a}\ell(B)=D^{(k)}_{\bf a}s_{1}(B)\ell(B).$

Since $\ell(B)\neq 0$ we conclude that $D^{(k)}_{\bf a}s_{1}(B)=0.$

Now we are in a position to show that

$D^{(i)}_{\bf a}\sigma_{1}(B)=D^{(i)}_{\bf a}\sigma_{2}(B)=D^{(i)}_{\bf
a}\sigma_{3}(B)=0,\ i=0,1,\ldots,k.$ (6)

Let us prove say equalities with $\sigma_{1}.$ Consider the polynomial

$p=\sigma_{1}-c_{1}s_{1}-c_{2}s_{2},\ \hbox{where}\ c_{i}=\sigma_{1}(B_{i}).$
(7)

We get readily that $p(B_{1})=p(B_{2})=0.$ Hence, in view of Assumption 2, as
above, we get that $p(B)=D_{\bf a}p(B)=\ldots=D^{(k)}_{\bf a}p(B)=0.$ It
remains to use the relations (5) and (7).

Hence except the two intersection points
$B_{1},B_{2}\in\mathcal{I}:=\ell_{12}\cap,s$ all other $n-3$ points, counting
also the multiplicities, are common for the three curves
$\sigma_{1},\sigma_{2},$ and $\sigma_{3}.$

From this, in view of the condition $(iv)$ (page 5), we conclude that the
above three polynomials $\sigma_{1},\sigma_{2},$ and $\sigma_{3},$ have a
common divisor $q\in\Pi_{n-3}:$

$\sigma_{1}=\beta_{1}q,\quad\sigma_{2}=\beta_{2}q,\quad\sigma_{3}=\beta_{3}q,\
\hbox{where}\ \beta_{i}\in\Pi_{2}.$

Therefore we have that

$\mathcal{X}\subset\sigma_{1}\cap\sigma_{2}\cap\sigma_{3}\subset
q\cup[\beta_{1}\cap\beta_{2}\cap\beta_{3}].$ (8)

Now consider two cases for $\mathcal{B}:=\beta_{1}\cap\beta_{2}\cap\beta_{3}:$

Case (a), $\\#\mathcal{B}\geq 4.$

According to Proposition 1.6 any subset $\mathcal{A}\subset\mathcal{B}$ with
$\\#\mathcal{A}=4$ is $2$-dependent. From here we obtain readily that the
points of $\mathcal{A}$ are collinear. Hence all the points of $\mathcal{B}$
are collinear: $\mathcal{B}\subset\ell\in\Pi_{1}.$

Now we readily get that $\ell$ is a common divisor of $\beta_{1},\beta_{2},$
and $\beta_{3},$ i.e.,

$\beta_{1}=\ell_{1}\ell,\quad\beta_{2}=\ell_{2}\ell,\quad\beta_{3}=\ell_{3}\ell,$

where $\ell_{i}\in\Pi_{1}.$ Thus, as above, we get that

$\mathcal{B}\subset\ell\cup[\ell_{1}\cap\ell_{2}\cap\ell_{3}]\subset\ell.$ (9)

The last relation here we get from the fact that the polynomials
$\sigma_{1},\sigma_{2},\sigma_{3},$ and hence the polynomials
$\ell_{1},\ell_{2}\,\ell_{3},$ are linearly independent and hence
$\ell_{1}\cap\ell_{2}\cap\ell_{3}=\emptyset.$

Finally, we get from (8) and (9) that

$\mathcal{X}\subset q\cup\ell,$

or, in other words, all the nodes of ${\mathcal{X}}$ lie in a curve of degree
$n-2,$ namely in the curve $q\ell\in\Pi_{n-2}.$

Case (b), $\\#\mathcal{B}\leq 3.$

In this case we obtain from (8) that all the nodes of ${\mathcal{X}}$ but
$\leq 3$ lie in a curve $q$ of degree $n-3.$ From here we readily conclude
that $q$ is a maximal curve and exactly $3$ nodes of $\mathcal{X}$ are outside
of it.

Thus Proposition 2.2 is proved.

Finally note that in view of Theorem 2.1 and Proposition 2.2 one can formulate
the following

######  Theorem 3.2.

Assume that ${\mathcal{X}}$ is an $n$-independent set of $d(n,k-2)+3$ nodes
with $3\leq k\leq n-1.$ Then at most three linearly independent curves of
degree $\leq k$ may pass through all the nodes of ${\mathcal{X}}.$ Moreover,
there are such three curves for the set ${\mathcal{X}}$ if and only if all the
nodes of ${\mathcal{X}}$ lie in a curve of degree $k-1,$ or all the nodes of
${\mathcal{X}}$ but three lie in a (maximal) curve of degree $k-2.$

REFERENCES

## References

  * [1] Eisenbud D., Green M., Harris J., Cayley-Bacharach Theorems and Conjectures. Bull. Amer. Math. Soc. (N.S.), 33:3 (1996), 295–324.
  * [2] Hakopian H., On the regularity of multiariate Hermite interpolation J. Approx. Theory, 105 (2000), 1–18.
  * [3] Hakopian H., Jetter K., Zimmermann G. Vandermonde matrices for intersection points of curves. Jaen J. Approx., 1 (2009), 67–81.
  * [4] Hakopian H., Kloyan H., On the dimension of spaces of algebraic curves passing through $n$-indepent nodes. Proceedings of YSU. Physical and Mathematical Sciences, no. 2 (2019), 3–13.
  * [5] Hakopian H., Kloyan H., Voskanyan D., On plane algebraic curves passing through $n$-independent nodes, J. Cont. Math. Anal., 2021, 56, (2021), 280–294.
  * [6] Hakopian H., Malinyan A. Characterization of $n$-independent sets with no more than $3n$ points. Jaen J. Approx., 4:2 (2012), 121–136.
  * [7] Hakopian H., Toroyan S. On the Uniqueness of algebraic curves passing through $n$-independent nodes. New York J. Math., 22 (2016), 441–452.
  * [8] Rafayelyan L. Poised nodes set constructions on algebraic curves. East J. Approx., 17:3 (2011), 285–298.
  * [9] Walker R. J., Algebraic Curves, Princeton, New Jersey, 1950.

The work was carried out under grant 21T-A055 from the Scientific Committee of
the Ministry of ESCS RA.


∎

11institutetext:  Liping Zheng
11email<EMAIL_ADDRESS>22institutetext:  School of Computer Science and
Information Engineering, Hefei University of Technology, Hefei, China Anhui
Province Key Laboratory of Industry Safety and Emergency Technology, Hefei
University of Technology, Hefei, China School of Software, Hefei University of
Technology, Hefei, China

# SRA-LSTM: Social Relationship Attention LSTM for Human Trajectory Prediction

Yusheng Peng1,2 Gaofeng Zhang3 Jun Shi3 Benzhu Xu3 Liping Zheng1,2,3

(Received: date / Accepted: date)

###### Abstract

Pedestrian trajectory prediction for surveillance video is one of the
important research topics in the field of computer vision and a key technology
of intelligent surveillance systems. Social relationship among pedestrians is
a key factor influencing pedestrian walking patterns but was mostly ignored in
the literature. Pedestrians with different social relationships play different
roles in the motion decision of target pedestrian. Motivated by this idea, we
propose a Social Relationship Attention LSTM (SRA-LSTM) model to predict
future trajectories. We design a social relationship encoder to obtain the
representation of their social relationship through the relative position
between each pair of pedestrians. Afterwards, the social relationship feature
and latent movements are adopted to acquire the social relationship attention
of this pair of pedestrians. Social interaction modeling is achieved by
utilizing social relationship attention to aggregate movement information from
neighbor pedestrians. Experimental results on two public walking pedestrian
video datasets (ETH and UCY), our model achieves superior performance compared
with state-of-the-art methods. Contrast experiments with other attention
methods also demonstrate the effectiveness of social relationship attention.

###### Keywords:

trajectory prediction social interaction social relationship social
relationship attention

††journal: Neural Computing and Applications

##  1 Introduction

Pedestrian trajectory prediction is an important research topic in the field
of computer vision, and has various applications, such as intelligent
surveillance system, autonomous driving system and robot navigation system.
Intelligent surveillance system plan an important role in preventing and
investigating crimes, protecting public safety, and safeguarding national
security. However, due to the intricate and subtle interactions between
pedestrians, the pedestrian trajectory prediction for surveillance video is
still challenging, which has attracted much attention from both academia and
industry in recent years.

In summary, the general framework of intelligent surveillance consists of
several stages including environment modeling 1 , object classification 2 ,
tracking 3 , behaviour understanding and description 4 , motion understanding
and detection 5 , and possibly personal identification 6 . Our work is
concerned with the stage of behavior and motion analysis, and more
specifically, predicting the future trajectory of given trajectory data from
the tracking stage. Before executing the trajectory prediction task, the
position sequences of all pedestrians in the video are obtained through the
tracking algorithm 7 .

The trajectory of a pedestrian can be influenced by multiple factors such as
scene topologies, pedestrian beliefs, and human-human interactions. Many
scholars have worked to model the intricate and subtle interactions that often
take place among the pedestrians. Although the hand-crafted energy functions
adopted in earlier works 8 ; 9 ; 10 ; 11  attempted to build crowd
interactions among pedestrians in crowded spaces, it is challenging to take a
comprehensive consideration of various social behaviors. In recent years,
Long-Short Term Memory networks(LSTM) 12  are widely used for each pedestrian
to capture latent motion patterns in the trajectory prediction task. In LSTM
architecture based trajectory prediction methods, the pooling 13 ; 14 ,
attention 15 ; 16 , and graph 17 ; 18  mechanisms are widely used to model
complex social interactions. The pooling mechanism utilizes social pooling on
the occupancy maps to integrate the latent motions of pedestrians in a local
neighborhood or the whole scene. The attention mechanism integrates latent
motions by assigning different attention weights to neighbors. The graph
structure mechanism constructs a graph based on observed trajectories of
participants to explicitly model the paired interactions between participants.
Compared with the other two mechanisms, the attention mechanism can model the
contributions of different neighbor pedestrians to the target pedestrian to
better predict the future trajectory. For this reason, some pooling based 19 ;
22  and graph based 20  approaches are coupled with attention mechanism to
achieve good prediction performance. The attention mentioned in existing work
is always captured by latent motion patterns 15 ; 21  or spatial
information(i.e. distance, relative position, bearing angle) 16 ; 22 .
However, both types of attention methods simply capture attention from
possible motion interactions.

Figure 1: Illustration of the social relationship attention in the crowd. A
and B are friends with similar motion patterns of their trajectories. A and C
are strangers who come from different source places and go to different
destinations. The social relationships of A-B and A-C are different so that A
pays different attention to B and C when predicting the future trajectory.

However, although the diverse aspects have been well researched, a factor was
neglected in previous work. The inference of the pedestrian’s future
trajectory is not only affected by the motion interaction but also closely
related to the social relationship between pedestrians. As shown in Fig.1, A
and B are friends, and the motion patterns of their trajectories are similar.
Because of their accompanying behavior, they would pay higher attention to
each other when predicting the future trajectory. As to A and C, who have a
strange relationship, they keep less attention to each other unless there has
possible motion interaction. We intend to model social interaction by social
relationship attention that coupling the social relationship between
pedestrians and possible motion interactions. Social relationship attention
takes into account the influence of social relationships and motion
interactions on pedestrian trajectory prediction.

To model this new insight, we present a novel LSTM architecture that
recursively encodes social relationships and integrates information by social
relationship attention, called Social Relationship Attention LSTM (SRA-LSTM).
For each pedestrian, an LSTM is used to capture latent motion patterns. For
each pair of pedestrians, an LSTM is applied to encode their relative
positions and thus generate the feature representation for manifesting their
social relationship. The social relationship attention is captured by the
hidden state of motion LSTM and social relationship encoder, which used to
integrate neighbor pedestrians’ hidden states. The integrated hidden state is
served as the input of motion LSTM, and the output hidden state predicts the
position of the next key frame. Experiments on multiple human trajectory
baseline, including two datasets in ETH 9  and three datasets in UCY 23 , show
the superiority of our model. Our contributions can be summarized as follows:

  1. 1.

We propose a novel interactive recurrent structure, namely SRA-LSTM, serving
as a new pipeline for jointly predicting the future trajectories of
pedestrians in the crowd.

  2. 2.

We adopt an LSTM as a social relationship encoder to model the temporal
correlation of the relative position among pedestrians to obtain a
representation of their social relationship. To the best of our knowledge, the
modeling of social relationships by the temporal correlation of relative
positions hasn’t been considered separately yet.

  3. 3.

We propose a novel attention mechanism called social relationship attention,
which takes into account the consideration of the social relationship between
pedestrians and their motion patterns. This attention module is applied to the
prediction task, which contributes to greater expressive power and higher
performance.

The rest of the paper is organized as follows. Section 2 reviews the related
works. The proposed SRA-LSTM model for human trajectory prediction is
described in Section 3. Experiment results are evaluated and discussed in
Section 4. We conclude this paper and point out the future works in Section 5.

##  2 Related Works

The social interaction in trajectory prediction contains Human-human
interaction and Human-Scene interaction. The former models the dynamic content
of the scenes, i.e. how pedestrians interact with each other. The latter tends
to learn scene-specific motion patterns 24 ; 25 ; 26 ; 27 ; 28 . The focus of
our work is the former: learning to model human-human interactions. We review
existing work on this topic as well as relevant work in LSTMs based and
attention approaches in trajectory prediction.

###  2.1 LSTM models for trajectory prediction

As a classic variant of RNNs, LSTM has achieved great success in various
sequence tasks 29 ; 30 ; 31 . Aliha 13  proposed the Social-LSTM model that
first introduced the LSTM network for pedestrian trajectory prediction. In
Social-LSTM model, a separate LSTM network is used for each trajectory in a
scene, and the LSTMs are connected through a social pooling layer. These LSTM
framework models32 ; 33  utilize LSTMs to capture motion features and connect
the LSTMs through specific designed modules to model social interaction among
pedestrian

Besides being the main framework of prediction models, the LSTM network is
often used as the encoder and decoder in GAN framework models 14 ; 34 ; 35
and encoder-decoder framework models 36 ; 37 . Among them, the LSTM encoder is
applied to learn motion features from historical trajectories, and the decoder
acts as a predictor to predict future trajectories. Not limited to this, Huang
et al. 38  adopt an extra LSTM to encode the temporal correlations of
interactions, Xue et al. 39 ; 40  utilize two LSTM layers to capture the
location information as well as the velocity information, and Syed et al. 26
utilize three LSTMs to encode person, social, and scene scale information. In
our approach, we utilize one LSTM to capture motion features, and another LSTM
is served as a social relationship encoder to acquire the representation of
social relationships between each pair of pedestrians.

###  2.2 Research on human-human Interactions

Modeling social interactions is crucial for pedestrian trajectory prediction.
These interactions can be defined by hand-crafted rules, such as social forces
8  and stationary crowds¡¯ influences 10 ; 11 . However, it is difficult to
capture the complex interactions in the scenario by these rules. Therefore,
the majority of current research captures social interactions in a data-driven
manner. Social-LSTM 13  firstly proposes the social pooling layer on the
occupancy maps to aggregate neighbor’s latent motion dynamics in a local
neighborhood. Social-GAN 14  removes the regional restraint and directly
aggregates the latent motions of neighbors in the whole scene.

Different from the pooling mechanism, the attention-based message-passing
mechanism models 39 ; 40 ; 41  aggregates information by paying different
attention to neighbor pedestrians, which can better model social interaction.
But beyond that, some recent models 17 ; 34 ; 38  consider the pedestrians in
a scene as nodes on the graph and leverage the Graph Convolution Networks
(GCNs) or Graph Attention Networks (GATs) to aggregate information from
neighbors. Nevertheless, we still apply the attention mechanism to model
social interaction and propose a novel attention.

###  2.3 Attention approaches for trajectory prediction

Attention mechanisms have been proven to be significantly successful in
various tasks 42 ; 43 ; 44 ; 45 . Fernando et al. 15  first apply the
attention mechanism to pedestrian trajectory prediction tasks, in which soft
attention is acquired through hidden states and hard attention is calculated
from distance. Analogously, the soft and hard attention in TPPO model 22  are
calculated on the basis of the cosine values of all pedestrians’ bearing
angles. However, Amirian et al. 19 coupling multiple spatial
features¡ªEuclidean distance, bearing angle, and closest distance¡ªto capture
the attentional weights. Zhang et al. 33  combines the hidden states of each
pair of pedestrians and the embedding vector of their relative position to
capture attentional weights.

Besides the above attention approaches, the temporal attention mechanism
captures the relationships between a time step of the prediction phase and
different time steps of the observed part of the input trajectory. Xue et al.
40  apply two temporal attention mechanisms to the hidden states from the
location and velocity LSTM layers. Zhao et al. 37  apply a spatial-temporal
attention mechanism to connect the decoder state and the temporal encoder
state, which allows give an importance value for each time instant’s
trajectory state of the neighboring humans and the target human. In our
approach, we do not directly capture spatio-temporal attention, but acquire
spatio-temporal features through a specific encoder, and then couple these
features with hidden states to capture attention weights.

Our work in this paper differs from the above works in two main aspects:
firstly, the above works model social interactions by the spatial relationship
among pedestrians and latent motions while we introduce social relationships
to model social interactions. Secondly, we did not adopt the manual label 0/1
in 18  to represent the social relationship among pedestrians, but utilize the
LSTM model to actively learn deeper representation of social relationships
from the relative movement information among pedestrians.

Figure 2: Illustration of the overall approach. At each time-step, the
pedestrians positions are used to calculate relative positions of each other,
and the relative positions are processed through embed layer and LSTM to
encode the social relationships of each pair of pedestrians. The social
relationship attention module models the social interactions by attentively
integrating the hidden states of neighbors. Then the social interaction tensor
and the embedding vector of each pedestrian’s position are treated as inputs
of LSTM to output the current hidden states and infer the positions of next
time-step.

##  3 Proposed Method

The overview of the SRA-LSTM framework is illustrated in Fig.2. We treat one
kind of LSTM as a social relationship encoder to model the temporal
correlation of the relative position between pedestrians to obtain a
representation of their social relationships. Then, the social interactions
are modeled by a social relationship attention module that captures social
relationship attention and attentively integrates hidden states which
represent the latent motion patterns. The embedding of position and output
social tensor are treated as an input of motion LSTM for each person to
capture current latent motions and infer the position of the next time-step.

###  3.1 Problem Formulation

In this paper, we address the problem of pedestrian trajectory prediction in
the crowd scenes for surveillance video. For better modeling the social
interactions among pedestrians, we focus on two-dimensional coordinations of
pedestrians in the world coordinate system at specific key frames. For each
sample, we assume there are _N_ pedestrians involved in the scene of
surveillance video. Given certain observed positions
$\\{p_{i}^{t}|(x_{i}^{t},y_{i}^{t}),t=1,2,...,T_{obs}\\}$ of pedestrians _i_
of $T_{obs}$ key frames, our goal is predicting the positions
$\\{p_{i}^{t^{\prime}}|(\widehat{x}_{i}^{t^{\prime}},\widehat{y}_{i}^{t^{\prime}}),{t^{\prime}}=T_{obs}+1,T_{obs}+2,...,T_{pred}\\}$
of future $T_{pred}$ key frames.

###  3.2 Social Relationship Encoding

In crowd scenes, pedestrians with different social relationships exhibit
different social behaviors. Pedestrians with intimate relationships (such as
lovers, friends) tend to maintain a stable intimate distance while walking.
Pedestrians tend to change their walking routes to avoid the approaching of
strange pedestrians. Therefore, the social relationship between pedestrians is
a factor that cannot be ignored in pedestrian trajectory prediction modeling.
However, the social relationship between a pair of pedestrians is unknown in
the trajectory prediction task. Our primary task is acquiring knowledge that
can represent the social relationship between pedestrians.

Motivated by the idea above, Sun et al. 18  utilize group-based social
interaction model to explore relationships among pedestrians. Sun invited
experts who have sociological background to judge the relationship of two
pedestrians and utilize labels to annotate whether pedestrians belong to the
same group. In contrast, we intend to capture the representation of social
relationship by a spatio-temporal model. Therefore, we try to obtain a
representation of the social relationship by modeling the temporal correlation
of the relative positions between pedestrians. In our method, for each pair of
pedestrians, an LSTM is used as an encoder to encode the relative position of
the pedestrians recurrently to capture the representation of their social
relationship. As illustrated in Fig.3, for the target pedestrian i, the
relative positions of the neighbor pedestrians are calculated and served as
the current input of the LSTM encoder. The current hidden state of the LSTM
encoder represents the social relationship between the pair of pedestrians. We
term this LSTM as R-LSTM (LSTM for social relationship encoding):

$\displaystyle
e_{ij}^{t}={\phi}_{r}(x_{j}^{t}-x_{i}^{t},y_{j}^{t}-y_{i}^{t};W_{re})$ (1)
$\displaystyle r_{ij}^{t}=\textrm{R-LSTM}(r_{ij}^{t-1},e_{ij}^{t};W_{r})$ (2)

where $e_{ij}^{t}$ is embedding vector of the relative spatial location.
$W_{re}$ denotes the parameter for the embedding function ${\phi}_{r}$.
$r_{ij}^{t}$ is the hidden state of the R-LSTM among pedestrian _i_ and _j_ at
the time-step _t_ , $W_{r}$ is the R-LSTM weight and is shared among all the
sequences.

In real life interpersonal communication, the intimate relationship between
people is not equal because of the diversity and the difference in
interpersonal emotions. As illustrated by the right part of Fig.3, the
understanding of social relationships between pedestrians is not equal, e.g.
$r_{12}^{t}\neq r_{21}^{t}$. $r_{12}^{t}$ represents the pedestrian 1’s
understanding of the social relationship between pedestrians 1 and 2.
Similarly, $r_{12}^{t}$ is the understanding of social relationship from
pedestrian 2. The representation $r_{ij}^{t}$ of the social relationship
between pedestrians is continuously learning as time steps increases.

Figure 3: We model the spatio-temporal relationship of pedestrians’ positions
to capture the representation of social relationship between each pair of
pedestrians. For each time-step, the relative position between couple of
pedestrians is processed through embed layer and LSTM to output the
representation tensor of social relationships.

###  3.3 Social Relationship Attention Module

Vanilla LSTM used for per person does not capture human-human interactions. To
model the social interaction behavior between pedestrians, pooling mechanism
13 ; 14 ; 32  is used to aggregate hidden states between pedestrians on
occupancy map. Recently, the trajectory prediction models 15 ; 33 ; 37  that
adopt attention mechanisms to model social interaction have achieved good
performance. This is because the attention mechanism can pay different
attention to aggregate the shared information according to the importance of
neighbor pedestrians. Therefore, we adopt the attention mechanism to model
social interactions. SR-LSTM 33  utilizes relative position and hidden states
to capture attention in state refinement module to model social interactions.
ST-Attention 37  adopts soft attention 15  to acquire social interaction
features in encoder, and spatial attention is adopted to capture the different
influences of historical location sequences on future trajectories in the
decoder. Differ from them, we utilize social relationship representation to
capture attention which has similar temporal-spatial property. As shown in
Fig.4(a), Red lines between pedestrians represent the existence of human-human
interactions.

The location and movement intention of the neighbor pedestrian are the key
influence to the decision of the target pedestrian’s movement. Furthermore,
pedestrians with different social relationships always affect the motion
decision of the target pedestrian. Motivated by the idea, we introduce a novel
attention called social relationship attention which is captured by coupling
pedestrians’ latent motion patterns and social relationships of each pair of
pedestrians. The social relationship attention is calculated by:

$\alpha_{ij}^{t}=\frac{\exp{W^{at}[r_{ij}^{t};h_{i}^{t-1};h_{j}^{t-1}]}}{\sum_{k\in
N(i)}{\exp{W^{at}[r_{ik}^{t};h_{i}^{t-1};h_{k}^{t-1}]}}}$ (3)

where the $r_{ij}^{t}$ is the hidden state of the R-LSTM, which represents the
social relationship between pedestrians _i_ and _j_. The $h_{i}^{t-1}$ and
$h_{i}^{t-1}$ are hidden states of pedestrian _i_ and _j_ at time-step $t-1$,
which represent the latent motion patterns of _i_ and _j_ respectively.
$W^{at}$ are a weight matrix.

Figure 4: (a) The red lines between pedestrians represent the exist of human-
human interactions. (b) The target pedestrian attentively aggregate the
features of different neighbors with different importance.

After capturing the social relationship attention, we aggregate the latent
motion patterns by paying attention to neighbor pedestrians. As illustrated in
Fig.4(b), we attentively aggregate the hidden states of each actor to obtain
social interaction context. The social interaction context vector for
pedestrian _i_ at time-step _t_ is given by:

$H_{i}^{t}=\sum_{j\in N(i)}{{\alpha_{ij}^{t}}h_{j}^{t-1}}$ (4)

where $h_{j}^{t-1}$ is the hidden state encoded by history positions of
pedestrian _j_. $N(i)$ is the set of neighbors of pedestrian _i_ , and
$\alpha_{ij}^{t}$ is the attention weight of the pedestrian pair $(i,j)$.

###  3.4 SRA-LSTM Prediction Model

LSTM has been proven to successfully capture the historical motion state of a
single pedestrian 13 ; 32 ; 33 . By following these works, we also employ an
LSTM denoted as motion LSTM to capture the latent motion pattern for each
pedestrian. In our implementation, we use the normalized absolute(Nabs)
position 33  which shifts the origin to the latest observed time slot:

$\begin{split}\Delta x_{i}^{t}&=x_{i}^{t}-x_{i}^{T_{obs}}\\\ \Delta
y_{i}^{t}&=y_{i}^{t}-y_{i}^{T_{obs}}\end{split}$ (5)

The hidden state of motion LSTM of each pedestrian captured by his/her past
Nabs positions, which represents the current latent motion pattern and infer
the position of the next time-step. The latent motion patterns of pedestrians
are independent of each other, so that the predicted positions may collide.
Therefore, we model social interactions by social relationship attention
module that integrate information of neighbor pedestrians for capturing a
social context tensor. We treat the social context tensor and the embedding
vector $e_{i}^{t}$ of position as inputs of the LSTM cell. This introduces the
following recurrence:

$\displaystyle e_{i}^{t}=\phi(\Delta x_{i}^{t},\Delta y_{i}^{t};W_{e})$ (6)
$\displaystyle h_{i}^{t}=\textrm{LSTM}(h_{i}^{t-1},H_{i}^{t},e_{i}^{t};W_{l})$
(7)

where $\phi(\cdot)$ is an embedding function with ReLU nonlinearity, $W_{e}$
is the embedding weights. The LSTM weight is denoted by $W_{l}$. These
parameters are shared among all the pedestrians in the whole scene.
$H_{i}^{t}$ is the social context tensor which is the output of the social
relationship attention module. It is the social interaction feature which is
integrate the hidden states of the interested person and neighbors.

The hidden-state $h_{i}^{t}$ at time _t_ is used to predict the Nab position
$(\Delta\widehat{x}_{i}^{t+1},\Delta\widehat{y}_{i}^{t+1})$ at the next time-
step _t+1_ :

$[\Delta\widehat{x}_{i}^{t+1},\Delta\widehat{y}_{i}^{t+1}]^{T}=W_{p}h_{i}^{t}$
(8)

where $W_{p}$ is a weight matrix. From time $T_{obs}+1$ to $T_{pred}$, we
transform the predicted Nabs positions to absolute positions, which utilized
to calculate relative positions to encode social relationship.

###  3.5 Implementation Details

The parameters of the SRA-LSTM model are directly learned by minimizing the L2
loss between the predicted position and ground truth. All LSTMs in our
implementation only have one layer. The dimension of hidden states of all LSTM
cells is set to 64. The dimension of embed vector $e_{ij}^{t}$ in Eq.1 and
$e_{i}^{t}$ in Eq.6 are set to 32. A sliding time window with a length of 20
and a stride size of 1 is adopted to get the training samples. All trajectory
segments in the same time window are regarded as a mini-batch, as they are
processed in parallel. Adam optimizer is adopted to train models in 300
epochs, with an initial learning rate of 0.001.

Table 1: Quantitative results of all the baselines and the proposed method (SAM:Samples, SCE:Scene, ATT:Attention, SRS:Social Relationships) Method | Notes | Performance(ADE/FDE)
---|---|---
SAM | SCE | ATT | SRS | ETH-univ | ETH-hotel | UCY-zara01 | UCY-zara02 | UCY-univ | AVG
S-LSTM 13  |  |  |  |  | 1.09 / 2.35 | 0.79 / 1.73 | 0.47 / 1.00 | 0.56 / 1.17 | 0.67 / 1.40 | 0.72 / 1.54
SGAN 14  | $\surd$ |  |  |  | 0.87 / 1.62 | 0.67 / 1.37 | 0.35 / 0.68 | 0.42 / 0.78 | 0.76 / 1.52 | 0.61 / 1.21
Sophie 35  | $\surd$ | $\surd$ | $\surd$ |  | 0.70 / 1.43 | 0.76 / 1.67 | 0.30 / 0.62 | 0.38 / 0.75 | 0.54 / 1.24 | 0.54 / 1.15
S-BiGAT 34  | $\surd$ | $\surd$ | $\surd$ |  | 0.69 / 1.29 | 0.49 / 1.01 | 0.30 / 0.62 | 0.36 / 0.75 | 0.55 / 1.32 | 0.48 / 1.00
SR-LSTM 33  |  |  | $\surd$ |  | 0.63 / 1.25 | 0.37 / 0.74 | 0.41 / 0.90 | 0.32 / 0.70 | 0.51 / 1.10 |  0.45 / 0.94
ST-Attenion 37  |  |  | $\surd$ |  | 0.85 / 1.85 | 0.32 / 0.66 | 0.42 / 0.91 | 0.34 / 0.73 | 0.63 / 1.33 | 0.51 / 1.10
RSBG 18  |  |  |  | $\surd$ | 0.80 / 1.53 | 0.33 / 0.64 | 0.40 / 0.86 | 0.30 / 0.65 | 0.59 / 1.25 | 0.48 / 0.99
Ours |  |  | $\surd$ | $\surd$ | 0.59 / 1.16 | 0.29 / 0.56 | 0.37 / 0.82 | 0.43 / 0.93 | 0.55 / 1.19 | 0.45 / 0.93

##  4 Experiments

In this section, we evaluate our method on two public walking pedestrian video
datasets: ETH and UCY. These two datasets contain 5 crowd scenes, including
ETH-univ, ETH-hotel, UCY-zara01, UCY-zara02, and UCY-univ. There are 1536
pedestrians and thousands of real-world pedestrian trajectories. All the
trajectories are converted to the world coordinate system and then
interpolated to obtain values at every 0.4 seconds.

Evaluation Metrics. Similar to prior works 13 ; 14 , the proposed method is
evaluated with two types of metrics as follow:

  1. 1.

_Average Displacement error(ADE)_ : the mean square error(MSE) between the
ground-truth trajectory and predicted trajectory over all predicted time
steps.

  2. 2.

_Final Displacement error(FDE)_ : the mean square error(MSE) between the
ground-truth trajectory and predicted trajectory at the last predicted time
steps.

Baseline. We do not use traditional methods(such as linear model, social force
model, etc.) based on handcrafted features as baselines, but only compared
with the deep learning models. We compare the proposed model with the
following recent works:

  1. 1.

_S-LSTM_ 13 : An improved trajectory prediction method that combines LSTM with
a social pooling layer, which can aggregate hidden states of the neighbor
pedestrians. Future trajectories are predicted by decoding the concatenation
of coordinates embedding and social pooling vector.

  2. 2.

_SGAN_ 14 : An improved version of S-LSTM that the social pooling is displaced
with a new pooling mechanism which can learn a ”global” pooling vector. A
variety loss function is proposed to encourage the GAN to spread its
distribution and generate multiple socially acceptable trajectories.

  3. 3.

_SoPhie_ 35 : An attentive GAN model for trajectory prediction by using social
and physical attention modules. The trajectory prediction performance is
improved by highlighting the key information with attention operations.

  4. 4.

_S-BiGAT_ 34 : An improved version of SGAN by using the bicycle structure to
train the generator. A graph attention network is used to model social
interactions for better prediction performance. Self-attention is used on
images to consider the physical feature of a scene.

  5. 5.

_SR-LSTM_ 33 : An improved version of S-LSTM by proposing a data-driven state
refinement module. The refinement module can jointly and iteratively refines
the current states of all participants in the crowd on the basis of their
neighbors’ intentions through a message passing mechanism.

  6. 6.

_ST-Attention_ 37 : A novel spatial-temporal attention (ST-Attention) model,
which studies spatial and temporal affinities jointly. Among them, a novel
temporal attention mechanism is used to extract temporal affinity, and the
soft attention mechanism 15  is used to explore spatial affinity.

  7. 7.

_RSBG_ 18 : A novel structure called Recursive Social Behavior Graph, which is
supervised by group-based annotations. The social interactions are modeled by
GCNs that adequately integrate information from nodes and edges in RSBG.

Evaluation Methodology. We use the leave-one-out approach similar to that from
S-LSTM 13 . Specifically, we train models on four datasets and test on the
remaining dataset. We take the coordinates of 8 key frames (3.2s) of the
pedestrian as the observed trajectory, and predict the trajectory of the next
12 key frames (4.8s). For each mini-batch, random rotation is employed for
data augmentation.

###  4.1 Quantitative Evaluations

####  4.1.1 Evaluations on ADE/FDE Metrics

We compare our method to the various baselines in Table 1 and report the
average displacement error (ADE) and final displacement error (FDE). We
compare the differences among the methods in the notes section. SAM denotes
that the model was trained using variety loss and predicts 20 samples for each
observed trajectory during test time, ATT denotes using attention mechanism,
SCE denotes using scene information, SRS denotes that the model take advantage
of social relationship. Among these baselines, S-LSTM, SR-LSTM, ST-Attention,
and RSBG are deterministic models. For these models, only one socially
acceptable path is predicted of each person according to observed trajectory.
The proposed SRA-LSTM is also a deterministic model. The SGAN, Sophie, S-BiGAT
are stochastic models that can generate multiple socially acceptable future
paths. The ADE and FDE of these methods are evaluated using 20 samples. The
S-LSTM and SGAN adopt pooling mechanisms to model social interactions. As
classic baselines, the results of these two models are not as well as other
recent methods.

Different from S-LSTM and SGAN models, Sophie, S-BiGAT, SR-LSTM, and ST-
Attention adopt attention mechanism to model social interactions. Besides
this, Sophie and S-BiGAT take advantage of scene information to model the
interactions between human and scene. While the scene information was not used
in our model, its prediction performance was best on the ETH-univ and ETH-
hotel datasets. Furthermore, the average ADE(FDE) of our model on the five
datasets was reduced by 16.67%(19.13%) and 6.25%(7%), respectively, compared
with the two models. SR-LSTM and ST-Attention only utilize attention mechanism
to model human-human interactions. The proposed model performs better than SR-
LSTM and ST-Attention on the ETH-univ, ETH-hotel and UCY-zara01 datasets.
Besides, the average ADE and FDE of the five datasets is also better.

It is worth noting that only RSBG and our model regard social relationship as
an impact factor of social interaction. RSBG introduces social related
annotations and uses 0/1 to represent whether two pedestrians are in the same
group. In contrast, our model acquire the representation of social
relationship of each pair of pedestrians through a social relationship encoder
from their relative positions. Due to the existence of stationary crowd groups
in UCY-zara02 video, the RSBG model has the best performance on this dataset.
But our model has better performance on the remaining datasets.

####  4.1.2 Inference Speed and Model Size

Table 2 lists out the speed comparisons between our model and publicly
available models which we could bench-mark against. The size of SRA-LSTM is
67.1K parameters. SGAN 14  has the smallest model size with 46.4k parameters,
which is about seven tenth of the number of parameters in SRA-LSTM. The size
of SR-LSTM is 64.9K parameters which is very close to the number of parameters
in SRA-LSTM. In terms of inference speed, SR-LSTM was previously the fastest
method with an inference time of 0.0049 seconds per inference step. The
inference time of our model is 0.0045 seconds per inference step which is
about 1.09x faster than SR-LSTM.

Table 2: Parameters size and inference time of different models compared to ours. The lower the better. Models were bench-marked using Nvidia GTX2080Ti GPU. The inference time is the average of several single inference steps. We notice that SRA-LSTM has the least inference time compared to others despite it has the most parameters. The text in blue show how many times our model is faster than others. | Parameters count | Inference time
---|---|---
SGAN 14  |  46.4K (0.69x) | 0.0057 (1.27x)
SR-LSTM 33  | 64.9K (0.97x) | 0.0049 (1.09x)
SRA-LSTM | 67.1K | 0.0045

###  4.2 Ablation Study

In order to further illustrate the effectiveness of social relationship
attention and the rationality of the key parameter settings of our model, we
conduct ablation experiments. Our ablation experiments are also evaluated on
the above five subsets, in terms of ADE and FDE. For each ablation experiment,
we strictly control all the hyper-parameters to be consistent.

####  4.2.1 Ablation Study of Different Attention Mechanisms

In pedestrian trajectory prediction, pedestrian’s motion decisions are
affected by the scene layout and surrounding pedestrians’ movement.
Pedestrians with different distances, different social relationships, and
different motion will have different influence on the target pedestrian’s
decision-making. Therefore, it is necessary to use attention mechanism to
model social interaction. In our approach, we present a novel attention called
”Social Relationship Attention(SRA)” which is acquired by coupling the latent
motions of pedestrians and social relationship among them. We verify the
effectiveness of social relationship attention through ablation study of
different attention Mechanisms. Table 3 shows the comparison of different
attention methods. Column 2 in the table shows the trajectory prediction
results with no attention. The soft attention 15  denoted as SA is captured by
the latent motions of the target pedestrian and his/her neighbor. We also
adopt the SA to model social interactions in our comparison. Beside this, RA
represents the attention in 33  which is acquired from relative position and
hidden states. According to the statistical results, the trajectory prediction
based on SRA achieved the lowest ADE and FDE on ETH-univ, ETH-hotel, UCY-
zara01, and UCY-univ datasets. As for the average ADE and FDE on the five
datasets, the average ADE(FDE) of SRA is reduced by 13.46%(23.94%) and
11.76%(14.68%) compared to SA and RA. And compared with the model with no
attention, the average ADE(FDE) of SRA-LSTM is reduced by 11.76%(15.45%).

Table 3: Quantitative results of different types of attention methods in social attention module Dataset | Attention type
---|---
Non | SA | RA | SRA
ETH-univ | 0.69 / 1.38 | 0.64 / 1.27 | 0.67 / 1.35 | 0.59 / 1.16
ETH-hotel | 0.45 / 0.99 | 0.45 / 0.96 | 0.44 / 0.91 | 0.29 / 0.56
UCY-zara01 | 0.48 / 1.05 | 0.45 / 0.98 | 0.44 / 0.98 | 0.37 / 0.82
UCY-zara02 | 0.36 / 0.81 | 0.41 / 0.93 | 0.41 / 0.96 | 0.43 / 0.93
UCY-univ | 0.59 / 1.28 | 0.68 / 1.60 | 0.58 / 1.26 | 0.55 / 0.82
AVG | 0.51 / 1.10 | 0.52 / 1.14 | 0.51 / 1.09 | 0.45 / 0.93
Table 4: Quantitative results of SRA-LSTM model with different parameters. The value of dim1 is the dimention of all embedding vectors. The value of dim2 is the dimention of hidden states of all LSTM cells. Datasets | Key parameter settings |
---|---|---
dim1 | 32 | 32 | 64 | 64
dim2 | 32 | 64 | 64 | 128
ETH-univ | 0.64 /1.25 |  0.59/1.16 | 0.59/1.14 | 0.63/1.23
ETH-hotel | 0.32/0.61 | 0.29/0.56 | 0.31/0.62 | 0.31/0.66
UCY-zara1 | 0.44/0.96 |  0.43/0.93 |  0.43/0.94 | 0.43/0.92
UCY-zara2 | 0.37/0.82 | 0.37/0.82 | 0.36/0.79 | 0.38/0.88
UCY-univ | 0.59/1.27 | 0.55/1.19 | 0.56/1.23 | 0.57/1.26
AVG | 0.47/0.98 | 0.45/0.93 |  0.45/0.94 | 0.46/0.99

####  4.2.2 Ablation Study of Key Parameter Settings

Table 4 shows the comparison of key parameter settings of our SRA-LSTM model.
The dim1 in table represent the dimension of embed vector $e_{ij}^{t}$ in Eq.1
and $e_{i}^{t}$ in Eq.6. The dim2 represent the dimension of hidden states of
all LSTM cells. As shown in Table 4, we list four groups parameter settings of
dim1 and dim2 for ablation study. When dim1 and dim2 set to 32 and 64, the
model achieves an average performance of ADE/FDE = 0.45/0.93 on the five
subsets, which perform better than other parameter settings. The average
ADE/FDE of the four groups of parameter settings is 0.4575/0.9600, and the
standard deviation of ADEs/FDEs is 0.008/0.025. So it is clear that the change
of dimensions has a small impact on the performance of the model. The main
reason for this situation may be that the SRA-LSTM model is stable and robust.

###  4.3 Qualitative Evaluations

As mentioned before, the quantitative results show that SRA-LSTM outperforms
state-of-art models in terms of ADE/FDE metrics. We now qualitatively analyze
how the SRA-LSTM model successfully captures the social interactions. We
compare the performances of SGAN, SR-LSTM, and our model in four common social
scenarios. Besides, we provide comparisons between our model with SR-LSTM in
two different social scenarios of group. Finally, we also analyzed the failure
cases in two different scenarios.

ETH-univ_#4277

ETH-hotel_#10480

UCY-zara1_#3700

UCY-univ_#4380

() Parallel Walking

ETH-univ_#4871

UCY-zara1_#3460

UCY-zara2_#500

UCY-zara2_#6010

(a) People Merging

ETH-univ_#12303

UCY-zara1_#7770

UCY-zara2_#2510

UCY-zara2_#10320

(b) Person Following

ETH-univ_#7823

UCY-zara1_#1030

UCY-zara1_#6890

UCY-univ_#4150

(c) People Meeting

Figure 5: Comparisons of our method with SGAN and SR-LSTM in four common
social scenarios. The examples in each row belong to the same type of social
scenario, from top to bottom: parallel walking, people merging, person
following, and people meeting. For each case, such as ETH-univ_#4277 which is
the scenario of the $4277^{th}$ frame in the ETH-univ dataset, the blue solid
line represents the trajectory of observed 8 key frames, the dashed line is
the trajectory of future 12 key frames (blue: ground truth, yellow: SGAN,
green: SR-LSTM, red: our model).

####  4.3.1 Individual Interaction Scenarios

We consider four types of social scenarios where people have to consider
possible social interactions to avoid collision (see Fig. 5).

Parallel Walking. (Row 1) It is very common for two individuals walking in
parallel in real-scenarios. For example, the behaviors of classmates going to
school together and couples shopping together. There are 4 parallel walking
scenarios from ETH-univ, ETH-hotel, UCY-zara01 and UCY-univ datasets shown in
Fig. 5(). In these scenarios, the trajectories predicted by SRA-LSTM are
closest to ground truth, followed by the SR-LSTM model. For the first
scenario, the SGAN model cannot successfully predict future trajectories. It
is worth noting the fourth scenario, the pair of pedestrians changed their
original directions of movement in future trajectory. The SGAN model and SR-
LSTM model still predict the future trajectories in the original direction of
movement. Our model successfully learned the change of pedestrians’ movement
directions and predicted the future trajectories. Unfortunately, our model
does not learn the speed of pedestrian’s movement that the predicted position
of the final time-step is still a little bit away from ground truth. To a
certain extent, our prediction is still successful.

People Merging. (Row 2) In hallways or on roads, it is common for people
coming from different directions to merge and walk towards a common
destination. People adopt various ways such as walking speed, slow down to
avoid colliding while continuing towards their destinations. As the first
scenario shown in Fig. 5(a), the lower pedestrian walk speed up to avoids
collision with the upper pedestrian. The prediction of SGAN model shows that
the lower person avoid collision by changing the direction of movement, which
is inconsistent with ground truth. The prediction of SR-LSTM model shows that
the lower pedestrian approaches to the upper pedestrian and then adjusts the
direction of movement to move away, which is also inconsistent with ground
truth. We predict the speed behavior and successfully predict the future
trajectory, which closely matches with the ground truth trajectory. In the
other three scenarios, the predicted trajectories by SRA-LSTM also closely
match the ground truth unlike the deviation we see in SGAN and SR-LSTM.

Person Following. (Row 3) People tend to follow the people in front when
walking toward a common destination. But if the person in front walks slowly,
we have to bypass them to reach the destination. For the first scenario shown
in Fig. 5(b), the three pedestrians have the common destination, but the
walking speed of the pair of pedestrians in front is slower than the
pedestrian behind. In this situation, the pedestrian behind chose to pass over
them from the left side of the pair. For the pedestrian behind, the predicted
trajectories of these three models have all detoured, but only our prediction
is close to the ground truth. Although the predicted trajectory does not reach
the specified position, the predicted movement direction is correct. In the
other three scenarios, the trajectories predicted by our model are also the
closest to the ground truth. For the two scenarios in the middle, the
predictions of SGAN and SR-LSTM show that there are various deviations between
the predicted trajectories and ground truth.

People Meeting. (Row 4) On the way to the destination, there will be other
people coming from the opposite direction. For the face-to-face meeting, one
has to adjust the direction of movement temporarily to avoid collision. In
other cases, it is not necessary. As the first scenario shown in Fig. 5(c),
without avoidance, the two pedestrians would pass by. The upper pedestrian’s
trajectories predicted by SGAN and SR-LSTM changed the direction of movement
to avoid collision, which deviated from the ground truth. The trajectory
predicted by our model of this person is closest to the ground truth. But the
predicted trajectories for the lower pedestrian are all shorter than ground
truth. For several other scenarios, our model can always predict the
trajectory closest to ground truth.

####  4.3.2 Group Interaction Scenarios

When there are many pedestrians, they unconsciously form a group, especially
acquaintances. We compare our model with the SR-LSTM model in two common group
scenarios. The scenarios include group walking and group avoiding.

ETH-univ_#10395

UCY-zara1_#7500

ETH-univ_#10395

UCY-zara1_#7500

Figure 6: Scenarios of group walking parallel case. (a) shows the predictions
of SR-LSTM model. (b) shows the predictions of SRA-LSTM model.

UCY-zara1_#1660

UCY-zara2_#1320

UCY-zara1_#1660

UCY-zara2_#1320

Figure 7: Scenarios of group avoiding case. (a)shows the prediction of SR-LSTM
model. (b)shows the prediction of SRA-LSTM model.

Group walking. The common group walking behaviors such as several classmates
going to school together or several friends shopping together. The group
walking scenarios from ETH-univ and ETH-zara01 datasets are shown in Fig. 6.
Column 1 shows the prediction of SR-LSTM model, and column 2 shows the
prediction of our model. For the upper scenario, For the scenario shown in row
1, the trajectories predicted by SR-LSTM show that pedestrians 3 and 4 are
gradually getting closer together, which means that the two collide. Although
there is a deviation between the trajectory predicted by our model and the
ground truth, there is no collision. For the scenario in row 2, there are five
pedestrians walking together. There are various deviations between the
trajectories predicted by SR-LSTM with the ground truth. The same goes for our
predicted trajectories. Although our predicted trajectories also have various
deviations, they are closer to ground truth. It also shows that our predicted
pedestrian’s walking speed is faster than in ground truth.

Group avoiding. There are two scenarios of group avoiding cases shown in Fig.
7. In this scenario, two pairs of pedestrians met from opposite directions.
For the scenario in row 1, pedestrians 1 and 2’s trajectories predicted by our
model are closer to ground truth than SR-LSTM. Pedestrian 3 changed the
direction of movement to avoid collision with pedestrian 2, and pedestrian 4
as a partner of pedestrian 3 also changed. The pedestrian 3’s trajectory
predicted by our model is closer to the ground truth. The trajectories of
pedestrian 4 predicted by the two models are quite different from the ground
truth. For the scenario in row 2, the pair of pedestrians 1 and 2 change the
direction of their movement to avoid collision with the other pair, and then
return to the original direction. Our prediction only changed the direction of
pedestrians 1 and 2, but did not return to the original direction, which is
the reason for the deviation of the prediction trajectory. However, the
predicted trajectory of pedestrian 3 matches with ground truth very well. The
trajectory of pedestrian 4 predicted by SR-LSTM is better than our prediction.

####  4.3.3 Failure Cases Scenarios

The above two subsections show the successful cases of the model in individual
interaction scenarios and group interaction scenarios. However, our model
cannot successfully predict the future trajectory of pedestrians in some
special scenarios. Two failure case scenarios are shown in Fig. 8. The target
pedestrian in Fig. 8(a) walks towards the wall and chooses to stop by the
wall. Our model cannot understand this motivation from the pedestrian’s
observed trajectory, and thus incorrectly predicts the future trajectory. The
reason for the failure case shown in Fig. 8(b) is also that the model cannot
understand the pedestrian’s motivation from the observed trajectory, which
leads to the failure of the prediction. If the model can understand the scene
structure information, the above failure cases may not exist. However, the
thorough solution to the problem lies in accurately understanding the motion
motivation of pedestrians, which is also a difficulty in the trajectory
prediction research. And it is also the goal of our future work.

(a) UCY-zara2_#1320

(b) UCY-zara2_#2730

Figure 8: Scenarios of failure case. The blue solid line represents the
observed trajectory, the yellow dashed line represents groundtruth, and the
red dashed line represents the predicted trajectory.

##  5 Conclusions and Future Work

In this paper, we propose a novel interactive recurrent structure SRA-LSTM for
jointly predicting the future trajectories of pedestrians in the crowd. We
also introduce a social relationship attention, which is acquired from social
relationship representation between pedestrians and their latent motion
patterns. The social relationship attention is adopt to aggregate movement
information from neighbor pedestrians to model social interactions. The
advantage of this method is that it simultaneously takes into account the
impact of potential movement interactions and social relationships on motion
decision. Quantitative evaluations on public datasets prove that our model is
superior to state-of-art models. The qualitative results of some individual
interaction scenarios and group interaction scenarios demonstrate the
effectiveness of our method in social interaction modeling.

Although our SRA-LSTM model outperforms other methods in social interaction
modeling, the scene layout also impacts the movement of pedestrians. In the
future, we will focus on modeling human-scene interactions. We intend to
capture scene layout features from a semantic map of the scene, and then
combine it with human motion information to model the potential interactions
between humans and the scene. We expect to improve the prediction performance
by coupling human-scene interaction with our SRA-LSTM prediction model.
Besides, how to effectively perceive the intentions of pedestrians’ movement
is also a difficult point that we need to solve. This paper focus on
pedestrian trajectory prediction for surveillance video. In the future, we
also hope to study pedestrian trajectory prediction based on the first
perspective in order to apply to robot navigation system.

###### Acknowledgements.

This work is supported by the National Natural Science Foundation of China
(61972128), the Fundamental Research Funds for the Central Universities of
China (Grant No.PA2019GDPK0071).

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * (1) Ahmed SA, Dogra DP, Kar S, Roy PP (2018) Surveillance Scene Representation and Trajectory Abnormality Detection Using Aggregation of Multiple Concepts. Expert Syst Appl 101:43–55. https://doi.org/10.1016/j.eswa.2018.02.013
  * (2) Dai C (2016) Online surveillance object classification with training data updating. In: 2016 international conference on audio, language and image processing (ICALIP), IEEE, Shanghai, pp 733–737. https://doi.org/10.1109/ICALIP.2016.7846535
  * (3) Li X, Huang L, Wei Z, Nie J, Chen Z (2020) Adaptive multi-branch correlation filters for robust visual tracking. Neural Comput Appl 32:5339–5351. https://doi.org/10.1007/s00521-020-05126-9
  * (4) Pereira EM, Ciobanu L, Cardoso JS (2017) Cross-layer classification framework for automatic social behavioural analysis in surveillance scenario. Neural Comput Appl 28:2425–2444. https://doi.org/10.1007/s00521-016-2282-z
  * (5) Al-Smadi M, Abdulrahim K, Seman K, Salam RA (2020) A new spatio-temporal background-foreground bimodal for motion segmentation and detection in urban traffic scenes. Neural Comput Appl 32:9453–9469. https://doi.org/10.1007/s00521-019-04458-5
  * (6) Yaghoubi E, Borza D, Neves JC, Aruna kumar SV (2020) An attention-based deep learning model for multiple pedestrian attributes recognition. Image Vis Comput 101:103981. https://doi.org/10.1016/j.imavis.2020.103981
  * (7) Bouguet JY (2000) Pyramidal implementation of the lucas kanade feature tracker. Intel Corporation Microprocessor Research Labs
  * (8) Helbing D, Molnar P (1998) Social force model for pedestrian dynamics. Phys Rev E 51(5):4282–4286. http://dx.doi.org/10.1103/PhysRevE.51.4282
  * (9) Pellegrini S, Ess A, Schindler K, Gool LJV (2009) You’ll never walk alone: modeling social behavior for multi-target tracking. In: 2015 IEEE international conference on Computer Vision (ICCV), IEEE, Miami, pp 261–268. http://dx.doi.org/10.1109/ICCV.2009.5459260
  * (10) Yi S, Li H, Wang X (2016) Pedestrian behavior modeling from stationary crowds with applications to intelligent surveillance. IEEE Trans Image Proc 25(9):4354–4368. http://dx.doi.org/10.1109/TIP.2016.2590322
  * (11) Yi S, Li H, Wang X (2015) Understanding pedestrian behaviors from stationary crowd groups. In: 2015 IEEE conference on computer vision and pattern recognition(CVPR), IEEE, Boston, pp 3488–3496. http://dx.doi.org/10.1109/CVPR.2015.7298971
  * (12) Hochreiter S, Schmidhuber J (1997) Long Short-term Memory. Neural Comput 9(8):1735–1780. http://dx.doi.org/10.1162/neco.1997.9.8.1735
  * (13) Alahi A, Goel K, Ramanathan V, Robicquet A, Fei-Fei L, Savarese S (2016) Social LSTM: human trajectory prediction in crowded spaces. In: 2016 IEEE conference on computer vision and pattern recognition (CVPR), IEEE, Las Vegas, pp 961–971. http://dx.doi.org/10.1109/CVPR.2016.110
  * (14) Gupta A, Johnson J, Fei-Fei L, Savarese S, Alahi A (2018) Social GAN: socially acceptable trajectories with generative adversarial networks. In: 2018 IEEE conference on computer vision and pattern recognition (CVPR), IEEE, Salt Lake City, pp 2255–2264. http://dx.doi.org/10.1109/CVPR.2018.00240
  * (15) Fernando T, Denman S, Sridharan S, Fookes C (2018) Soft+ hardwired attention: an lstm framework for human trajectory prediction and abnormal event detection. Neural Networks 108:466–478. https://doi.org/10.1016/j.neunet.2018.09.002
  * (16) Vemula A, Muelling K, Oh J (2018) Social Attention: modeling attention in human crowds. In: 2018 IEEE international conference on robotics and automation (ICRA), IEEE, Brisbane, pp 1–7. http://dx.doi.org/10.1109/ICRA.2018.8460504
  * (17) Mohamed A, Qian K, Elhoseiny M, Claudel C (2020) Social-STGCNN: A social spatio-temporal graph convolutional neural network for human trajectory prediction. In: 2020 IEEE/CVF conference on computer vision and pattern recognition (CVPR), IEEE, Seattle, pp 14412–14420. http://dx.doi.org/10.1109/CVPR42600.2020.01443
  * (18) Sun J, Jiang Q, Lu C (2020) Recursive social behavior graph for trajectory prediction. In: 2020 IEEE/CVF conference on computer vision and pattern recognition (CVPR), IEEE, Seattle, pp 657–666. http://dx.doi.org/10.1109/CVPR42600.2020.00074
  * (19) Amirian J, Hayet JB, Pettre J (2019) Social ways: learning multi-modal distributions of pedestrian trajectories with GANs. In: 2019 IEEE international conference on computer vision and pattern recognition (CVPR), IEEE, Long Beach, pp 2964–2972. http://dx.doi.org/10.1109/CVPRW.2019.00359
  * (20) Hu Y, Chen B, Zhang Y, Gu X (2020) Collaborative motion prediction via neural motion message passing. In: 2020 IEEE/CVF conference on computer vision and pattern recognition (CVPR), IEEE, Seattle, pp 6318–6327. http://dx.doi.org/10.1109/CVPR42600.2020.00635
  * (21) Xu Ya, Piao Z, Gao S (2018) Encoding crowd interaction with deep neural network for pedestrian trajectory prediction. In: 2018 IEEE international conference on computer vision and pattern recognition (CVPR), IEEE, Salt Lake City, pp 5275–5284. http://dx.doi.org/10.1109/CVPR.2018.00553
  * (22) Yang B, Yan G, Wang P, Chan C, Liu X, Chen Y (2020) TPPO: a novel trajectory predictor with pseudo oracle. arXiv preprint arXiv:2002.01852https://arxiv.org/abs/2002.01852
  * (23) Lerner A, Chrysanthou Y, Lischinski D (2007) Crowds by example. Comput Graph Forum 26(3):655–664. http://dx.doi.org/10.1111/j.1467-8659.2007.01089.x
  * (24) Xue H, Huynh DQ, Reynolds M (2018) SS-LSTM: A Hierarchical LSTM Model for Pedestrian Trajectory Prediction. In: 2018 IEEE winter conference on applications of computer vision (WACV), IEEE, Lake Tahoe, pp 1186–1194. http://dx.doi.org/10.1109/WACV.2018.00135
  * (25) Li J, Ma H, Tomizuka M (2019) Conditional generative neural system for probabilistic trajectory prediction. In: 2019 IEEE/RSJ international conference on intelligent robots and systems (IROS), IEEE, Macau, pp 6150–6156. http://dx.doi.org/10.1109/IROS40897.2019.8967822
  * (26) Syed A, Morris BT (2019) SSeg-LSTM: semantic scene segmentation for trajectory prediction. In: 2019 IEEE intelligent vehicles symposium (IV), IEEE, Paris, pp 2504–2509. http://dx.doi.org/10.1109/IVS.2019.8813801
  * (27) Lisotto M, Coscia P, Ballan L (2019) Social and Scene-Aware Trajectory Prediction in Crowded Spaces. In: 2019 IEEE/CVF international conference on computer vision workshop (ICCVW), IEEE, Seoul, pp 2567–2574. http://dx.doi.org/10.1109/ICCVW.2019.00314.
  * (28) Choi D, Min K, Choi J (2020) Regularising neural networks for future trajectory prediction via inverse reinforcement learning framework. IET Comput Vis 15(5):192–200. http://dx.doi.org/10.1049/iet-cvi.2019.0546
  * (29) Qing-dao-er-ji R, Su Y, Liu W (2020) Research on the LSTM Mongolian and Chinese machine translation based on morpheme encoding. Neural Comput Appl 32:41–49. https://doi.org/10.1007/s00521-018-3741-5
  * (30) Gupta N, Jalal AS (2019) Integration of textual cues for fine-grained image captioning using deep CNN and LSTM. Neural Comput Appl. https://doi.org/10.1007/s00521-019-04515-z
  * (31) Livieris IE, Pintelas E, Pintelas P (2020) A CNN-LSTM model for gold price time-series forecasting. Neural Comput Appl. https://doi.org/10.1007/s00521-020-04867-x
  * (32) Xu K, Zheng Q, Wang G, Huang K, Ye S, Zhang H (2018) Collision-free LSTM for human trajectory prediction. In: 2018 international conference on multimedia modeling (MMM), Springer, Osaka, pp 106–116. https://doi.org/10.1007/978-3-319-73603-7_9
  * (33) Zhang P, Ouyang W, Zhang P, Xue J, Zheng N (2019) SR-LSTM: state refinement for LSTM towards pedestrian trajectory prediction. In: 2019 IEEE conference on computer vision and pattern tecognition(CVPR), IEEE, Long Beach, pp 12077–12086. http://dx.doi.org/10.1109/CVPR.2019.01236
  * (34) Kosaraju V, Sadeghian A, Martín-Martín R, Reid I, Rezatofighi H, Savarese S (2019) Social-BiGAT: Multimodal trajectory forecasting using Bicycle-GAN and graph attention networks. In: 33rd conference on neural information processing systems (NeurIPS), Curran Associates, Vancouver, pp 137–146
  * (35) Sadeghian A, Kosaraju V, Sadeghian A, Hirose N, Rezatofighi H, Savarese S (2019) SoPhie: An attentive GAN for predicting paths pompliant to social and physical constraints. In: 2019 IEEE conference on computer vision and pattern tecognition(CVPR), IEEE, Long Beach, pp 1349–1358. http://dx.doi.org/10.1109/CVPR.2019.00144
  * (36) Shi X, Shao X, Guo Z, Wu G, Zhang H, Shibasaki R (2019) Pedestrian trajectory prediction in extremely crowded scenarios. Sensors 19(5):1223. https://doi.org/10.3390/s19051223
  * (37) Zhao X, Chen Y, Guo J, Zhao D (2020) A spatial-temporal attention model for human trajectory prediction. IEEE-CAA J Autom 7(4):965–974. https://doi.org/10.1109/JAS.2020.1003228
  * (38) Huang Y, Bi H, Li Z, Mao T, Wang Z (2019) STGAT: modeling spatial-temporal interactions for human trajectory prediction. In: 2019 IEEE conference on computer vision and pattern recognition (CVPR), IEEE, Seoul, pp 6271–6280. http://dx.doi.org/10.1109/ICCV.2019.00637
  * (39) Xue H, Huynh DQ, Reynolds M (2019) Location-velocity attention for pedestrian trajectory prediction. In: 2019 IEEE winter conference on applications of computer vision (WACV), IEEE, Waikoloa Village, pp 2038–2047. http://dx.doi.org/10.1109/WACV.2019.00221
  * (40) Xue H, Huynh DQ, Reynolds M (2020) A location-velocity-temporal attention LSTM model for pedestrian trajectory prediction. IEEE Access 8:44576–44589. https://doi.org/doi:10.1109/ACCESS.2020.2977747
  * (41) Liang Ju, Jiang L, Niebles JC, Hauptmann A, Fei-Fei L (2019) Peeking into the future: Predicting future person activities and locations in videos. In: 2019 IEEE conference on computer vision and pattern recognition workshops (CVPRW), IEEE, Long Beach, pp 5725–5734. http://dx.doi.org/10.1109/CVPRW.2019.00358
  * (42) Leng J, Liu Y, Chen S (2019) Context-aware attention network for image recognition. Neural Comput Appl 31:9295–9305. https://doi.org/10.1007/s00521-019-04281-y
  * (43) Zhu H, Zhang M, Zhang X, Zhang L (2020) Two-branch encoding and iterative attention decoding network for semantic segmentation. Neural Comput Appl. https://doi.org/10.1007/s00521-020-05312-9
  * (44) Ju M, Luo J, Wang Z, Luo H (2020) Adaptive feature fusion with attention mechanism for multi-scale target detection. Neural Comput Appl. https://doi.org/10.1007/s00521-020-05150-9
  * (45) Ji Y, Zhang H, Jie Z, Ma L and Wu QMJ (2020) CASNet: A Cross-attention siamese network for video salient object detection. IEEE Trans Neural Netw Learn Syst. https://doi.org/10.1109/TNNLS.2020.3007534