Programando Particulas

Mi tarea últimamente ha sido programar las partículas, aunque no he tenido mucho tiempo esta semana por mis "múltiples ocupaciones", en una primera aproximación tengo que hacer tres clases, una para la partícula, otra para un conjunto de partículas que implemente las operaciones normales de conjuntos de partículas y otra de filtro de partículas:


El diagrama es algo chapucero, solo es para dar una idea de lo que estoy intentando hacer.

Aquí una simulación con varias partículas usando valores aleatorios:


Algo que tengo que pensar es como representar el conocimiento sobre la posición siguiente de la partícula conocida la actual.

El mundo de las particulas (4)

La ultima de las operaciones básicas sobre partículas se llama resampling (¿remuestreo?), esto viene de la idea de que una distribución de probabilidad p(x) se puede representar de muchas formas, pero algunas son mas eficientes que otras, esto tiene su definición y explicación matemática (que me salto así porque si).

La idea clave es que para que una representacion sea eficiente la mayoría de las partículas deberían tener pesos iguales, y el resampling es una forma de conseguirlo.

Supongamos que tenemos un conjunto de partículas S, después de aplicar el resampling obtendremos otro S' que sera como sigue:



S' sera otro conjunto de partículas con:

con probabilidad


Donde escoger es independiente cada vez.

Tambien se puede hacer resampling determinista, es decir que el número de partículas escogidas es directamente proporcional al peso de las antiguas sin ninguna aleatoriedad, eso presenta algún problema matemático con el que como no nos encontraremos haremos como que no importa.

Supongamos que tenemos un conjunto de partículas S como de costumbre y vamos a definir uno S' después de hacer un resampling determinista, antes tenemos que definir los pesos acumulados como sigue:



Entonces obtendremos un S' cuyas partículas serán:

donde es el j mas pequeño tal que


Mas gráficamente:


El resultado de la operación seria algo similar a esto:

El Bump'n go Car

El Bump'n go Car es un coche de juguete que al chocarse contra una pared retrocede y luego gira hacia un lado para posteriormente seguir avanzando, así da la impresión de ser "inteligente" por esquivar de alguna forma los obstáculos, esta es la primera idea para construir con el NXT.




Este es el modelo que he montado para probarlo, aunque intente que el sensor de choque estuviese al otro lado me daba algunos problemas porque no detectaba bien los choques así que finalmente he seguido el manual de lego.

Problemas: No conseguía que funcionase el nxjupload en casa ni poder hacer el ant de LejOS, finalmente encontré dos problemas, no tenia permisos para acceder al usb y faltaba la librería libbluetooth??? aunque yo solo subo las cosas por cable usb pero por fin todo funciona.



Por ultimo el vídeo del robot en acción.

Lego NXT

Lo primero para empezar es familiarizarse con el robot, el NXT es un robot controlado por un brick fabricado por lego, las características técnicas son:

• 32-bit ARM7 microcontroller
• 256 Kbytes FLASH, 64 Kbytes RAM
• 8-bit AVR microcontroller
• 4 Kbytes FLASH, 512 Byte RAM
• Bluetooth wireless communication (Bluetooth Class II V2.0 compliant)
• USB full speed port (12 Mbit/s)
• 4 input ports, 6-wire cable digital platform (One port includes a IEC 61158 Type 4/EN 50 170 compliant expansion port for future use)
• 3 output ports, 6-wire cable digital platform
• 100 x 64 pixel LCD graphical display
• Loudspeaker - 8 kHz sound quality. Sound channel with 8-bit resolution and 2-16 KHz sample rate.
• Power source: 6 AA batteries

Copiado y pegado directamente de la página oficial, una de las primeras cosas que me llamo la atención es el micro que tiene, es el mismo que el de mi Nintendo DS, cosa interesante por algún proyecto que tengo para la DS :P

La primera practica fue familiarizarnos con el API y con los sensores, escribir por la pantalla algunos valores de los sensores etc, interesante para empezar pero poco vistoso (así que no hay vídeo).

Algunas cosas raras son que la jvm no tiene recogedor de basura, (algunos dicen que java sin recogedor de basura no es java), de todas formas el LejOS esta muy conseguido y te deja tocar mas a bajo nivel que el sistema de Lego que es mas visual.

El mundo de las particulas (3)

Aplicando la dinamica, esta es la segunda operación básica sobre una partícula, la idea es que tenemos alguna idea de donde va a estar la partícula en un instante t+1 si sabemos donde estaba en el instante t, esto lo expresamos con una distribución de probabilidades como de costumbre.

Tenemos nuestro conjunto de partículas y una función de densidad:



La operación nos devuelve otro conjunto de partículas:



La idea es que las partículas se dispersen siguiendo la función de densidad que hemos dado, esa función representa lo que sabemos del movimiento, si no sabemos nada sera la distribución uniforme aunque parece una buena idea usar una Gausiana, habrá que probar que funciona mejor.



En el vídeo se aplica una dinámica sobre las partículas para simular un fluido, impresiona bastante, es para otro uso pero la idea es la misma o al menos eso parece porque solo he podido ver el vídeo y no la implementación.

El mundo de las particulas (2)

Sobre un conjunto de partículas se pueden hacer operaciones, la mas simple es multiplicar por una función continua y no negativa, esto consigue el efecto de mantener la situación de las partículas dentro de nuestro espacio pero modifica su peso para que sea proporcional a la función por la que hemos multiplicado.

Sea nuestro conjunto de partículas S definido en nuestro espacio :

Y una función h(x) continua, no negativa y acotada lejos de 0.

La multiplicación por una función define un nuevo conjunto de partículas como el que sigue:




Esto tiene la propiedad de representar la distribución de probabilidad que representaba la partícula multiplicada por la función h(x).

Este dibujo muestra lo que sucedería, las partículas se quedan en el mismo lugar pero sus pesos cambian para que sean proporcionales a la función, (esta hecho con Inkscape).

Si nuestra función es por ejemplo asignar a cada partícula el numero de pixels del objeto que estamos siguiendo que caen dentro de la partícula esta función nos empieza a ser útil así que ahora tengo que programarlo todo.

Fin de la transmisión

El mundo de las particulas (1)

En mi libro pone que la definición de una partícula es como sigue:



x pertenece a nuestro espacio de estudio y el peso esta normalizado entre 0 y 1, así que podemos usar las partículas para delimitar regiones de espacio y darles un peso a unas con relación a las otras.

Así que seguramente tengamos que usar varias partículas, algo como un conjunto de partículas:



La idea es usar estos conjuntos de partículas para aproximar distribuciones de probabilidades, si dibujamos cada partícula de forma independiente desde la distribución uniforme y le damos el peso 1/n y si el numero de partículas n es grande se puede demostrar que el conjunto de partículas sera aproximadamente lo mismo que una muestra aleatoria de la distribución de probabilidades dada, en este caso la uniforme, eso se escribe así:

Rectangulo sobre la imagen

Otra de las cosas que tengo que hacer es dibujar un rectángulo sobre la imagen en estudio, esto es importante aunque sea sencillo porque sirve para representar a las partículas y conjuntos de partículas, que definíamos de esta forma tan rara:




Donde X pertenece al espacio en estudio, por lo que necesitamos algo que nos permita dividir el espacio, en los libros de teoría suelen venir círculos, pero es mas difícil contar píxeles dentro de un circulo así que parece mejor usar rectángulos, así que una partícula seria:



y se puede representar en pantalla por un rectángulo, para visualizar el peso de una partícula se podría usar por ejemplo un código de colores.

Aquí un ejemplo de como he pintado un rectángulo sobre la rana del post anterior:

void cvRectangle( CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color,
int thickness=1, int line_type=8, int shift=0 );

Restando Imagenes

Para encontrar una imagen en una secuencia se pueden hacer muchas cosas pero una de las mas sencillas si conocemos el fondo es restar las dos imagenes, esto nos devolvera una imagen de nuestro objeto con los colores un poco raros.

La idea principal es ir recorriendo a la vez dos imagenes y restando pixel a pixel el fondo de la imagen que usamos, esto puede dar valores negativos por lo que habra que ajustarlos, necesitamos tambien que las imagenes tengan el mismo tamaño:



Que en algoritmo seria lo siguiente:



Usando opencv se puede hacer de una forma mucho mas facil ya que esta implementado:

cvSub(img1,img2,resta,NULL );

Pequeños avances

Usando la pagina de Introduction to programming with opencv he dado mis primeros pasos con el tratamiento de imagenes, en el ejemplo de la pagina se enseñaba como sacar el negativo de una imagen, la idea es ir recorriendo la imagen y cambiar pixel al pixel el valor actual por el contrario que en rgb es 255-actual.





El siguiente paso es convertir la imagen a tonos de gris, si sumamos el valor de todos los canales y dividimos por el numero de canales saldra gris, lo malo es que la imagen aun tiene 3 canales y eso no es lo que yo queria.




Usando las cosas que vienen en la libreria sale todo mejor

1) Definirse otra imagen para guardar la transformacion

IplImage* bw = 0;

2) Crear la imagen del mismo tamaño que el original en tonos de gris

CvSize tam = cvSize(width,height);
bw = cvCreateImage(tam,IPL_DEPTH_8U,1);

3) Convertirla en gris

cvCvtColor(img ,bw, CV_RGB2GRAY);

Que es el filtro de Kalman

Es un algoritmo que permite estimar el estado de un sistema dinámico lineal que no podemos medir aunque este sometido al ruido blanco.

Tenemos que tener el ruido blanco normalizado de tal forma que la media sea 0 y la varianza un valor conocido Q.

La idea es estimar un estado de un proceso que esta gobernado por la siguiente ecuación:



Usando nuestras medidas que son:



Donde y son ruido blanco aditivo que sigue una distribucion normal:




A es una matriz n x n que relaciona el estado en el paso k-1 con el estado en el paso k, en ausencia de ruido y de la función de guía que queremos aproximar.

B es una matriz n x l que relaciona el factor de control opcional u con el estado x, .

H es una matriz m x n en la ecuación de medida que relaciona el estado con la medida .

La idea final es encontrar una ecuación que compute el estimado a posteriori a partir de una combinación lineal de el estimado a priori y la diferencia entre el estimado actual y la predicción de la medida.



K es una matriz n x m escogida para que minimice el error de la covarianza a posteriori.

Las ecuaciones del filtro de Kalman se clasifican por actualización del tiempo y actualización de la medida, las ecuaciones de actualización de tiempo proyectan los datos actuales para conseguir los a priori de tiempo t+1y las de actualización de la medida incorporan las medidas nuevas a las a priori para conseguir las a posteriori.

Toda esa frase es equivalente a un dibujito:











Todo esto da bastante miedico pero el propósito principal era comprobar que al menos algo había entendido y que el script para escribir en latex había funcionado, y creo que de momento la misión ha sido completada.

De todas formas el original asusta mas
Fin de la transmisión.