Tarea 5: Experimento de congestión

Se nos pide averiguar cómo se genera tráfico con distintas propiedades y cómo podemos monitorear las medidas de desempeño (mencionadas en la clase) en su simulador, para luego modificar un esquema de congestión

Hice un programa en el cual puedes generar los siguientes tipos de tráfico.

• Trafico CBR (Constant bit rate)
• Trafico exponencial
• Trafico Pareto

De manera que por medio de los argumentos dados al correr la simulación se puede especificar de la siguiente manera sus entradas.

ns simulacion.tcl [Topologia] [Tipo de trafico] [Tamaño de paquetes] [Rate] [Esquema]

Por ejemplo podemos correr el programa de la siguiente manera.

ns simulacion.tcl arbol CBR 1000 1mb Heap

Se nos pide realizar un experimento sobre nuestra simulación es por eso que hice un python que obtiene del archivo .nam los valores de kbps y el tiempo para graficar la medida de desempeño Throughput de manera que podamos saber como afecta el trafico a un nodo udp con CBR en diferentes tamaños de paquetes y rates.

Obtuvimos los siguientes resultados.

De manera que podemos observar que al agregar paquetes más pesados en un rate medianamente alto se transmite menos flujo por segundo, pero con mayor cantidad de información, este experimento fue realizado con una topología de árbol y generando trafico CBR dado el ns2.


Este es el código.

	set sim [new Simulator]
	set archivo_1 [open salida_1.nam w]
	$sim namtrace-all $archivo_1
	proc termina_1 {} {
	global sim archivo_1
	$sim flush-trace
	close $archivo_1
	exec nam salida_1.nam &
	exit 0
	}
	#Nodos suficientes para topologia
	set padre [$sim node]
	set hijo1 [$sim node]
	set hijo2 [$sim node]
	set hijo3 [$sim node]
	set ter1 [$sim node]
	set ter2 [$sim node]
	set ter3 [$sim node]
	set ter4 [$sim node]
	set ter5 [$sim node]
	#conexiones para topologia arbol
	proc conecta_arbol {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo3 2Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo2 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo1 $hijo3 15
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $hijo3 $ter2 10
	$sim queue-limit $hijo3 $ter3 10
	$sim queue-limit $hijo2 $ter4 10
	$sim queue-limit $ter3 $ter5 10
	$sim duplex-link-op $padre $hijo1 orient down
	$sim duplex-link-op $hijo1 $hijo2 orient down-right
	$sim duplex-link-op $hijo1 $hijo3 orient down-left
	$sim duplex-link-op $hijo3 $ter1 orient down-left
	$sim duplex-link-op $hijo3 $ter2 orient down-right
	$sim duplex-link-op $hijo3 $ter3 orient down
	$sim duplex-link-op $ter3 $ter5 orient down
	$sim duplex-link-op $hijo2 $ter4 orient down-right
	}
	#conexiones para topologia estrella
	proc conecta_estrella {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $padre $hijo2 2Mb 10ms DropTail
	$sim duplex-link $padre $hijo3 2Mb 10ms DropTail
	$sim duplex-link $padre $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $padre $hijo2 15
	$sim queue-limit $padre $hijo3 15
	$sim queue-limit $padre $ter1 10
	$sim queue-limit $padre $ter2 10
	$sim queue-limit $padre $ter3 10
	$sim queue-limit $padre $ter4 10
	$sim queue-limit $padre $ter5 10
	$sim duplex-link-op $padre $hijo1 orient down
	$sim duplex-link-op $padre $hijo2 orient down-right
	$sim duplex-link-op $padre $hijo3 orient down-left
	$sim duplex-link-op $padre $ter1 orient up-left
	$sim duplex-link-op $padre $ter2 orient up-right
	$sim duplex-link-op $padre $ter3 orient up
	$sim duplex-link-op $padre $ter5 orient right
	$sim duplex-link-op $padre $ter4 orient left
	}
	#conexiones para topologia anillo
	proc conecta_anillo {} {
	global sim padre ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim duplex-link $ter5 $padre 1.5Mb 10ms DropTail
	$sim queue-limit $padre $ter1 10
	$sim queue-limit $ter1 $ter2 10
	$sim queue-limit $ter2 $ter3 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter5 10
	$sim queue-limit $ter5 $padre 10
	$sim duplex-link-op $padre $ter1 orient down-right
	$sim duplex-link-op $ter1 $ter2 orient down
	$sim duplex-link-op $ter2 $ter3 orient down-left
	$sim duplex-link-op $ter3 $ter4 orient up-left
	$sim duplex-link-op $ter4 $ter5 orient up
	$sim duplex-link-op $ter5 $padre orient up-right
	}
	#conexiones para topologia mixta
	proc conecta_mixto {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $padre $hijo2 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo1 $ter1 2Mb 10ms DropTail
	$sim duplex-link $hijo2 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $hijo3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim duplex-link $ter5 $ter2 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $padre $hijo2 15
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo2 $ter2 10
	$sim queue-limit $ter2 $ter1 10
	$sim queue-limit $ter1 $hijo3 10
	$sim queue-limit $hijo3 $ter3 10
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter1 10
	$sim queue-limit $ter4 $ter5 10
	$sim queue-limit $ter5 $ter2 10
	$sim duplex-link-op $padre $hijo1 queuePos 0.5
	$sim duplex-link-op $padre $hijo2 queuePos 0.5
	$sim duplex-link-op $hijo1 $hijo2 queuePos 0.5
	$sim duplex-link-op $hijo2 $ter2 queuePos 0.5
	$sim duplex-link-op $ter2 $ter1 queuePos 0.5
	$sim duplex-link-op $ter1 $hijo3 queuePos 0.5
	$sim duplex-link-op $hijo3 $ter3 queuePos 0.5
	$sim duplex-link-op $hijo3 $ter1 queuePos 0.5
	$sim duplex-link-op $ter3 $ter4 queuePos 0.5
	$sim duplex-link-op $ter4 $ter1 queuePos 0.5
	$sim duplex-link-op $ter4 $ter5 queuePos 0.5
	$sim duplex-link-op $ter5 $ter2 queuePos 0.5
	}
	#conexiones para topologia lineal
	proc conecta_lineal {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo2 $hijo3 2Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo2 $hijo3 15
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $ter1 $ter2 10
	$sim queue-limit $ter2 $ter3 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter5 10
	$sim duplex-link-op $padre $hijo1 orient left
	$sim duplex-link-op $hijo1 $hijo2 orient left
	$sim duplex-link-op $hijo2 $hijo3 orient left
	$sim duplex-link-op $hijo3 $ter1 orient left
	$sim duplex-link-op $ter1 $ter2 orient left
	$sim duplex-link-op $ter2 $ter3 orient left
	$sim duplex-link-op $ter3 $ter4 orient left
	$sim duplex-link-op $ter4 $ter5 orient left
	}
	proc llamada {topo} {
	if {$topo == "estrella"} {
	conecta_estrella
	} elseif {$topo == "arbol"} {
	conecta_arbol
	} elseif {$topo == "anillo"} {
	conecta_anillo
	} elseif {$topo == "mixto"} {
	conecta_mixto
	} elseif {$topo == "lineal"} {
	conecta_lineal
	} else {
	puts "Selecciona un comando, prueba arbol"
	conecta_arbol
	}
	}
	proc control {sch} {
	global sim
	if {$sch == "Calendar"} {
	$sim use-scheduler Calendar
	} elseif {$sch == "List"} {
	$sim use-scheduler List
	} elseif {$sch == "Heap"} {
	$sim use-scheduler Heap
	} else {
	$sim use-scheduler Calenadar
	}
	}
	set topo [lindex $argv 0]
	set gene [lindex $argv 1]
	set tam_paq [lindex $argv 2]
	set rate [lindex $argv 3]
	set sch [lindex $argv 4]
	puts "Topologia seleccionada: $topo Tipo de trafico: $gene Tamano de paquete: $tam_paq Rate: $rate Scheme: $sch"
	control $sch
	llamada $topo
	global sim padre ter4 ter5
	set tcp [new Agent/TCP]
	$sim attach-agent $padre $tcp
	set sink [new Agent/TCPSink]
	$sim attach-agent $ter4 $sink
	$sim connect $tcp $sink
	set tcp2 [new Agent/TCP]
	$sim attach-agent $padre $tcp2
	set sink2 [new Agent/TCPSink]
	$sim attach-agent $ter5 $sink2
	$sim connect $tcp2 $sink2
	set ftp [new Application/FTP]
	$ftp attach-agent $tcp
	set ftp2 [new Application/FTP]
	$ftp2 attach-agent $tcp2
	set udp [new Agent/UDP]
	$sim attach-agent $padre $udp
	set null [new Agent/Null]
	$sim attach-agent $ter4 $null
	$sim connect $udp $null
	if {$gene == "CBR"} {
	puts "algo"
	set traffic [new Application/Traffic/CBR]
	$traffic attach-agent $udp
	$traffic set type_ CBR
	$traffic set packetSize_ $tam_paq
	$traffic set rate_ $rate
	$traffic set random_ false
	} elseif {$gene == "Expo"} {
	set traffic [new Application/Traffic/Exponential]
	$traffic attach-agent $udp
	$traffic set packetSize_ $tam_paq
	$traffic set rate_ $rate
	$traffic set burst_time_ 500ms
	$traffic set idle_time_ 50ms
	} elseif {$gene == "Pareto"} {
	set traffic [new Application/Traffic/Pareto]
	$traffic attach-agent $udp
	$traffic set burst_time_ 500ms
	$traffic set idle_time_ 50ms
	$traffic set rate_ $rate
	$traffic set packetSize_ $tam_paq
	$traffic set shape_ 1.5
	} else {
	puts "Selecciona un comando, prueba CBR"
	set traffic [new Application/Traffic/CBR]
	$traffic attach-agent $udp
	$traffic set type_ CBR
	$traffic set packetSize_ $tam_paq
	$traffic set rate_ $rate
	$traffic set random_ true
	}
	$sim at 0.001 "$traffic start"
	$sim at 0.01 "$ftp start"
	$sim at 0.5 "$ftp stop"
	$sim at 0.51 "$ftp2 start"
	$sim at 1.0 "$ftp2 stop"
	$sim at 1.5 "$traffic stop"
	$sim at 1.0 "termina_1"
	$sim run

view raw simulacion.tcl hosted with ❤ by GitHub

Métodos de diccionario-Byte pair encoding

Para este método se utiliza las repeticiones que sean iguales dentro de una cadena de manera que se sustituyen con variables para al final tener variables como referencia y una cadena más corta, para realizar este ejemplo hice en python una cadena aleatoria de la siguiente manera.

''.join(random.choice("abcde") for x in range(20))

De manera que tengamos una cadena de largo 20 y con un alfabeto A = {a, b, c, d, e}

Esta es la cadena que vamos a utilizar 'bbbeadbaaddadabceacb'

Encontramos los valores que podemos sustituir en la primera iteración

En la primera iteración buscamos caracteres que se repitan pero en bares diferentes por lo que primero voy a comprimir con la variable X a la repetición ea.

• bbbeadbaaddadabceacb
• X = ea

Luego en la segunda iteración encontramos caracteres repetidos como da.

• bbbXdbaaddadabcXcb
• Y = da

Ahora ya no tenemos caracteres diferentes que se repitan, por lo que empezamos a buscar caracteres del mismo tipo que se repitan en la cadena, encontramos bbb

• bbbXdbaadYYbcXcb
• Z = bbb

Encontramos al igual aa en la cuarta iteración.

• ZXdbaadYYbcXcb
• W= aa

Luego encontramos la letra YY repetida

• ZXdbWdYYbcXcb
• Q=YY

Ya no existen patrones de repetición por lo que esta sería nuestra cadena comprimida, junto con su diccionario.

• ZXdbWdQbcXcb
• X = ea
• Y = da
• Z = bbb
• W= aa
• Q=YY

Ahora para decomprimirlo, como ya tenemos el diccionario, en la primera iteración sustituimos la Q ya que esta contiene referencias al mismo diccionario.

• ZXdbWdQbcXcb
• ZXdbWdYYbcXcb

Luego sustituimos la W de la cadena que tenemos

• ZXdbaadYYbcXcb

Ahora, sustituimos la letra Z

• ZXdbaadYYbcXcb
• bbbXdbaadYYbcXcb

Luego, en la siguiente iteración, sustituimos las Y

• bbbXdbaadYYbcXcb
• bbbXdbaaddadabcXcb

Para después en la siguiente iteración y última con la variable X

• bbbXdbaaddadabcXcb
• bbbeadbaaddadabceacb

Entonces como resumen tenemos lo siguiente.

• Cadena = bbbeadbaaddadabceacb   
• largo = 20
• Cadena comprimida = ZXdbWdQbcXcb   
• largo = 12

Lab: Detección de hoyos

Para este laboratorio se nos pide realizar lineas en donde las intercesiones tengan hoyos, Aquí unas capturas de pantalla.

 

Este es el código.

	def boton_hoyos():
	#A grises
	imagen2 = cambiar_agrises(path_imagen_original)
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	umbral_valor = 0.2
	imagen = cambiar_umbral(imagen.convert("RGB"), umbral_valor)
	imagen.save("paso_2.jpg")
	pixeles_img = imagen.load()
	x, y = imagen.size
	pixeles = numpy.zeros(x*y).reshape((x, y))
	for a in range(x):
	for b in range(y):
	pixeles[a, b] = pixeles_img[a, b][0]
	col, fil = pixeles.shape
	suma_filas = []
	suma_col = []
	dibuja = ImageDraw.Draw(imagen2)
	for i in range(col):
	suma_col.append(pixeles[i].sum())
	for i in range(fil):
	suma_filas.append(pixeles[:, i].sum())
	maxcol, mincol, prueba_col = peakdet(suma_col, .1)
	maxfil, minfil, prueba_fil = peakdet(suma_filas, .1)
	coor_filas = []
	coor_col = []
	for i in range(len(suma_filas)):
	y = i
	PixMax = 255*col
	x = (((suma_filas[i]) * col) / PixMax)
	#print "(%s, %s)" %(str(x), str(y))
	dibuja.ellipse((x-2, y-2, x+2, y+2), fill="blue")
	if i in prueba_fil:
	coor_filas.append(y)
	dibuja.line((x, y, 0, y), fill="green")
	#dibuja.ellipse((x-4, y-4, x+4, y+4), fill="red")
	for i in range(len(suma_col)):
	x = i
	PixMax = 255*fil
	y = (((suma_col[i]) * fil) / PixMax)
	#print "(%s, %s)" %(str(x), str(y))
	dibuja.ellipse((x-2, y-2, x+2, y+2), fill="green")
	if i in prueba_col:
	coor_col.append(x)
	dibuja.line((x, y, x, 0), fill="red")
	#dibuja.ellipse((x-4, y-4, x+4, y+4), fill="red")
	imagen2.save("paso_algo.jpg")
	if coor_col < coor_filas:
	tam = len(coor_filas)
	else:
	tam = len(coor_col)
	coor_filas = coor_filas[::-1]
	#coor_col = coor_col[::-1]
	centros = []
	imagen_copia = imagen
	for i in range(tam):
	x = coor_col[i]
	y = coor_filas[i]
	print "(%s, %s)" %(str(x), str(y))
	print pixeles[x, y]
	color = (randint(170,230), randint(0,190), 255)
	if pixeles[x, y] == 0.0:
	imagen_copia, masa, c = BFS(imagen_copia.convert("RGB"), (x, y), color)
	x_suma = 0
	y_suma = 0
	for i in range(len(masa)):
	x_suma = x_suma + masa[i][0]
	y_suma = y_suma + masa[i][1]
	x_centro = x_suma/len(masa)
	y_centro = y_suma/len(masa)
	centros.append((x_centro, y_centro))
	#dibuja.ellipse((x-1, y-1, x+1, y+1), fill="yellow")
	imagen_copia.save("paso_3.jpg")
	label.destroy()
	poner_imagen(imagen2)
	global frame
	y = frame.winfo_height()
	imagen4 = cambiar_agrises(path_imagen_original)
	dibuja3 = ImageDraw.Draw(imagen4)
	for i in range(len(centros)):
	label_fig = Label(text = str(i))
	label_fig.place(x = centros[i][0], y = centros[i][1] + y)
	#dibuja3.ellipse((centros[i][0]-2, centros[i][1]-2, centros[i][0]+2, centros[i][1]+2), fill="yellow")
	dibuja3.line((x, y, x, 0), fill="red")
	imagen4.save("paso_4.jpg")

view raw hoyos.py hosted with ❤ by GitHub

Huffman adaptativo

Estuve trabajando para hacer el código huffman, lo que hice fue hacer un código que va pasando de 5 en 5 caracteres para ir formando el árbol para al final tener el código huffman, en realidad no se ha implementado el decodificador y en rendimiento no grafique.

	import collections
	import string
	import random
	import time
	class Hoja:
	def __init__(self, texto, prob, bit0=None, bit1=None):
	self.bit0 = bit0
	self.bit1 = bit1
	self.texto = texto
	self.prob = prob
	def genera_str(tam):
	return ''.join(random.choice(string.ascii_letters) for x in range(tam))
	def genera_str_alfa(tam, str):
	return ''.join(random.choice(str) for x in range(tam))
	def mostrar(arbol, nivel, bit=""):
	if arbol == None: return
	mostrar(arbol.bit1, nivel + 1, 1)
	print(" " * nivel + "[" + str(bit) + "] " + str(arbol.texto))
	mostrar(arbol.bit0, nivel + 1, 0)
	def experimento_2():
	x = 0
	str = string.ascii_letters
	str_fibo = "a"
	b = 0
	c = 1
	print "tam long tiempo_ran mayor_ran suma_ran compress_ran tiempo_fibo mayor_fibo suma_fibo compress_fibo"
	for i in range(len(str)):
	a = b + c
	c = b
	b = a
	if x != 0:
	str_fibo = str_fibo + str[x]*a
	#mixta = "".join(random.sample(str_fibo, len(str_fibo)))
	inicio = time.time()
	#print "Fibo:"
	mapa_1 = codificacion(str_fibo)
	fin = time.time()
	tiempo = fin - inicio
	inv_mapa_1 = {v:k for k, v in mapa_1.items()}
	mayor_1 = len(max(inv_mapa_1, key=len))
	suma_1 = sum(len(x) for x in inv_mapa_1)
	longitud = len(inv_mapa_1)*7
	alfa = str[:x+1]
	#print "Random:"
	str_ran = genera_str_alfa(len(str_fibo), alfa)
	inicio = time.time()
	mapa_2 = codificacion(str_ran)
	fin = time.time()
	tiempo_ran = fin - inicio
	inv_mapa_2 = {v:k for k, v in mapa_2.items()}
	mayor_2 = len(max(inv_mapa_2, key=len))
	suma_2 = sum(len(x) for x in inv_mapa_2)
	compress_bit_ran = float(suma_2)/float(longitud)
	compress_bit_fibo = float(suma_1)/float(longitud)
	print "%s %s %s %s %s %s %s %s %s %s" % (len(str_ran), longitud, tiempo_ran, mayor_2, suma_2, compress_bit_ran, tiempo, mayor_1, suma_1, compress_bit_fibo)
	x = x + 1
	def obtener_alfabeto(cadena):
	dic = collections.defaultdict(int)
	for letra in cadena:
	dic[letra] += 1
	alfa = []
	total = len(cadena)
	#print ("Alfabeto & prob:")
	#print cadena
	cod = ""
	for letra in sorted(dic, key = dic.get):
	prob = float(dic[letra])/float(total)
	#print("%s : %f" % (letra, prob))
	alfa.append((letra, prob, cod))
	#time.sleep(3)
	return alfa
	def mapa_codigos(arbol, alfa={}, lista=[]):
	if not arbol.bit1 and not arbol.bit0:
	alfa[arbol.texto] = "".join(lista)
	return
	lista.append("1")
	mapa_codigos(arbol.bit1, alfa, lista)
	lista.pop()
	lista.append("0")
	mapa_codigos(arbol.bit0, alfa, lista)
	lista.pop()
	def codificacion(cadena, alfa):
	mapeo = {}
	nodos = []
	for i in range(len(alfa)):
	hijo = Hoja(alfa[i][0], alfa[i][1])
	nodos.append((hijo.texto, hijo.prob, hijo))
	while (len(nodos) != 0):
	bit0 = nodos.pop(0)
	try:
	bit1 = nodos.pop(0)
	except IndexError:
	break
	texto_unido = str(bit0[0]) + str(bit1[0])
	suma = float(bit0[1]) + float(bit1[1])
	hoja = Hoja(texto_unido, suma, bit0[2], bit1[2])
	for i in range(len(nodos)):
	if nodos[i][1] > suma:
	index = i
	break
	nodos = nodos[:i] + [(hoja.texto, hoja.prob, hoja)] + nodos[i:]
	#print("Arbol: ")
	#mostrar(hoja, 0)
	mapa_codigos(hoja, mapeo)
	#print("Mapeo:")
	#print(mapeo)
	return mapeo
	def experimento_1(veces):
	print "datos random bits_ran prob bits_prob"
	x = 0
	for i in range(0, veces, 100000):
	if i != 0 and x < 10:
	str = (string.ascii_uppercase)*i
	inicio = time.time()
	mapa_1 = codificacion(str)
	fin = time.time()
	tiempo_prob = fin - inicio
	inv_mapa_1 = {v:k for k, v in mapa_1.items()}
	mayor_1 = len(max(inv_mapa_1, key=len))
	str_ran = genera_str(len(str))
	inicio = time.time()
	mapa_2 = codificacion(str_ran)
	fin = time.time()
	tiempo_ran = fin - inicio
	inv_mapa_2 = {v:k for k, v in mapa_2.items()}
	mayor_2 = len(max(inv_mapa_2, key=len))
	print "%s %s %s %s %s" % (len(str), tiempo_ran, mayor_2, tiempo_prob, mayor_1)
	x = x + 1
	def adap():
	with open("data.txt", "r") as archivo:
	cadena = archivo.read()
	for i in range(5, len(cadena)+5, 5):
	inicio = time.time()
	alfa = obtener_alfabeto(cadena[:i])
	mapa_1 = codificacion(cadena[:i], alfa)
	fin = time.time()
	tiempo = fin - inicio
	inv_mapa = {v:k for k, v in mapa_1.items()}
	mayor = len(max(inv_mapa, key=len))
	print "%s %s %s %s" % (len(cadena[:i]), len(mapa_1), tiempo, mayor)

view raw adap.py hosted with ❤ by GitHub

No alcancé a graficarlo.

Lab: Acceptance and Usability of Physical Mobile Application

Para el laboratorio de esta semana se nos piden realizar una investigación acerca de la usabilidad en cómputo ubicuo y que de igual manera pueda ser útil para nuestro proyecto, es por eso que en base a lo que estamos trabajando este semestre he decidido hablar acerca del paper Acceptance and Usability of Physical Mobile Applications cuyos autores son Tanja Herting y Gregor Broll.

Este paper trata acerca de las aplicaciones móviles en los cuales intervienen aparatos físicos y la combinaciones de gadgets móviles para la interacción de objetos presentes en el dia a dia, facilitando la interacción y asociando información y servicios a estos objetos, de manera que la usabilidad y la interacción del diseño de manera sistemática hace que tengamos diferentes categorías de aplicaciones según los casos de uso y patrones de interacción en un ambiente controlado, este paper se enfoca en el estudio de diferentes prototipos y evaluarlos de manera que se pueda generar ciertas guías para las mejores practicas en usabilidad de aplicaciones móviles.

Durante los últimos años, las aplicaciones de cómputo ubicuo ha incrementado el potencial de posibilidades para la interacción con objetos en donde antes no se tenía, es por eso que el desarrollo de tecnologías usando bluetooth, RFID, NFC o GPS hace que sea posible crear multiples aplicaciones para diferentes servicios y utilidades.

La interacción móvil fisica viene como concepto para tomar como ventaja estos desarrollos hablados anteriormente cuyos servicios usan aparatos móviles que interactuan con objetos fisicos para facilitar el descubrimiento, por ejemplo, de información.

En el paper tienen como clasificación grupos diferentes de PMA (Physical Mobile Applications), basados en diferentes patrones de interacción entre los dispositivos móviles y los objetos físicos, estos son las 6 de sus clasificaciones:

Presentación de información
Es la PMI (Physical Mobile Interaction) más simple el cual se utiliza un dispositivo móvil activo para leer información de alguna objeto, refiere a una característica homónima al contexto, dependiendo de este directamente, se puede decidir que hacer con dicha información, por ejemplo podemos encontrar aplicaciones como estas en museos o posters.

Ligas físicas
Se habla de ligas físicas cuando se tiene un objeto que contiene un acceso a algún otro servicio utilizando diferentes tecnologías, entre ellas, por ejemplo NFC, bluetooth, QR-code, etc.

Etiquetas
Sistemas que leen información de alguna etiqueta utilizada para escribir información del mundo real presentando información complementaria utilizando tecnologías como RFID o geo-tagging. (Fig 2.a) se puede ver una aplicación PMA en la cual se coloca información relevante en un objeto.


Broadcasting
Por la popularidad de etiquetas RFID y marcadores visuales, muchas PMA incluyen objetos pasivos y etiquetas para dar información de manera activa en los dispositivos móviles, usando objetos con tecnología explícita, el poner información cuando el usuario no la necesita, nos dice en el paper, que podría de cierta manera ofenderlos, por lo que en broadcasting se permite filtrar información por el usuario, básicamente podemos decir que este tipo de aplicaciones es consciente al contexto del usuario (Fig 2.b)

Tag emulation
Esta inspirada en el uso de la tecnología NFC el cual explícitamente permite a los dispositivos leer información de forma activa mediante un aparato diferente el cual emite de forma pasiva, estos son comúnmente utilizados por ejemplo en tarjetas inteligentes, como de identificación, de tickets, de registros, etc. Igualmente que las Ligas físicas, estos tienen una interacción PMI simple, por ejemplo cuando se interactua con una vending machine, puertas o alguna estación.

Interacción de 2 caminos.
Es cuando los dispositivos moviles adquieren información de objetos físicos en un paso de interacción simple, por citar el ejemplo del paper, es un proyecto llamado SMS el cual es un aparato para hacer check-in en un aeropuerto sin muchos pasos, simplemente mostrando tu celular al terminal.

Para realizar un estudio y diseño de prototipos del proyecto SMS, ellos utilizaron entre los diferentes campos, un video corto introduciendo los beneficios del proyecto, por lo que las personas realizaron una encuesta sobre que les parecía las ligas físicas, las etiquetas e interacción de dos caminos, en el cual tuvieron resultados entre 12 personas 6 mujeres y 6 hombres, entre 22 y 36 años que han utilizado celulares en aproximadamente 5,8 años.

Como conclusión, se hace un estudio demográfico entre las diferentes clasificaciones, teniendo como resultado que la mayoría de las personas (en la fecha de la publicación del paper), eran usuarios que prefieren lo tradicional para resolver sus dudas, por ejemplo ellos dicen que las personas votaron en el que es preferible pedir ayuda a una persona que usar tu celular, aunque yo creo que actualmente las personas están muy conectadas con sus aparatos móviles y que las personas prefieren tener el control de todo en ese tipo de aparatos, por lo que la combinación del cómputo ubicuo y la ingeniería de dispositivos móviles podemos tener sistemas inteligentes que ayuden a generar nuevos servicios, incluidos entre las dominos que se hablan en el paper.

Bibliografía.
Acceptance and Usability of Physical Mobile Applications, Tanja Herting. Liga.

Tarea 6: Detección de agujeros

Se nos pide para esta tarea que detectemos agujeros con un relleno morado y marcar el centro con un punto amarillo, agregar un ID a cada agujero.

Por lo que primero que nada pongo algunos ejemplos que corrí con mi programa, los resultados no son muy buenos en todos los casos, para detectar los puntos mínimos utilizo como referencia la función de MATLAB peakdet en python aquí.

Este es el código

	def boton_hoyos():
	#A grises
	imagen2 = cambiar_agrises(path_imagen_original)
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	umbral_valor = 0.2
	imagen = cambiar_umbral(imagen.convert("RGB"), umbral_valor)
	imagen.save("paso_2.jpg")
	pixeles_img = imagen.load()
	x, y = imagen.size
	pixeles = numpy.zeros(x*y).reshape((x, y))
	for a in range(x):
	for b in range(y):
	pixeles[a, b] = pixeles_img[a, b][0]
	col, fil = pixeles.shape
	suma_filas = []
	suma_col = []
	dibuja = ImageDraw.Draw(imagen2)
	for i in range(col):
	suma_col.append(pixeles[i].sum())
	for i in range(fil):
	suma_filas.append(pixeles[:, i].sum())
	maxcol, mincol, prueba_col = peakdet(suma_col, .1)
	maxfil, minfil, prueba_fil = peakdet(suma_filas, .1)
	coor_filas = []
	coor_col = []
	for i in range(len(suma_filas)):
	y = i
	PixMax = 255*col
	x = (((suma_filas[i]) * col) / PixMax)
	#print "(%s, %s)" %(str(x), str(y))
	#dibuja.ellipse((x-2, y-2, x+2, y+2), fill="blue")
	if i in prueba_fil:
	coor_filas.append(y)
	#dibuja.line((x, y, 0, y), fill="green")
	#dibuja.ellipse((x-4, y-4, x+4, y+4), fill="red")
	for i in range(len(suma_col)):
	x = i
	PixMax = 255*fil
	y = (((suma_col[i]) * fil) / PixMax)
	#print "(%s, %s)" %(str(x), str(y))
	#dibuja.ellipse((x-2, y-2, x+2, y+2), fill="green")
	if i in prueba_col:
	coor_col.append(x)
	#dibuja.line((x, y, x, 0), fill="red")
	#dibuja.ellipse((x-4, y-4, x+4, y+4), fill="red")
	if coor_col < coor_filas:
	tam = len(coor_filas)
	else:
	tam = len(coor_col)
	coor_filas = coor_filas[::-1]
	#coor_col = coor_col[::-1]
	centros = []
	imagen_copia = imagen
	for i in range(tam):
	x = coor_col[i]
	y = coor_filas[i]
	print "(%s, %s)" %(str(x), str(y))
	print pixeles[x, y]
	color = (randint(170,230), randint(0,190), 255)
	if pixeles[x, y] == 0.0:
	imagen_copia, masa, c = BFS(imagen_copia.convert("RGB"), (x, y), color)
	x_suma = 0
	y_suma = 0
	for i in range(len(masa)):
	x_suma = x_suma + masa[i][0]
	y_suma = y_suma + masa[i][1]
	x_centro = x_suma/len(masa)
	y_centro = y_suma/len(masa)
	centros.append((x_centro, y_centro))
	#dibuja.ellipse((x-1, y-1, x+1, y+1), fill="yellow")
	imagen_copia.save("paso_3.jpg")
	label.destroy()
	poner_imagen(imagen2)
	global frame
	y = frame.winfo_height()
	dibuja3 = ImageDraw.Draw(imagen_copia)
	for i in range(len(centros)):
	label_fig = Label(text = str(i))
	label_fig.place(x = centros[i][0], y = centros[i][1] + y)
	dibuja3.ellipse((centros[i][0]-2, centros[i][1]-2, centros[i][0]+2, centros[i][1]+2), fill="yellow")
	imagen_copia.save("paso_4.jpg")

view raw hoyos.py hosted with ❤ by GitHub

Extra points: Huffman coding

2. Table4.1 gives the relative frequencies,in English prose minus punctuation and blanks, ignoring capitalization, of the alphabetic characters a, b, . . . , z, estimated by examination of a large block of English prose, believed to be typical. This table is copied, with one small change, from [6, Appendix 1]. Find an optimal (with respect to average code word length) prefix-condition encoding scheme for S = {a, b, ... , z} if

(a) A={0,1};
(b) A={0,1,∗}.
(c) What are the lengths of the shortest fixed-length encoding schemes, resulting in uniquely decodable codes, for S, in cases (a) and (b), above?

For do this exercise I made a program that are pretty similar that my last homework where by doing the huffman tree we have the optimal prefix-condition, this is the code.

	class Hoja:
	def __init__(self, texto, prob, bit0=None, bit1=None):
	self.bit0 = bit0
	self.bit1 = bit1
	self.texto = texto
	self.prob = prob
	def mapa_codigos(arbol, alfa={}, lista=[]):
	if not arbol.bit1 and not arbol.bit0:
	alfa[arbol.texto] = "".join(lista)
	return
	lista.append("1")
	mapa_codigos(arbol.bit1, alfa, lista)
	lista.pop()
	lista.append("0")
	mapa_codigos(arbol.bit0, alfa, lista)
	lista.pop()
	def codificacion(cadena):
	mapeo = {}
	nodos = []
	alfa = [('e', 12.702, ''), ('t', 9.056, ''), ('a', 8.167, ''), ('o', 7.507, ''), ('i', 6.966, ''), ('n', 6.749, ''), ('s', 6.327, ''), ('h', 6.094, ''), ('r', 5.987, ''), ('d', 4.253, ''), ('l', 4.025, ''), ('c', 2.782, ''), ('u', 2.758, ''), ('m', 2.406, ''), ('w', 2.36, ''), ('f', 2.228, ''), ('g', 2.015, ''), ('y', 1.974, ''), ('p', 1.929, ''), ('b', 1.492, ''), ('v', 0.978, ''), ('k', 0.772, ''), ('j', 0.153, ''), ('x', 0.15, ''), ('q', 0.095, ''), ('z', 0.075, '')]
	for i in range(len(alfa)):
	hijo = Hoja(alfa[i][0], alfa[i][1])
	nodos.append((hijo.texto, hijo.prob, hijo))
	while (len(nodos) != 0):
	bit0 = nodos.pop(0)
	try:
	bit1 = nodos.pop(0)
	except IndexError:
	break
	texto_unido = str(bit0[0]) + str(bit1[0])
	suma = float(bit0[1]) + float(bit1[1])
	hoja = Hoja(texto_unido, suma, bit0[2], bit1[2])
	for i in range(len(nodos)):
	if nodos[i][1] > suma:
	index = i
	break
	nodos = nodos[:i] + [(hoja.texto, hoja.prob, hoja)] + nodos[i:]
	mapa_codigos(hoja, mapeo)
	print(mapeo)

view raw extra.py hosted with ❤ by GitHub

So we have like result for the question a:

• 'a': '0000', 
• 'c': '010001', 
• 'b': '0111000',
•  'e': '1', 
• 'd': '00011', 
• 'g': '0111011',
•  'f': '001101', 
• 'i': '01101', 
• 'h': '01010', 
• 'k': '00110011', 
• 'j': '0011001011',
•  'm': '001111', 
• 'l': '00010', 
• 'o': '01111',
• 'n': '01100', 
• 'q': '0011001001', 
• 'p': '0111001', 
• 's': '01011',
•  'r': '01001', 
• 'u': '010000', 
• 't': '0010', 
• 'w': '001110',
•  'v': '0011000', 
• 'y': '0111010', 
• 'x': '0011001010', 
• 'z': '0011001000'

Then I modified the code to have another node, so in the alphabet we have a new character and also a new coding data.

	class Hoja:
	def __init__(self, texto, prob, bit0=None, bit1=None, bit_=None):
	self.bit0 = bit0
	self.bit1 = bit1
	self.bit_ = bit_
	self.texto = texto
	self.prob = prob
	def mapa_codigos(arbol, alfa={}, lista=[]):
	if not arbol.bit1 and not arbol.bit0:
	alfa[arbol.texto] = "".join(lista)
	return
	lista.append("1")
	mapa_codigos(arbol.bit1, alfa, lista)
	lista.pop()
	lista.append("0")
	mapa_codigos(arbol.bit0, alfa, lista)
	lista.pop()
	lista.append("*")
	mapa_codigos(arbol.bit_, alfa, lista)
	lista.pop()
	def codificacion(cadena):
	#alfa = obtener_alfabeto(cadena)
	mapeo = {}
	nodos = []
	alfa = [('e', 12.702, ''), ('t', 9.056, ''), ('a', 8.167, ''), ('o', 7.507, ''), ('i', 6.966, ''), ('n', 6.749, ''), ('s', 6.327, ''), ('h', 6.094, ''), ('r', 5.987, ''), ('d', 4.253, ''), ('l', 4.025, ''), ('c', 2.782, ''), ('u', 2.758, ''), ('m', 2.406, ''), ('w', 2.36, ''), ('f', 2.228, ''), ('g', 2.015, ''), ('y', 1.974, ''), ('p', 1.929, ''), ('b', 1.492, ''), ('v', 0.978, ''), ('k', 0.772, ''), ('j', 0.153, ''), ('x', 0.15, ''), ('q', 0.095, ''), ('z', 0.075, '')]
	for i in range(len(alfa)):
	hijo = Hoja(alfa[i][0], alfa[i][1])
	nodos.append((hijo.texto, hijo.prob, hijo))
	while (len(nodos) != 0):
	try:
	bit0 = nodos.pop(0)
	print "bit0"
	except IndexError:
	break
	try:
	bit1 = nodos.pop(0)
	print "bit1"
	except IndexError:
	break
	try:
	bit_ = nodos.pop(0)
	print "bit_"
	except IndexError:
	break
	texto_unido = str(bit0[0]) + str(bit1[0]) + str(bit_[0])
	suma = float(bit0[1]) + float(bit1[1]) + float(bit_[1])
	hoja = Hoja(texto_unido, suma, bit0[2], bit1[2], bit_[2])
	for i in range(len(nodos)):
	if nodos[i][1] > suma:
	index = i
	break
	nodos = nodos[:i] + [(hoja.texto, hoja.prob, hoja)] + nodos[i:]
	mapa_codigos(hoja, mapeo)
	print(mapeo)
	return mapeo

view raw hoja.py hosted with ❤ by GitHub

• 'a': '11', 
• 'c': '*01',
•  'b': '*0**', 
• 'e': '1'
• 'd': '*11', 
• 'g': '*1**', 
• 'f': '0*0',
•  'i': '01', 
• 'h': '**1', 
• 'k': '*0*1*', 
• 'j': '*0*10', 
• 'm': '0**', 
• 'l': '*10',
•  'o': '10', 
• 'n': '00', 
• 'q': '*0*111', 
• 'p': '*1*0', 
• 's': '***', 
• 'r': '**0', 
• 'u': '*00', 
• 't': '1*', 
• 'w': '0*1', 
• 'v': '*0*0', 
• 'y': '*1*1', 
• 'x': '*0*11*', 
• 'z': '*0*110'

For the next question we have that e are the last in the list and only have a number 1 as a bit of codification and for the question b also have e with one bit, but in general we have a code more shorter in the second one than in the first one.

Lab: Relleno de elipses/círculos

Se nos pide que del código que detecte elipses y/o círculos

• Identificar cada elipse/círculo individual
• Rellénalo de un color aleatorio
• Sigue marcando su centro con bolita & ID con etiqueta
• Imprime un listado de los áreas de los círculos/elipses
• En porcentaje de la imagen completa

Por lo que para realizar esto, utilicé las mismas funciones que he estado reutilizando durante el curso, para identificar el elipse o círculo lo que se hace es verificar sus radios y comparar que si el radio calculado obtenido es igual para ambos lados (o sea, vertical y horizontal) quiere decir que tenemos un círculo, por el contrario tenemos un elipse.

Estos se rellenan con mi subrutina BFS con un color aleatorio, se marca una bolita en el centro y se identifican para proceder a obtener un listado de los que son círculos y elipses, al igual que su porcentaje en base a la figura completa.

Estas son las capturas del programa.

En donde podemos ver que el programa sabe satisfactoriamente si es un circulo o un elipse al igual que información en base a la imagen en general

A continuación expongo el código modificado.

	def BFS(imagen, inicio, color):
	#Busqueda de anchura para determinar una figura
	pixeles = imagen.load()
	altura, ancho = imagen.size
	fila, columna = inicio
	original = pixeles[fila, columna]
	cola = []
	cola.append((fila, columna))
	masa = []
	c = []
	while len(cola) > 0:
	(fila, columna) = cola.pop(0)
	actual = pixeles[fila, columna]
	if actual == original or actual == color:
	for dx in [-1, 0, 1]:
	for dy in [-1, 0, 1]:
	candidato = (fila + dy, columna + dx)
	if candidato[0] >= 0 and candidato[0] < altura and candidato[1] >= 0 and candidato[1] < ancho:
	contenido = pixeles[candidato[0], candidato[1]]
	if contenido == original:
	pixeles[candidato[0], candidato[1]] = color
	imagen.putpixel((candidato[0], candidato[1]), color)
	cola.append(candidato)
	masa.append((candidato[0], candidato[1]))
	c.append((candidato[0], candidato[1]))
	return imagen, masa, c
	def aplicar_BFS(imagen_BFS):
	#aplica busqueda de anchura a todas las figuras encontradas con color aleatorio
	pixeles = imagen_BFS.load()
	x, y = imagen_BFS.size
	colores = []
	elipses = []
	for a in range(x):
	for b in range(y):
	if pixeles[a, b] == (255, 255, 255):
	color = (random.randint(0,255), random.randint(0,255), random.randint(0, 255))
	imagen_BFS, masa, c = BFS(imagen_BFS.convert("RGB"), (a, b), color)
	elipses.append(c)
	x_suma = 0
	y_suma = 0
	for i in range(len(masa)):
	x_suma = x_suma + masa[i][0]
	y_suma = y_suma + masa[i][1]
	x_centro = x_suma/len(masa)
	y_centro = y_suma/len(masa)
	colores.append([color, 0, (x_centro, y_centro)])
	pixeles = imagen_BFS.load()
	masa = []
	#suma la cantidad de colores diferentes en la imagen
	pixeles = imagen_BFS.load()
	for a in range(x):
	for b in range(y):
	for n in range(len(colores)):
	if colores[n][0] == pixeles[a,b]:
	colores[n][1] = colores[n][1] + 1
	print colores
	suma = 0
	for i in range(len(colores)):
	suma = suma + colores[i][1]
	global frame
	y = frame.winfo_height()
	#Obtenemos porcentajes
	prom = []
	for i in range(len(colores)):
	promedio = float(colores[i][1])/float(suma)*100.0
	if promedio > 3.0:
	print "Porcentajes: "
	print "Figura " + str(i) + ": " + str(promedio)
	prom.append((i, promedio, colores[i][0]))
	maxim = 0.0
	for i in range(len(prom)):
	if maxim < prom[i][1]:
	maxim = prom[i][1]
	fig = prom[i][0]
	color_max = prom[i][2]
	#Itentificamos fondo y lo pintamos a gris
	print "Fondo fig: " + str(fig)
	imagen_BFS = pinta_fondo(imagen_BFS, color_max)
	#poner_imagen(imagen_BFS)
	return imagen_BFS, colores, elipses
	def pinta_fondo(imagen_BFS, color_max):
	#pintamos fondo de manera que obtenemos el color que predomina en la imagen
	pixeles = imagen_BFS.load()
	x, y = imagen_BFS.size
	for a in range(x):
	for b in range(y):
	if pixeles[a, b] == color_max:
	color = (100,100,100)
	imagen_BFS, masa, c = BFS(imagen_BFS.convert("RGB"), (a, b), color)
	return imagen_BFS
	def boton_elipse():
	inicio = time.time()
	label.destroy()
	max = 0
	suma = 0.0
	#A grises
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	votos = list()
	#A grises
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	#Agrego Laplaciana
	h_lap = numpy.array([[1, 1, 1], [1, -8, 1], [1, 1, 1]])
	imagen_prom, puntos = convolucion(imagen, numpy.multiply(1.0/1.0,h_lap))
	imagen_prom = cambiar_umbral(imagen_prom, 0.5)
	imagen_prom.save("paso_2.jpg")
	#Agrego normalizacion
	imagen_nor = normalizacion(imagen_prom)
	imagen_nor.save("paso_3.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.1
	imagen_bin = cambiar_umbral(imagen_nor.convert("RGB"), umbral_valor)
	imagen_bin.save("paso_4.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_bin.convert("RGB"))
	imagen_prom.save("paso_5.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.08
	imagen_bin2 = cambiar_umbral(imagen_prom.convert("RGB"), umbral_valor)
	imagen_bin2.save("paso_6.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_bin2.convert("RGB"))
	imagen_prom.save("paso_7.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_prom.convert("RGB"))
	imagen_prom.save("paso_8.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.5
	imagen_BFS = cambiar_umbral(imagen_prom.convert("RGB"), umbral_valor)
	imagen_BFS.save("paso_9.jpg")
	#Se aplica BFS
	imagen_BFS, colores, elipses = aplicar_BFS(imagen_BFS)
	imagen_BFS.save("paso_10.jpg")
	x, y = imagen_BFS.size
	pixeles = imagen_BFS.load()
	bordes_detectados = []
	#Se aplican mascaras de sobel
	h_Y = numpy.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
	h_X = numpy.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])
	imagen_hori, puntos_GX = convolucion(imagen, numpy.multiply(1.0/1.0,h_X))
	imagen_hori.save("paso_sobelX.jpg")
	pixeles_GX = imagen_hori.load()
	imagen_verti, puntos_GY = convolucion(imagen, numpy.multiply(1.0/1.0,h_Y))
	imagen_verti.save("paso_sobelY.jpg")
	pixeles_GY = imagen_verti.load()
	#Empezamos a detectar elipses y circulos
	dibuja = ImageDraw.Draw(imagen_BFS)
	x, y = imagen_BFS.size
	puntos = numpy.zeros(x*y).reshape((x, y))
	centros = []
	for elipse in elipses:
	x, y = imagen_BFS.size
	puntos = numpy.zeros(x*y).reshape((x, y))
	#Sacamos 2000 puntos aleatorios para calcular el centro mas preciso
	for i in range(2000):
	tam = len(elipse)
	punto_1 = elipse[randint(0,tam-1)]
	punto_2 = elipse[randint(0,tam-1)]
	x_1 = punto_1[0]
	y_1 = punto_1[1]
	x_2 = punto_2[0]
	y_2 = punto_2[1]
	gx_1 = puntos_GX[x_1, y_1]
	gy_1 = puntos_GY[x_1, y_1]
	gx_2 = puntos_GX[x_2, y_2]
	gy_2 = puntos_GY[x_2, y_2]
	gx_1 = - float(gx_1)
	gx_2 = - float(gx_2)
	x_22 = x_2
	y_22 = y_2
	x_11 = x_1
	y_11 = y_1
	if abs(gx_1) + abs(gy_1) <= 0:
	theta = None
	else:
	theta = atan2(gy_1, gx_1)
	l = 50
	if theta is not None:
	theta = theta-(pi/2)
	x_1 = x_11 - l * cos(theta)
	y_1 = y_11 - l * sin(theta)
	x_2 = x_11 + l * cos(theta)
	y_2 = y_11 + l * sin(theta)
	if abs(gx_2) + abs(gy_2) <= 0:
	theta = None
	else:
	theta = atan2(gy_2, gx_2)
	if theta is not None:
	theta = theta-(pi/2)
	x_3 = x_22 - l * cos(theta)
	y_3 = y_22 - l * sin(theta)
	x_4 = x_22 + l * cos(theta)
	y_4 = y_22 + l * sin(theta)
	y_medio = (y_11+y_22) / 2
	x_medio = (x_11+x_22) / 2
	pixeles = imagen_BFS.load()
	try:
	Px = ((x_1*y_2-y_1*x_2)*(x_3-x_4)-(x_1-x_2)*(x_3*y_4-y_3*x_4))/((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4))
	Py = ((x_1*y_2-y_1*x_2)*(y_3-y_4)-(y_1-y_2)*(x_3*y_4-y_3*x_4))/((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4))
	Dx = Px - x_medio
	Dy = Py - y_medio
	m = Dy/Dx
	x0 = x_medio
	y0 = y_medio
	#Obtenemos votos
	while True:
	x = x0+1
	y = m*(x-x0)+y0
	if pixeles[x,y] == (0, 0, 0):
	puntos[x, y] = puntos[x, y] + 1
	x0 = x
	y0 = y
	else:
	break
	except:
	pass
	max = numpy.max(puntos)
	index = numpy.where(puntos==max)
	try:
	mayor_x = sum(index[0])/len(index[0])
	mayor_y = sum(index[1])/len(index[0])
	#dibuja.ellipse((mayor_x-2, mayor_y-2, mayor_x+2, mayor_y+2), fill="blue")
	centros.append((mayor_x, mayor_y))
	except:
	mayor_x = index[0]
	mayor_y = index[1]
	#dibuja.ellipse((mayor_x-2, mayor_y-2, mayor_x+2, mayor_y+2), fill="blue")
	centros.append((mayor_x, mayor_y))
	#de los mayores detectados, los utilizamos como centros
	r_x = []
	r_y = []
	pixeles_imagen = imagen_BFS.load()
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	while True:
	y0 = y0 + 1
	if pixeles_imagen[x0, y0] != (0, 0, 0):
	r_y.append((x0, y0))
	break
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	while True:
	x0 = x0 + 1
	if pixeles_imagen[x0, y0] != (0, 0, 0):
	r_x.append((x0, y0))
	break
	Radios = []
	x, y = imagen_BFS.size
	print "Semidiametros perpendiculares del elipse"
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	x1 = int(r_x[i][0])
	y1 = int(r_x[i][1])
	x2 = int(r_y[i][0])
	y2 = int(r_y[i][1])
	Rx = sqrt((x1-x0)**2+(y1-y0)**2)
	Ry = sqrt((x2-x0)**2+(y2-y0)**2)
	#si los radios son iguales, es un circulo
	if Rx == Ry:
	cad = "Es circulo"
	else:
	cad = "Es elipse"
	porcentaje = float(Rx * 100)/float(x)
	print "ID: %s SemiDiametro: %s Porcentaje: %s %s" % (i, Rx, porcentaje, cad)
	#Radios.append((Rx, Ry))
	color = (255, 255, 255)
	a = 0
	#Pintamos en los 360 grados
	while a < 2*pi:
	x4, y4 = x0 + Rx * sin(a), y0 + Ry * cos(a)
	a = a + 0.01
	dibuja.ellipse((x4-2, y4-2, x4+2, y4+2), fill=color)
	for i in range(len(centros)):
	#Agregamos BFS empezando por el centro del circulo o elipse capturado
	color = (random.randint(0,255), random.randint(0,255), random.randint(0, 255))
	imagen_BFS, masa, c = BFS(imagen_BFS.convert("RGB"), (int(centros[i][0]), int(centros[i][1])), color)
	dibuja.ellipse((centros[i][0]-2, centros[i][1]-2, centros[i][0]+2, centros[i][1]+2), fill="blue")
	poner_imagen(imagen_BFS)
	global frame
	y = frame.winfo_height()
	for i in range(len(centros)):
	label_fig = Label(text = str(i))
	label_fig.place(x = centros[i][0], y = centros[i][1] + y)
	imagen_BFS.save("paso_lineas.jpg")
	#Tiempo
	fin = time.time()
	tiempo = fin - inicio
	print "Tiempo que trascurrio -> " + str(tiempo)
	return tiempo

view raw lab.py hosted with ❤ by GitHub

Lab: Localización interiores y exteriores

Para este laboratorio de cómputo ubicuo, se nos pide realizar una investigación sobre un proyecto de investigación de sistemas inteligentes que utilicen localización de interiores y exteriores de forma definida para cómputo ubicuo, es por eso que en este laboratorio voy a hablar acerca de un proyecto llamado DOLPHIN en donde se hace el desarrollo de un sistema completo de localización de objetos preciso en interiores pero reduciendo costos en sensores y nodos de redes que otros.

Como se sabe, sacar la ubicación de algún objeto en el interior de un espacio es una tarea difícil pero a la vez es clave para aplicaciones sensibles al contexto en cómputo ubicuo, actualmente existen diferentes sensores que ayudan a aproximar la ubicación de objetos pero estos algunas veces para poder desarrollarlos en un sistema completo requiere que se instalación complicada o una configuración que requiere ser completamente manual o para la localización de exteriores existen satélites como GPS que son buenos para eso, pero en interiores tenemos diferentes dificultades que debemos de tomar en cuenta, es por eso que se desarrollo un sistema llamado Dolphin, en el cual se pretende reducir el costo de configuración, principalmente.

El sistema dolphin es un sistema de redes inalámbricas distribuidos en sensores nodos que son capaces de enviar y recibir señales RF y ultrasónicas, proporcionando la posición de manera autónoma con una configuración manual mínima, en este paper lo que se pretende es describir el diseño de la implementación de este sistema y evaluar su comportamiento en diferentes ambientes.

La estructura de su sistema es de la siguiente forma, se tiene nodos que tienen transmisión y receptor de sensores RF y ultrasónicos, al igual que un CPU pequeño para hacer los cálculos de posición, las señales RF contienen una predeterminada posición, mientras tanto el nodo A transmite un pulso ultrasónico que permite medir la distancia del nodo, basado según la velocidad del sonido, el nodo recauda información de 3 o más entradas de distancia y hace un cómputo en 3D con un algoritmo parecido al que se utiliza para el GPS.

De manera que, si deseamos configurar el sistema Dolphin, basado en configuración hop-by-hop, hace que sea mucho más sencillo, por ejemplo en la imagen que ellos nos muestran, tenemos un nodo D que determina la posición recibiendo los pulsos ultrasónicos de los nodos referenciados, que en este caso es el A, C y B, pero como podemos ver, el E y el F no reciben pulsos ultrasónicos por que tienen un obstáculo, en este caso, la pared, entonces ¿Qué pasa en este caso?, bueno, como ya tenemos una posible posición para el nodo D, entonces el nodo E recibe un pulso ultrasónico y calcula a cuanta distancia se encuentra del nodo D, pero ahora también utilizando como referencia el C y B porque estos no los obstruye la pared, entonces si ya tenemos la posición D y E, entonces el nodo D utiliza los nodos E, D y posiblemente el C para determinar sus distancias, por lo que esta es la manera que el sistema trabaja, jugando con las posiciones de todos los nodos y de esta manera poder obtener la referencia de cada uno.

Existen ventajas al utilizar este mecanismo, primero que nada es que el sistema requiere solamente algunos nodos para determinar todas las posiciones de los nodos, mínimo se necesitan 3 nodos, otra de las ventajas es que inclusive si los nodos entre si no pueden recibir señales ultrasónicas, nos podemos utilizar como referencia de otros nodos directamente, de manera que tenemos un algoritmo distribuido.

El algoritmo utilizado en dolphin utiliza dos tipos de nodos, el que se utiliza como referencia y los nodos normales, los cuales ya tienen su localización, cada nodo tiene un ID para la comunicación RF, proporcionando una lista de nodos y su posible posición.

Se mandan entre los nodos, mensajes de intercambio, entre ellos un mensaje de notificación de ID, la medida el cual produce la distancia entre cada nodo y un mensaje de localización después de un procesamiento entre el nodo master, el nodo transmisor y el nodo que recibe información.

Un nodo master selecciona un nodo transmisor basado en la lista de nodos, trata de transmitir la medida de pulsos con cierto ID, cuando el nodo recibe dicho mensaje, une su ID con el transmitido para luego convertirse en un nodo transmisor y luego generar el pulso ultrasónico, al mismo tiempo todos los nodos comienzan a recibir e iniciar su contador interno, si un nodo que recibe detecta un pulso ultrasónico, este para de contar internamente y calcula la distancia entre el nodo y el nodo transmisor.

No todo es maravillas, después de su implementación y experimentos, realizaron un prototipo con unos pics y unos chips RF/ultrasónicos, pusieron algunos nodos e implementaron el programa, descubrieron que existe un error de propagación entre ciertos nodos, ya que si un nodo esta mal posicionado, afecta la determinación de todos los demás, por lo que ellos dicen que están trabajando en minimizar el error.

Como quiera, considero que su sistema es interesante y creo que puede ser un buen paso para iniciar un proyecto de cómputo ubicuo en el cual se requiera saber la posición de cada objeto, tal vez con alguna variación de su algoritmo utilizado podemos obtener resultados buenos para ciertas condiciones.

Esto sería todo para el laboratorio.

Referencias.

DOLPHIN: An Autonomous Indoor Positioning System in Ubiquitous Computing Environment 

Yasuhiro FUKUJU, Masateru MINAMI, Hiroyuki MORIKAWA, and Tomonori AOYAMA.
Liga.

Tarea 5: Detección de elipses

Para esta tarea se nos piden los siguientes puntos:

• Detectar elipses marcados con tonos naranja.
• Marcar el centro con un punto azul
• Poner una etiqueta ID 
• Imprimir un listado de los semidiametros perpendiculares y su porcentaje con la diagonal máxima de la imagen

Para realizar esto, se nos pide utilizar el método de la cuerda tangente, es por eso que se hacen los siguientes pasos:

1. Cambiar a grises
2. Sacar convolución Laplaciana para sacar bordes
3. Normalizo la imagen
4. Binarizo los datos
5. Sacamos el promedio
6. Se agrega un umbral
7. Agregamos BFS para detectar todos los bordes 
8. Los pintamos de diferentes colores
9. Sacamos mascara de sobel en X
10. Sacamos mascara de sobel en Y
11. Generamos puntos aleatorios para cada borde detectado
12. Calculamos su theta 
13. Creamos dos lineas tangenciales a los bordes
14. Se calcula su punto medio
15. Realizamos los votos a partir de esa linea hasta al final del borde siguiente
16. Repetimos varias veces para obtener mejor precisión en el centro
17. Se calcula los radios en X y en Y
18. dibujamos un punto entre 0 a 360 grados a partir de los datos obtenidos
19. Vemos el elipse detectado en un tono anaranjado

Les muestro unas capturas de pantalla del procedimiento

Otros ejemplos:

Este es el código de la función principal, si quieren ver mi repositorio, ahí se encuentra completo.

	def boton_elipse():
	inicio = time.time()
	label.destroy()
	max = 0
	suma = 0.0
	#A grises
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	votos = list()
	#A grises
	imagen = cambiar_agrises(path_imagen_original)
	imagen.save("paso_1.jpg")
	#Agrego Laplaciana
	h_lap = numpy.array([[1, 1, 1], [1, -8, 1], [1, 1, 1]])
	imagen_prom, puntos = convolucion(imagen, numpy.multiply(1.0/1.0,h_lap))
	imagen_prom = cambiar_umbral(imagen_prom, 0.5)
	imagen_prom.save("paso_2.jpg")
	#Agrego normalizacion
	imagen_nor = normalizacion(imagen_prom)
	imagen_nor.save("paso_3.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.1
	imagen_bin = cambiar_umbral(imagen_nor.convert("RGB"), umbral_valor)
	imagen_bin.save("paso_4.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_bin.convert("RGB"))
	imagen_prom.save("paso_5.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.08
	imagen_bin2 = cambiar_umbral(imagen_prom.convert("RGB"), umbral_valor)
	imagen_bin2.save("paso_6.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_bin2.convert("RGB"))
	imagen_prom.save("paso_7.jpg")
	#Pongo promedio
	imagen_prom = cambiar_promedio(imagen_prom.convert("RGB"))
	imagen_prom.save("paso_8.jpg")
	#Agrego umbral para binarizar
	umbral_valor = 0.5
	imagen_BFS = cambiar_umbral(imagen_prom.convert("RGB"), umbral_valor)
	imagen_BFS.save("paso_9.jpg")
	#Aplica BFS a los bordes detectados
	imagen_BFS, colores, elipses = aplicar_BFS(imagen_BFS)
	imagen_BFS.save("paso_10.jpg")
	x, y = imagen_BFS.size
	pixeles = imagen_BFS.load()
	bordes_detectados = []
	#Se aplica mascara sobel en X y Y
	h_Y = numpy.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
	h_X = numpy.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])
	imagen_hori, puntos_GX = convolucion(imagen, numpy.multiply(1.0/1.0,h_X))
	imagen_hori.save("paso_sobelX.jpg")
	pixeles_GX = imagen_hori.load()
	imagen_verti, puntos_GY = convolucion(imagen, numpy.multiply(1.0/1.0,h_Y))
	imagen_verti.save("paso_sobelY.jpg")
	pixeles_GY = imagen_verti.load()
	#Empezamos a detectar los elipses
	dibuja = ImageDraw.Draw(imagen_BFS)
	x, y = imagen_BFS.size
	puntos = numpy.zeros(x*y).reshape((x, y))
	centros = []
	#Para cada borde detectado sacamos puntos aleatorios para hacer votos en la linea donde posiblemente tenemos un centro
	for elipse in elipses:
	x, y = imagen_BFS.size
	puntos = numpy.zeros(x*y).reshape((x, y))
	for i in range(2000):
	tam = len(elipse)
	punto_1 = elipse[randint(0,tam-1)]
	punto_2 = elipse[randint(0,tam-1)]
	x_1 = punto_1[0]
	y_1 = punto_1[1]
	x_2 = punto_2[0]
	y_2 = punto_2[1]
	gx_1 = puntos_GX[x_1, y_1]
	gy_1 = puntos_GY[x_1, y_1]
	gx_2 = puntos_GX[x_2, y_2]
	gy_2 = puntos_GY[x_2, y_2]
	gx_1 = - float(gx_1)
	gx_2 = - float(gx_2)
	x_22 = x_2
	y_22 = y_2
	x_11 = x_1
	y_11 = y_1
	#Calculamos theta segun mascara de sobel
	if abs(gx_1) + abs(gy_1) <= 0:
	theta = None
	else:
	theta = atan2(gy_1, gx_1)
	l = 50
	#Creamos las lineas tangentes
	if theta is not None:
	theta = theta-(pi/2)
	x_1 = x_11 - l * cos(theta)
	y_1 = y_11 - l * sin(theta)
	x_2 = x_11 + l * cos(theta)
	y_2 = y_11 + l * sin(theta)
	#Misma operacion con otro punto
	if abs(gx_2) + abs(gy_2) <= 0:
	theta = None
	else:
	theta = atan2(gy_2, gx_2)
	if theta is not None:
	theta = theta-(pi/2)
	x_3 = x_22 - l * cos(theta)
	y_3 = y_22 - l * sin(theta)
	x_4 = x_22 + l * cos(theta)
	y_4 = y_22 + l * sin(theta)
	y_medio = (y_11+y_22) / 2
	x_medio = (x_11+x_22) / 2
	pixeles = imagen_BFS.load()
	try:
	#Detectamos la interseccion y pendiente
	Px = ((x_1*y_2-y_1*x_2)*(x_3-x_4)-(x_1-x_2)*(x_3*y_4-y_3*x_4))/((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4))
	Py = ((x_1*y_2-y_1*x_2)*(y_3-y_4)-(y_1-y_2)*(x_3*y_4-y_3*x_4))/((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4))
	Dx = Px - x_medio
	Dy = Py - y_medio
	m = Dy/Dx
	x0 = x_medio
	y0 = y_medio
	#Empezamos a hacer votos hasta encontrar un borde
	while True:
	x = x0+1
	y = m*(x-x0)+y0
	if pixeles[x,y] == (0, 0, 0):
	puntos[x, y] = puntos[x, y] + 1
	x0 = x
	y0 = y
	else:
	break
	except:
	pass
	#De los resultados sacamos los mas voteados
	max = numpy.max(puntos)
	index = numpy.where(puntos==max)
	try:
	mayor_x = sum(index[0])/len(index[0])
	mayor_y = sum(index[1])/len(index[0])
	#dibuja.ellipse((mayor_x-2, mayor_y-2, mayor_x+2, mayor_y+2), fill="blue")
	centros.append((mayor_x, mayor_y))
	except:
	mayor_x = index[0]
	mayor_y = index[1]
	#dibuja.ellipse((mayor_x-2, mayor_y-2, mayor_x+2, mayor_y+2), fill="blue")
	centros.append((mayor_x, mayor_y))
	#Sacamos los radios
	r_x = []
	r_y = []
	pixeles_imagen = imagen_BFS.load()
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	while True:
	y0 = y0 + 1
	if pixeles_imagen[x0, y0] != (0, 0, 0):
	r_y.append((x0, y0))
	break
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	while True:
	x0 = x0 + 1
	if pixeles_imagen[x0, y0] != (0, 0, 0):
	r_x.append((x0, y0))
	break
	#Dibujamos elipse
	x, y = imagen_BFS.size
	print "Semidiametros perpendiculares del elipse"
	for i in range(len(centros)):
	x0 = int(centros[i][0])
	y0 = int(centros[i][1])
	x1 = int(r_x[i][0])
	y1 = int(r_x[i][1])
	x2 = int(r_y[i][0])
	y2 = int(r_y[i][1])
	Rx = sqrt((x1-x0)**2+(y1-y0)**2)
	Ry = sqrt((x2-x0)**2+(y2-y0)**2)
	porcentaje = float(Rx * 100)/float(x)
	print "ID: %s SemiDiametro: %s Porcentaje: %s" % (i, Rx, porcentaje)
	color = (randint(175,255), randint(134, 196), 0) #rango anaranjado
	a = 0
	while a < 2*pi:
	x4, y4 = x0 + Rx * sin(a), y0 + Ry * cos(a)
	a = a + 0.01
	dibuja.ellipse((x4-2, y4-2, x4+2, y4+2), fill=color)
	#Ponemos imagen en ventana
	poner_imagen(imagen_BFS)
	#Etiquetamos
	global frame
	y = frame.winfo_height()
	for i in range(len(centros)):
	label_fig = Label(text = str(i))
	label_fig.place(x = centros[i][0], y = centros[i][1] + y)
	dibuja.ellipse((centros[i][0]-2, centros[i][1]-2, centros[i][0]+2, centros[i][1]+2), fill="blue")
	#Guardamos
	imagen_BFS.save("paso_lineas.jpg")
	#Tiempo
	fin = time.time()
	tiempo = fin - inicio
	print "Tiempo que trascurrio -> " + str(tiempo)
	return tiempo

view raw python.py hosted with ❤ by GitHub

Huffman coding

For this week we need to implement the tree-based Huffman coding for Unicode strings, implementing the tree structure, then we need to do a report with a design of an experiment to determine the worst-case and typical-case complexity and compression ratio.

Determining the worst-case and typical-case

As we know, fibonacci sequence are the sum of the previous two, knowing at first that Fo = 0 and F1 = 1, this sequence produces a tree that are the most unbalanced, because if we know that huffman are base in the last two frequencies which produce another node that are the sum of both, so, if we have a fibonacci sequence as a frequency of the letters that we would like to test, we can have this type of tree.

For example, let say that we have these case, when we have only 7 letter, just for know how works.


1, 1, 2, 3
a, b, cc, ddd


Alphabet and probability:
a : 0.142857 = 1/7
b : 0.142857 = 1/7
c : 0.285714 = 2/7
d : 0.428571 = 3/7

Tree:

                  [1] d
[] cabd
                                 [1] b
                      [1] ab
                                 [0] a
           [0] cab
                      [0] c

The same:

              cabd

             /        \
           d        cab
                     /    \
                    c   ab
                        /  \   
                        a  b

We can see that the tree have only new nodes just for one side, because we made the tree having the sum of the probabilities of frequency, and have a pattern that builds the tree in that way, also we can say that if the have in all the probabilities the same number, would have the same pattern.

A typical case is when we have a frequencies that are not the same for all the text or that don't have the pattern of fibonacci, so I made an experiment for the type that I think is interesting, I made a different graphics that can shows that these type of cases are bad compare to the average case.

We have in this graphic the sum of bits that need to handle with a entire alphabet, using ascii, without compress the bits in the line yellow, the average using huffman compression and then using fibonacci sequence frequency and compression with huffman, with a sample of 35 strings with different size.

In this graphic, we can see the compress ratio between the average-case and the worst-case, we can see that clearly are much difference between them, having a difference about 62% more compress than the strings that have a fibonacci sequence.

Program

	import collections
	import string
	import random
	import time
	class Hoja:
	def __init__(self, texto, prob, bit0=None, bit1=None):
	self.bit0 = bit0
	self.bit1 = bit1
	self.texto = texto
	self.prob = prob
	def genera_str(tam):
	return ''.join(random.choice(string.ascii_letters) for x in range(tam))
	def genera_str_alfa(tam, str):
	return ''.join(random.choice(str) for x in range(tam))
	def mostrar(arbol, nivel, bit=""):
	if arbol == None: return
	mostrar(arbol.bit1, nivel + 1, 1)
	print(" " * nivel + "[" + str(bit) + "] " + str(arbol.texto))
	mostrar(arbol.bit0, nivel + 1, 0)
	def obtener_alfabeto(cadena):
	dic = collections.defaultdict(int)
	for letra in cadena:
	dic[letra] += 1
	alfa = []
	total = len(cadena)
	#print ("Alfabeto & prob:")
	#print cadena
	cod = ""
	for letra in sorted(dic, key = dic.get):
	prob = float(dic[letra])/float(total)
	#print("%s : %f" % (letra, dic[letra]))
	alfa.append((letra, prob, cod))
	#time.sleep(3)
	return alfa
	def mapa_codigos(arbol, alfa={}, lista=[]):
	if not arbol.bit1 and not arbol.bit0:
	alfa[arbol.texto] = "".join(lista)
	return
	lista.append("1")
	mapa_codigos(arbol.bit1, alfa, lista)
	lista.pop()
	lista.append("0")
	mapa_codigos(arbol.bit0, alfa, lista)
	lista.pop()
	def codificacion(cadena):
	alfa = obtener_alfabeto(cadena)
	mapeo = {}
	nodos = []
	for i in range(len(alfa)):
	hijo = Hoja(alfa[i][0], alfa[i][1])
	nodos.append((hijo.texto, hijo.prob, hijo))
	while (len(nodos) != 0):
	bit0 = nodos.pop(0)
	try:
	bit1 = nodos.pop(0)
	except IndexError:
	break
	texto_unido = str(bit0[0]) + str(bit1[0])
	suma = float(bit0[1]) + float(bit1[1])
	hoja = Hoja(texto_unido, suma, bit0[2], bit1[2])
	for i in range(len(nodos)):
	if nodos[i][1] > suma:
	index = i
	break
	nodos = nodos[:i] + [(hoja.texto, hoja.prob, hoja)] + nodos[i:]
	#print("Arbol: ")
	#mostrar(hoja, 0)
	mapa_codigos(hoja, mapeo)
	#print("Mapeo:")
	#print(mapeo)
	return mapeo
	#codificacion(string.printable)
	def experimento_1(veces):
	print "datos random bits_ran prob bits_prob"
	x = 0
	for i in range(0, veces, 100000):
	if i != 0 and x < 10:
	str = (string.ascii_uppercase)*i
	inicio = time.time()
	mapa_1 = codificacion(str)
	fin = time.time()
	tiempo_prob = fin - inicio
	inv_mapa_1 = {v:k for k, v in mapa_1.items()}
	mayor_1 = len(max(inv_mapa_1, key=len))
	str_ran = genera_str(len(str))
	inicio = time.time()
	mapa_2 = codificacion(str_ran)
	fin = time.time()
	tiempo_ran = fin - inicio
	inv_mapa_2 = {v:k for k, v in mapa_2.items()}
	mayor_2 = len(max(inv_mapa_2, key=len))
	print "%s %s %s %s %s" % (len(str), tiempo_ran, mayor_2, tiempo_prob, mayor_1)
	x = x + 1
	def experimento_2():
	x = 0
	str = string.ascii_letters
	str_fibo = "a"
	b = 0
	c = 1
	#print "tam long tiempo_ran mayor_ran suma_ran compress_ran tiempo_fibo mayor_fibo suma_fibo compress_fibo"
	for i in range(len(str)):
	a = b + c
	c = b
	b = a
	if x != 0:
	str_fibo = str_fibo + str[x]*a
	#mixta = "".join(random.sample(str_fibo, len(str_fibo)))
	inicio = time.time()
	#print "Fibo:"
	mapa_1 = codificacion(str_fibo)
	fin = time.time()
	tiempo = fin - inicio
	inv_mapa_1 = {v:k for k, v in mapa_1.items()}
	mayor_1 = len(max(inv_mapa_1, key=len))
	suma_1 = sum(len(x) for x in inv_mapa_1)
	longitud = len(inv_mapa_1)*7
	alfa = str[:x+1]
	#print "Random:"
	str_ran = genera_str_alfa(len(str_fibo), alfa)
	inicio = time.time()
	mapa_2 = codificacion(str_ran)
	fin = time.time()
	tiempo_ran = fin - inicio
	inv_mapa_2 = {v:k for k, v in mapa_2.items()}
	mayor_2 = len(max(inv_mapa_2, key=len))
	suma_2 = sum(len(x) for x in inv_mapa_2)
	compress_bit_ran = float(suma_2)/float(longitud)
	compress_bit_fibo = float(suma_1)/float(longitud)
	print "%s %s %s %s %s %s %s %s %s %s" % (len(str_ran), longitud, tiempo_ran, mayor_2, suma_2, compress_bit_ran, tiempo, mayor_1, suma_1, compress_bit_fibo)
	x = x + 1
	experimento_2()

view raw arbol.py hosted with ❤ by GitHub

Presentación proyecto

Lab: Sugerencias de hardware and software

Para el laboratorio de la materia de Cómputo Ubicuo se nos pide realizar sugerencias a los equipos que presentaron la clase pasada sobre el hardware y software que ellos definieron para el desarrollo de sus proyectos, por lo que leyendo acerca de sus proyectos voy a resumir brevemente que es lo que yo considero que deberían tomar encuentra.

Seguridad en computadora.

Para su proyecto, creo que están bien el hardware que quieren utilizar, yo pudiera sugerirles que para agregar más seguridad pueden utilizar algún tipo de sensor como este [tienda] en donde puedes saber si existe luz o no, para de esta manera saber si la persona está utilizando la computadora o no y saber cuando debe estar detectando a la persona la cámara y no tenga que interactuar con ella en la computadora justo al picar botones, si no que este capturando imágenes necesarias para al momento que la persona este enfrente de ella, esta se pueda desbloquear.


Carro con NFC.

Si van a utilizar python, pueden utilizar la librería pynfc, según encontré en internet tiene buena integración con raspberry pi y pueden utilizar python, lo cual hace que su código sea mas simple y no esten batallando tanto en ese aspecto, aquí pueden encontrar la liga a la librería [liga]


Galería inteligente.

Para la lectura de la descripción de las obras pueden utilizar el wave shield de arduino [tienda] que te da la posibilidad de con una tarjeta de memoria SD tener conectados bocinas y poder transmitir sonido de alta calidad desde el arduino sin necesidad de conectarlo a una computadora, aquí les dejo un ejemplo.



Oficina inteligente.

Cómo vi que van a utilizar sensores RFID y ustedes están planteando el utilizar pulseras, pudieran utilizar también etiquetas que estén en metal de manera que se agreguen por ejemplo a un carro y que cuando entre por la cochera de la oficina o estacionamiento, pueda tener desde ahí el acceso a la oficina de forma controlada.

Aquí les dejo la liga de la etiqueta metálica [tienda].

Alarma de automóvil

En su presentación que tienen en su blog ponen que van a necesitar sensores, pero no especifican exactamente que tipo de sensores van a utilizar, entonces aquí les pongo algunos que considero útiles, junto con sus ligas a la tienda 5hz.

Sensor de sonido [tienda]:
Un sensor de sonido les pudiera servir para cuando se escuche algún ruido dentro de la casa cuando el coche no se encuentra en la cochera, mandar una notificación de que existe un ruido extraño en casa.

Etiqueta RFID para metal [tienda]:
Esta pudiera ir en el carro para de alguna manera por medio de un sistema que hicieran pudieran detectar que el carro se encuentra en la cochera y avisar a la casa que se encuentra el habitante en ella.

Localización de cosas por bluetooth

Como veo que van a utilizar librerías para reconocimiento de voz, existe una librería muy completa que a mi me gusta, se llama Dragonfly, es un framework para python que es muy bueno y les resultaría de mucha ayuda para lo que están desarrollando, lo que tienen de hardware considero que está muy bien para su proyecto, pueden encontrar la liga del framework aquí [liga]

Casa segura.

Para este proyecto pueden utilizar este switch miniatura de contacto magnético, simplemente se instala en la puerta y lo conectas al arduino, por lo que ahora puedes saber cuando se abre o se cierra la puerta y de esta manera tener el control de dicha puerta o ventana, en internet viene mucha información de como lo puedes utilizar, por ejemplo puedes usar un xbee para crear una alarma inalámbrica como viene en los ejemplos.

Aquí puedes encontrar ese switch [tienda]

Garage inteligente.

Tal vez no para el prototipo final pero si para una versión de prueba pueden utilizar una toolkit que nosotros utilizamos para hacer el proyecto de cómputo integrado, el amarino, se utiliza para conectar mediante bluetooth el arduino y el android de esta manera pueden hacer pruebas sencillas para saber si su smartphone esta pasando información a su arduino y realizar algunas mejoras para el prototipo final.

Esto sería todo para el laboratorio de cómputo ubicuo, si tienen alguna duda o comentario, favor de hacérmelo saber.

Lab: generación de topologías y modos de rateo

Para esta semana de laboratorio se nos pide averiguar cómo se habilitan distintos modos de ruteo en ns-2, al igual que inventar e implementar mecanismos de generación de topologías que imiten alguna infraestructura de redes del mundo real en específico.

Modos de ruteo

Los distintos modos de ruteo que podemos modelar en NS2 se encuentran disponibles códigos ejemplos de como implementar una prueba de ruteo según el código que estes realizando en las clases de prueba de NS-2.35 versión en la cual he estado trabajando, estos son los que yo encontré en la carpeta ns-allinone-2.35/ns-2.35/tcl/test:

• Ruteo algoritmico:
• Lo puedes encontrar en el archivo test-suite-algo-routing.tcl
• Ruteo jerárquico:
• Lo puedes encontrar en el archivo test-suite-hier-routing.tcl
• Ruteo de LAN y broadcast:
• Lo puedes encontrar en el archivo test-suite-lan.tcl
• Ruteo manual:
• Lo puedes encontrar en el archivo test-suite-manual-routing.tcl
• Ruteo centralizado multicast:
• Lo puedes encontrar en el archivo test-suite-mcast.tcl
• Ruteo dinamico:
• Lo puedes encontrar en el archivo test-suite-routed.tcl
• Clasificador virtual de ruteo:
• Lo puedes encontrar en el archivo test -suite-vc

Al igual que podemos encontrar mecanismos que nos sirven para hacer scheduling, manejar colas, admisiones de control, etc, entre los cuales encontré:

• Algoritmos de scheduling como:
• FQ (Fair Queueing)
• SFQ (Stochastic Fair Queuing)
• DRR (Deficit Round Robin)
• FIFO
• Estos se encuentran en el archivo test-suite-schedule.tcl
• Control de admisión:
• MS, HB, ACTP, ACTO
• Estos se encuentran en el archivo test-suite-intserv.tcl

Generador de Topologías

Por el lado de implementación de un generador de topologías realicé un programa en TCL en el cual pones como parámetro la topología que deseas realizarle un experimento y realiza una simulación de envio de datos con TCP y FTP.

Las topologías implementadas son:

• Arbol
• Estrella
• Anillo
• Mixto
• Lineal

Entonces, cuando ejecutamos la simulación, ponemos la topología la cual queremos experimentar.

ns simulacion.tcl arbol

A continuación les presento el código que hice.

	set sim [new Simulator]
	set archivo_1 [open salida_1.nam w]
	$sim namtrace-all $archivo_1
	proc termina_1 {} {
	global sim archivo_1
	$sim flush-trace
	close $archivo_1
	exec nam salida_1.nam &
	exit 0
	}
	#Nodos suficientes para topologia
	set padre [$sim node]
	set hijo1 [$sim node]
	set hijo2 [$sim node]
	set hijo3 [$sim node]
	set ter1 [$sim node]
	set ter2 [$sim node]
	set ter3 [$sim node]
	set ter4 [$sim node]
	set ter5 [$sim node]
	#conexiones para topologia arbol
	proc conecta_arbol {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo3 2Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo2 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo1 $hijo3 15
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $hijo3 $ter2 10
	$sim queue-limit $hijo3 $ter3 10
	$sim queue-limit $hijo2 $ter4 10
	$sim queue-limit $ter3 $ter5 10
	$sim duplex-link-op $padre $hijo1 orient down
	$sim duplex-link-op $hijo1 $hijo2 orient down-right
	$sim duplex-link-op $hijo1 $hijo3 orient down-left
	$sim duplex-link-op $hijo3 $ter1 orient down-left
	$sim duplex-link-op $hijo3 $ter2 orient down-right
	$sim duplex-link-op $hijo3 $ter3 orient down
	$sim duplex-link-op $ter3 $ter5 orient down
	$sim duplex-link-op $hijo2 $ter4 orient down-right
	}
	#conexiones para topologia estrella
	proc conecta_estrella {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $padre $hijo2 2Mb 10ms DropTail
	$sim duplex-link $padre $hijo3 2Mb 10ms DropTail
	$sim duplex-link $padre $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $padre $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $padre $hijo2 15
	$sim queue-limit $padre $hijo3 15
	$sim queue-limit $padre $ter1 10
	$sim queue-limit $padre $ter2 10
	$sim queue-limit $padre $ter3 10
	$sim queue-limit $padre $ter4 10
	$sim queue-limit $padre $ter5 10
	$sim duplex-link-op $padre $hijo1 orient down
	$sim duplex-link-op $padre $hijo2 orient down-right
	$sim duplex-link-op $padre $hijo3 orient down-left
	$sim duplex-link-op $padre $ter1 orient up-left
	$sim duplex-link-op $padre $ter2 orient up-right
	$sim duplex-link-op $padre $ter3 orient up
	$sim duplex-link-op $padre $ter5 orient right
	$sim duplex-link-op $padre $ter4 orient left
	}
	#conexiones para topologia anillo
	proc conecta_anillo {} {
	global sim padre ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim duplex-link $ter5 $padre 1.5Mb 10ms DropTail
	$sim queue-limit $padre $ter1 10
	$sim queue-limit $ter1 $ter2 10
	$sim queue-limit $ter2 $ter3 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter5 10
	$sim queue-limit $ter5 $padre 10
	$sim duplex-link-op $padre $ter1 orient down-right
	$sim duplex-link-op $ter1 $ter2 orient down
	$sim duplex-link-op $ter2 $ter3 orient down-left
	$sim duplex-link-op $ter3 $ter4 orient up-left
	$sim duplex-link-op $ter4 $ter5 orient up
	$sim duplex-link-op $ter5 $padre orient up-right
	}
	#conexiones para topologia mixta
	proc conecta_mixto {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $padre $hijo2 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo1 $ter1 2Mb 10ms DropTail
	$sim duplex-link $hijo2 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $hijo3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim duplex-link $ter5 $ter2 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $padre $hijo2 15
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo2 $ter2 10
	$sim queue-limit $ter2 $ter1 10
	$sim queue-limit $ter1 $hijo3 10
	$sim queue-limit $hijo3 $ter3 10
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter1 10
	$sim queue-limit $ter4 $ter5 10
	$sim queue-limit $ter5 $ter2 10
	$sim duplex-link-op $padre $hijo1 queuePos 0.5
	$sim duplex-link-op $padre $hijo2 queuePos 0.5
	$sim duplex-link-op $hijo1 $hijo2 queuePos 0.5
	$sim duplex-link-op $hijo2 $ter2 queuePos 0.5
	$sim duplex-link-op $ter2 $ter1 queuePos 0.5
	$sim duplex-link-op $ter1 $hijo3 queuePos 0.5
	$sim duplex-link-op $hijo3 $ter3 queuePos 0.5
	$sim duplex-link-op $hijo3 $ter1 queuePos 0.5
	$sim duplex-link-op $ter3 $ter4 queuePos 0.5
	$sim duplex-link-op $ter4 $ter1 queuePos 0.5
	$sim duplex-link-op $ter4 $ter5 queuePos 0.5
	$sim duplex-link-op $ter5 $ter2 queuePos 0.5
	}
	#conexiones para topologia lineal
	proc conecta_lineal {} {
	global sim padre hijo1 hijo2 hijo3 ter1 ter2 ter3 ter4 ter5
	$sim duplex-link $padre $hijo1 2.5Mb 10ms DropTail
	$sim duplex-link $hijo1 $hijo2 2Mb 10ms DropTail
	$sim duplex-link $hijo2 $hijo3 2Mb 10ms DropTail
	$sim duplex-link $hijo3 $ter1 1.5Mb 10ms DropTail
	$sim duplex-link $ter1 $ter2 1.5Mb 10ms DropTail
	$sim duplex-link $ter2 $ter3 1.5Mb 10ms DropTail
	$sim duplex-link $ter3 $ter4 1.5Mb 10ms DropTail
	$sim duplex-link $ter4 $ter5 1.5Mb 10ms DropTail
	$sim queue-limit $padre $hijo1 25
	$sim queue-limit $hijo1 $hijo2 15
	$sim queue-limit $hijo2 $hijo3 15
	$sim queue-limit $hijo3 $ter1 10
	$sim queue-limit $ter1 $ter2 10
	$sim queue-limit $ter2 $ter3 10
	$sim queue-limit $ter3 $ter4 10
	$sim queue-limit $ter4 $ter5 10
	$sim duplex-link-op $padre $hijo1 orient left
	$sim duplex-link-op $hijo1 $hijo2 orient left
	$sim duplex-link-op $hijo2 $hijo3 orient left
	$sim duplex-link-op $hijo3 $ter1 orient left
	$sim duplex-link-op $ter1 $ter2 orient left
	$sim duplex-link-op $ter2 $ter3 orient left
	$sim duplex-link-op $ter3 $ter4 orient left
	$sim duplex-link-op $ter4 $ter5 orient left
	}
	proc llamada args {
	foreach arg $args {
	puts "Comando de entrada: $args"
	if {$args == "estrella"} {
	conecta_estrella
	} elseif {$args == "arbol"} {
	conecta_arbol
	} elseif {$args == "anillo"} {
	conecta_anillo
	} elseif {$args == "mixto"} {
	conecta_mixto
	} elseif {$args == "lineal"} {
	conecta_lineal
	} else {
	puts "Selecciona un comando, prueba arbol"
	conecta_arbol
	}
	}
	}
	llamada $argv
	global sim padre ter4 ter5
	set tcp [new Agent/TCP]
	$sim attach-agent $padre $tcp
	set sink [new Agent/TCPSink]
	$sim attach-agent $ter4 $sink
	$sim connect $tcp $sink
	set tcp2 [new Agent/TCP]
	$sim attach-agent $padre $tcp2
	set sink2 [new Agent/TCPSink]
	$sim attach-agent $ter5 $sink2
	$sim connect $tcp2 $sink2
	set ftp [new Application/FTP]
	$ftp attach-agent $tcp
	set ftp2 [new Application/FTP]
	$ftp2 attach-agent $tcp2
	$sim at 0.01 "$ftp start"
	$sim at 0.5 "$ftp stop"
	$sim at 0.51 "$ftp2 start"
	$sim at 1.0 "$ftp2 stop"
	$sim at 1.0 "termina_1"
	$sim run

view raw simulacion.tcl hosted with ❤ by GitHub

Estas son algunas capturas de pantalla del código funcionando.

Para finalizar les muestro un video de la simulación de la topología de árbol.

Esto sería todo para la actividad de laboratorio.