Software para la detección de anuncios en radio

Equation Chapter 1 Section 1 Proyecto Fin de Carrera Ingeniería de Telecomunicación Software para la Detección de Anuncios en Radio Autor: Alejandro Rubio Rey Tutor: José Ramón Cerquides Bueno Dpto. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 iii Proyecto Fin de Carrera Ingeniería de Telecomunicación Software para la Detección de Anuncios en Radio Autor: Alejandro Rubio Rey Tutor: José Ramón Cerquides Bueno Profesor titular Dpto. de Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 v Proyecto Fin de Carrera: Software para la Detección de Anuncios en Radio Autor: Alejandro Rubio Rey Tutor: José Ramón Cerquides Bueno El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2019 El Secretario del Tribunal vii A mi familia. ix Agradecimientos En primer lugar, me gustaría dar las gracias a mi familia por haber estado presente a lo largo de estos años y haber sido un pilar imprescindible durante este camino. Estos años de estudio no habrían sido lo mismo sin mis amigos del grado, grandes compañeros con los que he podido compartir un sinfín de experiencias y que se han convertido en un apoyo de suma importancia tanto en lo académico como personal. También quiero dar las gracias a mis amigos de Ingeniería Civil, quienes también han estado presentes a lo largo de estos años y con los que he podido compartir una gran cantidad de momentos en la Escuela. Especial mención a todos aquellos que hicieron de mi experiencia en Brasil todo un hito, con los que tuve la oportunidad de explorar una cultura completamente nueva. Alejandro Rubio Rey Sevilla, 2019 Referencias 55 xvii ÍNDICE DE TABLAS Tabla 1 - Formatos de las pistas de audio 13 Tabla 2 - Base de datos 18 Tabla 3 - Número de hashes 26 Tabla 4 - Probabilidad de acierto mediante segmentación 37 Tabla 5 - Probabilidad de acierto mediante grabación 37 Tabla 6 - Probabilidad de acierto con solapamiento (10 segundos) 38 Tabla 7 - Probabilidad de acierto con solapamiento (5 segundos) 39 Tabla 8 - Probabilidad de acierto con solapamiento (3 segundos) 39 xix ÍNDICE DE FIGURAS Figura 1 - Espectrograma de un diálogo [5] 6 Figura 2 - Espectrograma de un diálogo con ruido de fondo [5] 6 Figura 3 – Espectrograma de diálogo con picos representados [5] 7 Figura 4 – Espectrograma de diálogo con ruido de fondo con picos representados [5] 7 Figura 5 - Pares de picos usados para las huellas acústicas digitales [5] 8 Figura 6 - Correspondencias entre sub-fingerprints, fingerprint-blocks y fingerprints. (3) 9 Figura 7 - Esquema general del algoritmo [3] 10 Figura 8 - Espectrograma de la señal [13] 11 Figura 9 - Fingerprint o huella acústica binaria [13] 11 Figura 10 - Filtrado a través de frecuencias [13] 12 Figura 11 - Filtrado a través de frecuencias [13] 12 Figura 12 - Histograma de Intrasonics [13] 13 Figura 13 - Captura de WavePad 18 Figura 14 - Resultado en tiempo de la ejecución 26 Figura 15 - Resultado identificación anuncio 30 Figura 16 - Resultado identificación con truncamiento 31 Figura 17 - Resultado identificación con truncamiento 31 Figura 18 - Resultado identificación con ganancia 32 Figura 19 - Resultado identificación con ganancia 32 Figura 20 - Resultado identificación con ganancia y truncamiento 33 Figura 21 - Resultado aplicar filtro LP 33 Figura 22 - Resultado grabación 10 segundos y cambio de formato 34 Figura 23 - Resultado grabación 7 segundos 34 Figura 24 - Resultado grabación de 4 segundos 35 Figura 25 - Resultado grabación durante transición de anuncios 35 Figura 26 - Resultado grabación durante transición de dos anuncios. 35 Figura 27 - Resultado grabación con solapamiento 35 Figura 28 - Tiempo de carga de la base de datos 36 Figura 29 - Gráfica de dispersión del tiempo de la base de datos en comparación con el tiempo de muestreo para una pista que no coincide con la muestra [19] 45 Figura 30 - Gráfica con número significativo de pares coincidentes en la línea diagonal [30] 45 Figura 31 - Histograma de los valores δtk de la Figura 9 [30] 45 Figura 32 - Histograma de los valores δtk de la Figura 10 [30] 46 Figura 33 - Rango de reconocimiento - Ruido aditivo [30] 47 Figura 34 - Rango de reconocimiento – Ruido aditivo y compresión GSM [30] 48 Figura 35 - Esquema de inserción de marca de agua [35] 49 Figura 36 - Diagrama de bloques de la identificación [35] 50 Figura 37 - Correlación cruzada [35] 51 xxi Notación A* Conjugado c.t.p. En casi todos los puntos c.q.d. Como queríamos demostrar ∎ Como queríamos demostrar e.o.c. En cualquier otro caso e número e IRe Parte real IIm Parte imaginaria sen Función seno tg Función tangente arctg Función arco tangente sen Función seno sinxy Función seno de x elevado a y cosxy Función coseno de x elevado a y Sa Función sampling sgn Función signo rect Función rectángulo Sinc Función sinc ∂y ∂x x◦ Derivada parcial de y respecto Notación de grado, x grados. Pr(A) Probabilidad del suceso A SNR Signal-to-noise ratio MSE Minimum square error : Tal que < Menor o igual > Mayor o igual \ Backslash ⇔ Si y sólo si 1 1 INTRODUCCIÓN Y OBJETIVOS tendiendo a los datos ofrecidos por la Asociación para la Investigación de Medios de Comunicación (AIMC) a través del Marco General de los Medios en España publicado este 2019, en España se consiguió una audiencia acumulada diaria de 22,930.000 durante 2018. Esto lo convierte en uno de los medios de comunicación más importantes del país gracias a su penetración del 57,5% sobre la población mayor de 14 años, tan solo superado por la televisión (85%) e internet (77,9%). Aún así, esos 98,8 minutos de escucha diaria estipulados por la AIMC convierten la radiofórmula en un escaparate irresistible para la promoción por parte de las grandes -y no tan grandesempresas. [1] Los anuncios publicitarios suponen una importante fuente de ingresos para los medios de comunicación y, dado a que la audiencia y el target varían con respecto a la hora y cadena de emisión del anuncio, también lo hará el contrato publicitario acordado con el medio. Las empresas realizan fuertes inversiones en cuanto a publicidad radiofónica de manera diaria pues, una cuña de 20 segundos en una Cadena Ser Sevilla un sábado de 23:00 a 1:00 asciende a 387,99€. La empresa que quiera anunciarse de manera nacional en Cadena Cope un día entre semana de 6:00 a 10:00 deberá abonar 11.005,93€ por una cuña publicitaria de 20 segundos. [2] Es aquí donde nace la aplicación que sirve como proyecto y que se expondrá en esta memoria: un programa capaz de detectar e identificar los anuncios que toman lugar en la radio y que, a través de una serie de algoritmos y una base de datos obtenida mediante una señal en streaming, conseguirá extraer las características de los ficheros a través de la técnica audio fingerprinting y realizar una comprobación para saber si ese anuncio se encuentra o no dentro de la base de datos creada inicialmente. Una aplicación como esta puede llegar a tener una gran serie de ventajas tanto para el cliente como para la empresa. Con un mero contador, podríamos llegar a saber si los anuncios han sido emitidos a la hora establecida, si el anuncio ha sido acortado o se ha reproducido de manera íntegra, el número de veces que este ha sido emitido a lo largo de un periodo de tiempo o el entorno en el que este ha sido emitido. A lo largo de esta memoria, se establecerán los conceptos a conocer para el entendimiento óptimo del programa, se explicará de manera larga y tendida cómo se ha llevado a cabo la mejora del algoritmo del cual se ha partido inicialmente y se expondrán los resultados obtenido tras la ejecución de este. A “Para crear, uno debe primero cuestionarlo todo” - Eileen Gray - Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 2 Dado a los avances tecnológicos vividos en la última década, este proyecto prescindirá de la captura de la señal de radio a través de una tarjeta capturadora FM utilizando de manera directa la señal streaming ofrecida por la emisora a estudiar, disponible gracias a su portal web y que además facilitará el manejo de la entrada al ser directamente digital y no haber tenido que sufrir ningún tipo de conversión. El desarrollo del algoritmo se ha realizado a través de MATLAB. Este se encargará de extraer las características más relevantes de la señal de entrada y de generar una “huella” distintiva que la diferenciará de todas aquellas presentes en la base de datos. Es aquí cuando se comparará el audio fingerprinting de la señal de entrada con las “huellas” almacenadas previamente, extrayendo un valor de similitud que, si se muestra por encima de un valor previamente marcado, provocará la detección e identificación del anuncio de manera exitosa. El principal motivo por el que se establece este valor es que las señales pueden haber sido afectadas por agentes externos tales como el ruido de fondo si la captura no es directa e inmediata, la compresión y descompresión del propio archivo o la frecuencia a la que se ha muestreado de la señal. Para establecer este valor se han realizado una serie de comprobaciones estudiando su eficacia, habiendo adherido a la señal de entrada algunas de las variaciones ya numeradas y analizando el comportamiento del algoritmo para aportar validez a la detección e identificación o no. Esto se verá de manera detallada en su respectivo capítulo. Grosso modo, la aplicación deberá cumplir con los siguientes requisitos: • Eficiencia: El programa está planteado para que la obtención de resultado sea lo mejor posible y que computacionalmente no surjan adversidades que se vean reflejadas en la obtención de resultados. Esto además repercute en la cantidad de anuncios y la rapidez con la que podría identificar los anuncios. • Sencillez de uso: El programa diseñado está ideado para que el usuario -o la empresa para comprobar el correcto comportamiento de sus anunciospueda usarlo de manera sencilla. Además, una de las mejoras que se han aportado en esta nueva versión del trabajo está relacionada con su portabilidad: dado a que se prescinde de la tarjeta capturadora FM, no necesitamos más hardware que nuestro ordenador para poder hacer uso del algoritmo sin complementos externos. • Funcionamiento en tiempo real: Es una de las grandes ventajas que ofrece este algoritmo, ya que es capaz de funcionar con inmediatez y ofrecer los resultados de manera momentánea. [3] Por último, resulta de suma importancia comentar la estructura que seguirá este proyecto, pues ha sido dividido en diferentes bloques para que su comprensión sea lo mejor posible. Para ello, se ha comenzado definiendo los objetivos de este. Seguidamente, en el segundo bloque, se explicará de manera detallada cada uno de los conceptos y técnicas que serán utilizadas para comprender de manera exacta el funcionamiento del programa. Es en el tercer bloque de este proyecto, en el cual se analiza el código utilizado para la detección e identificación de los anuncios emitidos en la radiofórmula, donde se detallará la jerarquía de los múltiples ficheros que componen este trabajo para entender las funcionalidades de estos y cómo se complementan y se analizarán de manera independiente todas y cada una de las funciones que forman el cuerpo de este proyecto. A continuación, en el cuarto apartado de este trabajo, se realizará la fase de testeo, donde se notificará la importancia de dotar ciertas variables con unos valores específicos para optimizar al máximo el código utilizado. Se ejemplificará a través de gráficas cómo variarán los resultados obtenidos cuando nuestras señales de audio sufren modificaciones como la inserción de ruido o un cambio en su tonalidad. En el penúltimo bloque se expondrá el paralelismo que existe entre este algoritmo y otros usados de manera diaria por gran parte de los usuarios de teléfonos móviles melómanos: Shazam. Además, se expondrán las múltiples posibilidades que ofrece una técnica como el audio fingerprinting como la detección de contenidos con derechos de autor o copyright. Por último, en el sexto bloque de este proyecto, se obtendrán las conclusiones y reflexiones finales relativas al algoritmo y a los resultados obtenidos gracias a este. 3 3 Software para la Detección de Anuncios en Radio Además, el proyecto incluye una serie de anexos en el cual se encuentra el código utilizado para la ejecución de esta aplicación, así como todas las referencias que se han tomado para la elaboración del escrito o las distintas figuras usadas para ilustrar de manera detallada el funcionamiento de alguna técnica e incluso del propio algoritmo. Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 10 - Hash: Es aquel identificador único proporcionado a un valor, concretamente a una pareja creada mediante el landmark y el anchor point. - Target region: Es aquella región o zona de búsqueda de landmark próxima al anchor point. - Anchor point: Conocido también como el punto de anclaje, se corresponde con aquel punto sobre el que se buscan los landmarks para emparejarlos. - Espectrograma: Es la representación de la señal de audio que se realizará en dominio tiempo-frecuencia. Para concluir con este bloque, mostramos un esquema genérico del funcionamiento de este algoritmo. Figura 7 - Esquema general del algoritmo [3] 2.3. Otras técnicas. 2.3.1. Philips Cuando Shazam era lanzado a principios de siglo, el departamento de investigación de audio de Philips presentó otro método de toma de fingerprints. Estas técnicas presentan diferencias notables entre ellas, tal y como se verá más detalladamente en el quinto capítulo de esta memoria. Mientras que el algoritmo de Shazam 11 Software para la Detección de Anuncios en Radio representa selectivamente las partes del espectrograma que considera más importantes, el algoritmo de Philips gira en torno a la compresión del espectrograma completo en la medida de lo posible. Grosso modo, el algoritmo de Philips busca cambios en el tiempo y la frecuencia. [11] Figura 8 - Espectrograma de la señal [13] En la figura sobre estas líneas se muestran los cambios en el espectrograma de "Back to Black" (es decir, comparado con el espectrograma original). Por ende, esta técnica pone especial énfasis en los picos de alta frecuencia y menos en los picos de baja frecuencia, ya que no cambian tan rápidamente. [12] La figura resultante será una huella acústica binaria que tan solo almacenará los cambios que son mayores a un umbral, tal y como se puede ver a continuación: Figura 9 - Fingerprint o huella acústica binaria [13] Aunque la figura anterior no parezca muy útil, codifica una gran cantidad de información esencial que es fácilmente analizada y comparada por un ordenador. Esto muestra algunas diferencias clave entre este algoritmo y el de Shazam: el algoritmo de Philips es mucho más resistente a una alta cantidad momentánea de ruido o a un desplazamiento de los picos, ya que no existe ninguna preferencia por ninguna sección del espectrograma en particular. Sin embargo, es menos resistente al ruido continuo. [13] 2.3.2. Intrasonics. Intrasonics ha investigado una solución que intenta encontrar un punto medio entre la idea original de Philips y Shazam. Mientras estas dos técnicas mencionadas deciden qué parte del espectrograma consideran más importante, el algoritmo de Intrasonics aprovecha las técnicas modernas de aprendizaje por máquina para seleccionar las mejores características del espectrograma. Para ello, el algoritmo de Intrasonics entra primero Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 12 en una fase que se podría considerar una “fase de entrenamiento”, en la que el espectrograma se filtra por una serie de filtros posibles a diferentes frecuencias, algunos de los cuales se ilustran a continuación. [14] Figura 10 - Filtrado a través de frecuencias [13] Figura 11 - Filtrado a través de frecuencias [13] La forma del filtro refleja aproximadamente la característica que el filtro busca. Durante la fase de entrenamiento, se aplican más de 10.000 filtros al espectrograma y se recogen todos los resultados. Estos resultados son analizados por el ordenador para aprender qué características son las más características del audio. 13 Software para la Detección de Anuncios en Radio Figura 12 - Histograma de Intrasonics [13] La imagen sobre estas líneas muestra lo que el ordenador está buscando. Si una característica es muy distintiva, se verá muy diferente para distintos segmentos de audio (representado mediante el color azul) mientras que se verá muy similar para segmentos de audio similares (representado en rojo). Se buscan características que separan los puntos de datos rojos y azules tanto como sea posible, y selecciona los mejores filtros de entre los candidatos a filtro. Una vez que se selecciona un conjunto de filtros que funcionan bien juntos, se completa la fase de formación. Los filtros seleccionados se utilizan para extraer las características del espectrograma que nos ayudan a identificar el mejor audio. La ventaja de esta técnica es que el sistema no depende de lo que se cree que pueden llegar a ser características distintivas del espectrograma, sino de las características que se ha demostrado que lo son. Además, al añadir ruido se puede entrenar al sistema para que ignore ruidos similares en el futuro. El sistema puede ser fácilmente modificado para casos de uso específicos si así se desea. Estas son las ventajas típicas del uso de la máquina de aprendizaje para ayudar a la extracción de características. [13] Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 14 11 3 DESARROLLO DEL ALGORITMO n este bloque se van a analizar todos los ficheros usados para la creación del algoritmo. Se establecerá la jerarquía que siguen estos, resaltando la dependencia que sufren las funciones creadas unas con otras. Seguidamente, se desarrollarán todos y cada uno de los ficheros con sus respectivas funciones para entender correctamente cómo se ejecuta la técnica del audio fingerprinting y qué otras técnicas debemos utilizar para que el algoritmo de este proyecto se ejecute de manera satisfactoria. También se hablará de la creación de la base de datos en su respectivo apartado. Además, es en este bloque -durante la explicación del desarrollo del códigodonde serán comentados algunos de los parámetros y valores tomados para el correcto funcionamiento del algoritmo. Será en el capítulo siguiente, dedicado a la fase de testeo, donde se valorará cómo cambiará el funcionamiento de este algoritmo dependiendo de cómo sean inicializadas sus variables. 3.1 Desarrollo de los archivos utilizados Para lograr la detección e identificación de los anuncios de radio se han necesitado nueve archivos de código de extensión “.m”. Todos ellos se complementan entre sí, facilitando el uso de funciones y quedando de manera ordenada por si se desean hacer modificaciones de manera futura. Estas rutinas implementan un sistema basado en los landmarks encontrados a través del audio fingerprinting estando lo suficientemente dotado para lograr la detección en aquellos ficheros de audio que hayan sido afectados debido a su compresión o el ruido. Se basa en la idea de la aplicación Shazam, un servicio de detección de canciones a través de coincidencias entre un fichero de entrada y una base de datos previamente generada. A pesar de que esta aplicación está destinada al reconocimiento de canciones, este algoritmo funcionaría con todo aquello que se componga de pistas de audio, como es el caso de la detección e identificación de los anuncios de radio. La idea fundamental será ser capaz de reconocer una pista a través de un fragmento de esta. Tal y como ocurre en Shazam, está preparada para buscar la coincidencia de una canción a través de un audio grabado desde un teléfono móvil, lo que implica la suma de ciertos factores externos que harán que la pista de audio no sea idéntica. Es aquí donde la reside la mayor complicación de este algoritmo y la utilización del audio fingerprinting para obtener la mayor eficacia. E “La tecnología es una palabra que describe algo que no funciona todavía” - Douglas Adams - Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 12 Cada pista de audio estará descrita por sus landmarks, que podrán llegar a contabilizarse en cientos, y los tiempos en los que estos ocurren. Para identificar una consulta, se pregunta a la base de datos para que encuentre todas aquellas pistas con las que comparte landmarks y las diferencias en tiempo relativo cuando ocurre en la pista de audio de la base de datos y en la pista con la que realizamos la consulta. Cuando se han identificado un número suficiente landmarks que coincidan y con el mismo tiempo relativo, podemos considerar que es un match: es decir, que el anuncio de radio es el mismo. Normalmente, un pequeño número de coincidencias (por ejemplo, 5) es suficiente para considerar que la pista de audio es la misma, ya que la probabilidad de que exista coincidencias entre dos pistas completamente diferentes son prácticamente nulas. El enfoque es, básicamente, que tan solo algunos de los máximos tienen que ser los mismos. Si el ejemplo de consulta es ruidoso o ha sido filtrado de algún modo que ha modificado la señal o ha sido truncado, aún existen altas posibilidades de que muchos de los puntos de referencia de la señal sigan intactos pudiendo ser reconocidos y, por ende, seguir obteniendo la coincidencia entre ambas pistas. [7] [15] Se dividirán los ficheros en dos bloques en función de la tarea que realicen. En primer lugar, todos aquellos orientados a la creación de la base de datos. En segundo lugar, aquellos que se usarán para la correcta identificación del anuncio con el que se realiza la consulta. 3.1.1 Ficheros utilizados para la creación de la base de datos. 3.1.1.1 Fichero test_bbdd.m Es el fichero principal para llevar a cabo la creación de la base de datos. A diferencia del resto de ficheros que serán analizados a continuación, este no posee ninguna función. Se basa solamente en la llamada a las funciones create_database y add_tracks. En “test_bbdd.m” se crea la base de datos y se indica en que archivo se encuentra la información de los anuncios a leer. En este proyecto se trata de “anuncios.txt”. Con esos parámetros se llama a la función add_tracks, función encargada de leer los ficheros, extraer sus huellas acústicas digitales identificativas y añadirlas a la base de datos. Cuando este paso sea concluido, tan solo se necesitaría usar la función match_query para realizar las pruebas de coincidencia. 3.1.1.2 Fichero create_database.m Este fichero contiene la función create_database, encargada de la creación de un map en el cual almacenar los hashes. Se debe resaltar que este mapa creado, ‘d’, será tipo uint32 y de “ValueType = any”, es decir, válido para cualquier tipo de valor. 3.1.1.3 Fichero add_tracks.m Este fichero contiene la función add_tracks, la cual analiza los anuncios y almacena los hashes en la base de datos. Esta función lee el fichero que contiene las grabaciones de los anuncios que se quiere almacenar en la base de datos ‘d’, las procesa y las almacena. El fichero de lectura debe tener un formato que sea una fila por anuncio. En cada fila se escribirá la ubicación del fichero a leer, su nombre, la categoría en la que será almacenada y la identifica, el día de emisión y una portada que identificará la grabación con el fin de obtener un resultado más visual. Esta información irá separada por '---' y se debe saber que no admite espacios. 13 Software para la Detección de Anuncios en Radio Anuncios/juliaenlaonda01.wav---JuliaEnLaOnda---Programa---30/08/2019- --Imagenes/juliaenlaonda.jpg Su salida seguirá esta estructura: [#anuncio, 5], conteniendo toda la información de cada uno de los anuncios. Su funcionamiento es sencillo: se crea la variable detalles con los anuncios que formarán nuestra base de datos, se lee el dichero y se toma toda la información. Seguidamente, se procesan los anuncios y se realiza una conversión monocanal con el fin de que las pistas de audio no estén divididas. Esto se hará con una frecuencia de 8KHz. A continuación, se encontrarán los landmarks y se almacenarán los hashes en la base de datos a través de las funciones landmark2hash y record_hashes, explicadas más adelante. Para saber que la ejecución de este programa está siendo realizada con éxito, se mostrará en el terminal “Anuncio leído correctamente” y se expondrá el número de hashes obtenidos por anuncio mediante la longitud de la matriz ‘H’ en la que están siendo almacenados los anuncios. Cada vez que se muestren los hashes de cada anuncio, se liberará la memoria para poder almacenar el siguiente anuncio. También es necesario conocer el formato de la pista de audio que leyendo para conocer el muestreo que se realiza. Usando los comandos de ayuda de Matlab obtenemos la siguiente información. Tabla 1 - Formatos de las pistas de audio File Format BitsPerSample Data Type of Y Data Range of Y WAVE (.wav) 8 uint8 0 Y 255 16 int16 -32768 Y 32767 24 int32 Y 32 int32 Y 32 single -1.0 Y +1.0 FLAC (.flac) 6 uint8 0 Y 255 16 int16 -32768 Y 32767 24 int32 Y MP3 (.mp3) MPEG-4 (.m4a, .mp4) OGG (.ogg) N/A single -1.0 Y +1.0 La función audioread será utilizada numerosas veces para este algoritmo de detección e identificación de anuncios de radio, ya que se trabaja exclusivamente sobre pistas de audio. 3.1.1.4 Fichero find_landmarks.m Este fichero contiene la función find_landmarks, encargada de emparejar los máximos y de obtener las huellas acústicas de identidad de los anuncios. Esta función toma los datos del anuncio sampleado (8KHz) y los representa en un espectrograma, seleccionando los máximos representados y emparejándolos entre ellos. Las parejas pueden ser usadas como Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 14 huella acústica digital identificativa si se almacenan correctamente. Los argumentos de entrada de esta función son los siguientes: - anuncio_data: array que contiene los valores del anuncio cuyos máximos se quieren emparejas. Solo puede tener una columna. - dilate_size: tamaño del elemento estructurador utilizado en el paso de dilatación. Debe ser un array bidimensional, ya que se está usando uno rectangular. Las salidas son las siguientes: - L: matriz que contiene los landmarks obtenidos. Su tamaño será [#hashes, 4]. Cada fila de ‘L’ está formada por [start_time, start_freq, freq_diff, time_diff] - S: es el espectrograma preprocesado. - maxes: matriz que contiene la posición de los máximos en el espectrograma. La primera columna indica la fila. La segunda, la columna. Primero de todo, inicializamos los parámetros que usaremos en el espectrograma. En este proyecto, todos los anuncios serán muestreados a 8 KHz. Además, se debe abarcar un tamaño de ventana lo suficientemente grande para abarcar los 64 milisegundos de la señal (se escogerá 0.064). También se escogerá un valor de solapamiento del 50%. Seguidamente, se llevará a cabo el preprocesado del espectrograma para que sea más cómodo trabajar con él. Se eliminarán los picos pequeños -ya que no aportarán información relevante para adquirir los landmarks- y se filtrará. Existen una serie de factores que afectan al número de landmarks encontrados y devueltos por la función: a. El número de máximos locales encontrados, los cuales también sufren una dependencia con respecto a: i. El ancho de separación aplicado a la máscara para cada uno de los picos encontrados. Un mayor valor implicará encontrar menos picos en la señal, obstaculizando el proceso de identificación. Para ello, se establecerá un valor igual a 30. ii. El descenso del valor de la máscara detrás de cada pico (proporcional al tamaño). Valores cercanos a ‘1’ implicarán un número menor de picos encontrados. Por ello, se establecerá un valor de 0,99. iii. El número de picos máximos para cada frame. En la fase de testeo se podrá comprobar que rara vez se alcanza, ya que gran parte de los picos caen por debajo de la máscara. Por tanto, se ha establecido un valor igual a 5 para el número máximo de picos por frame. iv. El filtro HP aplicado, que es parametrizado por la posición del polo real. Un polo cercano a +1 conseguirá eliminar aquellas partes que varían lentamente. Sin embargo, un polo ubicado en -1 enfatizará aquellas variaciones que ocurren con rapidez, lo cual conlleva al encuentro de más picos inicialmente. Por ello, se ha establecido un valor igual a 0.98. b. El número de parejas para cada uno de los picos. Cuanto mayor sea el tamaño de la zona que fijemos como objetivo, mayor será el número de máximos que encontraremos. Esta zona, llamada “target region” será delimitada a través de una frecuencia -será 31-, y una duración máxima -63-. A continuación, se llevará a cabo la búsqueda de los máximos. Para realizar esto se tomará la “dilatación” del espectrograma y después se buscarán los puntos cuyo valor es el mismo tanto en el “pre-dilatado” por en el espectrograma procesado. Se creará el elemento estructurador, teniendo en cuenta la importancia de probar distintas formas para ver cuál de ellas aporta el mejor resultado. La rectangular ofrece un resultado bastante bueno con un tamaño aproximado de [30,30]. Seguidamente se obtienen las coordenadas donde los valores coinciden y se toma su valor temporal y frecuencia. Por último, una vez obtenidos los máximos, estos deben ser emparejados. Se quieren obtener aquellas parejas cuya diferencia temporal es menor de 64 columnas (alrededor de los 2 segundos) y aquellas diferencia que 15 Software para la Detección de Anuncios en Radio difieren en menos de 32 (500 Hz). A parte, si para un máximo se encuentran más de tres parejas, se almacenarán tan solo las tres más próximos en tiempo. Estos datos serán almacenados en la matriz ‘L’, en la cual se usará una fila por cada pareja y cuya estructura es la siguiente. LFILA = [initialTime, initialFreq, finalFreq-initialFreq, finalTimeinitialTime] Almacenadas las tres parejas en cada punto, la longitud máxima que ‘L’ puede adquirir es 3*#maximos. Para cada máximo encontrado, se buscarán aquellas frecuencias que no sean mayores de 500 Hz o 2,048 segundos con respecto a la posición. En caso de que se encuentren más de tres que cumplan estos requisitos, tan solo se almacenarán las tres más cercanas. Solo serán devueltas aquellas filas de ‘L’ que contengan una pareja y se eliminarán aquellas que se han creado con ceros al principio de este bloque pero que no han sido usadas. 3.1.1.5 Fichero landmark2hash.m Este fichero contiene la función landmark2hash, encargada de la conversión de los landmarks en un hash de 20 bits. Esta función toma cada landmark encontrado con la función find_landmarks y devuelve una matriz ‘H’ con los hashes de cada uno, añadiendo la información necesaria para saber a qué anuncio pertenece y el instante temporal en el que aparece. Cada landmark será comprimido en un hash en el cual se almacenará la frecuencia del primer máximo del landmark y el tiempo y la frecuencia que existe entre las parejas usando 8 bits como frecuencia inicial y 6 bits por cada diferencia. Además, se terminará con un bloque de 20 bits. ‘H’ es una matriz con tamaño [length(L),3], cuyas columnas tienen la siguiente estructura: Hfila = [id_anuncio, uint32(initialTime), hashed_landmark] ‘L’ es la matriz de landmarks obtenida con find_landmarks. La variable id_anuncio es el identificador del anuncio que está siendo analizado. Debe ser un entero menor a 215. Esta función se ejecuta de la siguiente manera: en primer lugar, se realiza una reserva de memoria para ‘H’, por lo que se puede operar sin que se pierdan sus propiedades cuando se entre en el bucle. A continuación, se crea el hash y se almacena en una fila de ‘H’ con todos los valores que se necesiten. 3.1.1.6 Fichero record_hashes.m Esta función posee la función record_hashes, encargada del almacenamiento de los hashes en la base de datos. La función obtiene la matriz ‘H’ con el formato ofrecido por la función landmark2hash y la base de datos ‘d’. Esta almacenará la información que los hashes contienen en la base de dato, creando nuevas entradas para los hashes que aún no han aparecido y editando los ya existentes para aquellos que han sido encontrados en anuncios previos. Se trata de realizar la lectura, concatenarlos y finalmente almacenarlos. 3.1.2 Ficheros utilizados para las pruebas de identificación Como las funciones find_landmarks y landmark2hash ya han sido explicadas de manera previa, no serán analizadas nuevamente. Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 22 1 Mercaoficina 3:08:08 3:08:13 6s 1,2 MB 1 Atresmedia + ONG 3:08:14 3:08:43 30s 5,7 MB 1 La Brújula 3:08:44 3:09:36 53s 10,2 MB 1 Julia en la Onda 3:09:37 3:40:12 30min 36s 352,5 MB 1 El Corte Inglés 3:40:13 3:40:34 22s 4,2 MB 1 Pequeñas Coincidencias 3:40:35 3:40:57 23s 4,4 MB 1 Securitas Direct 3:40:58 3:41:23 26s 5 MB 1 Mutua 3:41:24 3:41:43 20s 3,9 MB 1 Pequeñas Coincidencias 3:41:44 3:42:07 24s 4,6 MB 1 Día 3:42:08 3:42:26 19s 3,7 MB 1 Clínica Baviera 3:42:27 3:42:48 22s 4,3 MB 1 Onda Cero Madrid 3:42:49 3:42:51 3s 537 KB 1 Media Markt 3:42:52 3:43:05 14s 2,7 MB 1 BMW Madrid 3:43:06 3:43:30 25s 4,8 MB 1 Muebles Adama 3:43:31 3:43:52 22s 4,2 MB 1 Bricolaje Moraleja 3:43:53 3:44:12 20s 3,8 MB 1 Invermax 3:44:13 3:44:38 26s 5 MB 1 Bricolaje Moraleja 3:44:39 3:44:58 20s 3,9 MB 1 Onda Cero y Alexa 3:44:59 3:45:37 39s 7,5 MB 1 Onda Cero Madrid 3:45:38 3:45:51 14s 2,7 MB 1 Julia en la Onda 3:45:52 3:54:31 8min 40s 99,8 MB En amarillo, el programa radiofónico de “Julia en la Onda”. En azul, cabeceras y entradillas. En verde, publicidad de la cadena. 23 Software para la Detección de Anuncios en Radio Todos los ficheros han sido utilizados en formato “.wav”. Para incluirlos en la base de datos, tal y como se comentaba en el código, se ha creado un fichero llamado “anuncios.txt” en el cual se crea a modo de tabla la base de datos con todas las características de cada uno de los anuncios. En esta se incluye la ruta, el nombre del anuncio, la categoría (anuncio, programa o cabecera), la fecha de la emisión y una portada. Este fichero se ha realizado a través del editor Sublime Text [18]. Además, es importante resaltar que la función de MATLAB imshow presenta problemas a la hora de mostrar imágenes superiores a 1000x1000 píxeles. Por ello, se ha hecho un reajuste de cada una de las portadas o logos mediante la función de escalado presente en el editor de Mac Vista Previa. La base de datos, sin embargo, no se ha hecho con todos los ficheros tomados a lo largo de estas cuatro horas. Como mucho de los anuncios se repiten, se han eliminado las copias idénticas de Adelgar (1), Clínica Baviera (1), Cofidís (2), El Hormiguero (1), KIA (1), la Brújula (1), Leroy Merlín (1), MediaMarkt (1), Onda Cero y Alexa (1), Pequeñas Coincidencias (3), Securitas Direct (1), Speedy (1) y Vuelta a Casa (2). Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 24 25 Software para la Detección de Anuncios en Radio 4 FASE DE TESTEO n este capítulo se va a describir el comportamiento del algoritmo ante distintas pruebas a las que va a ser sometido. Se comprobará cómo responde el programa creado ante la presencia de ruido de fondo, el truncamiento, el número de hashes obtenidos para cada uno de los anuncios o se propondrán situaciones extremas para ver cómo de efectivo puede llegar a ser. Este bloque es, quizás, el más importante de este proyecto. Es por ello por lo que lo dividiremos también en distintos apartados que estarán enfocados a cada una de las partes en las que se ha dividido este proyecto de manera teórica. Se comprobará en primer lugar la eficacia y la rapidez con la que se crea la base de datos. A continuación, se modificarán los ficheros de prueba y se analizará el comportamiento del algoritmo ante distintas situaciones no ideales. 4.1 Base de datos Como se explicaba en la parte teórica de este proyecto, para la creación de la base de dato tan solo se tendrá que ejecutar el fichero "test_bbdd.m". MATLAB ofrece la opción de ejecutar y temporizar. Este ha sido el resultado: E “Life is essentially an endless series of problems. The solution to one problem is merely the creation of another.” - Mark Manson - Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 26 Figura 14 - Resultado en tiempo de la ejecución La ejecución de ““test_bbdd.m”” ha tenido una duración de 86,298 segundos. Tal y como se puede ver, 86 ficheros de audio han sido analizados atendiendo al número de veces que funciones como audioread o find_landmarks has sido llamadas. En pantalla se muestra el número de hashes encontrados por archivo de audio, recopilado en esta tabla: Tabla 3 - Número de hashes Nº Anuncio Nombre Número de hashes 1 Julia en la Onda 26781 2 Mutua 363 27 Software para la Detección de Anuncios en Radio 3 ING Direct 488 4 Pequeñas Coincidencias 471 5 Hipercor 417 6 Vodafone 624 7 Carrefour 293 8 Movistar 351 9 Automatic 408 10 Intocable 344 11 Montes de Galicia 404 12 Duchamanía 533 13 La Brújula 1027 14 La Vuelta 728 15 Julia en la Onda 37587 16 Más de Uno 720 17 Cofidís 405 18 El Hormiguero 3.0 218 19 Cofidís 162 20 ING Direct 505 21 Línea Directa 263 22 Leroy Merlin 266 23 Clínica Baviera 366 24 Onda Cero Madrid 35 25 Speedy 353 26 Maternatal 459 27 RealVisión 342 28 Somnium 168 29 Mirador de Mayorazgo 486 30 La Fuerza del Cariño 252 Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 28 31 El Transistor 959 32 Onda Cero (RRSS) 366 33 Julia en la Onda 14907 34 Volkswagen 510 35 Hipercor 347 36 Securitas Direct 514 37 Algemesí 952 38 KIA 657 39 Decorman 398 40 Adelgar 534 41 Decorman 398 42 CC Moda Shopping 415 43 Vuelta a Casa 1016 44 Onda Cero Madrid 132 45 Julia en la Onda 24927 46 Mutua 447 47 Rastreator 135 48 Mercedes Benz 678 49 Juntos 414 50 Electrocasión 196 51 Dirsa 369 52 Gilmar 403 53 Onda Cero Madrid 118 54 Julia en la Onda 4822 55 Boston Medical Group 384 56 Julia en la Onda 33748 57 ING Direct 426 58 Hijolusa 267 29 Software para la Detección de Anuncios en Radio 59 ONCE 532 60 Media Markt 284 61 Cómete Las Ventas 406 62 Rolex 320 63 Duchamanía 444 64 Onda Cero y Alexa 929 65 Onda Cero Madrid 199 66 Julia en la Onda 18467 67 AirEuropa 363 68 UEM 342 69 Alquiler Seguro 344 70 Julia en la Onda 5685 71 Los Nogales 367 72 Somnium 377 73 Mercaoficina 146 74 Atresmedia + ONG 592 75 Julia en la Onda 32443 76 El Corte Inglés 463 77 Mutua 323 78 Día 367 79 Onda Cero Madrid 22 80 BMW Madrid 472 81 Muebles Adama 404 82 Bricolaje Moraleja 402 83 Invermax 524 84 Bricolaje Moraleja 345 85 Onda Cero Madrid 233 86 Julia en la Onda 8327 Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 30 Tal y como se puede apreciar, el número de hashes por anuncio tiene cierta dependencia a la duración del corte de audio. Mientras que ficheros de audio como los de “Julia en la Onda” superan siempre los 5.000 hashes, los anuncios, que tienden a ser más o menos de 20 segundos, tienden a estar por valores cercanos a 500 hashes. Por último, recalcar el modo de ejecución de este algoritmo en dos partes. Debido al coste temporal que supone la creación de la tabla de datos, el hecho de poder ejecutar la identificación en un proceso completamente independiente facilitará poder trabajar con la base de datos ya cargada sin necesidad de volver a ejecutar “test_bbdd.m” 4.2 Identificación de anuncios A continuación, se abarcará la fase de testeo de identificación de anuncios. Para ello, se llevarán a cabo distintas pruebas con diferentes archivos. Se comenzará con el truncamiento, tomando los archivos locales segmentados. Seguidamente, se realizarán pruebas con cambios de formato, adicionando distintos tipos de ruido y lo que se podría denominar como “casos reales”: realizar una grabación del audio con un teléfono móvil con ruido de fondo: tráfico, conversaciones en segundo plano o música sonando. 4.2.1 Pruebas con truncamiento Se tomarán los ficheros “JuliaEnLaOnda01” de 14, 8, 5 y 3 segundos. Además, se tomarán otros anuncios como “Cofidís01” y “PequeñasCoincidencias01”. El programa muestra los resultados tal que así: Figura 15 - Resultado identificación anuncio Se puede ver que incluso con una muestra de 3 segundos, el algoritmo es capaz de reconocer el anuncio o programa al que pertenece: 31 Software para la Detección de Anuncios en Radio Figura 16 - Resultado identificación con truncamiento Lo mismo ocurriría con los anuncios previamente mencionados: Figura 17 - Resultado identificación con truncamiento 4.2.2 Pruebas modificando la ganacia A continuación, se modificará la ganancia de algunas de las pistas de audio que sirve de consulta. Con una ganancia de -9 dB, el algoritmo aún es capaz de identificar el anuncio correctamente, aunque cuando se escuche esté completamente distorsionado. Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 38 95,24% de probabilidad de positivo sigue siendo un dato excelente para la identificación de los anuncios en radio considerando el ruido de fondo existente en las grabaciones de audio tomadas. Seguidamente, será analizado estadísticamente el comportamiento del algoritmo frente a solapamiento entre anuncios. Para ello, la tabla será diferente, incluyendo el acierto de cada uno de los anuncios con un valor de coeficiente de tolerancia variable. Se estudiarán los resultados de 42 solapamientos de anuncios distintos también durante 10 segundos. Tabla 6 - Probabilidad de acierto con solapamiento (10 segundos) Tolerancia Acierto total Acierto parcial Fallo No detección Tasa de acierto de al menos un anuncio Tasa de acierto de ambos anuncios Tasa de acierto 1,5 6 35 1 0 97,62 % 14,28 % 55,95 % 2 9 32 1 0 97,62 % 21,42 % 59,52 % 4 21 20 1 0 97,62 % 50 % 73,81 % 10 30 11 1 0 97,62 % 71,42 % 84,52 % Atendiendo a los resultados obtenidos, cuanto mayor será el valor de la tolerancia, mayor será la probabilidad de acierto. Esta probabilidad se ha calculado a través del número de anuncios identificados correctamente. Se ha establecido 10 como valor máximo de la tolerancia ya que, a pesar de que aumentemos este valor, el algoritmo ha identificado la pista de consulta como un anuncio erróneo debido a la cantidad de hashes coincidentes. Para la creación de esta última prueba estadística se han combinado solapamientos de manera digital a través de un editor de audio y mediante grabaciones, tal y como se hizo anteriormente. A continuación se mostrará cuáles han sido los resultados del algoritmo habiendo segmentado este solapamiento en 5 y 3 segundos. 39 Software para la Detección de Anuncios en Radio Tabla 7 - Probabilidad de acierto con solapamiento (5 segundos) Tolerancia Acierto total Acierto parcial Fallo No detección Tasa de acierto de al menos un anuncio Tasa de acierto de ambos anuncios Tasa de acierto 1,5 2 37 3 0 92,86 % 4,76 % 48,81 % 2 5 34 3 0 92,86 % 11,90 % 52,38 % 4 11 28 3 0 92,86 % 26,19 % 59,52 % 10 15 24 3 0 92,86 % 35,71 % 64,29 % Tabla 8 - Probabilidad de acierto con solapamiento (3 segundos) Tolerancia Acierto total Acierto parcial Fallo No detección Tasa de acierto de al menos un anuncio Tasa de acierto de ambos anuncios Tasa de acierto 1,5 2 27 13 0 69,05 % 4,76 % 36,90 % 2 3 26 13 0 69,05 % 7,14 % 38,10 % 4 10 19 13 0 69,05 % 23,91 % 46,43 % 10 14 14 13 0 69,05 % 33,33 % 50 % En las tablas superiores se ve reflejado cómo cuanto menor es la duración del audio de consulta y menor es la tolerancia seleccionada, menor será la probabilidad de acierto. Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 40 5 OTRAS FUNCIONES DE LA TÉCNICA DEL AUDIO FINGERPRINTING n este apartado se estudiarán algunos de los casos más frecuentes para el uso de la técnica del audio fingerprinting. El primero de ellos, tal y como se narraba en la introducción de esta memoria, será un estudio exhaustivo del nacimiento y uso de esta técnica por parte de Shazam Entertainment desde principios del siglo: las razones por la que la empresa británica seleccionaron esta técnica, cómo la utilizan y los parámetros que seleccionan para la mayor efectividad. Se expondrá su evolución a lo largo de estas casi dos décadas y la revolución que supuso en cuanto a identificación de canciones, además de su impresionante repercusión, siendo integrada ya, por ejemplo, en todos los iPhone y demás dispositivos de la marca Apple con tan solo preguntar a Siri “¿qué está sonando?”. Seguidamente, también se analizará una técnica que tiende a confundirse con el audio fingerprinting: el watermarking. Este método de grabado de marca de agua es una de las técnicas más utilizadas en términos de derechos de autor, ya que servirá para detectar cuando un archivo ha sido plagiado o emitido sin el consentimiento de la empresa. 5.1 Algoritmo de Shazam Este proyecto comparte muchas de sus característica con Shazam, una aplicación móvil fundada a través de Shazam Entertainment. En el año 2000, la empresa comenzó el desarrollo de esta idea: ofrecer un servicio a un cliente con el cual poder conectarlos a la música a través del reconocimiento de canciones usando su teléfono móvil de manera directa. El algoritmo debía ser capaz de reconocer un fragmento pequeño de una pista de audio que estuviese siendo emitido por una fuente, considerando la fuerte cantidad de ruido que esta capturaría o la reverberación al ser capturado por un pequeño micrófono de un teléfono móvil, sometido a compresión de la codificación de la voz o la caída del servicio web, todo ello antes de llegar a los servidores de la empresa. Otra de las principales dificultades de este algoritmo era su base de datos: Shazam debía reconocer rápidamente la pista e identificarlo con las más de dos millones de canciones que se encontraban en la base de datos, además de tener un número bajo de falsos positivos mientras se selecciona un alto rango de reconocimiento. E “Ethics change with technology” - Larry Nevin - 41 Software para la Detección de Anuncios en Radio Para la empresa, cumplir con estos requisitos suponía un gran problema, pues ninguno de los algoritmos creados hasta el momento cumplía las características que requería este proyecto para alcanzar resultados óptimos. [19] Durante los primeros años de servicio, Shazam se instauró de manera exitosa en países como Alemania, Finlandia o Reino Unido con una base de datos de 1,8 millones de canciones y llegando a alcanzar el medio millón de usuarios. Años más adelante, estuvo disponible en otros países de Europa y Asia, así como en Estados Unidos. La experiencia que proponía la empresa era sencilla: un usuario escucha música siendo reproducida en cualquier tipo de situación, hace uso de Shazam y toma una captura de hasta 15 segundos. La identificación se efectúa en los servidores de la empresa, siendo enviado el nombre de la canción vía mensaje de texto. Shazam Entertainment también disponía de una página web donde el usuario podía registrarse e iniciar sesión para hacer uso de esta aplicación. A raíz de Shazam, muchas empresas comenzaron a crear aplicaciones con funcionalidades parecidas a las que ofrecía Shazam, pionera en detección e identificación de canciones. Fue el caso de la compañía española Amena, que mediante determinados teléfonos móviles de la marca Philips crearon un algoritmo de hashing similar al que proporciona la empresa británica. Este algoritmo utilizado será explicado en detalle más adelante [20] [21] [22]. Por otro lado, la empresa Neuros permitía que sus reproductores MP3 pudiesen pinchar la señal de una emisora de radio y grabar y almacenar 30 segundos de audio. Seguidamente, el usuario podía conectar el dispositivo a una ordenador y mediante un servidor online identificar la canción que había sido grabado. [23] [24] Tal y como se ha podido ver con el paso de los años, actualmente Shazam funciona a través de una aplicación disponible en todo el mundo y que es capaz de realizar su tarea de identificación en incluso dos segundos. Además, esta aplicación ha avanzado hasta el punto de mostrar detalles más específicos de la canción (vocalistas de la canción, productores musicales, discográfica…), vinculando los distintos servicios streaming donde se puede escuchar la canción, mostrando descubrimientos a raíz de las escuchas tomadas o la biblioteca musical existente en tu móvil. Aunque este proyecto esté explícitamente enfocado a la detección de anuncios en radio y su posterior identificación, se puede observar una gran similitud entre ambos algoritmos, pues tanto las canciones como los anuncios son pistas de audios y se trabajará con ellas de la misma manera. Es por eso por lo que el algoritmo de Shazam ofrece tantísimas posibilidades más allá del reconocimiento de una canción. En primer lugar, por su habilidad relativa a tratar audios con un alto componente de ruido y poder detectar la pista principal de manera correcta. Además, este algoritmo opera de manera rápida y puede ser usado para asuntos relacionados con los derechos de autor con efectividad, pues es capaz de ejecutarse 1000 veces más rápido que de manera manual. Por último, anotar que este algoritmo permite su modificación para implementar su base de datos. Es de suma importancia conocer su principio básico de operación, tema que será desarrollado en profundidad pues será también utilizado en nuestro proyecto para la creación del algoritmo de detección e identificación de anuncios de radio. 5.1.1 Principios básicos del algoritmo El algoritmo parte de la idea de buscar la huella acústica digital de cada uno de los ficheros de audios con los que se opera. Esta huella se conoce como fingerprint, pues al igual que ocurre con la huella dactilar de las personas, sirve como código infalible para la identificación. Este proceso se aplicará tanto a la señal de audio de consulta como a aquellas que tomen lugar en la base de datos. Los fingerprints del audio no identificado serán relacionados debido a su similitud con un conjunto de fingerprints extraídos de la base de datos. Además, las pistas seleccionadas de la BBDD serán analizadas en modo de secuencia para estudiar que el caso de identificación es correcto. Algunos requisitos o principios para que los atributos puedan ser utilizados por audio fingerprint es que deberían estar localizados temporalmente, deben ser invariantes en el tiempo y suficientemente entrópicos. La línea de guía de localización temporal indicará que cada hash se ha calculado usando extractos de audio correspondientes a punto temporal. El aspecto Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 42 de traslación invariante significa que los hashes derivados desde un contenido identificado correspondiente pueden ser reproducido independientemente de su posición dentro del fichero de audio, siempre y cuando la localización temporal que contiene del hash se encuentre dentro del fichero. La robustez implica que los hashes generados desde la base de datos “limpia” debería ser reproducible desde una copia degradada del audio. Además, los landmarks tomados deberían tener una entropía suficientemente alta para minimizar la probabilidad de falsas coincidencias en zonas no correspondidas entre el track no identificado y el track de la base de datos. Si la entropía existente no es suficiente, aparecerán demasiadas coincidencias falsas, requiriendo más procesado para desechar los resultados. Una entropía demasiada alta implicaría fragilidad y que esos fingerprints no puedan ser reproducibles en presencia de ruido y distorsión. [25] Existen tres componentes principales: construcción de mapas de constelaciones, proceso de hash combinatorial y búsqueda y tanteo. 5.1.1.1 Constelaciones: Para abordar el problema de la identificación robusta en presencia de ruido y distorsión altamente significativos, se experimentará con una variedad de características candidatas que podrían sobrevivir a la codificación GSM en presencia de ruido. Esto se decide mediante los picos del espectrograma generado con la pista de audio. [19] Para ello, se debe considerar que un punto de frecuencia de tiempo es un pico candidato si tiene un contenido de energía más alto que todos sus vecinos en una región centrada alrededor del punto. Los picos candidatos se eligen de acuerdo con un criterio de densidad para asegurar que la franja de frecuencia de tiempo para el archivo de audio tenga una cobertura razonablemente uniforme. Los picos en cada localidad de frecuencia de tiempo también se eligen de acuerdo con la amplitud, con la justificación de que los picos de amplitud más altos tienen una mayor probabilidad de sobrevivir a las distorsiones enumeradas anteriormente. Es por ello por lo que se debe realizar una reducción del espectrograma. Extraer las características fundamentales de audio servirá para que este algoritmo funcione de manera mucho más rápida y menos costosa. Conseguir que un espectrograma quede recudido a tan solo un conjunto de coordenadas es todo un avance para el algoritmo, al igual que para el que se desarrolla en este proyecto. Esto ocurre tras la eliminación de la componente de amplitud. Se deben tener en cuenta alguno de los efectos que provoca esta reducción, ya que pueden ser tanto positivos como negativos. Una de las ventajas que aporta es que se vuelve insensible con respecto a la ecualización, ya que generalmente un pico en el espectro sigue siendo un pico con las mismas coordenadas en un espectro filtrado (suponiendo que la derivada de la función de transferencia del filtro sea razonablemente pequeña: picos en las proximidades de una transición brusca en la función de transferencia cambia ligeramente de frecuencia). Por supuesto, el patrón debe ser el mismo para hacer coincidir segmentos de audio. Si coloca el mapa de la constelación de una canción o anuncio de radio contenido en la base de datos en un gráfico de tiras, y el mapa de la constelación de una muestra corta de audio coincidente de unos segundos de duración en una pieza de plástico transparente, deslice la última sobre la primera, en algún momento el número de puntos coincidirá cuando se localice el desplazamiento de tiempo apropiado y los dos mapas de constelación estén alineados en el registro. [26] El número de puntos coincidentes será significativo en presencia de picos inyectados debido al ruido, ya que las posiciones máximas son relativamente independientes. Además, el número de coincidencias también puede ser significativo incluso si se han eliminado muchos de los puntos correctos. El mapas de constelaciones es, por lo tanto, una eficiente forma de emparejar en presencia de ruido y/o eliminación de características. 43 Software para la Detección de Anuncios en Radio 5.1.1.2 Proceso de hash combinatorial Encontrar el desplazamiento correcto directamente de los mapas de constelación puede ser bastante lento, debido a que los puntos de constelación tienen baja entropía. Por ejemplo, un eje de frecuencia de 1024 bits sólo produce un máximo de 10 bits de datos de frecuencia por pico. Por ello, la empresa desarrolló una forma rápida de indexar los mapas de constelaciones. Los hashes de las huellas digitales acústicas se forman a partir del mapa de la constelación, en el que se asocia de forma combinatoria con pares de puntos de tiempo-frecuencia. Se eligen los puntos ancla y la zona objetivo asociada a ella. Cada punto ancla se empareja secuencialmente con puntos dentro de su zona objetivo, cada par produce dos componentes de frecuencia más la diferencia de tiempo entre los puntos. Cada uno de los hashes puede ser almacenado en un entero sin signo de 32 bits. [27] Para crear un índice de base de datos la operación anterior se lleva a cabo para cada pista y así generar una lista correspondiente de hashes y sus tiempos de desplazamiento asociados. Los identificadores de las pistas de audio pueden añadirse a las pequeñas estructuras de datos, dando como resultado una estructura agregada de 64 bits, 32 bits para el hash y 32 bits para el offset de tiempo y el ID del track. Para facilitar un procesamiento rápido, las estructuras de 64 bits se clasifican según el valor del hash. El número de hashes por segundo de la grabación de audio que se procesa es aproximadamente igual a la densidad de los puntos de la constelación por segundo multiplicada por el factor de fan-out en la zona objetivo. Por ejemplo, si se toma cada punto de constelación como un anchor point, y si la zona objetivo tiene un fan-out de tamaño F=10, entonces el número de hashes es aproximadamente igual a F=10 veces el número de puntos de constelación extraídos del archivo. La búsqueda de pares y no de puntos sueltos con respecto a las coincidencias provocará una enorme aceleración en la búsqueda. Por ejemplo, si cada componente de frecuencia es de 10 bits y ∆t también tiene ese valor, entonces la coincidencia de un par de puntos produce 30 bits de información, frente a solo 10 para un solo punto. La especificidad del hash sería aproximadamente un millón de veces mayor, debido a los 20 bits adicionales, y por lo tanto la velocidad de búsqueda de una sola toma de hash es igualmente acelerada. Por otro lado, debido a la generación combinatoria de hashes, asumiendo la densidad simétrica y el fan-out tanto para la generación de hash de la base de datos como para la generación de hash de la muestra, hay F veces más de combinaciones en la muestra desconocida que buscar y F veces más en la base de datos, por lo tanto el total de la aceleración es un factor de alrededor de 1000000/F2, o alrededor de 10000, sobre las búsquedas basadas en puntos individuales. [28] Si p es la probabilidad de que un pico de espectrograma sobreviva el viaje hasta el registro de la muestra capturada, entonces la probabilidad de que un hash de un par de puntos sobreviva es de aproximadamente 𝑝2. Esta reducción es una compensación contra la tremenda cantidad de aceleración que se proporciona. Por ejemplo, si F=10, la probabilidad de que sobreviva al menos un hash para un punto ancla dado sería la probabilidad conjunta del punto ancla y de que sobreviva al menos un punto en su zona objetivo. Si asumimos de manera simplista la probabilidad de supervivencia para todos los puntos involucrados, entonces la probabilidad de que al menos un hash sobreviva por punto ancla es 𝑝 = 𝑝[1 − (1− 𝑝)𝐹] Para valores razonablemente grandes de F, por ejemplo F>10, y valores razonables de p, por ejemplo p>0.1, se tiene aproximadamente 𝑝  𝑝[1 − (1− 𝑝)𝐹] por lo que no se empeora mucho más que como ocurría anteriormente. Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 44 Se aprecia que tras el uso del hash combinatorio se ha cambiado aproximadamente 10 veces el espacio de almacenamiento por aproximadamente 10.000 veces la mejora en velocidad, y una pequeña pérdida en la probabilidad de detección de la señal. Se pueden elegir diferentes factores de densidad y fan-out para distintas condiciones de señal. Para un audio relativamente limpio, por ejemplo para aplicaciones de monitorización de radio, se puede elegir un valor de F para que sea modestamente pequeño y la densidad también se puede elegir para que sea baja, en comparación con la aplicación del consumidor de telefonía móvil, que es un poco más exigente. Por lo tanto, la diferencia en los requisitos de procesamiento puede abarcar muchos órdenes de magnitud. 5.1.1.3 Fase de búsqueda y testeo Para realizar una búsqueda, el paso anterior se realiza en un archivo de sonido de muestra capturado para generar un conjunto de registros hash:time offset. Cada hash de la muestra se utiliza para buscar en la base de datos los hashes coincidentes. Para cada hash coincidente encontrado en la base de datos, los tiempos de desplazamiento correspondientes desde el principio de los archivos de muestra y de base de datos se asocian en pares de tiempos. [29] Después de que se hayan utilizado todos los hashes de muestra para buscar en la base de datos pares de tiempos coincidentes, las ubicaciones se escanean en busca de coincidencias. El conjunto de pares de tiempo representa una gráfica de dispersión de la asociación entre la muestra y los archivos de sonido de la base de datos. Si coinciden, las características de coincidencia deben ocurrir en desviaciones relativas similares desde el principio del archivo, es decir, una secuencia de hash en un archivo también debe ocurrir en el archivo coincidente con la misma secuencia de tiempo relativa. El problema de decidir si se ha encontrado una coincidencia se reduce a la detección de un grupo significativo de puntos que forman una línea diagonal dentro de la gráfica de dispersión. Varias técnicas pueden ser usada para esta detección, como por ejemplo la transformada de Hough. Debido a las rígidas restricciones del problema, la siguiente técnica resuelve el problema en aproximadamente N·log(N) (en escala temporal), donde N es el número de puntos que aparecen en la gráfica de dispersión. Se puede asumir que la pendiente de la línea diagonal es 1.0. Entonces, los tiempos correspondientes de las características de coincidencia entre archivos coincidentes tienen la relación 𝑡𝑘 ′= 𝑡𝑘+𝑜𝑓𝑓𝑠𝑒𝑡 donde 𝑡𝑘 ′ es la coordenada de tiempo de la característica en el archivo de sonido de la base de datos (limpia) y 𝑡𝑘 es la coordenada de tiempo de la característica correspondiente en el archivo de sonido de muestra que se identificará. Para cada coordenada (tk’, tk) en la gráfica de dispersión, se calcula 𝛿𝑡𝑘= 𝑡𝑘 ′−𝑡𝑘 Seguidamente se calcula un histograma de estos valores de 𝛿𝑡𝑘 y se busca un pico. Esto puede hacerse clasificando el conjunto de valores de 𝛿𝑡𝑘 y escaneando rápidamente en busca de un grupo de valores. Los diagramas de dispersión suelen ser muy dispersos, debido a la especificidad de los hashes debido al método combinatorio de generación como se discutió anteriormente. Este proceso de escaneo tendrá un orden de microsegundos e incluso menos. El resultado del match es el número de puntos que coinciden en el pico del histograma. La presencia de un grupo estadísticamente significativo indica una coincidencia. 45 Software para la Detección de Anuncios en Radio Figura 29 - Gráfica de dispersión del tiempo de la base de datos en comparación con el tiempo de muestreo para una pista que no coincide con la muestra [19] Figura 30 - Gráfica con número significativo de pares coincidentes en la línea diagonal [30] Figura 31 - Histograma de los valores 𝛿𝑡𝑘 de la Figura 9 [30] Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 46 Figura 32 - Histograma de los valores 𝛿𝑡𝑘 de la Figura 10 [30] Este proceso de escaneo se repite para cada pista de la base de datos hasta que se encuentra una coincidencia significativa. 5.1.2 Desempeño 5.1.2.1 Resistencia al ruido El algoritmo funciona correctamente con niveles significativos de ruido e incluso con distorsiones no lineales. Se puede identificar correctamente la música en presencia de voces, ruido del tráfico e incluso otra música sonando de fondo. Para dar una idea del poder de esta técnica, a partir de una muestra de 15 segundos muy corrupta, se puede determinar una coincidencia estadísticamente significativa con sólo un 1-2% de los hashes. Una propiedad de la técnica del histogramas de dispersión es que las discontinuidades son irrelevantes, permitiendo inmunidad a los abandonos y enmascaramientos debidos a la interferencia. Un resultado algo sorprendente es que incluso con una base de datos grande, pueden llegar a ser identificadas correctamente cada una de las varias pistas mezcladas entre sí, incluyendo múltiples versiones de la misma pieza, una propiedad conocida como "transparencia". 47 Software para la Detección de Anuncios en Radio Figura 33 - Rango de reconocimiento - Ruido aditivo [30] La figura sobre estas líneas muestra el resultado de realizar 250 reconocimientos de muestras de diferentes longitudes y niveles de ruido contra una base de datos de prueba de 10.000 tracks. Se grabó una muestra de ruido en un bar ruidoso para simular las condiciones de la "vida real". Se tomaron extractos de audio de 15, 10 y 5 segundos de duración de la mitad de cada pista de prueba, cada uno de los cuales fue tomado de la base de datos de la prueba. Para cada extracto de la prueba, la potencia relativa del ruido se normalizó a la relación señal/ruido deseada, y luego se agregó linealmente a la muestra. Se puede apreciar que la tasa de reconocimiento baja al 50% durante 15, 10 y 5 segundos con muestras de aproximadamente -9, -6 y -3 dB SNR, respectivamente. [30] Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 54 55 Software para la Detección de Anuncios en Radio REFERENCIAS [1] Asociación para las Invesitgación de los Medios de Comunicación (2019). Marco General de los Medios en España, datos de 2018. Consultado el 7 de julio de 2019 en https://www.aimc.es/a1mc- c0nt3nt/uploads/2019/01/marco19.pdf. [2] Anuncios-Radio, http://anunciosradio.com/publicidad/shopping_cart.php?manufacturers_id=374&osCsid=clqp40c4vhhc863m90tm4hf7r3. [3] E. Subirá Nimo (2007). “Detección e identificación de anuncios de radio y televisión en tiempo real”. Trabajo de Fin de Grado, Universidad de Sevilla. [4] J. Fernández de la Puente Campano (2015). “¿Qué es el watermarking y el audio fingerprinting?”. Consultado el 10 de julio de 2019 en http://www.jaimefernandez.com/que-es-el-audio-watermarking-y-audio- fingerprint/ [5] The Data Over Sound Blog, “Audio fingerprinting – what it is and why it is useful?”. Consultado el 23 de julio en 2019 en https://blog.chirp.io/audio-fingerprinting-what-is-it-and-why-is-it-useful/. [6] Vijayalakshmi A, Aastha Hissaria, Abhishek Jaisinghani (2014). “A Study on mucis Recognition Technology-Shazam”. International Journal of Advanced Research in Computer Science and Software Engineering. Computer Science Department. Christ University, India. Consultado el 22 de agosto de 2019 en http://ijarcsse.com/Before_August_2017/docs/papers/Volume_4/2_February2014/V4I2-0447.pdf [7] Á. Gascón Bonodan (2015), “Do-It-Yourself Shazam en Matlab – T3chFest”. Consultado el 13 de julio de 2019 en https://t3chfest.uc3m.es/2016/programa/diy-shazam-matlab/?lang=es. [8] Audio watermark en https://en.wikipedia.org/wiki/Audio_watermark. [9] A. Escudero Barrero (2017). “Búsqueda Eficiente de Audio Pregrabado en Audio Broadcast”. Universidad Autónoma de Madrid. [10] J. Serradilla Arellano (2007), “Análisis de las prestaciones de distintas técnicas de preprocesado en audio fingerprinting”. Consultado el 1 de agosto de 2019 en https://es.slideshare.net/cerquides/anlisis-de-las- prestaciones-de-distintas-tcnicas-de-preprocesado-en-audio-fingerprinting?next_slideshow=1. [11] N. J. Hurley, F. Balado, E. P. McCarthy, G. C. M. Silvestre. “Performance of Philips Audio Fingerprinting under Desynchronization”, School of computer Science and Informatics. University College Dublin, Ireland. [12] . Haitsma, T. Kalker, and J. Oostven (2001), “Robust audio hashing for content identification,” in Procs. of the International Workshop on Content-Based Multimedia Indexing, (Brescia, Italy). [13] J. Schalkwijk (2018), “A Fingerprint for Audio”. Consultado en Medium el 25 de Agosto de 2019 en https://medium.com/intrasonics/a-fingerprint-for-audio-3b337551a671. [14] Intrasonics, https://www.intrasonics.com/how-it-works.html. [15] D. Ellis (2009). “Robust Landmark-based Audio Fingerprinting”, MathWorks. Consultado el 22 de abril de 2019 en https://es.mathworks.com/matlabcentral/fileexchange/23332-robust-landmark-based-audio- Error! Use the Home tab to apply Título 1 to the text that you want to appear here. 56 fingerprinting. [16] Onda Cero, http://www.ondacero.es. [17] WavePad, https://www.nch.com.au/wavepad/index.html. [18] Sublime Text, https://www.sublimetext.com. [19] Avery Li-Chun Wang and Julius O. Smith, III., WIPO publication WO 02/11123A2, 7 (2000). [20] Music Wave, http://www.musiwave.com [21] J. Haitsma, A. Kalker, C. Baggen, y J. Oostveen (2001), WIPO publication WO 02/065782A1 [22] J. Haitsma, A. Kalker (2002). “A Highly Robust Audio Fingerprinting System”, International Symposium on Music Information Retrieval (ISMIR) pag. 107-115. [23] Neuros Audio, http://www.neurosaudio.com/. [24] S. Ward e Isaac Richards (2002). WIPO publication WO 02/073520A1. [25] Y. Sharma (2016). “How does Shazam works? What is the logic behind Shazam tracing out the exact song by just a sample of it?”. Quora. Consultado el 28 de agosto de 2019 en https://www.quora.com/How-does-Shazam-work-What-is-the-logic-behind-Shazam-tracing-out-the- exact-song-by-just-a-sample-of-it. [26] Audiograins (2014), “Honeslty It’s Not Magic – How Shazam Works”. Consultado el 13 de agosto de 2019 en http://audiograins.com/blog/2014/03/honestly-its-not-magic-how-shazam-works/ [27] S. Shum (2014). “The Basics of Audio Firngerprinting”. Consultado el 22 de agosto de 2019 en https://people.csail.mit.edu/sshum/talks/audio_fingerprinting_sls_24Oct2011.pdf [28] GitHub, https://github.com/toonketels/Notes/blob/master/how-shazam-works.md [29] Laplacian (2014), “How Shazam Works” en https://laplacian.wordpress.com/2009/01/10/howshazam-works/. [30] Avery Li-Chung Wang, “An Industrial-Strength Audio Search Algorithm”. Shazam Entertainment Ldt. Consultado el 15 de agosto de 2019 en https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf. [31] LAM, D. , “Audio watermarking”. Department of Electronic and Electrical Engineering, University of Auckland, 2003. [32] Bassias, P. Pitas. “Robust audio watermarking in the time domain”, Dept. of informatics, University of Thessaloniki, Greece. [33] R. Carrillo, P. Vizcaya (2003). “Control de pautas comerciales al aire empleando marcas de agua de espectro expandido”, Trabajo adscrito al grupo de Bioingeniería, análisis de señales y procesamiento de imágenes de la Pontificia Universidad Javeriana. [34] F. J. Rodriguez, M, Henríquez Rocha-Pérez y F. Sánchez (2000). “Generation of Gold-sequences with applications to spread spectrum systems”. Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional CINVESTAV-IPN, Computer Science Section, México D. F. [35] D.A., Arango Parrado, P.R. Vicaya Gaurín (2018). “Comparación de marcas de agua y huellas de audio como técnicas para la implementación de pautas comerciales”. Universidad Manuela Beltrán de Bogotá, Colombia. Consultado el 2 de septiembre de 2019 en https://www.redalyc.org/pdf/304/30401203.pdf 57 Software para la Detección de Anuncios en Radio