Proyecto final: Lector de códigos QR

Buen día, como requisito del proyecto final de la clase de visión computacional es necesario realizar un reporte del proyecto realizado, esta publicación servirá como reporte para el proyecto final.

Lector de códigos QR
Mi proyecto como ya se ha visto en presentaciones pasadas es un lector de códigos QR, la finalidad es que el lector tenga un alcance mucho mayor que los lectores normales.

¿Por que un lector de códigos QR?
La tecnología es de estos códigos no es realmente nueva pero en los últimos tiempos se ha incrementado considerablemente el uso de los mismos. Los podemos ver en periódicos, revistas, anuncios en la calle y en distintos edificios (al menos en mi cuidad), por lo cual considero que es una habilidad muy útil tener conocimiento técnico de los mismos y poder crear un software que sea capaz de identificarlos y leerlos.

Además de todo esto, el proyecto no se planea dejar aquí, si no que tengo la intención de reutilizarlo en un momento futuro. Uno de los usos que le pienso dar es crear una versión para la construcción de la tesis de un compañero en donde se pretende utilizar los códigos en conjunto con robots inteligentes, que usen los robots para identificarse unos con otros.

Algunos otros usos de los códigos QR:

• Publicidad
• Orientación de robots
• Orientación sobre sitios
• Tarjetas de presentación
• Información de piezas en museos
• Información de productos 

Realidad aumentada
Dado que los QR code trabajan con visión computacional y esta rama tambien se utilizara para realizar realidad aumentada, es fácil implementar un sistema de realidad aumentada apoyándose en estos códigos. Tengo que aceptar que una de mis primeras ideas cuando me imagine el proyecto, fue utilizar QR codes con realidad aumentada en mi tarjeta de presentación.


En este vídeo me pareció muy interesante pues la persona se tatuó una especie de QR code en el pecho y utiliza realidad aumentada para correr una animación:


El siguiente vídeo se muestra diferentes figuras 3D dibujadas sobre QR codes impresos sobre tarjetas de papel: 


Diseño del software
En un pricipio se planteó realizarse de la manera en que se muestra en el diagrama de secuencias inferior, teniendo solamente dos clases.

Pero debido a que el proyecto no es en sí muy extenso si no que es complicado, en algunas de sus partes y requirió mas un análisis de sus partes y de que filtros y métodos que iban a ser utilizados. En el diagrama superior se muestran los pasos que se tenían planeados y esos en realidad no han cambiado. Lo que pretendo ahora mostrar es los filtros que se utilizaron en la detección y el orden, dado que el código tiene un paradigma funcional, mostrare los pasos con el siguiente diagrama de flujo.

En el diagrama de flujo de muestran los pasos que se siguieron para poder detectar el QR y su posición.

¿Como funciona?
El programa generado se puede dividir en dos partes, en la primera que genera un preprocesamiento para encontrar con mayor facilidad espacios en los que puede haber un código QR:

1. Primero se obtiene un "frame" de la cámara.
2. Se modifica su tamaño a un maximo de 128x128.
3. Se convierte a escala de grises.
4. Se calcula el gradiente en vertical y horizontal utilizando una mascara de Sobel.
5. Se hace una copia de la imagen.
6. Se aplica un filtro de media a la copia de la imagen.
7. Se resta la copia con filtro de la media a la imagen original.
8. Se aplica un filtro Blur por ahora la intensidad del filtro es constante pero se buscara a futuro que esta cambie dependiendo de la mancha que se forma.
9. Se aplica un filtro umbral.
10. Después se recorre cada mancha con un BFS y se encuentran las dimensiones de un rectángulo que rodé cada mancha.

Una vez que se tienen lugares donde es muy probable que haya un código QR se llevan a cabo los siguientes pasos:

1. Se recorta el pedazo donde esta el código QR en la imagen original la que tiene el tamaño original, que sera nuestra nueva imagen de trabajo. 
2. Se modifica el tamaño de la nueva imagen a 128x128.
3. Se aplica un filtro para mejorar el contraste utilizando histogramas.
4. Después de recorre cada fila de la imagen y se restan los vecinos de la derecha y de la izquierda de cada pixel, a este valor se le aplica un umbral para decidir si dicho pixel sera blanco o negro, por ahora de 120 pero se buscara después que se adapte a los valores de la imagen.
5. Ahora que tenemos blancos y negros bien definidos, se recorre cada fila buscando las esquinas del código QR que tienen un patron de blancos y negros parecido a este: Negro, Blanco, Negro, Negro, Negro, Blanco Negro. Una vez encontrada una fila con ese patrón se busca en las columnas para asegurar que sea dicho cuadrado. Si tiene las características deseadas la función regresa un valor boolean con valor True.

Aun faltas partes de implementar pero implementarlas se planea hacer lo siguiente:

1. para poder obtener la matriz de los datos del código QR, lo que se quiere hacer es dividir la imagen en una malla, después verificar celda por celda de la maya obteniendo el porcentaje de blancos y negros en la imagen estos valores servirán como medida de probabilidad de ser blanco o negro, con esto definiremos por medio de umbrales si el valor es un negro, un blanco o si simplemente no podemos determinar que valor es.
2. Una vez que tenemos el código de dos dimensiones, necesitamos decodificarlo utilizando algoritmos para decodificar códigos Solomon, pero debido a que implementar estos algoritmos aun es un poco avanzado para mí, buscaré una implementación ya existente que se pueda adaptar a mí código.

Desempeño

Para medir el desempeño del programa se midieron los frames por segundo que se calcularon a partir del tiempo de ejecución en diferentes ámbitos, los tres que se eligieron fueron los que creí que serian los más comunes en la forma en la que se usara para el proyecto de ubicuo.

Este primero muestra los frames por segundo en un ambiente estático, este solo se tomo tiempos poniendo la cámara en una sala sin personas.

En el siguiente no se escanea un código QR aun, pero se pone la cámara en una sola con multiples personas y además se genera gran cantidad de movimiento frente a la cámara.

En este ultimo caso solo se encuentra una persona en la sala y esta escanea un código QR durante el tiempo que se tomaron las medidas.

Conclusiones
El tiempo de lectura estático es algo más o menos decente, puesto que casi alcanza los 20 frames por segundo los cual es aceptable si se fuera a mostrar en un vídeo lo que se muestra en la cámara, Los frames por segundo de lectura con el código QR bajan notablemente casi hasta alcanzar números negativos, lo cual no es un problema si solo se utiliza leen códigos durante cortos periodos de tiempo.
El problema esta en que en un espacio con movimiento tienes picos donde el tiempo se eleva considerablemente.
Tomando en cuenta esto se considera que podría producir un desgaste de energía quizás innecesario, espero que estos números mejoren utilizando mejores filtros de reducción de ruido y encontrando una característica en las esquinas de los QR en imágenes que me permita reducir el tiempo de ejecución, para dar espacios de descanso a la maquina.

Librerías utilizadas
Para el proyecto se planteó utilizar las siguientes librerías:

• Opencv: Para usar la cámara web y algunos filtros de la librería.
• QR Tools para decodificar la matriz obtenida.

Pero debido a la falta de tiempo aun no se ha decodificado la matriz de el QR, así que la única librería que se utilizo fue Opencv para llevar a cabo todo el proceso de visón computacional.

Trabajo a futuro
Ahora hablare de algunas de las características del código QR que quiero agregar y mejorar.

Mejorar la detección 
Se plantea que el QR sea detectable desde largas distancias, para eso se hace un preprocesamiento buscando figuras que tengan las características que tienen los QR codes antes de verificar que lo sean, la meta es mejorar este algoritmo agregando que el tamaño en el que se esparcen las orillas detectadas varié dependiendo de la distancia que hay entre esquinas, además de implementar un algoritmo mas eficiente.
En esta imagen se muestra la mancha que se forma con las esquinas a una distancia cercana:

En la siguiente imagen se muestra el resultado alejando solo unos centímetros el código QR, como se puede ver el desempeño disminuye bastante, puesto que el código se encuentra donde esta la mancha blanca que esta mas arriba en la imagen a la izquierda casi en el centro, todo lo demás es ruido en la imagen:

Agregar detección de movimiento
 Se plantea además agregar detección de movimiento del código QR esto por ahora solo se planea hacerlo utilizando el fondo verde que se muestra en el código al inicio de esta publicación, simplemente siguiendo objetos que tengan dicho color.

Otras partes a mejorar

1. Implementar un blur adaptativo para engordar los puntos de las esquinas
2. Implementar un algoritmo mas realista para encontrar las esquinas
3. Disminuir el espacio de búsqueda buscando mejores características en con el calculo de los gradientes de las esquinas o eliminar el calculo de gradientes pues produce perdida de tiempo
4. Reducir el error en la búsqueda de patrones de las esquinas eliminando el ruido que se produce al calcular el error del patrón.
5. Posiblemente implementar un grupo de mallas en horizontal y vertical respecto al QR code para obtener los valores de la matriz
6. Buscar una libreria para decodificar los códigos Solomon
7. Arregla las distorsiones que ocurren al voltear el QR code

Control de versiones

Por ultimo dejo el link al control de versiones para esta clase, en el se encuentran todas las tareas realizadas en clase, además de el proyecto final cuyo nombre es QRScanner en el repositorio.

https://github.com/MaxHernandez/Vision_computacional

Presentación

Referencias:

• Docstoc.com (2010) QR Barcode Detection. [online] Available at: http://www.docstoc.com/docs/55691974/QR-Barcode-Detection [Accessed: 14 May 2013].
• Utkarsh (2012) Scanning QR Codes | AI Shack. [online] Available at: http://www.aishack.in/2012/02/scanning-qr-codes/ [Accessed: 14 May 2013].
• Utkarsh (2012) Scanning QR Codes | AI Shack. [online] Available at: http://www.aishack.in/2010/05/corner-detection-in-opencv/ [Accessed: 14 May 2013].

Laboratorio 9: Usando detección de esquinas para encontrar poligonos

Para esta semana en la clase de visón computacional se nos dio a la tarea de utilizar las técnicas aprendidas en el salón para encontrar esquinas para encontrar polígonos en una imagen, esta publicación servirá a manera de reporte para dicha tarea.

Paso 1 - detectando esquinas
Para detectar las esquinas en una imagen se utilizo una técnica muy simple primero se aplica a una copia de la imagen con la que se va a tratar un filtro de media, después se resta este mismo filtro a la imagen original y se le aplica un filtro umbral.

Debido a que el filtro de la media disminuye la intensidad los píxeles que se diferencian mucho de sus vecinos, esto provoca que al restas estas dos imágenes las esquinas y el ruido de la imagen se pinten con mas intensidad. Para obtener la imagen de arriba se aplico además BFS para promediar los píxeles de las esquinas y que fuese mas fácil de tratar.

Paso 2 - Detectando bordes
En el siguiente paso se detectan los bordes de las figuras utilizando gradientes calculados con la mascara de Sobel, no voy a meterme a detalle con esto por que esté método ya ha sido implementado en la siguiente publicación:
http://maxkalavera.blogspot.mx/2013/02/tarea-1-deteccion-de-bordes.html

Paso 3 - Recorriendo las esquinas

Ahora para poder saber a que polígono pertenece cada esquina se utilizo de nueva cuenta BFS para recorrer todos los bordes guardando en un arreglo las esquinas que pertenecen a cada polígono.

Otro punto importante de este pasó es que el recorrido del BFS debe darse en una dirección puesto que necesitamos saber que esquinas tiene conexión con otras para poder comprobar que es una figura, esto debido a que en el siguiente paso analizaremos si estos bordes que juntan las esquinas son lineas rectas o no.

Para poder lograr esto simplemente se modifico la implementación de BFS para que los nuevos vecinos a visitar se agreguen al final de la lista, esto para que los píxeles recorridos se expandan como si ese borde fuera un canal de agua y se llenara con agua, después se hace que empiece a correr en una de las esquinas, cuando llegue a la siguiente esquina se borran todos los píxeles a visitar en la lista, esto provoca que se cierre el punte entre la primer esquina y las demás pero como la primer esquina ya fue visitada, no nos interesa volver a visitar sus píxeles vecinos.

Paso 4 - Comprobando los bordes

Una vez que el programa conoce las esquinas y cuales se comunican con otras se hace un recorrido de esquina a su vecina con un algoritmo para dibujar lineas, comprobando que haya píxeles de borde en cada píxel que se visita.

Como punto final para encontrar el centro de la figura solamente se promedian los puntos de las esquinas.

Código


Resultados 

Imagen uno

Esquinas	Bordes	Recorrido	Salida

Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-1.png 
Poligono1 encontrado, tiene 6 lados.
Poligono2 encontrado, tiene 4 lados.
Poligono3 encontrado, tiene 5 lados.
Tiempo de corrida: 0.922751903534

Imagen dos 


Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-2.png 
Poligono1 encontrado, tiene 3 lados.
Tiempo de corrida: 0.841367959976

Imagen tres

Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-3.png 
Poligono1 encontrado, tiene 10 lados.
Tiempo de corrida: 0.845256090164

Conclusiones
Como se puede ver la implementación funciona bien con figuras bien definidas con pocos lados ya que como pudimos ver en el hexágono dado que los ángulos son mas amplios no fue posible para el programa detectar de forma correcta las esquinas.
Otra cosa que serviría recalcar es que en el mundo real no todos los objetos de forma poligonal tienen esquinas definidas así que esta implementación podría no ser muy útil para el uso de robots o cosas parecidas.

Referencias: 

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

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

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

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