Fast String Searching with Suffixes trees

I’ll make a summary about an article of Fast String Searching with suffixes trees posted in August 1 1996 by Mark Nelson in Computer Science, Data Compression, and Magazine Articles.

The article was published in Dr.Dobb’s Journal in August 1996

http://marknelson.us/1996/08/01/suffix-trees/

Problem

The article starts specifying what the problem is; it talks about how programmers face day to day some match string sequence problems, and how improving it will benefit a lot. Then it gives an example of how useful it would be to improve string searching algorithms, imagine that you work as a programmer in a DNA sequence project, researchers will be busy producing fragmented sequences of nucleotides, they send this information to the server and it’s expected to locale the sequences in a database of genomes, as we already know a genome of a specific virus may contain thousands of nucleotides bases and as a server of a DNA research would be full of viruses, if the string searching algorithm is not efficient it would take a lot of time to match with the correct virus. If you use a brute force string search algorithm it would take forever to perform a string comparison at every single nucleotide in every genome in the database. So the problem is how this can be solved.

Intuitive Solution

Building a search trie for searching through input text. A trie is a type of tree that has N possible branches from each node, where N is the number of characters in the alphabet. It’s called suffix because the trie contains all the suffixes of a given block of text, in this case all the viral genome.

Example:

This example shows a suffix trie for the word BANANAS. It gets divided in a starting root node and all of the suffixes of the word BANANAS in this case the suffixes are BANANAS, ANANAS, NANAS and an S. Suffixes trees simplify the job because if you input a text of N length and need to search for a length M string it would just need to compare M to search, in traditional brute force search algorithms it would take a lot of time because it would compare all N*M comparisons available. Suffixes trees are so efficient that if the word BANANAS was in the collected works of Shakespear it would only take 7 character comparisons to find it.

But if they are so efficient why we don’t hear much about there use?

This is because constructing one requires O(N²) time and space.

A solution to this was proposed in 1976 by Edward McCreight when he published a paper on what came to be known as the suffix tree. The difference between suffix tree and suffix trie it’s that the suffix tree eliminate nodes that have a single descendant, meaning that now individual edges in the tree may now represent sequences of text instead of single characters.

In this picture we can see that by using this method we removed 12 nodes meaning that the time and space requeriment for the contruction is also reduced  from O(N²) to O(N).

McCreight’s original algorithm had some disadvantages; one of them was that it required the tree to be built in reverse order meaning characters were added from the end of the input. This makes much more difficult to use for applications of data compression. Then Esko Ukkonen from the Iniversity of Helsinki make some modifications to the McCreight algorithm making it able to work from left to right.

Esko Ukkonen algorithm would work this way:

It starts with an empty tree for a given string of text, it then adds each of the N prefixes in this case B is inserte to the tree then BA then BAN untll its completely inserted and the tree is complete.

Lab 4 Recomendaciones proyectos

Auto Seguro

En este proyecto el equipo propone realizar varias funcionalidades que den mas seguridad en cuanto al auto, mencionaron que querían tener algunas funcionalidades como alarmas, rastreo gps y un localizador del carro en un estacionamiento. Yo propondría que agregaran algo como notificaciones al celular de alarmas ya que algunas veces nos encontramos en lugares como centros comerciales o lugares donde no podemos escuchar la alarma, seria útil que nos avisara de alguna forma aunque no podamos escucharla.

Auto Bloqueo de PC

Este proyecto propone un auto bloqueo de la PC cuando nos alejamos de ella, algo muy útil ya que siempre vemos otra  gente posteando sonsadas en los face de otros por haber dejado la sesión abierta. Algunas ideas que yo les propondría seria en la parte del desbloqueo que fuera por medio de voz o huella digital o algo biometrico.

Localizador de Personas

Este equipo propone un localizador gps de personas por medio de un brazalete rfid, me parece buena idea y recomendaría agregar algunas funcionalidades como algún tipo de alarma si la persona se queda inmóvil mucho tiempo que significaría que la persona se quito el brazalete o se murió o algo así.

Cama Inteligente

En este proyecto se propuso mas que nada funcionalidades de alarma en caso de que alguien se quede dormido, yo lo que propondría es agregar otras funcionalidades como controlar luces del cuarto o cosas por el estilo ya que es molesto estando acostado tener que levantarse, tambien seria bueno algún control de televisión.

Casa Inteligente

Este equipo nos propone lo que es todo una casa inteligente un tema ya bastante conocido entre los de la clase ya que se trabajo en semestres anteriores, lo que yo podria recomendar es revisar lo que se hizo anteriormente y intentar agregar alguna funcionalidad que no se haya trabajado anteriormente.

Garage Inteligente

Para garage inteligente el proyecto en si nos propone una manera de poder abrir nuestra cochera sin utilizar control ademas el equipo propuso generar algunos códigos QR para dar acceso temporal a visitantes si se quisiera, yo creo que se podría trabajar también con RFID ya que en algunas colonias se tiene este sistema para dar acceso a los que viven ahí.

Oficina Personalizada

El proyecto de la oficina personalizada propone como su nombre lo dice tener los detalles del lugar personalizados dependiendo de la persona que este dentro, una buena idea seria la manera que se identificara el cambio de persona si lo harán por medio de alguna llave o algo por el estilo o se podría programar por horas y cada cierta hora activar un perfil y a otra hora que llegue otro tipo otro perfil.

Tarea 3 Deteccion de Lineas

La tarea 3 consiste en realizar un programa capaz de detectar lineas verticales y horizontales, una ves detectadas había que pintar de rojo las horizontales y de azul las verticales.

Para poder trabajar con esto hay que contar con lo que hicimos anteriormente la parte de convolucion(detección de bordes) y binarizacion son importantes sin alguna de estas 2 no se puede avanzar.

Para la detección de lineas lo primero que hay que hacer es con lo utilizado en convolucion obtener los gradientes x,y con la siguiente formula utilizada ya anteriormente en convolucion:

Una ves obtenido los gradientes con la siguiente formula podemos obtener su angulo o dirección:

Con esta formula podemos calcular la dirección del gradiente por medio del método de sobel.

Lo que se busca es obtener resultados como los siguientes:

 Imagen  normalizada con gradiente x obtenida con operador de sobel

 Imagen normalizada con gradiente y obtenido con operador de sobel 

Fuentes:

• Operador Sobel

Lab #3 Vision Convex Hull

Para esta entrada de laboratorio se trabajo con lo que es convex hull, basicamente convex hull es un recubrimiento de contorno de una figura en especifica, existen diversos algoritmos para realizar este proceso en esta entrada hablare de Gift Wrapping algorithm.

El algorithmo gift wrapping tambien conocido como jarvis inicia con i=0 y un punto[0] siendo este el punto mas a la izquierda despues de busca el punto mas cercano a la derecha de la linea siendo este pi+1 esto se repite hasta llegar al fin que es el punto de inicio osea punto[0].

De esta forma quedan los recorridos.

La imagen que utilice fue la siguiente:

El codigo es el siguiente:

La imagen resultante es la siguiente:

Logre que recorra los bordes y si marca todos los puntos que deben de ser el problema es que marca otros que no son y no e encontrado el error y al intentar pintar las lineas se hacen mal los trazos por lo mismo.


Para la generacion del codigo me base de el pseudo-codigo de gift wrapping:

Fuentes:

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

String Searching Algorithms

For this week we had to implement a string searching algorithm to check how efficient it is in terms of time.

The algorithm that i implemented was the Knuth-Morris-Pratt, the KMP algorithm searches for occurrences of a Word "W" meaning the word we have to look within a main "text string" S that contains the word W and some other random characters.

I used this pseudo code to create my code:

This is the code that i did unfortunately it doesn't work, the code doesn't goes trough all the segment so it isn't looking for the word.

Lab 3 Diseño Contextual

Diseño Contextual

El diseño contextual es un diseño centrado en el usuario, incorpora métodos ethnograficos para la obtención de datos relevantes para el producto vía estudio de campo, racionalización de pasos y diseño de interfaz gráfica. En la practica esto significa que los investigadores estudian al consumidor en el campo de su vida diaria y con base a los resultados de dicha investigación se aplican cosas al diseño final. 

 El diseño contextual consta de las siguientes partes: 

•  Investigación contextual o recopilación de datos:  La investigación contextual consiste en recolectar datos y realizar estudios sobre como usuarios interactuan con los productos en el día a día. La parte importante aquí es estudiar la interacción directa y indirectamente con el producto.
• Interpretación: En esta parte se detectan los puntos clave del estudio pasado, a partir de aquí se crean los modelos del trabajo tomando en cuenta los diferentes aspectos que son importantes para el diseño. El modelo consiste de 5 partes:

1. Flujo de modelo: Representa la cordinacion, comunicación,interacion de roles y responsabilidades de cada persona dentro del modelo.
2. Secuencia de modelo: Representa los pasos que el usuario sigue para realizar cierta actividad.
3. Modelo cultural: Representa las normas, influencias y presiones que están presentes dentro del proyecto.
4. Artefacto de modelo: Representa los documentos o otras cosas físicas que son creadas durante el proceso o que son importantes para el apoyo del proyecto.
5. Modelo Físico: Representa el ambiente físico donde los procesos se completan.

Ejemplo de un modelo físico:

Consolidación de datos:

Se realizan entrevistas a diferentes usuarios individualmente se analizan para encontrar respuestas similares o alguna patente. Otra forma de procesar las entrevista y buscar similitudes es realizar un diagrama de afinidad, en un diagrama de afinidad se colocan todas las ideas de manera individual, después se agrupan las ideas parecidas o de contenido parecido, se dividen los grupos por color y cada color representa un nivel diferente de herencia, por ultimo se junta todo para crear la idea final.

Quedan algo parecido a esto:

Conclusión:

En conclusión es un tipo de modelo a seguir que nos puede ser útil para realizar nuestro proyecto, en lo personal ya trabaje con este modelo en las conferencias de IHC se creo un diagrama de afinidad con post-its lo cual sirvió para desinhibir a las personas trabajando en el proyecto ya que todas las ideas se plasman sin saber de quien es cual.

Fuentes:

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

Sistemas Emergentes

En esta entrada se explicara un poco sobre algunas tecnologías emergentes que se relacionan con nuestro proyecto, las mismas fueron sugeridas por los compañeros de clases, y nos ayudaran a darnos una idea de lo que podemos hacer y lo que ya existe en relación al tema de galerías y museos inteligentes.

D-MU Vitrinas inteligentes para Museos

Las vitrinas inteligentes para museos, son como lo dice su nombre vitrinas especiales que sirven en museos y centros de exposición de arte para reducir el deterioro fotoquimico en las obras de arte que son sensibles a la luz, como lo son los libros antiguos, las fotrografias, los cuadros y las esculturas. Su funcionamiento consta de 2 partes una vitrina oscura protectora y un sensor de proximidad que detecta cuando alguien se acerca a la obra. Cuando una persona se acerca a la vitrina, el sensor de proximidad acciona una luz interna regulada la cual hace transparente el vidrio, permitiendo así a la persona ver la obra y esta misma sin el riesgo de dañarse, al momento que la persona se aleja la obra vuelve a oscurecerse.

Un vídeo explicativo del proyecto:

Para mayor información de este proyecto:

Vitrinas Inteligentes

Museo Italiano con RFID

El museo y galería de arte ambrosiana, que esta localizado en Milán -Italia es uno de los primeros museos italianos y una de las mejores galerías de arte en Milán. El propósito de este proyecto es inspirar a los nuevos artistas. El museo en una fuerte y ambiciosa apuesta por la tecnología ha desplegado atraves del lugar tecnología NFC(Near Field Comunication) y etiquetas RFID adheridas a las obras atraves de todo el lugar, con la idea de atraer a mas jóvenes a los museos. La mecánica consiste en ofrecer un mejor servicio y por ahora permite que smarthphones que cuentan con la tecnología NFC puedan scanear los códigos RFID y conocer mas acerca de la obra por medio de su teléfono y ademas poder guardar las obras que mas te hayan gustado.

Para conocer mas sobre este proyecto:

Museo RFID

Galerías Virtuales Inteligentes

Otro proyecto muy interesante realizado en una galería de arte es una galería virtual inteligente, la cual consta de una pantalla táctil en la que se puede interactuar de muchas formas con las obras de arte con el firme propósito de atraes a la gente joven. Lo que hacen estas pantallas táctiles colocadas en varios puntos de la galería es desplegar distintas opciones desde ver información y vídeos sobre las obras que tenemos enfrente, hasta poder estampar nuestra cara en alguna de las esculturas o pinturas por medio de tecnología de detección de rostros, también en esculturas con cierta posición podemos replicar la posición de la escultura y el programa nos dirá que tanta similitud existe entre nuestra postura y la de la escultura  todo esto queda fotografiado y podemos publicarlo en redes sociales o mandarlo a nuestro correo desde la misma galería.

Aquí un vídeo explicativo de la tecnología mencionada:

Avatares Inteligentes

Te as imaginado que un histórico famoso volviera a la vida para contarte sus hazañas? Los museos, galerías y científicos buscan hacer esto posible, se planea mantener mas entretenidos a los visitantes por medio de avatares inteligentes que expliquen el recorrido y estos serian personas famosas o históricas  Los avatares inteligentes consisten de 2 partes un cerebro virtual y una animación holografía atraves de la cual se manifiesta, ademas contaria con una voz la cual nos iría hablando sobre sus hazañas o según sea el caso.

Para mayor información de esta tecnología:

Avatares

Fuentes:

• http://www.chatbots.org/conversational/agent/intelligent_avatars_platform_museums_galleries_science_centers/
• http://www.facebook.com/l.php?u=http%3A%2F%2Fgentedigital.es%2Fcomunidad%2Frodrigoburgos%2F2013%2F01%2F23%2Faplicaciones-tecnologicas-para-museos-en-2013%2F&h=uAQHsbRXp
• http://www.aton.eu/riflessioni/el-museo-de-arte-italiano-milanese-adopta-rfid/es/
• http://www.domoticware.com/es/D-MU_smart_museum_display_cases.php

Sistemas Existentes

En esta entrada hablare un poco de algunos Sistemas Existentes con relación a proyectos que realizaran algunos compañeros estas son solo algunas ideas que yo publique para algunos compañeros.

Face Biometric Login Through Web

El acceso web es algo que a preocupado a los ingenieros desde que se diseñaron sitios donde hay que autentificarse para tener acceso. En los últimos años se a estado trabajando en poder autentificarse atraves del rostro. Como funciona este proyecto? La diferencia de un login normal es que en este caso ademas de hacer login con un usuario y contraseña se añade la seguridad biometrica por lo cual para tener acceso a alguna cuenta se autentificaría al usuario por medio de su rostro. Las ventajas de este sistema es que el usuario puede logear desde cualquier parte del mundo con toda seguridad de que su cuenta no correrá riesgos, no se requiere de algún software adicional, la detección es rápida y confiable.

Video demostrativo:

Mayor información sobre este proyecto:

Face Recognition

Open Your Garage Door

Open your garage door no es un proyecto nuevo y en este caso pertenece a una compañía muy famosa como lo es CRAFTSMAN, esta compañía de motores para cochera aparte de ofrecernos una extensa gama de motores, nos ofrece la una aplicación para nuestro dispositivo movil para evitarnos el tener que cargar con el control de la cochera. Por un costo extra de 20 dolares anuales ademas de 280 dolares por la instalación CRAFTSMAN nos ofrece añadir este servicio a nuestro hogar.

Aquí un video demostrativo:

Para mayor información del servicio:

Open Garage

GPS monitoring products

Para los compañeros que están trabajando con el brazalete con GPS encontré un sitio en donde se vende este producto, solo que embes de ir orientado para gente como mis compañeros lo quieren emplear va enfocado a convictos que son puestos en libertad condición y tienen que ser monitoreados. El sitio ofrece una gran variedad de productos pero todos orientados al mismo publico, todos en forma de esposa la diferencia entre cada uno de ellos son la versatilidad que nos da y la distancia que cubre así como alarmas que suenan si una persona sale de cierto rango.

Para mayor información de este producto:

GPS Monitoring

Fuentes:

• http://www.gpsmonitoring.com/products.html
• http://www.autoguide.com/auto-news/2011/10/open-your-garage-door-with-your-cell-phone-with-the-craftsman-assurelink-video.html
• http://ex-sight.com/webaccess.htm

Deteccion de formas

Para la tarea 2 de la clase de visión se nos pidió realizar un programa el cual detectara formas en una imagen, separadas por sus diferentes bordes, después de realizar esto se pintarían de colores diferentes cada forma y la de mayor tamaño se pintaría de gris, después de hacer esto hay que encontrar el centro de masa de cada forma y colocarle una etiqueta. Explicare cada paso por partes.

Convolucion y Binarizacion

Primero que nada para poder hacer la parte de detección de formas debemos tener hecho la parte de detección de bordes por medio de convolucion y a partir de la imagen que nos genera usar binarizacion.

Como no había hecho anteriormente la parte de binarizacion la explicare aquí para la parte de convolucion ya tengo una entrada que explica eso y el código utilizado para esa parte es el mismo.

• Convolucion

Para realizar la parte de binarizacion es muy sencillo, partiendo de la imagen obtenida de la detección de bordes con convolucion, generamos un valor máximo, recorremos la imagen y sacamos el promedio de cada pixel si su promedio es menor que el valor lo cambiamos a negro si no cumple con esto se hace blanco. De esta manera obtenemos una imagen con los bordes bien definidos con la que podemos trabajar en la detección de formas.

El código que utilice para binarizacion es el siguiente:

Ejemplos

Original

                                 

                                          Convolucion                                    Binarizacion

Original

                   

                                        Convolucion                                      Binarizacion

Como las 2 imágenes anteriores ya tenían sus bordes bien definidos de inicio pondré un 3r ejemplo utilice las anteriores ya que me gusta su resultado final en las figuras ya que desde el inicio tienen formas bien marcadas.

Original

                                 

                                             Bordes                                      Binarizacion

Ya que tenemos bien toda esta parte podemos pasar a la primera parte de detección de formas.

Detección de formas

BFS

Para esta parte partiremos de la imagen obtenida de la binarizacion, lo que haremos aquí es empesar a recorrer la imagen desde el punto 0,0 generamos un color random, creamos una cola en la cual agregaremos el primer valor a checar en este caso 0,0 que se convertirá en nuestro punto de partida después creamos un while que seguirá hasta que la cola este vacía como tenemos actualmente el valor 0,0 se cumple la condición lo primero que haremos dentro de la condición sera eliminar el valor que ya vamos a revisar para no repetirlo y empesaremos a revisar los vecinos en el caso de 0,0 solo tiene 2 uno a su derecha y el otro abajo de igual forma esto lo verificamos con trys que verifica que existan vecinos, una ves que encontramos vecinos revisamos si su valor r,g,b es igual al del punto de partida si es igual se pinta del color generado y se agrega a la cola, esto se hace con todos los vecinos y así vamos revisando todas los vecinos hasta que se encuentre con un borde ya que como binarizamos la imagen cuando encuentre otro valor que no sea negro significara el comienzo de otra forma.

Imagen explicativa:

Código utilizado:

Ejemplos

Partiendo de las imágenes anteriores

Figura de mayor área

Después de haber coloreado la imagen también se nos pidió pintar el fondo de la figura de mayor área de color gris, para esto lo que hice fue crear 2 listas una que en la cual guardare la cantidad de pixeles de cada corrida en la función bfs por ende cada corrida es una figura diferente entonces en cada corrida por medio de un contador sumo la cantidad de pixeles que contiene la figura lo regreso y lo almaceno en la lista contador y de la misma forma regreso el color que contiene esa figura y lo almaceno en la otra lista de esta manera quedara en la misma posición ejemplo:

lista contador[0]=2000

lista color[0]=(0,0,0)

De esta forma de ser el 2000 el valor mas grande en la lista sabre que el color que tengo que repintar de gris es el negro.Una ves que tenemos todas las figuras pintadas, todos los valores almacenados en la lista buscamos el valor mas alto de la cadena contador usando:

máximo =contador.index(max(contador))

en este caso nos regresara a la variable máximo la posición del valor mayor, ya lo único que hacemos es conociendo la posición del máximo sacar el color del cual esta pintado esa parte de la siguiente manera:

 gris=colores[máximo]

Conociendo todo esto solo recorremos la imagen buscando el color de la variable gris en este caso y lo repintamos de color gris.

El código que realice quedo de la siguiente manera:

 

      Primer Resultado                                      Área mayor repintada

               

Obtención de centros y etiquetado

Para obtener los centros de cada figura se hizo algo parecido a lo de obtener el valor mayor, cree 2 listas  en las cuales el bfs me regresara cada valor de i,j que se agreguen a la cola esto para utilizarlos después con una formula para obtener su centro, la cual quedo de la siguiente manera:

centro.append((sum(centro1)/float(len(centro1)),sum(centro2)/float(len(centro2))))

centro1 siendo los valores de i

centro2 los valores de j

La formula la aplique con un try ta que hay casos en fotos que pequeñas manchas 1 solo pixel lo detecta como una figura y causa errores al querer dividir entre 0.

La formula nos almacenara en otra lista los centros de cada figura y después con esto recorremos la cadena y dibujamos un circulo en cada uno de esos puntos para diferenciar los centros. Al mismo tiempo que se dibuja los círculos hay que crear las labels para diferenciar las figuras, esta parte también la hice pero tuve problemas con la ventana al mostrar las labels lo cual aun no eh resuelto y dejo solo las imagenes hasta los puntos.

El código que utilice:

El código completo se encuentra en mi repositorio:

https://github.com/rodo2043/VisionComputacional

Generación de ruido sal pimienta

Para esta semana en laboratorio de visión computacional la tarea consistió en generar ruido sal pimienta sobre una imagen y después buscar la manera de como eliminarlo y aplicarlo.

Generación Ruido Sal-Pimienta

Para generar el ruido sal-pimienta lo primero que hice fue pedir un valor que sera tomado como intensidad donde podemos poner el valor que sea lo recomendado es usar valores entre 0 y 1 ya que 1 recorrerá todo el tamaño del ancho x alto de la imagen, esto no significa que habrá ruido en toda la imagen porque no se va insertando pixel por pixel pero si habrá una cantidad muy alta. Después generamos un valor x random que se le sumara al pixel actual que se recorre por lo que se moverá a un pixel random el cual sera el pintado. Para decidir si pintarlo blanco o negro nos basamos en el mismo valor random generado, si el valor generado x es modulo de 2 sera blanco sino sera negro.

Imagen Explicativa:

Imágenes Resultante:

 

                    Original                                              Sal-Pimienta intensidad:0.1

Otro ejemplo:

Imagen Original

 Sal-Pimienta intensidad:1

El código que cree para generar el ruido es el siguiente:

Remover Ruido Sal-Pimienta

La segunda parte de la tarea consiste en remover el ruido generado anteriormente para esto yo decidí hacer 2 cosas, primero que nada decidí recorrer la imagen en búsqueda de un pixel con sal o pimienta es decir blanco o negro, una ves encontrado un pixel que cumpla esta condición lo que hice fue revisar sus vecinos para generar un promedio, para generar el promedio revisamos todos los vecinos alrededor y tomamos en cuenta para el promedio solo los vecinos que no contengan sal y pimienta, es decir que si en el pixel que estamos actualmente su vecino derecho contiene sal y pimienta y los demás no, el promedio sera el valor del pixel izq+pixel abajo+pixel arriba dividido entre 3 y sera el valor que obtenga el pixel actual que contenía anteriormente ruido.

Imagen Explicativa:

Imágenes Resultantes:

          Ruido intensidad: 0.1                                                   Primer removidoRuido Intensidad 1

Primer removido

El código que cree para la eliminación del ruido es el siguiente:

Como se puede ver en las imágenes el ruido no se elimina completamente así que para eliminarlo en su totalidad decidí pasar la imagen resultante del primer removido por el filtro que había hecho anteriormente y me quedo de la siguiente manera:

Segundo Filtro:

          Ruido 0.1                                                       Primer Filtro                             

                                                 Segundo Filtro

Ruido intensidad 1 

Primer Filtro 

 Segundo Filtro

El código que utilice es el siguiente:

Como se puede ver ya con el segundo filtro se elimina prácticamente toda la sal pimienta, el segundo filtro es igual al que ya había utilizado en la clase.

Tiempos:

Primera Imagen:

Segunda Imagen:

El código completo se encuentra en mi repositorio:

https://github.com/rodo2043/VisionComputacional

Eso seria todo para esta semana :P