Repositorio Institucional de Documentos
Abstract
En este trabajo se exploran diferentes técnicas para modificar la información sobre la identidad del locutor de señales grabadas de voz. Aplicando el modelo excitación-filtro para el proceso de producción del habla, el objetivo es modificar la información de la señal de excitación y del tracto vocal por separado. Para valorar las trasformaciones realizadas se ha usado un sistema de verificación de locutor del estado del arte. Usando las trasformaciones propuestas se simulará un ataque al verificador donde se tratará de modificar u ocultar la identidad de un locutor. Ramírez Aretio, Santiago; Lleida Solano, Eduardo
Full text
Sistemas de alteración de la voz para falsear la identidad en sistemas de verificación de locutor.
Sistemas de alteración de la voz para falsear la identidad en sistemas de verificación de locutor.
Indice 1-Introducción........................................................................................................................... 2 2Modelo digital de la señal de voz.......................................................................................... 4 2.1-Sistema de producción del habla............................................................................. 4 2.2-Modelo del tracto vocal: Predicción lineal............................................................. 5 2.3-Cepstrum real.......................................................................................................... 8 2.4-Sistemas de verificación de locutor......................................................................... 11 3Modificación de la señal de voz............................................................................................ 16 3.1-Modificacion de la señal de excitación................................................................... 16 3.1.1-Desplazamiento frecuencial del pitch...................................................... 17 3.1.2-Time stretching......................................................................................... 18 3.2 -Modificación del tracto vocal................................................................................. 20 3.2.1-Entrenamiento.......................................................................................... 20 3.2.2-Síntesis..................................................................................................... 21 3.2.3-Modificación con predicción lineal.......................................................... 22 3.2.4-Modificación con cepstrum...................................................................... 23 4Resultados............................................................................................................................. 25 4.1-Desplazamiento frecuencial del pitch..................................................................... 25 4.1.1-Análisis cualitativo................................................................................... 26 4.1.2-Medida de la distorsión espectral............................................................. 27 4.2-Modificación del tracto vocal.................................................................................. 30 4.2.1-Análisis cualitativo................................................................................... 31 4.2.2-Análisis cuantitativo................................................................................. 32 4.2.3-Spoofing................................................................................................... 37 4.2.4-Tampering................................................................................................. 41 6Conclusiones y líneas futuras................................................................................................ 44 7Referencias............................................................................................................................ 46 Anexo........................................................................................................................................ 47 1
1-Introducción La señal de voz captada por un micrófono contiene mucha información. En primer lugar contiene sonidos que forman las palabras de un mensaje que un locutor quiere transmitir. Pero también incluye información acerca del entorno acústico, el idioma, el estado emocional o la identidad el locutor. Este TFG se centra en este último tipo de información. Por diversas circunstancias, una persona puede querer modificar su voz. Por ejemplo un cantante puede querer subirla o bajarla un tono o un delincuente puede querer modificarla para no ser reconocido, etc. En este TFG vamos a desarrollar un sistema de transformación de la señal de voz que permita modificar las características de dicha señal relacionadas con la identidad del locutor. La señal de voz puede descomponerse en una excitación y un filtro que modela la forma del tracto vocal. La mayoría que de las aplicaciones para la modificación de la señal de voz que pueden obtenerse en Internet transforman la información de excitación y del tracto vocal al mismo tiempo. En este TFG vamos a explorar diversas técnicas para modificar la información de la excitación y del tracto vocal por separado. La primera transformación consistirá en un desplazamiento frecuencial sobre la señal de excitación para modificar el pitch. La segunda consistirá en un mapeo entre las características del tracto vocal de dos locutores. Después, para valorar las transformaciones realizadas, usaremos un sistema de verificación de locutor. Los sistemas de verificación de locutor explotan la información sobre la identidad del locutor de la señal de voz para tratar de identificar a personas de manera automática. Otros sistemas de verificación tradicionales basan la identificación de una persona en un objeto o en un conocimiento que solo esa persona puede tener, como por ejemplo una llave o una contraseña. Por el contrario los sistemas de verificación de locutor basan la identificación en la voz, una característica propia de cada persona y que no se puede perder u olvidar. Esta característica hace interesante el uso de estos sistemas en aplicaciones de seguridad tales como el control de acceso o el análisis forense. El modelo digital de producción del habla permite parametrizar el proceso de generación de la señal de voz. Modificando los parámetros relacionados con la identidad del locutor podemos hacer 2
transformaciones que puedan ocultar la identidad o suplantar la de otra persona. En los sistemas de verificación de locutor, esto supone dos problemas bien diferenciados: -Tampering: Una persona intenta ocultar su identidad para no ser detectada. -Spoofing: Una persona intenta suplantar la identidad de otra para, por ejemplo, tener acceso a sus privilegios en un sistema de seguridad. En [1] se puede encontrar una clasificación de las diferentes técnicas de spoofing y tampering existentes. En este TFG se proponen varios sistemas para la transformación de parámetros que contienen información del locutor. El objetivo principal es estudiar el comportamiento de estas transformaciones y sus implicaciones en un sistema de verificación de locutor. La memoria de este trabajo esta dividida en 6 secciones: 1. En esta sección se realiza una introducción a la temática y al trabajo realizado. 2. En esta sección se expone el modelo digital de producción del habla basado en filtro y excitación y se hace una breve introducción a los sistemas de verificación de locutor. 3. En esta sección se proponen varios sistemas para modificar la información de locutor de grabaciones de voz. 4. En esta sección se exponen un serie de experimentos realizados para medir el rendimiento de los sistemas propuestos. También se exponen los resultados de utilizar los sistemas propuestos para realizar un ataque de spoofing y tampering a un sistema de verificación de locutor. 5. En esta sección se realizan conclusiones generales del trabajo realizado y se proponen posibles líneas futuras. 6. En esta sección aparecen todas las referencias que se han aparecido durante la memoria. 3
2-Modelo digital de la señal de voz 2.1-Sistema de producción del habla La producción del habla humana es un proceso complejo donde, desde los pulmones hasta los orificios nasales y labios, intervienen un extenso conjunto de órganos. Una manera sencilla de explicar el proceso de producción consiste en dividir el sistema en excitación y tracto vocal. -Excitación: Los pulmones generan un flujo de aire que atraviesa las cuerdas vocales. Si estas oscilan pueden modular el flujo de aire dándole cierta periodicidad. Los sonidos producidos mediante este fenómeno se llaman sonidos sonoros. Las cuerdas vocales también pueden permanecer relajadas mientras les atraviesa el flujo de aire produciendo así sonidos sordos. La frecuencia de oscilación se llama frecuencia fundamental o pitch. El valor de pitch depende de la longitud y tensión de las cuerdas vocales y por lo tanto es característico de cada persona. Para hombres el valor de pitch suele estar entre 50 Hz y 250 Hz y para mujeres y niños entre 120 Hz y 500 Hz. El ser humano también puede aumentar y disminuir el valor de pitch con el objetivo de cambiar la entonación del habla. 4 Figura 2.1.1: Órganos que intervienen en el sistema de producción del habla Figura 2.1.2: Simplificación del sistema de producción del habla.
-Tracto vocal: El tracto vocal esta formado por todos los órganos entre las cuerdas vocales y la nariz y boca. Cuando la onda acústica atraviesa el tracto vocal, este actúa como un filtro acústico modificando la distribución espectral de la onda original. Se puede demostrar[2] que el filtro acústico se compota como un filtro todo-polos, por lo tanto su respuesta frecuencial está caracterizada por una serie de frecuencias de resonancia. Estas frecuencias de resonancia se llaman formantes y su valor depende de la forma del tracto vocal. Puesto que la forma del tracto vocal de cada persona es diferente, el espectro de la señal de voz contiene información del locutor. La mayoría de los sistemas de verificación de locutor usan únicamente características derivadas de la forma del tracto vocal. 2.2Modelo del tracto vocal: predicción lineal El tracto vocal puede modelarse como un tubo donde el área de cada sección A(x) varia con la longitud. Discretizando la longitud en p intervalos equidistantes podemos representar la forma del tracto vocal con el valor del área de la secciones en cada intervalo Ai. De acuerdo con este modelo de p tubos, en cada unión un parte de la onda acústica es reflejada y otra transmitida. Se define el coeficiente de reflexión ki como el cociente entre la onda reflejada e incidente en la i-ésima unión. Considerando tubos sin pérdidas se cumple: ki=Ai+1−Ai Ai+1+Ai Ai > 0 => |ki | < 1 Si consideramos que la velocidad de propagación es constante, el tiempo requerido por la onda 5 Figura 2.2.1: Modelado de la forma del tracto vocal por 5 tubos de igual longitud y distinto radio.
Por lo tanto el modelo del locutor estará definido por: λ = { wi, μ i,Σi } i=1 M Dado un conjunto de vectores de entrenamiento los parámetros del modelo pueden estimarse usando el algoritmo iterativo EM (expectation-maximization) [9]. Para adaptar el modelo general UBM a cada locutor se utiliza la adaptación MAP (máximo a posteriori) [10]. En el siguiente esquema se muestra un resumen del proceso de entrenamiento: Durante la fase de test se extraen los parámetros de la señal de voz de test del locutor desconocido y se comparan con el modelo del locutor objetivo y con el modelo UBM. Los resultados con cada modelo se comparan y se genera un estadístico , de modo que cuanto más alto sea el valor de este estadístico, más se parece el locutor desconocido al locutor objetivo. La idea principal de este procedimiento es que si el locutor desconocido es quien dice ser, sus vectores de parámetros se ajustarán bien al modelo del locutor. Si es un impostor, sus parámetros se ajustarán mejor al modelo UBM. De la grabación de voz del locutor desconocido se extrae un conjunto de vectores V= { vt } t=1 T . Puede calcularse la log-verosimilitud entre y el conjunto de vectores de test V como: log p(V∣ λ )= 1 T∑ t=1 T log p(vi∣ λ ) Sea UBM el conjunto de parámetros estadísticos del modelo general UBM. El valor del estadístico puede calcularse comparando la log-verosimilitud de V con los modelos del locutor objetivo y con el modelo UBM: 12 Figura 2.4.1: Esquema del proceso de entrenamiento de un sistema de verificación de locutor. Extracción de parámetros Adaptación al modelo de locutor λ = { w i , μ i , Σ i } i = 1 M UBM Modelo de locutor λ UMB Señal de voz del locutor a registrar
Λ(V)=log p(V∣ λ )−log p(V∣ λ UBM ) Para reducir la varianza del estadístico resultante se suele realizar una normalización[11] Λ(V)=Λ(V)− μλ σλ Donde y sl son los parámetros de normalización del modelo de locutor l. Finalmente se fija un umbral y se compara con el estadístico normalizado. Si este es mayor que el umbral el sistema decide que el locutor desconocido es quien dice ser. En el siguiente esquema se muestra un resumen del proceso de test: Los sistemas de verificación de locutor pueden encontrarse con dos situaciones. La primera es que el locutor desconocido sea quien diga ser y la segunda que sea un impostor. La probabilidad de pérdida Ploss se define como la probabilidad de que el sistema rechace a un locutor que sea quien dice ser. Por otro lado la probabilidad de falsa alarma PFA se define como la probabilidad de que el sistema acepte a un impostor. La figura 2.4.3 muestra las distribuciones de los estadísticos obtenidas por un sistema de verificación de locutor real. Se observa que las distribuciones de los impostores y de los no impostores no están completamente separadas. La elección del umbral por lo tanto generará un compromiso entre los valores de PFA y Ploss En la figura 2.4.4 muestra el compromiso entre PFA y Ploss a la hora de elegir el umbral. 13 Figura 2.4.2: Esquema del proceso de test de un sistema de verificación de locutor. Extracción de parámetros Cálculo del estadístico UBM Modelo de locutor Señal de voz del locutor desconocido V = { vt } t=1 T Identidad solicitada λ UMB λ Λ( V ) > θ Aceptar Rechazar Normalización Λ( V ) μ λ , σ λ
La curva DET(detection error tradeoff) es una visualización de las prestaciones del sistema. Consiste en representa Ploss en función de PFA. Se denomina EER (equal-error-rate) al punto de operación en el que se cumple PFA = Ploss. El valor del EER es una representación simplificada de las prestaciones de un sistema de verificación de locutor. -Sistemas de verificación de locutor basados en i-vectors Uno de los principales problemas de los sistemas de verificación es la influencia del canal por el que se transmite la señal de voz. Para resolver este problema se ha propuesto una solución basada en el análisis de factores[12], que conforma lo que hoy en día es el estado del arte en los sistemas de verificación de locutor. 14 Figura 2.4.3: Distribución de los estadísticos obtenidos por un sistema de verificación de locutor. Figura 2.4.4: PFA, Ploss vs umbral en un sistema de verificación de locutor. Figura 2.4.4: Curva DET de un sistema de verificación de locutor
Recientemente los modelos de locutor de total variabilidad basados en i-vectors[13] han ganado importancia debido a su buenos resultados y a su bajo coste computacional. Sea S el supervector de medias del modelo GMM de un locutor. S será un vector formado por la concatenación de { μ i } i=1 M y de dimensión DM1, según el modelo de total variablidad: S=SUBM +T ω i Donde SUBM es el supervector de medias del modelo UBM. T es la matriz de total variabilidad de dimensión DML con L << DM. ω i es un vector aleatorio de distribución normal estándar y dimensión L1 denominado vector intermedio o i-vector. La reducción dimensional hace que los ivectors sean una representación más eficiente de la información cada locutor. En [12, 13] se pueden encontrar diversos métodos para entrenar la matriz T. La mayoría de los sistemas de verificación de locutor basados en i-vectors calculan su estadístico mediante la distancia coseno: Λ( ω 1, ω 2)= 〈 ω 1, ω 2 〉 ∥ ω 1 ∥∥ ω 2 ∥ Donde ω 1 es el i-vector obtenido del locutor desconocido y ω 2 es el i-vector obtenido del locutor objetivo. 15
3Modificación de la señal de voz En la sección anterior se han visto algunas técnicas para separar la información del tracto vocal y la información sobre la excitación de la señal de voz. En esta sección se hacen uso de esas técnicas y se proponen sistemas para transformar tracto vocal y la señal de excitación por separado. 3.1Modificación de la señal de excitación El phase vocoder es una técnica de procesado digital de la señal que permite realizar escalados temporales y desplazamientos del pitch de gran calidad. Su funcionamiento fue descrito por primera vez[14] en 1966 y debido a su bajo coste computacional y a su buen funcionamiento hoy en día su uso es muy frecuente en aplicaciones musicales. El phase vocoder usa la información de fase obtenida en el análisis STFT (short-time Fourier tranform) para modificar la amplitud o fase de las componentes frecuenciales de una señal. Después, sobre la señal modificada en el dominio frecuencial, realiza la STFT inversa para obtener su representación en el dominio temporal. La mayoría de aplicaciones existentes para la modificación del pitch usan técnicas basadas en phase vocoder para realizar un desplazamiento frecuencial sobre la señal de voz. Al no separar las componentes de excitación y de tracto vocal estas aplicaciones también desplazan la posición de los formantes modificando así la información de la forma del tracto vocal. En esta subsección se propone un sistema para la modificación del pitch que actúa solo sobre la señal de excitación con el objetivo de preservar la información del tracto vocal. 16
3.1.1Desplazamiento frecuencial del pitch A continuación se propone un sistema para modificar el valor de pitch de una señal de voz grabada. El objetivo es realizar un desplazamiento frecuencial sobre la señal de excitación tratando de no alterar los parámetros del tracto vocal. El sistema se resume en el siguiente esquema: La señal grabada se divide en segmentos de N muestras con un avance temporal entre segmentos de hop muestras. Para cada segmento se realiza análisis de predicción lineal obteniendo un segmento de señal de excitación y unos coeficientes LP. El efecto de desplazamiento frecuencial lo conseguiremos interpolando o diezmando en tiempo la señal de excitación en un factor . De este modo al interpolar ( >1), se producirá un desplazamiento frecuencial negativo y el valor de pitch se reducirá veces. Al diezmar ( <1), se producirá un desplazamiento frecuencial positivo y el valor de pitch aumentará veces. El proceso de diezmado involucra un problema de alisasing, por lo que en esos casos cada fragmento se pasará antes por un filtro antialiasing. Por otro lado, durante el proceso de interpolación, el espectro original se ve reducido y replicado, efecto que debido a la periodicidad de la señal de excitación resulta interesante conservar. El proceso de interpolación y diezmado a su vez modifica la duración de la señal en un factor . Puesto que nos interesa conservar la duración original previamente modificaremos la duración de esta en un factor 1/ sin alterar su distribución espectral. Esta técnica se conoce como time stretching y es ampliamente utilizada en los procesos de modificación de la escala temporal en los sistemas phase vocoder. Una vez hecho el desplazamiento frecuencial sin haber modificado la duración temporal, cada 17 Figura 3.1.1: Esuquema del proceso de modificación del pitch análisis LP localizado Time stretching ( ) H(z) s[n] (f0 = fi) (N0 = Ni) e[n] (f0 = fi) (N0 = Ni) e'[n] (f0 = fi) (N0 = Ni/α) e''[n] (f0 = fi/α) (N0 = Ni) s'[n] (f0 = fi/α) (N0 = Ni) Coeficientes LP (ai)
segmento de la señal de excitación recuperado es filtrado por sus correspondientes coeficientes LP. En el sistema anterior quedan ciertos parámetros por definir como: -Parámetros de los segmentos de señal (duración, tipo de ventana, factor de overlap) -Orden del análisis LP. -Técnica de interpolación. La elección de estos parámetros y su influencia en la señal sintetizada se discuten en la sección de resultados. 3.1.2Time stretching Conseguiremos el efecto time stretching sintetizando con un número de muestras de avance temporal entre segmentos diferente del de la fase de análisis. El factor de dilatación temporal será por lo tanto: =ho/hi Donde hi y ho son el número de muestras de avance temporal u overlap entre segmentos en la fase de análisis y síntesis respectivamente. El objetivo es calcular el nuevo incremento de fase asociado a ho. Dividimos la señal x[n] en segmentos de N muestras con hi muestras de overlap. Denotamos xm[n] como el m-ésimo fragmento. Definimos: Xm[k]=DFT N{xm[n]} φm[k]=Xm[k] El incremento de fase entre los instantes m y m-1 puede expresarse en términos de la frecuencia instantánea m de sm como: φm[k]−φm−1[k]=him[k] 18
El incremento total de fase puede dividirse en un incremento de fase nominal debido al salto temporal entre los instantes m y m-1 de hi muestras y un incremento de fase adicional: φm[k]−φm−1[k]=him[k]=hi 2πk N+Δφm[k] En términos de frecuencia instantánea: m[k]=2πk N+Δφm[k] hi =2πk N+Δm[k] Puesto que en la práctica calcularemos la DFT mediante el algoritmo FFT, los valores de fase instantánea estarán comprendidos entre - y . Por lo tanto no podemos calcular el incremento instantáneo de fase directamente. Una solución es calcular el incremento de fase adicional como: Δφm[k]=argπ { φm[k]−φm−1−hi 2πk N } donde argπ { x } =x−floor(x/π)π Podemos calcular el incremento de frecuencia instantánea adicional como: Δm[k]=Δφm[k] hi Finalmente el incremento de fase entre los instantes m y m-1de la señal a sintetizar puede expresarse como: φm '[k]−φm−1 '[k]=ho ( 2πk N+Δ m[k] ) normalmente C.I: φ0 '[k]=φ0[k] El espectro del segmento de señal a sintetizar podrá calcularse como: Xm '[k]= ∣ Xm[k] ∣ ejφm '[k] 19
3.2Modificación del tracto vocal En esta sección se propone un sistema para modificar los parámetros del tracto vocal de un locutor A y transformarlos en los de un segundo locutor B. Partimos de un conjunto de grabaciones de la misma frase de A y B. En la fase de entrenamiento se procesarán estos pares de grabaciones y se establecerá un código de mapeo entre los parámetros del tracto vocal del locutor A y los del locutor B. La fase de síntesis modificará una nueva grabación del locutor A no vista en la fase de entrenamiento usando este código de mapeo. 3.2.1Entrenamiento A continuación se muestra un esquema de la fase de entrenamiento del sistema propuesto: 1) Las grabaciones de A y de B se enventanan y se extraen los parámetros del tracto vocal de cada fragmento. 2) Cada vector de parámetros de A se empareja con un vector de B mediante DTW[15] (dynamic time warping) usando una determinada métrica de distancias. El algoritmo DTW permite alinear secuencias de vectores con distinta velocidad de producción. 3) Después se aplica un cuantificador vectorial basado en k-means[16] sobre todos los vectores de A y de B por separado. El resultado de esta operación es una división de todo el 20 Figura 3.2.1: Esuquema del proceso de entrenamiento para la modificación de los parámetros del tracto vocal Extracción de parámetros dtw K-means contador windowing windowing Extracción de parámetros Modelo locutor A K-means Modelo de mapeo LP Modelo locutor B sA[n] sB [ n ] { sm A [ n ] } m=1 Na { sm B [ n ] } m=1 Nb { V m A } m = 1 Na { V m B } m = 1 Nb { Ci A } i=1 K { Ci B } i=1 K Ci A←Cj B V i A ← V j B , ∀ 1 ≤ i ≤ N a
conjunto de vectores de parámetros en diferentes grupos denominados clusters. El vector más representativo de cada cluster se denomina centroide y el conjunto de centroides representará un modelo del tracto vocal de cada locutor. 4) Usando los modelos obtenidos se transforma cada emparejamiento obtenido en el paso 2 en un emparejamiento entre centroides. 5) Se contabilizan todos los emparejamientos. El código de mapeo se establece asignando a cada centroide de A el centroide de B con el que más veces se ha emparejado. Aplicando el algoritmo k-means conseguimos una representación eficiente de todos los vectores de parámetros obtenidos en la fase de entrenamiento. El objetivo de usar este algoritmo es resumir todas las formas del tracto vocal estimadas durante el entrenamiento. El algoritmo DTW trata de emparejar vectores de parámetros de A y de B que se corresponden con el mismo sonido de cada frase de entrenamiento. Puesto que tras el algoritmo k-means todos los vectores ya han sido clasificados en un determinado cluster, este emparejamiento puede traducirse inmediatamente en un emparejamiento entre clusters. Si los centroides son una representación eficiente de las posibles formas del tracto vocal, un emparejamiento entre centroides de A y de B será una representación eficiente de todos los emparejamientos obtenidos mediante DTW. La hipótesis es que si el número de muestras de entrenamiento es lo suficientemente grande estos emparejamientos de centroides serán un buen modelo para mapear el tracto vocal del locutor B en el locutor A. 3.2.2Síntesis A continuación se muestra un esquema de la fase de síntesis del sistema propuesto: 21 Figura 3.2.2: Esuquema del proceso de síntesis para la modificación de los parámetros del tracto vocal Extracción de parámetros windowing sA[n] sm A[n] Modelo locutor A V m A Modelo mapeo C i A C j B = V m B Modificación de parámetros sm B [ n ] sm A [ n ]
La señal original y modificada se dividen en fragmentos de 20 ms. Sobre cada segmento se realiza análisis LP de orden 16 para obtener los coeficientes de predicción de los filtros Am(z) y A'm(z). Después para cada par de coeficientes de la señal original y modificada se calcula la distancia Itakura y se guarda en memoria. Finalmente se calcula la media de todas las distancias obtenidas para cada fragmento. Para tener una distancia de referencia se ha realizado la misma medida comparando pares de grabaciones de la misma frase de un mismo locutor. El problema de alineado debido a la diferencia de velocidad del habla entre grabaciones de la misma frase se ha solucionado utilizado DTW[15]. En total se ha medido la diferencia espectral de trece pares de grabaciones de 13 locutores diferentes obteniendo una distancia media de 0.865. En el experimento se han utilizado 100 grabaciones del corpus Albayzin[19] de las cuales 50 son de hombres y 50 de mujeres. Las grabaciones tienen una frecuencia de muestreo de 16 kHz y las muestras están linealmente cuantificadas con 16 bits. Se han realizado dos conjuntos de medidas para comprobar la influencia del factor de escalado y del orden de predicción en la distorsión espectral. A continuación se muestran los parámetros con los que se han realizado las medidas y los resultados: r N hop p H 1 variable 512 (20ms) N/4 12 100 2 1.3 512 (20ms) N/4 variable 100 Tabla 4.1.1: Parámetros para la medida de la distorsión espectral.r(factor de escalado), N(tamaño de la ventana), hop(avance temporal entre fragmentos), p(orden de predicción), H(precisión de la interpolación). 28
Observamos que la distorsión espectral obtenida en todo el rango de valores de test está por debajo de la referencia. Esto significa que la modificación que introduce el sistema sobre los parámetros del tracto vocal es inferior a la variabilidad temporal intralocutor de los parámetros del tracto vocal. En la figura 4.1.4 llama la atención que para r = 1 la distorsión no es nula. Puesto que en este caso la fase teórica con la que sintetiza es la misma que la fase original, la distorsión puede deberse a errores durante la interpolación. En la figura 4.1.5 puede observarse que para valores de p pequeños la distorsión es mayor. Esto se debe a que si el orden de predicción no es lo suficientemente grande, la forma del espectro de la señal de excitación estimada contiene componentes del tracto vocal. En esos casos al desplazar en frecuencia la excitación estamos modificando el tracto vocal también. También se puede observar como la distorsión es superior para mujeres que para hombres cuando el factor de conversión es mayor que uno. Puede deberse a que el valor de pitch de las voces femeninas es superior y por lo tanto su espectro contiene armónicos lo suficientemente separados para que la predicción lineal contenga detalles de la seña de excitación para órdenes bajos de predicción. 29 Figura 4.1.4: Distorsión espectral en dunción del factor de escalado del pitch. Figura 4.1.5: Distorsión espectral en dunción del factor del orden de predicción
4.2-Modificación del tracto vocal Los sistemas propuestos para la modificación del tracto vocal han sido implementados en Matlab orientados a la transformación de señales con una frecuencia de muestreo de 16 kHz. Se ha usado una ventana Hamming de 512 muestras y un factor de solapamiento del 50%. El resto de parámetros como el número de coeficientes o el número de clusters no han sido fijados y su influencia sobre el resultado se discute en los siguientes apartados. -Sistema de referencia Para tener una cota del máximo rendimiento del sistema se ha tomado una medida de referencia. Consiste en comparar la frase a transformar del locutor de A con la misma frase pronunciada por B, alinearlas con DTW[15] y hacer la transformación de parámetros del tracto vocal. A continuación se muestra un esquema del sistema de medida de referencia. De esta manera no necesitamos generar un modelo de mapeo para estimar los parámetros del tracto vocal del locutor B y el resultado solo depende del método de modificación. Esta medida será por lo tanto una referencia del rendimiento máximo que se puede esperar de los sistemas propuestos para modificar el tracto vocal. 30 Figura 4.2.1: Esquema del sistema de medida de referencia. Extracción de parámetros dtw windowing windowing Extracción de parámetros sA[n] sB[n] { sm B [ n ] } m=1 Nb { V m A } m = 1 Na { V m B } m = 1 Nb V i A ← V j B Modificación de parámetros { sm A [ n ] } m=1 Na { sm B [ n ] } m=1 Na
4.2.1Análisis cualitativo Se ha realizado un análisis cualitativo sobre cómo influyen los parámetros de la función de transformación sobre la señal recuperada. Se ha prestado atención a la calidad y al parecido entre la voz de la señal sintetizada y del locutor objetivo. En general, para todas las señales sintetizadas, los sonidos de la grabación original se conservan y se puede entender la frase pronunciada, por lo que parece que el modelo de mapeo funciona correctamente. No obstante se aprecian algunos artefactos en las señales recuperadas debidos a la pérdida de coherencia en la fase. Tanto para el caso de transformación mediante coeficientes LP como en el caso de coeficientes cepstrum, no se ha tenido en cuenta la fase a la hora de sintetizar. -Tranformación LP En las señales modificadas mediante LP además se escuchan cambios bruscos durante la pronunciación de un sonido de larga duración. Al disminuir el número de clusters este efecto se ve reducido. Este hecho puede deberse a una mala clasificación, formas del tracto vocal propias de un mismo sonido han sido asignadas a diferentes clusters. También se observa que a medida que incrementamos el orden de predicción hasta 64 aumenta la sensación de que la señal sintetizada ha sido pronunciada por el locutor objetivo. Para órdenes altos superiores a 128 comienza a distorsionarse mucho la señal sintetizada. Esto se debe a que con un orden de predicción tan alto se están extrayendo detalles del espectro propios de la información de pitch. -Transformación cepstrum En el caso de señales modificadas mediante coeficientes cepstrum no se aprecian diferencias significativas al cambiar el número de clusters. Parece que el proceso de clasificación mediante el algoritmo k-means funciona mejor con vectores de coeficientes cepstrum que con vectores de coeficientes LP. A medida que aumentamos el número de coeficientes cepstrum aumenta la sensación de que la señal sintetizada ha sido pronunciada por el locutor B y disminuye la calidad de la señal. Este hecho se debe 31
a que al emplear más coeficientes estamos modelando mejor el tracto vocal pero a la hora de sintetizar estamos aumentando la porción del espectro cuya fase estamos estimando. A partir de un cierto número de coeficientes, aproximadamente 130 para hombres y 80 para mujeres, la señal recuperada se ve muy distorsionada. A partir de ese punto se pierde por completo la sensación de transformación hacia el locutor objetivo y se escucha una voz “metálica”. Este fenómeno se debe a que a partir de cierto número de coeficientes estamos mapeando información de pitch. Como se ha visto en la primera sección, la información sobre el pitch en el dominio transformado cepstrum aparece en torno a la muestra que se corresponde con el periodo de pitch. El hecho de que las mujeres tengan una frecuencia de pitch más alta explica que este efecto aparezca antes en mujeres que en hombres. Podemos calcular un teórico valor de pitch a partir de los resultados teniendo en cuenta que en nuestro caso la frecuencia de muestreo Fs es de 16 kHz: f0 H=Fs/130=123Hz f0 M=Fs/80=200Hz Los valores obtenidos encajan entre los valores típicos de pitch para hombres y para mujeres. 4.2.2-Análisis cuantitativo Una vez hecho un análisis cualitativo del funcionamiento de los sistemas, queremos cuantificar el parecido entre el tracto vocal de la señal sintetizada y el tracto vocal del locutor B. Como medida del parecido del tracto vocal usaremos el estadístico resultante de un sistema de verificación de locutor basado en i-vectors. Para este experimento se ha utilizado la partición de pruebas del subcorpus fonético de Albayzin[19]. En esta partición hay un total de 2000 grabaciones de 40 locutores diferentes (50 grabaciones por cada locutor). Cada grabación tiene una duración aproximada de 3 s, una frecuencia de muestreo de 16 kHz y muestras linealmente cuantificadas con precisión de 16 bits. En total hay 500 frases diferentes divididas en 10 particiones de tal forma que hay 10 grupos de 4 locutores (2 hombres y dos mujeres) que pronuncian las mismas frases. 32
Primero se ha entrenado el sistema de verificación de locutor con las 20 primeras frases de cada uno de los 40 locutores. Las 20 frases siguientes se han utilizado para entrenar al sistema de modificación del tracto vocal. Sean {h1 h2 m1 m2} los locutores de un grupo donde h1 y h2 son hombres y m1 y m2 mujeres. Para cada grupo se han generado los siguientes seis modelos de mapeo: h1←h2, h2←h1, m1←m2, m2←m1, h1←m2, m2←h1 Las últimas 10 frases de cada locutor han sido tranformadas con los modelos de mapeo anteriores. Finalmente se han recogido todos los estadísticos que el sistema de verificación de locutor ha obtenido con cada una de las frases modificadas y con las 10 ultimas frases de cada locutor sin modificar. -Análisis del sistema de verificación de locutor Denotamos S1 como el estadístico resultante de un locutor tratando de verificar su verdadera identidad y S0 como el estadístico resultante de un locutor tratando de verificar una identidad falsa. A continuación se muestran las distribuciones de S1 y S0 obtenidas a partir de señales sin modificar: La distribución de los estadísticos se ajusta muy bien a una distribución gaussiana. Para hacer más fácil la interpretación de las gráficas de aquí en adelante se mostrará la curva gaussiana como resumen de la distribución de los estadísticos obtenidos. 33 Figura 4.2.2: Sistema de verificación de locutor en ausencia de spoofing
Una vez realizada una transformación del locutor origen A al locutor objetivo B, nos interesa obtener el resultado de comparar la señal modificada con el modelo del locutor origen y con el modelo del locutor objetivo. Sea Sa el estadístico resultante de una señal modificada tratando de verificar la identidad del locutor origen y Sb el estadístico resultante de una señal modificada tratando de verificar la identidad del locutor destino. Una transformación perfecta daría como resultados Sa S0 y Sb S1 . -Transformación LP Se ha usado el sistema de referencia con diferentes órdenes de predicción M con el objetivo de obtener la influencia del número de coeficientes en el resultado. También se han realizado transformaciones con diferente número de clusters K con p = 64. A continuación se muestran los resultados: En la figura 4.2.5 se observa que a medida que aumenta p la distribución de Sb se aproxima a la de S1 y la distribución de Sa se aproxima a la de S0. Resultado que concuerda con la teoria puesto que un orden superior permite a la predicción lineal extraer más detalles del tracto vocal del locutor origen y destino. La notable diferencia en media entre las distribuciones de S1 y Sb indica que no se están mapendo todos los parámetros del tracto vocal que usa el verificador de locutor En la figura 4.2.6 puede apreciarse el correcto funcionamiento de los modelos de mapeo puesto que los resultados obtenidos para diferentes valores de K se parecen mucho a los resultados del sistema de referencia. También se observa que al doblar el valor de K la distribución de Sb se aproxima un poco a la de referencia mientras que la de Sa no cambia. 34 Figura 4.2.5: Referencia spoofing LP para varios órdenes de predicción Figura 4.2.6: Spoofing LP con diferente número de clusters
A la vista de las dos gráficas se saca como conclusión que el orden de predicción tiene más influencia sobre el resultado que el número de clusters. El coste computacional asociado a doblar el tamaño del cluster no compensa la mejora en los resultados. -Transformación cepstrum Al igual que en el caso anterior se ha usado el sistema de referencia con diferente número de coeficientes cepstrum NC. Después se ha fijado NC = 80 y se han realizado transformaciones con distintos valores de K. A continuación se muestran los resultados: En la figura 4.2.7 se observa, al igual que en el caso anterior, que aumentando NC se consigue que Sa y Sb se separen y se acerquen a S0 y S1 respectivamente. Al incrementar NC se están utilizando coeficientes cepstrum con cada vez menos información del tracto vocal. En la figura 4.2.7 se puede apreciar como la mejora al pasar de 100 a 120 coeficientes es menor que al pasar de 80 a 100. La figura 4.2.8 muestra que el modelo de mapeo funciona correctamente y que K tiene poca influencia en los resultados. Un tamaño K=128 parece ofrecer las mismas prestaciones que el sistema de referencia. Comparando lo resultados del gráfico 4.2.8 con los de 4.2.6 podemos sacar como conclusión que la clasificación y la generación del modelo de mapeo funciona mejor con coeficientes cepstrum que con coeficientes LP. 35 Figura 4.2.8: Spoofing cepstrum para distinto número clusters Figura 4.2.7: Referencia spoofing cepstrum para distintos NC
A continuación se muestran los resultados de transformaciones LP y cepstrum separando transformaciones entre locutores del mismo sexo y de distinto sexo. Se puede observar que, tanto para la transformación mediante LP como mediante cepstrum, se obtienen mejores resultados en transformaciones entre locutores del mismo sexo. Una explicación sencilla es que estos casos el tracto vocal del locutor origen es más similar al del locutor objetivo que en los casos contrarios. Si nos fijamos en las transformaciones entre locutores del mismo sexo se puede observar que la transfomación mediante cepstrum genera mejores resultados que la transformación LP con un menor número de coeficientes. Este resultado pone de manifiesto que los coeficientes cepstrum son una representación más compacta del tracto vocal que los coeficientes LP. No obstane también se puede apreciar que la transformación LP genera mejores resultados que la transformación cepstrum en transformaciones entre locutores de diferente sexo. 36 Figura 4.2.9: spoofing entre locutores de igual y distinto sexo
4.2.3Spoofing En esta subsección se expone un estudio sobre las implicaciones que tendrían los sistemas de transformación del tracto vocal propuestos a la hora de intentar falsear una identidad. En este escenario el locutor origen de la transformación es un intruso que trata de identificarse como el locutor destino. La probabilidad de engañar al sistema por lo tanto será la probabilidad de falsa alarma obtenida en presencia de spoofing. -Sistema de verificación de locutor en ausencia de spoofing Con los resultados del gráfico 4.2.2 para distintos umbrales de decisión se obtienen las siguientes probabilidades de falsa alarma PFA y probabilidades de pérdida Ploss: Tomamos el punto EER como punto de operación del sistema es ausencia de spoofing: umbral PFA Ploss 40.87 0.02 0.02 Tabla 4.2.1: Punto de operación del verificador de locutor sin spoofing -Sistema de verificación de locutor en presencia de spoofing Sustituyendo ahora S0 por Sb puede obtenerse el comportamiento del sistema ante un ataque de spoofing usando los sistemas de transformación propuestos. En este caso el locutor origen de la transformación 37 Figura 4.2.11: PFA, Ploss vs umbral en ausencia de spoofing Figura 4.2.10: PFA, Ploss vs umbral en ausencia de spoofing
5-Conclusiones y líneas futuras En este trabajo, a partir de un modelo digital del proceso de producción el habla, se han propuesto e implementado sistemas para modificar la señal de voz. El sistema para la modificación del pitch consigue señales de buena calidad con determinados parámetros y con factores de escalado cercanos a uno. También se ha visto que el sistema no modifica significativamente los parámetros del tracto vocal. Una posible mejora consistiría en poder cambiar el factor de escalado del pitch a lo largo del tiempo. De este modo se podría elegir un valor de pitch en cada instante de tiempo y poder cambiar la entonación de la frase sintetizada. A la vista de los resultados obtenidos en la transformación del tracto vocal se puede concluir que hay un compromiso entre la calidad de la señal recuperada y la cantidad de información del tracto vocal que se mapea de un locutor a otro. Las transformaciones con 80 coeficientes cepstrum permiten sintetizar señales con bastante calidad y que generan distribuciones cercanas a las del locutor objetivo. Las distribuciones más cercanas a las del locutor objetivo se han obtenido modificando con 256 coeficientes cepstrum. En modificaciones con tantos coeficientes la señal recuperada no parece natural y cualquier ser humano que la escuchara detectaría la transformación. Con el sistema para la modificación del tracto vocal se ha simulado un ataque de spoofing y de tampering a un sistema de verificación de locutor del estado del arte y se ha conseguido reducir sus prestaciones en un orden de magnitud. Suponiendo que el verificador opera en el punto de EER en ausencia de señales modificadas, el sistema de transformación propuesto conseguiría suplantar una identidad en el 72% de los casos y ocultar una identidad en el 99% de los casos, resultados que ponen de manifiesto la problemática del uso de los sistemas de verificación de locutor en aplicaciones de seguridad. Siguiendo el esquema básico del sistema, generación del modelo de mapeo y modificación de los parámetros del tracto vocal, una posible continuación del trabajo pasaría por mejorar cada uno de estos dos procesos por separado: -Mejorar el modelo de mapeo entre locutores: 44
-Usar modelos ocultos de Markov para tener en cuenta la evolución temporal. -Incluir derivadas de los parámetros en el proceso de clasificación. -Usar modelos perceptibles como la escala Mel en el proceso de clasificación. -Mejorar la modificación de parámetros -Tener en cuenta la fase a la hora de sintetizar para recuperar señales con más calidad. -Investigar otras técnicas más sofisticadas del estado del arte. En este trabajo se ha puesto de manifiesto la problemática del spoofing y del tampering en los sistemas de verificación de locutor. Los artefactos generados con los sistemas de transformación podrían ser estudiados para después ser utilizados en la detección de spoofing y tampering. 45
6Referencias [1] Jesús Villaba, Eduardo Lleida,”Speaker Verification Performance Degradation against Spoofing and Tampering Attacks”. VI Jornadas en Tecnología del Habla and II Iberian SLTech Workshop. 2010 [2] Xuedong Huang, Alex Acero, Hsiao-Wuen Hon, “Spoken Language Processing” , Chap 6.2 Acustical Model of Speech Production. ISBN 0-13-022616-5. [3] Atal, B.S. and M.R. Schroeder, “Predictive Coding of Speech Signals”. Report of the 6th Int. Congress on Acoustics, 1968, Tokyo, Japan. [4] Anexo: 1-Principio de ortogonalidad y solución del análisis LP. p 48. [5] Anexo: 2-Recursión de Durbin.p 49. [6] Anexo: 5-Recursión para calcular los coeficientes de reflexion a partir de los coeficientes LP. p 51. [7] Xuedong Huang, Alex Acero, Hsiao-Wuen Hon, “Spoken Language Processing” , Chap 6.4 Cepstral Processing. ISBN 0-13-022616-5. [8] A.V. Oppenheim, R.W. Schafer, From Frequency to Quefrency: “A History of the Cepstrum”. IEEE Signal Processing Magazine, September (2004), pp. 95-99, 106. [9] A. Dempster, N. Laird, and D. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society, vol. 39, no. 1, pp. 1–38, 1977. [10] Bimbot, Frédéric et al. “A Tutorial on Text-Independent Speaker Verification.” EURASIP Journal on Advances in Signal Processing 2004.4 (2004): 430-451. Web. [11] K. P. Li and J. E. Porter, “Normalizations and selection of speech segments for speaker recognition scoring,” in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP ’88), vol. 1, pp. 595–598, New York, NY, USA, April 1988. [12] N. Dehak, P. Kenny, R. Dehak, P. Dumouchel, and P. Ouellet, “Front end factor analysis for speaker verification”. In print IEEE Trans. Audio, Speech and Language Processing, 2010. [13] P. Kenny, P. Ouellet, N. Dehak, V. Gupta, , and P Dumouchel, “A study of inter-speaker variability in speaker verification,” IEEE Trans. Audio, Speech, and Language Processing, vol. 16, pp. 980–988, 2008. [14] Flanagan, J.L, Golden, R.M, “Phase vocoder”, in Bell System Technical Journal, vol 45, pp 1493-1509. November 1966. [15] Xuedong Huang, Alex Acero, Hsiao-Wuen Hon, “Spoken Language Processing” , Chap 8.2.1 Dynamic Programming and DTW. ISBN 0-13-022616-5. [16] Anexo: 6-Algorimto k-means.pp 51-52. [17 Anexo: 3-Distancia Itakura. p 50. [18] Anexo: 7-Algorimto k-means modificado. p 53. [19] A. Moreno, D.Poch, A.Bonafonte, E.Lleida, J.Llisterri, J.B.Marino, C.Nadeu "Albayzin speech data base: design of the phonetic corpus" EUROSPEECH'93, Berlin, 21-23 Sept. 1993, pp.175-8. 46
ANEXO 1/1 47
1Principio de ortogonalidad y solución del análisis LP Queremos predecir el valor de la señal s[n] a partir de sus p valores anteriores: s[n]=∑ k=1 p aks[n−k] (1) el error de predicción por lo tanto será: e[n]=s[n]−∑ k=1 p aks[n−k] (2) Si J es el error cuadrático medio de la señal error: J=E{e2[n]}=E{(s[n]−∑ k=1 p aks[n−k])2} (3) Derivando respecto a un coeficiente arbitrario ai e igualando a cero: ∂J ∂ai =2E{e[n]∂e[n] ∂ai }=2E{e[n]s[n−i]}=0,1⩽i⩽p (4) De la ecuación anterior se deduce que los coeficientes de predicción que minimizan el error cuadrático medio son aquellos que generan un residuo cuyo producto escalar con las p muestras anteriores de s[n] es cero. Esto se conoce como el principio de ortogonalidad. Substituyendo e[n] por la ecuación (2) en el principio de ortogonalidad obtenemos: E { s[n−i]s[n] } =∑ k=1 p akE { s[n−i]s[n−k] } ,1⩽i⩽p (5) Si Rs [k] es la función de autocorrelación de s[n] obtenemos las siguientes ecuaciones lineales: Rs[i]=∑ k=1 p akRs[i−k],1⩽i⩽p (6) En formato matricial: ( Rs[0]Rs[1] ⋯ Rs[p−1] Rs[1]Rs[0] ⋯ Rs[p−2] ⋮ ⋮ ⋱ ⋮ Rs[p−1]Rs[p−2] ⋯ Rs[0] ) ( a1 a2 ⋮ ap ) = ( Rs[1] Rs[2] ⋮ Rs[p] ) (7) 48
2Recursión de Durbin Dado un sistema de ecuaciones cuyos coeficientes dependientes forman una matriz tipo Toepliz como por ejemplo las ecuaciones del análisis LP: ( Rs[0]Rs[1] ⋯ Rs[p−1] Rs[1]Rs[0] ⋯ Rs[p−2] ⋮ ⋮ ⋱ ⋮ Rs[p−1]Rs[p−2] ⋯ Rs[0] ) ( a1 a2 ⋮ ap ) = ( Rs[1] Rs[2] ⋮ Rs[p] ) Los coeficientes ai pueden calcularse siguiendo la siguiente recursion: Inicialización: E0=Rs[0] Iterar para i=1, …, p : ki= ( Rs[i]−∑ k=1 i−1 ak i−1Rs[i−k] ) /Ei−1 ai i=ki ak i=ak i−1−kiai−k i−1,1⩽k<i Ei=(1−ki 2)Ei−1 Final: ak=ak p,1⩽k⩽p Los coeficientes intermedios ki son los coeficientes de reflexión. 49
3Distancia Itakura Sean A0 y A1 los coeficientes de predicción lineal obtendos de los segmentos de señal de voz x0 y x1 respectivamente. La distancia Itakura permite medir la separación entre la represetnación espectral de A0 y A1. Sean E00 y E01 las energías de los errores de predicción obtenidos al filtrar x0 con los coeficientes A0 y A1 respectivamente: E00=E ( ∣A0 Tx0∣2 ) =A0 TR0A0 E01=E ( ∣A1 Tx0 ∣2 ) =A1 TR0A1 Donde R0 es la matriz de autocorrelación de x0. La distancia Itakura entre A0 y A1 se calcula como el cociente entre E00 y E01: D(A0, A1)= A0 TR0A0 A1 TR0A1 Puesto que D(A0, A1)≠D(A1, A0) normalemnte se calcula la versión simétrica de la distancia Itakura como: Ds(A0, A1)=log A0 TR0A0 A1 TR0A1 +log A1 TR1A1 A0 TR1A0 50
4Recursión para calcular los coeficientes LP a partir de los coeficientes de reflexión Iterar para i=1, …, p : ai i=ki ak i=ak i−1−kiai−k i−1,1⩽k<i Finalmente: ai=ai p,1⩽i⩽p 5Recursión para calcular los coeficientes de reflexion a partir de los coeficientes LP Inicialización: ai p=ai Iterar para i=p , …,1 : ki=ai i ak i−1=ak i+ai iai−k i 1−ki 2,1⩽k<i 6Algoritmo k-means Dado un conjunto de vectores de observación { Xi } i=1 N el algoritmo iterativo k-menas contruye una partición de las observaviones en K conjuntos { Sn } n=1 K tratando de minimizar: ∑ n=1 k∑ Xj∈Sn ∥Xj−Cn∥2 donde los vectores { Cn } n=1 K se conocen como centroides y son la media de vectores asignados a cada conjunto. Sea Sn t el conjunto de observaciones de vecotores pertenecientes al n-esimo cluster en la iteración 51
número t y { Cn t } n=1 K los K centroides en la iteración numero t. El comportamiento del algoritmo se describe a continuación: -Inicialización: Se toman K vectores al hazar del conjunto { Xi } i=1 N como centroides. -Iteraración: Asignación: Sn t= { Xi: ∥ Xi−Cn t ∥ ≤ ∥ Xi−Cj t ∥ ∀1≤j≤K } Actualización: Cn t+1=1 card (Sn t)∑ Xi∈Sn t Xi El algoritmo ha convergido cuando las asiganciones no cambian. 52
7Algoritmo k-means modificado Se define { Ai } i=1 N como el conjunto de observaciones de vectores de coeficientes LP a clasificar y { ri } i=1 N el conjuntio de coeficientes de reflexión asociados. Sean { Cn t } n=1 K los K centroides en la iteración numero t y { Rn t } n=1 K su conjuntio de coeficientes de reflexión asociados. Sea Sn t el conjunto de vecotores de coeficientes LP pertenecientes al n-esimo cluster en la iteración número t. Se define d ( A, B ) como la distancia Itakura entre los vectores A y B. El comportamiento del algoritmo consiste en: -Inicialización: Se calcula { ri } i=1 N a partir de { Ai } i=1 N usando el algoritmo [5] y se toman K vectores al hazar del conjunto { Ai } i=1 N como centroides. -Iteraración: Se calculan las distancias entre cada observacion y cada centroide: d ( Ai,Cn t ) ∀1≤i≤N 1≤n≤K Asignación Sn t= { ri:d ( Ai,Cn t ) ≤d ( Ai,C j t ) ∀1≤j≤K } Actualización de los centroides mediante la media artimética de los coeficeintes de reflexión: Rn t+1=1 card (Sn t)∑ ri∈Sn t ri Cn t+1lp ←Rn t+1 El algoritmo ha convergido cuando las asiganciones no cambian. 53