jueves, 7 de marzo de 2013

Laboratorio 5-Detección de círculos de diferentes tamaños


Para esta semana se nos pidió realizar un programa capaz de detectar círculos de diferentes tamaños a partir de una imagen.

Lo que utilice para realiza esto es a partir de lo realizado en clase ver entrada:

http://m8sem.blogspot.mx/2013/03/deteccion-de-circulos.html

Partiendo de este código que ya detectaba los círculos simplemente elimine el error que se marcaban los centros de otras figuras que no eran círculos.

Como ya lo había mencionado en la entrada de clase, los círculos detectados serán pintados de Azul y su centro sera marcado.

Para confirmar que sea un circulo obtendremos el radio y su área.




Ejemplo:







Obteniendo la distancia entre el punto de partida y el centro obtenemos el radio.


Código:



martes, 5 de marzo de 2013

Laboratorio 5 -Catalogo

Para esta semana se nos pidió elaborar un catalogo que contenga el material a utilizar así como el sitio donde lo podemos conseguir, al igual que el software.

Arduino UNO:

http://www.5hz-electronica.com/

En 5hz podemos encontrar desde Arduino UNO hasta mega cuentan con los diferentes tipos de Arduino y en caso de no existir stock se puede realizar el pedido.




Sensor de Proximidad:

http://www.seeedstudio.com/

En seedstudio tienda estadounidense podemos encontrar
diferentes tipos de sensores de proximidad el que
nosotros usaríamos seria algo como el de la imagen, el cual
es un sensor de proximidad infrarrojo de 80cm, esta no es la
única opción existen diferentes tipos de sensores como
ultrasonido entre otros.


Bocina/buzzer:



http://www.steren.com.mx/

En steren podemos encontrar diferentes tipos de buzzers,
diferentes potencias tonos,variaciones y velocidades.


Foco interno

http://www.steren.com.mx/

Al igual que el buzzer en esteren podemos conseguir una gran cantidad de focos de diferente intensidad y tipo en este caso el mas apropiado para nosotros seria el foco de kripton 2.2volts




Software

En cuanto a software se trabajaría con el ide de Arduino el cual podemos obtener de la siguiente pagina:
http://www.arduino.cc/

Detección de círculos

Para esta semana la actividad consistió en realizar un programa capaz de identificar círculos a partir de una imagen.


Lo que utilice para realizar esto fue partiendo de lo que ya se tenia de detección de figuras y centros:
por lo que para poder realizarlo se tiene que contar con todo lo que se necesita para detección de figuras- formas ver esta entrada:http://m8sem.blogspot.mx/2013/02/clase-2-deteccion-de-formas.html


Partiendo de esto para no estar buscando los centros de nuevo una ves que se obtiene el centro de una figura lo que hago es lo siguiente:

Envió en una función llamada círculos el valor inicial en el cual se detecto la figura, este valor es donde se recorre toda la imagen y se encuentra un pixel blanco dando a entender que inicia una nueva figura,el centro de dicha figura obtenido con una formula ya empleada en la entrada anterior,la cantidad de pixeles que conforma la figura en este caso representara el área de la figura y por ultimo el color que tiene actualmente la figura, esto en dado caso de que si sea un circulo re-pintarlo de color azul para marcarlo.

Con todo esto podemos hacer uno de algunas formulas para confirmar si la figura es o no un circulo

Formulas a utilizar:


La formula para obtener el área de un circulo, para poder utilizar esta formula necesitamos el radio.

Para obtener el radio utilizaremos la formula de distancia:

Con la formula de distancia podremos obtener el radio ya que tenemos 2 puntos el punto de inicio donde se detecto una nueva figura y el punto donde se ubica el centro, estos serán nuestros valores de (x1,x2)(y1,y2).

Una ves que obtenemos el radio podemos utilizar la formula del área de un circulo con pi*r^2 el resultado nos dará el área de la figura que en caso de coincidir con el área en cantidad de pixeles que ya tenemos(puede haber una variación mínima de pocas décimas) podremos saber si la figura es un circulo.

Ejemplos:

Imagen original:
Circulo detectado:
Corrida:


Otro ejemplo

Imagen Original:
Circulo detectado:
En este caso el centro de la bandera y el del circulo casi están posicionados en el mismo punto.
Corrida:




Otro ejemplo:

Imagen original:


Circulo detectado:
El punto extra en el circulo del medio es el centro de la imagen total

Corrida:


Aclaro que el otro cambio de color es por lo utilizado anteriormente en formas y figuras todo lo que sea un circulo sera pintado de azul.

El código que realice es el siguiente:

Para saber si es un circulo:



Llamado de función círculos y pintado de los círculos:



Código Completo:

Fuentes:




jueves, 28 de febrero de 2013

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

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(N2) 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(N2) 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.






martes, 26 de febrero de 2013

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:


Fuentes:






jueves, 21 de febrero de 2013

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