Juan Carlos Espinosa Ceniceros: marzo 2013

jueves, 7 de marzo de 2013

[Lab VC] Actividad 4: Detección de círculos (radio diferentes)

Para esta actividad se debieron programar las rutinas para detectar círculos de diferentes tamaños, es decir, con radios variables, en una imagen. Para ello se utilizó la Transformada de Hough.

En la entrada anterior:

http://juankenny.blogspot.mx/2013/03/vc-tarea-4-deteccion-de-circulos-radio.html

se describió el método utilizado para la detección de círculos a detalle, las bases para esta actividad son las mismas, sin embargo, ahora el radio es variable, por lo que hay que adaptar el código para que haga ésto.

Cuando el radio no es conocido, la solución más simple es comenzar con un radio de cota inferior e ir aumentándolo en cierta cantidad, pasos de 1 o 2.

Posteriormente hay que establecer una cota superior, una cota superior segura generalmente es la longitud de la diagonal mayor de la imagen ya que no tiene sentido buscar por circulos más grandes que ese tamaño.

Fuente: http://www.aishack.in/2010/03/circle-hough-transform/

Podemos limitar un poco más la búsqueda, por ejemplo, a 3/4 del tamaño de la longitud mayor.

Posteriormente, por cada radio tendremos una arreglo de bidimensional de votos, si cada arreglo lo agregamos a una lista terminaremos con un arreglo de tres dimensiones que contendrá los votos por cada radio probado.

Las imágenes utilizadas para la prueba fueron:

Original
Binarizada
Contornos

Los resultados fueron los siguientes:

Como podemos ver en las imágenes, hasta cierto punto el programa sabe dónde se encuentran los círculos ya que detecta y dibuja los contornos dentro de los límites de los mismos, y, por ejemplo en la primea imagen ignora cualquier otra cosa (caso del triángulo invertido a la derecha). Sin embargo, no detecta correctamente los círculos lanzando basura en cada radio analizado.

Se necesita alguna rutina que limpie esa basura, ya que el problema que he notado es que por cada radio analizado, no importa cuan pequeño sea el radio o que el radio analizado no corresponda a un círculo en específico, siempre me lanza algún resultado, centros de círculos en alguna posición de la imagen posiblemente porque a pesar de que el radio analizado no corresponde a ningún círculo visible, los pixeles aún así votan, los votos aún así se agrupan y aún así se lanza algún "centro" falso.

Implemente un pequeño algoritmo que hace una segunda agrupación de votos para detectar mejor los círculos y barrer un poco la basura, los resultados obtenidos fueron los siguientes:

Como podemos ver, los resultados son un poco mejores, en la primera imagen por lo menos se ubican los círculos, pero no exactamente en los centros. En la segunda imagen el resultado fue un poco mejor ya que se detectan los centros de 2 de los círculos, por lo menos de los 2 mas grandes. Sin embargo, esta segunda agrupación elimina la posibilidad de detectar la longitud del radio y no puedo dibujar el contorno de los círculos.

Mejoraré un poco el código, pienso que algún tipo de hibridación entre el primero y el segundo puede funcionar

Código

En el repositorio encuentran la implementación completa en código, la carpeta marcada como Tarea 5.

https://github.com/jcespinosa/vision_computacional

La mayoría de las funciones fueron explicadas en la entrada anterior, ahora solo se modularizó un poco el código y se adaptó a lo nuevo.

	def groupCircles(centers): # Para la agrupacion de centros de circulos
	newCenters = list() # cuando varios centros correspondientes al
	mainCenter = list() # mismo radio estan muy cerca, entonces se
	cThreshold = 5 # juntan para dibujar un solo centro promediado.
	x, y = centers[0]
	for a, center in enumerate(centers):
	if(abs(center[0]-x) < cThreshold and abs(center[1]-y) < cThreshold):
	mainCenter.append(center)
	print mainCenter
	else:
	newCenter = (sum([ce[0] for ce in mainCenter])/len(mainCenter),\
	sum([ce[1] for ce in mainCenter])/len(mainCenter))
	mainCenter = [center]
	newCenters.append(newCenter)
	print newCenters
	try: x, y = centers[a]
	except IndexError: return newCenters
	if(a == len(centers)):
	newCenter = (sum([ce[0] for ce in center])/len(center),\
	sum([ce[1] for ce in center])/len(center))
	newCenters.append(newCenter)
	print newCenters
	try: x, y = centers[a]
	except IndexError: return newCenters
	return centers


	def circleDetection(pixels, width, height): # Deteccion de circulos diferentes
	minRadius = 2 # Radio minimo
	maxRadius = int(floor(sqrt(width2+height2)*0.5)) # Radio maximo, longitud de la diagonal maxima calculada mediante teorema de pitagoras
	votes = [[0 for a in xrange(width)] for b in xrange(height)] # Matriz para agrupar los votos por segunda vez
	allVotes, circles, radius = list(), list(), list() # Almacen de ciertos datos
	gCircles = list() # Almacen de circulos agrupados

	pixelsOr = slicing(pixels, width) # Preproceso de la imagen
	pixels = slicing(pixels, width)
	pixels = numpy.array(pixels)
	pS = pixels.shape

	n = 1.0/1.0 # Mascaras
	maskX = numpy.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]) * n
	maskY = numpy.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]]) * n

	Gx = convolution2D(pixels, maskX) # Gradiente horizontal
	Gy = convolution2D(pixels, maskY) # Gradiente vertical

	for r in range(minRadius, maxRadius): # Evaluamos todos los radios del minimo al maximo
	lastVotes = houghCircles(pixelsOr, Gx, Gy, width, height, radius=r) # Votos del radio evaluado
	for a,v in enumerate(zip(votes, lastVotes)): # Agrupamos los votos
	votes[a] = [i+j for i,j in zip(v[0], v[1])] # Con los votos el anterior radio evaluado

	allVotes = groupVotes(votes, width, height) # Segunda agrupacion de nodos
	circles = detectCircles(allVotes, width, height) # Detectamos los potenciales centros de circulos
	gCircles = groupCircles(circles) # Agrupamos los centros de circulos cercanos entre si

	return gCircles, maxRadius


	def houghCircles(pixels, Gx, Gy, width, height, radius=50): # Tranformada de Hough para detectar circulos
	votes = [[0 for a in xrange(width)] for b in xrange(height)]

	for ym in xrange(height):
	y = height /2- ym
	for xm in xrange(width):
	if(pixels[ym][xm] == WHITE):
	x = xm - width / 2
	gx = Gx[ym,xm][0]
	gy = Gy[ym,xm][0]
	g = sqrt(gx2 + gy2)

	if(abs(g) > 0.0):
	cosTheta = gx / g
	sinTheta = gy / g
	xc = int(round(x - radius * cosTheta))
	yc = int(round(y - radius * sinTheta))
	xcm = xc + width / 2
	ycm = height / 2 - yc
	if xcm >= 0 and xcm < width and ycm >= 0 and ycm < height:
	votes[ycm][xcm] += 1
	return votes

	def groupVotes(votes, width, height): # Heuristico para agrupar votos
	for rango in xrange (1, int(round(width * 0.1))):
	print "%d - %d"%(int(round(width * 0.1)), rango)
	agregado = True
	while agregado:
	agregado = False
	for y in xrange(height):
	for x in xrange(width):
	v = votes[y][x]
	if v > 1:
	for dx in xrange(-rango, rango):
	for dy in xrange(-rango, rango):
	if not (dx == 0 and dy == 0):
	if y + dy >= 0 and y + dy < height and x + dx >= 0 and x + dx < width:
	w = votes[y + dy][x + dx]
	if w > 0:
	if v - rango >= w:
	votes[y][x] = v + w
	votes[y + dy][x + dx] = 0
	agregado = True
	return votes

	def detectCircles(votes, width, height): # Detectar potenciales centros de circulos
	newPixels = list()
	maximo = 0
	suma = 0.0
	for x in xrange(width):
	for y in xrange(height):
	v = votes[y][x]
	suma += v
	if v > maximo:
	maximo = v

	promedio = suma / (width * height)
	umbral = (maximo + promedio) / 2.0

	for x in xrange(width):
	for y in xrange(height):
	v = votes[y][x]
	if v > umbral:
	print 'Posible centro detectado en (%d, %d). ' % (x, y)
	newPixels.append((x,y))
	return newPixels

view raw circleDetection2.py hosted with ❤ by GitHub

Referencias:

martes, 5 de marzo de 2013

[Lab RT] Actividad 5: Práctica con NS-2 y NAM

"NS es un simulador de redes basado en eventos discretos. Se usa principalmente en ambientes educativos y de investigación. Permite simular tanto protocolos unicast como multicast y se utiliza intensamente en la investigación de redes móviles ad-hoc. Implementa una amplia gama de protocolos tanto de redes cableadas como de redes inalámbricas. La versión actual, ns-3, esta diseñada para soportar todo el flujo de trabajo de la simulación desde la configuración hasta la recolección y análisis de tramas."

de: http://es.wikipedia.org/wiki/Ns_(simulador)

"NAM es una herramienta de animación basada en TCL / TK, utilizada para ver las huellas de simulación y reales trazas de paquetes de una simulación de una topología de red utilizando NS. Soporta diseño de topologías, animación a nivel de paquete, y varias herramientas de inspección de datos. Nam comenzó a LBL. Ha evolucionado considerablemente en los últimos años. El esfuerzo de desarrollo nam fue una colaboración continua con el proyecto VINT. Actualmente, se está desarrollando como un proyecto de código abierto alojado en Sourceforge."

de: http://www.isi.edu/nsnam/nam/

Instalación

Para instalar el simulador NS y NAM en Ubuntu 12.04 necesitamos hacer lo siguiente:

Descargar el código fuente desde http://sourceforge.net/projects/nsnam/
Verificar que nuestro Ubuntu esté actualizado, tecleando el comando: sudo apt-get update
Instalar algunas dependencias, el comando completo es: sudo apt-get install build-essential autoconf automake libxmu-dev
Nos desplazamos a la ubicación donde descargamos el código fuente de NAM y lo descomprimimos con el comando tar -xzvf ns-allinone-2.35.tar.gz (el número 2.35 es el número de versión el cual puede variar, para la fecha actual 2.35 es la más nueva)
Una vez descomprimido, escribimos el siguiente comando para cambiar de carpeta cd ns-allinone-2.35
Instalamos ejecutando el comando ./install

Esperamos a que la instalación termine.

Después procedemos a configurar las variables de entorno para que NS y NAM funcionen correctamente, son 3 variables de entorno que hay que configurar.

PATH
LD_LIBRARY_PATH
TCL_LIBRARY

Ahora, todas las variables de entorno de configuran de acuerdo a la ubicación de la instalación, en mi caso corresponde a /home/juancarlos/Downloads/ , ustedes ubiquen la propia. El directorio de instalación lo identificaremos más adelante con la abreviación [install_path]

Para configurar las variables de entorno nos vamos a nuestro home tecleando cd en la terminal, ahí editaremos el archivo .bashrc

Abrimos el archivo con nuestro editor favorito y nos vamos hasta el final del archivo, ahí comenzaremos a escribir. Las variables de entorno las configuramos añadiendo las siguientes líneas al .bashrc:

export PATH=[install_path]/ns-allinone-2.35/bin:[install_path]/ns-allinone-2.35/tcl8.5.10/unix:[install_path]/ns-allinone-2.35/tk8.5.10/unix:$PATH

export LD_LIBRARY_PATH=[install_path]/ns-allinone-2.35/otcl-1.14:[install_path]/ns-allinone-2.35/lib:$LD_LIBRARY_PATH

export TCL_LIBRARY=[install_path]/ns-allinone-2.35/tcl8.5.10/library:$TCL_LIBRARY

Hay que tener cuidado en esta parte de no escribir nada mal para evitar romper algo en el sistema operativo, verifiquen bien los datos antes de guardarlos. Después solo reiniciamos.

Si todo funciona bien, al teclear en la terminal el comando ns se abrirá una consola especial que solo mostrará el símbolo % que indica que NS ha iniciado en modo interactivo.

Si tecleamos nam se abrirá la ventana del visualizador.

ns	nam

Práctica

Para ésta semana la actividad fue documentar una práctica utilizando cualquiera se los simuladores NS. En mi caso utilicé el simulador NS-2 y NAM para visualizar los resultados. La topología de la red se define mediante scripts TCL de una forma muy simple.

El modelo de red que simulé tiene las siguientes característica:

Topología de estrella
4 nodos, uno central y tres hoja
Todos se conectan al nodo central mediante una conexión full duplex

El flujo de datos tuvo las siguientes características:

Dos flujos UDP con tasa de transferencia constante (CBR)
Un flujo TCP de tipo FTP.
El flujo TCP y UDP en cierto momento corren paralelos.

Todos los scripts siempre comienzan con la línea:


set ns [new Simulator]

con la que se define un nuevo objeto simulador. A partir de aquí podemos comenzar a definir toda las características de la topología de red que queremos simular.
Primero definimos los archivos de salida, para poder guardar las trazas producidas por la simulación y ver la simulación en NAM


set myFile [open out.tr w]
$ns trace-all $myFile

set myNamFile [open out.nam w]
$ns namtrace-all $myNamFile

Despues, para cuestiones de visualización, coloreamos cada flujo de tráfico de diferente color. No es necesario indicar cuál flujo va de cuál color, NS-2 lo hace automáticamente.


$ns color 0 blue
$ns color 1 red
$ns color 2 green

Ahora definimos la topología, son 4 nodos:


set n0 [$ns node]
set n1 [$ns node]
set n2 [$ns node]
set n3 [$ns node]

Y conectamos los nodos entre sí definiendo los enlaces. En este caso todas las conexiones son de tipo full duplex, las conexiones entre el nodo 0 y el nodo 2, así como la del nodo 1 con nodo 2 tienen las mismas características, la entre el nodo 2 y nodo 3 es más rápida pero tiene más delay. Todas tienen una queue de tipo Tail Drop. NS-2 ofrece una gran variedad de enlaces


$ns duplex-link $n0 $n2 1.5Mb 2ms DropTail
$ns duplex-link $n1 $n2 1.5Mb 2ms DropTail
$ns duplex-link $n2 $n3 3.0Mb 10ms DropTail

Ahora, para cuestiones de visualización nuevamente, posicionamos cada nodo en un layout que se vea bonito, 2 nodos a la izquierda, arriba y abajo, un nodo al centro y un nodo a la derecha en el centro.

Creamos también un monitor en cada conexión para mantener una queue de paquetes y evitar desbordamientos y pérdida de paquetes.


$ns duplex-link-op $n0 $n2 orient right-up
$ns duplex-link-op $n1 $n2 orient right-down
$ns duplex-link-op $n2 $n3 orient right

$ns duplex-link-op $n0 $n2 queuePos 0.5
$ns duplex-link-op $n1 $n2 queuePos 0.5
$ns duplex-link-op $n2 $n3 queuePos 0.5

Ahora definimos las conexiones UDP, debemos crear un agente UDP por cada una, crear un "sink" que no es más que un agente que recibe el flujo de tráfico UDP, y también es necesario colocarle a cada conexión UDP una fuente de tráfico constante CBR.
Las conexiones UDP van del nodo 0 al nodo 3 y del nodo 1 al nodo 3, pasando forzozamente por el nodo 2 aunque esto último no es necesario especificarlo.
La primera conexión UDP comienza en el segundo 0.2 y la segunda conexión UDP comienza en el segundo 0.5, ambas permanecen activas durante toda la simulación.


set udp0 [new Agent/UDP]
$ns attach-agent $n0 $udp0
$udp0 set class_ 0

set null0 [new Agent/Null]
$ns attach-agent $n3 $null0

$ns connect $udp0 $null0

set cbr0 [new Application/Traffic/CBR]
$cbr0 attach-agent $udp0

$ns at 0.2 "$cbr0 start"


set udp1 [new Agent/UDP]
$ns attach-agent $n3 $udp1
$udp1 set class_ 1

set null1 [new Agent/Null]
$ns attach-agent $n1 $null1

$ns connect $udp1 $null1

set cbr1 [new Application/Traffic/CBR]
$cbr1 attach-agent $udp1

$ns at 0.5 "$cbr1 start"

Por último creamos una fuente de tráfico TCP de tipo FTP, la cual va del nodo 1 al nodo 3. La conexión TCP comienza en el segundo 1 de simulación y finaliza en el segundo 2.


set tcp0 [new Agent/TCP]
$ns attach-agent $n0 $tcp0
$tcp0 set class_ 2

set fin0 [new Agent/TCPSink]
$ns attach-agent $n3 $fin0

$ns connect $tcp0 $fin0

set ftp [new Application/FTP]
$ftp attach-agent $tcp0

$ns at 1.0 "$ftp start"

$ns at 2.0 "$ns detach-agent $n0 $tcp0 ; $ns detach-agent $n3 $fin0"

Finalmente siguen las instrucciones para la simulación, indicamos que la misma durara 3 segundos. Después declaramos el procedimiento de finalización donde limpiamos la memoria, cerramos los archivos y ejecutamos NAM para visualizar los resultados.


$ns at 3.0 "finish"

proc finish {} {
    global ns myFile myNamFile
    $ns flush-trace
    close $myFile
    close $myNamFile
        puts "Simulacion terminada"
    exec nam out.nam &
    exit 0
}

Los scripts finalizan con la instrucción para indicar cuándo la simuación debe correr, hasta que terminan de configurarse todos los parámetros.


$ns run

Script completo

Los dejo el script completo, comentado, con el que corrí la simulación de la topología definida.

	# Creamos el objeto simulador
	set ns [new Simulator]

	#Abrimos un archivo para guardar las trazas
	set myFile [open out.tr w]
	$ns trace-all$ myFile

	#Abrimos un archivo para guardar las trazas
	# y visualizarlas en NAM
	set myNamFile [open out.nam w]
	$ns namtrace-all$ myNamFile

	puts "Archivos creados..."

	# Definimos algunos colores diferentes para
	# diferenciar las fuentes de trafico
	$ns color 0 blue
	$ns color 1 red
	$ns color 2 green

	#------- DEFINICION DE LA TOPOLOGIA --------

	#Creamos los nodos de la topologia
	#4 nodos en este caso
	set n0 [$ns node]
	set n1 [$ns node]
	set n2 [$ns node]
	set n3 [$ns node]

	#Definimos los enlaces entre los nodos
	$ns duplex-link$ n0 $n2 1.5Mb 2ms DropTail
	$ns duplex-link$ n1 $n2 1.5Mb 2ms DropTail
	$ns duplex-link$ n2 $n3 3.0Mb 10ms DropTail

	#Definimos la orientacion y ubicacion de los nodos
	#para que se vean con formato en NAM
	$ns duplex-link-op$ n0 $n2 orient right-up
	$ns duplex-link-op$ n1 $n2 orient right-down
	$ns duplex-link-op$ n2 $n3 orient right

	#Creamos un monitor de conexion entre los nodos 0,2, 1,2 y 2,3
	#ya que 2 fuentes de trafico pasan por este enlace
	#lo que permitira crear una queue y evitar desbordamientos.
	$ns duplex-link-op$ n0 $n2 queuePos 0.5
	$ns duplex-link-op$ n1 $n2 queuePos 0.5
	$ns duplex-link-op$ n2 $n3 queuePos 0.5

	puts "Topologia creada..."

	#-------------------------------------------

	#----- DEFINICION DE UNA CONEXION UDP ------

	#Creamos un agente UDP "udp0" y se lo asignamos al nodo 0
	#El nodo 0 sera una fuente de trafico UDP
	set udp0 [new Agent/UDP]
	$ns attach-agent$ n0 $udp0
	$udp0 set class_ 0

	#Creamos un agente Nulo y lo asignamos al nodo 3
	#Este agente es el destino del trafico UDP
	#y es necesario para hacer fluir el trafico UDP
	set null0 [new Agent/Null]
	$ns attach-agent$ n3 $null0

	#Indicamos que el flujo de datos UDP ira del agente
	#"udp0" al destino "null0"
	$ns connect$ udp0 $null0

	#Creamos una fuente de trafico constante CBR
	#y lo asignamos al agente "udp0"
	set cbr0 [new Application/Traffic/CBR]
	$cbr0 attach-agent$ udp0

	#Indicamos que el trafico UDP del agente "udp0"
	#comenzara en el segundo 1 de la simulacion
	$ns at 0.2 "$ cbr0 start"

	puts "El trafico CBR fluye por la conexion UDP entre los nodos 0 y 3"
	puts "El trafico CBR comienza en el segundo 0.2"

	#-------------------------------------------

	#----- DEFINICION DE OTRA CONEXION UDP ------

	#Creamos un agente UDP "udp1" y se lo asignamos al nodo 3
	#El nodo 3 sera una fuente de trafico UDP
	set udp1 [new Agent/UDP]
	$ns attach-agent$ n3 $udp1
	$udp1 set class_ 1

	#Creamos un agente Nulo y lo asignamos al nodo 1
	set null1 [new Agent/Null]
	$ns attach-agent$ n1 $null1

	#Indicamos que el flujo de datos UDP ira del agente
	#"udp1" al destino "null1"
	$ns connect$ udp1 $null1

	#Creamos una fuente de trafico constante CBR
	#y lo asignamos al agente "udp1"
	set cbr1 [new Application/Traffic/CBR]
	$cbr1 attach-agent$ udp1

	#Indicamos que el trafico UDP del agente "udp1"
	#comenzara en el segundo 1.1 de la simulacion
	$ns at 0.5 "$ cbr1 start"

	puts "El trafico CBR fluye por la conexion UDP entre los nodos 3 y 1"
	puts "El trafico CBR comienza en el segundo 0.5"

	#-------------------------------------------

	#----- DEFINICION DE UNA CONEXION TCP ------

	#Creamos un agente TCP "tcp" y se lo asignamos al nodo 0
	#El nodo 0 sera una fuente de trafico TCP
	set tcp0 [new Agent/TCP]
	$ns attach-agent$ n0 $tcp0
	$tcp0 set class_ 2

	#Creamos el destino del agente TCP "tcp1" y lo asignamos
	#al nodo 3
	set fin0 [new Agent/TCPSink]
	$ns attach-agent$ n3 $fin0

	#Creamos una conexion TCP ente el agente "tcp0"
	#y el destino "fin0"
	$ns connect$ tcp0 $fin0

	#Creamos una fuente de trafico FTP
	#Indicamos que el agente TCP sera de tipo FTP
	set ftp [new Application/FTP]
	$ftp attach-agent$ tcp0

	#Indicamos que la conexion TCP iniciara en el
	#segundo 1.5
	$ns at 1.0 "$ ftp start"

	#Indicamos que la conexion TCP terminara en el
	#segundo 2.0
	$ns at 2.0 "$ ns detach-agent $n0$ tcp0 ; $ns detach-agent$ n3 $fin0"

	puts "El trafico FTP fluye por la conexion TCP entre los nodos 0 y 3"
	puts "El trafico FTP comienza en el segundo 1.0"
	puts "El trafico FTP termina en el segundo 2.0"

	#-------------------------------------------

	#Indicamos que la simulacion durara 3 segundos
	$ns at 3.0 "finish"

	#Procedimientos al finalizar la simulacion
	#Limpiamos y cerramos los archivos
	#Abrimos NAM para ver la simulacion
	proc finish {} {
	global ns myFile myNamFile
	$ns flush-trace
	close $myFile
	close $myNamFile
	puts "Simulacion terminada"
	exec nam out.nam &
	exit 0
	}

	#Corremos la simulacion
	$ns run

view raw ns.tcl hosted with ❤ by GitHub

Video de la simulación.

El video muestra la visualización de la simulación en NAM, los momentos interesantes del video son:

0:30 comienza a correr la simulación
0:33 comienza el primer tráfico UDP
0:39 comienza el segundo tráfico UDP
0:50 comienza el tráfico TCP, podemos ver como los monitores comienzan a enviar los paquetes a las queues debido a que el nodo 2 esta a capacidad máxima debido a que ya tiene 2 conexiones activas. La queue de la conexión entre los nodos n0 y n2 es la que se hace más grande.
1:14 Finaliza el tráfico TCP

Ésta fue una implementación muy sencilla utilizando NS-2 pero se puede leer la documentación del simulador para lograr topologías mas complejas.
Las ligas están en las referencias al final de la entrada.

Referencias

[VC] Tarea 4: Detección de círculos (radio conocido)

Para ésta tarea se debieron programar las rutinas para detectar circulos con radio conocido y preestablecido un una imágen. Para ello se utilizó la Transformada de Hough.

Para la detección de bordes es necesario:

Aplicar máscaras mediante el método de convolución discreta.

Los pasos necesarios son muy parecidos a la detección de lineas, éstos son:

Elegir las máscaras a aplicar, en mi caso elegí 2 máscaras de Sobel
Aplicar las máscaras utilizando convolución discreta (2D)

Aplicar por separado para obtener 2 gradientes Gx y Gy
Obtener G con la fórmula

$G=\sqrt{Gx^{2} + Gy^{2}}$

A partir de las matrices de gradientes obtenidas, calcular los ángulos para seno y coseno con las fórmulas:

$\cos\theta = Gx/G$

$\sin\theta = Gy/G$

Hayar las coordenadas del centro del circulo aplicando las formulas

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

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

Hacer esto por cada pixel para obtener las coordenadas centro a partir de un radio establecido.

Declarar un acumulador de votos, que puede ser un arreglo del mismo tamaño de la imágen en pixeles. El acumulador de votos recoge los potenciales centros de circulos de acuerdo al número de votaciónes de los pixeles que lo rodean.

Agrupar los votos que ésten demasiado cerca, que el pixel con mayores votos se coma a los pixeles con menores votos para reducir el ruido y centros falsos.

Los pixeles con mayores votos son los centros, implementar las rutinas necesarias para descartar falsas alarmas no detectadas en el proceso anterior.

A partir de los centros, dibujar el contorno de los círculos encontrados, marcar su centro, etiquetar cada círculo y obtener el diámetro total.

Las imágenes necesitan tratarse antes de pasar por el proceso de detección de círculos:

Binarizar la imágen
Obtener su contorno

El radio es un parámetro de la simulación y se mide utilizando cualquier software de edición de imágenes, simplemente se mide cuantos pixeles hay de contorno a contorno en el centro, asi obtenemos el diámetro, diámetro entre dos nos da el radio estimado en pixeles.

Las imágenes utilizadas para el ejercicio fueron las siguientes:

Datos	Original	Binarizada	Contornos
Radio=72px
Radio=46px
Radio=41px

Después las imágenes pasan por el proceso donde se detectan los círculos los contornos se pintan de color amarillo y los centros se marcan con un punto verde y se les coloca una etiqueta. Así mismo, en la terminal, se imprime el ID del círculo y la longitud de su diámetro el porcentaje del diámetro se calcula a partir de la diagonal máxima de la imagen.

Los resultados fueron

Como podemos ver, los círculos se detectan muy bien, puede haber pocos círculos, muchos círculos o círculos incompletos.
El único bug visible es un centro ligeramente desplazado en la última imágen, pero creo es más cuestión de ajustes de los parámetros de procesamiento que un error en si.

Código

En el repositorio encuentran la implementación completa en código, la carpeta marcada como Tarea 5.

https://github.com/jcespinosa/vision_computacional

	def houghCircles(pixels, width, height, radio=50):
	newPixels = list() # Donde almacenamos todo lo que se procesa
	votos = [[0 for a in xrange(width)] for b in xrange(height)] # Acumulador de votos

	pixelsOr = slicing(pixels, width) # Backup de los pixeles originales
	pixels = slicing(pixels, width) # Preprocesamiento de los pixeles
	pixels = numpy.array(pixels)
	pS = pixels.shape

	# Mascaras de sobel
	maskX = numpy.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
	maskY = numpy.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])

	Gx = convolution2D(pixels, maskX) # Convolución discreta de los pixeles con la mascara horizontal
	Gy = convolution2D(pixels, maskY) # Convolución discreta de los pixeles con la mascara vertical

	for ym in xrange(height): # Recorremos la imagen a lo alto
	y = height /2- ym
	for xm in xrange(width): # y a lo largo
	x = xm - width / 2
	gx = Gx[ym,xm][0] # Obtenemos una gradiente horizontal
	gy = Gy[ym,xm][0] # Obtenemos una gradiente vertical
	g = sqrt(gx 2 + gy 2)# Obtenemos el valor de la gradiente

	if(abs(g) > 0.0):
	cosTheta = gx / g # Obtenemos el angulo del coseno
	sinTheta = gy / g # Obtenemos el angulo del seno
	xc = int(round(x - radio * cosTheta)) # Obtener la coordenada x del centro
	yc = int(round(y - radio * sinTheta)) # Obtener la coordenada y del centro
	xcm = xc + width / 2
	ycm = height / 2 - yc
	if xcm >= 0 and xcm < width and ycm >= 0 and ycm < height:
	votos[ycm][xcm] += 1 # Incrementamos la cantidad de votos

	for rango in xrange (1, int(round(width * 0.1)),2): # Heuristico que agrupa los votos de los pixeles
	print "%d - %d"%(int(round(width * 0.1)), rango) # de menor peso con los votos de un pixel de mayor
	agregado = True # peso
	while agregado:
	agregado = False
	for y in xrange(height):
	for x in xrange(width):
	v = votos[y][x]
	if v > 1:
	for dx in xrange(-rango, rango):
	for dy in xrange(-rango, rango):
	if not (dx == 0 and dy == 0):
	if y + dy >= 0 and y + dy < height and x + dx >= 0 and x + dx < width:
	w = votos[y + dy][x + dx]
	if w > 0:
	if v - rango >= w:
	votos[y][x] = v + w
	votos[y + dy][x + dx] = 0
	agregado = True
	maximo = 0 # Obtenemos la cantidad maxima de votos
	suma = 0.0 # Obtenemos la suma de todos los votos
	for x in xrange(width):
	for y in xrange(height):
	v = votos[y][x]
	suma += v
	if v > maximo:
	maximo = v

	promedio = suma / (width * height) # Obtenemos la cantidad promedio de votos
	umbral = (maximo + promedio) / 2.0 # para sacar el umbral para incluir posibles centros

	for x in xrange(width):
	for y in xrange(height):
	v = votos[y][x]
	if v > umbral: # Si la cantidad de votos esta dentro del umbra
	print "Possible cener detected (%d, %d)" % (x, y) #Detectamos un posible centro
	newPixels.append((x,y)) # Y lo agregamos a la lista
	return detectCircles(newPixels), sqrt(width2+height2) #Regresamos los circulos detectados, y la diagonal maxima de la imagen


	def detectCircles(centers): # La funcion detectCircles recibe los centros y agrupa aquellos
	newCenters = list() # que tienen coordenadas parecidas dentro de un cierto umbral
	mainCenter = list() # para dibujar un solo circulo.
	cThreshold = 5
	x, y = centers[0]
	for a, center in enumerate(centers):
	if(abs(center[0]-x) < cThreshold and abs(center[1]-y) < cThreshold):
	mainCenter.append(center)
	print mainCenter
	else:
	newCenter = (sum([ce[0] for ce in mainCenter])/len(mainCenter),\
	sum([ce[1] for ce in mainCenter])/len(mainCenter))
	mainCenter = [center]
	newCenters.append(newCenter)
	print newCenters
	try: x, y = centers[a]
	except IndexError: return newCenters
	if(a == len(centers)):
	newCenter = (sum([ce[0] for ce in center])/len(center),\
	sum([ce[1] for ce in center])/len(center))
	newCenters.append(newCenter)
	print newCenters
	try: x, y = centers[a+1]
	except IndexError: return newCenters
	return centers

view raw circleDetection.py hosted with ❤ by GitHub

El dibujo en el canvas se hace con la siguiente función

	def circleDetection(radio): # Funcion para dibujar los circulos en el canvas
	global app, workingImage
	pixels = workingImage["pixels"]
	width, height = workingImage["size"][0], workingImage["size"][1]
	circles, r, maxD = filters.houghTransform2(pixels, width, height, radio=radio)
	app.resetCanvas()
	for id, c in enumerate(circles):
	app.edit_canvas.create_oval(c[0]-r, c[1]-r, c[0]+r, c[1]+r, fill="", outline="yellow")
	app.edit_canvas.create_oval(c[0]-3, c[1]-3, c[0]+2, c[1]+2, fill="green", outline="green")
	l = Label(app.edit_canvas, text="Circle %d"%(id)).place(x=c[0],y=c[1])
	return

view raw circleDetection.py hosted with ❤ by GitHub

viernes, 1 de marzo de 2013

[Lab CU] Actividad 5: Listado de proveedores

Adafruit

"Adafruit fue fundada en 2005 por la ingeniera del MIT, Limor "Ladyada" Fried. Su objetivo era crear el mejor lugar en línea para el aprendizaje de la electrónica y hacer los mejores productos diseñados para los responsables de todas las edades y niveles de habilidad. En los últimos 6 años Adafruit ha crecido a más de 45 empleados y se encuentra en el corazón de Nueva York. Adafruit ha ampliado su oferta para incluir herramientas, equipos y componentes electrónicos que Limor personalmente selecciona, prueba y aprueba antes de ir a la tienda Adafruit."

http://www.adafruit.com/about/

Adafruit es una excelente tienda en línea que ofrece un muy amplio catálogo de productos para eléctronica, componentes, chips, tarjetas de desarrollo, kits de robótica, baterias, entre muchas cosas más.
El beneficio principal de esta tienda son los precios, los cuales se encuentran muy por debajo de los ofecidos por otras tiendas dedicadas al mismo giro.
Otro de los beneficios de la tienda es que ofrece envío a muchos lugares del mundo, entre ellos México, lo que permite recibir nuestros componentes a la puerta de la casa, pagando obviamente el respectivo precio del envío internacional.

Nos parece una buena opción como proveedora ya que es la única tienda que distribuye uno de los componente que más ocupamos a un buen precio, el componente Adafruit PN532 NFC/RFID Controller Shield for Arduino.

Fuente: https://www.adafruit.com/products/789

Que es básicamente la tarjeta que necesitamos para leer y escribir tags NFC, y asi transferir los permisos necesarios para abrir y cerrar las puertas de un automóvil para el prototipo que planeamos hacer. Por $40USD se pueden hacer de uno de estos.

Otro producto que la compañia ofrece y es relevante es el kit Raspberry PI Starter Pack

Fuente: https://www.adafruit.com/products/1014

Incluye todo lo necesario para iniciar a manipular nuestra Raspberry PI.
El producto es relevante porque la Raspberry hará las veces de computadora dentro del automóvil. Se puede adquirir por $104USD.

Se puede ver todo el amplio catálogo de productos en la siguiente liga: https://www.adafruit.com/

...

Sparkfun

"SparkFun es una tienda online dedicada a la venta al por menor las partes y piezas para hacer casi cualquier proyecto de electrónica posible. Los productos y recursos están diseñados para hacer ell mundo de la electrónica más accesible para la persona promedio. Además de los productos, SparkFun, a través de su departamento de educación, ofrece clases y tutorías en línea diseñados para ayudar a educar a las personas en el maravilloso mundo de la electrónica incorporada. Su creciente catálogo de productos cuenta con más de 2.000 componentes y widgets diseñados para ayudarle a dar rienda suelta a su inventor interior."

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

Sparkfun es una comunidad de estudiantes ingenieros que se dedican a crear prototipos para eléctronica y demás componentes, cuya inspiración vino de la dificultad para hallar las partes que en algún momento ellos necesitaron para crear sus proyectos.
Parecido a Adafruit, su modelo de negocio primario es la venta de un variado tipo de componentes electrónicos, kits, tarjetas de desarrollo, entre muchas otros clasificaciones.
También cuenta con envío internacional, con el que podremos recibir todo lo que pidamos directo en nuestras casas.

En un buen proveedor debido a su amplio catálogo, entre los cuales tenemos varios componentes para nuestro proyecto, entre ellos esta la tarjeta de desarrollo Arduino UNO - R3

Fuente: https://www.sparkfun.com/products/11021

Necesitamos el Arduino porque en él irá montada la controladora de NFC/RFID, posteriormente el Arduino irá conectado a la Raspberry PI mediante una interfaz.Cuesta $30USD.

Otro componente relevante y que podemos incluir en el prototipo es el uso de comunicación mediante zigbee, más especificamente, el componente XBee 2mW Wire Antenna - Series 2.

Fuente: https://www.sparkfun.com/products/10414

Las antenas zigbee nos servirán para transmitir datos entre la computadora interna del automóvil y el servidor principal de autenticación de credenciales, posiblemente sea necesario otro Arduino para lograr ésto. Cada antena cuesta $21USD, posiblemente se necesiten 2.

Todos los productos y servicios se pueden consultar en la página https://www.sparkfun.com/

...

Newark

"Newark, parte de Premier Farnell plc global (LSE: PFL), es el distribuidor basado en conocimientos y líder en el mercado de componentes electrónicos, servicios de valor agregado y soluciones de eProcurement en todo el continente americano, con instalaciones en los Estados Unidos, Canadá, México y Brasil. Newark, un innovador en la distribución de electrónicos durante al menos 70 años, es parte de la familia de empresas InOne dentro del grupo Premier Farnell, las cuales trabajan en conjunto a través fronteras geográficas y comerciales para brindar a los clientes, grandes y pequeños, el imponente respaldo y apoyo que sólo una organización internacional puede ofrecer. Newark ofrece un excepcional servicio personalizado, el más amplio surtido de productos electrónicos y servicios de valor agregado únicos."

http://mexico.newark.com/jsp/bespoke/bespoke1.jsp?bespokepage=newark/es_MX/inside/profile.jsp

A diferencia de los dos casoa anteriores, Newark es un distribuidor de componentes electrónicos. Cuenta con un masivo catálogo de componentes de muy variados tipos que abarcan prácticamente todos los campos de la electrónica. Sus proveedores son reconocidos a nivel internacional y ello se encargan de distribuir sus productos de manera legal en México.

Se eligió como proveedor porque es una compañía local que ofrece un componente que necesitamos, el chip/módulo GPS

Fuente: http://mexico.newark.com/te-connectivity/a1080-a/module-gps-high-sensitivity/dp/50M3350

El módulo GPS nos servirá para ofrecer los servicios de reconocimiento y almacenamiento de rutas, y de medición de distancias y velocidad. Los precios varían, pero se ubican en una media de $200USD.

También tenemos en la mira utilizar un módulo GSM/3G

Fuente: http://mexico.newark.com/telit-wireless-solutions/gc864pyt730/module-gsm-gprs-quad-band/dp/25R4633

Es nuestra segunda opción de comunicación entre toda la infraestructura GPS + Arduino + Raspberry con el servidor principal, y nos servirá entre otras cosas para envíar toda la información recolectada por internet y almacenarla en la base de datos correspondiente. Los precios son algo elevados, pero se ubican en promedio en los $220USD.

Pata ver todo el catálogo de productos, se puede accesar al sitio http://mexico.newark.com/

...

Electrónica Steren

Steren es una tienda mexicana dedicada a la venta de componentes electrónicos, pero con más énfasis en la venta de componentes para comunicaciones como cables y conectores. Actualmente esta limitación en su modelo de negocios se ha ido haciendo mas borrosa ya que ahora ofrece una gran cantidad de artículos de electrónica, desde pequeños componentes como chips PIC, transistores, circuitos integrados, resistores, capacitores; hasta artículos más especializados como equipos de medición, antenas VHF y UHF, kits sencillos de robótica, etcétera. Steren es distribuidor, sin embargo también manufactura productos bajo su propia marca.

Lo elegimos como proveedor de los artículos más simples pero importantes de todo proyecto de electrónica, ya que, a pesar de contar con los componentes fuertes, nada funcionaría sin ellos.
Entre estos productos relevantes estan los componentes eléctronicos

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

Estos componentes incluyen resistores, capacitores, leds, diodos, potenciometros, relevadores, entre muchas cosas más; y todos sabemos que éstos componentes nunca pueden faltar en todo proyecto de electrónica.

Los precios son muy económicos, por lo general en el orden de los 5 a 30 pesos por componente, o en el caso de las resistencias, paquetes de 10 componentes del mismo tipo.

Otro producto relevante en cualquier proyecto son los cables.

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

Como mencioné al principio, Steren se dedicaba mas que nada a la venta y distribución de estos productos, desde cableado de cobre simple hasta cables de telefonía y redes. Muchas veces necesitamos hacer conexiones simples para construir nuestros circuitos, entonces podemos sencillamente utilizar cables para realizarlas.

O si se desea transmitir información por medio de un cable, siempre existe la posibilidad de comprar cierta medida de cable cruzado o directo.

Los precios varían en función de la cantidad requerida, pero no van más allá de 50 pesos por metro.

Otros componentes importantes que podemos hallar en este proveedor son:

Semiconductores
Chips
Equipo para soldar
Herramientas de medición como multimetros.

Para ver el catálogo completo se puede visitar la página http://www.steren.com.mx/

...

Referencias