martes, 5 de marzo de 2013

Laboratorio 5: Detección de Círculos (Radios Desconocidos)

Link al repositorio: https://github.com/synnick/viscomp


Ésta semana se trabajo con la detección de círculos con radios comunes (que suele ser la forma más común utilizada en visión computacional. Para laboratorio, se pidió realizar una detección de círculos con diferentes tamaños, es decir radios diferentes.

El principio es el mismo que anteriormente. Antes teníamos una matriz bidimensional con pares de coordenadas $(x_{c}, y_{c})$ a los cuales se realizaba un histograma para saber cuantos pixeles votan por cada par. Ahora, esta matriz será tridimensional, teniendo una matriz como la mencionada para cada diferente radio que estemos probando. 

Esto podemos imaginarlo como buscar partes de un cono en la imagen, partiendo desde la punta que sería un círculo con radio pequeño, y aumentando el radio progresivamente hasta un cierto punto.

Para cada radio diferente, existiría una matriz con los puntos  $(x_{c}, y_{c})$. Entonces deberíamos de quedarnos en cada iteración de cada radio, con los centros que tengan una mayor cantidad de votos, procurando además que los pixeles que no sean bordes (los bordes se localizan previamente con gradientes) no puedan votar.

Probando lo anterior, agregando simplemente al programa de radios comunes, funciona de la siguiente manera:

Los 3 círculos se detectan correctamente pero además de ellos aparece demasiado ruido, detectando círculos de múltiples radios dentro y fuera de los círculos originales. Lo siguiente sería eliminar los círculos con radio al cual no pertenece.

Para realizar esto, podemos trazar dos líneas a través del centro, marcando dos diámetros perpendiculares vertical y horizontal. Estas líneas serían de tamaño aproximado al diámetro del círculo actual (2 veces el radio para el cual se están buscando círculos) agregando un pequeño umbral en caso de que el círculo se detecte un poco movido.

Haciendo esto, se puede verificar que ambos diámetros horizontales y verticales estén en contacto con el círculo 2 veces, es decir, determinaríamos si dicho punto es un círculo de un radio determinado sí:


Para poder aplicar éste método ES NECESARIO contar con una buena detección de bordes, debido a que se van a utilizar valores de los bordes para poder determinar si el círculo es válido o no. Una buena detección de bordes para la imagen anterior sería:

                                           Usando

Con estos bordes, verificamos que trazando "líneas" imaginarias de tamaño r + umbral (umbral siendo una cantidad de tolerancia de separación que puede haber entre el radio y el borde) dichas líneas hagan contacto con los bordes. Cambiando los umbrales es posible disminuir la cantidad de ruido, eliminando círculos que no pertenecen a ningún borde encontrado:

Umbral 30                                        Umbral 20                                                           Umbral 5


(Nota: El avance en los radios se hace en pasos de 5 en 5 para acelerar el proceso)

La detección correcta depende de dos cosas entonces, el paso (cambio) en el radio y el umbral.

Si el paso es de 1 en 1 y $umbral >= 2$, es probable que se detecten diferentes círculos de diferentes radios alrededor de un centro. Por eso sería necesario ajustar los valores dependiendo de la aplicación para la cual se use.

Ahora ya tenemos listo el detector de círculos de diferentes radios.

Igual que en la detección de círculos con radios conocidos, se nos pidió hacer lo siguiente:
  • Marcar los círculos con tonos de amarillo fuerte.
    • Marcar cada círculo de un tono de amarillo diferente.
  • Marcar el centro del círculo con un punto verde.
  • Agregar una etiqueta con el ID del círculo.
  • Imprimir un listado con ID's y diámetros de cada círculo (como porcentaje de la diagonal máxima de la imagen)
La forma de realizar todos los puntos excepto el último están explicadas en el post de detección de círculos con radios conocidos.

Para obtener la diagonal máxima de la imagen, simplemente se puede obtener la distancia desde una esquina, a su contraria usando la fórmula:

$D = \sqrt{ {(x_2 - x_1)}^2 + {(y_2 - y_1)}^2 }$

Con la fórmula obtenemos la distancia desde un punto hasta otro, siendo en nuestro caso en términos de pixeles y siendo los puntos dos esquinas contrarias, por ejemplo la esquina inferior izquierda y la esquina superior derecha.

Ejemplos:




Código

El código siguiente, no funciona para todas las imágenes con círculos pero se comporta correctamente en pruebas hechas en cualquier editor de imágenes con círculos exactos.
Para pruebas rápidas lo mejor es editar el rango del último for con los radios aproximados que sabemos que se tiene, si se colocan rangos puede tardar demasiado, aunque lo peor que puede pasar es detectar múltiples círculos de radios similares en donde hay uno.




Catálogo de Proveedores de HW / SW

Hardware

En la sección de hardware mencionaré algunas tiendas que conozco que se dedican a vender electrónica, la mayoría con un amplio repertorio para casi todas las necesidades.

AG Electrónica
http://www.agelectronica.com/

AG cuenta con gran variedad de circuitos integrados analógicos y digitales, diodos, transistores, y demás de marcas como Motorola, Toshiba, Microchip, Atmel, y otros.

Se pueden encontrar además diversos componentes para aplicaciones de comunicaciones, monitoreo y control. Se ofrecen dispositivos con tecnologías como WiFi, Zigbee, GSM, Ethernet, Bluetooth, RFID y demás.
Shield - Xbee w/o RF module
Xbee                                                         Microcontrolador PIC

Para realizar compras en AG Electrónica, es posible comprar desde las sucursales, que se pueden localizar en el siguiente link: http://www.agelectronica.com/?p=sucursales

La otra forma es utilizando la tienda virtual, para después imprimir el recibo y depositar el monto en el bnaco. Después se puede a pasar a recoger los componentes ordenados con el recibo.

Sparkfun
https://www.sparkfun.com/static/about

SparkFun es una tienda en línea que vende partes electrónicas para todo tipo de proyectos.  Se especializan en una gran cantidad de componentes de electrónica, especialmente en tablillas de desarrollo para microcontroladores como el ARM, ATMEGA, AVR y otros.


Arduino Uno                                   Insertor de Monedas

Para realizar compras en Sparkfun, es necesario contar con una cuenta y realizar las compras en línea, siendo posible recibir tu pedido en tu hogar, o recogiendo los componentes ordenados en la tienda. Sin embargo, por el momento solo existen tiendas en los Estados Unidos, por lo cual si deseamos conseguir algo de Sparkfun desde México, tenemos que contactar los distribuidores. Los distribuidores se pueden conseguir aquí: https://www.sparkfun.com/distributors

Steren
http://www.steren.com.mx/

Steren es una tienda de electrónica general que cuenta con una gran cantidad de componentes básicos de electrónica, como TTLS, LEDs, diodos, capacitores, relevadores, etc. No vende ni distribuye placas de desarrollo como Arduino o Teensy, sin embargo, es un buen distribuidor para conseguir lo antes mencionado a buenos precios, sobre todo al comprar al mayoreo.



Convertidor Analógico/Digital               PIC16F628A-I/P


Software

En esta sección mencionaré software utilizado en conjunto con hardware común en sistemas.

pySerial - Python

No en sí un lenguaje para programar hardware, con Python y la librería pySerial es posible realizar una comunicación serial con otros dispositivos conectados a la computadora que ejecuta el código de Python.

    

Haciendo esto es posible utilizar toda la gama de funciones y librerías con las que cuenta Python para poder realizar tareas con datos obtenidos desde los dispositivos conectados, o viceversa podiendo utilizar Python como medio para obtener datos desde la computadora, y pasarlos al dispositivo conectado.

Processing
http://processing.org/download/

Processing es un lenguaje de programación open source que es posible usar en conjunción con Arduino mediante librerias. Processing provee una excelente interfaz entre la computadora y el Arduino para utilizar el hardware conectado con el Arduino y poder procesar los datos obtenidos por el mismo desde la computadora, siendo capaz de realizar animaciones, gráficas y demás.



Arduino IDE
http://arduino.cc/en/main/software
El Arduino IDE es una interfaz para poder escribir y subir códigos para programarlos. Cuenta con una gran cantidad de ejemplos de todo tipo, desde el simple hola mundo (parpadeo de LED) hasta comunicaciones seriales, interrupciones y otras cosas más avanzadas.



Teensy Loader
http://www.pjrc.com/teensy/loader.html

El Teensy loader es un programa usado para comunicar la computadora con la placa Teensy, para poder descargar programas nuevos en la placa y ejecutarlos.

lunes, 4 de marzo de 2013

Tarea 4: Detección de Círculos (Radios Conocidos)

Link al repositorio: https://github.com/synnick/viscomp

Usando principios similares a la detección de línea, ahora lo que se debe de detectar son círculos. 

Para este post que corresponde a la materia, se utilizarán círculos con el mismo radio, el cuál será conocido. Para medir el radio (en pixeles) se utiliza cualquier herramienta de dibujo como GIMP o Paint.

Recordando anteriormente, para la detección de líneas buscábamos pares $(\rho, \theta)$ para cada pixel a partir de sus gradientes horizontal y vertical, y después se hacía un histograma con las frecuencias y se quedaban los que tenían más "votos".

En el caso de los círculos, buscaremos pares $(x_{c}, y_{c})$ que representan los posibles centros de círculos.

Para calcularlos, igualmente en base a los gradientes horizontal ($g_{x}$) y vertical ($g_{y}$) se hace lo siguiente:
Se calcula la magnitud $g$ usando la fórmula:

$g = \sqrt{gx^{2} + gy^{2}}$

Con esto se calcula:
$\cos \theta = {g_{x}}/{g}$
$\sin \theta = {g_{y}}/{g}$

Teniendo $\cos \theta$ y $\sin \theta$, calculamos $x_{c}$ y $y_{c}$:

$x_{c} = x - r \cos \theta$
$y_{c} = y - r \sin \theta$

Donde $r$ es el radio designado como parámetro.

Calculando estos pares, se hará un histograma de frecuencias para cada par, contando cuantos hay. Después, solo se dejarán los más significativos, que corresponden a posibles centros para muchos puntos.

Teniendo ya los posibles centros localizados, se solicitó localizar lo siguiente:
  • Marcar los contornos de los círculos detectados de color amarillo.
    • Si hay más de un círculo, el tono debe ser diferente para cada uno.
  • El centro del círculo, se marca con un punto de color verde.
  • Al centro de cada círculo se coloca una etiqueta con un ID para cada círculo.
Para marcar los contornos de los círculos, hago uso de ImageDraw de la librería PIL y su función draw.ellipse, ya que teniendo localizados los centros, y teniendo el radio, podemos trazar círculos alrededor de ese punto con un radio determinado. 

Para los diferentes tonos de amarillo, simplemente se obtiene un color $Amarillo = (var, var, 0)$, donde var es un número del 100 al 255, que varía para dar diferentes tonos de amarillo (más cercano a 0 más oscuro, más cercano a 255 más brillante).

Para pintar los centros basta con simplemente pintar cada pixel de centro localizado de color verde, es decir $(0, 255, 0)$.

Y finalmente para colocar el ID, de nuevo se usa ImageDraw para colocar un texto con un número asignado al círculo, usando draw.text en las coordenadas del centro.

Ejemplos


Los círculos se dibujaron en Paint, por lo cual no son perfectos. El radio usado para localizarlos es 40. La cantidad de círculos localizados es la correcta, sin embargo, la localización del centro y el contorno parece ser incorrecta, pero es debido al mismo problema de que no son círculos perfectos.



En este ejemplo se localizan correctamente los círculos y se agregan dos círculos fantasmas más. Gracias a éste ejemplo me di cuenta que cuando los círculos que se buscan están a una distancia R (radio) cercanos, se crea un círculo fantasma entre los círculos reales cercanos (lo cual es el caso del círculo 3, que se forma debido a que tiene puntos alrededor que corresponderían a la circunferencia de los círculos 1 y 5, y lo mismo para el cŕculo 4, con vecinos 2 y 6.


En cambio cuando los círculos están pegados uno al otro, no se localizan círculos fantasmas, aunque aquí aparecen ligeramente alejados de donde se encuentra el centro exactamente, pero la cantidad de círculos es correcta, y la localización es bastante aceptable.

Código


Laboratorio 5: Simulación con NS-2

Para esta Tarea de laboratorio, se solicitó realizar una simulación en el programa Network Simulator, en su versión 2 o 3 (NS-2, NS-3), en forma conjunta con Network Animator para realizar animaciones de las simulaciones.

Elegí la versión 2 por ser más sencilla de instalar, siguiendo esta guía para Fedora, y ésta para Ubuntu.

Simulación 1

Para entender como funciona el NS-2, lo primero que hice fue buscar ejemplos para poder escribir una pequeña simulación básica de un nodo a otro. Con la ayuda de los ejemplos logré escribir un pequeño script con una simulación con un nodo adjuntado a un agente UDP, y una fuente de tráfico CBR para el mismo agente. Para que el segundo nodo reciba los paquetes del primero, se debe agregar un agente NULL, y realizar la conexión con el agente UDP para que los paquetes vayan hacía ahí.


Al final, se deben definir los eventos que sucederán en la simulación. En este ejemplo, inicio CBR a los 0.1 segundos, y lo detengo al completarse un segundo. De todas formas al correr la simulación, esta se hace con un paso de 2 ms, por lo que se puede observar bien el comportamiento.

He aquí la simulación:


Algo simple, pero sirvió para aprender lo básico.

Simulación 2

Para la segunda simulación, agregue un nuevo agente UDP para ver como se comportaba un nodo que recibiera paquetes desde dos conexiones. Se utiliza el mismo principio que anteriormente, agregando un nuevo agente UDP, adjuntando a su fuente de tráfico CBR y esta conectándola con el mismo agente NULL que el primer agente.



La simulación se ve bien, se ve como quería pero no hace exactamente nada útil solo algo gráfico. La siguiente simulación arreglará eso.



Simulación 3

Ahora para poder en verdad simular algo y realizar mediciones al respecto, necesitamos crear algo un poco más robusto. Para ello, en vez de tener dos agentes UDP y un nodo al que llegarán, tendremos un agente TCP para un nodo, un agente UDP para otro, y un nodo que sirva como cuello de botella para recibir y poner los paquetes en una cola.




En la simulación se puede observar como se simula la conexión TCP, que a diferencia de la UDP, el destinatario reenvía un ACK para confirmar que se recibió el paquete. Los cuadros rojos pertenecen a paquetes enviados mediante UDP, y los azules mediante TCP. En el nodo 2 se puede observar como se llena la cola con los paquetes que se van procesando, y en un cierto momento esa cola se llena y algunos paquetes se pierden (apareciendo cayendo en la simulación).


Medidas de Desempeño

A partir del archivo generado al correr el código con ns (el mismo usado por nam) es posible obtener datos de como se comportó la simulación. En base a ello podemos calcular diferentes cosas, como el throughput, la pérdida de paquetes, jitter y demás. Buscando en Internet, existen ya algunas medidas de desempeño programadas por diferentes personas para usarlas con las salidas de una simulación, estas programadas en AWK.

Los archivos de salida de ns-2 cuentan con el formato:

r -t 0.76804 -s 2 -d 3 -p tcp -e 1040 -c 1 -i 134 -a 1 -x {0.0 3.0 22 ------- null}

donde:
 r significa que se recibió el paquete correctamente,
-t indica que el siguiente valor es el tiempo en el que se recibió (desde el inicio de la simulación),
-s nodo orígen = 2,
-d nodo destino = 3,
-p protocolo = tcp,
-e tamaño de paquete = 1040 bytes,
-c es el id de flujo = 1,
-i el número de paquete.

Las demás líneas son datos que no se ocuparán para las pruebas.

La pruebas hechas (a la simulación 3) son las siguentes:

Delay

Código



Resultado



Pérdida de Paquetes

Código



Resultado



Referencias: