Porcentajes de acierto

He hecho un modulo nuevo que mide los porcentajes de acierto del filtro con respecto del video, la forma de acierto se corresponde con el numero de pixels del objeto que se encuentran en la zona pronosticada por el filtro, de este modo si el objeto tiene 1600 pixels y dentro de la zona caen los 1600 pixels el acierto sera del 100%.

Existe el problema de que cuando el objeto está perdido la zona pronosticada por el filtro va creciendo, debido a la perdida de confianza en la prediccion, aun asi si el objeto entero esta dentro de dicha zona el acierto sera del 100%, lo que no parece muy logico.

Hay que buscar una formula que tenga en cuenta que estadisticamente existe una posibilidad de que el objeto caiga en una zona de la pantalla que crece proporcionalmente a la zona de la pantalla observada y sustraer dicha probabilidad de nuestro calculo.

Haciendo diagramas

Para hacer un proyecto medianamente grande hacen falta muchos diagramas, aunque en principio estaban casi todos en papel los he ido pasando usando Dia.

Como se ve cada modulo salvo el historial tiene su modulo de pruebas que ha sido usado durante la creación del modulo para probar su funcionamiento.

En este diagrama se ven las funciones y atributos importantes de cada clase omitiendo los de las clases de pruebas ya que una vez creado el modulo y probado no influyen mas en el software creado.


Continuo con la memoria.

Porque la interpolación no fue una buena idea

Mientras que estamos interpolando la cosa va bien y la operacion es bastante precisa, pero en nuestro problema en general no necesitamos interpolar nada sino extrapolar, es decir que tenemos que averiguar que pasara en el futuro.

Esto es bastante mas dificil de lo que parece por muchas razones, la primera y mas antiintuitiva es que no se puede interpolar directamente y en funcion de x ya que tampoco tenemos estimacion de como crece x asi que nos quedan dos opciones:

interpolar x e y en funcion de t (por ejemplo el numero del frame en que estamos).
interpolar x en funcion de t e y en funcion de x.

Esto no es demasiado problema pero vamos perdiendo precision. El verdadero problema es que el polinomio se ajusta muy bien entre los n puntos que le damos, sin embargo predecir lo que hara la funcion a partir de ahi no es facil.

Algunos ejemplos:


En la zona en que se interpola las funciones coinciden, pero luego el polinomio crece mucho mas rápido por lo que la estimación es cada vez peor.


Para esta línea la estimación es casi perfecta, pero para conseguir esto fue necesario probar diferentes separaciones entre puntos y grados del polinomio, este en concreto tiene grado 4 y los puntos han sido tomados cada 5t.


Este es un caso extremadamente malo en que la funcion de estimacion crece de forma exponencial a diferencia de la original que es lineal.

Otro ejemplo de funciones que crecen a diferente velocidad.

Lo importante a darse cuenta es que dependemos de los puntos tomados, la separación entre ellos, la función original y el grado del polinomio usado y los parámetros que son buenos para una función original no lo son para otra, de modo que tendríamos que dejar al programa que decida, esto es un montón de trabajo y computo.

La idea ahora es usar algún tipo de componente derivativa dentro de la dinámica inercial para suplir esto que nos ayude a seguir objetos en trayectoria curva y no complique excesivamente las cosas para aquellos que siguen una recta.

Incertidumbre

Cuando se pierde de vista un objeto podemos hacer predicciones a cerca de donde esta, pero lo cierto es que nuestra incertidumbre aumenta con el tiempo que lleva el objeto fuera de nuestro alcance y hay que representarlo de alguna manera.

Si estamos trabajando en periodos de tiempo discretos lo mas fácil es poner la incertidumbre en función del tiempo, pero como lo que queremos hacer es representarlo mas gráficamente puede que se nos ocurra por ejemplo aumentar el tamaño del centroide de la estimación en uno por cada instante t que lleve perdido.

Supongamos que el centroide es un cuadrado, y que es de lado 40, esto implica que si perdemos nuestro objeto durante 40 instantes de tiempo el cuadrado sera el doble de grande (cubrirá 4 veces mas área).

Lo cierto es que no sabemos en general a que velocidad estamos perdiendo precisión por lo que tenemos que comprobarlo experimentalmente, después de unas cuantas pruebas he obtenido que si aumento el tamaño del cuadrado en proporción 2:1 con respecto al tiempo que lleva el objeto perdido se consiguen resultados aceptables.



También he inicializado el generador de pseudoaletorios con srand(time(NULL)) de modo que ahora cada repetición es diferente de las anteriores.

Interpolación (3)

La idea que proponen en numerical recipes para la interpolación de Lagrange es bastante mejor, la idea es definir:

como el valor x del unico polinomio de grado 0 (una constante) que pasa por , entonces , definimos de la misma forma y de forma analoga diremos que como el valor en x del unico polinomio de grado 1 (una recta) que pasa a la vez por y , seguimos definiendo de esta forma todos los polinomios hasta el grado del polinomio de interpolacion que queramos, ya que el polinomio es el unico polinomio de grado N que pasa por todos los puntos que queremos!

Si ponemos los valores de P en una tabla en forma de "arbol" obtenemos lo siguiente:

El algoritmo para obtener hijos a partir de los ancestros de este arbol de llama algoritmo de Neville:



Esto funciona porque los "padres" ya están de acuerdo en .

La siguiente mejora para la recursión es guardar un registro de las diferencias entre padres e hijos, esto es:

Para


Y juntando esto con la ecuacion de Neville obtenemos:


Para cada nivel m en nuestro arbol las Ces y las Des son las correcciones que hay que aplicar para convertir el polinomio en un orden mayor.

Finalmente obtenemos , que es el resultado de mas los Ces y Des que haya en el camino en el árbol tomando siempre el hijo de la derecha.


Las ideas fueron sacadas de Numerical Recipes in C, que como siempre esta mucho mejor explicado que aquí y mucho mas en ingles.

Interpolación (2)

Entre dos puntos (diferentes) pasa una única línea, entre tres puntos (diferentes) pasa una única función cuadrática etc. etc.

El polinomio de Lagrange de grado N-1 nos da exactamente eso para N puntos tales que , esto es:



La idea es que en los puntos que nos dan todos los polinomios excepto uno serán 0, y el que no es cero nos dará justo el valor esperado.


Programar esto tal como viene no es una idea demasiado buena ya que tenemos una complejidad O(N²) por cada punto nuevo que queramos calcular.

Interpolación (1)

A veces conocemos el valor de una función f(x) en unos puntos dados siendo pero no tenemos una expresión que nos permita calcular f(x) en otro punto cualquiera.

La misión es obtener una estimación de f(x) para un x cualquiera de modo que la curva que dibujemos sea "suave" entre los puntos y en su alrededor. La forma en que aproximemos las funciones tiene que ser general porque no sabemos en principio con que función nos estamos enfrentando. Las aproximaciones mas comunes o al menos las que aprendí en mis clases de calculo son (1)Polinomios (2)Cocientes de polinomios y (3)Funciones trigonométricas.

Hay funciones que tienen un "mal comportamiento" con la interpolación, para saber si el comportamiento ha sido bueno o malo es útil tener una estimación del error, hay que notar que estamos presumiendo que las funciones son suaves y continuas, lo que es perfecto para el movimiento real.

La idea básica es encontrar una función que encaje en los puntos dados y luego evaluarla para otro punto deseado, la mayoría de las aproximaciones empiezan con un punto y van haciendo correcciones al ir agregando otros nuevos puntos, esto nos da una complejidad de

La misión es obtener una estimación de f(x) para un x cualquiera de modo que la curva que dibujemos sea "suave" entre los puntos y en su alrededor. La forma en que aproximemos las funciones tiene que ser general porque no sabemos en principio con que función nos estamos enfrentando. Las aproximaciones mas comunes o al menos las que aprendí en mis clases de calculo son (1)Polinomios (2)Cocientes de polinomios y (3)Funciones trigonometricas.

Hay funciones que tienen un "mal comportamiento" con la interpolación, para saber si el comportamiento ha sido bueno o malo es útil tener una estimación del error, hay que notar que estamos presumiendo que las funciones son suaves y continuas, lo que es perfecto para el movimiento real.

La interpolación local con un numero finito de vecinos no es continua en las derivadas, si necesitamos que sea continua en las derivadas tenemos que usas la no localidad, por ejemplo con splines, es decir entre dos puntos dados definimos un polinomio que los interpola.

Pequeñas Mejoras

A raíz de las ultimas pruebas descubrí algunos fallos, el mas evidente era el que perdiese a los objetos que se movían con una velocidad "no entera", para solucionarlo se me ocurrió agregar un acumulador de velocidad que funciona de la siguiente forma:

velxAcum=velx+velxAcum-(int)(trunc(velx+velxAcum));
velyAcum=vely+velyAcum-(int)(trunc(vely+velyAcum));

De forma que guarda la porción del movimiento que por no ser entera no se ha podido aplicar a un solo paso, pero que al sumarse con otras partes no enteras dara finalmente con una solución mejor que si las ignoramos.

Este es el resultado:




Los saltos que se observan son debido a que el centroide se calcula desde las partículas que se dispersan aleatoriamente. No esta mal teniendo en cuenta que el objeto es invisible al filtro durante 80 frames y aun así la estimación cae sobre el objeto :)

Probando el filtro

Finalmente solucione el problema del circulo y la espiral, la idea es que la x no tiene porque avanzar un pixel en cada iteración, así que la solución que se me ocurrió es rellenar los espacios en que la y avanza mas de un pixel interpolando de alguna forma los pasos intermedios en que la x estaría estática.

Una vez conseguido eso pasamos a las pruebas:

Prueba 1: El rectángulo




Valoración: Satisfactoria, el filtro hace exactamente lo que tiene que hacer y no pierde el objeto aunque "desaparezca", cuando el objeto está rojo el filtro no lo reconoce, esto ayuda a que se pueda evaluar el funcionamiento ya que yo si lo puedo ver (es un super poder que tengo).

Prueba 2: La Recta




Valoración: Mal, muy mal, lo he puesto a posta para que lo haga mal, el problema es que la ecuación de esta recta es y = 50 + 1.2x, dado que el filtro esta trabajando sobre cantidades discretas pierde ese 0.2 a cada iteración, por eso se retrasa, esta en mi lista de TODO arreglar ese aspecto del filtro.

Prueba 3: El Circulo




Valoración: Regular, el filtro funciona como era de esperar, el problema es que esto no es suficiente para seguir al objeto, sigue la recta perpendicular al circulo, esto no pasaría o mejoraría si usase de alguna forma la derivada de la función... esto aun son suposiciones.

Prueba 4: La Espiral




Valoración: Similar al circulo, este es solo un caso ligeramente mas general al del circulo pero quedaba bonito y ademas me gustan las espirales que pasa. Se ve en el video que en algunos casos funciona mejor que en otros, esto depende de la zona de la circunferencia en que nos encontremos ya que en las zonas que estan proximas a los ejes del plano se recorren pixeles sucesivos en una misma linea, es decir solo hay movimiento en el eje x o en el eje y pero no en ambos.

Prueba 5: La Mosca




Valoración: Este es el prototipo de caso en que la realimentación no funciona, ya que el movimiento cambia rápidamente de dirección de forma quasi-aleatoria. No se me ocurre ninguna forma de hacer que esto funcione así que de momento tendrá que esperar.

Prueba 6: Función Sinusoide




Valoración: En este caso existe el mismo problema que sobre la recta, dado que estamos aproximando reales con enteros tenemos el problema de perdida de precisión, aun así no esta mal como primera aproximación.

                      uuuuuuu
                 uu$$$$$$$$$$$uu
              uu$$$$$$$$$$$$$$$$$uu
             u$$$$$$$$$$$$$$$$$$$$$u
            u$$$$$$$$$$$$$$$$$$$$$$$u
           u$$$$$$$$$$$$$$$$$$$$$$$$$u
           u$$$$$$$$$$$$$$$$$$$$$$$$$u
           u$$$$$$"   "$$$"   "$$$$$$u
           "$$$$"      u$u       $$$$"
            $$$u       u$u       u$$$
            $$$u      u$$$u      u$$$
             "$$$$uu$$$   $$$uu$$$$"
              "$$$$$$$"   "$$$$$$$"
                u$$$$$$$u$$$$$$$u
                 u$"$"$"$"$"$"$u
       uuu        $$u$ $ $ $ $u$$       uuu
      u$$$$        $$$$$u$u$u$$$       u$$$$
       $$$$$uu      "$$$$$$$$$"     uu$$$$$$
     u$$$$$$$$$$$uu    """""    uuuu$$$$$$$$$$
     $$$$"""$$$$$$$$$$uuu   uu$$$$$$$$$"""$$$"
      """      ""$$$$$$$$$$$uu ""$"""
                uuuu ""$$$$$$$$$$uuu
       u$$$uuu$$$$$$$$$uu ""$$$$$$$$$$$uuu$$$
       $$$$$$$$$$""""           ""$$$$$$$$$$$"
        "$$$$$"                      ""$$$$""
          $$$"                         $$$$"

Algo de Geometria I

Mi tarea de hoy ha sido programar pequeñas funciones en C++ que sean capaces de devolver coordenadas en pantalla que representen ciertas funciones.

Sen(x)

El problema con esta función es que esta definida entre -1 y 1, por lo que hace falta escalar la imagen y discretizarla.

y=a+(int)round(b*sin(gradosAradianes(i)));



Rectangulo:
Esta funcion es tan simple como concatenar 4 bucles que lo describan.


Circunferencia:




Al despejar la y obtenemos lo siguiente:



Esto debería generar un circulo pero como se puede comprobar no lo genera:




Esto se debe a que el avance de las x es constante cuando en realidad no tiene por que ser así, es decir que aunque describe un circulo correctamente hay zonas en que se mueve mas rápido de lo que cabria esperar debido al efecto de la discretización.

Algunas imágenes contienen oclusiones totales o cambios de color, esa característica se usara para probar el filtro.

Todas las gráficas fueron sacadas de la Wikipedia

Diseño Modular

Después de muchas vueltas y mas vueltas me he decidido por un diseño para el nuevo sintetizador de vídeo mejorado (mágico, plus, maestro del universo!), la idea es que el usuario tenga que escribir un pequeño fichero describiendo el tipo de video que desea y se genere automáticamente.

Un ejemplo del fichero de usuario sería:

NFrames=340
Width=400
Height=400
FPS=1
ObjectSize=40
Function=/home/zenko/workspace/senoidal/Debug/senoidal
args=100 200 0 340
Color=/home/zenko/workspace/colores/Debug/colores
Sections=200 255 255 255 50 0 0 0 90 255 255 255

Donde cada cosa es exactamente lo que parece según la descripción.

Function es la ruta a un ejecutable que recibe 4 argumentos a, b, inicio y fin, con esto ejecuta la función:

for(i=primero;i < ultimo;i++)
{
 y=a+b*sin(gradosAradianes(i)));
}

Color es la ruta de un ejecutable que devuelve ternas R G B y recibe n parámetros de tal forma que si dividimos los parámetros en grupos de 4 tenemos:

1) Numero de ternas
2) R
3) G
4) B

y nos devuelve una lista de N ternas.

Finalmente el script toma la salida de ambos programas y pega los ficheros en uno solo tal que guarde la sintaxis esperada por el generador.

#Numero de frames del vídeo
4
#Ancho del vídeo
400
#Alto del ideo
400
#FPS para el vídeo
1
#Tamaño del objeto
40
#x y R G B para cada frame
1 102 255 255 255
2 103 255 255 255
3 105 255 255 255

De esta forma cada vez que queramos generar un vídeo con una función extraña o exótica solo hará falta escribir la función y todo el resto del código sera reutilizable.

Sintetizador de video

Una vez conseguido el algoritmo básico de seguimiento se inicia la etapa de pruebas en donde necesitaré muchos vídeos de distintos tipos, es una buena practica tener un sintetizador que me cree vídeos a medida para comprobar el seguimiento.

En principio las funciones escogidas son:

a*Sen(x)+b
a*x+b
(x-h)^2 + (y-k)^2 = r^2
Espiral de Arquímedes

Esta será la primera batería de pruebas para comprobar el rendimiento del filtro.

Prueba usando 100*Sen(x)+200



El vídeo es bastaaaante lento, pero es parametrizable así que se puede poner a la velocidad deseada.

Falta escribir algunas de las funciones y modelizar las oclusiones, una vez conseguido esto necesito también alguna forma de tomar estadísticas del seguimiento del objeto.

Evitando la dispersion desde un centro

Un efecto extraño que teníamos en anteriores versiones es que la dispersión generaba un cuadrado casi perfecto, se debe a que las todas las partículas se dispersan desde un mismo centro, esto no es tan buena idea ya que se supone que estamos perdiendo precisión con respecto a cuando tenemos medida, y en ese momento la nube es mas dispersa.

Para solucionarlo he cambiado la forma en que se calcula la velocidad y los centroides, el centroide se sigue calculando a partir de las n partículas en vez de moverlo por la inercia, las partículas se dispersan con la función aleatoria estándar como de costumbre pero la velocidad no se actualiza de nuevo hasta obtener una nueva medida.

Esto que parece ser la idea mas lógica y obvia no se me ocurrió hasta tiempo después de estarlo pensando!

Seguimiento exitoso

Después de mucho trabajo arduo y todo eso que se suele decir por fin el filtro ha seguido un objeto correctamente mezclando las dos aproximaciones anteriores, si hay medida usa su esquema estándar de filtro de partículas y cuando no hay medida usa el esquema secundario realimentado.

Durante el tiempo que no tiene medida se va aumentando la incertidumbre linealmente en función del tiempo que ha pasado desde la ultima medida, siendo la incertidumbre inicial la dispersión que se estaba usando en el pf.

Al aumentar la incertidumbre desde la estimación de la realimentación obtenemos un cuadrado en vez de un circulo como cabria esperar para un radio constante, esto se debe a la forma en que está programado.

Usando 150 partículas



El cuadrado que se genera se debe a dos cosas, la primera es que todas las partículas se dispersan desde el mismo centro, la segunda es que todo el área que cubren es equiprobable ya que no tenemos medida.

Usando 10 particulas


Una prueba curiosa es ver como funciona el filtro con tan solo 10 partículas, para mi sorpresa termino encontrando al objeto y siguiéndolo, las fluctuaciones del centroide (cuadrado rojo) mientras no tiene medida son debidas a que se esta calculando el centroide real de las partículas no el estimado debido a la inercia, Como las partículas se dispersan con una función aleatoria normal si usamos muchas partículas ambos centroides convergen, aunque para pocas partículas da un poco de mala pinta.

El problema del aleatorio no tan aleatorio

#include 
#include 

int main()
{
    int i,cont=0,aux=0;
    for(i=0;i<300;i++)
    {
        aux=rand()%7-3;
        if(aux>0)
            cont++;
        else if (aux<0)
            cont--;
    }
    printf("cont= %d\n",cont);
}

Al ejecutar este código en un bucle durante 300 iteraciones me encuentro con que cont vale -13, es decir que han habido 13 números negativos mas que positivos, si tuviese un aleatorio realmente aleatorio la cantidad de negativos y positivos debería ser igual, el problema es que al salir mas números negativos que positivos el centro de la distribución sufre un retroceso.

Si estamos siguiendo un objeto con partículas ese retroceso significa perder el objeto, por lo que ahora la opción es aumentar el grado de incertidumbre sin usar ninguna función aleatoria, ya que perdemos incertidumbre de una forma constante desde que perdemos el objeto.

El siguiente objetivo es crear una función Esparcir() o algo similar que distribuya uniformemente x partículas en una zona de espacio.

O incluso mejor mover el centroide y luego dispersar las partículas a partir de el sin volverlo a actualizar si no tenemos una medida!

La informacion es poder

La inercia solo funciona si nuestro sistema inercial tiene suficiente información, es decir el sistema tiene una "creencia" de la velocidad a la que se mueve la partícula que está siguiendo, esta creencia sera mas o menos informada y según sea mas o menos podrá simular el efecto de movimiento con mayor o menor precisión.

Tras 5 iteraciones de dispersión normal:



Tras 10 iteraciones de dispersión normal


Tras 15 iteraciones de dispersión normal se obtiene información suficiente



Lo importante de esto es notar que no podemos pedir una buena estimación si antes no hemos proporcionado cierta información para que siga una cierta inercia.

Actualización: He subido los vídeos que ilustran lo anterior para subsanar el error de ayer que subí tres vídeos iguales.

Ligeramente atascado con los modelos de dispersión

He estado trabajando con nuevos modelos de dispersión para las partículas, y viendo las simulaciones me di cuenta de algunos errores en el anterior enfoque, ni la dispersión lineal ni la inercial funcionan como esperaba, así que habrá que hacer algunos cambios.

Dinámica Inercial

Cada partícula guarda su propia inercia, esto es un "error" porque la inercia del movimiento se ve aproximada por la inercia de la estimación, la inercia de las partículas individuales no aproxima nada y se pierde el objeto.

Ademas al usar la inercia de las partículas individuales se tiene que la velocidad de dispersión es constante, aunque la velocidad del movimiento no lo sea.

Para solucionar esto hay que guardar un historial de estimaciones por grupos de dispersión.

Una vez conseguido que el historial nos devuelva la velocidad media de desplazamiento de las ultimas N iteraciones conseguimos un comportamiento bastante mejor:




El siguiente cambio es conseguir un método que represente la perdida de seguridad que se tiene cuando desaparece una partícula.

Dispersiones Multiples

Hoy la tarea es ver como funcionan diferentes tipos de dispersiones, la dispersión normal que es dado un radio máximo usamos una función aleatoria normal para esparcir las partículas en dicho radio, la segunda opción es seguir la recta de mínimos cuadrados que hemos creado en anteriores entregas y finalmente habrá partículas que únicamente tengan inercia, es decir que continúen con la velocidad que ya tenían.

El ultimo enfoque no me gusta tanto porque al cambiar el movimiento del objeto no hay forma de que la dispersión lo encuentre, sin embargo si el objeto desaparece nos daría una idea de por donde esta en dicho momento porque las cosas en el mundo real tienen cierta inercia.

He hecho una simulación, la partícula roja muestra la dispersión estándar, la partícula azul sigue la recta de mínimos cuadrados y la verde es inercial.



Cada movimiento funciona con 100 partículas independientes, aunque como veremos en un futuro este no es el mejor enfoque posible por lo que ya comente.

La recta de mínimos cuadrados

lo que queremos es aproximar una distribución de N puntos por una recta de forma que la recta este lo mas cerca posible de todos los puntos, lo primero es decir a que nos referimos por cerca, esto es que la distancia entre el todos los puntos y la recta sea mínima.




Tenemos que encontrar entonces los valores de a y b para que el valor siguiente sea minimo:



Es decir

En este caso lo que tenemos que encontrar es a y b, para eso supongamos que las derivadas parciales son 0.





Es decir que:



Y substituyendo obtenemos a y b:







Mucho mejor explicado aunque mucho mas en ingles