Musiikin analysointia taajuuksien perusteella

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Kunnianhimoisena tavoitteena on tehdä ohjelma, joka analysoi biisejä ja ryhmittelee biisit eri genreihin. Täytyy kuitenkin edetä askel kerrallaan ja katsoa, että mihin asti tiedot / taidot riittävät.

Asioiden helpottamiseksi luen biisin datan WAV tiedostota. Tämä onnistuikin melko helposti (ohjelma olettaa saavansa 44.1 kHz, 16 bit mono dataa). Seuraavaksi ajattelin laskea DCT muunnoksia ja katsoa miltä biisit näyttävät taajuustasossa. Tähän tarvitsisi tietysti tehokkaan algoritmin, sillä dataa on melko paljon (etenkin jos haluaa analysoida 3 min sijasta 100 tuntia musiikkia). Onko kellään hihassa sopivaa koodia? Tällainen tuli vastaan: http://www.fftw.org/

FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST).



Tuo löytyi jopa Devpak:ina käyttämääni Dev-C++:an, mutta linkkeri väittää silti ettei tuota löydy. Tuo on kyllä opensourcea, mutta tuota on aika vaivalloista hyödyntää omassa ohjelmassani ilman suurehkoja muutoksia.

Wikipediasta opin, että DCT:n voi laskea O(n*log(n)) ajassa hyödyntäen FFT:tä (esim. Cooley-Tukey). Uskoakseni parempaan suorituskykyyn pääsisi kuitenkin ilman FFT:tä, koska käyttämäni data on täysin reaalista. O(n^2) algoritmi löytyy kivassa muodossa wikistä http://en.wikipedia.org/wiki/Discrete_cosine_transform, mutta se on optimointienkin jälkeen liian hidas. 2^14 datapisteelle kestää noin 2,5 sek, 2^15 pisteelle taasen yli 16 sekuntia.

Nyt ohjelma näyttää tällaista kuvaa: http://msdos464.no-ip.com/pics/wavdata.png

Vihreät palkit kuvaavat siis kyseisen taajuuden intensiteettiä (nämä on skaalattu siten, että aina jokin amplitudi saavuttaa "maksimin" (asteikko on skaalattu välille [-1, 1]).

Onko siis algoritmi ehdotuksia (tai ohjeita jonkin kirjaston käyttämiseksi)? Mp3 tiedostosta saisi vissiin datan suoraan taajuuksien amplitudeina, siinä mielessä se olisi paljon parempi formaatti.

Sivut

Kommentit (28)

Vierailija
msdos464
Wikipediasta opin, että DCT:n voi laskea O(n*log(n)) ajassa hyödyntäen FFT:tä (esim. Cooley-Tukey). Uskoakseni parempaan suorituskykyyn pääsisi kuitenkin ilman FFT:tä, koska käyttämäni data on täysin reaalista. O(n^2) algoritmi löytyy kivassa muodossa wikistä http://en.wikipedia.org/wiki/Discrete_cosine_transform, mutta se on optimointienkin jälkeen liian hidas. 2^14 datapisteelle kestää noin 2,5 sek, 2^15 pisteelle taasen yli 16 sekuntia.



Onhan tuo FFT paljon nopeampi kuin O(n^2) algoritmi. Tulee vielä selkeämmin esille, kun datamäärät ovat suuria. Eikö sekään riitä?

msdos464
Onko siis algoritmi ehdotuksia (tai ohjeita jonkin kirjaston käyttämiseksi)? Mp3 tiedostosta saisi vissiin datan suoraan taajuuksien amplitudeina, siinä mielessä se olisi paljon parempi formaatti.



Tämähän riippuu siitä kuinka paljon haluaa itse tehdä. Varmaankin mp3:sten käyttö tekisi hommasta askeleen helpompaa. Lisäksi ottaen huomioon mp3:sten yleisyyden, se saattaisi olla parempikin kuin .wavit.

Neutroni
Seuraa 
Viestejä26853
Liittynyt16.3.2005
msdos464
Kunnianhimoisena tavoitteena on tehdä ohjelma, joka analysoi biisejä ja ryhmittelee biisit eri genreihin. Täytyy kuitenkin edetä askel kerrallaan ja katsoa, että mihin asti tiedot / taidot riittävät.



Mitenköhän joku sellainen opetettava neuroverkkosofta suoriutuisi tuosta.

Wikipediasta opin, että DCT:n voi laskea O(n*log(n)) ajassa hyödyntäen FFT:tä (esim. Cooley-Tukey). Uskoakseni parempaan suorituskykyyn pääsisi kuitenkin ilman FFT:tä, koska käyttämäni data on täysin reaalista.



Muistaakseni tuo n*log(n) on raja noille. FFT on ihan hyvä algoritmi, kohtuullisen helppo implemetoida tehokkaasti. Kannattaa käyttää sitä (tai jotain sen sukulaista, cosinimuunnoksia tai Walshin muunnosta (konsultoi googlea tai signaalinkäsittelyn oppikirjaa)). n*log(n):stä parempaa et saa, mutta hieman nopeampia muunnoksia kuitenkin. Reaalisuus ei juurikaan säästä laskuja.

O(n^2) algoritmi löytyy kivassa muodossa wikistä http://en.wikipedia.org/wiki/Discrete_cosine_transform, mutta se on optimointienkin jälkeen liian hidas. 2^14 datapisteelle kestää noin 2,5 sek, 2^15 pisteelle taasen yli 16 sekuntia.



Tuo algoritmi kannattaa unohtaa, jos tekee jotain koulun alkeistehtävää vaativampaa.

Onko siis algoritmi ehdotuksia (tai ohjeita jonkin kirjaston käyttämiseksi)? Mp3 tiedostosta saisi vissiin datan suoraan taajuuksien amplitudeina, siinä mielessä se olisi paljon parempi formaatti.



Ehkä tosiaan kannattaa perehtyä mp3:een tai koodata FFT. FFT:n saanee miljoonana ohjelmakirjastona tai sorsanakin. Musiikkilajin tunnistamiseen ei tarvinne muuntaa koko kappaletta, vaan pätkiä sieltä täältä. Se on mielenkiintoisempi ongelma, miten taajuustason esityksestä sen paremmin tunnistat minkälaista renkutusta se on.

Vierailija
Neutroni
Wikipediasta opin, että DCT:n voi laskea O(n*log(n)) ajassa hyödyntäen FFT:tä (esim. Cooley-Tukey). Uskoakseni parempaan suorituskykyyn pääsisi kuitenkin ilman FFT:tä, koska käyttämäni data on täysin reaalista.



Muistaakseni tuo n*log(n) on raja noille. FFT on ihan hyvä algoritmi, kohtuullisen helppo implemetoida tehokkaasti. Kannattaa käyttää sitä (tai jotain sen sukulaista, cosinimuunnoksia tai Walshin muunnosta (konsultoi googlea tai signaalinkäsittelyn oppikirjaa)). n*log(n):stä parempaa et saa, mutta hieman nopeampia muunnoksia kuitenkin. Reaalisuus ei juurikaan säästä laskuja.



Juu tiedän että parempaan Big-O notaatioon ei päästä, mutta niissä algoritmeissa on kuitenkin (likimäärin) vakiokertoimen verran eroja. Mikäli käyttää FFT:tä DFT:n laskemiseen, siihen täytyy tehdä noita esi- ja jälkimuunnoksia että päästään haluttuun lopputulokseen.

DFT vaikuttaa siinä mielessä houkuttelevammalta, että saa pyöritellä kokonaislukuja ja spektri on (tietääkseni) "tiiviimpi" (wikin kuva aiheesta, käsittelee kylläkin kuvaa eikä ääntä)

Tällainen tuli myös vastaan: http://en.wikipedia.org/wiki/Discrete_wavelet_transform, pitää katsoa miltä sen tuloste näyttää.

Neutroni
Se on mielenkiintoisempi ongelma, miten taajuustason esityksestä sen paremmin tunnistat minkälaista renkutusta se on.



Juu niin on Pitää ensiksi muunnella noita erityyppisiä biisejä ja katsoa, että löytyykö sieltä mitään vihjeitä.

Vierailija

Tiedätte kai mikä on TAAJUUSERO puolisävelaskelen välillä!
Se on (2)^(1/12)=1,059463094.

Siis kun tolla kertoo tajuuden saa seuraavan puolisävelaskelen, esim v=>vis tai ves=>v.

Oktaavin ero alempaan on puoli-, ja ylempään kaksinkertainen.

Vierailija
msdos464
Kunnianhimoisena tavoitteena on tehdä ohjelma, joka analysoi biisejä ja ryhmittelee biisit eri genreihin. Täytyy kuitenkin edetä askel kerrallaan ja katsoa, että mihin asti tiedot / taidot riittävät.

Asioiden helpottamiseksi luen biisin datan WAV tiedostota. Tämä onnistuikin melko helposti (ohjelma olettaa saavansa 44.1 kHz, 16 bit mono dataa). Seuraavaksi ajattelin laskea DCT muunnoksia ja katsoa miltä biisit näyttävät taajuustasossa. Tähän tarvitsisi tietysti tehokkaan algoritmin, sillä dataa on melko paljon (etenkin jos haluaa analysoida 3 min sijasta 100 tuntia musiikkia). Onko kellään hihassa sopivaa koodia? Tällainen tuli vastaan: http://www.fftw.org/

FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST).



Tuo löytyi jopa Devpak:ina käyttämääni Dev-C++:an, mutta linkkeri väittää silti ettei tuota löydy. Tuo on kyllä opensourcea, mutta tuota on aika vaivalloista hyödyntää omassa ohjelmassani ilman suurehkoja muutoksia.

Wikipediasta opin, että DCT:n voi laskea O(n*log(n)) ajassa hyödyntäen FFT:tä (esim. Cooley-Tukey). Uskoakseni parempaan suorituskykyyn pääsisi kuitenkin ilman FFT:tä, koska käyttämäni data on täysin reaalista. O(n^2) algoritmi löytyy kivassa muodossa wikistä http://en.wikipedia.org/wiki/Discrete_cosine_transform, mutta se on optimointienkin jälkeen liian hidas. 2^14 datapisteelle kestää noin 2,5 sek, 2^15 pisteelle taasen yli 16 sekuntia.

Nyt ohjelma näyttää tällaista kuvaa: http://msdos464.no-ip.com/pics/wavdata.png

Vihreät palkit kuvaavat siis kyseisen taajuuden intensiteettiä (nämä on skaalattu siten, että aina jokin amplitudi saavuttaa "maksimin" (asteikko on skaalattu välille [-1, 1]).

Onko siis algoritmi ehdotuksia (tai ohjeita jonkin kirjaston käyttämiseksi)? Mp3 tiedostosta saisi vissiin datan suoraan taajuuksien amplitudeina, siinä mielessä se olisi paljon parempi formaatti.





tämmonen algoritmi

input:.........................................................................4 lukua

välivaihe:......................................2 keskiarvoa..........................2 poikkeamaa

output:..................................1 keskiarvo 1 poikkeama.........1 keskiarvo 1 poikkeama

luvut outputissa ovat eritaajuisten kanttiaaltojen voimakkuuksia
eka luku kertoo matalimman taajuuden, kolmas toiseksi matalimman

toka ja neljäs on sitten korkein ja toiseksi korkein taajuus, en tiedä kummassa järjestyksessä

ongelmaksi tässä algoritmissä olen todennut nimenomaan sen että järjestys on hiukka monimutkainen

Neutroni
Seuraa 
Viestejä26853
Liittynyt16.3.2005
jartsa

tämmonen algoritmi
...
ongelmaksi tässä algoritmissä olen todennut nimenomaan sen että järjestys on hiukka monimutkainen



Eikö tuo ole ihan normaali "bit reversal" -järjestys? Eli kirjoitetaan luku binäärilukuna ja luetaan bitijono lopusta alkaan. Noilla FFT:ssäkin piti puljata, ellen aivan väärin muista.

Vierailija
Neutroni
jartsa

tämmonen algoritmi
...
ongelmaksi tässä algoritmissä olen todennut nimenomaan sen että järjestys on hiukka monimutkainen



Eikö tuo ole ihan normaali "bit reversal" -järjestys? Eli kirjoitetaan luku binäärilukuna ja luetaan bitijono lopusta alkaan. Noilla FFT:ssäkin piti puljata, ellen aivan väärin muista.




voipi hyvinkin olla

minä kun en ihan oivaltanut FFT:tä tai bit reversallia

kattelin vaan että kahden luvun FFT on keskiarvo ja poikkeama,
joten neljän luvun sitten lienee sitä ja kahdeksan tätä

no siitä tulikin sitten kanttiaalto muunnos

mikä onkin juuri mitämsdos tilasi:
monta millisekuntia säästyy jos voi vaan antaa olla tossa järjestyksessä, ja keskiarvon laskemisesta jos jättää kahdella jakemisen pois, niin taas nopeutuu, ja tarkentuu

Vierailija

Tuo taitaa olla juuri se mitä olen nyt kokeilemassa.

Javaa wikistä:

[code:2nxglmz7]public static int[] invoke(int[] input)
{

//This function assumes input.length=2^n, n>1
int[] output = new int[input.length];

for (int length = input.length >> 1; ; length >>= 1) {
//length=2^n, WITH DECREASING n
for (int i = 0; i < length; i++) {
int sum = input[i*2]+input[i*2+1];
int difference = input[i*2]-input[i*2+1];
output[i] = sum;
output[length+i] = difference;
}
if (length == 1)
return output;

//Swap arrays to do next iteration
System.arraycopy(output, 0, input, 0, length<<1);
}
}[/code:2nxglmz7]

Tuo ei kyllä näytä yhtä kivalta kuin DCT...

Vierailija

En oikein kysymyksestä täysin kärryille päässyt, mutta lado päällekkäin sopivalla liukuvalla ikkunalla (kiertopuskurilla) keskiarvoa, vähennys, summaus ja bittisiirto. Kaikki korkeat taajuudet suodattuvat pois, ja jäljelle jää rytmikäppyrä. (Muuten jos haluaa, rytmikäppyrän voi summata alkuperäiseen, niin supparitkin saavat jotain toistettavaa).

Tarvitsin joskus tuollaista tehokasta rytminbongaajaa pieneen sulautettuun systeemiin, jolla oli vain näyte ko. ihmisen puheesta. Muu puhe sitten koodattiin mööpeliin 1:1000000 pakkaussuhteella, josko makrokieltä sellaiseksi voi edes kutsua. Ei se perinteinen signaalinkäsittely aina välttämättä ole paras vaihtoehto. Riippuu paljon tapauksesta ja käyttötarpeesta.

(Muuten mööpeli muunsi naisen puheen miehen puheeksi ja päinvastoin. Aika koomisen kuuloista oli, mutta elämä on.)

Vierailija

Miten saisi filtterin joka olisi "high-pass" ja "low-pass" filttereiden väliltä (vissiin sitten "Band-pass")? Wikistä löytyi O(N) algoritmit noille kahdelle:

High-pass:
[code:1m611p1u] y[0] := x[0]
for i from 1 to n
y[i] := alpha*(y[i-1] + x[i] - x[i-1])
return y
[/code:1m611p1u]

Low-pass:
[code:1m611p1u] y[0] := x[0]
for i from 1 to n
y[i] := y[i-1] + alpha * (x[i] - y[i-1])
[/code:1m611p1u]

Band-pass filterillä voisi skannata sopivat alueet, algoritmi olisi edelleen kokonaisuudessaan O(N).

Waveleteista ei tullut niin eleganttia tulostusta kuin DCT:llä.

Neutroni
Seuraa 
Viestejä26853
Liittynyt16.3.2005
msdos464
Miten saisi filtterin joka olisi "high-pass" ja "low-pass" filttereiden väliltä (vissiin sitten "Band-pass")? Wikistä löytyi O(N) algoritmit noille kahdelle:



Googlaa FIR ja bandpass. Voit myös tehdä peräkkäin ali- ja ylipäästöt sopivilla rajataajuuksilla.

Waveleteista ei tullut niin eleganttia tulostusta kuin DCT:llä.



Kokeilitko sitä bit reversalia lukujen uudellenjärjestämisessä? (en tiedä autaako se, mutta tuosta selityksestä sai sen vaikutelman, että voisi auttaa). Se menee siis näin (luvut binäärisiä):

0000 -> 0000
0001 -> 1000
0011 -> 1100
0100 -> 0010
...
1110 -> 0111
1111 -> 1111

Vierailija

En kokeillut... tuhosin jo sen osan koodista kun se näytti niin "rumalta". Olisi pitänyt kyllä ottaa ainakin screenshotti.

Nyt testailen high-pass filtteriä siten, että filteröin alkuperäisestä datasta A korkeat taajuudet talteen taulukkoon B. Lasken B:lle amplitudien neliöiden summan talteen ja vähennän A:n alkioista B:n vastaavat alkiot. Sitten tämä toistetaan, mutta päästetään hieman matalammat taajuudet läpi.

Vierailija

Nyt olen FFT:tä testaillut, se vaikuttaa (tällä hetkellä) parhaalta vaihtoehdolta (en löytänyt sopivaa bandpass filtterin algoritmia).

Oma FFT funkkari suoriutuu laskennasta tällaista tahtia:

[code:2wqmwluf]N FFT / sec
512 2210
1024 1460
2048 800
4096 460
8192 230
16384 120[/code:2wqmwluf]

Tuossa on siis datapisteiden määrä ja montako FFT muunnosta lasketaan sekunnissa.

Täällä on kaava [mflops = 5 N log2(N) / (time for one FFT in microseconds)] ja benchmarkkeja.

Itselläni nuo mflopsit kasvavat tasaisesti 50:stä 140 asti, isommilla datoilla on parempi. En raaskinut jakaa kakkosella noita, vaikka tuolla sivulla käskettiin tehdä reaalidatalle niin. Ilmeisesti tässä olisi mahdollisuus noin 5 kertaiseen nopeuteen. Pitää koittaa karsia noita mallockeja. Kun nuo epx(2*PI*I*n/N) lausekkeet cachesi päästiin jo 4-5 kertaiseen nopeuteen. Jos tuon säikeistäisi (helppo tehdä Cooley-Tukeylle heti alussa) saisi tällä Quad-corella helposti 3-kertaisen nopeuden. Lisäksi voinen hylätä ylimmät taajuudet, koska siellä ei tunnu oikein olevan eloa noissa biiseissä.

http://en.wikipedia.org/wiki/Image:Windowlicker_spiral.png
http://koti.mbnet.fi/msdos464/dl/aphex.png

Raportoin taas jos jotain uutta ilmenee.

Vierailija

Hieman kiinnostaa, että mitä -- vaikka täydellinen algoritmi ja menetelmä löytyisikin -- tällä haetaan.

Musiikkigenreistä väännetään filosofian tyyliin loputtomasti, koska eri genreillä harvoin on kivenkovat rajat ja määritelmät. Ammattilaisetkin ovat eri mieltä genrejen määritelmistä, niiden tarpeellisuudesta puhumattakaan.

Ei niin, etteikö tämä olisi mielenkiintoinen tai jopa tarpeellinen asia esim. tekoälyn musikaalisuuden kehittämisessä.

Vierailija

Lähinnä varmaankin haetaan ratkaisua, jolla voidaan koneellinen musiikkia nopeasti lajitella about oikein esim. omiin kansioihinsa.

Sivut

Uusimmat

Suosituimmat