Realidad Aumentada
Tarea 2: Reconocimiento de Triangulos
| MATERIA | REALIDAD AUMENTADA |
|---|---|
| ALUMNO | ORTIGOSA FLORES JOSE LUIS |
| FECHA ENTREGA | 1-OCT-2015 |
Actividades
- Imagenes segmentadas
- Caja envolvente
- Vertices
- Descripción del programa realizado
- Resultados despues de analizar las imagenes segmentadas
Imagenes segmentadas
Descripción actividad
Usar imagenes de la tarea uno para aplicar el algorítmo de
extracción de formas.
De las 25 fotos tomadas para realizar la tarea 1 se eligieron a las que a primera vista presentaron las formas mejor efinidas.
Imagenes originales a una resolución de 1600x1200.
 foto 1 |
 foto 6 |
 foto 11 |
 foto 16 |
 foto 22 |
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
Imagenes doblemente reducidas (resolución 400x300) y segmentadas con umbralización.
 foto 1 (png) archivo (pgm) |
 foto 6 (png) archivo (pgm) |
 foto 11 (png) archivo (pgm) |
 foto 16 (png) archivo (pgm) |
 foto 22 (png) archivo (pgm) |
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
Creación de la caja envolvente
Descripción de la actividad
Modifcar y/o usar el "algorítmo para extracción de formas", encontrado en la publicación Una bliblioteca para el procesamiento de imagen: scimagen para:
> Encontrar y etiquetar formas dentro de imagenes umbralizadas, y
> encontrarle a cada forma sus caja envolvente.
La idea principal del algoritmo para extraer formas es la siguiente:
Recorrer desde el primer pixel hasta el último.
Para cada pixel checar si es blanco ignorarlo, y sí es negro, entonces
se inicia la extracción de la forma.
Instanciar un objeto de tipo Forma
Meter el pixel negro a una pila (se crea un objeto Punto con las coordenadas del pixel)
Después para cada pixel(Punto) en la pila se hace lo siguiente:
se mete a sus pixeles(Puntos) vecinos negros a la pila
Se checa si el pixel actual es un vertice,
sí lo es se agrega a la lista de vertices de la forma.
después agrega el pixel(punto) a la forma
para finalmente marcar con un numero concecutivo el pixel
para evitar que el algoritmo lo relea.
Punto
Este objeto tiene funciones que se utilizan para calcular el producto punto entre vectores, además de hacer otras operaciones como la resta.
Forma
Este objeto representa a las formas encontradas dentro de una imagen. Este objeto guarda datos importantes como son: área, puntos máximo y mínimo que forman la caja envolvente, además de el vertice en el que se encuentra el angulo recto.
Caja envolvente y área de la forma
Para obtener la caja envolvente se requieren de dos puntos uno con las coordenadas mínimas (x mínima, y mínima) de todos los coordenas x e y de todos puntos que forman la imagen. Y uno punto con la x máxima e y máxima de entre todos las x e y de todos los puntos.
La tarea de calcular los puntos máximo y mínomo es responsabilidad del objeto Forma, en donde a cada momento que le agregamos un punto a una forma este se encarga de cachar al las Xs mínima y máxima. Lo anterior se ve en el siguiente fragmento de código.
Como se puede ver en el código anterior, además de calcular los puntos para la caja envolvente, en esta misma funcion también se esta calculando el área que es igual al número de pixeles que confirman la forma.
Encontrando los vertices
Descripción de la actividad
Encontrar los vertices de los triangulos además de encontrar
el vertice en el que se encuentra el angulo recto.
Buscando los Vertices
Para encontrar los vertices se opta por buscar una caracteristica que comparten aquellos pixeles que son vertices. Existen tres tipos de pixeles:
- El pixel que esta totalmente rodeado por otros pixeles negros.
- El pixel que es de frontera o borde, este pixel esta rodeado mayoritariamente, por pixeles negros
- El pixel que es vertice esta rodeado mayoritariamente por pixeles blancos.
Existen varias posiblilidades, en las que el caso tres puede darse sin embargo y aprovechando que estamos en busca de vertices que pertenecen a triangulos, se seleccioan sólo 4 posibilidades, que son las siguientes:
-
Que el vertice(pixel) que estamos buscando este en la esquina superior izquierda.
En este caso sólo debemos de checar que los 5 pixeles marcados en verde esten en blanco. Sí este es el caso podemos decir que se trata de un vertice.
-
Que el vertice(pixel) que estamos buscando este en la esquina superior derecha.
En este caso también debemos de checar que los 5 pixeles marcados en verde esten en blanco. Sí este es el caso podemos decir que se trata de un vertice.
-
Que el vertice(pixel) que estamos buscando este en la esquina inferior derecha.
Si sus vecinos en color verde son blancos entonces este pixel se concidera como un vertice.
-
Que el pixel que estamos buscando este en la esquina inferior izquierda.
Aun cuando esta idea funciona es claro que no es perfecta puesto que las imagenes no son perfectas, pues hay imagenes en las que las esquinas no estan bien definidas, o rectas que tiene brincos o deformaciones que de algun modo podrian caer en alguno de los casos anteriores.
Detectando ángulo recto
Para detectar el ángulo recto se uso la idea del producto punto, sin embargo no podemos checar que el producto punto entre dos vectores sea cero. Aun cuando las imagenes tienen triangulos rectangulo. Esto se debe a que las fotos tienen una perspectiva, lo que hace que los ángulos rectos sean ligeramente menores a 90°.
El algorítmo realiza todas las permutaciones de grupos de tres vertices de entre "todos" los vertices. Aunque se supone que son triángulo y que sólo habran tres vertices y que las permutaciones de tres puntos son 6. Hay ocaciones en las que el detector de vertices identificara más de tres vertices debido a que las formas pueden presentar alteraciones.
Algorítmos para detectar ángulo de 90°
La idea general es dados tres puntos a, b y c, seleccionamos al punto "a" para ver
que angulo se forma entre las linea(vectores) ab y ac, para lograrlo, debemos de
restar los punto "a" menos "b" para obtener el vector r1 = "ab" y "a" menos "c" para obtener
el vector r2 = "ac". Al hacer lo anterior los vectores seran enviados al origen. Ya teniendo estos
vectores hacemos el producto punto entre r1 y r2. y sólo almacenamos el producto punto más pequeño.
Al terminar de calcular todo lo anterior para cada permutacion de tres vectores regresamos el vertice
que haya tenido el menor producto, que seguramente sera el ángulo de 90°.
El programa
El programa toma una imagen segmentada (umbralizada) como entrada, y genera como salida dos archivos, el primero un archivo *.pgm donde estan dibujados los vertices, nodos y caja envolvente, además identificadores sobre las formas que se lograron detectar.
Para ejecutar el programa, primero se debe de compilar el codigo con ayuda del makefile, este genera un programa llamado recTriangulos.
El programa requiere de dos parametros, el primero es el nombre del archivo con la imagen segmentada
en formato *.pgm y el segundo sera el nombre de una imagen *.pgm en la que se dibujaran los resultados.
La salida del program es la imagen y un archivo con los resoltados del análisis de la imagen.
$./recTriangulos 1.pgm 1.result.pgm
Resultados
Se aplico el programa detector de triangulos a las imagenes indicadas al inicio y los resultados fueron los siguientes:
Analisis de la imagen 1.pgm
|
Imagen original |
Imagen segmentada |
Al ejecutar el programa sobre la imagen segmentada, el programa da como resultado el siguiente archivo de texto.
El análisis de la imagen nos indica que el programa pudo identificar 4 formas dentro de la imagen las formas se enumeraron de la 1 a la 4.
Para cada forma analizada el programa calcula el área en pixeles. En este caso nos indica que la forma 1 tiene un área de 9322px, que los puntos que forman su caja envolvente son (117,112) y (197,217). También nos entrega una lista con los vertices, además de indicarnos cual de ellos es el de 90°.
Aunque el archivo tiene mucha información, no hay nada mejor que mostrar los resultados sobre la imagen procesada. Que para este caso es la siguiente:
En la imagen podemos ver que los vertices estan marcados con cuadros grises pequeño, también podemos ver en un tono gris mas tenue las cajas envolventes de cada forma identificada y en sus esquinas superiores podemos ver la etiqueta que le coloco a cada forma. Otra cosa importante en la imagen es que esta marcado el ángulo de 90° con un cuadro gris más grande y obscuro.
En esta imagen el programa logro localizar con exito todas las formas, cajas y vertices.
Al ejecutar el programa sobre la imagen segmentada, el programa da como
resultado el siguiente archivo de texto.
En esta imagen el programa tuvo problemas para identificar
los vertices y en ocaciones identifico vertices de más, debido a la
inperfección de las imagenes y a que el algoritmo sólo
concidera 4 casos de posibles esquinas.
En la imagen podemos ver que el programa logro identificar las 4 formas
y que a cada una logro calcular correctamente sus cajas envolventes, sin embargo
en la forma 3 identifico vertices de más así como en la forma 1. En esta
ocación sólo logro identificar correctamente a dos triangulos.
Analisis de la imagen 6.pgm
Imagen original
Imagen segmentada
Al ejecutar el programa sobre la imagen segmentada, el programa da como
resultado el siguiente archivo de texto.
En esta imagen el programa logro identificar a los triangulos rectangulos
de las esquinas y los etiqueto con los número 1, 3, 6 y 7. Además de que
logro sin problema identificar las cajas envolventes de las 8 formas que encontro.
Sin embargo en las formas 2, 4, 5 y 8 no logro identificar correctamente los vertices.
Analisis de la imagen 11.pgm
Imagen original
Imagen segmentada
Al ejecutar el programa sobre la imagen segmentada, el programa da como
resultado el siguiente archivo de texto.
En esta imagen también se tuvieron problemas en identificar los vertices correctamente
tal es el caso de las formas 1 y 2, sin embargo a pesar de eso en las formas 1, 3 y 4
se logro identificar correctamente los angulos rectos.
Analisis de la imagen 16.pgm
Imagen original
Imagen segmentada
Al ejecutar el programa sobre la imagen segmentada, el programa da como
resultado el siguiente archivo de texto.
En esta imagen el programa logro identificar todas las formas,
los vertice, las cajas envolventes, y los angulos rectos de cada forma.
Analisis de la imagen 22.pgm
Imagen original
Imagen segmentada
El programa en general reconoce todas las formas, sin embargo no logra identificar correctamente a los vertices y como el algoritmo de detección de angulos rectos depende totalmente de la correcta detección de los vertices, este ultimo también falla en repetidas ocaciones, algunas veces por que el algoritmo de reconocimiento de vertices no reconoce todos los vertices y otras, por que caen sobre una misma linea lo que los hace ser practicamente el mismo vector.
Programas
recTriangulos.tarPara poder implementar el algoritmo se requirio de crear una estructura de datos que se comportara como una lista, y al mismo tiempo como una pila, por lo que se creo la estructura de datos ArrayList que es una implementación de un arreglo dinamico generico.
**Para compilar el programa se requiere cambiar las rutas de la biblioteca de scimagen, tanto en el codigo fuente como en el makefile.