# Curvature estimation for meshes via algebraic quadric fitting

Marcel Makovník Corresponding author<EMAIL_ADDRESS>Pavel
Chalmovianský
Faculty of Mathematics, Physics and Informatics, Comenius University in
Bratislava

(April 2023)

###### Abstract

We introduce the novel method for estimation of mean and Gaussian curvature
and several related quantities for polygonal meshes. The algebraic quadric
fitting curvature (AQFC) is based on local approximation of the mesh vertices
and associated normals by a quadratic surface. The quadric is computed as an
implicit surface, so it minimizes algebraic distances and normal deviations
from the approximated point-normal neighbourhood of the processed vertex. Its
mean and Gaussian curvature estimate is then obtained as the respective
curvature of its orthogonal projection onto the fitted quadratic surface.
Experimental results for both sampled parametric surfaces and arbitrary meshes
are provided. The proposed method AQFC approaches the true curvatures of the
reference smooth surfaces with increasing density of sampling, regardless of
its regularity. It is resilient to irregular sampling of the mesh, compared to
the contemporary curvature estimators. In the case of arbitrary meshes,
obtained from scanning, AQFC provides robust curvature estimation.

##  1 Introduction

Characterization of the shape is well described for smooth curves and
surfaces. The basic notion of curvature is subject to differential geometry,
whose rigorous review may be found in e. g. [DC16] or [Spi99]. With the
development of computer graphics, the approximation of surfaces by piecewise
linear surfaces – polygon meshes – became predominant. Hence, the natural
question arises about how the geometric properties known for such surfaces
(especially smooth) may be described for their piecewise linear
approximations. The curvature estimation is widely used in areas like surface
segmentation [LKK15, BB20], mesh simplification [YHXL15], remeshing [SLC+19]
or feature line extraction [HPW05] and even in architecture [PLW+07].

Approaches for the estimation of curvature may be divided into several
categories. One of the most frequently used is the construction of discrete
curvature operators based solely on the geometry of the mesh. The second
approach estimates curvature by taking its value from the underlying
approximating surface.

We employ the approach, where we fit an implicit quadric to a small part of
the mesh. In contrary to the majority of methods, our contribution is, that we
use also vertex normals in the fitting and the quadric is fitted in algebraic
sense. This means, we do not minimize Euclidean distance, which usually leads
to solving least squares. Instead, we focus on algebraic distance which
approximates the Euclidean distance well in the vicinity of the fitted
quadric, see [Tau94]. Moreover, we minimize also the deviation between the
normals associated to vertices and the gradient of the fitted quadric.

The paper is organized as follows. In Section 2, we mention several frequently
used approaches for approximation of curvature for meshes. Then, we provide
the description of our approach for computation of curvatures using quadric
fitting in Section 3. The last part of our contribution, Section 5, is
dedicated to experimental results, comparing our approach to frequently used
methods on publicly available data. The quality of the approximating mesh and
its approximation of the curvature values are examined. The summary of our
work is found in Section 6.

##  2 Related works

The first works on approximation of curvatures on meshes were motivated not
only by needs of geometric modelling, but also by many algorithms used in
computer vision. One of the early approaches used construction of parametric
surface, which is a graph of a function given by a bivariate polynomial. For
each vertex of the triangle mesh, this polynomial approximated the distances
between the vertices of one-ring and the tangent plane passing through that
vertex [Ham93]. One-ring neighbourhood of the inspected vertex was used also
by Taubin in [Tau95] to estimate the curvature tensor. The proposed algorithm
works for triangle meshes, since the necessary vertex normals are computed
from face normals. The discretization of the curvature theory using mesh
paralellity was explored in [BPW10].

One of the most frequently used approximations was introduced in [MDSB03]. The
popularity of this method for meshes is caused by its simple implementation,
since the mean and Gaussian curvatures are computed using the areas and angles
of triangles adjacent to the explored vertex. In [YLH+06] the extraction of
principle curvatures was achieved using principal component analysis of local
neighbourhoods.

Another class of the estimation methods is to choose the curvature of the
underlying surface. Semenova estimated curvatures using quadric, which were
represented as functions in Monge form [SSH04]. The local fitting of a
biquadratic Bézier patch, whose control net was obtained by least squares
fitting, was utilized in [RB05]. Another method uses algebraic fit of spheres
for either point sets or point-normal sets, which immediately gives the value
of mean curvature by using the radius of the sphere [GG07]. Another way of
describing the underlying surface was presented in [ÖGG09], where moving least
squares are utilized. One of the main advantages of using the underlying
surface is, that it is independent on the graph structure of a polygon mesh,
i. e. the curvature may be described also for point clouds. Estimation of the
curvature per triangle rather than vertex was suggested in [ZGYL11]. Each
triangle, whose each corner was given by a vertex and an associated normal,
was interpolated by triangular Bézier patch and the first and the second
fundamental form was obtained from its parametrization.

A robust statistical approach for estimation of the curvature tensor was
introduced in [KSNS07]. The provided algorithm is capable of correcting the
noise in the meshes. Its extension for processing of point clouds was
introduced in [KNSS09]. Principled construction of discrete differential
operators may be used for computation of curvatures of arbitrary polygon
meshes, see [DGBD20]. Several analyses and empirical comparisons of curvature
estimation methods are available in [GG04, GG06, DM14, VVP+16] or [KWH18].

##  3 Curvature for implicit surfaces

Since in our research we are interested in algebraic fitting of the surfaces,
we enlist basic notions concerning implicit surfaces which are used throughout
our work. Subsequently, we include the curvature related notions in terms of
implicit surfaces.

Let $g:\mathbb{R}^{3}\rightarrow\mathbb{R}$ be a differentiable real valued
function of three variables. Then, an implicit surface $\mathcal{Z}(g)$ is the
set of all zeros of $g$, i. e.

$\mathcal{Z}(g)=\\{(x,y,z)^{\top}\in\mathbb{R}^{3}\>|\>g(x,y,z)=0\\}.$ (1)

The gradient of the implicit function $\nabla g(x,y,z)$ represents the normal
vector at the point $(x,y,z)^{\top}\in\mathcal{Z}(g)$. If the function
$q:\mathbb{R}^{3}\rightarrow\mathbb{R}$ is given by

$\begin{split}q(x,y,z)&=a_{11}x^{2}+a_{22}y^{2}+a_{33}z^{2}+a_{12}xy+a_{13}xz+a_{23}yz\\\
&+a_{14}x+a_{24}y+a_{34}z+a_{44},\end{split}$ (2)

with $a_{11},\ldots,a_{44}\in\mathbb{R}$ and at least one of the numbers
$a_{11},\ldots,a_{23}$ being non-zero, we obtain the surface $\mathcal{Z}(q)$
known as a quadratic surface or simply quadric.

Consider a regular surface $\mathcal{S}\subset\mathbb{R}^{3}$. For each point
$P\in\mathcal{S}$, we may determine the values $\kappa_{1}$ and $\kappa_{2}$,
called principal curvatures, that are the maximum and minimum of normal
curvatures at that point. For parametrized surfaces, the principal curvatures
$\kappa_{1}$ and $\kappa_{2}$ are easily computed using the coefficients of
the first and second fundamental forms [Spi99]. Subsequently, we may define
the two well-known measures of curvature – Gaussian curvature $K$ and mean
curvature $H$ given by

$K=\kappa_{1}\kappa_{2},\quad\text{and}\quad
H=\frac{\kappa_{1}+\kappa_{2}}{2}.$ (3)

For our needs, it is suitable to use curvature formulas, obtained from the
function $g:\mathbb{R}^{3}\rightarrow\mathbb{R}$ defining the implicit surface
$\mathcal{Z}(g)$. More precisely, these formulas rely on the gradient $\nabla
g$ and Hessian $\mathbf{H}_{g}$ of the function $g$. These formulas (and their
proofs) for both implicit planar curves and implicit surfaces may be found in
[Gol05]. The principal curvatures are derived from the Gaussian and mean
curvatures, as follows.

Let $g:\mathbb{R}^{3}\rightarrow\mathbb{R}$ and let $V$ be the regular point
of the corresponding surface $\mathcal{Z}(g)$. The Gaussian curvature $K$ at
the point $V$ is then given by

$K=\frac{\nabla g(V)^{\top}\,\text{adj}(\,\mathbf{H}_{g}(V)\,)\,\nabla
g(V)}{\|\nabla g(V)\|^{4}},$ (4)

and the mean curvature $H$ at $V$ is given by

$H=\frac{\nabla g(V)^{\top}\,\mathbf{H}_{g}(V)\,\nabla g(V)-\|\nabla
g(V)\|^{2}\,\text{tr}(\,\mathbf{H}_{g}(V)\,)}{2\|\nabla g(V)\|^{3}},$ (5)

where $\nabla g(V)$ and $\mathbf{H}_{g}(V)$ denote the value of the gradient
and the Hessian of the function $g$ at the point
$V=(x_{V},y_{V},z_{V})\in\mathcal{Z}(g)$, respectively. For completeness,
knowing the values $K$ and $H$ we can now easily compute the principal
curvatures as

$\kappa_{1,2}=H\pm\sqrt{H^{2}-K}.$ (6)

As introduced in [Koe90], one may define the measure of the size and shape
using the polar coordinates in the $(\kappa_{1},\kappa_{2})$-plane. Let
$\kappa_{1}$ and $\kappa_{2}$ be the principal curvatures of a point $V$ of
the regular surface $\mathcal{S}\subset\mathbb{R}^{3}$. Then, the number

$R=\sqrt{\frac{\kappa_{1}^{2}+\kappa_{2}^{2}}{2}}$ (7)

is called curvedness and the number

$S=-\frac{2}{\pi}\arctan\frac{\kappa_{1}+\kappa_{2}}{\kappa_{1}-\kappa_{2}}$
(8)

is called shape index at the point $V$.

The interpretation of curvedness and shape index might be more intuitive in
comparison to the traditional measures – the mean and Gaussian curvature.
Clearly, $R\geq 0$ and $-1\leq S\leq 1$. On contrary, the bounds of $H$ and
$K$ vary from surface to surface. The curvedness describes, what is the
difference between the surface and a plane in the vicinity of the point
$V\in\mathcal{S}$. The values of $R$ approaching zero signify more gently
curved points, while $R=0$ implies that the point is planar (i. e.
$\kappa_{1}=\kappa_{2}=0$). The values of $S$ determine the shape of a local
patch at the point $V$. This allows us to classify points – whether they are
elliptic, parabolic, hyperbolic or umbilic. Note, that the shape index is
indeterminate for planar points.

To compute curvedness and shape index for implicit surfaces, it is more
efficient to omit the computation of principal curvatures and use the Gaussian
and mean curvature instead. Then, the curvedness $R$ and shape index $S$ at
the point $V$ are given by

$R=\sqrt{2H^{2}-K},$ (9)

and

$S=-\frac{2}{\pi}\arctan 2\sqrt{H^{2}-K}.$ (10)

##  4 Quadric fitting curvature

In this section we propose the novel method, referred to as Algebraic quadric
fitting curvature (AQFC), to determine mean and Gaussian curvature at vertex
of a polygon mesh. The method AQFC is based on finding an underlying surface
to a certain area of the mesh, similarly as [GG07] and [ÖGG09]. More
precisely, the surface is a quadric fitted to a certain set of points and
their associated normals.

###  4.1 Input data and quadric computation

The proposed method may process any type of polygonal mesh
$\mathcal{M}=\left\\{\mathcal{V}_{\mathcal{N}},\mathcal{E},\mathcal{F}\right\\}$,
where $\mathcal{V}_{\mathcal{N}}$ is the set of vertex-normals, i. e. each
vertex is associated with a normal vector, and $\mathcal{E}$ and $\mathcal{F}$
are respectively the set of edges and faces. The vertex normals may be
prescribed or we may use any of the methods of the computation listed in
[JLW05], e. g. simple averaging of adjacent face normals or averaging weighted
by vertex angles.

For each processed vertex-normal $(V,\mathbf{n})\in\mathcal{V}_{\mathcal{N}}$,
we assign a neighbourhood $\mathcal{H}$ by finding the smallest possible
vertex ring (including $(V,\mathbf{n})$), containing fixed number of vertex-
normals. Subsequently, we determine a quadric $\mathcal{Z}(q)$ which is the
best approximation of $\mathcal{H}$ as follows.

Let $\mathcal{H}=\left\\{(V_{i},\mathbf{n}_{i})\right\\},\>i=1,...,m$. We
define an objective function $f:\mathbb{R}^{10}\rightarrow\mathbb{R}$ as

$f(a_{11},...,a_{44})=\sum_{i=1}^{m}\left(\omega_{V_{i}}q(V_{i})^{2}+\omega_{\mathbf{n}_{i}}\|\mathbf{n}_{i}-\nabla
q(V_{i})\|^{2}\right),$ (11)

where $\omega_{V_{i}},\omega_{\mathbf{n}_{i}}>0$ are fixed weights assigned to
the vertices $V_{i}$ and normals $\mathbf{n}_{i}$, respectively. The arguments
of the function $f$ are the coefficients of the unknown quadric $q$ and the
function accumulates the weighted squared algebraic distances between the
vertices and the surface $\mathcal{Z}(q)$ and deviations between gradients of
the quadric and input normal vectors of $\mathcal{H}$.

The coefficients of the fitted quadric are obtained by finding such
$a_{11},...,a_{44}$ that the function $f$ attains a minimal value. Since $f$
is a quadratic function, its global minimum is located at a critical point of
$f$. Assuming the Hessian of $f$ is positive definite, the coefficients are
obtained by solving the system of linear equations

$\dfrac{\partial f}{\partial a_{ij}}(a_{11},...,a_{44})=0,\quad 1\leq i\leq
j\leq 4.$ (12)

If we used unit weights for both vertices and normals, the quadric would fit
all the point-normals of the neighbourhood $\mathcal{H}$ with the same
importance. This may result in unexpected visual result, since we naturally
expect, that the quadric should fit the vertices in the first place. Also, the
quadric is assigned to the processed vertex-normal $(V,\mathbf{n})$. Hence, we
may modify the quadric in such way, that the point-normals closer to the
processed vertex-normal are approximated better, i. e. we use the weights

$\omega_{V_{i}}=\dfrac{1}{e^{\|V-V_{i}\|^{4}}},\quad\omega_{\mathbf{n}_{i}}=\frac{10^{-4}}{e^{\|\frac{\mathbf{n}}{\|\mathbf{n}\|}-\frac{\mathbf{n}_{i}}{\|\mathbf{n}_{i}\|}\|^{2}}},\quad
i=1,...,m.$ (13)

These weights reflect the Euclidean distance between $V_{i}$ and $V$ and
deviation between the normalized associated normal $\mathbf{n}_{i}$ and the
normalized processed normal $\mathbf{n}$.

###  4.2 Estimation of mean and Gaussian curvature

Let $p(V)$ be the orthogonal projection of $V$ onto the quadric
$\mathcal{Z}(q)$ given by

$p(V)=\operatorname*{arg\,min}_{W\in\mathcal{Z}(q)}\|V-W\|.$ (14)

Obviously, for the point of the quadratic surface $V\in\mathcal{Z}(q)$, we
have $p(V)=V$. Geometrically, the point $p(V)$ is the footpoint of the point
$V$ onto the tangent plane of $\mathcal{Z}(q)$ at the point $p(V)$. In other
words, the vector $V-p(V)$ and the gradient $\nabla q(p(V))$ are linearly
dependent, as seen in Figure 1.

$V$
---
$\mathcal{Z}(q)$
---
$p(V)$
---
$\nabla q(p(V))$
---
Figure 1: Projection of the point $V$ onto the quadratic surface
$\mathcal{Z}(q)$.

Also, let $s(\mathbf{n},V)$ denote the gradient with corrected length given by

$s(\mathbf{n},V)=\|\mathbf{n}\|\frac{\nabla q(p(V))}{\|\nabla q(p(V))\|}.$
(15)

The estimate of the mean curvature $\tilde{H}$ and Gaussian curvature
$\tilde{K}$ assigned to the vertex-normal $(V,\mathbf{n})$ are computed as

$\tilde{K}=\frac{s(\mathbf{n},V)^{\top}\,\text{adj}(\,\mathbf{H}_{q}(p(V))\,)\,s(\mathbf{n},V)}{\|s(\mathbf{n},V)\|^{4}}$
(16)

and

$\tilde{H}=\frac{s(\mathbf{n},V)^{\top}\,\mathbf{H}_{q}(p(V))\,s(\mathbf{n},V)-\|s(\mathbf{n},V)\|^{2}\,\text{tr}(\,\mathbf{H}_{q}(p(V))\,)}{2\|s(\mathbf{n},V)\|^{3}}.$
(17)

Note, that we intentionally compute the curvatures at the point $p(V)$ instead
of the point $V$. The reason is, that the point $p(V)$ is the point of the
quadric $\mathcal{Z}(q)$, hence the respective gradient is not distorted by
the displacement of the point $V$. The possible error caused by the
computation of the gradient at the point $V$ would be reflected also in its
norm. The displacement of $V$ does not affect the Hessian, since $q$ is given
by quadratic polynomial. However, the error would be magnified in the
computation of the mean and Gaussian curvatures, since the third and fourth
power of the gradient norm is present in the denominators of the respective
formulas. For the same reason, we rescale the original gradient $\nabla
q(p(V))$ by the length of the vector $\mathbf{n}$ in the estimations.

All remaining notions related to curvature – principal curvatures, curvedness
and shape index – may be computed using the respective formulas (6), (9) and
(10).

##  5 Experimental results

In this part, we explore the suitability of AQFC for estimating curvatures on
polygon meshes. Firstly, we describe the dataset, on which the experiments are
made. For each mesh of the dataset we emphasize the features which may affect
the precision of the curvature estimations. Then, we describe the measures
used for the comparison. Finally, we provide the illustrations and measured
values for the experiments and discuss the pros and cons of our method with
respect to the selected competitors.

###  5.1 Meshes for testing

We compare our method on several categories of polygonal meshes, whose
description is provided below. The selected meshes are representative for the
purposes of the error measurement, described in Subsection 5.2.

####  5.1.1 Regularly sampled surfaces

The regular sampling of a surface is obtained from its parametric equations
given by the function $\mathbf{s}:\mathcal{D}\rightarrow\mathbb{R}^{3}$, where
$\mathcal{D}\subset\mathbb{R}^{2}$.

For testing, we consider the torus $\mathbf{s}_{\mathbb{T}^{2}}$ with the
minor radius equal to $1$ and the major radius being $3$. Its parametrization
is given by

$\mathbf{s}_{\mathbb{T}^{2}}(\theta,\varphi)=\begin{pmatrix}(3+\cos\theta)\cos\varphi\\\
(3+\cos\theta)\sin\varphi\\\
\sin\theta\end{pmatrix},\quad(\theta,\varphi)\in[0,2\pi)\times[0,2\pi).$ (18)

The mean and Gaussian curvature is computed directly from the parametrization
as

$H_{\mathbb{T}^{2}}(\theta,\varphi)=-\frac{3+2\cos\theta}{2(3+\cos\theta)},$
(19)

and

$K_{\mathbb{T}^{2}}(\theta,\varphi)=\frac{\cos\theta}{3+\cos\theta},$ (20)

respectively. By computing extrema of functions
$H_{\mathbb{T}^{2}}(\theta,\varphi)$ and $K_{\mathbb{T}^{2}}(\theta,\varphi)$,
we get the bounds of the mean and Gaussian curvatures, which are

$\begin{split}-0.65&\leq H_{\mathbb{T}^{2}}(\theta,\varphi)\leq-0.25\\\
-0.5&\leq K_{\mathbb{T}^{2}}(\theta,\varphi)\leq 0.25.\end{split}$ (21)

By uniform sampling of the domain for parameters $\theta$ and $\varphi$, we
constructed the quad meshes with 400, 3,600, 10,000, 360,000 and 1,000,000
vertices. Our aim is to inspect the behaviour of curvature estimation for
increasing level of detail of the respective meshes.

####  5.1.2 Surfaces with irregular sampling

Having a parametrization $\mathbf{s}(\theta,\varphi)$ of the surface, we
randomly choose the fixed number $m$ of distinct pairs
$(\theta_{i},\varphi_{i})\in\mathcal{D}$, $i=1,...,m$. The samples are then
obtained by plugging these random values of the parameters into the
parametrization surface, i. e. the vertices $V_{i}\in\mathcal{V}$ of the mesh
are given by points $\mathbf{s}(\theta_{i},\varphi_{i})$ for $i=1,...,m$.

The faces of the mesh are given by the triangulation of the set of vertices
$\mathcal{V}$ obtained from Ball pivoting algorithm [BMR+99]. The input
parameters for pivoting were manually adjusted to obtain the mesh with as few
holes as possible. The remaining holes were enclosed, so the resulting mesh
has no boundary. For testing, we use the irregular sampling of the torus
$\mathbf{s}_{\mathbb{T}^{2}}(\theta,\varphi)$ (18) with 10,000 vertices.

The mesh obtained by this procedure is irregular in terms of edge lengths, the
ratio of obtuse and acute triangles, their areas and valence of the vertices.
Our aim is to test the robustness of the curvature estimation with respect to
such irregularities.

Another instance of the irregular sampling is the one obtained from a unit
sphere as follows. In the first step, we constructed the regular sampling of
the sphere from its parametrization, similarly to the case of torus. Then, we
split each quad face into two triangles by choosing a random diagonal of that
quadrilateral. The multiple vertices at the poles of the sphere were merged to
avoid degenerate faces. The resulting sphere has $482$ vertices. The main
feature of the unit sphere is, that its mean and Gaussian curvatures are equal
and constant, that is

$H_{\mathbb{S}^{2}}=K_{\mathbb{S}^{2}}=1.$ (22)

This sampling of the unit sphere is not as irregular as the sampling of the
torus. Our goal is to check if even slight changes in the regularity of the
sampling affect the precision of the estimation of the curvature.

####  5.1.3 Meshes obtained from scanning

We provide comparison also on the meshes – Retheur and Damme Assise – which
are obtained by the surface reconstruction of the point cloud from the 3D
scanning. These models are publicly available in the test dataset used in
[YWH+19]. The meshes have approximately 250,000 vertices.

###  5.2 Tested methods and error measurement

For comparison, we selected the curvature estimation by two commonly used
state-of-the-art methods. The first one is DDGO [MDSB03], which estimates
curvature directly from the geometry of the input mesh. The second competitor
is APSS [GG07], which is a method based on describing the underlying surface,
similarly as our method AQFC. We used the Python library PyMeshLab [MC21] for
the computation of curvatures using DDGO and APSS.

For fairness, we consider all tested meshes without prescribed normals at
vertices, even if they may be obtained from the parametrization or implicit
equation of the sampled surface. For computation of vertex normals necessary
for AQFC, we used the simple averaging of adjacent face normals.

For each method, we inspect separately on Gaussian curvature and mean
curvature. Consider an input mesh
$\mathcal{M}=\\{\mathcal{V},\mathcal{E},\mathcal{F}\\}$. For any vertex
$V\in\mathcal{V}$, let us denote by $\tilde{K}$ the estimation of Gaussian
curvature obtained by either AQFC, DDGO or APSS. By $K$ we denote the Gaussian
curvature of the underlying surface. Then, we propose the following three
measures $K_{avg},K_{min},K_{max}\in\mathbb{R}$ given by

$\begin{split}K_{avg}&=\frac{1}{|\mathcal{V}|}\sum_{V\in\mathcal{V}}|\tilde{K}-K|,\\\
K_{min}&=\min_{V\in\mathcal{V}}\>\tilde{K},\\\
K_{max}&=\max_{V\in\mathcal{V}}\>\tilde{K}.\end{split}$ (23)

The meshes in the dataset are obtained by sampling of a surface, where the
curvature may be computed for each sample (vertex of the mesh). Hence, we may
measure the absolute value of the difference between the estimated and true
curvature at any mesh vertex. The value $K_{avg}$ is a mean value of such
differences and it provides us with the information how precisely each method
approximates the curvatures of the underlying surface. Also, we inspect on the
minimal and maximal values $K_{min}$ and $K_{max}$ to see, how well are the
bounds of the curvature preserved. The difference between the bounds of
estimated and true curvatures also shows the robustness of the estimates to
outliers, caused by the features of the sampled mesh.

Analogously, we define the measures $H_{avg},H_{min},H_{max}\in\mathbb{R}$ for
mean curvature. These are dependent on the estimated values $\tilde{H}$ and
the true values $H$ of mean curvature for any $V\in\mathcal{V}$. Hence,

$\begin{split}H_{avg}&=\frac{1}{|\mathcal{V}|}\sum_{V\in\mathcal{V}}|\tilde{H}-H|,\\\
H_{min}&=\min_{V\in\mathcal{V}}\>\tilde{H},\\\
H_{max}&=\max_{V\in\mathcal{V}}\>\tilde{H}.\end{split}$ (24)

If the computed values of the proposed error measures for Gaussian and mean
curvature are sufficiently small for certain method, we may assume that the
method correctly estimates the principal curvatures, curvedness and shape
index as well. Hence, the latter are not subject of our interest for the
included experiments on regular and irregular sampling of the surfaces.

In the case of the meshes from 3D scans, we inspect on curvedness rather than
Gaussian and mean curvature, since their bounds are unknown. We visualize the
distribution of the curvedness across the tested meshes. We are interested in
the presence of noise in the distribution. In this case, the noise is
perceived as the difference in curvedness within small homogeneous region of
the mesh. For instance, in the areas with small curvedness (almost planar
areas), we expect no vertices with high curvedness.

-0,64
---
-0,635
---
-0,63
---
-0,625
---
-0,62
---
-0,615
---
400
---
3600
---
10000
---
360000
---
1000000
---
H
---
min
---
AQFC (proposed)
---
DDGO
---
APSS
---
-0,27
---
-0,26
---
-0,25
---
-0,24
---
-0,23
---
-0,22
---
-0,21
---
400
---
3600
---
10000
---
360000
---
1000000
---
H
---
max
---
AQFC (proposed)
---
DDGO
---
APSS
---
0
---
0,005
---
0,01
---
0,015
---
0,02
---
400
---
3600
---
10000
---
360000
---
1000000
---
H
---
avg
---
AQFC (proposed)
---
DDGO
---
APSS
---
(i) Mean curvature.

0,245
---
0,25
---
0,255
---
0,26
---
0,265
---
0,27
---
400
---
3600
---
10000
---
360000
---
1000000
---
K
---
max
---
AQFC (proposed)
---
DDGO
---
APSS
---
0
---
0,005
---
0,01
---
0,015
---
400
---
3600
---
10000
---
360000
---
1000000
---
K
---
avg
---
AQFC (proposed)
---
DDGO
---
APSS
---
-0,55
---
-0,53
---
-0,51
---
-0,49
---
-0,47
---
400
---
3600
---
10000
---
360000
---
1000000
---
K
---
min
---
AQFC (proposed)
---
DDGO
---
APSS
---
(ii) Gaussian curvature.

Figure 2: The comparison of different methods of the minimal, maximal and
average values for estimation of mean and Gaussian curvature on the regularly
sampled torus at various levels of detail. The values on the horizontal axis
denote the number of vertices of the sampled meshes.

###  5.3 Comparison with other methods and discussion

In this subsection, we provide the measurements of curvature on the meshes
from Subsection 5.1, using the proposed method AQFC and methods DDGO and APSS.
The figures of the meshes and their colourings were created using MeshLab
[CCC+08].

$\tilde{H}=-1.15$
---
$\tilde{H}=-0.85$
---

(a) Input
---

(b) AQFC (proposed)
---

(c) DDGO
---

(d) APSS
---

$\tilde{K}=0.85$
---
$\tilde{K}=1.15$
---
Figure 3:  The estimation of mean (left column) and Gaussian (right column)
curvatures on the irregularly sampled sphere with $482$ vertices.

####  5.3.1 Estimation precision with respect to level of detail

For all methods, we measured minimal, maximal and average mean and Gaussian
curvatures (see (23) and (24)) of the regularly sampled torus at various level
of density, as described in Subsection 5.1. The values of the measurements are
provided in Figure 2(i) and 2(ii), respectively.

As seen in these charts, the best average deviation values of both mean and
Gaussian curvature were obtained by DDGO for the sampling of 400 vertices. The
average deviations $H_{avg}$ and $K_{avg}$ produced by the proposed method
AQFC for 3,600 and 10,000 were comparable to the ones given by DDGO.
Nevertheless, we consider these values to be satisfactory since the
approximation of lower bounds $H_{min}$, $K_{min}$ and upper bounds $H_{max}$,
$K_{max}$ were similar to DDGO and both of them approximate the true bounds of
that torus (21) fair well. The method APSS was not able to approximate upper
bound of mean curvature $H_{max}$ and the lower bound of Gaussian curvature
$K_{min}$ sufficiently. For illustration, we depict the distribution of
curvatures on the torus with 10,000 vertices in Figure 4(i). The lower and
upper bounds are cropped to the values of true bounds. Visually, all three
methods depict curvatures correctly, except for the mean curvature from APSS
(row (c) left), where the graduation from the areas with low mean curvature to
the areas with higher is sharper.

If the torus is finely sampled, that is
$|\mathcal{V}|=\text{360,000},\text{1,000,000}$, the method AQFC outperformed
both DDGO and APSS. The average deviations are significantly smaller for both
mean and Gaussian curvature. Also the upper and lower bounds were best
preserved by our proposed method.

$\tilde{H}=-0.65$
---
$\tilde{H}=-0.25$
---

(a) Input
---

(b) AQFC (proposed)
---

(c) DDGO
---

(d) APSS
---

$\tilde{K}=-0.5$
---
$\tilde{K}=0.25$
---
(i) Regular sampling.

$\tilde{H}=-0.65$
---
$\tilde{H}=-0.25$
---

(a) Input
---

(b) AQFC (proposed)
---

(c) DDGO
---

(d) APSS
---

$\tilde{K}=-0.5$
---
$\tilde{K}=0.25$
---
(ii) Irregular sampling.

Figure 4:  The estimation of mean (left column) and Gaussian (right column)
curvatures on the sampled torus with 10,000 vertices with different sampling.

####  5.3.2 Influence of sampling regularity on estimation

For the irregular sampling of torus and sphere, we calculate the same measures
as in the case of regular sampling. The measured values for both meshes are
present in Table 1.

As indicated by average deviations in this table, the method AQFC is
remarkably better in handling of irregular sampling. The approximation of the
bounds is worse than in the case of regular sampling of the torus. However,
the irregularities cause major issues for estimation of the bounds for both
DDGO and APSS. The distributions of curvatures across the torus are shown in
Figure 4(ii). Note, that the cropping of the color scale to the bounds of true
values affects the colouring of the meshes. Still, we are able to notice for
how many vertices the curvatures were estimated fair well. As seen in the row
(b) of Figure 4(ii), the method AQFC produces only minor disruptions in the
vertex curvatures compared to the estimation on the regular sampling (see
Figure 4(i) (b)).

Now, we discuss the case of the sphere, whose irregularities are caused only
by flipping some of the diagonals of the regularly sampled quadrilaterals. The
depiction of curvatures for the sphere are provided in Figure 3. The color
scale is adjusted, so it covers the majority of deviations produced by the
tested methods. As seen in the row (d), the problems with estimation by APSS
were mainly at the poles of the spheres, which were vertices with high
valence. The method DDGO (row (c)) produced bad estimates in the areas where
the regularity of the sampling was violated by flipped edges and these
deviations are magnified nearer to the poles. The estimation by our method
(row (b)) is not visibly affected by the slight irregularities in sampling.

| Torus
---|---
|  AQFC (proposed) | DDGO | APSS
$H_{min}$ | -0.627818 | -30.7685 | -0.57315
$H_{max}$ | -0.244277 | 21.7019 | 0.0500141
$H_{avg}$ | 0.00651111 | 0.0874593 | 0.220647
$K_{min}$ | -0.503117 | -318.85 | -1.29606
$K_{max}$ | 0.251109 | 3232.91 | 0.925429
$K_{avg}$ | 0.00687775 | 0.909176 | 0.0962692
| Sphere
|  AQFC (proposed) | DDGO | APSS
$H_{min}$ | -1.03639 | -1.14966 | -1.07738
$H_{max}$ | -0.997533 | -0.890629 | 0.0058888
$H_{avg}$ | 0.00191217 | 0.0113342 | 0.0214852
$K_{min}$ | 0.995068 | 0.894789 | -0.00106665
$K_{max}$ | 1.0741 | 1.15526 | 1.16044
$K_{avg}$ | 0.00383101 | 0.0163219 | 0.0405045
Table 1: The comparison of different methods of the minimal, maximal and
average values for estimation of mean and Gaussian curvature on the
irregularly sampled torus with 10,000 vertices and sphere with 482 vertices.
The lowest average of deviations are highlighted by bold. Note, that the best
approximation of minimal and maximal values of curvatures is achieved by using
AQFC.

$R=0$
---
$R=200$
---
(a) Input
---
(b) AQFC (proposed)
---
(c) DDGO
---
(d) APSS
---
(i)  Curvedness $R$ on the model of Retheur with 250,562 vertices (a).
Curvature estimation by the proposed method AQFC (b) generates less noise than
the methods DDGO (c) and APSS (d).

$R=0$
---
$R=200$
---
(a) Input
---
(b) AQFC (proposed)
---
(c) DDGO
---
(d) APSS
---
(ii)  Curvedness $R$ on the model of Dame Assise with 257,818 vertices (a).
Curvature estimation by the proposed method AQFC (b) highlights the features
(wrinkles, sharp edges) without significant disruption compared to DDGO (c)
and APSS (d).

Figure 5: Curvedness distribution over meshes.

####  5.3.3 Curvedness distribution over meshes

Finally, we compared the tested method on real data meshes obtained from
scanning. The comparison of curvedness distribution for Retheus is depicted in
Figure 5(i) and for Dame Assise in Figure 5(ii). Since the curvedness
generally has no upper bound, we set the colour scale to the interval
$[0,200]$, so all features of the mesh are visible.

In the case of Retheus, the noise in the curvedness distribution is present
for both DDGO and APSS (Figure 5(i) (c) and (d)). The most notable disruption
is in the areas of the forehead and the left part of the chest, which may be
perceived as homogeneous areas in terms of the curvedness. On contrary, the
proposed AQFC does not produce any significant noise and the main features,
characterized by high curvedness (blue color in the figure), are easily
recognizable, e. g. curls on the beard, creases on the toga or the sharp edges
of the pedestal. The slight deviations of curvatures are present in the smooth
areas, e. g. chest, however these are caused by the material of the scanned
statue and are considered the feature of the mesh as well.

The effect of imprecise curvedness estimation by DDGO and APSS is even more
visible in the case of Dame Assise, see Figure 5(ii) (c) and (d). The features
like creases on the dress or parts of the face are hardy distinguishable.
However, AQFC captures even the fine details as waviness of the bottom part of
the dress (Figure 5(ii) (b)).

##  6 Conclusion

In our work, we introduced mean and Gaussian curvature estimation method AQFC,
which is based on local algebraic fitting of quadratic surfaces. AQFC is
capable to process arbitrary polygon meshes, whose vertices are equipped with
associated normal vectors.

The experimental results indicate, that AQFC is feasible for estimation of the
mean and Gaussian curvature and their derivatives. We consider our method to
be more universal albeit the well established method DDGO provides more
precise results for the regular sampling of the surfaces. However, DDGO fails
to provide satisfactory results for meshes with irregular sampling. Even if
APSS is less prone to irregularities compared to DDFO, AQFC provides more
precise estimate of curvatures.

The proposed method AQFC is also robust at the computation of curvedness for
meshes, where the prescription of the underlying surface is unknown. Thus, it
has potential to be used in various application as denoising or smoothing of
the meshes.

In future work we plan on to extend this approach for processing of point
clouds. The modifications that need to be made is the way of obtaining
neighbourhood since edges and faces are not present. This may be solved by
using the feasible space partitioning structure as octrees or $k$-d trees.

## References

  * [BB20] Mohamed Yaghmorasan Benzian and Nacéra Benamrane.  3d mesh segmentation by region growing based on discrete curvature.  In 2020 1st International Conference on Communications, Control Systems and Signal Processing (CCSSP), pages 271–276. IEEE, 2020.
  * [BMR+99] Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Cláudio Silva, and Gabriel Taubin.  The ball-pivoting algorithm for surface reconstruction.  IEEE Transactions on Visualization and Computer Graphics, 5(4):349–359, 1999.
  * [BPW10] Alexander I Bobenko, Helmut Pottmann, and Johannes Wallner.  A curvature theory for discrete surfaces based on mesh parallelity.  Mathematische annalen, 348:1–24, 2010.
  * [CCC+08] Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia.  MeshLab: an Open-Source Mesh Processing Tool.  In Vittorio Scarano, Rosario De Chiara, and Ugo Erra, editors, Eurographics Italian Chapter Conference. The Eurographics Association, 2008.
  * [DC16] Manfredo P. Do Carmo.  Differential geometry of curves and surfaces: revised and updated second edition.  Courier Dover Publications, 2016.
  * [DGBD20] Fernando De Goes, Andrew Butts, and Mathieu Desbrun.  Discrete differential operators on polygonal meshes.  ACM Transactions on Graphics (TOG), 39(4):110–1, 2020.
  * [DM14] Julie Digne and Jean-Michel Morel.  Numerical analysis of differential operators on raw point clouds.  Numerische Mathematik, 127:255–289, 2014.
  * [GG04] Tim Gatzke and Cindy Grimm.  Improved curvature estimation on triangular meshes.  2004\.
  * [GG06] Timothy D Gatzke and Cindy M Grimm.  Estimating curvature on triangular meshes.  International journal of shape modeling, 12(01):1–28, 2006.
  * [GG07] Gaël Guennebaud and Markus Gross.  Algebraic point set surfaces.  In ACM Transactions on Graphics, pages 23–es. 2007.
  * [Gol05] Ron Goldman.  Curvature formulas for implicit curves and surfaces.  Computer Aided Geometric Design, 22(7):632–658, 2005.
  * [Ham93] Bernd Hamann.  Curvature approximation for triangulated surfaces.  In Geometric Modelling, pages 139–153. Springer, 1993.
  * [HPW05] Klaus Hildebrandt, Konrad Polthier, and Max Wardetzky.  Smooth feature lines on surface meshes.  In Symposium on geometry processing, pages 85–90, 2005.
  * [JLW05] Shuangshuang Jin, Robert R. Lewis, and David West.  A comparison of algorithms for vertex normal computation.  The Visual Computer, 21(1):71–82, 2005.
  * [KNSS09] Evangelos Kalogerakis, Derek Nowrouzezahrai, Patricio Simari, and Karan Singh.  Extracting lines of curvature from noisy point clouds.  Computer-Aided Design, 41(4):282–292, 2009.
  * [Koe90] Jan J. Koenderink.  Solid shape, volume 2.  MIT press Cambridge, MA, 1990.
  * [KSNS07] Evangelos Kalogerakis, Patricio Simari, Derek Nowrouzezahrai, and Karan Singh.  Robust statistical estimation of curvature on discretized surfaces.  In Symposium on Geometry Processing, volume 13, pages 110–114, 2007\.
  * [KWH18] Markus Kronenberger, Oliver Wirjadi, and Hans Hagen.  Empirical comparison of curvature estimators on volume images and triangle meshes.  IEEE transactions on visualization and computer graphics, 25(10):3032–3041, 2018.
  * [LKK15] Jung Lee, Seokhun Kim, and Sun-Jeong Kim.  Mesh segmentation based on curvatures using the gpu.  Multimedia Tools and Applications, 74:3401–3412, 2015.
  * [MC21] Alessandro Muntoni and Paolo Cignoni.  PyMeshLab, January 2021.
  * [MDSB03] Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H. Barr.  Discrete differential-geometry operators for triangulated 2-manifolds.  In Visualization and Mathematics III, pages 35–57. Springer, 2003\.
  * [ÖGG09] Cengiz Öztireli, Gaël Guennebaud, and Markus Gross.  Feature preserving point set surfaces based on non-linear kernel regression.  In Computer Graphics Forum, volume 28, pages 493–501. Wiley Online Library, 2009.
  * [PLW+07] Helmut Pottmann, Yang Liu, Johannes Wallner, Alexander Bobenko, and Wenping Wang.  Geometry of multi-layer freeform structures for architecture.  In ACM SIGGRAPH 2007 papers, pages 65–es. 2007.
  * [RB05] Anshuman Razdan and MyungSoo Bae.  Curvature estimation scheme for triangle meshes using biquadratic bézier patches.  Computer-Aided Design, 37(14):1481–1491, 2005.
  * [SLC+19] Kehua Su, Na Lei, Wei Chen, Li Cui, Hang Si, Shikui Chen, and Xianfeng Gu.  Curvature adaptive surface remeshing by sampling normal cycle.  Computer-Aided Design, 111:1–12, 2019.
  * [Spi99] Michael Spivak.  A comprehensive introduction to differential geometry, volume 2.  Publish or Perish, Incorporated, 1999.
  * [SSH04] Irina Semenova, Vladimir Savchenko, and Ichiro Hagiwara.  Curvature based mesh improvement.  WSEAS Transactions on Systems, 3(4):1346–1354, 2004.
  * [Tau94] Gabriel Taubin.  Distance approximations for rasterizing implicit curves.  ACM Transactions on Graphics (TOG), 13(1):3–42, 1994.
  * [Tau95] Gabriel Taubin.  Estimating the tensor of curvature of a surface from a polyhedral approximation.  In Proceedings of IEEE International Conference on Computer Vision, pages 902–907. IEEE, 1995.
  * [VVP+16] Libor Váša, Petr Vaněček, Martin Prantl, Vera Skorkovská, Petr Martínek, and Ivana Kolingerová.  Mesh statistics for robust curvature estimation.  In Computer Graphics Forum, volume 35, pages 271–280. Wiley Online Library, 2016.
  * [YHXL15] Li Yao, Shihui Huang, Hui Xu, and Peilin Li.  Quadratic error metric mesh simplification algorithm based on discrete curvature.  Mathematical Problems in Engineering, 2015, 2015.
  * [YLH+06] Yong-Liang Yang, Yu-Kun Lai, Shi-Min Hu, Helmut Pottmann, et al.  Robust principal curvatures on multiple scales.  In Symposium on Geometry Processing, pages 223–226, 2006.
  * [YWH+19] Wang Yifan, Shihao Wu, Hui Huang, Daniel Cohen-Or, and Olga Sorkine-Hornung.  Patch-based progressive 3D point set upsampling.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5958–5967, 2019.
  * [ZGYL11] Mao Zhihong, Cao Guo, Ma Yanzhao, and Kunwoo Lee.  Curvature estimation for meshes based on vertex normal triangles.  Computer-Aided Design, 43(12):1561–1566, 2011.


# Encoding Projective Dependency Trees with 4-Bit Labels

Carlos Gómez-Rodríguez, Diego Roca and David Vilares
Universidade da Coruña, CITIC
Departamento de Ciencias de la Computación y Tecnologías de la Información
Campus de Elviña s/n, 15071
A Coruña, Spain
{carlos.gomez, d.roca1<EMAIL_ADDRESS>

# Encoding Projective Dependency Trees with 4-Bit Labels, and Non-Projectivity
with 7

Carlos Gómez-Rodríguez, Diego Roca and David Vilares
Universidade da Coruña, CITIC
Departamento de Ciencias de la Computación y Tecnologías de la Información
Campus de Elviña s/n, 15071
A Coruña, Spain
{carlos.gomez, d.roca1<EMAIL_ADDRESS>

# Encoding Projective and Non-Projective Dependency Trees with 4- and 7-bit
labels

Carlos Gómez-Rodríguez, Diego Roca and David Vilares
Universidade da Coruña, CITIC
Departamento de Ciencias de la Computación y Tecnologías de la Información
Campus de Elviña s/n, 15071
A Coruña, Spain
{carlos.gomez, d.roca1<EMAIL_ADDRESS>

# 4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees

Carlos Gómez-Rodríguez, Diego Roca and David Vilares
Universidade da Coruña, CITIC
Departamento de Ciencias de la Computación y Tecnologías de la Información
Campus de Elviña s/n, 15071
A Coruña, Spain
{carlos.gomez, d.roca1<EMAIL_ADDRESS>

###### Abstract

We introduce an encoding for syntactic parsing as sequence labeling that can
represent any projective dependency tree as a sequence of 4-bit labels, one
per word. The bits in each word’s label represent (1) whether it is a right or
left dependent, (2) whether it is the outermost (left/right) dependent of its
parent, (3) whether it has any left children and (4) whether it has any right
children. We show that this provides an injective mapping from trees to labels
that can be encoded and decoded in linear time. We then define a 7-bit
extension that represents an extra plane of arcs, extending the coverage to
almost full non-projectivity (over 99.9% empirical arc coverage). Results on a
set of diverse treebanks show that our 7-bit encoding obtains substantial
accuracy gains over the previously best-performing sequence labeling
encodings.

##  1 Introduction

Approaches that cast parsing as sequence labeling have gathered interest as
they are simple, fast (Anderson and Gómez-Rodríguez, 2021), highly
parallelizable (Amini and Cotterell, 2022) and produce outputs that are easy
to feed to other tasks (Wang et al., 2019). Their main ingredient are the
encodings that map trees into sequences of one discrete label per word. Thus,
various such encodings have been proposed both for constituency (Gómez-
Rodríguez and Vilares, 2018; Amini and Cotterell, 2022) and dependency parsing
(Strzyz et al., 2019; Lacroix, 2019; Gómez-Rodríguez et al., 2020).

Most such encodings have an unbounded label set, whose cardinality grows with
sentence length. An exception for constituent parsing is tetratagging (Kitaev
and Klein, 2020). For dependency parsing, to our knowledge, no bounded
encodings were known. Simultaneously to this work, Amini et al. (2023) have
just proposed one: hexatagging, where projective dependency trees are
represented by tagging each word with one of a set of 8 tags.111The “hexa” in
the name comes from a set of six atoms used to define the labels. However, the
label for each word is composed of two such atoms (one from a set of two, and
other from a set of four) so there are eight possible labels per word.

[theme = simple] [row sep=.70em, column sep=1.0em,font=] & & & & & & &
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7
-ROOT- & It & should & continue & to & be & defanged & .

& <* & < & \>*/ & <* & < & \> & >*

& 0100 & 0000 & 1111 & 0100 & 0000 & 1010 & 1100
[edge style=black]42 [edge style=black]43 [edge style=black]14 [edge
style=black]75 [edge style=black]76 [edge style=black]47 [edge style=black]48

Figure 1: A dependency tree and its 4-bit encoding.

#### Contribution

We present a bounded sequence-labeling encoding that represents any projective
dependency tree with 4 bits (i.e., 16 distinct labels) per word. While this
requires one more bit than hexatagging, it is arguably more straightforward,
as the bits directly reflect properties of each node in the dependency tree
without an intermediate constituent structure, as hexatagging requires. Also,
it has a clear relation to existing bracketing encodings, and has a
straightforward non-projective extension using 7 bits with almost full non-
projective coverage. Empirical results show that our encoding provides more
accurate parsers than the existing unbounded bracketing encodings, which had
the best previous results among sequence-labeling encodings, although it
underperforms hexatagging.

##  2 Projective Encoding

Let $T_{n}$ be a set of unlabeled dependency trees222For simplicity, we ignore
dependency labels in definitions. In the implementation, they are added as a
separate component to the label of each word, following common practice. for
sentences of length $n$. A sequence-labeling encoding defines a function
$\Phi_{n}:T_{n}\rightarrow L^{n}$, for a label set $L$. Thus, each tree for a
sentence $w_{1}\ldots w_{n}$ is encoded as a sequence of labels, $l_{1}\ldots
l_{n}$, that assigns a label $l_{i}\in L$ to each word $w_{i}$.

We define the _4-bit projective encoding_ as an encoding where $T_{n}$ is the
set of projective dependency trees, and we assign to each word $w_{i}$ a label
$l_{i}=b_{0}b_{1}b_{2}b_{3}$, such that $b_{j}$ is a boolean as follows:

  * •

$b_{0}$ is true if $w_{i}$ is a right dependent, and false if it is a left
dependent. Root nodes are considered right dependents for this purpose (i.e.,
we assume that they are linked as dependents of a dummy root node $w_{0}$
located to the left).

  * •

$b_{1}$ is true iff $w_{i}$ is the outermost right (or left) dependent of its
parent node.

  * •

$b_{2}$ (respectively, $b_{3}$) is true iff $w_{i}$ has one or more left
(right) dependents.

All combinations of the four bits are possible, so we have 16 possible labels.

For easier visualization and comparison to existing bracketing encodings, we
will represent the values of $b_{0}$ as > (right dependent) or < (left
dependent), $b_{1}$ as * (true) or blank (false), and $b_{2}$ and $b_{3}$
respectively as \ and / (true) or blank (false). We will use these
representations with set notation to make claims about a label’s bits, e.g.
$\texttt{>*}\in l$ means that label $l$ has $b_{0}=1,b_{1}=1$. Figure 1 shows
a sample tree encoded with this method.

We will now show how to encode and decode trees, and prove that the encoding
is a total, injective map from projective trees to label sequences.

#### Encoding and Totality

Encoding a tree is trivial: one just needs to traverse each word and apply the
definition of each bit to obtain the label. This also means that our encoding
from trees to labels is a total function, as the labels are well defined for
any dependency tree (and thus, for any projective tree).

#### Decoding and Injectivity

Assuming a well-formed sequence of labels, we can decode it to a tree. We can
partition the arcs of any tree $t\in T_{n}$ into a subset of left arcs,
$t_{l}$, and a subset of right arcs, $t_{r}$. We will decode these subsets
separately. Algorithm 1 shows how to obtain the arcs of $t_{r}$.

1:function DecodeRightArcs($l_{1}..l_{n}$)

2: $\text{s}\leftarrow\text{empty stack}$

3: $\text{a}\leftarrow\text{empty set of arcs}$

4: s.push(0) $\triangleright$ corresponding to dummy root

5: for $i\leftarrow 1$ to $n$ do

6: if $>\in l_{i}$ then

7: $\text{a.addArc( s.peek() }\rightarrow i)$

8: if $*\in l_{i}$ then

9: s.pop()

10: end if

11: end if

12: if $/\in l_{i}$ then

13: s.push(i)

14: end if

15: end for

16: return a

17:end function

Algorithm 1 To decode right arcs in the 4-bit encoding.

The idea of the algorithm is as follows: we read labels from left to right.
When we find a label containing /, we know that the corresponding node will be
a source of one or more right arcs. We push it into the stack. When we find a
label with >, we know that its node is the target of a right arc, so we link
it to the / on top of the stack. Additionally, if the label contains *, the
node is a rightmost sibling, so we pop the stack because no more arcs will be
created from the same head. Otherwise, we do not pop as we expect more arcs
from the same origin.333Note that, thus, the interpretation of the symbols /
and > is similar to that of the same symbols in the unbounded bracketing
encoding by (Strzyz et al., 2019), but here the / symbol is acting as a
“superbracket” that matches several opposing brackets (Yli-Jyrä, 2017, 2019)

Intuitively, this lets us generate all the possible non-crossing combinations
of right arcs: the stack enforces projectivity (to cover a / label with a
dependency we need to remove it from the stack, so crossing arcs from inside
the covering dependency to its right are not allowed), and the distinction
between > with and without * allows us to link a new node to any of the
previous, non-covered nodes.

To decode left arcs, we use a symmetric algorithm DecodeLeftArcs (not shown as
it is analogous), which traverses the labels from right to left, operating on
the elements \ and < rather than / and >; with the difference that the stack
is not initialized with the dummy root node (as the arc originating in it is a
right arc). By the same reasoning as above, this algorithm can obtain all the
possible non-crossing configurations of left arcs, and hence the mapping is
injective. The decoding is trivially linear-time with respect to sequence
length.

A sketch of an injectivity proof can be based on showing that the set of right
arcs generated by Algorithm 1 (and the analogous for left arcs) is the only
possible one that meets the conditions of the labels and does not have
crossing arcs (hence, we cannot have two projective trees with the same
encoding). To prove this, we can show that at each iteration, the arc added by
line 7 of Algorithm 1 is the only possible alternative that can lead to a
legal projective tree (i.e., that s.peek() is the only possible parent of node
$i$). This is true because (1) if we choose a parent to the left of s.peek(),
then we cover s.peek() with a dependency, while it has not yet found all of
its right dependents (as otherwise it would have been popped from the stack),
so a crossing arc will be generated later; (2) if we choose a parent to the
right of s.peek() and to the left of $i$, its label must contain / (otherwise,
by definition, it could not have right dependents) and not be on the stack (as
the stack is always ordered from left to right), so it must have been removed
from the stack due to finding all its right dependents, and adding one more
would violate the conditions of the encoding; and finally (3) a parent to the
right of $i$ cannot be chosen as the algorithm is only considering right arcs.
Together with the analogous proof for the symmetric algorithm, we show
injectivity.

#### Coverage

While we have defined and proved this encoding for projective trees,444 If we
did not consider a dummy root, we would be able to cover planar trees, rather
than just projective trees (as in the bracketing of (Strzyz et al., 2019)),
but this would require an extra label for the sentence’s syntactic root.
Instead, we use a dummy root on the left and explicitly encode the arc from it
to the syntactic root, which is thus labeled as a right child instead of using
an extra label. This simplifies the encoding, and the practical difference
between the coverage of projectivity and planarity is small (Gómez-Rodríguez
and Nivre, 2013). its coverage is actually larger: it can encode any
dependency forest (i.e., does not require connectedness) such that arcs in the
same direction do not cross (i.e., it can handle some non-projective
structures where arcs only cross in opposite directions, as the process of
encoding and decoding left and right arcs is independent). This is just like
in the unbounded bracketing encodings of (Strzyz et al., 2019), but this extra
coverage is not very large in practice, and we will define a better non-
projective extension later.

#### Non-surjectivity

Just like other sequence-labeling encodings (Strzyz et al., 2019; Lacroix,
2019; Strzyz et al., 2020, inter alia), ours is not surjective: not every
label sequence corresponds to a valid tree, so heuristics are needed to fix
cases where the sequence labeling component generates an invalid sequence.
This can happen regardless of whether we only consider a tree to be valid if
it is projective, or we accept the extra coverage mentioned above. For
example, a sequence where the last word is marked as a left child (<) is
invalid in either case. Trying to decode invalid label sequences will result
in trying to pop an empty stack or leaving material in the stack after
finishing Algorithm 1 or its symmetric. In practice, we can skip dependency
creation when the stack is empty, ignore material left in the stack after
decoding, break cycles and (if we require connectedness) attach any
unconnected nodes to a neighbor.

##  3 Non-Projective Encoding

[theme = simple] [row sep=.25em, column sep=1.5em] 0 & 1 & 2 & 3 & 4 & 5 & 6 &
7
-ROOT- & What & country & are & we & talking & about & ?
& <0* & \0<0*/1 & <0 & <0 & \0>0*/0 & >1* & >0*
& 0010000 & 0011001 & 0000000 & 0000000 & 1011100 & 1110000 & 1010000
[edge style=black]32det [edge style=black]63obl [edge style=black]64aux [edge
style=black]65nsubj [edge style=black]16root [edge style=red, dotted]37case
[edge style=black]68punct

Figure 2: A non-projective tree and its 7-bit encoding.

For a wider coverage of non-projective dependency trees (including the
overwhelming majority of trees found in treebanks), we use the same technique
as defined for unbounded brackets in (Strzyz et al., 2020): we partition
dependency trees into two subsets (planes) of arcs (details in Appendix D),
and this lets us define a _7-bit non-projective encoding_ by assigning each
word $w_{i}$ a label $l_{i}=(b_{0}\ldots b_{6})$, where:

  * •

$b_{0}b_{1}$ can take values <0 ($w_{i}$ is a left dependent in the first
plane), >0 (right dependent in the 1st plane), <1 or >1 (same for the 2nd
plane).

  * •

$b_{2}$ is true iff $w_{i}$ is the outermost right (or left) dependent of its
parent (regardless of plane). We represent it as * if true or blank if false.

  * •

$b_{3}$ (respectively, $b_{4}$) is true iff $w_{i}$ has one or more left
(right) dependents in the first plane. We denote it as \0 (/0) if true, blank
if false.

  * •

$b_{5}$ and $b_{6}$ are analogous to $b_{3}$ and $b_{4}$, but in the second
plane, represented as \1 or /1.

Every 7-bit combination is possible, leading to 128 distinct labels. Figure 2
shows an example of a non-projective tree represented with this encoding.

The encoding is able to cover every possible dependency tree whose arc set can
be partitioned into two subsets (planes), such that arcs with the same
direction and plane do not cross.

This immediately follows from defining the decoding with a set of four
algorithms, two for decoding left and right arcs on the first plane (defined
as Algorithm 1 and its symmetric, but considering only the symbols making
reference to arcs in the first plane) and other two identical decoding passes
for the second plane. With this, injectivity is shown in the same way as for
the 4-bit encoding. Decoding is still linear-time.

Note that the set of trees covered by the encoding, described above, is a
variant of the set of 2-Planar trees (Yli-Jyrä, 2003; Gómez-Rodríguez and
Nivre, 2010), which are trees that can be split into two planes such that arcs
within the same plane do not cross, regardless of direction. Compared to
2-Planar trees, and just like the encodings in (Strzyz et al., 2020), our set
is extended as it allows arcs with opposite directions to cross within the
same plane. However, it also loses some trees because the dummy root arc is
also counted when restricting crossings, whereas in 2-Planar trees it is
ignored.

##  4 Experiments

We compare our 4-bit and 7-bit encodings to their unbounded analogs, the
bracketing (Strzyz et al., 2019) and 2-planar bracketing encodings (Strzyz et
al., 2020) which overall are the best performing in previous work (Muñoz-Ortiz
et al., 2021). We use MaChAmp (van der Goot et al., 2021) as a sequence
labeling library, with default hyperparameters (Appendix B). We use XLM-
RoBERTa (Conneau et al., 2020) followed by two separate one-layered feed-
forward networks, one for syntactic labels and another for dependency types.
We evaluate on the Penn Treebank Stanford Dependencies 3.3.0 conversion and on
UD 2.9: a set of 9 linguistically-diverse treebanks taken from (Anderson and
Gómez-Rodríguez, 2020), and a low-resource set of 7 (Anderson et al., 2021).
We consider multiple subsets of treebanks as a single subset could be fragile
Alonso-Alonso et al. (2022).

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
| L | C | L | C | L | C | L | C
PTB | 114 | >99.99 | 124 | 100 | 16 | >99.99 | 28 | 100
RussianGSD | 104 | 99.76 | 166 | >99.99 | 16 | 99.61 | 70 | >99.99
FinnishTDT | 121 | 99.72 | 172 | >99.99 | 16 | 99.35 | 65 | >99.99
Anc-GreekPerseus | 259 | 95.81 | 527 | 99.24 | 16 | 88.93 | 128 | 99.24
ChineseGSD | 101 | 99.91 | 152 | >99.99 | 16 | 99.84 | 46 | >99.99
HebrewHTB | 97 | 99.98 | 125 | 100 | 16 | 99.98 | 36 | 100
TamilTTB | 51 | 99.94 | 58 | 100 | 16 | 99.98 | 22 | 100
UyghurUDT | 78 | 99.43 | 150 | >99.99 | 16 | 99.85 | 58 | >99.99
WolofWTB | 74 | 99.83 | 111 | >99.99 | 16 | 99.06 | 46 | >99.99
EnglishEWT | 110 | 99.88 | 174 | >99.99 | 16 | 99.75 | 63 | >99.99
Macro average | 110.9 | 99.43 | 165.9 | 99.92 | 16 | 98.62 | 56.2 | 99.92
Table 1: Number of labels (L) and coverage (C) for each treebank and encoding.
B and B-2P are the baselines.

Table 1 compares the compactness of the encodings by showing the number of
unique syntactic labels needed to encode the (unlabeled) trees in the training
set (i.e. the label set of the first task). The new encodings yield clearly
smaller label set sizes, as predicted in theory. In particular, the 4-bit
encoding always uses its 16 distinct labels. The 7-bit encoding only needs its
theoretical maximum of 128 labels for the Ancient Greek treebank (the most
non-projective one). On average, it uses around a third as many labels as the
2-planar bracketing encoding, and half as many as the basic bracketing.
Regarding coverage, the 7-bit encoding covers over 99.9% of arcs, like the
2-planar bracketing. The 4-bit encoding has lower coverage than basic
brackets: both cover all projective trees, but they differ on coverage of non-
projectivity (see Appendix C for an explanation of the reasons). More detailed
data (e.g. coverage and label set size for low-resource treebanks) is in
Appendix A.

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
PTB | 94.62 | 92.03 | 94.72 | 94.66
RussianGSD | 87.84 | 87.36 | 88.04 | 89.58
FinnishTDT | 92.45 | 92.37 | 92.19 | 92.74
Anc-GreekPerseus | 71.84 | 71.76 | 67.63 | 75.36
ChineseGSD | 85.23 | 84.38 | 85.36 | 85.70
HebrewHTB | 90.25 | 90.21 | 90.81 | 90.58
TamilTTB | 63.65 | 61.68 | 65.16 | 65.69
UyghurUDT | 67.22 | 65.49 | 67.17 | 69.10
WolofWTF | 75.04 | 74.59 | 76.24 | 75.57
EnglishEWT | 91.03 | 91.30 | 89.48 | 91.78
Macro average | 81.92 | 81.12 | 81.68 | 83.08
Table 2: LAS for the linguistically-diverse test sets

Table 2 shows the models’ performance in terms of LAS. The 4-bit encoding has
mixed performance, excelling in highly projective treebanks like the PTB or
Hebrew-HTB, but falling behind in non-projective ones like Ancient Greek,
which is consistent with the lower non-projective coverage. The 7-bit
encoding, however, does not exhibit this problem (given the almost total arc
coverage mentioned above) and it outperforms both baselines for every
treebank: the basic bracketing by 1.16 and the 2-planar one by 1.96 LAS points
on average.555In our setup, the basic bracketing encoding baseline beats the
2-planar baseline on average, contrary to the results in the papers that
introduced them (cf. (Strzyz et al., 2020)). This likely owes to the
architecture used: they used BiLSTMs, whereas we perform our experiments on a
more competitive architecture with XLM-RoBERTa.

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
BelarusianHSE | 85.21 | 86.83 | 86.77 | 88.23
GalicianTreeGal | 78.32 | 77.94 | 81.54 | 81.22
LithuanianHSE | 52.26 | 49.53 | 55.56 | 56.02
MarathiUFAL | 62.13 | 55.19 | 66.50 | 67.19
Old-East-SlavicRNC | 64.15 | 63.43 | 68.96 | 68.84
WelshCCG | 81.17 | 80.91 | 82.31 | 82.00
TamilTTB | 63.65 | 61.68 | 65.16 | 65.69
Macro average | 69.56 | 67.93 | 72.40 | 72.74
Table 3: LAS for the low-resource test sets

If we focus on low-resource corpora (Table 3), label set sparsity is
especially relevant so compactness further boosts accuracy. The new encodings
obtain large improvements, the 7-bit one surpassing the best baseline by over
3 average LAS points.

###  4.1 Additional results: splitting bits and external parsers

We perform additional experiments to test implementation variants of our
encodings, as well as to put our results into context with respect to non-
sequence-labeling parsers and simultaneous work. In the previous tables, both
for the 4-bit and 7-bit experiments, all bits were predicted as a single,
atomic task. We contrast this with a multi-task version where we split certain
groups of bits to be predicted separately. We only explore a preliminary
division of bits. For the 4-bit encoding, instead of predicting a label of the
form $b_{0}b_{1}b_{2}b_{3}$, the model predicts two labels of the form
$b_{0}b_{1}$ and $b_{2}b_{3}$, respectively. We call this method 4-bit-s. For
the 7-bit encoding, we decided to predict the bits corresponding to each plane
as a separate task, i.e., $b_{0}b_{2}b_{3}b_{4}$ and $b_{1}b_{5}b_{6}$. We
call this method 7-bit-s. We acknowledge that other divisions could be better.
However, this falls outside the scope of this paper.

We additionally compare our results with other relevant models. As mentioned
earlier, alongside this work, Amini et al. (2023) introduced a parsing-as-
tagging method called hexatagging. In what follows, we abbreviate this method
as 6tg. We implement 6tg under the same framework as our encodings for
homogeneous comparison, and we predict these hexatags through two separate
linear layers, one to predict the arc representation and another for the
dependency type. We also consider a split version, 6tg-s, where the two
components of the arc representation are predicted separately. For a better
understanding of their method, we refer the reader to Amini et al. and
Appendix E. Finally, we include a comparison against the biaffine graph-based
parser by Dozat et al. (2017). For this, we trained the implementation in
SuPar666https://github.com/yzhangcs/parser using xlm-roberta-large as the
encoder, which is often taken as a strong upper bound baseline.

Table 4 compares the performance of external parsers with our bit encodings.
First, the results show that the choice of whether to split labels into
components or not has a considerable influence, both for 6tg (where splitting
is harmful across the board) and for our encodings (where it is mostly
beneficial, perhaps because the structure of the encoding in bits with
independent meanings naturally lends itself to multi-task learning). Second,
on average, the best (multi-task) version of our 7-bit encoding is about 1.7
points behind the 6tg and 1.2 behind biaffine state-of-the-art parsers in
terms of LAS. However, the difference between versions with and without multi-
task learning suggests that there might be room for improvement by
investigating different splitting techniques. Additionally, in Appendix F,
Table 14 compares the processing speeds of these parsers (on a single CPU). In
Appendix G, Tables 15 and 16 show how often heuristics are applied in
decoding.

Treebank | 4-bit | 7-bit | 6tg | 6tg-s | 4-bit-s | 7-bit-s | biaffine
---|---|---|---|---|---|---|---
PTB | 94.72 | 94.66 | 96.13 | 96.04 | 94.92 | 94.88 | 95.32
RussianGSD | 88.04 | 89.58 | 91.83 | 90.95 | 88.78 | 90.18 | 90.17
FinnishTDT | 92.19 | 92.74 | 94.12 | 92.66 | 92.11 | 93.10 | 93.33
Anc-GreekPerseus | 67.63 | 75.36 | 73.12 | 72.78 | 68.02 | 76.12 | 79.81
ChineseGSD | 85.36 | 85.70 | 87.39 | 87.32 | 85.99 | 86.13 | 88.67
HebrewHTB | 90.81 | 90.58 | 92.82 | 91.27 | 90.81 | 91.05 | 91.88
TamilTTB | 65.16 | 65.69 | 78.33 | 76.32 | 66.99 | 67.19 | 67.52
UyghurUDT | 67.17 | 69.10 | 71.11 | 65.23 | 67.55 | 69.13 | 72.33
WolofWTF | 76.24 | 75.57 | 76.04 | 72.11 | 76.85 | 76.24 | 76.73
EnglishEWT | 89.48 | 91.78 | 92.62 | 90.06 | 89.48 | 92.15 | 92.72
Macro avg | 81.68 | 83.08 | 85.35 | 83.47 | 82.15 | 83.62 | 84.85
Table 4: LAS comparison against related parsers, for the linguistically-
diverse test sets.

Finally, Table 5 shows the external comparison on the low-resource treebanks,
where our encodings lag further behind biaffine and especially 6tg, which
surpasses 7-bit-s by over 5 points.

Treebank | 4bit | 7bit | 6tg | 6tg-s | 4bit-s | 7bit-s | biaffine
---|---|---|---|---|---|---|---
BelarusianHSE | 86.77 | 88.23 | 89.14 | 89.01 | 87.01 | 88.52 | 93.83
GalicianTreeGal | 81.54 | 81.22 | 82.03 | 81.94 | 81.97 | 81.31 | 86.81
LithuanianHSE | 55.56 | 56.02 | 64.47 | 64.74 | 55.97 | 57.31 | 56.75
MarathiUFAL | 66.50 | 67.19 | 75.00 | 74.66 | 66.92 | 67.57 | 61.22
Old-East-SlavicRNC | 68.96 | 68.84 | 71.35 | 71.37 | 69.02 | 68.86 | 72.06
WelshCCG | 82.31 | 82.00 | 87.05 | 86.92 | 82.62 | 82.13 | 85.05
TamilTTB | 65.16 | 65.69 | 78.33 | 77.91 | 65.27 | 65.82 | 76.12
Macro average | 72.40 | 72.74 | 78.19 | 78.07 | 72.68 | 73.07 | 75.97
Table 5: LAS comparison against related parsers, for the low-resource test
sets.

##  5 Conclusion

We have presented two new bracketing encodings for dependency parsing as
sequence labeling, which use a bounded number of labels. The 4-bit encoding,
designed for projective trees, excels in projective treebanks and low-resource
setups. The 7-bit encoding, designed to accommodate non-projectivity, clearly
outperforms the best prior sequence-labeling encodings across a diverse set of
treebanks. The source code is available at
https://github.com/Polifack/CoDeLin/releases/tag/1.25.

## Limitations

In our experiments, we do not perform any hyperparameter optimization or other
task-specific tweaks to try to bring the raw accuracy figures as close as
possible to state of the art. This is for several reasons: (1) limited
resources, (2) the paper having a mainly theoretical focus, with the
experiments serving to demonstrate that our encodings are useful when compared
to alternatives (the baselines) rather than chasing state-of-the-art accuracy,
and (3) because we believe that one of the primary advantages of parsing as
sequence labeling is its ease of use for practitioners, as one can perform
parsing with any off-the-shelf sequence labeling library, and our results
directly reflect this kind of usage. We note that, even under such a setup,
raw accuracies are remarkably good.

## Ethics Statement

This is a primarily theoretical paper that presents new encodings for the
well-known task of dependency parsing. We conduct experiments with the sole
purpose of evaluating the new encodings, and we use publicly-available
standard datasets that have long been in wide use among the NLP community.
Hence, we do not think this paper raises any ethical concern.

## Acknowledgments

This work has received funding by the European Research Council (ERC), under
the Horizon Europe research and innovation programme (SALSA, grant agreement
No 101100615), ERDF/MICINN-AEI (SCANNER-UDC, PID2020-113230RB-C21), Xunta de
Galicia (ED431C 2020/11), Grant GAP (PID2022-139308OA-I00) funded by
MCIN/AEI/10.13039/501100011033/ and by ERDF “A way of making Europe”, and
Centro de Investigación de Galicia “CITIC”, funded by the Xunta de Galicia
through the collaboration agreement between the Consellería de Cultura,
Educación, Formación Profesional e Universidades and the Galician universities
for the reinforcement of the research centres of the Galician University
System (CIGUS).

## References

  * Alonso-Alonso et al. (2022) Iago Alonso-Alonso, David Vilares, and Carlos Gómez-Rodríguez. 2022.  The fragility of multi-treebank parsing evaluation.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 5345–5359, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Amini and Cotterell (2022) Afra Amini and Ryan Cotterell. 2022.  On parsing as tagging.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 8884–8900, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Amini et al. (2023) Afra Amini, Tianyu Liu, and Ryan Cotterell. 2023.  Hexatagging: Projective dependency parsing as tagging.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 1453–1464, Toronto, Canada. Association for Computational Linguistics.
  * Anderson et al. (2021) Mark Anderson, Mathieu Dehouck, and Carlos Gómez-Rodríguez. 2021.  A falta de pan, buenas son tortas: The efficacy of predicted UPOS tags for low resource UD parsing.  In _Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021)_ , pages 78–83, Online. Association for Computational Linguistics.
  * Anderson and Gómez-Rodríguez (2020) Mark Anderson and Carlos Gómez-Rodríguez. 2020.  Distilling neural networks for greener and faster dependency parsing.  In _Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies_ , pages 2–13, Online. Association for Computational Linguistics.
  * Anderson and Gómez-Rodríguez (2021) Mark Anderson and Carlos Gómez-Rodríguez. 2021.  A modest Pareto optimisation analysis of dependency parsers in 2021.  In _Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021)_ , pages 119–130, Online. Association for Computational Linguistics.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Dozat et al. (2017) Timothy Dozat, Peng Qi, and Christopher D. Manning. 2017.  Stanford’s graph-based neural dependency parser at the CoNLL 2017 shared task.  In _Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 20–30, Vancouver, Canada. Association for Computational Linguistics.
  * Gómez-Rodríguez and Nivre (2010) Carlos Gómez-Rodríguez and Joakim Nivre. 2010.  A transition-based parser for 2-planar dependency structures.  In _Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics_ , pages 1492–1501, Uppsala, Sweden. Association for Computational Linguistics.
  * Gómez-Rodríguez and Nivre (2013) Carlos Gómez-Rodríguez and Joakim Nivre. 2013.  Divisible transition systems and multiplanar dependency parsing.  _Computational Linguistics_ , 39(4):799–845.
  * Gómez-Rodríguez et al. (2020) Carlos Gómez-Rodríguez, Michalina Strzyz, and David Vilares. 2020.  A unifying theory of transition-based and sequence labeling parsing.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 3776–3793, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Gómez-Rodríguez and Vilares (2018) Carlos Gómez-Rodríguez and David Vilares. 2018.  Constituent parsing as sequence labeling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1314–1324, Brussels, Belgium. Association for Computational Linguistics.
  * Kitaev and Klein (2020) Nikita Kitaev and Dan Klein. 2020.  Tetra-tagging: Word-synchronous parsing with linear-time inference.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6255–6261, Online. Association for Computational Linguistics.
  * Lacroix (2019) Ophélie Lacroix. 2019.  Dependency parsing as sequence labeling with head-based encoding and multi-task learning.  In _Proceedings of the Fifth International Conference on Dependency Linguistics (Depling, SyntaxFest 2019)_ , pages 136–143, Paris, France. Association for Computational Linguistics.
  * Muñoz-Ortiz et al. (2021) Alberto Muñoz-Ortiz, Michalina Strzyz, and David Vilares. 2021.  Not all linearizations are equally data-hungry in sequence labeling parsing.  In _Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2021)_ , pages 978–988, Held Online. INCOMA Ltd.
  * Strzyz et al. (2019) Michalina Strzyz, David Vilares, and Carlos Gómez-Rodríguez. 2019.  Viable dependency parsing as sequence labeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 717–723, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Strzyz et al. (2020) Michalina Strzyz, David Vilares, and Carlos Gómez-Rodríguez. 2020.  Bracketing encodings for 2-planar dependency parsing.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2472–2484, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * van der Goot et al. (2021) Rob van der Goot, Ahmet Üstün, Alan Ramponi, Ibrahim Sharaf, and Barbara Plank. 2021.  Massive choice, ample tasks (MaChAmp): A toolkit for multi-task learning in NLP.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations_ , pages 176–197, Online. Association for Computational Linguistics.
  * Wang et al. (2019) Yufei Wang, Mark Johnson, Stephen Wan, Yifang Sun, and Wei Wang. 2019.  How to best use syntax in semantic role labelling.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5338–5343, Florence, Italy. Association for Computational Linguistics.
  * Yli-Jyrä (2017) Anssi Yli-Jyrä. 2017.  Bounded-depth high-coverage search space for noncrossing parses.  In _Proceedings of the 13th International Conference on Finite State Methods and Natural Language Processing (FSMNLP 2017)_ , pages 30–40, Umeå, Sweden. Association for Computational Linguistics.
  * Yli-Jyrä (2003) Anssi Mikael Yli-Jyrä. 2003.  Multiplanarity – a model for dependency structures in treebanks.  In _TLT 2003. Proceedings of the Second Workshop on Treebanks and Linguistic Theories_ , volume 9 of _Mathematical Modelling in Physics, Engineering and Cognitive Sciences_ , pages 189–200, Växjö, Sweden. Växjö University Press.
  * Yli-Jyrä (2019) Anssi Mikael Yli-Jyrä. 2019.  How to embed noncrossing trees in universal dependencies treebanks in a low-complexity regular language.  _Journal of Language Modelling_ , 7(2):177–232.

##  Appendix A Further Data

Tables 6 and 7 show treebank statistics for the general and low-resource set
of treebanks, respectively.

Treebank | projective | 1-planar | r arcs | avg d
---|---|---|---|---
PTB | 99.89% | 99.89% | 48.74% | 2.295
RussianGSD | 93.87% | 93.89% | 49.03% | 2.263
FinnishTDT | 93.85% | 93.88% | 52.88% | 2.365
Anc-GreekPerseus | 37.66% | 37.67% | 52.81% | 2.447
ChineseGSD | 97.75% | 97.87% | 63.67% | 2.440
HebrewHTB | 96.26% | 96.28% | 49.21% | 2.242
TamilTTB | 98.33% | 98.33% | 68.56% | 2.262
UyghurUDT | 95.02% | 96.03% | 64.31% | 2.140
WolofWTF | 97.01% | 97.10% | 48.21% | 2.519
EnglishEWT | 97.47% | 97.63% | 57.18% | 2.525
Table 6: Statistics for the linguistically-diverse set of treebanks: percentage of projective trees, 1-planar trees, percentage of rightward arcs (r arcs), and average dependency distance (avg d). Treebank | projective | 1-planar | r arcs | avg d
---|---|---|---|---
BelarusianHSE | 94.92% | 95.22% | 46.92% | 2.232
GalicianTreeGal | 88.80% | 89.20% | 53.02% | 2.530
LithuanianHSE | 85.93% | 86.69% | 58.40% | 2.321
Old-East-SlavicRNC | 66.26% | 66.35% | 58.21% | 2.433
MarathiUFAL | 95.92% | 96.35% | 50.81% | 2.362
WelshCCG | 98.24% | 98.24% | 43.94% | 2.324
TamilTTB | 98.33% | 98.33% | 68.56% | 2.262
Table 7: Statistics for the low-resource set of treebanks: percentage of
projective trees, 1-planar trees, percentage of rightward arcs (r arcs), and
average dependency distance (avg d).

Table 8 shows the number of labels and the arc coverage of each considered
encoding for the low-resource treebank set of Anderson et al. (2021), in the
same notation as in Table 1. As can be seen in the table, the trends are
analogous to those for the other treebanks (Table 1 in the main text).

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
| L | C | L | C | L | C | L | C
BelarusianHSE | 133 | 99.53 | 228 | >99.99 | 16 | 99.46 | 89 | >99.99
GalicianTreeGal | 79 | 99.51 | 129 | >99.99 | 16 | 99.52 | 60 | >99.99
LithuanianHSE | 64 | 98.88 | 84 | 99.98 | 16 | 98.82 | 45 | 99.98
MarathiUFAL | 46 | 99.44 | 58 | 100 | 16 | 99.32 | 36 | 100
Old-East-SlavicRNC | 134 | 97.66 | 230 | 99.94 | 16 | 97.46 | 86 | 99.94
WelshCCG | 53 | 99.90 | 71 | 100 | 16 | 99.93 | 38 | 100
TamilTTB | 51 | 99.82 | 58 | 100 | 16 | 99.84 | 22 | 100
Macro average | 80.0 | 99.25 | 122.6 | 99.99 | 16 | 99.19 | 53.7 | 99.99
Table 8: Number of labels (L) and arc coverage (C) for each low-resource
treebank and encoding. B and B-2P are the baselines.

Tables 9 and 10 show the coverage of the encodings in terms of full trees,
rather than arcs (i.e., what percentage of the dependency trees in each
treebank can be fully encoded and decoded back by each of the encodings).

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
PTB | >99.99% | 100% | >99.99% | 100%
RussianGSD | 96.94% | 99.92% | 95.65% | 99.92%
FinnishTDT | 99.43% | 100% | 99.35% | 100%
Anc-GreekPerseus | 72.25% | 90.63% | 50.48% | 90.63%
ChineseGSD | 99.30% | 100% | 98.54% | 100%
HebrewHTB | 98.26% | 99.89% | 97.20% | 99.89%
TamilTTB | 99.50% | 100% | 98.67% | 100%
UyghurUDT | 97.80% | 100% | 97.19% | 100%
WolofWTF | 97.86% | 99.95% | 97.25% | 99.95%
EnglishEWT | 98.73% | 99.98% | 98.18% | 99.98%
Macro average | 96.01% | 99.04% | 93.25% | 99.04%
Table 9: Full tree coverage for each encoding on the linguistically-diverse set of treebanks. Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
BelarusianHSE | 96.36% | 99.95% | 96.22% | 99.95%
GalicianTreeGal | 92.90% | 99.80% | 92.60% | 99.80%
LithuanianHSE | 88.97% | 99.62% | 88.97% | 99.62%
Old-East-SlavicRNC | 72.15% | 97.75% | 72.05% | 97.75%
MarathiUFAL | 97.63% | 100% | 97.42% | 100%
WelshCCG | 98.88% | 100% | 98.88% | 100%
TamilTTB | 99.50% | 100% | 98.67% | 100%
Macro average | 92.34% | 99.59% | 92.12% | 99.59%
Table 10: Full tree coverage for each encoding on the low-resource set of
treebanks.

Tables 11 and 12 show the total number of labels needed to encode the training
set for each encoding and treebank, when considering full labels (i.e., the
number of combinations of syntactic labels and dependency type labels). This
can be relevant for implementations that generate such combinations as atomic
labels (in our implementation, label components are generated separately
instead).

Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
PTB | 1216 | 1233 | 396 | 408
RussianGSD | 802 | 961 | 400 | 614
FinnishTDT | 1054 | 1223 | 435 | 685
Anc-GreekPerseus | 1469 | 2401 | 304 | 1167
ChineseGSD | 804 | 912 | 321 | 406
HebrewHTB | 754 | 798 | 317 | 357
TamilTTB | 262 | 274 | 153 | 164
UyghurUDT | 553 | 683 | 353 | 475
WolofWTF | 585 | 643 | 318 | 382
EnglishEWT | 1089 | 1281 | 487 | 709
Macro average | 858.8 | 1040.9 | 348.4 | 536.7
Table 11: Unique labels generated when encoding the training sets of the linguistically-diverse set of treebanks, including dependency types as a component of the labels.  Treebank | B | B-2P | 4bit | 7bit
---|---|---|---|---
BelarusianHSE | 1136 | 1479 | 477 | 926
GalicianTreeGal | 512 | 601 | 270 | 376
LithuanianHSE | 398 | 432 | 256 | 306
Old-East-SlavicRNC | 910 | 1181 | 378 | 715
MarathiUFAL | 275 | 291 | 197 | 223
WelshCCG | 474 | 514 | 265 | 312
TamilTTB | 262 | 274 | 153 | 164
Macro average | 566.7 | 681.7 | 285.1 | 431.7
Table 12: Unique labels generated when encoding the training sets of the low-
resource set of treebanks, including dependency types as a component of the
labels.

##  Appendix B Hyperparameters

We did not perform hyperparameter search, but just used MaChAmp’s defaults,
which can be seen in Table 13.

Parameter | Value
---|---
dropout | 0.1
max input length | 128
batch size | 8
training epochs | 50
optimizer | adam
learning rate | 0.0001
weight decay | 0.01
Table 13: Hyperparameter settings

##  Appendix C Coverage Differences

It is worth noting that, while the 7-bit encoding has exactly the same
coverage as the 2-planar bracketing encoding (see Tables 1, 8, 9, 10); the
4-bit encoding has less coverage than the basic bracketing. As mentioned in
the main text, both have full coverage of projective trees, but there are
subtle differences in how they behave when they are applied to non-projective
trees. We did not enumerate all of these differences in detail for space
reasons. In particular, they are the following:

  * •

Contrary to basic bracketing, the 4-bit encoding needs to encode the arc
originating from the dummy root explicitly. This means that it cannot encode
non-projective, but planar trees where the dummy root arc crosses a right arc
(or equivalently, the syntactic root is covered by a right arc).

  * •

In the basic bracketing, a dependency involving words $w_{i}$ and $w_{j}$
($i<j$) is not encoded in the labels of $w_{i}$ and $w_{j}$, but in the labels
of $w_{i+1}$ and $w_{j}$ (see (Strzyz et al., 2019)), as a technique to
alleviate sparsity (in the particular case of that encoding, it guarantees
that the worst-case number of labels is linear, rather than quadratic, with
respect to sentence length). In the 2-planar, 4- and 7-bit encodings, this is
unneeded so dependencies are encoded directly in the labels of the intervening
words.

  * •

Contrary to basic bracketing, in the 4-bit encoding a single / or \ element is
shared by several arcs. Thus, if an arc cannot be successfully encoded due to
unsupported non-projectivity, the problem can propagate to sibling
dependencies. In other words, due to being more compact, the 4-bit encoding
has less redundancy than basic bracketing.

##  Appendix D Plane Assignment

The 2-planar and 7-bit encodings need a strategy to partition trees into two
planes. We used the second-plane-averse strategy based on restriction
propagation on the crossings graph (Strzyz et al., 2020). It can be summarized
as follows:

  1. 1.

The crossings graph is defined as an undirected graph where each node
corresponds to an arc in the dependency tree, and there is an edge between
nodes $a$ and $b$ if arc $a$ crosses arc $b$ in the dependency tree.

  2. 2.

Initially, both planes are marked as allowed for every arc in the dependency
tree.

  3. 3.

The arcs are visited in the order of their right endpoint, moving from left to
right. Priority is given to shorter arcs if they have a common right endpoint.
Once sorted, we iterate through the arcs.

  4. 4.

Whenever we assign an arc $a$ to a given plane $p$, we immediately propagate
restrictions in the following way: we forbid plane $p$ for the arcs that cross
$a$ (its neighbors in the crossings graph), we forbid the other plane
($p^{\prime}$) for the neighbors of its neighbors, plane $p$ for the neighbors
of those, and so on.

  5. 5.

Plane assignment is made by traversing arcs. For each new arc $a$, we look at
the restrictions and assign it to the first plane if allowed, otherwise to the
second plane if allowed, and finally to no plane if none is allowed (for
non-2-planar structures).

##  Appendix E Hexatagging

Amini et al. (2023) use an intermediate representation, called binary head
trees, that acts as a proxy between dependency trees and hexatags. These trees
have a structure akin to binary constituent trees in order to apply the tetra-
tagging encoding Kitaev and Klein (2020). In addition, non-terminal
intermediate nodes are labeled with ‘L’ or ‘R’ based on whether the head of
the constituent is on its left or right subtree. We direct the reader to the
paper for specifics. However, a mapping between projective dependency trees
and this structure can be achieved by starting at the sentence’s root and
conducting a depth-first traversal of the tree. The arc representation
components for each hexatag encode: (i) the original label corresponding to
the tetratag, and (ii) the value of the non-terminal symbol in the binary head
tree.

##  Appendix F Speed comparison

Table 14 compares the speed of the models over an execution on a single
CPU.777Intel(R) Core(TM) i9-10920X CPU @ 3.50GHz. It is important to note that
while SuPar is an optimized parser, in this context, we used MaChAmp as a
general sequence labeling framework without specific optimization for speed.
With a more optimized model, practical processing speeds in the range of 100
sentences per second on CPU or 1000 on a consumer-grade GPU should be
achievable (cf. the figures for sequence-labeling parsing implementations in
(Anderson and Gómez-Rodríguez, 2021)).

Treebank | biaffine | 6tg | 4bit | 7bit
---|---|---|---|---
Penn-Treebank | 28.34 | 14.65 | 14.28 | 14.42
UD-Russian-GSD | 28.15 | 14.27 | 14.63 | 14.30
UD-Finnish-TDT | 34.68 | 18.22 | 17.56 | 17.82
UD-Ancient-Greek-Perseus | 24.12 | 12.53 | 12.93 | 12.15
UD-Chinese-GSD | 22.64 | 10.78 | 11.05 | 10.86
UD-Hebrew-HTB | 27.06 | 13.46 | 13.15 | 13.71
UD-Tamil-TTB | 29.19 | 11.98 | 12.17 | 12.87
UD-Uyghur-UDT | 34.87 | 18.69 | 18.01 | 18.93
UD-Wolof-WTF | 28.14 | 12.61 | 12.31 | 12.61
UD-English-EWT | 35.02 | 20.03 | 19.87 | 20.17
Table 14: Speed (sentences per second) for the linguistically-diverse test
sets.

##  Appendix G Non-Surjectivity in Decoding

As mentioned in the main text, all encodings explored in this paper are non-
surjective, meaning that there are label sequences that do not correspond to a
valid tree. In these cases, the labels are decoded using simple heuristics
(e.g. skipping dependency creation if the stack is empty, ignoring material
remaining in the stack after decoding, attaching unconnected nodes and
breaking cycles). Table 15 shows data about the number of trees in the test
set such that the labels output by the tagger do not directly correspond to a
valid tree, and at least one of these heuristics has to be applied. Table 16
shows the same information in terms of the percentage of dependency arcs that
are affected by said heuristics.

Treebank | 6tg | 4-bit | 7-bit
---|---|---|---
PTB |  04.01% |  08.24% |  04.13%
RussianGSD | 14.42% | 19.34% | 16.57%
FinnishTDT |  03.75% | 10.01% |  08.84%
Anc-GreekPerseus | 12.66% | 20.08% | 18.81%
ChineseGSD | 12.31% | 22.06% | 21.81%
HebrewHTB | 10.82% | 16.76% | 16.79%
TamilTTB | 29.06% | 36.12% | 37.67%
UyghurUDT | 18.13% | 22.19% | 18.52%
WolofWTF | 30.01% | 42.15% | 50.54%
EnglishEWT |  04.01% | 12.24% |  06.48%
Macro average | 13.92% | 20.92% | 20.02%
Table 15: Percentage of trees in the linguistically-diverse test sets where the label sequence output by the tagger does not correspond to a valid tree, and heuristics need to be applied to deal with unconnected nodes, cycles or out-of-bounds indexes. Treebank | 6tg | 4-bit | 7-bit
---|---|---|---
PTB | 0.531% | 0.941% | 0.566%
RussianGSD | 0.930% | 1.479% | 1.200%
FinnishTDT | 0.291% | 0.987% | 0.780%
Anc-GreekPerseus | 0.563% | 2.291% | 1.917%
ChineseGSD | 0.705% | 1.622% | 1.593%
HebrewHTB | 0.550% | 0.965% | 0.958%
TamilTTB | 2.728% | 3.819% | 4.280%
UyghurUDT | 2.052% | 2.801% | 2.191%
WolofWTF | 1.853% | 3.043% | 3.868%
EnglishEWT | 0.554% | 1.523% | 0.726%
Macro average | 1.075% | 1.947% | 1.807%
Table 16: Percentage of dependency arcs in the linguistically-diverse test
sets where heuristics need to be applied to deal with unconnected nodes,
cycles or out-of-bounds indexes.