Capítulo 4 La selección de unidades

49

Capítulo 4: La selección de unidades.

El propósito fundamental de este epígrafe es el de explicar con todo grado de

detalle el mecanismo empleado por los distintos programas realizados para seleccionar a

partir de un texto objetivo a sintetizar (que contiene las características prosódicas de las

unidades, procedente del bloque de procesado lingüístico del Conversor Texto-Voz), las

unidades concretas de la base de datos que van a ser finalmente empleadas en la síntesis.

Como ya se reseñó anteriormente, el principal objetivo que se persigue en este

trabajo es mejorar la calidad de la síntesis de voz mediante la introducción de una

mayor variedad de unidades de la que nos encontraríamos en una base de datos de

difonemas convencional. Tradicionalmente, en este tipo de bases de datos se trabaja con

una sola instancia para cada tipo de unidad, teniendo esta unidad una serie de

características prosódicas (tono y duración) que la hacen que pueda ser considerada

como un ejemplo “típico” de la misma. Como es lógico pensar, con una sola instancia

de cada unidad no resulta posible representar todas las posibles combinaciones de tono

y duración que se van producir en la práctica (combinaciones que van a ser pedidas por

el programa que se encarga de generar la prosodia automática), de tal forma que en

algunas ocasiones se dará la circunstancia de que las características prosódicas de la

unidad objetivo no diferirán mucho de las de nuestra unidad patrón de la base de datos,

en cuyo caso no será muy grande la distorsión producida al adaptar la prosodia de la

unidad original a la de la unidad objetivo mediante TD-PSOLA y en consecuencia no

deteriorándose mucho la calidad de la síntesis. Sin embargo, en otras muchas ocasiones

la prosodia original será tan diferente de la perseguida, que las modificaciones

prosódicas que sea necesario realizar a la unidad para adaptarse a dichas características

pueden hacer que la distorsión introducida lleve incluso a hacer irreconocible la unidad

en el resultado final, lo que se traducirá en una importante degradación de la calidad de

la voz sintética generada.

Otro aspecto a tener en cuenta, además de la modificación en la prosodia de las

unidades, lo constituye el hecho de que éstas no se graban de forma aislada. En efecto,

las unidades son extraídas de un determinado contexto fonético, que por lo general no

Capítulo 4 La selección de unidades

50

tiene porque ser igual al contexto fonético en el que van a ser empleadas en la síntesis.

Este hecho se traduce en que una misma unidad procedente de distintos contextos

fonéticos, debido a los efectos de coarticulación entre los sonidos, va a tener distintas

estructuras de formantes y, en definitiva, un espectro diferente, lo que puede producir la

sensación de que se trata de diferentes unidades cuando la escuchemos. Esto,

evidentemente, también va a influir en la calidad de la síntesis.

Con el objetivo de mejorar dentro de lo posible estos dos efectos explicados

anteriormente, lo que se hizo fue introducir una mayor variedad de unidades en la base

de datos. Para ello, se introdujeron en la base de datos varias instancias para cada

unidad, lo que la dotó de una mayor variedad prosódica y de contextos fonéticos por

unidad debiendo este efecto revertir de una manera directa sobre la calidad final de la

síntesis. Esto es así porque el algoritmo TD-PSOLA se verá obligado a realizar cambios

mucho menos drásticos sobre la estructura de las unidades, reduciéndose por lo tanto

bastante la distorsión introducida al realizar el procesado de señal.

El hecho de construir bases de datos con varias instancias de cada unidad nos

permite modelar con mayor grado de detalle el lenguaje natural, pudiéndonos adaptar a

distintos acentos, entonaciones, expresión de emociones ... además de eliminarse la

necesidad de construir bases de datos específicas para cada aplicación, lo que resulta

claramente ventajoso desde el punto de vista de los desarrolladores de las mismas.

Llevando a su extremo la idea de introducir varias instancias para cada unidad de

la base de datos, si dispusiésemos de un buen conjunto de instancias para cada unidad –

no en cuanto al número sino en el sentido de ser bastante representativas de las distintas

posibilidades en cuanto a características prosódicas y contextos fonéticos que se nos

pueden presentar en el lenguaje natural- se podría pensar incluso en eliminar el

procesamiento de señal posterior. Es decir, se podría pensar en realizar la concatenación

directa de las unidades de la base de datos más adecuadas para cada caso particular con

su prosodia original, eliminándose la carga de cálculo asociada al TD-PSOLA. De esta

forma se eliminaría la distorsión derivada de modificar las unidades, aunque en algunos

casos se podría apreciar claramente un cambio en la prosodia y ritmo de los resultados

frente al objetivo buscado, lo que no sería ni mucho menos positivo. Si consiguiésemos

una “buena” base de datos la desviación no debería ser demasiada, quedando

Capítulo 4 La selección de unidades

51

compensada con creces por la drástica reducción de la complejidad de la síntesis, al

quedar reducida al mero pegado de unidades directamente tomadas de la base de datos.

Un aspecto muy importante a tener en cuenta al margen de lo anterior, es el

hecho de que dado el carácter finito de la base de datos hay que tener presente el hecho

de que incluso la mejor selección nunca se ajustará por completo a la pronunciación

buscada, por lo que siempre será necesario un procesado de señal posterior (TD-

PSOLA) que llevará asociado una distorsión. El objetivo perseguido con todo esto es

realizar la selección de unidades de tal forma que el procesado de señal adicional sea

mínimo y, por lo tanto, la distorsión introducida también lo sea.

La introducción de varias instancias de cada unidad en la base de datos hizo

aparecer dos nuevos aspectos que no se encontraban presentes en la metodología

clásica. Por un lado, fue necesario determinar el mecanismo a emplear de cara a

seleccionar las unidades de la base de datos, de tal forma que dicha selección

minimizase la distorsión producida al concatenar mediante TD-PSOLA. Por otro lado

apareció el aspecto de la capacidad de almacenamiento necesaria para trabajar con esta

estrategia de “grandes” bases de datos.

En relación a este último aspecto, es lógico pensar que el hecho de introducir un

mayor número de unidades tiene el efecto beneficioso de mejorar la calidad de la

síntesis [Black, 91], pero también hay que tener en cuenta que lleva asociado el aspecto

de necesitar una mayor capacidad de almacenamiento, lo que se traduce en ficheros que

contienen bases de datos mucho más grandes (al contener no sólo un mayor número de

unidades, sino también características adicionales a tener en cuenta de cada una de ellas

de cara a la selección) y, sobre todo, de tiempos de búsqueda y de proceso cuando

dichos ficheros son mucho mayores. En este sentido conviene darse cuenta de que no es

posible tratar de mejorar la calidad de la síntesis sólo a base de introducir una mayor

cantidad de unidades, ya que el tamaño de los ficheros y, sobre todo, los tiempos de

búsqueda en los ficheros y de ejecución de los programas asociados, llevarían a que la

síntesis en tiempo real sería impracticable, careciendo en ese caso por completo de

utilidad.

Capítulo 4 La selección de unidades

52

Con el objetivo de reducir la capacidad de almacenamiento necesaria se

emplearon distintas técnicas cuyo objetivo era eliminar aquellas unidades de la base de

datos que resultaban redundantes tanto desde un punto de vista prosódico, como de

contexto fonético, llegándose de este modo a un compromiso entre el tamaño de los

ficheros y la “calidad” de la base de datos. Este último aspecto se tratará más adelante.

4.1. El proceso de la síntesis por selección deunidades.

En este apartado se va a explicar el mecanismo que fue necesario seguir para

realizar todo el proceso de la síntesis, partiendo del texto con la secuencia objetivo hasta

obtener como resultado el fichero con la secuencia sintetizada.

Al igual que en todos los procedimientos anteriores, para realizar la síntesis era

necesario ejecutar una determinada secuencia de programas para llegar al resultado

final. Para automatizar en el mayor grado posible este proceso se realizó un fichero por

lotes (*.bat) de MS-DOS que se encargaba de hacer las distintas llamadas con los

argumentos adecuados. Este fichero se llamaba sintetiza.bat y su contenido se describe

a continuación:

SET DIR_FRASES = D:\SINTESIS\FRASESSET DIR_PRUEBAS =D:\SINTESISCD % DIR_FRASESfor %i in (*.uni) gosub :SINTETIZAquit

:SINTETIZAcd %DIR_FRASEScopy "%@NAME["%i"].uni" %DIR_PRUEBAS\prueba.dicd %DIR_PRUEBAS

bunidad2.exe prueba listetiq >dep.depgendb32.exe prueba.lis pru.dfm >prueba.dpgconca32.exe prueba.dif >prueba.dpc

return

Capítulo 4 La selección de unidades

53

En primer lugar, podemos ver que se definían dos directorios de trabajo. El

primero de ellos, DIR_FRASES, era aquel en el que se encontraban almacenados todos

los ficheros que contenían los distintos textos a sintetizar (generados por el programa

que da lugar a la prosodia automática). Estos ficheros se distinguían por una extensión

de la forma *.uni y tenían exactamente el mismo formato que los ficheros *.DI, esto es,

las líneas del fichero eran de la forma:

NOMBRE_UD DURACION_UD TONOFINAL_UD

El otro directorio, de nombre DIR_PRUEBAS, era aquel en el que se iban

almacenando los distintos resultados, y que además contenía todos los programas

involucrados en la secuencia de la síntesis.

Una vez definidos estos directorios, el programa iba al directorio que contenía

los textos objetivo y, para cada uno de ellos, se realizaba todo el proceso de la síntesis.

El primer paso de cara sintetizar un texto determinado era cambiar la extensión de los

ficheros de *.uni a *.di para seguir con el criterio que había sido empleado hasta aquel

momento. Como se puede ver en el código del programa, no se realizaba simplemente

un cambio en la extensión de los ficheros, sino que se renombraba todo el fichero. Esto

fue hecho así porque los nombres que tenían dichos ficheros (que eran los que generaba

el programa con la prosodia automática) contenían, en algunos casos, espacios y en

ocasiones, eran demasiado largos, dando problemas al pasar dichos nombres como

argumentos a los programas.

Tras cambiarse el nombre del fichero, la primera llamada se hacía al programa

BUNIDAD2.exe, que recibía como argumentos el nombre de dicho fichero (con la lista

de difonemas objetivo a sintetizar), y el nombre del fichero que contenía la lista con

todas las unidades disponibles (en realidad las etiquetas asociadas a dichas unidades),

que en nuestro caso siempre iba a ser el fichero listetiq. El resultado de la ejecución de

este programa era otro fichero con el mismo nombre que el *.DI pero en este caso de

extensión *.DIF , que contenía la lista con los difonemas que habían sido seleccionados

dentro del total, en función de los distintos criterios que serán explicados más adelante.

Capítulo 4 La selección de unidades

54

El formato del fichero *.DIF era el mismo que el del *.DI; es más, en realidad se

trataba de una “copia” de este con la diferencia de que aparecían las etiquetas de las

unidades concretas que habían sido seleccionadas, pero con la duración y tono final

pedidos en el *.DI.

Además de esto, el programa también generaba un fichero con el mismo nombre

del *.DI, pero con la extensión *.INF, en el cual se hacía un resumen de las unidades

que habían sido seleccionadas, sacando la información sobre las características

prosódicas originales y las buscadas, y dándonos además información sobre la

localización de los ficheros y sobre el contexto fonético de procedencia. El aspecto

típico de estos ficheros es el siguiente:

Unidad: UE@6 directorio: BV19048/

Unidad anterior: ALU

duracion original: 72

duracion pedida: 60

tonos originales: 172 204

tonos pedidos: 185 201

Por último, también se generaba un fichero con el mismo nombre que los

anteriores y extensión *.LIS, que contenía una lista con todas las unidades

seleccionadas (ordenadas alfabéticamente), junto con la información sobre los

directorios de localización. Este fichero era el que empleaba el programa que generaba

la base de datos de cara a copiar la información sobre las unidades en la misma. El

formato típico de una línea de estos ficheros es el siguiente (básicamente es el mismo

que se sigue en el fichero listetiq):

AD1@25 AD1 70 178 167 BV01040/ MA FRASE1

El siguiente paso de cara a la síntesis consistía en generar la base de datos con

las unidades seleccionadas. Hay que destacar que, durante el periodo de desarrollo de

las aplicaciones ,se optó por esta estrategia de generar una base de datos que contuviese

tan sólo los difonemas que iban a ser empleados cada vez que se iba a generar una frase,

en lugar de generar toda la base de datos completa de una forma previa y cargar toda

esta base de datos de cara a la síntesis TD-PSOLA. Esto se hizo de esta manera con el

Capítulo 4 La selección de unidades

55

fin de reducir el tiempo de proceso al tratarse de ficheros con un tamaño

considerablemente grande, ya que el programa que generaba la síntesis TD-PSOLA en

primer lugar hacía una carga de toda la base de datos y una normalizacíon de las

energías de las unidades requiriendo este proceso mucho tiempo cuando los ficheros

eran muy grandes.

El programa que generaba la base de datos era el mismo que ya fue empleado en

el apartado anterior, esto es, GENDB32.EXE, recibiendo por lo tanto los mismos

argumentos (la lista con los difonemas de la frase a generar *.LIS y el nombre que iba a

tener la base de datos generada *.DFM) y generando los mismos ficheros de salida.

A continuación se hacía una llamada al programa CONCA32.EXE, que era el

encargado de realizar la síntesis según el algoritmo TD-PSOLA. Este programa recibía

como argumentos el nombre del fichero *.DIF que generó BUNIDAD2.EXE con la lista

de unidades a emplear y la base de datos que contenía dichas unidades. Al final de la

ejecución del programa se generaba un fichero de nombre pru.mst que contenía el

resultado de la síntesis TD-PSOLA.

Al final de todo el proceso se renombraban todos los ficheros “importantes”

(*.MST ...) según el nombre original de la frase de procedencia para evitar que los

ficheros se sobreescribieran en los siguientes procesamientos. Hay que destacar que en

cada uno de los procesamientos las salidas por pantalla de los distintos programas

ejecutados se redirigían a unos ficheros de texto con el fín de depurar los resultados

obtenidos.

4.2. El modelo de selección de unidades.

Como ya se citó, el punto de partida para el programa de selección de unidades

era un fichero de texto procedente de un modulo anterior del Conversor Texto-Voz que

contenía la secuencia de difonemas a sintetizar, acompañados de sus características de

duración y tono medio. El objetivo perseguido por el algoritmo de selección de

unidades era buscar la secuencia de unidades procedentes de la base de datos que mejor

se ajustase a la de la secuencia objetivo, en el sentido de que la utilización de dicha

secuencia tuviese como resultado la minimización de la distorsión en la síntesis

Capítulo 4 La selección de unidades

56

(distorsión que se produce durante el procesamiento de señal que lleva a cabo el

algoritmo TD-PSOLA).

Dentro de la base de datos cada unidad llevaba asociado un vector de parámetros

que la caracterizaba, siendo esta información en la que nos ibamos a basar de cara a la

selección. En nuestro caso, la información que se guardaba para cada unidad estaba

contenida en el fichero listetiq que, como ya fue descrito anteriormente, guardaba para

cada elemento de la base de datos las características que a continuación se relacionan:

- una etiqueta que identificaba de forma unívoca a la unidad. Estas

etiquetas son necesarias para distinguir unas unidades de otras, y son

generadas según el mecanismo que ya fue explicado en el epígrafe anterior

durante la creación del fichero listetiq, esto es, concatenando al nombre

original de la unidad una cadena de la forma @XX siendo XX el número de

veces que había aparecido hasta aquel instante la unidad en la base de datos.

- una etiqueta con el nombre original de la unidad dentro de la frase

de la que fue extraída. Esta información se guardaba para luego poder copiar

los ficheros de muestras y marcas asociados a la unidad, ya que estos estaban

contenidos en el directorio para la frase que generó sacadif32 (el programa

de extracción de los difonemas) y eran de la forma NOMBRE.mst y

NOMBRE.mar, siendo NOMBRE el nombre de la unidad dentro de esa

frase.

- la duración de la unidad expresada en milisegundos. Esta

duración no era exactamente la duración de la unidad completa, sino que se

trataba de la duración entre la primera y última marca de pitch. Esto se hacía

así para adaptarnos a la manera en que trabaja TD-PSOLA, ya que TD-

PSOLA trabaja copiando periodos de señal, que vienen delimitados por las

marcas de pitch, siendo por lo tanto esta la información que a nosotros nos

interesa.

- los tonos inicial y final de la unidad expresados en Hz. Hay que

destacar que la información sobre el tono final es la que nos daba

Capítulo 4 La selección de unidades

57

sacadif32.exe, y que la del tono inicial la tomábamos a partir del tono final

de la unidad anterior de la frase de que fue extraída el difonema. Este aspecto

nos presentaba un pequeño problema, ya que en el caso de las primeras

unidades de las frases carecíamos de una unidad anterior que nos

determinase el tono inicial de la frase. La solución adoptada fue la de copiar

el tono inicial del tono final, haciendo que la unidad tuviese una curva de

entonación lineal. Este criterio de generación del tono inicial fue el mismo

que se siguió a la hora de cargar la información del fichero con la prosodia

objetivo para evitar que se pudiesen producir efectos “extraños” derivados de

una falta de unificación de criterios.

- el nombre del directorio en el que están almacenados los ficheros

de muestras y marcas asociados a la unidad (bv* para la síntesis de dominio

restringido ó r* para el caso de la síntesis de emociones).

- la etiqueta de la unidad precedente en la frase de la que había sido

extraída la unidad de cara a poder determinar el contexto fonético de

procedencia.

- la frase o emoción de que procedía la unidad. Toda esta

información relacionada con directorios y frases realmente no era empleada

por el programa de selección de unidades, pero era necesario almacenarla de

cara a que luego el programa que genera la base de datos fuese capaz de

recuperar los ficheros que le estabamos pidiendo.

- los coeficientes mel cepstrum de la primera y última trama de la

unidad de cara a disponer de información sobre las características espectrales

sin necesidad de tener que recurrir a las muestras.

Con el fin de determinar qué unidad concreta de la base de datos tenía las

características que mejor se ajustaban a las de la unidad/secuencia de unidades objetivo

debíamos tener en cuenta los distintos factores que iban a influir en la distorsión. Así, se

pudo distinguir en principio los siguientes factores causantes de la distorsión [Black,

91]:

Capítulo 4 La selección de unidades

58

- Distorsión producida por la sustitución:

Esta distorsión se produce como consecuencia de la sustitución de la unidad

objetivo por una unidad de la base de datos, que generalmente poseerá unas

características prosódicas diferentes de las buscadas, siendo necesario un procesamiento

de señal mediante TD-PSOLA, que es el que precisamente da lugar a esta distorsión.

Como ya se señaló anteriormente, las características finitas de la base de datos harán

que esta distorsión siempre se encuentre presente (aún tratándose de una unidad con

exactamente las mismas características prosódicas que las buscadas, se generará una

distorsión en la misma derivada de los distintos redondeos que se producen en el

procesado).

- Distorsión producida por la concatenación:

Esta distorsión se genera al pegar unidades de la base de datos que provienen de

contextos fonéticos diferentes. En general, al proceder las unidades de lugares diferentes

van a tener características espectrales diferentes en la zona de pegado, existiendo una

discontinuidad que influirá negativamente sobre la calidad de la síntesis al poderse

percibir en mayor o menor grado sonidos similares a una pequeña explosión en las

uniones entre unidades [Hunt, 96].

Figura 4.1 Componentes de la distorsión.

secuencia objetivo

oi-1 oi oi+1

ui-1 ui u i+1

secuencia de unidades

dist. sustitución

dist. concatenación

Capítulo 4 La selección de unidades

59

4.3. El programa BUNIDAD2.EXE.

Como ya se citó en la descripción global del proceso de la síntesis, este

programa era el encargado de seleccionar la secuencia óptima de unidades de la base de

datos que mejor se ajustaba a una secuencia objetivo, en el sentido de que al emplear

dichas unidades en la síntesis la distorsión derivada del procesamiento llevado a cabo

por TD-PSOLA fuese mínima.

Para poder cuantificar la distorsión introducida por el sintetizador al modificar la

prosodia de las unidades, se definieron una serie de distancias entre las distintas

características contempladas en los vectores que representaban a cada unidad y las

características demandadas por el fichero que contenía la secuencia de unidades

objetivo acompañadas de su prosodia (*.di). Se definió una distancia asociada a cada

característica que tratara de medir la distorsión derivada del hecho de emplear una

unidad de la base de datos con un valor dado para dicha característica, en lugar del valor

pedido para la unidad correspondiente de la secuencia objetivo, considerándose la

distorsión global como una suma ponderada de todas estas distancias. Al tratarse de una

suma ponderada se pudo controlar la importancia relativa que se asignaba a cada

distancia dentro de la distorsión global, sin más que modificar los valores de los pesos

asociados a cada una de ellas, y pudiendo incluso llegar a anular alguno de los factores

considerados inicialmente (asignando un peso de valor nulo a dicha distancia) en caso

de considerar que su importancia no resultaba significativa de cara a la medida de la

distorsión. En cuanto a la definición de las distancias parciales nos encontramos con dos

casos bien diferenciados:

- Distancia entre características que tomaban valores dentro de un rango

aproximadamente continuo.

- Distancia entre características que no toman valores en un rango continuo o

cuyos valores no guardan ninguna relación de orden aparente entre sí.

En el primer caso, en el que los valores de las características se movían en un

rango “continuo” –como puede ser el caso de la duración de las unidades o su tono- la

Capítulo 4 La selección de unidades

60

definición de distancias se presentó como una tarea más sencilla de realizar que en el

caso de características del segundo grupo descrito, como puede ser el contexto fonético.

En el primero de los casos, la definición de las distancias siempre implicaba alguna

variación sobre la distancia euclídea entre las características, pero en el segundo, al no

ser posible establecer una relación de orden, no se pudo recurrir a esta estrategia. En

este segundo caso lo que se hizo fue recurrir a distancias que, o bien no penalizasen en

absoluto la elección de la unidad (al tratarse de una unidad compatible con lo que

estábamos buscando, asignando un valor cero a la distancia), o bien hiciesen prohibitiva

la elección de la unidad (asignando un valor muy grande a la distancia, de tal forma que

se pusiese en clara desventaja a esta unidad frente a unidades del mismo tipo de cara a

la selección).

Hay que tener en cuenta que nuestras distancias no debían, en ningún caso,

eliminar unidades por muy malas que fuesen desde el punto de vista de la distorsión, ya

que el algoritmo de selección siempre debía proporcionar al menos una unidad de la

base de datos para que fuese empleada en la síntesis. Por lo tanto, la estrategia a seguir

fue la de asignar distancias muy grandes a las unidades “malas”, teniendo en cuenta, que

en caso de no disponer de una unidad que se ajustase apropiadamente a las condiciones

de búsqueda, se seleccionaría aquella unidad dentro de las “malas” que mejor se

ajustase a nuestros propósitos. Este hecho lógicamente se reflejaría de forma negativa

sobre la calidad de la síntesis, pero hay que considerar que esta reducción en la calidad

no sería consecuencia de un defecto del algoritmo de selección de unidades, sino más

bien de la calidad de la base de datos empleada en cuanto a la variedad de unidades

presente en la misma.

Asociadas a los distintos factores detectados que influían en la distorsión se

decidió emplear las siguientes distancias:

- Distancia entre la duración de las unidades.

- Distancia entre los tonos.

- Distancia entre los contextos fonéticos.

- Distancia asociada a la concatenación de unidades.

Capítulo 4 La selección de unidades

61

Las dos primeras distancias vienen asociadas a la distorsión citada anteriormente

derivada de la sustitución de unidades, mientras que las dos últimas engloban el

fenómeno de la distorsión en el pegado de las mismas.

De este modo, la expresión global de la distorsión introducida en la síntesis

quedaría como sigue:

Donde:

- Dglobal es la distorsión global procedente de la síntesis de toda la

secuencia objetivo.

- n es el numero de unidades a sintetizar en la secuencia objetivo.

- px es el peso que se asocia a la característica x.

- distx es la distancia que se asocia a la característica x.

- ui y oi representan respectivamente la unidad de la base de datos y

la unidad objetivo que van en la posición i-ésima de la secuencia a sintetizar.

Hay que destacar que, alternativamente a esta elección de características, se

podría haber empleado otra serie de ellas, o incluso un conjunto adicional que

complementase a las actuales y contribuyese a un mayor refinamiento del modelo

aunque, si bien es cierto, también contribuiría a aumentar la complejidad del mismo

[Black, 91].

4.3.1. Distancia entre la duración de las unidades.

Esta distancia trata de medir la distorsión que se produce por el hecho de

emplear una unidad de la base de datos con una duración diferente de la perseguida en

la unidad objetivo. Hay que tener en cuenta que la definición de esta distorsión debe

estar directamente relacionada con el mecanismo que se emplea en TD-PSOLA para

modificar las duraciones, con el fin de medir realmente la distorsión producida por el

procesado de señal y no otra cosa diferente. Además, la distancia debe de ser relativa a

la duración perseguida, con el fin de ser capaces de estimar la distorsión que se produce

)),(),(),(),(( 11

iicontexcontexiiconcconcatiitonotonoii

n

iduracionduraciónglobal oudistpuudistpoudistpoudistpD ∗+∗+∗+∗= −

=∑

Capítulo 4 La selección de unidades

62

en la duración de una forma porcentual y poder comparar directamente las distorsiones

asociadas a las distintas instancias de la base de datos. La expresión general para la

distancia es la que sigue:

donde:

-dur es la duración del elemento a considerar.

-peso es un factor que dependerá de una serie de condiciones.

-u y o son respectivamente la unidad de la base de datos y la unidad objetivo.

El valor del peso que se aplica a la expresión general se encuentra directamente

relacionado con la forma que tiene el algoritmo TD-PSOLA de modificar las

duraciones. Como ya se citó en el apartado dedicado a TD-PSOLA, la modificación de

la prosodia era posible mediante la repetición con una determinada cadencia de los

periodos básicos constituyentes de la unidad, de tal forma que se consideró que la

variación del peso se debía producir en función del número de periodos que fuera

necesario quitar o repetir de la unidad de la base de datos. Para ello se calculó el número

medio de periodos que contenían tanto la unidad de la base de datos como la unidad a

sintetizar:

Como se puede ver, esta definición de distancia tiene cuenta de forma

simultánea la duración y el tono, aspecto acorde con las modificaciones realizadas por

TD-PSOLA, en el que resulta imposible hacer modificaciones en una característica sin

hacerlas en la otra. Con el objeto de ir penalizando progresivamente aquellas situaciones

que nos resultaban menos ventajosas se decidió cuantificar los pesos en cuatro valores

de menor a mayor grado de penalización.

)(/)()( odurodurudurpesodistduracion −∗=

número medio de periodos = duración * (tono medio)

Capítulo 4 La selección de unidades

63

Así se optó por emplear el siguiente esquema en la asignación de los pesos:

Figura 4.2. Asignación de pesos en la distancia entre duraciones

Lo que se hizo en primer lugar fue comprobar si la duración de la unidad

contenida en la base de datos era mayor que la duración pedida, en cuyo caso el peso

que se imponía a la distancia siempre era menor. De este modo se trató de evitar que el

algoritmo seleccionase unidades con una duración original más pequeña que la pedida.

Esto se hizo así porque cuando la duración de la unidad es inferior a la solicitada, la

forma que tiene el algoritmo TD-PSOLA de alargar la duración es mediante la

repetición de periodos de la misma, lo que va a dar lugar a fenómenos de acoplamiento

o reverberación cuando se repiten varios periodos exactamente iguales, lo que se

traduce en que estas unidades presentan una especie de timbre metálico al ser

escuchadas, reduciendo este efecto considerablemente la calidad de la síntesis.

dur u>dur o

(period u-period o)> porcentaje*periodos o

period u=period o

peso=peso_1 peso=peso_2 peso=peso_3peso=peso_4

SI NO

SI

NO NO

SI

Capítulo 4 La selección de unidades

64

Asimismo, se estableció también un porcentaje sobre el número de periodos de

modificación de las unidades, de cara a penalizar algo más aquellas unidades en las que

fuera necesario eliminar un mayor número de periodos de señal para recortar su

duración. De este modo se pretendía centrar la selección sobre aquellas unidades cuya

duración, además de ser mayor que la pedida, difiriese de ella en un número pequeño de

periodos, de tal modo que el número de periodos a eliminar para recortar su duración

siempre fuese el mínimo posible, respetándose la estructura original de la unidad en la

mayor medida de lo posible. Esto se hizo así porque el criterio de eliminación de

periodos no era capaz de distinguir aquellos periodos de señal más significativos de

aquellos que resultaban menos importantes, pudiéndose degradar bastante la calidad de

la unidad original. Hay que destacar que este mismo criterio también se aplicó para las

unidades cortas, de cara a que, en las condiciones más adversas en las que no hubiese

unidades largas en la base de datos, la tendencia fuese a seleccionar siempre las más

largas que estuviesen disponibles.

4.3.2. Distancia entre el tono de las unidades.

Como su propio nombre indica esta distancia trata de medir la distorsión que se

produce al modificar la curva de tono de las unidades de la base de datos para ajustarse

a la de la unidad objetivo. De forma similar al caso anterior, la distancia entre las curvas

de tono de las unidades se definió como una distancia euclídea entre los tonos medios

de la unidad de la base de datos y de la unidad objetivo, ponderada por un cierto factor

que trataba de penalizar aquellas situaciones más desfavorables. Además, esta distancia

se normalizó para ver la distorsión porcentual producida en la unidad al realizar la

midificación en frecuencia, y para poder comparar con las distancias de otras unidades

de cara a la posterior selección. La expresión general de la distancia así descrita:

En cuanto al valor otorgado a los pesos, al igual que en el caso de las duraciones

se empleó un conjunto cuantificado de cuatro valores que trataba de reflejar la

penalización en función de la situación concreta.

objetivofobjetivofunidadfpesodisttono 0/00 −∗=

Capítulo 4 La selección de unidades

65

Así :

Figura 4.3. Asignación de pesos en la distancia en tono

La estrategia seguida fue la de dar una mayor preferencia a aquellas unidades de

la base de datos que, además de presentar una curva de tono con una pendiente similar a

la de la unidad objetivo, tenían tonos medios cuya diferencia era inferior a un porcentaje

fijado del tono medio de la unidad a sintetizar. De esta forma se pretendía que las

modificaciones en la estructura de los periodos de las unidades no fuesen muy grandes,

quedando las unidades con una estructura muy similar a la original y estando, por lo

tanto menos distorsionadas.

Hay que destacar que además se penalizó muy fuertemente a aquellas unidades

cuyo tono medio difería en más de un porcentaje dado del tono medio de la unidad a

sintetizar, tanto por exceso como por defecto. De este modo se pretendió reflejar la

limitación que presenta TD-PSOLA de cara a modificar el tono medio de las unidades

en más de dos octavas, tanto hacia arriba como hacia abajo.

| p t e u - p t e o | > p o r c _ 1 * p t e o

| f 0 _ u - f 0 _ o | < p o r c _ 2 * f 0 _ o

S

p e s o = p e s o _1

S

m o d i f ic a c io n > p o r c

N

p e s o = p e s o_ 2

p e s o = p e s o_ 3

p e s o = p e s o_ 4

S

N

m o d i f ic a c io n > p o r c

N

N

p e s o = p e s o_ 4

S

Capítulo 4 La selección de unidades

66

No obstante, en nuestro caso el porcentaje que se fijó fue algo inferior a esas dos

octavas, ya que al escuchar algunas de las unidades que habían sido sometidas a

modificaciones de este orden, se pudo apreciar que la distorsión introducida era

demasiado elevada, cifrándose experimentalmente la modificación máxima en

frecuencia en un valor en torno al cuarenta por ciento del tono medio original.

4.3.3. Distancia entre los contextos fonéticos.

La distancia entre contextos fonéticos trata de medir la distorsión que se produce

en la síntesis por el hecho de emplear una unidad de la base de datos procedente de un

contexto fonético diferente de aquel en el que va a ser utilizado en la secuencia objetivo

[King, 97]. En efecto, si observamos distintas instancias de una misma unidad

provenientes de contextos fonéticos diferentes, se puede apreciar que en ocasiones

presentan diferencias espectrales en su zona inicial y, dado que es precisamente en este

punto en el que se produce la concatenación de unidades, este aspecto se traducirá en un

mal pegado de las mismas, reduciéndose la calidad de la síntesis al ser claramente

perceptibles los saltos entre unidades.

Figura 4.4. Unidad AB1 tomada de contextos diferentes (/K/ y /N/)

Capítulo 4 La selección de unidades

67

Las diferencias espectrales encontradas en la zona inicial de las unidades son

debidas a que existe un efecto de coarticulación entre los sonidos adyacentes, siendo

aproximadamente igual el espectro de las unidades cuando la unidad precedente es la

misma. En adición a esto, se pudo apreciar que existían algunos grupos de fonemas para

los cuales la estructura de formantes que se daba en el comienzo de la unidad siguiente

no difería mucho, constituyendo por lo tanto una serie de conjuntos de contextos

fonéticos en principio equivalentes para cada sonido en concreto, no siendo por lo

general las relaciones de equivalencia bilaterales.

Figura 4.5. Unidad ALA proveniente de contextos compatibles (/S/ y /T/)

Dado que esta característica no nos ofrecía la posibilidad de hacer una definición

de distancia similar a las anteriores, en el sentido de tratarse de una distancia euclídea,

en nuestro caso se optó por emplear una distancia que estuviese cuantificada en

principio en tres valores diferentes:

Capítulo 4 La selección de unidades

68

- el primero de ellos era un valor que no penalizaba en absoluto a la unidad,

haciendo más fácil, por lo tanto, su selección posterior. Este valor se reservó

para aquellos casos en los que el contexto fonético de procedencia era

exactamente el mismo.

- en segundo lugar se dió un valor intermedio, que pusiese a la unidad en una

leve desventaja con el grupo anterior de unidades, de cara a que en principio

la elección siempre se hiciese dentro del grupo de instancias de la unidad

correspondientes a un mismo contexto fonético de procedencia. Este

segundo valor se aplicó a las unidades que provenían de aquellos contextos

fonéticos que se habían identificado como “equivalentes” para cada sonido

concreto.

- por último, se dio un valor elevado a aquellas unidades procedentes de

contextos fonéticos que no resultaban compatibles con el de la unidad

objetivo. De esta forma se pretendió conseguir que estas unidades sólo

fuesen escogidas en caso de que no existiesen unidades contenidas en los dos

grupos anteriores.

Capítulo 4 La selección de unidades

69

4.3.4. Distancia de concatenación de unidades.

Esta distancia, al igual que la anterior, trata de reflejar la distorsión producida

por el hecho de concatenar unidades de la base de datos que han sido extraídas de

lugares diferentes, debiendo en principio poseer características espectrales diferentes en

la zona de unión. La principal diferencia con la anterior es que, mientras que la distancia

de contextos asignaba un valor en función de unas reglas “estáticas” definidas a través

de la experiencia, en este caso se trata de medir directamente la distorsión a partir de la

distancia entre los espectros de las unidades a concatenar, resultando una medida de la

distorsión que se presenta en principio como mucho más objetiva.

Para medir la distancia entre los espectros se empleó un conjunto de coeficientes

que fuera capaz de representar el espectro de la unidad trama a trama, de tal modo que

la distancia entre dichos coeficientes fuese directamente proporcional a la distancia

entre los espectros. De este modo, la distorsión producida por la concatenación de dos

unidades sería proporcional de alguna forma a la diferencia entre los coeficientes de la

última y primera trama de las unidades a concatenar.

Los coeficientes empleados fueron los mel frequency cepstrum (mfc), que nos

proporcionan una “medición” del espectro en un conjunto de bandas de frecuencia que

se encuentran predefinidas. Hay que destacar que para el cálculo de los mel cepstrum no

se emplea una escala lineal de frecuencias, sino que se utilizan unas bandas

logarítmicas, lo que es claramente acorde con las características del oído humano.

El cálculo de los mel cepstrum se hizo en el programa que extraía los difonemas,

para lo cual se añadió al mismo una rutina que básicamente consistía en lo siguiente:

En primer lugar se define un conjunto de 20 bandas de frecuencia en una escala

logarítmica, cuyos límites expresados en hertzios son los siguientes:

Capítulo 4 La selección de unidades

70

Límites de las bandas ={0, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,

1231.144, 1515.717, 1866.066, 2297.396, 2828.427, 3482.202,

4287.093, 5278.031, 6498.019, 8000.000}

A continuación, se calcula con qué punto concreto de la FFT se corresponde

cada uno de los límites definidos anteriormente:

[ ] [ ] [ ]hzmuestreofrecPOINTSFFThzbandalimitemuestrasbandalimite _/___ ×=

Puesto que en principio todas las bandas no van a tener la misma importancia, de

cara al cálculo de los coeficientes, también se definen unos pesos que van a ponderar los

resultados parciales obtenidos para cada banda, y que dependen tanto de la banda en

concreto considerada como de la posición de la muestra dentro de la misma.

El cálculo de dichos coeficientes se efectúa de la siguiente forma:

[ ][ ] ][___/)__(_ muestrasbandaladelongitudmuestraibandalimiteibandamuestrapeso −=

Una vez efectuado todo este proceso previo común para el cálculo de los

coeficientes de las distintas tramas, se procede al cálculo propiamente dicho de los

coeficientes para cada trama de los difonemas. Para ello, lo primero que hay que hacer

es determinar las muestras que caen dentro de cada una de las tramas. Al igual que en el

algoritmo TD-PSOLA, cada trama está compuesta por dos periodos de señal del

difonema (análisis Pitch-Synchronous), de tal forma que el número de tramas por que

esta compuesto cada difonema es:

num_tramas = num_marcas_pitch - 2

Por lo tanto, cada trama contendrá las muestras comprendidas entre tres marcas

de pitch consecutivas del difonema, existiendo un solapamiento de un periodo de señal

entre cada dos tramas consecutivas. A continuación, para las muestras de la trama se

hace el siguiente proceso:

Capítulo 4 La selección de unidades

71

- En primer lugar se elimina la componente continua de la señal y se aplica a

las muestras un enventanado de Hamming. Para el cálculo de la componente

continua lo que se hace es restar a cada una de las muestras el valor medio de

las muestras de toda la trama. En cuanto al tamaño de ventana que se empleó

se trata del mismo que el de las tramas:

[ ]

[ ] [ ] ))_/2cos(*46.054.0()(0

ventanalongnmedianxnx

nxmedianmst

n

Π−×−=

= ∑=

siendo x[n] el valor de las muestras.

- Posteriormente se calcula la FFT de las muestras resultantes del proceso

anterior.

- A continuación se calcula la energía de la trama, que se va a corresponder

con el último de los coeficientes mel cepstrum.

donde X[k] son los coeficientes obtenidos del cálculo de la FFT.

- El siguiente paso es el cálculo ponderado de la energía de la trama en las

bandas empleadas.

- Por último, se procede al cálculo de los coeficientes mel cepstrum para lo

que se tomó un número de 10 coeficientes por trama, sin considerar el último

de ellos que, como ya se dijo, es la energía de la trama (en principio la única

restricción con que nos encontrábamos fue que este número fuese menor que

el número de bandas en que se trabajaba).

[ ]22/_

0∑

==

POINTSFFT

k

kXenergía

[ ] [ ] [ ][ ]bandakpesoskXbandaebandafin

bandaink∑

=×=

_

_

Capítulo 4 La selección de unidades

72

Una vez realizado el cálculo de los coeficientes mel cepstrum, se procedió a la

definición de una distancia que fuese capaz de cuantificar la distorsión. De cara a esta

distorsión, cada unidad vendría representada por dos vectores de coeficientes: el vector

con los mel cepstrum correspondiente a la primera trama de la unidad y el vector

correspondiente a los coeficientes de la última trama. El resto de vectores no se tuvo en

cuenta, ya que se consideró que las tramas intermedias no resultaban determinantes de

cara a evaluar la distorsión en el pegado de unidades. Se optó por definir la distancia

como la "diferencia" entre los vectores de cepstrum de la última y de la primera trama

de la unidades que deseábamos concatenar, pero dado que el rango de variación de cada

uno de los coeficientes era diferente esta diferencia no podía hacerse directamente como

la distancia euclídea entre ambos vectores, sino que era necesario recurrir a otro tipo de

solución. Puesto que se consideró que en principio la importancia de todos los

coeficientes debía ser la misma, la solución escogida fue la de emplear la distancia de

Mahalanobis entre los dos vectores de coeficientes. La expresión simplificada de esta

distancia queda en nuestro caso:

donde var[i] representa la varianza del coeficiente i-ésimo.

Como se puede ver, la expresión es similar a la de la distancia euclídea,

quedando dividido cada uno de los miembros por la varianza del coeficiente en

cuestión. De esta forma se consigue que, a pesar de que los coeficientes tengan un rango

de variación diferente unos de otros, a la hora de calcular la distancia todos tengan la

misma importancia relativa. Al dividir por la varianza de cada coeficiente quedan

amortiguadas las diferencias muy grandes en aquellos coeficientes que presentan una

[ ] [ ]

9..0

)_/)5.0(cos(_

0

=

+×= ∑=

k

BANDSNUMlklekmfcBANDSNUM

l

π

[ ] [ ] [ ])var/)2_1_(( 2_

0

iivectorivectordistanciaescoeficientnum

i

−= ∑=

Capítulo 4 La selección de unidades

73

mayor varianza, y se amplifica la diferencia en aquellos con una varianza más pequeña

dado que en ellos esta pequeña diferencia puede ser más significativa.

Al igual que en los casos anteriores, se decidió ponderar estas distancias por un

determinado factor que se encargase de que la distancia entre aquellas unidades que no

concatenaban bien fuese muy grande, perjudicándolas de cara a la posterior selección.

En caso de que la distorsión en el pegado fuese razonable, este peso sería igual a la

unidad, resultando directamente la distorsión la distancia de Mahalanobis entre los

vectores de mel cepstrum de las unidades. Para ello, lo que se hizo fue multiplicar por

un factor bastante elevado el resultado del cálculo de la distancia de Mahalanobis entre

las unidades cuando este valor sobrepasase un cierto valor, a partir del cual se

consideraba que la concatenación entre unidades no era buena.

Con el fin de poder determinar este valor de una forma más o menos fiable se

elaboró un programa que realizaba una serie de cálculos de tipo estadístico de las

distancias entre las unidades originales. Para ello, se tomó todo el conjunto de unidades

que aparecía en el fichero listetiq, y se analizó la distancia de concatenación entre las

distintas unidades, tomando sólo para este análisis aquellas unidades que eran sonoras,

ya que se consideró que esta era la mejor forma de obtener unos resultados fiables. Se

calculó la distancia de concatenación entre cada una de estas unidades y su unidad

precedente en el contexto original del que habían sido extraídas, y se hizo un estudio

sobre el valor medio y la desviación típica de estas distancias para ver cuáles eran los

valores de distancias que se podían considerar como “buenos”. Asimismo, se resaltaron

las distancias más elevadas, empleando estos valores (añadiéndoles un cierto margen

para asegurarnos de que eran válidos) como el umbral por encima del cual se debía

considerar que los espectros de dos unidades no pegaban adecuadamente.

Adicionalmente, en el estudio de aquellos casos en los cuales la distancia era

excesiva pudimos detectar que en algunas de estas unidades se habían producido errores

de segmentación o de marcado, no resultando por lo tanto estas unidades fiables de cara

al cálculo y siendo eliminadas de la base de datos hasta que fuesen correctamente

marcadas o segmentadas.

Capítulo 4 La selección de unidades

74

4.3.5. El algoritmo de búsqueda.

El algoritmo de búsqueda es el encargado de encontrar la secuencia de unidades

de la base de datos que mejor se ajusta a las características prosódicas de la secuencia

objetivo, en el sentido de que esta secuencia es aquella para la que se minimiza la

distorsión global producida por el procesado de señal [Black, 91] [Hunt, 96]:

En nuestro caso se empleó una búsqueda de Viterbi, de cara a obtener aquel

conjunto de unidades para las cuales se minimizaba la distorsión de una forma global.

Hay que destacar que la selección de unidades no se podía hacer de izquierda a derecha

de la secuencia (unidad a unidad), ya que de este modo lo que se hacía era optimizar la

selección de cada una de las unidades por separado, no teniendo este por qué ser el

resultado que minimizase la distorsión global producida. Este hecho se puede explicar

fácilmente si tenemos en cuenta que, al ser el carácter de las unidades de la base de

datos bastante heterogéneo, sería bastante probable que el algoritmo fuese

seleccionando unidades que pegasen muy bien unas con otras, pero que se encontrase en

cierto momento con que el pegado de una determinada unidad por la izquierda fuese

muy bueno y por la derecha realmente malo, al carecer de unidades en este lugar que

concatenasen bien con la anterior. En este sentido, la búsqueda de Viterbi solucionó este

problema, ya que siempre tiende a seleccionar una secuencia de unidades que sin llegar

a ser la óptima en cada uno de los puntos, es la que ofrece una continuidad más

uniforme en los puntos de pegado de una forma global, apreciándose menos saltos

bruscos entre unidades y tendiendo, por lo tanto, a ser mejor la calidad de la síntesis en

cuanto a continuidad de la misma.

Se elaboró un programa para el cálculo de las secuencias óptimas de unidades

según el algoritmo de Viterbi. Este programa recibe como argumento de entrada un

fichero con la secuencia de difonemas a sintetizar acompañados de sus características

prosódicas (*.di). Lo primero que hace el programa es buscar todas aquellas instancias

de las unidades demandadas que hay disponibles en la base de datos, para lo cual hace

)),(),(),(),(( 11

iicontexcontexiiconcconcatiitonotonoii

n

iduracionduraciónglobal oudistpuudistpoudistpoudistpD ∗+∗+∗+∗= −

=∑

Capítulo 4 La selección de unidades

75

una lectura previa del fichero que contiene la lista con todas las etiquetas, listetiq, junto

a toda aquella información sobre las unidades que nos va a resultar necesaria de cara al

cálculo de las distintas componentes de la distorsión citadas en el apartado anterior.

Una vez hecho esto, construye una especie de array con tantas columnas como

unidades tenga la secuencia objetivo a sintetizar. Cada una de las columnas contiene el

conjunto de instancias de la unidad que hay que sintetizar en esa posición concreta,

siendo el número de filas por lo tanto, el de instancias de dicha unidad. Así, a modo de

ejemplo, si suponemos que nuestra secuencia objetivo fuese la siguiente:

KA 115 180

AS 65 161

S 90 161

SA 70 161

A_ 80 142

el array resultante de la búsqueda en la base de datos podría ser:

AS@4

AS@3 SA@3

KA@2 AS@2 SA@2

KA@1 AS@1 SA@1 A_@1

KA AS S SA A_

Una vez construido este array se pasa directamente al proceso de búsqueda en el

mismo. Para cada una de las celdas del mismo, además de la información sobre la

unidad de la base de datos que representa, se almacenaba la distorsión (distancia)

acumulada que se llevaba hasta ese punto más información sobre el camino seguido a lo

largo del array para llegar a dicho valor.

Capítulo 4 La selección de unidades

76

La forma de calcular las distancias en cada una de las celdas es la siguiente:

Como se puede ver, la distancia en cada punto está compuesta como ya se dijo

anteriormente por dos elementos. En primer lugar, se encuentra la distancia derivada de

la sustitución, que se calcula a partir de las distancias entre el tono y duración de la

unidad en concreto y de la unidad objetivo contenida en el fichero *.di. En segundo

lugar está la suma de la distorsión derivada de la concatenación y de la distorsión

acumulada en el punto desde el cual se concatena. Esta segunda componente de la

distorsión se calcula como el valor mínimo de dicha suma de distancias (acumulada más

concatenación) entre la unidad considerada y todo el conjunto de unidades de la

columna anterior, guardando de forma adicional en la celda el punto [i-1][k] desde el

cual se ha llegado a tal valor. En el caso de la primera columna esta distorsión carece de

sentido, considerándose en este caso que el segundo término de la expresión es nulo y

señalando cada una de las celdas de dicha columna como el posible principio de la

secuencia óptima.

El proceso de cálculo de las distancias continúa hasta que se consiguen rellenar

todas las celdas del array, y es entonces cuando se puede proceder a determinar la

secuencia óptima. Como se puede apreciar, este aspecto constituye una de las

principales diferencias entre esta técnica y la de optimización de izquierda a derecha, ya

que en nuestro caso no se conoce cuál va a ser la secuencia global hasta el final de todo

el proceso, mientras que en el otro la selección se va haciendo en cada una de las

posiciones, pudiéndose conocer cuando estuviésemos en la posición i-ésima todo el

conjunto de unidades seleccionadas hasta esa posición.

La forma de determinar cuál es la secuencia a escoger, consiste en examinar las

celdas de la última columna, y quedarnos con aquella que presenta un valor mínimo de

distancia. Este punto se considera que es el correspondiente a la instancia de unidad a

escoger para la última posición, ya que es el que presenta una distorsión global

acumulada mínima tras recorrerse toda la secuencia. Lo que se hace para calcular la

secuencia óptima es recorrer el camino seguido para llegar hasta dicho punto, cosa

[ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ][ ]1_..0

)1)1,(_(_

−∈−+−+=

ifilasnumk

kidistanciakiunidadjiunidadconcdistminjisustdistjidistancia

Capítulo 4 La selección de unidades

77

sencilla si tenemos en cuenta que en las celdas, además de la distancia se almacena el

punto de la columna anterior a partir del cual se ha llegado a dicha distancia. De este

modo, podemos conocer cuál es el punto desde el cual se llegó a ese elemento final y

repetir todo este proceso columna a columna hasta llegar al elemento de la primera

columna del array, que será la instancia de la unidad inicial a escoger.