autokorrelaatio
Ilkka Seppälä
tarvitsisin yksityiskohtaisen selostuksen miten autokorrelaatio
algoritmi toimii. Tavoitteena olisi löytää digitaalisesta
musiikkidatasta iskua-minuutissa (bpm) luku. Käsittääkseni myös Fast
Fourier Transform (FFT) voisi olla hyödyksi projektissa. Linkit yms.
otetaan kiitollisena vastaan..
---
Ilkka
Sampo Smolander
Kannattaa etsiä kirjahyllystä/kirjastosta mikä tahansa
aikasarja-analyysin (=time series analysis) oppikirja.
Tai ehkä sellainen, joka juuri sinun silmääsi miellyttää.
- Sampo Smolander
Seppo Pitkänen
merkityksessä "autokorrelaatio" -käsitettä käytetään Ilkan
terminologiassa. Aikasarja-analyysin tai ekonometrian oppikirjoista
tuskin on hyötyä kysyttyn ongelmaan, noinkin selkeästi
digitaalitekniikkaan liitettynä. Eihän koko käsite sinänsä ole sen
enempää kuin peräkkäisten havaintojen/signaalien riippuvuus,
itse-generoivuus hienommin sanottuna.
S.P.
Sampo Smolander skrev:
Ilkka Seppälä
> Puhutte varmaan eri kieltä (?). Minua kiinostaisi tietää, missä
> merkityksessä "autokorrelaatio" -käsitettä käytetään Ilkan
> terminologiassa. Aikasarja-analyysin tai ekonometrian oppikirjoista
> tuskin on hyötyä kysyttyn ongelmaan, noinkin selkeästi
> digitaalitekniikkaan liitettynä. Eihän koko käsite sinänsä ole sen
> enempää kuin peräkkäisten havaintojen/signaalien riippuvuus,
> itse-generoivuus hienommin sanottuna.
>
> S.P.
Tällä hetkellä saan musiikkidatasta ns. biitit erotettua aika hyvin
algoritmillani mutta mukaan tulee myös ylimääräisiä kovia ääniä jotka
eivät ole biittejä. Periaatteessa data voidaan käsittää pitkänä
sarjana nollia ja ykkösiä jossa 0 tarkoittaa ei biittiä ja 1 on biitti
->
0000111000011100000110111100000111000011000000100001110000111
Nyt tästä sarjasta pitäisi löytää jaksollisuus joka toteutuu parhaiten
tietyissä rajoissa (voidaan sanoa että minimi bpm on vaikka 60 ja
maksimi 200). Käsittääkseni paras metodi tähän on ns. autokorrelaatio
algoritmi mutten tiedä miten se toteutetaan. Eli tähän tarvitsen apua.
---
Ilkka
Jyrki Lahtonen
Ilkka Seppälä wrote:
>
>
> Tällä hetkellä saan musiikkidatasta ns. biitit erotettua aika hyvin
> algoritmillani mutta mukaan tulee myös ylimääräisiä kovia ääniä jotka
> eivät ole biittejä. Periaatteessa data voidaan käsittää pitkänä
> sarjana nollia ja ykkösiä jossa 0 tarkoittaa ei biittiä ja 1 on biitti
> ->
>
> 0000111000011100000110111100000111000011000000100001110000111
>
> Nyt tästä sarjasta pitäisi löytää jaksollisuus joka toteutuu parhaiten
> tietyissä rajoissa (voidaan sanoa että minimi bpm on vaikka 60 ja
> maksimi 200). Käsittääkseni paras metodi tähän on ns. autokorrelaatio
> algoritmi mutten tiedä miten se toteutetaan. Eli tähän tarvitsen apua.
>
> ---
> Ilkka
Ainakin GPS-synkronointikoodien parametreja laskettaessa autokorrelaatio
tarkoittaa suurin piirtein seuraavaa: muutetaan tuo nollien ja ykkösten
jono ykkösten ja miinusykkösten jonoksi (jolloin keskiarvoksi tulee
suurin piirtein nolla, ainakin jos sämpläystaajuus on riittävän iso).
Näin saadaan funktio x:{0,...,L-1}->{+1,-1}. Esimerkiksi yllä mainitulle
datalle tulisi funktioksi
x(0)=1, x(1)=1, x(2)=1, x(3)=1, x(4)=-1, x(5)=-1, x(6)=-1 jne.
(nolla ykköseksi ja ykkönen miinusykköseksi)
Nyt autokorrelaatio on sitten
theta(t)=summa x(i)*x(i+t),
missä t on jokin ei-negatiivinen aikasiirtymä, ja summaus käy läpi
i:n arvot nollasta ylärajaan L-t-1 saakka (jos teet summauksen vain
osasta dataa, niin voit järjestää tilanteen sellaiseksi parametriä
L pienentämällä, että kaikilla tutkittavilla t:n arvoilla on
ko. summassa L kappaletta yhteenlaskettavia).
Huomataan, että theta(0)=L (= suurin mahdollinen arvo). Jos data
olisi täysin jaksollista, esimerkiksi aina x(i)=x(i+t), niin myös
vastaava autokorrelaatio theta(t) olisi mahdollisimman suuri
(= kaikki yhteenlaskettavat plusmerkkisiä). Esimerkiksi laskettaessa
summaa theta(7) esimerkkidatallesi, olisivat 7 ensimmäistä termiä
kaikki plusmerkkisiä, koska datan alussa 7 bitin jakso toistuu.
Toisaalta, jos aikasiirtymä t on sellainen, että x(i) ja x(i+t)
eivät lainkaan riipu toisistaan, niin silloin theta(t) on hyvin
pieni (summassa yhtä paljon plus- ja miinusmerkkisiä, joten
tapahtuu paljon kumoutumista).
Aloittaisin siis laskemalla theta(t):n arvoja, ja etsisin sieltä
maksimeja. Oletettavasti theta-funktion kuvaaja muistuttaa jonkin
verran sinikäyrää. Siitä sitten pitäisi etsiä pienin positiivinen
maksimikohta, jota vastaava aika-ero antanee hyvän arvauksen
biitin kestolle. Koska sinulla on kohtuullinen ennakkokäsitys
biitin kestosta, niin voit rajoittaa tutkimuksesi mielenkiintoisiin
t:n arvoihin.
Todennäköisesti et tarvitse koko kappaleen digitoimista. Siitä
voi olla jopa haittaa, jos datasettisi ohittaa fermaatin/ritardandon
(rubato-kappaleesta puhumattakaan), jolloin tahti sekoaa jonkin verran.
Jos tämä oli vain banaalia toistoa muualta lukemaasi, niin pyydän
anteeksi haaskaamaani kaistaleveyttä.
Cheers,
Jyrki Lahtonen,
Turun yliopisto
Sampo Smolander
> Puhutte varmaan eri kieltä (?). Minua kiinostaisi tietää, missä
> merkityksessä "autokorrelaatio" -käsitettä käytetään Ilkan
> terminologiassa. Aikasarja-analyysin tai ekonometrian oppikirjoista
> tuskin on hyötyä kysyttyn ongelmaan, noinkin selkeästi
> digitaalitekniikkaan liitettynä. Eihän koko käsite sinänsä ole sen
> enempää kuin peräkkäisten havaintojen/signaalien riippuvuus,
> itse-generoivuus hienommin sanottuna.
Puhumme ihan samasta asiasta. Autokorrelaatio ja
Fourier-muunnos (myös FFT) sopivat menetelminä yhtä hyvin
osakurssien ja äänitiedostojen ominaisuuksien katselemiseen.
Tai no, äänidatasta saattaa jotain oikeaa löytyäkin :-)
- Sampo Smolander
Ilkka Seppälä
> Nyt autokorrelaatio on sitten
>
> theta(t)=summa x(i)*x(i+t),
>
> missä t on jokin ei-negatiivinen aikasiirtymä, ja summaus käy läpi
> i:n arvot nollasta ylärajaan L-t-1 saakka (jos teet summauksen vain
> osasta dataa, niin voit järjestää tilanteen sellaiseksi parametriä
> L pienentämällä, että kaikilla tutkittavilla t:n arvoilla on
> ko. summassa L kappaletta yhteenlaskettavia).
>
> Huomataan, että theta(0)=L (= suurin mahdollinen arvo). Jos data
> olisi täysin jaksollista, esimerkiksi aina x(i)=x(i+t), niin myös
> vastaava autokorrelaatio theta(t) olisi mahdollisimman suuri
> (= kaikki yhteenlaskettavat plusmerkkisiä). Esimerkiksi laskettaessa
> summaa theta(7) esimerkkidatallesi, olisivat 7 ensimmäistä termiä
> kaikki plusmerkkisiä, koska datan alussa 7 bitin jakso toistuu.
Kiitos kattavasta selvityksestä. Yksi kysymys vielä jäi. Pitääkö
autokorrelaatiot laskea useammalla alkupisteellä vai antaako se
luotettavan tuloksen käyttämällä vain yhtä alkupistettä? Esimerkiksi
seuraava sarja
01010101
jos alkupiste tässä on x(0) ja t=2 niin ei löydy yhtään biittiä. Jos
taas alkupisteenä x(1) niin kaikki biitit täsmäävät. Pitääkö laskea
autokorrelaatiot molemmille alkupisteille x(0) ja x(1)?
Jyrki Lahtonen
Ilkka Seppälä wrote:
>
>
> Kiitos kattavasta selvityksestä. Yksi kysymys vielä jäi. Pitääkö
> autokorrelaatiot laskea useammalla alkupisteellä vai antaako se
> luotettavan tuloksen käyttämällä vain yhtä alkupistettä? Esimerkiksi
> seuraava sarja
>
> 01010101
>
> jos alkupiste tässä on x(0) ja t=2 niin ei löydy yhtään biittiä. Jos
> taas alkupisteenä x(1) niin kaikki biitit täsmäävät. Pitääkö laskea
> autokorrelaatiot molemmille alkupisteille x(0) ja x(1)?
Öö, nyt en ymmärtänyt. Tarkista alla olevista laskuista, että
ymmärsit oikein theta(t):n määritelmän. Tuolle datallehan saatiin
x(0)=x(2)=x(4)=x(6)=1 ja x(1)=x(3)=x(5)=x(7)=-1
joten nolla alkupisteenä
theta(0)= 1+1+1+1+1+1+1+1=8,
theta(1)=-1-1-1-1-1-1-1=-7,
theta(2)= x(0)*x(2)+x(1)*x(3)+....+x(5)*x(7)=
= 1+1+1+1+1=6
theta(3)=-1-1-1-1-1=-5
jne.
ja yksi alkupisteenä (siis theta(t)=summa_{i=1}^L x(i)x(i+t)
theta(0)=1+1+1+1+1+1+1=7
theta(1)=-1-1-1-1-1-1=-6
theta(2)= x(1)*x(3)+x(2)*x(4)+...x(5)*x(7)=
= 1+1+1+1+1=5
theta(3)=-1-1-1-1=-4
mielestäni theta(2) erottuu selkeänä maksimina kummassakin, joten
päättelemme, että 2 on tuolle datalle "melkein" jakso. Unohdin ehkä
korostaa, että maksimi on lokaali maksimi, siis esimerkiksi
tässä riittää, että theta(2) on selkeästi suurempi kuin theta(1)
ja theta(3). Kannattaa ehkä plotata theta:n kuvaaja, sillä myös
"selkeästi suurempi" on tässä suhteellinen käsite.
Oletan, että nuo bittisi vastaavat joitakin painotettuja arvoja
(=samples) esim wav-datasta. Tässä myös sämpläystaajuuden on
oltava riittävän korkea, jotta tuo "likimääräinen jaksollisuus"
(biitin välein) tulisi kunnolla näkyviin.
Cheers,
Jyrki Lahtonen
Ilkka Seppälä
> Oletan, että nuo bittisi vastaavat joitakin painotettuja arvoja
> (=samples) esim wav-datasta. Tässä myös sämpläystaajuuden on
> oltava riittävän korkea, jotta tuo "likimääräinen jaksollisuus"
> (biitin välein) tulisi kunnolla näkyviin.
Tämähän toimii paljon paremmin kuin odotin! Autokorrelaatio arvot näyttävät
tosiaan
muodostavan sinikäyrän muodon joten oletan että lasken sen oppiesi mukaan
oikein. Kiitoksia
asiantuntevasta avusta ja hyvää kesän jatkoa!
---
Ilkka Seppälä