Mostrando entradas con la etiqueta Matemáticas. Mostrar todas las entradas
Mostrando entradas con la etiqueta Matemáticas. Mostrar todas las entradas

martes, 27 de marzo de 2018

Python 3.x, que versión elegir




Estoy buscando la mejor versión de Python para afrontar un nuevo proyecto de machine-learning. Se trata de un proyecto muy ambicioso cuyo desarrollo se dilatará en el tiempo y que servirá también como laboratorio para ensayar la implementación de nuevas técnicas de IA. Es importante que la herramienta pueda perdurar sin tener que migrar, en mucho tiempo, a nuevas versiones de Python. He realizado un pequeño análisis para valorar cual será la mejor elección y he querido compartir este pequeño esfuerzo.

Empezaré describiendo los condicionantes que se han de cumplir:
  1. Debe ser compatible con Django 2.
  2. Debe ser compatible con la mayoría de las librerías importantes de machine-learning y matemáticas.
Antes de nada justificar la elección de 3.x y no de 2.x pero esto es inmediato si tenemos en cuenta que 2.7 tiene los días contados, concretamente el soporte finalizará en el 2020 y ya no habrá más versiones de 2.x. Una vez establecido este extremo pasamos a discutir los siguientes puntos:

1. Compatibilidad Django 2.

Como podemos ver aquí Django 2 solo es compatible con 3.x, concretamente nos ofrecen la siguiente tabla de compatibilidades:

 Django  Ptyhon
2.0:         3.4, 3.5, 3.6
2.1:         3.5, 3.6, 3.7

Ni Django 2.0 ni 2.1 son del tipo LTS, será la 2.2 la próxima LTS y como podemos ver nada se nos dice sobre la compatibilidad de Python para esta versión LTS, no obstante si confiamos en que continúen con la mima serie tendremos:

Django  Ptyhon
2.2:         3.6, 3.7, 3.8

Bajo este ángulo tenemos tres opciones, la 3.5, la 3.6 y la 3.7. Es evidente que la mejor opción en este caso es la 3.6 ya que por un lado 3.5 pierde su compatibilidad con la versión LTS (2.2) y la 3.7 necesita de la versión 2.1 de Django que saldrá en Agosto del 2018. 

La mejor elección: Python 3.6

2. Compatibilidad con librerías machine-learning.

En este apartado se incluyen todas las necesarias para el desarrollo de algoritmos y algunas muy recomendadas. A continuación una lista de las imprescindibles:

  1. Numpy: Paquete de para computación científica, imprescindible para afrontar cualquier problema matemático. La versión 1.14 requiere Python >= 2.7 pero es incompatible con 3.0, 3.1, 3.2, 3.3 y compatible con 3.4-3.6. Numpy 1.14 se ha compilado con Cython 0.26.1 que no es compatible con Python 3.7.
  2. Pandas:  Paquete para análisis de datos, totalmente imprescindible. Las versión 0.22 es compatible con 2.7, 3.5 y 3.6, por el momento no soporta 3.7.
  3. ScyPy: Totalmente imprescindible. Requiere Python >= 2.7 o Python >= 3.4, no dice nada respecto a Python 3.7. 
  4. SymPy: Matemáticas simbólicas. No es imprescindible pero si muy recomendada. La última versión 1.1.1 requiere Python 2.7, 3.3, 3.4, 3.5, 3.6.
  5. Matplotlib: Representación gráfica. No es imprescindible pero si muy recomendada. Python >= 2.7 o >= 3.4, no se dice nada respecto a 3.7.
  6. TensorFlow: API de Google para deep-learning. Muy recomendable.  Requiere 2.7 o 3.x.
  7. OpenCV: Para visión artificial. Muy recomendable. Soporta las siguientes versiones de Python:  2.7, 3.4, 3.5, 3.6. 
  8. Numba: Para correr nuestro código usando también la GPU. Muy recomendable. Sigue exactamente el mismo criterio de Numpy por lo que podemos decir que es compatible con 2.7 y 3.4-3.6 pero no es compatible con Python 3.7. 
  9. Python StatsModels: Para estadśitica. Imprescindible, requiere 2.7 o 3.x.  
La mejor elección: Python 3.6, Python 3.5 

Todo parece indicar que la mejor elección es Python 3.6, no obstante repasemos algunas de las mejoras de la versión 3.6 respecto a la 3.5:
  1. Se pueden usar guiones bajos para leer mejor los números grandes 1_000_250=1000250.
  2. Se introduce en el estándar la anotación de los tipos para las variables, listas, diccionarios y clases.
  3. Se puede usar await y async en las list, set, dict comprehensions.
  4. Se puede usar await y async en una misma función. 
  5. Se incorpora el módulo secret para generar números aleatorios válidos para criptografía.   
  6. Se agrega un nuevo protocolo file system path.
Parece que la inminente versión 3.7 de Python traerá mejoras considerables respecto a la depuración del código, sin embargo introducen un cambio en el manejo de las excepciones de tal manera que estas serán incompatibles con las versiones anteriores de Python.
Conclusión: La versión de Python 3.5 es compatible con todos los paquetes de machine-learning y aunque las mejoras de 3.6 con respecto a 3.5 no son espectaculares Python 3.5 dejará de ser compatible con la versión de Django 2.2. Por otro lado la versión 3.7 parece introducir muchas mejoras pero no estará disponible la versión estable hasta el verano del 2018. Por otro lado no es soportado por muchos paquetes debido a la notable diferencia al tratar las excepciones. Por todo ello parece que la mejor elección es Python 3.6.

miércoles, 9 de abril de 2014

La funcion Gaussiana en visión artificial II


Como decíamos en la anterior entrada dedicada a la gaussiana, su empleo  puede servir de ayuda para encontrar características en una imagen sin tener que preocuparnos por la escala. Para ver como funciona vamos a recordar un nuevo operador ampliamente conocido en el mundo de la física, se trata del operador laplanciano:


$\Delta f =\nabla^2f$

O en dos dimensiones y en coordenadas cartesianas:

$\Delta f =\nabla^2f = \frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}$ 

Cuando es aplicado sobre imágenes, la función f es $I(x,y)$ y designa la intensidad del pixel de coordenadas x, y. En OpenCV podemos fácilmente calcular el resultado del operador laplanciano si tenemos en cuenta que este puede calcularse como una convolución con un kernel determinado. El siguiente ejemplo muestra lo que hace el operador laplanciano, en este caso con un kernel de 5x5:


Como puede verse la segunda derivada ofrece una gran sensibilidad al ruido. Si lo que se desea es calcular los bordes de los objetos el uso del operador laplanciano  pude ser de utilidad, pero la excesiva sensibilidad al ruido lo hace de difícil uso. No obstante podemos emplear, antes del operador laplanciano, un filtrado gaussiano. Esta nueva convolución es conocida como LoG. A grandes rasgos el filtrado LoG tendrá el siguiente comportamiento al aplicarlo a una imagen:

- Cero a lo largo de los contornos.
- Positivo justo a un lado del contorno.
- Negativo al otro lado del contorno.
- Cero en el interior del contorno.

Cuando se eligen valores de sigma pequeños el filtro LoG es capaz de captar los bordes que se encuentran a menos escala, mientras que con valores grandes se capturan los de mayor tamaño. El siguiente ejemplo muestra un LoG con un sigma de 3.


La parte correspondiente a la cabeza y al borde de las alas se distinguen con facilidad, sin embargo otras zonas mas sutiles son menos nítidas - las antenas, por ejemplo -. Si reducimos el valor de sigma, digamos a 1, tenemos el siguiente resultado:



Ahora logramos que otras características se hagan visibles. Aplicando este método, usando con cuidados los valores del tamaño del kernel y el de sigma, podemos descubrir muchas de las características notables de una imagen. Ahora bien, el LoG es costoso en tiempo de computación, aunque existe una solución si empleamos un camino opcional calculando las diferencias de convoluciones gaussianas con dos diferentes sigmas, por ejemplo $\sigma$ y $k\sigma$. Esto es una aproximación al cálculo de LoG más rápida. Esto se hace para varios valores de sigma, en forma piramidal y disminuyendo la escala - o aumentándola si partimos de un valor de sigma pequeño -. Una vez realizadas las diferencias se buscan los máximos comparándolos con 8 los píxeles vecinos, así como los 9 píxeles de los niveles de escala posteriores y anteriores. De esta forma se consiguen los extremos locales, que potencialmente pueden ser keypoints. Una vez obtenidos estos máximos locales se puede refinar aún más nuestro conjunto de keypoints desechando los que estén por debajo de un cierto umbral. Esta descripción corresponde al método SIFT, descrito en 2004, D.Lowe, University of British Columbia, Came up with a new algorithm, Scale Invariant Feature Transform. El algoritmo esta disponible en OpenCV por lo que no necesitamos implementarlo nosotros mismos. Ahora describimos en pocas líneas como usar SIFT en openCV desde Python:
 
sift = cv2.SIFT()
keypoints, descriptor = self.sift.detectAndCompute(image,None) 

Para representar los keypoints sobre la imagen podemos recurrir a  drawKeypoints, que si le añadimos DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS como flag, nos dibujará los keypoints  con su orientación y un radio proporcional a la "fuerza" del mismo. El resultado es el siguiente:





En la siguiente entrada veremos como podemos recurrir a un algoritmo aún más eficiente que el SIFT.

martes, 8 de abril de 2014

La función Gaussiana en visión artificial I



¿Cuanto se le debe a Johann Carl Friedrich Gauss?. Imposible de cuantificar la aportación del brillante matemático al mundo de la física , de las matemáticas o de la astronomía. Desde los fractales, pasando por el electromagnetismo y como no, la visión artificial son, entre otras muchas ramas de la ciencia, deudoras del ingenio del "príncipe de las matemáticas". La visión por computador es posible hoy en día por estar, en términos newtonianos, aupada a hombros de gigantes como Gauss. En esta entrada vamos a explicar en que consiste la función Gaussiana, y que importancia tiene en la visión por computador.

La función gaussiana tiene el siguiente aspecto en dos dimensiones:

$G(x,y;\sigma ) = \frac{1}{2\pi \sigma ^2}e^-\frac{x^2+y^2}{2\sigma ^2}$

Esta misma función, en una dimensión es considerada la función de densidad de una variable aleatoria cuando se entiende a $\sigma ^2$ como la varianza.  En el caso que nos ocupa el valor $\sigma$ representará la "escala interior", cuyo valor siempre será mayor que cero, esto es evidente si consideramos que no es posible realizar un observación a través de una apertura nula. Por otro lado la parte correspondiente a $\frac{1}{2\pi \sigma ^2}$ sirve  para normalizar la función - en la versión de 1 dimensión esto es muy fácil de ver- . Esto último es importante ya que el volumen que encierra la superficie tiene valor la unidad, independientemente del valor de sigma. 



Ahora expliquemos lo que es la convolución de dos funciones, y que se define de forma discreta como:

$g(m)*f(m)=\sum _ng(n)f(m-n)$

Y que cumple las siguientes propiedades:

- Conmutativa: $w*f = f*g$
- Asociativa: $w*(f*g) = (w*f)*g$
- Distributiva: $w*(f+g) =w*f+w*g$
- Teorema de la convolución $F(w*g) = F(w)*F(g)$, donde F es la transformada de  Fourier

Una propiedad importante es que la convolución de dos funciones gaussiana es también una función gaussiana, esto se denomina autosimilaridad.

$G_1(x,\sigma_1^2)*G_2(x,\sigma_2^2)=G(x,\sigma_1^2+\sigma_2^2)$

Para hacer esta última propiedad más explicita usamos el siguiente parámetro:


$\widetilde{x}=\frac{x}{\sigma\sqrt{2}}$

En ese caso nuestra función para una dimensión queda como:

$G(\widetilde{x},\sigma)=\frac{1}{\sigma\sqrt{2\pi }}e^-\widetilde{x}^2$

Una vez explicada brevemente el aspecto de la función gaussiana vamos a ver como puede emplearse en visión artificial. Para mejorar el aspecto de una imagen, eliminar ruido o destacar algunas características de la misma se pueden emplear distintos tipos de filtros. Un filtro en el dominio del espacio se realiza sobre todos y cada uno de los píxeles de una imagen, de tal forma que para modificar el pixel i,j se tienen en cuenta los valores de los vecinos. Los filtros en el dominio del espacio pueden ser de dos tipos, lo lineales y los no lineales.  Los filtros lineales usan un kernel o mascara $w(x,y)$ para realizar la siguiente operación que transforma cada píxel f(x,y):

$g(x,y)=\sum_{s=-i}^{i}\sum_{t=-j}^{j}w(i,j)f(x+i,y+j)$ 

Como puede comprobarse esta operación es una convolución.
 
Un ejemplo de filtro lineal es el que sustituye el valor del píxel por la suma ponderada de los píxeles vecinos. Para ello, se realiza una convolución donde la mascara o kernel es como el siguiente - en este caso hemos tomado una máscara de 2x2 -:

$\begin{pmatrix}
 1/2&1/2 \\
 1/2&1/2 
\end{pmatrix}$
 
Apliquemos un filtro de convolución como este usando OpenCV para Python:  

 
kernel = np.ones((3,3), dtype=np.float32)/9.0
cv2.filter2D(img,-1,kernel)

En este caso hemos aplicado una convolución tal que cada píxel es transformado en la media de los 9 vecinos, para ello se utiliza el kernel definido en la primera línea. El resultado de aplicar este filtro se muestra a continuación:



Como puede verse este filtro empaña o emborrona la imagen. Lo que puede lograrse mediante este filtro es suavizar la imagen, eliminado detalles dispersos y de pequeño tamaño. Como se deduce inmediatamente parte de su utilidad se encuentra en su capacidad para eliminar ruido.


El filtro de la media tiene algunas desventajas, ya que es muy sensible a cambios locales y puede crear nuevas intensidades que no aparecen en el original. Empleando un kernel más sofisticado pueden obtenerse resultados más óptimos. Para ello podemos recurrir a la función gaussiana:

$G(x,y;\sigma ) = \frac{1}{2\pi \sigma ^2}e^-\frac{x^2+y^2}{2\sigma ^2}$

El valor de $sigma$ determina la anchura de la campana. Hay que destacar que en virtud de las propiedades vistas anteriormente el filtro gaussiano es separable, es decir podemos aplicar un filtro 2D aplicando dos mascaras, una horizontal y otra vertical.

Si aplicamos un filtro gaussiano, empleando OpenCV:
cv2.GaussianBlur(img,(0,0),1)

Donde el valor (0,0) designa el tamaño del kernel o máscara y el valor 1 es el correspondiente a sigma. Si el valor del tamaño del kernel es cero - como en el caso que nos ocupa - la evaluación se realiza empleando el valor de sigma. También es posible dar distintos valores para la sigma de x y la sigma de y. El resultado es:



Uno de los usos más interesantes de este tipo de filtros es el que va encaminado a facilitar la detección de características. Los algoritmos para extraer esquinas como el propuesto por Harris son invariantes ante las rotaciones pero no lo son con respecto a los cambios de escala, es decir, no detectara esquinas y bordes que no estén el la misma escala. En estos casos se puede recurrir a un nuevo tratamiento, como por ejemplo el algoritmo SIFT - Scale-Invariant Feature Transform - que hace uso del filtrado con kernel gaussiano y que veremos en la siguiente entrada.        
 

lunes, 17 de marzo de 2014

Geometría en la visión por computador, calibrado de la cámara I


En esta entrada voy a tratar algunos aspectos de la geometría que hay detrás de la visión por computador, en este caso en concreto voy a abordar la relación que hay entre las imágenes capturadas por un cámara en el mundo real, y la representación o proyección que se tiene en el plano de la imagen. Esto nos resultará muy útil a la hora de poder calibrar una cámara. 

Primeramente asumimos que  los rayos luminosos entran en la cámara y quedan enfocados en un punto denominado centro de proyección. Este centro será el origen de un sistema de referencia de tres dimensiones, por tanto este centro, denominado C, tendrá coordenadas $C(0,0,0)$. Justo delante del centro de proyección tenemos el plano de la imagen, que es el plano que contiene la proyección de la imagen que la cámara está "observando", como puede verse en la figura está se encuentra a una distancia f del centro del proyección, en nuestra representación sobre el eje Z. El plano de la imagen va a tener su propio sistema de coordenadas, formado por los vectores unitarios $(u,v)$. Ahora un punto de un objeto del mundo real, con coordenadas $p(x,y,z)$ - según sistema de referencia en centro de proyección - se proyecta en el plano de la imagen con coordenadas $p(u_{c},v_{c})$, según sistema de referencia $(u,v)$.




Los triángulos formados por los vértices C(0,0,0), $p(u_{c},v_{c})$, p(x,y,z) y (u_{0},v_{0}), son semejantes por lo que:

$\frac{f}{z}=\frac{u_p}{x}$

$\frac{v_p-u_0}{y}=\frac{f}{z}$

Sin embargo desde el punto de vista del software el origen de la imagen se encuentra en el extremo superior izquierdo de la imagen - plano de la imagen -, por lo que las ecuaciones anteriores deberían describirse como:  

$\frac{f}{z}=\frac{u_p-u_0}{x}$

Con la información de una sola cámara no es posible decir nada sobre la profundidad de la imagen, esto es, sobre el valor de z, no obstante si es posible relacionar la posición en el plano de la imagen con los valores x e y del mundo real. Para ello se emplea la matriz de transformación M tal que:

$[u_p,v_p,1]=M[x,y,z,1]^{T}$

Donde la matriz $M=K[RT]$, siendo R y T una rotación y una traslación entre el sistema de referencia de la cámara y las del objeto  respectivamente. La matriz K contiene los parámetros internos de la cámara, ya que su valor es:

$K = \begin{pmatrix}
 f& 0 & u_0 \\
 0& f & v_0\\
 0& 0  &0
\end{pmatrix}$


Si ahora consideramos el valor z como 0 para todos los objetos y colocamos un tablero de ajedrez donde el tamaño de los recuadros es conocido, tendremos una relación entre las coordenadas de los píxeles y las coordenadas reales, esta relación podría ser usada en la ecuación de transformación para averiguar R,T y la matriz de parámetros internos de la cámara. Se necesitan muchas de estas correspondencias para poder resolver el sistema de ecuaciones que sale de la ecuación matricial anterior, no obstante este trabajo lo puede realizar OpenCV o Matlab por nosotros. En la siguiente entrada emplearemos OpencCV para realizar esta calibración y si dispongo de tiempo, también añadiré una entrada más realizando este trabajo desde Matlab.




sábado, 8 de marzo de 2014

Python y el problema del jugador



El problema del jugador, el problema del paseo del borracho o del camino aleatorio, es un clásico de la probabilidad que tiene enorme interés en distintos campos de matemática aplicada, como en la segmentación de imágenes o en las finanzas. El problema, en su formulación más sencilla, podría describirse de la siguiente manera:

Sea un jugador que partiendo de una cantidad inicial de dinero, desea alcanzar un cierto objetivo apostando en un juego. La mecánica del juego es tal que si el jugador gana (con probabilidad p) se embolsa una cantidad igual a la apostada, perdiendo el dinero de la apuesta (con probabilidad q) en caso contrario. El juego solo finaliza si el jugador alcanza su objetivo o si termina en la banca rota. El problema consiste en establecer la probabilidad de terminar en bancarrota antes de alcanzar el objetivo, en función del objetivo y de la cantidad de dinero con la que se parte, así como de las probabilidades p y q. 


Vamos a resolver el problema usando probabilidad, de forma teórica, para luego solucionarlo de forma empírica empleando Python. Ambas deberían converger cuando el número de ensayos es lo suficientemente grande (Ley de los grandes números). 
 
Supongamos que la cantidad apostada es tratada como unidad, no hay problema en esto ya que todas las apuestas deben ser iguales a lo largo del juego. Sea $u_{j}$ la probabilidad de que termine en la bancarrota y j la cantidad con la que se parte. En ese caso es claro que:

$u_{j}=p\cdot u_{j+1}+q\cdot u_{j-1}$

Con las condiciones de frontera:

$u_{0}=1$ y $u_{c}=0$ , siendo c el objetivo

Tras algunas operaciones algebraicas, obtenemos la probabilidad buscada:

 $u_{j}=\frac{r^{j}-r^{c}}{1-r}$  siendo r=q/p

Para los detalles matemáticos se puede consultar cualquier libro de probabilidad que trate el tema de los caminos aleatorios, como por ejemplo Elementary Probability Theory, K. L. Chung. Springer (2003).

Evidentemente este resultado solo es válido si r es distinto de 1 ya que en ese caso la probabilidad nos da una indeterminación. Para el caso en el que r=1, se llega a la siguiente conclusión:

$u_{j}=\frac{c-j}{c}$

Una vez establecido el marco teórico, vamos a realizar un algoritmo que realice el papel de jugador. Empecemos con el caso más sencillo, aquel en el que las probabilidades son 1/2 para el jugador y la banca, esto es p=q=1/2, por lo que r=1. 

import random as rnd
def gambler(money0,objective, bet = 1): 
    cont = 1
    lines =[]
    num =  money0 
    while (num > 0 and num < objective):
        num = num + rnd.choice([-bet,bet])
        lines.append([cont,num])
        cont= cont + 1
    return lines  

Como puede verse el algoritmo es muy sencillo, se parte de una cantidad inicial de dinero (money0), de una apuesta (bet) que tomaremos como 1, y un objetivo. En la función un número pseudoaleatorio [-1,1] con idéntica probabilidad  hace las veces de resultado. Los distintos juegos se van sumando (o restando) a la cantidad inicial, el bucle continua hasta que se alcanza el objetivo o hasta que el jugador cae en bancarrota. El resultado de los distintos juegos se mete en una tupla (línea 7).

A continuación dibujamos el resultado de las partidas. Para el caso que nos ocupa he elegido pygame para representar los resultados. La función que dibuja los distintos lances de la partida es como sigue:

import pygame as pyg
def draw(points,color,screen,init_point):
    point0 = init_point
    point_end = [0,150]
    for point in points:
        point_end = [point_end[0] + 10, point[1] + 150]
        print point_end
        pyg.draw.line(screen,color,point0,point_end,1)
        point0 = point_end

En la línea 8 encontramos la función que dibuja la gráfica con los resultados, su uso es muy intuitivo y no requiere demasiadas explicaciones. Antes de poder dibujar con Pygame es necesario inicializar el área donde se va a dibujar, esto se realiza de la siguiente forma:

screen = pyg.display.set_mode((1000, 250 + OBJECTIVE))
pyg.init()
pyg.display.set_caption('Game')
pyg.display.flip()    

La línea 4 es necesaria para refrescar el contenido de la ventana del dibujo y debe ser invocada cada vez que pintemos algo. El resultado de un solo juego, queda gráficamente como:


Se han añadido los resultados de calcular la frecuencia relativa, así como los casos ganados y perdidos. También figura la probabilidad calculada según la formula ofrecida más arriba para el caso r=1. El resultado que arrojan para este caso es:



Los datos ofrecidos no arrojan demasiada información. Las frecuencias relativas no se parecen en nada a los cálculos teóricos. Al aumentar el número de jugadas, a 100, por ejemplo, los resultados van cambiando:

 
Los resultados numéricos son:



Como puede comprobarse los valores teóricos empiezan a parecerse a los resultados empíricos. Si aumentamos el número de juegos a 100000 tenemos que:



Aquí las frecuencias relativas son casi idénticas a las obtenidas mediante el pequeño juego que hemos elaborado. Si quisiéramos trabajar con probabilidades distintas de r=1 seria necesario modificar:


 
Ya que esta función de random selecciona entre -bet y bet con igual probabilidad. Una solución sencilla es emplear sample(population,k), donde population es una población y k la longitud de la lista extraída de population. En el siguiente ejemplo (+1) tiene una probabilidad de  0.333 mientras que (-1) de 0.666:

num_pos = [x/x for x in xrange(1,4)]
num_neg = [-x/x for x in xrange(1,7)]
space = num_pos + num_neg    
rnad_num = rnd.sample(space,1)[0] 

Los dibujos que representan los distintos caminos que sigue la jugada, hasta alcanzar la bancarrota o el objetivo, forman una curiosa forma geométrica.  Es un caso unidimensional de un paseo aleatorio también podría decirse que es un paseo aleatorio por una recta. La figura cumple con los requisitos de dimensión fraccionaria, lo que los convierte en una figura fractal. Son una versión sencilla de la curva de Korch, o una curva aleatoria de Peano, con un generador mucho más sencillo. Si se desea profundizar en este tipo de fractales recomiendo la lectura de los capítulos 7,8,9 y 10 del magnifico libro La Geometría Fractal de la Naturaleza, Benoît Mandelbrot, TusQuets (2003).