# Skew Dyck paths with catastrophes

Helmut Prodinger  Helmut Prodinger, Department of Mathematical Sciences,
Stellenbosch University, 7602 Stellenbosch, South Africa, and NITheCS
(National Institute for Theoretical and Computational Sciences), South Africa
<EMAIL_ADDRESS>
###### Abstract.

Skew Dyck paths are like Dyck paths, but an additional south-west step
$(-1,-1)$ is allowed, provided that the path does not intersect itself.
Lattice paths with catastrophes can drop from any level to the origin in just
one step. We combine these two ideas. The analysis is strictly based on
generating functions, and the kernel method is used.

###### 1991 Mathematics Subject Classification:

05A15

##  1\. Introduction

The standard random walk on the non-negative integers may be visualized by the
following graph (only the first 8 states are shown):

$0$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 1. Standard symmetric random walk on the
non-negative integers

Such walks are also known as Dyck paths, going up or down one step at the
time. Most of the time, they need to come back to the $x$-axis (end at state
0), but one also considers open-ended paths where the level of the end of the
path is not specified.111Philippe Flajolet [1] liked the names ‘excursion’
resp. ‘meander, which we will not use.

$0$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 2. Catastrophes can lead from a state
$i\geq 2$ back to the $x$-axis in one step.

The Figure 2 shows the graph underlying the catastrophes, drawn in purple.

The standard reference for lattice paths with catastrophes is the paper [2];
the very recent paper [3] contains some bijective aspects.

The present note will combine skew Dyck paths (with an extra step $(-1,-1)$),
as analyzed in [5], with the concept of catastrophes.

##  2\. A warm-up: Dyck paths and catastrophes

To offer a gentle path for our readers, we analyze the paths as in Fig. 2
(which is also contained in the earlier papers [2, 3]), since we will approach
the skew Dyck paths with catastrophes in a similar style in the next section.

We introduce generating functions $f_{i}=f_{i}(z)$, where the coefficient of
$z^{n}$ counts the number of paths starting at the origin (=the big circle)
and end after $n$ steps at state $i$ (=level $i$). The following recursions
are easy to see:

$\displaystyle f_{0}$ $\displaystyle=1+z(f_{1}+f_{2}+f_{3}+f_{4}+\cdots),$
$\displaystyle f_{i}$ $\displaystyle=zf_{i-1}+zf_{i+1},\ i\geq 1.$

Since $f_{0}$ is somewhat special, we leave it out for the moment and compute
the other ones, $f_{i}$, $i\geq 1$. Eventually we will solve the equation for
$f_{0}$, which will turn out to be just linear. Therefore we introduce the
bivariate generating function

$F(u)=F(u,z)=\sum_{i\geq 1}u^{i-1}f_{i}$

and we treat $f_{0}$ as a parameter. Summing the recursions,

$F(u)=zf_{0}+zuF(u)+\frac{z}{u}[F(u)-f_{1}],$

or

$F(u)=\frac{zf_{0}-\frac{z}{u}f_{1}}{1-zu-\frac{z}{u}}=\frac{zf_{1}-zuf_{0}}{zu^{2}-u+z}=\frac{zf_{1}-zuf_{0}}{z(u-r_{1})(u-r_{2})},$

with

$r_{1}=\frac{1+\sqrt{1-4z^{2}}}{2z},\quad r_{2}=\frac{1-\sqrt{1-4z^{2}}}{2z}.$

An essential step of the _kernel method_ is that the ‘bad’ factor $(u-r_{2})$
must cancel. The reciprocal of this factor does not have a power series
expansion in $(u,z)$. Dividing this factor out in both, denominator and
numerator, leads to

$F(u)=\frac{-zf_{0}}{z(u-r_{1})}=\frac{zf_{0}}{zr_{1}(1-u/r_{1})},$

and from this

$f_{i}=[u^{i-1}]F(u)=\frac{zf_{0}}{zr_{1}^{i}}=f_{0}r_{2}^{i}.$

This formula holds for all $i\geq 0$. It is interesting to note that all these
functions are just a multiple of the parameter $f_{0}$. Now we can go to the
first recursion:

$f_{0}=1+z(f_{0}r_{2}^{1}+f_{0}r_{2}^{2}+f_{0}r_{2}^{3}+\cdots)=1+zf_{0}\frac{r_{2}}{1-r_{2}}$

and solve the equation,

$f_{0}=\frac{2-3z-2z^{2}+z\sqrt{1-4z^{2}}}{2(1-z-2z^{2}-z^{3})}.$

It has the power series expansion

$f_{0}=1+z^{2}+z^{3}+3z^{4}+5z^{5}+12z^{6}+23z^{7}+52z^{8}+105z^{9}+232z^{10}+480z^{11}+1049z^{12}+2199z^{13}+\cdots,$

and the list of coefficients is sequence A224747 in the OEIS [6]. The papers
[2, 3] have this already. We can also compute the number of Dyck paths with
catastrophes and open (unspecified) end, via the generating function

$\displaystyle f_{0}$ $\displaystyle+f_{1}+f_{2}+f_{3}+f_{4}+\dots$
$\displaystyle=\frac{1-z+(1+z)\sqrt{1-4z^{2}}}{2(1-z-2z^{2}-z^{3})}$
$\displaystyle=1+z+2{z}^{2}+4{z}^{3}+8{z}^{4}+17{z}^{5}+35{z}^{6}+75{z}^{7}+157{z}^{8}+337{z}^{9}+712{z}^{10}+\cdots.$

This is almost sequence A274115 in the OEIS [6];
$1+z(f_{0}+f_{1}+f_{2}+\cdots)$ has this sequence as coefficients. Thanks go
to Michel Marcus to point out the connection with the sequences in the OEIS.

##  3\. Skew Dyck paths with catastrophes

Skew Dyck are a variation of Dyck paths, where additionally to steps $(1,1)$
and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided that the
path does not intersect itself.

Here is a list of the 10 skew paths consisting of 6 steps:

Figure 3. All 10 skew Dyck paths of length 6 (consisting of 6 steps).

We prefer to work with the equivalent model (resembling more traditional Dyck
paths) where we replace each step $(-1,-1)$ by $(1,-1)$ but label it red. Here
is the list of the 10 paths again (Figure 4):

Figure 4. The 10 paths redrawn, with red south-east edges instead of south-
west edges.

The rules to generate such decorated Dyck paths are: each edge $(1,-1)$ may be
black or red, but  and  are forbidden.

These figures are taken from our earlier paper [5].

Figure 5. Three layers of states according to the type of steps leading to
them (up, down-black, down-red). Purple arrows all end in the origin.

As in the motivating example from the previous section, we introduce
generating functions. But since we need 3 layers to control everything, we
need to introduce $f_{j}$, $g_{j}$, $h_{j}$. The purple edges all end in the
origin and represent the catastrophes. If they are ignored, one models skew
Dyck paths in this way, in particular $f_{0}+g_{0}+h_{0}$ is the generating
function of skew Dyck paths coming back to level 0. However, now, we will deal
with the purple arrows as well.

The following recursions can be read off immediately from the diagram 5:

$\displaystyle f_{0}=1+z\sum_{i\geq 2}f_{i}+z\sum_{i\geq 2}g_{i}+z\sum_{i\geq
2}h_{i},$ $\displaystyle f_{i+1}=zf_{i}+zg_{i},\quad i\geq 0,$ $\displaystyle
g_{i}=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\geq 0,$ $\displaystyle
h_{i}=zh_{i+1}+zg_{i+1},\quad i\geq 0.$

As before, we first ignore $f_{0}$ and treat is as a parameter. We introduce

$F(u)=\sum_{i\geq 1}u^{i-1}f_{i},\quad G(u)=\sum_{i\geq 0}u^{i}g_{i},\quad
H(u)=\sum_{i\geq 0}u^{i}h_{i}.$

Now we sum the recursions and get

$\displaystyle\sum_{i\geq 0}u^{i}f_{i+1}=\sum_{i\geq 0}u^{i}zf_{i}+\sum_{i\geq
0}u^{i}zg_{i}$

or

$\displaystyle F(u)=f_{0}+uzF(u)+zG(u).$

Further,

$\sum_{i\geq 0}u^{i}g_{i}=\sum_{i\geq 0}u^{i}zf_{i+1}+\sum_{i\geq
0}u^{i}zg_{i+1}+\sum_{i\geq 0}u^{i}zh_{i+1}$

which translates into

$G(u)=zF(u)+\frac{z}{u}[G(u)-G(0)]+\frac{z}{u}[H(u)-H(0)];$

similarly

$H(u)=\frac{z}{u}[G(u)-G(0)]+\frac{z}{u}[H(u)-H(0)].$

We will eliminate the functions $G$ and $H$:

$G=-{\frac{z{f_{0}}+zuF-F}{z}}$

and

$H=G-zF.$

Therefore we end up with just one equation for $F$

$-uzf_{0}-z{u}^{2}F+uF=-{z}^{2}Fu-2{z}^{2}f_{0}+2zF-2g_{0}{z}^{2}-{z}^{3}F+{z}^{3}f_{1}$

which can be solved,

$F(u)=-{\frac{\left(-2zf_{0}-2zg_{0}+{z}^{2}f_{1}+f_{0}u\right)z}{-{z}^{2}u+2z-{z}^{3}+z{u}^{2}-u}}=-\frac{\left(-2zf_{0}-2zg_{0}+{z}^{2}f_{1}+f_{0}u\right)z}{z(u-r_{1})(u-r_{2})}$

with

$r_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z},\quad
r_{2}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

The fact that $u-r_{2}$ must divide the numerator of $F$ leads to

$g_{0}={\frac{-2zf_{0}+{z}^{2}f_{1}+r_{2}f_{0}}{2z}},$

so that $g_{0}$ can be eliminated and only $f_{1}$ remains as unknown;

$F=\frac{zf_{0}}{1-zu+z^{2}-zr_{2}}$

plugging in $u=0$ allows to compute it:

$f_{1}=\frac{zf_{0}}{1+z^{2}-zr_{2}}=\frac{f_{0}}{r_{1}}.$

Therefore the function $F$ is known:

$F(u)=\frac{f_{0}}{r_{1}-u}$

and thus

$f_{j}=[u^{j-1}]F(u)=\frac{f_{0}}{r_{1}^{j}}.$

From this, the other functions can be computed as well:

$G(u)=\frac{1-zr_{1}}{z}\frac{f_{0}}{r_{1}-u}=(r_{2}-z)\frac{f_{0}}{r_{1}-u}$

and

$g_{j}=[u^{j}]G(u)=(r_{2}-z)\frac{f_{0}}{r_{1}^{j+1}},$

as well as

$H(u)=(r_{2}-2z)\frac{f_{0}}{r_{1}-u}$

and

$h_{j}=[u^{j}]H(u)=(r_{2}-2z)\frac{f_{0}}{r_{1}^{j+1}}.$

Now we can finally deal with $f_{0}$. The evaluations that are needed are
simple:

$\sum_{j\geq 2}f_{j}=\frac{f_{0}/r_{1}^{2}}{1-1/r_{1}},\quad\sum_{j\geq
2}g_{j}=(r_{2}-z)\frac{f_{0}/r_{1}^{3}}{1-1/r_{1}},\quad\sum_{j\geq
2}h_{j}=(r_{2}-2z)\frac{f_{0}/r_{1}^{3}}{1-1/r_{1}};$

of course this is better done with a computer. From this, the equation (just
linear) for $f_{0}$ can be solved:

$f_{0}=\frac{1-9{z}^{3}-5{z}^{4}+3{z}^{5}+2{z}^{6}-(1-z^{2}-z^{3})\sqrt{1-6z^{2}+5z^{4}}}{2(1-2{z}^{2}-6{z}^{3}-3{z}^{4}+{z}^{5}+{z}^{6})}.$

The series expansion

$1+{z}^{3}+{z}^{4}+4{z}^{5}+6{z}^{6}+18{z}^{7}+31{z}^{8}+85{z}^{9}+157{z}^{10}+410{z}^{11}+792{z}^{12}+2004{z}^{13}+\cdots$

is not in OEIS [6]. To compute the number of all skew Dyck paths coming back
to the $x$-axis, we need

$\displaystyle f_{0}$ $\displaystyle+g_{0}+h_{0}$
$\displaystyle=\frac{(1-z^{2})(3-z)(1-z-2z^{2}-z^{3})-(1-4z-3z^{2}+z^{3}+z^{4})\sqrt{1-6z^{2}+5z^{4}}}{2(1-2{z}^{2}-6{z}^{3}-3{z}^{4}+{z}^{5}+{z}^{6})}.$

The series expansion is

$1+z^{2}+z^{3}+4z^{4}+5z^{5}+17z^{6}+25z^{7}+76z^{8}+125z^{9}+353z^{10}+625z^{11}+1681z^{12}+\cdots.$

One can also sum everything to enumerate the open ended paths in this model:

$\displaystyle\sum_{j\geq 0}$ $\displaystyle f_{j}+\sum_{j\geq
0}g_{j}+\sum_{j\geq 0}h_{j}$
$\displaystyle=\frac{(1+z)(1-4z+4z^{2}+4z^{3}-z^{5})+(1+5z+3z^{2}-z^{3}-z^{4})\sqrt{1-6z^{2}+5z^{4}}}{2(1-2{z}^{2}-6{z}^{3}-3{z}^{4}+{z}^{5}+{z}^{6})};$

the series expansion is

$1+z+2z^{2}+4z^{3}+9z^{4}+18z^{5}+41z^{6}+85z^{7}+193z^{8}+410z^{9}+929z^{10}+2004z^{11}+\cdots.$

######  Theorem 1.

The generating functions related to the model of skew Dyck paths with
catastrophes are

$\displaystyle f_{j}$ $\displaystyle=\frac{f_{0}}{r_{1}^{j}},$ $\displaystyle
g_{j}$ $\displaystyle=(r_{2}-z)\frac{f_{0}}{r_{1}^{j+1}},$ $\displaystyle
h_{j}$ $\displaystyle=(r_{2}-2z)\frac{f_{0}}{r_{1}^{j+1}},$

with

$r_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z},\quad
r_{2}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z},$

and

$\displaystyle f_{0}$ $\displaystyle+g_{0}+h_{0}$
$\displaystyle=\frac{(1-z^{2})(3-z)(1-z-2z^{2}-z^{3})-(1-4z-3z^{2}+z^{3}+z^{4})\sqrt{1-6z^{2}+5z^{4}}}{2(1-2{z}^{2}-6{z}^{3}-3{z}^{4}+{z}^{5}+{z}^{6})}.$

The enumeration of all paths, regardless of the final level, is

$\displaystyle\sum_{j\geq 0}$ $\displaystyle f_{j}+\sum_{j\geq
0}g_{j}+\sum_{j\geq 0}h_{j}$
$\displaystyle=\frac{(1+z)(1-4z+4z^{2}+4z^{3}-z^{5})+(1+5z+3z^{2}-z^{3}-z^{4})\sqrt{1-6z^{2}+5z^{4}}}{2(1-2{z}^{2}-6{z}^{3}-3{z}^{4}+{z}^{5}+{z}^{6})}.$

##  4\. Conclusion

From our analysis, other types of catastrophes (example: only from an even-
numbered level one can drop to the ground) can be computed without much
further effort. This changes only the equation for $f_{0}$; the other
quantities stay as they are.

## References

  * [1] C. Banderier and P. Flajolet.  Basic analytic combinatorics of directed lattice paths,  Theor. Comput. Sci., 281 (2002),37–80.
  * [2] C. Banderier and M. Wallner.  Lattice paths with catastrophes,  Discrete Math. Theor. Comput. Sci., 19 (2017), Paper No. 23, 32.
  * [3] J.-L. Baril, S. Kirgizov.  Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths,  Discrete Mathematics Letters, 7 (2021), 5-10.
  * [4] H. Prodinger.  The Kernel Method: A Collection of Examples,  Séminaire Lotharingien de Combinatoire, B50f (2004), 19 pp.
  * [5] H. Prodinger, Partial skew Dyck paths—a kernel method approach, arXiv:2108.09785 (2021).
  * [6] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences, 2022.


# From Face to Gait: Weakly-Supervised Learning of Gender Information from
Walking Patterns

Andy Catruna1 Adrian Cosma2 Ion Emilian Radoi3
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>University Politehnica of Bucharest

###### Abstract

Obtaining demographics information from video is valuable for a range of real-
world applications. While approaches that leverage facial features for gender
inference are very successful in restrained environments, they do not work in
most real-world scenarios when the subject is not facing the camera, has the
face obstructed or the face is not clear due to distance from the camera or
poor resolution. We propose a weakly-supervised method for learning gender
information of people based on their manner of walking. We make use of state-
of-the art facial analysis models to automatically annotate front-view walking
sequences and generalise to unseen angles by leveraging gait-based label
propagation. Our results show on par or higher performance with facial
analysis models with an F1 score of 91% and the ability to successfully
generalise to scenarios in which facial analysis is unfeasible due to subjects
not facing the camera or having the face obstructed.

††publicationid: pubid: 978-1-6654-3176-7/21/$31.00 ©2021 IEEE

##  I INTRODUCTION

Figure 1: Our method for training gait-based gender identification based on
noisy labels given by the facial analysis model. Gender labels are inferred
from front-views and are processed by a ResNet-18 architecture which processes
skeleton sequences. For the final inference, only skeleton sequences are used.

Demographics estimation from video is a long standing research topic in the
machine learning community. Gender estimation in images and videos has
numerous potential applications in areas such as access control, marketing and
surveillance [4]. Across the years, developing facial analysis models was the
primary focus of computer vision research in this area. This led to the
construction of several large-scale datasets for modelling a plethora of
attributes derived from faces: demographics, emotions, appearance, and person
identity. Systems based on facial analysis models have matured to the point of
deployment in constrained environments [1]. However, in surveillance scenarios
limitations are apparent in situations where the subject is not cooperating
(i.e. not facing the camera) or surveillance cameras are placed at a distance
thus capturing faces in poor resolution.

Recent advances in gait analysis systems show that gait holds rich biometric
information, being able to reliably determine a person’s identity [6, 7],
demographics characteristics [24] and emotions [26], without requiring
specialized equipment or cooperation from the subject. The main limitation of
gait analysis models is the difficulty of gathering properly annotated
training data. Images containing faces are prevalent on the internet at large,
but gathering an exhaustive gait database requires the willing participation
of many subjects to walk in diverse scenarios, especially since gait is
affected by many more confounding factors including clothing, carrying
conditions and camera viewpoint [30].

Using advantages of both facial and gait analysis, we propose a method to
automatically annotate the gender of front-view walking sequences with facial
analysis models to generate training data for a gait-based gender recognition
system. Through experiments on the popular Front-View Gait (FVG) [34] dataset,
we show that gender annotations using facial analysis models are on par with
ground truth labels, in some cases surpassing facial analysis models,
obtaining an F1 score of 91%. This method is a reliable way to acquire data
for training demographic models in real-world scenarios. However, due to the
limitation of facial analysis models the proposed method only generates
annotated data of front-view walking patterns. To overcome this problem, we
propose using a semi-supervised approach to generalise to other angles in
which the face is not visible. We leverage gait-based metric learning and
label propagation to generate noisy pseudo-labels on unseen angles, and use
appropriate loss functions developed for training models with label
corruption. Training a model on pseudo-labels from label-propagation, we
obtain an overall F1 score of 82% on the CASIA-B [30], similar to a model
trained on real labels.

To model walking patterns, we make use of available state-of-the-art pose
estimation models (i.e. AlphaPose [14]), that allow for accurate estimation of
the joints of a walking person. We choose to operate on skeleton sequences, as
these are more flexible than the standard Gait Energy Images (GEI) used in
gait analysis, enabling more fine-grained filtering of the walking sequence,
more suitable in real-world scenarios.

While current datasets for modelling demographics from gait (i.e. OULP-Age
[25]) are valuable in aiding development of model architectures, we argue that
they are less suitable for real-world scenarios, as such controlled scenarios
are rarely encountered in surveillance streams. Our method is general in the
sense that it has the potential to generate annotated data from surveillance
streams without human interference. Walking sequences are automatically
annotated covering a wide range of real-world scenarios. Through semi-
supervised learning, from the annotated front-view walks we obtain annotations
for other unseen angles. Models of this pipeline can be replaced with
potentially better ones, enabling flexible and general applicability in real-
world scenarios.

This paper makes the following contributions:

  * •

A method for automatically annotating gender information in front-view walking
sequences through facial analysis methods. We show that models trained on such
pseudo-labels have similar performance to facial analysis methods, and
surpassing them in adverse scenarios.

  * •

A semi-supervised algorithm based on label-propagation to generate pseudo-
labels on walking sequences for unseen camera viewpoints, through gait-based
metric transfer. Models trained on these pseudo-labels show similar
performance to those trained on real labels.

##  II RELATED WORK

In recent years, there has been increased attention towards modelling
demographic information from human walking patterns from video. Research in
this direction, while still very new, is fuelled by the arrival of new large-
scale datasets (i.e. OULP-Age [25]) and the advent of deep learning. Most
approaches leverage appearance-based features in the form of a Gait Energy
Image (GEI) [9]. GEIs model the walking sequence be averaging silhouettes
across a gait cycle. While this data representation has its limitations by not
taking temporal information into account, it is nevertheless successful in
applications of gait analysis for both age [18, 21, 35] and gender [17, 23]
estimation.

Notably, Xu et al. [23] proposed a real-time framework for demographic
detection from a single silhouette. They firstly reconstruct the gait energy
image and process it with a gait recognition network. However, it is unclear
if the recognized gender is due to the appearance information of the
silhouette or the walking movement patterns. To gauge the impact of movement
patterns, skeleton sequences are more appropriate, as they abstract away any
appearance features. However, very few methods exist that make use of skeleton
sequences for inferring demographic attributes. Arai et al. [2] inferred the
skeleton through morphological manipulation of the silhouette. Ahmed et al.
[3] used a kinect sensor to estimate the skeleton of the walking subject and
analyse gender attributes using handcrafted features on a minimal dataset (18
subjects). In contrast, our goal is to alleviate the need for a carefully
gathered dataset of walking sequences and gender, and to develop a pipeline
that can generalise to more unconstrained environments. Moreover, as far as
the authors know, no method employed skeletons extracted from a modern 2D pose
estimation model. Regarding face analysis, many studies have been performed in
various conditions, including ”in the wild”: Zhang et al. [31] developed an
architecture called Deep RoR for age and gender identification, that achieves
more stable training than other CNN architectures at the time. Rothe et al.
[20] made a distinction between the real and apparent age of a person, and
developed a model that accurately estimates the apparent age of a person based
on their face. Significantly more face datasets are available for training and
evaluation than gait-based methods. Among the more popular ones include IMDB-
WIKI [20], UTKFace [33] and FairFace [12].

While some methods explore the fusion of face and gait modalities [29, 19, 8],
in which a model jointly learns to identify demographic attributes from both
modalities, we instead only use gait for the final prediction, and employ
facial traits as a supervisory signal. Our method more closely relates to
model distillation [11], in which the student model (i.e. gait analysis model)
learns to imitate the outputs of the teacher model (i.e. facial analysis
models). Moreover, to overcome the limitation of multiple viewpoints, most
methods employ a viewpoint classifier, and train an ensemble of models trained
on different angles. This assumes labels are present on all viewpoints, which
is not reasonable in our case. Instead of using an ensemble, we address this
problem using label-propagation guided by gait sequence similarity.

##  III METHOD

TABLE I: Accuracy of pseudo-labels on CASIA-B, using gait-based label propagation. | 0∘ | 18∘ | 36∘ | 54∘ | 72∘ | 90∘ | 108∘ | 126∘ | 144∘ | 162∘ | 180∘ | Mean
---|---|---|---|---|---|---|---|---|---|---|---|---
Nearest Neighbors | $-$ | 89.6 | 86.6 | 85.3 | 80.0 | 78.3 | 83.1 | 84.8 | 83.0 | 83.6 | 85.0 | 83.9
Spectral Clustering | $-$ | 92.3 | 90.5 | 87.0 | 84.3 | 83.6 | 85.3 | 85.3 | 86.1 | 85.0 | 85.5 | 86.5

Our aim is to develop a method for learning demographic attributes from gait
without explicit human annotations. We expand upon the two main components: i)
learning to estimate demographics from gait using facial analysis labels on
front views (Fig. 1) and ii) generalizing to camera viewpoints where the face
is not visible using label propagation.

###  III-A Distilling Information from Face Analysis

For this part of our method, we made use of the Front-View Gait (FVG) dataset
[34], a popular dataset for gait recognition from the more challenging front-
facing angle. The dataset contains multiple confounding factors such as
walking speed (WS), clothing variations (CL), carrying variations (CB) and
cluttered background (CBG). The dataset contains high-resolution images,
appropriate for facial identification. We repurpose it for gender estimation
by manually annotating the 226 subjects with gender information, to have a
clear ground truth for comparison. To analyse facial information, we employ
the MTCNN [32] model to detect faces present in each video, and use an
EfficientNet [22] trained on the popular IMDB-WIKI dataset [20] to infer
demographic attributes. As noted by Gonzalez-Sosa et al. [8], the performance
of face-based gender estimation works best on a close distance setting, while
gait-based inference is more appropriate at a distance. As such, for final
labels we employed a weighted average of the gender confidence based on the
area of the face bounding box relative to the frame dimensions. Further,
skeletons are extracted for each frame using AlphaPose [14], and height
normalized. The output of the AlphaPose model consists of 17 joints with X and
Y coordinates of the joints and the confidence. To normalize the data, we
first zero-center the data by subtracting from each joint the coordinates of
the pelvis and then we divide the coordinates of each joint on the X-axis by
the length from the right to the left shoulder and on the Y-axis by the length
from the pelvis to the neck. Through this process, any appearance information
such as the height of the person is removed. In a study by Yang et al. [27],
multiple ways of arranging the skeletons are described in order for a model to
be able to efficiently learn spatio-temporal information about the movement of
a person. We chose the approach in which multiple extracted poses are
concatenated to form a skeleton image (TSSI). This way, the spatial
information about the joints is preserved, as well as the temporal variation
across the gait cycle. We use a ResNet-18 [10] in all our experiments.

Figure 2: Pseudo-labels generated through facial analysis can be incorrect due
to obstructive headware or camera parameters (i.e. camera focus issues).

Using pseudo-labels generated from facial analysis invariably introduces noise
in the training process, as some of these labels can be incorrect due to
changes in illumination, head wear etc. Figure 2 illustrates some of the
incorrect labels produced by the facial analysis model. To alleviate the
impact of these incorrect labels, we experiment with several methods that
handle noisy or incorrect labels, such as more robust training losses [5],
noise modelling (i.e. PENCIL [28] and Importance Reweighting [16]). We posit
that gait patterns are more robust to extrinsic confounding factors that
relate to camera configuration and viewpoint.

###  III-B Gait-Based Label Propagation

The previous method is successful at generating pseudo-labels for gender
estimation in situations where the face is clearly visible. This corresponds
to the majority of cases in which the person is walking directly towards the
camera, in front-facing views. One of the major advantages of using gait as an
input signal is that is has the potential to work in more adverse situations
than facial analysis systems, mainly in scenarios in which the subject is far
from the camera or not facing towards it. However, by only using demographic
attributes estimated from front-facing views, the gait analysis model is
unable to generalise to other angles. To solve this issue, we propose to use a
method similar to that of Liu et al. [15]. The authors propose an algorithm
for deep label propagation, using a pretrained metric model. Given a small set
of labelled examples, labels are propagated to the large number of unlabelled
samples by making use of a semantic similarity measure between examples. In
our case, we consider only the front-facing views to be labelled and other
viewpoints in which the face is not visible to be unlabelled. However,
different from the simple case of images, walking sequences from different
viewpoints are qualitatively very different from one another. Previous work in
unsupervised gait recognition by Cosma et al. [6] showed that a similarity
metric between walking sequences can be effectively learned without human
labels, by leveraging contrastive learning and massive amounts of unlabelled
data. WildGait, the framework proposed by Cosma et al. [6] for gait-based
person identification using skeletons, achieves disentanglement of viewpoint
variation and confounding factors, and is a suitable candidate to be used as a
similarity measure between walking sequences. As such, we leverage a
pretrained WildGait network as a similarity network between walking sequences,
and use it to further propagate labels to unseen angles.

As FVG does not contain viewpoints in which the face is not visible, we
conduct experiments on CASIA-B, which offers 11 different viewpoints. We
manually annotate subjects with gender attributes to have an accurate
benchmark.

TABLE II: Results on gender classification on CASIA-B using only frontview
gender annotations (i.e. 0∘).

| 0∘ | 18∘ | 36∘ | 54∘ | 72∘ | 90∘ | 108∘ | 126∘ | 144∘ | 162∘ | 180∘ | Mean
---|---|---|---|---|---|---|---|---|---|---|---|---
Baseline (train only on 0∘) | 69.92 | 33.33 | 33.33 | 33.33 | 33.33 | 33.33 | 46.89 | 31.03 | 38.91 | 72.34 | 84.85 | 46.41
Gait-Based Label Propagation - NN | 76.30 | 85.0 | 65.77 | 87.3 | 52.38 | 56.36 | 67.03 | 70.25 | 71.63 | 70.25 | 81.95 | 71.29
Gait-Based Label Propagation - Spectral | 89.90 | 97.50 | 63.66 | 33.33 | 97.50 | 89.90 | 92.46 | 89.90 | 76.30 | 92.46 | 81.95 | 82.26
True Labels (all viewpoints) | 79.80 | 92.50 | 80.0 | 73.33 | 100.0 | 97.50 | 100.0 | 94.99 | 79.17 | 92.46 | 84.65 | 88.58

##  IV EXPERIMENTS & RESULTS

###  IV-A Distilling Information from Face Analysis: FVG

To avoid a favorable configuration of our setting, we used cross-validation by
randomly sampling 46 unique subjects and utilizing their data for validation
while the remaining identities are used for training. We ran each experiment
three times. Since FVG contains 64% male subjects and 36% female subjects, we
oversampled from the female class during the training process in order to
overcome class imbalance. Due to the disparity in the validation data, we
report the mean F1 score and standard deviations. In all experiments we used
ResNet-18 [10] architecture, Adam optimizer [13] with a learning rate of
0.0001 and batch size of 128. We employed the standard array of augmentations
for gait analysis: skeleton flipping, mirroring, joint dropout, pace
modification and random cropping.

Figure 3: Selected samples in which facial analysis outputs the wrong gender
due to extrinsic camera parameters, to which the gait model is robust.

Since pseudo-labels can be noisy, we compare several methods that account for
incorrect labels: Probabilistic End-to-end Noise Correction (PENCIL) [28], a
method agnostic to the backbone network and any prior knowledge of the noise
distribution; Importance Reweighting [16], a method widely used in domain
adaptation; a framework proposed Ciortan et al. [5] for classification with
noisy labels with promising results using a loss function designed for
adversarial robustness: a combination of Negative Focal Loss and Reverse Cross
Entropy (NFL-RCE).

Table III shows our results in terms of F1 score on multiple walking
variations from FVG. The gait-based model trained on real gender annotations
has good performance on the FVG test set, similar to the face-based model.
This is an encouraging result in terms of the reliability of gait-based gender
prediction systems. Since the gait-based model trained on real gender labels
or pseudo-labels has similar, good results demonstrates the effectiveness of
our method of training gait-based models with pseudo-labels. Also, a model
that relies on face analysis has shortcomings that gait analysis can overcome.
Figure 3 displays scenarios in which a gait-based model trained on pseudo-
labels produces the correct output where the face analysis model is incorrect.
Blurry faces or people wearing hats or glasses tend to make the face analysis
model underperform. In comparison, gait analysis is more robust to extrinsic
confounding factors. These results highlight the efficiency of our method.
Even though the gait-based model is trained on labels generated by face
analysis, in some difficult cases for face analysis (such as the ones in
Figure 3), it is able to generalise despite having been provided with
unreliable labels. Moreover, the addition of methods that incorporate noisy
labels further improves the classification robustness.

TABLE III: F1 score of the gait analysis model on FVG trained with different
methods that account of noisy training labels.

| WS | CB | CL | CBG | All
---|---|---|---|---|---
Face | 91.84 $\pm$ 3.1 | 89.14 $\pm$ 0.7 | 87.6 $\pm$ 6.8 | 91.7 $\pm$ 6.0 | 91.0 $\pm$ 2.7
Gait True Labels | 92.0 $\pm$ 3.1 | 87.2 $\pm$ 2.8 | 92.7 $\pm$ 7.0 | 91.0 $\pm$ 8.3 | 92.0 $\pm$ 2.6
Gait Face Labels | 92.0 $\pm$ 1.7 | 82.7 $\pm$ 8.3 | 91.0 $\pm$ 1.1 | 86.2 $\pm$ 5.7 | 90.7 $\pm$ 1.9
NFL-RCE [5] | 88.6 $\pm$ 2.7 | 86.1 $\pm$ 4.9 | 83.5 $\pm$ 2.5 | 83.7 $\pm$ 8.4 | 88.9 $\pm$ 1.7
IW$l$ [16] | 90.4 $\pm$ 0.5 | 82.2 $\pm$ 8.8 | 95.3 $\pm$ 3.3 | 89.9 $\pm$ 7.8 | 90.1 $\pm$ 1.2
PENCIL [28] | 90.8 $\pm$ 2.3 | 85.0 $\pm$ 7.1 | 92.1 $\pm$ 0.8 | 90.6 $\pm$ 7.5 | 91.0 $\pm$ 1.7

###  IV-B Gait-Based Label Propagation: CASIA-B

To evaluate our method in scenarios where only frontview walks are annotated
with gender labels, we utilize the popular CASIA-B [30] dataset for gait
recognition. CASIA-B contains 124 subjects walking from 11 different
viewpoints, with clothing variations and carrying conditions. The dataset was
manually annotated with gender labels, and 92 males and 32 females were
obtained. The data was split into 80% training and 20% validation and the
majority class (males) was undersampled to balance the dataset.

We follow the Deep Metric Transfer framework of Liu et al. [15], in which
label propagation is performed using a pretrained metric model between
samples. In our case, we employed WildGait [6] as a similarity measure between
walking sequences. WildGait was trained on UWG, a large-scale dataset of
noisily annotated walking sequences from real-world scenes, in an unsupervised
manner. The model was not fine-tuned on CASIA-B and was used as-is.

We considered only the frontview angle (0∘) to be annotated with gender
labels, and employed label-propagation to annotate other angles in which the
face is not visible. We compared 2 label-propagation methods: nearest
neighbors and spectral clustering. Similar to Liu et al. [15], best results
were obtained with the latter, as shown in Table I.

Further, we trained a ResNet-18 on the propagated pseudo-labels, together with
the true labels at angle 0∘. We employed the NFL-RCE loss function to account
for incorrect pseudo-labels. F1 scores are presented in Table II for all
angles in CASIA-B. Compared to the baseline model, label-propagation achieves
significantly better results. Moreover, spectral label propagation is similar
in performance to the model trained on data with all available true labels,
highlighting the capability of label propagation using a gait-based similarity
measure to generalise to unseen angles.

##  V CONCLUSIONS

This work proposes and evaluates a system to estimate the gender of a person
based on their walking patterns, without requiring any explicitly labelled
data. We make use of current state-of-the-art facial analysis systems to
automatically annotate videos of walking persons. However, facial analysis
models have two inherent problems: i) outputs are not always correct and ii)
only work on walking from front-views. To overcome these shortcomings, we
employed several methods to account for noisy labels, which increases the
robustness of our model, and employed a gait-based label propagation method to
generalise to unseen walking angles.

The results show great potential of automatic labeling of gait patterns to be
used in practice in surveillance scenarios, with performance on par with
facial analysis models, and oftentimes exceeding it, as gait analysis models
are inherently more robust to extrinsic confounding factors, such as camera
configuration and walking viewpoint.

## References

  * [1] Rite aid deployed facial recognition systems in hundreds of u.s. stores.  https://www.reuters.com/investigates/special-report/usa-riteaid-software/.  Accessed: 2021-08-19.
  * [2] K. Aarai and R. Andrie.  Gender classification with human gait based on skeleton model.  pages 113–118, 04 2013.
  * [3] M. H. Ahmed and A. T. Sabir.  Human gender classification based on gait features using kinect sensor.  In 2017 3rd IEEE International Conference on Cybernetics (CYBCONF), pages 1–5, 2017.
  * [4] V. D. Ambeth Kumar, S. Ramya, H. Divakar, and G. Kumutha Rajeswari.  A survey on face recognition in video surveillance.  In D. Pandian, X. Fernando, Z. Baig, and F. Shi, editors, Proceedings of the International Conference on ISMAC in Computational Vision and Bio-Engineering 2018 (ISMAC-CVB), pages 699–708, Cham, 2019. Springer International Publishing.
  * [5] M. Ciortan, R. Dupuis, and T. Peel.  A framework using contrastive learning for classification with noisy labels.  Data, 6(6), 2021.
  * [6] A. Cosma and E. Radoi.  Wildgait: Learning gait representations from raw surveillance streams, 2021.
  * [7] A. Cosma and I. E. Radoi.  Multi - task learning of confounding factors in pose-based gait recognition.  In 2020 19th RoEduNet Conference: Networking in Education and Research (RoEduNet), pages 1–6, 2020.
  * [8] E. Gonzalez-Sosa, A. Dantcheva, R. Vera-Rodriguez, J.-L. Dugelay, and J. Fierrez.  Image-based gender estimation from body and face across distances.  pages 3061–3066, 12 2016.
  * [9] J. Han and B. Bhanu.  ”individual recognition using gait energy image”.  IEEE transactions on pattern analysis and machine intelligence, 28:316–22, 03 2006.
  * [10] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [11] G. Hinton, O. Vinyals, and J. Dean.  Distilling the knowledge in a neural network.  In NIPS Deep Learning and Representation Learning Workshop, 2015\.
  * [12] K. Kärkkäinen and J. Joo.  Fairface: Face attribute dataset for balanced race, gender, and age.  CoRR, abs/1908.04913, 2019.
  * [13] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization, 2014.  cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
  * [14] J. Li, C. Wang, H. Zhu, Y. Mao, H.-S. Fang, and C. Lu.  Crowdpose: Efficient crowded scenes pose estimation and a new benchmark.  arXiv preprint arXiv:1812.00324, 2018.
  * [15] B. Liu, Z. Wu, H. Hu, and S. Lin.  Deep metric transfer for label propagation with limited annotated data.  CoRR, abs/1812.08781, 2018.
  * [16] T. Liu and D. Tao.  Classification with noisy labels by importance reweighting.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):447–461, Mar 2016.
  * [17] J. Lu, G. Wang, and P. Moulin.  Human identity and gender recognition from gait sequences with arbitrary walking directions.  IEEE Transactions on Information Forensics and Security, 9(1):51–61, 2014.
  * [18] Y. Makihara, M. Okumura, H. Iwama, and Y. Yagi.  Gait-based age estimation using a whole-generation gait database.  In 2011 International Joint Conference on Biometrics (IJCB), pages 1–6, 2011.
  * [19] P. Punyani, R. Gupta, and A. Kumar.  Human age-estimation system based on double-level feature fusion of face and gait images.  International Journal of Image and Data Fusion, 9(3):222–236, 2018\.
  * [20] R. Rothe, R. Timofte, and L. V. Gool.  Deep expectation of real and apparent age from a single image without facial landmarks.  International Journal of Computer Vision, 126(2-4):144–157, 2018\.
  * [21] A. Sakata, N. Takemura, and Y. Yagi.  Gait-based age estimation using multi-stage convolutional neural network.  IPSJ Transactions on Computer Vision and Applications, 11(1), 2020\.
  * [22] M. Tan and Q. V. Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  CoRR, abs/1905.11946, 2019.
  * [23] C. Xu, Y. Makihara, R. Liao, H. Niitsuma, X. Li, Y. Yagi, and J. Lu.  Real-time gait-based age estimation and gender classification from a single image.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 3460–3470, January 2021.
  * [24] C. Xu, Y. Makihara, G. Ogi, X. Li, Y. Yagi, and J. Lu.  The ou-isir gait database comprising the large population dataset with age and performance evaluation of age estimation.  IPSJ Transactions on Computer Vision and Applications, 9(1):24, Dec 2017.
  * [25] C. Xu, Y. Makihara, G. Ogi, X. Li, Y. Yagi, and J. Lu.  The OU-ISIR gait database comprising the large population dataset with age and performance evaluation of age estimation.  IPSJ Transactions on Computer Vision and Applications, 9(1), 2017\.
  * [26] S. Xu, J. Fang, X. Hu, E. Ngai, Y. Guo, V. C. M. Leung, J. Cheng, and B. Hu.  Emotion recognition from gait analyses: Current research and future directions, 2020.
  * [27] Z. Yang, Y. Li, J. Yang, and J. Luo.  Action recognition with spatio–temporal visual attention on skeleton image sequences.  IEEE Transactions on Circuits and Systems for Video Technology, 29(8):2405–2415, 2019.
  * [28] K. Yi and J. Wu.  Probabilistic end-to-end noise correction for learning with noisy labels.  CoRR, abs/1903.07788, 2019.
  * [29] M. C. Younis and H. Abuhammad.  A hybrid fusion framework to multi-modal bio metric identification.  Multimedia Tools and Applications, pages 1–24, 2021.
  * [30] S. Yu, D. Tan, and T. Tan.  A framework for evaluating the effect of view angle, clothing and carrying condition on gait recognition.  In 18th International Conference on Pattern Recognition (ICPR’06), volume 4, pages 441–444, 2006.
  * [31] K. Zhang, C. Gao, L. Guo, M. Sun, X. Yuan, T. X. Han, Z. Zhao, and B. Li.  Age group and gender estimation in the wild with deep ror architecture.  CoRR, abs/1710.02985, 2017.
  * [32] K. Zhang, Z. Zhang, Z. Li, and Y. Qiao.  Joint face detection and alignment using multitask cascaded convolutional networks.  IEEE Signal Processing Letters, 23(10):1499–1503, 2016.
  * [33] Z. Zhang, Y. Song, and H. Qi.  Age progression/regression by conditional adversarial autoencoder.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2017.
  * [34] Z. Zhang, L. Tran, X. Yin, Y. Atoum, X. Liu, J. Wan, and N. Wang.  Gait recognition via disentangled representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [35] H. Zhu, Y. Zhang, G. Li, J. Zhang, and H. Shan.  Ordinal distribution regression for gait-based age estimation.  Science China Information Sciences, 63(2), 2020.