midimatcher.tcl

Midimatcher is a tool for analyzing a large collection of musical works by one or more composers. The program identifies musical fragments in the melody line that recur. The program contains a convenient graphical user interface, for searching for such repeating patterns and listening to them either in isolation or in its context.

Introduction

Music can be parsed into phrases corresponding to places where the musician would catch his breath. These phrases end with cadences, a form of punctuation, which are linked to the tonality of the piece. A cadence indicates the end of an idea and may either suggest that more may follow or bring the part to a close. Phrases can be grouped to form larger sections. Unlike languages, music does not provide semantic meaning; instead it attempts to communicate an emotion. Though individual notes may correspond to the letters of an alphabet, there is nothing that corresponds to the words of a language.

A composer tends to use peculiar expressions in his various works and these represent his trademark. When examining the works of a composer with a large output, one often has the feeling of deja vu and is wondering whether the composer has either consciously or unconsciously used the same expressions elsewhere. For example, D. Scarlatti's composed a collection of 555 sonatas in the last few years of his life. This represents about 50 hours of music, so it is rather difficult to identifiy idiomatic expressions without the assistance of a computer. Applications of this program for analyzing such collections is illustrated in the separate web page referenced here.

Much of the research dealing with the extraction of the semantic content of music, either from raw audio files or from MIDI files, can be found in the conference notes of the Music Information Retrieval Symposium. Though much music is available in mp3 files, the technology for extracting useful information from this data is still limited. Most music is highly polyphonic, having rich harmony. Finding the main melody line is a challenging task.

Midimatcher uses a fairly unsophistocated melody extraction and melody matching algorithm. First it assumes that the user knows which MIDI track contains the melody line. When more than one note is playing at a time on that track, midimatcher assumes that the melody notes are the ones with the highest pitch. The matching algorithm takes two music fragments containing an equal number of notes and compares their pitch interval sequences. Differences in tempo, transposition and rhythm are all ignored. If the mismatch error is smaller than a threshold, then these two fragments are considered to be similar. Given a particular fragment, the program searches for all other occurrences of similar sequences in the collection of musical compositions.

MIDI file structure

For those readers who are unfamiliar with the MIDI representation, a MIDI file can be viewed as a piano roll. The file indicates the musical pitch, onset time and length of each note. Pitches are indicated by numbers ranging between 0 and 127, where middle C has a value of 60 and the numbers are in units of semitones. Onset times are indicated by MIDI pulse units which are related to real time by the MIDI tempo command. The MIDI format indicates how many pulses form a quarter note beat; however, this information is not required by the synthesizer and may not be reliable.

Historically MIDI files consisted of just a single track where individual musical instruments were separated into channels. The MIDI standard later evolved into multitracks where the different music voices would be separated into tracks. If the music for one instrument is complex, the individual lines may also be split up into several tracks. For example, the left and right hand of piano music may be split into two tracks.

MIDI files are created in one of two ways. If the person is an accomplished performer, the MIDI instrument acts like a tape recorder, storing every keystroke of the musician. This format maintains most of the nuances of the performance, in particular if the MIDI instrument is able to record the loudness level of every note. However, it is difficult to convert these files into readable music notation.

Other MIDI files are created directly from a music notation program where the user enters the music from a score one note at a time. The advantage of such a system is that the user does not need to be an accomplished performer but only needs to know the rudiments of music. There are many musical notation programs and the MIDI file is the common medium of moving files between programs. The music produced by such programs sounds rather mechanical unless an effort is made to include the dynamics. MIDI files of this type are easy to convert back to sheet music.

Program description

The graphical user's interface is written in a scripting language called Tcl/Tk, which has been around for many years. Like Java, it runs on many different operating systems where this interpreter has been installed. Tcl/Tk is commonly installed on Unix and Linux operating systems. The helper programs, were written in generic C so that they can be compiled from sources on many operating systems. If you are running Windows, compiled programs, as well as midimatcher with tcl/tk already built in are available.

User's guide

There is also the collection of Bach's chorales that can be found on the site The Bach Chorales.

For ragtime and other piano roll collections in MIDI form, see Terrence Smythe's archive. Other large collections can be found on the Classical Archive site, The Classical Archive but a subscription is required to download any files.

If you find any other interesting free collections that can be downloaded in one zip file, please send me an e-mail.

If you are trying out the program for the first time, I recommend you stick with Scarlatti's sonatas on John Sankey's site, since all the MIDI files are uniform in format and all the music is in track 1.

To avoid long folder path names, it is recommended that these folders of files be read directly off the C: drive; however, the program should be able to handle long path names that may contain embedded spaces.

If you are running Windows, I recommend using Winamp (e.g. http://winamp.com) for your MIDI player. For other operating systems, TiMidity is a very good MIDI synthesizer. For operating systems other than Windows, you will need a C compiler and tcl/tk 8.4 or higher installed on the system.

Operating Instructions

Click on the configure button in order to open the configuration window shown below.

Click on the menu button primary database appearing on the top left and select add database. This will pop up a new window shown below.

Using the browse button, select the folder containing the MIDI files and click open. The path name to this folder should now appear in the adjoining entry box. At this point, you need to indicate which track contains the melody line. If some of the MIDI files do not consistently contain the melody line in the same track, there is a way around this. In multitrack MIDI files the melody line is usually but not always in track 2. If it is a single track MIDI file, then you should select track 1. At this point click on the button create database and there should be a short pause while the program scans all the MIDI files and creates a database file called midibase.bin in the folder containing all the MIDI files. This file may be several megabytes, as it contains the top line of every MIDI file. The program also creates two other files in the same folder, midibase.log and refmap.dat. Neither of these files are essential to the program but they contain useful information.

When you click the create database button, midimatcher runs the program midibase, which scans all the MIDI files in the folder and creates the above three files. The midibase.log is a log file that reports any problems the program encounters. For example, the program may not find any notes for a particular track. An example of a portion of the midibase.log is shown below.

0 BWV772.MID 1 308 notes 83.037758 seconds 166.075516 beats
1 BWV773.MID 1 408 notes 98.338539 seconds 196.677078 beats
2 BWV774.MID 1 328 notes 87.696617 seconds 175.393234 beats
3 BWV775.MID 1 340 notes 68.809898 seconds 137.619797 beats
4 BWV776.MID 1 460 notes 117.652344 seconds 235.304688 beats
5 BWV777.MID 1 326 notes 98.182289 seconds 196.364578 beats
6 BWV778.MID 1 393 notes 90.243492 seconds 180.486984 beats

The program midibase provides an option of using a file list for creating the database file providing an additional level of flexibility. For example, you may not wish to include all the MIDI files in the folder or you may wish to use other track numbers for some MIDI files. If you wish to use a file list you must provide it in a particular format and name it refindex.dat. The file is placed in the same directory as your MIDI files. An example of such a file appears below.

0       BWV772.MID      Two-part invention 1
1       BWV773.MID      Two-part invention 2
2       BWV774.MID      Two-part invention 3
3       BWV775.MID      Two-part invention 4
4       BWV776.MID      Two-part invention 5
5       BWV777.MID      Two-part invention 6

To save you some trouble in creating the refindex.dat file, midibase will create a file called refmap.dat. To create the refindex.dat file, copy refmap.dat to refindex.dat and add the additional information using a text editor. To use this file, you must check the box use file list in the newdatabase window.

If you have several MIDI folders, you can create a database file for each folder in the same manner. Midimatcher will remember where to find these database files and will associate them with the primary and secondary database menu buttons in the configuration window. The information is stored in an initialization file called midimatch.ini, which is a text file that you can modify using any editor.

Because the programs Midibase and midimatch5 do not use dynamic allocation there are several built-in limits.
The MIDI file name should be less than 20 ASCII characters.
Only the first 5000 melody notes can be stored.
Only 600 MIDI files can be processed.
The length of a matching segment should not be larger than 50 notes.
If these limitations are too restrictive, you will need to modify and recompile the source code.

At this point, you are ready to use the program. When you click on the menu button primary database, a list of database folders are presented. Clicking on one of the folders will automatically display the fileselection window shown below.

Selecting one of the files will cause the program to display a graph of the notes of the top line in a scrollable canvas.

The notes appear as horizontal bars whose pitch is determined by their height. Pitch is indicated in MIDI pitch units, where middle C is 60 and each octave is 12 MIDI units wide. This is quite similar to a piano roll. Time is indicated in either second units or beat units. Each note, appearing as a horizontal bar, is mouse sensitive. If the mouse pointer, brushes over a particular note, a note index number will be displayed at lower left hand corner just below the horizontal scroll bar. The note index is not essential for operating the program but is used for identifying problems with this program.

The actual music may be very rich in harmony, as shown in in the following graph for the same MIDI file.

The matching program has no way of handling the complex harmony but only considers the highest pitched notes, which form the topline shown in the previous image.

At this point, you should also set the secondary database to the same one used as the primary database. When the program searches for matches corresponding to a displayed segment in the primary database, it will search the files referenced in the secondary database. (It is allowable to have the primary and secondary database reference the same folder.)

Temporal units are either in seconds or beats. Beats are usually in units of quarter notes specified in the header of the MIDI file and allow the user to relate the MIDI file to the score. Note that the MIDI file standard does not provide a means of indicating repeat marks, so all repeats are expanded in the MIDI file. Some of the earlier MIDI files do not attempt to separate the notes into beats and the beat indication is the header block is only a rough approximation. For those MIDI files you may prefer to use units of real time indicated in seconds. The radio buttons use beats and use seconds allow you to choose which units to use. There may be some differences in how the program extracts the MIDI segment when it plays it on the MIDI player.

If you click on any note (horizontal bar) displayed on the top line, the program will create a music segment consisting of several notes beginning with that note. It will play the segment on the MIDI synthesizer and it will list any matching segments it finds in the secondary database in a listbox that will appear below. (The audio output may have an extra or missing note. The program tries to find the segment in the MIDI file and produce a new MIDI file with just that segment. Because of small timing inaccuracies, the extracted segment may not be exactly correct.) In many cases, the program may not find any matches, in which case the listbox will be empty.

The listbox on the left lists the names of the MIDI files where the matches occur and the start time of the matching segment. If you select any item in the listbox, the program will play this selection and display more information in the frame to the right of the listbox. The position of the matching segments is indicated in second units or beat units. Several buttons and a scale slider allow you to listen to these fragments embedded in their musical context. If you click on the button labeled matcher, you will hear the reference fragment surrounded by several seconds of musical context. The amount of context in seconds or beats can be adjusted by the slider on the right. Similarly, clicking the button labeled matchee plays the corresponding fragment in the matched pair.

To the left of the slider there is another button labeled annotate. Clicking this button pops up a text window describing the characteristic of the match. The window was designed to assist you in documenting the match. You may add any text to this window, and when you are done you can select all of the text and place it onto your clipboard using the Cntl-c keystroke. You can then import this information into any word processor or text editor. The button at the bottom labeled save midis will save the matching segments into separate MIDI files in a folder called midisaves, which will be found in the same directory where this program was executed. The slider to the right of this button controls the amount of contextual information surrounding this match.

The button labeled view contours displays a graph of the matched contours. The matching algorithm does not consider the length of the notes, so parts of the contour may exhibit "rubber sheet stretching". This graph was used to check the integrity of the program when differences of rhythm conceal the tonal similarities of the top line of the music.

You will also see a list of the notes indicated in MIDI pitch units in an entry box immediately above the right listbox. Besides that entry box, there is another box listing the notes in music notation. If you wish, you can modify the notes in the left entry box and perform a search for the new segment, either by entering a return or clicking the button labeled match on the right. This allows you to search for your own pattern. (The searching algorithm only considers the intervals between the notes rather than the notes itself; however, it is more convenient to specify the actual notes.)

Searching for matches by clicking on random notes on the topline graph is rather inefficient and in many cases, you may not find any matches. This happens more frequently when you are comparing databases corresponding to different composers. Clicking the find button on the top of the main window will get you another tool called findconfig, which allows you to look for matches more efficiently. Run this tool by clicking on the button labeled search.

The program will scan this file note by note searching for any matches in the secondary database. The start of any segments that match will be displayed in red as seen in the example below. If you are finding too few matches, you can decrease the length of the segment by changing the value in the notes entry box. You can also increase the matching threshold, which specifies the size of the allowable error between the matcher and matchee. For very large databases and large MIDI files, the process for searching for matches may take an appreciable amount of time. The program searches starting from the beginning of the MIDI file and be interrupted before it finishes. Increasing the skip parameter speeds up the process, but some matches may be missed. For example, if the skip parameter is set at 3 the starting position of each segment examined shifts by 3 notes.

Midimatcher creates several housekeeping files in the same folder as the program. The file contour.dat is used to communicate information between this program and midimatch5. The file test.mid contains the audio segment which is sent to your MIDI player. The file midimatcher.ini contains some state information for the program allowing the program to initialize to the state when you last exited the program. In event that the program was left in a bad state and cannot be restarted, you can delete midimatcher.ini allowing the program to run as if it were started for the first time. A new file midimatcher.ini will be created automatically. Alternatively, you can try to correct this problem by editing the midimatcher.ini file using a text editor like vi, emacs, or notepad.

Programmers Guide

Midibase scans all the MIDI files in a specified folder and creates a large file called midibase.bin in the that folder. This file contains the top line of every MIDI file and will be used by midimatch5 described next. Midibase is created by compiling midibase.c. (If you are compiling this on Windows, you will need the Mingw C compiler and two other files glob-win.c and glob.h, which are provided.)

Midimatch5 loads the entire midibase.bin database into the memory of the computer and performs the fragment matching and a few other functions required by midimatcher.tcl. It is compiled from midimatch5.c. Information is transferred between midimatch5 and midimatcher.tcl through stdout, a pipe, or the file contour.dat.
Midicopy extracts a particular segment from a MIDI file and places it into a new MIDI file (test.mid) which is sent to a MIDI player. To create this application, compile midicopy.c.
For Unix and Linux systems there is a makefile for compiling these programs. Midimatcher.tcl expects these programs to be in the same directory.

To download, return to Midimatcher Home Page.