# Empremta digital acústica

Les empremtes digitals acústiques són identificadors per a arxius d'àudio basats en el contingut del fitxer. Amb elles podem identificar un patró o "signatura" d'un arxiu d'àudio, perquè aquest pugui ser reconegut des d'una base de dades d'àudio, sense necessitat de disposar informació sobre aquest. El seu ús es basa en la detecció d'una mostra d'àudio i posterior enviament a una base de dades (BD), per un cop analitzada buscar coincidències en aquesta i tornar informació sobre la mostra analitzada. Actualment ha evolucionat considerablement, ja que resulta un sistema molt ràpid i fiable en recuperació i indexació de dades, així com la reducció de la grandària dels continguts emmagatzemats al no ser necessari tenir-los al nostre equip, i per l'assignació d'una identitat a cada senyal d'àudio, per posteriorment ser tractat.

## Requisits d'identificació

Basant-nos en la detecció freqüencial, un algorisme precís de detecció d'empremtes acústiques ha de ser capaç de:
* Detectar amb precisió un fragment d'àudio, independentment de la compressió, distorsió i / o interferències del canal de transmissió.
* Depenent de l'aplicació, ser capaç de reconèixer el títol de l'arxiu amb una durada d'uns pocs segons, que anirà determinat pel mètode de tractament del senyal i sincronització entre la mostra adquirida i la base de dades.
* Reconèixer la mostra fins i tot si està degradada / modificada, equalitzada, també el seu pitch (velocitat de reproducció), efectes, sorolls externs, conversió i/o digitalització i codificació.
* Sistema eficient, en funció de la grandària de la mostra adquirida, la complexitat de l'algorisme de cerca i l'extracció de les empremtes de l'arxiu.
Donat un fragment d'àudio i la seva corresponent empremta dactilar, hem de buscar la via més ràpida per trobar la seva millor coincidència. Des del nombre d'iteracions en la cerca fins a la longitud de la mostra, poden resultar computacionalment costosos. Perquè la cerca sigui eficient, el mètode de cerca ha de ser:
    - Ràpid: Capacitat de lectura en escombrat en grans bases de dades.
    - Vàlid: Devolució d'un resultat correcte i precís.
    - Amb memòria eficient: Necessitat de poc espai en memòria.
    - Actualitzable: ha de permetre actualitzacions, modificacions i / o eliminació d'objectes.

## Tècniques de detecció

Podem detectar les empremtes acústiques d'un arxiu de dues maneres:
    - Temporalment: reconeixement del patró de l'arxiu en funció de la intensitat del senyal i el temps. Es basa en la forma d'ona en funció del temps.
    - Freqüencialment: reconeixement del patró de l'arxiu en funció de les freqüències i els seus pics d'intensitat i el temps. Es basa en les característiques del sistema auditiu humà.
La principal diferència entre les dues, es basa en la precisió. Una anàlisi temporal implica una detecció de soroll bastant important. L'alt grau de variància dels senyals d'àudio fa molt complicada una anàlisi temporal precisa.
Utilitzant l'anàlisi freqüencial, aconseguim detectar els valors màxims de les freqüències més representatives, aconseguint evitar el soroll de fons. Això implica:
    - Major precisió i detecció de l'arxiu d'àudio.
    - Menor vulnerabilitat al soroll i elements externs.
    - Menor valor màxim en detecció (valor entrada).

## Procés d'identificació d'arxius

Per a la detecció d'un arxiu d'àudio, ens trobem amb dos processos. En primer lloc extraurem la informació més característica del senyal i la tractarem perquè pugui ser modificada. Després l'enviarem per comprovar si hi ha alguna informació sobre la nostra mostra.

### Extracció d'empremtes dactilars

Per a l'extracció d'empremtes dactilars, hem de tenir en compte que el procés ha de ser capaç de:
    - Discriminar entre un gran nombre d'empremtes.
    - No variar per distorsions.
    - Compactar en execució.
    - Tenir una necessitat computacional baixa.
Aconseguir aquests requisits requereix un equilibri entre la reducció de la dimensionalitat i la pèrdua d'informació.
Aquest bloc està compost pels blocs front-end i modelatge d'empremtes dactilars. Front-end s'encarregarà de realitzar les mesures i càlculs necessaris per extreure la informació més important de l'arxiu, on una vegada calculada, s'enviarà al modelat d'empremtes dactilars, per tractar aquestes dades i la seva respectiva representació, per al seu posterior accés a la BD.

#### Front-End

Converteix el senyal d'àudio en una seqüència de les característiques més rellevants d'aquest. Per al seu correcte desenvolupament s'ha de tenir en compte que ha d'aconseguir:
    - Reducció de la dimensionalitat.
    - Paràmetres significatius similars als del sistema auditiu humà.
    - Invariància per paràmetres externs.
    - Correlació temporal.
En el seu interior trobem diversos processos que, en algunes aplicacions, poden contenir By-Pass per pre-configurar el procés.

##### Preprocessat

L'àudio es digitalitza (si cal) i es converteix a un format d'àudio genèric (normalment PCM 16 bits). S'analitzarà en funció del nombre de canals i el tipus d'àudio. A més es normalitzarà i filtrarà per bandes per adequar el senyal al processat.

##### Framing i overlap

Els senyals acústics es consideren estacionaris quan la seva durada és de l'ordre de mil·lisegons. Es subdivideix el senyal en mostres de grandària tal que les puguem considerar estacionàries. La mida anirà en funció de la velocitat de variació del senyal.

##### Transformada. Estimació d'espectre

La idea de les transformades és aconseguir un nou conjunt de característiques per reduir la redundància del senyal. Hi ha tècniques òptimes per a la transformació, com Karhunen-Loève (KL) o Singular value decomposition (SVD), però, com que són tècniques computacionalment complexes, s'utilitzen tècniques més senzilles com Lourens, Kurth, etc. La tècnica més comuna és la FFT o transformada ràpida de Fourier, encara que també són utilitzades la transformada discreta de cosinus (DCT) o la Wavelet de Haar transformada Haar, entre d'altres.

##### Extracció de característiques

Un cop aconseguida la representació temps-freqüència, hem d'aplicar diversos processos per aconseguir el vector característica final. L'objectiu és novament reduir la dimensionalitat i incrementar la invariància per distorsions. S'aplicaran diverses tècniques que aprofiten les limitacions del sistema auditiu humà per aconseguir-ho, així com mesures d'energia, volum, detectors d'envoltant, etc.

##### Postprocessat

La majoria de les característiques descrites fins ara són mesures absolutes. Per millorar la caracterització del senyal, s'afegeixen derivades d'ordre major. El vector de característiques es crearà amb aquest paràmetre, que variarà en funció de l'algorisme utilitzat. També és comú aplicar una resolució molt baixa en la quantificació. D'aquesta manera es guanya robustesa a distorsions. Així preparem les dades perquè siguin empaquetades en funció de com es mostraran i/o consultaran.

#### Modelat d'empremtes dactilars

Aquest bloc rep els vectors característiques creats en el procés anterior. S'encarregarà de processar els vectors i transformar-los en un únic vector característica (recordem que trobem diferents vectors, per a cada banda freqüencial, energies, filtres, etc.), per a posteriorment ser enviat. Novament és de vital importància la dimensionalitat dels algorismes, per evitar enviar grans quantitats d'informació a la BD. L'adaptació dels vectors variarà en funció de cada programa, els quals gestionaran la grandària de la mostra adquirida i els vectors que utilitzaran, entre altres paràmetres. Aquests programes han estat dissenyats per treballar amb Metadades, mitjançant ells rebrem la informació referent a la mostra analitzada. Actualment podem trobar diferents programes.

### Coincidència

Un cop creada l'empremta digital acústica, el següent pas és buscar coincidències per retornar informació sobre la nostra mostra. S'enviarà el nostre "patró" i tota la possible informació addicional creada (metadades, capçaleres, etc.) a una base de dades, per buscar qualsevol coincidència. Hem de tenir en compte dos factors que repercuteixen directament en aquest procés:

#### Distància

A l'hora de relacionar les característiques de la mostra, és de vital importància la distància presa entre característiques properes. Tècniques com la distància Euclidiana o la longitud Manhattan o Hamming són utilitzades per calcular aquestes distàncies. Per a una correcta cerca, tant el vector característica creat com el vector característica de la BD han d'utilitzar les mateixes tècniques, perquè les seves petjades coincideixin sense error de distància.

#### Cerca

D'altra banda, hem de realitzar de manera eficient la recerca a la BD. Si després de crear un vector de dimensionalitat reduïda no aconseguim un algorisme de cerca eficient, el nostre esforç haurà estat en va. La tècnica més comuna es basa en la creació d'índexs, per estructurar la informació. D'aquesta manera reduïm considerablement el rang de dades a consultar. Podem trobar diferents tècniques d'optimització de consulta de dades, basades en índexs, heurística, codi de paraules, etc. Un cop trobada (o no) la consulta, el sistema ens tornarà tota la informació continguda en el seu BD sobre la nostra mostra, incloent títol, artista, any, àlbum, etc.

#### Verificació hipòtesi

Finalment, durant la consulta a la BD, es creen resultats sobre el vector creat. Aquests resultats són utilitzats per actualitzar la BD. Amb ells s'aconsegueix actualitzar resultats anteriors, afegir nous resultats i millorar la precisió de les mostres emmagatzemades. En podem consultar tota la informació i nomenclatura utilitzada en aquest últim procés.

## Aplicacions

La majoria d'aplicacions es troben en dispositius mòbils i equips de sobretaula. Tot i això s'està començant a aplicar en medicina i indexació de dades, per la seva alta velocitat d'accés a la informació (consultes ADN, per exemple).
* BMAT Vericast
* Shazam
* Music ID
* Tunatic
* Fingerprints on FBI and law apps
* Fingerprints on medical apps

## Referències

* ↑ ISO IEC TR 21000-11 (2004), Multimedia framework (MPEG-21) -- Part 11: Evaluation Tools for Persistent Association Technologies
* 1 2 R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval. Addison Wesley, 1999.
* ↑ S. Theodoris and K. Koutroumbas, Pattern Recognition. Academic Press, 1999.
* ↑ J. Lourens, “Detection and logging advertisements using its sound,” in Proc. of the COMSIG, Johannesburg, 1990.
* 1 2 F. Kurth, A. Ribbrock, and M. Clausen, “Identification of highly distorted audio material for querying large scale databases,” in Proc. AES 112th Int. Conv., Munich, Germany, May 2002.
* ↑ S. Subramanya, R.Simha, B. Narahari, and A. Youssef, “Transformbased indexing of audio data for multimedia databases,” in Proc. of Int. Conf. on Computational Intelligence and Multimedia Applications, New Delhi, India, Sept. 1999.
* 1 2 P. Cano, E. Batlle, H. Mayer, and H. Neuschmied, “Robust sound modeling for song detection in broadcast audio,” in Proc. AES 112th Int. Conv., Munich, Germany, May 2002.
* ↑ E. Allamanche, J. Herrero, O. Helmuth, B. Fr ¨ oba, T. Kasten, and M. Cremer, "Content-based identification of àudio material using mpeg-7 low level description," in Proc. of the Int Symp. of Music Information Retrieval, Indiana, USA, Oct 2002.
* ↑ G. Richly, L. Varga, F. Kov'acs, and G. Hossz'u, "Short-term sound stream characterisation for reliable, real-time occurrence monitoring of given sound-prints," in Proc. 10th Mediterranean Electrotechnical Conference, MEleCon, 2000.
* ↑ (2002) Etantrum. [Online]. Available: http://www.freshmeat.net/projects/songprint%5BEnllaç+no+actiu%5D
* ↑ (2002) Musicbrainz TRM. MusicBrainz-1.1.0.tar.gz. [Online]. Available: ftp://ftp.musicbrainz.org/pub/musicbrainz/
* ↑ E. Chavez, G. Navarro, R. A. Baeza-Yates, and J. L. Marroquín, "Searching in metric spaces," ACM Computing Surveys, vol. 33, no. 3, pàg. 273-321, 2001.
* ↑ http://www.bmat.com/products/vericast/index.php Arxivat 2011-11-22 a Wayback Machine.
* ↑ http://www.shazam.com
* ↑ http://www.musicid2.com Arxivat 2010-12-20 a Wayback Machine.
* ↑ http://www.wildbits.com/tunatic
* ↑ http://hubpages.com/hub/Applications-For-Fingerprints-by-the-FBI-and-Law-Enforcement
* ↑ http://www.accessexcellence.org/RC/AB/BA/DNA_Fingerprinting_Basics.php

## Enllaços externs

* A Review of Algorithms for Audio Fingerprinting (P. Cano et al. In International Workshop on Multimedia Signal Processing, US Virgin Islands, December 2002)
* Content-Based Retrieval of Music and Audio by Jonathan Foote, ISS, National University of Singapore.