Visión por computador- detección de círculos.

Versión en Español

Resulta que he estado “liadillo” estos días con el TFM, pero al fin parece que estoy libre y listo para retomar este cajón desastre. Hoy, tras leer un artículo publicado recientemente en “Pattern Recognition” [1], tengo la intención de presentar algunos conceptos básicos, problemas y algún que otro ejemplo simple sobre algoritmos de detección de círculos.

El primer nombre que surge al buscar información sobre métodos de detección de círculos es Hough. Más concretamente, un método ampliamente aceptado basado en la “Circle Hough Transform (CHT)” que parece que funciona bastante bien en términos de localización, aunque presenta algunos “problemillas” relativos al tiempo de cómputo. Precisamente son esos problemas los que motivan la existencia de algoritmos alternativos como poner ejemplo el presentado en el artículo referido al comienzo. Ese artículo en concreto usa algo conocido como “circle power theorem” y “power histogram” para conseguir detectar círculos en imágenes ruidosas consiguiendo reducir el tiempo de cómputo necesario. Es bastante interesante pero hoy, la idea es simplemente entender el método CHT.

La idea escondida tras el “Hough Transform method” es identificar todas las líneas/cuadrados/círculos o lo que sea que se está buscando que pasen por los píxeles blancos de una imagen binaria registrando los candidatos en una matriz de acumulación. Posteriormente, los candidatos que más se repiten se consideran detecciones positivas. La dificultad normalmente reside en la forma en la que se describe la geometría que se quiere encontrar.

En el caso particular de un círculo, la ecuación paramétrica a utilizar sería:

Donde es el centro del círculo y su radio. Por tanto, solo con tres parámetros, podemos identificar un círculo de forma inequívoca. Hecho que nos permitirá pintar los resultados de una forma más o menos entendible.

Para explicar esta técnica, normalmente se comienza asumiendo que se buscan círculos de radio conocido, y luego, se generaliza la interpretación.

Considerando que se está buscando un círculo de radio conocido en una imagen ideal (que solo contiene el círculo objetivo), si se acumulan los centros de todos los círculos candidatos en una matriz, resulta lo siguiente.

Como puede verse, mientras que el proceso de búsqueda progresa, le matriz de acumulación presenta un pico justo en la posición que corresponde al centro a detectar. Sin embargo, cuando el radio es desconocido, la representación no es tan sencilla puesto que se ha de considerar una nueva dimensión.

Una posible forma de ilustrar esta idea, es construir conos en cada pixel-blanco, correspondiendo cada nivel en z con un radio distinto. La siguiente figura pretende representar este proceso de búsqueda. En ella puede verse como, para el valor de radio correcto, se detecta un pixel “brillante” en el centro de la representación de la matriz de acumulación.

Ahora, pasamos a aplicar el método (código disponible AQUÍ) primero sobre una imagen sintética, y luego sobre una real. La siguiente figura muestra una representación dinámica del subespacio resultante donde puedes ver que, cuando se alcanzan los niveles de los radios de los círculos presentes en la imagen, aparecen de nuevo puntos brillantes.

Si se representan los máximos valores registrados en cada uno de los niveles del subespacio, podemos observar tres picos, que probablemente correspondan con los tres círculos presentes.

Si se define un umbral para discernir entre detecciones positivas y negativas, e iluminamos los círculos detectados, se obtiene la siguiente imagen.

Parece que funciona bien … pero claro.. es cierto que es una imagen sintética y por lo tanto, la detección es más sencilla. Entonces veamos qué ocurre al aplicar la técnica a una imagen real. En este caso, al representar el subespacio, no se observan picos tan “diferenciables” como en el caso anterior.

Sin embargo, cuando se representan de nuevo los valores máximos en cada nivel del subespacio, sí que se diferencian algunos candidatos potenciales.

Si aplicamos de nuevo un umbral, y se iluminan las detecciones positicas, resulta que sí que hemos detectado los círculos principales de la foto. Aunque aparecen por ahí algunos círculos que uno no esperaría (falsos positivos?).

Las conclusiones que extraigo de este breve trabajo son las siguientes:

• Resulta que la “transformada de Hough” que conocía para la detección de líneas, puede generalizarse para la búsqueda de cualquier otra geometría.
• El tiempo de cálculo de este método es una de las grandes desventajas.
• Una vez obtenida el subespacio de acumulación, la tarea de decidir qué se considera una detección positiva-negativa no es para nada trivial.

Algún día sería interesante explorar el método presentado al principio de este post, pero ese día no será hoy.

Para cualquier inquietud, abajo tenéis el cajón de comentarios!

Nos vemos pronto.

Referencias.
[1] B. Yuan and M. Liu. Power histogram for circle detection on images. Pattern Recognition, 2015.

Visión por ordenador – Regiones nítidas

English version

Resulta que últimamente he salido de excursión el “apasionante mundo de la fotografía” y estoy descubriendo bastantes cosas interesantes en las que no había pensado antes. Uno de los asuntos que han despertado mi curiosidad es cómo funciona la función auto-focus. Además, recuerdo haber visto en algún momento una camara que, mientras mostraba la imagen en la pantalla, iluminaba las zonas enfocadas. En aquel momento no me paré a pensar cómo funcionaba aquella arma del diablo pero el momento ha llegado, y como siempre Wikipedia tiene la primera respuesta rápida Wiki.

El objetivo de hoy es desarrollar un pequeño script en Matlab que ilumine las regiones “más enfocadas” de una imagen. El código utilizado está disponible AQUÍ.

Antes de nada, ¿Cuál es la diferencia entre una imagen enfocada y borrosa? Nitidez. Una propiedad que mide cómo varía la intensidad de luz entre un pixel y su vecindad. En el siguiente patrón mostrado, podemos ver cómo efectivamente, el valor de intensidad cambía más suavemente en imágenes emborronadas.

Parece ser que hay varias maneras de medir dicha propiedad. Entre todas ellas, destacan dos métodos: basados en kernels Vs métodos frecuenciales. Los métodos basados en Kernels consisten básicamente en registrar la diferencia entre cada pixel y el valor medio de su vecindad. Mientras mayor sea esa diferencia, mayor es la probabilidad de tratarse de una región enfocada. Asumiendo que la imagen a procesar contiene alguna zona enfocada, los valores más altos se registrarán en dichas regiones.

Esa información relativa a la imagen pues, a menos que tengamos un valor absoluto de antemano que permita diferenciar zonas bien enfocadas por este método, este método iluminará “zonas enfocadas” incluso en imágenes totalmente borrosas.

Hay una forma alternativa de medir nitidez que no presenta ese problema y se basa en la cantidad de información de alta frecuencial que contiene la transformada de Fourier de la imagen. Sin haberme informado demasiado, tiene pinta de que son métodos más densos teóricamente hablando así que los métodos basados en kernels cubrirán nuestras expectativas de hoy.

Como se ha referido antes, la nitidez en cada píxel se calcula simplemente aplicando el kernel:

Para ver qué hace exactamente, lo aplicaremos sobre una imagen de ejemplo. Las dos imágenes siguientes muestran la imagen original y el resultado de la operación (tras normalizar la “matriz de nitidez” resultante).

En la última imagen en blanco y negro, las zonas más oscuras corresponderían a las zonas seleccionadas. Si aplicamos una umbralización a esa imagen, tendremos una imagen binaria (sólo “unos” y “ceros”) con las zonas bien señaladas.

Este último resultado lo usamos para iluminar píxeles en la imagen original y tenemos lo siguiente.

Finalmente, y siguiendo con la tendencia creciente de usar gifs en los posts, una pequeña animación generada a partir de imágenes de la misma escena pero con distintas zonas enfocadas.

Dudas, consultillas y/o comentarios son bienvenidos.

Nos vemos pronto!

Visión por computador: Tracking!

English Version

Resulta que  existen infinitas formas inteligentes de realizar el tracking the un objeto en una imagen: usando descriptores de características, flujo óptico, colores, filtro de Kalman etc. Puesto que no soy un genio, y aprovechando un tracking simplificado que he hecho hace poco para un proyecto de clase (código disponible AQUÍ), me gustaría comentaros algunas de las dificultades generales que hay que resolver.

Hoy empezarmeos la casa por el tejado: Resultados!. Gifs, gifs y más gifs. He aquí un pequeño gif del código funcionando.

—————————-Cómo implementar esto?—————————-

Una aplicación completa de tracking no tiene que resolver únicamente el proceso de seguimiento en sí mismo, sino que tiene que lidiar con varios problemas que lo acompañan.

• Cómo comenzar el seguimiento? Qué estoy buscando?
• Seguimiento: conozco dónde estaba el objetivo en el instante anterior, dónde debería buscar ahora? puedo simplificar el proceso?
• Y si pierdo el objeto en medio del seguimiento, qué hago?

Puede parecer fácil… sólo tres aspectos a resolver?… mejor no subestimemos a Murphy no vaya ser que se complique la cosa. El siguiente diagrama da una visión general del procedimiento que yo decidí plantear.

Lo primero que tenemos que tener en mente es que conocemos exactamente el objeo que estamos persiguiendo!. Lo creas o no, no siempre pasa. Esto quiere decir que siempre que el objeto esté a la vista, podremos localizar su posición. Esto no suele ser cierto en condiciones no controladas por muchas razones. La más inmediata es el hecho de que es imposible caracterizar un objeto teniendo en cuenta todas las posibles iluminaciones a las que puede estar sometida. Entre otras cosas porque un ordenador no puede saber si un objeto a cambiado su color a causa de una iluminación desafortunada, o simplemente es un objeto diferente. Vale… y si consideramos que la iluminación es conocida? (Simplificaciones!!). El algoritmo que aquí se comenta es bastante simple así que necesitamos bastantes simplificaciones (sinceramente, algunas de ellas un tanto “groseras”), y considerar que las iluminación está controlada es la primera.

—————————-Objetivo—————————-

Dicho esto, hablemos sobre el objetivo. Vamos a considerar el objetivo más sencillo de rastrear que existe: “una forma negra sobre fondo blanco” o lo que es lo mismo, un trocito de cinta aislante en medio de un A3.

—————————-Tracking—————————-

En esto de explicar algoritmos no suele aplicar eso de “lo primero es lo primero”, suele ser más útil entender el funcionamiento normal del algoritmo y luego ver excepciones, y transitorios de inicio y finalización; que es justo lo que haremos.

Asumamos primero que conocíamos la posición del objeto en el instante anterior. Esto nos da algo con lo que trabajar. Esta información nos permite colocar una “ventana de búsqueda” centrada en y de tamaño para no tener que buscar el objeto en toda la imagen. En otras palabras: el objeto se busca en torno al punto en el que suponemos que va a estar el objeto atendiendo a los datos pasados, y el tamaño de esa región de búsqueda dependerá de alguna forma de la incertidumbre de esa estimación. La siguiente imagen intenta mostrar por qué el tamaño de la ventana es una función de la velocidad.

Ok,ya tenemos la ventana de búsqueda bien situada, ahora qué? cómo refinamos la posición? esto suele ser complicado y normalmente requiere trabajo previo de caracterización del objeto a rastrear, por ejemplo, usando descriptores binarios invariantes… pero hoy no! Estamos buscando algo oscuro en un fondo blanco y esto facilita mucho el proceso. Nuestra solución particular consiste en: recortar la imagen para quedarnos sólo con la ventana de búsqueda, umbralizarla, invertirla, y calcular el centro de masa… eso es todo. Después de haber solucionado las cosas difíciles, esto es muy simple :).

—————————-Proceso de reenganche—————————-

Qué hacemos si no sabemos dónde está el objeto en el instante anterior? pues tenemos algunas alternativas, entre ellas:

• Buscar actívamente el objeto. Esto consume tiempo y capacidad de cálculo puesto que habría que analizar la imagen completa sin saber si quiera si el objeto está a la vista.
• Respuesta pasiva. Lo hemos perdido… pues nada, esperaremos justo en el sitio donde lo hemos perdido hasta que pase por aquí y nos reenganchamos.

La segunda alternativa es más simple por lo que, adivinas qué vamos a hacer? exactamente, ninguna de las anterior… nah, I’m kidding, la segunda xD. Para nosotros es suficiente esa opción puesto que no vamos a usar la aplicación para nada serio, en tal caso, seguramente la primera opción sería más adecuada.

Y se acabó! Esto ha sido todo por hoy. Os animo a que probéis el código, o mejor, a que implementéis vuestros propios algoritmos de seguimiento y los compartáis por aquí en los comentarios.

Hasta la próxima!

Visión por computador #1 – Flujo Óptico

English version
Resulta que la visión por computador no lidia solo con problemas basados en imágenes estáticas. El tratamiento de vídeos para la extracción de información es también labor de esta disciplina. Puede que la dificultad de este post rompa un poco con la tendencia de los anteriores, pero se dice que la mejor forma de aprender algo es explicándolo y como me gustaría usar este blog como otra herramienta de auto aprendizaje, aquí estamos. Preparado?

Uno de los retos que afronta la visión por computador hoy día es el reconocimiento de actividades. Resulta que el desarrollo esta tecnología parace interesante, por ejemplo, para ser implementada en dispositivos inteligentes y que estos sean capaces de interactuar con humanos en función de su estado anímico, o bien (un ejemplo más realista) reconocer accidentes de tráfico o actos vandálicos con cámaras de seguridad.

Hoy, me gustaría presentar uno de los conceptos básicos que da lugar a la existencia de métodos más avanzados: el Flujo Óptico. Algunos estudios plantean que la clave en el reconocimiento de actividades es ser capaz de analizar el flujo óptico de un conjunto adecuado de píxeles. El ejemplo tradicional que apoya este planteamiento describe una habitación a oscuras en la que se encuentra una persona con puntos de luz repartidos por sus brazos mientras realiza una cierta actividad. Simplemente observando el movimiento de estos puntos, sin duda seríamos capaces de saber qué está haciendo esta persona no? Pues algo parecido se pretende hacer de forma automática!

Para quellos que no estén interesados en las matemáticas de este asunto, empiezo por el resultado esperado (siguiente gif). Como puede verse, el cálculo del flujo óptico asocia a cada pixel una flecha que apunta en la dirección en la que “creemos” que el pixel se está moviendo.

Hay varias alternativas para calcular el flujo óptico, aunque podría decirse que uno de los más populares es el método de Lucas Kanade, que será descrito aquí en un minuto :). Antes de nada, aquí tienes el código Matlab usado para generar los resultados que se presentan que puedne verse por aquí.  GitHub

Antes de nada, necesitamos una representación matemática para describir vídeos. Los vídeos se representarán de la misma forma que las imágenes pero con una dimensión extra, el tiempo: . Dados dos instantes consecutivos y , queremos calcular el flujo óptico, más concretamente un campo de velocidades que representa la diferencia entre el frame en y .

Para cada pixel , buscamos la velocidad  que describe el cambio de posición de dicho pixel de un frame a otro.

Si seguimos un pixel concreto durante el tiempo, podemos escribir:

Asumiendo pequeños desplazamiento se tiene:

Por lo que podemos desarrollar en Taylor y escribir:

Obviamente, tenemos dos incógnitas y solo una ecuación. El método de Lucas Kande asume que la vencindad del pixel evaluado tiene la misma velocidad que el de interés, por lo que se podría escribir:

El sistema de ecuaciones puede expresarse como  donde

                   

Como puede verse, queda un sistema sobredimensionado puesto que para dos incógnitas tenemos más de dos ecuaciones. Lucas Kanade propone resolver el sistema con mínimos cuadrados mediante la siguiente relación:

Donde la matriz debe tener rango completo.

Este método funciona especialmente bien en regiones con geometría similar a esquinas, y… eso es todo!. No ha sido tan traumático no?. Espero que te haya interesado el contenido, y que comentes lo que te apetezca para enriquecer mi ignorancia jeje.

Cuídate!