Max Hernandez

Laberinto - Ejemplo de Canvas en HTML5

martes, 30 de abril de 2013

Laboratorio 9: Ahorro de energía

Para esta semana se nos dio a la tarea de buscar un texto científico relacionado con ahorro de energía en redes esta publicación servirá de reporte para dicha tarea y el documento que seleccione fue el siguiente:

Reducing Network Energy Consumption via Sleeping and Rate-Adaptation
Sergiu Nedevschi, Lucian Popa, Gianluca Iannaccone, Sylvia Ratnasamy, David Wetherall


El texto se centra en dos formas para reducir el uso de energía en redes, el primero esta basado en poner a dormir componentes de la red cuando estos estén inactivos, el segundo esta basado en adaptar el ritmo de operación de la red reduciendo la energía consumida por estar activamente procesando paquetes.

Razones por las cuales es importante ahorrar energía:
  • En los últimos tiempos las redes computaciones han tenido un gran crecimiento a nivel mundial.
  • Los equipos requieren cada vez mas energía para sus procesos y para enfriarse.

Oportunidades para reducir el consumo de energía en redes:
  • Existen en redes las horas pico de energía.
  • La segunda es que aun cuando la red esta inactiva el equipo aun sigue gastando gran cantidad de energía.

Para poder aprovechar las oportunidades el documento señala que necesita dos pasos:
  1. Que los elementos conectados a la red tengan funciones primitivas de administración de energía a nivel de hardware, con diferentes estados de sueño de la maquina.
  2. Que los protocolos de software necesitaran poder hacer uso de estas funciones primitivas del hardware.
Modelo de energía

Para determinar si un componente esta activo o ocioso, el documento señala que el elemento esta activo cuando esta procesando trafico de entrada o salida, y esta ocioso cuando no procesa ningún paquete, pero esta consumiendo energía.

Entonces la formula para calcular la energía usada por un componente es la siguiente:
$E = p_{a}T_{a} + p_{i}T_{i}$

Donde $p_{a}$ y $p_{i}$ son la energía gastada cuando el componente esta activo(a) y ocioso (i) y las $T$ representan el tiempo.

Entonces si ponemos a dormir el componente cuando esta inactivo por lógica reduciremos $p_{i}$ a $p_{s}$ obteniendo que $p_{s} < p_{i}$  por lo tanto se reduce el consumo de energía del componente.

Poniendo elementos a dormir

Esta parte se basa en una técnica muy conocida para reducir energía que es poner sub-componentes electrónicos a dormir. En el modelo manejan diferentes estados de "sueño" para algunos procesadores pero para simplificar se explica el modelo solo con un estado de "sueño" que es dormir.

Para este modelo se toman en cuenta las siguientes variables:

  • $p_{s}$ el cual se considera una fracción de $p_{i}$
  • $\delta$ el cuál es el tiempo que toma en pasar de estado activo a dormir y viceversa. Si este tiempo es muy alto, disminuye la cantidad de energía ahorrada del sistema, además de que pone una cota inferior al tiempo que debe dormir cada componente.

El tiempo $\delta$ además puede provocar una perdida de paquetes puesto que en el tiempo en el que esto sucede no puede escuchar paquetes, para evitar esto en el documento se especifica que los componentes mandan paquetes vacíos para despertar a los vecinos.

Enfoques y potenciales ahorros

Un enfoque que puede servir para explotar estados de sueño es el llamado sueño oportunista en el que las interfaces en la red duermen cuando están inactivas y son despertadas por un paquete vacío, después de esto vuelve a dormir cuando no recibe paquetes después de un tiempo.
El problema con este enfoque es que pueden ocurrir frecuentes transiciones de se activo a sueño lo cual limita la cantidad de energía ahorrada, por tanto esta técnica solo es útil cuando existen pequeños $/ delta$ y hardware mas sofisticado.

Enfoque en grupos
El siguiente enfoque se centra en mandar en grupos llamadas explosiones los paquetes para maximizar el tiempo en el que los componentes están ociosos, con lo cuál se aprovecharían mas los estados de sueño.
Normalmente se buscan evitar este tipo de agrupamiento de paquetes para evitar congestionamiento en la red pero en el documento se utilizan intervalos de envío de grupos y además los componentes no se van a dormir hasta asegurar que no haya grupos pendientes para evitar congestionamiento.


[imagen obtenida de:"http://static.usenix.org/event/nsdi08/tech/full_papers/nedevschi/nedevschi_html/figures/motivate-peregress.png"]

Adaptación del ritmo de la red

Modelo y suposiciones

Bueno se basa en dos suposiciones muy simples si haces que el componente trabaje mas lento gastara menos energía,
El modelo busca que cada conexión entre componentes de la red tenga una rito de transmisión independiente del otro.
En este modelo $\delta$ es el tiempo que tarda en pasar de un ritmo a otro.

Una estrategia óptima

Cuando el ritmo de llegada de los paquetes es uniforme se busca reducir la cantidad de energía mandando los paquetes  aun ritmo promedio al de llegada, pero si el ritmo de llegada no es uniforme esto puede traer problemas, por lo tanto lo que se busca es un algoritmo uniforme que minimice el consumo de la energía dependiendo de los ritmos de llegada de paquetes.


Mi opinión
En lo personal creo que estos algoritmos se están volviendo muy importantes dado al crecimiento de las redes, y me gusto mucho el enfoque y la forma en que se resuelven los mismos y mi primer pensamiento para arregla este problema sobre el consumo de energía fue reducir el número de nodos en redes y optimizando la energía que consumen los componentes de la red como unidad.

Referencia:
 Reducing Network Energy Consumption via Sleeping and Rate-Adaptation-Sergiu Nedevschi, Lucian Popa, Gianluca Iannaccone, Sylvia Ratnasamy, David Wetherall

Laboratorio 9: Sugerencias de Usabilidad a otros Proyectos

Para esta semana en la el laboratorio de cómputo ubicuo se nos dio la tarea de realizar retroalimentación en el área de usabilidad en los proyectos de nuestros compañeros, esta publicación servirá de reporte para dicha tarea.

Alarma inteligente para autos

En su proyecto la seguridad es muy importante por que como usuario, puede existir el temor de que el auto sea robado con mas facilidad utilizando una aplicación de este tipo. Creo que deberían explicar al usuario con mas detalle como es que funcionan los tres niveles de seguridad.
En la activación manual no presentaron mucha información de la interfaz gráfica del móvil ni del dispositivo de comunicación, pero creo que no debería haber una interfaz gráfica para abrir el auto, puesto que el tiempo de cargar la aplicación seria demasiado sería mejor utilizar los sistemas que utiliza el celular como desbloquear con patrones de movimiento en la pantalla y su aplicación como un daemon esperando a que se desbloquee el sistema para automáticamente detectar el auto y abrirlo, ya que estos modos de autenticación son muy rápidos, con un simple par de movimientos serían capaces de acceder a su carro lo que es más cómodo y le da mas valor a su aplicación.


[imagen obtenida de:"http://phandroid.com/wp-content/uploads/2012/03/android-unlock-pattern.jpg"]

Ahora mi sugerencia es no tener interfaz gráfica para abrir el carro, pero para los otros dos niveles de seguridad si sería necesario. El sensor de intrusos sugiero que funcione con el daemon dando notificaciones al usuario exclusivamente cuando se detecten amenazas en su auto, dando niveles de amenaza y poniendo colores para que el usuario entienda el nivel de amenaza mismo, verde para posible intruso, morado para el auto ha sido abierto y rojo para el auto esta en movimiento, por decir un ejemplo.
La localización no veo problema con que se encuentre en el menú de la aplicación mostrando una pantalla con un mapa y las opciones para localizar el auto.
Por ultimo me parece conveniente que añadan un menú de configuración con las diferentes opciones de seguridad muy detalladas y con sub-menus y pantallas diferentes para cada una, para mostrar las consecuencias y diferencias entre una configuración y otra.
Para el color de sus gráficos sugiero un color azul puesto que propicia la tranquilidad y seguridad.

Computadora inteligente (autenticación con detección de rostros)

Creo que las encuestas no son una manera fiable de obtener información de su sistema en especifico, creo que lo que deberían hacer es la prueba del hombre tras la cortina y medir los tiempos que toma la instalación, el entrenamiento de su software y reconocer el rostro y después compararlo con investigaciones ya existentes sobre cuanto tiempo puede permanecer un usuario en una tarea antes de que pierda la atención en ella. Además de medir el número de intentos que tiene que hacer el usuario para entrar a la sesión de su computadora.
Otra forma de llevar a cabo las encuestas es dejándole al usuario el demo del sistema y después unas cuantas semanas realizarle la encuesta, si el sistema es malo acabara con su paciencia y se volverá mas sincero en las preguntas, además de que tendrá bases mas solidas para contestar la encuesta.
Sobre el tiempo que espera el sistema operativo para bloquearse, los sistemas operativos ya tienen tiempos por defecto y creo que ustedes no deberían preocuparse por eso.
Creo que los temas que deberían investigar son sobre bloqueo de computadores por inactividad y detección de rostros, puesto que las tecnologías no son nuevas debe haber muchos artículos de ello y les ayudaran a saber exactamente que deben tomar en cuenta y preguntar.

Oficina personalizada

Yo creo que en su proyecto en cuestiones de usabilidad deben preocuparse por cuestiones como el tiempo que toma en leer y el alcance que tiene el dispositivo para leer, después determinar cual serían las medidas correctas que debería tener su sistema, yo sugiero que a diferentes usuarios les den dispositivos con diferentes capacidades para aproximar las medidas.
En el caso del tipo de RFID yo dejaría las tarjetas, puesto que las tarjetas son fáciles de guardar en una cartera y de utilizar como la tarjeta MIA del metro, la verdad yo tuve buenas experiencias utilizándola. El llavero puede ser incomodo llevar muchos llaveros si es que se deben abrir mas puertas de otros lugares, además de que el usuario puede cuestionar el hecho de tener que sacar las llaves para terminar usando el llavero, no se ve gran mejora.

Localizador de objetos

En su proyecto creo que deberían centrarse en el tipo de usos que los usuarios le van a dar a la aplicación, necesitan saber el alcance que debe tener el dispositivo hacia el marcador en el objeto, para eso yo investigaría el tamaño común de una casa o departamento si es que su proyecto será mas usado dentro de casas.
Otro punto importante es que necesitan asegurar que el usuario sea capaz de llegar al objeto sin que este proceso sea tan complicado, las opciones que se me ocurren es utilizar realidad aumentada para ver la posición del objeto en la pantalla, otra opción es hacer un mapa de la casa y mostrar el objeto en el mapa, una opción mas sería usar un sonido que se repita y que cambie de frecuencia entre mas lejos o mas cerca se este del usuario, para comprobar cual es mejor yo le daría las tres al usuario y comprobaría los tiempos que toma en encontrar los objetos.

Galería inteligente

No me gusta particularmente la idea de que la caja sea negra por que aunque la curiosidad puede atraer al usuario a interactuar con ella, me parece que se aburrirían de esto y al final les parecería tedioso tener que revisar vitrina por vitrina para encontrar una obra que les agrade, me parece mejor la idea de reproducir sonido o vídeo con la explicación de la obra cuando alguien se acerque.
Otra cosa que note que deben tomar en cuenta es el número de personas que se acerquen ala obra necesarias para empezar a interactuar con ellas, puesto que si se interactúa con el primero que llegue por ejemplo, si es un sonido los demás que se acerquen podrían escuchar solo la mitad de la explicación y podría ser molesto.

Despertador inteligente

En la interfaz de usuario deberían permitir que el usuario sea capaz de configurar días en los que debería sonar recurrentemente y en horas en las que solamente debería sonar una vez el despertador, yo sugeriría usar como interfaz un mini calendario en vertical con los diferentes días de la semana y dejar caer en cada día una hora para sonar la alarma y definir características especificas de la alarma como si es recurrente o no y el tipo de alarma y sonido.

Una opción que podrían agregar es añadir una alarma para dormir, algo como sonar una canción de cuna o algo parecido, al menos ocho horas antes de la hora señalada para despertarse, para evitar que el usuario pierda horas importantes de sueño, lo cuál si el usuario permite implementarlo podría ayudar con el problema de que el usuario no se siente descansado.

Casa inteligente

La casa inteligente me parece un sistema diseñado para automatizar los trabajos en una casa y agregar seguridad a la misma, en realidad yo creo que las pruebas que deberían realizar deberían ser para saber que tan cómodo estaría el usuario con una casa de este tipo y que consecuencias podría traer a su modo de vida. Es importante ofrecer mucho control sobre la casa, pero deberían preguntarse que sistemas de seguridad necesita la casa, y como deberían mostrárselos al usuario para que este se sienta seguro.

Una alternativa que podrían implementar sería poner micrófonos en la casa y controlarla por medio de la voz, esto haría mas rápido y simple el encender una luz o encender un aparato o abrir una puerta desde mi punto de vista.

CarFxP

Me parece interesante su proyecto y me parece excelente el diseño metro, yo creo que necesitarían mas notificaciones al usuario de que el sistema esta funcionando, puesto que no mostraron ninguna imagen sobre como el usuario se da cuenta que esta siendo leído el Tag NFC.
Otra cosa a cuidar es que tan cómodo es el uso de TagNFC en el auto para los usuarios tal vez deberían empezar a pensar en implementar formas alternativas.

Referencias:
http://elisa.dyndns-web.com/~elisa/teaching/sys/intel/

miércoles, 24 de abril de 2013

Homework 4: adaptive coding


For this week's class information theory and coding methods, we were given the task of thinking and to code a Huffman algorithm version made ​​of the last implementation made for the last class (link) to be able to function, taking as input the text online, this is getting character by character without actually knowing the frequency of all characters in the text.

My implementation of adaptative Huffman algorithm
The Huffman algorithm is a coding or compression algorithm, which takes a group of characters and their frequencies and generates Huffman codes which are used to perform compression.
The algorithm works by using frequencies of each character to build a binary tree, the path made from the root of the tree is the Huffman code character associated with the character and is used for compression.
The algorithm works on the premise that the more frequently characters should have shorter Huffman codes.
To ensure that the most frequent characters are shorter, We create the tree gathering the leaves are less frequently as children of a new node, this continue until it is a single root node for all characters.

In order to function adaptively, what i added is very simple, before you can compress character by character, the program stored in a variable buffer indicated amount of characters, this is used to calculate an initial tree Huffman coding, only that it add a node with zero frequency as a character, the character which is given the name of 'Joker', it has low frequency and represents the characters that have not appeared yet since these also have low frequency.



Now once we have an initial tree we can encode character by character as they come, the idea is that if you get a character that is not in the tree, add two children to the node "Joker", the new character and another "Joker" node, if we find another character that is not in the tree we will add this in the same way in the last "Joker" node.

In this example draws only the nodes that are added, the final Huffman code gather all nodes "Joker for convenience but serves to explain how adding nodes that have not yet appeared. the added nodes are" Y "and" U ".



Code


Results
To display a graphical results, this graphs are made similar to those of the non-adaptive Huffman task. As initial buffer size chosen 10% of the input text, input texts length vary, red lines are the distribution of letters in Spanish distribution, and the green uniform distribution, these distributions to show Huffman switching between Normal and my implementation of adaptive Huffman.

 The compression ratio estimated from the data compresed split between original data:
Time data encoding of the complete characters:
Time data decoding of the complete characters:

Size of the data obtained:

Suggestions of improvement
My implementation is very simple but I think it could be improved by:

  • Predefined frequencies:Choosing input character frequencies knowing what kind of text is, for example if it is a common text in Spanish there are many frequency tables, as input would receive the characters more frequent in that kind of text.
     
  • Adaptive node adding:
    Seeking a way to accommodate in a adaptive way nodes which are not found in the tree.

References:

http://elisa.dyndns-web.com/~elisa/teaching/comp/info/adaptive.pdf

lunes, 22 de abril de 2013

Laboratorio 8: Usabilidad en cómputo ubicuo

Buen día, para esta semana en el laboratorio de computo ubicuo se nos dio la tarea de buscar un texto científico relacionado con computo ubicuo y usabilidad y realizar un resumen del texto. El texto que elegí para esta tarea es el siguiente:

Usable ubiquitous computing in next-generation conference rooms: design, evaluation, and architecture

Autores:
Maribeth Back, Saadi Lahlou, Rafael Ballagas, Surapong Lertsithichai, Masatomi Inagaki, Kazunori Horikiri, Jeffrey Huang


[imagen obtenida de:"http://iamdaveknockles.files.wordpress.com/2011/03/conference-room-2-web-1.jpg"]

El texto abarca el tema del uso de la usabilidad en cuartos de conferencia inteligentes, de nueva generación. Primero abarcan el problema como de suma importancia por que, el uso de cuartos de conferencia inteligentes abarcan muchos aspectos de usabilidad importantes, por lo que parece importante diseñar mejores modelos para mejorarlos.
Para los autores el reto es poder encontrar métodos para tener buenas medidas de usabilidad y además de que estos métodos se adecuen a las nuevas tecnologías para conferencias, como conferencias por internet que creo que es la tecnología a la que le ponen mas importancia en el articulo.

Para resolver los problemas de la usabilidad en cuartos de conferencia, el documento plantea realizar un taller con personajes con muchos conocimientos y con experiencia en trabajos de usabilidad y en el tema planteado. El taller se llama de igual manera que el titulo del documento y fue realizado el 17 de septiembre del 2006.

Los temas de interés en el taller planeados eran los siguientes:
  • Diseño Usabilidad en salas de conferencias de última generación
  • Necesidades sociales de las reuniones formales e informales
  • Utilizando pantallas ubicuas: múltiples pantallas y medios de comunicación
  • Muebles interactivos y entornos inteligentes
  • Diseño atravez de las barreras culturales y lingüísticas
  • Aprender de prototipos y sistemas experimentales
  • Diseño de las salas de reunión y la forma física de los objetos inteligentes
  • Sistemas sensibles al contexto para las salas de conferencias
  • Captura de reuniones y acceso a datos
  • Seguridad, autenticación, manejo de datos, y la privacidad
  • Diseño adecuado y técnicas de evaluación

En la página web del proyecto se muestran los resultados obtenidos, mostrando los puntos de vista de diferentes areas de los participantes:
http://www.fxpal.com/UbiComp2006/

Algunos de la gran variedad de artículos interesantes que salieron de esta reunión son: 

inSpace


[Imagen obtenida de:"http://www.cc.gatech.edu/pixi/wp-content/uploads/2010/01/inSpaceTable-270x202.jpg"]

En el paper "inSpace Projector: An Accessible Display System for Meeting Environments" Aras Bilgen y W. Keith Edwards
hablan sobre como las tecnologías viejas con cables pueden ser un impedimento para que un aparato sea usable, y que las nuevas tecnologías de comunicación a distancia entra aparatos como Wi-fi o Bluetooth pueden mejorar estos aspectos.

Ellos proponen un proyecto inSpace el cuál permite a los participantes de una reunión proyectar una presentación en diferentes pantallas o cambiar entre pantallas con una interfaz de software basada en espacios.
El proyecto es muy interesante puesto que funciona instalando un dispositivo de software en la computadora de los usuarios, con este ellos pueden decidir en que pantalla presentar, pero el sistema detecta la posición de ellos en el cuarto y puede saber quien esta proyectando y que privilegios dar al mismo, además de los que no proyectan pueden pedir la pantalla en su ordenador. Otra característica solo necesita el usuario ponerse de pie para presentar.

The Use Use Project

En el articulo "The USE Project: designing smart spaces for real people" de:
Maribeth Back, Gene Golovchinsky, John Boreczky, Pernilla Qvarfordt, Laurent Denoue, Tony Dunnigan

Se habla como las personas dan conferencias para establecer relaciones con otras personas y lo que estos autores intentan es separar distintas piezas de tecnología con el fin de estimular la interacción natural entre personas sin tener que lidiar con la configuración de distintas tecnologías.

Nos explica como en los cuartos de conferencia existen personas dedicadas al mantenimiento y a la configuración de todo lo relacionado con los cuartos, pero que ellos buscan crear un proyecto que permite, liberar a estos de esas responsabilidades.
Para esto ellos proponen el proyecto USE(Usable Smart Environments), que es un proyecto que tratara de tener las características mencionadas tomando como punto principal la proyección de presentaciones en diferentes pantallas.


Access Grid



[imagen obtenida de:"http://rc.rit.edu/images/digroc2007-ag.jpg"]

En el documento "Toward Advanced Collaboration Environment with High-Quality Media and User-Friendly Interaction"  de JongWon Kim, se centra en las video conferencias y como estas son cada vez mas ampliamente utilizadas puesto que no siempre hay la facilidad de tiempo por los participantes de una reunion, o el precio del transporte no es accesible o simplemente por comodidad.
Esta persona propone el proyecto Access Grid que es un sistema de colaboración en grupo que permite llevar a cabo presentaciones a distancia. Su sistema utiliza paquetes UDP para distribuir los datos multimedia a los diferentes receptores en un túnel UDP. El proyecto se centra en tener una transmisión de alta definición de vídeo y que sea muy amigable con los usuarios.
Otra de las cuestiones de usabilidad en las que se centra es que las personas necesitan compartir diferentes tipos de multimedia como gráficas, imágenes, documentos o animaciones en 2d o en 3d.

Otras características de usabilidad destacables de su software:
  • Tiene un sistema para controlar la presentación utilizando un apuntador láser, la cual puede ser controlada por múltiples usuarios con múltiples apuntadores.
  • El apuntador láser cuenta con una etiqueta RFID por lo cuál es posible rastrear la posición física de los diferentes colaboradores en la presentación.
  • La presentación también puede ser controlada con un guante agregando además características para controlar modelos 3D de forma sencilla y la verdad muy impresionante.
  • El sistema puede utilizar diferentes aparatos de hardware en forma distribuida para utilizar algoritmos de compresión muy poderosos y aumentar la calidad del vídeo transferido.


Referencias:
http://fxpal.fxpal.com/publications/FXPAL-PR-06-373.pdf
http://www.fxpal.com/UbiComp2006/
http://www.fxpal.com/UbiComp2006/USE_ubicomp.pdf
http://www.fxpal.com/UbiComp2006/BilgenEdwards.pdf
http://www.fxpal.com/UbiComp2006/JongWonKim.pdf

sábado, 20 de abril de 2013

Tarea 6: Detección de agujeros

Para esta semana en la clase de visión computacional se nos dio a la tarea de detectar la posición de agujeros en una imagen, después deberíamos marcar con un punto amarillo el centro del agujero, rellenar el agujero de un tono morado, con un tono morado mas fuerte marcar el relleno, dibujar una etiqueta para el agujero e imprimir en la terminal, los identificadores de cada agujero y su porcentaje de tamaño respecto a toda la imagen.

Detección de agujeros

Un agujero es una figura elíptica donde existe una hendidura y por lo tanto un cambio de intensidad de la luz, aprovechando esto es fácil detectar una imagen donde existe un agujero.
Estas técnicas pueden ser utilizadas para miles de aplicaciones entre ellas puede ser medir la calidad de la superficie de un producto, o para desviar agujeros que puedan presentar un obstaculo a autos robots.

La técnica que estaremos programando en esta clase sera la de utilizar matrices con patrones de agujeros, y buscando por patrones parecidos en la imagen. Dado que esta técnica puede tomar mucho tiempo de procesamiento si se buscan los patrones en toda la imagen, necesitamos reducir el espacio de búsqueda de los patrones, para lo cual utilizaremos un histograma de los cambios de intensidad en cada linea o columna de pixeles en la imagen.

Con la practica de laboratorio de esta semana generamos un código que nos redujo el espacio de búsqueda de patrones de agujeros en la imagen.

Características del patrón
El primer paso fue identificar el patrón de búsqueda, para eso tome varias fotos a un grupo de agujeros en un pedazo de cartón, tomando uno como muestra y sabiendo la posición del agujero extraje, la matriz del agujero y obtuve cuando variaba un valor de otro dividiendo todos los valores entre el número mas pequeño encontrado.

La matriz de 11x11 obtenida fue la siguiente:
[[ 1.67, 1.67, 1.68, 1.66, 1.66, 1.65, 1.66, 1.65, 1.65, 1.66, 1.65], 
[1.68, 1.66, 1.61, 1.50, 1.43, 1.43, 1.50, 1.61, 1.65, 1.66, 1.65], 
[1.66, 1.61, 1.39, 1.08, 1.07, 1.09, 1.42, 1.50, 1.61, 1.66, 1.65], 
[1.65, 1.39, 1.08, 1.03, 1.00, 1.04, 1.09, 1.45, 1.65, 1.66, 1.65], 
[1.65, 1.28, 1.03, 1.00, 1.00, 1.00, 1.07, 1.45, 1.65, 1.66, 1.65], 
[1.68, 1.28, 1.03, 1.01, 1.01, 1.01, 1.07, 1.51, 1.66, 1.66, 1.65], 
[1.68, 1.59, 1.28, 1.03, 1.03, 1.07, 1.46, 1.65, 1.66, 1.66, 1.65], 
[1.70, 1.70, 1.59, 1.34, 1.34, 1.46, 1.66, 1.66, 1.66, 1.66, 1.65], 
[1.70, 1.69, 1.69, 1.68, 1.68, 1.68, 1.66, 1.66, 1.66, 1.65, 1.65], 
[1.69, 1.69, 1.69, 1.69, 1.69, 1.68, 1.68, 1.66, 1.66, 1.66, 1.65], 
[1.69, 1.69, 1.69, 1.69, 1.69, 1.68, 1.68, 1.66, 1.66, 1.66, 1.65]]
Aunque no todos los orificios son iguales, los demás orificios deben de ser muy parecidos a este tomando en cuenta que la distancia a la cámara es la misma y los orificios fueron hechos con el mismo artefacto.

Los orificios que tome como patrón tienen un radio aproximado de 5 píxeles reduciendo el tamaño de la imagen a un máximo de 128x128, tiene fondo oscuro y va incrementando la intensidad de la luz conforme se acerca a las orillas.

La Medición del parecido se hizo de la misma forma que se aplica una mascara de convolución a un píxel (en nuestro caso a nuestro supuesto centro del orificio obtenido con los histogramas), recorriendo todos los vecinos y aplicando una operación entre la celda del patrón y el valor que se superpone en la imagen. La diferencia es que la operación aplicada es un factor absoluto de la resta entre la celda del patrón y el valor que le corresponde en la imagen. Sumando las operaciones en cada celda se obtuvo una aproximación numérica del cuanto se parece el patrón a los vecinos del lugar donde supuestamente esta el orificio.

Código

Resultados

Original Salida
max@max-laptop:~/Dropbox/vision_computacional/tarea6$ python hole.py lb7-1.png 
Porcentaje del agujero con respecto a la imagen
    Agujero:  H1 0.204427083333%
    Agujero:  H2 0.160807291667%
    Agujero:  H3 0.136067708333%
Tiempo de corrida: 1.7956700325


Original Salida
max@max-laptop:~/Dropbox/vision_computacional/tarea6$ python hole.py lb7-2.png 
Porcentaje del agujero con respecto a la imagen
    Agujero:  H1 0.0706380208333%
    Agujero:  H2 0.0670572916667%
Tiempo de corrida: 1.49644517899


En la tercera y ultima imagen no fue posible detectar la posición de los agujeros debido a que como puede verse en la búsqueda vertical de posibles agujeros se confunden los tres como si fueran un solo orificio, lo que provoca que el patrón buscado no quede en el centro y no sea detectado.
Original Salida del histograma
max@max-laptop:~/Dropbox/vision_computacional/tarea6$ python hole.py lb7-3.png 
Porcentaje del agujero con respecto a la imagen
Tiempo de corrida: 0.777371883392


Referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/vision/agujeros.pdf

viernes, 19 de abril de 2013

Laboratorio 7: Histogramas como preprocesamiento para encontrar agujeros

Para esta semana en el laboratorio de visión computacional se nos dio a la tarea de utilizar histogramas con las intensidades de color de filas y columnas de una imagen, para buscar posiciones de posibles agujeros en la imagen, esto como preprocesamiento para la detección de los mismos.

Detección de agujeros
Un agujero es una figura elíptica donde existe una hendidura y por lo tanto un cambio de intensidad de la luz, aprovechando esto es fácil detectar una imagen donde existe un agujero.
Estas técnicas pueden ser utilizadas para miles de aplicaciones entre ellas puede ser medir la calidad de la superficie de un producto, o para desviar agujeros que puedan presentar un obstáculo a autos robots.

La técnica que estaremos programando en esta clase sera la de utilizar matrices con patrones de agujeros, y buscando por patrones parecidos en la imagen. Dado que esta técnica puede tomar mucho tiempo de procesamiento si se buscan los patrones en toda la imagen, necesitamos reducir el espacio de búsqueda de los patrones, para lo cual utilizaremos un histograma de los cambios de intensidad en cada linea o columna de pixeles en la imagen.

Para generar el histograma vertical de la imagen solamente sume la intensidad de todos los pixeles para cada fila de la imagen, y para generar el horizontal la suma de pixeles de cada columna en la imagen

Ejemplo:
En la siguiente imagen se cuenta la intensidad de pixeles y se muestra en la gráfica posterior.

Imagen:
 Histograma:

Esto nos servirá puesto que en los orificios hay muy distinguibles de intensidad de luz por lo que es muy probable que los orificios se encuentren en los lugares donde haya un minimo o maximo local de intensidad de la imagen.

Código


Resultado

Original Histograma Salida


Referencias: 
http://elisa.dyndns-web.com/~elisa/teaching/comp/vision/agujeros.pdf

miércoles, 17 de abril de 2013

Laboratorio 6: Detección de círculos y elipses

Para esta semana en la clase de visión computacional se nos dio a la tarea de construir un código capaz de detectar elipses y círculos en una imagen utilizando el método cuerda-tangente, además deberá rellenar la figura con un color aleatorio.

Detección de elipses
La detección de elipses es muy útil en la rama de visión computacional, puede utilizarse para detectar círculos distorsionados en un caso real de uso, para detectar la forma de un rostro o cualquier cosa circular.

Para este reporte mi implementación se basa en un método que utiliza las lineas tangentes las lineas del contorno del elipse, esto con la premisa de que utilizando estas lineas y los puntos al cual son tangentes las mismas, se puede calcular una linea que pasa por el centro de la elipse.


[Image obtenida de:"http://ars.els-cdn.com/content/image/1-s2.0-S0957417410014612-gr2.jpg"]

Esta vez debido se diferenciara entre círculos y debido a que un circulo es una elipse con características especificas el mismo código puede ser útil

A grandes rasgos los pasos de mi implementación son los siguientes:

  1. Se detecto el borde de la imagen utilizando mascaras de convolución de Sobel tal como se hizo en la tarea 1.
  2. Después se agruparon los bordes utilizando el algoritmo BFS de recorrido en grafos, esto con el fin de eliminar el ruido en el calculo.
  3. Después de manera aleatoria se eligieron parejas de pixeles en borde, cuidando que estos no tengan el mismo gradiente de cambio (El mismo gradiente utilizado para detectar bordes), y cuidando que fueran del mismo grupo.
  4. Por cada pareja se calcula:

    1. La recta tangente para cada pixel, esto utilizando el gradiente siendo $G_{y}$ y $G_{x}$ los lados de un triangulo se calcula la pendiente de la recta de la forma $m = \frac{G_{y}}{G_{x}}$, teniendo la pendiente y el punto por el que pasa es fácil calcularla.
    2. Después se calculó el punto medio $tl2$ que es el punto en el cual se cruzan las rectas.
    3. Después se calculó el punto medio entre los pixeles elegidos $ml2$.
    4. Teniendo esto se calculó una recta que pasa por los puntos $ml2$ y $tl2$, la cual pasa por el centro del ellipse.
    5. Se dibuja una linea que pase por el centro.
  5.  Una vez teniendo una gran cantidad de lineas dibujadas, se toman los puntos en los cuales se crucen mas lineas como centros de elipses.
  6. Después se calculan las magnitudes de los elipses, utilizando los pixeles bordes y buscando los pixeles horizontales y verticales para encontrar las magnitudes del rectángulo que rodea la elipse.

Código


Resultado

Original:
Salida:
max@max-laptop:~/Dropbox/vision_computacional/lb6$ python ellipse.py lb-2.png 
Porcentaje del area de las figuras respecto a la imagen:
Circulo encontrado: C1:
    Porcentaje del area: 26.2502462327 

Tiempo de corrida: 6.94555902481




Original:
max@juan-laptop:~/Dropbox/vision_computacional/lb6$ python ellipse.py lb-3.png 
Porcentaje del area de las figuras respecto a la imagen:
Ellipse encontrado: E1:
    Porcentaje del area: 16.8737886667
Tiempo de corrida: 3.23047399521
Salida:



Original:

Salida:

max@juan-laptop:~/Dropbox/vision_computacional/lb6$ python ellipse.py lb-1.png 
Porcentaje del area de las figuras respecto a la imagen:
Circulo encontrado: C1:
    Porcentaje del area: 9.28058376671 

Ellipse encontrado: E2:
    Porcentaje del area: 7.66990393943
Circulo encontrado: C3:
    Porcentaje del area: 4.90873852123 

Ellipse encontrado: E4:
    Porcentaje del area: 8.89708856974
Tiempo de corrida: 5.71808099747




Referencias:

http://elisa.dyndns-web.com/~elisa/teaching/comp/vision/elipses.pdf 



martes, 16 de abril de 2013

Laboratorio 7: Generadores de tráfico en NS-2

Para esta semana en la clase de redes de telecomunicaciones se nos dio la tarea de crear generadores de trafico en las topologías que ya teníamos en el simulador de redes NS-2 y medir algunas características de desempeño de los simuladores.

Generadores de tráfico
Para esta tarea tomé el generador de topologías de el laboratorio de la semana pasada y después generé tres tráficos entre 3 diferentes pares de nodos, estos elegidos al azar con distribución uniforme, después para cada uno de los tres tráficos se le asigno una de las tres distribuciones que vienen por defecto en NS-2 para generar tráfico entre dos nodos, las tres distribuciones son las siguientes:

  1. Exponencial: Esta distribución genera en curso y trafico detenido por periodos de tiempo definidos con distribución exponencial. Se define de la siguiente forma "Application/Traffic/Exponential".
  2. Exponencial: Esta distribución genera en curso y trafico detenido por periodos de tiempo definidos con distribución exponencial. Se define la siguiente forma "Application/Traffic/Pareto".
  3. CBR: Esta genera paquetes con una tasa de bits constante. Se define de la siguiente forma "Application/Traffic/CBR".
Después por cada trafico en la red, se mide el throughput, los paquetes enviados, y recibidos durante el mismo, utilizando el código de AWK utilizado en el laboratorio cinco de la materia.

Se agrego otro generador de

Código


Resultado
Para mostrar el resultado se utilizara el generador de anillo puesto que el generador de hipercubo fue utilizado la semana pasada.

kalavera@kalavera-AOD270:~/Dropbox/redes_de_telecomunicaciones/lb7$ python generador_trafico.py anillo 8
Exponencial:
  Enviados: 2128
  Recibidos: 2126
  Throughput: 555.681
Pareto 
  Enviados: 2679
  Recibidos: 2674
  Throughput:698.927
CBR:
  Enviados: 3748
  Recibidos: 3744
  Throughput:978.497


Video:


Referencias:
http://webingineer.wordpress.com/2010/08/15/simulation-example-in-ns-2/
http://sydney.edu.au/engineering/it/~deveritt/networksimulation/trafficgeneration.html

lunes, 15 de abril de 2013

Tarea 5: Detección de ellipses

Para esta semana en la clase de visión computacional se nos dio a la tarea de construir un código capaz de detectar Elipses en una imagen utilizando el método cuerda-tangente.

Detección de elipses
La detección de elipses es muy útil en la rama de visión computacional, puede utilizarse para detectar círculos distorsionados en un caso real de uso, para detectar la forma de un rostro o cualquier cosa circular.

Para este reporte mi implementación se basa en un método que utiliza las lineas tangentes las lineas del contorno del elipse, esto con la premisa de que utilizando estas lineas y los puntos al cual son tangentes las mismas, se puede calcular una linea que pasa por el centro de la elipse.


[Image obtenida de:"http://ars.els-cdn.com/content/image/1-s2.0-S0957417410014612-gr2.jpg"]

A grandes rasgos los pasos de mi implementación son los siguientes:

  1. Se detecto el borde de la imagen utilizando mascaras de convolución de Sobel tal como se hizo en la tarea 1.
  2. Después se agruparon los bordes utilizando el algoritmo BFS de recorrido en grafos, esto con el fin de eliminar el ruido en el calculo.
  3. Después de manera aleatoria se eligieron parejas de pixeles en borde, cuidando que estos no tengan el mismo gradiente de cambio (El mismo gradiente utilizado para detectar bordes), y cuidando que fueran del mismo grupo.
  4. Por cada pareja se calcula:

    1. La recta tangente para cada pixel, esto utilizando el gradiente siendo $G_{y}$ y $G_{x}$ los lados de un triangulo se calcula la pendiente de la recta de la forma $m = \frac{G_{y}}{G_{x}}$, teniendo la pendiente y el punto por el que pasa es fácil calcularla.
    2. Después se calculó el punto medio $tl2$ que es el punto en el cual se cruzan las rectas.
    3. Después se calculó el punto medio entre los pixeles elegidos $ml2$.
    4. Teniendo esto se calculó una recta que pasa por los puntos $ml2$ y $tl2$, la cual pasa por el centro del ellipse.
    5. Se dibuja una linea que pase por el centro.
  5.  Una vez teniendo una gran cantidad de lineas dibujadas, se toman los puntos en los cuales se crucen mas lineas como centros de elipses.
  6. Después se calculan las magnitudes de los elipses, utilizando los pixeles bordes y buscando los pixeles horizontales y verticales para encontrar las magnitudes del rectángulo que rodea la elipse.

Código


Resultado

Imagen original:

Salida:

max@max-laptop:~/Dropbox/vision_computacional/tarea5$ python ellipse.py ellipse.png 
1
Porcentaje de diagonales de las ellipses respecto al digonal de la imagen:
E1:
    Diagonal horizontal: 7.40740740741
    Diagonal vertical: 7.40740740741
Tiempo de corrida: 0.608282089233


Imagen original:

max@max-laptop:~/Dropbox/vision_computacional/tarea5$ python ellipse.py ellipses.png 
4
Porcentaje de diagonales de las ellipses respecto al digonal de la imagen:
E1:
    Diagonal horizontal: 2.95138888889
    Diagonal vertical: 2.95138888889
E2:
    Diagonal horizontal: 3.125
    Diagonal vertical: 3.125
E3:
    Diagonal horizontal: 4.34027777778
    Diagonal vertical: 4.34027777778
E4:
    Diagonal horizontal: 2.08333333333
    Diagonal vertical: 2.08333333333
Tiempo de corrida: 0.995491027832


Referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/vision/elipses.pdf

jueves, 11 de abril de 2013

Huffman encoding algorithm

For this week's class theory of information we were given the task of building an implementation of the Huffman compression algorithm, this publication will serve as a way to report for the task.

Huffman compression algorithm


The Huffman algorithm is a coding or compression algorithm, which takes a group of characters and their frequencies and generates Huffman codes which are used to perform compression.
The algorithm works by using frequencies of each character to build a binary tree, the path made from the root of the tree is the Huffman code character associated with the character and is used for compression.
The algorithm works on the premise that the more frequently characters should have shorter Huffman codes.
To ensure that the most frequent characters are shorter, We create the tree gathering the leaves are less frequently as children of a new node, this continue until it is a single root node for all characters.

An example and an explanation of the method that helped me to understand the workings of the algorithm is in the following video on the channel www.youtube.com "soguw".

To unzip the file, I use a code implementation that used the tree and data bits, bit by bit is traversed the encoded text and each iteration moves through the tree according to bits of the encoded text. It runs from the root, until a final leave, the character of the leave is added to the file decrypted and we get back to the root, go finish it until the bits of the encoded file is traversed.
Code


program running

To demonstrate the program, this running will show the output for text "Huffman", the output of the program was:
max@juan-laptop:~/Dropbox/teoria_informacion/homework3$ python huffman.py

Encoding...

Encoding dictionary: {'a': '100', 'f': '01', 'H': '101', 'm': '110', 'n': '111', 'u': '00', 'root': ''}

Original text: Huffman

Encoded text: 101000101110100111

Compression ratio (compressed / original): 0.0128571428571

Decoding...

Original text: 101000101110100111

Decoded text: Huffman



And the program generated the following tree:


Testing
Now to test the algorithm did some graphs showing various steps of the run of the program, shown in red runs the program on a regular character, these were obtained from the common frequency of occurrence of certain characters in Spanish texts. Green is shown in the worst case, that is one in which the frequency is the same for all characters.

This shows the compression time in seconds, the red line shows a typical case and worst case green, time running time increase en normal case because it need more calculations to find the less frequency nodes, but it is good because if the difference between frequencies increase the compression works better:
This shows the decompression times in seconds:
The amount of memory used for compression:
This shows the compression ratio is the approximate amount of memory of the compressed file divided by the weight of the original file.
As you can see the time to compress and decompress increases for typical cases, but the memory used and clearly the compression ratio decreases.

References:
http://es.wikipedia.org/wiki/Algoritmo_de_Huffman
http://www.cprogramming.com/tutorial/computersciencetheory/huffman.html