How important are scales in EEG signals?

Análisis de EEG en escalas

¿ Si vemos un objeto desde una distancia específica, cómo podemos hacer para poder seguir visualizandolo aún cuando nos acerquemos o alejemos, o cuando la escala cambie?

¿ La percepción de información se mantiene aún cuando se cambia la escala sensorial mediante la cual se adquiere esa información? Los seres humanos somos muy buenos para percibir información que sea covariante (que varia con) o invariante a la escala pero, ¿ es posible modelarlo, identificarlo y reproducirlo computacionalmente?

La respuesta es que sí, y existe un poderoso trabajo que se desarrolló en la decada del 90 dentro del área de Computer Vision, donde se establecieron las bases tanto matemáticas como algorítmicas de lo que implica la invariabilidad en la escala.

Espacio de Escalas

En esto es dónde aparece la técnica de SIFT y todos sus técnicas hermanas que explotan la misma idea.

Similar al método de Harris, SIFT se basa en identificar puntos clave, keypoints, característicos en las imágenes que aporten información relevante. Justamente esta información viene dada por tasas de cambios vectoriales, y precisamente, como en el caso de Harris, los corners conllevan parte de esta información.

Sin embargo, en Harris, no es posible identificar corners que no representen cambios en el Hessiano simplemente porque esos cambios se producen en una escala que no queda registrada en esa variabilidad, es decir, son imperceptibles.

Trabajos de Lindeberg, resumido en su autoreferencial libro (Scale Space Theory and Computer Vision, 1994), Lowe y Mikilajczyk 2002 y otros, establecieron que utilizando un kernel Gaussiano, convolucionado con una imagen a diferentes valores de sigma, resampleando (decimation) la imagen, y estudiando el comportamiento variacional de la imagen, ahora en este nuevo espacio, permite justamente buscar caracterìsticas que sí tengan en cuenta la escala. Posteriormente se establecieron formalismos y axiomas sobre los espacios de escala y su aplicación a cualquier tipo de señales y se cimientaron las bases de Scale Space Theory (MultiScale Signal Analysis and Modelling, Shen/Zayed). En definitiva, todo un mundo (que curiosamente ha tenido poca actividad reciente).

Imágenes binarias.

El paper de Lowe del 2004 de SIFT, tiene más de 4000 citas en Google Scholar y existen míriadas de modificacones y variantes del algoritmo base (se encuentra patentado en EEUU http://www.google.com/patents/US6711293 para uso comercial). Sin embargo, “as far as I am aware of” no hay demasiados trabajos que exploren las particularidades de la aplicación de SIFT para imagenes binarias. De hecho, no encontré ninguno.

De la experimentación, surgieron dos puntos importantes:

1. Utilizando la misma analogía de la difusión anisotrópica, y la solución a la Heat Equation, cuando las imagenes son binarias (y particularmente Sparse, como son las de las señales que veremos más adelante), el sistema se queda “sin energía”, “sin calor” rapidamente (i.e. la imagen queda con todos los pixeles en cero rapidamente). Parecería que se necesita alguna manera de conservar algo de la energía.
2. El segundo punto también relacionado, es que utilizando los parámetros estándar de SIFT, en cuanto a la dimensión del espacio de escalas y los valores para sigma, se accede a valores de escala sin sentido, donde ya no se aprecia ningún tipo de información. Se requiere entonces de una parametrización del espacio diferente.

Señales de EEG

Si se utilizan señales de EEG para la construcción de imágenes binarias, los ‘plots’ de esas señales, es posible implementar métodos de identificación y clasificación de características sobre imágenes especificos de Computer Vision, que a su vez, permitan identificar y clasificar las propias señales que los generan (Santos, Villar, Ramele, CLAIB2014).

Así por ejemplo, a una imagen típica de P300, que luce así:

se la puede procesar para buscar información que permite justamente identificar el patrón característico de una señal de P300. Es un método de procesar las señales de forma indirecta, pero que aborda el problema desde una dirección diferente.

Utilizando así el algoritmo descripto en la referencia antes mencionada, se pueden generar imagenes plots de las señales y procesarlas con técnicas de exploración del espacio de escalas, como SIFT. Las técnicas de procesamiento de imágenes tienen varios años de lucha contra la performance por lo que además son ideales para el procesamiento de información en tiempo-real, como es en el caso del procesamiento de señales de EEG para aplicaciones de Brain Computer Interfaces.

Handmade Sift

Para intentar abordar este problema de identificación, utilizando técnicas basadas en los mismos mecanismos que SIFT, pero buscando una implementación rápida, alternativa y que considere algunas de las particularidades del tipo de imágenes construídas, podemos hacer como Confuccio e intenar hacerlo a mano en un programa

El programa se construyó en C++ utilizando las rápidas y eficientes librerías de OpenCV, integrado con la STL de C++ y sobre la plataforma portable de Qt. Hace lo siguiente: genera una señal aleatoria (distribución uniforme con la mitad de la altura de imagen como desvio estándard), similar a una señal de EEG. A esta señal, aleatoriamente, le agrega una señal objetivo característica de once puntos, con la semblanza similar a la estructura de P300:

(la imagen aparece invertida, ya que el (0,0) en las imágenes se encuentra en el ángulo superior izquierdo y crece de arriba hacia abajo, de izquierda a derecha)

Cada vez que se completan las muestras necesarias para completar una imagen, arranca el algoritmo de procesamiento que busca identificar los keypoints más importantes. Para esto hace lo siguiente:

• Construye el espacio de escala, pero usando como base sigma=sqrt(2)/2. La siguiente escala es sigma * k, siendo k = sqrt(2) (como sugiere Lowe). El tamaño de la ventana (s) es s=8 sigma + 1, y al igual que en el algoritmo estándar se calculan 5 escalas por octava.
• OpenCV necesita que el tamaño del kernel gaussiano sea impar, por lo que se ajusta si es necesario.
• Debido al punto (1) mencionado arriba, cuando se “decima la imagen” (usando la técnica sugerida por Lowe, de cada 4 pixels me quedo con 2), se “calienta” la imagen aplicando un threshold a todos los valores por arriba de el valor máximo encontrado menos un desvio estándar.
• Debido al punto (2) mencionado arriba, se utilizan 2 octavas (en vez de 4).
• Se calculan los 2 DoG en base a las pirámides de imágenes (de las 5 escalas, se obtienen 4 DoG)
• Sobre las dos DoG del medio, se buscan los k-máximos valores, y esos valores se rotulan como posibles keypoints.
• El algoritmo busca un máximo global, y recursivamente busca otro máximo global excluyendo al encontrado y así sucesivamente hasta alcanzar el número específico por parámetro de keypoints a buscar.

Experimentación

Para poder probar los diferentes métodos y analizar sus diferencias, en relación al problema en cuestión, se procedió a generar aleatoriamente la curva característica de P300, y ruído en forma aleatoria con una varianza incremental (hasta llegar a la mitad de la altura de la imagen). En base a eso, se estima el SNR, como la proporción de sample points que forma parte de la señal de P300, sobre la cantidad de puntos que son ruído.

Finalmente, se considera un hit, cuando el Keypoint es localizado dentro de un parche de 10x10 de donde efectivamente está localizado.

Resultados

OpenCV tiene varios métodos de extracción de características similares a SIFT, así que se experimentaron con algunos de ellos.

Los resultados de los experimentos realizados se resumen en el siguiente gráfico:

• FAST: Juego de palabras para un método que apunta a la velocidad. Se identifican los corners e las imagénes donde el punto central sea más brillante que todos los de alrededor, interpretando a todos como los ubicados a un radio de 3 del centro y posicionados en 16 divisiones de ángulos.
• SURF: Surf es similar a SIFT, pero se basa en las Diferencias de boxes DoB para aproximar las derivadas del Hessiano (en ambas direcciones y las dos combinadas). Al usar kernels de convolución, el algoritmo es muy rápido.

Algoritmo	Descriptores	Hits
SIFT
SURF
FAST
Handmade SIFT

Conclusiones

Visto y Considerando: SIFT, SURF y FAST, generán más descriptores a medida que la SNR disminuye, alcanza el pico máximo cuando se aproxima a cero (altísima proporción de ruído en la señal). SIFT además es el que tiene la mayor cantidad de descriptores cuando la señal es muy aleatoria: mucha variabilidad que representa más información. Adicionalmente, la cantidad de descriptores de SIFT es la más representativa del contenido informacional de la imágen. El método “handmade” no varía la cantidad de descriptores ya que esta es fija (se buscan los k-máximos).

SIFT, SURF y el método detallado en esta entrada, ubican descriptores en el perfil de la señal de P300 cuando el ruído es bajo o nulo (altos hits). SURF particularmente lo hace mucho más rápido y sin tener que variar parámetros por default como sí ocurre en SIFT (edge-threshold). FAST por otro lado, no lo identifica tan directamente y establece como keypoints lugares de la señal donde no aparece ninguna variación.

En definitiva, incluso con una implementación rudimentaria de identificación de keypoints en una imagen de un plot de una señal, puede observarse ya la posibilidad de localizar perfiles específicos que pueden corresponder a un evento particular que los genere, caracterizarlos y posteriormente identificarlos.

Agua de otro costal, sería la propia interpretación y clasificación de los descriptores generados por cada uno de estos métodos.

Código de BciSift

https://github.com/faturita/BciSift

Referencias

Libros

• Szeliski, Computer Vision, 2010, Springer
• Bradski, Learning Open CV, 2013, OReilly
• Laganiere, OpenCV 2 Computer Vision Application Programming Cookbook, Packt Publishing
• Lindeberg.Scale Space Theory in Computer Vision, 1994, Springer
• Viergever.Gaussian Scale Space Theory,1997, Springer
• Front-End vision and Multi-Scale Image Analysis: Multi-Scale Computer Vision theory and Applications, written in Mathematica, Bart M.ter Haar Romeny,2003, Springer
• Shen, Zayed,Multiscale Signal Analysis and Modelling, 2013, Springer

Online

• Material de un curso de bioingeniería sobre espacios escalares:
• http://www.stat.wisc.edu/~mchung/teaching/MIA/
• http://www.stat.wisc.edu/~mchung/teaching/MIA/reading/
• Excelente implementaión de SIFT a mano con OpenCV:https://github.com/aishack/sift/blob/master/SIFT.cpp, con un blog detallado: http://www.aishack.in/tutorials/sift-scale-invariant-feature-transform-introduction/
• SIFT Multithreading: http://www.vlfeat.org/api/sift.html
• OpenCV Drawing functions usando Bresenham y otras referencias de OpenCV
• http://docs.opencv.org/modules/core/doc/drawing_functions.html
• http://stackoverflow.com/questions/20314524/c-opencv-image-sending-through-socket
• http://docs.opencv.org/doc/tutorials/introduction/display_image/display_image.html
• Scale Space Theory http://en.wikipedia.org/wiki/Scale_space
• http://en.wikipedia.org/wiki/Scale_space_implementation
• http://www.scholarpedia.org/article/Scale_Invariant_Feature_Transform
• Scale Space in Signals http://fr.mathworks.com/matlabcentral/fileexchange/42927-pickpeaks-v-select-display-

Implementación de pirámides en OpenCV

http://docs.opencv.org/doc/tutorials/imgproc/pyramids/pyramids.html

VLFeat

I will check what kind of information is important for SIFT binary image processing.

(I will check later what else I can do, but focus striclty on that)

git clone git://github.com/vlfeat/vlfeat.git

$ nmake /f Makefile.mak # for the Windows 64 target $ nmake /f Makefile.mak ARCH=win32 # for the Windows 32 target

( desde una consola de vc 2010)

OpenCV VlFeat intgration

Usarlo desde vlfeat opencv http://stackoverflow.com/questions/7927105/how-to-convert-an-opencv-cvmat-into-a-float-that-can-be-fed-into-vlfeat-vl-ds