detección.de.círculos transformada.hough

abril 20, 2010

http://iie.fing.edu.uy/investigacion/grupos/gti/timag/trabajos/2004/deteccion_circulos/alcance.html

Problema

Objetivos

El objetivo del siguiente trabajo es detectar círculos en una imagen de pruebas clínicas, donde se pone una muestra en un reactivo y se observa si hay reacción o no. El objetivo de reconocer los círculos en la imagen (coordenadas del centro y radio) puede ser contarlos, etiquetarlos o hacer un promediado de color dentro de estos para decidir si el resultado fue o no positivo.

Para la detección de los círculos se implementa el un algoritmo de detección de círculos basado en la transformada de Hough, con el correspondiente procesamiento previo de las imágenes.

imagenes

http://iie.fing.edu.uy/investigacion/grupos/gti/timag/trabajos/2004/deteccion_circulos/imorig.html

Alcance

Todo el procesamiento y la detección de los círculos en este trabajo esta pensado para las imágenes que se nos suministraron.

Estas imágenes siguen un patrón que comienza con una muestra en un fondo claro y luego viene una franja oscura donde no hay círculos.

Teoria

Transformada de Hough

Esta es una técnica que permite descubrir formas en una imagen. Se basa en transformar puntos de la imagen en un espacio de parámetros. La idea es encontrar curvas parametrizabales como rectas, círculos y polinomiales. En teoría se pueden encontrar formas más complejas pero el costo computacional crece rápidamente. Generalmente se realiza detección de bordes a la imagen, y luego se aplica la transformada a esta. De esta forma son menos los puntos que hay que recorrer y por lo tanto mas rápido es el algoritmo. El más usado para realizar la detección de bordes es el Filtro de Canny.

Ejemplo: Detección de rectas.

Detección de círculos:
La ecuación del circulo tiene tres parámetros ( dos para el centro del círculo, uno para el radio). Por lo tanto el espacio de parámetros esta forma es de dimensión tres. Esto dificulta el algoritmo, recorrer un espacio de dimensión dos, y encontrar máximos en espacio de dimensión tres.

Detección de rectas

La aplicación mas simple de la transforma de hough es para la detección de rectas.

Suponga una imagen binarizada, resultado de la detección de bordes. Para cada punto x,y de la imagen pasan infinitas rectas de la forma: y=ax+b.
Luego cada punto x,y vota para cada pareja de puntos que satisface b=y-ax.
El algoritmo tiene que recorrer todos los puntos x,y, y para cada uno votar en el espacio de parámetros a,b o acumulador. Luego la pareja a,b con mas votos o el máximo del acumulador da la ecuación de la recta.

El problema planteado así tiene el problema que el espacio no es finito, a varia de 0 a infinito. En general se utiliza la siguiente parametrización: xcosO + ysin O=r. Donde r es la distancia de la recta al origen y O el ángulo entre la perpendicular y el eje x. Estos parámetros están acotados, r varia entre 0 y la diagonal de la imagen y O entre 0 y 2 veces pi.

ver imagenes

http://iie.fing.edu.uy/investigacion/grupos/gti/timag/trabajos/2004/deteccion_circulos/detrecta.html

Morfología Matemática

La palabra morfología significa forma y estructura de un objeto. Para imágenes binarias se definen operaciones morfológicas. y con estas se constituye una herramienta de extracción de componentes de imagen útiles en la representación y descripción de la forma de las regiones.

Las operaciones básicas de la morfología matemática son: dilatación se puede simplificar a decir que es agregar pixeles a un objeto, hacerlo mas grande, y luego erosión es hacerlo mas chico. La erosión saca los “outlayers del objeto”.

Luego la combinación de estas dan origen a los operadores Apertura y Clausura. El primero consiste en aplicar una erosión seguida de una dilatación aplicando la misma forma estructurante, como resultado esta tiende a “abrir pequeños huecos”. La clausura es el la aplicación de las operaciones básicas en el sentido inverso, y resulta en “cerrar los huecos”.

Algoritmo

Evolución del algoritmo

Filtro de Canny y Transf. de Hough

El filtro de Canny resulto aceptable para los circulos oscuros, pero no es posible detectar los círculos más claros se esta forma.

Una segunda opción es la utilización de umbrales. Esto surge a partir de que se puede distinguir claramente el fondo de los círculos. Pero esto no es suficiente para un funcionamiento óptimo de la transformada de hough. Por lo que se realiza un procesamiento posterior a la binarización.

ver imagen

http://iie.fing.edu.uy/investigacion/grupos/gti/timag/trabajos/2004/deteccion_circulos/imumbral.html

División

Dado que en la imagen se puede distinguir claramente donde se encuentran las zona de interés, decidimos recortar la imagen en franjas. De esta forma se aceleran todos los procesos.

Otra ventaja de separar la imagen en zonas de interés, es que se puede clasificar el contenido de la zona, y aplicarle algoritmos diferentes a cada una.

De aquí se clasifican las zonas en tres: circulo oscuro, circulo claro, o vacía. Para la división de la imagen se clasifican zonas comparando el nivel de gris promedio en la columna con un umbral, luego buscan las transiciones. Un último paso es dividir las imágenes resultantes a la mitad.

Para la clasificación del tipo de imagen se utiliza la desviación estándar de los pixeles de esta imagen. En una imagen oscura la desviación es alta porque hay pixeles de alto nivel de gris en un fondo de bajo nivel de gris. En las imágenes con círculos claros, estos también tienen una desviación estándar apreciable. Por lo tanto se clasifica comparando la desviación estándar contra dos umbrales.

Procesamiento previo a Transf. de Hough

Círculos oscuros.
El primer paso es la umbralización, con un umbral que se calcula para cada imagen. Luego se aplican las operaciones de morfología apertura y cierre, con las ventajas que se describieron de estas, y en este caso particular para tener formas mas circulares. El ultimo paso previo a la trasformada de hough es hacer una resta entre la imagen y la erosión de la misma, lo que da como resultado el perímetro.
De aquí se estima el radio como el perímetro dividido dos veces pi. El algoritmo de hough se aplica sobre esta imagen perímetro.

Círculos claros.
A esto círculos no se les puede aplicar las operaciones de morfología matemática directamente después de umbralizar. Luego de binarizar se aplica un filtro de mediana y finalmente la operación de perímetro, para tener menos puntos para procesar en el algoritmo de hough. No se puede estimar el radio en este caso, por lo que se usa el ultimo radio estimado
.

ver imagen

http://iie.fing.edu.uy/investigacion/grupos/gti/timag/trabajos/2004/deteccion_circulos/impclaro.html

Transformada de Hough

En esta implementación de la transformada de hough se busca eliminar un parámetro. Para esto se realiza una estimación previa del radio y luego solo se calcula el acumulador para radios en un entorno de dos pixeles del radio estimado. Las coordenadas del máximo de este acumulador corresponde al trío (coordenadas del centro, y radio) que mejor se ajusta.

Para desplegar los resultados se implemento el algoritmo de Bresenham, que utiliza las simetrías del círculo para optimizar la representación de este.

Resultados

Códigos

.M deteccion.m Corre todo el algoritmo llamando a las subrutinas que sean necesarias. En esta rutina se hace el cálculo del perímetro.

.M divide.m Subrutina para encontrar las zonas de interes de la imagen, es decir la zona clara donde puede haber un circulo. Como parametros recibe la imagen y un umbral y devuelve un vector con el comienzo y fin de cada zona de interes.

.M morfo.m Subrutina que aplica las operaciones de morfología matemática, apertura y cierre a la imagen que recibe como parámetro.

.M fmedian.m Filtro de mediana para 8 vecinos.

.M hough.m Nuestra implementación de la transformada de Hough, antes explicada.

.M bresen.m Algoritmo para dibujar los círculos de una manera eficiente.

Resultados finales.

Imagen original uno con la detección de los círculos.imagen

Imagen original dos con la detección de los círculos.imagen

Conclusiones

El algoritmo dio resultados aceptables para casi todos los círculos de las imágenes que disponíamos.

Se puede ver que hay círculos que no son bien detectados por este algoritmo. Esto se debe a que algunas de las muestras no son circulos perfectos. En otros casos se debe a que el resultado de la umbralización no fue el esperado.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: