El Historial

La idea del filtro de partículas es (en nuestro caso) seguir un objeto a través de un vídeo, por lo que es útil tener una estimación puntual para cada iteración, si guardamos esa iteración podemos realizar muchos "bonitos" cálculos sobre la trayectoria del objeto.

Con esa idea y también la del mínimos esfuerzo me puse a buscar una lista enlazada para guardarlo y me encontré con la libreria estándar de c++ que tiene una interfaz genial para las listas enlazadas y nos evita tener que escribir una cada vez que la necesitamos.

El uso es de lo mas simple:

Declarar una lista:

list < CvPoint >  historial;

Insertar un objeto:

historial.push_back(punto);

Iterar en la lista:

list < CvPoint > ::const_iterator actual = historial.begin();
while(actual!=historial.end())
actual++;

Si después de cada Resampling guardamos el centroide del conjunto de partículas tendremos un historial para hacer todos los cálculos que queramos.

La presentacion

El jueves 13 (13/12/2007) se celebro una reunión para explicar la parte hecha del proyecto y salieron varias ideas que he estado implementando poco a poco:

1. El filtro de partículas debería dar una "estimación" de donde esta el objeto que se esta buscando tras cada iteración, he llamado a esto Centroide, es básicamente una partícula que nos dice la mejor estimación que tiene del objeto para cada frame.
2. Las partículas deberían incorporar una "velocidad" para poder guardar un historial de lo que han hecho en el ultimo movimiento.
3. Para las siguientes pruebas voy a usar unas 100 partículas para que haya menos posibilidades de que ninguna caiga dentro del objeto.
4. Ahora tengo un sintetizador de vídeo que usa opencv, cortesía de Juanjo Pantrigo.

Bueno basándome en esas ideas y aunque con no demasiado tiempo por la cantidad de trabajo que he tenido la ultima semana he preparado un filtro funcional, de momento es muy sencillo y la única función discriminante que usa es: todos los pixeles deben estar a 0 salvo los del objeto.

Como he aprendido a usar el vlc para grabar vídeos desde el escritorio ahí va una de las pruebas que he hecho al filtro:




Aunque no se vea muy bien un cuadro rojo sigue al blanco durante el vídeo de una forma bastante aproximada :P

Implementacion parcial

Esta semana he conseguido una implementación parcial de lo que seria el conjunto de partículas y lo he probado con una imagen fija, la idea esta conseguida pero faltan bastantes mejoras.

La operación mas básica es lanzar las partículas sobre posiciones aleatorias, existe el problema de que ninguna caiga sobre el objeto que estamos buscando, para lo que se me ocurren dos soluciones, iterar hasta que alguna caiga o lanzar un numero mas grande de partículas.


Una vez están todas las partículas iniciadas, debemos discriminar las que han caído sobre el objeto de estudio de las que no, para esto hace falta una función que nos diga que es objeto y que no, en el caso que he probado es muy fácil porque lo que no es objeto esta todo en negro, pero puede no ser tan evidente y habría que hacer por ejemplo un vector de características del objeto. Como la función puede variar y la idea es que el filtro sea reutilizable he definido la función así:

void MultFuncion(IplImage* img,float (*evaluacion)(IplImage* img, Particula p));

Se le pasa un puntero a la función que se encarga de reconocer el objeto y esta función es responsabilidad del usuario del filtro (al menos por ahora).

Lo anterior solo cambia el peso de las partículas, pero lo que necesitamos es que las partículas "mas aptas" tengan hijos de forma proporcional a su peso, esto es lo que hace Resampling, tal como explique en otro post anterior.


Nos falta aplicar la dinámica, por el momento esta definida como sigue:

void Dinamica(int desviacionMax,int ancho, int alto);

La idea es cambiarla para que sea capaz de simular diferentes distribuciones, y para poder hacer experimentos con computación basada en palabras.

No entiendes realmente algo a menos que seas capaz de explicarselo a tu abuela.

Albert Einstein

Fin de la transmisión

El Radar

Los radares suelen usar ondas de radio como dice la wikipedia pero nada nos impide hacernos un radar casero con el lego, la idea es montar el ultrasonido sobre un motor para que gire, en principio 180º y valla tomando mediciones, después de eso lo que hará sera convertir las coordenadas polares que obtenemos en cartesianas, trasladarlo y pintarlo en la pantalla.

Después de un rato pegándome con la pantalla LCD, decidí usar un objeto Graphics, que permite pintar mas cómodamente.

Nota: Los matemáticos usan radianes, los grados son para la bebida, al pasarle grados a una función matemática que espera radianes salen unas cosas muy raras.

La función seno y coseno del API usan la aproximación de Chebyshev-Pade, que esperan radianes.

Esta es una foto de nuestro triunfante radar:


La primera implementación tenia el problema de que no aprovechaba bien la pantalla para mostrar los resultados pero finalmente esta arreglado.

Notas rápidas:

• Se trata de girar el motor e ir tomando medidas con el ultrasonido
• La mínima distancia que puede girar el motor con precisión son 2 grados (en la implementación se usan 3).
• El rango del ultrasonido esta entre 2 y 130 cm aprox.
• obtenemos dos medidas distancia y grados girados por el motor
• x = distancia*cos(grados_girados); y = distancia*sin(grados_girados).
• Las coordenadas en la pantalla son raras (0,0) esta en la esquina superior izquierda.

Aquí el resultado:




1. Un robot no puede hacer daño a un ser humano o, por inacción, permitir que un ser humano sufra daño. Siempre que no se tenga en cuenta el daño cerebral al intentar programarlo.
(visto por ahi)

Lanzando particulas

La idea de hoy es la siguiente, refinar las partículas para poder lanzarlas de forma aleatoria sobre una imagen, hay algunas cosas que hay que tener en cuenta:

• Las partículas deberían tener el mismo tamaño
• No se debe dibujar ninguna partícula hasta que haya terminado el estudio de la imagen!
• Las partículas deben estar enteramente dentro de la imagen

Aquí un resultado improvisado:

Ahora necesito encontrar una función que sea capaz de dar una medida, dada una partícula que tanto se parece su contenido a la imagen que se está buscando, que genere una "firma", algo así como una cadena MD5 que al ser comparada con la del objeto original nos de un porcentaje de concordancia.

Sigo en la búsqueda...

Caracterizacion del Ultrasonido

Aunque en general se dice que el sensor de ultrasonido nos devuelve la posición la realidad es que tiene algún ruido para los valores muy cercanos y muy lejanos, tenemos que contar con ese ruido para poder controlar bien al robot, así que hacen falta algunas pruebas para comprobar en que valores existe ruido y que tan preciso es el sensor.



Esta es una gráfica que representa espacio real frente al espacio medido por el sensor, el sensor es muy preciso para valores entre 2 y 125 cm, pero fuera de esos valores tiene mucho ruido, eso es debido a la forma en que funcionan los ultrasonidos.

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.