Figura 1: Ilustración del problema de la Separación Ciega de Fuentes (BSS). El objetivo es estimar las señales fuentes s1(t) y s2(t) a partir de los registros de los micrófonos (mezclas) x1(t) y x2(t).
Fig. 2: Señales Fuentes y Mezclas en el problema de BSS. Se muestran las funciones de densidad de probabilidad (pdfs) de las señales donde puede observarse que las mezclas tienen pdfs que son mas cercanas a la pdf de Gauss que las de las fuentes.
Fig. 3: El problema de la separación espectral: en cada píxel se registra un espectro que es una combinación lineal de los espectros de los materiales presentes en el píxel. A través de un algoritmo BSS es posible estimar los porcentajes de cada uno de los materiales presentes por píxel.
Fig. 4: Resultado de aplicar el Algoritmo MaxNG a una porción de imagen (50x50 pixeles). a) Imagen RGB, b) Clasificación de pixeles por un método tradicional, c) Fuente 1 (porcentaje de cemento), d) Fuente 2 (porcentaje de ladrillo) y e) Fuente 3 (porcentaje de vegetación).
Fig. 5: Aplicación de BSS a la Radioastronomía. Las separación de fuentes de radiación registradas por el radio-telescopio Planck puede ser ecarada como un problema de separación ciega de fuentes.
Fig. 6: Ejemplo de aplicación de BSS a la radioastronomía. Los mapas de radiación asociados a distintas fuentes (CMB, SYN y DUST) pueden obtenerse buscando el máximo y mínimos de la Entropia en el espacio de los parámetros de separación (detalles en Caiafa, C. F., Kuruoglu, E., & Proto, A. (2006). Maxent 2006 Conference Proceedings. 872, pp. 81 - 88. Paris: AIP.). Las señales utilizadas fueron simuladas y las mezclas fueran generadas con un modelo lineal.
- Descargar artículo
Tópico en Procesamiento de Señales: Separación Ciega de Fuentes y Aplicaciones
Los algoritmos de BSS ("Blind Source Separation - BSS") han sido desarrollados ampliamente durante los últimos 15 años y han sido aplicados con éxito a problemas prácticos en diversas áreas científicas y tecnológicas, a saber: separación de señales acústicas (audio), análisis de señales neuronales en Neurociencias, etc. (Comon & Jutten, 2010). Además, BSS también representa una herramienta muy útil para el procesamiento de imágenes satelitales y en Radioastronomía, dos aplicaciones que abordamos en este artículo.
- Separación Ciega de Fuentes: definición del problema
Consideremos que existen dos fuentes (sources) que producen señales temporales: s1(t) y s2(t). Por ejemplo, este podría ser el caso de dos fuentes sonoras emitiendo señales acústicas. Supongamos que estas fuentes sonoras se encuentran en un ambiente especial sin eco y que colocamos dos micrófonos (sensores) en distintas posiciones en el espacio (Fig. 1). Estos micrófonos registrarán, cada uno, una superposición diferente de las fuentes, es decir:
| x1(t) = a11 s1(t) + a12 s2(t), | (1) |
| x2(t) = a21 s1(t) + a22 s2(t), | (2) |
donde x1(t) y x2(t) son las señales registradas por los micrófonos (mezclas) y los valores de los coeficientes aij dependerán de la geometría de la configuración de fuentes y sensores. Las ecuaciones (1-2) pueden escribirse en forma compacta usando notación matricial de la siguiente manera:
| x(t) = As(t), | (3) |
donde s(t) = [s1(t) s2(t)]T y x(t) = [x1(t) x2(t)]T y A es la matriz de coeficientes o matriz de mezcla. Desde luego la ecuación (3) también puede aplicarse al caso de la mezcla de un número arbitrario N de fuentes y sensores.
El problema de la separación ciega de fuentes (BSS) consiste en recuperar las señales de las fuentes s(t) utilizando solamente los registros capturados por los micrófonos, es decir, a partir de x(t). Está claro que, si se conocieran los coeficientes de mezcla o lo que es lo mismo las distancias relativas entre sensores y fuentes, entonces el problema estaría resuelto gracias al Algebra utilizando la transformación lineal inversa, es decir:
| s(t) = A-1x(t), | (4) |
donde A-1 es la inversa de la matriz de mezcla.
Sin embargo, en los problemas prácticos rara vez se conoce la matriz A y la resolución de este problema "ciego" no es trivial requiriendo la utilización de herramientas matemáticas más sofisticadas. Es interesante observar que muchas de estas ideas matemáticas están basadas en conceptos intuitivos simples tal como intentaremos ilustrar en este artículo.
- Las señales como fuentes de información
Una de las herramientas matemáticas que utilizaremos es la Teoría de Probabilidades. Dada una señal s(t), si observamos sus valores para cada t podremos asignar probabilidades a esos valores de acuerdo a si ellos ocurren muy frecuentemente o, por el contrario, muy esporádicamente. Para hablar en términos matemáticos decimos que una señal s(t) tiene asociada una función de densidad de probabilidad fs(s) ("probability density function - pdf") que la caracteriza. Por ejemplo, en la Fig. 2 podemos observar ejemplos de señales fuentes y sus mezclas con sus correspondientes pdfs asociadas.
El concepto de función de densidad de probabilidad (pdf) tiene aparejada la definición de la Información asociada a dicha variable aleatoria. La Teoría de la Información fue desarrollada por Claude Shannon a partir de su celebrado artículo "A Mathematical Theory of Communication" publicado en 1948 (Shannon, 1948). En ese trabajo se definió a la Entropía H(s) como una medida de la Información de una variable aleatoria s. Básicamente, la Entropía mide que tan impredecible es una señal. Por ejemplo, una señal cuya pdf esté concentrada mayormente en pocos valores será fácilmente predecible y tendrá una Entropía baja.
La Entropía definida por Shannon H(s) tiene propiedades matemáticas útiles. En particular, y en relación con nuestro problema de separación de fuentes podemos mencionar las siguientes:
1- Propiedad 1: La distribución Gaussiana tiene la máxima Entropía de entre todas las distribuciones con idénticas medias e iguales desvíos standards:
| H(w) > H(z), | (5) |
siempre que w sea Gaussiana, z sea no-Gaussiana, y además μw = μz, σw = σz.
2- Propiedad 2: La Entropía de la combinación lineal de variables independientes (no-Gaussianas) normalizada es mayor que las Entropías individuales normalizadas. Es decir, si definimos w = z + y entonces
| H(w/σw) > H(z/σz) y H(w/σw) > H(y/σy), | (6) |
donde σw, σz y σy son los desvíos standard de w, z e y respectivamente y asumimos medias nulas ( μz = μy = 0).
Los aficionados a las matemáticas podrán reconocer en la Propiedad 2 una consecuencia del Teorema del Límite Central1 que establece que, a medida que sumamos más variables independientes y normalizamos el resultado, la distribución resultante se aproxima a la distribución Gaussiana. De hecho, este resultado hace que la distribución Gaussiana aparezca naturalmente en la naturaleza ya que muchos fenómenos en la naturaleza se producen por la combinación de infinidad de procesos independientes.
¿Cómo se relacionan estos resultados matemáticos con nuestro problema de separación de fuentes? A continuación ilustramos como utilizarlos para elaborar algoritmos BSS.
- ¿Cómo identificar las fuentes?
Suponiendo que las fuentes son estadísticamente independientes y tienen distribuciones no-Gaussianas entonces, aplicando las propiedades de la Entropía a la ecuación (3) podemos concluir que las señales en los sensores x1(t) y x2(t) serán mas Gaussianas que las fuentes s1(t) y s2(t).
Intuitivamente podemos decir que la acción de mezclar señales produce señales mas complejas (mas Gaussianas o con más Entropía) y por lo tanto, la forma de recuperar las señales originales es aplicar la operación inversa que haga que las señales fuentes estimadas sean lo menos complejas posibles (menos Gaussianas o con menor Entropía). Éste es el concepto básico sobre el que se desarrollaron los algoritmos de Análisis de Componentes Independientes ("Independet Component Analysis - ICA")(Comon P. , 1994)(Hyvarinen, Karhunen, & Oja, 2001).
¿Pero cómo hacen los algoritmos ICA para recuperar las fuentes?. Para esto observamos en la ecuación (4) que las fuentes pueden ser recuperadas a través de una transformación lineal de las mezclas. El objetivo de un algoritmo de BSS es encontrar la matriz D, tal que las estimaciones de las fuentes se obtenga como
| y(t) = Dx(t), | (7) |
donde observamos que, con D=A-1 obtenemos una estimación exacta de las fuentes (y(t)= s(t)). Muchos algoritmos ICA realizan una búsqueda sobre todas las posibles matrices D seleccionando aquella para la cual las estimaciones de las fuentes y(t) (ecuación (7)) tienen mínima Entropía (son lo menos Gaussianas posibles).
Existen diversas formas de medir el grado no-Gaussianidad o la Entropía a partir de muestras de una señal lo cual permitió el desarrollo de distintos algoritmos ICA. Podríamos decir que el algoritmo más famoso es el FastICA, propuesto por A. Hyvarinen en (Hyvarinen & Oja, 1997) donde la no-Gaussianidad se mide a través del momento estadístico de orden 4 conocido como "kurtosis". Este algoritmo debe su popularidad a que es sencillo y veloz.
Otra familia de algoritmos buscan la matriz D que minimiza la Información Mutua (Shannon, 1948) entre las componentes del vector y(t) ya que durante el proceso de mezcla de señales, no solo se incrementa la Gaussianidad sino que además se aumenta la Información Mutua entre los sensores (Cardoso & Souloumiac, 1996).
La hipótesis de independencia estadística entre las fuentes es válida en muchos escenarios pero hay casos en los cuales no se aplica y como consecuencia los algoritmos ICA pueden no separar las fuentes. Sin embargo, se ha observado que la medida de no-Gaussianidad también es útil para señales fuentes con un tipo especial de dependencia (Caiafa & Proto, 2006)(Caiafa C. F., Salerno, Proto, & Fiumi, 2008).
En (Caiafa & Proto, 2006) se desarrolló un algoritmo BSS denominado MaxNG que permite la separación de señales dependientes e independientes utilizando una medida de la no-Gaussianidad basada en la distancia de funciones L2. En este contexto se definió el Análisis de Componentes Dependientes ("Dependent Component Analysis - DCA") como una generalización de ICA permitiendo la separación de un tipo especial de señales dependientes.
A continuación ilustraremos la utilización de algoritmos de separación de fuentes dependientes en dos casos de estudio derivados de problemas prácticos reales en el procesamiento de imágenes satelitales y en Radioastronomía.
- Aplicación al procesamiento de imágenes satelitales
Actualmente, los sensores ópticos utilizados en satélites son capaces de proveer alta resolución espectral obteniendo imágenes con cientos de canales (hiperespectrales). Pero, desafortunadamente, la resolución espacial está limitada ya que la energía total recibida por el sensor, correspondiente a un pixel, está directamente relacionada con el área relevada, el ancho de banda del sensor y el tiempo de integración. Por lo tanto, lo que en realidad medimos con el sensor es una combinación lineal de los espectros de los materiales presentes en cada píxel (Fig. 3). A su vez, los coeficientes de mezcla de los espectros son los porcentajes de ocupación de los materiales en ese píxel. Éste modelo lineal ha sido validado por mediciones de laboratorio.
En ciertas aplicaciones de sensado remoto es necesario obtener información a nivel subpixel y determinar los porcentajes de ocupación de los distintos materiales presentes en cada píxel. Este problema se conoce como Separación Espectral ("Spectral Unmixing") y puede ser resuelto aplicando algoritmos BSS.
Mas específicamente, en el contexto de BSS en la ecuación (2) la matriz de mezcla A contiene en sus columnas los espectros de los distintos materiales (ladrillo, césped, etc) y el vector s(t) contiene los porcentajes de ocupación de cada uno de los materiales en el pixel indexado por t.
Dado que en este caso las fuentes corresponden a fracciones (porcentajes), éstos cumplen con una restricción y es que la suma de las fuentes da 1 (100%). Esta restricción impone una dependencia estadística entre las fuentes y hace que los algoritmos ICA no funcionen correctamente o lo hagan parcialmente.
En (Caiafa C. F., Salerno, Proto, & Fiumi, 2008)(Caiafa, Salerno, & Proto, 2007; Caiafa C. , Salerno, Proto, & Fiumi, 2006) hemos aplicado el algoritmo MaxNG al procesamiento de imágenes satelitales hiperespectrales capturadas por el instrumento MIVIS del Airborne Laboratory for Environmental Research, CNR, Roma (Italia). Se trabajó sobre una imagen de 540x337 pixeles con 102 bandas: canales 1-20 (0.43-0.83 μm), canales 21-28 (1.15-1.55 μm), canales 29-92 (2.00-2.50 μm), canales 93-102 (8.20-12.70μm).
En la Fig. 4 se muestran los resultados de aplicar el algoritmo MaxNG una porción de la imagen espectral correspondiente al Palazzo Corsini alla Lungara y el Jardín Botánico en Roma. En las Fig. 4 c)-e) se muestran las imágenes correspondientes a los porcentajes de ocupación de los materiales predominantes donde cuatro materiales han sido detectados (cemento, ladrillo y vegetación). Puede verse la correspondencia con la clasificación de los pixeles como pertenecientemente a una clase efectuados por un método clásico de clasificación de pixeles.
- Separación de fuentes de radiación en Radioastronomía
El satélite Planck de la Agencia Espacial Europea (ESA) (http://www.esa.int/planck) ha sido puesto en órbita en 2009 generando gran expectativa en la comunidad de astrónomos y astrofísicos en todo el mundo. Al igual que en otras misiones anteriores de NASA como WMAP (map.gsfc.nasa.gov) o COBE (aether.lbl.gov/www/projects/cobe/), el principal objetivo de la misión es reconstruir la radiación cósmica de fondo ("Cosmic Microwave Background - CMB") que es la prueba más relevante del modelo "hot big-bang", una de las teorías más aceptadas sobre el origen del Universo. Según esta teoría, el CMB sería la radiación producida por la explosión que dio origen al Universo.
Por lo tanto, es muy importante disponer de un relevamiento del CMB en todo el cielo ya que daría información vital sobre los orígenes del Universo. Además, las inhomogeneidades del CMB dieron origen a las galaxias que hoy existen y por lo tanto podría también explicar la topología del Universo.
Sin embargo, un problema fundamental con el que se encuentran los científicos al momento de analizar las imágenes capturadas por los sensores del satélite Planck es que la radicación CMB se encuentra contaminada por otras fuentes de radiación, básicamente radiaciones cercanas y fuentes de radiación extragalácticas, además del ruido propio del instrumento.
En (Baccigalupi, et al., 2000) se propuso resolver la extracción del CMB como un problema de BSS utilizando algoritmos ICA ya que la radiación medida por cada sensor es una combinación lineal de las distintas fuentes de radicación (Fig. 5). Sin embargo existen características especiales que hacen difícil de resolver por algoritmos clásicos porque las señales no son independientes y la fuente CMB es prácticamente Gaussiana.
En (Caiafa, Kuruoglu, & Proto, 2006) desarrollamos un algoritmo basado en las ideas usadas en MaxNG y fue testeado con señales generadas sintéticamente por los equipos de la misión Planck en Italia. Una característica particular de este algoritmo es que logra la separación del CMB buscando el máximo2 de la Entropía debido a la característica Gaussiana de esta fuente. Por el contrario el resto de las fuentes (no-Gaussianas) se logra buscando los mínimos de la Entropía como se muestra en la Fig. 6. a). Es así que este nuevo algoritmo fue denominado MiniMax Entropy. En las Fig. 6. b) - d) se muestran las imágenes fuentes originales, las mezclas generadas con el modelo lineal y las estimaciones de las fuentes obtenidas con este algoritmo.
- Conclusiones finales
La separación ciega de fuentes (BSS) es un problema que aparece naturalmente en distintas aplicaciones de la Astronomía, de sensado remoto y otras áreas científicas y tecnológicas. En este pequeño artículo, además de describir el problema desde el punto de vista matemático, hemos visto cuales son los principales conceptos y herramientas que permiten resolver la separación de fuentes. La Entropía y Gaussianidad de señales son conceptos sofisticados derivados de la Teoría de la Información, sin embargo tienen una interpretación accesible desde la intuición. Las técnicas aquí presentadas son de gran interés en la actualidad teniendo en cuenta que los instrumentos modernos utilizados por ejemplo en la Astronomía proveen grandes volúmenes de datos que requieren ser procesados para poder extraer información útil de ellos.
- Sobre el autor:
El Dr. César F. Caiafa es Ingeniero Electrónico, recibido en la Facultad de Ingeniería de la Universidad de Buenos Aires (FI-UBA), entidad donde también realizó su doctorado. Se incorporó al plantel científico del IAR en noviembre del año 2010, luego de realizar trabajos de investigación en el Laboratorio de ISTI - CNR, Pisa, Italia y en el Instituto de Ciencia del Cerebro RIKEN, Saitama, Japón.
- Bibliografía
- Baccigalupi, C., Bedini, L., Burigana, C., Zotti, G. D., Farusi, A., Maino, D., et al. (2000). Neural networks and the separation of cosmic microwave background and astrophysical signals in sky maps. Monthly Notices of the Royal Astronomical Society , 318, 769 - 780.
- Bell, A. J., & Sejnowski, T. J. (1995). A Non-linear Information Maximisation Algorithm that Performs Blind Separation . Advances in Neural Information Processing Systems , 7, 467 - 474.
- Caiafa, C. F., & Proto, A. (2006). Separation of Statistically Dependent Sources Using an L2-distance Non-gaussianity Measure. Signal Processing , 86 (11), 3404 - 3420.
- Caiafa, C. F., Kuruoglu, E., & Proto, A. (2006). A Minimax Entropy Method for Blind Separation of Dependent Components in Astrophysical Images. Maxent 2006 Conference Proceedings. 872, pp. 81 - 88. Paris: AIP.
- Caiafa, C. F., Salerno, E., Proto, A., & Fiumi, L. (2008). Blind Spectral Unmixing by Local Maximization of Non-gaussianity. Signal Processing , 88 (1), 50 - 68.
- Caiafa, C. R., Salerno, E., & Proto, A. (2007). Blind Source Separation Applied to Spectral Unmixing: Comparing Different Measures of Nongaussianity. Lecture Notes of Computer Science (LNCS) , 4694, 1 - 8.
- Caiafa, C., Salerno, E., Proto, A., & Fiumi, L. (2006). Dependent Component Analysis as a Tool for Blind Spectral Unmixing of Remote Sensed Images. EUSIPCO 2006 (pp. 1- 8). Florence: EURASIP.
- Cardoso, J. F., & Souloumiac, A. (1996). Jacobi angles for simultaneous diagonalization . SIAM Journal of Matrix Analysis and Applications , 17 (1), 161 - 164.
- Comon, J., & Jutten, C. (2010). Handbook of Blind Source Separation: Inde- pendent Component Analysis and Applications. Academic Press.
- Comon, P. (1994). Independent Component Analysis, a new concept? . Signal Processing , 36 (3), 287 - 314.
- Hyvarinen, A., & Oja, E. (1997). A fast fixed-point algorithm for independent component analysis. Neural Computation , 9 (7), 1483 - 1492.
- Hyvarinen, A., Karhunen, J., & Oja, E. (2001). Independent Component Analysis. John Wiley & Sons.
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal , 27, 379-423.
1 El Teorema del Límite Central fue postulado por primera vez en 1773 por el matemático francés de Moivre y republicado en 1812 por el famoso matemático francés Laplace.
2 Los máximos y mínimos se buscan en el espacio de los parámetros de separación que en este caso es bidimensional (θ1, θ2) (detalles en Caiafa, C. F., Kuruoglu, E., & Proto, A. (2006). Maxent 2006 Conference Proceedings. 872, pp. 81 - 88. Paris: AIP.).
