Un enfoque bayesiano para la extracción de características y agrupamiento en visión artificial

Miguel Ángel Cazorla Quevedo

Versión pdf comprimida con zip (23Mb)  (4Mb) 

Enlace a la tesis en la Biblioteca Virtual Miguel de Cervantes

Para visualizar mejor el documento (sobre todo las fórmulas matemáticas) es preferible utilizar Internet Explorer (Aaargh!)

Para vosotros, padres
También para ti, Fran
(en tu memoria)
 

No hay sistemas visuales perfectos. Para construir un sistema óptimo, es necesario especificar claramente sus tareas y el coste de no realizarlas. Además, para construir una máquina visual óptima, uno debe usar tanto conocimiento como sea posible acerca del mundo y de los recursos computacionales disponibles.

[Grzywacz y Escolano2000]
 
Agradecimientos

Una tesis doctoral no surge como un producto aislado. Suele ser la consecución de un camino que a veces se bifurca en bastantes ocasiones, muchas más de las que quisiéramos, para llegar a una meta final. Este camino se empezó a andar con los cursos de doctorado realizados en el Departamento de Tecnología Informática y Computación de la Universidad de Alicante. Durante los cursos empecé a trabajar con dos personas que desde entonces han sido una fuente de constante ánimo y crítica. Me refiero a mi director de tesis Francisco Escolano y a Domingo Gallardo. Junto a ellos, y más tarde con Otto Colomina, fuimos dando forma al contenido final de este trabajo. Fueron muchos días de pizarrón y latiguillos.

Las personas integrantes del grupo de investigación al que uno pertenece da soporte y ánimos para seguir adelante. En concreto, Ramón Rizo como director, Isabel Alfonso, Pilar Arques, Patricia Compañ, Faraón Llorens y Rosana Satorre. Los recursos, tanto humanos como materiales, de este grupo han servido para que esta tesis se desarrollara de la mejor manera posible.

En el verano de 1999 realicé una estancia en el Smith-Kettlewell Eye Research Institute (SKREI) de San Francisco. Quisiera dedicar unas líneas a agradecer la tremenda amabilidad con la que me acogieron. En especial, agradecer a Norberto Grzywacz todos los esfuerzos realizados para que mi estancia fuera lo más agradable posible. El final del camino de esta tesis empezó a verse en dicha estancia. Alan Yuille y James Coughlan compartieron conmigo sus trabajos actuales. El laboratorio de Alan fue el lugar de múltiples reuniones, en las cuales se discutieron y sacaron adelante muchas de las propuestas aquí presentadas. También a ellos deseo agradecer el tiempo dedicado a ampliar mis conocimientos (en principio bastante escasos) sobre teoría bayesiana. El trabajo de Scott Konishi sirvió de base para la formulación bayesiana de la evidencia de aristas. Scott me asesoró sobre la mejor forma de obtener las mejores instantáneas que luego utilizamos en los experimentos.

Prefacio
Dotar a un robot móvil de las capacidades visuales necesarias para sobrevivir en un entorno dado no es una tarea fácil. Dicha supervivencia implica desarrollar con éxito ciertas tareas como auto-localización, evitación de obstáculos, aproximación al objetivo, etc., y el éxito en su realización depende de la capacidad de inferir el estado del mundo y la ubicación del robot en el mismo. Para ello es imprescindible disponer de representaciones y estrategias capaces de procesar y asimilar de manera eficiente y robusta el elevado flujo de información captado por el robot durante su movimiento. Reconstruir exhaustivamente el mundo, tal como enfatiza el paradigma clásico [Marr1982], no es una opción aceptable debido a su elevado coste computacional. Durante la última década, el paradigma de la visión activa [Aloimonos et al.1988], [Bajcsy1988], [Ballard1991], [Krotkov1987], [Yuille y Blake1992] viene abordando ésta y otras cuestiones relacionadas con el diseño de sistemas visuales artificiales óptimos en el sentido en que se enfatiza el carácter selectivo del procesamiento visual y su íntimo acoplamiento con la tarea a desarrollar, lo cual conlleva un conocimiento básico acerca del entorno y de los recursos computacionales disponibles.

La inferencia bayesiana proporciona, en combinación con la teoría de la información, un marco conceptual atractivo para formalizar el problema de la inferencia visual [Knill y Richards1996]. Asimismo, este planteamiento permite expresar de forma cuantitativa y cualitativa la optimalidad del sistema visual en el sentido en que el paradigma de la visión activa lo requiere. Por ejemplo, dada una tarea concreta (auto-localización, evitación de obstáculos, aproximación al objetivo) el teorema de Bayes proporciona una regla para cuantificar la bondad de la inferencia realizada por los distintos módulos del sistema que intervienen: filtrado [Geman y Geman1984], extracción de características [Zerubia y Chellapa1993], segmentación [Zhu y Yuille1996b], estimación de profundidad [Belhumeur1996], matching y reconocimiento [Kittler1997]. Dicha regla integra una métrica para identificar la compatibilidad de una solución propuesta con la entrada visual (verosimilitud) con el conocimiento previo del entorno disponible (información a priori). Por otro lado la teoría de la información [Cover y Thomas1991] aporta métricas (como la entropía, la información mutua o la distancia de Kullback-Leibler) y principios (como el principio MDL o de longitud de codificación mínima) que permiten, entre otras cosas: reducir la redundancia en la entrada visual [Bartlett et al.1998], reducir la complejidad de los modelos de contorno [Figuereido et al.1997], búsqueda de caminos óptimos [Coughlan y Yuille1998], determinar las características necesarias para construir modelos de imagen [Zhu et al.1997], cuantificar la efectividad de los filtros en la extracción de características [Konishi et al.1999], así como seleccionar los módulos estrictamente necesarios para resolver la tarea, en la medida en que estos aportan información de utilidad [Rimey y Brown1992].

Esta tesis incorpora elementos de inferencia bayesiana y teoría de la información, en los distintos módulos (filtrado y detección de aristas, detección de puntos esquina y uniones, agrupamiento de uniones mediante búsqueda de caminos) que intervienen en la obtención eficiente de una representación geométrica robusta y adecuada para inferir parámetros de posicionamiento, en particular la orientación relativa del robot con respecto al entorno.
Preface
Endowing a robot with the visual capabilities to survive in a partial known environment is not a trivial task. Surviving implies to develop successfully several tasks such as self-localization, obstacle avoidance, target approaching, and so on, and the success depends on the capability of inferring the state of the world and the robot position in it. To do this inference it is essential to have good representations and strategies for processing and assimilating in an efficient and robust way the huge flow of information collected by the robot while it is moving around. Exhaustive world reconstruction, as the classic paradigm emphasizes [Marr1982], is not a acceptable option due to its high computational cost. During the last decade, the active vision paradigm [Aloimonos et al.1988], [Bajcsy1988], [Ballard1991], [Krotkov1987], [Yuille y Blake1992] has been addressing this and another questions related to the design of optimal artificial visual systems, but optimal in the sense that emphasizes selective visual processing, close coupling between vision and task, which implies a good knowledge about the environment and the available resources.

Bayesian inference provides, in combination with information theory, an attractive conceptual frame to formalize the visual inference problem
[Knill y Richards1996]. This approach allows us to express in a quantitative and qualitative way the optimality of the visual system in the sense that the active vision paradigm requires. For instance, given a specific task (self-localization, obstacle avoidance, target approaching) the Bayes theorem provides a rule to quantify the goodness of a given inference performed by, for instance: filtering [Geman y Geman1984], feature extraction [Zerubia y Chellapa1993], segmentation [Zhu y Yuille1996b], depth estimation [Belhumeur1996], matching and recognition [Kittler1997]. Such a rule combines a metric to identify the compatibility of a proposed solution with the visual input (likelihood) and the prior knowledge. On the other hand, the information theory [Cover y Thomas1991] provides metrics (like entropy, mutual information and the Kullback-Leibler distance) and principles (like the MDL or minimum description length principle) which yields: reducing the redundancy of the visual input [Bartlett et al.1998], reducing the complexity of the contour models [Figuereido et al.1997], optimal path searching [Coughlan y Yuille1998], determining the necessary features to build image models [Zhu et al.1997], quantifying the effectiveness of the filters used in feature extraction [Konishi et al.1999], and selecting only those modules which are needed to solve a task by evaluating the utility of the information provide by these modules [Rimey y Brown1992].

This thesis includes elements of Bayesian inference and information theory points in several visual modules (filtering and edge detection, corner and junctions detection, junction grouping by means of path searching) which are involved in obtaining an efficient and robust geometric representation which is adequated to infer positional parameters, like the robot relative orientation with respect to the environment.

Resumen
El marco de esta tesis se centra en la extracción de características y agrupamiento perceptual en visión. Nuestro propósito principal ha sido formular y experimentar con nuevos métodos para la extracción de características (principalmente aquellos relacionados con la identificación de puntos característicos y la clasificación de uniones) y el agrupamiento (realizando conexión entre uniones). El contexto de aplicación de estos métodos, la visión en robots autónomos, nos impone restricciones especiales sobre su aplicabilidad y así se observan los siguientes requerimientos: eficiencia, robustez y flexibilidad. Estos requerimientos están presentes en todas las técnicas aportadas en esta tesis: la clasificación de uniones se realiza mediante un método voraz que se basa en estadística robusta; el agrupamiento de uniones se realiza mediante un método de búsqueda de caminos con complejidad lineal media, el cual utiliza condiciones estadísticas de poda para restringir la búsqueda de caminos estables; por último, el agrupamiento de uniones encuentra la orientación relativa entre el robot y su entorno. Sin embargo, el rango de aplicación de los métodos propuestos no está restringido a inferir la orientación relativa del robot, y puede ser extendido a otras tareas como la segmentación de imágenes, estimación de profundidad o reconocimiento de objetos.

Esta tesis está estructurada en tres partes: clasificación de uniones, agrupamiento y cálculo de la orientación relativa. Los métodos presentados en cada parte son usados por las siguientes de acuerdo a una organización de complejidad incremental: Finalizaremos esta tesis con las conclusiones y planteamientos futuros, fundamentalmente en las siguientes líneas: mejora de la localización, aplicación en tareas de segmentación, reconocimiento y estimación de profundidad, y mejora de los métodos de cálculo de orientación, fundamentalmente en su aplicación dinámica.
Abstract
This thesis focuses on feature extraction and perceptual grouping in computer vision. Our main purpose has been to formulate and test new methods for feature extraction (mainly those related to corner identification and junction classification) and grouping (through junction connection). The context of application of these methods, robot vision, imposes special constrains over their applicability and thus, the following requirements are observed: efficiency, robustness, and flexibility. These requirements are present in almost all the techniques presented in this thesis: Junction classification is performed by greedy method that relies on sound statistics; Junction grouping is performed by a path-searching method of linear complexity on average, which is based on pruning conditions to constrain the search of stable paths, and such conditions rely on statistical information; and junction grouping yields speeding up the voting scheme used to find the relative orientation between the robot and the environment. However, the range of application of the proposed method is not restricted to infer relative orientation, and can be extended to other tasks like image segmentation, depth estimation or object recognition.

This thesis is structured in three parts which cover junction classification, grouping and relative orientation, yielding a bottom-up exposition: This thesis is completed by final discussion and conclusions. We have identified several issues which can be improved in the future. Some of these issues are referred to the quality of the representations, and others refer to applying our grouping strategy in other tasks like segmentation or even object recognition.

Índice

Apéndices




This document was translated from LATEX by HEVEA and HACHA.