De unde ºtiu melodia asta?

Cristian Frâncu -- 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ºterea muzicii
Cunoºtinþe necesare:
cunoºtinþe elementare despre muzicã ºi baze de date
Cuvinte cheie:
semnal, eºantionare, cuantizare, cãutare, indexare, bibliotecã digitalã


Cuprins




Evoluþia calculatoarelor spre multimedia

John von Neumann este considerat creatorul arhitecturii calculatoarelor aºa cum o cunoaºtem astãzi. Neumann a ajuns la calculatoare din dorinþa de a rezolva probleme de fizica fluidelor. Multe ecuaþii diferenþiale nu admit soluþii 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 ºi-a suflecat mînecile ºi s-a apucat sã le amelioreze, pentru a putea gãsi soluþiile care-l interesau. El a propus o mulþime de concepte care ºi astãzi se regãsesc în arhitectura calculatoarelor, cum ar fi separarea funcþionalitãþii fizice ºi logice a circuitelor (adicã construcþia de porþi logice din tuburi - mai tîrziu tranzistoare, ºi acum circuite integrate, care apoi pot fi manipulate independent de modul în care sunt construite, ca niºte obiecte matematice ideale), ºi diviziunea calculatorului în unitate de procesare, unitãþi de intrare-ieºire ºi memorie în care sunt stocate atît programele cît ºi datele prelucrate.

Dar, deºi a anticipat ºi dat naºtere multor idei seminale, povestea spune cã von Neumann a fost foarte supãrat pe un colaborator de-al sãu, care încerca sã scrie un asamblor. Asamblorul e un program care uºureazã munca programatorului, permiþîndu-i sã scrie programele într-un limbaj textual în loc de a folosi ºiruri de zero ºi unu, în cod-maºinã. Von Neumann spunea cã timpul de calcul este irosit fãcînd o activitate pe care o poate face foarte bine omul.

Astãzi afirmaþia lui von Neumann ni se pare absolut anacronicã, dar acest lucru se întîmplã pentru cã balanþa între costul puterii de calcul ºi cel al muncii omeneºti s-a schimbat absolut dramatic; la ora de astãzi orice investiþie care mutã efortul omenesc pe seama unui calculator este productivã.

De-a lungul timpului tipurile de prelucrare fãcute de calculatoare s-au diversificat enorm; creºterea capacitãþii de stocare ºi prelucrare ne-a permis sã trecem încetul cu încetul de la procesarea unor cantitãþi infime de date la folosirea unor baze de date enorme, la folosirea interfeþelor grafice sofisticate, la comunicaþii care înglobeazã tot mai mult imagine, sunet, film, culoare.

Dar dacã astãzi lumea strîmbã din nas la ideea folosirii unui browser în mod text (deºi numai în urmã cu 10 ani gopher-ul era cea mai avansatã tehnologie), evoluþia în complexitatea informaþiei procesatã în mod curent de cãtre calculator este departe de a fi încheiatã. Chiar dacã astãzi o mulþime de site-uri de web au graficã spectaculoasã, ºi jocurile în spaþii tridimensionale sunt banalitãþi, o mulþime de alte operaþii elementare sunt încã foarte greu de fãcut de cãtre calculator. Chiar stocarea ºi transmisiunea informaþiei video este extrem de primitivã, cele mai evoluate sisteme putînd transmite imagini de dimensiunea unui timbru (vorbim de produse disponibile comercial, ºi nu de experimente în laborator).

În ceea ce priveºte imaginile ºi muzica, situaþia este ceva mai bunã: ºtim sã le stocãm, livrãm, reproducem ºi înregistrãm. Dacã este însã vorba de procesãri mai complicate, suntem încã foarte neajutoraþi.

În textul de faþã vom investiga felul în care putem manipula muzica digitalã.

Acest articol se bazeazã pe cercetarea unuia dintre autori, Cristian Frâncu; rezultatele sale au fost prezentate de curînd cu mult succes la conferinþa internaþionalã despre multimedia ICME 2000. Aparent sistemul construit de el pentru recunoaºterea melodiilor dupã exemple este cel mai performant în existenþã la ora actualã. Algoritmii dezvoltaþi de Cristi împreunã cu grupul lui de cercetare vor forma baza unei biblioteci digitale de muzicã, în curs de dezvoltare.

Despre sunet

Dar înainte de a putea plonja în detaliile modului în care muzica poate fi indexatã ºi cãutatã, va trebui sã discutãm puþin despre cum se înregistreazã muzica în mod digital.

Sunetul se propaga prin aer sub forma unei unde; aceastã undã poate fi caracterizatã prin amplitudinea ei în fiecare moment. Un sunet ``pur'', fundamental, are amplitudinea descrisã de o sinusoidã. Frecvenþa sinusoidei (inversul perioadei) se numeºte ``frecvenþa sunetului'', ºi se mãsoarã în hertzi, Hz.

Cînd mai multe surse emit sunete simultan, undele lor se suprapun (se adunã) ºi 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întatã la pian sunã altfel decît nota ``la'' cîntatã la vioarã, deºi ambele au aceeaºi frecvenþã (stabilitã la 440hz). În 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 însele ºi intrã în rezonanþã cu alte frecvenþe decît cele prezente în sunetul ambiant (genereazã ceea ce se numesc ``armonici auriculare''). Pe lîngã faptul cã genereazã sunete inexistente, urechea omeneascã este inegal de sensibilã la frecvenþe diferite; aparatul auditiv poate percepe sunete între 16hz ºi 24khz, fiind cel mai sensibil în jurul frecvenþei de 4khz (sensibil însemnînd cã poate auzi semnalele cu energia cea mai micã). De asemenea, sensibilitatea scade cu vîrsta.

Toate aceste slãbiciuni ale aparatului auditiv uman sunt exploatate de metodele de înregistrare digitalã. Toate aceste metode filtreazã sunetul în aºa fel încît sã înregistreze doar o bandã îngustã de frecvenþe.

Putem distinge douã clase mari de metode de stocare a muzicii sub formã digitalã: înregistrãrile ºi descrierile simbolice. Ne vom ocupa pe scurt de fiecare dintre ele.

Înregistrãri digitale

Înregistrãrile digitale sunt echivalente cu tehnicile de înregistrare analogicã patentate de Edison în urmã cu 127 de ani: capteazã un semnal din aer, îl prelucreazã, codificã ºi stocheazã. Spre deosebire de patefon, tehnicile digitale descriu semnalul prin secvenþe de cifre ºi nu prin procese fizice (de exemplu, patefonul descrie semnalul prin forma ºanþurilor de pe disc).

Eºantionare ºi cuantizare

Pentru a putea transforma o mãrime continuã într-o serie de numere trebuie sã facem douã operaþii distincte: sã o eºantionãm ºi sã o cuantizãm.

Figura 1: Semnalele înregistrate sunt funcþii continue de timp (a). Semnalul este întîi eºantionat, mãsurînd valoarea lui într-un numãr finit de puncte, de regulã echidistante (b). Apoi valorile eºantioanelor sunt codificate cu un numãr finit de biþi în procesul de cuantizare (c). În aceastã figurã cuantizarea s-a fãcut cu 3 biþi, care pot distinge opt valori diferite ale amplitudinii (unele pozitive, unele negative.)
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{esantionare.eps}}\end{figure}

Eºantionarea mãsoarã semnalul audio din timp în timp, de obicei cu o perioadã fixã. Teorema lui Nyquist aratã cã dacã vrem sã înregistrãm un semnal ale cãrui frecvenþe componente sunt sub X hz, e suficient sã eºantionãm semnalul cu frecvenþa 2X hz. Compact-disc-urile de pildã eºantioneazã sunetul la 44.1 khz, ceea ce este dublul lui 22.05khz, care este o limitã mult înafara auzului celor mai multe persoane (dacã nu a tuturor). Teorema lui Nyquist aratã cã din aceste eºantioane, în numãr finit, se poate reconstitui complet, fãrã nici un fel de pierderi, forma semnalului original, continuu! Figura 1 ilustreazã aceste procedee.

Astfel am rezolvat problema transformãrii unui semnal continuu într-o secvenþã finitã de valori discrete. Dar fiecare din aceste valori poate fi exprimatã printr-un numãr real, care ar putea avea nevoie de o precizie infinitã pentru a fi exprimat. Sistemele de înregistrare digitalã aproximeazã valorile posibile ale amplitudinii printr-un numãr finit; acesta este procesul de cuantizare. Intervalul între amplitudinea zero ºi o amplitudine maximã posibilã este împãrþit în segmente (de obicei egale). Numãrul de segmente este apoi codificat printr-un numãr de biþi. De exemplu, compact disc-urile folosesc 16 biþi de precizie pentru a descrie o valoare a amplitudinii; asta înseamnã cã pot distinge 216 = 65536 de nivele diferite de amplitudine, suficient de fine pentru a pãcãli urechea umanã.

PCM ºi CD-urile

Dacã înregistrãm valoarea fiecãrui eºantion în ordinea în care apar am înregistrat efectiv sunetul. Acest gen de descriere a unui semnal se numeºte ``modulare cu pulsuri'', pulse code modulation, prescurtat PCM.

Compact-disc-urile stocheazã informaþia necomprimatã; dimpotrivã, pentru a preveni erorile care pot apãrea din cauza zgîrieturilor, expandeazã informaþia ºi o codificã în mod redundant: dacã unii biþi dispar, ei pot fi reconstituiþim în mãsura în care stricãciunile nu sunt prea mari.

Un CD înregistrat stereo are deci douã canale care conþin 44100 de valori de 16 biþi pentru fiecare secundã de muzicã; asta înseamnã o ratã de transfer a informaþiei de 2 * 44100 * 16 = 1.411Mbps (megabiþi pe secundã). Aceasta este viteza cu care informaþia iese din CD-player-ul calculatorului dumneavoastrã; în interior rata este chiar mai mare, din cauza codificãrii redundante. Un compact disc poate stoca aproximativ 70 de minute de muzicã, avînd deci o capacitate de 70 * 60 * 1.411 / 8 = 740 MB (megaocteþi). Pe un hard-disc de 20 de gigaocteþi putem deci stoca aproximativ 25 de CD-uri.

Tipul standard de fiºier de sunet în Microsoft Windows este cel cu extensia .wav, care codificã de obicei informaþia tot în formã PCM. De asemenea, PCM este metoda folositã pentru codificarea vocii în telefonia digitalã ºi ISDN.

Compresie digitalã

Prin eºantionare ºi cuantizare putem stoca informaþiile din orice semnal continuu (în anumite limite de frecvenþã). Adesea însã informaþia din acest semnal este foarte amplã ºi redundantã. Depinzînd de mediul de stocare ºi transmisie putem dori sã reducem informaþia sau nu.

Mai multe scheme din ce în ce mai sofisticate au fost dezvoltate pentru a comprima muzica. Putem distinge douã mari categorii de metode de compresie: compresie cu pierderi ºi compresie fãrã pierderi. Compresia fãrã pierderi poate oricînd reconstitui identic semnalul original; cea cu pierderi decide sã arunce la gunoi informaþiile ``neimportante''.

Compresie fãrã pierderi

Un program care comprimã un semnal audio se numeºte codec, de la codor-decodor. Fiecare firmã mare din telecomunicaþii, industria electronicã a echipamentelor audio ºi din software a dezvoltat propriile codec-uri; cele mai multe dintre acestea sunt secrete bine pãzite.

În general, nu putem comprima decît puþin muzica dacã insistãm sã nu avem pierderi (lossless), dar pentru aplicaþii specifice compresia fãrã pierderi este acceptabilã ca performanþã (mãsuratã prin resurse de calcul consumate pentru a obþine o anumitã calitate a sunetului). De exemplu, vocea umanã are un spectru relativ îngust, ºi variaþiile de intensitate ºi frecvenþã nu sunt foarte mari în timp scurt.

Metode eficace de compresie sunt compresia diferenþialã (DPCM) ºi compresia adaptivã diferenþialã (ADPCM). Compresia diferenþialã, în loc de a codifica fiecare eºantion separat, codificã diferenþa dintre douã eºantioane succesive; dacã semnalul nu poate varia foarte repede, aceastã diferenþã va fi întotdeauna micã, ºi deci va putea fi transmisã cu mai puþini biþi (folosind de exemplu un cod Huffmann).

Compresia adaptivã merge chiar mai departe: foloseºte un model predictiv al semnalului, ºi calculeazã în fiecare clipã care este cea mai probabilã valoare a semnalului. Apoi stocheazã diferenþa între semnalul real ºi valoarea prezisã. Dacã predictorul este foarte bun, diferenþa va fi adesea minusculã. Predictorii înºiºi sunt adesea adaptivi, învãþînd o serie de coeficienþi de predicþie în timp ce fac prezicerea (adicã învaþã din propriile erori). Acelaºi predictor este folosit atît la sursã cît ºi la destinaþie.

Compresie cu pierderi

Compresia fãrã pierderi poate cel mult obþine reduceri de 2-3 ori a cantitãþii de informaþie 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ãrþi din semnal pot fi aruncate, ºi de aceea se numesc compresii perceptuale.

De pildã, dacã auzim un sunet foarte puternic, alte sunete slabe din imediata vecinãtate temporalã sunt acoperite (cîteva milisecunde). Dacã le eliminãm pe acestea din semnal putem transporta mai puþinã informaþie. Sunetele puternice acoperã vecinii lor apropiaþi atît în timp cît ºi în frecvenþã; asta înseamnã cã un sunet puternic va împiedica percepþia altor sunete de frecvenþe apropiate sau care se aud în imediata vecinãtate.

Pentru a descoperi pãrþile nesemnificative, codec-urile perceptuale adesea fac o analizã spectralã a sunetului, extrãgînd frecvenþele componente. Apoi calculeazã cîtã energie sonorã este în fiecare frecvenþã, ºi cele care sunt sub pragurile audibile, sau care sunt acoperite de alte frecvenþe care se aud mai tare, sunt eliminate din semnal.

Alte trucuri deºtepte sunt folosite pentru a reduce informaþia cînd înregistrãm canale stereo, sau chiar sound surround (cinci canale): de exemplu se înregistreazã doar un canal ºi diferenþa de la acesta la celãlalt, care tinde sã fie micã, ºi se folosesc canale cu bandã de frecvenþã redusã pentru baºi (subwoofers).

Printre cele mai importante formate de compresie cu pierderi sunt:

Dolby Digital
numit ºi AC-3, care este folosit în televiziunea de înaltã rezoluþie (HDTV), DVD, discuri laser, televiziune digitalã ºi în unele cinematografe pentru sunetul filmelor.

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

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

Apple quicktime
e un format dezvoltat de Apple, care permite codificarea atît a muzicii cît ºi a informaþiei video.

DVD Audio
este încã în curs de dezvoltare; ar fi trebuit sã aparã deja, dar fabricanþii încearcã sã dezvolte metode eficiente împotriva copierii.

Formate flux (streaming)

E o diferenþã foarte mare între a cînta muzicã de pe un disc aflat în unitatea calculatorului propriu ºi a transfera muzica de la distanþã prin reþea: discul local poate garanta un flux susþinut de informaþii, fãrã erori ºi pierderi. Internet-ul este însã impredictibil, ºi nu orice tip de format este potrivit pentru transmisiune.

Dacã mai dorim ºi sã reproducem informaþia în timp ce este primitã avem de-a face cu un format de tip flux (streaming). Formatele flux trebuie sã previnã erorile care pot apãrea. Douã tehnologii sunt folosite pentru transmisiune pe o reþea nefiabilã:

Real Audio este probabil cel mai rãspîndit format de tip flux în Internet, dar Microsoft împinge tare propriul format secret, Windows Media Audio.

Formate simbolice

Toate formatele pe care le-am trecut în revistã pînã acum sunt destinate pentru a ``înregistra'' o interpretare. Alte formate, cele simbolice, se mulþumesc sã descrie forma echivalentã a partiturii muzicale. Acestea sunt deci mult mai compacte, pentru cã reprezintã doar notele, duratele lor ºi informaþii despre instrumentaþie.

Cel mai rãspîndit standard de reprezentare simbolicã este MIDI, Musical Instruments Digital Interface. Acesta este folosit practic de toate instrumentele electronice pentru codificarea informaþiei.

O metodã hibridã este de a reprezenta notele, ca într-o reprezentare simbolicã, dar de a le obþine prin eºantionare. De exemplu, cînd înregistraþi o melodie la o orgã electronicã, ea este înregistratã în acest fel, mãsurînd la fiecare 2 milisecunde care clape sunt apãsate. MIDI poate conþine multe alte informaþii: mai multe canale separate, informaþii despre ritm, intensitate ºi informaþii simbolice despre titlul piesei, autor, etc.

Sistemul pe care îl vom prezenta în continuare foloseºte ca mod de reprezentare a muzicii aceastã din urmã metodã. Dacã melodia conþine o singurã voce (ºi nu are acompaniament), ea poate fi reprezentatã printr-o funcþie, ca în figura 2. Graficul acestei funcþii aratã ca o colecþie de segmente orizontale, numite ``funcþii treaptã''.

Figura 2: Reprezentarea muzicii sub formã de funcþii-treaptã reprezintã la fiecare moment de timp nota muzicalã cîntatã în acel moment. Pauzele sunt indicate prin absenþa oricãrei note. Timpul este eºantionat cu granularitate micã (în jur de 2 milisecunde).
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{treapta.eps}}\end{figure}

Cãutare multimedia: o problemã nerezolvatã

Cãutarea de melodii se poate împãrþi în cîteva categorii. Prima, ºi cea mai popularã, este de departe cãutarea de cîntece în format MP3, sau alte formate de bunã calitate, care sunt destinate ascultãrii. Acum cîteva luni cererile la motoarele de cãutare pentru fiºiere MP3 au trecut pe locul întîi ca frecvenþã, depãºind liderul anterior, pornografia. A doua categorie este cãutarea de versuri, iar a treia este cãutarea de partituri. Obiectele cãutate sunt adesea ilegal prezente pe Internet, cei care le oferã încãlcînd legea copyright-ului. Sunt ilegale atît publicarea cîntecelor, versurilor, sau partiturilor, cît ºi obþinerea lor de pe Internet, fãrã încuviinþarea posesorului copyright-ului.

Existã însã ºi un alt fel de cãutare, care poate fi perfect legalã: identificarea cîntecului. În acest tip de cãutare rezultatul este numele cîntecului, eventual autorul, albumul, ºi poate o legãturã spre un magazin care oferã piesa spre vînzare. De cîte ori vi s-a întîmplat sã nu vã puteþi scoate din minte o melodie? Uneori vã amintiþi un vers sau douã, caz în care Internetul vã poate ajuta sã-l identificaþi. Alteori, tot ce vã mai amintiþi este melodia, caz în care singura speranþã stã în prieteni: poate dacã încercaþi sã le cîntaþi un fragment (ºi dacã vocea vã permite) ºi dacã prietenii recunosc melodia, atunci veþi afla numele cîntecului.

Aceastã ultimã metoda de cãutare poartã numele de cãutare dupã conþinut; aplicaþiile ei sunt nenumãrate. Prin analogie, cãutarea dupã conþinut în domeniul imaginilor1 gãseºte imagini similare pornind de la o imagine-exemplu. Tehnologia cãutãrii dupã conþinut este încã foarte primitivã pentru tipuri de date multimedia. Sã încercãm sã vedem care sunt dificultãþile în domeniul muzical.

Probleme în cãutarea dupã conþinut

Vrem deci ca un utilizator sã poatã cînta o melodie (întrebarea), ºi un sistem electronic sã o identifice în mod automat într-o bazã de date. Pentru aceasta trebuie sã fim capabili sã comparãm douã melodii (sau o melodie cu un fragment -- întrebarea), pentru a putea spune cînd douã melodii sunt asemãnãtoare ºi cînd sunt diferite. Avem de rezolvat însã mai multe probleme dificile:

Una din problemele cele mai mari este chiar sursa. Nu toþi oamenii au ureche muzicalã bunã ºi numai o parte dintre aceºtia pot cînta bine. Un sistem care cere o reproducere perfectã a fragmentului este util doar pentru o minoritate restrînsã. De aceea cãutarea trebuie sa fie tolerantã la erori în ``întrebare'': note greºite, note lipsã, note în plus. De asemenea este foarte probabil cã fragmentul va fi cîntat mai rapid sau mai lent decît originalul, ºi în altã tonalitate.

O a doua problemã este extragerea notelor (pitch tracking) din întrebare. În urma înregistrãrii nu obþinem un fiºier cu conþinut simbolic (ex. MIDI), ci o înregistrare (ex. wav). Cãutarea necesitã identificarea notelor din acest fiºier. Acest proces introduce erori suplimentare: unele note vor ieºi fragmentate, cîteodatã note identice vor fi concatenate; vocea umanã adesea trece între note consecutive în mod continuu (glissando), iar sistemul ar putea decide cã trecerea de la ``sol'' la ``la'' s-a fãcut în alt moment decît intenþiona utilizatorul, note fictive pot apãrea, de obicei armonicele notei cîntate, pentru cã am vãzut cã sunetele emise nu sunt pure. Extragerea notelor este una din componentele în care s-au înregistrat progrese substanþiale în ultima vreme, ºi pe care o putem considera rezolvatã satisfãcãtor din punct de vedere ingineresc. Programe precum Digital Ear http://digitalear.iwarp.com ºi Autoscore http://www.wildcat.com/Site/Homepage.htm au ajuns la performanþe uimitoare.

O a treia problemã este cea a bazei de date. Cãutarea necesitã o bazã de date cu toate cîntecele ce se doresc recunoscute, stocate în format simbolic. La ora actualã nu existã nici o astfel de colecþie care sã fie suficient de comprehensivã pentru a fi cu adevãrat utilã în aplicaþii practice.

Soluþii

Sã ne reamintim cã încercãm sã definim o noþiune de distanþã între douã fragmente muzicale, care mãsoarã similaritatea dintre ele.

Sã încercãm sã vedem ce soluþii existã pentru toate aceste probleme. Prima problemã constã în inacurateþea reproducerii fragmentului de cãtre utilizatorii sistemului. De aceea, sistemul trebuie sa foloseascã o mãsurã a similaritãþii care sã aibã urmãtoarele proprietãþi:

Date douã fragmente de melodii, putem mãsura similaritatea dintre ele prin compararea graficelor lor. Problema similaritãþii a douã fragmente de melodii se transformã astfel într-una de comparare a douã funcþii treaptã.

Figura 3: ``Distanþa'' dintre douã melodii reprezentate ca funcþii treaptã se poate mãsura prin aria dintre ele.
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{arie.eps}}\end{figure}

Sã presupunem cã cele douã fragmente au aceeaºi lungime. Graficele corespunzãtoare vor avea ºi ele aceeaºi lungime. Dacã le vom vizualiza suprapuse, o bunã mãsurã a distanþei dintre ele este aria dintre cele douã grafice, ca în figura 3.

Cînd calculãm distanþa dintre grafice, trebuie sã translatãm unul din grafice pe verticalã, astfel încît sa minimizãm aria dintre ele. În felul acesta distanþa este invariantã la schimbarea gamei ºi, în acelaºi timp, tolerantã la note false.

Pentru a obþine invarianþã la tempo, încercãm sã dilatãm unul din fragmente cu diverºi factori, pentru a minimiza aria dintre cele doua funcþii.

Iatã o schiþã a algoritmului pe care Cristi l-a implementat, care calculeazã distanþa dintre un fragment cîntat ºi o melodie monofonicã (care are o singurã linie melodicã, fãrã acompaniament):


pentru diverºi factori de scalare între 0.5 ºi 2 

scaleazã fragmentul cu factorul curent
translateazã graficul lui de-a lungul graficului melodiei (peorizontalã)
pentru fiecare poziþie intermediarã
translateazã fragmentul pe verticalã pentru a minimiza aria dintre cele douã
raporteazã cea mai micã arie gãsitã în acest proces

Funcþionarea acestui algoritm este ilustratã în figura 4.

Figura 4: Funcþionarea algoritmului de calcul a distanþei: (1) date fiind o melodie (linia neagrã) ºi o întrebare (linia roºie) exprimate prin funcþii treaptã, trebuie sã gãsim ``potriveala'' maximã dintre ele. În prima fazã (care nu e ilustratã) întrebarea este translatatã în timp pentru a gãsi locul unde apare în melodie (nu neapãrat la început), apoi (2) întrebarea este scalatã în timp, pentru a potrivi tempo-ul cu cel al melodiei, ºi în fine (3) este scalatã în frecvenþã pentru a fi la aceeaºi ``înãlþime'' cu piesa. Toþi cei trei paºi sunt fãcuþi pînã cînd distanþa (aria dintre cele douã curbe) este minimizatã; calculul distanþei este deci un proces de cãutare.
\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îteva alte probleme neplãcute înainte de a face acest sistem cu adevãrat practic.

Prima dintre ele este faptul cã melodiile nu sunt, în general, monofonice (în vreme ce reproducerile oamenilor sunt). De aceea, înainte de a putea aplica algoritmul nostru, trebuie sã transformãm fiecare cîntec într-o melodie monofonicã. Acest lucru este fãcut fãcînd o analizã spectralã a muzicii ºi eliminînd toate notele în afarã de cea cu energia maximã2.

A doua problemã constã în extragerea notelor din fiºiere de tip wav (conversia de la o înregistrare la un format simbolic). În mod cert, calitatea programelor ce convertesc wav la MIDI a crescut foarte mult, pentru fiºiere monofonice. Distanþa pe care o folosim însã este tolerantã ºi erori introduse de aceastã conversie: fragmentare sau alipire de note, trecerea de la o notã la alta la momente inoportune.

A treia problemã constã în lipsa de cîntece în format simbolic. Un mod de a rezolva aceastã problemã este de culege fiºiere MIDI de pe Web. Pe web existã cel puþin 100 000 de astfel fiºiere, suficient pentru a construi o bazã de date respectabilã folosind un ``pãianjen'' (web spider, crawler), asemãnãtor celor folosite de motoarele de cãutare. Se estimeazã cã 99.99% dintre cererile de cãutare de cîntece pe Internet se referã la mai puþin de 10000 de melodii diferite.

Deºi folosirea MIDI este atractivã datoritã numãrului mare de fiºiere disponibile, existã ºi dezavantaje: marea majoritate a acestor fiºiere sunt create de cãtre amatori, ceea ce duce la o calitate îndoielnicã a reproducerii originalului. Aºa cum am menþionat mai sus, prezenþa unor multiple canale ºi a mai multor sunete simultane în fiecare canal este un impediment în folosirea acestor fiºiere; cu toate acestea, din punct de vedere practic fiºierele MIDI reprezintã un compromis excelent, fiind într-un format uºor de prelucrat, ºi în numãr foarte mare.

Figura 5: Sistemul humwistle, http://www.humwistle.com în întregime. Componentele indicate cu albastru sunt în curs de dezvoltare. O colecþie mare de fiºiere MIDI este extrasã de pe web. Informaþiile textuale inserate în corpul fiºierelor MIDI sunt extrase ºi folosite pentru etichetarea ºi indexarea fiºierelor. Componenta aurie este cea descrisã în acest articol ºi este partea cea mai inovatoare a sistemului, care permite cãutarea dupã melodii cîntate.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{sistem.eps}}\end{figure}

Acestea fiind zise sã aruncãm o privire asupra sistemului în curs de dezvoltare în cadrul departamentului de calculatoare al universitãþii Rutgers, descris în figura 5. Sistemul este format din trei componente majore. Prima colecteazã fiºiere MIDI de pe web într-un proces continuu, le clasificã ºi le adaugã la baza de date. A doua componentã preia cererile de cãutare pe bazã de text (autor, cîntec, album, versuri) ºi executã o cãutare textualã în baza de date, folosind tehnici standard de biblioteci digitale ºi informaþiile simbolice prezente în fiºierele MIDI. A treia componentã preia cererile de cãutare pe bazã de fragmente cîntate, le transformã în fiºiere MIDI folosind o subcomponentã de extragere a notelor, apoi cautã fragmentul respectiv în cîntecele din baza de date folosind algoritmul de mai sus.

Experimente

Rezultatele obþinute cu acest sistem sunt încurajatoare. Am efectuat experimente pe un set de 10 000 de cîntece, din totalul de 100  000 existente în baza de date. Mai mulþi subiecþi au cîntat 30 de fragmente muzicale diferite, fiecare între 4 ºi 22 de secunde în 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întecului real, din care fãcea parte fragmentul (chiar dacã cîntecul era substanþial diferit, cu ritm sincopat sau cu variaþiuni). Cîntecul original, din care fãcea parte fragmentul, a fost aproape mereu prezent între primele 20 de posibilitãþi, cel mai adesea pe primul loc.

Un al doilea set de experimente a avut ca obiectiv evaluarea performanþei subiecþilor umani pentru acelaºi test: cît de buni sunt oamenii la recunoaºterea unui cîntec dupã un fragment cîntat de cineva. Am selectat ºase fragmente dintre cele 30. Subiecþii umani au pornit recunoaºterea de la fragmentul transpus în formã simbolicã MIDI, deci dupã pitch tracker; în felul acesta au primit aceleaºi erori introduse de pitch tracker pe care le-a primit ºi sistemul automat. Subiecþii nu au avut constrîngeri de timp ºi li s-a permis sã asculte fragmentele de ori cîte ori au dorit. Am considerat cã un subiect a recunoscut cîntecul fie dacã a putut spune numele, fie dacã a putut sã fredoneze cîteva note în continuarea fragmentului. Nici unul din subiecþi nu a fost muzician profesionist. Toate fragmentele muzicale erau cunoscute subiecþilor.

În medie subiecþii au recunoscut 1,5 cîntece din 6 posibile. Numãrul maxim de cîntece recunoscute a fost 4, iar numãrul minim zero. În schimb, sistemul a reuºit sa identifice 4 din 6. Concluzia acestui experiment este cã recunoaºterea cîntecelor este o problemã grea chiar ºi pentru oameni, ºi este plauzibil ca în viitor calculatoarele sã devinã mai bune decît omul în acest domeniu.

Calculele necesare pentru identificarea unui cîntec sunt foarte costisitoare: implementarea curentã necesitã aproximativ ºapte ore ºi jumãtate pentru a rãspunde la o întrebare, ºi aceasta folosind baza de date redusã, de 10000 de melodii. De aceea eforturile de cercetare se concentreazã în gãsirea unui algoritm mai rapid. De asemenea, trecerea de la 10000 de cîntece la un milion de cîntece este deosebit de grea: indiferent de viteza algoritmului de calcul al distanþei, el tot va trebui sa compare fragmentul cu un milion de posibili candidaþi. De aceea eforturile noastre se îndreaptã spre gãsirea unor metode de indexare care sã permitã eliminarea din start a majoritãþii cîntecelor, ca fiind foarte diferite. Algoritmi folosind tehnologii de inteligenþã artificialã vor fi folosiþi pentru a grupa (clustering) cîntecele în categorii înrudite, care pot fi eliminate dintr-o datã.

Alte eforturi de cercetare în biblioteci muzicale

Proiectul humwistle nu este singurul care studiazã problema creãrii ºi accesãrii unei biblioteci digitale. Pare însã sã fie cel care a rezolvat cu cel mai mare succes problema cãutãrii, datoritã funcþiei distanþã folosite pentru mãsurãtori. În aceastã secþiune enumerãm pe scurt alte cîteva proiecte, care sunt din cunoºtinþele autorilor cele mai avansate în domeniu.

Cercetarea universitarã în domeniul similaritãþii melodiilor a început prin anii '70, dar sisteme practice nu au apãrut pînã în 1995. Cauzele acestei stagnãri sînt multiple; Internet-ul a explodat de curînd, deci cererea de cãutare dupã conþinut are mult mai mulþi ``clienþi''. Marile companii de discuri au început sã foloseascã Internet-ul de numai cîþiva ani. De asemenea, fiºierele MIDI au devenit cu adevãrat populare de curînd.

Asif Ghias ºi echipa lui de la universitatea Cornell din SUA în 1995 au construit primul sistem experimental de recunoaºtere a unui cîntec. Metoda folositã de ei constã în extragerea notelor din fragmentul cîntat; apoi fragmentul este transcris ca o secvenþã de simboluri U, D, sau S. O notã este transformatã în U (up) dacã este mai înaltã decît nota anterioarã, S (same) dacã este aceeaºi notã sau D (down) dacã este mai joasã. Melodiile din baza de date sunt reprezentate în aceeaºi manierã. Fragmentul este cãutat în baza de date folosind un algoritm binecunoscut de comparare a unor ºiruri de caractere, permiþînd mai puþin de k diferenþe (algoritmul Baesa-Yates).

Sistemul a demonstrat viabilitatea ideii, dar lãsa de dorit din punct de vedere practic: baza de date conþinea numai 183 de cîntece, iar algoritmul necesita din ce în ce mai multe note în fragmentul cîntat pe mãsurã ce baza de date creºte,3 fãcîndu-l nepractic pentru 10000 de cîntece.

De departe cele mai bune rezultate în domeniu au fost obþinute de McNab ºi echipa sa, la universitatea Waikato din Noua Zeelandã. Ei au construit un sistem care a testat mai multe funcþii distanþã diferitã. Baza lor de date, asamblatã din partituri de cîntece populare germane ºi chinezeºti, conþinea 10000 de melodii. Metoda de comparare care a dat cele mai bune rezultate constã în exprimarea fiecãrei note ca o pereche (interval, duratã), unde intervalul este distanþa faþã de nota precedentã. Cîntecele din baza de date erau codificate în acelaºi fel, iar distanþa folositã era ``distanþa de editare''. Distanþa de editare dintre douã ºiruri de caractere, edit-distance, este numãrul minim de operaþii de inserare, ºtergere sau înlocuire de caracter care trebuie aplicate primului ºir pentru a-l obþine pe al doilea.

Sistemul a demonstrat performanþe uimitoare: atunci cînd fragmentul cîntat era chiar începutul cîntecului, 12 note erau de ajuns pentru a reduce numãrul de melodii candidat la mai puþin de 10. Din pãcate publicaþiile lor nu spun ce se întîmplã atunci cînd fragmentul de recunoscut poate fi oriunde în cîntec. Cercetãri ulterioare sugereazã cã, în acest caz, numãrul de note necesare pentru dezambiguare creºte din nou foarte mult, fãcînd sistemul nepractic.

Un alt pionier al cãutãrii pe bazã de conþinut este J. S. Downie, de la universitatea din Western Ontario, Canada. El a observat faptul cã atunci cînd baza de date creºte este prea costisitor sã comparãm fragmentul cîntat cu toate melodiile: numãrul de calcule ar fi prea mare. De aceea el a încercat sã aplice tehnici clasice de indexare folosite în bibliotecile digitale cu text ºi de motoarele de cãutare de pe World Wide Web. El a definit ``cuvintele'' ca fiind secvenþe de patru sau cinci note consecutive ºi apoi a construit un index foarte asemãnãtor cu indexul de la sfîrºitul unei cãrþi tehnice: pentru fiecare cuvînt, indexul indicã locul lui de apariþie, pagina în cazul cãrþii, cîntecul în cazul nostru. Un fragment de recunoscut este segmentat în note, apoi scris ca o succesiune de ``cuvinte''. Fiecare din aceste cuvinte apare în mai multe cîntece, iar, dintre acestea, cîntecul care apare în listele indicate de toate cuvintele este cel cãutat.

Metoda funcþioneazã foarte bine ºi mai ales rapid, atunci cînd fragmentele cãutate sunt reproduceri fidele ale originalului. Din pãcate, performanþa sistemului se degradeazã foarte mult atunci cînd o notã sau douã sunt greºite, ceea ce, din nou, face sistemul nepractic.

Toate aceste încercãri 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 ºir de caractere. Un simbol este fie nota, fie diferenþa în semitonuri faþã de nota anterioarã, fie o pereche de un de numãr ºi o duratã. Aceastã reprezentare este problematicã pentru construcþia unei bune mãsuri de similaritate, deoarece o notã fragmentatã, sau mai multe note concatenate schimba dramatic reprezentarea unui fragment, deºi, în esenþã, el diferã puþin de original. De aceea, noi am optat pentru reprezentarea prezentatã mai sus, în care o melodie nu mai este o înºiruire de simboluri, ci mai degrabã o variaþie continuã în timp a înãlþimii notei. Considerãm cã aceasta este cheia care a permis obþinerea unor rezultate mai bune decît oricare din cele raportate pînã în prezent.

Evoluþii viitoare

Sistemul humwistle este disponibil pe Internet. În momentul de faþã numai cãutarea textualã este accesibilã on-line. Cînd performanþele cãutãrii pe bazã de conþinut se vor îmbunãtãþi suficient pentru o utilizare interactivã, ea va fi de asemenea disponibilã pe web.

Aplicaþiile comerciale ale sistemului sunt enorme: companiile de discuri ar putea crea astfel de baze de date în care fiecare piesã în format wav sau PCM (de pe CD) este însoþitã de o descriere MIDI, eventual extrasã automat. Utilizatorul poate interoga baza de date, iar sistemul descris poate identifica melodia MIDI corespunzãtoare. Apoi utilizatorul poate cumpãra dupã dorinþã înregistrãrile piesei, sau partitura, extrasã direct din MIDI.

Muzicienii ar putea folosi un astfel de sistem pentru a detecta plagiarismul în cantitãþi enorme de cîntece, cãutînd temele din propriile lor compoziþii.

O aplicaþie interesantã acestei tehnologii este în calculatoare mobile, unde spaþiul ecran este foarte restrîns. Posibilitatea de a selecta cîntece spre ascultare prin cîntarea unui fragment ar putea fi de nepreþuit. Un player de MP3-uri conectat la reþeaua de telefonie celularã ar putea sa aducã cîntece la cerere, pornind de la scurte fragmente cîntate.

Imaginaþi-vã conducînd un automobil peste zece ani, care va include un player de MP3 care are suficientã memorie pentru a stoca toatã colecþia dumneavoastrã de cîntece. Cum aþi putea face pentru a selecta o melodie sau un album spre ascultare, fãrã sã trebuiascã sã luaþi mîna de pe volan pentru a scotoci în cutia cu discuri? O soluþie elegantã ar fi sã cîntaþi un fragment din cîntecul dorit. În plus, aceastã soluþie nu necesitã luarea mîinilor de pe volan.

Alte surse de informaþie

Pe Internet existã o cantitate enormã de informaþie despre formatele digitale audio, ºi mai ales despre MP3, care e la mare vogã. Folosiþi motorul dumneavoastrã de cãutare favorit.

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

Cristian Frâncu ºi 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.

Asociaþia internaþionalã pentru muzicã pe calculator are liste foarte impresionante de resurse ºi informaþii plecînd 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
Vedeþi ºi articolul despre Computer Vision PC Report din iulie.
... a2
Aceasta nu este neapãrat cea mai bunã metodã pentru a detecta ``melodia principalã'', dar este foarte simplã ºi funcþioneazã bine în practicã.
... ste,3
Asta pentru cã dacã transformãm cîntecele doar în U, D, S, ele tind sã semene mult între ele; pentru a le diferenþia e nevoie de din ce în ce mai multe note.