Ondículas

Yves Meyer (francés), Ingrid Daubechies (belga y estadounidense), Terence Tao (australiano y estadounidense) y Emmanuel Candès (francés) han realizado contribuciones pioneras y trascendentales a las teorías y técnicas modernas del procesamiento matemático de datos y señales. Estas son base y soporte de la era digital, al permitir comprimir archivos sin apenas pérdida de resolución; de la imagen y del diagnóstico médico, al permitir reconstruir imágenes precisas a partir de un reducido número de datos; y soporte de la ingeniería y la investigación científica, al eliminar interferencias y ruido de fondo.

Así reza el comunicado de la Fundación Princesa de Asturias por el cuál se concedió el Premio Princesa de Asturias de Investigación Científica y Técnica 2020 a los matemáticos Yves Meyer (doctor honoris causa por la UAM), Ingrid Daubechies, Terence Tao y Emmanuel Candès. Todo un hito para esta disciplina.

Pero, ¿qué hicieron exactamente? Bien, la respuesta tiene que ver con algo conocido como teoría de ondículas, de gran importancia porque consigue dividir imágenes y sonidos en objetos matemáticos más pequeños y manejables, pero manteniendo los detalles con precisión, eliminando ruidos e interferencias, comprimiendo sin apenas pérdida de calidad.

Los pioneros fueron Meyer y Daubechies (al primero, las ondículas le hicieron merecedor del Premio Abel en 2017) y, más adelante, Tao y Candès completarían su trabajo con estudios relacionados con la teoría del compressed sensing, permitiendo la reconstrucción eficiente de datos dispersos basados en muy pocas mediciones. Las aplicaciones son muchas y de gran relevancia para nuestra vida cotidiana: procesamiento de imágenes, reconocimiento de voz, múltiples campos de la medicina, geofísica o astrofísica entre otras. Por todo esto, queremos que este breve artículo sirva de introducción a una de las ramas de las matemáticas de mayor actualidad.

El descubrimiento

La historia del origen de estos artefactos matemáticos resulta, cuando menos, curiosa. Yves Meyer estaba esperando a que uno de sus colegas de la École Polytechnique terminara de fotocopiar un artículo de Jean Morlet y Alex Grossmann (de Marsella) sobre una nueva técnica para descomponer las señales sísmicas complejas registradas en los terremotos. Meyer cogió una copia de este artículo y se percató de que contenía elementos similares a teorías de descomposición de funciones de Análisis Armónico (su rama de especialización en ese momento). Ese mismo día tomó el tren a Marsella para conocer a los autores y, a partir de ahí, el resto es historia. Las ondículas, resultado final de esta intrigante anécdota, se convirtieron en una teoría que ha inspirado muchos trabajos de matemáticos, físicos e ingenieros durante los últimos años.

Llegados a este punto, probablemente te estés preguntando qué son o en qué consisten exactamente estas ondículas. Pero antes debemos introducir un concepto del que seguramente hayas oı́do hablar en algún momento: las series de Fourier (y si no, no pasa nada porque te lo explicamos aquı́).

El objetivo de las series de Fourier es aproximar funciones por medio de senos y cosenos. Es muy fácil, tomamos una función $f$ periódica con periodo $T$, es decir, $f(x) = f(x+T)$ para todo $x$ real, y damos una aproximación en un intervalo de longitud $T$.

Reproduciendo a continuación este intervalo por toda la recta real, obtenemos una aproximación final. Sea $s_{N}$ la serie formada por los elementos:

$$s_N(t) = \frac{a_{0}}{2} + \sum_{n=1}^{N} \left[ a_{n} \cos \left( \frac{2n\pi}{T} t \right) + b_{n} \sin \left( \frac{2n\pi}{T} t \right) \right]$$

con:

$$a_{0} = \frac{2}{T} \int_{-T/2}^{T/2} f(t) \, dt \\ a_{n} = \frac{2}{T} \int_{-T/2}^{T/2} f(t) \cos \left( \frac{2n\pi}{T} t \right) dt \\ b_{n} = \frac{2}{T} \int_{-T/2}^{T/2} f(t) \sin \left( \frac{2n\pi}{T} t \right) dt$$

llamados los coeficientes de Fourier.

Ahora bien, si ya teníamos una expresión de $f$ ¿por qué usar otra más complicada? ¿Qué ventajas ofrece?

La serie $s_{N}$ converge a $f$ en casi todo punto, es decir, cuanto más grande sea $N$ (y, por tanto, más términos de la serie de Fourier usemos), más se parecerá $f$ a $s_{N}$. Esto es importante sobre todo para almacenar funciones y trabajar con ellas computacionalmente de forma mucho más eficiente. En vez de tener que guardar el valor de la función en los puntos, basta con que guardemos un puñado de puntos para tener una muy buena aproximación de $f$ con la que poder trabajar y, por ende, consumimos mucha menos memoria del ordenador.

El problema es que el diablo vive en los pequeños detalles y esta no es una excepción, por desgracia…

Que $s_{N}$ converja a $f$ no nos dice nada sobre la velocidad de esta, puede que tengamos una aproximación decente de $f$ para $N = 10$ o que tengamos que esperar hasta $N = 1.000.000.000.000$ y, claro, si tenemos que esperar hasta coeficientes tan altos, esta idea tan maravillosa de Fourier se vuelve incapaz de ayudarnos con el almacenaje de datos.

En particular, las series de Fourier son sumas de senos y cosenos, funciones demasiado suaves. Por esta razón, cuando las funciones tienen algún punto muy picudo se necesitan demasiados pasos hasta que la serie de Fourier dé aproximaciones decentes de $f$, perdiéndose inevitablemente mucha información.

La pregunta clave que surge ahora, después de todos estos razonamientos, es la siguiente: si cambiamos el tipo de curvas y en vez de usar senos y cosenos recurrimos a otras, ¿podríamos corregir este inconveniente?

Las ondículas pretenden dar la solución. En la década de los 80 Meyer construyó el primer ejemplo de ondículas no-triviales, continuamente diferenciables. Dos años después, Daubechies consiguió describir una familia de ondículas que formaban una base de funciones ortonormales con soporte compacto o, en cristiano, la matemática, si no hizo magia, cerca se quedó. Resultados muy elegantes, que constituyen el pilar de las ondículas hoy en día y resuelven el problema que planteábamos.

Por ejemplo, usando las ondículas de Daubechies $dbn$, dilatándolas y trasladándolas apropiadamente para que estas formen una base, un tecnicismo necesario para poder abarcar todo el rango de funciones que necesitamos, estaríamos expresando nuestra función como una serie que depende de los elementos $dbn$ y no de los

$$\cos \left( \frac{2n\pi}{T} t \right) + \sin \left( \frac{2n\pi}{T} t \right)$$

como teníamos en el modelo de Fourier. Con las $dbn$ nos referimos a la familia de curvas que se puede ver en la siguiente figura:

Compressed sensing

Al comienzo de este texto decíamos que la teoría de ondículas permitía dividir imágenes y sonidos en objetos matemáticos manejables. Esto se consigue gracias al compressed sensing, o muestreo comprimido, una de las aplicaciones más relevantes de las ondículas en nuestro día a día.

Fruto de la colaboración entre Terence Tao y Emmanuel Candès (entre otros), durante la primera década del siglo XXI se produjo una revolución en las técnicas de tratamiento de datos y señales gracias al desarrollo del compressed sensing. Esta teoría es especialmente útil porque permite la reconstrucción eficiente de datos dispersos basados en muy pocas mediciones.

En este artículo queremos explicar cómo funciona esta técnica. Para poder centrarnos en la idea que hay detrás de ella y no perdernos en los tecnicismos, vamos a tomar el ejemplo más sencillo, el de la cámara.

El objetivo de una cámara es, por supuesto, hacer fotos. Ahora bien, es una práctica común que la cámara comprima la imagen. Por ejemplo, si el tamaño inicial de la fotografía es de 2MB sería preferible quedarse con algo queso ocupe menos, por ejemplo 200KB, que es un 10% del tamaño inicial.

La clave detrás de esta idea es que, mientras el espacio de todas las imágenes tiene un valor de 2MB de grados de libertad, el espacio de todas las imágenes interesantes (las partes que contienen los detalles relevantes de la fotografía) es mucho más pequeño y puede almacenarse en un espacio considerablemente menor, si a uno no le importa perder un poco de calidad.

Desde luego, existen varias formas de comprimir imágenes. Empecemos con una un poco ingenua. Supongamos que en nuestra fotografía encontramos unscuadrado monocromático muy grande, por ejemplo de 100x100 píxeles, que son exactamente del mismo color. Si no hiciéramos ninguna compresión, usando una escala de grises 8-bit, almacenar toda la información de este cuadrado requerirían 10.000 bytes cuando, lo único que necesitaríamos, es almacenar la dimensión, la localización y el color usados (que es mucha menos información). Por supuesto, esta idea no nos serviría en la práctica pues no consigue dar resultados satisfactorios para las transiciones abruptas entre dos colores.

En realidad, para resolver este problema en la comunidad científica se ha llegado al consenso de que es mejor no trabajar usando el color medio de cada cuadradito, sino que lo más óptimo es utilizar los desequilibrios medios. Esto es, de media, cuán más intensa es la mitad derecha del cuadradito en comparación con la mitad izquierda del mismo. Y esto resulta que se puede formalizar utilizando sistemas de ondículas, que nos permiten expresar una imagen como la superposición lineal de varias ondículas. En la práctica, se utilizan técnicas más complejas, pero esto es suficiente para entender las ideas detrás del compressed sensing.

Visto esto, volvamos a nuestro ejemplo anterior. La imagen original tiene 2 millones de grados de libertad y, en particular, si uno quiere expresar esta imagen en términos de ondículas, necesitaría 2 millones de ondículas diferentes para poder reconstruirla perfectamente. No obstante, una imagen típica interesante es muy dispersa en una base de ondículas. Es muy posible que no necesitemos más de unas 100.000 ondículas para poder capturar todas las características importantes de la imagen, y que el 1.9 millón de ondículas restantes tan solo contribuyan a una pequeña cantidad de ruido aleatorio, imperceptible para la mayoría de los observadores.

Ahora, si nosotros (o la cámara) supiéramos cuáles son los 100.000 coeficientes de las ondículas que vamos a utilizar, entonces la cámara podría simplemente medir el valor de sólo esos coeficientes y ni siquiera molestarse en intentar obtener el resto. Es posible medir un único coeficiente aplicando un filtro adecuado a la imagen y haciendo una medida de una única intensidad del resultado obtenido. No obstante, la cámara no conoce a priori cuáles son los coeficientes claves, así que tiene que obtener los 2 millones de píxeles, convertir la imagen a una base de ondículas, localizar los 100.000 coeficientes dominantes, almacenarlos y desechar el resto. Este es el momento en el que las matemáticas obran un discreto milagro.

Con esto en mente, la filosofía principal del compressed sensing es esta: si uno necesita sólo 100.000 coeficientes para recuperar la mayor parte de la imagen, ¿por qué no tomar solo 100.000 medidas en lugar de 2 millones? En la práctica se deja un margen de seguridad tomando, por ejemplo, 300.000 medidas. Claro, existe una dificultad evidente, tal y como decíamos antes, la cámara no sabe de antemano qué 100.000 coeficientes de los 2 millones que hay son los importantes que se necesitan guardar. De esta forma, una pregunta que resulta muy interesante es saber qué ocurriría al seleccionar un conjunto completamente diferente de 100.000 (ó 300.000) ondículas. ¿Se perdería toda la información interesante en la imagen?

La solución a esta pregunta es simple y poco intuitiva. Consiste en hacer 300.000 medidas que no tengan nada que ver con la base de ondículas. La idea es generar medidas pseudo-aleatorias, generando al azar 300.000 imágenes, máscaras, y midiendo hasta qué punto se parece a las máscaras la imagen con la que estamos trabajando. Ahora, estas medidas (o correlaciones) entre la imagen y las máscaras serán, con casi toda seguridad, muy pequeñas e impredecibles. Sin embargo, cada una de las 2 millones de ondículas que comprimen la imagen generará su propia firma distintiva dentro de estas medidas aleatorias y, además, (con una probabilidad desorbitadamente alta) cada una de las firmas será distinta. Resulta que la combinación lineal de hasta 100.000 de estas firmas serán distintas. Desde la perspectiva del álgebra lineal, esto significa que dos subespacios de dimensión 100.000 de un espacio de dimensión 300.000 elegidos de forma aleatoria, serán casi siempre disjuntos. Así que en principio es posible recuperar la imagen o, al menos, sus 100.000 componentes más importantes, a partir de estas 300.000 medidas aleatorias.

En esencia, entender una imagen de 2 millones de píxeles en una base de ondículas nos garantiza que, eligiendo sólo 300.000 de estas de forma completamente aleatoria, 100.000 de ellas nos permitirán recuperar la imagen con mucha precisión.

Para rescatar la imagen evitando ruidos habrá que usar algunas técnicas de recuperación de algoritmos no triviales. Pero eso ya es harina de otro costal y, quizás… para otro artículo.

Por último, puede ser interesante repasar algunas de las aplicaciones de esta idea tan abstracta del compressed sensing:

1. Imagen por resonancia magnética: En medicina, una resonancia intenta recuperar una imagen detallada de partes del cuerpo humano a partir de un número grande, pero finito, de medidas. Por el número de medidas necesitadas el proceso es lento para el paciente, pero las técnicas de compressed sensing pueden reducir el número de medidas necesitadas significativamente, llevándonos a procesos más rápidos.
2. Astronomía: Muchos fenómenos astronómicos (por ejemplo los púlsares, estrellas de neutrones con un intenso campo magnético que giran sobre sí mismas) tienen varias frecuencias de oscilación que puede provocar que se dispersen o compriman mucho en distintos dominios de frecuencia. En este caso las técnicas de compressed sensing permiten medir estos fenómenos en el dominio temporal (a partir de datos del telescopio) consiguiendo reconstruir la señal original con precisión incluso a partir de datos incompletos o ruido.
3. Códigos lineales: En este caso el _compressed sensing nos proporciona un método simple para combinar el output de varios transmisores de tal forma que si una fracción importante del output se pierde o se daña, todavía podamos recuperar la transmisión original.

---