the musical analog of word processing. Almost all score typesetting applications provide a means of automatic generation of a conventional music notation from MIDI data.

In conventional music notation, the onset time of each note is implicitly represented by the cumulative sum of durations of previous notes.  Durations are encoded by simple rational nmbers (e.g., quarter note, eighth note), consequently all events in music are placed on a discrete grid. So the basic task in MIDI transcription is to associate onset times with discrete grid locations, i.e., quantization.

However, unless the music is performed with mechanical precision, identification of the correct association becomes difficult. This is due to the fact that musicians introduce intentional (and unintentional) deviations from a mechanical prescription.  For example timing of events can be deliberately delayed or pushed. Moreover, the tempo can fluctuate by slowing down or accelerating. In fact, such deviations are natural aspects of expressive performance; in the absence of these, music tends to sound rather dull and mechanical.

On the other hand, if these deviations are not accounted for during transcription, resulting scores have often very poor quality.

Robust and fast quantization and tempo tracking is also an important requirement for interactive performance systems; applications that "listen" to a performer for generating an accompaniment or improvisation in real time (Raphael, 2001b; Thom, 2000). At last, such models are also useful in musicology for systematic study and characterization of expressive timing by principled analysis of existing performance data.

From a theoretical perspective, simultaneous quantization and tempo tracking is a
"chicken-and-egg" problem: the quantization depends upon the intended tempo interpretation and the tempo interpretation depends upon the quantization. Apparently, human listeners can resolve this ambiguity (in most cases) without any effort. Even persons without any musical training are able to determine the beat and the tempo very rapidly. However, it is still unclear what precisely constitutes tempo and how it relates to the perception of the beat, rhythmical structure, pitch, style of music etc. Tempo is a perceptual construct and cannot directly be measured in a performance.

The goal of understanding tempo perception has stimulated a significant body of ress beat induction, e.g., see (Desain & Honing, 1994; Large & Jones, 1999; Toiviainen, 1999).

These papers assume that events are presented as an onset list. Attempts are also made to deal directly with the audio signal (Goto & Muraoka, 1998; Scheirer, 1998; Dixon &
Cambouropoulos, 200).

Another class of tempo tracking models are developed in the context of interactive performance systems and score following. These models make use of prior knowledge in the form of an annotated score (Dannenberg, 1984; Vercoe & Puckette, 1985). More recently, Raphael (2001b) has demonstrated an interactive real-time system that follows a solo player and schedules accompaniment events according to the player's tempo interpretation.

Tempo tracking is crucial for quantization, since one can not uniquely quantize onsets without having an estimate of tempo and the beat.  The converse, that quantization can help in identification of the correct tempo interpretation has already been noted by Desain and Honing (1991). Here, one defines correct tempo as the one that results in a simpler quantization. However, such a schema has never been fully implemented in practice due to computational complexity of obtaining a perceptually plausible quantization.  Hence