De unde 演iu melodia asta?

Cristian Fr滱cu -- francu@cs.rutgers.edu, http://www.cs.rutgers.edu/~francu
Mihai Budiu -- mihaib+@cs.cmu.edu, http://www.cs.cmu.edu/~mihaib/

august 2000

Subiect:
recunoa演erea muzicii
Cuno演ine necesare:
cuno演ine elementare despre muzic 槐 baze de date
Cuvinte cheie:
semnal, e榮ntionare, cuantizare, c綦tare, indexare, bibliotec digital


Cuprins




Evoluia calculatoarelor spre multimedia

John von Neumann este considerat creatorul arhitecturii calculatoarelor a榮 cum o cunoa演em ast罳i. Neumann a ajuns la calculatoare din dorina de a rezolva probleme de fizica fluidelor. Multe ecuaii difereniale nu admit soluii analitice (adic sub forma unei formule), ci pot fi rezolvate doar aproximativ, numeric. Cum calculatoarele cu care avea de a face erau extrem de nefiabile, von Neumann 槐-a suflecat m螽ecile 槐 s-a apucat s le amelioreze, pentru a putea g綼i soluiile care-l interesau. El a propus o mulime de concepte care 槐 ast罳i se reg綼esc 螽 arhitectura calculatoarelor, cum ar fi separarea funcionalit裻ii fizice 槐 logice a circuitelor (adic construcia de pori logice din tuburi - mai t褳ziu tranzistoare, 槐 acum circuite integrate, care apoi pot fi manipulate independent de modul 螽 care sunt construite, ca ni演e obiecte matematice ideale), 槐 diviziunea calculatorului 螽 unitate de procesare, unit裻i de intrare-ie槐re 槐 memorie 螽 care sunt stocate at褾 programele c褾 槐 datele prelucrate.

Dar, de槐 a anticipat 槐 dat na演ere multor idei seminale, povestea spune c von Neumann a fost foarte sup綖at pe un colaborator de-al s綦, care 螽cerca s scrie un asamblor. Asamblorul e un program care u滾reaz munca programatorului, permi螽du-i s scrie programele 螽tr-un limbaj textual 螽 loc de a folosi 槐ruri de zero 槐 unu, 螽 cod-ma槐n. Von Neumann spunea c timpul de calcul este irosit f綷螽d o activitate pe care o poate face foarte bine omul.

Ast罳i afirmaia lui von Neumann ni se pare absolut anacronic, dar acest lucru se 螽t螸pl pentru c balana 螽tre costul puterii de calcul 槐 cel al muncii omene演i s-a schimbat absolut dramatic; la ora de ast罳i orice investiie care mut efortul omenesc pe seama unui calculator este productiv.

De-a lungul timpului tipurile de prelucrare f綷ute de calculatoare s-au diversificat enorm; cre演erea capacit裻ii de stocare 槐 prelucrare ne-a permis s trecem 螽cetul cu 螽cetul de la procesarea unor cantit裻i infime de date la folosirea unor baze de date enorme, la folosirea interfeelor grafice sofisticate, la comunicaii care 螽globeaz tot mai mult imagine, sunet, film, culoare.

Dar dac ast罳i lumea str螸b din nas la ideea folosirii unui browser 螽 mod text (de槐 numai 螽 urm cu 10 ani gopher-ul era cea mai avansat tehnologie), evoluia 螽 complexitatea informaiei procesat 螽 mod curent de c綟re calculator este departe de a fi 螽cheiat. Chiar dac ast罳i o mulime de site-uri de web au grafic spectaculoas, 槐 jocurile 螽 spaii tridimensionale sunt banalit裻i, o mulime de alte operaii elementare sunt 螽c foarte greu de f綷ut de c綟re calculator. Chiar stocarea 槐 transmisiunea informaiei video este extrem de primitiv, cele mai evoluate sisteme put螽d transmite imagini de dimensiunea unui timbru (vorbim de produse disponibile comercial, 槐 nu de experimente 螽 laborator).

姷 ceea ce prive演e imaginile 槐 muzica, situaia este ceva mai bun: 演im s le stoc緆, livr緆, reproducem 槐 螽registr緆. Dac este 螽s vorba de proces綖i mai complicate, suntem 螽c foarte neajutorai.

姷 textul de fa vom investiga felul 螽 care putem manipula muzica digital.

Acest articol se bazeaz pe cercetarea unuia dintre autori, Cristian Fr滱cu; rezultatele sale au fost prezentate de cur螽d cu mult succes la conferina internaional despre multimedia ICME 2000. Aparent sistemul construit de el pentru recunoa演erea melodiilor dup exemple este cel mai performant 螽 existen la ora actual. Algoritmii dezvoltai de Cristi 螸preun cu grupul lui de cercetare vor forma baza unei biblioteci digitale de muzic, 螽 curs de dezvoltare.

Despre sunet

Dar 螽ainte de a putea plonja 螽 detaliile modului 螽 care muzica poate fi indexat 槐 c綦tat, va trebui s discut緆 puin despre cum se 螽registreaz muzica 螽 mod digital.

Sunetul se propaga prin aer sub forma unei unde; aceast und poate fi caracterizat prin amplitudinea ei 螽 fiecare moment. Un sunet ``pur'', fundamental, are amplitudinea descris de o sinusoid. Frecvena sinusoidei (inversul perioadei) se nume演e ``frecvena sunetului'', 槐 se m綼oar 螽 hertzi, Hz.

C螽d mai multe surse emit sunete simultan, undele lor se suprapun (se adun) 槐 auzim sunetul rezultant. Dintre sunetele instrumentelor muzicale, cel mai apropiat de un sunet pur este cel al flautului. Toate instrumentele emit de fapt o mixtur de sunete, dintre care unul este preponderent; de aceea nota ``la'' c螽tat la pian sun altfel dec褾 nota ``la'' c螽tat la vioar, de槐 ambele au aceea槐 frecven (stabilit la 440hz). 姷 natur nu exist surse de sunete pure, dar ele pot fi generate electronic, folosind oscilatoare.

Chiar dac putem genera sunete pure, urechea omeneasc nu le poate auzi: chiar organele de sim din ureche vibreaz ele 螽sele 槐 intr 螽 rezonan cu alte frecvene dec褾 cele prezente 螽 sunetul ambiant (genereaz ceea ce se numesc ``armonici auriculare''). Pe l螽g faptul c genereaz sunete inexistente, urechea omeneasc este inegal de sensibil la frecvene diferite; aparatul auditiv poate percepe sunete 螽tre 16hz 槐 24khz, fiind cel mai sensibil 螽 jurul frecvenei de 4khz (sensibil 螽semn螽d c poate auzi semnalele cu energia cea mai mic). De asemenea, sensibilitatea scade cu v褳sta.

Toate aceste sl綧iciuni ale aparatului auditiv uman sunt exploatate de metodele de 螽registrare digital. Toate aceste metode filtreaz sunetul 螽 a榮 fel 螽c褾 s 螽registreze doar o band 螽gust de frecvene.

Putem distinge dou clase mari de metode de stocare a muzicii sub form digital: 螽registr綖ile 槐 descrierile simbolice. Ne vom ocupa pe scurt de fiecare dintre ele.

姷registr綖i digitale

姷registr綖ile digitale sunt echivalente cu tehnicile de 螽registrare analogic patentate de Edison 螽 urm cu 127 de ani: capteaz un semnal din aer, 螿 prelucreaz, codific 槐 stocheaz. Spre deosebire de patefon, tehnicile digitale descriu semnalul prin secvene de cifre 槐 nu prin procese fizice (de exemplu, patefonul descrie semnalul prin forma 榮nurilor de pe disc).

E榮ntionare 槐 cuantizare

Pentru a putea transforma o m綖ime continu 螽tr-o serie de numere trebuie s facem dou operaii distincte: s o e榮ntion緆 槐 s o cuantiz緆.

Figura 1: Semnalele 螽registrate sunt funcii continue de timp (a). Semnalul este 螽t蟊 e榮ntionat, m綼ur螽d valoarea lui 螽tr-un num綖 finit de puncte, de regul echidistante (b). Apoi valorile e榮ntioanelor sunt codificate cu un num綖 finit de bii 螽 procesul de cuantizare (c). 姷 aceast figur cuantizarea s-a f綷ut cu 3 bii, care pot distinge opt valori diferite ale amplitudinii (unele pozitive, unele negative.)
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{esantionare.eps}}\end{figure}

E榮ntionarea m綼oar semnalul audio din timp 螽 timp, de obicei cu o perioad fix. Teorema lui Nyquist arat c dac vrem s 螽registr緆 un semnal ale c綖ui frecvene componente sunt sub X hz, e suficient s e榮ntion緆 semnalul cu frecvena 2X hz. Compact-disc-urile de pild e榮ntioneaz sunetul la 44.1 khz, ceea ce este dublul lui 22.05khz, care este o limit mult 螽afara auzului celor mai multe persoane (dac nu a tuturor). Teorema lui Nyquist arat c din aceste e榮ntioane, 螽 num綖 finit, se poate reconstitui complet, f綖 nici un fel de pierderi, forma semnalului original, continuu! Figura 1 ilustreaz aceste procedee.

Astfel am rezolvat problema transform綖ii unui semnal continuu 螽tr-o secven finit de valori discrete. Dar fiecare din aceste valori poate fi exprimat printr-un num綖 real, care ar putea avea nevoie de o precizie infinit pentru a fi exprimat. Sistemele de 螽registrare digital aproximeaz valorile posibile ale amplitudinii printr-un num綖 finit; acesta este procesul de cuantizare. Intervalul 螽tre amplitudinea zero 槐 o amplitudine maxim posibil este 螸p綖it 螽 segmente (de obicei egale). Num綖ul de segmente este apoi codificat printr-un num綖 de bii. De exemplu, compact disc-urile folosesc 16 bii de precizie pentru a descrie o valoare a amplitudinii; asta 螽seamn c pot distinge 216 = 65536 de nivele diferite de amplitudine, suficient de fine pentru a p綷緄i urechea uman.

PCM 槐 CD-urile

Dac 螽registr緆 valoarea fiec綖ui e榮ntion 螽 ordinea 螽 care apar am 螽registrat efectiv sunetul. Acest gen de descriere a unui semnal se nume演e ``modulare cu pulsuri'', pulse code modulation, prescurtat PCM.

Compact-disc-urile stocheaz informaia necomprimat; dimpotriv, pentru a preveni erorile care pot ap綖ea din cauza zg褳ieturilor, expandeaz informaia 槐 o codific 螽 mod redundant: dac unii bii dispar, ei pot fi reconstituiim 螽 m綼ura 螽 care stric綷iunile nu sunt prea mari.

Un CD 螽registrat stereo are deci dou canale care conin 44100 de valori de 16 bii pentru fiecare secund de muzic; asta 螽seamn o rat de transfer a informaiei de 2 * 44100 * 16 = 1.411Mbps (megabii pe secund). Aceasta este viteza cu care informaia iese din CD-player-ul calculatorului dumneavoastr; 螽 interior rata este chiar mai mare, din cauza codific綖ii redundante. Un compact disc poate stoca aproximativ 70 de minute de muzic, av螽d deci o capacitate de 70 * 60 * 1.411 / 8 = 740 MB (megaoctei). Pe un hard-disc de 20 de gigaoctei putem deci stoca aproximativ 25 de CD-uri.

Tipul standard de fi槐er de sunet 螽 Microsoft Windows este cel cu extensia .wav, care codific de obicei informaia tot 螽 form PCM. De asemenea, PCM este metoda folosit pentru codificarea vocii 螽 telefonia digital 槐 ISDN.

Compresie digital

Prin e榮ntionare 槐 cuantizare putem stoca informaiile din orice semnal continuu (螽 anumite limite de frecven). Adesea 螽s informaia din acest semnal este foarte ampl 槐 redundant. Depinz螽d de mediul de stocare 槐 transmisie putem dori s reducem informaia sau nu.

Mai multe scheme din ce 螽 ce mai sofisticate au fost dezvoltate pentru a comprima muzica. Putem distinge dou mari categorii de metode de compresie: compresie cu pierderi 槐 compresie f綖 pierderi. Compresia f綖 pierderi poate oric螽d reconstitui identic semnalul original; cea cu pierderi decide s arunce la gunoi informaiile ``neimportante''.

Compresie f綖 pierderi

Un program care comprim un semnal audio se nume演e codec, de la codor-decodor. Fiecare firm mare din telecomunicaii, industria electronic a echipamentelor audio 槐 din software a dezvoltat propriile codec-uri; cele mai multe dintre acestea sunt secrete bine p罳ite.

姷 general, nu putem comprima dec褾 puin muzica dac insist緆 s nu avem pierderi (lossless), dar pentru aplicaii specifice compresia f綖 pierderi este acceptabil ca performan (m綼urat prin resurse de calcul consumate pentru a obine o anumit calitate a sunetului). De exemplu, vocea uman are un spectru relativ 螽gust, 槐 variaiile de intensitate 槐 frecven nu sunt foarte mari 螽 timp scurt.

Metode eficace de compresie sunt compresia diferenial (DPCM) 槐 compresia adaptiv diferenial (ADPCM). Compresia diferenial, 螽 loc de a codifica fiecare e榮ntion separat, codific diferena dintre dou e榮ntioane succesive; dac semnalul nu poate varia foarte repede, aceast diferen va fi 螽totdeauna mic, 槐 deci va putea fi transmis cu mai puini bii (folosind de exemplu un cod Huffmann).

Compresia adaptiv merge chiar mai departe: folose演e un model predictiv al semnalului, 槐 calculeaz 螽 fiecare clip care este cea mai probabil valoare a semnalului. Apoi stocheaz diferena 螽tre semnalul real 槐 valoarea prezis. Dac predictorul este foarte bun, diferena va fi adesea minuscul. Predictorii 螽槐槐 sunt adesea adaptivi, 螽v裻螽d o serie de coeficieni de predicie 螽 timp ce fac prezicerea (adic 螽va din propriile erori). Acela槐 predictor este folosit at褾 la surs c褾 槐 la destinaie.

Compresie cu pierderi

Compresia f綖 pierderi poate cel mult obine reduceri de 2-3 ori a cantit裻ii de informaie din semnal. De aceea cele mai folosite la ora actual pe scar sunt compresiile cu pierderi (lossy). Cele mai eficace scheme de compresie cu pierderi se bazeaz pe sensibilitatea urechii umane pentru a deduce ce p綖i din semnal pot fi aruncate, 槐 de aceea se numesc compresii perceptuale.

De pild, dac auzim un sunet foarte puternic, alte sunete slabe din imediata vecin綟ate temporal sunt acoperite (c褾eva milisecunde). Dac le elimin緆 pe acestea din semnal putem transporta mai puin informaie. Sunetele puternice acoper vecinii lor apropiai at褾 螽 timp c褾 槐 螽 frecven; asta 螽seamn c un sunet puternic va 螸piedica percepia altor sunete de frecvene apropiate sau care se aud 螽 imediata vecin綟ate.

Pentru a descoperi p綖ile nesemnificative, codec-urile perceptuale adesea fac o analiz spectral a sunetului, extr緁螽d frecvenele componente. Apoi calculeaz c褾 energie sonor este 螽 fiecare frecven, 槐 cele care sunt sub pragurile audibile, sau care sunt acoperite de alte frecvene care se aud mai tare, sunt eliminate din semnal.

Alte trucuri de演epte sunt folosite pentru a reduce informaia c螽d 螽registr緆 canale stereo, sau chiar sound surround (cinci canale): de exemplu se 螽registreaz doar un canal 槐 diferena de la acesta la cel緄alt, care tinde s fie mic, 槐 se folosesc canale cu band de frecven redus pentru ba槐 (subwoofers).

Printre cele mai importante formate de compresie cu pierderi sunt:

Dolby Digital
numit 槐 AC-3, care este folosit 螽 televiziunea de 螽alt rezoluie (HDTV), DVD, discuri laser, televiziune digital 槐 螽 unele cinematografe pentru sunetul filmelor.

MPEG audio
este o familie mare de standarde, care cuprinde mai multe variante MPEG1, MPEG2, MPEG4, MPEG7; MPEG1 槐 doi la r螽dul lor au sub-nivele 1, 2, 3 槐 AAC. MP3 este la ora actual formatul preferat pentru schimb de muzic pe Internet, datorit compresiei care poate ajunge p螽 la 12/1; este o prescurtare de la MPEG 2 level 3.

Liquid Audio
este un format sofisticat pentru a reprezenta muzica, bazat at褾 pe Dolby Digital c褾 槐 pe MPEG AAC. Permite integrarea unor tipuri de date felurite 螽 fluxul muzical (imagini, text, partitura, pre, versuri, etc.).

Apple quicktime
e un format dezvoltat de Apple, care permite codificarea at褾 a muzicii c褾 槐 a informaiei video.

DVD Audio
este 螽c 螽 curs de dezvoltare; ar fi trebuit s apar deja, dar fabricanii 螽cearc s dezvolte metode eficiente 螸potriva copierii.

Formate flux (streaming)

E o diferen foarte mare 螽tre a c螽ta muzic de pe un disc aflat 螽 unitatea calculatorului propriu 槐 a transfera muzica de la distan prin reea: discul local poate garanta un flux susinut de informaii, f綖 erori 槐 pierderi. Internet-ul este 螽s impredictibil, 槐 nu orice tip de format este potrivit pentru transmisiune.

Dac mai dorim 槐 s reproducem informaia 螽 timp ce este primit avem de-a face cu un format de tip flux (streaming). Formatele flux trebuie s previn erorile care pot ap綖ea. Dou tehnologii sunt folosite pentru transmisiune pe o reea nefiabil:

Real Audio este probabil cel mai r綼p螽dit format de tip flux 螽 Internet, dar Microsoft 螸pinge tare propriul format secret, Windows Media Audio.

Formate simbolice

Toate formatele pe care le-am trecut 螽 revist p螽 acum sunt destinate pentru a ``螽registra'' o interpretare. Alte formate, cele simbolice, se mulumesc s descrie forma echivalent a partiturii muzicale. Acestea sunt deci mult mai compacte, pentru c reprezint doar notele, duratele lor 槐 informaii despre instrumentaie.

Cel mai r綼p螽dit standard de reprezentare simbolic este MIDI, Musical Instruments Digital Interface. Acesta este folosit practic de toate instrumentele electronice pentru codificarea informaiei.

O metod hibrid este de a reprezenta notele, ca 螽tr-o reprezentare simbolic, dar de a le obine prin e榮ntionare. De exemplu, c螽d 螽registrai o melodie la o org electronic, ea este 螽registrat 螽 acest fel, m綼ur螽d la fiecare 2 milisecunde care clape sunt ap綼ate. MIDI poate conine multe alte informaii: mai multe canale separate, informaii despre ritm, intensitate 槐 informaii simbolice despre titlul piesei, autor, etc.

Sistemul pe care 螿 vom prezenta 螽 continuare folose演e ca mod de reprezentare a muzicii aceast din urm metod. Dac melodia conine o singur voce (槐 nu are acompaniament), ea poate fi reprezentat printr-o funcie, ca 螽 figura 2. Graficul acestei funcii arat ca o colecie de segmente orizontale, numite ``funcii treapt''.

Figura 2: Reprezentarea muzicii sub form de funcii-treapt reprezint la fiecare moment de timp nota muzical c螽tat 螽 acel moment. Pauzele sunt indicate prin absena oric綖ei note. Timpul este e榮ntionat cu granularitate mic (螽 jur de 2 milisecunde).
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{treapta.eps}}\end{figure}

C綦tare multimedia: o problem nerezolvat

C綦tarea de melodii se poate 螸p綖i 螽 c褾eva categorii. Prima, 槐 cea mai popular, este de departe c綦tarea de c螽tece 螽 format MP3, sau alte formate de bun calitate, care sunt destinate ascult綖ii. Acum c褾eva luni cererile la motoarele de c綦tare pentru fi槐ere MP3 au trecut pe locul 螽t蟊 ca frecven, dep蒪ind liderul anterior, pornografia. A doua categorie este c綦tarea de versuri, iar a treia este c綦tarea de partituri. Obiectele c綦tate sunt adesea ilegal prezente pe Internet, cei care le ofer 螽c緄c螽d legea copyright-ului. Sunt ilegale at褾 publicarea c螽tecelor, versurilor, sau partiturilor, c褾 槐 obinerea lor de pe Internet, f綖 螽cuviinarea posesorului copyright-ului.

Exist 螽s 槐 un alt fel de c綦tare, care poate fi perfect legal: identificarea c螽tecului. 姷 acest tip de c綦tare rezultatul este numele c螽tecului, eventual autorul, albumul, 槐 poate o leg綟ur spre un magazin care ofer piesa spre v螽zare. De c褾e ori vi s-a 螽t螸plat s nu v putei scoate din minte o melodie? Uneori v amintii un vers sau dou, caz 螽 care Internetul v poate ajuta s-l identificai. Alteori, tot ce v mai amintii este melodia, caz 螽 care singura speran st 螽 prieteni: poate dac 螽cercai s le c螽tai un fragment (槐 dac vocea v permite) 槐 dac prietenii recunosc melodia, atunci vei afla numele c螽tecului.

Aceast ultim metoda de c綦tare poart numele de c綦tare dup coninut; aplicaiile ei sunt nenum綖ate. Prin analogie, c綦tarea dup coninut 螽 domeniul imaginilor1 g綼e演e imagini similare pornind de la o imagine-exemplu. Tehnologia c綦t綖ii dup coninut este 螽c foarte primitiv pentru tipuri de date multimedia. S 螽cerc緆 s vedem care sunt dificult裻ile 螽 domeniul muzical.

Probleme 螽 c綦tarea dup coninut

Vrem deci ca un utilizator s poat c螽ta o melodie (螽trebarea), 槐 un sistem electronic s o identifice 螽 mod automat 螽tr-o baz de date. Pentru aceasta trebuie s fim capabili s compar緆 dou melodii (sau o melodie cu un fragment -- 螽trebarea), pentru a putea spune c螽d dou melodii sunt asem緋綟oare 槐 c螽d sunt diferite. Avem de rezolvat 螽s mai multe probleme dificile:

Una din problemele cele mai mari este chiar sursa. Nu toi oamenii au ureche muzical bun 槐 numai o parte dintre ace演ia pot c螽ta bine. Un sistem care cere o reproducere perfect a fragmentului este util doar pentru o minoritate restr螽s. De aceea c綦tarea trebuie sa fie tolerant la erori 螽 ``螽trebare'': note gre槐te, note lips, note 螽 plus. De asemenea este foarte probabil c fragmentul va fi c螽tat mai rapid sau mai lent dec褾 originalul, 槐 螽 alt tonalitate.

O a doua problem este extragerea notelor (pitch tracking) din 螽trebare. 姷 urma 螽registr綖ii nu obinem un fi槐er cu coninut simbolic (ex. MIDI), ci o 螽registrare (ex. wav). C綦tarea necesit identificarea notelor din acest fi槐er. Acest proces introduce erori suplimentare: unele note vor ie槐 fragmentate, c褾eodat note identice vor fi concatenate; vocea uman adesea trece 螽tre note consecutive 螽 mod continuu (glissando), iar sistemul ar putea decide c trecerea de la ``sol'' la ``la'' s-a f綷ut 螽 alt moment dec褾 inteniona utilizatorul, note fictive pot ap綖ea, de obicei armonicele notei c螽tate, pentru c am v罳ut c sunetele emise nu sunt pure. Extragerea notelor este una din componentele 螽 care s-au 螽registrat progrese substaniale 螽 ultima vreme, 槐 pe care o putem considera rezolvat satisf綷綟or din punct de vedere ingineresc. Programe precum Digital Ear http://digitalear.iwarp.com 槐 Autoscore http://www.wildcat.com/Site/Homepage.htm au ajuns la performane uimitoare.

O a treia problem este cea a bazei de date. C綦tarea necesit o baz de date cu toate c螽tecele ce se doresc recunoscute, stocate 螽 format simbolic. La ora actual nu exist nici o astfel de colecie care s fie suficient de comprehensiv pentru a fi cu adev綖at util 螽 aplicaii practice.

Soluii

S ne reamintim c 螽cerc緆 s definim o noiune de distan 螽tre dou fragmente muzicale, care m綼oar similaritatea dintre ele.

S 螽cerc緆 s vedem ce soluii exist pentru toate aceste probleme. Prima problem const 螽 inacurateea reproducerii fragmentului de c綟re utilizatorii sistemului. De aceea, sistemul trebuie sa foloseasc o m綼ur a similarit裻ii care s aib urm綟oarele propriet裻i:

Date dou fragmente de melodii, putem m綼ura similaritatea dintre ele prin compararea graficelor lor. Problema similarit裻ii a dou fragmente de melodii se transform astfel 螽tr-una de comparare a dou funcii treapt.

Figura 3: ``Distana'' dintre dou melodii reprezentate ca funcii treapt se poate m綼ura prin aria dintre ele.
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{arie.eps}}\end{figure}

S presupunem c cele dou fragmente au aceea槐 lungime. Graficele corespunz綟oare vor avea 槐 ele aceea槐 lungime. Dac le vom vizualiza suprapuse, o bun m綼ur a distanei dintre ele este aria dintre cele dou grafice, ca 螽 figura 3.

C螽d calcul緆 distana dintre grafice, trebuie s translat緆 unul din grafice pe vertical, astfel 螽c褾 sa minimiz緆 aria dintre ele. 姷 felul acesta distana este invariant la schimbarea gamei 槐, 螽 acela槐 timp, tolerant la note false.

Pentru a obine invarian la tempo, 螽cerc緆 s dilat緆 unul din fragmente cu diver槐 factori, pentru a minimiza aria dintre cele doua funcii.

Iat o schi a algoritmului pe care Cristi l-a implementat, care calculeaz distana dintre un fragment c螽tat 槐 o melodie monofonic (care are o singur linie melodic, f綖 acompaniament):


pentru diver槐 factori de scalare 螽tre 0.5 槐 2 

scaleaz fragmentul cu factorul curent
translateaz graficul lui de-a lungul graficului melodiei (peorizontal)
pentru fiecare poziie intermediar
translateaz fragmentul pe vertical pentru a minimiza aria dintre cele dou
raporteaz cea mai mic arie g綼it 螽 acest proces

Funcionarea acestui algoritm este ilustrat 螽 figura 4.

Figura 4: Funcionarea algoritmului de calcul a distanei: (1) date fiind o melodie (linia neagr) 槐 o 螽trebare (linia ro槐e) exprimate prin funcii treapt, trebuie s g綼im ``potriveala'' maxim dintre ele. 姷 prima faz (care nu e ilustrat) 螽trebarea este translatat 螽 timp pentru a g綼i locul unde apare 螽 melodie (nu neap綖at la 螽ceput), apoi (2) 螽trebarea este scalat 螽 timp, pentru a potrivi tempo-ul cu cel al melodiei, 槐 螽 fine (3) este scalat 螽 frecven pentru a fi la aceea槐 ``螽緄ime'' cu piesa. Toi cei trei pa槐 sunt f綷ui p螽 c螽d distana (aria dintre cele dou curbe) este minimizat; calculul distanei este deci un proces de c綦tare.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{algo.eps}}\end{figure}

Alte probleme de inginerie

Am rezolvat astfel problema teoretic cea mai spinoas, de a defini o distan. Aceasta se preteaz la o implementare relativ simpl, dar mai avem de rezolvat c褾eva alte probleme nepl綷ute 螽ainte de a face acest sistem cu adev綖at practic.

Prima dintre ele este faptul c melodiile nu sunt, 螽 general, monofonice (螽 vreme ce reproducerile oamenilor sunt). De aceea, 螽ainte de a putea aplica algoritmul nostru, trebuie s transform緆 fiecare c螽tec 螽tr-o melodie monofonic. Acest lucru este f綷ut f綷螽d o analiz spectral a muzicii 槐 elimin螽d toate notele 螽 afar de cea cu energia maxim2.

A doua problem const 螽 extragerea notelor din fi槐ere de tip wav (conversia de la o 螽registrare la un format simbolic). 姷 mod cert, calitatea programelor ce convertesc wav la MIDI a crescut foarte mult, pentru fi槐ere monofonice. Distana pe care o folosim 螽s este tolerant 槐 erori introduse de aceast conversie: fragmentare sau alipire de note, trecerea de la o not la alta la momente inoportune.

A treia problem const 螽 lipsa de c螽tece 螽 format simbolic. Un mod de a rezolva aceast problem este de culege fi槐ere MIDI de pe Web. Pe web exist cel puin 100 000 de astfel fi槐ere, suficient pentru a construi o baz de date respectabil folosind un ``p緅anjen'' (web spider, crawler), asem緋綟or celor folosite de motoarele de c綦tare. Se estimeaz c 99.99% dintre cererile de c綦tare de c螽tece pe Internet se refer la mai puin de 10000 de melodii diferite.

De槐 folosirea MIDI este atractiv datorit num綖ului mare de fi槐ere disponibile, exist 槐 dezavantaje: marea majoritate a acestor fi槐ere sunt create de c綟re amatori, ceea ce duce la o calitate 螽doielnic a reproducerii originalului. A榮 cum am menionat mai sus, prezena unor multiple canale 槐 a mai multor sunete simultane 螽 fiecare canal este un impediment 螽 folosirea acestor fi槐ere; cu toate acestea, din punct de vedere practic fi槐erele MIDI reprezint un compromis excelent, fiind 螽tr-un format u榣r de prelucrat, 槐 螽 num綖 foarte mare.

Figura 5: Sistemul humwistle, http://www.humwistle.com 螽 螽tregime. Componentele indicate cu albastru sunt 螽 curs de dezvoltare. O colecie mare de fi槐ere MIDI este extras de pe web. Informaiile textuale inserate 螽 corpul fi槐erelor MIDI sunt extrase 槐 folosite pentru etichetarea 槐 indexarea fi槐erelor. Componenta aurie este cea descris 螽 acest articol 槐 este partea cea mai inovatoare a sistemului, care permite c綦tarea dup melodii c螽tate.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{sistem.eps}}\end{figure}

Acestea fiind zise s arunc緆 o privire asupra sistemului 螽 curs de dezvoltare 螽 cadrul departamentului de calculatoare al universit裻ii Rutgers, descris 螽 figura 5. Sistemul este format din trei componente majore. Prima colecteaz fi槐ere MIDI de pe web 螽tr-un proces continuu, le clasific 槐 le adaug la baza de date. A doua component preia cererile de c綦tare pe baz de text (autor, c螽tec, album, versuri) 槐 execut o c綦tare textual 螽 baza de date, folosind tehnici standard de biblioteci digitale 槐 informaiile simbolice prezente 螽 fi槐erele MIDI. A treia component preia cererile de c綦tare pe baz de fragmente c螽tate, le transform 螽 fi槐ere MIDI folosind o subcomponent de extragere a notelor, apoi caut fragmentul respectiv 螽 c螽tecele din baza de date folosind algoritmul de mai sus.

Experimente

Rezultatele obinute cu acest sistem sunt 螽curajatoare. Am efectuat experimente pe un set de 10 000 de c螽tece, din totalul de 100  000 existente 螽 baza de date. Mai muli subieci au c螽tat 30 de fragmente muzicale diferite, fiecare 螽tre 4 槐 22 de secunde 螽 lungime. Sistemul a returnat pentru fiecare fragment cele mai potrivite 20 de melodii.

Sistemul a identificat cel mai adesea cu succes diferite versiuni ale c螽tecului real, din care f綷ea parte fragmentul (chiar dac c螽tecul era substanial diferit, cu ritm sincopat sau cu variaiuni). C螽tecul original, din care f綷ea parte fragmentul, a fost aproape mereu prezent 螽tre primele 20 de posibilit裻i, cel mai adesea pe primul loc.

Un al doilea set de experimente a avut ca obiectiv evaluarea performanei subiecilor umani pentru acela槐 test: c褾 de buni sunt oamenii la recunoa演erea unui c螽tec dup un fragment c螽tat de cineva. Am selectat 榮se fragmente dintre cele 30. Subiecii umani au pornit recunoa演erea de la fragmentul transpus 螽 form simbolic MIDI, deci dup pitch tracker; 螽 felul acesta au primit acelea槐 erori introduse de pitch tracker pe care le-a primit 槐 sistemul automat. Subiecii nu au avut constr螽geri de timp 槐 li s-a permis s asculte fragmentele de ori c褾e ori au dorit. Am considerat c un subiect a recunoscut c螽tecul fie dac a putut spune numele, fie dac a putut s fredoneze c褾eva note 螽 continuarea fragmentului. Nici unul din subieci nu a fost muzician profesionist. Toate fragmentele muzicale erau cunoscute subiecilor.

姷 medie subiecii au recunoscut 1,5 c螽tece din 6 posibile. Num綖ul maxim de c螽tece recunoscute a fost 4, iar num綖ul minim zero. 姷 schimb, sistemul a reu槐t sa identifice 4 din 6. Concluzia acestui experiment este c recunoa演erea c螽tecelor este o problem grea chiar 槐 pentru oameni, 槐 este plauzibil ca 螽 viitor calculatoarele s devin mai bune dec褾 omul 螽 acest domeniu.

Calculele necesare pentru identificarea unui c螽tec sunt foarte costisitoare: implementarea curent necesit aproximativ 榮pte ore 槐 jum綟ate pentru a r綼punde la o 螽trebare, 槐 aceasta folosind baza de date redus, de 10000 de melodii. De aceea eforturile de cercetare se concentreaz 螽 g綼irea unui algoritm mai rapid. De asemenea, trecerea de la 10000 de c螽tece la un milion de c螽tece este deosebit de grea: indiferent de viteza algoritmului de calcul al distanei, el tot va trebui sa compare fragmentul cu un milion de posibili candidai. De aceea eforturile noastre se 螽dreapt spre g綼irea unor metode de indexare care s permit eliminarea din start a majorit裻ii c螽tecelor, ca fiind foarte diferite. Algoritmi folosind tehnologii de inteligen artificial vor fi folosii pentru a grupa (clustering) c螽tecele 螽 categorii 螽rudite, care pot fi eliminate dintr-o dat.

Alte eforturi de cercetare 螽 biblioteci muzicale

Proiectul humwistle nu este singurul care studiaz problema cre綖ii 槐 acces綖ii unei biblioteci digitale. Pare 螽s s fie cel care a rezolvat cu cel mai mare succes problema c綦t綖ii, datorit funciei distan folosite pentru m綼ur綟ori. 姷 aceast seciune enumer緆 pe scurt alte c褾eva proiecte, care sunt din cuno演inele autorilor cele mai avansate 螽 domeniu.

Cercetarea universitar 螽 domeniul similarit裻ii melodiilor a 螽ceput prin anii '70, dar sisteme practice nu au ap綖ut p螽 螽 1995. Cauzele acestei stagn綖i s螽t multiple; Internet-ul a explodat de cur螽d, deci cererea de c綦tare dup coninut are mult mai muli ``clieni''. Marile companii de discuri au 螽ceput s foloseasc Internet-ul de numai c鞜iva ani. De asemenea, fi槐erele MIDI au devenit cu adev綖at populare de cur螽d.

Asif Ghias 槐 echipa lui de la universitatea Cornell din SUA 螽 1995 au construit primul sistem experimental de recunoa演ere a unui c螽tec. Metoda folosit de ei const 螽 extragerea notelor din fragmentul c螽tat; apoi fragmentul este transcris ca o secven de simboluri U, D, sau S. O not este transformat 螽 U (up) dac este mai 螽alt dec褾 nota anterioar, S (same) dac este aceea槐 not sau D (down) dac este mai joas. Melodiile din baza de date sunt reprezentate 螽 aceea槐 manier. Fragmentul este c綦tat 螽 baza de date folosind un algoritm binecunoscut de comparare a unor 槐ruri de caractere, permi螽d mai puin de k diferene (algoritmul Baesa-Yates).

Sistemul a demonstrat viabilitatea ideii, dar l綼a de dorit din punct de vedere practic: baza de date coninea numai 183 de c螽tece, iar algoritmul necesita din ce 螽 ce mai multe note 螽 fragmentul c螽tat pe m綼ur ce baza de date cre演e,3 f綷螽du-l nepractic pentru 10000 de c螽tece.

De departe cele mai bune rezultate 螽 domeniu au fost obinute de McNab 槐 echipa sa, la universitatea Waikato din Noua Zeeland. Ei au construit un sistem care a testat mai multe funcii distan diferit. Baza lor de date, asamblat din partituri de c螽tece populare germane 槐 chineze演i, coninea 10000 de melodii. Metoda de comparare care a dat cele mai bune rezultate const 螽 exprimarea fiec綖ei note ca o pereche (interval, durat), unde intervalul este distana fa de nota precedent. C螽tecele din baza de date erau codificate 螽 acela槐 fel, iar distana folosit era ``distana de editare''. Distana de editare dintre dou 槐ruri de caractere, edit-distance, este num綖ul minim de operaii de inserare, 演ergere sau 螽locuire de caracter care trebuie aplicate primului 槐r pentru a-l obine pe al doilea.

Sistemul a demonstrat performane uimitoare: atunci c螽d fragmentul c螽tat era chiar 螽ceputul c螽tecului, 12 note erau de ajuns pentru a reduce num綖ul de melodii candidat la mai puin de 10. Din p綷ate publicaiile lor nu spun ce se 螽t螸pl atunci c螽d fragmentul de recunoscut poate fi oriunde 螽 c螽tec. Cercet綖i ulterioare sugereaz c, 螽 acest caz, num綖ul de note necesare pentru dezambiguare cre演e din nou foarte mult, f綷螽d sistemul nepractic.

Un alt pionier al c綦t綖ii pe baz de coninut este J. S. Downie, de la universitatea din Western Ontario, Canada. El a observat faptul c atunci c螽d baza de date cre演e este prea costisitor s compar緆 fragmentul c螽tat cu toate melodiile: num綖ul de calcule ar fi prea mare. De aceea el a 螽cercat s aplice tehnici clasice de indexare folosite 螽 bibliotecile digitale cu text 槐 de motoarele de c綦tare de pe World Wide Web. El a definit ``cuvintele'' ca fiind secvene de patru sau cinci note consecutive 槐 apoi a construit un index foarte asem緋綟or cu indexul de la sf褳槐tul unei c綖i tehnice: pentru fiecare cuv螽t, indexul indic locul lui de apariie, pagina 螽 cazul c綖ii, c螽tecul 螽 cazul nostru. Un fragment de recunoscut este segmentat 螽 note, apoi scris ca o succesiune de ``cuvinte''. Fiecare din aceste cuvinte apare 螽 mai multe c螽tece, iar, dintre acestea, c螽tecul care apare 螽 listele indicate de toate cuvintele este cel c綦tat.

Metoda funcioneaz foarte bine 槐 mai ales rapid, atunci c螽d fragmentele c綦tate sunt reproduceri fidele ale originalului. Din p綷ate, performana sistemului se degradeaz foarte mult atunci c螽d o not sau dou sunt gre槐te, ceea ce, din nou, face sistemul nepractic.

Toate aceste 螽cerc綖i de a construi o bibliotec digital muzical au avut un punct comun: modul lor de reprezentare a melodiilor era o secven de simboluri discrete, ca un 槐r de caractere. Un simbol este fie nota, fie diferena 螽 semitonuri fa de nota anterioar, fie o pereche de un de num綖 槐 o durat. Aceast reprezentare este problematic pentru construcia unei bune m綼uri de similaritate, deoarece o not fragmentat, sau mai multe note concatenate schimba dramatic reprezentarea unui fragment, de槐, 螽 esen, el difer puin de original. De aceea, noi am optat pentru reprezentarea prezentat mai sus, 螽 care o melodie nu mai este o 螽槐ruire de simboluri, ci mai degrab o variaie continu 螽 timp a 螽緄imii notei. Consider緆 c aceasta este cheia care a permis obinerea unor rezultate mai bune dec褾 oricare din cele raportate p螽 螽 prezent.

Evoluii viitoare

Sistemul humwistle este disponibil pe Internet. 姷 momentul de fa numai c綦tarea textual este accesibil on-line. C螽d performanele c綦t綖ii pe baz de coninut se vor 螸bun綟裻i suficient pentru o utilizare interactiv, ea va fi de asemenea disponibil pe web.

Aplicaiile comerciale ale sistemului sunt enorme: companiile de discuri ar putea crea astfel de baze de date 螽 care fiecare pies 螽 format wav sau PCM (de pe CD) este 螽soit de o descriere MIDI, eventual extras automat. Utilizatorul poate interoga baza de date, iar sistemul descris poate identifica melodia MIDI corespunz綟oare. Apoi utilizatorul poate cump綖a dup dorin 螽registr綖ile piesei, sau partitura, extras direct din MIDI.

Muzicienii ar putea folosi un astfel de sistem pentru a detecta plagiarismul 螽 cantit裻i enorme de c螽tece, c綦t螽d temele din propriile lor compoziii.

O aplicaie interesant acestei tehnologii este 螽 calculatoare mobile, unde spaiul ecran este foarte restr螽s. Posibilitatea de a selecta c螽tece spre ascultare prin c螽tarea unui fragment ar putea fi de nepreuit. Un player de MP3-uri conectat la reeaua de telefonie celular ar putea sa aduc c螽tece la cerere, pornind de la scurte fragmente c螽tate.

Imaginai-v conduc螽d un automobil peste zece ani, care va include un player de MP3 care are suficient memorie pentru a stoca toat colecia dumneavoastr de c螽tece. Cum ai putea face pentru a selecta o melodie sau un album spre ascultare, f綖 s trebuiasc s luai m螽a de pe volan pentru a scotoci 螽 cutia cu discuri? O soluie elegant ar fi s c螽tai un fragment din c螽tecul dorit. 姷 plus, aceast soluie nu necesit luarea m蟊nilor de pe volan.

Alte surse de informaie

Pe Internet exist o cantitate enorm de informaie despre formatele digitale audio, 槐 mai ales despre MP3, care e la mare vog. Folosii motorul dumneavoastr de c綦tare favorit.

Sistemul dezvoltat este disponibil on-line la http://www.humwhistle.com.

Cristian Fr滱cu 槐 Craig Nevill-Manning ``Distance metrics and indexing strategies for a digital library of popular music'', International Conference on Multimedia and Expo, July 30 -- August 2, 2000, New York City, USA, http://sequence.rutgers.edu/~francu/Papers/icme00.pdf.

Asociaia internaional pentru muzic pe calculator are liste foarte impresionante de resurse 槐 informaii plec螽d de la http://www.computermusic.org/.

Fraunhofer Gesellschaft http://www.iis.fhg.de/amm/techinf este institutul German care a creat MPEG 2 layer 3, sau MP3.



Note

... imaginilor1
Vedei 槐 articolul despre Computer Vision PC Report din iulie.
... a2
Aceasta nu este neap綖at cea mai bun metod pentru a detecta ``melodia principal'', dar este foarte simpl 槐 funcioneaz bine 螽 practic.
... ste,3
Asta pentru c dac transform緆 c螽tecele doar 螽 U, D, S, ele tind s semene mult 螽tre ele; pentru a le diferenia e nevoie de din ce 螽 ce mai multe note.