[Lab VC] Actividad 3: Detección de líneas en múltiples orientación.

La tarea de la clase consistió en hallar líneas horizontales y verticales en una imagen utilizando convolución discreta, máscaras de sobel y Transformada de Hough.

Como podemos ver, los resultados no fueron los más favorables:

Siguiendo el mismo método explicado en la entrada anterior:

http://juankenny.blogspot.mx/2013/02/vc-tarea-3-deteccion-de-lineas.html

y con algunas modificaciones y actualizaciones se obtuvieron mejores resultados:

Pueden ver los cambios hechos en el código incluido al final de la entrada.

Detección de líneas diagonales

Para esta clase el requisito fue detectar líneas en cualquier ángulo posible, en un principio el código estaba preparado para detectar líneas horizontales y verticales solamente, sin embargo, ésto eliminaba la posibilidad de detectar otro tipo de líneas.

Ahora se eliminaron esas condiciones y cambiamos la función atan por atan2, ésto otorga más flexibilidad al momento de tratar valores negativos y divisiones entre cero.

Básicamente lo que hice fue colocar una sola condición para solamente detectar cuando no haya nada en ninguna condición y cualquier otro caso se calcule como un ángulo cualquiera.

Después el ángulo se discretiza en valores entre -10 y 10 para no tener tantas combinaciones diferentes de pares ($\theta, \rho$).

Al final solo se incluyes 3 condiciones de clasificación:

• Si el ángulo es igual a -180, 0 o 180, tenemos una linea horizontal
• Si el ángulo es igual a -90 o 90, tenemos una línea vertical
• Cualquier otro ángulo se trata como línea diagonal
• 
  

Para limpiar el ruido generado por posibles pixeles solos simplemente se disminuye el numero de pares ($\theta,$rho) candidatos por aquellos que contengan solamente la mayor cantidad de coincidencias.

Resultados

En las siguientes imágenes se ve la interfaz de la aplicación, comparando las imágenes utilizadas con la ubicación de las líneas, el código de colores es el siguiente:

• Rojo: líneas verticales.
• Azul: líneas horizontales.
• Verde: líneas diagonales.
• Gris: no hay nada

Ahora solo se muestra la imagen real y la matriz resultante con la orientación detectada para cada pixel solo con fines demostrativos, no es nada complicado después colorear los pixeles resultantes en la imagen real:

 Prueba 1

Prueba 2

Prueba 3 

Prueba 4

Un detalle que se encontró fue que a veces es necesario tratar la imagen con algunos filtros, por ejemplo, las últimas 2 imágenes, la que contiene el teorema de pitágoras y la que contiene los rombos, fueron binarizadas antes, ésto debido a la cantidad de ruido generado (pixeles huerfanos).

Esto en realidad no es un problema, si se detecta algo extraño simplemente se aplican los filtros necesarios individualmente y después de pasa a la detección de líneas.

Código

Solo muestro la parte del código relevante y programada para esta entrega, en la liga al repositorio pueden encontrar el todo código mas las actualizaciones.

https://github.com/jcespinosa/vision_computacional

en la carpeta Tarea 4

	# Nueva version de Transformada de Hough
	def houghTransform(pixels, width, height):
	newPixels = list() # Donde almacenamos todo lo que se procesa
	results = [[None for a in xrange(width)] for b in xrange(height)] # Resultados temporales
	combinations = dict() # Para guardar las parejas de (theta,rho)
	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]]) * 1.0/8.0
	maskY = numpy.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]]) * 1.0/8.0
	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 y in xrange(height): # Recorremos a cada fila de la imagen
	for x in xrange(width): # Cada fila la recorremos a lo ancho
	h = gx[y,x][0] # Sacamos un gradiente horizontal
	v = gy[y,x][0] # Sacamos un gradiente vertical
	if(abs(h) + abs(v) <= 0.0): # Verificamos que los valores sean mayores a cero
	theta = None # Si no, no hay nada en ninguna direccion
	else: # Si si son mayores a cero
	theta = atan2(v,h) # Obtenemos el angulo para todos los casos
	if theta is not None: # Si el angulo existe, es decir, hay algo en alguna direccion
	rho = ceil((x - width/2) * cos(theta) + (height/2 - y) * sin(theta)) # Calculamos rho
	theta = int(degrees(theta))/18 # Discretizamos los angulos
	combination = ("%d"%(theta), "%d"%rho) # y armamos pares con (theta, rho)
	results[y][x] = combination
	if x > 0 and y > 0 and x < width-1 and y < height-1: # Descartamos los bordes
	if combination in combinations: # Verificamos si existe la combinacion (theta, rho)
	combinations[combination] += 1 # Aumentamos las coincidencias en ese par
	else: # Si no existe
	combinations[combination] = 1 # La creamos
	else:
	results[y][x] = (None, None) # Si el angulo no existe, creamos un par vacio
	frec = sorted(combinations, key=combinations.get, reverse=True) # Ordenamos las frecuencias, las mas relevantes primero
	frec = frec[:int(ceil(len(combinations) * 0.3))] # Cantidad de pares de valores (theta, rho) a utilizar
	for y in xrange(height): # Recorremos la imagen en toda su extension
	for x in xrange(width):
	(ang, rho) = results[y][x] # Obtenemos un par (theta, rho)
	if(ang, rho) in frec: # Si ese par se toma en cuenta, verificamos el tipo de linea que es
	if(ang == -10 or ang == 0 or ang == 10):# Si es horizontal
	newPixels.append(RED) # va color rojo
	elif(ang == -5 or ang == 5): # Si es vertical
	newPixels.append(BLUE) # va color azul
	else: # Todo angulo diagonal arbitrario
	newPixels.append(GREEN) # va de color verde
	else: # Si el par no se toma en cuenta
	newPixels.append(pixelsOr[y][x]) # Agregamos el pixel que normalmente iria en esa posicion
	return newPixels # Regresamos los pixeles procesados para mostrar el resltado

view raw houghTransform2.py hosted with ❤ by GitHub

Continuidad

Una forma simple de detectar la continuidad de las imágenes es utilizar BFS para recuperar la lista de pixeles que componen cada linea, así como el angulo al que corresponden y el valor de rho.

Después simplemente se almacena la información en los objetos creados.

Prueba 5

Como se puede ver en la imágen de muestra, hay pequeñas lineas incontinuas, lo que se puede hacer es eliminar esas líneas poco continuas o unirlas utilizando un algoritmo para dilatar los pixeles y asi lograr lineas más uniformes.

[RT] Extra: Ataques a redes (Lectura)

La actividad de puntos extra consistió en realizar un pequeño reporte sobre algún documento buscado a través de Google Scholar donde se utilice el simulador NS (NS-2 o NS-3).

El documento seleccionado fue:

Collaborative Change Detection of DDoS

Attacks on Community and ISP Networks* 

Yu Chen and Kai Hwang 

University of Southern California, Los Angeles, CA 90089, USA 

{cheny, kaihwang}@usc.edu 

...

Resumen

El documento introduce el problema sobre el problema de los ataques DDoS. Por lo general las redes comunitarias funcionan bajo el mismo ISP (Internet Service Provider) o se administran bajo un método de organización virtual que se extiende a través de múltiples dominios de red bajo una relación de confianza.

Los ataques DDoS se pueden contrarrestar si los routers dentro de esa red trabajan de forma cooperativa para enviar alertas tempranas para evitar los daños a la red. Entonces el objetivo del trabajo es "proponer una arquitectura de colaboración para detectar inundaciones por ataques DDoS".

Ésto es posible mediante el monitoreo de la distribución del tráfico sospechoso en cierta cantidad de routers  por donde transita el ataque y los cambios que sufre, para ello se desarrolló un nuevo mecanismo CAT (Change-Aggregation Tree) que permite la detección tempran de los ataques.

Para ello se utilizaron simulaciones con NS-2 en una red ISP de dominio simple.

El sistema ofrece un nivel de detección de un 95% con menos de un 1% de alarmas falsas-positivas.

Arquitectura de un ataque DDoS

Introducción

Una red comunitaria pueden ser pequeñas o grandes, desde una LAN hasta WAN, y por lo general forman parte de la infraestructura de clusters, redes colaborativas, redes P2P, servidores se servicios web, etcétera. Por lo general estas conformadas por un gran número de administradores IT.

Los requisito básico en una red es proveer un acceso seguro y confiable a los recursos, ya sean locales o remotos. Los ataques DDoS cancelan este requisito, volviéndose la más peligrosa amenaza para los sistemas distribuidos.

Actualmente existen técnicas bastante simples para detectar un ataque DDoS, por ejemplo, cuando el tráfico de entrada y salida no esta muy balanceado, desafortunadamente cuando se detectan estas condiciones ya es demasiado tarde. 

Si se trata el tráfico de internet como un proceso estocástico, una técnica de detección de cambios secuenciales de puntos fue desarrollada para detectar el inicio de los ataques DDoS. La típica metodología de detección de cambios esta obstaculizada por la falta de precisión en el modelo estadístico utilizado para describir los pre-cambios y post-cambios en la distribución del tráfico de la red. Se utiliza el algoritmo CUSUM debido a su simplicidad y baja complexidad computacional, sin embargo, a pesar de ser un buen método de detección de inundaciones TCP SYN a nivel gateway, no sirve para redes distribuidas donde existe mas de un gateway.

ISP de red central

En esencia, las redes comunitarias son organizaciones virtuales (VO) encima del internet físico. Los miembros de la VO pueden compartir recursos con base en requisitos específicos de la aplicación. Los usuarios no tienen ningún control sobre las redes físicas aplicadas. en este caso, las redes utilizadas son administradas por diferentes ISPs. Esto se suma a la complejidad en la realización de trabajo colaborativo.

La investigación sugiere que una solución total para los ataques DDoS es una defensa a escala mundial

sistema a través de la totalidad de Internet.

Dentro de una red de núcleo único ISP, es factible exigir los routers a cooperar entre sí en la lucha contra los ataques DDoS, para ello se propone un cambio en el esquema de detección mediante un cambio al CAT. 

El CAT se basa en el reconocimiento rápido de un patrón de flujo de tráfico dirigido hacia la víctima

máquina.

La raíz es el último router al borde de la red donde el equipo de la víctima es alcanzado. Cada árbol

nodo corresponde a un enrutador de ataque-tránsito (ATR). Cada arista del árbol corresponde a un enlace entre los ATR. El administrador del sistema asegura que todos los routers puedan trabajar cooperativamente. El CAT servidor conoce la topología de la red.

Los patrones legítimos de tráfico no se presentan con la direccionalidad y características de convergencia.

Por lo tanto, una vez que un patrón de CAT se reconoce más allá de cierto umbral, se ha detectado la estadio muy temprano de un ataque DDoS. El esquema de detección esta diseñado para distribuir la información del ataque. Los ATR recolectan la información y la envían regularmente al servidor CAT que la procesa. En caso de que el trafico sobrepase cierto umbral, entonces una advertencia es enviada al servidor CAT.

Patrones de inundación durante los ataques DDoS

Como sabemos, los ataques DDoS atacan un equipo para denegar el acceso a un servicio. Dichos ataques saturan a la victima y a la red entera con una gran cantidad de paquetes los cuales son imposibles de manejar.

Un atacante simplemente explota la red y la gran magnitud de paquetes provocan el agotamiento del ancho de banda por lo que pueden hacer caer a la victima de su conexión a internet. Para lograrlo los atacantes utilizan direcciones IP falsas o duplicadas.

Simulación con NS-2

Para evaluar el rendimiento del cambio propuesto al CAT, se permitieron variaciones en 3 dimensiones: topología de prueba, tráfico legítimo de fondo y las características del ataque.

Se utilizó un modelo real de una topología de un ISP descargada del la página web del proyecto Rocketfuel de la Universidad de Washington.

Los retrasos en la comunicación fueron uniformemente distribuidos en el rango de 40 a 200ms con un ancho de banda de 100MB.

El tráfico de fondo es generado de mediante métodos estadísticos mediante el análisis real de la trama OC48 del proyecto CAIDA.

Para las características del ataque, se estudio una herramienta real de ataques DDoS llamada Stacheldraht V4. Es una de las herramientas mas representativas de este tipo de ataques.

El rendimiento de la simulación se midió con tres parámetros diferentes: detección de retrasos, precisión en la detección y la proporción de falsos positivos.

Los tres parámetros se midieron en 3 tipos de ataques diferentes: inundación TCP, inundación UDP e inundación ICMP. El promedio del tiempo de detección mide el intervalo de tiempo entre el inicio del ataque DDoS y el tiempo en el cual el servido CAT lanza una alarma de ataque.

La precisión de la detección es evaluada usando tres mediciones: proporción de detección, proporción de falsas alarmas y las características del recibidor.

El esquema CAT detecta el inicio de la inundación DDoS monitoreando la variación en el volumen de tráfico, recolectando los patrones sospechosos y construyendo el árbol CAT periódicamente  Después se necesita decidir si el árbol resultante es debido a un ataque o a las fluctuaciones en el tráfico de la red. La diferencia entre ambos es que el tráfico por fluctuaciones en la red no se propaga muy lejos y no muestran la direccionalidad del flujo y un blanco de convergencia en el proceso.

Un umbral se puede establecer para detectar exitosamente un verdadero ataque de inundación, simplemente se obtiene la suma del conteo de las hojas en el árbol y se divide entre la altura del árbol para evaluar el tamaño del árbol. Este tamaño establece el umbral de detección para los ataques DDoS.

Utilizando un umbral menor a 5, la proporción de detección es casi 100%, y cuando ésta proporción se mantiene por encima del 95% y el umbral en 5, la proporción de falsos-positivos cae de 70% a 0%.

También se estudió la relación entre el umbral de detección y la proporción de tráfico experimentado en los ATR's. En un ataque de inundación altamente distribuido, donde el tráfico experimentado por routers individuales es muy bajo, la situación de inundación no es detectada hasta que el stream de información causan cambios notorios.

Eventualmente el valor de umbral se saturará, entre mas zombies estén involucrados, mayor sera el umbral seleccionado. Con un tráfico mayor a 1MB/s ambas curvas de umbrales se saturarán. Esto significa que se tendrá un umbral de detección más estable cuando la inundación DDoS alcanza un nivel lo suficientemente alto.

Otro problema crítico encontrado es cuan rápido se puede detectar el lanzamiento de ataques DDoS desde un gran número de zombies. Desde que el árbol CAT se puede actualizar con todos los ATR periódicamente  el tiempo de retraso puede incurrir en la actualización del servidor CAT con cambios locales frecuentes detectados por cada ATR's. El servidor CAT necesita tiempo para procesar toda la información si un gran número de servidores esta involucrado. Un retraso mayor a 0.5s  no es tolerable.

Conclusiones

La complejidad de los patrones en los ataques DDoS crece rápidamente  también si una nueva vulnerabilidad en las redes es encontrada y herramientas más sofisticadas de ataque están disponibles, por lo que una solución puede servir en algunas redes y fallar en otras.

Las contribuciones de la investigación realizada son la detección temprana de la ola de ataques DDoS basados en los patrones y las anomalías detectadas en la red ISP, los cambios propuestos en el árbol de agregación pueden detectar las inundaciones DDoS de forma temprana.

El método propuesto de puede desplegar en redes ISP centrales, y el esquema de detección se puede implementar en los routers utilizados en la red ISP bajo la misma autoridad.

Existen ventajas y desventajas entre la proporción de detección y la tolerancia a falsas alarmas, los resultados se verificaron satisfactoriamente y los resultados indican que el sistema es capaz de detectar inundaciones DDoS rápidamente con una alta proporción de detecciones y una baja proporción de falsas alarmas, sin embargo, la precisión esta por ser probada con un prototipo desarrollado y experimentos de referencia en el futuro.

** Las imágenes fueron tomadas del paper.

Referencias:

• http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1644164

[VC] Tarea 3: Detección de líneas

Para ésta tarea se debieron programar las rutinas para detectar líneas horizontales y verticales 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.

Primeramente, los pasos necesarios para la detección 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
• A partir de las matrices de gradientes obtenidas, calcular el ángulo para cada pixel de acuerdo a la formula:

$$\theta = \arctan \left ( gy/gx \right )$$

• Calcular la variable rho aplicando la formula

$$\rho = x \cos \left ( \theta \right ) + y \sin \left ( \theta \right )$$

• Establecer las condiciones necesarias para obtener los ángulos correctos.

• Armar pares ($\rho , \theta$) y almacenar dichos pares en una matriz del mismo tamaño (ancho, alto) de la imágen original, a cada pixel le corresponde un par ($\rho , \theta$).

• Realizar un histograma para cada par ($\rho , \theta$), si un cierto número de pixeles tiene coincidencia en dicho par  ($\rho , \theta$) es probable que existan líneas en la imágen.

• Clasificar las líneas en horizontales y verticales, colorearlas de diferente tono.

Las máscaras aplicadas fueron obtenidad de la siguiente lectura:

http://www.cse.unr.edu/~bebis/CS791E/Notes/LineDetection

Resultados

Primeramente, estas son las imágenes utilizadas para realizar las pruebas.

Los resultados obtenidos de la aplicación de la transformada fueron:


Los resultados son parciales y no muy favorables, posiblemente se necesitan algunos ajustes en el cálculo de los ángulos y en la realización del histograma.

Código

	def houghTransform(pixels, width, height):
	newPixels = list()
	result = list()
	combinations = dict()
	pixels = slicing(pixels, width)
	pixels = numpy.array(pixels)
	pS = pixels.shape
	maskX = numpy.array([[-1, -1, -1], [2, 2, 2], [-1, -1, -1]])
	maskY = numpy.array([[-1, 2, -1], [-1, 2, -1], [-1, 2, -1]])
	gx = convolution2D(pixels, maskX)
	gy = convolution2D(pixels, maskY)
	for y in xrange(height):
	rowData = list()
	for x in xrange(width):
	h = gx[y,x][0]
	v = gy[y,x][0]
	if(abs(h) > 0.0):
	theta = atan(v/h)
	elif(abs(h) + abs(v) <= 0.0):
	theta = None
	elif(abs(v-h) < 0.0):
	theta = atan(1.0)
	elif(h*v > 0.0):
	theta = pi
	else:
	theta = 0.0
	if theta is not None:
	theta = int(degrees(theta))
	rho = abs((x - width/2) * cos(theta) + (height/2 - y) * sin(theta))
	combination = ("%d"%(theta), "%d"%rho)
	rowData.append(combination)
	if x > 0 and y > 0 and x < width-1 and y < height-1:
	if combination in combinations:
	combinations[combination] += 1
	else:
	combinations[combination] = 1
	else:
	rowData.append((None, None))
	result.append(rowData)
	frec = frecuentes(combinations, int(ceil(len(combinations) * 0.3)))
	procesado = list()
	for y in xrange(height):
	renglon = list()
	for x in xrange(width):
	(ang, rho) = result[y][x]
	deberia = (pixels[y,x][0] == WHITE[0])
	if (ang, rho) in frec:
	renglon.append(RED)
	else:
	renglon.append(GRAY)
	pixels[y,x] = pixels[y,x]
	procesado.append(renglon)
	numero = 0
	procesado=de_slicing(procesado)
	return procesado

view raw houghTransform.py hosted with ❤ by GitHub

Referencias

• http://www.cse.unr.edu/~bebis/CS791E/Notes/LineDetection.pdf

[RT] Tarea 4: Experimentos de calidad de servicio

Como se especificó en la entrada:

http://juankenny.blogspot.mx/2013/02/lab-rt-parametros-de-medicion-en-qos.html

la tarea de esta semana consistió en analizar la calidad del servicio QoS de una aplicación en internet

Para mi tarea establecí las siguientes condiciones:

• Stream de video desde http://www.youtube.com
• Conexión cableada a internet mediante interfaz ethernet
• Red infinitum
• Banda ancha promedio de 2.88Mbps de bajada al momento del experimento
• Video a 480p de resolución.

Los parámetros a analizar son:

• Latencia
• Jitter
• Perdida de paquetes
• Tasa de transferencia

Los resultados esperados de acuerdo a la teoría investigada son:

• Latencia: menor a 150ms
• Jitter: menor a 50ms
• Perdida de paquetes: menor o igual al 3% del volumen de datos transmitido
• Tasa de transferencia:
• Video a 480p con codec FLV o WebM = 1Mbps aprox.
• Audio con codec AAC o Vorbis = 128Kbps
• Valor teórico esperado = 1152Kbps o 1.2Mbps aprox.

1. Medición de latencia y Jitter

Metodología

Como primer herramienta para calcular la latencia utilicé el comando ping a la url www.youtube.com.

Escribí un pequeño script en python para automatizar la tarea pues realicé la medición con 300 paquetes.

	#!/usr/bin/python
	import subprocess
	from time import sleep
	from math import sqrt
	tLatencias = list()
	tJitters = list()
	latencia_promedio = 0
	jitter_promedio = 0
	conteo = 0
	def desviacionEstandar(valores):
	n = len(valores)
	suma = sum(valores)
	media = suma/n
	suma_dif = sum([(valor-media)**2 for valor in valores])
	varianza = suma_dif/n
	desviacion = sqrt(varianza)
	return desviacion
	def parsearElementos(p):
	global conteo
	for e in p:
	if("time" in e):
	e = e.split("=")
	if(len(e) > 1):
	conteo += 1
	tLatencias.append(float(e[1]))
	return
	while True:
	if(conteo < 300):
	try:
	p = subprocess.check_output("ping -c 1 www.youtube.com", shell=True)
	p = p.split(" ")
	parsearElementos(p)
	print conteo
	sleep(1)
	except:
	print "[>] Buscando, espere..."
	sleep(2)
	else:
	break
	print "\nCalcular latencia promedio"
	print tLatencias
	latencia_promedio = sum(tLatencias)/len(tLatencias)
	print "Latencia promedio > %f"%(latencia_promedio)
	print "\nCalcular Jitter promedio"
	for a, v in enumerate(tLatencias):
	try:
	tJitters.append(abs(tLatencias[a]-tLatencias[a+1]))
	except IndexError:
	pass
	print tJitters
	jitter_promedio = sum(tJitters)/len(tJitters)
	print "Jitter promedio > %f"%(jitter_promedio)
	print "\nCalcular desviacion estandar latencia"
	desviacion_latencia = desviacionEstandar(tLatencias)
	print "Desviacion estandar latencia > %f"%(desviacion_latencia)
	print "\nCalcular desviacion estandar jitter"
	desviacion_jitter = desviacionEstandar(tJitters)
	print "Desviacion estandar jitter > %f"%(desviacion_jitter)
	with open("latencia.dat", "w") as oF:
	for a, lat in enumerate(tLatencias):
	oF.write("%d %f %f %f\n"%(a+1, lat, latencia_promedio, desviacion_latencia))
	with open("jitter.dat", "w") as oF:
	for a, jit in enumerate(tJitters):
	oF.write("%d %f %f %f\n"%(a+1, jit, jitter_promedio, desviacion_jitter))
	exit()

view raw latencia_jitter.py hosted with ❤ by GitHub

Se midió la latencia para esos 300 paquetes y se calculo el promedio y la desviación estándar. Después a partir de las 300 mediciones de la latencia se calculó el jitter promedio.

Ejecución

Pantalla de resultados

Resultados

La ejecución produce dos archivos los cuales posteriormente grafiqué, obteniendo lo siguiente

Latencia	Jitter

• Latencia promedio: 47.115ms
• Jitter promedio: 17.425ms

Podemos ver como la latencia permanece estable, con un promedio de 47ms lo cual significa que el primer parámetro de medición de QoS esta en excelentes condiciones.

Lo mismo pasa con el Jitter, ya que la medición permanece debajo de 20ms lo cual también es excelente.

2. Medición pérdida de paquetes

Después de un rato de pensar que tenía problemas, me sorprendió descubrir que estuvé en un error desde el principio. Intentaba obtener los paquetes de Youtube filtrando UDP y descubrí que youtube utiliza TCP para sus transmisiones. Así que en realidad en un stream de video de Youtube no hay muchas pérdidas ya que el protocolo TCP al detectar un paquete perdido simplemente lo retransmitirá.

Entonces, para comprobar que todo esté en orden voy a medir la cantidad de retransmisiones de paquetes que se hacen durante la transmisión.

Metodología

Primero dediqué la mayor parte de mi banda ancha a Youtube, es decir, cerré otras páginas web abiertas. Despues busqué por el video seleccionado, y esperé.

Después abrimos Wireshark y vamos al menú: Capture > Interfaces

 Seleccionar intefaces

En la ventana emergente seleccionamos la interfaz a escuchar, en mi caso es eth0, y presionamos el botón start.

Elegir la interfaz a escuchar

En la ventana principal, en el campo de texto que dice Filter escribimos TCP

Después rápidamente regresé al navegador, abrí el video, lo configuré a 480p y comencé la reproducción, después solo esperé a que el video terminara de reproducirse.

Resultados

Una vez terminada la reproducción, presionamos el botón Stop the running live capture, nos vamos al menú Statistics > Conversations, en la ventana emergente seleccionamos la pestaña TCP y en la tabla ordenamos los resultados de mayor a menor utilizando la columna Bytes A←B. Así la primera fila será la conversación con más bytes transmitidos, la cual debe ser el stream de video. Hacemos click en esa fila y presionamos botón Follow stream para filtrar solo los paquetes TCP que pertenecen a la comunicación con Youtube.

Conversaciones TCP

Una vez hecho ésto, veremos que en la ventana principal veremos los paquetes de la comunicación con Youtube, veremos también que el campo de texto Filter ha cambiado, ahora dice algo parecido a tcp.stream eq 11 (donde el último número puede variar ya que pertenece a un id interno de wireshark para clasificar las conversaciones). Dejamos ese filtro y escribimos después and tcp.analysis.retransmission. Con ello filtraremos los paquetes que fueron retransmitidos durante la reproducción.

Paquetes retransmitidos

En la parte de inferior de la ventana veremos dos valores, Packets y Displayed, estos valores nos ayudarán a calcular la pérdida de paquetes.

Packets indica la cantidad total de paquetes transmitidos durante toda la conversación, el cual fue de 21062.  Displayed muestra la cantidad de paquetes retransmitidos filtrados, el cual fue de 913 , entonces, haciendo una regla de 3 obtenemos que el porcentaje de paquetes perdidos fue de 4.33%.

Para garantizar una buena calidad en el servicio se necesita tener una cantidad de paquetes perdidos menor o igual al 3% del volumen de datos transmitido, el resultado de esta medición nos indica que la cantidad de paquetes perdidos fue 1.33% arriba de lo permitido, por lo que ya esta fuera de los límites recomendados. Sin embargo la medición permanece por debajo del porcentaje permitido para las líneas ADSL el cual es de 5% del volumen de datos transmitido.

3. Medición tasa de transferencia

Metodología

La tasa de transferencia se analiza desde el menú Statistics > Conversations, en la ventana emergente seleccionamos la pestaña TCP y la tabla la ordenamos de mayor a menor utilizando la columna  Bytes A←B. Así la primera fila será la conversación con más bytes transmitidos, la cual debe ser el stream de video.

Análisis de la tasa de transferencia

Resultados

Aqui nos interesan 3 columnas, las marcadas como  Bytes A←B, Duration y bps A←B.

La columna  Bytes A←B nos indica la cantidad de bytes transmitidos, el cual fue de 14 660 397bytes o  13.95MB aproximadamente, éste es el tamaño del video.

La columna Duration indica la duración de la conversación TCP en segundos, la cual fue de 440.21s, o aproximadamente 7.33 minutos.

La columna bps A←B muestra la tasa de transferencia, la cual fue de 266421.81bps o 266.422Kbps.

Aquí es donde obtuvimos los peores resultados, el valor teórico lanza una tasa de transferencia de 1.2Mbps aproximadamente, de acuerdo a los parámetros de codificación de Youtube; la medición práctica nos indica una tasa de transferencia de 266.422Kbps, es decir, aproximadamente un 22% de lo esperado.

El resultado no sorprende en realidad, ya que la duración real del video reproducido es de 5:33 minutos y la duración de la conversación fue de 7.33 minutos, 2 minutos de retraso.

También podemos ver que el valor teórico recomendado para la configuración del video recomendado es muy alto, posiblemente se utilizó un códec diferente para el video seleccionado.

Conclusiones

• Latencia
• Esperado: menor a 150ms
• Obtenido: 47.115ms
• Jitter:
• Esperado: menor a 50ms
• Obtenido: 17.425ms
• Perdida de paquetes:
• Esperado: menor o igual al 3% del volumen de datos transmitido
• Obtenido: 4.33% del volumen de datos transmitido
• Tasa de transferencia:
• Esperado: 1152Kbps o 1.2Mbps aprox.
• Obtenido: 266.422Kbps

Mientras la conexión con el servidor de Youtube se mantuvo muy limpia, la transmisión del video fue insatisfactoria.

Una alta pérdida de paquetes y tasas de transferencia tan bajas pueden ser indicador de una alta congestión en los servidores de la compañía.

Se concluye entonces que, bajo las condiciones establecidas para el experimento, la calidad en el servicio es insatisfactoria, lo que repercute en la experiencia de usuario.

Referencias:

• http://ask.wireshark.org/questions/5597/how-to-capture-traffic-from-youtube
• http://blog.davidvassallo.me/2011/01/07/identifying-network-latency-jitter-issues-w-wireshark/
• http://www.cardinalpeak.com/blog/?p=1054
• http://www.nessoft.com/kb/article/what-is-jitter-57.html
• http://www.wireshark.org/lists/wireshark-users/200802/msg00231.html
• http://ask.wireshark.org/questions/5675/how-to-analyse-througput-packet-loss-rtt-rather-than-go-through-the-graph-of-built-in-feature-of-wireshark
• http://www.wireshark.org/docs/dfref/t/tcp.html

[Lab CU] Actividad 4: Observaciones y recomendaciones para los proyectos

Para esta entrada hay que realizar comentarios y cualquier tipo de retroalimentación a las presentaciones  sobre diseño conceptual y contextual de los proyectos de otros compañeros.

...

Casa segura (Rene, Raúl, Iván)

El proyecto esta interesante, pero la recomendación les doy es orientar correctamente su proyecto. Actualmente 2 temas se mezclan en el proyecto, la seguridad y la automatización. Se podría definir el alcance del proyecto para obtener mejores resultados, pues en su encuesta se realizan preguntas sobre diferentes tópicos. O en caso contrario, dividir su proyecto en 2 partes y realizar encuestas centradas en un tema especifico.

Enfocando su proyecto pueden además ofrecer servicios modulares dependiendo del tipo de servicio que el usuario necesite, asi pueden cubrir desde necesidades básicas de seguridad para casas, oficinas, industrias, hasta suites completas de seguridad y automatización.

También recomiendo estudiar el mercado para ofrecer en su producto algunas "features" interesantes, algo diferente a lo existente

En esta liga vienen buenos contenidos: http://domoticamexico.blogspot.mx/

...

Garage Inteligente (Emmanuel, Max, Carmen, Victor)

El proyecto parece bastante intuitivo y novedoso, sin embargo deben analizar muy bien los clientes a quienes quieren orientarse. Pienso que es posible obtener beneficio incluso de quienes no tienen garage, puede ser algún sistema automatizado para abrir todo tipo de puertas de forma remota, ofrecer variaciones del producto a otros campos.

También considero buena idea unificar los prototipos 3 y 4 que mostraron, ¿porqué no hacer una aplicación de smartphone que se conecte a un servicio web? Suena viable, no creo que sea muy costoso implementarlo y así se logra algo más unificado.

Una oportunidad de desarrollo a futuro es formar alguna alianza con fabricantes de puertas automáticas para garages. Pueden vender su idea o hacer un acuerdo de cooperación, ya que el sistema no es solamente la aplicación, sino todo el hardware que se necesita para abrir la puerta, entonces ahí es donde conviene mucho hablar con fabricantes de este tipo de puertas.

Es todo, pienso tiene todo muy bien cubierto y planeado.

...

Bloqueo mágico de computadora (Obed, Ave, Pedro, Jona)

Algo interesante para éste proyecto puede ser convertirla en una API para todo tipo de aplicaciones. En un principio la idea suena bien, crear una aplicación aparte que controlé las aplicaciones compatibles de forma remota, pero después crear una API para que los desarrolladores puedan embeber las propiedades del sistema que desarrollarán en otro tipo de aplicaciones. Así su aplicación puede ser incluso hasta un servicio más en los sistemas operativos.

Otra cosa que deben cuidar es la seguridad, ver que la aplicación no sea vulnerable y pueda ser utilizada por terceros para monitorear otros usuarios. Ya sea aplicar algún sistema de bloqueo para que nadie interfiera en el proceso de la aplicación y tomar el stream que está siendo grabado.

Me parece una buena idea en absoluto, espero que si se desarrolle hasta el final, sobre todo porque no encontré muchas referencias a algo parecido (pero si algunos sistemas de reconocimiento facial), pienso es una gran idea.

...

Galeria Inteligente (Blanca, Vanessa, Adriana, Rodolfo)

Muy interesante el proyecto, sin embargo, sería bueno orientar las encuestas al grupo correcto de personas, en lugar de tomar una muestra de personas general tomar una muestra de personas de una población que acostumbre a visitar museos o galerías de arte. Hacer las encuestas a la salida de los museos y galerías puede funcionar muy bien.

También sería bueno presentar el concepto de galería inteligente, qué es una galería inteligente y qué tipo de servicios ofrece.

Después se puede presentar la propuesta del proyecto propio, presentarle a los usuarios qué es lo que ofrecerán y cómo pueden lograrlo, prototipos de baja fidelidad como bocetos, presentación de los diversos escenarios.

Otra opción puede ser presentar lo qué haría que el producto resalte, por ejemplo, la tecnología. Si el usuario utilizará su smartphone vía WIFI, bluetooth o QR codes para obtener la información de las obras de arte.

Por último recomiendo modificar el nombre del proyecto, ya que buscando por conceptos similares solo encontré uno solo el museo de Luvre el cual fue preparado por IBM para ser inteligente, el concepto inteligente se refiere a las tecnologías de seguridad instaladas:

http://www-03.ibm.com/press/es/es/pressrelease/37021.wss

El proyecto que presentan es más una galería interactiva

Es un buen proyecto, no se cierren a un solo tipo de concepto, se pueden utilizar todas las tecnologías que proponen para lograr algo más interactivo.

...

Alarma de automóvil (Alex, Ricardo, Sergio, Roberto)

Recomiendo presentar la aplicación de una forma mas concreta y precisa, sería bueno realizar un prototipo que explique la forma en la que el usuario interactuará con el sistema propuesto.

Presentar también el tipo de tecnologías incluidas y explicarlas en el contexto.

Lo anterior lo menciono porque con el transcurso de su presentación la alarma se vuelve más compleja convirtiéndose en un sistema de notificaciones completo.

Se pueden presentar las diferentes formas en la que interactúan los módulos del proyecto para llegar al resultado final, por ejemplo:

1 tecnología de detección > 2 suena la alarma > 3 Obtener información GPS > 4 envío de la notificación sobre el incidente

También elegir un sistema más amplio de notificaciones, como por ejemplo, hacer un broadcast del incidente a una lista de usuarios predefinidos por el usuario principal, incluso agregar notificaciones a las instancias de seguridad pública para que se tomen cartas en el asunto inmediatamente.

Muy buen proyecto, solo falta enfocarlo correctamente

...

Pulsera GPS (Omar, Saúl Isaías)

En esencia, la idea es buena, sin embargo deben estudiar mucho mejor el mercado existente.

El problema con el proyecto es que ya existen muchos productos muy parecidos en el mercado, donde empresas expertas ya han desarrollado productos bastante avanzados.

Lo que se podría hacer es crear un tipo de servicio en forma de una aplicación para smarthphone, no creo que sea necesario que los usuarios compren otro teléfono o incluso un gadget más como sería un localizador. Pueden aprovechar el hecho que el uso del smartphone ya esta bastante extendido, tienen el hardware incluído en los mismos equipos y además pueden utilizar las tecnologías ahí incluídas como la comunicación WI-FI, GSM/3G, GPS Asistido, etc.

Se puede cambiar a un servicio transparente, es decir, que el usuario pueda abrir la aplicación como un servicio transparente y que cada cierto tiempo o distancia recorrida envíe su información a algún servidor, para mayor seguridad, puede ser un servidor en la casa del mismo usuario.

Éste sistema sería más transparente para el usuario, se llevaría un control de los lugares que ha visitado y a partir de ahí generar otro tipo de datos como gráficas o recomendaciones de lugares para visitar.

La aplicación se complementaría con un botón de pánico, o un algoritmo inteligente que detecte cuando el usuario se mueva por lugares extraños en la ciudad.

Mis recomendaciones son esas, pero sobre todo, analizar el mercado para entender bien a la competencia y obtener el contexto de la competencia más que de los usuarios. Se puede hacer una encuesta a usuarios de éste tipo de productos y analizar sus espectativas al utilizarlos; así ustedes podrán desarrollar aquellas características que sean de interés para los usuarios pero que no hayan sido tomadas en cuenta por los otros fabricantes.

...

Oficina Inteligente (Lupe, Osvaldo, Triana, Esteban)

Es un proyecto bastante completo que toma en cuenta muchos aspectos.

Pienso que lo mejor hubiera sido que fueran más arriba, es decir, con las personas que compran las oficinas, es decir, los verdaderos dueños de los corporativos ya que son ellos quienes realmente saben lo que se necesita en una oficina. De ahí la entrevista partiría para detectar cuales son las verdaderas necesidades de una oficina inteligente, cuáles son de primera prioridad, de segunda, qué ideas son necesarias pero que nadie ofrece, etcétera. Así pueden garantizar ofrecer un servicio a la medida de las necesidades del cliente

También las características actuales que ofrecen son de muy variados tipos, entonces recomiendo lo mismo que la casa segura, crear varias divisiones del proyecto y, ya sea, centrarse en una sola o en todas pero ofreciendo diferentes configuraciones a la carta.

Son mis recomendaciones, todo lo demás lo percibo bien identificado.

...

Despertador inteligente (Ramón, Cecy, Roberto)

Me parece un excelente proyecto, bastante interesante la idea.

Justamente mi recomendación era que enfocaran mejor su proyecto, ya que el concepto de "cama inteligente" no cumplía al 100% con las verdaderas especificaciones.

Mi recomendación es que realicen varios prototipos diferentes para mostrar la alarma en diferentes modalidades, cada una con un nivel de dificultad diferente para apagarla, y así cubrir las necesidades de varios usuarios a la vez. Y no es necesario crear una interfaz diferente para cada una, sino que se puede complementar con una aplicación de smartphone que permita configurarla, ya sea vía Bluetooth o NFC.

Un buen prototipo puede ser aquella alarma que se apaga solo cuando acercas el tag NFC correcto, y el usuario puede pegar el tag en cualquier parte de su casa.

En fin, hay muchas posibilidades para el proyecto.

Me parece que lo demás ya lo tienen muy planeado.

...

Esas fueron mis observaciones y recomendaciones para los demás proyectos.

[Lab RT] Actividad 4: Parámetros de medición en QoS

Definición

"QoS (Calidad de Servicio) es un conjunto de requisitos que debe cumplir una red para el transporte de información"

QoS incorpora una serie de tecnologías que garantizan la capacidad de una red para dar un buen servicio a sus usuarios así como una buena experiencia de usuario, dicha garantía de debe mantener desde la planificación de una red y en todo el proceso de ingeniería posterior.

Arquitectura

Para garantizar la calidad en el servicio, detrás existe una completa arquitectura de medición que incluye:

• Puntos de medición: ubicados en los nodos de la red como routers, firewalls, hosts.
• Herramientas de medición de tráfico: que capturan los paquetes y recolectan información sobre el flujo de tráfico deseado.
• Herramientas de análisis: que analizan los datos recolectados y realizan cálculos estadísticos sobre la situación actual de la calidad en el servicio. El análisis puede hacerse en tiempo real y/o después del flujo de datos
• Monitores y bases de datos: que recolectan y almacenan los datos analizados.

El análisis puede ser centralizado en un servidor específico, o puede estar distribuido en toda la red

Parámetros de medición

Existen una gran cantidad de parámetros que sirven para medir el rendimiento de las aplicaciones en una red y se clasifican de diferentes formas:

• Medición objetiva: Que se refieren a aspectos concretos y cuantitativos como la perdida de paquetes, retardos, jitter, duración de la conexión.
• Medición subjetiva: Corresponde a aspectos desde la perspectiva del usuario, como el MOS (mean opinion score) que mide el impacto de las fallas en la experiencia del usuario.

Ejemplo categorías y parámetros de medición
Tiempo Intervalo de sincronización Tiempo de inicialización Tiempo de recuperación Latencia Retrasos Garantía Disponibilidad Volumen de tráfico Throughput Picos de volumen Precisión Precisión de direccionamiento Tasas de error Integridad	Robustez Confianza Mantenibilidad Resistencia Supervivencia Confiabilidad Costo Auditabilidad Manejabilidad Monitoreo Control Seguridad Autentificación Confidencialidad Seguridad de transmisión y tráfico

QoS en stream de video

Existen ciertos parámetros clave en la medición de la calidad de servicio al hacer stream de video, por ejemplo: youtube, vimeo o ustream.

Los parámetros clave para éste tipo de aplicaciones son:

• Pérdida de paquetes

La pérdida de paquetes ocurre cuando uno o más paquetes no logra alcanzar su destino. En esta categoría también se incluyen los paquetes descartados por la red en su camino al host destino.

Al tratarse de una comunicación en tiempo real, los stream de video está basado en UDP, al no estar orientado a la conexión los paquetes perdidos no se reenvían.

Para conexiones ADSL se admite un máximo de 3% del volumen de datos transmitido para la perdida de paquetes, este porcentaje se atribuye a "cuestiones de calidad" en el servicio y sus causas pueden ser la alta congestión en la red o los paquetes descartados por la red.

Síntoma de la pérdida de paquetes, fuente: http://www.plixer.com/blog/network-traffic-analysis/netflow-collection-what-is-packet-loss/

Se recomienda que la perdida de paquetes durante un stream de video sea de un 2%, sin embargo, este porcentaje depende del códec utilizado. Entre mayor compresión, mas perjudicial es la pérdida de datos y el umbral permitido disminuye.

• Latencia

Son los retardos que existen dentro de una red producidos principalmente por la congestión de la misma que obliga a los paquetes a esperar en largas colas o a tomar rutas alternas (mas largas) para llegar a su destino.

Básicamente se trata del tiempo que tarda un paquete en llegar al host destino.

En promedio, la latencia se encuentra entre 50 y 100 ms. Durante la transmisión de video se recomiendan latencias menores a 150ms.

El ser humano puede detectar un retardo cuando la latencia es mayor a 200 ms.

• Jitter

Es un efecto propio de las redes de datos no orientadas a la conexión. El stream de datos se discretiza en paquetes donde cada uno puede seguir una ruta diferente para alcanzar su destino.

El jitter mide la variación en el tiempo de llegada de los paquetes o la variación de la latencia.

Como vemos, el jitter depende de la latencia.

El valor recomendado de jitter para la transmisión de video es de 30 ms, lo cual es un buen umbral para que la latencia no alcance valores superiores a 150ms

Una alta latencia puede ocasionar que un video no se cargue adecuadamente.

La latencia y el jitter son conceptos que afectan a los buffers de video.

• Tasa de transferencia y vaciado del buffer

Aún si la latencia es baja, la tasa de transferencia puede afectar mucho la experiencia de usuario al visualizar un video.

La tasa de transferencia depende del ancho de banda, la cual esta compartido con múltiples aplicaciones al mismo tiempo.

La tasa de transferencia es la cantidad de información o datos que se envían a través de una conexión de red en un periodo de tiempo establecido. Por lo general de mide en bits por segundo (bps), kilobits por segundo (Kbps) o megabits por segundo (Mbps).

Por ejemplo, Youtube utilizando el códec FLV para un video en 480p de resolución necesita una tasa de transferencia de hasta 1Mbps más 128 Kbps para audio codificado bajo el códec AAC, añadiendo las cabeceras de los paquetes se pueden requerir hasta 1.2Mbps de tasa de transferencia. El vaciado del buffer es igual a la tasa de transferencia requerida en la red. Entonces, si la tasa de transferencia es menor a lo requerido, el usuario puede experimentar retrasos en la reproducción del video.

¡Hasta 6Mbps si elegimos una calidad de 1080p!

Por lo general los ISP proveen planes de banda ancha que permiten tasas de transferencia desde 1Mbps, pero hay que tomar en cuenta que la conexión puede ser compartida por diversos equipos y que cada equipo tiene multiples procesos que utilizan una parte de esa banda ancha, asi que aún con 2Mbps se pueden experimentar retrasos en los stream de video.

Experimento

Para la actividad de medición de la calidad en el servicio QoS se tomarán en cuenta los parámetros analizados:

• Stream de video de Youtube, sobre la red Infinitum utilizando conexión cableada Ethernet
• Medir la perdida de paquetes, que no sobrepase el 3%
• Medir la latencia, que se mantenga menor a 150ms
• Medir el jitter, que se mantenga menor a 50ms (ampliar el umbral)
• Medir la tasa de transferencia.

Referencias

• http://www.moviquity.com/easywireless/proceedings/1.2%20QoS%20Measurements%20Methods%20and%20Tools.pdf
• http://searchunifiedcommunications.techtarget.com/definition/QoS-Quality-of-Service
• http://www.dte.us.es/personal/mcromero/masredes/docs/SMARD.0910.qos.pdf
• http://www.aiotestking.com/cisco/2012/08/which-qos-requirement-applies-to-streaming-video-traffic/
• http://networkjutsu.com/qos-requirements-for-video/
• http://www.cisco.com/en/US/docs/solutions/Enterprise/WAN_and_MAN/QoS_SRND/QoSIntro.html#wp46626
• http://www.voipforo.com/QoS/QoSVoip.php
• http://www.networkworld.com/community/node/37865

[IT] Homework 2: Coupling text methods: Boyer-Moore & Knuth-Morris-Pratt

Implementation of Knuth-Morris-Pratt and Boyer-Moore algorithms in Python, written by me:

	#!/usr/bin/python
	from time import time
	from sys import argv
	def generateWord(l):
	w = ["a"] * l
	return "".join(w)
	def KMP(pattern, text):
	index = 0
	m, n = len(text), len(pattern)
	attempts, comparisons = 0, 0
	#print "Text >> %s"%(text)
	#print "Pattern >> %s"%(pattern)
	while(index < m-n+1):
	try:
	attempts += 1
	segment = text[index:index+n]
	#print "\nSegment >> %s"%(segment)
	for i, (p,s) in enumerate(zip(pattern, segment)):
	#print "[%d]: %s - %s"%(i, p, s)
	comparisons += 1
	if(s != p):
	index += i
	#print "Mismatch at index %d"%(index)
	break
	if(i == n-1):
	#print "Match at index %d"%(index)
	index += (n-2)
	break
	index += 1
	except: break
	#print "\nUsing Knuth-Morris-Pratt Algorithm"
	#print " String length: %d"%(m)
	#print "Pattern length: %d"%(n)
	#print " Attempts: %d"%(attempts)
	#print " Comparisons: %d"%(comparisons)
	return comparisons
	def BM(pattern, text):
	m, n = len(text), len(pattern)
	index, shift = n, 0
	attempts, comparisons = 0, 0
	pattern = "".join(reversed(pattern))
	#print "\nText >> %s"%(text)
	while(index <= m-1):
	try:
	attempts += 1
	segment = "".join(reversed(text[shift:shift+n]))
	#print "\nSlice [%d : %d]"%(shift,shift+n)
	#print "Pattern >> %s"%(pattern)
	#print "Segment >> %s"%(segment)
	for i, (p,s) in enumerate(zip(pattern, segment)):
	comparisons += 1
	shift += 1
	#print "[%d]: %s - %s"%(i, p, s)
	if(s != p):
	#print "Mismatch at index %d"%(index)
	break
	if(i == n-1):
	#print "Match at index %d"%(index)
	shift -= 1
	break
	index = shift+n
	except: break
	#print "\nUsing Boyer-Moore Algorithm"
	#print " String length: %d"%(m)
	#print "Pattern length: %d"%(n)
	#print " Attempts: %d"%(attempts)
	#print " Comparisons: %d"%(comparisons)
	return comparisons
	def main():
	patternLength = int(argv[1])
	wordLength = int(argv[2])
	repet = int(argv[3])
	p = generateWord(patternLength)
	t = generateWord(wordLength)
	comparisons = 0
	start = time()
	for i in range(repet):
	#comparisons += KMP(p,t)
	comparisons += BM(p,t)
	end = time()
	print "%d %f"%((comparisons/repet),((end-start)/repet))
	if(__name__=="__main__"):
	main()

view raw kmp_bm.py hosted with ❤ by GitHub

Execution

This is the code to automate all the execution:

	#!/usr/bin/python
	import subprocess
	from time import time
	start = time()
	wordLen = [100*a for a in range(1,11)]
	patternLen = [1+a for a in range(1,11)]
	repet = 30
	tempFile = "temp.dat"
	dataFile = "data.dat"
	open(tempFile,"w").close
	open(dataFile,"w").close
	print wordLen
	print patternLen
	print "[>] Launching experiment, please wait...\n"
	for a, wL in enumerate(wordLen):
	st = time()
	for b, pL in enumerate(patternLen):
	print "[>] Running experiment with word length %d and pattern length %d"%(wL, pL)
	for i in range(repet):
	commands = "python algorithms.py %d %d %d"%(pL, wL, repet)
	commands = commands.split(" ")
	res = subprocess.check_output(commands)
	#print res
	with open(tempFile, "a") as f: f.write("%d %d %d %s\n"%(i+1, wL, pL, res.rstrip("\t\n")))
	commands = "./channel.awk -v len=%d %s"%(wL, tempFile)
	commands = commands.split(" ")
	res = subprocess.check_output(commands)
	with open(dataFile, "a") as f: f.write("%d %d %s\n"%(wL, pL, res.rstrip("\t\n")))
	open(tempFile,"w").close
	with open(dataFile, "a") as f: f.write("\n")
	elapsedTime = (time() - st)
	print "Elapsed time >> %0.2f seconds"%(elapsedTime)
	print "Elapsed time >> %0.2f seconds from the start\n"%(time()-start)
	print "[O] Experiment completed\n"
	print "[>] Plotting data"
	subprocess.call(["gnuplot", "time.plot"])
	print "[O] Done!"
	print "[>] Plotting data"
	subprocess.call(["gnuplot", "comp.plot"])
	print "[O] Done!"
	print "[O] Experiment finished\n"
	elapsedTime = (time() - start)
	print "Total elapsed time >> %0.2f seconds\n"%(elapsedTime)
	exit()

view raw experiment.py hosted with ❤ by GitHub

Experiment

My initial conditions was:

• Word length: from 100 to 1000
• Pattern length: from 2 to 11
• Repetitions: 30

I made all the posible conditions between these values, iterating the pattern length through each word length, and also running each combination 30 times.

Results

Knuth-Morris-Pratt
Time	Comparisons
Boyer-Moore
Time	Comparisons

I wrote these codes after understanding the following examples:

• http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
• http://www-igm.univ-mlv.fr/~lecroq/string/node8.html 
• http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

[Lab VC] Actividad 2: Convex Hull

Para la tercer actividad de laboratorio se tuvo que programar las rutinas necesarias para hallar el convex hull en una imágen dada.
Convex Hull o envolvente convexa es un algoritmo que, dados los puntos de un objeto en una imágen, permite crear un polígono que encierra todos los puntos de dicho objeto, como si un cinturón los envolviera.

Para lograr ésto es necesario identificar los pixeles del borde del objeto que queremos encerrar, para lograr ésto utilicé la técnica de detección de formas aplicada en la tarea 2:

http://juankenny.blogspot.com/2013/02/vc-tarea-2-deteccion-de-formas.html

En la entrada se explica la aplicación del algoritmo BFS para la detección de formas y el fondo de la imágen, también se explica como lograr unos buenos bordes gruesos y continuos para obtener buenos resultados.

Para aplicar el convex hull utilicé las siguientes imágenes:

Ahora, la instrucción para detectar un objeto dada una imágen binarizada es tomar aquellos pixeles de color negro, ya que los de color blanco se consideran del borde. Bien, para el convex hull se supone lo contrarío, detectar los pixeles blancos como objeto porque ahora queremos los pixeles que conforman el borde. Aquí identificamos los pixeles del borde, los pintamos de un color diferente.


Ahora, la rutina programada para BFS nos regresa los pixeles del borde, lo que haremos con esos pixeles será dárselos como entrada al algoritmo de convex hull. El algoritmo elegido para dicha tarea fue Graham Scan

...

Graham Scan

Se usará una variación del algoritmo Graham Scan que divide el convex hull en 2 partes: superior e inferior. Los pasos que realiza este algoritmo para hallar el convex hull son:

• Ordenar los puntos de mayor a menor de acuerdo al eje y, si dos puntos comparten la misma coordenada entonces se ordenan de acuerdo al eje x.
• El primer punto es el que se encuentre más a la parte inferior izquierda, se recorre la lista tomando 3 puntos en todo momento, uno inicial, uno medio y uno final.
• Se comprueba si el cambio de dirección dados los 3 puntos es positivo o negativo.
• Si es negativo entonces puede ser candidato del hull inferior, si es positivo entonces puede formar parte del hull superior.

Así se van eliminando candidatos hasta que quedan aquellos que son los vértices de la figura. Como tenemos 2 hull diferentes tenemos que unirlos, sabemos que ambos comparten los vértices que se encuentren más a la izquierda y a la derecha. Simplemente tomamos una de las 2 listas, eliminamos los puntos extremos que corresponderían a estos puntos, giramos la lista para ponerla en orden y finalmente sumamos ambas listas superior e inferior.

Para una explicación más completa recomiendo el siguiente documento: http://intinno.iitkgp.ernet.in/courses/91/wfiles/29755

...

El algoritmo nos regresa los puntos correspondientes a los vértices mas extremos dado el borde de un objeto en la imagen, pintamos los vértices para identificarlos.


Por ultimo, concateno los puntos en una lista continua de tuplas y se la paso a Tkinter para que dibuje un polígono con ellos que envuelva a los pixeles del objeto dado.

0.604544878006 s (400x300)	0.413755893707 s (350x263)
0.922349214554 s (450x291)	2.62748289108 s (1004x465)

Enla parte superior se pueden ver los tiempos de ejecución para cada imágen, sirven para comparar el rendimiento del algoritmo. Los tiempos se tomaron desde el punto donde BFS toma el borde como objeto hasta el dibujo del convex hull.

Así concluye la actividad.

Código

Código Graham Scan

	TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0) # Vueltas
	def turn(p1, p2, p3): # Funcion que regresa hacia donde es la vuelta de los pixeles
	return cmp((p2[0] - p1[0])*(p3[1] - p1[1]) - (p3[0] - p1[0])*(p2[1] - p1[1]), 0) # Calculamos la vuelta y regresamos su valor
	def graham_scan(points): # Graham Scan
	u = list() # Hull superior
	l = list() # Hull inferior
	points.sort() # Ordenamos los pixeles
	for p in points: # Recorremos todos los pixeles
	while len(u) > 1 and turn(u[-2], u[-1], p) <= 0: # Verificamos que el pixel no sea candidato del hull superior
	u.pop() # Si no es candidato lo sacamos
	while len(l) > 1 and turn(l[-2], l[-1], p) >= 0: # Verificamos que el pixel no sea candidato del hull inferior
	l.pop() # Si no es candidato lo sacamos
	u.append(p) # Agregamos el pixel como candidato al hull superior
	l.append(p) # Agregamos el pixel como candidato al hull inferior
	l = l[1:-1][::-1] # Eliminamos los pixeles derecho e izquiedo mas extremos y giramos
	l += u # Concatenamos la lista de hulls
	return l # Regresamos la lista de puntos de los hulls

view raw grahamScan.py hosted with ❤ by GitHub

Código para dibujar el convex hull en el canvas

	def convexHull(): # Dibujar convex hull
	global app # Para modificar el canvas
	start = time() # Medimos el tiempo
	objects = objectClassification((255,255,255)) # Obtenemos la informacion del borde usando clasificacion de objetos
	for mObject in objects: # Recorremos los bordes de las figuras encontradas
	hulls= filters.graham_scan(mObject["pixels"]) # Enviamos los pixeles a la funcion de convex hull
	points = list() # Los puntos del convex hull
	for hull in hulls: # Recorremos la lista de puntos regresada por el Graham Scan
	points += list(hull) # Convertimos los puntos en una lista continua para Tkinter
	#app.edit_canvas.create_oval(hull[0]-3, hull[1]-3, hull[0]+3, hull[1]+3, fill="black", outline="red") # Dibujar un punto en cada vertice del convex hull
	app.edit_canvas.create_polygon(points, outline="red", fill="", width=3.0) # Creamos un poligono que encierre la figura usando los puntos del convex hull
	print (time() - start) # Terminamos de medir el tiempo
	return # Finaliza la funcion

view raw convexHull.py hosted with ❤ by GitHub

Referencias:
http://personal.us.es/almar/docencia/practicas/envolvente/tema5.html
http://tomswitzer.net/2010/03/graham-scan/