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.
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:
-
En primer lugar, abordaremos el problema de la clasificación de uniones. Para ello
nos apoyaremos en la detección de puntos característicos, es decir, de puntos donde la
curvatura de los contornos es alta. También son puntos característicos aquellos puntos donde
convergen varias aristas. Hemos comparado dos de los métodos de detección de dichos puntos,
el operador de SUSAN y el de Nitzberg. Hemos determinado en qué situaciones utilizaremos uno y otro.
Siendo las uniones estructuras geométricas que emanan de puntos característicos, definimos dichas
uniones de forma paramétrica. Formulamos el problema de su clasificación en términos de la búsqueda
de los parámetros que mejor se ajustan a la evidencia de la imagen. Dicha búsqueda se basa en la
minimización de funciones de energía. Definimos dos métodos basados en inferencia bayesiana.
Hemos realizado experimentos para comprobar la eficacia de estos métodos, presentando resultados
obtenidos al aplicarlos sobre imágenes tanto de interior como de exterior. Ambos métodos presentan
buenos resultados en imágenes de interior. Sin embargo, cuando procesamos imágenes de exterior, y
debido a la aparición de objetos no estructurados (árboles, carteles, etc.) el elevado número de
puntos candidatos obtenidos genera un gran número de uniones ficticias. También hemos observado que
los métodos propuestos son muy dependientes de la localización del centro de la unión. Malas
localizaciones de dicho centro provocan errores en la clasificación de los límites angulares.
Hemos analizado la eficiencia y robustez de estos métodos propuestos frente a un método reciente
basado en programación dinámica, Kona, obteniéndose un error medio y un tiempo de procesamiento
menor cuando aplicamos nuestros operadores. Nuestro algoritmo de segmentación lineal detecta un
menor número de falsos positivos, es decir, límites que en realidad no lo son. Sin embargo, nuestro
algoritmo de modelización de aristas tiene un tiempo de computación menor y deja un menor número de
límites sin detectar.
En algunas situaciones se detectan falsos positivos o límites inexistentes, como por ejemplo cuando
se invaden dominios de otras regiones. Este caso se puede salvar recurriendo a la prolongación de la
unión para buscar otra unión en la dirección que marca el límite de la sección angular. Esta
propuesta es la que desarrollaremos en el siguiente punto de la tesis.
- El objetivo de la segunda parte de la tesis es definir estrategias de conexión de uniones,
lo cual se plantea como la búsqueda de un camino, marcado por el contraste de la
imagen. Dicha búsqueda se basa en un algoritmo A* bayesiano, que nos permite centrarnos en
la extracción del camino verdadero en una población de falsos caminos, en lugar de buscar el
mejor camino en una población de caminos candidatos. Esta simplificación no
asegura la optimalidad del resultado, pero permite obtener un coste lineal. El coste de un camino
vendrá dado por la suma de dos componentes, la componente de intensidad y la geométrica. La
componente de intensidad nos da una medida de la evidencia de arista. La geométrica nos permite
modelar la rigidez de los caminos a explorar. Dentro de la componente de intensidad presentamos dos
modelos a seguir. En uno de ellos utilizamos un filtro no lineal basado en el número de votos
obtenidos para un segmento dado. Para ello se han tomado estadísticas previas, determinando la
respuesta del filtro para un determinado operador de gradiente (en nuestro caso hemos utilizado
SUSAN) cuando el segmento se encuentra encima de una arista y cuando se encuentra fuera de ésta. En
el otro modelo, el de modelización de aristas, las estadísticas se han obtenido de un trabajo
previo y modelamos tanto la componente de magnitud del gradiente como su orientación. Al igual que
tenemos dos términos, consideramos dos umbrales, el de intensidad y el geométrico, que sirven para
modelar la evidencia de gradiente y la rigidez del camino, respectivamente. El umbral de
intensidad, nos modela la cantidad de evidencia que debe tener debajo un bloque de segmentos para
considerarlo válido. Si aumentamos este umbral, sólo nos quedaremos con aquellos caminos que estén
encima de un gradiente con mucha magnitud. Al disminuir el umbral permitimos que caminos con
poca evidencia (magnitud de gradiente) sobrevivan a la poda. En cuanto al umbral de geométrico,
cuando lo disminuimos, siempre dentro de los límites teóricos establecidos, permitimos caminos poco
rígidos, mientras que si aumentamos el umbral sólo permitimos caminos con una variación de ángulo
entre segmentos muy pequeña.
Una vez definidos los dos modelos, presentamos resultados obtenidos al aplicarlos sobre imágenes
tanto de interior como de exterior. Al igual que en los métodos de clasificación de uniones, el
método propuesto presenta buenos resultados en imágenes de interior, teniendo una respuesta no tan
buena en entornos no estructurados.
El método propuesto es robusto frente a posibles errores en la localización de los límites
angulares. Esto es debido a que inicializamos la búsqueda con un margen lo suficientemente grande
para que se subsanen estos posibles errores. También es robusto a la no localización de un límite
angular, ya que, dadas dos uniones existen dos formas de conectarlas: trazar caminos en ambas
direcciones.
Hemos comprobado la ganancia en calidad de las uniones detectadas al aplicar el método de
agrupamiento. Comprobamos que se produce una mejora notable en cuanto al número de límites de
secciones angulares falsos eliminados. También mejora el error angular cometido en el cálculo de
dichos límites. De esta forma estamos introduciendo una retroalimentación de un proceso de alto
nivel en otro de un nivel inferior.
- Finalmente, abordamos la obtención del ángulo de
orientación de la cámara. Partimos de un novedoso método de estimación que consiste en un proceso
de votación basado en un criterio bayesiano, utiliza información bayesiana de pertenencia de un
determinado píxel a una arista. Hemos realizado experimentos para comprobar su funcionamiento,
proponiendo mejoras para solventar algunos problemas. Se ha comprobado que el tiempo de ejecución
es excesivo para el el dominio de trabajo en el que estamos interesados, la robótica móvil. Por
ello y haciendo uso de nuestro método de agrupamiento de uniones, hemos desarrollado un nuevo
método que hace uso de la misma formulación bayesiana. Este método presenta una mejora
sustancial en cuanto a tiempo de computación y el error medio cometido es prácticamente
despreciable.
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:
-
Junction Classification: It relies on combining corner detectors and
template matching. Corner detection is performed through two well
known operators: SUSAN and Nitzberg. These operators provide an
initial localization of the junction center. Given this
localization, junction classification is posed in terms of
finding the set of angular sections, or wedges, that
explain as better as possible the underlying evidence in the
image. We propose two greedy methods which relies on elements of
Bayesian inference. These methods are tested with indoor and
outdoor images in order to identify their robustness to noise
and also to bad localizations of junctions centers. Experimental
results show that these methods are saver than other methods
recently proposed, like Kona, and their computational efficiency
is even better. However, we have detected some problems due to
the local extent of junction detection. These problems and those
derived from bad center localization can be aliviated through
local-to-global interactions, and these interactions are
inferred by grouping processes.
- Grouping: Using classified junctions as starting elements, this
stage is performed by finding connecting paths between wedge limits belonging
to pairs of junctions, and these paths exist when there is sufficient contrast or
edge support below them. Given that corners are usually
associated to points of high curvature in the image, it can be
assumed that connecting paths must be smooth if they exist.
Contrast support and smoothness are quantified by a cost
function. As it can be assumed that there will be no more than
one path between two junctions through a pair of wedge limits,
such a path can be found by the Bayesian version of the well
known A* algorithm. This method recently proposed
searches the true path, according to the cost function, in a
population of false path, instead of the best paths among a
population of possible paths. Such a simplification yields a
computational average cost which is linear with the length of the
path. We propose two versions of the cost functions and explore the
possibilities of the method for the task at hand by selecting
adequate thresholds which control the penalization introduced by
the lack of support or smoothness. Penalized partial paths can
be discarded by a pruning rule. We also modify this rule to
provide stronger pruning although the admissibility of the
algorithm is not guaranteed in this case. Grouping is completed
by end-path conditions, and the robustness of the process is
ensured by bidirectional search. Experimental results show that
the grouping stage improves individual junction identification,
and in this sense grouping gives feedback to a low level task.
But grouping also provides a schematic representation which is
useful to higher-level tasks like computing relative orientation
from a single image.
- Relative orientation: Grouping results followed by
straight line detection are very useful to compute the relative
orientation between the observer and the environment. A recent
proposal, which relies on bayesian inference, has proved that
this task can be performed by using a single image, at least
when horizontal viewing direction is assumed. This method uses
perspective and assumes that lines follow a particular
configuration known as Manhattan world. We have replaced the
original pixel-based strategy by the edges resulting from
grouping in the preceding stage, yielding robust and fast
results.
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.