Download PROMS:A Web-based Tool for Searching in Polyphonic Music

Curso doctorado CAMO 2008
PROMS:A Web-based Tool for
Searching in Polyphonic Music
M.Clausen, R. Engelbrech, D. Meyer, J. Schmitz
Institut für Informatik V, Universität Bonn
Jose Francisco Bernabeu Briones
Introducción
Principal tarea de una biblioteca de música digital (DML)
-Proporcionar técnicas para localizar un patrón musical en las piezas de música
de la base de datos..
-Estas técnicas normalmente trabajan con información similar a las partituras.
Se han utilizado:
-Modo tolerante a fallos
-Métodos basados en cadenas
-Principalmente teniendo en cuenta la información de tono (pitch).
Introducción
Barlow y Morgenstern muestran que:
-Recuperación de música basada sólo en la información del tono (pitch) conduce a
-Resultados con demasiadas coincidencias falsas.
Reconocimiento de melodías son cruciales:
-El tono (pitch)
-El ritmo.
PROMS,
-Es un servicio de computación de música basado en web
-Desarrollado en la Universidad de Bonn, Alemania,
-Es parte del proyecto MiDiLiB
-Objetivo
- Diseñar y aplicar PROcedimientos de búsqueda de MúSica.
La base de datos contiene varios tipos de música
-Polifónica
-Monofónica
Utilizamos información similar a las partituras.
Consulta (query) a la base de datos es:
-Un fragmento de una pieza musical.
-Melodía
-Figura de un acompañamiento.
Objetivo
-Localizar de forma eficiente
-El fragmento en todas las piezas musicales de la base de datos.
Consideraciones
Necesitamos:
- Altura (pitch)
- El tiempo de inicio de cada nota (onset).
No tendremos en cuenta la duración de las notas.
Representación de una pieza musical:
-Conjunto de notas donde cada nota es un par [t, p] donde:
-t (onset)
-p (pitch).
Consideraciones
Tiempo de resolución
-Hace muy difícil la recuperación
-Onsets de las notas pueden ser muy irregulares.
Solución:
-Fijar un time-grid (divisiones del compás) facilita la implementación
considerablemente.
-Onsets deben cuantizarse a un time-grid preseleccionado,
-Ej. resolución 16 (semicorcheas).
-Piezas y consulta son cuantizadas de la misma forma.
Consideraciones
Problemas de cuantización
-Diferentes combinaciones de notas podrían ser iguales una vez cuantizadas.
-Una melodía cuantizada podría dar lugar a unos acordes.
Consideraciones
Time- grid (divisiones de un compás)
-Se pueden utilizar time-grids que dividan un compas irregularmente:
-Ej, time-grid que contiene puntos de grid
-En semicorcheas
-En tresillos de corchea.
-Simplificación
-Consideramos sólo grids equidistantes.
Consideraciones
Pitch (tono, altura de las notas)
-Representado por un entero.
-Enteros entre el 0 y 127 .Las piezas proceden de ficheros MIDI.
Una nota con el tiempo de inicio (onset) t y altura (pitch) p sera denotado por [t, p]
(i, M) es un índice que apunta al compás M de la pieza i.
PROMS también incluye la recuperación en bases de datos de melodía.
Consideraciones
El usuario puede consultar
-Un fragmento melódico no contiguo
-Dejar fuera pasajes demasiado complejos o poco familiares.
-No tiene repercusión en la eficiencia.
-Posibilidad de especificar (notas aleatorias),
-Reflejan cierto grado de tolerancia a fallos con respecto a la altura (pitch) y la
métrica.
PROMS puede recuperar las ocurrencias de una consulta que como máximo tiene
k errores en las piezas recuperadas.
Coincidencia de patrones en música
Nuestra base de datos consta de N piezas de música P 1 , ... , P N
.
Time signature (métrica) = b / u (beats por unidad de compás).
-Es conocida en todas las piezas.
-Todas las piezas tienen la misma
Una vez se dé la resolución. Todas las piezas son cuantizadas con esta resolución
-Ej, r = 16 implica resolución de semicorchea (16 ticks por beat).
Coincidencia de patrones en música
- r / u es un entero.
-Selecciones habituales son r = 2u o r = 4u.
-Numero de posiciones de Time-grid dentro de un compás.
-l = br / u
b = 3, u = 4, y r = 16 obteniendo l = 12.
Coincidencia de patrones en música
Cada pieza Pi es un subconjunto finito de ℕ0 x [0 , 127],
-Conjunto de pares [t,p]
-[t, p] Pi .en el momento t la nota MIDI con altura p ocurre en la pieza Pi
Nota Absoluta [t, p]
Nota relativa [t mod l, p].
-Refleja la posición dentro del compás ⌊t /l ⌋
Coincidencia de patrones en música
La siguiente partitura está representada por los siguientes datos:
77
Coincidencia de patrones en música
Consulta (query) Q
-También es un subconjunto finito de ℕ0 x [0,127] con la misma semántica que
las piezas.
-Q tiene el misma métrica que las piezas de la base de datos.
La tarea consiste en listar todas las ocurrencias de Q en las diversas piezas Pi .
Q puede ocurrir varias veces en una misma pieza Pi , necesitamos especificar:
-La pieza
-La ubicación exacta donde se produce Q. (El Compás)
Coincidencia de patrones en música
Por definición, Q ocurre en el compás M de la pieza Pi si y sólo si
Sumamos el compas M a la query
Donde la suma de las notas es componente a componente:
[t, p] + [t ', p']:=[ t + t', p + p '].
Coincidencia de patrones en música
Cada ocurrencia de Q en la base de datos
-Se describe con un par (i, M) donde M es el compas M de la pieza Pi .
Las notas que están fuera de la resolución de grid no se tendrán en cuenta.
La siguiente figura ilustra dos consultas diferentes:
Q1 = {[0,74], [4,70]} y Q2 = {[4,74], [8,70]}.
Nuestro sistema no tiene en cuenta la duración de la nota,
Q1 y Q2 son similares y ocurren en P como hemos definido
anteriormente.
Coincidencia de patrones en música
Sin embargo, como sólo se permitirá posiciones de tiempo por múltiplos de l
(correspondientes al compás entero) cada una de Q1 y Q2 se produce exactamente una
vez en P.
Suponiendo que P es la pieza P1 de nuestra base de datos, la ocurrencia de Q1 es
descrita por (1, 2) mientras que Q2 corresponde a (1,1).
Q2
Q1
Coincidencia de patrones en música
En general, dada una consulta Q, nuestra tarea consiste en calcular el conjunto donde aparece
la consulta:
Construcción de la lista de consultas coincidentes
-Recolectamos todas las apariciones de notas con pitch p que pertenecen a [0: 127]
-Posiciones métricas m que pertenecen a [0: l-1]
en una lista L (m, p), es decir :
Coincidencia de patrones en música
Ahora hacemos que
sea una consulta con
Nos quedamos con la nota relativa.
A partir de la lista de coincidencias se puede obtener la siguiente intersección:
Donde
Coincidencia de patrones en música
Demostramos esta afirmación a través de la siguiente cadena de equivalencias:
Este resultado constituye la base teórica de una solución eficiente del problema de
reconocimiento de patrones.
Archivo de índice invertido
Es una técnica estándar de indexación utilizada en bases de datos de texto.
Contiene
-Para cada palabra w que aparece en la base de datos
- Una lista L (w) de referencias a los documentos que contengan dicha palabra.
Un consulta típica como "palabra1 AND ... AND palabraN" se procesa computando las
intersecciones de las listas invertidas para cada termino de la consulta (palabra):
Archivo de índice invertido
En el peor de los casos un archivo de índice invertido puede ser tan grande como toda la
base de datos.
Puede ser comprimido para ahorrar espacio en disco.
Las referencias se suelen guardar en forma relativa a la última referencia
Ej , L(ejemplo) = (5,11,13) se almacena en forma relativa como L '(ejemplo) = (5,6,2).
Las dos formas son equivalentes
-Los números de la forma relativa son mucho menores que en la forma absoluta.
Archivo de índice invertido
Comparación Texto vs Música.
-Una palabra de un texto corresponde a una nota relativa.
-Cada nota absoluta [t, p] corresponde a la “palabra” [t mod l, p].
Con esta idea, podemos implementar nuestro sistema de recuperación de música
mediante un archivo de índice invertido.
Dos diferencias entre la recuperación de texto y de música.
-El vocabulario de las bases de datos:
-La posición relativa de las palabras:
Archivo de índice invertido
El vocabulario de las bases de datos:
-De texto puede crecer con nuevos documentos.
-De música no crece con los nuevos documentos
hay 128 x l (resolución) listas invertidas.
Archivo de índice invertido
La posición relativa de las palabras:
-En texto no es importante
-En música, la situación es muy diferente.
-Si la consulta Q, contiene más de un compás, las listas en cuestión tienen
que ser preprocesadas de acuerdo a la Eq. (2) antes de intersectar las
listas modificadas.
-Es una variante del procesamiento de consulta habitual mediante
archivos invertidos.
Implementación
En general, los archivos MIDI no son monofónicos, y no están explícitamente
estructurados en componentes musicales, como melodías, temas, acordes, etc.
-Formato MIDI0
El tipo de compás (time signature) se conoce para cada archivo MIDI.
Aplicamos archivos invertidos para indexar nuestra base de datos de música.
-Una lista invertida existe para cada combinación de la altura y posición métricas.
Tenemos 128 x l listas L (m, p). En la práctica, una parte importante de las listas están
vacías. Ej:
L(8,9) =
L(8,10) =
L(8,11) =
L(8,12) = (0,2)(0,3)(0,4)(0,5)(1,2)(1,3)(1,4)(1,5)(2,2)(2,3)(2,4)(2,5)
L(8,13) =
L(8,14) =
Implementación
Algunos resultados.
*****************test 0 ****************
[0,0],
---------------------------------------------*****************test 1 ****************
[1,0],
---------------------------------------------*****************test 2 ****************
[2,0],
----------------------------------------------
Test i indica que la pieza i se
ha pasado como query.
[i,M] nos indica donde ha
encontrado la query.
i = pieza
M = compás
Búsqueda tolerante a fallos
En las secciones anteriores hemos tratado la recuperación exacta de la consulta.
Nuestro archivo de índice invertido soporta consultas incompletas para el caso de notas
desaparecidas.
Omitir notas es un tipo de tolerancia a fallos
Otro tipo es la especificación de notas aleatorias (fuzzy).
-El usuario sólo conoce el tiempo aproximado o
-Los intervalos de las notas de la consulta.
Búsqueda tolerante a fallos
El sistema de recuperación permite que el usuario especifique
-(en lugar de una consulta Q que consiste en una secuencia (q1 ,..., qn) de notas)
-una consulta difusa (fuzzy) Q que consiste en una secuencia (Q1 ,..., Qn)
-cada Qk es un conjunto finito y no vacío de notas absolutas.
Si Qk contiene más de un elemento, este puede reflejar la incertidumbre del usuario.
El conjunto de emparejados correspondientes a esa consulta difusa se define como
Búsqueda tolerante a fallos
En analogía a Eq. (2) obtenemos (con q =: [tq, pq] para una nota absoluta arbitraria q)
El tiempo de ejecución para una búsqueda de consulta difusa (fuzzy) se incrementa en
un factor proporcional a | Q1 |+...+| Qn |-n, donde | X | denota el número de elementos
del conjunto X .
Si | Qk | = 1 para todos los k entonces la búsqueda fuzzy se reduce a una búsqueda
exacta.
Búsqueda tolerante a fallos
Otro tipo de tolerancia a fallo consiste en permitir un máximo de desajustes fijos k, k
pertenece N0.
El parámetro k lleva de manera natural a la clasificación en un ranking de los resultados.
Por último, se pueden combinar las consultas fuzzy, distribuciones de probabilidad, y la
inadecuación de k, para obtener una mejor clasificación.
Búsqueda tolerante a fallos
Algunos resultados:
*****************test 1 ****************
(i,M) nos indica donde ha
encontrado la query.
i = pieza
M = compás
Lista de encontradas con 170 concidencias = (1,0)[0][[0]]
Lista de
Lista de
Lista de
Lista de
Lista de
encontradas
encontradas
encontradas
encontradas
encontradas
con 169 concidencias =
con 168 concidencias =
con 167 concidencias =
con 166 concidencias =
con 165 concidencias =
*****************test 27 ****************
Lista de encontradas con 118 concidencias = (27,0)[0][[0]]
Lista de encontradas con 117 concidencias =
Lista de encontradas con 116 concidencias =
Lista de encontradas con 115 concidencias =
Lista de encontradas con 114 concidencias =
Lista de encontradas con 113 concidencias = (26,0)[0][[0]]
Lista de encontradas con 112 concidencias =
Lista de encontradas con 111 concidencias = (24,0)[0][[0]]
Lista de encontradas con 110 concidencias =
Lista de encontradas con 109 concidencias =
Lista de encontradas con 108 concidencias = (23,0)[0][[0]]
-El número de
coincidencias nos indica el
número de notas que son
iguales a la query.
-El primer número nos
indica el número de notas
de la query.
-Nos aparecerán k lineas,
donde k es el número de
notas que podemos fallar.
Búsqueda con transposición invariante
Una opción de recuperación deseable es encontrar coincidencias que son
transposiciones de la consulta.
Estrategia de fuerza bruta
-Buscar todas las transposiciones posibles.
Como hay 128 alturas (pitch) diferentes en MIDI,
-Esta estrategia reduce el tiempo de eficiencia en un factor de 128 en el peor de
los casos.
Alternativa
-Se puede utilizar un procedimiento más eficaz basado en la técnica del resto chino.
-Uso de aritmética modular.
-En lugar de un índice se utilizan tres.