[TEORÍA DE LA INFORMACIÓN] Resumen

Accelerating Protein Classification Using Suffix Trees

Bogdan Dorohonceanu and C.G. Nevill-Manning

Introducción

Las matrices de búsqueda de posición específica han sido usadas extensamente para reconocer regiones altamente conservadas de proteinas. Dorohonceanu y Nevill-Manning presentan un método para acelerar las búsquedas usando estructura de arboles de sufijos calculada desde las secuencias que se buscarán.

Estas matrices de búsqueda capturan la distribución característica de aminoácidos. Son más sensitivas que los métodos basados en expresión regular coo PROSITE y EMOTIF pero requieren menos información que los modelos ocultos de Markov.

Su principal desventaja contra PROSITE y EMOTIF es su velocidad. Debido a que en esos métodos permiten hacer saltos en cualquier discrepancia, en una matriz de búsqueda siempre se acierta con la misma probabilidad, por lo que hacer saltos es algo problemático.

La desventaja de usar arboles de sufijos es que es muy caro en términos de memoria; requiere 37 bytes por símbolo de entrada. Sin embargo los autores lograron reducir esto a 17 bytes.

Matices de búsqueda

Una matriz de búsqueda de posición específica S representa un alineamiento local sin pausas de una familia de secuencias. El alineamiento consiste en varias posiciones contiguas, cada posición representada por una columna en la matriz. Cada columna j consiste en un vector Sj(r), un resultado por cada posible residuo r.

Una matriz de búsqueda puede ser usada en análisis de secuencias, pasando la matriz por la secuencia y calculando el resultado del segmento. Cada resultado es la suma de las entradas apropiadas de la matriz, donde cada residuo corresponde a un resultado en una columna de la matriz.

Intuitivamente, un resultado del segmento mayor indica un mayor probabilidad de que la secuencia sea igual que la matriz de búsqueda.

Muchas implementaciones de PSSM's para funciones de predicción de proteínas aplican la matriz a cada segmento de cada proteína en la entrada. ordenan los segmentos por sus resultados y presentan los mejores resultados.

Arboles de sufijos

Un árbol de sufijos es un árbol compacto de sufijos en una cadena, para cada sufijo de una cadena hay un camino en su árbol correspondiente desde la raíz hasta las hojas que contengan la cadena.

La imagen anterior muestra un árbol de sufijos para la cadena "abab$". Este árbol es compactado de la siguiente manera. Donde sea que dos aristas inicien en el mismo nodo que comparta un prefijo, una nueva arista y un nodo son creados, y la arista tendrá la misma cadena. Por lo que las aristas anteriores ya no comparten el prefijo. Esto se hace hasta que ninguna arista comparta prefijos.

Para encontrar un segmento de buenos resultados en un set de secuencias de proteínas, primero se crea un arreglo de secuencias. Después se hace un DFT (búsqueda de profundidad) del árbol, calculando los resultados para las cadenas de las aristas.

Donde sea que el resultado alcance el umbral, todas las subcadenas representadas por las hojas de ese nodo deben también alcanzarlo, y pueden ser reportadas.

Esa es la llave para la aceleración, muchas subcadenas pueden ser descontinuadas basado en un simple camino. La siguiente imagen muestra dos casos: un subarbol que acierta y uno que no lo hace.

Arboles de sufijos compactos

Un problema significante es que los arboles son su tamaño en memoria primaria. Los aminoacidos consisten en 20 elementos, en la base de datos se registran 20 millones de aminoacidos y con aproximadamente 30 millones de nodos. Esto es 30,000,000 nodos x 22 punteros por nodo x 4 bytes por puntero dando como resultado 2.6 Gb. Pero no todos los nodos cuentan con almentos 20, se puede ahorrar memoria al usar listas enlazadas a sus hijos.

Esto da a un total de 30,000,000 nodos x 4 bytes por nodo x 4 bytes por puntero dando resultado a 480 Mb.

Fuente:
http://www.aaai.org/Papers/ISMB/2000/ISMB00-013.pdf

[VISIÓN COMPUTACIONAL] Lab 4: Diagonales

Siguiendo la entrada anterior sobre detección de lineas, esta vez haré lo mismo pero sobre diagonales. Básicamente lo que le decía al programa era que si encontraba una linea a 0º o a 90º, las pintara en colores distintos. Ahora el programa busca todas las lineas y separa las diagonales de las rectas.

En lugar de solo buscar diferencias en los gradientes, ahora utilizo la función arctan de python (math.atan) que dependiendo de los gradientes x o y se emplea de una o de otra manera.

La imagen de prueba la creé utilizando paint online usando lineas negras.

Para poder trabajar con la imagen, primero le apliqué un fondo rojo, las diagonales las pinté en blanco y las rectas en negro, aunque las lineas ya son negras solo detectaré el contorno de ellas.

La imagen queda de la siguiente mantera:

Se puede observar como las diagonales no son perfectas, esto es debido a que en realidad las diagonales son secuencias de lineas horizontales o verticales apiladas.

Ahora hay que separar las lineas, debido a que por ahora no sabemos si se trata de segmentos separados.

Para eso se utiliza BFS que ya había utilizado en entregas anteriores, con la ayuda de un poco de dilatación. El resultado es el siguiente:

Despues de eso solo pinté en la imagen original los pixeles pertenecientes al contorno de cada linea que estan en la imagen modificada:

El programa no detecta las lineas en si, sino que detecta el borde de ellas, ya que técnicamente una linea recta es un rectángulo de un pixel de grosor. por lo tanto hay 4 lineas que detectar. Para las diagonales es distinto, ya que el BFS las une, aún así se logran pintar los bordes de distinto color.

Código:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[REDES DE TELECOMUNICACIONES] Resumen NS-2 (Network Simulator)

Usando el Simulador de Redes NS-2 para Evaluar la Red en Chips (NoC)

Muhammad Ali, Michael Welzl, Awais Adnan, Farrukh Nadeem

1. Introducción:

En estos días, la tecnología de los chips ha llegado a un nivel en el que sistemas completos pueden ser integrados en ellos, son arquitecturas con diseños llamados VLSI (Very-large-scale integration). Estos chips son llamados SoC (System on a Chip) primariamente usados en sistemas integrados.

De acuerdo con la ITRS (International Technology Roadmap for Semiconductors) antes del fin de la década, los chips serán diseñados con millones de transistores. En el futuro cercano los chips serán de Circuitos Integrados para Aplicaciones Especificas (ASIC) que comprometerán miles de componentes heterogeneos integrados todos juntos para proveer funcionalidad completa a una aplicación.

Sin embargo, desarrollar estos chips no es una tarea fácil, debido a que el numero de transistores crece por chip, integran una gran complejidad.

La idea es conectar diferentes recursos en un chip a través de una red donde la comunicación toma lugar en lugar de conectar recursos usando cables dedicados.

NS-2 es un simulador open source orientado a objetos y eventos discretos, escrito en C++ y PTcl. Es una herramienta muy usada para simular pequeñas y grandes redes Debido a que los chips NoC presentan muchas similitudes con las redes, NS-2 ha sido de elección para simular redes NoC.

2. Network on a Chip (NoC)

NoC ha sido una propuesta alternativa viable para los buses ineficientes de los SoC's de hoy en dia. Los NoC son vistos como una colección de recursos computacionales conectados a través de una red donde se comunican usando paquetes. Muchas topologías se han `propuesto para los NoC's incluyendo ""D mesh", "fat tree", "honeycomb".

Debido a que NoC está compuesto por diferentes marcas con sus propias propiedades intelectuales, una interface de red (NI) para este tipo de infraestructura necesita actuar como una capa media que transforme flujos de datos de los recursos en paquetes antes de ser enviados al "router" y viceversa. Cuando un recurso necesita enviar algo, inicia transmitiendo la información al NI, que crea los paquetes de tamaños predefinidos. Los routers verifican las direcciones de destino y envían el paquete de acuerdo a esos datos.

3. NoC's y Redes: Similitudes

Es difícil mantener la sincronia global con varios componentes en un chip usando un solo reloj. Para eso, se utilizarán GALS (Globally Asynchronous Local Synchronous) que son modelos de reloj para realizar comunicaciones entre componentes.

Antes de empezar en el desafio, se propone un protocolo de 5 capas para gobernar la comunicación en un NoC, en comparación con el modelo OSI.

Las características de los NoC están influenciadas por las redes computacionales.

Los autores han realizado simulaciones con NS-2 y "chpsim" para varias topologías y patrones de trafico. Su argumento está basado en el hecho de que dibido a la escalabilidad de los chips, los SOC's son asíncronos, y por lo tanto operaciones "on-chip" pueden ser de eventos direccionados en lugar de controlados por una sola señal de reloj.

4. NoC's y Redes: Diferencias

La diferencia primaria entre redes y los NoC's es el tamaño. Las redes pueden alcanzar un tamaño desde un pequeño cuarto hasta una ciudad entera, además de el mundo entero (internet). Los NoC's son de unos 50 a 60 nanómetros hechos de silicón Lo que da pequeños problemas, por ejemplo, un buffer tiene que ser de tamaño limitado en estos chips

Mientras que las redes pueden llegar a consumir grandes cantidades de energía, los chips solo podrían consumir pequeñas cantidades de energía.

5. Simulando NoC's con NS-2

Un diseño de SoC involucra tres estados; Diseño de comportamiento, Diseño estructural, Diseño físico.

El diseño de comportamiento especifica la funcionalidad de el sistema a un alto nivel de abstracción, mientras que el diseño estructural y el diseño físico reduce la misma a un nivel de "compuertas lógicas" y nivel de transistores.

En el diseño de comportamiento, un SoC está realizado como una colección de componentes que son modelados como bloques y conexiones junto con los protocolos que gobiernan la comunicación.

6. Limitacones

Mientras que NS-2 es mejor para simular un NoC a nivel de comportamiento, no es posible obtener una vista del diseño estructural y físico.

Sin embargo existe software como VHDL que se ha utilizado para sintetizar chips y hacer casos de estudio de estos a un nivel de compuertas lógicas.

Este modelo aún esta en experimentación y cada vez hay mas propuestas para protocolos de comunicación a este nivel. Por ahora solo queda seguir con las simulaciones y perfeccionarlas.

Fuente:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4136934

[VISIÓN COMPUTACIONAL] Detección de lineas

Para esta tarea, se encargó realizar detección de lineas horizontales y verticales. Para los ejemplos utilizaré las siguientes imagenes.

Primero que nada, calcularemos los gradientes horizontal y vertical por separado para cada imagen. Esto se hace utilizando alguna mascara de convolución para bordes. Se utiliza tanto su forma horizontal como su forma vertical por que de ahí se sacaran las lineas.

Una vez teniendo los gradientes, se calcula el ángulo para cada pixel en cada gradiente. Si gx = 0 y gy = 0, entonces no se toma el ángulo. Si gx = 0 y gy = 255, entonces el ángulo es 90º. Si gx = 255 y gy = 0, entonces el ángulo es 0º.

Con esas condiciones podemos obtener las lineas horizontales y verticales.

Para ello es necesario calcular rho:

Este se guarda en un diccionario junto con un valor para cada pixel, si el pixel es igual al anterior, su rho será aparentemente igual. por lo tanto se trata de una posible linea.

Los resultados son los siguientes:

Código:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[REDES DE TELECOMUNICACIONES] Calidad de servicio de YouTube

Para esta entrada haré algunas pruebas de calidad de servicio a YouTube. Las pruebas son:

• Retardo.
• Perdida de paquetes.
• Jitter. 
• Ancho de banda.

Las pruebas consisten en analizar el comportamiento de los datos para 4 calidades de video de YouTube; 360p, 480p, 720p y 1080p. Las ultimas 2 pruebas (Jitter y Ancho de banda) las realizaré en forma general para un video en 480p ya que Wireshark no responde bien mientras se reproduce un video en HD.

Retardo:

Para esto utilizaré Wiresharck y capturaré los paquetes que corresponden al video.

Obtengo la información de tiempo, mi referencia es el "Epoch Time" que es el momento en que nació el paquete, solo tomaré las décimas, y se lo restare a las décimas del "Time since reference or first frame" que es la hora de llegada del paquete.

Después de promediar varios paquetes el retardo aproximado promedio es de 0.05 segundos entre paquetes al reproducir un video a 360p.

Ahora haré el de cada calidad de video:

360p:    0.05s
480p:    0.055s
720p:    0.07s
1080p:  0.06s

Los retardos se mantienen en un mismo rango para las 4 calidades de video.

Pérdida de paquetes:

Esta vez utilizaré la herramienta IO Graph para los paquetes recibidos con el filtro para analizar la perdida de paquetes "tcp.analysis.lost_segment".

Al reproducir un video en 360p este fue el resultado de la gráfica:

De izquierda a derecha se inicia la descarga y se detiene la misma, cabe destacar que durante algunas subidas de perdida de paquetes el video dejaba de hacer buffering.

Al reproducir un video a 480p:

Aunque esta vez se reprodujo un video de menor tiempo, se puede notar que las subidas son mayores. Los efectos de buffering son igual de aplicables, pausándose en algunas subidas.

Al reproducir un video a 720p:

Aunque no parece una perdida diferente a las demás, debo destacar que solo se muestra lo equivalente a   7 segundos de reproducción de video en 720p, mientras que en los demás logré reproducir al menos 1 minuto. El buffering se pausaba a cada momento durante la prueba.

Al reproducir un video a 1080p:

Sin palabras, después de eso Wireshark no respondió. El video nunca cargó.

Jitter:

Utilizando una de las gráficas de Wireshark pude analizar el jittering de un video, la pregunta es, ¿realmente hay jittering?

La gráfica es la siguiente:

Durante una descarga de un video, se capturo lo que se ve en la imagen. Es interesante ver como los primeros 4 segundos los paquetes llegaron (quizá con perdidas) agrupados uno detrás de otro. Pero a partir del segundo 5 los paquetes empezaron a agruparse. Cada punto contiene varios paquetes. Mi teoría es que las zonas vacías donde pudiera haber paquetes no hubo recepción debido al jittering. La recepción del paquete falla debido a que la lectura se realiza entre la llegada de un nuevo paquete y la salida del anterior.

Ancho de banda:

YouTube tiene una herramiente basica para la medición de mi ancho de banda, al dar click derecho sobre el video y seleccionar "Realizar prueba de velocidad" me dará información sore mi ancho de banda y otros datos interesantes.

Mi ancho de banda me permite reproducir cualquier video con una velocidad de descarga de 5.46 Mbps, es algo raro ver que el nivel mundial está por encima de los niveles locales, y ver mi gráfica (en negro) me hace pensar que la calidad de servicio con mi actual compañía proveedora de internet deja demaciado que desear.

Por último mencionar que todas las pruebas se hicieron con videos distintos, muchos de los resultados pueden variar en función al formato original del video.

Fuentes:

http://wiki.wireshark.org/

http://en.wikipedia.org/wiki/Quality_of_service

[REDES DE TELECOMUNICACIONES] Lab 4: Calidad de servicio (QoS)

Para este laboratorio mencionaré algunas medidas QoS. QoS o Calidad de servicio (Quality of Service, en inglés) es la capacidad de dar un buen servicio. Es especialmente importante para ciertas aplicaciones tales como la transmisión de vídeo o voz.

Muchas cosas le ocurren a los paquetes desde su origen al destino, resultando los siguientes problemas vistos desde el punto de vista del transmisor y receptor:

Retardos:

Los retardos son causa de demoras en el tiempo de transmisión y procesamiento de la información además del tiempo de ejecución y procesamiento de las aplicaciones que usan los usuarios.

Este parámetro es también conocido en el ámbito de las telecomunicaciones como latencia. La causa de este retardo es que cuando la información es procesada esta fluye a través de una gran cantidad de componentes y subsistemas de comunicación, situados en el sistema receptor así como en la red. Cada uno de esos componentes pueden ser caracterizados por su velocidad de procesamiento y por la capacidad de almacenamiento (buffers) donde los datos esperan para ser procesados.

La suma de todas las contribuciones de retardos individuales vista como un todo es lo que genera el parámetro reconocido como retardo. El máximo retardo que es el que ocurre de extremo a extremo conocido como mouth-to-ear (de boca a oído) recomendado para conversaciones en tiempo real no debe exceder los 150 ms. Los retardos impactan en el tiempo en que el usuario debe esperar para establecer la conexión y, una vez establecida, en las demoras temporales de la comunicación misma.

Pérdida de paquetes:

La perdida de paquetes ocurre cuando uno o mas paquetes de datos que viajan en una red IP fallan en alcanzar su destino. La causa de la perdida de paquetes es debida varios factores, entre los que se puede nombrar, degradación de la señal al viajar por el medio, interconexiones de la red sobresaturadas, paquetes con error rechazados en el transito, falla en el hardware de la red, o rutinas normales de enrutamiento.

Cuando la perdida de paquetes es causada por problemas en la red, los paquetes perdidos pueden resultar en problemas de desempeño que causen fallas notables en el desempeño de la red, sin embargo la perdida de paquetes no siempre es tan dañina, como por ejemplo cuando es usada para contrarrestar la latencia.

Se considera que la pérdida de paquetes de entre un 5% y un 10% del total de flujo de datos llega a ser percetible.

Cuando existen condiciones de red de cuello de botella, se deben descartar paquetes. Para esto, los protocolos de red como TCP tienen un control de congestion conocido como slow start, en que se evita que el emisor de la información reenvie aquellos paquetes que no fueron recepcionados para no colapsar la red sino hasta un cierto periodo.

Jitter:

El retardo por jitter o simplemente jitter es usualmente definida como la variación en el tiempo de llegada al punto receptor, sufrida entre paquetes de datos sucesivos. Los paquetes deberían llegar igualmente espaciados entre si para permitir una conversión trasparente. La medición del jitter se
realiza en segundos y expresa la distorsión que ocurre en el patrón original de datos enviados, o dicho de otra manera la degradación que ocurre en tiempo sobre la calidad de data. El jitter solo tiene sentido cuando es medido a un set de datos y no a datos individuales.

Una de las soluciones más típicas es considerar un buffer en la recepción de manera de dar una ventana más amplia al tiempo de recepción y poder ordenar los paquetes que no han llegado en el orden normal. La única desventaja es que agrega un retardo adicional al inicio y durante la operación de un servicio de  videos mientras que la rapidez de reproducción de video sea menor a la tasa de los datos que están siendo descargados.

Ancho de banda:

El ancho de banda es la cantidad de información o de datos que se puede enviar a través de una conexión de red en un período dado. El ancho de banda se indica generalmente en bits por segundo (bps), kilobits por segundo (Kbps), o megabits por segundo (Mbps).

Significa el rango neto de bits o la máxima salida de una huella de comunicación lógico o físico en un sistema de comunicación digital. La razón de este uso es que el rango máximo de tranferencia de datos de un enlace físico de comunicación es proporcional a su ancho de banda.

Fuentes:

http://saber.ucv.ve/jspui/bitstream/123456789/731/3/Anexo%202.pdf
http://www.tesis.uchile.cl/bitstream/handle/2250/111980/cf-segura_cv.pdf?sequence=1
http://en.wikipedia.org/wiki/Quality_of_service

[CÓMPUTO UBICUO] Lab 4: Recomendaciones y comentarios

Automóvil Seguro

• Algo que ya se mencionó durante la clase y de menor importancia, es el uso de "radio buttons" en lugar de "checkboxes" para las encuestas, que aunque no influya en gran medida en el proyecto, quizá algunos de los datos tengan más de una opción señalada.
• No seleccionaron las preguntas "obligatorias" tal cual, si bien muchas de las preguntas "opcionales" parecen de mayor o igual importancia.
• Entrando a lo que es el proyecto, muchas de las características que mencionan como posibles adiciones, podrian encajar perfectamente en el mismo proyecto, como la forma de controlar la alarma; las opciones son vía móvil, vía internet, vía control remoto, cuando en realidad controlar la alarma remotamente vía internet a través del móvil es posible.
• En si hay poca planeación, sus conclusiones solo muestran una especie de idea general de lo que recolectaron de los usuarios, y no una idea de lo que ahora harán en base a esos resultados.

Seguridad en Computadora

• La encuesta está a un nivel de lenguaje un poco elevado para un usuario común, podría causar un poco de confusión al encuestado y hacer a que responda solo por responder. Quizá enfocar las preguntas un poco más al proyecto.
• No muestran gráficos muy detallados, solo muestran unos cuantos, quizá debieron mostrar gráficos para preguntas de importancia mayor como el inicio de sesión ideal o problemas frecuentes de privacidad.
• El proyecto suena muy bien, pero hablan de una aplicación grande, es decir, abarcan cuestiones de seguridad y de entretenimiento, la idea no es mala, pero si podrían dividir un poco cada cosa. Además tiene mucho potencial no solo para esas cuestiones, facilmente se podría hablar de cosas como autentificación en sitios web, cajeros automáticos, etc.

Oficina Personalizada

• La parte de la encuesta me parece muy buena, se cubrieron varios aspectos de lo que pretenden hacer, sin embargo no concluyen, o al menos no recuerdo unas palabras acerca de lo que ahora implementarán como siguiente paso.
• Lo de las luces automáticas son cosas que ya existen y son ampliamente personalizables, cosa que les ahorraría mucho trabajo, sin embargo imagino que harán su propia versión. Deben de tomar en cuenta cosas como ahorro energético, ya que la luz de los focos es lo que generalmente gasta más energía. Se les sugiere utilizar energía renobable, pues utilizar un sistema de recarga solar no es mala idea (Claro está que hablamos de una versión a escala por ahora).

Localizador

• Como se mencionó en clase, creo que utilizan un lenguaje un poco elevado para un usuario común, y eso causaría confusiones. Sin embargo logran entenderse.
• La idea creo que es mejor que la enfoquen a alguna aplicación móvil, ya que es igual de fiable. Imaginando un escenario, una persona prefiere comprar un smartphone a cada uno de los de su familia, ya que ofrece mucho más, y existen API's que ayudarían mucho en este proyecto. Google Code ofrece la mayoría de lo que necesitan si deciden ir por el rumbo de smartphone.
• Si deciden irse por el rumbo de un dispositivo de localización, aun así pueden integrar servicios como Twitter y Facebook para estar más en contacto.

Galería Inteligente

• Una idea muy buena pero la opinión de sus encuestados no es lo que esperaba (en especial por lo de los dinosaurios). Creo que la encuesta debió ser a personas que están más en contacto con estos lugares. No estoy seguro si fue así, pero se debió encuestar a gente que trabaja en los museos o a personas que salen de ellos.
• La idea de interacción con el smartphone ya existe, pero es muy básica, en mi opinión pueden hacer algo mejor de los que ya lo intentaron. Además no solo dar soporte a un museo o galería en específico, sino tratar de "vender" el producto a varios museos.

Cama Inteligente

• Todo está bien, pero pienso que si tuviera algo así en días que estoy enfermo entonces sufriría unos minutos. Imagino que planean alguna clase de panel de control que diera la opción de suspender la alarma por las próximas horas y que al finalizar el tiempo pregunte al usuario si desea reanudar o suspender por otro periodo de tiempo.

Casa Inteligente

• La idea del simulador de presencia es excelente y algo inesperado, la verdad nunca había pensado en algo parecido, quizá la idea existía pero nunca la he visto en marcha. Tomen en cuenta cosas como ahorro energético si continúan con esa idea.
• Deberían tener en mente implementar un panel de control en linea para ver el estado de las cerraduras, por si al usuario se le olvida.

CarNXP

• Solo en cuanto a la perdida de dispositivo, seria fatal que descubrieran el uso del smartphone. Creo que se debería de contar con un sistema de apagado. Es decir, que en caso de perder el smartphone llave, acceder vía internet a la configuración y dar de baja el dispositivo, de esa manera permitir utilizar el vehículo sin el dispositivo, mas que con su propia llave de fábrica.

[VISIÓN COMPUTACIONAL] Lab 3: Convex hull y engordando pixeles

Para esta semana en el laboratorio de visión computacional, de la mano de la tarea de clase que fue búsqueda de formas, tenemos que hacer una covertura a esas mismas. Para ello se realizó una pequeña rutina que hace convex hull usando el algoritmo "Gift Wrapping" tambien llamado "Jarvis March".

El algoritmo consiste en tomar un punto en la izquierda de la forma ya detectada (no necesariamente, pero recomendable), este será el primer punto de la envoltura, despues se hace girar la envoltura para buscar al siguiente punto.

Para terminar los giros se completan los 360 grados, de esta manera quedará comletamente envuelta.

Código:
Las siguientes imagenes muestran el proceso:

Imagen original

Binarización

Convex hull

Una imagen más:

Imagen original

Binarización

Normalización

Convex Hull

Se puede apreciar que esta imagen no tenía los bordes definidos, así que apliqué la normalización, sin embargo los bordes quedan no muy bien marcados, así que apliqué anchura a los pixeles del borde.

El proceso es facil, solo se recorre la imagen y se busca los bordes de un color, al pixel que tenga el color deseado, tomaremos sus vecinos diagonales y los pintaremos del mismo color. El resultado es una imagen con mejor definición de bordes.

De esta manera, antes la imagen de las figuras estaba así:

Original

Sin bordes definidos, se pierden con los filtros

Ahora está así:

Código:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[TEORÍA DE LA INFORMACIÓN] String Matching

Para esta entrada se encargó analizar los algoritmos de "String matching" vistos en clase, estos son el algorimo de Boyer-Moore y el algoritmo de Knuth-Morris-Pratt, yo no alcancé a implementar el algoritmo Boyer-Moore por lo que utilicé en su lugar el algoritmo de fuerza bruta (comparar caracter por carácter) para comparar con el de Knuth-Morris-Pratt.

Boyer-Moore:

Éste algoritmo es un eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica. El algoritmo preprocesa la cadena objetivo que está siendo buscada, pero no en la cadena en que se busca.

El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos.

Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida.

Su principal característica es que su búsqueda la realiza de derecha a izquierda, de esta manera se sabe que si no coincide la última letra, entonces no hay por que comparar el resto, lo que ahorra tiempo.

Antes de iniciar con la búsqueda, se preprocesa una tabla llamada "bad character" que contiene las posiciones que hay que saltar para determinado caracter.

El tiempo promedio para este algoritmo es de O(n log(m/n)), pero en el peor caso genera un tiempo de O(mn).

Lógica:

• Al no haber coincidencia, el carácter del texto se compara con el patrón de búsqueda para determinar el salto hacia la derecha.
• Si el carácter no existe en el patrón de búsqueda se salta la cadena completa.
• Si tras varias coincidencias no se acertó, se salta en función de la repetición de patrones en la secuencia de búsqueda, y se alinea de nuevo usando ese valor.
• Se toma como salto el mayor de los dos valores.

Ejemplo:

Knuth-Morris-Pratt:

KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí , para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.

Con KPM se pre-calcula una tabla donde se localizan las posibles coincidencias de patrón. Una vez calculadas, se procede a tomar la primera celda de la tabla. Si el caracter coincide se procede con el siguiente, si no, el algoritmo se corta y busca la siguiente posible posición. 

Debido a que el algoritmo consta de 2 partes donde se analiza una cadena en cada parte, la complejidad resultante es O(m) y O(n), cuya suma resulta ser O(m+n).

Mi código es el siguiente:

Al correrlo me da como resultado lo siguiente:

La imagen muestra que son 1000 caracteres los que se generan aleatoriamente, despues se muestra la tabla de posibles coincidencias, al final muestra el total de caracteres y el tiempo de ejecución ademas de la unica coincidencia en la posición 717.

Analicé esto con gnuplot, haciendo correr el programa varias veces e imprimiendo los resultados en un archivo.

El resultado es:

Vemos por el eje Y que casi alcanzaba los 0.0004 segundos de ejecución por texto.

Por ultimo tambien decidí realizar un analisis del algoritmo fuerza bruta que compara caracter por caracter. La complejidad del algoritmo es O(m) ya que solo opera en una sola corrida.

El código es el siguiente:
Utilicé el mismo scripto para correrlo varias veces e imprimirlo a un archivo de texto, el resultado es el siguiente:

Se puede ver que para este, el máximo tiempo estuvo cerca de 0.0018 segundos. A diferencia del anterior, se puedenotar que crece más rapido.

La comparativa entre las 2:

El script que corre el algoritmo es el siguiente:
El script de gnuplot, al ser un ploteo sencillo, es el que sigue:

plot "Bruteforce.txt" with lines, "KMP.txt" with lines

Liga al proyecto:

https://github.com/victoralex911/teoria-informacion

Fuentes:
https://sites.google.com/site/busquedasecuencialdetexto/algoritmo-boyer-moore
http://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt
http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore

[CÓMPUTO UBICUO] Lab 3: Técnicas de diseño conceptual

Diseño conceptual

Cuando se trabaja bajo el análisis conceptual de una situación, nos referimos a la abstracción de hechos reales de los cuales se emite un concepto o es posible hacer una idea de ello. Para ello se necesitan requerimientos previamente formulados por los usuarios. Con estos se puede iniciar a la creación de un esquema conceptual con el cual se podrá realzar una descripión de alto nivel. Para manipular el esquema se utiliza un modelo conceptual que proporciona un conjunto de símbolos (estándares) para su creación.

Algunas fases del diseño conceptual y sus características son:

Teorías/especulación: Para algunas personas, diseño conceptual no es mas que la fabricación de prototipos, y eventualmente se convertirán en productos o bien solo un diseño futurista que no es práctico.

Significancia: El diseño conceptual es solo la primera fase de un diseño donde los dibujos son el foco principal, que se componen de planos y secciones simples.

Características: Fases específicas, o pasos, del diseño conceptual que son necesarias para transferir las ideas hacia los requisitos. Incluyen una descripción o definición general del concepto

Tipos de conceptos:

• Textuales: Descripción de la idea del producto que generalmente consiste en la descripción de lo que uno puede hacer con la idea del producto.
• Pictográficos: Son representaciones visuales de la idea general del uso del producto. Dependiendo del producto, estas son simples o complejas en cuanto al tipo de uso o la idea del producto.
• Animaciones: Un concepto nuevo que consiste en recrear la idea del uso del producto mediante el uso de animaciones. Generalmente un video también encaja en este tipo de concepto, ya que muestra literalmente como se usa tal producto.
• Mock-ups: son un tipo de prototipo que sólo muestra las características externas de una idea de producto.

Diseño contextual

Es un metodo de diseño centrado en el usuario que permite entender mejor el entorno donde se trabaja y las necesidades que se tienen que cumplir los sistemas interactivos que para ellos se desarrollan.

H. BEYER y K. HOLTZBLATT son los máximos exponentes del diseño contextual, describen el proceso que guía a los equipos de diseño en el mencionado conocimiento y comprensión para rediseñar el trabajo de las personas mediante la ayuda de nuevos sistemas software.

El proceso incorpora una gran cantidad de técnicas centradas en el usuario en un proceso de diseño integado que se dividen en seis partes diferentes:

• Integración contextual: Revela detalles y motivaciones implicitas en el trabajo de las personas, hace del cliente y su trabajo necesidades reales de los diseñadores y crea un conocimiento compartido para el equipo.
• Modelado de trabajo: Proporciona un lenguaje para hablar sobre el trabajo a compartir por los equipos y por medio de una serie de modelos se representa el trabajo de los clientes que ayudan a analizar los datos recogidos. Los modelos son:
• El modelo de Flujo define cómo se divide el trabajo entre varias personas y cómo éstas se coordinan para realizar dicho trabajo.
• El modelo Cultural identifica procesos culturales y políticas de actuación que condiciona el trabajo.
• El modelo de Secuencias muestra detalladamente los pasos seguidos para el seguimiento de las diferentes tareas.
• El modelo Físico representa el entorno físico en el que se realiza el trabajo incluyendo el espacio de trabajo, el posicionamiento de los objetos y como es que todos estos elementos influyen en la forma de trabajo.
• El modelo de Artefactos muestra como se utilizan y estructuran los diferentes objetos durante el transcurso del trabajo.
• Consolidación: Proporciona un mapa de la población de los clientes o usuarios, facilita la identficación de las necesidades del cliente mostrando la estructura organizacional que utilizan los usuarios mientras realizan su trabajo.
• Rediseño del trabajo: Orienta al equipo para mejorar el trabajo evitando que este se "deje llevar" por la tecnología.
• Diseño del Entorno del Usuario: Mantiene la coherencia del sistema desde el punto de vista del usuario capturando la estructura, la funcionalidad y el flujo del sistema. A su vez orienta al equipo de diseño en el uso del sistema y no tanto en la interfaz de usuario o en la implementación. 
• Maquetas y tests con clientes: Las principales virtudes de esta parte son que permite determinar errores en el nuevo diseño incluso antes de empezar con la codificación a la vez que crea el clima necesario para que los usuarios se involucren en el diseño del sistema como si de unos socios tecnológicos se tratara.

[VISIÓN COMPUTACIONAL] Detección de formas

La tarea para esta semana fue realizar un programa que detecte las formas dentro de una imagen, las etiquete y muestre su centro de masa.

Para eso, lo primero que necesitabamos saber era poder pintar una serie de pixeles que fueran del mismo color dentro de un área. Yo utilicé el método BFS (Breadth-first search) o al menos algo parecido que realizara la misma función.

Desarrollé la siguiente función:
Los resultados son lo s siguientes:

Imagen original

Imagen con una sección coloreada

Imagen con otra sección coloreada

El siguiente paso era hacer lo mismo pero para cada forma en la imagen. Los resultados fueron los siguientes:

Con esto ahora podría técnicamente saber el número de pixeles en la forma, por lo tanto saber cuantas formas existen en la imagen.

Me di a la tarea de buscar una imagen que mostrara mejor lo que buscaba. Entonces encontré esta imagen:

Y le apliqué el proceso de binarización para que quedara bicolor, descubrí su centro de masa y etiqueté cada objeto en la imagen, el resultado es el siguiente:

El objeto predominante lo pinté en gris para que no hubiera conflictos de color entre las formas.

El código es:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional