# On Mignotte secret sharing schemes over Gaussian Integers

Diego Munuera-Merayo

###### Abstract.

Secret Sharing Schemes (SSS) are methods for distributing a secret among a set
of participants. One of the first Secret Sharing Schemes was proposed by M.
Mignotte, based on the Chinese remainder theorem over the ring of integers. In
this article we extend the Mignotte’s scheme to the ring of Gaussian Integers
and study some of its properties. While doing this we aim to solve a gap in a
previous construction of such extension. In addition we show that any access
structure can be made through a SSS over $\mathbb{Z}[i]$.

Keywords. Secret sharing, Mignotte sharing scheme, Gaussian integer, Chinese
remainder theorem.
2021 MSC. 94A62, 13F07.

##  1\. Introduction

Secret sharing schemes (SSS’s) are methods for distributing a secret among a
set of participants. Among their applications we may highlight key management,
threshold and visual cryptography, e-voting, multiparty computation and more.
Given the increasing importance of information security in today’s society, it
is not surprising that SSS’s have become an active field of research within
public key cryptography.

In a SSS, a secret $s$ is broken into $n$ pieces or shares. Each share is
given to one out of $n$ participants. This shares are designed ensuring that
some authorized coalitions of participants can reconstruct the secret by
pooling the shares of its members, while non-authorized coalitions cannot do
it. This family of authorized coalitions is called access structure of the
scheme.

The problem of secret sharing was firstly introduced by A. Shamir in [11]. In
that article he also suggested a method to perform it: the so-called Shamir
threshold secret sharing schemes, based on Lagrangian interpolation. Since the
publication of Shamir’s work, several other methods have been proposed. For
our purposes within this article, we may highlight the ones by M. Mignotte [9]
and C. Asmuth and J. Bloom [1], both based on the Chinese remainder theorem
for coprime modules over the ring of integers $\mathbb{Z}$. This three methods
belong to the category of threshold $(t,n)$ schemes. This means that their
access structures are formed by all the coalitions with at least $t$ out of
$n$ participants, for a certain $t$.

On the other hand, the Chinese remainder theorem has many known applications
in cryptography, [3]. It is based on a well known property of integers, the
so-called Euclidean division: for any two integers $n,m$ with $m\neq 0$, there
exists integers $q$ (quotient) and $r$ (remainder) such that $m=nq+r$ with
$0\leq r<|m|$.

Of course, Euclidean division is not exclusive to $\mathbb{Z}$. As there exist
other rings that admit it, the called Euclidean Domains. Among these we may
highlight the ring of univariate polynomials over a field $\mathbb{K}[X]$, and
the ring of Gaussian Integers $\mathbb{Z}[i]$. As a consequence a Chinese
remainder theorem holds over both $\mathbb{K}[X]$ and $\mathbb{Z}[i]$, and
therefore we can extend the Mignotte secret sharing scheme to these rings.

In the literature we can find successive generalizations of Mignotte’s scheme.
Firstly by S. Iftene to not necessarily coprime integers [7]. Later T. Galibus
and G. Matveev [5] provided a version over polynomial rings of one variable.
In that paper the authors also showed the remarkable property that any access
structure can be realized by a Mignotte polynomial SSS. Finally, in [10] an
extension of Mignotte threshold scheme to the ring of Gaussian Integers is
proposed, and subsequently applied to the problem of image sharing.Recall that
Gaussian Integers play a role in digital signal processing, cryptography,
coding, and many other fields of science and technology, see [2]. And that
Mignotte’s threshold scheme has already been proposed for image sharing, [13].

However, the extension of Mignotte SSS to Gaussian Integers proposed in [10]
contains a crucial gap. Contrary to what occurs over $\mathbb{Z}$ and
$\mathbb{K}[X]$, in the Euclidean division over $\mathbb{Z}[i]$, quotient and
remainder are not unique. Thus, given $v,z\in\mathbb{Z}[i]$, the expression
$v\,(\mbox{mod }z)$ does not uniquely identify one element of $\mathbb{Z}[i]$.
This causes that the solution of a system of simultaneous congruence equations
is not unique over $\mathbb{Z}[i]$ and, finally, that Mignotte’s scheme based
on it may provide wrong recovered secrets.

In this article we propose a new version of Mignotte’s SSS over
$\mathbb{Z}[i]$ that works properly and investigate some of its properties.
The paper is organized as follows: in Section 2 we recall some basic facts on
SSS’s and the arithmetic of $\mathbb{Z}[i]$. The proposed scheme is developed
in Section 3, where we also study its main properties. In particular,
following [5] we show that any access structure can be realized by our scheme.
Also we characterize those access structures which are obtained from coprime
modules. Some examples are included in order to illustrate the obtained
results.

##  2\. Some background on SSS’s and Gaussian Integers

First, we recall some known facts about secret sharing schemes and Gaussian
Integers. A complete study of most of this subjects can be found in [12] for
secret sharing and [4] for Gaussian Integers.

###  2.1. Secret sharing schemes

Let ${\mathcal{P}}=\\{1,\dots,n\\}$ be a set of $n$ participants and
${\mathcal{S}}$ be a finite and non-empty set of secrets. We want to share a
secret $s\in{\mathcal{S}}$ among the participants in $\mathcal{P}$. For that
purpose, each participant will receive a data $s_{i}$ about the secret, which
we will call its share. A dealer computes the $s_{1},\dots,s_{n}$ from $s$ and
assigns $s_{i}$ to each participant $i$. A secret sharing scheme is a method
${\mathcal{R}}$ of calculating the shares $s_{i}$ so that certain groups of
participants, previously determined, can recover $s$ by pooling the shares of
their members; while making it impossible for any other coalition of
participants to recover the secret.

We will call access structure of the scheme (denoted by $\mathcal{A}$) to the
family of all coalitions authorized to recover the secret. Note that this
family is monotone increasing.

We say that a scheme is perfect if unauthorized coalitions cannot deduce any
information about the secret. Another important feature to take into account
in a scheme ${\mathcal{R}}$ is the size of the shares distributed to the
participants. Let us denote by ${\mathcal{S}}_{i}$ the set of all possible
values that $s_{i}$ can take when $s$ runs over ${\mathcal{S}}$. It can be
proved that when no unauthorized coalition can discard any element of
$\mathcal{S}$ to be the shared secret, it holds that
$|{\mathcal{S}}_{i}|\geq|{\mathcal{S}}|$. We define the information rate of
$\mathcal{R}$ as

$\rho(\mathcal{R})=\min\left\\{\frac{\log|{\mathcal{S}}_{i}|}{\log|{\mathcal{S}}|}\
:\ i=1,\dots,n\right\\}.$

If $\rho(\mathcal{R})=1$ then the scheme $\mathcal{R}$ is called ideal.

###  2.2. The Chinese remainder theorem

In its classical version, over the ring of integers, the Chinese remainder
theorem states the following.

######  Theorem 1.

Let $a_{1},\dots,a_{n}\in\mathbb{Z}$, and let $m_{1},\dots,m_{n}$ be
relatively pairwise coprime integers such that $m_{1},\dots,m_{n}\geq 2$. The
system of simultaneous congruence equations

$x\equiv a_{i}\;(\mbox{\rm mod }m_{i}),\hskip 11.38109pti=1,\dots,n$

has a unique solution modulo $\mbox{\rm lcm}(m_{1},\dots,m_{n})$. Furthermore,
this solution can be explicitly given as
$x=a_{1}q_{1}r_{1}+\cdots+a_{n}q_{n}r_{n}$. Where $q_{i}=m_{1}\cdots
m_{n}/m_{i}$ and $r_{i}=q_{i}^{-1}$ in $\mathbb{Z}/m_{i}\mathbb{Z}$, for
$i=1,\dots,n$.

This theorem can be generalized, as the integers need not to be relatively
pairwise coprime. In this case there exists a solution if and only if
$a_{i}\equiv a_{j}(\mbox{\rm mod }\mbox{ lcm}(m_{i},m_{j}))$ for all $1\leq
i,j\leq n$. Furthermore, it can be stated over Euclidean rings, such as
Gaussian Integers.

###  2.3. Mignotte SSS over $\mathbb{Z}$

The Mignotte’s original secret sharing scheme allows the construction of
threshold $(t,n)$ schemes over a set $\mathcal{P}=\\{1,\dots,n\\}$ of $n$
participants as follows [9]: Let $\mathbf{m}:m_{1}<m_{2}<\cdots<m_{n}$, be a
sequence of $n$ pairwise relatively coprime integers such that
$m_{n-t+2}\cdots m_{n}<m_{1}\cdots m_{t}$. The integer $m_{i}$ is assigned to
participant $i$. Let us write $m^{-}=m_{n-t+2}\cdots m_{n}$,
$m^{+}=m_{1}\cdots m_{t}$ and for a coalition $C\subseteq\mathcal{P}$, let
$m(C)=\prod_{i\in C}m_{i}$. The above condition on the $m_{i}$’s implies that
$m(C)\leq m^{-}$ when $|C|<t$ and $m(C)\geq m^{+}$ when $|C|\geq t$.

The scheme operates as follows: Let $\mathcal{S}=\\{s\in\mathbb{Z}\ :\
m^{-}<s<m^{+}\\}$ be the set of secrets to be shared. Given a secret $s$, the
share of participant $i$ is $s_{i}=s\ (\mbox{\rm mod }m_{i})$. An authorized
coalition $A$ with $|A|\geq t$ may recover the secret by solving the system

$(S_{A})\hskip 34.1433ptx\equiv s_{i}\;(\mbox{\rm mod }m_{i}),\hskip
11.38109pti\in A$

whose solution $x$ is unique modulo $m(A)$ as guaranteed by the Chinese
remainder theorem. Since $s<m^{+}\leq m(A)$, it holds that $x=s$. An
unauthorized coalition $B$ with $|B|<t$, may try to recover the secret by
solving the system

$(S_{B})\hskip 34.1433ptx\equiv s_{i}\;(\mbox{\rm mod }m_{i}),\hskip
11.38109pti\in B$

whose solution $x$ is unique modulo $m(B)$. But since $x<m(B)\leq m^{-}\leq
s$, it holds that $x\neq s$ and so $B$ does not recover the legitimate secret.

###  2.4. Extensions of Mignotte SSS

In [7] Iftene suggested an extension of Mignotte SSS over the integers as
follows. Let $\mathbf{m}:m_{1},m_{2},\cdots,m_{n}$, be a sequence of $n$ (not
necessarily coprime) integers. For a coalition $C\subseteq\mathcal{P}$ let us
denote by $\mbox{\rm lcm}(C)$ the least common multiple of $\\{m_{i}:i\in
C\\}$. Take two integers $m^{-}<m^{+}$ such that the interval $(m^{-},m^{+})$
does not contain the $\mbox{\rm lcm}(C)$ of any coalition
$C\subseteq\mathcal{P}$. Furthermore, we impose that
$\frac{\pi(m^{+}-4m^{-})}{4m^{-}}>1$. In this setting let us consider the
family
$\mathcal{A}=\mathcal{A}(\mathbf{m},m^{+})=\\{A\subseteq\mathcal{P}:\mbox{lcm}(A)\geq
m^{+}\\}$. This is a monotonous increasing family, so we may consider it as an
access structure over $\mathcal{P}$. The set of secrets is
$\mathcal{S}=\\{s\in\mathbb{Z}\ :\ m^{-}\leq s<m^{+}\\}$. Sharing and
reconstruction of secrets is carried out as in the original Mignotte scheme.

Another extension of Mignotte’s scheme to the ring of polynomials in one
variable over a finite field, $\mathbb{F}_{q}[X]$, was given in [5]. Following
this idea, other extensions of the method to Euclidean rings have been made,
such as [10] or [13]. From now on we will focus on the extension to Gaussian
Integers.

###  2.5. The ring of Gaussian Integers

A Gaussian Integer is a complex number $z=a+bi$, where both $a$ and $b$ are
integers. The set of Gaussian Integers is thus $\mathbb{Z}[i]$. Over this ring
we may consider the Euclidean function norm of $z$,
$N(z)=a^{2}+b^{2}=z\overline{z}$ (where $\overline{z}$ denotes the complex
conjugated of $z$). Thus the norm is multiplicative, $N(vz)=N(v)N(z)$ for all
$v,z\in\mathbb{Z}[i]$ and satisfies $N(v)\leq N(vz)$ if $z\neq 0$.

The most interesting arithmetic property of $\mathbb{Z}[i]$ is the existence
of an Euclidean division with respect to the norm: given $v,z\in\mathbb{Z}[i]$
with $z\neq 0$, there exist $q,r\in\mathbb{Z}[i]$ such that $v=zq+r$ with
$N(r)<N(z)$. We say that $\mathbb{Z}[i]$ is an Euclidean Domain. Thus
$\mathbb{Z}[i]$ is also a Principal Ideal Domain [4], and therefore a Chinese
remainder theorem similar to Theorem 1, holds over it.

We observe, however, that the quotient and remainder of the Euclidean division
are not uniquely determined, unlike what we have over $\mathbb{F}_{q}[X]$ or
what we can do over $\mathbb{Z}$, see [8]. For example we have
$10i=(5+4i)(1+i)+(i-1)=(5+4i)(1+2i)+(3-4i)$. Thus there is no a consistent way
to define the expression $v\;(\mbox{mod}\;z)$, as it does not uniquely
identify any element. As a result, the solution of a system of congruence
equations is not uniquely determined.

###  2.6. The Mignotte SSS over $\mathbb{Z}[i]$ of [10]

In [10] the authors propose an extension of Mignotte’s scheme to a threshold
$(t,n)$ SSS over $\mathbb{Z}[i]$, and they use this extension to give a method
for sharing secret images. However they did not take into account the lack of
uniqueness of Euclidean division. This causes that the proposed SSS may lead
to reconstruct the wrong secrets.

The method goes as expected: In order to share a secret among a set
$\mathcal{P}$ of $n$ participants, we begin from a sequence
$\mathbf{m}:m_{1},\dots,m_{n}$ of pairwise coprime Gaussian Integers such that
$N(m_{1})<\cdots<N(m_{n})$ and $N(m_{n-t+2}\cdots m_{n})<N(m_{1}\cdots
m_{t})$. The set of secrets is
$\mathcal{S}=\\{s\in\mathbb{Z}[i]:N(m_{n-t+2}\cdots m_{n})\leq
N(s)<N(m_{1}\cdots m_{t})\\}$. The sharing of a secret $s\in\mathcal{S}$ and
its subsequent reconstruction are performed in the usual way: Given a secret
$s$, the share of participant $i$ is $s_{i}=s\ (\mbox{\rm mod }m_{i})$. A
coalition $A$ with $|A|\geq t$, may recover the secret by solving the system

$(S_{A})\hskip 34.1433ptx\equiv s_{i}\;(\mbox{\rm mod }m_{i}),\hskip
11.38109pti\in A.$

We will now show an example of how it operates and how it may lead to
mistakes.

######  Example 1.

(Example 3.3 of [10]). Let $n=3$, $\mathbf{m}:7+4i,-3-13i,11+8i$ and take
$t=2$. The set of secrets is then $\mathcal{S}=\\{s\in\mathbb{Z}[i]:185\leq
N(s)<11570\\}$. Let $s=70-70i$. Note that $N(s)=9800$ so $s$ is a valid
secret. The shares are $s_{1}=1+2i,s_{2}=4,s_{3}=3-i$. The authorized
coalition $\\{2,3\\}$ wants to recover the secret. To that end they solve the
system

$\left\\{\begin{array}[]{lll}x\equiv&4&(\mbox{\rm mod }-3-13i)\\\
x\equiv&3-i&(\mbox{\rm mod }11+8i)\\\ \end{array}\right.$

whose solution is $x=70-70i$, but also $x=-1+97i$, and both are valid secrets.
Most computer systems choose the solution of smaller norm. Since
$N(-1+97i)=9410<N(70+70i)=9800$, then the coalition $\\{2,3\\}$ recovers
$s=-1+97i$, which is a wrong secret.

##  3\. A Mignotte SSS over Gaussian Integers

We now aim to develop an extension of Mignotte SSS to Gaussian Integers,
making sure that the remainders are uniquely determined. That is, to ensure
that the expression $v\ (\mbox{\rm mod }z)$ refers to a unique element of
$\mathbb{Z}[i]$. On top of that, we will not impose the condition that the
modules $m_{1},\cdots,m_{n}$ are coprime, so that we find more general
schemes.

###  3.1. Fundamental domains

In order to ensure the uniqueness of the remainder, we will operate in
restrictions of $\mathbb{Z}[i]$. Let $z\in\mathbb{Z}[i]$, $z\neq 0$.We may
define the fundamental domain of $z$ is the subset of $\mathbb{C}$

$\mathcal{F}(z)=\\{z(\alpha+\beta i)\ :\
\alpha,\beta\in\mathbb{R},\mbox{$-\frac{1}{2}<\alpha,\beta\leq\frac{1}{2}$}\\}.$

Geometrically $\mathcal{F}(z)$ is a semi-open square in
$\mathbb{C}\sim\mathbb{R}^{2}$, with vertices

$z(\frac{1}{2}+\frac{1}{2}i),\;z(\frac{1}{2}-\frac{1}{2}i),\;z(-\frac{1}{2}-\frac{1}{2}i),\,z(-\frac{1}{2}+\frac{1}{2}i).$

As seen in the above figure $\mathcal{F}(z)$ is centered at 0 and has side
length $|z|=\sqrt{N(z)}$ . Note that for every Gaussian Integer
$v\in\mathcal{F}(z)$ it holds that $N(v)\leq N(z)/2$. On this space, we find
the following.

######  Proposition 2.

Given two Gaussian Integers $v,z\in\mathbb{Z}[i]$ with $z\neq 0$, there exists
$q,r\in\mathbb{Z}[i]$ such that $r\in\mathcal{F}(z)$ and $v=zq+r$. Moreover
such $q$ and $r$ are unique and $N(r)\leq N(z)/2$.

###### Proof.

Let us consider the complex number $v/z=x+yi$. Let $a$, $b$ be the integers
$a=\lceil x-\frac{1}{2}\rceil$ and $b=\lceil y-\frac{1}{2}\rceil$. Thus
$-\frac{1}{2}<x-a\leq\frac{1}{2}$, $-\frac{1}{2}<y-b\leq\frac{1}{2}$. Let
$q=a+bi$. Then $v=zq+(z(v/z-q))=zq+r$ where
$r=z(v/z-q)=z((x-a)+(y-b)i)\in\mathcal{F}(z)$. To see the uniqueness, if
$zq_{1}+r_{1}=zq_{2}+r_{2}$ with $r_{1},r_{2}\in\mathcal{F}(z)$, then write
$r_{1}=z(\alpha_{1}+\beta_{1}i)$, $r_{2}=z(\alpha_{2}+\beta_{2}i)$ with
$-\frac{1}{2}<\alpha_{1},\beta_{1},\alpha_{2},\beta_{2}\leq\frac{1}{2}$. We
have
$z(q_{2}-q_{1})=r_{1}-r_{2}=z((\alpha_{1}-\alpha_{2})+(\beta_{1}-\beta_{2})i)$,
hence $\alpha_{1}-\alpha_{2}$ and $\beta_{1}-\beta_{2}$ are both integers. So
$\alpha_{1}=\alpha_{2}$ and $\beta_{1}=\beta_{2}$. The last statement,
$N(r)\leq N(z)/2$, is a consequence of the fact that $r\in\mathcal{F}(z)$. ∎

Given $v,z\in\mathbb{Z}[i]$ with $z\neq 0$ as above, we say that the unique
remainder $r\in\mathcal{F}(z)$ of the division $v=zq+r$, is the principal
value of $v\ (\mbox{\rm mod }z)$. We will write this as $r=v\ (\mbox{\bf mod
}z)$. Let us note that the above proof gives a procedure to explicitly compute
this number.

Besides $\mathcal{F}(z)$ we shall also consider the strict fundamental domain
of $z$, which is the set $\mathcal{F}^{o}(z)$ of points in $\mathcal{F}(z)$
but not on its border

$\mathcal{F}^{o}(z)=\\{z(\alpha+\beta i)\ :\
\alpha,\beta\in\mathbb{R},\mbox{$-\frac{1}{2}<\alpha,\beta<\frac{1}{2})$}\\}$

and the closure of $\mathcal{F}(z)$

$\overline{\mathcal{F}}(z)=\\{z(\alpha+\beta i)\ :\
\alpha,\beta\in\mathbb{R},\mbox{$-\frac{1}{2}\leq\alpha,\beta\leq\frac{1}{2})$}\\}.$

Clearly
$\mathcal{F}^{o}(z)\subset\mathcal{F}(z)\subset\overline{\mathcal{F}}(z)$. Now
we will expose some properties of these domains, that will allow us to
successfully develop the scheme.

######  Proposition 3.

Let $v,z\in\mathbb{Z}[i]$, $z\neq 0$.
(a) If $N(v)<N(z)/2$, then ${\mathcal{F}}(v)\subset{\mathcal{F}}(z)$.
(b)
$\\{u\in\mathbb{Z}[i]:N(u)<N(z/2)\\}\subset{\mathcal{F}}^{o}(z)\subset\\{u\in\mathbb{Z}[i]:N(u)\leq
N(z)/2\\}$.

###### Proof.

(a) Since both ${\mathcal{F}}(v)$ and ${\mathcal{F}}(z)$ are squares centered
at 0, it suffices to see that the highest norm of an element in
${\mathcal{F}}(v)$ is less than the smallest norm of an element on the border
of ${\mathcal{F}}(z)$. As these are reached at $v(\frac{1}{2}+\frac{1}{2}i)$
and $z(\frac{1}{2})$ respectively, the inclusion is a consequence of the chain
of inequalities

$N\left(v(\frac{1}{2}+\frac{1}{2}i)\right)=\frac{1}{2}N(v)<\frac{1}{4}N(z)=N\left(z(\frac{1}{2})\right)$.

(b) The left hand inclusion holds because the element with the lowest norm on
the border of ${\mathcal{F}}(z)$ has norm $N(z)/4$. The right hand one is due
to the property of the normalized remainder $r$ in the Euclidean division that
$N(r)\leq N(z)/2$. ∎

The units (that is, the invertible elements) of $\mathbb{Z}[i]$ are precisely
the elements with norm 1, that is $\pm 1,\pm i$. The associates of a Gaussian
integer $z$ are the products $uz$, where $u$ is a unit. Thus, the associates
of $z$ are $\pm z,\pm iz$. Clearly two associated numbers $z$ and $uz$
generate the same ideal in $\mathbb{Z}[i]$. So given
$z_{1},\dots,z_{n}\in\mathbb{Z}[i]$, the expressions $\mbox{\rm
gcd}(z_{1},\dots,z_{n})$ and $\mbox{\rm lcm}(z_{1},\dots,z_{n})$ are defined
up to associates. Note that in general $\mathcal{F}(z)\neq\mathcal{F}(uz)$ and
thus, for $v\in\mathbb{Z}[i]$, we may have $v\ (\mbox{\bf mod }z)\neq v\
(\mbox{\bf mod }uz)$. For example, $z/2\in\mathcal{F}(z)$ but
$z/2\notin\mathcal{F}(-z)$ and thus, if $z/2\in\mathbb{Z}[i]$ then we have
$z/2\ (\mbox{\bf mod }z)=z/2,z/2\ (\mbox{\bf mod }-z)=-z/2$.

######  Proposition 4.

Let $u,v,z$ be three Gaussian Integers such that $u$ is a unit. The following
properties hold.
(a) $\mathcal{F}^{o}(z)=\mathcal{F}^{o}(uz)$ and
$\overline{\mathcal{F}}(z)=\overline{\mathcal{F}}(uz)$.
(b) If $v\ (\mbox{\bf mod }z)\in\mathcal{F}^{o}(z)$, then $v\ (\mbox{\bf mod
}uz)=v\ (\mbox{\bf mod }z)$.

###### Proof.

The proof of (a) is straightforward from the definitions of
$\mathcal{F}^{o}(z)$ and $\overline{\mathcal{F}}(z)$. (b) If $v=qz+r$ then
also $v=(q/u)uz+r$, so the result is a direct consequence of (a). ∎

As a consequence of this result we find that if $v\ (\mbox{\rm mod }\mbox{\rm
lcm}(z_{1},\dots,z_{n}))\in\mathcal{F}^{o}(\mbox{\rm lcm}(z_{1},\dots,z_{n}))$
for some choice of $\mbox{\rm lcm}(z_{1},\dots,z_{n})$ and $v\ (\mbox{\rm mod
}\mbox{\rm lcm}(z_{1},\dots,z_{n}))$, then the Gaussian Integer given by the
expression $v\ (\mbox{\bf mod }\mbox{\rm lcm}(z_{1},\dots,z_{n}))$ is uniquely
determined, and moreover $v\ (\mbox{\bf mod }\mbox{\rm
lcm}(z_{1},\dots,z_{n}))\in\mathcal{F}^{o}(\mbox{\rm
lcm}(z_{1},\dots,z_{n}))$.

######  Proposition 5.

Let $v_{1},v_{2},z$ be Gaussian Integers such that
$v_{1},v_{2}\in\overline{\mathcal{F}}(z)$. If $v_{1}\equiv v_{2}\ (\mbox{\rm
mod }z)$ and $v_{1}\in\mathcal{F}^{o}(z)$, then $v_{1}=v_{2}$.

###### Proof.

If $v_{1}\equiv v_{2}\ (\mbox{\rm mod }z)$ with
$v_{1}\in\mathcal{F}^{o}(z),v_{2}\in\overline{\mathcal{F}}(z)$, then there
exist a unit $u$ such that $v_{1},v_{2}\in\mathcal{F}(uz)$. The result follows
from the uniqueness of the remainder in a fundamental domain stated in
Proposition 2. ∎

###  3.2. A Mignotte SSS over $\mathbb{Z}[i]$

Now that we have found a way to guarantee the uniqueness of a remainder, we
may expose the desired extension of the scheme. Let
${\mathcal{P}}=\\{1,\dots,n\\}$ be a set of $n$ participants and let
$\mathbf{m}:m_{1},m_{2},\dots,m_{n}$, be a sequence of $n$ (not necessarily
pairwise coprime) non-zero Gaussian Integers. We assign the Gaussian Integer
$m_{i}$ to each participant $i$. To abbreviate, given a coalition
$C\subseteq{\mathcal{P}}$ we write $\mbox{lcm}(C)=\mbox{lcm}\\{m_{i}\ :\ i\in
C\\}$. We say that $N(\mbox{lcm}(C))$ is the norm of $C$.

Let $m^{-},m^{+}$ be two integers such that $4m^{-}<m^{+}$ and the norm of no
coalition lies within the interval $(m^{-},m^{+})$ , that is, for all
$C\subseteq{\mathcal{P}}$ we have either $N(\mbox{lcm}(C))\leq m^{-}$ or
$N(\mbox{lcm}(C))\geq m^{+}$. Furthermore, we impose that
$\frac{\pi(m^{+}-4m^{-})}{4m^{-}}>1$. We may now consider the access structure
over $\mathcal{P}$

${\mathcal{A}}=\\{A\subseteq{\mathcal{P}}\ :\ N(\mbox{lcm}(A))\geq m^{+}\\}.$

Let us now develop a SSS $\mathcal{R}$ realizing the structure $\mathcal{A}$.
The set of secrets to be shared is

${\mathcal{S}}=\\{s\in Z[i]\ :\ m^{-}\leq N(s)<\frac{m^{+}}{4}\\}.$

The procedure goes as usual. Given a secret $s\in{\mathcal{S}}$, the shares
$s_{i}$ are $s_{i}=s\ (\mbox{\bf mod }m_{i})$. If an authorized coalition $A$
wants to recover the secret, they may solve the system of congruence equations

$(S_{A})\hskip 28.45274ptx\equiv s_{i}\ (\mbox{mod }m_{i})\hskip
28.45274pti\in A$

whose solution is unique modulo $\mbox{lcm}(A)$. The secret is $x\ (\mbox{{\bf
mod} lcm}(A))$.

Please note that for any coalition $C$ the corresponding system $(S_{C})$ has
a solution, since $s\ (\mbox{mod lcm}(C))$ is so. Thus we only need the
Chinese theorem to find the solution and to guarantee its uniqueness.

######  Theorem 6.

The above method is correct and gives a secret sharing scheme whose access
structure is $\mathcal{A}$.

###### Proof.

An authorized coalition $A$ can solve the system and, from the solution $x$,
obtain $x\ (\mbox{{\bf mod} lcm}(A))\in{\mathcal{F}}(\mbox{lcm}(A))$. Since
$N(s)<m^{+}/4\leq N(\mbox{lcm }(A))/4$, Proposition 3 guarantees that
$s\in\mathcal{F}^{o}(\mbox{lcm}(A))$, and by Proposition 4 this holds for any
choice of $\mbox{lcm}(A)$. Then, from Proposition 5, we have $x\ (\mbox{{\bf
mod} lcm}(A))=s$, and $A$ successfully recovers the secret. An unauthorized
coalition $B$ may find the solution $x$ of $(S_{B})$ modulo $\mbox{lcm}(B)$.
However, since $N(s)\geq m^{-}\geq N(\mbox{lcm}(B))>N(x)$, it holds that
$s\neq x$. $B$ can also compute $x\ (\mbox{{\bf mod}
lcm}(B))\in{\mathcal{F}}(\mbox{lcm}(B))$. But since $N(s)>m^{-}/2>N(\mbox{lcm
}(B))/2$, again according to Proposition 3, we have
$s\not\in{\mathcal{F}}(\mbox{lcm}(B))$. Hence $x\ (\mbox{{\bf mod}
lcm}(B))\neq s$. We focus on this on section 3.3. ∎

######  Example 2.

We will now see how Example 1 would work under this new method. Let $n=3$,
$\mathbf{m}:7+4i,-3-13i,11+8i$ and take $t=2$. The set of secrets will now be
$\mathcal{S}=\\{s\in\mathbb{Z}[i]:185\leq N(s)<2892\\}$. Let $s=70-70i$. Note
that $N(s)=9800$ so $s$ is not a valid secret, and thus cannot be shared. This
explains why the method proposed in [10] does not work on this case.

###  3.3. Some Properties

Once the method is described we may study some of its properties. Computing
the information rate of this scheme leads to the so called Gauss circle
problem, which asks about the number of Gaussian Integers inside a circle of
radius $r>0$ centered at the origin. That is to say, the number of Gaussian
Integers $z$ such that $N(z)\leq N(r)=r^{2}$, [6]. We denote this number by
$\mathfrak{N}(r)$. Since, on average, each unit square contains one Gaussian
Integer, $\mathfrak{N}(r)$ is approximately equal to the area of a circle of
radius $r$,

$\mathfrak{N}(r)\sim\pi r^{2}$

It is also known a explicit expression for this number:

$\mathfrak{N}(r)=1+4\sum_{j=0}^{\infty}(\lfloor\frac{r^{2}}{4j+1}\rfloor-\lfloor\frac{r^{2}}{4j+3}\rfloor)$

Then the number of possible secrets to be shared is

$|{\mathcal{S}}|=\mathfrak{N}(\frac{\sqrt{m^{+}-1}}{2})-\mathfrak{N}(\sqrt{m^{-}-1})$
$=4\sum_{j=0}^{\infty}(\lfloor\frac{m^{+}-1}{16j+16}\rfloor-\lfloor\frac{m^{+}-1}{16j+12}\rfloor)-\\{4\sum_{j=0}^{\infty}(\lfloor\frac{m^{-}-1}{4j+1}\rfloor-\lfloor\frac{m^{-}-1}{4j+3}\rfloor)\\}$
$\sim\pi\left(\frac{m^{+}-1}{4}-m^{-}+1\right)\sim\pi\left(\frac{m^{+}}{4}-m^{-}\right).$

On the other hand, the set $\mathcal{S}_{i}$ of possible shares for
participant $i$ is precisely the set of congruence classes of Gaussian
Integers modulo $m_{i}$. It is well known that the number of such congruence
classes is the norm $N(m_{i})$, [4].

Unfortunately, the scheme is not perfect. An unauthorized coalition $B$ can
solve $(S_{B})$ and thus it may compute $x=s\ (\mbox{mod lcm}(B))$. So it may
deduce that the secret is of the form $x+\lambda\mbox{ lcm}(B)$ for some
$\lambda\in Z[i]$. Thus it can discard all secrets of $\mathcal{S}$ not
satisfying this condition. Since $N(\mbox{\rm lcm}(B))<m^{-}$, this fact
reduces for $B$ the set of secrets to a set of cardinality equal to

$\left\\{4\sum_{j=0}^{\infty}(\lfloor\frac{m^{+}-1}{16j+16}\rfloor-\lfloor\frac{m^{+}-1}{16j+12}\rfloor)-\\{4\sum_{j=0}^{\infty}(\lfloor\frac{m^{-}-1}{4j+1}\rfloor-\lfloor\frac{m^{-}-1}{4j+3}\rfloor)\\}\right\\}/N(lcm(B))$

$\sim\frac{\pi(m^{+}-4m^{-})/4}{N(\mbox{\rm
lcm}(B))}>\frac{\pi(m^{+}-4m^{-})}{4m^{-}}.$

So this number should be large enough in order to guarantee the security of
the scheme. Note that we have imposed that number to be larger than $2$, so
that the coalition $B$ never compute the correct secret.

######  Example 3.

Let $\mathbf{m}$ be the sequence of pairwise coprime Gaussian Integers
$\mathbf{m}:15+14i,10-18i,13+16i$. Take $m^{-}=425,m^{+}=178504$. This choice
leads to a $(2,3)$ threshold access structure. The set of secrets is
$\mathcal{S}=\\{s\in\mathbb{Z}[i]:425\leq N(s)\leq 44625\\}$. The number of
possible secrets is then

$|{\mathcal{S}}|=\mathfrak{N}(\sqrt{44625})-\mathfrak{N}(\sqrt{424})\sim
138858$

while the set of possible shares has cardinality at most $N(13+16i)=425$. Of
course the scheme is not perfect. As noted before, an unauthorized coalition
$B$ can reduce the whole set of secrets to a set of size at least
(approximately)

$\frac{\pi\left((m^{+}/4)^{2}-(m^{-}-1)^{2}\right)}{m^{-}}\approx 327.$

###  3.4. Any access structure can be realized by a Mignotte SSS over
$\mathbb{Z}[i]$

An interesting question is to characterize those access structures that can be
realized by a Mignotte construction. The next proposition is analogous to
Theorem 2.2 of [5]. Even the proof is an adaptation of it, we will include it
for the convenience of the reader.

######  Theorem 7.

For any access structure $\mathcal{A}$ over $n$ participants and any integer
$S$, there is sequence $\mathbf{m}:m_{1},\dots,m_{n}$ of Gaussian Integers
such that the Mignotte SSS over $\mathbb{Z}[i]$ arising from $\mathbf{m}$
realizes the structure $\mathcal{A}$ with a set of secrets $\mathcal{S}$ of
cardinality $|\mathcal{S}|\geq S$.

###### Proof.

Let $\mathcal{A}$ be an access structure over a set $\mathcal{P}$ of $n$
participants and let $B_{1},\dots,B_{t}$ be the maximal unauthorized
coalitions for $\mathcal{A}$. Choose $t$ pairwise coprime Gaussian Integers
$\mu^{(1)},\dots,\mu^{(t)}$ with $N(\mu^{(j)})>8$ for all $j=1,\dots,t$, and
let $\mu=\mu^{(1)}\cdots\mu^{(t)}$. Now for $i=1,\dots,n$ and $j=1,\dots,t$,
define

${\mu}^{(j)}_{i}=\left\\{\begin{array}[]{ll}1&\mbox{if $i\in B_{j}$}\\\
{\mu}^{(j)}&\mbox{if $i\not\in B_{j}$}\end{array}\right.$

and $m_{i}={\mu}^{(1)}_{i}\cdots{\mu}^{(t)}_{i}$. Then the Mignotte scheme
associated to the sequence $\mathbf{m}:m_{1},\dots,m_{n}$ realizes the
structure $\mathcal{A}$. To see that let

$m^{+}=N({\mu})\;\mbox{ and
}\;\ell=m^{+}/\min\\{N({\mu}^{(1)}),\dots,N({\mu}^{(t)})\\}.$

Note that $4\ell<m^{+}$. Let $A\in\mathcal{A}$ be an authorized coalition. For
each maximal unauthorized coalition $B_{j}$ there is a participant $i$
(depending on $j$) such that $i\in A\setminus B_{j}$. Thus
${\mu}^{(j)}_{i}={\mu}^{(j)}$ and hence ${\mu}^{(j)}|\mbox{lcm}(A)$. Since
this reasoning holds for any $j=1,\dots,t$, we conclude that
$\mbox{lcm}(A)={\mu}$, so $N(\mbox{lcm}(A))=m^{+}$. Conversely, let $B$ be an
unauthorized coalition. Then there exists $j$ such that $B\subseteq B_{j}$. It
follows that ${\mu}^{(j)}_{i}=1$ for all $i\in B$, and hence
$N(\mbox{lcm}(B))\leq m^{+}/N({\mu}^{(j)})\leq\ell$. We have proved that
${\mathcal{A}}=\\{A\subseteq{\mathcal{P}}\ |\ N(\mbox{lcm}(A))\geq m^{+}\\}$,
so the sequence $\mathbf{m}:m_{1},\dots,m_{n}$ realizes the structure
$\mathcal{A}$ with set of secrets $\mathcal{S}=\\{s\in Z[i]\ :\ m^{-}\leq
N(s)<\frac{m^{+}}{4}\\}$, where
$m^{-}=\max\\{N(\mbox{lcm}(B_{1})),\dots,N(\mbox{lcm}(B_{t}))\\}\leq\ell$.
Since $\frac{m^{+}}{4}-m^{-}\geq\ell$, by choosing the Gaussian Integers
$\mu^{(1)},\dots,\mu^{(t)}$ having large enough norm, it is clear that we can
always get $|\mathcal{S}|\geq S$. ∎

The simplest case of Mignotte’s construction arises when all the numbers in
the sequence $\mathbf{m}$ are pairwise coprime. Let us recall that an access
structure $\mathcal{A}$ is weighted threshold if there is an $n$-tuple
$\mathbf{w}=(w_{1},\dots,w_{n})$ of positive weights and a threshold $t$ such
that $\mathcal{A}=\\{A\subseteq\mathcal{P}:\sum_{i\in A}w_{i}\geq t\\}$. The
proof that a weighted access structure defined by real weights can be also
written by using integer weights is straightforward.

######  Proposition 8.

If the Gaussian Integers in the sequence $\mathbf{m}:m_{1},m_{2},\cdots,m_{n}$
are pairwise coprime, then for any $m^{+}$ the access structure
$\mathcal{A}(\mathbf{m},m^{+})$ is a weighted threshold access structure.

###### Proof.

A coalition $C$ is authorized if and only if $N(\mbox{lcm}(C))=\prod_{i\in
C}N(m_{i})\geq m^{+}$, that is if and only if $\sum_{i\in
C}\log(N(m_{i}))\geq\log(m^{+})$, so $\mathcal{A}(\mathbf{m},m^{+})$ is
weighted threshold structure with weights $\log(N(m_{i}))$, $j=1\dots,n$, and
threshold $\log(m^{+})$.

∎

######  Example 4.

Let $\mathbf{m}$ be the sequence of pairwise coprime Gaussian Integers
$\mathbf{m}:6+5i,1-9i,13+16i$, and take $m^{-}=5002,m^{+}=25925$. This
sequence leads to the access structure $\mathcal{A}$ whose minimal authorized
coalitions are $\\{1,3\\}$ and $\\{2,3\\}$, which certainly is a weighted
threshold access structure with weights $1,1,2$ and threshold $t=3$.

## References

  * [1] C. A. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE Transactions on Information Theory 29 (1983), 208–210. https://ieeexplore.ieee.org/document/1056651
  * [2] R. Blahut, Algebraic Methods for Signal Processing and Communications. Springer Verlag, 1992.
  * [3] P. Dingyi, S. Arto and D. Cunsheng, Chinese Remainder Theorem: Applications in Computing, Coding and Cryptography. World Scientific, 1996.
  * [4] J.B. Fraleigh, A First Course In Abstract Algebra (2nd ed.). Addison-Wesley, 1976.
  * [5] T. Galibus and G. Matveev, Generalized Mignotte’s Sequences over Polynomial Rings, Electronic Notes in Theoretical Computer Science 186 (2007), 43–48.
  * [6] R.K. Guy, Unsolved problems in number theory (3rd ed.). Springer-Verlag, 2004.
  * [7] S. Iftene, General secret sharing based on the Chinese Remainder Theorem with applications in E–Voting, Electronic Notes in Theoretical Computer Science 186 (2007) 67–84.
  * [8] M.A. Jodeit, Uniqueness in the division algorithm, Amer. Math. Montly 74 (1967), 835-836.
  * [9] M. Mignotte, How to share a secret. In Proceedings of the Workshop on Cryptography Burg Feuerstein, 1982. LNCS-149, Springer-Verlag, 1983, 371–375.
  * [10] I. Ozbek, F. Temiz and I. Siap, A generalization of the Mignotte’s scheme over Euclidean domains and applications to secret image sharing, J. Algebra Comb. Discrete Appl. 6 (2019) 147–161. https://dergipark.org.tr/en/pub/jacodesmath/issue/48724/617239
  * [11] A. Shamir, How to share a secret?, Communications of ACM 22 (1979), 612–613.
  * [12] D. Stinson, Cryptography: Theory and Practice. CRC Press 2005.
  * [13] G. Ulutas, M. Ulutas, V. Nabiyev, Secret sharing scheme based on Mignotte’s scheme, 2011 IEEE 19th Signal Processing and Communications Applications Conference, Antalya, 2011, 291–294. doi: 10.1109/SIU.2011.5929644


# Cluster and Separate: a GNN Approach to
Voice and Staff Prediction for Score Engraving

###### Abstract

This paper approaches the problem of separating the notes from a quantised
symbolic music piece (e.g., a MIDI file) into multiple voices and staves. This
is a fundamental part of the larger task of music score engraving (or score
typesetting), which aims to produce readable musical scores for human
performers. We focus on piano music and support homophonic voices, i.e.,
voices that can contain chords, and cross-staff voices, which are notably
difficult tasks that have often been overlooked in previous research. We
propose an end-to-end system based on graph neural networks that clusters
notes that belong to the same chord and connects them with edges if they are
part of a voice. Our results show clear and consistent improvements over a
previous approach on two datasets of different styles. To aid the qualitative
analysis of our results, we support the export in symbolic music formats and
provide a direct visualisation of our outputs graph over the musical score.
All code and pre-trained models are available at
https://github.com/CPJKU/piano_svsep.

##  1 Introduction

The musical score is an important tool for musicians due to its ability to
convey musical information in a compact graphical form. Compared to other
music representations that may be easier to define and process for machines,
for example, MIDI files, the musical score is characterized by how efficiently
trained musicians can read it.

An important factor that affects the readability of a musical score for
instruments that can produce more than one note simultaneously, is the
separation of notes into different voices (see Figure 1). This division may
follow what a listener perceives as independent auditory streams [1], which
can also be reflected in a clearer visual rendition of a musical score [2]. A
similar point can be made for the division into multiple staves (generally 2)
for instruments with a large pitch range, such as piano, organ, harp, or
marimba. We will consider in this paper piano music.

The term voice is frequently used to describe a sequence of musical notes that
do not overlap, which we call a monophonic voice. However, this definition may
be insufficient when considering polyphonic instruments. Voices could contain
chords, which are groups of synchronous notes (i.e., notes with the same onset
and offset) and are perceived as a single entity [3]. We name a voice that can
contain chords a homophonic voice. Note that partially overlapping notes
cannot be part of a homophonic voice.

Music encoded in MIDI (or similar) formats, even when containing quantized
notes, time signature, or bar information, often does not contain voice and
staff information. The same can be said for the output of music generation
[4], transcription [5], or arranging [6] systems. Therefore, such music cannot
be effectively converted into a musical score, to be efficiently read and
played by human musicians.111Voice and staff separation are only two of the
multiple elements, such as pitch spelling, rhythmic grouping, and tuplet
creations, which need to be targeted by a score engraving system, but we will
only focus on the former two in this paper. The tasks of producing voice and
staff information from unstructured symbolic music input are called voice
separation (or voice segregation in some papers [3]) and staff separation,
respectively.

Figure 1: Comparing different voice/staff assignments for two bars from C.
Debussy’s Estampes - Pagodes. (top) original; voices can be inferred from the
beam grouping and (horizontal lines connecting notes), rests, and stem
sharing, and are colored for clarity. (bottom) hard-to-read rendition with
voice and staff assigned according to heuristics we propose as a baseline.

Most of the existing approaches to voice separation have focused only on music
with monophonic voices [7, 8, 9, 10, 11, 12], which is not sufficient for our
goal of engraving222“score engraving” and “score typesetting” are used
interchangingly. piano music. The task of homophonic voice separation is much
harder to solve: the presence of chords within voices makes the space of
solutions grow much bigger; and the choice of the “true voice separation” can
be ambiguous, with multiple valid alternatives among which experts may
disagree.

The existing approaches to homophonic voice separation can be divided into two
groups: the first [1, 13, 3, 5] use dynamic programming algorithms based on a
set of heuristics, which makes for systems that are controllable and
interpretable, but also hard to develop and tune. Such systems are often prone
to fail on exceptions and corner cases that are present in musical pieces. The
second group of approaches [14, 15, 16, 17] applies deep learning models to
predict a voice label for each note. Such an approach creates two fundamental
issues: i) the necessity of setting a maximum number of voice labels, and ii)
a (highly) unbalanced ratio of occurrence of some voice labels. Moreover, all
these approaches assume that a voice cannot move between the two staves, which
is not true for complex piano pieces.

In this work, we propose a novel system for homophonic voice separation that
can efficiently and effectively assign notes to voices and staves for
polyphonic music engraving. Efficiency is ensured by a graph neural network
(GNN) encoder, which can create input embeddings with a relatively small
number of parameters. Effectiveness is targeted by approaching voice
prediction not as a note labeling, but as an edge prediction problem [12],
which solves the maximum voice number and the label imbalance problems
presented above. Our system predicts staff and voice separately and does not
make any assumption on the number of voices; therefore it can deal with cross-
staff voices and complex corner cases. We avoid the problem of ground truth
ambiguity since we focus specifically on voice separation for musical score
engraving, therefore we can extract the (unique) ground truth directly from
digitized musical scores.

We evaluate our system on two piano datasets of different difficulty levels,
one containing popular, the other classical music. A comparison with a
baseline and the approach of Shibata et al. [5] shows a consistent improvement
in performance on both datasets. Finally, we develop a visualization tool to
display the input and output of our system directly on the musical score, and
discuss some predictions and comments on homophonic voice separation.

##  2 Related Work

The most influential work for this paper is the monophonic voice separation
system by Karystinaios et al. [12]. Similarly, we consider voice separation a
edge prediction task and use a similar score-to-graph routine and the same GNN
encoder. Differently from that work, we consider homophonic voices and staves
and, therefore, we extend the model formulation, the deep learning
architecture, and the postprocessing routine to deal with this information.

Shibata et al. [5] developed a voice and staff separation technique applied
after music transcription to quantized MIDI files. It works in two stages:
first, an HMM separates the notes of the two hands (which will then be used as
staff), and then a dynamic programming algorithm that maximizes the adherence
to a set of heuristics is applied to separate voices in the two hands
independently. We compare against this method since it is the most recent
approach focusing specifically on homophonic voice separation.

There are some approaches based on neural networks [15, 16, 14, 17], but they
never perform this task in isolation, but rather in combination with other
tasks such as symbolic music transcription, full scorification, and automatic
arrangement. This means that they can only train on a much smaller dataset and
a comparison would not be fair.

All the approaches mentioned before, except [12], perform voice separation as
a label prediction task, which is problematic, as discussed in the
introduction, due to the label imbalance and choice of the maximum number of
voices. The former is particularly problematic for the neural network
approaches.

##  3 Methodology

Our system inputs data in the form of a set of quantized notes (e.g., coming
from a quantized MIDI or a digitized musical score), each characterized by
pitch, onset, and offset. This information is modeled as a graph, which we
call input graph, and then passed through a GNN model to predict an output
graph containing information about voices, staves, and chord groupings. We
remind the reader that in our ‘homophonic voice’ scenario, chords are groups
of synchronous notes that belong to the same voice.

###  3.1 Input Graph

From the set of quantized notes representing a musical piece we create a
directed heterogeneous graph [18] $G_{in}=(V,E_{in},\mathcal{R}_{in})$ where
each node $v\in V$ corresponds to one and only one note, and the edges $e\in
E_{in}$ of type $r\in\mathcal{R}_{in}$ model temporal relations between notes
[12]. $\mathcal{R}_{in}$ includes 4 types of relations: onset, during, follow,
and silence, corresponding, respectively, to two notes starting at the same
time, a note starting while the other is sounding, a note starting when the
other ends, and a note starting after a time when no note is sounding. We also
create the inverse edges for during, follows, and silence relations. Each node
corresponds to a vector of features: one of the 12 note pitch classes333We
don’t consider tonal pitch classes [19] since they are not specified in MIDI
files which we assume to be our input. (C, C#, D, etc.), the octave in
$[1,\dots,7]$, the note duration, encoded as a float value $d\in[0,1]$
computed as the ratio of the note and bar durations, passed through a tanh
function to limit its value and boost resolution for shorter notes, as
proposed in [12]. We don’t consider grace notes in our system, and we remove
them from the input notes.

###  3.2 Output Graph

The output graph $G_{out}=(V,E_{out},\mathcal{R}_{out})$ has the same set $V$
of nodes as the input graph, but a staff number in $\\{0,1\\}$ is assigned to
every node. There are two edge types in $E_{out}$: chord and voice, i.e.
$\mathcal{R}_{out}=\\{\text{"chord"},\text{"voice"}\\}$.

Voice edges [8, 12] are an alternative in the literature to the more
straightforward approach of predicting a voice number for every note; the
usage of voice edges has the advantage of enabling a system to work with a
non-specified number of voices, and avoiding the label imbalance problem for
high voice numbers. Voice edges are directed edges that connect consecutive
notes (without considering rests) in the same voice. Formally, let
$u_{1},u_{2}\in V$ be two notes in the same voice then
$(u_{1},\text{"voice"},u_{2})\in E_{out}$ if and only if
$\text{offset}(u_{1})\leq\text{onset}(u_{2})$ and $\nexists\ u_{3}\in V$
within the same voice such that $\
\text{offset}(u_{1})\leq\text{onset}(u_{3})<\text{onset}(u_{2})$.

The previous definition also holds in our setting with homophonic voices. Let
us extend the definition of chord (a set of synchronous notes) to include the
limit case of a single note. Two chords are consecutive if any two notes,
respectively, from the first and second chords are consecutive. In the case of
two consecutive chords with $m$ and $n$ notes in the same voice, there will be
$m*n$ voice edges.

Chord edges are undirected and connect all notes that belong to the same chord
without self-loops, so for a $n$-note chord, there are $n(n-1)$ edges. They
serve to unambiguously identify which notes together form a single chord.

The same output graph can be created from an already properly engraved score.
To obtain the graph we only need to draw the true voice edges between
consecutive notes in the same voice within a bar and for chord edges we draw
the chord ground truth between synchronous notes with the same voice number
assignment. This graph can subsequently serve as the ground truth during
training.

###  3.3 Problem Simplification

In this section, we apply some obvious musical constraints to reduce
computation and memory usage in our pipeline, without impacting the results.
Let us first focus on chord edge prediction. Given the simple constraint that
all notes of a chord must start and end simultaneously, we can restrict the
chord edge prediction process to only consider pairs of sychronous notes (same
onset and offset values) as candidates. We do this by creating a set of chord
edge candidates $\Lambda_{c}$ which are calculated automatically and
associated with our input graph. Only notes connected by such candidate edges
will be considered in the chord prediction part of the model (see next
section).

The same reasoning can be applied to the voice edges, by creating a set of
voice edge candidates $\Lambda_{v}$ such that $\forall u_{1},u_{2}\in
V,\;(u_{1},\text{"voice"},u_{2})\in\Lambda_{v}$ only when
$\text{offset}(u_{1})>\text{onset}(u_{2})$. Another step can be taken towards
reducing the number of candidates in the set $\Lambda_{v}$ by incorporating
some musical engraving considerations.

The separation of notes in multiple voices does not have to be consistent in
the whole score, but only within each bar, to produce the intended visual
representation. There are no graphical elements that show if two notes in
different bars are or are not in the same voice444This may change for cross-
bar beamings, but they are very rarely used in standard music notation (there
are no occurrences in our datasets) and therefore we do not consider them in
this work.. Music engraving software does not force users to use consistent
voices across bars. This can be often observed in digitized musical scores
where music motives that belong to the same voice, are assigned different
voices in different bars. Such observations have motivated projects such as
the Symbolic Multitrack Contrapuntal Music Archive [20] that explicitly encode
a “global” voice number.

Since cross-bar consistency is not necessary for our goal of engraving (and is
often wrongly annotated in our data) we limit the voice edge candidates
$\Lambda_{v}$ to contain only pairs of notes that occur within the same bar.
This design choice is also reflected in our evaluation, i.e. we do not
evaluate how the voices propagate across bars, but only within each bar. Note
that this process is different from processing each bar independently since
our network (detailed in the next section) considers music content across
bars.

###  3.4 Model

Figure 2: Our Architecture. For simplification, we display the output graph as
having “hard” voice predictions, while these are probabilities over voice
candidates.

We design an end-to-end model (see Figure 2) that receives an input graph as
described in Section 3.1 and produces an output graph as in Section 3.2. The
model is organized as an encoder–decoder architecture.

The encoder receives an input graph created from a quantized MIDI score and
passes it through three stacked Graph Convolutional Network (GCN) blocks to
produce a node embedding for each note. We use the heterogeneous version of
the Sage convolutional block [18] with a hidden size of 256; the update
function for each node $u$ is described by:

$\displaystyle\begin{aligned}
\mathbf{h}_{\mathcal{N}(u)}^{(l+1)}&=\sum\left(\\{\mathbf{h}_{v}^{l},\forall
v\in\mathcal{N}(u)\\}\right)\\\
\mathbf{h}_{u}^{(l+1)}&=\sigma\left(\mathbf{W}\cdot\mathrm{concat}(\mathbf{h}_{u}^{l},\mathbf{h}_{\mathcal{N}(u)}^{l+1})\right)\\\
\end{aligned}$ (1)

where $\mathcal{N}(u)$ are the neighbors of node $u$, $\sigma$ is a non-linear
activation function, $\mathbf{W}$ is a learnable weight matrix.

The decoder consists of three parts that all use the same node embedding as
input: i) a staff predictor; ii) a voice edge predictor; and iii) a chord
clustering (i.e., a chord edge predictor). The staff predictor is a 2-layer
Multi-Layer Perceptron (MLP) classifier that produces probabilities for each
graph node (i.e., each note) to belong to the first or second staff. The voice
edge predictor receives the embeddings of pairs of notes connected by edge
candidates and produces a probability for each pair to be in the same voice.
It works by concatenating the pairs of note embeddings and applying a 2-layer
MLP. The final decoder part, chord clustering, receives the embeddings of
pairs of notes connected by chord edge candidates (i.e., pairs of synchronous
notes) and produces the probability for a pair to be merged into a chord. This
is achieved by computing the cosine similarity between the elements of the
pair. This process forces the node embeddings created by the decoder to be
similar to each other for notes of the same chord, which helps the voice
predictor produce consistent voice edge probabilities for notes of the same
chord. We apply a threshold to pass from probabilities to decisions on which
notes to cluster.

The complete model contains $\sim 3$M parameters and we train it end-to-end
with the (unweighted) sum of three Binary Cross Entropy loss functions, one
for each task.

###  3.5 Postprocessing

A straightforward approach to deciding whether to connect two notes with a
voice edge would be to threshold the predicted voice edge probabilities.
However, even when using edge and chord candidates, we could still produce
three kinds of invalid output: (1) multiple voices merging into one voice, (2)
one voice splitting into multiple voices, and (3) notes in the same chord that
are not in the same voice. To eliminate these issues, we add a postprocessing
phase that accompanies our model and guarantees a valid output according to
music engraving rules.

The first step, which we call chord pooling, merges all nodes that belong to
the same chord to a single new "virtual node". This is done by looking for the
connected components considering only chord edges in the output graph, then
pooling in a single node all original nodes in each connected component,
creating a new node which has as incoming and outgoing voice edges all edges
entering and exiting the original nodes, respectively. If multiple edges
collapse in one edge (e.g. in the case of two consecutive chords in the same
voice), the new edge has a probability that is the average of the
corresponding edge probabilities.

After the first step, we are left with monophonic streams, which could still
exhibit problems (1) and (2). We can solve this with the technique proposed in
[12] for monophonic voices, i.e. by framing the voice assignment problem as a
linear assignment problem [21] over the adjacency matrix obtained by the
updated edge candidates $\Lambda^{\prime}_{v}$. We follow the linear
assignment step by unpooling or unmerging the nodes that were previously
pooled, in this way, obtaining the original nodes again. During unpooling, the
incoming edges and outgoing edges of the "virtual nodes" are reassigned to
each original node, thus resolving problem (3).

The complete postprocessing method is depicted in Figure 3. It is worth noting
that the staff labels are not considered during the postprocessing phase, and
we copy them unchanged to the postprocessed output graph.

Figure 3: Output graph postprocessing. We do not display the predicted staff
labels.

###  3.6 Evaluation

We evaluate the predicted voice assignments with the metric proposed by
Hiramatsu et al. [15], which formalizes the metric of McLeod and Steedman
[22]. This is a version of the F1-score for voice separation [8] which is
adapted to work on homophonic voices, by reducing the importance of notes if
they are part of a chord. This is important since chords create many voice
edges (e.g., two 4-note chords in the same voice are connected by 16 edges),
which could potentially overshadow the importance of edges in monophonic
voices (or voices with fewer/smaller chords).

Formally, the homophonic voice F1-score $F1$ is calculated as:

$\begin{gathered}P=\frac{\sum_{i<j}a_{ij}\hat{a}_{ij}/\hat{w}_{i}}{\sum_{i<j}\hat{a}_{ij}/\hat{w}_{i}},\;\;\;R=\frac{\sum_{i<j}a_{ij}\hat{a}_{ij}/w_{i}}{\sum_{i<j}a_{ij}/w_{i}}\\\
F1=\frac{2PR}{P+R}\end{gathered}$ (2)

where $i<j$, in the sum, considers all pair of notes $i,j$ such that
$\text{offset}(i)<\text{onset}(j)$; $a_{ij}$, $\hat{a}_{ij}$ are equal to 1 or
0 if a voice edge exists or not in the ground truth and predictions,
respectively; and $w_{i}$ and $\hat{w}_{i}$ are the number of notes that are
chorded together with the note $i$ in the ground truth and predictions,
respectively. Unlike [15], we consider only notes $j$ in the same bar of $i$,
for the reasons presented in Section 3.3. We evaluate the staff prediction
part of our model with binary accuracy, and we assess chord prediction with
the F1 score computed on the chord edges.

Dataset | J-pop Dataset | DCML Romantic Corpus
---|---|---
Staff Acc | Chord F1 | Voice F1 | Staff Acc | Chord F1 | Voice F1
Baseline | $89.9$ | $86.9$ | $85.4$ | $80.7$ | $65.2$ | $78.2$
Shibata et al. [5] | $92.8$ | - | $92.2$ | $88.5$ | - | $84.9$
GNN wo Chord wo Post | $\textbf{96.5}\pm 0.1$ | - | $95.2\pm 1.9$ | $\textbf{91.5}\pm 0.1$ | - | $87.2\pm 3.3$
GNN wo Post | $96.3\pm 0.1$ | $\mathbf{94.9}\pm 0.1$ | $95.7\pm 0.4$ | $91.0\pm 0.1$ | $\textbf{79.5}\pm 0.4$ | $88.9\pm 0.4$
GNN | $96.3\pm 0.1$ | $\mathbf{94.9}\pm 0.1$ | $\mathbf{96.6}\pm 0.1$ | $91.0\pm 0.1$ | $\textbf{79.5}\pm 0.4$ | $\mathbf{89.9}\pm 0.2$
Table 1:  Metrics for our the J-Pop and DCML test sets. “GNN” denotes our
method, without postprocessing (“GNN wo Post”), and without both
postprocessing and chord prediction parts (“GNN wo Chord wo Post”). All GNN
model runs are repeated 5 times: $\pm$ refers to the standard deviation of
results across runs.

###  3.7 From Network Prediction to Readable Output

The computation of voice and staff numbers is sufficient for the system
evaluation, but not for producing a usable tool, which we are interested in in
this paper. The missing step, to be described in this section, is the
integration of the network predictions into a readable musical score. To
achieve this integration we need to undertake two essential steps: beam
together notes within the same voice, and infill rests to "fill holes" within
each voice.

For the first step, we proceed according to the rules of engraving [2]. We
beam two consecutive notes (or chords) in the same voices if their duration is
less than a quarter note (excluding ties) unless they belong to different
beats. Following the music notation convention we consider the compound time
signatures, i.e., $\frac{6}{x}$,$\frac{9}{x}$,$\frac{12}{x}$ to have,
respectively, 2,3, and 4 beats. When confronted with tied notes, the algorithm
prioritizes producing notations with the fewest number of notes, an heuristic
with promotes easier-to-read notation [23].

The second step consists of introducing rests so that each voice fills the
entire bar and can be correctly displayed. Some rests could be set as
invisible to improve the graphical output when their presence and duration are
easy to assume from other score elements, but we display all of them for
simplicity. As for the notes, we choose the rest types (with eventual dots) to
minimize the number of rests in the score.

The two steps described above cover common cases and produce a complete score
in MEI format [24]. However, the score export is still a prototype, since
developing one that is robust against all corner cases is an extremely complex
task, and is outside the scope of this paper. Since score output problems may
obscure the output of our system, we also develop a graph visualization tool.
Both the input and output graphs (including the candidate edges) can be
displayed on top of the musical score in an interactive web-based interface
based on Verovio [25]. Some examples of the output graph visualization are in
Figure 4.

##  4 Experiments

We train our model with the ADAM optimizer with a learning rate of $0.001$ and
a weight decay of $5*10^{-4}$ for 100 epochs. For a quantitative evaluation,
we compare our results with those of a baseline algorithm and the method
proposed by Shibata et al. [5], on two rather diverse datasets.

Our baseline algorithm assigns all notes under C4 (middle C) to the second
staff and the rest to the first. Then it groups all synchronous notes (per
staff) as chords. Finally, it uses the time and pitch distances between the
candidate pairs of notes as weights to be minimized during the linear
assignment process (the same as we use in our postprocessing) which creates
the voice edges.

###  4.1 Datasets

We use two piano datasets of different styles and difficulties to evaluate our
system under diverse conditions. The ability to handle complex corner cases
should not reduce the performance on easier (and more common) pieces.

The J-Pop dataset contains pop piano scores introduced by [5]. Most of the
scores consist of accompaniment chords on the lower staff and some simple
melodic lines on the upper staff. The dataset contains 811 scores; we randomly
sampled 159 (roughly 20%) of these for testing and used the rest for training
and validation.

The DCML Romantic Corpus is more challenging. It was created by [26] and
contains piano pieces from the 17th to 20th centuries with some virtuosic
quality. It includes characteristics such as cross-staff beaming, a high
number of voices, challenging voicing, etc. Similarly to the pop dataset we
randomly sample 77 out of the 393 scores (approx. 20%) and use the rest for
training and validation.

The J-Pop dataset is available in MusicXML format, while the DCML Romantic
Corpus is in Musescore file format. We use Musescore to convert DCML files to
MusicXML and load them with the Python library Partitura [27] to extract the
note list.

###  4.2 Results

Our model aims to be generic across a variety of music, therefore we train a
single model on the joined training set of pop and classical scores, not two
individual ones. The rules that govern the handling of voices may be
fundamentally different in the two datasets, but we assign to the model the
task of handling these differences. This approach ensures better future
scalability on bigger and more diverse datasets. We compute the metrics
separately on the test part of our two datasets.

Table 1 reports results for three versions of our graph-based model: the
complete model from Section 3, a variant without postprocessing, and a variant
without chord prediction and postprocessing (our postprocessing technique
cannot be run without the chord prediction task, since it pools nodes that
belong to the same predicted chord). The method of Shibata requires the
specification of the number of voices per staff. For compactness, we report
only the results with one voice per staff (2 voices total); the results
degrade by increasing the number of voices.

Our results show that even our system without pooling and without
postprocessing obtains consistently better results than both Shibata et al.
[5] and our baseline. Interestingly, the chord prediction task improves the
Voice F1 results even when the post-processing is not used; this confirms the
benefits of multi-task training, and of enforcing notes of the same chord to
have similar representations in the hidden space, with cosine similarity, to
predict coherent voice edges. However, we observe a reduction in staff
accuracy, probably for the same reason, since the same hidden representation
is also used to predict chords, making it harder (though not impossible) to
split notes of the same chord in different staves. When the full system is
used, there are further improvements in Voice F1.

We are also evaluate our system on the bar-level and study performances for
music excerpts of varying difficulties. We compute the voice F1 score for each
bar and average them based on the number of voices in the ground truth. We
compare with Shibata et al. [5] with 1 & 2 voices per staff (vps). Table 2
shows the results for the DCML Romantic Corpus. Both our model and [5] perform
best with 2 voices, the most common number in our dataset. Interestingly,
Shibata et al. approach with 2 vps never outperforms vps 1, not even when the
target number of voices is 3 or 4, a situation that vps 1 cannot handle. This
can be explained by the fact that Shibata et al. parameters were tuned on a
simpler dataset, and accepting more voices creates more errors than benefits.
Setting vps $>2$ consistently degraded the performances, probably also for
similar reasons.

#Voices | #Bars | GNN |  [5] 1vps |  [5] 2vps
---|---|---|---|---
1 | 322 | 96.6 | 88.3 | 87.9
2 | 4576 | 94.1 | 89.3 | 88.1
3 | 2464 | 89.0 | 84.2 | 81.5
4 | 719 | 81.6 | 80.5 | 75.1
5 | 99 | 81.6 | 76.7 | 73.7
6 | 17 | 78.4 | 68.9 | 61.6
Table 2: Voice F1 score aggregated by bars with the same number of voices in
the ground truth, on the DCML Corpus. Shibata et al. [5] is used with 1 and 2
voices per staff (vps). Figure 4: Comparison of voice and staff assignment
between the original score (Ground Truth) and our method (GNN) on the first
bars of C. Debussy’s Estampes-Pagodes. Voice edges are drawn in red and chord
edges in blue.

###  4.3 Qualitative Analysis

Let us take a closer look into the predictions of our deep-learning approach
(GNN) on the excerpt of Figure 4 produced by our visualization tool. Our
approach captures correctly the cross-staff voice in the first two bars, while
such a situation causes performance degradation for all other voice separation
approaches that don’t support it. We observe some disagreements with the
original score in Measure 3: our model predicts a single chord (instead of
splitting across the staff) containing all the synchronous syncopated quarter
notes, and also mispredicts the staff for the first D#4 note. A more in-depth
study of why this happens is not trivial, as neural networks are not
interpretable. This is a drawback compared to heuristic-based separation
techniques.

Synchronous notes with the same pitch are problematic. Our system can predict
different voices for these notes, while Shibata et al. always predict them as
a chord in the same voice, and this reduces the performances for pieces that
contain a lot of them, like Schumann Kinderszenen Op.15. For fairness, we
should note that we should expect the output of a music transcription system
to only contain one of these notes, instead of multiple like in our current
input. An enhancement of our system would then be able to receive a single
note as input, assign multiple voices to it (with multiple incoming and
outgoing edges) and then split it into multiple notes. Another current
limitation of our system is the missing support for grace notes, which in the
actual version are ignored and removed from the input.

##  5 Conclusion and Future Work

This paper presented a novel graph-based method for homophonic voice
separation and staff prediction in symbolic piano music. Our experiments
highlight our system’s effectiveness compared to previous approaches. Notably,
we obtained consistent improvements over two datasets of different styles with
a single model.

Future work will focus on integrating grace notes and the possibility of
multiple voices converging on a single note. We aim to create a framework that
produces complete engravings from quantized MIDI, including the prediction of
clef changes, beams, pitch spelling, and key signatures.

##  6 Acknowledgements

This work is supported by the European Research Council (ERC) under the EU’s
Horizon 2020 research & innovation programme, grant agreement No. 101019375
(Whither Music?), and the Federal State of Upper Austria (LIT AI Lab).

## References

  * [1] E. Cambouropoulos, “Voice and stream: Perceptual and computational modeling of voice separation,” _Music Perception_ , vol. 26, no. 1, pp. 75–94, 2008.
  * [2] E. Gould, _Behind bars: the definitive guide to music notation_. Faber Music Ltd, 2016.
  * [3] D. Makris, I. Karydis, and E. Cambouropoulos, “VISA3: Refining the voice integration/segregation algorithm,” in _Proceedings of the Sound and Music Computing Conference_ , 2016.
  * [4] Y.-S. Huang and Y.-H. Yang, “Pop music transformer: Beat-based modeling and generation of expressive pop piano compositions,” in _Proceedings of the 28th ACM International Conference on Multimedia_ , 2020, p. 1180–1188.
  * [5] K. Shibata, E. Nakamura, and K. Yoshii, “Non-local musical statistics as guides for audio-to-score piano transcription,” _Information Sciences_ , vol. 566, pp. 262–280, 2021.
  * [6] M. Terao, E. Nakamura, and K. Yoshii, “Neural band-to-piano score arrangement with stepless difficulty control,” in _ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2023, pp. 1–5.
  * [7] E. Chew and X. Wu, “Separating voices in polyphonic music: A contig mapping approach,” in _Proceedings of the International Symposium on Computer Music Modeling and Retrieval_. Springer, 2004.
  * [8] B. Duane and B. Pardo, “Streaming from midi using constraint satisfaction optimization and sequence alignment,” in _Proceedings of the International Computer Music Conference (ICMC)_ , 2009.
  * [9] P. Gray and R. C. Bunescu, “A neural greedy model for voice separation in symbolic music.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2016.
  * [10] A. McLeod and M. Steedman, “Hmm-based voice separation of midi performance,” _Journal of New Music Research_ , vol. 45, no. 1, pp. 17–26, 2016.
  * [11] Y.-W. Hsiao and L. Su, “Learning note-to-note affinity for voice segregation and melody line identification of symbolic music data.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021.
  * [12] E. Karystinaios, F. Foscarin, and G. Widmer, “Musical voice separation as link prediction: Modeling a musical perception task as a multi-trajectory tracking problem,” in _Internation Joint Conference on Artificial Intelligence (IJCAI)_ , 2023.
  * [13] J. Kilian and H. H. Hoos, “Voice separation-a local optimization approach.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_. Citeseer, 2002.
  * [14] M. Suzuki, “Score transformer: Generating musical score from note-level representation,” in _Proceedings of the 3rd ACM International Conference on Multimedia in Asia_ , 2021, pp. 1–7.
  * [15] Y. Hiramatsu, E. Nakamura, and K. Yoshii, “Joint estimation of note values and voices for audio-to-score piano transcription.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021, pp. 278–284.
  * [16] L. Liu, Q. Kong, G. Morfi, E. Benetos _et al._ , “Performance midi-to-score conversion by neural beat tracking,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2022.
  * [17] J. Zhao, G. Xia, and Y. Wang, “Q&a: Query-based representation learning for multi-track symbolic music re-arrangement,” in _Internation Joint Conference on Artificial Intelligence (IJCAI)_ , 2023.
  * [18] W. L. Hamilton, R. Ying, and J. Leskovec, “Representation learning on graphs: Methods and applications,” _IEEE Data Engineering Bulletin_ , vol. 40, no. 3, pp. 52–74, 2017.
  * [19] F. Foscarin, N. Audebert, and R. Fournier S’niehotta, “PKSpell: Data-driven pitch spelling and key signature estimation,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021.
  * [20] A. Aljanaki, S. Kalonaris, G. Micchi, and E. Nichols, “MCMA: A symbolic multitrack contrapuntal music archive,” _Empirical Musicology Review_ , vol. 16, no. 1, pp. 99–105, 2021.
  * [21] R. E. Burkard and E. Cela, “Linear assignment problems and extensions,” in _Handbook of combinatorial optimization_. Springer, 1999, pp. 75–149.
  * [22] A. McLeod and M. Steedman, “Evaluating automatic polyphonic music transcription,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2018, pp. 42–49.
  * [23] F. Foscarin, F. Jacquemard, and P. Rigaux, “Modeling and learning rhythm structure,” in _Sound and Music Computing Conference (SMC)_ , 2019.
  * [24] P. Roland, “The music encoding initiative (mei),” in _Proceedings of the First International Conference on Musical Applications Using XML_ , vol. 1060. Citeseer, 2002, pp. 55–59.
  * [25] L. Pugin, R. Zitellini, and P. Roland, “Verovio: A library for engraving mei music notation into svg,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2014.
  * [26] J. Hentschel, Y. Rammos, F. C. Moss, M. Neuwirth, and M. Rohrmeier, “An annotated corpus of tonal piano music from the long 19th century,” _Empirical Musicology Review_ , vol. 18, no. 1, pp. 84–95, 2023.
  * [27] C. E. Cancino-Chacón, S. D. Peter, E. Karystinaios, F. Foscarin, M. Grachten, and G. Widmer, “Partitura: A python package for symbolic music processing,” in _Proceedings of the Music Encoding Conference (MEC)_ , Halifax, Canada, 2022.