ASARM-ReportB.lyx

#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{colortbl}
\usepackage{tikz}
\usepackage{pst-gantt}
\usepackage{pspicture}
\usepackage{pstricks}
\usepackage{pst-bezier}
% gantt charts

% enable listing highlighting
\lstset{
  keywordstyle=\color[rgb]{0,0,1},
  commentstyle=\color[rgb]{0.133,0.545,0.133},
  stringstyle=\color[rgb]{0.627,0.126,0.941},
}

% c#
\lstdefinelanguage{Pseudo}
{
 morecomment = [l]{//}, 
 morecomment = [l]{///},
 morecomment = [s]{/*}{*/},
 morestring=[b]", 
 sensitive = true,
 morekeywords = {abstract,  event,  new,  struct,
   as,  explicit,  null,  switch,
   base,  extern,  object,  this,
   bool,  false,  operator,  throw,
   break,  finally,  out,  true,
   byte,  fixed,  override,  try,
   case,  float,  params,  typeof,
   catch,  for,  private,  uint,
   char,  foreach,  protected,  ulong,
   checked,  goto,  public,  unchecked,
   class,  if,  readonly,  unsafe,
   const,  implicit,  ref,  ushort,
   continue,  in,  return,  using,
   decimal,  int,  sbyte,  virtual,
   default,  interface,  sealed,  volatile,
   delegate,  internal,  short,  void,
   do,  is,  sizeof,  while,
   double,  lock,  stackalloc,   
   else,  long,  static,   
   enum,  namespace,  string, end}
}

% empty float page style
\usepackage{nonfloat}
\end_preamble
\use_default_options true
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\paperfontsize 12
\spacing other 1.5
\use_hyperref false
\papersize a4paper
\use_geometry true
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\leftmargin 2cm
\rightmargin 2cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Standard
\align center

\series bold
THE UNIVERSITY OF NEW SOUTH WALES
\end_layout

\begin_layout Standard

\end_layout

\begin_layout Standard
\align center

\series bold
SCHOOL OF COMPUTER SCIENCE AND ENGINEERING
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset


\end_layout

\begin_layout Standard
\paragraph_spacing onehalf
\align center
\begin_inset Graphics
	filename images/UNSW_bw.png

\end_inset


\end_layout

\begin_layout Standard
\align center

\size larger
AUTOMATIC SCORE ALIGNMENT OF RECORDED MUSIC
\end_layout

\begin_layout Standard
\paragraph_spacing single
\align center

\size large
Georgy Roldugin (3220542)
\end_layout

\begin_layout Standard
\paragraph_spacing double
\align center

\size large
Supervisor: Dr.
 Julien Epps
\begin_inset Newline newline
\end_inset

Assessor: Dr.
 Daniel Woo
\end_layout

\begin_layout Standard
\paragraph_spacing onehalf
\align center

\size large
Bachelor of Software Engineering (Honours)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\backslash
today
\backslash
end{center}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{empty}
\end_layout

\begin_layout Plain Layout


\backslash
setcounter{page}{1}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Abstract
The process of score-to-audio alignment matches the events in the score
 to the time when they occur in the audio recording.
 The results of the alignment can thus be used to time scale modify a musical
 piece or alternatively assign exact tempo at every position of the score,
 so that both are in sync with each other.
 The method presented in this work uses a dynamic time warping technique
 with subsequent least squares line fitting to eliminate minor alignment
 errors and achieve a naturally sounding audio output.
 The method has been designed with music notation software tools in mind.
 As such it has performance optimisation as one of its goals.
 It is robust to errors in the score such as incorrectly transcribed notes
 or song structure elements.
 It does not make assumptions about the instruments present in either the
 audio recording or the score but is targeted towards pop/rock music.
 As opposed to methods that attempt to achieve a ground-truth alignment
 for indexing and machine training purposes, new ways have been explored
 to prioritise the perceptional quality of the alignment.
 A variety of methods at every stage of the alignment process are compared
 and discussed with reference to the problem at hand.
 In particular the chroma vectors will be presented as an alternative to
 pure spectral features.
 The tests have shown them to be more stable than spectral features during
 rough alignments, but not quite on the fine grained scale.
 The obtained performance and quality evaluation results show the validity
 of the approach and form the basis for a discussion of possible improvements.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{plain}
\end_layout

\end_inset


\end_layout

\begin_layout Section
Introduction
\end_layout

\begin_layout Standard
Score is a form of musical notation.
 It is most commonly known as sheet music but can also be presented in a
 digital equivalent.
 It is a symbolic representation of music.
 Each note to be played by the musician is described in terms of its pitch
 and playing characteristics.
 The relative position in time and length of each note are also recorded.
 Relative timing is specified by the tempo, i.e.
 the speed at which the musical piece should be played.
 The tempo may vary from one part to another but it is usually steady across
 one or more sections of the piece.
\end_layout

\begin_layout Standard
While tempo may be specified as a constant for a longer part of the piece
 it is often idealistic.
 It hardly ever reflects the reality of a human playing.
 And it is most certainly not the case with live performances or recordings
 made without a reference track.
 In fact, software synthesisers that attempt to mimic human playing often
 tend to loosen timing and velocity of individual notes to convey realism.
\end_layout

\begin_layout Standard
There are, however, many applications in which the opposite process is required.
 That is, having a music recording and the corresponding score, obtain the
 best match between the two (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:AlignmentGoal"

\end_inset

):
\end_layout

\begin_layout Enumerate
In film and music industries, session musicians are often given the score
 to the music they are to record.
 Once recorded the results of an alignment may be used to guide or aid the
 process of error correction with little or no intervention required.
\end_layout

\begin_layout Enumerate
In musicology the score with automatically marked tempo may be invaluable
 for performance analysis and evaluation.
 An example would be the comparison of the interpretation of the same musical
 score by two or more musicians.
\end_layout

\begin_layout Enumerate
In computer science indexing or segmentation of continuous media can be
 used for creating a database for subsequent model training and content-based
 retrieval.
 The former exploits the machine learning techniques to improve music transcript
ion or speech recognition.
 The latter attempts at finding the database entries that best mach the
 musical or symbolic data supplied.
\end_layout

\begin_layout Enumerate
Professional and amateur musicians may benefit from the new capabilities
 while working with their scores in music notation software.
 The score can be auditioned by playing back a prerecorded track synchronised
 appropriately.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename images/AlignmentGoal.png
	width 100text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:AlignmentGoal"

\end_inset

Goal of score alignment.
 The upper graph is a valid transcription of the original audio in the lower
 graph, misaligned in time and possibly in tempo.
 The selected notes at about 24s in the score occur at about 26s in the
 audio.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The work presented here attempts to solve the last problem on the list.
 While the methods are similar to the first three examples, the goals have
 subtle differences.
 It is probably beneficial for the first three tasks that the alignment
 is ground-truth, possibly with some automatic error detection functionality.
 This way if the alignment is erroneous the user is notified that, say,
 a manual intervention is required.
 The present application on the other hand, is targeted towards a non-technical
 user.
 It may seem logical to responsibly cover up the errors in the alignment
 to improve the perceptional alignment quality.
 Such problems include both the errors resulting from alignment, as well
 as the mistakes in transcription or performance:
\end_layout

\begin_layout Enumerate
The score may introduce repeated or be missing sections, usually due to
 incorrectly transcribed song structure.
 The algorithm used at heart of the method discussed here is implicitly
 resistant to such errors.
 However, it turned out that it did not perform reliably on the boundaries
 of the section in question and these have to be accounted for separately.
\end_layout

\begin_layout Enumerate
The alignment process may be confused by the the musical content and produce
 incorrect results in the short periods of time, usually in the breaks between
 two sections, like verse and chorus.
 This may be caused, for example, by the drummer going hard on drums or
 expressive vocals not being reflected by any instrument in the score.
\end_layout

\begin_layout Enumerate
While this is not an error, but rather something to be wished for in other
 applications, a high alignment resolution causes the tempo to always change
 from one note to another.
 Should the audio recording be time scaled to reflect every small change
 in tempo, it will loose its human touch and will be unpleasant to listen
 to.
 Added to that is a noticeable loss in quality introduced by changing the
 playing rate so often.
\end_layout

\begin_layout Standard
One of the main research goals has been to account for the above problems.
 Obviously, it introduces certain constrains on the types of music that
 can be processed.
 But perhaps only music in highly experimental styles will be misinterpreted
 by the improved algorithm.
 Usually when there is a sudden change in tempo, it is kept constant across
 longer periods of time before the next change.
\end_layout

\begin_layout Standard
Another important aspect of the problem is its computational complexity.
 The algorithms widely used to solve alignment problems require long running
 time.
 To give an idea, an unoptimised solution takes over a minute to align a
 4 minute song with its score to a 32nd note accuracy in tempo 120 bpm.
 This is unacceptable for a casual user and can be reduced considerably.
 Several optimisation solutions have been studied and a proposal made.
\end_layout

\begin_layout Standard
To reason about the design choices made, the discussion will follow with
 reference to a notation editing software TuxGuitar (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:TuxGuitar"

\end_inset

).
 The program is targeted at guitar players but can be used by all musicians
 for the purposes of editing and viewing scores.
 It currently allows playing back the score through several software synthesiser
s approximating the sound of real instruments.
 It supports third-party extensions so a plugin can be built to include
 the functionality described here.
 The extension would allow importing an audio file into the software.
 Subsequent use of the transport control buttons (play, next bar, loop,
 etc.) will result in the imported audio file being played from the appropriate
 position.
 This would allow musicians to play along to the original studio recordings
 or backing tracks freely available on the Internet, while at the same time
 visualising the scores to be played.
 The current progress of the extension development will be discussed in
 its own section of this document.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/TG.png
	lyxscale 85
	height 8cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:TuxGuitar"

\end_inset

Main window of TuxGuitar, a guitar tablature and score editor.
 Plays back the scores through a software synthesiser, graphically following
 the position in the song.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
The following section will cover the theory and the main alternatives proposed
 by researchers in the field.
 The technical details of the proposed system will then be disclosed.
 The report will be concluded with the evaluation results and a discussion
 of possible improvements.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
Background
\end_layout

\begin_layout Standard
The core of system to be developed can be divided into three main subsystems:
 Feature Extraction, Alignment and Error Correction (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:PrelimBlockDia"

\end_inset

).
 The inputs to the system are an audio and a score (also in form of audio,
 synthesised from MIDI, to be introduced).
 Two outputs are expected:
\end_layout

\begin_layout Enumerate
The original audio, time scaled to sound in sync with the score.
\end_layout

\begin_layout Enumerate
The alignment map, i.e.
 a plain text file containing mappings from sample indices in the original
 audio to the their new positions when time scaled.
\end_layout

\begin_layout Standard
This section discusses the main approaches in the field of score-to-audio
 alignment and their relevance to the problem at hand.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/PrelimBlockDia.png
	width 100text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:PrelimBlockDia"

\end_inset

Preliminary overview of the system.
 Includes Feature Extraction, Alignment and Error Correction subsystems.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Subsection
Feature Extraction
\end_layout

\begin_layout Standard
Score and audio fundamentally differ in the ways they are represented in
 data and content they carry.
 Musical Instrument Digital Interface, or MIDI for short, is an implementation
 of the score paradigm.
 It is a protocol for communication between electronic musical instruments,
 devices and computers.
 It defines a notion of events which, along with other control structures,
 can represent the notes and their characteristics.
 The latter include instrument, pitch, duration, velocity and basic playing
 techniques.
 The methods described in this document are applicable to any digital score
 representation that gives access to pitch and timing information of individual
 notes.
 However, since the target system uses a representation similar to MIDI,
 the terms will be used interchangeably.
\end_layout

\begin_layout Standard
While score is a purely symbolic representation of music, a valid audio
 signal is continuous by nature and carries enough information to reproduce
 the music as intended.
 It is a digital signal represented as a bitstream of amplitude quantities,
 called samples (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Waveform"

\end_inset

).
 The samples are captured at equal intervals 
\begin_inset Formula $F_{s}$
\end_inset

 times a second, where 
\begin_inset Formula $F_{s}$
\end_inset

 is called the sampling frequency.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/WaveformZoomed.png
	height 5cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Waveform"

\end_inset

Waveform of stereo digital audio signal.
 The frame contains a zoomed in fragment, where individual samples are distingui
shable (blue dots).
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Due to the differences described above, Audio and MIDI cannot be compared
 directly.
 A common representation of inputs is needed.
 Two main options have been explored by researchers: alignment in symbolic
 domain and alignment based on audio features.
 Both are discussed below.
\end_layout

\begin_layout Subsubsection
Symbolic Domain
\end_layout

\begin_layout Standard
Digital music analysis in symbolic form has been used long before the computers
 became powerful enough to manipulate digital audio.
 Such an alignment implies transcribing the given audio into MIDI and performing
 alignment between two MIDI representations on the same musical piece.
 The approach has its advantages:
\end_layout

\begin_layout Enumerate
Partial but reliable transcription will suffice.
 This means that once the main melody notes, chord changes and drum track
 are transcribed, the alignment will most probably succeed.
 The transcription algorithm does not need to pick up every little detail
 to obtain a high quality alignment.
 In fact, a few researches have shown that it is enough to guess the note
 onsets and the pitches of notes (
\begin_inset CommandInset citation
LatexCommand cite
key "Piano"

\end_inset

,
\begin_inset CommandInset citation
LatexCommand cite
key "AttackSustain"

\end_inset

).
\end_layout

\begin_layout Enumerate
A ground-truth transcription will guarantee a ground-truth alignment.
 If onsets of the notes are guessed correctly the match would be exact around
 these notes.
 However, it may be problematic to detect the exact time when the note started.
\end_layout

\begin_layout Standard
Among the disadvantages of the approach is the general difficulty of the
 of polyphonic transcription.
 It is a research area on its own.
 While there has been some success in the field, it is generally considered
 an unsolved problem.
 The methods that exist normally introduce constraints on the input audio.
 So the alignment is highly dependant on what the transcriber can and can't
 detect (e.g.
 support for polyphony, drums, multiple instruments with a similar timbre,
 etc..)
\end_layout

\begin_layout Standard
Some interesting works using this approach include 
\begin_inset CommandInset citation
LatexCommand cite
key "Piano"

\end_inset

.
 Their system was claimed to be able to align piano music of arbitrary complexit
y and genre.
 They made use of the fact that the characteristics of piano sound are well
 known.
 This made it possible to detect note onsets for each of the 88 piano keys
 with a high degree of reliability.
 They did not provide any numeric evaluation of their results except time
 and memory measurements.
 However, the results of several alignment experiments have been made available
 online.
 The system performed accurate alignment of examples that included complex
 jazz and classical music.
\end_layout

\begin_layout Standard
The restrictions imposed on the music that can be aligned were too narrow
 to choose this method.
\end_layout

\begin_layout Subsubsection
Audio Domain
\end_layout

\begin_layout Standard
As an alternative to a complicated and generally restrictive method of aligning
 in symbolic domain, a diametrically opposite technique was researched and
 successfully employed.
 Audio is generated from the given score and the alignment is performed
 between the original and the synthesised audio.
 This method is fairly permissive as it allows some instruments to be missing
 from either the audio or the score.
 Similarly, vocal tracks may be substituted by an instrument track in MIDI,
 or often omitted all together.
 It works well on more genres without further optimisations, thus increasing
 the probability of a successful alignment.
\end_layout

\begin_layout Standard
In many cases audio transcription is purely programmatic task not requiring
 any training data.
 Audio synthesis, on the contrary, may require prerecorded data to be distribute
d with the application.
 This introduces overhead to the distribution size (1-20 Mb).
 This may be negligible in other software packages, but TuxGuitar, the target
 system, is available as a Java WebStart Application.
 The executable may be downloaded and started in a convenient way from any
 Internet enabled computer.
 Therefore the footprint of the system should be monitored to insure this
 compatibility.
\end_layout

\begin_layout Standard
In regards to the distribution size constraint 
\begin_inset CommandInset citation
LatexCommand cite
key "Chroma+Compare3"

\end_inset

 has been helpful.
 They have looked at three possible ways to generate audio from MIDI that
 work with different degrees of accuracy:
\end_layout

\begin_layout Enumerate
A full-polyphony audio is likely to be similar to the original audio.
 It is obtained by substituting the MIDI note events with prerecorded instrument
 samples.
 The smallest of such libraries are typically 10-20 Mb in size.
\end_layout

\begin_layout Enumerate
Using piano or another instrument samples for every instrument in the MIDI
 has shown to have little impact on the quality of the alignment.
 This is due to the fact that the emphasis here is on the pitches and chords
 rather than timbres of individual instruments.
 It adds little overhead to the distribution size (less than 1 Mb).
 Percussive instruments cannot be substituted by a pitched instrument, of
 course.
\end_layout

\begin_layout Enumerate
When chroma representation is used (to be discussed later) the previous
 approach can be taken further.
 Simplistic data is generated directly from MIDI to reflect the pitch informatio
n only.
 This is very efficient and requires no sample libraries to be supplied.
 It was said to have had little impact the results, even though it ignores
 many information that would otherwise be present in the synthesized audio.
\end_layout

\begin_layout Subsubsection
Spectral Features
\end_layout

\begin_layout Standard
It is clear that alignment in audio domain is more suitable given the requiremen
ts to design a full-polyphony alignment tool.
 However, it is not that easy to define a good metric for similarity even
 between two audio files.
 In Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:CvsFm7"

\end_inset

 waveforms of chords C and Fm7 taken on a guitar are shown in the top row.
 One can see changes in amplitude over time.
 I.e.
 there is a fast attack with an immediate transient, after which the signal
 starts rapidly decaying.
 However, there is not any pitch information that would distinguish the
 two chords.
 It would be very hard if not impossible to align two complex pieces in
 this representation.
\end_layout

\begin_layout Standard
On the other hand the required information may be retrieved when working
 in frequency domain.
 The spectrograms of the same C and Fm7 chords are shown on the bottom row.
 Spectrograms are plots of energy of frequency ranges over time.
 Fundamental frequencies of individual notes and their harmonics are detectable.
 Two audio clips appear to be different.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
a.
 
\begin_inset Graphics
	filename images/Cwave.png
	lyxscale 75
	width 30text%

\end_inset

 b.
 
\begin_inset Graphics
	filename images/Fm7wave.png
	lyxscale 75
	width 30text%

\end_inset


\end_layout

\begin_layout Plain Layout
\align center
c.
 
\begin_inset Graphics
	filename images/Cspectre.png
	lyxscale 75
	width 30text%

\end_inset

 d.
 
\begin_inset Graphics
	filename images/Fm7spectre.png
	lyxscale 75
	width 30text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:CvsFm7"

\end_inset

Time vs.
 Frequency Domains.
 (a) Chord C waveform.
 (b) Chord Fm7 waveform.
 (c) Chord C spectrogram.
 (d) Chord Fm7 spectrogram.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Any time series including digital audio signal can be converted to frequency
 domain using Discrete Fourier Transform.
 DFT expresses the signal as sum of sinusoids scaled and phase-shifted appropria
tely.
 Individual frequency components of the original signal are found along
 with their relative amplitudes (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:4-16-FFT"

\end_inset

).
 The spectrogram of a signal is therefore a successive application of DFT,
 showing spectra of the signal varying over time.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/TwoSines2.eps

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:4-16-FFT"

\end_inset

Digital signal in time domain (left) and a corresponding representation
 in frequency domain (right).
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
The spectral representation seems like a good choice for the inputs comparison.
 It is now possible to define a measure of similarity between two audio
 frames.
 The output of DFT is a vector which means standard vector distance measures
 may be applied.
 Some of the possible options are:
\end_layout

\begin_layout Itemize
Cosine distance (employed in 
\begin_inset CommandInset citation
LatexCommand cite
key "LabROSA"

\end_inset

)
\begin_inset Newline newline
\end_inset


\begin_inset Formula \[
d_{a,b}=\frac{a^{T}b}{\|a\|\|b\|}\]

\end_inset

Similar frames have higher 
\begin_inset Formula $d$
\end_inset

-value close to 1
\end_layout

\begin_layout Itemize
Euclidean distance in 
\begin_inset Formula $n$
\end_inset

-dimensional space (employed in 
\begin_inset CommandInset citation
LatexCommand cite
key "Compare3"

\end_inset

)
\begin_inset Newline newline
\end_inset


\begin_inset Formula \[
d_{a,b}=\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2}}\]

\end_inset

Similar frames have lower 
\begin_inset Formula $d$
\end_inset

-value close to 0
\end_layout

\begin_layout Standard
The choice of a formula does not impact the quality of the alignment in
 any way.
\end_layout

\begin_layout Subsubsection
Chroma Features
\end_layout

\begin_layout Standard
The direct comparison of two DFT vectors is only one possible measure of
 similarity of two audio frames.
 A number of researchers 
\begin_inset CommandInset citation
LatexCommand cite
key "AudioEditors,Chroma+Compare3,Compare3"

\end_inset

 have successfully used the concept of discrete chroma vectors as audio
 features.
 The output from DFT is in frequency domain while frequencies of musical
 notes are well known.
 Pitch classes recur every octave (C, C#, D,...), so each DFT bin is assigned
 to the nearest pitch class as shown on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Chroma"

\end_inset

.
 The magnitudes are averaged within each bin.
 The set of 12 bins is called a chroma vector.
 A sequence of chroma vectors constitutes a chromagram.
 There are a few immediate advantages to this approach:
\end_layout

\begin_layout Itemize
Vector size is reduced to 12 elements as opposed to 256-1024 in the previous
 case.
 Calculating vector distances becomes considerably more efficient
\end_layout

\begin_layout Itemize
It is also a more music oriented approach since it is sensitive to pitches
 and chords
\end_layout

\begin_layout Itemize
It may seem like a disadvantage that the same notes from different octaves
 are mapped to a single bin.
 it's been shown though that this performs quite well and it is appropriate
 to focus on pitch classes and ignore timbre of individual instruments.
 In fact, chroma vectors are insensitive to spectral shape
\end_layout

\begin_layout Itemize
As it was discussed among other audio synthesis options, chroma vectors
 can be generated directly from MIDI events by mapping a value of 1 into
 the bin corresponding to the note pitch.
 To take into account the velocity parameter the value may be scaled.
 This form of chroma vector generation is not entirely justified since not
 all of the harmonics return into the same bin as the fundamental frequency
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/Chroma.png
	height 5cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Chroma"

\end_inset

Piano roll with approximate frequencies marked.
 Every frequency range corresponding to pitch class E is mapped to the same
 chroma vector bin.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
However, it has been confirmed in 
\begin_inset CommandInset citation
LatexCommand cite
key "ChromaClassification"

\end_inset

 that chroma content rarely changes within a single beat.
 Both 
\begin_inset CommandInset citation
LatexCommand cite
key "Robot,ChromaClassification"

\end_inset

 have used chroma vectors in conjunction with a beat tracking algorithm
 thus allowing longer windows to be used.
 Therefore, chroma features alone may not be enough to produce an alignment
 at high resolutions and may not replace the spectral features.
\end_layout

\begin_layout Subsubsection
Summary
\end_layout

\begin_layout Standard
This subsection has covered the previous work relevant for the feature extractio
n stage.
 Alignment in symbolic domain has been discarded almost immediately due
 to its complexity.
 Alignment based on audio features offered flexibility and proved to yield
 good quality alignments.
 The synthesis method to use has to be a trade-off between quality and distribut
ion size, biased towards quality, of course.
 The audio features to be extracted from audio can be a spectrogram or a
 chromagram.
 Both methods were attractive and needed to be evaluated side-by-side.
 
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Subsection
Alignment Stage
\end_layout

\begin_layout Standard
Once the audio features are extracted, the alignment subsystem can use them
 to perform the matching process.
 There are a few techniques for finding the best match between two data
 sequences.
 The ones encountered most often in the works on score-to-audio alignment
 are Dynamic Time Warping and Hidden Markov Models.
 The latter has been discarded due to it complexity and the requirement
 of model training.
 In fact, in 
\begin_inset CommandInset citation
LatexCommand cite
key "HMM"

\end_inset

 HMM was only applied after a preliminary DTW alignment.
 This ensures that the notes are already mostly aligned and thus no pitch
 information had to be encoded into the HMM.
 The technique is based on the notion of state transition where, for example,
 in sung voice the possible states are transient, silence, steady state
 (actual body of the word) and breathing (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:HMM"

\end_inset

).
 Some states are more likely to be followed by other states and some transitions
 may be prohibited.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
a.
 
\begin_inset Graphics
	filename images/HMM-States.png
	width 45text%

\end_inset

 b.
 
\begin_inset Graphics
	filename images/HMM-applied.png
	width 45text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:HMM"

\end_inset

a) Four-state basic state sequence: steady state (SS), silence (S), breath
 (B), beginning transient (BT), end transient (ET) and possible transitions
 between these.
 b) Time domain representation of a sung note with the HMM states labeled.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Transition probabilities may be calculated from manually labelled audio.
 This requires distributing the training data with the application as well
 as crafting the model suitable for many genres of polyphonic and polyinstrument
al music.
 It was therefore decided to focus on another technique, namely Dynamic
 Time Warping.
\end_layout

\begin_layout Subsubsection
Dynamic Time Warping
\end_layout

\begin_layout Standard
Dynamic time warping is an algorithm for finding the best match between
 two time sequences which may vary in time or speed.
 Its use is not limited to applications in signal processing as long as
 the two time series have a defined metric of similarity between any two
 of their elements.
 With certain additions it has been used successfully for connected word
 recognition 
\begin_inset CommandInset citation
LatexCommand cite
key "Ney"

\end_inset

 where a spoken string of words is matched against a set of reference patterns
 of individual words.
 
\end_layout

\begin_layout Standard
In its simplest form the algorithm is a typical example of dynamic programming
 paradigm.
 The calculations are performed on a matrix which is commonly referred to
 as similarity matrix.
 The row and column indices of a similarity matrix are time frame indices
 into the original and synthesised audio respectively.
 The frames, possibly overlapping, are audio features extracted from audio
 in that time range as described in the feature extraction section.
 Each element 
\begin_inset Formula $SM(i,j)$
\end_inset

 of the matrix is a measure of similarity between 
\begin_inset Formula $i$
\end_inset

th frame of original audio and 
\begin_inset Formula $j$
\end_inset

th frame of synthesised audio.
 Similar frames are represented visually as darker spots on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:SimMx"

\end_inset

.
 A distinguishable dark diagonal path represents the best match between
 the two audio and is therefore the primary interest of an alignment algorithm.
\end_layout

\begin_layout Standard
DTW runs on the similarity matrix as its input.
 Each element 
\begin_inset Formula $DTW(i,j)$
\end_inset

 is the cumulative distance along the best path from 
\begin_inset Formula $(0,0)$
\end_inset

 to 
\begin_inset Formula $(i,j)$
\end_inset

.
 The algorithm is based on the observation that if cell 
\begin_inset Formula $(i,j)$
\end_inset

 belongs to the lowest cost path across the whole matrix, then that path
 contains, as part of it, the best path from 
\begin_inset Formula $(0,0)$
\end_inset

 to 
\begin_inset Formula $(i,j)$
\end_inset

.
 It is therefore possible to reuse the results from previous calculations
 to determine the next step.
 More precisely, several neighbour cells are considered as the best previous
 step along the best path to 
\begin_inset Formula $(i,j)$
\end_inset

.
\end_layout

\begin_layout Standard
The pattern on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

a is the simplest and the only one of the three presented that allows skipping
 the whole sections of one or the other audio (by going vertically or horizontal
ly).
 The formula for calculating the cost of best warp path to cell 
\begin_inset Formula $(i,j)$
\end_inset

 is as follows:
\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
DTW(i,j)=min\left\{ \begin{array}{l}
DTW(i-1,j)\\
DTW(i-1,j-1)\\
DTW(i,j-1)\end{array}\right\} +SM(i,j)\label{eq:DTW}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
a.
 
\begin_inset Graphics
	filename images/DTW3.eps
	scale 40

\end_inset

 b.
 
\begin_inset Graphics
	filename images/DTW3greedy.eps
	scale 40

\end_inset

 c.
 
\begin_inset Graphics
	filename images/DTW5.eps
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Neighborhood"

\end_inset

Some DTW neighbourhood patterns.
 Marked cells are examined as best previous steps on the path to 
\begin_inset Formula $(i,j)$
\end_inset

.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
In a lot of cases this properly handles the missing or extra notes as well
 as incorrectly transcribed song structure.
 The other two options require at least one move in every direction at each
 step.
 As a workaround 
\begin_inset CommandInset citation
LatexCommand cite
key "LabROSA"

\end_inset

 presented a two stage algorithm.
 DTW is first applied using a pattern similar to 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

a.
 Any sections with dominating vertical or horizontal moves will then be
 removed from the respective audio.
 The algorithm will be run again this time using pattern 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

b (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Two-stage"

\end_inset

).
 
\end_layout

\begin_layout Standard
Pattern 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

c has been used in 
\begin_inset CommandInset citation
LatexCommand cite
key "AttackSustain"

\end_inset

 in an attempt to obtain smoother transitions right out of DTW.
 While this would achieve excellent results in many applications, it only
 implicitly allows slopes of 1, 2, 3 and their reciprocals.
 This would imply that the slopes would be constantly changing when the
 real slope is anywhere between them.
 If the changes occur too often, noticeable quality degradation of time
 scaled audio will most probably be introduced.
 It is therefore might not be possible to carefully model smooth paths having
 longer sections of constant tempo with DTW alone.
 In the work presented a technique based on linear regression has been successfu
lly applied to smooth the DTW output and achieve subframe resolution.
 Thus the simplest pattern allowing two orthogonal and a diagonal move should
 suffice and save extra computation.
\end_layout

\begin_layout Standard
It should be noted that DTW only produces the cost of the best path through
 the matrix.
 As the dynamic programming style might suggest a simple backtrace from
 the last cell to 
\begin_inset Formula $(0,0)$
\end_inset

 will return the best path as a relation of frame indices of the two audio.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/BSSMSimMx.png
	lyxscale 50
	height 9cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:SimMx"

\end_inset

Similarity matrix using spectral representation as the audio feature.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/Two-stage DTW.png
	lyxscale 50
	height 7cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Two-stage"

\end_inset

Two-stage alignment.
 White rectangles indicate the diagonal regions passed to the second-stage
 alignment.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Subsubsection
Optimisation Techniques
\end_layout

\begin_layout Standard
DTW always returns the optimal path and was shown to perform well.
 It runs in time 
\begin_inset Formula $\mathcal{O}(n\cdot m)$
\end_inset

 where 
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

 are the number of feature frames of original and synthesised audio respectively.
 For simplicity the length of both time series will be assumed to be 
\begin_inset Formula $n$
\end_inset

, so the asymptotic behavior becomes 
\begin_inset Formula $\mathcal{O}(n^{2})$
\end_inset

.
 Given a 4 minute song and the requirement to achieve a time resolution
 of 64 milliseconds (up to around 1/32 note in tempo 120), the number of
 frames will be about 4000 (no frame overlap).
 That results in a similarity matrix with around 16 million cells in it
 and takes a total of 1 minute running time on a 2.5 GHz machine in the Matlab
\begin_inset Formula $^{®}$
\end_inset

 environment.
 This is not acceptable considering that most of the audio used with the
 end product will probably be very close to the score and only minor tempo
 modifications will be required.
\end_layout

\begin_layout Standard
Methods used to make DTW faster fall into three categories:
\end_layout

\begin_layout Enumerate
Indexing
\end_layout

\begin_layout Enumerate
Constraints
\end_layout

\begin_layout Enumerate
Data Abstraction
\end_layout

\begin_layout Standard
Optimisations in the 
\series bold
indexing
\series default
 category attempt at reducing the number of times DTW has to be applied
 when a set of time series is given.
 An example of such a problem would be finding in set of time series one
 that is more similar to a given time series than the others.
 This relays back to the example of connected word recognition in 
\begin_inset CommandInset citation
LatexCommand cite
key "Ney"

\end_inset

 which could potentially employ the optimisation.
 As for the problem at hand, further research could be done that would take
 into account the repetitive nature of music.
 It may indeed be possible to convert it to a problem which would benefit
 from indexing optimisations.
 This is out of scope of the current research, however.
\end_layout

\begin_layout Standard

\series bold
Constraints-based 
\series default
optimisations reduce the running time of DTW by limiting the cells that
 are evaluated in the similarity matrix (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Constraints"

\end_inset

).
 Such a constrained algorithm will produce good or even optimal results
 in most cases where the score is a correct representation of audio.
 It may fail, however, when the score only partially represents the audio
 track.
 Suppose, the imported recording is a cover of the original song by another
 band and there are new sections introduced that are not in the score.
 Then the horizontal parts of the otherwise optimal path may be clipped
 by the boundaries of the constrained region.
\end_layout

\begin_layout Standard
A more adaptive constraint model, path pruning, has been used in 
\begin_inset CommandInset citation
LatexCommand cite
key "AttackSustain"

\end_inset

.
 For every successfully evaluated row in the cost matrix the paths with
 the augmented cost lower than a specified threshold are selected.
 The leftmost and the rightmost of such paths become the boundaries for
 the corridor in which the next row is evaluated.
 The threshold is dynamically calculated and is a function of the best cost
 encountered in the previous row.
 Such a model is designed to easily adapt to movements in the vertical direction
 and with sufficiently large threshold - in horizontal, too.
 
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
a.
 
\begin_inset Graphics
	filename images/Constraint1.png
	scale 70

\end_inset

 b.
 
\begin_inset Graphics
	filename images/Constraint2.png
	scale 70

\end_inset

 
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Constraints"

\end_inset

Two DTW constraints: Sakoe-Chiba Band (a) and an Itakura Parallelogram (b).
 Only shaded cells are evaluated.
 
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard

\series bold
Data abstraction
\series default
 based optimisations focus on the idea of performing DTW on the reduced
 representations of data.
 That is, performing DTW at a lower resolution, then working up to higher
 resolutions as required.
 In the case of the problem at hand this would mean taking larger frame
 sizes and using the results of DTW as an approximation for further DTW
 applications.
\end_layout

\begin_layout Standard
An innovative method has been proposed in 
\begin_inset CommandInset citation
LatexCommand cite
key "FastDTW"

\end_inset

, that combines the constraint-based approach with data abstraction achieving
 linear runtime and memory requirements.
 The algorithm, FastDTW, proceeds by recursively reducing the resolution
 of the time series by a factor of two, applying DTW at a lower resolution
 and using the resulting path to constraint DTW at the next finer resolution
 (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:FastDTW"

\end_inset

).
 Although the algorithm may seem very attractive, it will not be able to
 improve the performance of score-to-audio alignment.
 Since it requires creating a reduced data representation at every resolution
 (
\begin_inset Formula $\mathcal{O}(\log n)$
\end_inset

 in total) it only significantly outperforms plain DTW when the length of
 the time series exceeds about 10000 elements.
 This is about twice as much as is needed for a good time resolution for
 an average song.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/FastDTW.png
	width 100text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:FastDTW"

\end_inset

The four different resolutions evaluated during a complete run of the FastDTW
 algorithm.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Error Correction
\end_layout

\begin_layout Standard
One of the outputs of the system is a time scale modified audio.
 This means that the audio produced will be time stretched or compressed
 to adapt to to the tempo assigned to the score.
 There are, however, several problems associated with this requirement that
 arose with the use of Dynamic Time Warping algorithm introduced previously.
\end_layout

\begin_layout Itemize
DTW often returns a path full of little humps in the parts of the similarity
 matrix with a high concentration of similarly weighted elements
\end_layout

\begin_layout Itemize
DTW returns a numerically optimal path which does not always reflect the
 ground-truth
\end_layout

\begin_layout Itemize
An informal listening test showed that minor but frequent playback speed
 changes introduce a noticeable quality loss
\end_layout

\begin_layout Itemize
If the warping path produced by DTW is interpreted directly, the only playback
 rates would be 1, 0 and Infinity
\end_layout

\begin_layout Standard
It was therefore crucial to investigate possible ways to keep the tempo
 constant across longer sections of an audio file.
 Most of the works studied in the scope of this research only aimed at producing
 the appropriately modified score that would sound in sync with the audio.
 Surely, the modified score can be resynthesised and would not have the
 problems of the time scaled audio.
\end_layout

\begin_layout Standard
While 
\begin_inset CommandInset citation
LatexCommand cite
key "LabROSA"

\end_inset

 was one such research, they did look into addressing some of these issues.
 In addition to applying a two-stage DTW described in the respective section,
 the path was smoothed across multiple alignment frame pairs.
 No discussion of the smoothing method was provided, however.
 The remainder of this section is devoted to discussing several smoothing
 and fitting techniques from mathematics, statistics and computer graphics.
\end_layout

\begin_layout Subsubsection
Requirements
\end_layout

\begin_layout Standard
It is important to establish the requirements to the algorithm as well as
 its inputs and expected outputs.
 Ideally the algorithm would be able to analyse the path and segment it
 such that the slopes of the segments are piece-wise constant.
 Given a threshold in milliseconds, the segments should be the longest possible
 such that the new position of each point is within the threshold distance
 from the path predicted by DTW.
 The path would be supplied in the form of frame pairs which can be treated
 as Cartesian coordinates in two dimensions.
 The expected output is a reduced number of coordinates, called knots, such
 that the linear interpolation of these approximates the warping path according
 to some predefined metric.
 Sample input and output are shown on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:MSE"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/FitLines.png
	scale 60

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:MSE"

\end_inset

Automatic Segmentation Detection.
 Warping path as returned by DTW (blue) and segments fitted with linear
 regression models (red)
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Curve Fitting
\end_layout

\begin_layout Standard
A major area of study that has been looked at was curve fitting.
 Curve fitting is the process of construction a function that has the best
 fit to the given data.
 It may either be an exact fit to the data (also called interpolation),
 or approximate (smoothing).
\end_layout

\begin_layout Itemize
Interpolation is inapplicable since the warping path is already defined
 by a large number of points.
 However, the output of the algorithm, i.e.
 the sequence of knots, is linearly interpolated to produce the new path.
 
\end_layout

\begin_layout Itemize
Smoothing is the process creating an approximating function that attempts
 to capture important patterns in the data, while leaving out noise or other
 fine-scale structures.
 This definition very closely resembles the problem at hand.
 In many cases, the warping path is already a straight line, distorted by
 some off the line humps.
\end_layout

\begin_layout Standard
Many smoothing techniques are also inapplicable due to the nature of the
 input data or the expected output:
\end_layout

\begin_layout Itemize
Some are targeted at processing a set of observations of some real world
 variables that form a relationship, yet are scattered around some unknown
 points being approximated.
 On the other hand, DTW model precisely defines the relative positioning
 of two consecutive points on the path (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

).
\end_layout

\begin_layout Itemize
Besides, the smoothing may be carried out based on purely local features
 and does not guarantee any functional relationship on the output data (e.g.
 polynomial, or, in the present case, piece-wise linear).
\end_layout

\begin_layout Standard
To preserve the focus on the linearity of the output the research was turned
 towards the smoothing methods that employ linear regression discussed below.
\end_layout

\begin_layout Subsubsection
Linear Regression
\end_layout

\begin_layout Standard
Linear regression is a technique for model a linear relationship between
 two or more variables.
 To relate it back to the original problem, suppose that the abscissas and
 ordinates of all of the points in the warping path form vectors 
\begin_inset Formula $X=x_{1}\ldots x_{n}$
\end_inset

 and 
\begin_inset Formula $Y=y_{1}\ldots y_{n}$
\end_inset

 respectively.
 Also suppose that the path is conceptually a straight line.
 Two points is sufficient to uniquely define a line, yet 
\begin_inset Formula $ $
\end_inset

there is 
\begin_inset Formula $n$
\end_inset

 of them it total.
 Such a line is said to be overdetermined.
 Thus it is not possible to uniquely fit a line 
\begin_inset Formula $y=ax+b$
\end_inset

 through points 
\begin_inset Formula $(x_{i},y_{i})$
\end_inset

 where 
\begin_inset Formula $i=1\ldots n$
\end_inset

.
 Proceed by introducing an error parameter 
\begin_inset Formula $\varepsilon$
\end_inset

 and solving equations 
\begin_inset Formula $y_{i}=ax_{i}+b+\varepsilon_{i}$
\end_inset

, while minimising 
\begin_inset Formula $\varepsilon$
\end_inset

 in some way.
 The least squares method approaches it by minimising the sum of squared
 errors: 
\begin_inset Formula \begin{equation}
\|\varepsilon\|^{2}=\sum_{i=1}^{n}\varepsilon_{i}^{2}=\sum_{i=1}^{n}(y_{i}-ax_{i}-b)^{2}\label{eq:SSE}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
But 
\begin_inset Formula $\|\varepsilon\|^{2}$
\end_inset

 is a quadratic function of 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

, whose minimum is reached when both partial derivatives are 0:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
\frac{\partial\|\varepsilon\|^{2}}{\partial a}=-2\sum_{i=1}^{n}x_{i}(y_{i}-ax_{i}-b)=0\text{, leading to}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
\frac{\sum_{i=1}^{n}x_{i}}{n}a+b=\frac{\sum_{i=1}^{n}y_{i}}{n}\text{, and}\label{eq:deda}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula \[
\frac{\partial\|\varepsilon\|^{2}}{\partial b}=-2\sum_{i=1}^{n}(y_{i}-ax_{i}-b)=0\text{, leading to}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
a+\frac{\sum_{i}x_{i}}{\sum_{i}x_{i}^{2}}b=\frac{\sum_{i}x_{i}y_{i}}{\sum_{i}^{n}x_{i}^{2}}\label{eq:dedb}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
The system of two linear equations 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:deda"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:dedb"

\end_inset

 can be written in matrix form as
\end_layout

\begin_layout Standard
\begin_inset Formula \[
\left[\begin{array}{cc}
\frac{\sum_{i}x_{i}}{n} & 1\\
1 & \frac{\sum_{i}x_{i}}{\sum_{i}x_{i}^{2}}\end{array}\right]\left[\begin{array}{c}
a\\
b\end{array}\right]=\left[\begin{array}{c}
\frac{\sum_{i}y_{i}}{n}\\
\frac{\sum_{i}x_{i}y_{i}}{\sum_{i}x_{i}^{2}}\end{array}\right]\]

\end_inset


\end_layout

\begin_layout Standard
This can be rearranged to find 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 as follows:
\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
\left[\begin{array}{c}
a\\
b\end{array}\right]=\frac{1}{n\sum_{i}x_{i}^{2}-(\sum_{i}x_{i})^{2}}\left[\begin{array}{c}
n\sum_{i}x_{i}y_{i}-\sum_{i}x_{i}\sum_{i}y_{i}\\
\sum_{i}x_{i}^{2}\sum_{i}y_{i}-\sum_{i}x_{i}\sum_{i}x_{i}y_{i}\end{array}\right]\label{eq:lsq}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
The coefficients can be substituted back into 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SSE"

\end_inset

 to give the equation for sum of squared errors (
\emph on
SSE
\emph default
) or alternatively mean-square error 
\begin_inset Formula $MSE=\frac{1}{n}SSE$
\end_inset

.
 
\emph on
MSE 
\emph default
can give an idea of how good the model is on average.
 Recalling the original problem, 
\begin_inset Formula $\sqrt{MSE}$
\end_inset

 is actually the average vertical distance in frames, between the fitted
 line and the warping path as returned by DTW.
\end_layout

\begin_layout Standard
By using linear regression it is possible to fit one straight line to the
 compete data set.
 However, due to the possible tempo fluctuations between the two inputs,
 it is required that multiple lines are fitted.
 Below are some of the possible solutions that use linear regression in
 conjunction with the least squares method.
\end_layout

\begin_layout Description
Local
\begin_inset space ~
\end_inset

Linear
\begin_inset space ~
\end_inset

Regression
\begin_inset space ~
\end_inset

Smoother
\series medium
,
\series default
 first introduced in 
\begin_inset CommandInset citation
LatexCommand cite
key "LocalReg"

\end_inset

, starts by fitting a regression model to the data within the window of
 some predefined size 
\begin_inset Formula $\lambda$
\end_inset

 sliding by 
\begin_inset Formula $\Delta X$
\end_inset

.
 The estimate for the mid point 
\begin_inset Formula $X_{0}$
\end_inset

 of the window and its neighborhood is a constant equal to the value of
 the fitted line at 
\begin_inset Formula $X_{0}$
\end_inset

 (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:LocalReg"

\end_inset

).
 The process is repeated for every 
\begin_inset Formula $X_{0}$
\end_inset

 by shifting the window by 
\begin_inset Formula $\Delta X$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard
This is a greedy algorithm which does not need the complete data set to
 operate.
 It is very efficient and may be applied to the warping path with the following
 remarks:
\end_layout

\begin_layout Itemize
The window must be sufficiently large (and the overlap sufficiently small)
 to actually cure the problem of continuously fluctuating tempo
\end_layout

\begin_layout Itemize
Larger window, on the other hand, adapts slower to the real tempo fluctuations,
 thus may introduce discrepancies in the sound, defeating the purpose of
 error correction
\end_layout

\begin_layout Itemize
The window and the overlap parameters are fixed for the run of the algorithm
 and cannot be set according to the desired mean-square error threshold
 in advance.
\end_layout

\end_deeper
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/LocalLinReg.png
	height 8cm

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:LocalReg"

\end_inset

Application of local linear regression smoother.
 The result estimate 
\begin_inset Formula $\hat{Y}(X_{0})$
\end_inset

 is the value of the fitted line at 
\begin_inset Formula $X_{0}$
\end_inset

 (black)
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Description
Multivariate
\begin_inset space ~
\end_inset

Adaptive
\begin_inset space ~
\end_inset

Regression
\begin_inset space ~
\end_inset

Splines
\series medium
,
\series default
 abbreviated as 
\begin_inset Quotes eld
\end_inset

MARS
\begin_inset Quotes erd
\end_inset

 
\begin_inset CommandInset citation
LatexCommand cite
key "MARS"

\end_inset

, is an extension of linear models which automatically determines the knots
 from the provided data and returns a set linear function providing the
 best fit between the corresponding knots (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:MARS"

\end_inset

).
 It proceeds in two stages:
\end_layout

\begin_deeper
\begin_layout Enumerate
In the forward path it iteratively searches for the knots which, when added,
 give the maximum reduction in 
\emph on
SSE
\emph default
 (sum squared error).
 The search is stopped when either the change in the overall 
\emph on
SSE
\emph default
 is negligible or the maximum number knot is reached (user adjustable parameter).
\end_layout

\begin_layout Enumerate
The backward pass prunes the model by removing the least effective knots
 until it finds the best submodel.
 The algorithm trades off fitting quality against model complexity and no
 longer uses pure
\emph on
 SSE 
\emph default
as the criteria for choosing the candidate knot to be pruned.
\end_layout

\begin_layout Standard
MARS method automatically partitions the provided data into sections with
 one linear model in each of them without making an assumption about the
 length of such sections.
 This seems especially relevant to the problem of audio-to-score alignment
 where it is difficult to predict the number of places of tempo fracture
 in advance.
 
\end_layout

\begin_layout Standard
The algorithm allows adjusting the maximum number of knots and various other
 limits, which may appear to be useful for the problem at hand.
 Indeed, the user may want to take over the system and manually control
 the error correction.
 This might as well cure some particularly bad alignments by smoothing things
 out.
\end_layout

\begin_layout Standard
It is not clear, however, how well it performs on the data which is already
 mostly in linear relationship and the tempo changes are very subtle (expected
 
\emph on
MSE 
\emph default
less than 1)
\emph on
.

\emph default
 Never-the-less, this technique provides a good motivation for further research
 and demonstrates relevance to the problem at hand.
\end_layout

\end_deeper
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/MARS.png
	height 6cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:MARS"

\end_inset

Application of Multivariate Adaptive Regression Splines method modelling
 the relationship between two variables.
 The fitted model (black) has five knots at about 0, 1.5, 3.3 4.7 and 6.
 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Summary
\end_layout

\begin_layout Standard
This subsection presented a literature overview for the problem of aligning
 two sequences containing extracted audio features.
 The two alternatives were Hidden Markov Models and Dynamic Time Warping.
 The former was discarded for the reasons of complexity and because it required
 distributing model training data with the software package.
 On the other hand DTW proved to be a good algorithm for this task.
\end_layout

\begin_layout Standard
Several DTW movement models were considered.
 The simplest of them offers two orthogonal and one diagonal movement at
 each step it .
 Even with the simplest model there were concerns regarding the poor DTW
 performance time-wise.
 Several optimisation techniques have been reviewed.
 Some did not seem to meet the requirements of the software (like statically
 constrained methods), others did not improve performance in the case of
 the current task (FastDTW) or are simply inapplicable to the problem (Indexing-
based approaches).
 One improvement that did seem suitable was the adaptive constraint based
 approach, where the corridor for the warp path is generated on the fly.
\end_layout

\begin_layout Standard
A range of methods for smoothing the warping path and correcting the DTW
 error has also be presented in this section.
 This discussion formed the mathematical basis for the respective part of
 the proposal.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
Proposed Solution
\end_layout

\begin_layout Standard
This section covers the details of the proposed system at a conceptual level
 with only some implementation details.
 It presents design decisions at every step (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:BlockDia2"

\end_inset

).
 Several parts of the system offer more than one alternative implementation
 so as to aid evaluation by comparison.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/BlockDia.png
	width 100text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:BlockDia2"

\end_inset

Overview of the system with chosen alternatives at each stage.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Subsection
Target System
\end_layout

\begin_layout Standard
The alignment method proposed in this document was designed with a particular
 target system in mind.
 It was chosen to be an extension to a notation editing software with playback
 capabilities.
 No closed source products were considered as they typically do not have
 means for extending their functionality by third parties.
 Two guitar players oriented open source software solutions were considered:
 KGuitar 
\begin_inset CommandInset citation
LatexCommand cite
key "KGuitar"

\end_inset

 and TuxGuitar 
\begin_inset CommandInset citation
LatexCommand cite
key "TuxGuitar"

\end_inset

.
 At the time of this writing KGuitar is still in alpha development stage.
 TuxGuitar, on the other hand, is a mature cross-platform software with
 a large user base.
 TuxGuitar was chosen as the target system.
\end_layout

\begin_layout Standard
TuxGuitar, among other functionality, supports importing scores in various
 file formats including MIDI.
 Multitrack scores can be viewed, edited and auditioned using operating
 system's or third party software synthesisers.
\end_layout

\begin_layout Standard
TuxGuitar is implemented in the Java programming language and can be extended
 through the use of plugins.
 It previously did not provide support for importing or playing audio files.
 Nor there existed a publicly available time stretching library with Java
 bindings.
 Developing such an extension has appeared to be time consuming and therefore
 has not been completed.
 Besides, the alignment method itself is not yet suitable for use by the
 end-users.
 The current state of the implementation will be discussed in a later section.
\end_layout

\begin_layout Subsection
Prototyping Environment
\end_layout

\begin_layout Standard
While the final product is meant to extend TuxGuitar's functionality, the
 latter had no preexisting support for audio files or basic signal processing
 routines.
 To speed up prototyping, Matlab 
\begin_inset CommandInset citation
LatexCommand cite
key "Matlab"

\end_inset

 environment was chosen for its scripting features and a substantial digital
 signal processing support.
 Matlab's ability to generate complex plots to visualise results turned
 out to be invaluable also.
 Not all of the system's features are present in the prototype.
 As such all MIDI file handling was omitted.
 Instead, it expects another audio file, which may have been synthesised
 from MIDI.
 Generating audio from MIDI is done manually and has only been automated
 in the TuxGuitar implementation.
 This also allowed to conduct tests by aligning the original studio recording
 with a backing track or a cover by another band.
\end_layout

\begin_layout Subsection
Feature Extraction
\end_layout

\begin_layout Standard
The feature extraction subsystem is concerned with transforming the score
 and audio inputs into directly comparable structures.
 Comparison based on audio features has been chosen over comparison in symbolic
 domain due to the high complexity of the latter.
 Thus the score is rendered to audio using a software synthesiser and alignment
 between two audio is carried out.
\end_layout

\begin_layout Standard
As it has been discussed before at least two ways of generating audio exist:
\end_layout

\begin_layout Enumerate
MIDI tracks can be substituted by their corresponding instruments, or
\end_layout

\begin_layout Enumerate
one instrument can be substituted for every track.
\end_layout

\begin_layout Standard
Both were chosen to be implemented since adding support for one when the
 other is in place did not pose a problem.
 The third option dealing with direct extraction of audio-like features
 from MIDI events was omitted as it requires MIDI events manipulation at
 a low level and was not a priority of the research.
\end_layout

\begin_layout Standard
Next after the audio is generated, audio features are extracted.
 Two audio features most commonly found in literature were chosen:
\end_layout

\begin_layout Enumerate
Spectrograms - created by applying DFT to a moving window with an overlap.
\end_layout

\begin_layout Enumerate
Discrete chromagrams - created from the spectrograms by adding together
 and averaging the energy bins around the 12 pitch classes (as described
 in section 2).
\end_layout

\begin_layout Standard
The first one preserves the spectral shape of the audio which was found
 to confuse the alignment in some cases where the two audio are very different
 in that respect.
 The second approach minimises the differences in spectral shape, focusing
 on pitch alone.
 This was found to aid the alignment of pitched instruments but did not
 honour so much the percussive instruments.
 Both methods were evaluated against music in various genres.
 The option of generating chroma vectors directly from score is tempting
 but requires low level MIDI manipulation, so it was left out.
\end_layout

\begin_layout Standard
The spectrogram window is of Hann type o(Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Hann"

\end_inset

) which is applied to amplitudes through multiplication prior to taking
 the DFT.
 The window function is usually applied in order to minimise the effect
 of the overlap.
 In the present system overlapping was found not to be necessary.
 If the audio is downsampled to 8000 Hz, the highest chromatic pitch present
 in the transform is 
\begin_inset Formula $B_{7}$
\end_inset

 at 3951 Hz.
 This leaves out only one pitch on the standard 88-keys piano keyboard,
 that is 
\begin_inset Formula $C_{8}$
\end_inset

 at 4186 Hz.
 The above frequencies are given assuming the middle 
\begin_inset Formula $A$
\end_inset

 to be 440 Hz.
 In practice the playing range is much lower and the higher octaves only
 contain the smeared higher order harmonics.
 It is in the interest of the system to remove from the signal as much of
 the non-pitch information as possible.
\end_layout

\begin_layout Standard
Another advantage of such setup is that there are less DFT bins for the
 same time-frequency resolution.
 Assuming the sampling frequency of 8000 Hz and a window length of 512 samples,
 the time resolution is 64 milliseconds.
 This almost exactly corresponds to a 
\begin_inset Formula $^{1}/_{32}$
\end_inset

 note length in tempo 120 bpm (Table 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:Divlen"

\end_inset

).
 This results in a decent alignment resolution for most songs.
 At times one can hear the percussive hits being slightly off.
 However, this is a reasonable trade-off for performance once the system
 is used as intended.
 That is, the user is only hearing one audio track while the position in
 the song is being visually traced on the note staff.
 According to a non-official Stanford study referenced in 
\begin_inset CommandInset citation
LatexCommand cite
key "Stanford"

\end_inset

 the sound can come up to 45 ms early, or the picture can be ahead of the
 sound by as much as 125 ms.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
definecolor{lightlightgray}{gray}{0.90}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
cclg}{
\backslash
cellcolor{lightlightgray}}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="9">
<features>
<column alignment="right" valignment="top" width="0">
<column alignment="right" valignment="top" width="0">
<column alignment="right" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="right" valignment="top" width="0">
<column alignment="right" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Tempo,
\end_layout

\end_inset
</cell>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $^{1}/_{4}$
\end_inset

 note
\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $^{1}/_{8}$
\end_inset

 note
\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $ $
\end_inset


\begin_inset Formula $^{1}/_{16}$
\end_inset

 note
\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $^{1}/_{32}$
\end_inset

 note 
\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
BPM
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

samples
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
ms
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

samples
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
ms
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

samples
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
ms
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

samples
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
ms
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
90
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

5333
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
667
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

2667
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
333
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

1333
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
167
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

667
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
83
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
120
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

4000
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
500
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

2000
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
250
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

1000
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
125
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

500
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
63
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
150
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

3200
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
400
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

1600
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
200
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

800
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
100
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

400
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
50
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
180
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

2667
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
333
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

1333
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
167
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

667
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
83
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
cclg 
\end_layout

\end_inset

333
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
42
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:Divlen"

\end_inset

Note lengths at 8 kHz sampling rate
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/hann.png
	scale 60

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Hann"

\end_inset

64-point Hann window in time domain.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Alignment Stage
\end_layout

\begin_layout Standard
Out of the two major methods for aligning two musical sequences only DTW
 was discussed in detail due to HMM's increased complexity of the model
 and storage requirements.
 As for the type of DTW, no pattern would ensure that the best slope in
 the path will be chosen.
 It has therefore been decided to use to simplest pattern on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Neighborhood"

\end_inset

a and seek other ways of finding the right slope.
 The need for that will be explained in the next subsection.
\end_layout

\begin_layout Standard
DTW has been implemented in the prototype.
 It was found however, that the algorithm takes unacceptably long time to
 evaluate the whole matrix at sufficiently high resolutions.
 After studying the possible optimisation techniques, one of them has been
 adopted.
 Path Pruning 
\begin_inset CommandInset citation
LatexCommand cite
key "AttackSustain"

\end_inset

 has been chosen over the other proposals since it allows to adapt the constrain
t corridor to the path direction changes, therefore increasing the chances
 of getting the optimal path in more cases.
 It follows the constraint based optimisation pattern.
 It has described in some detail in the previous section.
 It does not evaluate the complete matrix but it does require it to be evaluated
 at full resolution in one go.
 As much as this approach seems attractive, it did not work very well in
 practice due to the added computational overhead as well as instabilities
 causing the full matrix to be evaluated.
\end_layout

\begin_layout Subsection
Error Correction
\end_layout

\begin_layout Standard
It has been decided to use the simplest 3-directional pattern for Dynamic
 Time Warping and instead rely on curve fitting to account for the problems
 associated with this choice and DTW in general.
 In particular, the algorithms based on linear regression were considered
 in order to
\end_layout

\begin_layout Itemize
smooth out the possible discrepancies in the path,
\end_layout

\begin_layout Itemize
identify the regions with the constant tempo, and
\end_layout

\begin_layout Itemize
prepare the alignment map with less entries than the number of frame pairs
 in the path.
\end_layout

\begin_layout Standard
The list of the methods chosen to be reviewed was in no way comprehensive
 but it provided sufficient directives and motivation to design a custom
 method for the task.
 Some of the highlights of the techniques are presented below:
\end_layout

\begin_layout Itemize
The 
\emph on
Local Linear Regression Smoother 
\emph default
traded the smoothness against being able to quickly adapt to tempo variations.
 The window length and the overlap are the only controllable parameters
 which cannot be specified in therms of the desired mean-square error or
 similar.
\end_layout

\begin_layout Itemize
The 
\emph on
Multivariate Adaptive Regression Splines 
\emph default
method is a sophisticated algorithm that can automatically determine the
 most important fracture points in the path (knots) and gives room for manual
 configuration.
\end_layout

\begin_layout Standard
It has been decided to design an algorithm specifically for the task, that
 would address the problems of the fixed-window algorithms yet be simpler
 and more efficient than MARS.
 The new algorithm makes use of the fact that the step of the input data
 is small and non-decreasing (i.e.
 
\begin_inset Formula $\Delta x,y\in\{0,1\}$
\end_inset

).
 The algorithm is still able to perform adequately on other data, e.g.
 if the pattern is replaced with a more sophisticated one.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/SimpleFit.eps

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:SampleFit"

\end_inset

A sample run of the proposed regression algorithm with 
\emph on
MSE 
\emph default
threshold 0.2
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The new algorithm proceeds by fitting a straight line to some contiguous
 subsequence of data from the path using the least squares method (Figure
 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:SampleFit"

\end_inset

).
 If the resulting 
\emph on
MSE 
\emph default
is below the specified threshold, then the data sequence being looked at
 is extended by one point.
 In case it exceeds 
\emph on
MSE
\emph default
 the data point added last is discarded and the previous fitted line parameters
 are used to set a new knot.
 In the figure example this knot is set to be 
\begin_inset Formula $A_{0}$
\end_inset

: fitting to the points up to 
\begin_inset Formula $(7,5)$
\end_inset

 resulting in a too high 
\emph on
MSE
\emph default
, therefore to obtain the knot 
\begin_inset Formula $A_{0}$
\end_inset

 the line was only fitted up to point 
\begin_inset Formula $(6,5)$
\end_inset

 of the original data.
\end_layout

\begin_layout Standard
Once a new knot is found a new data subsequence begins to accumulate starting
 with the last element of the previous subsequence.
 When it is time for a new knot (
\begin_inset Formula $B_{0}$
\end_inset

), that is the slope and intersect of the new line are known and will not
 change, the algorithm goes back to the previous knot (
\begin_inset Formula $A_{0}$
\end_inset

) and updates it to be the intersection of the two lines 
\begin_inset Formula $(0,A_{0})$
\end_inset

 and 
\begin_inset Formula $(A_{1},B_{0})$
\end_inset

, that is 
\begin_inset Formula $A_{1}$
\end_inset

.The algorithm proceeds in this fusion until no data points remain.
\end_layout

\begin_layout Standard
The algorithm's pseudo code is presented in Listing 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:ECC"

\end_inset

.
 It currently runs in quadratic time in the length of the path but can easily
 be made linear by not recalculating the regression model at every iteration.
 In practice this overhead does not pose a problem.
\end_layout

\begin_layout Subsection
Summary
\end_layout

\begin_layout Standard
This section introduced and justified the design decisions of the current
 system.
 The target system and the prototyping environment were introduced briefly
 mentioning the separation of scope between them.
 Then the two alternative feature sets were presented mentioning some of
 the constants involved.
 The alignment stage was only briefly touched up since DTW was discussed
 in great detail in the literature review section.
 The implementation specifics are left for the respective section.
 Lastly, a new Error Correction algorithm was presented as an alternative
 for more complicated DTW patterns and preparation for audio time scaling.
\end_layout

\begin_layout Standard
While the section only described the high level design with only some implementa
tion introduced, some of the most important implementation issues and details
 will be revisited once more in the following section.
 
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\paragraph_spacing single
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
lstset{ language=Pseudo }
\end_layout

\end_inset


\begin_inset listings
lstparams "basicstyle={\normalsize\ttfamily},tabsize=4"
inline false
status open

\begin_layout Plain Layout

/**
\end_layout

\begin_layout Plain Layout

 * Fits straight lines to a sequence of data points automatically
\end_layout

\begin_layout Plain Layout

 * determining the knots.
 The algorithm assumes the presence of
\end_layout

\begin_layout Plain Layout

 * LeastSquares function reterning the slope/intersect of the
\end_layout

\begin_layout Plain Layout

 * fitten line and the resulting MSE.
\end_layout

\begin_layout Plain Layout

 *
\end_layout

\begin_layout Plain Layout

 * path    sorted sequence of data points
\end_layout

\begin_layout Plain Layout

 * thresh  MSE threshold that *each* line will not exceed
\end_layout

\begin_layout Plain Layout

 * retruns sorted collection of knots 
\end_layout

\begin_layout Plain Layout

 */
\end_layout

\begin_layout Plain Layout

FitLines (path, thresh)
\end_layout

\begin_layout Plain Layout

  // initialise
\end_layout

\begin_layout Plain Layout

  knots  = []                // result is collection of points
\end_layout

\begin_layout Plain Layout

  data   = []                // window of data from path
\end_layout

\begin_layout Plain Layout

  a0, b0 = 0                 // parameters of the last fitted line
\end_layout

\begin_layout Plain Layout

  foreach point in path
\end_layout

\begin_layout Plain Layout

    data.append(point)                // add point to subsequence
\end_layout

\begin_layout Plain Layout

    (a,b,mse) = LeastSquares(data)    // fit line to the data
\end_layout

\begin_layout Plain Layout

    /* check if threshold is reached */
\end_layout

\begin_layout Plain Layout

    if mse > thresh
\end_layout

\begin_layout Plain Layout

      data.remove(end)                // discard last added point
\end_layout

\begin_layout Plain Layout

      (a,b,mse) = LeastSquares(data)  // fit line again
\end_layout

\begin_layout Plain Layout

      /* first shift the previous knot where it belongs */
\end_layout

\begin_layout Plain Layout

      x0 = -(b-b0)/(a-a0)             // find intersection
\end_layout

\begin_layout Plain Layout

      y0 = a*x0+b
\end_layout

\begin_layout Plain Layout

      knots.replace(end, Point(a0,b0))
\end_layout

\begin_layout Plain Layout

      /* find the coordinates of the new knot */
\end_layout

\begin_layout Plain Layout

      x = data(end).x
\end_layout

\begin_layout Plain Layout

      y = a*x + b
\end_layout

\begin_layout Plain Layout

      knots.append(Point(x,y))
\end_layout

\begin_layout Plain Layout

      a0 = a                          // record the parameters of
\end_layout

\begin_layout Plain Layout

      b0 = b                          // the just fitted line
\end_layout

\begin_layout Plain Layout

      data = [data(end), point]       // reinitialise subsequence
\end_layout

\begin_layout Plain Layout

    end if
\end_layout

\begin_layout Plain Layout

  end for
\end_layout

\begin_layout Plain Layout

  return knots
\end_layout

\begin_layout Plain Layout

end FitLines
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:ECC"

\end_inset

Error Correction Algorithm Pseudo Code
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
Implementation
\end_layout

\begin_layout Standard
The previous section were devoted almost entirely to the design of the system.
 Textual explanations with some pseudo code additions ware provided provided
 for each technique employed.
 The present section builds upon the the content of the previous section
 and projects it onto the target system and the prototype.
 It discusses the interaction between the parts of the system and the external
 frameworks or systems.
 Additionally, it elaborates on each technique by describing implementation
 specific issues that had to be overcome.
\end_layout

\begin_layout Subsection
Target System
\end_layout

\begin_layout Standard
TuxGuitar, the target system, is a powerfull guitar tablature editor enabling
 guitarists to edit and listen to multitrack scores.
 One of the reasons for it popularity is its extesible design.
 It provides support for extending its functionality through the use of
 several categories of plugins:
\end_layout

\begin_layout Description
Browser
\begin_inset space ~
\end_inset

Plugins Extend the built-in score collection management system.
 They unite the online community resources and the local content.
\end_layout

\begin_layout Description
Importer
\begin_inset space ~
\end_inset

and
\begin_inset space ~
\end_inset

Exporter
\begin_inset space ~
\end_inset

Plugins Add support for new score file types.
 In fact, MIDI support is provided in the form of such a plugin.
 These plugins, however, do not extend to audio since audio does not typically
 contain any score information.
\end_layout

\begin_layout Description
MIDI
\begin_inset space ~
\end_inset

Output
\begin_inset space ~
\end_inset

Port
\begin_inset space ~
\end_inset

Plugins Provide support for more synthesisers to audition scores.
 It refers to both software and physical output ports.
 The possibity to audition the scores through the Gervill software synthesiser,
 discussed earlier, is provided in the form of a plugin too.
\end_layout

\begin_layout Description
MIDI
\begin_inset space ~
\end_inset

Sequencer
\begin_inset space ~
\end_inset

Plugins Sequencers are low level implementations for MIDI playback handling.
 It is discussed in detail below.
\end_layout

\begin_layout Description
Tool
\begin_inset space ~
\end_inset

Item
\begin_inset space ~
\end_inset

Plugins General purpose plugins conveniently placed into the application's
 menu that have access to all internal structures and functionality.
\end_layout

\begin_layout Standard
written in Java programming language around the Standard Widget Toolkit
 
\begin_inset CommandInset citation
LatexCommand cite
key "SWT"

\end_inset

 to provide native look on all supported platforms.
\end_layout

\begin_layout Standard
Implementing the plugins falling into last two categories was required to
 get the required functionality into TuxGuitar.
 The tool item plugin is only useful for providing a simple user interface
 to the system, allowing to tweak alignment settings and to select an audio
 file to import.
 It neither provides an interest for discussion, nor it has been been implemente
d at current stage.
 
\end_layout

\begin_layout Standard
MIDI Sequencer, on the other hand, is the central point of communication
 between the alignment system and the host application and deserves a closer
 attention.
 It is responsible for directly receiving user's playback commands and deliverin
g each note to the selected synthesiser.
 It is therefore the duty of the sequencer to manage timing of the individual
 events heard in the outut.
 In return the application expects from the sequencer the current position
 in the song, which it queries at regular intervals and update visually
 on the staff.
\end_layout

\begin_layout Standard
The task of the replacement sequencer is to mimic the behaviour of a MIDI
 but to also transparently substitute MIDI by audio.
 The class diagram for the the system is presented on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:ClassDia"

\end_inset

.
 The class names are prefixed with 
\emph on
BT
\emph default
,
\emph on
 
\emph default
which stands for Backing Track, the name of the extension.
 Besides some plugin bookkeeping classes not shown on the diagram, 
\emph on
BTSequencer 
\emph default
is the class directly communicating with the playback system of TuxGuitar,
 while 
\emph on
BTToolMenuDialog 
\emph default
is communicating with the user.
 Once the alignment is required, 
\emph on
BTSequencer 
\emph default
requests it from 
\emph on
BTAlignmentManager, 
\emph default
which in turn relies on three class hierachies to perform the alignment
\emph on
.
 
\emph default
The latter correcpond to the three main components of the alignment subsystem
 (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:BlockDia2"

\end_inset

): 
\emph on
BTFeatures, BTDTW 
\emph default
and 
\emph on
BTErrorCorrector
\emph default
.
 
\emph on
BTSequencer 
\emph default
and 
\emph on
BTSettings 
\emph default
are described in more detail below deferring the discussion of other parts
 of the system until their respective sections.
\end_layout

\begin_layout Description
BTSequencer implements TuxGuitar's internal interface 
\emph on
MidiSequencer 
\emph default
which in turn is modelled after the 
\emph on
Sequencer 
\emph default
interface of the Java Sound API
\emph on
.
 
\emph default
It is the central class of the extension.
 It is a quite large class but the main fuctionality can be conceptually
 expressed in the six methods:
\end_layout

\begin_deeper
\begin_layout Itemize
There are
\emph on
 
\emph default
the 
\emph on
start/stop
\emph default
 methods which are quite self explanatory
\end_layout

\begin_layout Itemize
There are also ones that query and update the position within the song.
 The position is expressed in MIDI ticks (the base unit of MIDI timekeeping).
 However, since the position within the song is actually determined as a
 ratio of the tick position to the tick length of the whole song (MIDI ticks
 are not absolute), the values returned are actually expressed in milliseconds
 for simplicity
\end_layout

\begin_layout Itemize
By design, every time the user starts the playback, TuxGuitar supplies the
 complete song to the sequencer through the call to 
\emph on
createSequence.
 
\emph default
The new sequence of MIDI events is then compared to the one received the
 previous time (if any).
 In case there are differences, the alignment may no longer be valid and
 has to be computed again.
\end_layout

\begin_layout Standard
One other property worth noting is that it always keeps the reference to
 a conventional TuxGuitar MIDISequencer (
\emph on
backupSequencer
\emph default
).
 This comes useful for two reasons:
\end_layout

\begin_layout Itemize
The metronome, available in TuxGuitar, is really another MIDI track added
 to the swhich must still be played through a conventional sequencer, unless
 reimplemented
\end_layout

\begin_layout Itemize
The user may wish to temporarily disable the audio backing track and preview
 scores the old way.
 Switching the sequencers through the internal TuxGuitar facilities would
 mean unloading the whole extension, leading to loosing the current alignment
 and the associated state.
 Keeping a backup sequencer ready and initialised makes the switching almost
 intantaneous by transparently redirecting the method calls.
\end_layout

\end_deeper
\begin_layout Description
BTSettings is the class used extensively by almost every other class in
 the system.
 It has been decided to keep the setting for all aspects of alignment, file
 handling and playback centralised.
 This reduces the amount of direct communication between parts of the system
 leading to cleaner and better maitainable code.
 The class offers facilities for updating and retreiving both the user-adjustabl
e and internally used parameters.
 For example, the path to the backing track audio file is set by user through
 the system's user interface, while the 
\emph on
alignmentRequired 
\emph default
flag is only set internally when the underlying song or some settings have
 changed, possibly invalidating the alignment.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
thispagestyle{empty}
\end_layout

\begin_layout Plain Layout


\backslash
begin{minipage}{
\backslash
textwidth}
\end_layout

\begin_layout Plain Layout


\backslash
begin{flushleft}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename images/classdia.eps
	width 100text%

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "fig:ClassDia"

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
figcaption{Class Diagram}
\end_layout

\begin_layout Plain Layout


\backslash
end{flushleft}
\end_layout

\begin_layout Plain Layout


\backslash
end{minipage}
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Inputs Processing
\end_layout

\begin_layout Standard
As discussed in the design section of this document, the score-to-audio
 alignment is performed etirely in the audio domain.
 Therefore the score must first be synthesised to audio.
 Moreover, the internal audio processing is usually done with the audio
 samples converted to the floating point representation with the values
 ranging from -1.0 to 1.0.
 As it will be shown in later sections this data representation is essential
 for feature extraction and audio time scaling.
 Lastly, the file with the backing track selected by the user may be in
 a variety of different audio file formats and encodings which has to be
 accounted for.
\end_layout

\begin_layout Standard
To synthesise audio from MIDI, Gervill library 
\emph on

\begin_inset CommandInset citation
LatexCommand cite
key "Gervill"

\end_inset

 
\emph default
has been chosen for a number of reasons:
\end_layout

\begin_layout Itemize
It is designed to integrate well with Java Sound API, the standard Java
 framework for sampled audio and MIDI
\end_layout

\begin_layout Itemize
It is already distributed with most TuxGuitar packages
\end_layout

\begin_layout Itemize
The tiny size of 224 Kb including an emergency soundbank (version 1.0) allows
 it to be distributed as part of even the smallest packages
\end_layout

\begin_layout Standard
TuxGuitar relies heavily on Java Sound API.
 In fact, one of the two sequencers that come bundled with TuxGuitar simply
 delegates the main processing to the default Java sequencer.
 The framework has been very helpful in the handling of audio.
 It has implicit support for several uncompressed audio file formats such
 as WAVE and is extensible by third parties to support MP3, Vorbis/OGG,
 Flac and other popular compressed formats.
 The conversion is done by the respective classes and is presented to the
 programmer in a convenient 
\emph on
AudioInputStream
\emph default
 class.
 Likewise, the required number of channels, sample rate and encoding to
 be served by 
\emph on
AudioInputStream
\emph default
 (e.g.
 16/24 bit signed/unsigned integers, or 32/64 bit floats 
\begin_inset CommandInset citation
LatexCommand cite
key "PCMFLOAT"

\end_inset

) can be specified through the use of 
\emph on
AudioFormat
\emph default
.
 However, while 
\emph on
AudioInputStream
\emph default
 captures all the coversion details, it still works at a fairly low level.
 In particular:
\end_layout

\begin_layout Itemize
It seves data in byte arrays, which means that the bytes have to be combined
 into the correct primitives by the client programmer
\end_layout

\begin_layout Itemize
The channels are interleaved meaning that the samples from left and right
 (and possibly other) audio channels are stored contiguously.
 This is the way they are expected for playback by Java Sound API, but was
 incompatible with the time scaling framework which expects a separate array
 for each channel.
\end_layout

\begin_layout Itemize
Resetting to an older position within the file or in-memory audio stream
 is not always supported.
 However, this functionality is required in several parts of the system:
\end_layout

\begin_deeper
\begin_layout Itemize
the same audio file is usually read at least twice: during feature extraction
 and during playback
\end_layout

\begin_layout Itemize
the user may wish to revert to an earlier position within the song or enable
 looped playback of some section
\end_layout

\end_deeper
\begin_layout Standard
To accout for these inconveniences the 
\emph on
BTStream
\emph default
 class was introduced to simplify the audio handling through out the extension.
 It allows specifying the desired target format with the data being read
 directly into an array of floating point numbers.
 Additionally it provides functions for deinterleaving and interleaving
 multiple channels, and is guarranteed to be able to reset to the beginning.
\end_layout

\begin_layout Subsection
Spectral Features Extraction
\end_layout

\begin_layout Standard
Calculating spectral features for the the backing track and the synthesised
 score has been implemented in the class 
\emph on
BTSpectrogram
\emph default
.
 The spectrogram is stored internally as a list of float arrays, representing
 a sequence of feature vectors for overlaping window frames.
\end_layout

\begin_layout Standard
\begin_inset listings
lstparams "language=Java"
inline false
status open

\begin_layout Plain Layout

List<float[]> specgram = new LinkedList<float[]>();
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The spectrogram is computed by continuosly reading audio data into a buffer,
 extracting spectral features and adding it to the list of feature vectors.
 Since the windows may be overlapping and going back in the input stream
 is computationally expensive, the overlapping part of the buffer is reused
 from the previous frame.
 The spectral features are found by taking Discrete Fourier Transform and
 taking the absolute value of the resulting complex numbers.
 More presicely, a Fast Fourier Transform implementation for Java 
\begin_inset CommandInset citation
LatexCommand cite
key "LibFFT"

\end_inset

 has been used.
 Fast Fourier Transform, abbreviated as FFT, is a class of efficient algorithms
 for computing Discrete Fourier Transform.
 The following is the extract from the 
\emph on
BTSpectrogram
\emph default
 class that computes the spectrogram.
 
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Java,tabsize=2"
inline false
status open

\begin_layout Plain Layout

void doCompute() {
\end_layout

\begin_layout Plain Layout

	int len = getSettings().getWindowLength();
\end_layout

\begin_layout Plain Layout

	int ov  = getSettings().getWindowOverlap();
\end_layout

\begin_layout Plain Layout

	boolean normalize = getSettings().getNormalizeSpectra();
\end_layout

\begin_layout Plain Layout

	
\end_layout

\begin_layout Plain Layout

	/* error checking and FFT initialisation code skipped */
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

	// stream data will be read into the following buffer
\end_layout

\begin_layout Plain Layout

	float[] buffer = new float[len];
\end_layout

\begin_layout Plain Layout

	// complex number representation for FFT
\end_layout

\begin_layout Plain Layout

	float[] reals  = new float[len];
\end_layout

\begin_layout Plain Layout

	float[] imgs   = new float[len];
\end_layout

\begin_layout Plain Layout

	int cnt = stream.read(buffer, 0, buffer.length);
\end_layout

\begin_layout Plain Layout

	while(cnt != -1) {
\end_layout

\begin_layout Plain Layout

		reals = applyWindow(buffer);  // apply window function
\end_layout

\begin_layout Plain Layout

		fill0(imgs);                  // imaginary parts are all zeroes
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

		fft.doFFT(reals, imgs, /* inverse = */ false);
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

		float[] spectralEnergy = abs(reals, imgs);
\end_layout

\begin_layout Plain Layout

		if(normalize)
\end_layout

\begin_layout Plain Layout

			removeMean(spectralEnergy);
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

		specgram.add(spectralEnergy); // add processed window to spectrogram
\end_layout

\begin_layout Plain Layout

		shiftLeft(buffer, len-ov);    // reuse overlapping part for next win
\end_layout

\begin_layout Plain Layout

		cnt = stream.read(buffer, ov-1, len-ov); // read rest from stream			
\end_layout

\begin_layout Plain Layout

	}		
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The implementation can also normalize the features (frame-by-frame) if the
 corresponding option is enabled in the settings.
 This is done by subtracting the mean of the spectral energy across the
 DFT bins from every bin as follows:
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Java,tabsize=2"
inline false
status open

\begin_layout Plain Layout

void removeMean(float[] vector) {
\end_layout

\begin_layout Plain Layout

	// find mean
\end_layout

\begin_layout Plain Layout

	float sum = 0;
\end_layout

\begin_layout Plain Layout

	for(int i=0; i<vector.length; i++) {
\end_layout

\begin_layout Plain Layout

		sum += vector[i];
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

	float mean = sum / vector.length;
\end_layout

\begin_layout Plain Layout

	// subtract mean
\end_layout

\begin_layout Plain Layout

	for(int i=0; i<vector.length; i++) {
\end_layout

\begin_layout Plain Layout

		vector[i] -= mean;
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The goal of normalisation is to account for the differences in loudness
 of the two recordings.
 It may also include the adjustment of standard deviation of the energy
 but in practice it did not have an impact on the quality of the alignment
 and has been omitted in this implementation.
 
\end_layout

\begin_layout Subsection
Chroma Features Extraction
\end_layout

\begin_layout Standard
Extracting the croma features from audio turned out to be more complicated
 than constructing a spectrogram and involved solving the time-frequency
 resolution issues.
 The chromagram construction proceeds in three steps:
\end_layout

\begin_layout Enumerate
The spectrogram of the audio is constucted as described in the previous
 section
\end_layout

\begin_layout Enumerate
The croma weighting map is computed.
 It assigns each FFT bin to a pitch class
\end_layout

\begin_layout Enumerate
The weighing map is applied to the spectrogram to get sequence of chroma
 vectors
\end_layout

\begin_layout Standard
While chroma weighing map is conceptually a table that maps each FFT bin
 to a pitch class, it does not have a one-to-one correspondence.
 Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:ChromaWM"

\end_inset

 shows one possible chroma weighing map.
 Every two consequent grayscale rectangles on the same row represent an
 octave interval while the sequence of accending rectangles between them
 are the 12 semi-tones on the chromatic scale.
 It can be seen immediately that the rectangles corresponding to the same
 pitch class grow exponentially in width and the corresponding FFT bin number.
 This can be inferred from the fomula expressing the frequency of one note
 in terms of the frequency of another note as follows:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
f=f_{0}\cdot2^{n/N}\text{, where}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $f_{0}$
\end_inset

 is the fundamental (i.e.
 central) frequency of the reference note,
\end_layout

\begin_layout Standard
\begin_inset Formula $n$
\end_inset

 
\begin_inset space ~
\end_inset

is the number of semi-tones the required note is above the reference note
 (can be negative),
\end_layout

\begin_layout Standard
\begin_inset Formula $N$
\end_inset

 is the number of semi-tones in an octave, which equals 12 for chromatic
 scale.
\end_layout

\begin_layout Standard
It follows from the formula that, say, the fundametal frequency 
\begin_inset Formula $f_{A_{5}}=f_{A_{4}}\cdot2^{12/12}\thickapprox880$
\end_inset

 Hz taking 
\begin_inset Formula $f_{A_{4}}$
\end_inset

 to be 440 Hz which is a commonly used value.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/chromawm-2048-8000.png
	width 105text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:ChromaWM"

\end_inset

Chroma weighting map with widow length of 2048 samples at 8 KHz sampling
 rate (left).
 Zoomed in at first 31 bins (right).
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The FFT bins, on the other hand, are evenly distributed beween 0 and the
 sampling frequency.
 That is each been is centred around the frequency
\begin_inset Formula \[
f=f_{s}\cdot\frac{k}{N}\text{, where}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $f_{s}$
\end_inset

 is the samping frequency,
\end_layout

\begin_layout Standard
\begin_inset Formula $N$
\end_inset

 is the FFT window length in samples,
\end_layout

\begin_layout Standard
\begin_inset Formula $k$
\end_inset

 
\begin_inset space ~
\end_inset

is the 0-based index of the bin ranging from 0 to 
\begin_inset Formula $N-1$
\end_inset

.
\end_layout

\begin_layout Standard
Considering the example on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:ChromaWM"

\end_inset

, each FFT bin spans 
\begin_inset Formula $\frac{f_{s}}{N}=\frac{8000}{2048}\approx3.9$
\end_inset

 Hz.
 However, as can be seen from the notes frequencies table in Appendix 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Note-Frequencies"

\end_inset

, the fundamental frequencies of notes below 
\begin_inset Formula $B_{1}$
\end_inset

 are less than 3.9 Hz apart.
 This means that the frequency resolution of FFT with these parameters is
 not enough to uniqely identify the pitch class for lower notes.
 This is expressed graphically by vertical bars spanning more than one semitone
 (FFT bins 8 to 16).
\end_layout

\begin_layout Standard
In the above example the described issues do not pose a problem in practice
 since the consecutive minor second intervals (1 semitone difference) do
 not occur so ofter in music.
 However, the 2048 sample window at sampling rate 8 KHz only allows the
 relolution between 
\begin_inset Formula $^{1}/_{4}$
\end_inset

 and 
\begin_inset Formula $^{1}/_{8}$
\end_inset

 note length, resulting in noticeable misallignments.
 On the other hand, if the window length is lowered to 512 samples (the
 chosen default when aligning based on spectral features), the 
\begin_inset Quotes eld
\end_inset

uncertainty
\begin_inset Quotes erd
\end_inset

 range extends to 
\begin_inset Formula $C\#_{4}$
\end_inset

, well into the dominating playing range of most instruments.
 Additionally, the first two octaves are blured and become practically indisting
uishable (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:ChromaWM-512"

\end_inset

).
 An alternative implementaion has been proposed in 
\begin_inset CommandInset citation
LatexCommand cite
key "ChromaToolbox"

\end_inset

 whereby the signal is resampled to a lower sampling rate before taking
 FFT thus increasing the time-frequency resolution for lower pitches (Table
 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:ChromaTBox"

\end_inset

) but this is left as a possible enhancement.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="3">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $A_{0}-B_{3}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $C_{4}-B_{6}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $C_{7}-C_{8}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
882 Hz
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4410 Hz
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
22050 Hz
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:ChromaTBox"

\end_inset

Variable sampling rate chroma extraction at 22050 Hz sampling rate.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/chromawm-512-8000.png

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:ChromaWM-512"

\end_inset

Chroma weighting map with widow length of 512 samples at 8 KHz sampling
 rate zoomed in at first 18 bins.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
To calculate the chroma weighting map in MATLAB, the following steps have
 been taken by the author:
\end_layout

\begin_layout Enumerate
The central frequency for each FFT bin is determined
\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab"
inline false
status open

\begin_layout Plain Layout

ffthz = (1:nfft-1)/nfft*(Fs/2) % where nfft = window/2+1
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
The semitone differenct between every FFT bin and 
\begin_inset Formula $A_{0}$
\end_inset

 is determined.
 This may, and for most bins will be a decimal number, since the central
 frequency of a bin does not neccessarily align with any note's fundamental
 frequency
\end_layout

\begin_deeper
\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab"
inline false
status open

\begin_layout Plain Layout

fftsemitones = N*log2(ffthz./A0)
\end_layout

\begin_layout Plain Layout

% make up a value for bin 0
\end_layout

\begin_layout Plain Layout

fftsemitones = [fftsemitones(1)-1.5*N,fftsemitones]
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Determine how many semitones every bin spans
\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab"
inline false
status open

\begin_layout Plain Layout

binspan = [max(1, fftsemitones(2:nfft) - fftsemitones(1:nfft-1)), 1]
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Iterate over FFT bins ranging from 
\begin_inset Formula $A_{0}$
\end_inset

 to 
\begin_inset Formula $A_{8}$
\end_inset

 (the actual implementation allows specifying a different range)
\end_layout

\begin_deeper
\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

% find first bin belonging to A0
\end_layout

\begin_layout Plain Layout

fst = find(fftsemitones > -1, 1, 'first')
\end_layout

\begin_layout Plain Layout

% find last bin belonging to A8
\end_layout

\begin_layout Plain Layout

lst = find(fftsemitones < 88, 1, 'last')
\end_layout

\begin_layout Plain Layout

for k = fst:lst
\end_layout

\begin_layout Plain Layout

	% retreive the semitone difference with A0 
\end_layout

\begin_layout Plain Layout

	n = fftsemitones(k);
\end_layout

\begin_layout Plain Layout

	
\end_layout

\begin_layout Plain Layout

	% Notes in higher octaves span more frequencies, penalise them
\end_layout

\begin_layout Plain Layout

	scaling = 1.3^-(n/N); % should be 2.0 but we are generous
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Find the 
\begin_inset Quotes eld
\end_inset

exact
\begin_inset Quotes erd
\end_inset

 notes in the neighbourhood of the current bin (since the current bin is
 most propably somewhere in between two notes).
 Then assign how much weight the current bin has on each of them 
\end_layout

\begin_deeper
\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

	% Each semitone is associated with a Gaussian distribution
\end_layout

\begin_layout Plain Layout

	% That is 2*stddev = 1
\end_layout

\begin_layout Plain Layout

	denom = -2*(1/2)^2;
\end_layout

\begin_layout Plain Layout

	
\end_layout

\begin_layout Plain Layout

	% The note on the left
\end_layout

\begin_layout Plain Layout

	n0 = floor(n);
\end_layout

\begin_layout Plain Layout

	M(mod(n0,N)+1,k) = exp((n-n0)^2/denom)*scaling;
\end_layout

\begin_layout Plain Layout

	
\end_layout

\begin_layout Plain Layout

	% The note on the right
\end_layout

\begin_layout Plain Layout

	n0 = ceil(n);
\end_layout

\begin_layout Plain Layout

	M(mod(n0,N)+1,k) = exp((n-n0)^2/denom)*scaling;
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Or, in case the bin spans more than one semitone (which is the case with
 notes in lower octaves, as discussed), distribute the energy beween the
 notes it spans.
\end_layout

\begin_deeper
\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

	if binspan(k) > 1
\end_layout

\begin_layout Plain Layout

		nlo = fftsemitones(k-1);        % prev bin
\end_layout

\begin_layout Plain Layout

		nlo = min(ceil(nlo), floor(n)); % lowest "exact" note
\end_layout

\begin_layout Plain Layout

		nhi = fftsemitones(k+1);        % next bin
\end_layout

\begin_layout Plain Layout

		nhi = max(ceil(n), floor(nhi)); % highest "exact" note
\end_layout

\begin_layout Plain Layout

		ns  = (nlo:nhi);                % all notes it spans
\end_layout

\begin_layout Plain Layout

		M(mod(ns,N)+1,k) = 1*scaling/length(ns);
\end_layout

\begin_layout Plain Layout

		continue;                       % done with this iteration
\end_layout

\begin_layout Plain Layout

	end
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that above condition is checked before step 5, and, if found to be
 true, is executed instead of it.
\end_layout

\end_deeper
\begin_layout Standard
Once the chroma wigthing map is computed, it may safely be applied to the
 spectrogram via matrix multiplication.
 That is, if the map is a matrix of size 
\begin_inset Formula $(12,nfft)$
\end_inset

 and the spectrogram is a matrix of size 
\begin_inset Formula $(nfft,nframes)$
\end_inset

 their multipication yields a matrix of size 
\begin_inset Formula $(12,nframes)$
\end_inset

, that is a column feature vector for each frame.
 
\begin_inset Formula $nfft$
\end_inset

 in the above is half the window length plus 1 due to the specifics of the
 Fourier Transform.
\end_layout

\begin_layout Subsection
Dynamic Time Warping
\end_layout

\begin_layout Standard
One of the reasons for choosing Dynamic Time Warping to be at core of the
 alignment process was its simplicity and extensibility.
 Indeed it allowed to quickly get a working system and afterwards explore
 the possible ways to optimise for performance.
 This section mostly focuses on the issues that arose and had to be overcome
 when implementing an optimised version of DTW, namely, Path Pruned DTW
 proposed in 
\begin_inset CommandInset citation
LatexCommand cite
key "AttackSustain"

\end_inset

.
 The following is the description of the solution quotion the original authors
 (names of some of the variables were changed to be consistent with the
 rest of the report):
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{quotation}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
To reduce the computation time and the resources needed, at every iteration
 
\begin_inset Formula $i$
\end_inset

, only the best paths are kept, by pruning the paths with an augmented distance
 
\begin_inset Formula $D(i,j)$
\end_inset

 over a threshold 
\begin_inset Formula $\theta_{p}$
\end_inset

.
 This threshold is dynamically set using the minimum of the previous 
\begin_inset Formula $D$
\end_inset

 row.
 After various experiments this threshold was set to: 
\begin_inset Formula \[
\theta_{p}(i)=1.1min(D(i-1))\]

\end_inset

However, the paths between the corridor of selected paths and the diagonal
 are not pruned to leave more possible paths.
 Usually the corridor width is about 400 frames.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{quotation}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Intuitively, the trend in the path movement is determined at every row.
 Since the lowest cost path for the current row may not neccessarily coincide
 with the best path for the complete matrix, other low-cost paths are kept
 too.
 However, the paths that have already accumulated excessive cost are left
 behind the bounds of corridor at the next iteration.
 Thus the potentially best paths at every row are followed by the constraint
 corridor.
 It's worth noting that for many allignments the path formed by the augmented
 cost minimums approximates the final path very closely.
 A sample run of the algorithm is shown on Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Pruned-spellbound"

\end_inset

.
 Only the narrow corridor between the cyan lines is evaluated, which makes
 up about 26% of the matrix in this particualr example.
\end_layout

\begin_layout Standard
Conceptually, there are two cost matrices involved in computing the warping
 path.
 One is the local distance matrix, or similarity matrix, 
\begin_inset Formula $SM$
\end_inset

, with each element 
\begin_inset Formula $SM(i,j)$
\end_inset

 being the measure of similarity between 
\begin_inset Formula $i$
\end_inset

th frame of the audio and 
\begin_inset Formula $j$
\end_inset

th frame of the synthesised score.
 The other is is the augmented distance matrix 
\begin_inset Formula $D$
\end_inset

.
 The latter is filled row-by-row with each element 
\begin_inset Formula $D(i,j)$
\end_inset

 being the total cost of the best path from 
\begin_inset Formula $(1,1)$
\end_inset

 to 
\begin_inset Formula $(i,j)$
\end_inset

.
 In practice the local distance matrix is reused since, as follows from
 Formula 
\begin_inset CommandInset ref
LatexCommand vref
reference "eq:DTW"

\end_inset

, 
\begin_inset Formula $SM(i,j)$
\end_inset

 is only required when calculating 
\begin_inset Formula $D(i,j)$
\end_inset

 and can be overwritten.
 Assuming the working copy of the similarity matrix is named 
\begin_inset Formula $D$
\end_inset

, the core of DTW can be implemented in MATLAB as follows:
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

% First row and column are precomputed to avoid bounds checking
\end_layout

\begin_layout Plain Layout

for i = 2:rows
\end_layout

\begin_layout Plain Layout

	for j = 2:cols
\end_layout

\begin_layout Plain Layout

		D(i,j) = D(i,j) + min([D(i-1,j-1), D(i-1,j), D(i,j-1)]);
\end_layout

\begin_layout Plain Layout

	end
\end_layout

\begin_layout Plain Layout

end
\end_layout

\end_inset


\end_layout

\begin_layout Standard
When the proposed optimisation was implemented, the outer 
\begin_inset Formula $for$
\end_inset

 loop became much more involved though the only modification to the inner
 loop has been the reduced range over which it executes:
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

% First row and column are precomputed to avoid bounds checking
\end_layout

\begin_layout Plain Layout

% Other initialisation code
\end_layout

\begin_layout Plain Layout

for i = 2:rows
\end_layout

\begin_layout Plain Layout

	% Skipped code A...
\end_layout

\begin_layout Plain Layout

	for j = l:r
\end_layout

\begin_layout Plain Layout

		D(i,j) = D(i,j) + min([D(i-1,j-1), D(i-1,j), D(i,j-1)]);
\end_layout

\begin_layout Plain Layout

	end
\end_layout

\begin_layout Plain Layout

	% Skipped code B ...
\end_layout

\begin_layout Plain Layout

end
\end_layout

\end_inset


\end_layout

\begin_layout Standard
According to the original authors, the range 
\begin_inset Formula $l\ldots r$
\end_inset

 for the inner loop is found by pruning the paths over some threshold value
 
\begin_inset Formula $\theta_{p}$
\end_inset

 computed for every row.
 Since 
\begin_inset Formula $\theta_{p}(i)=const\cdot min(D(i-1))$
\end_inset

, the code 
\begin_inset Formula $A$
\end_inset

 may just be setting the threshold to the appropriate value, e.g.:
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

	% Code B
\end_layout

\begin_layout Plain Layout

	thresh = scale_factor * D(i-1,mi); % mi is index of min element
\end_layout

\end_inset


\end_layout

\begin_layout Standard
After the inner loop has executed, it is only required to find the first
 and the last cells of the current row which have the values below the theshold.
 The code stub 
\begin_inset Formula $B$
\end_inset

 may look similar to the following:
\end_layout

\begin_layout Standard
\paragraph_spacing single
\begin_inset listings
lstparams "basicstyle={\ttfamily},language=Matlab,tabsize=2"
inline false
status open

\begin_layout Plain Layout

	% Code C attempt
\end_layout

\begin_layout Plain Layout

	cells = D(i,(l:r));             % augmented cost in (l:r)
\end_layout

\begin_layout Plain Layout

	okcells = find(cells < thresh); % indices of cells with augm.
 cost
\end_layout

\begin_layout Plain Layout

	                                % below threshold
\end_layout

\begin_layout Plain Layout

	[~,mi] = min(cells);            % lowest cost path of this row
\end_layout

\begin_layout Plain Layout

	mi = l-1+mi;                    % make index rel to column 1,
\end_layout

\begin_layout Plain Layout

	                                % not to left bound
\end_layout

\begin_layout Plain Layout

	% determine new boundaries for next row
\end_layout

\begin_layout Plain Layout

	r = l-1+okcells(end);           % take the last below threshold
\end_layout

\begin_layout Plain Layout

	l = l-1+okcells(1);             % take the first below threshold
\end_layout

\end_inset


\end_layout

\begin_layout Standard
This code has been modelled following the original description of the algorithm.
 However, upon running the presented code with the same parameters as before,
 the corridor tends to diverge sharply upwards (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:FailedPruned-spellbound"

\end_inset

).
 This is, indeed explainable, since there is no constraints on the general
 direction of the corridor, except that it has to follows the absolute minimums.
 But going across the colums will almost always accumutate more cost than
 going vertically upwards, hence the white line is rapidly accending.
\end_layout

\begin_layout Standard
To rectify this issue, the augmented costs 
\begin_inset Formula $D(i,j)\vert j\in[l,r]$
\end_inset

 of the current row 
\begin_inset Formula $i$
\end_inset

 are scaled by the ratio 
\begin_inset Formula $\sqrt{i^{2}+(\frac{cols}{2})^{2}}/\sqrt{i^{2}+j^{2}}$
\end_inset

, that is the ratio of the linear distances from 
\begin_inset Formula $(1,1)$
\end_inset

 to the 
\begin_inset Formula $i$
\end_inset

th row's mid point and 
\begin_inset Formula $(i,j)$
\end_inset

 respectively (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Weighting"

\end_inset

).
 The matrix cells are not updated with the weighted values, instead, the
 minimum value and the bounds for the next row are determined from them.
 Likewise, the threshold is also scaled by 
\begin_inset Formula $\sqrt{i^{2}+(\frac{cols}{2})^{2}}/\sqrt{i^{2}+mi^{2}}$
\end_inset

 before being applied, where 
\begin_inset Formula $mi$
\end_inset

 is the column that contained the weighted minimum value of the previous
 row.
\end_layout

\begin_layout Standard
The two features that have been added to the algorithm to make it more flexible
 and robust are listed below.
\end_layout

\begin_layout Enumerate
It is able to precalculate the specified number of rows in full without
 pruning.
 It may be useful in the cases where it is not possible to adequately form
 a 
\begin_inset Quotes eld
\end_inset

trend
\begin_inset Quotes erd
\end_inset

 for the path until several seconds into the music.
 Additionally it is crutial to be past the silence or other non-musical
 content like metronome precounts commonly found in backing tracks.
 It can be seen from the figures that the white path 
\begin_inset Quotes eld
\end_inset

trend
\begin_inset Quotes erd
\end_inset

 estimate is not very well decided until frame ________ into the audio and
 jums from one value to another, justifying the expence of precalculating
 the rows.
\end_layout

\begin_layout Enumerate
The user may specify the minimum width of the corridor that has be maintained
 throughout the run of the algorithm.
 In case the estimated boundaries are narrower than the specified width
 are force extended.
 Figure _____ presents the alignment of Bethoven's 5th symphony 1st movement
 where the audio recording had the intro repeaded twice and therefore the
 green warping path is vertical.
 The white path of minimums at every row, on the other hand, is significantly
 off to the right in that region (although almost exactly coincides with
 the warping path outside the region in question).
 It can be seen that the final warping path is very close to the left boundary.
 The minimum corridor with has been set to ________ for this particular
 alignment.
 Therefore, for some alignments it may be very important to set this parameter
 to a higher value.
\end_layout

\begin_layout Standard
In a potential improvement both of the above parameters may be set dynamically
 by a heuristic based on the amount of scatter in the estimate path.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/prunned-mscs-spellbound.png
	lyxscale 70

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Pruned-spellbound"

\end_inset

Path pruned DTW with left and right constraints in cyan and weighted minimums
 in white.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/prunned-mscs-spellbound-unweighted.png
	lyxscale 70

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:FailedPruned-spellbound"

\end_inset

Incorrectly Path Pruned DTW due to lack of weighting across columns.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/weighting.svg
	lyxscale 50
	width 100text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Weighting"

\end_inset

Augmented distance weighting
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename images/prunned-5th-corr200.png

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:pruned-5th-corr200"

\end_inset

Path Pruned DTW applied with ___ frames minimum corridor width
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Output Generation
\end_layout

\begin_layout Standard
The next stage after the DTW algnment is the error correction.
 The implementation very closely follows the pseudo code Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:ECC"

\end_inset

 presented in the design section of this report.
 However, it includes additional code dealing with cases when the line is
 vertical and therefore the slope is infinite.
 This is a purely an implementation issue, so the discussion moves on to
 interpreting the results of the alignment and error correction to generate
 output.
\end_layout

\begin_layout Standard
By requirements, there are two outputs generated by the system: 
\end_layout

\begin_layout Enumerate
the alignment map between the provided audio and the synthesised score,
 and
\end_layout

\begin_layout Enumerate
the time scale modified audio that is stretched or contracted between appropriat
e points to be sound sync with the score.
\end_layout

\begin_layout Standard
The alignment map is ultimately a file which contains the key alignment
 points between the imported audio recording and the MIDI score.
 At the implementation level for each key point the file contains its millisecon
d position in the audio recording and the new position where it should be
 to be in sync with the score.
 These millisecond positions are available with little extra work from the
 outputs of the error correction algorithm.
 As it has been discussed in the respective section, it automatically detemines
 the feature frames, such that the time saling ratio is constant.
 between which the 
\end_layout

\begin_layout Subsection
Tempo Aligned Score
\end_layout

\begin_layout Standard
When the scores would be played back, the audio track will play in sync
 with the visual representation of the score.
 Up until now only the case when audio is timescale modified to fit the
 tempo of the score was considered.
 One option that will be offered to the user if the time permits, would
 be the in versed behavior.
 The audio will play unmodified while the visual representation of the score
 would sync to it.
 This would mean the new tempo would be assigned in the parts of the score
 where it's necessary.
 It is also required, as in the case with audio, to determine longer sections
 with constant tempo.
 It is justified because otherwise vertical steps in the path would mean
 0 tempo while horizontal steps - an infinitely large tempo.
\end_layout

\begin_layout Standard
While it is unlikely that direct MIDI file manipulation will be necessary,
 it is probable that TuxGuitar score representation is similar to that of
 MIDI.
 Standard MIDI stores the tempo change information in events just like everythin
g else.
 The base unit of MIDI timekeeping is a tick.
 Each MIDI file keeps the value of ticks per quarter note and this value
 is constant for the whole file.
 The actual tempo change meta event can occur at anytime and is defined
 as microseconds per quarter note.
 Converting between samples of audio and MIDI ticks is therefore possible
 using these two values.
\end_layout

\begin_layout Subsection
Planning
\end_layout

\begin_layout Standard
The section has covered the techniques and technologies of the methods that
 will be used to fulfill the requirements of the proposed system.
 Table 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:TaskList"

\end_inset

 is the summary of the expected functionality for both the prototypes.
 Any external frameworks or interfacing are listed per task.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
definecolor{lightgray}{gray}{0.8}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
statnotreq}{
\backslash
cellcolor{lightgray} Not required}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
statdef}   {
\backslash
cellcolor{white}     Deferred}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
statinprog}{
\backslash
cellcolor{yellow}    In progress}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
statdone}  {
\backslash
cellcolor{green}     Completed}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float table
placement h
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="13" columns="5">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Task class
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Task
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
MATLAB
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
TuxGuitar
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ext.
 Framework
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Inputs processing
\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Import audio
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Java Sound API
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Synthesise MIDI
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statnotreq
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gervill 
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Feature extraction
\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Spectrograms
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
FFT 
\begin_inset CommandInset citation
LatexCommand cite
key "LibFFT"

\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Chromagrams
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdef
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Alignment
\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
DTW
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdef
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
DTW w/path pruning
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdef
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Output processing
\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Error correction
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdef
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Tempo map generation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statnotreq
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Audio time scaling
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
librubberband
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Output generation
\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Audible
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statnotreq
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Java Sound API
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
User controlled playback
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statnotreq
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statinprog
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Java Sound API
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="left" valignment="top" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
GUI / Visual
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdone
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
statdef
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
SWT
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:TaskList"

\end_inset

Project task list
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
A preliminary project plan is presented below.
 In green are the tasks requiring interfacing third-party frameworks and
 TuxGuitar's internal functionality.
 In yellow are the core algorithms, mostly ported from the prototype.
 Non-programming tasks are presented in blue with deadlines in red.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
Results
\end_layout

\begin_layout Standard
This section presents a preliminary evaluation and testing schema for the
 project.
 Some informal evaluation of the prototype in its current state will be
 presented along the way.
\end_layout

\begin_layout Subsection
Evaluation Criteria
\end_layout

\begin_layout Standard
By design the system offers several alternative implementations for each
 subsystem:
\end_layout

\begin_layout Enumerate
Feature extraction subsystem
\end_layout

\begin_deeper
\begin_layout Enumerate
Scores can be converted to either a polyinstrumental or a monoinstrumental
 audio
\end_layout

\begin_layout Enumerate
Spectrograms or chromagrams can be chosen as audio features.
\end_layout

\end_deeper
\begin_layout Enumerate
Alignment subsystem - two possible DTW optimisations were proposed.
\end_layout

\begin_layout Enumerate
Segmentation subsystem - audio can be synchronised to scores or vice versa.
\end_layout

\begin_layout Standard
Automatic evaluation of the alignment results is currently an open problem.
 There is no database with manually labelled or synchronised data either
 (although there are works specifically working towards that 
\begin_inset CommandInset citation
LatexCommand cite
key "LabROSA"

\end_inset

).
 It is therefore not possible to tell with a high probability whether the
 alignment is correct.
 Most of the evaluation will be done by sonification.
 In fact, alternative implementations were provided to compare them to each
 other in a statistical manner.
 Most likely, the evaluation would involve human resources and be carried
 out on music pieces that they are familiar with.
 A marking sheet will be provided to the testers.
 Each musical piece will be evaluated five times with the following configuratio
ns:
\end_layout

\begin_layout Enumerate
Polyphonic audio / Spectrogram audio feature / Path pruning DTW
\end_layout

\begin_layout Enumerate
Monophonic audio / Spectrogram audio feature / Path pruning DTW
\end_layout

\begin_layout Enumerate
Polyphonic audio / Chromagram audio feature / Path pruning DTW
\end_layout

\begin_layout Enumerate
Monophonic audio / Chromagram audio feature / Path pruning DTW
\end_layout

\begin_layout Enumerate
-- best of the above -- / Pseudo Real-Time Data Abstraction DTW
\end_layout

\begin_layout Standard
Alignments with problem will be reevaluated using the prototype to determine
 the exact problems and possible solutions.
\end_layout

\begin_layout Standard
At the same time, erroneous scores and audio files will be prepared.
 The following properties of the system will be evaluated:
\end_layout

\begin_layout Enumerate
Ability to skip missing sections in either score or audio
\end_layout

\begin_layout Enumerate
Ability to recover from incorrectly transcribed notes
\end_layout

\begin_layout Enumerate
Silence handling
\end_layout

\begin_layout Enumerate
Live performances speed-ups and slow-downs handling
\end_layout

\begin_layout Enumerate
Ability to align audio and MIDI with tracks missing from either
\end_layout

\begin_layout Standard
The comparison between spectrogram and chromagram feature performance will
 also be done by recording average distance along the best path.
 The two performance optimised DTW algorithms will be validated against
 ordinary DTW to judge on the optimality of the returned best paths.
\end_layout

\begin_layout Subsection
Preliminary Evaluation 
\end_layout

\begin_layout Standard
Some tests were conducted on the prototype in its current state.
 The audio features used in all cases were spectrograms calculated with
 a Hann window of length 256 samples and a 25% overlap.
 Both audio were downsampled to 8 KHz.
\end_layout

\begin_layout Standard
The first example presents an artificially speeded up version of a drum
 loop aligned with itself (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:DTW-Eval"

\end_inset

a).
 A continuous speed up can be clearly seen by the skewed checker pattern.
 DTW managed to correctly find the bending path.
 It took DTW 1.33 seconds to perform the alignment on two audio of length
 10 and 6 seconds.
\end_layout

\begin_layout Standard
The second example is also of an experiment nature.
 It presents an extract from a song in which one channel was subtracted
 from the other, thus leaving the vocals behind.
 When it was aligned to the original, DTW managed to find the path correctly
 (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:DTW-Eval"

\end_inset

b).
\end_layout

\begin_layout Standard
The last example presents a song with was aligned to an audio generated
 from MIDI.
 The MIDI file did not completely correspond to the audio.
 It can be seen by horizontal lines that there was extra section present
 (Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:DTW-Eval"

\end_inset

c).
 One vertical bar also denotes untranscribed measures.
 The overall quality of the alignment was good but took 684 seconds
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
a.
 
\begin_inset Graphics
	filename images/drumloop.eps
	width 33text%

\end_inset

 b.
 
\begin_inset Graphics
	filename images/BSSM.png
	width 33text%

\end_inset


\end_layout

\begin_layout Plain Layout
\align center
c.
\begin_inset Graphics
	filename images/IDE.png
	width 66text%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:DTW-Eval"

\end_inset

DTW Alignment of audio with a) time compressed audio b) music without vocals
 c) audio generated from midi with incorrect song structure
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
Conclusion
\end_layout

\begin_layout Standard
The document has presented a proposal a score-to-audio alignment system.
 First the literature overview was presented offering several option to
 choose from while leaving room for new proposals.
 The subsystems were then described in detail, explaining the design decisions.
 Most of the functionality is duplicated by alternative implementations
 to aid evaluation by comparison and offering more options to choose from
 in the end.
 
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "LabROSA"

\end_inset

Turetsky, R., Ellis, D..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph on
 Ground-Truth Transcription of Real Music from Force-Aligned MIDI Syntheses
\emph default
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Columbia University, 2003.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Compare3"

\end_inset

Niedermayer, B..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Improving Accuracy of Polyphonic Music-To-Score Alignment.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Proceedings of the 10th International Society for Music Information Retrieval
 Conference, 2009.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Piano"

\end_inset

Müller, M., Kurth, F., Röder, T..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Towards an Efficient Algorithm For Automatic Score-To-Audio Synchronisation.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Universität Bonn, 2004.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "AttackSustain"

\end_inset

Soulez, F., Rodet, X., Schwarz, D..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph on
 Improving Polyphonic and Poly-Instrumental Music to Score Alignment.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Institut de Recherche et Coordination Acoustique/Musique, 2003.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Chroma+Compare3"

\end_inset

Hu, N., Dannenberg, R., Tzanetakis, G..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Polyphonic Audio Matching and Alignment for Music Retrieval.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Proceedings of the 2003 IEEE Workshop on Applications of Signal Processing
 to Audio and Acoustics.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "AudioEditors"

\end_inset

Hu, N., Dannenberg, R..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Polyphonic Audio Matching for Score Following and Audio Editors.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Proceedings of the 2003 IEEE Workshop on Applications of Signal Processing
 to Audio and Acoustics.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "HMM"

\end_inset

Devaney, J., Mandel, M., Ellis, D..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Improving MIDI-Audio Alignment With Acoustic Features.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Proceedings of the 2009 IEEE Workshop on Applications of Signal Processing
 to Audio and Acoustics.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "FastDTW"

\end_inset

Salvador, S., Chan, P..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph default
Florida Institute of Technology, 2007.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Ney"

\end_inset

Ney, H..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
The Use of a One-Stage Dynamic Programming Algorithm for Connected Word
 Recognition.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Proceedings of the 1984 IEEE Transactions on Acoustics, Speech, and Signal
 Processing, VOL.
 ASSP-32, No.
 2.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Robot"

\end_inset

Otsuka, T., Murata, K., Nakadai, K., Takahashi, T., Komatani, K., Ogata,.
 T., Okuno, H.
 G..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Incremental Polyphonic Audio to Score Alignment using Beat Tracking for
 Singer Robots.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph default
 Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent
 Robots and Systems, pp.
 2289-2296.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "ChromaClassification"

\end_inset

Ellis, D..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph on
 Classifying Music Audio with Timbral and Chroma Features.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph default
 Columbia University, 2007.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "ChromaToolbox"

\end_inset

Müller, M..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Information Retrieval for Music and Motion
\emph default
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Springer, 2007.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Stanford"

\end_inset

Salmutter, E..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Synchronizing Audio and Video.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset


\emph on
 
\emph default
[Online].
 Available: http://www.televisions.com/tv-articles/Synchronizing-Audio-and-Video.ph
p, Apr.
 12, 2009 [Oct.
 15, 2010].
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "LocalReg"

\end_inset

Cleveland, W.S., Devlin, S.J..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Locally-Weighted Regression: An Approach to Regression Analysis by Local
 Fitting
\emph default
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Journal of the American Statistical Association 83 (403), pp.
 596–610, 1988.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "MARS"

\end_inset

Friedman, J.
 H..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Multivariate Adaptive Regression Splines
\emph default
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Annals of Statistics 19 (1), p.p.
 1–67, 1991.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "TuxGuitar"

\end_inset


\emph on
TuxGuitar 
\emph default
version 1.2
\emph on
.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Herac Modern Solutions.
 2009
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "KGuitar"

\end_inset

Mikhail Yakshin
\emph on
, 
\emph default
Wilane Ousmane
\emph on
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 KGuitar
\emph default
 version 0.5.1.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 [Online].
 Available: http://kguitar.sourceforge.net, Jan.
 16, 2008 [Oct.
 15, 2010].
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "SWT"

\end_inset


\emph on
The Standard Widget Toolkit
\emph default
 version 3.5.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 The Eclipse Foundation.
 2010.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Matlab"

\end_inset


\emph on
MATLAB 
\emph default
version 7
\emph on
.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph default
Natick, Massachusetts: The MathWorks Inc., 2009.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "LibFFT"

\end_inset

Lindley C.A..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Java FFT Implementation 
\emph default
version as of Feb.
 27, 1999
\emph on
.

\emph default
 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 [Online].
 Available: ftp://ftp.prenhall.com/pub/ptr/professional_computer_science.w-022/digi
tal_audio, Apr.
 3, 2000 [Aug.
 25, 2010].
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "PCMFLOAT"

\end_inset

Robledo M..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Float Encoding SPI for Java Sound API.
\emph default

\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 [Online].
 Available: http://www.groovemanager.com/manudiplom/CDRom/Quellcode/Java,
 Feb.
 2, 2005 [Aug.
 16, 2010].
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Gervill"

\end_inset

Helgason K..
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 
\emph on
Gervill 
\emph default
version 1.0.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 [Online].
 Available: https://gervill.dev.java.net [Aug.
 16, 2010]
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "RubberBand"

\end_inset


\emph on
Rubber Band Library 
\emph default
version 1.5.
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
newblock
\end_layout

\end_inset

 Breakfast Quay, 2010.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
appendix
\end_layout

\end_inset


\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Note-Frequencies"

\end_inset

Frequencies of Musical Notes
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
definecolor{gtrcolor} {RGB}{20  210 0}
\end_layout

\begin_layout Plain Layout


\backslash
definecolor{basscolor}{RGB}{220 220 0}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
gtr}[1]{
\backslash
cellcolor{gtrcolor}$^{#1}$}
\end_layout

\begin_layout Plain Layout


\backslash
newcommand{
\backslash
bass}[1]{
\backslash
cellcolor{basscolor}$^{#1}$}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\align left

\lang british
\begin_inset Tabular
<lyxtabular version="3" rows="11" columns="14">
<features>
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="left" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
P
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

i
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

t
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

c
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

h
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

C
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

l
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

a
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

s
\begin_inset space ~
\end_inset


\begin_inset space ~
\end_inset

s
\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell multicolumn="2" alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
C
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
C#
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
D 
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
Eb
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
E
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
F 
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
F#
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
G
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
G# 
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
A
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
Bb
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
B
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
o
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
27.50
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
29.14
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
30.87
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
n
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
32.70
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
34.65
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
36.71
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
38.89
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
41.20
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
bass{4}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
43.65
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
46.25
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
49.00
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
51.91
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
55.00
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
bass{3}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
58.27
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
61.74
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
65.41
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
69.30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
73.42
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
bass{2}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
77.78
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
82.41
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{6}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
87.31
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
92.50
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
98.00
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
bass{1}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
103.8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
110.0
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{5}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
116.5
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
123.5
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
e
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
130.8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
138.6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
146.8
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{4}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
155.6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
164.8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
174.6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
185.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
196.0
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{3}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
207.7
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
220.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
233.1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
246.9
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{2}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
v
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
4
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
261.6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
277.2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
293.7
\begin_inset Formula $ $
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
311.1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
329.6
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
gtr{1}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
349.2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
370.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
392.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
415.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
440.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
466.2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
493.9
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
5
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
523.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
554.4
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
587.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
622.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
659.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
698.5
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
740.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
784.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
830.6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
880.0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
932.3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
987.8
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
t
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1047
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1109
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1175
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1245
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1319
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1397
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1480
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1568
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1661
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1760
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1865
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
1976
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
c
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
7
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2093
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2217
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2349
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2489
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2637
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2794
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
2960
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
3136
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
3322
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
3520
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
3729
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
3951
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" bottomline="true" leftline="true" rotate="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
O
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\series bold
\lang british
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\lang british
4186
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Standard pitch: 
\begin_inset Formula $A_{4}=440$
\end_inset

 Hz.
\end_layout

\begin_layout Standard
Piano playing range: 
\begin_inset Formula $A_{0}-C_{8}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
tikz 
\backslash
fill[gtrcolor] (0.8ex,0.8ex) circle (0.8ex);
\end_layout

\end_inset

 6-string guitar open string notes.
 Playing range (24 frets): 
\begin_inset Formula $E_{2}-E_{6}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
tikz 
\backslash
fill[basscolor] (0.8ex,0.8ex) circle (0.8ex);
\end_layout

\end_inset

 4-string bass guitar open string notes.
 Playing range (24 frets): 
\begin_inset Formula $E_{1}-G_{4}$
\end_inset

.
\end_layout

\begin_layout Standard
Standrard tuning assumed on all instruments.
\end_layout

\end_body
\end_document