# Spatio-Temporal Pyramid Graph Convolutions
for Human Action Recognition and Postural Assessment

Behnoosh Parsa
University of Washington
<EMAIL_ADDRESS>Co-first authors who contributed equally to this work.
This work was done while Behnoosh Parsa was an intern at Honda Research
Institute USA. Athma Narayanan
Honda Research Institute
<EMAIL_ADDRESS>1 Behzad Dariush
Honda Research Institute
<EMAIL_ADDRESS>
###### Abstract

Recognition of human actions and associated interactions with objects and the
environment is an important problem in computer vision due to its potential
applications in a variety of domains. The most versatile methods can
generalize to various environments and deal with cluttered backgrounds,
occlusions, and viewpoint variations. Among them, methods based on graph
convolutional networks that extract features from the skeleton have
demonstrated promising performance. In this paper, we propose a novel Spatio-
Temporal Pyramid Graph Convolutional Network (ST-PGN) for online action
recognition for ergonomic risk assessment that enables the use of features
from all levels of the skeleton feature hierarchy. The proposed algorithm
outperforms state-of-art action recognition algorithms tested on two public
benchmark datasets typically used for postural assessment (TUM and UW-IOM). We
also introduce a pipeline to enhance postural assessment methods with online
action recognition techniques. Finally, the proposed algorithm is integrated
with a traditional ergonomic risk index (REBA) to demonstrate the potential
value for assessment of musculoskeletal disorders in occupational safety.

##  1 Introduction

Human action recognition has been a widely studied research topic in computer
vision for several decades. The task is to infer the human action and activity
from still images or video frames. Solutions to this important and challenging
problem have traditionally been applied to domains such as surveillance,
entertainment, robotics, video retrieval, and intelligent driving assistance
systems [37, 33, 62]. Recently, there are emerging applications that involve
assessment of human performance for virtual fitness, health monitoring,
training, and ergonomic risk assessment for occupational safety [34, 10, 39].
These applications have unique requirements that may involve simultaneous
association of time varying pose with action and object interaction, and
relating such information for computational modeling and prediction of various
biomechanical indicators. Vision only systems are non-invasive and less
expensive alternatives to study these problems as opposed to expensive drift
prone motion capture systems and wearable sensors [32, 5].

Figure 1: Our model (ST-PGN) takes a sequence of skeleton input produced by a
pose extraction unit (like LCR-Net [41]) and does early action recognition.
The skeleton sequence along with the activity labels go to the REBA
computation unit to assess the ergonomic risk while testing.

Depending on the application, human action recognition can be formulated in an
online or off-line setting. In most applications, processing is performed off-
line, making use of the entire video sequence without strict limitations on
computational resources. In such cases, the typical assumption is that the
start and end points of the action is known [9, 31] and the training video is
pre-segmented into various action classes. Recent advances in hardware and GPU
performance has led to the emergence of many online applications, where the
requirement is to process video streams in real-time and without a priori
knowledge of the transitions between actions [28, 29, 49]. Generalization of
action recognition algorithms is a challenging and unsolved problem. Ideally,
the method should generalize to various environments and deal with cluttered
backgrounds, occlusions, and viewpoint variations. While end to end video to
action classification have shown great promise, generalization is achieved
through domain adaptation [11, 2] or using intermediate skeletal
representations that are robust to these variations [58, 40]. In particular,
skeleton-based features appear to produce favorable results since human pose
is typically a consistent representation of action across people and context.
Among them, recent work based on graph convolutional networks that extract
meaningful features from the skeleton have achieved good performance [58, 24].

The work in this paper is inspired by emerging applications involving human
performance assessment in various domains including health, fitness,
rehabilitation, and occupational safety. In particular, we consider specific
challenges for real-time ergonomic risk assessment in complex environments
such as manufacturing assembly. The requirements include correlation of action
with the time varying posture and associated ergonomic and biomechanical risk.
The ultimate goal is to produce reliable estimates of pose, action, and
associated ergonomic indicators in order to identify the risk of
musculoskeletal disorders associated with acute and repetitive tasks.

To achieve this goal, we propose a novel real-time Spatio-Temporal Pyramid
Graph Convolutional Network (ST-PGN) for action recognition that enables the
use of features from all levels of the skeleton feature hierarchy. We tested
the performance of the algorithm on two public benchmark datasets typically
used for postural assessment (TUM and UW-IOM) as well as Kinetics and NTU-RGBD
datasets. The main contributions of this paper are as follows: First, we
demonstrate the efficacy of the ST-PGN algorithm by achieving high recognition
performance on long video sequences as well as the common public benchmarks.
We show that the algorithm is also able to learn the transitions between
actions and is suitable for real-time applications. Second, as compared to the
state-of-the-art algorithms such as ST-GCN [58], our model has fewer graph
convolution kernels without sacrificing performance. Third, the feature
pyramid architecture enables the proposed model to automatically capture the
correlation between body parts, rather than hand-coding body-part relations.
Finally, we introduce a pipeline to enhance postural assessment methods with
online action recognition techniques. The proposed ST-PGN algorithm is
integrated with a traditional ergonomic risk index (REBA) [13] to demonstrate
the potential value for assessment of musculoskeletal disorders in
occupational safety.

##  2 Related Work

Given the recent advances in obtaining accurate pose through depth sensing or
vision based pose estimation algorithms, skeleton based action recognition
methods have become vital for achieving generalization across a variety of
environments [41]. Skeleton based methods also offer opportunity to study down
stream applications that involve human performance analysis and require
postural assessment. We summarize work related to the proposed ST-GPN
algorithm for association of action, posture, and ergonomic risk. This section
surveys the literature in action classification, graph convolution and
ergonomic risk assessment. To the best of our knowledge this is the first work
that combines the three separately studied problems jointly and in an online
fashion.

###  2.1 Action classification

Video action segmentation tasks such as [45, 51, 61, 54, 4, 53, 58] focus on
localizing action labels in untrimmed videos or classifying entire video clips
with one label. Evaluation is generally performed on large scale datasets such
as [50, 20, 16, 4]. Variations of temporal convolutions outperform
conventional recurrent networks in these tasks [1, 21] since they are capable
of aggregating motion changes and long term temporal windows of past and
future frames. Extending these models to an ongoing, partially observed, and
multi-action sequence, such as in online ergonomic risk assessment, is
unclear. Hence, we focus on models and datasets (TUM [52] and UW-IOM [34])
that translate to ergonomic risk assessment datasets that contain repetitive
actions that are closely tied to activities such as manufacturing assembly. As
evidenced by our ST-GCN[58] experiments, these offline models do not translate
well to other online ergonomic action datasets.

Most similar to our work are [28, 29, 49], which address online early action
recognition for indoor datasets such as [25, 27]. However, the focus of those
works is on modelling the temporal evolution of poses and early prediction of
future actions. Rather than predicting future pose streams, our aim is to
instead classify incoming pose streams. It is imperative to capture local
label transitions (reaching to pickup) by exploiting subtle pose cues and
temporal sequence understating. Hence, our focus is in designing a
hierarchical architecture that can do these tasks jointly. With advances in
reliable pose estimation models [60, 41, 3], skeleton only action recognition
has gained popularity [59, 58, 22, 47]. Those methods have shown to be robust
to variations in illumination and scene, and are typically context agnostic.

One limitation of previous methods is that they do not contain the necessary
features from scene context or object handling that give more meaning to the
actions (e.g. walking on crosswalk means crossing verses walking indoors,
lifting box vs lifting rod). Using scene only cues limits models from
capturing complex pose dynamics and relative pose structure changes (e.g. hand
moving in relation to torso means reaching for object). In this regard [58]
is, to our knowledge, the first method to operate on a local pose structure
graph. However, our work addresses the sub-problem of online ergonomic-action
classification by exploiting hierarchical spatio-temporal cues jointly. To
focus of our discussion and avoid comparison to plethora of action recognition
work, we compare our models to spatio-temporal models that use GCN.

###  2.2 Graph Convolution Networks

Graph convolution network (GCN) is a powerful method for processing non-
Euclidean spaces [56]. Since the skeleton structure is inherently represented
as a graph with nodes and connections, GCN is increasingly being used for
analyzing human motion for different applications. Spatio-temporal graph
convolutions add another dimension to GCN by applying convolutions over
spatial domain, and temporal convolutions (TCN) over the time domain in a
sequential manner. Most related work in skeleton based action recognition
include [58, 17, 24, 47]. The first three papers focus on graph convolution on
temporal skeleton sequences. However, they do not model the hierarchical parts
structure in graphs.

Recently, Kim et al.[17] introduced a two-stream method for human action
recognition. They used a human pose stream based on ST-GCN and an object-
related pose stream which is achieved by training an object detector on the
set of objects of their interest. Similarly, our work attempt to fuse the
object/context features along with pose dynamics. However, we focus on
enhancing the skeleton features and treat objects as features from VGG16. We
propose an alternative strategy for fusion inspired by GRU. The focus is to
avoid confusion between objects handled in the labels (pose configuration for
rod-pickup and box-pickup look similar).

###  2.3 Ergonomic risk assessment

Work-related musculoskeletal disorders (MSDs) are costly, affect all age
groups, and are common in many occupations. MSD is a major contributing factor
to disability, loss of independence, and early retirement. Therefore, many
studies analyze the ergonomic risk to workers, particularly in manufacturing
assembly [36, 48, 6, 42, 38, 30].

Rapid Entire Body Assessment (REBA) [14] and The European Assembly Worksheet
(EAWS) [43] are two common ergonomic risk measures used in the industry. REBA
assigns human posture scores, in the range 1-15, based on joint angles during
an activity. First, a risk score is computed for lower and upper extremities
and those scores are added to the task-related scores such as coupling and
load. EAWS, however, is focused at the activity level, and how it is
performed. Both metrics are traditionally determined visually, by an expert
observing the action.

Li et al. [23] use distributed surveillance cameras and body-mounted motion
sensors to automatically calculate ergonomic risk. Shafti et al. [44] use an
RGB-D camera to understand the safe range for arm motions and give feedback on
the subjects’ performance during welding. Kim et al. [18] use a camera to
monitor and adjust the ergonomic risks of working with power tools in real-
time. Parsa et al. [34], introduced an offline method to segment a video into
semantically meaningful actions and report an ergonomic risk level for each
action. Online ergonomic risk computation provides a real-time assessment
based on the individual’s posture. Improved ergonomic assessment, particularly
for metrics such as EAWS, can be attained by considering not only the posture,
but also the action and object interaction. In this work, we compute REBA
frame-wise and use the recognition predictions to adjust the scores. Our
activity recognition predicts the postures and actions, and identifies object
interactions and the height at which the activity is being performed. Such
information affect the REBA score computation.

##  3 Spatio-Temporal Feature Pyramid Graph Convolution

In this work we introduce Saptio-Temporal Pyramid Graph Convolutional Network
(ST-PGN). ST-PGN models the spatio temporal features of the skeletal structure
using combinations of Pyramidal GCNs (PGNs) and Long-Short-Term-Memory
Units(LSTMs). PGN is a novel way to process non-Euclidean skeletal data in a
hierarchical form. Each feature representation in PGN hierarchy is used as an
input to an LSTM unit to learn the temporal aspect of the input sequence
(shown in Fig.2 and described in Sec. 3.4).

###  3.1 Graph Convolutional Network

Graph convolutional networks (GCN) [63] learn the layer-wise propagation
operation that can be applied on structured data represented by a graph. To
briefly introduce how GCNs work, assume we have an undirected graph with $N$
nodes, a set of edges between nodes, an adjacency matrix
$\mathbf{A}\in\mathbf{R}^{N\times N}$, and a degree matrix
$\mathbf{D}_{ii}=\sum_{j}\mathbf{A}_{ij}$. If
$\mathbf{x}\in\mathbf{R}^{f\times N}$ represents the feature matrix of the
graph ($\mathbf{x}_{i}\in\mathbf{R}^{f}$ is the feature vector of node $i$), a
linear formulation of graph convolution is,

$\mathbf{f}=\hat{\mathbf{D}}^{-\frac{1}{2}}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-\frac{1}{2}}{\mathbf{x}_{i}}^{\top}\mathbf{W},$
(1)

where $\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}$, $\mathbf{I}$ is the identity
matrix and $\mathbf{W}\in\mathbf{R}^{f\times c}$ is the weight matrix. So, if
the input to a GCN layer is $f\times N$ the output would be $N\times c$. As
with any other convolution layer we can have a stack of GCNs each followed by
a nonlinear function (such as ReLU) [19].

In this work, we are following the spatial configuration partitioning
introduced in ST-GCN [58], therefore,
$\hat{\mathbf{A}}=\sum_{a}\mathbf{A}_{a}$ and equation 1 is written in a
summation form.

$\mathbf{f}=\sum_{a}\hat{\mathbf{D}}_{a}^{-\frac{1}{2}}\mathbf{A}_{a}\hat{\mathbf{D}}_{a}^{-\frac{1}{2}}{\mathbf{x}}^{\top}\mathbf{W}_{a},$
(2)

Eq. 2 is represented for $k^{th}$ level of the pyramidal hierarchy in line 4
of Algorithm 1. We hypothesize that a hierarchical graph convolution that
operates on human joints, body parts and global structure would enrich the
input representation.

###  3.2 Pyramidal Graph Architecture

Pyramidal Graph Convolutional Network (PGN) is a hierarchical GCN that
produces different spatial features with semantic meaning at different levels.
The input to the PGN is the skeleton with $\mathbf{N}$ joints represented by a
tensor ($\mathbf{X}$) of dimension $F\times N\times T$. Each GCN aggregates
features along the spatial dimension using a specific adjacency matrix
$\hat{\mathbf{A}}_{k}$ using Eq.2. Our PGN has three graph levels
($\hat{\mathbf{A}}_{1}$,$\hat{\mathbf{A}}_{2}$,$\hat{\mathbf{A}}_{3}$). The
initial GCN works on the skeleton with $\hat{\mathbf{A}}_{1}$, which is
constructed based on the skeleton connections and accompanied with an edge-
importance matrix. The subsequent graph levels represent the body parts and
global structure respectively. Since the correlation between the nodes for
higher level graphs is unknown, $\hat{\mathbf{A}}_{2}$ and
$\hat{\mathbf{A}}_{3}$ represent fully connected graphs and we let the edge-
importance learn the correlations.

Thus our model has a hierarchy of graphs with the base as the input skeleton
and the top level a graph with three nodes representing right arm and leg,
left arm and leg, and the head and spine. We refer to this hierarchical graph
structure as a pyramidal graph architecture because it is large at the base
and becomes smaller as we move to the top levels.

###  3.3 Group Average Pool

A Group Average Pool (GAP) layer average-pools the features in a selected
group of nodes/joints using a specific kernel ($\mathbf{J}_{k}$) for each
level (line 5 of Alg. 1). The resulting graph has nodes that represent a
higher level body part (as shown in Fig. 2). Therefore, every layer of the
pyramid has a semantic meaning, from low to high level. In the bottom left
corner of Fig. 2, we show how the groups are defined in TUM and UW-IOM
datasets.

More specifically, feature masking is inspired by [7] which is generally used
in foreground background separation. Here, kernels are pre-determined matrices
with ones or zeros. These kernels are element-wise multiplied by the features
to group only certain body parts one at a time. For example, the kernel has
ones in the particular rows corresponding to those joints representing left
arm ($7,9,11$) and zero everywhere else. Hence, the masked features (features
multiplied by the mask) all belong to the left arm. These features are average
pooled as they belong to the same group. Multiple such combinations are used
to group the joints into different parts. Similarly , parts are combined into
global structure using another set of kernels. Such successive GCN-GAP
combinations allows us to model the entire local and global motions jointly.
We refer to this as the feature update rule (Alg.1), and later in Sec. 3.4, it
is referred to as a bottom-up pathway.

Algorithm 1 Feature Update Rule

1:$\mathbf{X}_{0}\leftarrow\mathbf{X}$$\triangleright$ input skeleton
distributed over time

2:$k\leftarrow 1$$\triangleright$ iterator

3:while $k\leq 3$ do

4: $\mathbf{f}_{k}=\bm{c_{k}}(\mathbf{X}_{k-1};\hat{\mathbf{A}}_{k})$
$\triangleright$ GCN operation

5:
$\mathbf{X}_{k}=\begin{cases}\bm{g_{k}}(\mathbf{f}_{k};\mathbf{J}_{k})&\text{if
$k<3$,}\\\ None&\text{otherwise.}\end{cases}$ $\triangleright$ GAP operation

6: k=k+1
$\triangleright$ The $\mathbf{f}_{k}\forall k\in(1,2,3)$ are used as input
features for the feature pyramid operations in Algorithm 2.

Algorithm 2 Pyramid Update Rule

1:$k\leftarrow 1$$\triangleright$ iterator

2:while $k\leq 3$ do

3: $\mathbf{p}_{k}=$$\begin{cases}\bm{w_{k}}\otimes\mathbf{f}_{k}&\text{if
$k<3$,}\\\ \mathbf{f}_{k}&\text{otherwise.}\end{cases}$ $\triangleright$
$1\times 1$ convolution

4: $\bm{z}_{k}=\begin{cases}\bm{p}_{k}\oplus\bm{u}_{k}(\bm{p}_{k-1})&\text{if
$k<3$,}\\\ \bm{p}_{k}&\text{otherwise.}\end{cases}$

5: $\triangleright$ Upsample & Add

6: k=k+1
$\triangleright$ The Following $\bm{z}_{k}\forall k\in(1,2,3)$ are used as
input features for the temporal modelling using three separate LSTMs.

Symbol | Legend
---|---
$N$ |  Number of 3D Skeleton joints,$(x,y,z)$ tuples
$T$ | Time history of 80 samples
$\mathbf{c}_{k}$ | Graph convolution(GCN) at each hierarchy k
$\hat{\mathbf{A}}_{k}$ | Adjacency matrix at each hierarchy k
$\mathbf{X}_{0}$ |  Input Skeleton feature to first GCN ( $3\times N\times T$)
$\mathbf{g}_{k}$ | Group Average Pool at each hierarchy k
$\mathbf{J}_{k}$ | Pooling kernel at each hierarchy k
$\mathbf{f}_{k}$ |  Output of each GCN ( $3\times N\times F$)
$\mathbf{w}_{k}$ |  $1\times 1$ convolution operation
$\mathbf{u}_{k}$ | Upsample and Add
$\mathbf{p}_{k}$ |  Output of $1\times 1$ convolution
$\mathbf{z}_{k}$ | Final features sent to LSTMs
Table 1: Description of the symbols used in Algorithms

###  3.4 Feature Pyramid Graph Convolutional Network

Feature pyramids have been an important component of object recognition
algorithms [26, 46, 12]. The advantage of using pyramids is that it produces a
multi-scale feature representation in which all feature levels are
semantically strong. Especially in skeleton-based action recognition the
correlation of body-parts can be very informative in recognizing actions.
However, a pre-defined graph might not be sufficient to represent every
sample. For example, in ST-GCN graph, there is no connection between hand and
head, which is important in actions such as eating. Therefore, here we are
generalizing the feature pyramid network to a GCN pyramidal feature hierarchy,
and we believe that learning the correlations at different levels of the
hierarchy enhances the performance of our model. Here feature pyramids are
still valid in skeleton structure as global motion is a combination of local
motion of parts and part motion is a combination of local motion of joints.
Hence our feature pyramids aggregate joints, parts and global features jointly
[57].

The feature pyramid networks consist of two pathways, a bottom-up and a top-
down pathway. The bottom-up pathway is the feed-forward computation of the
backbone GCN, which computes a feature hierarchy consisting of feature maps at
different scales. The top-down pathway produces higher resolution features by
up-sampling spatially larger, but semantically stronger, feature maps from
higher pyramid levels. The top-down path is enhanced by the features produced
in the bottom-up pathway through lateral connections. The features from the
bottom-up pathway undergo a $1\times 1$ conv layer to reduce channel
dimensions and then are merged into the top-down pathway features by element-
wise addition. The purple connections in Fig. 2 shows this process, and it is
described as the pyramid update rule.

###  3.5 Spatio-Temporal Modelling

Now we briefly summarize ST-PGN steps that are described in Algorithm 1-2 and
Fig. 2, and also describe major differences with respect to ST-GCN. The input
skeleton ($\mathbf{X}_{0}$) goes through three levels of GCN and GAP, and the
output of each level ($\mathbf{f}_{k}$) is aggregated with the upsample
features through lateral connection and forms the final features
($\mathbf{z}_{k}$). Each pyramidal feature is passed through separate LSTMs to
create three frame-wise activity predictions. As an ablation study we either
1) average these three predictions and compute one loss or 2) compute three
losses separately and average the predictions while testing. The latter gives
us better performance. As a comparison, in ST-GCN, the input goes through a
sequence of multiple GCN and TCN units so that the final feature embodies
spatial and temporal properties of the input. A final feature that summarizes
spatial and temporal properties is the key for video clip classification.
However, when we need to recognize activities frame-wise, that strategy fails
as will be shown in Sec. 4.3.2. Therefore, we are extracting the spatial
features through PGN and send these features to individual LSTM units so that
the temporal aspect is learned at different spatially semantic layers.

Figure 2: The Feature Pyramid Convolutional Graph Network pipeline.

###  3.6 Ergonomic Risk Assessment

Given the input skeleton ($\mathbf{X}$) and the recognized activity, we
compute REBA. [34] averaged the score over all subjects offline and reported
one score for each activity class. However we compute the score online and
adjust it using the model prediction as shown in Fig. 1. For additional
details on REBA computation, refer to [14].

###  3.7 Optional Fusion Unit

To study the benefit of image features, we also perform experiments with image
features concatenated along with skeleton pose features. We hope to avoid
confusion in situations with object handling. Hence we extract VGG16 features
from a crop image region around the human and fuse them with the final
skeleton feature pyramid. Our fusion unit is inspired by GRU [8], that learns
to weight the features before LSTM. We freeze the weights of the pre-tained
network and only train the fusion unit along with the final LSTM layer. While
the benefit of the image features are very minimal, for completeness, we will
describe the fusion unit below.

At time $t$, let the image features and the final feature pyramid layer
features be denoted by $i_{t}$ and ${z_{1}}_{t}$, respectively. Since the
dimensions of these features do not match, we apply linear weights
($\bm{U_{i}}$, $\bm{U_{z}}$) to transform them into the same dimension and
arrive at the transformed image and skeleton features $I_{t}$ and $S(t)$ as
shown in Eq. 3. The terms $W_{i}$ and $W_{z}$ are learnt weights that are used
to learn a gauging value ($p_{t}$) between the two features similar to the
GRU. The weight $p_{t}$ is squished to take on values $\in[0,1]$ using a
sigmoid operation. Finally this weights are multiplied to the incoming
features.

$\displaystyle I_{t}$ $\displaystyle=\text{relu}(\mathbf{U}_{i}\ast
i_{t}),S_{t}=\text{relu}(\mathbf{U}_{z}\ast{z_{1}}_{t})$ (3) $\displaystyle
p_{t}$ $\displaystyle=\sigma(\mathbf{W}_{i}\ast I_{t}+\mathbf{W}_{s}\ast
S_{t}),$ (4) $\displaystyle\mathbf{O}_{t}$
$\displaystyle=p_{t}I_{t}+(1-p_{t})S_{t}$ (5)

Where, $\mathbf{O}_{t}$ is the weighted feature that is sent as input into one
LSTM unit. For Example, If $p_{t}$ is $0.6$ then the image features ($I_{t}$)
is weighted higher and the skeletal features ($S_{t}$) are weighted lower
($1-0.6=0.4$).

##  4 Experiments

Modalities | Backbones | UW-IOM | TUM
---|---|---|---
mAP (%) | Edit (%) | F1-overlap (%) | mAP (%) | Edit (%) | F1-overlap (%)
Skeleton (only) | Frame based | 39.82 $\pm$ 1.45 | 29.26 $\pm$ 1.32 | 37.87 $\pm$ 1.82 | 29.79 $\pm$ 4.74 | 27.55 $\pm$ 2.89 | 32.63 $\pm$ 4.66
LSTM [15] | 79.35 $\pm$ 4.55 | 77.82 $\pm$ 6.34 | 85.32 $\pm$ 5.37 | 44.24 $\pm$ 5.97 | 56.46 $\pm$ 5.92 | 57.13 $\pm$ 8.24
TCN [1] | 57.72 $\pm$ 6.40 | 56.40 $\pm$ 5.36 | 64.78 $\pm$ 6.38 | 30.61 $\pm$ 5.40 | 51.07 $\pm$ 6.17 | 49.87 $\pm$ 11.01
ED-TCN [21] | 60.05 $\pm$ 4.89 | 81.73 $\pm$ 2.44 | 84.60 $\pm$ 2.64 | 28.89 $\pm$ 5.77 | 56.75 $\pm$ 8.50 | 55.92 $\pm$ 11.11
ST-GCN [58] | 66.94 $\pm$ 3.49 | 61.89 $\pm$ 3.56 | 71.08 $\pm$ 2.83 | 34.73 $\pm$ 5.98 | 53.88 $\pm$ 5.53 | 53.52 $\pm$ 7.09
ST-GCN+IMP [58] | 73.28 $\pm$ 4.30 | 67.21 $\pm$ 6.05 | 76.58 $\pm$ 4.95 | 34.93 $\pm$ 4.75 | 52.27 $\pm$ 3.99 | 52.60 $\pm$ 5.72
GCN+LSTM+IMP | 81.97 $\pm$ 7.34 | 72.25 $\pm$ 7.24 | 82.04 $\pm$ 6.08 | 45.92 $\pm$ 4.19 | 52.07 $\pm$ 4.01 | 55.26 $\pm$ 5.54
ST-PGN+LSTM (ours) | 86.33 $\pm$ 2.71 | 77.92 $\pm$ 2.44 | 86.83 $\pm$ 1.74 | 48.02 $\pm$ 4.68 | 55.31 $\pm$ 5.09 | 57.58 $\pm$ 6.38
ST-PGN+LSTM+IMP (ours) | 85.92 $\pm$ 1.62 | 77.75 $\pm$ 2.46 | 86.21 $\pm$ 1.91 | 42.74 $\pm$ 1.03 | 47.19 $\pm$ 6.39 | 51.14 $\pm$ 6.94
ST-PGN+LSTM+IMP+ML (ours) | 87.03 $\pm$ 2.85 | 97.86 $\pm$ 2.15 | 87.95 $\pm$ 1.54 | 49.62 $\pm$ 6.10 | 56.10 $\pm$ 4.98 | 57.60 $\pm$ 6.03
Image (only) | Frame based | 51.62 $\pm$ 4.12 | 25.60 $\pm$ 1.55 | 34.17 $\pm$ 3.08 | 35.33 $\pm$ 5.26 | 28.33 $\pm$ 1.94 | 35.34 $\pm$ 2.65
LSTM | 66.50 $\pm$ 7.55 | 48.31 $\pm$ 5.90 | 57.81 $\pm$ 6.64 | 49.04 $\pm$ 7.03 | 52.64 $\pm$ 7.50 | 58.60 $\pm$ 7.53
Fusion | Frame based+ Concat | 50.54 $\pm$ 1.55 | 27.57 $\pm$ 0.96 | 36.42 $\pm$ 2.09 | 41.70 $\pm$ 5.76 | 29.66 $\pm$ 1.25 | 36.04 $\pm$ 1.59
LSTM+ Concat | 83.55 $\pm$ 5.74 | 72.98 $\pm$ 7.32 | 77.89 $\pm$ 11.70 | 48.71 $\pm$ 9.42 | 54.86 $\pm$ 6.83 | 57.11 $\pm$ 8.81
ST-PGN+LSTM+IMP+ML+GRU-Fusion (ours) | 87.05 $\pm$ 3.47 | 80.90 $\pm$ 2.06 | 88.08 $\pm$ 1.89 | 57.79 $\pm$ 6.43 | 54.49 $\pm$ 5.59 | 58.35 $\pm$ 9.78

Table 2: mAP, edit, and F1-overlap score represented in mean and standard
deviation over five splits in UW-IOM and TUM datasets for different methods
and modalities. The best results in skeleton and fusion modality are shown in
bold.

###  4.1 Datasets

The skeletal information is required to construct the graph structure and node
features. For our vision only system, we use state of the art 3D skeleton
estimation LCR-Net [41] to estimate poses for the TUM Kitchen and UW-IOM
dataset. While the focus of our work is to evaluate our proposed method on
online ergonomic datasets, we also run experiments on an offline setting for
Skeleton Kinetics and NTU-RGB datasets by substituting ST-GCN with our
network. These experiments and results are provided in the Appendix.
UW-IOM Dataset UW-IOM is a new dataset introduced in [34] with the intention
of capturing activities that are common in warehouses; therefore, videos
consist of three times repetition of a sequence of object manipulation. This
dataset has twenty videos recorded using a Kinect Sensor for at an average
rate of twelve frames per second. The duration of every video is approximately
three minutes. The labels are of four-tier hierarchy, the first tier indicates
the object (box/rod), the second tier denotes human motion (walk, stand, and
bend), the third tier captures the type of object manipulation if applicable
(reach, pick-up, place, and hold), and the fourth tier represents the relative
height of the surface where manipulation is taking place (low, medium, and
high).
TUM Kitchen Dataset The TUM Kitchen dataset [52] consists of nineteen videos
of a sequence of kitchen activities. Four different monocular cameras recorded
the activity of an individual with the rate of twenty-five frames per second
and the average duration of the videos is about two minutes. Some of the
activities we see in these videos are walking, picking up, and placing
utensils to and from cabinets, drawers, and tables. We use the provided two-
tier labels for this dataset by [34], which includes a motion verb (place,
reach, stand), and a location (cabinet, drawer) or object manipulation mode
(both-hands, one-hand). Using these labels, we have twenty-one activity
classes. For our experiments, we choose camera two view alone.

###  4.2 Implementation Details

In our experiments, we sample a fixed length $T$=80 frames from each skeleton
sequence as the input for online experiments. For offline experiments( NTU
dataset and Skeleton Kinetics ) we set the length $T$ = 150 to cover the
entire sequence for one label. We set the batch size to $128$ and $32$ for
online and offline experiments respectively. In order to compare fairly with
ST-GCN, the graph partitioning for the first adjacency matrix
($\hat{\mathbf{A}}_{1}$) is set to the same spatial strategy and partitioned
into 3 subsets: the root node itself, centripetal group, and centrifugal
group. However for the subsequent graphs $\hat{\mathbf{A}}_{2}$ and
$\hat{\mathbf{A}}_{3}$ we assume that fully connected graph as initialization
(all nodes are connected to every other node) and learn the edge importance
weighting.

It should be noted that we do not modify the original ST-GCN model in terms of
number of GCN or parameters. Our final model has only three GCN layers as
opposed to the ten GCN-TCN components. More specifically the first GCN layer
has $64$ channels, second GCN has $128$ and third has $256$ channels. During
training, we use the Adam optimizer [11] to optimize the network. We set the
betas to 0.9 and 0.999 and set weight decay to zero. We split the training and
validation using a five fold split in both TUM and UW-IOM. We report he mean
and variance of all the splits in the results Table 2. We also do a grid
search for learning rate(lr) from 0.1 to 0.001. On an average, lr of 0.05
performs best on all the splits in both datasets.

###  4.3 Results and Discussion

####  4.3.1 Baseline Models

GCN vs Non-GCN Methods. To see the benefit of temporal analysis we perform
experiments that only take skeleton (joint position) or image as input. We use
these feature as inputs of a TCN [1], ED-TCN [21] and LSTM [15] model.
Baselines are trained in an online fashion. We also perform frame based
experiments to determine the efficacy of temporal modelling. It must be noted
that no additional convolution or linear layers are used to transform the pose
inputs.
ST-GCN variants. We showcase the original ST-GCN implementations modified to
support online setting by removing the final average pooling layer. Most ST-
GCN variants used for spatio-temporal modelling, support recursive GCN-TCN
models that pool messages across the overall graph of full skeleton. We also
replace the 1x1 TCN convolutions with LSTMs. We refer to this model as
GCN+TCN. Edge Importance, as in the original work, is also trained and is
showcased as ST-GCN+IMP. LSTMs generally outperforms the TCNs to capture short
transition changes in online fashion. Hence for the following experiments we
choose to use LSTM as a primary temporal modelling source.
ST-PGN variants. Our models are showcased as pyramid-GCN (PGN) models. Similar
to the previous section, we choose to train the edge importance for each of
the sub graphs. The predictions are averaged for ST-PGN+LSTM and ST-
PGN+LSTM+IMP and used to compute a single loss. Alternatively, our final
multi-loss (ML) model has three losses, one for each of the pyramids. These
losses are averaged and propagated during training. During testing the model’s
predictions are averaged and used for evaluation. The results for this model
is shown in Table. 2 under ST-PGN+LSTM+IMP+ML.
Fusion Models. To evaluate the impact of adding contextual features, we use a
fusion mechanism that learns the importance of each feature modalities through
a gauging mechanism ($p_{t}$ in top-left of Fig. 2).

####  4.3.2 Performance Analysis

The UW-IOM dataset focus is on object manipulation tasks that involve picking
up, placing, and carrying objects, as well as walking bending and standing.
Therefore, when we look at the edge importance demonstrations in the top left
of Fig. 3, we see that left hand (L-hand), right hand (R-hand) and right hip
(R-hip) are the most important nodes in the low-level edge importance heat-
map. Also, at the high-level, the importance of arms is higher than the legs
and spine. We achieve an overall +5% improvement in mAP, +2% improvement in
F1-overlap (ST-PGN+LSTM) over the best baseline (GCN+LSTM and LSTM). However,
we see an overall performance boost of +16% in Edit score and similar to our
multi-loss model. Importantly, ST-PGN is more powerful in distinguishing pick-
up and place. These activities are spatially very similar and differ primarily
in temporal aspects. We do not see a huge benefit in Edit score using our
image fusion. However, we see a minor improvement of 1% in the mAP and
F1-overlap.

TUM kitchen dataset also includes object manipulation activities; however, it
is focused on common daily activities in a kitchen. Looking at the low-level
heat-map (top right in Fig.3) we observe that the hand, elbow, shoulder, and
the neck joints have more importance. Looking at the high-level demonstration,
we observe that the arms are more important than the legs and spine. We
observe an overall improvement in mAP and F1-overlap using our models.
However, a simple ED-TCN is slightly better at capturing the sequence and
hence the Edit score is higher. Since the subjects move around in the scene,
the significance of the lower body(legs, hip) is visibly higher in the edge
importance compared to UW-IOM.

The results reported in Tab. 2 show that using skeleton is sufficient to get
equal or better performance as compared to image-only or the fusion of
skeleton and image. In UW-IOM, the human is facing the camera; thus, the
detected skeleton is accurate. However, since this is not the case in the TUM
dataset, the image-based models perform better as compared to the skeleton
only on TUM dataset. If the skeleton is accurate, the addition of the image
does not seem to enhance the results significantly in these tasks.

Figure 3: Three level edge importance heat-map in UW-IOM (shaded) and TUM
datasets. Each row shows the edge importance of each level of graph pyramid
and it is consistent with bottom-left of Fig. 2. Every level of PGCN consists
of the sum of three edge importance multiplied by the adjacency matrix and
node features. Here we are depicting the learned edge importance matrices.

(a) UW-IOM

(b) TUM

Figure 4: Confusion Matrix of ST-PGN+LSTM+IMP+ML model. Larger figures are
added in the Appendix section.

####  4.3.3 Failure Cases

We showcase confusion matrices of our best ST-PGN+LSTM+IMP+ML model, as
described in Figure 4 of the previous section. While we see an overall
performance increase on both UW-IOM and TUM datasets, the model cannot deal
with confusion among similar classes. We showcase the skeleton only model as
adding image features do not help significantly. We describe our insights in
detail below.
UW-IOM Dataset Our models can differentiate between box-handling actions and
rod-handling actions without the use of image features (The skeleton
configuration differs and handling of these objects is distinct due to the
object size and location). However,  Standing and walking misclassifications
occur especially when the subject’s back faces the camera. Hence important
hand motions that help to infer these actions are missed. Better self-
occlusion handling is warranted. Confusion also occurs between bending actions
such as bending-place. This is predominantly due to misclassifications in
transitions between these actions since bending is followed by pickup action
or preceded by place action. Since it is a challenge for human annotators to
accurately label transitions, the edit score should avoid penalizing such
transitions.
TUM Dataset The camera view angle contributes to significant confusion between
related classes. We choose the training-validation split with the lowest mAP
score to analyze the results. The following observations are made:
1) The pickup-drawer and close-drawer are completely misclassified in this
split. Once the drawer is closed, the pose estimation predicted the hand
orientation and location using LCR-Net occlusion strategy [41]. However, the
predicted pose is not always reliable, resulting in poor performance due to
incorrect pose input during training. 2) Walk-not holding is misclassified for
the majority of the classes such as reach-cabinet, reach-drawer, stand-hold-
both-hands, stand-not-hold. This is attributed to unbalanced class
distribution, where most of the actions are walking. In future work, we plan
to address biases introduced by data imbalance by introducing sampling
strategies. 3) Twisting actions are very challenging to detect using vision
only since we only measure poses in Cartesian coordinates. Adding rotation
information should help the model detect twisting actions about certain body
axes. 4) Pickup-hold-both-hands gets confused with either  Pickup-hold-one-
hand or stand-hold-both-hands. Confusion is primarily due to one hand either
being occluded by the object being handled, or the pose configuration being
too similar in pose configuration with standing. More key-points in the pose
prediction models could help resolve such issues.

##  5 Conclusion and Future Work

We proposed a novel Spatio-Temporal Pyramid Graph Convolutional Net-work (ST-
PGN) for online action recognition. The method integrates the following: a)
basic prior knowledge about the skeletal structure, b) hierarchical joint
relationships and c) data-driven learning framework for online action based
ergonomic risk assessment. The proposed approach addresses the simultaneous
association of time-varying pose with action and objects interaction to enable
downstream applications that involve computational modeling and prediction of
various human performance metrics for ergonomic assessment.

Some open issues remain. First, generalization concerning other skeletal joint
representations ( Lie [55], Quaternion [35] ) and camera viewpoint changes has
not been addressed. Furthermore, different actions could share similar pose
configurations, resulting in severe inter-class confusion. In future work, we
hope to address these issues with improved context fusion, long-term temporal
modeling, and biomechanically consistent human pose representations [64].

## References

  * [1] S. Bai, J. Z. Kolter, and V. Koltun.  An empirical evaluation of generic convolutional and recurrent networks for sequence modeling.  arXiv preprint arXiv:1803.01271, 2018.
  * [2] P. P. Busto, A. Iqbal, and J. Gall.  Open set domain adaptation for image and action recognition.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018\.
  * [3] Z. Cao, G. Hidalgo, T. Simon, S.-E. Wei, and Y. Sheikh.  OpenPose: realtime multi-person 2D pose estimation using Part Affinity Fields.  arXiv preprint arXiv:1812.08008, 2018.
  * [4] J. Carreira and A. Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6299–6308, 2017.
  * [5] T. Cloete and C. Scheffer.  Benchmarking of a full-body inertial motion capture system for clinical gait analysis.  In 2008 30th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pages 4579–4582. IEEE, 2008.
  * [6] A. Colim, P. Carneiro, N. Costa, P. M. Arezes, and N. Sousa.  Ergonomic assessment and workstation design in a furniture manufacturing industry—a case study.  In Occupational and Environmental Safety and Health, pages 409–417. Springer, 2019.
  * [7] J. Dai, K. He, and J. Sun.  Convolutional feature masking for joint object and stuff segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3992–4000, 2015.
  * [8] R. Dey and F. M. Salemt.  Gate-variants of gated recurrent unit (GRU) neural networks.  In 2017 IEEE 60th international midwest symposium on circuits and systems (MWSCAS), pages 1597–1600. IEEE, 2017.
  * [9] Y. Du, W. Wang, and L. Wang.  Hierarchical recurrent neural network for skeleton based action recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1110–1118, 2015.
  * [10] X. Guo, J. Liu, and Y. Chen.  Fitcoach: Virtual fitness coach empowered by wearable mobile devices.  In IEEE INFOCOM 2017-IEEE Conference on Computer Communications, pages 1–9. IEEE, 2017.
  * [11] I. Habibie, W. Xu, D. Mehta, G. Pons-Moll, and C. Theobalt.  In the wild human pose estimation using explicit 2d features and intermediate 3d representations.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10905–10914, 2019.
  * [12] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [13] S. Hignett and L. McAtamney.  Rapid entire body assessment (reba).  Applied ergonomics, 31(2):201–205, 2000.
  * [14] S. Hignett and L. McAtamney.  Rapid entire body assessment.  In Handbook of Human Factors and Ergonomics Methods, pages 97–108. CRC Press, 2004.
  * [15] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [16] H. Idrees, A. R. Zamir, Y.-G. Jiang, A. Gorban, I. Laptev, R. Sukthankar, and M. Shah.  The THUMOS challenge on action recognition for videos “in the wild”.  Computer Vision and Image Understanding, 155:1–23, 2017.
  * [17] S. Kim, K. Yun, J. Park, and J. Y. Choi.  Skeleton-based action recognition of people handling objects.  In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 61–70. IEEE, 2019.
  * [18] W. Kim et al.  Adaptable workstations for human-robot collaboration: A reconfigurable framework for improving worker ergonomics and productivity.  IEEE Robot. Autom. Mag., pages 1–1, 2019.
  * [19] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [20] H. Kuehne, H. Jhuang, E. Garrote, T. Poggio, and T. Serre.  HMDB: a large video database for human motion recognition.  In 2011 International Conference on Computer Vision, pages 2556–2563. IEEE, 2011.
  * [21] C. Lea, M. D. Flynn, R. Vidal, A. Reiter, and G. D. Hager.  Temporal convolutional networks for action segmentation and detection.  In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 156–165, 2017.
  * [22] I. Lee, D. Kim, S. Kang, and S. Lee.  Ensemble deep learning for skeleton-based action recognition using temporal sliding lstm networks.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1012–1020, 2017.
  * [23] C. Li and S. Lee.  Computer vision techniques for worker motion analysis to reduce musculoskeletal disorders in construction.  In Comput. Civil Eng., pages 380–387. 2011.
  * [24] M. Li, S. Chen, X. Chen, Y. Zhang, Y. Wang, and Q. Tian.  Actional-structural graph convolutional networks for skeleton-based action recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3595–3603, 2019.
  * [25] Y. Li, C. Lan, J. Xing, W. Zeng, C. Yuan, and J. Liu.  Online human action detection using joint classification-regression recurrent neural networks.  In European Conference on Computer Vision, pages 203–220. Springer, 2016.
  * [26] T.-Y. Lin, P. Dollár, R. Girshick, K. He, B. Hariharan, and S. Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [27] C. Liu, Y. Hu, Y. Li, S. Song, and J. Liu.  Pku-mmd: A large scale benchmark for continuous multi-modal human action understanding.  arXiv preprint arXiv:1703.07475, 2017.
  * [28] J. Liu, A. Shahroudy, G. Wang, L.-Y. Duan, and A. C. Kot.  SSNet: scale selection network for online 3D action prediction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8349–8358, 2018.
  * [29] J. Liu, G. Wang, P. Hu, L.-Y. Duan, and A. C. Kot.  Global context-aware attention LSTM networks for 3D action recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1647–1656, 2017.
  * [30] A. Malaisé, P. Maurice, F. Colas, and S. Ivaldi.  Activity recognition for ergonomics assessment of industrial tasks with automatic feature selection.  IEEE Robotics and Automation Letters, 4(2):1132–1139, 2019.
  * [31] E. Mavroudi, D. Bhaskara, S. Sefati, H. Ali, and R. Vidal.  End-to-end fine-grained action segmentation and recognition using conditional random field models and discriminative sparse coding.  In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1558–1567. IEEE, 2018.
  * [32] A. Mazzoldi, D. De Rossi, F. Lorussi, E. Scilingo, and R. Paradiso.  Smart textiles for wearable motion capture systems.  AUTEX Research Journal, 2(4):199–203, 2002.
  * [33] S. Oh, A. Hoogs, A. Perera, N. Cuntoor, C.-C. Chen, J. T. Lee, S. Mukherjee, J. Aggarwal, H. Lee, L. Davis, et al.  A large-scale benchmark dataset for event recognition in surveillance video.  In CVPR 2011, pages 3153–3160. IEEE, 2011.
  * [34] B. Parsa, E. U. Samani, R. Hendrix, C. Devine, S. M. Singh, S. Devasia, and A. G. Banerjee.  Toward ergonomic risk prediction via segmentation of indoor object manipulation actions using spatiotemporal convolutional networks.  IEEE Robotics and Automation Letters, 4(4):3153–3160, 2019.
  * [35] D. Pavllo, D. Grangier, and M. Auli.  Quaternet: A quaternion-based recurrent model for human motion.  arXiv preprint arXiv:1805.06485, 2018.
  * [36] L. Peppoloni, A. Filippeschi, E. Ruffaldi, and C. Avizzano.  A novel wearable system for the online assessment of risk for biomechanical load in repetitive efforts.  International Journal of Industrial Ergonomics, 52:1–11, 2016.
  * [37] R. Poppe.  A survey on vision-based human action recognition.  Image and vision computing, 28(6):976–990, 2010.
  * [38] G. Possebom, A. dos Santos Alonço, S. D. C. Bellochio, T. G. Lopes, D. P. Carpes, R. S. Becker, A. R. Moreira, T. R. Francetto, F. P. Rossato, and B. C. C. R. Zart.  Comparison of methods for postural assessment in the operation of agricultural machinery.  Journal of Agricultural Science, 10(9), 2018.
  * [39] A. Prati, C. Shan, and K. I.-K. Wang.  Sensors, vision and networks: From video surveillance to activity recognition and health monitoring.  Journal of Ambient Intelligence and Smart Environments, 11(1):5–22, 2019.
  * [40] G. Rogez and C. Schmid.  Mocap-guided data augmentation for 3d pose estimation in the wild.  In Advances in neural information processing systems, pages 3108–3116, 2016.
  * [41] G. Rogez, P. Weinzaepfel, and C. Schmid.  Lcr-net: Localization-classification-regression for human pose.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3433–3441, 2017.
  * [42] A. S. J. Roodbandi, F. Ekhlaspour, M. N. Takaloo, and S. Farokhipour.  Prevalence of musculoskeletal disorders and posture assessment by qec and inter-rater agreement in this method in an automobile assembly factory: Iran-2016.  In Congress of the International Ergonomics Association, pages 333–339. Springer, 2018.
  * [43] K. Schaub, G. Caragnano, B. Britzke, and R. Bruder.  The european assembly worksheet.  Theoretical Issues in Ergonomics Science, 14(6):616–639, 2013.
  * [44] A. Shafti, A. Ataka, B. U. Lazpita, A. Shiva, H. A. Wurdemann, and K. Althoefer.  Real-time robot-assisted ergonomics.  In IEEE Int. Conf. Robot. Autom., 2019.
  * [45] Z. Shou, D. Wang, and S.-F. Chang.  Temporal action localization in untrimmed videos via multi-stage cnns.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1049–1058, 2016.
  * [46] A. Shrivastava, A. Gupta, and R. Girshick.  Training region-based object detectors with online hard example mining.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 761–769, 2016.
  * [47] C. Si, W. Chen, W. Wang, L. Wang, and T. Tan.  An attention enhanced graph convolutional lstm network for skeleton-based action recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1227–1236, 2019.
  * [48] A. K. Singh, M. Meena, H. Chaudhary, and G. Dangayach.  Ergonomic assessment and prevalence of musculoskeletal disorders among washer-men during carpet washing: guidelines to an effective sustainability in workstation design.  International Journal of Human Factors and Ergonomics, 5(1):22–43, 2017.
  * [49] G. Singh, S. Saha, M. Sapienza, P. H. Torr, and F. Cuzzolin.  Online real-time multiple spatiotemporal action localisation and prediction.  In Proceedings of the IEEE International Conference on Computer Vision, pages 3637–3646, 2017.
  * [50] K. Soomro, A. R. Zamir, and M. Shah.  UCF101: A dataset of 101 human actions classes from videos in the wild.  arXiv preprint arXiv:1212.0402, 2012.
  * [51] W. Sultani and M. Shah.  What If We Do Not Have Multiple Videos of the Same Action?–Video Action Localization Using Web Images.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1077–1085, 2016.
  * [52] M. Tenorth, J. Bandouch, and M. Beetz.  The TUM kitchen data set of everyday manipulation activities for motion tracking and action recognition.  In IEEE Int. Conf. Comput. Vis. Workshops, pages 1089–1096, 2009\.
  * [53] D. Tran, L. Bourdev, R. Fergus, L. Torresani, and M. Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In Proceedings of the IEEE international conference on computer vision, pages 4489–4497, 2015.
  * [54] D. Tran, H. Wang, L. Torresani, J. Ray, Y. LeCun, and M. Paluri.  A closer look at spatiotemporal convolutions for action recognition.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 6450–6459, 2018.
  * [55] R. Vemulapalli, F. Arrate, and R. Chellappa.  Human action recognition by representing 3d skeletons as points in a lie group.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 588–595, 2014.
  * [56] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu.  A comprehensive survey on graph neural networks.  arXiv preprint arXiv:1901.00596, 2019.
  * [57] Z. Xu, Z. Liu, C. Sun, K. Murphy, W. T. Freeman, J. B. Tenenbaum, and J. Wu.  Unsupervised Discovery of Parts, Structure, and Dynamics.  2018\.
  * [58] S. Yan, Y. Xiong, and D. Lin.  Spatial temporal graph convolutional networks for skeleton-based action recognition.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [59] P. Zhang, C. Lan, J. Xing, W. Zeng, J. Xue, and N. Zheng.  View adaptive recurrent neural networks for high performance human action recognition from skeleton data.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2117–2126, 2017.
  * [60] H. Zhao, M. Tian, S. Sun, J. Shao, J. Yan, S. Yi, X. Wang, and X. Tang.  Spindle net: Person re-identification with human body region guided feature decomposition and fusion.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1077–1085, 2017.
  * [61] Y. Zhao, Y. Xiong, and D. Lin.  Recognize actions by disentangling components of dynamics.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6566–6575, 2018.
  * [62] W. Zheng, L. Li, Z. Zhang, Y. Huang, and L. Wang.  Relational network for skeleton-based action recognition.  In 2019 IEEE International Conference on Multimedia and Expo (ICME), pages 826–831. IEEE, 2019.
  * [63] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, and M. Sun.  Graph neural networks: A review of methods and applications.  arXiv preprint arXiv:1812.08434, 2018.
  * [64] Y. Zhu, B. Dariush, and K. Fujimura.  Kinematic self retargeting: A framework for human pose estimation.  Computer vision and image understanding, 114(12):1362–1375, 2010\.


# Uniform Sampling and Visualization of 3D Reluctant Walks

Benjamin Buckley Marni Mishna This work is generously funded by NSERC
Discovery Grant (Canada) RGPIN-04157Simon Fraser University
Burnaby, BC, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A family of walks confined to the first orthant whose defining stepset has
drift outside of the region can be challenging to sample uniformly at random
for large lengths. We address this by generalizing the 2D walk sampler of
Lumbroso et al. to handle 3D walks restricted to the first orthant. The
sampler includes a visualizer and means to animate the walks.

Figure 1: _A walk of length 16,778 generated uniformly at random from a
stepset with drift (-1, -1 -1). Progression of the walk is given by hue, with
the initial position at $(0,0,0)$ in red and the final position in magenta._

##  1 Introduction

A combinatorial class of lattice walks is a set of walks, where each step is
taken from a finite set of possibilities, and that the walks remain within
some region (typically a cone centered at the origin). The simplicity of
lattice walks contributes to their ubiquity. Indeed, many families of discrete
objects have natural bijections to lattice walks models. Visualizations of the
large scale behaviour of uniformly generated random walks can reveal
underlying structure of the walks, and consequently, of related objects.

Here, we will focus on the uniform random generation of 3-D walks confined to
the first orthant ($\mathbb{Z}_{\geq 0}^{3}$), in particular models that are
said to be _reluctant_ because the drift of the stepset (the vector sum) is
outside of the cone. The random sampling algorithm naturally extends the 2D
sampling algorithm for reluctant walks of Lumbroso et al. [14]. Fig. 1
illustrates a visualization of a 16,778 step reluctant walk restricted to the
first orthant, (with drift $(-1,-1,-1)$) taken from the Unity interface we
have developed. We have represented the walk steps using blocks, and have
coloured the walk in a way to make its evolution clear.

###  1.1 Motivation

When the stepset has zero drift, naive generation (where steps are drawn at
random, and a walk is rejected once it leaves the region) can be effective.
However, when the drift is outside of the region, particularly when it fits
the criterion (defined below) of being reluctant such a strategy is defeated
by the very small proportion of unrestricted walks that remain in the region.

Some recent asymptotic studies of weighted walk models have provided explicit
examples of complete asymptotic formulas in terms of the weights and have
pointed to some potential sources of interesting phenomena. For example in
both [7], and [15] the authors fix a stepset, and then determine asymptotic
counting formulas as a function of weightings of each allowable step. In both
cases, the exponential growth factor in the dominant term is smooth as a
function of the weights, but the sub-exponential growth is defined piecewise
in terms of the drift of the model. That is to say, as the drift changes the
asymptotic growth formula undergoes phase transitions as the drift crosses
into different regions. One of our motivations is to understand how these
changes influence a uniformly chosen model near these critical drift regimes.
A robust, easy to use visualizer can be useful to identify phenomena that may
subsequently be established analytically or algebraically.

###  1.2 Definitions

To describe the algorithm, we first make some notation explicit. We focus on
finite stepsets $\mathcal{S}\subset\mathbb{Z}^{3}$ with the property that the
defining set of vectors are not contained in any half-space. A walk starts at
the origin, takes steps in $\mathcal{S}$ such that there is no step outside of
the first orthant, $\mathbb{N}^{3}$. Although our random sampler is generic,
in this abstract we present various integer weightings of $\\{\pm e_{1},\pm
e_{2},\pm e_{3}\\}$. In this context a model is reluctant if the drift has all
negative components, that is $\sum_{s\in\mathcal{S}}s\in\mathbb{Z}_{<0}^{3}$.
We also consider weightings that result in a drift outside the first orthant.

##  2 Algorithm

The sampling algorithm we use, like the 2D sampling algorithm of Lumbroso _et
al._ [14] has three key elements. It is a rejection algorithm, but rather than
generating an unrestricted walk, our algorithm generates walks confined to a
judiciously chosen half-space containing the first orthant, and rejects
generated walks if they exit the first orthant. The set of walks confined to a
half space is in bijection with a set of generalized Dyck words, for which a
grammar can be made explicit [9]. Given the grammar, uniform sampling can be
effectively accomplished using a Boltzmann sampler. We visualize the walks in
Unity to give access to an interface, and open the possibility to animation.
Images and videos demonstrating this are available to view at
https://benbuckleyanimator.wixsite.com/portfolio/randwalkviz.

###  2.1 A well chosen half-space

From our restriction on $\mathcal{S}$ we can deduce that there exists a half
space (and possibly many) so that, asymptotically, the number of walks
confined to that half space has the same exponential growth factor as walks
further confined to the first orthant. We say more about this in the example
below, but generically this follows from a result of Garbit and Raschel [12].
This means that the proportion of the walks the half-space that are _not_ in
the first orthant grows sub-exponentially with length.

Since walks confined to a half space only interact with a single boundary,
these walks are in bijection with a one dimensional model. To define this one
dimensional model, the stepset $\mathcal{S}$ is projected onto a vector
$\mathbf{v}=(a,b,1)\in\mathbb{R}^{3}$ orthogonal to the hyperplane defining
the halfspace to create a 1D stepset. We can make this set explicit:
$\mathcal{A}_{\mathbf{v}}=\\{ai+bj+k\mid(i,j,k)\in\mathcal{S}\\}$, with steps
in $\mathbb{R}$. The exponential growth of the asymptotic number of walks in
the first orthant model is the equal to the minimum value of the Laurent
polynomial $S(x,y,z)=\sum_{(i,j,k)\in\mathcal{S}}x^{i}y^{j}z^{k}$ attained in
a suitable domain of $\mathbb{R}_{>0}^{3}$. Suppose the minimum value is
attained at $(x^{*},y^{*},z^{*})$. Provided $z^{*}\neq 1$, we can show that
the 1D model associated to $\mathbf{v}=(a,b,1)$ with
$a=\log(x^{*})/\log(z^{*})$, $b=\log(y^{*})/\log(z^{*})$ is such that the
exponential growth of the asymptotic number of walks in the model is the same
as the orthant model. Remark, that because of our conditions on $\mathcal{S}$
we have $x^{*}y^{*}z^{*}\neq 0$. In the case where $z^{*}=1$, we can project
on to $(a,b,0)$ with $a=\log(x^{*})$ and $b=\log(y^{*})$. If
$x^{*}=y^{*}=z^{*}=1$, then any halfspace containing the orthant can be used.

###  2.2 Generalized Dyck words

The previous process yields a one-dimensional stepset with real valued steps.
In order to create a grammar for a Boltzmann sampler, we need a stepset with
integer valued steps. We find a rational approximation – that is, a stepset
with steps in $\mathbb{Q}$ sharing a small denominator, typically $<10$ for
ease of computation – and then multiply through by the denominators to obtain
a stepset with steps in $\mathbb{Z}$. The closer the approximation, the less
the rejection although we will always generate walks in the orthant uniformly.
In our example, the previous step yields integer steps directly.

Given a finite set of integers, the grammar for 1D walks that do not go below
0 is described in [9]. We have applied to this to our running example in Fig.
2 below.

###  2.3 Boltzmann generation

Given the grammar, the sampling is done using a Boltzmann sampling strategy,
following [10], although any random generating strategy for a grammar could be
used in its place. Here we describe only how we compute some of the required
elements.

Given the grammar, we used Maple’s Combstruct library to solve the algebraic
equations to obtain explicit generating function for these 1-dimensional
walks. It turns out that this is the most difficult step for computational
reasons: when stepset has large integers, the number of rules in the grammar
can grow quickly, potentially inhibiting the computation of the generating
function.

When an explicit generating function is not determined a high order series
approximation is used in the computation.

Given the generating function, we determine its dominant singularity, and in
the case of a series approximation we determine an approximation. Boltzmann
sampling uses generating function evaluations at, or near, this singularity.

Boltzmann sampling can generate objects of any size, but, for a given size the
sampling is uniform. To generate large objects, one uses evaluation points
close to or at the dominant singularity, provided it is not a pole. In these
problems, the singularities are branch points, not poles, and so we can
evaluate directly at the dominant singularities.

###  2.4 Running the algorithm

Thus, in summary, for a given model $\mathcal{S}$, we first have a set up
phase to first determine the best half-space, then generate the corresponding
grammar, and do the computational preamble (generating function evaluations)
for the Boltzmann sampler. To generated a walk, we run the sampler, biject
back to a 3D walk, and eliminate those walks that leave the first orthant. The
preamble is done in Maple, but we run the sampler in Unity.

##  3 Drawn walks

###  3.1 The reluctant model in Fig.1

The walk in Fig. 1 is sampled from the set of walks with the stepset
$\\{e_{1},e_{2},e_{3},-e_{1},-e_{1},-e_{2},-e_{2},-e_{3},-e_{3}\\}$. Note that
this is a multiset with each of the negative steps appearing twice, increasing
their probability. We calculate the drift by taking the vector sum of these
steps, and obtaining $-e_{1}-e_{2}-e_{3}=(-1,-1,-1)$. We note that this model
fits in the framework of Theorem 2 in [15], from which we deduce that the
number of walks of length $n$ grows, up to a constant, like
$(6\sqrt{2})^{n}\,n^{-3}$. Thus, the exponential growth factor is $6\sqrt{2}$.

#### Find the halfspace

The inventory of the stepset is
$S(x,y,z)=\sum_{(i,j,k)\in\mathcal{S}}x^{i}y^{j}z^{k}=x+2/x+y+2/y+z+2/z$. A
gradient computation shows this function is minimized at $\sqrt{2}(1,1,1)$.
The optimal vector is $\mathbf{v}=(a,b,1)$ with
$a=\frac{\log(x^{*})}{\log(z^{*})}$ and $b=\frac{\log(y^{*})}{\log(z^{*})}$,
that is, $\mathbf{v}=(1,1,1)$. The stepset $\mathcal{S}$ is projected onto
this vector to obtain a 1-dimensional stepset with steps in $\mathbb{R}$:

$\displaystyle\mathcal{A}_{\mathbf{v}}=\\{1,1,1,-1,-1,-1,-1,-1,-1\\}.$

Remark that the inventory of this walk is $A(u)=3u+6/u$. Because the drift is
negative, by Banderier and Flajolet [2, Theorem 4], the exponential growth
factor for the walks that are never negative is $A(\tau)$, where $\tau$ is the
critical point of $A(u)$. In this case $A^{\prime}(\sqrt{2})=0$ and
$A(\tau)=2\sqrt{6}$. Furthermore, we know that the number of walks of length
$n$, grows like $(2\sqrt{6})^{n}n^{-3/2}$ (up to a multiplicative constant) We
are assured: This walk has an identical exponential growth factor to the 3D
walks. The proportion of these walks that are images of walks remaining in the
first orthant is approximately $\frac{n^{-3}}{n^{-3/2}}=n^{-3/2}$, for length
$n$.

#### Find the grammar

As the steps are all integer valued, we can proceed directly to the grammar
phase. We use the formulation of grammars for generalized Dyck words, as
described in [9], to obtain a grammar for half-hyperplane walks in our
1-dimensional stepset. Following this specification, we obtain the grammar in
Figure 2.

$\displaystyle\mathcal{P}$ $\displaystyle=$
$\displaystyle\mathcal{D}\times\mathcal{P}_{aux}$
$\displaystyle\mathcal{P}_{aux}$ $\displaystyle=$
$\displaystyle\epsilon+\mathcal{L}_{1}\times\mathcal{P}_{aux}$
$\displaystyle\mathcal{L}_{1}$ $\displaystyle=$ $\displaystyle
a_{1}\times\mathcal{D}+a_{2}\times\mathcal{D}+a_{3}\times\mathcal{D}$
$\displaystyle\mathcal{R}_{1}$ $\displaystyle=$ $\displaystyle
b_{1}\times\mathcal{D}+b_{2}\times\mathcal{D}+b_{3}\times\mathcal{D}+b_{4}\times\mathcal{D}+b_{5}\times\mathcal{D}+b_{6}\times\mathcal{D}$
$\displaystyle\mathcal{D}$ $\displaystyle=$
$\displaystyle\mathcal{L}_{1}\times\mathcal{R}_{1}+\epsilon$ $\displaystyle
a_{1},...,a_{3}$ $\displaystyle=$ Atoms representing $+1$ steps $\displaystyle
b_{1},...,b_{6}$ $\displaystyle=$ Atoms representing $-1$ steps Figure 2:
_Grammar for 1-dimensional walks with inventory $A(u)=3u+6/u$_

#### Boltzmann sampling

To generate a walk, we next set up the Boltzmann sampler. This requires
generating functions for each non-terminal in the grammar. The generator
requires an evaluation point, which we take as the dominant singularity
$\frac{1}{6\sqrt{2}}$. Walks that are deemed too short or outside the target
length are rejected. The inverse bijection is applied to determine the
corresponding 3-dimensional step from which it was projected. The walk is
accepted if it stays in the orthant, and rejected if it exits.

#### Verification

Since there is some computational approximation in the Boltzmann sampler, we
did some tests to convince ourselves that we were achieving uniform
generation. We generated 10,000 walks of length 10, and tallied the number of
walks ending at each point. The proportions were compared with the exact
proportion of walks expected to end at each point, calculated using
recurrences. As the number of walks increases, we calculate the root-mean-
square error between the discrete distribution generated by our results, and
the distribution implied by exact counting. The root-mean-square error
decreases from $\approx 0.00340361673$ when generating 10 walks, $\approx
2.815461678\times 10^{-6}$ when generating 1,000,000 walks. While this isn’t a
proof, it does lend confidence that the algorithm generates walks uniformly.

(a) Drift $(0,0,0)$, approximately 1000 steps

(b) Drift $(-1,-1,-1)$, approximately 1000 steps (d) Drift $(0,-1,-1)$,
approximately 1000 steps Figure 3: _Randomly generated lattice walks with
various stepsets. Images each show 10 walks in the same space. A translucent
sphere with radius 20 is centered at the origin to give a sense of scale._

(c) Drift $(0,-1,0)$, approximately 1000 steps

###  3.2 Comparative study of models

Some examples of walks in $\mathbb{Z}^{3}$, restricted to the positive octant,
can be seen in Fig. 3b. Multiple walks are shown in each image.

The development of a typical walk changes significantly depending on the
drift.

For example, note that in Fig. 3b(b), when the drift tends towards the XZ
plane, the walks tend to form an arc from the origin towards a point further
out on the XZ plane. In contrast, in Fig. 3b(d), then the drift tends towards
the origin, a cluster of magenta near the origin and green on the outer
regions suggests that walks tend to venture far away from the origin, not
returning until the end of the walk.

Our algorithm makes it possible to generate long reluctant walks with high
probability in cases where a generating a walk of comparable length under the
naive scheme is virtually statistically impossible. Using the approximate
number of orthant walks of length $n$ to be $(6\sqrt{2})^{n}n^{-3}$, we can
see that in the naive scheme a walk of length $n$ has probability on the order
of $\left(\frac{6\sqrt{2}}{9}\right)^{n}n^{-3}$ of being generated in a given
run. This is less than .0002% when $n=100$, where as the Boltzmann sampler has
probability $n^{-3/2}$, which is $0.1\%$ for $n=100$. Both take strategies
take linear time to generate a walk of length $n$.

To be even more concrete, we generated 10 walks with drift $(-1,-1,-1)$ of
length around 100 using both strategies. With the naive rejection 133,065,405
walks were generated in total in order to find 10 that remained in the
positive octant, the rest being rejected. This took approximately 8 minutes
and 8.7 seconds. In contrast, when using Boltzmann sampling targeting lengths
between 95 and 105 steps, it was only necessary to generate 202,669 walks to
find 10 that were the appropriate length and remained in the positive octant.
This was done in approximately 8.4 seconds. Both computations were done on
similar conditions on a 2020 Macbook Pro with an Apple M1 chip.

Figure 4: _The convex hull at step 220 in the progression of 10 walks._

##  4 Future work

One of the appeals of this project – and one of the reasons we’ve created it
in the game engine Unity – is that the application provides the user with
multiple ways to visualize and understand walks. The reader is encouraged to
visit the site for some animations associated with reluctant walks.

We have discussed the colour coding already. It is also possible to animate
sets of walks, with each frame showing a simultaneous position of every walk
in the set. Recently, we’ve made it possible to view the convex hull of the
simultaneous positions of the walks at a given step, with the convex hull
changing as the walk progresses. (See Figure 4).

Other future plans include tools for generating data to give a sense of how
quickly the walks are generated with different methods, and how many
rejections occur. We also plan to create animations visualizing walks in terms
of their bijection with other objects – for example, queues and tableaux. We
also hope to make the Unity interface available in the future.

## References

  * [1]
  * [2] Cyril Banderier & Philippe Flajolet (2002): _Basic analytic combinatorics of directed lattice paths_.  Theoretical Computer Science 281, pp. 37–80, 10.1016/S0304-3975(02)00007-5.
  * [3] Alin Bostan, Mireille Bousquet-Mélou, Manuel Kauers & Stephen Melczer (2016): _On 3-dimensional lattice walks confined to the positive octant_.  Annals of Combinatorics 20(4), pp. 661–704, 10.1007/s00026-016-0328-7.
  * [4] Alin Bostan & Manuel Kauers (2009): _Automatic classification of restricted lattice walks_.  In: 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Math. Theor. Comput. Sci. Proc. AK, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 201–215, 10.46298/dmtcs.2724.
  * [5] Alin Bostan, Kilian Raschel & Bruno Salvy (2014): _Non-D-finite excursions in the quarter plane_.  Journal of Combinatorial Theory. Series A 121, pp. 45–63, 10.1016/j.jcta.2013.09.005.
  * [6] C. Banderier & Ph. Flajolet (2002): _Basic analytic combinatorics of directed lattice paths_.  Theoretical Computer Science 281(1-2), pp. 37–80, 10.1016/S0304-3975(02)00007-5.
  * [7] J. Courtiel, S. Melczer, M. Mishna & K. Raschel (2017): _Weighted lattice walks and universality classes_.  Journal of Combinatorial Theory. Series A 152, pp. 255–302, 10.1016/j.jcta.2017.06.008.
  * [8] Denis Denisov & Vitali Wachtel (2015): _Random walks in cones_.  The Annals of Probability 43(3), pp. 992–1044, 10.1214/13-AOP867.
  * [9] Philippe Duchon (2000): _On the enumeration and generation of generalized Dyck words_.  In: Discrete Mathematics, 225, pp. 121–135, 10.1016/S0012-365X(00)00150-3.
  * [10] Philippe Duchon, Philippe Flajolet, Guy Louchard & Gilles Schaeffer (2004): _Boltzmann samplers for the random generation of combinatorial structures_.  Combinatorics, Probability and Computing 13(4-5), pp. 577–625, 10.1017/S0963548304006315.
  * [11] Jetlir Duraj (2014): _Random walks in cones: the case of nonzero drift_.  Stochastic Processes and their Applications 124(4), pp. 1503–1518, 10.1016/j.spa.2013.12.003.
  * [12] Rodolphe Garbit & Kilian Raschel (2016): _On the exit time from a cone for random walks with drift_.  Revista Matemática Iberoamericana 32(2), pp. 511–532, 10.4171/RMI/893.
  * [13] Samuel Johnson, Marni Mishna & Karen Yeats (2018): _A combinatorial understanding of lattice path asymptotics_.  Advances in Applied Mathematics 92, pp. 144–163, 10.1016/j.aam.2017.08.001.
  * [14] Jérémie Lumbroso, Marni Mishna & Yann Ponty (2017): _Taming reluctant random walks in the positive quadrant_.  In: Random generation of combinatorial structures—GASCom 2016, Electron. Notes Discrete Math. 59, Elsevier Sci. B. V., Amsterdam, pp. 99–114, 10.1016/j.endm.2017.05.008.
  * [15] Marni Mishna & Samuel Simon (2020): _The asymptotics of reflectable weighted walks in arbitrary dimension_.  Advances in Applied Mathematics 118, pp. 102043, 19, 10.1016/j.aam.2020.102043.