Faculteit Ingenieurswetenschappen Vakgroep Telecommunicatie en informatieverwerking Voorzitter: Prof. dr. ir. Herwig Bruneel
Automatische detectie van ritmepatronen in muziek
door Len Vrijders
Promotors: Prof. dr. Guy De Tr´e, Prof. dr. Marc Leman Begeleiders: Tom Matth´e, Olmo Cornelis
Scriptie ingediend tot het behalen van de graad van licentiaat in de informatica optie: informatie- en communicatietechnologie
Academiejaar 2005–2006
Faculteit Ingenieurswetenschappen Vakgroep Telecommunicatie en informatieverwerking Voorzitter: Prof. dr. ir. Herwig Bruneel
Automatische detectie van ritmepatronen in muziek
door Len Vrijders
Promotors: Prof. dr. Guy De Tr´e, Prof. dr. Marc Leman Begeleiders: Tom Matth´e, Olmo Cornelis
Scriptie ingediend tot het behalen van de graad van licentiaat in de informatica optie: informatie- en communicatietechnologie
Academiejaar 2005–2006
De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie.
Gent, augustus 2006 De auteur
Len Vrijders
Voorwoord Als fervent muziekliefhebber kom ik het meermaals tegen dat ik een liedje gehoord heb en het graag zou willen hebben. Helaas luister ik nooit naar de woorden. Ik ben slagwerker, afgestudeerd aan de Muziekacademie van Buggenhout, en beoordeel hierdoor liedjes op hun muzikale inhoud. Een tekst die driemaal op hetzelfde deuntje geschreven is, boeit me niet. Soms kan een catchy refrein wel eens blijven hangen, maar dan nog zijn het vaak loze woorden. Hierdoor is het natuurlijk ook moeilijk om te onthouden hoe het liedje heet. Een fantastische oplossing zou zijn dat er een zoekmachine bestaat waar ik het deuntje kan neuri¨en en die me daarna vertelt wat de titel en uitvoerder is. Een dergelijke zoekmachine ontwikkelen vraagt kennis over twee domeinen: het domein van informatica en het domein van muziek. Niet toevallig hebben deze twee werelden me steeds geboeid. Als kleine jongen werd ik door mijn ouders naar de muziekschool gestuurd en dankzij het werk van mijn vader werd ik ondergedompeld in die andere wereld. Uiteindelijk kwam het zo ver dat ik de computer begon te gebruiken om zelf muziek te maken. Na de middelbare school was het kiezen tussen muziekconservatorium of universiteit. De keuze van de richting informatica was snel gemaakt, maar muziek bleef me achtervolgen. In mijn voorlaatste jaar was ik zelf al op zoek gegaan hoe ik in een afstudeerwerk muziek en informatica kon combineren. Mijn oog was toen gevallen op dit onderwerp: patronen zoeken in ritme secties van audio. De hierboven beschreven zoekmachine lijkt momenteel nog toekomstmuziek, maar ik hoop dat ik met dit werk toch al een stapje in die richting gezet heb. Graag zou ik iedereen willen bedanken die heeft bijgedragen tot de verwezenlijking van dit eindwerk. Mijn vrienden, medestudenten, bewoners en ex-bewoners uit Home Astrid en alle anderen die ik met vragen over muziek of informatica ongetwijfeld heb verblijd. In het bijzonder mijn ouders Herman Vrijders en Sabine De Boos voor elke vorm van steun tijdens mijn studies. Ook mijn nicht Eva, studente aan de KUL die net als ik de thesisstress moest ondergaan, moet ik bedanken voor de moed en voor het doorzettingsvermogen dat ze me gegeven heeft; mijn promotors, Prof. dr. Guy De Tr´e en Prof. dr. Marc Leman, en begeleiders Tom en Olmo en de vakgroepen ELIS en IPEM van de UGent voor het scheppen van de mogelijkheid om dit onderzoek te verrichten.
Bedankt iedereen! -Len Vrijders, augustus 2006.
Automatische detectie van ritmepatronen in muziek door Len Vrijders Afstudeerwerk ingediend tot het behalen van de graad van licentiaat in de informatica, optie: informatie- en communicatietechnologie Academiejaar 2005–2006 Universiteit Gent Faculteit Ingenieurswetenschappen - Vakgroep Telecommunicatie en informatieverwerking [14]
Promotors: Prof. dr. Guy De Tr´e en Prof. dr. Marc Leman
Samenvatting De problematiek van dit onderwerp situeert zich in het brede veld van feature extractie uit elektronische media. In dit onderzoeksdomein wordt getracht om op basis van het elektronisch formaat van een object (audio, video, etc...) meer informatie te bekomen over de inhoud van het object. In dit afstudeerwerk zal worden samengewerkt met het Instituut voor Psychoacoustica en Elektronische Muziek (IPEM) [5] . Door het IPEM werd reeds een tool ontwikkeld die toelaat om uit een digitale audio-opname een sequentie van aanslagen op percussieinstrumenten te achterhalen. Daarbij wordt voor elke aanslag het tijdstip en de intensiteit vastgelegd. In dit afstudeerwerk zal een algoritme worden ontwikkeld, dat op basis van een dergelijke sequentie het ritmepatroon van de opname tracht te achterhalen. Discipline: Informatieverwerking Aard: Modellering en implementatie Trefwoorden: patroonherkenning
Automatic Detection of Rhythmpatterns in Audio Len Vrijders Supervisor(s): Prof. dr. Guy De Tr´e, Prof. dr. Marc Leman, Tom Matth´e, Olmo Cornelis Abstract— This article will give a brief status of the work done in the matter of automatic detection of patterns in rhythm onsets found in musical audio. We will explain some techniques that cover realistic problems found in live-played music. Most solutions are based on techniques using Fuzzy Logic. Keywords—Patternrecogniton, Onsets, Fuzzy Logic
I. I NTRODUCTION
T
Interval1 0.000 0.400 0.400 0.200 0.600 0.400 1.000 0.200 1.200 0.200 1.400 0.200 1.600
== == == == == !=
Interval2 0.400 1.600 0.200 2.000 0.400 2.200 0.200 2.600 0.200 2.800 0.300 3.000 3.300
HE main goal of our topic is covering some problems specific to the recognition of patterns (small time intervals with events in it that are repeated more than once) in the rhythm section of live music. Most music pieces are not a perfect copy of the score: artists tend to give their own twist to the score (most of the times unwillingly), resulting in an (inaudible to the public) imperfect rendition. The input of our problem are onsets generated by the drumdetect tools[1]. An onset is described by the timestamp on which the event occurs. The extracted onsets are rhythm events, this way, the rhythm is separated from the melody. In the following section, we will explain how patterns can be found when we know the input is perfect, e.g. made by a synthesizer. This way, we know exactly where the events of the patterns are. Of course this approach is not realistic: when a live band plays music, they will always be out of tempo. When using the techniques from the perfect onsets on the live audio no patterns will be found. In section IV, another technique is proposed, one that will find an interval of onsets that is repeated in the live music. When certain conditions are fulfilled, some repetitions can be classified as a pattern, and ultimately as being the pattern of the song as stated in section V.
In table I we can match the first five Interonset Intervals, the last one fails. For index 6, k == 5 and also k == j-i-1 == 7-1-1 == 5. If that last one was a match, we would say that interval2 immeditaly follows interval1 , making the pattern of an ideal length. The last one is not a match so our pattern is made out of the onsets with index 0 till 5. When even one Interonset Interval is slightly different, pattern recognition fails. It its possible to solve this by specifying another equals-method. It is up to the user to decide if the value of Abs(δj+k - δi+k )1 must be equal to zero or not. When a value higher than zero is being allowed, a less-perfect-input can be used and pattern recogniton may succeed. However, this algorithm will fail when somewhere in the song there is an event that is not on it’s place, e.g. the drummer tapped two times on a tom-tom when he should have tapped only one time.
II. P ERFECT ONSETS
III. F UZZY L OGIC
TABLE I M ATCHES IN TWO TIME INTERVALS ( IN SECONDS ), ALONG WITH THEIR INTERONSET VALUE .
Fuzzy Logic[3] uses a membership function to denote the degree to which an object is valid against a given statement. The classic Boolean Logic has values 0 (false) or 1 (true), whereas Fuzzy Logic uses a value between 0 and 1. E.g. the temperature of water can be cold (0) or hot (1). But what if the water is something in between? Then Fuzzy Logic would assign a value between 0 and 1 to that given temperature. The same principle can be applied to the case of the onsets: two Find 2 equal values: δi en δj events (a and b in figure 1) from two intervals (meaning they are Now check if δi+k == δj+k holds, starting seperated by some time t) can be thought of as being the same with k=1. For every k that the above holds, event within a pattern, even though they are not exactly on the a pattern is found. same place where the tempo of the song would want them to be. If k == j-i-1 then pattern starting with δj The membership function used has a base, an interval with the follows pattern starting with δi . time of the event in the middle. When the possibility that two events can be the same is being calculated, an interval can be This simple algorithm will find patterns in a perfect input. made around the two events. This will make it possible to calThe last line states that if k equals j-i-1, no other events are 1 Abs(x) is the absolute value of x. in between the patterns. After onsets are generated, the Interonset Interval[2] can also be generated. An Interonset Interval is the time between two onsets and just that. An Interonset Interval is not the same as the length of an event. It is in the Interonset Interval values patterns will be searched for. Repetitions of certain values in a row will result in a pattern. Patterns can be found as followed:
culate the amount of equalness between two events based on an overlapping surface (figure 1).
Ignoring the start and the end of a pattern, it is still likely that humans will make up their own pattern, one that resembles very close to the real pattern. No worries, it is possible to calculate the edit-distance2 and still match it. Suppose there are 3 patterns found in the song (fig. 2), the question remains which one to label as the pattern. The number of repetitions are all the same, so they all are entitled to being the pattern. The edit-distance can now be calculated: for every event that has to be inserted, a cost of λ is added. With this distance, an expression (the elements in table II) can be made as to how far patterns match each other; a value of 1 expressing a perfect match, meaning no event had to be inserted to match the patterns. z z v z z z z 1 2
z
z
z
z
3
z
z
z
z
z z v
z
Fig. 2. Three patterns found in the same song. Two events are marked white, meaning they have no match in the other patterns.
Pattern1 Pattern1 Fig. 1. Poss[b=a] is calculated by the overlapping surface.
IV. M ATCHING INTERVALS The number of events in a pattern should be at least 3. Less will induce many short repetitions that frequently tend to nothing instead of a pattern. When there are n events in an interval, a technique is needed to match them to M events from another interval. For an event from an interval1 and an event from an interval2 , the technique explained in the previous section can be used. Now the reader probably noted already that the two intervals do not have the same amount of events. Even when they are equal, some events may not be matched. This means that a new event should be inserted. This can be easily achieved by thinking there is an event in the other interval to match it. This will of course induce a cost, named λ (0 ≤ λ ≤ 1). This techniques lends itself to solve problems when notes are played that shouldn’t have been played. Also, when there is a complete silence (a period in time having length equal to the current intervallength) in between patterns, this technique can be used to continue searching for more occurences of the current parrent. V. S ELECTING the PATTERN When more than one candidate-pattern is found, some conditions are needed to select the pattern that is the most realistic to humans as being the pattern. However, a small experiment showed that even a large group of humans do not tend to hear the same pattern in the same song. Selecting the best pattern seems to be a subjective matter. But a closer look at those results showed that each of the patterns were actually the same, they just started on another note. So instead of giving a pattern a start- and an end-event, it is possible to look at the patterns as being cyclic.
Pattern2 Pattern3
1 5+λ 6 5+2∗λ 7
Pattern2 5+λ 6 1 5+λ 6
Pattern3 5+2∗λ 7 5+λ 6 1
TABLE II E XPRESSIONS OF MATCHES BETWEEN PATTERNS FROM FIG . 2
Now all of these values per row from the matrix in table II are added and divided by the number of patterns. We have 5 5 (for λ equal to 0): (1 + + )/3 for pattern1 and pattern3 , 6 7 5 5 ( + 1 + )/3 for pattern2 . This gives 0.85 and 0.89. These 6 6 are numbers that express the gradation of the patterns. Pattern2 has the highest gradation, meaning this one has to do the least amount of work to transform itself into all of the other found patterns. So only pattern2 is being called ”the best” pattern. VI. C ONCLUSIONS A technique based on Fuzzy Logic was proposed to search for patterns in Interonset Intervals. An implementation was made and succesfully found patterns in manually made audio based on simple (simple in the way that only a very few number of instruments were used) rhythm sections. R EFERENCES [1] K. Tanghe and S. Degroeve and B. De Baets, An algorithm for detecting and labeling drum events in polyphonic music, Proceedings of the first Music Information Retrieval Evaluation eXchange (MIREX), London, United Kingdom, September 11-15, 2005. [2] J. London, Hearing in Time : Psychological Aspects of Musical Meter, Oxford University Press, USA, September 2004. [3] L.A. Zadeh, Fuzzy Sets, Information and Control 338-353,1965. 2 edit-distance: amount of work needed to transform a pattern into another pattern
Inhoudsopgave 1 Inleiding 1.1 Uitwerking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Drum detectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Patroonherkenning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Perfecte onsets 2.0 Introductie . . . . . . . . . . . . 2.1 Werken via een voorbeeld . . . . 2.2 Onsets . . . . . . . . . . . . . . . 2.3 Naar een algoritme . . . . . . . . 2.3.1 Algoritme met de hand . 2.3.2 Algoritme met δ-waarden 2.4 Slechtere input . . . . . . . . . . 2.4.1 Een foutmarge . . . . . . 2.4.2 De kleinste foutmarge . . 2.5 Conclusie . . . . . . . . . . . . .
1 1 1 2
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
3 3 3 4 6 6 8 11 11 12 12
3 Naar meer realisme 3.0 Introductie . . . . . . . . . . . . . . 3.1 Minder strak gespeeld . . . . . . . . 3.1.1 Vage Logica . . . . . . . . . . 3.1.2 Vage Logica toegepast . . . . 3.1.3 Vaste intervallengte . . . . . 3.2 Meerdere patronen . . . . . . . . . . 3.2.1 Overlappende oppervlakten . 3.3 Ruis . . . . . . . . . . . . . . . . . . 3.3.1 Onduidelijkheden in patroon 3.4 Pauze . . . . . . . . . . . . . . . . . 3.4.1 Perfecte pauze . . . . . . . . 3.5 Algortime . . . . . . . . . . . . . . . 3.6 Conclusie . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
14 14 14 14 15 21 25 27 31 31 34 34 35 36
4 Toepassingen 4.0 Introductie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Tempo afleiden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37 37 37
. . . . . . . . . .
vi
Inhoudsopgave 4.2 4.3 4.4
p. vii
Genormaliseerd patroon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Patronen vergelijken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gemiddeld patroon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Software 5.0 Introductie . . . . . . . . . . . . 5.1 Code . . . . . . . . . . . . . . . . 5.2 Output . . . . . . . . . . . . . . 5.3 Autocorrelatie . . . . . . . . . . . 5.4 Tests en vergelijkingen . . . . . . 5.4.1 Zelfgemaakte Voorbeelden 5.4.2 Muziekfragmenten . . . . 5.4.3 Samenvatting . . . . . . . 5.5 Uitvoeringstijd . . . . . . . . . . 5.6 Conclusie . . . . . . . . . . . . .
38 40 42
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
43 . 43 . 43 . 43 . 49 . 54 . 54 . 62 . 113 . 115 . 115
6 Besluit 6.1 Suggesties . . . . . . . . . . . . . . 6.1.1 Relevance parameter . . . . 6.1.2 Tempo afleiden . . . . . . . 6.1.3 Andere vormen van pauze . 6.1.4 Tempo verandering . . . . . 6.1.5 Verschillende instrumenten
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
117 117 117 118 118 119 120
A Handleiding 121 A.1 Benodigdheden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.2 Command line opties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 A.3 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 B Projectbeschrijving B.1 Klankarchief . . . B.2 Opdracht . . . . B.3 Doelstellingen . . B.4 Promotoren . . . B.5 Financiering . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
125 125 125 126 126 127
Bibliografie
128
Lijst van figuren
130
Lijst van tabellen
133
Hoofdstuk 1
Inleiding Dit afstudeerwerk past in het DEKKMMA-project (Digitalisatie van het Etnomusicologisch Klankarchief van het Koninklijk Museum voor Midden-Afrika) dat het IPEM samen met TELIN uitvoert. Dit project is een samenwerking tussen het Koninklijk Museum voor Midden-Afrika (KMMA), Universit´e Libre de Bruxelles en Universiteit Gent, en heeft als opdracht het etnomusicologisch klankarchief van het KMMA te digitaliseren. Een beschrijving van dit project is te vinden als bijlage B.
1.1
Uitwerking
Het IPEM en TELIN van de UGent staan in voor de annotatie van de muziek. De bedoeling is om aan elk lied een kenmerkenvector te koppelen. Al deze vectoren worden in een databank bijgehouden. Er zal dan een mogelijkheid [8] gecre¨eerd worden om op basis van enkele kenmerken liederen te zoeken die sterk op het gevraagde lijken. Deze scriptie zal verderwerken op reeds bestaande tools van het IPEM uit het MAMI [6] -project. Meer bepaald wordt gebruik gemaakt van de Drum detection console applications” [13] . ” De bedoeling is tot een algoritme te komen om in onsets (een onset is een tijdstip waarop een event plaats heeft) te zoeken naar patronen en herhaling van deze patronen. Een doelpatroon is liefst zo lang mogelijk (herhaling niet inbegrepen) en wordt zoveel mogelijk herhaald. In dit afstudeerwerk komen informatica en muziek samen. Voorkennis van beide domeinen is gewenst, maar van de meeste begrippen zal een kleine voorlichting gegeven worden.
1.1.1
Drum detectie
De Drum detection console applications” (applicaties geschreven met bevindingen uit het MAMI” project [13] , [16] , [17] , [15] ) worden aangepast aan de noden van de muziek van het KMMA. Origineel 1
1.1. Uitwerking
p. 2
zoeken deze tools immers naar Westerse muziek met Westerse instrumenten zoals bassdrum, snaredrum en cymbaal. Deze tools hebben uiteindelijk als output een lijst van koppels (tijd,relevantie) voor ieder gevonden event. Voor elk event aanwezig in deze lijst gelooft [3] de gebruikte tool dat dit event afkomstig is van een percussie-instrument. Het is voor deze lijst van tijd-events zijn dat we een algoritme zullen ontwikkelen dat een patroon kan vinden.
1.1.2
Patroonherkenning
Vooraleer een implementatie te geven dat patronen kan vinden in onsets, zoeken we enkele technieken die een basis vormen voor de implementatie. We beginnen door te veronderstellen dat we een perfecte input hebben, waarmee we bedoelen dat we al op voorhand weten dat er een patroon te vinden is. We gaan op zoek naar een manier hoe we dit patroon kunnen vinden. Eens we een algoritme hebben gevonden, bekijken we wat er te kort is om ook realistische input te verwerken. Hiervoor hebben we ons gebaseerd op het principe van vage logica om patronen die niet exact gelijk zijn toch met elkaar te vergelijken.
Hoofdstuk 2
Perfecte onsets 2.0
Introductie
In dit hoofdstuk beginnen we met zelf gemaakte audio waar we de data uithalen om een patroon te zoeken. We passen deze data aan, zodat we op voorhand weten waar herhalingen zich voordoen en wat het patroon is. We zullen een algoritme beschrijven dat op dit soort input kan werken.
2.1
I4 ˇ 4
Werken via een voorbeeld
ˇ( ˇ
Ľ Ľ ˇ( ˇ ˇ ˇ
ˇ( ˇ ? >
ˇ
ˇ( ˇ
Ľ Ľ ˇ( ˇ ˇ ˇ
ˇ( ˇ ? >
Figuur 2.1: Voorbeeld input. Een patroon is hier tweemaal herhaald en bestaat uit negen noten.
Dit is een eenvoudig ritme. De representatie is in MIDI (Musical Instrument Digital Interface), channel 10. Channel 10 in MIDI is speciaal gereserveerd voor slagwerk: elke lijn op een notenbalk is eigenlijk een ander instrument. In dit voorbeeld gebruiken we twee verschillende instrumenten. Het is de taak van de ”Drum detection console applications” [13] om een goede output te produceren die alle noten van de verschillende instrumenten kan vinden. In tabel 2.1 staat de output die deze tools gegenereerd hebben. In plaats van deze output te gebruiken, maken we zelf de output voor dit ritme omdat de tools rekenfouten introduceren: een computer werkt met een eindig aantal decimalen. Als we deze output wat aanpassen, weten we meteen waar patronen aanwezig zijn. In tabel 2.2 staat de uiteindelijke bijgewerkte input voor het algoritme. Het gebruikte tempo staat op 150BPM (Beats Per Minute) en de maatsoort is
4 4
3
. Dit betekent
2.2. Onsets
p. 4
dat er vier 4e noten zijn per maat en dat er per minuut 150 4e noten gespeeld worden. Dit geeft 0.400 seconden voor de duur van een 4e noot. Voor een 8e noot komt dit op 0.200 seconden enzovoort.
2.2
Onsets
Een onset [10] is een tijdstip waarop een event zich voordoet. De tijd tussen twee opeenvolgende onsets noemen we het interonset interval. Merk op dat deze tijd niet gelijk is aan de duur van het event. Indien een noot wordt gespeeld, kan er tijdens de duur van deze noot nog een andere noot beginnen. Dit is zeker zo in het geval van polyfone muziek. Daar we geen bijkomende informatie hebben over duurtijden per noot, gaan we ervan uit dat we monofone muziek gebruiken. Het interonset interval kan dan aanzien worden als duur tot het volgende event en ook als duur van het huidige event. In tabel 2.2 is bij elk event x.00050 seconde te zien. Dit heeft te maken met het eerste event, namelijk het begin van een liedje. We staan even stil bij de vraag: wanneer begint een liedje? Noemen we het eerste geluid dat we vinden het begin en zetten we dit op tijd = 0 seconden? Mag dat geluid enkel het begin van een slaginstrument zijn? Mag dat geluid enkel het begin van het te zoeken patroon zijn? Uiteraard kan deze afwijking afkomstig van de bronopname zijn: er werd iets voor het begin van het liedje op de opname-knop gedrukt. Een dirigent van een orkest zal ook eerst een lege maat slaan zodat de artiesten samen op hetzelfde moment beginnen te spelen. Als we de voorgaande vragen omzetten in eisen roepen deze veel beperkingen op, zodat enkel nog op een beperkt aantal inputmogelijkheden het algoritme zou werken. We wensen op zoveel mogelijk liedjes ons algoritme los te laten, dus proberen we al deze beperkingen overboord te werpen. In een later stadium zullen we het algoritme verfijnen zodat we ook rustperiodes v´o´or en na een herhaling van het patroon mogen invoegen.
De onsets uit tabel 2.1 hebben elk zo’n 14 decimalen. We vragen ons af of dit wel nodig is. Immers in geluid is het zo dat het menselijk oor geen verschil kan merken tussen de events 4.40503401360544 en 4.40503401360545 (gesteld dat ze door hetzelfde instrument en met dezelfde luidheid gespeeld worden). Sterker nog, het menselijk oor kan pas events onderscheiden die minimaal 50ms [10] van elkaar gescheiden zijn. Als we hier rekening mee houden, dan hebben we al meer dan genoeg met 3 decimalen, wat gelijk is aan 1 milliseconde.
2.2. Onsets
Event
p. 5
OnsetTime
Event
OnsetTime
1
0.0249886621315193
1
0.00050
2
0.404126984126984
2
0.40050
3
0.603673469387755
3
0.60050
4
1.0027664399093
4
1.00050
5
1.20730158730159
5
1.20050
6
1.41183673469388
6
1.40050
7
1.60639455782313
7
1.60050
8
2.00548752834467
8
2.00050
9
2.20503401360544
9
2.20050
10
3.2027664399093
10
3.20050
11
3.60684807256236
11
3.60050
12
3.80639455782313
12
3.80050
13
4.20548752834467
13
4.20050
14
4.40503401360544
14
4.40050
15
4.61455782312925
15
4.60050
16
4.80412698412698
16
4.80050
17
5.20321995464853
17
5.20050
18
5.40775510204082
18
5.40050
Tabel 2.1: De originele onsets
Tabel 2.2: De aangepaste onsets
2.3. Naar een algoritme
2.3
p. 6
Naar een algoritme
Om tot een algoritme te komen dat het patroon zal vinden in muziekvoorbeeld 2.1, gebruiken we een methode zoals we het met de hand zouden doen, gelijkend op [2] .
2.3.1
Algoritme met de hand
1. Neem de tijd van het eerste event:
tijd1
Neem de tijd van het tweede event:
tijd2
Neem de tijd van het derde event:
2.
tijd3
Bereken:
δ 1,2 = tijd2 - tijd1 δ 2,3 = tijd3 - tijd2
3.
Nu zoeken we een tijdk , tijdk+1 en tijdk+2
zodat (δ k,k+1 == δ 1,2 ) en (δ k+1,k+2 == δ 2,3 )
1
t1 }
t2 } δ1,2 tp }
2
δ2,3 tp+1 }
δp,p+1
3
t3 }
tq }
δp+1,p+2 tq+1 }
δq,q+1
tp+2 }
tq+2 }
δq+1,q+2
Figuur 2.2: Visualisatie van algoritme 1
In figuur 2.2 is dit algoritme visueel voorgesteld. De as is de tijdlijn, de bollen zijn events die zich op dat tijdstip t voordoen. We zien dat δ 1,2 niet gelijk is aan δ p,p+1 dus het voorgesteld patroon2 is niet gelijk aan patroon1 . Voor patroon3 geldt dat δ q,q+1 gelijk is aan δ 1,2 en δ q+1,q+2 gelijk is aan δ 2,3 met andere woorden patroon3 is gelijk aan patroon1 . We zouden ook de afstand van t1 tot t3 kunnen vergelijken met de afstand van tq tot tq+2 om te zien of deze ook een patroon vormen. Maar aangezien deze afstand gelijk is aan δ 1,2 +δ 2,3 wordt deze afstand impliciet meegerekend en hoeft dit niet expliciet berekend worden.
2.3. Naar een algoritme
p. 7
Aan de hand van dit algoritme kunnen we al enkele verbeteringen aanbrengen. Er wordt vooral met de tussen-event-tijden gerekend. Deze kunnen we al op voorhand
berekenen. Ook weten we niet hoeveel events we in stap 1 moeten nemen om te vergelijken. De oplossing hiervoor is een venster te gebruiken. Dit venster kunnen we vergroten, maar timestamp van laatste event ook verschuiven. De maximale grootte van het venster is . 2 Immers als een interval langer is dan deze maximale grootte, is het onmogelijk om nog een herhaling te vinden van dat interval. Verschuiven kan wel over alle events. Hier zal al een eerste beperking ingevoerd worden: de minimale lengte van een patroon. We
proberen eigenlijk zo vaag mogelijk te blijven over wat een patroon juist is, maar langzaam aan zullen we er toch een beter beeld over moeten krijgen. Waarom is deze minimale lengte belangrijk? Stel dat we patronen kunnen beschouwen van lengte = 1 event. Dan kunnen we eigenlijk elk ander event met dit ene event vergelijken en zeggen dat deze gelijk zijn. Dit resulteert in een te groot aantal patronen, wat niet wenselijk is. Ook voor lengte = 2 events zullen er nog veel patronen te vinden zijn, zoals ge¨ıllustreerd
in tabel 2.3. Deze patronen komen veel voor en zijn eigenlijk gewoon de tijd tot het volgende event. Als we deze patronen breder bekijken (volgende en/of vorige waarde erbij nemen) zien we dat er geen sprake meer is van een herhaling. Ons algoritme gebruikt meteen twee δ-waarden zodat het minimum aantal events 3 moet zijn. Dit kan nog betwist worden voor een liedje waar het ritme enkel bestaat uit opeenvolgende noten van dezelfde duur die daar eigenlijk het patroon vormen. Is het die ene noot die altijd herhaald wordt, of is het een opeenvolging van noten die herhaald worden? Een beter minimum is dan niet het aantal events, maar wel een tijdsinterval.
400 200 400 200
200
200 400 200 1000 400 200 400 200
200
200 400 200
Tabel 2.3: Hier zijn alle 8e noten (duur = 0.200s) gevonden als patroon voor lengte = 1. Er is enkel een structuur te zien als we meerdere noten bij elkaar nemen. Voor de leesbaarheid in milliseconden genoteerd.
Als er een minimale lengte wordt vastgezet, kunnen we dan ook een maximale lengte vast-
zetten? Het is beter dit niet te doen, daar het algoritme inventief genoeg moet zijn om in een gevonden patroon deelpatronen te ontdekken. Zo een patroon kan dan gereduceerd worden tot een patroon met een minimum lengte. Is dit het geval, dan mocht dat patroon eigenlijk niet aangezien worden als een patroon. Dit brengt een beperking mee naar de vraag: zoek
2.3. Naar een algoritme
p. 8
het langst mogelijke (in tabel 2.3 willen we rechthoeken met meer dan ´e´en event, liefst zoveel mogelijk), meest herhaalde (het aantal rechthoeken moet zo hoog mogelijk zijn) patroon. Nog een bijkomend probleem is het laatste event. Er komt geen event meer zodat we ook geen
tussen-event-tijd (meer bekend als interonset interval of IOI ) kunnen berekenen. Dit lossen we op door een dummy waarde te gebruiken die elke mogelijke waarde kan betekenen. In tabel 2.5 staan nu ook de tussen-event-tijden vermeld. We kunnen nog opmerken dat de tussenevent-tijd schijnbaar de duur van het vorige event bepaalt. Immers, voor slaginstrumenten is er geen verschil te horen tussen de voorbeelden in figuur 2.3, tenzij bij sommige instrumenten een rust dempen betekent, maar dit komt niet vaak voor. Het gebruik van een dummy waarde blijkt geen invloed te hebben op de definitie van een onset in sectie 2.2: het interonset interval is niet te interpreteren als duurtijd van een event, maar wel als duurtijd tot het volgende event.
I4 ˇ 4 ˇ
ˇ
ˇ
I4 ˇ ( 4 ? ˇ( ? ˇ( ? ˇ( ? I4 ˇ ) 4 @ ? ˇ)@ ? ˇ)@ ? ˇ)@ ? Figuur 2.3: Gespeeld door een slaginstrument klinkt dit driemaal hetzelfde. Het is moeilijk om bij slaginstrumenten de duur van een noot te bepalen.
Een tweede algoritme zal op de lijst van δ-waarden inwerken, want daar kan je zelfs met het blote oog meteen herhalingen van patronen zien. Dit zullen we dan ook implementeren.
2.3.2
Algoritme met δ-waarden
Neem twee gelijke interonset-waarden:
δ i en δ j
Ga nu na of voor elke opeenvolgende k, startend vanaf k:=1 geldt:
δ i+k == δ j+k
Als dit zo is, dan hebben we een herhaling gevonden. Als bovendien geldt dat k == (j-i-1), dan is een aansluitend patroon gevonden.
2.3. Naar een algoritme
Event
p. 9
OnsetTime
delta
1
0.0249886621315193
0.379138321995465
2
0.404126984126984
3
0.603673469387755
4
OnsetTime
delta
1
0.00050
0.400
0.199546485260771
2
0.40050
0.200
0.399092970521545
3
0.60050
0.400
1.002766439909300
0.204535147392290
4
1.00050
0.200
5
1.207301587301590
0.204535147392290
5
1.20050
0.200
6
1.411836734693880
0.194557823129250
6
1.40050
0.200
7
1.606394557823130
0.399092970521540
7
1.60050
0.400
8
2.005487528344670
0.199546485260770
8
2.00050
0.200
9
2.205034013605440
0.997732426303860
9
2.20050
1.000
10
3.202766439909300
0.404081632653060
10
3.20050
0.400
11
3.606848072562360
0.199546485260770
11
3.60050
0.200
12
3.806394557823130
0.399092970521540
12
3.80050
0.400
13
4.205487528344670
0.199546485260770
13
4.20050
0.200
14
4.405034013605440
0.209523809523810
14
4.40050
0.200
15
4.614557823129250
0.189569160997730
15
4.60050
0.200
16
4.804126984126980
0.399092970521550
16
4.80050
0.400
17
5.203219954648530
0.204535147392290
17
5.20050
0.200
18
5.407755102040820
dummy
18
5.40050
dummy
Tabel 2.4: De originele onsets met berekende tussenwaarde
Event
Tabel 2.5: Zelfgemaakte onsets met berekende tussenwaarde
2.3. Naar een algoritme
p. 10
Om wat duidelijkheid te scheppen, illustreren we dit algoritme door gebruik te maken van het voorbeeld:
Input: δ-waarden uit tabel 2.5 met als dummy-waarde -1. Deze waarden kunnen we vergelijken met de noten uit het muziekvoorbeeld 2.1. Daar hebben we beschreven hoe we deze tussentijden (0.400 voor een 4e , 0.200 voor een 8e ) exact kunnen berekenen. 400 200 400 200 200 200 400 200 1000 400 200 400 200 200 200 400 200 -1
1: 400 200 400 200 200
200 400 200 1000 400 200 400 200 200
2: 400 200 400 200 200 200 400 200 1000
200 400 200 -1
400 200 400 200 200 200 400 200 -1
3: 400 200 400 200 200 200 400 200 1000 400 200 400 200 200 200 400 200 -1 4: 400 200 400 200 200 200 400 200 1000 400 200 400 200 200 200 400 200 -1 5: 400 200 400 200 200 200 400 200 1000 400 200 400 200 200 200 400 200 -1 6: 400 200 400 200 200 200 400 200 1000
400 200 400 200 200 200 400 200 -1
Tabel 2.6: Output: Enkele mogelijke patronen. De herhalingen zijn aangeduid door een rechthoek.
Aangezien het gebruik van een dummy betekent dat 400 200 -1 gelijk is aan 400 200 400
en 400 200 -1 gelijk is aan 400 200 1000 volgt hieruit dat ook 400 200 400 gelijk is aan 400 200 1000 . Zodat we dit ook als herhaling kunnen aanzien. Uiteraard geldt dat bij het ontbreken van een dummy dat 400 200 400 niet gelijk is aan 400 200 1000 . In het 3e resultaat is i gelijk aan 1 en j gelijk aan 12. Vanaf k gelijk aan 2 geldt δ 3 != δ 14 .
Het patroon stopt dus met δ 2 . In het 6e resultaat is i gelijk aan 1 en j gelijk aan 10. Bovendien is de laatste k gelijk
aan j-i-1 = 10-1-1 = 8 wat betekent dat het deel startend met δ 1 aansluit op het deel startend met δ 10 . Er is meer dan ´e´en herhaling gevonden. Sommige patronen zijn langer, sommige zijn meer
gebruikt. Wederom rijst de vraag: wat is hier het” patroon? We zouden graag van resultaat ” 6 zeggen dat dit het” patroon tweemaal bevat. In de context van perfecte liedjes is de helft ” van resultaat 6 het” patroon: het is een herhaling dat in heel het liedje aanwezig is en als ” we het patroon herhalen bevat deze verzameling alle events. Als we deze regel gebruiken, hebben we het” patroon gevonden. Voor tabel 2.6 komt dit neer op het zoeken per lijn ”
2.4. Slechtere input
p. 11
naar zoveel mogelijk rechthoeken en zoveel mogelijk events per rechthoek. Zo ´e´en rechthoek apart wordt dan aanzien als het” patroon. ”
2.4
Slechtere input
Het algoritme beschreven in de vorige sectie werkt op perfecte input. Echter, de realiteit is niet zo perfect zoals te zien is in de gedetecteerde onsets (tabel 2.1). Als nog maar ´e´en van de getallen een kleine afwijking vertoonde, zou het patroon niet gevonden zijn. We kunnen dit toch verhelpen door een niet zo strikte eis te stellen aan het gelijk zijn van twee δ-waarden.
2.4.1
Een foutmarge
Stel dat onze perfecte input 400 200 400 eigenlijk 404 192 388 en wat later 421 202 410 is. Dit zijn slechts enkele milliseconden verschil. Enkel een computer kan horen dat dit niet allemaal hetzelfde is. Als een mens het verschil niet hoort, kunnen we de computer dit ook niet verbieden. In plaats van dat 404 192 388 exact gelijk moet zijn aan 421 202 410 (dus door te verifi¨eren dat 404 gelijk is aan 421, 192 aan 202, 388 aan 410), kunnen we een foutmarge toelaten. Twee interonset intervallen δ1 en δ2 zijn dan gelijk als en slechts als Abs(δ 1 -δ 2 )1 <= foutmarge. Het algoritme wordt dan:
Neem twee interonset-waarden zodat Abs(δ i -δ j ) <= foutmarge Ga nu na of voor elke opeenvolgende k, startend vanaf k:=1 geldt:
Abs(δ i+k -δ j+k ) <= foutmarge
Als dit zo is, dan hebben we een herhaling gevonden. Als bovendien geldt dat k == (j-i-1), dan is een aansluitend patroon gevonden.
We laten dit algoritme nu inwerken op de data uit tabel 2.4 met foutmarge = 20ms. De input is 379 200 399 205 205 195 399 200 998 404 200 399 200 210 190 399 205 -1. Met -1 bedoelen we de dummy waarde.
Dit zijn enkele resultaten: 1: 379 200 399 205 205
195 399 200 998 404 200 399 200 210
190 399 205 -1
2: 379 200 399 205 205 195 399 200 998 404 200 399 200 210 190 399 205 -1 3: 379 200 399 205 205 195 399 200 998 404 200 399 200 210 190 399 205 -1 1 Abs(x)
is de absolute waarde van x
2.5. Conclusie
p. 12
Het eerste resultaat is te verklaren doordat de dummy waarde betekent dat 190 399 205 -1
gelijk is aan 200 399 200 210 en 190 399 205 -1 gelijk is aan 195 399 200 998 zodat ook 200 399 200 210 gelijk is aan 195 399 200 998 . Het langste patroon met alle events is nu niet aanwezig. Dit komt omdat Abs(379-404) =
25 groter is dan de foutmarge 20.
2.4.2
De kleinste foutmarge
We kunnen een algoritme maken dat zelf op zoek gaat naar een foutmarge zodat zo veel mogelijk events (dit aantal wordt op voorhand vastgezet of kan bijvoorbeeld minstens twee derde van het totale aantal events zijn) gebruikt worden. Dit kan gemakkelijk gedaan worden door de foutmarge iteratief te verhogen:
Stel foutmarge gelijk aan 0. Neem twee interonset-waarden zodat Abs(δ i -δ j ) <= foutmarge Ga nu na of voor elke opeenvolgende k, startend vanaf k:=1 geldt:
Abs(δ i+k -δ j+k ) <= foutmarge
Als dit zo is, dan hebben we een herhaling gevonden. Als bovendien geldt dat k == (j-i-1), dan is een aansluitend patroon gevonden. Is geen patroon gevonden of is het langste patroon te kort, verhoog dan de foutmarge en begin opnieuw.
Het gewenste patroon is: 379 200 399 205 205 195 399 200 998
404 200 399 200 210 190 399 205 -1
Om al deze events te gebruiken blijkt dat de foutmarge minstens 25ms moet bedragen.
2.5
Conclusie
We hebben een algoritme voorgesteld dat kan worden uitgebreid om kleine fouten op te vangen zodat er toch een patroon gevonden kan worden. We moeten in principe de gebruiker zelfs niet vragen om expliciet een foutmarge aan te geven, maar kunnen hem vragen hoeveel events er zeker gebruikt moeten worden. Indien de foutmarge dan te groot wordt, is het aan de gebruiker om te oordelen of het daadwerkelijk om een patroon gaat. De technieken beschreven in dit hoofdstuk kunnen enkel toegepast worden op input afkomstig van bijna-perfecte muziek. Indien er in de input een event niet op zijn plaats staat, faalt het vinden
2.5. Conclusie
p. 13
van een patroon. Het algoritme aanziet elke herhaling als patroon. Deze verzameling kan groot zijn, terwijl we ge¨ınteresseerd zijn in slechts ´e´en oplossing. Het selecteren van het beste patroon gaan als volgt: 1. Zoek de patronen die het meeste gebruikt worden: het maximum aantal herhalingen. 2. Indien vorige verzameling geen singleton is, zoek het langste basispatroon: dit heeft het maximum aantal onsets per interval. Bemerk dat het omdraaien van deze stappen niet tot hetzelfde resultaat komt. Indien eerst stap 2 wordt uitgevoerd zullen er lange patronen (veel onsets per rechthoek, cfr. tabel 2.6) worden gevonden, maar deze worden meestal slechts ´e´en maal herhaald.
Hoofdstuk 3
Naar meer realisme 3.0
Introductie
Niet veel artiesten kunnen perfect (zoals een synthesizer) in de maat spelen. Als we dan twee dezelfde patronen moeten onderzoeken op gelijkheid, moet er enige afwijking toegelaten worden om dit probleem aan te pakken. Een methode die ons hiervoor geschikt lijkt is het domein van de vage logica. In dit hoofdstuk zullen we enkele problemen aankaarten die veel voorkomen in live gespeelde muziek. Het moet bijvoorbeeld mogelijk zijn om een noot die niet op zijn plaats staat te negeren en verder te zoeken naar patronen. In sectie 3.3 noemen we dit ruis. Het blijkt dat we die ruis-techniek ook kunnen gebruiken om uit meerdere patronen het beste patroon te vinden.
3.1 3.1.1
Minder strak gespeeld Vage Logica
Om imperfecties op te sporen en te negeren maken we gebruik van vage logica. In de traditionele booleaanse logica is een propositie enkel waar of vals (0 of 1) en niets anders. In de vage logica gebruiken we waarden tussen 0 en 1 om uit te drukken hoe sterk iets waar of vals is. Dit wordt berekend door het gebruik van een lidmaatschapsfunctie. Een grondige studie van vage logica is te vinden in onder meer het werk van Prof. E. E. Kerre [7] of Prof. L. Zadeh [18] .
Het voorbeeld in figuur 3.1 zal wat duidelijkheid scheppen. Bijvoorbeeld voor het begrip is ongeveer 60 jaar oud” zal elke persoon die exact 60 jaar is (punt ” a), de waarde 1 hebben. Personen die net geen 60 zijn (punt b) hebben een kleinere lidmaatschapswaarde (punt c) voor dit begrip. Als we punt p gelijk stellen aan 40 jaar en punt q gelijk stellen aan 80 jaar zullen personen die 20 jaar zijn waarde 0 hebben. Waarmee we van deze personen 14
3.1. Minder strak gespeeld
p. 15
Figuur 3.1: Vage Logica
zeggen dat ze niet ongeveer 60 jaar oud zijn. Het punt a wordt vergeleken met punt b. We krijgen de volgende resultaten voor de possibiliteit dat punt b gelijk is aan punt a:
b=a 1 : b − p : p
(3.1)
De lidmaatschapsfunctie is hier een symmetrische driehoek rondom het punt a met een parameter die de breedte van de driehoek moet voorstellen. Er bestaan verschillende soorten lidmaatschapsfuncties. In figuren 3.2a tot en met 3.2f zijn enkele functies afgebeeld.
3.1.2
Vage Logica toegepast
De manier hoe vage logica verschillende punten van elkaar onderscheidt, is uiterst geschikt om een maat te geven aan patronen die sterk op elkaar gelijken maar het toch niet zijn. Om dit uit te drukken, hebben we een lidmaatschapsfunctie nodig. We gaan op zoek naar, voor onze toepassing,
3.1. Minder strak gespeeld
p. 16
(a) Driehoekige lidmaatschapsfunctie
(b) Kwadratische lidmaatschapsfunctie
(c) Lidmaatschapsfunctie met wortel
(d) Rechte lidmaatschapsfunctie
(e) Assymetrische lidmaatschapsfunctie
(f ) Niet-stijgende lidmaatschapsfunctie
Figuur 3.2: Enkele lidmaatschapsfuncties
3.1. Minder strak gespeeld
p. 17
bruikbare en niet-bruikbare lidmaatschapsfuncties. Een eerste vereiste is dat de functie symmetrisch moet zijn. Er is geen reden dat events die
langs weerskanten even ver van een ander liggen niet dezelfde lidmaatschapsgraad zouden hebben. In figuur 3.2e is een assymetrische functie gebruikt. Het punt a- en het punt a+ hebben niet dezelfde lidmaatschapsgraad, bijgevolg is deze functie niet bruikbaar. Een tweede vereiste is dat de functie stijgend resp. dalend moet zijn langs links resp. rechts
van de top. In figuur 3.2f is er een niet-stijgende functie gebruikt. Het kan nu voorvallen dat een punt b dat dichter gelegen is tot punt a dan een punt c toch een kleinere lidmaatschapsgraad heeft dan punt c. In deze context is er geen reden dat dit wordt toegelaten. Dus dergelijke functies moeten niet gebruikt worden. In elke lidmaatschapsfunctie is een interval als basis te zien. In de figuren van 3.2 is dit interval [p,q]. Om de lidmaatschapsgraad te berekenen tussen twee punten hebben we een waarde nodig voor deze basis. In muziek is een mogelijke keuze de kleinst mogelijke waarde tussen twee opeenvolgende events. Als dit groter is kunnen noten overlappen. In figuur1 3.3 kan noot a nu vergeleken worden
met noot b en met noot c. Als dit kleiner is (figuur 3.4) dan kunnen sommige noten niet vergeleken worden met een
andere. We moeten uiteindelijk toch een keuze maken voor een interval om in de hele analyse te gebruiken. Kleiner dan de kleinste waarde tussen twee opeenvolgende events van alle events (een interonset interval - IOI ) mag dit niet zijn, anders zullen er zeker events zijn die geen tegenkandidaat hebben. Als we ze groter zouden nemen, zullen er intervallen zijn die elkaar overlappen. Dit is niet wenselijk. Onze keuze is het kleinste interonset interval van de te analyseren onsets. De vraag stelt zich nu of er een verschil moet gevonden worden voor het geval dat b dicht bij a ligt en b dicht bij de grenzen p of q (zie figuur 3.1). Met andere woorden, is het wel nodig dat deze gevallen andere lidmaatschapsgraden moeten krijgen? Immers, nu de patronen niet meer perfect in de maat gespeeld zijn, kunnen we niet meer weten wat het” juiste patroon is. In figuur 3.2d ” wordt een rechte lidmaatschapsfunctie gebruikt: alle punten die tussen p en q liggen hebben als lidmaatschapsgraad 1. Het kan toch aangewezen zijn om te weten dat als events toch niet perfect op elkaar liggen, dit dan ook in rekening wordt gebracht. In dit geval kunnen we geen rechthoek gebruiken. 1 Om
berekeningen te maken liggen punten a, b, c uiteraard allemaal op de X-as (op y = 0). Maar om iets
overzichtelijkere figuren te geven plaatsen we punten van een ander patroon iets lager dan de punten uit het patroon waarmee deze vergeleken worden.
3.1. Minder strak gespeeld
Figuur 3.3: Te grote breedte: de intervallen rond b en c overlappen elkaar.
Figuur 3.4: Te kleine breedte: noot c kan niet meer worden vergeleken.
p. 18
3.1. Minder strak gespeeld
p. 19
Nu kunnen we tot een algoritme komen om twee patronen te vergelijken met vage logica en een waarde berekenen in welke mate ze op elkaar gelijken. In figuur 3.5 is te zien hoe we dit doen. Voor elk punt wordt de lidmaatschapsgraad berekend, gebruik makend van een rechte lidmaatschapsfunctie. Punt a2 ligt dicht genoeg bij a1 zodat Poss[a2 =a1 ] = 1. Dit geldt ook voor de andere punten. Om de globale waarde van een patroon met n events te berekenen gebruiken we:
Poss[p(11 , 12 , ..., 1n ) = p(21 , 22 , ..., 2n )] =
1 ∗ (Poss[11 = 21 ] + Poss[12 = 22 ] + ... + Poss[1n = 2n ]) n (3.2)
Uit figuur 3.5: Poss[a1 = a2 ]
= 1
Poss[b1 = b2 ]
= 1
Poss[c1 = c2 ]
= 1
Poss[d1 = d2 ]
= 1
(3.3)
Patroon2 met punten (a2 ,b2 ,c2 ,d2 ) is gelijk aan patroon1 met punten (a1 ,b1 ,c1 ,d1 ) in de mate 1 ∗ (1 + 1 + 1 + 1) = 1. 4 We gebruiken possibiliteiten en geen probabiliteiten. Poss[a=b] = 1 betekent dat het mogelijk is dat a gelijk is aan b, maar het is niet zeker. Prob[a=b] = 1 betekent dat er geen andere mogelijkheid meer is dan dat a gelijk is aan b.
Hetzelfde wordt nu eens gedaan met een driehoekige lidmaatschapsfunctie in figuur 3.6. De possibiliteiten zullen nu niet allemaal 1 zijn. Uit figuur 3.6: Poss[a1 = a2 ]
= 0.58
Poss[b1 = b2 ]
= 0.40
Poss[c1 = c2 ]
= 0.20
Poss[d1 = d2 ]
= 0.62
(3.4)
Patroon2 met punten (a2 ,b2 ,c2 ,d2 ) is gelijk aan patroon1 met punten (a1 ,b1 ,c1 ,d1 ) in de mate 1 ∗ (0.58 + 0.4 + 0.2 + 0.62) = 0.45. 4 Dit is veel slechter dan wanneer we een rechthoekige lidmaatschapsfunctie gebruiken. Dit is enerzijds te verklaren door de lineariteit van de driehoek: hoe verder van het middelpunt, hoe lager de lidmaatschapsgraad is. Exact de helft van de punten in het interval heeft een lidmaatschapsgraad 1 die hoger is dan . 2 Uiteraard heeft het geval met de driehoek meer gelijk dan het geval met de rechthoek als het aantoont dat alle lidmaatschapsgraden niet gelijk zijn aan 1. De twee patronen zijn ook niet perfect
3.1. Minder strak gespeeld
Figuur 3.5: Voor elke 2 noten wordt een possibiliteitsmaat berekend.
Figuur 3.6: Een driehoekige lidmaatschapsfunctie
p. 20
3.1. Minder strak gespeeld
p. 21
gelijk (maar het wordt wel aangenomen dat ze gelijk zijn gezien deze waarde hoger is dan 0).
3.1.3
Vaste intervallengte
Het volgende probleem biedt zich nu aan: op welke plaats in de tijd moeten we knippen om patronen met elkaar te vergelijken. Enerzijds kunnen we een vaste intervallengte gebruiken en vergelijken we de events uit het ene interval met het andere, anderzijds kunnen we een aantal opeenvolgende events bij elkaar nemen en die vergelijken met een volgende groep events van eventueel kortere of langere duur. We bekijken de eerste manier, namelijk twee tijdsintervallen met elkaar vergelijken.
We kunnen nu al van twee patronen uitdrukken hoe sterk ze op elkaar gelijken. Er komt nu bij welke events samen het eerste patroon vormen en welke, volgend op het eerste, het tweede patroon vormen. We zullen dus een goede intervallengte moeten vinden, zodat het liedje volledig uitgelijnd kan worden. In figuur 3.7 hebben we enkele events uit een ritme op een tijdsas geplaatst.
z
z
z
z
z
z
z
z
z
z
Figuur 3.7: De bron-events uitgelijnd in de tijd
We kunnen nu eigenlijk vanaf een beginwaarde (die we zelf op 3 events gekozen hebben uit het algoritme van de perfecte onsets) tot de helft van het liedje (als het eerste interval al langer is dan de helft zullen er op het einde geen events meer overblijven om te vergelijken (figuur 3.8)) alle mogelijkheden gebruiken. z z
z z
z
z
z
z
z
z
Figuur 3.8: Het eerste tijdsinterval is langer dan de helft van het liedje. Er kan geen volgend interval meer gevonden worden om patronen te vergelijken.
We kunnen events indelen in klassen van gelijke tussentijden: voor alle events van een zelfde klasse duurt het even lang tot er nog een ander event komt. Het laatste event van het eerste interval in figuur 3.9 behoort tot de klasse van de minst-langst-durende-events. Wat wilt zeggen dat de duur hiervan - de kleinst mogelijke duur” - gelijk is aan de breedte van de basis die we gebruiken in de ”
3.1. Minder strak gespeeld
p. 22
lidmaatschapsfunctie zoals bvb in figuur 3.1 (=afstand van p tot q met a in het midden). Dus we 1 mogen zeker knippen in het gebied [timestamp,timestamp + * Kleinste Duur], immers het 2 volgende event kan zich pas op een afstand van minimaal Kleinste Duur bevinden. We kiezen natuurlijk zo groot mogelijk om de volgende intervallen zo mooi mogelijk uitgelijnd te krijgen. De uitlijning door te knippen na het 3e event is te zien in figuur 3.9.
z
z
z
z
z
z
z
z
z
z
Figuur 3.9: De bron-events geknipt in gelijke intervallen na het derde event.
Als we terugkeren naar onze input (figuur 3.7) is het 4e event niet een event van kleinst mogelijke ” 1 duur”. Als we daar ook knippen op het tijdstip timestamp + * Kleinste Duur krijgen we iets 2 zoals in figuur 3.10. Het tweede interval vertoont dan nog enigszins een gelijkenis met het eerste interval. Het derde interval is al minder duidelijk gelijk aan het eerste interval. Als we knippen in de helft tussen het 4e en 5e event komen we wel een iets betere uitlijning uit, zoals te zien in figuur 3.11.
z
z
z z
z
z
z
z
z
z
Figuur 3.10: Zomaar ergens knippen na het vierde event levert geen goede uitlijning.
z
z
z
z
z
z
z
z z
z
Figuur 3.11: De bron-events geknipt in gelijke intervallen na het vierde event.
3.1. Minder strak gespeeld
p. 23
Figuur 3.12 toont wat we noemen het beste patroon” omdat dezelfde herhaling in elk interval te ” zien is. Dit is dan ook de beste uitlijning die we graag altijd zouden verkrijgen.
z
z
z
z
z
z
z
z
z
z
Figuur 3.12: De bron-events geknipt in gelijke intervallen na het vijfde event.
Hieruit volgt dat we een goede manier moeten vinden om tijd te knippen. We delen de tijd eerst in in n gelijke intervallen. In figuur 3.13 doen we dit voor de events uit figuur 3.7 met n = 6. Deze n intervallen kunnen we dan samennemen als segmenten waarin we events met elkaar zullen vergelijken. Op het eerste zicht kan dit aantal sterk oplopen. Voor n = 6 hebben we zes mogelijkheden. De vijf uit figuur 3.14 en zichzelf. Per mogelijkheid moeten we de intervallen met elkaar vergelijken. Als we bvb alle intervallen apart nemen, bekomen we 6 segmenten. Dan moet het eerste segment met segment 2,3,4 en 5 vergeken worden. Het tweede segment met 3,4 en 5, enzoverder. Samenvattend voor n = 6: 1 samen: levert 6 segmenten, deze leveren 5+4+3+2+1 = 15 vergelijkingen 2 samen: levert 3 segmenten, deze leveren 2+1 = 3 vergelijkingen 3 samen: levert 2 segmenten, deze leveren 1 vergelijking 4 samen: levert 2 segmenten, deze leveren 1 vergelijking 5 samen: levert 2 segmenten, deze leveren 1 vergelijking 6 samen: levert 1 segmenten, deze levert geen vergelijking
1
z
z
2
z
z
3
z
z
4
z
z
5
z
z
6
Figuur 3.13: De hele tijdsas wordt ingedeeld in 6 gelijke intervallen.
Eigenlijk leveren de vergelijkingen van 4, 5, 6 intervallen samen geen bruikbaar patroon op. In die gevallen is ons eerste segment langer dan de helft waardoor er geen herhaling meer gevonden kan worden. We kunnen dus stoppen met segmenteren vanaf dat we i = ceil(n/2)2 intervallen 2 ceil
is de gehele afronding naar boven van een getal. Bvb ceil(7.3) = 8
3.1. Minder strak gespeeld
p. 24
samengenomen hebben.
1
1 2 3
1 2 3 4
2
4 5 6
5 6
3 4
1 2 1 2 3 4 5
5
3 4 6
6
5 6
Figuur 3.14: Alle 5 mogelijke splitsingen van de intervallen voor fig. 3.13.
De aandachtige lezer zal gemerkt hebben dat met deze manier van samennemen het niet mogelijk is om het beste patroon (fig. 3.12) als resultaat te vinden. Immers 1, 2, 3 en 4, 5, 6 samennemen betekent de uitlijning van figuur 3.15. Van het 6e event is niet duidelijk of het tot het eerste of tweede segment behoort. Voor het 1e event begint is, is er al wat tijd verstreken. Ook na het laatste event is er eigenlijk geen tijd meer te beschouwen aangezien we niet weten hoe lang dit duurt. We zouden de grenzen waartussen we indelen dus links op het eerste event kunnen zetten en rechts op het laatste event. Een andere mogelijkheid is een stapgrootte te voorzien waarmee we iteratief de lengte van een interval vergroten als we beginnen met een kleine lengte voor het eerste interval. Er komt dan enkel nog bij dat we de tijd voor het eerste interval deels of helemaal zullen moeten negeren.
1
z z
4
z
2
z
z
z
z
5
z z
3
z
z
6
Figuur 3.15: 3 intervallen samen geeft 2 segmenten, maar geen perfecte uitlijning.
In principe zouden we per mogelijkheid van samennemen alle vergelijkingen moeten uitvoeren. Dit zullen we later bespreken. Eerst berekenen we hoeveel segmenten er kunnen zijn. We nemen
3.2. Meerdere patronen
p. 25
enkel de bruikbare mogelijkheden: voor n = 6 was dat 1 samen, 2 samen en 3 samen. Als we ze afzonderlijk bekijken, hebben we 6 segmenten, voor 2 samen hebben we er 3, voor 3 samen hebben we er nog 2. Dit alles samen geeft 6+3+2 = 11. Dit kunnen we uitdrukken voor een algemene n: Pceil(n/2) als er n tijdseenheden zijn, zijn er i=1 ceil(n/i) mogelijkheden (eenheidslengte meegerekend en we mogen stoppen als de helft bereikt is). Wensen we dit uit te drukken naar gelang de tijdsduur van het te analyseren audiofragment: stel dat het fragment 20 seconden duurt en onze stapgrootte is 0.01 seconde, dan hebben we Pceil(2000/2) 20 = 2000. Voor n = 2000 geeft dit i=1 ceil(2000/i) = 15499 mogelijke segmenten. 0.01 Deze techniek biedt zich aan om niet-perfect gespeelde liedjes te analyseren. Ook indien er een event niet gedetecteerd is dat er wel zou moeten zijn kunnen we nog verder. Dit komt omdat we eerst twee (of meer) tijdsintervallen vastzetten en daarna pas vergelijken hoe sterk deze intervallen op elkaar lijken. Dit is meteen het verschil met de techniek uit het vorige hoofdstuk. Indien met de vorige manier (het algoritme uit sectie 2.4.1) ergens tussen twee events een te groot verschil bestaat met twee events uit een ander tijdsinterval, zou er zeker geen patroon meer gevonden kunnen worden.
3.2
Meerdere patronen
Eigenlijk is er ook rondom de punten van patroon2 in figuur 3.5 een schelp” te maken waarin pun” ten liggen die vergeleken kunnen worden met punten uit een ander patroon. Dit wordt afgebeeld in figuur 3.16. Dit levert enkele nieuwe combinaties op: punt c2 kan nu vergeleken worden met punt c1 maar ook met punt b1 aangezien hun intervallen overlappen. Als we van c2 veronderstellen dat het overeenkomt met b1 wil dit zeggen dat c2 niet meer overeenkomt met c1 . Ook van b2 kan niet meer gezegd worden dat dit b1 is (aangezien c2 het al is). Dus voor b2 en c1 kan er geen overeenkomstige noot meer gevonden worden. Dit impliceert dat er noten moeten toegevoegd worden. Dit moet natuurlijk een lagere lidmaatschapsgraad hebben dan het geval dat er geen noten moeten toegevoegd worden. Wanneer dit voorvalt stellen we deze noot voor door een X. De possibiliteit is dan gelijk aan een penalty: Poss[b2 =X] = λ, (0 ≤ λ ≤ 1). Samenvattend: 1 ∗ (1 + 1 + 1 + 1) = 1 4 (3.5) 3 + 2λ 1 ∗ (1 + λ + 1 + λ + 1) = Poss[p(a1 , X, b1 , c1 , d1 ) = p(a2 , b2 , c2 , X, d2 )] = 5 5 We kunnen dit ook toepassen op twee noten die elkaars tegenkandidaat zijn (fig 3.17): van deze Poss[p(a1 , b1 , c1 , d1 ) = p(a2 , b2 , c2 , d2 )]
=
twee noten kan dan ook gezegd worden dat ze niet elkaars tegenkandidaat zijn wat betekent dat er dan 2 noten (´e´en voor punt a en ´e´en voor punt b) moeten toegevoegd worden.
3.2. Meerdere patronen
p. 26
Figuur 3.16: Ook rond de te vergelijken punten kan een schelp gemaakt worden.
Figuur 3.17: Twee events, ofwel vergelijken we ze met elkaar ofwel moeten 2 nieuwe events bijgevoegd worden.
3.2. Meerdere patronen
p. 27
Dit geeft: Poss[p(a) = p(b)] =
1 1 Poss[p(X, a) = p(b, X)] = ∗ (λ + λ) = λ (3.6) 2 1 ∗ (λ + λ) = λ Poss[p(a, X) = p(X, b)] = 2 Voor λ=0 zijn deze twee laatste possibiliteiten ook 0, wat wil zeggen dat we niet aanvaarden dat noten die elkaars tegenkandidaat zijn toch ook vergeleken kunnen worden met een ingevoegde noot.
3.2.1
Overlappende oppervlakten
Als we de twee noten van figuur 3.18a nu ver genoeg uit elkaar leggen zodat de ene noot niet meer in het interval ligt van de andere noot kunnen we in principe geen possibiliteitswaarde meer berekenen zoals met de methode van vergelijking 3.1. Immers, het punt b ligt niet meer in het interval [p,q] rond punt a zodat Poss[b=a] = 0. We kunnen rond punt b ook een schelp” maken zoals in figuur 3.18b: een interval dat even breed ” is als het interval [p,q] rond a. Als beide intervallen niet overlappen, herleidt de zaak zich tot het geval zoals in figuur 3.4: Poss[b=a] blijft 0. Overlappen beide intervallen nu wel (fig. 3.19a), dan kunnen we eigenlijk aan deze possibiliteitsmaat toch nog een waarde hoger dan 0 geven. Het is namelijk zo dat b overal in dat interval kan liggen zodat het punt wel nog vergeleken kan worden met punt a. We kunnen bijvoorbeeld de grens van het interval nemen omdat dit het dichtst bij het punt a zal liggen. Zo krijgen we resultaten 3.7. 1: bR − aL : a − aL b − aL : a − aL p = Poss[b = a] = aR − b : aR − a aR − bL : aR − a 0 :
b=a aL < bR < a aL < b < a (3.7) a < b < aR a < bL < aR bR ≤ aL of bL ≥ aR
De waarde van Poss[b=a] is nu niet meer 0 (fig. 3.18b) ook al ligt b niet tussen aL en aR . Maar wat is er nu gebeurd? Stel dat b nu in interval [aL ,j] ligt (j is het snijpunt van bR :
fig.
3.19b met het interval [aL ,a]). Met andere woorden deze b is kleiner dan j maar groter dan aL . De possibiliteitswaarde voor deze situatie zal kleiner zijn ondanks dat b dichter bij a ligt dan voordien (fig. 3.19)! Dit kan natuurlijk niet zijn. Daarom voeren we een nieuwe manier in om de possibiliteitswaarde te berekenen. In plaats van het snijpunt te berekenen, gebruiken we de
3.2. Meerdere patronen
(a) Punt b ligt niet meer in het interval rondom punt
p. 28
(b) De rechtergrens van punt b ligt wel in het interval rondom punt a.
a.
Figuur 3.18: Ook rond punt b kunnen we een interval beschouwen.
(a) b ligt niet in het interval rond a, maar het interval
(b) b ligt tussen aL en j
rond b wel.
Figuur 3.19: In de rechterfiguur ligt b dichter bij a maar heeft toch een lagere waarde voor p.
3.2. Meerdere patronen
p. 29
gemeenschappelijke oppervlakte om een maat van gelijkheid uit te drukken. We maken alle vorige situaties opnieuw en verkrijgen zo de situaties in figuur 3.20. De afstand van aL tot a of van a tot aR noemen we de Half Note Size (HNS). Dit is de helft van de kleinste afstand tussen alle events (zie sectie 3.1.3). Voorts weten we uit vergelijking 3.7 de hoogte van een overblijvende driehoek. Voor de situatie uit figuur 3.20c krijgen we als resultaat:
Overlapping
= = =
Oppervlakte driehoek − Overblijvende driehoek 1 Oppervlakte driehoek − ∗ Overblijvende rechthoek 2 1 1 aR − bR ∗ 2 ∗ HN S ∗ 1 − ∗ (aR − bR ) ∗ 2 2 HN S
Om een waarde tussen 0 en 1 te krijgen, moeten we dit nog delen door de oppervlakte van de driehoek:
Poss[b = a] = 1 −
1 (aR − bR )2 ∗ 2 HN S 2
(3.8)
Analoog voor 3.20d.
Voor de situatie uit figuur 3.20e is dit enkel een kleine driehoek:
Overlapping
= Oppervlakte kleine driehoek 1 ∗ Oppervlakte kleine rechthoek = 2 1 = ∗ basis ∗ hoogte 2 1 bR − aL = ∗ basis ∗ 2 HNS 1 bR − aL = ∗ (bR − aL ) ∗ 2 HNS 1 (bR − aL )2 = ∗ 2 HN S
Om een waarde tussen 0 en 1 te krijgen, moeten we dit nog delen door de oppervlakte van de driehoek:
Poss[b = a] =
1 (bR − aL )2 ∗ 2 HN S 2
(3.9)
3.2. Meerdere patronen
p. 30
(a) Helemaal
(b) Niets
(c) Meer dan de helft
(d) Meer dan de helft
(e) Minder dan de helft
(f ) Minder dan de helft
Figuur 3.20: Alle mogelijke overlappeningen
3.3. Ruis
p. 31
Analoog voor 3.20f.
Samengevat (zie figuur 3.21): 1: (aR − bR )2 : 1 − 2 ∗ HN S22 1 − (bL − aL ) : 2 ∗ HN S2 Poss[b = a] = 2 (b − a ) R L : 2 ∗ HN S 22 (aR − bL ) : 2 ∗ HN S 2 0 :
b=a aL < b < a a < b < aR
(3.10)
b < aL < bR b L < aR < b bR < aL of bL > aR
We hebben nu een manier gevonden om twee events te vergelijken naar gelang hun afstand tot elkaar. We houden bovendien rekening met de mogelijkheid dat hun positie niet exact is, maar dat een event overal in een interval kan liggen. De formule om intervallen van n events met elkaar te vergelijken blijft dezelfde:
Poss[p(11 , 12 , ..., 1n ) = p(21 , 22 , ..., 2n )] =
3.3 3.3.1
1 ∗ (Poss[11 = 21 ] + Poss[12 = 22 ] + ... + Poss[1n = 2n ]) n (3.11)
Ruis Onduidelijkheden in patroon
Met onduidelijkheden bedoelen we events die zich niet op regelmatige basis herhalen. In het ruisloze voorbeeld van figuur 3.22a is de mate waarin elk patroon op elk ander patroon lijkt gelijk aan 1 zoals te zien in tabel 3.1. Dit betekent dat elk patroon een perfecte match is met het andere: nergens moest een event bijgevoegd worden. Introduceren we ruis in dit patroon, dan bekomen we de resultaten in tabel 3.2 overeenkomstig met figuur 3.22b. De fout λ is dezelfde zoals die ge¨ıntroduceerd is in sectie 3.2. Er moeten namelijk in de andere patronen events bijgevoegd worden om tot hetzelfde patroon te komen. Een bekende manier die hier toegepast zou kunnen worden is de zogenaamde edit-distance [9] - een algoritme dat vooral gebruikt wordt om tekst te vergelijken zoals in een spellingchecker. De operaties om een edit-distance te berekenen zijn: toevoegen van een letter, verwijderen van een letter, een letter in een andere letter veranderen. Om patronen in elkaar te transformeren gebruiken we volgende mogelijkheden: toevoegen van een event, verwijderen van een event of gelijkstellen van twee events. Het toevoegen of verwijderen zal de strafmaat introduceren.
3.3. Ruis
p. 32
Figuur 3.21: b ligt niet in het interval rond a, maar het interval rond b wel.
Voor patroon1 en patroon2 geeft dit bijvoorbeeld 5 events die matchen en 1 toevoeging (bes5+λ te mogelijkheid): . Als slechtste mogelijkheid geeft dit 0 matches en 11 toevoegingen: 5+1 0 + 11 ∗ λ = λ. 11 Uit tabel 3.2 kunnen we nu het” patroon vinden door te classificeren in klassen. Als we naar de ” totale afstand kijken per lijn, krijgen we uiteindelijk nog drie verschillende: patronen(2,3,4,6,8), patronen(1,7), patronen(5). Omdat in dit geval de patronen(2,3,4,6,8) het meeste voorkomen noemen we het” patroon hier een patroon van de vorm zoals patroon2 uit figuur 3.22b. ”
Pat 1
Pat 2
Pat 3
Pat 4
Pat 5
Pat 6
Pat 7
Pat 8
Pat 1
1
1
1
1
1
1
1
1
Pat 2
1
1
1
1
1
1
1
1
Pat 3
1
1
1
1
1
1
1
1
Pat 4
1
1
1
1
1
1
1
1
Pat 5
1
1
1
1
1
1
1
1
Pat 6
1
1
1
1
1
1
1
1
Pat 7
1
1
1
1
1
1
1
1
Pat 8
1
1
1
1
1
1
1
1
Tabel 3.1: Perfecte matches tussen patronen uit figuur 3.22a.
3.3. Ruis
p. 33
1
z
z
z
z
z
1
z
2
z
z
z
z
z
2
3
z
z
z
z
z
4
z
z
z
z
5
z
z
z
6
z
z
7
z
8
z
z
z
z
z
z
z
z
z
z
3
z
z
z
z
z
z
4
z
z
z
z
z
z
z
5
z
z
z
z
z
z
z
6
z
z
z
z
z
z
z
z
z
7
z
z
z
z
z
z
z
z
z
8
z
z
z
z
z
(a) Een patroon netjes herhaald.
z v
z v
z v
z v
z
(b) Ruis toegevoegd, gemerkt door een witte bol.
Figuur 3.22: Bijna hetzelfde liedje
Pat 1 Pat 1 Pat 2 Pat 3 Pat 4 Pat 5 Pat 6 Pat 7 Pat 8
1 5+λ 6 5+λ 6 5+λ 6 5+λ 6 5+λ 6 1 5+λ 6
Pat 2 5+λ 6 1
Pat 3 5+λ 6 1
Pat 4 5+λ 6 1
1
1
1
1 5+2∗λ 7 1 5+λ 6 1
1 5+2∗λ 7 1 5+λ 6 1
1 5+2∗λ 7 1 5+λ 6 1
Pat 5 5+λ 6 5+2∗λ 7 5+2∗λ 7 5+2∗λ 7 1 5+2∗λ 7 5+λ 6 5+2∗λ 7
Pat 6 5+λ 6 1 1 1 5+2∗λ 7 1 5+λ 6 1
Pat 7 1 5+λ 6 5+λ 6 5+λ 6 5+λ 6 5+λ 6 1 5+λ 6
Pat 8 5+λ 6 1 1 1 5+2∗λ 7 1 5+λ 6 1
Tabel 3.2: Maat voor match tussen patronen uit figuur 3.22b.
Stel dat ons lied nu bestaat uit evenveel patronen van de vormen uit figuur 3.23. De zogenaamde ruis die we ge¨ıntroduceerd hebben blijkt meer dan slechts een aantal keer voor te komen. Geven we nu als output voor het” patroon het eerste, tweede of derde of alle drie? Uiteindelijk komen ” ze alle drie even waarschijnlijk voor, dus hebben ze alle drie recht op de benaming van het” ” patroon. Kijken we toch eens naar de afstand tussen de drie patronen in tabel 3.3. We berekenen het 5 5 gemiddelde per rij. Voor λ dicht bij 0 komt dit neer op voor patroon1 en patroon3 : (1 + + )/3 6 7
3.4. Pauze
p. 34
5 5 voor patroon2 : ( + 1 + )/3 ofwel 0.85 en 0.89. Met andere woorden patroon2 heeft het minste 6 6 werk nodig om zich te transformeren in patroon1 of patroon3 . We slaan dus patroon2 op en noemen dit het” gevonden patroon. ”
1
z
2 3
z v
z
z
z
z
z
z
z
z
z
z
z
z
z
v z
Pat 1 Pat 1 Pat 2
z
Pat 3
1 5+λ 6 5+2∗λ 7
Pat 2 5+λ 6 1 5+λ 6
Pat 3 5+2∗λ 7 5+λ 6 1
Figuur 3.23: Evenveel voorkomende patroTabel 3.3: Afstand tussen patronen uit finen in het liedje, maar toch guur 3.23. verschillend van elkaar.
3.4
Pauze
Met een pauze bedoelen we een korte tijd waarin geen events te bespeuren zijn. We kunnen twee soorten onderscheiden: een pauze in de maat, zodat na de pauze het patroon weer op een normale manier verder gaat of een pauze zodat het patroon niet meer mooi uitgelijnd is.
3.4.1
Perfecte pauze
Met een perfecte pauze hebben we niet veel last: deze duurt net zo lang (of een veelvoud hiervan) als het interval waar het patroon in past en zorgt dat de events na de pauze mooi gealigneerd blijven (fig. 3.24). Het algoritme zal nu wel zoeken naar events in deze pauze en volgens de methode uit sectie 3.2 overal events willen toevoegen aan dit interval.
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
Figuur 3.24: De pauze duurt net zo lang als een patroon.
Voor een interval met n events moeten er n events bijgedacht worden in het pauze-interval. De n∗λ afstand tussen deze twee intervallen is dan = λ. n
3.5. Algortime
3.5
p. 35
Algortime
Nu we enkele theoretische inzichten gegeven hebben, is het de bedoeling om tot een algoritme te komen dat kan ge¨ımplementeerd worden. We starten met het vastleggen van de intervallengte. We zullen de hele tijdsas van events opdelen in subintervallen van deze lengte. Het zullen deze subintervallen zijn die we met elkaar gaan vergelijken om hopelijk een herhalend patroon te vinden. Het vergelijken van twee intervallen gebeurt op de manier zoals uitgelegd in sectie 3.2.1. 1. Bereken de huidige intervallengte:
start vanaf een minimum tot de laatste
timestamp. Bereken de linkergrens van het eerste interval.
De rechtergrens is linkergrens
+ intervallengte. Zoek alle events in dit interval.
2. Zoek alle events die 1 tot n intervallengtes verder liggen.
We kunnen n
laten stoppen als de linksgrens van dit interval voorbij de laatste timestamp gaat. Per interval wordt via de techniek van overlappende oppervlakken een waarde van gelijkheid berekend.
3. Zoek de optimale combinatie van matches en inserts voor deze twee intervallen. Alle mogelijkheden worden geconstrueerd en daarna gecontroleerd.
De beste
hangt af van de strafmaat van een insert bewerking.
4. Alle intervallen zijn gecontroleerd.
Zoek nu van al deze intervallen de
basis die aanleiding geeft tot het minst werk om zich te transformeren in alle andere intervallen.
5. Houd alle basispatronen bij.
Het beste patroon kan hieruit geslecteerd worden:
a) het beste op vlak van aantal gebruike onsets b) het beste op vlak van aantal keer dat het gebruikt wordt
3.6. Conclusie
p. 36
c) het beste op vlak van het werk nodig om zich te transformeren Verschillende combinaties van deze drie mogelijkheden levert steeds een ander resultaat als beste patroon.
3.6
Conclusie
We hebben een inleiding tot de vage logica gegeven wat ons hielp om events te vergelijken. Deze manier hebben we uitgebreid om een waarde van gelijkheid te berekenen aan de hand van de grootte van overlappende oppervlakten. Het bleek nodig te zijn om bij events die geen gelijke hebben er toch een event bij te denken zodat het interval als patroon aanzien kon worden. De andere mogelijkheid, het negeren van het event, lieten we niet in aanmerking komen. Eens we patronen gevonden hebben, kunnen we nu ook berekenen hoe sterk deze patronen op elkaar lijken en geven het patroon terug dat het minste werk nodig heeft om zich te transformeren in de andere kandidaten. Om het beste patroon als resultaat te geven blijkt dat er toch nog een keuze gemaakt moet worden. De eindgebruiker kan hierin zelf kiezen: wilt hij als beste patroon een kort, veel herhaald patroon? Een patroon dat lang is en veel onsets gebruikt? We zullen later (zie hoofdstuk 5) door de praktijk te toetsen aan de theorie een standaardkeuze instellen die het meest intu¨ıtieve patroon weergeeft als resultaat.
Hoofdstuk 4
Toepassingen 4.0
Introductie
We overlopen enkele toepassingen die uit het voorgaande voortvloeien. We bekijken hoe we de onsets kunnen aanwenden om meer informatie over de gevonden patronen te vinden. We leggen uit hoe we het tempo kunnen afleiden uit de onsets in sectie 4.1. Verder leggen we uit hoe we verschillende inputs kunnen vergelijken door het patroon te normaliseren (sectie 4.2) en daarna te vergelijken (sectie 4.3).
4.1
Tempo afleiden
Als we een tempo en een maatsoort hebben, dan kunnen we berekenen hoelang een noot duurt. Stel dat het tempo 120BPM is en de maatsoort
7
. Dit betekent dat er zeven 4e noten zijn
4 per maat en dat er 120 4e noten zijn per minuut. Dus ´e´en 4e noot duurt 60s/120 = een halve seconde. Wat hieruit opvalt is dat de maatsoort er niet toe doet. De indeling in maten hebben we dus niet nodig. 60 = duur van een vierde tempo 60 Of nog: tempo = duur van een vierde
We vinden dus:
Uit het gevonden patroon kunnen we het tempo afleiden. We berekenen de kleinste tussentijd tussen de events in het patroon. Als we deze in de bovenstaande vergelijking gebruiken komen we het tempo uit. Dit zal evenwel een niet-standaard tempo zijn. Bvb is de kleinste tussen-tijd 0.200s dan is 60/0.200 = 300. Een tempo van 300BPM wordt algemeen niet gebruikt. Maar 300/4 = 150/2 = 75BPM. Eigenlijk zijn 300BPM, 150BPM en 75BPM in weze allen hetzelfde tempo, wat
37
4.2. Genormaliseerd patroon
p. 38
het begrip tempo iets subjectiefs maakt. Een uitgebreide studie over het cognitieve tempo vindt u in Extracting the perceptual tempo from music” [11] . ” Het valt op te merken dat met deze techniek het patroon niet gevonden moet worden. We kunnen ook van de input data (alle onsets) de tussentijden berekenen en van hieruit vertrekken. Dit kan zelfs een exacter resultaat opleveren omdat we over meer informatie beschikken. Een tijd van 0.200s komt exact overeen met 150BPM, maar een kleine afwijking levert snel grove fouten op: 60/0.190 = 315,789BPM wat in muziek een groot verschil betekent t.o.v. 300BPM. Als we nu een classificatie algoritme kunnen vinden dat slim genoeg is om bepaalde waarden zoals 0.190 om te zetten naar 0.200, krijgen we het exacte tempo. In tabel 4.1 staan waarden uit een realistisch voorbeeld afgekapt op drie decimalen.
De juiste bruikbare waarden bij elkaar genomen geeft uiteindelijk volgende klassen: 379 400 met exacte waarde: 400 en gemiddelde waarde: 389.5 200 205 205 195 200 met exacte waarde: 200 en gemiddelde waarde: 201
Merk op dat de waarden in klasse 1 eigenlijk een veelvoud beschrijven van klasse 2. Als we deze informatie gebruiken krijgen we: 189.5 200 200 205 205 195 200 met gemiddelde waarde: 199.21
Als we deze waarden gebruiken om het tempo te berekenen krijgen we: 60/0.201 = 298,507 en 60/0.19921 = 301,19 met respectievelijke fouten 1,493BPM en 1,19BPM, wat voor live muziek niet hoorbaar is.
Opmerking over triolen: Voor musicologen zal deze aanpak van tempo afleiding niet als muziek in de oren klinken. Immers dit klopt alleen voor hele, halve, vierde, ... noten en niet voor triolen. Een triool zijn drie noten per tel. Voor een tempo van 150BPM zal een triool ook 0.400 seconden duren, dus per noot van die triool is dit 0.4/3 seconden. Dit levert een kleinere delta op (0.133) t.o.v. de gehele 0.200. Met de bovenstaande redenering is het tempo dan 60/0.133 = 450BPM = 112.5BPM geworden i.p.v. 150BPM. Dit is wederom een kwestie van interpretatie van het muziekstuk en de maatsoort en is uiteindelijk iets subjectiefs. Meer hierover in Extracting the perceptual tempo from music” [11] . ”
4.2
Genormaliseerd patroon
Eens we een patroon uit een liedje gehaald hebben, kunnen we dit bewaren. Het is de bedoeling om een grote collectie van patronen aan te leggen, dus is een eenvoudige, transparante opslag-methode
4.2. Genormaliseerd patroon
p. 39
Event
Onset
delta
afgerond
werkelijk
1
0.025
0.379
379
400
2
0.404
0.200
200
200
3
0.604
0.399
400
400
4
1.003
0.205
205
200
5
1.207
0.205
205
200
6
1.412
0.195
195
200
7
1.606
0.399
400
400
8
2.005
0.200
200
200
9
2.205
0.998
1
1
10
3.203
Tabel 4.1: Classificatie van tussentijden
nodig. Elk patroon zal immers verschillen in totale duur, tempo en aantal events. Het verband tussen deze drie eigenschappen is reeds aangetoond in sectie 4.1, met name dat het tempo niet afhangt van de totale duur van een patroon en enkel afhangt van de kleinste δ tussen de events. Het tempo hebben we evenwel al berekend voor we op zoek gaan naar een patroon. We kunnen dus met de totale duur van de gevonden patronen spelen als we het tempo ook bijhouden. Zo kunnen we elk patroon dat in de databank voorkomt herschalen naar een tijdsinterval [0,t]. De t nieuwe tijdstippen worden dan: event0 = ∗ event. Toegepast op een voorbeeld geeft totale duur dit het resultaat uit tabel 4.2.
Event
OnsetTime
Herschaald
1
0.025
0.045
2
0.404
0.733
3
0.604
1.095
4
1.003
1.819
5
1.207
2.190
6
1.412
2.561
7
1.606
2.914
8
2.005
3.638
9
2.205
4
Tabel 4.2: Herschaald =
4 ∗ OnsetT ime 2.205
4.3. Patronen vergelijken
p. 40
Met deze functie worden de events enkel herschaald. Ook is het eerste event niet gelijk aan 0. Een betere herschaling is alle punten in een interval [a,b] af te beelden op [c,d]. Voor elk punt geldt d−c d−c +d−b∗ . Gebruik makend van de voorwaarden f(a)=c en f(b)=d en dan: y = x ∗ b−a b−a x−a c=0 en d=gewenste lengte geeft dit nog y = d ∗ . Deze herschaling is te zien in tabel 4.3. b−a
Event
OnsetTime
Herschaald
1
0.025
0
2
0.404
0.696
3
0.604
1.062
4
1.003
1.794
5
1.207
2.169
6
1.412
2.545
7
1.606
2.902
8
2.005
3.634
9
2.205
4
Tabel 4.3: Herschaald = 4 ∗
OnsetT ime − 0.025 2.205 − 0.025
Met de afspraak om het tijdstip van het eerste event gelijk te stellen aan 0 en het laatste event gelijk aan t, moeten we deze twee events niet opslaan in de databank. Elke berekening met komma getallen is een berekening te veel wegens afkapping- en afrondingsfouten door de computer. In het voorbeeld is d = 4 genomen wat wilt zeggen dat elk patroon uitgerokken wordt zodat het 4 seconden duurt.
4.3
Patronen vergelijken
Nu we veel problemen met de input hebben besproken en er ook manieren zijn om erop te reageren kunnen we het eigenlijke doel uitproberen: een gebruiker die in een databank van liedjes zoekt naar meer informatie over dat ritme of andere stukken die er op lijken. Eerst moet een databank aangemaakt worden. De stukken die gebruikt worden zijn de werken uit het Koninklijk Museum voor Midden-Afrika. Van al deze werken genereren we eenmalig de onsets via de Drum detection ” console applications” [13] . Deze onsets geven we eenmalig aan ons programma die als output het gevonden patroon geeft in dezelfde vorm als een inputbestand. We doen hetzelfde met de input van de gebruiker. Hiervoor moet de applicatie een manier vinden om onsets te genereren uit de opgegeven audio (bvb via een microfoon afkomstig van de
4.3. Patronen vergelijken
p. 41
stem [6] , [12] ), dan patroon genereren. Dit moeten we nu vergelijken met de patronen uit de databank. Methodes om dit te doen zijn besproken in het vorige hoofdstuk. Hierbij kunnen we alle patronen vergelijken of een slimmere methode ontwikkelen zodat niet alle patronen uitgeprobeerd moeten worden. Afhankelijk van afspraken kunnen we verzamelingen maken van patronen die veel of weinig kans hebben om erop te lijken. We hebben al enkele parameters die we kunnen gebruiken: het tempo kan vergeleken worden, alsook het aantal events in het patroon.
Verder moeten we beseffen dat begin en einde van een patroon niet eenduidig vast staat. Een gebruiker kan starten in het midden van een patroon om zo ook een patroon te vormen (fig. 4.1). Dit lossen we op door elk patroon circulair te zien, zodat geen sprake meer is van start en einde (fig. 4.2). Hierbij moeten we wel opletten met de voorstelling van het patroon zoals in sectie 4.2, meer bepaald de duur van het laatste event. Deze kan zo kort of zo lang zijn als gewenst aangezien er geen event meer na komt. Als natuurlijk een patroon gevonden is dat, na zichzelf geplaatst, het hele lied omslaat (er zitten dus geen events meer tussen de patronen), kan de gebruikte dummywaarde berekend worden en de echte lengte van het patroon gevonden worden.
z
1
z
z
z
2
z
z
z
z
z
z
Figuur 4.1: Deze twee patronen lijken niet op elkaar.
z
z z z
1
z
z
z
z
z
z
z
z
z
z
z
z z
z
z
z
z
z
z
z
z
z
z
z
z z
z z
z z
z
z z
z
z z
z
z
z
2
z
z z
z z
z z
z
Figuur 4.2: Circulair bekijken van patroon2 levert toch patroon1 op.
4.4. Gemiddeld patroon
4.4
p. 42
Gemiddeld patroon
De timestamps in het uiteindelijk gevonden patroon zijn dezelfde als die van het patroon waarmee de rest van de patronen worden vergeleken. Deze patronen verschillen nog van elkaar. Voor elk event van het” patroon hebben we eigenlijk meerdere timestamps (gescheiden door een zekere ” afstand) waarmee dit overeenkomt. Als echte” timestamp per event zouden we het gemiddelde ” kunnen nemen van al deze timestamps en dit als output geven. Dit doen we in figuur 4.3.
1
z
zz z
2
z
z
z
3
z
z
4
z
z
z z
z z
z
z
z z
z
Figuur 4.3: Als output-timestamp geven we het gemiddelde van de timestamps van de basispatronen.
Omgekeerd (bvb een gebruiker die 1 van de originelen als te zoeken patroon opgeeft) is het zo dat elk van deze patronen 100% gelijk zijn aan elkaar door onze methode van vergelijking (sec. 3.2). Het berekenen van dit gemiddelde was dan eigenlijk niet nodig, aangezien de gebruiker enkel wilt weten of er een match was of niet.
Hoofdstuk 5
Software 5.0
Introductie
In dit hoofdstuk zullen we de geschreven software, die deel uitmaakte van de opdracht, testen en vergelijken met een andere techniek om patronen te vinden in data, namelijk de autocorrelatie. We hebben naar de fragmenten geluisterd en een manuele annotatie opgesteld van het ritme dat er gespeeld wordt. De uitkomsten van beide technieken worden hiermee vergeleken.
5.1
Code
Een print-out van de code is vervat in een apart boek als bijlage bij dit boek. De command line opties zijn te vinden in bijlage A om zo via parameters de werking van de algoritmes te be¨ınvloeden. De output naar een bestand gebeurt in hetzelfde formaat als de input (sectie A.3) en kan verder verwerkt worden met de Drum detection console applications” [13] om bijvoorbeeld ” een MIDI bestand aan te maken. Het algoritme dat standaard wordt gebruikt, komt voort uit de idee¨en van hoofdstuk 3. De andere algoritmes worden niet getest, omdat deze gebaseerd zijn op hoofdstuk 2 en niet bedoeld zijn voor echte muziek.
5.2
Output
Om de output van het programma te bespreken, gebruiken we muziekvoorbeeld 2.1 met als gedetecteerde onsets tabel 2.1. Output: Tempo: 79.12679425837408
43
5.2. Output
p. 44
Half Note Size: 0.09478458049886518 timeL 0.0 0.2 0.6 0.0 0.1 0.5 0.7 1.1 0.0 0.4 0.6 1.0 0.1 0.3 0.5 0.7 0.9 0.2 0.4 0.6 0.8 0.1 0.3 0.5 0.7 0.0 0.2 0.4 0.6 0.1 0.3 0.5 0.0 0.2 0.4 0.1 0.3 0.0 0.2 0.4 0.1 0.3
timeR 2.0 2.2 2.6 2.1 2.2 2.6 2.8 3.2 2.2 2.6 2.8 3.2 2.4 2.6 2.8 3.0 3.2 2.6 2.8 3.0 3.2 2.6 2.8 3.0 3.2 2.6 2.8 3.0 3.2 2.8 3.0 3.2 2.8 3.0 3.2 3.0 3.2 3.0 3.2 3.4 3.2 3.4
grad 0.79 0.78 0.8 0.82 0.8 0.85 0.78 0.78 0.85 0.82 0.76 0.82 0.76 0.87 0.76 0.76 0.87 0.87 0.8 0.8 0.87 0.87 0.78 0.78 0.87 0.84 0.78 0.77 0.91 0.77 0.77 0.91 0.75 0.77 0.96 0.77 0.96 0.76 0.96 0.77 0.96 0.77
#herh 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#ind 13 13 12 14 12 13 13 13 13 14 14 14 14 15 14 14 15 15 15 15 15 15 16 16 15 16 16 17 16 17 17 16 18 17 17 17 17 18 17 17 17 17
basisindices 0123456 1234567 2345678 01234567 1234567 2345678 345678 45678 01234567 12345678 2345678 345678 12345678 12345678 2345678 345678 345678 12345678 12345678 2345678 345678 12345678 12345678 2345678 345678 01234567 12345678 12345678 2345678 12345678 12345678 2345678 01234567 12345678 12345678 12345678 12345678 01234567 12345678 12345678 12345678 12345678
8
8
8 9 9
5.2. Output
p. 45 timeL 0.0 0.2 0.1 0.0 0.4 0.3 0.0 0.2 0.1 0.0 0.0
timeR 3.2 3.4 3.4 3.4 3.8 3.8 3.6 3.8 3.8 3.8 4.2
grad 1.0 0.77 0.77 0.76 0.77 0.77 0.75 0.77 0.77 0.8 0.75
#herh 1 1 1 1 1 1 1 1 1 1 1
#ind 18 17 17 18 17 17 18 17 17 18 18
basisindices 01234567 12345678 12345678 01234567 12345678 12345678 01234567 12345678 12345678 01234567 01234567
8 9 9 8 9 9 8 9 9 8 8
9 10 10 9 10 10 9 10 9 10 11
Tabel 5.1: Alle gevonden patronen uit tabel 2.1.
Tabel 5.1 toont de output van de software. timeL en timeR staan voor de grenzen van het tijdsinterval van het eerste interval waar het patroon te vinden is. In de volgende kolom wordt de gradatie getoond zoals beschreven in sectie 3.3. Er is een minimale gradatie van 0.5 vastgelegd als standaardparameter. Herhalingen met een lagere gradatie komen dan niet in aanmerking. De kolom herhaling betekent hoeveel maal dit basispatroon nog eens weerkomt. Indien deze waarde 1 is, wilt dit zeggen dat dit patroon tweemaal in heel het liedje terugkomt. Er is ook nog een kolom met het aantal indices dat dit patroon omslaat. Bijvoorbeeld: de laatste rij gebruikt 18 indices, maar het basispatroon bestaat uit 12 events. Dus in de eerste herhaling van dit patroon zijn er nog 6 events te matchen en zullen er 6 bijgedacht worden (zoals beschreven in sectie 3.3). De laatste kolom zijn de basisindices. Uit alle herhalingen worden de indices gezocht die het makkelijkst te transformeren zijn in alle andere herhalingen. Dit wordt het basispatroon genoemd en zijn (herschaalde) timestamps worden naar een bestand geschreven. We spreken hier van indices: de eerste timestamp heeft index 0.
Resultaat: t=[0.0, 3.2] grad:
1.0 herh:
1 ind:
18 basis:
0 1 2 3 4 5 6 7 8
Inderdaad, dit is de gewenste output. Als we kijken in de tabel zijn er nog meerdere intervallen die dit basispatroon bevatten: t=[0.0, 2.6] grad:
0.84 herh:
1 ind:
16 basis:
0 1 2 3 4 5 6 7 8
Dit is duidelijk: er zijn minder indices gebruikt. Dit willen we vermijden om als beste” patroon ” te krijgen. t=[0.0, 2.8] grad:
0.75 herh:
1 ind:
18 basis:
0 1 2 3 4 5 6 7 8
t=[0.0, 3.0] grad:
0.76 herh:
1 ind:
18 basis:
0 1 2 3 4 5 6 7 8
5.2. Output
p. 46
In interval [2.2, 3.2] (net voor event 9) zijn er helemaal geen events meer. Event 8 is het laatste event dat geselecteerd wordt om een patroon te vormen. We zoeken verder naar een interval dat met dit patroon gematched kan worden. Event 17 zal met event 8 gematched worden. Event 17 is het allerlaatste event en heeft dus geen bijhorende delta waarde. Dit hebben we opgelost door een dummy-waarde te gebruiken die elk mogelijke waarde kan zijn. Vandaar dat deze intervallen ook tussen de mogelijkheden staan. Waarom hebben deze twee dan toch een lagere gradatie gekregen dan het” patroon? Dit komt doordat we intervallen van vaste lengte gebruiken. Als het ” eerste interval loopt van 0.0 tot 3.2 zal het volgende interval dat we onderzoeken van 3.2 tot 6.4 lopen (eindpunt van het eene is het beginpunt van het andere, en beide zijn ze gelijk in lengte). De events in dit interval zullen gematched worden met de events uit het eerste interval. Als we dit doen voor het interval [0.0, 2.8] zullen de events uit [2.8, 5.6] schever staan ten opzichte van het eerste interval en dus een kleinere possibiliteitswaarde krijgen (zoals beschreven in sectie 3.2.1).
Ruis Als test gaan we langzaamaan de input verslechten. We beginnen met een event achteraan toe te voegen op t=5.6. Dit geeft als resultaat: t=[0.0, 3.2] grad:
0.96 herh:
1 ind:
19 basis:
0 1 2 3 4 5 6 7 8
Dit is hetzelfde als het origineel. We voegen nog een event toe op t=5.8: t=[0.0, 3.2] grad:
0.93 herh:
1 ind:
20 basis:
0 1 2 3 4 5 6 7 8
De gradatie neemt geleidelijk af, aangezien de toegevoegde events geen echte match hebben. We blijven events toevoegen met als stapgrootte 0.2 seconden tot het basispatroon verandert. We hebben nu 5 events toegevoegd, de output van het beste patroon is: t=[0.0, 3.2] grad:
0.86 herh:
1 ind:
23 basis:
0 1 2 3 4 5 6 7 8
t=[0.0, 4.2] grad:
0.86 herh:
1 ind:
23 basis:
0 1 2 3 4 5 6 7 8 9 10 11
We hebben nu meerdere kandidaat-basispatronen gevonden. Indices 9, 10 en 11 komen eigenlijk overeen met respectievelijk indices 0, 1, 2. Maar aangezien ons algoritme denkt dat de toegevoegde events ook goed kunnen zijn, kunnen 9, 10 en 11 ook gematched worden met deze toegevoegde events. Uiteraard weten wij dat deze events foutief zijn, maar het algoritme niet. We nemen de output tabel met alle gevonden basispatronen er nog eens bij (tabel 5.2): Tempo: 79.12679425837408 Half Note Size: 0.09478458049886518
timeL 0.0 0.2
timeR 2.0 2.2
grad 0.79 0.88
#herh 1 1
#ind 16 17
basisindices 0123456 1234567
5.2. Output timeL 0.4 0.6 0.8 0.0 0.1 0.2 0.4 0.5 0.6 0.7 1.1 0.0 0.2 0.4 0.6 1.0 0.0 0.1 0.2 0.3 0.4 0.5 0.7 0.9 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.1 0.3 0.5 0.7 0.9 0.0 0.2 0.4 0.6 0.8 0.1 0.3 0.5
p. 47 timeR 2.4 2.6 2.8 2.1 2.2 2.3 2.5 2.6 2.7 2.8 3.2 2.2 2.4 2.6 2.8 3.2 2.3 2.4 2.5 2.6 2.7 2.8 3.0 3.2 2.4 2.6 2.8 3.0 3.2 3.4 2.5 2.6 2.8 3.0 3.2 3.4 2.6 2.8 3.0 3.2 3.4 2.8 3.0 3.2
grad 0.8 0.75 0.76 0.92 0.8 0.8 0.77 0.85 0.8 0.78 0.78 0.8 0.77 0.77 0.68 0.82 0.8 0.76 0.84 0.87 0.8 0.76 0.76 0.87 0.88 0.78 0.8 0.8 0.84 0.77 0.79 0.87 0.78 0.78 0.84 0.77 0.75 0.78 0.75 0.85 0.75 0.77 0.75 0.85
#herh 1 2 1 1 1 1 1 1 1 1 1 2 1 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1
#ind 18 21 14 18 12 18 17 13 15 13 13 23 17 22 21 14 18 14 16 15 15 14 14 15 17 22 15 15 16 17 16 15 16 16 16 17 23 16 18 18 18 17 18 18
basisindices 12345678 9 10 11 12 13 345678 01234567 1234567 12345678 12345678 2345678 2345678 345678 45678 01234567 12345678 12345678 9 10 11 12 13 14 15 345678 012345678 12345678 12345678 12345678 12345678 2345678 345678 345678 012345678 12345678 12345678 2345678 345678 3456789 012345678 12345678 12345678 2345678 345678 3456789 012345678 12345678 12345678 2345678 3456789 12345678 12345678 2345678
5.2. Output
p. 48
timeL 0.7 0.4 0.3 0.2 0.6 0.1 0.5 0.0 0.6 1.0 0.5 0.9 0.4 0.6 0.8 0.3 0.5 0.7 0.0 0.2 0.4 0.6 0.1 0.3 0.5 0.0 0.2 0.4 0.1 0.3 0.0 0.2 0.1 0.0 0.0 0.0
timeR 3.4 3.2 3.2 3.2 3.6 3.2 3.6 3.2 3.8 4.2 3.8 4.2 3.8 4.0 4.2 3.8 4.0 4.2 3.6 3.8 4.0 4.2 3.8 4.0 4.2 3.8 4.0 4.2 4.0 4.2 4.0 4.2 4.2 4.2 4.4 4.8
grad 0.75 0.87 0.87 0.85 0.76 0.85 0.76 0.86 0.76 0.77 0.76 0.77 0.79 0.76 0.77 0.79 0.76 0.77 0.77 0.79 0.79 0.8 0.79 0.79 0.8 0.81 0.79 0.83 0.79 0.83 0.78 0.83 0.83 0.86 0.77 0.77
#herh 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#ind 18 20 20 21 21 21 21 23 21 20 21 20 22 21 20 22 21 20 23 22 22 21 22 22 21 23 22 22 22 22 23 22 22 23 23 23
basisindices 3456789 12345678 12345678 12345678 23456789 12345678 23456789 012345678 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 0123456789 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Tabel 5.2: Alle gevonden patronen uit tabel 2.1 met toegevoegde ruis.
Wat ons opvalt is dat het beste patroon dat we geven, niet de hoogste gradatie heeft. Het resultaat met hoogste gradatie is: t=[0.0, 2.1] grad:
0.92 herh:
1 ind:
18 basis:
0 1 2 3 4 5 6 7
5.3. Autocorrelatie
p. 49
Dit komt omdat er verschillende pistes zijn om het beste” patroon te selecteren. We kunnen ” vragen om het patroon te selecteren dat het meeste indices gebruikt, maar niet noodzakelijk de hoogste gradatie heeft. (Dit is de voorgaande manier.) We kunnen eerst selecteren op hoogste gradatie, en dan pas op het aantal gebruikte indices. Met deze manier wordt het zo juist beschreven patroon gegeven. We zouden ook een selectie kunnen maken naar het aantal keer dat een patroon herhaald wordt. Het is dan niet ondenkbaar dat in langere werken korte patronen meer terug komen terwijl we graag een lang patroon zouden hebben. Het zal moeten blijken uit de tests welke manier van bevragen de beste is om het intu¨ıtieve patroon weer te geven. Welke manier we uiteindelijk gebruiken staat in sectie 5.6.
5.3
Autocorrelatie
Definitie autocorrelatie: voor een bepaalde verschuiving betekent een hoge waarde van autocorrelatie dat er in de data een periode is te vinden van lengte gelijk aan die verschuiving. Autocorrelatie bemonstert het signaal (deelt het in in gelijke intervallen). Als er een event in dat interval voorkomt krijgt dit de waarde 1, zo niet de waarde 0. Eventueel kan er per event een convolutie gemaakt worden. In ons geval gaan we ervan uit dat er 1 of geen event per interval voorkomt. Dit verkrijgen we door intervallengte = 50ms te nemen. 50ms is ongeveer de grens voor het menselijk gehoor om twee aparte events uit elkaar te houden. Hierdoor is een convolutie niet meer nodig. We hebben uit de oorspronkelijke audiobestanden fragmenten van 20 seconden genomen en hierop onze tests uitgevoerd. We berekenen in Matlab eerst de autocorrelatie. Dit kan lineair (xcorr) of circulair (ifft) gebeuren. Circulair zal het deel dat afvalt van het einde van de verschuiving weer in het begin invoegen, terwijl bij het lineaire geval in het begin enkel nullen worden ingevoegd. Bvb: input 10100001010000. We vermelden ook (aantal verschuivingen, waarde). 10100001010000 (0,4) 01010000101000 (1,0) 00101000010100 (2,2) 00010100001010 (3,0) 00001010000101 (4,0) en zo verder. De volgende verschuiving leidt tot 00000101000010 (lineaire) of tot 10000101000010 (circulair). Om de autocorrelatie te berekenen van onze fragmenten hebben we het volgende Matlab script gebruikt:
5.3. Autocorrelatie
p. 50
function myauto(name,data)
%lineair %%%%%%%% [c_ww,lags] = xcorr(data,’none’); pic = figure;
%maak figuur
stem( lags(ceil(length(lags)/2):length(lags)), c_ww(ceil(length(c_ww)/2):length(c_ww)),’k’,’f’);
print(pic,’-dpng’,[name,’.png’]) %schrijf grafiek naar bestand fp = fopen([name,’.txt’],’w’); for i = ceil(length(c_ww)/2) : length(c_ww) fprintf(fp,’%.0f & %.0f\\\\\r\n’,lags(i),c_ww(i)); %schrijf data naar bestand end fclose(fp);
%circulair %%%%%%%%%%% cor = ifft(conj(fft(data)).*fft(data)); pic2 = figure; stem(cor,’k’,’f’);
print(pic2,’-dpng’,[name,’.circ.png’]) %schrijf grafiek naar bestand fp = fopen([name,’.circ.txt’],’w’); for i = 0 : length(cor)-1 fprintf(fp,’%.0f & %.0f\\\\\r\n’,i,cor(i+1)); %schrijf data naar bestand end fclose(fp); Beide functies zijn symmetrisch rond de Y-as (we kunnen de data zowel naar rechts als naar links verschuiven). Bij het circulaire geval is de uitkomst ook nog eens symmetrisch vanaf de helft van de lengte van de data (figuur 5.1b). De maxima blijven evenwel bij dezelfde verschuivingen. Het is dan niet nodig om de autocorrelatie circulair uit te rekenen. We gebruiken de lineaire manier (figuur 5.1a). Hiervan zoeken we een passend maximum en delen de input data in intervallen volgens de verschuiving die tot dit maximum leidt. Per interval zijn er ´e´en of meerdere cijfers 1 waarmee een onset overeenstemt. We nemen het eerste interval en geven dit terug als resultaat voor het basispatroon.
5.3. Autocorrelatie
(a) Lineaire autocorrelatie
p. 51
(b) Circulaire autocorrelatie is symmetrisch vanaf de helft
Figuur 5.1: De maxima zijn bij beide gevallen op dezelfde X te vinden
Dezelfde onsets voeren we in voor de software en nemen het resultaat dat dit geeft over. Deze twee uitkomsten vergelijken we dan met elkaar en berekenen we hoe zeker beide technieken zijn over hun patroon. Verder hebben we manueel de ritmes van de fragmenten geannoteerd in muzieknoten. Dit hebben we niet voor de resultaten van de technieken gedaan. In de plaats daarvan hebben we de basispatronen op een tijdsas gezet. Zo zien we meestal het verschil tussen een vierde en een achtste noot: een vierde duurt tweemaal zo lang als een achtste. Dit vergelijken we dan met de ground truth (de manuele annotatie).
Als voorbeeld voor een berekening van autocorrelatie gebruiken we tabel 2.1.
5.3. Autocorrelatie
p. 52
Figuur 5.2: Autocorrelatie van tabel 2.1
In figuur 5.2 zijn verschillende pieken te zien. De software geeft als beste patroon (tabel 5.1) indices 0 tot en met 8 weer. De hoogste Y-waarde in de grafiek is 12 voor X=12. De input gesplitst over deze 12 geeft het volgende: 100000001000 100000001000 100010001000 000010001000 000000000000 000010000000 100010000000 100010001000 100000001000 10
Elke 1 in deze rij komt overeen met een gedetecteerde onset uit de audio. In dit geval betekent de eerste lijn dat slechts de eerste twee events (indices 0 en 1) samengenomen worden en aanzien worden als herhalend patroon.
5.3. Autocorrelatie
p. 53
Omgekeerd zoeken we eens naar waar het 9e event begint (het beste zoals aangegeven door onze software). Dat is voor (X,Y) = (64,9): 1000000010001000000010001000100010000000100010000000000000000000 1000000010001000000010001000100010000000100010 Y=9 komt ook voor bij X=32: 10000000100010000000100010001000 10000000100010000000000000000000 10000000100010000000100010001000 10000000100010 Dit zijn indices 0 1 2 3 4 5, een patroon dat zelfs niet voorkomt in de output van de software, omdat het geen goed genoeg resultaat oplevert. Immers in de 2e en 4e lijn zijn er veel events die geen match hebben, wat zal resulteren in een te lage gradatie. Dat de autocorrelatie in dit voorbeeld geen goed resultaat geeft, is te wijten aan het aantal herhalingen: het patroon wordt slechts tweemaal herhaald, terwijl de gebruikte noten in het patroon onderling niet hard van elkaar verschillen. We doen eens hetzelfde maar zetten het patroon 18 maal achter elkaar. Dit geeft figuur 5.3. Hier zien we pieken om de 64 verschuivingen. Dit geeft als resultaat inderdaad de gezochte herhaling.
Figuur 5.3: Meer herhaling geeft een beter overzicht
5.4. Tests en vergelijkingen
5.4
p. 54
Tests en vergelijkingen
We vergelijken de output van de software met de techniek van autocorrelatie. Zo kunnen we een beeld vormen van welke techniek in welke gevallen beter scoort. Eerst nemen we enkele zelfgemaakte testcases uit het voorgaande gedeelte onder handen. Daarna volgen de tests met muziekvoorbeelden uit de collectie van het Koninklijk Museum voor Midden-Afrika te Tervuren (zie bijlage B).
5.4.1
Zelfgemaakte Voorbeelden
Tabel 2.2
Figuur 5.4: Autocorrelatie van onsets van tabel 2.2
De maxima in de verschuivingen van de autocorrelatie: (X,Y) = (12,12), (20,11) X=12 geeft aanleiding tot een kort patroon. Dit komt omdat het patroon slechts tweemaal herhaald wordt in de input zoals aangegeven in figuur 5.3. 100000001000 100000001000 100010001000 000010001000
5.4. Tests en vergelijkingen
p. 55
000000000000 000010000000 100010000000 100010001000 100000001000 10
Dit betekent de volgende indices: 0 1
De software geeft als resultaat: [0.0, 3.2] grad: 1.00 herh: 1 ind: 18 basis: 0 1 2 3 4 5 6 7 8 [0.2, 2.2] grad: 0.69 herh: 2 ind: 17 basis: 1 2 3 4 5 6 7 Als we eerst sorteren op aantal indices en dan op gradatie, dan krijgen we het eerste resultaat. Als we eerst sorteren op aantal herhalingen, dan krijgen we het tweede resultaat. Het eerste is het patroon dat we wensen te verkrijgen, dit heeft zelfs een gradatie = 1, terwijl het meest herhaalde patroon korter is, niet alle events kan gebruiken en een lagere gradatie heeft. z z z zz zzzz zz
M ˇ ˇ( ˇ ˇ( ˇ( ˇ( ˇ ˇ( ˇ
? >
Figuur 5.5: Autocorrelatie vs Software vs Ground Truth
De software geeft hetzelfde resultaat als de ground truth en geeft zelfs aan dat het een 100% exacte match is. Doordat het patroon te weinig wordt herhaald, geeft de autocorrelatie een kort patroon.
5.4. Tests en vergelijkingen
p. 56
Patroon uit 3.22a
Figuur 5.6: Autocorrelatie van onsets van patroon uit 3.22a
Er is een duidelijke herhaling te zien. Het maximum ligt op (X,Y) = (80,35). X=80 heeft 35/40 = 88% matches, bovendien zijn het de eerste 5 die verantwoordelijk zijn voor niet alle 40 matches (omdat we geen circulaire autocorrelatie beschouwen). X=80 geeft aanleiding tot de volgende splitsing: 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 000000000010000000000000000000100000000010000000001000000000000000000010
Dit betekent de volgende indices: 0 1 2 3 4
De software geeft als resultaat:
5.4. Tests en vergelijkingen
p. 57
[0.0, 4.0] grad: 1.00 herh: 7 ind: 40 basis: 10 11 12 13 14 [0.0, 2.0] grad: 0.87 herh: 15 ind: 40 basis: 0 1 In [0.0, 4.0] zitten de events met indices 0 1 2 3 4, het resultaat van de autocorrelatie. Beide technieken geven hetzelfde patroon, al heeft het patroon van de software wel een gradatie van 1. Als we kijken naar het meest herhaalde patroon van de software, bestaat dit uit slechts 2 events met een lage gradatie. z z
z
z
z
z
z
z
z z
M ˇ ˇ( ˇ( ˇ ˇ Figuur 5.7: Autocorrelatie vs Software vs Ground Truth
Circulair gezien geven beide technieken hetzelfde resultaat als de ground truth.
5.4. Tests en vergelijkingen
p. 58
Patroon uit 3.22b
Figuur 5.8: Autocorrelatie van onsets van patroon uit 3.22b
Dit is hetzelfde ritme als het voorgaande voorbeeld, maar met hier en daar wat ruis toegevoegd. De maxima in de verschuivingen van de autocorrelatie: (X,Y) = (20,35), (80,35) X=20 geeft aanleiding tot een kort patroon, wat niet wenselijk is. X=80 geeft bijna hetzelfde resultaat als in het vorig voorbeeld. 00000000001000000000100000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000100000000010000000001000000000100000000010000000001000000000 00000000001000000000000000000010000000001000000000100000000000000000001000000000 00000000001000000000100000000010000000001000000000100000000000000000001000000000 000000000010000000000000000000100000000010000000001000000000000000000010
Dit betekent de volgende indices: 0 1 2 3 4 5 Er is nu ´e´en event meer gebruikt, omdat in de eerste lijn de ruis al voorkomt.
5.4. Tests en vergelijkingen
p. 59
De software geeft als resultaat: [0.0, 2.0] grad: 0.83 herh: 15 ind: 44 basis: 3 4 5 Er is geen patroon gevonden met gradatie ´e´en. Het patroon dat het meest herhaald wordt, bestaat slechts uit drie events. Als we eerst sorteren op gradatie, verkrijgen we dit resultaat: [0.0, 4.0] grad: 0.94 herh: 7 ind: 44 basis: 6 7 8 9 10
z z
z
z
z
z
z
z
z
z z
M ˇ ˇ( ˇ( ˇ ˇ( ˇ ˇ( ˇ Figuur 5.9: Autocorrelatie vs Software vs Ground Truth
Beide technieken kunnen de ground truth als resultaat geven. Voor de software moet opgemerkt worden dat we dit resultaat enkel verkregen hebben door een andere volgorde van zoeken in de oplossingverzameling te gebruiken.
5.4. Tests en vergelijkingen
p. 60
Partituur 6.2
Figuur 5.10: Autocorrelatie van onsets van partituur 6.2
Daar dit stuk nogal kort is, zetten we het patroon meteen viermaal na elkaar. Het maximum in de verschuivingen van de autocorrelatie: (X,Y) = (120,18) Dit geeft aanleiding tot de volgende opsplitsing: 100000010000000100 ..(70 nullen)..
01000000010000000100000000000000
100000010000000100 ..(70 nullen)..
01000000010000000100000000000000
100000010000000100 ..(70 nullen)..
01000000010000000100000000000000
100000010000000100 ..(70 nullen)..
0100000001000000010
Dit betekent de volgende indices: 0 1 2 3 4 5
De software geeft als resultaat: [0.1, 2.1] grad: 0.76 herh: 7 ind: 23 basis: 1 2 Dit zijn slechts twee noten samengenomen. Als we kijken naar resultaten met gradatie 1: [0.1, 3.3] grad: 1.00 herh: 1 ind: 4 basis: 1 2 [0.0, 2.4] grad: 1.00 herh: 1 ind: 6 basis: 0 1 2 [0.0, 3.6] grad: 1.00 herh: 1 ind: 6 basis: 0 1 2
5.4. Tests en vergelijkingen
p. 61
[0.0, 4.0] grad: 1.00 herh: 1 ind: 6 basis: 0 1 2 [0.0, 2.0] grad: 1.00 herh: 3 ind: 12 basis: 18 19 20 [0.0, 3.0] grad: 1.00 herh: 3 ind: 12 basis: 18 19 20 [0.0, 6.0] grad: 1.00 herh: 3 ind: 24 basis: 18 19 20 21 22 23 We hadden graag als resultaat gezien dat de helft samengenomen zou worden van de partituur (6.2). Inderdaad, het laatste resultaat geeft dit patroon weer. Het gebruikt ook alle 24 indices, daarom gebruiken we dit als oplossing. z z z
z z z
z z z
z z z
M ˇ( ˇ( ˇ
> > > >
ˇ( ˇ( ˇ
Figuur 5.11: Autocorrelatie vs Software vs Ground Truth
Autocorrelatie en software geven exact hetzelfde resultaat. Tevens zijn ze gelijk aan de ground truth.
5.4. Tests en vergelijkingen
5.4.2
Muziekfragmenten
73.9.1 - 8 - 20s
Figuur 5.12: Autocorrelatie van onsets van 73.9.1 - 8 - 20s
De maximale verschuiving van de autocorrelatie: (X,Y) = (24,16) en (96,16) Het eerste maximum ligt op X=24. Dit geeft aanleiding tot de volgende opsplitsing: 10010000000001000000001 00000000000010000000001 00001000000001000000001 00001000000001000000001 00000000000010000000000 01000001000000010000000 01000010000000001000000 00010000100000000100000 00001000010000000001000 00000010000010000000100 00100100001000001000010 00000001000010000100010
p. 62
5.4. Tests en vergelijkingen
p. 63
00000000001000000000000 10000000001000100000000 01000000001000010000000 00100000000100000100010 00010000000001000001000 0000100000000010000010
Dit betekent de volgende indices: 0 1 2 3
De software geeft als resultaat: [0.0, 4.8] grad: 0.76 herh: 3 ind: 50 basis: 38 39 40 41 42 43 44 45 46 47 48 49 Was X=96 gekozen als splitsing bij de autocorrelatie zou dit indices 0 .. 11 geweest zijn. In [0.0, 4.8] zitten enkel indices 0 .. 11. Zo zouden beide technieken hetzelfde resultaat opgeleverd kunnen hebben. De software is zeker van 50/54 = 93% events tov 16/54 = 29% bij de autocorrelatie. zz z
z z zz
z zz
z z zzz
z
M ˇ( ˇ( ˇ( ˇ ˇ( ˇ( ˇ( ˇ Figuur 5.13: Autocorrelatie vs Software vs Ground Truth
Beide technieken komen niet in de buurt van de ground truth. Zelfs het subpatroon wordt niet gevonden.
5.4. Tests en vergelijkingen
p. 64
73.9.1 - 9 - 20s
Figuur 5.14: Autocorrelatie van onsets van 73.9.1 - 9 - 20s
De maxima in de verschuivingen van de autocorrelatie: (X,Y) = (9,28), (18,22), (45,21), (54,22) X=9 geeft aanleiding tot een heel kort basispatroon (indices 0,1,2), maar kan zo 28/55 = 51% events matchen. Alle andere maxima komen voor bij veelvouden van 9. X=54 geeft aanleiding tot de volgende opsplitsing met 22/55 = 40% events gematched: 100100001000000001000000000000010000100000000100000000 000001000010000000100000000010001000100000000100001000 010001000010000000010000000010001000010000000010001000 010001000010000000010000000010001000010000000100000000 001001000010000000010000000001000100001000000001000000 000000100010000000000100000000100010000100000000100000 000100000000100000000100000000100000000100000000100000 0010000000010
Dit betekent de volgende indices: 0 .. 6
De software geeft als resultaat:
5.4. Tests en vergelijkingen
p. 65
[0.1, 2.8] grad: 0.77 herh: 5 ind: 46 basis: 32 .. 39 Dit betekent dat er 46 van de 55 onsets gematched kunnen worden. Dit is 82% tov 39/55 = 71%. zzz z
zz z
zzz z
zzz z
M ˇ ˇ( ˇ( ˇ ˇ( ˇ ˇ( ˇ Figuur 5.15: Autocorrelatie vs Software vs Ground Truth
Autocorrelatie en software geven bijna exact hetzelfde resultaat. Tevens zijn ze (circulair gezien) zo goed als gelijk aan de ground truth. 73.9.10 - 5 - 20s
Figuur 5.16: Autocorrelatie van onsets van 73.9.10 - 5 - 20s
De top 4 van de maxima in de verschuivingen van de autocorrelatie: (X,Y) = (59,15), (15,14), (25,12), (119,10)
5.4. Tests en vergelijkingen
p. 66
Gebruiken we X=59 geeft dit aanleiding tot de volgende opsplitsing met 15/41 = 37%: 01000010001000010000000001000000000000001000000000100000000 00000010001000010000000010000000000000010000000001000010000 00000100001000010000000010000000000000010000000001000010001 00000100000000000000000010000000000000001000001000100010000 00000100000100000000000001000000000000000100000000100001000 00000010000000000000000000100000000000000100000000010000000 00000001000000000000000000010000000000000010
Dit betekent de volgende indices: 0 .. 6
De software geeft als resultaat: [0.0, 2.7] grad: 0.67 herh: 3 ind: 26 basis: 0 1 2 3 4 5 6 Dit betekent dat er 26 van de 41 onsets gematched kunnen worden: 63%. zzzz
z
z
z
zzzz
z
z
z
M ˇ( ˇ ˇ ˇ( ˇ ˇ > Figuur 5.17: Autocorrelatie vs Software vs Ground Truth
Het resultaat voor het patroon is bij beide technieken dezelfde maar dit komt niet overeen met de ground truth.
5.4. Tests en vergelijkingen
p. 67
73.9.11 - 9 - 20s
Figuur 5.18: Autocorrelatie van onsets van 73.9.11 - 9 - 20s
Opmerkelijke pieken: (X,Y) = (9,18), (14,16), (23,14), (32,14), (55,20), (111,14) X=55 geeft de meeste matches (20/49 = 41%). X=111 is het dubbele van 55 daarom dat we X=55 gebruiken (wat een patroon van lengte 55 betekent). Dit geeft aanleiding tot de volgende opsplitsing: 1000000100000000000000000100001001000001000010000100010 0000100100000000000000000010001000001001000000001000010 0000000100000000000000000010000100000000100010000100001 0000000010000000000000000001000000000000010000000010001 0000000010000000000000000001000010000000010000000010001 0000000001000000000000000001000000001000010001000010001 0000010001000000000000000001000000000000010000000100001 0000000010
Dit betekent de volgende indices: 0 .. 8
De software geeft als resultaat:
5.4. Tests en vergelijkingen
p. 68
[0.3, 3.9] grad: 0.70 herh: 3 ind: 35 basis: 1 .. 10 Dit resultaat geeft aanleiding tot een gebruik van 35/49 = 71% events tov 41% van de autocorrelatie. z z z
zzz zzzz zzz zzzz zz
M ˇ ( ˇ˜¨ ˇ ˇ ( ˇ ˇ >
Figuur 5.19: Autocorrelatie vs Software vs Ground Truth
Het resultaat van de autocorrelatie en de software komen bijna overeen. De software geeft een iets langer patroon. De ground truth is ook niet altijd zeker van het gespeelde patroon. Alleen door het weglaten van enkele noten kunnen de gevonden resultaten overeenstemmen met de ground truth.
5.4. Tests en vergelijkingen
p. 69
73.9.12 - 5 - 20s
Figuur 5.20: Autocorrelatie van onsets van 73.9.12 - 5 - 20s
Opmerkelijke pieken: (X,Y) = (25,18), (34,17), (58,20), (116,18) Het maximum is voor X=58 en 20/50 = 40% events gebruikt. Dit geeft aanleiding tot de volgende opsplitsing: 1000100000100000000010000000001000000001000010000000001000 0000100010000000000010001000010000000010000100000000010000 0001000001000000000100000000010000000010000010000000010000 0001000001000100000100000000010000000010000100000000010000 0001000010000000000100000000000000000010000010000000010000 0000100001000000000100000000010000000001000100000000010010 000100000100000000010000000000000000001000010
Dit betekent de volgende indices: 0 .. 7
De software geeft als resultaat: [0.0, 2.9] grad: 0.85 herh: 6 ind: 50 basis: 16 .. 22 Dit geeft aanleiding tot het gebruik van alle indices. Bovendien betekent interval [0.0, 2.9] het
5.4. Tests en vergelijkingen
p. 70
gebruik van indices 0 .. 7 zodoende kunnen we stellen dat in dit geval autocorrelatie hetzelfde resultaat oplevert als de software. zz z
z
z zz z
zz
z
z zz z
M ˇ( ˇ ˇ ˇ ˇ( ˇ ˇ Figuur 5.21: Autocorrelatie vs Software vs Ground Truth
Beide technieken komen tot dezelfde indeling, enkel het basispatroon is anders. Het basispatroon van de software is wel gelijk aan de ground truth. 73.9.14 - 9 - 20s
Figuur 5.22: Autocorrelatie van onsets van 73.9.14 - 9 - 20s
Opmerkelijke pieken: (X,Y) = (9,28), (27,27) Dit geeft aanleiding tot de volgende opsplitsing:
5.4. Tests en vergelijkingen
p. 71
100100001000000001000000000 000010000100000000100000000 000001000010000000100000000 010001000100000000100001000 010001000010000000010000000 010001000010000000010001000 010001000010000000010000000 010001000010000000100000000 001001000010000000010000000 001000100001000000001000000 000000100010000000000100000 000100010000100000000100000 000100000000100000000100000 000100000000100000000100000 0010000000010 Dit betekent de volgende indices: 0 1 2 3
De software geeft als resultaat: [0.0, 2.2] grad: 0.83 herh: 6 ind: 54 basis: 14 15 16 17 18 19 20 21
zzz z zzzz
M ˇ( ˇ ˇ
z zzz
ˇ ( ˇ ( ˜¨ˇ ( ˇ ( ˇ˜¨ ( ˇ ( ˇ ( ˜¨ˇ ( ˇ ( ˜¨ˇ (
Figuur 5.23: Autocorrelatie vs Software vs Ground Truth
Er worden eigenlijk twee ritmes gespeeld. Het tweede ritme bevat zachtere noten (tussen haakjes genoteerd). Deze twee ritmes kunnen niet uit elkaar gehouden worden. Het resultaat van de autocorrelatie komt in de buurt van het eerste fragment van de ground truth. De software doet zijn best om zo veel mogelijk indices te bereiken met dit patroon en slaagt daar wel in: 54/55 = 98%. Het resultaat neigt naar het tweede ritme in de ground truth, met rusten waar zachte noten gespeeld worden.
5.4. Tests en vergelijkingen
p. 72
73.9.15 - 7 - 20s
Figuur 5.24: Autocorrelatie van onsets van 73.9.15 - 7 - 20s
Er zijn in het begin enkele pieken die dicht bij elkaar zijn: (X,Y) = (9,33), (13,34), (18,30), (22,32) Het maximum ligt bij X=13 wat een vrij kort patroon zal betekenen. Dit geeft aanleiding tot de volgende opsplitsing: 0010001000100 0100010000100 0000000100000 0001000100010 0001000100001 0001000000001 0001000010000 1001000010000 1000000001000 0000100001000 0100010001000 0100001000000 0100000000100
5.4. Tests en vergelijkingen
p. 73
0010000100010 0010000100000 0010000100000 0001000010001 0000100100001 0000100000001 0000000010001 0000100010001 0000100010000 1000100000000 1000010001000 0100100001000 0100000001000 0000010000000 0100010001000 1000010000000 0100000000100 01000010
Dit betekent de volgende indices: 0 1 2
De software geeft als resultaat: [0.1, 2.3] grad: 0.81 herh: 8 ind: 73 basis: 25 26 27 28 29 30 31 32 Het resultaat van de software is veel langer (8) dan van de autocorrelatie (3), maar het kan wel alle 73 events matchen met dit patroon tov 34/73 = 47% bij autocorrelatie. zzz zzzz z zzz
M ˇ( ˇ( ˇ( ˇ( Figuur 5.25: Autocorrelatie vs Software vs Ground Truth
Het ritme bestaat uit dezelfde noten. Het is voor beide technieken niet mogelijk om te berekenen hoeveel noten er tot het patroon horen. Hier en daar zijn er gaten tijdens het ritme wat het
5.4. Tests en vergelijkingen
p. 74
resultaat van de software aangeeft. De software is in staat om soms events bij te denken om andere intervallen te matchen en dit gebeurt hier ook. Zo kan het alle events uit de input matchen. Beide resultaten zijn goed. 73.9.2 - 4 - 20s
Figuur 5.26: Autocorrelatie van onsets van 73.9.2 - 4 - 20s
Opmerkelijke pieken: (X,Y) = (19,24), (38,28), (76,23) Het maximum ligt op X=38 en geeft aanleiding tot de volgende opsplitsing: 00001000010000100000000100001000010000 00001000000001000000010000001000100000 00001000000001000000100000001000100000 00010000000000010000000100010000100000 00010000000001000000001000010000100000 00010000000001000000000100010000100000 00010000000001000010001000010000100000 00010000000001000000100000010000100000 00010000000001000010010000010001000000 00100000100000010001000000010001000000
5.4. Tests en vergelijkingen
p. 75
00100000000010
Dit betekent de volgende indices: 0 1 2 3 4 5
De software geeft als resultaat: [0.0, 2.2] grad: 0.71 herh: 5 ind: 38 basis: 0 1 2 3 4 5 6 Beide technieken geven een ander resultaat. zzz zzz zzz zzz z
M ˇ( ˇ( ˇ ˇ˛
? >
ˇ( ˇ( ˇ
> >
Figuur 5.27: Autocorrelatie vs Software vs Ground Truth
In dit fragment zijn twee aparte ritmes tegelijk hoorbaar. Het is moeilijk om deze gescheiden te houden en zeker gescheiden van elkaar te detecteren. Beide technieken komen in de buurt van de ground truth, maar zijn niet gelijk. Circulair gezien komt de software wel goed in de buurt van de ground truth.
5.4. Tests en vergelijkingen 73.9.20 - 9 - 20s
Figuur 5.28: Autocorrelatie van onsets van 73.9.20 - 9 - 20s
Er zijn weer niet veel pieken te onderscheiden. Het maximum ligt op: (X,Y) = (21,32) Dit geeft aanleiding tot de volgende opsplitsing: 100100001000010000010 000100000000000000000 000000001000000000010 000010000100000000010 000010000100000100010 000000010010000100000 000000000100001000000 000001000010000100001 000000100010000000000 100000000001000100000 100000000010000100000 100001000001000010000 100000100001000010000 100000100001000010000
p. 76
5.4. Tests en vergelijkingen
p. 77
010000000001000001000 010000100001000001000 010000100001000001000 010000100001000001000 0100001000001000010
Dit betekent de volgende indices: 0 1 2 3 4
De software geeft als patronen die het meest herhaald worden: [0.4, 2.5] grad: 0.79 herh: 4 ind: 33 basis: 38 39 40 41 42 43 44 [0.1, 2.3] grad: 0.67 herh: 4 ind: 34 basis: 1 2 3 4 5 [0.1, 2.4] grad: 0.70 herh: 4 ind: 33 basis: 1 2 3 4 5 [0.3, 4.0] grad: 0.81 herh: 4 ind: 57 basis: 45 .. 58 Het laatste is eigenlijk het” resultaat: het wordt evenveel herhaald als de andere, maar geeft ” aanleiding tot 57/63 = 90% matches. Het negeert evenwel de eerste twee events. In [0.3, 4.0] zitten indices 2 .. 9: acht events terwijl de basis er 14 telt. Overeenstemmend met index 9 (het 10e event) zou de autocorrelatie moeten splitsen tussen X=73 of X=82. In dat interval zijn er twee lokale maxima: (74,25) en (79,22). zzz z zz
z zzzz zzzz zzz
M ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( Figuur 5.29: Autocorrelatie vs Software vs Ground Truth
In dit fragment bestaat het patroon uit opeenvolgende achtste noten, zoals aangegeven door de ground truth. De autocorrelatie is te herleiden tot de helft van de ground truth (of een opeenvolging van vier achtste noten). De software geeft meer herhalingen weer van achtsten. Bovendien betekent het begin van de notatie dat er wat ruis is: er zit wat meer tijd tussen de eerste drie dan bij de rest.
5.4. Tests en vergelijkingen
p. 78
73.9.22 - 6 - 20s
Figuur 5.30: Autocorrelatie van onsets van 73.9.22 - 6 - 20s
Opmerkelijke pieken: (X,Y) = (10,18), (15,16), (35,20), (50,16) X=10 betekent dat er slechts 1 event als patroon bekeken wordt. Dit aanvaarden we niet. X=35 geeft het maximum: 20/46 = 44%. Dit geeft aanleiding tot de volgende opsplitsing: 10000000001000010000000001000010000 10000000001000000000000001000000001 00000100000000100000000001000000001 00001000000000100000000010000100000 00000100000000100000000010000100000 00001000000000100001000000000100000 00001000000000010000000000000010000 00001000000100000000010000000010000 00000100001000000000010000010010000 10000000001000000000010000000001000 10000000001000000000100000100000000 010
5.4. Tests en vergelijkingen
p. 79
Dit betekent de volgende indices: 0 .. 4
De software geeft als resultaat: [0.0, 3.0] grad: 0.76 herh: 6 ind: 46 basis: 27 .. 33 In [0.0, 3.0] zitten indices 0 .. 6. Dit zou overeenkomen met de autocorrelatie als X=50 was gebruikt. z
zz
z z z
zz z z
zz
M ˇ( ˇ ˇ ˇ( ˇ ˇ ˇ Figuur 5.31: Autocorrelatie vs Software vs Ground Truth
Als we het patroon circulair bekijken blijkt dat het resultaat van de software gelijk is aan de ground truth. Ook circulair bekijken van het resultaat van de autocorrelatie blijkt geen (zelfs niet deels) match te zijn met de ground truth.
5.4. Tests en vergelijkingen 73.9.22 - 8 - 20s
Figuur 5.32: Autocorrelatie van onsets van 73.9.22 - 8 - 20s
Opmerkelijke pieken: (X,Y) = (10,20), (61,20) X=10 zou slechts 1 event betekenen. X=61 geeft aanleiding tot de volgende opsplitsing: 1000000000100010000000000100000000100000000010000100000000010 0001000000000100001000010000000000100010001000001000000000010 0000000100000100000000100000000001000000000100000100000000010 0000000010001000000000010000100001000000000100000100010000010 0010000000000100000000010000010000100000000100000100001000010 0000100010000100010000010000000000100000000100001000000000010 0000000010000100000000010
Dit betekent de volgende indices: 0 .. 7
De software geeft als resultaat: [0.3, 2.5] grad: 0.71 herh: 4 ind: 29 basis: 44 45 46 47 48 49 [0.4, 2.7] grad: 0.74 herh: 4 ind: 32 basis: 20 21 22 23 24 [0.1, 4.2] grad: 0.67 herh: 4 ind: 53 basis: 1 2 3 4 5 6 7 8 9 10
p. 80
5.4. Tests en vergelijkingen
p. 81
Het laatste resultaat is langer dan de autocorrelatie, maar dit patroon leidt tot een match van 53/54 = 98% events. z zz
zz
z z
z z
zz
zz
z
zz
zz
M ˇ( ˇ ˇ ˇ( ˇ ˇ ˇ Figuur 5.33: Autocorrelatie vs Software vs Ground Truth
In dit muziekfragment zijn twee verschillende percussielijnen te horen. Het is dan moeilijk om beide ritmes te onderscheiden. De software geeft een lang patroon als resultaat en is iets anders dan de ground truth. Circulair bekijken van het resultaat van de autocorrelatie geeft ook niet de ground truth. z
zz
z
z
Figuur 5.34: Software resultaat met hogere gradatie
In dit voorbeeld zien we de impact van het toelaten van niet-matches. In de software heeft dit tot gevolg het bijrekenen van een strafmaat en een lagere gradatie, maar een hoger aantal events die gebruikt kunnen worden (zoals het derde resultaat: 98%). In figuur 5.34 is het tweede resultaat (indices 20 .. 24) op een tijdsas gezet. Dit patroon is iets korter dan de ground truth maar is er wel een submatch van.
5.4. Tests en vergelijkingen 73.9.24 - 1 - 20s
Figuur 5.35: Autocorrelatie van onsets van 73.9.24 - 1 - 20s
Er zijn geen echte uitschieters te zien. Het maximum ligt bij (X,Y) = (32,27) Dit geeft aanleiding tot de volgende opsplitsing: 10001001001001000100000100000010 00001000001000000100000010000010 00001000001000000100000100000010 00000100001000000100000100000100 00000000001000000000001000000100 00010000000000000100000100000100 00010000001000001000000100000100 00001000010000001000001000001000 00000000010000000000001000000100 00100000010000010000000000000100 00010000010000010000001000001000 00100000010000001000000000001000 00000000010
p. 82
5.4. Tests en vergelijkingen
p. 83
Dit betekent de volgende indices: 0 1 2 3 4 5 6 7
De software geeft als resultaat: [0.1, 2.3] grad: 0.69 herh: 5 ind: 40 basis: 1 2 3 4 5 6 7 8 9 De software kan 40/57 = 70% van de events als patroon aanzien tov 47% door autocorrelatie. zzzz zz z z zzzzz z z z z
M ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( ˇ( Figuur 5.36: Autocorrelatie vs Software vs Ground Truth
Het gespeelde ritme bestaat uit dezelfde noten. Beide technieken hebben het bij het rechte eind: er is immers geen bijkomende informatie voorhanden hoeveel noten het patroon maakt.
5.4. Tests en vergelijkingen
p. 84
73.9.4 - 11 - 20s
Figuur 5.37: Autocorrelatie van onsets van 73.9.4 - 11 - 20s
Opmerkelijke pieken: (X,Y) = (5,28), (10,22), (15,31), (20,22), (30,33), (45,20), (60,18) Het maximum is bij X=30 met 33/56 = 59% events gematched. Dit geeft aanleiding tot de volgende opsplitsing: 100100001000010000100001000000 000100001000000000100001000000 001000001000000001000000000000 001000001000000001000000000000 001000010000000010000000000000 010000100000000100000000000000 100000100000000100000000000000 100000100000000100001000010000 100000100000000100001000010000 010000100000000010000100001000 010000100000000010000100001000 010000100000000010000100001000 010000100000000010000010000100
5.4. Tests en vergelijkingen
p. 85
0010
Dit betekent de volgende indices: 0 .. 5
De software geeft als resultaat: [0.4, 2.4] grad: 0.73 herh: 6 ind: 42 basis: 45 .. 51 Het meest herhaalde patroon bestaat (zoals het resultaat van de autocorrelatie) ook uit 6 indices, maar het eerste interval ligt op [0.4, 2.4] waarin events 2 .. 7 liggen. Dit betekent dat de eerste 2 events worden genegeerd. Er worden 75% events gematched. zzzzzz zz z zzzz
M ˇ( ˇ ˇ( ˇ
ˇ(ˇ(ˇ(ˇ(ˇ
Figuur 5.38: Autocorrelatie vs Software vs Ground Truth
In dit fragment zijn twee verschillende ritmes te horen, zoals de ground truth aangeeft. De autocorrelatie en de software kunnen dit niet onderscheiden en proberen beide ritmes te combineren tot 1 patroon.
5.4. Tests en vergelijkingen
p. 86
73.9.4 - 14 - 20s
Figuur 5.39: Autocorrelatie van onsets van 73.9.4 - 14 - 20s
Uit de figuur blijkt al dat er veel patronen te vinden zijn. Opmerkelijke pieken: (X,Y) = (9,33), (18,28) De twee maxima zijn niet toevallig bij X elkaars veelvoud. Gebruiken we X=18: 100000010000000001 000000001000000001 000000001000000001 000000001000000001 000000001000000000 100000001000000000 100000000100000000 100000000100000000 010000000010000000 010000000010000000 001000000001000000 001000000001000000 001000000001000000
5.4. Tests en vergelijkingen
p. 87
001000000001000000 001000000001000000 001000000000100000 000100000000100000 000100000000100000 000100000000010000 000010000000010000 000010000000010000 0000010000000010
Er is weer een verschuiving naar rechts te zien. De intervallen van de autocorrelatie zijn 50ms groot. Indien deze nog kleiner zouden genomen worden, zou de verschuiving minder merkbaar moeten zijn. Voor X=9 bestaat de basis uit 0 1, maar er zullen veel lijnen zijn met slechts 1 event. Voor X=18 zijn er meestal 2 events per lijn. De software geeft als resultaat: [0.0, 2.3] grad: 0.93 herh: 8 ind: 44 basis: 16 17 18 19 20 De software geeft meer events samen als basispatroon. Het kan wel alle events met elkaar matchen terwijl autocorrelatie van (33/44 =) 75% events zeker is. z z z z z
z
M ˇ ˇ ˇ ˇ Figuur 5.40: Autocorrelatie vs Software vs Ground Truth
In het muziekfragment zijn slechts 4e noten te horen die elkaar opvolgen. Zonder bijkomende informatie per noot (zoals bvb accenten of identificatie van het instrument) is het moeilijk om af te bakenen wat het patroon is. Slechts 1 noot apart (autocorrelatie) beschouwen wordt meestal niet gedaan. Met het oor luisteren duidt op 4 noten samen (ground truth). Om de meeste matches te verkrijgen neemt de software er 5 samen.
5.4. Tests en vergelijkingen
p. 88
73.9.6 - 1 - 20s
Figuur 5.41: Autocorrelatie van onsets van 73.9.6 - 1 - 20s
Opmerkelijke pieken: (X,Y) = (10,18), (24,16) X=10 zijn slechts 2 events, we nemen de volgende top: X=24. Dit geeft aanleiding tot de volgende opsplitsing: 100001000010000000010000 000000000001000000010000 000001000000000000001000 000100000010000000010000 000001000000000100000000 000001000100000100010001 000001000000001000001000 100001000000001000000001 000010000100001000010000 100000000100000000000000 100000000100000100000000 100000000001000000001000 000010000001000010001000
5.4. Tests en vergelijkingen
p. 89
001000000001000000000100 000000010000000000000100 000000010000100000000010 0000000010
Een duidelijk patroon is niet met het blote oog te zien. Gebruiken we toch deze opsplitsing betekent dit de volgende indices als basispatroon: 0 .. 3
De software geeft als resultaat: [0.0, 2.4] grad: 0.69 herh: 4 ind: 30 basis: 37 38 39 40 41 42 43 Beide technieken geven een ander resultaat. In [0.0, 2.4] zitten events 0 .. 5, twee meer dan 0 .. 3 volgens de autocorrelatie. zzz z z zzz z z
z
M ˇ( ˇ ˇ ˇ( ˇ ˇ ˇ Figuur 5.42: Autocorrelatie vs Software vs Ground Truth
Het is niet duidelijk welk ritme er in het fragment te horen is. De beschreven ground truth komt aardig in de buurt. Het resultaat van de software lijkt meer op de ground truth dan dat van de autocorrelatie: het telt ook zeven events zoals in de manuele annotatie, hoewel ze niet exact gelijk zijn. De software is dan ook maar zeker van 30/50 = 60%. De autocorrelatie is dit voor slechts 32%.
5.4. Tests en vergelijkingen
p. 90
76.8.1 - 12 - 20s
Figuur 5.43: Autocorrelatie van onsets van 76.8.1 - 12 - 20s
Opmerkelijke pieken: (X,Y) = (6,12), (16,12), (32,11), (33,14), (64,12), (98,10) Het maximum ligt op X=33 (14/41 = 34%). Dit geeft aanleiding tot de volgende opsplitsing: 100000001000001000001000000000100 000000000000001000001000000000010 000000000000001000001000000000010 000000000000001000010001000001000 000000000000010000010000000001000 000000000000010000010000000001000 000000010000100000100000000010000 000000000000100000100000000100000 000001000010000010000000001000000 000000000010000100000000010000000 000000001000001000000001000000000 000000100000100000000010
Als we vanaf lijn 5 kijken, zien we een verschuiving toenemen naar links. Om dit beter uitge-
5.4. Tests en vergelijkingen
p. 91
lijnd te krijgen zouden we vroeger moeten splitsen. Inderdaad, X=32 geeft nog 11 matches maar een betere uitlijning voor die lagere lijnen. Maar dit betekent dat er dan weer een verschuiving naar rechts te zien is: 10000000100000100000100000000010 00000000000000010000010000000000 10000000000000001000001000000000 01000000000000000100001000100000 10000000000000000100000100000000 01000000000000000010000010000000 00100000000001000010000010000000 00100000000000000001000001000000 00100000000001000010000010000000 00100000000000000001000010000000 00100000000000000010000010000000 01000000000000000100000100000000 010
Beide gevallen geven als basisindices: 0 .. 4, dit zijn er 5.
De software geeft als resultaat: [0.2, 3.4] grad: 0.87 herh: 4 ind: 33 basis: 28 .. 34 Dit zijn in totaal 33/41 = 80% events die gematched kunnen worden. z zzz zz z
z
M ˇ ( ˇ `ˇ
z zz
z
ˇ( ˇ ˇ ˇ(
Figuur 5.44: Autocorrelatie vs Software vs Ground Truth
Wederom blijkt het niet zo duidelijk te zijn welk ritme er juist gespeeld wordt. Door het resultaat van de software circulair te bekijken, bekomen we de manuele annotatie.
5.4. Tests en vergelijkingen 76.8.1 - 17 - 20s
Figuur 5.45: Autocorrelatie van onsets van 76.8.1 - 17 - 20s
Opmerkelijke pieken: (X,Y) = (14,22), (28,25), (85,18) Het maximum zit op X=28. Dit geeft aanleiding tot de volgende opsplitsing: 1001000010000000010000000000 0001000001000010001000100000 0000100001000001001000000000 0000100001000000001000000100 1000010000100000000100000010 0000010000100000000100000000 0000010000100000000100000000 0000010000010000000100000000 0000010000010000000100000001 0000010000100000001000000000 0000100000100000000100000000 0000010000100000000100000000 1000010000100000100100000000 0000010000010000000010
p. 92
5.4. Tests en vergelijkingen
p. 93
De meeste lijnen hebben zo drie events. De eerste lijn heeft de volgende indices: 0 1 2 3
De software geeft als resultaat: [0.1, 2.2] grad: 0.77 herh: 7 ind: 44 basis: 25 26 27 28 29 Dit patroon kan 44/52 = 85% events gebruiken tov 48% van de autocorrelatie. zzz z zz z
M ˇ( ˇ ˇ
zz
?
Figuur 5.46: Autocorrelatie vs Software vs Ground Truth
Een deel van beide resultaten is gelijk aan de ground truth. Bij beide technieken zijn er toch meer events dan de annotatie. Dit komt omdat er hier en daar toch wat meer events tussen de patronen tijdens de onsetdetectie gekomen zijn.
5.4. Tests en vergelijkingen
p. 94
92.6.7 - 5 - 20s
Figuur 5.47: Autocorrelatie van onsets van 92.6.7 - 5 - 20s
Opmerkelijke pieken: (X,Y) = (7,12), (43,9) X=7 is te klein, het volgende maximum ligt op X=43. Dit geeft aanleiding tot de volgende opsplitsing met een gebruik van 9/35 = 26%: 1000000010000000000000010000000000000000000 0100000010000000000000010000000100000010000 0100000010000001000000100000000000000000001 0000001000000000000001000000000000000000000 1000001000000000000010000000000000000000010 0000010000100000000100000000000000000000000 0001000000000000001000000000000000000000100 0000100000000000000100000000000100000000100 0000100000010000001000001000000000000000100 000010
We zien als het ware het patroon ongeveer goed gevormd, maar een goede opsplitsing vinden we niet. Dit blijkt ook uit het groot aantal splitsingen met Y=7. X=43 betekent een kort patroon
5.4. Tests en vergelijkingen
p. 95
met de volgende indices: 0 1 2
De software geeft als resultaat: [0.0, 2.1] grad: 0.82 herh: 6 ind: 24 basis: 12 13 14 In interval [0.0, 2.1] zitten enkel indices 0 1 2, wat betekent dat het laatste resultaat overeenstemt met de uitkomst van de autocorrelatie. Dit patroon kan 67% events matchen. z z
z
z z
z
M ˇ ( ˇ `ˇ Figuur 5.48: Autocorrelatie vs Software vs Ground Truth
Beide technieken komen tot hetzelfde resultaat als de ground truth.
5.4. Tests en vergelijkingen
p. 96
92.6.7 - 8 - 20s
Figuur 5.49: Autocorrelatie van onsets van 92.6.7 - 8 - 20s
Opmerkelijke pieken: (X,Y) = (22,13), (44,12), (87,12), (109,11), (131,12), (175,10) X=44: 44 + 43 = 87, 87 + 43 = 130, 130 + 43 = 174. Dit is quasi dezelfde afstand, X=44 geeft dus een mooi resultaat en matcht 12/37 = 32%: 10001000000001000000000000000000000100000001 00000000000001000000000000000000000100000001 00000000010001001000000100010000001000000010 00000000000001000000000000000000000100000010 00000001000010000000000000000000001000000100 00000000000010000000000000000000001000010010 00000100000010000000000000000000010000000100 00000000000100000000000000000000010000001000 0000000000010000000000000010000001000000010
Dit betekent de volgende indices: 0 .. 4
De software geeft als resultaat:
5.4. Tests en vergelijkingen
p. 97
[0.0, 2.2] grad: 0.83 herh: 3 ind: 15 basis: 5 6 7 Het interval [0.0, 2.2] geeft ook aanleiding (zoals de autocorrelatie) tot indices 0 .. 4 en is zeker van 15/37 = 41% events. zz z z
z z z z
M ˇ ( ˇ ˇ` Figuur 5.50: Autocorrelatie vs Software vs Ground Truth
Door het resultaat van de software circulair te bekijken, bekomen we de manuele annotatie. De autocorrelatie gaat hier de mist in. 97.10.3 - 1 - 20s
Figuur 5.51: Autocorrelatie van onsets van 97.10.3 - 1 - 20s
5.4. Tests en vergelijkingen
p. 98
Opmerkelijke pieken: (X,Y) = (27,22), (41,20), (68,22), (95,18), (109,17), (136,16), (163,15) Dit zijn allemaal pieken die ongeveer even ver van elkaar liggen. X=27 geeft een kort patroon. X=41 geeft aanleiding tot de volgende splitsing: 10000000000000010000100000000100000000000 00100000000000001000000100000100000000000 01000001000000010000010000000100000000000 01000001000000010000010000001000001000000 01000000000000100000100000001000000000000 01000001000000010000100000001000000000000 01000010000000100000000000001000000000000 10000000000000100000000000001000010000000 10000000000000100000000000001000000000000 10000010000000100010
Voor X=68 is er ook een maximum, wat de volgende splitsing betekent: 10000000000000010000100000000100000000000001000000000000010000001000 00100000000000010000010000000100000100000001000000000000100000100000 00100000100000010000010000000100000000000010000010000000100000000000 00100000100000001000010000000100000000000001000010000000100000000000 00100000000000010000000000000100000000000001000010000000100000000000 0010000000000000100000000000010000010000000100010
Dit betekent de volgende indices: 0 .. 6
De software geeft als resultaat: [0.1, 2.8] grad: 0.77 herh: 5 ind: 33 basis: 19 .. 24 Het meest herhaalde patroon (19 .. 24) stemt overeen met de splitsing X=68 van de autocorrelatie. De software is zeker van 33/43 = 77% tov 51% voor de autocorrelatie.
5.4. Tests en vergelijkingen
p. 99 z z
zz z zz z
z
z z
zz
M ˇ( ˇ ˇ( ˇ ˇ( ˇ Figuur 5.52: Autocorrelatie vs Software vs Ground Truth
Het gespeelde ritme in het fragment is niet exact gelijk aan de ground truth, daardoor lijken beide technieken niet op de annotatie. 97.10.3 - 16 - 20s
Figuur 5.53: Autocorrelatie van onsets van 97.10.3 - 16 - 20s
Opmerkelijke pieken: (X,Y) = (22,38), (65,30), (87,32) X=22 geeft aanleiding tot de volgende opsplitsing: 1000000001000010000000 1000000001000010000000
5.4. Tests en vergelijkingen
p. 100
1000010001000100000000 1000000001000100000000 1000000010000100000000 1000000010000100000000 1000000010001000000001 0000000010001000000001 0000000100001000000001 0000000100001000000010 0000000100001000000010 0000000100001000000010 0000000100010000000010 0000001000010000100010 0000001000010000000100 0000001000010000000010 0000010000100000000100 0000010000100000001
Hier zien we al een patroon ontstaan. Dit betekent de volgende indices: 0 1 2
De software geeft als resultaat: [0.3, 2.6] grad: 0.64 herh: 4 ind: 35 basis: 1 2 3 4 5 6 7 [0.0, 2.4] grad: 0.77 herh: 4 ind: 35 basis: 34 35 36 37 38 39 40 [0.2, 2.6] grad: 0.75 herh: 4 ind: 36 basis: 28 29 30 31 32 33 34 Het derde resultaat gebruikt 1 onset meer dan de andere twee, maar heeft een lagere gradatie dan het tweede resultaat. z zz z zz z z
z
M ˇ( ˇ ˇ Figuur 5.54: Autocorrelatie vs Software vs Ground Truth
De autocorrelatie vindt in dit geval een patroon dat goed op de ground truth lijkt. De software maakt er iets anders van doordat er meer onsets gedetecteerd worden dan er in het ritme zitten.
5.4. Tests en vergelijkingen 97.10.3 - 5 - 20s
Figuur 5.55: Autocorrelatie van onsets van 97.10.3 - 5 - 20s
Opmerkelijke pieken: (X,Y) = (22,34), (65,30), (87,33) Het maximum bij X=22 geeft aanleiding tot de volgende opsplitsing: 1000100000001000010000 0001000000001000010000 0001000000001000010000 0001000000010000100000 0001000000010000100000 0001000000010000100000 0001000000010000100000 0010000000100001000000 0010000000100001000000 0100000100000001000000 0100001000100001000000 0100000001000010000000 1000000001000010010001 0000001001000010000000
p. 101
5.4. Tests en vergelijkingen
p. 102
1000000001000010000000 1000000010000100000000 1000000010000100000001 0000000010000100000000 10
Dit betekent de volgende indices: 0 1 2 3
De software geeft als resultaat: [0.2, 2.6] grad: 0.68 herh: 5 ind: 43 basis: 1 2 3 4 5 6 7
zz zz z zz z zz z
M ˇ( ˇ ˇ ˇ( ˇ ˇ Figuur 5.56: Autocorrelatie vs Software vs Ground Truth
In beide resultaten is de ground truth terug te vinden als subset. Bij de autocorrelatie zijn er veel lijnen met drie events. Als we ´e´en van deze lijnen nemen als patroon komt dit overeen met de helft van de ground truth. De software geeft ook de ground truth met nog ´e´en event meer.
5.4. Tests en vergelijkingen 97.10.3 - 6 - 20s
Figuur 5.57: Autocorrelatie van onsets van 97.10.3 - 6 - 20s
Opmerkelijke pieken: (X,Y) = (13,41), (66,36) Het maximum zit bij X=13. Dit geeft aanleiding tot de volgende opsplitsing: 1001000100000 1000000010000 1000000010000 1000000010000 1000000010000 0100000001000 0100000001000 0100000001000 0010000000100 0010000001000 0010000000100 0010000000100 0010000000100 0010000000100
p. 103
5.4. Tests en vergelijkingen
p. 104
0001000000010 0001000000010 0001000000010 0001000100010 0001000000001 0000100000001 0000000000001 0000100000010 0000100000001 0000100000001 0000010000000 1000010001000 1000010000000 1000010000000 1000010000000 1000010000000 10000010
Er zijn veel lijnen met slechts 2 events. Iets wat we normaal niet aanvaarden als patroon wegens te kort. Het volgende maximum zit op X=66, wat deze splitsing geeft: 100100010000010000000100001000000010000100000001000010000000100000 100000001000010000000100001000000010000010000000100001000000100000 100000001000010000000100001000000010000100000001000001000000010000 100000001000010000000100001000100010000100000000100001000000010000 000000001000010000001000001000000010000100000001000001000000010000 100010001000010000000100001000000010000100000001000010000000100000 10
Als we naar deze lijnen kijken, zien we dat er per lijn veel malen 1000000010000 na elkaar komen. Dit zijn twee events, zoals aangegeven door de eerste splitsing. Naar gewoonte nemen we de eerste lijn: indices 0 1 2.
De software geeft als resultaat: [0.6, 2.6] grad: 0.77 herh: 6 ind: 43 basis: 28 29 30 31 32 33 [0.0, 2.3] grad: 0.77 herh: 6 ind: 52 basis: 43 44 45 46 47 48 49 [0.1, 2.4] grad: 0.65 herh: 6 ind: 45 basis: 1 2 3 4 5 6 7 8
5.4. Tests en vergelijkingen
p. 105
Het tweede resultaat gebruikt de meeste indices: 52/63 = 83% tov 41/63 = 65% matches bij de autocorrelatie.
zzz z z z zz z z
M ˇ( ˇ Figuur 5.58: Autocorrelatie vs Software vs Ground Truth
Hadden we een andere lijn gebruikt voor de autocorrelatie zou deze dezelfde zijn als de ground truth. In de software is het patroon driemaal herhaald met nog ´e´en extra event. Dit komt omdat in het muziekfragment op een bepaalde plaats even niet het ritme gespeeld wordt. 97.10.3 - 7 - 20s
Figuur 5.59: Autocorrelatie van onsets van 97.10.3 - 7 - 20s
5.4. Tests en vergelijkingen
p. 106
Pieken zijn op te merken met een lengte van 26: (X,Y) = (26,24), (53,23), (79,20), (105,19) We gebruiken het maximum: X=26. Dit geeft aanleiding tot de volgende opsplitsing: 01000000001000000100000100 00100000000100000000000100 00100000000100000100000010 00010000000100000000000010 00010000000100000001000001 00010000000010000000000010 00010000000010000000100001 00010000000010000000000010 00001000000010000000010001 00000000000010000000000001 00001000000010000000010001 00001000000001000000000000 10000100000001000000000100 10000100000000100000000000 01000100000000100000010000 010
Dit betekent de volgende indices: 0 1 2 3
De software geeft als resultaat: [0.0, 2.2] grad: 0.70 herh: 5 ind: 35 basis: 0 1 2 3 4 5 [0.1, 2.7] grad: 0.87 herh: 5 ind: 40 basis: 21 22 23 24 25 26 27 Het tweede resultaat heeft een hogere gradatie en gebruikt meer indices: 40/52 = 77% tov 46% bij de autocorrelatie. z z zz z z zzz z
z
M ˇ ? ˇ( ˇ Figuur 5.60: Autocorrelatie vs Software vs Ground Truth
In het fragment zit slechts op ´e´en plaats een verkeerd ritme dan het geannoteerde. De onsetdetectie
5.4. Tests en vergelijkingen
p. 107
vindt evenwel meer events tijdens de verschillende herhalingen. Hierdoor vindt de software iets anders dan het ritme omdat dit patroon veel events met elkaar kan matchen. De autocorrelatie vindt het beschreven ritme ook niet. 97.10.8 - 10 - 20s
Figuur 5.61: Autocorrelatie van onsets van 97.10.8 - 10 - 20s
Opmerkelijke pieken: (X,Y) = (45,11), (91,12) Het lijkt erop dat er een patroon bestaat met lengte = 91-45 = 46. X=45 geeft aanleiding tot de volgende opsplitsing: 010000000000001000000000000010000000000000000 100000000010000100000100000001000000000000000 001000000000000100000000000001000000000000000 000100000000010010000001000000100000000000000 000100000000000010000000000000100000000000000 000010000000000001000000000000010000000010000 000100000000000001000000000000100000000000000 000100000000000001000000000000100000000000000 00010000000000001000000000000010
5.4. Tests en vergelijkingen
p. 108
Dit betekent de volgende indices: 0 1 2 3 events is nogal een kort patroon, nemen we X=91 krijgen we: 0100000000000010..11x..0100..12x..001000000000100001000001000000010000000000000000 0100000000000010..11x..0100..12x..000010000000001001000000100000010000000000000000 0100000000000010..11x..0100..12x..000010000000000001000000000000010000000010000000 1000000000000010..11x..1000..12x..001000000000000010000000000001000000000000000001 0000000000001000000000000010
De software geeft als resultaat: [0.1, 4.6] grad: 0.80 herh: 3 ind: 28 basis: 23 .. 28 [0.1, 4.6] bevat indices 1 .. 7 en geeft aanleiding tot 28/32 = 88% matches. In [0.0, 4.6] zijn events 0 .. 7 vervat, wat de splitsing van de autocorrelatie is bij X=91 (het maximum) met 38% matches. z
z
z
z
z
z
M ˇ ˇ ˇ
z
z
z
?
Figuur 5.62: Autocorrelatie vs Software vs Ground Truth
De software geeft hier voorrang aan het dubbele van het patroon zoals gevonden door de autocorrelatie en de annotatie beschrijft.
5.4. Tests en vergelijkingen
p. 109
97.10.8 - 22 - 20s
Figuur 5.63: Autocorrelatie van onsets van 97.10.8 - 22 - 20s
Er zijn niet veel pieken op te merken: (X,Y) = (15,12), (30,8), (45,7), (61,7). Dit komt omdat er slechts 31 onsets in het fragment gevonden zijn. Een vergelijking (fig. 5.64) van de audio met de gedetecteerde onsets leert dat er veel events overgeslagen zijn. In het midden is er even een stuk waar de zangstem de percussie bijna onhoorbaar maakt, alhoewel ze aanwezig is. Evenwel worden deze events niet gedetecteerd. Elke splitsing van deze maxima blijkt onzinnig te zijn doordat er te weinig overeenkomsten gevonden kunnen worden.
Figuur 5.64: Detectie versus audio van 97.10.8 - 22 - 20s
De software geeft als resultaat:
5.4. Tests en vergelijkingen
p. 110
[0.1, 2.3] grad: 0.63 herh: 4 ind: 22 basis: 1 .. 7 Er kunnen 22/31 = 71% events gematched worden. De vraag blijft natuurlijk of voor zo een onduidelijke detectie dit in de buurt komt van het gespeelde patroon. Uiteindelijk is het gespeelde heel eenvoudig, maar zijn er andere elementen aanwezig die de detectie niet ten goede komen. 97.10.8 - 7 - 20s
Figuur 5.65: Autocorrelatie van onsets van 97.10.8 - 7 - 20s
Opmerkelijke pieken: (X,Y) = (17,37), (23,35), (40,37) X=17 geeft aanleiding tot de volgende opsplitsing: 00100010000010000 00010000010000010 00010000000000000 00010000010000010 00001000000000001 00001000001000010 00001000001000001 00000100001000001 00000100000100001
5.4. Tests en vergelijkingen
p. 111
00000100000100000 10000100000100000 10000100000100000 10000100000100000 10000100000100000 10000010000100000 00000010000100000 10000010001000000 10000010000010000 10000010000000000 10000010001000000 10000010000000000 00000010000010000 00100010000000000 010
Dit betekent de volgende indices: 0 1 2
De software geeft als resultaat: [0.1, 2.1] grad: 0.86 herh: 9 ind: 61 basis: 11 12 13 14 15 16 17 Met dit patroon wordt elk event gebruikt tov 37/61 = 61% van de autocorrelatie. zz z zz zz z z z
M ˇ( ˇ( ˇ( Figuur 5.66: Autocorrelatie vs Software vs Ground Truth
Beide resultaten zijn goed te rekenen gezien het algoritme geen informatie m´e´er heeft over de zware tel (soms aanwezig in muziek zodat men voelt wanneer een maat begint).
5.4. Tests en vergelijkingen
p. 112
97.10.8 - 8 - 20s
Figuur 5.67: Autocorrelatie van onsets van 97.10.8 - 8 - 20s
Opmerkelijke pieken: (X,Y) = (19,12), (28,11), (47,15) Het maximum ligt bij X=47 (15/28 = 54%). Dit geeft aanleiding tot de volgende opsplitsing: 10001000000000000100000000000000000010000000010 00000000000000000100000000000000000010000000010 00000000000000000100000000000000000010000000010 00000000000000000100000000000000000010000000001 00000000000000000010000000000000000010000000001 00000000000000000100000000000000000010001000001 00000000000000000100000000000000000001000000000 10000000000000000001000000000000000000100000000 100000000000000000010
Dit betekent de volgende indices: 0 1 2 3 4
De software geeft als resultaat: [0.0, 4.7] grad: 0.79 herh: 3 ind: 26 basis: 8 .. 13
5.4. Tests en vergelijkingen
p. 113
In [0.0, 4.7] bevinden zich indices 0 .. 7. Het valt op te merken dat 0 .. 7 het dubbele is van 0 .. 4: het patroon bestaat eigenlijk uit indices 2 3 4 die gematched kunnen worden met 5 6 7. Maar doordat het fragment kort is en er ruis aanwezig is, is het resultaat van het meest herhaald patroon dat van indices 8 .. 13, en niet de helft zoals aangegeven door het eerste resultaat. Als we dit patroon als basis nemen, kan het van 93% events met zekerheid zeggen dat ze dit patroon vormen. De autocorrelatie geeft de helft als patroon aan. z z
z z
z z
z
z
z
M ˇ( ˇ ˇ Figuur 5.68: Autocorrelatie vs Software vs Ground Truth
Voor de autocorrelatie is nu niet de eerste, maar de tweede lijn genomen. Bijna alle lijnen, buiten de eerste, tellen slechts 3 events. Als we ´e´en van die lijnen (circulair) bekijken bekomen we ook de ground truth (maar dat doen we anders nooit). De software geeft als (circulair) resultaat tweemaal de ground truth.
5.4.3
Samenvatting
We zetten de resultaten van de echte muziekvoorbeelden op een rijtje. We zijn tenslotte vooral hierin ge¨ınteresseerd en niet zozeer in zelfgemaakte voorbeelden.
fragment 73.9.1 - 8 - 20s 73.9.1 - 9 - 20s 73.9.10 - 5 - 20s 73.9.11 - 9 - 20s 73.9.12 - 5 - 20s 73.9.14 - 9 - 20s 73.9.15 - 7 - 20s† 73.9.2 - 4 - 20s 73.9.20 - 9 - 20s 73.9.22 - 6 - 20s 73.9.22 - 8 - 20s* 73.9.24 - 1 - 20s† 73.9.4 - 11 - 20s*
software vs autocorrelatie SOF = AUTO SOF = AUTO SOF ±= > AUTO SOF ±= > AUTO SOF > AUTO SOF > AUTO SOF > AUTO SOF ±= > AUTO SOF > AUTO
tov ground truth SOF en AUTO SOF SOF onbepaald SOF en AUTO SOF SOF en AUTO SOF SOF en AUTO -
5.4. Tests en vergelijkingen fragment 73.9.4 - 14 - 20s† 73.9.6 - 1 - 20s 76.8.1 - 12 - 20s* 76.8.1 - 17 - 20s‡ 92.6.7 - 5 - 20s 92.6.7 - 8 - 20s 97.10.3 - 1 - 20s 97.10.3 - 16 - 20s 97.10.3 - 5 - 20s 97.10.3 - 6 - 20s 97.10.3 - 7 - 20s‡ 97.10.8 - 10 - 20s 97.10.8 - 22 - 20s‡ 97.10.8 - 7 - 20s† 97.10.8 - 8 - 20s
p. 114
software vs autocorrelatie tov ground truth SOF > AUTO SOF en AUTO SOF ±= > AUTO SOF SOF SOF = AUTO SOF en AUTO SOF AUTO > SOF SOF > AUTO AUTO SOF > AUTO subset(SOF) en subset(AUTO) SOF SOF tweemaal patroon SOF > AUTO SOF SOF tweemaal patroon Tabel 5.3: Samenvattende tabel
∗ : Fragment bestaat uit een mengeling van ritmes † : Patroon bestaat enkel uit dezelfde noten ‡ : Te slechte onsetdetectie om patroon te vinden
Bespreking Het uiteindelijke resultaat: van de 28 geteste voorbeeldfragmenten, blijkt dat de software en autocorrelatie bij 7 (25%) tests hetzelfde resultaat geven (wanneer SOF en AUTO min of meer gelijk zijn, eerste kolom). De software geeft 11 keer meer dan autocorrelatie hetzelfde patroon als de ground truth. In 60% van de gevallen heeft de software hetzelfde resultaat als de ground truth tov 25% bij autocorrelatie (tweede kolom).
In twee gevallen toont de software een patroon dat dubbel zo lang is. Dit komt meestal doordat het gespeelde ritme bestaat uit dezelfde noten (bvb allemaal achtsten zonder eens een vierde). Ook is er een minimale lengte (in tijd) voor patronen opgegeven. Deze staat standaard op 2 seconden. Ritmes die uit dezelfde noten bestaan zullen een korte annotatie hebben, maar een eerder lang patroon als resultaat van de software. Dit is zo voor bvb 97.10.8 - 8 - 20s. De software geeft daar indices 8 tot en met 13 als basispatroon bij een minimale lengte van 2 seconden. Als we de minimale lengte op 1 seconden zetten, bestaat het beste patroon uit indices 1 en 2, wat korter is.
5.5. Uitvoeringstijd
5.5
p. 115
Uitvoeringstijd
Een belangrijke factor van software is de uitvoeringstijd. Het opdelen in intervallen en vergelijken van de events in deze intervallen blijkt eenvoudig en snel te zijn. Per twee intervallen worden alle mogelijke combinaties van events die matchen en niet matchen uitgeprobeerd en de beste combinatie wordt als resultaat weergegeven. De beste is in dit geval de combinatie die de meeste matches bevat. Het berekenen van al deze combinaties blijkt een grote brok rekenwerk te zijn, wat de uitvoeringstijd drastisch omhoog brengt. Om alle mogelijkheden te berekenen en hieruit de beste te selecteren is het nodig om al die combinaties te zoeken. Het langst mogelijke interval kan dan de halve lengte van het fragment hebben. Uit de tests blijkt echter dat de meeste patronen vrij kort zijn in aantal noten gerekend. Dit betekent meestal ook dat ze vrij kort zijn in tijd. Om de uitvoeringstijd te beperken kunnen we een maximale lengte invoegen. Ter vergelijking: om alle mogelijkheden te berekenen van 73.9.4 - 14 had de software 7 dagen nodig. Stellen we een maximale lengte in van 5 seconden duurde dit nog slechts 12 seconden met in beide gevallen hetzelfde patroon als beste resultaat. Een andere grens die we eventueel kunnen introduceren is een maximum aantal events die niet gematched moeten worden per basispatroon. Dit hebben we nog niet ge¨ımplementeerd omdat we ge¨ınteresseerd zijn in alle mogelijke patronen.
5.6
Conclusie
De geschreven software heeft haar nut bewezen: het kan meer patronen ontdekken en is van meer onsets zeker dat ze tot een ritme behoren dan autocorrelatie. Per interval maakt de software een gradatie van het ritme in dat interval tegenover de andere intervallen. Hiervan zoekt het het beste patroon dat op de andere lijkt. Het zou geen kwaad kunnen om deze techniek ook toe te passen op de resultaten van de autocorrelatie. Autocorrelatie zou tot een beter resultaat komen indien hiervan ook gebruik zou gemaakt worden. Praktisch is gebleken dat de gebruiker een afweging moet maken tussen de gradatie en de zekerheid van het aantal gebruikte indices. Een lagere gradatie gaat meestal gepaard met een hoger aantal gebruikte indices. Dit komt omdat dan de fout (het aantal bijgedachte onsets) hoger ligt. Om het meest intu¨ıtieve patroon te krijgen als resultaat gebruiken we deze stappen: 1. Zoek alle patronen. 2. Indien er ´e´en patroon is met gradatie 1.0, geef dit als resultaat. Indien er meerdere patronen zijn met gradatie 1.0, geef het resultaat dat het meeste indices gebruikt.
5.6. Conclusie
p. 116
3. Anders, geef de patronen weer met het meeste aantal herhalingen. Indien er meer dan ´e´en zijn, geef het resultaat dat het meeste indices gebruikt. Indien gewenst, kan nog een mechanisme ingebouwd worden dat een verhouding gradatie/indices berekent en op basis hiervan een ander patroon als resultaat geeft.
Hoofdstuk 6
Besluit We zijn begonnen met perfecte input: we wisten waar het patroon was en hebben een algoritme gevonden dat het patroon kon vinden. Het bleek al snel dat dit algoritme te kort zou schieten om ook minder-perfecte input te verwerken. We moesten enkele technieken vinden die problemen die gepaard gaan met echte muziekvoorbeelden konden oplossen. Zo hebben we het mogelijk gemaakt om events die bijna nooit optreden toch mee te tellen en als deel van een patroon te aanzien.
Nadat we enkele theoretische inzichten besproken hebben over mogelijke problemen bij live muziek, hebben we deze idee¨en toegepast in een programma. Dit programma werd getest tegenover een andere techniek: autocorrelatie. Het is gebleken dat de geschreven software intu¨ıtievere patronen voortbrengt dan autocorrelatie.
6.1
Suggesties
Hierna volgen enkele suggesties naar de toekomst toe om de software beter uit te werken. De bedoeling was om eenvoudige patronen op te sporen. Voor meer complexe, moderne muziek zijn aanpassingen nodig.
6.1.1
Relevance parameter
Tijdens het onderzoek hebben we de relevance parameter die gegenereerd wordt uit de Drum ” detection console applications” [13] moeilijk kunnen be¨ınvloeden of voorspellen. Deze parameter is eigenlijk een maat waarin het algoritme dat de onsets detecteert, gelooft dat een event werkelijk een drumevent is. Deze software werd eigenlijk geschreven voor andere doeleinden maar de detectie van drumevents komt wel goed in de buurt van de werkelijkheid. Maar het spreekt voor zich dat als er al fouten worden ge¨ıntroduceerd in de input, de output er niet beter op wordt. 117
6.1. Suggesties
p. 118
Eens de relevance parameter voorspeld kan worden, kan hiervan gebruik gemaakt worden om een nieuw algoritme te ontwikkelen dat patronen kan vinden met een andere gradatie van zekerheid. Verder mag opgemerkt worden dat de muziekstukken waarvoor de implementatie bedoeld is, meestal niet overdreven complex zijn: vaak is er slechts 1 slaginstrument aanwezig zodat de onsetdetectie vrij sterk realistisch is. Langs de andere kant, kan het beter zijn om een nieuw algoritme te maken dat rekening houdt met meerdere instrumenten om ook Westerse muziek te analyseren.
Een andere interessante parameter dan de relevance zou de dynamiek per event kunnen zijn. Veel ritmes die op ´e´en instrument gespeeld worden gebruiken accenten: sommige noten klinken luider dan andere. Eenvoudige ritmes van opeenvolgende noten van dezelfde duur zullen hierdoor gemakkelijker uit elkaar gehaald kunnen worden.
6.1.2
Tempo afleiden
Er is een betrouwbare classificatie methode nodig om het tempo af te leiden uit de onsets. In de literatuur [1] wordt hiervoor uitgegaan van de bronaudio in plaats van de onsets, maar uiteindelijk doen ze net hetzelfde: pieken detecteren die op regelmatige basis terugkomen en hieruit het tempo afleiden. Dat is net hetzelfde als onsets detecteren en uit de inter-onset-tijden het tempo afleiden. Een methode om verschillende waarden samen te clusteren zoals voorgesteld in sectie 4.1 zal dichter in de buurt komen van het werkelijke tempo zoals aangetoond.
6.1.3
Andere vormen van pauze
Als de pauze niet even lang duurt als het beschouwde interval, zullen de events na de pauze niet meer goed gealigneerd zijn (fig. 6.1). Om dit op te lossen moeten we deze pauze negeren. Met andere woorden we laten toe dat tijd waar geen events zijn, weggesmeten wordt.
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
Figuur 6.1: De pauze verlegt de segmenten.
Als we het wegsmijten van lege tijd toelaten, zullen in muziekvoorbeeld 6.2 de drie samenhorende
6.1. Suggesties
I2 ˇ ˇ ˇ 4
p. 119
> >
ˇ ˇ ˇ
> >
ˇ ˇ ˇ
> >
> >
ˇ ˇ ˇ
Figuur 6.2: Bestaat dit uit 1 patroon? Of uit 2? Of uit 4?
noten (twee 8en en ´e´en 4e ) herkend worden als patroon dat viermaal voorkomt. Maar aangezien we al afspraken gemaakt hebben dat een patroon zo lang mogelijk moet zijn, zullen telkens vier maten samen genomen worden en herkend worden als patroon dat tweemaal voorkomt.
6.1.4
Tempo verandering
In moderne muziek komt het vaak voor dat er een verandering in tempo gebeurt. We geven een kort overzicht en geven een suggestie hoe dit zou kunnen verwerkt worden. Ritenuto Ritenuto is een muziekterm die langzamer, terughoudend” betekent. Dit is meestal een kort ” stukje in muziek waar het tempo alsmaar langzamer wordt en er plots weer naar het normale tempo gesprongen wordt.
z
z
z
z
z
z
z
z
z
z
z z
z z
z z
z
z
z
z
Figuur 6.3: Ritenuto: een stukje muziek wordt uitgerokken over de tijd.
Als we natuurlijk enkel naar gelijke intervallen kijken, zouden onze events er uitzien zoals in figuur 6.4. Onze structuur is nu helemaal verloren. Dezelfde techniek als met een pauze kunnen we hier toepassen. Dit introduceert echter het negeren van events, een gevaarlijke zaak. Zo kunnen ook overeenkomstige, juiste events genegeerd worden zoals in figuur 6.5: enkel de eerste drie events worden samen aanzien als het” patroon. Dit kan niet de bedoeling zijn en we zullen het negeren ” van events dan ook niet mogelijk maken.
6.1. Suggesties
p. 120
z
z
z
z
z
z
z
z
z
z
z
z
z z
z
z
z
z z
z
Figuur 6.4: Ritenuto is gevaarlijk bij het gebruik van gelijke intervallen.
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
Figuur 6.5: Als we dan toch events mogen negeren, is het onderste interval bestaande uit slechts drie events evengoed een resultaat.
Nieuw tempo Het kan zijn dat ons liedje bestaat uit twee (of meerdere) delen met verschillend tempo. Dit betekent dat er ook meerdere patronen zullen zijn die in aanmerking komen die een gebruiker als het” patroon zal aanzien. Onze restricties die we hebben gebruikt zijn onder andere: het” ” ” patroon moet het meest herhaald zijn. Dus als het patroon uit het eerste deel meer herhaald wordt dan de patronen uit andere delen zal enkel het eerste gegeven worden. De oplossing hiervoor is een afweging tussen enerzijds het aantal patronen dat als output gegeven wordt (met resultaat dat dit aantal voor elk muziekstuk zal oplopen, ook al is er geen sprake van een nieuw deel), en anderzijds slechts ´e´en patroon wat misschien net niet het patroon is dat de gebruiker bedoelt.
6.1.5
Verschillende instrumenten
Momenteel wordt geen rekening gehouden met het type van slaginstrumet tijdens de detectie in de audio. De detectie software is evenwel in staat om verschillende instrumenten te zoeken, zoals het onderscheid tussen toms en cymbalen. Het gebruik van deze extra informatie kan ons misschien ook op een beter spoor zetten om herhalingen te vinden.
Bijlage A
Handleiding A.1
Benodigdheden
De implementatie is geschreven in Java 1.5.0 04. De volgende klassen zijn nodig: OnsetsReader
Dit is een klasse om de Onset bestanden te lezen die de output zijn van de Drum detection ” console applications” [13] . PatternFinder
Dit is de main klasse waar patronen gevonden en vergeleken worden met elkaar. PatternKeeper
Dit is een hulp klasse om ´e´en patroon voor te stellen aan de hand van het koppel (Onsettime,Relevance) uit de input. PatternKeeperWrapper
Dit is een hulp klasse om een verzameling van patronen voor te stellen. FuzzyKoppels
Deze klasse houdt overeenkomstige events bij die samenhoren. FuzzyPattern
Indien bepaalde onsets een patroon vormen, wordt dit patroon in dit object bijgehouden. FuzzyPatternCollection
Meerdere patronen per liedje worden hier bijgehouden. Compileer als volgt: PROMPT:javac PatternFinder.java 121
A.2. Command line opties
p. 122
Voer uit als volgt: PROMPT:java PatternFinder
Indien u het programma runt zonder argumenten krijgt u een samenvatting van mogelijk te gebruiken argumenten. De algemene manier van opstarten gebeurt zo: java PatternFinder -OptionName OptionValue (...)
A.2
filename1 (filename2 ...)
Command line opties
* De opties mogen ook in kleine letters meegegeven worden.
Deze opties worden gebruikt door de algoritmes die zonder vage logica werken: -TimeError <double> (default: 0.0)
Bij het vergelijken van twee timestamp-waarden bepaalt TimeError hoeveel verschil hier mag zijn zodat beide waarden verondersteld worden gelijk te zijn. -MinimalPatternSize (default: 3)
Dit is het minimaal aantal onsets (niet tijdsinterval) bij elkaar om van een patroon te spreken. Deze opties worden enkel gebruikt door het algoritme met vage logica: -fuzzyInsertPenalty <double> (default: 0.2)
Als een onset geen match heeft, moet er een noot bijgevoegd worden. Deze gebeurtenis krijgt dan deze waarde. -fuzzyMinimalIntervalLength <double> (default: 2.0 seconden)
De startwaarde van de minimum lengte van een patroon. -fuzzyMaximalIntervalLength <double> (default: 5.0 seconden)
De maximale lengte van een patroon. -fuzzyInterval <double> (default: 0.1)
Bij elke stap wordt het interval met deze waarde uitgebreid. -fuzzyMinimalMatch <double> (default: 0.5)
Indien de lidmaatschapsgraad tussen twee patronen niet hoger is dan dit, worden de twee niet als zijnde gelijk beschouwd. -fuzzyProbType (default: 1)
Hier kan u de lidmaatschapsfunctie kiezen die zal gebruikt worden.
A.3. Output
p. 123
Deze opties zijn gemeenschappelijk: -MODE <String> (default: MODEFUZZY)
Kies welk algoritme u wilt gebruiken. Mogelijkheden zijn: MODETIMESTAMPS: om te zoeken in tijdsstippen MODEAUTOFIND: om automatisch de laagste TimeError waarde te zoeken zodat een patroon gevonden wordt op basis van tijdsstippen. U specificeert best zelf een waarde voor TimeError die dan als maximale waarde zal gebruikt worden. MODEFUZZY: om gebruik te maken van de vage logica om te zoeken. -debug (default: 0)
Hoe hoger dit getal is, hoe meer informatie op het scherm verschijnt. -DoublePlaces (default: 2)
Intern wordt er met veel cijfers na de komma gewerkt, maar een noot op 2.3333333 en een noot op 2.3333334 zijn niet hoorbaar te onderscheiden. -stretchedLength <double> (default: 4.0 seconden)
Dit is de lengte van het gevonden patroon na stretching alvorens naar een bestand te schrijven.
A.3
Output
Het gevonden patroon wordt omgezet naar het formaat dat als input gebruikt is: koppels (timestamp, relevance). Als ´e´en patroon gevonden is, wordt dit naar een bestand geschreven dat als naam de vorm inputfilename.tempo.algoritme.pattern heeft. Indien er meer zijn gevonden wordt dit inputfilename.tempo.algoritme.x.pattern, met x een (nietsbetekenend) rangnummer.
Na het zoeken naar patronen wordt in de lijst van resultaten het beste patroon uitgekozen volgens volgende criteria: 1. Zoek alle patronen. 2. Indien er ´e´en patroon is met gradatie 1.0, geef dit als resultaat. Indien er meerdere patronen zijn met gradatie 1.0, geef het resultaat dat het meeste indices gebruikt. 3. Anders, geef de patronen weer met het meeste aantal herhalingen. Indien er meer dan ´e´en zijn, geef het resultaat dat het meeste indices gebruikt.
A.3. Output
p. 124
De laatste verzameling bestaat dan normaal gezien uit ´e´en patroon als er niet al te lage grenzen zijn gebruikt voor het verschil van lidmaatschapsgraad tussen twee patronen. Opmerking: deze bewerkingen moeten in deze volgorde uitgevoerd worden om het beste patroon te vinden. Een andere volgorde geeft niet hetzelfde resultaat.
Bijlage B
Projectbeschrijving Dit is de beschrijving zoals terug te vinden op de website van het Koninklijk Museum voor MiddenAfrika te Tervuren1 .
B.1
Klankarchief
Het klankarchief van de Dienst Etnomusicologie in het Koninklijk Museum voor Midden-Afrika te Tervuren (Belgi¨e) bevat een collectie klankopnamen van traditionele muziek uit Centraal-Afrika met de nadruk op Congo en Rwanda. Het beslaat in totaal 3000 uren muziekopnamen waarvan de oudste teruggaan tot 1910 (wassen rollen opgenomen door Hutereau in Uele-Congo). Het archief omvat verschillende geluidsdragers (Edisoncilinders, Sonofildraad, audiocassettes, magneetband, fonoplaten, CD’s ...) en daaraan gekoppeld metadata (steekkaartensysteem) en contextuele informatie (foto’s, film, video, bibliotheek en documenten van allerlei aard). De collectie werd samengesteld tijdens en na de koloniale periode van het Koninkrijk Belgi¨e in Centraal-Afrika. Zij is en blijft voor een aanzienlijk deel het muzikale geheugen van CentraalAfrika en naar omvang, documentatie en muzikale kwaliteit is zij zonder enige twijfel wereldwijd het belangrijkste klankarchief voor deze regio.
B.2
Opdracht
Het meest dringende objectief van het project is de strijd tegen de beschadiging van een aantal oude opnamen. Maar ook alle audio bestanden van deze delicate geluidsdragers moeten gedigitaliseerd worden evenals alle metadata, verbonden met deze audiobestanden, om de toegang tot de informatie op een gemakkelijkere manier te kunnen realiseren. Wat betreft de contextuele infor1 BRON:
http://music.africamuseum.be
125
B.3. Doelstellingen
p. 126
matie kan men stellen dat ook hier een gedeelte moet gedigitaliseerd worden terwijl een ander deel een meer uitgewerkte beschrijving vereist. Teneinde het archief open te stellen voor een breder publiek zijn databankfacilitieiten en internettoegang noodzakelijk. Van belang hierbij is dat deze databankfacilitieiten en de internettoegang ge¨ıntegreerd worden in de globale ICT-strategie van het Museum. Dit is de grootste uitdaging en tegelijk het vernieuwende aspect van dit project. Een vrije toegang tot deze belangrijke verzameling zal de interesse opwekken van onderzoekers, zodat de studie en het respect voor een rijke culturele traditie, die momenteel wordt bedreigd door lokale oorlogen, kan voortgezet en gepromoot worden. Wij hebben dan ook de morele plicht om te voorzien in de best mogelijke voorwaarden voor een duurzame en veilige bewaring, documentatie en beschikbaarheid van een dusdanig belangrijke collectie.
B.3
Doelstellingen
De doelstellingen van het project zijn: Klankdigitalisatie: Digitalisatie van het volledige klankarchief van de Dienst Etnomusicologie
van het KMMA Metadata Digitalisatie: Digitalisatie van de beschikbare metadata verbonden met het audio-
archief, wat het terugvinden van de audiobestanden toelaat Ontwikkeling van een Databank en Integratie: Een databank moet ontwikkeld worden en
volledig ge¨ıntegreerd in de huidige beschikbare infrastructuur voor informatie, communicatie en technologie (ICT) binnen het KMMA Contextuele Digitalisatie: Metadata productie en digitalisatie van de contextuele informatie
verbonden met het klankarchief Muzikale Informatie: Verkenning van data-mining technieken en het operationeel maken
ervan als een muzikaal informatiesysteem voor verdere toepassingen
B.4
Promotoren
Dr. J. GANSEMANS (EM - KMMA : Dienst Etnomusicologie - Koninklijk Museum voor
Midden-Afrika) Prof. Dr. M. LEMAN (IPEM - UGent : Afdeling Musicologie - Universiteit Gent) Prof. Dr. R. DE CALUWE (TELIN-CSL - UGent : Seminarie en Laboratorium voor
Informatica van de Vakgroep Telecommunicatie en Informatieverwerking - Universiteit Gent)
B.5. Financiering
p. 127
Prof. Dr. D. DEMOLIN (PHONOLAB - ULB : Laboratorium voor Fonologie - Universit´e
Libre de Bruxelles) ˆ Ir. A. DE MUELENAERE (ICT - KMMA : Dienst ICT - Koninklijk Museum voor MiddenAfrika)
B.5
Financiering
Federaal Wetenschapsbeleid Diensten van de Eerste Minister : Programmatorische Federale Overheidsdienst Wetenschapsbeleid Meerjarig Ondersteuningsprogramma voor de uitbouw van de Informatiemaatschappij
Bibliografie [1] Chang, Y.-Y., and Lin, Y.-C. Music tempo (speed) classification. [2] Dannenberg, R. B., and Hu, N. Pattern discovery techniques for music audio. In Proceedings of the 3rd International Conference on Music Information Retrieval (ISMIR), Paris, France (October 13-17 2002). [3] Degroeve, S., Tanghe, K., De Baets, B., Leman, M., and Martens, J.-P. A simulated annealing optimization of audio features for drum classification. In Proceedings of the International Conference on Music Information Retrieval (ISMIR), London, United Kingdom (September 11-15 2005). [4] GNU. General public license. http://www.gnu.org/licenses/gpl.txt. [5] IPEM. Instituut voor psychoacoustica en elektronische muziek, 2006. http://www.ipem.ugent.be. [6] IPEM. Musical audio-mining - query by humming”, 2006. ” http://www.ipem.ugent.be/MAMI. [7] Kerre, E. Introduction to the basic principles of fuzzy set theory and some of its applications. Communication and Cognition, 1991. [8] Leman, M. Digitale muziekbibliotheken: hoe kunnen we er muziek in terugvinden? In Digitale bibliotheken voor muzikale audio - Perspectieven en tendensen in digitalisering, archivering en ontsluiting van muziek, M. Leman, O. Cornelis, and A. Ganzevoort, Eds. 2006. [9] Levenshtein, V. I. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 6 (1966), 707–710. [10] London, J. Hearing in Time : Psychological Aspects of Musical Meter. Oxford University Press, USA, September 2004. [11] McKinney, M., and Moelants, D. Extracting the perceptual tempo from music. Proceedings of the 5th International Symposium on Musical Information Retrieval (ISMIR), Barcelona, Spain (2004). [12] Nakano, T., Ogata, J., Goto, M., and Hiraga, Y. A drum pattern retrieval method by voice percussion. In Proceedings of the 5th International Conference on Music Information Retrieval (ISMIR), London, United Kingdom (October 10-14 2004).
128
Bibliografie
p. 129
[13] Tanghe, K., Degroeve, S., and De Baets, B. An algorithm for detecting and labeling drum events in polyphonic music. Proceedings of the first Music Information Retrieval Evaluation eXchange (MIREX), London, United Kingdom (September 11-15 2005). [14] TELIN. Telecommunicatie en informatieverwerking, 2006. http://telin.ugent.be. [15] Van Steelant, D., De Baets, B., De Meyer, H., Leman, M., Martens, J.-P., Clarisse, L., and Lesaffre, M. Discovering structure and repetition in musical audio. In Proceedings of Eurofuse Workshop, Varenna, Italy (2002). [16] Van Steelant, D., Tanghe, K., Degroeve, S., De Baets, B., Leman, M., and Martens, J.-P. Support vector machines for bass and snare drum recognition. In Classification - the Ubiquitous Challenge: Proceedings of the 28th Annual Conference of the Gesellschaft F¨ ur Klassifikation e.V. University of Dortmund (March 9-11 2004), Studies in Classification, Data Analysis, and Knowledge Organization, Springer. [17] Van Steelant, D., Tanghe, K., Degroeve, S., De Baets, B., Leman, M., Martens, J.-P., and De Mulder, T. Classification of percussive sounds using support vector machines. In Proceedings of the annual machine learning conference of Belgium and The Netherlands, Brussels, Belgium (January 8-9 2004), Benelearn. [18] Zadeh, L. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems (1978).
Lijst van figuren 2.1 2.2 2.3
3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8
Voorbeeld input. Een patroon is hier tweemaal herhaald en bestaat uit negen noten. Visualisatie van algoritme 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gespeeld door een slaginstrument klinkt dit driemaal hetzelfde. Het is moeilijk om bij slaginstrumenten de duur van een noot te bepalen. . . . . . . . . . . . . . . . .
3 6 8 15 16 18 18 20 20 21
3.18 3.19 3.20 3.21 3.22 3.23 3.24
Vage Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Enkele lidmaatschapsfuncties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Te grote breedte: de intervallen rond b en c overlappen elkaar. . . . . . . . . . . . Te kleine breedte: noot c kan niet meer worden vergeleken. . . . . . . . . . . . . . Voor elke 2 noten wordt een possibiliteitsmaat berekend. . . . . . . . . . . . . . . . Een driehoekige lidmaatschapsfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . De bron-events uitgelijnd in de tijd . . . . . . . . . . . . . . . . . . . . . . . . . . . Het eerste tijdsinterval is langer dan de helft van het liedje. Er kan geen volgend interval meer gevonden worden om patronen te vergelijken. . . . . . . . . . . . . . De bron-events geknipt in gelijke intervallen na het derde event. . . . . . . . . . . . Zomaar ergens knippen na het vierde event levert geen goede uitlijning. . . . . . . De bron-events geknipt in gelijke intervallen na het vierde event. . . . . . . . . . . De bron-events geknipt in gelijke intervallen na het vijfde event. . . . . . . . . . . . De hele tijdsas wordt ingedeeld in 6 gelijke intervallen. . . . . . . . . . . . . . . . . Alle 5 mogelijke splitsingen van de intervallen voor fig. 3.13. . . . . . . . . . . . . . 3 intervallen samen geeft 2 segmenten, maar geen perfecte uitlijning. . . . . . . . . Ook rond de te vergelijken punten kan een schelp gemaakt worden. . . . . . . . . . Twee events, ofwel vergelijken we ze met elkaar ofwel moeten 2 nieuwe events bijgevoegd worden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ook rond punt b kunnen we een interval beschouwen. . . . . . . . . . . . . . . . . In de rechterfiguur ligt b dichter bij a maar heeft toch een lagere waarde voor p. . Alle mogelijke overlappeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . b ligt niet in het interval rond a, maar het interval rond b wel. . . . . . . . . . . . Bijna hetzelfde liedje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evenveel voorkomende patronen in het liedje, maar toch verschillend van elkaar. . De pauze duurt net zo lang als een patroon. . . . . . . . . . . . . . . . . . . . . . .
4.1 4.2
Deze twee patronen lijken niet op elkaar. . . . . . . . . . . . . . . . . . . . . . . . . Circulair bekijken van patroon2 levert toch patroon1 op. . . . . . . . . . . . . . . .
41 41
3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17
130
21 22 22 22 23 23 24 24 26 26 28 28 30 32 33 34 34
Lijst van figuren 4.3
5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19 5.20 5.21 5.22 5.23 5.24 5.25 5.26 5.27 5.28 5.29 5.30 5.31 5.32 5.33 5.34 5.35 5.36 5.37 5.38 5.39 5.40 5.41 5.42
p. 131
Als output-timestamp geven we het gemiddelde van de timestamps van de basispatronen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
De maxima zijn bij beide gevallen op dezelfde X te vinden Autocorrelatie van tabel 2.1 . . . . . . . . . . . . . . . . . Meer herhaling geeft een beter overzicht . . . . . . . . . . Autocorrelatie van onsets van tabel 2.2 . . . . . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van patroon uit 3.22a . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van patroon uit 3.22b . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van partituur 6.2 . . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.1 - 8 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.1 - 9 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.10 - 5 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.11 - 9 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.12 - 5 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.14 - 9 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.15 - 7 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.2 - 4 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.20 - 9 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.22 - 6 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.22 - 8 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Software resultaat met hogere gradatie . . . . . . . . . . . Autocorrelatie van onsets van 73.9.24 - 1 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.4 - 11 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.4 - 14 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . . Autocorrelatie van onsets van 73.9.6 - 1 - 20s . . . . . . . Autocorrelatie vs Software vs Ground Truth . . . . . . . .
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 65 66 67 68 69 70 70 71 72 73 74 75 76 77 78 79 80 81 81 82 83 84 85 86 87 88 89
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Lijst van figuren
p. 132
5.43 5.44 5.45 5.46 5.47 5.48 5.49 5.50 5.51 5.52 5.53 5.54 5.55 5.56 5.57 5.58 5.59 5.60 5.61 5.62 5.63 5.64 5.65 5.66 5.67 5.68
Autocorrelatie van onsets van 76.8.1 - 12 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 76.8.1 - 17 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 92.6.7 - 5 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 92.6.7 - 8 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.3 - 1 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.3 - 16 - 20s Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.3 - 5 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.3 - 6 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.3 - 7 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.8 - 10 - 20s Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.8 - 22 - 20s Detectie versus audio van 97.10.8 - 22 - 20s . . Autocorrelatie van onsets van 97.10.8 - 7 - 20s . Autocorrelatie vs Software vs Ground Truth . . Autocorrelatie van onsets van 97.10.8 - 8 - 20s . Autocorrelatie vs Software vs Ground Truth . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
90 91 92 93 94 95 96 97 97 99 99 100 101 102 103 105 105 106 107 108 109 109 110 111 112 113
6.1 6.2 6.3 6.4 6.5
De pauze verlegt de segmenten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bestaat dit uit 1 patroon? Of uit 2? Of uit 4? . . . . . . . . . . . . . . . . . . . . . Ritenuto: een stukje muziek wordt uitgerokken over de tijd. . . . . . . . . . . . . . Ritenuto is gevaarlijk bij het gebruik van gelijke intervallen. . . . . . . . . . . . . . Als we dan toch events mogen negeren, is het onderste interval bestaande uit slechts drie events evengoed een resultaat. . . . . . . . . . . . . . . . . . . . . . . . . . . .
118 119 119 120 120
Lijst van tabellen 2.1 2.2 2.3
De originele onsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . De aangepaste onsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hier zijn alle 8e noten (duur = 0.200s) gevonden als patroon voor lengte = 1. Er is enkel een structuur te zien als we meerdere noten bij elkaar nemen. Voor de leesbaarheid in milliseconden genoteerd. . . . . . . . . . . . . . . . . . . . . . . . . De originele onsets met berekende tussenwaarde . . . . . . . . . . . . . . . . . . . . Zelfgemaakte onsets met berekende tussenwaarde . . . . . . . . . . . . . . . . . . . Output: Enkele mogelijke patronen. De herhalingen zijn aangeduid door een rechthoek. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1 3.2 3.3
Perfecte matches tussen patronen uit figuur 3.22a. . . . . . . . . . . . . . . . . . . Maat voor match tussen patronen uit figuur 3.22b. . . . . . . . . . . . . . . . . . . Afstand tussen patronen uit figuur 3.23. . . . . . . . . . . . . . . . . . . . . . . . .
32 33 34
4.1
Classificatie van tussentijden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 ∗ OnsetT ime . . . . . . . . . . . . . . . . . . . . . . . . . . . Herschaald = 2.205 OnsetT ime − 0.025 . . . . . . . . . . . . . . . . . . . . . . . . . Herschaald = 4 ∗ 2.205 − 0.025
39
2.4 2.5 2.6
4.2 4.3 5.1 5.2 5.3
5 5
7 9 9
39 40
Alle gevonden patronen uit tabel 2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Alle gevonden patronen uit tabel 2.1 met toegevoegde ruis. . . . . . . . . . . . . . 48 Samenvattende tabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
133