# Motion-Based Sign Language Video Summarization using Curvature and Torsion

Evangelos G. Sartinas
& Emmanouil Z. Psarakis
& Dimitrios I. Kosmopoulos
&
Department of Computer Engineering and Informatics
University of Patras, Patras, Greece 26504
{sartinas, psarakis<EMAIL_ADDRESS>

###### Abstract

An interesting problem in many video-based applications is the generation of
short synopses by selecting the most informative frames, a procedure which is
known as video summarization. For sign language videos the benefits of using
the $t$-parameterized counterpart of the curvature of the 2-D signer’s wrist
trajectory to identify keyframes, have been recently reported in the
literature. In this paper we extend these ideas by modeling the 3-D hand
motion that is extracted from each frame of the video. To this end we propose
a new informative function based on the $t$-parameterized curvature and
torsion of the 3-D trajectory. The method to characterize video frames as
keyframes depends on whether the motion occurs in 2-D or 3-D space.
Specifically, in the case of 3-D motion we look for the maxima of the harmonic
mean of the curvature and torsion of the target’s trajectory; in the planar
motion case we seek for the maxima of the trajectory’s curvature. The proposed
3-D feature is experimentally evaluated in applications of sign language
videos on (1) objective measures using ground-truth keyframe annotations, (2)
human-based evaluation of understanding, and (3) gloss classification and the
results obtained are promising.

_Keywords_ video summarization, curvature, sign language, Frenet-Serret frame,
torsion.

##  1 Introduction

The Sign Languages (SLs) are typically the main languages used by the Deaf and
by many of the hard-of-hearing (HoH). Due to their poor experiences in spoken
or written languages the Deaf almost always prefer SLs than reading or writing
text [1]. Nowadays, video capturing devices are ubiquitous and play an
important role in the communication and education of the Deaf. A method to
summarize SL videos, without sacrificing the semantics of the performed signs
would offer significant benefits, especially in applications that require
communication over low-bandwidth networks, or content browsing.

In the past, several general-purpose video summarization methods were
presented (e.g., [2], [3], [4]); however those are not applicable in SL
videos, since they treat the video frames holistically, while in the SL videos
only some very specific regions are important for interpretation, while the
rest of the frame is actually less relevant. Such regions are associated with
specific parts of the human body, mainly the hands and face. This fact stands
in stark contrast to holistic summarization methods.

The proposed method may have an impact on research related to the efficient
transmission of SL videos over low-bandwidth networks. It is also expected to
have indirect impact on the analysis of SL, by focusing on the frames where
the most important information is present. This could result in significant
savings in the recognition process, such as by using only a small portion of
the data as input to a classifier.

Sign phonology includes the description of the handshape (hand formation), the
movement, the location and the orientation (palm and fingers). In relation to
the movement [5] notes that the wrist moves through space in order to achieve
a change of location. Furthermore, [6] refer to the sonority of syllables as
the ability of a sign to be perceived at greater distance. Therefore, joints
closer to the body are considered to be higher in the rank of sonority. [7]
proposes a sonority hierarchy as follows: Shoulder - elbow - wrist - base
joints - non-base joints. The above underline the importance of the wrist for
the perceptions of the movement of a sign.

In this work, building upon the ideas presented in [8], we contribute by
introducing a method for efficient summarization of SL videos, based on wrist
motion, that preserves their lexical meaning. Specifically, we use the
$t$-parameterized Frennet-Serret frame to trace the signer’s wrist and
introduce a new informative function based on the curvature and torsion of the
curve. These fundamental features measure how much the trajectory bends as it
evolves and are used to identify the keyframes in the sign language video.

The rest of the paper is structured as follows: Section 2 presents the prior
work. Section 3 contains the problem formulation while in Section 4 the
proposed methodology is presented, which is followed by the experimental
results in Section 5. Finally, Section 6 concludes this paper.

##  2 Related Work

A related line of research deals with the extraction of keyframes from video
content, also called “static summary” (in contrast to “dynamic summary” that
extracts short videos). Many initial approaches used low-level features such
as the color or motion histograms (e.g., [4]), SIFT/SURF (e.g., [3]), or more
recently features from pretrained CNNs [2]. Then the keyframes are typically
extracted using entropy (e.g., [9]) or clustering methods (e.g., [10]). Such
methods mainly use the structural and not the semantic information in the
video; however, they count on the fact that the changes in the structural
frame data (objects) may be associated to semantic changes, which quite often
is true. Some later approaches try to identify the semantic events, which are
of importance, like in sports, e.g., [11] or video surveillance, e.g., [12].
To this end, objects may be identified and tracked.

There have been reported supervised methods, which assume human annotations of
keyframes in training videos, and seek to optimize the frame selection by
minimizing loss with respect to this ground truth. In [13], two LSTMs are used
to select keyframes, by minimizing the cross-entropy loss on annotated ground-
truth keyframes with an additional objective based on determinantal point
process (DPP) to ensure diversity of the selected frames. In our method we
don’t optimize an objective using ground-truth labels, so our method belongs
to the unsupervised ones.

Some of the most recent works in unsupervised summarization exploit the
autoencoder architecture combined with recurrent networks such as the LSTM. In
[14] the auto-encoder is trained using a proposed shrinking exponential loss
function that makes it robust to noise in the web-crawled training data, and
is configured with bidirectional long-short-term memory (LSTM) cells to better
model the temporal structure of highlight segments. In [15] the summarizer is
the autoencoder long short-term memory network (LSTM) aimed at, first,
selecting video frames, and then decoding the obtained summarization for
reconstructing the input video.

Another line of research aims to find some trade-offs for the transmission of
SL videos via low-bandwidth networks without sacrificing comprehensibility.
Video coding systems use the particular structure of SL, i.e., the fact that
the hands and face are the most important and thus need higher quality of
representation, e.g., [16], [17]. Of more relevance to our work is the
laboratory study in [18], which identified the lower threshold for real-time
conversations to be intelligible. The study found that it was possible to hold
a discussion even at a rate of 5fps, although the signers would need to sign
at a slower speed. In the general case, a threshold of 10fps at 50kbps was
found to be satisfactory.

The summarization of SL videos has only been addressed in a few studies. In
[19] the region of hands and face are segmented using skin color and then
modeled using Zernike moments. The second derivative of the moment norm may be
used to extract the keyframes, assuming these are the turning points in the
overall motion. While the method provides reasonable results, the shapes are
often inaccurately represented and calculating higher order moments for better
representation can be demanding. A related method is proposed in [20], where
the keyframes for compressing sign videos and solving sign classification
problems are identified as the frames corresponding to the Maximum Curvature
Points (MCPs) of the global trajectory. However, this feature is invariant to
the motion speed variability that may occur when different persons perform the
same gesture making its use unsuitable for describing the dynamics of the
motion model, which are critical for selecting the keyframes of a gloss.

The use of keyframes in translation and/or classification problems has been
treated in few works related with sign language or action recognition.
Specifically, in [21], a keyframe extraction method, called adaptive clip
summarization where the proposed scheme automatically obtains variable-sized
key frames/clips and implements dynamic temporal pooling on less-important
frames/clips, was used. Then, the compact vectors are considered as
visemes/signemes under respective RGB/skeleton channels.

In [22], the authors, motivated by the observation that consecutive frames are
highly redundant, developed a video-level framework, called temporal segment
network (TSN). This framework extracts short snippets over a long video
sequence with a sparse sampling scheme, where the samples are distributed
uniformly along the temporal dimension. Finally, in [23], the authors extract
key volumes in both temporal and spatial domain, in order to improve the
system’s classification performance. The method identified key volumes
simultaneously with classification.

In contrast to our work, all of these methods are applied to classification or
translation tasks and require training for efficient summarization of SL
videos.

##  3 Problem Formulation

The inability of the human visual system to perceive and track fast motions
has been extensively exploited to reduce the high computational cost in many
applications in the field of computer graphics [24]. This is because the
velocity of motion, which is a fundamental characteristic of movement in
general, strongly affects the intelligibility of sign language.

It is common for videos to have at least one significant object in motion,
often including the camera itself. In a sign language video there are some
frames, which offer clear hand shapes and others that suffer from motion blur.
The blurry frames most often correspond to abrupt hand motion that the camera
struggles to capture, but typically such frames are not semantically
significant [25]. In addition, not all the frames showing sharp handshapes are
essential for the intelligibility of the sign, as they may simply repeat the
same view. Based on this fact, we anticipate that certain keyframes within a
sign are crucial for comprehending its meaning, while the majority of video
frames are not critical at all. This is a rule, rather than an exception in
SLs, that we are going to exploit to extract summaries of SL videos while
preserving their intelligibility.

In order to identify the keyframes of a SL video we are going to introduce a
new feature function, which is based on the harmonic mean of the
$t$-parameterized curvature and torsion of the trace of the signer’s wrist. To
this end, let us define the following pointset:

$\mathbb{P}_{N}=\left\\{\tilde{\mathbf{r}}_{n}\right\\}^{N}_{n=1}$ (1)

with $\tilde{\mathbf{r}}_{n}~{}\in\mathbb{R}^{3}$ denoting the coordinates of
the signer’s wrist at the $n-th$ frame of the video with respect to the
frame’s upper left corner. Note that the aforementioned pointset, denotes the
trace of the signer’s wrist in 3-D Euclidean space $\mathbb{R}^{3}$, as it
moves from its starting (rest) position to its ending one as shown for the
sign in Fig.1a. In order to make mathematics tractable, let us consider that
the elements of the pointset $\mathbb{P}_{N}$ result from sampling the
following 3-D differentiable curve:

$\tilde{\mathbf{r}}(t)=[\tilde{x}(t)~{}\tilde{y}(t)~{}\tilde{z}(t)]^{T},~{}t\in(t_{0},~{}T)$
(2)

that represents the time - parameterized trajectory of a particle as it moves
in the 3-D Euclidean space $\mathbb{R}^{3}$ for the time interval
$[t_{0},~{}T]$. We assume that the velocity vector
$\tilde{\mathbf{r}}^{(1)}(t)$, the acceleration vector
$\tilde{\mathbf{r}}^{(2)}(t)$ and the jerk vector
$\tilde{\mathbf{r}}^{(3)}(t)$ are not proportional to each other. Let $s(t)$
denote the arc length covered by a particle along the curve
$\tilde{\mathbf{r}}(t)$ over the time interval $[t_{0},~{}t]$, that is:

$s(t)=\int_{t_{0}}^{t}||\tilde{\mathbf{r}}^{(1)}_{t}(\tau)||_{2}d\tau,$ (3)

with $||\mathbf{p}(.)||_{2}$ and $\mathbf{p}^{(1)}_{w}(.)$ denoting the
$l_{2}$ norm of 3-D vector function $\mathbf{p}(.)$ and the derivative of the
function $\mathbf{p}()$ with respect to the variable $w$ respectively.

The 3-D curve defined in Eq. (2) can be re-parameterized by its arc length $s$
as:

$\mathbf{r}(s)=[x(s)~{}y(s)~{}z(s)]^{T},~{}s\in[s(t_{0}),~{}s(T)].$ (4)

Note that since the function defined in Eq. (3) is an increasing function of
$t$, its inverse function, let us denote it by $t(s)$, exists and is a well-
defined function. Based on that fact, the $t$ and $s$ parameterized
trajectories, although they are distinct functions, are related by the
following equations: $\tilde{\mathbf{r}}(t)=\mathbf{r}(s(t))$ and
$\mathbf{r}(s)=\tilde{\mathbf{r}}(t(s))$. Note also that by parameterizing the
trajectory of the particle by the arc length, its description does not depend
on the rate quantified by the time derivative of the arc length, i.e.
$s^{(1)}(t)$, in which the particle has traversed it. Proposition 2 proves
that the number of $t$-parameterized trajectories corresponding to the same
$s$-parameterized one defined in Eq. (4) is infinite.

Figure 1: The consecutive frames from rest to rest position corresponding to
the sign “$\kappa\alpha\lambda\eta\mu\acute{\epsilon}\rho\alpha$” (good
morning)

###  3.1 Frenet-Serret Frame

Using the $s$-parameterized trajectory defined in Eq. (4), Frenet-Serret
$\mathbf{tnb}$ frame is defined through the following three orthogonal
vectors:

$\mathbf{t}(s)=\frac{\mathbf{r}^{(1)}_{s}(s)}{||\mathbf{r}^{(1)}_{s}(s)||_{2}},~{}\mathbf{n}(s)=\frac{\mathbf{t}^{(1)}_{s}(s)}{||\mathbf{t}^{(1)}_{s}(s)||_{2}},~{}\mathbf{b}(s)=\mathbf{t}(s)\times\mathbf{n}(s)$
(5)

where $\mathbf{f}^{(1)}_{s}(s)$, “$\times$” denote the derivative of the
vector function with respect to arc length $s$ of the 3-D curve and the cross-
product operator respectively. More precisely, the tangent vector
$\mathbf{t}(s)$ points to the direction the curve travels, the normal vector
$\mathbf{n}(s)$ is orthogonal to the tangent, while binormal vector
$\mathbf{b}(s)$ is orthogonal to the plane defined by the aforementioned pair
of orthonormal vectors, as it can be validated by Eq. (5). Note also that any
pair of the above defined vectors can be used for defining a specific plane;
namely:

  * •

the osculating $\mathbf{t-n}$,

  * •

the normal $\mathbf{n-b}$ and

  * •

the rectifying $\mathbf{b-t}$ respectively.

Based on the orthogonality of the above mentioned vectors, a local, data-
dependent orthonormal basis for the space $\mathbb{R}^{3}$ is derived.

By defining now the matrix function:

$R(s)=[\mathbf{t}(s)~{}\mathbf{n}(s)~{}\mathbf{b}(s)]$ (6)

whose columns contain the above defined unit vector functions, the
$\mathbf{Frenet-Serret}$ frame can be defined by the following differential
equation:

$R^{(1)}_{s}(s)=R(s)C(s)$ (7)

where $X^{(1)}_{s}(s)$, denotes the derivative of the matrix function $X(s)$
with respect to arc length $s$, and matrix $C(s)$ an antisymmetric matrix
which is defined as follows:

$C(s)=\left[\begin{array}[]{ccc}0&-\kappa(s)&0\\\ \kappa(s)&0&-\tau(s)\\\
0&\tau(s)&0\end{array}\right]$ (8)

with $\kappa(s)$, $\tau(s)$ denoting the curvature and the torsion of the
curve respectively.

Note that Frenet-Serret frame can be defined and used for the description of
both 2-D and 3-D curves that are not straight lines; for straight lines the
curvature is equal to zero and the torsion is undefined. Moreover, in the case
of planar (that is 2-D) curves, the torsion is equal to zero; the curvature at
a point of such a differentiable curve is defined as the reciprocal of the
radius of its osculating circle, that is the circle that best approximates the
curve near that point. It is clear that the smaller this circle is the higher
its curvature, with its units being $m^{-1}$ in International System of Units
(SI).

For the 3-D curves, the torsion measures how sharply the curve is twisting out
of the plane of curvature, i.e. the osculating $\mathbf{t-n}$ plane. It has
the same units with the curvature and taken together can be used for the
perfect reconstruction of a 3-D curve.

In order to take into account the existing particularities in the description
of the 2-D and 3-D curves and define an appropriate measure that uses in a
natural manner the above mentioned quantities, using $\mathbf{tnb}$ frame, we
are going to prove the following proposition.

Proposition 1:  Let
$\mathbf{r}_{s}^{(n)}(s),~{}n=1,~{}2,~{}3,~{}||\mathbf{r}^{(1)}_{t}(s(t))||_{2}$
be the $n-$th order derivative of the $s$-parameterized trajectory of the
curve defined in Eq. (4) with respect to its arc length $s$ (that is the
$s$-parameterized counterparts of the velocity, acceleration and the jerk) and
the speed $v(t)$ respectively. Then, the following $s$-parameterized based
relations hold:

$\displaystyle\mathbf{r}^{(1)}_{s}(s)~{}\times~{}\mathbf{r}_{s}^{(2)}(s)$
$\displaystyle=\kappa(s)\mathbf{b}(s)$ (9)
$\displaystyle\left\langle\mathbf{r}^{(1)}_{s}(s)~{}\times~{}\mathbf{r}^{(2)}_{s}(s),~{}\mathbf{r}^{(3)}_{s}(s)\right\rangle$
$\displaystyle=\tau(s)||\mathbf{r}^{(1)}_{s}(s)~{}\times~{}\mathbf{r}^{(2)}_{s}(s)||_{2}^{2},$
(10)

where $\langle\mathbf{x},\mathbf{y}\rangle$ denotes the inner product of the
vectors $\mathbf{x},~{}\mathbf{y}$, and $\kappa(s),~{}\tau(s)$ are the
curvature and torsion respectively.

Proof: The proof of the proposition goes as follows. Let
$\mathbf{r}_{t}^{(1)}\big{(}s(t)\big{)}$ be the derivative of the function
$\mathbf{r}\big{(}s(t)\big{)}$ (that is the composition of functions
$\mathbf{r}(s)$ and $s(t)$) with respect to time variable $t$. Then, using the
chain rule the following relation holds:

$\mathbf{r}^{(1)}_{t}\big{(}s(t)\big{)}=\frac{d\mathbf{r}\big{(}s(t)\big{)}}{dt}=\frac{d\mathbf{r}\big{(}s(t)\big{)}}{ds(t)}\frac{ds(t)}{dt}=\mathbf{r}^{(1)}_{s}\big{(}s(t)\big{)}v(t)$
(11)

where $\mathbf{r}\big{(}s(t)\big{)}$, $v(t)$ denote the $t$-parameterized
counterpart of $\mathbf{r}(s)$ and the speed of the moved particle
respectively. Thus, given that $||\mathbf{r}^{(1)}_{s}(s)||_{2}=1$ (since
$||\mathbf{r}^{(1)}_{t}\big{(}s(t)\big{)}||_{2}=v(t)$), the first component of
the Frenet-Serret frame of Eq. (5) can be rewritten as:

$\mathbf{r}^{(1)}_{s}(s)=\mathbf{t}(s).$ (12)

By differentiating both sides of this relation with respect to the arc length
and using the Frennet-Serret frame defined in Eq. (7), the $s$-parameterized
counterpart of the vector acceleration function can be defined as follows:

$\mathbf{r}^{(2)}_{s}(s)=\kappa(s)\mathbf{n}(s).$ (13)

Note that this function is collinear with the normal vector $\mathbf{n}(s)$ of
the Frenet-Serret frame. Using this relation, Eq. (12) and the definition of
the cross product, the relation (9) of the proposition can be easily obtained.

Let us prove the relation (10) of the proposition. In order to achieve our
goal we differentiate both sides of Eq. (13) with respect to the arc length
$s$ and use again the Frennet-Serret frame defined in Eq. (7) to obtain:

$\mathbf{r}^{(3)}_{s}(s)=-\kappa^{2}(s)\mathbf{t}(s)+\kappa^{(1)}_{s}(s)\mathbf{n}(s)+\kappa(s)\tau(s)\mathbf{b}(s)$
(14)

where $\kappa^{(1)}_{s}(s)$ denotes the first order derivative of the
curvature with respect to the arc length $s$. Note that the $s$-parameterized
counterpart of the jerk function belongs in the 3-D space, i.e.,
$\mathbb{R}^{3}$. Using this relation, Eq. (9), the orthonormality of the
Frennet-Serret frame and the definition of the dot product, the relation (10)
of the proposition can be easily obtained. $\square$

Using Proposition 1, we can define the curvature as well as the torsion by the
following relations:

$\displaystyle\kappa(s)$ $\displaystyle=$
$\displaystyle||\mathbf{r}^{(1)}_{s}(s)~{}\times~{}\mathbf{r}^{(2)}_{s}(s)||_{2}$
(15) $\displaystyle|\tau(s)|$ $\displaystyle=$
$\displaystyle\frac{\left|\left\langle\mathbf{r}^{(1)}_{s}(s)~{}\times~{}\mathbf{r}^{(2)}_{s}(s),~{}\mathbf{r}^{(3)}_{s}(s)\right\rangle\right|}{\kappa^{2}(s)}$
(16)

where $|x|$ denotes the absolute value of the scalar quantity $x$.

It is clear from Eq.(16), that torsion can be defined only when curvature is
strictly positive that is, when the particle’s trajectory does not coincide to
a straight line. From this point on we consider that it holds. Note, as it was
aforementioned, that the units of the quantities defined in Eqs. (15) and (16)
are the same; these quantities are strongly related to the binormal vector
$\mathbf{b}(s)$. The $s$-parameterized curvature $\kappa(s)$ and torsion
$\tau(s)$, as seen from Eqs. (9) and (10), define two different instantaneous
radii for the composite total motion.

Let us concentrate ourselves on the basic drawback of the above defined
$s$-parameterized quantities. It is worth noting that the $s$-parameterized
curvature and torsion remain unchanged despite the particle’s motion, as the
same displacement can be achieved by the particle moving with a constant
velocity, also known as the average velocity, within the same time interval.
This means that the $s$-parameterized curvature and torsion can be considered
as static or shape descriptors, which do not describe the kinematic model of
the particle, and are thus unsuitable for it. Indeed, as it was pointed out in
[8] through the simple but informative case of the circular motion the
$s$-parameterized curvature, that is $\kappa(s)=r^{-1}$, does not depend on
the motion model of the particle.

In the following proposition we prove rigorously a more general result
regarding the $s$ parameterization based 3-D curves, that definitely points to
the aforementioned direction.

Proposition 2:  Let $\tilde{\mathbf{r}}_{1}(t)$ be a $t$-parameterized
trajectory of a particle that is moving into $\mathbb{R}^{3}$ for the time
interval $[t_{0},~{}T]$ and $f(t)$ a continuous and increasing function of $t$
in the same time interval with its initial and final value satisfying
$f(t_{0})=t_{0}$ and $f(T)=T$. Let us also consider that
$\tilde{\mathbf{r}}_{2}(t)=\tilde{\mathbf{r}}_{1}(f(t))$ is the
$t$-parameterized trajectory of the particle resulting from the composition of
the $\tilde{\mathbf{r}}(t)$ with function $f(\cdot)$. Then, their
$s$-parameterized counterparts coincide, i.e.,
$\mathbf{r}_{2}(s)=\mathbf{r}_{1}(s)$.

Proof: For the archlength $s_{2}(t)$ of the second trajectory, we have:

$\displaystyle s_{2}(t)$
$\displaystyle=\int_{t_{0}}^{t}||\tilde{\mathbf{r}}_{2~{}\tau}^{(1)}(\tau)||_{2}d\tau$
$\displaystyle=\int_{f(t_{0})}^{f(t)}||\tilde{\mathbf{r}}_{1~{}f(\tau)}^{(1)}\Big{(}f(\tau)\Big{)}||_{2}df(\tau),$
(17)

and since $f(t_{0})=t_{0}$ the following relation holds:

$s_{2}(t)=s_{1}(f(t)).$ (18)

Let us define now the following inverse functions:

$t_{i}(s)=s_{i}^{-1}(s),~{}i=1,2.$

Based on the monotonicity of the functions $s_{i}(t),~{}i=1,2$ as well as of
the function $f(t)$ the above defined inverse functions are well defined.
Using the definition of the inverse function $t_{1}(s)$ and Eq. (18) the
inverse function $t_{2}(s)$ can be expressed as follows:

$t_{2}(s)=s_{2}^{-1}(s)=f^{-1}\big{(}s_{1}^{-1}(s)\big{)}.$ (19)

The $s$-parameterized trajectories of the particles can now easily obtained.
Indeed, for the first particle we have:

$\mathbf{r}_{1}(s)=\tilde{\mathbf{r}}_{1}\big{(}t_{1}(s)\big{)}=\tilde{\mathbf{r}}_{1}\big{(}s_{1}^{-1}(s)\big{)},$
(20)

while for the second one, using Eq. (19):

$\displaystyle\mathbf{r}_{2}(s)$
$\displaystyle=\tilde{\mathbf{r}}_{1}\Big{(}f\big{(}t_{2}(s)\big{)}\Big{)}$
$\displaystyle=\tilde{\mathbf{r}}_{1}\Big{(}f\big{(}f^{-1}(s_{1}^{-1}(s))\big{)}\Big{)}=\tilde{\mathbf{r}}_{1}\big{(}s_{1}^{-1}(s)\big{)}.$
(21)

From Eqs. (20) and (3.1) we have that $\mathbf{r}_{2}(s)=\mathbf{r}_{1}(s)$
and this concludes the proof of the proposition. $\square$

##  4 The Proposed Solution

To overcome the limitations of the $s$-parameterized curvature and torsion in
representing the kinematic model we propose the use of their $t$-parameterized
counterparts. Let us define the $t$-parameterized counterparts of the Frenet-
Serret $\mathbf{tnb}$ frame defined in Eq. (5) by substituting the arc length
variable $s$ with the function defined in Eq. (3) and defining the following
matrix function:

$\tilde{R}(t)=[\mathbf{t}\big{(}s(t)\big{)}~{}\mathbf{n}\big{(}s(t)\big{)}~{}\mathbf{b}\big{(}s(t)\big{)}]$
(22)

which constitutes the $t$-counterpart of the matrix function defined in Eq.
(6). Then, the $t$ Frenet-Serret $\mathbf{tnb}$ frame can be defined by the
following differential equation:

$R^{(1)}_{t}(t)=\tilde{R}(t)\tilde{C}(t)$ (23)

and the elements of the matrix $\tilde{C}(t)$ that constitute the
$t$-parameterized counterparts of the curvature and torsion, are defined as
follows:

$\displaystyle K(t)$ $\displaystyle=$
$\displaystyle\kappa\big{(}s(t)\big{)}v(t)$ (24) $\displaystyle T(t)$
$\displaystyle=$ $\displaystyle\tau\big{(}s(t)\big{)}v(t)$ (25)

with $v(t)$ denoting the speed of the particle.

It is clear from Eqs. (24) and (25) that the units of the proposed re-
parameterized curvature and torsion are $sec^{-1}$, i.e., Hz and consequently
they can be considered as the instantaneous ordinary frequencies of the
composite motion of the particle as it moves in the 3-D space. As pointed out
in [8], the proposed descriptor not only represents the related shape
information of the trajectory, but also the kinetics, i.e., the dynamics, of
the motion. This is exemplified in the case of planar simple circular motion
where $K(t)=\theta^{(1)}(t)$, where the phase function $\theta(t)$ describes
the motion model of the particle.

Moreover, adopting the proposition of[8], the frames in SL videos that contain
the highest $t$-parameterized curvature, denoted by $K(t)$, can be used as
keyframes to achieve highly compressed videos while maintaining their
intelligibility.

We must stress at this point that the maxima of the $s$-parameterized
curvature $|\kappa(s)|$ was proposed for identifying keyframes in [20] and
this concludes our analysis for the planar (that is 2-D) curves.

###  4.1 3-D Curves - Harmonic Mean of Curvature and Torsion

We propose using the harmonic mean of curvature and torsion as a figure of
merit for selecting the most informative frames in 3-D curves. The harmonic
mean is appropriate for situations when the average of rates is desired [26].
Since the $t$-parameterized quantities represent instantaneous frequencies
closely related to rates, using their harmonic mean is a reasonable choice. In
3-D motion, the torsion $T(t)$ is not zero, and the harmonic mean is defined
as:

$H(t)=\displaystyle{\frac{2K(t)|T(t)|}{K(t)+|T(t)|}}$ (26)

However, when the 3-D motion degenerates to a planar one the $t$-parameterized
Curvature proposed in [8] is adopted, so we have the following cases:

$M(t)=\begin{cases}H(t),&\text{ in the case of 3-D motion}\\\ K(t),&\text{in
the case of 2-D motion.}\end{cases}$ (27)

We seek for maxima of this metric, i.e.:

$M^{(1)}(t)=0~{}~{}\text{and}~{}M^{(2)}(t)<0.$ (28)

The $H(t)$ expresses the reciprocal of the arithmetic mean of the
instantaneous radiuses where the “mean” motion should occur.

Note that in order to chose the most appropriate metric in Eq. (27), first we
have to solve a classification problem regarding to the kind of the particle’s
motion and in particular the dimensionality of its motion. As we are going to
see in the next section, in order to achieve our goal, we adopt a PCA-based
approach in each rest-to-rest (R2R) signing interval.

##  5 Experimental results

This section will present the results obtained by applying our proposed figure
of merit as well as other state-of-the-art techniques [20, 19, 8] to the only
available annotated dataset with keyframes that we are aware of [8].

We will follow an experimental procedure similar to the one described in [8].
It is clear that the first we have to do for the application of the proposed
technique is to detect the appropriate branch in Eq. (27) by classifying the
wrist motion in each signing interval. The hand pose is always measured in 3D,
but its motion can still be planar, or close to planar depending on the
uttered sign. In order to classify a R2R signing interval as planar or non-
planar the 3-D wrist trajectory of the signing interval is fitted with a plane
using PCA. To this end if $\mathcal{S}=\\{\mathbf{r}_{n}\\}_{n=1}^{N}$ is the
set of trajectory points in the R2R signing interval, we form their $3\times
3$ covariance matrix and the fitting error is calculated from the ratio
$\sigma_{3}/(\sigma_{1}+\sigma_{2}+\sigma_{3})$, with $\sigma_{i}$ denoting
the $i$-th singular value of the aforementioned matrix. If the resulting
fitting error is smaller than a predefined value $f_{error}$, then the
trajectory is considered planar and thus the second branch of Eq. (27) is used
with the coordinates of the wrist points projected to the plane defined by the
corresponding first two principal eigenvectors.

Figure 2: The proposed overall summarization framework (dotted box). Its
output is used for the objective measures evaluation (Section 5.2), by
comparing it with the ground truth keyframes, and the creation of the database
for human based evaluation (Section 5.3) and gloss classification (Section
5.4)

###  5.1 Experimental Setup

We evaluated our method in a sign language dataset, which is manually
annotated with keyframes. It was presented for the first time in [8], and is
composed by 32 videos of Greek SL of a total duration of 168 minutes
containing approximately 5500 signs and a vocabulary of 387 unique glosses.
Eight native signers performed four different scripts and were captured from a
Ximea camera with 60 fps. The dataset was annotated by four experts in Greek
SL who selected the least amount of keyframes for each gloss in order to be
fully understandable. The range of the least amount of keyframes for each
gloss was in the interval $[1,~{}10]$.

To assess the performance of the techniques, we compared them in (a) objective
measures using the ground-truth, (b) human-based evaluation of understanding
and (c) gloss classification.

We compared our technique that is based on the metric $M(t)$, against the 2-D
$s$-parameterized curvature $\kappa_{2D}(s)$ [20], the 3-D $s$-parameterized
curvature $\kappa_{3D}(s)$ [20], the Zernike moment - based [19], the 2-D
$t$-parameterized curvature $K_{2D}(t)$ [8] and 3-D $t$-parameterized
curvature $K_{3D}(t)$ that constitutes the 3-D extension of its 2-D
counterpart.

In Fig. 2 the overall proposed framework of summarizing SL video is depicted,
that works for every video frame as follows: the skeleton tracker extracts
among other keypoints the Signer’s dominant wrist position (a) which is used
in turn for the detection of the signing intervals (b) and the calculation of
the curve describing the importance of every frame (c). Finally, the important
frames are selected using the positions, inside the signing intervals, where
the selection curve attains its strongest maxima (d).

For the moments-based technique, we directly used the extrema of the produced
curve instead of its second derivative proposed by the authors [19], because
it performed better in our dataset. The 3-D pointset of the signer’s wrist
trajectory was determined from MediaPipe skeleton tracker [27] and was
smoothed by a Gaussian kernel to eliminate the noise influence occurred from
the wrist detection algorithm. Subsequently, the informative points were
identified, by applying the methods on the dataset. Since every technique
leads to a different curve, whose number of extrema points may differ, we used
the prominence [28] of every critical point as a measure of its importance.
Hence, for a given video for all techniques, the desired number of keyframes
were extracted by selecting the strongest extrema based on their prominence
values. Finally, in all experiments we have conducted the value of the fitting
error $f_{error}$ was set to 5e-2.

###  5.2 Objective Measures Evaluation

We assessed the methods performance by comparing the keyframes that they
selected with the ground truth one as depicted in Fig. 2, using the well-known
Recall rate and $F_{2}$ score. In order to transform the problem at hand into
a binary one, we consider that for each identified keyframe all neighbor
frames that are within a temporal distance less than or equal to an
experimentally defined threshold $\Delta$ are labeled by $1$. Following such a
procedure we obtain a binary label for every video frame we used for the
evaluation. Because of the occurrence of many abrupt motions in SL, the
threshold $\Delta$ in this experiment was set to 5 frames, which corresponds
to 1/12 seconds since the camera frame rate was 60.

The obtained results, in terms of recall and the $F_{2}$ score versus the
ratio $R_{c}$, that is the number of selected keyframes by each technique to
the number of the ones selected by the annotators, are shown in Fig. 3(a) and
(b) respectively. It is evident that the proposed figure of merit outperformed
the other methods. This in turn means that the proposed technique was in
closer $\Delta$ proximity to the ground-truth and thus captured the meaning
more accurately. Indeed, when for example the ratio $R_{c}=1$ the performance
of the proposed $t$-parameterized curvature in terms of the $F_{2}$ score was
4% better than $s$-parameterized one and 3% better than the moment-based
technique. By taking into account the complexity of the problem at hand, we
must stress at this point that the achieved $F_{2}$ score by the proposed
criterion is very promising.

Regarding the Recall rate, comparative results are depicted in Fig. 3(b). The
proposed technique achieved again better Recall rate than the other ones.
Indeed, the proposed technique selected the keyframes in such a way that 57%
of them were in $\Delta$ proximity with the corresponding ones of the
annotators; for the $s$-parameterized curvature and moment-based technique the
corresponding number was 52%.

Finally, in order to quantify the impact of the temporal threshold $\Delta$,
we measured for different values of $\Delta$ the $F_{2}$ score and Recall
rates for $R_{c}=1$ and $R_{c}=2$ (i.e., the amount of keyframes was set to be
equal or twice as much as the ground truth one). The results are shown in Fig.
3(c) and (d). Clearly, both $F_{2}$ score and Recall rate, are increasing
functions of the proximity factor $\Delta$, retaining methods ordering as
well. In addition, as it was expected both metrics are increasing as the ratio
$R_{c}$ increases.

(a)  (b)  (c)  (d)  (e)

Figure 3: Obtained results in terms of (a, c) $F_{2}$ score, (b, d) Recall
rate and (e) relative mean captured sign’s complexity metric $C_{s}$. Versus
$R_{c}$ for $\Delta=5$ (a - b) and versus temporal proximity threshold
$\Delta$ for $R_{c}=1,2$ (c - d)

Note also that for both values of $R_{c}$ and for both objective evaluation
metrics the proposed technique outperforms the other ones. This is more
evident in the Recall rate metric, that can be viewed as the probability that
a relevant keyframe is selected by the technique and whose significance over
Precision, that can be considered as the probability that a keyframe randomly
selected from the pool of total selected keyframes is relevant, has been
indicated from the use of $F_{2}$ score instead of $F_{1}$ in our evaluation.

We also assessed the ability of the summarization methods to capture the
complexity of signs by extracting a reasonable number of keyframes in
comparison to ground-truth. For each sign $\mathcal{S}_{k},~{}k=1,..,N_{S}$,
let us denote by $l_{S_{k}},~{}k=1,..,N_{S}$ the number of keyframes extracted
manually by the Greek SL experts. Let us also denote by
$l_{X_{k}},~{}k=1,..,N_{S}$ the number of the extracted keyframes for each one
of the $\mathcal{S}_{k}$ signs by using any computational method. Then, to
assess the computational method’s ability to capture the complexity of the
signs in our dataset, we used the following $l_{1}$-based metric, i.e.:

$C_{S}=\frac{1}{N_{S}}\sum_{k=1}^{N_{S}}|1-\frac{l_{X_{k}}}{l_{S_{k}}}|$ (29)

Note that, for each technique, the above defined metric quantifies the mean
relative percentage in selecting the same number of keyframes with the
annotator in each gloss. The obtained results in terms of the above defined
metric versus $R_{c}$, are shown in Fig. 3(e). It is evident that the proposed
figure of merit captures in a more effective way the sign’s complexity than
the other techniques do, achieving the lowest mean relative error.

###  5.3 Human-Based Evaluation

In this experiment we evaluated the intelligibility of the extracted summaries
by using human SL experts. We included the human generated summaries to
evaluate subjectivity. The evaluators were given only short videos depicting
isolated signs and not the continuous sentences they were extracted from,
because the latter are generally more easily interpretable due to their
context. Context may lead to more concise summaries, but we left it for future
work. More specifically, the extracted summaries, were used for the
reconstruction of the original videos by repeating every keyframe, until the
occurrence of the next one, so that the reconstructed video would have
approximately the same duration with the original one. Those reconstructed
videos, were evaluated by four expert interpreters in Greek SL who graded the
depicted signs as, understandable (2), semi-understandable (1) and non-
understandable (0).

Semi-understandable were those videos where the phonemic structure of the sign
was not complete. In these videos a path movement or an internal (finger)
movement was missing or an important handshape was missing. However, the
lexical meaning was clear for the observer. The results of the human-based
evaluation in approximately 500 signs of the dataset are shown in Table 1. The
superiority of the proposed technique is evident. The harmonic curvature
outperforms the 2D curvature, but both the 2D and 3D curvature based
techniques have almost the same performance. This suggests that using 3D
curvature as a figure of merit may not be the best approach for solving the
problem. Finally, from Table 1 is clear that the 2-D $t$-parameterized
curvature outperforms its $s$-parameterized counterpart thus validating our
proposition.

Table 1: Human Based Evaluation: Proportion of glosses characterized from SL experts, as Understandable, Semi-Understandable and Non-Understandable from their keyframes |  | Techniques
---|---|---
|  |  Ground Truth |  $M(t)$ |  $K_{2D}(t)$ |  $\kappa_{3D}(s)$ [20] |  $\kappa_{2D}(s)$ [20] |  Moments [19]
Understandable |  0.598 |  0.534 |  0.512 |  0.487 |  0.490 |  0.426
Semi-Understandable |  0.254 |  0.243 |  0.254 |  0.248 |  0.238 |  0.272
Non-Understandable |  0.148 |  0.223 |  0.234 |  0.265 |  0.272 |  0.302

###  5.4 Gloss Classification

In [8], the authors evaluated the effectiveness of various keyframe extraction
techniques, in the gloss classification problem, including the summaries
created by human sign language experts. In this paper we add as a baseline the
case of the full video, i.e., using all the original frames for
classification. To this end, we grouped the selected keyframes by each
technique into glosses and used the available annotation of glosses (including
the start and stop timestamps and the meaning of each gloss) to identify their
meaning in the available data.We used the obtained by MediaPipe keypoints with
the setup described in [8].

The results, measured in terms of top-$N$ accuracy for $N$=1, 2, 5, and 10,
are shown in Table 2. We consider a classification to be top-$N$ accurate if
the true meaning of the gloss appears in the $N$ most probable classes. The
results demonstrate that the keyframes extracted using our proposed criterion
are more effective at identifying the meanings of glosses, as they achieve
higher accuracy scores. These results are promising given the sizeo of the
vocabulary, i.e., 387 possible classes.

Note also that despite the huge difference in compression, the keyframes
selected by the SL professionals outperform the full frames baseline,
indicating the quality of the ground truth.This result also suggests that the
original videos contain many frames that are noisy, e.g., due to blur or due
to intermediate non-semantically significant hand poses; such frames can be
discarded by using properly selected keyframes.

Table 2: Evaluation in classification task in the keyframe skeletal features obtained from proposed and techniques in [20, 19, 8]. | Techniques
---|---
|  Ground Truth |  Full Frames |  $M(t)$ |  $K_{3D}(t)$ |  $K_{2D}(t)$ [8] |  $\kappa_{3D}(s)$ [20] |  $\kappa_{2D}(s)$ [20] |  Moments [19]
Top-1 |  0.56 |  0.52 |  0.44 |  0.42 |  0.43 |  0.39 |  0.39 |  0.38
Top-2 |  0.70 |  0.64 |  0.56 |  0.53 |  0.54 |  0.51 |  0.51 |  0.51
Top-5 |  0.82 |  0.78 |  0.69 |  0.66 |  0.68 |  0.62 |  0.64 |  0.64
Top-10 |  0.88 |  0.85 |  0.76 |  0.73 |  0.73 |  0.69 |  0.73 |  0.73

###  5.5 Ablation Study

How well do the keyframes capture the meaning of sign language glosses? In
this experiment we are going to answer this question via an ablation study.
Specifically, we are going to solve the gloss classification problem under
three different settings, by employing a state-of-the-art deep neural network,
namely; a spatiotemporal graph convolutional neural network (ST-GCNN) [29].

We used the following settings:

  * •

In the first setting, we fed all frames within a specific gloss to the deep
neural network.

  * •

In the second setting, we excluded the keyframes extracted by the annotators,
because these yield the best results in the gloss classification experiment,
and their bilateral ($\pm 5$ frames) neighboring frames.

  * •

Finally, under the third setting, which we consider as the baseline one, we
excluded from the input the same number of randomly selected keyframes and
their bilateral neighbors.

In all cases, we interpolated every gloss to 150 frames to ensure that all
glosses had the same temporal length.

The Top-1 and Top-5 obtained results are shown in Table 3. As it is clear the
interpolation is not effective when keyframes are missing, leading to a
significant drop in classification accuracy. This demonstrates the importance
of keyframes in accurately capturing the meaning of sign language glosses. Our
proposed technique for keyframe extraction, which utilizes both hand keypoints
from mediapipe as features, seems to be effective in this regard.

Table 3: Evaluation of the ground truth keyframes’ importance in
classification’s accuracy using ST-GCN

Accuracy |  Full Frames |  Exclude Random |  Exclude GT Keyframes |  Exclude $K_{2D}(t)$ Keyframes |  Exclude $M(t)$ Keyframes
---|---|---|---|---|---
Top-1 |  0.67 |  0.66 |  0.52 |  0.56 |  0.56
Top-2 |  0.80 |  0.79 |  0.64 |  0.72 |  0.69
Top-5 |  0.88 |  0.88 |  0.77 |  0.84 |  0.80
Top-10 |  0.93 |  0.92 |  0.82 |  0.88 |  0.88

##  6 Conclusions

In this paper, we proposed a new method for identifying keyframes in videos by
using $t$-parameterized curvature and torsion of the 3-D feature motion
extracted from each frame. The proposed figure is the harmonic mean of
$t$-parameterized curvature and torsion in the case of non-planar 3-D motion
of the feature and $t$-parameterized curvature in the planar case, which is
used to determine which frames are the most informative. We applied our
keyframe extraction method to sign language videos, considering that the
moving feature of importance is the signer’s dominant wrist. We evaluated the
proposed feature using objective measures with ground-truth keyframe
annotations, human-based evaluations of understanding, and gloss
classification in Greek Sign Language videos. The results of these experiments
were promising.

##  7 Acknowledgments

The research was co-financed by Greece and EU through the Operational Program
“Human Resource Development, Education and Lifelong Learning”, 2014-2020,
within the framework of the Action ”Strengthening human resources through the
implementation of doctoral research - Action 2: IKY grant program for PhD
candidates of Greek universities”.

## References

  * [1] M. Nikolaraizi, I. Vekiri, and S. R. Easterbrooks, “Investigating deaf students use of visual multimedia resources in reading comprehension,” _American Annals of the Deaf_ , vol. 157, no. 5, p. 458–473, 2013.
  * [2] M. Rochan, L. Ye, and Y. Wang, “Video summarization using fully convolutional sequence networks,” _ArXiv_ , vol. abs/1805.10538, 2018.
  * [3] G. Guan, Z. Wang, K. Yu, S. Mei, M. He, and D. Feng, “Video summarization with global and local features,” in _2012 IEEE International Conference on Multimedia and Expo Workshops_ , July 2012, pp. 570–575.
  * [4] L. Shao and L. Ji, “Motion histogram analysis based key frame extraction for human action/activity representation,” in _2009 Canadian Conference on Computer and Robot Vision_ , May 2009, pp. 88–92.
  * [5] O. Crasborn, “Phonetic implementation of phonological categories in sign language of the netherlands,” _Sign Language & Linguistics, Utrecht: Landelijke Onderzoeksschool Taalwetenschap_, vol. 5, no. 1, 2001.
  * [6] R. Pfau, M. Steinbach, and B. Woll, “Sign language: An international handbook,” _Berlin: De Gruyter Mouton_ , 2012.
  * [7] B. D., “A prosodic model of sign language phonology,” _Cambridge, MA: MIT Press_ , 1998.
  * [8] E. G. Sartinas, E. Z. Psarakis, K. Antzakas, and D. I. Kosmopoulos, “A 2-d wrist motion based sign language video summarization,” _In Proceedings of BMVC_ , 2021.
  * [9] Z. ¯Cerneková, C. Nikou, and I. Pitas, “Entropy metrics used for video summarization,” in _Proceedings of the 18th Spring Conference on Computer Graphics_ , New York, NY, USA, 2002, pp. 73–82.
  * [10] V. Chasanis, A. Likas, and N. Galatsanos, “Efficient video shot summarization using an enhanced spectral clustering approach,” in _Artificial Neural Networks - ICANN_ , V. Kůrková, R. Neruda, and J. Koutník, Eds. Springer, 2008, pp. 847–856.
  * [11] R. Agyeman, R. Muhammad, and G. S. Choi, “Soccer video summarization using deep learning,” in _2019 IEEE Conference on Multimedia Information Processing and Retrieval (MIPR)_ , March 2019.
  * [12] Po Kong Lai, M. Décombas, K. Moutet, and R. Laganière, “Video summarization of surveillance cameras,” in _2016 13th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS)_ , Aug 2016, pp. 286–294.
  * [13] K. Zhang, W.-L. Chao, F. Sha, and K. Grauman, “Video summarization with long short-term memory,” in _ECCV_ , 2016.
  * [14] H. Yang, B. Wang, S. Lin, D. Wipf, M. Guo, and B. Guo, “Unsupervised extraction of video highlights via robust recurrent auto-encoders,” in _Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV)_ , ser. ICCV ’15, 2015, pp. 4633–4641.
  * [15] B. Mahasseni, M. Lam, and S. Todorovic, “Unsupervised video summarization with adversarial lstm networks,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , July 2017, pp. 2982–2991.
  * [16] D. Agrafiotis, N. Canagarajah, D. R. Bull, J. Kyle, H. Seers, and M. Dye, “A perceptually optimised video coding system for sign language communication at low bit rates,” _Signal Processing: Image Communication_ , vol. 21, no. 7, pp. 531 – 549, 2006.
  * [17] D. M. Saxe and R. A. Foulds, “Robust region of interest coding for improved sign language telecommunication,” _IEEE Transactions on Information Technology in Biomedicine_ , vol. 6, no. 4, Dec 2002.
  * [18] J. J. Tran, B. Flowers, E. A. Risken, R. E. Ladner, and J. O. Wobbrock, “Analyzing the intelligibility of real-time mobile sign language video transmitted below recommended standards,” in _Proceedings of the 16th International ACM SIGACCESS Conference on Computers & Accessibility_, ser. ASSETS ’14. New York, NY, USA: ACM, 2014, pp. 177–184.
  * [19] D. I. Kosmopoulos, A. Doulamis, and N. Doulamis, “Gesture-based video summarization,” in _IEEE International Conference on Image Processing 2005_ , vol. 3, Sep. 2005, pp. III–1220.
  * [20] M. Geetha and P. Aswathi, “Dynamic gesture recognition of indian sign language considering local motion of hand using spatial location of key maximum curvature points,” in _2013 IEEE Recent Advances in Intelligent Computational Systems (RAICS)_. IEEE, 2013, pp. 86–91.
  * [21] D. Guo, W. Zhou, A. Li, H. Li, and M. Wang, “Hierarchical recurrent deep fusion using adaptive clip summarization for sign language translation,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 1575–1590, 2020.
  * [22] L. Wang, Y. Xiong, Z. Wang, Y. Qiao, D. Lin, X. Tang, and L. Van Gool, “Temporal segment networks for action recognition in videos,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 41, no. 11, pp. 2740–2755, 2018.
  * [23] W. Zhu, J. Hu, G. Sun, X. Cao, and Y. Qiao, “A key volume mining deep framework for action recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 1991–1999.
  * [24] A. Chalmers, K. Cater, and D. Maflioli, “Visual attention models for producing high fidelity graphics efficiently,” in _Proceedings of the 19th spring conference on Computer graphics_ , 2003, pp. 39–45.
  * [25] M. Dilsizian, P. Yanovich, S. Wang, C. Neidle, and D. Metaxas, “A new framework for sign language recognition based on 3D handshape identification and linguistic modeling,” in _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , May 2014, pp. 1924–1929.
  * [26] W. F. Ferger, “The nature and use of the harmonic mean,” _Journal of the American Statistical Association_ , vol. 26, no. 173, 1931.
  * [27] C. L. et all, “Mediapipe: A framework for building perception pipelines,” _CoRR_ , 2019. [Online]. Available: http://arxiv.org/abs/1906.08172
  * [28] E. Fink and H. S. Gandhi, “Important extrema of time series,” _https://www.cs.cmu.edu/eugene/research/full/important-extrema.pdf_ , 2004\.
  * [29] S. Yan, Y. Xiong, and D. Lin, “Spatial temporal graph convolutional networks for skeleton-based action recognition,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32, no. 1, 2018.


# A non-backtracking method for long matrix completion

Ludovic StephanInformation, Learning and Physics (IdePHICS)École Polytechnique
Fédérale de Lausanne (EPFL<EMAIL_ADDRESS>Yizhe ZhuDepartment of
MathematicsUniversity of California<EMAIL_ADDRESS>
###### Abstract

We consider the problem of rectangular matrix completion in the regime where
the matrix $M$ of size $n\times m$ is “long”, i.e., the aspect ratio $m/n$
diverges to infinity. Such matrices are of particular interest in the study of
tensor completion, where they arise from the unfolding of an odd-order low-
rank tensor. In the case where the sampling probability is
$\frac{d}{\sqrt{mn}}$, we propose a new algorithm for recovering the singular
values and left singular vectors of the original matrix based on a variant of
the standard non-backtracking operator of a suitably defined bipartite graph.
We show that when $d$ is above a Kesten-Stigum-type sampling threshold, our
algorithm recovers a correlated version of the singular value decomposition of
$M$ with quantifiable error bounds. This is the first result in the regime of
bounded $d$ for weak recovery and the first result for weak consistency when
$d\to\infty$ arbitrarily slowly without any polylog factors.

##  1 Introduction

Matrix completion is the problem of reconstructing a matrix from a (usually
random) subset of entries, leveraging prior structural knowledge such as rank
and incoherence. When the two dimensions $n,m$ of the matrix $M$ are
comparable, this problem has been widely studied in the past decades, with a
fairly general pattern emerging. Roughly speaking, if the ground truth matrix
is low-rank and eigenvectors are sufficiently incoherent (or delocalized),
sampling $\Omega(n\log n)$ many entries uniformly at random with a certain
efficient optimization procedure, one can exactly recover the ground truth
matrix [keshavan.montanari.ea_2009_matrix, keshavan2010matrix,
candes.tao_2010_power, candes.plan_2010_matrix, recht2011simpler,
candes2012exact, jain2013low]. This is not the case when the sample size is
only $O(n)$, where full completion is provably impossible. However, an
approximation of the ground truth matrix is still possible
[heiman2014deterministic, gamarnik2017matrix, brito2022spectral] with
efficient algorithms, and more refined estimates of the eigenvectors were
studied in [bordenave2020detection].

In recent years, attention has shifted to “long” matrix models where the row
and column sizes of the matrix are not proportional. This is the case, for
example, in the spiked long matrix and tensor models
[montanari.wu_2022_fundamental, ding.hopkins.ea_2020_estimating,
arous2021long, montanari.richard_2014_statistical]. This situation also occurs
in bipartite clustering and community detection, where the goal is to recover
the community structure in the smaller vertex set [florescu2016spectral,
ndaoud2021improved, cai2021subspace, braun2022minimax] for a bipartite
stochastic block model, and general subspace recovery problems
[cai2021subspace, zhou2021rate] in the sparse setting.

Our work is closely related to tensor completion, which is the higher-order
analog of matrix completion. Indeed, tensor problems are highly related to
their long matrix counterparts through the unfolding operation

$\mathrm{unfold}_{a,b}:\mathbb{R}^{n^{k}}\to\mathbb{R}^{n^{a}\times n^{b}}$
(1)

where $a+b=k$. For example, an order-3 tensor of size $n$ yields an unfolded
matrix of size $n\times n^{2}$; in general, odd-order tensors give rise to
long rectangular matrices. In those tensor problems, the ground truth is
assumed to have a low CP-rank, which implies that the unfolded matrix is low-
rank.

In $k$-tensor completion, the best known polynomial-time algorithms require
$\tilde{O}(n^{k/2})$ revealed entries [jain2014provable,
montanari.sun_2018_spectral, xia2019polynomial, cai.li.ea_2019_nonconvex],
while information theoretically $\tilde{O}(n)$ suffices [ghadermarzy2019near,
harris2021]. In [barak.moitra_2016_noisy], the authors conjectured that for an
order-3 tensor, $\Omega(n^{3/2})$ many samples are needed for any polynomial
algorithms by connecting it to the literature on refuting random 3-SAT. This
is aligned with other tensor estimation problems where a diverging
statistical-to-computational gap is expected
[montanari.richard_2014_statistical, jagannath2020statistical,
arous2020algorithmic, dudeja2022statistical]. However, so far no known work
has reached the exact threshold $\Omega(n^{3/2})$, only approaching it up to
polylogarithmic factors, in a similar fashion to the matrix completion phase
diagram described above.

The applications we mentioned above are related to the same question: can we
improve the sample complexity for estimating a one-sided structure for
singular vectors in a sparse, long matrix? Specifically, we explore the use of
the non-backtracking operator in this context.

The non-backtracking operator of a graph is a powerful tool for understanding
the spectrum of a very sparse random matrix [bordenave2018nonbacktracking,
bordenave2020detection, stephan2020non, bordenave2020new,
bordenave2019eigenvalues, brito2022spectral, benaych2020spectral,
alt2021extremal, alt2021delocalization, dumitriu2022extreme]. In the bipartite
graph setting, the non-backtracking spectrum was analyzed in
[brito2022spectral, dumitriu2022extreme, dumitriu2021spectra] when the two
sides have a bounded aspect ratio. For the spectrum of the adjacency matrix of
a random bipartite graph with a diverging aspect ratio, only a few results
were obtained in [zhu2022second, dumitriu2020global] for random bipartite
biregular graphs, and in [guruswami2022l_p] for the adjacency matrix of
bipartite random graphs with random sign flips.

In this work, we aim to address this gap by defining a non-backtracking
operator that is suitable for sparse matrix estimation with a diverging aspect
ratio. Our work sheds light on the fundamental limits and practical algorithms
for sparse long matrix estimation with a focus on one-sided structure
recovery. To the best of our knowledge, this is the first result for a long
$n\times m$ low-rank matrix completion with sampling probability
$p=\frac{d}{\sqrt{mn}}$ in the regime of bounded $d$ for weak recovery and the
first result for weak consistency when $d\to\infty$ arbitrarily slowly without
any polylog factors. These two types of recovery guarantees are well studied
in the literature of community detection [abbe_2018_community]. In fact, a
direct adaptation of the bipartite non-backtracking operator we define here
leads to a simpler spectral algorithm for the detection of bipartite
stochastic block model beyond the 2-block case studied in
[florescu2016spectral]. The main statements are provided in Section 2, with a
detailed discussion in Section LABEL:sec:discussion.

The non-backtracking operator we define is tailored for the situation where
the underlying sparse bipartite graph has a diverging aspect ratio. It is
similar in spirit to the non-backtracking operator for hypergraphs
[stephan2022sparse], and the nomadic walk operator in [mohanty2020sdp,
guruswami2022l_p]. The main difference compared to [guruswami2022l_p] is that
we work with a non-centered random matrix model, and we only count one-sided
non-backtracking walks. In addition, a detailed eigenvector analysis is
provided while [guruswami2022l_p] is about extreme eigenvalues. Another
relevant work is the estimation of a spiked tensor model under heavy-tail
noise [ding.hopkins.ea_2020_estimating], where the authors connect self-
avoiding walks (a variant of the non-backtracking walk) with low-degree
polynomial methods.

##  2 Setting and main results

###  2.1 Detailed setting

We consider a rectangular matrix $M$ of size $n\times m$, with aspect ratio
$\alpha=m/n$. We write the singular value decomposition of $M$ as

$M=\sum_{i=1}^{n}\nu_{i}\phi_{i}\psi_{i}^{*}$ (2)

where the $\nu_{i}$ are the positive singular values of $M$, and the
$(\phi_{i})_{i\in[r]}$ (resp. the $(\psi_{i})_{i\in[r]}$) are an orthonormal
family of its left (resp. right) singular vectors. We order the singular
values of $M$ in decreasing order, that is

$\nu_{1}\geq\dots\geq\nu_{n}.$

Our observed matrix is of the form

$A=\frac{\sqrt{mn}}{d}(X\circ M),$ (3)

where $X$ is an i.i.d Bernoulli matrix:

$X_{ij}\stackrel{{\scriptstyle i.i.d}}{{\sim}}\
\mathrm{Ber}\left(\frac{d}{\sqrt{mn}}\right).$ (4)

In the following, we will use the shortcut $p=d/\sqrt{mn}$. The scaling of $A$
is chosen so that the expected value of $A$ is exactly $M$.

#### The bipartite non-backtracking operator

We can view the matrix $A$ as the weighted biadjacency matrix of a bipartite
graph $G=(V_{1}\cup V_{2},E)$ with $|V_{1}|=n$, $|V_{2}|=m$. We call $V_{1}$ a
left vertex set and $V_{2}$ a right vertex set. Define the set of _oriented
two-paths_ $\vec{E}$ as

$\vec{E}=\left\\{(e_{1},e_{2},e_{3})\in V_{1}\times V_{2}\times
V_{1}:\\{e_{1},e_{2}\\}\in E,\\{e_{2},e_{3}\\}\in E,e_{1}\neq e_{3}\right\\}.$
(5)

The _bipartite non-backtracking_ operator $B$ associated to $G$ is defined on
$\vec{E}\times\vec{E}$ by

$B_{ef}=\mathbf{1}_{e\to
f}A_{f_{1}f_{2}}A_{f_{3}f_{2}},\quad\text{where}\quad\mathbf{1}_{e\to
f}=\mathbf{1}_{e_{3}=f_{1}}\mathbf{1}_{e_{2}\neq f_{2}}.$ (6)

Equivalently, $\mathbf{1}_{e\to f}$ is one if and only if
$(e_{1},e_{2},e_{3},f_{2},f_{3})$ is a non-backtracking walk of length 4 in
$G$. See Figure 1.

$e_{1}$$e_{2}$$e_{3}$$f_{2}$$f_{3}$ Figure 1: Example of a non-backtracking
path between $(e_{1},e_{2},e_{3})$ and $(f_{1},f_{2},f_{3})$.

###  2.2 Quantifying the convergence

The alignment between the spectrum of $B$ and the SVD of $A$ will be governed
by a wealth of different quantities. For ease of understanding, we separate
those parameters into two categories, depending on their role in the
convergence.

#### Threshold parameters

These parameters describe which parts of the SVD of $M$ will be reflected in
the spectrum of $B$.

  1. (i)

Variance parameter:

$\rho=\lVert Q\rVert,\quad\text{where}\quad Q=\sqrt{mn}(M\circ M).$ (7)

  2. (ii)

Amplitude parameter:

$L=\sqrt{mn}\max_{x\in[n],y\in[m]}|M_{xy}|$ (8)

  3. (iii)

Detection thresholds

$\theta=\max(\theta_{1},\theta_{2}),$ (9)

where the two parameters $\theta_{1}$ and $\theta_{2}$ are defined as

$\theta_{1}=\sqrt{\frac{\rho}{d}}\quad\ $ (10)