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.