Optimización de un sistema de audio fingerprinting para la detección de anuncios en tiempo real
-
Upload
jose-ramon-cerquides-bueno -
Category
Documents
-
view
888 -
download
3
Transcript of Optimización de un sistema de audio fingerprinting para la detección de anuncios en tiempo real
Proyecto Fin de Carrera
Optimización de un Sistema de Audio Fingerprinting para la detección de anuncios en tiempo real
Autor: Alejandro Álvarez Dujat des AllimesTutor: Dr. José Ramón Cerquides Bueno
Ingeniería de TelecomunicaciónEscuela Superior de Ingenieros de Sevilla
Índice
Introducción Objetivo Sistema analizado Optimización
Fase 1: Modelado y decisión de umbral Fase 2: Búsqueda de valores óptimos Fase 3: Pruebas de robustez
Conclusiones
Introducción
SISTEMA DE AUDIO FINGERPRINTINGSISTEMA DE AUDIO FINGERPRINTING
Objetivo: detectar automáticamente objetos de audio en tiempo real
Esquema general de funcionamiento:
Fingerprints
+ Datos de los
anuncios
Búsqueda y detección
Señal de audio Búsqueda en la
base de Datos
Semejanza
Examinar
Extracción de fingerprint
Front - endModelado de Fingerprint Verificación de
deteccíon
Datos del objeto de
audiodetectado
Señal de audio
FRONT - END
Pre-procesado
Pos-procesado
Extracción de característica
Transformación lineal
Enventanado y Overlap
Introducción
Conversión A/D
Conversión a mono
Pre-énfasis
Normalización
Filtro paso banda
Codificador/Deco GSM
Tamaño de trama
Overlap
Tipo de enventanado
DFT
MCLT
Haar
Hadamard
Wavelet
Diferencia de energías entre bandas
MFCC
Monotonía espectral
Descriptores de alto nivel: tono, graves
Normalización
Decorrelación
Diferenciación
Cuantización
Histogramas
Trayectorias
Estadísticos
GMM
VQ
HMM
Fijar un umbral
Distancias pre-computadas
Filtrado de candidatos no probables con una medida simple
Índices invertidos a ficheros
Reducción de candidatos con mejor resultado encontrado
División de la base de datos en dos: audio más probable y menos probable
Introducción
2 procesos principales en un sistema de identificación:
Extracción de huellas
Algoritmos de búsqueda de semejanza
Ventajas de utilizar “huellas digitales de audio” frente al uso de objetos de audio directamente:
Reducción de memoria requerida para almacenamiento
Comparación más eficiente
Búsquedas más rápidas en la base de datos
Objetivo
Conseguir un sistema basado en huella de audio óptimo desde el punto de vista computacional
Nos centramos en optimizar el algoritmo de extracción diseñado por Philips
¿Qué pretendemos conseguir con la optimización? Reducir el tiempo necesario para extraer una huella de
anuncio Y reducir el tamaño de una huella
manteniendo las probabilidades de error y el grado de robustez del sistema en unos valores aceptables
Sistema analizado
Características del Sistema Audio Fingerprinting analizado (diseñado por PHILIPS)
Fingerprints
+ Datos de los
anuncios
Búsqueda y detección
Señal de audio Búsqueda en la
base de Datos
Semejanza
Examinar
Extracción de fingerprint
Front - endModelado de Fingerprint Verificación de
deteccíon
Datos del objeto de
audiodetectado
Señal de audio
FRONT - END
Pre-procesado
Pos-procesado
Extracción de característica
Transformación lineal
Enventanado y Overlap
Conversión A/D: PCM-mono a 8 kHz. y 8 bits/muestra
Tiempo de captura: 3 seg.
Tamaño de trama: 0,37 seg.
Overlap: 31/32
Ventana de Hanning
|FFT|
Energía de bandas espectrales
Diferencia entre energías de bandas consecutivas en tiempo y frecuencia
Min(Distancia de Hamming entre fingerprint calculado y los de la BD)
Si BER < 0.35, acepta detección
Si BER > 0.35, rechaza detección
Distancia de Hamming = BER ∙ Tamaño de fingerprint
Sistema analizadoDivisión en 33 bandas logarítmicamente entre
300 Hz y 2 Khz
Factor de Overlap = 31/32
0),(0
0),(1),(
mnEDsi
mnEDsimnF
))1,1(),1(()1,(),(),( mnEmnEmnEmnEnmED
FIN
GE
RP
RIN
TF
ING
ER
PR
INT
Sistema analizado
Parámetros del algoritmo de extracción: Tiempo de captura de la señal de audio Tamaño de trama (en número de muestras) Factor de Overlap Número de bandas en que se divide cada trama Frecuencia inferior para la división de bandas Frecuencia superior para la división de bandas
Para la optimización trabajaremos con los 4 primeros, pues las frecuencias inferior y superior no alteran el tamaño de la huella ni el tiempo de cómputo de esta.
Optimización
Programación del sistema y pruebas sobre este en Matlab 7.0
Metodología: 3 fases FASE 1: MODELADO Y DECISIÓN DE UMBRAL FASE 2: BÚSQUEDA DE VALORES ÓPTIMOS
Con un parámetro Con dos parámetros
FASE 3: PRUEBAS DE ROBUSTEZ
Optimización: Fase 1
Objetivos: Modelar mediante funciones de densidad de
probabilidad conocidas las probabilidades de error que están asociadas al funcionamiento de este sistema.
Fijar el umbral de decisión
¿Probabilidades de error?
Probabilidad de falsa alarma (Pf): probabilidad de que se
produzca una detección de anuncio sin que debiera producirse
Probabilidad de no alarma (Pn): probabilidad de que no se
produzca una detección de anuncio cuando sí debería producirse
Optimización: Fase 1
Funciones densidad de probabilidad de error (PDF):
Pn
Pf
Optimización: Fase 1
Pn → Dist. Weibull Pf → Dist. Normal Umbral de decisión (α): valor medio entre el valor de α a
partir del cual Pn vale 0 y el valor de α a partir del cual Pf vale 0.
0,091 0,274
α =
0,1
8
Optimización: Fase 2
Objetivo: encontrar los valores de los parámetros del algoritmo
de extracción que optimizan el sistema Menor tamaño de fingerprint
Criterios: Pn < 10-12
Pf < 10-12
Menor tiempo de cómputo
Menor requerimiento de memoria
Optimización: Fase 2
Algoritmo básico empleado en las diferentes pruebas implementadas en Matlab 7.0:
Definición de los parámetros que no se variamos durante las simulaciones
Bucle en el que se varía el parámetro o los parámetros objetos de análisis
Representación de la PDF experimental y, con α=0,18, cálculo de Pn y Pf
Cálculo de los parámetros de las funciones de probabilidad que modelan la Pn y la Pf
Cálculo de las distancias de Hamming entre este fingerprint y los de los 15 anuncios
Cálculo del fingerprint de un trozo al azar de duración “tiempo de captura” del anuncio de referencia
Bucle
Cálculo de los fingerprints de 15 anuncios (4 grabaciones son del mismo anuncio en diferentes momentos, anuncio de referencia)
Optimización: Fase 2
Con un parámetro: variamos uno de los 4 parámetros del algoritmo que vamos a analizar y el resto dejamos sus valores de diseño
Conclusión:
Parámetro estudiado Valores analizadosvalores óptimos para
cada parámetro:
Número de muestras por trama 2960:1000:23960 12960
Factor de overlap31/32, 24/32, 16/32,
12/32, 8/3231/32
Número de bandas espectrales 32, 16, 8 8
Tiempo de captura (segundos) 3, 2.5, 2, 1.5, 1, 0.5 1
Con dos parámetros: partiendo del valor óptimo de uno de los 3 parámetros que podemos modificar, modificamos los otros dos restantes empeorándolos desde sus valores óptimos hasta conseguir cumplir con los criterios sobre Pn y Pf
Optimización: Fase 2Pn = 0 Pf = 3.7217·10-138
T. Cómputo = 0,44 Nº Bits = 7328
Pn = 0 Pf = 2.4342·10-12
T. Cómputo = 0,14 Nº Bits = 792
Pn = 0 Pf = 1.4516·10-13
T. Cómputo = 0,10 Nº Bits = 736Pn = 0 Pf = 4.4363·10-12
T. Cómputo = 0,06 Nº Bits = 640
Pn = 0 Pf = 2.1838·10-13
T. Cómputo = 0,16 Nº Bits = 896
Conclusión: Valores que optimizan el sistema
Nº de muestras por trama: 4960 Pn = 0
Factor de Overlap: 31/32 Pf = 4.4363∙10-12
Nº de bandas espectrales: 32 T. Cómputo = 0,0645 seg.
Tiempo de captura: 1 segundo Nº Bits por fingerprint = 640
Optimización: Fase 3
Objetivo: Comprobar el comportamiento de nuestro sistema optimizado ante diferentes degradaciones en la señal de entrada
Las pruebas se realizan sobre 4 anuncios diferentes, los cuales se degradan con el programa Adobe Audition 2.0, se calculan fingerprints de trozos de estos anuncios degradados y se buscan las mínimas distancias deHamming con los fingerprints de los anuncios originales
Algoritmo deextraccíon
Anuncio
Comp.
Algoritmo deextraccíon
Selección de un trozo al azar
Anuncio distorsionado
BER
Optimización: Fase 3
En cuanto a la relación señal-ruido: El sistema original es robusto a partir de
SNR > 10 dB El sistema optimizado es robusto a partir de
SNR > 11 dB
Media de la BER
Desviación estandar de la BER
Optimización: Fase 3
ProcesadoBacardi Limón Viajes Marsans Carrefour La ONCE
Media Desv. Media Desv. Media Desv. Media Desv.
MP3 con VBR nivel 10 0.0419 0.0130 0.0420 0.0125 0.0403 0.0120 0.0408 0.0127
MP3 con VBR nivel 50 0.0407 0.0135 0.0401 0.0123 0.0405 0.0120 0.0409 0.0128
MP3 con VBR nivel 100 0.0411 0.0134 0.0398 0.0125 0.0405 0.0119 0.0399 0.0129
WMA con CBR 5 Kbps 0.0416 0.0137 0.0411 0.0124 0.0403 0.0118 0.0413 0.0128
WMA con CBR 6 Kbps 0.0402 0.0123 0.0420 0.0125 0.0403 0.0120 0.0408 0.0127
Filtrado pasa todo 0.0708 0.0184 0.0633 0.0146 0.0635 0.0157 0.0615 0.0153
Comp. Amplitud 0.1166 0.0377 0.1115 0.0285 0.1049 0.0278 0.1343 0.0373
Ecualización 0.0630 0.0179 0.0582 0.0134 0.0577 0.0131 0.0570 0.0147
Filtrado paso banda 0.0536 0.0299 0.0491 0.0213 0.0496 0.0222 0.0566 0.0295
Esc. Tiempo -2% 0.0625 0.0209 0.0609 0.0174 0.0627 0.0229 0.0412 0.0133
Esc. Tiempo +2% 0.0675 0.0242 0.0752 0.0193 0.0651 0.0247 0.0657 0.0215
Esc. Tiempo -4% 0.0744 0.0221 0.0938 0.0226 0.0776 0.0234 0.0799 0.0233
Esc. Tiempo +4% 0.0796 0.0256 0.0886 0.0247 0.0788 0.0266 0.0814 0.0308
Veloc. Lineal -1% 0.1421 0.0313 0.1447 0.0328 0.1404 0.0319 0.1595 0.0401
Veloc. Lineal +1% 0.1388 0.0347 0.1415 0.0347 0.1218 0.0238 0.1507 0.0351
Veloc. Lineal -4% 0.3466 0.0243 0.3618 0.0278 0.3429 0.0311 0.3556 0.0256
Veloc. Lineal +4% 0.3430 0.0329 0.3608 0.0224 0.3386 0.0318 0.3492 0.0287
Conclusiones
Mejora en el sistema original:
Reducción del tiempo de cómputo de un fingerprint: unas 7 veces más rápido que el sistema con el algoritmo original
Reducción de requerimiento de memoria en un 87%:
Tamaño de huella: 229x32 bits a 20x32 bits
Mantenemos el grado de robustez más o menos en los mismos valores con respecto al sistema original
Gracias por su atención
¿Alguna pregunta?
Proyecto Fin de Carrera
Optimización de un Sistema de Audio Fingerprinting para la detección de anuncios en tiempo real
Autor: Alejandro Álvarez Dujat des Allimes Tutor: Dr. José Ramón Cerquides Bueno
Ingeniería de TelecomunicaciónEscuela Superior de Ingenieros de Sevilla