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.

La aplicación que se cae

Todos hemos tenido alguna vez el problema de que una aplicación se cierra sin motivo aparente, y si esa aplicación es el emule/bittorrent/ares etc toca mucho la moral porque es tiempo que va a tardar de mas en descargar lo que sea, así que si pudiéramos darnos cuenta de que se ha caído y volverlo a poner solo unos minutos después seria una buena idea pero claro ... si no estas todo el día en frente del pc es complicado.

A menos que tengas un espía!, este es mi espía:

#!/bin/bash
PID=$(pidof $APLICACION)

if [ "$PID" = "" ]
then
 echo $(date +"%d %m %Y - %H:%M:%S") reiniciando aplicacion >> $HOME/crash.log
 $APLICACION 2>&1 > /dev/null
fi

Luego añadimos la siguiente linea al cron:

0,15,30,45 * * * * $HOME/scripts/crash.sh

y ya esta, cada 15 minutos se comprobara si la aplicación esta funcionando y si no la volverá a lanzar.

NOTA: manda la salida del programa a la porra (/dev/null) y el log es cuuutre pero para mi sobra

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.