Previous Contents Next

Capítulo 3   Agrupamiento de uniones

Un segundo paso en nuestra propuesta es la creación de un mapa planar mínimo que describa la imagen y la relación entre las uniones. En esta parte tomaremos como entrada las uniones clasificadas con el detector de uniones descrito anteriormente. A partir de dichas uniones pretendemos crear una estructura geométrica que describa las relaciones entre éstas y las aristas presentes en la imagen. Por supuesto, cuanta más información (mayor número de uniones y de aristas entre estas) mejor definida estará la imagen, pero buscaremos el mínimo número de uniones y aristas necesario para realizar una descripción aceptable, en términos de su ajuste a la geometría de la imagen, con objeto de simplificar la complejidad de tareas subsiguientes. En este sentido, aplicaremos el criterio de longitud de descripción mínima.

El esquema clásico de agrupamiento utilizado en visión computacional
[Lowe1985], [Trucco y Verri1998], [Ullman1996] consiste en agrupar aristas por proximidad y por similitud en orientación y longitud. Sin embargo, los elementos a agrupar en nuestra propuesta son las uniones. Pretendemos explotar la información de conexión que nos viene dada por el gradiente de la imagen.

Como ya hemos adelantado previamente, los problemas que nos vamos a encontrar una vez detectadas las uniones son los siguientes:
Errores de localización
Pueden aparecer uniones que no se corresponden con ninguna unión real en la imagen. Debido a la presencia de ruido existe una posibilidad de detectar uniones en posiciones erróneas. También la discretización de la imagen juega un papel importante en la detección de uniones erróneas.
Errores de clasificación
Algunas uniones son ficticias. Esto surge también debido a la discretización de la imagen: algunos objetos cuyos bordes son curvos provocan que se detecten uniones en dichos bordes. Realmente existe una arista debajo, pero el eliminar dicha unión no implica perder información.
Falsos negativos
Es posible que no se detecten ciertas uniones. Puede ser debido a la no detección del candidato por parte del filtro de detección de puntos característicos o bien por que el algoritmo de clasificación de uniones desecha el candidato por tratarse de una arista terminal o por problemas derivados de la pérdida de gradiente.
El método a utilizar para el agrupamiento de uniones tiene que tener todo esto en cuenta y tratar de solventar las problemáticas presentadas.

 

Figure 3.1: Imagen original (izquierda) junto con el resultado de calcular el gradiente (derecha).
Estamos interesados en encontrar caminos que conecten uniones, es decir, caminos a lo largo de aristas que conecten uniones, siempre y cuando dichas aristas existan. El resultado de calcular el gradiente de una imagen se muestra en la Figura 3.1. Vamos a enfocar el problema del agrupamiento como la búsqueda de un camino entre dos uniones. Si realmente existe una arista entre dos uniones, la magnitud del gradiente de la imagen nos proporcionará dicho camino.

En este capítulo vamos a presentar un método de búsqueda de caminos que utiliza la información del gradiente de la imagen para establecer el soporte de arista. Primero, veremos los métodos previos utilizados para el cálculo del ángulo de orientación en la Sección 3.1.

Como hemos comentado previamente, vamos a realizar la conexión entre dos uniones haciendo uso de la información de gradiente. Para la búsqueda de caminos entre uniones nos basaremos en la propuesta de [Yuille y Coughlan1999] que extiende el trabajo previo de [Geman y Jedynak1996] para la detección y seguimiento de carreteras en imágenes tomadas desde satélite.

El resto del capítulo se organiza de la siguiente manera: la Sección 3.2 detalla cómo vamos a modelar un camino. En la Sección 3.3 explicaremos el algoritmo de seguimiento de caminos propuesto. Acabamos presentando el algoritmo completo con resultados y conclusiones del método.

3.1   Agrupamiento de características

El agrupamiento de características se puede definir como [Trucco y Verri1998]: Dado un conjunto de características en una imagen, se trata de decidir que grupos de características forman parte del mismo objeto con mayor probabilidad, sin tener conocimiento de qué objetos estamos buscando. Las características a utilizar pueden ser puntos, líneas, segmentos curvos, uniones, etc. El agrupamiento sirve de base en diversas tareas, como el reconocimiento de objetos [Ullman1996]. Un buen agrupamiento puede restringir las posibles interpretaciones de un objeto debido a que existe un número limitado de posibles combinaciones de dichas características como, por ejemplo, el caso de las uniones, tal como fue propuesto en [Waltz1975] y [Malik1987].

Se han propuesto diversas formas de llevar a cabo este agrupamiento de características. Un trabajo ya clásico es [Lowe1985], donde se discute el agrupamiento perceptual desde el punto de vista computacional y psicofísico. En [Sarkar y Boyer1993] se realiza una revisión de los distintos métodos sobre agrupamiento y organización perceptual. La mayoría de métodos realizan agrupamiento de aristas, utilizando criterios de proximidad, longitud de arista y orientación. Para el agrupamiento de uniones existe muy poco trabajo desarrollado. En [Brunstrom et al.1996] se propone un esquema de agrupamiento de uniones mediante seguimiento de caminos. Este método fija una dirección de búsqueda propuesta por una unión y utiliza un esquema de filtro de Kalman para seguir hasta la siguiente unión. La búsqueda se realiza utilizando un círculo que se va desplazando a saltos por el gradiente, buscando zonas con un gradiente similar. Los parámetros que rigen la búsqueda son la longitud de salto y el dominio del círculo.

En [Matas y Kittler1995] se propone un método que realiza detección, agrupamiento y etiquetado de las uniones en el mismo proceso. Para ello aplican un detector de aristas y utilizan los finales de aristas y las intersecciones entre ellas para realizar la detección y el etiquetado. Proponen un modelo de etiquetado de relajación probabilístico. El algoritmo presenta buenos resultados en imágenes con poco nivel de ruido y donde los contornos de los objetos están bien delimitados. Además el tiempo de ejecución fue de 2 segundos con únicamente 90 aristas presentes.

3.2   Modelado de caminos

Definimos un camino P de longitud N como una colección de segmentos conectados consecutivos p1, p2, ..., pM, donde M no es necesariamente constante para todos los caminos. El camino comienza en una unión con centro (x,y) y tiene un ángulo de salida q, correspondiente a uno de las direcciones principales de la unión. Puesto que los puntos esquina vienen asociados a puntos de elevada curvatura, asumimos que la curvatura de los caminos entre uniones es suave. Para cada par de segmentos consecutivos definimos las variables a1, a2, ..., aM-1 como los ángulos que forman dichos segmentos. En concreto, ai es el ángulo que forman los segmentos pi y pi+1. Utilizando el enfoque bayesiano de Yuille y Coughlan [Yuille y Coughlan1999], el camino óptimo P* maximiza la siguiente función de energía:
E P({pj, aj}) =
N
å
j=1
log {
Pon(f
 
(pj)
)
Poff(f
 
(pj)
)
}+
N-1
å
j=1
log {
P
 
G
(aj+1 -aj)
U (aj+1 - aj)
}     (3.1)

El primer término de esta función se denomina recompensa de intensidad y está relacionado con la probabilidad de que el segmento se encuentre o no encima de una arista de la imagen. En la Sección 3.2.1 se definen dos posibles filtros a utilizar y la funciones de distribución obtenidas.

El segundo término es la recompensa geométrica y codifica la rigidez de los caminos. Variando esta componente podemos conseguir caminos más rígidos (rectas) o muy sinuosos. En la Sección 3.2.2 se define este término geométrico.

El logaritmo del ratio de las probabilidades representa el ratio de verosimilitud que minimiza errores de clasificación y tiene el siguiente comportamiento: si la función en el numerador tiene una valor superior al del denominador, para una misma instancia de la variable, el logaritmo devuelve un valor positivo. Sin embargo si ocurre al contrario, el valor del denominador es mayor, entonces devolverá un valor negativo.

3.2.1   Definición de la componente de intensidad

Para definir la componente de intensidad, haremos uso de dos filtros que aplicaremos a la imagen. El primero de ellos utiliza la información estadística descrita en la Sección 2.5. El segundo utiliza un filtro no lineal definido previamente en [Geman y Jedynak1996].

Filtro de modelado de aristas

Tal como se definió en la Sección 2.5 aplicaremos un filtro gausiano a la imagen: DGs=1* I. La respuesta de este filtro se modela mediante estadísticas obtenidas de imágenes. Estas estadísticas se obtuvieron en [Konishi et al.1999]. Dado un segmento pi, el valor de Pon y Poff se obtiene de la siguiente manera:
Pon(pi)=
 
å
uÎ pi
Pon(E
 
u
)Pang(f
 
u
-b)    y    Poff(pi)=
 
å
uÎ pi
Poff(E
 
u
)U(f
 
u
)     (3.2)
donde u son los puntos del segmento pi, Eu es la magnitud del gradiente en el punto u, b es el ángulo de la normal al segmento, su es la orientación del gradiente en el punto u y U(·) es una distribución uniforme. La Figura 3.2 muestra las estadísticas obtenidas con este filtro y el logaritmo del cociente entre Pon y Poff.

Figure 3.2: Estadísticas de las aristas: Pon y Poff, junto con el logaritmo del ratio entre las dos.

Filtro no lineal

Figure 3.3: Las posibles configuraciones del filtro (izquierda), nomenclatura de los píxeles (derecha arriba) y los diez test realizados a lo largo de una determinada configuración (derecha abajo).
La probabilidad de que un segmento se encuentre encima de una arista se modela mediante una función de distribución P(f(pj)) sobre las respuestas de un filtro no lineal f(pj)=f(|Ñ I (pj)|), donde |Ñ I (pj)| es la magnitud del gradiente. La función de distribución P(f(pj)) se modela dependiendo de la posición relativa entre un segmento pj y la arista, y se define en los siguientes términos:
P(f
 
(pj)
) = ì
í
î
Pon(f
 
(pj)
)
   pj Î P
*
 
Poff(f
 
(pj)
)
   en otro caso.
    (3.3)
donde Pon(f(pj)) y Poff(f(pj)) son las distribuciones de probabilidad de las respuestas de los segmentos encima y fuera de una arista. Estas funciones se obtienen empìricamente, calculando las estadísticas de las respuestas del filtro cuando localizamos el segmento encima de la arista y cuando lo localizamos fuera de ella. Para el diseño del filtro de intensidad nos hemos basado en el propuesto en [Geman y Jedynak1996], filtro que también utilizaron Yuille y Coughlan [Yuille y Coughlan1999] y que detallamos a continuación.

Primero aplicamos el operador de SUSAN para aristas sobre la imagen. Sobre el resultado aplicamos el siguiente test:
|I
 
t1
-I
 
t4
| < min {|I
 
t3
-I
 
t1
|, |I
 
t2
-I
 
t1
|, |I
 
t5
-I
 
t4
|, |I
 
t6
-I
 
t4
|}     (3.4)
donde Iti indica el valor de intensidad del correspondiente píxel ti (ver Figura 3.3). Este test lo realizamos por todos los píxeles a lo largo del segmento, hasta un total de 10. En la Figura 3.3 se muestran las distintas configuraciones utilizadas en la implementación así como un ejemplo de los filtros utilizados. Una vez realizados todos los test para un segmento, tendremos un número de respuestas afirmativas entre 0 y 10. Valores altos indicarán mayor presencia de arista. Valores bajos constatarán poca presencia de arista. Se han realizado 200 mediciones del filtro situando el segmento sobre una arista y otras 200 sobre fondo. Las funciones de distribución obtenidas, junto con el logaritmo del ratio entre las dos, se muestran en la Figura 3.4.



Figure 3.4: Funciones de distribución de probabilidad: Pon y Poff, junto con el logaritmo del ratio entre las dos.

3.2.2   Definición de la componente geométrica

La recompensa geométrica permite codificar la rigidez del camino. En determinadas ocasiones podemos desear caminos completamente rectos y en otras podemos desear que la configuración del camino sea libre. Para ello tenemos la recompensa geométrica que está compuesta por dos funciones de distribución: PG(aj+1 -aj) y U (aj+1 - aj). PG modela una cadena de Markov de primer orden sobre las variables de orientación aj. Esta función se define mediante una exponencial negativa:
P
 
G
( aj) µ exp{ -
C
2A
| aj|}     (3.5)
donde: aj=aj+1 - aj, A es el máximo ángulo entre dos segmentos consecutivos y C modula la rigidez del camino. Por otro lado, U (aj+1 - aj) es la distribución uniforme de la variación angular y se introduce para mantener las componentes geométrica y de intensidad en el mismo rango. En la Figura 3.5 se muestran estas funciones.
Figure 3.5: Funciones de distribución de probabilidad: P G y U, junto con el logaritmo del ratio entre las dos

3.3   Seguimiento de caminos

Encontrar caminos en escenas ruidosas y/o con fragmentación de aristas puede llegar a ser una tarea de difícil solución y esta tarea debe ser realizada en un corto intervalo de tiempo, especialmente cuando se imponen restricciones de tiempo real. Coughlan y Yuille [Coughlan y Yuille1998] recientemente han propuesto un método denominado A* bayesiano que explota el conocimiento estadístico asociado a las componentes de intensidad y geometría. Este método surge de un análisis teórico previo [Yuille y Coughlan1997] sobre la conexión entre el algoritmo Twenty Question de Geman y Jedynak [Geman y Jedynak1996] y A*, el algoritmo clásico utilizado en Inteligencia Artificial [Pearl1984]. A continuación se describe el enfoque genérico del algoritmo A* bayesiano y su adaptación a la búsqueda de caminos entre uniones.
Figure 3.6: Ejemplo de árbol de búsqueda. El factor de ramificación Q es tres.

3.3.1   Algoritmo y restricciones

Dado el centro de una unión (x0,y0) y una orientación q0, el algoritmo explora un árbol cuya raíz es el centro de la unión y cada rama es un posible camino (ver Figura 3.6). Cada arista entre dos nodos se corresponde con un segmento. Cada segmento puede expandir Q sucesores, por ello tenemos QN caminos posibles y en consecuencia la búsqueda exhaustiva no es practicable. El algoritmo A* bayesiano reduce la conducta conservadora del clásico A* explotando el hecho de que queremos detectar un camino en vez del encontrar el mejor de todos. En nuestro caso sabemos que puede existir un camino entre las uniones a unir. Como consecuencia de esto tenemos un único camino real frente a un gran número de caminos falsos. Podemos reducir la complejidad del problema eliminando (podando) caminos parciales cuya recompensa acumulada sea muy baja. El algoritmo evalúa las recompensas de intensidad y geométrica de los últimos N0 segmentos del camino eliminando aquellos caminos cuya recompensa ponderada está por debajo de un cierto umbral, es decir:
1
N0
N
å
j=N-N0
log {
Pon(pj)
Poff(pj)
} < T, o
1
N0
N
å
j=N-N0
log {
P
 
G
( aj)
U ( aj)
} < T     (3.6)
donde T y T son los umbrales de intensidad y geométrico que modulan la conducta de poda del algoritmo. Estos parámetros establecen la recompensa (en los últimos segmentos) mínima que un camino necesita para sobrevivir y su valor no es arbitrario. Están relacionados con las distribuciones de probabilidad utilizadas para diseñar las recompensas de intensidad y geométricas. En [Coughlan y Yuille1998] se demuestra que estos valores umbral tienen que encontrarse en los siguientes intervalos:
- D(Poff||Pon) < T < D(Pon||Poff), - D(U
 
G
||P
 
G
) < T < D(P
 
G
||U
 
G
)     (3.7)
donde D es la divergencia de Kullback-Leibler que nos mide lo diferentes que son dos distribuciones. Este distancia es siempre mayor o igual a cero, siendo cero cuando ambas distribuciones son la misma, y se define de la siguiente manera:
D(P1||P2)=
M
å
j=0
P1(xj)log
P1(xj)
P2(xj)
    (3.8)
siendo M el número de elementos del dominio en el cual están definidas ambas distribuciones.

El algoritmo encuentra el mejor camino que sobrevive a la poda. El ratio de convergencia es O(N). Los valores T y T se suelen escoger cercanos a los límites superiores, para que la poda sea mayor. Si las distribuciones Pon y Poff son muy similares, el algoritmo será conservativo y no podará demasiados caminos. El máximo rendimiento se consigue cuando ambas distribuciones son muy dispares. En definitiva, el grado de solape es inversamente proporcional a la potencia de discriminación del filtro de gradiente. El mismo razonamiento se sigue para P G and U G.

La aplicación de este algoritmo en el contexto de agrupamiento de uniones motiva la extensión de la regla de poda. Consideramos la estabilidad de caminos largos frente a los cortos. Los caminos más largos estarán más cerca del camino verdadero que los cortos debido a que han sobrevivido a un mayor número de podas. Por ello podemos eliminar aquellos caminos cuya longitud Nj sea menor que la del mejor camino hasta el momento Nmejor menos una constante, es decir, eliminaremos aquellos caminos que no cumplan:
Nj > Nmejor-zN0
donde z>0 es un parámetro que permite restringir o aumentar la poda. Valores altos de z provocan una mayor poda y un mayor riesgo de perder el camino y valores bajos conservan todos los caminos ralentizando el proceso. Dicho parámetro debe fijarse de forma experimental.

3.3.2   Finalización del camino

El algoritmo selecciona para expansión el mejor camino parcial hasta el momento y le aplica la regla de expansión, generando tres puntos de extensión. Consideramos que hemos alcanzado el final del camino cuando encontramos una unión en una pequeña vecindad alrededor del punto final del camino. Para comprobar si existe una determinada unión en una vecindad hemos utilizado árboles de rango, que son estructuras geométricas [de Berg et al.1997] que permiten realizar de forma eficiente consultas dentro de un rango. El coste de generar el árbol es O(Jlog J) donde J es el número de uniones detectadas. El coste de realizar una consulta es O(K+log J) donde K es el número de elementos devueltos. En el Apéndice B se detalla la construcción y consulta de esta estructura. Si el camino actual encuentra una unión, hemos alcanzado una unión, por lo que el algoritmo finaliza y conecta ambas uniones.

 

Figure 3.7: Situaciones a detectar cuando nos quedamos sin caminos.
Por otro lado, la búsqueda puede finalizar sin encontrar ninguna unión. Esto sucede cuando todos los caminos parciales han sido eliminados. Uno a uno se van eliminando debido a la pérdida de alguna de las recompensas. Podemos distinguir entre dos situaciones: La Figura 3.8 muestra un ejemplo de generación de caminos. Partimos del límite de la sección angular de una unión y tomamos su ángulo de salida como inicialización del camino. A continuación comenzamos a explorar dicho camino aplicando las restricciones comentadas anteriormente. En el momento en que se encuentre una unión en una cierta vecindad alrededor del final del camino actual, podemos finalizar la búsqueda. Sólo mostramos el mejor camino hasta ese momento. Como se puede observar en la figura, hemos encontrado una unión y procedemos a marcar el límite de la unión entrante como visitado y conectamos ambas uniones. En la siguiente sección se comenta el algoritmo completo de agrupamiento de uniones.

       
Figure 3.8: Ejemplo de inicialización, búsqueda y finalización de camino.

3.4   Agrupamiento de uniones

En esta sección detallamos el algoritmo de agrupamiento de uniones. El algoritmo toma como entrada el conjunto de uniones obtenidas con el detector de uniones propuesto anteriormente. Una vez procesadas todas las uniones devuelve un mapa de la escena, donde cada vértice del mapa es el centro de una unión y las aristas se corresponden con los caminos encontrados entre las uniones. Antes de detallar el algoritmo de agrupamiento pasamos a comentar el algoritmo de búsqueda de camino que será utilizado por el de agrupamiento para encontrar los caminos. El algoritmo se muestra en la Figura 3.9. El umbral NT marca la longitud mínima que un camino debe tener para que sea considerado como tal.

Algoritmo de búsqueda de camino Alg_ABayes
Entrada: xc, yc, q centro y ángulo de salida del camino a buscar. Ie imagen de gradiente.
Salida: Verdadero si ha encontrado camino y falso si no lo ha encontrado. También devuelve el Camino y Union_detectada.
Generar Q caminos. Cada camino está compuesto de un segmento que parte del punto pasado como parámetro. El segmento está compuesto por dos puntos. El primero de ellos tendrá como punto inicial (xc, yc) y como final (xc+ls*cosq, xc+ls*sinq). Los dos siguientes caminos se generan de la misma forma pero variando en ±b grados el ángulo de salida y así sucesivamente.
El algoritmo utiliza una lista de caminos LF. Al principio esta lista está compuesta por los Q caminos generados en el paso anterior. Cuando insertamos en esta lista lo hacemos de forma ordenada según el valor de E de cada camino, siendo el primer elemento de la lista el de menor E. De esta manera nos evitamos el reordenar la lista.

Mientras siempre hacer /* Bucle infinito */
 Si LF está vacía entonces
   Si longitud(Mejor_camino) < NT entonces
     Devolver Falso.
   Sino
     Devolver Cierto, Mejor_camino. No hemos alcanzado ninguna unión. El punto de terminación de Mejor_camino es un posible candidato a unión.
   FinSi
 FinSi
 Seleccionamos aquel elemento de LF con menor valor de E y lo eliminamos de la lista. Al estar ordenada de menor a mayor simplemente seleccionamos el primer elemento de la lista. Lo llamaremos Mcamino.
 Si longitud(Mejor_camino) < longitud(Mcamino) entonces
   Mejor_camino=Mcamino. Almacenamos una copia del mejor camino hasta el momento para el caso de que no encontremos ninguna unión y eliminemos todos los caminos.
 FinSi
 Eliminamos todos los caminos de LF cuya longitud sea inferior a la de Mcamino menos una constante.
 Expandimos el camino actual. A partir del último segmento de Mcamino generamos Q caminos, de la misma forma que hemos generado los primeros caminos. Los insertaremos en LF siempre y cuando su recompensa geométrica y de intensidad en los últimos segmentos supere el umbral T y T, respectivamente.
FinMientras

Figure 3.9: Algoritmo de búsqueda de camino.

En la Figura 3.10 se puede observar algunos caminos generados. El algoritmo mostrado en la Figura 3.11 es el que realiza el agrupamiento de las uniones visitando todas las uniones.
Figure 3.10: Generación de caminos.
Algoritmo de agrupamiento Alg_Agr
Entrada: C={Ui:(xci, yci, q1i, q2i, ..., qli)} conjunto de uniones detectadas, con l no necesariamente el mismo para todo i. Ie imagen de gradiente.
Salida: Mapa planar detectado.
Para cada unión U de C hacer
 Para cada límite qi de las secciones angulares de U hacer
   Si qi ya ha sido visitado entonces continuar con el siguiente límite
   Sino
     Marcar qi como visitado
     Introducir las coordenadas del centro de la unión como un vértice del mapa.
    Si Alg_ABayes ( Ie, xc, yc, qi, Camino, Union_encontrada) entonces
       Incorporar Camino al mapa junto con las coordenadas del centro de Union_encontrada.
       Marcar como visitado aquel o aquellos límites de Union_encontrada cuya diferencia angular con respecto al ángulo de entrada del camino a la unión sea menor de qf.
    FinSi
   FinSi
 FinPara
FinPara

Figure 3.11: Algoritmo de agrupamiento.

Usamos el etiquetado de los límites de las secciones angulares para evitar que se recorra el mismo camino dos veces: en un sentido y en el contrario. Esta redundancia proporciona robustez en el sentido de que si un camino no se obtiene en un sentido, se podría obtener en el contrario.

Este método genera una representación de nivel medio en forma de mapa o grafo de conectividad. Podemos usar la información contenida en los caminos para tareas de segmentación, seguimiento de características y reconocimiento. La Figura 3.12 muestra dos ejemplos de aplicación del algoritmo (siendo la componente de intensidad el filtro no lineal) a las uniones obtenidas con el detector de uniones propuesto. Otros ejemplos son los mostrados en las Figuras 3.13, 3.14 y 3.15, en las cuales se ha utilizado la componente de intensidad del filtro de modelado de aristas. Los parámetros utilizados en la implementación fueron: Al igual que en el capítulo anterior, los experimentos se realizaron sobre secuencias de interior e imágenes de exterior. El tiempo medio de ejecución fue de 5 segundos, sin contar el tiempo de procesamiento de las uniones.

 
Figure 3.12: Ejemplos de aplicación del algoritmo de agrupamiento (componente de intensidad: filtro no lineal).
 
Figure 3.13: Ejemplos de aplicación del algoritmo de agrupamiento (componente de intensidad: filtro de modelado de aristas).
 
Figure 3.14: Ejemplos de aplicación del algoritmo de agrupamiento (componente de intensidad: filtro de modelado de aristas).
 
Figure 3.15: Ejemplos de aplicación del algoritmo de agrupamiento (componente de intensidad: filtro de modelado de aristas).

3.4.1   Conexión punto a punto

Comparamos ahora el método anterior con un método de búsqueda mediante fuerza bruta. Partimos de los puntos característicos obtenidos por cualquier detector (por ejemplo, SUSAN o Nitzberg). Este método consiste en ir visitando cada par de puntos característicos y comprobando si en el segmento definido por estos puntos existe evidencia de arista en la imagen. Para comprobar si existe evidencia vamos a utilizar la información estadística presentada en la Sección 2.5. Siendo r el segmento definido por dos puntos característicos y b el ángulo de la normal a ese segmento, nuestra función de energía viene dada por:
E (r)= ó
õ
 


r
log
Pon(E
 
u
|b)
Poff(E
 
u
)
du
y en el caso discreto:
E (r)=
 
å
uÎ r
log
Pon(E
 
u
|b)
Poff(E
 
u
)

Esta función de energía nos permite cuantificar si existe evidencia de arista debajo del segmento definido por los puntos característicos. La determinación de si existe evidencia o no, viene dada por el criterio de corte detallado en la Sección 3.3 y reflejado en la Ecuación 3.6.
 
Figure 3.16: Aplicación del método de agrupamiento exhaustivo.
En la Figura 3.16 se muestra un resultado de aplicar este método. Como se puede observar existen segmentos que mantienen evidencia a pesar de no tener un soporte de arista en buena parte de su longitud. Esto es debido a que la parte que sí tiene soporte compensa la parte que no tiene. Esto provoca que se detecten demasiadas aristas entre puntos. Además, otro problema es que es poco flexible a pequeños cambios en la posición de los puntos característicos. Es decir, pequeños errores en la localización de los puntos esquina pueden provocar que perdamos la evidencia de la arista.

El tiempo medio de ejecución fue de 90 segundos. El tamaño de las imágenes utilizadas es de 640x480 y el número medio de puntos característicos detectados fue de 200.

Tanto el tiempo de ejecución como los problemas encontrados desaconsejan el uso de este método para el agrupamiento de uniones.

3.5   Variación de las componentes geométrica y de intensidad

Hemos realizado experimentos variando el umbral de corte de las componentes geométrica y de intensidad. La Figura 3.17 muestra la imagen utilizada para los experimentos. La Figura 3.18 muestra el resultado de variar la componente de intensidad. Para la imagen superior se utilizó un umbral de corte de 1 y para la inferior de 2. Como se puede observar cuando aumentamos el umbral de corte sólo sobreviven aquellos caminos donde la magnitud de gradiente es mayor. Al disminuir el umbral pasa lo contrario, permitiendo caminos con una magnitud de gradiente muy baja. El tiempo de procesamiento aumenta conforme disminuimos el umbral de corte y se debe a que se exploran muchos más caminos.
Figure 3.17: Imagen utilizada en los experimentos de variación de los umbrales de corte.
La imagen superior de la Figura 3.19 muestra el resultado de aplicar un umbral de -1. En la imagen inferior se muestra el resultado de variar la componente geométrica. En este caso hemos aplicado un umbral de -0.5. La Figura 3.20 muestra el resultado de aumentar el umbral de la componente geométrica a 0.5 (arriba) y 1 (abajo). Como se puede observar, conforme aumentamos la componente geométrica, sólo sobreviven aquellos caminos cuyo cambio de curvatura es poco significativo.

 
Figure 3.18: Variación del umbral de corte de la componente de intensidad.
 
Figure 3.19: Variación del umbral de corte de la componente de intensidad y geométrica.
 
Figure 3.20: Variación del umbral de corte de la componente geométrica.

3.6   Clasificación de uniones

Como ya vimos en el capítulo anterior, los métodos de localización y clasificación de uniones son muy locales. Por ello, el error cometido es alto debido al ruido localizado en las proximidades de uniones y esquinas. El método de agrupamiento de uniones propuesto en este capítulo sirve para disminuir el efecto del ruido cometido en la clasificación de uniones. Con este método extendemos la unión en la dirección indicada por los límites de las secciones angulares. Al permitir una cierta flexibilidad en la dirección a seguir, estamos solventando posibles errores en la localización de dicho límite. También, si un camino no sobrevive en la primera fase de la búsqueda, desechamos ese camino. Lo que estamos haciendo es eliminar aquellos límites que, al extenderlos, no tengan suficiente evidencia de arista. En la Figura 3.21 mostramos varios ejemplos de cómo mejora el proceso de agrupamiento de uniones.

Con este proceso estamos mejorando los resultados obtenidos en la fase de detección y clasificación de uniones. Estamos produciendo una retroalimentación de un nivel superior a un nivel inferior para mejorar sus resultados.

Figure 3.21: Mejora producida al introducir el agrupamiento de uniones. Las líneas azules son las uniones detectadas y las verdes son los caminos del agrupamiento. En la imagen de la izquierda podemos observar como algunas de las uniones tienen límites que no se corresponden con regiones reales. El proceso de agrupamiento elimina estos límites. En la imagen de la derecha (centro) una unión con forma de T termina clasificándose como una L. En la imagen de la derecha (arriba) la unión original es eliminada al no tener ningún límite soporte de arista.

3.7   Discusión

Este capítulo se ha planteado como una continuación de los métodos propuestos en el capítulo anterior. El objetivo a conseguir es la prolongación de las uniones detectadas para conectar uniones. La búsqueda de uniones se plantea como una búsqueda de camino, donde el camino lo marca el gradiente de la imagen. Se ha formulado dicha búsqueda en términos bayesianos, no buscando el mejor camino posible sino el camino verdadero en una población de caminos falsos. La búsqueda del camino se realiza con un algoritmo A* modificado, donde no se asegura la optimalidad del resultado, pero se mejora en cuanto al coste temporal. 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 presencia 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 que se realizan en 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 modelado de aristas, las estadísticas se han obtenido a partir de otros autores y modelamos tanto la componente de magnitud del gradiente como su orientación.

Una vez definidos los dos nuevos métodos, presentamos resultados obtenidos al aplicarlos sobre imágenes tanto de interior como de exterior. Igual que en los métodos de clasificación de uniones del capítulo anterior, 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, puesto que para un camino dado, tenemos dos posibles puntos de partida dadas dos uniones.

Tenemos dos umbrales, el geométrico y el de intensidad, que sirven para modelar la rigidez del camino y la evidencia de gradiente, respectivamente. Cuando disminuimos el umbral de gradiente, 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. En cuanto al 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 con caminos con poca evidencia (magnitud de gradiente) sobrevivan a la poda.

Hemos comprobado la mejora que se produce al aplicar el método de agrupamiento frente a las uniones detectadas. Comprobamos que se produce una mejora notable en cuanto al número de límites de secciones angulares falsos que se eliminan. También mejora el error angular cometido en el cálculo de dichos límites. De esta forma estamos produciendo una retroalimentación de un proceso de un nivel a uno de un nivel inferior.

Previous Contents Next