Pattern matching in polyphonic music: the Chamfer distance

Due to the complexity of human perception, the evaluation of symbolic musical similarity constitutes a fundamental challenge in Music Information Retrieval (MIR). Standard approaches in the literature include geometric, string-matching, n-gram, tree-based, graph-based, and probabilistic methods, as well as recent approaches based on neural networks. Geometric approaches model notes as point sets or horizontal line segments (piano roll representation) and are particularly suited for pattern matching in polyphonic music given their multidimensional nature. The directed Hausdorff distance, an established geometric measure, evaluates similarity based on a worst-case criterion, which considers the maximum nearest-neighbor distance between two musical fragments. This thesis investigates the use of the directed Chamfer distance as a more robust alternative. By averaging the nearest-neighbor distances rather than considering the maximum, Chamfer is less sensitive to outliers in the query fragment. Given a musical score, and a relatively short pattern, the problem is to find the minimum directed Chamfer distance from the pattern to the score. We propose an algorithm that is transposition-invariant and time-shift-invariant, and is computationally efficient for large databases. Finally, we compare Chamfer with Hausdorff by implementing the two models and testing them on a polyphonic corpus in relation to three experimental cases: (i) a monophonic query versus a polyphonic score, (ii) a monophonic query augmented with outlier notes (thus polyphonic) versus a polyphonic score, (iii) a monophonic query (fixed tempo) versus a live performance, characterized by temporal fluctuations. The obtained results show that Chamfer outperforms Hausdorff in all three experimental cases. The precision-recall curves suggest that the average of the nearest-neighbors plays a fundamental role, especially in absorbing the noise introduced by the additional outlier notes and performance imperfections.

Data la notevole complessità della percezione umana, la valutazione della similarità musicale in forma notata costituisce una sfida importante nell'ambito del Music Information Retrieval (MIR). Gli approcci standard presenti in letteratura includono metodi geometrici, di string-matching, n-gram, basati su alberi, su grafi e approcci probabilistici, oltre a soluzioni più recenti basate su reti neurali. Gli approcci geometrici modellano le note come insiemi di punti o segmenti orizzontali (rappresentazione piano-roll), e sono particolarmente adatti per il pattern matching in ambito polifonico data la loro natura multidimensionale. La distanza di Hausdorff orientata, una misura geometrica già consolidata, valuta la similarità musicale sulla base di un criterio worst-case, che considera il massimo delle distanze dei nearest-neighbors tra i due frammenti. Questa tesi studia l'uso della distanza di Chamfer orientata come alternativa più robusta. Calcolando la media delle distanze dei nearest-neighbors invece di considerare il massimo delle distanze, Chamfer è meno sensibile rispetto alla presenza di note outlier nel frammento query. Dato uno spartito musicale e un frammento relativamente breve, il problema quindi consiste nel trovare la minima distanza di Chamfer orientata dal frammento allo spartito. Si propone un algoritmo che è invariante per trasposizione e per traslazione temporale, oltre ad essere computazionalmente efficiente per database di grandi dimensioni. Infine, si confrontano Chamfer e Hausdorff implementando i due modelli e testandoli su un corpus polifonico in relazione a tre casi sperimentali: (i) ricerca di query monofonica su partitura polifonica, (ii) ricerca di query monofonica aumentata con note outlier (quindi polifonica) rispetto a una partitura polifonica, (iii) ricerca di una query monofonica (a tempo fisso) rispetto a una performance dal vivo, caratterizzata da fluttuazioni temporali e imperfezioni tipiche di una esecuzione. I risultati ottenuti mostrano che Chamfer offre prestazioni superiori ad Hausdorff in tutti e tre i casi sperimentali. Le curve di precision-recall suggeriscono che calcolare la media delle distanze dei nearest-neighbors assume un ruolo fondamentale, soprattutto nell'assorbire il rumore introdotto dalle note outlier aggiuntive e dalle imperfezioni dell'esecuzione.