PERFORMANCE ERROR DETECTION AND POST-PROCESSING FORFAST AND ACCURATE SYMBOLIC MUSIC ALIGNMENT
Eita Nakamura
Kyoto University

Kazuyoshi Yoshii
Kyoto University/RIKEN AIPHaruhiro Katayose
Kwansei Gakuin University

enakamura@sap.ist.i.kyoto-u.ac.jp

yoshii@kuis.kyoto-u.ac.jp

katayose@kwansei.ac.jp

ABSTRACTThis paper presents a fast and accurate alignment method
for polyphonic symbolic music signals. It is known thatto accurately align piano performances, methods using thevoice structure are needed. However, such methods typically have high computational cost and they are applicable
only when prior voice information is given. It is pointed
out that alignment errors are typically accompanied by performance errors in the aligned signal. This suggests thepossibility of correcting (or realigning) preliminary results
by a fast (but not-so-accurate) alignment method with arefined method applied to limited segments of aligned signals, to save the computational cost. To realise this, wedevelop a method for detecting performance errors and arealignment method that works fast and accurately in local regions around performance errors. To remove the dependence on prior voice information, voice separation is
performed to the reference signal in the local regions. By
applying our method to results obtained by previously proposed hidden Markov models, the highest accuracies areachieved with short computation time. Our source code ispublished in the accompanying web page, together with auser interface to examine and correct alignment results.
1. INTRODUCTION
To computationally analyse music performances or to construct performance databases, it is needed to match notes
in a music performance signal (called an aligned signal)to those in a reference musical score or another performance signal (reference signal). This process is called music alignment and automating it is a fundamental techniquefor music information processing and has been a popular
field of research [1–16]. This study deals with offline symbolic music alignment, with particular focus on piano performances. Both score-to-MIDI alignment and MIDI-toMIDI alignment are considered in this paper. We consider
Western classical music or similar music styles where musical scores exist behind the performances.
c Eita Nakamura, Kazuyoshi Yoshii, Haruhiro Katayose.
Licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Attribution: Eita Nakamura, Kazuyoshi Yoshii,
Haruhiro Katayose. “ Performance Error Detection and Post-Processing
for Fast and Accurate Symbolic Music Alignment ”, 18th International
Society for Music Information Retrieval Conference, Suzhou, China,
2017.

Input: Reference score/MIDI signal + aligned MIDI signal
Preliminary alignment & Performance error detection
Pitch error

Reference
signalAlignedsignalReference
signalAlignedsignal

(sec)

&
?
&
?

#

#

#

&
?

#*

#

#

#

#

#

#

‹

#

#

*

#

#

#*
#

‹

#

#

#

22

#

#

#

#

22

#
#

Error regions
Realignment
Realignment

#

#

#

#

#

#*

#

Extra note

21

#

#

#

#

#

#

#

#
#

(sec)

&
?

#

#

Missing note

21

#

#
#

#

#
#

#

#

#

#
#

21

#

#

#

#

#

#

#

#

#

#

‹

#

‹

#

#

21

#

#

#
#

#

#

#
#

22

#

#

#

22

#
#

Figure 1. An outcome of the proposed method. Errors
in preliminary alignment caused by reordered note pairs in
the aligned signal are corrected by the realignment method.
Since music alignment between two identical performances is trivial, the central issue of automatic musicalignment is to handle deviations in music performances.
Possible deviations include tempo changes, performanceerrors (e.g. pitch errors, note insertions and deletions), ornamentation, and global structural differences (repeats andskips). To find the optimal alignment, various extensionsof sequence matching methods such as hidden Markov
models (HMMs) [7–9] and dynamic time warping (DTW)[1,2,6] have been studied. In the method using HMMs [7],for example, an HMM is constructed for each reference
signal, in which note insertions and deletions, repeats, andskips are described by transition probabilities, and pitch
errors are described by output probabilities. The aligned
signal is considered as an output sequence from the HMM
and the most probable sequence of latent states is estimatedwith the Viterbi algorithm for alignment.
It has been found that, in the case of polyphonic piano performances, deviations in performances due to asynchronies between hands/voices require special treatments[4, 5, 7, 9]. Such asynchronies result in reordering of notes
with different score times, which is the main cause ofalignment errors for HMMs or DTWs that are not specially designed to handle them. Models with explicit voice
structure have been proposed and proved effective to solve
this [4,5,9]. However, prior voice information of the reference signal is needed for applying these methods, which
imposes limitations on usability since voice information
is not given in single-channel MIDI signals and in somescore file formats. Moreover, these methods have highcomputational cost compared to standard HMMs or DTWs
[5–7, 9]. As is empirically known, those reordered notes
appear only occasionally and in most cases the standardalignment methods work as accurately as the refined methods using voice information. Thus, the high computational
cost would be reduced if parts of aligned signals, for which
special treatments are necessary, can be selected.
Because significant deviations in music performances
can usually be interpreted as performance errors, alignment errors are often connected with performance errors.
For example, a pair of extra and missing notes as in Fig. 1
typically appear as a result of alignment errors. Based on
the authors’ experience, displaying performance errors enables human annotators to easily find alignment errors andgreatly improves the efficiency of examining and correcting automatic alignment results. Likewise, by detecting
performance errors in a given result of automatic alignment, it would be possible to select limited regions in thealigned signal that may contain alignment errors.
Based on these observations, this study aims to develop
an automatic post-processing method for correcting given
symbolic music alignment results. We first develop a performance error detection algorithm that recognises pitch
errors, extra notes, and missing notes in a given alignment result. Error regions are then defined as segments ofaligned and reference signals around performance errors
and we investigate how much alignment errors are contained in these regions with various sizes of the regions.
Next we develop a post-processing realignment methodthat can handle hand/voice asynchrony based on a voicestructured model. Since both music alignment and recognition of performance errors involve searches for an optimal choice among possible candidate solutions, we formulate them based on statistical models whose parameters canbe optimised from data. To construct a realignment methodthat does not require prior voice information, we combine
the method using merged-output HMMs [9] with a voice(hand) separation method [17]. For concreteness, we use
as a preliminary alignment method the one based on temporal HMMs [7]. The results of the proposed method are
evaluated in comparison with the state-of-the-art methods.
The contributions of this study are as follows. First,
our alignment method achieves the highest accuracy and its
computational cost is much smaller than previous methods
with comparable accuracies. The method works without
prior voice information and can be applied for a wide classof performance and score data. The source code for ouralgorithms and a user interface to examine and correct theresults is published in the accompanying web page [18]. To
our knowledge, this is currently the only publicly availablealignment tool of comparable accuracies. Second, this is
the first paper that quantitatively investigates the relation
between performance errors and alignment errors, which
can be used generally to reduce high computational costthat is typically required in elaborated methods. Lastly, ouralignment algorithm of the merged-output HMMs yields
better sub-optimisation than a previous one [9].

1.1 Current State-of-the-Art Methods
The method by Gingras and McAdams [5] (GM algorithm), which takes into account the voice structure andtiming information, is regarded as one of the most accurate methods for symbolic music alignment, with 99.978%of accuracy on their data. The method based on the temporal HMM by Nakamura et al. [7] (NOSW algorithm)
also uses the timing information but not the voice structure. The method can handle arbitrary repeats and skips,
but the accuracy was lower than the GM algorithm in a direct comparison. For online alignment, the method using
merged-output HMMs for incorporating the voice structure
had better accuracies than the temporal HMMs [9].
Recently, Chen et al. [6] reported a significant lower accuracy (≤ 91.93%) for the GM algorithm on other data andproposed a method based on DTW (CJL1 algorithm) witha better accuracy (≤ 98.51%) 1 . Another method (CJL2
algorithm) is proposed in the paper, which is less accurate
but more efficient than the CJL1 algorithm. The CJL algorithms neither use voice information nor have a special
architecture to utilise the voice structure.
2. PERFORMANCE ERROR DETECTION
2.1 Problem Statement
Both reference and aligned signals can be represented asa sequence of musical notes (called reference notes andaligned notes) with a pitch and an onset time described asphysical or score time. For MIDI-to-MIDI alignment, thereference signal can be a performed MIDI signal that has(almost) continuous onset times. In this case, we cluster
notes according to onset times to obtain a reference signal with quantised onset times, which enables us to discuss score-to-MIDI and MIDI-to-MIDI alignment in a unified way. Specifically, we put a threshold of 35 ms, which
is known to well discriminate chordal notes [19], to form
clusters of notes and then quantise onset times (e.g. in unitsof ms etc.). An alignment result is a sequence of labels thatindicates for each aligned note the corresponding reference
note. If there is no corresponding note (as is the case forextra notes), a distinguished label ‘EXTRA’ is given.
As performance errors we consider pitch errors, extra
notes, and missing notes. Extra notes are aligned notes thatare not matched to any of the reference notes and missing
notes are reference notes that do not appear in the aligned
signal. In this study we consider the strict alignment, forwhich each reference note can be matched to at most onealigned note 2 . For a strict alignment result, performanceerrors are automatically determined: aligned notes without corresponding reference notes are extra notes; aligned
notes with pitches different from the corresponding reference notes have pitch errors; reference notes not appearing
1 A different evaluation measure was used in Ref. [6] and these upperbounds have been derived as conservative limits.
2 This condition must be relaxed and apply only locally if we allow
global repeats and skips in the aligned signal. In addition, trills and tremolos are exceptions where multiple aligned notes correspond to each reference note. For simplicity and for the lack of space, we concentrate on thecase without ornaments, repeats, and skips in this paper.

Reference cluster

Reference
signal&&Result of preliminaryalignment

AlignedsignalMissing note&

Referencecluster

Alignedcluster

Extra note

LR Viterbi alignment
for notes between
correctly played notes

Pitch error

LR Viterbi alignment
for aligned clusters(a)Extra cluster(b)

Figure 2. Steps for performance error detection. After (a)cluster-wise LR Viterbi alignment is performed, (b) notewise LR Viterbi alignment is performed for each cluster.
in the alignment result are missing notes.
Standard alignment methods such as HMMs and DTWs
often output alignment results that are not strict (so thata reference note can appear more than once) and performance error indications are not given. Therefore, the aimof performance error detection is to obtain a strict alignment result from a non-strict alignment result, which isequivalent to identifying extra notes in the latter one. In
fact, our method uses only the information of matchedscore times for each note in an input alignment result.
2.2 Model
Our approach for the identification of extra notes is to carryout two left-to-right (LR) Viterbi alignments, first in unitsof ‘chords’ and second in units of notes within each ‘chord’(Fig. 2). To be precise, we define a reference cluster as a setof all notes with the same score time in the reference signal. Aligned notes are clustered so that all successive notes
form a cluster (aligned cluster) as long as their referencelabels are in the same onset cluster. The first LR Viterbialignment is then performed on the sequence of aligned
clusters and those clusters assigned a reference cluster different from the original one are identified as extra clusters.
Note that after this procedure each non-extra aligned cluster is matched to a unique reference cluster.
In the next step, extra notes in each (non-extra) aligned
cluster are identified. Based on our intuition that aligned
notes with correct pitches play a pivot role and the assigned reference labels should respect the pitch order, wefirst identify aligned notes with correct pitches and thenmatch other notes, which are either extra notes or notes
with pitch errors. Since in general there are multiple notes
with the same pitch in one aligned cluster, the onset time
information should be used here. As a reference point of
onset time, the expected onset time t̃ of the reference onset
cluster is computed by local averaging, similarly as tempo
estimation [19]. If there are multiple candidates with thecorrect pitch, the one with an onset time nearest to t̃ is chosen and the other candidates are identified as extra notes.
Let (q1 , . . . , qC ) denote an ordered set of notes in theconcerned reference cluster, where qc is the integral pitchof the c-th note and satisfies q1 ≤ q2 ≤ · · · ≤ qC , and let
Qcorr denote the set of reference notes matched to aligned
notes with correct pitches. Similarly, let us order notes in
the concerned aligned cluster according to pitch first andthen onset time. Denoting the pitch and onset time of theb-th note by pb and tb , we thus have for all b ∈ {1, . . . , B}
(B is the number of notes in the aligned cluster) pb−1 ≤ pb
and tb−1 ≤ tb if pb−1 = pb . Now suppose that a pairof pivot notes (c, c0 ) (c, c0 ∈ {1, . . . , C}) satisfies thatqc , qc0 ∈ Qcorr , qc < qc0 , and qj ∈/ Qcorr for each qj
0with c < j < c . For such a pair we define Q = {qj | c <j < c0 } and S = {b ∈ {1, . . . , B} | qc < pb < qc0 }. The
next step is to match Q and S for each pair (c, c0 ) of pivot
notes. For aligned notes with pitches higher or lower thanthe highest or lowest pivot note, we can similarly define Q
and S as half-bounded sets, and for the case with no pivot
notes, we define Q = {1, . . . , C} and S = {1, . . . , B},
and carry out the following procedure.
The matching is trivial when #Q ≤ 1 and #S ≤ 1.
In other cases, multiple interpretations of pitch errors exist and some principle must be introduced to find the optimal choice (Fig. 2(b)). We solve this optimisation problem with a statistical performance model including temporal fluctuations and pitch errors, similar to the model in
Ref. [7]. The mapping z : Q 3 j 7→ zj ∈ S is optimisedby LR Viterbi alignment with the following probability:
P (zj = b | zj−1 = b0 ) = θb0 b ψ pitch (pb − qb )ψ time (tb − t̃)
where θ is a #S×#S LR transition probability matrix,(
1/#{l ∈ S | l > b0 }, b0 < b;
θ b0 b =(1)0,otherwise,and ψ pitch (δp) is the probability of pitch errors in δp semitones (given by Eq. (30) of Ref. [19]), and ψ time (δt) is theprobability of onset time fluctuation given asψ time (δt) = N(δt; 0, ρ2 ).

(2)Here, N( · ; µ, Σ) denotes a normal distribution with mean
µ and variance Σ. The value of ρ is taken as 100 ms in our
implementation. Aligned notes without matched reference
notes are classified as extra notes.
2.3 Error Regions and Alignment Errors
Having identified the performance errors, we now define
error regions in the aligned signal around them. To do this,
we first calculate the synchronised onset time for each reference cluster by averaging onset times of correspondingaligned notes, or if there are no such notes, by interpolating/extrapolating neighbouring synchronised onset times.
We consider, for each extra note n with onset time tn , atime interval of the form [tn − ∆, tn + ∆) with width ∆(called an extra note region) and construct the set Re ofsuch time intervals for all extra notes. Likewise, the set ofpitch error regions Rp is constructed. The set of missingnote regions Rm is similarly constructed by using the synchronised onset times to define each time region. Finally,
the error region R is constructed by combining elements
in Re , Rp , and Rm . If there are overlapping time regions,they are expanded/unified to one time region at this stepR
(Fig. 3). Thus, R is a set {[tr , t0r )}N
r=1 of non-overlapping

100

Missing note2∆

Extra note2∆

Pitch error

2∆Error regions(nm , ne , np ) :(1,1,1)

Alignment errors
Correctable errors
Aligned notes

80(0,1,1)(1,1,0)Figure 3. Examples of error regions and their indices.

Proportion (%)

Physical time in
the aligned signal

60

40

20

0

0

0.5

1

1.5

2

2.5

3

time regions where we have t0r−1 < tr for all r. The num-

Width ∆ [sec]ber of missing notes, extra notes, and pitch errors in eachregion r is denoted by nm (r), ne (r), and np (r).
Let us discuss the relation between performance errors
and alignment errors. An alignment error is defined as areference label in an alignment result that is different fromthe ground-truth label. We say that an alignment error iscontained in the error regions if the onset time of the incorrectly aligned note is contained in one of the regions in
R. The proportion of alignment errors contained in the error regions for varying time width ∆, calculated for alignment results of the temporal HMM on the three datasets
explained in Sec. 4, is shown in Fig. 4, together with theproportion of aligned notes contained in the error regions.
More than 90% of the performance errors are contained in
the error regions for ∆ as small as 0.1 s, while containedaligned notes remain less than 20% for ∆ ≤ 0.3 s.
For the alignment errors to be corrected by realignment carried out on each error region, not only incorrectly aligned notes but also their corresponding reference
notes must be contained in the region. To be precise, foreach time region [tr , t0r ) in R, we choose segments of thealigned and reference signals and use them as the aligned
and reference signals for realignment. For the segment of
the aligned signal, the subsequence of aligned notes whose
onset times belong to the time region is used. For thesealigned notes, we obtain the maximal and minimal score
times (τmax and τmin ) of corresponding reference notes.
The subsequence of all reference notes whose onset score
times are in the range [τmin , τmax ] is used as the segment of
the reference signal. We call an alignment error in an error
region correctable if its ground-truth label is ‘EXTRA’ oris a reference note in the reference signal segment. We seein Fig. 4 that the proportion of correctable errors increases
rapidly for ∆ < 0.3 s and gradually for ∆ > 0.3 s.
Although it is not always the case, naively we expectthat the number of performance errors is reduced whenalignment results are corrected, as is evident in the case ofcorrecting a mismatched pair of missing and extra notes.
On the other hand, if only one performance error exists or
only missing notes exist in an error region, the number of
performance errors cannot be reduced by realigning notes.
By expanding this idea, we can impose conditions on error regions so that most of the alignment errors remaincontained in the selected error regions but the containedalignment notes are reduced significantly. Results in Table 1, where error regions were imposed the condition ofcontaining at least two types of performance errors, show
an example of this fact. Such conditions can be used toincrease the efficiency of realignment, as we see in Sec. 4.

Figure 4. Proportion of alignment errors and aligned notes
contained in the error regions.
Alignment Correctableg Aligned
errorserrorsnotes

Conditions

None
98.7%
nm ne +ne np +np nm > 0 88.5%

87.5%
80.3%

18.5%
9.2%

Table 1. Same as Fig. 4 with and without imposed conditions on the error regions (∆ = 0.3 s).
3. REALIGNMENT
Here we develop a realignment method based on mergedoutput HMMs, which is applied to the error regions to correct the preliminary alignment result. The overall procedure of realignment is illustrated in Fig. 5. We first apply
hand separation for the reference signal segment to estimate the voice structure and then carry out alignment basedon the merged-output HMM using the estimated voices.
3.1 Hand Separation
To formulate a method that does not require prior voice
information, we apply voice separation to each reference
signal segment. Because voice asynchrony in piano performances usually appears between the left- and right-handparts and a larger number of voices increases the computational cost for realignment, we use a technique that separates a performance signal into two hand parts [17].
Voice information is described with a binary variable
sm for each note m in the reference signal segment. If
sm = L (or R), the m-th note is in the left-hand (or righthand) part. Let us denote the pitches of the reference signal segment by x = x1:M = (x1 , . . . , xM ), where thenotes are ordered according to the onset score time. (Similar notations appear throughout the paper.) To estimate
the sequence s = s1:M from the input x, we construct amerged-output HMM. The Markov model for each voice is
described with transition probabilities on pitches, denotedRby χL
yy 0 and χyy 0 . Introducing pitch variables for the twoLRvoices, ym and ym
for each m, the latent state variable forLR
the merged-output HMM is given as Ym = (sm , ym
, ym)
and the transition and output probabilities are given as
P (Ym = Y | Ym−1 = Y 0 )R= 21 (δsL χL
y 0L y L δy 0R y R + δsR χy 0R y R δy 0L y L ),P (xm | Ym = Y ) = δsL δyL xm + δsR δyR xm ,

(3)
(4)

where δyy0 denotes Kronecker’s delta. To complete theMissing note
Reference
Error region
signal&?#&?

Alignedsignal

#

#

#

‹

#
#

‹

(1) Hand separation&?#
Left hand##‹

Right hand

(2) Alignment by themerged-output HMM

&
?#
&
?

#

#

#

‹

#
#

‹

Extra note

Figure 5. The realignment step consists of hand separation
and alignment by the merged-output HMM.
stochastic process, we should specify the initial probability, which is given similarly as in Eq. (3) with initial pitch
values denoted by y0L and y0R . We use as y0L and y0R thelowest and highest pitch in the reference signal segment.
We can estimate s with the maximal posterior probability
using an efficient Viterbi algorithm [17].
3.2 Realignment Based on Merged-Output HMM
For realignment we use the merged-output HMM proposed
previously [9]. Modifications to the model are introduced
to reduce computational cost and an inference algorithm
that is more rigorous than the original one is derived.
Let us first briefly review the temporal HMM [7] formusic alignment. The aligned signal (segment) can be canbe described as a sequence (p, t), where p = (p1 , . . . , pN )denotes the integral pitches and t = (t1 , . . . , tN ) denotes
the onset times (N is the number of aligned notes). The
reference signal (segment) is represented as a sequenceof reference clusters indexed by i ∈ {1, . . . , I} (I is thenumber of reference clusters), and the corresponding onset
score time is denoted by τi . Local tempos are denoted by
v = (v1 , . . . , vN ). The corresponding reference cluster ofthe n-th aligned note is denoted by in ∈ {1, . . . , I}. The
latent state of the temporal HMM is indexed by (in , vn )for each n ∈ {1, . . . , N } and the output symbol is the pair(pn , tn ). Transition and output probabilities are given as
P (in , vn | in−1 , vn−1 ) = π(in−1 , in )N(vn ; vn−1 , σv2 ),P (pn |in ) = φ(in , pn ),(5)

P (tn | tn−1 , in−1 = i0 , in = i, vn )= (1 − δii0 )N(tn ; tn−1 + vn (τi − τi0 ); σt2 )+ δii0 Exp(tn − tn−1 ; λ),(6)where we have assumed the statistical independence for thepairs in and vn , and pn and tn . The probability π stochastically describes how the performance proceeds in the reference signal. The standard deviation σv represents theamount of tempo variation during the performance. The
pitch output probability φ stochastically describes pitch
errors (similarly as ψ pitch in Sec. 2.2); it depends on thepitch context of reference cluster i. The form of the output
probability for onset times reflects the fact that inter-onset
intervals between chordal notes obey an exponential distribution (denoted by Exp) and those between onset clusters
are approximately given as the product of the local tempo
and the score time interval [7]. The scale parameter λ andthe standard deviations σt and σv have been measured [7].

We can now construct the merged-output HMM for music alignment using voice information, by describing eachvoice by the temporal HMM and merging outputs from thetwo HMMs [9]. To reduce computational cost, we introduce two simplifications to the model. First, since the error
region is considered to span a small time range (less than afew seconds), the variation of tempos should be relatively
small. We therefore assume a constant tempo v in eacherror region, which can be obtained from the preliminaryalignment result. This removes the dynamics of tempos
and reduces the state space of the temporal HMM to thatindexed only by in . Second, again because of the localityof error regions, we can assume LR transition probabilitiesfor π. This reduces the number of possible state transition
paths and thus reduces the computational cost. With these
simplifications, the state space of the merged-output HMM
is indexed by k = (s, iL , iR , tL , tR ) (s ∈ {L, R}) and thetransition and output probabilities are
P (kn = k | kn−1 = k 0 )= 12 As (is , ts | i0s , t0s , v)· δsL δi0R iR δ(t0R − tR ) + δsR δi0L iL δ(t0L − tL ) ,As (is , ts | i0s , t0s ; v) = π(i0s , is )P (t0s | ts , i0s , is , v), (7)P (pn | kn = k) = φ(is , pn ),

(8)

s

(9)

P (tn | kn = k) = δ(tn − t ),where δ( · ) is the Dirac delta function. Notating k = k1:N ,the complete-data probability is given as
P (k, p, t) =NY

P (kn |kn−1 )P (pn |kn )P (tn |kn ). (10)n=1

The alignment result is obtained by inferring k thatmaximises P (k, p, t). The direct application of the Viterbi
algorithm is impossible since the temporal HMM is of
autoregressive type, i.e. the output probability of onset
times depends on past values. Instead of the rough suboptimisation method used in Ref. [9], we use a trick of introducing an auxiliary variable that encodes the historicalpath, as in Ref. [20], which enables almost exact optimisation. Introduce hn = 1, 2, · · · , which is defined as thesmallest h ≥ 1 satisfying sn 6= sn−h for each n. We have((hn−1 +1, sn = sn−1 ; stn ,s = sn ;
hn =
tn =
1,
sn 6= sn−1 ,tn−hn , s 6= sn .
With a change of variables (h = h1:N , iL = iL
1:N , etc.),
P (k, p, t) = P (s, h, iL , iR , p, t)
Y 

1
=
2 δsn L δi0R iR + δsn R δi0L iLn·hδsn sn−1 δhn (hn−1 +1) Asame+ (1 − δsn sn−1 )δhn 1 Adiff
n
n

i

n
Asame
= Asn (isnn , tn | isn−1, tn−1 ; v),
n

sn
sn
Adiff
n = Asn (in , tn | in−1 , tñ ; v)

(11)

where ñ = n − hn−1 − 1. It is now possible to derive theViterbi algorithm for the state space of (s, h, iL , iR ). A,Algorithm
GM data
CJL data
Our data
Proposed 0.18 ± 0.08 0.79 ± 0.06 0.48 ± 0.03
NOSW+
1.46 ± 0.23
1.81 ± 0.08 0.64 ± 0.04
NOSW [7] 1.78 ± 0.25
2.33 ± 0.10 2.24 ± 0.07
GM [5]
0.28 ± 0.10 [7] 8.07† ± 0.18 [6]N/A
CJL1 [6]N/A
1.49† ± 0.08 [6]N/A
CJL2 [6]N/A
2.20† ± 0.09 [6]N/A
Table 2. Alignment error rates (%) with 1σ statistical errors. The best values within 1σ significance are displayedin bold font. Daggers indicate lower bounds (see Sec. 1.1).
cutoff (∼ 50) on the maximum value of hn can be put toreduce the search space with little loss of optimality [20].
Finally, the performance error detection described in Sec. 2
is performed separately on each voice (hand part).
During testing the method, we noticed that alignment
errors as simple as a pair of missing and extra notes as inFig. 1 sometimes remain after applying the described realignment step. This is often because the result of handseparation is not completely correct. To handle this, we
carried out a simple processing step (called pairing step)of matching trivially corresponding missing and extra notepairs. For each missing note, an extra note with the same
pitch is searched within the time region of half width ∆,and if found, they are matched. The pairing step can also
be applied before the realignment step to correct trivialalignment errors and thus reduce the cost of realignment.
4. EVALUATIONAs explained in Sec. 1.1, the state-of-the-art methods are
the NOSW algorithm [7], the GM algorithm [5], and the
CJL algorithms (CJL1 and CJL2) [6]. For comparison, we
run the performance error detection on the results of the
NOSW algorithm (NOSW+ algorithm), and the proposed
realignment was applied to its results. Since the GM andCJL algorithms were not available from their authors but
the used data were provided, we run the proposed method
and temporal HMM on their data and directly compared
the accuracies. The GM data consisted of seven performances of two excerpts of Chopin’s piano pieces (total of
2,815 aligned notes). The CJL data consisted of 21 pairsof piano MIDI files (total of 25,656 aligned notes), mostof which are synthetic (not human-played) performances.
We also tested the proposed method on the human-played
performance data that we prepared. Our data consisted of
60 excerpts of classical piano pieces each played by threedifferent pianists (total of 43,608 aligned notes) 3 . For the
GM data and our data it was score-to-MIDI alignment andfor the CJL data it was MIDI-to-MIDI alignment. For the
proposed method, ∆ = 0.3 s was used, error regions satisfying the condition (nm ne + ne np + np nm > 0) wereselected for realignment, and the pairing step was applied
before and after the realignment step.
The rates of alignment errors in Table 2 show that for
all data the realignment method significantly improved thepreliminary alignment results: in total 47% (= 369 aligned
3 The data could be provided upon requests to the authors.

GM data CJL data Our data Time (s)
(a)
0.18
0.79
0.48 5.54 ± 0.07(b) 0.25
1.17
0.51 6.31 ± 0.07
(c)
0.14
0.85
0.61 6.32 ± 0.05
Table 3. Alignment error rates (%) and processing time(averaged over five trials) for the proposed method with (a)both paring steps and conditions on error regions, (b) only
conditions on error regions, and (c) only pairing steps.
notes) of alignment errors made by the NOSW+ algorithm
were reduced. The proposed method had the highest accuracies for all datasets. To evaluate computational efficiency, the processing time was measured. Our algorithms were implemented in C++ on a computer with 3.1
GHz CPU and 16 GB memory running Mac OS X 10.11.
The measured time for the CJL data was 8.25 s for the
NOSW algorithm, 17.76 s for the performance error detection, and 1.12 s for the realignment. Compared to thereported values [6], 342.70 s and 3535.36 s for the CJL1and GM algorithm, the computational efficiency of the proposed method is evident, although direct comparison is notpossible because of different computer environments. Examples demonstrating the effect of the realignment method
are shown in the accompanying web page [18].
To examine the effect of the paring step and the conditions imposed on error regions, the proposed method without these modifications was compared in terms of accuracies and processing time for all data (Table 3). In addition
to the expected reduction of computation time, these modifications were also effective in reducing overall alignment
errors. This suggests that the realignment by the mergedoutput HMM increases alignment errors in some error regions and these modifications have effects in avoiding this.
Detailed analyses are currently being undertaken.
5. CONCLUSION
We have described a realignment method for symbolic music signals based on merged-output HMMs, which can deal
with reordered notes due to voice asynchrony. To reduce
the high computational cost, performance errors are detected and the merged-output HMMs are applied to regions
around the performance errors rather than to the whole
signal. In all tested data and for both score-to-MIDI and
MIDI-to-MIDI alignment cases, the proposed realignment
method combined with an HMM-based method achieved
the highest accuracies, with short computation time.
The principle of using performance errors to select regions in the aligned signals that possibly contain alignment
errors is generally applicable to save computation time.
For example, when a further refined alignment method isfound in the future, we can apply it to the error regionsof the results by the proposed method, instead of doingalignment from scratch. In addition, since the realignment
can be done locally, it can be applied to performance signals with global repeats and skips [7]. For future work,
refinements for the model for performance error detection
by examining human-annotated data would be possible tofurther improve the accuracy and efficiency.

6. ACKNOWLEDGEMENTS
We are grateful to Bruno Gingras and Chun-Ta Chen forproviding evaluation data. E. Nakamura is supported by
the JSPS Postdoctoral Research Fellowship. This work
is in part supported by JSPS KAKENHI Nos. 24220006,
26280089, 26700020, 15K16054, 16H01744, 16H02917,
16K00501, and 16J05486 and JST ACCEL No. JPMJAC1602.
7. REFERENCES[1] R. Dannenberg, “An On-Line Algorithm for Real-Time
Accompaniment,” Proc. ICMC, pp. 193–198, 1984.
[2] J. Bloch and R. Dannenberg, “Real-Time Computer
Accompaniment of Keyboard Performances,” Proc.
ICMC, pp. 279–290, 1985.
[3] P. Desain, H. Honing, and H. Heijink, “Robust ScorePerformance Matching: Taking Advantage of Structural Information,” Proc. ICMC, pp. 337–340, 1997.
[4] H. Heijink, L. Windsor, and P. Desain, “Data Processing in Music Performance Research: Using Structural
Information to Improve Score-Performance Matching,” Behavior Research Methods, Instruments, &Computers, vol. 32, no. 4, pp. 546–554, 2000.
[5] B. Gingras and S. McAdams, “Improved ScorePerformance Matching Using Both Structural andTemporal Information from MIDI Recordings,” J. New
Music Res., vol. 40, no. 1, pp. 43–57, 2011.
[6] C. Chen, J. R. Jang, and W. Liou, “Improved ScorePerformance Alignment Algorithms on PolyphonicMusic,” Proc. ICASSP, pp. 1365–1369, 2014.
[7] E. Nakamura, N. Ono, S. Sagayama, and K. Watanabe,“A Stochastic Temporal Model of Polyphonic MIDI
Performance with Ornaments,” J. New Music Res.,
vol. 44, no. 4, pp. 287–304, 2015.
[8] B. Pardo and W. Birmingham, “Modeling Form for Online Following of Musical Performances,” Proc. NCAI,
2005.
[9] E. Nakamura, Y. Saito, N. Ono, and S. Sagayama,“Merged-Output Hidden Markov Model for Score Following of MIDI Performance with Ornaments, Desynchronized Voices, Repeats and Skips,” Proc. JointICMC|SMC 2014, pp. 1185–1192, 2014.
[10] C. Raphael, “Automatic Segmentation of Acoustic Musical Signals Using Hidden Markov Models,” IEEE
TPAMI, vol. 21, no. 4, pp. 360–370, 1999.
[11] A. Cont, “A Coupled Duration-Focused Architecture for Realtime Music to Score Alignment,” IEEE
TPAMI, vol. 2, no. 6, pp. 974–987, 2010.
[12] C. Fremerey, M. Müller, and M. Clausen, “Handling
Repeats and Jumps in Score-Performance Synchronization,” Proc. ISMIR, pp. 243–248, 2010.
[13] C. Joder, S. Essid, and G. Richard, “A Conditional
Random Field Framework for Robust and Scalable
Audio-to-Score Matching, IEEE TASLP, vol. 19, no. 8,
pp. 2385–2397, 2011.

[14] M. Grachten, M. Gasser, A. Arzt, and G. Widmer, “Automatic Alignment of Music Performances with Structural Differences,” Proc. ISMIR, pp. 607–612, 2013.
[15] A. Maezawa, K. Itoyama, K. Yoshii, and H. G. Okuno,“Bayesian Audio Alignment Based on a Unified Modelof Music Composition and Performance,” Proc. ISMIR, pp. 233–238, 2014.
[16] W. Siying, S. Ewert, and S. Dixon, “Robust and Efficient Joint Alignment of Multiple Musical Performances,” IEEE/ACM TASLP, vol. 24, no. 11, pp. 2132–
2145, 2016.
[17] E. Nakamura, N. Ono, and S. Sagayama, “MergedOutput HMM for Piano Fingering of Both Hands,”
Proc. ISMIR, pp. 531–536, 2014.
[18] E. Nakamura, K. Yoshii, and H. Katayose,
SymbolicMusic
Alignment
Tool,
2017.
http://anonym9382.github.io/demo.html[Online][19] E. Nakamura, T. Nakamura, Y. Saito, N. Ono, and
S. Sagayama, “Outer-Product Hidden Markov Model
and Polyphonic MIDI Score Following,” J. New Music
Res., vol. 43, no. 2, pp. 183–201, 2014.
[20] E. Nakamura, K. Yoshii, and S. Sagayama, “Rhythm
Transcription of Polyphonic Piano Music Basedon Merged-Output HMM for Multiple Voices,”
IEEE/ACM TASLP, vol. 25, no. 4, pp. 794–806, 2017.